edge planes )))bsp-edges

3 files changed, 137 insertions, 93 deletions

diff --git a/src/game/world/bsp.cpp b/src/game/world/bsp.cpp
index 7c6b9ab..7f72e52 100644
--- a/src/game/world/bsp.cpp
+++ b/src/game/world/bsp.cpp
@@ -135,7 +135,6 @@ LIST<BSP_PLANE> bsp_map_get_planes( WORLD_MAP* map ) {
   return ret;
 }
 
-
 LIST<BSP_FACE> bsp_map_faces_from_walls( WORLD_MAP* map ) {
   LIST<BSP_FACE> ret{};
 
@@ -169,7 +168,6 @@ LIST<BSP_FACE> bsp_map_faces_from_walls( WORLD_MAP* map ) {
     f.verts.push( vertices[1] );
     f.verts.push( vertices[0] );
     f.verts.push( vertices[3] );
-
     ret.push( f );
   };
 
@@ -418,8 +416,42 @@ I32 bsp_build_nodes(
   return nidx;
 }
 
-void bsp_gen_leaf_edges( BSP* bsp, I32 leaf_idx, LIST<BSP_EDGE>* out ) {
+U8 bsp_edge_is_shared( BSP* bsp, VEC3 edge1a, VEC3 edge1b, VEC3 center, VEC3 ecross, U32 facei ) {
+  for( U32 i = 0; i < bsp->faces.size; ++i ) {
+    if( facei == i )
+      continue;
+
+    BSP_FACE* other = &bsp->faces[i];
+    if( other->verts.size < 3 )
+      continue;
+
+    VEC3 otherc{};
+    for( U32 vi = 0; vi < other->verts.size; ++vi )
+      otherc += other->verts[vi].pos;
+    otherc /= other->verts.size;
+
+    for( U32 vi = 0; vi < other->verts.size; ++vi ) {
+      VEC3 edge2a = other->verts[vi].pos;
+      VEC3 edge2b = other->verts[(vi + 1) % other->verts.size].pos;
+
+      F32 t = BSP_EDGE_TOLERANCE;
+      U8 match = ( vec_dist( edge1a, edge2a ) < t && vec_dist( edge1b, edge2b ) < t ) ||
+                 ( vec_dist( edge1a, edge2b ) < t && vec_dist( edge1b, edge2a ) < t );
+
+      if( !match )
+        continue;
+
+      if( vec_dot( ecross, otherc - edge2a ) < BSP_NORM_EPSILON )
+        return 1;
+    }
+  }
+
+  return 0;
+}
+
+void bsp_gen_leaf_edges( BSP* bsp, I32 leaf_idx ) {
   BSP_LEAF* leaf = &bsp->leaves.data[leaf_idx];
+  LIST<BSP_EDGE>* edges = &leaf->edges;
 
   for( U32 facei = 0; facei < leaf->count; ++facei ) {
     U32 faceidx = leaf->first + facei;
@@ -432,7 +464,7 @@ void bsp_gen_leaf_edges( BSP* bsp, I32 leaf_idx, LIST<BSP_EDGE>* out ) {
     VEC3 center{};
     for( U32 i = 0; i < face->verts.size; ++i )
       center = center + face->verts.data[i].pos;
-    center = center / face->verts.size;
+    center /= face->verts.size;
 
     for( U32 i = 0; i < face->verts.size; ++i ) {
       VEC3 a = face->verts[i].pos;
@@ -441,87 +473,50 @@ void bsp_gen_leaf_edges( BSP* bsp, I32 leaf_idx, LIST<BSP_EDGE>* out ) {
       F32  elen = vec_len( edge );
       if( elen < 0.0001f )
         continue;
-      edge = edge * (1.f / elen);
-
-      VEC3 edgen = vec_normalize( vec_cross( facen, edge ) );
+      edge *= (1.f / elen);
 
-      if( vec_dot( edgen, center - a ) > 0.f )
-        edgen = edgen * -1.f;
-
-      if( fabsf( vec_dot( edgen, facen ) ) > 0.9999f )
-        continue;
-
-      BSP_EDGE bedge;
-      bedge.plane.normal = edgen;
-      bedge.plane.dist   = vec_dot( edgen, a );
-      bedge.face         = faceidx;
-      bedge.v1           = a;
-      bedge.v2           = b;
-      bedge.avgc         = 1;
-      out->push( bedge );
-    }
-  }
-}
-
-U8 bsp_edge_is_adjacent( BSP_EDGE* a, BSP_EDGE* b ) {
-  F32 t = BSP_EDGE_TOLERANCE;
-  F32 dv1 = vec_dist( a->v1, b->v1 );
-  F32 dv2 = vec_dist( a->v2, b->v2 );
-
-  if( dv1 < t && dv2 < t )
-    return 1;
+      for( U32 axis = 0; axis < 3; ++axis ) {
+        VEC3 cross = vec_cross( edge, vec3_axis[axis] );
+        F32 clen = vec_len( cross );
+        if( clen < 0.001f )
+          continue;
+        cross *= (1.f / clen);
+        if( vec_dot( cross, center - a ) > 0.f )
+          cross *= -1.f;
 
-  dv1 = vec_dist( a->v1, b->v2 );
-  dv2 = vec_dist( a->v2, b->v1 );
+        if( fabsf( vec_dot( cross, facen ) ) > 0.995f )
+          continue;
 
-  if( dv1 < t && dv2 < t )
-    return 1;
+        if( !bsp_edge_is_shared( bsp, a, b, center, cross, faceidx ) )
+          continue;
 
-  return 0;
-}
+        F32 d = vec_dot( cross, a );
+        BSP_PLANE plane = { cross, d };
+        U8 dupe = 0;
+        for( U32 i = 0; i < edges->size; ++i ) {
+          if( edges->data[i].plane == plane ) { dupe = 1; break; }
+        }
 
-LIST<BSP_EDGE> bsp_average_leaf_edges( BSP* bsp, LIST<BSP_EDGE>* edges ) {
-  LIST<BSP_EDGE> out{};
-  for( U32 i = 0; i < edges->size; ++i ) {
-    BSP_EDGE a = edges->data[i];
+        if( dupe )
+          continue;
 
-    for( U32 i2 = 0; i2 < out.size; ++i2 ) {
-      BSP_EDGE* b = &out.data[i2];
-      if( bsp_edge_is_adjacent( &a, b ) ) {
-        VEC3 avg = vec_normalize( a.plane.normal + b->plane.normal * b->avgc );
-        b->plane.normal = avg;
-        a.plane.normal = avg;
-        b->avgc++;
+        BSP_EDGE e;
+        e.plane = plane;
+        e.face = faceidx;
+        e.v1 = a;
+        e.v2 = b;
+        edges->push( e );
       }
     }
-
-    a.avgc = 1;
-    out.push( a );
   }
-
-  return out;
 }
 
 void bsp_gen_leaf_edges( BSP* bsp ) {
   LIST<BSP_EDGE> edges;
   for( U32 i = 0; i < bsp->leaves.size; ++i )
-    bsp_gen_leaf_edges( bsp, i, &edges );
-
-  edges = bsp_average_leaf_edges( bsp, &edges );
-  edges.each( fn( BSP_EDGE* e ) {
-    U32 facei = e->face;
-
-    bsp->leaves.each( fn( BSP_LEAF* l ) {
-      U32 starti = l->first;
-      U32 endi = l->first + l->count;
-
-      if( facei >= starti && facei < endi )
-        l->edges.push( *e );
-    } );
-  } );
+    bsp_gen_leaf_edges( bsp, i );
 }
 
-
 inline void bsp_plane_basis( const VEC3& norm, VEC3* u, VEC3* v ) {
   VEC3 a = fabsf( norm.x ) > 0.9f ? VEC3{ 0, 1, 0 } : VEC3{ 1, 0, 0 };
   *u = vec_normalize( vec_cross( a, norm ) );
@@ -830,9 +825,10 @@ BSP* bsp_build_map( WORLD_MAP* m ) {
 
   bsp->root = bsp_build_nodes( bsp, planes, faces, 0 );
   for( U32 i = 0; i < bsp->faces.size; ++i ) {
+    bsp_face_calc_extents( &bsp->faces.data[i] );
     bsp->faces.data[i].id = i;
   }
-  // bsp_gen_leaf_edges( bsp );
+  bsp_gen_leaf_edges( bsp );
   bsp_gen_render_vertices( bsp );
 
   bsp_build_portals( bsp );
diff --git a/src/game/world/bsp.h b/src/game/world/bsp.h
index 50e8764..8892108 100644
--- a/src/game/world/bsp.h
+++ b/src/game/world/bsp.h
@@ -30,6 +30,8 @@ struct BSP_FACE {
   I32 id;
   LIST<MAP_VERTEX> verts{};
   LIST<VERTEX3D> render_verts{};
+  VEC3 mins;
+  VEC3 maxs;
 };
 
 struct BSP_NODE {
@@ -41,7 +43,6 @@ struct BSP_NODE {
 struct BSP_EDGE {
   BSP_PLANE plane;
   U32 face;
-  U8 avgc;
 
   VEC3 v1, v2;
 };
@@ -117,9 +118,26 @@ inline SURF_PROPS* bsp_face_get_props( WORLD_MAP* w, BSP_FACE* s ) {
     &w->props[s->propid];
 }
 
-inline VEC3 bsp_face_get_normal( const BSP_FACE* f ){
-  const VEC3 v0 = f->verts.data[0].pos;
-  const VEC3 v1 = f->verts.data[1].pos;
-  const VEC3 v2 = f->verts.data[2].pos;
+inline VEC3 bsp_face_get_normal( BSP_FACE* f ){
+  VEC3 v0 = f->verts.data[0].pos;
+  VEC3 v1 = f->verts.data[1].pos;
+  VEC3 v2 = f->verts.data[2].pos;
   return vec_normalize( vec_cross( v1 - v0, v2 - v0 ) );
 }
+
+inline void bsp_face_calc_extents( BSP_FACE* f ) {
+  VEC3 mins{ +INFINITY, +INFINITY, +INFINITY }, maxs{ -INFINITY, -INFINITY, -INFINITY };
+  for( U32 i = 0; i < f->verts.size; ++i ) {
+    VEC3 v = f->verts.data[i].pos;
+    mins.x = min( mins.x, v.x );
+    mins.y = min( mins.y, v.y );
+    mins.z = min( mins.z, v.z );
+
+    maxs.x = max( maxs.x, v.x );
+    maxs.y = max( maxs.y, v.y );
+    maxs.z = max( maxs.z, v.z );
+  }
+
+  f->mins = mins;
+  f->maxs = maxs;
+}
diff --git a/src/game/world/trace.cpp b/src/game/world/trace.cpp
index 6d1e8db..61e3da4 100644
--- a/src/game/world/trace.cpp
+++ b/src/game/world/trace.cpp
@@ -218,16 +218,18 @@ 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 );
+  VEC3 hullh  = (hull.max - hull.min) * 0.5f;
+  AABB fhull  = { face->mins - hullh, face->maxs + hullh };
+  VEC3 norm   = bsp_face_get_normal( face );
+  F32  d      = vec_dot( norm, face->verts[0].pos );
+  F32  radius = aabb_support_radius( hull, norm );
 
-  VEC3 dir  = end - start;
+  VEC3 dir  = trace->in_end - trace->in_start;
   F32  s0   = vec_dot( norm, trace->in_start ) - d;
   F32  ndir = vec_dot( norm, trace->in_end - trace->in_start );
 
   if( fabsf( s0 ) <= radius + BSP_TRACE_EPSILON ) {
-    if( point_in_inflated_poly( start, face, hull, norm ) ) {
+    if( aabb_contains_point( fhull, start ) && point_in_inflated_poly( start, face, hull, norm ) ) {
       trace->hit = 1;
       trace->frac = 0.f;
       trace->startsolid = 1;
@@ -250,7 +252,10 @@ U8 bsp_trace_sweep_aabb_to_face(
     return 0;
 
   F32 t = m_clamp( t_enter, 0.f, 1.f );
-  VEC3 step = start + dir * t;
+  VEC3 step = trace->in_start + dir * t;
+
+  if( !aabb_contains_point( fhull, step ) )
+    return 0;
 
   if( !point_in_inflated_poly( step, face, hull, norm ) )
     return 0;
@@ -276,7 +281,7 @@ U8 bsp_trace_sweep_aabb_to_leaf_edges(
   BSP_LEAF* leaf = &bsp->leaves.data[leaf_idx];
   U8 hit = 0;
   F32 best = *in_best;
-  
+ 
   BSP_TRACE besthit = *trace;
   for( U32 i = 0; i < leaf->edges.size; ++i ) {
     BSP_EDGE* e = &leaf->edges[i];
@@ -294,15 +299,31 @@ U8 bsp_trace_sweep_aabb_to_leaf_edges(
 
     if( ndir >= 0.f ) continue;
     if( s0 < -(r + BSP_TRACE_EPSILON) ) continue;
-    
-    F32 t = (-r - s0) / ndir;
-    if( t < 0.f || t > 1.f ) continue;
-    t = m_clamp( t, 0.f, 1.f );
+ 
+    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 < -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;
 
-    if( !point_in_inflated_poly( step, f, hull, n ) )
+    VEC3 edir = e->v2 - e->v1;
+    F32 elen = vec_len( edir );
+    if( elen < 0.001f )
       continue;
+    edir *= (1.f / elen);
+
+    F32 along = vec_dot( step - e->v1, edir );
+    VEC3 proj = e->v1 + edir * m_clamp( along, 0.f, elen );
+    F32 dist = vec_dist( proj, step );
+    if( dist > BSP_TRACE_EPSILON ) {
+      F32 expand = aabb_support_radius( hull, vec_normalize( step - proj ) );
+      if( dist < -(expand) || dist > expand )
+        continue;
+    }
 
     if( t < best ) {
       best = t;
@@ -338,6 +359,7 @@ U8 bsp_trace_sweep_aabb_to_leaf(
   F32 best = FLT_MAX;
 
   BSP_TRACE besthit = *trace;
+  BSP_TRACE edgehit = *trace;
 
   for( U32 i = 0; i < leaf->count; ++i ) {
     U32 face_idx = leaf->first + i;
@@ -358,14 +380,22 @@ U8 bsp_trace_sweep_aabb_to_leaf(
     }
   }
 
-  U8 ehit = bsp_trace_sweep_aabb_to_leaf_edges( bsp, trace, hull, start, end, leaf_idx, &best );
-  if( !hit ) hit = ehit;
-
-  if( hit ) {
-    *trace = besthit;
+  U8 ehit = bsp_trace_sweep_aabb_to_leaf_edges( bsp, &edgehit, hull, start, end, leaf_idx, &best );
+
+  if( hit || ehit ) {
+    if( ehit && !hit )
+      *trace = edgehit;
+    else if( !ehit && hit )
+      *trace = besthit;
+    else if( edgehit.frac < besthit.frac )
+      *trace = edgehit;
+    else
+      *trace = besthit;
     trace->hit = 1;
+    return 1;
   }
-  return hit;
+
+  return 0;
 }
 
 U8 bsp_trace_sweep_aabb(