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