distance from a point to a triangle
Started by Jul 11 2001 05:24 PM
,
13 replies to this topic
#2 Members  Reputation: 351
Posted 11 July 2001  09:10 PM
When I did this recently I did this:
Calculated the distance from the point to each corner of the triangle, each edge and each the face. The distance to each point is easy. For the distance to each edge I worked out the distance from the point to each line, then made sure the closest point on the line was actually on the edge (if not just throw away the result as a corner is nearer). And similarly for the face I worked out the pointplane distance and used it if the nearest point on the plane is inside the triangle.
Then the distance is the smallest of the results worked out above. Note that this requires a lot of calculations to do. I only did it as part of debugging code used to confirm that more efficient code (a vclip implementation) was converging.
Calculated the distance from the point to each corner of the triangle, each edge and each the face. The distance to each point is easy. For the distance to each edge I worked out the distance from the point to each line, then made sure the closest point on the line was actually on the edge (if not just throw away the result as a corner is nearer). And similarly for the face I worked out the pointplane distance and used it if the nearest point on the plane is inside the triangle.
Then the distance is the smallest of the results worked out above. Note that this requires a lot of calculations to do. I only did it as part of debugging code used to confirm that more efficient code (a vclip implementation) was converging.
#3 Members  Reputation: 1377
Posted 12 July 2001  03:39 AM
Here are the steps:
1) Let the triangle points be (ax, ab, az), (bx, by, bz), and (cx, cy, cz). Let the point of interest be (px, py, pz).
2) Compute a unit normal vector for the triangle. Let the normal be (nx, ny, nz).
3) Make a vector from one of the triangle points to the point of interest. Let that vector be (for example):
vx = px  ax
vy = py  ay
vz = pz  az
4) Take the dot product of (vx, vy, vz) with (nx, ny, nz):
dotp = vx * nx + vy * ny + vz * nz
5) Subtract (nx, ny, nz) times dotp from (vx, vy, vz) to get:
sx = vx  nx*dotp
sy = vy  ny*dotp
sz = vz  nz*dotp
Now, (sx, sy, sz) is a vector from the point to the *plane* of the triangle to the point (px, py, pz). And it is perpendicular to the triangle.
6) The length of (sx, sy, sz) is the distance from the triangle to the point:
distance = sqrt(sx*sx + sy*sy + sz*sz)
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
1) Let the triangle points be (ax, ab, az), (bx, by, bz), and (cx, cy, cz). Let the point of interest be (px, py, pz).
2) Compute a unit normal vector for the triangle. Let the normal be (nx, ny, nz).
3) Make a vector from one of the triangle points to the point of interest. Let that vector be (for example):
vx = px  ax
vy = py  ay
vz = pz  az
4) Take the dot product of (vx, vy, vz) with (nx, ny, nz):
dotp = vx * nx + vy * ny + vz * nz
5) Subtract (nx, ny, nz) times dotp from (vx, vy, vz) to get:
sx = vx  nx*dotp
sy = vy  ny*dotp
sz = vz  nz*dotp
Now, (sx, sy, sz) is a vector from the point to the *plane* of the triangle to the point (px, py, pz). And it is perpendicular to the triangle.
6) The length of (sx, sy, sz) is the distance from the triangle to the point:
distance = sqrt(sx*sx + sy*sy + sz*sz)
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
#5 Members  Reputation: 1377
Posted 12 July 2001  05:01 AM
To compute the normal vector, do this:
1) Make a vector from (ax, ay, az) to (bx, by, bz):
2) Make a vector from (ax, ay, az) to (cx, cy, cz):
3) Take the cross product of (e1x, e1y, e1z) and (e2x, e2y, e2z). The cross product is done by finding the determinant of this matrix:
Or, expanding out:
i*(e1y*e2z  e1z*e2y) +
j*(e1z*e2x  e1x*e2z) +
k*(e1x*e2y  e1y*e2x)
so that,
nx = e1y*e2z  e1z*e2y
ny = e1z*e2x  e1x*e2z
nz = e1x*e2y  e1y*e2x
4) Finally, make it a unit vector:
length = sqrt(nx*nx + ny*ny + nz*nz)
nx = nx/length
ny = ny/length
nz = nz/length
That''s it!
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
1) Make a vector from (ax, ay, az) to (bx, by, bz):
e1x = bx  ax
e1y = by  ay
e1z = bz  az
2) Make a vector from (ax, ay, az) to (cx, cy, cz):
e2x = cx  ax
e2y = cy  ay
e2z = cz  az
3) Take the cross product of (e1x, e1y, e1z) and (e2x, e2y, e2z). The cross product is done by finding the determinant of this matrix:
[ i j k ]
e1x e1y e1z = i*nx + j*ny + k*nz
[e2x e2y e2z]
Or, expanding out:
i*(e1y*e2z  e1z*e2y) +
j*(e1z*e2x  e1x*e2z) +
k*(e1x*e2y  e1y*e2x)
so that,
nx = e1y*e2z  e1z*e2y
ny = e1z*e2x  e1x*e2z
nz = e1x*e2y  e1y*e2x
4) Finally, make it a unit vector:
length = sqrt(nx*nx + ny*ny + nz*nz)
nx = nx/length
ny = ny/length
nz = nz/length
That''s it!
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
#7 Members  Reputation: 1377
Posted 12 July 2001  03:44 PM
Anyway you could post *your* code? It might be more helpful to correct the work you''ve already done.
It would also help if you describe exactly in what way it is not working. Are you just getting a totally wrong distancea distance that you *know* to be wrong? Are you testing this on simple problems with easy solutions (i.e., triangle in the xy plane, point vertically above one of the vertices at some z value)?
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
It would also help if you describe exactly in what way it is not working. Are you just getting a totally wrong distancea distance that you *know* to be wrong? Are you testing this on simple problems with easy solutions (i.e., triangle in the xy plane, point vertically above one of the vertices at some z value)?
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
#8 Members  Reputation: 122
Posted 12 July 2001  04:30 PM
Ok, Here''s the code. "tri" is a structure that I made containing the 3 vectors of the triangle. The problem is that it doesn''t collide when it is suppose and something it does when it is not supposed to.

#9 Members  Reputation: 2076
Posted 12 July 2001  05:34 PM
I''m a little tired and the code is starting to merge before my eyes, but it looks pretty good (could you insert spaces between variables and operators? It improves readability severalfold). What does occur to me is the vertex ordering. Depending on the ordering of your vertices, the normal may point out the "face" or the "back" of your polygon (I believe you want counterclockwise ordering, but I may be wrong).
If this is the case, then your normal''s apex is located on the other side of your polygon, meaning the distance between the point and the plane of the poly will be alternatively greater than, less than or just plain different than expected. Try explicitly declaring polygons both clockwise and counterclockwise and see if that makes any difference. Just a thought.
If this is the case, then your normal''s apex is located on the other side of your polygon, meaning the distance between the point and the plane of the poly will be alternatively greater than, less than or just plain different than expected. Try explicitly declaring polygons both clockwise and counterclockwise and see if that makes any difference. Just a thought.
#11 Members  Reputation: 1377
Posted 13 July 2001  05:58 AM
It doesn't matter if the triangle is clockwise or counterclockwise. The sign of the dot product (dotp) will take care of that, and the result should be the same with either orientation.
Your code does exactly implement my instructions; however, I'm afraid that I made a mistake in my instructions, , and that is probably why you're seeing the wrong results.
In fact, when you do this:
You're actually projecting the point down onto the triangle. The value of intersect computed here is the vector within the plane of the triangle that, when added to tri.v1, gives you the point of interest projected onto the plane of the triangle. This length of this has nothing to do with what you want.
Here's the fix, . Replace the code above with the following:
With this code, intersect will be the vector that points from the point of interest (x,y,z) towards the triangle. This value of intersect is perpendicular to the triangle, and its magnitude is the minimum distance to the plane of the triangle.
Since you're using this for collision detection, you should note that this code really just gives the minimum distance to the plane of the triangle and not really to the triangle itself. It is entirely possible, even likely, that your point of interest may still be very far away from the triangle. If the triangle is horizontal, then the point may be horizontally a 1000 units away, but only 50 units perpendicular to the triangle's plane. How to fix this easily? You may want to do an oriented bounding box check first, make sure the point is contained within the bounding box before checking the minimum distance. If the point falls outside the bounding box, skip the more detailed check.
I do apologize for the error. I just didn't review it carefully enough to begin with.
Edited by  grhodes_at_work on July 13, 2001 1:26:24 PM
Your code does exactly implement my instructions; however, I'm afraid that I made a mistake in my instructions, , and that is probably why you're seeing the wrong results.
In fact, when you do this:
intersect.x = v1.x  normal.x*dotp;
intersect.y = v1.y  normal.y*dotp;
intersect.z = v1.z  normal.z*dotp;
You're actually projecting the point down onto the triangle. The value of intersect computed here is the vector within the plane of the triangle that, when added to tri.v1, gives you the point of interest projected onto the plane of the triangle. This length of this has nothing to do with what you want.
Here's the fix, . Replace the code above with the following:
intersect.x =  normal.x*dotp;
intersect.y =  normal.y*dotp;
intersect.z =  normal.z*dotp;
With this code, intersect will be the vector that points from the point of interest (x,y,z) towards the triangle. This value of intersect is perpendicular to the triangle, and its magnitude is the minimum distance to the plane of the triangle.
Since you're using this for collision detection, you should note that this code really just gives the minimum distance to the plane of the triangle and not really to the triangle itself. It is entirely possible, even likely, that your point of interest may still be very far away from the triangle. If the triangle is horizontal, then the point may be horizontally a 1000 units away, but only 50 units perpendicular to the triangle's plane. How to fix this easily? You may want to do an oriented bounding box check first, make sure the point is contained within the bounding box before checking the minimum distance. If the point falls outside the bounding box, skip the more detailed check.
I do apologize for the error. I just didn't review it carefully enough to begin with.
Edited by  grhodes_at_work on July 13, 2001 1:26:24 PM
#13 Members  Reputation: 1377
Posted 13 July 2001  06:49 AM
Yes, using these quickanddirty techniques to detect collisions will often result in erroneous detections. But we often have to do approximate checks just to do it fast enough. And its often good enough for games. The bounding box check is a very nice way to avoid doing detailed checks that aren''t necessary.
If you''re interested in very precise collision detection (at a cost of CPU usage) then you might want to look into triangletotriangle intersection techniques. There is a *lot* of work done at the University of North Carolina at Chapel Hill on this (although their implementations are not considered robust by many folks in the game industry). Here is a link to their work:
http://www.cs.unc.edu/~geom/projects.shtml
See the second block of projects, "Collision Detection/Proximity Queries." For noncommercial use, you should be able to download code, or at least binaries.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.
If you''re interested in very precise collision detection (at a cost of CPU usage) then you might want to look into triangletotriangle intersection techniques. There is a *lot* of work done at the University of North Carolina at Chapel Hill on this (although their implementations are not considered robust by many folks in the game industry). Here is a link to their work:
http://www.cs.unc.edu/~geom/projects.shtml
See the second block of projects, "Collision Detection/Proximity Queries." For noncommercial use, you should be able to download code, or at least binaries.
Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.