Ray casting, triangle intersection

Started by
18 comments, last by DenisHorvat 12 years, 10 months ago

Mostly correct.
You will first calculate the normal and plug it in the a,b,c parameters in the equation.
Then replace x,y,z by one of the points on the plane(one of the points of the triangle) and you have got d.
The reset is correct.
Two things to note:
1. if (D * n) = 0 it means that the ray and the plane are parallel hence no intersection.
2. The algorithm described in the linked paper performs ray/triangle intersection yet what I've described only performs ray.plane intersection.
Which means that after you calculated the intersection point of the ray and the plane you still have to check if it lies within the triangle.


Yes. Thank you!

oh...I thought (according to wiki) that I must do the folowing:


Method 2
To describe the plane as an equation in the form ax + by + cz + d = 0, solve the following system of equations:

c3534973d50f86314d66c895f17fb863.pngfff6a2d4cb605565fd098ab85fd1ee2e.pngb39d8ae4509790beeff693e68558d4cd.png This system can be solved using Cramer's Rule and basic matrix manipulations. Let

3ce6b7e89b269396089e2b23c555f52d.png. If D is non-zero (so for planes not through the origin) the values for a, b and c can be calculated as follows:

b3432de82d70979fe35b1ab73ff7be6a.png c2e79e92ff115015b55f87ffd085301d.png 10b4308580b13de805c6f8c478227790.pngAnd then:

a463f034c5002b73ff7d03bc79fc8075.pngI dont se a normal in the equasion. What did you ment by: "normal and plug it in the a,b,c"
Advertisement
So, I've this is what I have done (can someone give me confirmation that I am doing this correctly):


float t;
float a, c;
vector3 b, pointOnPlane;

for(int i = 0; i < hitTestPoints.size(); i++)
{
for(int j = 0; j < model->triangles.size(); j++)
{
a = model->triangles[j].normal * rayOrientation; //rayOrientation (0,1,0)
//if a == 0 then the ray is paralel to the plane, hence no intersection
if(a == 0)
{
continue;
}
b = model->triangles[j].v3 - hitTestPoints;
c= model->triangles[j].normal * b;
t = c/a;
//if intersection point is not behind the ray
if(t < 0)
{
continue;
}
//calculate intersection point
b.x = t*b.x;
b.y = t*b.y;
b.z = t*b.z;
pointOnPlane = hitTestPoints + b;

}
}

}


hitTestPoints are the ray origins
Suspecting my last attempt was a fail, here is a new attempt that I think is correct:


void OpenGLControl::hitTest()
{

float t;
float a, b;
vector3 b, pointOnPlane, tempPoint;
float distance;


for(int i = 0; i < hitTestPoints.size(); i++)
{
for(int j = 0; j < model->triangles.size(); j++)
{
//N.D normal . (0,1,0)
a = model->triangles[j].normal * rayOrientation;
//if plane is paralel to ray
if(a == 0)
{
continue;
}
//N.v3 normal . one point on plane (one of the vertices)
//ax + by + cz + d = 0 wich can be rewritten as N.v3 + d = 0 => d = -(N.v3)
distance = -(model->triangles[j].normal*model->triangles[j].v3);
//origin . normal + distance ( N.O + d )
b = hitTestPoints * model->triangles[j].normal + distance;
t = (-b)/a;
//intersection is behind the ray
if(t < 0)
{
continue;
}
//calculate the point
tempPoint = rayOrientation*t;
pointOnPlane = hitTestPoints + tempPoint;
}
}
}
Hi, can anyone tell me what are we suppose to know to implement in OpenGL ?

I found this, vectors, cross/dot product concept ...

http://www.lighthous...utorials/maths/

Is there any example, tutorials ?

Suspecting my last attempt was a fail, here is a new attempt that I think is correct:


void OpenGLControl::hitTest()
{

float t;
float a, b;
vector3 b, pointOnPlane, tempPoint;
float distance;


for(int i = 0; i < hitTestPoints.size(); i++)
{
for(int j = 0; j < model->triangles.size(); j++)
{
//N.D normal . (0,1,0)
a = model->triangles[j].normal * rayOrientation;
//if plane is paralel to ray
if(a == 0)
{
continue;
}
//N.v3 normal . one point on plane (one of the vertices)
//ax + by + cz + d = 0 wich can be rewritten as N.v3 + d = 0 => d = -(N.v3)
distance = -(model->triangles[j].normal*model->triangles[j].v3);
//origin . normal + distance ( N.O + d )
b = hitTestPoints * model->triangles[j].normal + distance;
t = (-b)/a;
//intersection is behind the ray
if(t < 0)
{
continue;
}
//calculate the point
tempPoint = rayOrientation*t;
pointOnPlane = hitTestPoints + tempPoint;
}
}
}



I've only glanced at the code but it seems correct, now all is left is just a 2d point in triangle test...
Does it account for hitting the back of a plane too? Most of the time you'll want to hit only one side of a triangle.

Interested in Fractals? Check out my App, Fractal Scout, free on the Google Play store.

Ok, here is where I'm at. I think I understand all the math behind this.
HOW I CALCULATE POINT ON THE PLANE:
  1. calculate Vd: normal . orientation (orientation is (0,1,0))
  2. check if Vd == 0, then go to next iteration - ray is paralel
  3. calculate distance: d = abs((vertex3 - rayOrigin) . normal); vertex3 is one of the 3 vertices on the plane
  4. calculate V0: -(normal . rayOrigin + distance)
  5. calculate t: t = V0/Vd
  6. check if t < 0, then behind the ray, go to next iteration
  7. calculate the point on plane: pointOnPlane = t . orientation + rayOrigin
. is dot product, v3 is one of the vertices in the triangle. I dont know what is wrong.


My new code:


float t;
float Vd, V0;
vector3 pointOnPlane;
float distance;
vector3 nNormal;
int interCount = 0;

for(int i = 0; i < hitTestPoints.size(); i++)
{
interCount = 0;
for(int j = 0; j < model->triangles.size(); j++)
{
//N.D normal . (0,1,0)
nNormal = support::normalize(model->triangles[j].normal);
Vd = nNormal * rayOrientation;
//if plane is paralel to ray
if(Vd == 0)
{
continue;
}
//calculate the distance: (vertex3 - origin)*normal
distance = abs((model->triangles[j].v3 - hitTestPoints) *nNormal);
//-(normal*origin)+distance
V0 = -((nNormal* hitTestPoints) + distance);
t = V0/Vd;
//intersection is behind the ray
if(t < 0)
{
continue;
}
//calculate the point: orientation*t + origin
pointOnPlane = rayOrientation*t + hitTestPoints;
if(checkSide(pointOnPlane, model->triangles[j].v1, model->triangles[j].v2, model->triangles[j].v3))
{
if(checkSide(pointOnPlane, model->triangles[j].v2, model->triangles[j].v1, model->triangles[j].v3))
{
if(checkSide(pointOnPlane, model->triangles[j].v3, model->triangles[j].v2, model->triangles[j].v1))
{
interCount++;
}

}

}
}

if(interCount%2==1)
{
pointsInModel.push_back(hitTestPoints);
}
interCount = 0;
}

}


And this is what I get if I draw the points on plane (which you can see they are incorrect)
http://imageshack.us/photo/my-images/121/error2oa.png/
Blue - point on plane; Green - ray origin

@Nanoha - I take this into calculation with t < 0, then I skip the iteration.
Taking the plane equation as ax + by + cz - d = 0
we get that d = ax + by + cz
so by substituting a,b,c by the plane normal and x y z by some point on it we get d.
Then we know that:
t = (d - O*n) / (D * n)
where t is the distance along the ray direction, O is the ray origin, D is the ray direction, n is the plane normal and d is the value we calculated above.
calculate distance: d = abs((vertex3 - rayOrigin) . normal); vertex3 is one of the 3 vertices on the plane[/quote]
So, d should be either vertex3 * normal or -(vertex3 * normal) depending how you wrote the plane equation.
calculate V0: -(normal . rayOrigin + distance)[/quote]
Again V0 should be either d - rayOrigin * normal or rayOrigin * normal - d.

Make sure you understand the equations and follow the calculation.

Taking the plane equation as ax + by + cz - d = 0
we get that d = ax + by + cz
so by substituting a,b,c by the plane normal and x y z by some point on it we get d.
Then we know that:
t = (d - O*n) / (D * n)
where t is the distance along the ray direction, O is the ray origin, D is the ray direction, n is the plane normal and d is the value we calculated above.
calculate distance: d = abs((vertex3 - rayOrigin) . normal); vertex3 is one of the 3 vertices on the plane

So, d should be either vertex3 * normal or -(vertex3 * normal) depending how you wrote the plane equation.
calculate V0: -(normal . rayOrigin + distance)[/quote]
Again V0 should be either d - rayOrigin * normal or rayOrigin * normal - d.

Make sure you understand the equations and follow the calculation.
[/quote]

Im little confused: Isn't d distance from an origin point to the plane? Btw, I am very grateful that you are helping me despite my stupidity.
d is the distance of the plane from the origin - (0,0,0). So d is a property of the plane and does not depend on any other value.
To define a plane you need a normal. But that is not enough. There is an infinite amount of planes sharing the same normal. Adding d makes the plane unique.
But it doesn't matter too much what d represents as long as you follow the two equations that define a plane and a ray.

This topic is closed to new replies.

Advertisement