More Web Proxy on the site http://driver.im/

research-article

Tracing ridges on B-Spline surfaces

Authors:

Suraj Musuvathy,

Joon-Kyung Seong,

James DamonAuthors Info & Claims

SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

Pages 55 - 66

https://doi.org/10.1145/1629255.1629263

Published: 05 October 2009 Publication History

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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[17]

M. Hosaka. Modeling of curves and surfaces in CAD/CAM with 90 figures Symbolic computation. Springer, 1992.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[24]

J. Koenderink. Solid shape. MIT Press Cambridge, MA, USA, 1990.

Digital Library

[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.

Digital Library

[26]

J. Little and P. Shi. Structural lines, TINs, and DEMs. Algorithmica, 30(2):243--263, 2001.

Digital Library

[27]

K. Ma and V. Interrante. Extracting feature lines from 3D unstructured grids. In Visualization'97., Proceedings, pages 285--292, 1997.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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.

Digital Library

Cited By

Che WZhang XZhang YPaul JXu B(2011)Ridge extraction of a smooth 2-manifold surface based on vector fieldComputer Aided Geometric Design10.1016/j.cagd.2011.03.00528:4(215-232)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.cagd.2011.03.005
Musuvathy SCohen EDamon J(2011)Computing medial axes of generic 3D regions bounded by B-spline surfacesComputer-Aided Design10.1016/j.cad.2011.08.02343:11(1485-1495)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1016/j.cad.2011.08.023
Musuvathy SMartin TCohen E(2010)Ridge Extraction from Isosurfaces of Volumetric Data Using Implicit B-SplinesProceedings of the 2010 Shape Modeling International Conference10.1109/SMI.2010.29(163-174)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.1109/SMI.2010.29
Show More Cited By

Index Terms

Tracing ridges on B-Spline surfaces
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision problems
  2. Computer graphics
    1. Image manipulation
    2. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Principal curvature ridges and geometrically salient regions of parametric B-spline surfaces

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 ...
Semi-structured B -spline for blending two B -spline surfaces

Surface blending is a useful operation in geometric design for rounding sharp edges or corners. Meanwhile, NURBS has already become the de facto industrial standard in existing CAD/CAM systems. Therefore, it is required to study how to blend two B -...
Ridge Extraction from Isosurfaces of Volumetric Data Using Implicit B-Splines
SMI '10: Proceedings of the 2010 Shape Modeling International Conference

Ridges are extremal curves of principal curvatures on a surface that indicate salient intrinsic features of its shape. This paper presents a novel approach for extracting ridges of improved quality from isosurfaces of volumetric scalar-valued grids by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SPM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

October 2009

380 pages

ISBN:9781605587110

DOI:10.1145/1629255

Conference Chair:
Wim Bronsvoort
Delft University of Technology, The Netherlands
,
General Chairs:
Daniel Gonsor
The Boeing Company
,
William Regli
Drexel University
,
Thomas Grandine
The Boeing Company
,
Jan Vandenbrande
The Boeing Company
,
Program Chairs:
Jens Gravesen
Technical University of Denmark, Denmark
,
John Keyser
Texas A&M University

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIAM Activity Group on Geometric Design

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Computing and Communication Foundations

Conference

SIAM '09

Sponsor:

SIAM '09: 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling

October 5 - 8, 2009

California, San Francisco

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
294
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Che WZhang XZhang YPaul JXu B(2011)Ridge extraction of a smooth 2-manifold surface based on vector fieldComputer Aided Geometric Design10.1016/j.cagd.2011.03.00528:4(215-232)Online publication date: 1-May-2011
https://dl.acm.org/doi/10.1016/j.cagd.2011.03.005
Musuvathy SCohen EDamon J(2011)Computing medial axes of generic 3D regions bounded by B-spline surfacesComputer-Aided Design10.1016/j.cad.2011.08.02343:11(1485-1495)Online publication date: 1-Nov-2011
https://dl.acm.org/doi/10.1016/j.cad.2011.08.023
Musuvathy SMartin TCohen E(2010)Ridge Extraction from Isosurfaces of Volumetric Data Using Implicit B-SplinesProceedings of the 2010 Shape Modeling International Conference10.1109/SMI.2010.29(163-174)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.1109/SMI.2010.29
Musuvathy SCohen E(2009)Extracting Principal Curvature Ridges from B-Spline Surfaces with Deficient SmoothnessProceedings of the 5th International Symposium on Advances in Visual Computing: Part I10.1007/978-3-642-10331-5_10(101-110)Online publication date: 26-Nov-2009
https://dl.acm.org/doi/10.1007/978-3-642-10331-5_10

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents