1 /*
2 ===========================================================================
3
4 Return to Castle Wolfenstein multiplayer GPL Source Code
5 Copyright (C) 1999-2010 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Return to Castle Wolfenstein multiplayer GPL Source Code (RTCW MP Source Code).
8
9 RTCW MP 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 RTCW MP 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 RTCW MP Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the RTCW MP 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 RTCW MP 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 "cm_local.h"
30
31
32 /*
33 ==================
34 CM_PointLeafnum_r
35
36 ==================
37 */
CM_PointLeafnum_r(const vec3_t p,int num)38 int CM_PointLeafnum_r( const vec3_t p, int num ) {
39 float d;
40 cNode_t *node;
41 cplane_t *plane;
42
43 while ( num >= 0 )
44 {
45 node = cm.nodes + num;
46 plane = node->plane;
47
48 if ( plane->type < 3 ) {
49 d = p[plane->type] - plane->dist;
50 } else {
51 d = DotProduct( plane->normal, p ) - plane->dist;
52 }
53 if ( d < 0 ) {
54 num = node->children[1];
55 } else {
56 num = node->children[0];
57 }
58 }
59
60 c_pointcontents++; // optimize counter
61
62 return -1 - num;
63 }
64
CM_PointLeafnum(const vec3_t p)65 int CM_PointLeafnum( const vec3_t p ) {
66 if ( !cm.numNodes ) { // map not loaded
67 return 0;
68 }
69 return CM_PointLeafnum_r( p, 0 );
70 }
71
72
73 /*
74 ======================================================================
75
76 LEAF LISTING
77
78 ======================================================================
79 */
80
81
CM_StoreLeafs(leafList_t * ll,int nodenum)82 void CM_StoreLeafs( leafList_t *ll, int nodenum ) {
83 int leafNum;
84
85 leafNum = -1 - nodenum;
86
87 // store the lastLeaf even if the list is overflowed
88 if ( cm.leafs[ leafNum ].cluster != -1 ) {
89 ll->lastLeaf = leafNum;
90 }
91
92 if ( ll->count >= ll->maxcount ) {
93 ll->overflowed = qtrue;
94 return;
95 }
96 ll->list[ ll->count++ ] = leafNum;
97 }
98
CM_StoreBrushes(leafList_t * ll,int nodenum)99 void CM_StoreBrushes( leafList_t *ll, int nodenum ) {
100 int i, k;
101 int leafnum;
102 int brushnum;
103 cLeaf_t *leaf;
104 cbrush_t *b;
105
106 leafnum = -1 - nodenum;
107
108 leaf = &cm.leafs[leafnum];
109
110 for ( k = 0 ; k < leaf->numLeafBrushes ; k++ ) {
111 brushnum = cm.leafbrushes[leaf->firstLeafBrush + k];
112 b = &cm.brushes[brushnum];
113 if ( b->checkcount == cm.checkcount ) {
114 continue; // already checked this brush in another leaf
115 }
116 b->checkcount = cm.checkcount;
117 for ( i = 0 ; i < 3 ; i++ ) {
118 if ( b->bounds[0][i] >= ll->bounds[1][i] || b->bounds[1][i] <= ll->bounds[0][i] ) {
119 break;
120 }
121 }
122 if ( i != 3 ) {
123 continue;
124 }
125 if ( ll->count >= ll->maxcount ) {
126 ll->overflowed = qtrue;
127 return;
128 }
129 ( (cbrush_t **)ll->list )[ ll->count++ ] = b;
130 }
131 #if 0
132 // store patches?
133 for ( k = 0 ; k < leaf->numLeafSurfaces ; k++ ) {
134 patch = cm.surfaces[ cm.leafsurfaces[ leaf->firstleafsurface + k ] ];
135 if ( !patch ) {
136 continue;
137 }
138 }
139 #endif
140 }
141
142 /*
143 =============
144 CM_BoxLeafnums
145
146 Fills in a list of all the leafs touched
147 =============
148 */
CM_BoxLeafnums_r(leafList_t * ll,int nodenum)149 void CM_BoxLeafnums_r( leafList_t *ll, int nodenum ) {
150 cplane_t *plane;
151 cNode_t *node;
152 int s;
153
154 while ( 1 ) {
155 if ( nodenum < 0 ) {
156 ll->storeLeafs( ll, nodenum );
157 return;
158 }
159
160 node = &cm.nodes[nodenum];
161 plane = node->plane;
162 s = BoxOnPlaneSide( ll->bounds[0], ll->bounds[1], plane );
163 if ( s == 1 ) {
164 nodenum = node->children[0];
165 } else if ( s == 2 ) {
166 nodenum = node->children[1];
167 } else {
168 // go down both
169 CM_BoxLeafnums_r( ll, node->children[0] );
170 nodenum = node->children[1];
171 }
172
173 }
174 }
175
176 /*
177 ==================
178 CM_BoxLeafnums
179 ==================
180 */
CM_BoxLeafnums(const vec3_t mins,const vec3_t maxs,int * list,int listsize,int * lastLeaf)181 int CM_BoxLeafnums( const vec3_t mins, const vec3_t maxs, int *list, int listsize, int *lastLeaf ) {
182 leafList_t ll;
183
184 cm.checkcount++;
185
186 VectorCopy( mins, ll.bounds[0] );
187 VectorCopy( maxs, ll.bounds[1] );
188 ll.count = 0;
189 ll.maxcount = listsize;
190 ll.list = list;
191 ll.storeLeafs = CM_StoreLeafs;
192 ll.lastLeaf = 0;
193 ll.overflowed = qfalse;
194
195 CM_BoxLeafnums_r( &ll, 0 );
196
197 *lastLeaf = ll.lastLeaf;
198 return ll.count;
199 }
200
201 /*
202 ==================
203 CM_BoxBrushes
204 ==================
205 */
CM_BoxBrushes(const vec3_t mins,const vec3_t maxs,cbrush_t ** list,int listsize)206 int CM_BoxBrushes( const vec3_t mins, const vec3_t maxs, cbrush_t **list, int listsize ) {
207 leafList_t ll;
208
209 cm.checkcount++;
210
211 VectorCopy( mins, ll.bounds[0] );
212 VectorCopy( maxs, ll.bounds[1] );
213 ll.count = 0;
214 ll.maxcount = listsize;
215 ll.list = (void *)list;
216 ll.storeLeafs = CM_StoreBrushes;
217 ll.lastLeaf = 0;
218 ll.overflowed = qfalse;
219
220 CM_BoxLeafnums_r( &ll, 0 );
221
222 return ll.count;
223 }
224
225
226 //====================================================================
227
228
229 /*
230 ==================
231 CM_PointContents
232
233 ==================
234 */
CM_PointContents(const vec3_t p,clipHandle_t model)235 int CM_PointContents( const vec3_t p, clipHandle_t model ) {
236 int leafnum;
237 int i, k;
238 int brushnum;
239 cLeaf_t *leaf;
240 cbrush_t *b;
241 int contents;
242 float d;
243 cmodel_t *clipm;
244
245 if ( !cm.numNodes ) { // map not loaded
246 return 0;
247 }
248
249 if ( model ) {
250 clipm = CM_ClipHandleToModel( model );
251 leaf = &clipm->leaf;
252 } else {
253 leafnum = CM_PointLeafnum_r( p, 0 );
254 leaf = &cm.leafs[leafnum];
255 }
256
257 contents = 0;
258 for ( k = 0 ; k < leaf->numLeafBrushes ; k++ ) {
259 brushnum = cm.leafbrushes[leaf->firstLeafBrush + k];
260 b = &cm.brushes[brushnum];
261
262 if ( !CM_BoundsIntersectPoint( b->bounds[0], b->bounds[1], p ) ) {
263 continue;
264 }
265
266 // see if the point is in the brush
267 for ( i = 0 ; i < b->numsides ; i++ ) {
268 d = DotProduct( p, b->sides[i].plane->normal );
269 // FIXME test for Cash
270 // if ( d >= b->sides[i].plane->dist ) {
271 if ( d > b->sides[i].plane->dist ) {
272 break;
273 }
274 }
275
276 if ( i == b->numsides ) {
277 contents |= b->contents;
278 }
279 }
280
281 return contents;
282 }
283
284 /*
285 ==================
286 CM_TransformedPointContents
287
288 Handles offseting and rotation of the end points for moving and
289 rotating entities
290 ==================
291 */
CM_TransformedPointContents(const vec3_t p,clipHandle_t model,const vec3_t origin,const vec3_t angles)292 int CM_TransformedPointContents( const vec3_t p, clipHandle_t model, const vec3_t origin, const vec3_t angles ) {
293 vec3_t p_l;
294 vec3_t temp;
295 vec3_t forward, right, up;
296
297 // subtract origin offset
298 VectorSubtract( p, origin, p_l );
299
300 // rotate start and end into the models frame of reference
301 if ( model != BOX_MODEL_HANDLE &&
302 ( angles[0] || angles[1] || angles[2] ) ) {
303 AngleVectors( angles, forward, right, up );
304
305 VectorCopy( p_l, temp );
306 p_l[0] = DotProduct( temp, forward );
307 p_l[1] = -DotProduct( temp, right );
308 p_l[2] = DotProduct( temp, up );
309 }
310
311 return CM_PointContents( p_l, model );
312 }
313
314
315
316 /*
317 ===============================================================================
318
319 PVS
320
321 ===============================================================================
322 */
323
CM_ClusterPVS(int cluster)324 byte *CM_ClusterPVS( int cluster ) {
325 if ( cluster < 0 || cluster >= cm.numClusters || !cm.vised ) {
326 return cm.visibility;
327 }
328
329 return cm.visibility + cluster * cm.clusterBytes;
330 }
331
332
333
334 /*
335 ===============================================================================
336
337 AREAPORTALS
338
339 ===============================================================================
340 */
341
CM_FloodArea_r(int areaNum,int floodnum)342 void CM_FloodArea_r( int areaNum, int floodnum ) {
343 int i;
344 cArea_t *area;
345 int *con;
346
347 area = &cm.areas[ areaNum ];
348
349 if ( area->floodvalid == cm.floodvalid ) {
350 if ( area->floodnum == floodnum ) {
351 return;
352 }
353 Com_Error( ERR_DROP, "FloodArea_r: reflooded" );
354 }
355
356 area->floodnum = floodnum;
357 area->floodvalid = cm.floodvalid;
358 con = cm.areaPortals + areaNum * cm.numAreas;
359 for ( i = 0 ; i < cm.numAreas ; i++ ) {
360 if ( con[i] > 0 ) {
361 CM_FloodArea_r( i, floodnum );
362 }
363 }
364 }
365
366 /*
367 ====================
368 CM_FloodAreaConnections
369
370 ====================
371 */
CM_FloodAreaConnections(void)372 void CM_FloodAreaConnections( void ) {
373 int i;
374 cArea_t *area;
375 int floodnum;
376
377 // all current floods are now invalid
378 cm.floodvalid++;
379 floodnum = 0;
380
381 area = cm.areas; // Ridah, optimization
382 for ( i = 0 ; i < cm.numAreas ; i++, area++ ) {
383 if ( area->floodvalid == cm.floodvalid ) {
384 continue; // already flooded into
385 }
386 floodnum++;
387 CM_FloodArea_r( i, floodnum );
388 }
389
390 }
391
392 /*
393 ====================
394 CM_AdjustAreaPortalState
395
396 ====================
397 */
CM_AdjustAreaPortalState(int area1,int area2,qboolean open)398 void CM_AdjustAreaPortalState( int area1, int area2, qboolean open ) {
399 if ( area1 < 0 || area2 < 0 ) {
400 return;
401 }
402
403 if ( area1 >= cm.numAreas || area2 >= cm.numAreas ) {
404 Com_Error( ERR_DROP, "CM_ChangeAreaPortalState: bad area number" );
405 }
406
407 if ( open ) {
408 cm.areaPortals[ area1 * cm.numAreas + area2 ]++;
409 cm.areaPortals[ area2 * cm.numAreas + area1 ]++;
410 } else if ( cm.areaPortals[ area2 * cm.numAreas + area1 ] ) { // Ridah, fixes loadgame issue
411 cm.areaPortals[ area1 * cm.numAreas + area2 ]--;
412 cm.areaPortals[ area2 * cm.numAreas + area1 ]--;
413 if ( cm.areaPortals[ area2 * cm.numAreas + area1 ] < 0 ) {
414 Com_Error( ERR_DROP, "CM_AdjustAreaPortalState: negative reference count" );
415 }
416 }
417
418 CM_FloodAreaConnections();
419 }
420
421 /*
422 ====================
423 CM_AreasConnected
424
425 ====================
426 */
CM_AreasConnected(int area1,int area2)427 qboolean CM_AreasConnected( int area1, int area2 ) {
428 #ifndef BSPC
429 if ( cm_noAreas->integer ) {
430 return qtrue;
431 }
432 #endif
433
434 if ( area1 < 0 || area2 < 0 ) {
435 return qfalse;
436 }
437
438 if ( area1 >= cm.numAreas || area2 >= cm.numAreas ) {
439 Com_Error( ERR_DROP, "area >= cm.numAreas" );
440 }
441
442 if ( cm.areas[area1].floodnum == cm.areas[area2].floodnum ) {
443 return qtrue;
444 }
445 return qfalse;
446 }
447
448
449 /*
450 =================
451 CM_WriteAreaBits
452
453 Writes a bit vector of all the areas
454 that are in the same flood as the area parameter
455 Returns the number of bytes needed to hold all the bits.
456
457 The bits are OR'd in, so you can CM_WriteAreaBits from multiple
458 viewpoints and get the union of all visible areas.
459
460 This is used to cull non-visible entities from snapshots
461 =================
462 */
CM_WriteAreaBits(byte * buffer,int area)463 int CM_WriteAreaBits( byte *buffer, int area ) {
464 int i;
465 int floodnum;
466 int bytes;
467
468 bytes = ( cm.numAreas + 7 ) >> 3;
469
470 #ifndef BSPC
471 if ( cm_noAreas->integer || area == -1 )
472 #else
473 if ( area == -1 )
474 #endif
475 { // for debugging, send everything
476 memset( buffer, 255, bytes );
477 } else
478 {
479 floodnum = cm.areas[area].floodnum;
480 for ( i = 0 ; i < cm.numAreas ; i++ )
481 {
482 if ( cm.areas[i].floodnum == floodnum || area == -1 ) {
483 buffer[i >> 3] |= 1 << ( i & 7 );
484 }
485 }
486 }
487
488 return bytes;
489 }
490
491 /*
492 ====================
493 CM_BoundsIntersect
494 ====================
495 */
CM_BoundsIntersect(const vec3_t mins,const vec3_t maxs,const vec3_t mins2,const vec3_t maxs2)496 qboolean CM_BoundsIntersect( const vec3_t mins, const vec3_t maxs, const vec3_t mins2, const vec3_t maxs2 )
497 {
498 if (maxs[0] < mins2[0] - SURFACE_CLIP_EPSILON ||
499 maxs[1] < mins2[1] - SURFACE_CLIP_EPSILON ||
500 maxs[2] < mins2[2] - SURFACE_CLIP_EPSILON ||
501 mins[0] > maxs2[0] + SURFACE_CLIP_EPSILON ||
502 mins[1] > maxs2[1] + SURFACE_CLIP_EPSILON ||
503 mins[2] > maxs2[2] + SURFACE_CLIP_EPSILON)
504 {
505 return qfalse;
506 }
507
508 return qtrue;
509 }
510
511 /*
512 ====================
513 CM_BoundsIntersectPoint
514 ====================
515 */
CM_BoundsIntersectPoint(const vec3_t mins,const vec3_t maxs,const vec3_t point)516 qboolean CM_BoundsIntersectPoint( const vec3_t mins, const vec3_t maxs, const vec3_t point )
517 {
518 if (maxs[0] < point[0] - SURFACE_CLIP_EPSILON ||
519 maxs[1] < point[1] - SURFACE_CLIP_EPSILON ||
520 maxs[2] < point[2] - SURFACE_CLIP_EPSILON ||
521 mins[0] > point[0] + SURFACE_CLIP_EPSILON ||
522 mins[1] > point[1] + SURFACE_CLIP_EPSILON ||
523 mins[2] > point[2] + SURFACE_CLIP_EPSILON)
524 {
525 return qfalse;
526 }
527
528 return qtrue;
529 }
530