1 /*
2 * Copyright(c) 1997-2001 Id Software, Inc.
3 * Copyright(c) 2002 The Quakeforge Project.
4 * Copyright(c) 2006 Quetoo.
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or(at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
14 *
15 * See the GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 */
21
22 /*
23 * world query functions
24 */
25
26 #include "server.h"
27
28 /*
29
30 ENTITY AREA CHECKING
31
32 FIXME: this use of "area" is different from the bsp file use
33 */
34
35 //(type *)STRUCT_FROM_LINK(link_t *link, type, member)
36 // ent = STRUCT_FROM_LINK(link,entity_t,order)
37 // FIXME: remove this mess!
38 #include <inttypes.h>
39 #define STRUCT_FROM_LINK(l,t,m)((t *)((byte *)l -(intptr_t)&(((t *)0)->m)))
40
41 #define EDICT_FROM_AREA(l) STRUCT_FROM_LINK(l,edict_t,area)
42
43 typedef struct areanode_s {
44 int axis; // -1 = leaf node
45 float dist;
46 struct areanode_s *children[2];
47 link_t trigger_edicts;
48 link_t solid_edicts;
49 } areanode_t;
50
51 #define AREA_DEPTH 4
52 #define AREA_NODES 32
53
54 areanode_t sv_areanodes[AREA_NODES];
55 int sv_numareanodes;
56
57 float *area_mins, *area_maxs;
58 edict_t **area_list;
59 int area_count, area_maxcount;
60 int area_type;
61
62 int SV_HullForEntity(edict_t *ent);
63
64
65 // ClearLink is used for new headnodes
ClearLink(link_t * l)66 void ClearLink(link_t *l){
67 l->prev = l->next = l;
68 }
69
RemoveLink(link_t * l)70 void RemoveLink(link_t *l){
71 l->next->prev = l->prev;
72 l->prev->next = l->next;
73 }
74
InsertLinkBefore(link_t * l,link_t * before)75 void InsertLinkBefore(link_t *l, link_t *before){
76 l->next = before;
77 l->prev = before->prev;
78 l->prev->next = l;
79 l->next->prev = l;
80 }
81
82 /*
83 SV_CreateAreaNode
84
85 Builds a uniformly subdivided tree for the given world size
86 */
SV_CreateAreaNode(int depth,vec3_t mins,vec3_t maxs)87 areanode_t *SV_CreateAreaNode(int depth, vec3_t mins, vec3_t maxs){
88 areanode_t *anode;
89 vec3_t size;
90 vec3_t mins1, maxs1, mins2, maxs2;
91
92 anode = &sv_areanodes[sv_numareanodes];
93 sv_numareanodes++;
94
95 ClearLink(&anode->trigger_edicts);
96 ClearLink(&anode->solid_edicts);
97
98 if(depth == AREA_DEPTH){
99 anode->axis = -1;
100 anode->children[0] = anode->children[1] = NULL;
101 return anode;
102 }
103
104 VectorSubtract(maxs, mins, size);
105 if(size[0] > size[1])
106 anode->axis = 0;
107 else
108 anode->axis = 1;
109
110 anode->dist = 0.5 *(maxs[anode->axis] + mins[anode->axis]);
111 VectorCopy(mins, mins1);
112 VectorCopy(mins, mins2);
113 VectorCopy(maxs, maxs1);
114 VectorCopy(maxs, maxs2);
115
116 maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
117
118 anode->children[0] = SV_CreateAreaNode(depth + 1, mins2, maxs2);
119 anode->children[1] = SV_CreateAreaNode(depth + 1, mins1, maxs1);
120
121 return anode;
122 }
123
124 /*
125 SV_ClearWorld
126
127 */
SV_ClearWorld(void)128 void SV_ClearWorld(void){
129 memset(sv_areanodes, 0, sizeof(sv_areanodes));
130 sv_numareanodes = 0;
131 SV_CreateAreaNode(0, sv.models[1]->mins, sv.models[1]->maxs);
132 }
133
134
135 /*
136 SV_UnlinkEdict
137
138 */
SV_UnlinkEdict(edict_t * ent)139 void SV_UnlinkEdict(edict_t *ent){
140 if(!ent->area.prev)
141 return; // not linked in anywhere
142 RemoveLink(&ent->area);
143 ent->area.prev = ent->area.next = NULL;
144 }
145
146
147 /*
148 SV_LinkEdict
149
150 */
151 #define MAX_TOTAL_ENT_LEAFS 128
SV_LinkEdict(edict_t * ent)152 void SV_LinkEdict(edict_t *ent){
153 areanode_t *node;
154 int leafs[MAX_TOTAL_ENT_LEAFS];
155 int clusters[MAX_TOTAL_ENT_LEAFS];
156 int num_leafs;
157 int i, j, k;
158 int area;
159 int topnode;
160
161 if(ent->area.prev)
162 SV_UnlinkEdict(ent); // unlink from old position
163
164 if(ent == ge->edicts)
165 return; // don't add the world
166
167 if(!ent->inuse)
168 return;
169
170 // set the size
171 VectorSubtract(ent->maxs, ent->mins, ent->size);
172
173 // encode the size into the entity_state for client prediction
174 if(ent->solid == SOLID_BBOX && !(ent->svflags & SVF_DEADMONSTER)){ // assume that x/y are equal and symetric
175 i = ent->maxs[0] / 8;
176 if(i < 1)
177 i = 1;
178 if(i > 31)
179 i = 31;
180
181 // z is not symetric
182 j =(-ent->mins[2]) / 8;
183 if(j < 1)
184 j = 1;
185 if(j > 31)
186 j = 31;
187
188 // and z maxs can be negative...
189 k =(ent->maxs[2] + 32) / 8;
190 if(k < 1)
191 k = 1;
192 if(k > 63)
193 k = 63;
194
195 ent->s.solid =(k << 10) |(j << 5) | i;
196 } else if(ent->solid == SOLID_BSP){
197 ent->s.solid = 31; // a solid_bbox will never create this value
198 } else
199 ent->s.solid = 0;
200
201 // set the abs box
202 if(ent->solid == SOLID_BSP &&
203 (ent->s.angles[0] || ent->s.angles[1] || ent->s.angles[2])){ // expand for rotation
204 float max, v;
205 int i;
206
207 max = 0;
208 for(i = 0; i < 3; i++){
209 v = fabs(ent->mins[i]);
210 if(v > max)
211 max = v;
212 v = fabs(ent->maxs[i]);
213 if(v > max)
214 max = v;
215 }
216 for(i = 0; i < 3; i++){
217 ent->absmin[i] = ent->s.origin[i] - max;
218 ent->absmax[i] = ent->s.origin[i] + max;
219 }
220 } else { // normal
221 VectorAdd(ent->s.origin, ent->mins, ent->absmin);
222 VectorAdd(ent->s.origin, ent->maxs, ent->absmax);
223 }
224
225 // because movement is clipped an epsilon away from an actual edge,
226 // we must fully check even when bounding boxes don't quite touch
227 ent->absmin[0] -= 1;
228 ent->absmin[1] -= 1;
229 ent->absmin[2] -= 1;
230 ent->absmax[0] += 1;
231 ent->absmax[1] += 1;
232 ent->absmax[2] += 1;
233
234 // link to PVS leafs
235 ent->num_clusters = 0;
236 ent->areanum = 0;
237 ent->areanum2 = 0;
238
239 //get all leafs, including solids
240 num_leafs = CM_BoxLeafnums(ent->absmin, ent->absmax,
241 leafs, MAX_TOTAL_ENT_LEAFS, &topnode);
242
243 // set areas
244 for(i = 0; i < num_leafs; i++){
245 clusters[i] = CM_LeafCluster(leafs[i]);
246 area = CM_LeafArea(leafs[i]);
247 if(area){ // doors may legally straggle two areas,
248 // but nothing should evern need more than that
249 if(ent->areanum && ent->areanum != area){
250 if(ent->areanum2 && ent->areanum2 != area && sv.state == ss_loading)
251 Com_DPrintf("Object touching 3 areas at %f %f %f\n",
252 ent->absmin[0], ent->absmin[1], ent->absmin[2]);
253 ent->areanum2 = area;
254 } else
255 ent->areanum = area;
256 }
257 }
258
259 if(num_leafs >= MAX_TOTAL_ENT_LEAFS){ // assume we missed some leafs, and mark by headnode
260 ent->num_clusters = -1;
261 ent->headnode = topnode;
262 } else {
263 ent->num_clusters = 0;
264 for(i = 0; i < num_leafs; i++){
265 if(clusters[i] == -1)
266 continue; // not a visible leaf
267 for(j = 0; j < i; j++)
268 if(clusters[j] == clusters[i])
269 break;
270 if(j == i){
271 if(ent->num_clusters == MAX_ENT_CLUSTERS){ // assume we missed some leafs, and mark by headnode
272 ent->num_clusters = -1;
273 ent->headnode = topnode;
274 break;
275 }
276
277 ent->clusternums[ent->num_clusters++] = clusters[i];
278 }
279 }
280 }
281
282 // if first time, make sure old_origin is valid
283 if(!ent->linkcount){
284 VectorCopy(ent->s.origin, ent->s.old_origin);
285 }
286 ent->linkcount++;
287
288 if(ent->solid == SOLID_NOT)
289 return;
290
291 // find the first node that the ent's box crosses
292 node = sv_areanodes;
293 while(1){
294 if(node->axis == -1)
295 break;
296 if(ent->absmin[node->axis] > node->dist)
297 node = node->children[0];
298 else if(ent->absmax[node->axis] < node->dist)
299 node = node->children[1];
300 else
301 break; // crosses the node
302 }
303
304 // link it in
305 if(ent->solid == SOLID_TRIGGER)
306 InsertLinkBefore(&ent->area, &node->trigger_edicts);
307 else
308 InsertLinkBefore(&ent->area, &node->solid_edicts);
309
310 }
311
312
313 /*
314 SV_AreaEdicts_r
315
316 */
SV_AreaEdicts_r(areanode_t * node)317 void SV_AreaEdicts_r(areanode_t *node){
318 link_t *l, *next, *start;
319 edict_t *check;
320 int count;
321
322 count = 0;
323
324 // touch linked edicts
325 if(area_type == AREA_SOLID)
326 start = &node->solid_edicts;
327 else
328 start = &node->trigger_edicts;
329
330 for(l = start->next; l != start; l = next){
331 next = l->next;
332 check = EDICT_FROM_AREA(l);
333
334 if(check->solid == SOLID_NOT)
335 continue; // deactivated
336 if(check->absmin[0] > area_maxs[0]
337 || check->absmin[1] > area_maxs[1]
338 || check->absmin[2] > area_maxs[2]
339 || check->absmax[0] < area_mins[0]
340 || check->absmax[1] < area_mins[1]
341 || check->absmax[2] < area_mins[2])
342 continue; // not touching
343
344 if(area_count == area_maxcount){
345 Com_Printf("SV_AreaEdicts: MAXCOUNT\n");
346 return;
347 }
348
349 area_list[area_count] = check;
350 area_count++;
351 }
352
353 if(node->axis == -1)
354 return; // terminal node
355
356 // recurse down both sides
357 if(area_maxs[node->axis] > node->dist)
358 SV_AreaEdicts_r(node->children[0]);
359 if(area_mins[node->axis] < node->dist)
360 SV_AreaEdicts_r(node->children[1]);
361 }
362
363 /*
364 SV_AreaEdicts
365 */
SV_AreaEdicts(vec3_t mins,vec3_t maxs,edict_t ** list,int maxcount,int areatype)366 int SV_AreaEdicts(vec3_t mins, vec3_t maxs, edict_t **list,
367 int maxcount, int areatype){
368 area_mins = mins;
369 area_maxs = maxs;
370 area_list = list;
371 area_count = 0;
372 area_maxcount = maxcount;
373 area_type = areatype;
374
375 SV_AreaEdicts_r(sv_areanodes);
376
377 return area_count;
378 }
379
380
381
382 /*
383 SV_PointContents
384 */
SV_PointContents(vec3_t p)385 int SV_PointContents(vec3_t p){
386 edict_t *touch[MAX_EDICTS], *hit;
387 int i, num;
388 int contents, c2;
389 int headnode;
390 float *angles;
391
392 // get base contents from world
393 contents = CM_PointContents(p, sv.models[1]->headnode);
394
395 // or in contents from all the other entities
396 num = SV_AreaEdicts(p, p, touch, MAX_EDICTS, AREA_SOLID);
397
398 for(i = 0; i < num; i++){
399 hit = touch[i];
400
401 // might intersect, so do an exact clip
402 headnode = SV_HullForEntity(hit);
403 angles = hit->s.angles;
404 if(hit->solid != SOLID_BSP)
405 angles = vec3_origin; // boxes don't rotate
406
407 c2 = CM_TransformedPointContents(p, headnode, hit->s.origin, hit->s.angles);
408
409 contents |= c2;
410 }
411
412 return contents;
413 }
414
415
416
417 typedef struct {
418 vec3_t boxmins, boxmaxs; // enclose the test object along entire move
419 float *mins, *maxs; // size of the moving object
420 vec3_t mins2, maxs2; // size when clipping against mosnters
421 float *start, *end;
422 trace_t trace;
423 edict_t *passedict;
424 int contentmask;
425 }
426 moveclip_t;
427
428
429
430 /*
431 SV_HullForEntity
432
433 Returns a headnode that can be used for testing or clipping an
434 object of mins/maxs size.
435 Offset is filled in to contain the adjustment that must be added to the
436 testing object's origin to get a point to use with the returned hull.
437 */
SV_HullForEntity(edict_t * ent)438 int SV_HullForEntity(edict_t *ent){
439 cmodel_t *model;
440
441 // decide which clipping hull to use, based on the size
442 if(ent->solid == SOLID_BSP){ // explicit hulls in the BSP model
443 model = sv.models[ ent->s.modelindex ];
444
445 if(!model)
446 Com_Error(ERR_FATAL, "MOVETYPE_PUSH with a non bsp model");
447
448 return model->headnode;
449 }
450
451 // create a temp hull from bounding box sizes
452
453 return CM_HeadnodeForBox(ent->mins, ent->maxs);
454 }
455
456
457
458 /*
459 SV_ClipMoveToEntities
460
461 */
SV_ClipMoveToEntities(moveclip_t * clip)462 void SV_ClipMoveToEntities(moveclip_t *clip){
463 int i, num;
464 edict_t *touchlist[MAX_EDICTS], *touch;
465 trace_t trace;
466 int headnode;
467 float *angles;
468
469 num = SV_AreaEdicts(clip->boxmins, clip->boxmaxs, touchlist
470 , MAX_EDICTS, AREA_SOLID);
471
472 // be careful, it is possible to have an entity in this
473 // list removed before we get to it(killtriggered)
474 for(i = 0; i < num; i++){
475 touch = touchlist[i];
476 if(touch->solid == SOLID_NOT)
477 continue;
478 if(touch == clip->passedict)
479 continue;
480 if(clip->trace.allsolid)
481 return;
482 if(clip->passedict){
483 if(touch->owner == clip->passedict)
484 continue; // don't clip against own missiles
485 if(clip->passedict->owner == touch)
486 continue; // don't clip against owner
487 }
488
489 if(!(clip->contentmask & CONTENTS_DEADMONSTER)
490 &&(touch->svflags & SVF_DEADMONSTER))
491 continue;
492
493 // might intersect, so do an exact clip
494 headnode = SV_HullForEntity(touch);
495 angles = touch->s.angles;
496 if(touch->solid != SOLID_BSP)
497 angles = vec3_origin; // boxes don't rotate
498
499 if(touch->svflags & SVF_MONSTER)
500 trace = CM_TransformedBoxTrace(clip->start, clip->end,
501 clip->mins2, clip->maxs2, headnode, clip->contentmask,
502 touch->s.origin, angles);
503 else
504 trace = CM_TransformedBoxTrace(clip->start, clip->end,
505 clip->mins, clip->maxs, headnode, clip->contentmask,
506 touch->s.origin, angles);
507
508 if(trace.allsolid || trace.startsolid ||
509 trace.fraction < clip->trace.fraction){
510 trace.ent = touch;
511 if(clip->trace.startsolid){
512 clip->trace = trace;
513 clip->trace.startsolid = true;
514 } else
515 clip->trace = trace;
516 } else if(trace.startsolid)
517 clip->trace.startsolid = true;
518 }
519 }
520
521
522 /*
523 SV_TraceBounds
524 */
SV_TraceBounds(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,vec3_t boxmins,vec3_t boxmaxs)525 void SV_TraceBounds(vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs){
526
527 int i;
528
529 for(i = 0; i < 3; i++){
530 if(end[i] > start[i]){
531 boxmins[i] = start[i] + mins[i] - 1;
532 boxmaxs[i] = end[i] + maxs[i] + 1;
533 } else {
534 boxmins[i] = end[i] + mins[i] - 1;
535 boxmaxs[i] = start[i] + maxs[i] + 1;
536 }
537 }
538 }
539
540 /*
541 SV_Trace
542
543 Moves the given mins/maxs volume through the world from start to end.
544
545 Passedict and edicts owned by passedict are explicitly not checked.
546
547 */
SV_Trace(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,edict_t * passedict,int contentmask)548 trace_t SV_Trace(vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, edict_t *passedict, int contentmask){
549 moveclip_t clip;
550
551 if(!mins)
552 mins = vec3_origin;
553 if(!maxs)
554 maxs = vec3_origin;
555
556 memset(&clip, 0, sizeof(moveclip_t));
557
558 // clip to world
559 clip.trace = CM_BoxTrace(start, end, mins, maxs, 0, contentmask);
560 clip.trace.ent = ge->edicts;
561 if(clip.trace.fraction == 0)
562 return clip.trace; // blocked by the world
563
564 clip.contentmask = contentmask;
565 clip.start = start;
566 clip.end = end;
567 clip.mins = mins;
568 clip.maxs = maxs;
569 clip.passedict = passedict;
570
571 VectorCopy(mins, clip.mins2);
572 VectorCopy(maxs, clip.maxs2);
573
574 // create the bounding box of the entire move
575 SV_TraceBounds(start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs);
576
577 // clip to other solid entities
578 SV_ClipMoveToEntities(&clip);
579
580 return clip.trace;
581 }
582