Fastest way to find closest triangle of mesh from specified point

Question

I have two triangle meshes (let me call them A and B). The meshes may be really big (10.000 - 100.000 polygons). I want to find for every point in A the closest triangle from mesh B.

Is there a fast way to do it? Does a near real time solution exist?

I found several papers that describe ways to find distance from a point to a triangle and I know a little bit about kd-tree/bvh-tree. Hence I may be able to find several triangles that are close enough to the specified point and then I can find triangle by brute force.

But I guess that this method will be not fast enough.

Answer 1

Create an octree and in each leaf cells put the list of all triangles from B that intersect the cell, mark at each levels whether or not the cell is empty. If one cell at any level has only 1 poly note the poly so you can stop the search early (large floor/wall triangles). You can keep sub-dividing cells until you have a reasonable number of triangles in each cells.

Using the octree find the closest non-empty cell.

Find the closest triangle in this cell, note the distance.

For each non-empty cells that are within this distance: Find the closest triangle in these cells, keeping the closest distance, ignoring cells that are further than this each time.

The reason for this last iteration is that a triangle at the far end of a cell might be further than a triangle in a neighbor cell.

If you need more speed you can use this with GPGPU (e.g.: OpenCL) to both build the octree and to iterate over every points of A in parallel once your octree is built.

Note that GPGPU performance varies greatly between GPUs. So what is realtime on one might be barely faster (or even slower) than the CPU.