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):

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):

The CS598d Scene Graph Optimization Metric


RING Software Library

To aid you in this assignment, you can use RING, a software library written at Bell Labs for Real-time 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 ...

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 fill-in for this assignment.  Finally, it prints some statistics regarding the improvement of the metric.  For instance, the following is a sample execution ... Your job is to fill-in 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: