6 replies to this topic

[01.data]

Hi there,

I'm searching a fast algorithm for the following problem:
I've an arbitrary 3d point P and a triangle mesh (consisting of vertices, edges and triangles). For point P I must find the coordinate of the closest point on the surface of the mesh. This point can therefore lay within a mesh's triangle, onto an edge or can coincide with a vertex.

The question is: How? How am I doing this efficiently?

My first thought was to try to find a point defined in barycentric coordinates on each triangle for which the distance to the point P is minimal. But I assume this is very time consuming and secondly I've no clue how to do that.

Another way of thinking was to find the closest vertex within the mesh. Then, find the closest point on each adjacent edge by projecting the point P on the edge and -- further on -- find the closest point on the adjacent triangles by projecting P onto the plane defined by them and checking if this projection lays within the triangle and taking the closest of all these. But this also sounds too inefficient.

Well, if anyone can give me a hint I'd be thankful.

Greetings,
Data

[Reedbeta]

The key to doing this efficiently is to apply a spatial subdivision algorithm to cut down on the number of triangles you need to actually process. This could be some kind of BSP tree (e.g. kd-tree or octree), or a uniform grid.

[01.data]

Reedbeta said:

The key to doing this efficiently is to apply a spatial subdivision algorithm to cut down on the number of triangles you need to actually process. This could be some kind of BSP tree (e.g. kd-tree or octree), or a uniform grid.

Thanks for the fast reply. Yeah, I'll subdivide my mesh for acceleration. But do you think that there'll be a faster way to determine the closest point once a vertex/edge/triangle was selected? Faster than my second idea?

[velocitysg]

I know this a very old post but I am having the same problem. Did you find a good solution for this? Thanks.

[v71]

The best solution as reedbeta pointed out is to use a subdivision scheme,
kd-trees are very usefull in this very context.

[bravodwayne23]

spatial subdivision algorithm is good but i don't know how to apply...
plese help me.

[rouncer]

write the tool in the gpu, then just brute force it, its valid programming these days.