C++ / C# - line triangle intersect? (sparky?)

Author

Message

mm0zct

21

Years of Service

User Offline

Joined: 18th Nov 2003

Location: scotland-uk

Posted: 17th Jun 2005 08:07

Link

i'm struggling with a function i need, i need to be able to find the point of intersection of a line and a triangle pased to the function as lots of coordinates but my 3d vector math is not good enough (esp in c++).
could someone please explain how to do this or, failing that, post a suitable function?
sparky could probably help since he wrote an intersect object dll, if you read this sparky please help

i attached the startings of my opengl c++ fps game so you can see why i need the function.

http://www.larinar.tk
AMD athlon 64 3000+, 512mb ddr400, abit kv8, 160gb hdd, gigabit lan, ati radeon 9800se 128mb.

Attachments

Login to view attachments

Back to top

Profile PM Email

Paul Johnston

TGC Developer

22

Years of Service

User Offline

Joined: 16th Nov 2002

Location: United Kingdom

Posted: 18th Jun 2005 21:51 Edited at: 18th Jun 2005 21:51

Link

Typically you need at least the co-ordinates of the three vertices of your polygon, and the co-ordinates of the start and end points of the line. Having the normal of the plane stored, and its distance from the origin can help, if not you'll have to calculate it. (a plane is just an infinite extension of our polygon across 3d space)

Here's the general method I use:

-Work out (if not already stored) the plane equation in which the triangle lies. Check if the end points of the line are on different sides of the plane.

-Work out the point at which the line crosses the plane (the one point on the line that lies in the plane)

-Then check if this point lies inside the triangle, there are many methods to do this.

The plane equation is of the form Ax + By + Cz + D = 0, where A,B,C and D are values you need to work out (I don't know how much 3d maths you already know so if any of this seems like another language let me know). It just so happens that the A,B and C parts are equal to the normal of the polygon. D can be worked out by rearranging the equation and using any vertex point as the x,y,z values.

The idea behind the plane equation is if you plug any point into the x, y and z parts of a particular plane equation it will equal 0 if that point is on the plane, <0 if it's on one side, or >0 if it's on the other. so if we put our two line points into this equation it will tell us if both points are on the same side or if they cross the plane. If they are on the same side, then there's no way the line can cross the polygon and we can stop. Otherwise we continue to check if the line crosses the part of the plane where the polygon lies.

Here's a snippet from the code I use to achieve this:

//p->x p->y p->z is the start point of the line
//v->x v->y v->z is the vector from start point to end point
//p+v gives the end point

//check the points distance from the plane
dist1 = normal.x*(p->x+v->x) + normal.y*(p->y+v->y) + normal.z*(p->z+v->z) + d;
dist2 = normal.x*p->x + normal.y*p->y + normal.z*p->z + d;

// >0 means the point is on the visible side of the plane
// <0 means the point is on the back side of the plane
// if start point is behind the plane, or the end point is in front
// of the plane, ignore the point (can't collide with back of polygon)
if (dist2<-0.00001 || dist1>0.00001) return false;

//use dot product to work out the distance along the line to the intersect point
dist1=-(normal.x*v->x) - (normal.y*v->y) - (normal.z*v->z);
if (dist1!=0) dist1=dist2/dist1;
else dist1=0;

//work out the point of intersection with the plane                
intersect.x = p->x + v->x*dist1;
intersect.y = p->y + v->y*dist1;
intersect.z = p->z + v->z*dist1;

//check if this point lies in the triangle                
if (!pointInPoly(intersect)) return false;

return true;

Sorry your browser is not supported!

Programming Talk / C++ / C# - line triangle intersect? (sparky?)

Attachments

Attachments