From 1019743b2072b60aa1a2897b04c7cbb8f94454d1 Mon Sep 17 00:00:00 2001 From: lordhavoc Date: Tue, 21 May 2002 10:47:23 +0000 Subject: [PATCH] split out RecursiveHullCheck and related code into collision.c (shared by client and server, doesn't care what an entity is), and cl_collision.c (CL_TraceLine and related code), this cleans up a lot of messy RecursiveHullCheck calls, replacing them with Collision_ClipTrace calls also removed some commented out code and fixed an epsilon glitch in RecursiveHullCheck which was mostly visible when shooting a gun along a wall at angles nearly parallel with the wall git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@1861 d7cf8633-e32d-0410-b094-e92efae38249 --- cgamevm.c | 3 +- chase.c | 131 +------------- cl_collision.c | 127 ++++++++++++++ cl_collision.h | 14 ++ cl_main.c | 5 +- cl_particles.c | 9 +- client.h | 7 - collision.c | 405 ++++++++++++++++++++++++++++++++++++++++++++ collision.h | 42 +++++ makefile | 2 +- makefile.mingw | 2 +- r_explosion.c | 3 +- r_light.c | 7 +- sv_main.c | 67 ++------ world.c | 452 +++---------------------------------------------- world.h | 51 +----- 16 files changed, 650 insertions(+), 677 deletions(-) create mode 100644 cl_collision.c create mode 100644 cl_collision.h create mode 100644 collision.c create mode 100644 collision.h diff --git a/cgamevm.c b/cgamevm.c index 249185e2..57f53dc8 100644 --- a/cgamevm.c +++ b/cgamevm.c @@ -1,6 +1,7 @@ #include "quakedef.h" #include "cgame_api.h" +#include "cl_collision.h" #define CGVM_RENDERENTITIES 1024 @@ -202,7 +203,7 @@ float CGVM_TracePhysics(const float *start, const float *end, const float *world middle[2] = (worldmins[2] + worldmaxs[2]) * 0.5f; VectorAdd(start, middle, start2); VectorAdd(end, middle, end2); - frac = TraceLine((float *)start2, (float *)end2, impactpos, impactnormal, 0, true); + frac = CL_TraceLine((float *)start2, (float *)end2, impactpos, impactnormal, 0, true); VectorSubtract(impactpos, middle, impactpos); //VectorCopy(end, impactpos); //VectorClear(impactnormal); diff --git a/chase.c b/chase.c index 1a9da003..fa0f0a03 100644 --- a/chase.c +++ b/chase.c @@ -20,6 +20,7 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. // chase.c -- chase camera code #include "quakedef.h" +#include "cl_collision.h" cvar_t chase_back = {CVAR_SAVE, "chase_back", "48"}; cvar_t chase_up = {CVAR_SAVE, "chase_up", "24"}; @@ -38,134 +39,6 @@ void Chase_Reset (void) // start position 12 units behind head } -int traceline_endcontents; - -static entity_render_t *traceline_entity[MAX_EDICTS]; -static int traceline_entities; - -// builds list of entities for TraceLine to check later -void TraceLine_ScanForBModels(void) -{ - int i; - entity_render_t *ent; - model_t *model; - traceline_entities = 0; - for (i = 1;i < MAX_EDICTS;i++) - { - ent = &cl_entities[i].render; - model = ent->model; - // look for embedded brush models only - if (model && model->name[0] == '*') - { - // this does nothing for * models currently... - //Mod_CheckLoaded(model); - if (model->type == mod_brush) - { - traceline_entity[traceline_entities++] = ent; - if (ent->angles[0] || ent->angles[2]) - { - // pitch or roll - VectorAdd(ent->origin, model->rotatedmins, ent->mins); - VectorAdd(ent->origin, model->rotatedmaxs, ent->maxs); - } - else if (ent->angles[1]) - { - // yaw - VectorAdd(ent->origin, model->yawmins, ent->mins); - VectorAdd(ent->origin, model->yawmaxs, ent->maxs); - } - else - { - VectorAdd(ent->origin, model->normalmins, ent->mins); - VectorAdd(ent->origin, model->normalmaxs, ent->maxs); - } - } - } - } -} - -float TraceLine (vec3_t start, vec3_t end, vec3_t impact, vec3_t normal, int contents, int hitbmodels) -{ - double maxfrac, startd[3], endd[3]; - trace_t trace; - -// FIXME: broken, fix it -// if (impact == NULL && normal == NULL && contents == 0) -// return SV_TestLine (cl.worldmodel->hulls, 0, start, end); - - VectorCopy(start, startd); - VectorCopy(end, endd); - - Mod_CheckLoaded(cl.worldmodel); - memset (&trace, 0, sizeof(trace)); - VectorCopy (endd, trace.endpos); - trace.fraction = 1; - trace.startcontents = contents; - VectorCopy(startd, RecursiveHullCheckInfo.start); - VectorSubtract(endd, startd, RecursiveHullCheckInfo.dist); - RecursiveHullCheckInfo.hull = cl.worldmodel->hulls; - RecursiveHullCheckInfo.trace = &trace; - SV_RecursiveHullCheck (0, 0, 1, startd, endd); - if (impact) - VectorCopy (trace.endpos, impact); - if (normal) - VectorCopy (trace.plane.normal, normal); - traceline_endcontents = trace.endcontents; - maxfrac = trace.fraction; - - if (hitbmodels && traceline_entities) - { - int n; - entity_render_t *ent; - double start2[3], end2[3], tracemins[3], tracemaxs[3]; - tracemins[0] = min(start[0], end[0]); - tracemaxs[0] = max(start[0], end[0]); - tracemins[1] = min(start[1], end[1]); - tracemaxs[1] = max(start[1], end[1]); - tracemins[2] = min(start[2], end[2]); - tracemaxs[2] = max(start[2], end[2]); - - // look for embedded bmodels - for (n = 0;n < traceline_entities;n++) - { - ent = traceline_entity[n]; - if (ent->mins[0] > tracemaxs[0] || ent->maxs[0] < tracemins[0] - || ent->mins[1] > tracemaxs[1] || ent->maxs[1] < tracemins[1] - || ent->mins[2] > tracemaxs[2] || ent->maxs[2] < tracemins[2]) - continue; - - softwaretransformforentity(ent); - softwareuntransform(start, start2); - softwareuntransform(end, end2); - - memset (&trace, 0, sizeof(trace)); - VectorCopy (end2, trace.endpos); - trace.fraction = 1; - trace.startcontents = contents; - VectorCopy(start2, RecursiveHullCheckInfo.start); - VectorSubtract(end2, start2, RecursiveHullCheckInfo.dist); - RecursiveHullCheckInfo.hull = ent->model->hulls; - RecursiveHullCheckInfo.trace = &trace; - SV_RecursiveHullCheck (ent->model->hulls->firstclipnode, 0, 1, start2, end2); - - if (trace.allsolid || trace.startsolid || trace.fraction < maxfrac) - { - maxfrac = trace.fraction; - if (impact) - { - softwaretransform(trace.endpos, impact); - } - if (normal) - { - softwaretransformdirection(trace.plane.normal, normal); - } - traceline_endcontents = trace.endcontents; - } - } - } - return maxfrac; -} - void Chase_Update (void) { vec3_t forward, stop, chase_dest, normal; @@ -181,7 +54,7 @@ void Chase_Update (void) chase_dest[1] = r_refdef.vieworg[1] + forward[1] * dist; chase_dest[2] = r_refdef.vieworg[2] + forward[2] * dist + chase_up.value; - TraceLine (r_refdef.vieworg, chase_dest, stop, normal, 0, true); + CL_TraceLine (r_refdef.vieworg, chase_dest, stop, normal, 0, true); chase_dest[0] = stop[0] + forward[0] * 8 + normal[0] * 4; chase_dest[1] = stop[1] + forward[1] * 8 + normal[1] * 4; chase_dest[2] = stop[2] + forward[2] * 8 + normal[2] * 4; diff --git a/cl_collision.c b/cl_collision.c new file mode 100644 index 00000000..22d846af --- /dev/null +++ b/cl_collision.c @@ -0,0 +1,127 @@ + +#include "quakedef.h" + +/* +// not yet used +typedef struct physentity_s +{ + // this may be a entity_t, or a edict_t, or whatever + void *realentity; + + // can be NULL if it is a bbox object + model_t *bmodel; + + // node this entity crosses + // for avoiding unnecessary collisions + physnode_t *node; + + // matrix for converting from model to world coordinates + double modeltoworldmatrix[3][4]; + + // matrix for converting from world to model coordinates + double worldtomodelmatrix[3][4]; + + // if this is a bmodel, this is used for culling it quickly + // if this is not a bmodel, this is used for actual collisions + double mins[3], maxs[3]; +} +physentity_t; +*/ + +static entity_render_t *traceline_entity[MAX_EDICTS]; +static int traceline_entities; + +// builds list of entities for TraceLine to check later +void CL_TraceLine_ScanForBModels(void) +{ + int i; + entity_render_t *ent; + model_t *model; + traceline_entities = 0; + for (i = 1;i < MAX_EDICTS;i++) + { + ent = &cl_entities[i].render; + model = ent->model; + // look for embedded brush models only + if (model && model->name[0] == '*') + { + // this does nothing for * models currently... + //Mod_CheckLoaded(model); + if (model->type == mod_brush) + { + traceline_entity[traceline_entities++] = ent; + if (ent->angles[0] || ent->angles[2]) + { + // pitch or roll + VectorAdd(ent->origin, model->rotatedmins, ent->mins); + VectorAdd(ent->origin, model->rotatedmaxs, ent->maxs); + } + else if (ent->angles[1]) + { + // yaw + VectorAdd(ent->origin, model->yawmins, ent->mins); + VectorAdd(ent->origin, model->yawmaxs, ent->maxs); + } + else + { + VectorAdd(ent->origin, model->normalmins, ent->mins); + VectorAdd(ent->origin, model->normalmaxs, ent->maxs); + } + } + } + } +} + +int cl_traceline_endcontents; + +float CL_TraceLine (vec3_t start, vec3_t end, vec3_t impact, vec3_t normal, int contents, int hitbmodels) +{ + double maxfrac; + trace_t trace; + + Mod_CheckLoaded(cl.worldmodel); + Collision_ClipTrace(&trace, NULL, cl.worldmodel, vec3_origin, vec3_origin, vec3_origin, vec3_origin, start, vec3_origin, vec3_origin, end); + + if (impact) + VectorCopy (trace.endpos, impact); + if (normal) + VectorCopy (trace.plane.normal, normal); + cl_traceline_endcontents = trace.endcontents; + maxfrac = trace.fraction; + + if (hitbmodels && traceline_entities) + { + int n; + entity_render_t *ent; + double /*start2[3], end2[3], */tracemins[3], tracemaxs[3]; + tracemins[0] = min(start[0], end[0]); + tracemaxs[0] = max(start[0], end[0]); + tracemins[1] = min(start[1], end[1]); + tracemaxs[1] = max(start[1], end[1]); + tracemins[2] = min(start[2], end[2]); + tracemaxs[2] = max(start[2], end[2]); + + // look for embedded bmodels + for (n = 0;n < traceline_entities;n++) + { + ent = traceline_entity[n]; + if (ent->mins[0] > tracemaxs[0] || ent->maxs[0] < tracemins[0] + || ent->mins[1] > tracemaxs[1] || ent->maxs[1] < tracemins[1] + || ent->mins[2] > tracemaxs[2] || ent->maxs[2] < tracemins[2]) + continue; + + Collision_ClipTrace(&trace, ent, ent->model, ent->origin, ent->angles, ent->mins, ent->maxs, start, vec3_origin, vec3_origin, end); + + if (trace.allsolid || trace.startsolid || trace.fraction < maxfrac) + { + maxfrac = trace.fraction; + if (impact) + VectorCopy(trace.endpos, impact); + if (normal) + VectorCopy(trace.plane.normal, normal); + cl_traceline_endcontents = trace.endcontents; + } + } + } + return maxfrac; +} diff --git a/cl_collision.h b/cl_collision.h new file mode 100644 index 00000000..ec4a89f0 --- /dev/null +++ b/cl_collision.h @@ -0,0 +1,14 @@ + +#ifndef CL_COLLISION_H +#define CL_COLLISION_H + +// if contents is not zero, it will impact on content changes +// (leafs matching contents are considered empty, others are solid) +extern int cl_traceline_endcontents; // set by TraceLine + +// need to call this sometime before using TraceLine with hitbmodels +void CL_TraceLine_ScanForBModels(void); + +float CL_TraceLine (vec3_t start, vec3_t end, vec3_t impact, vec3_t normal, int contents, int hitbmodels); + +#endif diff --git a/cl_main.c b/cl_main.c index b387596d..73139f74 100644 --- a/cl_main.c +++ b/cl_main.c @@ -20,6 +20,7 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. // cl_main.c -- client main loop #include "quakedef.h" +#include "cl_collision.h" // we need to declare some mouse variables here, because the menu system // references them even when on a unix system. @@ -589,7 +590,7 @@ static void CL_RelinkNetworkEntities() v2[0] = v[0] * 18 + neworg[0]; v2[1] = v[1] * 18 + neworg[1]; v2[2] = v[2] * 18 + neworg[2] + 16; - TraceLine(neworg, v2, v, NULL, 0, true); + CL_TraceLine(neworg, v2, v, NULL, 0, true); CL_AllocDlight (NULL, v, ent->persistent.muzzleflash, 1, 1, 1, 0, 0); ent->persistent.muzzleflash -= cl.frametime * 1000; @@ -796,7 +797,7 @@ void CL_RelinkEntities (void) CL_DecayLights (); CL_RelinkStaticEntities(); CL_RelinkNetworkEntities(); - TraceLine_ScanForBModels(); + CL_TraceLine_ScanForBModels(); CL_RelinkEffects(); CL_MoveParticles(); CL_UpdateTEnts(); diff --git a/cl_particles.c b/cl_particles.c index 4bc57357..aba0f15c 100644 --- a/cl_particles.c +++ b/cl_particles.c @@ -19,6 +19,7 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include "quakedef.h" +#include "cl_collision.h" #define MAX_PARTICLES 16384 // default max # of particles at one time #define ABSOLUTE_MIN_PARTICLES 512 // no fewer than this no matter what's on the command line @@ -385,7 +386,7 @@ void CL_ParticleExplosion (vec3_t org, int smoke) { VectorRandom(v); VectorMA(org, 16, v, v); - TraceLine(org, v, end, NULL, 0, true); + CL_TraceLine(org, v, end, NULL, 0, true); ang[0] = (j + 0.5f) * (360.0f / 32.0f); ang[1] = (i + 0.5f) * (360.0f / 32.0f); AngleVectors(ang, v, NULL, NULL); @@ -410,7 +411,7 @@ void CL_ParticleExplosion (vec3_t org, int smoke) { VectorRandom(v); VectorMA(org, 16, v, v); - TraceLine(org, v, end, NULL, 0, true); + CL_TraceLine(org, v, end, NULL, 0, true); ang[0] = (j + 0.5f) * (360.0f / 32.0f); ang[1] = (i + 0.5f) * (360.0f / 32.0f); AngleVectors(ang, v, NULL, NULL); @@ -974,7 +975,7 @@ void CL_MoveParticles (void) VectorCopy(p->org, org); if (p->bounce) { - if (TraceLine(p->oldorg, p->org, v, normal, 0, true) < 1) + if (CL_TraceLine(p->oldorg, p->org, v, normal, 0, true) < 1) { VectorCopy(v, p->org); if (p->bounce < 0) @@ -1211,7 +1212,7 @@ void CL_MoveParticles (void) { a = b; f = TraceLine(o, p->org, v, normal, a, true); - b = traceline_endcontents; + b = cl_traceline_endcontents; if (f < 1 && b != CONTENTS_EMPTY && b != CONTENTS_SKY) { #if 1 diff --git a/client.h b/client.h index a2fccefb..4b7eab45 100644 --- a/client.h +++ b/client.h @@ -516,13 +516,6 @@ void CL_MoveParticles(void); void R_MoveExplosions(void); void R_NewExplosion(vec3_t org); -// if contents is not zero, it will impact on content changes -// (leafs matching contents are considered empty, others are solid) -extern int traceline_endcontents; // set by TraceLine -// need to call this sometime before using TraceLine with hitbmodels -void TraceLine_ScanForBModels(void); -float TraceLine (vec3_t start, vec3_t end, vec3_t impact, vec3_t normal, int contents, int hitbmodels); - #include "cl_screen.h" #define MAX_VISEDICTS (MAX_EDICTS + MAX_STATIC_ENTITIES + MAX_TEMP_ENTITIES) diff --git a/collision.c b/collision.c new file mode 100644 index 00000000..dfbfedbb --- /dev/null +++ b/collision.c @@ -0,0 +1,405 @@ + +#include "quakedef.h" + +typedef struct +{ + // the hull we're tracing through + const hull_t *hull; + + // the trace structure to fill in + trace_t *trace; + + // start and end of the trace (in model space) + double start[3]; + double end[3]; + + // end - start (for quick fraction -> vector conversions) + double dist[3]; +} +RecursiveHullCheckTraceInfo_t; + +// 1/32 epsilon to keep floating point happy +#define DIST_EPSILON (0.03125) + +#define HULLCHECKSTATE_EMPTY 0 +#define HULLCHECKSTATE_SOLID 1 +#define HULLCHECKSTATE_DONE 2 + +static void RecursiveHullCheck_Impact (RecursiveHullCheckTraceInfo_t *t, const mplane_t *plane, const int side) +{ + // LordHavoc: using doubles for extra accuracy + double t1, t2, frac, pdist; + + // LordHavoc: now that we have found the impact, recalculate the impact + // point from scratch for maximum accuracy, with an epsilon bias on the + // surface distance + pdist = plane->dist; + if (side) + { + pdist -= DIST_EPSILON; + VectorNegate (plane->normal, t->trace->plane.normal); + t->trace->plane.dist = -plane->dist; + } + else + { + pdist += DIST_EPSILON; + VectorCopy (plane->normal, t->trace->plane.normal); + t->trace->plane.dist = plane->dist; + } + + if (plane->type < 3) + { + t1 = t->start[plane->type] - pdist; + t2 = t->start[plane->type] + t->dist[plane->type] - pdist; + } + else + { + t1 = plane->normal[0] * t->start[0] + plane->normal[1] * t->start[1] + plane->normal[2] * t->start[2] - pdist; + t2 = plane->normal[0] * (t->start[0] + t->dist[0]) + plane->normal[1] * (t->start[1] + t->dist[1]) + plane->normal[2] * (t->start[2] + t->dist[2]) - pdist; + } + + frac = t1 / (t1 - t2); + frac = bound(0.0f, frac, 1.0); + + t->trace->fraction = frac; + VectorMA(t->start, frac, t->dist, t->trace->endpos); +} + +static int RecursiveHullCheck (RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, const double p1[3], const double p2[3]) +{ + // status variables, these don't need to be saved on the stack when + // recursing... but are because this should be thread-safe + // (note: tracing against a bbox is not thread-safe, yet) + int ret; + mplane_t *plane; + double t1, t2, frac; + + // variables that need to be stored on the stack when recursing + dclipnode_t *node; + int side; + double midf, mid[3]; + + // LordHavoc: a goto! everyone flee in terror... :) +loc0: + // check for empty + if (num < 0) + { + t->trace->endcontents = num; + if (t->trace->startcontents) + { + if (num == t->trace->startcontents) + t->trace->allsolid = false; + else + { + // if the first leaf is solid, set startsolid + if (t->trace->allsolid) + t->trace->startsolid = true; + return HULLCHECKSTATE_SOLID; + } + return HULLCHECKSTATE_EMPTY; + } + else + { + if (num != CONTENTS_SOLID) + { + t->trace->allsolid = false; + if (num == CONTENTS_EMPTY) + t->trace->inopen = true; + else + t->trace->inwater = true; + } + else + { + // if the first leaf is solid, set startsolid + if (t->trace->allsolid) + t->trace->startsolid = true; + return HULLCHECKSTATE_SOLID; + } + return HULLCHECKSTATE_EMPTY; + } + } + + // find the point distances + node = t->hull->clipnodes + num; + + plane = t->hull->planes + node->planenum; + if (plane->type < 3) + { + t1 = p1[plane->type] - plane->dist; + t2 = p2[plane->type] - plane->dist; + } + else + { + t1 = DotProduct (plane->normal, p1) - plane->dist; + t2 = DotProduct (plane->normal, p2) - plane->dist; + } + + side = t1 < 0; + + if (side) + { + if (t1 < -DIST_EPSILON && t2 < -DIST_EPSILON) + { + num = node->children[1]; + goto loc0; + } + } + else + { + if (t1 > DIST_EPSILON && t2 > DIST_EPSILON) + { + num = node->children[0]; + goto loc0; + } + } + + // the line (almost) intersects, recurse both sides + + frac = t1 / (t1 - t2); + frac = bound(0.0f, frac, 1.0); + + midf = p1f + ((p2f - p1f) * frac); + VectorMA(t->start, midf, t->dist, mid); + + // front side first + ret = RecursiveHullCheck (t, node->children[side], p1f, midf, p1, mid); + if (ret != HULLCHECKSTATE_EMPTY) + return ret; // solid or done + ret = RecursiveHullCheck (t, node->children[!side], midf, p2f, mid, p2); + if (ret != HULLCHECKSTATE_SOLID) + return ret; // empty or done + + // front is air and back is solid, this is the impact point... + RecursiveHullCheck_Impact(t, t->hull->planes + node->planenum, side); + + return HULLCHECKSTATE_DONE; +} + +void Collision_RoundUpToHullSize(const model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs) +{ + vec3_t size; + const hull_t *hull; + + VectorSubtract(inmaxs, inmins, size); + if (cmodel->ishlbsp) + { + if (size[0] < 3) + hull = &cmodel->hulls[0]; // 0x0x0 + else if (size[0] <= 32) + { + if (size[2] < 54) // pick the nearest of 36 or 72 + hull = &cmodel->hulls[3]; // 32x32x36 + else + hull = &cmodel->hulls[1]; // 32x32x72 + } + else + hull = &cmodel->hulls[2]; // 64x64x64 + } + else + { + if (size[0] < 3) + hull = &cmodel->hulls[0]; // 0x0x0 + else if (size[0] <= 32) + hull = &cmodel->hulls[1]; // 32x32x56 + else + hull = &cmodel->hulls[2]; // 64x64x88 + } + VectorCopy(inmins, outmins); + VectorAdd(inmins, hull->clip_size, outmaxs); +} + +static hull_t box_hull; +static dclipnode_t box_clipnodes[6]; +static mplane_t box_planes[6]; + +void Collision_Init (void) +{ + int i; + int side; + + //Set up the planes and clipnodes so that the six floats of a bounding box + //can just be stored out and get a proper hull_t structure. + + box_hull.clipnodes = box_clipnodes; + box_hull.planes = box_planes; + box_hull.firstclipnode = 0; + box_hull.lastclipnode = 5; + + for (i = 0;i < 6;i++) + { + box_clipnodes[i].planenum = i; + + side = i&1; + + box_clipnodes[i].children[side] = CONTENTS_EMPTY; + if (i != 5) + box_clipnodes[i].children[side^1] = i + 1; + else + box_clipnodes[i].children[side^1] = CONTENTS_SOLID; + + box_planes[i].type = i>>1; + box_planes[i].normal[i>>1] = 1; + } +} + + +static hull_t *HullForBBoxEntity (const vec3_t corigin, const vec3_t cmins, const vec3_t cmaxs, const vec3_t mins, const vec3_t maxs, vec3_t offset) +{ + vec3_t hullmins, hullmaxs; + + // create a temp hull from bounding box sizes + VectorCopy (corigin, offset); + VectorSubtract (cmins, maxs, hullmins); + VectorSubtract (cmaxs, mins, hullmaxs); + + //To keep everything totally uniform, bounding boxes are turned into small + //BSP trees instead of being compared directly. + box_planes[0].dist = hullmaxs[0]; + box_planes[1].dist = hullmins[0]; + box_planes[2].dist = hullmaxs[1]; + box_planes[3].dist = hullmins[1]; + box_planes[4].dist = hullmaxs[2]; + box_planes[5].dist = hullmins[2]; + return &box_hull; +} + +static const hull_t *HullForBrushModel (const model_t *cmodel, const vec3_t corigin, const vec3_t mins, const vec3_t maxs, vec3_t offset) +{ + vec3_t size; + const hull_t *hull; + + // decide which clipping hull to use, based on the size + // explicit hulls in the BSP model + VectorSubtract (maxs, mins, size); + // LordHavoc: FIXME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! + if (cmodel->ishlbsp) + { + if (size[0] < 3) + hull = &cmodel->hulls[0]; // 0x0x0 + else if (size[0] <= 32) + { + if (size[2] < 54) // pick the nearest of 36 or 72 + hull = &cmodel->hulls[3]; // 32x32x36 + else + hull = &cmodel->hulls[1]; // 32x32x72 + } + else + hull = &cmodel->hulls[2]; // 64x64x64 + } + else + { + if (size[0] < 3) + hull = &cmodel->hulls[0]; // 0x0x0 + else if (size[0] <= 32) + hull = &cmodel->hulls[1]; // 32x32x56 + else + hull = &cmodel->hulls[2]; // 64x64x88 + } + + // calculate an offset value to center the origin + VectorSubtract (hull->clip_mins, mins, offset); + VectorAdd (offset, corigin, offset); + + return hull; +} + +void Collision_ClipTrace (trace_t *trace, const void *cent, const model_t *cmodel, const vec3_t corigin, const vec3_t cangles, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end) +{ + RecursiveHullCheckTraceInfo_t rhc; + vec3_t offset, forward, left, up; + double startd[3], endd[3], tempd[3]; + + // fill in a default trace + memset (&rhc, 0, sizeof(rhc)); + memset (trace, 0, sizeof(trace_t)); + + rhc.trace = trace; + + rhc.trace->fraction = 1; + rhc.trace->allsolid = true; + + if (cmodel && cmodel->type == mod_brush) + { + // brush model + + // get the clipping hull + rhc.hull = HullForBrushModel (cmodel, corigin, mins, maxs, offset); + + VectorSubtract(start, offset, startd); + VectorSubtract(end, offset, endd); + + // rotate start and end into the model's frame of reference + if (cangles[0] || cangles[1] || cangles[2]) + { + AngleVectorsFLU (cangles, forward, left, up); + VectorCopy(startd, tempd); + startd[0] = DotProduct (tempd, forward); + startd[1] = DotProduct (tempd, left); + startd[2] = DotProduct (tempd, up); + VectorCopy(endd, tempd); + endd[0] = DotProduct (tempd, forward); + endd[1] = DotProduct (tempd, left); + endd[2] = DotProduct (tempd, up); + } + + VectorCopy(end, rhc.trace->endpos); + + // trace a line through the appropriate clipping hull + VectorCopy(startd, rhc.start); + VectorCopy(endd, rhc.end); + + VectorSubtract(rhc.end, rhc.start, rhc.dist); + RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, startd, endd); + + // if we hit, unrotate endpos and normal, and store the entity we hit + if (rhc.trace->fraction != 1) + { + // rotate endpos back to world frame of reference + if (cangles[0] || cangles[1] || cangles[2]) + { + VectorNegate (cangles, offset); + AngleVectorsFLU (offset, forward, left, up); + + VectorCopy (rhc.trace->endpos, tempd); + rhc.trace->endpos[0] = DotProduct (tempd, forward); + rhc.trace->endpos[1] = DotProduct (tempd, left); + rhc.trace->endpos[2] = DotProduct (tempd, up); + + VectorCopy (rhc.trace->plane.normal, tempd); + rhc.trace->plane.normal[0] = DotProduct (tempd, forward); + rhc.trace->plane.normal[1] = DotProduct (tempd, left); + rhc.trace->plane.normal[2] = DotProduct (tempd, up); + } + // fix offset + VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos); + rhc.trace->ent = (void *) cent; + } + else if (rhc.trace->allsolid || rhc.trace->startsolid) + rhc.trace->ent = (void *) cent; + } + else + { + // bounding box + + rhc.hull = HullForBBoxEntity (corigin, cmins, cmaxs, mins, maxs, offset); + + VectorSubtract(start, offset, startd); + VectorSubtract(end, offset, endd); + VectorCopy(end, rhc.trace->endpos); + + // trace a line through the generated clipping hull + VectorCopy(startd, rhc.start); + VectorSubtract(endd, startd, rhc.dist); + RecursiveHullCheck (&rhc, rhc.hull->firstclipnode, 0, 1, startd, endd); + + // if we hit, store the entity we hit + if (rhc.trace->fraction != 1) + { + // fix offset + VectorAdd (rhc.trace->endpos, offset, rhc.trace->endpos); + rhc.trace->ent = (void *) cent; + } + else if (rhc.trace->allsolid || rhc.trace->startsolid) + rhc.trace->ent = (void *) cent; + } +} diff --git a/collision.h b/collision.h new file mode 100644 index 00000000..36111951 --- /dev/null +++ b/collision.h @@ -0,0 +1,42 @@ + +#ifndef COLLISION_H +#define COLLISION_H + +typedef struct +{ + vec3_t normal; + float dist; +} plane_t; + +typedef struct +{ + // if true, the entire trace was in solid + qboolean allsolid; + // if true, the initial point was in solid + qboolean startsolid; + // if true, the trace passed through empty somewhere + qboolean inopen; + // if true, the trace passed through water somewhere + qboolean inwater; + // fraction of the total distance that was traveled before impact + // (1.0 = did not hit anything) + double fraction; + // final position + double endpos[3]; + // surface normal at impact + plane_t plane; + // entity the surface is on + void *ent; + // if not zero, treats this value as empty, and all others as solid (impact + // on content change) + int startcontents; + // the contents that was hit at the end or impact point + int endcontents; +} +trace_t; + +void Collision_RoundUpToHullSize(const model_t *cmodel, const vec3_t inmins, const vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs); +void Collision_Init (void); +void Collision_ClipTrace (trace_t *trace, const void *cent, const model_t *cmodel, const vec3_t corigin, const vec3_t cangles, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end); + +#endif diff --git a/makefile b/makefile index addcf781..b834db88 100644 --- a/makefile +++ b/makefile @@ -9,7 +9,7 @@ SOUNDLIB=-lasound #SND=snd_oss.o #SOUNDLIB= -OBJECTS= builddate.o cd_linux.o chase.o cl_demo.o cl_input.o cl_main.o cl_parse.o cl_tent.o cmd.o common.o console.o crc.o cvar.o fractalnoise.o gl_draw.o r_sky.o gl_rmain.o gl_rsurf.o host.o host_cmd.o image.o keys.o mathlib.o menu.o model_alias.o model_brush.o model_shared.o model_sprite.o net_bsd.o net_udp.o net_dgrm.o net_loop.o net_main.o pr_cmds.o pr_edict.o pr_exec.o r_light.o r_explosion.o sbar.o snd_dma.o snd_mem.o snd_mix.o $(SND) sv_main.o sv_move.o sv_phys.o sv_user.o sv_light.o sys_linux.o transform.o view.o wad.o world.o zone.o vid_shared.o palette.o r_crosshairs.o gl_textures.o gl_models.o r_sprites.o r_modules.o r_explosion.o r_lerpanim.o protocol.o quakeio.o r_clip.o ui.o portals.o sys_shared.o cl_light.o gl_backend.o cl_particles.o cl_screen.o cgamevm.o cgame.o filematch.o +OBJECTS= builddate.o cd_linux.o chase.o cl_demo.o cl_input.o cl_main.o cl_parse.o cl_tent.o cmd.o common.o console.o crc.o cvar.o fractalnoise.o gl_draw.o r_sky.o gl_rmain.o gl_rsurf.o host.o host_cmd.o image.o keys.o mathlib.o menu.o model_alias.o model_brush.o model_shared.o model_sprite.o net_bsd.o net_udp.o net_dgrm.o net_loop.o net_main.o pr_cmds.o pr_edict.o pr_exec.o r_light.o r_explosion.o sbar.o snd_dma.o snd_mem.o snd_mix.o $(SND) sv_main.o sv_move.o sv_phys.o sv_user.o sv_light.o sys_linux.o transform.o view.o wad.o world.o zone.o vid_shared.o palette.o r_crosshairs.o gl_textures.o gl_models.o r_sprites.o r_modules.o r_explosion.o r_lerpanim.o protocol.o quakeio.o r_clip.o ui.o portals.o sys_shared.o cl_light.o gl_backend.o cl_particles.o cl_screen.o cgamevm.o cgame.o filematch.o collision.o cl_collision.o #K6/athlon optimizations CPUOPTIMIZATIONS=-march=k6 diff --git a/makefile.mingw b/makefile.mingw index 4f6a5a71..d4349d84 100644 --- a/makefile.mingw +++ b/makefile.mingw @@ -1,5 +1,5 @@ -OBJECTS= builddate.o chase.o cl_demo.o cl_input.o cl_main.o cl_parse.o cl_tent.o cmd.o common.o console.o crc.o cvar.o fractalnoise.o gl_draw.o r_sky.o gl_rmain.o gl_rsurf.o host.o host_cmd.o image.o keys.o mathlib.o menu.o model_alias.o model_brush.o model_shared.o model_sprite.o net_dgrm.o net_loop.o net_main.o pr_cmds.o pr_edict.o pr_exec.o r_light.o r_explosion.o sbar.o snd_dma.o snd_mem.o snd_mix.o sv_main.o sv_move.o sv_phys.o sv_user.o sv_light.o transform.o view.o wad.o world.o zone.o vid_shared.o palette.o r_crosshairs.o gl_textures.o gl_models.o r_sprites.o r_modules.o r_explosion.o r_lerpanim.o protocol.o quakeio.o r_clip.o ui.o portals.o sys_shared.o cl_light.o gl_backend.o cl_particles.o cl_screen.o cgamevm.o cgame.o filematch.o +OBJECTS= builddate.o chase.o cl_demo.o cl_input.o cl_main.o cl_parse.o cl_tent.o cmd.o common.o console.o crc.o cvar.o fractalnoise.o gl_draw.o r_sky.o gl_rmain.o gl_rsurf.o host.o host_cmd.o image.o keys.o mathlib.o menu.o model_alias.o model_brush.o model_shared.o model_sprite.o net_dgrm.o net_loop.o net_main.o pr_cmds.o pr_edict.o pr_exec.o r_light.o r_explosion.o sbar.o snd_dma.o snd_mem.o snd_mix.o sv_main.o sv_move.o sv_phys.o sv_user.o sv_light.o transform.o view.o wad.o world.o zone.o vid_shared.o palette.o r_crosshairs.o gl_textures.o gl_models.o r_sprites.o r_modules.o r_explosion.o r_lerpanim.o protocol.o quakeio.o r_clip.o ui.o portals.o sys_shared.o cl_light.o gl_backend.o cl_particles.o cl_screen.o cgamevm.o cgame.o filematch.o collision.o cl_collision.o #K6/athlon optimizations #CPUOPTIMIZATIONS=-march=k6 diff --git a/r_explosion.c b/r_explosion.c index 56ad69ac..a3991d2c 100644 --- a/r_explosion.c +++ b/r_explosion.c @@ -19,6 +19,7 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #include "quakedef.h" +#include "cl_collision.h" #define MAX_EXPLOSIONS 64 #define EXPLOSIONGRID 8 @@ -366,7 +367,7 @@ void R_MoveExplosion(explosion_t *e/*, explosiongas_t **list, explosiongas_t **l VectorMA(e->vert[i], frametime, e->vertvel[i], end); if (r_explosionclip.integer) { - if (TraceLine(e->vert[i], end, impact, normal, 0, true) < 1) + if (CL_TraceLine(e->vert[i], end, impact, normal, 0, true) < 1) { // clip velocity against the wall dot = DotProduct(e->vertvel[i], normal) * -1.125f; diff --git a/r_light.c b/r_light.c index 6860122a..c8984b7a 100644 --- a/r_light.c +++ b/r_light.c @@ -20,6 +20,7 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. // r_light.c #include "quakedef.h" +#include "cl_collision.h" rdlight_t r_dlight[MAX_DLIGHTS]; int r_numdlights = 0; @@ -170,7 +171,7 @@ void R_DrawCoronas(void) { // trace to a point just barely closer to the eye VectorSubtract(rd->origin, vpn, diff); - if (TraceLine(r_origin, diff, NULL, NULL, 0, true) == 1) + if (CL_TraceLine(r_origin, diff, NULL, NULL, 0, true) == 1) { scale = 1.0f / 262144.0f; //scale = 64.0f / (DotProduct(diff,diff) + 1024.0f); @@ -759,7 +760,7 @@ void R_CompleteLightPoint (vec3_t color, vec3_t p, int dynamic, mleaf_t *leaf) f = (1.0f / f) - sl->subtract; if (f > 0) { - if (TraceLine(p, sl->origin, NULL, NULL, 0, false) == 1) + if (CL_TraceLine(p, sl->origin, NULL, NULL, 0, false) == 1) { f *= d_lightstylevalue[sl->style] * (1.0f / 32768.0f); VectorMA(color, f, sl->light, color); @@ -885,7 +886,7 @@ void R_LightModel(int numverts, float colorr, float colorg, float colorb, int wo // this code is unused for now for (i = 0, sl = cl.worldmodel->lights;i < cl.worldmodel->numlights && nearlights < MAX_DLIGHTS;i++, sl++) { - if (TraceLine(currentrenderentity->origin, sl->origin, NULL, NULL, 0, false) == 1) + if (CL_TraceLine(currentrenderentity->origin, sl->origin, NULL, NULL, 0, false) == 1) { nl->falloff = sl->falloff; // transform the light into the model's coordinate system diff --git a/sv_main.c b/sv_main.c index b1dd7400..00fb0581 100644 --- a/sv_main.c +++ b/sv_main.c @@ -519,28 +519,25 @@ void SV_WriteEntitiesToClient (client_t *client, edict_t *clent, sizebuf_t *msg) int e, clentnum, bits, alpha, glowcolor, glowsize, scale, effects; int culled_pvs, culled_portal, culled_trace, visibleentities, totalentities; qbyte *pvs; - vec3_t org, origin, angles, entmins, entmaxs; + vec3_t origin, angles, entmins, entmaxs, testorigin, testeye; float nextfullupdate; edict_t *ent; eval_t *val; entity_state_t *baseline; // LordHavoc: delta or startup baseline trace_t trace; model_t *model; - double testeye[3]; - double testorigin[3]; Mod_CheckLoaded(sv.worldmodel); // find the client's PVS - VectorAdd (clent->v.origin, clent->v.view_ofs, org); - VectorCopy (org, testeye); - pvs = SV_FatPVS (org); + VectorAdd (clent->v.origin, clent->v.view_ofs, testeye); + pvs = SV_FatPVS (testeye); /* // dp protocol MSG_WriteByte(msg, svc_playerposition); - MSG_WriteFloat(msg, org[0]); - MSG_WriteFloat(msg, org[1]); - MSG_WriteFloat(msg, org[2]); + MSG_WriteFloat(msg, testeye[0]); + MSG_WriteFloat(msg, testeye[1]); + MSG_WriteFloat(msg, testeye[2]); */ culled_pvs = 0; @@ -659,7 +656,7 @@ void SV_WriteEntitiesToClient (client_t *client, edict_t *clent, sizebuf_t *msg) } // or not visible through the portals - if (sv_cullentities_portal.integer && !Portal_CheckBox(sv.worldmodel, org, entmins, entmaxs)) + if (sv_cullentities_portal.integer && !Portal_CheckBox(sv.worldmodel, testeye, entmins, entmaxs)) { culled_portal++; continue; @@ -673,36 +670,18 @@ void SV_WriteEntitiesToClient (client_t *client, edict_t *clent, sizebuf_t *msg) testorigin[1] = lhrandom(entmins[1], entmaxs[1]); testorigin[2] = lhrandom(entmins[2], entmaxs[2]); - memset (&trace, 0, sizeof(trace_t)); - trace.fraction = 1; - trace.allsolid = true; - VectorCopy(testorigin, trace.endpos); - - VectorCopy(org, RecursiveHullCheckInfo.start); - VectorSubtract(testorigin, testeye, RecursiveHullCheckInfo.dist); - RecursiveHullCheckInfo.hull = sv.worldmodel->hulls; - RecursiveHullCheckInfo.trace = &trace; - SV_RecursiveHullCheck (sv.worldmodel->hulls->firstclipnode, 0, 1, testeye, testorigin); + Collision_ClipTrace(&trace, NULL, sv.worldmodel, vec3_origin, vec3_origin, vec3_origin, testeye, vec3_origin, vec3_origin, testorigin); if (trace.fraction == 1) client->visibletime[e] = realtime + 1; else { //test nearest point on bbox - testorigin[0] = bound(entmins[0], org[0], entmaxs[0]); - testorigin[1] = bound(entmins[1], org[1], entmaxs[1]); - testorigin[2] = bound(entmins[2], org[2], entmaxs[2]); + testorigin[0] = bound(entmins[0], testeye[0], entmaxs[0]); + testorigin[1] = bound(entmins[1], testeye[1], entmaxs[1]); + testorigin[2] = bound(entmins[2], testeye[2], entmaxs[2]); - memset (&trace, 0, sizeof(trace_t)); - trace.fraction = 1; - trace.allsolid = true; - VectorCopy(testorigin, trace.endpos); - - VectorCopy(org, RecursiveHullCheckInfo.start); - VectorSubtract(testorigin, testeye, RecursiveHullCheckInfo.dist); - RecursiveHullCheckInfo.hull = sv.worldmodel->hulls; - RecursiveHullCheckInfo.trace = &trace; - SV_RecursiveHullCheck (sv.worldmodel->hulls->firstclipnode, 0, 1, testeye, testorigin); + Collision_ClipTrace(&trace, NULL, sv.worldmodel, vec3_origin, vec3_origin, vec3_origin, testeye, vec3_origin, vec3_origin, testorigin); if (trace.fraction == 1) client->visibletime[e] = realtime + 1; @@ -895,13 +874,11 @@ void SV_WriteEntitiesToClient (client_t *client, edict_t *clent, sizebuf_t *msg) int e, clentnum, flags, alpha, glowcolor, glowsize, scale, effects; int culled_pvs, culled_portal, culled_trace, visibleentities, totalentities; qbyte *pvs; - vec3_t org, origin, angles, entmins, entmaxs; + vec3_t origin, angles, entmins, entmaxs, testorigin, testeye; edict_t *ent; eval_t *val; trace_t trace; model_t *model; - double testeye[3]; - double testorigin[3]; entity_frame_t entityframe; entity_state_t *s; @@ -912,9 +889,8 @@ void SV_WriteEntitiesToClient (client_t *client, edict_t *clent, sizebuf_t *msg) // find the client's PVS VectorAdd (clent->v.origin, clent->v.view_ofs, testeye); - VectorCopy (testeye, org); - pvs = SV_FatPVS (org); - EntityFrame_Clear(&entityframe, org); + pvs = SV_FatPVS (testeye); + EntityFrame_Clear(&entityframe, testeye); culled_pvs = 0; culled_portal = 0; @@ -1028,7 +1004,7 @@ void SV_WriteEntitiesToClient (client_t *client, edict_t *clent, sizebuf_t *msg) } // or not visible through the portals - if (sv_cullentities_portal.integer && !Portal_CheckBox(sv.worldmodel, org, entmins, entmaxs)) + if (sv_cullentities_portal.integer && !Portal_CheckBox(sv.worldmodel, testeye, entmins, entmaxs)) { culled_portal++; continue; @@ -1041,16 +1017,7 @@ void SV_WriteEntitiesToClient (client_t *client, edict_t *clent, sizebuf_t *msg) testorigin[1] = lhrandom(entmins[1], entmaxs[1]); testorigin[2] = lhrandom(entmins[2], entmaxs[2]); - memset (&trace, 0, sizeof(trace_t)); - trace.fraction = 1; - trace.allsolid = true; - VectorCopy(testorigin, trace.endpos); - - VectorCopy(org, RecursiveHullCheckInfo.start); - VectorSubtract(testorigin, testeye, RecursiveHullCheckInfo.dist); - RecursiveHullCheckInfo.hull = sv.worldmodel->hulls; - RecursiveHullCheckInfo.trace = &trace; - SV_RecursiveHullCheck (sv.worldmodel->hulls->firstclipnode, 0, 1, testeye, testorigin); + Collision_ClipTrace(&trace, NULL, sv.worldmodel, vec3_origin, vec3_origin, vec3_origin, vec3_origin, testeye, vec3_origin, vec3_origin, testorigin); if (trace.fraction == 1) client->visibletime[e] = realtime + 1; diff --git a/world.c b/world.c index d5444cd9..f4e2436c 100644 --- a/world.c +++ b/world.c @@ -108,189 +108,6 @@ typedef struct moveclip_t; -/* -=============================================================================== - -HULL BOXES - -=============================================================================== -*/ - - -static hull_t box_hull; -static dclipnode_t box_clipnodes[6]; -static mplane_t box_planes[6]; - -/* -=================== -SV_InitBoxHull - -Set up the planes and clipnodes so that the six floats of a bounding box -can just be stored out and get a proper hull_t structure. -=================== -*/ -void SV_InitBoxHull (void) -{ - int i; - int side; - - box_hull.clipnodes = box_clipnodes; - box_hull.planes = box_planes; - box_hull.firstclipnode = 0; - box_hull.lastclipnode = 5; - - for (i=0 ; i<6 ; i++) - { - box_clipnodes[i].planenum = i; - - side = i&1; - - box_clipnodes[i].children[side] = CONTENTS_EMPTY; - if (i != 5) - box_clipnodes[i].children[side^1] = i + 1; - else - box_clipnodes[i].children[side^1] = CONTENTS_SOLID; - - box_planes[i].type = i>>1; - box_planes[i].normal[i>>1] = 1; - } -} - - -/* -=================== -SV_HullForBox - -To keep everything totally uniform, bounding boxes are turned into small -BSP trees instead of being compared directly. -=================== -*/ -hull_t *SV_HullForBox (vec3_t mins, vec3_t maxs) -{ - box_planes[0].dist = maxs[0]; - box_planes[1].dist = mins[0]; - box_planes[2].dist = maxs[1]; - box_planes[3].dist = mins[1]; - box_planes[4].dist = maxs[2]; - box_planes[5].dist = mins[2]; - - return &box_hull; -} - - - -/* -================ -SV_HullForEntity - -Returns a hull that can be used for testing or clipping an object of mins/maxs -size. -Offset is filled in to contain the adjustment that must be added to the -testing object's origin to get a point to use with the returned hull. -================ -*/ -hull_t *SV_HullForEntity (edict_t *ent, vec3_t mins, vec3_t maxs, vec3_t offset) -{ - model_t *model; - vec3_t size; - vec3_t hullmins, hullmaxs; - hull_t *hull; - -// decide which clipping hull to use, based on the size - if (ent->v.solid == SOLID_BSP) - { - // explicit hulls in the BSP model - if (ent->v.movetype != MOVETYPE_PUSH) - Host_Error ("SOLID_BSP without MOVETYPE_PUSH"); - - model = sv.models[ (int)ent->v.modelindex ]; - Mod_CheckLoaded(model); - - // LordHavoc: fixed SOLID_BSP error message - if (!model || model->type != mod_brush) - { - Con_Printf ("SOLID_BSP with a non bsp model, entity dump:\n"); - ED_Print (ent); - Host_Error ("SOLID_BSP with a non bsp model\n"); - } - - VectorSubtract (maxs, mins, size); - // LordHavoc: FIXME!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! - if (model->ishlbsp) - { - if (size[0] < 3) - hull = &model->hulls[0]; // 0x0x0 - else if (size[0] <= 32) - { - if (size[2] < 54) // pick the nearest of 36 or 72 - hull = &model->hulls[3]; // 32x32x36 - else - hull = &model->hulls[1]; // 32x32x72 - } - else - hull = &model->hulls[2]; // 64x64x64 - } - else - { - if (size[0] < 3) - hull = &model->hulls[0]; // 0x0x0 - else if (size[0] <= 32) - hull = &model->hulls[1]; // 32x32x56 - else - hull = &model->hulls[2]; // 64x64x88 - } - -// calculate an offset value to center the origin - VectorSubtract (hull->clip_mins, mins, offset); - VectorAdd (offset, ent->v.origin, offset); - } - else - { // create a temp hull from bounding box sizes - - VectorSubtract (ent->v.mins, maxs, hullmins); - VectorSubtract (ent->v.maxs, mins, hullmaxs); - hull = SV_HullForBox (hullmins, hullmaxs); - - VectorCopy (ent->v.origin, offset); - } - - - return hull; -} - -void SV_RoundUpToHullSize(vec3_t inmins, vec3_t inmaxs, vec3_t outmins, vec3_t outmaxs) -{ - vec3_t size; - hull_t *hull; - - VectorSubtract(inmaxs, inmins, size); - if (sv.worldmodel->ishlbsp) - { - if (size[0] < 3) - hull = &sv.worldmodel->hulls[0]; // 0x0x0 - else if (size[0] <= 32) - { - if (size[2] < 54) // pick the nearest of 36 or 72 - hull = &sv.worldmodel->hulls[3]; // 32x32x36 - else - hull = &sv.worldmodel->hulls[1]; // 32x32x72 - } - else - hull = &sv.worldmodel->hulls[2]; // 64x64x64 - } - else - { - if (size[0] < 3) - hull = &sv.worldmodel->hulls[0]; // 0x0x0 - else if (size[0] <= 32) - hull = &sv.worldmodel->hulls[1]; // 32x32x56 - else - hull = &sv.worldmodel->hulls[2]; // 64x64x88 - } - VectorCopy(inmins, outmins); - VectorAdd(inmins, hull->clip_size, outmaxs); -} - /* =============================================================================== @@ -367,7 +184,7 @@ SV_ClearWorld */ void SV_ClearWorld (void) { - SV_InitBoxHull (); + Collision_Init (); memset (sv_areanodes, 0, sizeof(sv_areanodes)); sv_numareanodes = 0; @@ -663,170 +480,6 @@ LINE TESTING IN HULLS =============================================================================== */ -// 1/32 epsilon to keep floating point happy -#define DIST_EPSILON (0.03125) - -#define HULLCHECKSTATE_EMPTY 0 -#define HULLCHECKSTATE_SOLID 1 -#define HULLCHECKSTATE_DONE 2 - -// LordHavoc: FIXME: this is not thread safe, if threading matters here, pass -// this as a struct to RecursiveHullCheck, RecursiveHullCheck_Impact, etc... -RecursiveHullCheckTraceInfo_t RecursiveHullCheckInfo; -#define RHC RecursiveHullCheckInfo - -void SV_RecursiveHullCheck_Impact (mplane_t *plane, int side) -{ - // LordHavoc: using doubles for extra accuracy - double t1, t2, frac; - - // LordHavoc: now that we have found the impact, recalculate the impact - // point from scratch for maximum accuracy, with an epsilon bias on the - // surface distance - frac = plane->dist; - if (side) - { - frac -= DIST_EPSILON; - VectorNegate (plane->normal, RHC.trace->plane.normal); - RHC.trace->plane.dist = -plane->dist; - } - else - { - frac += DIST_EPSILON; - VectorCopy (plane->normal, RHC.trace->plane.normal); - RHC.trace->plane.dist = plane->dist; - } - - if (plane->type < 3) - { - t1 = RHC.start[plane->type] - frac; - t2 = RHC.start[plane->type] + RHC.dist[plane->type] - frac; - } - else - { - t1 = plane->normal[0] * RHC.start[0] + plane->normal[1] * RHC.start[1] + plane->normal[2] * RHC.start[2] - frac; - t2 = plane->normal[0] * (RHC.start[0] + RHC.dist[0]) + plane->normal[1] * (RHC.start[1] + RHC.dist[1]) + plane->normal[2] * (RHC.start[2] + RHC.dist[2]) - frac; - } - - frac = t1 / (t1 - t2); - frac = bound(0.0f, frac, 1.0); - - RHC.trace->fraction = frac; - RHC.trace->endpos[0] = RHC.start[0] + frac * RHC.dist[0]; - RHC.trace->endpos[1] = RHC.start[1] + frac * RHC.dist[1]; - RHC.trace->endpos[2] = RHC.start[2] + frac * RHC.dist[2]; -} - -int SV_RecursiveHullCheck (int num, double p1f, double p2f, double p1[3], double p2[3]) -{ - dclipnode_t *node; - int side; - double midf, mid[3]; - // LordHavoc: FIXME: this is not thread safe... if threading matters here, - // remove the static prefixes - static int ret; - static mplane_t *plane; - static double t1, t2, frac; - - // LordHavoc: a goto! everyone flee in terror... :) -loc0: - // check for empty - if (num < 0) - { - RHC.trace->endcontents = num; - if (RHC.trace->startcontents) - { - if (num == RHC.trace->startcontents) - RHC.trace->allsolid = false; - else - { - // if the first leaf is solid, set startsolid - if (RHC.trace->allsolid) - RHC.trace->startsolid = true; - return HULLCHECKSTATE_SOLID; - } - return HULLCHECKSTATE_EMPTY; - } - else - { - if (num != CONTENTS_SOLID) - { - RHC.trace->allsolid = false; - if (num == CONTENTS_EMPTY) - RHC.trace->inopen = true; - else - RHC.trace->inwater = true; - } - else - { - // if the first leaf is solid, set startsolid - if (RHC.trace->allsolid) - RHC.trace->startsolid = true; - return HULLCHECKSTATE_SOLID; - } - return HULLCHECKSTATE_EMPTY; - } - } - - // find the point distances - node = RHC.hull->clipnodes + num; - - plane = RHC.hull->planes + node->planenum; - if (plane->type < 3) - { - t1 = p1[plane->type] - plane->dist; - t2 = p2[plane->type] - plane->dist; - } - else - { - t1 = DotProduct (plane->normal, p1) - plane->dist; - t2 = DotProduct (plane->normal, p2) - plane->dist; - } - - // LordHavoc: rearranged the side/frac code - if (t1 >= 0) - { - if (t2 >= 0) - { - num = node->children[0]; - goto loc0; - } - // put the crosspoint DIST_EPSILON pixels on the near side - side = 0; - } - else - { - if (t2 < 0) - { - num = node->children[1]; - goto loc0; - } - // put the crosspoint DIST_EPSILON pixels on the near side - side = 1; - } - - frac = t1 / (t1 - t2); - frac = bound(0.0f, frac, 1.0); - - midf = p1f + ((p2f - p1f) * frac); - mid[0] = RHC.start[0] + midf * RHC.dist[0]; - mid[1] = RHC.start[1] + midf * RHC.dist[1]; - mid[2] = RHC.start[2] + midf * RHC.dist[2]; - - // front side first - ret = SV_RecursiveHullCheck (node->children[side], p1f, midf, p1, mid); - if (ret != HULLCHECKSTATE_EMPTY) - return ret; // solid or done - ret = SV_RecursiveHullCheck (node->children[!side], midf, p2f, mid, p2); - if (ret != HULLCHECKSTATE_SOLID) - return ret; // empty or done - - // front is air and back is solid, this is the impact point... - SV_RecursiveHullCheck_Impact(RHC.hull->planes + node->planenum, side); - - return HULLCHECKSTATE_DONE; -} - /* ================== SV_ClipMoveToEntity @@ -837,70 +490,31 @@ eventually rotation) of the end points */ trace_t SV_ClipMoveToEntity (edict_t *ent, vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end) { + int i; trace_t trace; - vec3_t offset, forward, left, up; - double startd[3], endd[3], tempd[3]; - hull_t *hull; - -// fill in a default trace - memset (&trace, 0, sizeof(trace_t)); - trace.fraction = 1; - trace.allsolid = true; - -// get the clipping hull - hull = SV_HullForEntity (ent, mins, maxs, offset); - - VectorSubtract(start, offset, startd); - VectorSubtract(end, offset, endd); + model_t *model; - // rotate start and end into the model's frame of reference - if (ent->v.solid == SOLID_BSP && (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2])) - { - AngleVectorsFLU (ent->v.angles, forward, left, up); - VectorCopy(startd, tempd); - startd[0] = DotProduct (tempd, forward); - startd[1] = DotProduct (tempd, left); - startd[2] = DotProduct (tempd, up); - VectorCopy(endd, tempd); - endd[0] = DotProduct (tempd, forward); - endd[1] = DotProduct (tempd, left); - endd[2] = DotProduct (tempd, up); - } + i = ent->v.modelindex; + if ((unsigned int) i >= MAX_MODELS) + PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n"); + model = sv.models[i]; + if (i != 0 && model == NULL) + PR_RunError("SV_ClipMoveToEntity: invalid modelindex\n"); - VectorCopy(end, trace.endpos); - -// trace a line through the appropriate clipping hull - VectorCopy(startd, RecursiveHullCheckInfo.start); - VectorSubtract(endd, startd, RecursiveHullCheckInfo.dist); - RecursiveHullCheckInfo.hull = hull; - RecursiveHullCheckInfo.trace = &trace; - SV_RecursiveHullCheck (hull->firstclipnode, 0, 1, startd, endd); - - // if we hit, unrotate endpos and normal, and store the entity we hit - if (trace.fraction != 1) + if ((int) ent->v.solid == SOLID_BSP) { - // rotate endpos back to world frame of reference - if (ent->v.solid == SOLID_BSP && (ent->v.angles[0] || ent->v.angles[1] || ent->v.angles[2])) + Mod_CheckLoaded(model); + if (model->type != mod_brush) { - VectorNegate (ent->v.angles, offset); - AngleVectorsFLU (offset, forward, left, up); - - VectorCopy (trace.endpos, tempd); - trace.endpos[0] = DotProduct (tempd, forward); - trace.endpos[1] = DotProduct (tempd, left); - trace.endpos[2] = DotProduct (tempd, up); - - VectorCopy (trace.plane.normal, tempd); - trace.plane.normal[0] = DotProduct (tempd, forward); - trace.plane.normal[1] = DotProduct (tempd, left); - trace.plane.normal[2] = DotProduct (tempd, up); + Con_Printf ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model, entity dump:\n"); + ED_Print (ent); + Host_Error ("SV_ClipMoveToEntity: SOLID_BSP with a non bsp model\n"); } - // fix offset - VectorAdd (trace.endpos, offset, trace.endpos); - trace.ent = ent; + if (ent->v.movetype != MOVETYPE_PUSH) + Host_Error ("SV_ClipMoveToEntity: SOLID_BSP without MOVETYPE_PUSH"); } - else if (trace.allsolid || trace.startsolid) - trace.ent = ent; + + Collision_ClipTrace(&trace, ent, model, ent->v.origin, ent->v.angles, ent->v.mins, ent->v.maxs, start, mins, maxs, end); return trace; } @@ -989,23 +603,6 @@ loc0: clip->trace.endcontents = trace.endcontents; clip->trace.ent = trace.ent; } - /* - if (trace.allsolid) - { - clip->trace = trace; - return; - } - if (trace.startsolid || trace.fraction < clip->trace.fraction) - { - if (clip->trace.startsolid) - { - clip->trace = trace; - clip->trace.startsolid = true; - } - else - clip->trace = trace; - } - */ } // recurse down both sides @@ -1080,7 +677,7 @@ trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, e clip.type = type; clip.passedict = passedict; - SV_RoundUpToHullSize(clip.mins, clip.maxs, clip.hullmins, clip.hullmaxs); + Collision_RoundUpToHullSize(sv.worldmodel, clip.mins, clip.maxs, clip.hullmins, clip.hullmaxs); if (type == MOVE_MISSILE) { @@ -1108,13 +705,10 @@ trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, e clip.trace = SV_ClipMoveToEntity (sv.edicts, start, mins, maxs, end); // clip to entities - //if (!clip.trace.allsolid) - { - // create the bounding box of the entire move - SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs ); + // create the bounding box of the entire move + SV_MoveBounds ( start, bigmins, bigmaxs, end, clip.boxmins, clip.boxmaxs ); - SV_ClipToLinks ( sv_areanodes, &clip ); - } + SV_ClipToLinks ( sv_areanodes, &clip ); return clip.trace; } diff --git a/world.h b/world.h index db8b5ca8..624b9431 100644 --- a/world.h +++ b/world.h @@ -19,39 +19,7 @@ Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ // world.h -typedef struct -{ - vec3_t normal; - float dist; -} plane_t; - -typedef struct -{ - // if true, the entire trace was in solid - qboolean allsolid; - // if true, the initial point was in solid - qboolean startsolid; - // if true, the trace passed through empty somewhere - qboolean inopen; - // if true, the trace passed through water somewhere - qboolean inwater; - // fraction of the total distance that was traveled before impact - // (1.0 = did not hit anything) - double fraction; - // final position - double endpos[3]; - // surface normal at impact - plane_t plane; - // entity the surface is on - edict_t *ent; - // if not zero, treats this value as empty, and all others as solid (impact - // on content change) - int startcontents; - // the contents that was hit at the end or impact point - int endcontents; -} -trace_t; - +#include "collision.h" #define MOVE_NORMAL 0 #define MOVE_NOMONSTERS 1 @@ -83,7 +51,7 @@ extern int SV_HullPointContents (hull_t *hull, int num, vec3_t p); edict_t *SV_TestEntityPosition (edict_t *ent); trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, edict_t *passedict); -// mins and maxs are reletive +// mins and maxs are relative // if the entire move stays in a solid volume, trace.allsolid will be set @@ -94,18 +62,3 @@ trace_t SV_Move (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, int type, e // shouldn't be considered solid objects // passedict is explicitly excluded from clipping checks (normally NULL) - -int SV_RecursiveHullCheck (int num, double p1f, double p2f, double p1[3], double p2[3]); - -typedef struct -{ - hull_t *hull; - trace_t *trace; - double start[3]; - double dist[3]; -} -RecursiveHullCheckTraceInfo_t; - -// LordHavoc: FIXME: this is not thread safe, if threading matters here, pass -// this as a struct to RecursiveHullCheck, RecursiveHullCheck_Impact, etc... -extern RecursiveHullCheckTraceInfo_t RecursiveHullCheckInfo; -- 2.39.2