Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations

This paper presents a new method to compute constructive solid geometry (CSG) tree representations of an object whose faces consist of planar and non-planar surfaces. The algorithm described accepts as input a valid boundary representation of an object consisting of piecewise implicit surfaces, and computes a halfspace CSG representation of the object. A class of objects that are describable by the surfaces bounding them are valid input for the algorithm of this work, although methods currently exist to compute the additional information necessary to process non-describable quadric objects as well. This work builds on and complements the other work in this area, in which dominating halfspaces are used to simplify the b-rep to CSG conversion process. We include factored faces to enable the factorization of dominating halfspaces throughout the algorithm. Thus, an efficient disjoint decomposition of the solid is obtained as a matter of course in the algorithm, so that CSG minimization is generally not necessary.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 (e.g. CAT scanning, laser range finding). The recovery of a valid 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. The CSG tree also provides a relatively neutral representation that can enhance form feature recognition and translation.