Friday, January 16, 2009

some plants and shrubbaries

This post is a round up of some papers about procedural plant generation.


Structural Simulation of plant growth and response ( doi? | springer | 2003 )
John Hart, Brent Baker, Jeyprakash Michaelraj

These trees are grown by modeling the trees responses to graivty and light. Different trees respond differently to gravity, there are two main types -
  • Gymnosperms (pine, spruce) have external seeds. These trees support their weight of their branches by adding extra material below the branches, that is "compression wood".
  • Angiosperms (apple) have seeds in a fruit. These trees, however, support their weight by adding additional material above the branches, causing it to be in tension, hence "tension wood"
These two types of growth produce different shaped branches and this model simulates that by widening the area of the trunk above/below the branch for Gymnosperms/Angiosperms.

The algorithm here is to
  1. Compute mass
  2. Compute center of mass
  3. Compute photosynthesis
  4. Compute growth rates
  5. Grow branches.
By knowing how big a branch is and how dense it is, these calculations are mostly straight forward. However photosynthesis is computed using (the old work around for openGL's "select" function) a test-render with the leaves on each branch rendered in a different colour.

The grow branches stage works by firstly killing branches that don't recieve enough light, and then boosting the growth rate of branches that photosynthesis most (collecte the most light). Branches' growth is then limited by the ability of the parent branch to support additional weight.

Because there is a collision between the strength of a tree (proportional to area of trunk) and it's weight (proportional to volume) this provides a natural mechanism for the tree to stop growing.

Because of the physical modelling used here, the resulting trees are very well ballanced (even if some branches are pruned during growth) and effectively compete for sunlight.

On a final pleasing note the paper begins with a comment about L-systems very close to my own opinion:

In an effort to make these models produce more realistic results, some have encoded the environmental influences, such as geotropism (sagging branches) directly into the L-system. While this allows the genetic model to include more detailed information about its reaction to external forces, it makes the model much more complex and difficult to decipher.



Voxel space automata: modeling with stochastic growth processes in voxel space ( doi | acm | 1980 )
Ned Greene

This is a really old paper that explores the use of voxels (3d pixels) as a representation for the environment of a vine. They show that testing for availbility of light (through monte carlo probing of the environment) and proximity (empty voxels know the distance to the nearest occupied voxel) is easily doable using a voxel representation. However the paper notes that it is hard to ("we didn't implement...") estimate surface normals using voxels.

Heliotropism (plants tracking the sun) is implemented by calculating a table of brightnesses and applying a low pass filter to find the brightest direction. The paper states that the simulation of heliotropism is exaggerated, but it does produce pleasing results.

To create the above image a model of a house was imported into a voxel grid. The plant model was then biased to grow with respect to this model (branches staying clear of the doorway, leaving allowed to hang down).

For its time this paper included lots of ideas that are still being explored today.



A Plausible Model of Phyllotaxis ( pdf | pnas | 2006 )
Richard S. Smith, Soazig Guyomarc'h, Therese Mandel, Didier Reinhardt, Cris Kuhlemeier, Przemyslaw Prusinkiewicz.

This is a slightly different take on plant synthesis. Phyllotaxis is the name of the patterns formed by leaves on the stem of a plant, and this paper implements a model of a biologist's hypothesis for how these patterns occur. There are numerous geometrical/mathematical/physical explinations for these patterns, but finally scientists seem to be trying understand how it happens in real plants. It's all to do with Auxin, the substance that stimulates plant growth (it's the stuff that causes elongation on the dark side of plants so they always face the sum (or at least that's the simple story)).

Reinhardt et al's Regulation of phyllotaxis by polar auxin transport describes the concentrations of auxin and the protiens that control it's location. By using a scanning electron microscope it's possible to see how the phyllotacic patterns emerge. The following is the tip of a growing shoot (apical meristem) showing the older (larger) shoots and the newer shoots growing between them.



Renhardt's hypothisis is (I think, was a quite biological paper) that auxin is mainly produced at the base of the stem and moves to it's tip. Any existing apex's act as an auxin sink (shunting it downwards in the centre of the stem where it doesn't effect the growth). If enough auxin makes it to the peripheral zone (just below the main tip, yellow below) a new shoot forms and becomes it's own auxin sink. In this way new stems avoid the existing stems:

auxin

This means that each shoot grows as far away from the previous shoots/sinks as possible. This paper implements a model of the various chemicals involved and produces a pleasing 3D simulation of the shoot.



As you can see the same model replicates the pattern observed in the real world. It can even be tweaked to describe the different observed modes of phyllotaxis.

However, as the authors recognise, lots of this work is still experimental and big assumptions/tweaks without biological justification have had to be made to get it to work nicely:

In the absence of experimental data, we tested a number of alternative formulas and found that the postulated exponential dependence of the localization of PIN1 on the concentration of IAA results in the most stable phyllotactic patterns.

This work produces some very encouraging results, for not just emulating plants but understanding how that form was created.




Modeling Trees with a Spcae Colonization Algorithm (pdf | doi | eurographics | 2007 )
Adam Runions, Brendan Lane, and Przemyslaw Prusinkiewicz




This paper doesn't use L-systems! A branching model is creating using a space colonization algorithm. As the trunk of the tree grows upwards it is attracted to a set of (maybe thousands) of attractors (above & left - blue balls). These are scattered around in the volume of the tree, representing a preferred density map of the final tree. As the trunk gets within a set proximity for each attractor, the attractor is removed.

Once the tree skeleton is complete, various filtering operation are applied to smooth transitions between the branches. Then cylinders (as the Mighty Maple paper describes) are positioned over the skeleton to create a decent skin. Leaves, flowers etc... are then added.

By positioning the attractors in different ways (uniformly through a volume, on the surface of a volume) using different volumes (cones, cylinders) a variety of different plants can be created.

Another paper also uses a particle system (but this time interactively) to reproduce 3D models of trees from photos or sketches. Quite realistic leaf density is achieved from a set of photos from a number of viewpoints.



A Morphological Study of the form of nature ( doi | acm | 1982 )
Yoichiro Kawaguchi



This early paper presents some techniques for imitating some features of nature based on spirals, and rendering these out in 3d.

"The forms of nature based on spirals and ramification are generated not through the use of object data calculated by measurement, but through the use of algorithmic structure based on the laws of nature."

Each chamber in the spiral is constructed as a skew cylindrical prism. These provide growth in the forward direction and are repeated and scaled by a set ratio ie - geometric progression. Knots are added to allow the spiral form to rotate and as a location to add branches.

A tendril plant can be created by allowing a knot to form new branch. There is an adjustment factor to move child branches away from the parents. There isn't a formal grammar behind this system, rather a successive application of rules. However some pleasing shell and horn shapes are created in some really fantastic colours.

How wish these where the days where a typewrite and a badly penciled-in formulae were enough to get you published.



Synthetic Topiary ( doi | pdf | 1994 )
Przemyslaw Prusinkiewicz, Mark James, Radomír Měch


Prusinkiewicz is a hard man to escape from in this field! It is curious how authors of procedural form papers tend to stick to a given domain; many of the techniques seem to be shared between the different domains but aren't exploited by the same people.

Anyway this paper presents a modification to an context sensitive, probabilistic L-system that gives environmental sensitivity. While evaluating, each derivation step is followed by an evaluation stage that returns environmental (eg positional) information as parameters.


The left image here shows a environmentally sensitive L-system that prunes itself to a elliptical outline. The right image show a more complicated L-system that back-tracks every time it reaches the boundary:

w: FA?P(x,y)
p1: A>P(x,y) : !prune(x,y) → @oF/(180)A
p2: A>?(x,y): prune(x,y) → T%
p3: F>T →S
p4: F>s → SF
p5: S → o
p6: @o>S → [+FA?P(x,y)]
Apologies if this makes no sense, simply we start with w and apply the rules until prune() becomes true, then the symbol S propagates back through the string to a previous bud that hasn't sprouted yet and starts again. So it's a backtracking space search technique. It also highlights one of my main issues with L-systems - they can be easily engineered in non-biological ways (here it's back prorogation) so that intrinsic simple beauty (and comprehendability) of the system is lost. This grammar tells us little about how plants grow and isn't the most sensible way to describe form.

All that being said, it does seem to create some great results.

A stochastic branching L-system is developed that simulates real-world observed branching tendencies (bifurcation ratio), and combined with the above pruning system to produce the final model. All that is left is to find some 3d surfaces (some define implicitly, like the dinosaur above) to prune the growth to.

Here's an implementation.




Modelling the mighty maple ( doi | acm | 1985 )
Jules Bloomenthal


From an acyclic graph this paper produces a nice curvy 1-piece polygonal tree. Assumes that at a branch point, any branch that goes straight-on-ish is a continuation. It is then possible to draw splines through these n+1 control points on extended branches to create a nice spliney-tree skeleton. This is a well cited paper that brings together several techniques that are still used today.

Discs are then extruded at different sizes along the branch splines, but leaving gaps at the branch points. These branch points are computed by using the nearest disc on each branch as a starting point and using a system of splines to form a basis for polygonization.

Because close ups of the branches may be required it is possible to change the acceleration along the spline (before adding the discs) to add additional detail into certain areas on camera.

Textures were used to improve realism. The thing of note here was that the bump map was extracted by X-raying a plaster cast of a bark-section, then digitizing it.

To model the above ground bumps that roots cause, blobby objects where added to the contours at the base of the trunk.



Approximate and Probabilistic Algorithms for Shading and Rendering Structured Particle Systems ( doi | acm | 1985 )
William T. Reeves, Ricki Blau


you learn something new every day :-
Particle systems were first used to model a wall of fire in the Genesis sequence from the film Star Trek II: The Wrath of Khan [11].

The model of the tree they use is a recursive set of branches with leaves/pinneedles on the smallest branches. The forest has a certain probability dist for all trunks (width = mean width + random * delta), similarly for the heights that branches start occurring at. There is a bounding volume that stops branches growing too far from trunks. The child branches take some parameters from their parents, modify some and take other from the global tree model.

Different types of trees have different models.

The above image has 18 thousand clumps of grass, rendered with 733,887 particles. These are rendered using ambient, diffuse and specular components. A stochastic model is used as it would be too very expensive to raytrace for these properties on a per particle basis (this seems to be the general drawback for particle systems, esp wrt external shadows). So the diffuse colour changes the deeper into the tree we are from the lit side.

Rendering the lit particles to screen involves rendering the furthest away tree first, then the next nearest etc... (painters algorithm) Each subtree also has to be sub-sorted by depth. The information for each tree is procedurally generated for each rendering of the tree, and then disgarded (this is a really neat feature of procedurals).

Wind is simulated using a 2D tensor field that drives "wind particles".

These trees really blow away the competition image-quality wise (for their age) - must have been expensive to compute tho! Was rendered on "an essentially idle VAX 11/750 with floating point accelerator and 4Mb of memory". A 512 square image took a 10Mb of memory and 10 hours to render. They talk about the need for a real hardware frame buffer - I feel like I'm reading a classical textbook...

Particle systems are still used in video games for special effects - fire, water splashes, rain etc... but they don't seem to have caught on as a central rendering paradigm.




Plant models faithful to botanical structure and development ( doi | acm | 1988 )
Phillippe de Reffye, Claude Edelin, Jean Françon, Marc Jaeger, Claude Puech




This paper overviews a general mechanism for modelling the topology of trees. It explicitly ignores the finer details of rendering, leaving those to the Maple paper. It presents a really quite interesting view of the different forms that trees take and how the different observed patterns can be modelled.

The growth of a tree is modelled using a set of buds. By iterating through time these create the leaves, nodes, and branches. It uses the observation that topological change only happens at buds, and other growth (eg girth of a branch) can be modelled by age.

This is a good, botanically based introduction to the different topologies of trees. The different branching patterns ("architectures") and Phyllotaxies given, represent a lot of different tree structures, and many subtleties (such as branch direction - orthotropic (absolute position, always pointing up) vs palgiotropic (relative and orthogonal to the parent branch)).

The technique used in the paper isn't as clean or insightful as L-systems. However admitting a time-based approach allows for features such as discrete events(trauma, pruning) and forces(gravity) to be modelled without too much deviation from the main algorithm (unlike L-Systems, where contorted rule sets of special cases are needed for each of these).

The general evaluation algorithm is :-

for each clock signal do
for each bud which is still alive do {order, age, dimension, position, etc. are known attributes of the bud}
if bud doesn't die then
if bud doesn't make a pause then
create intemode
{with position in space}
create apical bud
for each possible bud do
if ramification then create axillary buds
{with age, order and dimension}
endfor
endif
endif
endfor
endfor

Each section of the tree is then associated with some geometry (cylinder, cone etc..) before rendering out.



Visual models of plants interacting with their environment ( doi | pdf |1996 )
Radomír Měch, Przemyslaw Prusinkiewicz

This paper addresses a shortcoming in lots of the previous research; namely that the environment's didn't respond the the plants. The basic model is two concurrent systems run in parallel - the plant and the environment. The plant receives information from the environment, transports the information to the needed location and responds to this information by changing the form. The environment perceives the plants actions and simulates the environment (diffusion of chemicals or flow of light) and gives feedback tot he plant. The development of this paper was this two way communication between model and environment.

The particular evolution of the L-system to achieve this is named an Open L-system. Certain symbols in the system are communication points. The L-system is interpreted to these points and the requested information (given as parameters to the symbols) are transferred to the environment process, which returns a result. This loop is repeated several times when transforming the String L-system output to a graphical form.

A self-sensitive system is run by the environment process. By modelling split-branch points and end points of branches a spheres, a simple proximity check is used to determine branch creation and direction.

Floor creeping (Colonal) plants are evaluated in 2D using a given bitmap of light-intensities which the leaves then obscures. The model nicely shows the plant filling the brightest patches first, then when the leaves obscure too much light for any more growth, moving into the darker patches. Similarly a 3D water-density map is used to guide a root system - this causes the roots to compete for water and grow away from each other.

Another section of this paper discusses light sensitivity - again by using a fairly course voxel representation of the tree's volume and a number of directional light, the flux of each voxel can be calculated and fed back into the model. Leaves occlude the light flow. Growth can then be slowed and leaves not produced in areas of insufficient light. By sharing this voxel array between trees, two trees compete for the same light source (photo, above). These techniques gives some really good effects, with branches moving around each other searching for more light.

This is all implemented as a framework (which is mostly an easy way of increasing the author's funding ;)




trees
A screenshot from Fallout3, a game that uses SpeedTree

SpeedTree is a commercial product that allows artists to design trees and incorporate the results into 3D environments, usually video games. The offering is a suite of software, the most impressive part of which is SpeedTreeRT, which calculates physical effects and LOD in real time for video games. It is very widely used in the industry.

The challenging part of generating a forest of trees is being able to render them quickly and convincingly - SpeedTreeRT does this very well.

A CAD system provides the artists with a back end to specify what their trees will look like. The output from this can be used in real time or, of course, taken as a mesh and edited further in a 3D editor.

The cost is $8,500 per title released - I was really surprised that the price was this low, they must have a lot of customers to be able to sell it that cheaply. I guess tree creation technology was really figured out 25 years ago so this is an expected product, much more mature than the architecture/city equivalents.





The Algorithmic Beauty of Plants (pdf, 40mb | 1990)
Prusinkiewicz, Lindenmayer


This book describes various variations on the theme of L-Systems. Basically L-systems are very good at simulating cell induction in plants, but need many inelegant modifications to create realistic specimens. I've summarized it's contents in this blog post.




Meta notes:
  • Most of the work on L-systems dates back to the 80's - has nothing important & interesting been done since then?
  • The more I read the more I have one big idea that I want to implement, but I'm scared of writing what it is before I have some results, but I won't bother getting any results until i write it down.
  • Prusinkiewicz has a lot of work in this area, his pages are a good place to start
  • I didn't notice any authors who did work on procedural botany and other areas of procedural generation.
  • Apologies for the quality of some of the images, a lot of the old paper's were just scanned.
  • While I'm interested in form there was other cool work, light this one about realisting shading models for leaves.
  • Compared to the computer generated architecture corpus there was a much larger emphasis on biologically correct results:
Programs addressed to the biological audience are often limited to narrow groups of plants (for example, poplars [9] or trees in the pine family [21]), and present the results in a rudimentary graphical form. On the other hand, models addressed to the computer graphics audience use more advanced techniques for realistic image synthesis, but put little emphasis on the faithful reproduction of physiological mechanisms characteristic to specific plants. [Virtual models of plants interacting with their environment]

Our concern here is to produce images of plants and trees which should be faithful to their botanical nature and so to build a model which should include the known botanical laws which explain plants' growth and architecture. [Plant Models Faithful to Botanical Structure and Development]

We have not found much published information characterizing the impact of pruning on tree architecture. More data would be necessary to construct faithful models of particular tree species. [Synthetic Topiary]
  • But not entirely:
We concentrated on visual results more that botanical data [Approximate and Probabilistic Algorithms for Shading and Rendering Structured Particle Systems]

Altough rules based on intuitively obvious relationships such as the ones given in this paper may produce reasonable looking results, simulation that is true to nature requires rules based on empirical study[voxel space automata]
Some other round-ups in this area:
Papers I still mean to read




[edit: from sigg09, perhaps I'll write this up properly sometime]
Self-organizing tree models for image synthesis ( pdf | web | toappear: SIGGRAPH09 )
Wojciech Palubicki, Kipp Horel, Steven Longay, Adam Runions, Brendan Lane, Radomir Mech, and Przemyslaw Prusinkiewicz

This paper is a compilation of many of the above techniques. It offers some small incremental improvements over . I think the authors (if there are more than 4, it counts as a possy-of-authors) must have been surprised when it got accepted.

They use an existing L-system system, along with Moore's law since the last papers to produce some very pretty looking results. They tweak some of the resource-flow algorithms of earlier authors.

Lack of comment about leaves, rendering techniques (did they really use povray?)!

No comments:

Post a Comment