From 3b0c5d8f3870412b045f9cfe0a22f18b493359e1 Mon Sep 17 00:00:00 2001
From: James Canete <smiletheory@gmail.com>
Date: Wed, 22 Feb 2012 13:48:48 +0100
Subject: [PATCH] patch to speed up map compiling:
kill tail recursion in TraceLine_r
speed up normalizing again where the full accuracy is not necessary
---
libs/mathlib.h | 8 +-
libs/mathlib/mathlib.c | 39 +++---
tools/quake3/q3map2/light.c | 4 +-
tools/quake3/q3map2/light_trace.c | 206 +++++++++++++++++-------------
4 files changed, 148 insertions(+), 109 deletions(-)
diff --git a/libs/mathlib.h b/libs/mathlib.h
index 382933d7..02ed6fd0 100644
--- a/libs/mathlib.h
+++ b/libs/mathlib.h
@@ -101,7 +101,13 @@ void _CrossProduct (vec3_t v1, vec3_t v2, vec3_t cross);
// I need this define in order to test some of the regression tests from time to time.
// This define affect the precision of VectorNormalize() function only.
#define MATHLIB_VECTOR_NORMALIZE_PRECISION_FIX 1
-vec_t VectorNormalize (const vec3_t in, vec3_t out);
+vec_t VectorAccurateNormalize (const vec3_t in, vec3_t out);
+vec_t VectorFastNormalize (const vec3_t in, vec3_t out);
+#if MATHLIB_VECTOR_NORMALIZE_PRECISION_FIX
+#define VectorNormalize VectorAccurateNormalize
+#else
+#define VectorNormalize VectorFastNormalize
+#endif
vec_t ColorNormalize( const vec3_t in, vec3_t out );
void VectorInverse (vec3_t v);
void VectorPolar(vec3_t v, float radius, float theta, float phi);
diff --git a/libs/mathlib/mathlib.c b/libs/mathlib/mathlib.c
index 98fb972a..41d1496d 100644
--- a/libs/mathlib/mathlib.c
+++ b/libs/mathlib/mathlib.c
@@ -166,9 +166,7 @@ void _VectorCopy (vec3_t in, vec3_t out)
out[2] = in[2];
}
-vec_t VectorNormalize( const vec3_t in, vec3_t out ) {
-
-#if MATHLIB_VECTOR_NORMALIZE_PRECISION_FIX
+vec_t VectorAccurateNormalize( const vec3_t in, vec3_t out ) {
// The sqrt() function takes double as an input and returns double as an
// output according the the man pages on Debian and on FreeBSD. Therefore,
@@ -193,27 +191,30 @@ vec_t VectorNormalize( const vec3_t in, vec3_t out ) {
out[2] = (vec_t) (z / length);
return (vec_t) length;
+}
-#else
-
- vec_t length, ilength;
-
- length = (vec_t)sqrt (in[0]*in[0] + in[1]*in[1] + in[2]*in[2]);
- if (length == 0)
- {
- VectorClear (out);
- return 0;
- }
+vec_t VectorFastNormalize( const vec3_t in, vec3_t out ) {
- ilength = 1.0f/length;
- out[0] = in[0]*ilength;
- out[1] = in[1]*ilength;
- out[2] = in[2]*ilength;
+ // SmileTheory: This is ioquake3's VectorNormalize2
+ // for when accuracy matters less than speed
+ float length, ilength;
- return length;
+ length = in[0]*in[0] + in[1]*in[1] + in[2]*in[2];
-#endif
+ if (length)
+ {
+ /* writing it this way allows gcc to recognize that rsqrt can be used */
+ ilength = 1/(float)sqrt (length);
+ /* sqrt(length) = length * (1 / sqrt(length)) */
+ length *= ilength;
+ out[0] = in[0]*ilength;
+ out[1] = in[1]*ilength;
+ out[2] = in[2]*ilength;
+ } else {
+ VectorClear( out );
+ }
+ return length;
}
vec_t ColorNormalize( const vec3_t in, vec3_t out ) {
diff --git a/tools/quake3/q3map2/light.c b/tools/quake3/q3map2/light.c
index db1cc576..fe4bcf1b 100644
--- a/tools/quake3/q3map2/light.c
+++ b/tools/quake3/q3map2/light.c
@@ -702,7 +702,7 @@ float PointToPolygonFormFactor( const vec3_t point, const vec3_t normal, const w
for( i = 0; i < w->numpoints; i++ )
{
VectorSubtract( w->p[ i ], point, dirs[ i ] );
- VectorNormalize( dirs[ i ], dirs[ i ] );
+ VectorFastNormalize( dirs[ i ], dirs[ i ] );
}
/* duplicate first vertex to avoid mod operation */
@@ -726,7 +726,7 @@ float PointToPolygonFormFactor( const vec3_t point, const vec3_t normal, const w
angle = acos( dot );
CrossProduct( dirs[ i ], dirs[ j ], triVector );
- if( VectorNormalize( triVector, triNormal ) < 0.0001f )
+ if( VectorFastNormalize( triVector, triNormal ) < 0.0001f )
continue;
facing = DotProduct( normal, triNormal );
diff --git a/tools/quake3/q3map2/light_trace.c b/tools/quake3/q3map2/light_trace.c
index d0b72d35..e7c3b019 100644
--- a/tools/quake3/q3map2/light_trace.c
+++ b/tools/quake3/q3map2/light_trace.c
@@ -1581,102 +1581,134 @@ qboolean TraceWinding( traceWinding_t *tw, trace_t *trace )
/*
TraceLine_r()
returns qtrue if something is hit and tracing can stop
+
+SmileTheory: made half-iterative
*/
-static qboolean TraceLine_r( int nodeNum, vec3_t origin, vec3_t end, trace_t *trace )
+#define TRACELINE_R_HALF_ITERATIVE 1
+
+#if TRACELINE_R_HALF_ITERATIVE
+static qboolean TraceLine_r( int nodeNum, const vec3_t start, const vec3_t end, trace_t *trace )
+#else
+static qboolean TraceLine_r( int nodeNum, const vec3_t origin, const vec3_t end, trace_t *trace )
+#endif
{
traceNode_t *node;
int side;
float front, back, frac;
- vec3_t mid;
+ vec3_t origin, mid;
qboolean r;
-
-
- /* bogus node number means solid, end tracing unless testing all */
- if( nodeNum < 0 )
- {
- VectorCopy( origin, trace->hit );
- trace->passSolid = qtrue;
- return qtrue;
- }
-
- /* get node */
- node = &traceNodes[ nodeNum ];
-
- /* solid? */
- if( node->type == TRACE_LEAF_SOLID )
- {
- VectorCopy( origin, trace->hit );
- trace->passSolid = qtrue;
- return qtrue;
- }
-
- /* leafnode? */
- if( node->type < 0 )
- {
- /* note leaf and return */
- if( node->numItems > 0 && trace->numTestNodes < MAX_TRACE_TEST_NODES )
- trace->testNodes[ trace->numTestNodes++ ] = nodeNum;
- return qfalse;
- }
- /* ydnar 2003-09-07: don't test branches of the bsp with nothing in them when testall is enabled */
- if( trace->testAll && node->numItems == 0 )
- return qfalse;
-
- /* classify beginning and end points */
- switch( node->type )
+#if TRACELINE_R_HALF_ITERATIVE
+ VectorCopy( start, origin );
+
+ while( 1 )
+#endif
{
- case PLANE_X:
- front = origin[ 0 ] - node->plane[ 3 ];
- back = end[ 0 ] - node->plane[ 3 ];
- break;
-
- case PLANE_Y:
- front = origin[ 1 ] - node->plane[ 3 ];
- back = end[ 1 ] - node->plane[ 3 ];
- break;
-
- case PLANE_Z:
- front = origin[ 2 ] - node->plane[ 3 ];
- back = end[ 2 ] - node->plane[ 3 ];
- break;
-
- default:
- front = DotProduct( origin, node->plane ) - node->plane[ 3 ];
- back = DotProduct( end, node->plane ) - node->plane[ 3 ];
- break;
+ /* bogus node number means solid, end tracing unless testing all */
+ if( nodeNum < 0 )
+ {
+ VectorCopy( origin, trace->hit );
+ trace->passSolid = qtrue;
+ return qtrue;
+ }
+
+ /* get node */
+ node = &traceNodes[ nodeNum ];
+
+ /* solid? */
+ if( node->type == TRACE_LEAF_SOLID )
+ {
+ VectorCopy( origin, trace->hit );
+ trace->passSolid = qtrue;
+ return qtrue;
+ }
+
+ /* leafnode? */
+ if( node->type < 0 )
+ {
+ /* note leaf and return */
+ if( node->numItems > 0 && trace->numTestNodes < MAX_TRACE_TEST_NODES )
+ trace->testNodes[ trace->numTestNodes++ ] = nodeNum;
+ return qfalse;
+ }
+
+ /* ydnar 2003-09-07: don't test branches of the bsp with nothing in them when testall is enabled */
+ if( trace->testAll && node->numItems == 0 )
+ return qfalse;
+
+ /* classify beginning and end points */
+ switch( node->type )
+ {
+ case PLANE_X:
+ front = origin[ 0 ] - node->plane[ 3 ];
+ back = end[ 0 ] - node->plane[ 3 ];
+ break;
+
+ case PLANE_Y:
+ front = origin[ 1 ] - node->plane[ 3 ];
+ back = end[ 1 ] - node->plane[ 3 ];
+ break;
+
+ case PLANE_Z:
+ front = origin[ 2 ] - node->plane[ 3 ];
+ back = end[ 2 ] - node->plane[ 3 ];
+ break;
+
+ default:
+ front = DotProduct( origin, node->plane ) - node->plane[ 3 ];
+ back = DotProduct( end, node->plane ) - node->plane[ 3 ];
+ break;
+ }
+
+ /* entirely in front side? */
+ if( front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON )
+ {
+#if TRACELINE_R_HALF_ITERATIVE
+ nodeNum = node->children[ 0 ];
+ continue;
+#else
+ return TraceLine_r( node->children[ 0 ], origin, end, trace );
+#endif
+ }
+
+ /* entirely on back side? */
+ if( front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON )
+ {
+#if TRACELINE_R_HALF_ITERATIVE
+ nodeNum = node->children[ 1 ];
+ continue;
+#else
+ return TraceLine_r( node->children[ 1 ], origin, end, trace );
+#endif
+ }
+
+ /* select side */
+ side = front < 0;
+
+ /* calculate intercept point */
+ frac = front / (front - back);
+ mid[ 0 ] = origin[ 0 ] + (end[ 0 ] - origin[ 0 ]) * frac;
+ mid[ 1 ] = origin[ 1 ] + (end[ 1 ] - origin[ 1 ]) * frac;
+ mid[ 2 ] = origin[ 2 ] + (end[ 2 ] - origin[ 2 ]) * frac;
+
+ /* fixme: check inhibit radius, then solid nodes and ignore */
+
+ /* set trace hit here */
+ //% VectorCopy( mid, trace->hit );
+
+ /* trace first side */
+ if( TraceLine_r( node->children[ side ], origin, mid, trace ) )
+ return qtrue;
+
+ /* trace other side */
+#if TRACELINE_R_HALF_ITERATIVE
+ nodeNum = node->children[ !side ];
+ VectorCopy( mid, origin );
+#else
+ return TraceLine_r( node->children[ !side ], mid, end, trace );
+#endif
}
-
- /* entirely in front side? */
- if( front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON )
- return TraceLine_r( node->children[ 0 ], origin, end, trace );
-
- /* entirely on back side? */
- if( front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON )
- return TraceLine_r( node->children[ 1 ], origin, end, trace );
-
- /* select side */
- side = front < 0;
-
- /* calculate intercept point */
- frac = front / (front - back);
- mid[ 0 ] = origin[ 0 ] + (end[ 0 ] - origin[ 0 ]) * frac;
- mid[ 1 ] = origin[ 1 ] + (end[ 1 ] - origin[ 1 ]) * frac;
- mid[ 2 ] = origin[ 2 ] + (end[ 2 ] - origin[ 2 ]) * frac;
-
- /* fixme: check inhibit radius, then solid nodes and ignore */
-
- /* set trace hit here */
- //% VectorCopy( mid, trace->hit );
-
- /* trace first side */
- r = TraceLine_r( node->children[ side ], origin, mid, trace );
- if( r )
- return r;
-
- /* trace other side */
- return TraceLine_r( node->children[ !side ], mid, end, trace );
}
@@ -1754,7 +1786,7 @@ sets up certain trace values
float SetupTrace( trace_t *trace )
{
VectorSubtract( trace->end, trace->origin, trace->displacement );
- trace->distance = VectorNormalize( trace->displacement, trace->direction );
+ trace->distance = VectorFastNormalize( trace->displacement, trace->direction );
VectorCopy( trace->origin, trace->hit );
return trace->distance;
}
--
2.39.5