Sign in to follow this  
h3ro

Ray / Triangle intersection code

Recommended Posts

Hallo, Im working on the collision detection part of my program and have it partially working. Right now it works in some cases, but fails in other A triangle made like this works: 0.00 0.00 0.00 -150.00 0.00 0.00 0.00 150.00 0.00 But a triangle like this does not work. 0.00 0.00 0.00 -150.00 0.00 0.00 0.00 -150.00 0.00 Any ideas on what I am doing wrong?
result Triangle::intersectionTest(Ray r)
{
       // structure for holding the result of the test
       result res;
      
       Vector3D vertexAB = v2 - v1;
       Vector3D vertexAC = v3 - v1;
       
       // Find the cross product of vertexAC and the ray direction
       Vector3D acCrossRayDir = Cross(r.getDirection(), vertexAC);
       
       // Find the divisor
       float div = Dot (vertexAB,acCrossRayDir);
       float invDiv = 1/ div;
       
       if (div < 0.000001)
       {
               res.hit = 0;
               return res;
       }
       
       Vector3D rayO = PointToVector3D(r.getOrigin());
       Vector3D rayPointVector = rayO - v1;
       
       // Check if triangle is in front of ray or not
       float test1 = Dot(rayPointVector,acCrossRayDir);
       if (test1 < 0.0 || test1 > div)
       {
                 res.hit = 0;
                 return res;
       }
       
       Vector3D test2vector = Cross(rayPointVector,vertexAB);
       float test2 = Dot(r.getDirection(), test2vector);
       if (test2 < 0.0 || test1 + test2 > div)
       {
                 res.hit = 0;
                 return res;
       }
       
       res.hit = 1;
       res.distance =Dot(vertexAC, test2vector) * invDiv;
       return res;      
}
 

Thanks for your time :) [Edited by - h3ro on May 14, 2007 10:52:22 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by h3ro
A triangle made like this works:
0.00 0.00 0.00
-150.00 0.00 0.00
0.00 150.00 0.00

But a triangle like this does not work.
0.00 0.00 0.00
-150.00 0.00 0.00
0.00 150.00 0.00


I think you mistyped something... there doesn't appear to be a difference between the two.

I'm not sure I follow the logic of your intersection test--granted I only did a quick skimming of it. I usually find point of intersection for the ray and the plane containing the triangle. Then I use barycentric coordinates to determine if that point lies within the triangle.

Share this post


Link to post
Share on other sites
Your right, I miss typed one of the coordinates(fixed now).
To be honest I am not to sure about how to do this and are currently looking for a simple computer graphic math book.

I use barycentric coordinates as well I think. v1,v2 and v3 are the coordinates of the triangle.

Share this post


Link to post
Share on other sites
This isn't as complicated as it might look initially, so bare with me and try to visualize it as you read... maybe make a sketch. I am going to assume that you know how to calculate the ray-plane intersection for brevity.

You would first find the point at which the ray strikes the plane of the triangle (let's call the triangle T). Let's call this ray-plane intersection point P, with P0, P1, and P2 being the vertices of the triangle. You then will calculate barycentric coordinates to determine if P is inside of triangle P0-P1-P2.

To calculate the barycentric coordinates: Use intersection point P to create 3 separate triangles out of the T's vertices: P-P0-P1, P-P1-P2, and P-P2-P0, which we will call T0, T1, and T2 respectively.

You will calculate the areas of T, T0, T1, T2 (call them A(T), A(T0), A(T1), A(T2)).

The barycentric coordinates of intersection point P are then A(T0)/A(T), A(T1)/A(T), and A(T2)/A(T). In other words, they are the new triangles' areas as a fraction of the original triangle's areas.

If the intersection point P is inside of the triangle, then those 3 values will each fall between 0.0 and 1.0, and will add up to 1.0 (100% of the original triangle's area). If any of those values is below 0.0 or above 1.0, then you can bail out and return false (a miss) without wasting time computing the others.

Share this post


Link to post
Share on other sites
I think my problem was that I had if (barycCoord_1 < 0.0 || barycCoord_1 > div), where div is not 1.0 so the test would fail as this point.

When I are doing the things that add to s1 and s2, what am I really doing there? As I said before, I really need a math book for this stuff. Maybe someone could recommend one for me? I know basic algebra and trigonometry, but thats about it

Thanks.

Btw: In my last post it should be "working now" not "working not". Stupid typo, sorry

Here is my new and working code:
result Triangle::intersectionTest(Ray r)
{
// structure for holding the result of the test
result res;

Vector3D edge1 = v2 - v1;
Vector3D edge2 = v3 - v1;

// Find the cross product of edge2 and the ray direction
Vector3D s1 = Cross(r.getDirection(), edge2);

// Find the divisor, if its zero, return false as the triangle is
// degenerated
float divisor = Dot (s1 ,edge1);
if (divisor == 0.0)
{
res.hit = 0;
return res;
}

// A inverted divisor, as multipling is faster then division
float invDivisor = 1/ divisor;


// Calculate the first barycentic coordinate. Barycentic coordinates
// are between 0.0 and 1.0
Vector3D distance = PointToVector3D(r.getOrigin()) - v1;
float barycCoord_1 = Dot(distance, s1) * invDivisor;
if (barycCoord_1 < 0.0 || barycCoord_1 > 1.0)
{
res.hit = 0;
return res;
}


// Calculate the second barycentic coordinate
Vector3D s2 = Cross(distance, edge1);
float barycCoord_2 = Dot(r.getDirection(), s2) * invDivisor;
if (barycCoord_2 < 0.0 || (barycCoord_1 + barycCoord_2) > 1.0)
{
res.hit = 0;
return res;
}

// After doing the barycentic coordinate test we know if the ray hits or
// not. If we got this far the ray hits.
// Calculate the distance to the intersection point
float intersectionDistance = Dot(edge2, s2) * invDivisor;

res.hit = 1;
res.distance = intersectionDistance;
return res;
}

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