Efficient Simplification of Point-Sampled SurfacesMark Pauly Markus Gross Leif P. KobbeltETH Zürich ETH Zürich RWTH AachenAbstractIn this paper we introduce, analyze and quantitatively compare anumber of surface simplification methods for point-sampledgeometry. We have implemented incremental and hierarchicalclustering, iterative simplification, and particle simulation algo-rithms to create approximations of point-based models with lowersampling density. All these methods work directly on the pointcloud, requiring no intermediate tesselation. We show how localvariation estimation and quadric error metrics can be employed todiminish the approximation error and concentrate more samples inregions of high curvature. To compare the quality of the simplifiedsurfaces, we have designed a new method for computing numeri-cal and visual error estimates for point-sampled surfaces. Ouralgorithms are fast, easy to implement, and create high-quality sur-face approximations, clearly demonstrating the effectiveness ofpoint-based surface simplification.1 INTRODUCTIONIrregularly sampled point clouds constitute one of the canonicalinput data formats for scientific visualization. Very often such datasets result from measurements of some physical process and arecorrupted by noise and various other distortions. Point clouds canexplicitly represent surfaces, e.g. in geoscience [12], volumetric oriso-surface data, as in medical applications [8], or higher dimen-sional tensor fields, as in flow visualization [22]. For surface dataacquisition, modern 3D scanning devices are capable of producingpoint sets that contain millions of sample points [18].Reducing the complexity of such data sets is one of the key pre-processing techniques for subsequent visualization algorithms. Inour work, we present, compare and analyze algorithms for the sim-plification of point-sampled geometry.Acquisition devices typically produce a discrete point cloud thatdescribes the boundary surface of a scanned 3D object. This sam-ple set is often converted into a continuous surface representation,such as polygonal meshes or splines, for further processing. Manyof these conversion algorithms are computationally quite involved[2] and require substantial amounts of main memory. This posesgreat challenges for increasing data sizes, since most methods donot scale well with model size. We argue that effective surfacesimplification can be performed directly on the point cloud, similarto other point-based processing and visualization applications [21,1, 14]. In particular, the connectivity information of a trianglemesh, which is not inherent in the underlying geometry, can bereplaced by spatial proximity of the sample points for sufficientlydense point clouds [2]. We will demonstrate that this does not leadto a significant loss in quality of the simplified surface.To goal of point-based surface simplification can be stated asfollows: Given a surface defined by a point cloud and a targetsampling rate , find a point cloud with suchthat the distance of the corresponding surface to the originalsurface is minimal. A related problem is to find a point cloudwith minimal sampling rate given a maximum distance .In practice, finding a global optimum to the above problems isintractable. Therefore, different heuristics have been presented inthe polygonal mesh setting (see [9] for an overview) that we haveadapted and generalized to point-based surfaces:• Clustering methods split the point cloud into a number of sub-sets, each of which is replaced by one representative sample(see Section 3.1).• Iterative simplification successively collapses point pairs in apoint cloud according to a quadric error metric (Section 3.2).• Particle simulation computes new sampling positions by mov-ing particles on the point-sampled surface according to inter-particle repelling forces (Section 3.3).The choice of the right method, however, depends on the intendedapplication. Real-time applications, for instance, will put particularemphasis on efficiency and low memory footprint. Methods forcreating surface hierarchies favor specific sampling patterns (e.g.[30]), while visualization applications require accurate preserva-tion of appearance attributes, such as color or material properties.We also present a comparative analysis of the different tech-niques including aspects such as surface quality, computationaland memory overhead, and implementational issues. Surface qual-ity is evaluated using a new method for measuring the distancebetween two point set surfaces based on a point sampling approach(Section 4). The purpose of this analysis is to give potential usersof point-based surface simplification suitable guidance for choos-ing the right method for their specific application.Figure 1: Michelangelo’s David at different levels-of-detail. From left to right, 10k, 20k, 60k, 200k and 2000k points for the original model,rendered with a point splatting renderer.SPNP< P′ P′ N=ε S′SεEarlier methods for simplification of point-sampled modelshave been introduced by Alexa et al. [1] and Linsen [20]. Thesealgorithms create a simplified point cloud that is a true subset ofthe original point set, by ordering iterative point removal opera-tions according to a surface error metric. While both papers reportgood results for reducing redundancy in point sets, pure subsam-pling unnecessarily restricts potential sampling positions, whichcan lead to aliasing artefacts and uneven sampling distributions. Toalleviate these problems, the algorithms described in this paperresample the input surface and implicitly apply a low-pass filter(e.g. clustering methods perform a local averaging step to computethe cluster’s centroid).In [21], Pauly and Gross introduced a resampling strategy basedon Fourier theory. They split the model surface into a set ofpatches that are resampled individually using a spectral decompo-sition. This method directly applies signal processing theory topoint-sampled geometry, yielding a fast and versatile point clouddecimation method. Potential problems arise due to the depen-dency on the specific patch layout and difficulties in controllingthe target model size by specifying spectral error bounds.Depending on the intended application, working directly on thepoint cloud that represents the surface to be simplified offers anumber of advantages:• Apart from geometric inaccuracies, noise present in physicaldata can also lead to topological distortions, e.g.