Jump to content
  • Advertisement
Sign in to follow this  
harmless

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.

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by harmless
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.

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 this post


Link to post
Share on other sites
Quote:
Original post by harmless
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.


Parallel isn't enough. Must be colinear.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Guest Anonymous Poster
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 this post


Link to post
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 this post


Link to post
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).

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!