1 /*
2 * world.c -- world query functions
3 * $Id: world.c 6041 2018-05-31 07:00:13Z sezero $
4 *
5 * entities never clip against themselves, or their owner
6 * line of sight checks trace->crosscontent, but bullets don't
7 *
8 * Copyright (C) 1996-1997 Id Software, Inc.
9 * Copyright (C) 1997-1998 Raven Software Corp.
10 *
11 * This program is free software; you can redistribute it and/or modify
12 * it under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; either version 2 of the License, or (at
14 * your option) any later version.
15 *
16 * This program is distributed in the hope that it will be useful, but
17 * WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
19 *
20 * See the GNU General Public License for more details.
21 *
22 * You should have received a copy of the GNU General Public License along
23 * with this program; if not, write to the Free Software Foundation, Inc.,
24 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 */
26
27 #include "quakedef.h"
28
29 typedef struct
30 {
31 vec3_t boxmins, boxmaxs;// enclose the test object along entire move
32 float *mins, *maxs; // size of the moving object
33 vec3_t mins2, maxs2; // size when clipping against mosnters
34 float *start, *end;
35 trace_t trace;
36 int type;
37 edict_t *passedict;
38 } moveclip_t;
39
40 #if !id386
41 static int SV_HullPointContents (hull_t *hull, int num, vec3_t p);
42 #endif
43
44
45 /*
46 ===============================================================================
47
48 HULL BOXES
49
50 ===============================================================================
51 */
52
53
54 static hull_t box_hull;
55 static dclipnode_t box_clipnodes[6];
56 static mplane_t box_planes[6];
57 static int move_type;
58
59 /*
60 ===================
61 SV_InitBoxHull
62
63 Set up the planes and clipnodes so that the six floats of a bounding box
64 can just be stored out and get a proper hull_t structure.
65 ===================
66 */
SV_InitBoxHull(void)67 static void SV_InitBoxHull (void)
68 {
69 int i;
70 int side;
71
72 box_hull.clipnodes = box_clipnodes;
73 box_hull.planes = box_planes;
74 box_hull.firstclipnode = 0;
75 box_hull.lastclipnode = 5;
76
77 for (i = 0; i < 6; i++)
78 {
79 box_clipnodes[i].planenum = i;
80
81 side = i & 1;
82
83 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
84 if (i != 5)
85 box_clipnodes[i].children[side^1] = i + 1;
86 else
87 box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
88
89 box_planes[i].type = i>>1;
90 box_planes[i].normal[i>>1] = 1;
91 }
92 }
93
94
95 /*
96 ===================
97 SV_HullForBox
98
99 To keep everything totally uniform, bounding boxes are turned into small
100 BSP trees instead of being compared directly.
101 ===================
102 */
SV_HullForBox(vec3_t mins,vec3_t maxs)103 static hull_t *SV_HullForBox (vec3_t mins, vec3_t maxs)
104 {
105 box_planes[0].dist = maxs[0];
106 box_planes[1].dist = mins[0];
107 box_planes[2].dist = maxs[1];
108 box_planes[3].dist = mins[1];
109 box_planes[4].dist = maxs[2];
110 box_planes[5].dist = mins[2];
111
112 return &box_hull;
113 }
114
115
116 /*
117 ================
118 SV_HullForEntity
119
120 Returns a hull that can be used for testing or clipping an object of mins/maxs
121 size.
122 Offset is filled in to contain the adjustment that must be added to the
123 testing object's origin to get a point to use with the returned hull.
124 ================
125 */
SV_HullForEntity(edict_t * ent,vec3_t mins,vec3_t maxs,vec3_t offset,edict_t * move_ent)126 static hull_t *SV_HullForEntity (edict_t *ent, vec3_t mins, vec3_t maxs, vec3_t offset, edict_t *move_ent)
127 {
128 qmodel_t *model;
129 vec3_t size;
130 vec3_t hullmins, hullmaxs;
131 hull_t *hull;
132 int idx;
133
134 // decide which clipping hull to use, based on the size
135 if (ent->v.solid == SOLID_BSP)
136 { // explicit hulls in the BSP model
137 if (ent->v.movetype != MOVETYPE_PUSH)
138 Sys_Error ("SOLID_BSP without MOVETYPE_PUSH");
139
140 model = sv.models[ (int)ent->v.modelindex ];
141
142 if (!model || model->type != mod_brush)
143 Sys_Error ("SOLID_BSP with a non bsp model");
144
145 VectorSubtract (maxs, mins, size);
146
147 //THIS IS WHERE THE MONSTER STEPPING ERROR WAS- IN CHECKBOTTOM,
148 //A '0 0 0' MINS AND MAXS WERE SENT, BUT HERE, IT LOOKS TO SEE
149 //IF THE MONSTER HAS A HULL AND CALCULATES THE OFFSET FROM
150 //THE HULL MINS AND MAXS AND THE PASSED MINS AND MAXS,
151 //THIS WILL INCORRECTLY OFFSET THE TEST MOVE BY THE MINS AND
152 //MAXS OF THE MONSTER! WILL CHECK FOR SIDE EFFECTS...
153
154 if (move_ent->v.hull) // Entity is specifying which hull to use
155 {
156 idx = move_ent->v.hull-1;
157 hull = &model->hulls[idx];
158 if (!hull) // Invalid hull
159 {
160 Con_Printf ("ERROR: hull %d is null.\n", idx);
161 hull = &model->hulls[0];
162 }
163 }
164 else // Using the old way uses size to determine hull to use
165 {
166 // if ((int)move_ent->v.flags & FL_MONSTER)
167 // Con_DPrintf("ERROR: auto-detecing hull for monster!\n");
168 if (size[0] < 3) // Point
169 hull = &model->hulls[0];
170 else if ( (size[0] <= 8) && ((int)(sv.edicts->v.spawnflags) & 1) ) // Pentacles
171 hull = &model->hulls[4];
172 else if (size[0] <= 32 && size[2] <= 28) // Half Player
173 hull = &model->hulls[3];
174 else if (size[0] <= 32) // Full Player
175 hull = &model->hulls[1];
176 else // Golem
177 hull = &model->hulls[5];
178 }
179
180 // calculate an offset value to center the origin:
181 VectorSubtract (hull->clip_mins, mins, offset);
182 if ((int)move_ent->v.flags & FL_MONSTER)
183 {
184 if (offset[0] != 0 || offset[1] != 0)
185 {
186 // Con_DPrintf("ERROR: Non-zero offset (%f,%f,%f)!!!\n",
187 // offset[0], offset[1], offset[2]);
188 // 524288 (FL_MISMATCHEDBOUNDS ?) is an abandoned H2MP flag?
189 // if ((int)move_ent->v.flags2 & 524288)
190 offset[0] = 0;
191 offset[1] = 0;
192 }
193 }
194 VectorAdd (offset, ent->v.origin, offset);
195 }
196 else
197 { // create a temp hull from bounding box sizes
198 VectorSubtract (ent->v.mins, maxs, hullmins);
199 VectorSubtract (ent->v.maxs, mins, hullmaxs);
200 hull = SV_HullForBox (hullmins, hullmaxs);
201
202 VectorCopy (ent->v.origin, offset);
203 }
204
205 return hull;
206 }
207
208 /*
209 ===============================================================================
210
211 ENTITY AREA CHECKING
212
213 ===============================================================================
214 */
215
216 static areanode_t sv_areanodes[AREA_NODES];
217 static int sv_numareanodes;
218
219 /*
220 ===============
221 SV_CreateAreaNode
222
223 ===============
224 */
SV_CreateAreaNode(int depth,vec3_t mins,vec3_t maxs)225 static areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
226 {
227 areanode_t *anode;
228 vec3_t size;
229 vec3_t mins1, maxs1, mins2, maxs2;
230
231 anode = &sv_areanodes[sv_numareanodes];
232 sv_numareanodes++;
233
234 ClearLink (&anode->trigger_edicts);
235 ClearLink (&anode->solid_edicts);
236
237 if (depth == AREA_DEPTH)
238 {
239 anode->axis = -1;
240 anode->children[0] = anode->children[1] = NULL;
241 return anode;
242 }
243
244 VectorSubtract (maxs, mins, size);
245 if (size[0] > size[1])
246 anode->axis = 0;
247 else
248 anode->axis = 1;
249
250 anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
251 VectorCopy (mins, mins1);
252 VectorCopy (mins, mins2);
253 VectorCopy (maxs, maxs1);
254 VectorCopy (maxs, maxs2);
255
256 maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
257
258 anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
259 anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
260
261 return anode;
262 }
263
264 /*
265 ===============
266 SV_ClearWorld
267
268 ===============
269 */
SV_ClearWorld(void)270 void SV_ClearWorld (void)
271 {
272 SV_InitBoxHull ();
273
274 memset (sv_areanodes, 0, sizeof(sv_areanodes));
275 sv_numareanodes = 0;
276 SV_CreateAreaNode (0, sv.worldmodel->mins, sv.worldmodel->maxs);
277 }
278
279
280 /*
281 ===============
282 SV_UnlinkEdict
283
284 ===============
285 */
286 static link_t **sv_link_next;
287 static link_t **sv_link_prev;
288
SV_UnlinkEdict(edict_t * ent)289 void SV_UnlinkEdict (edict_t *ent)
290 {
291 if (!ent->area.prev)
292 return; // not linked in anywhere
293 RemoveLink (&ent->area);
294 if (sv_link_next && *sv_link_next == &ent->area)
295 *sv_link_next = ent->area.next;
296 if (sv_link_prev && *sv_link_prev == &ent->area)
297 *sv_link_prev = ent->area.prev;
298 ent->area.prev = ent->area.next = NULL;
299 }
300
301
302 /*
303 ====================
304 SV_TouchLinks
305 ====================
306 */
SV_TouchLinks(edict_t * ent,areanode_t * node)307 static void SV_TouchLinks (edict_t *ent, areanode_t *node)
308 {
309 link_t *l, *lnext;
310 edict_t *touch;
311 int old_self, old_other;
312
313 loc0:
314 // touch linked edicts
315 sv_link_next = &lnext;
316 for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = lnext)
317 {
318 if (!l)
319 {
320 // my area got removed out from under me!
321 Con_Printf ("%s: encountered NULL link!\n", __thisfunc__);
322 break;
323 }
324
325 lnext = l->next;
326 touch = EDICT_FROM_AREA(l);
327 if (touch == ent)
328 continue;
329 if (!touch->v.touch || touch->v.solid != SOLID_TRIGGER)
330 continue;
331 if (ent->v.absmin[0] > touch->v.absmax[0]
332 || ent->v.absmin[1] > touch->v.absmax[1]
333 || ent->v.absmin[2] > touch->v.absmax[2]
334 || ent->v.absmax[0] < touch->v.absmin[0]
335 || ent->v.absmax[1] < touch->v.absmin[1]
336 || ent->v.absmax[2] < touch->v.absmin[2] )
337 continue;
338
339 old_self = *sv_globals.self;
340 old_other = *sv_globals.other;
341
342 *sv_globals.self = EDICT_TO_PROG(touch);
343 *sv_globals.other = EDICT_TO_PROG(ent);
344 *sv_globals.time = sv.time;
345 PR_ExecuteProgram (touch->v.touch);
346
347 *sv_globals.self = old_self;
348 *sv_globals.other = old_other;
349 }
350
351 sv_link_next = NULL;
352
353 // recurse down both sides
354 if (node->axis == -1)
355 return;
356
357 // LordHavoc: optimized recursion
358 //if (ent->v.absmax[node->axis] > node->dist) SV_TouchLinks (ent, node->children[0]);
359 //if (ent->v.absmin[node->axis] < node->dist) SV_TouchLinks (ent, node->children[1]);
360 if (ent->v.absmax[node->axis] > node->dist)
361 {
362 if (ent->v.absmin[node->axis] < node->dist)
363 SV_TouchLinks(ent, node->children[1]); // order reversed to reduce code
364 node = node->children[0];
365 goto loc0;
366 }
367 else
368 {
369 if (ent->v.absmin[node->axis] < node->dist)
370 {
371 node = node->children[1];
372 goto loc0;
373 }
374 }
375 }
376
377
378 /*
379 ===============
380 SV_FindTouchedLeafs
381
382 ===============
383 */
SV_FindTouchedLeafs(edict_t * ent,mnode_t * node)384 static void SV_FindTouchedLeafs (edict_t *ent, mnode_t *node)
385 {
386 mplane_t *splitplane;
387 mleaf_t *leaf;
388 int sides;
389 int leafnum;
390
391 loc0:
392 if (node->contents == CONTENTS_SOLID)
393 return;
394
395 // add an efrag if the node is a leaf
396
397 if (node->contents < 0)
398 {
399 if (ent->num_leafs == MAX_ENT_LEAFS)
400 return;
401
402 leaf = (mleaf_t *)node;
403 leafnum = leaf - sv.worldmodel->leafs - 1;
404
405 ent->leafnums[ent->num_leafs] = leafnum;
406 ent->num_leafs++;
407 return;
408 }
409
410 // NODE_MIXED
411
412 splitplane = node->plane;
413 sides = BOX_ON_PLANE_SIDE(ent->v.absmin, ent->v.absmax, splitplane);
414
415 // recurse down the contacted sides
416 // LordHavoc: optimized recursion
417 //if (sides & 1) SV_FindTouchedLeafs (ent, node->children[0]);
418 //if (sides & 2) SV_FindTouchedLeafs (ent, node->children[1]);
419 switch (sides)
420 {
421 case 1:
422 node = node->children[0];
423 goto loc0;
424 case 2:
425 node = node->children[1];
426 goto loc0;
427 default: // 3
428 if (node->children[0]->contents != CONTENTS_SOLID)
429 SV_FindTouchedLeafs (ent, node->children[0]);
430 node = node->children[1];
431 goto loc0;
432 }
433 }
434
435 /*
436 ===============
437 SV_LinkEdict
438
439 ===============
440 */
SV_LinkEdict(edict_t * ent,qboolean touch_triggers)441 void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
442 {
443 areanode_t *node;
444
445 if (ent->area.prev)
446 SV_UnlinkEdict (ent); // unlink from old position
447
448 if (ent == sv.edicts)
449 return; // don't add the world
450
451 if (ent->free)
452 return;
453
454 // set the abs box
455 if (ent->v.solid == SOLID_BSP &&
456 (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]) )
457 { // expand for rotation
458 float v, maxv;
459 int i;
460
461 maxv = 0;
462 for (i = 0; i < 3; i++)
463 {
464 v = fabs(ent->v.mins[i]);
465 if (v > maxv)
466 maxv = v;
467 v = fabs(ent->v.maxs[i]);
468 if (v > maxv)
469 maxv = v;
470 }
471 for (i = 0; i < 3; i++)
472 {
473 ent->v.absmin[i] = ent->v.origin[i] - maxv;
474 ent->v.absmax[i] = ent->v.origin[i] + maxv;
475 }
476 }
477 else
478 {
479 VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);
480 VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
481 }
482
483 //
484 // to make items easier to pick up and allow them to be grabbed off
485 // of shelves, the abs sizes are expanded
486 //
487 if ((int)ent->v.flags & FL_ITEM)
488 {
489 ent->v.absmin[0] -= 15;
490 ent->v.absmin[1] -= 15;
491 ent->v.absmax[0] += 15;
492 ent->v.absmax[1] += 15;
493 }
494 else
495 { // because movement is clipped an epsilon away from an actual edge,
496 // we must fully check even when bounding boxes don't quite touch
497 ent->v.absmin[0] -= 1;
498 ent->v.absmin[1] -= 1;
499 ent->v.absmin[2] -= 1;
500 ent->v.absmax[0] += 1;
501 ent->v.absmax[1] += 1;
502 ent->v.absmax[2] += 1;
503 }
504
505 // link to PVS leafs
506 ent->num_leafs = 0;
507 if (ent->v.modelindex)
508 SV_FindTouchedLeafs (ent, sv.worldmodel->nodes);
509
510 if (ent->v.solid == SOLID_NOT)
511 return;
512
513 // find the first node that the ent's box crosses
514 node = sv_areanodes;
515 while (1)
516 {
517 if (node->axis == -1)
518 break;
519 if (ent->v.absmin[node->axis] > node->dist)
520 node = node->children[0];
521 else if (ent->v.absmax[node->axis] < node->dist)
522 node = node->children[1];
523 else
524 break; // crosses the node
525 }
526
527 // link it in
528
529 if (ent->v.solid == SOLID_TRIGGER)
530 InsertLinkBefore (&ent->area, &node->trigger_edicts);
531 else
532 InsertLinkBefore (&ent->area, &node->solid_edicts);
533
534 // if touch_triggers, touch all entities at this node and decend for more
535 if (touch_triggers)
536 SV_TouchLinks ( ent, sv_areanodes );
537 }
538
539
540 /*
541 ===============================================================================
542
543 POINT TESTING IN HULLS
544
545 ===============================================================================
546 */
547
548 #if !id386
549
550 /*
551 ==================
552 SV_HullPointContents
553
554 ==================
555 */
SV_HullPointContents(hull_t * hull,int num,vec3_t p)556 static int SV_HullPointContents (hull_t *hull, int num, vec3_t p)
557 {
558 float d;
559 dclipnode_t *node;
560 mplane_t *plane;
561
562 while (num >= 0)
563 {
564 if (num < hull->firstclipnode || num > hull->lastclipnode)
565 Sys_Error ("%s: bad node number", __thisfunc__);
566
567 node = hull->clipnodes + num;
568 plane = hull->planes + node->planenum;
569
570 if (plane->type < 3)
571 d = p[plane->type] - plane->dist;
572 else
573 d = DotProductDBL(plane->normal, p) - plane->dist;
574 if (d < 0)
575 num = node->children[1];
576 else
577 num = node->children[0];
578 }
579
580 return num;
581 }
582
583 #endif /* !id386 */
584
585
586 /*
587 ==================
588 SV_PointContents
589
590 ==================
591 */
SV_PointContents(vec3_t p)592 int SV_PointContents (vec3_t p)
593 {
594 int cont;
595
596 cont = SV_HullPointContents (&sv.worldmodel->hulls[0], 0, p);
597 if (cont <= CONTENTS_CURRENT_0 && cont >= CONTENTS_CURRENT_DOWN)
598 cont = CONTENTS_WATER;
599 return cont;
600 }
601
602 #ifdef QUAKE2
SV_TruePointContents(vec3_t p)603 int SV_TruePointContents (vec3_t p)
604 {
605 return SV_HullPointContents (&sv.worldmodel->hulls[0], 0, p);
606 }
607 #endif
608
609 //===========================================================================
610
611 /*
612 ============
613 SV_TestEntityPosition
614
615 This could be a lot more efficient...
616 FIXME!!! For rotating doors, this is totally inaccurate
617 ============
618 */
SV_TestEntityPosition(edict_t * ent)619 edict_t *SV_TestEntityPosition (edict_t *ent)
620 {
621 trace_t trace;
622
623 trace = SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, 0, ent);
624
625 if (trace.startsolid)
626 {
627 // Con_DPrintf("%s inside check\n", PR_GetString(trace.ent->v.classname));
628 return sv.edicts;
629 }
630
631 return NULL;
632 }
633
634
635 /*
636 ===============================================================================
637
638 LINE TESTING IN HULLS
639
640 ===============================================================================
641 */
642
WackyBugFixer(float * p1,float * p2,float * frac,float * mid)643 static void WackyBugFixer(float *p1, float *p2, float *frac, float *mid)
644 {
645 int i;
646
647 for (i = 0; i < 3; i++)
648 mid[i] = p1[i] + (*frac)*(p2[i] - p1[i]);
649 }
650
651 /*
652 ==================
653 SV_RecursiveHullCheck
654
655 ==================
656 */
SV_RecursiveHullCheck(hull_t * hull,int num,float p1f,float p2f,vec3_t p1,vec3_t p2,trace_t * trace)657 qboolean SV_RecursiveHullCheck (hull_t *hull, int num, float p1f, float p2f, vec3_t p1, vec3_t p2, trace_t *trace)
658 {
659 dclipnode_t *node;
660 mplane_t *plane;
661 float t1, t2;
662 float frac;
663 int i;
664 vec3_t mid;
665 int side;
666 float midf;
667 int contents;
668
669 loc0: // optimized recursion
670
671 // check for empty
672 if (num < 0)
673 {
674 if (num != CONTENTS_SOLID)
675 {
676 trace->allsolid = false;
677 if (num == CONTENTS_EMPTY)
678 trace->inopen = true;
679 else
680 trace->inwater = true;
681 }
682 else
683 trace->startsolid = true;
684
685 return true; // empty
686 }
687
688 if (num < hull->firstclipnode || num > hull->lastclipnode)
689 Sys_Error ("%s: bad node number", __thisfunc__);
690
691 //
692 // find the point distances
693 //
694 node = hull->clipnodes + num;
695 plane = hull->planes + node->planenum;
696
697 if (plane->type < 3)
698 {
699 t1 = p1[plane->type] - plane->dist;
700 t2 = p2[plane->type] - plane->dist;
701 }
702 else
703 {
704 t1 = DotProductDBL(plane->normal, p1) - plane->dist;
705 t2 = DotProductDBL(plane->normal, p2) - plane->dist;
706 }
707
708 #if 1
709 if (t1 >= 0 && t2 >= 0)
710 {
711 //return SV_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
712 num = node->children[0];
713 goto loc0;
714 }
715 if (t1 < 0 && t2 < 0)
716 {
717 //return SV_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
718 num = node->children[1];
719 goto loc0;
720 }
721 #else
722 if ( (t1 >= DIST_EPSILON && t2 >= DIST_EPSILON) || (t2 > t1 && t1 >= 0) )
723 return SV_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
724 if ( (t1 <= -DIST_EPSILON && t2 <= -DIST_EPSILON) || (t2 < t1 && t1 <= 0) )
725 return SV_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
726 #endif
727
728 // put the crosspoint DIST_EPSILON pixels on the near side
729 side = (t1 < 0);
730 if (side)
731 frac = (t1 + DIST_EPSILON)/(t1-t2);
732 else
733 frac = (t1 - DIST_EPSILON)/(t1-t2);
734 if (frac < 0)
735 frac = 0;
736 else if (frac > 1)
737 frac = 1;
738
739 midf = p1f + (p2f - p1f)*frac;
740 for (i = 0; i < 3; i++)
741 mid[i] = p1[i] + frac*(p2[i] - p1[i]);
742
743 // move up to the node
744 if (!SV_RecursiveHullCheck (hull, node->children[side], p1f, midf, p1, mid, trace) )
745 return false;
746
747 #ifdef PARANOID
748 if (SV_HullPointContents (hull, node->children[side], mid) == CONTENTS_SOLID)
749 {
750 Con_Printf ("mid PointInHullSolid\n");
751 return false;
752 }
753 #endif
754
755 // LordHavoc: this recursion can not be optimized because mid would need to be duplicated on a stack
756 contents = SV_HullPointContents (hull, node->children[side^1], mid);
757 // if (contents != CONTENTS_SOLID && (contents == CONTENTS_WATER || move_type != MOVE_WATER))
758 if (contents != CONTENTS_SOLID)
759 // go past the node
760 return SV_RecursiveHullCheck (hull, node->children[side^1], midf, p2f, mid, p2, trace);
761
762 if (trace->allsolid)
763 return false; // never got out of the solid area
764
765 //==================
766 // the other side of the node is solid, this is the impact point
767 //==================
768 if (!side)
769 {
770 VectorCopy (plane->normal, trace->plane.normal);
771 trace->plane.dist = plane->dist;
772 }
773 else
774 {
775 VectorNegate (plane->normal, trace->plane.normal);
776 trace->plane.dist = -plane->dist;
777 }
778
779 // while (SV_HullPointContents (hull, hull->firstclipnode, mid) == CONTENTS_SOLID)
780 while (1)
781 {
782 // shouldn't really happen, but does occasionally
783 contents = SV_HullPointContents (hull, hull->firstclipnode, mid);
784 // if (contents != CONTENTS_SOLID && (contents == CONTENTS_WATER || move_type != MOVE_WATER))
785 if (contents != CONTENTS_SOLID)
786 break;
787
788 frac -= 0.1;
789 if (frac < 0)
790 {
791 trace->fraction = midf;
792 VectorCopy (mid, trace->endpos);
793 Con_DPrintf ("backup past 0\n");
794 return false;
795 }
796 midf = p1f + (p2f - p1f)*frac;
797
798 // for (i = 0; i < 3; i++)
799 // mid[i] = p1[i] + frac * (p2[i] - p1[i]);
800
801 WackyBugFixer(p1, p2, &frac, mid);
802 }
803
804 trace->fraction = midf;
805 VectorCopy (mid, trace->endpos);
806
807 return false;
808 }
809
810
811 /*
812 ==================
813 SV_ClipMoveToEntity
814
815 Handles selection or creation of a clipping hull, and offseting (and
816 eventually rotation) of the end points
817 ==================
818 */
SV_ClipMoveToEntity(edict_t * ent,vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,edict_t * move_ent)819 static trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, edict_t *move_ent)
820 {
821 trace_t trace;
822 vec3_t offset;
823 vec3_t start_l, end_l;
824 hull_t *hull;
825
826 // fill in a default trace
827 memset (&trace, 0, sizeof(trace_t));
828 trace.fraction = 1;
829 trace.allsolid = true;
830 VectorCopy (end, trace.endpos);
831
832 // get the clipping hull
833 hull = SV_HullForEntity (ent, mins, maxs, offset, move_ent);
834
835 VectorSubtract (start, offset, start_l);
836 VectorSubtract (end, offset, end_l);
837
838 // rotate start and end into the models frame of reference
839 if (ent->v.solid == SOLID_BSP &&
840 (fabs(ent->v.angles[0]) > 1 || fabs(ent->v.angles[1]) > 1 || fabs(ent->v.angles[2]) > 1) )
841 {
842 vec3_t forward, right, up;
843 vec3_t temp;
844
845 AngleVectors (ent->v.angles, forward, right, up);
846
847 VectorCopy (start_l, temp);
848 start_l[0] = DotProduct (temp, forward);
849 start_l[1] = -DotProduct (temp, right);
850 start_l[2] = DotProduct (temp, up);
851
852 VectorCopy (end_l, temp);
853 end_l[0] = DotProduct (temp, forward);
854 end_l[1] = -DotProduct (temp, right);
855 end_l[2] = DotProduct (temp, up);
856 }
857
858 // trace a line through the apropriate clipping hull
859 SV_RecursiveHullCheck (hull, hull->firstclipnode, 0, 1, start_l, end_l, &trace);
860
861 if (move_type == MOVE_WATER)
862 {
863 if (SV_PointContents (trace.endpos) != CONTENTS_WATER)
864 {
865 VectorCopy(start_l, trace.endpos);
866 trace.fraction = 0;
867 }
868 }
869
870 // rotate endpos back to world frame of reference
871 if (ent->v.solid == SOLID_BSP &&
872 (fabs(ent->v.angles[0]) > 1 || fabs(ent->v.angles[1]) > 1 || fabs(ent->v.angles[2]) > 1) )
873 {
874 vec3_t a;
875 vec3_t forward, right, up;
876 vec3_t temp;
877
878 if (trace.fraction != 1)
879 {
880 VectorNegate (ent->v.angles, a);
881 AngleVectors (a, forward, right, up);
882
883 VectorCopy (trace.endpos, temp);
884 trace.endpos[0] = DotProduct (temp, forward);
885 trace.endpos[1] = -DotProduct (temp, right);
886 trace.endpos[2] = DotProduct (temp, up);
887
888 VectorCopy (trace.plane.normal, temp);
889 trace.plane.normal[0] = DotProduct (temp, forward);
890 trace.plane.normal[1] = -DotProduct (temp, right);
891 trace.plane.normal[2] = DotProduct (temp, up);
892 }
893 }
894
895 // fix trace up by the offset
896 if (trace.fraction != 1)
897 VectorAdd (trace.endpos, offset, trace.endpos);
898
899 // did we clip the move?
900 if (trace.fraction < 1 || trace.startsolid)
901 trace.ent = ent;
902
903 return trace;
904 }
905
906 //===========================================================================
907
908 /*
909 ====================
910 SV_ClipToLinks
911
912 Mins and maxs enclose the entire area swept by the move
913 ====================
914 */
SV_ClipToLinks(areanode_t * node,moveclip_t * clip)915 static void SV_ClipToLinks (areanode_t *node, moveclip_t *clip)
916 {
917 link_t *l, *next;
918 edict_t *touch;
919 trace_t trace;
920
921 loc0: // optimized recursion
922
923 // touch linked edicts
924 for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
925 {
926 next = l->next;
927 touch = EDICT_FROM_AREA(l);
928 if (touch->v.solid == SOLID_NOT)
929 continue;
930 if (touch == clip->passedict)
931 continue;
932 if (touch->v.solid == SOLID_TRIGGER)
933 Sys_Error ("Trigger in clipping list (%s)", PR_GetString(touch->v.classname));
934
935 if ((clip->type == MOVE_NOMONSTERS || clip->type == MOVE_PHASE)
936 && touch->v.solid != SOLID_BSP)
937 continue;
938
939 if (clip->boxmins[0] > touch->v.absmax[0]
940 || clip->boxmins[1] > touch->v.absmax[1]
941 || clip->boxmins[2] > touch->v.absmax[2]
942 || clip->boxmaxs[0] < touch->v.absmin[0]
943 || clip->boxmaxs[1] < touch->v.absmin[1]
944 || clip->boxmaxs[2] < touch->v.absmin[2] )
945 continue;
946
947 if (clip->passedict && clip->passedict->v.size[0] && !touch->v.size[0])
948 continue; // points never interact
949
950 // might intersect, so do an exact clip
951 if (clip->trace.allsolid)
952 return;
953 if (clip->passedict)
954 {
955 if (PROG_TO_EDICT(touch->v.owner) == clip->passedict)
956 continue; // don't clip against own missiles
957 if (PROG_TO_EDICT(clip->passedict->v.owner) == touch)
958 continue; // don't clip against owner
959 }
960
961 if ((int)touch->v.flags & FL_MONSTER)
962 trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end, touch);
963 else
964 trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end, touch);
965 if (trace.allsolid || trace.startsolid || trace.fraction < clip->trace.fraction)
966 {
967 trace.ent = touch;
968 if (clip->trace.startsolid)
969 {
970 clip->trace = trace;
971 clip->trace.startsolid = true;
972 }
973 else
974 clip->trace = trace;
975 }
976 else if (trace.startsolid)
977 clip->trace.startsolid = true;
978 }
979
980 // recurse down both sides
981 if (node->axis == -1)
982 return;
983
984 if ( clip->boxmaxs[node->axis] > node->dist )
985 {
986 //SV_ClipToLinks ( node->children[0], clip );
987 if (clip->boxmins[node->axis] < node->dist)
988 SV_ClipToLinks(node->children[1], clip);
989 node = node->children[0];
990 goto loc0;
991 }
992 else if ( clip->boxmins[node->axis] < node->dist )
993 {
994 //SV_ClipToLinks ( node->children[1], clip );
995 node = node->children[1];
996 goto loc0;
997 }
998 }
999
1000
1001 /*
1002 ==================
1003 SV_MoveBounds
1004 ==================
1005 */
SV_MoveBounds(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,vec3_t boxmins,vec3_t boxmaxs)1006 static void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
1007 {
1008 #if 0
1009 // debug to test against everything
1010 boxmins[0] = boxmins[1] = boxmins[2] = -9999;
1011 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] = 9999;
1012 #else
1013 int i;
1014
1015 for (i = 0; i < 3; i++)
1016 {
1017 if (end[i] > start[i])
1018 {
1019 boxmins[i] = start[i] + mins[i] - 1;
1020 boxmaxs[i] = end[i] + maxs[i] + 1;
1021 }
1022 else
1023 {
1024 boxmins[i] = end[i] + mins[i] - 1;
1025 boxmaxs[i] = start[i] + maxs[i] + 1;
1026 }
1027 }
1028 #endif
1029 }
1030
1031 /*
1032 ==================
1033 SV_Move
1034 ==================
1035 */
SV_Move(vec3_t start,vec3_t mins,vec3_t maxs,vec3_t end,int type,edict_t * passedict)1036 trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
1037 {
1038 moveclip_t clip;
1039 int i;
1040
1041 // type = MOVE_WATER;
1042 memset ( &clip, 0, sizeof ( moveclip_t ) );
1043
1044 move_type = type;
1045 // clip to world
1046 clip.trace = SV_ClipMoveToEntity ( sv.edicts, start, mins, maxs, end, passedict );
1047
1048 clip.start = start;
1049 clip.end = end;
1050 clip.mins = mins;
1051 clip.maxs = maxs;
1052 clip.type = type;
1053 clip.passedict = passedict;
1054
1055 if (type == MOVE_MISSILE || type == MOVE_PHASE)
1056 {
1057 //Larger for projectiles against monsters
1058 for (i = 0; i < 3; i++)
1059 {
1060 clip.mins2[i] = -15;
1061 clip.maxs2[i] = 15;
1062 }
1063 }
1064 else
1065 {
1066 VectorCopy (mins, clip.mins2);
1067 VectorCopy (maxs, clip.maxs2);
1068 }
1069
1070 // create the bounding box of the entire move
1071 SV_MoveBounds ( start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs );
1072
1073 // clip to entities
1074 SV_ClipToLinks ( sv_areanodes, &clip );
1075
1076 return clip.trace;
1077 }
1078
1079