Tree Shadows

I've been working on improving the 3DWorld trees again. I feel that trees are one of the best looking elements of 3DWorld, and are in general very difficult to get correct. This time I decided to add real shadows to the tiled (infinite) terrain tree branches and leaves, as well as other vegetation such as plants. 3DWorld has included mesh and grass shadows for a while now, but I hadn't really added shadows for the other vegetation because I felt the texture fill rate was too high and wouldn't give me good frame rates. That may have been true on my old computer/GPU, but the new system has much better performance. This is going to get pretty technical, so you might want to jump down to the pictures that I added later in the post.


Shadow Map Creation

The terrain is too large to use a single shadow map texture for the entire scene as it would be too coarse and would produce blocky shadows at that size, assuming a reasonable texture resolution of around 4096x4096. The dynamic scrolling nature of the scene also makes it difficult to use a single shadow map, since it would become misaligned with the scene bounds as the player moved. Scenes like this containing thousands of trees make for very slow shadow map generation because the leaves produce very high overlap/fill rate. I can get away with rendering distant trees as billboards/sprites (textured rectangles containing generated images of each tree), but using the billboards to create shadows looks terrible since they're not true 3D. The tree billboards are designed to be viewed from the side as the player is walking around on the ground. They're not intended to be viewed from above in the direction of the sun, which is required for shadow map generation. The shadow map needs to be rendered once and cached rather than recreated every frame to get good performance. This rules out perspective shadow maps, cascaded shadow maps, and trapezoidal shadow maps as they all require regenerating the shadow map as the view frustum changes (when the camera rotates). In the worse case - every frame.

Instead I decided to create one shadow map per tile, and only for the nearby tiles. This was a reasonable trade-off between shadow map quality and performance. Nearby objects could have very highly detailed shadows that blended to low-resolution precomputed ambient occlusion in the distance. A smooth transition between the two minimized the visual artifacts. Since the shadow maps of each tile are independent, their creation can be parallelized and spread across frames, they could be cached for later reuse, and could have multiple levels of detail (not yet implemented). A per-tile shadow map size of 2048x2048 texels seemed to work well. For reference, a tile is around 130 feet on a side for these scenes and there are about 400 total tiles with 100 or so visible on average.


Water Shadows

I decided to start with something simpler though - water shadows. In theory the surface of the water is the same as the terrain mesh, just with a different shader to handle the different material properties. Tree shadows work just fine for the water surface mesh, using per-tile shadow maps. Here are two images showing deciduous trees and pine trees shadowing the mesh, grass, and water. Both types of trees can be mixed together, but it looks cleaner if I show separate screenshots of the two types of trees.

Deciduous tree shadows on the water surface.

Pine tree shadows on the water surface.

Note that the terrain mesh doesn't cast a shadow on the water, trees, etc. This is because it's difficult to determine which mesh tiles are shadow casters for each receiver tile. A distant mountain can cast a shadow very far away when the sun is low in the sky, and searching for that mountain for each tile can be time consuming. The distant mountain would need to be rendered into the shadow map of every tile it cast a shadow on, even tiles that are far away. However, the mesh and grass are correctly shadowed by the terrain. Rather than using a shadow map, the mesh shadows use a modified "wave surfing" algorithm to trace shadow rays across the grid of 2D mesh tiles. This is done on the CPU, and uses the mesh surface height arrays directly. For each mesh vertex/shadow texel, a single 0 or 1 weight is determined from testing whether the mesh height at that vertex is above or below the shadow ray. This works well for the mesh, is fast (especially using multiple threads), and is compact to store. However, it only works for a fixed z height value at each {x,y} vertex. This doesn't work for the water surface, which has a different height from the terrain mesh. If I reran the algorithm using the max(water height, mesh height) and cached a different set of shadow weights it would be correct, but this is twice the computation and storage cost. It's even more difficult for objects such as trees that can have many branches/leaves at the same {x,y} position but different z heights.


Tree Trunk and Branch Shadows

Next, I added shadows for deciduous tree trunks and branches. This seemed like the easiest part of the tree to add shadows to, since the shader is the same as the one used in "fixed ground mode" (those smaller scenes with houses and buildings), which already has tree branch shadows. All I needed to do was to setup the shader variables and bind the shadow maps of each tile as was done when rendering the mesh and grass. Here is how tree branch shadows look:

Deciduous tree trunk and branch shadows. The sun is behind the camera.

The branches have shadows but the leaves don't. It looks a bit odd and unnatural, since the leaves on the bottom of the tree are too bright. We'll get back to this issue later.

Next I added shadows for pine tree trunks. These generated pine trees don't have any smaller branches, only needles - I just call the green parts "leaves". Originally, the pine tree trunks used a unique custom shader, so the first task was to change them to use the same shader as the deciduous tree branches, which already included shadow map support from the previous step. After that it was easy to enable shadows. Here is what they look like:

Pine tree trunk shadows. The sun is behind the camera.

Shadows don't add too much realism to pine tree trunks, since they are mostly in shadow anyway and don't often face toward the light. You can only see the trunks lit when trees are on a steep hill or the sun is low in the sky. However, they are basically free in terms of runtime and code complexity. Also, the trunks are no longer so bright compared to the rest of the tree.


Leaf Shadows

I decided to make an attempt at plant shadows before moving on to tree leaf shadows. Plants and trees use the same leaf shader. I wanted to start with plants since they're easier, because they're smaller on screen and performance/pixel fill rate isn't a big issue. The existing leaf shader performed lighting per-vertex (4 leaf corners per quad) for efficiency. Since the 4 vertices all have the same normal, the lighting terms are the same for every pixel in the leaf. Well that was the case, but this is no longer true when shadows are involved, since shadow boundaries can cross through the center of a leaf. Thus, the first task was to move the lighting computation from the vertex shader to the fragment shader for per-pixel lighting. After that, it was more copy-and-paste from the tree branch shader code to make it work. Oh, and merging in the two-sided translucent leaf lighting code where leaves can be lit from behind. Here is the result - you can ignore everything but the small (tall/thin) plants.

Plant leaf soft shadows. The sun is behind the camera.

Great! Tree leaf shadows should be easy now, since they use the same shader, right? Not exactly. Yes, they did mostly just work the first time, but the performance was poor. In some cases this cut the frame rate nearly in half. The worst case was under 30 FPS (frames per second), which was unacceptable for a realtime engine. I knew this would happen, which is one of the reasons I waited to long to add leaf shadows. The problem is that tree leaves overlap on the screen - a lot. When the camera is deep in the middle of the trees there could be dozens of leaves covering every pixel, and they're all drawn on top of each other.

Fortunately, there were various optimizations to make:

• Sorting the trees front to back (based on camera position) helped improve early Z fragment culling on the GPU. If the leaves from the nearest tree block most of the camera's view, then the leaves behind them don't need to be drawn.
• Disabling multisample anti-aliasing for tree leaves helped somewhat (see below)
• Skipping shadow map lookup for leaves facing away from the sun helped for pine trees
• Other various shader optimizations gave minor improvements

Even after all of these optimizations, the framerate was still too low for some views, in particular when looking down at a dense area of trees from above. This is the case where trees don't occlude each other, but instead occlude themselves top-to-bottom, which would require sorting every leaf of a tree front-to-back. I decided to go back to computing per-vertex leaf lighting. Since the leaves are so small, it's hard to tell the difference between per-vertex and per-pixel lighting anyway. From a distance they looked identical, and the framerate was much better. In fact, it was about the same as the framerate before I enabled tree shadow maps since the optimizations above helped so much, even when shadow maps were disabled. Nearby leaves had gradual shadow transitions across their surface rather than sharper shadow boundaries. This is less precise, but actually looks better considering the softer nature of leaf shadows. Here is how tree leaf shadows looked at this stage:

Tree branch + leaf soft shadows.

Here's another screenshot that includes water as well. There are some difficult-to-see reflections of the trees in the water, where the reflections also have shadows. Maybe I'll add a reflection screenshot in a later post.

Tree branch + leaf and water shadows.

I made a few final tweaks to my shadow map PCF (percentage closer filtering) to blur the sharp edges a bit more. This change mostly affects the mesh and tree branch shadows, which are per-pixel. It's difficult to tell the difference in the final image, unless the camera is very close to the mesh. But here is the final version anyway:

Final tree shadows after some addition tweaks to make them softer.

There was still one final problem to solve. Distant trees occasionally had bright pixels that randomly sparkled as the leaves moved in the wind. It was especially noticeable at night when the lighting level was low. The effect looked like fireflies and was actually pretty neat, but not what I was looking for. It took me a while to experiment with the shaders to track this one down. It turned out to be some problem with multisample anti-aliasing that I couldn't quite understand. I disabled anti-aliasing on tree leaves and the problem went away. In addition, this improved the frame rate slightly and made the nearby trees blend with the distant tree billboards better, improving the level-of-detail transition. This is because the billboards use a single large polygon rather than many small polygons, where anti-aliasing has little effect. The only downside is that medium distance trees (geometry where leaves are a few pixels in size) were not anti-aliased and flickered a bit when the camera moved. However, the benefits seemed to outweigh this so I left MSAA disabled. Here is an updated screenshot that's not much different:

Trees with leaf multisample anti-aliasing disabled - higher framerate, blends better with billboard trees, but sharper leaves.

If I increase the density and number of trees, it starts to look more like a forest and less like a meadow. However, the framerate drops significantly. I'm not sure the framerate is high enough for a game, but it will do for a demo where I can get some good screenshots.

Dense forest shown at ground level. Shadows make the forest floor seem darker.

Here is a view from above, where you can see just how many trees there are. I estimate there are 10,000 visible trees here, each one with 10K-20K leaves. That's 100M-200M total leaves! Do we have enough for a real forest yet? The framerate is down to 30 FPS but still feels fast enough for a demo. I have never seen a game or tech demo with nearly this many trees at this detail level. I've even implemented player collision detection with all these trees. Can you tell which trees are real geometry and which are billboards? I can't tell very easily in this screenshot. I'll give you a hint: the billboard trees don't have true shadows. I suppose I could add billboard tree shadows; however, they are normally beyond the distance at which I have shadow maps cached (due to performance reasons noted above).

Dense forest from above: 10,000 visible trees of 5 different species with shadows at 30 FPS.

The forest consists of 5 different tree species, each with their own parameters, branch textures, and leaf textures. Some of these parameters can be configured at runtime. There are also some smaller bushes mixed in at ground level (a new addition) to improve the amount of "ground clutter". The probability of generating each species of tree varies spatially over the scene, which is why different areas are dominated by one type of tree. This is intended to simulate multiple biospheres, at least at a small scale. There are a total of 50 unique trees that are each instanced many times. The number is limited by GPU memory for storing the leaf + branch geometry and all of the billboard textures.


Pine Tree Shadows

The final step was to add shadows for pine tree needles/leaves. The pine tree model assumes fully opaque leaves that transmit no light to the back side. This is basically the same as tree branches, and can use almost the same shader. The only real difference is support for alpha masks for transparency. Each pine tree is composed of only 30 quad billboards / 120 vertices with an alpha mask to produce the different branches. I was able to factor out all of the shadow map code and share it between the tree trunk/branch and pine tree shaders. This change added pine tree self-shadowing, at least for nearby trees, which made them loom more real. Since the leaf quads are large relative to the shadow map resolution, I had to use per-pixel lighting/shadowing. Here is a another screenshot:

Pine trees with full self-shadows and shadows from nearby trees.

Day and Night Cycle

3DWorld has a full day/night cycle, with both sun and moon. Here you can see how the trees look in moonlight. Both the sun and moon produce shadows, and for a brief period of they light the scene together, with two sets of shadows (not shown).

Trees at night, illuminated only by moonlight. With shadows.

There is an option to enable continuous time elapse at various scales from realtime to around 10s per simulated day. When the sun and moon positions change, this invalidates the shadows and requires rebuilding the shadow map and terrain mesh shadow matrices. The rebuild time is around 100ms: interactive, but not realtime. Instead of rebuilding the shadow maps every frame, they are only rebuilt when the sun or moon move by a specified incremental amount. This way, most of the frames are fast and rendering can mostly be in realtime.

Update: I just replaced some of the tree and plant leaf textures with higher quality versions. They look better close-up, but don't look much different (other than differences in  average colors) from further away. I need to do a bit more work on the colors at the leaf edges where the texture fades to transparent. Right now the leaf colors are more consistent across the species of trees, which makes the different clusters less obvious. I'm not sure if that's good or bad - maybe more realistic, but less variety? I already have too many screenshots in this post so I won't add any more. Maybe next time, if I continue to work on trees.

Update 2: I fixed the tops of the pine trees so that they look better.

Pine trees with shadows.

Update 3: I adjusted the deciduous tree trunk curvature parameters to make it smoother and remove that odd bend near the base of the tree.