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_q3_trace.c
22 // Quake3 BSP map model tracing
23 //
24
25 #include "cm_q3_local.h"
26
27 static int cm_q3_checkCount;
28 static int cm_q3_floodValid;
29
30 static cBspPlane_t *cm_q3_boxPlanes;
31 static int cm_q3_boxHeadNode;
32 static cbrush_t *cm_q3_boxBrush;
33 static cleaf_t *cm_q3_boxLeaf;
34
35 static int cm_q3_leafCount, cm_q3_leafMaxCount;
36 static int *cm_q3_leafList;
37 static float *cm_q3_leafMins, *cm_q3_leafMaxs;
38 static int cm_q3_leafTopNode;
39
40 // 1/32 epsilon to keep floating point happy
41 #define DIST_EPSILON (0.03125f)
42
43 static trace_t cm_q3_currentTrace;
44 static vec3_t cm_q3_traceStart, cm_q3_traceStartMins, cm_q3_traceStartMaxs;
45 static vec3_t cm_q3_traceEnd, cm_q3_traceEndMins, cm_q3_traceEndMaxs;
46 static vec3_t cm_q3_traceMins, cm_q3_traceMaxs;
47 static vec3_t cm_q3_traceAbsMins, cm_q3_traceAbsMaxs;
48 static vec3_t cm_q3_traceExtents;
49 static int cm_q3_traceContents;
50 static qBool cm_q3_traceIsPoint; // Optimized case
51
52 /*
53 =============================================================================
54
55 TRACING
56
57 =============================================================================
58 */
59
60 /*
61 ==================
62 CM_Q3BSP_LeafArea
63 ==================
64 */
CM_Q3BSP_LeafArea(int leafNum)65 int CM_Q3BSP_LeafArea (int leafNum)
66 {
67 if (leafNum < 0 || leafNum >= cm_q3_numLeafs)
68 Com_Error (ERR_DROP, "CM_Q3BSP_LeafArea: bad number");
69
70 return cm_q3_leafs[leafNum].area;
71 }
72
73
74 /*
75 ==================
76 CM_Q3BSP_LeafCluster
77 ==================
78 */
CM_Q3BSP_LeafCluster(int leafNum)79 int CM_Q3BSP_LeafCluster (int leafNum)
80 {
81 if (leafNum < 0 || leafNum >= cm_q3_numLeafs)
82 Com_Error (ERR_DROP, "CM_Q3BSP_LeafCluster: bad number");
83
84 return cm_q3_leafs[leafNum].cluster;
85 }
86
87
88 /*
89 ==================
90 CM_Q3BSP_LeafContents
91 ==================
92 */
CM_Q3BSP_LeafContents(int leafNum)93 int CM_Q3BSP_LeafContents (int leafNum)
94 {
95 if (leafNum < 0 || leafNum >= cm_q3_numLeafs)
96 Com_Error (ERR_DROP, "CM_Q3BSP_LeafContents: bad number");
97
98 return cm_q3_leafs[leafNum].contents;
99 }
100
101 // ==========================================================================
102
103 /*
104 ===================
105 CM_Q3BSP_InitBoxHull
106 ===================
107 */
CM_Q3BSP_InitBoxHull(void)108 void CM_Q3BSP_InitBoxHull (void)
109 {
110 int i;
111 int side;
112 cnode_t *c;
113 cBspPlane_t *p;
114 cbrushside_t *s;
115
116 cm_q3_boxHeadNode = cm_q3_numNodes;
117 cm_q3_boxPlanes = &cm_q3_planes[cm_q3_numPlanes];
118 if (cm_q3_numNodes+6 > MAX_Q3BSP_CM_NODES
119 || cm_q3_numBrushes+1 > MAX_Q3BSP_CM_BRUSHES
120 || cm_q3_numLeafBrushes+1 > MAX_Q3BSP_CM_LEAFBRUSHES
121 || cm_q3_numBrushSides+6 > MAX_Q3BSP_CM_BRUSHSIDES
122 || cm_q3_numPlanes+12 > MAX_Q3BSP_CM_PLANES)
123 Com_Error (ERR_DROP, "CM_Q3BSP_InitBoxHull: Not enough room for box tree");
124
125 cm_q3_boxBrush = &cm_q3_brushes[cm_q3_numBrushes];
126 cm_q3_boxBrush->numSides = 6;
127 cm_q3_boxBrush->firstBrushSide = cm_q3_numBrushSides;
128 cm_q3_boxBrush->contents = Q3CNTNTS_BODY;
129
130 cm_q3_boxLeaf = &cm_q3_leafs[cm_q3_numLeafs];
131 cm_q3_boxLeaf->contents = Q3CNTNTS_BODY;
132 cm_q3_boxLeaf->firstLeafBrush = cm_q3_numLeafBrushes;
133 cm_q3_boxLeaf->numLeafBrushes = 1;
134
135 cm_q3_leafBrushes[cm_q3_numLeafBrushes] = cm_q3_numBrushes;
136
137 for (i=0 ; i<6 ; i++) {
138 side = i&1;
139
140 // Brush sides
141 s = &cm_q3_brushSides[cm_q3_numBrushSides+i];
142 s->plane = cm_q3_planes + (cm_q3_numPlanes+i*2+side);
143 s->surface = &cm_q3_nullSurface;
144
145 // Nodes
146 c = &cm_q3_nodes[cm_q3_boxHeadNode+i];
147 c->plane = cm_q3_planes + (cm_q3_numPlanes+i*2);
148 c->children[side] = -1 - cm_q3_emptyLeaf;
149 if (i != 5)
150 c->children[side^1] = cm_q3_boxHeadNode+i + 1;
151 else
152 c->children[side^1] = -1 - cm_q3_numLeafs;
153
154 // Planes
155 p = &cm_q3_boxPlanes[i*2];
156 p->type = i>>1;
157 p->signBits = 0;
158 Vec3Clear (p->normal);
159 p->normal[i>>1] = 1;
160
161 p = &cm_q3_boxPlanes[i*2+1];
162 p->type = 3 + (i>>1);
163 p->signBits = 0;
164 Vec3Clear (p->normal);
165 p->normal[i>>1] = -1;
166 }
167 }
168
169
170 /*
171 ===================
172 CM_Q3BSP_HeadnodeForBox
173 ===================
174 */
CM_Q3BSP_HeadnodeForBox(vec3_t mins,vec3_t maxs)175 int CM_Q3BSP_HeadnodeForBox (vec3_t mins, vec3_t maxs)
176 {
177 cm_q3_boxPlanes[0].dist = maxs[0];
178 cm_q3_boxPlanes[1].dist = -maxs[0];
179 cm_q3_boxPlanes[2].dist = mins[0];
180 cm_q3_boxPlanes[3].dist = -mins[0];
181 cm_q3_boxPlanes[4].dist = maxs[1];
182 cm_q3_boxPlanes[5].dist = -maxs[1];
183 cm_q3_boxPlanes[6].dist = mins[1];
184 cm_q3_boxPlanes[7].dist = -mins[1];
185 cm_q3_boxPlanes[8].dist = maxs[2];
186 cm_q3_boxPlanes[9].dist = -maxs[2];
187 cm_q3_boxPlanes[10].dist = mins[2];
188 cm_q3_boxPlanes[11].dist = -mins[2];
189
190 return cm_q3_boxHeadNode;
191 }
192
193
194 /*
195 ==================
196 CM_Q3BSP_PointLeafnum
197 ==================
198 */
CM_PointLeafnum_r(vec3_t p,int num)199 int CM_PointLeafnum_r (vec3_t p, int num)
200 {
201 float d;
202 cnode_t *node;
203 cBspPlane_t *plane;
204
205 while (num >= 0) {
206 node = cm_q3_nodes + num;
207 plane = node->plane;
208 d = PlaneDiff (p, plane);
209
210 if (d < 0)
211 num = node->children[1];
212 else
213 num = node->children[0];
214 }
215
216 // Optimize counter
217 cm_numPointContents++;
218 return -1 - num;
219 }
CM_Q3BSP_PointLeafnum(vec3_t p)220 int CM_Q3BSP_PointLeafnum (vec3_t p)
221 {
222 if (!cm_q3_numPlanes)
223 return 0; // Sound may call this without map loaded
224 return CM_PointLeafnum_r (p, 0);
225 }
226
227
228 /*
229 ==================
230 CM_Q3BSP_BoxLeafnums
231 ==================
232 */
CM_Q3BSP_BoxLeafnums_r(int nodeNum)233 static void CM_Q3BSP_BoxLeafnums_r (int nodeNum)
234 {
235 cnode_t *node;
236 int s;
237
238 for ( ; ; ) {
239 if (nodeNum < 0) {
240 if (cm_q3_leafCount >= cm_q3_leafMaxCount)
241 return;
242
243 cm_q3_leafList[cm_q3_leafCount++] = -1 - nodeNum;
244 return;
245 }
246
247 node = &cm_q3_nodes[nodeNum];
248 s = BoxOnPlaneSide (cm_q3_leafMins, cm_q3_leafMaxs, node->plane);
249
250 if (s == 1) {
251 nodeNum = node->children[0];
252 }
253 else if (s == 2) {
254 nodeNum = node->children[1];
255 }
256 else {
257 // Go down both
258 if (cm_q3_leafTopNode == -1)
259 cm_q3_leafTopNode = nodeNum;
260 CM_Q3BSP_BoxLeafnums_r (node->children[0]);
261 nodeNum = node->children[1];
262 }
263 }
264 }
CM_Q3BSP_BoxLeafnums_headnode(vec3_t mins,vec3_t maxs,int * list,int listSize,int headNode,int * topNode)265 static int CM_Q3BSP_BoxLeafnums_headnode (vec3_t mins, vec3_t maxs, int *list, int listSize, int headNode, int *topNode)
266 {
267 cm_q3_leafList = list;
268 cm_q3_leafCount = 0;
269 cm_q3_leafMaxCount = listSize;
270 cm_q3_leafMins = mins;
271 cm_q3_leafMaxs = maxs;
272 cm_q3_leafTopNode = -1;
273
274 CM_Q3BSP_BoxLeafnums_r (headNode);
275
276 if (topNode)
277 *topNode = cm_q3_leafTopNode;
278
279 return cm_q3_leafCount;
280 }
CM_Q3BSP_BoxLeafnums(vec3_t mins,vec3_t maxs,int * list,int listSize,int * topNode)281 int CM_Q3BSP_BoxLeafnums (vec3_t mins, vec3_t maxs, int *list, int listSize, int *topNode)
282 {
283 return CM_Q3BSP_BoxLeafnums_headnode (mins, maxs, list, listSize, cm_mapCModels[0].headNode, topNode);
284 }
285
286
287 /*
288 ==================
289 CM_Q3BSP_PointContents
290 ==================
291 */
CM_Q3BSP_PointContents(vec3_t p,int headNode)292 int CM_Q3BSP_PointContents (vec3_t p, int headNode)
293 {
294 int i, j, contents;
295 cleaf_t *leaf;
296 cbrush_t *brush;
297 cbrushside_t *brushSide;
298
299 if (!cm_q3_numNodes)
300 return 0; // Map not loaded
301
302 i = CM_PointLeafnum_r (p, headNode);
303 leaf = &cm_q3_leafs[i];
304
305 if (leaf->contents & Q3CNTNTS_NODROP)
306 contents = Q3CNTNTS_NODROP;
307 else
308 contents = 0;
309
310 for (i=0 ; i<leaf->numLeafBrushes ; i++) {
311 brush = &cm_q3_brushes[cm_q3_leafBrushes[leaf->firstLeafBrush + i]];
312
313 // Check if brush actually adds something to contents
314 if ((contents & brush->contents) == brush->contents)
315 continue;
316
317 brushSide = &cm_q3_brushSides[brush->firstBrushSide];
318 for (j=0 ; j<brush->numSides ; j++, brushSide++) {
319 if (PlaneDiff (p, brushSide->plane) > 0)
320 break;
321 }
322
323 if (j == brush->numSides)
324 contents |= brush->contents;
325 }
326
327 return contents;
328 }
329
330
331 /*
332 ==================
333 CM_Q3BSP_TransformedPointContents
334 ==================
335 */
CM_Q3BSP_TransformedPointContents(vec3_t p,int headNode,vec3_t origin,vec3_t angles)336 int CM_Q3BSP_TransformedPointContents (vec3_t p, int headNode, vec3_t origin, vec3_t angles)
337 {
338 vec3_t p_l;
339 vec3_t temp;
340 vec3_t forward, right, up;
341
342 if (!cm_q3_numNodes)
343 return 0; // Map not loaded
344
345 // Subtract origin offset
346 Vec3Subtract (p, origin, p_l);
347
348 // Rotate start and end into the models frame of reference
349 if (headNode != cm_q3_boxHeadNode && (angles[0] || angles[1] || angles[2])) {
350 Angles_Vectors (angles, forward, right, up);
351
352 Vec3Copy (p_l, temp);
353 p_l[0] = DotProduct (temp, forward);
354 p_l[1] = -DotProduct (temp, right);
355 p_l[2] = DotProduct (temp, up);
356 }
357
358 return CM_PointContents (p_l, headNode);
359 }
360
361 /*
362 =============================================================================
363
364 BOX TRACING
365
366 =============================================================================
367 */
368
369 /*
370 ================
371 CM_Q3BSP_ClipBoxToBrush
372 ================
373 */
CM_Q3BSP_ClipBoxToBrush(cbrush_t * brush)374 static void CM_Q3BSP_ClipBoxToBrush (cbrush_t *brush)
375 {
376 int i;
377 cBspPlane_t *p, *clipPlane;
378 float enterFrac, leaveFrac;
379 float d1, d2;
380 qBool getOut, startOut;
381 float f;
382 cbrushside_t *side, *leadSide;
383
384 enterFrac = -1;
385 leaveFrac = 1;
386 clipPlane = NULL;
387
388 if (!brush->numSides)
389 return;
390
391 cm_numBrushTraces++;
392
393 getOut = qFalse;
394 startOut = qFalse;
395 leadSide = NULL;
396
397 for (i=0, side=&cm_q3_brushSides[brush->firstBrushSide] ; i<brush->numSides ; side++, i++) {
398 p = side->plane;
399
400 // Push the plane out apropriately for mins/maxs
401 if (p->type < 3) {
402 d1 = cm_q3_traceStartMins[p->type] - p->dist;
403 d2 = cm_q3_traceEndMins[p->type] - p->dist;
404 }
405 else {
406 switch (p->signBits) {
407 case 0:
408 d1 = p->normal[0]*cm_q3_traceStartMins[0] + p->normal[1]*cm_q3_traceStartMins[1] + p->normal[2]*cm_q3_traceStartMins[2] - p->dist;
409 d2 = p->normal[0]*cm_q3_traceEndMins[0] + p->normal[1]*cm_q3_traceEndMins[1] + p->normal[2]*cm_q3_traceEndMins[2] - p->dist;
410 break;
411 case 1:
412 d1 = p->normal[0]*cm_q3_traceStartMaxs[0] + p->normal[1]*cm_q3_traceStartMins[1] + p->normal[2]*cm_q3_traceStartMins[2] - p->dist;
413 d2 = p->normal[0]*cm_q3_traceEndMaxs[0] + p->normal[1]*cm_q3_traceEndMins[1] + p->normal[2]*cm_q3_traceEndMins[2] - p->dist;
414 break;
415 case 2:
416 d1 = p->normal[0]*cm_q3_traceStartMins[0] + p->normal[1]*cm_q3_traceStartMaxs[1] + p->normal[2]*cm_q3_traceStartMins[2] - p->dist;
417 d2 = p->normal[0]*cm_q3_traceEndMins[0] + p->normal[1]*cm_q3_traceEndMaxs[1] + p->normal[2]*cm_q3_traceEndMins[2] - p->dist;
418 break;
419 case 3:
420 d1 = p->normal[0]*cm_q3_traceStartMaxs[0] + p->normal[1]*cm_q3_traceStartMaxs[1] + p->normal[2]*cm_q3_traceStartMins[2] - p->dist;
421 d2 = p->normal[0]*cm_q3_traceEndMaxs[0] + p->normal[1]*cm_q3_traceEndMaxs[1] + p->normal[2]*cm_q3_traceEndMins[2] - p->dist;
422 break;
423 case 4:
424 d1 = p->normal[0]*cm_q3_traceStartMins[0] + p->normal[1]*cm_q3_traceStartMins[1] + p->normal[2]*cm_q3_traceStartMaxs[2] - p->dist;
425 d2 = p->normal[0]*cm_q3_traceEndMins[0] + p->normal[1]*cm_q3_traceEndMins[1] + p->normal[2]*cm_q3_traceEndMaxs[2] - p->dist;
426 break;
427 case 5:
428 d1 = p->normal[0]*cm_q3_traceStartMaxs[0] + p->normal[1]*cm_q3_traceStartMins[1] + p->normal[2]*cm_q3_traceStartMaxs[2] - p->dist;
429 d2 = p->normal[0]*cm_q3_traceEndMaxs[0] + p->normal[1]*cm_q3_traceEndMins[1] + p->normal[2]*cm_q3_traceEndMaxs[2] - p->dist;
430 break;
431 case 6:
432 d1 = p->normal[0]*cm_q3_traceStartMins[0] + p->normal[1]*cm_q3_traceStartMaxs[1] + p->normal[2]*cm_q3_traceStartMaxs[2] - p->dist;
433 d2 = p->normal[0]*cm_q3_traceEndMins[0] + p->normal[1]*cm_q3_traceEndMaxs[1] + p->normal[2]*cm_q3_traceEndMaxs[2] - p->dist;
434 break;
435 case 7:
436 d1 = p->normal[0]*cm_q3_traceStartMaxs[0] + p->normal[1]*cm_q3_traceStartMaxs[1] + p->normal[2]*cm_q3_traceStartMaxs[2] - p->dist;
437 d2 = p->normal[0]*cm_q3_traceEndMaxs[0] + p->normal[1]*cm_q3_traceEndMaxs[1] + p->normal[2]*cm_q3_traceEndMaxs[2] - p->dist;
438 break;
439 default:
440 d1 = d2 = 0; // Shut up compiler
441 assert (0);
442 break;
443 }
444 }
445
446 if (d2 > 0)
447 getOut = qTrue; // Endpoint is not in solid
448 if (d1 > 0)
449 startOut = qTrue;
450
451 // If completely in front of face, no intersection
452 if (d1 > 0 && d2 >= d1)
453 return;
454 if (d1 <= 0 && d2 <= 0)
455 continue;
456
457 // Crosses face
458 f = d1 - d2;
459 if (f > 0) {
460 // Enter
461 f = (d1 - DIST_EPSILON) / f;
462 if (f > enterFrac) {
463 enterFrac = f;
464 clipPlane = p;
465 leadSide = side;
466 }
467 }
468 else {
469 // Leave
470 f = (d1 + DIST_EPSILON) / f;
471 if (f < leaveFrac)
472 leaveFrac = f;
473 }
474 }
475
476 if (!startOut) {
477 // Original point was inside brush
478 cm_q3_currentTrace.startSolid = qTrue;
479 if (!getOut)
480 cm_q3_currentTrace.allSolid = qTrue;
481 return;
482 }
483
484 if (enterFrac-(1.0f/1024.0f) <= leaveFrac) {
485 if (enterFrac > -1 && enterFrac < cm_q3_currentTrace.fraction) {
486 if (enterFrac < 0)
487 enterFrac = 0;
488 cm_q3_currentTrace.fraction = enterFrac;
489 cm_q3_currentTrace.plane = *clipPlane;
490 cm_q3_currentTrace.surface = leadSide->surface;
491 cm_q3_currentTrace.contents = brush->contents;
492 }
493 }
494 }
495
496
497 /*
498 ================
499 CM_Q3BSP_ClipBoxes
500 ================
501 */
CM_Q3BSP_ClipBoxes(int leafNum)502 static void CM_Q3BSP_ClipBoxes (int leafNum)
503 {
504 int i, j;
505 int brushNum, patchNum;
506 cleaf_t *leaf;
507 cbrush_t *brush;
508 cpatch_t *patch;
509
510 leaf = &cm_q3_leafs[leafNum];
511 if (!(leaf->contents & cm_q3_traceContents))
512 return;
513
514 // Trace line against all brushes in the leaf
515 for (i=0 ; i<leaf->numLeafBrushes ; i++) {
516 brushNum = cm_q3_leafBrushes[leaf->firstLeafBrush+i];
517 brush = &cm_q3_brushes[brushNum];
518
519 if (brush->checkCount == cm_q3_checkCount)
520 continue; // Already checked this brush in another leaf
521 brush->checkCount = cm_q3_checkCount;
522 if (!(brush->contents & cm_q3_traceContents))
523 continue;
524
525 CM_Q3BSP_ClipBoxToBrush (brush);
526 if (!cm_q3_currentTrace.fraction)
527 return;
528 }
529
530 if (cm_noCurves->intVal)
531 return;
532
533 // Trace line against all patches in the leaf
534 for (i=0 ; i<leaf->numLeafPatches ; i++) {
535 patchNum = cm_q3_leafPatches[leaf->firstLeafPatch+i];
536 patch = &cm_q3_patches[patchNum];
537
538 if (patch->checkCount == cm_q3_checkCount)
539 continue; // Already checked this patch in another leaf
540 patch->checkCount = cm_q3_checkCount;
541 if (!(patch->surface->contents & cm_q3_traceContents))
542 continue;
543 if (!BoundsIntersect(patch->absMins, patch->absMaxs, cm_q3_traceAbsMins, cm_q3_traceAbsMaxs))
544 continue;
545
546 for (j=0 ; j<patch->numBrushes ; j++) {
547 CM_Q3BSP_ClipBoxToBrush (&patch->brushes[j]);
548 if (!cm_q3_currentTrace.fraction)
549 return;
550 }
551 }
552 }
553
554
555 /*
556 ================
557 CM_Q3BSP_TestBoxInBrush
558 ================
559 */
CM_Q3BSP_TestBoxInBrush(cbrush_t * brush)560 static void CM_Q3BSP_TestBoxInBrush (cbrush_t *brush)
561 {
562 int i;
563 cBspPlane_t *p;
564 cbrushside_t *side;
565
566 if (!brush->numSides)
567 return;
568
569 for (i=0, side=&cm_q3_brushSides[brush->firstBrushSide] ; i<brush->numSides ; side++, i++) {
570 p = side->plane;
571
572 // Push the plane out apropriately for mins/maxs
573 // if completely in front of face, no intersection
574 if (p->type < 3) {
575 if (cm_q3_traceStartMins[p->type] > p->dist)
576 return;
577 }
578 else {
579 switch (p->signBits) {
580 case 0:
581 if (p->normal[0]*cm_q3_traceStartMins[0] + p->normal[1]*cm_q3_traceStartMins[1] + p->normal[2]*cm_q3_traceStartMins[2] > p->dist)
582 return;
583 break;
584 case 1:
585 if (p->normal[0]*cm_q3_traceStartMaxs[0] + p->normal[1]*cm_q3_traceStartMins[1] + p->normal[2]*cm_q3_traceStartMins[2] > p->dist)
586 return;
587 break;
588 case 2:
589 if (p->normal[0]*cm_q3_traceStartMins[0] + p->normal[1]*cm_q3_traceStartMaxs[1] + p->normal[2]*cm_q3_traceStartMins[2] > p->dist)
590 return;
591 break;
592 case 3:
593 if (p->normal[0]*cm_q3_traceStartMaxs[0] + p->normal[1]*cm_q3_traceStartMaxs[1] + p->normal[2]*cm_q3_traceStartMins[2] > p->dist)
594 return;
595 break;
596 case 4:
597 if (p->normal[0]*cm_q3_traceStartMins[0] + p->normal[1]*cm_q3_traceStartMins[1] + p->normal[2]*cm_q3_traceStartMaxs[2] > p->dist)
598 return;
599 break;
600 case 5:
601 if (p->normal[0]*cm_q3_traceStartMaxs[0] + p->normal[1]*cm_q3_traceStartMins[1] + p->normal[2]*cm_q3_traceStartMaxs[2] > p->dist)
602 return;
603 break;
604 case 6:
605 if (p->normal[0]*cm_q3_traceStartMins[0] + p->normal[1]*cm_q3_traceStartMaxs[1] + p->normal[2]*cm_q3_traceStartMaxs[2] > p->dist)
606 return;
607 break;
608 case 7:
609 if (p->normal[0]*cm_q3_traceStartMaxs[0] + p->normal[1]*cm_q3_traceStartMaxs[1] + p->normal[2]*cm_q3_traceStartMaxs[2] > p->dist)
610 return;
611 break;
612 default:
613 assert (0);
614 return;
615 }
616 }
617 }
618
619 // Inside this brush
620 cm_q3_currentTrace.startSolid = cm_q3_currentTrace.allSolid = qTrue;
621 cm_q3_currentTrace.fraction = 0;
622 cm_q3_currentTrace.contents = brush->contents;
623 }
624
625
626 /*
627 ================
628 CM_Q3BSP_TestBoxInLeaf
629 ================
630 */
CM_Q3BSP_TestBoxInLeaf(int leafNum)631 static void CM_Q3BSP_TestBoxInLeaf (int leafNum)
632 {
633 int i, j;
634 int brushNum, patchNum;
635 cleaf_t *leaf;
636 cbrush_t *brush;
637 cpatch_t *patch;
638
639 leaf = &cm_q3_leafs[leafNum];
640 if (!(leaf->contents & cm_q3_traceContents))
641 return;
642
643 // Trace line against all brushes in the leaf
644 for (i=0 ; i<leaf->numLeafBrushes ; i++) {
645 brushNum = cm_q3_leafBrushes[leaf->firstLeafBrush+i];
646 brush = &cm_q3_brushes[brushNum];
647
648 if (brush->checkCount == cm_q3_checkCount)
649 continue; // Already checked this brush in another leaf
650 brush->checkCount = cm_q3_checkCount;
651 if (!(brush->contents & cm_q3_traceContents))
652 continue;
653
654 CM_Q3BSP_TestBoxInBrush (brush);
655 if (!cm_q3_currentTrace.fraction)
656 return;
657 }
658
659 if (cm_noCurves->intVal)
660 return;
661
662 // Trace line against all patches in the leaf
663 for (i=0 ; i<leaf->numLeafPatches ; i++) {
664 patchNum = cm_q3_leafPatches[leaf->firstLeafPatch+i];
665 patch = &cm_q3_patches[patchNum];
666
667 if (patch->checkCount == cm_q3_checkCount)
668 continue; // Already checked this patch in another leaf
669 patch->checkCount = cm_q3_checkCount;
670 if (!(patch->surface->contents & cm_q3_traceContents))
671 continue;
672 if (!BoundsIntersect(patch->absMins, patch->absMaxs, cm_q3_traceAbsMins, cm_q3_traceAbsMaxs))
673 continue;
674
675 for (j=0 ; j<patch->numBrushes; j++) {
676 CM_Q3BSP_TestBoxInBrush (&patch->brushes[j]);
677 if (!cm_q3_currentTrace.fraction)
678 return;
679 }
680 }
681 }
682
683
684 /*
685 ==================
686 CM_Q3BSP_RecursiveHullCheck
687 ==================
688 */
CM_Q3BSP_RecursiveHullCheck(int num,float p1f,float p2f,vec3_t p1,vec3_t p2)689 static void CM_Q3BSP_RecursiveHullCheck (int num, float p1f, float p2f, vec3_t p1, vec3_t p2)
690 {
691 cnode_t *node;
692 cBspPlane_t *plane;
693 float t1, t2, offset;
694 float frac, frac2;
695 float idist;
696 int i;
697 vec3_t mid;
698 int side;
699 float midf;
700
701 if (cm_q3_currentTrace.fraction <= p1f)
702 return; // Already hit something nearer
703
704 // If < 0, we are in a leaf node
705 if (num < 0) {
706 CM_Q3BSP_ClipBoxes (-1-num);
707 return;
708 }
709
710 //
711 // Find the point distances to the seperating plane
712 // and the offset for the size of the box
713 //
714 node = cm_q3_nodes + num;
715 plane = node->plane;
716
717 if (plane->type < 3) {
718 t1 = p1[plane->type] - plane->dist;
719 t2 = p2[plane->type] - plane->dist;
720 offset = cm_q3_traceExtents[plane->type];
721 }
722 else {
723 t1 = DotProduct (plane->normal, p1) - plane->dist;
724 t2 = DotProduct (plane->normal, p2) - plane->dist;
725 if (cm_q3_traceIsPoint)
726 offset = 0;
727 else
728 offset = fabs(cm_q3_traceExtents[0]*plane->normal[0])
729 + fabs(cm_q3_traceExtents[1]*plane->normal[1])
730 + fabs(cm_q3_traceExtents[2]*plane->normal[2]);
731 }
732
733
734 // See which sides we need to consider
735 if (t1 >= offset && t2 >= offset) {
736 CM_Q3BSP_RecursiveHullCheck (node->children[0], p1f, p2f, p1, p2);
737 return;
738 }
739 if (t1 < -offset && t2 < -offset) {
740 CM_Q3BSP_RecursiveHullCheck (node->children[1], p1f, p2f, p1, p2);
741 return;
742 }
743
744 // Put the crosspoint DIST_EPSILON pixels on the near side
745 if (t1 < t2) {
746 idist = 1.0/(t1-t2);
747 side = 1;
748 frac2 = (t1 + offset + DIST_EPSILON)*idist;
749 frac = (t1 - offset + DIST_EPSILON)*idist;
750 }
751 else if (t1 > t2) {
752 idist = 1.0/(t1-t2);
753 side = 0;
754 frac2 = (t1 - offset - DIST_EPSILON)*idist;
755 frac = (t1 + offset + DIST_EPSILON)*idist;
756 }
757 else {
758 side = 0;
759 frac = 1;
760 frac2 = 0;
761 }
762
763 // Move up to the node
764 if (frac < 0)
765 frac = 0;
766 if (frac > 1)
767 frac = 1;
768
769 midf = p1f + (p2f - p1f)*frac;
770 for (i=0 ; i<3 ; i++)
771 mid[i] = p1[i] + frac*(p2[i] - p1[i]);
772
773 CM_Q3BSP_RecursiveHullCheck (node->children[side], p1f, midf, p1, mid);
774
775 // Go past the node
776 if (frac2 < 0)
777 frac2 = 0;
778 if (frac2 > 1)
779 frac2 = 1;
780
781 midf = p1f + (p2f - p1f)*frac2;
782 for (i=0 ; i<3 ; i++)
783 mid[i] = p1[i] + frac2*(p2[i] - p1[i]);
784
785 CM_Q3BSP_RecursiveHullCheck (node->children[side^1], midf, p2f, mid, p2);
786 }
787
788 // ==========================================================================
789
790 /*
791 ====================
792 CM_Q3BSP_Trace
793 ====================
794 */
CM_Q3BSP_Trace(vec3_t start,vec3_t end,float size,int contentMask)795 trace_t CM_Q3BSP_Trace (vec3_t start, vec3_t end, float size, int contentMask)
796 {
797 vec3_t maxs, mins;
798
799 Vec3Set (maxs, size, size, size);
800 Vec3Set (mins, -size, -size, -size);
801
802 return CM_Q3BSP_BoxTrace (start, end, mins, maxs, 0, contentMask);
803 }
804
805
806 /*
807 ==================
808 CM_Q3BSP_BoxTrace
809 ==================
810 */
CM_Q3BSP_BoxTrace(vec3_t start,vec3_t end,vec3_t mins,vec3_t maxs,int headNode,int brushMask)811 trace_t CM_Q3BSP_BoxTrace (vec3_t start, vec3_t end, vec3_t mins, vec3_t maxs, int headNode, int brushMask)
812 {
813 cm_q3_checkCount++; // For multi-check avoidance
814 cm_numTraces++; // For statistics, may be zeroed
815
816 // Fill in a default trace
817 cm_q3_currentTrace.allSolid = qFalse;
818 cm_q3_currentTrace.contents = 0;
819 Vec3Clear (cm_q3_currentTrace.endPos);
820 cm_q3_currentTrace.ent = NULL;
821 cm_q3_currentTrace.fraction = 1;
822 cm_q3_currentTrace.plane.dist = 0;
823 Vec3Clear (cm_q3_currentTrace.plane.normal);
824 cm_q3_currentTrace.plane.signBits = 0;
825 cm_q3_currentTrace.plane.type = 0;
826 cm_q3_currentTrace.startSolid = qFalse;
827 cm_q3_currentTrace.surface = &cm_q3_nullSurface;
828
829 if (!cm_q3_numNodes) // map not loaded
830 return cm_q3_currentTrace;
831
832 cm_q3_traceContents = brushMask;
833 Vec3Copy (start, cm_q3_traceStart);
834 Vec3Copy (end, cm_q3_traceEnd);
835 Vec3Copy (mins, cm_q3_traceMins);
836 Vec3Copy (maxs, cm_q3_traceMaxs);
837
838 // Build a bounding box of the entire move
839 ClearBounds (cm_q3_traceAbsMins, cm_q3_traceAbsMaxs);
840 Vec3Add (start, cm_q3_traceMins, cm_q3_traceStartMins);
841 AddPointToBounds (cm_q3_traceStartMins, cm_q3_traceAbsMins, cm_q3_traceAbsMaxs);
842 Vec3Add (start, cm_q3_traceMaxs, cm_q3_traceStartMaxs);
843 AddPointToBounds (cm_q3_traceStartMaxs, cm_q3_traceAbsMins, cm_q3_traceAbsMaxs);
844 Vec3Add (end, cm_q3_traceMins, cm_q3_traceEndMins);
845 AddPointToBounds (cm_q3_traceEndMins, cm_q3_traceAbsMins, cm_q3_traceAbsMaxs);
846 Vec3Add (end, cm_q3_traceMaxs, cm_q3_traceEndMaxs);
847 AddPointToBounds (cm_q3_traceEndMaxs, cm_q3_traceAbsMins, cm_q3_traceAbsMaxs);
848
849 // Check for position test special case
850 if (start[0] == end[0] && start[1] == end[1] && start[2] == end[2]) {
851 int leafs[1024];
852 int i, numLeafs;
853 vec3_t c1, c2;
854 int topnode;
855
856 Vec3Add (start, mins, c1);
857 Vec3Add (start, maxs, c2);
858 for (i=0 ; i<3 ; i++) {
859 c1[i] -= 1;
860 c2[i] += 1;
861 }
862
863 numLeafs = CM_Q3BSP_BoxLeafnums_headnode (c1, c2, leafs, 1024, headNode, &topnode);
864 for (i=0 ; i<numLeafs ; i++) {
865 CM_Q3BSP_TestBoxInLeaf (leafs[i]);
866 if (cm_q3_currentTrace.allSolid)
867 break;
868 }
869 Vec3Copy (start, cm_q3_currentTrace.endPos);
870 return cm_q3_currentTrace;
871 }
872
873 // Check for point special case
874 if (mins[0] == 0 && mins[1] == 0 && mins[2] == 0 && maxs[0] == 0 && maxs[1] == 0 && maxs[2] == 0) {
875 cm_q3_traceIsPoint = qTrue;
876 Vec3Clear (cm_q3_traceExtents);
877 }
878 else {
879 cm_q3_traceIsPoint = qFalse;
880 cm_q3_traceExtents[0] = -mins[0] > maxs[0] ? -mins[0] : maxs[0];
881 cm_q3_traceExtents[1] = -mins[1] > maxs[1] ? -mins[1] : maxs[1];
882 cm_q3_traceExtents[2] = -mins[2] > maxs[2] ? -mins[2] : maxs[2];
883 }
884
885 // General sweeping through world
886 CM_Q3BSP_RecursiveHullCheck (headNode, 0, 1, start, end);
887
888 if (cm_q3_currentTrace.fraction == 1) {
889 Vec3Copy (end, cm_q3_currentTrace.endPos);
890 }
891 else {
892 cm_q3_currentTrace.endPos[0] = start[0] + cm_q3_currentTrace.fraction * (end[0] - start[0]);
893 cm_q3_currentTrace.endPos[1] = start[1] + cm_q3_currentTrace.fraction * (end[1] - start[1]);
894 cm_q3_currentTrace.endPos[2] = start[2] + cm_q3_currentTrace.fraction * (end[2] - start[2]);
895 }
896 return cm_q3_currentTrace;
897 }
898
899
900 /*
901 ==================
902 CM_Q3BSP_TransformedBoxTrace
903 ==================
904 */
905 #ifdef WIN32
906 #pragma optimize( "", off )
907 #endif
CM_Q3BSP_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)908 void CM_Q3BSP_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)
909 {
910 vec3_t start_l, end_l;
911 vec3_t a;
912 vec3_t forward, right, up;
913 vec3_t temp;
914 qBool rotated;
915
916 // Subtract origin offset
917 Vec3Subtract (start, origin, start_l);
918 Vec3Subtract (end, origin, end_l);
919
920 // Rotate start and end into the models frame of reference
921 if (headNode != cm_q3_boxHeadNode && (angles[0] || angles[1] || angles[2]))
922 rotated = qTrue;
923 else
924 rotated = qFalse;
925
926 if (rotated) {
927 Angles_Vectors (angles, forward, right, up);
928
929 Vec3Copy (start_l, temp);
930 start_l[0] = DotProduct (temp, forward);
931 start_l[1] = -DotProduct (temp, right);
932 start_l[2] = DotProduct (temp, up);
933
934 Vec3Copy (end_l, temp);
935 end_l[0] = DotProduct (temp, forward);
936 end_l[1] = -DotProduct (temp, right);
937 end_l[2] = DotProduct (temp, up);
938 }
939
940 // Sweep the box through the model
941 *out = CM_Q3BSP_BoxTrace (start_l, end_l, mins, maxs, headNode, brushMask);
942
943 if (rotated && out->fraction != 1.0) {
944 // FIXME: figure out how to do this with existing angles
945 Vec3Negate (angles, a);
946 Angles_Vectors (a, forward, right, up);
947
948 Vec3Copy (out->plane.normal, temp);
949 out->plane.normal[0] = DotProduct (temp, forward);
950 out->plane.normal[1] = -DotProduct (temp, right);
951 out->plane.normal[2] = DotProduct (temp, up);
952 }
953
954 out->endPos[0] = start[0] + out->fraction * (end[0] - start[0]);
955 out->endPos[1] = start[1] + out->fraction * (end[1] - start[1]);
956 out->endPos[2] = start[2] + out->fraction * (end[2] - start[2]);
957 }
958 #ifdef WIN32
959 #pragma optimize( "", on )
960 #endif
961
962 /*
963 =============================================================================
964
965 PVS / PHS
966
967 =============================================================================
968 */
969
970 /*
971 ===================
972 CM_Q3BSP_ClusterPVS
973 ===================
974 */
CM_Q3BSP_ClusterPVS(int cluster)975 byte *CM_Q3BSP_ClusterPVS (int cluster)
976 {
977 if (cluster != -1 && cm_q3_visData && cm_q3_visData->numClusters)
978 return (byte *)cm_q3_visData->data + cluster * cm_q3_visData->rowSize;
979
980 return cm_q3_nullRow;
981 }
982
983
984 /*
985 ===================
986 CM_Q3BSP_ClusterPHS
987 ===================
988 */
CM_Q3BSP_ClusterPHS(int cluster)989 byte *CM_Q3BSP_ClusterPHS (int cluster)
990 {
991 if (cluster != -1 && cm_q3_hearData && cm_q3_hearData->numClusters)
992 return (byte *)cm_q3_hearData->data + cluster * cm_q3_hearData->rowSize;
993
994 return cm_q3_nullRow;
995 }
996
997 /*
998 =============================================================================
999
1000 AREAPORTALS
1001
1002 =============================================================================
1003 */
1004
1005 /*
1006 =================
1007 CM_Q3BSP_AddAreaPortal
1008 =================
1009 */
CM_Q3BSP_AddAreaPortal(int portalNum,int area,int otherArea)1010 static qBool CM_Q3BSP_AddAreaPortal (int portalNum, int area, int otherArea)
1011 {
1012 carea_t *a;
1013 careaportal_t *ap;
1014
1015 if (portalNum >= MAX_Q3BSP_CM_AREAPORTALS)
1016 return qFalse;
1017 if (!area || area > cm_q3_numAreas || !otherArea || otherArea > cm_q3_numAreas)
1018 return qFalse;
1019
1020 ap = &cm_q3_areaPortals[portalNum];
1021 ap->area = area;
1022 ap->otherArea = otherArea;
1023
1024 a = &cm_q3_areas[area];
1025 a->areaPortals[a->numAreaPortals++] = portalNum;
1026
1027 a = &cm_q3_areas[otherArea];
1028 a->areaPortals[a->numAreaPortals++] = portalNum;
1029
1030 cm_q3_numAreaPortals++;
1031 return qTrue;
1032 }
1033
1034
1035 /*
1036 =================
1037 CM_Q3BSP_FloodArea_r
1038 =================
1039 */
CM_Q3BSP_FloodArea_r(int areaNum,int floodNum)1040 static void CM_Q3BSP_FloodArea_r (int areaNum, int floodNum)
1041 {
1042 int i;
1043 carea_t *area;
1044 careaportal_t *p;
1045
1046 area = &cm_q3_areas[areaNum];
1047 if (area->floodValid == cm_q3_floodValid) {
1048 if (area->floodNum == floodNum)
1049 return;
1050 Com_Error (ERR_DROP, "CM_Q3BSP_FloodArea_r: reflooded");
1051 }
1052
1053 area->floodNum = floodNum;
1054 area->floodValid = cm_q3_floodValid;
1055 for (i=0 ; i<area->numAreaPortals ; i++) {
1056 p = &cm_q3_areaPortals[area->areaPortals[i]];
1057 if (!p->open)
1058 continue;
1059
1060 if (p->area == areaNum)
1061 CM_Q3BSP_FloodArea_r (p->otherArea, floodNum);
1062 else if (p->otherArea == areaNum)
1063 CM_Q3BSP_FloodArea_r (p->area, floodNum);
1064 }
1065 }
1066
1067
1068 /*
1069 ====================
1070 CM_Q3BSP_FloodAreaConnections
1071 ====================
1072 */
CM_Q3BSP_FloodAreaConnections(void)1073 void CM_Q3BSP_FloodAreaConnections (void)
1074 {
1075 int i;
1076 int floodNum;
1077
1078 // All current floods are now invalid
1079 cm_q3_floodValid++;
1080 floodNum = 0;
1081
1082 // Area 0 is not used
1083 for (i=1 ; i<cm_q3_numAreas ; i++) {
1084 if (cm_q3_areas[i].floodValid == cm_q3_floodValid)
1085 continue; // already flooded into
1086 floodNum++;
1087 CM_Q3BSP_FloodArea_r (i, floodNum);
1088 }
1089 }
1090
1091
1092 /*
1093 ====================
1094 CM_Q3BSP_SetAreaPortalState
1095 ====================
1096 */
CM_Q3BSP_SetAreaPortalState(int portalNum,int area,int otherArea,qBool open)1097 void CM_Q3BSP_SetAreaPortalState (int portalNum, int area, int otherArea, qBool open)
1098 {
1099 if (portalNum >= MAX_Q3BSP_CM_AREAPORTALS)
1100 Com_Error (ERR_DROP, "portalNum >= MAX_Q3BSP_CM_AREAPORTALS");
1101
1102 if (!cm_q3_areaPortals[portalNum].area) {
1103 // Add new areaportal if it doesn't exist
1104 if (!CM_Q3BSP_AddAreaPortal (portalNum, area, otherArea))
1105 return;
1106 }
1107
1108 cm_q3_areaPortals[portalNum].open = open;
1109 CM_Q3BSP_FloodAreaConnections ();
1110 }
1111
1112
1113 /*
1114 ====================
1115 CM_Q3BSP_AreasConnected
1116 ====================
1117 */
CM_Q3BSP_AreasConnected(int area1,int area2)1118 qBool CM_Q3BSP_AreasConnected (int area1, int area2)
1119 {
1120 if (cm_noAreas->intVal)
1121 return qTrue;
1122 if (area1 > cm_q3_numAreas || area2 > cm_q3_numAreas)
1123 Com_Error (ERR_DROP, "CM_AreasConnected: area > cm_q3_numAreas");
1124
1125 if (cm_q3_areas[area1].floodNum == cm_q3_areas[area2].floodNum)
1126 return qTrue;
1127 return qFalse;
1128 }
1129
1130
1131 /*
1132 =================
1133 CM_Q3BSP_WriteAreaBits
1134 =================
1135 */
CM_Q3BSP_WriteAreaBits(byte * buffer,int area)1136 int CM_Q3BSP_WriteAreaBits (byte *buffer, int area)
1137 {
1138 int i;
1139 int bytes;
1140
1141 bytes = (cm_q3_numAreas+7)>>3;
1142
1143 if (cm_noAreas->intVal) {
1144 // For debugging, send everything
1145 memset (buffer, 255, bytes);
1146 }
1147 else {
1148 memset (buffer, 0, bytes);
1149
1150 for (i=1 ; i<cm_q3_numAreas ; i++) {
1151 if (!area || CM_AreasConnected ( i, area ) || i == area)
1152 buffer[i>>3] |= 1<<(i&7);
1153 }
1154 }
1155
1156 return bytes;
1157 }
1158
1159
1160 /*
1161 ===================
1162 CM_Q3BSP_WritePortalState
1163 ===================
1164 */
CM_Q3BSP_WritePortalState(fileHandle_t fileNum)1165 void CM_Q3BSP_WritePortalState (fileHandle_t fileNum)
1166 {
1167 }
1168
1169
1170 /*
1171 ===================
1172 CM_Q3BSP_ReadPortalState
1173 ===================
1174 */
CM_Q3BSP_ReadPortalState(fileHandle_t fileNum)1175 void CM_Q3BSP_ReadPortalState (fileHandle_t fileNum)
1176 {
1177 }
1178
1179
1180 /*
1181 =============
1182 CM_Q3BSP_HeadnodeVisible
1183 =============
1184 */
CM_Q3BSP_HeadnodeVisible(int nodeNum,byte * visBits)1185 qBool CM_Q3BSP_HeadnodeVisible (int nodeNum, byte *visBits)
1186 {
1187 int leafNum;
1188 int cluster;
1189 cnode_t *node;
1190
1191 if (nodeNum < 0) {
1192 leafNum = -1-nodeNum;
1193 cluster = cm_q3_leafs[leafNum].cluster;
1194 if (cluster == -1)
1195 return qFalse;
1196 if (visBits[cluster>>3] & (1<<(cluster&7)))
1197 return qTrue;
1198 return qFalse;
1199 }
1200
1201 node = &cm_q3_nodes[nodeNum];
1202 if (CM_HeadnodeVisible(node->children[0], visBits))
1203 return qTrue;
1204 return CM_HeadnodeVisible(node->children[1], visBits);
1205 }
1206