# Ray / Triangle intersection code

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

## 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 on other sites
Quote:
 Original post by h3roA triangle made like this works:0.00 0.00 0.00-150.00 0.00 0.000.00 150.00 0.00But a triangle like this does not work.0.00 0.00 0.00-150.00 0.00 0.000.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 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 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 on other sites
Thanks for the help and the encouragement to do some research. It works not after rewriting it. :)

##### Share on other sites
Quote:
 Original post by h3roThanks for the help and the encouragement to do some research. It works not after rewriting it. :)
What did you do to make it work?

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

1. 1
2. 2
3. 3
Rutin
12
4. 4
5. 5

• 26
• 10
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633695
• Total Posts
3013382
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!