ACCRETIVE BREP-TO-CSG CONVERSION FOR FREE-FORM SOLIDS USING POINT-SAMPLING METHODS
Jai P. Menon · International Journal of Shape Modeling · 1996
Meshes of low degree (quadratic, cubic) implicit algebraic patches have been used for constructing a smooth Boundary representation (Brep) of a free-form solid A. We provide methods for computing a consistent Constructive Solid Geometry (CSG) representation. of A in order to maintain dual [Brep, CSG] representations of these solids. CSG computation however requires expensive combinatorial processing, especially when bounding tetrahedra of the patches of Brep(A) inter-penetrate. This paper develops a new accretive algorithm for solving this combinatorial problem in the following manner.We employ a technique for fast Line Membership Classification (LMC) using an enhanced CSG algorithm that does not require complete CSG conversion from Brep(A). Instead, the LMC algorithm processes a partial CSG(A), called the Constructive Shell Representation of A, to compute line segments that are "in" A. This algorithm is well suited, especially for processing A on dedicated CSG hardware such as the RayCasting Engine. When the lines are parallel and regularly spaced, we get a ray-grid, and the line segments "in" A (resulting from LMC) constitute a ray-rep of A. This ray-rep is used to speed up the computation of the complete CSG(A) through a new accretive algorithm. The algorithm employs a point-sampling technique that obviates combinatorial processing, especially for inter-penetrating tetrahedra, and offers an ∊-close conversion to within the resolution of the ray-grid.