collision.c

   1
   2 #include "quakedef.h"
   3
   4 typedef struct
   5 {
   6         // the hull we're tracing through
   7         const hull_t *hull;
   8
   9         // the trace structure to fill in
  10         trace_t *trace;
  11
  12         // start and end of the trace (in model space)
  13         double start[3];
  14         double end[3];
  15
  16         // end - start (for quick fraction -> vector conversions)
  17         double dist[3];
  18 }
  19 RecursiveHullCheckTraceInfo_t;
  20
  21 // 1/32 epsilon to keep floating point happy
  22 #define DIST_EPSILON (0.03125)
  23
  24 #define HULLCHECKSTATE_EMPTY 0
  25 #define HULLCHECKSTATE_SOLID 1
  26 #define HULLCHECKSTATE_DONE 2
  27
  28 static void RecursiveHullCheck_Impact (RecursiveHullCheckTraceInfo_t *t, const mplane_t *plane, const int side)
  29 {
  30         // LordHavoc: using doubles for extra accuracy
  31         double t1, t2, frac, pdist;
  32
  33         // LordHavoc: now that we have found the impact, recalculate the impact
  34         // point from scratch for maximum accuracy, with an epsilon bias on the
  35         // surface distance
  36         pdist = plane->dist;
  37         if (side)
  38         {
  39                 pdist -= DIST_EPSILON;
  40                 VectorNegate (plane->normal, t->trace->plane.normal);
  41                 t->trace->plane.dist = -plane->dist;
  42         }
  43         else
  44         {
  45                 pdist += DIST_EPSILON;
  46                 VectorCopy (plane->normal, t->trace->plane.normal);
  47                 t->trace->plane.dist = plane->dist;
  48         }
  49
  50         if (plane->type < 3)
  51         {
  52                 t1 = t->start[plane->type] - pdist;
  53                 t2 = t->start[plane->type] + t->dist[plane->type] - pdist;
  54         }
  55         else
  56         {
  57                 t1 = plane->normal[0] * t->start[0] + plane->normal[1] * t->start[1] + plane->normal[2] * t->start[2] - pdist;
  58                 t2 = plane->normal[0] * (t->start[0] + t->dist[0]) + plane->normal[1] * (t->start[1] + t->dist[1]) + plane->normal[2] * (t->start[2] + t->dist[2]) - pdist;
  59         }
  60
  61         frac = t1 / (t1 - t2);
  62         frac = bound(0.0f, frac, 1.0);
  63
  64         t->trace->fraction = frac;
  65         VectorMA(t->start, frac, t->dist, t->trace->endpos);
  66 }
  67
  68 static int RecursiveHullCheck (RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, const double p1[3], const double p2[3])
  69 {
  70         // status variables, these don't need to be saved on the stack when
  71         // recursing...  but are because this should be thread-safe
  72         // (note: tracing against a bbox is not thread-safe, yet)
  73         int ret;
  74         mplane_t *plane;
  75         double t1, t2, frac;
  76
  77         // variables that need to be stored on the stack when recursing
  78         dclipnode_t     *node;
  79         int                     side;
  80         double          midf, mid[3];
  81
  82         // LordHavoc: a goto!  everyone flee in terror... :)
  83 loc0:
  84         // check for empty
  85         if (num < 0)
  86         {
  87                 t->trace->endcontents = num;
  88                 if (t->trace->startcontents)
  89                 {
  90                         if (num == t->trace->startcontents)
  91                                 t->trace->allsolid = false;
  92                         else
  93                         {
  94                                 // if the first leaf is solid, set startsolid
  95                                 if (t->trace->allsolid)
  96                                         t->trace->startsolid = true;
  97                                 return HULLCHECKSTATE_SOLID;
  98                         }
  99                         return HULLCHECKSTATE_EMPTY;
 100                 }
 101                 else
 102                 {
 103                         if (num != CONTENTS_SOLID)
 104                         {
 105                                 t->trace->allsolid = false;
 106                                 if (num == CONTENTS_EMPTY)
 107                                         t->trace->inopen = true;
 108                                 else
 109                                         t->trace->inwater = true;
 110                         }
 111                         else
 112                         {
 113                                 // if the first leaf is solid, set startsolid
 114                                 if (t->trace->allsolid)
 115                                         t->trace->startsolid = true;
 116                                 return HULLCHECKSTATE_SOLID;
 117                         }
 118                         return HULLCHECKSTATE_EMPTY;
 119                 }
 120         }
 121
 122         // find the point distances
 123         node = t->hull->clipnodes + num;
 124
 125         plane = t->hull->planes + node->planenum;
 126         if (plane->type < 3)
 127         {
 128                 t1 = p1[plane->type] - plane->dist;
 129                 t2 = p2[plane->type] - plane->dist;
 130         }
 131         else
 132         {
 133                 t1 = DotProduct (plane->normal, p1) - plane->dist;
 134                 t2 = DotProduct (plane->normal, p2) - plane->dist;
 135         }
 136
 137         side = t1 < 0;
 138
 139         if (side)
 140         {
 141                 if (t1 < -DIST_EPSILON && t2 < -DIST_EPSILON)
 142                 {
 143                         num = node->children[1];
 144                         goto loc0;
 145                 }
 146         }
 147         else
 148         {
 149                 if (t1 > DIST_EPSILON && t2 > DIST_EPSILON)
 150                 {
 151                         num = node->children[0];
 152                         goto loc0;
 153                 }
 154         }
 155
 156         // the line (almost) intersects, recurse both sides
 157
 158         frac = t1 / (t1 - t2);
 159         frac = bound(0.0f, frac, 1.0);
 160
 161         midf = p1f + ((p2f - p1f) * frac);
 162         VectorMA(t->start, midf, t->dist, mid);
 163
 164         // front side first
 165         ret = RecursiveHullCheck (t, node->children[side], p1f, midf, p1, mid);
 166         if (ret != HULLCHECKSTATE_EMPTY)
 167                 return ret; // solid or done
 168         ret = RecursiveHullCheck (t, node->children[!side], midf, p2f, mid, p2);
 169         if (ret != HULLCHECKSTATE_SOLID)
 170                 return ret; // empty or done
 171
 172         // front is air and back is solid, this is the impact point...
 173         RecursiveHullCheck_Impact(t, t->hull->planes + node->planenum, side);
 174
 175         return HULLCHECKSTATE_DONE;
 176 }
 177
 178 void Collision_RoundUpToHullSize(const model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
 179 {
 180         vec3_t size;
 181         const hull_t *hull;
 182
 183         VectorSubtract(inmaxs, inmins, size);
 184         if (cmodel->ishlbsp)
 185         {
 186                 if (size[0] < 3)
 187                         hull = &cmodel->hulls[0]; // 0x0x0
 188                 else if (size[0] <= 32)
 189                 {
 190                         if (size[2] < 54) // pick the nearest of 36 or 72
 191                                 hull = &cmodel->hulls[3]; // 32x32x36
 192                         else
 193                                 hull = &cmodel->hulls[1]; // 32x32x72
 194                 }
 195                 else
 196                         hull = &cmodel->hulls[2]; // 64x64x64
 197         }
 198         else
 199         {
 200                 if (size[0] < 3)
 201                         hull = &cmodel->hulls[0]; // 0x0x0
 202                 else if (size[0] <= 32)
 203                         hull = &cmodel->hulls[1]; // 32x32x56
 204                 else
 205                         hull = &cmodel->hulls[2]; // 64x64x88
 206         }
 207         VectorCopy(inmins, outmins);
 208         VectorAdd(inmins, hull->clip_size, outmaxs);
 209 }
 210
 211 static hull_t box_hull;
 212 static dclipnode_t box_clipnodes[6];
 213 static mplane_t box_planes[6];
 214
 215 void Collision_Init (void)
 216 {
 217         int             i;
 218         int             side;
 219
 220         //Set up the planes and clipnodes so that the six floats of a bounding box
 221         //can just be stored out and get a proper hull_t structure.
 222
 223         box_hull.clipnodes = box_clipnodes;
 224         box_hull.planes = box_planes;
 225         box_hull.firstclipnode = 0;
 226         box_hull.lastclipnode = 5;
 227
 228         for (i = 0;i < 6;i++)
 229         {
 230                 box_clipnodes[i].planenum = i;
 231
 232                 side = i&1;
 233
 234                 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
 235                 if (i != 5)
 236                         box_clipnodes[i].children[side^1] = i + 1;
 237                 else
 238                         box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
 239
 240                 box_planes[i].type = i>>1;
 241                 box_planes[i].normal[i>>1] = 1;
 242         }
 243 }
 244
 245
 246 static hull_t *HullForBBoxEntity (const vec3_t corigin, const vec3_t cmins, const vec3_t cmaxs, const vec3_t mins, const vec3_t maxs, vec3_t offset)
 247 {
 248         vec3_t hullmins, hullmaxs;
 249
 250         // create a temp hull from bounding box sizes
 251         VectorCopy (corigin, offset);
 252         VectorSubtract (cmins, maxs, hullmins);
 253         VectorSubtract (cmaxs, mins, hullmaxs);
 254
 255         //To keep everything totally uniform, bounding boxes are turned into small
 256         //BSP trees instead of being compared directly.
 257         box_planes[0].dist = hullmaxs[0];
 258         box_planes[1].dist = hullmins[0];
 259         box_planes[2].dist = hullmaxs[1];
 260         box_planes[3].dist = hullmins[1];
 261         box_planes[4].dist = hullmaxs[2];
 262         box_planes[5].dist = hullmins[2];
 263         return &box_hull;
 264 }
 265
 266 static const hull_t *HullForBrushModel (const model_t *cmodel, const vec3_t corigin, const vec3_t mins, const vec3_t maxs, vec3_t offset)
 267 {
 268         vec3_t size;
 269         const hull_t *hull;
 270
 271         // decide which clipping hull to use, based on the size
 272         // explicit hulls in the BSP model
 273         VectorSubtract (maxs, mins, size);
 274         // LordHavoc: FIXME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 275         if (cmodel->ishlbsp)
 276         {
 277                 if (size[0] < 3)
 278                         hull = &cmodel->hulls[0]; // 0x0x0
 279                 else if (size[0] <= 32)
 280                 {
 281                         if (size[2] < 54) // pick the nearest of 36 or 72
 282                                 hull = &cmodel->hulls[3]; // 32x32x36
 283                         else
 284                                 hull = &cmodel->hulls[1]; // 32x32x72
 285                 }
 286                 else
 287                         hull = &cmodel->hulls[2]; // 64x64x64
 288         }
 289         else
 290         {
 291                 if (size[0] < 3)
 292                         hull = &cmodel->hulls[0]; // 0x0x0
 293                 else if (size[0] <= 32)
 294                         hull = &cmodel->hulls[1]; // 32x32x56
 295                 else
 296                         hull = &cmodel->hulls[2]; // 64x64x88
 297         }
 298
 299         // calculate an offset value to center the origin
 300         VectorSubtract (hull->clip_mins, mins, offset);
 301         VectorAdd (offset, corigin, offset);
 302
 303         return hull;
 304 }
 305
 306 void Collision_ClipTrace (trace_t *trace, const void *cent, const model_t *cmodel, const vec3_t corigin, const vec3_t cangles, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end)
 307 {
 308         RecursiveHullCheckTraceInfo_t rhc;
 309         vec3_t offset, forward, left, up;
 310         double startd[3], endd[3], tempd[3];
 311
 312         // fill in a default trace
 313         memset (&rhc, 0, sizeof(rhc));
 314         memset (trace, 0, sizeof(trace_t));
 315
 316         rhc.trace = trace;
 317
 318         rhc.trace->fraction = 1;
 319         rhc.trace->allsolid = true;
 320
 321         if (cmodel && cmodel->type == mod_brush)
 322         {
 323                 // brush model
 324
 325                 // get the clipping hull
 326                 rhc.hull = HullForBrushModel (cmodel, corigin, mins, maxs, offset);
 327
 328                 VectorSubtract(start, offset, startd);
 329                 VectorSubtract(end, offset, endd);
 330
 331                 // rotate start and end into the model's frame of reference
 332                 if (cangles[0] || cangles[1] || cangles[2])
 333                 {
 334                         AngleVectorsFLU (cangles, forward, left, up);
 335                         VectorCopy(startd, tempd);
 336                         startd[0] = DotProduct (tempd, forward);
 337                         startd[1] = DotProduct (tempd, left);
 338                         startd[2] = DotProduct (tempd, up);
 339                         VectorCopy(endd, tempd);
 340                         endd[0] = DotProduct (tempd, forward);
 341                         endd[1] = DotProduct (tempd, left);
 342                         endd[2] = DotProduct (tempd, up);
 343                 }
 344
 345                 VectorCopy(end, rhc.trace->endpos);
 346
 347                 // trace a line through the appropriate clipping hull
 348                 VectorCopy(startd, rhc.start);
 349                 VectorCopy(endd, rhc.end);
 350
 351                 VectorSubtract(rhc.end, rhc.start, rhc.dist);
 352                 RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, startd, endd);
 353
 354                 // if we hit, unrotate endpos and normal, and store the entity we hit
 355                 if (rhc.trace->fraction != 1)
 356                 {
 357                         // rotate endpos back to world frame of reference
 358                         if (cangles[0] || cangles[1] || cangles[2])
 359                         {
 360                                 VectorNegate (cangles, offset);
 361                                 AngleVectorsFLU (offset, forward, left, up);
 362
 363                                 VectorCopy (rhc.trace->endpos, tempd);
 364                                 rhc.trace->endpos[0] = DotProduct (tempd, forward);
 365                                 rhc.trace->endpos[1] = DotProduct (tempd, left);
 366                                 rhc.trace->endpos[2] = DotProduct (tempd, up);
 367
 368                                 VectorCopy (rhc.trace->plane.normal, tempd);
 369                                 rhc.trace->plane.normal[0] = DotProduct (tempd, forward);
 370                                 rhc.trace->plane.normal[1] = DotProduct (tempd, left);
 371                                 rhc.trace->plane.normal[2] = DotProduct (tempd, up);
 372                         }
 373                         // fix offset
 374                         VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
 375                         rhc.trace->ent = (void *) cent;
 376                 }
 377                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
 378                         rhc.trace->ent = (void *) cent;
 379         }
 380         else
 381         {
 382                 // bounding box
 383
 384                 rhc.hull = HullForBBoxEntity (corigin, cmins, cmaxs, mins, maxs, offset);
 385
 386                 VectorSubtract(start, offset, startd);
 387                 VectorSubtract(end, offset, endd);
 388                 VectorCopy(end, rhc.trace->endpos);
 389
 390                 // trace a line through the generated clipping hull
 391                 VectorCopy(startd, rhc.start);
 392                 VectorSubtract(endd, startd, rhc.dist);
 393                 RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, startd, endd);
 394
 395                 // if we hit, store the entity we hit
 396                 if (rhc.trace->fraction != 1)
 397                 {
 398                         // fix offset
 399                         VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
 400                         rhc.trace->ent = (void *) cent;
 401                 }
 402                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
 403                         rhc.trace->ent = (void *) cent;
 404         }
 405 }