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.

Please log in or register to post a reply.

@Reedbeta

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?

kd-trees are very usefull in this very context.

- Upcoming Multiplatform Game Program...
- Network Emulation Tool
- Trouble with accessing GLSL array
- Game Programming Patterns: Bytecode
- Fiction
- Unreal Engine 4
- Skeletal Animation Tutorial with GP...
- Interactive WebGL Water Demo
- Microsoft xbox one selling poorly
- Using OpenGL Camera with Box2D in C++

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