home *** CD-ROM | disk | FTP | other *** search
/ Enigma Amiga Life 113 / EnigmaAmiga113CD.iso / software / sviluppo / glquake_src / world.c < prev    next >
C/C++ Source or Header  |  1999-12-28  |  22KB  |  963 lines
  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 =fabs( ent->v.mins[i]);
  398.       if (v > max)
  399.         max = v;
  400.       v =fabs( 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.  
  963.