[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/1064092.1064126acmconferencesArticle/Chapter ViewAbstractPublication PagessocgConference Proceedingsconference-collections
Article

Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based surface reconstruction

Published: 06 June 2005 Publication History

Abstract

The distance function to surfaces in three dimensions plays a key role in many geometric modeling applications such as medial axis approximations, surface reconstructions, offset computations, feature extractions and others. In most cases, the distance function induced by the surface is approximated by a discrete distance function induced by a discrete sample of the surface. The critical points of the distance function determine the topology of the set inducing the function. However, no earlier theoretical result has linked the critical points of the distance to a sampling of geometric structures to their topological properties. We provide this link by showing that the critical points of the distance function induced by a discrete sample of a surface either lie very close to the surface or near its medial axis and this closeness is quantified with the sampling density. Based on this result, we provide a new flow-complex-based surface reconstruction algorithm that, given a tight ε-sampling of a surface, approximates the surface geometrically, both in Hausdorff distance and normals, and captures its topology.

References

[1]
N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. Discr. Comput. Geom., 22 pp. 481--504,(1999).
[2]
N. Amenta, M. Bern and D. Eppstein. The crust and the beta-skeleton: combinatorial curve reconstruction. Graphical Models and Image Processing, 60 pp. 125--135 (1998).
[3]
N. Amenta, S. Chi, T. K. Dey and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. J. Comput. Geom. & Applications, vol.12, 2002, pages 125--141.
[4]
N. Amenta, S. Choi and R. Kolluri. The power crust, unions of balls,and the medial axis transform. Computational Geometry: Theory and Applications, 19 pp. 127--153,(2001).
[5]
J. D. Boissonnat and F. Cazals. Smooth Surface Reconstruction via Natural Neighbour Interpolation of Distance Functions. Computational Geometry: Theory and Applications, 22 pp. 185--203,(2002).
[6]
R. Chaine. A geometric convection approach f 3-D reconstruction. In Proc.Eurographics Sympos. on Geometry Processing, pp. 218--229,(2003).
[7]
T. K. Dey, J. Giesen and S. Goswami. Shape Segmentation and Matching with Flow Discretization. In Proc.8th Workshop on Algorithms Data Strucutres, pp. 25--36,(2003).
[8]
T. K. Dey, J. Giesen, S. Goswami and W. Zhao. Shape dimension and approximation from samples. Discr. Comput. Geom., 29 pp. 419--434 (2003).
[9]
T. K. Dey and W. Zhao. Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee. Algorithmica, 38 pp. 179--200 (2004).
[10]
H. Edelsbrunner. Surface reconstruction by wrapping finite point sets in space. Discr. Comput. Geom., 32 pp.231--244,(2004).
[11]
J. Giesen and M. John. The Flow Complex: A Data Structure for Geometric Modeling. In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 285--294,(2003)
[12]
K. Grove. Critical Point Theory for Distance Functions. In Proceedings of Symposia in Pure Mathematics 54 3),pp. 357--385,(1993)

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SCG '05: Proceedings of the twenty-first annual symposium on Computational geometry
June 2005
398 pages
ISBN:1581139918
DOI:10.1145/1064092
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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2005

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SoCG05

Acceptance Rates

SCG '05 Paper Acceptance Rate 41 of 141 submissions, 29%;
Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)1
Reflects downloads up to 11 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2018)Density of Local Maxima of the Distance Function to a Set of Points in the PlaneResearch in Computational Topology10.1007/978-3-319-89593-2_7(115-123)Online publication date: 31-Jul-2018
  • (2017)Sclow PlotsComputer Graphics Forum10.1111/cgf.1317536:3(145-155)Online publication date: 1-Jun-2017
  • (2014)Flow-complex-based shape reconstruction from 3D curvesACM Transactions on Graphics10.1145/256032833:2(1-15)Online publication date: 8-Apr-2014
  • (2013)A parallel algorithm for computing the flow complexProceedings of the twenty-ninth annual symposium on Computational geometry10.1145/2462356.2462384(57-66)Online publication date: 17-Jun-2013
  • (2013)SMI 2013Computers and Graphics10.1016/j.cag.2013.05.01637:6(645-658)Online publication date: 1-Oct-2013
  • (2013)Optimal Reconstruction Might be HardDiscrete & Computational Geometry10.1007/s00454-012-9475-849:2(133-156)Online publication date: 1-Mar-2013
  • (2010)Reconstructing shapes with guarantees by unions of convex setsProceedings of the twenty-sixth annual symposium on Computational geometry10.1145/1810959.1811015(344-353)Online publication date: 13-Jun-2010
  • (2010)Optimal reconstruction might be hardProceedings of the twenty-sixth annual symposium on Computational geometry10.1145/1810959.1811014(334-343)Online publication date: 13-Jun-2010
  • (2009)A Sampling Theory for Compact Sets in Euclidean SpaceDiscrete & Computational Geometry10.5555/3115960.311606641:3(461-479)Online publication date: 1-Apr-2009
  • (2009)Manifold homotopy via the flow complexProceedings of the Symposium on Geometry Processing10.5555/1735603.1735618(1361-1370)Online publication date: 15-Jul-2009
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media