The Elements of Network Communication


Comparison with L-Systems

L-systems consist of rewrite rules and have been widely used for plant modeling and simulation. Perhaps surprisingly, there is a direct mapping between the string expansions of a rule system and the visual representation of a plant. An example, using a bracketed L-system, will give an idea of how this works.

The L-system contains one start string F and rewrite rule:

     F --> F [-F] F [+F] F

The start symbol represents the initial plant form; in this case, F is a single plant limb. The rewrite rule specifies how the symbol on the left of the > should be replaced or expanded to create the longer sequence of symbols on the right of the >. The rewrite rule replaces F with the sequence F[-F]F[+F].

The visual characterization is obtained by thinking of each F in the sequence as a limb of the plant. The bracketed notation is viewed as a branch-creation operator; the - is a rotation to the right for the branch, and the + is a left rotation. Consequently, the rewrite of F to F[-F]F[+F] can be seen as the plant expansion in Figure 28-6.

Figure 28-6. First rewrite of F


The rewrite rule can be applied again to each F symbol in the F[-F]F[+F]sequence, producing a longer sequence. Repeated application of the rewrite rule creates ever larger sequences with more complex plant-like shapes as in Figure 28-7.

Perhaps the richest L-system language is cpfg, available from http://www.cpsc.ucalgary.ca/Research/bmv/. It includes a full range of programming constructs, data structures, library functions, and various extensions, such as parameterized L-system symbols and sub-L-systems.

Two good introductions to L-Systems, both available online, are "An Introduction to Lindenmayer Systems" by Gabriela Ochoa (http://www.cogs.susx.ac.uk/lab/nlp/gazdar/teach/atc/1998/web/ochoa/) and "Simulating Plant Growth" by Marco Grubert in ACM Crossroads Student Magazine (http://www.acm.org/crossroads/xrds8-2/plantsim.html).

Figure 28-7. A sequence of rewrites


Java 3D and L-Systems

Java 3D was used by René Gressly to implement L-systems for growing bushes, trees, and flowers in a landscape. The user chooses where to place plants and then walks around the scene as the plants grow (http://www.hta-bi.bfh.ch/~swc/DemoJ3D/VirtualPlants/).

Chris Buckalew implemented a Java 3D L-Systems engine that uses recursion to parse the start string and replace string elements. It's part of a lab exercise in his CSC 474 Computer Graphics course (http://www.csc.calpoly.edu/~buckalew/474Lab7-W02.html).

Scott Teresi has written code that reads a 2D L-System and renders it in 3D (http://teresi.us/html/main/programming.html)

So Why Not Use L-Systems?

The truth is that originally I did use L-systems. A student and I developed code along the lines of Chris Buckalew's example. Unfortunately, the heavy use of recursion meant that only one or two trees of perhaps 10 or so levels could be generated before Java required a major memory extension.

The real problem is with the L-system formalism, which has difficulty representing incremental change using L-system rewrite rules. As Figure 28-7 indicates, each expansion creates a more complex tree, but it is hard to see how the fancier tree has grown out of the simpler one. What part of the current tree is new wood, and which is old wood that has grown a bit?

An L-system sees growth as a new tree completely replacing the old one. That doesn't matter when the tree is a mathematical abstraction but has consequences when implementing growth in Java 3D. The natural approach, and the most disastrous from an efficiency point of view, is to discard the current tree at the start of a rewrite and generate a new one matching the new string expansion.

The rules notation used here, as typified by the rules in applyRules( ), are phrased in terms of incremental change to existing limbs. New limbs can be added, but only by explicitly spawning children. This has the practical benefit that thousands of limbs can be created before the application needs additional heap space.

Another drawback of the Lindenmayer notation is its lack of tree nomenclature. For instance, it's impossible to talk about the parent of a node, its children, its level in the tree, and so on. To be fair, some of these capabilities can be programmed by using parameterized L-system rules, and basic L-systems have no notion of global time or the age of individual limbs. This can be remedied with additional parameters in rules.

L-system rules tend to be embedded in procedural languages, so it's difficult to create new plant node types (or classes) with their own data, operators, and behavior. This presents no problem to Java of course; I could start by subclassing TReeLimb.



Killer Game Programming in Java
Killer Game Programming in Java
ISBN: 0596007302
EAN: 2147483647
Year: 2006
Pages: 340

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net