Fast and robust detection of crest lines on meshes

ABSTRACT

We propose a fast and robust method for detecting crest lines on surfaces approximated by dense triangle meshes. The crest lines, salient surface features defined via first- and second-order curvature derivatives, are widely used for shape matching and interrogation purposes. Their practical extraction is difficult because it requires good estimation of high-order surface derivatives. Our approach to the crest line detection is based on estimating the curvature tensor and curvature derivatives via local polynomial fitting.Since the crest lines are not defined in the surface regions where the surface focal set (caustic) degenerates, we introduce a new thresholding scheme which exploits interesting relationships between curvature extrema, the so-called MVS functional of Moreton and Sequin, and Dupin cyclides,An application of the crest lines to adaptive mesh simplification is also considered.

REFERENCES

• 1: Belyaev, A. G., Anoshkina, E. V., and Kunii, T. L. 1997. Ridges, ravines, and singularities. In A. T. Fomenko, and T. L. Kunii, Topological Modeling for Visualization, Springer, 375--383. Ch. 18.
• 2: Jules Bloomenthal, An implicit surface polygonizer, Graphics gems IV, Academic Press Professional, Inc., San Diego, CA, 1994
• 3: F. Cazals , M. Pouget, Estimating differential quantities using polynomial fitting of osculating jets, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 4: Cazals, F., and Pouget, M. 2004. Ridges and umbilics of a sampled smooth surface: a complete picture gearing toward topological coherence. Rapport de Recherche RR-5294, INRIA, September.
• 5: Cazals, F., and Pouget, M. 2004. Smooth surfaces, umbilics, lines of curvatures, foliations, ridges and the medial axis: a concise overview. Rapport de Recherche RR-5138, INRIA, March.
• 6: Chandru, V., Dutta, D., and Hoffmann, C. M. 1989. On the geometry of Dupin cyclides. The Visual Computer 5, 5 (October), 277--290.
• 7: Doug DeCarlo , Adam Finkelstein , Szymon Rusinkiewicz , Anthony Santella, Suggestive contours for conveying shape, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 8: Foufou, S., and Garnier, L. 2004. Dupin cyclide blends between quadric surfaces for shape modeling. Computer Graphics Forum 23, 3, 321--330. Eurographics 2004 issue.
• 9: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 10: Jack Goldfeather , Victoria Interrante, A novel cubic-order algorithm for approximating principal direction vectors, ACM Transactions on Graphics (TOG), v.23 n.1, p.45-63, January 2004 [doi>10.1145/966131.966134]
• 11: Guéziec, A. 1993. Large deformable splines, crest lines and matching. In Proc. IEEE Fourth Int'l Conf. Computer Vision, 650--657.
• 12: Gumhold, S., Wang, X., and McLeod, R. 2001. Feature extraction from point clouds. In Proc. 10th International Meshing Roundtable, 293--305.
• 13: Peter W. Hallinan , Gaile G. Gordon , A. L. Yuille , Peter Giblin , David Mumford, Two- and three-dimensional patterns of the face, A. K. Peters, Ltd., Natick, MA, 1999
• 14: Hoffman, D. D., and Richards, W. A. 1985. Parts of recognition. Cognition 18, 65--96.
• 15: M. Hosaka, Modeling of curves and surfaces in CAD/CAM, Springer-Verlag New York, Inc., New York, NY, 1992
• 16: Andreas Hubeli , Markus Gross, Multiresolution feature extraction for unstructured meshes, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 17: Victoria Interrante , Henry Fuchs , Stephen Pizer, Enhancing Transparent Skin Surfaces with Ridge and Valley Lines, Proceedings of the 6th conference on Visualization '95, p.52, October 29-November 03, 1995
• 18: Kent, J. T., Mardia, K. V., and West, J. 1996. Ridge curves and shape analysis. In The British Machine. Vision Conference 1996, 43--52.
• 19: N. Khaneja , M. I. Miller , U. Grenander, Dynamic Programming Generation of Curves on Brain Surfaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.11, p.1260-1265, November 1998 [doi>10.1109/34.730559]
• 20: Youngihn Kho , Michael Garland, User-guided simplification, Proceedings of the 2003 symposium on Interactive 3D graphics, April 27-30, 2003, Monterey, California [doi>10.1145/641480.641504]
• 21: Jan J. Koenderink, Solid shape, MIT Press, Cambridge, MA, 1990
• 22: Lee, Y., and Lee, S. 2002. Geometric snakes for triangular meshes. Computer Graphics Forum 21, 3, 229--238. Eurographics 2002 issue.
• 23: Bruno Lévy , Sylvain Petitjean , Nicolas Ray , Jérome Maillot, Least squares conformal maps for automatic texture atlas generation, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002
• 24: Little, J. J., and Shi, P. 2001. Structural lines, TINs and DEMs. Algorithimica 30, 2, 243--263.
• 25: Nelson Max, Weights for computing vertex normals from facet normals, Journal of Graphics Tools, v.4 n.2, p.1-6, March 1999
• 26: Monga, O., Benayoun, S., and Faugeras, O. 1992. From partial derivatives of 3-D density images to ridge lines. In Proc. CVPR'92, IEEE, 354--359.
• 27: Henry P. Moreton , Carlo H. Séquin, Functional optimization for fair surface design, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.167-176, July 1992
• 28: Yutaka Ohtake , Alexander Belyaev , Hans-Peter Seidel, Ridge-valley lines on meshes via implicit surface fitting, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 29: D. L. Page , Y. Sun , A. F. Koschan , J. Paik , M. A. Abidi, Normal vector voting: crease detection and curvature estimation on large, noisy meshes, Graphical Models, v.64 n.3/4, p.199-229, May/July 2002 [doi>10.1006/gmod.2002.0574]
• 30: Pauly, M., Keiser, R., and Gross, M. 2003. Multi-scale feature extraction on point-sampled models. Computer Graphics Forum 22, 3, 281--289. Eurographics 2003 issue.
• 31: Xavier Pennec , Nicholas Ayache , Jean-Philippe Thirion, Landmark-based registration using features identified through differential geometry, Handbook of medical imaging, Academic Press, Inc., Orlando, FL, 2000
• 32: I. R. Porteous, Ridges and umbilics of surfaces, Proceedings on Mathematics of surfaces II, p.447-458, October 1987, Cardiff, United Kingdom
• 33: Porteous, I. R. 1994. Geometric Differentiation for the Intelligence of Curves and Surfaces. Cambridge University Press, Cambridge.
• 34: Georgios Stylianou , Gerald Farin, Crest Lines for Surface Segmentation and Flattening, IEEE Transactions on Visualization and Computer Graphics, v.10 n.5, p.536-544, September 2004 [doi>10.1109/TVCG.2004.24]
• 35: Jean-Philippe Thirion, The extremal mesh and the understanding of 3D surfaces, International Journal of Computer Vision, v.19 n.2, p.115-128, Aug. 1996 [doi>10.1007/BF00055800]
• 36: Yoshizawa, S. www.mpisb.mpg.de/~shin/Research/Crests/Crests.html.