path: root/src/game/world/bsp.cpp

#include "bsp.h"
#include "../../util/math.h"
#include "map.h"
#include "trace.h"
#include <climits>

const F32 BSP_PORTAL_PLANE_SIZE = 64000.f;

struct MAP_TRI {
  MAP_VERTEX p0, p1, p2;
};

void bsp_face_gen_render_verts( BSP* bsp, BSP_FACE* f ) {
  LIST<VERTEX3D> vertices;
  vertices.reserve( f->verts.size );

  SURF_PROPS* props = map_get_props( bsp->map, f->propid );

  f->verts.each( fn( MAP_VERTEX* v ) {
    VERTEX3D v3d;
    v3d.pos = { v->pos.x, v->pos.z, v->pos.y };
    v3d.uv = v->uv;
    v3d.clr = v->clr * props->clr;
    v3d.sampler = 0;
    vertices.push( v3d );
  } );

  f->render_verts = triangle_fan_to_list( vertices.data, vertices.size );
}

void bsp_gen_render_vertices( BSP* bsp ) {
  bsp->faces.each( fn( BSP_FACE* f ) {
    bsp_face_gen_render_verts( bsp, f );
  } );
}

LIST<BSP_PLANE> bsp_map_get_wall_planes( WORLD_MAP* map ) {
  LIST<BSP_PLANE> ret{};

  auto calc_wall_plane = fn( MAP_WALL* w ) {
    VEC3 dir = w->end - w->start;
    VEC3 normal = vec_normalize( { -dir.y, dir.x, 0.0f } );
    F32 dist = vec_dot( normal, w->start );

    BSP_PLANE p = { normal, dist };
    for( U32 i = 0; i < ret.size; ++i ) {
      if( ret[i] == p )
        return;
    }

    ret.push( p );
  };

  map->walls.each( calc_wall_plane );
  for( U32 i = 0; i < 4; ++i )
    calc_wall_plane( &map->skybox.walls[i] );

  return ret;
}


LIST<MAP_TRI> bsp_map_triangulate_planes( WORLD_MAP* map ) {
  LIST<MAP_TRI> ret;

  auto triangulate_plane = fn( MAP_POLYGON* p ) {
    MAP_VERTEX* start = &p->vertices[0];
    MAP_VERTEX* last = &p->vertices[1];
    for( U32 i = 2; i < p->vertices.size; ++i ) {
      MAP_TRI tri = MAP_TRI{
        *start,
        *last,
        p->vertices[i]
      };

      last = &p->vertices[i];
      ret.push( tri );
    }
  };

  map->polygons.each( triangulate_plane );
  triangulate_plane( &map->skybox.polygons[0] );
  triangulate_plane( &map->skybox.polygons[1] );

  return ret;
}

LIST<BSP_PLANE> bsp_map_get_tri_planes( WORLD_MAP* map ) {
  LIST<BSP_PLANE> ret;
  LIST<MAP_TRI> tris = bsp_map_triangulate_planes( map );

  tris.each( fn( MAP_TRI* tri ) {
    VEC3 cross = vec_cross( tri->p1.pos - tri->p0.pos, tri->p2.pos - tri->p0.pos );
    VEC3 normal = vec_normalize( cross );
    F32 dist = vec_dot( normal, tri->p0.pos );

    BSP_PLANE p = { normal, dist };
    for( U32 i = 0; i < ret.size; ++i ) {
      if( ret[i] == p )
        return;
    }

    ret.push( p );
  } );

  return ret;
}

LIST<BSP_PLANE> bsp_map_get_planes( WORLD_MAP* map ) {
  LIST<BSP_PLANE> ret;

  LIST<BSP_PLANE> walls = bsp_map_get_wall_planes( map );
  LIST<BSP_PLANE> floors = bsp_map_get_tri_planes( map );

  ret.push_list( walls );
  ret.push_list( floors );

  // probably unnecessary, slow as fuck
  // remove any dupes in case a polygon ends up the same as a wall
  // unlikely but dont wanna run into the edge case
  // this wont run that much anyway
  // maybe remove later
  for( U32 i = 0; i < ret.size; ++i ) {
    BSP_PLANE* p = &ret[i];
    for( U32 i2 = 0; i2 < ret.size; ++i2 ) {
      if( i == i2 )
        continue;

      if( ret.data[i2] == *p ) {
        ret.erase( i );
        --i;
      }
    }
  }

  return ret;
}


LIST<BSP_FACE> bsp_map_faces_from_walls( WORLD_MAP* map ) {
  LIST<BSP_FACE> ret{};

  auto triangulate_wall = fn( MAP_WALL* w ) {
    SURF_PROPS* p = wall_get_props( map, w );
    VEC3 points[] = {
      { w->start.x, w->start.y, w->start.z },
      { w->end.x, w->end.y, w->start.z },
      { w->end.x, w->end.y, w->start.z + w->end.z },
      { w->start.x, w->start.y, w->start.z + w->end.z },
    };

    VEC2 uvs[] = {
      { w->uvstart.x, 1.f - w->uvend.y },
      { 1.f - w->uvend.x, 1.f - w->uvend.y },
      { 1.f - w->uvend.x, w->uvstart.y },
      { w->uvstart.x, w->uvstart.y },
    };

    MAP_VERTEX vertices[4];
    for( U32 i = 0; i < 4; ++i ) {
      vertices[i] = {
        .pos = points[i],
        .uv = uvs[i],
        .clr = p->clr,
      };
    }

    BSP_FACE f{ .propid = w->propid };
    f.verts.push( vertices[2] );
    f.verts.push( vertices[1] );
    f.verts.push( vertices[0] );
    f.verts.push( vertices[3] );

    ret.push( f );
  };

  map->walls.each( triangulate_wall );
  for( U32 i = 0; i < 4; ++i ) triangulate_wall( &map->skybox.walls[i] );

  return ret;
}

LIST<BSP_FACE> bsp_map_faces_from_planes( WORLD_MAP* map ) {
  LIST<BSP_FACE> ret;

  auto triangulate_plane = fn( MAP_POLYGON* p ) {
    MAP_VERTEX* start = &p->vertices[0];
    MAP_VERTEX* last = &p->vertices[1];
    for( U32 i = 2; i < p->vertices.size; ++i ) {
      BSP_FACE f = { .propid = p->propid };
      f.verts.push( *start );
      f.verts.push( *last );
      f.verts.push( p->vertices[i] );

      ret.push( f );
      last = &p->vertices[i];
    }
  };

  map->polygons.each( triangulate_plane );
  triangulate_plane( &map->skybox.polygons[0] );
  triangulate_plane( &map->skybox.polygons[1] );

  return ret;
}

LIST<BSP_FACE> bsp_map_get_faces( WORLD_MAP* map ) {
  LIST<BSP_FACE> ret;

  LIST<BSP_FACE> walls = bsp_map_faces_from_walls( map );
  LIST<BSP_FACE> floors = bsp_map_faces_from_planes( map );

  ret.emplace_list( walls );
  ret.emplace_list( floors );

  return ret;
}

inline I32 point_classify( const BSP_PLANE& plane, const VEC3& point ) {
  F32 side = bsp_plane_dist( plane, point );
  if( side > BSP_NORM_EPSILON )
    return BSP_SIDE_FRONT;
  else if( side < -BSP_NORM_EPSILON )
    return BSP_SIDE_BACK;
  else
    return BSP_SIDE_ON;
}

inline I32 polygon_classify(
  const BSP_PLANE& plane,
  const BSP_FACE* face,
  I32* out_fr = 0,
  I32* out_bk = 0
) {
  I32 cf = 0, cb = 0;
  for( U32 i = 0; i < face->verts.size; ++i ) {
    I32 side = point_classify( plane, face->verts.data[i].pos );
    if( side & BSP_SIDE_FRONT )
      ++cf;
    else if( side & BSP_SIDE_BACK )
      ++cb;
  }

  if( out_fr )
    *out_fr = cf;
  if( out_bk )
    *out_bk = cb;

  if( cf && cb ) return BSP_SIDE_SPAN;
  if( cf ) return BSP_SIDE_FRONT;
  if( cb ) return BSP_SIDE_BACK;
  return BSP_SIDE_ON;
}

STAT polygon_split( const BSP_PLANE& plane, const BSP_FACE* in, BSP_FACE* out_fr, BSP_FACE* out_bk ) {
  LIST<MAP_VERTEX> front, back;
  STAT stat = STAT_ERR;

  for( U32 i = 0; i < in->verts.size; ++i ) {
    U32 i2 = (i+1) % in->verts.size;
    MAP_VERTEX* a = &in->verts.data[i];
    MAP_VERTEX* c = &in->verts.data[i2];

    F32 da = bsp_plane_dist( plane, a->pos );
    F32 dc = bsp_plane_dist( plane, c->pos );

    U8 afront = da > BSP_NORM_EPSILON;
    U8 aback  = da < -BSP_NORM_EPSILON;
    U8 cfront = dc > BSP_NORM_EPSILON;
    U8 cback  = dc < -BSP_NORM_EPSILON;

    if( !aback )  front.push( *a );
    if( !afront ) back.push( *a );

    if( (afront && cback) || (aback && cfront) ) {
      F32 t = m_clamp( da / (da - dc), 0.f, 1.f );
      VEC3 isec = a->pos + (c->pos - a->pos) * t;
      VEC2 uv = a->uv + (c->uv - a->uv) * t;
      CLR clr = a->clr + (c->clr - a->clr) * t;
      MAP_VERTEX v = { .pos = isec, .uv = uv, .clr = clr };
      front.push( v );
      back.push( v );
    }
  }

  if( front.size > 2 ) {
    out_fr->propid = in->propid;
    out_fr->verts = front;
    stat = STAT_OK;
  }
  if( back.size > 2 ) {
    out_bk->propid = in->propid;
    out_bk->verts = back;
    stat = STAT_OK;
  }

  return stat;
}

I32 bsp_splitter_cost( const BSP_PLANE& plane, const LIST<BSP_FACE>& faces ) {
  I32 splits = 0, front = 0, back = 0;
  for( U32 i = 0; i < faces.size; ++i ) {
    I32 side = polygon_classify( plane, &faces.data[i], 0, 0 );
    if( side == BSP_SIDE_SPAN ) ++splits;
    else if( side == BSP_SIDE_FRONT ) ++front;
    else if( side == BSP_SIDE_BACK ) ++back;
    else { ++front; ++back; }
  }

  I32 diff = ( front > back ) ? front - back : back - front;
  return splits * 8 + diff;
}

I32 bsp_calc_splitter_index( const LIST<BSP_PLANE>& planes, const LIST<BSP_FACE>& faces ) {
  I32 best = -1;
  I32 bestc = INT_MAX;

  for( U32 i = 0; i < planes.size; ++i ) {
    I32 cost = bsp_splitter_cost( planes.data[i], faces );
    if( cost < bestc ) {
      best = i;
      bestc = cost;
    }
  }

  return best;
}

U8 bsp_is_convex_cluster( const LIST<BSP_FACE>& faces ) {
  for( U32 i = 0; i < faces.size; ++i ) {
    VEC3 e1 = faces.data[i].verts[1].pos - faces.data[i].verts[0].pos;
    VEC3 e2 = faces.data[i].verts[2].pos - faces.data[i].verts[0].pos;
    VEC3 norm = vec_normalize( vec_cross( e1, e2 ) );
    F32 dist = vec_dot( norm, faces.data[i].verts[0].pos );
    BSP_PLANE plane{ norm, dist };
    for( U32 i2 = 0; i2 < faces.size; ++i2 ) {
      if( i == i2 )
        continue;

      if( polygon_classify( plane, &faces.data[i2], 0, 0 ) == BSP_SIDE_SPAN )
        return 0;
    }
  }

  return 1;
}

I32 bsp_insert_leaf( BSP* bsp, LIST<BSP_FACE>& faces ) {
  BSP_LEAF leaf{};
  leaf.first = bsp->faces.size;
  leaf.count = faces.size;
  leaf.cluster = -1; // todo: pvs
  bsp->faces.push_list( faces );
  bsp->leaves.push( leaf );
  return ~( (I32)bsp->leaves.size - 1 );
}

I32 bsp_build_nodes(
  BSP* bsp,
  LIST<BSP_PLANE>& planes,
  LIST<BSP_FACE>& faces,
  I32 depth ) {
  if( faces.size == 0 )
    return bsp_insert_leaf( bsp, faces );
  if( depth > BSP_DEPTH_MAX || bsp_is_convex_cluster( faces ) )
    return bsp_insert_leaf( bsp, faces );

  I32 splitter_idx = bsp_calc_splitter_index( planes, faces );
  if( splitter_idx < 0 ) return bsp_insert_leaf( bsp, faces );

  BSP_PLANE split = planes.data[splitter_idx];

  LIST<BSP_FACE> front, back, coplane;
  for( U32 i = 0; i < faces.size; ++i ) {
    BSP_FACE* f = &faces.data[i];
    I32 frontc = 0, backc = 0;
    I32 side = polygon_classify( split, f, &frontc, &backc );
    if( side == BSP_SIDE_FRONT )
      front.push( *f );
    else if( side == BSP_SIDE_BACK )
      back.push( *f );
    else if( side == BSP_SIDE_ON )
      coplane.push( *f );
    else {
      BSP_FACE fr{}, bk{};
      if( OK( polygon_split( split, f, &fr, &bk ) ) )  {
        if( fr.verts.size > 2 ) front.push( fr );
        if( bk.verts.size > 2 ) back.push( bk );
      }
    }
  }

  BSP_NODE node{};
  node.plane = split;
  I32 nidx = bsp->nodes.size;
  bsp->nodes.push( node );

  LIST<BSP_PLANE> child_planes;
  child_planes.reserve( planes.size > 0 ? planes.size - 1 : 0 );
  for( I32 i = 0; i < planes.size; ++i ) {
    if( i != splitter_idx ) child_planes.push( planes.data[i] );
  }

  I32 front_child = bsp_build_nodes( bsp, child_planes, front, depth + 1 );
  if( coplane.size ) {
    I32 coplane_leaf = bsp_insert_leaf( bsp, coplane );
    BSP_NODE glue{};
    glue.plane = split;
    glue.front = front_child;
    glue.back = coplane_leaf;
    front_child = bsp->nodes.size;
    bsp->nodes.push( glue );
  }

  I32 back_child = bsp_build_nodes( bsp, child_planes, back, depth + 1 );

  bsp->nodes.data[nidx].front = front_child;
  bsp->nodes.data[nidx].back = back_child;
  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 ) );
  *v = vec_normalize( vec_cross( norm, *v ) );
}

BSP_WINDING bsp_winding_create( BSP_PLANE* plane ) {
  BSP_WINDING w{};
  VEC3 n = plane->normal, nu = n * -1.f;
  VEC3 u, v;
  bsp_plane_basis( n, &u, &v );

  VEC3 c = n * plane->dist;

  F32 s = BSP_PORTAL_PLANE_SIZE;
  w.points.reserve( 4 );
  w.points.push( c + (  u + v ) * s );
  w.points.push( c + ( nu + v ) * s );
  w.points.push( c + ( nu - v ) * s );
  w.points.push( c + (  u - v ) * s );

  return w;
}


F32 signed_dist_point_to_plane( const BSP_PLANE& plane, const VEC3& point ) {
  return vec_dot( plane.normal, point ) - plane.dist;
}

U8 bsp_clip_winding( BSP_WINDING* w, const BSP_PLANE& plane, U8 keep_front ) {
  if( w->points.size < 3 )
    return 0;

  LIST<VEC3> out;
  out.reserve( w->points.size + 2 );

  for( U32 i = 0; i < w->points.size; ++i ) {
    VEC3* a = &w->points.data[i];
    VEC3* b = &w->points.data[(i + 1) % w->points.size];

    F32 da = signed_dist_point_to_plane( plane, *a );
    F32 db = signed_dist_point_to_plane( plane, *b );

    U8 ain = keep_front ? ( da >= -BSP_NORM_EPSILON ) : ( da <= BSP_NORM_EPSILON );
    U8 bin = keep_front ? ( db >= -BSP_NORM_EPSILON ) : ( db <= BSP_NORM_EPSILON );

    if( ain )
      out.push( *a );

    if( ain != bin ) {
      F32 t = da / (da - db);
      t = m_clamp( t, 0.f, 1.f );
      VEC3 p = *a + (*b - *a) * t;
      out.push( p );
    }
  }

  if( out.size < 3 ) {
    w->points.clear();
    return 0;
  }

  w->points = out;
  return 1;
}

U8 bsp_clip_winding_to_set( BSP_WINDING* w, LIST<BSP_PLANE>* planes ) {
  for( U32 i = 0; i < planes->size; ++i ) {
    if( !bsp_clip_winding( w, planes->data[i], 1 ) )
      return 0;
  }

  return 1;
}

U8 bsp_winding_intersect_plane( BSP_PLANE* plane, BSP_WINDING* wa, BSP_WINDING* wb, BSP_WINDING* out ) {
  if( wa->points.size < 3 || wb->points.size < 3 )
    return 0;

  BSP_WINDING w = *wa;

  for( U32 i = 0; i < wb->points.size; ++i ) {
    VEC3* b1 = &wb->points[i];
    VEC3* b2 = &wb->points[(i + 1) % wb->points.size];

    VEC3 edge = *b2 - *b1;

    VEC3 inward_norm = vec_normalize( vec_cross( plane->normal, edge ) );
    F32 d = vec_dot( inward_norm, *b1 );

    BSP_PLANE horip{ inward_norm, d };
    if( !bsp_clip_winding( &w, horip, 1 ) )
      return 0;
  }

  *out = w;
  return 1;
}

void bsp_gather_volumes_for_node(
  BSP* bsp,
  I32 node_idx,
  const LIST<BSP_PLANE>& parents,
  U8 go_front,
  LIST<BSP_PLANE>* out
) {
  *out = parents;
  BSP_NODE* n = &bsp->nodes.data[node_idx];
  BSP_PLANE newp = n->plane;
  if( !go_front ) {
    newp.normal = newp.normal * -1;
    newp.dist = -newp.dist;
  }

  out->push( newp );
}

void bsp_clip_portal_to_subtree(
  BSP* bsp,
  I32 idx,
  BSP_WINDING w,
  U8 in_front,
  LIST<BSP_PORTAL_NODE>* nodes
) {
  if( bsp_is_leaf( idx ) ) {
    BSP_PORTAL_NODE newn{ .leaf = bsp_leaf_index( idx ), .w = w };
    nodes->push( newn );
    return;
  }

  BSP_NODE* n = &bsp->nodes.data[idx];
  BSP_WINDING wf = w, wb = w;

  if( !bsp_clip_winding( in_front ? &wf : &wb, n->plane, in_front ) )
    return;

  if( in_front ) {
    bsp_clip_portal_to_subtree( bsp, n->front, wf, 1, nodes );
  } else {
    bsp_clip_portal_to_subtree( bsp, n->back, wb, 0, nodes );
  }
}

void bsp_build_portals( BSP* bsp ) {
  if( bsp->root < 0 )
    return;

  LIST<BSP_PORTAL_STACK_FRAME> stack;
  stack.push( BSP_PORTAL_STACK_FRAME{ bsp->root, LIST<BSP_PLANE>{} } );

  // todo: multithread this
  while( stack.size ) {
    BSP_PORTAL_STACK_FRAME frame = stack.data[stack.size - 1];
    stack.pop();

    if( bsp_is_leaf( frame.idx ) )
      continue;

    BSP_NODE* n = &bsp->nodes.data[frame.idx];

    BSP_WINDING wind = bsp_winding_create( &n->plane );
    BSP_WINDING bounded = wind;
    if( bsp_clip_winding_to_set( &bounded, &frame.planes ) ) {
      LIST<BSP_PORTAL_NODE> fr_nodes, bk_nodes;

      bsp_clip_portal_to_subtree( bsp, n->front, bounded, 1, &fr_nodes );
      bsp_clip_portal_to_subtree( bsp, n->back, bounded, 1, &bk_nodes );

      for( U32 ifr = 0; ifr < fr_nodes.size; ++ifr ) {
        for( U32 ibk = 0; ibk < bk_nodes.size; ++ibk ) {
          BSP_WINDING intersect;
          if( bsp_winding_intersect_plane( &n->plane, &fr_nodes.data[ifr].w, &bk_nodes.data[ibk].w, &intersect ) ) {
            if( intersect.points.size > 3 ) {
              BSP_PORTAL p;
              p.w = intersect;
              p.plane = n->plane;
              p.front = bsp_leaf_index( fr_nodes.data[ifr].leaf );
              p.back  = bsp_leaf_index( bk_nodes.data[ibk].leaf );
              bsp->portals.push( p );
            }
          }
        }
      }
    }

    LIST<BSP_PLANE> fr, bk;
    bsp_gather_volumes_for_node( bsp, frame.idx, frame.planes, 1, &fr );
    bsp_gather_volumes_for_node( bsp, frame.idx, frame.planes, 0, &bk );

    BSP_NODE* n1 = &bsp->nodes.data[frame.idx];
    if( !bsp_is_leaf( n1->front ) ) stack.push( BSP_PORTAL_STACK_FRAME{ n1->front, fr } );
    if( !bsp_is_leaf( n1->back ) )  stack.push( BSP_PORTAL_STACK_FRAME{ n1->back,  bk } );
  }

  for( U32 i = 0; i < bsp->leaves.size; ++i ) {
    bsp->leaves.data[i].cluster = (I32)i;
  }
}

void pvs_set( BSP_BITSET* pvs, U32 count, U32 cluster, U32 seen ) {
  U32 wp = (count + 31) / 32;
  U32 base = cluster * wp;

  U32 w = seen / 32, b = seen % 32;
  while( base + w >= pvs->size ) pvs->push( 0 );
  pvs->data[base + w] |= (1u << b);
}

U8 pvs_get( BSP_BITSET* pvs, U32 count, U32 cluster, U32 seen ) {
  U32 wp = (count + 31) / 32;
  U32 base = cluster * wp;

  U32 w = seen / 32, b = seen % 32;
  if( base + w >= pvs->size ) return 0;

  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 ) {
  BSP* bsp = new BSP;
  bsp->map = m;
  LIST<BSP_FACE> faces = bsp_map_get_faces( m );
  LIST<BSP_PLANE> planes = bsp_map_get_planes( m );

  bsp->root = bsp_build_nodes( bsp, planes, faces, 0 );
  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 );
  bsp_build_pvs( bsp );
  m->bsp = bsp;
  return bsp;
}

void bsp_free( BSP* bsp ) {
  delete bsp;
}