a

1 files changed, 662 insertions, 0 deletions

diff --git a/src/game/world/bsp.cpp b/src/game/world/bsp.cpp
new file mode 100644
index 0000000..9aa94d7
--- /dev/null
+++ b/src/game/world/bsp.cpp
@@ -0,0 +1,662 @@
+#include "bsp.h"
+#include "../../util/math.h"
+#include "map.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 f1{ .propid = w->propid };
+    f1.verts.push( vertices[2] );
+    f1.verts.push( vertices[1] );
+    f1.verts.push( vertices[0] );
+
+    BSP_FACE f2{ .propid = w->propid };
+    f2.verts.push( vertices[3] );
+    f2.verts.push( vertices[2] );
+    f2.verts.push( vertices[0] );
+
+    ret.push( f1 );
+    ret.push( f2 );
+  };
+
+  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;
+}
+
+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;
+}
+
+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 );
+  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 );
+  return bsp;
+}
+
+void bsp_free( BSP* bsp ) {
+  delete bsp;
+}
+