Last update: August 5, 2004

BACK

References in Computational Geometry by

• Curve and surface reconstruction, 2004.
• Sampling and meshing a surface with guaranteed topology and geometry, 2004.
• Quality meshing for polyhedra with small angles, 2004.
• Provable surface reconstruction from noisy samples, 2004.
• Tight Cocone: A water-tight surface reconstructor, 2003.
• Approximating medial axis for CAD models, 2003.
• Approximating medial axis from the Voronoi diagram with convergence guarantee, 2002 & 2004.
• Approximate medial axis as a Voronoi subcomplex, 2002 & 2004.
• Detecting Undersampling in Surface Reconstruction, 2001 & 2003.
• Delaunay based shape reconstruction from large data, 2001.

BibTeX references

Web links:

• At engineering-shop.com

The problem of reconstructing a shape from its sample appears in many scientific and engineering applications. Because of the variety in shapes and applications, many algorithms have been proposed over the last two decades, some of which exploit application-specific information and some of which are more general. We will concentrate on techniques that apply to the general setting and have proved to provide some guarantees on the quality of reconstruction.

This paper presents an algorithm for sampling and triangulating a smooth surface in R3 where the triangulation is homeomorphic to the surface. The only assumption we make is that the input surface representation is amenable to certain types of computations, namely computations of the intersection points of a line with the surface, computations of the critical points of some height functions defined on the surface and its restriction to a plane, and computations of some silhouette points. The algorithm ensures bounded aspect ratio, size optimality, and smoothness of the output triangulation. Unlike previous algorithms, this algorithm does not need to compute the local feature size for generating the sample points which was a major bottleneck. Experiments show the usefulness of the algorithm in remeshing and meshing CAD surfaces that are piecewise smooth.

We present an algorithm to compute a Delaunay mesh conforming to a polyhedron possibly with small input angles. The radius-edge ratio of most output tetrahedra are bounded by a constant, except possibly those that are provably close to small angles. Further, the mesh is graded, that is, edge lengths are at least a constant fraction of the local feature sizes at the edge endpoints. Unlike a previous algorithm, this algorithm is simple to implement as it avoids computing local feature sizes and protective zones explicitly. Our experimental results confirm our claims and show that few skinny tetrahedra remain.

We present an algorithm for surface reconstruction in presence of noise. We show that, under a reasonable noise model, the algorithm has theoretical guarantees. Actual performance of the algorithm is illustrated by our experimental results.

Cocone softwares.

Surface reconstruction from unorganized sample points is an important problem in computer graphics, computer aided design, medical imaging and solid modeling. Recently a few algorithms have been developed that have theoretical guarantee of computing a topologically correct and geometrically close surface under certain condition on sampling density. Unfortunately, this sampling condition is not always met in practice due to noise, non-smoothness or simply due to inadequate sampling. This leads to undesired holes and other artifacts in the output surface. Certain CAD applications such as creating a prototype from a model boundary require a water-tight surface, i.e., no hole should be allowed in the surface. In this paper we describe a simple algorithm called Tight Cocone that works on an initial mesh generated by a popular surface reconstruction algorithm and fills up all holes to output a water-tight surface. In doing so, it does not introduce any extra points and produces a triangulated surface interpolating the input sample points. In support of our method we present experimental results with a number of difficult data sets.

Summary

After reconstruction with undersampling detection we are sometimes left with small holes. We stitch these holes with Delaunay triangles. We get almost 'perfect' reconstruction in many cases. This produces a Water Tight model no matter how the input is (implemented by Samrat Goswami). It also computes the medial axis (implemented by Wulue Zhao).

NB: Even after undersampling detection, some extra (wrong) triangles may be left; this occurs where the undersampling is not local (e.g., where two different surface patches come into the same vicinity, like for a closely tied knot tubular shape).

Good sample point: its incident surface triangles form a toplogical disk, called umbrella, U_p.

Other points are called poor.

Each umbrella locally separates tetrahedra incident to p into 2 clusters, one on each side.

Marking step:

Inner and outer tetrahedra incident to good points are marked as in and out via a propagation step starting from "infinite" tetrahedra associated with samples part of the convex hull of the point cloud.

We are left with a small set of (often isolated) poor tetrahedra (i.e., with poor points as vertices only). These are carefully labelled as in or out (in small ones tend to lie in a single undersampled region; other big poor tetrahedra can either be in or out, depending on the surrounding already labelled tetrahedra; in particular in ones should be reached through their smallest triangle face, as only out tetrahedra are discarded).

Peeling:

A "walk" is initiated to peel off out tetrahedra and some of the poor ones.

Web links:

• http://www.cse.ohio-state.edu/~tamaldey/medialaxis_CADobject.htm
• ACM portal

Several research have pointed out the potential use of the medial axis in various geometric modeling applications. The computation of the medial axis for a three dimensional shape often becomes the major bottleneck in these applications. Towards this end, in a recent work, we suggested an efficient algorithm that approximates the medial axis of a shape from a point sample. The input to this algorithm is only the coordinates of the sample points. As a result the approximation quality is limited by the input sample density. However, in geometric applications involving CAD models, the surfaces from which samples need to be derived are known. In this paper we present heuristics to take advantage of this a priori knowledge in our medial axis approximation algorithm. The quality of the approximation achieved by the method is surprisingly high as our experimental results exhibit.

Summary:

In geometric applications involving CAD models, the surfaces from which samples need to be derived are known. We extended our medial axis algorithm to 3D CAD objects by first sampling the CAD surfaces appropriately and then modifying the original algorithm.

NB: They use the known surface of the object and knowledge about ridges and corners, to fix the approximate MA produced by their other algorithm (below).

Web link

Web link

Medial axis as a compact representation of shapes has evolved as an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to approximate them. One line of research considers the point cloud representation of the boundary surface of a solid and then attempts to compute an approximate medial axis from this point sample. It is known that the Voronoi vertices converge to the medial axis for a curve in 2D as the sample density approaches infinity. Unfortunately, the same is not true in 3D. Recently, it is discovered that a subset of Voronoi vertices called poles converge to the medial axis in 3D. However, in practice, a continuous approximation as opposed to a discrete one is sought. Recently few algorithms have been proposed which use the Voronoi diagram and its derivatives to compute this continuous approximation. These algorithms are scale or density dependent. Most of them do not have convergence guarantees, and one of them computes it indirectly from the power diagram of the poles. In this paper we present a new algorithm that approximates the medial axis straight from the Voronoi diagram in a scale and density independent manner with convergence guarantees. The advantage is that, unlike for others, one does not need to fine tune any parameter for this algorithm. We present extensive experimental evidences in support of our claims.

Summary

Start with the Delaunay Triangulation (DT) and remove some Delaunay edges. The resulting (subcomplex) dual Voronoi graph (made of facets, incident edges and vertices) is an approximation of the MA.

1st criterion : Angle condition:

• is the max angle a Delaunay edge makes viz a "tangent plane" to the surface at a point p.

So if a Voronoi vertex is too close to the surface, the goal is to get rid of it in the representation of the MA by using the above criterion.

Because this angle condition is not independent of the scale (here the sampling density) they introduce a 2nd criterion, the ratio condition. NB: The required value of theta gets larger with decreasing sample density.

2nd criterion: Ratio condition:

• is the min of the ratio of the distance between the pair of sources, p & q, to the circumradii of umbrella triangles.

By simple geometry, we expect that the lengths pq should be much larger than the smallest circumradii of umbrella triangles, for MA points/balls.

Web link.

Motivation for the work:

• This is provided as an alternative to the use of the power crust/shape of Amental et al. which, although it guarantess water-tight surface recnstruction, "produces many extra points in the ouput" (up to twice as many as there are input samples) and "does not produce a triangulation" as M* but rather a polygonization.

Summary:

We detect undersampling from the samples. Boundaries, regions of sharp edges, corners or high curvatures where undersampling usually takes place are detected by this algorithm. This algorithm can be used with crust or our cocone algorithm to make them robust and detect boundaries.

We adapt our cocone algorithm to handle surfaces with boundaries. The samples detected as boundary samples do not choose any triangle. The neighboring interior samples choose correct triangles for them in many cases.

Pole vector: v_p = p^+ - p

Cocone neighbors (of p): The set N_p = {q in P : C_p intersects V_q is not empty}

The radius r_p of a Voronoi cell V_p is the radius of C_p, i.e., r_p = max{|| y-p || : y in C_p}.

The height h_p of V_p is the distance to 2nd pole: || p - p^- ||.

Flatness conditions:

1. Ratio condition: r_p <= rho . h_p
    
2. Normal condition: For all q in N_p , Angle (v_p , v_q) <= alpha
    

The ratio condition imposes that the Voronoi cell V_p is long and thin in the direction of v_p (rho = 1.3 epsilon, where espilon is the weight on the minimum distance to the MA).

The normal condition requires that the direction of elongation of V_p matches with that of any sample point whose cocone neighbor is p.

It is proved that interior points are flat and that boundary points are not flat.

Web link.

Summary:

SuperCocone: We extend the cocone algorithm to handle large data in the range of million points. We avoid computing the Delaunay/Voronoi diagram of the entire point set. Instead, we divide the data into chunks using an octree subdivision and then apply cocone on each chunk. The matching of surface pieces from adjacent octree cells are obtained by a `padding mechanism' and some local properties of cocone. We have computed a surface from a data of 3.5 million points in 3hrs 18 minutes with a PIII 733Mhz, 512MB,10GB PC.

Surface reconstruction provides a powerful paradigm for modeling shapes from samples. For point cloud data with only geometric coordinates as input, Delaunay based surface reconstruction algorithms are shown to be quite effective both in theory and practice. However, a major complaint against Delaunay based methods is that they are slow and cannot handle large data. We extend the COCONE algorithm to handle supersize data. This is the first reported Delaunay based surface reconstruction algorithm that can handle data containing more than a million sample points on a modest machine.

BACK

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