2
1 introduction
cyclic csg graphs are a memory safe representation of recursive objects, which are defined by
parallel rewriting systems. they are an extention to conventional csg trees and thus can directly be
used for ray tracing. csg graphs emerge from csg-pl-systems, which are an adaption of the well
known parametric lindenmayer-systems (briefly pl-systems). the main difference between pl-
systems, which are fully described in [lind90], and csg-pl-systems are their formal languages.
while the derived strings of the first are command sequences for a virtual construction tool called
turtle, the derived strings of the last are a subset of the infinite set of all valid csg expressions.
instead of running a derivation process and building up a large csg tree out of the resulting string,
the rules of the grammar are directly transformed into a cyclic csg-graph, which is traversed by the
rays to visualize the object.
for that purpose, we extended the csg concept to three new nodes. selection nodes, briefly s-
nodes, join all the rules for one grammar symbol and are associated with a selection function. this
function controls the flow by selecting a proper rule and passing the rays to it. the rules themselves
are translated into csg trees and attached as successors to the s-node. for each occurrence of a
grammar symbol in the right hand side of a rule an edge is spanned to the corresponding s-node.
this yields to a graph with cycles, wherby s-nodes are the only targets of cyclic edges.
like with conventional csg trees, the rays are mapped from the world coordinate frame into the
object coordinate frame, because this is much more efficient than mapping the primitive objects. in
csg graphs this is done by special nodes, called transformation nodes or briefly t-nodes. they can
be seen as unary operators and thus have only one successor. the same is true for calculation
nodes, briefly c-nodes, which evaluate a finite set of arithmetic expressions to modify global
parameters. their values effect flow control, i.e. the selection of rules, and transformations. all
other nodes, i.e. csg operators and primitive objects are handled as in csg trees. the csg graphs
introduced so far are as compact as the describing data set. an explicit representation of the scene
(like with csg trees) is avoided and therefore no restrictions of the complexity of the scene or the
approximation accuracy of objects must be considerated. a related method was introduced in
[kaji83] for the ray tracing of fractal terrains and in [hart91] for the ray tracing of objects
defined by iterated function systems (ifs). fig.1.1a shows a csg-pl-system, that generates a
simple sympodial branching structure and fig.1.1b the corresponding csg graph. a full description
of this approach we gave in [gerv95].
initialization of the parameters
{cnt = 8;// order of the branching structure
trunk = 2,// number of t runk segments (cycl es of rule with index 2)
ftr = 0.96;// scaling factor for trunk segments
gamma = -72.0;// divergence angle
alpha1= -60.0;// branching angles
alpha2 = 20.0;
fbr1 = 0.73;// scaling factors for left and right branches
fbr2 = 0.67;
noleaves = 3;// if cnt is less than noleaves the limbs bear leaves
segments = 2;// number of segments for a limb with leaves
fxsg = 1/7;// scaling factors for segment cylinders
fysg = 1/7;
dsg = 1/segments;// height of a segment cylinder
flv = 0.6;// scaling factor for leaves
} tr// the start node
评论