bunch o stuff

2 files changed, 91 insertions, 3 deletions

diff --git a/src/game/world/bsp.cpp b/src/game/world/bsp.cpp
index 9aa94d7..a95a693 100644
--- a/src/game/world/bsp.cpp
+++ b/src/game/world/bsp.cpp
@@ -637,7 +637,89 @@ U8 pvs_get( BSP_BITSET* pvs, U32 count, U32 cluster, U32 seen ) {
   U32 w = seen / 32, b = seen % 32;
   if( base + w >= pvs->size ) return 0;
 
-  return ( pvs->data[base + w] >> b) & 1u;
+  return (pvs->data[base + w] >> b) & 1u;
+}
+
+void bsp_build_pvs( BSP* bsp ) {
+  U32 nclusters = bsp->leaves.size;
+  bsp->pvs_bits.clear();
+  bsp->clusters.clear();
+  bsp->clusters.reserve( nclusters );
+
+  LIST<LIST<I32>> leaf_portals;
+  leaf_portals.resize( nclusters );
+
+  for( U32 i = 0; i < bsp->portals.size; ++i ) {
+    BSP_PORTAL* p = &bsp->portals.data[i];
+    I32 lf = bsp_leaf_index( p->front );
+    I32 rf = bsp_leaf_index( p->back );
+
+    leaf_portals.data[lf].push( i );
+    leaf_portals.data[rf].push( i );
+  }
+
+  for( U32 i = 0; i < nclusters; ++i ) {
+    BSP_CLUSTER* c = &bsp->clusters.data[i];
+    c->first = 0;
+    c->count = 0;
+    c->pvs_off = 0;
+  }
+
+  for( U32 from = 0; from < nclusters; ++from ) {
+    LIST<I32>* plist = &leaf_portals.data[from];
+    pvs_set( &bsp->pvs_bits, nclusters, from, from );
+
+    LIST<BSP_PORTAL_QUEUE> queue;
+    for( U32 i = 0; i < plist->size; ++i ) {
+      I32 pid = plist->data[i];
+      BSP_PORTAL* p = &bsp->portals.data[pid];
+
+      BSP_PORTAL_QUEUE it{
+        .front = (I32)from,
+        .frustum = p->w
+      };
+
+      queue.push( it ) ;
+    }
+
+    while( queue.size ) {
+      BSP_PORTAL_QUEUE it = queue.pop();
+      LIST<I32>* plist = &leaf_portals.data[it.front];
+
+      for( U32 i = 0; plist->size; ++i ) {
+        BSP_PORTAL* p = &bsp->portals.data[plist->data[i]];
+        I32 lf = bsp_leaf_index( p->front );
+        I32 lb = bsp_leaf_index( p->back );
+
+        I32 neighbor = (lf == it.front) ? lb : (lb == it.front) ? lf : -1;
+        if( neighbor < 0 )
+          continue;
+
+        BSP_WINDING next_w;
+        if( !bsp_winding_intersect_plane( &p->plane, &it.frustum, &p->w, &next_w ) )
+          continue;
+
+        if( !pvs_get( &bsp->pvs_bits, nclusters, from, (U32)neighbor ) ) {
+          pvs_set( &bsp->pvs_bits, nclusters, from, (U32)neighbor );
+
+          LIST<I32>* nbr_plist = &leaf_portals.data[neighbor];
+          for( U32 i2 = 0; i2 < nbr_plist->size; ++i2 ) {
+            BSP_PORTAL* nbr_p = &bsp->portals.data[nbr_plist->data[i2]];
+            if( nbr_p == p )
+              continue;
+
+            BSP_WINDING clipped = next_w;
+            if( bsp_winding_intersect_plane( &nbr_p->plane, &clipped, &nbr_p->w, &clipped ) ) {
+              BSP_PORTAL_QUEUE n{};
+              n.front = neighbor;
+              n.frustum = clipped;
+              queue.push( n );
+            }
+          }
+        }
+      }
+    }
+  }
 }
 
 BSP* bsp_build_map( WORLD_MAP* m ) {
@@ -647,12 +729,13 @@ BSP* bsp_build_map( WORLD_MAP* m ) {
   LIST<BSP_PLANE> planes = bsp_map_get_planes( m );
 
   bsp->root = bsp_build_nodes( bsp, planes, faces, 0 );
-  U32 vertc = 0;
-  m->polygons.each( fn( MAP_POLYGON* p ) { vertc += p->vertices.size; } );
   for( U32 i = 0; i < bsp->faces.size; ++i ) {
     bsp->faces.data[i].id = i;
   }
   bsp_gen_render_vertices( bsp );
+
+  bsp_build_portals( bsp );
+  bsp_build_pvs( bsp );
   return bsp;
 }
 
diff --git a/src/game/world/bsp.h b/src/game/world/bsp.h
index 439fce1..457bcb9 100644
--- a/src/game/world/bsp.h
+++ b/src/game/world/bsp.h
@@ -71,6 +71,11 @@ struct BSP_PORTAL_NODE {
   BSP_WINDING w;
 };
 
+struct BSP_PORTAL_QUEUE {
+  I32 front;
+  BSP_WINDING frustum;
+};
+
 struct BSP_BITSET : public LIST<U32> {};
 
 struct BSP {