John Whigham's Blog: Trees

Moving from the planetary scale to something a bit smaller, I've been experimenting with adding some vegetation to my terrain based planets - specifically trees for now although I also hope to add grass, flowers and other flora in due course. Sticking with the Osiris project's procedural generation axiom I want to use algorithms to create not just the placement of the trees but also their appearance as far as possible. I need to be pragmatic however and while I doubt it's practical to procedurally generate down to the individual leaf level it feels like there is a suitable compromise to be found

Terrain based planet with trees

There are several decisions that need to be made when adding trees to a terrain model and functional requirements that need to be implemented:

where to place the trees
what types of trees should be present at each point
create a realistic looking mesh for each different type of tree
be able to render potentially tens of thousands of trees at real-time frame rates

I've spent more time on some of these points than others and hope to spend more time fleshing out the weak points as time allows, but this post gives a summary of progress so far.

Where to place the trees?

The first thing to decide is where to put the trees. A planet is a pretty big place and while I want some nice densely forested areas it wouldn't be very interesting to have a uniform covering of trees everywhere - there needs to be some logic to it. This is one of the areas that I haven't spent as much time on as I hope to, an interesting reference I have found though is Generating Spatial Distributions for Multilevel Models of Plant Communities which appears to offer a fairly practical yet real world representative algorithm for modelling where plants should grow within an area and selecting from a range of tree types.

A larger scale decision needs to be made first though to identify the areas to be populated in the first place. Ideally this would be a mixture of randomness combined with climate and geophysical parameters so for example particular types of tree would tend to grow near water, within certain height ranges, within certain latitudes and on particular types of soil and slope.

For now however to get the system going so I could focus more on the generation of the trees and rendering them I have opted for a simpler noise based approach where each terrain tile is assigned a possible maximum number of trees then for each of these potential trees a random point is chosen within the tile. This point is then used to evaluate an exponential turbulence function, low values of which are ignored to create gaps between the tree clumps while high values are used as the probability that a tree will indeed be placed at that point. Because of the marble vein like pattern formed by such a turbulence function this tends to produce interesting shaped clumps of trees with organic looking edges.

Tree placement probability map for a terrain tile generated from a turbulence function

Birds-eye view showing the resultant tree placement from the probability map

This really is a quick and dirty approach and doesn't even take into account factors such as the slope of the terrain - the only limiting factor in fact is that trees aren't placed below the water line!

What type of tree to grow?

Generating a unique tree mesh for each of potentially millions of tree instances is obviously prohibitively expensive in terms of computation and memory so I instead store a palette of tree type meshes one of which is used for each instance placed on a terrain tile. Each instance can have a unique orientation around the tree's primary axis along with a unique scale so there is still scope for plenty of variation on the terrain even with only a limited selection of meshes to choose from.

The decision as to which tree from this palette to use at each point is fairly closely tied to the above decision about where to place the tree in the first place. The same environmental and geophysical attributes that drive one inform the other as you should for example expect fir trees on colder steeper terrain and palm trees in hotter drier climes.

For now though I took the simplest of shortcuts and pick a random entry from my tree palette.

What should a tree look like?

This is one of the areas I've spent more time on as it's central to getting pretty much anything tree like on screen. Of course I could simply gone out to TurboSquid or similar and picked up some tree meshes that I could have plonked down on the terrain but that wouldn't really be holding true to the whole procedural ethos - it also wouldn't have been very interesting.

Instead, I wanted to be able to "grow" my own tree meshes using procedural techniques which would be both an interesting technical challenge and allow me to produce as many variations as I felt necessary without finding pre-built meshes for each. There are a couple of fairly well known approaches to growing trees in this fashion, space colonisation such as utilised here can produce good quality results while L-System or grammar based approaches are also highly effective.

I decided for this project on a fairly procedural parameter driven approach as I felt it was a little more controllable for producing a wide variety of plants although I think it would be interesting to try space colonisation at some point if time allows. My primary reference is Jason Weber and Joseph Pen's excellent paper Creation and Rendering of Realistic Trees where they describe a procedural algorithm that takes a set of parameters describing first the trunk, each of three generations of stems/branches and finally leaves to constitute a complete tree.

The parameters offer a great deal of control over the primary visual characteristics of the tree and as they helpfully provide a detailed description of the algorithm and exemplar parameters for four types of tree it's reasonably straightforward to implement and get something usable out of it - an achievement not all published papers manage in my experience. To speed up development however I decided not to implement the entire system in C++ but instead use the Lua scripting language that I had previously integrated to facilitate procedural architecture generation (which I plan to post about in the future). The core algorithm from their paper is written in Lua which generates a representation of the final tree from it's parameters, there is a shared common file that implements the guts of the code and a separate much smaller file per tree type that pretty much declares the parameters for the tree in a Lua table then makes a few function calls into the common code passing those tables as parameters.

Using Lua makes for very rapid iteration as I can change one of the files in Notepad++ then Alt-Tab back to Osiris and have it instantly reload the file and regenerate the tree mesh without having to stop the program. This makes it painless to not only find bugs in the code but also to play with the tree parameters an an almost interactive basis - something that is pretty handy when trying to map parameters designed to produce tree meshes with potentially millions of polygons down to some that produce a similar result with just a couple of thousand.

Once the Lua code has produced the tree representation then the C++ takes over to do the heavy lifting of turning that into a renderable mesh. I've made four types of tree so far using modified versions of the parameters from the Weber and Pen paper:

"Black Tupelo" (4670 vertices and 5988 triangles)

"CA Black Oak" (11490 vertices and 13694 triangles)

"Quaking Aspen" (8969 vertices and 10416 triangles)

"Weeping Willow" (4850 vertices and 6940 triangles)

The tree palette used at runtime also includes leaf-less versions of these to represent dead or sickly trees and to add a bit of variety, there is currently a 15% chance that any particular tree instance won't have leaves.

CA Black Oak without leaves

Rendering trees

With tree meshes to render and a crude approximation of where to place them the final challenge is of course actually rendering them. There are two main challenges that face real-time applications when it comes to rendering trees and flora in general.

Firstly the sheer number of vegetation instances that a typical view can contain presents a major challenge. As you may have noticed from the screenshots above each tree model can contain from a couple of thousand triangles up to ten thousand or more. Even with the phenomenal grunt of modern PC graphics cards there is a very real limit on the number of those that can be drawn at interactive frame rates. Off-screen culling is an obvious start with trees that are off the sides of the view or behind the camera being ignored but on a panoramic view that can still leave many tens of thousands to be processed.

The solution is pretty obviously a level of detail (LOD) approach where trees that are nearer the camera are drawn using a higher resolution representation than those further away - the distant trees are very small on screen so if done well the drop in fidelity shouldn't be very obvious. To this end, once the Lua code has generated the tree representation the mesh generator produces not one but three different versions of the mesh each storing less detail than the previous one. LOD level #0 is the maximum detail version (shown above), level #1 uses fewer segments for the trunk and primary branches, fewer leaf fronds and removes the secondary branches altogether while level #2 reduces the trunk segments and leaf fronds yet further and also loses the primary branches leaving just the low detail trunk itself and the leaves.

By scaling up the remaining leaf fronds slightly in each LOD the apparent volume of the tree is preserved despite being made up of significantly less triangles. Which leaf fronds to keep and which to remove at each level of detail is based upon the K-Means Clustering algorithm to ensure as even a distribution of remaining fronds as possible in an effort to also preserve the tree's overall shape and silhouette.

LOD #0 of CA Black Oak, 11490 vertices and 13694 triangles

LOD #1 of CA Black Oak, 1810 vertices and 247 triangles

LOD #2 of CA Black Oak, only uses 40 vertices and 54 triangles

Although the lowest lod mesh above uses only a handful of triangles when drawing tens of thousands of them it's still a lot of work for the GPU so an additional LOD level is also produced by rendering the maximum detail version of the tree to a render target then saving that off as a texture. This texture can then be used as a billboard sprite to render the most distant trees using just two triangles each. As this billboard sprite is aligned to always face the camera when rendered to the screen several views of the tree are generated from different elevations to prevent the visual effect of the trees looking like they are lying down when viewed from above.

The billboard sprite rendered for the Weeping Willow tree type

Here you can see that a side elevation is produced along with views from 30 degrees, 60 degrees and 90 degrees of elevation. The appropriate section of the texture is chosen when rendering the billboards to most closely replicate the actual viewing elevation.

LOD #3 of CA Black Oak, four vertices and two triangles

I've shown the effect large on screen here for clarity but of course in practice this is all happening on trees that are only a few pixels tall so the crudeness of the effect is effectively hidden.

To complement the tree LOD system I also use hardware instancing where a single tree mesh can be drawn multiple times by the GPU without requiring multiple draw calls from the program. In my scenario each terrain tile has a secondary vertex buffer containing the positions, orientations and scales of each tree instance to draw which is used in conjunction with the vertex buffers for the tree meshes themselves to allow all instances of a particular tree type within the tile to be drawn with a single draw call.

Such hardware instancing conflicts completely with off-screen culling however as the program doesn't get a chance to test individual tree instances so I only use it for the billboard level LOD rendering where the cost of each instance to the GPU is very low and any culling done on the CPU would probably be more expensive than just trying to draw the off-screen billboards.

Alpha Blending

The second challenge with vegetation rendering is that leaf textures tend to work better when they can be alpha-blended into the scene allowing their rough edges to fade out to produce a nicer effect. For this alpha blending to work properly however the triangles need to be rendered in a back-to-front order so leaves at the back of the tree are drawn before those at the front - performing this sorting is prohibitively expensive on the CPU though and not really an option. Alpha blending also does not play well with the deferred rendering that is used to draw the terrain itself - a double whammy.

For now then I have to live with hard edges to my leaf textures which avoids the sorting problem but definitely doesn't look as good. There are some minor tricks that can be used to improve the situation however by playing with the alpha threshold that is used when deciding which pixels on the leaves are transparent and which are not. As the alpha value on the texture varies smoothly across the boundary from transparent to semi-transparent to opaque pixels by choosing where the threshold is for non-alpha blended rendering I can control how much of the texture is visible. A low threshold for example will cause most of the leaf texture to be used with only the absolutely transparent areas hidden while a higher threshold will cause more of the texture to be considered transparent with less and less rendered to the screen.

By varying the alpha threshold on a per-leaf basis a couple of aesthetic improvements can be made. Most significantly by using the angle between the leaf's normal and the view vector to vary the threshold leafs that are almost edge-on to the view can be made to render less of their pixels removing many of the unsightly splinters of polygon that would otherwise result:

Without view dependent alpha threshold edge-on leaf polygons are unsightly

With view dependent alpha threshold the edge-on leafs render fewer pixels and produce a better effect

A more subtle effect along the same vein is to also vary the alpha threshold of a leaf based upon it's distance from the centre of the tree. The main aim here is to allow the branches to stick out more around the periphery of the tree which I think looks a little more realistic:

No distance alpha threshold effect, all leaves are consistent

Distance based alpha threshold - the leaves around the ends of the branches are less visible

Future Work

While I'm quite pleased with the work so far there are still some fairly major areas I would like to develop. The most obvious one to me is the inclusion of shadow mapping on the terrain so the trees and everything else I place there don't look like they are floating around above it. While it's a reasonably complex effect to get right I think this alone would make a massive improvement to the visual appearance of the terrain and the trees. Other ground cover such as grass and flowers would also add a lot providing something of the ground clutter found in typical real world scenes.

While the tricks I employ improve the leaf edges alpha blending would definitely make them better. I've been reviewing an article in GPU Pro where alpha blending for vegetation is performed as a post-process using a combination of additive and maximal alpha values. This would sit well with my deferred rendering pipeline although it would incur some additional render cost - definitely an avenue I want to explore though.

The placement of trees could obviously be far more intelligent although this will require a degree of topographic and environmental data that I currently don't simulate. Adding more tree types such as palm or fir would also help add variety along with autumnal or snowy appearance styles where the climate dictates.

This post is already way past the TL;DR threshold though so I'll leave it there for now. Hopefully if you made it this far you found it interesting. I'll leave you with a few more screenshots: