wip on adding edge normals

4 files changed, 190 insertions, 7 deletions

diff --git a/src/game/physics/movement.cpp b/src/game/physics/movement.cpp
index 1e2e973..b2b2ffa 100644
--- a/src/game/physics/movement.cpp
+++ b/src/game/physics/movement.cpp
@@ -257,7 +257,7 @@ F32 gmove_try_move( BSP_TRACE* t, VEC3* pos, VEC3* vel ) {
     F32 dot = vec_dot( *vel, t->normal );
     *pos += wishmove * t->frac;
     // nudge player away from wall
-    *pos += t->normal * BSP_TRACE_EPSILON * 4.f;
+    *pos += t->normal * BSP_TRACE_EPSILON * 2.f;
 
     // avoid clipping planes twice
     // in a rare edge case its possible to get stuck in the plane again after pushing away from it
diff --git a/src/game/world/bsp.cpp b/src/game/world/bsp.cpp
index e163d6e..7c6b9ab 100644
--- a/src/game/world/bsp.cpp
+++ b/src/game/world/bsp.cpp
@@ -1,6 +1,7 @@
 #include "bsp.h"
 #include "../../util/math.h"
 #include "map.h"
+#include "trace.h"
 #include <climits>
 
 const F32 BSP_PORTAL_PLANE_SIZE = 64000.f;
@@ -417,6 +418,110 @@ I32 bsp_build_nodes(
   return nidx;
 }
 
+void bsp_gen_leaf_edges( BSP* bsp, I32 leaf_idx, LIST<BSP_EDGE>* out ) {
+  BSP_LEAF* leaf = &bsp->leaves.data[leaf_idx];
+
+  for( U32 facei = 0; facei < leaf->count; ++facei ) {
+    U32 faceidx = leaf->first + facei;
+    BSP_FACE* face = &bsp->faces.data[faceidx];
+
+    if( face->verts.size < 3 )
+      continue;
+
+    VEC3 facen = bsp_face_get_normal( face );
+    VEC3 center{};
+    for( U32 i = 0; i < face->verts.size; ++i )
+      center = center + face->verts.data[i].pos;
+    center = center / face->verts.size;
+
+    for( U32 i = 0; i < face->verts.size; ++i ) {
+      VEC3 a = face->verts[i].pos;
+      VEC3 b = face->verts[(i+1) % face->verts.size].pos;
+      VEC3 edge = b - a;
+      F32  elen = vec_len( edge );
+      if( elen < 0.0001f )
+        continue;
+      edge = edge * (1.f / elen);
+
+      VEC3 edgen = vec_normalize( vec_cross( facen, edge ) );
+
+      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;
+
+  dv1 = vec_dist( a->v1, b->v2 );
+  dv2 = vec_dist( a->v2, b->v1 );
+
+  if( dv1 < t && dv2 < t )
+    return 1;
+
+  return 0;
+}
+
+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];
+
+    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++;
+      }
+    }
+
+    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 );
+    } );
+  } );
+}
+
+
 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 ) );
@@ -727,6 +832,7 @@ BSP* bsp_build_map( WORLD_MAP* m ) {
   for( U32 i = 0; i < bsp->faces.size; ++i ) {
     bsp->faces.data[i].id = i;
   }
+  // 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 457bcb9..50e8764 100644
--- a/src/game/world/bsp.h
+++ b/src/game/world/bsp.h
@@ -38,10 +38,20 @@ struct BSP_NODE {
   I32 back;
 };
 
+struct BSP_EDGE {
+  BSP_PLANE plane;
+  U32 face;
+  U8 avgc;
+
+  VEC3 v1, v2;
+};
+
 struct BSP_LEAF {
   U32 first;
   U32 count;
   I32 cluster;
+
+  LIST<BSP_EDGE> edges;
 };
 
 struct BSP_WINDING {
@@ -106,3 +116,10 @@ inline SURF_PROPS* bsp_face_get_props( WORLD_MAP* w, BSP_FACE* s ) {
     map_props_get_special( w, s->propid ) :
     &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;
+  return vec_normalize( vec_cross( v1 - v0, v2 - v0 ) );
+}
diff --git a/src/game/world/trace.cpp b/src/game/world/trace.cpp
index 3548fa8..6d1e8db 100644
--- a/src/game/world/trace.cpp
+++ b/src/game/world/trace.cpp
@@ -1,6 +1,7 @@
 #include "trace.h"
 #include "../../util/math.h"
 #include "bsp.h"
+#include "map.h"
 
 // i have no idea how this works tbh i pasted this
 // todo : backface culling (return 0 if d < BSP_TRACE_EPSILON)
@@ -172,12 +173,7 @@ U8 bsp_trace( BSP_TRACE* trace, BSP* bsp ) {
   return bsp_trace_segment( trace, bsp, bsp->root, start, end );
 }
 
-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;
-  return vec_normalize( vec_cross( v1 - v0, v2 - v0 ) );
-}
+
 
 inline U8 point_in_inflated_poly(
   const VEC3& point,
@@ -268,6 +264,67 @@ U8 bsp_trace_sweep_aabb_to_face(
   return 1;
 }
 
+U8 bsp_trace_sweep_aabb_to_leaf_edges(
+  BSP* bsp,
+  BSP_TRACE* trace,
+  const AABB& hull,
+  const VEC3& start,
+  const VEC3& end,
+  I32 leaf_idx,
+  F32* in_best
+) {
+  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];
+    BSP_FACE* f = &bsp->faces.data[e->face];
+
+    if( f->propid == MAPPROP_SKYBOX )
+      continue;
+
+    VEC3 n = e->plane.normal;
+    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 );
+
+    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 );
+
+    VEC3 step = start + (end - start) * t;
+
+    if( !point_in_inflated_poly( step, f, hull, n ) )
+      continue;
+
+    if( t < best ) {
+      best = t;
+      *in_best = best;
+      besthit.frac = t;
+      besthit.point = step;
+      besthit.normal = n;
+      besthit.propid = f->propid;
+      besthit.faceid = e->face;
+      besthit.leafid = leaf_idx;
+      hit = 1;
+    }
+  }
+
+  if( hit ) {
+    *trace = besthit;
+    trace->hit = 1;
+  }
+
+  return hit;
+}
+
 U8 bsp_trace_sweep_aabb_to_leaf(
   BSP* bsp,
   BSP_TRACE* trace,
@@ -301,6 +358,9 @@ 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;
     trace->hit = 1;