Premium
Triangulation of arbitrary polyhedra to support automatic mesh generators
Author(s) -
Karamete B. Kaan,
Beall Mark W.,
Shephard Mark S.
Publication year - 2000
Publication title -
international journal for numerical methods in engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.421
H-Index - 168
eISSN - 1097-0207
pISSN - 0029-5981
DOI - 10.1002/1097-0207(20000910/20)49:1/2<167::aid-nme928>3.0.co;2-l
Subject(s) - delaunay triangulation , constrained delaunay triangulation , bowyer–watson algorithm , surface triangulation , minimum weight triangulation , pitteway triangulation , computer science , algorithm , chew's second algorithm , vertex (graph theory) , mesh generation , t vertices , polyhedron , triangulation , boundary (topology) , laplacian smoothing , ruppert's algorithm , mathematics , combinatorics , theoretical computer science , geometry , finite element method , graph , mathematical analysis , physics , thermodynamics
An algorithm is presented for the triangulation of arbitrary non‐convex polyhedral regions starting with a prescribed boundary triangulation matching existing mesh entities in the remainder of the domain. The algorithm is designed to circumvent the termination problems of volume meshing algorithms which manifest themselves in the inability to successfully create tetrahedra within small subdomains to be referred to herein as cavities. To address this need, a robust Delaunay algorithm with an efficient and termination guaranteed face recovery method is the most appropriate approach. The algorithm begins with Delaunay vertex insertion followed by a face recovery method that conserves the boundary of the cavity by utilizing local mesh modification operations such as edge split, collapse and swap and a new set of tools which we call complex splits. The local mesh modifications are performed in such a manner that each original surface triangulation is represented either as was, or as a concatenation of triangles. When done in this manner, it is always possible to split the matching mesh entities, ensuring that a compatible mesh is created. The algorithm is robust and has been tested against complex manifold and non‐manifold cavities resulting in a valid mesh of the entire domain. Copyright © 2000 John Wiley & Sons, Ltd.