Monday, September 7, 2009

Meshing Point Clouds

One of the most requested tasks when managing 3D scanning data is the conversion of point clouds into more practical triangular meshes. Here is a step-by-step guide for transforming a raw point cloud into a colored mesh.

Let's start from a colored point cloud (typical output of many 3D scanning devices), each point has just color and no normal information. The example dataset that we will use is a medium sized dataset of 9 millions of points. Typical issues of such a dataset dataset: it is non uniform (comes from an integration of different datasets), has some strongly biased error (alignment error, some problem during data integration), it comes without normals (hard to be shaded).

1. Subsampling

As a first step we reduce a bit the dataset in order to have amore manageable dataset. Many different options here. Having a nicely spaced subsampling is a good way to make some computation in a faster way. The Sampling->Poisson Disk Sampling filter is a good option. While it was designed to create Poisson disk samples over a mesh, it is able to also compute Poisson disk subsampling of a given point cloud (remember to check the 'subsampling' boolean flag). For the curious ones, it uses an algorithm very similar to the dart throwing paper presented at EGSR2009 (except that we have released code for such an algorith long before the publication of this article :) ). In the invisible side figure a Poisson disk subsampling of just 66k vertices.
2. Normal Reconstruction

Currently inside MeshLab the construction of normals for a point cloud is not particularly optimized (I would not apply it over 9M point cloud) so starting from smaller mesh can give better, faster results. You can use this small point cloud to issue a fast surface reconstruction (using Remeshing->Poisson surface reconstruction) and then transfer the normals of this small rough surface to the original point cloud. Obviously in this way the full point cloud will have a normal field that is by far smoother than necessary, but this is not an issue for most surface reconstruction algorithms (but it is an issue if you want to use these normals for shading!).
3. Surface reconstruction

Once rough normals are available Poisson surface reconstruction is a good choice. Using the original point cloud with the computed normals we build a surface at the highest resolution (recursion level 11). Roughly clean it removing large faces filter, and eventually simplify it a bit (remove 30% of the faces) using classical Remeshing->Quadric edge collapse simplification filter (many implicit surface filters rely on marching cube like algorithms and leave useless tiny triangles).
4. Recovering original color

Here we have two options, recovering color as a texture or recovering color as per-vertex color. Here we go for the latter, leaving the former to a next post where we will go in more details on the new automatic parametrization stuff that we are adding in MeshLab. Obviously if you store color onto vertexes you need to have a very dense mesh, more or less of the same magnitudo of the original point cloud, so probably refining large faces a bit could be useful. After refining the mesh you simply transfer the color attribute from the original point cloud to the reconstructed surface using the vertex attribute transfer filter.

5. Cleaning up and assessing

The vertex attribute transfer filter uses a simple closest point heuristic to match the points between the two meshes. As a side product it can store (in the all-purpose per-vertex scalar quality) the distance of the matching points. Now just selecting the faces having vertices whose distance is larger than a given threshold we can easily remove the redundant faces created by the Poisson Surface Reconstruction.

This pipeline is only one of the many possible way of ending up into a nice mesh. For example different choices could have been done for step 2/3. There are reconstruction algorithms that do not need surface normals, like for example the "Voronoi Filtering" that is an interpolating reconstruction algorithm (e.g. it build up only triangles on the given input points) but usually these filters works better on very clean datasets, without noise or alignment errors. Otherwise on noisy datasets it is easy that they create a lot of non manifold situations. Final thanks to Denis Pitzalis for providing me this nice dataset of a Cypriot theater.

Alexwarrior said...

Cool thanks for the tips, I ended up playing for a quite a while after reading this

Matt said...

I have 2 3D cubes. Unlike your datasets, the 3-D cubes are filled with points, instead of just a sufrace.
The MeshLab program crashed...any suggestions? Thanks MAtt

insane said...

you lost me in the 2nd step , a video or slide would be great.

Anyway thanks!!

Herr Keim said...

Hi,

I am very interested in using Meshlab in combination with surface scanners. But why didn't you state the menu names in your tutorial? I have to search the menu for things such as normal reconstruction.

Which data format stores color with the point cloud? How can I display xyzuv data?

The Viking said...

Hi, your blog is very helpful thank you for posting so much information. I was trying to follow your tutorial but got stuck on the subsampling step. I tried to perform Poisson disk samples but Meshlab gave me an error that it could not perform this action on a point set. Any suggestions?
Thanks

ALoopingIcon said...

@Herr Keim:
You are right, I have added it now.
PLY save colored point clouds.

@The Viking:

When using the Poisson sampling filter
you have to check the boolean option "base mesh subsampling". Ok it is not a very helpful name :) I will change it in the next beta....

Mona said...

Hi all, I have been trying to follow the instructions for about 2 working days. This is my simplified instruction oriented on the Menu.

But I could simply not find the "vertex attribute transfer filter", where should that be in the menu?
Also I don't see the colour information from my xyzrgb ascii file (arius scan).

Thanks
Mona

1. Import Ascii file (xyzrgb in my case)
2. Open Layer view (next to little img symbol)
3. SUBSAMPLING: Filters > Sampling > Poisson-disk Sampling: Enter Number of Samples as the resulting vertex number / number of points. Good to start with about the same number as your vertex to maintain resolution.
4. COMPUTE NORMALS: Filters > Normals/Curvatures and Orientation > compute Normals for Point Set [neighbours = 20]
5. TRIANGULATION : Filters > Point set
a. Poisson, set octree to 11 [you should now see a new layer in the Layer Dialog to the right] but really strange border!
b. Marching cubes. Default > no result. Grid resolution to 1000 > detailed mesh. [500K vertices > 1mio faces. Very good.
6. Fill holes by Filters > Cleaning and Repairing > Fill Holes, picks out number automatically
7. SAVE MESH save as obj file as backup, program crashes often

then how do I do the recoloration?

mgb said...

If you have data from a laser scanner isn't the normal the direction back to the laser? Surely that's the 'normal' between the beam and the surface at that point

ALoopingIcon said...

@Mona
About the recoloration, you can find some instructions on how to transfer attributes (like color) from a point cloud either to per-vertex color or to a texture in the last post about hausdorff distance computation:

@mgb
No, the direction between a sampled point and the laser emitter/receiver is not the surface normal (except in the rare case that you are in the middle of a sphere and you are sampling it from inside :) ). On the other hand this direction is an important one and can be used by surface reconstruction algorithms as a carving> constraint to disambiguate complex configurations.
In other words if the surface is not perfectly perpendicular to you r viewing direction, the line-of-sight of a TOF scanner is not coincident with the surface normal.

jamesrobertrye said...

Hi,

I have no problems to make a mesh from a point cloud. But I am having trouble colouring the mesh using the point cloud.

My input is X,Y,Z,I,R,G,B

x=easting
y=northing
z=height
I=intensity
R=red
G=green
B=blue

I have tried removing the intensity value.

I import the data as .asc format

James

Thomas said...

The Vertex Attribute Transfer Function everyone was looking for can be found under Filter->Sampling

Esfahlan said...

I have a 1600x3 matrix of poin clouds. I pasted into .txt file and changed the file extension to .asc.
The poit set is quite well as I have done by Ansys. But Meshlab can not construct a meshing! Your instruction didnot worked. I am mechanical engineer and I dont understand different type of algorithem in this field. Meshlab seems easy to use but didnot worked for me. Can I sent my file to you for processing?
Thanks alot.

marco said...

After performing "Vertex transfer attribute", my textured mesh has many gaps in grey because my points cloud is not very dense. How can fill these "gray gaps"?
Thanks

beelzebeau said...

you say here that you are processing a medium sized mesh of 9 mil polys. I am working with a 12 mil mesh and it crashes when I try to do anything. What am I missing?

jazzros said...

Good work.

Another project is: reconstruct a surfaces by surface-mesh.

If it interesting, please go at: http://jazzros.blogspot.com/2011/02/hi-all.html

This is a Surface Reconstruction tool.

Thanks.

PraaPi said...

In general, to model general indoor objects (like shoes, say) what is a good number of points in the point cloud? I have come across some sites which give around 10000 points from multiple images of the object like my3dscanner.com and photosynth...

Thanks,
Chaitanya.

Chip Moore said...

I am using the 64 bit windows version of meshlab 1.3.0 on a windows 7 machine and trying to create a mesh for from a PLY file based on the laurana500.ply file in the Meshlab samples directory. (This is a learning exercise.) I removed the faces from the original PLY file and added color information for the vertices. The resulting PLY file looks like this:

ply
format ascii 1.0
comment VCGLIB generated
comment TextureFile laurana500.png
element vertex 7
property float x
property float y
property float z
property uchar red
property uchar green
property uchar blue
0.780933 -45.9836 -2.47675 91 88 235
4.75189 -38.1508 -4.34072 236 33 33
7.16471 -35.9699 -3.60734 254 49 135
9.12254 -46.1688 -8.60547 56 31 203
15.4418 -46.1823 -9.14635 73 211 0
2.83145 -52.2864 -7.27532 37 13 207
0.160988 -53.076 -5.00516 7 153 155

Meshlab successfully imports and displays the PLY file. Following the steps described by Mona, I successfully execute

1. Import Ascii file (xyzrgb in my case)
2. Open Layer view (next to little img symbol)
3. SUBSAMPLING: Filters > Sampling > Poisson-disk Sampling: Enter Number of Samples as the resulting vertex number / number of points. Good to start with about the same number as your vertex to maintain resolution.

but step 4

4. COMPUTE NORMALS: Filters > Normals/Curvatures and Orientation > compute Normals for Point Set [neighbours = 20]

reliably crashes. I have no idea what is causing a problem. Suggestions.

Thanks.

yko said...

Hello,
I'm also trying to convert pointclouds into meshes. Well, I managed to get a nice mesh (thank you Mona) with marching cubes and Poisson. But I can't find how to colorize my mesh using the original point cloud. The chapter 5 doesn't give a detailed procedure. If someone could help me...

akuhero said...

tqvm for the information

Twigs said...

When following this Meshlab consistently crashes when I get up to the surface reconstruction: poisson, citing an assertion error. What could be the cause of this I get it a fair bit with this program.

Narcolessico said...

It is a great software, but I'm experiencing stability problems too. It is a bit annoying that most of times no explicit error is given. Shell output:

meshlab: mlssurface.tpp:126: void GaelMls::MlsSurface::computeVertexRaddi(int) [with MeshType = CMeshO]: asserzione "mPoints.size()>=2" non riuscita.
Annullato

Mike Knoop said...

I found this solution to stability issues on another blog, but mostly you just need to vary the parameters to the filters. For example, the Poisson filter, set the first value to 10 or 11. When calculating normal faces, use first value > 50 or > 100. It's annoying but I got my models to not crash simply by not using default values for the filters.

Sergi said...

"Now just selecting the faces having vertices whose distance is larger than a given threshold we can easily remove the redundant faces created by the Poisson Surface Reconstruction."

I don't understand this point.

How I remove the redundant faces created by the Poisson Surface?

Thank you

David said...

Hi everybody,

I have a point cloud .txt extension with 6 columns x y z R G B so...I have a colorized point cloud...nevertheless, when I try to open it qith meshlab a warning raise up saying that it's impossible to open the file...so I decided to chage the format to .asc extension BUT it's a triplet point ascii so the RGB (colour)is not considered...Can anyone tell how could I open my colorized point cloud?? THANKK YOU VERY MUCH :)

Immi Immens said...

@David: You can change your txt into ply manually. just insert the header for ply file:
ply
format ascii 1.0
comment VCGLIB generated
element vertex 12345
property float x
property float y
property float z
property uchar red
property uchar green
property uchar blue
element face 0
property list uchar int vertex_indices

12345 is the number of points in your file.

I hope its not too late

Jacek Kustra said...

Is the point normal calculation based on a published algorithm? if so, can you provide the reference?

Thanks!
Jacek

high temper said...
This comment has been removed by the author.
sherlina s said...

My cousin recommended this blog and she was totally right keep up the fantastic work!
Cloud Point

Quinno said...

Looks very useful but I'm stuck at step 2: "then transfer the normals of this small rough surface to the original point cloud."
How do I do this? Can anyone help?

Sarah said...

When I export my point cloud coordinates I get them in 6 columns. What are the columns? I only need x,y and z.

tkel said...

@sergi
I have the same question. How are you able to only select the faces of the created mesh that are closest to the points that were used to create the mesh?

There is a huge bubble around my mesh (I believe that it's shown above in light red) that I want to remove.

Dhiraj Kumar said...
This comment has been removed by a blog administrator.
Mike Bacher said...
This comment has been removed by a blog administrator.
Virendra Bhatiya said...
This comment has been removed by a blog administrator.
M RAZA ABBAS said...

Thanks, this is in every respect what I need to know. Thank you, it's very interesting. I wish you all the best and every success in future.
paver restoration Wellington

Jessica Jessi said...

Great talent post! Have you any idea about the site? http://feeds.feedburner.com/ReportingAccounts , where you can get all information about all company’s present activities. Thanks.