summaryrefslogtreecommitdiff
path: root/src/qcommon
diff options
context:
space:
mode:
Diffstat (limited to 'src/qcommon')
-rw-r--r--src/qcommon/cm_load.c181
-rw-r--r--src/qcommon/cm_local.h51
-rw-r--r--src/qcommon/cm_patch.c8
-rw-r--r--src/qcommon/cm_public.h11
-rw-r--r--src/qcommon/cm_trace.c365
-rw-r--r--src/qcommon/q_math.c124
-rw-r--r--src/qcommon/q_shared.h35
7 files changed, 734 insertions, 41 deletions
diff --git a/src/qcommon/cm_load.c b/src/qcommon/cm_load.c
index f5369fa3..06a037aa 100644
--- a/src/qcommon/cm_load.c
+++ b/src/qcommon/cm_load.c
@@ -426,6 +426,7 @@ void CMod_LoadBrushSides (lump_t *l)
for ( i=0 ; i<count ; i++, in++, out++) {
num = LittleLong( in->planeNum );
+ out->planeNum = num;
out->plane = &cm.planes[num];
out->shaderNum = LittleLong( in->shaderNum );
if ( out->shaderNum < 0 || out->shaderNum >= cm.numShaders ) {
@@ -435,6 +436,151 @@ void CMod_LoadBrushSides (lump_t *l)
}
}
+#define CM_EDGE_VERTEX_EPSILON 0.1f
+
+/*
+=================
+CMod_BrushEdgesAreTheSame
+=================
+*/
+static qboolean CMod_BrushEdgesAreTheSame( const vec3_t p0, const vec3_t p1,
+ const vec3_t q0, const vec3_t q1 )
+{
+ if( VectorCompareEpsilon( p0, q0, CM_EDGE_VERTEX_EPSILON ) &&
+ VectorCompareEpsilon( p1, q1, CM_EDGE_VERTEX_EPSILON ) )
+ return qtrue;
+
+ if( VectorCompareEpsilon( p1, q0, CM_EDGE_VERTEX_EPSILON ) &&
+ VectorCompareEpsilon( p0, q1, CM_EDGE_VERTEX_EPSILON ) )
+ return qtrue;
+
+ return qfalse;
+}
+
+/*
+=================
+CMod_AddEdgeToBrush
+=================
+*/
+static qboolean CMod_AddEdgeToBrush( const vec3_t p0, const vec3_t p1,
+ cbrushedge_t *edges, int *numEdges )
+{
+ int i;
+
+ if( !edges || !numEdges )
+ return qfalse;
+
+ for( i = 0; i < *numEdges; i++ )
+ {
+ if( CMod_BrushEdgesAreTheSame( p0, p1,
+ edges[ i ].p0, edges[ i ].p1 ) )
+ return qfalse;
+ }
+
+ VectorCopy( p0, edges[ *numEdges ].p0 );
+ VectorCopy( p1, edges[ *numEdges ].p1 );
+ (*numEdges)++;
+
+ return qtrue;
+}
+
+/*
+=================
+CMod_CreateBrushSideWindings
+=================
+*/
+static void CMod_CreateBrushSideWindings( void )
+{
+ int i, j, k;
+ winding_t *w;
+ cbrushside_t *side, *chopSide;
+ cplane_t *plane;
+ cbrush_t *brush;
+ cbrushedge_t *tempEdges;
+ int numEdges;
+ int edgesAlloc;
+ int totalEdgesAlloc = 0;
+ int totalEdges = 0;
+
+ for( i = 0; i < cm.numBrushes; i++ )
+ {
+ brush = &cm.brushes[ i ];
+ numEdges = 0;
+
+ // walk the list of brush sides
+ for( j = 0; j < brush->numsides; j++ )
+ {
+ // get side and plane
+ side = &brush->sides[ j ];
+ plane = side->plane;
+
+ w = BaseWindingForPlane( plane->normal, plane->dist );
+
+ // walk the list of brush sides
+ for( k = 0; k < brush->numsides && w != NULL; k++ )
+ {
+ chopSide = &brush->sides[ k ];
+
+ if( chopSide == side )
+ continue;
+
+ if( chopSide->planeNum == ( side->planeNum ^ 1 ) )
+ continue; // back side clipaway
+
+ plane = &cm.planes[ chopSide->planeNum ^ 1 ];
+ ChopWindingInPlace( &w, plane->normal, plane->dist, 0 );
+ }
+
+ if( w )
+ numEdges += w->numpoints;
+
+ // set side winding
+ side->winding = w;
+ }
+
+ // Allocate a temporary buffer of the maximal size
+ tempEdges = (cbrushedge_t *)Z_Malloc( sizeof( cbrushedge_t ) * numEdges );
+ brush->numEdges = 0;
+
+ // compose the points into edges
+ for( j = 0; j < brush->numsides; j++ )
+ {
+ side = &brush->sides[ j ];
+
+ if( side->winding )
+ {
+ for( k = 0; k < side->winding->numpoints - 1; k++ )
+ {
+ if( brush->numEdges == numEdges )
+ Com_Error( ERR_FATAL,
+ "Insufficient memory allocated for collision map edges" );
+
+ CMod_AddEdgeToBrush( side->winding->p[ k ],
+ side->winding->p[ k + 1 ], tempEdges, &brush->numEdges );
+ }
+
+ FreeWinding( side->winding );
+ side->winding = NULL;
+ }
+ }
+
+ // Allocate a buffer of the actual size
+ edgesAlloc = sizeof( cbrushedge_t ) * brush->numEdges;
+ totalEdgesAlloc += edgesAlloc;
+ brush->edges = (cbrushedge_t *)Hunk_Alloc( edgesAlloc, h_low );
+
+ // Copy temporary buffer to permanent buffer
+ Com_Memcpy( brush->edges, tempEdges, edgesAlloc );
+
+ // Free temporary buffer
+ Z_Free( tempEdges );
+
+ totalEdges += brush->numEdges;
+ }
+
+ Com_DPrintf( "Allocated %d bytes for %d collision map edges...\n",
+ totalEdgesAlloc, totalEdges );
+}
/*
=================
@@ -645,6 +791,8 @@ void CM_LoadMap( const char *name, qboolean clientload, int *checksum ) {
CMod_LoadVisibility( &header.lumps[LUMP_VISIBILITY] );
CMod_LoadPatches( &header.lumps[LUMP_SURFACES], &header.lumps[LUMP_DRAWVERTS] );
+ CMod_CreateBrushSideWindings( );
+
// we are NOT freeing the file, because it is cached for the ref
FS_FreeFile (buf);
@@ -755,6 +903,9 @@ void CM_InitBoxHull (void)
box_brush->numsides = 6;
box_brush->sides = cm.brushsides + cm.numBrushSides;
box_brush->contents = CONTENTS_BODY;
+ box_brush->edges = (cbrushedge_t *)Hunk_Alloc(
+ sizeof( cbrushedge_t ) * 12, h_low );
+ box_brush->numEdges = 12;
box_model.leaf.numLeafBrushes = 1;
// box_model.leaf.firstLeafBrush = cm.numBrushes;
@@ -818,6 +969,36 @@ clipHandle_t CM_TempBoxModel( const vec3_t mins, const vec3_t maxs, int capsule
box_planes[10].dist = mins[2];
box_planes[11].dist = -mins[2];
+ // First side
+ VectorSet( box_brush->edges[ 0 ].p0, mins[ 0 ], mins[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 0 ].p1, mins[ 0 ], maxs[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 1 ].p0, mins[ 0 ], maxs[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 1 ].p1, mins[ 0 ], maxs[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 2 ].p0, mins[ 0 ], maxs[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 2 ].p1, mins[ 0 ], mins[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 3 ].p0, mins[ 0 ], mins[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 3 ].p1, mins[ 0 ], mins[ 1 ], mins[ 2 ] );
+
+ // Opposite side
+ VectorSet( box_brush->edges[ 4 ].p0, maxs[ 0 ], mins[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 4 ].p1, maxs[ 0 ], maxs[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 5 ].p0, maxs[ 0 ], maxs[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 5 ].p1, maxs[ 0 ], maxs[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 6 ].p0, maxs[ 0 ], maxs[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 6 ].p1, maxs[ 0 ], mins[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 7 ].p0, maxs[ 0 ], mins[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 7 ].p1, maxs[ 0 ], mins[ 1 ], mins[ 2 ] );
+
+ // Connecting edges
+ VectorSet( box_brush->edges[ 8 ].p0, mins[ 0 ], mins[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 8 ].p1, maxs[ 0 ], mins[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 9 ].p0, mins[ 0 ], maxs[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 9 ].p1, maxs[ 0 ], maxs[ 1 ], mins[ 2 ] );
+ VectorSet( box_brush->edges[ 10 ].p0, mins[ 0 ], maxs[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 10 ].p1, maxs[ 0 ], maxs[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 11 ].p0, mins[ 0 ], mins[ 1 ], maxs[ 2 ] );
+ VectorSet( box_brush->edges[ 11 ].p1, maxs[ 0 ], mins[ 1 ], maxs[ 2 ] );
+
VectorCopy( mins, box_brush->bounds[0] );
VectorCopy( maxs, box_brush->bounds[1] );
diff --git a/src/qcommon/cm_local.h b/src/qcommon/cm_local.h
index 0b4f72cc..cc69482b 100644
--- a/src/qcommon/cm_local.h
+++ b/src/qcommon/cm_local.h
@@ -51,10 +51,18 @@ typedef struct cmodel_s {
cLeaf_t leaf; // submodels don't reference the main tree
} cmodel_t;
+typedef struct cbrushedge_s
+{
+ vec3_t p0;
+ vec3_t p1;
+} cbrushedge_t;
+
typedef struct {
- cplane_t *plane;
- int surfaceFlags;
- int shaderNum;
+ cplane_t *plane;
+ int planeNum;
+ int surfaceFlags;
+ int shaderNum;
+ winding_t *winding;
} cbrushside_t;
typedef struct {
@@ -64,6 +72,9 @@ typedef struct {
int numsides;
cbrushside_t *sides;
int checkcount; // to avoid repeated testings
+ qboolean collided; // marker for optimisation
+ cbrushedge_t *edges;
+ int numEdges;
} cbrush_t;
@@ -143,28 +154,36 @@ extern cvar_t *cm_playerCurveClip;
// cm_test.c
+typedef struct
+{
+ float startRadius;
+ float endRadius;
+} biSphere_t;
+
// Used for oriented capsule collision detection
typedef struct
{
- qboolean use;
float radius;
float halfheight;
vec3_t offset;
} sphere_t;
typedef struct {
- vec3_t start;
- vec3_t end;
- vec3_t size[2]; // size of the box being swept through the model
- vec3_t offsets[8]; // [signbits][x] = either size[0][x] or size[1][x]
- float maxOffset; // longest corner length from origin
- vec3_t extents; // greatest of abs(size[0]) and abs(size[1])
- vec3_t bounds[2]; // enclosing box of start and end surrounding by size
- vec3_t modelOrigin;// origin of the model tracing through
- int contents; // ored contents of the model tracing through
- qboolean isPoint; // optimized case
- trace_t trace; // returned from trace call
- sphere_t sphere; // sphere for oriendted capsule collision
+ traceType_t type;
+ vec3_t start;
+ vec3_t end;
+ vec3_t size[2]; // size of the box being swept through the model
+ vec3_t offsets[8]; // [signbits][x] = either size[0][x] or size[1][x]
+ float maxOffset; // longest corner length from origin
+ vec3_t extents; // greatest of abs(size[0]) and abs(size[1])
+ vec3_t bounds[2]; // enclosing box of start and end surrounding by size
+ vec3_t modelOrigin;// origin of the model tracing through
+ int contents; // ored contents of the model tracing through
+ qboolean isPoint; // optimized case
+ trace_t trace; // returned from trace call
+ sphere_t sphere; // sphere for oriendted capsule collision
+ biSphere_t biSphere;
+ qboolean testLateralCollision; // whether or not to test for lateral collision
} traceWork_t;
typedef struct leafList_s {
diff --git a/src/qcommon/cm_patch.c b/src/qcommon/cm_patch.c
index 806021da..fa0ff55a 100644
--- a/src/qcommon/cm_patch.c
+++ b/src/qcommon/cm_patch.c
@@ -1400,7 +1400,7 @@ void CM_TraceThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *
planes = &pc->planes[ facet->surfacePlane ];
VectorCopy(planes->plane, plane);
plane[3] = planes->plane[3];
- if ( tw->sphere.use ) {
+ if ( tw->type == TT_CAPSULE ) {
// adjust the plane distance apropriately for radius
plane[3] += tw->sphere.radius;
@@ -1439,7 +1439,7 @@ void CM_TraceThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *
VectorCopy(planes->plane, plane);
plane[3] = planes->plane[3];
}
- if ( tw->sphere.use ) {
+ if ( tw->type == TT_CAPSULE ) {
// adjust the plane distance apropriately for radius
plane[3] += tw->sphere.radius;
@@ -1528,7 +1528,7 @@ qboolean CM_PositionTestInPatchCollide( traceWork_t *tw, const struct patchColli
planes = &pc->planes[ facet->surfacePlane ];
VectorCopy(planes->plane, plane);
plane[3] = planes->plane[3];
- if ( tw->sphere.use ) {
+ if ( tw->type == TT_CAPSULE ) {
// adjust the plane distance apropriately for radius
plane[3] += tw->sphere.radius;
@@ -1561,7 +1561,7 @@ qboolean CM_PositionTestInPatchCollide( traceWork_t *tw, const struct patchColli
VectorCopy(planes->plane, plane);
plane[3] = planes->plane[3];
}
- if ( tw->sphere.use ) {
+ if ( tw->type == TT_CAPSULE ) {
// adjust the plane distance apropriately for radius
plane[3] += tw->sphere.radius;
diff --git a/src/qcommon/cm_public.h b/src/qcommon/cm_public.h
index ea5b203d..68d04afe 100644
--- a/src/qcommon/cm_public.h
+++ b/src/qcommon/cm_public.h
@@ -41,11 +41,18 @@ int CM_TransformedPointContents( const vec3_t p, clipHandle_t model, const vec
void CM_BoxTrace ( trace_t *results, const vec3_t start, const vec3_t end,
vec3_t mins, vec3_t maxs,
- clipHandle_t model, int brushmask, int capsule );
+ clipHandle_t model, int brushmask, traceType_t type );
void CM_TransformedBoxTrace( trace_t *results, const vec3_t start, const vec3_t end,
vec3_t mins, vec3_t maxs,
clipHandle_t model, int brushmask,
- const vec3_t origin, const vec3_t angles, int capsule );
+ const vec3_t origin, const vec3_t angles, traceType_t type );
+void CM_BiSphereTrace( trace_t *results, const vec3_t start,
+ const vec3_t end, float startRad, float endRad,
+ clipHandle_t model, int mask );
+void CM_TransformedBiSphereTrace( trace_t *results, const vec3_t start,
+ const vec3_t end, float startRad, float endRad,
+ clipHandle_t model, int mask,
+ const vec3_t origin );
byte *CM_ClusterPVS (int cluster);
diff --git a/src/qcommon/cm_trace.c b/src/qcommon/cm_trace.c
index 750bd2e3..483b0756 100644
--- a/src/qcommon/cm_trace.c
+++ b/src/qcommon/cm_trace.c
@@ -186,7 +186,7 @@ void CM_TestBoxInBrush( traceWork_t *tw, cbrush_t *brush ) {
return;
}
- if ( tw->sphere.use ) {
+ if ( tw->type == TT_CAPSULE ) {
// the first six planes are the axial planes, so we only
// need to test the remainder
for ( i = 6 ; i < brush->numsides ; i++ ) {
@@ -393,7 +393,7 @@ void CM_TestBoundingBoxInCapsule( traceWork_t *tw, clipHandle_t model ) {
}
// replace the bounding box with the capsule
- tw->sphere.use = qtrue;
+ tw->type = TT_CAPSULE;
tw->sphere.radius = ( size[1][0] > size[1][2] ) ? size[1][2]: size[1][0];
tw->sphere.halfheight = size[1][2];
VectorSet( tw->sphere.offset, 0, 0, size[1][2] - tw->sphere.radius );
@@ -456,7 +456,6 @@ TRACING
===============================================================================
*/
-
/*
================
CM_TraceThroughPatch
@@ -511,7 +510,70 @@ void CM_TraceThroughBrush( traceWork_t *tw, cbrush_t *brush ) {
leadside = NULL;
- if ( tw->sphere.use ) {
+ if( tw->type == TT_BISPHERE )
+ {
+ //
+ // compare the trace against all planes of the brush
+ // find the latest time the trace crosses a plane towards the interior
+ // and the earliest time the trace crosses a plane towards the exterior
+ //
+ for( i = 0; i < brush->numsides; i++ )
+ {
+ side = brush->sides + i;
+ plane = side->plane;
+
+ // adjust the plane distance apropriately for radius
+ d1 = DotProduct( tw->start, plane->normal ) -
+ ( plane->dist + tw->biSphere.startRadius );
+ d2 = DotProduct( tw->end, plane->normal ) -
+ ( plane->dist + tw->biSphere.endRadius );
+
+ if( d2 > 0 )
+ getout = qtrue; // endpoint is not in solid
+
+ if( d1 > 0 )
+ startout = qtrue;
+
+ // if completely in front of face, no intersection with the entire brush
+ if( d1 > 0 && ( d2 >= SURFACE_CLIP_EPSILON || d2 >= d1 ) )
+ return;
+
+ // if it doesn't cross the plane, the plane isn't relevent
+ if( d1 <= 0 && d2 <= 0 )
+ continue;
+
+ brush->collided = qtrue;
+
+ // crosses face
+ if( d1 > d2 )
+ {
+ // enter
+ f = ( d1 - SURFACE_CLIP_EPSILON ) / ( d1 - d2 );
+
+ if( f < 0 )
+ f = 0;
+
+ if( f > enterFrac )
+ {
+ enterFrac = f;
+ clipplane = plane;
+ leadside = side;
+ }
+ }
+ else
+ {
+ // leave
+ f = ( d1 + SURFACE_CLIP_EPSILON ) / ( d1 - d2 );
+
+ if( f > 1 )
+ f = 1;
+
+ if( f < leaveFrac )
+ leaveFrac = f;
+ }
+ }
+ }
+ else if ( tw->type == TT_CAPSULE ) {
//
// compare the trace against all planes of the brush
// find the latest time the trace crosses a plane towards the interior
@@ -557,6 +619,8 @@ void CM_TraceThroughBrush( traceWork_t *tw, cbrush_t *brush ) {
continue;
}
+ brush->collided = qtrue;
+
// crosses face
if (d1 > d2) { // enter
f = (d1-SURFACE_CLIP_EPSILON) / (d1-d2);
@@ -611,6 +675,8 @@ void CM_TraceThroughBrush( traceWork_t *tw, cbrush_t *brush ) {
continue;
}
+ brush->collided = qtrue;
+
// crosses face
if (d1 > d2) { // enter
f = (d1-SURFACE_CLIP_EPSILON) / (d1-d2);
@@ -663,6 +729,98 @@ void CM_TraceThroughBrush( traceWork_t *tw, cbrush_t *brush ) {
/*
================
+CM_ProximityToBrush
+================
+*/
+static void CM_ProximityToBrush( traceWork_t *tw, cbrush_t *brush )
+{
+ int i;
+ cbrushedge_t *edge;
+ float dist, minDist = 1e+10f;
+ float s, t;
+ float sAtMin, radius, fraction;
+ traceWork_t tw2;
+
+ // cheapish purely linear trace to test for intersection
+ Com_Memset( &tw2, 0, sizeof( tw2 ) );
+ tw2.trace.fraction = 1.0f;
+ tw2.type = TT_CAPSULE;
+ tw2.sphere.radius = 0.0f;
+ VectorClear( tw2.sphere.offset );
+ VectorCopy( tw->start, tw2.start );
+ VectorCopy( tw->end, tw2.end );
+
+ CM_TraceThroughBrush( &tw2, brush );
+
+ if( tw2.trace.fraction == 1.0f && !tw2.trace.allsolid && !tw2.trace.startsolid )
+ {
+ for( i = 0; i < brush->numEdges; i++ )
+ {
+ edge = &brush->edges[ i ];
+
+ dist = DistanceBetweenLineSegmentsSquared( tw->start, tw->end,
+ edge->p0, edge->p1, &s, &t );
+
+ if( dist < minDist )
+ {
+ minDist = dist;
+ sAtMin = s;
+ }
+ }
+
+ if( tw->type == TT_BISPHERE )
+ {
+ radius = tw->biSphere.startRadius +
+ ( sAtMin * ( tw->biSphere.endRadius - tw->biSphere.startRadius ) );
+ }
+ else if( tw->type == TT_CAPSULE )
+ {
+ radius = tw->sphere.radius;
+ }
+ else if( tw->type == TT_AABB )
+ {
+ //FIXME
+ }
+
+ fraction = minDist / ( radius * radius );
+
+ if( fraction < tw->trace.lateralFraction )
+ tw->trace.lateralFraction = fraction;
+ }
+ else
+ tw->trace.lateralFraction = 0.0f;
+}
+
+/*
+================
+CM_ProximityToPatch
+================
+*/
+static void CM_ProximityToPatch( traceWork_t *tw, cPatch_t *patch )
+{
+ traceWork_t tw2;
+
+ // cheapish purely linear trace to test for intersection
+ Com_Memset( &tw2, 0, sizeof( tw2 ) );
+ tw2.trace.fraction = 1.0f;
+ tw2.type = TT_CAPSULE;
+ tw2.sphere.radius = 0.0f;
+ VectorClear( tw2.sphere.offset );
+ VectorCopy( tw->start, tw2.start );
+ VectorCopy( tw->end, tw2.end );
+
+ CM_TraceThroughPatch( &tw2, patch );
+
+ if( tw2.trace.fraction == 1.0f && !tw2.trace.allsolid && !tw2.trace.startsolid )
+ {
+ //FIXME: implement me
+ }
+ else
+ tw->trace.lateralFraction = 0.0f;
+}
+
+/*
+================
CM_TraceThroughLeaf
================
*/
@@ -686,8 +844,11 @@ void CM_TraceThroughLeaf( traceWork_t *tw, cLeaf_t *leaf ) {
continue;
}
+ b->collided = qfalse;
+
CM_TraceThroughBrush( tw, b );
if ( !tw->trace.fraction ) {
+ tw->trace.lateralFraction = 0.0f;
return;
}
}
@@ -713,11 +874,50 @@ void CM_TraceThroughLeaf( traceWork_t *tw, cLeaf_t *leaf ) {
}
CM_TraceThroughPatch( tw, patch );
+
if ( !tw->trace.fraction ) {
+ tw->trace.lateralFraction = 0.0f;
return;
}
}
}
+
+ if( tw->testLateralCollision && tw->trace.fraction < 1.0f )
+ {
+ for( k = 0; k < leaf->numLeafBrushes; k++ )
+ {
+ brushnum = cm.leafbrushes[ leaf->firstLeafBrush + k ];
+
+ b = &cm.brushes[ brushnum ];
+
+ // This brush never collided, so don't bother
+ if( !b->collided )
+ continue;
+
+ if( !( b->contents & tw->contents ) )
+ continue;
+
+ CM_ProximityToBrush( tw, b );
+
+ if( !tw->trace.lateralFraction )
+ return;
+ }
+
+ for( k = 0; k < leaf->numLeafSurfaces; k++ )
+ {
+ patch = cm.surfaces[ cm.leafsurfaces[ leaf->firstLeafSurface + k ] ];
+ if( !patch )
+ continue;
+
+ if( !( patch->contents & tw->contents ) )
+ continue;
+
+ CM_ProximityToPatch( tw, patch );
+
+ if( !tw->trace.lateralFraction )
+ return;
+ }
+ }
}
#define RADIUS_EPSILON 1.0f
@@ -1001,7 +1201,7 @@ void CM_TraceBoundingBoxThroughCapsule( traceWork_t *tw, clipHandle_t model ) {
}
// replace the bounding box with the capsule
- tw->sphere.use = qtrue;
+ tw->type = TT_CAPSULE;
tw->sphere.radius = ( size[1][0] > size[1][2] ) ? size[1][2]: size[1][0];
tw->sphere.halfheight = size[1][2];
VectorSet( tw->sphere.offset, 0, 0, size[1][2] - tw->sphere.radius );
@@ -1140,7 +1340,6 @@ void CM_TraceThroughTree( traceWork_t *tw, int num, float p1f, float p2f, vec3_t
CM_TraceThroughTree( tw, node->children[side^1], midf, p2f, mid, p2 );
}
-
//======================================================================
@@ -1149,8 +1348,10 @@ void CM_TraceThroughTree( traceWork_t *tw, int num, float p1f, float p2f, vec3_t
CM_Trace
==================
*/
-void CM_Trace( trace_t *results, const vec3_t start, const vec3_t end, vec3_t mins, vec3_t maxs,
- clipHandle_t model, const vec3_t origin, int brushmask, int capsule, sphere_t *sphere ) {
+void CM_Trace( trace_t *results, const vec3_t start,
+ const vec3_t end, vec3_t mins, vec3_t maxs,
+ clipHandle_t model, const vec3_t origin, int brushmask,
+ traceType_t type, sphere_t *sphere ) {
int i;
traceWork_t tw;
vec3_t offset;
@@ -1166,6 +1367,7 @@ void CM_Trace( trace_t *results, const vec3_t start, const vec3_t end, vec3_t mi
Com_Memset( &tw, 0, sizeof(tw) );
tw.trace.fraction = 1; // assume it goes the entire distance until shown otherwise
VectorCopy(origin, tw.modelOrigin);
+ tw.type = type;
if (!cm.numNodes) {
*results = tw.trace;
@@ -1200,7 +1402,6 @@ void CM_Trace( trace_t *results, const vec3_t start, const vec3_t end, vec3_t mi
tw.sphere = *sphere;
}
else {
- tw.sphere.use = capsule;
tw.sphere.radius = ( tw.size[1][0] > tw.size[1][2] ) ? tw.size[1][2]: tw.size[1][0];
tw.sphere.halfheight = tw.size[1][2];
VectorSet( tw.sphere.offset, 0, 0, tw.size[1][2] - tw.sphere.radius );
@@ -1244,7 +1445,7 @@ void CM_Trace( trace_t *results, const vec3_t start, const vec3_t end, vec3_t mi
//
// calculate bounds
//
- if ( tw.sphere.use ) {
+ if ( tw.type == TT_CAPSULE ) {
for ( i = 0 ; i < 3 ; i++ ) {
if ( tw.start[i] < tw.end[i] ) {
tw.bounds[0][i] = tw.start[i] - fabs(tw.sphere.offset[i]) - tw.sphere.radius;
@@ -1274,7 +1475,7 @@ void CM_Trace( trace_t *results, const vec3_t start, const vec3_t end, vec3_t mi
if ( model ) {
#ifdef ALWAYS_BBOX_VS_BBOX // bk010201 - FIXME - compile time flag?
if ( model == BOX_MODEL_HANDLE || model == CAPSULE_MODEL_HANDLE) {
- tw.sphere.use = qfalse;
+ tw.type = TT_AABB;
CM_TestInLeaf( &tw, &cmod->leaf );
}
else
@@ -1285,7 +1486,7 @@ void CM_Trace( trace_t *results, const vec3_t start, const vec3_t end, vec3_t mi
else
#endif
if ( model == CAPSULE_MODEL_HANDLE ) {
- if ( tw.sphere.use ) {
+ if ( tw.type == TT_CAPSULE ) {
CM_TestCapsuleInCapsule( &tw, model );
}
else {
@@ -1318,7 +1519,7 @@ void CM_Trace( trace_t *results, const vec3_t start, const vec3_t end, vec3_t mi
if ( model ) {
#ifdef ALWAYS_BBOX_VS_BBOX
if ( model == BOX_MODEL_HANDLE || model == CAPSULE_MODEL_HANDLE) {
- tw.sphere.use = qfalse;
+ tw.type = TT_AABB;
CM_TraceThroughLeaf( &tw, &cmod->leaf );
}
else
@@ -1329,7 +1530,7 @@ void CM_Trace( trace_t *results, const vec3_t start, const vec3_t end, vec3_t mi
else
#endif
if ( model == CAPSULE_MODEL_HANDLE ) {
- if ( tw.sphere.use ) {
+ if ( tw.type == TT_CAPSULE ) {
CM_TraceCapsuleThroughCapsule( &tw, model );
}
else {
@@ -1369,8 +1570,8 @@ CM_BoxTrace
*/
void CM_BoxTrace( trace_t *results, const vec3_t start, const vec3_t end,
vec3_t mins, vec3_t maxs,
- clipHandle_t model, int brushmask, int capsule ) {
- CM_Trace( results, start, end, mins, maxs, model, vec3_origin, brushmask, capsule, NULL );
+ clipHandle_t model, int brushmask, traceType_t type ) {
+ CM_Trace( results, start, end, mins, maxs, model, vec3_origin, brushmask, type, NULL );
}
/*
@@ -1384,7 +1585,7 @@ rotating entities
void CM_TransformedBoxTrace( trace_t *results, const vec3_t start, const vec3_t end,
vec3_t mins, vec3_t maxs,
clipHandle_t model, int brushmask,
- const vec3_t origin, const vec3_t angles, int capsule ) {
+ const vec3_t origin, const vec3_t angles, traceType_t type ) {
trace_t trace;
vec3_t start_l, end_l;
qboolean rotated;
@@ -1430,7 +1631,6 @@ void CM_TransformedBoxTrace( trace_t *results, const vec3_t start, const vec3_t
halfwidth = symetricSize[ 1 ][ 0 ];
halfheight = symetricSize[ 1 ][ 2 ];
- sphere.use = capsule;
sphere.radius = ( halfwidth > halfheight ) ? halfheight : halfwidth;
sphere.halfheight = halfheight;
t = halfheight - sphere.radius;
@@ -1455,7 +1655,8 @@ void CM_TransformedBoxTrace( trace_t *results, const vec3_t start, const vec3_t
}
// sweep the box through the model
- CM_Trace( &trace, start_l, end_l, symetricSize[0], symetricSize[1], model, origin, brushmask, capsule, &sphere );
+ CM_Trace( &trace, start_l, end_l, symetricSize[0], symetricSize[1],
+ model, origin, brushmask, type, &sphere );
// if the bmodel was rotated and there was a collision
if ( rotated && trace.fraction != 1.0 ) {
@@ -1472,3 +1673,129 @@ void CM_TransformedBoxTrace( trace_t *results, const vec3_t start, const vec3_t
*results = trace;
}
+
+/*
+==================
+CM_BiSphereTrace
+==================
+*/
+void CM_BiSphereTrace( trace_t *results, const vec3_t start,
+ const vec3_t end, float startRad, float endRad,
+ clipHandle_t model, int mask )
+{
+ int i;
+ traceWork_t tw;
+ float largestRadius = startRad > endRad ? startRad : endRad;
+ cmodel_t *cmod;
+
+ cmod = CM_ClipHandleToModel( model );
+
+ cm.checkcount++; // for multi-check avoidance
+
+ c_traces++; // for statistics, may be zeroed
+
+ // fill in a default trace
+ Com_Memset( &tw, 0, sizeof( tw ) );
+ tw.trace.fraction = 1.0f; // assume it goes the entire distance until shown otherwise
+ VectorCopy( vec3_origin, tw.modelOrigin );
+ tw.type = TT_BISPHERE;
+ tw.testLateralCollision = qtrue;
+ tw.trace.lateralFraction = 1.0f;
+
+ if( !cm.numNodes )
+ {
+ *results = tw.trace;
+
+ return; // map not loaded, shouldn't happen
+ }
+
+ // set basic parms
+ tw.contents = mask;
+
+ VectorCopy( start, tw.start );
+ VectorCopy( end, tw.end );
+
+ tw.biSphere.startRadius = startRad;
+ tw.biSphere.endRadius = endRad;
+
+ //
+ // calculate bounds
+ //
+ for( i = 0 ; i < 3 ; i++ )
+ {
+ if( tw.start[ i ] < tw.end[ i ] )
+ {
+ tw.bounds[ 0 ][ i ] = tw.start[ i ] - tw.biSphere.startRadius;
+ tw.bounds[ 1 ][ i ] = tw.end[ i ] + tw.biSphere.endRadius;
+ }
+ else
+ {
+ tw.bounds[ 0 ][ i ] = tw.end[ i ] + tw.biSphere.endRadius;
+ tw.bounds[ 1 ][ i ] = tw.start[ i ] - tw.biSphere.startRadius;
+ }
+ }
+
+ tw.isPoint = qfalse;
+ tw.extents[ 0 ] = largestRadius;
+ tw.extents[ 1 ] = largestRadius;
+ tw.extents[ 2 ] = largestRadius;
+
+ //
+ // general sweeping through world
+ //
+ if( model )
+ CM_TraceThroughLeaf( &tw, &cmod->leaf );
+ else
+ CM_TraceThroughTree( &tw, 0, 0.0f, 1.0f, tw.start, tw.end );
+
+ // generate endpos from the original, unmodified start/end
+ if( tw.trace.fraction == 1.0f )
+ {
+ VectorCopy( end, tw.trace.endpos );
+ }
+ else
+ {
+ for( i = 0; i < 3; i++ )
+ tw.trace.endpos[ i ] = start[ i ] + tw.trace.fraction * ( end[ i ] - start[ i ] );
+ }
+
+ // If allsolid is set (was entirely inside something solid), the plane is not valid.
+ // If fraction == 1.0, we never hit anything, and thus the plane is not valid.
+ // Otherwise, the normal on the plane should have unit length
+ assert( tw.trace.allsolid ||
+ tw.trace.fraction == 1.0 ||
+ VectorLengthSquared(tw.trace.plane.normal ) > 0.9999 );
+
+ *results = tw.trace;
+}
+
+/*
+==================
+CM_TransformedBiSphereTrace
+
+Handles offseting and rotation of the end points for moving and
+rotating entities
+==================
+*/
+void CM_TransformedBiSphereTrace( trace_t *results, const vec3_t start,
+ const vec3_t end, float startRad, float endRad,
+ clipHandle_t model, int mask,
+ const vec3_t origin )
+{
+ trace_t trace;
+ vec3_t start_l, end_l;
+
+ // subtract origin offset
+ VectorSubtract( start, origin, start_l );
+ VectorSubtract( end, origin, end_l );
+
+ CM_BiSphereTrace( &trace, start_l, end_l, startRad, endRad, model, mask );
+
+ // re-calculate the end position of the trace because the trace.endpos
+ // calculated by CM_BiSphereTrace could be rotated and have an offset
+ trace.endpos[0] = start[0] + trace.fraction * (end[0] - start[0]);
+ trace.endpos[1] = start[1] + trace.fraction * (end[1] - start[1]);
+ trace.endpos[2] = start[2] + trace.fraction * (end[2] - start[2]);
+
+ *results = trace;
+}
diff --git a/src/qcommon/q_math.c b/src/qcommon/q_math.c
index 189fb0a2..bf209562 100644
--- a/src/qcommon/q_math.c
+++ b/src/qcommon/q_math.c
@@ -1414,3 +1414,127 @@ float VectorMinComponent( vec3_t v )
return smallest;
}
+
+
+#define LINE_DISTANCE_EPSILON 1e-05f
+
+/*
+================
+DistanceBetweenLineSegmentsSquared
+
+Return the smallest distance between two line segments, squared
+================
+*/
+vec_t DistanceBetweenLineSegmentsSquared(
+ const vec3_t sP0, const vec3_t sP1,
+ const vec3_t tP0, const vec3_t tP1,
+ float *s, float *t )
+{
+ vec3_t sMag, tMag, diff;
+ float a, b, c, d, e;
+ float D;
+ float sN, sD;
+ float tN, tD;
+ vec3_t separation;
+
+ VectorSubtract( sP1, sP0, sMag );
+ VectorSubtract( tP1, tP0, tMag );
+ VectorSubtract( sP0, tP0, diff );
+ a = DotProduct( sMag, sMag );
+ b = DotProduct( sMag, tMag );
+ c = DotProduct( tMag, tMag );
+ d = DotProduct( sMag, diff );
+ e = DotProduct( tMag, diff );
+ sD = tD = D = a * c - b * b;
+
+ if( D < LINE_DISTANCE_EPSILON )
+ {
+ // the lines are almost parallel
+ sN = 0.0; // force using point P0 on segment S1
+ sD = 1.0; // to prevent possible division by 0.0 later
+ tN = e;
+ tD = c;
+ }
+ else
+ {
+ // get the closest points on the infinite lines
+ sN = ( b * e - c * d );
+ tN = ( a * e - b * d );
+
+ if( sN < 0.0 )
+ {
+ // sN < 0 => the s=0 edge is visible
+ sN = 0.0;
+ tN = e;
+ tD = c;
+ }
+ else if( sN > sD )
+ {
+ // sN > sD => the s=1 edge is visible
+ sN = sD;
+ tN = e + b;
+ tD = c;
+ }
+ }
+
+ if( tN < 0.0 )
+ {
+ // tN < 0 => the t=0 edge is visible
+ tN = 0.0;
+
+ // recompute sN for this edge
+ if( -d < 0.0 )
+ sN = 0.0;
+ else if( -d > a )
+ sN = sD;
+ else
+ {
+ sN = -d;
+ sD = a;
+ }
+ }
+ else if( tN > tD )
+ {
+ // tN > tD => the t=1 edge is visible
+ tN = tD;
+
+ // recompute sN for this edge
+ if( ( -d + b ) < 0.0 )
+ sN = 0;
+ else if( ( -d + b ) > a )
+ sN = sD;
+ else
+ {
+ sN = ( -d + b );
+ sD = a;
+ }
+ }
+
+ // finally do the division to get *s and *t
+ *s = ( fabs( sN ) < LINE_DISTANCE_EPSILON ? 0.0 : sN / sD );
+ *t = ( fabs( tN ) < LINE_DISTANCE_EPSILON ? 0.0 : tN / tD );
+
+ // get the difference of the two closest points
+ VectorScale( sMag, *s, sMag );
+ VectorScale( tMag, *t, tMag );
+ VectorAdd( diff, sMag, separation );
+ VectorSubtract( separation, tMag, separation );
+
+ return VectorLengthSquared( separation );
+}
+
+/*
+================
+DistanceBetweenLineSegments
+
+Return the smallest distance between two line segments
+================
+*/
+vec_t DistanceBetweenLineSegments(
+ const vec3_t sP0, const vec3_t sP1,
+ const vec3_t tP0, const vec3_t tP1,
+ float *s, float *t )
+{
+ return (vec_t)sqrt( DistanceBetweenLineSegmentsSquared(
+ sP0, sP1, tP0, tP1, s, t ) );
+}
diff --git a/src/qcommon/q_shared.h b/src/qcommon/q_shared.h
index 737b9f0e..6dd8527d 100644
--- a/src/qcommon/q_shared.h
+++ b/src/qcommon/q_shared.h
@@ -461,6 +461,22 @@ static ID_INLINE int VectorCompare( const vec3_t v1, const vec3_t v2 ) {
return 1;
}
+static ID_INLINE int VectorCompareEpsilon(
+ const vec3_t v1, const vec3_t v2, float epsilon )
+{
+ vec3_t d;
+
+ VectorSubtract( v1, v2, d );
+ d[ 0 ] = fabs( d[ 0 ] );
+ d[ 1 ] = fabs( d[ 1 ] );
+ d[ 2 ] = fabs( d[ 2 ] );
+
+ if( d[ 0 ] > epsilon || d[ 1 ] > epsilon || d[ 2 ] > epsilon )
+ return 0;
+
+ return 1;
+}
+
static ID_INLINE vec_t VectorLength( const vec3_t v ) {
return (vec_t)sqrt (v[0]*v[0] + v[1]*v[1] + v[2]*v[2]);
}
@@ -585,6 +601,15 @@ float pointToLineDistance( const vec3_t point, const vec3_t p1, const vec3_t p2
float VectorMinComponent( vec3_t v );
float VectorMaxComponent( vec3_t v );
+vec_t DistanceBetweenLineSegmentsSquared(
+ const vec3_t sP0, const vec3_t sP1,
+ const vec3_t tP0, const vec3_t tP1,
+ float *s, float *t );
+vec_t DistanceBetweenLineSegments(
+ const vec3_t sP0, const vec3_t sP1,
+ const vec3_t tP0, const vec3_t tP1,
+ float *s, float *t );
+
#ifndef MAX
#define MAX(x,y) (x)>(y)?(x):(y)
#endif
@@ -826,6 +851,15 @@ typedef struct cplane_s {
byte pad[2];
} cplane_t;
+typedef enum {
+ TT_NONE,
+
+ TT_AABB,
+ TT_CAPSULE,
+ TT_BISPHERE,
+
+ TT_NUM_TRACE_TYPES
+} traceType_t;
// a trace is returned when a box is swept through the world
typedef struct {
@@ -837,6 +871,7 @@ typedef struct {
int surfaceFlags; // surface hit
int contents; // contents on other side of surface hit
int entityNum; // entity the contacted sirface is a part of
+ float lateralFraction; // fraction of collision tangetially to the trace direction
} trace_t;
// trace->entityNum can also be 0 to (MAX_GENTITIES-1)
generated by cgit (git 2.34.1) at 2024-11-15 07:43:52 +0000