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.