Terrain Erosion

3DWorld's terrain generation looks pretty interesting with domain warp noise, but there's one thing that's missing: erosion. I already have erosion working for individual terrain chunks in ground/gameplay mode.  I'm using this erosion implementation from Ranmantaru Games which I've slightly modified to make it more efficient and configurable, and to make it work with a global water height value. The way this algorithm works is by placing one unit of water randomly on the map for each iteration, and computing the path that this water follows to a "sink". A "sink" can be an ocean, a local minima in the mesh, or the edge of the map. Material is removed from steep path segments and deposited when the path levels off, forming a series of peaks and valleys. Local minima eventually form lakes.

It currently takes 36ms to apply 5000 erosion iterations to a 128x128 vertex/texel heightmap. Here is an example of what this looks like. It's not too interesting, though this is proof that the system works.

Erosion on a single 128x128 vertex mesh tile.

This is fine for a single tile, but I want to be able to erode an infinite terrain consisting of an endless grid of tiles. I started working on erosion of large terrains as soon as I finished the previous blog post. My first attempt was to just apply the erosion algorithm independently to each terrain tile as it was generated, after the height values were assigned but before they were used for normals and object placement. Of course, this simple idea doesn't work. There are huge gaps between tiles where heights have been eroded to very different values. There are no constraints that force the edges of the tiles to line up. Take a look at the screenshot below.

Erosion applied independently to each tile produces terrible seams at the tile borders (erosion values are discontinuous).

The problem is that the water and sediment crossing each tile boundary isn't being tracked. Each tile starts out completely dry. There may be a large river valley in one tile that accumulates most of the water for the tile, but the adjacent tile doesn't see a single drop. The valley is deep in the first tile and nonexistent in the adjacent tile. When the river reaches the next tile, it basically stops flowing, and the sediment is lost.

One possible solution is to store data at the boundaries of each generated tile and use that as seed data for any adjacent tiles that are generated later. This has been suggested in a Reddit thread I started on the topic of Procedural Generation, but I haven't implemented it because I don't think this is an ideal solution. There are several problems. First, this only works when downstream tiles are generated after upstream tiles. If the downstream tile is generated first, there's no way to push the valley back up to the water source.

Second, the results will depend on the order in which tiles are created, which itself depends on the order in which tiles are visited by the player. The problem here is that if objects such as buildings are placed via editing operations on the terrain and saved, they may not be at the correct height later when the tile is approached from a different direction. If the user takes a longer route to the building, it may be floating in the air or buried under the ground. No, this isn't acceptable.

Another approach is to blend the heights between adjacent tiles to remove the gaps. While this is efficient and will produce seamless terrain, the results don't look realistic. River valleys may contain segments that go uphill. This is also unacceptable.

In the end, I decided that I only need erosion to work on island maps, at least for now. Islands are surrounded by water. Erosion stops at the water's edge, so there can be no underwater seams between tiles. All I have to do is clip the island out of the infinite world and generate the erosion solution for the entire heightmap mesh at once. I had to add two features to accomplish this: an option to write a terrain image file from the area visible in overhead map view, and an option to apply erosion to a terrain heightmap during import. This requires some extra steps, but the result is still fully procedural. While not infinite, it would be possible to automate this process for each island visited by the player. Below is an overhead map view of my selected island.

The island of interest. The island isn't exactly square, so some parts have been truncated and part of an adjacent island is visible in the upper left corner. The red dot is the current player position and the black dot shows player orientation.

I've taken a square clip of the terrain. The island itself isn't quite square; I've managed to clip off some small parts of it and included a bit of the adjacent island in the top left corner. This is close enough. The heightmap image will be tiled using mirroring to create a seamless terrain with no gaps between the edges of the image. When the player walks to the edge, the height values will be mirrored and repeat in another copy of the image. The resulting terrain is still infinite, but it repeats a finite amount of unique data. This solution may not work for fully infinite terrains, but it's close enough. The erosion results look just fine using this flow.

The island itself is pretty large. The square area I clipped out was 7085x7085 pixels, for around 49M pixels of data representing 7x7 km of data. This is 200MB of floating-point data, or 65MB when compressed to a 16-bit PNG image. Image writing time is 22s. The compression doesn't help much, so I may be better off using a raw BMP image format to reduce read/write times. However, I don't have any image viewers that can load a 16-bit BMP image of this size, which makes debugging difficult. Reducing bit depth from 16 bit to 8 bits loses too much resolution and makes the height values appear stairstepped like in Minecraft. That's not the look I'm going for. This image may see very large, but it's still a fraction of the size of the 16,384 x 16,384 Puget Sound dataset that has appeared in other blog posts such as this one.

I ran the erosion algorithm using OpenMP with 8 threads on 4 CPU cores including hyperthreading. Runtime was 18s for 10M iterations/samples. I just put an "omp parallel for" around the iterations loop. This implementation can suffer from thread race conditions, but I don't really care because there are so many random numbers used there anyway. This gives me a 5x runtime reduction. 18s is long compared to most of the other operations, but not unreasonable for a map of this size. It should be possible to save the post-eroded terrain back to an image for fast reloading at a later time.

Here is a zoomed in overhead map view of the upper right corner of the island, showing some rivers and lakes that have formed. This example uses domain warping for the noise calculation. I'm using a fixed water height here, which means those rivers and lakes have eroded down below sea level. In the future, I may want to have a way of generating higher altitude lakes where water collects. It's currently a rendering limitation related to water waves and reflections, not a generation limitation. This map looks fairly realistic to me.

Zoomed in view of the island's upper right corner showing small rivers and lakes that are a product of erosion.

Here are some screenshots showing erosion on large, smooth, rolling hills. I find that erosion results look cleaner and are easier to debug when domain warping is disabled. Sometimes it's hard to tell which valleys come from the procedural height generation algorithm and which ones come from erosion. The valleys form nice fractal patterns. Perhaps they're too narrow and deep? It would be nice to have the algorithm produce wider rivers/valleys for areas of higher water flow, which would make the results look more natural. Unfortunately, it's not clear how to extend the selected erosion algorithm to do this.

Erosion applied to a large rounded mountain, no trees. No domain warp has been enabled, so the mesh started out smooth.

Here is another view of eroded grassy cliffs at the edge of the ocean. Ambient occlusion really makes the canyons stand out. The erosion continues under the surface of the water. This is probably incorrect, so I better go fix it. ... This has been fixed in the other screenshots below. Does this look physically correct? It could be, compared to photos of Hawaii such as this and this and this and this, any of these, and other ocean cliff photos such as this.

Heavy erosion on the grassy cliffs near the ocean. Maybe too much erosion, especially under the water.

Here is how things look when enabling domain warping noise again. This image shows one end of the island with steep cliffs, some bays, and a few lakes. Trees have been disabled to make it easier to see the terrain itself, including the details of the narrow ravines. The small bits of greenery are other types of plants that are sparse enough that I left them enabled.

This very rugged terrain produced by domain warping noise has been eroded into many small valleys.

Here is a location along the coast that looks very much like Hawaii. The erosion algorithm now stops at the edge of the water to avoid eroding underwater features.

Another view of eroded domain warped terrain, near the ocean.

Here is an overhead view from a mile up showing a small mountain range and some thin lakes. Some areas between the peaks have been filled in with eroded sediment, producing smooth, flat areas.

Overhead terrain view showing some small lakes and small, sharp peaks that remain after erosion.

Erosion produces natural rivers, and lakes at the bottom of large watersheds. There are two lakes visible in the screenshot below. Each lake is fed by a network of short rivers, but the lakes are at local minima in the terrain and there is no place for the water to drain to. The area shown below is between some large mountain ranges and gets a lot of water.

Two small interior lakes with river networks formed from erosion. The water height is constant, so these lakes have been eroded down to ocean height.

I finally have real, physically modeled, procedural rivers. These rivers are a result of the erosion process, rather than accidents arising from the noise function values. Here is an example river surrounded by pine trees for a more natural effect. The trees are probably drawn too large for this terrain.

Finally, a real river that flows to the sea! Or maybe it's just a stream. Pine trees haven been added for a more natural look. No manual effort was made here, the results are purely procedural.

If I increase the number of erosion iterations by 20x from 10M to 200M, much of the terrain is eroded away. All but the tallest, sharpest peaks have been replaced by smoothly sloped hills. All the material in the mountains was turned into sediment and deposited throughout the scene. The lakes and bays become surrounded by deep canyons.

Erosion with 200M iterations rather than the usual 10M. The mountains have mostly eroded away into smooth sloping plains that eventually end in steep ravines and lakes.

Here is a final screenshot that includes a medium density forest of pine trees. All objects placed on the terrain by either an algorithm or a human should be at the correct heights with this approach.

Final terrain with pine trees, grass, and all effects enabled.

I'm pretty happy with the erosion results on this island. However, there are a few things I would like to improve as future work.

First, I think there are too many narrow valleys. I would like to see wider valleys in locations where the water flow is high. I'm not sure how to accomplish this in a clean, efficient, and stable way. It's not clear if the original erosion algorithm can easily be modified to get this effect. Maybe it can be accomplished with multiple passes over the terrain at increasingly larger grid resolution. I'm not sure if this would have too many grid artifacts or not.

Second, I don't like the manual effort involved in clipping out the island and tweaking parameters to make it work. The problem is that the clipping operation changes the min, max, and average height values, and this affects the biome distribution. The height ranges of the various terrain layers (sand, dirt, grass, rock, and snow) as well as water level are derived from the height histogram. This is estimated by taking a large number (~10K) of random height samples prior to generating any of the tiles. If I clip out part of the scene, it may not include the min or max values. For example, my clip might not contain the highest peak or the lowest part of the ocean floor. Texture layers and water level will be assigned differently when reading the heightmap image back in, which will change the look of the island. For example, it can create an island that's all snowy peaks and no water. To compensate for this, I need to experiment with various config file parameters using trial-and-error. I can have the heightmap clipping algorithm create a table with some constants such as real min and max heights, but there's still some manual iteration required. It should be possible to fix this, though it's a trade-off between a large upfront development cost vs. small amounts of manual work over time.

Current State of Terrain Generation

I haven't done any major work on terrain or vegetation lately, but I'm constantly tweaking parameters and fixing minor problems. This post shows screenshots and a video of the current state of tiled terrain mode. The technical details have been mostly covered in previous blog posts, so I won't repeat them all here. Feel free to review some of my earlier posts if you're interested.

I've settled on Simplex noise with domain warping as the primary source of noise for procedural terrain height generation. The noise functions are all user configurable from a text config file in case I want to revisit them later. Take a look at my post from May 2017 for more information. Once the terrain is generated, trees, grass, and other scenery objects are placed on the landscape. The type and distribution of objects depends on terrain height/altitude and slope. These first three screenshots show how the noise algorithm can generate realistic looking rivers and lakes using a parallel algorithm where all height values are computed independently. Note that I'm using a 2D sine function here to form a grid of unique islands within an infinite ocean. This is why the terrain is often bordered by water. There's no technical reason why I have to use islands; the generation and rendering system works fine with an infinite forest. I just like the look and feel of islands.

Procedurally generated terrain with sandy lake surrounded by grass, plants, and trees.

Rivers aren't explicitly generated or properly connected based on water flow. They're just the product of narrow ravines produced by the domain warping function. All of the water is drawn at a constant Z height without regard for interior (lakes) vs. exterior (ocean) water. I've experimented with specialized river generation algorithms, but so far I haven't gotten them to work well in tiled terrain mode. In particular, there are heightmap seams at the borders between tiles (which are generated independently). River generation for infinite heightmaps is very difficult.

Procedurally generated terrain with a river that happens to appear.

I've switched from deciduous trees to pine trees in the next two images. 3DWorld can cycle through four tree modes using the F5 key: none, deciduous, pine, and mixed deciduous/pine/palm. In mixed mode, palm trees are placed near the water line, pine trees are placed on mountains, and deciduous trees are placed in between. This provides more vegetation variety, at the cost of increased generation time for new tiles and increased rendering time due to more draw calls. The increased generation time is due to calling multiple tree distribution functions per tile. The increased rendering time comes from extra draw calls and shader state setting for each visible tile.

Hilly terrain with lakes and pine trees.

I used the realtime terrain editing feature of 3DWorld described here to cover almost the entire surface of the ground above the water line with pine trees. I believe there are around 500K trees on the island and 50-100K trees visible in the screenshot below. 3DWorld uses 2D texture billboards to draw distant trees using only one quad (two triangles) each, which allows this scene to be drawn in realtime at 200 Frames Per Second (FPS). It's also possible to zoom out and create a larger landmass that contains 2M trees, 500K of which are in view, which can be drawn at over 60 FPS. This scene looks more like a dense pine forest, though the underlying terrain can hardly be seen.

Forest covered by around 100K pine trees placed with a large editing brush.

I recently optimized palm tree drawing using hardware instancing + Vertex Buffer Objects (VBOs) on the GPU. This allowed me to adjust the view distance of palm trees so that they're visible to the far fog distance, almost out to the horizon. Unlike pine trees, palm trees aren't usually rotationally symmetric about the Z (up) axis. I haven't been able to get billboards to work well with them. Therefore, each one is drawn in native polygon format using 20 palm fronds = 40 quads = 80 triangles each. In addition, trunks are drawn at various Levels of Detail (LODs) from single lines to 32-sided cylinders consisting of 32 quads = 64 triangles each. This allows me to draw more than 10K palm trees at over 100 FPS, as shown in the image below.

Tens of thousands of palm trees drawn out to the horizon at 143 FPS.

To finish off the screenshot gallery, I'll add an image of a sunset with long shadows and water reflections. If you look carefully, shadow maps are only used for nearby terrain tiles. You can tell which trees have shadows by looking at the lighting changes for distant trees. Terrain drawn beyond the shadow distance uses a more efficient, precomputed, low-resolution ambient occlusion lighting texture. These two modes are linearly blended to make a smooth transition for the player.

This is required to save GPU memory and CPU time for shadow map generation. I haven't used Cascaded Shadow Maps (CSMs) here because the overhead of drawing the scene multiple times (once per cascade) is too high, especially for the trees. Note that rendering tree billboards into the shadow map doesn't look correct; I have to use the full 3D polygon model of each tree, which is slow. There are a lot of polygons in all of those tree models! This is why I decided to precompute a separate static shadow map for each nearby tile instead.

Sunset on procedurally generated landscape and vegetation showing tree shadows and water reflections.

Finally, here is a video where I walk around the terrain and view some deciduous trees up close. You can watch me walk through a river similar to the one featured in the second image above. Then I enable flight mode and fly across the terrain at high speed. This demonstrates how quickly tiles can be generated as the player moves around in the world. In reality the framerate is a bit erratic, which can't actually be seen from a video played back at a fixed 60 FPS. The frame rate drops during frames where more than one tile needs to be generated, and the GPU must split its time between tile generation and scene rendering. In the end, I change the time of day. The sun goes down and the moon comes up, making interesting light reflections in the water.

This video shows that the grass blades are more than single triangles now when viewed from close up. This is a relatively new feature that was visible in some of my grass/tree fire screenshots but maybe not mentioned until now. I implemented this using tessellation shaders on the GPU. That's also how water waves are implemented in tiled terrain mode.

That's all for this post. Next time I'll probably talk about erosion simulation and water flow. I've experimented with these in the past but never mentioned them in the blog. I already have some interesting screenshots prepared. I haven't gotten erosion to work for infinite terrain tiles though. It currently only supports a single square tile at a time. I wonder if I'll be able to fix this in time for the next post.

Procedural City Revisited

I introduced 3DWorld's procedural city generation and rendering in a blog post from a few months ago, back in June, then I switched to working on physics and fires. I was reading some online articles on procedural buildings recently, so I decided to go back and improve 3DWorld's buildings. I originally wanted to add real window geometry and building interiors. Unfortunately, that seems to be very difficult given the way I'm implementing buildings. One problem is that I'm using textures that include windows, which I found online. It's not easy to have 3DWorld auto detect where the windows are in the textures and replace them with geometry when the player gets close. Also, I don't want to create, download, or import 3D models of furniture. I want everything to be procedural.

Instead of adding building interiors, I made minor improvements to building placement, textures, rendering, optimizations, etc. Here is a list of the changes:

• Buildings no longer overlap each other when placed (fixed intersection queries)
• Added more buildings (denser building placement)
• Collision detection now works on elliptical building footprints
• Added roof detail cubes to buildings (AC units, antennas, etc.)
• Improved building texture (better quality, more variety)
• Added normal maps for all building textures
• Fixed texture seams - they should all be gone now
• Major optimization to building drawing - store vertex data on the GPU - 2-3x faster

I'll describe some of these changes in more detail below, and I'll add screenshots in along the way.

Procedurally generated city with dense office buildings, roof details, window textures, normal maps, and shadows.

New Textures

The original building system used several brick and concrete block textures for houses and small buildings, plus five office building/skyscraper textures. These were fairly low resolution generic textures I found online that were at least somewhat seamless, meaning the image tiles in both the X and Y directions. They all looked fine when viewed from a distance, but I decided that some of them didn't look so good up close. I went searching for better textures using Google image search. I found a site called SketchUp Textures that had a nice collection of skyscraper texture images. I created an account so that I could download my 15 daily free textures. The textures have pretty good variety and quality, but the resolution isn't that great. They're also odd sizes with aspect ratios from 1:2.5 to 1:3.5. They do offer a paid account that has higher image resolution. That's fine, I'll make do with the lower quality free textures. The smaller size/lower resolution textures load faster anyway (I'm using 12 of them).

Procedural city buildings, showing the unlit side. There are 16 unique office building textures and several additional textures for smaller buildings.

Normal Maps

Normal maps, or bump maps, are used as a cheap way to add apparent geometric detail to a model. They interact with the light to create fake geometric edges and shapes in what's really a flat polygon. Now, normal maps don't make all that much of a visual difference on office buildings. Building exteriors consist mostly of flat surfaces such as windows and walls. In fact, very tall building exteriors are designed to be smooth and aerodynamic so that they resist moving with the wind. Maybe there's some geometry around the edges of the windows and between the sections of walls. In any case, all modern games use normal maps, so 3DWorld is going to have them whether or not they're needed.

Unfortunately, SketchUp doesn't provide normal maps for their skyscraper textures. Most sites don't seem to do this. I've used CrazyBump to create normal maps from diffuse textures on my old computer in the past. Hm, it looks like my temporary license has expired. On the other hand, I'm in luck; I can install a new copy on my new computer for another one month free trial. It's a really nice tool, so I should probably buy it. I would definitely buy it if it was $10 or $20, but it's $99. That's a lot for a tool that I would use a few times a year. And it apparently crashes constantly...

The way CrazyBump works is that you first load a texture file, it asks you to pick one of two images, it presents you with a 3D rendering with a lot of sliders that can be moved around, then finally it saves a normal map image. The pick-an-image game is there to let the user decide which way the bumps go. Are those circles supposed to be holes that go down, or posts that point up? The sliders take more work to get right, since their default values don't work well on walls and windows. Fortunately, building textures all look similar to a tool like this, so I was able to use nearly the same settings for each texture. Unfortunately, there seems to be no way to save the settings, and the tool crashed when I try to load a new texture over the old one. I had to painfully repeat this process dozens of times for the 20 (5 old + 15 new) textures I was using:

1. Open CrazyBump and wait for splash/title screen
2. Select and load a texture. If it crashes (about half the time), go back to step 1.
3. Pick the image that seems to make the windows point inward.
4. Select a cube shape for preview, which is the best shape for representing a building. If I got the window direction backward, quit and go back to 1.
5. Move the 9 sliders around to the positions I decided they should be in for most buildings.
6. Save the file. If it crashes (occasionally), go back to 1.

Yeah, this was painful and took quite a while. I had to start the program at step 1 maybe 50 times. Each crash brought up that useless Windows 10 "Checking for a solution to this problem online" dialog box that must be clicked on twice (?) to make it go away. It would have been much faster if it didn't crash so much, especially if it saved the slider positions between textures. It would have been awesome if there was a way to write a script that just did these same steps on every texture and output two images for each one (bumps going in vs. out) so that I could pick the correct one at the end. Maybe there is a way to script it, if it could actually get through the script without crashing. Anyway, I finished them all eventually.

[Update: It seems like CrazyBump no longer crashes for me, so it must have fixed itself at some point. Huh. Maybe my computer just needed a therapeutic reboot.]

Normal maps can be seen on the window frames on the building on the left. The small building in the center casts a shadow on the building behind it.

Rendering Optimizations

Up until now I had been using distance culling, view frustum culling, and back face culling on the CPU to limit the amount of building geometry that was drawn each frame. Simply iterate over each part of each building using an acceleration structure and draw it if the following conditions are met:

1. Close enough to the player (not beyond the far clipping plane/fog distance),
2. Visible within the players view frustum (field of view), and
3. Facing the player (not on the other side of the building)

The general idea is that you don't want to be drawing every single triangle of every single building every frame. Twice, if reflections are enabled. Three times, if dynamic shadow maps are enabled. With these tests, only a very small faction of the total building geometry was being drawn. I was normally getting 100-200 FPS (frames per second) for scenes such as the ones shown in these screenshots. But when viewing a large city center from above, with shadows, reflections, and grass enabled, it could drop below 60 FPS. Framerate was even worse when recording video.

Almost all of the CPU time was spent preparing vertex data and sending it to the GPU in a dynamic buffer. Building vertex data isn't stored in memory, it's generated from the overall building shape (from equations) on-demand. Every vertex of every triangle of every building has to be translated, rotated, and scaled to put it in into the correct position. Note that buildings are mostly sharp edges rather than smooth surfaces, so there isn't much sharing of vertex normals. Most vertices belong to only one triangle. I'm not even using indexed triangles here, it's not worth the added complexity.

Okay, we're only drawing about 5% of the total building geometry, but that still takes a long time. This system still needs to test a lot of build parts for visibility, and it's really slow to send dynamic vertex data to the GPU. How bad is it to build a GPU buffer of all of the geometry - every vertex of every triangle of every face of every part of every building? I initially though this would be unreasonable, which is why I didn't start out this way. It turns out to not be that bad at all. This scene has about 40K buildings, 4M vertices, and 1.8M triangles (800K quads and 200K triangles). Together this is only 113MB of vertex data - a lot less data than I expected - and can be drawn at 550 FPS. That's almost 3x faster than the old approach! Just let the GPU draw everything and don't bother culling any of it. Huh. I guess that's the way modern GPUs are to be used. Who needs code branches?

I was later able to further reduce the data to 104MB by removing the bottom surfaces of buildings, which usually can't be seen.

Procedural city viewed from above. There are 39,400 total generated buildings that stretch past the horizon.

Of course, it's not really that easy. There's the minor detail of the tile shadow maps to deal with. Each terrain tile creates and uses its own independent 2048x2048 shadow map. See, buildings don't move, and the ground doesn't move. I haven't yet implemented destroyable geometry in tiled terrain mode. Rather than rendering everything twice (shadow map pass + normal draw pass), the shadow maps can be pre-rendered once and reused. However, we can't just have one shadow map, otherwise we'll constantly need to update it as the player moves around and buildings go in and out of view. Instead, we have N shadow maps that are independently created and destroyed as the player moves around. One shadow map is assigned to each nearby terrain tile.

Ah, that's nice, and it works well, but it does cause a problem - we can't just render the entire city in one draw call per texture/material any more. No, the shadow map texture needs to be updated between tiles. Maybe there's some GPU trick for doing this that I don't know about. Maybe it can be done in Vulcan? I haven't come up with any GPU/driver trickery to make it work yet, so I had to throw CPU cycles at the problem. I used a hybrid approach between the old and new flows.

If the buildings were contained in or assigned to specific tiles then we could have one buffer per material per tile. This doesn't actually work though, because buildings can span multiple tiles and can be translated relative to the tile grid when the scene origin is updated. Instead, I have to keep the old CPU rendering code around and use it to draw nearby buildings that happen to reside in tiles that have active shadow maps. Instead of getting a 3x speedup, I only get a 1.8x speedup. Such is life. At least it's better than it was, and I still get 3x speedup outside of tiled terrain mode. If I disable water reflections it runs at over 200 FPS.

Building skyline at the beach. Buildings reflect in the surface of the water. One lonely windowless brick building is on the left. Can you spot the fish under the water in the bottom center of the image?

That's about it for this post. I didn't have too much new content, but hopefully this post helps to explain some of the problems that must be solved when procedurally generating and rendering cities. It's 10% of the work to make something that looks okay, and the other 90% to polish and fix all of the minor issues. On the bright side, this version of the city system runs at > 100 FPS in all cases and has no rendering artifacts, no texture seams, no glitches, no LOD popping, no shadow problems, and no other issues that I'm aware of. The city stretches for miles and looks just like in these screenshots, while allowing the player to move around at speeds up to hundreds of miles per hour in realtime.

Trees on Fire

As promised at the end of my previous post, I've implemented fire spreading in trees in 3DWorld. I'm happy with the way it turned out, both the visual quality and simulation accuracy.

I chose to use a more physically correct fire propagation algorithm for trees rather than a 3D voxel/volume based approach as described here. Fire is fueled and spread by individual tree branch cylinder segments, and nearby leaves are burned black. The tree trunk, roots, and larger branches can all be on fire. A branch section has the following fire-related properties:

• Hitpoints: how much heat damage this segment can take before catching on fire; scales as a function of branch radius so that thin branches are easier to burn (kindling)
• Fuel: how much fuel is available to the fire from this branch segment; scales as volume
• Burn rate: rate at which fuel is consumed; also controls the fire size/intensity; scales as surface area, since the branch surface is what's actually burning

As far as I can tell, the scaling is physically accurate to first order. Small, thin branches will burn easily and quickly. Trunks take a while to catch fire, but burn with high intensity for a long time.

Tree branches are each composed of several cylindrical sections that have their end point vertices merged to produce a closed 3D volume. One or more leaves are placed along the thinner branch segments. Each burning branch segment has a fire randomly placed somewhere on its upper surface, with wider branches having larger fires. Every frame, the active fires burn nearby branch segments and leaves that are within their damage radius. Segments take damage until their hitpoints are reduced to zero, at which point they catch fire. Leaves are burned to a black color and eventually are randomly either consumed, or fall off the tree and slowly drift to the ground. The bark color is gradually and uniformly transitioned from brown to black as leaves are burned off.

Below are some screenshots of trees in various stages of fire.

Simulation and rendering of fire spreading to three trees using a realistic fuel/volume and surface area model. Oh, look, I finally added a real health bar at the top left of the screen!

Fires are drawn as animated billboards using a fire texture atlas, the same rendering method used to draw grass fires in the previous post. Additive blending is used to provide emissive color and make the branches behind the fires appear to be red hot. Fires also produce occasional puffs of dark gray smoke that rise into the sky. When the player is close to a burning tree, a looping fire sound is played and a shimmering heat screen-space postprocessing effect is enabled.

Closeup of a burning tree with glowing red hot branches, blackened branches,burnt leaves, and falling leaves.

Grass fires and tree fires have been integrated together so that they can start each other. Burning tree roots will set the grass on fire, and burning grass will set the lower tree trunk on fire. In addition, fire can spread between the small branches of nearby trees, quickly setting dense clumps of trees ablaze.

I've put a lot of work into making tree fire spreading efficient so that it scales to hundreds of trees. The next three screenshots show a forest scene with 140 trees chosen from 100 unique procedurally generated models. Each tree has an average of 800 branch cylinders and between 4,000 and 16,000 leaves; bushes on the ground have fewer leaves. That's over 100K total leaf cylinders and around 1.4M leaves that can be damaged. I get a framerate of around 35 FPS (45 FPS after the latest optimizations) when most of these are burning.

Starting a forest fire by firing rockets at trees. The trees have begun to burn, as well as the grass around their trunks.

One key optimization is to only allow each individual fire to spread once every several frames. I chose to call the update (spread) logic for any given fire at most once every 16 frames (leaves) / 4 frames (branches). Each frame, a sliding window of leaves and branches is processed so that they all get updated at the same average rate.

Another optimization applies to the later stages of tree burning. Just like in the real world, fire spreads quickly through trees, but takes some time to finally die out. Most of the burning period of a 3DWorld tree is spent after all branches have been ignited and most of the leaves have been burned off. In this phase, the fires have nothing else to damage. Each fire tracks the last frame in which it applied damage. Fires that haven't applied damage in the previous frame are put into sleep for the next 8 frames, saving CPU cycles.

I had to make the smoke effect very sparse because smoke particles add a lot of GPU pixel fill and hurt the frame rate when the camera is close to them. With this amount of smoke, it may be more efficient to use a screen space technique such as ray marching in a volume field rather than rendering individual smoke particle billboards. In any case, at least the smoke doesn't obscure the fires too much in these images.

Some trees have been consumed by fire, and now the grass has started to burn outward as the fire spreads.

I've thought about making the tree fire spreading system multi-threaded, but so far I don't have a working solution. The problem is that the tree fires affect other scene elements such as grass, nearby trees, smoke, players, objects, etc. Some of these, such as blackening and removing of leaves, requires modifying GPU state, which can only be done from the master thread. In fact, most of the CPU time is spent updating all of these other scene objects. The fire logic applied to each branch itself has good cache performance and is very fast.

It's now a full forest fire, with nearly half the trees and over half the grass burned or burning. Note the volumetric, depth-aware gray smoke puff at the center of the screen.

Here are some videos showing how fires spread through individual trees, and through groups of trees. I watched a number of videos of real trees burning on YouTube and tried to adjust the constants to get a believable effect. At first I though the 3DWorld fire spread too quickly, but apparently dry trees can be consumed by flames in a matter of seconds in the real world. I also remember watching a tree fire years ago when I lived in Berkeley. The trunk of a tree in the parking lot of an apartment building was burning. I watched as someone ran to his parked car and quickly drove it out from under the tree just before the crown burst into flames. There sure was a lot of smoke!

The first video shows me burning three trees in the office building scene. Rocket explosions start fires almost all the time, but plasma cannon explosions only start fires half the time. The trees are over concrete so there's no grass under them to burn, making this a good test of isolated trees.

The next four videos have a lot of trees and bushes. I recorded these videos before I was finished optimizing the code, and 3DWorld can't quite keep up with the target 60 FPS video recording rate. I got around 40 FPS in the house scene and as little as 25-30 FPS in the forest scene when streaming video compression was running at the same time as rendering. (With the latest optimizations I now get over 40 FPS in the forest scene.) This means that the videos play back at around 2x the realtime rate after the fires have spread a bit. It takes 3DWorld 2 seconds to generate 1s worth of recorded video (60 frames / 30 frames per second). That's okay though, it takes a while for the trees to burn so speeding up the process shortens the videos and makes them more interesting.

Keep in mind that video compression seems to ruin the nice alpha blending and antialiased leaf and fire edges. The raw frames sent to the screen at 1080p resolution look much better. Unfortunately, the high resolution videos are over 100MB and are too large to include here.

This scene contains a yard with three trees, two hedges, and lots of grass. The hedges are each composed of dozens of small square shaped trees. The dense packing of these trees makes fire spread quickly through the hedges. I start by setting the trees on fire, which quickly ignites the grass as well. The small tree burns very quickly, and the large tree on the hill burns for a long time. There is strong wind enabled, which affects the fire spreading direction and also makes the leaves fall in a diagonal direction.

These three videos show fires spreading in the forest scene. This is a square region of light forest with a total of 140 trees + bushes and 1.86M blades of grass. Each tree has around 200 branches composed of a total of about 800 cylinders and 4,000 to 16,000 leaves. Fire burns the leaves to black over time. When leaves are fully burned they fall off the trees and land in the grass. The max number of active leaves is set to 3000, so when many leaves are falling, the leaf objects are recycled before they reach the ground.  As the percentage of burned leaves increases, the tree bark transitions from a light brown to black color. A single fire will spread to every grass blade and every tree in this scene within 5 to 10 minutes.

The first forest video shows how fires and started and how they spread through trees and grass. Near the end I disable the terrain mesh (ground) so that the burning tree roots can be seen.

This video shows fire spreading between the small branches of nearby trees. I set one tree trunk on fire and wait for it to spread. Note that I've turned off grass blades to prevent the grass from burning and igniting other trees. Fire will only spread to dense clusters of trees and will stop at the gaps.

Here I set the grass and trees on fire, then put the fires out with rain. Rain and snow have two effects on fire. First, they reduces fire intensity by a fixed amount per unit time, decreasing the temperature and radius of each fire until it's extinguished. Second, they temporarily increase the wetness factor of the scene. This effectively increases the hitpoints (resistance to heat damage) of the tree branches and grass, making it more difficult for fire to spread. Once the rain has stopped and the scene dries out, the fires can be restarted and will once again spread quickly across the trees and grass.

I've also just recently implemented burning of plants. It's pretty simple though, the plant leaves just turn black and disappear after they've taken enough heat damage. It's not much of an effect, but it does remove those pesky bits of green that remain after everything else has burned to black.

That's it for now. I might work on burning other objects next, such as building structures and other non-vegetation items. I'm not quite sure how to model those objects though. There's currently no way of tagging scene objects such as chairs and walls with parameters that control their flammability or fuel content. There's also no obvious way to burn or destroy these objects. Do they turn black? Do they explode? Break apart? Melt and change shape? Disappear? This requires a more detailed material model. I already have objects that can and do explode when burned, but no system for implementing the other effects.

Grass Fire Simulation and Rendering

About two weeks ago I was looking through some graphics blogs and was inspired by this article on fire spreading in the game Far Cry. I decided to implement something similar in 3DWorld, since it seemed like a good addition to the existing physics and terrain systems. I already have support for isolated fires, but so far I didn't have a good/efficient system for fire spreading.

Note: This work was started the week before the California wildfires and is unrelated to that disaster.

I decided to start with only grass fires that spread across the terrain mesh but don't spread to other scene objects. The existing uniform mesh x-y grid structure seemed like a fine place to store fire related data. Each grid cell contains the following fire fields:

• Hitpoints: The amount of fire/heat damage this cell can take before it catches on fire; this is a function of humidity (grass wetness), current precipitation (rain/snow), and some randomness
• Available Fuel: The amount of grass fuel available for the fire to burn; consumed over time as the fire burns; this is a function of grass density (blade count)
• Burn Intensity: The intensity of the fire from 0.0 to 1.0; this controls fuel consumption rate, heat/damage generated, spreading rate, and flame density + height

Weapons such as the plasma cannon and rocket launcher can be used to start fires in grass covered mesh cells. Explosions have a probability of creating one or more nearby fires. Once an isolated fire is burning in close proximity to the mesh, it will start doing damage to reduce the hitpoints of the containing cell. When the hitpoints reach zero, the fire will start to burn with a small intensity. The intensity increases over time until all fuel is consumed, at which point the intensity will decrease over time to zero. High intensity cells do damage to their four neighbors, which will eventually also catch on fire. Rain and snow quickly extinguish fires by reducing their intensity to zero over the course of a few seconds. They also wet the grass, making it more difficult to set it on fire later.

Here are some screenshots of fires burning in a scene consisting of dense grass with light tree cover. The fires burn the grass and flowers but not the trees. Fire leaves behind burnt black grass blades and gray ash covered ground where the green grass used to be.

Grass fire burning a circular area between the trees. Oops, looks like flowers aren't burning.

Ring of fire, after flowers were fixed so that they burn as well.

Fire burning the grass and flowers nearby, with heat haze producing rippling effects on the screen.

Fire won't burn areas that are over dirt or rock, or cells that are underwater. Also, once the grass has been burned, it remains black and can't be set on fire again. This image shows multiple fires. If you look closely, there is a shallow pool of water under the grassy area in the bottom right, which is why it's not burning. In addition, the steep slopes are covered in dirt and don't burn. The source of the nearest fire was an explosion in bottom center of the image where the grass is pushed away in a circle.

Multiple fires burning in this scene. The puddle near the bottom right produces wet grass that doesn't burn.

The rate and direction of fire spreading is affected by wind speed and direction. The fire will spread more quickly in the direction of strong winds. In the absence of strong wind, fire spreads approximately uniformly in all directions that contain grass, forming a circular burn area and a doughnut shaped ring of active fire. The fire at the center of the circle has consumed all of the grass fuel and has burned out.

This fire implementation is integrated into the physics and gameplay system of 3DWorld through the following effects:

• Green grass blades are slowly turned black at randomly varying rates
• Green terrain texture is temporarily turned black and will fade to gray ash over time
• Light black/gray smoke is produced that will float toward the sky
• The player takes damage while walking over fire in gameplay mode
• Objects tagged as explode-able explode when fire contacts them (see video below)
• A burning sound loop is played when the player is near a fire
• Heat from nearby fire produces a wavy screen space effect (see image above)
• Heat sensors can detect the heat from fires

Here's another image showing a fire burning in the back yard of my house scene. It was like that when I got there, I swear! This plasma cannon I'm holding has nothing to do with it!

Fire from the plasma cannon spreading in the back yard.

Given enough time, the fire will eventually spread to all the grass around the house, but it currently won't set anything else on fire.

I recorded two videos of the grass fire effect. The first video shows how a fire spreads, destroying an exploding tank in its path. Near the end I stand in the fire and take damage until I burn to death. Sorry, there's no sound this time.

The second video shows fire spreading in a dense grassy meadow with sparse tree cover. It will climb the hills and reach any area connected by a path through the grass until the entire scene is burned black. You can see how the fire produces emissive lighting when I cycle to night time. At the end of the video, I enable rain, which wets the grass and quickly extinguishes all fires.

This system is very efficient. The entire scene can be burning and I still get about 40 frames per second. More reasonable fires will give me at least 100 FPS. Most of the frame time is taken by the grass and terrain texture updates, as these require new data to be sent to the GPU each frame in many small batches. To reduce the time spent in these operations, grid cells are split into batches and updated sparsely. Each cell is assigned a random number from 0 to 31 every frame, with the following update cycle:
0: Update grass color (green => black)
1: Update terrain texture (grass => dirt or rock, depending on elevation)
2: Update terrain color modulation (white => black, temporary)
3: Generate a smoke puff that rises
4: Damage nearby objects such as exploding tanks
Any other number does no update. Therefore, expensive updates are only done for 1/32 of the active fire cells each frame. This is enough to keep cell update time around 1ms in most cases.

Fire is drawn as a collection of up to 6 variable sized, camera facing quads (billboards) per active cell, for the cells within the camera's view frustum. The number of quads is a function of burning intensity with some random variation. Each quad is textured with a sequence of 16 images from a texture atlas that gives a burning flame animation. They're drawn with additive blending and emissive lighting to produce bright, intense colors. Enabling additive blending and disabling depth testing allows thousands of fire billboards to be drawn without having to sort them back to front for alpha blending. I also use the depth buffer from the previous frame to blend the bottom edges of the flame quads to transparent where they meet the ground, which avoids ugly artifacts at locations where the quads intersect the terrain mesh under them.

For future work, I would like to extend this system to non-grass types of fires. For example, fire could be made to spread to trees and other scene objects. This is more difficult because it's a 3D effect rather than a 2D affect applied to a uniform grid on the ground. It's not clear if my billboard rendering will look good when the fire is up in the air on a tree branch. It's also unclear how to make other scene objects appear burned. I'll be sure to post more screenshots and videos if I ever figure this out.

Slow Motion Physics Video

I haven't done much work on the 3DWorld source code since my last post. I've been mostly experimenting with the physics system and trying to reduce instability. I took some videos of slow motion physics to help me analyze the quality and problems in my system, and I'll show two of these here.

3DWorld has an interactive timestep adjustment feature that allows the user to slow down the physics timestep by an arbitrary factor, which can be used to make objects move in slow motion. The timestep can also be reduced to 0 to disable physics and lock all objects in place. This doesn't affect the player movement or weapon firing, only dynamic object motion. I can use this feature for analysis and debugging of physics problems. For example, I can fire a rocket at an object, then freeze physics and walk up to the object for a closer view of the collision, then let the rocket continue to explode in slow motion.

The following video shows me breaking windows in 3DWorld with the physics timestep set slow enough that the individual triangular glass fragments can be seen spinning though the air and colliding with the scene. They don't collide with each other. The sharp glass fragments damage the player, which is why there is so much blood in the air and on the ground. Blood moves in slow motion as well. Bloody glass fragments will turn a reddish color.

Note that I'm recording video in realtime on 7 of 8 threads (3.5 of 4 cores) and only letting 3DWorld use one thread for physics + rendering + screen capture. Even with this setup, the video compression can't always keep up with the 60 FPS target framerate. This means that 3DWorld sometimes can't produce the results at the recording rate, which is why the video plays back somewhat faster than realtime. However, the physics is slowed down by ~10x, so you can see the fragments moving just fine. Sorry, I still haven't figured out how to capture and record 3DWorld's audio stream, which is why there's no sound.

That big gray sphere at the end is my skull, and the black sphere is one of my eyes. The camera follows the other eye as it bounces on the floor. I have no idea what happened to my red nose. Yes, I bled to death from cuts due to broken glass. It happens, especially when using the baseball bat on windows. I don't recommend trying this at home. Oh, and if you're curious, you can get hurt by wood fragments as well.

If you look closely, there's some instability in the glass fragments resting on the windowsill and on the ground. Some of them rotate in place even though they're no longer falling. Why is that? Fragments rotate about a random axis at a rate that's a function of object velocity. This means that angular velocity scales with linear velocity. Objects that have come to rest on a flat horizontal surface such as the ground are flagged as "stopped". This allows the physics system to skip some of the work when processing stopped objects, and it also disables object rotation. Objects that aren't moving but aren't in a stopped state have a small negative Z velocity impulse related to the effect of gravity that pulls them down. This velocity produces a small rotation that looks odd.

The problem is that the stopped state logic is approximate, and doesn't work well when an object collides with multiple scene faces at the same time. This is what happens near the outside corner of the windowsills and the inside corner between the wall and the floor. They're not put into a stopped state due to the possible collision with a vertical face that may push the object away at the next timestep. If they land far enough away from vertical surfaces, everything is fine. These fragments look like triangles, but the physics system uses bounding spheres for them. This means that a triangle that appears to be resting on the ground may actually have its bounding sphere touching the wall.

In addition, the wood fragments from the bench are 1D polygons. I hadn't implemented texturing of thick 3D triangle fragments yet. I've partially fixed the glass instability now - the fragments sometimes jitter a small amount, but they don't rotate. I've also added textured thick wood fragments. These look better than flat polygons, but still don't look much like real wood splinters. It's progress, but far from complete. The updated video is below.

I was careful not to die this time.

There are still some issues to fix, but it looks a bit better. Well, at least if you know what to look for. For example, real glass fragments don't land at odd angles, they land with the flat side down. Unfortunately, that's also a bit too simple and doesn't look right. Drawing triangle fragments that intersect each other on the ground looks even worse. No, they land with the flat side down, but only if they're not landing on top of each other. If fragments land on each other, they form a chaotic pile. This requires collision detection between thousands of fragments. It's something to possibly add later.

I'll post more screenshots or videos if I make progress later.

Bouncy Ball Physics

Recently, I've watched some videos of physics simulations in other game engines. This got me interested in experimenting with physics and collisions of large number of objects in 3DWorld. 3DWorld supports full physics for spherical objects, including gravity, elastic and inelastic collisions, momentum, friction forces, air resistance, etc. All "large" (non-particle) spheres collide with all objects in the scene, including each other. Spheres are simpler to work with than other object shapes due to their rotational invariance and other factors. Each frame runs multiple physics simulation + collision detection steps on all active (moving) objects. The active object test significantly reduces computation time for common cases where most of the objects have stopped moving. In theory, the collision detection should prevent objects from intersecting each other and the scene.

I added a config file option that reduces weapon fire delay to 0, which allows me to throw a ball every frame. The maximum number of active balls is set to 20,000. At ~100 FPS, it only takes a few minutes to generate 20K balls. Here is a video of me throwing some 10K balls into the office building scene in realtime. See the balls fall and bounce in parabolic trajectories. Note that I've disabled player collision detection to prevent the ball recoil from pushing me around wildly.

Collision detection works for dynamic as well as static scene objects. I can push balls around on the ground using the player model or by pushing a movable object such as a crate into them. They'll go up and down inside an elevator, and fall when pushed over a ledge. I can place objects on a glass surface or in a glass box, shatter the glass, and watch them fall. Even though the balls are stopped, the breaking glass will re-activate their physics and put them back into motion.

Balls will also stack when added to a container so that they're non-overlapping, and will spread out to fill in the gaps just like real world spheres. I have a colored glass box on the third floor of the office building scene that I use for lighting experiments. It's fairly large, so it takes a while to fill with balls. I marked the glass as shatterable in the config file so that I can break it with weapon fire. Here is the video showing the glass plate and glass box experiments. Note that the lighting is static/baked into the scene because the glass box isn't supposed to be destroyable, which is why the lighting looks odd near the end of the video.

This is a high resolution screenshot showing the balls stacked in the glass box. See how closely together they're packed. The collision force of the glass on the balls keeps them inside the volume. It takes several seconds for the simulation to converge to this solution and the balls to stop moving. When the glass is broken, the balls will spill out to form a single layer on the floor.

1000 bouncy balls in a colored glass enclosure. Collision forces keep the balls from intersecting each other and the glass.

There are a number of different ways to apply forces to objects in 3DWorld. Weapon explosions produce force radiating outward from a central point, which affects dynamic objects. Here I use a rocket launcher (named "Seek and Destroy") to create explosions that push the balls around the scene. The following video shows the effect of these explosions on the physics state. This also shows off my neat explosion shockwave postprocessing shader effect. The shader distorts the image by simulating a spherical region of compressed gas with higher index of refraction forming a lens.

The rocket launcher is a crazy weapon to use with zero fire delay! I wouldn't recommend this in real gameplay, it's usually instant death. The small random rocket firing error causes two rockets to occasionally collide in mid-air - they're also dynamic objects. This results in an explosion and chain reaction that sometimes propagates back to the player along the chain of close proximity in-flight rockets, resulting in a high amount of area damage. Oops. Better stick to bullets, or some other non-explosive weapon.