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