Finding closest point on mesh

6 replies to this topic

#101.data

New Member

• Members
• 4 posts

Posted 06 October 2006 - 06:41 AM

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

#2Reedbeta

DevMaster Staff

• 5311 posts
• LocationSanta Clara, CA

Posted 06 October 2006 - 06:49 AM

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.
reedbeta.com - developer blog, OpenGL demos, and other projects

#301.data

New Member

• Members
• 4 posts

Posted 06 October 2006 - 07:00 AM

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?

#4velocitysg

New Member

• Members
• 1 posts

Posted 21 July 2011 - 04:07 PM

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

#5v71

Valued Member

• Members
• 355 posts

Posted 21 July 2011 - 10:11 PM

The best solution as reedbeta pointed out is to use a subdivision scheme,
kd-trees are very usefull in this very context.
Check my code in the c/c++ section :
http://www.binpress.com/browse/c

#6bravodwayne23

New Member

• Members
• 1 posts

Posted 24 August 2011 - 08:40 AM

spatial subdivision algorithm is good but i don't know how to apply...
plese help me.
Easy Video Player &Green Tea

#7rouncer

Senior Member

• Members
• 2725 posts

Posted 24 August 2011 - 09:09 AM

write the tool in the gpu, then just brute force it, its valid programming these days.
you used to be able to fit a game on a disk, then you used to be able to fit a game on a cd, then you used to be able to fit a game on a dvd, now you can barely fit one on your harddrive.

1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users