Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  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.