split out RecursiveHullCheck and related code into collision.c (shared by client...
authorlordhavoc <lordhavoc@d7cf8633-e32d-0410-b094-e92efae38249>
Tue, 21 May 2002 10:47:23 +0000 (10:47 +0000)
committerlordhavoc <lordhavoc@d7cf8633-e32d-0410-b094-e92efae38249>
Tue, 21 May 2002 10:47:23 +0000 (10:47 +0000)
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

16 files changed:
cgamevm.c
chase.c
cl_collision.c [new file with mode: 0644]
cl_collision.h [new file with mode: 0644]
cl_main.c
cl_particles.c
client.h
collision.c [new file with mode: 0644]
collision.h [new file with mode: 0644]
makefile
makefile.mingw
r_explosion.c
r_light.c
sv_main.c
world.c
world.h

index 249185e..57f53dc 100644 (file)
--- 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 1a9da00..fa0f0a0 100644 (file)
--- 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 (file)
index 0000000..22d846a
--- /dev/null
@@ -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 (file)
index 0000000..ec4a89f
--- /dev/null
@@ -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
index b387596..73139f7 100644 (file)
--- 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();
index 4bc5735..aba0f15 100644 (file)
@@ -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
index a2fccef..4b7eab4 100644 (file)
--- 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 (file)
index 0000000..dfbfedb
--- /dev/null
@@ -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 (file)
index 0000000..3611195
--- /dev/null
@@ -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
index addcf78..b834db8 100644 (file)
--- 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
index 4f6a5a7..d4349d8 100644 (file)
@@ -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
index 56ad69a..a3991d2 100644 (file)
@@ -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;
index 6860122..c8984b7 100644 (file)
--- 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
index b1dd740..00fb058 100644 (file)
--- 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 d5444cd..f4e2436 100644 (file)
--- 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 db8b5ca..624b943 100644 (file)
--- 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;