Computer Science 598d
Programming Assignment #2
Scene Graph Optimization
Due: March 26, 1998
For this assignment, you will write a program that reads a VRML scene graph
from a file, and then writes an optimized version of the scene graph to
a new file.
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
To judge the quality of your optimized scene graphs, we will use the ``CS598d
Scene Graph Optimization Metric,'' M, which combines several
factors, including (G) the global ``goodness'' of the scene
graph (e.g, its conciseness), (I) the estimated cost of ray
intersection for the scene graph (averaged over many sample rays), and
(R) the estimated cost of rendering the scene graph (averaged
over many sample viewpoints).
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 axisaligned 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
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
To aid you in this assignment, you can use RING, a software library written
at Bell Labs for Realtime Interactive Networked Graphics.
All the documentation and source code for RING can be found in /usr/graphics/ring
on the CS machines, and at ~cs598d/ring on the CIT machines. In particular,
you can look at the RING ``reference manual'' (on CS machines at /usr/graphics/ring/docs/index.html,
and on CIT machines at ~cs598d/ring/docs/index.html)
to find descriptions for the C++ classes and example programs available
in RING. The scene graph C++ classes are in the R3Nodes
package.
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>]
This sample program first builds a RING scene graph (similar to a VRML
scene graph, but different) by parsing an input file (which can be in UNIGRAFIX,
VRML 1.0, or VRML 2.0 formats). Then, it calls OptimizeSceneGraph
(currently a dummy function), which you must fillin for this assignment.
Finally, it prints some statistics regarding the improvement of the metric.
For instance, the following is a sample execution ...
> 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%
Your job is to fillin the details of the OptimizeSceneGraph function (in
opt.C). You should aim to achieve a large reduction in the scene
graph metric, while using as little computation time as possible.
When you are done, please email me the location of your version of opt.C
and any other source code files you create.
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: