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:

  \