3D point cloud generation from 3D triangular mesh
Introduction
Point clouds and polygonal (usually and from now on: “triangular”) meshes are the 2 main entities for representing three dimensional (“3D” from now on) data, and the two are closely interlinked.
You can’t represent a 3D object using a triangular mesh without vertices, and those required vertices might be interpreted as a point cloud.
In the same way, points in a point cloud represent the underlying surface of some 3D object, and that underlying surface might be interpreted as a polygonal mesh.
Point clouds
Point clouds are the raw output of many different sensors, such as:
- Lidar
- RGB-D (Microsoft Kinect, Google Tango, Asus Xtion, …)
- Camera + Photogrammetry software (Open source Colmap, Agisoft Photoscan, …)
Thus, those are the main sources from which point clouds are generated. You can also generate a point cloud from a triangular mesh using a process called mesh sampling, and we are about to learn how to code this process.
Triangular meshes
Triangular meshes are usually generated using 3D modelling, CAD, GIS, or similar software. Here are some examples:
In addition to those sources, you can generate a triangular mesh from a point cloud using a process called surface reconstruction. We are not going to talk about this, if you want to know more about surface reconstruction I strongly recommend you this paper:
Real world example
Let’s illustrate the previous concepts with some images.
This is (part of) my real-world collection of dinosaurs, with an ankylosaurus in the middle:
And these are rendered models of the 3D reconstruction (using my smart-phone’s camera + the previously mentioned software: Colmap) of that same ankylosaurus:
In the picture above is quite difficult to distinguish the triangular mesh from the point cloud (you can see that I didn’t lie when I said that both are quite similar).
That point cloud on the right was generated from the triangular mesh on the left with the code that I’ll show you later.
Here are some zoomed images of the triangular mesh and the point cloud:
Why do we want to generate point clouds from triangular meshes
If you want my (probably biased) opinion, point clouds are the true and purest way for representing the world around us.
Triangular meshes are quite convenient for many computer graphic tasks, but I believe that point clouds are just ideal for processing and extracting information from a 3D object.
Leaving aside my biased opinion, there are actually many algorithms and applications where you need to generate a point cloud from a triangular mesh.
Another fair reason might be that you want to use this Python library for working with point clouds (self-promoting ^^) to process some meshes generated in some 3D modelling software.
Mesh sampling — Explanation + Code
We are going to learn how the conversion from mesh to point cloud is done and implement the process in Python.
The first thing we need to do is to load the 3D mesh into Python. There are way too many file formats for storing 3D data.
Loading the mesh
This post isn’t about how to parse those formats so we will use an out-of-the-box ply loader from pyntcloud. You can inspect the source code to see how it works.
The ply file format (and many other common formats) store the mesh information in the face-vertex format:
So anky is a Python dictionary that contains 2 pandas DataFrame:
To actually get the x,y and z coordinates of each vertex of the triangle we need to use the indices in mesh to extract the information from points:
And now that we have our data loaded and formatted let’s solve the problem step by step.
The first thing we need to define is how many points will our output point cloud have. This is really situation-dependent and because of that our code should let the user define this parameter, which we’ll name n.
Once we know how many points we need to generate, we have to randomly select n triangles of the mesh and generate one point, in a random position, inside it’s corresponding triangle.
Naive random selection
First thing we might want to try is to generate n random integers between 0 and the number of triangles in the mesh:
But this random selection has a little problem that we probably wouldn’t notice until we actually run the final code. I’ll spoiler you with an image that illustrates the problem of this approach:
In the picture you can see a semi-sphere viewed from the top. The top right point cloud was generated with the sampling method that we will cover later; the bottom right point cloud was generated using the naive method explained above.
As you can see in the picture, our naive method is concentrating more points in the areas where there is a larger number of smaller triangles, because there is a higher probability of choosing those.
A solution to this it to adjust the random selection to make the probability of choosing a triangle proportional to it’s area.
Weighted random selection
So as stated above, we need to weight our probabilities according to the area of the triangles. To do this we need to first compute the areas of all the triangles in the mesh.
Check this math.stackexchange question to see different ways of computing the area of a 3D triangle.
The good thing about Python is that sometimes the code is actually a better explanation (at least for me) than math formulas:
Now we can make a weighted random selection:
Ok! We’ve already solved the problem of selecting the triangles, now we need to find a way to generate a random point inside a triangle. To do this we will make use of a cool concept which is very often used in the computer graphics world.
Barycentric coordinates — Explanation
I always enjoy a beautiful visualization that illustrates a geometry/math concept, so I made an interactive visualization to illustrate the concept of barycentric coordinates (it’s not beautiful but, in my defense, design is of one of my mortal enemies).
We will refer to this interactive visualization along the explanation.
I recommend you to check the page: Barycentric coordinate system. The page is very well explained mathematically so I will try to add a little of geometric intuition.
According to the page, you can generate a point inside a triangle using a linear combination of three numbers and the vertices of that triangle.
Let’s name this 3 numbers: u, v and w.
Since:
u + v + w ≤ 1
We can generate a point inside a triangle by just generating 2 random numbers u and v, letting:
w = (1 — (u + v))
And then multiplying these numbers with the coordinates of the vertices of the triangle.
Now go back to the visualization and try the following:
- Set u = 0 and try different values of v.
You should see the value of v indicates the position of our sampled point along the Red-Blue edge.
- Set v = 0 and try different values of u.
You should see that u indicates the position of our sampled point along the Red-Green edge.
- Watch the value of w.
You should see that w represents how far our sampled point is from the Green-Blue edge, following the median of the Red vertex.
- Set u = 0.5 and slice the value of v from 0 to 1.
You should see that our sampled point goes all the way down (following a trajectory parallel to Red-Blue edge) until it reaches the Green-Blue edge (v = 0.5) then, the point bounces and goes back to the Red-Green edge.
This happens because in the JavaScript code we are using a if statement that ensures that we always satisfy the Wikipedia restriction:
if (u + v > 1){
u = 1 - u;
v = 1 - v;
}Now you can see that the restriction is stated in order to prevent our sampled point from exceeding the Green-Blue edge.
- Set u and v to 0.33
You will see that w is also 0.33.
You have just found the barycentre(also known as centroid) of the triangle!
- Watch the colour of the sampled point while you move it; Try to change the colour of the vertices.
You just discovered another cool thing about barycentric coordinates: The same u and v values can also be used to interpolate the colour our sampled point.
Now that we understand the barycentric coordinates, let’s code.
Barycentric coordinates — Code
First thing we need to to is get the (weighted) randomly selected triangles:
Now we can generate the u and v values, and rectify the values where there is a problem with the restriction:
And compute our new points as follows:
A quick note is that for computing the normal of the sampled point, barycentric coordinates might not be the most logical solution.
What I like to do is to take the normalized average of the normals of the 3 vertices forming the triangle:
THE END
And that’s all, we now have a sweet point cloud of n points generated from a triangular mesh.
We can save our point cloud to a ply file in order to visualize it in some software:
You can download the 3D mesh of the ankylosaurus from this link and try the to re-write the code of this post in order to generate a point cloud yourself.
To self-promote again, you can also obtain the same result in pyntcloud with this little piece of code:
