summaryrefslogtreecommitdiff
path: root/src/game/world/trace.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/game/world/trace.cpp')
-rw-r--r--src/game/world/trace.cpp151
1 files changed, 129 insertions, 22 deletions
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(
generated by cgit v1.2.3 (git 2.26.2) at 2026-06-15 21:36:33 +0000