7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.