Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


Is my triangle intersection code correct?

  • You cannot reply to this topic
2 replies to this topic

#1 IsItSharp   Members   -  Reputation: 192

Like
0Likes
Like

Posted Today, 03:14 AM

I was wondering if my triangle intersection code is correct?

            Triangle.prototype.intersect = function(ray){
                var v1 = this.t1.sub(ray.direction);
                var v2 = this.t2.sub(ray.direction);
                var n1 = v1.cross(v2);
                n1 = n1.normalize();
                
                var d1 = -ray.origin.dot(n1);
                if((ray.direction.dot(n1) + d1) < 0)
                    return -1.0;
                return d1;
            }

My triangle is defined by 3 Vectors (t1,t2,t3).



Sponsor:

#2 haegarr   Crossbones+   -  Reputation: 5243

Like
2Likes
Like

Posted Today, 04:18 AM


I was wondering if my triangle intersection code is correct?

IMHO it isn't. It has at least 3 issues.

 

It seems that v1, v2 shall be some direction vectors that span the (infinite) plane in which the triangle lies. Then t1, t2, t3 are known to be on that plane, but ray.direction is not related to that plane. Hence computing v1, v2 must not use ray.direction. Now, with 3 positions, you can compute 6 difference vectors

    t1 - t2, t1 - t3, t2 - t3 (and their negative variants)

from which you need 2, say

   v1 := t1 - t3

   v2 := t2 - t3

 

(This is your 1st issue: Your difference vectors are not correct.)

 

With the above you can describe the plane as an infinite set of points in space, reachable by any linear combination of v1 and v2 when starting at any known point on the plane. For example

   P( a, b ) := t3 + v1 * a + v2 * b

Notice, however, that this works if and only if v1 and v2 are not co-linear itself, so you cannot find a scalar f so that v1 * f = v2. This mean, in other words, that t1, t2, and t3 must not lie on a straight line in space.

 

Another kind of definition for such a plane is to use not 2 direction vectors inside that plane, but instead the normal of the plane. Well, with 2 difference vectors you can compute the normal as their cross-product:

    n1 := v1 x v2

The the plane can be given in the so-called Hesse Normal Form:

   ( x - t3 ) . n1 == 0

It means "any point x in space belongs to that plane if the distance to the plane is zero".

 

(This is your 2nd issue: You can use the Hesse Normal Form for computing whether / where the ray hits the plane but not whether / where the ray hits the triangle, because the information about the triangle is lost in that formula. The 3rd issue is that using the Hesse Normal Form in that way is not complete.)

 

Similar to the plane above, a ray can be understood as the set of points in space when starting at a known position (the ray.origin) and going for any distance along a direction (the ray.direction):

   R( t ) := ray.origin + c * ray.direction

 

What you are now interested in is the set of points in space that are part of both the set of points of the plane and the set of points of the ray. Hence you want to look for any points with the condition

   P( a, b ) == R( c )

 

Obviously you have to solve for the 3 unknowns a, b, and c. Luckily, the above condition is given in 3 dimensional space, hence giving you 3 equations, one for each dimension:

   Px( a, b ) == Rx( c )

   Py( a, b ) == Ry( c )

   Pz( a, b ) == Rz( c )

 

You need to solve the above linear equation system for a, b. On the going you will see that the chance of a "division by zero" exists. If that occurs then the ray is parallel to the plane, hence there is no intersection (if the ray is distance from the plane) or infinite many intersections (if the ray is on the plane). You have to catch this, of course.

 

Considering here that the ray is not parallel to the plane, you get a unique solution for a and b, say a' and b'. However, so far you still just know that the ray hits the plane, but you want to know whether the ray hits the triangle. As said above, a and b in the plane formula allow you to reach any point on the plane. So you need to take a closer look at a' and b', especially whether they describe a point within the triangle. Because we have build v1 and v2 from the triangle's corners so that they describe 2 of its legs emanating from t3, any solution with

    a' < 0  or  a' > 1  or  b' < 0  or  b' > 1

cannot be part of the triangle. That gives the condition

   0 <= a' <= 1  and  0 <= b' <= 1

 

Thinking further of the above limits, the figure described by them is a rhombus with the desired triangle is one half of (simply chose a' == 1 and try some b' between 0 and 1 to see that). That introduces an extended condition:

  … and a' + b' <= 1

 

 

EDIT: Other ways of solution may exist as well. The above way is the straight forward one.


Edited by haegarr, Today, 04:48 AM.


#3 IsItSharp   Members   -  Reputation: 192

Like
0Likes
Like

Posted Today, 06:42 AM

 

 

P( a, b ) := t3 + v1 * a + v2 * b

 

How can solve this equation with two unknown values?







PARTNERS