collision.c

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