Blame Imath/ImathFrustumTest.h

Packit 8dc392
///////////////////////////////////////////////////////////////////////////
Packit 8dc392
//
Packit 8dc392
// Copyright (c) 2011-2012, Industrial Light & Magic, a division of Lucas
Packit 8dc392
// Digital Ltd. LLC
Packit 8dc392
// 
Packit 8dc392
// All rights reserved.
Packit 8dc392
// 
Packit 8dc392
// Redistribution and use in source and binary forms, with or without
Packit 8dc392
// modification, are permitted provided that the following conditions are
Packit 8dc392
// met:
Packit 8dc392
// *       Redistributions of source code must retain the above copyright
Packit 8dc392
// notice, this list of conditions and the following disclaimer.
Packit 8dc392
// *       Redistributions in binary form must reproduce the above
Packit 8dc392
// copyright notice, this list of conditions and the following disclaimer
Packit 8dc392
// in the documentation and/or other materials provided with the
Packit 8dc392
// distribution.
Packit 8dc392
// *       Neither the name of Industrial Light & Magic nor the names of
Packit 8dc392
// its contributors may be used to endorse or promote products derived
Packit 8dc392
// from this software without specific prior written permission. 
Packit 8dc392
// 
Packit 8dc392
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
Packit 8dc392
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
Packit 8dc392
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
Packit 8dc392
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
Packit 8dc392
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
Packit 8dc392
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
Packit 8dc392
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
Packit 8dc392
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
Packit 8dc392
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
Packit 8dc392
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
Packit 8dc392
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Packit 8dc392
//
Packit 8dc392
///////////////////////////////////////////////////////////////////////////
Packit 8dc392
Packit 8dc392
Packit 8dc392
#ifndef INCLUDED_IMATHFRUSTUMTEST_H
Packit 8dc392
#define INCLUDED_IMATHFRUSTUMTEST_H
Packit 8dc392
Packit 8dc392
//-------------------------------------------------------------------------
Packit 8dc392
//
Packit 8dc392
//  This file contains algorithms applied to or in conjunction with
Packit 8dc392
//  Frustum visibility testing (Imath::Frustum).
Packit 8dc392
//
Packit 8dc392
//  Methods for frustum-based rejection of primitives are contained here.
Packit 8dc392
//
Packit 8dc392
//-------------------------------------------------------------------------
Packit 8dc392
Packit 8dc392
#include "ImathFrustum.h"
Packit 8dc392
#include "ImathBox.h"
Packit 8dc392
#include "ImathSphere.h"
Packit 8dc392
#include "ImathMatrix.h"
Packit 8dc392
#include "ImathVec.h"
Packit 8dc392
#include "ImathNamespace.h"
Packit 8dc392
Packit 8dc392
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER
Packit 8dc392
Packit 8dc392
/////////////////////////////////////////////////////////////////
Packit 8dc392
// FrustumTest
Packit 8dc392
//
Packit 8dc392
//	template class FrustumTest<T>
Packit 8dc392
//
Packit 8dc392
// This is a helper class, designed to accelerate the case
Packit 8dc392
// where many tests are made against the same frustum.
Packit 8dc392
// That's a really common case.
Packit 8dc392
//
Packit 8dc392
// The acceleration is achieved by pre-computing the planes of
Packit 8dc392
// the frustum, along with the ablsolute values of the plane normals.
Packit 8dc392
//
Packit 8dc392
Packit 8dc392
Packit 8dc392
Packit 8dc392
//////////////////////////////////////////////////////////////////
Packit 8dc392
// How to use this
Packit 8dc392
//
Packit 8dc392
// Given that you already have:
Packit 8dc392
//    Imath::Frustum   myFrustum
Packit 8dc392
//    Imath::Matrix44  myCameraWorldMatrix
Packit 8dc392
//
Packit 8dc392
// First, make a frustum test object:
Packit 8dc392
//    FrustumTest myFrustumTest(myFrustum, myCameraWorldMatrix)
Packit 8dc392
//
Packit 8dc392
// Whenever the camera or frustum changes, call:
Packit 8dc392
//    myFrustumTest.setFrustum(myFrustum, myCameraWorldMatrix)
Packit 8dc392
//
Packit 8dc392
// For each object you want to test for visibility, call:
Packit 8dc392
//    myFrustumTest.isVisible(myBox)
Packit 8dc392
//    myFrustumTest.isVisible(mySphere)
Packit 8dc392
//    myFrustumTest.isVisible(myVec3)
Packit 8dc392
//    myFrustumTest.completelyContains(myBox)
Packit 8dc392
//    myFrustumTest.completelyContains(mySphere)
Packit 8dc392
//
Packit 8dc392
Packit 8dc392
Packit 8dc392
Packit 8dc392
Packit 8dc392
//////////////////////////////////////////////////////////////////
Packit 8dc392
// Explanation of how it works
Packit 8dc392
//
Packit 8dc392
//
Packit 8dc392
// We store six world-space Frustum planes (nx, ny, nz, offset)
Packit 8dc392
//
Packit 8dc392
// Points: To test a Vec3 for visibility, test it against each plane
Packit 8dc392
//         using the normal (v dot n - offset) method. (the result is exact)
Packit 8dc392
//
Packit 8dc392
// BBoxes: To test an axis-aligned bbox, test the center against each plane
Packit 8dc392
//         using the normal (v dot n - offset) method, but offset by the
Packit 8dc392
//         box extents dot the abs of the plane normal. (the result is NOT
Packit 8dc392
//         exact, but will not return false-negatives.)
Packit 8dc392
//
Packit 8dc392
// Spheres: To test a sphere, test the center against each plane
Packit 8dc392
//         using the normal (v dot n - offset) method, but offset by the
Packit 8dc392
//         sphere's radius. (the result is NOT exact, but will not return
Packit 8dc392
//         false-negatives.)
Packit 8dc392
//
Packit 8dc392
//
Packit 8dc392
// SPECIAL NOTE: "Where are the dot products?"
Packit 8dc392
//     Actual dot products are currently slow for most SIMD architectures.
Packit 8dc392
//     In order to keep this code optimization-ready, the dot products
Packit 8dc392
//     are all performed using vector adds and multipies.
Packit 8dc392
//
Packit 8dc392
//     In order to do this, the plane equations are stored in "transpose"
Packit 8dc392
//     form, with the X components grouped into an X vector, etc.
Packit 8dc392
//
Packit 8dc392
Packit 8dc392
Packit 8dc392
template <class T>
Packit 8dc392
class FrustumTest
Packit 8dc392
{
Packit 8dc392
public:
Packit 8dc392
    FrustumTest()
Packit 8dc392
    {
Packit 8dc392
        Frustum<T>  frust;
Packit 8dc392
        Matrix44<T> cameraMat;
Packit 8dc392
        cameraMat.makeIdentity();
Packit 8dc392
        setFrustum(frust, cameraMat);
Packit 8dc392
    }
Packit 8dc392
    FrustumTest(const Frustum<T> &frustum, const Matrix44<T> &cameraMat)
Packit 8dc392
    {
Packit 8dc392
        setFrustum(frustum, cameraMat);
Packit 8dc392
    }
Packit 8dc392
Packit 8dc392
    ////////////////////////////////////////////////////////////////////
Packit 8dc392
    // setFrustum()
Packit 8dc392
    // This updates the frustum test with a new frustum and matrix.
Packit 8dc392
    // This should usually be called just once per frame.
Packit 8dc392
    void setFrustum(const Frustum<T> &frustum, const Matrix44<T> &cameraMat);
Packit 8dc392
Packit 8dc392
    ////////////////////////////////////////////////////////////////////
Packit 8dc392
    // isVisible()
Packit 8dc392
    // Check to see if shapes are visible.
Packit 8dc392
    bool isVisible(const Sphere3<T> &sphere) const;
Packit 8dc392
    bool isVisible(const Box<Vec3<T> > &box) const;
Packit 8dc392
    bool isVisible(const Vec3<T> &vec) const;
Packit 8dc392
    
Packit 8dc392
    ////////////////////////////////////////////////////////////////////
Packit 8dc392
    // completelyContains()
Packit 8dc392
    // Check to see if shapes are entirely contained.
Packit 8dc392
    bool completelyContains(const Sphere3<T> &sphere) const;
Packit 8dc392
    bool completelyContains(const Box<Vec3<T> > &box) const;
Packit 8dc392
    
Packit 8dc392
    // These next items are kept primarily for debugging tools.
Packit 8dc392
    // It's useful for drawing the culling environment, and also
Packit 8dc392
    // for getting an "outside view" of the culling frustum.
Packit 8dc392
    IMATH_INTERNAL_NAMESPACE::Matrix44<T> cameraMat() const {return cameraMatrix;}
Packit 8dc392
    IMATH_INTERNAL_NAMESPACE::Frustum<T> currentFrustum() const {return currFrustum;}
Packit 8dc392
Packit 8dc392
protected:
Packit 8dc392
    // To understand why the planes are stored this way, see
Packit 8dc392
    // the SPECIAL NOTE above.
Packit 8dc392
    Vec3<T> planeNormX[2];  // The X compunents from 6 plane equations
Packit 8dc392
    Vec3<T> planeNormY[2];  // The Y compunents from 6 plane equations
Packit 8dc392
    Vec3<T> planeNormZ[2];  // The Z compunents from 6 plane equations
Packit 8dc392
Packit 8dc392
    Vec3<T> planeOffsetVec[2]; // The distance offsets from 6 plane equations
Packit 8dc392
Packit 8dc392
    // The absolute values are stored to assist with bounding box tests.
Packit 8dc392
    Vec3<T> planeNormAbsX[2];  // The abs(X) compunents from 6 plane equations
Packit 8dc392
    Vec3<T> planeNormAbsY[2];  // The abs(X) compunents from 6 plane equations
Packit 8dc392
    Vec3<T> planeNormAbsZ[2];  // The abs(X) compunents from 6 plane equations
Packit 8dc392
Packit 8dc392
    // These are kept primarily for debugging tools.
Packit 8dc392
    Frustum<T> currFrustum;
Packit 8dc392
    Matrix44<T> cameraMatrix;
Packit 8dc392
};
Packit 8dc392
Packit 8dc392
Packit 8dc392
////////////////////////////////////////////////////////////////////
Packit 8dc392
// setFrustum()
Packit 8dc392
// This should usually only be called once per frame, or however
Packit 8dc392
// often the camera moves.
Packit 8dc392
template<class T>
Packit 8dc392
void FrustumTest<T>::setFrustum(const Frustum<T> &frustum,
Packit 8dc392
                                const Matrix44<T> &cameraMat)
Packit 8dc392
{
Packit 8dc392
    Plane3<T> frustumPlanes[6];
Packit 8dc392
    frustum.planes(frustumPlanes, cameraMat);
Packit 8dc392
Packit 8dc392
    // Here's where we effectively transpose the plane equations.
Packit 8dc392
    // We stuff all six X's into the two planeNormX vectors, etc.
Packit 8dc392
    for (int i = 0; i < 2; ++i)
Packit 8dc392
    {
Packit 8dc392
        int index = i * 3;
Packit 8dc392
Packit 8dc392
        planeNormX[i]     = Vec3<T>(frustumPlanes[index + 0].normal.x,
Packit 8dc392
                                    frustumPlanes[index + 1].normal.x, 
Packit 8dc392
                                    frustumPlanes[index + 2].normal.x);
Packit 8dc392
        planeNormY[i]     = Vec3<T>(frustumPlanes[index + 0].normal.y,
Packit 8dc392
                                    frustumPlanes[index + 1].normal.y,
Packit 8dc392
                                    frustumPlanes[index + 2].normal.y);
Packit 8dc392
        planeNormZ[i]     = Vec3<T>(frustumPlanes[index + 0].normal.z,
Packit 8dc392
                                    frustumPlanes[index + 1].normal.z,
Packit 8dc392
                                    frustumPlanes[index + 2].normal.z);
Packit 8dc392
Packit 8dc392
        planeNormAbsX[i]  = Vec3<T>(IMATH_INTERNAL_NAMESPACE::abs(planeNormX[i].x),
Packit 8dc392
                                    IMATH_INTERNAL_NAMESPACE::abs(planeNormX[i].y), 
Packit 8dc392
                                    IMATH_INTERNAL_NAMESPACE::abs(planeNormX[i].z));
Packit 8dc392
        planeNormAbsY[i]  = Vec3<T>(IMATH_INTERNAL_NAMESPACE::abs(planeNormY[i].x), 
Packit 8dc392
                                    IMATH_INTERNAL_NAMESPACE::abs(planeNormY[i].y),
Packit 8dc392
                                    IMATH_INTERNAL_NAMESPACE::abs(planeNormY[i].z));
Packit 8dc392
        planeNormAbsZ[i]  = Vec3<T>(IMATH_INTERNAL_NAMESPACE::abs(planeNormZ[i].x), 
Packit 8dc392
                                    IMATH_INTERNAL_NAMESPACE::abs(planeNormZ[i].y),
Packit 8dc392
                                    IMATH_INTERNAL_NAMESPACE::abs(planeNormZ[i].z));
Packit 8dc392
Packit 8dc392
        planeOffsetVec[i] = Vec3<T>(frustumPlanes[index + 0].distance,
Packit 8dc392
                                    frustumPlanes[index + 1].distance,
Packit 8dc392
                                    frustumPlanes[index + 2].distance);
Packit 8dc392
    }
Packit 8dc392
    currFrustum = frustum;
Packit 8dc392
    cameraMatrix = cameraMat;
Packit 8dc392
}
Packit 8dc392
Packit 8dc392
Packit 8dc392
////////////////////////////////////////////////////////////////////
Packit 8dc392
// isVisible(Sphere)
Packit 8dc392
// Returns true if any part of the sphere is inside
Packit 8dc392
// the frustum.
Packit 8dc392
// The result MAY return close false-positives, but not false-negatives.
Packit 8dc392
//
Packit 8dc392
template<typename T>
Packit 8dc392
bool FrustumTest<T>::isVisible(const Sphere3<T> &sphere) const
Packit 8dc392
{
Packit 8dc392
    Vec3<T> center = sphere.center;
Packit 8dc392
    Vec3<T> radiusVec = Vec3<T>(sphere.radius, sphere.radius, sphere.radius);
Packit 8dc392
Packit 8dc392
    // This is a vertical dot-product on three vectors at once.
Packit 8dc392
    Vec3<T> d0  = planeNormX[0] * center.x 
Packit 8dc392
                + planeNormY[0] * center.y 
Packit 8dc392
                + planeNormZ[0] * center.z 
Packit 8dc392
                - radiusVec
Packit 8dc392
                - planeOffsetVec[0];
Packit 8dc392
Packit 8dc392
    if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    Vec3<T> d1  = planeNormX[1] * center.x 
Packit 8dc392
                + planeNormY[1] * center.y 
Packit 8dc392
                + planeNormZ[1] * center.z 
Packit 8dc392
                - radiusVec
Packit 8dc392
                - planeOffsetVec[1];
Packit 8dc392
Packit 8dc392
    if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    return true;
Packit 8dc392
}
Packit 8dc392
Packit 8dc392
////////////////////////////////////////////////////////////////////
Packit 8dc392
// completelyContains(Sphere)
Packit 8dc392
// Returns true if every part of the sphere is inside
Packit 8dc392
// the frustum.
Packit 8dc392
// The result MAY return close false-negatives, but not false-positives.
Packit 8dc392
//
Packit 8dc392
template<typename T>
Packit 8dc392
bool FrustumTest<T>::completelyContains(const Sphere3<T> &sphere) const
Packit 8dc392
{
Packit 8dc392
    Vec3<T> center = sphere.center;
Packit 8dc392
    Vec3<T> radiusVec = Vec3<T>(sphere.radius, sphere.radius, sphere.radius);
Packit 8dc392
Packit 8dc392
    // This is a vertical dot-product on three vectors at once.
Packit 8dc392
    Vec3<T> d0  = planeNormX[0] * center.x 
Packit 8dc392
                + planeNormY[0] * center.y 
Packit 8dc392
                + planeNormZ[0] * center.z 
Packit 8dc392
                + radiusVec
Packit 8dc392
                - planeOffsetVec[0];
Packit 8dc392
Packit 8dc392
    if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    Vec3<T> d1  = planeNormX[1] * center.x 
Packit 8dc392
                + planeNormY[1] * center.y 
Packit 8dc392
                + planeNormZ[1] * center.z 
Packit 8dc392
                + radiusVec
Packit 8dc392
                - planeOffsetVec[1];
Packit 8dc392
Packit 8dc392
    if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    return true;
Packit 8dc392
}
Packit 8dc392
Packit 8dc392
////////////////////////////////////////////////////////////////////
Packit 8dc392
// isVisible(Box)
Packit 8dc392
// Returns true if any part of the axis-aligned box
Packit 8dc392
// is inside the frustum.
Packit 8dc392
// The result MAY return close false-positives, but not false-negatives.
Packit 8dc392
//
Packit 8dc392
template<typename T>
Packit 8dc392
bool FrustumTest<T>::isVisible(const Box<Vec3<T> > &box) const
Packit 8dc392
{
Packit 8dc392
    if (box.isEmpty())
Packit 8dc392
        return false;
Packit 8dc392
    
Packit 8dc392
    Vec3<T> center = (box.min + box.max) / 2;
Packit 8dc392
    Vec3<T> extent = (box.max - center);
Packit 8dc392
Packit 8dc392
    // This is a vertical dot-product on three vectors at once.
Packit 8dc392
    Vec3<T> d0  = planeNormX[0] * center.x 
Packit 8dc392
                + planeNormY[0] * center.y 
Packit 8dc392
                + planeNormZ[0] * center.z
Packit 8dc392
                - planeNormAbsX[0] * extent.x 
Packit 8dc392
                - planeNormAbsY[0] * extent.y 
Packit 8dc392
                - planeNormAbsZ[0] * extent.z 
Packit 8dc392
                - planeOffsetVec[0];
Packit 8dc392
Packit 8dc392
    if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    Vec3<T> d1  = planeNormX[1] * center.x 
Packit 8dc392
                + planeNormY[1] * center.y 
Packit 8dc392
                + planeNormZ[1] * center.z
Packit 8dc392
                - planeNormAbsX[1] * extent.x 
Packit 8dc392
                - planeNormAbsY[1] * extent.y 
Packit 8dc392
                - planeNormAbsZ[1] * extent.z 
Packit 8dc392
                - planeOffsetVec[1];
Packit 8dc392
Packit 8dc392
    if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    return true;
Packit 8dc392
}
Packit 8dc392
Packit 8dc392
////////////////////////////////////////////////////////////////////
Packit 8dc392
// completelyContains(Box)
Packit 8dc392
// Returns true if every part of the axis-aligned box
Packit 8dc392
// is inside the frustum.
Packit 8dc392
// The result MAY return close false-negatives, but not false-positives.
Packit 8dc392
//
Packit 8dc392
template<typename T>
Packit 8dc392
bool FrustumTest<T>::completelyContains(const Box<Vec3<T> > &box) const
Packit 8dc392
{
Packit 8dc392
    if (box.isEmpty())
Packit 8dc392
        return false;
Packit 8dc392
    
Packit 8dc392
    Vec3<T> center = (box.min + box.max) / 2;
Packit 8dc392
    Vec3<T> extent = (box.max - center);
Packit 8dc392
Packit 8dc392
    // This is a vertical dot-product on three vectors at once.
Packit 8dc392
    Vec3<T> d0  = planeNormX[0] * center.x 
Packit 8dc392
                + planeNormY[0] * center.y 
Packit 8dc392
                + planeNormZ[0] * center.z
Packit 8dc392
                + planeNormAbsX[0] * extent.x 
Packit 8dc392
                + planeNormAbsY[0] * extent.y 
Packit 8dc392
                + planeNormAbsZ[0] * extent.z 
Packit 8dc392
                - planeOffsetVec[0];
Packit 8dc392
Packit 8dc392
    if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    Vec3<T> d1  = planeNormX[1] * center.x 
Packit 8dc392
                + planeNormY[1] * center.y 
Packit 8dc392
                + planeNormZ[1] * center.z
Packit 8dc392
                + planeNormAbsX[1] * extent.x 
Packit 8dc392
                + planeNormAbsY[1] * extent.y 
Packit 8dc392
                + planeNormAbsZ[1] * extent.z 
Packit 8dc392
                - planeOffsetVec[1];
Packit 8dc392
Packit 8dc392
    if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    return true;
Packit 8dc392
}
Packit 8dc392
Packit 8dc392
Packit 8dc392
////////////////////////////////////////////////////////////////////
Packit 8dc392
// isVisible(Vec3)
Packit 8dc392
// Returns true if the point is inside the frustum.
Packit 8dc392
//
Packit 8dc392
template<typename T>
Packit 8dc392
bool FrustumTest<T>::isVisible(const Vec3<T> &vec) const
Packit 8dc392
{
Packit 8dc392
    // This is a vertical dot-product on three vectors at once.
Packit 8dc392
    Vec3<T> d0  = (planeNormX[0] * vec.x) 
Packit 8dc392
                + (planeNormY[0] * vec.y) 
Packit 8dc392
                + (planeNormZ[0] * vec.z) 
Packit 8dc392
                - planeOffsetVec[0];
Packit 8dc392
Packit 8dc392
    if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    Vec3<T> d1  = (planeNormX[1] * vec.x) 
Packit 8dc392
                + (planeNormY[1] * vec.y) 
Packit 8dc392
                + (planeNormZ[1] * vec.z) 
Packit 8dc392
                - planeOffsetVec[1];
Packit 8dc392
Packit 8dc392
    if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
Packit 8dc392
        return false;
Packit 8dc392
Packit 8dc392
    return true;
Packit 8dc392
}
Packit 8dc392
Packit 8dc392
Packit 8dc392
typedef FrustumTest<float>	FrustumTestf;
Packit 8dc392
typedef FrustumTest<double> FrustumTestd;
Packit 8dc392
Packit 8dc392
IMATH_INTERNAL_NAMESPACE_HEADER_EXIT
Packit 8dc392
Packit 8dc392
#endif // INCLUDED_IMATHFRUSTUMTEST_H