On Sampling and Reconstructing Surfaces with Boundaries

Abstract

Summary

Definition 1 (Correctness of the Surface Reconstruction): The reconstructed surface is said to be correct if it is topologically equivalent and geometrically close (w.r.t a given error bound) to the original surface.

Definition 2 (Valid Surface): Any non-self-intersecting compact two manifold with or without boundary is considered a valid surface, denoted M. A small geometric perturbation of M is denoted M' (same topology).

NB(ffl): 3 constraints:

1. Non-self-intersecting (e.g., thus not a medial axis (MA) type)
2. Compact
3. Two manifold
   

Definition 3 (Valid Sampling Condition): Requires a non-empty set of samples to reconstruct a valid surface correctly.

Definition (Boundary Size): Maximum distance between sample points on the boundary of the surface M (with boundary), for which the (given) algorithm will correctly reconstruct the boundary.

Examples: (a) For Amenta et al.'s Voronoi Filtering, the boundary size is prescribed as the smallest feature size (distance to MA) of all boundary points. (b) For the Alpha Shapes, the boundary size is the minimal value of alpha such that the algorithm cannot reconstruct a topologically correct and geometrically close surface.

Definition 5 (Finiteness of sampling): A sampling condition is said to satisfy the finiteness property if there exists a finite set of points that samples M or M' and satisfies the sampling condition.

NB(ffl): By considering either M or M' as the target reconstruction, Gopi is avoiding issues of sharp (non-smooth) features (corners, ridges) which may require infinite sampling near such features (i.e., a small geometric perturbation removes the non-smoothness). In particular this ensures the MA is not required to touch (reach) M', which makes Amenta et al.'s sampling criterion still useful (always finite in practice). Of course, depending on how close the MA may reach M' or how much perturbation we permit, this may still prove an impractical sampling condition.

Assumptions:

A Fast and Efficient Projection Based Approach for Surface Reconstruction

We present a fast and memory efficient algorithm that generates a manifold triangular mesh S passing through a set of unorganized points P in R³. Nothing is assumed about the geometry, topology or presence of boundaries in the data set except that P is sampled from a real manifold surface. The speed of our algorithm is derived from a projection-based approach we use to determine the incident faces on a point. Our algorithm has successfully reconstructed the surfaces of unorganized point clouds of sizes varying from 10,000 to 100,000 in about 3-30 seconds on a 250 MHz, R10000 SGI Onyx2. Our technique is especially suitable for height fields like terrain and range scan data even in the presence of noise. We have successfully generated meshes for scan data of size 900,000 points in less than 40 seconds.

Theory and Practice of Sampling and Reconstruction for Manifolds with Boundaries

Surface Reconstruction based on Lower Dimensional Localized Delaunay Triangulation

We present a fast, memory efficient algorithm that generates a manifold triangular mesh S passing through a set of unorganized points P in R³. Nothing is assumed about the geometry, topology or presence of boundaries in the data set except that P is sampled from a real manifold surface. The speed of our algorithm is derived from a projection-based approach we use to determine the incident faces on a point. We define our sampling criteria to sample the surface and guarantee a topologically correct mesh after surface reconstruction for such a sampled surface. We also present a new algorithm to find the normal at a vertex, when the surface is sampled according our given criteria. We also present results of our surface reconstruction using our algorithm on unorganized point clouds of various models.