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