Efficient polygonization of CSG solids using boundary tracking

Abstract

In this paper, we propose a procedure that directly polygonizes the boundary surface of CSG solids. The procedure consists of a preprocessing step and a polygonization process followed by a postprocessing that recovers rounded edges and corners. In the preprocessing step, the minimum 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 way that among leaf voxels of the space subdivision only voxels that overlap the solid's boundary are traversed and inside such voxels only grid cells transversal to the solid's boundary are tracked. The surface-edge intersections and vertex normals are computed directly from the exact boundary surfaces of the CSG solid. In the postprocessing step, rounded edges and corners are detected and recovered using primitive geometry. (C) 1997 Elsevier Science Ltd. All rights reserved.