Skip to main content
gamedev.net
🔒 Locked

Ray/Triangle intersection... again!

OpenGL
Started by resle 3 replies 2.4k views
Original Post
resle
resle
Greetings,

I bet the topic has been covered 1000 times, and even myself - I've coded the damn thing again and again through many interations of opengl versions and languages.

This time I am having a hard time debugging, since Javascript and Webgl aren't exactly debugging-friendly.

First: building the ray.
I am using the GLUUnproject function which I found here: https://github.com/fintler/webgl-unproject/blob/master/GLU.js
Simple and clean, not much to explain.

Second: the intersection itself
I've coded this from scratch, basing myself on this paper http://www.cs.virginia.edu/~gfx/Courses/2003/ImageSynthesis/papers/Acceleration/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf

The code looks like this


function check(vert0, vert1, vert2, orig, dir)
{
// OUT
var t,u,v;
// VAR
var edge1 = vec3.create();
var edge2 = vec3.create();
var tvec = vec3.create();
var pvec = vec3.create();
var qvec = vec3.create();
var det, inv_det;

// find vectors for edges
vec3.subtract(vert1, vert0, edge1);
vec3.subtract(vert2, vert0, edge2);

// calculate determinant
vec3.cross(dir, edge2, pvec);
det = vec3.dot(edge1, pvec);

// calculations - CULLING ENABLED
vec3.subtract(orig, vert0, tvec);

u = vec3.dot(tvec,pvec);
if(u<0 || u>det) return null;

vec3.cross(tvec, edge1, qvec);

v = vec3.dot(dir, qvec);
if(v<0 || (u+v)>det) return null;

t = vec3.dot(edge2,qvec);
inv_det = 1/det;
t = t * inv_det;
u = u * inv_det;
v = v * inv_det;

return vec3.create([t,u,v]);
}




Then I drew the simplest triangle ever and checked against it, failing.
I've double checked all the values that I pass to the functions (both GluUnproject and Check), and they're correct.
Nonetheless Check() fails.

I think I may be doing something wrong in creating the ray, possibly because I am using a right-hand camera system.
Do you see anything that may be wrong?
Can someone tell me how to "build" manually a ray that goes straight from the center of the screen to the horizon?

Thanks in advance

andrea
..so we ate rare animals, we spent the night eating rare animals..
Vilem Otte
Vilem Otte
Hi andrea,

ray triangle intersections are not part of OpenGL, they must be written separately ... anyway to the topic.

Anyway as you use culling, make sure your winding order is correct (it should be counter-clockwise afaik, but not sure) - try flipping second and third vertices for Check function (if it works, than your winding order is wrong and you see (don't see) back face of your triangle). Ray from the center of screen will have origin and camera and direction in its view vector. Don't forget to normalize ray direction! Otherwise you won't get correct result.

On that article - the test they're using suck (unless you use clipping, and single sided triangles aren't that common), it is a bit outdated (2003), and the culling version is good just because it moves the ugly division to the end ... plus there is evil (very evil) epsilon ... yuk! Although basically every barycentric test (like you're using) can be drilled to Moller ...

For good CCW (Counter clockwise triangles only) test, one can use Arenberg test. Otherwise using Badouel can be good ... anyway standard barycentric (like Moller is also a good way to go).

resle
resle
Hi Vilelm, thanks for your hints.

To complete the picture, I never actually coded a ray-triangle intersection test before - since in the early days of OpenGL I used to rely on backreading the depth buffer and with that, I could track a single pixel in 3d space without much hassle.

Now that backreading is gone, I am trying to pickpoint a single (x,y,z) point out of a very large terrain.
I definitely need to discard the culled triangles, that's why I chose that article although outdated... I am looking into the Arenberg test but I am having a hard time finding a proper algorithmical description of that.

My doubts are falling, mostly, on: ehat should I pass exactly to GLU.unProject as ModelView matrix. I have a camera matrix representing the ... camera which moves on the terrain, and it's a plain 4x4 matrix which only tells me where (posx, posy, posz, rotx, roty, rotz) the camera is currently. I also have a single matrices for every object in the world, which I separately multiply by the camera matrix, one by one as needed.
..so we ate rare animals, we spent the night eating rare animals..
RobTheBloke
RobTheBloke

My doubts are falling, mostly, on: ehat should I pass exactly to GLU.unProject as ModelView matrix. I have a camera matrix representing the ... camera which moves on the terrain, and it's a plain 4x4 matrix which only tells me where (posx, posy, posz, rotx, roty, rotz) the camera is currently. I also have a single matrices for every object in the world, which I separately multiply by the camera matrix, one by one as needed.


Compare the matrix you are passing to gluUnproject, with the GL_MODELVIEW_MATRIX set at the point where you render the triangle (you can grab the matrix using glGet). It's one of those fiddly bit's that can take a little bit of faffing about to achieve.
dpadam450
dpadam450
When I dealt with rays from the camera and unproject I did the following to debug:

On(KeyPress())
{
saveCameraPosition();
saveRayEndPoint();
}

You can draw the ray as GL_LINE. when moving the camera verify the ray you made is actually intersecting the triangle first and that maybe your ray isnt backwards.
NBA2K, Madden, Maneater, Killing Floor, Sims 

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.