Trying to speed up code for Routing

[Namerutan]

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:

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.

[DarkRain]

I'm not familiarised with this part of the code, so I don't really know what was the intent of those...

[Namerutan]

I have used
ufo2map -tracefile -debugtrace maps/mine.map
for several maps (not just "mine"), using both copies of the ufo2map.exe (the original one and the one with my modification), to get the routing data in csv format. Then used notepad++ with the "compare" plugin and found the routing data matches in all cases. Then compared the bsp files using WinDiff (utility to compare binary files), and also matches.
So I think this modification is safe to be used, and means a good improvement for speed at compile time.

[Namerutan]

I was going to add timing data to compare with and without the modification, then noticed a big fail in my comparison.
My first impression was just comparing the downloaded ufo2map (from downloads section) with the compiled with modifications, but the main difference on timing surely is due to the optimizations used by the compiler; my modification is just a very small improvement 

Next you can find an example of timing (on my machine, taken from the log) using 3 copies of ufo2map.exe: the one I downloaded from downloads section, the one I compiled from source (unmodified source, using optimizations from compiler), and the one I compiled with my modification.
The 3 amounts of time are for map data, day light data and night light data; only the first timing is affected by the modified code. After map name, you can find timing with original ufo2map, self compiled from unmodified source, then timing with modified ufo2map.

"Mine.map", 34 + 66 + 61 = 161 seconds, 24 + 44 + 43 = 111 seconds, 21 + 44 + 43 = 108 seconds

Note how the timing for Lighting are the same for both .exe compiled on my machine, and the improvement is just the first part (from 24 to 21); at first I was comparing 34 to 21, so a bigger difference, and much bigger in % if you just take the part of the timing related to the Routing calculations.

Lesson learned: Don't use the compiled exes for windows users; better compile on my own (as linux users do).

[DarkRain]

Well, if the routing data is the same, I say we go for it, not so much for the performance improvement, but because the less unnecessary code there is the easier it will be be to disentangle it when we need to make changes for any reason

So, patch?

[Sandro]

Somehow missed this topic earlier.

A quick answer:

1) Intent of this code is stated just a few lines above: "/* put the crosspoint DIST_EPSILON pixels on the near side */". The same comment is present in the original Quake2 source code, which also uses the same signs; in fact, UFO:AI code is 100% identical here.

2) First Quake uses a different approach, with a single fraction, like  Namerutan proposes. So calculating two fraction for the split is the intentional by the engeine developers.

3) Quake3 collision detection code is seriously refactored, but this calculation is identical to the Quake2 and the UFO:AI. So this math is likely to be intentional rather than bug.

4) CPU consumption by calculating fractions separately is marginal; main cost lies in the AABB vs arbitrary polytope collision detection.

So, unless someone sits with paper & pencil to redo the math, I'd recommend to keep it as it is.

PS: Routing code can (and, likely, should) be optimized, that is true. But not here.