Separation for boundary to CSG conversion

Abstract

important applications of b-rep -CSG conversion arise in solid modeling, image processing, and c,lsewhere. 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 o 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 suff]cicnt set of linear separating half-spaces exists for any solid whose boundary contains only planar edges. A compl[,te construction is given for solids whose faces lie in convex surfaces. Separation for more L,cneral solids, whose b-rep includes othm surfaces and nonplanar edges, is alsa discussed, but this general problem remains poorly understood. We apply the boundary-based separation to solids hounded by genera] 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 + CSW conversion system that converts natural quadric b-reps in ]>:lras(J]ldTMt(} ~~clcnt C'SG representations in PADL-2 Categ[jric,s and Subject Ilescriptors