summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--assets/maps/test.hmap41
-rw-r--r--assets/maps/test2.hmap100
-rw-r--r--assets/maps/test3.hmap70
-rw-r--r--src/game/physics/movement.cpp22
-rw-r--r--src/game/world/bsp.cpp106
-rw-r--r--src/game/world/bsp.h35
-rw-r--r--src/game/world/trace.cpp151
-rw-r--r--src/util/aabb.h20
-rw-r--r--src/util/vector.h10
9 files changed, 511 insertions, 44 deletions
diff --git a/assets/maps/test.hmap b/assets/maps/test.hmap
index df52de5..3d7db93 100644
--- a/assets/maps/test.hmap
+++ b/assets/maps/test.hmap
@@ -1,9 +1,9 @@
DEF map {
I32 wallcount = 7;
- I32 polycount = 2;
+ I32 polycount = 3;
I32 propcount = 5;
I32 spritecount = 1;
- VEC3 startpos = { 84, 109, -39.75 };
+ VEC3 startpos = { 124, 42, -39.75 };
F32 startang = 0;
DEF props {
DEF 0 {
@@ -38,7 +38,7 @@ DEF map {
}
DEF 2 {
VEC3 start = { 200, 200, -40 };
- VEC3 end = { 0, 200, 120 };
+ VEC3 end = { 83, 200, 120 };
I32 propid = 2;
}
DEF 3 {
@@ -96,22 +96,49 @@ DEF map {
I32 type = 0;
DEF vertices {
DEF 0 {
- VEC3 pos = { 188, 187, -7.5 };
+ VEC3 pos = { 192, 124, -7.5 };
VEC2 uv = { 1, 0 };
CLR clr = { 1, 1, 1, 1 };
}
DEF 1 {
- VEC3 pos = { 6, 187, -7.5 };
+ VEC3 pos = { 10, 124, -7.5 };
VEC2 uv = { 0, 0 };
CLR clr = { 1, 1, 1, 1 };
}
DEF 2 {
- VEC3 pos = { 6.79887, 133.711, -40 };
+ VEC3 pos = { 10, 70, -40 };
VEC2 uv = { 0, 1 };
CLR clr = { 1, 1, 1, 1 };
}
DEF 3 {
- VEC3 pos = { 188.102, 133.711, -40 };
+ VEC3 pos = { 192, 70, -40 };
+ VEC2 uv = { 1, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ }
+ }
+ DEF 2 {
+ I32 vertcount = 4;
+ I32 propid = 0;
+ I32 type = 0;
+ DEF vertices {
+ DEF 0 {
+ VEC3 pos = { 192, 169, -40 };
+ VEC2 uv = { 1, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 1 {
+ VEC3 pos = { 10, 169, -40 };
+ VEC2 uv = { 0, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 2 {
+ VEC3 pos = { 10, 124, -7.5 };
+ VEC2 uv = { 0, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 3 {
+ VEC3 pos = { 192, 124, -7.5 };
VEC2 uv = { 1, 1 };
CLR clr = { 1, 1, 1, 1 };
}
diff --git a/assets/maps/test2.hmap b/assets/maps/test2.hmap
index 69992df..de62787 100644
--- a/assets/maps/test2.hmap
+++ b/assets/maps/test2.hmap
@@ -1,23 +1,113 @@
DEF map {
- I32 wallcount = 1;
- I32 polycount = 0;
- I32 propcount = 1;
+ I32 wallcount = 2;
+ I32 polycount = 3;
+ I32 propcount = 2;
I32 spritecount = 0;
- VEC3 startpos = { 10, 10, 0 };
+ VEC3 startpos = { 146, 104, 15 };
F32 startang = -0.372549;
DEF props {
DEF 0 {
CLR clr = { 1, 1, 1, 1 };
+ STR tex[256] = "uvtest2.png";
+ }
+ DEF 1 {
+ CLR clr = { 1, 1, 1, 1 };
}
}
DEF walls {
DEF 0 {
VEC3 start = { 0, 0, -40 };
- VEC3 end = { 10, 0, 80 };
+ VEC3 end = { 545.75, 0, 80 };
+ I32 propid = 1;
+ }
+ DEF 1 {
+ VEC3 start = { 219, 408, -40 };
+ VEC3 end = { 219, 175, 80 };
I32 propid = 0;
}
}
DEF polygons {
+ DEF 0 {
+ I32 vertcount = 4;
+ I32 propid = 0;
+ I32 type = 0;
+ DEF vertices {
+ DEF 0 {
+ VEC3 pos = { 545, 467, -40 };
+ VEC2 uv = { 1, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 1 {
+ VEC3 pos = { 0, 467, -40 };
+ VEC2 uv = { 0, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 2 {
+ VEC3 pos = { 0, 1, -40 };
+ VEC2 uv = { 0, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 3 {
+ VEC3 pos = { 545, 1, -40 };
+ VEC2 uv = { 1, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ }
+ }
+ DEF 1 {
+ I32 vertcount = 4;
+ I32 propid = 0;
+ I32 type = 0;
+ DEF vertices {
+ DEF 0 {
+ VEC3 pos = { 477, 291, 0 };
+ VEC2 uv = { 1, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 1 {
+ VEC3 pos = { 219, 291, 0 };
+ VEC2 uv = { 0, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 2 {
+ VEC3 pos = { 219, 175, -40 };
+ VEC2 uv = { 0, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 3 {
+ VEC3 pos = { 477, 175, -40.25 };
+ VEC2 uv = { 1, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ }
+ }
+ DEF 2 {
+ I32 vertcount = 4;
+ I32 propid = 0;
+ I32 type = 0;
+ DEF vertices {
+ DEF 0 {
+ VEC3 pos = { 477, 408, -80 };
+ VEC2 uv = { 1, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 1 {
+ VEC3 pos = { 219, 408, -80 };
+ VEC2 uv = { 0, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 2 {
+ VEC3 pos = { 219, 291, 0 };
+ VEC2 uv = { 0, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 3 {
+ VEC3 pos = { 477, 291, 0 };
+ VEC2 uv = { 1, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ }
+ }
}
DEF sprites {
}
diff --git a/assets/maps/test3.hmap b/assets/maps/test3.hmap
new file mode 100644
index 0000000..e424ead
--- /dev/null
+++ b/assets/maps/test3.hmap
@@ -0,0 +1,70 @@
+DEF map {
+ I32 wallcount = 4;
+ I32 polycount = 1;
+ I32 propcount = 2;
+ I32 spritecount = 0;
+ VEC3 startpos = { 246, 199, 0 };
+ F32 startang = -0.372549;
+ DEF props {
+ DEF 0 {
+ CLR clr = { 1, 0, 1, 1 };
+ }
+ DEF 1 {
+ CLR clr = { 1, 1, 1, 1 };
+ STR tex[256] = "uvtest2.png";
+ }
+ }
+ DEF walls {
+ DEF 0 {
+ VEC3 start = { 0, 0, -40 };
+ VEC3 end = { 512, 0, 80 };
+ I32 propid = 0;
+ }
+ DEF 1 {
+ VEC3 start = { 116, 165, -40 };
+ VEC3 end = { 116, 293, 80 };
+ I32 propid = 0;
+ }
+ DEF 2 {
+ VEC3 start = { 250, 183, -40 };
+ VEC3 end = { 160, 96, 80 };
+ I32 propid = 0;
+ }
+ DEF 3 {
+ VEC3 start = { 160, 96, -40 };
+ VEC3 end = { 80, 96, 80 };
+ I32 propid = 0;
+ }
+ }
+ DEF polygons {
+ DEF 0 {
+ I32 vertcount = 4;
+ I32 propid = 1;
+ I32 type = 0;
+ DEF vertices {
+ DEF 0 {
+ VEC3 pos = { 512, 512, -40 };
+ VEC2 uv = { 1, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 1 {
+ VEC3 pos = { 0, 512, -40 };
+ VEC2 uv = { 0, 0 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 2 {
+ VEC3 pos = { -3.6704, -0.685966, -40 };
+ VEC2 uv = { 0, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ DEF 3 {
+ VEC3 pos = { 512, 0, -40 };
+ VEC2 uv = { 1, 1 };
+ CLR clr = { 1, 1, 1, 1 };
+ }
+ }
+ }
+ }
+ DEF sprites {
+ }
+}
diff --git a/src/game/physics/movement.cpp b/src/game/physics/movement.cpp
index 1e2e973..fce9d73 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;
// avoid clipping planes twice
// in a rare edge case its possible to get stuck in the plane again after pushing away from it
@@ -291,7 +291,7 @@ void gmove_check_stuck( VEC3* in_pos ) {
gmove->unstuck_vel = { 0, 0, 1.f };
bsp_trace( &t, gmove->bsp, gmove->aabb, pos, pos );
- if( !t.hit ) {
+ if( !t.hit || !t.startsolid ) {
if( vec_len( gmove->velocity ) > 1.f ) {
gmove->unstuck_pos = pos;
gmove->unstuck_vel = gmove->velocity;
@@ -299,6 +299,18 @@ void gmove_check_stuck( VEC3* in_pos ) {
return;
}
+ for( U32 i = 0; i < 3; ++i ) {
+ VEC3 dir = vec3_axis[i];
+ VEC3 nudge = pos + dir;
+ bsp_trace( &t, gmove->bsp, gmove->aabb, pos, nudge );
+ if( !t.hit || !t.startsolid )
+ return; // not actually stuck, just somewhat inside a solid
+
+ nudge = pos + dir * -1.f;
+ if( !t.hit || !t.startsolid )
+ return;
+ }
+
VEC3 p1 = pos;
defer( {
if( !t.hit ) {
@@ -435,14 +447,11 @@ void gmove_step_move( VEC3 dest, BSP_TRACE* tr ) {
VEC3 up = pos, down = pos;
VEC3 upvel = vel, downvel = vel;
- F32 groundn = 0.f;
if( gmove->ground ) {
VEC3 ground = pos;
ground.z += 2.f;
bsp_trace( tr, gmove->bsp, gmove->aabb, pos, ground );
- if( tr->hit )
- groundn = tr->normal.z;
}
// try moving forward first
@@ -504,9 +513,6 @@ void gmove_step_move( VEC3 dest, BSP_TRACE* tr ) {
gmove->pos += delta;
if( tr->normal.z < 0.99f )
gmove->pos += tr->normal * BSP_TRACE_EPSILON * 2.f;
- // hack : moving to a steeper slope, move up a bit to avoid getting stuck in the edge
- if( gmove->ground && tr->normal.z < groundn )
- gmove->pos.z += BSP_TRACE_EPSILON;
gmove->velocity = upvel;
gmove->velocity.z = downvel.z;
}
diff --git a/src/game/world/bsp.cpp b/src/game/world/bsp.cpp
index e163d6e..7f72e52 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;
@@ -134,7 +135,6 @@ LIST<BSP_PLANE> bsp_map_get_planes( WORLD_MAP* map ) {
return ret;
}
-
LIST<BSP_FACE> bsp_map_faces_from_walls( WORLD_MAP* map ) {
LIST<BSP_FACE> ret{};
@@ -168,7 +168,6 @@ LIST<BSP_FACE> 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 );
};
@@ -417,6 +416,107 @@ I32 bsp_build_nodes(
return nidx;
}
+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<BSP_EDGE>* edges = &leaf->edges;
+
+ 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 /= 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 *= (1.f / elen);
+
+ 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;
+
+ if( fabsf( vec_dot( cross, facen ) ) > 0.995f )
+ continue;
+
+ if( !bsp_edge_is_shared( bsp, a, b, center, cross, faceidx ) )
+ continue;
+
+ 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; }
+ }
+
+ if( dupe )
+ continue;
+
+ BSP_EDGE e;
+ e.plane = plane;
+ e.face = faceidx;
+ e.v1 = a;
+ e.v2 = b;
+ edges->push( e );
+ }
+ }
+ }
+}
+
+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 );
+}
+
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 ) );
@@ -725,8 +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_render_vertices( bsp );
bsp_build_portals( bsp );
diff --git a/src/game/world/bsp.h b/src/game/world/bsp.h
index 457bcb9..8892108 100644
--- a/src/game/world/bsp.h
+++ b/src/game/world/bsp.h
@@ -30,6 +30,8 @@ struct BSP_FACE {
I32 id;
LIST<MAP_VERTEX> verts{};
LIST<VERTEX3D> render_verts{};
+ VEC3 mins;
+ VEC3 maxs;
};
struct BSP_NODE {
@@ -38,10 +40,19 @@ struct BSP_NODE {
I32 back;
};
+struct BSP_EDGE {
+ BSP_PLANE plane;
+ U32 face;
+
+ VEC3 v1, v2;
+};
+
struct BSP_LEAF {
U32 first;
U32 count;
I32 cluster;
+
+ LIST<BSP_EDGE> edges;
};
struct BSP_WINDING {
@@ -106,3 +117,27 @@ 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( BSP_FACE* f ){
+ VEC3 v0 = f->verts.data[0].pos;
+ VEC3 v1 = f->verts.data[1].pos;
+ VEC3 v2 = f->verts.data[2].pos;
+ return vec_normalize( vec_cross( v1 - v0, v2 - v0 ) );
+}
+
+inline void bsp_face_calc_extents( BSP_FACE* f ) {
+ VEC3 mins{ +INFINITY, +INFINITY, +INFINITY }, maxs{ -INFINITY, -INFINITY, -INFINITY };
+ for( U32 i = 0; i < f->verts.size; ++i ) {
+ VEC3 v = f->verts.data[i].pos;
+ mins.x = min( mins.x, v.x );
+ mins.y = min( mins.y, v.y );
+ mins.z = min( mins.z, v.z );
+
+ maxs.x = max( maxs.x, v.x );
+ maxs.y = max( maxs.y, v.y );
+ maxs.z = max( maxs.z, v.z );
+ }
+
+ f->mins = mins;
+ f->maxs = maxs;
+}
diff --git a/src/game/world/trace.cpp b/src/game/world/trace.cpp
index 3548fa8..1d32afe 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,
@@ -194,9 +190,10 @@ inline U8 point_in_inflated_poly(
for( U32 i = 0; i < c; ++i ) {
VEC3 a = face->verts.data[i].pos;
VEC3 b = face->verts.data[(i+1)%c].pos;
- VEC3 in = vec_cross( norm, b - a );
+ VEC3 e = b - a;
+ VEC3 in = vec_cross( norm, e );
F32 len = vec_len( in );
- if( len <= 0.00001f ) continue;
+ if( len <= 0.0001f ) continue;
in *= (1.0f/ len);
if( vec_dot( center - a, in ) < 0.0f )
in = in * -1.0f;
@@ -205,6 +202,13 @@ inline U8 point_in_inflated_poly(
F32 expand = aabb_support_radius( hull, in );
if( dist < -( expand - BSP_EDGE_TOLERANCE ) )
return 0;
+
+ // check if plane is aligned to any hull edge in x/y plane
+ if( fabsf( norm.x ) >= BSP_TRACE_EPSILON && fabsf( norm.y ) >= BSP_TRACE_EPSILON ) {
+ // for non-axis-aligned faces the point of contact is infinitely thin
+ if( dist < BSP_EDGE_TOLERANCE )
+ return 0;
+ }
}
return 1;
}
@@ -222,20 +226,30 @@ U8 bsp_trace_sweep_aabb_to_face(
if( face->verts.size < 3 )
return 0;
- VEC3 norm = bsp_face_get_normal( face );
- F32 d = vec_dot( norm, face->verts[0].pos );
- F32 radius = aabb_support_radius( hull, norm );
+ VEC3 hullv = hull.max - hull.min;
+ AABB fhull = { face->mins - hullv, face->maxs + hullv };
+ AABB fhullh = { face->mins - hullv * 0.5f, face->maxs + hullv * 0.5f };
+ VEC3 norm = bsp_face_get_normal( face );
+ F32 d = vec_dot( norm, face->verts[0].pos );
+ F32 radius = aabb_support_radius( hull, norm );
- VEC3 dir = end - start;
+ VEC3 dir = trace->in_end - trace->in_start;
F32 s0 = vec_dot( norm, trace->in_start ) - d;
- F32 ndir = vec_dot( norm, trace->in_end - trace->in_start );
+ F32 ndir = vec_dot( norm, dir );
+
+ F32 tdot = vec_dot( dir, norm );
+ if( tdot >= 0 ) // dont collide with rear side
+ return 0;
if( fabsf( s0 ) <= radius + BSP_TRACE_EPSILON ) {
- if( point_in_inflated_poly( start, face, hull, norm ) ) {
+ if( aabb_contains_point( fhullh, start ) && point_in_inflated_poly( start, face, hull, norm ) ) {
trace->hit = 1;
trace->frac = 0.f;
trace->startsolid = 1;
trace->point = start;
+ trace->point.x = m_clamp( trace->point.x, fhullh.min.x, fhullh.max.x );
+ trace->point.y = m_clamp( trace->point.y, fhullh.min.y, fhullh.max.y );
+ trace->point.z = m_clamp( trace->point.z, fhullh.min.z, fhullh.max.z );
trace->normal = norm;
trace->propid = face->propid;
trace->faceid = face_idx;
@@ -243,22 +257,25 @@ U8 bsp_trace_sweep_aabb_to_face(
}
}
- if( ndir > BSP_TRACE_EPSILON )
- return 0;
-
F32 t_enter = (-radius - s0) / ndir;
F32 t_exit = ( radius - s0) / ndir;
if( t_enter > t_exit ) { F32 tmp=t_enter; t_enter=t_exit; t_exit=tmp; }
-
if( t_exit < 0.f - BSP_TRACE_EPSILON || t_enter > 1.f + BSP_TRACE_EPSILON )
return 0;
F32 t = m_clamp( t_enter, 0.f, 1.f );
- VEC3 step = start + dir * t;
+ VEC3 step = trace->in_start + dir * t;
+
+ if( !aabb_contains_point( fhull, step ) )
+ return 0;
if( !point_in_inflated_poly( step, face, hull, norm ) )
return 0;
+ step.x = m_clamp( step.x, fhullh.min.x, fhullh.max.x );
+ step.y = m_clamp( step.y, fhullh.min.y, fhullh.max.y );
+ step.z = m_clamp( step.z, fhullh.min.z, fhullh.max.z );
+
trace->hit = 1;
trace->frac = t;
trace->point = step;
@@ -268,6 +285,84 @@ 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_enter = ( r - s0) / ndir;
+ F32 t_exit = (-r - s0) / ndir;
+ if( t_enter > t_exit ) { F32 tmp = t_enter; t_enter = t_exit; t_exit = tmp; }
+
+ if( t_exit < -BSP_TRACE_EPSILON || t_enter > 1.f + BSP_TRACE_EPSILON )
+ continue;
+
+ F32 t = m_clamp( t_enter, 0.f, 1.f );
+ VEC3 step = start + (end - start) * t;
+
+ VEC3 edir = e->v2 - e->v1;
+ F32 elen = vec_len( edir );
+ if( elen < 0.001f )
+ continue;
+ edir *= (1.f / elen);
+
+ F32 along = vec_dot( step - e->v1, edir );
+ VEC3 proj = e->v1 + edir * m_clamp( along, 0.f, elen );
+ F32 dist = vec_dist( proj, step );
+
+ F32 expand = aabb_support_radius( hull, n );
+ if( dist > BSP_TRACE_EPSILON ) {
+ if( dist > expand - BSP_EDGE_TOLERANCE )
+ 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,
@@ -281,6 +376,7 @@ U8 bsp_trace_sweep_aabb_to_leaf(
F32 best = FLT_MAX;
BSP_TRACE besthit = *trace;
+ BSP_TRACE edgehit = *trace;
for( U32 i = 0; i < leaf->count; ++i ) {
U32 face_idx = leaf->first + i;
@@ -301,11 +397,22 @@ U8 bsp_trace_sweep_aabb_to_leaf(
}
}
- if( hit ) {
- *trace = besthit;
+ U8 ehit = bsp_trace_sweep_aabb_to_leaf_edges( bsp, &edgehit, hull, start, end, leaf_idx, &best );
+
+ if( hit || ehit ) {
+ if( ehit && !hit )
+ *trace = edgehit;
+ else if( !ehit && hit )
+ *trace = besthit;
+ else if( edgehit.frac < besthit.frac )
+ *trace = edgehit;
+ else
+ *trace = besthit;
trace->hit = 1;
+ return 1;
}
- return hit;
+
+ return 0;
}
U8 bsp_trace_sweep_aabb(
diff --git a/src/util/aabb.h b/src/util/aabb.h
index 96e40bf..9dc4b20 100644
--- a/src/util/aabb.h
+++ b/src/util/aabb.h
@@ -13,3 +13,23 @@ inline F32 aabb_support_radius( const AABB& aabb, const VEC3& dir ) {
VEC3 half = aabb_half( aabb );
return fabsf(dir.x) * half.x + fabsf(dir.y) * half.y + fabsf(dir.z) * half.z;
}
+
+inline U8 aabb_intersects( const AABB& aabb, const AABB& other ) {
+ if (aabb.min.x > other.max.x || aabb.max.x < other.min.x)
+ return 0;
+ if (aabb.min.y > other.max.y || aabb.max.y < other.min.y)
+ return 0;
+ if (aabb.min.z > other.max.z || aabb.max.z < other.min.z)
+ return 0;
+ return 1;
+}
+
+inline U8 aabb_contains_point( const AABB& aabb, const VEC3& point ) {
+ if (point.x < aabb.min.x || point.x > aabb.max.x)
+ return 0;
+ if (point.y < aabb.min.y || point.y > aabb.max.y)
+ return 0;
+ if (point.z < aabb.min.z || point.z > aabb.max.z)
+ return 0;
+ return 1;
+}
diff --git a/src/util/vector.h b/src/util/vector.h
index 6065343..a01689c 100644
--- a/src/util/vector.h
+++ b/src/util/vector.h
@@ -55,6 +55,7 @@ struct VEC3 {
VEC3( const VEC2& v ) { x = v.x; y = v.y; z = 0.f; }
bool operator==( const VEC3& v ) const { return ( x == v.x && y == v.y && z == v.z ); }
+ bool operator!=( const VEC3& v ) const { return !( x == v.x && y == v.y && z == v.z ); }
VEC3& operator=( const VEC3& v ) { x = v.x; y = v.y; z = v.z; return *this; }
F32& operator[]( I32 i ) { return ( (F32*)this )[i]; }
F32 operator[]( I32 i ) const { return ( (F32*)this )[i]; }
@@ -119,6 +120,15 @@ struct VEC4 {
VEC4 operator/( const F32& v ) { return VEC4( x / v, y / v, z / v, w / v ); }
};
+static const VEC2 vec2_right = { 1.f, 0.f };
+static const VEC2 vec2_forward = { 0.f, 1.f };
+static const VEC2 vec2_axis[] = { vec2_right, vec2_forward };
+
+static const VEC3 vec3_up = { 0.f, 0.f, 1.f };
+static const VEC3 vec3_right = { 1.f, 0.f, 0.f };
+static const VEC3 vec3_forward = { 0.f, 1.f, 0.f };
+static const VEC3 vec3_axis[] = { vec3_right, vec3_forward, vec3_up };
+
inline U8 is_zero( VEC2 v ) { return v.x == 0.f && v.y == 0.f; }
inline U8 is_zero( VEC3 v ) { return v.x == 0.f && v.y == 0.f && v.z == 0.f; }
inline U8 is_zero( VEC4 v ) { return v.x == 0.f && v.y == 0.f && v.z == 0.f && v.w == 0.f; }
generated by cgit v1.2.3 (git 2.26.2) at 2026-06-15 19:44:29 +0000