1 //------------------------------------------------------------------------------
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
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.
18 //============================================================================
19 // camutils.cpp : a set of camera utility functions
20 //============================================================================
22 #include "camutils.hpp"
25 #include <minmaxbox.hpp>
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)
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
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;
49 // TRIVIAL ACCEPTANCE: IF ANY VERTEX IS COMPLETELY INSIDE ALL PLANES (=0)
50 if (BitMaskA==0 || BitMaskB==0 || BitMaskC==0) return(1);
52 // TRIVIAL REJECTION: IF ALL VERTICES ARE OUTSIDE OF ANY PLANE
56 if ((BitMaskA & BitMaskB & BitMaskC & PlaneBitMask) > 0) return(0);
60 // TEST EDGES OF TRIANGLE AGAINST PLANES OF CAMERA
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);
66 // TEST EDGES OF CAMERA AGAINST TRIANGLE
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);
84 int CamTriOverlap(const Camera *Cam,
85 const Vec3f& A, const Vec3f& B, const Vec3f& C)
87 // GET CAMERA VERTICES
91 // CALCULATE SIX CAMERA PLANES FROM CAMERA VERTICES
95 return( CamTriOverlap(V,P,A,B,C) );
98 //----------------------------------------------------------------------------
99 // Temporary implementation of CamQuadOverlap (uses CamTriOverlap).
100 //----------------------------------------------------------------------------
103 const Vec3f& A, const Vec3f& B, const Vec3f& C, const Vec3f& D)
105 if ( CamTriOverlap(Cam,A,B,C) ) return(1);
106 if ( CamTriOverlap(Cam,C,D,A) ) return(1);
112 const float A[3], const float B[3], const float C[3], const float D[3])
114 Vec3f a(A),b(B),c(C),d(D);
115 return( CamQuadOverlap(Cam,a,b,c,d) );
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])
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
133 void CalcCamPlanes(const Camera *Cam, float P[][4])
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
146 //--------------------------------------------------------------------------
147 int CamMinMaxBoxOverlap(
148 const Camera *Cam, const Vec3f V1[8], const float cP[][4],
149 const Vec3f& m, const Vec3f& M)
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++)
156 R=PlaneMinMaxBoxOverlap(cP[i],&(m.x),&(M.x));
157 if(R==COMPLETEOUT) return(COMPLETEOUT);
158 else if(R==PARTIAL) CompletelyIn=0;
161 if (CompletelyIn) return(COMPLETEIN); // CHECK IF STILL COMPLETELY "IN"
163 // TEST IF VIEW-FRUSTUM EDGES PROTRUDE THROUGH AABB
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);
178 // COMPUTE VERTICES OF AABB
180 GetMinMaxBoxVerts(&(m.x),&(M.x),bV);
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);
196 // VF MUST BE COMPLETELY ENCLOSED SINCE PT IS NOT "OUT "OF ANY AABB PLANE.
197 //return(COMPLETEOUT);
201 int CamMinMaxBoxOverlap(
202 const Camera *Cam, const float m[3], const float M[3])
204 // GET CAMERA VERTICES
208 // CALCULATE SIX CAMERA PLANES FROM CAMERA VERTICES
210 CalcCamPlanes(V1,cP);
212 return( CamMinMaxBoxOverlap(Cam,V1,cP,m,M) );
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])
219 return (CamMinMaxBoxOverlap(Cam, m, M) == COMPLETEOUT);
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 //----------------------------------------------------------------------------
228 const Vec3f V1[8], const float P1[][4],
229 const Vec3f V2[8], const float P2[][4])
231 int i, NumVertsOutAllPlanes, NumVertsOutOnePlane;
234 // TEST ALL CAM1 VERTICES AGAINST PLANES OF CAM2
235 NumVertsOutAllPlanes=0;
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;
244 if (NumVertsOutAllPlanes==0) return(0); // TRIVIAL ACCEPT, PARTIAL!
246 // TEST ALL CAM2 VERTICES AGAINST PLANES OF CAM1
247 NumVertsOutAllPlanes=0;
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;
256 if (NumVertsOutAllPlanes==0) return(-1); // TRIVIAL ACCEPT, COMPLETELY IN!
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);
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);
289 int CamCamOverlap(const Camera *Cam1, const Camera *Cam2)
291 // GET CAMERA VERTICES
296 // CALCULATE SIX CAMERA PLANES FROM CAMERA VERTICES
297 float P1[6][4], P2[6][4];
298 CalcCamPlanes(V1,P1);
299 CalcCamPlanes(V2,P2);
301 return( CamCamOverlap(V1,P1,V2,P2) );
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])
312 // CREATE PLANAR REFLECTION MATRIX
314 PlanarReflection16fv(M,Plane);
319 // RESULTING CAM IS LEFT-HANDED, FLIP THE X-AXIS, FLIP X WINDOW BOUNDS
321 float t = -(Cam->wL);
322 Cam->wL = -(Cam->wR);