Exact and Efficient Intersection Resolution for Mesh Arrangements

We propose a novel method to exactly and efficiently resolve intersections and self-intersections in triangle meshes. Our method contains two key components. First, we present a new concept of geometric predicates, called indirect offset predicates , to represent all intersection points through a new formulation and establish all necessary geometric predicates. Consequently, we reduce numerical errors in floating-point evaluations and improve the success rate of early stages of arithmetic filtering. Second, we develop localization and dimension reduction techniques for sorting, deduplicating, and locating the intersection points, thereby boosting efficiency and parallelism while maintaining accuracy. Rigorous testing confirms the robustness of our algorithm and consistency with previous methods. Comprehensive testing across diverse datasets further highlights the speed improvement achieved by our method, which is one order of magnitude faster than the state-of-the-art methods.