Identifying flat and tubular regions of a shape by unstable manifolds

ABSTRACT

We present an algorithm to identify the flat and tubular regions of a three dimensional shape from its point sample. We consider the distance function to the input point cloud and the Morse structure induced by it on R³. Specifically we focus on the index 1 and index 2 saddle points and their unstable manifolds. The unstable manifolds of index 2 saddles are one dimensional whereas those of index 1 saddles are two dimensional. Mapping these unstable manifolds back onto the surface, we get the tubular and flat regions. The computations are carried out on the Voronoi diagram of the input points by approximating the unstable manifolds with Voronoi faces. We demonstrate the performance of our algorithm on several point sampled objects.

REFERENCES

• 1: Chandrajit L. Bajaj , Fausto Bernardini , Guoliang Xu, Automatic reconstruction of surfaces and scalar fields from 3D scans, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.109-118, September 1995 [doi>10.1145/218380.218424]
• 2: Berman, H. M., Westbrook, J., Feng, Z., Gilliland, G., Bhat, T., Weissig, H., Shindyalov, I., and Bourne, P. 2000. The protein data bank. Nucleic Acids Research, 235--242.
• 3: Bernardini, F., Bajaj, C., Chen, J., and Schikore, D. 1999. Automatic reconstruction of 3d cad models from digital scans. Int. J. on Comp. Geom. and Appl. 9, 4--5, 327--369.
• 4: CGAL CONSORTIUM. CGAL: Computational Geometry Algorithms Library. http://www.cgal.org.
• 5: Raphaëlle Chaine, A geometric convection approach of 3-D reconstruction, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 6: Chazal, F., and Lieutier, A. 2004. Stability and homotopy of a subset of the medial axis. In Proc. 9th ACM Sympos. Solid Modeling and Applications, 243--248.
• 7: COCONE. Tight Cocone Software for surface reconstruction and medial axis approximation. http://www.cse.ohio-state.edu/~tamaldey/cocone.html.
• 8: Tamal K. Dey , Samrat Goswami, Tight cocone: a water-tight surface reconstructor, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781627]
• 9: Dey, T. K., and Goswami, S. 2004. Provable surface reconstruction from noisy samples. In Proc. 20th ACM-SIAM Sympos. Comput. Geom., 330--339.
• 10: Tamal K. Dey , Wulue Zhao, Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee, Algorithmica, v.38 n.1, p.179-200, October 2003 [doi>10.1007/s00453-003-1049-y]
• 11: Dey, T. K., Giesen, J., and Goswami, S. 2003. Shape segmentation and matching with flow discretization. In Proc. Workshop Algorithms Data Strucutres (WADS 03), F. Dehne, J.-R. Sack, and M. Smid, Eds., LNCS 2748, 25--36.
• 12: Dey, T. K., Giesen, J., Ramos, E., and Sadri, B. 2005. Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based surface reconstruction. In Proc. 21st ACM-SIAM Sympos. Comput. Geom., 218--227.
• 13: Edelsbrunner, H. 2002. Surface reconstruction by wrapping finite point sets in space. In Ricky Pollack and Eli Goodman Festschrift, B. Aronov, S. Basu, J. Pach, and M. Sharir, Eds. Springer-Verlag, 379--404.
• 14: Joachim Giesen , Matthias John, The flow complex: a data structure for geometric modeling, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 15: Sagi Katz , Ayellet Tal, Hierarchical mesh decomposition using fuzzy clustering and cuts, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 16: Michela Mortara , Giuseppe Patané , Michela Spagnuolo , Bianca Falcidieno , Jarek Rossignac, Blowing Bubbles for Multi-Scale Analysis and Decomposition of Triangle Meshes, Algorithmica, v.38 n.1, p.227-248, October 2003 [doi>10.1007/s00453-003-1051-4]
• 17: Mortara, M., Patanè, G., Spagnuolo, M., Falcidieno, B., and Rossignac, J. 2004. Plumber: a multi-scale decomposition of 3d shapes into tubular primitives and bodies. In Proc. 9th ACM Sympos. Solid Modeling and Applications, 139--158.
• 18: Pottmann, H., Hofer, M., Odehnal, B., and Wallner, J. 2004. Line geometry for 3d shape understanding and reconstruction. Computer Vision - ECCV 3021, 1, 297--309.
• 19: Shinagawa, Y., Kunni, T., Belayev, A., and Tsukioka, T. 1996. Shape modeling and shape analysis based on singularities. Internat. J. Shape Modeling 2, 85--102.
• 20: Kaleem Siddiqi , Ali Shokoufandeh , Sven J. Dickinson , Steven W. Zucker, Shock Graphs and Shape Matching, Proceedings of the Sixth International Conference on Computer Vision, p.222, January 04-07, 1998
• 21: Várady, T., Martin, R., and Cox, J. 1997. Reverse engineering of geometric models - an introduction. Computer Aided Design 29, 255--268.
• 22: Verroust, A., and Lazarus, F. 2000. Extracting skeletal curves from 3d scattered data. The Visual Computer 16, 15--25.
• 23: Wu, J., and Kobbelt, L. 2005. Structure recovery via hybrid variational surface approximation. Computer Graphics Forum 24, 3, 277--284.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Keywords:
Point cloud, delaunay triangulation, unstable manifold, voronoi diagram