realistic procedural tree generation
A subdivision surface is a polygon mesh that has been recursively refined until it approximates a smooth surface. With each refinement step the faces are subdivided and vertex positions are smoothed. This allows curved geometry to be modelled with the efficiency and convenience of a polygon mesh.
The models that TreeDraw produces are constructed as a set of generalized cylinders swept along bezier curves. The cylinder is generalized as its start and end radii are not necessarily the same. Every branch in the model is created as a separate cylinder. To create the illusion of connectivity the cylinders are intersected at their meeting points. Unfortunately, this approach results in abrupt transitions at points of furcation as wells as gaps between branches. Examples of these issues are highlighted in the figures below.
It was postulated that the transition between connected branches could be more
realistically modelled as a subdivision surface. To investigate this a coarse mesh
had to be generated for the entire model and then converted into a subdivision surface.
From this two research questions arose:
1) Can subdivision surfaces be used to emulate the smooth curves found in real trees?
2) Is it possible to generate a single mesh form a directed acyclic graph?
The mesh is generated from a graph describing the branches of a tree. This graph
is produced by the TreeDraw L-System Compiler. Generating the coarse control mesh
from the graph is a two step process:
1) construct the branch segments between joints
2) construct the joints that connect the branch segments
Creating the faces which constitute the joints is the most challenging aspect of
the design. The approach taken is to project the ends of the branches onto a sphere,
and then construct a 3D convex hull around them. Once the hull is completed, the
ends of the branches are restored to their original positions. The convex hull algorithm
that was implemented is the Randomized Incremental Algorithm first proposed by K.L.
Clarkson and P.W. Shor in 1989. The figure below illustrates the steps envolved
in joint construction.
Ttexture coordinates are assigened as the face are formed. The assignment is such that a bark-like texture is tiled along the length of the length of each branch. Unfortunately, zig-zagging textures seams are introduced at the across the joints.
The mesh is now complete, however, it is a faceted and unnatural representation of a tree. To achieve smoothness three iterations of Loop subdivision are applied to the mesh. With each iteration the mesh better approximates a smooth surface. Loop subdivision is designed to be applied to triangular faces, and was chosen because the faces created by the convex hull are triangular. Every triangle is sudivided into four smaller triangles by splitting the edges into two. The texture coordinate of new vertex, which splits the edge, is simply the average of the texture coordinates assigned to the endpoints of the edge. This introduces a slight distortion in the texture mapping near the joints.
In order to evaluate whether subdivision surfaces are a better approach to modelling branching stuctures an experimental study was conducted. In this study, 39 participants were asked to assign a score of realism to images of the original models and images subdivision surface models. The score was a measure of how realistic the partipants felt that the pictured model was. The results of this experiment indicate that the subdivision surfaces are perceived as more realistic, at the p = 0.5 significance level.
