EconPapers    
Economics at your fingertips  
 

Simple and Robust Boolean Operations for Triangulated Surfaces

Meijun Zhou, Jiayu Qin (), Gang Mei () and John C. Tipper
Additional contact information
Meijun Zhou: School of Engineering and Technology, China University of Geosciences (Beijing), Beijing 100083, China
Jiayu Qin: School of Engineering and Technology, China University of Geosciences (Beijing), Beijing 100083, China
Gang Mei: School of Engineering and Technology, China University of Geosciences (Beijing), Beijing 100083, China
John C. Tipper: Institute of Earth and Environmental Science, University of Freiburg, D-79104 Freiburg im Breisgau, Germany

Mathematics, 2023, vol. 11, issue 12, 1-20

Abstract: Boolean operations on geometric models are important in numerical simulation and serve as essential tools in the fields of computer-aided design and computer graphics. The accuracy of these operations is heavily influenced by finite precision arithmetic, a commonly employed technique in geometric calculations, which introduces numerical approximations. To ensure robustness in Boolean operations, numerical methods relying on rational numbers or geometric predicates have been developed. These methods circumvent the accumulation of rounding errors during computation, thus preserving accuracy. Nonetheless, it is worth noting that these approaches often entail more intricate operation rules and data structures, consequently leading to longer computation times. In this paper, we present a straightforward and robust method for performing Boolean operations on both closed and open triangulated surfaces. Our approach aims to eliminate errors caused by floating-point operations by relying solely on entity indexing operations, without the need for coordinate computation. By doing so, we ensure the robustness required for Boolean operations. Our method consists of two main stages: (1) Firstly, candidate triangle intersection pairs are identified using an octree data structure, and then parallel algorithms are employed to compute the intersection lines for all pairs of triangles. (2) Secondly, closed or open intersection rings, sub-surfaces, and sub-blocks are formed, which is achieved entirely by cleaning and updating the mesh topology without geometric solid coordinate computation. Furthermore, we propose a novel method based on entity indexing to differentiate between the union, subtraction, and intersection of Boolean operation results, rather than relying on inner and outer classification. We validate the effectiveness of our method through various types of Boolean operations on triangulated surfaces.

Keywords: Boolean operations; triangulated surfaces; computational geometry; geometrical robustness (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/12/2713/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/12/2713/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:12:p:2713-:d:1171761

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().

 
Page updated 2025-03-19
Handle: RePEc:gam:jmathe:v:11:y:2023:i:12:p:2713-:d:1171761