doom3-gpl
Doom 3 GPL source release
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Frustum.cpp
Go to the documentation of this file.
1 /*
2 ===========================================================================
3 
4 Doom 3 GPL Source Code
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
6 
7 This file is part of the Doom 3 GPL Source Code (?Doom 3 Source Code?).
8 
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13 
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18 
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
21 
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
23 
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25 
26 ===========================================================================
27 */
28 
29 #include "../precompiled.h"
30 #pragma hdrstop
31 
32 //#define FRUSTUM_DEBUG
33 
34 /*
35  bit 0 = min x
36  bit 1 = max x
37  bit 2 = min y
38  bit 3 = max y
39  bit 4 = min z
40  bit 5 = max z
41 */
42 static int boxVertPlanes[8] = {
43  ( (1<<0) | (1<<2) | (1<<4) ),
44  ( (1<<1) | (1<<2) | (1<<4) ),
45  ( (1<<1) | (1<<3) | (1<<4) ),
46  ( (1<<0) | (1<<3) | (1<<4) ),
47  ( (1<<0) | (1<<2) | (1<<5) ),
48  ( (1<<1) | (1<<2) | (1<<5) ),
49  ( (1<<1) | (1<<3) | (1<<5) ),
50  ( (1<<0) | (1<<3) | (1<<5) ),
51 };
52 
53 /*
54 ============
55 BoxToPoints
56 ============
57 */
58 void BoxToPoints( const idVec3 &center, const idVec3 &extents, const idMat3 &axis, idVec3 points[8] ) {
59  idMat3 ax;
60  idVec3 temp[4];
61 
62  ax[0] = extents[0] * axis[0];
63  ax[1] = extents[1] * axis[1];
64  ax[2] = extents[2] * axis[2];
65  temp[0] = center - ax[0];
66  temp[1] = center + ax[0];
67  temp[2] = ax[1] - ax[2];
68  temp[3] = ax[1] + ax[2];
69  points[0] = temp[0] - temp[3];
70  points[1] = temp[1] - temp[3];
71  points[2] = temp[1] + temp[2];
72  points[3] = temp[0] + temp[2];
73  points[4] = temp[0] - temp[2];
74  points[5] = temp[1] - temp[2];
75  points[6] = temp[1] + temp[3];
76  points[7] = temp[0] + temp[3];
77 }
78 
79 /*
80 ================
81 idFrustum::PlaneDistance
82 ================
83 */
84 float idFrustum::PlaneDistance( const idPlane &plane ) const {
85  float min, max;
86 
87  AxisProjection( plane.Normal(), min, max );
88  if ( min + plane[3] > 0.0f ) {
89  return min + plane[3];
90  }
91  if ( max + plane[3] < 0.0f ) {
92  return max + plane[3];
93  }
94  return 0.0f;
95 }
96 
97 /*
98 ================
99 idFrustum::PlaneSide
100 ================
101 */
102 int idFrustum::PlaneSide( const idPlane &plane, const float epsilon ) const {
103  float min, max;
104 
105  AxisProjection( plane.Normal(), min, max );
106  if ( min + plane[3] > epsilon ) {
107  return PLANESIDE_FRONT;
108  }
109  if ( max + plane[3] < epsilon ) {
110  return PLANESIDE_BACK;
111  }
112  return PLANESIDE_CROSS;
113 }
114 
115 /*
116 ============
117 idFrustum::CullPoint
118 ============
119 */
120 bool idFrustum::CullPoint( const idVec3 &point ) const {
121  idVec3 p;
122  float scale;
123 
124  // transform point to frustum space
125  p = ( point - origin ) * axis.Transpose();
126  // test whether or not the point is within the frustum
127  if ( p.x < dNear || p.x > dFar ) {
128  return true;
129  }
130  scale = p.x * invFar;
131  if ( idMath::Fabs( p.y ) > dLeft * scale ) {
132  return true;
133  }
134  if ( idMath::Fabs( p.z ) > dUp * scale ) {
135  return true;
136  }
137  return false;
138 }
139 
140 /*
141 ============
142 idFrustum::CullLocalBox
143 
144  Tests if any of the planes of the frustum can be used as a separating plane.
145 
146  3 muls best case
147  25 muls worst case
148 ============
149 */
150 bool idFrustum::CullLocalBox( const idVec3 &localOrigin, const idVec3 &extents, const idMat3 &localAxis ) const {
151  float d1, d2;
152  idVec3 testOrigin;
153  idMat3 testAxis;
154 
155  // near plane
156  d1 = dNear - localOrigin.x;
157  d2 = idMath::Fabs( extents[0] * localAxis[0][0] ) +
158  idMath::Fabs( extents[1] * localAxis[1][0] ) +
159  idMath::Fabs( extents[2] * localAxis[2][0] );
160  if ( d1 - d2 > 0.0f ) {
161  return true;
162  }
163 
164  // far plane
165  d1 = localOrigin.x - dFar;
166  if ( d1 - d2 > 0.0f ) {
167  return true;
168  }
169 
170  testOrigin = localOrigin;
171  testAxis = localAxis;
172 
173  if ( testOrigin.y < 0.0f ) {
174  testOrigin.y = -testOrigin.y;
175  testAxis[0][1] = -testAxis[0][1];
176  testAxis[1][1] = -testAxis[1][1];
177  testAxis[2][1] = -testAxis[2][1];
178  }
179 
180  // test left/right planes
181  d1 = dFar * testOrigin.y - dLeft * testOrigin.x;
182  d2 = idMath::Fabs( extents[0] * ( dFar * testAxis[0][1] - dLeft * testAxis[0][0] ) ) +
183  idMath::Fabs( extents[1] * ( dFar * testAxis[1][1] - dLeft * testAxis[1][0] ) ) +
184  idMath::Fabs( extents[2] * ( dFar * testAxis[2][1] - dLeft * testAxis[2][0] ) );
185  if ( d1 - d2 > 0.0f ) {
186  return true;
187  }
188 
189  if ( testOrigin.z < 0.0f ) {
190  testOrigin.z = -testOrigin.z;
191  testAxis[0][2] = -testAxis[0][2];
192  testAxis[1][2] = -testAxis[1][2];
193  testAxis[2][2] = -testAxis[2][2];
194  }
195 
196  // test up/down planes
197  d1 = dFar * testOrigin.z - dUp * testOrigin.x;
198  d2 = idMath::Fabs( extents[0] * ( dFar * testAxis[0][2] - dUp * testAxis[0][0] ) ) +
199  idMath::Fabs( extents[1] * ( dFar * testAxis[1][2] - dUp * testAxis[1][0] ) ) +
200  idMath::Fabs( extents[2] * ( dFar * testAxis[2][2] - dUp * testAxis[2][0] ) );
201  if ( d1 - d2 > 0.0f ) {
202  return true;
203  }
204 
205  return false;
206 }
207 
208 /*
209 ============
210 idFrustum::CullBounds
211 
212  Tests if any of the planes of the frustum can be used as a separating plane.
213 
214  24 muls best case
215  37 muls worst case
216 ============
217 */
218 bool idFrustum::CullBounds( const idBounds &bounds ) const {
219  idVec3 localOrigin, center, extents;
220  idMat3 localAxis;
221 
222  center = ( bounds[0] + bounds[1] ) * 0.5f;
223  extents = bounds[1] - center;
224 
225  // transform the bounds into the space of this frustum
226  localOrigin = ( center - origin ) * axis.Transpose();
227  localAxis = axis.Transpose();
228 
229  return CullLocalBox( localOrigin, extents, localAxis );
230 }
231 
232 /*
233 ============
234 idFrustum::CullBounds
235 
236  Tests if any of the planes of the frustum can be used as a separating plane.
237 
238  39 muls best case
239  61 muls worst case
240 ============
241 */
242 bool idFrustum::CullBox( const idBox &box ) const {
243  idVec3 localOrigin;
244  idMat3 localAxis;
245 
246  // transform the box into the space of this frustum
247  localOrigin = ( box.GetCenter() - origin ) * axis.Transpose();
248  localAxis = box.GetAxis() * axis.Transpose();
249 
250  return CullLocalBox( localOrigin, box.GetExtents(), localAxis );
251 }
252 
253 /*
254 ============
255 idFrustum::CullSphere
256 
257  Tests if any of the planes of the frustum can be used as a separating plane.
258 
259  9 muls best case
260  21 muls worst case
261 ============
262 */
263 bool idFrustum::CullSphere( const idSphere &sphere ) const {
264  float d, r, rs, sFar;
265  idVec3 center;
266 
267  center = ( sphere.GetOrigin() - origin ) * axis.Transpose();
268  r = sphere.GetRadius();
269 
270  // test near plane
271  if ( dNear - center.x > r ) {
272  return true;
273  }
274 
275  // test far plane
276  if ( center.x - dFar > r ) {
277  return true;
278  }
279 
280  rs = r * r;
281  sFar = dFar * dFar;
282 
283  // test left/right planes
284  d = dFar * idMath::Fabs( center.y ) - dLeft * center.x;
285  if ( ( d * d ) > rs * ( sFar + dLeft * dLeft ) ) {
286  return true;
287  }
288 
289  // test up/down planes
290  d = dFar * idMath::Fabs( center.z ) - dUp * center.x;
291  if ( ( d * d ) > rs * ( sFar + dUp * dUp ) ) {
292  return true;
293  }
294 
295  return false;
296 }
297 
298 /*
299 ============
300 idFrustum::CullLocalFrustum
301 
302  Tests if any of the planes of this frustum can be used as a separating plane.
303 
304  0 muls best case
305  30 muls worst case
306 ============
307 */
308 bool idFrustum::CullLocalFrustum( const idFrustum &localFrustum, const idVec3 indexPoints[8], const idVec3 cornerVecs[4] ) const {
309  int index;
310  float dx, dy, dz, leftScale, upScale;
311 
312  // test near plane
313  dy = -localFrustum.axis[1].x;
314  dz = -localFrustum.axis[2].x;
315  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
316  dx = -cornerVecs[index].x;
317  index |= ( FLOATSIGNBITSET( dx ) << 2 );
318 
319  if ( indexPoints[index].x < dNear ) {
320  return true;
321  }
322 
323  // test far plane
324  dy = localFrustum.axis[1].x;
325  dz = localFrustum.axis[2].x;
326  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
327  dx = cornerVecs[index].x;
328  index |= ( FLOATSIGNBITSET( dx ) << 2 );
329 
330  if ( indexPoints[index].x > dFar ) {
331  return true;
332  }
333 
334  leftScale = dLeft * invFar;
335 
336  // test left plane
337  dy = dFar * localFrustum.axis[1].y - dLeft * localFrustum.axis[1].x;
338  dz = dFar * localFrustum.axis[2].y - dLeft * localFrustum.axis[2].x;
339  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
340  dx = dFar * cornerVecs[index].y - dLeft * cornerVecs[index].x;
341  index |= ( FLOATSIGNBITSET( dx ) << 2 );
342 
343  if ( indexPoints[index].y > indexPoints[index].x * leftScale ) {
344  return true;
345  }
346 
347  // test right plane
348  dy = -dFar * localFrustum.axis[1].y - dLeft * localFrustum.axis[1].x;
349  dz = -dFar * localFrustum.axis[2].y - dLeft * localFrustum.axis[2].x;
350  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
351  dx = -dFar * cornerVecs[index].y - dLeft * cornerVecs[index].x;
352  index |= ( FLOATSIGNBITSET( dx ) << 2 );
353 
354  if ( indexPoints[index].y < -indexPoints[index].x * leftScale ) {
355  return true;
356  }
357 
358  upScale = dUp * invFar;
359 
360  // test up plane
361  dy = dFar * localFrustum.axis[1].z - dUp * localFrustum.axis[1].x;
362  dz = dFar * localFrustum.axis[2].z - dUp * localFrustum.axis[2].x;
363  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
364  dx = dFar * cornerVecs[index].z - dUp * cornerVecs[index].x;
365  index |= ( FLOATSIGNBITSET( dx ) << 2 );
366 
367  if ( indexPoints[index].z > indexPoints[index].x * upScale ) {
368  return true;
369  }
370 
371  // test down plane
372  dy = -dFar * localFrustum.axis[1].z - dUp * localFrustum.axis[1].x;
373  dz = -dFar * localFrustum.axis[2].z - dUp * localFrustum.axis[2].x;
374  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
375  dx = -dFar * cornerVecs[index].z - dUp * cornerVecs[index].x;
376  index |= ( FLOATSIGNBITSET( dx ) << 2 );
377 
378  if ( indexPoints[index].z < -indexPoints[index].x * upScale ) {
379  return true;
380  }
381 
382  return false;
383 }
384 
385 /*
386 ============
387 idFrustum::CullFrustum
388 
389  Tests if any of the planes of this frustum can be used as a separating plane.
390 
391  58 muls best case
392  88 muls worst case
393 ============
394 */
395 bool idFrustum::CullFrustum( const idFrustum &frustum ) const {
396  idFrustum localFrustum;
397  idVec3 indexPoints[8], cornerVecs[4];
398 
399  // transform the given frustum into the space of this frustum
400  localFrustum = frustum;
401  localFrustum.origin = ( frustum.origin - origin ) * axis.Transpose();
402  localFrustum.axis = frustum.axis * axis.Transpose();
403 
404  localFrustum.ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
405 
406  return CullLocalFrustum( localFrustum, indexPoints, cornerVecs );
407 }
408 
409 /*
410 ============
411 idFrustum::CullLocalWinding
412 ============
413 */
414 bool idFrustum::CullLocalWinding( const idVec3 *points, const int numPoints, int *pointCull ) const {
415  int i, pCull, culled;
416  float leftScale, upScale;
417 
418  leftScale = dLeft * invFar;
419  upScale = dUp * invFar;
420 
421  culled = -1;
422  for ( i = 0; i < numPoints; i++ ) {
423  const idVec3 &p = points[i];
424  pCull = 0;
425  if ( p.x < dNear ) {
426  pCull = 1;
427  }
428  else if ( p.x > dFar ) {
429  pCull = 2;
430  }
431  if ( idMath::Fabs( p.y ) > p.x * leftScale ) {
432  pCull |= 4 << FLOATSIGNBITSET( p.y );
433  }
434  if ( idMath::Fabs( p.z ) > p.x * upScale ) {
435  pCull |= 16 << FLOATSIGNBITSET( p.z );
436  }
437  culled &= pCull;
438  pointCull[i] = pCull;
439  }
440 
441  return ( culled != 0 );
442 }
443 
444 /*
445 ============
446 idFrustum::CullWinding
447 ============
448 */
449 bool idFrustum::CullWinding( const idWinding &winding ) const {
450  int i, *pointCull;
451  idVec3 *localPoints;
452  idMat3 transpose;
453 
454  localPoints = (idVec3 *) _alloca16( winding.GetNumPoints() * sizeof( idVec3 ) );
455  pointCull = (int *) _alloca16( winding.GetNumPoints() * sizeof( int ) );
456 
457  transpose = axis.Transpose();
458  for ( i = 0; i < winding.GetNumPoints(); i++ ) {
459  localPoints[i] = ( winding[i].ToVec3() - origin ) * transpose;
460  }
461 
462  return CullLocalWinding( localPoints, winding.GetNumPoints(), pointCull );
463 }
464 
465 /*
466 ============
467 idFrustum::BoundsCullLocalFrustum
468 
469  Tests if any of the bounding box planes can be used as a separating plane.
470 ============
471 */
472 bool idFrustum::BoundsCullLocalFrustum( const idBounds &bounds, const idFrustum &localFrustum, const idVec3 indexPoints[8], const idVec3 cornerVecs[4] ) const {
473  int index;
474  float dx, dy, dz;
475 
476  dy = -localFrustum.axis[1].x;
477  dz = -localFrustum.axis[2].x;
478  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
479  dx = -cornerVecs[index].x;
480  index |= ( FLOATSIGNBITSET( dx ) << 2 );
481 
482  if ( indexPoints[index].x < bounds[0].x ) {
483  return true;
484  }
485 
486  dy = localFrustum.axis[1].x;
487  dz = localFrustum.axis[2].x;
488  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
489  dx = cornerVecs[index].x;
490  index |= ( FLOATSIGNBITSET( dx ) << 2 );
491 
492  if ( indexPoints[index].x > bounds[1].x ) {
493  return true;
494  }
495 
496  dy = -localFrustum.axis[1].y;
497  dz = -localFrustum.axis[2].y;
498  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
499  dx = -cornerVecs[index].y;
500  index |= ( FLOATSIGNBITSET( dx ) << 2 );
501 
502  if ( indexPoints[index].y < bounds[0].y ) {
503  return true;
504  }
505 
506  dy = localFrustum.axis[1].y;
507  dz = localFrustum.axis[2].y;
508  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
509  dx = cornerVecs[index].y;
510  index |= ( FLOATSIGNBITSET( dx ) << 2 );
511 
512  if ( indexPoints[index].y > bounds[1].y ) {
513  return true;
514  }
515 
516  dy = -localFrustum.axis[1].z;
517  dz = -localFrustum.axis[2].z;
518  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
519  dx = -cornerVecs[index].z;
520  index |= ( FLOATSIGNBITSET( dx ) << 2 );
521 
522  if ( indexPoints[index].z < bounds[0].z ) {
523  return true;
524  }
525 
526  dy = localFrustum.axis[1].z;
527  dz = localFrustum.axis[2].z;
528  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
529  dx = cornerVecs[index].z;
530  index |= ( FLOATSIGNBITSET( dx ) << 2 );
531 
532  if ( indexPoints[index].z > bounds[1].z ) {
533  return true;
534  }
535 
536  return false;
537 }
538 
539 /*
540 ============
541 idFrustum::LocalLineIntersection
542 
543  7 divs
544  30 muls
545 ============
546 */
547 bool idFrustum::LocalLineIntersection( const idVec3 &start, const idVec3 &end ) const {
548  idVec3 dir;
549  float d1, d2, fstart, fend, lstart, lend, f, x;
550  float leftScale, upScale;
551  int startInside = 1;
552 
553  leftScale = dLeft * invFar;
554  upScale = dUp * invFar;
555  dir = end - start;
556 
557  // test near plane
558  if ( dNear > 0.0f ) {
559  d1 = dNear - start.x;
560  startInside &= FLOATSIGNBITSET( d1 );
561  if ( FLOATNOTZERO( d1 ) ) {
562  d2 = dNear - end.x;
563  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
564  f = d1 / ( d1 - d2 );
565  if ( idMath::Fabs( start.y + f * dir.y ) <= dNear * leftScale ) {
566  if ( idMath::Fabs( start.z + f * dir.z ) <= dNear * upScale ) {
567  return true;
568  }
569  }
570  }
571  }
572  }
573 
574  // test far plane
575  d1 = start.x - dFar;
576  startInside &= FLOATSIGNBITSET( d1 );
577  if ( FLOATNOTZERO( d1 ) ) {
578  d2 = end.x - dFar;
579  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
580  f = d1 / ( d1 - d2 );
581  if ( idMath::Fabs( start.y + f * dir.y ) <= dFar * leftScale ) {
582  if ( idMath::Fabs( start.z + f * dir.z ) <= dFar * upScale ) {
583  return true;
584  }
585  }
586  }
587  }
588 
589  fstart = dFar * start.y;
590  fend = dFar * end.y;
591  lstart = dLeft * start.x;
592  lend = dLeft * end.x;
593 
594  // test left plane
595  d1 = fstart - lstart;
596  startInside &= FLOATSIGNBITSET( d1 );
597  if ( FLOATNOTZERO( d1 ) ) {
598  d2 = fend - lend;
599  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
600  f = d1 / ( d1 - d2 );
601  x = start.x + f * dir.x;
602  if ( x >= dNear && x <= dFar ) {
603  if ( idMath::Fabs( start.z + f * dir.z ) <= x * upScale ) {
604  return true;
605  }
606  }
607  }
608  }
609 
610  // test right plane
611  d1 = -fstart - lstart;
612  startInside &= FLOATSIGNBITSET( d1 );
613  if ( FLOATNOTZERO( d1 ) ) {
614  d2 = -fend - lend;
615  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
616  f = d1 / ( d1 - d2 );
617  x = start.x + f * dir.x;
618  if ( x >= dNear && x <= dFar ) {
619  if ( idMath::Fabs( start.z + f * dir.z ) <= x * upScale ) {
620  return true;
621  }
622  }
623  }
624  }
625 
626  fstart = dFar * start.z;
627  fend = dFar * end.z;
628  lstart = dUp * start.x;
629  lend = dUp * end.x;
630 
631  // test up plane
632  d1 = fstart - lstart;
633  startInside &= FLOATSIGNBITSET( d1 );
634  if ( FLOATNOTZERO( d1 ) ) {
635  d2 = fend - lend;
636  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
637  f = d1 / ( d1 - d2 );
638  x = start.x + f * dir.x;
639  if ( x >= dNear && x <= dFar ) {
640  if ( idMath::Fabs( start.y + f * dir.y ) <= x * leftScale ) {
641  return true;
642  }
643  }
644  }
645  }
646 
647  // test down plane
648  d1 = -fstart - lstart;
649  startInside &= FLOATSIGNBITSET( d1 );
650  if ( FLOATNOTZERO( d1 ) ) {
651  d2 = -fend - lend;
652  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
653  f = d1 / ( d1 - d2 );
654  x = start.x + f * dir.x;
655  if ( x >= dNear && x <= dFar ) {
656  if ( idMath::Fabs( start.y + f * dir.y ) <= x * leftScale ) {
657  return true;
658  }
659  }
660  }
661  }
662 
663  return ( startInside != 0 );
664 }
665 
666 /*
667 ============
668 idFrustum::LocalRayIntersection
669 
670  Returns true if the ray starts inside the frustum.
671  If there was an intersection scale1 <= scale2
672 ============
673 */
674 bool idFrustum::LocalRayIntersection( const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2 ) const {
675  idVec3 end;
676  float d1, d2, fstart, fend, lstart, lend, f, x;
677  float leftScale, upScale;
678  int startInside = 1;
679 
680  leftScale = dLeft * invFar;
681  upScale = dUp * invFar;
682  end = start + dir;
683 
684  scale1 = idMath::INFINITY;
685  scale2 = -idMath::INFINITY;
686 
687  // test near plane
688  if ( dNear > 0.0f ) {
689  d1 = dNear - start.x;
690  startInside &= FLOATSIGNBITSET( d1 );
691  d2 = dNear - end.x;
692  if ( d1 != d2 ) {
693  f = d1 / ( d1 - d2 );
694  if ( idMath::Fabs( start.y + f * dir.y ) <= dNear * leftScale ) {
695  if ( idMath::Fabs( start.z + f * dir.z ) <= dNear * upScale ) {
696  if ( f < scale1 ) scale1 = f;
697  if ( f > scale2 ) scale2 = f;
698  }
699  }
700  }
701  }
702 
703  // test far plane
704  d1 = start.x - dFar;
705  startInside &= FLOATSIGNBITSET( d1 );
706  d2 = end.x - dFar;
707  if ( d1 != d2 ) {
708  f = d1 / ( d1 - d2 );
709  if ( idMath::Fabs( start.y + f * dir.y ) <= dFar * leftScale ) {
710  if ( idMath::Fabs( start.z + f * dir.z ) <= dFar * upScale ) {
711  if ( f < scale1 ) scale1 = f;
712  if ( f > scale2 ) scale2 = f;
713  }
714  }
715  }
716 
717  fstart = dFar * start.y;
718  fend = dFar * end.y;
719  lstart = dLeft * start.x;
720  lend = dLeft * end.x;
721 
722  // test left plane
723  d1 = fstart - lstart;
724  startInside &= FLOATSIGNBITSET( d1 );
725  d2 = fend - lend;
726  if ( d1 != d2 ) {
727  f = d1 / ( d1 - d2 );
728  x = start.x + f * dir.x;
729  if ( x >= dNear && x <= dFar ) {
730  if ( idMath::Fabs( start.z + f * dir.z ) <= x * upScale ) {
731  if ( f < scale1 ) scale1 = f;
732  if ( f > scale2 ) scale2 = f;
733  }
734  }
735  }
736 
737  // test right plane
738  d1 = -fstart - lstart;
739  startInside &= FLOATSIGNBITSET( d1 );
740  d2 = -fend - lend;
741  if ( d1 != d2 ) {
742  f = d1 / ( d1 - d2 );
743  x = start.x + f * dir.x;
744  if ( x >= dNear && x <= dFar ) {
745  if ( idMath::Fabs( start.z + f * dir.z ) <= x * upScale ) {
746  if ( f < scale1 ) scale1 = f;
747  if ( f > scale2 ) scale2 = f;
748  }
749  }
750  }
751 
752  fstart = dFar * start.z;
753  fend = dFar * end.z;
754  lstart = dUp * start.x;
755  lend = dUp * end.x;
756 
757  // test up plane
758  d1 = fstart - lstart;
759  startInside &= FLOATSIGNBITSET( d1 );
760  d2 = fend - lend;
761  if ( d1 != d2 ) {
762  f = d1 / ( d1 - d2 );
763  x = start.x + f * dir.x;
764  if ( x >= dNear && x <= dFar ) {
765  if ( idMath::Fabs( start.y + f * dir.y ) <= x * leftScale ) {
766  if ( f < scale1 ) scale1 = f;
767  if ( f > scale2 ) scale2 = f;
768  }
769  }
770  }
771 
772  // test down plane
773  d1 = -fstart - lstart;
774  startInside &= FLOATSIGNBITSET( d1 );
775  d2 = -fend - lend;
776  if ( d1 != d2 ) {
777  f = d1 / ( d1 - d2 );
778  x = start.x + f * dir.x;
779  if ( x >= dNear && x <= dFar ) {
780  if ( idMath::Fabs( start.y + f * dir.y ) <= x * leftScale ) {
781  if ( f < scale1 ) scale1 = f;
782  if ( f > scale2 ) scale2 = f;
783  }
784  }
785  }
786 
787  return ( startInside != 0 );
788 }
789 
790 /*
791 ============
792 idFrustum::ContainsPoint
793 ============
794 */
795 bool idFrustum::ContainsPoint( const idVec3 &point ) const {
796  return !CullPoint( point );
797 }
798 
799 /*
800 ============
801 idFrustum::LocalFrustumIntersectsFrustum
802 ============
803 */
804 bool idFrustum::LocalFrustumIntersectsFrustum( const idVec3 points[8], const bool testFirstSide ) const {
805  int i;
806 
807  // test if any edges of the other frustum intersect this frustum
808  for ( i = 0; i < 4; i++ ) {
809  if ( LocalLineIntersection( points[i], points[4+i] ) ) {
810  return true;
811  }
812  }
813  if ( testFirstSide ) {
814  for ( i = 0; i < 4; i++ ) {
815  if ( LocalLineIntersection( points[i], points[(i+1)&3] ) ) {
816  return true;
817  }
818  }
819  }
820  for ( i = 0; i < 4; i++ ) {
821  if ( LocalLineIntersection( points[4+i], points[4+((i+1)&3)] ) ) {
822  return true;
823  }
824  }
825 
826  return false;
827 }
828 
829 /*
830 ============
831 idFrustum::LocalFrustumIntersectsBounds
832 ============
833 */
834 bool idFrustum::LocalFrustumIntersectsBounds( const idVec3 points[8], const idBounds &bounds ) const {
835  int i;
836 
837  // test if any edges of the other frustum intersect this frustum
838  for ( i = 0; i < 4; i++ ) {
839  if ( bounds.LineIntersection( points[i], points[4+i] ) ) {
840  return true;
841  }
842  }
843  if ( dNear > 0.0f ) {
844  for ( i = 0; i < 4; i++ ) {
845  if ( bounds.LineIntersection( points[i], points[(i+1)&3] ) ) {
846  return true;
847  }
848  }
849  }
850  for ( i = 0; i < 4; i++ ) {
851  if ( bounds.LineIntersection( points[4+i], points[4+((i+1)&3)] ) ) {
852  return true;
853  }
854  }
855 
856  return false;
857 }
858 
859 /*
860 ============
861 idFrustum::IntersectsBounds
862 ============
863 */
864 bool idFrustum::IntersectsBounds( const idBounds &bounds ) const {
865  idVec3 localOrigin, center, extents;
866  idMat3 localAxis;
867 
868  center = ( bounds[0] + bounds[1] ) * 0.5f;
869  extents = bounds[1] - center;
870 
871  localOrigin = ( center - origin ) * axis.Transpose();
872  localAxis = axis.Transpose();
873 
874  if ( CullLocalBox( localOrigin, extents, localAxis ) ) {
875  return false;
876  }
877 
878  idVec3 indexPoints[8], cornerVecs[4];
879 
880  ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
881 
882  if ( BoundsCullLocalFrustum( bounds, *this, indexPoints, cornerVecs ) ) {
883  return false;
884  }
885 
886  idSwap( indexPoints[2], indexPoints[3] );
887  idSwap( indexPoints[6], indexPoints[7] );
888 
889  if ( LocalFrustumIntersectsBounds( indexPoints, bounds ) ) {
890  return true;
891  }
892 
893  BoxToPoints( localOrigin, extents, localAxis, indexPoints );
894 
895  if ( LocalFrustumIntersectsFrustum( indexPoints, true ) ) {
896  return true;
897  }
898 
899  return false;
900 }
901 
902 /*
903 ============
904 idFrustum::IntersectsBox
905 ============
906 */
907 bool idFrustum::IntersectsBox( const idBox &box ) const {
908  idVec3 localOrigin;
909  idMat3 localAxis;
910 
911  localOrigin = ( box.GetCenter() - origin ) * axis.Transpose();
912  localAxis = box.GetAxis() * axis.Transpose();
913 
914  if ( CullLocalBox( localOrigin, box.GetExtents(), localAxis ) ) {
915  return false;
916  }
917 
918  idVec3 indexPoints[8], cornerVecs[4];
919  idFrustum localFrustum;
920 
921  localFrustum = *this;
922  localFrustum.origin = ( origin - box.GetCenter() ) * box.GetAxis().Transpose();
923  localFrustum.axis = axis * box.GetAxis().Transpose();
924  localFrustum.ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
925 
926  if ( BoundsCullLocalFrustum( idBounds( -box.GetExtents(), box.GetExtents() ), localFrustum, indexPoints, cornerVecs ) ) {
927  return false;
928  }
929 
930  idSwap( indexPoints[2], indexPoints[3] );
931  idSwap( indexPoints[6], indexPoints[7] );
932 
933  if ( LocalFrustumIntersectsBounds( indexPoints, idBounds( -box.GetExtents(), box.GetExtents() ) ) ) {
934  return true;
935  }
936 
937  BoxToPoints( localOrigin, box.GetExtents(), localAxis, indexPoints );
938 
939  if ( LocalFrustumIntersectsFrustum( indexPoints, true ) ) {
940  return true;
941  }
942 
943  return false;
944 }
945 
946 /*
947 ============
948 idFrustum::IntersectsSphere
949 
950  FIXME: test this
951 ============
952 */
953 #define VORONOI_INDEX( x, y, z ) ( x + y * 3 + z * 9 )
954 
955 bool idFrustum::IntersectsSphere( const idSphere &sphere ) const {
956  int index, x, y, z;
957  float scale, r, d;
958  idVec3 p, dir, points[8];
959 
960  if ( CullSphere( sphere ) ) {
961  return false;
962  }
963 
964  x = y = z = 0;
965  dir.Zero();
966 
967  p = ( sphere.GetOrigin() - origin ) * axis.Transpose();
968 
969  if ( p.x <= dNear ) {
970  scale = dNear * invFar;
971  dir.y = idMath::Fabs( p.y ) - dLeft * scale;
972  dir.z = idMath::Fabs( p.z ) - dUp * scale;
973  }
974  else if ( p.x >= dFar ) {
975  dir.y = idMath::Fabs( p.y ) - dLeft;
976  dir.z = idMath::Fabs( p.z ) - dUp;
977  }
978  else {
979  scale = p.x * invFar;
980  dir.y = idMath::Fabs( p.y ) - dLeft * scale;
981  dir.z = idMath::Fabs( p.z ) - dUp * scale;
982  }
983  if ( dir.y > 0.0f ) {
984  y = ( 1 + FLOATSIGNBITNOTSET( p.y ) );
985  }
986  if ( dir.z > 0.0f ) {
987  z = ( 1 + FLOATSIGNBITNOTSET( p.z ) );
988  }
989  if ( p.x < dNear ) {
990  scale = dLeft * dNear * invFar;
991  if ( p.x < dNear + ( scale - p.y ) * scale * invFar ) {
992  scale = dUp * dNear * invFar;
993  if ( p.x < dNear + ( scale - p.z ) * scale * invFar ) {
994  x = 1;
995  }
996  }
997  }
998  else {
999  if ( p.x > dFar ) {
1000  x = 2;
1001  }
1002  else if ( p.x > dFar + ( dLeft - p.y ) * dLeft * invFar ) {
1003  x = 2;
1004  }
1005  else if ( p.x > dFar + ( dUp - p.z ) * dUp * invFar ) {
1006  x = 2;
1007  }
1008  }
1009 
1010  r = sphere.GetRadius();
1011  index = VORONOI_INDEX( x, y, z );
1012  switch( index ) {
1013  case VORONOI_INDEX( 0, 0, 0 ): return true;
1014  case VORONOI_INDEX( 1, 0, 0 ): return ( dNear - p.x < r );
1015  case VORONOI_INDEX( 2, 0, 0 ): return ( p.x - dFar < r );
1016  case VORONOI_INDEX( 0, 1, 0 ): d = dFar * p.y - dLeft * p.x; return ( d * d < r * r * ( dFar * dFar + dLeft * dLeft ) );
1017  case VORONOI_INDEX( 0, 2, 0 ): d = -dFar * p.z - dLeft * p.x; return ( d * d < r * r * ( dFar * dFar + dLeft * dLeft ) );
1018  case VORONOI_INDEX( 0, 0, 1 ): d = dFar * p.z - dUp * p.x; return ( d * d < r * r * ( dFar * dFar + dUp * dUp ) );
1019  case VORONOI_INDEX( 0, 0, 2 ): d = -dFar * p.z - dUp * p.x; return ( d * d < r * r * ( dFar * dFar + dUp * dUp ) );
1020  default: {
1021  ToIndexPoints( points );
1022  switch( index ) {
1023  case VORONOI_INDEX( 1, 1, 1 ): return sphere.ContainsPoint( points[0] );
1024  case VORONOI_INDEX( 2, 1, 1 ): return sphere.ContainsPoint( points[4] );
1025  case VORONOI_INDEX( 1, 2, 1 ): return sphere.ContainsPoint( points[1] );
1026  case VORONOI_INDEX( 2, 2, 1 ): return sphere.ContainsPoint( points[5] );
1027  case VORONOI_INDEX( 1, 1, 2 ): return sphere.ContainsPoint( points[2] );
1028  case VORONOI_INDEX( 2, 1, 2 ): return sphere.ContainsPoint( points[6] );
1029  case VORONOI_INDEX( 1, 2, 2 ): return sphere.ContainsPoint( points[3] );
1030  case VORONOI_INDEX( 2, 2, 2 ): return sphere.ContainsPoint( points[7] );
1031  case VORONOI_INDEX( 1, 1, 0 ): return sphere.LineIntersection( points[0], points[2] );
1032  case VORONOI_INDEX( 2, 1, 0 ): return sphere.LineIntersection( points[4], points[6] );
1033  case VORONOI_INDEX( 1, 2, 0 ): return sphere.LineIntersection( points[1], points[3] );
1034  case VORONOI_INDEX( 2, 2, 0 ): return sphere.LineIntersection( points[5], points[7] );
1035  case VORONOI_INDEX( 1, 0, 1 ): return sphere.LineIntersection( points[0], points[1] );
1036  case VORONOI_INDEX( 2, 0, 1 ): return sphere.LineIntersection( points[4], points[5] );
1037  case VORONOI_INDEX( 0, 1, 1 ): return sphere.LineIntersection( points[0], points[4] );
1038  case VORONOI_INDEX( 0, 2, 1 ): return sphere.LineIntersection( points[1], points[5] );
1039  case VORONOI_INDEX( 1, 0, 2 ): return sphere.LineIntersection( points[2], points[3] );
1040  case VORONOI_INDEX( 2, 0, 2 ): return sphere.LineIntersection( points[6], points[7] );
1041  case VORONOI_INDEX( 0, 1, 2 ): return sphere.LineIntersection( points[2], points[6] );
1042  case VORONOI_INDEX( 0, 2, 2 ): return sphere.LineIntersection( points[3], points[7] );
1043  }
1044  break;
1045  }
1046  }
1047  return false;
1048 }
1049 
1050 /*
1051 ============
1052 idFrustum::IntersectsFrustum
1053 ============
1054 */
1055 bool idFrustum::IntersectsFrustum( const idFrustum &frustum ) const {
1056  idVec3 indexPoints2[8], cornerVecs2[4];
1057  idFrustum localFrustum2;
1058 
1059  localFrustum2 = frustum;
1060  localFrustum2.origin = ( frustum.origin - origin ) * axis.Transpose();
1061  localFrustum2.axis = frustum.axis * axis.Transpose();
1062  localFrustum2.ToIndexPointsAndCornerVecs( indexPoints2, cornerVecs2 );
1063 
1064  if ( CullLocalFrustum( localFrustum2, indexPoints2, cornerVecs2 ) ) {
1065  return false;
1066  }
1067 
1068  idVec3 indexPoints1[8], cornerVecs1[4];
1069  idFrustum localFrustum1;
1070 
1071  localFrustum1 = *this;
1072  localFrustum1.origin = ( origin - frustum.origin ) * frustum.axis.Transpose();
1073  localFrustum1.axis = axis * frustum.axis.Transpose();
1074  localFrustum1.ToIndexPointsAndCornerVecs( indexPoints1, cornerVecs1 );
1075 
1076  if ( frustum.CullLocalFrustum( localFrustum1, indexPoints1, cornerVecs1 ) ) {
1077  return false;
1078  }
1079 
1080  idSwap( indexPoints2[2], indexPoints2[3] );
1081  idSwap( indexPoints2[6], indexPoints2[7] );
1082 
1083  if ( LocalFrustumIntersectsFrustum( indexPoints2, ( localFrustum2.dNear > 0.0f ) ) ) {
1084  return true;
1085  }
1086 
1087  idSwap( indexPoints1[2], indexPoints1[3] );
1088  idSwap( indexPoints1[6], indexPoints1[7] );
1089 
1090  if ( frustum.LocalFrustumIntersectsFrustum( indexPoints1, ( localFrustum1.dNear > 0.0f ) ) ) {
1091  return true;
1092  }
1093 
1094  return false;
1095 }
1096 
1097 /*
1098 ============
1099 idFrustum::IntersectsWinding
1100 ============
1101 */
1102 bool idFrustum::IntersectsWinding( const idWinding &winding ) const {
1103  int i, j, *pointCull;
1104  float min, max;
1105  idVec3 *localPoints, indexPoints[8], cornerVecs[4];
1106  idMat3 transpose;
1107  idPlane plane;
1108 
1109  localPoints = (idVec3 *) _alloca16( winding.GetNumPoints() * sizeof( idVec3 ) );
1110  pointCull = (int *) _alloca16( winding.GetNumPoints() * sizeof( int ) );
1111 
1112  transpose = axis.Transpose();
1113  for ( i = 0; i < winding.GetNumPoints(); i++ ) {
1114  localPoints[i] = ( winding[i].ToVec3() - origin ) * transpose;
1115  }
1116 
1117  // if the winding is culled
1118  if ( CullLocalWinding( localPoints, winding.GetNumPoints(), pointCull ) ) {
1119  return false;
1120  }
1121 
1122  winding.GetPlane( plane );
1123 
1124  ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
1125  AxisProjection( indexPoints, cornerVecs, plane.Normal(), min, max );
1126 
1127  // if the frustum does not cross the winding plane
1128  if ( min + plane[3] > 0.0f || max + plane[3] < 0.0f ) {
1129  return false;
1130  }
1131 
1132  // test if any of the winding edges goes through the frustum
1133  for ( i = 0; i < winding.GetNumPoints(); i++ ) {
1134  j = (i+1)%winding.GetNumPoints();
1135  if ( !( pointCull[i] & pointCull[j] ) ) {
1136  if ( LocalLineIntersection( localPoints[i], localPoints[j] ) ) {
1137  return true;
1138  }
1139  }
1140  }
1141 
1142  idSwap( indexPoints[2], indexPoints[3] );
1143  idSwap( indexPoints[6], indexPoints[7] );
1144 
1145  // test if any edges of the frustum intersect the winding
1146  for ( i = 0; i < 4; i++ ) {
1147  if ( winding.LineIntersection( plane, indexPoints[i], indexPoints[4+i] ) ) {
1148  return true;
1149  }
1150  }
1151  if ( dNear > 0.0f ) {
1152  for ( i = 0; i < 4; i++ ) {
1153  if ( winding.LineIntersection( plane, indexPoints[i], indexPoints[(i+1)&3] ) ) {
1154  return true;
1155  }
1156  }
1157  }
1158  for ( i = 0; i < 4; i++ ) {
1159  if ( winding.LineIntersection( plane, indexPoints[4+i], indexPoints[4+((i+1)&3)] ) ) {
1160  return true;
1161  }
1162  }
1163 
1164  return false;
1165 }
1166 
1167 /*
1168 ============
1169 idFrustum::LineIntersection
1170 
1171  Returns true if the line intersects the box between the start and end point.
1172 ============
1173 */
1174 bool idFrustum::LineIntersection( const idVec3 &start, const idVec3 &end ) const {
1175  return LocalLineIntersection( ( start - origin ) * axis.Transpose(), ( end - origin ) * axis.Transpose() );
1176 }
1177 
1178 /*
1179 ============
1180 idFrustum::RayIntersection
1181 
1182  Returns true if the ray intersects the bounds.
1183  The ray can intersect the bounds in both directions from the start point.
1184  If start is inside the frustum then scale1 < 0 and scale2 > 0.
1185 ============
1186 */
1187 bool idFrustum::RayIntersection( const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2 ) const {
1188  if ( LocalRayIntersection( ( start - origin ) * axis.Transpose(), dir * axis.Transpose(), scale1, scale2 ) ) {
1189  return true;
1190  }
1191  if ( scale1 <= scale2 ) {
1192  return true;
1193  }
1194  return false;
1195 }
1196 
1197 /*
1198 ============
1199 idFrustum::FromProjection
1200 
1201  Creates a frustum which contains the projection of the bounds.
1202 ============
1203 */
1204 bool idFrustum::FromProjection( const idBounds &bounds, const idVec3 &projectionOrigin, const float dFar ) {
1205  return FromProjection( idBox( bounds, vec3_origin, mat3_identity ), projectionOrigin, dFar );
1206 }
1207 
1208 /*
1209 ============
1210 idFrustum::FromProjection
1211 
1212  Creates a frustum which contains the projection of the box.
1213 ============
1214 */
1215 bool idFrustum::FromProjection( const idBox &box, const idVec3 &projectionOrigin, const float dFar ) {
1216  int i, bestAxis;
1217  float value, bestValue;
1218  idVec3 dir;
1219 
1220  assert( dFar > 0.0f );
1221 
1222  this->dNear = this->dFar = this->invFar = 0.0f;
1223 
1224  dir = box.GetCenter() - projectionOrigin;
1225  if ( dir.Normalize() == 0.0f ) {
1226  return false;
1227  }
1228 
1229  bestAxis = 0;
1230  bestValue = idMath::Fabs( box.GetAxis()[0] * dir );
1231  for ( i = 1; i < 3; i++ ) {
1232  value = idMath::Fabs( box.GetAxis()[i] * dir );
1233  if ( value * box.GetExtents()[bestAxis] * box.GetExtents()[bestAxis] < bestValue * box.GetExtents()[i] * box.GetExtents()[i] ) {
1234  bestValue = value;
1235  bestAxis = i;
1236  }
1237  }
1238 
1239 #if 1
1240 
1241  int j, minX, minY, maxY, minZ, maxZ;
1242  idVec3 points[8];
1243 
1244  minX = minY = maxY = minZ = maxZ = 0;
1245 
1246  for ( j = 0; j < 2; j++ ) {
1247 
1248  axis[0] = dir;
1249  axis[1] = box.GetAxis()[bestAxis] - ( box.GetAxis()[bestAxis] * axis[0] ) * axis[0];
1250  axis[1].Normalize();
1251  axis[2].Cross( axis[0], axis[1] );
1252 
1253  BoxToPoints( ( box.GetCenter() - projectionOrigin ) * axis.Transpose(), box.GetExtents(), box.GetAxis() * axis.Transpose(), points );
1254 
1255  if ( points[0].x <= 1.0f ) {
1256  return false;
1257  }
1258 
1259  minX = minY = maxY = minZ = maxZ = 0;
1260  for ( i = 1; i < 8; i++ ) {
1261  if ( points[i].x <= 1.0f ) {
1262  return false;
1263  }
1264  if ( points[i].x < points[minX].x ) {
1265  minX = i;
1266  }
1267  if ( points[minY].x * points[i].y < points[i].x * points[minY].y ) {
1268  minY = i;
1269  } else if ( points[maxY].x * points[i].y > points[i].x * points[maxY].y ) {
1270  maxY = i;
1271  }
1272  if ( points[minZ].x * points[i].z < points[i].x * points[minZ].z ) {
1273  minZ = i;
1274  } else if ( points[maxZ].x * points[i].z > points[i].x * points[maxZ].z ) {
1275  maxZ = i;
1276  }
1277  }
1278 
1279  if ( j == 0 ) {
1280  dir += idMath::Tan16( 0.5f * ( idMath::ATan16( points[minY].y, points[minY].x ) + idMath::ATan16( points[maxY].y, points[maxY].x ) ) ) * axis[1];
1281  dir += idMath::Tan16( 0.5f * ( idMath::ATan16( points[minZ].z, points[minZ].x ) + idMath::ATan16( points[maxZ].z, points[maxZ].x ) ) ) * axis[2];
1282  dir.Normalize();
1283  }
1284  }
1285 
1286  this->origin = projectionOrigin;
1287  this->dNear = points[minX].x;
1288  this->dFar = dFar;
1289  this->dLeft = Max( idMath::Fabs( points[minY].y / points[minY].x ), idMath::Fabs( points[maxY].y / points[maxY].x ) ) * dFar;
1290  this->dUp = Max( idMath::Fabs( points[minZ].z / points[minZ].x ), idMath::Fabs( points[maxZ].z / points[maxZ].x ) ) * dFar;
1291  this->invFar = 1.0f / dFar;
1292 
1293 #elif 1
1294 
1295  int j;
1296  float f, x;
1297  idBounds b;
1298  idVec3 points[8];
1299 
1300  for ( j = 0; j < 2; j++ ) {
1301 
1302  axis[0] = dir;
1303  axis[1] = box.GetAxis()[bestAxis] - ( box.GetAxis()[bestAxis] * axis[0] ) * axis[0];
1304  axis[1].Normalize();
1305  axis[2].Cross( axis[0], axis[1] );
1306 
1307  BoxToPoints( ( box.GetCenter() - projectionOrigin ) * axis.Transpose(), box.GetExtents(), box.GetAxis() * axis.Transpose(), points );
1308 
1309  b.Clear();
1310  for ( i = 0; i < 8; i++ ) {
1311  x = points[i].x;
1312  if ( x <= 1.0f ) {
1313  return false;
1314  }
1315  f = 1.0f / x;
1316  points[i].y *= f;
1317  points[i].z *= f;
1318  b.AddPoint( points[i] );
1319  }
1320 
1321  if ( j == 0 ) {
1322  dir += idMath::Tan16( 0.5f * ( idMath::ATan16( b[1][1] ) + idMath::ATan16( b[0][1] ) ) ) * axis[1];
1323  dir += idMath::Tan16( 0.5f * ( idMath::ATan16( b[1][2] ) + idMath::ATan16( b[0][2] ) ) ) * axis[2];
1324  dir.Normalize();
1325  }
1326  }
1327 
1328  this->origin = projectionOrigin;
1329  this->dNear = b[0][0];
1330  this->dFar = dFar;
1331  this->dLeft = Max( idMath::Fabs( b[0][1] ), idMath::Fabs( b[1][1] ) ) * dFar;
1332  this->dUp = Max( idMath::Fabs( b[0][2] ), idMath::Fabs( b[1][2] ) ) * dFar;
1333  this->invFar = 1.0f / dFar;
1334 
1335 #else
1336 
1337  float dist;
1338  idVec3 org;
1339 
1340  axis[0] = dir;
1341  axis[1] = box.GetAxis()[bestAxis] - ( box.GetAxis()[bestAxis] * axis[0] ) * axis[0];
1342  axis[1].Normalize();
1343  axis[2].Cross( axis[0], axis[1] );
1344 
1345  for ( i = 0; i < 3; i++ ) {
1346  dist[i] = idMath::Fabs( box.GetExtents()[0] * ( axis[i] * box.GetAxis()[0] ) ) +
1347  idMath::Fabs( box.GetExtents()[1] * ( axis[i] * box.GetAxis()[1] ) ) +
1348  idMath::Fabs( box.GetExtents()[2] * ( axis[i] * box.GetAxis()[2] ) );
1349  }
1350 
1351  dist[0] = axis[0] * ( box.GetCenter() - projectionOrigin ) - dist[0];
1352  if ( dist[0] <= 1.0f ) {
1353  return false;
1354  }
1355  float invDist = 1.0f / dist[0];
1356 
1357  this->origin = projectionOrigin;
1358  this->dNear = dist[0];
1359  this->dFar = dFar;
1360  this->dLeft = dist[1] * invDist * dFar;
1361  this->dUp = dist[2] * invDist * dFar;
1362  this->invFar = 1.0f / dFar;
1363 
1364 #endif
1365 
1366  return true;
1367 }
1368 
1369 /*
1370 ============
1371 idFrustum::FromProjection
1372 
1373  Creates a frustum which contains the projection of the sphere.
1374 ============
1375 */
1376 bool idFrustum::FromProjection( const idSphere &sphere, const idVec3 &projectionOrigin, const float dFar ) {
1377  idVec3 dir;
1378  float d, r, s, x, y;
1379 
1380  assert( dFar > 0.0f );
1381 
1382  dir = sphere.GetOrigin() - projectionOrigin;
1383  d = dir.Normalize();
1384  r = sphere.GetRadius();
1385 
1386  if ( d <= r + 1.0f ) {
1387  this->dNear = this->dFar = this->invFar = 0.0f;
1388  return false;
1389  }
1390 
1391  origin = projectionOrigin;
1392  axis = dir.ToMat3();
1393 
1394  s = idMath::Sqrt( d * d - r * r );
1395  x = r / d * s;
1396  y = idMath::Sqrt( s * s - x * x );
1397 
1398  this->dNear = d - r;
1399  this->dFar = dFar;
1400  this->dLeft = x / y * dFar;
1401  this->dUp = dLeft;
1402  this->invFar = 1.0f / dFar;
1403 
1404  return true;
1405 }
1406 
1407 /*
1408 ============
1409 idFrustum::ConstrainToBounds
1410 
1411  Returns false if no part of the bounds extends beyond the near plane.
1412 ============
1413 */
1414 bool idFrustum::ConstrainToBounds( const idBounds &bounds ) {
1415  float min, max, newdFar;
1416 
1417  bounds.AxisProjection( axis[0], min, max );
1418  newdFar = max - axis[0] * origin;
1419  if ( newdFar <= dNear ) {
1420  MoveFarDistance( dNear + 1.0f );
1421  return false;
1422  }
1423  MoveFarDistance( newdFar );
1424  return true;
1425 }
1426 
1427 /*
1428 ============
1429 idFrustum::ConstrainToBox
1430 
1431  Returns false if no part of the box extends beyond the near plane.
1432 ============
1433 */
1434 bool idFrustum::ConstrainToBox( const idBox &box ) {
1435  float min, max, newdFar;
1436 
1437  box.AxisProjection( axis[0], min, max );
1438  newdFar = max - axis[0] * origin;
1439  if ( newdFar <= dNear ) {
1440  MoveFarDistance( dNear + 1.0f );
1441  return false;
1442  }
1443  MoveFarDistance( newdFar );
1444  return true;
1445 }
1446 
1447 /*
1448 ============
1449 idFrustum::ConstrainToSphere
1450 
1451  Returns false if no part of the sphere extends beyond the near plane.
1452 ============
1453 */
1454 bool idFrustum::ConstrainToSphere( const idSphere &sphere ) {
1455  float min, max, newdFar;
1456 
1457  sphere.AxisProjection( axis[0], min, max );
1458  newdFar = max - axis[0] * origin;
1459  if ( newdFar <= dNear ) {
1460  MoveFarDistance( dNear + 1.0f );
1461  return false;
1462  }
1463  MoveFarDistance( newdFar );
1464  return true;
1465 }
1466 
1467 /*
1468 ============
1469 idFrustum::ConstrainToFrustum
1470 
1471  Returns false if no part of the frustum extends beyond the near plane.
1472 ============
1473 */
1474 bool idFrustum::ConstrainToFrustum( const idFrustum &frustum ) {
1475  float min, max, newdFar;
1476 
1477  frustum.AxisProjection( axis[0], min, max );
1478  newdFar = max - axis[0] * origin;
1479  if ( newdFar <= dNear ) {
1480  MoveFarDistance( dNear + 1.0f );
1481  return false;
1482  }
1483  MoveFarDistance( newdFar );
1484  return true;
1485 }
1486 
1487 /*
1488 ============
1489 idFrustum::ToPlanes
1490 
1491  planes point outwards
1492 ============
1493 */
1494 void idFrustum::ToPlanes( idPlane planes[6] ) const {
1495  int i;
1496  idVec3 scaled[2];
1497  idVec3 points[4];
1498 
1499  planes[0].Normal() = -axis[0];
1500  planes[0].SetDist( -dNear );
1501  planes[1].Normal() = axis[0];
1502  planes[1].SetDist( dFar );
1503 
1504  scaled[0] = axis[1] * dLeft;
1505  scaled[1] = axis[2] * dUp;
1506  points[0] = scaled[0] + scaled[1];
1507  points[1] = -scaled[0] + scaled[1];
1508  points[2] = -scaled[0] - scaled[1];
1509  points[3] = scaled[0] - scaled[1];
1510 
1511  for ( i = 0; i < 4; i++ ) {
1512  planes[i+2].Normal() = points[i].Cross( points[(i+1)&3] - points[i] );
1513  planes[i+2].Normalize();
1514  planes[i+2].FitThroughPoint( points[i] );
1515  }
1516 }
1517 
1518 /*
1519 ============
1520 idFrustum::ToPoints
1521 ============
1522 */
1523 void idFrustum::ToPoints( idVec3 points[8] ) const {
1524  idMat3 scaled;
1525 
1526  scaled[0] = origin + axis[0] * dNear;
1527  scaled[1] = axis[1] * ( dLeft * dNear * invFar );
1528  scaled[2] = axis[2] * ( dUp * dNear * invFar );
1529 
1530  points[0] = scaled[0] + scaled[1];
1531  points[1] = scaled[0] - scaled[1];
1532  points[2] = points[1] - scaled[2];
1533  points[3] = points[0] - scaled[2];
1534  points[0] += scaled[2];
1535  points[1] += scaled[2];
1536 
1537  scaled[0] = origin + axis[0] * dFar;
1538  scaled[1] = axis[1] * dLeft;
1539  scaled[2] = axis[2] * dUp;
1540 
1541  points[4] = scaled[0] + scaled[1];
1542  points[5] = scaled[0] - scaled[1];
1543  points[6] = points[5] - scaled[2];
1544  points[7] = points[4] - scaled[2];
1545  points[4] += scaled[2];
1546  points[5] += scaled[2];
1547 }
1548 
1549 /*
1550 ============
1551 idFrustum::ToClippedPoints
1552 ============
1553 */
1554 void idFrustum::ToClippedPoints( const float fractions[4], idVec3 points[8] ) const {
1555  idMat3 scaled;
1556 
1557  scaled[0] = origin + axis[0] * dNear;
1558  scaled[1] = axis[1] * ( dLeft * dNear * invFar );
1559  scaled[2] = axis[2] * ( dUp * dNear * invFar );
1560 
1561  points[0] = scaled[0] + scaled[1];
1562  points[1] = scaled[0] - scaled[1];
1563  points[2] = points[1] - scaled[2];
1564  points[3] = points[0] - scaled[2];
1565  points[0] += scaled[2];
1566  points[1] += scaled[2];
1567 
1568  scaled[0] = axis[0] * dFar;
1569  scaled[1] = axis[1] * dLeft;
1570  scaled[2] = axis[2] * dUp;
1571 
1572  points[4] = scaled[0] + scaled[1];
1573  points[5] = scaled[0] - scaled[1];
1574  points[6] = points[5] - scaled[2];
1575  points[7] = points[4] - scaled[2];
1576  points[4] += scaled[2];
1577  points[5] += scaled[2];
1578 
1579  points[4] = origin + fractions[0] * points[4];
1580  points[5] = origin + fractions[1] * points[5];
1581  points[6] = origin + fractions[2] * points[6];
1582  points[7] = origin + fractions[3] * points[7];
1583 }
1584 
1585 /*
1586 ============
1587 idFrustum::ToIndexPoints
1588 ============
1589 */
1590 void idFrustum::ToIndexPoints( idVec3 indexPoints[8] ) const {
1591  idMat3 scaled;
1592 
1593  scaled[0] = origin + axis[0] * dNear;
1594  scaled[1] = axis[1] * ( dLeft * dNear * invFar );
1595  scaled[2] = axis[2] * ( dUp * dNear * invFar );
1596 
1597  indexPoints[0] = scaled[0] - scaled[1];
1598  indexPoints[2] = scaled[0] + scaled[1];
1599  indexPoints[1] = indexPoints[0] + scaled[2];
1600  indexPoints[3] = indexPoints[2] + scaled[2];
1601  indexPoints[0] -= scaled[2];
1602  indexPoints[2] -= scaled[2];
1603 
1604  scaled[0] = origin + axis[0] * dFar;
1605  scaled[1] = axis[1] * dLeft;
1606  scaled[2] = axis[2] * dUp;
1607 
1608  indexPoints[4] = scaled[0] - scaled[1];
1609  indexPoints[6] = scaled[0] + scaled[1];
1610  indexPoints[5] = indexPoints[4] + scaled[2];
1611  indexPoints[7] = indexPoints[6] + scaled[2];
1612  indexPoints[4] -= scaled[2];
1613  indexPoints[6] -= scaled[2];
1614 }
1615 
1616 /*
1617 ============
1618 idFrustum::ToIndexPointsAndCornerVecs
1619 
1620  22 muls
1621 ============
1622 */
1623 void idFrustum::ToIndexPointsAndCornerVecs( idVec3 indexPoints[8], idVec3 cornerVecs[4] ) const {
1624  idMat3 scaled;
1625 
1626  scaled[0] = origin + axis[0] * dNear;
1627  scaled[1] = axis[1] * ( dLeft * dNear * invFar );
1628  scaled[2] = axis[2] * ( dUp * dNear * invFar );
1629 
1630  indexPoints[0] = scaled[0] - scaled[1];
1631  indexPoints[2] = scaled[0] + scaled[1];
1632  indexPoints[1] = indexPoints[0] + scaled[2];
1633  indexPoints[3] = indexPoints[2] + scaled[2];
1634  indexPoints[0] -= scaled[2];
1635  indexPoints[2] -= scaled[2];
1636 
1637  scaled[0] = axis[0] * dFar;
1638  scaled[1] = axis[1] * dLeft;
1639  scaled[2] = axis[2] * dUp;
1640 
1641  cornerVecs[0] = scaled[0] - scaled[1];
1642  cornerVecs[2] = scaled[0] + scaled[1];
1643  cornerVecs[1] = cornerVecs[0] + scaled[2];
1644  cornerVecs[3] = cornerVecs[2] + scaled[2];
1645  cornerVecs[0] -= scaled[2];
1646  cornerVecs[2] -= scaled[2];
1647 
1648  indexPoints[4] = cornerVecs[0] + origin;
1649  indexPoints[5] = cornerVecs[1] + origin;
1650  indexPoints[6] = cornerVecs[2] + origin;
1651  indexPoints[7] = cornerVecs[3] + origin;
1652 }
1653 
1654 /*
1655 ============
1656 idFrustum::AxisProjection
1657 
1658  18 muls
1659 ============
1660 */
1661 void idFrustum::AxisProjection( const idVec3 indexPoints[8], const idVec3 cornerVecs[4], const idVec3 &dir, float &min, float &max ) const {
1662  float dx, dy, dz;
1663  int index;
1664 
1665  dy = dir.x * axis[1].x + dir.y * axis[1].y + dir.z * axis[1].z;
1666  dz = dir.x * axis[2].x + dir.y * axis[2].y + dir.z * axis[2].z;
1667  index = ( FLOATSIGNBITSET( dy ) << 1 ) | FLOATSIGNBITSET( dz );
1668  dx = dir.x * cornerVecs[index].x + dir.y * cornerVecs[index].y + dir.z * cornerVecs[index].z;
1669  index |= ( FLOATSIGNBITSET( dx ) << 2 );
1670  min = indexPoints[index] * dir;
1671  index = ~index & 3;
1672  dx = -dir.x * cornerVecs[index].x - dir.y * cornerVecs[index].y - dir.z * cornerVecs[index].z;
1673  index |= ( FLOATSIGNBITSET( dx ) << 2 );
1674  max = indexPoints[index] * dir;
1675 }
1676 
1677 /*
1678 ============
1679 idFrustum::AxisProjection
1680 
1681  40 muls
1682 ============
1683 */
1684 void idFrustum::AxisProjection( const idVec3 &dir, float &min, float &max ) const {
1685  idVec3 indexPoints[8], cornerVecs[4];
1686 
1687  ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
1688  AxisProjection( indexPoints, cornerVecs, dir, min, max );
1689 }
1690 
1691 /*
1692 ============
1693 idFrustum::AxisProjection
1694 
1695  76 muls
1696 ============
1697 */
1698 void idFrustum::AxisProjection( const idMat3 &ax, idBounds &bounds ) const {
1699  idVec3 indexPoints[8], cornerVecs[4];
1700 
1701  ToIndexPointsAndCornerVecs( indexPoints, cornerVecs );
1702  AxisProjection( indexPoints, cornerVecs, ax[0], bounds[0][0], bounds[1][0] );
1703  AxisProjection( indexPoints, cornerVecs, ax[1], bounds[0][1], bounds[1][1] );
1704  AxisProjection( indexPoints, cornerVecs, ax[2], bounds[0][2], bounds[1][2] );
1705 }
1706 
1707 /*
1708 ============
1709 idFrustum::AddLocalLineToProjectionBoundsSetCull
1710 ============
1711 */
1712 void idFrustum::AddLocalLineToProjectionBoundsSetCull( const idVec3 &start, const idVec3 &end, int &startCull, int &endCull, idBounds &bounds ) const {
1713  idVec3 dir, p;
1714  float d1, d2, fstart, fend, lstart, lend, f;
1715  float leftScale, upScale;
1716  int cull1, cull2;
1717 
1718 #ifdef FRUSTUM_DEBUG
1719  static idCVar r_showInteractionScissors( "r_showInteractionScissors", "0", CVAR_RENDERER | CVAR_INTEGER, "", 0, 2, idCmdSystem::ArgCompletion_Integer<0,2> );
1720  if ( r_showInteractionScissors.GetInteger() > 1 ) {
1721  session->rw->DebugLine( colorGreen, origin + start * axis, origin + end * axis );
1722  }
1723 #endif
1724 
1725  leftScale = dLeft * invFar;
1726  upScale = dUp * invFar;
1727  dir = end - start;
1728 
1729  fstart = dFar * start.y;
1730  fend = dFar * end.y;
1731  lstart = dLeft * start.x;
1732  lend = dLeft * end.x;
1733 
1734  // test left plane
1735  d1 = -fstart + lstart;
1736  d2 = -fend + lend;
1737  cull1 = FLOATSIGNBITSET( d1 );
1738  cull2 = FLOATSIGNBITSET( d2 );
1739  if ( FLOATNOTZERO( d1 ) ) {
1740  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1741  f = d1 / ( d1 - d2 );
1742  p.x = start.x + f * dir.x;
1743  if ( p.x > 0.0f ) {
1744  p.z = start.z + f * dir.z;
1745  if ( idMath::Fabs( p.z ) <= p.x * upScale ) {
1746  p.y = 1.0f;
1747  p.z = p.z * dFar / ( p.x * dUp );
1748  bounds.AddPoint( p );
1749  }
1750  }
1751  }
1752  }
1753 
1754  // test right plane
1755  d1 = fstart + lstart;
1756  d2 = fend + lend;
1757  cull1 |= FLOATSIGNBITSET( d1 ) << 1;
1758  cull2 |= FLOATSIGNBITSET( d2 ) << 1;
1759  if ( FLOATNOTZERO( d1 ) ) {
1760  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1761  f = d1 / ( d1 - d2 );
1762  p.x = start.x + f * dir.x;
1763  if ( p.x > 0.0f ) {
1764  p.z = start.z + f * dir.z;
1765  if ( idMath::Fabs( p.z ) <= p.x * upScale ) {
1766  p.y = -1.0f;
1767  p.z = p.z * dFar / ( p.x * dUp );
1768  bounds.AddPoint( p );
1769  }
1770  }
1771  }
1772  }
1773 
1774  fstart = dFar * start.z;
1775  fend = dFar * end.z;
1776  lstart = dUp * start.x;
1777  lend = dUp * end.x;
1778 
1779  // test up plane
1780  d1 = -fstart + lstart;
1781  d2 = -fend + lend;
1782  cull1 |= FLOATSIGNBITSET( d1 ) << 2;
1783  cull2 |= FLOATSIGNBITSET( d2 ) << 2;
1784  if ( FLOATNOTZERO( d1 ) ) {
1785  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1786  f = d1 / ( d1 - d2 );
1787  p.x = start.x + f * dir.x;
1788  if ( p.x > 0.0f ) {
1789  p.y = start.y + f * dir.y;
1790  if ( idMath::Fabs( p.y ) <= p.x * leftScale ) {
1791  p.y = p.y * dFar / ( p.x * dLeft );
1792  p.z = 1.0f;
1793  bounds.AddPoint( p );
1794  }
1795  }
1796  }
1797  }
1798 
1799  // test down plane
1800  d1 = fstart + lstart;
1801  d2 = fend + lend;
1802  cull1 |= FLOATSIGNBITSET( d1 ) << 3;
1803  cull2 |= FLOATSIGNBITSET( d2 ) << 3;
1804  if ( FLOATNOTZERO( d1 ) ) {
1805  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1806  f = d1 / ( d1 - d2 );
1807  p.x = start.x + f * dir.x;
1808  if ( p.x > 0.0f ) {
1809  p.y = start.y + f * dir.y;
1810  if ( idMath::Fabs( p.y ) <= p.x * leftScale ) {
1811  p.y = p.y * dFar / ( p.x * dLeft );
1812  p.z = -1.0f;
1813  bounds.AddPoint( p );
1814  }
1815  }
1816  }
1817  }
1818 
1819  if ( cull1 == 0 && start.x > 0.0f ) {
1820  // add start point to projection bounds
1821  p.x = start.x;
1822  p.y = start.y * dFar / ( start.x * dLeft );
1823  p.z = start.z * dFar / ( start.x * dUp );
1824  bounds.AddPoint( p );
1825  }
1826 
1827  if ( cull2 == 0 && end.x > 0.0f ) {
1828  // add end point to projection bounds
1829  p.x = end.x;
1830  p.y = end.y * dFar / ( end.x * dLeft );
1831  p.z = end.z * dFar / ( end.x * dUp );
1832  bounds.AddPoint( p );
1833  }
1834 
1835  if ( start.x < bounds[0].x ) {
1836  bounds[0].x = start.x < 0.0f ? 0.0f : start.x;
1837  }
1838  if ( end.x < bounds[0].x ) {
1839  bounds[0].x = end.x < 0.0f ? 0.0f : end.x;
1840  }
1841 
1842  startCull = cull1;
1843  endCull = cull2;
1844 }
1845 
1846 /*
1847 ============
1848 idFrustum::AddLocalLineToProjectionBoundsUseCull
1849 ============
1850 */
1851 void idFrustum::AddLocalLineToProjectionBoundsUseCull( const idVec3 &start, const idVec3 &end, int startCull, int endCull, idBounds &bounds ) const {
1852  idVec3 dir, p;
1853  float d1, d2, fstart, fend, lstart, lend, f;
1854  float leftScale, upScale;
1855  int clip;
1856 
1857  clip = startCull ^ endCull;
1858  if ( !clip ) {
1859  return;
1860  }
1861 
1862 #ifdef FRUSTUM_DEBUG
1863  static idCVar r_showInteractionScissors( "r_showInteractionScissors", "0", CVAR_RENDERER | CVAR_INTEGER, "", 0, 2, idCmdSystem::ArgCompletion_Integer<0,2> );
1864  if ( r_showInteractionScissors.GetInteger() > 1 ) {
1865  session->rw->DebugLine( colorGreen, origin + start * axis, origin + end * axis );
1866  }
1867 #endif
1868 
1869  leftScale = dLeft * invFar;
1870  upScale = dUp * invFar;
1871  dir = end - start;
1872 
1873  if ( clip & (1|2) ) {
1874 
1875  fstart = dFar * start.y;
1876  fend = dFar * end.y;
1877  lstart = dLeft * start.x;
1878  lend = dLeft * end.x;
1879 
1880  if ( clip & 1 ) {
1881  // test left plane
1882  d1 = -fstart + lstart;
1883  d2 = -fend + lend;
1884  if ( FLOATNOTZERO( d1 ) ) {
1885  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1886  f = d1 / ( d1 - d2 );
1887  p.x = start.x + f * dir.x;
1888  if ( p.x > 0.0f ) {
1889  p.z = start.z + f * dir.z;
1890  if ( idMath::Fabs( p.z ) <= p.x * upScale ) {
1891  p.y = 1.0f;
1892  p.z = p.z * dFar / ( p.x * dUp );
1893  bounds.AddPoint( p );
1894  }
1895  }
1896  }
1897  }
1898  }
1899 
1900  if ( clip & 2 ) {
1901  // test right plane
1902  d1 = fstart + lstart;
1903  d2 = fend + lend;
1904  if ( FLOATNOTZERO( d1 ) ) {
1905  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1906  f = d1 / ( d1 - d2 );
1907  p.x = start.x + f * dir.x;
1908  if ( p.x > 0.0f ) {
1909  p.z = start.z + f * dir.z;
1910  if ( idMath::Fabs( p.z ) <= p.x * upScale ) {
1911  p.y = -1.0f;
1912  p.z = p.z * dFar / ( p.x * dUp );
1913  bounds.AddPoint( p );
1914  }
1915  }
1916  }
1917  }
1918  }
1919  }
1920 
1921  if ( clip & (4|8) ) {
1922 
1923  fstart = dFar * start.z;
1924  fend = dFar * end.z;
1925  lstart = dUp * start.x;
1926  lend = dUp * end.x;
1927 
1928  if ( clip & 4 ) {
1929  // test up plane
1930  d1 = -fstart + lstart;
1931  d2 = -fend + lend;
1932  if ( FLOATNOTZERO( d1 ) ) {
1933  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1934  f = d1 / ( d1 - d2 );
1935  p.x = start.x + f * dir.x;
1936  if ( p.x > 0.0f ) {
1937  p.y = start.y + f * dir.y;
1938  if ( idMath::Fabs( p.y ) <= p.x * leftScale ) {
1939  p.y = p.y * dFar / ( p.x * dLeft );
1940  p.z = 1.0f;
1941  bounds.AddPoint( p );
1942  }
1943  }
1944  }
1945  }
1946  }
1947 
1948  if ( clip & 8 ) {
1949  // test down plane
1950  d1 = fstart + lstart;
1951  d2 = fend + lend;
1952  if ( FLOATNOTZERO( d1 ) ) {
1953  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
1954  f = d1 / ( d1 - d2 );
1955  p.x = start.x + f * dir.x;
1956  if ( p.x > 0.0f ) {
1957  p.y = start.y + f * dir.y;
1958  if ( idMath::Fabs( p.y ) <= p.x * leftScale ) {
1959  p.y = p.y * dFar / ( p.x * dLeft );
1960  p.z = -1.0f;
1961  bounds.AddPoint( p );
1962  }
1963  }
1964  }
1965  }
1966  }
1967  }
1968 }
1969 
1970 /*
1971 ============
1972 idFrustum::BoundsRayIntersection
1973 
1974  Returns true if the ray starts inside the bounds.
1975  If there was an intersection scale1 <= scale2
1976 ============
1977 */
1978 bool idFrustum::BoundsRayIntersection( const idBounds &bounds, const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2 ) const {
1979  idVec3 end, p;
1980  float d1, d2, f;
1981  int i, startInside = 1;
1982 
1983  scale1 = idMath::INFINITY;
1984  scale2 = -idMath::INFINITY;
1985 
1986  end = start + dir;
1987 
1988  for ( i = 0; i < 2; i++ ) {
1989  d1 = start.x - bounds[i].x;
1990  startInside &= FLOATSIGNBITSET( d1 ) ^ i;
1991  d2 = end.x - bounds[i].x;
1992  if ( d1 != d2 ) {
1993  f = d1 / ( d1 - d2 );
1994  p.y = start.y + f * dir.y;
1995  if ( bounds[0].y <= p.y && p.y <= bounds[1].y ) {
1996  p.z = start.z + f * dir.z;
1997  if ( bounds[0].z <= p.z && p.z <= bounds[1].z ) {
1998  if ( f < scale1 ) scale1 = f;
1999  if ( f > scale2 ) scale2 = f;
2000  }
2001  }
2002  }
2003 
2004  d1 = start.y - bounds[i].y;
2005  startInside &= FLOATSIGNBITSET( d1 ) ^ i;
2006  d2 = end.y - bounds[i].y;
2007  if ( d1 != d2 ) {
2008  f = d1 / ( d1 - d2 );
2009  p.x = start.x + f * dir.x;
2010  if ( bounds[0].x <= p.x && p.x <= bounds[1].x ) {
2011  p.z = start.z + f * dir.z;
2012  if ( bounds[0].z <= p.z && p.z <= bounds[1].z ) {
2013  if ( f < scale1 ) scale1 = f;
2014  if ( f > scale2 ) scale2 = f;
2015  }
2016  }
2017  }
2018 
2019  d1 = start.z - bounds[i].z;
2020  startInside &= FLOATSIGNBITSET( d1 ) ^ i;
2021  d2 = end.z - bounds[i].z;
2022  if ( d1 != d2 ) {
2023  f = d1 / ( d1 - d2 );
2024  p.x = start.x + f * dir.x;
2025  if ( bounds[0].x <= p.x && p.x <= bounds[1].x ) {
2026  p.y = start.y + f * dir.y;
2027  if ( bounds[0].y <= p.y && p.y <= bounds[1].y ) {
2028  if ( f < scale1 ) scale1 = f;
2029  if ( f > scale2 ) scale2 = f;
2030  }
2031  }
2032  }
2033  }
2034 
2035  return ( startInside != 0 );
2036 }
2037 
2038 /*
2039 ============
2040 idFrustum::ProjectionBounds
2041 ============
2042 */
2043 bool idFrustum::ProjectionBounds( const idBounds &bounds, idBounds &projectionBounds ) const {
2044  return ProjectionBounds( idBox( bounds, vec3_origin, mat3_identity ), projectionBounds );
2045 }
2046 
2047 #ifndef __linux__
2048 
2049 /*
2050 ============
2051 idFrustum::ProjectionBounds
2052 ============
2053 */
2054 bool idFrustum::ProjectionBounds( const idBox &box, idBounds &projectionBounds ) const {
2055  int i, p1, p2, pointCull[8], culled, outside;
2056  float scale1, scale2;
2057  idFrustum localFrustum;
2058  idVec3 points[8], localOrigin;
2059  idMat3 localAxis, localScaled;
2060  idBounds bounds( -box.GetExtents(), box.GetExtents() );
2061 
2062  // if the frustum origin is inside the bounds
2063  if ( bounds.ContainsPoint( ( origin - box.GetCenter() ) * box.GetAxis().Transpose() ) ) {
2064  // bounds that cover the whole frustum
2065  float boxMin, boxMax, base;
2066 
2067  base = origin * axis[0];
2068  box.AxisProjection( axis[0], boxMin, boxMax );
2069 
2070  projectionBounds[0].x = boxMin - base;
2071  projectionBounds[1].x = boxMax - base;
2072  projectionBounds[0].y = projectionBounds[0].z = -1.0f;
2073  projectionBounds[1].y = projectionBounds[1].z = 1.0f;
2074 
2075  return true;
2076  }
2077 
2078  projectionBounds.Clear();
2079 
2080  // transform the bounds into the space of this frustum
2081  localOrigin = ( box.GetCenter() - origin ) * axis.Transpose();
2082  localAxis = box.GetAxis() * axis.Transpose();
2083  BoxToPoints( localOrigin, box.GetExtents(), localAxis, points );
2084 
2085  // test outer four edges of the bounds
2086  culled = -1;
2087  outside = 0;
2088  for ( i = 0; i < 4; i++ ) {
2089  p1 = i;
2090  p2 = 4 + i;
2091  AddLocalLineToProjectionBoundsSetCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2092  culled &= pointCull[p1] & pointCull[p2];
2093  outside |= pointCull[p1] | pointCull[p2];
2094  }
2095 
2096  // if the bounds are completely outside this frustum
2097  if ( culled ) {
2098  return false;
2099  }
2100 
2101  // if the bounds are completely inside this frustum
2102  if ( !outside ) {
2103  return true;
2104  }
2105 
2106  // test the remaining edges of the bounds
2107  for ( i = 0; i < 4; i++ ) {
2108  p1 = i;
2109  p2 = (i+1)&3;
2110  AddLocalLineToProjectionBoundsUseCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2111  }
2112 
2113  for ( i = 0; i < 4; i++ ) {
2114  p1 = 4 + i;
2115  p2 = 4 + ((i+1)&3);
2116  AddLocalLineToProjectionBoundsUseCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2117  }
2118 
2119  // if the bounds extend beyond two or more boundaries of this frustum
2120  if ( outside != 1 && outside != 2 && outside != 4 && outside != 8 ) {
2121 
2122  localOrigin = ( origin - box.GetCenter() ) * box.GetAxis().Transpose();
2123  localScaled = axis * box.GetAxis().Transpose();
2124  localScaled[0] *= dFar;
2125  localScaled[1] *= dLeft;
2126  localScaled[2] *= dUp;
2127 
2128  // test the outer edges of this frustum for intersection with the bounds
2129  if ( (outside & 2) && (outside & 8) ) {
2130  BoundsRayIntersection( bounds, localOrigin, localScaled[0] - localScaled[1] - localScaled[2], scale1, scale2 );
2131  if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2132  projectionBounds.AddPoint( idVec3( scale1 * dFar, -1.0f, -1.0f ) );
2133  projectionBounds.AddPoint( idVec3( scale2 * dFar, -1.0f, -1.0f ) );
2134  }
2135  }
2136  if ( (outside & 2) && (outside & 4) ) {
2137  BoundsRayIntersection( bounds, localOrigin, localScaled[0] - localScaled[1] + localScaled[2], scale1, scale2 );
2138  if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2139  projectionBounds.AddPoint( idVec3( scale1 * dFar, -1.0f, 1.0f ) );
2140  projectionBounds.AddPoint( idVec3( scale2 * dFar, -1.0f, 1.0f ) );
2141  }
2142  }
2143  if ( (outside & 1) && (outside & 8) ) {
2144  BoundsRayIntersection( bounds, localOrigin, localScaled[0] + localScaled[1] - localScaled[2], scale1, scale2 );
2145  if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2146  projectionBounds.AddPoint( idVec3( scale1 * dFar, 1.0f, -1.0f ) );
2147  projectionBounds.AddPoint( idVec3( scale2 * dFar, 1.0f, -1.0f ) );
2148  }
2149  }
2150  if ( (outside & 1) && (outside & 2) ) {
2151  BoundsRayIntersection( bounds, localOrigin, localScaled[0] + localScaled[1] + localScaled[2], scale1, scale2 );
2152  if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2153  projectionBounds.AddPoint( idVec3( scale1 * dFar, 1.0f, 1.0f ) );
2154  projectionBounds.AddPoint( idVec3( scale2 * dFar, 1.0f, 1.0f ) );
2155  }
2156  }
2157  }
2158 
2159  return true;
2160 }
2161 
2162 #endif
2163 
2164 /*
2165 ============
2166 idFrustum::ProjectionBounds
2167 ============
2168 */
2169 bool idFrustum::ProjectionBounds( const idSphere &sphere, idBounds &projectionBounds ) const {
2170  float d, r, rs, sFar;
2171  idVec3 center;
2172 
2173  projectionBounds.Clear();
2174 
2175  center = ( sphere.GetOrigin() - origin ) * axis.Transpose();
2176  r = sphere.GetRadius();
2177  rs = r * r;
2178  sFar = dFar * dFar;
2179 
2180  // test left/right planes
2181  d = dFar * idMath::Fabs( center.y ) - dLeft * center.x;
2182  if ( ( d * d ) > rs * ( sFar + dLeft * dLeft ) ) {
2183  return false;
2184  }
2185 
2186  // test up/down planes
2187  d = dFar * idMath::Fabs( center.z ) - dUp * center.x;
2188  if ( ( d * d ) > rs * ( sFar + dUp * dUp ) ) {
2189  return false;
2190  }
2191 
2192  // bounds that cover the whole frustum
2193  projectionBounds[0].x = 0.0f;
2194  projectionBounds[1].x = dFar;
2195  projectionBounds[0].y = projectionBounds[0].z = -1.0f;
2196  projectionBounds[1].y = projectionBounds[1].z = 1.0f;
2197  return true;
2198 }
2199 
2200 /*
2201 ============
2202 idFrustum::ProjectionBounds
2203 ============
2204 */
2205 bool idFrustum::ProjectionBounds( const idFrustum &frustum, idBounds &projectionBounds ) const {
2206  int i, p1, p2, pointCull[8], culled, outside;
2207  float scale1, scale2;
2208  idFrustum localFrustum;
2209  idVec3 points[8], localOrigin;
2210  idMat3 localScaled;
2211 
2212  // if the frustum origin is inside the other frustum
2213  if ( frustum.ContainsPoint( origin ) ) {
2214  // bounds that cover the whole frustum
2215  float frustumMin, frustumMax, base;
2216 
2217  base = origin * axis[0];
2218  frustum.AxisProjection( axis[0], frustumMin, frustumMax );
2219 
2220  projectionBounds[0].x = frustumMin - base;
2221  projectionBounds[1].x = frustumMax - base;
2222  projectionBounds[0].y = projectionBounds[0].z = -1.0f;
2223  projectionBounds[1].y = projectionBounds[1].z = 1.0f;
2224  return true;
2225  }
2226 
2227  projectionBounds.Clear();
2228 
2229  // transform the given frustum into the space of this frustum
2230  localFrustum = frustum;
2231  localFrustum.origin = ( frustum.origin - origin ) * axis.Transpose();
2232  localFrustum.axis = frustum.axis * axis.Transpose();
2233  localFrustum.ToPoints( points );
2234 
2235  // test outer four edges of the other frustum
2236  culled = -1;
2237  outside = 0;
2238  for ( i = 0; i < 4; i++ ) {
2239  p1 = i;
2240  p2 = 4 + i;
2241  AddLocalLineToProjectionBoundsSetCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2242  culled &= pointCull[p1] & pointCull[p2];
2243  outside |= pointCull[p1] | pointCull[p2];
2244  }
2245 
2246  // if the other frustum is completely outside this frustum
2247  if ( culled ) {
2248  return false;
2249  }
2250 
2251  // if the other frustum is completely inside this frustum
2252  if ( !outside ) {
2253  return true;
2254  }
2255 
2256  // test the remaining edges of the other frustum
2257  if ( localFrustum.dNear > 0.0f ) {
2258  for ( i = 0; i < 4; i++ ) {
2259  p1 = i;
2260  p2 = (i+1)&3;
2261  AddLocalLineToProjectionBoundsUseCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2262  }
2263  }
2264 
2265  for ( i = 0; i < 4; i++ ) {
2266  p1 = 4 + i;
2267  p2 = 4 + ((i+1)&3);
2268  AddLocalLineToProjectionBoundsUseCull( points[p1], points[p2], pointCull[p1], pointCull[p2], projectionBounds );
2269  }
2270 
2271  // if the other frustum extends beyond two or more boundaries of this frustum
2272  if ( outside != 1 && outside != 2 && outside != 4 && outside != 8 ) {
2273 
2274  localOrigin = ( origin - frustum.origin ) * frustum.axis.Transpose();
2275  localScaled = axis * frustum.axis.Transpose();
2276  localScaled[0] *= dFar;
2277  localScaled[1] *= dLeft;
2278  localScaled[2] *= dUp;
2279 
2280  // test the outer edges of this frustum for intersection with the other frustum
2281  if ( (outside & 2) && (outside & 8) ) {
2282  frustum.LocalRayIntersection( localOrigin, localScaled[0] - localScaled[1] - localScaled[2], scale1, scale2 );
2283  if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2284  projectionBounds.AddPoint( idVec3( scale1 * dFar, -1.0f, -1.0f ) );
2285  projectionBounds.AddPoint( idVec3( scale2 * dFar, -1.0f, -1.0f ) );
2286  }
2287  }
2288  if ( (outside & 2) && (outside & 4) ) {
2289  frustum.LocalRayIntersection( localOrigin, localScaled[0] - localScaled[1] + localScaled[2], scale1, scale2 );
2290  if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2291  projectionBounds.AddPoint( idVec3( scale1 * dFar, -1.0f, 1.0f ) );
2292  projectionBounds.AddPoint( idVec3( scale2 * dFar, -1.0f, 1.0f ) );
2293  }
2294  }
2295  if ( (outside & 1) && (outside & 8) ) {
2296  frustum.LocalRayIntersection( localOrigin, localScaled[0] + localScaled[1] - localScaled[2], scale1, scale2 );
2297  if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2298  projectionBounds.AddPoint( idVec3( scale1 * dFar, 1.0f, -1.0f ) );
2299  projectionBounds.AddPoint( idVec3( scale2 * dFar, 1.0f, -1.0f ) );
2300  }
2301  }
2302  if ( (outside & 1) && (outside & 2) ) {
2303  frustum.LocalRayIntersection( localOrigin, localScaled[0] + localScaled[1] + localScaled[2], scale1, scale2 );
2304  if ( scale1 <= scale2 && scale1 >= 0.0f ) {
2305  projectionBounds.AddPoint( idVec3( scale1 * dFar, 1.0f, 1.0f ) );
2306  projectionBounds.AddPoint( idVec3( scale2 * dFar, 1.0f, 1.0f ) );
2307  }
2308  }
2309  }
2310 
2311  return true;
2312 }
2313 
2314 /*
2315 ============
2316 idFrustum::ProjectionBounds
2317 ============
2318 */
2319 bool idFrustum::ProjectionBounds( const idWinding &winding, idBounds &projectionBounds ) const {
2320  int i, p1, p2, *pointCull, culled, outside;
2321  float scale;
2322  idVec3 *localPoints;
2323  idMat3 transpose, scaled;
2324  idPlane plane;
2325 
2326  projectionBounds.Clear();
2327 
2328  // transform the winding points into the space of this frustum
2329  localPoints = (idVec3 *) _alloca16( winding.GetNumPoints() * sizeof( idVec3 ) );
2330  transpose = axis.Transpose();
2331  for ( i = 0; i < winding.GetNumPoints(); i++ ) {
2332  localPoints[i] = ( winding[i].ToVec3() - origin ) * transpose;
2333  }
2334 
2335  // test the winding edges
2336  culled = -1;
2337  outside = 0;
2338  pointCull = (int *) _alloca16( winding.GetNumPoints() * sizeof( int ) );
2339  for ( i = 0; i < winding.GetNumPoints(); i += 2 ) {
2340  p1 = i;
2341  p2 = (i+1)%winding.GetNumPoints();
2342  AddLocalLineToProjectionBoundsSetCull( localPoints[p1], localPoints[p2], pointCull[p1], pointCull[p2], projectionBounds );
2343  culled &= pointCull[p1] & pointCull[p2];
2344  outside |= pointCull[p1] | pointCull[p2];
2345  }
2346 
2347  // if completely culled
2348  if ( culled ) {
2349  return false;
2350  }
2351 
2352  // if completely inside
2353  if ( !outside ) {
2354  return true;
2355  }
2356 
2357  // test remaining winding edges
2358  for ( i = 1; i < winding.GetNumPoints(); i += 2 ) {
2359  p1 = i;
2360  p2 = (i+1)%winding.GetNumPoints();
2361  AddLocalLineToProjectionBoundsUseCull( localPoints[p1], localPoints[p2], pointCull[p1], pointCull[p2], projectionBounds );
2362  }
2363 
2364  // if the winding extends beyond two or more boundaries of this frustum
2365  if ( outside != 1 && outside != 2 && outside != 4 && outside != 8 ) {
2366 
2367  winding.GetPlane( plane );
2368  scaled[0] = axis[0] * dFar;
2369  scaled[1] = axis[1] * dLeft;
2370  scaled[2] = axis[2] * dUp;
2371 
2372  // test the outer edges of this frustum for intersection with the winding
2373  if ( (outside & 2) && (outside & 8) ) {
2374  if ( winding.RayIntersection( plane, origin, scaled[0] - scaled[1] - scaled[2], scale ) ) {
2375  projectionBounds.AddPoint( idVec3( scale * dFar, -1.0f, -1.0f ) );
2376  }
2377  }
2378  if ( (outside & 2) && (outside & 4) ) {
2379  if ( winding.RayIntersection( plane, origin, scaled[0] - scaled[1] + scaled[2], scale ) ) {
2380  projectionBounds.AddPoint( idVec3( scale * dFar, -1.0f, 1.0f ) );
2381  }
2382  }
2383  if ( (outside & 1) && (outside & 8) ) {
2384  if ( winding.RayIntersection( plane, origin, scaled[0] + scaled[1] - scaled[2], scale ) ) {
2385  projectionBounds.AddPoint( idVec3( scale * dFar, 1.0f, -1.0f ) );
2386  }
2387  }
2388  if ( (outside & 1) && (outside & 2) ) {
2389  if ( winding.RayIntersection( plane, origin, scaled[0] + scaled[1] + scaled[2], scale ) ) {
2390  projectionBounds.AddPoint( idVec3( scale * dFar, 1.0f, 1.0f ) );
2391  }
2392  }
2393  }
2394 
2395  return true;
2396 }
2397 
2398 /*
2399 ============
2400 idFrustum::ClipFrustumToBox
2401 
2402  Clips the frustum far extents to the box.
2403 ============
2404 */
2405 void idFrustum::ClipFrustumToBox( const idBox &box, float clipFractions[4], int clipPlanes[4] ) const {
2406  int i, index;
2407  float f, minf;
2408  idMat3 scaled, localAxis, transpose;
2409  idVec3 localOrigin, cornerVecs[4];
2410  idBounds bounds;
2411 
2412  transpose = box.GetAxis();
2413  transpose.TransposeSelf();
2414  localOrigin = ( origin - box.GetCenter() ) * transpose;
2415  localAxis = axis * transpose;
2416 
2417  scaled[0] = localAxis[0] * dFar;
2418  scaled[1] = localAxis[1] * dLeft;
2419  scaled[2] = localAxis[2] * dUp;
2420  cornerVecs[0] = scaled[0] + scaled[1];
2421  cornerVecs[1] = scaled[0] - scaled[1];
2422  cornerVecs[2] = cornerVecs[1] - scaled[2];
2423  cornerVecs[3] = cornerVecs[0] - scaled[2];
2424  cornerVecs[0] += scaled[2];
2425  cornerVecs[1] += scaled[2];
2426 
2427  bounds[0] = -box.GetExtents();
2428  bounds[1] = box.GetExtents();
2429 
2430  minf = ( dNear + 1.0f ) * invFar;
2431 
2432  for ( i = 0; i < 4; i++ ) {
2433 
2434  index = FLOATSIGNBITNOTSET( cornerVecs[i].x );
2435  f = ( bounds[index].x - localOrigin.x ) / cornerVecs[i].x;
2436  clipFractions[i] = f;
2437  clipPlanes[i] = 1 << index;
2438 
2439  index = FLOATSIGNBITNOTSET( cornerVecs[i].y );
2440  f = ( bounds[index].y - localOrigin.y ) / cornerVecs[i].y;
2441  if ( f < clipFractions[i] ) {
2442  clipFractions[i] = f;
2443  clipPlanes[i] = 4 << index;
2444  }
2445 
2446  index = FLOATSIGNBITNOTSET( cornerVecs[i].z );
2447  f = ( bounds[index].z - localOrigin.z ) / cornerVecs[i].z;
2448  if ( f < clipFractions[i] ) {
2449  clipFractions[i] = f;
2450  clipPlanes[i] = 16 << index;
2451  }
2452 
2453  // make sure the frustum is not clipped between the frustum origin and the near plane
2454  if ( clipFractions[i] < minf ) {
2455  clipFractions[i] = minf;
2456  }
2457  }
2458 }
2459 
2460 /*
2461 ============
2462 idFrustum::ClipLine
2463 
2464  Returns true if part of the line is inside the frustum.
2465  Does not clip to the near and far plane.
2466 ============
2467 */
2468 bool idFrustum::ClipLine( const idVec3 localPoints[8], const idVec3 points[8], int startIndex, int endIndex, idVec3 &start, idVec3 &end, int &startClip, int &endClip ) const {
2469  float d1, d2, fstart, fend, lstart, lend, f, x;
2470  float leftScale, upScale;
2471  float scale1, scale2;
2472  int startCull, endCull;
2473  idVec3 localStart, localEnd, localDir;
2474 
2475  leftScale = dLeft * invFar;
2476  upScale = dUp * invFar;
2477 
2478  localStart = localPoints[startIndex];
2479  localEnd = localPoints[endIndex];
2480  localDir = localEnd - localStart;
2481 
2482  startClip = endClip = -1;
2483  scale1 = idMath::INFINITY;
2484  scale2 = -idMath::INFINITY;
2485 
2486  fstart = dFar * localStart.y;
2487  fend = dFar * localEnd.y;
2488  lstart = dLeft * localStart.x;
2489  lend = dLeft * localEnd.x;
2490 
2491  // test left plane
2492  d1 = -fstart + lstart;
2493  d2 = -fend + lend;
2494  startCull = FLOATSIGNBITSET( d1 );
2495  endCull = FLOATSIGNBITSET( d2 );
2496  if ( FLOATNOTZERO( d1 ) ) {
2497  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
2498  f = d1 / ( d1 - d2 );
2499  x = localStart.x + f * localDir.x;
2500  if ( x >= 0.0f ) {
2501  if ( idMath::Fabs( localStart.z + f * localDir.z ) <= x * upScale ) {
2502  if ( f < scale1 ) { scale1 = f; startClip = 0; }
2503  if ( f > scale2 ) { scale2 = f; endClip = 0; }
2504  }
2505  }
2506  }
2507  }
2508 
2509  // test right plane
2510  d1 = fstart + lstart;
2511  d2 = fend + lend;
2512  startCull |= FLOATSIGNBITSET( d1 ) << 1;
2513  endCull |= FLOATSIGNBITSET( d2 ) << 1;
2514  if ( FLOATNOTZERO( d1 ) ) {
2515  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
2516  f = d1 / ( d1 - d2 );
2517  x = localStart.x + f * localDir.x;
2518  if ( x >= 0.0f ) {
2519  if ( idMath::Fabs( localStart.z + f * localDir.z ) <= x * upScale ) {
2520  if ( f < scale1 ) { scale1 = f; startClip = 1; }
2521  if ( f > scale2 ) { scale2 = f; endClip = 1; }
2522  }
2523  }
2524  }
2525  }
2526 
2527  fstart = dFar * localStart.z;
2528  fend = dFar * localEnd.z;
2529  lstart = dUp * localStart.x;
2530  lend = dUp * localEnd.x;
2531 
2532  // test up plane
2533  d1 = -fstart + lstart;
2534  d2 = -fend + lend;
2535  startCull |= FLOATSIGNBITSET( d1 ) << 2;
2536  endCull |= FLOATSIGNBITSET( d2 ) << 2;
2537  if ( FLOATNOTZERO( d1 ) ) {
2538  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
2539  f = d1 / ( d1 - d2 );
2540  x = localStart.x + f * localDir.x;
2541  if ( x >= 0.0f ) {
2542  if ( idMath::Fabs( localStart.y + f * localDir.y ) <= x * leftScale ) {
2543  if ( f < scale1 ) { scale1 = f; startClip = 2; }
2544  if ( f > scale2 ) { scale2 = f; endClip = 2; }
2545  }
2546  }
2547  }
2548  }
2549 
2550  // test down plane
2551  d1 = fstart + lstart;
2552  d2 = fend + lend;
2553  startCull |= FLOATSIGNBITSET( d1 ) << 3;
2554  endCull |= FLOATSIGNBITSET( d2 ) << 3;
2555  if ( FLOATNOTZERO( d1 ) ) {
2556  if ( FLOATSIGNBITSET( d1 ) ^ FLOATSIGNBITSET( d2 ) ) {
2557  f = d1 / ( d1 - d2 );
2558  x = localStart.x + f * localDir.x;
2559  if ( x >= 0.0f ) {
2560  if ( idMath::Fabs( localStart.y + f * localDir.y ) <= x * leftScale ) {
2561  if ( f < scale1 ) { scale1 = f; startClip = 3; }
2562  if ( f > scale2 ) { scale2 = f; endClip = 3; }
2563  }
2564  }
2565  }
2566  }
2567 
2568  // if completely inside
2569  if ( !( startCull | endCull ) ) {
2570  start = points[startIndex];
2571  end = points[endIndex];
2572  return true;
2573  }
2574  else if ( scale1 <= scale2 ) {
2575  if ( !startCull ) {
2576  start = points[startIndex];
2577  startClip = -1;
2578  }
2579  else {
2580  start = points[startIndex] + scale1 * ( points[endIndex] - points[startIndex] );
2581  }
2582  if ( !endCull ) {
2583  end = points[endIndex];
2584  endClip = -1;
2585  }
2586  else {
2587  end = points[startIndex] + scale2 * ( points[endIndex] - points[startIndex] );
2588  }
2589  return true;
2590  }
2591  return false;
2592 }
2593 
2594 /*
2595 ============
2596 idFrustum::AddLocalCapsToProjectionBounds
2597 ============
2598 */
2599 static int capPointIndex[4][2] = {
2600  { 0, 3 },
2601  { 1, 2 },
2602  { 0, 1 },
2603  { 2, 3 }
2604 };
2605 
2606 ID_INLINE bool idFrustum::AddLocalCapsToProjectionBounds( const idVec3 endPoints[4], const int endPointCull[4], const idVec3 &point, int pointCull, int pointClip, idBounds &projectionBounds ) const {
2607  int *p;
2608 
2609  if ( pointClip < 0 ) {
2610  return false;
2611  }
2612  p = capPointIndex[pointClip];
2613  AddLocalLineToProjectionBoundsUseCull( endPoints[p[0]], point, endPointCull[p[0]], pointCull, projectionBounds );
2614  AddLocalLineToProjectionBoundsUseCull( endPoints[p[1]], point, endPointCull[p[1]], pointCull, projectionBounds );
2615  return true;
2616 }
2617 
2618 /*
2619 ============
2620 idFrustum::ClippedProjectionBounds
2621 ============
2622 */
2623 bool idFrustum::ClippedProjectionBounds( const idFrustum &frustum, const idBox &clipBox, idBounds &projectionBounds ) const {
2624  int i, p1, p2, clipPointCull[8], clipPlanes[4], usedClipPlanes, nearCull, farCull, outside;
2625  int pointCull[2], startClip, endClip, boxPointCull[8];
2626  float clipFractions[4], s1, s2, t1, t2, leftScale, upScale;
2627  idFrustum localFrustum;
2628  idVec3 clipPoints[8], localPoints1[8], localPoints2[8], localOrigin1, localOrigin2, start, end;
2629  idMat3 localAxis1, localAxis2, transpose;
2630  idBounds clipBounds;
2631 
2632  // if the frustum origin is inside the other frustum
2633  if ( frustum.ContainsPoint( origin ) ) {
2634  // bounds that cover the whole frustum
2635  float clipBoxMin, clipBoxMax, frustumMin, frustumMax, base;
2636 
2637  base = origin * axis[0];
2638  clipBox.AxisProjection( axis[0], clipBoxMin, clipBoxMax );
2639  frustum.AxisProjection( axis[0], frustumMin, frustumMax );
2640 
2641  projectionBounds[0].x = Max( clipBoxMin, frustumMin ) - base;
2642  projectionBounds[1].x = Min( clipBoxMax, frustumMax ) - base;
2643  projectionBounds[0].y = projectionBounds[0].z = -1.0f;
2644  projectionBounds[1].y = projectionBounds[1].z = 1.0f;
2645  return true;
2646  }
2647 
2648  projectionBounds.Clear();
2649 
2650  // clip the outer edges of the given frustum to the clip bounds
2651  frustum.ClipFrustumToBox( clipBox, clipFractions, clipPlanes );
2652  usedClipPlanes = clipPlanes[0] | clipPlanes[1] | clipPlanes[2] | clipPlanes[3];
2653 
2654  // transform the clipped frustum to the space of this frustum
2655  transpose = axis;
2656  transpose.TransposeSelf();
2657  localFrustum = frustum;
2658  localFrustum.origin = ( frustum.origin - origin ) * transpose;
2659  localFrustum.axis = frustum.axis * transpose;
2660  localFrustum.ToClippedPoints( clipFractions, clipPoints );
2661 
2662  // test outer four edges of the clipped frustum
2663  for ( i = 0; i < 4; i++ ) {
2664  p1 = i;
2665  p2 = 4 + i;
2666  AddLocalLineToProjectionBoundsSetCull( clipPoints[p1], clipPoints[p2], clipPointCull[p1], clipPointCull[p2], projectionBounds );
2667  }
2668 
2669  // get cull bits for the clipped frustum
2670  outside = clipPointCull[0] | clipPointCull[1] | clipPointCull[2] | clipPointCull[3] |
2671  clipPointCull[4] | clipPointCull[5] | clipPointCull[6] | clipPointCull[7];
2672  nearCull = clipPointCull[0] & clipPointCull[1] & clipPointCull[2] & clipPointCull[3];
2673  farCull = clipPointCull[4] & clipPointCull[5] & clipPointCull[6] & clipPointCull[7];
2674 
2675  // if the clipped frustum is not completely inside this frustum
2676  if ( outside ) {
2677 
2678  // test the remaining edges of the clipped frustum
2679  if ( !nearCull && localFrustum.dNear > 0.0f ) {
2680  for ( i = 0; i < 4; i++ ) {
2681  p1 = i;
2682  p2 = (i+1)&3;
2683  AddLocalLineToProjectionBoundsUseCull( clipPoints[p1], clipPoints[p2], clipPointCull[p1], clipPointCull[p2], projectionBounds );
2684  }
2685  }
2686 
2687  if ( !farCull ) {
2688  for ( i = 0; i < 4; i++ ) {
2689  p1 = 4 + i;
2690  p2 = 4 + ((i+1)&3);
2691  AddLocalLineToProjectionBoundsUseCull( clipPoints[p1], clipPoints[p2], clipPointCull[p1], clipPointCull[p2], projectionBounds );
2692  }
2693  }
2694  }
2695 
2696  // if the clipped frustum far end points are inside this frustum
2697  if ( !( farCull && !( nearCull & farCull ) ) &&
2698  // if the clipped frustum is not clipped to a single plane of the clip bounds
2699  ( clipPlanes[0] != clipPlanes[1] || clipPlanes[1] != clipPlanes[2] || clipPlanes[2] != clipPlanes[3] ) ) {
2700 
2701  // transform the clip box into the space of the other frustum
2702  transpose = frustum.axis;
2703  transpose.TransposeSelf();
2704  localOrigin1 = ( clipBox.GetCenter() - frustum.origin ) * transpose;
2705  localAxis1 = clipBox.GetAxis() * transpose;
2706  BoxToPoints( localOrigin1, clipBox.GetExtents(), localAxis1, localPoints1 );
2707 
2708  // cull the box corners with the other frustum
2709  leftScale = frustum.dLeft * frustum.invFar;
2710  upScale = frustum.dUp * frustum.invFar;
2711  for ( i = 0; i < 8; i++ ) {
2712  idVec3 &p = localPoints1[i];
2713  if ( !( boxVertPlanes[i] & usedClipPlanes ) || p.x <= 0.0f ) {
2714  boxPointCull[i] = 1|2|4|8;
2715  }
2716  else {
2717  boxPointCull[i] = 0;
2718  if ( idMath::Fabs( p.y ) > p.x * leftScale ) {
2719  boxPointCull[i] |= 1 << FLOATSIGNBITSET( p.y );
2720  }
2721  if ( idMath::Fabs( p.z ) > p.x * upScale ) {
2722  boxPointCull[i] |= 4 << FLOATSIGNBITSET( p.z );
2723  }
2724  }
2725  }
2726 
2727  // transform the clip box into the space of this frustum
2728  transpose = axis;
2729  transpose.TransposeSelf();
2730  localOrigin2 = ( clipBox.GetCenter() - origin ) * transpose;
2731  localAxis2 = clipBox.GetAxis() * transpose;
2732  BoxToPoints( localOrigin2, clipBox.GetExtents(), localAxis2, localPoints2 );
2733 
2734  // clip the edges of the clip bounds to the other frustum and add the clipped edges to the projection bounds
2735  for ( i = 0; i < 4; i++ ) {
2736  p1 = i;
2737  p2 = 4 + i;
2738  if ( !( boxPointCull[p1] & boxPointCull[p2] ) ) {
2739  if ( frustum.ClipLine( localPoints1, localPoints2, p1, p2, start, end, startClip, endClip ) ) {
2740  AddLocalLineToProjectionBoundsSetCull( start, end, pointCull[0], pointCull[1], projectionBounds );
2741  AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, start, pointCull[0], startClip, projectionBounds );
2742  AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, end, pointCull[1], endClip, projectionBounds );
2743  outside |= pointCull[0] | pointCull[1];
2744  }
2745  }
2746  }
2747 
2748  for ( i = 0; i < 4; i++ ) {
2749  p1 = i;
2750  p2 = (i+1)&3;
2751  if ( !( boxPointCull[p1] & boxPointCull[p2] ) ) {
2752  if ( frustum.ClipLine( localPoints1, localPoints2, p1, p2, start, end, startClip, endClip ) ) {
2753  AddLocalLineToProjectionBoundsSetCull( start, end, pointCull[0], pointCull[1], projectionBounds );
2754  AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, start, pointCull[0], startClip, projectionBounds );
2755  AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, end, pointCull[1], endClip, projectionBounds );
2756  outside |= pointCull[0] | pointCull[1];
2757  }
2758  }
2759  }
2760 
2761  for ( i = 0; i < 4; i++ ) {
2762  p1 = 4 + i;
2763  p2 = 4 + ((i+1)&3);
2764  if ( !( boxPointCull[p1] & boxPointCull[p2] ) ) {
2765  if ( frustum.ClipLine( localPoints1, localPoints2, p1, p2, start, end, startClip, endClip ) ) {
2766  AddLocalLineToProjectionBoundsSetCull( start, end, pointCull[0], pointCull[1], projectionBounds );
2767  AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, start, pointCull[0], startClip, projectionBounds );
2768  AddLocalCapsToProjectionBounds( clipPoints+4, clipPointCull+4, end, pointCull[1], endClip, projectionBounds );
2769  outside |= pointCull[0] | pointCull[1];
2770  }
2771  }
2772  }
2773  }
2774 
2775  // if the clipped frustum extends beyond two or more boundaries of this frustum
2776  if ( outside != 1 && outside != 2 && outside != 4 && outside != 8 ) {
2777 
2778  // transform this frustum into the space of the other frustum
2779  transpose = frustum.axis;
2780  transpose.TransposeSelf();
2781  localOrigin1 = ( origin - frustum.origin ) * transpose;
2782  localAxis1 = axis * transpose;
2783  localAxis1[0] *= dFar;
2784  localAxis1[1] *= dLeft;
2785  localAxis1[2] *= dUp;
2786 
2787  // transform this frustum into the space of the clip bounds
2788  transpose = clipBox.GetAxis();
2789  transpose.TransposeSelf();
2790  localOrigin2 = ( origin - clipBox.GetCenter() ) * transpose;
2791  localAxis2 = axis * transpose;
2792  localAxis2[0] *= dFar;
2793  localAxis2[1] *= dLeft;
2794  localAxis2[2] *= dUp;
2795 
2796  clipBounds[0] = -clipBox.GetExtents();
2797  clipBounds[1] = clipBox.GetExtents();
2798 
2799  // test the outer edges of this frustum for intersection with both the other frustum and the clip bounds
2800  if ( (outside & 2) && (outside & 8) ) {
2801  frustum.LocalRayIntersection( localOrigin1, localAxis1[0] - localAxis1[1] - localAxis1[2], s1, s2 );
2802  if ( s1 <= s2 && s1 >= 0.0f ) {
2803  BoundsRayIntersection( clipBounds, localOrigin2, localAxis2[0] - localAxis2[1] - localAxis2[2], t1, t2 );
2804  if ( t1 <= t2 && t2 > s1 && t1 < s2 ) {
2805  projectionBounds.AddPoint( idVec3( s1 * dFar, -1.0f, -1.0f ) );
2806  projectionBounds.AddPoint( idVec3( s2 * dFar, -1.0f, -1.0f ) );
2807  }
2808  }
2809  }
2810  if ( (outside & 2) && (outside & 4) ) {
2811  frustum.LocalRayIntersection( localOrigin1, localAxis1[0] - localAxis1[1] + localAxis1[2], s1, s2 );
2812  if ( s1 <= s2 && s1 >= 0.0f ) {
2813  BoundsRayIntersection( clipBounds, localOrigin2, localAxis2[0] - localAxis2[1] + localAxis2[2], t1, t2 );
2814  if ( t1 <= t2 && t2 > s1 && t1 < s2 ) {
2815  projectionBounds.AddPoint( idVec3( s1 * dFar, -1.0f, 1.0f ) );
2816  projectionBounds.AddPoint( idVec3( s2 * dFar, -1.0f, 1.0f ) );
2817  }
2818  }
2819  }
2820  if ( (outside & 1) && (outside & 8) ) {
2821  frustum.LocalRayIntersection( localOrigin1, localAxis1[0] + localAxis1[1] - localAxis1[2], s1, s2 );
2822  if ( s1 <= s2 && s1 >= 0.0f ) {
2823  BoundsRayIntersection( clipBounds, localOrigin2, localAxis2[0] + localAxis2[1] - localAxis2[2], t1, t2 );
2824  if ( t1 <= t2 && t2 > s1 && t1 < s2 ) {
2825  projectionBounds.AddPoint( idVec3( s1 * dFar, 1.0f, -1.0f ) );
2826  projectionBounds.AddPoint( idVec3( s2 * dFar, 1.0f, -1.0f ) );
2827  }
2828  }
2829  }
2830  if ( (outside & 1) && (outside & 2) ) {
2831  frustum.LocalRayIntersection( localOrigin1, localAxis1[0] + localAxis1[1] + localAxis1[2], s1, s2 );
2832  if ( s1 <= s2 && s1 >= 0.0f ) {
2833  BoundsRayIntersection( clipBounds, localOrigin2, localAxis2[0] + localAxis2[1] + localAxis2[2], t1, t2 );
2834  if ( t1 <= t2 && t2 > s1 && t1 < s2 ) {
2835  projectionBounds.AddPoint( idVec3( s1 * dFar, 1.0f, 1.0f ) );
2836  projectionBounds.AddPoint( idVec3( s2 * dFar, 1.0f, 1.0f ) );
2837  }
2838  }
2839  }
2840  }
2841 
2842  return true;
2843 }
idFrustum::AxisProjection
void AxisProjection(const idVec3 &dir, float &min, float &max) const
Definition: Frustum.cpp:1684
idFrustum::PlaneDistance
float PlaneDistance(const idPlane &plane) const
Definition: Frustum.cpp:84
idMath::ATan16
static float ATan16(float a)
Definition: Math.h:583
idFrustum::CullSphere
bool CullSphere(const idSphere &sphere) const
Definition: Frustum.cpp:263
idFrustum::dNear
float dNear
Definition: Frustum.h:120
idFrustum::ConstrainToBox
bool ConstrainToBox(const idBox &box)
Definition: Frustum.cpp:1434
points
GLsizei const GLfloat * points
Definition: glext.h:3884
idSphere::GetOrigin
const idVec3 & GetOrigin(void) const
Definition: Sphere.h:165
idMath::INFINITY
static const float INFINITY
Definition: Math.h:218
idVec3::ToMat3
idMat3 ToMat3(void) const
Definition: Vector.cpp:195
min
#define min(a, b)
value
GLsizei const GLfloat * value
Definition: glext.h:3614
idVec3::Normalize
float Normalize(void)
Definition: Vector.h:646
colorGreen
idVec4 colorGreen
Definition: Lib.cpp:118
assert
assert(prefInfo.fullscreenBtn)
idPlane::Normal
const idVec3 & Normal(void) const
Definition: Plane.h:239
mat3_identity
idMat3 mat3_identity(idVec3(1, 0, 0), idVec3(0, 1, 0), idVec3(0, 0, 1))
idFrustum::ToIndexPointsAndCornerVecs
void ToIndexPointsAndCornerVecs(idVec3 indexPoints[8], idVec3 cornerVecs[4]) const
Definition: Frustum.cpp:1623
idFrustum::CullFrustum
bool CullFrustum(const idFrustum &frustum) const
Definition: Frustum.cpp:395
idFrustum::ToPoints
void ToPoints(idVec3 points[8]) const
Definition: Frustum.cpp:1523
idFrustum::LocalRayIntersection
bool LocalRayIntersection(const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2) const
Definition: Frustum.cpp:674
idWinding::LineIntersection
bool LineIntersection(const idPlane &windingPlane, const idVec3 &start, const idVec3 &end, bool backFaceCull=false) const
Definition: Winding.cpp:1379
idFrustum::LocalLineIntersection
bool LocalLineIntersection(const idVec3 &start, const idVec3 &end) const
Definition: Frustum.cpp:547
FLOATNOTZERO
#define FLOATNOTZERO(f)
Definition: Math.h:70
idBox::GetExtents
const idVec3 & GetExtents(void) const
Definition: Box.h:217
idFrustum::ClipFrustumToBox
void ClipFrustumToBox(const idBox &box, float clipFractions[4], int clipPlanes[4]) const
Definition: Frustum.cpp:2405
idMath::Tan16
static float Tan16(float a)
Definition: Math.h:463
idFrustum::invFar
float invFar
Definition: Frustum.h:124
Max
ID_INLINE T Max(T x, T y)
Definition: Lib.h:158
idFrustum::AddLocalLineToProjectionBoundsUseCull
void AddLocalLineToProjectionBoundsUseCull(const idVec3 &start, const idVec3 &end, int startCull, int endCull, idBounds &bounds) const
Definition: Frustum.cpp:1851
idFrustum::MoveFarDistance
void MoveFarDistance(float dFar)
Definition: Frustum.h:183
scale
GLenum GLenum GLenum GLenum GLenum scale
Definition: glext.h:4804
idMat3::Transpose
idMat3 Transpose(void) const
Definition: Matrix.h:677
y
GLenum GLint GLint y
Definition: glext.h:2849
idFrustum::IntersectsBounds
bool IntersectsBounds(const idBounds &bounds) const
Definition: Frustum.cpp:864
idFrustum::ConstrainToBounds
bool ConstrainToBounds(const idBounds &bounds)
Definition: Frustum.cpp:1414
idVec3::z
float z
Definition: Vector.h:320
int
case const int
Definition: Callbacks.cpp:52
idFrustum::ToPlanes
void ToPlanes(idPlane planes[6]) const
Definition: Frustum.cpp:1494
idFrustum::LineIntersection
bool LineIntersection(const idVec3 &start, const idVec3 &end) const
Definition: Frustum.cpp:1174
idVec3
Definition: Vector.h:316
idMath::Sqrt
static float Sqrt(float x)
Definition: Math.h:302
idBounds::Clear
void Clear(void)
Definition: Bounds.h:201
s
GLdouble s
Definition: glext.h:2935
idVec3::Cross
idVec3 Cross(const idVec3 &a) const
Definition: Vector.h:619
idVec3::x
float x
Definition: Vector.h:318
idFrustum::CullLocalBox
bool CullLocalBox(const idVec3 &localOrigin, const idVec3 &extents, const idMat3 &localAxis) const
Definition: Frustum.cpp:150
x
GLenum GLint x
Definition: glext.h:2849
process.i
int i
Definition: process.py:33
idFrustum::AddLocalLineToProjectionBoundsSetCull
void AddLocalLineToProjectionBoundsSetCull(const idVec3 &start, const idVec3 &end, int &startCull, int &endCull, idBounds &bounds) const
Definition: Frustum.cpp:1712
idFrustum::AddLocalCapsToProjectionBounds
bool AddLocalCapsToProjectionBounds(const idVec3 endPoints[4], const int endPointCull[4], const idVec3 &point, int pointCull, int pointClip, idBounds &projectionBounds) const
Definition: Frustum.cpp:2606
idFrustum::ProjectionBounds
bool ProjectionBounds(const idBounds &bounds, idBounds &projectionBounds) const
Definition: Frustum.cpp:2043
idSphere::ContainsPoint
bool ContainsPoint(const idVec3 &p) const
Definition: Sphere.h:231
idFrustum::CullLocalWinding
bool CullLocalWinding(const idVec3 *points, const int numPoints, int *pointCull) const
Definition: Frustum.cpp:414
CVAR_RENDERER
Definition: CVarSystem.h:88
idFrustum::CullBox
bool CullBox(const idBox &box) const
Definition: Frustum.cpp:242
idFrustum::ContainsPoint
bool ContainsPoint(const idVec3 &point) const
Definition: Frustum.cpp:795
PLANESIDE_FRONT
#define PLANESIDE_FRONT
Definition: Plane.h:53
idFrustum::ClipLine
bool ClipLine(const idVec3 localPoints[8], const idVec3 points[8], int startIndex, int endIndex, idVec3 &start, idVec3 &end, int &startClip, int &endClip) const
Definition: Frustum.cpp:2468
idBounds::AddPoint
bool AddPoint(const idVec3 &v)
Definition: Bounds.h:226
idSession::rw
idRenderWorld * rw
Definition: Session.h:153
idFrustum::IntersectsBox
bool IntersectsBox(const idBox &box) const
Definition: Frustum.cpp:907
idFrustum::LocalFrustumIntersectsFrustum
bool LocalFrustumIntersectsFrustum(const idVec3 points[8], const bool testFirstSide) const
Definition: Frustum.cpp:804
FLOATSIGNBITSET
#define FLOATSIGNBITSET(f)
Definition: Math.h:68
idRenderWorld::DebugLine
virtual void DebugLine(const idVec4 &color, const idVec3 &start, const idVec3 &end, const int lifetime=0, const bool depthTest=false)=0
idWinding::GetNumPoints
int GetNumPoints(void) const
Definition: Winding.h:238
index
GLuint index
Definition: glext.h:3476
idPlane::SetDist
void SetDist(const float dist)
Definition: Plane.h:275
vec3_origin
idVec3 vec3_origin(0.0f, 0.0f, 0.0f)
end
GLuint GLuint end
Definition: glext.h:2845
idMath::Fabs
static float Fabs(float f)
Definition: Math.h:779
idSphere::GetRadius
float GetRadius(void) const
Definition: Sphere.h:169
idFrustum::PlaneSide
int PlaneSide(const idPlane &plane, const float epsilon=ON_EPSILON) const
Definition: Frustum.cpp:102
idFrustum::CullWinding
bool CullWinding(const class idWinding &winding) const
Definition: Frustum.cpp:449
PLANESIDE_BACK
#define PLANESIDE_BACK
Definition: Plane.h:54
idFrustum::IntersectsWinding
bool IntersectsWinding(const idWinding &winding) const
Definition: Frustum.cpp:1102
idVec3::y
float y
Definition: Vector.h:319
idFrustum::dLeft
float dLeft
Definition: Frustum.h:122
idCVar::GetInteger
int GetInteger(void) const
Definition: CVarSystem.h:143
idWinding::GetPlane
void GetPlane(idVec3 &normal, float &dist) const
Definition: Winding.cpp:656
idPlane
Definition: Plane.h:71
idFrustum::LocalFrustumIntersectsBounds
bool LocalFrustumIntersectsBounds(const idVec3 points[8], const idBounds &bounds) const
Definition: Frustum.cpp:834
CVAR_INTEGER
Definition: CVarSystem.h:85
idFrustum::ToClippedPoints
void ToClippedPoints(const float fractions[4], idVec3 points[8]) const
Definition: Frustum.cpp:1554
idSphere::LineIntersection
bool LineIntersection(const idVec3 &start, const idVec3 &end) const
Definition: Sphere.cpp:79
idPlane::Normalize
float Normalize(bool fixDegenerate=true)
Definition: Plane.h:247
idBox::GetAxis
const idMat3 & GetAxis(void) const
Definition: Box.h:221
idSwap
ID_INLINE void idSwap(type &a, type &b)
Definition: List.h:77
transpose
GLsizei GLboolean transpose
Definition: glext.h:3622
idFrustum::dUp
float dUp
Definition: Frustum.h:123
idFrustum::ToIndexPoints
void ToIndexPoints(idVec3 indexPoints[8]) const
Definition: Frustum.cpp:1590
r_showInteractionScissors
idCVar r_showInteractionScissors("r_showInteractionScissors","0", CVAR_RENDERER|CVAR_INTEGER,"1 = show screen rectangle which contains the interaction frustum, 2 = also draw construction lines", 0, 2, idCmdSystem::ArgCompletion_Integer< 0, 2 >)
VORONOI_INDEX
#define VORONOI_INDEX(x, y, z)
Definition: Frustum.cpp:953
idBox::GetCenter
const idVec3 & GetCenter(void) const
Definition: Box.h:213
b
GLubyte GLubyte b
Definition: glext.h:4662
r
GLdouble GLdouble GLdouble r
Definition: glext.h:2951
idFrustum::ClippedProjectionBounds
bool ClippedProjectionBounds(const idFrustum &frustum, const idBox &clipBox, idBounds &projectionBounds) const
Definition: Frustum.cpp:2623
idMat3
Definition: Matrix.h:333
idFrustum::ConstrainToSphere
bool ConstrainToSphere(const idSphere &sphere)
Definition: Frustum.cpp:1454
idBounds::LineIntersection
bool LineIntersection(const idVec3 &start, const idVec3 &end) const
Definition: Bounds.cpp:135
idal.f
tuple f
Definition: idal.py:89
FLOATSIGNBITNOTSET
#define FLOATSIGNBITNOTSET(f)
Definition: Math.h:69
idFrustum::FromProjection
bool FromProjection(const idBounds &bounds, const idVec3 &projectionOrigin, const float dFar)
Definition: Frustum.cpp:1204
idFrustum::dFar
float dFar
Definition: Frustum.h:121
idFrustum::IntersectsFrustum
bool IntersectsFrustum(const idFrustum &frustum) const
Definition: Frustum.cpp:1055
idFrustum::CullBounds
bool CullBounds(const idBounds &bounds) const
Definition: Frustum.cpp:218
idFrustum::origin
idVec3 origin
Definition: Frustum.h:118
idFrustum::CullLocalFrustum
bool CullLocalFrustum(const idFrustum &localFrustum, const idVec3 indexPoints[8], const idVec3 cornerVecs[4]) const
Definition: Frustum.cpp:308
idFrustum::BoundsRayIntersection
bool BoundsRayIntersection(const idBounds &bounds, const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2) const
Definition: Frustum.cpp:1978
idFrustum::RayIntersection
bool RayIntersection(const idVec3 &start, const idVec3 &dir, float &scale1, float &scale2) const
Definition: Frustum.cpp:1187
idBounds::AxisProjection
void AxisProjection(const idVec3 &dir, float &min, float &max) const
Definition: Bounds.h:376
idSphere::AxisProjection
void AxisProjection(const idVec3 &dir, float &min, float &max) const
Definition: Sphere.h:268
PLANESIDE_CROSS
#define PLANESIDE_CROSS
Definition: Plane.h:56
BoxToPoints
void BoxToPoints(const idVec3 &center, const idVec3 &extents, const idMat3 &axis, idVec3 points[8])
Definition: Frustum.cpp:58
j
GLint j
Definition: qgl.h:264
session
idSession * session
Definition: Session.cpp:48
idFrustum::ConstrainToFrustum
bool ConstrainToFrustum(const idFrustum &frustum)
Definition: Frustum.cpp:1474
max
#define max(x, y)
Definition: os.h:70
p
GLfloat GLfloat p
Definition: glext.h:4674
z
GLdouble GLdouble z
Definition: glext.h:3067
idVec3::Zero
void Zero(void)
Definition: Vector.h:415
Min
ID_INLINE T Min(T x, T y)
Definition: Lib.h:159
idWinding::RayIntersection
bool RayIntersection(const idPlane &windingPlane, const idVec3 &start, const idVec3 &dir, float &scale, bool backFaceCull=false) const
Definition: Winding.cpp:1419
idBox
Definition: Box.h:40
idFrustum::CullPoint
bool CullPoint(const idVec3 &point) const
Definition: Frustum.cpp:120
start
GLuint start
Definition: glext.h:2845
idBox::AxisProjection
void AxisProjection(const idVec3 &dir, float &min, float &max) const
Definition: Box.h:277
idFrustum::IntersectsSphere
bool IntersectsSphere(const idSphere &sphere) const
Definition: Frustum.cpp:955
idMat3::TransposeSelf
idMat3 & TransposeSelf(void)
Definition: Matrix.h:683
idPlane::FitThroughPoint
void FitThroughPoint(const idVec3 &p)
Definition: Plane.h:297
idFrustum::axis
idMat3 axis
Definition: Frustum.h:119
idFrustum::BoundsCullLocalFrustum
bool BoundsCullLocalFrustum(const idBounds &bounds, const idFrustum &localFrustum, const idVec3 indexPoints[8], const idVec3 cornerVecs[4]) const
Definition: Frustum.cpp:472
This page is maintained by Wladimir van der Laan. Generated on Mon Nov 17 2014 12:23:21 for doom3-gpl by doxygen 1.8.6.