triboxoverlap.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
*/

/********************************************************/
/* AABB-triangle overlap test code                      */
/* by Tomas Akenine-Möller                              */
/* Function: int triBoxOverlap(float boxcenter[3],      */
/*          float boxhalfsize[3],float triverts[3][3]); */
/* History:                                             */
/*   2001-03-05: released the code in its first version */
/*   2001-06-18: changed the order of the tests, faster */
/*                                                      */
/* Acknowledgement: Many thanks to Pierre Terdiman for  */
/* suggestions and discussions on how to optimize code. */
/* Thanks to David Hunt for finding a ">="-bug!         */
/********************************************************/

#include "triboxoverlap.h"  // include first

#include <cmath>

using namespace sheep;
using namespace toxic;

#define FINDMINMAX(x0, x1, x2, min, max) \
    min = max = x0; \
    if(x1 < min) min = x1; \
    if(x1 > max) max = x1; \
    if(x2 < min) min = x2; \
    if(x2 > max) max = x2;

namespace {
    bool plane_box_overlap(const Vector3 &normal, Real d, const Vector3 &maxbox) {
        Vector3 vmin, vmax;

        if(normal.m_x > 0.0) {
            vmin.m_x = -maxbox.m_x;
            vmax.m_x = maxbox.m_x;
        } else {
            vmin.m_x = maxbox.m_x;
            vmax.m_x = -maxbox.m_x;
        }

        if(normal.m_y > 0.0) {
            vmin.m_y = -maxbox.m_y;
            vmax.m_y = maxbox.m_y;
        } else {
            vmin.m_y = maxbox.m_y;
            vmax.m_y = -maxbox.m_y;
        }

        if(normal.m_z > 0.0) {
            vmin.m_z = -maxbox.m_z;
            vmax.m_z = maxbox.m_z;
        } else {
            vmin.m_z = maxbox.m_z;
            vmax.m_z = -maxbox.m_z;
        }

        if(normal * vmin + d > 0.0) return false;
        if(normal * vmax + d >= 0.0) return true;

        return false;
    }
}

//======================== X-tests ========================

#define AXISTEST_X01(a, b, fa, fb) \
    p0 = a * v0.m_y - b * v0.m_z; \
    p2 = a * v2.m_y - b * v2.m_z; \
    if(p0 < p2) { min = p0; max = p2; } else { min = p2; max = p0; } \
    rad = fa * boxhalfsize.m_y + fb * boxhalfsize.m_z; \
    if(min > rad || max < -rad) return false;

#define AXISTEST_X2(a, b, fa, fb) \
    p0 = a * v0.m_y - b * v0.m_z; \
    p1 = a * v1.m_y - b * v1.m_z; \
    if(p0 < p1) { min = p0; max = p1; } else { min = p1; max = p0; } \
    rad = fa * boxhalfsize.m_y + fb * boxhalfsize.m_z; \
    if(min > rad || max < -rad) return false;

//======================== Y-tests ========================

#define AXISTEST_Y02(a, b, fa, fb) \
    p0 = -a * v0.m_x + b * v0.m_z; \
    p2 = -a * v2.m_x + b * v2.m_z; \
    if(p0 < p2) { min = p0; max = p2; } else { min = p2; max = p0; } \
    rad = fa * boxhalfsize.m_x + fb * boxhalfsize.m_z; \
    if(min > rad || max < -rad) return false;

#define AXISTEST_Y1(a, b, fa, fb) \
    p0 = -a * v0.m_x + b * v0.m_z; \
    p1 = -a * v1.m_x + b * v1.m_z; \
    if(p0 < p1) { min = p0; max = p1; } else { min = p1; max = p0; } \
    rad = fa * boxhalfsize.m_x + fb * boxhalfsize.m_z; \
    if(min > rad || max < -rad) return false;

//======================== Z-tests ========================

#define AXISTEST_Z12(a, b, fa, fb) \
    p1 = a * v1.m_x - b * v1.m_y; \
    p2 = a * v2.m_x - b * v2.m_y; \
    if(p2 < p1) { min = p2; max = p1; } else { min = p1; max = p2; } \
    rad = fa * boxhalfsize.m_x + fb * boxhalfsize.m_y; \
    if(min > rad || max < -rad) return false;

#define AXISTEST_Z0(a, b, fa, fb) \
    p0 = a * v0.m_x - b * v0.m_y; \
    p1 = a * v1.m_x - b * v1.m_y; \
    if(p0 < p1) { min = p0; max = p1; } else { min = p1; max = p0; } \
    rad = fa * boxhalfsize.m_x + fb * boxhalfsize.m_y; \
    if(min > rad || max < -rad) return false;

bool toxic::tri_box_overlap(const Point3 &boxcenter,
                            const Vector3 &boxhalfsize,
                            const Point3 &vert0,
                            const Point3 &vert1,
                            const Point3 &vert2)
{
    // Use separating axis theorem to test overlap between triangle and box.
    // Need to test for overlap in these directions:
    // 1) the {x,y,z}-directions (actually, since we use the AABB of the triangle
    //    we do not even need to test these)
    // 2) normal of the triangle
    // 3) crossproduct(edge from tri, {x,y,z}-directin).
    //    This gives 3x3=9 more tests.
    Real min, max, p0, p1, p2, rad, fex, fey, fez;

    // This is the fastest branch on Sun.
    // Move everything so that the boxcenter is in (0,0,0).
    const Vector3 v0 = vert0 - boxcenter;
    const Vector3 v1 = vert1 - boxcenter;
    const Vector3 v2 = vert2 - boxcenter;

    // Compute triangle edges.
    const Vector3 e0 = v1 - v0; // tri edge 0
    const Vector3 e1 = v2 - v1; // tri edge 1
    const Vector3 e2 = v0 - v2; // tri edge 2

    // Bullet 3:
    //   Test the 9 tests first (this was faster).
    fex = fabs(e0.m_x);
    fey = fabs(e0.m_y);
    fez = fabs(e0.m_z);
    AXISTEST_X01(e0.m_z, e0.m_y, fez, fey);
    AXISTEST_Y02(e0.m_z, e0.m_x, fez, fex);
    AXISTEST_Z12(e0.m_y, e0.m_x, fey, fex);

    fex = fabs(e1.m_x);
    fey = fabs(e1.m_y);
    fez = fabs(e1.m_z);
    AXISTEST_X01(e1.m_z, e1.m_y, fez, fey);
    AXISTEST_Y02(e1.m_z, e1.m_x, fez, fex);
    AXISTEST_Z0(e1.m_y, e1.m_x, fey, fex);

    fex = fabs(e2.m_x);
    fey = fabs(e2.m_y);
    fez = fabs(e2.m_z);
    AXISTEST_X2(e2.m_z, e2.m_y, fez, fey);
    AXISTEST_Y1(e2.m_z, e2.m_x, fez, fex);
    AXISTEST_Z12(e2.m_y, e2.m_x, fey, fex);

    // Bullet 1:
    //   First test overlap in the {x,y,z}-directions.
    //   Find min, max of the triangle each direction, and test for overlap in that
    //   direction -- this is equivalent to testing a minimal AABB around the triangle
    //   against the AABB.

    // Test in X-direction.
    FINDMINMAX(v0.m_x, v1.m_x, v2.m_x, min, max);
    if(min > boxhalfsize.m_x || max < -boxhalfsize.m_x)
        return false;

    // Test in Y-direction.
    FINDMINMAX(v0.m_y, v1.m_y, v2.m_y, min, max);
    if(min > boxhalfsize.m_y || max < -boxhalfsize.m_y)
        return false;

    // Test in Z-direction.
    FINDMINMAX(v0.m_z, v1.m_z, v2.m_z, min, max);
    if(min > boxhalfsize.m_z || max < -boxhalfsize.m_z)
        return false;

    // Bullet 2:
    //   Test if the box intersects the plane of the triangle.
    //   Compute plane equation of triangle: normal*x+d=0.
    const Vector3 normal = e0 ^ e1;
    const Real d = -(normal * v0);  // plane eq: normal.x+d=0
    if(!plane_box_overlap(normal, d, boxhalfsize))
        return false;

    return true;    // box and triangle overlaps
}

---