Jump to content
  • Advertisement
Sign in to follow this  

Can I get a sanity check on ray/triangle intersections?

This topic is 4412 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'm trying to write a function to determine if a ray intersects with a triangle. Don't need any information about where, just if. The problem is, the results coming from it don't seem to make any sense. I'll render a ray and triangle in OpenGL, and they seem quite separate. But the function insists they intersect. I've modeled my code on that found in this article. My code, while different, is getting the same results as theirs. Here's my code:
const double EPSILON = 0.000001;
bool line_intercepts_triangle(const Ray& r, const Triangle& t){
  // Normals for the triangle's edges.
  Vector e1(t.b, t.a), // Normal from vertex 1 to vertex 0
         e2(t.c, t.a); // Normal from vertex 2 to vertex 0

  // pvec = the cross product of the ray's direction and the v2-v0 normal
  Vector pvec;
  pvec.cross(r.d, e2);

  // Determinant
  double det = e1.dot_product(pvec);

  // If the determinant is 0, the ray is on the same plane as the triangle
  // Determinant == 0, modified for floating point imprecision
  if (det > -EPSILON && det < EPSILON)
    return false;

  // Inverse determinant
  double inv_det = 1.0 / det;

  // Distance from vertex 0 to the origin of the ray
  Vector tvec(r.o, t.a);

  // Calculate U value, and ensure it is valid
  double u = tvec.dot_product(pvec) * inv_det;
  if (u < 0.0 || u > 1.0)
    return false;

  // ??
  Vector qvec = tvec;

  // Calculate V value, and ensure it is valid
  double v = r.d.dot_product(qvec) * inv_det;
  if (v < 0.0 || u + v > 1.0)
    return false;

  return true;
The ray I am testing with: from (-0.0833333, 0.0833333, 0.25) in direction (-0.771634, 0.45399, 0.445504) ( I know the numbers are wierd, sorry about that) The triangle: (0.25, -0.25, 0.25, 0.25, -0.25, -0.25, 0.25, 0.25, -0.25) The render, which seems to indicate the ray and triangle do not intersect.

Share this post

Link to post
Share on other sites
Does the ray intersect the triangle if you go backwards? From your picture it looks like it does. I don't know how the algorithm works but it may handle lines and not rays. You could do a simple halfspace test with the ray direction as the plane normal and a vertex of the triangle as the halfspace test point to see if its on the correct side.

Share this post

Link to post
Share on other sites
I think StormArmageddon is right.... the ray does intersect the triangle if you go backwards.
Looking at the original algorithm and code.. it calculates t the (signed) distance from ray origin to intersection, but doesn't check it.. it simply returns the value.

Your version does not even calculate it.. presumably you didn't see the need since (from the original code) the value of t "seems" to have no effect on whether the ray intersects the triangle... but it does.

If you ignore t then your test is line-triangle, rather than ray-triangle.

For Ray-Triangle you need to calculate t, and check it's value.
t > 0 will confirm the intersection is in the "forward" direction of the ray.


[Edited by - daftasbrush on May 20, 2006 6:16:34 PM]

Share this post

Link to post
Share on other sites
Thanks, it seems the code was checking for lines rather than rays. I had hoped to avoid calculating t, to speed up the code.

Share this post

Link to post
Share on other sites
Original post by LewsTherin

hmm.. I thought you only existed in somebodies head. i.e. you are dead?

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!