Triangulation of the surface determined by sampling two of its cross-sections - MathOverflow

Triangulation of the surface determined by sampling two of its cross-sections

2013-02-22T22:13:05Z

I have a data set that essentially looks like the picture below, i.e., it's given by sets of points in $\mathbb{R}^3$ that sample the cross-sections of a certain surface that in principle I do not know. In fact, I would like to recover this surface or, more precisely, a triangulation/mesh of it.

In this particular example, it is not difficult to see that we have a section of a cone. In this sense, I do not want to compute the convex hull of these points, but instead I just want to find its boundary (if this makes any sense; I actually don't know whether it does), i.e., I want to find the surface that one could obtain by simply joining the "corresponding" points in both "slices". (I've put "corresponding [points]" in quotes because I believe it's not straightforward to perform this matching exercise, i.e., find the point on the adjacent slice that isn't necessarily the closest one in the $\mathbb{R}^3$ metric, but would correspond to the closest one if we projected one slice into another and considered only the $\mathbb{R}^2$ distance between them, as seen below.)

Answer by Joseph O'Rourke for Triangulation of the surface determined by sampling two of its cross-sections

2013-02-23T01:09:06Z

This is a problem that has been studied for a long time. I showed with my students Carol Gitlin and Vinita Subramanian, that there does not always exist a polyhedron that connects two arbitrary polygons in parallel slices. In other words, Daniel's hope to "simply [join] the 'corresponding' points in both 'slices' " cannot always be realized:

C. Gitlin, J. O'Rourke, V. Subramanian. "On reconstruction of polyhedra from parallel slices," International Journal of Computational Geometry & Applications, 6(1) 1996, 103-122.

These two polygons constitute a counterexample:

There is a very nice summary of the early work, and a practical algorithm, in:

Gill Barequet, Daniel Shapiro, Ayellet Tal. "History Consideration in Reconstructing Polyhedral Surfaces from Parallel Slices." Proceedings of IEEE Visualization, 1996. (CiteSeer link)

Maybe look at this more recent work?:

Samir Akkouche, Eric Galin. "Implicit surface reconstruction from contours." The Visual Computer. August 2004, Volume 20, Issue 6, pp 392-401. (Springer link)