Fast, Exact and Robust Set Operations on Polyhedrons Using Localized Constructive Solid Geometry Trees

摘要

Regularized Boolean operations have been widely used in 3D modeling systems. However, evaluating Boolean operations may be quite numerically unstable and time consuming, espe⁃cially for iterated set operations. A novel and unified tech⁃nique is proposed in this paper for computing single and iter⁃ated set operations efficiently, robustly and exactly. An adap⁃tive octree is combined with a nested constructive solid geom⁃etry (CSG) tree by this technique. The intersection handling is restricted to the cells in the octree where intersection actu⁃ally occurs. Within those cells, a CSG tree template is in⁃stanced by the surfaces and the tree is converted to plane⁃based binary space partitioning (BSP) for set evaluation;More⁃over, the surface classification is restricted to the cells in the octree where the surfaces only come from a model and are within the bounding⁃boxes of other polyhedrons. These two ways bring about the efficiency and scalability of the opera⁃tions, in terms of runtime and memory. As all surfaces in such a cell have the same classification relation, they are clas⁃sified as a whole. Robustness and exactness are achieved by integrating plane⁃based geometry representation with adaptive geometry predicate technique in intersection handling, and by applying divide⁃and⁃conquer arithmetic on surface classifica⁃tion. Experimental results demonstrate that the proposed ap⁃proach can guarantee the robustness of Boolean computations and runs faster than other existing approaches.