Creating a Triangle Primitive

[ LiB ]

Intersecting a ray with a triangle can be a trivial, but slow task. The basic idea of ray-triangle intersections is that most people would intersect the ray with the tangent plane a triangle is sitting in and then do some type of test to determine whether a point lies within the surrounding edges of a triangle. The algorithm would then go to work and return success if it intersects the triangle within the given A, B, and C vertices. The incoming ray is going to hit the triangle at some point within its boundaries. The class and all its functionality are defined in the file cObject.h .

Designing the Primitive

Let's define a class that includes the three points for a triangle. The class will also include the plane definition and center point. The plane definition is composed of the plane distance and the plane unit normal. The center point vector is going to be used to find the center of the triangle. Instead of calling the vertices A, B, and C, you'll define them into an array of Vertex [0] , Vertex [1] , and Vertex [2] . Upon initialization and setup, the plane and the center point are automatically computed. The class will also include an internal Find_Hitpoint(cRay * pRay) method that passes a ray in as a referenced parameter and computes the destination point of the ray. The ray structure will return with the destination point as the exact hit point on the triangle.

The cTriangle class consists of an array of three vertices. It will contain a unit normal for the plane as well as the plane distance. It also contains a center point variable that determines the center of the triangle between vertices 1, 2, and 3. Two constructors are utilized as well as a few member methods . The constructors set up the member variables of the triangle. One member function is used to set up the triangle, one to calculate the center point of the triangle, and the other to find the intersection point of an incoming ray.

 class cTriangle { public:    // Triangle Definition   cVector3 Vertex[3];   cVector3 vNormal, vCenterPoint;   float fPlane_Distance;    cTriangle ()    {            vNormal         = cVector3::vZero;            vCenterPoint    = cVector3::vZero;            fPlane_Distance = 0;    };    cTriangle(cVector3 a, cVector3 b, cVector3 c, bool left_handed = true)    {            Vertex [0] = a;            Vertex [1] = b;            Vertex [2]       = c;            if ( left_handed == true)            {                      // Note: triangle defined in left handed system                       Vertex [0].x = -Vertex [0].x;                       Vertex [0].y = -Vertex [0].y;                       Vertex [1].x = -Vertex [1].x;                       Vertex [1].y = -Vertex [1].y;                       Vertex [2].x = -Vertex [2].x;                       Vertex 2].y    Vertex [2].y;       }          // compute plane         vNormal         = (c-b) ^ (a-b);         vNormal.Normalize();         fPlane_Distance   = vNormal * a;        // compute center point        Compute_CenterPoint();   };   void Setup_Triangle(cVector3 a, cVector3 b, cVector3 c,                                      bool left_handed = true)   {             Vertex [0]           = a;             Vertex [1]           = b;             Vertex [2]           = c;             if ( left_handed == true)             {                   //Note: tri angle defined in left handed system        Vertex [0].x       = -Vertex [0].x;        Vertex [0].y       = -Vertex [0].y;                    Vertex [1].x       = -Vertex [1].x;                    Vertex [1].y       = -Vertex [1].y ;                    Vertex [2].x       = -Vertex [2].x ;                    Vertex [2].y       = -Vertex [2].y;            }           // compute plane            vNormal = ( c-b) ^ (a-b);            vNormal.Normalize();            fPlane_Distance = vNormal * a;           // compute center point            Compute_Cen terPoint();   };        // find hit point        bool    ind_H itpoint(cRay * pRay);        void    Compute_CenterPoint(); protected:        bool    TomasANDBen_Intersect(cRay * pRay,            cVector3 *a, cVector3 *b, cVector3 *c ); };

Computing the Center Point

This procedure cycles through the three points of each triangle and finds the average of each component. This procedure computes a point that's in the middle of the three points of the triangle, as follows :

 void cTriangle::Compute_CenterPoint() {    vCenterPoint = cVector3::vZero;    for (int i = 0; i <3; i++)    {       vCenterPoint.x += Vertex[i].x; vCenterPoint.y += Vertex[i].y; vCenterPoint.z += Vertex[i].z;    }       vCenterPoint /= 3; }

The method simply sums the vertices of the triangle up into one variable. It then divides each X, Y, and Z component by three.

Intersection

There are numerous algorithms out there that do triangle intersections. The first thing you need to do is determine whether the ray intersects the plane and then find the distance and destination point of the ray to the tangent plane of the triangle. This is conducted with Find_Hitpoint(cRay * pRay). The function calculates the triangle's plane and then finds the actual hit point by calling Find_Destination(). However, we're not done because we still need to find out if the intersection point sits within the boundaries of the triangle. This is found by calling TomasANDBen_Intersect(cRay * pRay, cVector3 A, cVector3 B, cVector3 C) , which is discussed next .

 bool cTriangle::Find_Hitpoint(cRay *  pRay) {    float  A, B, Distance;    bool   Return =  lse;       if( ( A = pRay->direction * vNormal ) != 0.0f ) {          B = - ( vNormal * pRay->origin ) + this->fPlane_Distance ;          Distance = B / A;  if( Distance > 1.0f  )        {           // we found the distance from the ray origin to the plane           pRay->distance = Distance;          // calculate destination point           pRay->Find_Destination();          // check to see if it lies within the A, B, and C          // vertices of the unit triangle             bReturn = TomasANDBen_Intersect             ( pRay,              &Vertex[0],              &Vertex[1],              &Vertex[2] );              // (yes or no) that's it              return bReturn;          }       }     // if it fails no by default    return false; }

Using the Tomas and Ben Triangle Intersection

Finding an algorithm to determine if the ray's destination point sits within the three points of the triangle is our objective. I am going to use an algorithm developed by Tomas Moller and Ben Trumbore (Fast, Minimum Storage Ray/Triangle Intersection) that uses a minimum storage ray-triangle intersection function. The algorithm was designed to be very fast and use minimal storage that only utilizes vertices that are needed for the triangle with no preprocessing necessary. The algorithm translates the ray's origin and then changes the vector to a new vector using this equation:

 (t u v) ^ t

Where t is the distance to the plane and the local coordinates of the triangle sitting flat on the plane are u and v . These two coordinates are also known as texture coordinates . Coordinates u and v represent the local coordinate system inside the triangle. The coordinate system is 2D because the triangle is sitting flat on the plane.

The u and v are used for texture mapping, normal interpolation, and color interpolation.

NOTE

Tomas Moller and Ben Trumbore's Web site (Fast, Minimum Storage Ray/Triangle Intersection) is located at http://www.acm.org/jgt/papers/MollerTrumbore97/ .

The process for finding the intersection is as follows:

Use the definition of the ray with a special formula to determine whether the previously calculated intersection point on the plane sits within the triangle's boundaries.

Ray Formula:

A ray has an origina distance scalar and a normalized direction vec-tor. The function is defined as R (t) = O + tD . O is the origin, t is the delta distance, and D is the unit direction vector.

To determine whether the intersection point sits within the triangle, you need to use the following formula as the input to the ray function R(t) .

Triangle Intersection Formula:
```
 t (u, v) = (1  u  v) V0 + uV1 + vV2 
```
Plug in the terms and you'll get R (t (u, v)) , meaning a point in the triangle can be found. The function t(u,v) is equal to R(t) = t(u,v) .
The input parameters of the function (u and v) are given in Barycentric coordinates. This means that u and v must be equal to or greater than ( u >= 0 , v >= 0 ) and u + v must be equal to or less than one ( u <= 1 , v <= 1 ).

If you plug in 0,0,0 as the ray's origin meaning the ray begins at the world origin (0,0,0), then you can simplify the terms as: O + tD = (1 u v ) V0 + uV1 + vV2

Rearranging the previous terms depicts:

 [   t   ] [ -D, V1  V0, V2  V0 ]  [ u ]  = O  V0 [   v   ]

These equations basically translate a triangle to the world origin (0, 0, 0) and scale the full- sized triangle down to a unit triangle. Remember, you can always scale these values back up once you find the correct result. The triangle is then transformed to the Y and Z axes with the incoming ray direction aligned to the X axis. See Figure 7.3 for an illustration. If the normalized ray is within the unit triangle edges, the function returns true .

Figure 7.3. Intersecting a ray with a triangle is done by placing the triangle on the Y and Z axes and intersecting it with a ray aligned with the X axis.

graphic/07fig03.gif

Here is the code:

 bool cTriangle:: TomasANDBen_Intersect(cRay * pRay, cVector3 *a,                   cVector3 *b, cVector3 *c ) {    cVector3 edge1, edge2, tvec, pvec, qvec;    double det,inv_det;    double t, u, v;    edge1 = *b - *a;    edge2 = *c - *a;    pvec = ( pRay->direction ^ edge2 );    det = ( edge1 * pvec );    if (det > -0.000001f && det < 0.000001f)      return false;    inv_det = 1.0 / det;    // calculate distance from vert0 to ray origin    tvec = pRay->origin - *a;    // calculate U parameter and test bounds    u = ( tvec * pvec ) * inv_det;   if (u < 0.0  u > 1.0)      return false;    // prepare to test V parameter    qvec = ( tvec ^ edge1 );    // calculate V parameter and test bounds    v = ( pRay->direction * qvec) * inv_det;    if (v < 0.0  u + v > 1.0)      return false;    // calculate t, ray intersects triangle    t = ( edge2 * qvec) * inv_det;    return true; }

[ LiB ]