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