frustum.cpp

Go to the documentation of this file.

/*
 * frustum.cpp
 *
 * Copyright (C) 2009  Thomas A. Vaughan
 * All rights reserved.
 *
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the <organization> nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Implementation of frustum methods.  See frustum.h
 */

// includes --------------------------------------------------------------------
#include "frustum.h"            // always include our own header first

#include <math.h>



////////////////////////////////////////////////////////////////////////////////
//
//      static helper methods
//
////////////////////////////////////////////////////////////////////////////////

static void
setFrustumPlane
(
IO frustum_t& f,
IN frustum_t::ePlane index,
IN const point3d_t& a,          ///< one vector in plane
IN const point3d_t& b,          ///< another vector in plane
IN const point3d_t& p           ///< a point in the plane
)
throw()
{
        plane_t& plane = f.plane[index];

        // calculate normal based on the two vectors in the plane
        plane.n = crossProduct(a, b);
        normalize(plane.n);

        // calculate distance from origin to plane
        plane.d = dotProduct(plane.n, p);
}



static float
getTimeWhenLineIntersectsPlane
(
IN const plane_t& P,
IN const point3d_t& p0,
IN const point3d_t& pt
)
throw()
{
        float denom = dotProduct(P.n, pt);
        float np = dotProduct(P.n, p0);

        return (P.d - np) / denom;
}



////////////////////////////////////////////////////////////////////////////////
//
//      public API
//
////////////////////////////////////////////////////////////////////////////////

eContains
frustum_t::containsRect
(
IN const rect3d_t& r
)
const
throw()
{
        // see http://www.lighthouse3d.com/opengl/viewfrustum/index.php?gatest2
        //   for details.  In particular, this method will sometimes incorrectly
        //   include rectangles that should be rejected.  But that is safer than
        //   inappropriately rejecting rectangles, and is rare enough to not
        //   cause performance problems.
        eContains retval = eContains_Fully;   // assume rect is fully contained

        // check each plane
        for (int i = 0; i < ePlaneCount; ++i) {
                bool someInside = false;     // some rect vertices in frustum?
                bool someOutside = false;    // some rect vertices outside?

                // loop over all corners of rectangle
                for (int j = 0; j < 8 && (!someInside || !someOutside); ++j) {
                        if (plane[i].distance(r.getCorner(j)) < 0) {
                                someOutside = true;
                        } else {
                                someInside = true;
                        }
                }

                if (!someInside) {
                        // no rectangle corners inside frustum!
                        return eContains_None;  // rect does not intersect
                }

                if (someOutside) {
                        // some points in, some out
                        retval = eContains_Partial;
                }
        }

        // if we get here, rect is fully or partially contained by frustum
        return retval;
}



void
frustum_t::getEdge
(
IN int index,
OUT point3d_t& p0,
OUT point3d_t& p1
)
const
throw()
{
        ASSERT(index >= 0 && index < eEdgeCount,
            "Bad frustum edge index: %d", index);

        // every edge is described as:
        //  - the line where two planes meet
        //  - start and end of edge are where additional planes intersect
        // so each edge is determined by 4 planes:
        //  - the 2 planes that define the line
        //  - the 2 planes that define the start and end points of the edge

        struct edge_info_t {
                int             planeA; // first intersection plane
                int             planeB; // second intersection plane
                int             start;  // plane that defines start point
                int             end;    // plane that defines end point
        };

        static edge_info_t s_edgeInfo[eEdgeCount] = {
                // A            B               start           end
                { eTop,         eRight,         eNear,          eFar },
                { eRight,       eBottom,        eNear,          eFar },
                { eBottom,      eLeft,          eNear,          eFar },
                { eLeft,        eTop,           eNear,          eFar },

                { eNear,        eTop,           eLeft,          eRight },
                { eNear,        eRight,         eTop,           eBottom },
                { eNear,        eBottom,        eRight,         eLeft },
                { eNear,        eLeft,          eBottom,        eTop },

                { eFar,         eTop,           eLeft,          eRight },
                { eFar,         eRight,         eTop,           eBottom },
                { eFar,         eBottom,        eRight,         eLeft },
                { eFar,         eLeft,          eBottom,        eTop }
        };

        const edge_info_t& ei = s_edgeInfo[index];

        // get the equation of the line for the two intersecting planes
        //  p(t) = p + t pt
        const plane_t& A = plane[ei.planeA];
        const plane_t& B = plane[ei.planeB];

        point3d_t p, pt;
        ASSERT(getLineOfIntersection(A, B, p, pt),
            "Badly constructed frustum?  Two adjacent planes are parallel?");

//      p.dump("p");
//      pt.dump("pt");

        // now determine start and end points
        float t0 = getTimeWhenLineIntersectsPlane(plane[ei.start], p, pt);
        float t1 = getTimeWhenLineIntersectsPlane(plane[ei.end], p, pt);

//      DPRINTF("t0=%f   t1=%f", t0, t1);

        // calculate and return
        p0 = p + t0 * pt;
        p1 = p + t1 * pt;
}



////////////////////////////////////////////////////////////////////////////////
//
//      public API
//
////////////////////////////////////////////////////////////////////////////////

bool
createViewFrustum
(
IN const point3d_t& position,
IN const point3d_t& facing,
IN const point3d_t& up,
IN float fovyRadians,
IN float zNear,
IN float zFar,
IN float aspect,
OUT frustum_t& f
)
throw()
{
        ASSERT(fovyRadians > 0, "bad field of view: %f", fovyRadians);
        ASSERT(zNear > 0, "Bad z near: %f", zNear);
        ASSERT(zFar > zNear, "Bad z far: %f", zFar);
        ASSERT(aspect > 0, "Bad aspect ratio: %f", aspect);
        f.clear();

        // We use basic geometry to get the frustum.  See
        // http://www.lighthouse3d.com/opengl/viewfrustum/index.php?gaplanes
//      DPRINTF("Calculating view frustum (aspect = %f)...", aspect);

        // need to ensure these are normalized
//      position.dump("  position");
//      facing.dump("  facing");
//      up.dump("  up");

        // based on up and facing, we can calculate which direction is "right"
        point3d_t right = crossProduct(facing, up);
//      right.dump("  right");
        normalize(right);

        // we trust the facing and right directions, but not "up"!
        // do another cross product
        point3d_t newUp = crossProduct(right, facing);
        normalize(newUp);

        // we mostly care about the near and far planes
        point3d_t nc;           // center of near plane
        point3d_t fc;           // center of far plane

        nc = position + zNear * facing;
        fc = position + zFar * facing;

//      nc.dump("  center of near plane");
//      fc.dump("  center of far plane");

        // height of planes
        float yRadians = 0.5 * fovyRadians;

        float hScale = tan(yRadians);
        float wScale = aspect * hScale;

        // these are actually HALF heights and widths
        float farHeight = hScale * zFar;
        float farWidth = wScale * zFar;

        float nearHeight = hScale * zNear;
        float nearWidth = wScale * zNear;

//      DPRINTF("  Far plane half height, width:  %f x %f meters",
//          farHeight, farWidth);
//      DPRINTF("  Near plane half height, width: %f x %f meters",
//          nearHeight, nearWidth);

        // these are the interesting points (corners) of the frustum
        point3d_t ftl;          // far plane, top left corner
        point3d_t ftr;          // far plane, top right corner
        point3d_t fbl;          // far plane, bottom left
        point3d_t fbr;          // far plane, bottom right

        point3d_t ntl;          // near plane, top left
        point3d_t ntr;          // near plane, top right
        point3d_t nbl;          // near bottom left
        point3d_t nbr;          // near bottom right

        ftl = fc + farHeight * newUp - farWidth * right;
        ftr = fc + farHeight * newUp + farWidth * right;
        fbl = fc - farHeight * newUp - farWidth * right;
        fbr = fc - farHeight * newUp + farWidth * right;

        ntl = nc + nearHeight * newUp - nearWidth * right;
        ntr = nc + nearHeight * newUp + nearWidth * right;
        nbl = nc - nearHeight * newUp - nearWidth * right;
        nbr = nc - nearHeight * newUp + nearWidth * right;

//      ftl.dump("  far top left     ");
//      ftr.dump("  far top right    ");
//      fbl.dump("  far bottom left  ");
//      fbr.dump("  far bottom right ");

//      ntl.dump("  near top left    ");
//      ntr.dump("  near top right   ");
//      nbl.dump("  near bottom left ");
//      nbr.dump("  near bottom right");

        // compute plane normals and distances
        //   (all normals point *into* frustum)
        // To do this, we provide two vectors in the plane, such that their
        //   cross product points into the frustum.
        // We also provide a point known to be in the plane.
        //                 plane index          vector  vector          point
        setFrustumPlane(f, frustum_t::eFar,     right,  newUp,          fc);
        setFrustumPlane(f, frustum_t::eNear,    newUp,  right,          nc);
        setFrustumPlane(f, frustum_t::eLeft,    newUp,  ntl - ftl,      position);
        setFrustumPlane(f, frustum_t::eRight,   newUp,  ftr - ntr,      position);
        setFrustumPlane(f, frustum_t::eTop,     right,  ntr - ftr,      position);
        setFrustumPlane(f, frustum_t::eBottom,  right,  fbr - nbr,      position);

//      f.dump("  final frustum");
        return true;
}