From f8b92ce3aa08b1445c9f956d8166830946562d12 Mon Sep 17 00:00:00 2001 From: navewindre Date: Wed, 3 Sep 2025 20:10:09 +0200 Subject: a --- src/game/world/bsp.cpp | 662 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 662 insertions(+) create mode 100644 src/game/world/bsp.cpp (limited to 'src/game/world/bsp.cpp') 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 + +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 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_map_get_wall_planes( WORLD_MAP* map ) { + LIST 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 bsp_map_triangulate_planes( WORLD_MAP* map ) { + LIST 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_map_get_tri_planes( WORLD_MAP* map ) { + LIST ret; + LIST 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_map_get_planes( WORLD_MAP* map ) { + LIST ret; + + LIST walls = bsp_map_get_wall_planes( map ); + LIST 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_map_faces_from_walls( WORLD_MAP* map ) { + LIST 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_map_faces_from_planes( WORLD_MAP* map ) { + LIST 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_map_get_faces( WORLD_MAP* map ) { + LIST ret; + + LIST walls = bsp_map_faces_from_walls( map ); + LIST 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 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& 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& planes, const LIST& 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& 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& 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& planes, + LIST& 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 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 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 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* 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& parents, + U8 go_front, + LIST* 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* 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 stack; + stack.push( BSP_PORTAL_STACK_FRAME{ bsp->root, LIST{} } ); + + // 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 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 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 faces = bsp_map_get_faces( m ); + LIST 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; +} + -- cgit v1.2.3