intersecttriangle.cpp

Go to the documentation of this file.

/*
    toxic - A Global Illumination Renderer
    Copyright (C) 2003-2004 Francois Beaune
    Contact: http://toxicengine.sourceforge.net/

    This file is part of toxic.

    toxic is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    toxic is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with toxic; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/

/* Ray-Triangle Intersection Test Routines          */
/* Different optimizations of my and Ben Trumbore's */
/* code from journals of graphics tools (JGT)       */
/* http://www.acm.org/jgt/                          */
/* by Tomas Moller, May 2000                        */

#include "intersecttriangle.h"  // include first
#include "ray.h"

#include <cmath>

using namespace sheep;
using namespace toxic;

const Real EPSILON = 0.000001;

// The original jgt code.
bool toxic::intersect_triangle(const Ray &ray,
                               const Vector3 &vert0,
                               const Vector3 &vert1,
                               const Vector3 &vert2,
                               Real *t, Real *u, Real *v)
{
    // Find vectors for two edges sharing vert0.
    const Vector3 edge1 = vert1 - vert0;
    const Vector3 edge2 = vert2 - vert0;

    // Begin calculating determinant - also used to calculate U parameter.
    const Vector3 pvec = ray.m_direction ^ edge2;

    // If determinant is near zero, ray lies in plane of triangle.
    const Real det = edge1 * pvec;
//  if(det > -EPSILON && det < EPSILON)
//      return false;
    if(det == 0.0)
        return false;

    const Real inv_det = 1.0 / det;

    // Calculate distance from vert0 to ray origin.
    const Vector3 tvec = ray.m_origin - vert0;

    // 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.
    const Vector3 qvec = tvec ^ edge1;

    // Calculate V parameter and test bounds.
    *v = (ray.m_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;
}

// Code rewritten to do tests on the sign of the determinant.
// The division is at the end in the code.
bool toxic::intersect_triangle1(const Ray &ray,
                                const Vector3 &vert0,
                                const Vector3 &vert1,
                                const Vector3 &vert2,
                                Real *t, Real *u, Real *v)
{
    // Find vectors for two edges sharing vert0.
    const Vector3 edge1 = vert1 - vert0;
    const Vector3 edge2 = vert2 - vert0;

    // Begin calculating determinant - also used to calculate U parameter.
    const Vector3 pvec = ray.m_direction ^ edge2;

    // If determinant is near zero, ray lies in plane of triangle.
    const Real det = edge1 * pvec;

    Vector3 qvec;

    if(det > EPSILON) {
        // Calculate distance from vert0 to ray origin.
        const Vector3 tvec = ray.m_origin - vert0;

        // Calculate U parameter and test bounds.
        *u = tvec * pvec;
        if(*u < 0.0 || *u > det)
            return false;

        // Prepare to test V parameter.
        qvec = tvec ^ edge1;

        // Calculate V parameter and test bounds.
        *v = ray.m_direction * qvec;
        if(*v < 0.0 || *u + *v > det)
            return false;
    }
    else if(det < -EPSILON) {
        // Calculate distance from vert0 to ray origin.
        const Vector3 tvec = ray.m_origin - vert0;

        // Calculate U parameter and test bounds.
        *u = tvec * pvec;
        if(*u > 0.0 || *u < det)
            return false;

        // Prepare to test V parameter.
        qvec = tvec ^ edge1;

        // Calculate V parameter and test bounds.
        *v = ray.m_direction * qvec;
        if(*v > 0.0 || *u + *v < det)
            return false;
    }
    else return false;  // ray is parallel to the plane of the triangle

    const Real inv_det = 1.0 / det;

    // Calculate t, ray intersects triangle.
    *t = (edge2 * qvec) * inv_det;
    (*u) *= inv_det;
    (*v) *= inv_det;

    return true;
}

// Code rewritten to do tests on the sign of the determinant.
// The division is before the test of the sign of the determinant.
bool toxic::intersect_triangle2(const Ray &ray,
                                const Vector3 &vert0,
                                const Vector3 &vert1,
                                const Vector3 &vert2,
                                Real *t, Real *u, Real *v)
{
    // Find vectors for two edges sharing vert0.
    const Vector3 edge1 = vert1 - vert0;
    const Vector3 edge2 = vert2 - vert0;

    // Begin calculating determinant - also used to calculate U parameter.
    const Vector3 pvec = ray.m_direction ^ edge2;

    // If determinant is near zero, ray lies in plane of triangle.
    const Real det = edge1 * pvec;

    // Calculate distance from vert0 to ray origin.
    const Vector3 tvec = ray.m_origin - vert0;

    const Real inv_det = 1.0 / det;

    Vector3 qvec;

    if(det > EPSILON) {
        // Calculate U parameter and test bounds.
        *u = tvec * pvec;
        if(*u < 0.0 || *u > det)
            return false;

        // Prepare to test V parameter.
        qvec = tvec ^ edge1;

        // Calculate V parameter and test bounds.
        *v = ray.m_direction * qvec;
        if(*v < 0.0 || *u + *v > det)
            return false;
    }
    else if(det < -EPSILON) {
        // Calculate U parameter and test bounds.
        *u = tvec * pvec;
        if(*u > 0.0 || *u < det)
            return false;

        // Prepare to test V parameter.
        qvec = tvec ^ edge1;

        // Calculate V parameter and test bounds.
        *v = ray.m_direction * qvec;
        if(*v > 0.0 || *u + *v < det)
            return false;
    }
    else return false;  // ray is parallel to the plane of the triangle

    // Calculate t, ray intersects triangle.
    *t = (edge2 * qvec) * inv_det;
    (*u) *= inv_det;
    (*v) *= inv_det;

    return true;
}

// Code rewritten to do tests on the sign of the determinant.
// The division is before the test of the sign of the determinant and
// one cross product has been moved out from the if-else if-else.
bool toxic::intersect_triangle3(const Ray &ray,
                                const Vector3 &vert0,
                                const Vector3 &vert1,
                                const Vector3 &vert2,
                                Real *t, Real *u, Real *v)
{
    // Find vectors for two edges sharing vert0.
    const Vector3 edge1 = vert1 - vert0;
    const Vector3 edge2 = vert2 - vert0;

    // Begin calculating determinant - also used to calculate U parameter.
    const Vector3 pvec = ray.m_direction ^ edge2;

    // If determinant is near zero, ray lies in plane of triangle.
    const Real det = edge1 * pvec;

    // Calculate distance from vert0 to ray origin.
    const Vector3 tvec = ray.m_origin - vert0;

    const Real inv_det = 1.0 / det;

    const Vector3 qvec = tvec ^ edge1;

    if(det > EPSILON) {
        // Calculate U parameter and test bounds.
        *u = tvec * pvec;
        if(*u < 0.0 || *u > det)
            return false;

        // Calculate V parameter and test bounds.
        *v = ray.m_direction * qvec;
        if(*v < 0.0 || *u + *v > det)
            return false;
    }
    else if(det < -EPSILON) {
        // Calculate U parameter and test bounds.
        *u = tvec * pvec;
        if(*u > 0.0 || *u < det)
            return false;

        // Calculate V parameter and test bounds.
        *v = ray.m_direction * qvec;
        if(*v > 0.0 || *u + *v < det)
            return false;
    }
    else return false;  // ray is parallel to the plane of the triangle

    // Calculate t, ray intersects triangle.
    *t = (edge2 * qvec) * inv_det;
    (*u) *= inv_det;
    (*v) *= inv_det;

    return true;
}

---