Infinite Fields of Grass

Before I write about grass, I want to post a more recent screenshot of trees. That last blog post on trees got me working to improve their quality, mostly by adding more variation to height, branch placement, leaf size, textures, etc. The 5 different species of trees look more different from each other after these changes, and add increased variety to the scene. Here is how the trees are looking now:

The latest version of  5 species of procedurally generated trees in an open landscape. There are around 5000 visible trees.

Now, onto infinite fields of grass. Well, not really infinite - the grass does end, just far enough away that you can't see the transition. There are actually two scene modes, as noted in the previous post on trees.

Finite Grass

The first mode is a small cube of land that the player can walk around in and is mostly pre-generated and static. Not static in the sense that it can't be modified (because it can), but static in the sense that it's all generated upfront for a fixed area. I'll describe how grass works here fist, since it's simpler. In this mode, several million blades of grass can be generated and stored in a VBO (vertex buffer object) on the GPU. This takes a lot of graphics memory, and a significant fraction of a second of CPU time (using OpenMP parallelism again of course), but on the plus side there is no LOD (level-of-detail) to deal with so the grass looks very nice. It does help to divide the grass up into a few hundred patches with bounding cubes so that they can be dynamically updated and view culled so that patches that aren't visible aren't drawn. A few million blades of grass (typically 1.2M to 2.0M) in those grassy meadow-type scenes is a lot to draw, even as a single textured triangle each. Fortunately, it's relatively easy to do view frustum culling and occlusion culling against the terrain mesh and scene objects for each patch of grass.

Grass in this mode is very dynamic. It sways in the wind. The player can step on it and flatten out an area of grass. Similarly, it can be shaped and flattened by other heavy objects moving over it. Some game mode weapons will cut the grass. Explosions and fires will burn and flatten it. If the grass gets covered with dynamic water it will die and turn brown. And of course, since this mode supports a first person shooter game, the grass will get bloody. Most of this is handled on the CPU side by updating individual patches of grass when they change, which is a single VBO update call since each patch is stored together in a contiguous block GPU memory.

The grass shaders are some of the more unique of the custom shaders used in 3DWorld. The vertex shader moves the grass blades in the wind based on a wind direction uniform variable and wind speed texture map. Only the top point on the grass triangle moves in the wind, so the root part of the grass stays in place. Everything else is done per-pixel in the fragment shader: texturing, shadow maps, direct and indirect lighting, fog, etc. The fragment shader is somewhat slow and expensive, but grass doesn't usually take up much screen space so this tends to not be a limiting factor unless the camera height is around the height of the grass - which of course can happen, since grass height can be set to any value in the config file. But in most cases the grass height is low.

Here are two screenshots of grass modeled outside my parents' house.

Lush green grass surrounds this house model. This grass is dynamically shadowed and sways in the wind. [Note that I haven't updated this scene to use the new tree models as this requires recomputing indirect lighting.]

Grass is fully dynamic. It can be cut, crushed by walking on it, burned and flattened by explosions, stained red by blood, browned out by over watering, and even spray painted different colors.

Infinite Grass

Now I'll describe how I implemented an "infinite" field of grass for tiled terrain mode. In this mode, several hundred terrain tiles are generated around the player, and the ~100 tiles falling within the view frustum (visible to the player) are drawn. As the player moves around, old/distant tiles are discarded and new tiles are generated to maintain a constant number of active tiles. Each tile is the size of the entire scene in the previous (finite) mode. So that's 100x as much visible grass! It's no longer possible to generate, store, or draw that much grass on today's graphics hardware. The grass needs to be more dynamic and more compact. I chose to use hardware instancing of 32 unique patches of around 1500 grass blades each for ~500K total grass blades, which is actually 4x less memory than the finite terrain mode uses. Each tile contains many patches, and each patch is a random index representing which of the unique patches to instance in that position. This solves the generation time and memory problem, and the tiling artifacts of reusing patches aren't very noticeable.

It took quite a bit of work to figure out how to map a constant density, constant color, flat, square patch of uniform grass onto a curved landscape requiring variation in color, height, and density. All of this had to be done in the vertex shader on the GPU. The shader takes the terrain heightmap, terrain type map (which grass height, density, and color are derived from), and some 2D noise textures used to select random subsets of grass blades to remove. Grass blades selected to be removed are mapped to a degenerate single point triangle and made fully transparent in the hopes that the rasterizer (or at least the fragment shader) will discard them. It seemed a bit wasteful to discard 100% of the grass over rocky, snowy, or ocean terrain, so grass patches aren't even generated for tiles that contain no grassy terrain types. I think about half of the blades are discarded on average per patch/tile, which seems acceptable and the best I was able to come up with.

The time taken to draw that many (> 100M) individual grass blades is prohibitive, so a LOD (level of detail) system was needed. I decided to create approximate powers-of-two LOD with 5 levels plus the base full detail. Each detail level starts from the previous detail level and works by selecting a grass blade, then finding the blade closest to it to merge into a single larger grass blade. The surface area/width of the merged blade is the sum of the two input blades and the position and color is averaged. Preserving the total surface area is important to give the grass a consistent density across detail levels. This process of merging grass blades is continued until half the blades have been merged, or there are no nearby blades that can be merged together. This produces nearly a power-of-two reduction in the grass vertex count. In reality the sizes of each LOD level are more like 1500, 800, 450, 250, 150, 100. This works well, but gives at most a 15x reduction in the number of grass blades. Going further to higher LOD levels starts to create blades that are too wide and look unnatural.

15x isn't quite enough to get the rendering time down to a reasonable level, but there are other tricks to be played. The more distant tiles that are over a mile away don't need to have their grass drawn as individual blades. They can simply use a green grass terrain texture, which looks fine in the distance. The trick is making the transition from grass geometry to grass texture smooth so that the user can't see it. It turns out that always using the grass texture, even for nearby grass, looks just fine. The nearby grass blade geometry blocks most of the texture anyway, so the player doesn't see much of it. The harder part is removing those 5-th level LOD grass blades (that are made from merging some 15 nearby blades together) in a smooth transition when they reach the geometry/texture boundary distance. I tried various things:

• Remove random blades near the cutoff distance so that the density decreases smoothly to zero
• Increase transparency of grass near the cutoff distance smoothly from alpha = 1.0 to 0.0
• Introduce random noise dithering to make individual pixels transparent in the distance
• Translate the blades incrementally downward (in -z) until their tops go under the mesh

It turns out that the last approach (translation) worked the best and was also one of the simplest and most efficient. It worked so well, in fact, that it was nearly impossible to determine where the geometry to texture transition point was just by looking. So that's how I decided to do the transition.

Unfortunately, since the grass patches are instanced, it's no longer possible to dynamically update them for object interactions (crushed, burnt, dead, colored by blood) like in the case of finite grass. But this grass can still move in the wind, which preserves at least some of the dynamic nature of grass so that it doesn't look entirely static. As another optimization, wind motion is only enabled for nearby patches where the individual blades are apparent.

In addition to the grass, I added some colorful wildflowers for variety. These use a similar generation and rendering system, except that they're much sparser and don't require instancing. Flowers are procedurally generated, placed with density based on terrain type, and also move in the wind.

I'm not sure how much of what I did here for infinite grass is actually novel. There are plenty of papers out there on rendering infinite fields of grass. What I did here was a combination of what I read in those papers and some new tricks and ideas I came up with. It looks pretty good, is very efficient, and may be more generally useful than grass shown in many of those papers. After all, 3DWorld's grass is just one of many components of the entire scene, not the only/primary component. It needs to share runtime and resources with everything else and blend into the rest of the scene.

Here are some grass screenshots from tiled terrain mode.

A grassy field with wildflowers. The grass extends out to the distance, simulating many millions of individual grass blades. This nearly infinite field is still drawn at 135 FPS (frames per second). Can you spot the LOD transitions?

Grassy hillside showing how grass color and density can vary with terrain type between grassy, sandy, and rocky terrain.

Well, that's all I have to say about grass for now. I wonder if writing this blog post will get me working on grass again just like writing the previous tree post got me working on trees?

Trees and Forests

I was originally going to make a post about vegetation rendering in general, but since I have so much to say on this topic I decided to split the posts into trees, grass, and maybe other plants. This first post will concentrate on procedurally generating and then rendering deciduous and pine trees, from a single tree to a forest of thousands of trees.

It's quite difficult to generate and draw good trees and other vegetation. Things created by nature tend to have the sort of random variation that makes them complex to model and quick to identify as fake. Sure, it's easy to create and render a convincing brick wall, and it can often be a single quad, but with trees you need to have a polygon for every leaf when up close. If the leaves are placed too regularly it looks fake. If the leaves are all the same size, color, orientation, texture, etc. it looks fake. Even artificial (plastic) trees are easy to identify as not real when up close. On top of all that, put the user in the middle of a dense forest with thousands of trees, and now it not only needs to look real, but also be fast.

I've seen quite a few failed attempts (in my opinion) at drawing fast trees from various websites, conference papers, and graphics demos:

• Billboard clouds (multiple leaves in textured polygons) look horrible when up close and have parallax bugs when more distant
• Point clouds also look horrible up close and aren't very efficient in general for lots of trees
• Sharp transitions between polygon and billboard models have significant popping artifacts that ruin the appearance of tree
• Smooth alpha blending between LOD (level of detail) levels looks unrealistic when the tree is viewed during a LOD transition where parts of it are semi transparent.

What I ended up doing was splitting the trees into two types/classes: pine trees and deciduous trees.


Pine Trees

Pine trees seem to have less of a problem since they don't really have leaves, and branches (with their needles) are roughly planar so can be represented as a polygon. I'm sort of giving up on rendering each individual pine needle here since that's insane. I don't think I could draw a single tree in real time if it has a realistic number of needles. Pine trees are also fairly rotationally symmetric about the trunk's axis, so a single precomputed billboard can be rotated around the up-direction vector and it looks okay. This is a pretty standard way of handling pine trees.

3DWorld draws nearby pine trees as a six level stack of 5-branch rings, for a total of 30 quads (60 triangles) per tree, plus the trunk as a single truncated cone formed from a triangle fan. This looks good at medium to far distances, and acceptable up close. Far pine trees are drawn as a single quad with a pre-generated pine tree texture, shared across all trees, plus a single triangle for the projected cross-section of the trunk (or even a line when far away, or skip the trunk entirely when very far away). The width, height, and base leaf color can all be varied per-tree to add more variety while still sharing a single texture. Oh, and what texture do you think is used for the leaf quads? The same one as the distant pine tree texture! Since pine trees are self-similar, each branch looks like a smaller tree, so that's exactly how I draw them.

Since pine trees are so simple to draw, 3DWorld can support a ton of them - 10K visible nearby trees or  500K distant trees can be drawn at over 100 FPS (frames per second). In reality it's the video memory that limits the number of trees in the scene - at least in my initial implementation. If there are 500K visible distant trees, then the scene probably contains millions of total trees. Fortunately, they don't all have to be unique, hardware instancing can be used on both the nearby and distant tree models. As little as 100 unique trees is sufficient to make them all appear to be unique. Good luck finding two of the same trees in the forest! Then we just need to store the locations of each placement of an instanced tree in memory, which can be only 12 bytes per tree (in theory, 3DWorld doesn't actually store them that compactly).

Here are some screenshots of pine trees at varying distances, from a single tree to an entire forest.

Closeup view of pine trees in the house scene, with soft shadows.

 

Closeup view of pine trees planted in the courtyard of this office building, with maple trees in the background.

These pine trees don't look too convincing up close, due to the obvious pixelization of the leaf textures. A better texture map may help improve the look, but I've had a hard time finding textures that look good as pine tree branches. The trees look great when far enough away that the individual leaf pixels aren't visible. Most other tree rendering tools that I've used/seen produce pine trees that look like this.

Pine forest of ~500K trees extending out to the horizon over mountainous terrain. Note the  slight color variation between the individual trees that adds variation to the scene.

Deciduous Trees

Deciduous trees are more challenging, since they are less symmetric and their appearance is dominated by the shape, orientation, and distribution of individual leaves. There's no getting away with using the same texture for individual leaves and the entire tree! Also, the leaves tend to have specular highlights, and some light may leak through the leaves, which makes leaf lighting more challenging here than in pine trees. It seems like the only way to get good quality trees that the user can walk up to is to use a polygon (quad or triangle) for each leaf, and to have detailed branch meshes. That's a lot of polygons!

3DWorld has five hard-coded tree types, each with its own set of generation parameters, base bark/leaf colors, and bark/leaf textures. This seems to give enough variety to the trees. Tree type is either determined from a per-type procedural random tree distribution map, or specified per-tree in the config file when placing individual trees in a scene.

I should say something about how the branches are generated and drawn. 3DWorld uses something like L-systems (but more hard-coded for efficiency) for generating each tree, from the bottom up. Starting with the trunk, it continues to add branch segments and splits, and decreasing the branch radius, until some stopping criteria is met. Each new segment is rotated to add bends and twists to the branches and make them look more natural. The generated model and collision model consists of cylinders - well, actually truncated cones. However, they can't be rendered this way, because just rendering them as cylinders will produce overlaps and gaps between the cylinder sections at bends as the points on the two cylinders don't line up. So instead, the vertices are averaged across the two cylinders and shared in the vertex data so that there are no holes in the mesh. The entire branch structure is rendered as a single draw call with indexed quad strips. Generating the leaves is easy - just attach them to random points along small branches with radius less than some threshold.

The leaves are drawn as polygons - more specifically as quads (2 indexed triangles). I did attempt to use individual triangles for leaves to reduce the vertex count by 25% (4 -> 3) and the triangle count by 50%, but there were various problems. This approach involves using texture coordinates outside of the normal [0.0, 1.0] range, which introduces some stretching artifacts. Also, it's more difficult to animate triangle leaves in the wind. Finally, this approach has empty/wasted space near the corners of the leaf triangle where the texture is unused and fully transparent, which increases fill rate and actually makes rendering slower for groups of nearby dense leaves.

3DWorld has a variety of config file variables that control the tree parameters, including max detail level. Trees typically contain somewhere between 1000 and 20K leaves and 800-20K branch polygons, depending on the number and density/placement of trees in the scene and performance vs. quality tradeoffs. For small maps, 3DWorld can easily support hundreds of ~1000 leaf trees or dozens of 20K leaf trees. But for infinite tiled scenes it just won't scale. There may be 10K visible trees out to the horizon where the fog finally obscures them. Even if these are low detail trees, that's still ~2K * 10K = 20M total polygons. Sure, modern GPUs can handle that just fine, but not at a good frame rate. So some form of LOD (level of detail) is needed.

If you look back at my list of failed attempts at trees (above), you may wonder what's left to try. Well, this is a tough one. The first step is to take the polygon model to its limits. For example, for far away trees, the branch meshes can be reduced from cylinders to individual quads approximating the cross-sectional area of each branch segment. In fact, the smallest branches can even be skipped when drawing a distant tree, since they're usually hidden behind the leaves anyway.

Unfortunately, reducing the detail on the leaves is more of a challenge, since they start as individual polygons. There are no vertices that can be removed from a leaf without destroying the leaf. Merging distant leaves together is hard/slow and looks ... bad. I tried several approaches, none of which I really liked:

1. Remove leaves near the center of the tree: looks good for dense trees since these leaves typically aren't visible anyway, but bad for sparse trees.
2. Remove leaves on the edges of the tree: looks okay for symmetric trees, but those occasional trees that have a single long outlier branch that suddenly loses its leaves are no good.
3. Remove a random set of leaves: looks okay until more than 75% of the leaves are removed, then the tree starts to look pretty bare.
4. Remove some leaves but increase the size of the remaining leaves to keep the same leaf density/area: I really thought this would look better than 3., but it produces some strange optical illusions that remind me of those curvy funhouse mirrors, which makes the trees look fake.

In the end I had to go with 3. since it's the least of 4 evils, and I couldn't think of anything better. But we limit the number of leaves removed to no more than 75%. Okay, so that gets at most a factor of 4 reduction of leaf polygons, but that's not good enough fro 10K trees. When trees are even further away they need to be represented as billboards like the pine trees. Of course deciduous trees aren't symmetric, and a single distant billboard texture won't work for all of the trees. Each tree needs to have its own billboard texture, for both the branches and leaves parts. Even better, use one texture per view direction (for ~8 directions), but that ended up taking too much memory in addition to generating other visual artifacts.

In the end I generated textures for a single view/orientation of each tree. There are four 256x256 RGBA textures per tree, one pair for branches and another pair for leaves. The pair consists of a RGBA diffuse color + opacity/transparency mask, and an XYZD {normal + depth} map used for rendering in the shader. This is similar to what would be in a G-buffer of a deferred renderer. Just like the pine tree case, I limited the number of unique trees to 100, 20 trees of each of the 5 types. This uses around 200MB of graphics memory, 100MB for the tree geometry VBOs (vertex buffers) and 100MB for the textures. I'm sure I could increase the sizes or counts to improve quality, but the goal is to have enough memory for the entire scene, not to use all the video memory on trees alone.

Once the leaf and branch textures have been generated, they can be used to draw the distant trees. To reduce popping artifacts, the transition between full geometry and billboard quads is done with a "dissolve" transparency mask that blends between the two modes. The tree is drawn as both models overlapping for a small window of the LOD transition. The majority of the popping artifacts come from the often incorrect orientation of the billboard texture. It can be rotated around the trunk axis to face the viewer, but can only show the side of the tree that was rendered into the texture. This looks particularly bad when viewing the tree from above, since the tree leaves should have a circular shape and the branches should not even be visible. To avoid this problem, LOD is only determined by considering XY distance from the viewer to the tree. If the viewer is high above the tree, the vertical (Z) distance may be large, but the XY distance is still small. In this case, the tree is drawn as geometry, thus avoiding the billboard texture issue.

Finally, real deciduous trees have one more important property: their leaves move with the wind. Technically, so do their branches, but the leaf movement is usually more visually important. 3DWorld can animate each individual leaf of nearby trees based on a procedurally generated local wind field. I tried all sorts of ways of doing this in the shaders, but nothing really looked right and was efficient at the same time. I think what is needed is some sort of geometry shader that processes each leaf quad, though there is no quads mode for geometry shaders. I ended up doing the wind animation on the CPU, by updating the vertices of any nearby leaves that move so that the GPU has the new data in the VBOs (vertex buffer objects) at draw time. This is slow, but at least has the added benefit that the leaves can interact with the physics system. For example, if the player collides with the leaves, they will move. If a projectile hits a leaf, the leaf will move and maybe even fall from the tree. This would have been difficult to implement entirely on the GPU.

Here are some screenshots of deciduous trees in various contexts.

Mixed deciduous trees on hilly terrain with soft shadows and two-sided leaf lighting.

Maple and other trees in a grassy meadow with soft shadows.

Hedges formed from small trees constrained to fit into a cube-shaped bounding volume.

A scene with ~10K trees extending out to the horizon, with shadows, fog, and water reflections.

The process of writing this article has given me some ideas of improvements I can make to the tree rendering. In particular, I think they would look much better with higher resolution leaf textures.

I would like to include a video of leaves blowing in the wind, but I think I'll wait until my post on grass, where I can add a video of both tree leaves and grass moving in the wind together.


Update: I did find a new higher resolution pine tree branch texture, and it looks much better up close. The color and leaf density was different so it took awhile to update all of the constants in the code. I also generated a new distant pine tree texture by taking an unlit screenshot of an isolated in-game pine tree against a black background, to make sure it blends properly with the polygon model.

Updated office building scene with higher resolution pine tree textures. The sun is in a different position from the previous screenshot, so the lighting and shadows look different.

Ocean Water Simulation and Rendering

Water is a great way to show off a graphics engine. There are so many interesting ways to implement water, and with enough care the water can be made to look very real, while at the same time taking only a few milliseconds of frame time with all the effects. This past week I've been working on improving the quality of 3DWorld's ocean water simulation and rendering with GPU-based waves. I've decided to use OpenGL 4 tessellation shaders for creating the wave mesh from a low-resolution grid of quads, one per mesh tile. This isn't the first time I've used tessellation shaders - I replaced the fixed planet meshes in universe mode with hardware tessellated meshes last month, right after my universe blog post. I should make another post on universe mode later with the new planets, as the mesh is both better looking and faster to generate and draw.

The water effect includes the following features, all in realtime (> 200 frames per second):

• True Fresnel reflection of the entire scene (ground, trees, plants, clouds, sky, sun, moon)
• Wavelength-dependent underwater scattering along sun->ground->water surface path
• Large scale waves using mesh deformation with dynamic level of detail (GPU shader)
• Detailed waves implemented with animated high resolution normal maps (precomputed)
• Raindrop splashes + choppy waves to simulate stormy weather
• Underwater caustics using a precomputed animated caustics light map
• Underwater and above water colored, weather based fog effects

 Here is a screenshot of the ocean from far above. You can clearly see the high detail of the waves, and how the ocean can stretch to the horizon. This is a shader and textures based approach that can render any size of ocean to an approximate xy plane on the screen.

View of water from above, showing highly detailed waves, depth-based color attenuation/scattering, and fog to the horizon.

I spent a great deal of time making the reflections look nice. The entire scene (ground, vegetation, sky, etc.) is rendered in two high level passes. The first pass uses a mirroring about the Z (up) axis to a reflection texture at half screen resolution in X and Y. The second pass renders the normal scene landscape and water. The water shader uses procedural noise to bias the reflection texture lookups slightly to produce the dynamic wave distortion seen in the reflections. The bias depends on wind and weather effects to simulate different wave conditions on the water surface.

The water itself is actually rendered in two passes. First, the terrain under the water is drawn. Since the water is approximated as a flat plane at constant z-value (up), the ground terrain fragment shader can determine the depth of water above the fragment (pixel) being rendered using simple math. It can then trace the path from the position of the light source (sun or moon) to the terrain point underwater, then from that point to the camera/eye. The point where the rays enter and exit the water can easily be calculated, and the optical path lengths from light->ground and ground->camera can be computed. This is used to determine the depth-dependent attenuation and scattering + refracted term, which is rendered as part of the ground, not the water itself.

The second pass renders the water plane itself using a different shader. This pass uses alpha blending and adds the water surface effects: reflections, specular highlights, foam, and view angle-dependent term that adds a green tint to the water at shallow angles. The water surface shader has access to the terrain heightmap and can calculate the water depth at every fragment (pixel). This is used to discard/clip fragments where the water is under the mesh, to add foam near the shoreline, and to make the water more transparent near the shore so that the water/beach transition is smoother. The shader uses different constants and textures for shallow vs. deep water and does a linear blend between the two modes in between. I have even added a set of runtime controls that allow the user to adjust water color, opacity/transparency, muddiness, wave amplitude and frequency, viscosity, etc. in realtime. Yes, there is even a mode to render lava.

In reality there is actually one more pass. When the camera is just above the water, and GPU waves are enabled, you can see the water surface through a partially transparent wave peak. The eye vector goes through the front side of a wave, out the back side, and into another wave behind the first one. It so happens that when the camera is close to the water, the view of the ocean is at a grazing angle, where the Fresnel term weights the reflection term from the second rendering pass more than the refracted term from the mesh drawing pass. In this case, the final color is nearly an additive blend of the ground and reflected colors. This will doubly add the reflected contribution from the front and back waves, making the water surface appear oddly brighter than it should be. The attenuation of light through the volume of the front wave is missing. If there is more than one wave visible, it looks even worse. This can be partially fixed by enabling back face culling, which removes the back face of the front wave. In order to remove the water behind the front wave, an additional drawing pass is used. First, the water is drawn in a Z/depth pre-pass with no color information. Then the water is drawn again with depth testing enabled using a color pass (with water fragment shader enabled). This second pass uses a depth compare of LESS_EQUAL so that only the front face of the water (nearest wave) is drawn. The water behind the nearest wave fails the depth test and those fragments are discarded so they don't contribute to the final color. This involves running the tessellation shaders twice, but most of the work is in the fragment shader, which is only run once, so this has a minimal impact on frame rate.

Here is a screenshot of the ocean from near the water surface. The detailed waves add realism to the water, and the lower frequency rolling waves add depth to the image. It's hard to tell from a screenshot, but the surface of the water is animated with multiple layers of waves for a natural look with very low tiling, aliasing, and repetitive artifacts. The shader is actually quite complex and uses a dozen different textures for the wave normals, caustics patterns, etc.

Ocean water just above wave peaks showing closeup of waves, scene reflections, and specular sun reflection.

 Here is a video I uploaded to YouTube showing the water in realtime. The in-game water is much less blurry!

I made some adjustments to the environment to get a nice screenshot near sunset with a planet and asteroid belt in the background. I can use the universe mode planet rendering as a dynamic background in ground/terrain mode, and even have the sun, planets, and moons move in the background in realtime. There is a key to switch between universe and ground mode that lets you fly your spaceship around to find a planet to land on, then generate the terrain using the planet's temperature, water level, vegetation, atmosphere, gravity, etc. This is the same location as the previous screenshot, but on a different planet where there is more water, a thinner atmosphere, and larger but dimmer sun.

Ocean near sunset with isolated islands, specular reflections, and distant planet + asteroids.

I have also implemented weather effects including rain, snow, wind, fog, and lightning. Here is an image of the same ocean on a cloudy, rainy day. The rain can be clearly seen, along with many small ripples in the water, choppy waves, and more high frequency noise in the reflection. There are some gaps in the clouds that allow light rays to shine down on the mesh and water. I'll have to say more about this later as it's getting a bit off topic.

Rainy day with choppy waves and raindrop splashes. Note the mostly cloudy skies and thick fog in the distance.

Here is a wireframe view of the ocean surface mesh. I'm using tessellation shaders to dynamically subdivide a very coarse mesh based on distance to the camera. The ocean mesh has higher resolution near the camera - but it doesn't have to be very high to achieve a nice sine-based wave effect. The waves are low amplitude to reduce any obvious repetitive patterns, aliasing, and other artifacts. Even these small waves add a lot of realism, at very low framerate cost. I had to use a mixture of 4 different sine waves to break up the repetition and reduce popping artifacts when the level of mesh detail changes.

Wireframe mesh of ocean water surface showing GPU waves implemented with OpenGL 4 hardware tessellation shaders.

Finally, an underwater view. The bottom of the ocean's surface waves can be seen, and the dense fog limits visibility. I have added "fake" caustics on the ocean floor using another animated texture that matches the detailed wave texture above and is animated at the same rate. This view also uses the same wavelength-dependent attenuation with slightly different constant factors. I procedurally placed some rocks and seaweed under the water to make it look a bit more interesting.

Underwater view showing caustics and normal mapping on the ocean floor, underwater fog, and distance based per-wavelength color attenuation.

Overall, I'm pretty happy with this approach to rendering ocean water. It's a mix of real physics for the "easier" and more efficient effects, and precomputed, texture-based solutions for the traditionally more expensive effects such as wave peaks and underwater caustics. It looks like a real ocean, and responds in realistic ways to environmental effects such as lighting and weather. It's also fast enough that it can coexist with all the other terrain features without taking too much frame time. Now I just need to figure out how to have dynamic objects interact with and float on the water surface. I do have that for my older small area CPU-based water, but that's a topic for another post.

Volume Lighting Effects with Smoke and Fog

This past week or so I've been working on improving the volumetric lighting of smoke and fog in 3DWorld. The engine supports full-scene volumetric smoke in a uniform 3D grid, as well as full-scene uniform fog. Smoke is generated by weapons, fires, and explosions in gameplay mode (first person shooter). Smoke and fog use the same algorithm and code, and use the same data, so we can only have one enabled at a time. The only real difference is that smoke is dynamic and varies over the volume vs. fog, which is uniform and constant (= more efficient). So I'll just refer to it as "smoke" here.

Each frame, the generated smoke is accumulated and diffused through open spaces in the scene, with a bias that pushes the smoke upward over time so that it accumulates near the ceilings. Most of the time I use something like a 128x128x64 grid, which is a reasonable tradeoff between quality and performance. Now that I have a new computer + GPU I might be able to get away with a higher resolution, though it's nice to make everything a power of 2, and increasing by 2x in all three dimensions is 8x more volume data to store and process. 4MB of texture data for smoke density + RGB indirect colors is a reasonable amount of data to generate and upload to the GPU each frame, but 32MB is a lot.

The smoke effect is implemented in my GLSL fragment shader of every material used in the indoor scene. It's generally too expensive to use on vegetation due to high pixel overdraw, but that's okay, the grass and trees are all outside and can be smoke-free. Standard fog without volumetric lighting can still be used on the outdoor parts of the scene. To get the true volumetric effect, smoke can't be explicitly rendered in a way that modifies the dept buffer. The individual smoke puffs can be rendered that way, but it doesn't make a convincing room full of smoke.

For each triangle fragment of indoor geometry we need to do a 3D volume ray traversal from the fragment (point on the scene geometry) to the camera/player/eye in world space, and accumulate light along the ray to include the effects of both forward and back scattering. The shader performs this ray marching in a loop, where each iteration:

• Looks up the smoke density and local indirect lighting in a 3D texture that's incrementally updated each frame
• Computes the forward and back scattering at that point using the smoke density and color
• Checks the scene shadow map to determine if the point is visible to the sun and adds sun light
• Finds any nearby dynamic light sources and adds their light contributions

In the real world we have a set of differential equations with exponential relationships between the variables, but I'm not trying to write a physically correct (slow) model here. I want it to be as simple and fast as possible, and also easy to tweak to get the effects I want. So I just went with a simplified linear equation, and the code looks like this (edited/simplified from the original shader):

vec3 dir      = eye_pos - vpos; // pos to eye
vec3 normal   = normalize(dir); // used for dynamic lights
vec3 pos      = vpos; // world space
float nsteps  = length(dir)/step_delta;
int num_steps = 1 + int(nsteps); // round up to nearest int
vec3 delta    = dir/(nsteps*scene_scale); // world space delta for each iteration
float step_weight  = fract(nsteps); // needed to remove sharp transitions (popping)
float smoke_sscale = SMOKE_SCALE*step_delta;
vec4 cur_epos   = fg_ModelViewMatrix * vec4(vpos, 1.0); // world => eye space
vec3 epos_delta = fg_NormalMatrix * delta; // eye space delta

// smoke volume iteration using 3D texture, pos to eye
for (int i = 0; i < num_steps; ++i) {
 vec4 tex_val = texture(smoke_texture, pos.zxy); // rgba = {indir_color.rgb, smoke}
 // add dynamic lighting
 tex_val.rgb += add_dynamic_lights(pos, normal); // world space
 // add sun light with shadows
 const float smoke_albedo = 0.9;
 tex_val.rgb  += smoke_albedo * get_shadow_map_weight(cur_epos) * light.diffuse.rgb;
 cur_epos.rgb += epos_delta; // move position in eye space
 // final calculation at this step
 float smoke  = smoke_sscale*tex_val.a*step_weight; // smoke density
 color        = mix(color, vec4((tex_val.rgb * smoke_color), 1.0), smoke);
 pos         += delta*step_weight; // move position in world space

 step_weight  = 1.0;

} // for i

return color;

This shader does a ton of work, over 100 iterations of this loop per fragment, where each iteration does a 3D texture lookup, shadow map texture lookup, lighting computation, and various vector floating-point math. All this done at 1080p = 1920x1080 pixels. It hasn't been practical to use this approach until I got my new computer and GPU (GeForce GTX 770), where I now get at least 60 fps. That's good enough for this one effect, but not good that this single effect takes most of my allocated frame time. Oh well, maybe I can optimize this more later. If I was using a deferred rendering pipeline I could do the volume lighting on a lower resolution (half? quarter?) target then upsample and blur it. But I'm doing this with a forward renderer, which means I need to process every fragment independently.

Now that I have this effect working, I can have fun setting the scene on fire to get some nice looking volumetric smoke. The plasma cannon does a nice job of creating fire and smoke. Here is a screenshot of the lobby area of my office building (modeled by myself). The fires are out, but the room is filled with smoke, and you can see the shafts of sunlight coming from the windows around the stairwell above.

[Note: I'm not sure why the left side of these screenshots has a tiny strip of pixels from the right edge. It's not clear what stage of my screen capture, image resize, and bmp->jpg compression did this.]

Sunlight filtering down between the stairs, producing light shafts in a smoke-filled room.

If you look at the floor, you can see that the sunlight isn't very strong. That's because I also compute a shadow term for each fragment that accumulates smoke along the direction of the sun light to produce soft partial shadows due to the smoke itself. This is a nice effect, but not one that would normally be noticed without me pointing it out.

Over time, the smoke will dissipate as it diffuses through the air, up the stairs, and out the doors. If I was to shoot out the windows, the smoke would quickly escape the building and the air would clear up in a few seconds. This is because the smoke diffusion algorithm uses dynamically updated flow vectors for each cell that determine the rate at which smoke can flow between that cell and the adjacent cell in {x, y, z}, based on cross sectional area of a 2D cut. When the scene is modified/destroyed, this data is updated, and the smoke diffusion algorithm incrementally updates the 3D texture across several frames.

Here is another screenshot showing high contrast light and shadows caused by a skylight in the ceiling. Volumetric smoke is added when the smoke puffs rising from the fires hit the glass plate in the ceiling. I had to use a pretty small step size of 0.2x cell grid size (5 steps per texel) to remove the aliasing effects at the shadow boundary, which hurt the frame rate. There is still a small amount of aliasing present if you look at the right angle.

Light from the overhead skylight scatters in the smoky room to produce volumetric shadows.

Dynamic and static scene lights also contribute scattered light to smoke. As I've shown in previous posts, 3DWorld supports hundreds of dynamic point and line light sources. These can be made to illuminate smoke particles as well as scene geometry, though this decreases the frame rate to only 30 fps in some cases. In this screenshot you can see the glow/halos from the laser beam line light source and the blue floating point light source interacting with a smoky basement.

A laser beam and blue floating point light illuminate the surrounding smoke, producing a glow due to light scattering.

Finally, here is a screenshot of my "God Rays" implementation in tiled terrain mode. In this case there is no 3D volume texture, since the scene is "infinite" in size, so the cloud density is procedural. The shader is different, but the general idea is the same. I'm evaluating 4 octaves of Perlin noise at every step along the ray, for every fragment (pixel) of every object in this scene, at > 2M pixels, so I only get 22 fps. This is a very brute force solution, so it's impractical to have this effect in a realtime engine, but it makes a pretty picture:

God rays from sun filtering through rain clouds in tiled terrain mode.

I still have more work to do, mostly improving the performance, but the results look pretty good so far. I'll have to see if there's some way to do the ray marching on a lower resolution image. Or maybe I can find a way to decrease the number of steps and use some kind of blur to remove the aliasing and noise from the shadow map. There are plenty of papers and presentations available on this topic. Overall, this volumetric scattering approach produces some pretty nice effects.

Voxel Terrain Generation and Rendering

This time I'll present 3DWorld's voxel terrain system.

I'm generating a 3D array of noise values using different noise functions, computed either on the CPU or on the GPU using a custom fragment shader. The current set of noise functions supported are Perlin noise, Simplex noise, and sum-of-products-of-sines noise (of my own invention). They all seem to produce the same sort of lumpy terrain; in fact, the only real difference is computation time. Naturally, it's faster to generate noise values on the GPU, though reading back all that floating-point data takes around half the time of the CPU noise generation. This inefficiency is partly because I have to generate the volume in 2D slices, to match a 2D frame buffer. If anyone manages to invent a 3D frame buffer then let me know - or I suppose I could give in and use Nvidia-specific compute shaders or CUDA. In the end, it only takes 200ms to generate 16M noise values (64 slices) for a 512x512x64 scene, which comes to 64MB of data.

A big array of noise values is great, but it needs to be rendered. I chose to use the Marching Cubes algorithm because it's fairly simple (compared to the alternatives) and the crazy lookup tables needed for MC can be found online. There are some ambiguous cases in MC, but they tend to not show up often in the scenes I create and I prefer simplicity and efficiency over perfect quality, at least for now. So I can use MC to get triangles, then connect them together and compute the shared vertices so I can render with indexed triangles. This seems to be the most efficient way to render large triangle datasets using OpenGL, and is more compact than storing individual triangles. I divide the scene up into XY tiles (I use Z=up). 16x16 tiles seems to work well, and this division gives some nice benefits:

• Each block can be generated independently, so I can use openmp to run separate threads on each core. 8 threads (4 core + hyperthreading) gives me about a 5.5x speedup.
• View frustum culling can be used to drop invisible blocks when rendering
• Individual blocks can be modified, which is fast enough for realtime voxel editing

Of course I skipped a few steps here, including handling of the mesh boundary, clipping the bottom of the volume with the heightmap floor, removal of disconnected "floaters", etc. This is all pretty standard stuff so I won't go into all of those details. One more important thing is lighting: these voxel scenes just don't look right with simple direct lighting. They need real ambient, and fortunately it's easy to compute ambient occlusion by ray marching through the 3D volume and tracking the visibility of each voxel (again using openmp). I also run path tracing on the triangle mesh like in my previous lighting post with the Sponza scene screenshots. This gives multiple bounce indirect lighting from the sun, moon, etc. for each voxel, which is recomputed (using openmp) when the light sources change.

Here is a screenshot of a 128x128x128 voxel rock/mountain that uses triplanar texturing with different textures + procedural texture selection to give it a variety of rock/grass features. I also placed some dynamic grass blades on the top surfaces of the rock. The shadows and ambient occlusion really bring out the dark crevasses in the rock and make it come to life.

Voxel mountain covered in grass, with indirect lighting, ambient occlusion, and shadows.

Voxel mountain with longer grass blades and denser grass.

Here is another screenshot of a 512x512x64 voxel snowy/icy landscape. The normal maps on the surfaces add nice specular highlights to the snow. The ambient lighting and shadows give depth to the scene, and the indirect lighting is responsible for the blue vs. white coloring. The blue areas are mostly lit by the sky but the white areas include indirect reflections from the sun on the snowy ground and icy walls. I have the indirect term set higher than what is realistic to make the indirect lighting stand out.

If you look at the ridge line on the right, there are some strange cube shapes placed there. These are the results of my voxel editing tests on this scene. I have implemented realtime addition and removal of volumes using different brush shapes (sphere, cube, etc.), sizes, and weights. These brush strokes can be saved to files and re-applied when the scene is loaded after the procedural generation is finished. I decided to store the brushes instead of the raw volume data because it allows for tiny file sizes. It would take a huge amount of time for a user to accumulate 64MB of brush strokes to make the save file exceed the size of the floating-point volume data!

Procedurally generated ice/snow caves + user edits with indirect lighting, ambient occlusion, shadows, and normal mapping.

Here is a zoomed out view of the entire scene - there is a surprising amount of data here! You can easily get lost walking around in this cave system, which is almost entirely connected and walkable. This is 16M voxels, which is converted to around 2M triangles for rendering. I'm getting a nice 300 FPS here with all the effects turned on, even though the camera is too far away to see the details. Oh, and that round hole in the bottom left is a tunnel I made horizontally through the entire scene.

Zoomed out view of voxel ice cave scene.

And finally, that same scene with more interesting lighting: 100 moving, light emitting, colored spheres. This time the sun and moon are both below the horizon for a nice dark night, which makes the colorful light sources stand out. The normal mapping produces some nice specular reflections, though they're a little hard to see at this view distance. I'm still getting a high frame rate of 130 FPS here, even with all the lighting computations for 100 lights.

Ice caves scene with 100 dynamic colored lights.

If I was more of an artist, I would show you some cool screenshots of what I created with the voxel editing tools. However, I was never really into art, and the procedural terrain looks pretty good to me. I'm hoping that I can integrate voxel content into other 3DWorld scene types in the future. 3DWorld already supports the addition of non-voxel polygon objects into voxel-based scenes. For example, I can put the Sponza atrium model on top of these voxels or inside of a large cave. The first person shooter "smiley killer" game can be played in these caves (if you could ever find something to shoot at in the maze). [Yes, I know, I need to post something about that game here since it's not just an engine.]

Well, that's about it for this post. I'll try to put some more screenshots of cool stuff I created with voxels into a later post. I'm sure there's a lot I can do with 3DWorld's voxel framework.

Procedural Universe and Planet Generation and Rendering

It's time to introduce the "universe" mode of 3DWorld, which is quite a bit different from the other "terrain" modes. This mode doesn't share too much of the high-level classes, functions, and control flow with the rest of 3DWorld, but it does share a lot of the low-level infrastructure. It can also be used to draw a real, animated nighttime starfield (with planets, moons, rings, etc.) in the background of terrain mode.

Universe Objects
There are two classes of objects in universe mode: procedural, natural universe objects and dynamic, manufactured objects such as space ships, their projectiles, and their particles. The procedural universe objects are generated in a hierarchy of cell -> galaxy -> solar system (with star) -> planet -> moon. Each cell contains several galaxies and is identified by 32-bit integers for {x, y, z} grid positions, so the universe is effectively a 3D grid of 2^32 cells, and contains some 2^98 galaxies. I call that universe infinite - in fact any procedural world where you can move at max speed in the same direction for a lifetime without reaching the end is more of less infinite in size. The objects in the universe have compressed scales so that you're not flying for hours in empty space to get from one planet to another, or one star to another. Even with the compression, there are still issues with floating-point precision, so I had to use custom float + int coordinates in some places, and double precision in others.

The universe contains the following physical objects at various levels of the hierarchy:

• Stars (one per system, up to 500 per galaxy)
• Nebulae (one or more per galaxy) - volumetric with 3D ridged perlin noise
• Asteroid fields (multiple per galaxy, either inside or outside of a system)
• Asteroid belts (in some systems and around some planets)
• Planets (up to 15 per system)
• Moons (up to 8 per planet)
• Comets (spawned near the player, out of view)

Everything is procedurally generated, more or less from scratch. Since the player can travel between star systems in a fraction of a second in hyperspeed, everything needs to be generated within a single frame. In the end I had to move almost all the generation and rendering into large shaders up to 600 lines of GLSL code. So far I haven't been able to find any other online tool/product/demo that draws an entire planet from scratch using a single shader in a single pass. Well, it's not exactly a single shader - I have a shader generation framework that takes bits and pieces of GLSL code and combines them together to create a shader customized for the particular class of planet, moon, etc. being rendered. So it's one shader/pass per planet, but different shaders for each type of planet or moon. The types of planet that 3DWorld supports consist of:

• Terran/Earth-like: Procedural ground/vegetation color, normal map, water, snow/ice coverage, clouds with shadows, and atmosphere
• Alien: Colorful terrain, toxic clouds and atmosphere with shadows
• Ocean/Water: Clouds and atmosphere
• Ice: Gas clouds/atmosphere
• Rocky: Procedural height generation in vertex shader, normal maps at multiple octaves, shadows
• Hot/Lava: Lava instead of water, possible toxic atmosphere, normal maps, colored
• Gas Giants: Multiple layers of procedural clouds, perturbed 1D color bands, animated procedural cyclone storms, soft cloud shadows
• Moon: with procedural heightmap and craters generated within the shader using normal maps

Each planet can also have rings that cast and receive proper analytical soft shadows, asteroid belts, and one or more moons that revolve around it. All objects rotate and revolve according to the laws of planetary physics. In addition, each object is given a unique generated name.

In addition to creation and rendering, 3DWorld provides a framework for physics simulation, collision detection, and modification of the universe. There are query functions for gravity, temperature, and lighting at any point in the universe. 3DWorld supports efficient object line intersection tests, sphere intersection tests, nearest object queries, future collision queries, and other functions necessary for interacting with the universe. Objects can be destroyed and renamed by the player, and modifications can be saved to disk and reloaded in future sessions.

Screenshots
Here are some screenshots of planets and other universe objects, all procedurally generated and rendered with custom shaders. There are no predefined textures used, all planets are unique, and I'm getting framerates of hundreds of FPS. Note that the planets are closer together than they would be in reality, to make the scene look more interesting with multiple planets in view at the same time.

Volumetric procedural nebula that the player can fly through, using 3D ridged perlin noise. Each one is unique.

Star with asteroid belt and nearby planets, with stars, galaxies, and nebulae in the background.

Closeup of system asteroid belt with 10K large rotating asteroids (perturbed spheres with hardware instancing and LOD) and 1M small asteroids (point sprites). All asteroids rotate around the star, and can be collided with, selected, and destroyed.

Gas giant with swirling animated clouds, animated storm cyclones, cloud shadows, lightning, rings with animated asteroids and particles, soft shadows to/from planet <=> rings, and indirect moon lighting.

Terran planet with procedural terrain (8 octave 3D ridged noise multifractal), normal mapping, snow covered mountains, ice at poles, animated swirly clouds with shadows, specular snow, ice, and water, and atmosphere.

Icy planet near the asteroid belt with some snowy peaks and green forested areas. Note the moon in the back left.

Planet with clouds, toxic atmosphere, and emissive lava glow (black body radiation). You can also see a distant comet in the upper right corner.

Rocky ice planet with nearby asteroids. The vertices are perturbed by evaluating noise in the vertex shader. All planets of this type use a constant/shared VBO of initial sphere vertices.

Ships
In the other category we have artificially created objects consisting of:

• Space Ships
• Starbases
• Planetary Colonies
• Projectiles (missiles, etc.)
• Particles and Particle Effects
• Explosions

This is the space gameplay part of universe mode, where the player engages in colonization and fleet combat with one or more AI-controlled sides. All of these objects are either initially placed in the config file, randomly spawned, created by the player, or created by an AI. We start with the ships, which can create other ships, colonies, projectiles, and particles. All of these objects can interact with universe objects (stars, planets, moons, etc.) and with each other. I'll make a later post with more ship details and screenshots.


Video Update

Here is a procedural universe fly-through recorded by 3DWorld. I fly my ship away from the battle, past a planet, into the asteroid belt, past the star, to a ringed gas giant, back and forth through a nebula, and back into a system to view a planet up close.

YouTube Video Link

At one point I fly my ship into an asteroid and bounce off, which shows how physics and collision detection work with every solid object in the universe. I also get too close to the star at one point and start taking damage, which is why the screen turns red and shakes. (I have the health bar and other UI elements turned off to reduce screen clutter.) The nebula is procedural, which allows the player ship to fly though it. All planets, including the gas giant and Terran planets in the video, are entirely generated and drawn on the GPU. I'm only sending a low-resolution, untextured sphere to the GPU for tessellation and rendering. Everything is generated seamlessly with no visible LOD transitions and no loading screens.

Indirect Lighting in Sponza Scene

The video from the last post didn't turn out very well. It was smaller and lower resolution than the original, probably because it was compressed (again). So I'll just post images for now and hold off on posting more videos until I figure out a better system.

This time I want to talk about how 3DWorld does lighting in mostly static scenes. There are four types of lighting supported:

• Directional lights with shadow maps (sun and moon)
• Indirect lighting from sun, moon, and sky (as an area light source)
• Static point lights "compiled" into the scene such as room lights and streetlights
• Dynamic point, line, and spotlights (large number, but no shadows or indirect/ambient)

The directional lights are conventional OpenGL lights with standard shadow maps, nothing really too new. Indirect and static lights are precomputed using ray/path tracing and stored in a matrix + texture. Dynamic lights use textures as an acceleration structure that's traversed in the fragment shader. I'll explain these last two in more detail below.

Indirect Lighting

Indirect and static scene lights are precomputed using ray/path tracing across multiple threads and stored in a 3D volume texture that covers the entire scene. There is also an option to store the data sparsely for scenes that don't really fill a cubicle volume. This data is initially stored in a 3D array on the CPU side and transferred to the GPU once at program startup and also incrementally as lighting changes. There are several components to this lighting:

• Sun indirect: Updated interactively as the user moves the sun position in background threads (several seconds lag for computation time). Stored as a weight so that changing the sun color or intensity can be done efficiently without recomputing the ray intersections.
• Sky/Cloud indirect: Precomputed for a large number of point light source emitters positioned in a hemisphere around the scene, and constant for a given scene. Stored as a weight so that the sky color can transition between light blue and near black over the course of a day without recomputing ray intersections.
• Static point light sources baked into the scene as either point lights or arbitrary area lights. These are mostly for fixed lighting such as lights in the ceiling, outside in street lights, fixed position fires, etc. These lights can have high quality indirect lighting (ambient) and aside from pre-processing time they are "free". They can be combined with dynamic lights so that the combination has some amount of dynamic to it.

This type of lighting produces very nice and close to physically correct soft shadows, ambient occlusion and color bleeding effects. Path tracing does produce great results when you have the CPU time to do it correctly and allow for large numbers of light bounces on a variety of surface types, including partial transparency. For example, here is a screenshot of ambient lighting applied to the Sponza scene:

Crytek Sponza scene with shadows and indirect lighting from both the sun and sky at 335 FPS

Note the green, red, and blue color bleeding on the pillars in the back due to light reflecting off the colored cloth. Note the soft shadow of the large pillar in the top right of the image. Also note the orange glow from a fire on the floor near the back wall which has been added as a static light source. Here is another view from below:

Crytek Sponza scene with fires that produce soft shadows and indirect lighting at 421 FPS

This is a view of the fires that were placed in each corner of the bottom floor of the Sponza atrium. Each of these lights is static and compiled into the scene, but also has a dynamic light placed at the same location that flickers, giving a sense of dynamic intensity to the fire. You can see the shadow of the top of the urn (or whatever it is) on the left side - but that's really a trick, the light is actually a spotlight shining up. Note the normal mapping that gives more 3D volume to the pattern on the bottom right. All types of light sources support normal maps - and specular maps as well, though you can't really tell in these screenshots. Those horizontal black strips in the middle of the pillars are probably incorrect texture UVs from the original model.

This Sponza model was imported from Lightwave Object file format. The original object file was downloaded from http://graphics.cs.williams.edu/data/meshes.xml

This runs at an amazing 400 FPS (frames per second) because the indirect lighting is implemented as a 3D texture lookup in the fragment shader with no ray marching or loops and almost no CPU work done per frame. In this example I'm using a 128x128x256 RGB (red, green, blue) texture, which has 2M entries and takes a mere 6MB of GPU memory. In reality the size of the texture is limited by the CPU computation time of the path tracing. For this scene, it takes about 10 min. to path trace on a quad core CPU with hyperthreading (8 threads). [Okay, so it's really 8MB of texture since I'm actually storing it as RGBA and using the alpha channel to store volumetric smoke/fog information, but I'll explain that in a later post.]

But what about normals? Don't you need to store at least 3 values in the 3D texture for each face direction {X, Y, Z}? Well, there's a trick to this. Instead of storing ray intersections in the matrix, I store something like lighting flux for each of the RGB channels. Each photon leaves some light in each matrix cell that it passes through, not just in the final cell the ray hits along its path. If you take the difference between two adjacent cells in one dimension (say X), you can determine how many of those photons' paths ended between those two cells. If the delta is large we know there is some sort of wall there that is blocking the light. So what we do in the shader is bias our texture lookup by half a grid cell/texel in the direction of the object normal in world space. For example, if the wall is facing into a bright area, our normal will point toward the light and move our lookup into the middle of a well lit cell where many photons have passed and deposited their light. If the normal is facing into a dark wall or corner, this will move our texture lookup into an area inside of the wall where few photons reached and give us a darker lighting value. It's not physically correct, but it looks plausible.

There is another advantage of storing light this way. If we add dynamic objects to the scene, they can pick up the indirect lighting even if they are in the middle of the air far from any ray intersection points! They don't need to be present when the original path tracing is done. We just do a volume texture lookup for the dynamic object's location biased by its normal, and as long as the object falls within the texture (the scene bounding cube) we have valid lighting that changes as the object moves. The change is nice and smooth too due to the trilinear texture filtering on the GPU.

Dynamic Lighting

Dynamic lights use several textures as a world-space acceleration structure that's traversed in the shader on the GPU to reduce the number of lights that have to be processed for each fragment. The number of light sources can be very large, currently up to 1024, but for efficiency they should be small in radius/area of effect. There is no limit to the number of lights that can affect a given pixel/fragment, though it certainly does affect frame rates. They also don't cast shadows (yet). Dynamic lights have diffuse and specular components and can be point lights, spotlights (point + direction + angle), or real analytical line lights such as laser beams, which I may post screenshots of later.

This is all made efficient using an acceleration structure that's encoded as three textures:

• Grid Bag Matrix: This is a 2D or 3D 32-bit integer texture that maps world space position to a {start, end} position within an index texture. We use this to find the set of lights that contribute to the fragment at a given world space position. 2D indexing (X,Y) is much simpler and seems to be faster due to reduced texture memory usage, though can be slow when there are a large number of dynamic lights at the same (x,y) position but different z values. .. But I really should try 3D textures again on my newer Nvidia card.
• Index Array Texture: This is a 1D 16-bit integer texture that maps to indexes of dynamic light sources. Each grid bag element refers to a contiguous range within this texture. This extra level of indirection effectively allows us to store a variable-sized array within each texel of the grid bag. This is important since current GPUs don't allow dynamic memory allocation.
• Dynamic Lighting Texture: This 1D 16-bit float RGBA texture stores all the lighting parameters. Technically it's a 2D texture since the lighting parameters don't fit into a single RGBA value and if stored as a single row may exceed the max dimension of a 1D texture (8192 on my old ATI card). Each light is a 16-bit float stored as three RGBA values: {center.xyz, radius}, {color.rgba}, {direction.xyz, beamwidth}. Line/cylinder light sources store the end point of the line in the direction field.

The code to use these textures to determine which lights contribute to a given point and to calculate the lighting is usually run in he fragment shader, but can also be in the vertex shader.

This lighting system is fairly complex but pretty fast, supporting hundreds of small dynamic lights in realtime. The lights are normally from weapons, explosions, fires, glowing fragments, the player flashlight, etc. I like to use random colored lights for testing since it's a little more stable and repeatable, and more obvious when something is wrong. Here is a screenshot of the Sponza scene with 100 moving colored lights:

Crytek Sponza scene with 100 Dynamic colored lights at 95FPS

Note that you can see some of the normal mapping at work on the sides of the column of the right. I should have put more effort into finding good viewing positions and angles to capture normal mapping. This would also have been better in a video. The lights use collision detection to stay inside the open air of the scene and also cast shadows, though you can't see the shadows at night. Also, you can see the specular reflection of the rightmost yellow light on the shiny floor.

I'll note one odd thing about this screenshot: The blue lights look purple when viewed in Windows Photo Viewer! I originally tried taking the screenshot using 3DWorld's internal screenshot capture function that uses glReadbuffer() and ligjpeg to write it out, but noticed the purple lights. Then I took a screenshot using Fraps (the one posted), which still had purple lights. Now that I see it on this page the lights are in fact blue, so what's going on here??? I kept the Fraps image anyway since it seemed to be better quality, which may just be due to a difference in JPEG compression level.

Wow, that was a lot of text, but it took orders of magnitude less time to write this up than it took to actually write, debug, and test the code. If anyone is interested I might be willing to share some of my C++ and GLSL shader lighting code. It's a bit messy though, and deeply integrated into 3DWorld, and I don't want to open source everything (yet). I would certainly appreciate some feedback on what I've done here.