wavepacket-lib/lib/geometry/frustum.cpp

Go to the documentation of this file.
00001 /*
00002  * frustum.cpp
00003  *
00004  * Copyright (C) 2009  Thomas A. Vaughan
00005  * All rights reserved.
00006  *
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions are met:
00010  *     * Redistributions of source code must retain the above copyright
00011  *       notice, this list of conditions and the following disclaimer.
00012  *     * Redistributions in binary form must reproduce the above copyright
00013  *       notice, this list of conditions and the following disclaimer in the
00014  *       documentation and/or other materials provided with the distribution.
00015  *     * Neither the name of the <organization> nor the
00016  *       names of its contributors may be used to endorse or promote products
00017  *       derived from this software without specific prior written permission.
00018  *
00019  * THIS SOFTWARE IS PROVIDED BY THOMAS A. VAUGHAN ''AS IS'' AND ANY
00020  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
00021  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00022  * DISCLAIMED. IN NO EVENT SHALL THOMAS A. VAUGHAN BE LIABLE FOR ANY
00023  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
00024  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00025  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
00026  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00027  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00028  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00029  *
00030  *
00031  * Implementation of frustum methods.  See frustum.h
00032  */
00033 
00034 // includes --------------------------------------------------------------------
00035 #include "frustum.h"            // always include our own header first
00036 
00037 #include <math.h>
00038 
00039 
00040 
00041 ////////////////////////////////////////////////////////////////////////////////
00042 //
00043 //      static helper methods
00044 //
00045 ////////////////////////////////////////////////////////////////////////////////
00046 
00047 static void
00048 setFrustumPlane
00049 (
00050 IO frustum_t& f,
00051 IN frustum_t::ePlane index,
00052 IN const point3d_t& a,          ///< one vector in plane
00053 IN const point3d_t& b,          ///< another vector in plane
00054 IN const point3d_t& p           ///< a point in the plane
00055 )
00056 throw()
00057 {
00058         plane_t& plane = f.plane[index];
00059 
00060         // calculate normal based on the two vectors in the plane
00061         plane.n = crossProduct(a, b);
00062         normalize(plane.n);
00063 
00064         // calculate distance from origin to plane
00065         plane.d = dotProduct(plane.n, p);
00066 }
00067 
00068 
00069 
00070 static float
00071 getTimeWhenLineIntersectsPlane
00072 (
00073 IN const plane_t& P,
00074 IN const point3d_t& p0,
00075 IN const point3d_t& pt
00076 )
00077 throw()
00078 {
00079         float denom = dotProduct(P.n, pt);
00080         float np = dotProduct(P.n, p0);
00081 
00082         return (P.d - np) / denom;
00083 }
00084 
00085 
00086 
00087 ////////////////////////////////////////////////////////////////////////////////
00088 //
00089 //      public API
00090 //
00091 ////////////////////////////////////////////////////////////////////////////////
00092 
00093 eContains
00094 frustum_t::containsRect
00095 (
00096 IN const rect3d_t& r
00097 )
00098 const
00099 throw()
00100 {
00101         // see http://www.lighthouse3d.com/opengl/viewfrustum/index.php?gatest2
00102         //   for details.  In particular, this method will sometimes incorrectly
00103         //   include rectangles that should be rejected.  But that is safer than
00104         //   inappropriately rejecting rectangles, and is rare enough to not
00105         //   cause performance problems.
00106         eContains retval = eContains_Fully;   // assume rect is fully contained
00107 
00108         // check each plane
00109         for (int i = 0; i < ePlaneCount; ++i) {
00110                 bool someInside = false;     // some rect vertices in frustum?
00111                 bool someOutside = false;    // some rect vertices outside?
00112 
00113                 // loop over all corners of rectangle
00114                 for (int j = 0; j < 8 && (!someInside || !someOutside); ++j) {
00115                         if (plane[i].distance(r.getCorner(j)) < 0) {
00116                                 someOutside = true;
00117                         } else {
00118                                 someInside = true;
00119                         }
00120                 }
00121 
00122                 if (!someInside) {
00123                         // no rectangle corners inside frustum!
00124                         return eContains_None;  // rect does not intersect
00125                 }
00126 
00127                 if (someOutside) {
00128                         // some points in, some out
00129                         retval = eContains_Partial;
00130                 }
00131         }
00132 
00133         // if we get here, rect is fully or partially contained by frustum
00134         return retval;
00135 }
00136 
00137 
00138 
00139 void
00140 frustum_t::getEdge
00141 (
00142 IN int index,
00143 OUT point3d_t& p0,
00144 OUT point3d_t& p1
00145 )
00146 const
00147 throw()
00148 {
00149         ASSERT(index >= 0 && index < eEdgeCount,
00150             "Bad frustum edge index: %d", index);
00151 
00152         // every edge is described as:
00153         //  - the line where two planes meet
00154         //  - start and end of edge are where additional planes intersect
00155         // so each edge is determined by 4 planes:
00156         //  - the 2 planes that define the line
00157         //  - the 2 planes that define the start and end points of the edge
00158 
00159         struct edge_info_t {
00160                 int             planeA; // first intersection plane
00161                 int             planeB; // second intersection plane
00162                 int             start;  // plane that defines start point
00163                 int             end;    // plane that defines end point
00164         };
00165 
00166         static edge_info_t s_edgeInfo[eEdgeCount] = {
00167                 // A            B               start           end
00168                 { eTop,         eRight,         eNear,          eFar },
00169                 { eRight,       eBottom,        eNear,          eFar },
00170                 { eBottom,      eLeft,          eNear,          eFar },
00171                 { eLeft,        eTop,           eNear,          eFar },
00172 
00173                 { eNear,        eTop,           eLeft,          eRight },
00174                 { eNear,        eRight,         eTop,           eBottom },
00175                 { eNear,        eBottom,        eRight,         eLeft },
00176                 { eNear,        eLeft,          eBottom,        eTop },
00177 
00178                 { eFar,         eTop,           eLeft,          eRight },
00179                 { eFar,         eRight,         eTop,           eBottom },
00180                 { eFar,         eBottom,        eRight,         eLeft },
00181                 { eFar,         eLeft,          eBottom,        eTop }
00182         };
00183 
00184         const edge_info_t& ei = s_edgeInfo[index];
00185 
00186         // get the equation of the line for the two intersecting planes
00187         //  p(t) = p + t pt
00188         const plane_t& A = plane[ei.planeA];
00189         const plane_t& B = plane[ei.planeB];
00190 
00191         point3d_t p, pt;
00192         ASSERT(getLineOfIntersection(A, B, p, pt),
00193             "Badly constructed frustum?  Two adjacent planes are parallel?");
00194 
00195 //      p.dump("p");
00196 //      pt.dump("pt");
00197 
00198         // now determine start and end points
00199         float t0 = getTimeWhenLineIntersectsPlane(plane[ei.start], p, pt);
00200         float t1 = getTimeWhenLineIntersectsPlane(plane[ei.end], p, pt);
00201 
00202 //      DPRINTF("t0=%f   t1=%f", t0, t1);
00203 
00204         // calculate and return
00205         p0 = p + t0 * pt;
00206         p1 = p + t1 * pt;
00207 }
00208 
00209 
00210 
00211 ////////////////////////////////////////////////////////////////////////////////
00212 //
00213 //      public API
00214 //
00215 ////////////////////////////////////////////////////////////////////////////////
00216 
00217 bool
00218 createViewFrustum
00219 (
00220 IN const point3d_t& position,
00221 IN const point3d_t& facing,
00222 IN const point3d_t& up,
00223 IN float fovyRadians,
00224 IN float zNear,
00225 IN float zFar,
00226 IN float aspect,
00227 OUT frustum_t& f
00228 )
00229 throw()
00230 {
00231         ASSERT(fovyRadians > 0, "bad field of view: %f", fovyRadians);
00232         ASSERT(zNear > 0, "Bad z near: %f", zNear);
00233         ASSERT(zFar > zNear, "Bad z far: %f", zFar);
00234         ASSERT(aspect > 0, "Bad aspect ratio: %f", aspect);
00235         f.clear();
00236 
00237         // We use basic geometry to get the frustum.  See
00238         // http://www.lighthouse3d.com/opengl/viewfrustum/index.php?gaplanes
00239 //      DPRINTF("Calculating view frustum (aspect = %f)...", aspect);
00240 
00241         // need to ensure these are normalized
00242 //      position.dump("  position");
00243 //      facing.dump("  facing");
00244 //      up.dump("  up");
00245 
00246         // based on up and facing, we can calculate which direction is "right"
00247         point3d_t right = crossProduct(facing, up);
00248 //      right.dump("  right");
00249         normalize(right);
00250 
00251         // we trust the facing and right directions, but not "up"!
00252         // do another cross product
00253         point3d_t newUp = crossProduct(right, facing);
00254         normalize(newUp);
00255 
00256         // we mostly care about the near and far planes
00257         point3d_t nc;           // center of near plane
00258         point3d_t fc;           // center of far plane
00259 
00260         nc = position + zNear * facing;
00261         fc = position + zFar * facing;
00262 
00263 //      nc.dump("  center of near plane");
00264 //      fc.dump("  center of far plane");
00265 
00266         // height of planes
00267         float yRadians = 0.5 * fovyRadians;
00268 
00269         float hScale = tan(yRadians);
00270         float wScale = aspect * hScale;
00271 
00272         // these are actually HALF heights and widths
00273         float farHeight = hScale * zFar;
00274         float farWidth = wScale * zFar;
00275 
00276         float nearHeight = hScale * zNear;
00277         float nearWidth = wScale * zNear;
00278 
00279 //      DPRINTF("  Far plane half height, width:  %f x %f meters",
00280 //          farHeight, farWidth);
00281 //      DPRINTF("  Near plane half height, width: %f x %f meters",
00282 //          nearHeight, nearWidth);
00283 
00284         // these are the interesting points (corners) of the frustum
00285         point3d_t ftl;          // far plane, top left corner
00286         point3d_t ftr;          // far plane, top right corner
00287         point3d_t fbl;          // far plane, bottom left
00288         point3d_t fbr;          // far plane, bottom right
00289 
00290         point3d_t ntl;          // near plane, top left
00291         point3d_t ntr;          // near plane, top right
00292         point3d_t nbl;          // near bottom left
00293         point3d_t nbr;          // near bottom right
00294 
00295         ftl = fc + farHeight * newUp - farWidth * right;
00296         ftr = fc + farHeight * newUp + farWidth * right;
00297         fbl = fc - farHeight * newUp - farWidth * right;
00298         fbr = fc - farHeight * newUp + farWidth * right;
00299 
00300         ntl = nc + nearHeight * newUp - nearWidth * right;
00301         ntr = nc + nearHeight * newUp + nearWidth * right;
00302         nbl = nc - nearHeight * newUp - nearWidth * right;
00303         nbr = nc - nearHeight * newUp + nearWidth * right;
00304 
00305 //      ftl.dump("  far top left     ");
00306 //      ftr.dump("  far top right    ");
00307 //      fbl.dump("  far bottom left  ");
00308 //      fbr.dump("  far bottom right ");
00309 
00310 //      ntl.dump("  near top left    ");
00311 //      ntr.dump("  near top right   ");
00312 //      nbl.dump("  near bottom left ");
00313 //      nbr.dump("  near bottom right");
00314 
00315         // compute plane normals and distances
00316         //   (all normals point *into* frustum)
00317         // To do this, we provide two vectors in the plane, such that their
00318         //   cross product points into the frustum.
00319         // We also provide a point known to be in the plane.
00320         //                 plane index          vector  vector          point
00321         setFrustumPlane(f, frustum_t::eFar,     right,  newUp,          fc);
00322         setFrustumPlane(f, frustum_t::eNear,    newUp,  right,          nc);
00323         setFrustumPlane(f, frustum_t::eLeft,    newUp,  ntl - ftl,      position);
00324         setFrustumPlane(f, frustum_t::eRight,   newUp,  ftr - ntr,      position);
00325         setFrustumPlane(f, frustum_t::eTop,     right,  ntr - ftr,      position);
00326         setFrustumPlane(f, frustum_t::eBottom,  right,  fbr - nbr,      position);
00327 
00328 //      f.dump("  final frustum");
00329         return true;
00330 }
00331