An important aspect of any rapid prototyping system is the speed with
which it can acquire a complete model from a set of incomplete views
of the model acquired from a sensor. As with segmentation all but the
simplest objects will require that each view be merged with the
others, often a difficult and time-consuming preocess. There are a
variety of methods used to merge multiple views of an object together,
including methods based on Constructive Solid Geometry, volumetric
approaches, and [add one more here]. These are all highly dependent
on the object representation being used. The desiderata for a
representation are that it be effective at modeling the segmented data
of each view and be able to *quickly* merge the different views into a
single, accurate representation of the data. Such a representation is
the Binary Space Partitioning Tree, or BSPT.

A BSPT is a method by which n dimensional space is partitioned by n-1 dimensional entities called hyperplanes. For example, 2D space would be partitioned by 1D entities, i.e. lines, and 3D space would be partitioned by 2D entities, i.e. planes. Once a space has been partitioned by a hyperplane, it is represented by two n dimensional spaces, one on each side of the partitioning hyperplane.

An effective way to understand the use of a BSPT is to follow a simple example of their construction, which can be done by a 2D example. Suppose one wishes to generate the BSPT representation of a triangle (See the figure below), beginning with an empty BSPT. To process starts by choosing a hyperplane to partition the space, say L1. If a normal is associated with L1, this partitions the space into two half-spaces, space in front of L1 and space behind it. The two half-spaces are then recursively partitioned until the homogenaity constraint is met. Note that it is only necessary to partition a half-space if it is not homogeneous. In this case, the space behind L1 is not homogeneous, so we will contine to partition it. The remaining figures show a continuation of this process, until the model is completely partitioned. By labeling the regions paritioned by the complete tree, it can be seen that each region is described by a leaf in the tree, while each internal node describes both an edge of the model and a hyperplane.

An analogous procedure may be followed to build a BSPT of a 3D space, using planes as the partitioning hyperplanes instead of lines as in the 2D example.

The BSPT has unique advantages as an intermediate representation for
the different views. Its tree structure allows very efficient
algorithms to be developed, it is compact, and it is numerically
robust. The BSPT representation has proven its utility in 3D modeling
, in graphics, and in image processing as a tool for
representation and compression. Of primary importance for this
work is that there exist very fast and robust algorithms for merging
models represented as BSPTs. If, after segmentation of each laser
image, we build a BSPT representing each image, we may then use
boolean operations to get the intersection of these images. This
intersection will be those parts in the model that *all* the views,
together, can determine.