1
Coding / Trying to speed up code for Routing
« on: March 19, 2017, 02:36:34 pm »
I'm trying to speed up the code for Routing, specially a recursive function that is used a lot: TR_RecursiveHullCheck() (in src/common/tracing.cpp)
It is called from TR_BoxTrace(), when checking if actors can enter each cell, to build the Routing table. Map2Ufo uses it to prepare the data into the BSP, but the game also uses it somewhere.
The part I'm interested in is from line 949.
After some checks in the previous code, we are splitting the vector in 2 fractions, to check both parts in sequence. Current code calculates twice the splitting point (frac, frac2, midf, again midf), but I think we need to do it just 1 time (so avoiding some time-expensive multiplications). Also I have found a weird thing, possibly a bug, in line 955:
If I'm right, then we don't need frac2 at all, and can use the first calculation for midf in both recursive calls to TR_RecursiveHullCheck() in lines 976 and 986.
This part of the function, from lines 949 to 986 could be (I have commented out the lines to be deleted):
With this changes I cannot find any problem in game, and map2ufo compiles map in less than half the time (besides lighting). So I would like anybody can check this too.
It is called from TR_BoxTrace(), when checking if actors can enter each cell, to build the Routing table. Map2Ufo uses it to prepare the data into the BSP, but the game also uses it somewhere.
The part I'm interested in is from line 949.
After some checks in the previous code, we are splitting the vector in 2 fractions, to check both parts in sequence. Current code calculates twice the splitting point (frac, frac2, midf, again midf), but I think we need to do it just 1 time (so avoiding some time-expensive multiplications). Also I have found a weird thing, possibly a bug, in line 955:
Code: [Select]
frac = (t1 - offset + DIST_EPSILON) * idist;
should be:Code: [Select]
frac = (t1 - offset - DIST_EPSILON) * idist;
If I'm right, then we don't need frac2 at all, and can use the first calculation for midf in both recursive calls to TR_RecursiveHullCheck() in lines 976 and 986.
This part of the function, from lines 949 to 986 could be (I have commented out the lines to be deleted):
Code: [Select]
/* float frac, frac2; */ /* To be deleted */
float frac; /* Added to replace previous line */
int side;
if (t1 < t2) {
const float idist = 1.0 / (t1 - t2);
side = 1;
/* frac2 = (t1 + offset + DIST_EPSILON) * idist; */ /* To be deleted */
/* frac = (t1 - offset + DIST_EPSILON) * idist; */ /* To be deleted */
frac = (t1 - offset - DIST_EPSILON) * idist; /* Added to replace previous line */
} else if (t1 > t2) {
const float idist = 1.0 / (t1 - t2);
side = 0;
/* frac2 = (t1 - offset - DIST_EPSILON) * idist; */ /* To be deleted */
frac = (t1 + offset + DIST_EPSILON) * idist;
} else {
side = 0;
frac = 1;
/* frac2 = 0; */ /* To be deleted */
}
/* move up to the node */
if (frac < 0)
frac = 0;
else if (frac > 1)
frac = 1;
float midf = p1f + (p2f - p1f) * frac;
vec3_t mid;
VectorInterpolation(p1, p2, frac, mid);
TR_RecursiveHullCheck(traceData, node->children[side], p1f, midf, p1, mid);
/* go past the node */
/* if (frac2 < 0) */ /* To be deleted */
/* frac2 = 0; */ /* To be deleted */
/* else if (frac2 > 1) */ /* To be deleted */
/* frac2 = 1; */ /* To be deleted */
/* midf = p1f + (p2f - p1f) * frac2; */ /* To be deleted */
/* VectorInterpolation(p1, p2, frac2, mid); */ /* To be deleted */
TR_RecursiveHullCheck(traceData, node->children[side ^ 1], midf, p2f, mid, p2);
With this changes I cannot find any problem in game, and map2ufo compiles map in less than half the time (besides lighting). So I would like anybody can check this too.