EFFICIENT POLYGONIZATION OF CSG SOLIDS USING BOUNDARY TRACKING

In this paper, we propose a procedure that directly polygonizes the bo undary surface of CSG solids. The procedure consists of a preprocessin g step and a polygonization process followed by a postprocessing that recovers rounded edges and corners. In the preprocessing step, the min imum bounding volumes, called S-bounds, of all nodes in the given CSG tree are computed and then used as a basis for subdividing the S-bound of the tree's root. In addition, a regular grid embedded on the root' s S-bound is constructed. The polygonization is performed in such a wa y that among leaf voxels of the space subdivision only voxels that ove rlap the solid's boundary are traversed and inside such voxels only gr id cells transversal to the solid's boundary are tracked. The surface- edge intersections and vertex normals are computed directly from the e xact boundary surfaces of the CSG solid. In the postprocessing step, r ounded edges and corners are detected and recovered using primitive ge ometry. (C) 1997 Elsevier Science Ltd. All rights reserved.