Jump to content
  • Advertisement
Sign in to follow this  
mikenovemberoscar

Simple Ray-Triangle Intersection

This topic is 2859 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

Hello everyone,

After five weeks of struggling I have decided to seek help with my Ray-Triangle Intersection function.

The basic steps are:

1. If the ray isn't intersecting with the triangle's plane, exit.
2. Determine the point of intersection between the ray and the triangle's plane.
3. Choose the largest component (x,y or z) of the triangle's normal, and exclude that component from the 2D projection of the triangle and intersection point (p02D,p12D,p22D,planeintersection2D)
If the normal is pointing UP, the y component is the largest, so project the component onto the XZ plane.


4. Using this test, check if the intersection point is in the 2D triangle.


I'm pretty sure my vector functions are OK but I can't really see what the problem is.

It seems as if the problem is to do with the projections but I can't decipher any more.

Ray-Plane
float rayPlane(vector3D planepoint, vector3D normal, vector3D origin, vector3D direction)
{

// normal.normalise();



float D = (planepoint).dot(normal);




float t = - (normal.x*origin.x + normal.y*origin.y + normal.z*origin.z + D) / (normal.x*direction.x + normal.y*direction.y + normal.z*direction.z );

cout << "t = " << t << endl;



return t;

}




Ray-Triangle:

float rayTriangle(vector3D p0 ,vector3D p1,vector3D p2,vector3D origin ,vector3D direction )
{

// work out planepoint = a point on the plane = a vertex;
// direction.normalise();
vector3D surfacenormal = calcnormal(p0,p1,p2); // work out the triangle's surface normal



float t = rayPlane(p0,surfacenormal,origin,direction); // is the ray intersecting with the triangle's plane?



if (t < 0)// if the ray is isn't pointing towards the triangle's plane
{
cout << "wrong direction" << endl;
return -1; // exit
}




// the ray is pointing towards the triangle's plane


// work out the absolute position of the ray-triangle intersection


vector3D planeintersection(0,0,0);



planeintersection.x = (direction.x * t) ;
planeintersection.y = (direction.y * t) ;
planeintersection.z = (direction.z * t) ;






planeintersection = planeintersection + origin; // adds the origin


// find the appropriate plane (X, Y or Z)

vector3D planeint2D;

vector3D p02D;
vector3D p12D;
vector3D p22D;










// find the range of the x0,x1,x2

vector3D absnormal(fabs(surfacenormal.x),fabs(surfacenormal.y),fabs(surfacenormal.z));

cout << "absnormal = " << absnormal.x << "," << absnormal.y << "," << absnormal.z << "." << endl;


if (absnormal.x > absnormal.y && (absnormal.x > absnormal.z || absnormal.y == absnormal.z) /* or zrange */) // xrange is the smallest OR the y and z are the same and x is less
{
planeint2D.x = planeintersection.z;
planeint2D.y = planeintersection.y;

p02D.x = p0.z;
p02D.y = p0.y;

p12D.x = p1.z;
p12D.y = p1.y;

p22D.x = p2.z;
p22D.y = p2.y;

cout << "excluding x\n";

}
if (absnormal.y > absnormal.x && (absnormal.y > absnormal.z || absnormal.x == absnormal.z) /* or zrange */) // yrange is the smallest
{
planeint2D.x = planeintersection.x;
planeint2D.y = planeintersection.z;

p02D.x = p0.x;
p02D.y = p0.z;

p12D.x = p1.x;
p12D.y = p1.z;

p22D.x = p2.x;
p22D.y = p2.z;
cout << "excluding y\n";

}
if ((absnormal.z > absnormal.y && (absnormal.z > absnormal.x || absnormal.y == absnormal.x) /* or zrange */)) // zrange is the smallest
{
planeint2D.x = planeintersection.x;
planeint2D.y = planeintersection.y;

p02D.x = p0.x;
p02D.y = p0.y;

p12D.x = p1.x;
p12D.y = p1.y;

p22D.x = p2.x;
p22D.y = p2.y;
cout << "excluding z\n";
}



//cout << "surfacenormal: " << absnormal.x << "," << absnormal.y << "," << absnormal.z << "\n";


glPushMatrix();



glLoadIdentity();
glColor4f(0.0f,0.0f,1.0f,1.0f);

glLineWidth(1.0f);
glBegin(GL_LINE_LOOP);
glVertex3f(p02D.x,p02D.y ,-20.0f);
glVertex3f(p12D.x,p12D.y,-20.0f);
glVertex3f(p22D.x,p22D.y,-20.0f);
glEnd();

glPointSize(5.0f);
glColor3f(1.0f,1.0f,0.0f);
glBegin(GL_POINTS);
glVertex3f(planeint2D.x,planeint2D.y,-20.0f);
glEnd();
glPopMatrix();








if (sameside(planeint2D,p02D,p12D,p22D) == 1 && sameside(planeint2D,p12D,p02D,p22D) == 1 && sameside(planeint2D,p22D,p02D,p12D) == 1)
return t;
else
return -1;




}






sameside:

int sameside(vector3D p1, vector3D p2,vector3D l1,vector3D l2)
{
vector3D cp1 = ((l1 - l2 ) * (p1 - l2));
vector3D cp2 = ((l1 - l2 ) * (p2 - l2));

if (cp2.dot(cp1) >= 0)
return 1;

return 0;

}







Thanks


mikey

Share this post


Link to post
Share on other sites
Advertisement
Barycentric Coordinates tutorial:

http://www.flipcode.com/archives/Raytracing_Topics_Techniques-Part_7_Kd-Trees_and_More_Speed.shtml

(Also some nice stuff about KD-trees if you reach a point where you want to check your rays against a truckload of triangles)

Share this post


Link to post
Share on other sites
It's not clear from your description or code. Can you describe what you want to do with the intersection point after you determine it? Are you doing some sort of orthographic projection?

Share this post


Link to post
Share on other sites
Sorry if it's not clear, these are the steps:

1. Intersect the ray with the triangle's plane.

2. Choose the largest component of the triangle's normal, then project the triangle onto the other plane.
e.g if the triangle's normal is pointing in the y direction, project the triangle onto the XZ plane.

3. Perform a 2D triangle point intersection test.

Share this post


Link to post
Share on other sites
Well, now my code looks like this:
(I have added comments to explain what I'm trying to do at each step)



float rayTriangle(vector3D p0 ,vector3D p1,vector3D p2,vector3D origin ,vector3D direction )
{

// work out planepoint = a point on the plane = a vertex of the triangle
// the normal isn't normalised, should I do this?
vector3D surfacenormal = p0 * p1 ; // work out the triangle's surface normal



float t = rayPlane(p0,surfacenormal,origin,direction); // is the ray intersecting with the triangle's plane?



if (t < 0)// if the ray is isn't pointing towards the triangle's plane
{
cout << "wrong direction" << endl;
return -1; // exit
}




// the ray is pointing towards the triangle's plane


// work out the absolute position of the ray-triangle intersection


vector3D planeintersection(0,0,0);

// get the absolute position of t.

planeintersection.x = (direction.x * t) ;
planeintersection.y = (direction.y * t) ;
planeintersection.z = (direction.z * t) ;






planeintersection = planeintersection + origin; // adds the origin


// find the appropriate plane (X, Y or Z)

vector3D planeint2D; // new 2D projected intersection point

vector3D p02D;
vector3D p12D; // new 2D projected triangle
vector3D p22D;












vector3D absnormal(fabs(surfacenormal.x),fabs(surfacenormal.y),fabs(surfacenormal.z)); // make all the normal's components positive


if (absnormal.x > absnormal.y && (absnormal.x > absnormal.z || absnormal.y == absnormal.z) /* or zrange */) // xrange is the smallest OR the y and z are the same and x is less
{
planeint2D.x = planeintersection.z;
planeint2D.y = planeintersection.y;

p02D.x = p0.z;
p02D.y = p0.y;

p12D.x = p1.z;
p12D.y = p1.y;

p22D.x = p2.z;
p22D.y = p2.y;


}
if (absnormal.y > absnormal.x && (absnormal.y > absnormal.z || absnormal.x == absnormal.z) /* or zrange */) // yrange is the smallest
{
planeint2D.x = planeintersection.x;
planeint2D.y = planeintersection.z;

p02D.x = p0.x;
p02D.y = p0.z;

p12D.x = p1.x;
p12D.y = p1.z;

p22D.x = p2.x;
p22D.y = p2.z;
cout << "excluding y\n";


}
if ((absnormal.z > absnormal.y && (absnormal.z > absnormal.x || absnormal.y == absnormal.x) /* or zrange */)) // zrange is the smallest
{
planeint2D.x = planeintersection.x;
planeint2D.y = planeintersection.y;

p02D.x = p0.x;
p02D.y = p0.y;

p12D.x = p1.x;
p12D.y = p1.y;

p22D.x = p2.x;
p22D.y = p2.y;
cout << "excluding z\n";




}


// the previous code just selected the largest component of the normal then excluded that component of the triangle and intersection point

float a2; // barycentric coordinate
float a3; // barycentric coordinate.


vector3D b = p22D - p02D; // direction vector from p2 to p0
vector3D c = p12D - p02D; // direction vector from p1 to p0





a2 = (b.x * planeint2D.y - b.y * planeint2D.x) / (b.x * c.y - b.y * c.x);
a3 = (planeint2D.x * c.y - planeint2D.y * c.x) / (b.x * c.y - b.y * c.x);



if (a2 < 0 || a3 < 0 || a2+a3 > 1)
return -1; // MISS


else
return t; // HIT



}



Share this post


Link to post
Share on other sites
Sorry, I wasn't very clear with my question.
Quote:
Choose the largest component (x,y or z) of the triangle's normal, and exclude that component from the 2D projection of the triangle and intersection point (p02D,p12D,p22D,planeintersection2D)

Why are you doing that? Just so you can use the method for a 2D triangle mentioned in your reference?

If so, meckelmann gave you a much better solution which works in 3D.

EDIT: To augment meckelmann's post:
- Determine the ray-triangle intersection point.
- Calculate the barycentric coordinates (L0, L1, L2) for that point in that triangle.
- Test each barycentric coord: 0 < Lx < 1. If those tests are successful, the ray hit in the triangle.

Share this post


Link to post
Share on other sites
So why does that page state:

Quote:
This can be solved in 3D, but it's cheaper in 2D. Therefore we project the triangle on a 2D plane. Convenient planes for this are the XY, YZ or XZ planes, obviously. To pick the best one of these, we take a look at the normal of the triangle: By using the dominant axis of this vector we get the projection with the greatest projected area, and thus the best precision for the rest of the calculations.

In 2D a2 and a3 can be calculated as follows:

a2 = (bx hy � by hx) / (bx cy � by cx)
a3 = (hx cy � hy cx) / (bx cy � by cx)
?

The new code uses the method of barycentric coordinates from the posted page.

Share this post


Link to post
Share on other sites
Maybe that page was changed after you posted. The link you posted originally doesn't mention 2D vs 3D, etc. At least, I couldn't find it.

EDIT: FYI, take a look at the FAQ (upper right-hand corner) to see how to post links.

Share this post


Link to post
Share on other sites
Quote:

If so, meckelmann gave you a much better solution which works in 3D.


This is a 2D solution. That's what I've been trying to say. I have tried to use it in my code but it doesn't work. That is the code I posted earlier.

Share this post


Link to post
Share on other sites
You're talking about what appears to be an alternative technique to a 3D intersection test that might well be useful. Rather than trying to figure out the theory from the code you posted (as it sounds like you may not be implementing it correctly), it would be more convenient to see the article you're using. Can you post the link?

Also, this looks suspicious:

vector3D surfacenormal = p0 * p1 ; // work out the triangle's surface normal

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!