Recently I stumbled across the Procedural World Blog (https://procworld.blogspot.de/). It has a nice post on how to generate trees algorithmically. They use the so-called Space Colonialization algorithm [1]. Basically, a large number of attraction-points is chosen randomly within the volume of the soon-to-be tree crown and each of these points excerts an influence on the sequentially growing branches. That post is from 2010 and there has been considerable progress. Just a quick glance into literature:
- Space Colonialization is actually based on a publication on leaf ventilation patterns (the branching structures within a leaf) [2]. The authors found that what works for leafes only needs some minor adjustments to be applicable to whole trees [1]. Copy, transform, combine – that’s how nature works after all.
- Guiding Vector Trees are created by choosing shortest paths between randomly sampled points within a volume. To avoid a straight line from the stem towards the tip of the branch, path weights are calculated by the distance towards the direction of a guiding vector. That is a vector that changes gradually based upon the vector of the parent node [3]. The authors worked towards this method in two prior publications that propose very similar algorithms [4,5] and might be helpful to understand some of the details.
- Procedural Branch Graph is a method created for fast real-time creation of trees within a virtual reality (yeah, that’s just to make it sound more fancy. You could of course use any of the above trees, if you sample a low poly version). But they propose some useful hints on how to process the 3D mesh structure of the tree for performance [6].
Furthermore there are some interesting approaches that start with a complete tree model:
- Pirk et al. animate a naturalistic growth process [7].
- Again Pirk et al. show how to transform a tree skeleton so that it responds to obstacles and lightning in its proximity [8].
- Ao et al. choose a clever representation of the tree structure, called Ball B-Spline Curves, that allows for a cheaper calculation of motion [9]. Moving tree meshes – well that’s cool.
Personally, I find the Guiding Vector Tree approach promising. The rendered images provided in the paper show some convincing examples of really beautiful, realistic-looking trees. In the following posts I’ll explain some of the details of implementing such an approach in C# and Unity.
PS: github of the Unity source code
A tree structure generated by the Guiding Vector Tree approach. Not exactly a beauty yet – but single line rendering seldomly is.
Sources
[1] Runions, Adam, Brendan Lane, and Przemyslaw Prusinkiewicz. “Modeling Trees with a Space Colonization Algorithm.” NPH 7 (2007): 63-70.
[2] Runions, Adam, et al. “Modeling and visualization of leaf venation patterns.” ACM Transactions on Graphics (TOG) 24.3 (2005): 702-711.
[3] Xu, L., & Mould, D. (2015, October). Procedural tree modeling with guiding vectors. In Computer Graphics Forum (Vol. 34, No. 7, pp. 47-56).
[4] Xu, Ling, and David Mould. “Synthetic tree models from iterated discrete graphs.” Proceedings of Graphics Interface 2012. Canadian Information Processing Society, 2012.
[5] Xu, Ling, and David Mould. “A procedural method for irregular tree models.” Computers & Graphics 36.8 (2012): 1036-1047.
[6] Kim, Jinmo. “Modeling and Optimization of a Tree Based on Virtual Reality for Immersive Virtual Landscape Generation.” Symmetry 8.9 (2016): 93.
[7] Pirk, Sören, et al. “Capturing and animating the morphogenesis of polygonal tree models.” ACM Transactions on Graphics (TOG) 31.6 (2012): 169.
[8] Pirk, Sören, et al. “Plastic trees: interactive self-adapting botanical tree models.” ACM Transactions on Graphics 31.4 (2012): 1-10.
[9] Ao, Xuefeng, Zhongke Wu, and Mingquan Zhou. “Real time animation of trees based on BBSC in computer games.” International Journal of Computer Games Technology 2009 (2009): 5.