 |
| Terrain based planet with trees |
- 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
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 |
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) |
 |
| CA Black Oak without leaves |
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 |
 |
| The billboard sprite rendered for the Weeping Willow tree type |
 |
| LOD #3 of CA Black Oak, four vertices and two triangles |
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 |
 |
| 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:
 |
| Tree count: 5 Lod-0, 21 Lod-1, 2938 Lod-2, 132459 Billboards |
 |
| Tree count: 7 Lod-0, 24 Lod-1, 1209 Lod-2, 57326 Billboard |
 |
| Tree count: 14 Lod-0, 35 Lod-1, 783 Lod-2, 39456 Billboard |
