0
101 Oct 06, 2006 at 06:41

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

#### 6 Replies

0
165 Oct 06, 2006 at 06:49

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.

0
101 Oct 06, 2006 at 07:00

@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.

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?

0
101 Jul 21, 2011 at 16:07

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

0
105 Jul 21, 2011 at 22:11

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

0
101 Aug 24, 2011 at 08:40

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

0
104 Aug 24, 2011 at 09:09

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