• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

Archived

This topic is now archived and is closed to further replies.

Strange Monkey

distance from a point to a triangle

13 posts in this topic

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???
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
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();


}
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
I tryed to declare my polygon both clockwise and counterclockwise but it still not working... Any other idea?
0

Share this post


Link to post
Share on other sites
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
0

Share this post


Link to post
Share on other sites
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?
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites