Boolean operations on arbitrary polygonal and polyhedral meshes. (April 2017)

• Record Type: Journal Article
• Authors: Landier, Sâm
• Is Part Of: Computer aided design. Volume 85(2017)
• Page Start: 138
• Page End: 153
• Publication Date: 2017-04
• Subjects: Boolean operations -- Polyhedral meshes -- Polygonal meshes -- Conservative remapping -- Cut-cell meshing -- Flood fill algorithm; Computer-aided design -- Periodicals; Engineering design -- Data processing -- Periodicals; Computer graphics -- Periodicals; Conception technique -- Informatique -- Périodiques; Infographie -- Périodiques; Computer graphics; Engineering design -- Data processing; Periodicals; Electronic journals; 620.00420285
• DOI: 10.1016/j.cad.2016.07.013
• Languages: English
• ISSNs: 0010-4485

Abstract

Abstract: A linearithmic floating-point arithmetic algorithm designed for solving usual boolean operations (intersection, union, and difference) on arbitrary polygonal and polyhedral meshes is described in this paper. This method does not dis-feature the inputs which can be two volume meshes, two surface meshes or one of each. It provides conformal meshes upon exit. It can be used in many pre- and post-processing applications in computational physics (e.g. cut-cell volume mesh generation or conservative remapping). The core idea is to consider any configuration as a polygonal cloud. The polygons are first triangulated, the intersections are solved, the polyhedral cells are then reconstructed from the conformal triangles cloud and finally their triangular faces are re-aggregated to polygons. This approach offers great flexibility regarding the admissible topologies: non-planar faces, concave faces or cells and some non-manifoldness are handled. The algorithm is described in detail and some current results are shown. Highlights: A general algorithm to solve boolean operations on arbitrary meshes is proposed. The inputs can be two volume meshes, two surface meshes or one of each. Admissible topologies are numerous; convexity and manifoldness are not required. The inputs can be partially or fully overlapping. The result is a polyhedral or polygonal conformal mesh.