simgear/scene/sky/clouds3d/camutils.cpp

   1 //------------------------------------------------------------------------------
   2 // File : camutils.cpp
   3 //------------------------------------------------------------------------------
   4 // GLVU : Copyright 1997 - 2002
   5 //        The University of North Carolina at Chapel Hill
   6 //------------------------------------------------------------------------------
   7 // Permission to use, copy, modify, distribute and sell this software and its
   8 // documentation for any purpose is hereby granted without fee, provided that
   9 // the above copyright notice appear in all copies and that both that copyright
  10 // notice and this permission notice appear in supporting documentation.
  11 // Binaries may be compiled with this software without any royalties or
  12 // restrictions.
  13 //
  14 // The University of North Carolina at Chapel Hill makes no representations
  15 // about the suitability of this software for any purpose. It is provided
  16 // "as is" without express or implied warranty.
  17
  18 //============================================================================
  19 // camutils.cpp : a set of camera utility functions
  20 //============================================================================
  21
  22 #include "camutils.hpp"
  23 #include "plane.hpp"
  24 #include "tri.hpp"
  25 #include "minmaxbox.hpp"
  26
  27 //----------------------------------------------------------------------------
  28 // Given a camera's 8 corner vertices and its 6 side planes and a triangle ABC,
  29 // return whether or not the tri overlaps the camera's frustum.
  30 //----------------------------------------------------------------------------
  31 int CamTriOverlap(const Vec3f V[8], const float P[][4],
  32                   const Vec3f& A, const Vec3f& B, const Vec3f& C)
  33 {
  34   // TEST TRIANGLE AGAINST ALL PLANES OF CAMERA, FOR EACH VERTEX CLASSIFY
  35   // AS INSIDE OR OUTSIDE OF PLANE (BY SETTING APPROPRIATE BIT IN BITMASK)
  36   // FOR EACH VERTEX, WE HAVE A BITMASK INDICATING WHETHER THE VERTEX
  37   // IS IN OR OUT OF EACH PLANE (LS 6-BITS, SET MEANS "OUT")
  38   unsigned int BitMaskA=0, BitMaskB=0, BitMaskC=0;
  39   unsigned int PlaneBitMask=1;  // CURRENT PLANE BEING CHECKED
  40   int i;
  41   for (i=0; i<6; i++)
  42   {
  43     if ( PlanePtOutTest(P[i], &(A.x)) ) BitMaskA |= PlaneBitMask;
  44     if ( PlanePtOutTest(P[i], &(B.x)) ) BitMaskB |= PlaneBitMask;
  45     if ( PlanePtOutTest(P[i], &(C.x)) ) BitMaskC |= PlaneBitMask;
  46     PlaneBitMask<<=1;
  47   }
  48
  49   // TRIVIAL ACCEPTANCE: IF ANY VERTEX IS COMPLETELY INSIDE ALL PLANES (=0)
  50   if (BitMaskA==0 || BitMaskB==0 || BitMaskC==0) return(1);
  51
  52   // TRIVIAL REJECTION: IF ALL VERTICES ARE OUTSIDE OF ANY PLANE
  53   PlaneBitMask=1;
  54   for (i=0; i<6; i++)
  55   {
  56     if ((BitMaskA & BitMaskB & BitMaskC & PlaneBitMask) > 0) return(0);
  57     PlaneBitMask<<=1;
  58   }
  59
  60   // TEST EDGES OF TRIANGLE AGAINST PLANES OF CAMERA
  61   float InT, OutT;
  62   if ( PlanesEdgeIsect(P,6,&(A.x),&(B.x),&InT,&OutT) ) return(1);
  63   if ( PlanesEdgeIsect(P,6,&(B.x),&(C.x),&InT,&OutT) ) return(1);
  64   if ( PlanesEdgeIsect(P,6,&(C.x),&(A.x),&InT,&OutT) ) return(1);
  65
  66   // TEST EDGES OF CAMERA AGAINST TRIANGLE
  67   float IsectPt[3];
  68   if ( EdgeTriIsect(&(V[0].x),&(V[4].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  69   if ( EdgeTriIsect(&(V[1].x),&(V[5].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  70   if ( EdgeTriIsect(&(V[2].x),&(V[6].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  71   if ( EdgeTriIsect(&(V[3].x),&(V[7].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  72   if ( EdgeTriIsect(&(V[1].x),&(V[0].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  73   if ( EdgeTriIsect(&(V[5].x),&(V[4].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  74   if ( EdgeTriIsect(&(V[6].x),&(V[7].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  75   if ( EdgeTriIsect(&(V[2].x),&(V[3].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  76   if ( EdgeTriIsect(&(V[4].x),&(V[7].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  77   if ( EdgeTriIsect(&(V[5].x),&(V[6].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  78   if ( EdgeTriIsect(&(V[1].x),&(V[2].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  79   if ( EdgeTriIsect(&(V[0].x),&(V[3].x),&(A.x),&(B.x),&(C.x),IsectPt) ) return(1);
  80
  81   return(0);
  82 }
  83
  84 int CamTriOverlap(const Camera *Cam,
  85                   const Vec3f& A, const Vec3f& B, const Vec3f& C)
  86 {
  87   // GET CAMERA VERTICES
  88   Vec3f V[8];
  89   Cam->CalcVerts(V);
  90
  91   // CALCULATE SIX CAMERA PLANES FROM CAMERA VERTICES
  92   float P[6][4];
  93   CalcCamPlanes(V,P);
  94
  95   return( CamTriOverlap(V,P,A,B,C) );
  96 }
  97
  98 //----------------------------------------------------------------------------
  99 // Temporary implementation of CamQuadOverlap (uses CamTriOverlap).
 100 //----------------------------------------------------------------------------
 101 int CamQuadOverlap(
 102   const Camera *Cam,
 103   const Vec3f& A, const Vec3f& B, const Vec3f& C, const Vec3f& D)
 104 {
 105   if ( CamTriOverlap(Cam,A,B,C) ) return(1);
 106   if ( CamTriOverlap(Cam,C,D,A) ) return(1);
 107   return(0);
 108 }
 109
 110 int CamQuadOverlap(
 111   const Camera *Cam,
 112   const float A[3], const float B[3], const float C[3], const float D[3])
 113 {
 114   Vec3f a(A),b(B),c(C),d(D);
 115   return( CamQuadOverlap(Cam,a,b,c,d) );
 116 }
 117
 118 //----------------------------------------------------------------------------
 119 // Calculate the six planes for a camera. User must have prealloced an array
 120 // of 24 floats (6 planes * 4 coeffs each). Two version: 1 that calculates
 121 // the camera vertices, requires the cam verts to be precomputed
 122 //----------------------------------------------------------------------------
 123 void CalcCamPlanes(const Vec3f *V, float P[][4])
 124 {
 125   PlaneEquation(P[0], &(V[2].x),&(V[5].x),&(V[6].x)); // LEFT
 126   PlaneEquation(P[1], &(V[0].x),&(V[7].x),&(V[4].x)); // RIGHT
 127   PlaneEquation(P[2], &(V[3].x),&(V[6].x),&(V[7].x)); // BOTTOM
 128   PlaneEquation(P[3], &(V[1].x),&(V[4].x),&(V[5].x)); // TOP
 129   PlaneEquation(P[4], &(V[1].x),&(V[2].x),&(V[0].x)); // NEAR
 130   PlaneEquation(P[5], &(V[4].x),&(V[6].x),&(V[5].x)); // FAR
 131 }
 132
 133 void CalcCamPlanes(const Camera *Cam, float P[][4])
 134 {
 135   Vec3f V[8];
 136   Cam->CalcVerts(V);
 137   CalcCamPlanes(V,P);
 138 }
 139
 140 //--------------------------------------------------------------------------
 141 // Camera view-frustum/MinMaxBox (AABB) overlap test: given the extents of the
 142 // AABB returns the type of overlap determined (complete out(1), partial (0),
 143 // complete in (-1)) m and M are the min and max extents of the AABB respectively.
 144 // Version is provided that takes in a precomputed set of camera vertices
 145 // and planes
 146 //--------------------------------------------------------------------------
 147 int CamMinMaxBoxOverlap(
 148   const Camera *Cam, const Vec3f V1[8], const float cP[][4],
 149   const Vec3f& m, const Vec3f& M)
 150 {
 151   // GO FOR TRIVIAL REJECTION OR ACCEPTANCE USING "FASTER OVERLAP TEST"
 152   int CompletelyIn=1;    // ASSUME COMPLETELY IN UNTIL ONE COUNTEREXAMPLE
 153   int R;                 // TEST RETURN VALUE
 154   for (int i=0; i<6; i++)
 155   {
 156     R=PlaneMinMaxBoxOverlap(cP[i],&(m.x),&(M.x));
 157     if(R==COMPLETEOUT) return(COMPLETEOUT);
 158     else if(R==PARTIAL) CompletelyIn=0;
 159   }
 160
 161   if (CompletelyIn) return(COMPLETEIN);  // CHECK IF STILL COMPLETELY "IN"
 162
 163   // TEST IF VIEW-FRUSTUM EDGES PROTRUDE THROUGH AABB
 164   float InT, OutT;
 165   if ( EdgeMinMaxBoxIsect(&(V1[0].x),&(V1[4].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 166   if ( EdgeMinMaxBoxIsect(&(V1[1].x),&(V1[5].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 167   if ( EdgeMinMaxBoxIsect(&(V1[2].x),&(V1[6].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 168   if ( EdgeMinMaxBoxIsect(&(V1[3].x),&(V1[7].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 169   if ( EdgeMinMaxBoxIsect(&(V1[0].x),&(V1[1].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 170   if ( EdgeMinMaxBoxIsect(&(V1[1].x),&(V1[2].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 171   if ( EdgeMinMaxBoxIsect(&(V1[2].x),&(V1[3].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 172   if ( EdgeMinMaxBoxIsect(&(V1[3].x),&(V1[0].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 173   if ( EdgeMinMaxBoxIsect(&(V1[4].x),&(V1[5].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 174   if ( EdgeMinMaxBoxIsect(&(V1[5].x),&(V1[6].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 175   if ( EdgeMinMaxBoxIsect(&(V1[6].x),&(V1[7].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 176   if ( EdgeMinMaxBoxIsect(&(V1[7].x),&(V1[0].x),&(m.x),&(M.x),&InT,&OutT) ) return(PARTIAL);
 177
 178   // COMPUTE VERTICES OF AABB
 179   float bV[8][3];
 180   GetMinMaxBoxVerts(&(m.x),&(M.x),bV);
 181
 182   // TEST FOR PROTRUSION OF AABB EDGES THROUGH VIEW-FRUSTUM
 183   if ( PlanesEdgeIsect(cP,6,bV[0],bV[4],&InT,&OutT) ) return(PARTIAL);
 184   if ( PlanesEdgeIsect(cP,6,bV[1],bV[5],&InT,&OutT) ) return(PARTIAL);
 185   if ( PlanesEdgeIsect(cP,6,bV[2],bV[6],&InT,&OutT) ) return(PARTIAL);
 186   if ( PlanesEdgeIsect(cP,6,bV[3],bV[7],&InT,&OutT) ) return(PARTIAL);
 187   if ( PlanesEdgeIsect(cP,6,bV[0],bV[1],&InT,&OutT) ) return(PARTIAL);
 188   if ( PlanesEdgeIsect(cP,6,bV[1],bV[2],&InT,&OutT) ) return(PARTIAL);
 189   if ( PlanesEdgeIsect(cP,6,bV[2],bV[3],&InT,&OutT) ) return(PARTIAL);
 190   if ( PlanesEdgeIsect(cP,6,bV[3],bV[0],&InT,&OutT) ) return(PARTIAL);
 191   if ( PlanesEdgeIsect(cP,6,bV[4],bV[5],&InT,&OutT) ) return(PARTIAL);
 192   if ( PlanesEdgeIsect(cP,6,bV[5],bV[6],&InT,&OutT) ) return(PARTIAL);
 193   if ( PlanesEdgeIsect(cP,6,bV[6],bV[7],&InT,&OutT) ) return(PARTIAL);
 194   if ( PlanesEdgeIsect(cP,6,bV[7],bV[0],&InT,&OutT) ) return(PARTIAL);
 195
 196   // VF MUST BE COMPLETELY ENCLOSED SINCE PT IS NOT "OUT "OF ANY AABB PLANE.
 197   //return(COMPLETEOUT);
 198         return (PARTIAL);
 199 };
 200
 201 int CamMinMaxBoxOverlap(
 202   const Camera *Cam, const float m[3], const float M[3])
 203 {
 204   // GET CAMERA VERTICES
 205   Vec3f V1[8];
 206   Cam->CalcVerts(V1);
 207
 208   // CALCULATE SIX CAMERA PLANES FROM CAMERA VERTICES
 209   float cP[6][4];
 210   CalcCamPlanes(V1,cP);
 211
 212   return( CamMinMaxBoxOverlap(Cam,V1,cP,m,M) );
 213 };
 214
 215 // ----------------------------------------------------------------------
 216 // Returns 1 if and only if the specified box is completely culled away.
 217 bool VFC(const Camera *Cam, const float m[3], const float M[3])
 218 {
 219   return (CamMinMaxBoxOverlap(Cam, m, M) == COMPLETEOUT);
 220 }
 221
 222 //----------------------------------------------------------------------------
 223 // Given the 8 corner vertices and the 6 side planes for two cameras,
 224 // returns the type of overlap (complete out(1), partial (0), complete in (-1))
 225 // with respect to the first camera.
 226 //----------------------------------------------------------------------------
 227 int CamCamOverlap(
 228   const Vec3f V1[8], const float P1[][4],
 229   const Vec3f V2[8], const float P2[][4])
 230 {
 231   int i, NumVertsOutAllPlanes, NumVertsOutOnePlane;
 232   float InT, OutT;
 233
 234   // TEST ALL CAM1 VERTICES AGAINST PLANES OF CAM2
 235   NumVertsOutAllPlanes=0;
 236   for (i=0; i<6; i++)
 237   {
 238     NumVertsOutOnePlane=0;
 239     for (int j=0; j<8; j++)
 240       NumVertsOutOnePlane += PlanePtOutTest(P2[i],&(V1[i].x));
 241     if (NumVertsOutOnePlane==8) return(1);  // TRIVIAL REJECT, COMPLETELY OUT!
 242     NumVertsOutAllPlanes+=NumVertsOutOnePlane;
 243   }
 244   if (NumVertsOutAllPlanes==0) return(0); // TRIVIAL ACCEPT, PARTIAL!
 245
 246   // TEST ALL CAM2 VERTICES AGAINST PLANES OF CAM1
 247   NumVertsOutAllPlanes=0;
 248   for (i=0; i<6; i++)
 249   {
 250     NumVertsOutOnePlane=0;
 251     for (int j=0; j<8; j++)
 252       NumVertsOutOnePlane += PlanePtOutTest(P1[i],&(V2[i].x));
 253     if (NumVertsOutOnePlane==8) return(1);  // TRIVIAL REJECT, COMPLETELY OUT!
 254     NumVertsOutAllPlanes+=NumVertsOutOnePlane;
 255   }
 256   if (NumVertsOutAllPlanes==0) return(-1); // TRIVIAL ACCEPT, COMPLETELY IN!
 257
 258   // TEST ALL CAM1 EDGES AGAINST SET OF CAM2 PLANES
 259   if ( PlanesEdgeIsect(P2,6,&(V1[0].x),&(V1[4].x),&InT,&OutT) ) return(0);
 260   if ( PlanesEdgeIsect(P2,6,&(V1[1].x),&(V1[5].x),&InT,&OutT) ) return(0);
 261   if ( PlanesEdgeIsect(P2,6,&(V1[2].x),&(V1[6].x),&InT,&OutT) ) return(0);
 262   if ( PlanesEdgeIsect(P2,6,&(V1[3].x),&(V1[7].x),&InT,&OutT) ) return(0);
 263   if ( PlanesEdgeIsect(P2,6,&(V1[0].x),&(V1[1].x),&InT,&OutT) ) return(0);
 264   if ( PlanesEdgeIsect(P2,6,&(V1[1].x),&(V1[2].x),&InT,&OutT) ) return(0);
 265   if ( PlanesEdgeIsect(P2,6,&(V1[2].x),&(V1[3].x),&InT,&OutT) ) return(0);
 266   if ( PlanesEdgeIsect(P2,6,&(V1[3].x),&(V1[0].x),&InT,&OutT) ) return(0);
 267   if ( PlanesEdgeIsect(P2,6,&(V1[4].x),&(V1[5].x),&InT,&OutT) ) return(0);
 268   if ( PlanesEdgeIsect(P2,6,&(V1[5].x),&(V1[6].x),&InT,&OutT) ) return(0);
 269   if ( PlanesEdgeIsect(P2,6,&(V1[6].x),&(V1[7].x),&InT,&OutT) ) return(0);
 270   if ( PlanesEdgeIsect(P2,6,&(V1[7].x),&(V1[0].x),&InT,&OutT) ) return(0);
 271
 272   // TEST ALL CAM2 EDGES AGAINST SET OF CAM1 PLANES
 273   if ( PlanesEdgeIsect(P1,6,&(V2[0].x),&(V2[4].x),&InT,&OutT) ) return(0);
 274   if ( PlanesEdgeIsect(P1,6,&(V2[1].x),&(V2[5].x),&InT,&OutT) ) return(0);
 275   if ( PlanesEdgeIsect(P1,6,&(V2[2].x),&(V2[6].x),&InT,&OutT) ) return(0);
 276   if ( PlanesEdgeIsect(P1,6,&(V2[3].x),&(V2[7].x),&InT,&OutT) ) return(0);
 277   if ( PlanesEdgeIsect(P1,6,&(V2[0].x),&(V2[1].x),&InT,&OutT) ) return(0);
 278   if ( PlanesEdgeIsect(P1,6,&(V2[1].x),&(V2[2].x),&InT,&OutT) ) return(0);
 279   if ( PlanesEdgeIsect(P1,6,&(V2[2].x),&(V2[3].x),&InT,&OutT) ) return(0);
 280   if ( PlanesEdgeIsect(P1,6,&(V2[3].x),&(V2[0].x),&InT,&OutT) ) return(0);
 281   if ( PlanesEdgeIsect(P1,6,&(V2[4].x),&(V2[5].x),&InT,&OutT) ) return(0);
 282   if ( PlanesEdgeIsect(P1,6,&(V2[5].x),&(V2[6].x),&InT,&OutT) ) return(0);
 283   if ( PlanesEdgeIsect(P1,6,&(V2[6].x),&(V2[7].x),&InT,&OutT) ) return(0);
 284   if ( PlanesEdgeIsect(P1,6,&(V2[7].x),&(V2[0].x),&InT,&OutT) ) return(0);
 285
 286   return(1);
 287 }
 288
 289 int CamCamOverlap(const Camera *Cam1, const Camera *Cam2)
 290 {
 291   // GET CAMERA VERTICES
 292   Vec3f V1[8], V2[8];
 293   Cam1->CalcVerts(V1);
 294   Cam2->CalcVerts(V2);
 295
 296   // CALCULATE SIX CAMERA PLANES FROM CAMERA VERTICES
 297   float P1[6][4], P2[6][4];
 298   CalcCamPlanes(V1,P1);
 299   CalcCamPlanes(V2,P2);
 300
 301   return( CamCamOverlap(V1,P1,V2,P2) );
 302 }
 303
 304 //--------------------------------------------------------------------------
 305 // Given a camera and a plane (defined by four coefficient of implicit
 306 // form: Ax+By+Cz+D=0), reflect the camera about the plane and invert
 307 // back into right-handed system (reflection inverts the space, so we
 308 // have to invert the X-axis and flip the window boundaries).
 309 //--------------------------------------------------------------------------
 310 void CamReflectAboutPlane(Camera *Cam, const float Plane[4])
 311 {
 312   // CREATE PLANAR REFLECTION MATRIX
 313   float M[16];
 314   PlanarReflection16fv(M,Plane);
 315
 316   // XFORM CAMERA
 317   Cam->Xform(M);
 318
 319   // RESULTING CAM IS LEFT-HANDED, FLIP THE X-AXIS, FLIP X WINDOW BOUNDS
 320   Cam->X = -(Cam->X);
 321   float t = -(Cam->wL);
 322   Cam->wL = -(Cam->wR);
 323   Cam->wR = t;
 324 }