Exact fast parallel intersection of large 3-d triangular meshes. (English) Zbl 07216463

Roca, Xevi (ed.) et al., Proceedings of the 27th International Meshing Roundtable (IMR), Albuquerque, NM, USA, October 1–5, 2018. Cham: Springer. Lect. Notes Comput. Sci. Eng. 127, 365-383 (2019).
Summary: We present 3D-EPUG-Overlay, a fast, exact, parallel, memory-efficient, algorithm for computing the intersection between two large 3-D triangular meshes with geometric degeneracies. Applications include CAD/CAM, CFD, GIS, and additive manufacturing. 3D-EPUG-Overlay combines five separate techniques: multiple precision rational numbers to eliminate roundoff errors during the computations; Simulation of Simplicity to properly handle geometric degeneracies; simple data representations and only local topological information to simplify the correct processing of the data and make the algorithm more parallelizable; a uniform grid to efficiently index the data, and accelerate testing pairs of triangles for intersection or locating points in the mesh; and parallel programming to exploit current hardware. 3D-EPUG-Overlay is up to 101 times faster than LibiGL, and comparable to QuickCSG, a parallel inexact algorithm. 3D-EPUG-Overlay is also more memory efficient. In all test cases 3D-EPUG-Overlay’s result matched the reference solution. It is freely available for nonprofit research and education at https://github.com/sallesviana/MeshIntersection.
For the entire collection see [Zbl 1417.65007].


65Dxx Numerical approximation and computational geometry (primarily algorithms)
Full Text: DOI


[1] V. Akman, W.R. Franklin, M. Kankanhalli, C. Narayanaswami, Geometric computing and the uniform grid data technique. Comput. Aided Des. 21(7), 410-420 (1989)
[2] A. Belussi, S. Migliorini, M. Negri, G. Pelagatti, Snap rounding with restore: an algorithm for producing robust geometric datasets. ACM Trans. Spatial Algoritm. Syst. 2(1), 1:1-1:36 (2016)
[3] G. Bernstein, D. Fussell, Fast, exact, linear booleans. Eurographics Symp. Geom. Process. 28(5), 1269-1278 (2009)
[4] Cgal, Computational Geometry Algorithms Library. https://www.cgal.org. Retrieved Sept 2018
[5] P. Cignoni, C. Rocchini, R. Scopigno, Metro: measuring error on simplified surfaces. Comput. Graphics Forum 17(2), 167-174 (1998)
[6] M. de Berg, D. Halperin, M. Overmars, An intersection-sensitive algorithm for snap rounding. Comput. Geom. 36(3), 159-165 (2007) · Zbl 1109.65018
[7] S.V.G. de Magalhães, Exact and parallel intersection of 3D triangular meshes, Ph.D. thesis, Rensselaer Polytechnic Institute, 2017
[8] S.V.G. de Magalhães, W.R. Franklin, M.V.A. Andrade, W. Li, An efficient algorithm for computing the exact overlay of triangulations, in 25th Fall Workshop on Computational Geometry, U. Buffalo, New York, USA, 23-24 Oct 2015 (2015). Extended abstract
[9] M. Douze, J.-S. Franco, B. Raffin, QuickCSG: arbitrary and faster boolean combinations of n solids, Ph.D. thesis, Inria-Research Centre, Grenoble-Rhône-Alpes, France, 2015
[10] H. Edelsbrunner, E.P. Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM TOG 9(1), 66-104 (1990) · Zbl 0732.68099
[11] F. Feito, C. Ogayar, R. Segura, M. Rivero, Fast and accurate evaluation of regularized boolean operations on triangulated solids. Comput. Aided Des. 45(3), 705-716 (2013)
[12] W.R. Franklin, Efficient polyhedron intersection and union, in Proceedings of Graphics Interface, pp. 73-80, Toronto (1982)
[13] W.R. Franklin, Adaptive grids for geometric operations. Cartographica 21(2-3), 161-167, Summer - Autumn (1984). Monograph 32-33
[14] W.R. Franklin, Polygon properties calculated from the vertex neighborhoods, in Proceedings of 3rd Annual ACM Symposium on Computational Geometry, pp. 110-118 (1987)
[15] W.R. Franklin, S.V.G. Magalhães, Parallel intersection detection in massive sets of cubes, in Proceedings of BigSpatial’ 17: 6th ACM SIGSPATIAL Workshop on Analytics for Big Geospatial Data, Los Angeles Area, CA, USA, 7-10 Nov 2017 (2017)
[16] W.R. Franklin, N. Chandrasekhar, M. Kankanhalli, M. Seshan, V. Akman, Efficiency of uniform grids for intersection detection on serial and parallel machines, in New Trends in Computer Graphics (Proc. Computer Graphics International’88), ed. by N. Magnenat-Thalmann, D. Thalmann, pp. 288-297 (Springer, Berlin, 1988)
[17] W.R. Franklin, C. Narayanaswami, M. Kankanhalli, D. Sun, M.-C. Zhou, P. Y. Wu, Uniform grids: a technique for intersection detection on serial and parallel machines, in Proceedings of Auto Carto 9: Ninth International Symposium on Computer-Assisted Cartography, pp. 100-109, Baltimore, Maryland, 2-7 April 1989 (1989)
[18] P.J. Frey, P. George, Mesh Generation: Application to Finite Elements, Second Edition (ISTE Ltd./Wiley, London/Hoboken, 2010) · Zbl 1156.65018
[19] C. Geuzaine, J.-F. Remacle, Gmsh: a 3-d finite element mesh generator with built-in pre-and post-processing facilities. Int. J. Numer. Methods Eng. 79(11), 1309-1331 (2009) · Zbl 1176.74181
[20] S. Ghemawat, P. Menage, TCMalloc: thread-caching malloc (15 Nov 2015), http://goog-perftools.sourceforge.net/doc/tcmalloc.html. Retrieved on 13 Nov 2016
[21] P. Hachenberger, L. Kettner, K. Mehlhorn, Boolean operations on 3d selective nef complexes: data structure, algorithms, optimized implementation and experiments. Comupt. Geom. 38(1), 64-99 (2007) · Zbl 1118.65308
[22] D. Hedin, W.R. Franklin, NearptD: a parallel implementation of exact nearest neighbor search using a uniform grid, in Canadian Conference on Computational Geometry, Vancouver Canada (Aug. 2016)
[23] J. Hershberger, Stable snap rounding. Comput. Geom. 46(4), 403-416 (2013) · Zbl 1261.65023
[24] J.D. Hobby, Practical segment intersection with finite precision output. Comput. Geom. 13(4), 199-214 (1999) · Zbl 0948.68197
[25] A. Jacobson, D. Panozzo, et al., libigl: A Simple C++ Geometry Processing Library (2016), http://libigl.github.io/libigl/. Retrieved on 18 Oct 2017
[26] M. Kankanhalli, W.R. Franklin, Area and perimeter computation of the union of a set of iso-rectangles in parallel. J. Parallel Distrib. Comput. 27(2), 107-117 (1995) · Zbl 0835.68059
[27] L. Kettner, K. Mehlhorn, S. Pion, S. Schirra, C. Yap, Classroom examples of robustness problems in geometric computations. Comput. Geom. Theory Appl. 40(1), 61-78 (2008) · Zbl 1135.65311
[28] C. Leconte, H. Barki, F. Dupont, Exact and Efficient Booleans for Polyhedra. Technical Report RR-LIRIS-2010-018, LIRIS UMR 5205 CNRS/INSA de Lyon/Université Claude Bernard Lyon 1/Université Lumière Lyon 2/École Centrale de Lyon (Oct. 2010). Retrieved on 19 Oct 2017
[29] C. Li, Exact geometric computation: theory and applications, Ph.D. thesis, Department of Computer Science, Courant Institute - New York University, January 2001
[30] S.V.G. Magalhães, M.V.A. Andrade, W.R. Franklin, W. Li, Fast exact parallel map overlay using a two-level uniform grid, in 4th ACM SIGSPATIAL International Workshop on Analytics for Big Geospatial Data (BigSpatial), Bellevue WA USA, 3 Nov 2015
[31] S.V.G. Magalhães, M.V.A. Andrade, W.R. Franklin, W. Li, PinMesh – fast and exact 3D point location queries using a uniform grid. Comput. Graph. J. 58, 1-11 (2016). Special issue on Shape Modeling International 2016 (online 17 May). Awarded a reproducibility stamp, http://www.reproducibilitystamp.com/
[32] S.V.G. Magalhães, M.V.A. Andrade, W.R. Franklin, W. Li, M.G. Gruppi, Exact intersection of 3D geometric models, in Geoinfo 2016, XVII Brazilian Symposium on GeoInformatics, Campos do Jordão, SP, Brazil (Nov. 2016)
[33] D.J. Meagher, Geometric modelling using octree encoding. Comput. Graphics Image Process. 19, 129-147 (1982)
[34] K. Mehlhorn, R. Osbild, M. Sagraloff, Reliable and efficient computational geometry via controlled perturbation, in ICALP (1), ed. by M. Bugliesi, B. Preneel, V. Sassone, I. Wegener. Lecture Notes in Computer Science, vol. 4051, pp. 299-310 (Springer, Berlin, 2006) · Zbl 1183.68671
[35] G. Mei, J.C. Tipper, Simple and robust boolean operations for triangulated surfaces. CoRR, abs/1308.4434 (2013)
[36] Oslandia, IGN, SFCGAL, 2017, http://www.sfcgal.org/. Retrieved on 19 Oct 2017
[37] D. Pavić, M. Campen, L. Kobbelt, Hybrid booleans. Comput. Graph. Forum 29(1), 75-87 (2010)
[38] S. Pion, A. Fabri, A generic lazy evaluation scheme for exact geometric computations. Sci. Comput. Program. 76(4), 307-323 (2011)
[39] J.R. Shewchuk, Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discret. Comput. Geom. 18(3), 305-363 (1997) · Zbl 0892.68098
[40] C.K. Yap, Symbolic treatment of geometric degeneracies, in System Modelling and Optimization: Proceedings of 13th IFIP Conference, ed. by M. Iri, K. Yajima, pp. 348-358 (Springer, Berlin, 1988) · Zbl 0685.65006
[41] J. Yongbin, W. Liguan, B. Lin, C. Jianhong, Boolean operations on polygonal meshes using obb trees, in ESIAT 2009, vol. 1, pp. 619-622 (IEEE, Piscataway, 2009)
[42] Q. Zhou,
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.