This is an example implementation of the closest point on mesh algorithm. Given any 3D point and any mesh, it should find the closest point on the mesh to the given point in a maximum given radius. A GUI comes with it to demonstrate the results and performance.

• 📓 Documentation
• 💥 Try it

Tests were made with an AMD Ryzen 5 3600 @ 3.59Ghz. The implemntation only use one core. In the following tests, all vertices were normalized in the range [-1, 1].

The obj files I have used are available in common-3d-test-models.

• Pre-process time: KDTree generation of the mesh point cloud
• Compute time: finding the closest point on the mesh of a given point

The search radius doesn't effectively affect the performances because of the way I'm using the KDTree. Although, if the query point is far away from the mesh, the compute time will increase. A simple point to bbox distance check could avoid that.

I am using a point cloud with a KDTree to find the closest point on the mesh.

Before-hand:

1. Compute a point cloud of the mesh
   1. Add vertices in the point cloud
   2. Generate points on the mesh to increase the point cloud precision Not implemented
2. Build a KDTree containing the point cloud

When requesting the closest point:

1. Find the N closest points in the point cloud using the KDTree
2. For each of these points
   1. Get the mesh triangle on which the point is
   2. Compute the closest point to the query point that is on the triangle
3. Keep the closest point to the query point

Requirements:

• The mesh needs to be uniform
• The search must always be higher than the size of one triangle

This program works only on Linux and require to install the following dependencies:

• assimp
• glfw

$ git clone git@github.com:oktomus/cpp-closest-point-on-mesh.git
$ cd cpp-closest-point-on-mesh
$ mkdir build && cd build;
$ cmake -DCMAKE_BUILD_TYPE=Release .. && make -j # Build
$ ./app.gui # Run the GUI

Used thirdparties:

• nanoflann: KDTree implementation
• GLFW
• GLAD
• assimp: Assets importer
• imgui: GUI

First, install doxygen.

$ doxygen doxygen
$ firefox docs/html/index.html # Open it

I didn't write any tests for this application. But if I do so, here is what I will do:

• Write unit tests for the low-level math functions
• Write test files to assert that the implementation gives correct result for a given mesh

• Generate more points in the mesh point cloud to support any type of mesh.
• When using the KDTree, find the N closest points that are in the given search radius. Right now I only consider the N closest points, even if they are too far away.
• Use SIMD instructions to compute distances and closest point on triangle.
• Make the algorithm multithread by splitting the point cloud in N buckets where N. Then simply give a bucket to each thread.

• 1: Closest Point on a Mesh : Background and Approaches
• 2: Fast Distance Queries for Triangles, Lines, andPoints using SSE Instructions
• 3: Distance Between Point and Triangle in 3D