1 /*
2 ===========================================================================
3 Copyright (C) 1999-2005 Id Software, Inc.
4
5 This file is part of Quake III Arena source code.
6
7 Quake III Arena source code is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2 of the License,
10 or (at your option) any later version.
11
12 Quake III Arena source code is distributed in the hope that it will be
13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Quake III Arena source code; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 ===========================================================================
21 */
22 // world.c -- world query functions
23
24 #include "server.h"
25
26 /*
27 ================
28 SV_ClipHandleForEntity
29
30 Returns a headnode that can be used for testing or clipping to a
31 given entity. If the entity is a bsp model, the headnode will
32 be returned, otherwise a custom box tree will be constructed.
33 ================
34 */
SV_ClipHandleForEntity(const sharedEntity_t * ent)35 clipHandle_t SV_ClipHandleForEntity( const sharedEntity_t *ent ) {
36 if ( ent->r.bmodel ) {
37 // explicit hulls in the BSP model
38 return CM_InlineModel( ent->s.modelindex );
39 }
40 if ( ent->r.svFlags & SVF_CAPSULE ) {
41 // create a temp capsule from bounding box sizes
42 return CM_TempBoxModel( ent->r.mins, ent->r.maxs, qtrue );
43 }
44
45 // create a temp tree from bounding box sizes
46 return CM_TempBoxModel( ent->r.mins, ent->r.maxs, qfalse );
47 }
48
49
50
51 /*
52 ===============================================================================
53
54 ENTITY CHECKING
55
56 To avoid linearly searching through lists of entities during environment testing,
57 the world is carved up with an evenly spaced, axially aligned bsp tree. Entities
58 are kept in chains either at the final leafs, or at the first node that splits
59 them, which prevents having to deal with multiple fragments of a single entity.
60
61 ===============================================================================
62 */
63
64 typedef struct worldSector_s {
65 int axis; // -1 = leaf node
66 float dist;
67 struct worldSector_s *children[2];
68 svEntity_t *entities;
69 } worldSector_t;
70
71 #define AREA_DEPTH 4
72 #define AREA_NODES 64
73
74 worldSector_t sv_worldSectors[AREA_NODES];
75 int sv_numworldSectors;
76
77
78 /*
79 ===============
80 SV_SectorList_f
81 ===============
82 */
SV_SectorList_f(void)83 void SV_SectorList_f( void ) {
84 int i, c;
85 worldSector_t *sec;
86 svEntity_t *ent;
87
88 for ( i = 0 ; i < AREA_NODES ; i++ ) {
89 sec = &sv_worldSectors[i];
90
91 c = 0;
92 for ( ent = sec->entities ; ent ; ent = ent->nextEntityInWorldSector ) {
93 c++;
94 }
95 Com_Printf( "sector %i: %i entities\n", i, c );
96 }
97 }
98
99 /*
100 ===============
101 SV_CreateworldSector
102
103 Builds a uniformly subdivided tree for the given world size
104 ===============
105 */
SV_CreateworldSector(int depth,vec3_t mins,vec3_t maxs)106 static worldSector_t *SV_CreateworldSector( int depth, vec3_t mins, vec3_t maxs ) {
107 worldSector_t *anode;
108 vec3_t size;
109 vec3_t mins1, maxs1, mins2, maxs2;
110
111 anode = &sv_worldSectors[sv_numworldSectors];
112 sv_numworldSectors++;
113
114 if (depth == AREA_DEPTH) {
115 anode->axis = -1;
116 anode->children[0] = anode->children[1] = NULL;
117 return anode;
118 }
119
120 VectorSubtract (maxs, mins, size);
121 if (size[0] > size[1]) {
122 anode->axis = 0;
123 } else {
124 anode->axis = 1;
125 }
126
127 anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
128 VectorCopy (mins, mins1);
129 VectorCopy (mins, mins2);
130 VectorCopy (maxs, maxs1);
131 VectorCopy (maxs, maxs2);
132
133 maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
134
135 anode->children[0] = SV_CreateworldSector (depth+1, mins2, maxs2);
136 anode->children[1] = SV_CreateworldSector (depth+1, mins1, maxs1);
137
138 return anode;
139 }
140
141 /*
142 ===============
143 SV_ClearWorld
144
145 ===============
146 */
SV_ClearWorld(void)147 void SV_ClearWorld( void ) {
148 clipHandle_t h;
149 vec3_t mins, maxs;
150
151 Com_Memset( sv_worldSectors, 0, sizeof(sv_worldSectors) );
152 sv_numworldSectors = 0;
153
154 // get world map bounds
155 h = CM_InlineModel( 0 );
156 CM_ModelBounds( h, mins, maxs );
157 SV_CreateworldSector( 0, mins, maxs );
158 }
159
160
161 /*
162 ===============
163 SV_UnlinkEntity
164
165 ===============
166 */
SV_UnlinkEntity(sharedEntity_t * gEnt)167 void SV_UnlinkEntity( sharedEntity_t *gEnt ) {
168 svEntity_t *ent;
169 svEntity_t *scan;
170 worldSector_t *ws;
171
172 ent = SV_SvEntityForGentity( gEnt );
173
174 gEnt->r.linked = qfalse;
175
176 ws = ent->worldSector;
177 if ( !ws ) {
178 return; // not linked in anywhere
179 }
180 ent->worldSector = NULL;
181
182 if ( ws->entities == ent ) {
183 ws->entities = ent->nextEntityInWorldSector;
184 return;
185 }
186
187 for ( scan = ws->entities ; scan ; scan = scan->nextEntityInWorldSector ) {
188 if ( scan->nextEntityInWorldSector == ent ) {
189 scan->nextEntityInWorldSector = ent->nextEntityInWorldSector;
190 return;
191 }
192 }
193
194 Com_Printf( "WARNING: SV_UnlinkEntity: not found in worldSector\n" );
195 }
196
197
198 /*
199 ===============
200 SV_LinkEntity
201
202 ===============
203 */
204 #define MAX_TOTAL_ENT_LEAFS 128
SV_LinkEntity(sharedEntity_t * gEnt)205 void SV_LinkEntity( sharedEntity_t *gEnt ) {
206 worldSector_t *node;
207 int leafs[MAX_TOTAL_ENT_LEAFS];
208 int cluster;
209 int num_leafs;
210 int i, j, k;
211 int area;
212 int lastLeaf;
213 float *origin, *angles;
214 svEntity_t *ent;
215
216 ent = SV_SvEntityForGentity( gEnt );
217
218 if ( ent->worldSector ) {
219 SV_UnlinkEntity( gEnt ); // unlink from old position
220 }
221
222 // encode the size into the entityState_t for client prediction
223 if ( gEnt->r.bmodel ) {
224 gEnt->s.solid = SOLID_BMODEL; // a solid_box will never create this value
225 } else if ( gEnt->r.contents & ( CONTENTS_SOLID | CONTENTS_BODY ) ) {
226 // assume that x/y are equal and symetric
227 i = gEnt->r.maxs[0];
228 if (i<1)
229 i = 1;
230 if (i>255)
231 i = 255;
232
233 // z is not symetric
234 j = (-gEnt->r.mins[2]);
235 if (j<1)
236 j = 1;
237 if (j>255)
238 j = 255;
239
240 // and z maxs can be negative...
241 k = (gEnt->r.maxs[2]+32);
242 if (k<1)
243 k = 1;
244 if (k>255)
245 k = 255;
246
247 gEnt->s.solid = (k<<16) | (j<<8) | i;
248 } else {
249 gEnt->s.solid = 0;
250 }
251
252 // get the position
253 origin = gEnt->r.currentOrigin;
254 angles = gEnt->r.currentAngles;
255
256 // set the abs box
257 if ( gEnt->r.bmodel && (angles[0] || angles[1] || angles[2]) ) {
258 // expand for rotation
259 float max;
260 int i;
261
262 max = RadiusFromBounds( gEnt->r.mins, gEnt->r.maxs );
263 for (i=0 ; i<3 ; i++) {
264 gEnt->r.absmin[i] = origin[i] - max;
265 gEnt->r.absmax[i] = origin[i] + max;
266 }
267 } else {
268 // normal
269 VectorAdd (origin, gEnt->r.mins, gEnt->r.absmin);
270 VectorAdd (origin, gEnt->r.maxs, gEnt->r.absmax);
271 }
272
273 // because movement is clipped an epsilon away from an actual edge,
274 // we must fully check even when bounding boxes don't quite touch
275 gEnt->r.absmin[0] -= 1;
276 gEnt->r.absmin[1] -= 1;
277 gEnt->r.absmin[2] -= 1;
278 gEnt->r.absmax[0] += 1;
279 gEnt->r.absmax[1] += 1;
280 gEnt->r.absmax[2] += 1;
281
282 // link to PVS leafs
283 ent->numClusters = 0;
284 ent->lastCluster = 0;
285 ent->areanum = -1;
286 ent->areanum2 = -1;
287
288 //get all leafs, including solids
289 num_leafs = CM_BoxLeafnums( gEnt->r.absmin, gEnt->r.absmax,
290 leafs, MAX_TOTAL_ENT_LEAFS, &lastLeaf );
291
292 // if none of the leafs were inside the map, the
293 // entity is outside the world and can be considered unlinked
294 if ( !num_leafs ) {
295 return;
296 }
297
298 // set areas, even from clusters that don't fit in the entity array
299 for (i=0 ; i<num_leafs ; i++) {
300 area = CM_LeafArea (leafs[i]);
301 if (area != -1) {
302 // doors may legally straggle two areas,
303 // but nothing should evern need more than that
304 if (ent->areanum != -1 && ent->areanum != area) {
305 if (ent->areanum2 != -1 && ent->areanum2 != area && sv.state == SS_LOADING) {
306 Com_DPrintf ("Object %i touching 3 areas at %f %f %f\n",
307 gEnt->s.number,
308 gEnt->r.absmin[0], gEnt->r.absmin[1], gEnt->r.absmin[2]);
309 }
310 ent->areanum2 = area;
311 } else {
312 ent->areanum = area;
313 }
314 }
315 }
316
317 // store as many explicit clusters as we can
318 ent->numClusters = 0;
319 for (i=0 ; i < num_leafs ; i++) {
320 cluster = CM_LeafCluster( leafs[i] );
321 if ( cluster != -1 ) {
322 ent->clusternums[ent->numClusters++] = cluster;
323 if ( ent->numClusters == MAX_ENT_CLUSTERS ) {
324 break;
325 }
326 }
327 }
328
329 // store off a last cluster if we need to
330 if ( i != num_leafs ) {
331 ent->lastCluster = CM_LeafCluster( lastLeaf );
332 }
333
334 gEnt->r.linkcount++;
335
336 // find the first world sector node that the ent's box crosses
337 node = sv_worldSectors;
338 while (1)
339 {
340 if (node->axis == -1)
341 break;
342 if ( gEnt->r.absmin[node->axis] > node->dist)
343 node = node->children[0];
344 else if ( gEnt->r.absmax[node->axis] < node->dist)
345 node = node->children[1];
346 else
347 break; // crosses the node
348 }
349
350 // link it in
351 ent->worldSector = node;
352 ent->nextEntityInWorldSector = node->entities;
353 node->entities = ent;
354
355 gEnt->r.linked = qtrue;
356 }
357
358 /*
359 ============================================================================
360
361 AREA QUERY
362
363 Fills in a list of all entities who's absmin / absmax intersects the given
364 bounds. This does NOT mean that they actually touch in the case of bmodels.
365 ============================================================================
366 */
367
368 typedef struct {
369 const float *mins;
370 const float *maxs;
371 int *list;
372 int count, maxcount;
373 } areaParms_t;
374
375
376 /*
377 ====================
378 SV_AreaEntities_r
379
380 ====================
381 */
SV_AreaEntities_r(worldSector_t * node,areaParms_t * ap)382 static void SV_AreaEntities_r( worldSector_t *node, areaParms_t *ap ) {
383 svEntity_t *check, *next;
384 sharedEntity_t *gcheck;
385 int count;
386
387 count = 0;
388
389 for ( check = node->entities ; check ; check = next ) {
390 next = check->nextEntityInWorldSector;
391
392 gcheck = SV_GEntityForSvEntity( check );
393
394 if ( gcheck->r.absmin[0] > ap->maxs[0]
395 || gcheck->r.absmin[1] > ap->maxs[1]
396 || gcheck->r.absmin[2] > ap->maxs[2]
397 || gcheck->r.absmax[0] < ap->mins[0]
398 || gcheck->r.absmax[1] < ap->mins[1]
399 || gcheck->r.absmax[2] < ap->mins[2]) {
400 continue;
401 }
402
403 if ( ap->count == ap->maxcount ) {
404 Com_Printf ("SV_AreaEntities: MAXCOUNT\n");
405 return;
406 }
407
408 ap->list[ap->count] = check - sv.svEntities;
409 ap->count++;
410 }
411
412 if (node->axis == -1) {
413 return; // terminal node
414 }
415
416 // recurse down both sides
417 if ( ap->maxs[node->axis] > node->dist ) {
418 SV_AreaEntities_r ( node->children[0], ap );
419 }
420 if ( ap->mins[node->axis] < node->dist ) {
421 SV_AreaEntities_r ( node->children[1], ap );
422 }
423 }
424
425 /*
426 ================
427 SV_AreaEntities
428 ================
429 */
SV_AreaEntities(const vec3_t mins,const vec3_t maxs,int * entityList,int maxcount)430 int SV_AreaEntities( const vec3_t mins, const vec3_t maxs, int *entityList, int maxcount ) {
431 areaParms_t ap;
432
433 ap.mins = mins;
434 ap.maxs = maxs;
435 ap.list = entityList;
436 ap.count = 0;
437 ap.maxcount = maxcount;
438
439 SV_AreaEntities_r( sv_worldSectors, &ap );
440
441 return ap.count;
442 }
443
444
445
446 //===========================================================================
447
448
449 typedef struct {
450 vec3_t boxmins, boxmaxs;// enclose the test object along entire move
451 const float *mins;
452 const float *maxs; // size of the moving object
453 const float *start;
454 vec3_t end;
455 trace_t trace;
456 int passEntityNum;
457 int contentmask;
458 int capsule;
459 } moveclip_t;
460
461
462 /*
463 ====================
464 SV_ClipToEntity
465
466 ====================
467 */
SV_ClipToEntity(trace_t * trace,const vec3_t start,const vec3_t mins,const vec3_t maxs,const vec3_t end,int entityNum,int contentmask,int capsule)468 void SV_ClipToEntity( trace_t *trace, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int entityNum, int contentmask, int capsule ) {
469 sharedEntity_t *touch;
470 clipHandle_t clipHandle;
471 float *origin, *angles;
472
473 touch = SV_GentityNum( entityNum );
474
475 Com_Memset(trace, 0, sizeof(trace_t));
476
477 // if it doesn't have any brushes of a type we
478 // are looking for, ignore it
479 if ( ! ( contentmask & touch->r.contents ) ) {
480 trace->fraction = 1.0;
481 return;
482 }
483
484 // might intersect, so do an exact clip
485 clipHandle = SV_ClipHandleForEntity (touch);
486
487 origin = touch->r.currentOrigin;
488 angles = touch->r.currentAngles;
489
490 if ( !touch->r.bmodel ) {
491 angles = vec3_origin; // boxes don't rotate
492 }
493
494 CM_TransformedBoxTrace ( trace, (float *)start, (float *)end,
495 (float *)mins, (float *)maxs, clipHandle, contentmask,
496 origin, angles, capsule);
497
498 if ( trace->fraction < 1 ) {
499 trace->entityNum = touch->s.number;
500 }
501 }
502
503
504 /*
505 ====================
506 SV_ClipMoveToEntities
507
508 ====================
509 */
SV_ClipMoveToEntities(moveclip_t * clip)510 static void SV_ClipMoveToEntities( moveclip_t *clip ) {
511 int i, num;
512 int touchlist[MAX_GENTITIES];
513 sharedEntity_t *touch;
514 int passOwnerNum;
515 trace_t trace;
516 clipHandle_t clipHandle;
517 float *origin, *angles;
518
519 num = SV_AreaEntities( clip->boxmins, clip->boxmaxs, touchlist, MAX_GENTITIES);
520
521 if ( clip->passEntityNum != ENTITYNUM_NONE ) {
522 passOwnerNum = ( SV_GentityNum( clip->passEntityNum ) )->r.ownerNum;
523 if ( passOwnerNum == ENTITYNUM_NONE ) {
524 passOwnerNum = -1;
525 }
526 } else {
527 passOwnerNum = -1;
528 }
529
530 for ( i=0 ; i<num ; i++ ) {
531 if ( clip->trace.allsolid ) {
532 return;
533 }
534 touch = SV_GentityNum( touchlist[i] );
535
536 // see if we should ignore this entity
537 if ( clip->passEntityNum != ENTITYNUM_NONE ) {
538 if ( touchlist[i] == clip->passEntityNum ) {
539 continue; // don't clip against the pass entity
540 }
541 if ( touch->r.ownerNum == clip->passEntityNum ) {
542 continue; // don't clip against own missiles
543 }
544 if ( touch->r.ownerNum == passOwnerNum ) {
545 continue; // don't clip against other missiles from our owner
546 }
547 }
548
549 // if it doesn't have any brushes of a type we
550 // are looking for, ignore it
551 if ( ! ( clip->contentmask & touch->r.contents ) ) {
552 continue;
553 }
554
555 // might intersect, so do an exact clip
556 clipHandle = SV_ClipHandleForEntity (touch);
557
558 origin = touch->r.currentOrigin;
559 angles = touch->r.currentAngles;
560
561
562 if ( !touch->r.bmodel ) {
563 angles = vec3_origin; // boxes don't rotate
564 }
565
566 CM_TransformedBoxTrace ( &trace, (float *)clip->start, (float *)clip->end,
567 (float *)clip->mins, (float *)clip->maxs, clipHandle, clip->contentmask,
568 origin, angles, clip->capsule);
569
570 if ( trace.allsolid ) {
571 clip->trace.allsolid = qtrue;
572 trace.entityNum = touch->s.number;
573 } else if ( trace.startsolid ) {
574 clip->trace.startsolid = qtrue;
575 trace.entityNum = touch->s.number;
576 }
577
578 if ( trace.fraction < clip->trace.fraction ) {
579 qboolean oldStart;
580
581 // make sure we keep a startsolid from a previous trace
582 oldStart = clip->trace.startsolid;
583
584 trace.entityNum = touch->s.number;
585 clip->trace = trace;
586 clip->trace.startsolid |= oldStart;
587 }
588 }
589 }
590
591
592 /*
593 ==================
594 SV_Trace
595
596 Moves the given mins/maxs volume through the world from start to end.
597 passEntityNum and entities owned by passEntityNum are explicitly not checked.
598 ==================
599 */
SV_Trace(trace_t * results,const vec3_t start,vec3_t mins,vec3_t maxs,const vec3_t end,int passEntityNum,int contentmask,int capsule)600 void SV_Trace( trace_t *results, const vec3_t start, vec3_t mins, vec3_t maxs, const vec3_t end, int passEntityNum, int contentmask, int capsule ) {
601 moveclip_t clip;
602 int i;
603
604 if ( !mins ) {
605 mins = vec3_origin;
606 }
607 if ( !maxs ) {
608 maxs = vec3_origin;
609 }
610
611 Com_Memset ( &clip, 0, sizeof ( moveclip_t ) );
612
613 // clip to world
614 CM_BoxTrace( &clip.trace, start, end, mins, maxs, 0, contentmask, capsule );
615 clip.trace.entityNum = clip.trace.fraction != 1.0 ? ENTITYNUM_WORLD : ENTITYNUM_NONE;
616 if ( clip.trace.fraction == 0 ) {
617 *results = clip.trace;
618 return; // blocked immediately by the world
619 }
620
621 clip.contentmask = contentmask;
622 clip.start = start;
623 // VectorCopy( clip.trace.endpos, clip.end );
624 VectorCopy( end, clip.end );
625 clip.mins = mins;
626 clip.maxs = maxs;
627 clip.passEntityNum = passEntityNum;
628 clip.capsule = capsule;
629
630 // create the bounding box of the entire move
631 // we can limit it to the part of the move not
632 // already clipped off by the world, which can be
633 // a significant savings for line of sight and shot traces
634 for ( i=0 ; i<3 ; i++ ) {
635 if ( end[i] > start[i] ) {
636 clip.boxmins[i] = clip.start[i] + clip.mins[i] - 1;
637 clip.boxmaxs[i] = clip.end[i] + clip.maxs[i] + 1;
638 } else {
639 clip.boxmins[i] = clip.end[i] + clip.mins[i] - 1;
640 clip.boxmaxs[i] = clip.start[i] + clip.maxs[i] + 1;
641 }
642 }
643
644 // clip to other solid entities
645 SV_ClipMoveToEntities ( &clip );
646
647 *results = clip.trace;
648 }
649
650
651
652 /*
653 =============
654 SV_PointContents
655 =============
656 */
SV_PointContents(const vec3_t p,int passEntityNum)657 int SV_PointContents( const vec3_t p, int passEntityNum ) {
658 int touch[MAX_GENTITIES];
659 sharedEntity_t *hit;
660 int i, num;
661 int contents, c2;
662 clipHandle_t clipHandle;
663 float *angles;
664
665 // get base contents from world
666 contents = CM_PointContents( p, 0 );
667
668 // or in contents from all the other entities
669 num = SV_AreaEntities( p, p, touch, MAX_GENTITIES );
670
671 for ( i=0 ; i<num ; i++ ) {
672 if ( touch[i] == passEntityNum ) {
673 continue;
674 }
675 hit = SV_GentityNum( touch[i] );
676 // might intersect, so do an exact clip
677 clipHandle = SV_ClipHandleForEntity( hit );
678 angles = hit->s.angles;
679 if ( !hit->r.bmodel ) {
680 angles = vec3_origin; // boxes don't rotate
681 }
682
683 c2 = CM_TransformedPointContents (p, clipHandle, hit->s.origin, hit->s.angles);
684
685 contents |= c2;
686 }
687
688 return contents;
689 }
690
691
692