Jump to content
• Advertisement

# Im about to have a nervous breakdown (Collision Detection)

This topic is 4466 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

## 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

##### Share on other sites
Advertisement
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

##### 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

##### 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

##### 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

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
3. 3
frob
15
4. 4
5. 5
• Advertisement

• 9
• 20
• 12
• 13
• 14
• ### Forum Statistics

• Total Topics
632143
• Total Posts
3004419

×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!