diff options
author | Tim Angus <tim@ngus.net> | 2005-12-20 00:53:13 +0000 |
---|---|---|
committer | Tim Angus <tim@ngus.net> | 2005-12-20 00:53:13 +0000 |
commit | 611eb5ee8a55d5aa473c48f8f9436a01e3f0cdb7 (patch) | |
tree | e2c52d2d0c43e5343df017c7578fb99275a8bfed /src | |
parent | 65b823bf367034c204d370a6a73965a196072153 (diff) |
* New collision type, for improved light flares
Diffstat (limited to 'src')
-rw-r--r-- | src/cgame/cg_ents.c | 42 | ||||
-rw-r--r-- | src/cgame/cg_local.h | 18 | ||||
-rw-r--r-- | src/cgame/cg_predict.c | 50 | ||||
-rw-r--r-- | src/cgame/cg_public.h | 2 | ||||
-rw-r--r-- | src/cgame/cg_syscalls.asm | 2 | ||||
-rw-r--r-- | src/cgame/cg_syscalls.c | 17 | ||||
-rw-r--r-- | src/client/cl_cgame.c | 17 | ||||
-rw-r--r-- | src/qcommon/cm_load.c | 181 | ||||
-rw-r--r-- | src/qcommon/cm_local.h | 51 | ||||
-rw-r--r-- | src/qcommon/cm_patch.c | 8 | ||||
-rw-r--r-- | src/qcommon/cm_public.h | 11 | ||||
-rw-r--r-- | src/qcommon/cm_trace.c | 365 | ||||
-rw-r--r-- | src/qcommon/q_math.c | 124 | ||||
-rw-r--r-- | src/qcommon/q_shared.h | 35 | ||||
-rw-r--r-- | src/server/server.h | 4 | ||||
-rw-r--r-- | src/server/sv_game.c | 12 | ||||
-rw-r--r-- | src/server/sv_world.c | 14 |
17 files changed, 850 insertions, 103 deletions
diff --git a/src/cgame/cg_ents.c b/src/cgame/cg_ents.c index f2f593cf..0c279a31 100644 --- a/src/cgame/cg_ents.c +++ b/src/cgame/cg_ents.c @@ -670,10 +670,10 @@ static void CG_LightFlare( centity_t *cent ) float radiusMod = 1.0f - ( 180.0f - RAD2DEG( acos( DotProduct( delta, forward ) ) ) ) / maxAngle; - if( es->eFlags & EF_NODRAW ) - flare.radius *= radiusMod; - else if( radiusMod < 0.0f ) - flare.radius = 0.0f; + if( radiusMod < 0.0f ) + radiusMod = 0.0f; + + flare.radius *= radiusMod; } if( flare.radius < 0.0f ) @@ -684,34 +684,14 @@ static void CG_LightFlare( centity_t *cent ) if( cg_lightFlare.integer == FLARE_REALFADE ) { - //draw "correct" albeit inefficient flares - srLocal = cent->lfs.lastSrcRadius; - - //flare radius is likely to be the same as last frame so start with it - do - { - srLocal += RADIUSSTEP; - SETBOUNDS( mins, maxs, srLocal ); - CG_Trace( &tr, start, mins, maxs, end, - entityNum, MASK_SHOT ); - - } while( ( tr.fraction == 1.0f && !tr.startsolid ) && ( srLocal < srcRadius ) ); - - srLocal -= RADIUSSTEP; + //"correct" flares + CG_BiSphereTrace( &tr, cg.refdef.vieworg, end, + 1.0f, srcRadius, entityNum, MASK_SHOT ); - //shink the flare until there is a los - do - { - SETBOUNDS( mins, maxs, srLocal ); - CG_Trace( &tr, start, mins, maxs, end, - entityNum, MASK_SHOT ); - - srLocal -= RADIUSSTEP; - } while( ( tr.fraction < 1.0f || tr.startsolid ) && ( srLocal > 0.0f ) ); - - ratio = srLocal / srcRadius; - - cent->lfs.lastSrcRadius = srLocal; + if( tr.fraction < 1.0f ) + ratio = tr.lateralFraction; + else + ratio = 1.0f; } else if( cg_lightFlare.integer == FLARE_TIMEFADE ) { diff --git a/src/cgame/cg_local.h b/src/cgame/cg_local.h index b88d8d0c..b319e547 100644 --- a/src/cgame/cg_local.h +++ b/src/cgame/cg_local.h @@ -591,7 +591,6 @@ typedef struct typedef struct lightFlareStatus_s { - float lastSrcRadius; //caching of likely flare source radius float lastRadius; //caching of likely flare radius float lastRatio; //caching of likely flare ratio int lastTime; //last time flare was visible/occluded @@ -1637,10 +1636,12 @@ void CG_ModelDoor( centity_t *cent ); void CG_BuildSolidList( void ); int CG_PointContents( const vec3_t point, int passEntityNum ); -void CG_Trace( trace_t *result, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, - int skipNumber, int mask ); -void CG_CapTrace( trace_t *result, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, - int skipNumber, int mask ); +void CG_Trace( trace_t *result, const vec3_t start, const vec3_t mins, const vec3_t maxs, + const vec3_t end, int skipNumber, int mask ); +void CG_CapTrace( trace_t *result, const vec3_t start, const vec3_t mins, const vec3_t maxs, + const vec3_t end, int skipNumber, int mask ); +void CG_BiSphereTrace( trace_t *result, const vec3_t start, const vec3_t end, + const float startRadius, const float endRadius, int skipNumber, int mask ); void CG_PredictPlayerState( void ); @@ -1891,6 +1892,13 @@ void trap_CM_TransformedCapsuleTrace( trace_t *results, const vec3_t st const vec3_t mins, const vec3_t maxs, clipHandle_t model, int brushmask, const vec3_t origin, const vec3_t angles ); +void trap_CM_BiSphereTrace( trace_t *results, const vec3_t start, + const vec3_t end, float startRad, float endRad, + clipHandle_t model, int mask ); +void trap_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 ); // Returns the projection of a polygon onto the solid brushes in the world int trap_CM_MarkFragments( int numPoints, const vec3_t *points, diff --git a/src/cgame/cg_predict.c b/src/cgame/cg_predict.c index 5d2950cb..8c4bc8e3 100644 --- a/src/cgame/cg_predict.c +++ b/src/cgame/cg_predict.c @@ -87,8 +87,9 @@ CG_ClipMoveToEntities ==================== */ -static void CG_ClipMoveToEntities ( const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, - int skipNumber, int mask, trace_t *tr, qboolean capsule ) +static void CG_ClipMoveToEntities ( const vec3_t start, const vec3_t mins, + const vec3_t maxs, const vec3_t end, int skipNumber, + int mask, trace_t *tr, traceType_t collisionType ) { int i, j, x, zd, zu; trace_t trace; @@ -145,21 +146,34 @@ static void CG_ClipMoveToEntities ( const vec3_t start, const vec3_t mins, const } - if( capsule ) + if( collisionType == TT_CAPSULE ) { trap_CM_TransformedCapsuleTrace ( &trace, start, end, mins, maxs, cmodel, mask, origin, angles ); } - else + else if( collisionType == TT_AABB ) { trap_CM_TransformedBoxTrace ( &trace, start, end, mins, maxs, cmodel, mask, origin, angles ); } + else if( collisionType == TT_BISPHERE ) + { + trap_CM_TransformedBiSphereTrace( &trace, start, end, + mins[ 0 ], maxs[ 0 ], cmodel, mask, origin ); + } if( trace.allsolid || trace.fraction < tr->fraction ) { trace.entityNum = ent->number; - *tr = trace; + + if( tr->lateralFraction < trace.lateralFraction ) + { + float oldLateralFraction = tr->lateralFraction; + *tr = trace; + tr->lateralFraction = oldLateralFraction; + } + else + *tr = trace; } else if( trace.startsolid ) tr->startsolid = qtrue; @@ -182,7 +196,7 @@ void CG_Trace( trace_t *result, const vec3_t start, const vec3_t mins, const ve trap_CM_BoxTrace( &t, start, end, mins, maxs, 0, mask ); t.entityNum = t.fraction != 1.0 ? ENTITYNUM_WORLD : ENTITYNUM_NONE; // check all other solid models - CG_ClipMoveToEntities( start, mins, maxs, end, skipNumber, mask, &t, qfalse ); + CG_ClipMoveToEntities( start, mins, maxs, end, skipNumber, mask, &t, TT_AABB ); *result = t; } @@ -200,7 +214,29 @@ void CG_CapTrace( trace_t *result, const vec3_t start, const vec3_t mins, const trap_CM_CapsuleTrace( &t, start, end, mins, maxs, 0, mask ); t.entityNum = t.fraction != 1.0 ? ENTITYNUM_WORLD : ENTITYNUM_NONE; // check all other solid models - CG_ClipMoveToEntities( start, mins, maxs, end, skipNumber, mask, &t, qtrue ); + CG_ClipMoveToEntities( start, mins, maxs, end, skipNumber, mask, &t, TT_CAPSULE ); + + *result = t; +} + +/* +================ +CG_BiSphereTrace +================ +*/ +void CG_BiSphereTrace( trace_t *result, const vec3_t start, const vec3_t end, + const float startRadius, const float endRadius, int skipNumber, int mask ) +{ + trace_t t; + vec3_t mins, maxs; + + mins[ 0 ] = startRadius; + maxs[ 0 ] = endRadius; + + trap_CM_BiSphereTrace( &t, start, end, startRadius, endRadius, 0, mask ); + t.entityNum = t.fraction != 1.0 ? ENTITYNUM_WORLD : ENTITYNUM_NONE; + // check all other solid models + CG_ClipMoveToEntities( start, mins, maxs, end, skipNumber, mask, &t, TT_BISPHERE ); *result = t; } diff --git a/src/cgame/cg_public.h b/src/cgame/cg_public.h index aa0298a2..958e96a6 100644 --- a/src/cgame/cg_public.h +++ b/src/cgame/cg_public.h @@ -167,6 +167,8 @@ typedef enum CG_FS_SEEK, CG_FS_GETFILELIST, CG_LITERAL_ARGS, + CG_CM_BISPHERETRACE, + CG_CM_TRANSFORMEDBISPHERETRACE, CG_MEMSET = 100, CG_MEMCPY, diff --git a/src/cgame/cg_syscalls.asm b/src/cgame/cg_syscalls.asm index ffa14c64..ee2ad7ab 100644 --- a/src/cgame/cg_syscalls.asm +++ b/src/cgame/cg_syscalls.asm @@ -92,6 +92,8 @@ equ trap_R_inPVS -89 equ trap_FS_Seek -90 equ trap_FS_GetFileList -91 equ trap_LiteralArgs -92 +equ trap_CM_BiSphereTrace -93 +equ trap_CM_TransformedBiSphereTrace -94 equ memset -101 equ memcpy -102 diff --git a/src/cgame/cg_syscalls.c b/src/cgame/cg_syscalls.c index 65a5e9c4..a5c42229 100644 --- a/src/cgame/cg_syscalls.c +++ b/src/cgame/cg_syscalls.c @@ -219,6 +219,23 @@ void trap_CM_TransformedCapsuleTrace( trace_t *results, const vec3_t start, con syscall( CG_CM_TRANSFORMEDCAPSULETRACE, results, start, end, mins, maxs, model, brushmask, origin, angles ); } +void trap_CM_BiSphereTrace( trace_t *results, const vec3_t start, + const vec3_t end, float startRad, float endRad, + clipHandle_t model, int mask ) +{ + syscall( CG_CM_BISPHERETRACE, results, start, end, + PASSFLOAT( startRad ), PASSFLOAT( endRad ), model, mask ); +} + +void trap_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 ) +{ + syscall( CG_CM_TRANSFORMEDBISPHERETRACE, results, start, end, PASSFLOAT( startRad ), + PASSFLOAT( endRad ), model, mask, origin ); +} + int trap_CM_MarkFragments( int numPoints, const vec3_t *points, const vec3_t projection, int maxPoints, vec3_t pointBuffer, diff --git a/src/client/cl_cgame.c b/src/client/cl_cgame.c index 38293518..db18a8f7 100644 --- a/src/client/cl_cgame.c +++ b/src/client/cl_cgame.c @@ -498,16 +498,25 @@ long CL_CgameSystemCalls( long *args ) { case CG_CM_TRANSFORMEDPOINTCONTENTS: return CM_TransformedPointContents( VMA(1), args[2], VMA(3), VMA(4) ); case CG_CM_BOXTRACE: - CM_BoxTrace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], /*int capsule*/ qfalse ); + CM_BoxTrace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], TT_AABB ); return 0; case CG_CM_CAPSULETRACE: - CM_BoxTrace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], /*int capsule*/ qtrue ); + CM_BoxTrace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], TT_CAPSULE ); return 0; case CG_CM_TRANSFORMEDBOXTRACE: - CM_TransformedBoxTrace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], VMA(8), VMA(9), /*int capsule*/ qfalse ); + CM_TransformedBoxTrace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), + args[6], args[7], VMA(8), VMA(9), TT_AABB ); return 0; case CG_CM_TRANSFORMEDCAPSULETRACE: - CM_TransformedBoxTrace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], VMA(8), VMA(9), /*int capsule*/ qtrue ); + CM_TransformedBoxTrace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), + args[6], args[7], VMA(8), VMA(9), TT_CAPSULE ); + return 0; + case CG_CM_BISPHERETRACE: + CM_BiSphereTrace( VMA(1), VMA(2), VMA(3), VMF(4), VMF(5), args[6], args[7] ); + return 0; + case CG_CM_TRANSFORMEDBISPHERETRACE: + CM_TransformedBiSphereTrace( VMA(1), VMA(2), VMA(3), VMF(4), VMF(5), + args[6], args[7], VMA(8) ); return 0; case CG_CM_MARKFRAGMENTS: return re.MarkFragments( args[1], VMA(2), VMA(3), args[4], VMA(5), args[6], VMA(7) ); 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) diff --git a/src/server/server.h b/src/server/server.h index da5e0947..3a0924a5 100644 --- a/src/server/server.h +++ b/src/server/server.h @@ -384,7 +384,7 @@ int SV_PointContents( const vec3_t p, int passEntityNum ); // returns the CONTENTS_* value from the world and all entities at the given point. -void SV_Trace( trace_t *results, const vec3_t start, vec3_t mins, vec3_t maxs, const vec3_t end, int passEntityNum, int contentmask, int capsule ); +void SV_Trace( trace_t *results, const vec3_t start, vec3_t mins, vec3_t maxs, const vec3_t end, int passEntityNum, int contentmask, traceType_t type ); // mins and maxs are relative // if the entire move stays in a solid volume, trace.allsolid will be set, @@ -396,7 +396,7 @@ void SV_Trace( trace_t *results, const vec3_t start, vec3_t mins, vec3_t maxs, c // passEntityNum is explicitly excluded from clipping checks (normally ENTITYNUM_NONE) -void SV_ClipToEntity( trace_t *trace, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int entityNum, int contentmask, int capsule ); +void SV_ClipToEntity( trace_t *trace, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int entityNum, int contentmask, traceType_t type ); // clip to a specific entity // diff --git a/src/server/sv_game.c b/src/server/sv_game.c index 2d07fab7..b89ea920 100644 --- a/src/server/sv_game.c +++ b/src/server/sv_game.c @@ -226,7 +226,7 @@ void SV_AdjustAreaPortalState( sharedEntity_t *ent, qboolean open ) { SV_GameAreaEntities ================== */ -qboolean SV_EntityContact( vec3_t mins, vec3_t maxs, const sharedEntity_t *gEnt, int capsule ) { +qboolean SV_EntityContact( vec3_t mins, vec3_t maxs, const sharedEntity_t *gEnt, traceType_t type ) { const float *origin, *angles; clipHandle_t ch; trace_t trace; @@ -237,7 +237,7 @@ qboolean SV_EntityContact( vec3_t mins, vec3_t maxs, const sharedEntity_t *gEnt, ch = SV_ClipHandleForEntity( gEnt ); CM_TransformedBoxTrace ( &trace, vec3_origin, vec3_origin, mins, maxs, - ch, -1, origin, angles, capsule ); + ch, -1, origin, angles, type ); return trace.startsolid; } @@ -373,14 +373,14 @@ long SV_GameSystemCalls( long *args ) { case G_ENTITIES_IN_BOX: return SV_AreaEntities( VMA(1), VMA(2), VMA(3), args[4] ); case G_ENTITY_CONTACT: - return SV_EntityContact( VMA(1), VMA(2), VMA(3), /*int capsule*/ qfalse ); + return SV_EntityContact( VMA(1), VMA(2), VMA(3), TT_AABB ); case G_ENTITY_CONTACTCAPSULE: - return SV_EntityContact( VMA(1), VMA(2), VMA(3), /*int capsule*/ qtrue ); + return SV_EntityContact( VMA(1), VMA(2), VMA(3), TT_CAPSULE ); case G_TRACE: - SV_Trace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], /*int capsule*/ qfalse ); + SV_Trace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], TT_AABB ); return 0; case G_TRACECAPSULE: - SV_Trace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], /*int capsule*/ qtrue ); + SV_Trace( VMA(1), VMA(2), VMA(3), VMA(4), VMA(5), args[6], args[7], TT_CAPSULE ); return 0; case G_POINT_CONTENTS: return SV_PointContents( VMA(1), args[2] ); diff --git a/src/server/sv_world.c b/src/server/sv_world.c index 2060985d..d40cc217 100644 --- a/src/server/sv_world.c +++ b/src/server/sv_world.c @@ -456,7 +456,7 @@ typedef struct { trace_t trace; int passEntityNum; int contentmask; - int capsule; + traceType_t collisionType; } moveclip_t; @@ -466,7 +466,7 @@ SV_ClipToEntity ==================== */ -void SV_ClipToEntity( trace_t *trace, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int entityNum, int contentmask, int capsule ) { +void SV_ClipToEntity( trace_t *trace, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int entityNum, int contentmask, traceType_t type ) { sharedEntity_t *touch; clipHandle_t clipHandle; float *origin, *angles; @@ -494,7 +494,7 @@ void SV_ClipToEntity( trace_t *trace, const vec3_t start, const vec3_t mins, con CM_TransformedBoxTrace ( trace, (float *)start, (float *)end, (float *)mins, (float *)maxs, clipHandle, contentmask, - origin, angles, capsule); + origin, angles, type); if ( trace->fraction < 1 ) { trace->entityNum = touch->s.number; @@ -566,7 +566,7 @@ void SV_ClipMoveToEntities( moveclip_t *clip ) { CM_TransformedBoxTrace ( &trace, (float *)clip->start, (float *)clip->end, (float *)clip->mins, (float *)clip->maxs, clipHandle, clip->contentmask, - origin, angles, clip->capsule); + origin, angles, clip->collisionType); if ( trace.allsolid ) { clip->trace.allsolid = qtrue; @@ -598,7 +598,7 @@ Moves the given mins/maxs volume through the world from start to end. passEntityNum and entities owned by passEntityNum are explicitly not checked. ================== */ -void SV_Trace( trace_t *results, const vec3_t start, vec3_t mins, vec3_t maxs, const vec3_t end, int passEntityNum, int contentmask, int capsule ) { +void SV_Trace( trace_t *results, const vec3_t start, vec3_t mins, vec3_t maxs, const vec3_t end, int passEntityNum, int contentmask, traceType_t type ) { moveclip_t clip; int i; @@ -612,7 +612,7 @@ void SV_Trace( trace_t *results, const vec3_t start, vec3_t mins, vec3_t maxs, c Com_Memset ( &clip, 0, sizeof ( moveclip_t ) ); // clip to world - CM_BoxTrace( &clip.trace, start, end, mins, maxs, 0, contentmask, capsule ); + CM_BoxTrace( &clip.trace, start, end, mins, maxs, 0, contentmask, type ); clip.trace.entityNum = clip.trace.fraction != 1.0 ? ENTITYNUM_WORLD : ENTITYNUM_NONE; if ( clip.trace.fraction == 0 ) { *results = clip.trace; @@ -626,7 +626,7 @@ void SV_Trace( trace_t *results, const vec3_t start, vec3_t mins, vec3_t maxs, c clip.mins = mins; clip.maxs = maxs; clip.passEntityNum = passEntityNum; - clip.capsule = capsule; + clip.collisionType = type; // create the bounding box of the entire move // we can limit it to the part of the move not |