Consistent orientation of normals in point cloud
Many algorithms for point clouds require consistent orientation of normals in all points to understand where the object has inside and outside. It is not an easy task to achieve. The most famous algorithm here is Surface Reconstruction from Unorganized Points, and it is based on orientation propagation along Minimum Spanning Tree. This algorithm is implemented with certain variations in several software packages and libraries, including MeshLib. Also MeshLib provides another algorithm that can outperform the former in many real cases as will be shown below.
Let us take an example point cloud of a triumphal arch from Eastern Europe, containing almost 300'000 points. Unoriented normals were computed by MeshLib and shown here:
Blue points have normals toward the camera, and yellow ones - away from camera. So the lack of consistent orientation is visible.
Open3D is a library with Python interface, that can solve this task as follows:
import open3d as o3d
import time
pcd = o3d.io.read_point_cloud("arch-unoriented_normals.xyzn")
start = time.time()
pcd.orient_normals_consistent_tangent_plane(16)
end = time.time()
print('Open3d orient normals time: ', end - start, 'sec')
o3d.io.write_point_cloud("arch-open3d-orientation.xyzn", pcd)Open3D result:
Red arrows point on the places with incorrect orientation of normals, which are numerous.
CloudCompare is a free software implementing normal orientation algorithm. Here it was launched from UI.
- Open input file as ASCII cloud:
- Select imported object and Orient normals with Minimum Spanning Tree with 16 neighbors of each node:
- Invert all normals (since they are formed on step 2. mostly inside) and export the result in file.
CloudCompare result:
Red arrows point on the places with incorrect orientation of normals, which are less numerous than in Open3D, but still visible.
Advanced normals orientation of MeshLib can be invoked from Python as well:
import meshlib.mrmeshpy as mr
import time
cloud = mr.loadPoints("arch-unoriented_normals.xyzn")
start = time.time()
settings = mr.TriangulationHelpersSettings()
settings.numNeis = 16
allLocal = mr.buildUnitedLocalTriangulations(cloud, settings)
cloud.normals = mr.makeOrientedNormals(cloud, allLocal)
end = time.time()
print('MeshLib make oriented normals: ', end - start, 'sec')
mr.savePoints(cloud, "arch-meshlib-normals.xyzn")MeshLib result:
No visual inconsistencies in the normals can be seen.
- arch-unoriented_normals.xyzn.zip
- arch-open3d-orientation.xyzn.zip
- arch-cloudcompare-orientation.xyzn.zip
- arch-meshlib-normals.xyzn.zip
Apart of result correctness, the performance of the implementations is also very important especially for huge point clouds.
Below measurements were made on a computer with
OS: Windows 11
CPU: AMD Ryzen 9 3900X 12-Core Processor, 24 Concurrent Threads
Memory: 64 Gb
| Implementation | Time |
|---|---|
| Open3D 0.18.0 | 11.3 sec |
| CloudCompare v2.13.1 | 4 sec |
| MeshLib v3.0.0.40 | 0.5 sec |
MeshLib is a clear winner in this example, both from quality perspective, and also it is the fastest in particularly because of excellent parallelization.
The idea behind the classical Minimum Spanning Tree algorithm is to construct the graph with nodes in cloud points, and edges among given number of closest points. Then every edge is given a weight depending on Euclidean distance between two points it connects, and absolute value of dot product of their unoriented normals. Iterative Minimum Spanning Tree construction is equivalent to finding the edge with the smallest weight, connecting one point from already processed set and another point from yet unprocessed points, and the reached unprocessed point gets its orientation there and the algorithm goes on.
MeshLib goes further by considering independently constructed local Delaunay triangulations around each point. Here for example two near points are shown, each with its own local Delaunay triangulation:
The orientation starts from most distant point from the center of point cloud, where the normal is oriented outside. Then the algorithm finds the unoriented point with the largest amount of local triangles present in local triangulations of already oriented points, and the found unprocessed point gets its orientation there and the algorithm goes on. Considering neighbor points sharing at least one triangle from local Delaunay triangulations allows filter out unrelated points, which both improves the quality and the performance of the algorithm.