W Randolph Franklin home page
... (old version)
Research/ home page Login

(in WR FranklinResearch)

This 1992 algorithm combines two different triangulations of the same 3D faceted object, to determine which pairs of tetrahedra overlap, and the intersection volumes. This is useful for interpolating data from one triangulation of an object to another.


Abstract: Consider a polyhedron that is triangulated into tetrahedra in two different ways. This paper presents an algorithm, and hints for implementation, for finding the volumes of the intersections of all overlapping pairs of tetrahedra. The algorithm should parallelize easily, based on our experience with similar algorithms. One application for this is, when given data in terms of one triangulation, to approximate it in terms of the other triangulation. One part of this algorithm is useful by itself. That is to locate a large number of points in a triangulation, by finding which tetrahedron contains each point.

Keywords: Keywords: tetrahedron, triangulation, overlay, uniform grid, finite element model, mass property, uniform grid, parallel, point location