Search code examples
computational-geometryeuclidean-distancetessellation

how to compute the shortest distance from a point to triangle using tesselated data

i have to solve a distance problem and i´m getting pretty upset because i don´t know how to do it despite having tried nearly everything that i´ve found on the web... here´s my problem:

i work in the automotive industry and we use tessellated data (like STL, in my case the JT-Format). I have a part that needs to be welded. and i have the coordinates of the weldpoint. to ensure that the weldpoint is located correctly i want to calculate if the weldpoint hits the part or, in other words, i want to check if the weldpoint collides with the part. if yes, then the part can be welded. otherwise the weldpoint would be in the air and it couldnt be welded. therefor i want to calculate the distance between the part (which is basically a set of triangles or polygons in the mentioned format) and the point. if the distance to one of the triangles is less then the also given radius of the weldpoint, then there must be a collision and thus the weldpoint is located correctly and can be welded.

a how to, pseudo-code or whatever that could be useful would be very appreciated. i´m coding in c++ using the JTOpen Toolkit. Please note that the point hasn´t necessarily have to lie within the triangle. Maybe an example could help you and me to understand the problems/answers (no collision in the following example):

let v1, v2, v3 be the vertices of a triangle and px, py, pz the coordinates of the weldpoint (radius 1.8). I also get normals (n1, n2, n3) to every vertex but i dont know what to to with them...

v1x = -273.439
v1y = -787.775
v1z = 854.273

v2x = -274.247
v2y = -788.085
v2z = 855.244

v3x = -272.077
v3y = -787.864
v3z = 855.377

px = 140.99
py = -787.78
pz = 458.93

n1x = -0.113447
n1y = 0.97007
n1z = 0.214693

n2x = -0.113423
n2y = 0.970069
n2z = 0.214712

n3x = -0.110158
n3y = 0.969844
n3z = 0.217413

thank you in advance!

Solution

  • The locus of the points at the same distance of a triangle is a complex surface made of

    • two triangles parallel to the original one, at the given distance;

    • three half cylindres corresponding to points at equal distances of the edges;

    • the spheres with points at equal distances of the vertices.

    enter image description here

    If you look facing the triangle, you will observe that these surfaces are split by

    • the three triangle sides,

    • the six normals to the sides at the vertices.

    Hence to find the distance of a given point, you need to project it orthogonally to the plane of the triangle and find its location among 7 regions delimited by half-lines and segments. Using an appropriate spatial rotation, the problem can be solved in 2D. Then knowing the region, you will use either the distance to the plane, to an edge or to a vertex.

    Note that in the case of a tessellation, several triangles have to be considered. If there are many of them, acceleration systems will be needed. This is a broad and a little technical topic.