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 /*
 169 // used if start and end are the same
 170 static void RecursiveHullCheckPoint (RecursiveHullCheckTraceInfo_t *t, int num)
 171 {
 172         // If you can read this, you understand BSP trees
 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
 209 void Collision_RoundUpToHullSize(const model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs)
 210 {
 211         vec3_t size;
 212         const hull_t *hull;
 213
 214         VectorSubtract(inmaxs, inmins, size);
 215         if (cmodel->ishlbsp)
 216         {
 217                 if (size[0] < 3)
 218                         hull = &cmodel->hulls[0]; // 0x0x0
 219                 else if (size[0] <= 32)
 220                 {
 221                         if (size[2] < 54) // pick the nearest of 36 or 72
 222                                 hull = &cmodel->hulls[3]; // 32x32x36
 223                         else
 224                                 hull = &cmodel->hulls[1]; // 32x32x72
 225                 }
 226                 else
 227                         hull = &cmodel->hulls[2]; // 64x64x64
 228         }
 229         else
 230         {
 231                 if (size[0] < 3)
 232                         hull = &cmodel->hulls[0]; // 0x0x0
 233                 else if (size[0] <= 32)
 234                         hull = &cmodel->hulls[1]; // 32x32x56
 235                 else
 236                         hull = &cmodel->hulls[2]; // 64x64x88
 237         }
 238         VectorCopy(inmins, outmins);
 239         VectorAdd(inmins, hull->clip_size, outmaxs);
 240 }
 241
 242 static hull_t box_hull;
 243 static dclipnode_t box_clipnodes[6];
 244 static mplane_t box_planes[6];
 245
 246 void Collision_Init (void)
 247 {
 248         int             i;
 249         int             side;
 250
 251         //Set up the planes and clipnodes so that the six floats of a bounding box
 252         //can just be stored out and get a proper hull_t structure.
 253
 254         box_hull.clipnodes = box_clipnodes;
 255         box_hull.planes = box_planes;
 256         box_hull.firstclipnode = 0;
 257         box_hull.lastclipnode = 5;
 258
 259         for (i = 0;i < 6;i++)
 260         {
 261                 box_clipnodes[i].planenum = i;
 262
 263                 side = i&1;
 264
 265                 box_clipnodes[i].children[side] = CONTENTS_EMPTY;
 266                 if (i != 5)
 267                         box_clipnodes[i].children[side^1] = i + 1;
 268                 else
 269                         box_clipnodes[i].children[side^1] = CONTENTS_SOLID;
 270
 271                 box_planes[i].type = i>>1;
 272                 box_planes[i].normal[i>>1] = 1;
 273         }
 274 }
 275
 276
 277 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)
 278 {
 279         vec3_t hullmins, hullmaxs;
 280
 281         // create a temp hull from bounding box sizes
 282         VectorCopy (corigin, offset);
 283         VectorSubtract (cmins, maxs, hullmins);
 284         VectorSubtract (cmaxs, mins, hullmaxs);
 285
 286         //To keep everything totally uniform, bounding boxes are turned into small
 287         //BSP trees instead of being compared directly.
 288         box_planes[0].dist = hullmaxs[0];
 289         box_planes[1].dist = hullmins[0];
 290         box_planes[2].dist = hullmaxs[1];
 291         box_planes[3].dist = hullmins[1];
 292         box_planes[4].dist = hullmaxs[2];
 293         box_planes[5].dist = hullmins[2];
 294         return &box_hull;
 295 }
 296
 297 static const hull_t *HullForBrushModel (const model_t *cmodel, const vec3_t corigin, const vec3_t mins, const vec3_t maxs, vec3_t offset)
 298 {
 299         vec3_t size;
 300         const hull_t *hull;
 301
 302         // decide which clipping hull to use, based on the size
 303         // explicit hulls in the BSP model
 304         VectorSubtract (maxs, mins, size);
 305         // LordHavoc: FIXME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 306         if (cmodel->ishlbsp)
 307         {
 308                 if (size[0] < 3)
 309                         hull = &cmodel->hulls[0]; // 0x0x0
 310                 else if (size[0] <= 32)
 311                 {
 312                         if (size[2] < 54) // pick the nearest of 36 or 72
 313                                 hull = &cmodel->hulls[3]; // 32x32x36
 314                         else
 315                                 hull = &cmodel->hulls[1]; // 32x32x72
 316                 }
 317                 else
 318                         hull = &cmodel->hulls[2]; // 64x64x64
 319         }
 320         else
 321         {
 322                 if (size[0] < 3)
 323                         hull = &cmodel->hulls[0]; // 0x0x0
 324                 else if (size[0] <= 32)
 325                         hull = &cmodel->hulls[1]; // 32x32x56
 326                 else
 327                         hull = &cmodel->hulls[2]; // 64x64x88
 328         }
 329
 330         // calculate an offset value to center the origin
 331         VectorSubtract (hull->clip_mins, mins, offset);
 332         VectorAdd (offset, corigin, offset);
 333
 334         return hull;
 335 }
 336
 337 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)
 338 {
 339         RecursiveHullCheckTraceInfo_t rhc;
 340         vec3_t offset, forward, left, up;
 341         double startd[3], endd[3], tempd[3];
 342
 343         // fill in a default trace
 344         memset (&rhc, 0, sizeof(rhc));
 345         memset (trace, 0, sizeof(trace_t));
 346
 347         rhc.trace = trace;
 348
 349         rhc.trace->fraction = 1;
 350         rhc.trace->allsolid = true;
 351
 352         if (cmodel && cmodel->type == mod_brush)
 353         {
 354                 // brush model
 355
 356                 // get the clipping hull
 357                 rhc.hull = HullForBrushModel (cmodel, corigin, mins, maxs, offset);
 358
 359                 VectorSubtract(start, offset, startd);
 360                 VectorSubtract(end, offset, endd);
 361
 362                 // rotate start and end into the model's frame of reference
 363                 if (cangles[0] || cangles[1] || cangles[2])
 364                 {
 365                         AngleVectorsFLU (cangles, forward, left, up);
 366                         VectorCopy(startd, tempd);
 367                         startd[0] = DotProduct (tempd, forward);
 368                         startd[1] = DotProduct (tempd, left);
 369                         startd[2] = DotProduct (tempd, up);
 370                         VectorCopy(endd, tempd);
 371                         endd[0] = DotProduct (tempd, forward);
 372                         endd[1] = DotProduct (tempd, left);
 373                         endd[2] = DotProduct (tempd, up);
 374                 }
 375
 376                 // trace a line through the appropriate clipping hull
 377                 VectorCopy(startd, rhc.start);
 378                 VectorCopy(endd, rhc.end);
 379                 VectorCopy(rhc.end, rhc.trace->endpos);
 380                 VectorSubtract(rhc.end, rhc.start, rhc.dist);
 381                 //if (DotProduct(rhc.dist, rhc.dist) > 0.00001)
 382                         RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
 383                 //else
 384                 //      RecursiveHullCheckPoint (&rhc, rhc.hull->firstclipnode);
 385
 386                 // if we hit, unrotate endpos and normal, and store the entity we hit
 387                 if (rhc.trace->fraction != 1)
 388                 {
 389                         // rotate endpos back to world frame of reference
 390                         if (cangles[0] || cangles[1] || cangles[2])
 391                         {
 392                                 VectorNegate (cangles, offset);
 393                                 AngleVectorsFLU (offset, forward, left, up);
 394
 395                                 VectorCopy (rhc.trace->endpos, tempd);
 396                                 rhc.trace->endpos[0] = DotProduct (tempd, forward);
 397                                 rhc.trace->endpos[1] = DotProduct (tempd, left);
 398                                 rhc.trace->endpos[2] = DotProduct (tempd, up);
 399
 400                                 VectorCopy (rhc.trace->plane.normal, tempd);
 401                                 rhc.trace->plane.normal[0] = DotProduct (tempd, forward);
 402                                 rhc.trace->plane.normal[1] = DotProduct (tempd, left);
 403                                 rhc.trace->plane.normal[2] = DotProduct (tempd, up);
 404                         }
 405                         rhc.trace->ent = (void *) cent;
 406                 }
 407                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
 408                         rhc.trace->ent = (void *) cent;
 409                 // fix offset
 410                 VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
 411         }
 412         else
 413         {
 414                 // bounding box
 415
 416                 rhc.hull = HullForBBoxEntity (corigin, cmins, cmaxs, mins, maxs, offset);
 417
 418                 // trace a line through the generated clipping hull
 419                 VectorSubtract(start, offset, rhc.start);
 420                 VectorSubtract(end, offset, rhc.end);
 421                 VectorCopy(rhc.end, rhc.trace->endpos);
 422                 VectorSubtract(rhc.end, rhc.start, rhc.dist);
 423                 //if (DotProduct(rhc.dist, rhc.dist) > 0.00001)
 424                         RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
 425                 //else
 426                 //      RecursiveHullCheckPoint (&rhc, rhc.hull->firstclipnode);
 427
 428                 // if we hit, store the entity we hit
 429                 if (rhc.trace->fraction != 1)
 430                 {
 431                         // fix offset
 432                         VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos);
 433                         rhc.trace->ent = (void *) cent;
 434                 }
 435                 else if (rhc.trace->allsolid || rhc.trace->startsolid)
 436                         rhc.trace->ent = (void *) cent;
 437         }
 438 }
 439