# Yet another Ray-Triangle Intersection Test Question

This topic is 5124 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi everyone, I already have a function that checks for intersection between a ray and triangle and the pseudo code works like this: 1. derive the plane where the triangle is on 2. check for the ray intersection with the above plane 3. if intersection exists, calculate the intersection points 4. check if the point is inside the triangle Now my problem is on item 2. If ray is parallel to plane AND lies on the plane, and assuming the the origin of ray is not inside the triangle, then the intersection point will be somewhere along the edges of the triangle. Currently, if this is the case, i just perform ray-segment intersection check with ray against each of the 3 edges ofthe triangle. It does work though. however, i am not too sure if this is the best way to approach this problem. I appreciate any advise on this problem. thanks! [Edited by - harmless on December 6, 2004 1:48:50 AM]

##### Share on other sites
Just assume that if ray is parallel to plane and lies on that plane, it does not intersect that plane. It's OK for any sane use on computers. Your ray and your plane is already non-perfect.

Even if you'll especially handle that case you'll have 'problems' with precision (if ray "should be" parallel, but only slightly inparallel due to inprecision, it will not work)

In 3D that issue corresponds to handling border of triangle especially.

##### Share on other sites
Yes i am aware of the imprecision issue. but i am concerned about the rare possibility that ray is perfectly parallel to triangle, in which case it hits one of the edges of the triangle.

##### Share on other sites
Quote:
 Original post by harmlessYes i am aware of the imprecision issue. but i am concerned about the rare possibility that ray is perfectly parallel to triangle, in which case it hits one of the edges of the triangle.

What you are coding? Raytracer? Collision detection? None of such applications requirs what you want to do. Even more, it is more valid assumption to assume tha parallel rays do not intersect plane at all no matter what. Unless you want to use your 3D code for 2D things, it is totally unnecessary to handle singular cases. You must only check not to divide by zero in intersection code.

If you turn your camera by any extremely small amount, image shouldn't change much, right? But if you somehow placed camera that there is some rays parallel to triangle, any small turn of camera will make that there will be no rays parallel to triangle.

Also, if your triangles is in mesh, parallel ray will intersect neighbouring triangles anyway.

[Edited by - Dmytry on December 6, 2004 6:21:35 AM]

##### Share on other sites
Quote:
 Original post by harmlessYes i am aware of the imprecision issue. but i am concerned about the rare possibility that ray is perfectly parallel to triangle, in which case it hits one of the edges of the triangle.

Parallel isn't enough. Must be colinear.

##### Share on other sites
just define an intersection to be a point on your ray where the ray goes from one side of a surface to the other one. voila, no conflict.

that way, a colinear ray and triangle arnt intersecting, and as other have mentioned, youre not going to see the slightest bit of difference in the endresult.

the reason why you want to define such cases as no intersection is because its a physicly impossible situation anyway, and hence might give rise to singularities/oddities in further calculations.

##### Share on other sites
If this is for a collision system as for a game, technically you'd never be parallel and lie on the plane. Assuming that all objects are closed, you would hit the poly joining the other poly that is parallel to your ray first.

   |  A|   |   |_________        B   |   |   |   R

If you have ray R, it's parallel to plane A, but technically would hit the edge of plane B first. If that makes more sense.

##### Share on other sites
If I'm not totally wrong then there is a better way to calculate triangle-ray intersection. There is a method that uses barycentric-coordinates to calculate the exact intersection point without calculating the normal of the triangle.

As soon as planes are used in intersection detection then you are heading for trouble. Just look at all the issues with precision when using k-DOPs or all the instable triangle-triangle intersection implementations that are availible on the net. The problem is that a normal n can't span u x v (in theory it does).

/__fold

##### Share on other sites
Try the Moller-Trumbore method here, there are other algorithms that *may* give better performance but this one is pretty good.

(some code in OCaml ;)
let closest_ray_intersect tri ray tmin tmax =  let origin = Ray.org ray in  let direction = Ray.dir ray in  let epsilon = 0.000001 in  let edge1 = Vector3.sub tri.p1 tri.p0 in  let edge2 = Vector3.sub tri.p2 tri.p0 in  let pvec = Vector3.cross direction edge2 in  let det = Vector3.dot edge1 pvec in  if (det > ~-.epsilon) && (det < epsilon) then    Intersection.None  else    let inv_det = 1.0 /. det in    let tvec = Vector3.sub origin tri.p0 in    let u = (Vector3.dot tvec pvec) *. inv_det in    if u < 0.0 || u > 1.0 then      Intersection.None    else      let qvec = Vector3.cross tvec edge1 in      let v = (Vector3.dot direction qvec) *. inv_det in      if v < 0.0 || (v +. u) > 1.0 then        Intersection.None      else        let t = (Vector3.dot edge2 qvec) *. inv_det in        if not ((t < tmin) || (t > tmax)) then          Intersection.Hit (t, Vector2.make u v )        else          Intersection.None

##### Share on other sites
I posted the most stable method for determining ray-tri here (at the bottom)

note that, triangles which are coplanar with the ray will return no intersection, as there is no unique value t for the intersection (technically, it rejects because the last test is > 0.0f instead of >= 0.0f, which means that it will miss any intersection that falls directly on the t1,t2 edge... I view this as a benefit, however, because for 2/3 of cases in mesh where ray intersects exactly a triangle edge, the test will return true for exactly one triangle, and not both that share the edge).

You can easily change the code to get exactly the behavior you want, by noting that a determinant == 0.0f means it hits an edge. 2 determinants == 0.0f means it hits the vertex shared by the two corresponding edges. All 3 == 0.0f means coplanar, the 'bad news' case.

This is much better than moller trumbore, IMO. I wrote an SSE version of this algorithm that determines ray-tri on batches of indexed triangle lists in 67 cycles per triangle, with no branching except to loop (which is predicted correctly on every iteration except the last).

1. 1
2. 2
Rutin
20
3. 3
khawk
18
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633763
• Total Posts
3013728
×