Site hosted by Angelfire.com: Build your free website today!
Line to Triangle intersection test:
By: Christopher Bartlett
Take a look at Solutions Page for other solutions.

Given:

  • A Triangle.
  • A line defined by a point and a vector.

Asked to Write Code for following:

  • How to test if line intersect inside triangle.

Assumptions:

  • none

Steps to Solve:

  1. Basic Idea is to find out if line intersect the plain of the triangle. And then test if this intersection point is inside the triangle. Using Clockness test: if the three triangles from by each side of the triangle to intersect point have same clocknees as the triangle then point is inside triangle.
  2. Start by finding Normal to triangle.
  3. Take dot product of triangle's normal and line's vector.
    Negitive: answer means the angle between tri's normal and line's vector is greater the 90 degrees, which means line hit front of triangle, this is the correct answer for a hit.
    Positive: answer means the angle is less then 90 and line's vector hit from the backside of triangle.
    Zero: answer means line is parallel to triangle's plane.
  4. Using plane equation solve for the intersection point. By finding time t to this point and line's vector.
    t is time if line's vector is given as units/time or t is distance if vector is given as just units, such as if given a line segment without a speed.
  5. Use clockness to test if this point is inside triangle.
  6. In 3D a triangle chould be clockwise from front view and counterclockwise from back in XYZ space.
    So you have to be careful of how you define your triangles clockness.
  7. Funtion check_same_clock_dir finds the norm to triangle formed by two points of triangle and intersect point. It then does a dot product with the triangle normal.
    If answer is zero or positive, intersect point lies on the line or the corect side of line to have same normal as triangle and SAME_CLOCKNESS is returned. If negitive answer then DIFF_CLOCKNESS is returned.
  8. Funtion check_tri_hit returns 1 for intersect with pt_int is fill in with intersection point ,and 0 for no intersection none with pt_int not a vaild answer.
  9. CODE
Some Notes:

Could speed up if you allready stored the triangle's normal.
If your line is a unit vector and speed then multiply unit vector with speed to make the line's vector.
Have not tested code but should work.

CODE
Code uses:

  • Everything is adds, subtractions, and multiplies with one divide.
  • // Start Code
    // must include at least these
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    
    #define SAME_CLOCKNESS = 1;
    #define DIFF_CLOCKNESS = 0;
    
    typedef struct fpoint_tag
    {
       float x;
       float y;
       float z;
    } fpoint;
    
    fpoint pt1 = {0.0, 0.0, 0.0};
    fpoint pt2 = {0.0, 3.0, 3.0};
    fpoint pt3 = {2.0, 0.0, 0.0};
    fpoint linept = {0.0, 0.0, 6.0};
    fpoint vect = {0.0, 2.0, -4.0};
    fpoint pt_int = {0.0, 0.0, 0.0};
    
    int check_same_clock_dir(fpoint pt1, fpoint pt2, fpoint pt3, fpoint norm)
    {  
       float testi, testj, testk;
       float dotprod;
       // normal of trinagle
       testi = (((pt2.y - pt1.y)*(pt3.z - pt1.z)) - ((pt3.y - pt1.y)*(pt2.z - pt1.z)));
       testj = (((pt2.z - pt1.z)*(pt3.x - pt1.x)) - ((pt3.z - pt1.z)*(pt2.x - pt1.x)));
       testk = (((pt2.x - pt1.x)*(pt3.y - pt1.y)) - ((pt3.x - pt1.x)*(pt2.y - pt1.y)));
    
       // Dot product with triangle normal
       dotprod = testi*norm.x + testj*norm.y + testk.norm.z;
    
       //answer
       if(dotprod < 0) return DIFF_CLOCKNESS;
       else return SAME_CLOCKNESS;
    }
    
    int check_intersect_tri(fpoint pt1, fpoint pt2, fpoint pt3, fpoint linept, fpoint vect,
                            fpoitnt* pt_int)
    {
       float V1x, V1y, V1z;
       float V2x, V2y, V2z;
       fpoint norm;
       float dotprod;
       float t;
    
       // vector form triangle pt1 to pt2
       V1x = pt2.x - pt1.x;
       V1y = pt2.y - pt1.y;
       V1z = pt2.z - pt1.z;
    
       // vector form triangle pt2 to pt3
       V2x = pt3.x - pt2.x;
       V2y = pt3.y - pt2.y;
       V2z = pt3.z - pt2.z;
    
       // vector normal of triangle
       norm.x = V1y*V2z-V1z*V2y;
       norm.y = V1z*V2x-V1x*V2z;
       norm.z = V1x*V2y-V1y*V2x;
    
       // dot product of normal and line's vector if zero line is parallel to triangle
       dotprod = norm.x*vect.x + norm.y*vect.y + norm.z*vect.z;
    
       if(dotprod < 0)
       {
          //Find point of intersect to triangle plane.
          //find t to intersect point
          t = -(norm.x*(linept.x-pt1.x)+norm.y*(linept.y-pt1.y)+norm.z*(linept.z-pt1.z))/
                 (norm.x*vect.x+norm.y*vect.y+norm.z*vect.z);
    
          // if ds is neg line started past triangle so can't hit triangle.
          if(t < 0) return 0
    
          pt_int->x = linept.x + vect.x*t;
          pt_int->y = linept.y + vect.y*t;
          pt_int->z = linept.z + vect.z*t;
    
          if(check_same_clock_dir(pt1, pt2, pt_int, norm) == SAME_CLOCKNESS)
          {
             if(check_same_clock_dir(pt2, pt3, pt_int, norm) == SAME_CLOCKNESS)
             {
                if(check_same_clock_dir(pt3, pt1, pt_int, norm) == SAME_CLOCKNESS)
                {
                   // answer in pt_int is insde triangle
                   return 1;
                }
             }
          }
       }
       return 0;
    }
    
    // End Code
    
    
    All Material within this article is Copyrighted © 2000 by Christopher Bartlett, All rights reserved.
    Use is Granted for Learning. Last Revised onAugust 2th, 2001 (8-1-01).
    Web: The House of Bartlett Contact: houseofbartlett@angelfire.com Visits: