Boolean operations on triangulated solids

摘要

In this paper an efficient and robust method for Boolean operations on triangulated solids is presented. It is applied to regularized Boolean operations including union, difference, and intersection. This approach is better than other methods because three optimizations have been introduced. First, the constructed topology information improves the data structure from discrete triangles to point indices, face indices, and their connectivity information. Second, the space dividing algorithm has improved the computational complexity from O (m * n) to O (k (log K)). Third, the tessellation has enumerated a number of special triangle-triangle intersection examples, which are then dealt with separately. Finally, this method is implemented by a program written in C++ and OSG. With some examples, this system is proved to be efficient and robust.