1 /*
2 Copyright (C) 1997-2001 Id Software, Inc.
3
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License
6 as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
13 See the GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18 */
19
20 //
21 // cm_q2_main.c
22 // Quake2 BSP map model tracing
23 //
24
25 #include "cm_q2_local.h"
26
27 static int cm_q2_checkCount;
28 static int cm_q2_floodValid;
29
30 static cBspPlane_t *cm_q2_boxPlanes;
31 static int cm_q2_boxHeadNode;
32 static cQ2BspBrush_t *cm_q2_boxBrush;
33 static cQ2BspLeaf_t *cm_q2_boxLeaf;
34
35 static int cm_q2_leafCount, cm_q2_leafMaxCount;
36 static int *cm_q2_leafList;
37 static float *cm_q2_leafMins, *cm_q2_leafMaxs;
38 static int cm_q2_leafTopNode;
39
40 // 1/32 epsilon to keep floating point happy
41 #define DIST_EPSILON (0.03125f)
42
43 static trace_t cm_q2_currentTrace;
44 static vec3_t cm_q2_traceStart, cm_q2_traceEnd;
45 static vec3_t cm_q2_traceMins, cm_q2_traceMaxs;
46 static vec3_t cm_q2_traceExtents;
47 static int cm_q2_traceContents;
48 static qBool cm_q2_traceIsPoint; // optimized case
49
50 /*
51 =============================================================================
52
53 TRACING
54
55 =============================================================================
56 */
57
58 /*
59 ==================
60 CM_Q2BSP_LeafArea
61 ==================
62 */
CM_Q2BSP_LeafArea(int leafNum)63 int CM_Q2BSP_LeafArea (int leafNum)
64 {
65 if (leafNum < 0 || leafNum >= cm_q2_numLeafs)
66 Com_Error (ERR_DROP, "CM_Q2BSP_LeafArea: bad number");
67
68 return cm_q2_leafs[leafNum].area;
69 }
70
71
72 /*
73 ==================
74 CM_Q2BSP_LeafCluster
75 ==================
76 */
CM_Q2BSP_LeafCluster(int leafNum)77 int CM_Q2BSP_LeafCluster (int leafNum)
78 {
79 if (leafNum < 0 || leafNum >= cm_q2_numLeafs)
80 Com_Error (ERR_DROP, "CM_Q2BSP_LeafCluster: bad number");
81
82 return cm_q2_leafs[leafNum].cluster;
83 }
84
85
86 /*
87 ==================
88 CM_Q2BSP_LeafContents
89 ==================
90 */
CM_Q2BSP_LeafContents(int leafNum)91 int CM_Q2BSP_LeafContents (int leafNum)
92 {
93 if (leafNum < 0 || leafNum >= cm_q2_numLeafs)
94 Com_Error (ERR_DROP, "CM_Q2BSP_LeafContents: bad number");
95
96 return cm_q2_leafs[leafNum].contents;
97 }
98
99 // ==========================================================================
100
101 /*
102 ===================
103 CM_Q2BSP_InitBoxHull
104
105 Set up the planes and nodes so that the six floats of a bounding box
106 can just be stored out and get a proper clipping hull structure.
107 ===================
108 */
CM_Q2BSP_InitBoxHull(void)109 void CM_Q2BSP_InitBoxHull (void)
110 {
111 int i;
112 int side;
113 cQ2BspNode_t *c;
114 cBspPlane_t *p;
115 cQ2BspBrushSide_t *s;
116
117 cm_q2_boxHeadNode = cm_q2_numNodes;
118 cm_q2_boxPlanes = &cm_q2_planes[cm_q2_numPlanes];
119 if (cm_q2_numNodes+6 > Q2BSP_MAX_NODES
120 || cm_q2_numBrushes+1 > Q2BSP_MAX_BRUSHES
121 || cm_q2_numLeafBrushes+1 > Q2BSP_MAX_LEAFBRUSHES
122 || cm_q2_numBrushSides+6 > Q2BSP_MAX_BRUSHSIDES
123 || cm_q2_numPlanes+12 > Q2BSP_MAX_PLANES)
124 Com_Error (ERR_DROP, "CM_Q2BSP_InitBoxHull: Not enough room for box tree");
125
126 cm_q2_boxBrush = &cm_q2_brushes[cm_q2_numBrushes];
127 cm_q2_boxBrush->numSides = 6;
128 cm_q2_boxBrush->firstBrushSide = cm_q2_numBrushSides;
129 cm_q2_boxBrush->contents = CONTENTS_MONSTER;
130
131 cm_q2_boxLeaf = &cm_q2_leafs[cm_q2_numLeafs];
132 cm_q2_boxLeaf->contents = CONTENTS_MONSTER;
133 cm_q2_boxLeaf->firstLeafBrush = cm_q2_numLeafBrushes;
134 cm_q2_boxLeaf->numLeafBrushes = 1;
135
136 cm_q2_leafBrushes[cm_q2_numLeafBrushes] = cm_q2_numBrushes;
137
138 for (i=0 ; i<6 ; i++) {
139 side = i&1;
140
141 // Brush sides
142 s = &cm_q2_brushSides[cm_q2_numBrushSides+i];
143 s->plane = cm_q2_planes + (cm_q2_numPlanes+i*2+side);
144 s->surface = &cm_q2_nullSurface;
145
146 // Nodes
147 c = &cm_q2_nodes[cm_q2_boxHeadNode+i];
148 c->plane = cm_q2_planes + (cm_q2_numPlanes+i*2);
149 c->children[side] = -1 - cm_q2_emptyLeaf;
150 if (i != 5)
151 c->children[side^1] = cm_q2_boxHeadNode+i + 1;
152 else
153 c->children[side^1] = -1 - cm_q2_numLeafs;
154
155 // Planes
156 p = &cm_q2_boxPlanes[i*2];
157 p->type = i>>1;
158 p->signBits = 0;
159 Vec3Clear (p->normal);
160 p->normal[i>>1] = 1;
161
162 p = &cm_q2_boxPlanes[i*2+1];
163 p->type = 3 + (i>>1);
164 p->signBits = 0;
165 Vec3Clear (p->normal);
166 p->normal[i>>1] = -1;
167 }
168 }
169
170
171 /*
172 ===================
173 CM_Q2BSP_HeadnodeForBox
174
175 To keep everything totally uniform, bounding boxes are turned into small
176 BSP trees instead of being compared directly.
177 ===================
178 */
CM_Q2BSP_HeadnodeForBox(vec3_t mins,vec3_t maxs)179 int CM_Q2BSP_HeadnodeForBox (vec3_t mins, vec3_t maxs)
180 {
181 cm_q2_boxPlanes[0].dist = maxs[0];
182 cm_q2_boxPlanes[1].dist = -maxs[0];
183 cm_q2_boxPlanes[2].dist = mins[0];
184 cm_q2_boxPlanes[3].dist = -mins[0];
185 cm_q2_boxPlanes[4].dist = maxs[1];
186 cm_q2_boxPlanes[5].dist = -maxs[1];
187 cm_q2_boxPlanes[6].dist = mins[1];
188 cm_q2_boxPlanes[7].dist = -mins[1];
189 cm_q2_boxPlanes[8].dist = maxs[2];
190 cm_q2_boxPlanes[9].dist = -maxs[2];
191 cm_q2_boxPlanes[10].dist = mins[2];
192 cm_q2_boxPlanes[11].dist = -mins[2];
193
194 return cm_q2_boxHeadNode;
195 }
196
197
198 /*
199 ==================
200 CM_Q2BSP_PointLeafnum_r
201 ==================
202 */
CM_Q2BSP_PointLeafnum_r(vec3_t p,int num)203 static int CM_Q2BSP_PointLeafnum_r (vec3_t p, int num)
204 {
205 float d;
206 cQ2BspNode_t *node;
207 cBspPlane_t *plane;
208
209 while (num >= 0) {
210 node = cm_q2_nodes + num;
211 plane = node->plane;
212
213 d = PlaneDiff (p, plane);
214 if (d < 0)
215 num = node->children[1];
216 else
217 num = node->children[0];
218 }
219
220 cm_numPointContents++; // Optimize counter
221
222 return -1 - num;
223 }
224
225
226 /*
227 ==================
228 CM_Q2BSP_PointLeafnum
229 ==================
230 */
CM_Q2BSP_PointLeafnum(vec3_t p)231 int CM_Q2BSP_PointLeafnum (vec3_t p)
232 {
233 if (!cm_q2_numPlanes)
234 return 0; // Sound may call this without map loaded
235 return CM_Q2BSP_PointLeafnum_r (p, 0);
236 }
237
238
239 /*
240 =============
241 CM_Q2BSP_BoxLeafnums
242
243 Fills in a list of all the leafs touched
244 =============
245 */
CM_Q2BSP_BoxLeafnums_r(int nodeNum)246 static void CM_Q2BSP_BoxLeafnums_r (int nodeNum)
247 {
248 cBspPlane_t *plane;
249 cQ2BspNode_t *node;
250 int s;
251
252 for ( ; ; ) {
253 if (nodeNum < 0) {
254 if (cm_q2_leafCount >= cm_q2_leafMaxCount)
255 return;
256
257 cm_q2_leafList[cm_q2_leafCount++] = -1 - nodeNum;
258 return;
259 }
260
261 node = &cm_q2_nodes[nodeNum];
262 plane = node->plane;
263 s = BOX_ON_PLANE_SIDE (cm_q2_leafMins, cm_q2_leafMaxs, plane);
264 if (s == 1)
265 nodeNum = node->children[0];
266 else if (s == 2)
267 nodeNum = node->children[1];
268 else {
269 // Go down both
270 if (cm_q2_leafTopNode == -1)
271 cm_q2_leafTopNode = nodeNum;
272 CM_Q2BSP_BoxLeafnums_r (node->children[0]);
273 nodeNum = node->children[1];
274 }
275 }
276 }
277
278
279 /*
280 ==================
281 CM_Q2BSP_BoxLeafnumsHeadNode
282 ==================
283 */
CM_Q2BSP_BoxLeafnumsHeadNode(vec3_t mins,vec3_t maxs,int * list,int listSize,int headNode,int * topNode)284 static int CM_Q2BSP_BoxLeafnumsHeadNode (vec3_t mins, vec3_t maxs, int *list, int listSize, int headNode, int *topNode)
285 {
286 cm_q2_leafList = list;
287 cm_q2_leafCount = 0;
288 cm_q2_leafMaxCount = listSize;
289 cm_q2_leafMins = mins;
290 cm_q2_leafMaxs = maxs;
291 cm_q2_leafTopNode = -1;
292
293 CM_Q2BSP_BoxLeafnums_r (headNode);
294
295 if (topNode)
296 *topNode = cm_q2_leafTopNode;
297
298 return cm_q2_leafCount;
299 }
300
301
302 /*
303 ==================
304 CM_Q2BSP_BoxLeafnums
305 ==================
306 */
CM_Q2BSP_BoxLeafnums(vec3_t mins,vec3_t maxs,int * list,int listSize,int * topNode)307 int CM_Q2BSP_BoxLeafnums (vec3_t mins, vec3_t maxs, int *list, int listSize, int *topNode)
308 {
309 return CM_Q2BSP_BoxLeafnumsHeadNode (mins, maxs, list, listSize, cm_mapCModels[0].headNode, topNode);
310 }
311
312
313 /*
314 ==================
315 CM_Q2BSP_PointContents
316 ==================
317 */
CM_Q2BSP_PointContents(vec3_t p,int headNode)318 int CM_Q2BSP_PointContents (vec3_t p, int headNode)
319 {
320 int l;
321
322 if (!cm_q2_numNodes) // Map not loaded
323 return 0;
324
325 l = CM_Q2BSP_PointLeafnum_r (p, headNode);
326
327 return cm_q2_leafs[l].contents;
328 }
329
330
331 /*
332 ==================
333 CM_Q2BSP_TransformedPointContents
334
335 Handles offseting and rotation of the end points for moving and rotating entities
336 ==================
337 */
CM_Q2BSP_TransformedPointContents(vec3_t p,int headNode,vec3_t origin,vec3_t angles)338 int CM_Q2BSP_TransformedPointContents (vec3_t p, int headNode, vec3_t origin, vec3_t angles)
339 {
340 vec3_t dist;
341 vec3_t temp;
342 vec3_t forward, right, up;
343 int l;
344
345 // Subtract origin offset
346 Vec3Subtract (p, origin, dist);
347
348 // Rotate start and end into the models frame of reference
349 if (headNode != cm_q2_boxHeadNode && (angles[0] || angles[1] || angles[2])) {
350 Angles_Vectors (angles, forward, right, up);
351
352 Vec3Copy (dist, temp);
353 dist[0] = DotProduct (temp, forward);
354 dist[1] = -DotProduct (temp, right);
355 dist[2] = DotProduct (temp, up);
356 }
357
358 l = CM_Q2BSP_PointLeafnum_r (dist, headNode);
359
360 return cm_q2_leafs[l].contents;
361 }
362
363 /*
364 =============================================================================
365
366 BOX TRACING
367
368 =============================================================================
369 */
370
371 /*
372 ================
373 CM_Q2BSP_ClipBoxToBrush
374 ================
375 */
CM_Q2BSP_ClipBoxToBrush(cQ2BspBrush_t * brush)376 static void CM_Q2BSP_ClipBoxToBrush (cQ2BspBrush_t *brush)
377 {
378 int i, j;
379 cBspPlane_t *p, *clipPlane;
380 float dist, dot1, dot2, f;
381 float enterFrac, leaveFrac;
382 vec3_t ofs;
383 qBool getOut, startOut;
384 cQ2BspBrushSide_t *side, *leadSide;
385
386 enterFrac = -1;
387 leaveFrac = 1;
388 clipPlane = NULL;
389
390 if (!brush->numSides)
391 return;
392
393 cm_numBrushTraces++;
394
395 getOut = qFalse;
396 startOut = qFalse;
397 leadSide = NULL;
398
399 for (i=0, side=&cm_q2_brushSides[brush->firstBrushSide] ; i<brush->numSides ; side++, i++) {
400 p = side->plane;
401
402 // FIXME: special case for axial
403 if (!cm_q2_traceIsPoint) {
404 // general box case
405 // push the plane out apropriately for mins/maxs
406 // FIXME: use signBits into 8 way lookup for each mins/maxs
407 for (j=0 ; j<3 ; j++) {
408 if (p->normal[j] < 0)
409 ofs[j] = cm_q2_traceMaxs[j];
410 else
411 ofs[j] = cm_q2_traceMins[j];
412 }
413 dist = DotProduct (ofs, p->normal);
414 dist = p->dist - dist;
415 }
416 else {
417 // Special point case
418 dist = p->dist;
419 }
420
421 dot1 = DotProduct (cm_q2_traceStart, p->normal) - dist;
422 dot2 = DotProduct (cm_q2_traceEnd, p->normal) - dist;
423
424 if (dot2 > 0)
425 getOut = qTrue; // Endpoint is not in solid
426 if (dot1 > 0)
427 startOut = qTrue;
428
429 // If completely in front of face, no intersection
430 if (dot1 > 0 && dot2 >= dot1)
431 return;
432
433 if (dot1 <= 0 && dot2 <= 0)
434 continue;
435
436 // Crosses face
437 f = dot1 - dot2;
438 if (f > 0) {
439 // Enter
440 f = (dot1 - DIST_EPSILON) / f;
441 if (f > enterFrac) {
442 enterFrac = f;
443 clipPlane = p;
444 leadSide = side;
445 }
446 }
447 else {
448 // Leave
449 f = (dot1 + DIST_EPSILON) / f;
450 if (f < leaveFrac)
451 leaveFrac = f;
452 }
453 }
454
455 if (!startOut) {
456 // Original point was inside brush
457 cm_q2_currentTrace.startSolid = qTrue;
458 if (!getOut)
459 cm_q2_currentTrace.allSolid = qTrue;
460 return;
461 }
462
463 if (enterFrac < leaveFrac && enterFrac > -1 && enterFrac < cm_q2_currentTrace.fraction) {
464 if (enterFrac < 0)
465 enterFrac = 0;
466
467 cm_q2_currentTrace.fraction = enterFrac;
468 cm_q2_currentTrace.plane = *clipPlane;
469 cm_q2_currentTrace.surface = &(leadSide->surface->c);
470 cm_q2_currentTrace.contents = brush->contents;
471 }
472 }
473
474
475 /*
476 ================
477 CM_Q2BSP_ClipBoxes
478 ================
479 */
CM_Q2BSP_ClipBoxes(int leafNum)480 static void CM_Q2BSP_ClipBoxes (int leafNum)
481 {
482 cQ2BspLeaf_t *leaf;
483 cQ2BspBrush_t *brush;
484 int brushNum;
485 int k;
486
487 leaf = &cm_q2_leafs[leafNum];
488 if (!(leaf->contents & cm_q2_traceContents))
489 return;
490
491 // Trace line against all brushes in the leaf
492 for (k=0 ; k<leaf->numLeafBrushes ; k++) {
493 brushNum = cm_q2_leafBrushes[leaf->firstLeafBrush+k];
494 brush = &cm_q2_brushes[brushNum];
495
496 if (brush->checkCount == cm_q2_checkCount)
497 continue; // Already checked this brush in another leaf
498 brush->checkCount = cm_q2_checkCount;
499 if (!(brush->contents & cm_q2_traceContents))
500 continue;
501
502 CM_Q2BSP_ClipBoxToBrush (brush);
503 if (!cm_q2_currentTrace.fraction)
504 return;
505 }
506 }
507
508
509 /*
510 ================
511 CM_Q2BSP_TestBoxInBrush
512 ================
513 */
CM_Q2BSP_TestBoxInBrush(cQ2BspBrush_t * brush)514 static void CM_Q2BSP_TestBoxInBrush (cQ2BspBrush_t *brush)
515 {
516 int i, j;
517 vec3_t ofs;
518 cBspPlane_t *p;
519 cQ2BspBrushSide_t *side;
520 float dist, dot;
521
522 if (!brush->numSides)
523 return;
524
525 for (i=0, side=&cm_q2_brushSides[brush->firstBrushSide] ; i<brush->numSides ; side++, i++) {
526 p = side->plane;
527
528 // FIXME: special case for axial
529 // general box case
530 // push the plane out apropriately for mins/maxs
531 // FIXME: use signBits into 8 way lookup for each mins/maxs
532 for (j=0 ; j<3 ; j++) {
533 if (p->normal[j] < 0)
534 ofs[j] = cm_q2_traceMaxs[j];
535 else
536 ofs[j] = cm_q2_traceMins[j];
537 }
538
539 dist = p->dist - DotProduct (ofs, p->normal);
540 dot = DotProduct (cm_q2_traceStart, p->normal) - dist;
541
542 // If completely in front of face, no intersection
543 if (dot > 0)
544 return;
545 }
546
547 // Inside this brush
548 cm_q2_currentTrace.startSolid = cm_q2_currentTrace.allSolid = qTrue;
549 cm_q2_currentTrace.fraction = 0;
550 cm_q2_currentTrace.contents = brush->contents;
551 }
552
553
554 /*
555 ================
556 CM_Q2BSP_TestBoxes
557 ================
558 */
CM_Q2BSP_TestBoxes(int leafNum)559 static void CM_Q2BSP_TestBoxes (int leafNum)
560 {
561 cQ2BspLeaf_t *leaf;
562 cQ2BspBrush_t *brush;
563 int brushNum;
564 int k;
565
566 leaf = &cm_q2_leafs[leafNum];
567 if (!(leaf->contents & cm_q2_traceContents))
568 return;
569
570 // Trace line against all brushes in the leaf
571 for (k=0 ; k<leaf->numLeafBrushes ; k++) {
572 brushNum = cm_q2_leafBrushes[leaf->firstLeafBrush+k];
573 brush = &cm_q2_brushes[brushNum];
574
575 if (brush->checkCount == cm_q2_checkCount)
576 continue; // Already checked this brush in another leaf
577 brush->checkCount = cm_q2_checkCount;
578 if (!(brush->contents & cm_q2_traceContents))
579 continue;
580
581 CM_Q2BSP_TestBoxInBrush (brush);
582 if (!cm_q2_currentTrace.fraction)
583 return;
584 }
585 }
586
587
588 /*
589 ==================
590 CM_Q2BSP_RecursiveHullCheck
591 ==================
592 */
CM_Q2BSP_RecursiveHullCheck(int num,float p1f,float p2f,vec3_t p1,vec3_t p2)593 static void CM_Q2BSP_RecursiveHullCheck (int num, float p1f, float p2f, vec3_t p1, vec3_t p2)
594 {
595 cQ2BspNode_t *node;
596 cBspPlane_t *plane;
597 float t1, t2, offset;
598 float frac, frac2;
599 float idist;
600 int i, side;
601 vec3_t mid;
602 float midf;
603
604 if (cm_q2_currentTrace.fraction <= p1f)
605 return; // already hit something nearer
606
607 // if < 0, we are in a leaf node
608 if (num < 0) {
609 CM_Q2BSP_ClipBoxes (-1-num);
610 return;
611 }
612
613 /*
614 ** find the point distances to the seperating plane
615 ** and the offset for the size of the box
616 */
617 node = cm_q2_nodes + num;
618 plane = node->plane;
619
620 if (plane->type < 3) {
621 t1 = p1[plane->type] - plane->dist;
622 t2 = p2[plane->type] - plane->dist;
623 offset = cm_q2_traceExtents[plane->type];
624 }
625 else {
626 t1 = DotProduct (plane->normal, p1) - plane->dist;
627 t2 = DotProduct (plane->normal, p2) - plane->dist;
628 if (cm_q2_traceIsPoint)
629 offset = 0;
630 else
631 offset = fabs (cm_q2_traceExtents[0]*plane->normal[0])
632 + fabs (cm_q2_traceExtents[1]*plane->normal[1])
633 + fabs (cm_q2_traceExtents[2]*plane->normal[2]);
634 }
635
636 // see which sides we need to consider
637 if (t1 >= offset && t2 >= offset) {
638 CM_Q2BSP_RecursiveHullCheck (node->children[0], p1f, p2f, p1, p2);
639 return;
640 }
641 if (t1 < -offset && t2 < -offset) {
642 CM_Q2BSP_RecursiveHullCheck (node->children[1], p1f, p2f, p1, p2);
643 return;
644 }
645
646 // put the crosspoint DIST_EPSILON pixels on the near side
647 if (t1 < t2) {
648 idist = 1.0/(t1-t2);
649 side = 1;
650 frac2 = (t1 + offset + DIST_EPSILON)*idist;
651 frac = (t1 - offset + DIST_EPSILON)*idist;
652 }
653 else if (t1 > t2) {
654 idist = 1.0/(t1-t2);
655 side = 0;
656 frac2 = (t1 - offset - DIST_EPSILON)*idist;
657 frac = (t1 + offset + DIST_EPSILON)*idist;
658 }
659 else {
660 side = 0;
661 frac = 1;
662 frac2 = 0;
663 }
664
665 // move up to the node
666 frac = clamp (frac, 0, 1);
667 midf = p1f + (p2f - p1f ) * frac;
668 for (i=0 ; i<3 ; i++)
669 mid[i] = p1[i] + frac * (p2[i] - p1[i]);
670
671 CM_Q2BSP_RecursiveHullCheck (node->children[side], p1f, midf, p1, mid);
672
673 // go past the node
674 frac2 = clamp (frac2, 0, 1);
675 midf = p1f + (p2f - p1f) * frac2;
676 for (i=0 ; i<3 ; i++)
677 mid[i] = p1[i] + frac2 * (p2[i] - p1[i]);
678
679 CM_Q2BSP_RecursiveHullCheck (node->children[side^1], midf, p2f, mid, p2);
680 }
681
682 // ==========================================================================
683
684 /*
685 ====================
686 CM_Q2BSP_Trace
687 ====================
688 */
CM_Q2BSP_Trace(vec3_t start,vec3_t end,float size,int contentMask)689 trace_t CM_Q2BSP_Trace (vec3_t start, vec3_t end, float size, int contentMask)
690 {
691 vec3_t maxs, mins;
692
693 Vec3Set (maxs, size, size, size);
694 Vec3Set (mins, -size, -size, -size);
695
696 return CM_Q2BSP_BoxTrace (start, end, mins, maxs, 0, contentMask);
697 }
698
699
700 /*
701 ==================
702 CM_Q2BSP_BoxTrace
703 ==================
704 */
CM_Q2BSP_BoxTrace(vec3_t start,vec3_t end,vec3_t mins,vec3_t maxs,int headNode,int brushMask)705 trace_t CM_Q2BSP_BoxTrace (vec3_t start, vec3_t end, vec3_t mins, vec3_t maxs, int headNode, int brushMask)
706 {
707 cm_q2_checkCount++; // For multi-check avoidance
708 cm_numTraces++; // For statistics, may be zeroed
709
710 // Fill in a default trace
711 cm_q2_currentTrace.allSolid = qFalse;
712 cm_q2_currentTrace.contents = 0;
713 Vec3Clear (cm_q2_currentTrace.endPos);
714 cm_q2_currentTrace.ent = NULL;
715 cm_q2_currentTrace.fraction = 1;
716 cm_q2_currentTrace.plane.dist = 0;
717 Vec3Clear (cm_q2_currentTrace.plane.normal);
718 cm_q2_currentTrace.plane.signBits = 0;
719 cm_q2_currentTrace.plane.type = 0;
720 cm_q2_currentTrace.startSolid = qFalse;
721 cm_q2_currentTrace.surface = &(cm_q2_nullSurface.c);
722
723 if (!cm_q2_numNodes) // Map not loaded
724 return cm_q2_currentTrace;
725
726 cm_q2_traceContents = brushMask;
727 Vec3Copy (start, cm_q2_traceStart);
728 Vec3Copy (end, cm_q2_traceEnd);
729 Vec3Copy (mins, cm_q2_traceMins);
730 Vec3Copy (maxs, cm_q2_traceMaxs);
731
732 // Check for position test special case
733 if (Vec3Compare (start, end)) {
734 int leafs[1024];
735 int i, numLeafs;
736 vec3_t c1, c2;
737 int topNode;
738
739 Vec3Add (start, mins, c1);
740 Vec3Add (start, maxs, c2);
741 for (i=0 ; i<3 ; i++) {
742 c1[i] -= 1;
743 c2[i] += 1;
744 }
745
746 numLeafs = CM_Q2BSP_BoxLeafnumsHeadNode (c1, c2, leafs, 1024, headNode, &topNode);
747 for (i=0 ; i<numLeafs ; i++) {
748 CM_Q2BSP_TestBoxes (leafs[i]);
749 if (cm_q2_currentTrace.allSolid)
750 break;
751 }
752 Vec3Copy (start, cm_q2_currentTrace.endPos);
753 return cm_q2_currentTrace;
754 }
755
756 // Check for point special case
757 if (Vec3Compare (mins, vec3Origin) && Vec3Compare (maxs, vec3Origin)) {
758 cm_q2_traceIsPoint = qTrue;
759 Vec3Clear (cm_q2_traceExtents);
760 }
761 else {
762 cm_q2_traceIsPoint = qFalse;
763 cm_q2_traceExtents[0] = -mins[0] > maxs[0] ? -mins[0] : maxs[0];
764 cm_q2_traceExtents[1] = -mins[1] > maxs[1] ? -mins[1] : maxs[1];
765 cm_q2_traceExtents[2] = -mins[2] > maxs[2] ? -mins[2] : maxs[2];
766 }
767
768 // General sweeping through world
769 CM_Q2BSP_RecursiveHullCheck (headNode, 0, 1, start, end);
770
771 if (cm_q2_currentTrace.fraction == 1) {
772 Vec3Copy (end, cm_q2_currentTrace.endPos);
773 }
774 else {
775 cm_q2_currentTrace.endPos[0] = start[0] + cm_q2_currentTrace.fraction * (end[0] - start[0]);
776 cm_q2_currentTrace.endPos[1] = start[1] + cm_q2_currentTrace.fraction * (end[1] - start[1]);
777 cm_q2_currentTrace.endPos[2] = start[2] + cm_q2_currentTrace.fraction * (end[2] - start[2]);
778 }
779
780 return cm_q2_currentTrace;
781 }
782
783
784 /*
785 ==================
786 CM_Q2BSP_TransformedBoxTrace
787
788 Handles offseting and rotation of the end points for moving and rotating entities
789 ==================
790 */
791 #ifdef WIN32
792 #pragma optimize ("", off)
793 #endif
CM_Q2BSP_TransformedBoxTrace(trace_t * out,vec3_t start,vec3_t end,vec3_t mins,vec3_t maxs,int headNode,int brushMask,vec3_t origin,vec3_t angles)794 void CM_Q2BSP_TransformedBoxTrace (trace_t *out, vec3_t start, vec3_t end, vec3_t mins, vec3_t maxs, int headNode, int brushMask, vec3_t origin, vec3_t angles)
795 {
796 vec3_t start_l, end_l;
797 vec3_t forward, right, up;
798 vec3_t temp, a;
799 qBool rotated;
800
801 // Subtract origin offset
802 Vec3Subtract (start, origin, start_l);
803 Vec3Subtract (end, origin, end_l);
804
805 // Rotate start and end into the models frame of reference
806 if (headNode != cm_q2_boxHeadNode && (angles[0] || angles[1] || angles[2]))
807 rotated = qTrue;
808 else
809 rotated = qFalse;
810
811 if (rotated) {
812 Angles_Vectors (angles, forward, right, up);
813
814 Vec3Copy (start_l, temp);
815 start_l[0] = DotProduct (temp, forward);
816 start_l[1] = -DotProduct (temp, right);
817 start_l[2] = DotProduct (temp, up);
818
819 Vec3Copy (end_l, temp);
820 end_l[0] = DotProduct (temp, forward);
821 end_l[1] = -DotProduct (temp, right);
822 end_l[2] = DotProduct (temp, up);
823 }
824
825 // Sweep the box through the model
826 *out = CM_Q2BSP_BoxTrace (start_l, end_l, mins, maxs, headNode, brushMask);
827
828 if (rotated && out->fraction != 1.0) {
829 // FIXME: figure out how to do this with existing angles
830 Vec3Negate (angles, a);
831 Angles_Vectors (a, forward, right, up);
832
833 Vec3Copy (out->plane.normal, temp);
834 out->plane.normal[0] = DotProduct (temp, forward);
835 out->plane.normal[1] = -DotProduct (temp, right);
836 out->plane.normal[2] = DotProduct (temp, up);
837 }
838
839 out->endPos[0] = start[0] + out->fraction * (end[0] - start[0]);
840 out->endPos[1] = start[1] + out->fraction * (end[1] - start[1]);
841 out->endPos[2] = start[2] + out->fraction * (end[2] - start[2]);
842 }
843 #ifdef WIN32
844 #pragma optimize ("", on)
845 #endif
846
847 /*
848 =============================================================================
849
850 PVS / PHS
851
852 =============================================================================
853 */
854
855 /*
856 ===================
857 CM_Q2BSP_DecompressVis
858 ===================
859 */
CM_Q2BSP_DecompressVis(byte * in,byte * out)860 static void CM_Q2BSP_DecompressVis (byte *in, byte *out)
861 {
862 int c;
863 byte *outPtr;
864 int row;
865
866 row = (cm_q2_numClusters + 7) >> 3;
867 outPtr = out;
868
869 if (!in || !cm_q2_numVisibility) {
870 // No vis info, so make all visible
871 while (row) {
872 *outPtr++ = 0xff;
873 row--;
874 }
875 return;
876 }
877
878 do {
879 if (*in) {
880 *outPtr++ = *in++;
881 continue;
882 }
883
884 c = in[1];
885 in += 2;
886 if ((outPtr - out) + c > row) {
887 c = row - (outPtr - out);
888 Com_DevPrintf (PRNT_WARNING, "Warning: Vis decompression overrun\n");
889 }
890
891 while (c) {
892 *outPtr++ = 0;
893 c--;
894 }
895 } while (outPtr - out < row);
896 }
897
898
899 /*
900 ===================
901 CM_Q2BSP_ClusterPVS
902 ===================
903 */
CM_Q2BSP_ClusterPVS(int cluster)904 byte *CM_Q2BSP_ClusterPVS (int cluster)
905 {
906 static byte pvsRow[Q2BSP_MAX_VIS];
907
908 if (cluster == -1 || !cm_q2_visData)
909 memset (pvsRow, 0, (cm_q2_numClusters + 7) >> 3);
910 else
911 CM_Q2BSP_DecompressVis ((byte *)cm_q2_visData + cm_q2_visData->bitOfs[cluster][Q2BSP_VIS_PVS], pvsRow);
912 return pvsRow;
913 }
914
915
916 /*
917 ===================
918 CM_Q2BSP_ClusterPHS
919 ===================
920 */
CM_Q2BSP_ClusterPHS(int cluster)921 byte *CM_Q2BSP_ClusterPHS (int cluster)
922 {
923 static byte phsRow[Q2BSP_MAX_VIS];
924
925 if (cluster == -1 || !cm_q2_visData)
926 memset (phsRow, 0, (cm_q2_numClusters + 7) >> 3);
927 else
928 CM_Q2BSP_DecompressVis ((byte *)cm_q2_visData + cm_q2_visData->bitOfs[cluster][Q2BSP_VIS_PHS], phsRow);
929 return phsRow;
930 }
931
932 /*
933 =============================================================================
934
935 AREAPORTALS
936
937 =============================================================================
938 */
939
940 /*
941 ====================
942 CM_Q2BSP_FloodAreaConnections
943 ====================
944 */
FloodArea_r(cQ2BspArea_t * area,int floodNum)945 static void FloodArea_r (cQ2BspArea_t *area, int floodNum)
946 {
947 dQ2BspAreaPortal_t *p;
948 int i;
949
950 if (area->floodValid == cm_q2_floodValid) {
951 if (area->floodNum == floodNum)
952 return;
953 Com_Error (ERR_DROP, "FloodArea_r: reflooded");
954 }
955
956 area->floodNum = floodNum;
957 area->floodValid = cm_q2_floodValid;
958 p = &cm_q2_areaPortals[area->firstAreaPortal];
959 for (i=0 ; i<area->numAreaPortals ; i++, p++) {
960 if (cm_q2_portalOpen[p->portalNum])
961 FloodArea_r (&cm_q2_areas[p->otherArea], floodNum);
962 }
963 }
CM_Q2BSP_FloodAreaConnections(void)964 void CM_Q2BSP_FloodAreaConnections (void)
965 {
966 cQ2BspArea_t *area;
967 int floodNum;
968 int i;
969
970 // All current floods are now invalid
971 cm_q2_floodValid++;
972 floodNum = 0;
973
974 // Area 0 is not used
975 for (i=1 ; i<cm_q2_numAreas ; i++) {
976 area = &cm_q2_areas[i];
977 if (area->floodValid == cm_q2_floodValid)
978 continue; // already flooded into
979 floodNum++;
980 FloodArea_r (area, floodNum);
981 }
982 }
983
984
985 /*
986 ====================
987 CM_Q2BSP_SetAreaPortalState
988 ====================
989 */
CM_Q2BSP_SetAreaPortalState(int portalNum,qBool open)990 void CM_Q2BSP_SetAreaPortalState (int portalNum, qBool open)
991 {
992 if (portalNum > cm_q2_numAreaPortals)
993 Com_Error (ERR_DROP, "CM_SetAreaPortalState: areaportal > numAreaPortals");
994
995 cm_q2_portalOpen[portalNum] = open;
996 CM_Q2BSP_FloodAreaConnections ();
997 }
998
999
1000 /*
1001 ====================
1002 CM_Q2BSP_AreasConnected
1003 ====================
1004 */
CM_Q2BSP_AreasConnected(int area1,int area2)1005 qBool CM_Q2BSP_AreasConnected (int area1, int area2)
1006 {
1007 if (cm_noAreas->intVal)
1008 return qTrue;
1009
1010 if (area1 > cm_q2_numAreas || area2 > cm_q2_numAreas)
1011 Com_Error (ERR_DROP, "CM_AreasConnected: area > cm_q2_numAreas");
1012
1013 if (cm_q2_areas[area1].floodNum == cm_q2_areas[area2].floodNum)
1014 return qTrue;
1015 return qFalse;
1016 }
1017
1018
1019 /*
1020 =================
1021 CM_Q2BSP_WriteAreaBits
1022
1023 Writes a length byte followed by a bit vector of all the areas
1024 that area in the same flood as the area parameter
1025
1026 This is used by the client refreshes to cull visibility
1027 =================
1028 */
CM_Q2BSP_WriteAreaBits(byte * buffer,int area)1029 int CM_Q2BSP_WriteAreaBits (byte *buffer, int area)
1030 {
1031 int i;
1032 int floodNum;
1033 int bytes;
1034
1035 bytes = (cm_q2_numAreas+7)>>3;
1036
1037 if (cm_noAreas->intVal) {
1038 // For debugging, send everything
1039 memset (buffer, 255, bytes);
1040 }
1041 else {
1042 memset (buffer, 0, bytes);
1043
1044 floodNum = cm_q2_areas[area].floodNum;
1045 for (i=0 ; i<cm_q2_numAreas ; i++) {
1046 if (cm_q2_areas[i].floodNum == floodNum || !area)
1047 buffer[i>>3] |= 1<<(i&7);
1048 }
1049 }
1050
1051 return bytes;
1052 }
1053
1054
1055 /*
1056 ===================
1057 CM_Q2BSP_WritePortalState
1058
1059 Writes the portal state to a savegame file
1060 ===================
1061 */
CM_Q2BSP_WritePortalState(fileHandle_t fileNum)1062 void CM_Q2BSP_WritePortalState (fileHandle_t fileNum)
1063 {
1064 FS_Write (cm_q2_portalOpen, sizeof (qBool) * Q2BSP_MAX_AREAPORTALS, fileNum);
1065 }
1066
1067
1068 /*
1069 ===================
1070 CM_Q2BSP_ReadPortalState
1071
1072 Reads the portal state from a savegame file and recalculates the area connections
1073 ===================
1074 */
CM_Q2BSP_ReadPortalState(fileHandle_t fileNum)1075 void CM_Q2BSP_ReadPortalState (fileHandle_t fileNum)
1076 {
1077 FS_Read (cm_q2_portalOpen, sizeof (qBool) * Q2BSP_MAX_AREAPORTALS, fileNum);
1078 CM_Q2BSP_FloodAreaConnections ();
1079 }
1080
1081
1082 /*
1083 =============
1084 CM_Q2BSP_HeadnodeVisible
1085
1086 Returns qTrue if any leaf under headnode has a cluster that is potentially visible
1087 =============
1088 */
CM_Q2BSP_HeadnodeVisible(int nodeNum,byte * visBits)1089 qBool CM_Q2BSP_HeadnodeVisible (int nodeNum, byte *visBits)
1090 {
1091 cQ2BspNode_t *node;
1092 int leafNum;
1093 int cluster;
1094
1095 if (nodeNum < 0) {
1096 leafNum = -1-nodeNum;
1097 cluster = cm_q2_leafs[leafNum].cluster;
1098 if (cluster == -1)
1099 return qFalse;
1100 if (visBits[cluster>>3] & (1<<(cluster&7)))
1101 return qTrue;
1102 return qFalse;
1103 }
1104
1105 node = &cm_q2_nodes[nodeNum];
1106 if (CM_Q2BSP_HeadnodeVisible (node->children[0], visBits))
1107 return qTrue;
1108 return CM_Q2BSP_HeadnodeVisible (node->children[1], visBits);
1109 }
1110