Friday, March 24, 2017

Realtime Terrain Editing

I've changed topics once again and have gone back to working on realtime terrain editing. 3DWorld's heightmap based terrain has been editable using a brush system for a few years now. I'm currently working on additional editing functionality. Grass and trees can now be added and removed along with terrain height editing. This works for deciduous trees, pine trees, palm trees, grass, and flowers.

This is going to be a technical post. Sorry to those of you who were expecting another post with pretty pictures of fancy custom materials. I'll throw some samples of my wonderful terrain editing artwork in among the blocks of text to break things up a bit. Keep in mind that everything was created in realtime, and none of the scenes in the images took more than a minute or so to construct. I'm not an artist, but I'm sure an artist could make something really cool with these features.

Scene showing custom edited tree, grass, and flower coverage created in under a minute.

All editing modes use a brush system, with keyboard keys switching between modes and add vs. remove operations. The following modes are available:
  • Increase Terrain Height
  • Decrease Terrain Height
  • Smooth Terrain (constant height)
  • Add Trees (deciduous, pine, or palm depending on tree mode - another key)
  • Remove Trees
  • Add Grass (and flowers)
  • Remove Grass (and flowers)

Brushes have five parameters:
  • Brush Shape (square or round) 
  • Brush Size/Radius (in heightmap texel increments, from 0.5 to 128)
  • Brush Weight (applies to height increase/decrease and grass add/remove only)
  • Brush Falloff (for round brushes, controls falloff with radius: constant, linear, quadratic, sine)
  • Placement Delay (controls smooth brush application/painting vs. discrete stamp operations)

Terrain height editing operations only work for heightmap terrain read from a source image. The editing operates directly on heightmap image data stored in memory so that it can be saved back to an image on disk. Each user brush operation is stored in a list of edits that can be written to and loaded from disk, allowing the user to save their work. Brush operations that increase and decrease terrain height also support undo, which works by inverting the brush weight and reapplying it as a new brush at the same size and location. The updated height data is used everywhere, including in overhead map mode, which serves as a simple image viewer for the terrain in false colors.

3DWorld can load, display, and edit a terrain up to 2^15 by 2^15 (32K x32K) pixels in size, though the largest terrain image I have is the 16K x 16K Puget Sound dataset. This is an enormous 256M pixels! I can't even open the image in any standard image editing programs. Windows Explorer hangs when I try to click on the image because it can't even generate the thumbnail preview. Height data can be in either 8-bit or 16-bit resolution. Most of the larger datasets are 16-bit for higher precision.

Trees and grass can be added and removed without a heightmap because they operate directly on the procedurally generated data, overriding the procedural results. However, these brushes can't be saved (yet), and if the player moves far away from the edited region and comes back, the changes will be lost. I'll see if I can improve this in the future by saving and reapplying brushes when the terrain tiles they operate on are generated. Because of this, users will generally want to edit the height values before editing the vegetation.

Another example of my awesome artwork. This is a section of the Puget Sound heightmap, with custom hills and valleys and user placed trees and grass. The spikes in the back are one mesh quad wide and over 1 km tall.


All editing operations work on heightmap texels, or individual mesh elements when heightmaps aren't being used. Depending on the scene size/grid resolution, these units range from 1m to 10m. For example, the Puget Sound dataset is 10m resolution. This is around the spacing between trees, which means that individual trees can be added or removed. One mesh texel also contains a few hundred blades of grass, which isn't realistic but looks good enough. Addition and removal of grass is based on brush weight, meaning that the number of grass blades can be smoothly adjusted per grid cell. Flowers are generated or removed to match the grass density.

3DWorld also supports "zoomed out" heightmap editing on larger groups of power-of-two texels (2x2, 4x4, 8x8, etc.) This allows large heightmaps to be quickly modified without requiring a huge number of brush strokes to update millions of pixels. This increases CPU usage during editing, and is limited to a reasonable zoom factor of around 16x16. Zoomed editing is useful for creating larger features such as mountains and lakes that span many terrain tiles.

Who says you can't have a forest of 100K *unique* palms trees packed so close together you can't see the ground? I can create whatever I want in my map.

Heights (mesh z-values), trees, and grass and updated per-tile during editing. One tile consists of an NxN grid of height values, where N is typically equal to 128. Tiles that are modified have their data recomputed and sent to the GPU (height texture, material weight texture, ambient occlusion map, shadow map, etc.) The largest brush size available corresponds to one tile width (128), so in the worst case 4 tiles are updated per brush, if the brush happens to fall at the intersection of 4 tile corners. If brush delay is set to 0, this is 4 tiles per frame. The procedural generation and rendering system is capable of updating 4 tiles per frame at a realtime framerate of at least 30 Frames Per Second (FPS). Average editing framerate is often over 100 FPS. Most of the CPU time is spent recreating the various texture maps rather than on the editing operations themselves.

Smiley face "cookie" created with custom mesh brushes. This one is several hundred meters across, and has ponds for eyes and trees for hair.

The most important remaining task is adding a save + load system for trees and grass. That may also be the most difficult task. Considering the procedural nature of the vegetation system, it doesn't interact well with user edits. Edits are modifications on top of the procedural content; they can't be applied until the procedural content is first generated. This means that a saved edit file can only be replayed if the terrain tiles are loaded in the same order they were loaded during the initial editing. Unless the editable area is constrained to be within a few tiles of the starting location, this is difficult to guarantee. It requires some cooperation of the user - which means it only really works well when the user knows what they're doing.

I could, of course, save the entire state with every object placement. Then, when the save is loaded, skip all procedural generation and use the objects from the save file. It's unclear exactly how this would work if I continue editing the scene. If trees are removed and then re-added, are the new trees procedurally generated again, or do they need to match the trees from the save file that were removed? Also, there are performance/runtime issues to consider. I'll continue to think about this.

Finally, here is a video showing how I created a smiley face "cookie" within the Puget Sound scene. This one is similar to the steps I used to create the other smiley in the image above. Note that the water is at a constant height, so holes that are deep enough become filled with water.



If you're curious how I added the brush overlays as colors spread across the mesh, theses are done using the stencil buffer. A cylinder is drawn around the brush (cube for square brushes) in the proper editing color. Then the stencil buffer is used to mask off all but the pixels that are blocked by the mesh and trees, creating a decal effect. This way, the user can see exactly what area is being edited.

Here is another terrain editing video in the same scene. I loaded this heightmap with some existing edits, then added more.



I had only 1 of 4 CPU cores allocated to terrain generation/update, and the other 3 were allocated to video compression. This made update laggy since it's normally multi-threaded.That's why the video appears to play back so quickly in some places. It was recorded assuming a constant 60 FPS, but in reality I was getting 30-50 FPS during mesh height and tree editing. Grass editing takes almost no time. Also, the glitchy water tiles near the end of the video are only present during video recording, so I have no idea what's going on there. This is the first time I've seen that artifact.

Bonus: If you're curious how large the Puget Sound dataset is, take a look at this overhead map view. The area I was editing in in the center around that red circle. It's a tiny fraction of the entire heightmap. In reality, the heightmap is tiled/mirrored so that it actual goes on forever.

Puget Sound heightmap showing small user edited area in the center near the red circle.

Saturday, February 25, 2017

Yes, More Custom Materials!

It's time for more fun with custom materials in the form of reflective and refractive cubes and spheres. Every time I get distracted by some other new feature, I keep coming back to these materials. Part of the reason is that I've never seen a system that can do something like this before. I'm not saying no other game engines or material editors like this exist, just that I've never seen one.

In theory, 3DWorld should be rendering these materials using close to physically correct lighting models. Of course, there could be bugs. I have no idea how to check for correctness. Some of the materials I can create may not exist in the real world, such as a half metal half glass. Or a material that absorbs/scatters blue light and reflects red light. Maybe they exist, but I don't have any around for reference, and good luck finding a reference image for something like that online.

What's changed since I last blogged about this stuff? I think I finally have refraction working correctly with per-object cube maps, at least for cubes and spheres. These two shapes are simple enough that I can ray trace them inside the shader to compute correct ray intersection points and reflection/refraction angles. The shader code is pretty complex as it handles up to two reflections and two refractions corresponding to both the front and back faces of transparent materials. In addition, it handles volumetric light scattering and light absorption/attenuation. This is what we see in volumetric/solid, partially transparent materials such as ice, glass blocks, colored plastic, liquids such as milk, etc.

There are an incredibly large combination of material parameters that I can create in 3DWorld, so I can't possibly show them all in this post. At best I can show a dozen or so examples. Here is the set of parameters that can be edited in realtime that affect lighting (excluding parameters used for physics):
Texture, Emission, Reflectivity, Metalness, Alpha, Specular Magnitude, Shininess, Refraction Index, Light Attenuation, Diffuse Red, Diffuse Green, Diffuse Blue, Specular Red, Specular Green, and Specular Blue. These user parameters are explained more in my previous blog post on this topic.

Parameters are changed through my simple onscreen editing system where the arrow keys select the variables and move the sliders. It's similar to a monitor's onscreen menu system. Maybe it's not the best or nicest looking UI, but it's simple to use, easy to work with in the code, and has almost no impact on framerate. Plus, it avoids having to pull in a 3rd party UI library and figure out how to make it work in fullscreen mode when 3DWorld only supports a single window + render target. I did, however, add a texture preview image and some small color indicator circles. Everything but the texture image is ASCII art. If I ever release 3DWorld to the public, I'll have to add a better UI.

Here is an example of a refractive glass cube and sphere together. Refraction currently only works correctly with sphere and cube shapes; other shapes are approximated without knowing the exit point of the view ray from the object. You can see the reflection of the sphere in two of the back faces of the cube. The fragment shader traces each view ray through the object. The ray is both reflected and refracted at the front surface of the shape (the current pixel's 3D position in the fragment shader). The refracted ray is then intersected with the back face of the shape using a ray-sphere or ray-cube intersection. The hit position is reflected back into the shape, and also refracted out of the shape into air. The reflection and refraction angles depend on the indexes of refraction at the material/air interface. Each of the rays that exits the shape is looked up in the correct face of the reflection cube map to determine the color to use for blending. This produces first-order physically correct reflections and refractions, as seen in the image below.

Glass cube and sphere drawn using a cube map with two reflections and two refractions, in shadow.

Does that look like a real glass cube? Maybe. I do have a clear plastic cube that I used as a reference last year. Unfortunately, I seem to have misplaced it after moving to the new house. The sphere certainly looks like images of glass spheres I found on Google (example). It has the typical inverted, zoomed out refraction image of glass spheres. However, I don't have the physical parameters (such as index of refraction) for the glass used in those images, so I can't do an accurate comparison. A small change in index of refraction makes a large change in the reflections and refractions, especially the second order ones. The difference is amplified with each reflection/refraction.

I've also experimented with more than two reflections/refractions, but this didn't seem to improve the results, so I left it out. It definitely changed the results, but it wasn't clear that they were more correct. I don't think the average human can detect correct third order reflection/refraction effects. Also, multiple bounces in spheres tends to magnify part of the image, which makes the pixel borders of the cube map texture more obvious. I would rather have a smooth and clean image than one that is every so slightly more physically correct. Besides, this adds extra complexity and reduces framerate.

Here are some screenshots where I was experimenting with different diffuse and specular colors. The blueish diffuse and reddish specular makes these glass objects look like anti-reflective coated lenses as used in cameras and some sunglasses.

Textured glass "marble" with reflection, refraction, and scattering using custom material texture and colors. The smiley face is my placeholder player model!

The glass eyeball.

Normal maps can be applied to object as well to perturb the reflection/refraction normal vector and get some interesting effects.

Glass ... pumpkin? Well, this is a wooden fence normal map applied to a sphere.

I made some attempts at creating ice. I don't have any ice normal maps, so I had to make do with the normal maps I happen to have. The stucco normal map shown in the first video at the bottom looks like a natural chunk of ice. These two cubes look more like ice sculptures or something else man made.

Ice cube? More like ice bricks.

Another ice cube, using a different normal map texture. Since it's supposedly transparent, it doesn't cast a shadow.

Light absorption and scattering within the material volume is also supported. This is sometimes referred to as participating media. The way this works is by calculating the length of the view ray clipped to the bounds of the sphere or cube for each fragment in the shader. This is the distance light must travel to cross the 3D volume of the object. The amount of light absorption/scattering varies exponentially as exp(distance) and is used to blend between the cube map ray hit color and the material's bulk color.

I can add hundreds of cubes and spheres and they're all drawn in depth sorted order for correct alpha blending. You can see the reflections and refractions between all of the objects. Is this physically correct? I have no idea, it's not obviously wrong as far as I can tell. I've seen similar effects in image searches such as this one. The exact value for index of refraction makes a huge difference.

Refractive glass cubes and spheres that absorb and scatter light. They also reflect and refract each other.

Here is a screenshot of the San Miguel scene from the previous blog posts, this time with some interesting glass and metal objects on the ground. The gold sphere can be seen twice in the glass sphere. On the left is a refraction, and on the right is a reflection off the inside surface of the sphere. It looks like it could be physically correct. If I only had a glass sphere and gold sphere I could probably figure it out. Is anyone interested in donating these to me in the name of science?

Material spheres placed in the San Miguel scene. The reflective gold sphere is reflected and refracted in the glass sphere.

I created two videos showing material editing. Both videos were recorded in realtime. As long as a single sphere or cube is placed or moved at one time, the framerate remains high. There is a list of predefined materials read from a text file. The UI allows for editing of existing materials to create new named materials. These can be saved in the scene for later use. Dynamic objects can have their parameters modified after placement if their named material is the one being edited. This is because they store a reference back to their material. However, the cube map is rendered every frame, so this only works well for a single dynamic object. Multiple objects reduce framerate due to all the required scene rendering passes. Static objects, on the other hand, can be placed all over the scene until graphics memory is exhausted (a few hundred objects on my system). The downside is that their material parameters can't be modified once they're placed. Both types of objects can be moved by the player and also destroyed.




Here is a similar video, this time in the San Miguel scene shown in the previous two blog posts. The only collision object is the ground. The tables and chairs weren't added as collision objects because they're not really grouped in a convenient way in the model file, and I haven't computed their bounding volumes. 3DWorld really prefers volumetric collision objects rather than polygon-based ones. I could add all ~7M polygons as individual collision objects, and it would probably work, but the performance would be terrible. I'm not sure if 3DWorld could actually fit the data + acceleration structure in 32-bit address space. So you can ignore the fact that I'm pushing cubes through tables and chairs, because I haven't bothered to fix it. Also note that the final cube's refraction image looks a bit odd because it's partially sticking though the wall.




That's all I have for now. I have a lot more images and videos of more materials with strange parameters, but I feel I've shown enough of the interesting ones.

The question is, what can I do with these? Is it possible to build an entire building or game level with them? I guess I need to add support for shapes other than cubes and spheres. Technically, I do have other shapes, but I hard-coded the parameters into the source code rather than adding a proper UI for controlling them. I've already created a scene with over 10K cubes so I know it scales, as long as they're not all reflective and refractive. 10K opaque/diffuse objects and 100 reflective/refractive objects should be fine for a realtime scene. Of course, it would be an incredible amount of work to build something useful from them if every object needs to be individually placed. I suppose I can continue to use these objects as decorations. And yes, they can be saved and reloaded, keeping most of the parameters. I can no longer edit object materials properties after reloading.

Wednesday, February 1, 2017

San Miguel Rain and Snow

This post continues my San Miguel scene experiments using techniques from previous posts on rain and snow. I decided I wanted to see how this scene looked with wet and snowy surfaces and how well the environment coverage mask worked on a highly detailed, complex model.

Here are two screenshots showing a rainy San Miguel. The wet look on the stone ground, tables, and chairs is achieved by decreasing the material diffuse lighting and increasing both specular intensity and specular exponent. This is a pretty simple effect, but works well in practice, especially on the ground. Wetness is higher for horizontal surfaces, and surfaces that have an unoccluded view of the sky above. These are the surfaces that naturally receive and accumulate the most water.

The raindrops themselves are drawn as vertical lines that quickly fall in a mostly vertical direction depending on the wind. They look much better in a dynamic scene than they do in the static screenshots shown here. Each drop is visible for only a few frames.

Rain and wet ground. Raindrops are drawn as lines and look much better when moving.

Rain and wet ground + objects from another angle.

I also enabled snow coverage and let the simulation run for a few minutes. Snow is accumulated over time and is drawn as a white layer on top of the normal textured scene geometry as a postprocessing step in the fragment shader. Snow thickness/density is a function of polygon normal and is highest for horizontal surfaces that face the sky above. Since the camera is above the scene in this screenshot, most of the visible surfaces such as the tree leaves are pointed up and have a high snow density.

Snowy scene from above, after several minutes game time of accumulated snowfall.

I enabled the snow coverage mask for the next two screenshots. This works by precomputing a depth-based coverage mask for the scene that stores the vertical distance from the sky plane for each pixel. The fragment shader accesses this texture to determine whether the current fragment is at or below the recorded occluder height. If the fragment is below this height, it is occluded by other scene geometry from above and receives no snow. The texture is blurred using multiple projection angles to simulate a randomization from the typical vertical snowfall. This smooths the edges of the snow coverage mask in areas of high frequency geometry, such as under the trees. However, if snow is left to fall over an extended period of time, this saturates the coverage layer and produces sharper boundaries (as seen below).

The first image was created using a low resolution 512x512 coverage mask, and the second image was created using a much higher resolution 2048x2048 coverage mask. The second image contains higher frequency content for a more accurate representation of snow coverage, though it takes much longer to compute. Preprocessing time is still under a minute on 4 cores. I don't think it looks all that much better though.

Snowy scene using a low resolution 512x512 snow coverage mask.

Snowy scene with a high resolution 2048x2048 snow coverage mask. The snow "shadow" from the trees can be seen.

I'll continue to experiment with snow effects. It would be interesting to see how well true volumetric snow accumulation works on this scene. This will likely take several hours of CPU time, and generate a large amount of voxel coverage data.

[Update: It in fact only takes 7 minutes to create the snow volume for 1 billion simulated snowflakes. I underestimated how well the bounding volume hierarchy scales to scenes with many polygons. However, the snow coverage is very noisy due to the large number of small leaves and other objects. I think the white color non-volumetric snow actually looks better. If you're interested, here is a screenshot.]

Volumetric snow simulated using 1 billion snowflakes.

Monday, January 9, 2017

San Miguel Scene

This post doesn't contain much technical content, because I was busy with moving to a new house and then the holidays, so I didn't have much time to write code. Instead, I'll post some images of the San Miguel scene modeled by Guillermo M. Leal Llaguno of EvoluciƩn Visual. I downloaded the Lightwave object file model and textures from the McGuire Computer Graphics Archive.

It took me a few days at an hour or so per day to get the scene to render correctly in 3DWorld. I had to add several minor new features, including a user-specified environment map cube, per-model normal map options, texture invert, custom sunlight intensity, custom mipmap creation for the leaves, and a per-material metalness parameter. Some of the features worked well, but others need more work. In addition, there are some errors in this version of the model, including missing triangles, missing textures, and incorrect texture coordinates. However, these problems don't affect the overall scene quality too much, as long as you're not looking at the details.

I computed indirect lighting for both the sky and sun for this scene using a preprocessing ray tracing operation that took around 10 minutes on 4 CPU cores. Once the preprocessing is finished, the lighting can be used for all view points and various weather conditions. There is no fake ambient term here, all indirect lighting is computed over a 3D grid. This isn't a closed model - meaning, many of the polygons are two sided and don't form a watertight volume. This leads to light leaking through the walls in some places. I don't have a good solution for this problem yet.

I used a single 8192x8192 shadow map and a 6 face 1024x1024 cube map centered in the courtyard for environment reflections. 3DWorld computes the shadow map and cube map when the scene is loaded, and updates them dynamically when objects move or any lighting/environment parameters change. This update requires the scene to be drawn multiple times, but there aren't any dynamic objects enabled by default so this isn't a problem.

Here are some screenshots showing the San Miguel scene from various locations and directions. These are some of the most photorealistic images I've gotten from 3DWorld so far. It can render this scene at an average of almost 200 frames per second at 1920x1080 on my Geforce GTX 1070.

View of the San Miguel scene from the corner showing shadows and indirect lighting.

View from the trees looking down. The indirect lighting appears to soften the shadows.

San Miguel scene viewed from near the fountain with a low value of sun and sky indirect lighting but strong direct sunlight.

View from the upper balcony showing closeup of plants. The sky is cloudy, which makes indirect lighting stand out more.



Here are some screenshots showing cube map environment reflections on glass and metallic objects. The reflection and transmission model is physically based and uses true Fresnel equations. Reflections don't use per-object cube map centers yet, so they're not very accurate, but they still look pretty good. There are some alpha blending artifacts due to not sorting the faces for individual objects from back to front. The materials are themselves sorted correctly as the viewpoint changes. Some of the objects are misaligned with each other, such as the salt shaker. This appears to be a problem in the model file and not a 3DWorld bug.

Reflections in glasses and silverware. For some reason, the salt shaker's salt, glass case, and metal lid are misaligned from each other.

More environment reflections of objects on the table.



Cube map reflection in the window. The reflection is a bit undersampled and distorted because it's far from the single cube map center point.

Cube map reflections in the silverware on a table. Can you spot the sun?

Here is a short video where I fly through the scene and examine some objects. At some point I'll have to add a system to improve the smoothness of camera movements when recording videos.


Here is another video with a slower camera speed and my attempt at smoother movement.



This work has been pretty fun and interesting. It's quite different from writing graphics and physics algorithms. I can't wait to find more large and interesting models like this one, and the museum scene from a previous post, to show in 3DWorld. If I find enough of them, I can combine them into some sort of town and maybe build a game into exploring the environments.

Tuesday, November 15, 2016

Tiled Terrain Update and Screenshots

The past few weeks I haven't been working on 3DWorld as much as usual, partly because I'm preparing to move to a new house and have been distracted with other things. The work I've been doing with 3DWorld is mostly related to minor improvements to visuals and optimizations for generating and rendering large outdoor scenes. I've made many small improvements to tiled terrain mode. Each individual change has only a minor impact on the scene, but together they do improve visual quality considerably. I'll discuss some of these changes and show new screenshots in this blog post.

Terrain Normal Maps

I've modified the terrain texturing system in 3DWorld to support separate detail normal maps for each terrain texture layer (sand, dirt, grass, rock, and snow). I found suitable normal map textures online for all layers except for grass, for which I couldn't find a texture that I liked. The grass texture layer is drawn with a fine field of triangle grass blades, which cover up the mesh so that the normal map isn't visible anyway. This adds many more texture lookups inside the terrain fragment shader, but my GeForce GTX 1070 shows almost no change in frame rate. I'm sure this feature hurts frame rates on older/slower/cheaper cards though.

Here are some screenshots of steep normal mapped hills showing all of the texture layers. I have disabled trees and water so that the terrain is fully visible. Grass and plants are left enabled.

A different normal map is assigned to each of the five ground texture layers that make up this steep hillside.

Terrain normal maps viewed from a different angle.

Normal maps applied to rocky mountains, viewed from above from a distance. The terrain appears to have very high detail.

These new normal maps add a good deal of complexity and realism to the scene with little cost. They make the mesh appear to be highly detailed, almost for free.

Leafy Plants

After reviewing several other terrain generation and rendering systems written by other people, I decided that 3DWorld's terrain needs more detailed ground cover. The area on the ground under the trees was too bare, even with all of the grass. I had this as a todo list item for maybe a year before I finally got around to adding another plant type. Here they are. I call them "leafy plants".

View of a grassy beach with some new procedurally generated leafy plants.

There are four different types of leafy plants that appear at different elevations, including one type that is underwater. They're created by applying tree leaf textures to spherical sections that are scaled to an ellipsoid shape. This gives the leaves a smooth curve, rather than having them be boring flat polygons. However, they are also more expensive to create and draw than other types of plants that use single polygons (quads) for leaves. I had to use a sparse distribution of leafy plants to keep performance under control. These new plants seem to blend in well with the other plants, grass, and flowers. They're just one more component to the 3DWorld ground cover, meant to fill the gaps between the trees.

Improved Pine Tree Branch Randomization

I made another pass at procedural generation of pine tree branch sizes, positions, and orientations. This new approach uses more random numbers to produce a less symmetric branch coverage, which removes some of the repeating patterns found in my previous pine tree forests. Each branch is rotated a small random amount around the vertical (z) axis of the tree, and shifted a random distance up or down in z as well. This makes the trees look more natural and realistic, especially when shadows are enabled. Keep in mind that every tree in this scene is unique. Instancing is only used to save memory when there are more than ~100K trees.

Pine tree forest on the mountain, with high detail shadows and more randomized tree branch placement.

Note that in this screenshot, and the images from the following sections, I've increased the high resolution shadow map distance. This improves shadow map quality, at the expense of increased GPU memory usage and slightly longer tile generation time. My current GPU has 8GB of memory, so spending a few hundred MB on improved shadows seems like a good decision. The shadow map smoothly transitions to a lower resolution baked mesh shadow at about half the max view distance. It's possible to push the shadow maps out to the full view distance, at the loss of a smooth frame rate.

Large Numbers of Trees

I decided to test the limits of how many trees I could get onscreen at once. I optimized some of the tree placement and pine tree leaf/branch generation code so that it scaled better to many trees. At this point the number of trees is probably limited by the time taken to send the vertex data from the CPU to the GPU. I'm not sure how to profile this, or optimize it further.

Here is a scene showing pine trees on a terrain with tall mountains that extends into the distance.

Tall mountains covered with pine trees. The terrain height has been scaled and zoomed out to produce sharp peaks.

This is a scene showing tens of thousands of deciduous trees drawn using 50 unique generated tree models. 3DWorld can create hundreds of unique tree models with an 8GB graphics card. However, this increases initial scene load time, and I prefer to keep loading under a few seconds. [Update: I can see duplicate trees in this screenshot, so I increased the number of unique trees to 100 and tweaked the type randomization code to remove them.]

Distant, foggy mountains with trees.

Here I have decreased tree size and increased tree density in the config text file. The active area of the scene contains 4-5M pine trees, and around 1M trees are visible in these next two screenshots. This scene renders at a consistent 78 FPS, mostly independent of which way the camera is facing.

Maximum tree density: Pine trees cover every dry patch of land. This scene contains at least 1M trees and renders at 78 FPS. The white spot on the distance is a patch of bare snow that is too steep for trees.

A million pine trees near sunset. Note the complex cloud lighting and the dark tree shadows.

Fall Leaves

Yes, it's that time of year again. The trees outside my house are turning bright colors (mostly red) and covering the sidewalk with leaves. Once again I'm showing off screenshots of colorful fall trees in 3DWorld. I have tree leaf color parameters tied into the editing UI this time, which allows me to change colors interactively using the arrow keys on the keyboard. Here are two screenshots showing fall deciduous trees in a variety of colors.

Trees with colorful fall leaves spread across the rocky ground.

More fall leaves with grass, flowers, and plants.

I'll continue to work on trees in tiled terrain mode. Maybe I can add winter trees that have no leaves and are covered with snow in time for Christmas. Of course, we don't get snow here in San Jose, CA.

Thursday, October 13, 2016

Fun with Stacking Spheres and Cubes

This is more of a fun post compared to some of my previous technical posts. I'll be sure to add a lot of YouTube videos below and a few static images at the end. This is my first interactive scene editor feature, but is more for fun and amusement rather than real level editing. I don't imagine I could create any useful level by placing various one meter cubes and spheres one at a time in front of the player's camera.

The following videos show my progress on dynamic object placement. I've made huge improvements in my workflow and "artistic quality" over the past week. There are many additional improvements to be done and features to add. I believe that eventually this system can be made into a full level editor, but it has a long way to go before it's useful for this purpose.

None of these videos were recorded with sound. I still only have two options for video recording: Fraps with sound, limited to 30 seconds; and ffmpeg with unlimited length but no sound. I'm sure I'll figure it out eventually.

The first video shows a stack of 1 meter cubes of a variety of different materials that I slowly placed one on top of each other. It was more fun to push the stack down than it was to build it. Note that I didn't have dynamic shadows working for the cubes at this point. I later added the ability to destroy cubes with weapons instead of only being able to push them around and knock them down.


After a while I grew tired of placing blocks one-by-one, so I made the placement delay another in-game user editable parameter. I found it was much easier to create large piles of cubes and spheres with the delay set to 0. In reality it's one per frame, or 16ms delay for a framerate of 60 FPS.

This next videos shows how I can create large stacks of cubes. I still hadn't added shadows. The cubes are created so that they stack but don't intersect each other. If I have collision detection turned on, I'll quickly wall myself into a corner. But if I disable collision detection I can just insert the cubes into one place and they'll form a stack as the bottom cube is inserted at the bottom and will push all the other cubes up... or maybe the new cube is inserted and pops up to the top of the stack. I'm really not sure - the code is pretty complex, and it all happens within a single frame. At least the cubes don't intersect with anything, which is the most important property. Oh, and if I made the cubes small enough, I could probably walk up them like stairs. I really should try that and record a video if it works.


I had the material editing menu up for much of the video so that I could easily change the materials. It would be nice to hide the menu somehow in the future while still having a way to change the textures. The material itself can be selected with a hotkey from a user-created list of predefined materials that is read with the scene data, but it doesn't have the variety of textures I wanted to use for this video.

There is a small yellow number printed near the center of the screen that counts the number of objects placed. Here I've placed 1533 cubes and spheres. This was added to track how many objects can be created within reasonable performance constraints.

I finally enabled shadows for the cubes and spheres. I spent some time creating high stacks and then knocked them down in this next video. It was pretty fun! All of the weapons push the cubes around, but the rocket launcher has the most force per unit time. The seek-and-destroy has about twice the force, but fires too slowly. If I make the cubes small enough, around 0.4m on a side, I can push them out of the stack with a rocket or two. All the cubes above the one that was pushed out will fall in quick succession. The system is very stable, but this many cubes hurts the frame rate at this stage of development.


I tried to stack spheres next. At first it didn't work because the collision detection for this case wasn't fully implemented, and the spheres just sat there overlapping each other, forming a giant blob of spheres. My attempted fix had a surprising an unexpected effect, shown in the video below. Groups of spheres stuck together in a quivering unstable ball, then floated off on a random path toward the sky. Sometimes the sphere clusters got stuck on static level geometry and pulsated there. What's going on here? I recorded the video, but I hadn't enabled a lower screen resolution and the video compression couldn't keep up well. The frame rate dropped, leading to a laggy recording where some parts ran at up to 2x realtime. Sorry. I've reduced the sphere drawing time by 5-10x since recording this so it shouldn't be as much of a problem in the future.


What was causing this bug? I had the collision response vector sign backwards, and colliding spheres were being pulled together like magnets rather than pushed apart. They would overshoot and separate slightly, only to be pulled back together in the other direction. Some instability (floating-point error?) caused the clusters of attracted spheres to drift off in random directions with a random walk. Some sank into the floor/ground, some floated off into the sky, and some got stuck in the static level geometry such as the lamp posts and building walls. If I had come across this bug without just having rewritten the sphere intersection code, I would have never figured it out. The effect was pretty funny though. I might even add an option to enable it from within the material editor. Magnetic materials? Negative gravity materials? I'll have a hard time justifying this as anything resembling real physics!

I later got spheres working without much trouble. They stick to each other like masses of fish eggs. This actually reminds me of the little colored sticky foam balls that my daughter used for building sculptures and got spread all over the house. The user can disable player collision detection and float around creating sculptures of 1 meter spheres that fill the level. I'm not sure what use this is in real gameplay, but you can get a few thousand spheres scattered about before the framerate starts to drop.


Maybe it's unrealistic to stick brick spheres together like this. What should really happen when placing spheres this way in a sane world? I guess they would all fall down and roll around until they covered the ground - but that's no fun! Maybe I can make another option to control this later.

The final video of this post shows the exploding cube effect. I can mark objects as exploding in the material editor, and then fill the scene with them. Any hit from a weapon will detonate the object and also destroy the surrounding objects within the blast radius. One explosion takes out several cubes at a time, which allows me to destroy them all much more quickly. This clears space for placing even more stacks. I call it the "undo" feature. If you need more precision, there's also a "shatterable" material mode that will only destroy the object that was directly hit with weapon fire.


I spent some time stacking cubes and pushing them down, but it's not too much different from what I've shown in the previous videos. Here are two images of my "artwork". The first image shows a few thousand stacked cubes of various sizes and materials. This was earlier in the development when the framerate was too low to add more, and shadows still weren't enabled.

Thousands of stacked cubes of various materials and sizes litter the courtyard. The office workers are hiding in fear.

Imagine having this stack of cubes outside a real office building! Would anyone want to walk anywhere near it? In a real environment, the wind would probably push these stacks over, and one falling stack would bring all of the others down like dominoes. This stuff is fun to build due to the pure absurdity of the whole system. But, keep in mind, this is just a prototype of the level editor that in the future will be used to construct structures such as the office building itself. It's in no way meant to represent physically correct physics or real gameplay. I'm not creating another Minecraft clone here.

This next image shows a scene that took quite a while to create, even with one cube placed per frame. There are over 10,000 cubes here, in stacks that reach hundreds of feet into the sky. Some of them go above the cloud layer and beyond the far clipping plane so that the boxes at the top aren't even visible to the player. The stacks take up to 10s to fall if you remove a block near the bottom and watch the rest of them drop one by one. However, they do still completely fall. Shadows and indirect lighting from the lamps in the courtyard are enabled.

More than 10,000 cubes stack to the sky. This artwork took me a while to create and was a shame to lose when I realized I hadn't completed the "Save Level" feature yet.

It was a shame to create this wonderful bit of cube insanity and then throw it all away when I quit 3DWorld. See, I didn't implement a "Save Level" feature until after creating this scene. On the plus side, this problem encouraged me to finish the save feature in a hurry. Now the save system is complete, and I can save, load, and modify all of my cube and sphere creations as much as I want.

This post is short on technical details, so I should probably talk about why the performance was poor in the beginning, how I improved it, and how the physics works.

There are two types of user placeable objects in 3DWorld: dynamic objects and movable static objects. There are various other object types, but they can't be created by the player. The previous post on sphere and cube materials was all about dynamic objects. These include weapons, ammo, projectile effects, smiley body parts, etc. Anything that has free movement physics is a dynamic object. These objects support Newtonian physics with gravity, elastic and inelastic collisions, momentum, friction, air resistance, buoyancy, etc. Basically, all of the physical parameters that are normally modeled in games and physics engines, plus a few obscure ones that have little impact on the physics but were fun or challenging (= fun) to add.

There are three problems associated with building using dynamic objects:
  1. The physics really only works correctly for spheres (as implemented in 3DWorld).
  2. This system is too expensive for simulating thousands of interacting objects.
  3. There are problems with stability when creating stacks of objects.
The solution to these problems is to use a different physics system that solves for static constraints rather than realtime dynamics. I've extended my framework for movable (player pushable) static objects to work with user-placed material cubes and spheres. It works better with cubes since they have flat surfaces and the constraints are simpler, but it's acceptable for spheres. I could in theory add support for other 3DWorld shapes: cylinder, cone, capsule, torus, polygon, extruded polygon. However, that's a lot more work, and these other more complex shapes have more parameters that need to be set by the user. Cubes and spheres only have one parameter: size/radius.

When I say static objects, I really mean persistent objects that are created once and last forever, and will remain in place if no dynamic forces act on them. Static movable objects have a more limited set of physical parameters and a simpler physics model. There is no momentum, torque, friction, or elasticity. All collision responses other than gravity are resolved statically within a single frame. They can be pushed around by the player, stacked, and dropped - but that's about it. As I've shown in previous posts, buoyancy in water works, as do some other minor effects. Since there is no torque or friction, and materials are infinitely hard/rigid, they can be placed in stable stacks of unlimited height. As long as there is an object below supporting the objects above, everything stays in place. Remove one object (cube) from the bottom, and the cubes above will fall one-by-one until the entire stack has fallen down to the next supporting block (or the ground). Since static cubes don't rotate when stacked, any contact point on the bottom of the cube will support it, even if it's just a tiny corner of another cube. At least this simplifies the math.

Static objects are faster to simulate than dynamic objects, but they're still not free. My 10K blocks scene was dropping the frame rate all the way down to 40 FPS. Almost all the time (maybe 80%) was in querying the scene bounding volume hierarchy (BVH) for adjacent objects that were either supporting or resting on the current query object. The BVH was built incrementally while the objects were added, so it may not be optimal, in particular for these dense stacks.

The important observation here is that most of the time, an object is not moving at all. In fact, the majority of the game frames observe no block motion. The blocks only move when dropped, pushed, or shot at by the player, and there's a limit to how many blocks a player can get moving at the same time. The fix is to track which objects are moving vs. "sleeping" and not simulate the sleeping objects every frame. I used an active counter to track how many frames it's been since each object was last updated/moved. If an object goes for 8 consecutive frames without moving, it's marked as sleeping and only checked for collision once every 16 frames. This cuts the simulation time down by a factor of 16 in mostly static scenes. To avoid large delays with falling objects, every active object wakes up all other objects within a certain distance of it when it moves. If the player fires a rocket at a cube, the collision/explosion will wake up the cube, which will wake up the cubes above and below it as it falls. The chain effect will incrementally wake up the entire stack (but just that one stack), and make all of the blocks fall in quick succession.

This change improved the framerate from 40FPS to 90FPS. Good enough for now. I think the framerate is currently limited by actually drawing all of the cubes, or maybe the occlusion culling. I should be able to create 15K+ cubes while still hitting a solid 60 FPS. Spheres are more expensive to draw, so I can only have about 2000 of them in the scene.

Monday, September 26, 2016

Physically Based Materials

I'm continuing to work on improving object reflections in 3DWorld. The past few weeks I've been trying to integrate reflective objects into the engine as physically-based materials. As a first step, I provided a way to create and throw spheres and cubes with user-defined material properties as dynamic objects in the scene. The properties are specified in a config text file in keyword/value format. There is also a simple UI for realtime editing of material parameters and creating new materials. The UI is an in-game text overlay with arrow key input similar to the onscreen display you would find in a computer monitor. It's very simple but usable. I would like to use the mouse to select menu items, but I think it would interfere with the user's ability to play the game and interact with the world while the menu system was active.

The material parameters supported are:
  • Material Name - User-defined text string identifier
  • Texture - Name/filename of texture to use; "none" to disable texturing
  • Normal Map - Name/filename of normal map texture to use; "none" to disable normal mapping
  • Shadows - Flag to enable cube map shadows for point light spheres
  • Emissive - Flag to mark as having an emissive color (no lighting)
  • Reflective - Flag to mark surface as reflective (using an environment cube map)
  • Destroyability - Tag to mark as destroyable, shatterable, exploding, static, etc.
  • Metalness - Value in [0,1] to represent dielectric vs. metal
  • Hardness - Value in [0,1] to set hardness for elastic collision physics
  • Density - Value of material density, used to compute mass and buoyancy in water
  • Specular Magnitude - Magnitude of specular light reflection in [0,1]
  • Specular Shininess - Shininess of specular light reflection, converted to surface roughness
  • Alpha - Value in [0,1] to specify alpha value of partially transparent objects such as glass
  • Light Attenuation - Factor for computing transparency and scattering within the material
  • Index of Refraction - Value for controlling reflection and refraction in glass, plastic, etc.
  • Light Radius - Radius of light emission for light source spheres
  • Diffuse Color - {R,G,B} diffuse, emissive, or light source color value
  • Specular Color - {R,G,B} specular color value ((1,1,1)=white for non-metals)
For example, the material "Gold" is specified as:
hardness 0.8
density 19.29
alpha 1.0
reflective 1
metalness 1.0
specular_mag 1.0
specular_exp 128.0
diffuse_color 0.0 0.0 0.0
specular_color 0.9 0.6 0.1
add_material Gold


I recorded several videos showing how 3DWorld's dynamic, throw-able spheres and cubes work, including realtime editing of material parameters. I feel that videos are required to show these features. It's just too hard to tell what's going on in static images. I can only cover a small fraction of the materials, parameters, and features available in these short videos.

Sorry, none of these videos were recorded with sound. The only sounds I have enabled in these tests are for throwing and bouncing anyway. These videos are too long to record with the free version of Fraps (which has sound). The FFmpeg video recording wrapper support in 3DWorld can record unlimited length videos and compress them in realtime, but I haven't figured out how to record audio yet in Windows.

Here is a video of me throwing spheres of various materials around in the scene and editing the material parameters in realtime. Everything in the scene is reflected in mirror surfaces, including the placeholder smiley player model.


This is a video showing dynamic sphere point lights and cube mapped shadows in a dark room. Lighting, shadows, reflections, and various other parameters can be assigned to materials and edited in-game.


I later decided to add support for dynamic material cubes as well as spheres. Here is a video of me throwing some cubes around and changing their textures and normal maps. Cubes and spheres use partially elastic collision models and will propagate collision forces around when piled up on top of or against each other. They can be stacked, pushed around the scene, and the player can stand on them, though there are some issues with simulation/physics stability.


Density is one of the material parameters that can be modified in realtime through the material editor. The material's density affects the amount of resistance to pushing and its buoyancy in water. In this video, I edit the density of the brick cubes, which affects how high they float in the water or how quickly they sink. The player can stand on and stack objects on the cubes as well, and everything works correctly. Spheres can also be used.


This is a video of my incomplete puzzle/platformer scene. It uses a variety of different effects and materials. The marble floor and some of the glass surfaces are plane reflectors. I haven't finished all of the traps and obstacles, and the various sections aren't even fully connected. I had to use the "flight mode" cheat to get to the second section. I'll post more screenshots and videos of this map later when it nears completion.


 I'm continuing to work on dynamic objects and materials. I would like to add support for the other shape types supported by 3DWorld: polygon, extruded polygon, cylinder, cone, capsule, and torus. I'm also considering adding more physics properties to the editable materials list, for example parameters for friction, air resistance, deformation, elasticity, player damage, etc. Regular dynamic 3DWorld objects such as weapon projectiles and pickup items use fixed materials, which already have all of these properties. Finally, I would like to add a way to make these objects into efficient static scene objects so that this mode acts like an in-game scene/map editor. I'm curious to see what the performance is when there are thousands of placed objects of dozens of different materials in the scene.