L-Systems & Vine Growth

I began experimenting with growth over the scene. I took the resultant nodes from the distribution system as a starting point for the growth and recursively added further child nodes to build up a network of branches.

Growth-System
My research into L-Systems gave me a lot of results directed towards cellular and fractal structures constructed recursively using a simple set of rules. This alone produces uniform, unnatural vegetation. To simulate the diverse variation in real plants, other factors must interfere with the fractal properties. Streit (Federl and Sousa) suggested an algorithm to take pre-existing plant models and warped them based upon gravity and plant stimuli. e.g. light, local plant life.


I required an algorithm capable not of physically accurate growth, but generating visually pleasing vegetation that could react to an environment. I took the concepts of gravity, stimuli and recursion, creating a simple growth algorithm based upon weights to produce a reactionary plant structure. I began experimenting with constraints to shape the plant around the scene in order to produce vine type structure.


My initial attempts to expand branches from nodes resulted in some visually acceptable results. The vines would creep along floors and drape over edges, the results appeared natural. For each node I created a growth direction based upon several weights; sun direction, gravity, previous growth direction. I cast a ray in that direction and any resultant collision information was used to ensure the direction did not intersect the scene. However, the algorithm became fairly unstable in geometrically complex areas. Vines would exhaust space and intersect the scene, continuing to growing downwards due to gravity. The ray-casting method was just too unstable.


In searching for a solution to the algorithms instabilities, I discovered an ivy generation implementation capable of creeping ivy over a mesh surface. The author (Luft), used a much simpler, more robust approach. Rather than attempting to repel growth, nodes were attracted to a surface based upon distance. I implemented a similar approach, brute force testing against all triangles to find the closest point on a surface, and then clamping the new child node to this surface. The results were far more stable and produced good results even across a larger scale.

Ray-casting Method

Surface Attraction Method

Real-time Updates
As the system is designed for testing control over the procedural algorithms, I decided to migrate the growth system to a real-time solution. The growth is performed in small iterations, allowing the updated node database to be redrawn each frame. This should provide faster and higher quality feedback when testing controls for the growth system.


An interesting bug also arose when moving to a real-time update system, a snapshot of the database had to be taken before each growth step to prevent concurrent iteration and manipulation. This forced each node to be searched within the real database and caused an explosion of branches when two nodes had the same position. This problem would occur particularly on mesh corners, where nodes would be constrained to exactly the same position.

For now the bug is fixed by merging matching nodes to remove any duplicates. However, perhaps running the growth system on a separate thread would alleviate both the bug and much of the overhead incurred with copying and searching within the database upon each growth iteration.




Distribution Culling
I earlier in the project development I suggested culling the distributed nodes by firing a hemisphere of rays into the scene to find an occlusion value. I implemented this concept and found the distribution patterns to be quite useful. As vines and other vegetation is likely to grow out of cracks and crevices in the ground, I constrained the distribution height and fired 16 rays from a possible node location into the scene to find the occlusion value. 

The results are a natural spread of nodes around the wall and tower, good for interesting vines growth over the scene.




Performance
While performance is fairly acceptable on small scenes with few polygons, it does not scale well to larger more complex scenes. Both ray-cast occlusion culling and closest surface point algorithms rely on brute force iteration through all the scene triangles. As these are the current application bottlenecks, both these algorithms will need improvement to attain higher performance.




References
Streit, L.; Federl, P.; Sousa, M.C. "Modelling Plant Variation Through Growth". 2005
Computer Graphics Forum. Volume 24, Issue 3, pp. 497-506.
Blackwell Publishing, Inc.


Luft, T. An Ivy Generator. 2007 
A tool to interactively model three-dimensional ivys.
http://graphics.uni-konstanz.de/~luft/ivy_generator/
[Accessed 17/01/2012]

Point Distribution

I began implementing some of the geometric math and analytical algorithms required distribute vegetation over a scene.

Raycasting
I wrote a raycasting algorithm to allow rays to be fired at a mesh and return information about the closest collision. Although I am not currently using it for distribution, I believe this can be used for a variety of purposes when attempting to cull distributed points. I could fire a ray towards the sun to check if a plant would have sunlight, or fire multiple rays in a hemisphere to find corners and crevices for plants to grow in.

Point Distribution

I worked mostly on implementing a high quality point distribution algorithm to position points across the  scene. I plan to use these points to provide initial spacial data from which plants can grow.

First the mesh is analysed and a list of triangle weightings are built, the weighting is dependent entirely upon area. I then distribute points across each triangle dependent upon the weighting and distance from other nodes. Once a node position is computed it is added into the node database, and a debugging render of the database is displayed.

My first attempt suffered from some ugly artefacts. The point density was lost on small triangles due to the triangle area being too small to add any points. You can see in the image above, much of the tower has no point coverage. Clamping the density to a minimum of 1.0 gave smaller triangles excessive point density. The solution was simply to accumulate the area from each triangle, allowing several smaller triangles to accumulate a point density (right).

Rand()

The distribution also suffered from an artefact that proved to be much more difficult to solve. Non-uniform distribution in larger triangles. Observing the image to the left, many of the points on the floor plane are distributed in the lower left region and along the edges of the triangle pair. It is even possible to discern mesh topology from the point density.

Mersenne Twister

My first conclusion was the c-standard rand() function was simply not good enough. I tried using Mersenne twister (Bedaux, 2003). The results on the left show slight improvement, however many of the artefacts still persist.

Rand() - Poisson Disk

I decided to try and force the points apart by implementing a Poisson Disk algorithm with the distribution. For each point I performed a brute force distance comparison against all other points in the node database. Only if the point is outside the radius of all other points can it be added to the database. To maintain the desired density, the algorithm will continuously attempt to add points until a maximum iteration count is met. The results on the left are much better, with points very evenly spread across the plane.

Rand() - Poisson Disk(Low Density)

Unfortunately the algorithm now had to perform thousands of wasted operations and still suffered from similar artefacts when given a low density. A low density could only be achieved providing triangle weights in the scene had a small variance and by tweaking the radius size, maximum iterations and density. I decided this would not be good enough for a generic algorithm and continued to research for solutions.

Rand() - (Turk, 1995)

To choose the position of a point on a triangle, I had initially used bilinear interpolation driven by three random numbers to interpolate between the points on a triangle. I switched to a new algorithm (Turk, 1995) for placing points, which relies on using random coordinates (u, v) to distribute points across a parallelogram. Any coordinates then outside the triangle boundaries are negated produce correct (u, v) coordinates inside the triangle. This finally gave the non-uniform results I was after.


The final algorithm gives controllable high quality non-uniform results, allowing for a minimum distance between points. Resultant nodes are stored in the database with correct positioning and normals.


Performance
I was interesting in investigating the scalability and performance of the algorithm as any user control would become very cumbersome to use if the algorithm became a large stall in the application. I was unsure how well the algorithm would handle larger scenes, because point radius check required a brute force O(n^2) number of of comparisons against all other nodes in the node database. I applied the algorithm to a much large scene (as seen below) and profiled the application.

The results were as expected, the application initially hung for a large period of time while processing the scene and the profiler results showed that the majority of time was spent performing distance comparisons in the node database.

I decided to redesign the node database in order to improve performance. I implemented a spacial hashing algorithm based upon Hastings (Mesit and Guha, 2005) . Each new node's position is hashed and indexed into an ordered multi-map. As I do not need to concern myself with volumes, the hashing becomes extremely simple and fast. After implementing the new node database I re-profiled the same scenario, and found the results to be very surprising. Not only did the algorithm increase vastly in performance, the algorithm bottleneck has now become the random number generation. The cost of finding a local node has become negligible.

References
Bedaux, J. "C++ Mersenne Twister Pseudo-Random Number Generator" 2003
http://www.bedaux.net/mtrand/
[Accessed 12/01/2012]


Hastings, E.; Mesit, J.; Guha, R. "Optimization of Rendering, Collision and AI Routines in Large-Scale, Real-Time Simulations by Spatial Hashing".
Summer Computer Simulation Conference 2005, USA


M. Matsumoto and T. Nishimura,
Mersenne Twister: A 623-Dimensionally Equidistributed
Uniform Pseudo-Random Number Generator,
ACM Transactions on Modeling and Computer Simulation,
Vol. 8, No. 1, January 1998, pp. 3-30
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html.

Tulleken, H. "Poisson Disk Sampling". 2009
Dev.Mag Issue 21, released in March 2008
http://devmag.org.za/2009/05/03/poisson-disk-sampling/
[Accessed 17/01/2012]


Turk, G. "Generating Random Points In Triangles"
Graphics Gems, 1995, pp. 24-28
Xerox Palo Alto Research Center, Palo Alto, Californi.

Framework Further Planning

To generate vegetation within the scene, I plan to investigate and implement L-System type fractals to produce believable results. I plan to use these fractals as an input to along with other constraints and forces to produce a database of nodes. Each node will contain a world position and a link to another node in the world.   This database will allow the vegetation to coincide and adapt with the scene and will provide the backbone from which I can explore and prototype.

For now I will abstract away entirely the concept of meshes and concentrate on developing hierarchical structures of nodes, displaying raw visuals to give feedback on the quality of the fractal behaviour.

Above is a large scale overview of the design I will be striving to implement. The primary focus of my project is not the quality of the systems design; However, I believe it is important to maintain a modular design. This will allow me to easily develop systems of increasing complexity such as the fractal system on top of the node database.

Framework

A simple and flexible framework for my project is born.

The rendering is performed using a basic D3D10 renderer. A little rough looking perhaps, but I plan eventually to use a deferred renderer from my graphics module, however this current system is flexible enough and will allow me to visualise experiments.

As the project will end focusing on control over the vegetation system, I will need the ability to rapidly prototype user controls. I plan to use the DirectX UI system that is included in many of the DirectX SDK examples, as the controls seem flexible and should be quick to implement.

The mesh loading is done using an open source model library, going by the name Assimp. After integrating it into the project I found myself less than pleased with results. The library is fairly well designed, consistent and also boasts a large variety of import formats, unfortunately it appears to have some very severe and undermining flaws. The dragon shown in the screen capture to the left took a good minute or so to load, more complex scenes such as Sponza take far longer and every model loaded leaves a 7kb memory leak! For now I will keep the library and work with simple models, however I shall be looking out for an alternative. The vegetation system will require more complex scenes for analysis and waiting several minutes to gather results is just not a viable option.