Overlaying 3D Triangulations

Research archive · original page Research.Overlaying3DTriangulations · last recorded update 2009-11-14

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.

@incollection{fk-vo3tp-93,
    author = "Franklin, Wm Randolph and Kankanhalli, Mohan S.",
    editor = "Abel, D. and Ooi, B.C.",
    title = "Volumes From Overlaying 3-{D} Triangulations in Parallel",
    booktitle = "Advances in Spatial Databases: Third Intl. Symp., SSD'93",
    publisher = "Springer-Verlag",
    month = "June",
    year = "1993",
    series = "Lecture Notes in Computer Science",
    volume = "692",
    pages = "477--489",
    comment = "SSD = Symp on Large Spatial DBs, Singapore",
    fulltext = "https://wrfranklin.org/p/78-ssd93-tet.pdf",
    href = "\bibhref{78-ssd93-tet}",
    keywords = "parallel computation, intersection, volume, CAD",
    mykey = "kankanhalli overlay parallel"
}

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