# ray - triangle intersection

## Recommended Posts

me_here_me    102
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 on other sites
jyk    2094
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 on other sites
Hnefi    386
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 on other sites
jyk    2094
Quote:
 Original post by HnefiSince 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 on other sites
me_here_me    102
thanks all of u for ur replies

Hnefi!! can u elaborate a bit how to use these if u have some time

thanks

##### Share on other sites
Hnefi    386
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 on other sites
me_here_me    102
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 on other sites
jyk    2094
Quote:
 Original post by me_here_methanks 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 on other sites
me_here_me    102
ok :)

I will try converting the line from the screen to the object space rather then objects into the screen space and lets see how is goes.

thanks for the help

##### Share on other sites
me_here_me    102
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:)