+static void Collision_TranslateBrush(const vec3_t shift, colbrushf_t *brush)
+{
+ int i;
+ // now we can transform the data
+ for(i = 0; i < brush->numplanes; ++i)
+ {
+ brush->planes[i].dist += DotProduct(shift, brush->planes[i].normal);
+ }
+ for(i = 0; i < brush->numpoints; ++i)
+ {
+ VectorAdd(brush->points[i].v, shift, brush->points[i].v);
+ }
+ VectorAdd(brush->mins, shift, brush->mins);
+ VectorAdd(brush->maxs, shift, brush->maxs);
+}
+
+static void Collision_TransformBrush(const matrix4x4_t *matrix, colbrushf_t *brush)
+{
+ int i;
+ vec3_t v;
+ // we're breaking any AABB properties here...
+ brush->isaabb = false;
+ brush->hasaabbplanes = false;
+ // now we can transform the data
+ for(i = 0; i < brush->numplanes; ++i)
+ {
+ Matrix4x4_TransformPositivePlane(matrix, brush->planes[i].normal[0], brush->planes[i].normal[1], brush->planes[i].normal[2], brush->planes[i].dist, brush->planes[i].normal_and_dist);
+ }
+ for(i = 0; i < brush->numedgedirs; ++i)
+ {
+ Matrix4x4_Transform(matrix, brush->edgedirs[i].v, v);
+ VectorCopy(v, brush->edgedirs[i].v);
+ }
+ for(i = 0; i < brush->numpoints; ++i)
+ {
+ Matrix4x4_Transform(matrix, brush->points[i].v, v);
+ VectorCopy(v, brush->points[i].v);
+ }
+ VectorCopy(brush->points[0].v, brush->mins);
+ VectorCopy(brush->points[0].v, brush->maxs);
+ for(i = 1; i < brush->numpoints; ++i)
+ {
+ if(brush->points[i].v[0] < brush->mins[0]) brush->mins[0] = brush->points[i].v[0];
+ if(brush->points[i].v[1] < brush->mins[1]) brush->mins[1] = brush->points[i].v[1];
+ if(brush->points[i].v[2] < brush->mins[2]) brush->mins[2] = brush->points[i].v[2];
+ if(brush->points[i].v[0] > brush->maxs[0]) brush->maxs[0] = brush->points[i].v[0];
+ if(brush->points[i].v[1] > brush->maxs[1]) brush->maxs[1] = brush->points[i].v[1];
+ if(brush->points[i].v[2] > brush->maxs[2]) brush->maxs[2] = brush->points[i].v[2];
+ }
+}
+
+typedef struct collision_cachedtrace_parameters_s
+{
+ dp_model_t *model;
+ vec3_t end;
+ vec3_t start;
+ int hitsupercontentsmask;
+ int skipsupercontentsmask;
+ matrix4x4_t matrix;
+}
+collision_cachedtrace_parameters_t;
+
+typedef struct collision_cachedtrace_s
+{
+ qboolean valid;
+ collision_cachedtrace_parameters_t p;
+ trace_t result;
+}
+collision_cachedtrace_t;
+
+static mempool_t *collision_cachedtrace_mempool;
+static collision_cachedtrace_t *collision_cachedtrace_array;
+static int collision_cachedtrace_firstfree;
+static int collision_cachedtrace_lastused;
+static int collision_cachedtrace_max;
+static unsigned char collision_cachedtrace_sequence;
+static int collision_cachedtrace_hashsize;
+static int *collision_cachedtrace_hash;
+static unsigned int *collision_cachedtrace_arrayfullhashindex;
+static unsigned int *collision_cachedtrace_arrayhashindex;
+static unsigned int *collision_cachedtrace_arraynext;
+static unsigned char *collision_cachedtrace_arrayused;
+static qboolean collision_cachedtrace_rebuildhash;
+
+void Collision_Cache_Reset(qboolean resetlimits)
+{
+ if (collision_cachedtrace_hash)
+ Mem_Free(collision_cachedtrace_hash);
+ if (collision_cachedtrace_array)
+ Mem_Free(collision_cachedtrace_array);
+ if (collision_cachedtrace_arrayfullhashindex)
+ Mem_Free(collision_cachedtrace_arrayfullhashindex);
+ if (collision_cachedtrace_arrayhashindex)
+ Mem_Free(collision_cachedtrace_arrayhashindex);
+ if (collision_cachedtrace_arraynext)
+ Mem_Free(collision_cachedtrace_arraynext);
+ if (collision_cachedtrace_arrayused)
+ Mem_Free(collision_cachedtrace_arrayused);
+ if (resetlimits || !collision_cachedtrace_max)
+ collision_cachedtrace_max = collision_cache.integer ? 128 : 1;
+ collision_cachedtrace_firstfree = 1;
+ collision_cachedtrace_lastused = 0;
+ collision_cachedtrace_hashsize = collision_cachedtrace_max;
+ collision_cachedtrace_array = (collision_cachedtrace_t *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(collision_cachedtrace_t));
+ collision_cachedtrace_hash = (int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_hashsize * sizeof(int));
+ collision_cachedtrace_arrayfullhashindex = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
+ collision_cachedtrace_arrayhashindex = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
+ collision_cachedtrace_arraynext = (unsigned int *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned int));
+ collision_cachedtrace_arrayused = (unsigned char *)Mem_Alloc(collision_cachedtrace_mempool, collision_cachedtrace_max * sizeof(unsigned char));
+ collision_cachedtrace_sequence = 1;
+ collision_cachedtrace_rebuildhash = false;
+}
+
+void Collision_Cache_Init(mempool_t *mempool)
+{
+ collision_cachedtrace_mempool = mempool;
+ Collision_Cache_Reset(true);
+}
+
+static void Collision_Cache_RebuildHash(void)
+{
+ int index;
+ int range = collision_cachedtrace_lastused + 1;
+ unsigned char sequence = collision_cachedtrace_sequence;
+ int firstfree = collision_cachedtrace_max;
+ int lastused = 0;
+ int *hash = collision_cachedtrace_hash;
+ unsigned int hashindex;
+ unsigned int *arrayhashindex = collision_cachedtrace_arrayhashindex;
+ unsigned int *arraynext = collision_cachedtrace_arraynext;
+ collision_cachedtrace_rebuildhash = false;
+ memset(collision_cachedtrace_hash, 0, collision_cachedtrace_hashsize * sizeof(int));
+ for (index = 1;index < range;index++)
+ {
+ if (collision_cachedtrace_arrayused[index] == sequence)
+ {
+ hashindex = arrayhashindex[index];
+ arraynext[index] = hash[hashindex];
+ hash[hashindex] = index;
+ lastused = index;
+ }
+ else
+ {
+ if (firstfree > index)
+ firstfree = index;
+ collision_cachedtrace_arrayused[index] = 0;
+ }
+ }
+ collision_cachedtrace_firstfree = firstfree;
+ collision_cachedtrace_lastused = lastused;
+}
+
+void Collision_Cache_NewFrame(void)
+{
+ if (collision_cache.integer)
+ {
+ if (collision_cachedtrace_max < 128)
+ Collision_Cache_Reset(true);
+ }
+ else
+ {
+ if (collision_cachedtrace_max > 1)
+ Collision_Cache_Reset(true);
+ }
+ // rebuild hash if sequence would overflow byte, otherwise increment
+ if (collision_cachedtrace_sequence == 255)
+ {
+ Collision_Cache_RebuildHash();
+ collision_cachedtrace_sequence = 1;
+ }
+ else
+ {
+ collision_cachedtrace_rebuildhash = true;
+ collision_cachedtrace_sequence++;
+ }
+}
+
+static unsigned int Collision_Cache_HashIndexForArray(unsigned int *array, unsigned int size)
+{
+ unsigned int i;
+ unsigned int hashindex = 0;
+ // this is a super-cheesy checksum, designed only for speed
+ for (i = 0;i < size;i++)
+ hashindex += array[i] * (1 + i);
+ return hashindex;
+}
+
+static collision_cachedtrace_t *Collision_Cache_Lookup(dp_model_t *model, const matrix4x4_t *matrix, const matrix4x4_t *inversematrix, const vec3_t start, const vec3_t end, int hitsupercontentsmask, int skipsupercontentsmask)
+{
+ int hashindex = 0;
+ unsigned int fullhashindex;
+ int index = 0;
+ int range;
+ unsigned char sequence = collision_cachedtrace_sequence;
+ int *hash = collision_cachedtrace_hash;
+ unsigned int *arrayfullhashindex = collision_cachedtrace_arrayfullhashindex;
+ unsigned int *arraynext = collision_cachedtrace_arraynext;
+ collision_cachedtrace_t *cached = collision_cachedtrace_array + index;
+ collision_cachedtrace_parameters_t params;
+ // all non-cached traces use the same index
+ if (!collision_cache.integer)
+ r_refdef.stats[r_stat_photoncache_traced]++;
+ else
+ {
+ // cached trace lookup
+ memset(¶ms, 0, sizeof(params));
+ params.model = model;
+ VectorCopy(start, params.start);
+ VectorCopy(end, params.end);
+ params.hitsupercontentsmask = hitsupercontentsmask;
+ params.skipsupercontentsmask = skipsupercontentsmask;
+ params.matrix = *matrix;
+ fullhashindex = Collision_Cache_HashIndexForArray((unsigned int *)¶ms, sizeof(params) / sizeof(unsigned int));
+ hashindex = (int)(fullhashindex % (unsigned int)collision_cachedtrace_hashsize);
+ for (index = hash[hashindex];index;index = arraynext[index])
+ {
+ if (arrayfullhashindex[index] != fullhashindex)
+ continue;
+ cached = collision_cachedtrace_array + index;
+ //if (memcmp(&cached->p, ¶ms, sizeof(params)))
+ if (cached->p.model != params.model
+ || cached->p.end[0] != params.end[0]
+ || cached->p.end[1] != params.end[1]
+ || cached->p.end[2] != params.end[2]
+ || cached->p.start[0] != params.start[0]
+ || cached->p.start[1] != params.start[1]
+ || cached->p.start[2] != params.start[2]
+ || cached->p.hitsupercontentsmask != params.hitsupercontentsmask
+ || cached->p.skipsupercontentsmask != params.skipsupercontentsmask
+ || cached->p.matrix.m[0][0] != params.matrix.m[0][0]
+ || cached->p.matrix.m[0][1] != params.matrix.m[0][1]
+ || cached->p.matrix.m[0][2] != params.matrix.m[0][2]
+ || cached->p.matrix.m[0][3] != params.matrix.m[0][3]
+ || cached->p.matrix.m[1][0] != params.matrix.m[1][0]
+ || cached->p.matrix.m[1][1] != params.matrix.m[1][1]
+ || cached->p.matrix.m[1][2] != params.matrix.m[1][2]
+ || cached->p.matrix.m[1][3] != params.matrix.m[1][3]
+ || cached->p.matrix.m[2][0] != params.matrix.m[2][0]
+ || cached->p.matrix.m[2][1] != params.matrix.m[2][1]
+ || cached->p.matrix.m[2][2] != params.matrix.m[2][2]
+ || cached->p.matrix.m[2][3] != params.matrix.m[2][3]
+ || cached->p.matrix.m[3][0] != params.matrix.m[3][0]
+ || cached->p.matrix.m[3][1] != params.matrix.m[3][1]
+ || cached->p.matrix.m[3][2] != params.matrix.m[3][2]
+ || cached->p.matrix.m[3][3] != params.matrix.m[3][3]
+ )
+ continue;
+ // found a matching trace in the cache
+ r_refdef.stats[r_stat_photoncache_cached]++;
+ cached->valid = true;
+ collision_cachedtrace_arrayused[index] = collision_cachedtrace_sequence;
+ return cached;
+ }
+ r_refdef.stats[r_stat_photoncache_traced]++;
+ // find an unused cache entry
+ for (index = collision_cachedtrace_firstfree, range = collision_cachedtrace_max;index < range;index++)
+ if (collision_cachedtrace_arrayused[index] == 0)
+ break;
+ if (index == range)
+ {
+ // all claimed, but probably some are stale...
+ for (index = 1, range = collision_cachedtrace_max;index < range;index++)
+ if (collision_cachedtrace_arrayused[index] != sequence)
+ break;
+ if (index < range)
+ {
+ // found a stale one, rebuild the hash
+ Collision_Cache_RebuildHash();
+ }
+ else
+ {
+ // we need to grow the cache
+ collision_cachedtrace_max *= 2;
+ Collision_Cache_Reset(false);
+ index = 1;
+ }
+ }
+ // link the new cache entry into the hash bucket
+ collision_cachedtrace_firstfree = index + 1;
+ if (collision_cachedtrace_lastused < index)
+ collision_cachedtrace_lastused = index;
+ cached = collision_cachedtrace_array + index;
+ collision_cachedtrace_arraynext[index] = collision_cachedtrace_hash[hashindex];
+ collision_cachedtrace_hash[hashindex] = index;
+ collision_cachedtrace_arrayhashindex[index] = hashindex;
+ cached->valid = false;
+ cached->p = params;
+ collision_cachedtrace_arrayfullhashindex[index] = fullhashindex;
+ collision_cachedtrace_arrayused[index] = collision_cachedtrace_sequence;
+ }
+ return cached;
+}
+
+void Collision_Cache_ClipLineToGenericEntitySurfaces(trace_t *trace, dp_model_t *model, matrix4x4_t *matrix, matrix4x4_t *inversematrix, const vec3_t start, const vec3_t end, int hitsupercontentsmask, int skipsupercontentsmask)
+{
+ collision_cachedtrace_t *cached = Collision_Cache_Lookup(model, matrix, inversematrix, start, end, hitsupercontentsmask, skipsupercontentsmask);
+ if (cached->valid)
+ {
+ *trace = cached->result;
+ return;
+ }
+
+ Collision_ClipLineToGenericEntity(trace, model, NULL, NULL, vec3_origin, vec3_origin, 0, matrix, inversematrix, start, end, hitsupercontentsmask, skipsupercontentsmask, collision_extendmovelength.value, true);
+
+ cached->result = *trace;
+}
+
+void Collision_Cache_ClipLineToWorldSurfaces(trace_t *trace, dp_model_t *model, const vec3_t start, const vec3_t end, int hitsupercontentsmask, int skipsupercontentsmask)