“Reconstructing surfaces using envelopes: bridging the gap between theory and practice” by Bisceglio, Peters and Abe

Reconstruction of surfaces with boundary remains a challenge. Recent theoretical advances [Abe et al. 2006] define envelopes as surfaces without boundary to approximate those with boundary. Figure 1 shows a Möbius strip on the left, denoted as M. An illustration of its envelope appears next, intuitively understood as attaching a small ball to each point of M to create a 3-manifold. The envelope of M is then the bounding surface of this 3-manifold. The images represent approximations of this process. The new theory shows that envelopes can guarantee topological preservation during reconstruction, but practical implementations are still emerging. This theory is advantageous in that it offers a terse measure of equivalence known as an ambient isotopy and expands the class of surfaces which may be reconstructed. We present progress toward development of an algorithm that robustly implements this theorem.Constructing envelope enclosures around point set data, in the absence of all other geometric information, means approximating normals and identifying boundaries. The most current published approach [Ohtake et al. 2005], uses error minimization to create an adaptive spherical covering. However, the authors state that this approach is not supported by any mathematical results and is only appropriate for certain types of input data.The approximation quality of a reconstructed surface depends on how well the estimated normals approximate the true normals of the sampled surface. Dey [Dey et al. 2005] presents a detailed understanding of this concept with a survey of techniques for estimating normals and the circumstances under which they are appropriate. A sufficient sampling density is a prerequisite for approximating normals. We adapt a relation for bounding the sampling criteria [Amenta et al. 2003] to be suitable for the construction of envelopes. The sampling criteria of a surface is gauged according to the distance to its medial axis. With envelopes, the distance to the medial axis is the radius of the envelope. Thus, not only must a sample density be carefully chosen but so must the radius of the envelope. Our investigation begins by examining criteria for selecting these variables.An experimental study in 2005 gave an understanding of the importance of sufficient sampling and proper envelope construction. Pursuant to these findings, a detailed test on the effects of varying both the envelope radius and the sample density was performed yielding new insight regarding sufficient sampling when generating envelopes. We conclude with progress towards improving a realistic trial presented in the literature. Spline surfaces, which allow envelope construction through an exact evaluation, are used in most of our experiments. This is only helpful for testing. A publication [Abe et al. 2005] demonstrates the practical difficulties of using the envelope technique on point set data including an example with the Stanford bunny. A revised version of this bunny test is shown here.

1. Abe, K., Bisceglio, J., Peters, T. J., Russell, A. C., Ferguson, D. R., and Sakkalis, T. 2005. Computational topoloogy for reconstruction of surfaces with boundary: integrating experiments and theory. In IEEE International Conference on Shape Modeling and Applications, vol. 4, IEEE, 288–297.
2. Abe, K., Bisceglio, J., Peters, T. J., Russell, A. C., Ferguson, D. R., and Sakkalis, T., 2006. Computational topology for isotopic surface reconstruction. Theoretical Computer Science, to appear.
3. Amenta, N., Peters, T. J., and Russell, A. C. 2003. Computational topology: ambient isotopic approximation of 2-manifolds. Theoretical Computer Science 305, 3–15.
4. Dey, T. K., Li, G., and Su, J. 2005. Normal estimation for point clouds: a comparison study for a voronoi based method. In Eurographics Symposium on Point-Based Graphics, The Eurographics Association, 39–46.
5. Ohtake, Y., Belyaev, A., and Seidel, H.-P. 2005. An integrating approach to meshing scattered point data. In SPM ’05: Proceedings of the 2005 ACM symposium on Solid and physical modeling, ACM Press, New York, NY, USA, ACM, 61–69.