Surface Reconstruction From Unorganized Point Sets. piyush@cs. Example Reconstruction. Surface Reconstruction Algorithm. Organization of Talk. Problem Statement Some Basic Definitions Hoppe’s Algorithm : The Beginning Alpha Shapes : Generalizations of the convex hull
Delaunay Triangulation, Voronoi Diagram[2D,3D]
The space generated by point pairs that can be touched by an
empty disc of radius alpha.
Alpha Controls the desired level of detail.
Medial Axis: of surface F is the closure of points that have more
than one closest point in F.
Local Feature Size f(p) at a point p on F is the least distance of p to
the medial axis.
S is called an r-sample of F if every point has a sample
within a distance rf(p).
The Voronoi Cells of a dense sampling are thin and long.
The Medial Axis is the extension of Voronoi Diagram for
continuous surfaces in the sense that the Voronoi Diagram
of S Can be defined as the set of points with more than one
closest point in S. (S = Sample Point Set)
The Sampling criterion of
the Crust breaks down in case
of non-smooth curves and
Input : P = Set of sample points in the plane
Output: E = Set of edges connecting points in P
Compute the Voronoi vertices of P = V
Calculate the Delaunay of (P U V)
Pick the edges (p,q) where both p,q are in P
Restricted Voronoi Cells:
Restricted Delaunay Triangles: A triangle
Here S is a surface and p is a sample point.
(What is a correct connection in 3D??)
Single Pole Computation
Cross section of the
Voronoi cell of p in
If Edge e has three such
supporting points, the
dual triangle to e is in
Near pi/2 angle