“Ridge-valley lines on meshes via implicit surface fitting” by Ohtake, Belyaev and Seidel

  • ©Yutaka Ohtake, Alexander Belyaev, and Hans-Peter Seidel




    Ridge-valley lines on meshes via implicit surface fitting



    We propose a simple and effective method for detecting view-and scale-independent ridge-valley lines defined via first- and second-order curvature derivatives on shapes approximated by dense triangle meshes. A high-quality estimation of high-order surface derivatives is achieved by combining multi-level implicit surface fitting and finite difference approximations. We demonstrate that the ridges and valleys are geometrically and perceptually salient surface features, and, therefore, can be potentially used for shape recognition, coding, and quality evaluation purposes.


    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. Chapter 18.Google Scholar
    2. CARR, J. C., BEATSON, R. K., CHERRIE, J. B., MITCHELL, T. J., FRIGHT, W. R., MCCALLUM, B. C., AND EVANS, T. R. 2001. Reconstruction and representation of 3D objects with radial basis functions. In Proc. ACM SIGGRAPH 2001, 67–76. Google ScholarDigital Library
    3. CAZALS, F., AND POUGET, M. 2003. Estimating differential quantities using polynomial fitting of osculating jets. In Symposium on Geometry Processing, 177–187. Google ScholarDigital Library
    4. COHEN-STEINER, D., AND MORVAN, J.-M. 2003. Restricted Delaunay triangulations and normal cycle. In Proc. 19th ACM Symp. on Comput. Geom., 312–321. Google ScholarDigital Library
    5. DECARLO, D., FINKELSTEIN, A., RUSINKIEWICZ, S., AND SANTELLA, A. 2003. Suggestive contours for conveying shape. ACM Trans. on Graphics 22, 3, 848–855. Proc. ACM SIGGRAPH 2003. Google ScholarDigital Library
    6. FLOATER, M. S., AND ISKE, A. 1996. Multistep scattered data interpolation using compactly supported radial basis functions. J. Comput. Applied Math. 73, 65–78. Google ScholarDigital Library
    7. GOLDFEATHER, J., AND INTERRANTE, V. 2004. A novel cubic-order algorithm for approximating principal direction vectors. ACM Trans. on Graphics 23, 1, 45–63. Google ScholarDigital Library
    8. GRENADER, U., AND MILLER, M. I. 1998. Computational anatomy: An emerging discipline. Quarterly of Applied Mathematics 56, 4, 617–694. Google ScholarDigital Library
    9. GUMHOLD, S., WANG, X., AND MCLEOD, R. 2001. Feature extraction from point clouds. In Proc. 10th International Meshing Roundtable, 293–305.Google Scholar
    10. HALLINAN, P. L., GORDON, G. G., YUILLE, A. L., GIBLIN, P., AND MUMFORD, D. 1999. Two- and Three-Dimensional Patterns of the Face. A K Peters. Google ScholarDigital Library
    11. HOSAKA, M. 1992. Modeling of Curves and Surfaces in CAD/CAM. Springer, Berlin. Google ScholarDigital Library
    12. HUBELI, A., AND GROSS, M. 2001. Multiresolution feature extraction from unstructured meshes. In Proc. IEEE Visualization 2001, 287–294. Google ScholarDigital Library
    13. ISKE, A., AND LEVESLEY, J. 2002. Multilevel scattered data approximation by adaptive domain decomposition. Tech. Rep. TUM-M0208, Technische Universität München.Google Scholar
    14. KENT, J. T., MARDIA, K. V., AND WEST, J. 1996. Ridge curves and shape analysis. In The British Machine Vision Conference 1996, 43–52.Google ScholarCross Ref
    15. KOENDERINK, J. J. 1990. Solid Shape. MIT Press. Google ScholarDigital Library
    16. LITTLE, J. J., AND SHI, P. 2001. Structural lines, TINs and DEMs. Algorithmica 30, 2, 243–263.Google ScholarDigital Library
    17. LÓPEZ, A. M., F. LUMBRERAS, F., AND SERRAT, J. 1998. Creaseness from level set extrinsic curvature. In Proc. ECCV’98, Springer, 156–169. Google ScholarDigital Library
    18. MA, K.-L., AND INTERRANTE, V. 1997. Extracting feature lines from 3D unstructured grids. In Proc. IEEE Visualization 1997, 285–292. Google ScholarDigital Library
    19. MALLAT, S., AND ZHONG, S. 1992. Characterization of signals from multiscale edges. IEEE Trans. Pattern Anal. Mach. Intell. 4, 7, 710–732. Google ScholarDigital Library
    20. MEYER, M., DESBRUN, M., SCHRÖDER, P., AND BARR, A. H. 2003. Discrete differential-geometry operators for triangulated 2-manifolds. In Visualization and Mathematics III, Springer, H.-C. Hege and K. Polthier, Eds., 35–58.Google Scholar
    21. 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.Google ScholarCross Ref
    22. OHTAKE, Y., BELYAEV, A., ALEXA, M., TURK, G., AND SEIDEL, H.-P. 2003. Multi-level partition of unity implicits. ACM Trans. on Graphics 22, 3, 463–470. Proc. ACM SIGGRAPH 2003. Google ScholarDigital Library
    23. OHTAKE, Y., BELYAEV, A. G., AND SEIDEL, H.-P. 2003. A multi-scale approach to 3D scattered data interpolation with compactly supported basis functions. In Shape Modeling International 2003, 153–161. Google ScholarDigital Library
    24. PAGE, D. L., SUN, Y., KOSCHAN, A., PAIK, J., AND ABIDI, M. 2002. Normal vector voting: Crease detection and curvature estimation on large, noisy meshes. Journal of Graphical Models 64, 1–31. Google ScholarDigital Library
    25. 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.Google ScholarCross Ref
    26. PENNEC, X., AYACHE, N., AND THIRION, J. P. 2000. Landmark-based registration using features identified through differential geometry. In Handbook of Medical Imaging, I. N. Bankman, Ed. Academic Press, 499–513. Google ScholarDigital Library
    27. PORTEOUS, I. R. 1994. Geometric Differentiation for the Intelligence of Curves and Surfaces. Cambridge University Press, Cambridge.Google Scholar
    28. STYLIANOU, G., AND FARIN, G. 2003. Crest lines extraction from 3D triangulated meshes. In Hierarchical and Geometrical Methods in Scientific Visualization, Springer, G. Farin, B. Hamann, and H. Hagen, Eds., 269–281.Google Scholar
    29. WATANABE, K., AND BELYAEV, A. G. 2001. Detection of salient curvature features on polygonal surfaces. Computer Graphics Forum 20, 3, 385–392. Eurographics 2001 issue.Google ScholarCross Ref

ACM Digital Library Publication: