summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/game/physics/movement.cpp2
-rw-r--r--src/game/world/bsp.cpp106
-rw-r--r--src/game/world/bsp.h17
-rw-r--r--src/game/world/trace.cpp72
4 files changed, 190 insertions, 7 deletions
diff --git a/src/game/physics/movement.cpp b/src/game/physics/movement.cpp
index 1e2e973..b2b2ffa 100644
--- a/src/game/physics/movement.cpp
+++ b/src/game/physics/movement.cpp
@@ -257,7 +257,7 @@ F32 gmove_try_move( BSP_TRACE* t, VEC3* pos, VEC3* vel ) {
F32 dot = vec_dot( *vel, t->normal );
*pos += wishmove * t->frac;
// nudge player away from wall
- *pos += t->normal * BSP_TRACE_EPSILON * 4.f;
+ *pos += t->normal * BSP_TRACE_EPSILON * 2.f;
// avoid clipping planes twice
// in a rare edge case its possible to get stuck in the plane again after pushing away from it
diff --git a/src/game/world/bsp.cpp b/src/game/world/bsp.cpp
index e163d6e..7c6b9ab 100644
--- a/src/game/world/bsp.cpp
+++ b/src/game/world/bsp.cpp
@@ -1,6 +1,7 @@
#include "bsp.h"
#include "../../util/math.h"
#include "map.h"
+#include "trace.h"
#include <climits>
const F32 BSP_PORTAL_PLANE_SIZE = 64000.f;
@@ -417,6 +418,110 @@ I32 bsp_build_nodes(
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 ) );
@@ -727,6 +832,7 @@ BSP* bsp_build_map( WORLD_MAP* m ) {
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 );
diff --git a/src/game/world/bsp.h b/src/game/world/bsp.h
index 457bcb9..50e8764 100644
--- a/src/game/world/bsp.h
+++ b/src/game/world/bsp.h
@@ -38,10 +38,20 @@ struct BSP_NODE {
I32 back;
};
+struct BSP_EDGE {
+ BSP_PLANE plane;
+ U32 face;
+ U8 avgc;
+
+ VEC3 v1, v2;
+};
+
struct BSP_LEAF {
U32 first;
U32 count;
I32 cluster;
+
+ LIST<BSP_EDGE> edges;
};
struct BSP_WINDING {
@@ -106,3 +116,10 @@ inline SURF_PROPS* bsp_face_get_props( WORLD_MAP* w, BSP_FACE* s ) {
map_props_get_special( w, s->propid ) :
&w->props[s->propid];
}
+
+inline VEC3 bsp_face_get_normal( const BSP_FACE* f ){
+ const VEC3 v0 = f->verts.data[0].pos;
+ const VEC3 v1 = f->verts.data[1].pos;
+ const VEC3 v2 = f->verts.data[2].pos;
+ return vec_normalize( vec_cross( v1 - v0, v2 - v0 ) );
+}
diff --git a/src/game/world/trace.cpp b/src/game/world/trace.cpp
index 3548fa8..6d1e8db 100644
--- a/src/game/world/trace.cpp
+++ b/src/game/world/trace.cpp
@@ -1,6 +1,7 @@
#include "trace.h"
#include "../../util/math.h"
#include "bsp.h"
+#include "map.h"
// i have no idea how this works tbh i pasted this
// todo : backface culling (return 0 if d < BSP_TRACE_EPSILON)
@@ -172,12 +173,7 @@ U8 bsp_trace( BSP_TRACE* trace, BSP* bsp ) {
return bsp_trace_segment( trace, bsp, bsp->root, start, end );
}
-inline VEC3 bsp_face_get_normal( const BSP_FACE* f ){
- const VEC3 v0 = f->verts.data[0].pos;
- const VEC3 v1 = f->verts.data[1].pos;
- const VEC3 v2 = f->verts.data[2].pos;
- return vec_normalize( vec_cross( v1 - v0, v2 - v0 ) );
-}
+
inline U8 point_in_inflated_poly(
const VEC3& point,
@@ -268,6 +264,67 @@ U8 bsp_trace_sweep_aabb_to_face(
return 1;
}
+U8 bsp_trace_sweep_aabb_to_leaf_edges(
+ BSP* bsp,
+ BSP_TRACE* trace,
+ const AABB& hull,
+ const VEC3& start,
+ const VEC3& end,
+ I32 leaf_idx,
+ F32* in_best
+) {
+ BSP_LEAF* leaf = &bsp->leaves.data[leaf_idx];
+ U8 hit = 0;
+ F32 best = *in_best;
+
+ BSP_TRACE besthit = *trace;
+ for( U32 i = 0; i < leaf->edges.size; ++i ) {
+ BSP_EDGE* e = &leaf->edges[i];
+ BSP_FACE* f = &bsp->faces.data[e->face];
+
+ if( f->propid == MAPPROP_SKYBOX )
+ continue;
+
+ VEC3 n = e->plane.normal;
+ F32 d = e->plane.dist;
+ F32 r = aabb_support_radius( hull, n );
+
+ F32 s0 = vec_dot( n, start ) - d;
+ F32 ndir = vec_dot( n, end - start );
+
+ if( ndir >= 0.f ) continue;
+ if( s0 < -(r + BSP_TRACE_EPSILON) ) continue;
+
+ F32 t = (-r - s0) / ndir;
+ if( t < 0.f || t > 1.f ) continue;
+ t = m_clamp( t, 0.f, 1.f );
+
+ VEC3 step = start + (end - start) * t;
+
+ if( !point_in_inflated_poly( step, f, hull, n ) )
+ continue;
+
+ if( t < best ) {
+ best = t;
+ *in_best = best;
+ besthit.frac = t;
+ besthit.point = step;
+ besthit.normal = n;
+ besthit.propid = f->propid;
+ besthit.faceid = e->face;
+ besthit.leafid = leaf_idx;
+ hit = 1;
+ }
+ }
+
+ if( hit ) {
+ *trace = besthit;
+ trace->hit = 1;
+ }
+
+ return hit;
+}
+
U8 bsp_trace_sweep_aabb_to_leaf(
BSP* bsp,
BSP_TRACE* trace,
@@ -301,6 +358,9 @@ U8 bsp_trace_sweep_aabb_to_leaf(
}
}
+ U8 ehit = bsp_trace_sweep_aabb_to_leaf_edges( bsp, trace, hull, start, end, leaf_idx, &best );
+ if( !hit ) hit = ehit;
+
if( hit ) {
*trace = besthit;
trace->hit = 1;
generated by cgit v1.2.3 (git 2.26.2) at 2026-06-15 21:19:17 +0000