Project 2: Sphere Hierarchies & Splatting

Assigned: Tuesday, October 9

Due: Thursday, October 25 before 5:00pm

Overview

In this project, we'll explore the implementation of a system like QSplat. The goal of this project is to gain practical experience with implementing hierarchical spatial data structures, and to apply those hierarchies for a specific application (e.g., splat rendering).

Requirements

Your program should demonstrate the following required functionality:

Hierarchy Construction
Your program will input a triangulated 3D surface and construct a hierarchical partition of the vertex set using recursive bisection. You should implement 2 different strategies for hierarchy construction:

• Axis-Aligned Partition — Start with the axis-aligned bounding box of the entire object. Split the box in two along its longest axis. (You'll probably get the best results if you split at the median point, but you can split at the mean point if you prefer.) Recursively split each sub-box in the same manner. Stop splitting when every box has only one vertex in it.
  
  
• Oriented Partition — Start with the entire vertex set. Compute the direction of maximum variance of the point set (see the discussion below). Split the point set with the plane passing through the mean of all the vertices with this direction as its normal. Continue splitting until each cell contains exactly one vertex.

QSplat-style Sphere Splatting
Starting with the hierarchy just constructed, you can fit a bounding sphere and normal bounding cone to each node in the hierarchy. Implement the code necessary to draw this sphere hierarchy using sphere splats. (You may choose any or all of the splat primitives outlined in the QSplat paper.)

View-Dependent Traversal
Implement view-dependent traversal of the tree for rendering. You're free to choose the exact VDR heuristics that you use, but a very simple "projected screen size of sphere" heuristic is perfectly acceptable.

Sample Code & Data

You're asked to implement recursive oriented partition of a 3D point set. You can do this using principal component analysis, as mentioned in the Hoppe et al surface reconstruction paper. To briefly recap:

• Compute the mean of all the vertices vm
• For each vertex vi, compute di = (vi - vm)
• Sum the outer products of di over all points
• Extract the eigenvalues/vectors of this matrix
• The eigenvector corresponding to the largest eigenvalue is the direction of maximum variance.

    #include <gfx/mat3.h>

    Mat3 CV;  // Compute the covariance matrix

    // And extract the eigenvalues/eigenvectors
    Vec3 evals, evecs[3];
    if( !eigen(CV, evals, evecs) )
	... couldn't extract eigenvectors
	... fall back to some reasonable alternative (eg., axis-aligned split)
    else
	... evecs[0] is the direction to split in

Here are some surface models for you to experiment with:

Handin

You must hand in all the following things:

1. All source code that you have written.
2. An executable that works correctly on the machines in 1265 DCL.
3. A README.txt file which provides the details of how your implementation works.
4. Any other file necessary to make your software compile.

To actually hand in your project:

1. Package all your files in a single archive (either .zip or .tar.gz are acceptable).
2. E-mail this archive to me at garland+handin@cs.uiuc.edu prior to the handin deadline. If your project is too large for e-mail, you can contact to make other handin arrangements.