me | department | university | teaching | research | disclaimer | personal stuff



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.


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).


[Image of Tetrahedral Mesh] This image shows the tetrahedral mesh of a rook. (The red lines depict edges of the Delaunay tetrahedra.)
[Image of Polyhedron] 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.

[Image of Tetrahedral Mesh] This image shows the tetrahedral mesh of a WW-II aircraft. (The red lines depict edges of the Delaunay tetrahedra.)
[Image of Polyhedron] This image shows only those tetrahedra of the mesh which form the boundary of the aircraft.

[Image of Tetrahedral Mesh] This image shows the tetrahedral mesh of a triceratops. (The red lines depict edges of the Delaunay tetrahedra.)
[Image of Polyhedron] This image shows only those tetrahedra of the mesh which form the boundary of the triceratops.


[Image of CS Logo]
file last modified: Friday, 26-Feb-2016 12:34:25 CET
email address
Copyright © 2017 Martin Held. All rights reserved.
[Rock climbing]