Last update: July 15, 2004

BACK

References in Computational Geometry by

Publication list: http://www.cs.ucdavis.edu/~amenta/pubs/pubs.html

Selected publications:

• Defining point-set surfaces, 2004.
• Computational Topology: Ambient Isotopic Approximation of 2-Manifolds, 2003
• Finding alpha-helices in skeletons, 2002.
• The Power Crust, Unions of Balls, and the Medial Axis Transform, 2001.
• The Medial Axis of a Union of Balls, 2000.
• Accurate and Efficient Unions of Balls, 2000.
• A simple algorithm for homeomorphic surface reconstruction, 2000 & 2002.
• Surface Reconstruction by Voronoi Filtering, 1999.
• A New Voronoi-Based Surface Reconstruction Algorithm, SIGGRAPH'98.
• The crust and the beta-skeleton: combinatorial curve reconstruction, 1998.

BibTeX references

Summary:

• It is shown that for any C^2 compact 2-manifold without boundary embedded in R^3, there exists a piecewise linear ambient isotopic approximation. The proof relies on the medial axis.

NB: Isotopy is stronger than homeomorphism; besides topology in involves a continous mapping preserving the topology.

The medial axis transform (or MAT) is a representation of an object as an infinite union of balls. We consider approximating the MAT of a three-dimensional object, and its complement, with a finite union of balls. Using this approximate MAT we define a new piecewise-linear approximation to the object surface, which we call the power crust.

We assume that we are given as input a suficiently dense sample of points from the object surface. We select a subset of the Voronoi balls of the sample, the polar balls, as the union of balls representation. We bound the geometric error of the union, and of the corresponding power crust, and show that both representations are topologically correct as well. Thus, our results provide a new algorithm for surface reconstruction from sample points. By construction, the power crust is always the boundary of a solid, so we avoid the hole-filling or manifold extraction steps used in previous algorithms.

The union of balls representation and the power crust have corresponding piecewise-linear dual representations, which in some sense approximate the medial axis. We show a geometric relationship between these duals and the medial axis by proving that, as the sampling density goes to infinity, the set of poles, the centers of the polar balls, converge to the medial axis.

Geometry

Medial Axis Transform

Let W be a closed, bounded, and C1-continuous (smooth), 2D surface in R³. W is contained in an open bounder region Q, s.t. W divides Q in interior and exterior.

A ball B(c,r) has center c and radius r; it may also be represented by a weighted point with position c and weight r². Zero (r² = 0) and negative weights (-r², where the radius is i r, i = -sqrt(1)) are also possible. A ball is empty if it contains no points of W. A medial ball is a maximal empty ball.

MAT of W == set of medial balls. The medial axis M of W == set of centers of the medial balls.

The MA is homotopy equivalent to the complement of W, i.e., Q-W.

Deformation retraction:

• of Q-W onto M: continuous motion of every point away from W towards the closest MA point.
• of Q-M onto W: continuous motion of every point away from the MA towards its closest surface point.

Power Diagrams

Power distance between 2 balls B1(c1, r1) and B2(c2, r2) : d_pow(B1, B2) = d²(c1, c2) - r1² - r2²

Power diagram, Pow(B), of a set of balls is the weighted Voronoi diagram which assigns an (unweighted) point x=B(x,0) in space to the cell of the ball which minimizes d_pow(B,x).

Weighted Delaunay triangulation, WDT(B), is the dual of the power diagram and is a regular triangulation. A face f of WDT(B) is the simplex defined by a set, Bh, of weighted points inducing a (dual) face h of Pow(B).

Intersection of balls:

• Two weighted points are said to be orthogonal if the power distance between them is zero.
• The boundaries of two balls B1 & B2 intersect in a circle, C. The balls meet with an angle a defined bewteen their tangent planes along C. Equivalently, we can consider the angle b between the normal vectors to B1 & B2 along C, and we have the identity: b = pi - a.

Lemma: Pow(Vor(S)) == DT(S)

• Let S be a set of points in R³ and let B be the set of Voronoi balls centered at the Voronoi vertices of S, i.e., B = Vor(S). Then, Pow(B) is the Delaunay triangulations DT(S).

Constructions

Poles & Power Crust

Let S be a sufficiently dense set of sample points of W.

Poles, p1 & p2 of a sample s in S are 2 vertices of its Voronoi cell farthest from s, one on either side of the surface, W. The Voronoi balls B(p1, r1) and B(p2, r2) are polar balls, with ri = d(pi,s).

Procedure to identify both poles:

1. p1 is the farthest Voronoi vertex (from W).
2. Among the remaining Voronoi vertices v of s, select the ones s.t. the angle v - s - p1 > pi/2 and pick the farthest one as p2.

The surface W is divided in two sets of poles: inside and outside poles, Pi & Po, with set of polar balls, Bi & Bo.

Let Ui & Uo be the unions of inside and outside balls Bi & Bo, and let dUi & dUo be the boundaries of these unions. Then, every sample s in S lies both on dUi and dUo.

The power crust if S is the set of faces in Pow(Bi U Bo) separating cells belonging to inside polar balls from cells belonging to outside polar balls. Every sample s lies on the power crust. The power crust is the possibly non-regular boundary of a 3D solid.

Dual shapes

Theorem: MA is homotopy equivalent to the object

• The dual shape of a union of balls is homotopy equivalent to the union.

The dual shape of a set Y of closed faces selected from Pow(B) is the union of the dual faces of every face in Pow(B) - Y. The power shape of S is the dual shape of the power crust.

Theorem: Power shape is analogous to the MA

• Let Y be a set of (d-1)-dimensional faces, together with all their subfaces, selected from Pow(B). The dual shape is homotopy equivalent to the union U(Pow(B)-Y).

The d-dimensional cells of Pow(B)-Y form a family of convex sets. The nerve of a family of convex sets is a simplicial complex, with a vertex for every convex set and a simplex connecting every subset of convex sets which have a common intersection. The Nerve Theorem (Edelsbrunner 1993) states that the nerve of a family of convex sets is homotopy equivalent to their union. The dual shape is a geometric realization of the nerve of the d-dim cells in Pow(B) - Y.

Sampling condition

Local Feature Size, at a point w in W, is the distance from w to the nearest point on the MA of W : LFS(w) = d(w, MA).

The set S included in W is an r-sample if the distance from any point w in W to its closest sample in S is at most a constant fraction r times LFS(w).

Sampling assumption : r <= 0.1

Lemma : LFS is Lispschitz

• For any 2 points p and q on W, | LFS(p) - LFS(q) | < d(p,q)

Lemma : Lipschitz condition on the surface normals w/r to LFS

• For any 2 points p and q on W with d(p,q) <= rho min{LFS(p), LFS(q)}, for any rho < 1/3, the angle between the normals to W at p and q is at most rho/(1-3rho).

Lemma : Given a sample s in S and a point v in its Voronoi region, the angle between the vector from s to v and the surface normal at s has to be small (linear in r) when v is far away from s (as a function of LFS).

• Let s be a sample point from an r-sample S, v be any point in Vor(s) s.t. d(v,s >= k LFS(s), for k > r' = r(1-r) = O(r), and let alpha be the angle between the vector sv and the surface normal n at s. Then: alpha <= arcsin(r'/k)+arcsin r'.

Intuitively, the above lemma states that when S is sufficiently dense, the Voronoi cell of every sample s in S is long and skinny and roughly prependicular to the surface.

Corollary : Conversely, if alpha is large, v has to be close to s.

• For any v s.t. alpha > arcsin r', we have d(v,s) <= k LFS(s) with : k = r' / [sin(alpha-arcsin r']

Corollary :

• Every polar ball contains a point of the MA when r < 0.35 (or when 2 arcsin r' < pi/6 ).

Union of Polar Balls

1. Under the sampling assumption, Ui and Uo are both close to W.
2. Their surface normals agree with those of W.
3. Each of them is homeomorphic to W.

Shallow intersections

Inside and outside balls cannot intersect each other deeply.

 To be continued ...

Proximity

Normals

Homeomorphism

The Power Crust

Since Ui and Uo are accurate representations of W and its somplement, the power crust that they induce is also an accurate representation of W.

Proximity

Homeomorphism

Medial Axis approximation

The power shape is a good approximation, both geometrically and topologically, to the MA.

Theoretical algorithm

The Anti-Crust

Open questions

Conjecture :

• The power crust faces are exactly those for which the two polar balls determining the face intersect in a lune of at most O(r) degrees. [See Attali's 2D surface reconstruction algorithm].

Union of Balls web link.

Introduces the notion of co-cones to select candidate (Delaunay) triangles incident at each sample point.

We give a simple combinatorial algorithm that computes a piecewise-linear approximation of a smooth surface from a finite set of sample points. The algorithm uses Voronoi vertices to remove triangles from the Delaunay triangulation. We prove the algorithm correct by showing that for densely sampled surfaces, where density depends on a local feature size function, the output is topologically valid and convergent (both pointwise and in surface normals) to the original surface. We briefly describe an implementation of the algorithm and show example outputs.

Web-links :

• http://web.mit.edu/manoli/crust/www/crust.html
• http://www.parc.xerox.com/csl/members/bern/surface.html

The Crust Algorithm is a new algorithm for the reconstruction of surfaces of arbitrary topology from unorganized sample points in 3d. The algorithm is the first one for this problem with provable guarantees. Given a "good sample" from a smooth surface, the output is guraranteed to be topologically correct and convergent to the original surface as the sampling density increases. The defintion of a good sample is itself interesting: the required sampling density varies locally, rigorously capturing the intuitive notion that featureless areas can be reconstructed from fewer samples. Our algorithm is based on the three-dimensional Voronoi diagram.

BACK

Page created & maintained by Frederic Leymarie, 2000-4.
Comments, suggestions, etc., mail to: leymarie@lems.brown.edu