Triangulation of the surface determined by sampling two of its cross-sections - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T04:42:05Z http://mathoverflow.net/feeds/question/122668 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/122668/triangulation-of-the-surface-determined-by-sampling-two-of-its-cross-sections Triangulation of the surface determined by sampling two of its cross-sections Daniel 2013-02-22T22:13:05Z 2013-02-24T00:57:30Z <p>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.</p> <p><img src="http://i.imgur.com/z0itDGR.png" alt="3-Dimensional Triangulation/Tesselation of Two PointClouds"></p> <p>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.)</p> <p><img src="http://i.imgur.com/pOrnYsT.png" alt="2-Dimensional Projection Along the Z-axis"></p> http://mathoverflow.net/questions/122668/triangulation-of-the-surface-determined-by-sampling-two-of-its-cross-sections/122680#122680 Answer by Joseph O'Rourke for Triangulation of the surface determined by sampling two of its cross-sections Joseph O'Rourke 2013-02-23T01:09:06Z 2013-02-24T00:57:30Z <p>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 <em>arbitrary</em> polygons in parallel slices. In other words, Daniel's hope to "simply <code>[</code>join<code>]</code> the 'corresponding' points in both 'slices' " cannot always be realized:</p> <blockquote> <p>C. Gitlin, J. O'Rourke, V. Subramanian. "On reconstruction of polyhedra from parallel slices," <em>International Journal of Computational Geometry &amp; Applications</em>, <strong>6</strong>(1) 1996, 103-122.</p> </blockquote> <p>These two polygons constitute a counterexample: <br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/cantmate-small.gif" alt="cex" /> <br /></p> <p>There is a very nice summary of the early work, and a practical algorithm, in:</p> <blockquote> <p>Gill Barequet, Daniel Shapiro, Ayellet Tal. "History Consideration in Reconstructing Polyhedral Surfaces from Parallel Slices." <em>Proceedings of IEEE Visualization</em>, 1996. (<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.5007" rel="nofollow">CiteSeer link</a>)</p> </blockquote> <p>Maybe look at this more recent work?:</p> <blockquote> <p>Samir Akkouche, Eric Galin. "Implicit surface reconstruction from contours." <em>The Visual Computer</em>. August 2004, Volume 20, Issue 6, pp 392-401. (<a href="http://The%20Visual%20Computer%20August%202004,%20Volume%2020,%20Issue%206,%20pp%20392-401/" rel="nofollow">Springer link</a>)</p> </blockquote> <p><br /> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/ContourRecon.jpg" alt="Contours" /> <br /></p>