Wednesday, January 13, 2016

Simulation and Rendering of Snow

As promised, here is my post on snow simulation and rendering in 3DWorld. Last month, before the holidays, I was working on rain. In fact, I'm still working on rain. I traveled back to Pittsburgh, PA to visit my parents for two weeks and expected to see snow, but there was only rain (except for the last day). It's also raining here in California. The weather really isn't motivating me to work on snow. I'll just discuss the original snow system for various modes, since I think snow works pretty well already.

There are several aspects to snow in a 3D game engine. First is drawing all of the snowflakes as they fall through the air. Second, the engine needs to deal with adding snow to the ground/terrain texture so that snow covered peaks are white. Third, snow should be drawn as actual 3D geometry when it's deep and near the player. The challenging part is figuring out where snow will actually accumulate, given the terrain, scene geometry, weather factors (temperature, wind, etc.), and snow depth. This is what I call snow "simulation".

Snow Ground Coverage

First, I will compare 3DWorld's automatic snow map generation based on altitude and terrain slope to a reference photograph. Higher altitudes are cooler and therefore have more precipitation in the form of snow (as opposed to rain). Also, snow does not remain on steep slopes; it falls down the slope, leaving exposed rock behind. Here is a photograph of Mount Rainier covered in a layer of snow.

Photograph of Mount Rainier viewed from the southwest, from Wikipedia.
Here is 3DWorld's realtime rendering of Mount Rainier from a high resolution heightmap, where snow cover has been calculated from the terrain.

Mount Rainier drawn by 3DWorld using only a heightmap. Snow coverage was simulated using terrain slope and altitude.

Note that I did this image comparison after setting the snow parameters in 3DWorld and didn't go back to tweak anything. It happened to turn out very close to the actual snow coverage, validating the height and slope model. I cheated a bit with the clouds though, and set the average cloud height experimentally based on the reference image. The trees aren't really to scale (I wasn't too interested in fixing them here). Also, 3DWorld's mountain appears to be taller because there was no reference to convert the height map values from the image I found online to real height values, so I took a guess at it and overestimated. Oh, and someone pointed out that I'm missing the glacier on the top of Mount Rainier - I haven't gotten to simulating glaciers yet.

Falling Snowflakes

3DWorld has two forms of physical falling snowflakes. The original snowflakes are all dynamic physics objects that use the same game object class as balls, rockets, shell casings, etc. They have very accurate physical models that include collisions with the exact scene meshes, gravity, friction, wind resistance, and thermal effects (melting in high temperature areas). Unfortunately, it takes a large amount of CPU work to simulate tens of thousands of snowflakes this way. I had to find a faster alternative.

The second and newer snowflake model is more GPU based. Each snowflake is a single {x,y,z} point rendered as a point sprite on the GPU. The physics and collision detection is still performed on the CPU, but it's simpler and more efficient. For example, the velocity of each snowflake is not even tracked - all snowflakes have the same velocity based on gravity and wind. Collision detection is performed coarsely against a 3D voxel (volume grid) model of the scene, and the time consuming detailed collision detection is only performed when the voxel test returns a possible collision. Snowflakes are destroyed and respawned high in the sky when they collide, rather than bouncing or sticking as in the slower model. This approach scales up to 100K snowflakes and looks almost indistinguishable from the more accurate model. You can really only tell the difference when running physics in slow motion or freezing the frame. The lighting computation in the shaders is all the same as well.

In the end, I used a mixture of around 1:5 of old model vs. new model snowflakes. That way, most of the snowflakes are fast, but there are also some that actually stick to the scene objects. Here is what a scene looks like with 40K snowflakes. Can you tell which flakes use which model? I think the only way to tell would be to visually track an individual snowflake's path though the scene.

Snow falling in the office building scene and beginning to accumulate in the grass.

The white spots on the grassy ground mesh are the beginning of snow accumulation. When an old model snowflake collides with the terrain, it colors the terrain texture white in that area. After several minutes of snowfall the ground will be mostly white, except for the grass itself, which remains green. The office building surfaces are unaffected. There is no realtime snow accumulation - that is more expensive (in terms of CPU time) and done as a preprocessing step (see below).

One of the more challenging aspects of snow is drawing individual close-up snowflakes. Sure, snow looks fine in the distance when drawn with white points. But when you actually look closely at a snowflake, it's not a white dot. It has real structure. In fact, every snowflake has a unique fractal crystal pattern. I decided to use a single snowflake texture for nearby snowflakes. It looks nice, but it's not very realistic - more of a cartoon effect. Here is a screenshot of a snowflake on the player's eye/"camera lens".

A snowflake falls in front of the camera. There are 40K total snowflakes falling from the sky.

Snow Accumulation

Next, I will explain how snow accumulation works in 3DWorld. To get an immersive snowy scene, snow needs to have real depth, and needs to cover every object. Just painting it onto the terrain mesh texture doesn't work. But adding a constant layer of snow on top of every horizontal surface doesn't look right either - snow depth changes with the slope and geometry of the objects nearby.

Rather than trying to come up with a physical model for snow accumulation, I decide to approach it using a simulation of random falling snowflakes. One billion snowflakes are dropped from the sky with uniform distribution over the scene. The path of each snowflake is traced, taking into account wind and other factors, until a collision with the scene is found. Then, depending on the collision normal/direction, slope of the surface, friction, and wind, the snowflake either sticks or bounces off and continues falling. Snowflakes that stick are added to a sparse 3D accumulation volume implemented with a hash map. For the house scene below, I used a 1000x1000x500 volume. The actual number of nonempty cells (with at least one sticking snowflake) is around 4M, which can easily be stored in memory. The entire process takes around 20 min. on a 4 core CPU.

This first step produces a volume map of snow accumulation. The next step is to convert this volume to an actual surface. First we need to determine how much volume each of the 1B snowflakes contributes. Given a snowflake volume V, and scene size W by H, and voxel size X by Y by Z (=1000x1000x500 in this case):
volume = width*height*depth
V = voxel_width*voxel_height*delta_z
delta_z = V/(voxel_width*voxel_height) = V/[(W/X)*(H/Y)]

As you can see, the final snow depth is a linear function of the volume of a snowflake. Changing the value of V will vary the snow coverage from a light dusting to heavy accumulation to snow that covers the entire scene. The conversion from snow volume to a surface only takes about two seconds. Once the expensive (20 min.) simulation of 1B falling snowflakes is performed we can vary the snow depth interactively, or save the snow map and use it for different scenes with the same geometry but different snow coverage. 3DWorld saves the snow accumulation in a very compact, sparse structure that is only 13MB for the house scene.

The process of converting snow volume to a 3D surface works by extracting contiguous rows of voxels into triangle strips, then collecting adjacent triangle strips into mesh sections. The height (z-value) of each vertex in the triangle strip is determined by the amount of snow accumulated in that voxel in the snow map. If all of the nearby voxels in an area have similar volumes, this produces a flat snow cover (for example roads). If the volumes vary significantly between adjacent voxels, this produces rough snow (for example on trees). Any vertical (Z) stack of nonzero volume voxels will merge into a deep snowdrift, where the Z height of the mesh is taken from the sum of the volumes. This models snow stacked against the side of a house or tree. Areas that have stair-step patterns of filled voxels where adjacent nonempty voxels are one Z column above or below each other will produce steep triangle strips (for example on sloped roofs). This approach is able to extract multiple overlapping surfaces at different heights, such as the snow on top of the fence and the snow below the fence at the same {x,y} position. Here is what this algorithm produces for moderate snow depth on the house scene.

Snowy house scene with falling snow and heavy snow accumulation on the ground and scene collision objects.

This approach works very well for smooth surfaces, which account for most of the scene. The areas that need improvement are near scene objects that are smaller than a few voxels in width or size. In this case, the voxel snow volumes don't have enough resolution to accurately map a triangle mesh surface onto the small objects. This is an example of the Nyquist Samping Theorem. The result is single triangle patches of snow that in some cases are larger than the objects they are resting on. Using a higher resolution volume would help with this issue, though it would consume more runtime, memory, and disk space.

Snow Surface Rendering

Finally, I will discuss how the snow surface is rendered in 3DWorld. It's not all that difficult. The meshes that were formed from triangle strips are grouped together into vertex buffer objects (VBOs) and stored on the GPU for improved performance. They are static for the scene. [Well, there is dynamic snow deformation due to collisions that can be enabled, but that's a topic for another post.] Snow is then drawn using the normal rendering pipeline for 3DWorld with shadow mapping, normal mapping, and sharp specular lighting to get those nice bright highlights. The strength of the normal mapping is reduced for distant snow to avoid specular aliasing and texture tiling artifacts. Here is what the surface of the snow looks like up close, when looking toward the sun.

Snow drawn as a 3D geometry layer on the ground. Snow depth is based on simulating 1 billion falling snowflakes with collisions and tracking volume accumulation.

The snow surface itself casts shadows on the rest of the scene, which requires it to be drawn without texturing or normal mapping a second time to create the shadow map. When there are no dynamic objects, the snow shadows are cached between frames to improve frame rate. Snow rendering is surprisingly fast, considering the snow mesh contains nearly 4M vertices. On my new Nvidia card the addition of snow decreases the framerate from 500FPS to 250FPS. This is less frame time than grass (170FPS), so if the snow covers the grass the framerate actually increases!

Update: Here is a screenshot of player footsteps in the snow, simulated while the player is walking based on stride, foot length, foot spacing, player speed, and player direction.

Player footsteps in the snow.