Motivation: Conventionally, a surface is reconstructed from a point cloud by constructing a polygon mesh that connects the points. Instead, we would like to compute a smooth surface directly from a point cloud, which does not require us to compute a mesh. An advantage of such a mesh-independent approach is that we can use our reconstructed surface description to compare different patching approximations of the surface.

Goal of This Research: To derive an algorithm for constructing a smooth, mesh-independent interpolating or approximating surface from a given point cloud.

Goal of This Paper: A fundamental idea in differential geometry is that at each point on a smooth surface, we can describe the surface locally as a function over a coordinate system defined around that point. Using this theme, this paper introduces the moving least-squares (MLS) projection for surface approximation. Given a point cloud, the MLS projection first computes local coordinate system and then a local polynomial approximation for the projection of each point. The output surface is described by an implicit equation, as the set of all fixed points of the MLS projection operator defined in the paper.

Related Work: For interpolating or approximating functions using point clouds, extensive work has been done. Some methods create meshes representing the desired surface, while others give meshless approximations such as polynomial approximation, radial basis function approximations, and moving least-squares approximations. For surface approximation, it is hard to treat the problem the same way as for functions, since we cannot easily find a global parametric domain for the surface. So conventional solutions will find a mesh fitting the data, break up the mesh into local parameter domains, and then fit a surface to each local domain.

Results: The MLS projection is useful in computer graphics for visualizing and simplifying point-sampled surfaces. A challenge which remains is to find better projection operators than the one presented in this paper, if one exists.

Motivation: Same as in the above paper, except we are also interested in manipulating and exploiting the density of sample points in a given point cloud.

Goal of This Research: We would like to use point clouds and the MLS projection to represent shapes. But we would like to control the density of sample points in different regions and would like to speed up rendering of shapes.

Goal of This Paper: This paper describes the MLS projection, introduced in the above paper, a shape representation method which aims to minimize the geometric error of approximation. This paper goes a step further and describes how to downsample regions where there are too many sample points, and upsample regions with too few points, to create a representative point set, which is typically much smaller than the input point cloud. Then to render the MLS surface, we usually need to sample more points, and so we sample the polynomials associated with the points on the MLS surface to get these additional points. The paper picks the sampling density so that if the view changes slightly, we do not need to do any major resampling. The size of a point is also allowed to change as the view changes.

Related Work: Work has been done in the following areas:

1. Dealing with error from range scanners by scanning from different positions to get a thick point cloud
2. Algorithms for triangulating thick point clouds, but these methods often create rough, bumpy non-manifold surfaces that may have holes and tunnels, all of which are undesirable features; thus, some smoothing and manifold conversion work has been done
3. Consolidation is the process of "massaging" and point cloud into a surface. Some methods consolidate using an implicit representation based on a signed distance function; examples are Hoppe et al, Curless and Levoy, and Wheeler et al. These sign-distance techniques are part of the field of computer graphics now known as Volume Graphics. Other consolidation techniques include triangulation and averaging overlapping areas, as done by Turk and Levoy, or the opposite technique of first averaging and then triangulating.
4. Surface fitting is another way to define surfaces from point clouds. Examples are fitting polynomials or algebraic surfaces to the data. Krishnamurthy and Levoy have a semi-automatic way of fitting smooth surfaces to polygon meshes created by the technique of Curless and Levoy. Other algorithms do high-level model recognition in addition to fitting.
5. Sampling and resampling surfaces has been studied in many ways. Surface simplification algorithms sample surfaces in ways to optimize rendering performance. An example is the physically-based particle simulation technique of Turk. Related approaches use similar particle systems to sample an implicit surface, some of which are sensitive to curvature, so that regions with more variation (which tend to be important "features") are sampled more densely.
6. The moving-least squares approach has been used earlier in surface reconstruction, but requires more iterations than what is proposed in this paper.
7. The use of point clouds for representation of shapes for rendering was pioneered in Levoy and Whitted. Work done on converting geometric models into point clouds and rendering point clouds has addressed issues such as the sampling rate during conversion, handling gaps in images, visibility data, texture filtering, shading, representing high-resolution models, local and global illumination, and dealing with the limited resolution of point clouds in general (since they just consist of a bunch of points).

Results: Highlights, silhouettes, and normals are smoother than in standard Gouraud shading, so boundaries and reflections have less distortions. The frame rates (i.e. number of times we can recompute the image per unit time) that can be achieved are dependent mainly on how many points are visible in a particular set of views.

Motivation: An important task in reverse engineering is to organize an unstructured point cloud into some structure such as a triangulation.

Goal of This Research: To find a meshless parameterization of an unstructured point cloud. A meshless parameterization is simply a parameterization which does not depend on any topological structure of the point cloud.

Goal of This Paper: This paper presents a way to triangulate a point cloud which is assumed to be sampled from a single surface patch. A surface patch is any set that is homeomorphic to a disc in the plane. Now, the basic idea is to map from the point cloud into a convex parameter domain in the plane (a meshless parameterization), then triangulate the parameter domain (for example, use the Delaunay triangulation), and map back to the point cloud to obtain a triangulation of the point cloud.

The two basic steps in the algorithm are:

1. Map the points on the boundary of the point cloud to the boundary of some convex polygon D in the plane.
2. For each of the remaining interior points in the point cloud, we compute a neighborhood and weights for points in the neighborhood, so that the point in question is a convex combination of points in its neighborhood weighted by the chosen weights. This yields a system of linear equations which can be solved to find the interior points in the plane corresponding to the interior points in the point cloud. Three methods are presented for choosing these neighborhoods and weights.

Related Work: Much work has been done on parameterizing organized point sets, but we are interested in organizing unorganized point sets. Methods for triangulating unorganized point clouds include:

1. Successive removal of tetrahedra from a Delaunay triangulation of the point cloud, as done by Boissonnat and Isselhard, Brunnett, and Schreiber.
2. Methods based on the Voronoi diagram of the point cloud, as done by Amenta et al and Schreiber and Brunnett.
3. Implicit methods for generating triangulations, as done by Hoppe et al and Bajaj, Bernardini, and Xu.

Results: Of the three methods presented for choosing neighborhoods and weights, Method 2 appears to be simple, fast, and robust, but Method 3 yields better triangulations for dense samplings, even though it is more expensive.

The Delaunay triangulation can probably be modified into more useful triangulations which depend more on the geometry of the original data. Also, note that meshless parameterization can be used for interpolating or approximating point clouds with smoother parametric surfaces such as radial basis functions, splines over the domain triangulation, or B-spline surfaces.