Three-dimensional binary space partitioning tree and constructive solid geometry tree construction from algebraic boundary representations

The purpose of this thesis is to present a method to compute binary space partitioning (BSP) tree and constructive solid geometry (CSG) tree representations of an object whose faces consist of planar and non-planar surfaces. A class of objects that are describable by the surfaces bounding them are valid input for the algorithm of this thesis, although methods currently exist to compute the additional information necessary to process non-describable quadric objects [51, 52]. This work is motivated by reverse engineering of mechanical parts, in which a model of a part is recovered from information obtained by some sort of sensing technique (eg. CAT scanning, laser rangefinding). The recovery of a valid BSP-tree or CSG-tree description of an object from a boundary representation of it can provide useful information to an engineer in the area of reverse engineering and in other areas related to solid modeling as well. This thesis presents the details of the BB-family of algorithms to convert a boundary representation of a solid object to a BSP representation, a Halfspace CSG representation, and a Bounded Solid CSG representation of the object. In particular, the algorithms accept as input a valid boundary representation of an object consisting of piecewise implicit surfaces. A binary space partitioning tree representing the object is computed first (the BB algorithm), and is converted to a halfspace CSG representation of the object (the BBHC algorithm). In certain cases it is also possible to convert the BSP tree representation into a bounded solid CSG representation as well (the BBC algorithm).