Conforming Mesh Generation

The generation of a tetrahedral subdivision of the interior or of the exterior of a polyhedral solid has many applications, most notably in finite-element meshing (FEM). Our own motivation for designing and implementing a meshing code was provided by doing collision detection for VR: One can hope to reduce the number of pairwise intersection checks drastically by tracking the motion of the moving object within the tetrahedral mesh of the environment.

Currently, the tetrahedral meshes (in the interiors and in the exteriors of all polyhedral objects given) are generated in an iterative manner: starting with the polyhedra's vertex set, Steiner points are added until the corresponding Delaunay triangulation "conforms" to the surfaces of the polyhedra.

Related publications:

M. Held, J.T. Klosowski, J.S.B. Mitchell (1995):
``Evaluation of Collision Detection Methods for Virtual Reality Fly-Throughs''.
Proc. 7th Canad. Conf. Computat. Geometry, C. Gold, J.-M. Robert (eds.), pp. 205-210; Québec City, Québec, Canada, Aug 10-13, 1995.

Full paper (Postscript, 121 KB).

The following images show tetrahedral meshes for a few polyhedra which were computed by means of my meshing code. (Click on an image icon in order to see the full-size image. The full-size images have 1000x700 pixels.) Most polyhedral models have been obtained from the Web, e.g., from Viewpoint's "Avalon" Archive (which seems to have been taken off the net in the meantime).

This image shows the tetrahedral mesh of a rook. (The red lines depict edges of the Delaunay tetrahedra.)

This image shows only those tetrahedra of the mesh which form the boundary of the rook. Some of the Steiner points added in the top part of the rook are clearly visible.

This image shows the tetrahedral mesh of a WW-II aircraft. (The red lines depict edges of the Delaunay tetrahedra.)

This image shows only those tetrahedra of the mesh which form the boundary of the aircraft.

This image shows the tetrahedral mesh of a triceratops. (The red lines depict edges of the Delaunay tetrahedra.)

This image shows only those tetrahedra of the mesh which form the boundary of the triceratops.

file last modified: Thursday, 27-Feb-2020 07:29:07 CET