Jose's Blog

16.04.2015

Mesh to Point Cloud

Filed under: 3D mesh,point-cloud — Tags: — admin @ 20:14

I am working on a project wherein I need to convert a 3D mesh into a pointcloud. I tried looking at possible freeware that could do it for me, but in the end I decided to write my own program. The reason is simply because I need to automate a few things and it is easier if it is a program I made. I am working on an algorithm on medial axis that will help me on analytic path planning and this is one step towards this.

I will soon publicize the source code of this simple program, but before doing so I will write a bit about the algorithm used. A lot of mesh to point cloud algorithms rely on something sophisticated e.g. sampling based on ray tracing. But I decided to take something natural (which has probably been done before). Since I am mostly working with STL binary mesh format (I also love ply, obj and other 3D formats, but stl was what I was doing most of my work with), I decided to just discreticize the triangles (basically the polygon types in a STL file) and refine them iteratively to reach a certain sampling resolution.

The input for the program is an stl file and the resolution of the pointcloud. Alternatively one can input a second finer resolution. The algorithm works in the following way: First triangle edges are discretize using the finer resolution, say e. Then if one is able to inscribe in the triangle another triangle whose edges are e distance away from the original triangle we get something like the picture below

Interior Triangle e distance away from the exterior triangle

This is done iteratively until the edge of the inner triangle cannot be e distance away from the previous inner triangle (or the outer triangle if still in the first iteration). The edges of all inner triangles are then discreticize using the given resolution. The resulting triangles would then look like this

point-cloud with finer resolution from one triangle

point-cloud with finer resolution from one triangle

We now have a uniform distribution of points (a very fine point-cloud) in each triangle making up the mesh. The algorithm then uses a one-way trapdoor function using modulo arithmetic on three big primes (see [1]). The algorithm for the one-way trapdoor function produces a spatial hashing function and is described in [2].

The finer point-cloud is randomly shuffled and a first point is chosen from the point cloud generated from the triangles, the image of this point from the trapdoor function is computed and added to a list of scalars and the point is added to a list of points (a new point-cloud) if the image has not yet been added before (we may have two points of the same image if the points belong to the same leaf of an octree described the rougher resoluton). We continue choosing random points and adding it to the lists using the condition on the images until we exhausted all points. The resulting point-cloud from the list is the output of our algorithm.

You can download the program (7-zipped) by clicking here. Files can also be dragged into the window. A window based program starts if no parameter is given, otherwise with the correct parameter you can also run the program using command line. To know the parameter just give any parameter in command line and if the program detects wrong parameter it will display th usage  e.g.:

wmesh2pc help

at command line will display the usage.

[1] A. Menezes, Elliptic Curve Public Key Cryptosystem. Kluwer Academic Publishers, 1993.
[2] M. Teschner, B. Heidleberger, M Müller, D. Pomeranets, M. Gross, Optimized Spatial Hashing for Collision Detection of Deformable Objects. Proc. Vision, Modeling, Visualization VMV’03, Munich, Germany, pp. 47-54, Nov. 19-21, 2003.

Powered by WordPress