» Poisson Surface Reconstruction

After scanning an object into a point cloud, we want to create a mesh from this points. There are different approaches for creating a mesh, for example:

Because we want to get a watertight and smooth surface we decided to use the “Poisson Surface Reconstruction”. This approach was introduced by Michael Kazhdan and is used for example in the mesh processing software “MeshLab” as well as in the CGAL (Computational Geometry Algorithms Library). Since there is also an implementation from Kazhdan available (which is by the way also used in Meshlab) we used his code in our framework via a wrapper class.

How it works

Normals extrapolation
Picture 1: Extrapolate the normals

Extract the Surface (from: http://www.cs.jhu.edu/~misha/MyPapers/SGP06.pdf)
Picture 2: Extracting the iso surface
Source: “Poisson Surface Reconstruction”,Kazhdan et.al. SIGGRAPH 2006

Marching Cubes (from: http://www.cs.jhu.edu/~misha/MyPapers/SGP07a.pdf)
Picture 3: Extraction of the Surface using “Marching Cubes”
Source: “Unconstrained Isosurface Extraction on Arbitrary Octrees”,Kazhdan et.al. SIGGRAPH 2007

At first we need oriented normals for all of the points included in the scanned point cloud.
Therefor we use the “vcglib” that provides a nice algorithm for the extrapolation of the normals. The algorithm itself can be found in the file “normal_extrapolation.h” located in the folder “\vcglib\vcg\space”.
The algorithm requires 3 steps:

Or in other words: the algorithm computes the normals as a weighted product over the k-nearest neighbors. So we get a very smooth model. In picture 1 we will try to illustrate this, where the red marked normal is computed using the six nearest neighbors of it.
Assuming that the scanned points form the surface of the scanned object, the isosurface of the model is approximated from the normalfield that is in relation to the gradient of the indicator function describing the isosurface.
This problem is considered as the solution of a poisson problem.

Picture 2 illustrates this approach for an 2D example:

At first the points with the oriented normals are taken and the gradient of the indicator function is approximated through the normalfield. After that the indicator function, which is zero everywhere except near the surface, is derived from this gradient and the surface of the object can be extracted.

For this extraction the “marching cubes algorithm” is used to build an octree data structure for the representation of the surface. As seen in picture 3 the marching cubes algorithm devides the point cloud into a voxel grid by marching through the point cloud and analyzing which points define the isosurface of our object. By detecting which egdes of the voxel are intersected by the model’s isosurface the algorithm creates the triangles of the mesh.

For further information take a look at “Unconstrained Isosurface Extraction on Arbitrary Octrees” from Michael Kahzdan or “Polygonising a scalar field” written by Paul Bourke.

The Poisson Surface Reconstruction Parameters

There are several parameters available that affect the result of the remeshing: (see also here)

Especially the parameters depth and samples per node have a great influence on the generated mesh.

Comparison between different parametersets

After the mode of operation of the parameters was discussed we will now have a look on an example. For the comparison of some parameter sets the point cloud “CrokToy” was chosen. This file can be found in the Data/PointClouds directory as PLY file. Of course you can also find it in our 3D-Gallery!

CrokToy
File: CrokToy_2011_07_02_15_36_11_bin.ply
Points: 89326
CrokToy Pointcloud

By using the “-PoissonBench” parameter the app for creating reconstructed meshes with lots of different parameter sets gets started. Warning: before you start this application have a look into the code and be sure you are just using the parameters you want to analyze! If you use all available parameter combinations the remeshing process for all the models can take some minutes.

For a short comparison of the effects of the depth value, the amount of samples per node and the effect of the offset parameter the following images should give you an overview:

Let’s start with the default values of depth, samples per node and offset after reducing the cloud with the voxel-grid algorithm:

Depth: 8, SpN: 1, Offset: 1 – Vertices: 24899 Faces: 49794 Depth: 6, SpN: 1, Offset: 1 – Vertices: 6275, Faces: 12546
CrokToy depth 8, spn 1, off 1 CrokToy depth 6, spn 1, off 1

By reducing the depth value to 6 you get a model with less detail but a smoother surface. Since we have noisy data this effect is welcome.

A fast computed result with an acceptable level of detail and a nicely shaped smooth surface is produced by using a depth value of only 6.

Now by increasing the value for the samples per node (with a constant depth value of 6 and offset 1) you can see that the surface gets even smoother:

Depth: 6, SpN: 1, Offset: 1 – Vertices: 6275, Faces: 12546 Depth: 6, SpN: 5, Offset: 1 – Vertices: 6322, Faces: 12640
CrokToy depth 6, spn 1, off 1 CrokToy depth 6, spn 5, off 1
Depth: 6, SpN: 15, Offset: 1 – Vertices: 5833, Faces: 11662 Depth: 6, SpN: 20, Offset: 1 – Vertices: 5258, Faces: 10512
CrokToy depth 6, spn 1, off 1 CrokToy depth 6, spn 5, off 1

Considering the noisy data we get from our kinect scans a samples per node value between 15 and 20 seems good.

The effect of the offset can be seen cleary at this three pictures (depth constant at 6, samples per node: 5):

An offset value 1 keeps the surface as it is:

Depth: 6, SpN: 5, Offset: 1 – Vertices: 6322, Faces: 12640
CrokToy depth 6, spn 5, off 1, sideview

Increasing the value to 1.5 let the surfaces tend to move away from the center. On the other hand an offset value of 0.5 let the surfaces move to the inside (towards the center):

Depth: 6, SpN: 1, Offset: 1.5 – Vertices: 6268, Faces: 12532 Depth: 6, SpN: 5, Offset: 0.5 – Vertices: 6684, Faces: 13341
CrokToy depth 6, spn 1, off 1 CrokToy depth 6, spn 5, off 1

Easy to recognize that an offset value of 1 is the best choice in this case.


Further reading and sources


Michael Kazhdan – Poisson Surface Reconstruction (http://www.cs.jhu.edu/~misha/MyPapers/SGP06.pdf, Code: http://www.cs.jhu.edu/~misha/Code/PoissonRecon/)

Michael Kazhdan – Unconstrained Isosurface Extraction on Arbitrary Octrees (http://www.cs.jhu.edu/~misha/MyPapers/SGP07a.pdf)

Paul Bourke – Polygonising a scalar field (http://paulbourke.net/geometry/polygonise/

T.S. Newman, H. Yi – Computers & Graphics 30 (2006) (Marching Cubes) (http://www.proxyarch.com/util/techpapers/papers/survey%20of%20marching%20cubes.pdf)