Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


distance from a point to a triangle


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 Strange Monkey   Members   -  Reputation: 122

Like
Likes
Like

Posted 11 July 2001 - 05:24 PM

Hi! I''m writing a small game and I need to compute the smallest distance between a point and a triangle in a 3d space. Does someone know how to do it???

Sponsor:

#2 johnb   Members   -  Reputation: 347

Like
Likes
Like

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 point-plane 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 v-clip implementation) was converging.

#3 grhodes_at_work   Moderators   -  Reputation: 1361

Like
Likes
Like

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.

#4 Strange Monkey   Members   -  Reputation: 122

Like
Likes
Like

Posted 12 July 2001 - 04:16 AM

quote:
Original post by grhodes_at_work
2) Compute a unit normal vector for the triangle. Let the normal be (nx, ny, nz).



How do I compute that normal vector?

#5 grhodes_at_work   Moderators   -  Reputation: 1361

Like
Likes
Like

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):


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.

#6 Strange Monkey   Members   -  Reputation: 122

Like
Likes
Like

Posted 12 July 2001 - 10:39 AM

How don''t know why, but it still not working. Maybe if someone got an example project it could help me. My e-mail address is dagenais.f@videotron.ca.

#7 grhodes_at_work   Moderators   -  Reputation: 1361

Like
Likes
Like

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 distance----a 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 Strange Monkey   Members   -  Reputation: 122

Like
Likes
Like

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.

  
D3DXVECTOR3 v1,v2, intersect, normal;
float dotp,dist,length;
for (i=0;iNumFaces;i++)
{
//First, we have to find the normal of the polygon

//We start to meake a vetor from the first and second vertices

v1.x = tri[i].v2.x-tri[i].v1.x;
v1.y = tri[i].v2.y-tri[i].v1.y;
v1.z = tri[i].v2.z-tri[i].v1.z;

//Then with the first and third vertices

v2.x = tri[i].v3.x-tri[i].v1.x;
v2.y = tri[i].v3.y-tri[i].v1.y;
v2.z = tri[i].v3.z-tri[i].v1.z;

//After, we do the cross product

normal.x = v1.y*v2.z-v1.z*v2.y;
normal.y = v1.z*v2.x-v1.x*v2.z;
normal.z = v1.x*v2.y-v1.y*v2.x;

//Now we have to make it a unit vector

length = sqrt(normal.x*normal.x+normal.y*normal.y+normal.z*normal.z);
normal.x = normal.x/length;
normal.y = normal.y/length;
normal.z = normal.z/length;

//Making the intersection point

v1.x = x-tri[i].v1.x;
v1.y = y-tri[i].v1.y;
v1.z = z-tri[i].v1.z;
dotp = v1.x*normal.x+v1.y*normal.y+v1.z*normal.z;
intersect.x = v1.x-normal.x*dotp;
intersect.y = v1.y-normal.y*dotp;
intersect.z = v1.z-normal.z*dotp;

//Now that we got the intersection point,

//we just have to compute the lenght of this vector

dist = sqrt(intersect.x*intersect.x+intersect.y*intersect.y+intersect.z*intersect.z);

//Now, we check if there is a collision

if (dist <= 50.0f)
{
//if there is a collision, then we have to react

reactcollision();


}


#9 Oluseyi   Staff Emeritus   -  Reputation: 1678

Like
Likes
Like

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 several-fold). 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.

#10 Strange Monkey   Members   -  Reputation: 122

Like
Likes
Like

Posted 13 July 2001 - 04:44 AM

I tryed to declare my polygon both clockwise and counterclockwise but it still not working... Any other idea?

#11 grhodes_at_work   Moderators   -  Reputation: 1361

Like
Likes
Like

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:

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


#12 Strange Monkey   Members   -  Reputation: 122

Like
Likes
Like

Posted 13 July 2001 - 06:28 AM

Ok but even if I use the bounding box collision detection before this one, it''s still possible that it tell me that there is a collision when there is not. Am I right?

#13 grhodes_at_work   Moderators   -  Reputation: 1361

Like
Likes
Like

Posted 13 July 2001 - 06:49 AM

Yes, using these quick-and-dirty 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 triangle-to-triangle 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.

#14 Strange Monkey   Members   -  Reputation: 122

Like
Likes
Like

Posted 13 July 2001 - 09:03 AM

Ok thanks, I think all this info will help me




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS