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