Motivation: Irregularly sampled point cloud data commonly show up in scientific visualization problems. We would like to reduce the complexity of such data sets, so that visualization of the data is made easier.

Goal of This Research: Given a point cloud P sampled from a surface S, and given a target sampling rate N < |P| where |P| is the sampling rate of P, find a point cloud P' with |P'| = N such that the corresponding surface S' is as close to S as possible. This is called point-sampled surface simplification, or simply point cloud simplification.

Goal of This Paper: Present and compare three algorithms for point cloud simplification:

1. Clustering Methods. Split P into subsets, and then replace each subset with a simpler set of points. There are two types of clustering methods: incremental, where clusters are created by systematically growing small clusters into bigger ones, and hierarchical, where clusters are created by subdividing the original point cloud into smaller subsets.
2. Iterative Simplification. Repeatedly pick pairs of points and collapse them into single points. Note that each time we collapse two points, we increase the error of our sample. Thus, for all collapsings we can do, we keep an ordered list of which collapsing causes the least increase in error, which causes the second least increase, and so on. Then to minimize the error caused by this algorithm, we do the collapsing which causes the least error first, then the collapsing that causes the second least error next, and so on.
3. Particle Simulation. Randomly place the desired number of sample points on the surface. Then pretend each point is a particle that repels other particles, and move the points around until the points are distributed as desired.

Results: Incremental clustering has the highest average error, hierarchical clustering has the second highest error, particle simulation has the third highest error, and iterative simplification has the lowest error. The sampling distribution produced by a clustering method is close to the sampling distribution of the input data, which is sometimes desirable. However, particle simulation works best if uniform sampling density or local control over sampling density are desired. Clustering methods are the fastest running simplification techniques, because they are the simplest. Incremental clustering, iterative simplification, and particle simulation need extra storage that is linear in the input size, while hierarchical clustering depends only on the target model size. Also note that all three techniques operate directly on the point cloud, instead of first reconstructing the surface and then simplifying. Operating directly on the point cloud is much more efficient than first reconstructing, in theory as well as practice.

Motivation: In any problem involving free-form (i.e. flexible) geometric objects, we would like to be able to control the deformation of an object, while still being able to draw pictures of it or perform various set operations on it.

Goal of This Research: Create a framework for modeling free-form surfaces using their point clouds.

Goal of This Paper: This paper presents a good free-form shape modeling framework by combining advantages of implicit shape representations with those of parametric representations, and analyzes the quality of this framework. Implicit representations allow a simple representation of very complex surfaces and efficient set operations. But rendering and modeling of sharp features are difficult with implicit surfaces. Parametric surfaces can be quickly rendered and deformed, but complex parametric surfaces have very complex algebraic structure. This paper presents a hybrid technique for shape representation: we keep an unstructured point cloud and then use the moving least squares projection to derive an implicit representation of the surface. The point cloud essentially is a parametric definition, since we can roughly compute any point on the surface using the sample points. Thus this technique gives us the advantages of both implicit and parametric representations.

Results: This free-form shape modeling framework allows Boolean operations, which are facilitated by an implicit representation, and free-form deformations, which are most easily done with parametric representations. Also the system described in the paper can do dynamic sampling to handle large deformations, can represent, sample, and render sharp corners in point clouds, and can efficiently detect self-intersections. Yet, the system is simple and easy to implement. This work can be extended to more complex shapes and used in animation.

Motivation: Free-form (i.e. flexible) surfaces are useful for animation in computer graphics. Conventional techniques for describing free-form surfaces involve manual work, in order to split a surface into connected patches. We would like to eliminate this manual work.

Goal of This Research: To devise a new model of elastic surfaces which can split, join, or extend surfaces without manual work.

Goal of This Paper: This paper presents a model of elastic surfaces by using particles with long-range attraction and short-range repulsion, where each particle represents a part of a surface. This technique orients particles so that they model surface elements instead of points or volumes, and defines potential functions so that the particles favor either locally planar or locally spherical arrangements. This technique is essentially an extension of earlier particle systems, but is better suited for free-form surface modeling.

Results: A surface represented by a particle system can be efficiently rendered by Delaunay triangulation if it is point-sampled with respect to curvature. The simple modeling operations of adding, moving, and deleting single particles can be done efficiently. A drawback of this technique is the lack of control over the mathematical form of a surface. However this technique can still be used in a wide variety of animation and simulation applications, and can work to some extent with open or closed surfaces with arbitrary topology, including surfaces with or without holes.

Motivation: Using point clouds to represent surfaces is becoming popular. But many tasks require approximation of a continuous surface from point data.

Goal of This Research: Given a point cloud P sampled from a continuous surface S, reconstruct a continuous polynomial surface S' from P so that S' is a good approximation to S.

Goal of This Paper: This paper presents a method for approximately reconstructing surfaces from their point clouds using polynomial surfaces and iterative ray intersection. Data structures and efficient algorithms for ray-related computations are also described.

Results: For well-sampled surfaces we can reconstruct a continuously differentiable manifold.