Abstract
The use of discrete data to represent engineering structures as derivatives from intersecting components requires algorithms to perform Boolean operations between groups of triangulated surfaces. In the intersection process, an accurate and efficient method for the determination of intersection lines is a crucial step for large scale and complex surface intersections. An algorithm based on tracing the neighbours of intersecting triangles (TNOIT) is proposed to determine the intersection lines. Given the node numbers at the vertices of the triangles, the neighbour relationship is first established. A background grid is employed to limit the scope of searching for candidate triangles that may intersect. This will drastically reduce the time of geometrical checking for intersections between triangles, making the surface intersection and mesh generation a quasi-linear process with respect to the number of elements involved. In the determination of intersection between two triangles, four fundamental cases are identified and treated systematically to enhance robustness and reliability. Tracing the neighbours for the determination of intersection lines not only greatly increases the efficiency of the process, it also improves the reliability as branching and degenerated cases can all be dealt with in a consistent manner on the intersecting surfaces concerned. Five examples on a great variety of surface and mesh characteristics are given to demonstrate the effectiveness and robustness of the algorithm.
Similar content being viewed by others
References
Löhner R (1996) Regridding surface triangulations. J Comp Phys 126(1):1–10
Akkiraju N, Edelsbrunner H (1996) Triangulating the surface of a molecule. Disc Appl Math 71(1–3):5–22
Heiden W, Schlenkrich M, Brickmann J (1990) Triangulation algorithms for the representation of molecular surface properties. J Comp-Aid Mol Des 4(3):255–269
Laug P, Borouchaki H (2000) Automatic generation of finite element meshes for molecular surfaces. In: Proceedings of the European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS 2000), Barcelona, Spain, September 2000
Laug P, Borouchaki H (2001) Molecular surface modeling and meshing. In: Proceedings of the 10th International Meshing Roundtable, Newport Beach, CA, 7–10 October 2001
Shostko AA, Löhner R, Sandberg WC (1999) Surface triangulation over intersecting geometries. Int J Num Meth Eng 44:1359–1376
Bruyns CD, Senger S (2001) Interactive cutting of 3D surface meshes. Comp Graph 25(4):635–642
Lo SH (1995) Automatic mesh generation over intersecting surfaces. Int J Num Meth Eng 38:943–954
Owen SJ (1998) A survey of unstructured mesh generation technology. In: Proceedings of the 7th International Meshing Roundtable, Dearborn, MI, 26–28 October 1998
Shephard MS, Georges MK (1991) Automatic 3-dimensional mesh generation by the finite octree technique. Int J Num Meth Eng 32(4):709–749
Lo SH (1988) Finite element mesh generation over curved surfaces. Comp Struct 29:731–742
Lau TS, Lo SH (1996) Finite element mesh generation over analytical surfaces. Comp Struct 59(2):301–309
Anastasiou K, Chan CT (1996) Automatic triangular mesh generation scheme for curved surfaces. Comm Numer Meth Eng 12:197–208
Canann SA, Liu Y-C, Mobley AV (1997) Automatic 3D surface meshing to address today’s industrial needs. Fin Elem Anal Des 25:185–198
Cass RJ, Benzley SE, Meyers RJ, Blacker TD (1996) Generalized 3-D paving: an automated quadrilateral surface mesh generation algorithm. Int J Num Meth Eng 39(9):1475–1489
Hartmann E (1998) A marching method for the triangulation of surfaces. Vis Comp 14:95–108
Borouchaki H, Laug P, George P-L (2000) Parametric surface meshing using a combined advancing-front generalized Delaunay approach. Int J Num Meth Eng 49:233–259
Cuillière JC (1998) An adaptive method for the automatic triangulation of 3D parametric surfaces. Comp-Aid Des 30(2):95–161
Lee CK, Hobbs RE (1998) Automatic adaptive finite element mesh generation over rational B-spline surfaces. Comp Struct 69(5):577–608
Lee CK (1999) Automatic metric advancing front triangulation over curved surfaces. Eng Comp 16:230–263
Cebral JR, Löhner R, Choyke, Yim PJ (2001) Merging of intersecting triangulations for finite element modeling. J biomech 34(6):815–819
Cristovão L, Coelho G, Gattass M, de Figueiredo LH (2000) Intersecting and trimming parametric meshes on finite element shells. Int J Num Meth Eng 47:777–800
Bonet J, Peraire J (1991) An alternating digital tree (ADT) algorithm for geometric searching and intersection problems. Int J Num Meth Eng 31:1–17
Aftosmis MJ, Berger MJ, Melton JE (1998) Robust and efficient Cartesian mesh generation for component-based geometry. AIAA J 36(6):952–960
Lo SH (1998) Analysis and verification of the boundary surfaces of solid objects. Eng Comp 14:36–47
Acknowledgements
Financial support from the Committee of Research and Conference Grants for the project “Automatic mesh generation of 3D hexahedral elements” is highly appreciated.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lo, S.H., Wang, W.X. A fast robust algorithm for the intersection of triangulated surfaces. Engineering with Computers 20, 11–21 (2004). https://doi.org/10.1007/s00366-004-0277-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00366-004-0277-3