Sign in to follow this  
D3DXVECTOR3

Im about to have a nervous breakdown (Collision Detection)

Recommended Posts

I have a plane specified like this: struct Plane { Vector3 p1; Vector3 p2; Vector3 p3; float D; // distance Vector3 N;// normal }; I have a ray with Vector3 vPos; // position Vector3 vDir; // direction Detecting collision with a plane was easy (sortof), but a plane is infinite. So how do I found out if the point is within the bounds of p1, p2, p3. (triangle/quad)!? Now i have searched all day long the net and couldnt find any solution that worked for me. So im looking for a solution to find the intersection with ray-triangle/quad before i get a nervous breakdown... thx :)

Share this post


Link to post
Share on other sites
The simple way, would be to determine the intersection point (on the plane) then decide whether that point is inside the triangle.

However, there are better quicker ways..
Softsurfers Method
I actually prefer the Moller/Trumbore method mentioned by Softsurfer... but they're pretty similar.
There's a good PDF and source (on MT) out there...
I'll post a link when I find it again.

Found it...Fast, minimum Storage Ray-Triangle Intersection

One note : The source in the paper is for Line-Triangle... However... provided you check t > 0 either in the routine, or on return... that gets you "ray-triangle".

Share this post


Link to post
Share on other sites
Hi!

Maybe this can help some:
http://softsurfer.com/Archive/algorithm_0104/algorithm_0104B.htm

If not, check out the pages higher in that webdir. Hopefully you will something that can give you a hint on what to search on or make your own solution.


pir

Share this post


Link to post
Share on other sites
Here is the function i wrote.
Works perfectly.
used functions like vector.set(VECTOR3 v) and VECTOR3::subs(VECTOR3 v1, VECTOR3 v2) are quite self explaining, and probably also used in your programs.

INTERSECTPOINT calcTriangleLineIntersection(VECTOR3 trianglePoint1, VECTOR3 trianglePoint2, VECTOR3 trianglePoint3, VECTOR3 linePoint1, VECTOR3 linePoint2)

needs 3 points (polygons must be divided in triangles if necessary)
and a line determined by 2 points (probably camera position and camera lookat).
it returns the intersection point of the infinite plane and line (intersectpoint), intersect = true if intersectionpoint is in the triangle


struct INTERSECTPOINT
{
bool interSect;
VECTOR3 intersectPoint;
};

INTERSECTPOINT calcTriangleLineIntersection(VECTOR3 trianglePoint1, VECTOR3 trianglePoint2, VECTOR3 trianglePoint3, VECTOR3 linePoint1, VECTOR3 linePoint2)
{
INTERSECTPOINT iPoint;
float detA;
float kPar; // intersectionpoint = kPar*(vector triangleside1)+lPar*(vector triangleside2)
float lPar;

VECTOR3 rv1, rv2, rv3;
rv1.set(VECTOR3::subs(trianglePoint2, trianglePoint1));
rv2.set(VECTOR3::subs(trianglePoint3, trianglePoint1));
rv3.set(VECTOR3::subs(linePoint2, linePoint1));
detA = rv1.x*rv2.y*rv3.z+rv2.x*rv3.y*rv1.z+rv1.y*rv2.z*rv3.x
-rv3.x*rv2.y*rv1.z-rv3.y*rv2.z*rv1.x-rv2.x*rv1.y*rv3.z;
if (detA==0)
{ // plane and line are parallel, intersectionpoint is infinitly far away
iPoint.interSect = false;
iPoint.intersectPoint.set(3.4e37f, 3.4e37f, 3.4e37f);
return iPoint;
}

kPar = ((linePoint1.x-trianglePoint1.x)*rv2.y*rv3.z
+rv2.x*rv3.y*(linePoint1.z-trianglePoint1.z)
+(linePoint1.y-trianglePoint1.y)*rv2.z*rv3.x
-rv3.x*rv2.y*(linePoint1.z-trianglePoint1.z)
-rv3.y*rv2.z*(linePoint1.x-trianglePoint1.x)
-rv2.x*(linePoint1.y-trianglePoint1.y)*rv3.z)/detA;

lPar = (rv1.x*(linePoint1.y-trianglePoint1.y)*rv3.z
+(linePoint1.x-trianglePoint1.x)*rv3.y*rv1.z
+rv1.y*(linePoint1.z-trianglePoint1.z)*rv3.x
-rv3.x*(linePoint1.y-trianglePoint1.y)*rv1.z
-rv3.y*(linePoint1.z-trianglePoint1.z)*rv1.x
-(linePoint1.x-trianglePoint1.x)*rv1.y*rv3.z)/detA;

iPoint.intersectPoint.set(trianglePoint1.x+kPar*rv1.x+lPar*rv2.x, trianglePoint1.y+kPar*rv1.y+lPar*rv2.y, trianglePoint1.z+kPar*rv1.z+lPar*rv2.z);

float linePointLength = VECTOR3::distance(linePoint1, linePoint2);
if (kPar>=0 && lPar>=0 && kPar+lPar<=1
&& VECTOR3::distance(linePoint1, iPoint.intersectPoint) <= linePointLength
&& VECTOR3::distance(linePoint2, iPoint.intersectPoint) <= linePointLength)
iPoint.interSect = true;
else
iPoint.interSect = false;
return iPoint;

}


Copy paste, or try to analyze

So how do I found out if the point is within the bounds of p1, p2, p3.
----------------------------------------------------------------------
I used some matrix math (detA, kPar and lPar), this is probably the way you did it. Im not sure but i think
IntersectionPoint = kPar*(trianglePoint2-trianglepoint1)+lPar*(trianglePoint3-trianglepoint1)

Now if(kPar>=0 && lPar>=0 && kPar+lPar<=1), the infinite line intersects the not infinite triangle.
and if (VECTOR3::distance(linePoint1, iPoint.intersectPoint) <= linePointLength && VECTOR3::distance(linePoint2, iPoint.intersectPoint) <= linePointLength), the not infinite line intersects the not infinite triangle.

I hope i'm understandable.

[Edited by - Kwak on May 25, 2006 11:25:09 AM]

Share this post


Link to post
Share on other sites
Thanks guys, ill check those links and many thanks for the code Kwak i will analyze that. copy paste isnt gonna work for me cuz im writing it in C :p

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this