build number 101
[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
34 {
35         vec3_t          boxmins, boxmaxs;// enclose the test object along entire move
36         float           *mins, *maxs;   // size of the moving object
37         vec3_t          mins2, maxs2;   // size when clipping against mosnters
38         float           *start, *end;
39         trace_t         trace;
40         int                     type;
41         edict_t         *passedict;
42 } moveclip_t;
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
58 /*
59 ===================
60 SV_InitBoxHull
61
62 Set up the planes and clipnodes so that the six floats of a bounding box
63 can just be stored out and get a proper hull_t structure.
64 ===================
65 */
66 void SV_InitBoxHull (void)
67 {
68         int             i;
69         int             side;
70
71         box_hull.clipnodes = box_clipnodes;
72         box_hull.planes = box_planes;
73         box_hull.firstclipnode = 0;
74         box_hull.lastclipnode = 5;
75
76         for (i=0 ; i<6 ; i++)
77         {
78                 box_clipnodes[i].planenum = i;
79                 
80                 side = i&1;
81                 
82                 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
83                 if (i != 5)
84                         box_clipnodes[i].children[side^1] = i + 1;
85                 else
86                         box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
87                 
88                 box_planes[i].type = i>>1;
89                 box_planes[i].normal[i>>1] = 1;
90         }
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 */
103 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 ================
119 SV_HullForEntity
120
121 Returns a hull that can be used for testing or clipping an object of mins/maxs
122 size.
123 Offset is filled in to contain the adjustment that must be added to the
124 testing object's origin to get a point to use with the returned hull.
125 ================
126 */
127 hull_t *SV_HullForEntity (edict_t *ent, vec3_t mins, vec3_t maxs, vec3_t offset)
128 {
129         model_t         *model;
130         vec3_t          size;
131         vec3_t          hullmins, hullmaxs;
132         hull_t          *hull;
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                         Host_Error ("SOLID_BSP without MOVETYPE_PUSH");
139
140                 model = sv.models[ (int)ent->v.modelindex ];
141
142                 // LordHavoc: fixed SOLID_BSP error message
143                 if (!model || model->type != mod_brush)
144                 {
145                         Con_Printf ("SOLID_BSP with a non bsp model, entity dump:\n");
146                         ED_Print (ent);
147                         Host_Error ("SOLID_BSP with a non bsp model\n");
148                 }
149
150                 VectorSubtract (maxs, mins, size);
151                 // LordHavoc: FIXME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
152                 if (hlbsp)
153                 {
154                         if (size[0] < 3)
155                                 hull = &model->hulls[0]; // 0x0x0
156                         else if (size[0] <= 32)
157                         {
158                                 if (size[2] < 54) // pick the nearest of 36 or 72
159                                         hull = &model->hulls[3]; // 32x32x36
160                                 else
161                                         hull = &model->hulls[1]; // 32x32x72
162                         }
163                         else
164                                 hull = &model->hulls[2]; // 64x64x64
165                 }
166                 else
167                 {
168                         if (size[0] < 3)
169                                 hull = &model->hulls[0]; // 0x0x0
170                         else if (size[0] <= 32)
171                                 hull = &model->hulls[1]; // 32x32x56
172                         else
173                                 hull = &model->hulls[2]; // 64x64x88
174                 }
175
176 // calculate an offset value to center the origin
177                 VectorSubtract (hull->clip_mins, mins, offset);
178                 VectorAdd (offset, ent->v.origin, offset);
179         }
180         else
181         {       // create a temp hull from bounding box sizes
182
183                 VectorSubtract (ent->v.mins, maxs, hullmins);
184                 VectorSubtract (ent->v.maxs, mins, hullmaxs);
185                 hull = SV_HullForBox (hullmins, hullmaxs);
186                 
187                 VectorCopy (ent->v.origin, offset);
188         }
189
190
191         return hull;
192 }
193
194 /*
195 ===============================================================================
196
197 ENTITY AREA CHECKING
198
199 ===============================================================================
200 */
201
202 typedef struct areanode_s
203 {
204         int             axis;           // -1 = leaf node
205         float   dist;
206         struct areanode_s       *children[2];
207         link_t  trigger_edicts;
208         link_t  solid_edicts;
209 } areanode_t;
210
211 #define AREA_DEPTH      4
212 #define AREA_NODES      32
213
214 static  areanode_t      sv_areanodes[AREA_NODES];
215 static  int                     sv_numareanodes;
216
217 /*
218 ===============
219 SV_CreateAreaNode
220
221 ===============
222 */
223 areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
224 {
225         areanode_t      *anode;
226         vec3_t          size;
227         vec3_t          mins1, maxs1, mins2, maxs2;
228
229         anode = &sv_areanodes[sv_numareanodes];
230         sv_numareanodes++;
231
232         ClearLink (&anode->trigger_edicts);
233         ClearLink (&anode->solid_edicts);
234         
235         if (depth == AREA_DEPTH)
236         {
237                 anode->axis = -1;
238                 anode->children[0] = anode->children[1] = NULL;
239                 return anode;
240         }
241         
242         VectorSubtract (maxs, mins, size);
243         if (size[0] > size[1])
244                 anode->axis = 0;
245         else
246                 anode->axis = 1;
247         
248         anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
249         VectorCopy (mins, mins1);       
250         VectorCopy (mins, mins2);       
251         VectorCopy (maxs, maxs1);       
252         VectorCopy (maxs, maxs2);       
253         
254         maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
255         
256         anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
257         anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
258
259         return anode;
260 }
261
262 /*
263 ===============
264 SV_ClearWorld
265
266 ===============
267 */
268 void SV_ClearWorld (void)
269 {
270         SV_InitBoxHull ();
271         
272         memset (sv_areanodes, 0, sizeof(sv_areanodes));
273         sv_numareanodes = 0;
274         SV_CreateAreaNode (0, sv.worldmodel->mins, sv.worldmodel->maxs);
275 }
276
277
278 /*
279 ===============
280 SV_UnlinkEdict
281
282 ===============
283 */
284 void SV_UnlinkEdict (edict_t *ent)
285 {
286         if (!ent->area.prev)
287                 return;         // not linked in anywhere
288         RemoveLink (&ent->area);
289         ent->area.prev = ent->area.next = NULL;
290 }
291
292
293 /*
294 ====================
295 SV_TouchLinks
296 ====================
297 */
298 void SV_TouchLinks ( edict_t *ent, areanode_t *node )
299 {
300         link_t          *l, *next;
301         edict_t         *touch;
302         int                     old_self, old_other;
303
304 loc0:
305 // touch linked edicts
306         for (l = node->trigger_edicts.next ; l != &node->trigger_edicts ; l = next)
307         {
308                 next = l->next;
309                 touch = EDICT_FROM_AREA(l);
310                 if (touch == ent)
311                         continue;
312                 if (!touch->v.touch || touch->v.solid != SOLID_TRIGGER)
313                         continue;
314                 if (ent->v.absmin[0] > touch->v.absmax[0]
315                 || ent->v.absmin[1] > touch->v.absmax[1]
316                 || ent->v.absmin[2] > touch->v.absmax[2]
317                 || ent->v.absmax[0] < touch->v.absmin[0]
318                 || ent->v.absmax[1] < touch->v.absmin[1]
319                 || ent->v.absmax[2] < touch->v.absmin[2] )
320                         continue;
321                 old_self = pr_global_struct->self;
322                 old_other = pr_global_struct->other;
323
324                 pr_global_struct->self = EDICT_TO_PROG(touch);
325                 pr_global_struct->other = EDICT_TO_PROG(ent);
326                 pr_global_struct->time = sv.time;
327                 PR_ExecuteProgram (touch->v.touch, "");
328
329                 pr_global_struct->self = old_self;
330                 pr_global_struct->other = old_other;
331         }
332         
333 // recurse down both sides
334         if (node->axis == -1)
335                 return;
336         
337         // LordHavoc: optimized recursion
338 //      if (ent->v.absmax[node->axis] > node->dist) SV_TouchLinks (ent, node->children[0]);
339 //      if (ent->v.absmin[node->axis] < node->dist) SV_TouchLinks (ent, node->children[1]);
340         if (ent->v.absmax[node->axis] > node->dist)
341         {
342                 if (ent->v.absmin[node->axis] < node->dist)
343                         SV_TouchLinks(ent, node->children[1]); // order reversed to reduce code
344                 node = node->children[0];
345                 goto loc0;
346         }
347         else
348         {
349                 if (ent->v.absmin[node->axis] < node->dist)
350                 {
351                         node = node->children[1];
352                         goto loc0;
353                 }
354         }
355 }
356
357
358 /*
359 ===============
360 SV_FindTouchedLeafs
361
362 ===============
363 */
364 void SV_FindTouchedLeafs (edict_t *ent, mnode_t *node)
365 {
366         mplane_t        *splitplane;
367         mleaf_t         *leaf;
368         int                     sides;
369         int                     leafnum;
370
371 loc0:
372         if (node->contents == CONTENTS_SOLID)
373                 return;
374         
375 // add an efrag if the node is a leaf
376
377         if ( node->contents < 0)
378         {
379                 if (ent->num_leafs == MAX_ENT_LEAFS)
380                 {
381                         Con_DPrintf("FindTouchedLeafs overflow\n");
382                         return;
383                 }
384
385                 leaf = (mleaf_t *)node;
386                 leafnum = leaf - sv.worldmodel->leafs - 1;
387
388                 ent->leafnums[ent->num_leafs] = leafnum;
389                 ent->num_leafs++;                       
390                 return;
391         }
392         
393 // NODE_MIXED
394
395         splitplane = node->plane;
396         sides = BOX_ON_PLANE_SIDE(ent->v.absmin, ent->v.absmax, splitplane);
397         
398 // recurse down the contacted sides
399         // LordHavoc: optimized recursion
400 //      if (sides & 1) SV_FindTouchedLeafs (ent, node->children[0]);
401 //      if (sides & 2) SV_FindTouchedLeafs (ent, node->children[1]);
402         switch (sides)
403         {
404         case 1:
405                 node = node->children[0];
406                 goto loc0;
407         case 2:
408                 node = node->children[1];
409                 goto loc0;
410         default: // 3
411                 if (node->children[0]->contents != CONTENTS_SOLID)
412                         SV_FindTouchedLeafs (ent, node->children[0]);
413                 node = node->children[1];
414                 goto loc0;
415         }
416 }
417
418 /*
419 ===============
420 SV_LinkEdict
421
422 ===============
423 */
424 void SV_LinkEdict (edict_t *ent, qboolean touch_triggers)
425 {
426         areanode_t      *node;
427
428         if (ent->area.prev)
429                 SV_UnlinkEdict (ent);   // unlink from old position
430                 
431         if (ent == sv.edicts)
432                 return;         // don't add the world
433
434         if (ent->free)
435                 return;
436
437 // set the abs box
438
439 // LordHavoc: enabling rotating bmodels
440         if (ent->v.solid == SOLID_BSP && (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]))
441         {       // expand for rotation
442                 float           max, v;
443                 int                     i;
444
445                 max = DotProduct(ent->v.mins, ent->v.mins);
446                 v = DotProduct(ent->v.maxs, ent->v.maxs);
447                 if (max < v)
448                         max = v;
449                 max = sqrt(max);
450                 /*
451                 max = 0;
452                 for (i=0 ; i<3 ; i++)
453                 {
454                         v = fabs(ent->v.mins[i]);
455                         if (max < v)
456                                 max = v;
457                         v = fabs(ent->v.maxs[i]);
458                         if (max < v)
459                                 max = v;
460                 }
461                 */
462                 for (i=0 ; i<3 ; i++)
463                 {
464                         ent->v.absmin[i] = ent->v.origin[i] - max;
465                         ent->v.absmax[i] = ent->v.origin[i] + max;
466                 }
467         }
468         else
469         {
470                 VectorAdd (ent->v.origin, ent->v.mins, ent->v.absmin);  
471                 VectorAdd (ent->v.origin, ent->v.maxs, ent->v.absmax);
472         }
473
474 //
475 // to make items easier to pick up and allow them to be grabbed off
476 // of shelves, the abs sizes are expanded
477 //
478         if ((int)ent->v.flags & FL_ITEM)
479         {
480                 ent->v.absmin[0] -= 15;
481                 ent->v.absmin[1] -= 15;
482                 ent->v.absmax[0] += 15;
483                 ent->v.absmax[1] += 15;
484         }
485         else
486         {       // because movement is clipped an epsilon away from an actual edge,
487                 // we must fully check even when bounding boxes don't quite touch
488                 ent->v.absmin[0] -= 1;
489                 ent->v.absmin[1] -= 1;
490                 ent->v.absmin[2] -= 1;
491                 ent->v.absmax[0] += 1;
492                 ent->v.absmax[1] += 1;
493                 ent->v.absmax[2] += 1;
494         }
495
496 // link to PVS leafs
497         ent->num_leafs = 0;
498         if (ent->v.modelindex)
499                 SV_FindTouchedLeafs (ent, sv.worldmodel->nodes);
500
501         if (ent->v.solid == SOLID_NOT)
502                 return;
503
504 // find the first node that the ent's box crosses
505         node = sv_areanodes;
506         while (1)
507         {
508                 if (node->axis == -1)
509                         break;
510                 if (ent->v.absmin[node->axis] > node->dist)
511                         node = node->children[0];
512                 else if (ent->v.absmax[node->axis] < node->dist)
513                         node = node->children[1];
514                 else
515                         break;          // crosses the node
516         }
517
518 // link it in   
519
520         if (ent->v.solid == SOLID_TRIGGER)
521                 InsertLinkBefore (&ent->area, &node->trigger_edicts);
522         else
523                 InsertLinkBefore (&ent->area, &node->solid_edicts);
524         
525 // if touch_triggers, touch all entities at this node and descend for more
526         if (touch_triggers)
527                 SV_TouchLinks ( ent, sv_areanodes );
528 }
529
530
531
532 /*
533 ===============================================================================
534
535 POINT TESTING IN HULLS
536
537 ===============================================================================
538 */
539
540 /*
541 ==================
542 SV_HullPointContents
543
544 ==================
545 */
546 int SV_HullPointContents (hull_t *hull, int num, vec3_t p)
547 {
548         while (num >= 0)
549                 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];
550         
551         return num;
552 }
553
554 /*
555 ============
556 SV_TestEntityPosition
557
558 This could be a lot more efficient...
559 ============
560 */
561 edict_t *SV_TestEntityPosition (edict_t *ent)
562 {
563         trace_t trace;
564
565         trace = SV_Move (ent->v.origin, ent->v.mins, ent->v.maxs, ent->v.origin, 0, ent);
566         
567         if (trace.startsolid)
568                 return sv.edicts;
569                 
570         return NULL;
571 }
572
573
574 /*
575 ===============================================================================
576
577 LINE TESTING IN HULLS
578
579 ===============================================================================
580 */
581
582 // 1/32 epsilon to keep floating point happy
583 #define DIST_EPSILON    (0.03125)
584
585 /*
586 ==================
587 SV_RecursiveHullCheck
588
589 ==================
590 */
591 /*
592 qboolean SV_RecursiveHullCheck (hull_t *hull, int num, float p1f, float p2f, vec3_t p1, vec3_t p2, trace_t *trace)
593 {
594         dclipnode_t     *node;
595         mplane_t        *plane;
596         float           t1, t2;
597         float           frac;
598         int                     i;
599         vec3_t          mid;
600         int                     side;
601         float           midf;
602
603 loc0:
604 // check for empty
605         if (num < 0)
606         {
607                 if (num != CONTENTS_SOLID)
608                 {
609                         trace->allsolid = false;
610                         if (num == CONTENTS_EMPTY)
611                                 trace->inopen = true;
612                         else
613                                 trace->inwater = true;
614                 }
615                 else
616                         trace->startsolid = true;
617                 return true;            // empty
618         }
619
620         if (num < hull->firstclipnode || num > hull->lastclipnode)
621                 Sys_Error ("SV_RecursiveHullCheck: bad node number");
622
623 //
624 // find the point distances
625 //
626         node = hull->clipnodes + num;
627         plane = hull->planes + node->planenum;
628
629         t1 = PlaneDiff(p1, plane);
630         t2 = PlaneDiff(p2, plane);
631         
632 #if 1
633         if (t1 >= 0 && t2 >= 0)
634         // LordHavoc: optimized recursion
635 //              return SV_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
636         {
637                 num = node->children[0];
638                 goto loc0;
639         }
640         if (t1 < 0 && t2 < 0)
641 //              return SV_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
642         {
643                 num = node->children[1];
644                 goto loc0;
645         }
646 #else
647         if ( (t1 >= DIST_EPSILON && t2 >= DIST_EPSILON) || (t2 > t1 && t1 >= 0) )
648                 return SV_RecursiveHullCheck (hull, node->children[0], p1f, p2f, p1, p2, trace);
649         if ( (t1 <= -DIST_EPSILON && t2 <= -DIST_EPSILON) || (t2 < t1 && t1 <= 0) )
650                 return SV_RecursiveHullCheck (hull, node->children[1], p1f, p2f, p1, p2, trace);
651 #endif
652
653 // put the crosspoint DIST_EPSILON pixels on the near side
654         if (t1 < 0)
655                 frac = bound(0, (t1 + DIST_EPSILON)/(t1-t2), 1);
656         else
657                 frac = bound(0, (t1 - DIST_EPSILON)/(t1-t2), 1);
658                 
659         midf = p1f + (p2f - p1f)*frac;
660         mid[0] = p1[0] + frac*(p2[0] - p1[0]);
661         mid[1] = p1[1] + frac*(p2[1] - p1[1]);
662         mid[2] = p1[2] + frac*(p2[2] - p1[2]);
663
664         side = (t1 < 0);
665
666 // move up to the node
667         if (!SV_RecursiveHullCheck (hull, node->children[side], p1f, midf, p1, mid, trace) )
668                 return false;
669
670 #ifdef PARANOID
671         if (SV_HullPointContents (hull, node->children[side], mid) == CONTENTS_SOLID)
672         {
673                 Con_Printf ("mid PointInHullSolid\n");
674                 return false;
675         }
676 #endif
677
678         if (SV_HullPointContents (hull, node->children[side^1], mid) != CONTENTS_SOLID)
679 // go past the node
680                 return SV_RecursiveHullCheck (hull, node->children[side^1], midf, p2f, mid, p2, trace);
681         // mid would need to be duplicated during recursion...
682 */
683         /*
684         {
685                 p1f = midf;
686                 p1 = mid;
687                 num = node->children[side^1];
688                 goto loc0;
689         }
690         */
691 /*
692
693         if (trace->allsolid)
694                 return false;           // never got out of the solid area
695         
696 //==================
697 // the other side of the node is solid, this is the impact point
698 //==================
699         if (!side)
700         {
701                 VectorCopy (plane->normal, trace->plane.normal);
702                 trace->plane.dist = plane->dist;
703         }
704         else
705         {
706                 VectorNegate (plane->normal, trace->plane.normal);
707                 trace->plane.dist = -plane->dist;
708         }
709
710         while (SV_HullPointContents (hull, hull->firstclipnode, mid) == CONTENTS_SOLID)
711         { // shouldn't really happen, but does occasionally
712                 frac -= 0.1;
713                 if (frac < 0)
714                 {
715                         trace->fraction = midf;
716                         VectorCopy (mid, trace->endpos);
717                         Con_DPrintf ("backup past 0\n");
718                         return false;
719                 }
720                 midf = p1f + (p2f - p1f)*frac;
721                 for (i=0 ; i<3 ; i++)
722                         mid[i] = p1[i] + frac*(p2[i] - p1[i]);
723         }
724
725         trace->fraction = midf;
726         VectorCopy (mid, trace->endpos);
727
728         return false;
729 }
730 */
731
732 // LordHavoc: backported from my optimizations to PM_RecursiveHullCheck in QuakeForge newtree (QW)
733 qboolean SV_RecursiveHullCheck (hull_t *hull, int num, float p1f, float p2f, vec3_t p1, vec3_t p2, trace_t *trace)
734 {
735         dclipnode_t     *node;
736         mplane_t        *plane;
737         float           t1, t2;
738         float           frac;
739         int                     i;
740         vec3_t          mid;
741         int                     side;
742         float           midf;
743
744         // LordHavoc: a goto!  everyone flee in terror... :)
745 loc0:
746 // check for empty
747         if (num < 0)
748         {
749                 if (num != CONTENTS_SOLID)
750                 {
751                         trace->allsolid = false;
752                         if (num == CONTENTS_EMPTY)
753                                 trace->inopen = true;
754                         else
755                                 trace->inwater = true;
756                 }
757                 else
758                         trace->startsolid = true;
759                 return true;            // empty
760         }
761
762 // find the point distances
763         node = hull->clipnodes + num;
764         plane = hull->planes + node->planenum;
765
766         if (plane->type < 3)
767         {
768                 t1 = p1[plane->type] - plane->dist;
769                 t2 = p2[plane->type] - plane->dist;
770         }
771         else
772         {
773                 t1 = DotProduct (plane->normal, p1) - plane->dist;
774                 t2 = DotProduct (plane->normal, p2) - plane->dist;
775         }
776
777         // LordHavoc: recursion optimization
778         if (t1 >= 0 && t2 >= 0)
779         {
780                 num = node->children[0];
781                 goto loc0;
782         }
783         if (t1 < 0 && t2 < 0)
784         {
785                 num = node->children[1];
786                 goto loc0;
787         }
788
789 // put the crosspoint DIST_EPSILON pixels on the near side
790         side = (t1 < 0);
791         if (side)
792                 frac = bound(0, (t1 + DIST_EPSILON) / (t1 - t2), 1);
793         else
794                 frac = bound(0, (t1 - DIST_EPSILON) / (t1 - t2), 1);
795                 
796         midf = p1f + (p2f - p1f)*frac;
797         for (i=0 ; i<3 ; i++)
798                 mid[i] = p1[i] + frac*(p2[i] - p1[i]);
799
800 // move up to the node
801         if (!SV_RecursiveHullCheck (hull, node->children[side], p1f, midf, p1, mid, trace) )
802                 return false;
803
804 #ifdef PARANOID
805         if (SV_HullPointContents (pm_hullmodel, mid, node->children[side]) == CONTENTS_SOLID)
806         {
807                 Con_Printf ("mid PointInHullSolid\n");
808                 return false;
809         }
810 #endif
811
812         // LordHavoc: warning to the clumsy, this recursion can not be optimized because mid would need to be duplicated on a stack
813         if (SV_HullPointContents (hull, node->children[side^1], mid) != CONTENTS_SOLID)
814 // go past the node
815                 return SV_RecursiveHullCheck (hull, node->children[side^1], midf, p2f, mid, p2, trace);
816         
817         if (trace->allsolid)
818                 return false;           // never got out of the solid area
819                 
820 //==================
821 // the other side of the node is solid, this is the impact point
822 //==================
823         if (!side)
824         {
825                 VectorCopy (plane->normal, trace->plane.normal);
826                 trace->plane.dist = plane->dist;
827         }
828         else
829         {
830                 VectorNegate (plane->normal, trace->plane.normal);
831                 trace->plane.dist = -plane->dist;
832         }
833
834         while (SV_HullPointContents (hull, hull->firstclipnode, mid) == CONTENTS_SOLID)
835         { // shouldn't really happen, but does occasionally
836                 frac -= 0.1;
837                 if (frac < 0)
838                 {
839                         trace->fraction = midf;
840                         VectorCopy (mid, trace->endpos);
841                         Con_DPrintf ("backup past 0\n");
842                         return false;
843                 }
844                 midf = p1f + (p2f - p1f)*frac;
845                 for (i=0 ; i<3 ; i++)
846                         mid[i] = p1[i] + frac*(p2[i] - p1[i]);
847         }
848
849         trace->fraction = midf;
850         VectorCopy (mid, trace->endpos);
851
852         return false;
853 }
854
855 qboolean SV_TestLine (hull_t *hull, int num, vec3_t p1, vec3_t p2)
856 {
857         dclipnode_t     *node;
858         mplane_t        *plane;
859         float           t1, t2, frac;
860         vec3_t          mid;
861         int                     side;
862
863 loc0:
864 // check for empty
865         if (num < 0)
866                 return num != CONTENTS_SOLID;
867
868         if (num < hull->firstclipnode || num > hull->lastclipnode)
869                 Sys_Error ("SV_RecursiveHullCheck: bad node number");
870
871 //
872 // find the point distances
873 //
874         node = hull->clipnodes + num;
875         plane = hull->planes + node->planenum;
876
877         t1 = PlaneDiff(p1, plane);
878         t2 = PlaneDiff(p2, plane);
879         
880         if (t1 >= 0 && t2 >= 0)
881         {
882                 num = node->children[0];
883                 goto loc0;
884         }
885         if (t1 < 0 && t2 < 0)
886         {
887                 num = node->children[1];
888                 goto loc0;
889         }
890
891 // put the crosspoint DIST_EPSILON pixels on the near side
892         side = (t1 < 0);
893
894         if (side)
895                 frac = bound(0, (t1 + DIST_EPSILON)/(t1-t2), 1);
896         else
897                 frac = bound(0, (t1 - DIST_EPSILON)/(t1-t2), 1);
898                 
899         mid[0] = p1[0] + frac*(p2[0] - p1[0]);
900         mid[1] = p1[1] + frac*(p2[1] - p1[1]);
901         mid[2] = p1[2] + frac*(p2[2] - p1[2]);
902
903         if (node->children[side] < 0)
904         {
905                 if (node->children[side] == CONTENTS_SOLID)
906                         return false;
907                 return SV_TestLine(hull, node->children[!side], mid, p2);
908         }
909         else if (SV_TestLine(hull, node->children[side], p1, mid))
910                 return SV_TestLine(hull, node->children[!side], mid, p2);
911         else
912                 return false;
913 }
914
915
916 /*
917 ==================
918 SV_ClipMoveToEntity
919
920 Handles selection or creation of a clipping hull, and offseting (and
921 eventually rotation) of the end points
922 ==================
923 */
924 trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end)
925 {
926         trace_t         trace;
927         vec3_t          offset;
928         vec3_t          start_l, end_l;
929         hull_t          *hull;
930
931 // fill in a default trace
932         memset (&trace, 0, sizeof(trace_t));
933         trace.fraction = 1;
934         trace.allsolid = true;
935         VectorCopy (end, trace.endpos);
936
937 // get the clipping hull
938         hull = SV_HullForEntity (ent, mins, maxs, offset);
939
940         VectorSubtract (start, offset, start_l);
941         VectorSubtract (end, offset, end_l);
942
943 // LordHavoc: enabling rotating bmodels
944         // rotate start and end into the models frame of reference
945         if (ent->v.solid == SOLID_BSP && (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]))
946         {
947                 vec3_t  forward, right, up;
948                 vec3_t  temp;
949
950                 AngleVectors (ent->v.angles, forward, right, up);
951
952                 VectorCopy (start_l, temp);
953                 start_l[0] = DotProduct (temp, forward);
954                 start_l[1] = -DotProduct (temp, right);
955                 start_l[2] = DotProduct (temp, up);
956
957                 VectorCopy (end_l, temp);
958                 end_l[0] = DotProduct (temp, forward);
959                 end_l[1] = -DotProduct (temp, right);
960                 end_l[2] = DotProduct (temp, up);
961         }
962
963 // trace a line through the apropriate clipping hull
964         SV_RecursiveHullCheck (hull, hull->firstclipnode, 0, 1, start_l, end_l, &trace);
965
966 // LordHavoc: enabling rotating bmodels
967         // rotate endpos back to world frame of reference
968         if (ent->v.solid == SOLID_BSP && (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2]))
969         {
970                 vec3_t  a;
971                 vec3_t  forward, right, up;
972                 vec3_t  temp;
973
974                 if (trace.fraction != 1)
975                 {
976                         VectorNegate (ent->v.angles, a);
977                         AngleVectors (a, forward, right, up);
978
979                         VectorCopy (trace.endpos, temp);
980                         trace.endpos[0] = DotProduct (temp, forward);
981                         trace.endpos[1] = -DotProduct (temp, right);
982                         trace.endpos[2] = DotProduct (temp, up);
983
984                         VectorCopy (trace.plane.normal, temp);
985                         trace.plane.normal[0] = DotProduct (temp, forward);
986                         trace.plane.normal[1] = -DotProduct (temp, right);
987                         trace.plane.normal[2] = DotProduct (temp, up);
988                 }
989         }
990
991 // fix trace up by the offset
992         if (trace.fraction != 1)
993                 VectorAdd (trace.endpos, offset, trace.endpos);
994
995 // did we clip the move?
996         if (trace.fraction < 1 || trace.startsolid  )
997                 trace.ent = ent;
998
999         return trace;
1000 }
1001
1002 //===========================================================================
1003
1004 /*
1005 ====================
1006 SV_ClipToLinks
1007
1008 Mins and maxs enclose the entire area swept by the move
1009 ====================
1010 */
1011 void SV_ClipToLinks ( areanode_t *node, moveclip_t *clip )
1012 {
1013         link_t          *l, *next;
1014         edict_t         *touch;
1015         trace_t         trace;
1016
1017 loc0:
1018 // touch linked edicts
1019         for (l = node->solid_edicts.next ; l != &node->solid_edicts ; l = next)
1020         {
1021                 next = l->next;
1022                 touch = EDICT_FROM_AREA(l);
1023                 if (touch->v.solid == SOLID_NOT)
1024                         continue;
1025                 if (touch == clip->passedict)
1026                         continue;
1027                 if (touch->v.solid == SOLID_TRIGGER)
1028                         Sys_Error ("Trigger in clipping list");
1029
1030                 if (clip->type == MOVE_NOMONSTERS && touch->v.solid != SOLID_BSP)
1031                         continue;
1032
1033                 if (clip->boxmins[0] > touch->v.absmax[0]
1034                 || clip->boxmins[1] > touch->v.absmax[1]
1035                 || clip->boxmins[2] > touch->v.absmax[2]
1036                 || clip->boxmaxs[0] < touch->v.absmin[0]
1037                 || clip->boxmaxs[1] < touch->v.absmin[1]
1038                 || clip->boxmaxs[2] < touch->v.absmin[2] )
1039                         continue;
1040
1041                 if (clip->passedict!=0 && clip->passedict->v.size[0] && !touch->v.size[0])
1042                         continue;       // points never interact
1043
1044         // might intersect, so do an exact clip
1045                 if (clip->trace.allsolid)
1046                         return;
1047                 if (clip->passedict)
1048                 {
1049                         if (PROG_TO_EDICT(touch->v.owner) == clip->passedict)
1050                                 continue;       // don't clip against own missiles
1051                         if (PROG_TO_EDICT(clip->passedict->v.owner) == touch)
1052                                 continue;       // don't clip against owner
1053                         // LordHavoc: corpse code
1054                         if (clip->passedict->v.solid == SOLID_CORPSE && touch->v.solid == SOLID_SLIDEBOX)
1055                                 continue;
1056                         if (clip->passedict->v.solid == SOLID_SLIDEBOX && touch->v.solid == SOLID_CORPSE)
1057                                 continue;
1058                 }
1059
1060                 if ((int)touch->v.flags & FL_MONSTER)
1061                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins2, clip->maxs2, clip->end);
1062                 else
1063                         trace = SV_ClipMoveToEntity (touch, clip->start, clip->mins, clip->maxs, clip->end);
1064                 if (trace.allsolid || trace.startsolid || trace.fraction < clip->trace.fraction)
1065                 {
1066                         trace.ent = touch;
1067                         if (clip->trace.startsolid)
1068                         {
1069                                 clip->trace = trace;
1070                                 clip->trace.startsolid = true;
1071                         }
1072                         else
1073                                 clip->trace = trace;
1074                 }
1075                 else if (trace.startsolid)
1076                         clip->trace.startsolid = true;
1077         }
1078         
1079 // recurse down both sides
1080         if (node->axis == -1)
1081                 return;
1082
1083         // LordHavoc: optimized recursion
1084 //      if (clip->boxmaxs[node->axis] > node->dist) SV_ClipToLinks(node->children[0], clip);
1085 //      if (clip->boxmins[node->axis] < node->dist) SV_ClipToLinks(node->children[1], clip);
1086         if (clip->boxmaxs[node->axis] > node->dist)
1087         {
1088                 if (clip->boxmins[node->axis] < node->dist)
1089                         SV_ClipToLinks(node->children[1], clip);
1090                 node = node->children[0];
1091                 goto loc0;
1092         }
1093         else if (clip->boxmins[node->axis] < node->dist)
1094         {
1095                 node = node->children[1];
1096                 goto loc0;
1097         }
1098 }
1099
1100
1101 /*
1102 ==================
1103 SV_MoveBounds
1104 ==================
1105 */
1106 void SV_MoveBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
1107 {
1108 #if 0
1109 // debug to test against everything
1110 boxmins[0] = boxmins[1] = boxmins[2] = -9999;
1111 boxmaxs[0] = boxmaxs[1] = boxmaxs[2] = 9999;
1112 #else
1113         int             i;
1114         
1115         for (i=0 ; i<3 ; i++)
1116         {
1117                 if (end[i] > start[i])
1118                 {
1119                         boxmins[i] = start[i] + mins[i] - 1;
1120                         boxmaxs[i] = end[i] + maxs[i] + 1;
1121                 }
1122                 else
1123                 {
1124                         boxmins[i] = end[i] + mins[i] - 1;
1125                         boxmaxs[i] = start[i] + maxs[i] + 1;
1126                 }
1127         }
1128 #endif
1129 }
1130
1131 /*
1132 ==================
1133 SV_Move
1134 ==================
1135 */
1136 trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict)
1137 {
1138         moveclip_t      clip;
1139         int                     i;
1140
1141         memset ( &clip, 0, sizeof ( moveclip_t ) );
1142
1143 // clip to world
1144         clip.trace = SV_ClipMoveToEntity ( sv.edicts, start, mins, maxs, end );
1145
1146         clip.start = start;
1147         clip.end = end;
1148         clip.mins = mins;
1149         clip.maxs = maxs;
1150         clip.type = type;
1151         clip.passedict = passedict;
1152
1153         if (type == MOVE_MISSILE)
1154         {
1155                 for (i=0 ; i<3 ; i++)
1156                 {
1157                         clip.mins2[i] = -15;
1158                         clip.maxs2[i] = 15;
1159                 }
1160         }
1161         else
1162         {
1163                 VectorCopy (mins, clip.mins2);
1164                 VectorCopy (maxs, clip.maxs2);
1165         }
1166         
1167 // create the bounding box of the entire move
1168         SV_MoveBounds ( start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs );
1169
1170 // clip to entities
1171         SV_ClipToLinks ( sv_areanodes, &clip );
1172
1173         return clip.trace;
1174 }