Im about to have a nervous breakdown (Collision Detection)
Author
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 :)
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".
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".
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
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
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
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]
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]
Author
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
