From e57cac01b0a4eb764185e8eca9396a25b83f34d3 Mon Sep 17 00:00:00 2001 From: aura Date: Tue, 3 Mar 2026 16:16:06 +0100 Subject: edge planes ))) --- src/game/world/bsp.cpp | 136 ++++++++++++++++++++++++------------------------- 1 file changed, 66 insertions(+), 70 deletions(-) (limited to 'src/game/world/bsp.cpp') diff --git a/src/game/world/bsp.cpp b/src/game/world/bsp.cpp index 7c6b9ab..7f72e52 100644 --- a/src/game/world/bsp.cpp +++ b/src/game/world/bsp.cpp @@ -135,7 +135,6 @@ LIST bsp_map_get_planes( WORLD_MAP* map ) { return ret; } - LIST bsp_map_faces_from_walls( WORLD_MAP* map ) { LIST ret{}; @@ -169,7 +168,6 @@ LIST 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 ); }; @@ -418,8 +416,42 @@ I32 bsp_build_nodes( return nidx; } -void bsp_gen_leaf_edges( BSP* bsp, I32 leaf_idx, LIST* out ) { +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* edges = &leaf->edges; for( U32 facei = 0; facei < leaf->count; ++facei ) { U32 faceidx = leaf->first + facei; @@ -432,7 +464,7 @@ void bsp_gen_leaf_edges( BSP* bsp, I32 leaf_idx, LIST* out ) { VEC3 center{}; for( U32 i = 0; i < face->verts.size; ++i ) center = center + face->verts.data[i].pos; - center = center / face->verts.size; + center /= face->verts.size; for( U32 i = 0; i < face->verts.size; ++i ) { VEC3 a = face->verts[i].pos; @@ -441,87 +473,50 @@ void bsp_gen_leaf_edges( BSP* bsp, I32 leaf_idx, LIST* out ) { F32 elen = vec_len( edge ); if( elen < 0.0001f ) continue; - edge = edge * (1.f / elen); - - VEC3 edgen = vec_normalize( vec_cross( facen, edge ) ); + edge *= (1.f / elen); - 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; + 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; - dv1 = vec_dist( a->v1, b->v2 ); - dv2 = vec_dist( a->v2, b->v1 ); + if( fabsf( vec_dot( cross, facen ) ) > 0.995f ) + continue; - if( dv1 < t && dv2 < t ) - return 1; + if( !bsp_edge_is_shared( bsp, a, b, center, cross, faceidx ) ) + continue; - return 0; -} + 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; } + } -LIST bsp_average_leaf_edges( BSP* bsp, LIST* edges ) { - LIST out{}; - for( U32 i = 0; i < edges->size; ++i ) { - BSP_EDGE a = edges->data[i]; + if( dupe ) + continue; - 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++; + BSP_EDGE e; + e.plane = plane; + e.face = faceidx; + e.v1 = a; + e.v2 = b; + edges->push( e ); } } - - a.avgc = 1; - out.push( a ); } - - return out; } void bsp_gen_leaf_edges( BSP* bsp ) { LIST 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 ); - } ); - } ); + 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 ) ); @@ -830,9 +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_leaf_edges( bsp ); bsp_gen_render_vertices( bsp ); bsp_build_portals( bsp ); -- cgit v1.2.3