Object Instancing

To model branching structures, often tree-like data structures are used. We saw this already in some procedural methods in Chap. 4. In the case of L-systems, the tree is represented as text in linear form. Iterated function systems can, as demonstrated above, likewise be represented as trees that encode the transfor­mation rules for points.

Figure 5.16

Object instancing of fractal objects: (a) tree structure; (b) resulting approximation of a Sierpinski-triangle; (c) object instancing hierarchy; (d) object instancing hierarchy with cycles

 

(a) (b)

 

Object InstancingObject InstancingObject Instancing

Since these data structures most likely occupy a lot of space, depending upon the complexity of the objects, it is meaningful to introduce compression tech­niques. One option is to represent the produced geometrical primitives canon­ically and to place them in a tree using relative positioning data. In this case, subtrees, which produce the same objects in different places, can be represented by just one subtree, whose root nodes may have several fathers. The tree be­comes in this case a directed acyclic graph (DAG). The process is called object

instancing, and was used for the first time by Ivan Sutherland in his system Section 5.12

Подпись: OBJECT INSTANCINGSketchpad” [216].

A subset of L-systems, as well as the iterated function systems, can efficiently be represented by such graphs [166]. Kay and Kajiya [108] applied this tech­nology for the first time to fractal objects. Here, cycles develop in the directed graphs, and the object can be described in arbitrary detail.

Hart and DeFanti [84] describe efficient methods for the modeling and repre­sentation of cyclic object instancing hierarchies. Figure 5.16a shows the tree hierarchy for modeling an approximation of the Sierpinski triangle from part (b). The leaves of the tree are the geometric primitives; the internal nodes rep­resent relative transformations and combine the produced geometry.

Object Instancing Object Instancing

In Fig. 5.16c the graph was converted into a directed acyclic graph that also represents the object. If cycles in the graph are permitted (Fig. 5.16d), then the fractal object can be represented arbitrarily exactly and a Sierpinski triangle is yielded. Hart [83] provides a more detailed description of the graph in Fig.

Подпись: // node in the middleobject top

{ merge: up, left, right

}

Likewise in [83] the transformation of a subset of L-systems and of RIFSs into the cyclic graphs of the object instancing paradigm is described. The conver­sion of the RIFS is executed via the transformation of each function into a

canonical object; the RIFS graph is transferred directly into the cyclic graph of the object hierarchy.

The already-mentioned possibility of converting L-systems into RIFSs (see [166]) allows us also to convert them into the object instancing paradigm. Hart sketches furthermore a direct conversion method for strongly recursive branch­ing structures. However, a general transformation method seems not to exist.

Instancing is possible within a branching structure as well as in a compilation of plants. Thus in Chap. 8 instancing is applied for the modeling of plant com­munities. Instead of defining each plant individually in a lawn, a small number of prototypes is stored and copied as needed. This permits a strong reduction of the needed disk space, and at the same time makes the scenes easier to handle. A substantial difference to the method described here is the approximate char­acter of instancing. A number of similar objects are represented visually by only one prototype. “Approximate instancing” can be used for natural objects on many levels, without substantially affecting the visual appearance of the results.

Figure 5.17

Object InstancingTree model generated using a cyclic CSG-graph (Courtesy of M. Gervautz and C. Traxler)