PL-systems are parallel rewriting systems, operating on strings of symbols. Productions specify how symbols are replaced in the current string. In this way pL-systems produce a code that describes how geometric primitives are assembled to approximate a natural scene with sufficient detail. This is done before rendering. The code is then interpreted to obtain a geometric representation of the scene, which is necessary for the renderer. Thereby a huge number of linear transformations are applied to primitives, which puts them to the proper shape and position. This process is known as Turtle Graphics. The name comes from the programming language LOGO, dedicated for kids who were delighted to move a virtual turtle with a pen in its yap over the screen by simple commands to obtain simple graphics. This concept of incremental drawing (it works much like a plotter) was later extended to three dimension. You can imagine a turtle that floats through 3D space, equipped with a sack of geometric primitives and a long list of weird instructions that tells it how to attach one primitive to the other.

The approach described above has some major drawbacks, especially for very complex scenes. First the pL-system has to be processed to obtain the huge code that describes the construction of the scene. This is time consuming and demands pretty much memory. However this memory consumption is almost neglectible compared to that necessary for the representation of the scene. Each single primitive of the scene model is stored in memory regardless if it can be seen in the rendered image or not.

This problems are solved by a technique known as Object Instancing. Here repetitive parts of a scene are only stored once and instanced several times during rendering, whereby the proper transformation is applied to it, mapping it from its initial state to the final shape and position in the scene. Consider the model of a car. With object instancing all four tires are represented by one and the same assembly of primitives, which are transformed to their correct position during rendering. This approach has a decisive advantage. Only those instances are considered that contribute to the final image. The side view of the car shows only two of its tires, the top view may cover all of them. Thus the model of the tire is only instanced two times for the side view and never for the top view. This saves both memory and time. Now consider a natural scene consisting of a couple of trees with lot of leaves. Only a small percentage of the leaves can be seen from a particular viewing point. To be efficient it is crucial to instance only those that can be seen.

In this project we developed an object instancing technique for pL-systems. The idea was to avoid the process of interpreting and building up the whole scene. This is accomplished by using a special form of Directed Cyclic Graphs (DCG) to represent pL-systems. This novel data structure can directly be used for rendering. The so transformed pL-system generates directly an image instead of a code describing the scene. During rendering the graph is traversed and visibility tests are applied to check which parts of the scene contribute to the final image from the chosen view point. These test are pretty fast and efficient. There are a plenty of different traversal paths through the graph, which represent different parts of the scene. Those paths not relevant for the final image are not traversed, so that only visible objects are instanced.

DCGs can be used for multiple rendering techniques. Our main purpose was to use them for ray tracing, yielding photo realistic images (if you properly adjust all the parameters ;-). As underlying object representation we used Constructive Solid Geometry (CSG) were the volumes of so called primitive objects are represented procedurally. Three binary operators can be used to combine the volumes of objects, subtract the volume of one object from the other (to simulate drilling, carving, punching and so on) or keep only the intersecting area of both volumes. In this way complex scenes can be described by binary expression using brackets to obtain a hierarchy. This concept was used for DCGs so that CSG operators and primitives appear as nodes within this data structure. Therefore we introduced a special type of pL-systems that generate CSG expressions and hence are called CSG-pL-systems. The DCG for such a system is accurately named CSG-DCG. In CSG-pL-systems we distinguish between generating productions associated with a grammar symbol that generates a part of the scene and terminating productions that finally replaces all grammar symbols by CSG expressions.  

Ray tracing is done by traversing the DCG until the rays are send to a geometric primitive object. Then the appropriate intersection algorithm is used to obtain the intersection points with the primitive. Beside primitives and CSG operators the DCGs consists of three special types of nodes. Selection Nodes represent grammar symbols and join the tree representation of their production as successors. They direct rays to the appropriate production, which corresponds to the application of that productions. The selection depends on parameters. Parameters are modified by Calculation Nodes. Finally we need Transformation Nodes to map rays iteratively, which is geometrically equivalent with transforming of primitives.        

It is not enough that DCGs are memory safe but they have to be efficient for rendering, too. Thus a major part of this research project was to adapt conventional optimization techniques for them. We used a hierarchy of bounding boxes to efficiently test if they are hit by a ray. The recursive traversal is immediately terminated if the ray misses a bounding box, which encloses a part of the scene. An additional optimization was achieved by a regular 3D grid. The scene is thereby divided in coherent regions, whereby those crossed by a ray can be found rapidly. All other parts of the scene can be ignored.

Bending, twisting and tapering are the three major Non Linear Transformations (NLT) used in computer graphics. We incorporated these three NLTs as additional modeling feature. They are especially suited for plants. Plant structures are naturally non linear and can easily described by NLTs. Take for example the shape of a twig. It is usually a bent, tapered and slightly twisted cylinder. Twisting is also very efficient to model climbing plants. Beside that non linear fractals can be visualized with NTLs. More details of this project part can be found on Peter Wonkas page. 

Ray tracing emphasizes on realistic image synthesis and hence produces an image quality that is not desired in the modeling phase. Since it is important to have a preview opportunity during modeling, we used DCGs for real time, or at least, fast rendering. We used a standard interactive 3D graphics library, called OpenInventor™, which made the implementation easy. Single objects now can be interactively previewed. The modeler can play around with them and immediately sees the result of any modifications. The compact form of DCGs and interactive rendering facilities invite to apply them for distributed virtual environments. See the RecursiveIV page for more details on the use of DCGs in this exciting field.

One drawback of pL-systems is the modeling task itself, which demands great experience. They generate very complex objects out of a tinny data base, a property called data base amplification. It addresses the problem of sensitivity, small changes of the data base can drastically alter the result of the iterative process. Especially adjusting geometric aspects proves to be a hard and tedious task. To solve this problem we used genetic algorithms with the expected success. It was not our intention to generate different species, but to improve the visual quality of a particular species. Thus only some ratios between plant parts and branching angles are subject to artificial evolution.

DCGs are a very powerful technique for modeling and realistic rendering of very complex scenes, like landscapes. Two important concepts of CSG are thereby exploited, a hierarchical scene description and object instancing. The major aspect of our method is the compact and consistent representation of all repetitive parts of the scene by DCGs. Non repetitive parts are represented by CSG-DAGs, which of course can be combined with DCGs. Since they are a memory safe data structure, the complexity of the scene and the approximation accuracy of objects are not restricted.

Furthermore mutual influences of their visual appearance and interdependency of their geometry are considered. Landscapes for example can be created by combining two CSG-pL-systems. One system creates a designed terrain from reading a height field and the other one different individuals of a plant species. The spread of the fauna thereby is directly regulated by the terrain to fulfill natural constraints. Plants can only grow on locations between sea level and timber line that are not too steep, for example.

Levels of detail for plants can directly be incorporated to accelerate rendering. The approximation accuracy depends on the distance from the eye point, which is calculated by the DCGs and used to select the appropriate level of detail. Besides plants CSG-pL-systems can generate other objects with a repetitive structure as well. We also presented DCGs for other classes of objects. Approximations of linear fractals can be obtained easily, too. The systems for sea shells and skyscrapers demonstrate the application of the subtraction operator within a feedback system, an approach only possible with CSG-DCGs. For more details we refer to our publications. Results can be viewed and downloaded in the gallery.