Scale Space Meshing of Raw Data Point Set


Julie Digne   Jean-Michel Morel   Charyar Mehdi-Souzani   Claire Lartigue

PDF file (7.1 Mo)


This paper develops a scale space strategy for orienting and meshing exactly a complete raw data points sets. The scale space is based on the intrinsic heat equation, also called mean curvature motion (MCM). A simple iterative scheme implementing MCM directly on the raw points is described, and a mathematical proof of its consistency with MCM is given. Points evolved by this MCM implementation can be trivially backtracked to their initial raw position. Therefore, both the orientation and mesh of data point set obtained at a smooth scale can be transported back on the original. The gain in visual accuracy is demonstrated on archaeological objects by comparisons with other meshing methods.

Brief overview

This work is based on defining a scale-space for surface point clouds. The scale space is based on the intrinsic heat equation:

This scale space allows for the solving of two major problems, the point set orientation problem and the meshing problem in a manner that is specially suited with high precision data, since it permits to nicely preserve all details.

Some additional results: Point set orientation

Orientation in the scale space framework is straightforward: the normal orientation is propagated accross the neighborhoods on the coarse scale mesh. Finally, the orientation information is transported back to the initial point cloud.

Unoriented point set
Result of the scale space orientation. On this figure, no surface is reconstructed, points are simply given a gray value depending on the dot product of their normal with the lighting orientation.

Some additional results: Scale space meshing

Scale space meshing proceeds by meshing the smooth mesh and projecting the resulting connectivity onto the original points. The following figures show the initial meshing and the projection of the connectivity accross the scale space steps. In practice since we only need the final result, we do not need to perform all the steps of the reprojection (we go directly from the leftmost to the rightmost figure).

Meshing of the smooth mesh
Going back 1 step
Going back 2 steps
Going back 3 steps
Going back 4 steps (final result)
Meshing of the smooth mesh
Going back 1 step
Going back 2 steps
Going back 3 steps
Going back 4 steps (final result)

Comparison of the back-projected mesh with meshes obtained by Poisson Reconstruction ([Khazadan et al., 06]) and direct application of ball-pivoting algorithm ([Bernardini et al., 99]) with the same radius as for the scale space mesh

Scale space mesh
Poisson Mesh
Direct ball-pivoting mesh

Finally, the scale space orientation and scale space meshing can not only be used for high precision data, it is also capable of processing noisy data. Take the example of color clouds (the set of (r,g,b) values of a given image), it has been proven [Buades et al. 05] that their dimension is 2, so that prcocessing them as surfaces makes sense. Yet those point clouds are very noisy, they have a maximal side length of 256 and a radius 20 is needed to filter them leading to a SNR around 6. Still the algorithm is able to orient and mesh those point sets. Here the mesh is displayed in color (each point is given the color corresponding to its position in the RGB cube.


author = {Digne, Julie and Morel, Jean-Michel and Souzani, Charyar-Mehdi and Lartigue, Claire},
title = {Scale Space Meshing of Raw Data Point Sets},
journal = {Computer Graphics Forum},
year = {2011},
pages = {no--no},
doi = {10.1111/j.1467-8659.2011.01848.x},
issn = {1467-8659},
keywords = {scale space, mean curvature motion, mesh reconstruction},
publisher = {Blackwell Publishing Ltd},
url = {}