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 // sv_world.c
22 // World query functions
23 //
24
25 #include "sv_local.h"
26
27 // FIXME: this use of "area" is different from the bsp file use
28
29 // (type *)STRUCT_FROM_LINK(link_t *link, type, member)
30 // ent = STRUCT_FROM_LINK(link,entity_t,order)
31 // FIXME: remove this mess!
32 #define STRUCT_FROM_LINK(l,t,m) ((t *)((byte *)l - (int)&(((t *)0)->m)))
33
34 #define EDICT_FROM_AREA(l) STRUCT_FROM_LINK(l,edict_t,area)
35
36 typedef struct areaNode_s {
37 int axis; // -1 = leaf node
38 float dist;
39 struct areaNode_s *children[2];
40 link_t trigger_edicts;
41 link_t solid_edicts;
42 } areaNode_t;
43
44 #define AREA_DEPTH 4
45 #define AREA_NODES 32
46
47 static areaNode_t sv_areaNodes[AREA_NODES];
48 static int sv_numAreaNodes;
49
50 static float *sv_areaMins, *sv_areaMaxs;
51 static edict_t **sv_areaList;
52 static int sv_areaCount, sv_areaMaxCount;
53 static int sv_areaType;
54
55 // ClearLink is used for new headNodes
ClearLink(link_t * l)56 static void ClearLink (link_t *l)
57 {
58 l->prev = l->next = l;
59 }
RemoveLink(link_t * l)60 static void RemoveLink (link_t *l)
61 {
62 l->next->prev = l->prev;
63 l->prev->next = l->next;
64 }
InsertLinkBefore(link_t * l,link_t * before)65 static void InsertLinkBefore (link_t *l, link_t *before)
66 {
67 l->next = before;
68 l->prev = before->prev;
69 l->prev->next = l;
70 l->next->prev = l;
71 }
72
73 // ============================================================================
74
75 typedef struct moveClip_s {
76 vec3_t boxMins, boxMaxs; // enclose the test object along entire move
77 float *mins, *maxs; // size of the moving object
78 vec3_t mins2, maxs2; // size when clipping against mosnters
79 float *start, *end;
80 trace_t trace;
81 edict_t *passEdict;
82 int contentMask;
83 } moveClip_t;
84
85 /*
86 ===============================================================================
87
88 ENTITY AREA CHECKING
89
90 ===============================================================================
91 */
92
93 /*
94 ===============
95 SV_CreateAreaNode
96
97 Builds a uniformly subdivided tree for the given world size
98 ===============
99 */
SV_CreateAreaNode(int depth,vec3_t mins,vec3_t maxs)100 static areaNode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
101 {
102 areaNode_t *anode;
103 vec3_t size;
104 vec3_t mins1, maxs1, mins2, maxs2;
105
106 anode = &sv_areaNodes[sv_numAreaNodes];
107 sv_numAreaNodes++;
108
109 ClearLink (&anode->trigger_edicts);
110 ClearLink (&anode->solid_edicts);
111
112 if (depth == AREA_DEPTH) {
113 anode->axis = -1;
114 anode->children[0] = anode->children[1] = NULL;
115 return anode;
116 }
117
118 Vec3Subtract (maxs, mins, size);
119 if (size[0] > size[1])
120 anode->axis = 0;
121 else
122 anode->axis = 1;
123
124 anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
125 Vec3Copy (mins, mins1);
126 Vec3Copy (mins, mins2);
127 Vec3Copy (maxs, maxs1);
128 Vec3Copy (maxs, maxs2);
129
130 maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
131
132 anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
133 anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
134
135 return anode;
136 }
137
138
139 /*
140 ===============
141 SV_ClearWorld
142 ===============
143 */
SV_ClearWorld(void)144 void SV_ClearWorld (void)
145 {
146 vec3_t mins, maxs;
147
148 memset (sv_areaNodes, 0, sizeof (sv_areaNodes));
149 sv_numAreaNodes = 0;
150
151 CM_InlineModelBounds (sv.models[1], mins, maxs);
152 SV_CreateAreaNode (0, mins, maxs);
153 }
154
155
156 /*
157 ===============
158 SV_UnlinkEdict
159 ===============
160 */
SV_UnlinkEdict(edict_t * ent)161 void SV_UnlinkEdict (edict_t *ent)
162 {
163 if (!ent->area.prev)
164 return; // not linked in anywhere
165
166 RemoveLink (&ent->area);
167 ent->area.prev = ent->area.next = NULL;
168 }
169
170
171 /*
172 ===============
173 SV_LinkEdict
174 ===============
175 */
176 #define MAX_TOTAL_ENT_LEAFS 128
SV_LinkEdict(edict_t * ent)177 void SV_LinkEdict (edict_t *ent)
178 {
179 areaNode_t *node;
180 int leafs[MAX_TOTAL_ENT_LEAFS];
181 int clusters[MAX_TOTAL_ENT_LEAFS];
182 int num_leafs;
183 int i, j, k;
184 int area;
185 int topnode;
186
187 if (ent->area.prev)
188 SV_UnlinkEdict (ent); // unlink from old position
189
190 if (ent == ge->edicts)
191 return; // don't add the world
192
193 if (!ent->inUse)
194 return;
195
196 // Set the size
197 Vec3Subtract (ent->maxs, ent->mins, ent->size);
198
199 // Encode the size into the entity_state for client prediction
200 if (ent->solid == SOLID_BBOX && !(ent->svFlags & SVF_DEADMONSTER)) {
201 // Assume that x/y are equal and symetric
202 i = ent->maxs[0]/8;
203 if (i<1)
204 i = 1;
205 if (i>31)
206 i = 31;
207
208 // z is not symetric
209 j = (-ent->mins[2])/8;
210 if (j<1)
211 j = 1;
212 if (j>31)
213 j = 31;
214
215 // and z maxs can be negative...
216 k = (ent->maxs[2]+32)/8;
217 if (k<1)
218 k = 1;
219 if (k>63)
220 k = 63;
221
222 ent->s.solid = (k<<10) | (j<<5) | i;
223 }
224 else if (ent->solid == SOLID_BSP) {
225 ent->s.solid = 31; // A solid_bbox will never create this value
226 }
227 else
228 ent->s.solid = 0;
229
230 // Set the abs box
231 if (ent->solid == SOLID_BSP && (ent->s.angles[0] || ent->s.angles[1] || ent->s.angles[2])) {
232 // Expand for rotation
233 float rMax, v;
234 int i;
235
236 rMax = 0;
237 for (i=0 ; i<3 ; i++) {
238 v = fabs (ent->mins[i]);
239 if (v > rMax)
240 rMax = v;
241 v = fabs (ent->maxs[i]);
242 if (v > rMax)
243 rMax = v;
244 }
245
246 ent->absMin[0] = ent->s.origin[0] - rMax;
247 ent->absMin[1] = ent->s.origin[1] - rMax;
248 ent->absMin[2] = ent->s.origin[2] - rMax;
249
250 ent->absMax[0] = ent->s.origin[0] + rMax;
251 ent->absMax[1] = ent->s.origin[1] + rMax;
252 ent->absMax[2] = ent->s.origin[2] + rMax;
253 }
254 else {
255 // Normal
256 Vec3Add (ent->s.origin, ent->mins, ent->absMin);
257 Vec3Add (ent->s.origin, ent->maxs, ent->absMax);
258 }
259
260 /*
261 ** Because movement is clipped an epsilon away from an actual edge,
262 ** we must fully check even when bounding boxes don't quite touch
263 */
264 ent->absMin[0] -= 1;
265 ent->absMin[1] -= 1;
266 ent->absMin[2] -= 1;
267 ent->absMax[0] += 1;
268 ent->absMax[1] += 1;
269 ent->absMax[2] += 1;
270
271 // Link to PVS leafs
272 ent->numClusters = 0;
273 ent->areaNum = 0;
274 ent->areaNum2 = 0;
275
276 // Get all leafs, including solids
277 num_leafs = CM_BoxLeafnums (ent->absMin, ent->absMax, leafs, MAX_TOTAL_ENT_LEAFS, &topnode);
278
279 // Set areas
280 for (i=0 ; i<num_leafs ; i++) {
281 clusters[i] = CM_LeafCluster (leafs[i]);
282 area = CM_LeafArea (leafs[i]);
283 if (area) {
284 /*
285 ** Doors may legally straggle two areas,
286 ** but nothing should evern need more than that
287 */
288 if (ent->areaNum && ent->areaNum != area) {
289 if (ent->areaNum2 && ent->areaNum2 != area && Com_ServerState () == SS_LOADING)
290 Com_DevPrintf (0, "Object touching 3 areas at %f %f %f\n",
291 ent->absMin[0], ent->absMin[1], ent->absMin[2]);
292 ent->areaNum2 = area;
293 }
294 else
295 ent->areaNum = area;
296 }
297 }
298
299 if (num_leafs >= MAX_TOTAL_ENT_LEAFS) {
300 // Assume we missed some leafs, and mark by headNode
301 ent->numClusters = -1;
302 ent->headNode = topnode;
303 }
304 else {
305 ent->numClusters = 0;
306 for (i=0 ; i<num_leafs ; i++) {
307 if (clusters[i] == -1)
308 continue; // Not a visible leaf
309 for (j=0 ; j<i ; j++)
310 if (clusters[j] == clusters[i])
311 break;
312 if (j == i) {
313 if (ent->numClusters == MAX_ENT_CLUSTERS) {
314 // Assume we missed some leafs, and mark by headNode
315 ent->numClusters = -1;
316 ent->headNode = topnode;
317 break;
318 }
319
320 ent->clusterNums[ent->numClusters++] = clusters[i];
321 }
322 }
323 }
324
325 // If first time, make sure oldOrigin is valid
326 if (!ent->linkCount)
327 Vec3Copy (ent->s.origin, ent->s.oldOrigin);
328
329 ent->linkCount++;
330
331 if (ent->solid == SOLID_NOT)
332 return;
333
334 // Find the first node that the ent's box crosses
335 node = sv_areaNodes;
336 for ( ; ; ) {
337 if (node->axis == -1)
338 break;
339 if (ent->absMin[node->axis] > node->dist)
340 node = node->children[0];
341 else if (ent->absMax[node->axis] < node->dist)
342 node = node->children[1];
343 else
344 break; // Crosses the node
345 }
346
347 // Link it in
348 if (ent->solid == SOLID_TRIGGER)
349 InsertLinkBefore (&ent->area, &node->trigger_edicts);
350 else
351 InsertLinkBefore (&ent->area, &node->solid_edicts);
352 }
353
354
355 /*
356 ================
357 SV_AreaEdicts
358 ================
359 */
SV_AreaEdicts_r(areaNode_t * node)360 static void SV_AreaEdicts_r (areaNode_t *node)
361 {
362 link_t *l, *next, *start;
363 edict_t *check;
364
365 // Touch linked edicts
366 if (sv_areaType == AREA_SOLID)
367 start = &node->solid_edicts;
368 else
369 start = &node->trigger_edicts;
370
371 for (l=start->next ; l!=start ; l=next) {
372 next = l->next;
373 check = EDICT_FROM_AREA(l);
374
375 if (check->solid == SOLID_NOT)
376 continue; // Deactivated
377 if (check->absMin[0] > sv_areaMaxs[0]
378 || check->absMin[1] > sv_areaMaxs[1]
379 || check->absMin[2] > sv_areaMaxs[2]
380 || check->absMax[0] < sv_areaMins[0]
381 || check->absMax[1] < sv_areaMins[1]
382 || check->absMax[2] < sv_areaMins[2])
383 continue; // Not touching
384
385 if (sv_areaCount == sv_areaMaxCount) {
386 Com_Printf (0, "SV_AreaEdicts: MAXCOUNT\n");
387 return;
388 }
389
390 sv_areaList[sv_areaCount] = check;
391 sv_areaCount++;
392 }
393
394 if (node->axis == -1)
395 return; // Terminal node
396
397 // Recurse down both sides
398 if (sv_areaMaxs[node->axis] > node->dist)
399 SV_AreaEdicts_r (node->children[0]);
400 if (sv_areaMins[node->axis] < node->dist)
401 SV_AreaEdicts_r (node->children[1]);
402 }
403
SV_AreaEdicts(vec3_t mins,vec3_t maxs,edict_t ** list,int maxCount,int areaType)404 int SV_AreaEdicts (vec3_t mins, vec3_t maxs, edict_t **list, int maxCount, int areaType)
405 {
406 sv_areaMins = mins;
407 sv_areaMaxs = maxs;
408 sv_areaList = list;
409 sv_areaCount = 0;
410 sv_areaMaxCount = maxCount;
411 sv_areaType = areaType;
412
413 SV_AreaEdicts_r (sv_areaNodes);
414
415 return sv_areaCount;
416 }
417
418 /*
419 ===============================================================================
420
421 POINT CONTENTS
422
423 ===============================================================================
424 */
425
426 /*
427 ================
428 SV_HullForEntity
429
430 Returns a headNode that can be used for testing or clipping an
431 object of mins/maxs size.
432 Offset is filled in to contain the adjustment that must be added to the
433 testing object's origin to get a point to use with the returned hull.
434 ================
435 */
SV_HullForEntity(edict_t * ent)436 static int SV_HullForEntity (edict_t *ent)
437 {
438 struct cBspModel_s *model;
439
440 // decide which clipping hull to use, based on the size
441 if (ent->solid == SOLID_BSP) {
442 // explicit hulls in the BSP model
443 model = sv.models[ent->s.modelIndex];
444 if (!model)
445 Com_Error (ERR_FATAL, "MOVETYPE_PUSH with a non bsp model");
446
447 return CM_InlineModelHeadNode (model);
448 }
449
450 // create a temp hull from bounding box sizes
451 return CM_HeadnodeForBox (ent->mins, ent->maxs);
452 }
453
454
455 /*
456 =============
457 SV_PointContents
458 =============
459 */
SV_PointContents(vec3_t p)460 int SV_PointContents (vec3_t p)
461 {
462 edict_t *touch[MAX_CS_EDICTS], *hit;
463 int i, num;
464 int contents;
465 int headNode;
466 float *angles;
467
468 // Het base contents from world
469 contents = CM_PointContents (p, CM_InlineModelHeadNode (sv.models[1]));
470
471 // Or in contents from all the other entities
472 num = SV_AreaEdicts (p, p, touch, MAX_CS_EDICTS, AREA_SOLID);
473
474 for (i=0 ; i<num ; i++) {
475 hit = touch[i];
476
477 // Might intersect, so do an exact clip
478 headNode = SV_HullForEntity (hit);
479 if (hit->solid != SOLID_BSP)
480 angles = vec3Origin; // Boxes don't rotate
481 else
482 angles = hit->s.angles;
483
484 contents |= CM_TransformedPointContents (p, headNode, hit->s.origin, hit->s.angles);
485 }
486
487 return contents;
488 }
489
490 /*
491 ===============================================================================
492
493 TRACING
494
495 ===============================================================================
496 */
497
498 /*
499 ====================
500 SV_ClipMoveToEntities
501 ====================
502 */
SV_ClipMoveToEntities(moveClip_t * clip)503 static void SV_ClipMoveToEntities (moveClip_t *clip)
504 {
505 int i, num;
506 edict_t *touchlist[MAX_CS_EDICTS], *touch;
507 trace_t trace;
508 int headNode;
509 float *angles;
510
511 num = SV_AreaEdicts (clip->boxMins, clip->boxMaxs, touchlist, MAX_CS_EDICTS, AREA_SOLID);
512
513 /*
514 ** be careful, it is possible to have an entity in this
515 ** list removed before we get to it (killtriggered)
516 */
517 for (i=0 ; i<num ; i++) {
518 touch = touchlist[i];
519 if (touch->solid == SOLID_NOT)
520 continue;
521 if (touch == clip->passEdict)
522 continue;
523 if (clip->trace.allSolid)
524 return;
525 if (clip->passEdict) {
526 if (touch->owner == clip->passEdict)
527 continue; // Don't clip against own missiles
528 if (clip->passEdict->owner == touch)
529 continue; // Don't clip against owner
530 }
531
532 if (!(clip->contentMask & CONTENTS_DEADMONSTER) && (touch->svFlags & SVF_DEADMONSTER))
533 continue;
534
535 // Might intersect, so do an exact clip
536 headNode = SV_HullForEntity (touch);
537 if (touch->solid != SOLID_BSP)
538 angles = vec3Origin; // Boxes don't rotate
539 else
540 angles = touch->s.angles;
541
542 if (touch->svFlags & SVF_MONSTER)
543 CM_TransformedBoxTrace (&trace, clip->start, clip->end,
544 clip->mins2, clip->maxs2, headNode, clip->contentMask,
545 touch->s.origin, angles);
546 else
547 CM_TransformedBoxTrace (&trace, clip->start, clip->end,
548 clip->mins, clip->maxs, headNode, clip->contentMask,
549 touch->s.origin, angles);
550
551 if (trace.allSolid || trace.startSolid || (trace.fraction < clip->trace.fraction)) {
552 trace.ent = touch;
553 if (clip->trace.startSolid) {
554 clip->trace = trace;
555 clip->trace.startSolid = qTrue;
556 }
557 else
558 clip->trace = trace;
559 }
560 else if (trace.startSolid)
561 clip->trace.startSolid = qTrue;
562 }
563 }
564
565
566 /*
567 ==================
568 SV_TraceBounds
569 ==================
570 */
SV_TraceBounds(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,vec3_t boxMins,vec3_t boxMaxs)571 static void SV_TraceBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxMins, vec3_t boxMaxs)
572 {
573 int i;
574
575 for (i=0 ; i<3 ; i++) {
576 if (end[i] > start[i]) {
577 boxMins[i] = start[i] + mins[i] - 1;
578 boxMaxs[i] = end[i] + maxs[i] + 1;
579 }
580 else {
581 boxMins[i] = end[i] + mins[i] - 1;
582 boxMaxs[i] = start[i] + maxs[i] + 1;
583 }
584 }
585 }
586
587
588 /*
589 ==================
590 SV_Trace
591
592 Moves the given mins/maxs volume through the world from start to end.
593
594 passEdict and edicts owned by passEdict are explicitly not checked.
595 ==================
596 */
SV_Trace(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,edict_t * passEdict,int contentMask)597 trace_t SV_Trace (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, edict_t *passEdict, int contentMask)
598 {
599 moveClip_t clip;
600
601 if (!mins)
602 mins = vec3Origin;
603 if (!maxs)
604 maxs = vec3Origin;
605
606 memset (&clip, 0, sizeof (moveClip_t));
607
608 // Clip to world
609 clip.trace = CM_BoxTrace (start, end, mins, maxs, 0, contentMask);
610 clip.trace.ent = ge->edicts;
611 if (clip.trace.fraction == 0)
612 return clip.trace; // Blocked by the world
613
614 clip.contentMask = contentMask;
615 clip.start = start;
616 clip.end = end;
617 clip.mins = mins;
618 clip.maxs = maxs;
619 clip.passEdict = passEdict;
620
621 Vec3Copy (mins, clip.mins2);
622 Vec3Copy (maxs, clip.maxs2);
623
624 // Create the bounding box of the entire move
625 SV_TraceBounds (start, clip.mins2, clip.maxs2, end, clip.boxMins, clip.boxMaxs);
626
627 // Clip to other solid entities
628 SV_ClipMoveToEntities (&clip);
629
630 return clip.trace;
631 }
632