Sign in to follow this  

ray - triangle intersection

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

I am implementing the algorithm given in the following paper to determine the location of intersection of a ray with a triangle: http://www.graphics.cornell.edu/pubs/1997/MT97.pdf My problem: A mechanical part is displayed on the screen. The part is defined by a mesh. So in-last, I get an array of triangles from a text file that I transform by an MV matrix and then display onto the screen. Then the user clicks on the screen at some position, lets say (x,y) and I cast a ray from (x,y) parallel to the z axis and determine the triangles that are intersected by this ray. My Questions: Do I have to apply some transformation (like MV) on to the ray which is cast parallel to the z-axis from the (x,y) location? if yes, do I need to apply both MV and projection matrices or only MV? thanks in advance

Share this post


Link to post
Share on other sites
Typically you would construct the pick ray in world space, and then transform it into the local space of the mesh using the inverse of the mesh model matrix. This is quite straightforward to do if you have your own math code (or a third-party library), but can be somewhat awkward to do via OpenGL function calls.

To answer your specific question, generally speaking the matrix you want to apply is not M, V, or MV, but rather M^-1.

(Also, this is more of a 'Math & Physics' question than an OpenGL question.)

Share this post


Link to post
Share on other sites
Since this is OpenGL, you can circumvent the whole transformation issue by using GL specific functions that take perspective and modelview matrices into account. In particular, gluUnProject and gluProject will be of use.

Share this post


Link to post
Share on other sites
Quote:
Original post by Hnefi
Since this is OpenGL, you can circumvent the whole transformation issue by using GL specific functions that take perspective and modelview matrices into account. In particular, gluUnProject and gluProject will be of use.
That won't help with transforming the pick ray into the local space of the model though.

(Actually, I may be misunderstanding the question. If the OP is just asking about how to construct a pick ray, then yeah, the GLU functions mentioned above should do the trick.)

Share this post


Link to post
Share on other sites
Sure. I had problems with it a few days ago and posted a topic here. The final post, constructed with the help of the great people on this forum, contains a simple, working solution for picking with gluUnProject.

Do note that as jyk says, gluUnProject will give you a point in the world coordinate system, NOT your mesh coordinate system.

Share this post


Link to post
Share on other sites
thanks a lot,

The problem is solved though the use of glProject method. I project the vertices of the triangle from the object space to the screen space and then look for intersections.

One more question though (tell me if code is needed)!!

I want to know how far away was the intersection from the origin of the ray. Ray ofcourse originates from the screen and travels parallel to the z-axis.

The problem is that all the vertices of all the triangles have thier z coordinate set to 0.98. This is kindda strange and I am not able to figure out why this is always coming like this, as it is a wrong.

Can someone hint about the problem. May be I need not to project using all three matrices, i.e Projection, modelview and viewport

thanks

[Edited by - me_here_me on July 12, 2007 9:27:08 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by me_here_me
thanks a lot,

The problem is solved though the use of glProject method. I project the vertices of the triangle from the object space to the screen space and then look for intersections.

One more question though (tell me if code is needed)!!

I want to know how far away was the intersection from the origin of the ray. Ray ofcourse originates from the screen and travels parallel to the z-axis.

The problem is that all the vertices of all the triangles have thier z coordinate set to 0.98. This is kindda strange and I am not able to figure out why this is always coming like this, as it is a wrong.

Can someone hint about the problem. May be I need not to project using all three matrices, i.e Projection, modelview and viewport

thanks
This isn't really a complete answer, but if I were you I'd do the picking in world or model space, not screen space (this will give you the depth/distance that you're looking for, and may help you avoid other potential problems as well).

Share this post


Link to post
Share on other sites
Hi,
Now the code is changed. The line is projected from the screen space to the object space and correctly determines an intersection and the number of intersections. Although the distance from the origin of the ray to the intersection point is wrongly calculated :(

Following is the code:

[SOURCE]
int COpenGLCanvas2::intersect_triangle(vector3 orig, vector3 dir, vector3 vert0, vector3 vert1, vector3 vert2,
double *t, double *u, double *v){
// orig = origin of the ray (x,y,0)
// dir = direction of the ray (0,0,1)
// vert0, vert1, vert2 are the vertices of the triangle in question

static GLdouble modelmatrix[16];
static GLdouble projmatrix[16];
static GLint viewport[4];

glGetDoublev(GL_MODELVIEW_MATRIX, modelmatrix);
glGetDoublev(GL_PROJECTION_MATRIX, projmatrix);
glGetIntegerv(GL_VIEWPORT, viewport);

static GLdouble x0, y0, z0, x1, y1, z1, x2, y2, z2;

// converting from the windows coordinate system with centre in top left to the openGL coordinate system
orig.y = (float)viewport[3] - (float)orig.y;

// Following method is used to project the line and point from the screen space to the object space
gluUnProject(orig.x, orig.y, orig.z, modelmatrix, projmatrix, viewport, &x0, &y0, &z0);
gluUnProject(orig.x + dir.x, orig.y + dir.y, orig.z + dir.z, modelmatrix, projmatrix, viewport, &x1, &y1, &z1);

orig.x = x0; orig.y = y0; orig.z = z0;
dir.x = x1 - x0; dir.y = y1 - y0; dir.z = z1 - z0;

vector3 edge1, edge2, pvec, tvec, qvec;
double det,inv_det;

/* find vectors for two edges sharing vert0 */
edge1.copy(vert1); //subtracting vert0 from vert1 and storing in edge1
edge1 -= vert0;

edge2.copy(vert2); //subtracting vert0 from vert2 and storing in edge2
edge2 -= vert0;

/* begin calculating determinant - also used to calculate U parameter */
pvec = dir.cross(edge2);

/* if determinant is near zero, ray lies in plane of triangle */
det = pvec.dot(edge1);
if (det > -EPSILON && det < EPSILON)
return 0;

inv_det = 1.0 / det;

/* calculate distance from vert0 to ray origin */
tvec.copy(orig); //subtracting vert0 from orig and storing in tvec
tvec -= vert0;

/* calculate U parameter and test bounds */
*u = (pvec.dot(tvec)) * inv_det;
if (*u < 0.0 || *u > 1.0)
return 0;

/* prepare to test V parameter */
qvec = tvec.cross(edge1);

/* calculate V parameter and test bounds */
*v = (qvec.dot(dir)) * inv_det;
if (*v < 0.0 || *u + *v > 1.0)
return 0;

/* calculate t, ray intersects triangle */
*t = (qvec.dot(edge2)) * inv_det; //SOULD CONTAIN THE DISTANCE BETWEEN RAY ORIGIN AND INTERSECTION

return 1;
}
[/SOURCE]
[/source]

I will also post this thread in the Math and Physics forum:)

Share this post


Link to post
Share on other sites

This topic is 3804 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.

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