Playing with fire – WebGL fire simulation

August 17, 2016

Back in the early nineties, the demoscene was in love with a simple fire effect, that generally looked something like this:

Fire demo by Iguana - screenshot by pouet.net

That doesn’t look much like real fire, but with some simple tweaks you can get something that looks good, runs on most graphics hardware and is easy to implement:

Clear

Try touching the fire, or clicking and dragging with your mouse. If you’re on a phone or tablet, you can rotate your device and see how the fire aligns itself correctly.

Even though the effect is easy to implement, fairly cheap to simulate and looks really good, I rarely see it in games. It doesn’t translate very well to three dimensions (since all you get is a flat texture), but it works great for 2D games. It seems like there should be tons of indie 2D games with awesome fire effects, flamethrowers, burning zombies, torches or whatever, but since I haven’t found any, here’s my attempt to document how you make a simple and awesome fire simulation.

A very simple model of fire

The very simple model of fire used for the effect contains four parts: a heat source (generally something that is burning, i.e the top of a torch), convection (the fact that hot stuff tends to rise and cool stuff tends to sink), diffusion (heat will gradually spread out), and cooling.

The basic idea is to start with a grid of pixels, each pixel representing heat at that location. To get the fire started we plot heat (i.e pixels with maximum intensity) at the locations in the grid which have burning fuel.

To simulate diffusion, the grid of pixels is blurred. This simulates heat spreading to neighboring grid points. Convection is simulated by scrolling the grid upwards, and cooling by simply subtracting a constant from each pixel.

To render the fire, we map pixel intensities in the heat texture to a color ramp that goes from black, via red and orange to white, simulating black body radiation.

Example color ramp

Then we repeat the process, injecting heat, blurring and convecting and so on.

It is simple to combine the blurring and convection into a single step. In pseudocode:

sum = pixel(x+1, y) + pixel(x-1, y) + pixel(x, y+1) + pixel(x, y-1)
pixel(x, y - 1) = (sum / 4) - cooling_amount

This is easy to translate into WebGL, we store the heat in a texture, and use a pixel shader to blur and convect the heat. To inject heat where fuel is burning we render the burning parts to the heat texture with additive blending, modulated with a high frequency noise texture to simulate flicker. By translating the noise texture a random amount every flame, we get randomly flickering burning fuel.

Implementing this will give you something that looks a bit like this:

It sort of looks like fire, but the movement is strictly vertical, it doesn’t really move in the billowing, fluid-like way real fire does. Also the shape of the “flames” is very blobby and soft.

Uneven cooling

The easiest way to dramatically improve the look of the fire is to introduce uneven cooling. Instead of simply using a constant cooling factor, we use a cooling map, a grid of pixels of the same size as our heat grid. You want the cooling texture to be fairly smooth and to contain a mix of large blobs and high frequency noise. Here’s a good cooling texture:

This particular texture was generated in processing.js by drawing circles of random sizes and intensities and blurring the image repeatedly.

The cooling grid/texture should tile and scroll upwards at approximately twice the speed of the heat grid. Varying the rate at which the cooling texture scrolls affects the look of the flames, a slower scroll speed gives a more billowing look, and a faster scroll speed makes the fire look more turbulent.

As far as I know, the first description of using a cooling texture instead of constant cooling was by Hugo Elias.

Uneven cooling improves the look of the fire dramatically, implementing it will make the fire simulation look something like this:

Adding more fluid movement

In the current model, fire always rises upwards at the same speed, it never moves sideways or stops, and there are no swirls or turbulence. We sort of fake turbulence by scrolling the cooling map, but that doesn’t affect the direction the fire moves. To get the flames to move sideways and swirl, we must move the fire by a vector field instead, i.e. the direction we sample neighbors from when blurring and scrolling must vary across the grid.

A good candidate for computing this vector field is curl noise. Curl noise is fairly cheap to compute and is divergence free, i.e. the vector field generated won’t contain any sinks or “gutters”, areas where heat will get stuck. Being divergence free is equivalent to being incompressible when using the vector field to advect a fluid (i.e. fire in our case) and incompressibility is an important visual cue for fluids (although incompressibility probably is more visually important when simulating water).

The curl of a scalar valued potential field $F(x, y)$ is simply

$$(\frac{\partial F}{\partial y}, \frac{-\partial F}{\partial x})$$

The potential field $F$ is just noise, e.g. Perlin or Simplex noise. If we view the noise field as a height map, with high values indicating hills, and low values indicating valleys, then the gradient vector $(\frac{\partial F}{\partial x}, \frac{\partial F}{\partial y})$ points along the slope of the height field. If we define the perpendicular product of a vector as $perp(x, y) = (y, -x)$, (i.e. the perpendicular product of a vector rotates it by 90 degrees clockwise), then the curl is simply the perpendicular product of the fields gradient vector. In other words, moving along the curl of the noise field is the same thing as moving along points of equal elevation, the contour lines of the field (think of if as moving along the contour lines of a topological map).

Now we just need to implement curl noise advection in WebGL. A simple approach is to evaluate a 3D noise function (we want the noise to vary both spatially and with time) per pixel and use the pixel shader’s partial derivative instructions to get the curl of that noise. GPUs process pixels in groups of four, so computing partial derivatives in the pixel shader can be done cheaply with the finite difference method.

float noise = noise(texcoord.s, texcoord.t, time);
vec2 curl   = vec2(dFdy(noise), -dFdx(noise));
vec2 offset = texcoord - upvector + (curl * scalingfactor);

This is simple but probably not optimal. Instead of computing the curl noise per pixel we can evaluate it at evenly spaced points and then simply interpolate the vectors to get a per pixel value. That way the curl noise can be computed in a vertex shader and we can simply render a tessellated quad to get an interpolated velocity vector per pixel. When we compute the curl in the vertex shader, we lose the ability to use cheap partial derivative instructions to get the derivatives. To fix this we can either use the finite difference method directly (but this of course requires multiple evaluations of the noise function) or we can use a form of noise where it is simple to directly get the derivatives, e.g. simplex noise.

The fire simulation on this page uses the simpler per pixel implementation. Since the fire shader does plenty of texture sampling, we have quite a lot of free arithmetic instructions to spend anyway, and it makes the code simpler.

Other improvements

Improved curl noise

Currently we use a single evaluation of the noise function at a medium frequency to compute our curl noise. This gives some nice swirling motion, but lacks higher frequency details. By summing several evaluations of noise function at different frequencies, we can add high frequency detail to the curl noise. This is generally referred to as fractal browninan motion and works like this:

$$fbm(x, y, z) = \sum_{i=1}^{n} w^i \cdot noise(s^ix, s^iy, s^ix)$$

Usually $s=2$ and $w=1/2$, so each term of the sum is called an octave of noise, because the frequency doubles with each term, just like a musical octave.

Of course, this requires multiple evaluations of the noise function and is therefore more computationally expensive, but it does add a lot of detail. There are many ways to mitigate this, perhaps computing high frequency detail per pixel, and low frequency detail per vertex.

Using a non uniform scaling of the curl noise to stretch it a bit vertically might also improve the shape of the flames, making them more elongated.

Improved dynamic range

Since we are doing all computations on modern graphics hardware, there is really no need to use a standard 8-bit per channel RGBA texture when computing our simulation, 16-bit floating point makes much more sense. Fire is potentially very bright, so we want to represent values larger than 1.0. Rendering to floating point textures is not necessarily supported in WebGL (some mobile chipsets don’t support it), so another alternative is to encode a larger range than [0, 1] into several channels of an 8-bit per channel render target.

Tone mapping is straight forward since we already have a rendering step that maps heat to color, we just need some sort of exposure function to map values outside [0, 1] to our color ramp.

Bloom

To really sell how hot and bright the fire is, we can add bloom. This is simply a matter of blurring and optionally downsampling the fire texture and blending the result on top of the rendered fire.

Better looking fuel

The base of the flames (the burning fuel we add to the heat texture every simulation step) doesn’t really look like fire at all. They are just a flickering mess (which happens to produce pleasing flame like shapes), but they look nothing like fire. Maybe we can use animated noise to make the base of the flames more realistic, or we could just hide the flicker at the base by sampling the fire outside the base when we’re performing the final rendering step.

Physics based calculations

The current fire simulation isn’t really based on physics, it’s just a bunch of hacks that look good. We could try to improve realism by using math more based on the actual physics. For example, the rate of cooling is actually proportional to the temperature to the fourth power, while our model just uses a randomly fluctuating cooling factor based on the cooling map, independent of the temperature.

Another inaccuracy is the speed of convection. When hot gas rises, the speed at which it does isn’t constant like in our model, but proportional to the temperature difference. Hotter air rises faster.

Of course, using physics based calculations might not improve the look of the fire at all. Since the simulation isn’t physics based to start with, we might be better off going with a full fluid simulation instead of making small changes to our fundamentally incorrect model.

Get cracking

There’s no limit to all the stuff you could add: sparks or glowing pieces of fuel floating along the fire’s velocity field, smoke, motion blur for the flames, lightning the environment based on the fire texture, sound, a cellular automata based model of fuel consumption causing the fire to burn stuff away, a water simulation that causes the fire to extinguish, heat distortion and on and on and on.

So get started implementing an awesome fire effect for your game, I want to see flamethrowers, fireballs, fire brigade simulations and more!

Read more

Better contour rendering

November 22, 2010

At SIGGRAPH 2007, Chris Green at Valve published a paper, Improved Alpha-Tested Magnification for Vector Textures and Special Effects . The paper is about a neat trick for making alpha tested textures containing contours (like text, or logos) look much better. Here’s why you should use it:

Read more

Choosing how to branch in Mercurial

October 13, 2010

Mercurial has many different ways of handling branches. While there is plenty of information available on the different branching models, much of it is incomplete, and it can be difficult to decide what branching model to use when starting to use Mercurial.

Steve Losh has written an excellent guide to branching in Mercurial, but it mostly deals with how the different branching models work, how the branches are stored and what commands are used to handle them.

This guide intends to give more practical information on when to use what model and what the pros and cons are for each one.

Separate repositories

This is the simplest branching model and the one used by the Mercurial developers. You handle separate branches by simply having separate repositories. You might have one repository called stable that contains released versions of your software, and one called dev that contains code under development that will eventually go out in the next release.

Mercurial supports this type of branching very well. You create a branch by simply cloning an existing repository, delete it by deleting the repository and move changes between branches by pulling or pushing from one repository to another.

The main problem with this model is that branches are very heavyweight, especially if you have lots of source code and large repositories. Cloning an entire repository can take a while. If you have very long-lived branches like stable and dev in the example above, that is probably ok, but for shorter lived feature branches it becomes cumbersome.

Another consequence of this model is that there is no permanent record of where a certain commit originated. If you pull changes from one branch repository to another you can see the separate lines of development, but you cannot always easily tell which commits came from stable and which came from dev.

Named branches

Named branches try to fix the problems with using separate repositories as branches. They work by optionally stamping commits you make with a branch name.

Since named branches are just some extra meta data on commits, switching between branches is fast, the time it takes is proportional to the difference between the two branches. And you can always tell in which branch a commit was made, since the branch name is part of the commit.

However, this also means that you can never really delete branches (since that would mean altering older commits). And there is no way to rename branches either, so if you made a commit in a named branch called foo, everyone you ever share that commit with will have a named branch called foo in their history.

There are ways to manage this somewhat, you can mark branches as closed which means they don’t show up by default in certain places, but they’re still there. Closing branches is mostly an indication to Mercurial that you’re not interested in those particular branches any more.

Since branches are often given very common names like dev, master or 1.0, this can cause problems if you intend to share your code with many other people in an ad hoc fashion. They might want a different branch called dev.

But for long lived branches, where you only care about collaborating with a known group of people, named branches work well. They do not work as well for short lived feature branches (since the branch name will be a part of the commits forever) or if you do not want to impose your branch naming on people you share your code with.

Anonymous branches

Anonymous branches are just a Mercurial repository with multiple heads and no named branches. You refer to the branches by revision id or some other available name like tip.

This works well for very short lived feature branches (anything that is merged within five minutes up to a day), where you know that the branch very soon will be integrated with the main line of development. For these cases, naming the branch is often unnecessary since you know what you’re working on anyway.

Anonymous branching has excellent support in Mercurial, and is very easy to work with, but it has obvious problems for longer lived branches. It’s hard to keep track of which branch is which and it’s cumbersome to communicate which one you’re talking about if multiple people are involved.

Anonymous branches work very well for very short lived feature branches that never leave your local repository, but poorly for anything else.

Bookmarks

Bookmarks aren’t part of core Mercurial but the Bookmarks extension ships with Mercurial and is easy to enable. It is the branching model in Mercurial that is most similar to the one in Git.

Bookmarks are essentially pointers or references to commits, stored outside the commit graph itself. This means that you can add, delete and rename bookmarks without altering history (unlike named branches).

As of Mercurial 1.6, it is also possible to push and pull bookmarks between repositories. If you’re using earlier versions of Mercurial you will have to transfer bookmarks manually or with the help of something like rsync.

Bookmarks enables fast switching between branches in a single repository and don’t place many restrictions on other people that you want to collaborate with. Bookmarks can be deleted and renamed without altering history, since they aren’t a part of the commit graph, they just reference it. But there is still only one namespace for bookmarks, so if you want to share your bookmarks you probably want to ensure their names are unlikely to collide with other peoples bookmarks.

However, the support for bookmarks in older versions of Mercurial isn’t that hot. You need to transfer them manually between repositories and they interact badly with extensions that rewrite history like ‘‘hg strip’’ or ‘‘hg rollback’’. I have tried to use bookmarks in many older versions of Mercurial but always given up because I’d end up with crashes in the bookmarks extension because one of my bookmarks was referring to a commit that no longer existed.

I also missed the ability to have a bookmark refer to upstream development and have it update automatically when I pulled from there. Mercurial bookmarks only update when you make a commit, something which works well for your own line of development (because then you make the commits) but leads to problems if you want to refer to a line of development done by someone else with a bookmark. Because you’re not making the commits, only pulling them into the repository, the bookmark will not move forward as you pull in new commits, forcing you to update the bookmark manually.

If everyone you’re collaborating with is using Mercurial 1.6, and they use bookmarks to keep track of branches, this isn’t a problem because then they will update the bookmark when they make commits, and you will get both the bookmark and the commits when you pull.

Conclusion

If you’re unsure what branching model to pick, use separate repositories. This model has great support in Mercurial, you rarely need to add options or extra parameters to commands, and everything works in a very clear and simple manner. As an example, when repositories are branches, push and pull by default only update the current branch, and you have to give explicit options to move commits between branches. With any other sort of branching, Mercurial updates all branches on push or pull, which is rarely what I want. This forces me to constantly supply the branch name to some commands, which is extra work.

If you frequently create feature branches that live for some time (days at least) and then die, and are annoyed by the time it takes to clone the repository to create a branch, consider using bookmarks. It’s one of the more flexible branching models in Mercurial and has good support in the most recent versions.

If you only want a couple of very long-lived branches, and you only care about collaborating with a known group of people (like say the other programmers in your team), use named branches.

Read more