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 }