Boundry-Based Separation for B-rep $\rightarrow$ CSG Conversion

Abstract

We have shown earlier that one of the most difficult steps in performing b-rep $\rightarrow$ CSG conversion for a curved solid object consists of determining a set of halfspaces that is sufficient for a CSG representation of the solid. This usually requires the construction of additional halfspaces whose boundaries do not contribute to the boundary of the solid. Such halfspaces are called separating halfspaces because their purpose is to separate certain subsets of $E^{3}$ inside the solid from those outside of the solid. Construction of separating halfspaces is specific to a particular geometric domain, but several generic approaches are possible. A boundary-based separation is a construction of separating halfspaces that relies on the information present in the boundary of the solid being converted While boundary-based separation for solids with non-planar edges is not well understood, we study the contraints on the degree of separating halfspaces, and show that a set of linear separating halfspaces exists for any solid whose boundary contains only planar edges. We apply the boundary-based separation to solids bounded by general quadric surfaces. Specifically, we prove that a sufficient set of linear separating halfspaces exists for any such solid, and consider the required constructions in several common situations. Implications for more general solids are also discussed.