Sign in to follow this  
LewsTherin

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

Recommended Posts

LewsTherin    139
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;
  qvec.cross(e1);

  // 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
daftasbrush    252
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.

HTH

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

Share this post


Link to post
Share on other sites
Daerax    1207
Quote:
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

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