Tracing ridges on B-Spline surfaces

ABSTRACT

Ridges are characteristic curves of a surface that mark salient intrinsic features of its shape and are therefore valuable for shape matching, surface quality control, visualization and various other applications. Ridges are loci of points on a surface where either of the principal curvatures attain a critical value in its respective principal direction. These curves have complex behavior near umbilics on a surface, and may also pass through certain turning points causing added complexity for ridge computation. We present a new algorithm for numerically tracing ridges on B-Spline surfaces that also accurately captures ridge behavior at umbilics and ridge turning points. The algorithm traverses ridge segments by detecting ridge points while advancing and sliding in principal directions on a surface in a novel manner, thereby computing connected curves of ridge points. The output of the algorithm is a set of curve segments, some or all of which, may be selected for other applications such as those mentioned above. The results of our technique are validated by comparison with results from previous research and with a brute-force domain sampling technique.

REFERENCES

• 1: A. Belyaev, Y. Ohtake, and K. Abe. Detection of ridges and ravines on range images and triangular meshes. In Proceedings of SPIE, volume 4117, page 146, 2000.
• 2: A. Belyaev, A. Pasko, and T. Kunii. Ridges and ravines on implicit surfaces. In Computer Graphics International, 1998. Proceedings, pages 530--535, 1998.
• 3: I. Bogaevski, V. Lang, A. Belyaev, and T. Kunii. Color ridges on implicit polynomial surfaces. GraphiCon 2003, Moscow, Russia, 2003.
• 4: F. Cazals, J. Faugère, M. Pouget, and F. Rouillier. Topologically certified approximation of umbilics and ridges on polynomial parametric surface. 2005. INRIA Technical Report.
• 5: F. Cazals, J. Faugère, M. Pouget, and F. Rouillier. The implicit structure of ridges of a smooth parametric surface. Computer Aided Geometric Design, 23(7):582--598, 2006.
• 6: F. Cazals, J. Faugère, M. Pouget, and F. Rouillier. Ridges and umbilics of polynomial parametric surfaces. Geometric Modeling and Algebraic Geometry, pages 141--159, 2007. Jüttler, B. and Piene, R. (eds.).
• 7: F. Cazals and M. Pouget. Topology driven algorithms for ridge extraction on meshes. 2005. INRIA Technical Report.
• 8: E. Cohen, R. Riesenfeld, and G. Elber. Geometric modeling with splines: an introduction. AK Peters, Ltd., 2001.
• 9: F. Cole, A. Golovinskiy, A. Limpaecher, H. S. Barros, A. Finkelstein, T. Funkhouser, and S. Rusinkiewicz. Where do people draw lines? ACM Transactions on Graphics (Proc. SIGGRAPH), 27(3), Aug. 2008.
• 10: G. Elber. The IRIT modeling environment, version 10.0, 2008.
• 11: G. Elber and T. Grandine. Efficient solution to systems of multivariate polynomials using expression trees. In IEEE International Conference on Shape Modeling and Applications, 2008. SMI 2008, pages 163--169, 2008.
• 12: G. Elber and M. Kim. Geometric constraint solver using multivariate rational spline functions. In Proceedings of the sixth ACM symposium on Solid modeling and applications, pages 1--10. ACM New York, NY, USA, 2001.
• 13: A. Guéziec. Large deformable splines, crest lines and matching. In Computer Vision, 1993. Proceedings., Fourth International Conference on, pages 650--657, 1993.
• 14: P. Hallinan, G. Gordon, A. Yuille, P. Giblin, and D. Mumford. Two-and three-dimensional patterns of the face. AK Peters, Ltd. Natick, MA, USA, 1999.
• 15: D. Hastings, P. Dunbar, G. Elphingstone, M. Bootz, H. Murakami, H. Maruyama, H. Masaharu, P. Holland, J. Payne, N. Bryant, et al. The global land one-kilometer base elevation (GLOBE) digital elevation model. Version 1.0. National Oceanic and Atmospheric Administration, National Geophysical Data Center, Boulder, Colorado. National Geophysical Data Center, Digital data base on the World Wide Web (URL: http://www.ngdc.noaa.gov/mgg/topo/globe.html) and CD-ROMs., 1999.
• 16: K. Hildebrandt, K. Polthier, and M. Wardetzky. Smooth feature lines on surface meshes. In Symposium on geometry processing, pages 85--90, 2005.
• 17: M. Hosaka. Modeling of curves and surfaces in CAD/CAM with 90 figures Symbolic computation. Springer, 1992.
• 18: V. Interrante, H. Fuchs, and S. Pizer. Enhancing transparent skin surfaces with ridge and valley lines. In Proceedings of the 6th conference on Visualization'95. IEEE Computer Society Washington, DC, USA, 1995.
• 19: M. Jefferies. Extracting Crest Lines from B-spline Surfaces. Arizona State University, 2002.
• 20: D. Johnson and E. Cohen. An improved method for haptic tracing of sculptured surfaces. In Symp. on Haptic Interfaces, ASME International Mechanical Engineering Congress and Exposition, Anaheim, CA, 1998.
• 21: J. Kent, K. Mardia, and J. West. Ridge curves and shape analysis. In The British Machine Vision Conference 1996, pages 43--52, 1996.
• 22: S. Kim and C. Kim. Finding ridges and valleys in a discrete surface using a modified MLS approximation. Computer-Aided Design, 37(14):1533--1542, 2005.
• 23: K. Ko, T. Maekawa, N. Patrikalakis, H. Masuda, and F. Wolter. Shape intrinsic fingerprints for free-form object matching. In Proceedings of the eighth ACM symposium on Solid modeling and applications, pages 196--207. ACM New York, NY, USA, 2003.
• 24: J. Koenderink. Solid shape. MIT Press Cambridge, MA, USA, 1990.
• 25: Y. Lai, Q. Zhou, S. Hu, J. Wallner, and H. Pottmann. Robust feature classification and editing. IEEE Transactions on Visualization and Computer Graphics, 13(1):34--45, 2007.
• 26: J. Little and P. Shi. Structural lines, TINs, and DEMs. Algorithmica, 30(2):243--263, 2001.
• 27: K. Ma and V. Interrante. Extracting feature lines from 3D unstructured grids. In Visualization'97., Proceedings, pages 285--292, 1997.
• 28: T. Maekawa and N. Patrikalakis. Interrogation of differential geometry properties for design and manufacture. The Visual Computer, 10(4):216--237, 1994.
• 29: T. Maekawa, F. Wolter, and N. Patrikalakis. Umbilics and lines of curvature for shape interrogation. Computer Aided Geometric Design, 13(2):133--161, 1996.
• 30: O. Monga and S. Benayoun. Using partial derivatives of 3D images to extract typical surface features. Computer Vision and Image Understanding, 61(2):171--189, 1995.
• 31: R. Morris. Symmetry of Curves and the Geometry of Surfaces. PhD thesis, PhD thesis, University of Liverpool, 1990.
• 32: Y. Ohtake, A. Belyaev, and H. Seidel. Ridge-valley lines on meshes via implicit surface fitting. ACM Transactions on Graphics, 23(3):609--612, 2004.
• 33: B. O'Neill. Elementary differential geometry. Academic press, 2nd edition, 2006.
• 34: N. Patrikalakis and T. Maekawa. Shape interrogation for computer aided design and manufacturing. Springer, 2002.
• 35: X. Pennec, N. Ayache, and J.-P. Thirion. Landmark-based registration using features identified through differential geometry. In I. Bankman, editor, Handbook of Medical Image Processing and Analysis - New edition, chapter 34, pages 565--578. Academic Press, Dec. 2008.
• 36: I. Porteous. The normal singularities of a submanifold. Journal of Differential Geometry, 5:543--564, 1971.
• 37: I. Porteous. Geometric differentiation: for the intelligence of curves and surfaces. Cambridge University Press, 2001.
• 38: G. Stylianou and G. Farin. Crest lines extraction from 3D triangulated meshes. Hierarchical and geometrical methods in scientific visualization, pages 269--281, 2003.
• 39: G. Subsol. Crest lines for curve-based warping. Brain Warping, pages 241--262, 1999.
• 40: T. Tasdizen and R. Whitaker. Feature preserving variational smoothing of terrain data. In Proceedings of the Second IEEE Workshop on Variational, Geometric and Level Set Methods in Computer Vision (VLSM'03) (Institute of Electrical and Electronics Engineers, 2003), pages 121--128.
• 41: J. Thirion and A. Gourdon. The 3D marching lines algorithm and its application to crest lines extraction. 1992.
• 42: S. Yoshizawa, A. Belyaev, H. Yokota, and H. Seidel. Fast and faithful geometric algorithm for detecting crest lines on meshes. In Computer Graphics and Applications, 2007. PG'07. 15th Pacific Conference on, pages 231--237, 2007.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.7 Feature Measurement

Keywords:
crest, ridge