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.

53 comments:

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
Thanks for your detailed instructions!
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

Please can anyone help?

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
end_header
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
end_header


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.

Peter John said...

I'm very much inspired when I've visited your blog. Your blog is really informative. Hope you will continue with the new article. Managed Cloud Hosting Canada

Jon K Smith said...

What an informative post! I like this post very much. Because this post contains very helpful information about point cloud. Thanks for this post. Point cloud Grand Prairie, Alberta

Sharon Wood said...

Lifelock Phone Number
HP Printer Phone Number
Canon Printer Phone Number
Brother Printer Support Phone Number

Tuckerjackk said...


Norton.com/Setup is best antivirus available in the market. If you want to protect your system online or locally from any unforeseen events Norton is is a must have software in your PC or Mac. Activate your Norton.com/Setup to protect yourself ad your data from your system from malware and antivirus. Browse internet without any hesitation norton will take care of all malicious antiviruses floating all over internet.

For any concern and help just visit website for Office.com/Setup help and key activation of Office.com/Setup You can do it by yourself if you know how to install office.com/Setup on your PC or Mac or you can call third party companies as well who can do it on your behalf.

McAfee.com/Activate Since the world is developing each day with new computerized advances, digital dangers, malware, information, and harming diseases have additionally turned out to be increasingly more progressed with every day. These digital contaminations harm a gadget or documents in different ways.McAfee.com/Activate

lost_in_woods said...
This comment has been removed by the author.
lost_in_woods said...

needed some knowledge on this
thank u for any work regarding this topic log on to
Point Cloud to BIM conversion in India

Point Cloud to BIM conversion in UK

James jenny said...

Thanks for sharing. Please do visit the link below.
Point Cloud to BIM conversion in Uk

James jenny said...

Thanks for sharing. Please do visit the link below.
Point Cloud to BIM conversion in Uk

contactforprinter said...

HP Printer Support Number1-855-499-1999 doesn't have affiliation with these companies unless of course such relationship continues to be particularly pointed out. The service we provide for Independent items can also be available from the person brand proprietors on their specific websites, and can also be provided by them totally free.
HP Printer Support Number

All Customer Service Number said...

Microsoft Office PC Setup Office Remote turns your phone into a smart remote that interacts with Microsoft Office on your PC. The app lets you control Word, Excel, and PowerPoint, Outlook from across the room, so you can walk around freely during presentations. You can install it from the given link Office/setup.

john smith said...

In our MacBook, technical support delegates at MacBook backing are very talented and experienced, who give users support at the earliest opportunity. You need to get a instant solution through MacBook technical support which is guaranteed you also. You don’t need to stress over it since we give you the fast technical support through macbook support number :18003823046.

JAck Ponting said...

Microsoft Office 365 Installation is an important part of complete package that's employed by professionals and non-professionals. There is a simple activation procedure for activation by inputting thought credentials and Office Setup product key.

www.norton.com/setup
Office Setup
www.webroot.com/safe

allhelplinesupport3046 said...


ATT Customer Service Number
ATT Email Support Number
ATT email login

Comcast Email Support Number
Comcast Customer Service Number

AOL Customer Service Number
AOL Support Number
AOL Mail Help Number
AOL Mail login
Change Aol password

Phonesupportservices said...

HP printer support
epson pinter support
canon printer support

Mark Steven said...

HP PRINTER TECHNICAL SUPPORT NUMBER
HP TECHNICAL HELP NUMBER
HP PRINTER SUPPORT NUMBER
HP PRINTER CUSTOMER SUPPORT NUMBER
HP PRINTER SUPPORT PHONE NUMBER
HP PRINTER TECH SUPPORT
HP PRINTER TECH SUPPORT NUMBER
HP PRINTER TECH SUPPORT PHONE NUMBER
HP PRINTER TECHNICAL SUPPORT PHONE NUMBER
HP TECH SUPPORT FOR PRINTERS
hp technical support help number
HP Printer Technical Support Number
HP Technical Support Number
hp tech support help number
Google Account Recovery
askhelpme
HP Printer Technical Support Phone Number
HP Printer Customer Service Number

Printer Customer Support Number said...

Nice post thank you for sharing. Printer Tech Support Number 1-800-289-8149 for help you contact.Call us We are 24*7 available. https://www.printertechssupportnumber.com/

Billy said...

Nice post thank you for sharing. Antivirus Tech Support Number 1-800-524-2156 for your help.Call us We are 24*7 available. https://www.antivirustechsupports.com/avast-support/