collision.c

   1
   2 #include "quakedef.h"
   3 #include "polygon.h"
   4
   5 #define COLLISION_EDGEDIR_DOT_EPSILON (0.999f)
   6 #define COLLISION_EDGECROSS_MINLENGTH2 (1.0f / 4194304.0f)
   7 #define COLLISION_SNAPSCALE (32.0f)
   8 #define COLLISION_SNAP (1.0f / COLLISION_SNAPSCALE)
   9 #define COLLISION_SNAP2 (2.0f / COLLISION_SNAPSCALE)
  10 #define COLLISION_PLANE_DIST_EPSILON (2.0f / COLLISION_SNAPSCALE)
  11
  12 cvar_t collision_impactnudge = {0, "collision_impactnudge", "0.03125", "how much to back off from the impact"};
  13 cvar_t collision_startnudge = {0, "collision_startnudge", "0", "how much to bias collision trace start"};
  14 cvar_t collision_endnudge = {0, "collision_endnudge", "0", "how much to bias collision trace end"};
  15 cvar_t collision_enternudge = {0, "collision_enternudge", "0", "how much to bias collision entry fraction"};
  16 cvar_t collision_leavenudge = {0, "collision_leavenudge", "0", "how much to bias collision exit fraction"};
  17 cvar_t collision_prefernudgedfraction = {0, "collision_prefernudgedfraction", "1", "whether to sort collision events by nudged fraction (1) or real fraction (0)"};
  18 #ifdef COLLISION_STUPID_TRACE_ENDPOS_IN_SOLID_WORKAROUND
  19 cvar_t collision_endposnudge = {0, "collision_endposnudge", "0", "workaround to fix trace_endpos sometimes being returned where it would be inside solid by making that collision hit (recommended: values like 1)"};
  20 #endif
  21 cvar_t collision_debug_tracelineasbox = {0, "collision_debug_tracelineasbox", "0", "workaround for any bugs in Collision_TraceLineBrushFloat by using Collision_TraceBrushBrushFloat"};
  22 cvar_t collision_cache = {0, "collision_cache", "1", "store results of collision traces for next frame to reuse if possible (optimization)"};
  23 //cvar_t collision_triangle_neighborsides = {0, "collision_triangle_neighborsides", "1", "override automatic side generation if triangle has neighbors with face planes that form a convex edge (perfect solution, but can not work for all edges)"};
  24 cvar_t collision_triangle_bevelsides = {0, "collision_triangle_bevelsides", "1", "generate sloped edge planes on triangles - if 0, see axialedgeplanes"};
  25 cvar_t collision_triangle_axialsides = {0, "collision_triangle_axialsides", "1", "generate axially-aligned edge planes on triangles - otherwise use perpendicular edge planes"};
  26
  27 mempool_t *collision_mempool;
  28
  29 void Collision_Init (void)
  30 {
  31         Cvar_RegisterVariable(&collision_impactnudge);
  32         Cvar_RegisterVariable(&collision_startnudge);
  33         Cvar_RegisterVariable(&collision_endnudge);
  34         Cvar_RegisterVariable(&collision_enternudge);
  35         Cvar_RegisterVariable(&collision_leavenudge);
  36         Cvar_RegisterVariable(&collision_prefernudgedfraction);
  37 #ifdef COLLISION_STUPID_TRACE_ENDPOS_IN_SOLID_WORKAROUND
  38         Cvar_RegisterVariable(&collision_endposnudge);
  39 #endif
  40         Cvar_RegisterVariable(&collision_debug_tracelineasbox);
  41         Cvar_RegisterVariable(&collision_cache);
  42 //      Cvar_RegisterVariable(&collision_triangle_neighborsides);
  43         Cvar_RegisterVariable(&collision_triangle_bevelsides);
  44         Cvar_RegisterVariable(&collision_triangle_axialsides);
  45         collision_mempool = Mem_AllocPool("collision cache", 0, NULL);
  46         Collision_Cache_Init(collision_mempool);
  47 }
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62 static void Collision_PrintBrushAsQHull(colbrushf_t *brush, const char *name)
  63 {
  64         int i;
  65         Con_Printf("3 %s\n%i\n", name, brush->numpoints);
  66         for (i = 0;i < brush->numpoints;i++)
  67                 Con_Printf("%f %f %f\n", brush->points[i].v[0], brush->points[i].v[1], brush->points[i].v[2]);
  68         // FIXME: optimize!
  69         Con_Printf("4\n%i\n", brush->numplanes);
  70         for (i = 0;i < brush->numplanes;i++)
  71                 Con_Printf("%f %f %f %f\n", brush->planes[i].normal[0], brush->planes[i].normal[1], brush->planes[i].normal[2], brush->planes[i].dist);
  72 }
  73
  74 static void Collision_ValidateBrush(colbrushf_t *brush)
  75 {
  76         int j, k, pointsoffplanes, pointonplanes, pointswithinsufficientplanes, printbrush;
  77         float d;
  78         printbrush = false;
  79         if (!brush->numpoints)
  80         {
  81                 Con_Print("Collision_ValidateBrush: brush with no points!\n");
  82                 printbrush = true;
  83         }
  84 #if 0
  85         // it's ok for a brush to have one point and no planes...
  86         if (brush->numplanes == 0 && brush->numpoints != 1)
  87         {
  88                 Con_Print("Collision_ValidateBrush: brush with no planes and more than one point!\n");
  89                 printbrush = true;
  90         }
  91 #endif
  92         if (brush->numplanes)
  93         {
  94                 pointsoffplanes = 0;
  95                 pointswithinsufficientplanes = 0;
  96                 for (k = 0;k < brush->numplanes;k++)
  97                         if (DotProduct(brush->planes[k].normal, brush->planes[k].normal) < 0.0001f)
  98                                 Con_Printf("Collision_ValidateBrush: plane #%i (%f %f %f %f) is degenerate\n", k, brush->planes[k].normal[0], brush->planes[k].normal[1], brush->planes[k].normal[2], brush->planes[k].dist);
  99                 for (j = 0;j < brush->numpoints;j++)
 100                 {
 101                         pointonplanes = 0;
 102                         for (k = 0;k < brush->numplanes;k++)
 103                         {
 104                                 d = DotProduct(brush->points[j].v, brush->planes[k].normal) - brush->planes[k].dist;
 105                                 if (d > COLLISION_PLANE_DIST_EPSILON)
 106                                 {
 107                                         Con_Printf("Collision_ValidateBrush: point #%i (%f %f %f) infront of plane #%i (%f %f %f %f)\n", j, brush->points[j].v[0], brush->points[j].v[1], brush->points[j].v[2], k, brush->planes[k].normal[0], brush->planes[k].normal[1], brush->planes[k].normal[2], brush->planes[k].dist);
 108                                         printbrush = true;
 109                                 }
 110                                 if (fabs(d) > COLLISION_PLANE_DIST_EPSILON)
 111                                         pointsoffplanes++;
 112                                 else
 113                                         pointonplanes++;
 114                         }
 115                         if (pointonplanes < 3)
 116                                 pointswithinsufficientplanes++;
 117                 }
 118                 if (pointswithinsufficientplanes)
 119                 {
 120                         Con_Print("Collision_ValidateBrush: some points have insufficient planes, every point must be on at least 3 planes to form a corner.\n");
 121                         printbrush = true;
 122                 }
 123                 if (pointsoffplanes == 0) // all points are on all planes
 124                 {
 125                         Con_Print("Collision_ValidateBrush: all points lie on all planes (degenerate, no brush volume!)\n");
 126                         printbrush = true;
 127                 }
 128         }
 129         if (printbrush)
 130                 Collision_PrintBrushAsQHull(brush, "unnamed");
 131 }
 132
 133 static float nearestplanedist_float(const float *normal, const colpointf_t *points, int numpoints)
 134 {
 135         float dist, bestdist;
 136         if (!numpoints)
 137                 return 0;
 138         bestdist = DotProduct(points->v, normal);
 139         points++;
 140         while(--numpoints)
 141         {
 142                 dist = DotProduct(points->v, normal);
 143                 bestdist = min(bestdist, dist);
 144                 points++;
 145         }
 146         return bestdist;
 147 }
 148
 149 static float furthestplanedist_float(const float *normal, const colpointf_t *points, int numpoints)
 150 {
 151         float dist, bestdist;
 152         if (!numpoints)
 153                 return 0;
 154         bestdist = DotProduct(points->v, normal);
 155         points++;
 156         while(--numpoints)
 157         {
 158                 dist = DotProduct(points->v, normal);
 159                 bestdist = max(bestdist, dist);
 160                 points++;
 161         }
 162         return bestdist;
 163 }
 164
 165 static void Collision_CalcEdgeDirsForPolygonBrushFloat(colbrushf_t *brush)
 166 {
 167         int i, j;
 168         for (i = 0, j = brush->numpoints - 1;i < brush->numpoints;j = i, i++)
 169                 VectorSubtract(brush->points[i].v, brush->points[j].v, brush->edgedirs[j].v);
 170 }
 171
 172 colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const colplanef_t *originalplanes, int supercontents, int q3surfaceflags, const texture_t *texture, int hasaabbplanes)
 173 {
 174         // TODO: planesbuf could be replaced by a remapping table
 175         int j, k, l, m, w, xyzflags;
 176         int numpointsbuf = 0, maxpointsbuf = 256, numedgedirsbuf = 0, maxedgedirsbuf = 256, numplanesbuf = 0, maxplanesbuf = 256, numelementsbuf = 0, maxelementsbuf = 256;
 177         int isaabb = true;
 178         double maxdist;
 179         colbrushf_t *brush;
 180         colpointf_t pointsbuf[256];
 181         colpointf_t edgedirsbuf[256];
 182         colplanef_t planesbuf[256];
 183         int elementsbuf[1024];
 184         int polypointbuf[256];
 185         int pmaxpoints = 64;
 186         int pnumpoints;
 187         double p[2][3*64];
 188 #if 0
 189         // enable these if debugging to avoid seeing garbage in unused data-
 190         memset(pointsbuf, 0, sizeof(pointsbuf));
 191         memset(edgedirsbuf, 0, sizeof(edgedirsbuf));
 192         memset(planesbuf, 0, sizeof(planesbuf));
 193         memset(elementsbuf, 0, sizeof(elementsbuf));
 194         memset(polypointbuf, 0, sizeof(polypointbuf));
 195         memset(p, 0, sizeof(p));
 196 #endif
 197
 198         // check if there are too many planes and skip the brush
 199         if (numoriginalplanes >= maxplanesbuf)
 200         {
 201                 Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many planes for buffer\n");
 202                 return NULL;
 203         }
 204
 205         // figure out how large a bounding box we need to properly compute this brush
 206         maxdist = 0;
 207         for (j = 0;j < numoriginalplanes;j++)
 208                 maxdist = max(maxdist, fabs(originalplanes[j].dist));
 209         // now make it large enough to enclose the entire brush, and round it off to a reasonable multiple of 1024
 210         maxdist = floor(maxdist * (4.0 / 1024.0) + 2) * 1024.0;
 211         // construct a collision brush (points, planes, and renderable mesh) from
 212         // a set of planes, this also optimizes out any unnecessary planes (ones
 213         // whose polygon is clipped away by the other planes)
 214         for (j = 0;j < numoriginalplanes;j++)
 215         {
 216                 // add the new plane
 217                 VectorCopy(originalplanes[j].normal, planesbuf[numplanesbuf].normal);
 218                 planesbuf[numplanesbuf].dist = originalplanes[j].dist;
 219                 planesbuf[numplanesbuf].q3surfaceflags = originalplanes[j].q3surfaceflags;
 220                 planesbuf[numplanesbuf].texture = originalplanes[j].texture;
 221                 numplanesbuf++;
 222
 223                 // create a large polygon from the plane
 224                 w = 0;
 225                 PolygonD_QuadForPlane(p[w], originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist, maxdist);
 226                 pnumpoints = 4;
 227                 // clip it by all other planes
 228                 for (k = 0;k < numoriginalplanes && pnumpoints >= 3 && pnumpoints <= pmaxpoints;k++)
 229                 {
 230                         // skip the plane this polygon
 231                         // (nothing happens if it is processed, this is just an optimization)
 232                         if (k != j)
 233                         {
 234                                 // we want to keep the inside of the brush plane so we flip
 235                                 // the cutting plane
 236                                 PolygonD_Divide(pnumpoints, p[w], -originalplanes[k].normal[0], -originalplanes[k].normal[1], -originalplanes[k].normal[2], -originalplanes[k].dist, COLLISION_PLANE_DIST_EPSILON, pmaxpoints, p[!w], &pnumpoints, 0, NULL, NULL, NULL);
 237                                 w = !w;
 238                         }
 239                 }
 240
 241                 // if nothing is left, skip it
 242                 if (pnumpoints < 3)
 243                 {
 244                         //Con_DPrintf("Collision_NewBrushFromPlanes: warning: polygon for plane %f %f %f %f clipped away\n", originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist);
 245                         continue;
 246                 }
 247
 248                 for (k = 0;k < pnumpoints;k++)
 249                 {
 250                         int l, m;
 251                         m = 0;
 252                         for (l = 0;l < numoriginalplanes;l++)
 253                                 if (fabs(DotProduct(&p[w][k*3], originalplanes[l].normal) - originalplanes[l].dist) < COLLISION_PLANE_DIST_EPSILON)
 254                                         m++;
 255                         if (m < 3)
 256                                 break;
 257                 }
 258                 if (k < pnumpoints)
 259                 {
 260                         Con_DPrintf("Collision_NewBrushFromPlanes: warning: polygon point does not lie on at least 3 planes\n");
 261                         //return NULL;
 262                 }
 263
 264                 // check if there are too many polygon vertices for buffer
 265                 if (pnumpoints > pmaxpoints)
 266                 {
 267                         Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n");
 268                         return NULL;
 269                 }
 270
 271                 // check if there are too many triangle elements for buffer
 272                 if (numelementsbuf + (pnumpoints - 2) * 3 > maxelementsbuf)
 273                 {
 274                         Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many triangle elements for buffer\n");
 275                         return NULL;
 276                 }
 277
 278                 // add the unique points for this polygon
 279                 for (k = 0;k < pnumpoints;k++)
 280                 {
 281                         float v[3];
 282                         // downgrade to float precision before comparing
 283                         VectorCopy(&p[w][k*3], v);
 284
 285                         // check if there is already a matching point (no duplicates)
 286                         for (m = 0;m < numpointsbuf;m++)
 287                                 if (VectorDistance2(v, pointsbuf[m].v) < COLLISION_SNAP2)
 288                                         break;
 289
 290                         // if there is no match, add a new one
 291                         if (m == numpointsbuf)
 292                         {
 293                                 // check if there are too many and skip the brush
 294                                 if (numpointsbuf >= maxpointsbuf)
 295                                 {
 296                                         Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n");
 297                                         return NULL;
 298                                 }
 299                                 // add the new one
 300                                 VectorCopy(&p[w][k*3], pointsbuf[numpointsbuf].v);
 301                                 numpointsbuf++;
 302                         }
 303
 304                         // store the index into a buffer
 305                         polypointbuf[k] = m;
 306                 }
 307
 308                 // add the triangles for the polygon
 309                 // (this particular code makes a triangle fan)
 310                 for (k = 0;k < pnumpoints - 2;k++)
 311                 {
 312                         elementsbuf[numelementsbuf++] = polypointbuf[0];
 313                         elementsbuf[numelementsbuf++] = polypointbuf[k + 1];
 314                         elementsbuf[numelementsbuf++] = polypointbuf[k + 2];
 315                 }
 316
 317                 // add the unique edgedirs for this polygon
 318                 for (k = 0, l = pnumpoints-1;k < pnumpoints;l = k, k++)
 319                 {
 320                         float dir[3];
 321                         // downgrade to float precision before comparing
 322                         VectorSubtract(&p[w][k*3], &p[w][l*3], dir);
 323                         VectorNormalize(dir);
 324
 325                         // check if there is already a matching edgedir (no duplicates)
 326                         for (m = 0;m < numedgedirsbuf;m++)
 327                                 if (DotProduct(dir, edgedirsbuf[m].v) >= COLLISION_EDGEDIR_DOT_EPSILON)
 328                                         break;
 329                         // skip this if there is
 330                         if (m < numedgedirsbuf)
 331                                 continue;
 332
 333                         // try again with negated edgedir
 334                         VectorNegate(dir, dir);
 335                         // check if there is already a matching edgedir (no duplicates)
 336                         for (m = 0;m < numedgedirsbuf;m++)
 337                                 if (DotProduct(dir, edgedirsbuf[m].v) >= COLLISION_EDGEDIR_DOT_EPSILON)
 338                                         break;
 339                         // if there is no match, add a new one
 340                         if (m == numedgedirsbuf)
 341                         {
 342                                 // check if there are too many and skip the brush
 343                                 if (numedgedirsbuf >= maxedgedirsbuf)
 344                                 {
 345                                         Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many edgedirs for buffer\n");
 346                                         return NULL;
 347                                 }
 348                                 // add the new one
 349                                 VectorCopy(dir, edgedirsbuf[numedgedirsbuf].v);
 350                                 numedgedirsbuf++;
 351                         }
 352                 }
 353
 354                 // if any normal is not purely axial, it's not an axis-aligned box
 355                 if (isaabb && (originalplanes[j].normal[0] == 0) + (originalplanes[j].normal[1] == 0) + (originalplanes[j].normal[2] == 0) < 2)
 356                         isaabb = false;
 357         }
 358
 359         // if nothing is left, there's nothing to allocate
 360         if (numplanesbuf < 4)
 361         {
 362                 Con_DPrintf("Collision_NewBrushFromPlanes: failed to build collision brush: %i triangles, %i planes (input was %i planes), %i vertices\n", numelementsbuf / 3, numplanesbuf, numoriginalplanes, numpointsbuf);
 363                 return NULL;
 364         }
 365
 366         // if no triangles or points could be constructed, then this routine failed but the brush is not discarded
 367         if (numelementsbuf < 12 || numpointsbuf < 4)
 368                 Con_DPrintf("Collision_NewBrushFromPlanes: unable to rebuild triangles/points for collision brush: %i triangles, %i planes (input was %i planes), %i vertices\n", numelementsbuf / 3, numplanesbuf, numoriginalplanes, numpointsbuf);
 369
 370         // validate plane distances
 371         for (j = 0;j < numplanesbuf;j++)
 372         {
 373                 float d = furthestplanedist_float(planesbuf[j].normal, pointsbuf, numpointsbuf);
 374                 if (fabs(planesbuf[j].dist - d) > COLLISION_PLANE_DIST_EPSILON)
 375                         Con_DPrintf("plane %f %f %f %f mismatches dist %f\n", planesbuf[j].normal[0], planesbuf[j].normal[1], planesbuf[j].normal[2], planesbuf[j].dist, d);
 376         }
 377
 378         // allocate the brush and copy to it
 379         brush = (colbrushf_t *)Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colpointf_t) * numpointsbuf + sizeof(colpointf_t) * numedgedirsbuf + sizeof(colplanef_t) * numplanesbuf + sizeof(int) * numelementsbuf);
 380         brush->isaabb = isaabb;
 381         brush->hasaabbplanes = hasaabbplanes;
 382         brush->supercontents = supercontents;
 383         brush->numplanes = numplanesbuf;
 384         brush->numedgedirs = numedgedirsbuf;
 385         brush->numpoints = numpointsbuf;
 386         brush->numtriangles = numelementsbuf / 3;
 387         brush->planes = (colplanef_t *)(brush + 1);
 388         brush->points = (colpointf_t *)(brush->planes + brush->numplanes);
 389         brush->edgedirs = (colpointf_t *)(brush->points + brush->numpoints);
 390         brush->elements = (int *)(brush->points + brush->numpoints);
 391         brush->q3surfaceflags = q3surfaceflags;
 392         brush->texture = texture;
 393         for (j = 0;j < brush->numpoints;j++)
 394         {
 395                 brush->points[j].v[0] = pointsbuf[j].v[0];
 396                 brush->points[j].v[1] = pointsbuf[j].v[1];
 397                 brush->points[j].v[2] = pointsbuf[j].v[2];
 398         }
 399         for (j = 0;j < brush->numedgedirs;j++)
 400         {
 401                 brush->edgedirs[j].v[0] = edgedirsbuf[j].v[0];
 402                 brush->edgedirs[j].v[1] = edgedirsbuf[j].v[1];
 403                 brush->edgedirs[j].v[2] = edgedirsbuf[j].v[2];
 404         }
 405         for (j = 0;j < brush->numplanes;j++)
 406         {
 407                 brush->planes[j].normal[0] = planesbuf[j].normal[0];
 408                 brush->planes[j].normal[1] = planesbuf[j].normal[1];
 409                 brush->planes[j].normal[2] = planesbuf[j].normal[2];
 410                 brush->planes[j].dist = planesbuf[j].dist;
 411                 brush->planes[j].q3surfaceflags = planesbuf[j].q3surfaceflags;
 412                 brush->planes[j].texture = planesbuf[j].texture;
 413         }
 414         for (j = 0;j < brush->numtriangles * 3;j++)
 415                 brush->elements[j] = elementsbuf[j];
 416
 417         xyzflags = 0;
 418         VectorClear(brush->mins);
 419         VectorClear(brush->maxs);
 420         for (j = 0;j < min(6, numoriginalplanes);j++)
 421         {
 422                      if (originalplanes[j].normal[0] ==  1) {xyzflags |=  1;brush->maxs[0] =  originalplanes[j].dist;}
 423                 else if (originalplanes[j].normal[0] == -1) {xyzflags |=  2;brush->mins[0] = -originalplanes[j].dist;}
 424                 else if (originalplanes[j].normal[1] ==  1) {xyzflags |=  4;brush->maxs[1] =  originalplanes[j].dist;}
 425                 else if (originalplanes[j].normal[1] == -1) {xyzflags |=  8;brush->mins[1] = -originalplanes[j].dist;}
 426                 else if (originalplanes[j].normal[2] ==  1) {xyzflags |= 16;brush->maxs[2] =  originalplanes[j].dist;}
 427                 else if (originalplanes[j].normal[2] == -1) {xyzflags |= 32;brush->mins[2] = -originalplanes[j].dist;}
 428         }
 429         // if not all xyzflags were set, then this is not a brush from q3map/q3map2, and needs reconstruction of the bounding box
 430         // (this case works for any brush with valid points, but sometimes brushes are not reconstructed properly and hence the points are not valid, so this is reserved as a fallback case)
 431         if (xyzflags != 63)
 432         {
 433                 VectorCopy(brush->points[0].v, brush->mins);
 434                 VectorCopy(brush->points[0].v, brush->maxs);
 435                 for (j = 1;j < brush->numpoints;j++)
 436                 {
 437                         brush->mins[0] = min(brush->mins[0], brush->points[j].v[0]);
 438                         brush->mins[1] = min(brush->mins[1], brush->points[j].v[1]);
 439                         brush->mins[2] = min(brush->mins[2], brush->points[j].v[2]);
 440                         brush->maxs[0] = max(brush->maxs[0], brush->points[j].v[0]);
 441                         brush->maxs[1] = max(brush->maxs[1], brush->points[j].v[1]);
 442                         brush->maxs[2] = max(brush->maxs[2], brush->points[j].v[2]);
 443                 }
 444         }
 445         brush->mins[0] -= 1;
 446         brush->mins[1] -= 1;
 447         brush->mins[2] -= 1;
 448         brush->maxs[0] += 1;
 449         brush->maxs[1] += 1;
 450         brush->maxs[2] += 1;
 451         Collision_ValidateBrush(brush);
 452         return brush;
 453 }
 454
 455
 456
 457 void Collision_CalcPlanesForTriangleBrushFloat(colbrushf_t *brush)
 458 {
 459         int i;
 460         float edge0[3], edge1[3], edge2[3];
 461         colpointf_t *p;
 462
 463         TriangleNormal(brush->points[0].v, brush->points[1].v, brush->points[2].v, brush->planes[0].normal);
 464         if (DotProduct(brush->planes[0].normal, brush->planes[0].normal) < 0.0001f)
 465         {
 466                 // there's no point in processing a degenerate triangle (GIGO - Garbage In, Garbage Out)
 467                 // note that some of these exist in q3bsp bspline patches
 468                 brush->numplanes = 0;
 469                 return;
 470         }
 471
 472         // there are 5 planes (front, back, sides) and 3 edges
 473         brush->numplanes = 5;
 474         brush->numedgedirs = 3;
 475         VectorNormalize(brush->planes[0].normal);
 476         brush->planes[0].dist = DotProduct(brush->points->v, brush->planes[0].normal);
 477         VectorNegate(brush->planes[0].normal, brush->planes[1].normal);
 478         brush->planes[1].dist = -brush->planes[0].dist;
 479         // edge directions are easy to calculate
 480         VectorSubtract(brush->points[2].v, brush->points[0].v, edge0);
 481         VectorSubtract(brush->points[0].v, brush->points[1].v, edge1);
 482         VectorSubtract(brush->points[1].v, brush->points[2].v, edge2);
 483         VectorCopy(edge0, brush->edgedirs[0].v);
 484         VectorCopy(edge1, brush->edgedirs[1].v);
 485         VectorCopy(edge2, brush->edgedirs[2].v);
 486         // now select an algorithm to generate the side planes
 487         if (collision_triangle_bevelsides.integer)
 488         {
 489                 // use 45 degree slopes at the edges of the triangle to make a sinking trace error turn into "riding up" the slope rather than getting stuck
 490                 CrossProduct(edge0, brush->planes->normal, brush->planes[2].normal);
 491                 CrossProduct(edge1, brush->planes->normal, brush->planes[3].normal);
 492                 CrossProduct(edge2, brush->planes->normal, brush->planes[4].normal);
 493                 VectorNormalize(brush->planes[2].normal);
 494                 VectorNormalize(brush->planes[3].normal);
 495                 VectorNormalize(brush->planes[4].normal);
 496                 VectorAdd(brush->planes[2].normal, brush->planes[0].normal, brush->planes[2].normal);
 497                 VectorAdd(brush->planes[3].normal, brush->planes[0].normal, brush->planes[3].normal);
 498                 VectorAdd(brush->planes[4].normal, brush->planes[0].normal, brush->planes[4].normal);
 499                 VectorNormalize(brush->planes[2].normal);
 500                 VectorNormalize(brush->planes[3].normal);
 501                 VectorNormalize(brush->planes[4].normal);
 502         }
 503         else if (collision_triangle_axialsides.integer)
 504         {
 505                 float projectionnormal[3], projectionedge0[3], projectionedge1[3], projectionedge2[3];
 506                 int i, best;
 507                 float dist, bestdist;
 508                 bestdist = fabs(brush->planes[0].normal[0]);
 509                 best = 0;
 510                 for (i = 1;i < 3;i++)
 511                 {
 512                         dist = fabs(brush->planes[0].normal[i]);
 513                         if (bestdist < dist)
 514                         {
 515                                 bestdist = dist;
 516                                 best = i;
 517                         }
 518                 }
 519                 VectorClear(projectionnormal);
 520                 if (brush->planes[0].normal[best] < 0)
 521                         projectionnormal[best] = -1;
 522                 else
 523                         projectionnormal[best] = 1;
 524                 VectorCopy(edge0, projectionedge0);
 525                 VectorCopy(edge1, projectionedge1);
 526                 VectorCopy(edge2, projectionedge2);
 527                 projectionedge0[best] = 0;
 528                 projectionedge1[best] = 0;
 529                 projectionedge2[best] = 0;
 530                 CrossProduct(projectionedge0, projectionnormal, brush->planes[2].normal);
 531                 CrossProduct(projectionedge1, projectionnormal, brush->planes[3].normal);
 532                 CrossProduct(projectionedge2, projectionnormal, brush->planes[4].normal);
 533                 VectorNormalize(brush->planes[2].normal);
 534                 VectorNormalize(brush->planes[3].normal);
 535                 VectorNormalize(brush->planes[4].normal);
 536         }
 537         else
 538         {
 539                 CrossProduct(edge0, brush->planes->normal, brush->planes[2].normal);
 540                 CrossProduct(edge1, brush->planes->normal, brush->planes[3].normal);
 541                 CrossProduct(edge2, brush->planes->normal, brush->planes[4].normal);
 542                 VectorNormalize(brush->planes[2].normal);
 543                 VectorNormalize(brush->planes[3].normal);
 544                 VectorNormalize(brush->planes[4].normal);
 545         }
 546         brush->planes[2].dist = DotProduct(brush->points[2].v, brush->planes[2].normal);
 547         brush->planes[3].dist = DotProduct(brush->points[0].v, brush->planes[3].normal);
 548         brush->planes[4].dist = DotProduct(brush->points[1].v, brush->planes[4].normal);
 549
 550         if (developer_extra.integer)
 551         {
 552                 // validity check - will be disabled later
 553                 Collision_ValidateBrush(brush);
 554                 for (i = 0;i < brush->numplanes;i++)
 555                 {
 556                         int j;
 557                         for (j = 0, p = brush->points;j < brush->numpoints;j++, p++)
 558                                 if (DotProduct(p->v, brush->planes[i].normal) > brush->planes[i].dist + COLLISION_PLANE_DIST_EPSILON)
 559                                         Con_DPrintf("Error in brush plane generation, plane %i\n", i);
 560                 }
 561         }
 562 }
 563
 564 colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points, int supercontents, int q3surfaceflags, const texture_t *texture)
 565 {
 566         colbrushf_t *brush;
 567         brush = (colbrushf_t *)Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colplanef_t) * (numpoints + 2) + sizeof(colpointf_t) * numpoints);
 568         brush->isaabb = false;
 569         brush->hasaabbplanes = false;
 570         brush->supercontents = supercontents;
 571         brush->numpoints = numpoints;
 572         brush->numedgedirs = numpoints;
 573         brush->numplanes = numpoints + 2;
 574         brush->planes = (colplanef_t *)(brush + 1);
 575         brush->points = (colpointf_t *)points;
 576         brush->edgedirs = (colpointf_t *)(brush->planes + brush->numplanes);
 577         brush->q3surfaceflags = q3surfaceflags;
 578         brush->texture = texture;
 579         Sys_Error("Collision_AllocBrushFromPermanentPolygonFloat: FIXME: this code needs to be updated to generate a mesh...");
 580         return brush;
 581 }
 582
 583 // NOTE: start and end of each brush pair must have same numplanes/numpoints
 584 void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *trace_start, const colbrushf_t *trace_end, const colbrushf_t *other_start, const colbrushf_t *other_end)
 585 {
 586         int nplane, nplane2, nedge1, nedge2, hitq3surfaceflags = 0;
 587         int tracenumedgedirs = trace_start->numedgedirs;
 588         //int othernumedgedirs = other_start->numedgedirs;
 589         int tracenumpoints = trace_start->numpoints;
 590         int othernumpoints = other_start->numpoints;
 591         int numplanes1 = other_start->numplanes;
 592         int numplanes2 = numplanes1 + trace_start->numplanes;
 593         int numplanes3 = numplanes2 + trace_start->numedgedirs * other_start->numedgedirs * 2;
 594         vec_t enterfrac = -1, leavefrac = 1, startdist, enddist, ie, f, imove, enterfrac2 = -1;
 595         vec4_t startplane;
 596         vec4_t endplane;
 597         vec4_t newimpactplane;
 598         const texture_t *hittexture = NULL;
 599         vec_t startdepth = 1;
 600         vec3_t startdepthnormal;
 601
 602         VectorClear(startdepthnormal);
 603         Vector4Clear(newimpactplane);
 604
 605         // fast case for AABB vs compiled brushes (which begin with AABB planes and also have precomputed bevels for AABB collisions)
 606         if (trace_start->isaabb && other_start->hasaabbplanes)
 607                 numplanes3 = numplanes2 = numplanes1;
 608
 609         // Separating Axis Theorem:
 610         // if a supporting vector (plane normal) can be found that separates two
 611         // objects, they are not colliding.
 612         //
 613         // Minkowski Sum:
 614         // reduce the size of one object to a point while enlarging the other to
 615         // represent the space that point can not occupy.
 616         //
 617         // try every plane we can construct between the two brushes and measure
 618         // the distance between them.
 619         for (nplane = 0;nplane < numplanes3;nplane++)
 620         {
 621                 if (nplane < numplanes1)
 622                 {
 623                         nplane2 = nplane;
 624                         VectorCopy(other_start->planes[nplane2].normal, startplane);
 625                         VectorCopy(other_end->planes[nplane2].normal, endplane);
 626                 }
 627                 else if (nplane < numplanes2)
 628                 {
 629                         nplane2 = nplane - numplanes1;
 630                         VectorCopy(trace_start->planes[nplane2].normal, startplane);
 631                         VectorCopy(trace_end->planes[nplane2].normal, endplane);
 632                 }
 633                 else
 634                 {
 635                         // pick an edgedir from each brush and cross them
 636                         nplane2 = nplane - numplanes2;
 637                         nedge1 = nplane2 >> 1;
 638                         nedge2 = nedge1 / tracenumedgedirs;
 639                         nedge1 -= nedge2 * tracenumedgedirs;
 640                         if (nplane2 & 1)
 641                         {
 642                                 CrossProduct(trace_start->edgedirs[nedge1].v, other_start->edgedirs[nedge2].v, startplane);
 643                                 if (VectorLength2(startplane) < COLLISION_EDGECROSS_MINLENGTH2)
 644                                         continue; // degenerate crossproduct
 645                                 CrossProduct(trace_end->edgedirs[nedge1].v, other_end->edgedirs[nedge2].v, endplane);
 646                                 if (VectorLength2(endplane) < COLLISION_EDGECROSS_MINLENGTH2)
 647                                         continue; // degenerate crossproduct
 648                         }
 649                         else
 650                         {
 651                                 CrossProduct(other_start->edgedirs[nedge2].v, trace_start->edgedirs[nedge1].v, startplane);
 652                                 if (VectorLength2(startplane) < COLLISION_EDGECROSS_MINLENGTH2)
 653                                         continue; // degenerate crossproduct
 654                                 CrossProduct(other_end->edgedirs[nedge2].v, trace_end->edgedirs[nedge1].v, endplane);
 655                                 if (VectorLength2(endplane) < COLLISION_EDGECROSS_MINLENGTH2)
 656                                         continue; // degenerate crossproduct
 657                         }
 658                         VectorNormalize(startplane);
 659                         VectorNormalize(endplane);
 660                 }
 661                 startplane[3] = furthestplanedist_float(startplane, other_start->points, othernumpoints);
 662                 endplane[3] = furthestplanedist_float(startplane, other_end->points, othernumpoints);
 663                 startdist = nearestplanedist_float(startplane, trace_start->points, tracenumpoints) - startplane[3] - collision_startnudge.value;
 664                 enddist = nearestplanedist_float(endplane, trace_end->points, tracenumpoints) - endplane[3] - collision_endnudge.value;
 665                 //Con_Printf("%c%i: startdist = %f, enddist = %f, startdist / (startdist - enddist) = %f\n", nplane2 != nplane ? 'b' : 'a', nplane2, startdist, enddist, startdist / (startdist - enddist));
 666
 667                 // aside from collisions, this is also used for error correction
 668                 if (startdist < collision_impactnudge.value && nplane < numplanes1 && (startdepth < startdist || startdepth == 1))
 669                 {
 670                         startdepth = startdist;
 671                         VectorCopy(startplane, startdepthnormal);
 672                 }
 673
 674                 if (startdist > enddist)
 675                 {
 676                         // moving into brush
 677                         if (enddist >= collision_enternudge.value)
 678                                 return;
 679                         if (startdist > 0)
 680                         {
 681                                 // enter
 682                                 imove = 1 / (startdist - enddist);
 683                                 f = (startdist - collision_enternudge.value) * imove;
 684                                 if (f < 0)
 685                                         f = 0;
 686                                 // check if this will reduce the collision time range
 687                                 if (enterfrac < f)
 688                                 {
 689                                         // reduced collision time range
 690                                         enterfrac = f;
 691                                         // if the collision time range is now empty, no collision
 692                                         if (enterfrac > leavefrac)
 693                                                 return;
 694                                         // if the collision would be further away than the trace's
 695                                         // existing collision data, we don't care about this
 696                                         // collision
 697                                         if (enterfrac > trace->realfraction)
 698                                                 return;
 699                                         // calculate the nudged fraction and impact normal we'll
 700                                         // need if we accept this collision later
 701                                         enterfrac2 = (startdist - collision_impactnudge.value) * imove;
 702                                         ie = 1.0f - enterfrac;
 703                                         newimpactplane[0] = startplane[0] * ie + endplane[0] * enterfrac;
 704                                         newimpactplane[1] = startplane[1] * ie + endplane[1] * enterfrac;
 705                                         newimpactplane[2] = startplane[2] * ie + endplane[2] * enterfrac;
 706                                         newimpactplane[3] = startplane[3] * ie + endplane[3] * enterfrac;
 707                                         if (nplane < numplanes1)
 708                                         {
 709                                                 // use the plane from other
 710                                                 nplane2 = nplane;
 711                                                 hitq3surfaceflags = other_start->planes[nplane2].q3surfaceflags;
 712                                                 hittexture = other_start->planes[nplane2].texture;
 713                                         }
 714                                         else if (nplane < numplanes2)
 715                                         {
 716                                                 // use the plane from trace
 717                                                 nplane2 = nplane - numplanes1;
 718                                                 hitq3surfaceflags = trace_start->planes[nplane2].q3surfaceflags;
 719                                                 hittexture = trace_start->planes[nplane2].texture;
 720                                         }
 721                                         else
 722                                         {
 723                                                 hitq3surfaceflags = other_start->q3surfaceflags;
 724                                                 hittexture = other_start->texture;
 725                                         }
 726                                 }
 727                         }
 728                 }
 729                 else
 730                 {
 731                         // moving out of brush
 732                         if (startdist > 0)
 733                                 return;
 734                         if (enddist > 0)
 735                         {
 736                                 // leave
 737                                 f = (startdist + collision_leavenudge.value) / (startdist - enddist);
 738                                 if (f > 1)
 739                                         f = 1;
 740                                 // check if this will reduce the collision time range
 741                                 if (leavefrac > f)
 742                                 {
 743                                         // reduced collision time range
 744                                         leavefrac = f;
 745                                         // if the collision time range is now empty, no collision
 746                                         if (enterfrac > leavefrac)
 747                                                 return;
 748                                 }
 749                         }
 750                 }
 751         }
 752
 753         // at this point we know the trace overlaps the brush because it was not
 754         // rejected at any point in the loop above
 755
 756         // see if the trace started outside the brush or not
 757         if (enterfrac > -1)
 758         {
 759                 // started outside, and overlaps, therefore there is a collision here
 760                 // store out the impact information
 761                 if (trace->hitsupercontentsmask & other_start->supercontents)
 762                 {
 763                         trace->hitsupercontents = other_start->supercontents;
 764                         trace->hitq3surfaceflags = hitq3surfaceflags;
 765                         trace->hittexture = hittexture;
 766                         trace->realfraction = bound(0, enterfrac, 1);
 767                         trace->fraction = bound(0, enterfrac2, 1);
 768                         if (collision_prefernudgedfraction.integer)
 769                                 trace->realfraction = trace->fraction;
 770                         VectorCopy(newimpactplane, trace->plane.normal);
 771                         trace->plane.dist = newimpactplane[3];
 772                 }
 773         }
 774         else
 775         {
 776                 // started inside, update startsolid and friends
 777                 trace->startsupercontents |= other_start->supercontents;
 778                 if (trace->hitsupercontentsmask & other_start->supercontents)
 779                 {
 780                         trace->startsolid = true;
 781                         if (leavefrac < 1)
 782                                 trace->allsolid = true;
 783                         VectorCopy(newimpactplane, trace->plane.normal);
 784                         trace->plane.dist = newimpactplane[3];
 785                         if (trace->startdepth > startdepth)
 786                         {
 787                                 trace->startdepth = startdepth;
 788                                 VectorCopy(startdepthnormal, trace->startdepthnormal);
 789                         }
 790                 }
 791         }
 792 }
 793
 794 // NOTE: start and end of each brush pair must have same numplanes/numpoints
 795 void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const colbrushf_t *other_start, const colbrushf_t *other_end)
 796 {
 797         int nplane, hitq3surfaceflags = 0;
 798         int numplanes = other_start->numplanes;
 799         vec_t enterfrac = -1, leavefrac = 1, startdist, enddist, ie, f, imove, enterfrac2 = -1;
 800         vec4_t startplane;
 801         vec4_t endplane;
 802         vec4_t newimpactplane;
 803         const texture_t *hittexture = NULL;
 804         vec_t startdepth = 1;
 805         vec3_t startdepthnormal;
 806
 807         if (collision_debug_tracelineasbox.integer)
 808         {
 809                 colboxbrushf_t thisbrush_start, thisbrush_end;
 810                 Collision_BrushForBox(&thisbrush_start, linestart, linestart, 0, 0, NULL);
 811                 Collision_BrushForBox(&thisbrush_end, lineend, lineend, 0, 0, NULL);
 812                 Collision_TraceBrushBrushFloat(trace, &thisbrush_start.brush, &thisbrush_end.brush, other_start, other_end);
 813                 return;
 814         }
 815
 816         VectorClear(startdepthnormal);
 817         Vector4Clear(newimpactplane);
 818
 819         // Separating Axis Theorem:
 820         // if a supporting vector (plane normal) can be found that separates two
 821         // objects, they are not colliding.
 822         //
 823         // Minkowski Sum:
 824         // reduce the size of one object to a point while enlarging the other to
 825         // represent the space that point can not occupy.
 826         //
 827         // try every plane we can construct between the two brushes and measure
 828         // the distance between them.
 829         for (nplane = 0;nplane < numplanes;nplane++)
 830         {
 831                 VectorCopy(other_start->planes[nplane].normal, startplane);
 832                 startplane[3] = other_start->planes[nplane].dist;
 833                 VectorCopy(other_end->planes[nplane].normal, endplane);
 834                 endplane[3] = other_end->planes[nplane].dist;
 835                 startdist = DotProduct(linestart, startplane) - startplane[3] - collision_startnudge.value;
 836                 enddist = DotProduct(lineend, endplane) - endplane[3] - collision_endnudge.value;
 837                 //Con_Printf("%c%i: startdist = %f, enddist = %f, startdist / (startdist - enddist) = %f\n", nplane2 != nplane ? 'b' : 'a', nplane2, startdist, enddist, startdist / (startdist - enddist));
 838
 839                 // aside from collisions, this is also used for error correction
 840                 if (startdist < collision_impactnudge.value && (startdepth < startdist || startdepth == 1))
 841                 {
 842                         startdepth = startdist;
 843                         VectorCopy(startplane, startdepthnormal);
 844                 }
 845
 846                 if (startdist > enddist)
 847                 {
 848                         // moving into brush
 849                         if (enddist >= collision_enternudge.value)
 850                                 return;
 851                         if (startdist > 0)
 852                         {
 853                                 // enter
 854                                 imove = 1 / (startdist - enddist);
 855                                 f = (startdist - collision_enternudge.value) * imove;
 856                                 if (f < 0)
 857                                         f = 0;
 858                                 // check if this will reduce the collision time range
 859                                 if (enterfrac < f)
 860                                 {
 861                                         // reduced collision time range
 862                                         enterfrac = f;
 863                                         // if the collision time range is now empty, no collision
 864                                         if (enterfrac > leavefrac)
 865                                                 return;
 866                                         // if the collision would be further away than the trace's
 867                                         // existing collision data, we don't care about this
 868                                         // collision
 869                                         if (enterfrac > trace->realfraction)
 870                                                 return;
 871                                         // calculate the nudged fraction and impact normal we'll
 872                                         // need if we accept this collision later
 873                                         enterfrac2 = (startdist - collision_impactnudge.value) * imove;
 874                                         ie = 1.0f - enterfrac;
 875                                         newimpactplane[0] = startplane[0] * ie + endplane[0] * enterfrac;
 876                                         newimpactplane[1] = startplane[1] * ie + endplane[1] * enterfrac;
 877                                         newimpactplane[2] = startplane[2] * ie + endplane[2] * enterfrac;
 878                                         newimpactplane[3] = startplane[3] * ie + endplane[3] * enterfrac;
 879                                         hitq3surfaceflags = other_start->planes[nplane].q3surfaceflags;
 880                                         hittexture = other_start->planes[nplane].texture;
 881                                 }
 882                         }
 883                 }
 884                 else
 885                 {
 886                         // moving out of brush
 887                         if (startdist > 0)
 888                                 return;
 889                         if (enddist > 0)
 890                         {
 891                                 // leave
 892                                 f = (startdist + collision_leavenudge.value) / (startdist - enddist);
 893                                 if (f > 1)
 894                                         f = 1;
 895                                 // check if this will reduce the collision time range
 896                                 if (leavefrac > f)
 897                                 {
 898                                         // reduced collision time range
 899                                         leavefrac = f;
 900                                         // if the collision time range is now empty, no collision
 901                                         if (enterfrac > leavefrac)
 902                                                 return;
 903                                 }
 904                         }
 905                 }
 906         }
 907
 908         // at this point we know the trace overlaps the brush because it was not
 909         // rejected at any point in the loop above
 910
 911         // see if the trace started outside the brush or not
 912         if (enterfrac > -1)
 913         {
 914                 // started outside, and overlaps, therefore there is a collision here
 915                 // store out the impact information
 916                 if (trace->hitsupercontentsmask & other_start->supercontents)
 917                 {
 918                         trace->hitsupercontents = other_start->supercontents;
 919                         trace->hitq3surfaceflags = hitq3surfaceflags;
 920                         trace->hittexture = hittexture;
 921                         trace->realfraction = bound(0, enterfrac, 1);
 922                         trace->fraction = bound(0, enterfrac2, 1);
 923                         if (collision_prefernudgedfraction.integer)
 924                                 trace->realfraction = trace->fraction;
 925                         VectorCopy(newimpactplane, trace->plane.normal);
 926                         trace->plane.dist = newimpactplane[3];
 927                 }
 928         }
 929         else
 930         {
 931                 // started inside, update startsolid and friends
 932                 trace->startsupercontents |= other_start->supercontents;
 933                 if (trace->hitsupercontentsmask & other_start->supercontents)
 934                 {
 935                         trace->startsolid = true;
 936                         if (leavefrac < 1)
 937                                 trace->allsolid = true;
 938                         VectorCopy(newimpactplane, trace->plane.normal);
 939                         trace->plane.dist = newimpactplane[3];
 940                         if (trace->startdepth > startdepth)
 941                         {
 942                                 trace->startdepth = startdepth;
 943                                 VectorCopy(startdepthnormal, trace->startdepthnormal);
 944                         }
 945                 }
 946         }
 947 }
 948
 949 qboolean Collision_PointInsideBrushFloat(const vec3_t point, const colbrushf_t *brush)
 950 {
 951         int nplane;
 952         const colplanef_t *plane;
 953
 954         if (!BoxesOverlap(point, point, brush->mins, brush->maxs))
 955                 return false;
 956         for (nplane = 0, plane = brush->planes;nplane < brush->numplanes;nplane++, plane++)
 957                 if (DotProduct(plane->normal, point) > plane->dist)
 958                         return false;
 959         return true;
 960 }
 961
 962 void Collision_TracePointBrushFloat(trace_t *trace, const vec3_t point, const colbrushf_t *thatbrush)
 963 {
 964         if (!Collision_PointInsideBrushFloat(point, thatbrush))
 965                 return;
 966
 967         trace->startsupercontents |= thatbrush->supercontents;
 968         if (trace->hitsupercontentsmask & thatbrush->supercontents)
 969         {
 970                 trace->startsolid = true;
 971                 trace->allsolid = true;
 972         }
 973 }
 974
 975 static void Collision_SnapCopyPoints(int numpoints, const colpointf_t *in, colpointf_t *out, float fractionprecision, float invfractionprecision)
 976 {
 977         int i;
 978         for (i = 0;i < numpoints;i++)
 979         {
 980                 out[i].v[0] = floor(in[i].v[0] * fractionprecision + 0.5f) * invfractionprecision;
 981                 out[i].v[1] = floor(in[i].v[1] * fractionprecision + 0.5f) * invfractionprecision;
 982                 out[i].v[2] = floor(in[i].v[2] * fractionprecision + 0.5f) * invfractionprecision;
 983         }
 984 }
 985
 986 void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, const texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs)
 987 {
 988         int i;
 989         colpointf_t points[3];
 990         colpointf_t edgedirs[3];
 991         colplanef_t planes[5];
 992         colbrushf_t brush;
 993         memset(&brush, 0, sizeof(brush));
 994         brush.isaabb = false;
 995         brush.hasaabbplanes = false;
 996         brush.numpoints = 3;
 997         brush.numedgedirs = 3;
 998         brush.numplanes = 5;
 999         brush.points = points;
1000         brush.edgedirs = edgedirs;
1001         brush.planes = planes;
1002         brush.supercontents = supercontents;
1003         brush.q3surfaceflags = q3surfaceflags;
1004         brush.texture = texture;
1005         for (i = 0;i < brush.numplanes;i++)
1006         {
1007                 brush.planes[i].q3surfaceflags = q3surfaceflags;
1008                 brush.planes[i].texture = texture;
1009         }
1010         if(stride > 0)
1011         {
1012                 int k, cnt, tri;
1013                 cnt = (numtriangles + stride - 1) / stride;
1014                 for(i = 0; i < cnt; ++i)
1015                 {
1016                         if(BoxesOverlap(bbox6f + i * 6, bbox6f + i * 6 + 3, segmentmins, segmentmaxs))
1017                         {
1018                                 for(k = 0; k < stride; ++k)
1019                                 {
1020                                         tri = i * stride + k;
1021                                         if(tri >= numtriangles)
1022                                                 break;
1023                                         VectorCopy(vertex3f + element3i[tri * 3 + 0] * 3, points[0].v);
1024                                         VectorCopy(vertex3f + element3i[tri * 3 + 1] * 3, points[1].v);
1025                                         VectorCopy(vertex3f + element3i[tri * 3 + 2] * 3, points[2].v);
1026                                         Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1027                                         Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1028                                         Collision_CalcPlanesForTriangleBrushFloat(&brush);
1029                                         //Collision_PrintBrushAsQHull(&brush, "brush");
1030                                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1031                                 }
1032                         }
1033                 }
1034         }
1035         else if(stride == 0)
1036         {
1037                 for (i = 0;i < numtriangles;i++, element3i += 3)
1038                 {
1039                         if (TriangleOverlapsBox(vertex3f + element3i[0]*3, vertex3f + element3i[1]*3, vertex3f + element3i[2]*3, segmentmins, segmentmaxs))
1040                         {
1041                                 VectorCopy(vertex3f + element3i[0] * 3, points[0].v);
1042                                 VectorCopy(vertex3f + element3i[1] * 3, points[1].v);
1043                                 VectorCopy(vertex3f + element3i[2] * 3, points[2].v);
1044                                 Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1045                                 Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1046                                 Collision_CalcPlanesForTriangleBrushFloat(&brush);
1047                                 //Collision_PrintBrushAsQHull(&brush, "brush");
1048                                 Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1049                         }
1050                 }
1051         }
1052         else
1053         {
1054                 for (i = 0;i < numtriangles;i++, element3i += 3)
1055                 {
1056                         VectorCopy(vertex3f + element3i[0] * 3, points[0].v);
1057                         VectorCopy(vertex3f + element3i[1] * 3, points[1].v);
1058                         VectorCopy(vertex3f + element3i[2] * 3, points[2].v);
1059                         Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1060                         Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1061                         Collision_CalcPlanesForTriangleBrushFloat(&brush);
1062                         //Collision_PrintBrushAsQHull(&brush, "brush");
1063                         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1064                 }
1065         }
1066 }
1067
1068 void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, int stride, float *bbox6f, int supercontents, int q3surfaceflags, const texture_t *texture, const vec3_t segmentmins, const vec3_t segmentmaxs)
1069 {
1070         int i;
1071         // FIXME: snap vertices?
1072         if(stride > 0)
1073         {
1074                 int k, cnt, tri;
1075                 cnt = (numtriangles + stride - 1) / stride;
1076                 for(i = 0; i < cnt; ++i)
1077                 {
1078                         if(BoxesOverlap(bbox6f + i * 6, bbox6f + i * 6 + 3, segmentmins, segmentmaxs))
1079                         {
1080                                 for(k = 0; k < stride; ++k)
1081                                 {
1082                                         tri = i * stride + k;
1083                                         if(tri >= numtriangles)
1084                                                 break;
1085                                         Collision_TraceLineTriangleFloat(trace, linestart, lineend, vertex3f + element3i[tri * 3 + 0] * 3, vertex3f + element3i[tri * 3 + 1] * 3, vertex3f + element3i[tri * 3 + 2] * 3, supercontents, q3surfaceflags, texture);
1086                                 }
1087                         }
1088                 }
1089         }
1090         else
1091         {
1092                 for (i = 0;i < numtriangles;i++, element3i += 3)
1093                         Collision_TraceLineTriangleFloat(trace, linestart, lineend, vertex3f + element3i[0] * 3, vertex3f + element3i[1] * 3, vertex3f + element3i[2] * 3, supercontents, q3surfaceflags, texture);
1094         }
1095 }
1096
1097 void Collision_TraceBrushTriangleFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const float *v0, const float *v1, const float *v2, int supercontents, int q3surfaceflags, const texture_t *texture)
1098 {
1099         int i;
1100         colpointf_t points[3];
1101         colpointf_t edgedirs[3];
1102         colplanef_t planes[5];
1103         colbrushf_t brush;
1104         memset(&brush, 0, sizeof(brush));
1105         brush.isaabb = false;
1106         brush.hasaabbplanes = false;
1107         brush.numpoints = 3;
1108         brush.numedgedirs = 3;
1109         brush.numplanes = 5;
1110         brush.points = points;
1111         brush.edgedirs = edgedirs;
1112         brush.planes = planes;
1113         brush.supercontents = supercontents;
1114         brush.q3surfaceflags = q3surfaceflags;
1115         brush.texture = texture;
1116         for (i = 0;i < brush.numplanes;i++)
1117         {
1118                 brush.planes[i].q3surfaceflags = q3surfaceflags;
1119                 brush.planes[i].texture = texture;
1120         }
1121         VectorCopy(v0, points[0].v);
1122         VectorCopy(v1, points[1].v);
1123         VectorCopy(v2, points[2].v);
1124         Collision_SnapCopyPoints(brush.numpoints, points, points, COLLISION_SNAPSCALE, COLLISION_SNAP);
1125         Collision_CalcEdgeDirsForPolygonBrushFloat(&brush);
1126         Collision_CalcPlanesForTriangleBrushFloat(&brush);
1127         //Collision_PrintBrushAsQHull(&brush, "brush");
1128         Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &brush, &brush);
1129 }
1130
1131 void Collision_BrushForBox(colboxbrushf_t *boxbrush, const vec3_t mins, const vec3_t maxs, int supercontents, int q3surfaceflags, const texture_t *texture)
1132 {
1133         int i;
1134         memset(boxbrush, 0, sizeof(*boxbrush));
1135         boxbrush->brush.isaabb = true;
1136         boxbrush->brush.hasaabbplanes = true;
1137         boxbrush->brush.points = boxbrush->points;
1138         boxbrush->brush.edgedirs = boxbrush->edgedirs;
1139         boxbrush->brush.planes = boxbrush->planes;
1140         boxbrush->brush.supercontents = supercontents;
1141         boxbrush->brush.q3surfaceflags = q3surfaceflags;
1142         boxbrush->brush.texture = texture;
1143         if (VectorCompare(mins, maxs))
1144         {
1145                 // point brush
1146                 boxbrush->brush.numpoints = 1;
1147                 boxbrush->brush.numedgedirs = 0;
1148                 boxbrush->brush.numplanes = 0;
1149                 VectorCopy(mins, boxbrush->brush.points[0].v);
1150         }
1151         else
1152         {
1153                 boxbrush->brush.numpoints = 8;
1154                 boxbrush->brush.numedgedirs = 3;
1155                 boxbrush->brush.numplanes = 6;
1156                 // there are 8 points on a box
1157                 // there are 3 edgedirs on a box (both signs are tested in collision)
1158                 // there are 6 planes on a box
1159                 VectorSet(boxbrush->brush.points[0].v, mins[0], mins[1], mins[2]);
1160                 VectorSet(boxbrush->brush.points[1].v, maxs[0], mins[1], mins[2]);
1161                 VectorSet(boxbrush->brush.points[2].v, mins[0], maxs[1], mins[2]);
1162                 VectorSet(boxbrush->brush.points[3].v, maxs[0], maxs[1], mins[2]);
1163                 VectorSet(boxbrush->brush.points[4].v, mins[0], mins[1], maxs[2]);
1164                 VectorSet(boxbrush->brush.points[5].v, maxs[0], mins[1], maxs[2]);
1165                 VectorSet(boxbrush->brush.points[6].v, mins[0], maxs[1], maxs[2]);
1166                 VectorSet(boxbrush->brush.points[7].v, maxs[0], maxs[1], maxs[2]);
1167                 VectorSet(boxbrush->brush.edgedirs[0].v, 1, 0, 0);
1168                 VectorSet(boxbrush->brush.edgedirs[1].v, 0, 1, 0);
1169                 VectorSet(boxbrush->brush.edgedirs[2].v, 0, 0, 1);
1170                 VectorSet(boxbrush->brush.planes[0].normal, -1,  0,  0);boxbrush->brush.planes[0].dist = -mins[0];
1171                 VectorSet(boxbrush->brush.planes[1].normal,  1,  0,  0);boxbrush->brush.planes[1].dist =  maxs[0];
1172                 VectorSet(boxbrush->brush.planes[2].normal,  0, -1,  0);boxbrush->brush.planes[2].dist = -mins[1];
1173                 VectorSet(boxbrush->brush.planes[3].normal,  0,  1,  0);boxbrush->brush.planes[3].dist =  maxs[1];
1174                 VectorSet(boxbrush->brush.planes[4].normal,  0,  0, -1);boxbrush->brush.planes[4].dist = -mins[2];
1175                 VectorSet(boxbrush->brush.planes[5].normal,  0,  0,  1);boxbrush->brush.planes[5].dist =  maxs[2];
1176                 for (i = 0;i < 6;i++)
1177                 {
1178                         boxbrush->brush.planes[i].q3surfaceflags = q3surfaceflags;
1179                         boxbrush->brush.planes[i].texture = texture;
1180                 }
1181         }
1182         boxbrush->brush.supercontents = supercontents;
1183         boxbrush->brush.q3surfaceflags = q3surfaceflags;
1184         boxbrush->brush.texture = texture;
1185         VectorSet(boxbrush->brush.mins, mins[0] - 1, mins[1] - 1, mins[2] - 1);
1186         VectorSet(boxbrush->brush.maxs, maxs[0] + 1, maxs[1] + 1, maxs[2] + 1);
1187         //Collision_ValidateBrush(&boxbrush->brush);
1188 }
1189
1190 //pseudocode for detecting line/sphere overlap without calculating an impact point
1191 //linesphereorigin = sphereorigin - linestart;linediff = lineend - linestart;linespherefrac = DotProduct(linesphereorigin, linediff) / DotProduct(linediff, linediff);return VectorLength2(linesphereorigin - bound(0, linespherefrac, 1) * linediff) >= sphereradius*sphereradius;
1192
1193 // LordHavoc: currently unused, but tested
1194 // note: this can be used for tracing a moving sphere vs a stationary sphere,
1195 // by simply adding the moving sphere's radius to the sphereradius parameter,
1196 // all the results are correct (impactpoint, impactnormal, and fraction)
1197 float Collision_ClipTrace_Line_Sphere(double *linestart, double *lineend, double *sphereorigin, double sphereradius, double *impactpoint, double *impactnormal)
1198 {
1199         double dir[3], scale, v[3], deviationdist2, impactdist, linelength;
1200         // make sure the impactpoint and impactnormal are valid even if there is
1201         // no collision
1202         VectorCopy(lineend, impactpoint);
1203         VectorClear(impactnormal);
1204         // calculate line direction
1205         VectorSubtract(lineend, linestart, dir);
1206         // normalize direction
1207         linelength = VectorLength(dir);
1208         if (linelength)
1209         {
1210                 scale = 1.0 / linelength;
1211                 VectorScale(dir, scale, dir);
1212         }
1213         // this dotproduct calculates the distance along the line at which the
1214         // sphere origin is (nearest point to the sphere origin on the line)
1215         impactdist = DotProduct(sphereorigin, dir) - DotProduct(linestart, dir);
1216         // calculate point on line at that distance, and subtract the
1217         // sphereorigin from it, so we have a vector to measure for the distance
1218         // of the line from the sphereorigin (deviation, how off-center it is)
1219         VectorMA(linestart, impactdist, dir, v);
1220         VectorSubtract(v, sphereorigin, v);
1221         deviationdist2 = sphereradius * sphereradius - VectorLength2(v);
1222         // if squared offset length is outside the squared sphere radius, miss
1223         if (deviationdist2 < 0)
1224                 return 1; // miss (off to the side)
1225         // nudge back to find the correct impact distance
1226         impactdist -= sqrt(deviationdist2);
1227         if (impactdist >= linelength)
1228                 return 1; // miss (not close enough)
1229         if (impactdist < 0)
1230                 return 1; // miss (linestart is past or inside sphere)
1231         // calculate new impactpoint
1232         VectorMA(linestart, impactdist, dir, impactpoint);
1233         // calculate impactnormal (surface normal at point of impact)
1234         VectorSubtract(impactpoint, sphereorigin, impactnormal);
1235         // normalize impactnormal
1236         VectorNormalize(impactnormal);
1237         // return fraction of movement distance
1238         return impactdist / linelength;
1239 }
1240
1241 void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const float *point0, const float *point1, const float *point2, int supercontents, int q3surfaceflags, const texture_t *texture)
1242 {
1243 #if 1
1244         // more optimized
1245         float d1, d2, d, f, impact[3], edgenormal[3], faceplanenormal[3], faceplanedist, faceplanenormallength2, edge01[3], edge21[3], edge02[3];
1246
1247         // this function executes:
1248         // 32 ops when line starts behind triangle
1249         // 38 ops when line ends infront of triangle
1250         // 43 ops when line fraction is already closer than this triangle
1251         // 72 ops when line is outside edge 01
1252         // 92 ops when line is outside edge 21
1253         // 115 ops when line is outside edge 02
1254         // 123 ops when line impacts triangle and updates trace results
1255
1256         // this code is designed for clockwise triangles, conversion to
1257         // counterclockwise would require swapping some things around...
1258         // it is easier to simply swap the point0 and point2 parameters to this
1259         // function when calling it than it is to rewire the internals.
1260
1261         // calculate the faceplanenormal of the triangle, this represents the front side
1262         // 15 ops
1263         VectorSubtract(point0, point1, edge01);
1264         VectorSubtract(point2, point1, edge21);
1265         CrossProduct(edge01, edge21, faceplanenormal);
1266         // there's no point in processing a degenerate triangle (GIGO - Garbage In, Garbage Out)
1267         // 6 ops
1268         faceplanenormallength2 = DotProduct(faceplanenormal, faceplanenormal);
1269         if (faceplanenormallength2 < 0.0001f)
1270                 return;
1271         // calculate the distance
1272         // 5 ops
1273         faceplanedist = DotProduct(point0, faceplanenormal);
1274
1275         // if start point is on the back side there is no collision
1276         // (we don't care about traces going through the triangle the wrong way)
1277
1278         // calculate the start distance
1279         // 6 ops
1280         d1 = DotProduct(faceplanenormal, linestart);
1281         if (d1 <= faceplanedist)
1282                 return;
1283
1284         // calculate the end distance
1285         // 6 ops
1286         d2 = DotProduct(faceplanenormal, lineend);
1287         // if both are in front, there is no collision
1288         if (d2 >= faceplanedist)
1289                 return;
1290
1291         // from here on we know d1 is >= 0 and d2 is < 0
1292         // this means the line starts infront and ends behind, passing through it
1293
1294         // calculate the recipricol of the distance delta,
1295         // so we can use it multiple times cheaply (instead of division)
1296         // 2 ops
1297         d = 1.0f / (d1 - d2);
1298         // calculate the impact fraction by taking the start distance (> 0)
1299         // and subtracting the face plane distance (this is the distance of the
1300         // triangle along that same normal)
1301         // then multiply by the recipricol distance delta
1302         // 2 ops
1303         f = (d1 - faceplanedist) * d;
1304         // skip out if this impact is further away than previous ones
1305         // 1 ops
1306         if (f > trace->realfraction)
1307                 return;
1308         // calculate the perfect impact point for classification of insidedness
1309         // 9 ops
1310         impact[0] = linestart[0] + f * (lineend[0] - linestart[0]);
1311         impact[1] = linestart[1] + f * (lineend[1] - linestart[1]);
1312         impact[2] = linestart[2] + f * (lineend[2] - linestart[2]);
1313
1314         // calculate the edge normal and reject if impact is outside triangle
1315         // (an edge normal faces away from the triangle, to get the desired normal
1316         //  a crossproduct with the faceplanenormal is used, and because of the way
1317         // the insidedness comparison is written it does not need to be normalized)
1318
1319         // first use the two edges from the triangle plane math
1320         // the other edge only gets calculated if the point survives that long
1321
1322         // 20 ops
1323         CrossProduct(edge01, faceplanenormal, edgenormal);
1324         if (DotProduct(impact, edgenormal) > DotProduct(point1, edgenormal))
1325                 return;
1326
1327         // 20 ops
1328         CrossProduct(faceplanenormal, edge21, edgenormal);
1329         if (DotProduct(impact, edgenormal) > DotProduct(point2, edgenormal))
1330                 return;
1331
1332         // 23 ops
1333         VectorSubtract(point0, point2, edge02);
1334         CrossProduct(faceplanenormal, edge02, edgenormal);
1335         if (DotProduct(impact, edgenormal) > DotProduct(point0, edgenormal))
1336                 return;
1337
1338         // 8 ops (rare)
1339
1340         // store the new trace fraction
1341         trace->realfraction = f;
1342
1343         // calculate a nudged fraction to keep it out of the surface
1344         // (the main fraction remains perfect)
1345         trace->fraction = f - collision_impactnudge.value * d;
1346
1347         if (collision_prefernudgedfraction.integer)
1348                 trace->realfraction = trace->fraction;
1349
1350         // store the new trace plane (because collisions only happen from
1351         // the front this is always simply the triangle normal, never flipped)
1352         d = 1.0 / sqrt(faceplanenormallength2);
1353         VectorScale(faceplanenormal, d, trace->plane.normal);
1354         trace->plane.dist = faceplanedist * d;
1355
1356         trace->hitsupercontents = supercontents;
1357         trace->hitq3surfaceflags = q3surfaceflags;
1358         trace->hittexture = texture;
1359 #else
1360         float d1, d2, d, f, fnudged, impact[3], edgenormal[3], faceplanenormal[3], faceplanedist, edge[3];
1361
1362         // this code is designed for clockwise triangles, conversion to
1363         // counterclockwise would require swapping some things around...
1364         // it is easier to simply swap the point0 and point2 parameters to this
1365         // function when calling it than it is to rewire the internals.
1366
1367         // calculate the unnormalized faceplanenormal of the triangle,
1368         // this represents the front side
1369         TriangleNormal(point0, point1, point2, faceplanenormal);
1370         // there's no point in processing a degenerate triangle
1371         // (GIGO - Garbage In, Garbage Out)
1372         if (DotProduct(faceplanenormal, faceplanenormal) < 0.0001f)
1373                 return;
1374         // calculate the unnormalized distance
1375         faceplanedist = DotProduct(point0, faceplanenormal);
1376
1377         // calculate the unnormalized start distance
1378         d1 = DotProduct(faceplanenormal, linestart) - faceplanedist;
1379         // if start point is on the back side there is no collision
1380         // (we don't care about traces going through the triangle the wrong way)
1381         if (d1 <= 0)
1382                 return;
1383
1384         // calculate the unnormalized end distance
1385         d2 = DotProduct(faceplanenormal, lineend) - faceplanedist;
1386         // if both are in front, there is no collision
1387         if (d2 >= 0)
1388                 return;
1389
1390         // from here on we know d1 is >= 0 and d2 is < 0
1391         // this means the line starts infront and ends behind, passing through it
1392
1393         // calculate the recipricol of the distance delta,
1394         // so we can use it multiple times cheaply (instead of division)
1395         d = 1.0f / (d1 - d2);
1396         // calculate the impact fraction by taking the start distance (> 0)
1397         // and subtracting the face plane distance (this is the distance of the
1398         // triangle along that same normal)
1399         // then multiply by the recipricol distance delta
1400         f = d1 * d;
1401         // skip out if this impact is further away than previous ones
1402         if (f > trace->realfraction)
1403                 return;
1404         // calculate the perfect impact point for classification of insidedness
1405         impact[0] = linestart[0] + f * (lineend[0] - linestart[0]);
1406         impact[1] = linestart[1] + f * (lineend[1] - linestart[1]);
1407         impact[2] = linestart[2] + f * (lineend[2] - linestart[2]);
1408
1409         // calculate the edge normal and reject if impact is outside triangle
1410         // (an edge normal faces away from the triangle, to get the desired normal
1411         //  a crossproduct with the faceplanenormal is used, and because of the way
1412         // the insidedness comparison is written it does not need to be normalized)
1413
1414         VectorSubtract(point2, point0, edge);
1415         CrossProduct(edge, faceplanenormal, edgenormal);
1416         if (DotProduct(impact, edgenormal) > DotProduct(point0, edgenormal))
1417                 return;
1418
1419         VectorSubtract(point0, point1, edge);
1420         CrossProduct(edge, faceplanenormal, edgenormal);
1421         if (DotProduct(impact, edgenormal) > DotProduct(point1, edgenormal))
1422                 return;
1423
1424         VectorSubtract(point1, point2, edge);
1425         CrossProduct(edge, faceplanenormal, edgenormal);
1426         if (DotProduct(impact, edgenormal) > DotProduct(point2, edgenormal))
1427                 return;
1428
1429         // store the new trace fraction
1430         trace->realfraction = bound(0, f, 1);
1431
1432         // store the new trace plane (because collisions only happen from
1433         // the front this is always simply the triangle normal, never flipped)
1434         VectorNormalize(faceplanenormal);
1435         VectorCopy(faceplanenormal, trace->plane.normal);
1436         trace->plane.dist = DotProduct(point0, faceplanenormal);
1437
1438         // calculate the normalized start and end distances
1439         d1 = DotProduct(trace->plane.normal, linestart) - trace->plane.dist;
1440         d2 = DotProduct(trace->plane.normal, lineend) - trace->plane.dist;
1441
1442         // calculate a nudged fraction to keep it out of the surface
1443         // (the main fraction remains perfect)
1444         fnudged = (d1 - collision_impactnudge.value) / (d1 - d2);
1445         trace->fraction = bound(0, fnudged, 1);
1446
1447         // store the new trace endpos
1448         // not needed, it's calculated later when the trace is finished
1449         //trace->endpos[0] = linestart[0] + fnudged * (lineend[0] - linestart[0]);
1450         //trace->endpos[1] = linestart[1] + fnudged * (lineend[1] - linestart[1]);
1451         //trace->endpos[2] = linestart[2] + fnudged * (lineend[2] - linestart[2]);
1452         trace->hitsupercontents = supercontents;
1453         trace->hitq3surfaceflags = q3surfaceflags;
1454         trace->hittexture = texture;
1455 #endif
1456 }
1457
1458 void Collision_BoundingBoxOfBrushTraceSegment(const colbrushf_t *start, const colbrushf_t *end, vec3_t mins, vec3_t maxs, float startfrac, float endfrac)
1459 {
1460         int i;
1461         colpointf_t *ps, *pe;
1462         float tempstart[3], tempend[3];
1463         VectorLerp(start->points[0].v, startfrac, end->points[0].v, mins);
1464         VectorCopy(mins, maxs);
1465         for (i = 0, ps = start->points, pe = end->points;i < start->numpoints;i++, ps++, pe++)
1466         {
1467                 VectorLerp(ps->v, startfrac, pe->v, tempstart);
1468                 VectorLerp(ps->v, endfrac, pe->v, tempend);
1469                 mins[0] = min(mins[0], min(tempstart[0], tempend[0]));
1470                 mins[1] = min(mins[1], min(tempstart[1], tempend[1]));
1471                 mins[2] = min(mins[2], min(tempstart[2], tempend[2]));
1472                 maxs[0] = min(maxs[0], min(tempstart[0], tempend[0]));
1473                 maxs[1] = min(maxs[1], min(tempstart[1], tempend[1]));
1474                 maxs[2] = min(maxs[2], min(tempstart[2], tempend[2]));
1475         }
1476         mins[0] -= 1;
1477         mins[1] -= 1;
1478         mins[2] -= 1;
1479         maxs[0] += 1;
1480         maxs[1] += 1;
1481         maxs[2] += 1;
1482 }
1483
1484 //===========================================
1485
1486 static void Collision_TranslateBrush(const vec3_t shift, colbrushf_t *brush)
1487 {
1488         int i;
1489         // now we can transform the data
1490         for(i = 0; i < brush->numplanes; ++i)
1491         {
1492                 brush->planes[i].dist += DotProduct(shift, brush->planes[i].normal);
1493         }
1494         for(i = 0; i < brush->numpoints; ++i)
1495         {
1496                 VectorAdd(brush->points[i].v, shift, brush->points[i].v);
1497         }
1498         VectorAdd(brush->mins, shift, brush->mins);
1499         VectorAdd(brush->maxs, shift, brush->maxs);
1500 }
1501
1502 static void Collision_TransformBrush(const matrix4x4_t *matrix, colbrushf_t *brush)
1503 {
1504         int i;
1505         vec3_t v;
1506         // we're breaking any AABB properties here...
1507         brush->isaabb = false;
1508         brush->hasaabbplanes = false;
1509         // now we can transform the data
1510         for(i = 0; i < brush->numplanes; ++i)
1511         {
1512                 Matrix4x4_TransformPositivePlane(matrix, brush->planes[i].normal[0], brush->planes[i].normal[1], brush->planes[i].normal[2], brush->planes[i].dist, brush->planes[i].normal);
1513         }
1514         for(i = 0; i < brush->numedgedirs; ++i)
1515         {
1516                 Matrix4x4_Transform(matrix, brush->edgedirs[i].v, v);
1517                 VectorCopy(v, brush->edgedirs[i].v);
1518         }
1519         for(i = 0; i < brush->numpoints; ++i)
1520         {
1521                 Matrix4x4_Transform(matrix, brush->points[i].v, v);
1522                 VectorCopy(v, brush->points[i].v);
1523         }
1524         VectorCopy(brush->points[0].v, brush->mins);
1525         VectorCopy(brush->points[0].v, brush->maxs);
1526         for(i = 1; i < brush->numpoints; ++i)
1527         {
1528                 if(brush->points[i].v[0] < brush->mins[0]) brush->mins[0] = brush->points[i].v[0];
1529                 if(brush->points[i].v[1] < brush->mins[1]) brush->mins[1] = brush->points[i].v[1];
1530                 if(brush->points[i].v[2] < brush->mins[2]) brush->mins[2] = brush->points[i].v[2];
1531                 if(brush->points[i].v[0] > brush->maxs[0]) brush->maxs[0] = brush->points[i].v[0];
1532                 if(brush->points[i].v[1] > brush->maxs[1]) brush->maxs[1] = brush->points[i].v[1];
1533                 if(brush->points[i].v[2] > brush->maxs[2]) brush->maxs[2] = brush->points[i].v[2];
1534         }
1535 }
1536
1537 typedef struct collision_cachedtrace_parameters_s
1538 {
1539         dp_model_t *model;
1540         vec3_t end;
1541         vec3_t start;
1542         int hitsupercontentsmask;
1543         matrix4x4_t matrix;
1544 }
1545 collision_cachedtrace_parameters_t;
1546
1547 typedef struct collision_cachedtrace_s
1548 {
1549         qboolean valid;
1550         collision_cachedtrace_parameters_t p;
1551         trace_t result;
1552 }
1553 collision_cachedtrace_t;
1554
1555 static mempool_t *collision_cachedtrace_mempool;
1556 static collision_cachedtrace_t *collision_cachedtrace_array;
1557 static int collision_cachedtrace_firstfree;
1558 static int collision_cachedtrace_lastused;
1559 static int collision_cachedtrace_max;
1560 static int collision_cachedtrace_sequence;
1561 static int collision_cachedtrace_hashsize;
1562 static int *collision_cachedtrace_hash;
1563 static unsigned int *collision_cachedtrace_arrayfullhashindex;
1564 static unsigned int *collision_cachedtrace_arrayhashindex;
1565 static unsigned int *collision_cachedtrace_arraynext;
1566 static unsigned char *collision_cachedtrace_arrayused;
1567 static qboolean collision_cachedtrace_rebuildhash;
1568
1569 void Collision_Cache_Reset(qboolean resetlimits)
1570 {
1571         if (collision_cachedtrace_hash)
1572                 Mem_Free(collision_cachedtrace_hash);
1573         if (collision_cachedtrace_array)
1574                 Mem_Free(collision_cachedtrace_array);
1575         if (collision_cachedtrace_arrayfullhashindex)
1576                 Mem_Free(collision_cachedtrace_arrayfullhashindex);
1577         if (collision_cachedtrace_arrayhashindex)
1578                 Mem_Free(collision_cachedtrace_arrayhashindex);
1579         if (collision_cachedtrace_arraynext)
1580                 Mem_Free(collision_cachedtrace_arraynext);
1581         if (collision_cachedtrace_arrayused)
1582                 Mem_Free(collision_cachedtrace_arrayused);
1583         if (resetlimits || !collision_cachedtrace_max)
1584                 collision_cachedtrace_max = collision_cache.integer ? 128 : 1;
1585         collision_cachedtrace_firstfree = 1;
1586         collision_cachedtrace_lastused = 0;
1587         collision_cachedtrace_hashsize = collision_cachedtrace_max;
1588         collision_cachedtrace_array = (collision_cachedtrace_t *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(collision_cachedtrace_t));
1589         collision_cachedtrace_hash = (int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_hashsize * sizeof(int));
1590         collision_cachedtrace_arrayfullhashindex = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
1591         collision_cachedtrace_arrayhashindex = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
1592         collision_cachedtrace_arraynext = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
1593         collision_cachedtrace_arrayused = (unsigned char *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned char));
1594         collision_cachedtrace_sequence = 1;
1595         collision_cachedtrace_rebuildhash = false;
1596 }
1597
1598 void Collision_Cache_Init(mempool_t *mempool)
1599 {
1600         collision_cachedtrace_mempool = mempool;
1601         Collision_Cache_Reset(true);
1602 }
1603
1604 static void Collision_Cache_RebuildHash(void)
1605 {
1606         int index;
1607         int range = collision_cachedtrace_lastused + 1;
1608         int sequence = collision_cachedtrace_sequence;
1609         int firstfree = collision_cachedtrace_max;
1610         int lastused = 0;
1611         int *hash = collision_cachedtrace_hash;
1612         unsigned int hashindex;
1613         unsigned int *arrayhashindex = collision_cachedtrace_arrayhashindex;
1614         unsigned int *arraynext = collision_cachedtrace_arraynext;
1615         collision_cachedtrace_rebuildhash = false;
1616         memset(collision_cachedtrace_hash, 0, collision_cachedtrace_hashsize * sizeof(int));
1617         for (index = 1;index < range;index++)
1618         {
1619                 if (collision_cachedtrace_arrayused[index] == sequence)
1620                 {
1621                         hashindex = arrayhashindex[index];
1622                         arraynext[index] = hash[hashindex];
1623                         hash[hashindex] = index;
1624                         lastused = index;
1625                 }
1626                 else
1627                 {
1628                         if (firstfree > index)
1629                                 firstfree = index;
1630                         collision_cachedtrace_arrayused[index] = 0;
1631                 }
1632         }
1633         collision_cachedtrace_firstfree = firstfree;
1634         collision_cachedtrace_lastused = lastused;
1635 }
1636
1637 void Collision_Cache_NewFrame(void)
1638 {
1639         if (collision_cache.integer)
1640         {
1641                 if (collision_cachedtrace_max < 128)
1642                         Collision_Cache_Reset(true);
1643         }
1644         else
1645         {
1646                 if (collision_cachedtrace_max > 1)
1647                         Collision_Cache_Reset(true);
1648         }
1649         // rebuild hash if sequence would overflow byte, otherwise increment
1650         if (collision_cachedtrace_sequence == 255)
1651         {
1652                 Collision_Cache_RebuildHash();
1653                 collision_cachedtrace_sequence = 1;
1654         }
1655         else
1656         {
1657                 collision_cachedtrace_rebuildhash = true;
1658                 collision_cachedtrace_sequence++;
1659         }
1660 }
1661
1662 static unsigned int Collision_Cache_HashIndexForArray(unsigned int *array, unsigned int size)
1663 {
1664         unsigned int i;
1665         unsigned int hashindex = 0;
1666         // this is a super-cheesy checksum, designed only for speed
1667         for (i = 0;i < size;i++)
1668                 hashindex += array[i] * (1 + i);
1669         return hashindex;
1670 }
1671
1672 static collision_cachedtrace_t *Collision_Cache_Lookup(dp_model_t *model, const matrix4x4_t *matrix, const matrix4x4_t *inversematrix, const vec3_t start, const vec3_t end, int hitsupercontentsmask)
1673 {
1674         int hashindex = 0;
1675         unsigned int fullhashindex;
1676         int index = 0;
1677         int range;
1678         int sequence = collision_cachedtrace_sequence;
1679         int *hash = collision_cachedtrace_hash;
1680         unsigned int *arrayfullhashindex = collision_cachedtrace_arrayfullhashindex;
1681         unsigned int *arraynext = collision_cachedtrace_arraynext;
1682         collision_cachedtrace_t *cached = collision_cachedtrace_array + index;
1683         collision_cachedtrace_parameters_t params;
1684         // all non-cached traces use the same index
1685         if (!collision_cache.integer)
1686                 r_refdef.stats.collisioncache_traced++;
1687         else
1688         {
1689                 // cached trace lookup
1690                 memset(&params, 0, sizeof(params));
1691                 params.model = model;
1692                 VectorCopy(start, params.start);
1693                 VectorCopy(end,   params.end);
1694                 params.hitsupercontentsmask = hitsupercontentsmask;
1695                 params.matrix = *matrix;
1696                 fullhashindex = Collision_Cache_HashIndexForArray((unsigned int *)&params, sizeof(params) / sizeof(unsigned int));
1697                 hashindex = (int)(fullhashindex % (unsigned int)collision_cachedtrace_hashsize);
1698                 for (index = hash[hashindex];index;index = arraynext[index])
1699                 {
1700                         if (arrayfullhashindex[index] != fullhashindex)
1701                                 continue;
1702                         cached = collision_cachedtrace_array + index;
1703                         //if (memcmp(&cached->p, &params, sizeof(params)))
1704                         if (cached->p.model != params.model
1705                          || cached->p.end[0] != params.end[0]
1706                          || cached->p.end[1] != params.end[1]
1707                          || cached->p.end[2] != params.end[2]
1708                          || cached->p.start[0] != params.start[0]
1709                          || cached->p.start[1] != params.start[1]
1710                          || cached->p.start[2] != params.start[2]
1711                          || cached->p.hitsupercontentsmask != params.hitsupercontentsmask
1712                          || cached->p.matrix.m[0][0] != params.matrix.m[0][0]
1713                          || cached->p.matrix.m[0][1] != params.matrix.m[0][1]
1714                          || cached->p.matrix.m[0][2] != params.matrix.m[0][2]
1715                          || cached->p.matrix.m[0][3] != params.matrix.m[0][3]
1716                          || cached->p.matrix.m[1][0] != params.matrix.m[1][0]
1717                          || cached->p.matrix.m[1][1] != params.matrix.m[1][1]
1718                          || cached->p.matrix.m[1][2] != params.matrix.m[1][2]
1719                          || cached->p.matrix.m[1][3] != params.matrix.m[1][3]
1720                          || cached->p.matrix.m[2][0] != params.matrix.m[2][0]
1721                          || cached->p.matrix.m[2][1] != params.matrix.m[2][1]
1722                          || cached->p.matrix.m[2][2] != params.matrix.m[2][2]
1723                          || cached->p.matrix.m[2][3] != params.matrix.m[2][3]
1724                          || cached->p.matrix.m[3][0] != params.matrix.m[3][0]
1725                          || cached->p.matrix.m[3][1] != params.matrix.m[3][1]
1726                          || cached->p.matrix.m[3][2] != params.matrix.m[3][2]
1727                          || cached->p.matrix.m[3][3] != params.matrix.m[3][3]
1728                         )
1729                                 continue;
1730                         // found a matching trace in the cache
1731                         r_refdef.stats.collisioncache_cached++;
1732                         cached->valid = true;
1733                         collision_cachedtrace_arrayused[index] = collision_cachedtrace_sequence;
1734                         return cached;
1735                 }
1736                 r_refdef.stats.collisioncache_traced++;
1737                 // find an unused cache entry
1738                 for (index = collision_cachedtrace_firstfree, range = collision_cachedtrace_max;index < range;index++)
1739                         if (collision_cachedtrace_arrayused[index] == 0)
1740                                 break;
1741                 if (index == range)
1742                 {
1743                         // all claimed, but probably some are stale...
1744                         for (index = 1, range = collision_cachedtrace_max;index < range;index++)
1745                                 if (collision_cachedtrace_arrayused[index] != sequence)
1746                                         break;
1747                         if (index < range)
1748                         {
1749                                 // found a stale one, rebuild the hash
1750                                 Collision_Cache_RebuildHash();
1751                         }
1752                         else
1753                         {
1754                                 // we need to grow the cache
1755                                 collision_cachedtrace_max *= 2;
1756                                 Collision_Cache_Reset(false);
1757                                 index = 1;
1758                         }
1759                 }
1760                 // link the new cache entry into the hash bucket
1761                 collision_cachedtrace_firstfree = index + 1;
1762                 if (collision_cachedtrace_lastused < index)
1763                         collision_cachedtrace_lastused = index;
1764                 cached = collision_cachedtrace_array + index;
1765                 collision_cachedtrace_arraynext[index] = collision_cachedtrace_hash[hashindex];
1766                 collision_cachedtrace_hash[hashindex] = index;
1767                 collision_cachedtrace_arrayhashindex[index] = hashindex;
1768                 cached->valid = false;
1769                 cached->p = params;
1770                 collision_cachedtrace_arrayfullhashindex[index] = fullhashindex;
1771                 collision_cachedtrace_arrayused[index] = collision_cachedtrace_sequence;
1772         }
1773         return cached;
1774 }
1775
1776 void Collision_Cache_ClipLineToGenericEntitySurfaces(trace_t *trace, dp_model_t *model, matrix4x4_t *matrix, matrix4x4_t *inversematrix, const vec3_t start, const vec3_t end, int hitsupercontentsmask)
1777 {
1778         collision_cachedtrace_t *cached = Collision_Cache_Lookup(model, matrix, inversematrix, start, end, hitsupercontentsmask);
1779         if (cached->valid)
1780         {
1781                 *trace = cached->result;
1782                 return;
1783         }
1784
1785         Collision_ClipLineToGenericEntity(trace, model, NULL, NULL, vec3_origin, vec3_origin, 0, matrix, inversematrix, start, end, hitsupercontentsmask, true);
1786
1787         cached->result = *trace;
1788 }
1789
1790 void Collision_Cache_ClipLineToWorldSurfaces(trace_t *trace, dp_model_t *model, const vec3_t start, const vec3_t end, int hitsupercontents)
1791 {
1792         collision_cachedtrace_t *cached = Collision_Cache_Lookup(model, &identitymatrix, &identitymatrix, start, end, hitsupercontents);
1793         if (cached->valid)
1794         {
1795                 *trace = cached->result;
1796                 return;
1797         }
1798
1799         Collision_ClipLineToWorld(trace, model, start, end, hitsupercontents, true);
1800
1801         cached->result = *trace;
1802 }
1803
1804 void Collision_ClipToGenericEntity(trace_t *trace, dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, const vec3_t bodymins, const vec3_t bodymaxs, int bodysupercontents, matrix4x4_t *matrix, matrix4x4_t *inversematrix, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask)
1805 {
1806         float starttransformed[3], endtransformed[3];
1807
1808         memset(trace, 0, sizeof(*trace));
1809         trace->fraction = trace->realfraction = 1;
1810
1811         Matrix4x4_Transform(inversematrix, start, starttransformed);
1812         Matrix4x4_Transform(inversematrix, end, endtransformed);
1813 #if COLLISIONPARANOID >= 3
1814         Con_Printf("trans(%f %f %f -> %f %f %f, %f %f %f -> %f %f %f)", start[0], start[1], start[2], starttransformed[0], starttransformed[1], starttransformed[2], end[0], end[1], end[2], endtransformed[0], endtransformed[1], endtransformed[2]);
1815 #endif
1816
1817         if (model && model->TraceBox)
1818         {
1819                 if(model->TraceBrush && (inversematrix->m[0][1] || inversematrix->m[0][2] || inversematrix->m[1][0] || inversematrix->m[1][2] || inversematrix->m[2][0] || inversematrix->m[2][1]))
1820                 {
1821                         // we get here if TraceBrush exists, AND we have a rotation component (SOLID_BSP case)
1822                         // using starttransformed, endtransformed is WRONG in this case!
1823                         // should rather build a brush and trace using it
1824                         colboxbrushf_t thisbrush_start, thisbrush_end;
1825                         Collision_BrushForBox(&thisbrush_start, mins, maxs, 0, 0, NULL);
1826                         Collision_BrushForBox(&thisbrush_end, mins, maxs, 0, 0, NULL);
1827                         Collision_TranslateBrush(start, &thisbrush_start.brush);
1828                         Collision_TranslateBrush(end, &thisbrush_end.brush);
1829                         Collision_TransformBrush(inversematrix, &thisbrush_start.brush);
1830                         Collision_TransformBrush(inversematrix, &thisbrush_end.brush);
1831                         //Collision_TranslateBrush(starttransformed, &thisbrush_start.brush);
1832                         //Collision_TranslateBrush(endtransformed, &thisbrush_end.brush);
1833                         model->TraceBrush(model, frameblend, skeleton, trace, &thisbrush_start.brush, &thisbrush_end.brush, hitsupercontentsmask);
1834                 }
1835                 else // this is only approximate if rotated, quite useless
1836                         model->TraceBox(model, frameblend, skeleton, trace, starttransformed, mins, maxs, endtransformed, hitsupercontentsmask);
1837         }
1838         else // and this requires that the transformation matrix doesn't have angles components, like SV_TraceBox ensures; FIXME may get called if a model is SOLID_BSP but has no TraceBox function
1839                 Collision_ClipTrace_Box(trace, bodymins, bodymaxs, starttransformed, mins, maxs, endtransformed, hitsupercontentsmask, bodysupercontents, 0, NULL);
1840         trace->fraction = bound(0, trace->fraction, 1);
1841         trace->realfraction = bound(0, trace->realfraction, 1);
1842
1843         VectorLerp(start, trace->fraction, end, trace->endpos);
1844         // transform plane
1845         // NOTE: this relies on plane.dist being directly after plane.normal
1846         Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal);
1847 }
1848
1849 void Collision_ClipToWorld(trace_t *trace, dp_model_t *model, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontents)
1850 {
1851         memset(trace, 0, sizeof(*trace));
1852         trace->fraction = trace->realfraction = 1;
1853         // ->TraceBox: TraceBrush not needed here, as worldmodel is never rotated
1854         if (model && model->TraceBox)
1855                 model->TraceBox(model, NULL, NULL, trace, start, mins, maxs, end, hitsupercontents);
1856         trace->fraction = bound(0, trace->fraction, 1);
1857         trace->realfraction = bound(0, trace->realfraction, 1);
1858         VectorLerp(start, trace->fraction, end, trace->endpos);
1859 }
1860
1861 void Collision_ClipLineToGenericEntity(trace_t *trace, dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, const vec3_t bodymins, const vec3_t bodymaxs, int bodysupercontents, matrix4x4_t *matrix, matrix4x4_t *inversematrix, const vec3_t start, const vec3_t end, int hitsupercontentsmask, qboolean hitsurfaces)
1862 {
1863         float starttransformed[3], endtransformed[3];
1864         memset(trace, 0, sizeof(*trace));
1865         trace->fraction = trace->realfraction = 1;
1866
1867         Matrix4x4_Transform(inversematrix, start, starttransformed);
1868         Matrix4x4_Transform(inversematrix, end, endtransformed);
1869 #if COLLISIONPARANOID >= 3
1870         Con_Printf("trans(%f %f %f -> %f %f %f, %f %f %f -> %f %f %f)", start[0], start[1], start[2], starttransformed[0], starttransformed[1], starttransformed[2], end[0], end[1], end[2], endtransformed[0], endtransformed[1], endtransformed[2]);
1871 #endif
1872
1873         if (model && model->TraceLineAgainstSurfaces && hitsurfaces)
1874                 model->TraceLineAgainstSurfaces(model, frameblend, skeleton, trace, starttransformed, endtransformed, hitsupercontentsmask);
1875         else if (model && model->TraceLine)
1876                 model->TraceLine(model, frameblend, skeleton, trace, starttransformed, endtransformed, hitsupercontentsmask);
1877         else
1878                 Collision_ClipTrace_Box(trace, bodymins, bodymaxs, starttransformed, vec3_origin, vec3_origin, endtransformed, hitsupercontentsmask, bodysupercontents, 0, NULL);
1879         trace->fraction = bound(0, trace->fraction, 1);
1880         trace->realfraction = bound(0, trace->realfraction, 1);
1881
1882         VectorLerp(start, trace->fraction, end, trace->endpos);
1883         // transform plane
1884         // NOTE: this relies on plane.dist being directly after plane.normal
1885         Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal);
1886 }
1887
1888 void Collision_ClipLineToWorld(trace_t *trace, dp_model_t *model, const vec3_t start, const vec3_t end, int hitsupercontents, qboolean hitsurfaces)
1889 {
1890         memset(trace, 0, sizeof(*trace));
1891         trace->fraction = trace->realfraction = 1;
1892         if (model && model->TraceLineAgainstSurfaces && hitsurfaces)
1893                 model->TraceLineAgainstSurfaces(model, NULL, NULL, trace, start, end, hitsupercontents);
1894         else if (model && model->TraceLine)
1895                 model->TraceLine(model, NULL, NULL, trace, start, end, hitsupercontents);
1896         trace->fraction = bound(0, trace->fraction, 1);
1897         trace->realfraction = bound(0, trace->realfraction, 1);
1898         VectorLerp(start, trace->fraction, end, trace->endpos);
1899 }
1900
1901 void Collision_ClipPointToGenericEntity(trace_t *trace, dp_model_t *model, const frameblend_t *frameblend, const skeleton_t *skeleton, const vec3_t bodymins, const vec3_t bodymaxs, int bodysupercontents, matrix4x4_t *matrix, matrix4x4_t *inversematrix, const vec3_t start, int hitsupercontentsmask)
1902 {
1903         float starttransformed[3];
1904         memset(trace, 0, sizeof(*trace));
1905         trace->fraction = trace->realfraction = 1;
1906
1907         Matrix4x4_Transform(inversematrix, start, starttransformed);
1908 #if COLLISIONPARANOID >= 3
1909         Con_Printf("trans(%f %f %f -> %f %f %f)", start[0], start[1], start[2], starttransformed[0], starttransformed[1], starttransformed[2]);
1910 #endif
1911
1912         if (model && model->TracePoint)
1913                 model->TracePoint(model, NULL, NULL, trace, starttransformed, hitsupercontentsmask);
1914         else
1915                 Collision_ClipTrace_Point(trace, bodymins, bodymaxs, starttransformed, hitsupercontentsmask, bodysupercontents, 0, NULL);
1916
1917         VectorCopy(start, trace->endpos);
1918         // transform plane
1919         // NOTE: this relies on plane.dist being directly after plane.normal
1920         Matrix4x4_TransformPositivePlane(matrix, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2], trace->plane.dist, trace->plane.normal);
1921 }
1922
1923 void Collision_ClipPointToWorld(trace_t *trace, dp_model_t *model, const vec3_t start, int hitsupercontents)
1924 {
1925         memset(trace, 0, sizeof(*trace));
1926         trace->fraction = trace->realfraction = 1;
1927         if (model && model->TracePoint)
1928                 model->TracePoint(model, NULL, NULL, trace, start, hitsupercontents);
1929         VectorCopy(start, trace->endpos);
1930 }
1931
1932 void Collision_CombineTraces(trace_t *cliptrace, const trace_t *trace, void *touch, qboolean isbmodel)
1933 {
1934         // take the 'best' answers from the new trace and combine with existing data
1935         if (trace->allsolid)
1936                 cliptrace->allsolid = true;
1937         if (trace->startsolid)
1938         {
1939                 if (isbmodel)
1940                         cliptrace->bmodelstartsolid = true;
1941                 cliptrace->startsolid = true;
1942                 if (cliptrace->realfraction == 1)
1943                         cliptrace->ent = touch;
1944                 if (cliptrace->startdepth > trace->startdepth)
1945                 {
1946                         cliptrace->startdepth = trace->startdepth;
1947                         VectorCopy(trace->startdepthnormal, cliptrace->startdepthnormal);
1948                 }
1949         }
1950         // don't set this except on the world, because it can easily confuse
1951         // monsters underwater if there's a bmodel involved in the trace
1952         // (inopen && inwater is how they check water visibility)
1953         //if (trace->inopen)
1954         //      cliptrace->inopen = true;
1955         if (trace->inwater)
1956                 cliptrace->inwater = true;
1957         if ((trace->realfraction <= cliptrace->realfraction) && (VectorLength2(trace->plane.normal) > 0))
1958         {
1959                 cliptrace->fraction = trace->fraction;
1960                 cliptrace->realfraction = trace->realfraction;
1961                 VectorCopy(trace->endpos, cliptrace->endpos);
1962                 cliptrace->plane = trace->plane;
1963                 cliptrace->ent = touch;
1964                 cliptrace->hitsupercontents = trace->hitsupercontents;
1965                 cliptrace->hitq3surfaceflags = trace->hitq3surfaceflags;
1966                 cliptrace->hittexture = trace->hittexture;
1967         }
1968         cliptrace->startsupercontents |= trace->startsupercontents;
1969 }
1970
1971 void Collision_ShortenTrace(trace_t *trace, float shorten_factor, const vec3_t end)
1972 {
1973         // now undo our moving end 1 qu farther...
1974         trace->fraction = bound(trace->fraction, trace->fraction / shorten_factor - 1e-6, 1); // we subtract 1e-6 to guard for roundoff errors
1975         trace->realfraction = bound(trace->realfraction, trace->realfraction / shorten_factor - 1e-6, 1); // we subtract 1e-6 to guard for roundoff errors
1976         if(trace->fraction >= 1) // trace would NOT hit if not expanded!
1977         {
1978                 trace->fraction = 1;
1979                 trace->realfraction = 1;
1980                 VectorCopy(end, trace->endpos);
1981                 memset(&trace->plane, 0, sizeof(trace->plane));
1982                 trace->ent = NULL;
1983                 trace->hitsupercontentsmask = 0;
1984                 trace->hitsupercontents = 0;
1985                 trace->hitq3surfaceflags = 0;
1986                 trace->hittexture = NULL;
1987         }
1988 }