1 files changed, 104 insertions, 2 deletions

diff --git a/src/game/world/bsp.cpp b/src/game/world/bsp.cpp
index e163d6e..7f72e52 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;
@@ -134,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{};
 
@@ -168,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 );
   };
 
@@ -417,6 +416,107 @@ I32 bsp_build_nodes(
   return nidx;
 }
 
+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;
+    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 /= 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 *= (1.f / elen);
+
+      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;
+
+        if( fabsf( vec_dot( cross, facen ) ) > 0.995f )
+          continue;
+
+        if( !bsp_edge_is_shared( bsp, a, b, center, cross, faceidx ) )
+          continue;
+
+        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; }
+        }
+
+        if( dupe )
+          continue;
+
+        BSP_EDGE e;
+        e.plane = plane;
+        e.face = faceidx;
+        e.v1 = a;
+        e.v2 = b;
+        edges->push( e );
+      }
+    }
+  }
+}
+
+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 );
+}
+
 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 ) );
@@ -725,8 +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_render_vertices( bsp );
 
   bsp_build_portals( bsp );