Saturday, October 28, 2017

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.

Monday, October 16, 2017

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.