SEPARATION FOR BOUNDARY TO CSG CONVERSION

important applications of b-rep --> CSG conversion arise in solid modeling, image processing, and elsewhere. In addition, the problem is of considerable theoretical interest. One of the most difficult steps in performing b-rep --> CSG conversion for a curved solid object consists of determining a set of half-spaces that is sufficient for a CSG representation of the solid. This usually requires the construction of additional half-spaces whose boundaries do not contribute to the boundary of the solid. Such half-spaces are called separating half-spaces because their purpose is to separate certain subsets inside the solid from those outside of the solid. Construction of separating half-spaces is specific to a particular geometric domain, but several generic approaches are possible. We use the information present in the boundary of the solid being converted to study the constraints on the degree of separating half-spaces, and show that a sufficient set of linear separating half-spaces exists for any solid whose boundary contains only planar edges. A complete construction is given for solids whose faces lie in convex surfaces. Separation for more general solids, whose b-rep includes other surfaces and nonplanar edges, is also discussed, but this general problem remains poorly understood. We apply the boundary-based separation to solids bounded by general quadric surfaces. Specifically, we prove that a sufficient set of linear separating half-spaces exists for any such solid and consider the required constructions in several common situations. The presented results allowed a successful implementation of an experimental b-rep --> CSG conversion system that converts natural quadric b-reps in Parasolid(TM) to efficient CSG representations in PADL-2.