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