Computer Science 598d
Programming Assignment #3
BSP Construction
Due: April 9, 1998

For this assignment, you will write a program that constructs a BSP from a set of input polygons.  The resulting BSP must contain split(s) along the plane of each input polygon so that no leaf cell of the BSP contains any part of any input polygon in its interior (the input polygons should lie entirely on the boundary(s) of some leaf cell(s)).

Your goal is to develop an algorithm that automatically constructs BSPs with the fewest cells for a given set of input polygons.  To achieve this, you must be clever in your selection and ordering of splitting planes when constructing the BSPs.  Certainly, you will want to carefully order the splits along planes supporting input polygons, and
you may also want to introduce splits along other planes (i.e., ones not supporting any input polygon) as well.

This assignment will be performed in groups of two people (preferably pairing will be different than in any of the previous assignments).  At the completion of the assignment, we will all run our BSP 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) the number of cells in your constructed BSPs (mostly).  Some sample BREP files can be found on CS machines at /usr/graphics/ring/models/brep.

To aid you in this assignment, you can use the R3BspTree class in the R3Spaces package of RING.  I have written a simple program that you can use as a starting point to write your BSP program with RING.  To get started using it ...

This sample program first reads in a set of polygons (from a BREP file).  It then builds a BSP tree by iteratively splitting along the plane of each input polygon (in the order polygons appear in the input file).  Finally, the program prints some statistics regarding the size of the BSP and the time required to construct it, and possibly writes the (re-ordered) polygons to an output file. Your job is to re-write this program so that it chooses splits along input polygons in a better order, and possibly introduces other splits so that the BSP constructed has fewest cells, while your program uses as little computation time as possible.

At least one hour before class on April 9, each group should submit (via email):

Utility Programs

Using RING to Construct a BSP Tree

The R3BspTree<type> templated class is part of the R3Spaces package.  The important member functions for you to understand are the ones that split cells of the tree.  The first and most basic member function for constructing a BSP, splits a specific R3BspTreeCell by a specific R3Plane:

A second function recursively splits a subtree rooted at a specific R3BspTreeCell by a polygon.  All leaf cells descending from the specified R3BspTreeCell and intersected by the input polygon are split along the plane supporting the input polygon.  The member function is declared and implemented like this:
  Finally, a third function splits a BSP tree by a polygon (this is the function used in the sample version of rbsp).  All leaf cells intersected by the input polygon are split along the plane supporting the input polygon.   The member function is declared and implemented something like this: Following is a complete list of member functions for the R3BspTree templated class ...
 

R3BspTree<Type>:

Constructors:

R3BspTree<Type>(void);
    - constructs BSP containing one cell representing all of space

Tree Properties:

const RNBoolean IsEmpty(void) const;
    - returns whether BSP has no cells
const int NCells(void) const;
    - returns number of cells in BSP
      (THIS IS OUR METRIC)
const int NLeaves(void) const;
    - returns number of leaf cells in BSP
const int NInterior(void) const;
    - returns number of interior cells in BSP

Cell Properties:

const RNBoolean IsRoot(const R3BspTreeCell *cell) const;
    - returns whether cell is root
const RNBoolean IsLeaf(const R3BspTreeCell *cell) const;
    - returns whether cell is a leaf
const RNBoolean IsInterior(const R3BspTreeCell *cell) const;
    - returns whether cell is interior (not a leaf)
const RNBoolean IsAncestor(const R3BspTreeCell *cell, const R3BspTreeCell *decendent) const;
    - returns whether cell is an ancestor of `decendent'
const RNBoolean IsDecendent(const R3BspTreeCell *cell, const R3BspTreeCell *ancestor) const;
    - returns whether cell is a decendent of `ancestor'
const int NChildren(const R3BspTreeCell *cell) const;
    - returns number of child cells for cell
      (2 if interior, 0 if leaf)
const int NSiblings(const R3BspTreeCell *cell) const;
    - returns number of siblings for cell
      (0 if root, 1 otherwise)
const int NSiblingsBefore(const R3BspTreeCell *cell) const;
    - returns number of siblings to before cell in parent
      (0 if negative halfspace, 1 if positive)
const int NSiblingsAfter(const R3BspTreeCell *cell) const;
    - returns number of siblings to after cell in parent
      (1 if child for negative halfspace, 0 if child for positive halfspace)
const int NDecendents(const R3BspTreeCell *cell) const;
    - returns number of decendents under cell
const int NAncestors(const R3BspTreeCell *cell) const;
    - returns number of ancestors above cell
      (equals depth in tree)
const int NLeaves(const R3BspTreeCell *cell) const;
    - returns number of leaves under cell
const int Depth(const R3BspTreeCell *cell) const;
    - returns depth in tree
      (root is at depth 0)
const R3Plane& CellSplitPlane(const R3BspTreeCell *cell) const;
    - returns the split plane stored with an interior cell
Type& CellContents(R3BspTreeCell *cell) const;
    - returns a reference to the data stored with a cell
Type *CellData(R3BspTreeCell *cell) const;
    - returns a pointer to the data stored with a cell

Cell Access:

R3BspTreeCell *RootCell(void) const;
    - returns the root cell of the BSP
R3BspTreeCell *ParentCell(const R3BspTreeCell *cell) const;
    - returns the parent of a cell
R3BspTreeCell *SiblingCell(const R3BspTreeCell *cell, int k) const;
    - returns the sibling of a cell with index k in the parent's list
R3BspTreeCell *ChildCell(const R3BspTreeCell *cell, int k) const;
    - returns the kth child of a cell
      (0 is child for negative halfspace, 1 is child for positive halfspace)
R3BspTreeCell *LeastCommonAncestor(const R3BspTreeCell *cell1, const R3BspTreeCell *cell2) const;
    - returns the least common ancestor for two cells
      (returns NULL if not found)
R3BspTreeCell *FindCell(const Type& data, RNCompareFunction *compare = NULL, void *appl = NULL) const;
    - searches for a cell containing data match
      (returns NULL if not found)
R3BspTreeCell *FindCell(const R3Point& point) const;
    - searches for cell containing point
      (returns NULL if not found)
R3BspTreeCell *FindCell(R3BspTreeCell *cell, const R3Point& point) const;
    - executes a search rooted at cell for the cell containing a point
      (returns NULL if not found)

Manipulation:

void Collapse(void);
    - removes all cells in BSP tree
void CollapseCell(R3BspTreeCell *cell);
    - removes all decendents of cell
void Split(const R3Polygon& polygon);
    - splits all leaf cells intersecting polygon by the plane supporting polygon
void SplitCell(R3BspTreeCell *cell, const R3Polygon& polygon);
    - splits all decendent leaf cells intersecting polygon by the plane supporting polygon
void SplitCell(R3BspTreeCell *cell, const R3Plane& split);
    - splits a leaf cell by the plane and creates two children

Drawing:

void Outline(void) const;
    - Draws outline of all BSP cells
void OutlineCell(const R3BspTreeCell *cell) const;
    - Draws outline of one BSP cell

Iteration Macros:

R3_FOR_EACH_BSPTREE_LEAF_CELL(const R3BspTree& tree, R3BspTreeCell *&cell, RNIterator& iterator) { ... }
    - visits each leaf cell of BSP tree
R3_FOR_EACH_BSPTREE_LEAF_CELL_INTERSECTING_SHAPE(const R3BspTree& tree, R3BspTreeCell *&cell, R3Shape& shape, RNIterator& iterator) { ... }
    - visits each leaf cell that intersects a shape
R3_FOR_EACH_BSPTREE_CELL_CHILD(const R3BspTree& tree, const R3BspTreeCell *cell, R3BspTreeCell *&child, RNIterator& iterator) { ... }
    - visits each child of cell in BSP tree
 

BREP File Format

The BREP format is very simple. The file is a list of convex polygons, where each polygon is a list of vertices. The header indicates whether a particular type of information is included. "Texture" means there are may be texture coordinates while "NoTexture" means there are none, and "MaybeTexture" indicates that the  presence of texture coordinates is on a per polygon basis. "Colors" means that each polygon has a rgb color specified and "NoColors" means no polygons has rgb information. "Normals" mean each vertex has its own normal where as "NoNormals" means that no vertices have normals. "MaybeNormals" makes this on a per polygon basis.  Here is a BNF description: The code to read/write BREP files is in ring/pkgs/R3Shapes/R3Io.C.
Here are some example files, all of which describe cubes with different attributes:

Related Links: