Check bbox for overlap even on bmodels again (disabling it was a speed loss)
[divverent/darkplaces.git] / world.c
1 /*
2 Copyright (C) 1996-1997 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 // world.c -- world query functions
21
22 #include "quakedef.h"
23
24 /*
25
26 entities never clip against themselves, or their owner
27
28 line of sight checks trace->crosscontent, but bullets don't
29
30 */
31
32 /*
33 typedef struct link_s
34 {
35         struct link_s   *prev, *next;
36 } link_t;
37 */
38
39
40 void ClearLink (link_t *l);
41 void RemoveLink (link_t *l);
42 void InsertLinkBefore (link_t *l, link_t *before);
43 void InsertLinkAfter (link_t *l, link_t *after);
44
45 // (type *)STRUCT_FROM_LINK(link_t *link, type, member)
46 // ent = STRUCT_FROM_LINK(link,entity_t,order)
47 // FIXME: remove this mess!
48 //#define       STRUCT_FROM_LINK(l,t,m) ((t *)((qbyte *)l - (int)&(((t *)0)->m)))
49
50 #define EDICT_FROM_AREA(l) ((edict_t *)((qbyte *)l - (int)&(((edict_t *)0)->area)))
51
52 //============================================================================
53
54 // ClearLink is used for new headnodes
55 void ClearLink (link_t *l)
56 {
57         l->prev = l->next = l;
58 }
59
60 void RemoveLink (link_t *l)
61 {
62         l->next->prev = l->prev;
63         l->prev->next = l->next;
64 }
65
66 void InsertLinkBefore (link_t *l, link_t *before)
67 {
68         l->next = before;
69         l->prev = before->prev;
70         l->prev->next = l;
71         l->next->prev = l;
72 }
73 void InsertLinkAfter (link_t *l, link_t *after)
74 {
75         l->next = after->next;
76         l->prev = after;
77         l->prev->next = l;
78         l->next->prev = l;
79 }
80
81
82 typedef struct
83 {
84         vec3_t          boxmins, boxmaxs;// enclose the test object along entire move
85         float           *mins, *maxs;   // size of the moving object
86         vec3_t          mins2, maxs2;   // size when clipping against mosnters
87         float           *start, *end;
88         trace_t         trace;
89         int                     type;
90         edict_t         *passedict;
91 } moveclip_t;
92
93
94 /*
95 ===============================================================================
96
97 HULL BOXES
98
99 ===============================================================================
100 */
101
102
103 static  hull_t          box_hull;
104 static  dclipnode_t     box_clipnodes[6];
105 static  mplane_t        box_planes[6];
106
107 /*
108 ===================
109 SV_InitBoxHull
110
111 Set up the planes and clipnodes so that the six floats of a bounding box
112 can just be stored out and get a proper hull_t structure.
113 ===================
114 */
115 void SV_InitBoxHull (void)
116 {
117         int             i;
118         int             side;
119
120         box_hull.clipnodes = box_clipnodes;
121         box_hull.planes = box_planes;
122         box_hull.firstclipnode = 0;
123         box_hull.lastclipnode = 5;
124
125         for (i=0 ; i<6 ; i++)
126         {
127                 box_clipnodes[i].planenum = i;
128
129                 side = i&1;
130
131                 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
132                 if (i != 5)
133                         box_clipnodes[i].children[side^1] = i + 1;
134                 else
135                         box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
136
137                 box_planes[i].type = i>>1;
138                 box_planes[i].normal[i>>1] = 1;
139         }
140 }
141
142
143 /*
144 ===================
145 SV_HullForBox
146
147 To keep everything totally uniform, bounding boxes are turned into small
148 BSP trees instead of being compared directly.
149 ===================
150 */
151 hull_t  *SV_HullForBox (vec3_t mins, vec3_t maxs)
152 {
153         box_planes[0].dist = maxs[0];
154         box_planes[1].dist = mins[0];
155         box_planes[2].dist = maxs[1];
156         box_planes[3].dist = mins[1];
157         box_planes[4].dist = maxs[2];
158         box_planes[5].dist = mins[2];
159
160         return &box_hull;
161 }
162
163
164
165 /*
166 ================
167 SV_HullForEntity
168
169 Returns a hull that can be used for testing or clipping an object of mins/maxs
170 size.
171 Offset is filled in to contain the adjustment that must be added to the
172 testing object's origin to get a point to use with the returned hull.
173 ================
174 */
175 hull_t *SV_HullForEntity (edict_t *ent, vec3_t mins, vec3_t maxs, vec3_t offset)
176 {
177         model_t         *model;
178         vec3_t          size;
179         vec3_t          hullmins, hullmaxs;
180         hull_t          *hull;
181
182 // decide which clipping hull to use, based on the size
183         if (ent->v.solid == SOLID_BSP)
184         {       // explicit hulls in the BSP model
185                 if (ent->v.movetype != MOVETYPE_PUSH)
186                         Host_Error ("SOLID_BSP without MOVETYPE_PUSH");
187
188                 model = sv.models[ (int)ent->v.modelindex ];
189                 Mod_CheckLoaded(model);
190
191                 // LordHavoc: fixed SOLID_BSP error message
192                 if (!model || model->type != mod_brush)
193                 {
194                         Con_Printf ("SOLID_BSP with a non bsp model, entity dump:\n");
195                         ED_Print (ent);
196                         Host_Error ("SOLID_BSP with a non bsp model\n");
197                 }
198
199                 VectorSubtract (maxs, mins, size);
200                 // LordHavoc: FIXME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
201                 if (sv.worldmodel->ishlbsp)
202                 {
203                         if (size[0] < 3)
204                                 hull = &model->hulls[0]; // 0x0x0
205                         else if (size[0] <= 32)
206                         {
207                                 if (size[2] < 54) // pick the nearest of 36 or 72
208                                         hull = &model->hulls[3]; // 32x32x36
209                                 else
210                                         hull = &model->hulls[1]; // 32x32x72
211                         }
212                         else
213                                 hull = &model->hulls[2]; // 64x64x64
214                 }
215                 else
216                 {
217                         if (size[0] < 3)
218                                 hull = &model->hulls[0]; // 0x0x0
219                         else if (size[0] <= 32)
220                                 hull = &model->hulls[1]; // 32x32x56
221                         else
222                                 hull = &model->hulls[2]; // 64x64x88
223                 }
224
225 // calculate an offset value to center the origin
226                 VectorSubtract (hull->clip_mins, mins, offset);
227                 VectorAdd (offset, ent->v.origin, offset);
228         }
229         else
230         {       // create a temp hull from bounding box sizes
231
232                 VectorSubtract (ent->v.mins, maxs, hullmins);
233                 VectorSubtract (ent->v.maxs, mins, hullmaxs);
234                 hull = SV_HullForBox (hullmins, hullmaxs);
235
236                 VectorCopy (ent->v.origin, offset);
237         }
238
239
240         return hull;
241 }
242
243 /*
244 ===============================================================================
245
246 ENTITY AREA CHECKING
247
248 ===============================================================================
249 */
250
251 typedef struct areanode_s
252 {
253         int             axis;           // -1 = leaf node
254         float   dist;
255         struct areanode_s       *children[2];
256         link_t  trigger_edicts;
257         link_t  solid_edicts;
258 } areanode_t;
259
260 #define AREA_DEPTH      4
261 #define AREA_NODES      32
262
263 static  areanode_t      sv_areanodes[AREA_NODES];
264 static  int                     sv_numareanodes;
265
266 /*
267 ===============
268 SV_CreateAreaNode
269
270 ===============
271 */
272 areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
273 {
274         areanode_t      *anode;
275         vec3_t          size;
276         vec3_t          mins1, maxs1, mins2, maxs2;
277
278         anode = &sv_areanodes[sv_numareanodes];
279         sv_numareanodes++;
280
281         ClearLink (&anode->trigger_edicts);
282         ClearLink (&anode->solid_edicts);
283
284         if (depth == AREA_DEPTH)
285         {
286                 anode->axis = -1;
287                 anode->children[0] = anode->children[1] = NULL;
288                 return anode;
289         }
290
291         VectorSubtract (maxs, mins, size);
292         if (size[0] > size[1])
293                 anode->axis = 0;
294         else
295                 anode->axis = 1;
296
297         anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
298         VectorCopy (mins, mins1);
299         VectorCopy (mins, mins2);
300         VectorCopy (maxs, maxs1);
301         VectorCopy (maxs, maxs2);
302
303         maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
304
305         anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
306         anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
307
308         return anode;
309 }
310
311 /*
312 ===============
313 SV_ClearWorld
314
315 ===============
316 */
317 void SV_ClearWorld (void)
318 {
319         SV_InitBoxHull ();
320
321         memset (sv_areanodes, 0, sizeof(sv_areanodes));
322         sv_numareanodes = 0;
323         Mod_CheckLoaded(sv.worldmodel);
324         SV_CreateAreaNode (0, sv.worldmodel->normalmins, sv.worldmodel->normalmaxs);
325 }
326
327
328 /*
329 ===============
330 SV_UnlinkEdict
331
332 ===============
333 */
334 void SV_UnlinkEdict (edict_t *ent)
335 {
336         if (!ent->area.prev)
337                 return;         // not linked in anywhere
338         RemoveLink (&ent->area);
339         ent->area.prev = ent->area.next = NULL;
340 }
341
342
343 /*
344 ====================
345 SV_TouchLinks
346 ====================
347 */
348 void SV_TouchLinks ( edict_t *ent, areanode_t *node )
349 {
350         link_t          *l, *next;
351         edict_t         *touch;
352         int                     old_self, old_other;
353
354 loc0:
355 // touch linked edicts
356         for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = next)
357         {
358                 next = l->next;
359                 touch = EDICT_FROM_AREA(l);
360                 if (touch == ent)
361                         continue;
362                 if (!touch->v.touch || touch->v.solid != SOLID_TRIGGER)
363                         continue;
364                 if (ent->v.absmin[0] > touch->v.absmax[0]
365                  || ent->v.absmin[1] > touch->v.absmax[1]
366                  || ent->v.absmin[2] > touch->v.absmax[2]
367                  || ent->v.absmax[0] < touch->v.absmin[0]
368                  || ent->v.absmax[1] < touch->v.absmin[1]
369                  || ent->v.absmax[2] < touch->v.absmin[2])
370                         continue;
371                 old_self = pr_global_struct->self;
372                 old_other = pr_global_struct->other;
373
374                 pr_global_struct->self = EDICT_TO_PROG(touch);
375                 pr_global_struct->other = EDICT_TO_PROG(ent);
376                 pr_global_struct->time = sv.time;
377                 PR_ExecuteProgram (touch->v.touch, "");
378
379                 pr_global_struct->self = old_self;
380                 pr_global_struct->other = old_other;
381         }
382
383 // recurse down both sides
384         if (node->axis == -1)
385                 return;
386
387         // LordHavoc: optimized recursion
388 //      if (ent->v.absmax[node->axis] > node->dist) SV_TouchLinks (ent, node->children[0]);
389 //      if (ent->v.absmin[node->axis] < node->dist) SV_TouchLinks (ent, node->children[1]);
390         if (ent->v.absmax[node->axis] > node->dist)
391         {
392                 if (ent->v.absmin[node->axis] < node->dist)
393                         SV_TouchLinks(ent, node->children[1]); // order reversed to reduce code
394                 node = node->children[0];
395                 goto loc0;
396         }
397         else
398         {
399                 if (ent->v.absmin[node->axis] < node->dist)
400                 {
401                         node = node->children[1];
402                         goto loc0;
403                 }
404         }
405 }
406
407
408 /*
409 ===============
410 SV_LinkEdict
411
412 ===============
413 */
414 void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
415 {
416         areanode_t      *node;
417
418         if (ent->area.prev)
419                 SV_UnlinkEdict (ent);   // unlink from old position
420
421         if (ent == sv.edicts)
422                 return;         // don't add the world
423
424         if (ent->free)
425                 return;
426
427 // set the abs box
428
429 // LordHavoc: enabling rotating bmodels
430         if (ent->v.solid == SOLID_BSP && (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]))
431         {
432                 // expand for rotation
433                 float           max, v;
434                 int                     i;
435
436                 max = DotProduct(ent->v.mins, ent->v.mins);
437                 v = DotProduct(ent->v.maxs, ent->v.maxs);
438                 if (max < v)
439                         max = v;
440                 max = sqrt(max);
441                 /*
442                 max = 0;
443                 for (i=0 ; i<3 ; i++)
444                 {
445                         v = fabs(ent->v.mins[i]);
446                         if (max < v)
447                                 max = v;
448                         v = fabs(ent->v.maxs[i]);
449                         if (max < v)
450                                 max = v;
451                 }
452                 */
453                 for (i=0 ; i<3 ; i++)
454                 {
455                         ent->v.absmin[i] = ent->v.origin[i] - max;
456                         ent->v.absmax[i] = ent->v.origin[i] + max;
457                 }
458         }
459         else
460         {
461                 VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);
462                 VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
463         }
464
465 //
466 // to make items easier to pick up and allow them to be grabbed off
467 // of shelves, the abs sizes are expanded
468 //
469         if ((int)ent->v.flags & FL_ITEM)
470         {
471                 ent->v.absmin[0] -= 15;
472                 ent->v.absmin[1] -= 15;
473                 ent->v.absmax[0] += 15;
474                 ent->v.absmax[1] += 15;
475         }
476         else
477         {
478                 // because movement is clipped an epsilon away from an actual edge,
479                 // we must fully check even when bounding boxes don't quite touch
480                 ent->v.absmin[0] -= 1;
481                 ent->v.absmin[1] -= 1;
482                 ent->v.absmin[2] -= 1;
483                 ent->v.absmax[0] += 1;
484                 ent->v.absmax[1] += 1;
485                 ent->v.absmax[2] += 1;
486         }
487
488         if (ent->v.solid == SOLID_NOT)
489                 return;
490
491 // find the first node that the ent's box crosses
492         node = sv_areanodes;
493         while (1)
494         {
495                 if (node->axis == -1)
496                         break;
497                 if (ent->v.absmin[node->axis] > node->dist)
498                         node = node->children[0];
499                 else if (ent->v.absmax[node->axis] < node->dist)
500                         node = node->children[1];
501                 else
502                         break;          // crosses the node
503         }
504
505 // link it in
506
507         if (ent->v.solid == SOLID_TRIGGER)
508                 InsertLinkBefore (&ent->area, &node->trigger_edicts);
509         else
510                 InsertLinkBefore (&ent->area, &node->solid_edicts);
511
512 // if touch_triggers, touch all entities at this node and descend for more
513         if (touch_triggers)
514                 SV_TouchLinks ( ent, sv_areanodes );
515 }
516
517
518
519 /*
520 ===============================================================================
521
522 POINT TESTING IN HULLS
523
524 ===============================================================================
525 */
526
527 /*
528 ==================
529 SV_HullPointContents
530
531 ==================
532 */
533 int SV_HullPointContents (hull_t *hull, int num, vec3_t p)
534 {
535         while (num >= 0)
536                 num = hull->clipnodes[num].children[(hull->planes[hull->clipnodes[num].planenum].type < 3 ? p[hull->planes[hull->clipnodes[num].planenum].type] : DotProduct (hull->planes[hull->clipnodes[num].planenum].normal, p)) < hull->planes[hull->clipnodes[num].planenum].dist];
537
538         return num;
539 }
540
541 /*
542 ============
543 SV_TestEntityPosition
544
545 This could be a lot more efficient...
546 ============
547 */
548 edict_t *SV_TestEntityPosition (edict_t *ent)
549 {
550         trace_t trace;
551
552         trace = SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, MOVE_NORMAL, ent);
553
554         if (trace.startsolid)
555                 return sv.edicts;
556
557         return NULL;
558 }
559
560
561 /*
562 ===============================================================================
563
564 LINE TESTING IN HULLS
565
566 ===============================================================================
567 */
568
569 // 1/32 epsilon to keep floating point happy
570 #define DIST_EPSILON (0.03125)
571
572 #define HULLCHECKSTATE_EMPTY 0
573 #define HULLCHECKSTATE_SOLID 1
574 #define HULLCHECKSTATE_DONE 2
575
576 // LordHavoc: FIXME: this is not thread safe, if threading matters here, pass
577 // this as a struct to RecursiveHullCheck, RecursiveHullCheck_Impact, etc...
578 RecursiveHullCheckTraceInfo_t RecursiveHullCheckInfo;
579 #define RHC RecursiveHullCheckInfo
580
581 void SV_RecursiveHullCheck_Impact (mplane_t *plane, int side)
582 {
583         // LordHavoc: using doubles for extra accuracy
584         double t1, t2, frac;
585
586         // LordHavoc: now that we have found the impact, recalculate the impact
587         // point from scratch for maximum accuracy, with an epsilon bias on the
588         // surface distance
589         frac = plane->dist;
590         if (side)
591         {
592                 frac -= DIST_EPSILON;
593                 VectorNegate (plane->normal, RHC.trace->plane.normal);
594                 RHC.trace->plane.dist = -plane->dist;
595         }
596         else
597         {
598                 frac += DIST_EPSILON;
599                 VectorCopy (plane->normal, RHC.trace->plane.normal);
600                 RHC.trace->plane.dist = plane->dist;
601         }
602
603         if (plane->type < 3)
604         {
605                 t1 = RHC.start[plane->type] - frac;
606                 t2 = RHC.start[plane->type] + RHC.dist[plane->type] - frac;
607         }
608         else
609         {
610                 t1 = plane->normal[0] * RHC.start[0] + plane->normal[1] * RHC.start[1] + plane->normal[2] * RHC.start[2] - frac;
611                 t2 = plane->normal[0] * (RHC.start[0] + RHC.dist[0]) + plane->normal[1] * (RHC.start[1] + RHC.dist[1]) + plane->normal[2] * (RHC.start[2] + RHC.dist[2]) - frac;
612         }
613
614         frac = t1 / (t1 - t2);
615         frac = bound(0.0f, frac, 1.0);
616
617         RHC.trace->fraction = frac;
618         RHC.trace->endpos[0] = RHC.start[0] + frac * RHC.dist[0];
619         RHC.trace->endpos[1] = RHC.start[1] + frac * RHC.dist[1];
620         RHC.trace->endpos[2] = RHC.start[2] + frac * RHC.dist[2];
621 }
622
623 int SV_RecursiveHullCheck (int num, double p1f, double p2f, double p1[3], double p2[3])
624 {
625         dclipnode_t     *node;
626         int                     side;
627         double          midf, mid[3];
628         // LordHavoc: FIXME: this is not thread safe...  if threading matters here,
629         // remove the static prefixes
630         static int ret;
631         static mplane_t *plane;
632         static double t1, t2, frac;
633
634         // LordHavoc: a goto!  everyone flee in terror... :)
635 loc0:
636         // check for empty
637         if (num < 0)
638         {
639                 RHC.trace->endcontents = num;
640                 if (RHC.trace->startcontents)
641                 {
642                         if (num == RHC.trace->startcontents)
643                                 RHC.trace->allsolid = false;
644                         else
645                         {
646                                 // if the first leaf is solid, set startsolid
647                                 if (RHC.trace->allsolid)
648                                         RHC.trace->startsolid = true;
649                                 return HULLCHECKSTATE_SOLID;
650                         }
651                         return HULLCHECKSTATE_EMPTY;
652                 }
653                 else
654                 {
655                         if (num != CONTENTS_SOLID)
656                         {
657                                 RHC.trace->allsolid = false;
658                                 if (num == CONTENTS_EMPTY)
659                                         RHC.trace->inopen = true;
660                                 else
661                                         RHC.trace->inwater = true;
662                         }
663                         else
664                         {
665                                 // if the first leaf is solid, set startsolid
666                                 if (RHC.trace->allsolid)
667                                         RHC.trace->startsolid = true;
668                                 return HULLCHECKSTATE_SOLID;
669                         }
670                         return HULLCHECKSTATE_EMPTY;
671                 }
672         }
673
674         // find the point distances
675         node = RHC.hull->clipnodes + num;
676
677         plane = RHC.hull->planes + node->planenum;
678         if (plane->type < 3)
679         {
680                 t1 = p1[plane->type] - plane->dist;
681                 t2 = p2[plane->type] - plane->dist;
682         }
683         else
684         {
685                 t1 = DotProduct (plane->normal, p1) - plane->dist;
686                 t2 = DotProduct (plane->normal, p2) - plane->dist;
687         }
688
689         // LordHavoc: rearranged the side/frac code
690         if (t1 >= 0)
691         {
692                 if (t2 >= 0)
693                 {
694                         num = node->children[0];
695                         goto loc0;
696                 }
697                 // put the crosspoint DIST_EPSILON pixels on the near side
698                 side = 0;
699         }
700         else
701         {
702                 if (t2 < 0)
703                 {
704                         num = node->children[1];
705                         goto loc0;
706                 }
707                 // put the crosspoint DIST_EPSILON pixels on the near side
708                 side = 1;
709         }
710
711         frac = t1 / (t1 - t2);
712         frac = bound(0.0f, frac, 1.0);
713
714         midf = p1f + ((p2f - p1f) * frac);
715         mid[0] = RHC.start[0] + midf * RHC.dist[0];
716         mid[1] = RHC.start[1] + midf * RHC.dist[1];
717         mid[2] = RHC.start[2] + midf * RHC.dist[2];
718
719         // front side first
720         ret = SV_RecursiveHullCheck (node->children[side], p1f, midf, p1, mid);
721         if (ret != HULLCHECKSTATE_EMPTY)
722                 return ret; // solid or done
723         ret = SV_RecursiveHullCheck (node->children[!side], midf, p2f, mid, p2);
724         if (ret != HULLCHECKSTATE_SOLID)
725                 return ret; // empty or done
726
727         // front is air and back is solid, this is the impact point...
728         SV_RecursiveHullCheck_Impact(RHC.hull->planes + node->planenum, side);
729
730         return HULLCHECKSTATE_DONE;
731 }
732
733 /*
734 ==================
735 SV_ClipMoveToEntity
736
737 Handles selection or creation of a clipping hull, and offseting (and
738 eventually rotation) of the end points
739 ==================
740 */
741 trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
742 {
743         trace_t trace;
744         vec3_t offset, forward, left, up;
745         double startd[3], endd[3], tempd[3];
746         hull_t *hull;
747
748 // fill in a default trace
749         memset (&trace, 0, sizeof(trace_t));
750         trace.fraction = 1;
751         trace.allsolid = true;
752
753 // get the clipping hull
754         hull = SV_HullForEntity (ent, mins, maxs, offset);
755
756         VectorSubtract(start, offset, startd);
757         VectorSubtract(end, offset, endd);
758
759         // rotate start and end into the models frame of reference
760         if (ent->v.solid == SOLID_BSP && (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]))
761         {
762                 AngleVectorsFLU (ent->v.angles, forward, left, up);
763                 VectorCopy(startd, tempd);
764                 startd[0] = DotProduct (tempd, forward);
765                 startd[1] = DotProduct (tempd, left);
766                 startd[2] = DotProduct (tempd, up);
767                 VectorCopy(endd, tempd);
768                 endd[0] = DotProduct (tempd, forward);
769                 endd[1] = DotProduct (tempd, left);
770                 endd[2] = DotProduct (tempd, up);
771         }
772
773         VectorCopy(end, trace.endpos);
774
775 // trace a line through the appropriate clipping hull
776         VectorCopy(startd, RecursiveHullCheckInfo.start);
777         VectorSubtract(endd, startd, RecursiveHullCheckInfo.dist);
778         RecursiveHullCheckInfo.hull = hull;
779         RecursiveHullCheckInfo.trace = &trace;
780         SV_RecursiveHullCheck (hull->firstclipnode, 0, 1, startd, endd);
781
782         // if we hit, unrotate endpos and normal, and store the entity we hit
783         if (trace.fraction != 1)
784         {
785                 // rotate endpos back to world frame of reference
786                 if (ent->v.solid == SOLID_BSP && (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]))
787                 {
788                         VectorNegate (ent->v.angles, offset);
789                         AngleVectorsFLU (offset, forward, left, up);
790
791                         VectorCopy (trace.endpos, tempd);
792                         trace.endpos[0] = DotProduct (tempd, forward);
793                         trace.endpos[1] = DotProduct (tempd, left);
794                         trace.endpos[2] = DotProduct (tempd, up);
795
796                         VectorCopy (trace.plane.normal, tempd);
797                         trace.plane.normal[0] = DotProduct (tempd, forward);
798                         trace.plane.normal[1] = DotProduct (tempd, left);
799                         trace.plane.normal[2] = DotProduct (tempd, up);
800                 }
801                 // fix offset
802                 VectorAdd (trace.endpos, offset, trace.endpos);
803                 trace.ent = ent;
804         }
805         else if (trace.allsolid || trace.startsolid)
806                 trace.ent = ent;
807
808         return trace;
809 }
810
811 //===========================================================================
812
813 /*
814 ====================
815 SV_ClipToLinks
816
817 Mins and maxs enclose the entire area swept by the move
818 ====================
819 */
820 void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
821 {
822         link_t          *l, *next;
823         edict_t         *touch;
824         trace_t         trace;
825
826 loc0:
827         if (clip->trace.allsolid)
828                 return;
829 // touch linked edicts
830         for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
831         {
832                 next = l->next;
833                 touch = EDICT_FROM_AREA(l);
834                 if (touch->v.solid == SOLID_NOT)
835                         continue;
836                 if (touch == clip->passedict)
837                         continue;
838                 if (touch->v.solid == SOLID_TRIGGER)
839                         Host_Error ("Trigger in clipping list");
840
841                 if (clip->type == MOVE_NOMONSTERS && touch->v.solid != SOLID_BSP)
842                         continue;
843
844                 if (clip->boxmins[0] > touch->v.absmax[0]
845                  || clip->boxmaxs[0] < touch->v.absmin[0]
846                  || clip->boxmins[1] > touch->v.absmax[1]
847                  || clip->boxmaxs[1] < touch->v.absmin[1]
848                  || clip->boxmins[2] > touch->v.absmax[2]
849                  || clip->boxmaxs[2] < touch->v.absmin[2])
850                         continue;
851
852                 if (clip->passedict)
853                 {
854                         if (clip->passedict->v.size[0] && !touch->v.size[0])
855                                 continue;       // points never interact
856                         if (PROG_TO_EDICT(touch->v.owner) == clip->passedict)
857                                 continue;       // don't clip against own missiles
858                         if (PROG_TO_EDICT(clip->passedict->v.owner) == touch)
859                                 continue;       // don't clip against owner
860                         // LordHavoc: corpse code
861                         if (clip->passedict->v.solid == SOLID_CORPSE && (touch->v.solid == SOLID_SLIDEBOX || touch->v.solid == SOLID_CORPSE))
862                                 continue;
863                         if (clip->passedict->v.solid == SOLID_SLIDEBOX && touch->v.solid == SOLID_CORPSE)
864                                 continue;
865                 }
866
867                 // might interact, so do an exact clip
868                 if ((int)touch->v.flags & FL_MONSTER)
869                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
870                 else
871                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
872                 // LordHavoc: take the 'best' answers from the new trace and combine with existing data
873                 if (trace.allsolid)
874                         clip->trace.allsolid = true;
875                 if (trace.startsolid)
876                 {
877                         clip->trace.startsolid = true;
878                         if (!clip->trace.ent)
879                                 clip->trace.ent = trace.ent;
880                 }
881                 if (trace.inopen)
882                         clip->trace.inopen = true;
883                 if (trace.inwater)
884                         clip->trace.inwater = true;
885                 if (trace.fraction < clip->trace.fraction)
886                 {
887                         clip->trace.fraction = trace.fraction;
888                         VectorCopy(trace.endpos, clip->trace.endpos);
889                         clip->trace.plane = trace.plane;
890                         clip->trace.endcontents = trace.endcontents;
891                         clip->trace.ent = trace.ent;
892                 }
893                 /*
894                 if (trace.allsolid)
895                 {
896                         clip->trace = trace;
897                         return;
898                 }
899                 if (trace.startsolid || trace.fraction < clip->trace.fraction)
900                 {
901                         if (clip->trace.startsolid)
902                         {
903                                 clip->trace = trace;
904                                 clip->trace.startsolid = true;
905                         }
906                         else
907                                 clip->trace = trace;
908                 }
909                 */
910         }
911
912 // recurse down both sides
913         if (node->axis == -1)
914                 return;
915
916         // LordHavoc: optimized recursion
917 //      if (clip->boxmaxs[node->axis] > node->dist) SV_ClipToLinks(node->children[0], clip);
918 //      if (clip->boxmins[node->axis] < node->dist) SV_ClipToLinks(node->children[1], clip);
919         if (clip->boxmaxs[node->axis] > node->dist)
920         {
921                 if (clip->boxmins[node->axis] < node->dist)
922                         SV_ClipToLinks(node->children[1], clip);
923                 node = node->children[0];
924                 goto loc0;
925         }
926         else if (clip->boxmins[node->axis] < node->dist)
927         {
928                 node = node->children[1];
929                 goto loc0;
930         }
931 }
932
933
934 /*
935 ==================
936 SV_MoveBounds
937 ==================
938 */
939 void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
940 {
941 #if 0
942 // debug to test against everything
943 boxmins[0] = boxmins[1] = boxmins[2] = -9999;
944 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] = 9999;
945 #else
946         int             i;
947
948         for (i=0 ; i<3 ; i++)
949         {
950                 if (end[i] > start[i])
951                 {
952                         boxmins[i] = start[i] + mins[i] - 1;
953                         boxmaxs[i] = end[i] + maxs[i] + 1;
954                 }
955                 else
956                 {
957                         boxmins[i] = end[i] + mins[i] - 1;
958                         boxmaxs[i] = start[i] + maxs[i] + 1;
959                 }
960         }
961 #endif
962 }
963
964 /*
965 ==================
966 SV_Move
967 ==================
968 */
969 trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
970 {
971         moveclip_t      clip;
972         int                     i;
973
974         memset ( &clip, 0, sizeof ( moveclip_t ) );
975
976         clip.start = start;
977         clip.end = end;
978         clip.mins = mins;
979         clip.maxs = maxs;
980         clip.type = type;
981         clip.passedict = passedict;
982
983         if (type == MOVE_MISSILE)
984         {
985                 for (i=0 ; i<3 ; i++)
986                 {
987                         clip.mins2[i] = -15;
988                         clip.maxs2[i] = 15;
989                 }
990         }
991         else
992         {
993                 VectorCopy (clip.mins, clip.mins2);
994                 VectorCopy (clip.maxs, clip.maxs2);
995         }
996
997         // clip to world
998         clip.trace = SV_ClipMoveToEntity (sv.edicts, start, mins, maxs, end);
999
1000         // clip to entities
1001         //if (!clip.trace.allsolid)
1002         {
1003                 // create the bounding box of the entire move
1004                 SV_MoveBounds ( start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs );
1005
1006                 SV_ClipToLinks ( sv_areanodes, &clip );
1007         }
1008
1009         return clip.trace;
1010 }