giga improvement

3 files changed, 72 insertions, 28 deletions

diff --git a/src/game/world/bsp.cpp b/src/game/world/bsp.cpp
index c33cac1..4894d1c 100644
--- a/src/game/world/bsp.cpp
+++ b/src/game/world/bsp.cpp
@@ -515,6 +515,8 @@ void bsp_gen_leaf_edges( BSP* bsp, I32 leaf_idx ) {
         e.face = faceidx;
         e.v1 = a;
         e.v2 = b;
+        e.mins = vec_mins( e.v1, e.v2 );
+        e.maxs = vec_maxs( e.v1, e.v2 );
         edges->push( e );
       }
     }
diff --git a/src/game/world/bsp.h b/src/game/world/bsp.h
index 3b84e07..fa06696 100644
--- a/src/game/world/bsp.h
+++ b/src/game/world/bsp.h
@@ -45,6 +45,7 @@ struct BSP_EDGE {
   U32 face;
 
   VEC3 v1, v2;
+  VEC3 mins, maxs;
 };
 
 struct BSP_LEAF {
diff --git a/src/game/world/trace.cpp b/src/game/world/trace.cpp
index 25c0477..b1f91a3 100644
--- a/src/game/world/trace.cpp
+++ b/src/game/world/trace.cpp
@@ -173,7 +173,21 @@ U8 bsp_trace( BSP_TRACE* trace, BSP* bsp ) {
   return bsp_trace_segment( trace, bsp, bsp->root, start, end );
 }
 
-
+F32 hull_proj_radius( const AABB& hull, VEC3 dir ) {
+  F32 expand = aabb_support_radius( hull, dir );
+  VEC3 half   = (hull.max - hull.min) * 0.5f;
+  F32 r;
+  if( dir.z < BSP_NORM_EPSILON ) {
+    r = (half.x + half.y) * 0.5f;
+  } else
+    r = half.z;
+
+  F32 hypot = r * 1.414213f;
+  F32 a = expand;
+  F32 c = sqrtf( hypot * hypot - a * a );
+
+  return c;
+}
 
 inline U8 point_in_inflated_poly(
   const VEC3& point,
@@ -187,6 +201,7 @@ inline U8 point_in_inflated_poly(
     center = center + face->verts.data[i].pos;
   if( c ) center = center * (1.0f / c);
 
+  VEC3 hullh = ( hull.max - hull.min ) * 0.5f;
   for( U32 i = 0; i < c; ++i ) {
     VEC3 a = face->verts.data[i].pos;
     VEC3 b = face->verts.data[(i+1)%c].pos;
@@ -194,21 +209,39 @@ inline U8 point_in_inflated_poly(
     VEC3 in = vec_cross( norm, e );
     F32 len = vec_len( in );
     if( len <= 0.0001f ) continue;
-    in *= (1.0f/ len);
+    in /= len;
     if( vec_dot( center - a, in ) < 0.0f )
       in = in * -1.0f;
 
     F32 dist   = vec_dot( point - a, in );
-    F32 expand = aabb_support_radius( hull, in );
+    F32 expand = fabsf( in.z ) > 0.001f? hullh.z : hullh.x;
     if( dist < -( expand - BSP_EDGE_TOLERANCE ) )
       return 0;
 
-    // check if plane is aligned to any hull edge in x/y plane
-    if( fabsf( norm.x ) >= BSP_TRACE_EPSILON && fabsf( norm.y ) >= BSP_TRACE_EPSILON ) {
-      // for non-axis-aligned faces the point of contact is infinitely thin
-      if( dist < BSP_EDGE_TOLERANCE )
+    U8 axis = 0;
+    // check if plane is aligned to any axis
+    for( U32 i = 0; i < 3; ++i ) {
+      if( norm[i] < BSP_NORM_EPSILON )
+        ++axis;
+    }
+
+    if( axis == 3 )
+      continue;
+
+
+    if( !axis ) { // project closest hull corner onto plane
+      VEC3 diag = in;
+      diag *= -1;
+      for( U32 i = 0; i < 3; ++i ) {
+        if( diag[i] )
+          diag[i] = copysignf( 1.0f, diag[i] );
+      }
+
+      diag *= hullh;
+      if( vec_dot( point - diag, in ) < 0.f )
         return 0;
     }
+
   }
   return 1;
 }
@@ -226,7 +259,6 @@ U8 bsp_trace_sweep_aabb_to_face(
   if( face->verts.size < 3 )
     return 0;
 
-
   VEC3 norm   = bsp_face_get_normal( face );
   F32  d      = vec_dot( norm, face->verts[0].pos );
   F32  radius = aabb_support_radius( hull, norm );
@@ -235,7 +267,7 @@ U8 bsp_trace_sweep_aabb_to_face(
   F32  s0   = vec_dot( norm, trace->in_start ) - d;
   F32  ndir = vec_dot( norm, dir );
 
-  if( ndir >= 0 ) // dont collide with rear side
+  if( ndir > 0 ) // dont collide with rear side
     return 0;
 
   VEC3 hullv  = hull.max - hull.min;
@@ -293,6 +325,8 @@ U8 bsp_trace_sweep_aabb_to_leaf_edges(
   F32 best = *in_best;
  
   BSP_TRACE besthit = *trace;
+  VEC3 hullh = ( hull.max - hull.min ) * 0.5f;
+
   for( U32 i = 0; i < leaf->edges.size; ++i ) {
     BSP_EDGE* e = &leaf->edges[i];
     BSP_FACE* f = &bsp->faces.data[e->face];
@@ -304,39 +338,48 @@ U8 bsp_trace_sweep_aabb_to_leaf_edges(
     F32  d = e->plane.dist;
     F32  r = aabb_support_radius( hull, n );
 
-    F32 s0   = vec_dot( n, start ) - d;
-    F32 ndir = vec_dot( n, end - start );
+    VEC3 dir  = trace->in_end - trace->in_start;
+    F32  s0   = vec_dot( n, trace->in_start ) - d;
+    F32  ndir = vec_dot( n, dir );
 
-    if( ndir >= 0.f ) continue;
-    if( s0 < -(r + BSP_TRACE_EPSILON) ) continue;
+    if( ndir > 0.f ) continue;
+    if( s0 <= -(r + BSP_TRACE_EPSILON) ) continue;
  
     F32 t_enter = ( r - s0) / ndir;
     F32 t_exit  = (-r - s0) / ndir;
     if( t_enter > t_exit ) { F32 tmp = t_enter; t_enter = t_exit; t_exit = tmp; }
 
-    if( t_exit < 0.f || t_enter > 1.f )
+    if( t_exit < -BSP_TRACE_EPSILON || t_enter > 1.f + BSP_TRACE_EPSILON )
       continue;
 
     F32 t = m_clamp( t_enter, 0.f, 1.f );
-    VEC3 step = start + (end - start) * t;
-
+    VEC3 step = trace->in_start + (dir) * t;
     VEC3 edir = e->v2 - e->v1;
     F32 elen = vec_len( edir );
     if( elen < 0.001f )
       continue;
-    edir *= (1.f / elen);
+    edir /= elen;
 
     F32 along = vec_dot( step - e->v1, edir );
+    F32 expand;
+    if( fabsf( edir.z ) < BSP_NORM_EPSILON )
+      expand = (edir.x > edir.y)? hullh.y : hullh.x;
+    else
+      expand = hullh.z;
+
+    if( along < -( expand + BSP_EDGE_TOLERANCE ) || ( along > elen + expand ) )
+      continue;
+
     VEC3 proj = e->v1 + edir * m_clamp( along, 0.f, elen );
-    F32 dist = vec_dist( proj, step );
     VEC3 ec = vec_cross( edir, n );
     F32 nlen = vec_len( ec );
     if( nlen < 0.001f )
       continue;
-    ec *= (1.f / nlen);
+    ec /= nlen;
+    F32 dist = vec_dot( proj - step, ec );
 
-    F32 expand = aabb_support_radius( hull, ec );
-    if( dist - expand > r * 0.5f )
+    expand = aabb_support_radius( hull, ec );
+    if( fabsf( dist ) > expand )
       continue;
 
     if( t < best ) {
@@ -405,8 +448,7 @@ U8 bsp_trace_sweep_aabb_to_leaf(
       *trace = edgehit;
     else {
       *trace = besthit;
-      if( edgehit.normal.z > besthit.normal.z )
-        trace->normal.z = edgehit.normal.z;
+      trace->normal = edgehit.normal;
     }
     trace->hit = 1;
     return 1;
@@ -460,15 +502,14 @@ U8 bsp_trace_sweep_aabb(
   tin = m_clamp( tin, 0.f, 1.f );
   tout = m_clamp( tout , 0.f, 1.f );
 
-  VEC3 mid = start + dir * tin;
   I32 near = (s_dist > 0.f) ? node->front : node->back;
   I32 far  = (s_dist > 0.f) ? node->back  : node->front;
 
   BSP_TRACE tr_near = *trace;
   BSP_TRACE tr_far  = *trace;
 
-  U8 hit_near = bsp_trace_sweep_aabb( &tr_near, bsp, hull, start, mid, near );
-  U8 hit_far  = bsp_trace_sweep_aabb( &tr_far , bsp, hull, mid,    end, far );
+  U8 hit_near = bsp_trace_sweep_aabb( &tr_near, bsp, hull, start, end, near );
+  U8 hit_far  = bsp_trace_sweep_aabb( &tr_far , bsp, hull, start, end, far );
 
   if( hit_near && hit_far ) {
     *trace = (tr_near.frac <= tr_far.frac) ? tr_near : tr_far;
@@ -480,11 +521,11 @@ U8 bsp_trace_sweep_aabb(
 
   if( tin <= BSP_TRACE_EPSILON || tin >= 1.f - BSP_TRACE_EPSILON ) {
     F32 nudge = (denom >= 0.f ? 1.f : -1.f) * BSP_TRACE_EPSILON;
-    VEC3 nudged = mid + dir * nudge;
+    VEC3 nudged = start + dir * nudge;
     return bsp_trace_sweep_aabb( trace, bsp, hull, nudged, end, far );
   }
 
-  return bsp_trace_sweep_aabb(trace, bsp, hull, mid, end, far );
+  return bsp_trace_sweep_aabb(trace, bsp, hull, start, end, far );
 }
 
 U8 bsp_trace( BSP_TRACE* trace, BSP* bsp, AABB hull ) {