Next: Colour and the Up: Hierarchical Models and Previous: Hierarchical Transformations

# Hierarchical Data Structures

• Don't want to write a program for each scene...
• Instead, develop a data structure and traverse it.
• Use an external data format to describe model hierarchies.
• Process many different scenes with the same program.
• DAG data structure: lots of variations on the example given here.
• Consider the following DAG:

\

• Use a linked list to allow an arbitrary number of links from each node.

\

• Two node types: Data and Link.
• Data: Transformation, Model Geometry.
• Link: First child pointer, sibling pointer.
• We walk through the hierarchy with a preorder traversal...
• If multi-parented nodes uncommon, treat as special case...
• Combine Link and Data nodes.

\

• One node type.
• Contains transformation, model geometry, first child pointer, sibling pointer.
• Define an ``instance'' geometry type which is a link elsewhere in the tree.
• Traversal pseudocode:
```    Traverse (Node* ptr) {
Node *child, *instance;
PushMatrix();
MultMatrix(ptr->transform);

if (ptr->geom_type == INSTANCE_GEOM) {
instance = (Node *) ptr->geom_data;
Traverse(instance);
} else if (ptr->geom_type == PRIMITIVE_GEOM) {
DrawPrimitive(ptr->geom_type, ptr->geom_data);
}

child = ptr->first_child;
while (child != NULL) {
Traverse(child);
child = child->sibling;
}
PopMatrix();
}```

A3/A4 House Code

```gr_transform : scene

gr_transform : house
gr_polyhedron : prism {...} {...}
gr_instance :house roof :prism
gr_translate :house:roof {0 0 1}
gr_cube :house frame

gr_instance :scene farmhouse :house
gr_surfaceproperty :scene:farmhouse farmhouse_green
gr_instance :scene barn :house
gr_surfaceproperty :scene:barn barn_red
gr_translate :scene:barn {-2 0 3}
gr_rotate :scene:barn rotate "y" 30
gr_scale :scene:barn 2
gr_instance :scene doghouse :house
gr_surfaceproperty :scene:barn doghouse_blue
gr_translate :scene:barn {-1.5 0 -0.2}
gr_rotate :scene:barn rotate "y" -15
gr_scale :scene:barn 0.2```
• House example:

\

• Rendered House:

\

CS488/688: Introduction to Interactive Computer Graphics
University of Waterloo
Computer Graphics Lab

cs488@cgl.uwaterloo.ca