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