Surface and Medial Axis Topology Through Distance Flows Induced by Discrete Samples

Sadri, Bardia

Permalink

https://hdl.handle.net/2142/11272 Copy

Description

Title

Surface and Medial Axis Topology Through Distance Flows Induced by Discrete Samples

Author(s)

Sadri, Bardia

Issue Date

2006-12

Keyword(s)

computer science

Abstract

The distance function induced by a surface in R^n is known to carry a great deal of topological information about the surface and its embedding in space. It is an important question, from both theoretical and practical standpoints, whether such information about a surface can be extracted from the distance function induced by a discrete sample of it. Distance functions induced by discrete samples of surfaces and their associated mathematical structures are the main focus of this dissertation. These functions lead to continuous flow maps that turn out to be powerful topological tools. Based on these flow maps we design and analyze a number of simple and natural shape and medial axis reconstruction algorithms for which we can guarantee the topological type of output. We prove that critical points of distance functions induced dense enough (relative) epsilon-samples of surfaces are concentrated around the surface and its medial axis. These two types of critical points can be distinguished from each other algorithmically. This ``separation'' of critical points is crucial to the design and analysis of of the above-mentioned algorithms. Specifically, we present an algorithm for homeomorphic reconstruction of surfaces in 3D. This algorithm generalizes to higher dimensions with a slight change in the type of the provided topological guarantee. We also present an algorithm for medial axis approximation that computes a piece-wise linear core for the given sample. This core is guaranteed to be homotopy equivalent to the medial axis of the shape enclosed by the original surface. We then show that the core can be enhanced by any geometric medial axis approximation scheme without compromising the topological equivalence of the output and the medial axis being approximated. Finally, we present an analysis of Herbert Edelsbrunner's well-known Wrap reconstruction algorithm and show that under relative epsilon-sampling in 3D, the output of Wrap is homotopy equivalent to the original shape.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11272

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections