The basic premise of the algorithm is that you seed a volume with a number of randomly scattered points. Then you spawn an initial starting Node or set of Nodes, wherein a node is just a 3D position. Then you iterate a number of times. At each iteration, you iterate through the list of points and for each point, calculate the node that is nearest to the point. If that node is within a certain specifiable distance, then the vector from the node to the point is calculated, normalized to unit-length, and added as "influence" to the node. When all points have been iterated and added their influence to a node (if any) then the nodes themselves are iterated and for each node the list of influence vectors is averaged, and the average vector is used to determine the direction in which to add a new node. Nodes are added as new positions located a specified distance along the vector. After all nodes have been iterated, then the point list is iterated again to check each point's distance to the nearest node. If this distance is less than a certain kill distance, then the point is removed from the list. The result of this algorithm is a tree of connected nodes that form line segments that can be used to generate a tree.
I decided to put together some experimental code in Lua to try it out. It actually works pretty well so far, though it's slow. I generate the tree as described above, then iterate the tree structure recursively to calculate the thickness of the tree at each node. A node thickness is determined by the sum of the cross-sectional areas of its children. Once I have assigned a thickness to each node, I set up a voxel structure and rasterize density fields centered on the line segments into the voxel structure. The density value for a given point in relation to a tree segment is calculated by finding the point on the segment nearest the point in space, and using the distance between the two points to calculate the attenuation of the field based on a maximum distance computed as an interpolation of the thickness values for each end of the segment. Any point within the envelope defined by this thickness parameter is solid, anything outside of it is open.
Once all segments have been rasterized into the voxel field, I peel off a mesh.
Currently, I am simply using the PolyVox marching cubes extractor for this. This situation is not optimal, as you can see from the "bumpy" appearance. This is due to the marching cubes algorithm using the voxel grid as the density mesh for constructing the isosurface. I am in the process of writing a marching cubes extractor that will extract the mesh directly from the density field equations represented by the node line segments, rather than via an intermediate voxelization step. Unfortunately, this is requiring that I be a little smarter about organize the tree of segments in order to facilitate calculating density values quickly and storing the surface cells so that I can generate a sufficiently dense mesh.
Right now, a lot of things are hard-coded, but there are a lot of ways in which this system can be parameterized. Once I have built the improved isosurface extractor, I'll start working on parameterizing everything. I especially like how you can control crown density, shape and appearance, as well as overall branching, thickness and appearance of the tree to create "fantasy" type trees. The artwork for GC is very fantasy-themed, so I prefer tree models that are "interesting". Your standard L-system based tree really isn't all that interesting, since it is hard to really control the final shape of the crown.
Think bonsai trees for an idea of the kind of trees I'm really trying to generate. Gnarled, twisty, cool. My code isn't quite there yet, but there is great potential. Once I can start playing with the seed point generation, I think I'll see some cool stuff.
