Your program should reconstruct the scene graph hierarchy to allow faster rendering, more efficient intersection testing, and more effective view frustum culling.  For this assignment, we will assume that the model is static (i.e., no animating objects).  We will also assume that it is not important to preserve any functional hierarchy in the scene graph.  You should consider the following optimizations (in order of importance):

• Reconstructing the bounding volume hierarchy
• Splitting/merging leaf nodes (e.g., IndexedFaceSets)
• Removing unnecessary transformation nodes
• Removing unnecessary grouping nodes
• Removing unnecessary material nodes
• Removing unnecessary light nodes

This assignment will be performed in groups of two people (preferably pairing will be different than in the last assignment).  At the completion of the assignment, we will all run our scene graph optimization programs on a standardized suite of input files (provided by you and me) and tally the results to see which programs perform best.  Each pair of students will submit one file that they would like to be part of the standard suite of input files, and I will add some of my own.  You will be judged by the 1) the running time of your program, and 2) your improvement to the scene graph optimization metric (mostly).  Some sample VRML 1.0 files can be found on CS machines at /usr/graphics/ring/models/vrml1, and on CIT machines at ~cs598d/ring/models/vrml1.  In particular, we will consider (at least) the
city*.wrl files for evaluation of your algorithms.

Each group should submit (via email):

• A pointer to your source code (e.g., opt.C and other files)
• A one/two paragraph description of your approach
• A summary of your results for the class test scenes

For each test scene, provide an ascii text line of the form:<filename> <optimization time> <percentage reduction in scene graph metric>
e.g., city16a.wrl 0.0000 0.0000
      city16b.wrl 0.0000 0.0000
      etc.

The CS598d Scene Graph Optimization Metric

M = G + I + R , where ...
 
• G = N_G
• N_G = total number of nodes in the scene graph
• I = N_I + 2B_I + 4T_I + 8F_I
• N_I = average number of nodes visited during ray intersection
• B_I = average number of node bounding volumes tested during ray intersection
• T_I = average number of transformation nodes traversed during ray intersection
• F_I = average number of facets tested during ray intersection
• R = N_R + 2B_R + 4T_R + 8F_R
• N_R = average number of nodes visited during rendering
• B_R = average number of node bounding volumes tested during rendering
• T_R = average number of transformation nodes traversed during rendering
• F_R = average number of facets rendered

For the purposes of this metric, you should assume:

• The bounding volume of each node is the smallest axis-aligned box enclosing the geometry of all its decendents.
• The ray intersection function for each node executes as follows ...
if leaf node
return closest intersection (or none)
else
check for intersection with the bounding box of each child
for each bounding box intersection (sorted front to back)
    compute closest intersection with child's contents (or none)
    if (closer than any other bounding box) break;
return closest intersection (or none)

• The rendering function for each node roughly executes as follows ...
if leaf node
render facets
else
for each child node
if (view frustum intersects bounding box)
if (view frustum contains bounding box)
render child node without any more view frustum checks
else
render child node
 

RING Software Library

I have written a simple program that you can use as a starting point to write your scene graph optimizer with RING.  To get started using it ...

cd <your directory>
cp -r /usr/graphics/ring/apps/ropt .
cd ropt
make
ropt <input model filename> [-o <output model filename>]

-> ropt city16a.wrl
Optimization time = 0.0001
Start scene graph metric = 705.8594
End scene graph metric = 705.8594
Reduction in scene graph metric = 0.0000
Reduction in scene graph metric = 0.0000%

Source code for evaluation of the CS598d metric appears in metric.C in the ropt directory.  The metric averages intersection computations over several rays, and it averages rendering computations over several camera viewpoints.  The ray and camera samples can be generated in two ways.  First, they can be created randomly by using the `-nr <number of random rays>' and `-nc <number of random cameras>' program arguments in ropt.  Second, ray and camera samples can be read from files using the `-ir <input ray file>' and `-ic <input camera file>' program arguments in ropt.  Also, ray and camera samples can be written to ray and camera files (for use in subsequent executions) using the `-or <output ray file>' and `-oc <output camera file>' program arguments in ropt, respectively.  A ray file contains a sequence of ray entries of the form: x y z dx dy dz, where (x, y, z) is the origin of the ray, and (dx, dy, dz) is the direction vector of the ray.  A camera file contains a sequence of camera entries of the form: x y z tx ty tz ux uy uz, where (x, y, z) is the viewpoint of the camera, (tx, ty, tz) is the direction the camera is looking along, and (ux, uy, uz) is a vector pointing up from the camera perspective.  The field of view is PI/3 for all cameras sampled, and the cameras have no front- and back- clipping planes.
 

Related Links:

• VRML Repository
• SGI's VRML Site
• The Annotated VRML97 Reference Manual