added trace.realfraction field which is now used for comparisons instead of fraction...
authorhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Mon, 2 Feb 2004 03:56:38 +0000 (03:56 +0000)
committerhavoc <havoc@d7cf8633-e32d-0410-b094-e92efae38249>
Mon, 2 Feb 2004 03:56:38 +0000 (03:56 +0000)
optimized q3bsp point traces (point, not line)
optimized q3bsp line traces (finally got that code working, and added optimized line-triangle tracing code for curves which is 52% faster)
optimized q3bsp brush traces (or tried to...  seems to be slower unfortunately, more work to do on this in the future)
BrushForBox now sets the mins/maxs of the brush for culling
reduced q3mnode_t structure by 4 bytes (checks plane pointer now instead of a dedicated isnode variable)
cleaned up some collision code a bit
added some TargetQuake workarounds (spew warnings instead of crashing to console) for weird physics settings (like MOVETYPE_PUSH and SOLID_BSP with no model)

git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@3853 d7cf8633-e32d-0410-b094-e92efae38249

cl_collision.c
collision.c
collision.h
model_alias.c
model_brush.c
model_shared.h
todo
world.c

index 45dd768..486e875 100644 (file)
@@ -33,7 +33,7 @@ int cl_traceline_startsupercontents;
 
 float CL_TraceLine(const vec3_t start, const vec3_t end, vec3_t impact, vec3_t normal, int hitbmodels, entity_render_t **hitent, int hitsupercontentsmask)
 {
-       float maxfrac;
+       float maxfrac, maxrealfrac;
        int n;
        entity_render_t *ent;
        float tracemins[3], tracemaxs[3];
@@ -47,12 +47,11 @@ float CL_TraceLine(const vec3_t start, const vec3_t end, vec3_t impact, vec3_t n
        if (cl.worldmodel && cl.worldmodel->TraceBox)
                cl.worldmodel->TraceBox(cl.worldmodel, 0, &trace, start, start, end, end, hitsupercontentsmask);
 
-       if (impact)
-               VectorLerp(start, trace.fraction, end, impact);
        if (normal)
                VectorCopy(trace.plane.normal, normal);
        cl_traceline_startsupercontents = trace.startsupercontents;
        maxfrac = trace.fraction;
+       maxrealfrac = trace.realfraction;
 
        if (hitbmodels && cl_num_brushmodel_entities)
        {
@@ -81,13 +80,12 @@ float CL_TraceLine(const vec3_t start, const vec3_t end, vec3_t impact, vec3_t n
                                ent->model->TraceBox(ent->model, 0, &trace, starttransformed, starttransformed, endtransformed, endtransformed, hitsupercontentsmask);
 
                        cl_traceline_startsupercontents |= trace.startsupercontents;
-                       if (maxfrac > trace.fraction)
+                       if (maxrealfrac > trace.realfraction)
                        {
                                if (hitent)
                                        *hitent = ent;
                                maxfrac = trace.fraction;
-                               if (impact)
-                                       VectorLerp(start, trace.fraction, end, impact);
+                               maxrealfrac = trace.realfraction;
                                if (normal)
                                {
                                        VectorCopy(trace.plane.normal, tempnormal);
@@ -97,6 +95,8 @@ float CL_TraceLine(const vec3_t start, const vec3_t end, vec3_t impact, vec3_t n
                }
        }
        if (maxfrac < 0 || maxfrac > 1) Con_Printf("fraction out of bounds %f %s:%d\n", maxfrac, __FILE__, __LINE__);
+       if (impact)
+               VectorLerp(start, maxfrac, end, impact);
        return maxfrac;
 }
 
index f6636ba..7637071 100644 (file)
@@ -162,12 +162,15 @@ loc0:
                VectorCopy (plane->normal, t->trace->plane.normal);
        }
 
-       // bias away from surface a bit
-       t1 = DotProduct(t->trace->plane.normal, t->start) - (t->trace->plane.dist + DIST_EPSILON);
-       t2 = DotProduct(t->trace->plane.normal, t->end) - (t->trace->plane.dist + DIST_EPSILON);
-
+       // calculate the true fraction
+       t1 = DotProduct(t->trace->plane.normal, t->start) - t->trace->plane.dist;
+       t2 = DotProduct(t->trace->plane.normal, t->end) - t->trace->plane.dist;
        midf = t1 / (t1 - t2);
-       t->trace->fraction = bound(0.0f, midf, 1.0);
+       t->trace->realfraction = bound(0, midf, 1);
+
+       // calculate the return fraction which is nudged off the surface a bit
+       midf = (t1 - DIST_EPSILON) / (t1 - t2);
+       t->trace->fraction = bound(0, midf, 1);
 
 #if COLLISIONPARANOID >= 3
        Con_Printf("D");
@@ -271,6 +274,7 @@ void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cm
        rhc.trace = trace;
        rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
        rhc.trace->fraction = 1;
+       rhc.trace->realfraction = 1;
        rhc.trace->allsolid = true;
        VectorCopy(start, rhc.start);
        VectorCopy(end, rhc.end);
@@ -397,7 +401,6 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla
        colplanef_t planesbuf[256];
        int elementsbuf[1024];
        int polypointbuf[256];
-       float mins[3], maxs[3];
        // construct a collision brush (points, planes, and renderable mesh) from
        // a set of planes, this also optimizes out any unnecessary planes (ones
        // whose polygon is clipped away by the other planes)
@@ -505,25 +508,6 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla
                numplanes++;
        }
 
-       // recalc distances
-       for (j = 0;j < numplanes;j++)
-               planesbuf[j].dist = furthestplanedist_float(planesbuf[j].normal, pointsbuf, numpoints);
-
-       if (numpoints)
-       {
-               VectorCopy(pointsbuf[0].v, mins);
-               VectorCopy(pointsbuf[0].v, maxs);
-               for (j = 1;j < numpoints;j++)
-               {
-                       mins[0] = min(mins[0], pointsbuf[j].v[0]);
-                       mins[1] = min(mins[1], pointsbuf[j].v[1]);
-                       mins[2] = min(mins[2], pointsbuf[j].v[2]);
-                       maxs[0] = max(maxs[0], pointsbuf[j].v[0]);
-                       maxs[1] = max(maxs[1], pointsbuf[j].v[1]);
-                       maxs[2] = max(maxs[2], pointsbuf[j].v[2]);
-               }
-       }
-
        // if nothing is left, there's nothing to allocate
        if (numtriangles < 4 || numplanes < 4 || numpoints < 4)
                return NULL;
@@ -533,8 +517,20 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla
        memcpy(brush->points, pointsbuf, numpoints * sizeof(colpointf_t));
        memcpy(brush->planes, planesbuf, numplanes * sizeof(colplanef_t));
        memcpy(brush->elements, elementsbuf, numtriangles * sizeof(int[3]));
-       VectorCopy(mins, brush->mins);
-       VectorCopy(maxs, brush->maxs);
+       // recalc distances
+       for (j = 0;j < brush->numplanes;j++)
+               brush->planes[j].dist = furthestplanedist_float(brush->planes[j].normal, brush->points, brush->numpoints);
+       VectorCopy(brush->points[0].v, brush->mins);
+       VectorCopy(brush->points[0].v, brush->maxs);
+       for (j = 1;j < brush->numpoints;j++)
+       {
+               brush->mins[0] = min(brush->mins[0], brush->points[j].v[0]);
+               brush->mins[1] = min(brush->mins[1], brush->points[j].v[1]);
+               brush->mins[2] = min(brush->mins[2], brush->points[j].v[2]);
+               brush->maxs[0] = max(brush->maxs[0], brush->points[j].v[0]);
+               brush->maxs[1] = max(brush->maxs[1], brush->points[j].v[1]);
+               brush->maxs[2] = max(brush->maxs[2], brush->points[j].v[2]);
+       }
        Collision_ValidateBrush(brush);
        return brush;
 }
@@ -704,10 +700,11 @@ colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, i
 void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const colbrushf_t *thatbrush_start, const colbrushf_t *thatbrush_end)
 {
        int nplane, nplane2, fstartsolid, fendsolid, brushsolid;
-       float enterfrac, leavefrac, d1, d2, f, newimpactnormal[3];
+       float enterfrac, leavefrac, d1, d2, f, newimpactnormal[3], enterfrac2;
        const colplanef_t *startplane, *endplane;
 
        enterfrac = -1;
+       enterfrac2 = -1;
        leavefrac = 1;
        fstartsolid = true;
        fendsolid = true;
@@ -766,11 +763,11 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush
                                continue;
                        // enter
                        fstartsolid = false;
-                       f = (d1 - COLLISIONEPSILON) / f;
-                       f = bound(0, f, 1);
+                       f = d1 / (d1 - d2);
                        if (enterfrac < f)
                        {
                                enterfrac = f;
+                               enterfrac2 = (d1 - COLLISIONEPSILON) / (d1 - d2);
                                VectorLerp(startplane->normal, enterfrac, endplane->normal, newimpactnormal);
                        }
                }
@@ -783,8 +780,7 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush
                                continue;
                        // leave
                        fendsolid = false;
-                       f = (d1 + COLLISIONEPSILON) / f;
-                       f = bound(0, f, 1);
+                       f = d1 / f;
                        if (leavefrac > f)
                                leavefrac = f;
                }
@@ -806,9 +802,10 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush
        // penetrating line segment is normally zero length if this brush was
        // generated from a polygon (infinitely thin), and could even be slightly
        // positive or negative due to rounding errors in that case.
-       if (brushsolid && enterfrac > -1 && enterfrac < trace->fraction && enterfrac - (1.0f / 1024.0f) <= leavefrac)
+       if (brushsolid && enterfrac > -1 && enterfrac < trace->realfraction && enterfrac - (1.0f / 1024.0f) <= leavefrac)
        {
-               trace->fraction = bound(0, enterfrac, 1);
+               trace->realfraction = bound(0, enterfrac, 1);
+               trace->fraction = bound(0, enterfrac2, 1);  
                VectorCopy(newimpactnormal, trace->plane.normal);
        }
 }
@@ -817,7 +814,7 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush
 void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const colbrushf_t *thatbrush_start, const colbrushf_t *thatbrush_end)
 {
        int nplane, fstartsolid, fendsolid, brushsolid;
-       float enterfrac, leavefrac, d1, d2, f, newimpactnormal[3];
+       float enterfrac, leavefrac, d1, d2, f, newimpactnormal[3], enterfrac2;
        const colplanef_t *startplane, *endplane;
 
        enterfrac = -1;
@@ -830,7 +827,7 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const
                startplane = thatbrush_start->planes + nplane;
                endplane = thatbrush_end->planes + nplane;
                d1 = DotProduct(startplane->normal, linestart) - startplane->dist;
-               d2 = DotProduct(endplane->normal, lineend) - endplane->dist - COLLISIONEPSILON2;
+               d2 = DotProduct(endplane->normal, lineend) - endplane->dist;
                if (developer.integer)
                {
                        // any brush with degenerate planes is not worth handling
@@ -857,11 +854,11 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const
                                continue;
                        // enter
                        fstartsolid = false;
-                       f = (d1 - COLLISIONEPSILON) / f;
-                       f = bound(0, f, 1);
+                       f = d1 / (d1 - d2);
                        if (enterfrac < f)
                        {
                                enterfrac = f;
+                               enterfrac2 = (d1 - COLLISIONEPSILON) / (d1 - d2);
                                VectorLerp(startplane->normal, enterfrac, endplane->normal, newimpactnormal);
                        }
                }
@@ -874,8 +871,7 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const
                                continue;
                        // leave
                        fendsolid = false;
-                       f = (d1 + COLLISIONEPSILON) / f;
-                       f = bound(0, f, 1);
+                       f = d1 / (d1 - d2);
                        if (leavefrac > f)
                                leavefrac = f;
                }
@@ -897,13 +893,31 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const
        // penetrating line segment is normally zero length if this brush was
        // generated from a polygon (infinitely thin), and could even be slightly
        // positive or negative due to rounding errors in that case.
-       if (brushsolid && enterfrac > -1 && enterfrac < trace->fraction && enterfrac - (1.0f / 1024.0f) <= leavefrac)
+       if (brushsolid && enterfrac > -1 && enterfrac < trace->realfraction && enterfrac - (1.0f / 1024.0f) <= leavefrac)
        {
-               trace->fraction = bound(0, enterfrac, 1);
+               trace->realfraction = bound(0, enterfrac, 1);
+               trace->fraction = bound(0, enterfrac2, 1);
                VectorCopy(newimpactnormal, trace->plane.normal);
        }
 }
 
+void Collision_TracePointBrushFloat(trace_t *trace, const vec3_t point, const colbrushf_t *thatbrush)
+{
+       int nplane;
+       const colplanef_t *plane;
+
+       for (nplane = 0, plane = thatbrush->planes;nplane < thatbrush->numplanes;nplane++, plane++)
+               if (DotProduct(plane->normal, point) > plane->dist)
+                       return;
+
+       trace->startsupercontents |= thatbrush->supercontents;
+       if (trace->hitsupercontentsmask & thatbrush->supercontents)
+       {
+               trace->startsolid = true;
+               trace->allsolid = true;
+       }
+}
+
 static colpointf_t polyf_points[256];
 static colplanef_t polyf_planes[256 + 2];
 static colbrushf_t polyf_brush;
@@ -974,7 +988,10 @@ void Collision_TraceLinePolygonFloat(trace_t *trace, const vec3_t linestart, con
 void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, int supercontents, const vec3_t segmentmins, const vec3_t segmentmaxs)
 {
        int i;
-       float facemins[3], facemaxs[3];
+#if 1
+       for (i = 0;i < numtriangles;i++, element3i += 3)
+               Collision_TraceLineTriangleFloat(trace, linestart, lineend, vertex3f + element3i[0] * 3, vertex3f + element3i[1] * 3, vertex3f + element3i[2] * 3);
+#else
        polyf_brush.numpoints = 3;
        polyf_brush.numplanes = 5;
        polyf_brush.points = polyf_points;
@@ -982,6 +999,7 @@ void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart
        polyf_brush.supercontents = supercontents;
        for (i = 0;i < numtriangles;i++, element3i += 3)
        {
+               float facemins[3], facemaxs[3];
                VectorCopy(vertex3f + element3i[0] * 3, polyf_points[0].v);
                VectorCopy(vertex3f + element3i[1] * 3, polyf_points[1].v);
                VectorCopy(vertex3f + element3i[2] * 3, polyf_points[2].v);
@@ -998,6 +1016,7 @@ void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart
                        Collision_TraceLineBrushFloat(trace, linestart, lineend, &polyf_brush, &polyf_brush);
                }
        }
+#endif
 }
 
 
@@ -1065,7 +1084,7 @@ void Collision_InitBrushForBox(void)
 
 colbrushf_t *Collision_BrushForBox(const matrix4x4_t *matrix, const vec3_t mins, const vec3_t maxs)
 {
-       int i;
+       int i, j;
        vec3_t v;
        colbrushf_t *brush;
        if (brushforbox_brush[0].numpoints == 0)
@@ -1094,9 +1113,21 @@ colbrushf_t *Collision_BrushForBox(const matrix4x4_t *matrix, const vec3_t mins,
                        v[i >> 1] = i & 1 ? 1 : -1;
                        Matrix4x4_Transform3x3(matrix, v, brush->planes[i].normal);
                        VectorNormalize(brush->planes[i].normal);
-                       brush->planes[i].dist = furthestplanedist_float(brush->planes[i].normal, brush->points, brush->numpoints);
                }
        }
+       for (j = 0;j < brush->numplanes;j++)
+               brush->planes[j].dist = furthestplanedist_float(brush->planes[j].normal, brush->points, brush->numpoints);
+       VectorCopy(brush->points[0].v, brush->mins);
+       VectorCopy(brush->points[0].v, brush->maxs);
+       for (j = 1;j < brush->numpoints;j++)
+       {
+               brush->mins[0] = min(brush->mins[0], brush->points[j].v[0]);
+               brush->mins[1] = min(brush->mins[1], brush->points[j].v[1]);
+               brush->mins[2] = min(brush->mins[2], brush->points[j].v[2]);
+               brush->maxs[0] = max(brush->maxs[0], brush->points[j].v[0]);
+               brush->maxs[1] = max(brush->maxs[1], brush->points[j].v[1]);
+               brush->maxs[2] = max(brush->maxs[2], brush->points[j].v[2]);
+       }
        Collision_ValidateBrush(brush);
        return brush;
 }
@@ -1120,6 +1151,7 @@ void Collision_ClipTrace_BrushBox(trace_t *trace, const vec3_t cmins, const vec3
        memset(trace, 0, sizeof(trace_t));
        trace->hitsupercontentsmask = hitsupercontentsmask;
        trace->fraction = 1;
+       trace->realfraction = 1;
        trace->allsolid = true;
        Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, boxbrush, boxbrush);
 }
@@ -1193,6 +1225,97 @@ float Collision_ClipTrace_Line_Sphere(double *linestart, double *lineend, double
        return impactdist / linelength;
 }
 
+void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const float *point0, const float *point1, const float *point2)
+{
+       float d1, d2, d, f, fnudged, impact[3], edgenormal[3], faceplanenormal[3], faceplanedist, edge[3];
+
+       // this code is designed for clockwise triangles, conversion to
+       // counterclockwise would require swapping some things around...
+       // it is easier to simply swap the point0 and point2 parameters to this
+       // function when calling it than it is to rewire the internals.
+
+       // calculate the faceplanenormal of the triangle, this represents the front side
+       TriangleNormal(point0, point1, point2, faceplanenormal);
+       // there's no point in processing a degenerate triangle (GIGO - Garbage In, Garbage Out)
+       if (DotProduct(faceplanenormal, faceplanenormal) < 0.0001f)
+               return;
+       // normalize the normal
+       VectorNormalize(faceplanenormal);
+       // calculate the distance
+       faceplanedist = DotProduct(point0, faceplanenormal);
+
+       // calculate the start distance
+       d1 = DotProduct(faceplanenormal, linestart) - faceplanedist;
+       // if start point is on the back side there is no collision
+       // (we don't care about traces going through the triangle the wrong way)
+       if (d1 < 0)
+               return;
+
+       // calculate the end distance
+       d2 = DotProduct(faceplanenormal, lineend) - faceplanedist;
+       // if both are in front, there is no collision
+       if (d2 >= 0)
+               return;
+
+       // from here on we know d1 is >= 0 and d2 is < 0
+       // this means the line starts infront and ends behind, passing through it
+
+       // calculate the recipricol of the distance delta,
+       // so we can use it multiple times cheaply (instead of division)
+       d = 1.0f / (d1 - d2);
+       // calculate the impact fraction by taking the start distance (> 0)
+       // and subtracting the face plane distance (this is the distance of the
+       // triangle along that same normal)
+       // then multiply by the recipricol distance delta
+       f = d1 * d;
+       // skip out if this impact is further away than previous ones
+       if (f > trace->realfraction)
+               return;
+       // calculate the perfect impact point for classification of insidedness
+       impact[0] = linestart[0] + f * (lineend[0] - linestart[0]);
+       impact[1] = linestart[1] + f * (lineend[1] - linestart[1]);
+       impact[2] = linestart[2] + f * (lineend[2] - linestart[2]);
+
+       // calculate the edge normal and reject if impact is outside triangle
+       // (an edge normal faces away from the triangle, to get the desired normal
+       //  a crossproduct with the faceplanenormal is used, and because of the way
+       // the insidedness comparison is written it does not need to be normalized)
+       
+       VectorSubtract(point2, point0, edge);
+       CrossProduct(edge, faceplanenormal, edgenormal);
+       if (DotProduct(impact, edgenormal) > DotProduct(point0, edgenormal))
+               return;
+
+       VectorSubtract(point0, point1, edge);
+       CrossProduct(edge, faceplanenormal, edgenormal);
+       if (DotProduct(impact, edgenormal) > DotProduct(point1, edgenormal))
+               return;
+
+       VectorSubtract(point1, point2, edge);
+       CrossProduct(edge, faceplanenormal, edgenormal);
+       if (DotProduct(impact, edgenormal) > DotProduct(point2, edgenormal))
+               return;
+
+       // store the new trace fraction
+       trace->realfraction = bound(0, f, 1);
+
+       // calculate a nudged fraction to keep it out of the surface
+       // (the main fraction remains perfect)
+       fnudged = (d1 - COLLISIONEPSILON) * d;
+       trace->fraction = bound(0, fnudged, 1);
+
+       // store the new trace endpos
+       // not needed, it's calculated later when the trace is finished
+       //trace->endpos[0] = linestart[0] + fnudged * (lineend[0] - linestart[0]);
+       //trace->endpos[1] = linestart[1] + fnudged * (lineend[1] - linestart[1]);
+       //trace->endpos[2] = linestart[2] + fnudged * (lineend[2] - linestart[2]);
+
+       // store the new trace plane (because collisions only happen from
+       // the front this is always simply the triangle normal, never flipped)
+       VectorCopy(faceplanenormal, trace->plane.normal);
+       trace->plane.dist = faceplanedist;
+}
+
 typedef struct colbspnode_s
 {
        mplane_t plane;
index 1f58f95..f13f722 100644 (file)
@@ -26,6 +26,10 @@ typedef struct trace_s
        // fraction of the total distance that was traveled before impact
        // (1.0 = did not hit anything)
        double fraction;
+       // like fraction but is not nudged away from the surface (better for
+       // comparisons between two trace structs, as only one nudge for the final
+       // result is ever needed)
+       double realfraction;
        // final position of the trace (simply a point between start and end)
        double endpos[3];
        // surface normal at impact (not really correct for edge collisions)
@@ -94,6 +98,7 @@ void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *th
 void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const colbrushf_t *thatbrush_start, const colbrushf_t *thatbrush_end);
 void Collision_TraceLinePolygonFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numpoints, const float *points, int supercontents);
 void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, int numtriangles, const int *element3i, const float *vertex3f, int supercontents, const vec3_t segmentmins, const vec3_t segmentmaxs);
+void Collision_TracePointBrushFloat(trace_t *trace, const vec3_t point, const colbrushf_t *thatbrush);
 
 void Collision_TraceBrushPolygonTransformFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, const matrix4x4_t *polygonmatrixstart, const matrix4x4_t *polygonmatrixend, int supercontents);
 
@@ -101,6 +106,9 @@ colbrushf_t *Collision_BrushForBox(const matrix4x4_t *matrix, const vec3_t mins,
 
 void Collision_BoundingBoxOfBrushTraceSegment(const colbrushf_t *start, const colbrushf_t *end, vec3_t mins, vec3_t maxs, float startfrac, float endfrac);
 
+float Collision_ClipTrace_Line_Sphere(double *linestart, double *lineend, double *sphereorigin, double sphereradius, double *impactpoint, double *impactnormal);
+void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, const vec3_t lineend, const float *point0, const float *point1, const float *point2);
+
 // this enables rather large debugging spew!
 // settings:
 // 0 = no spew
index e3c0345..3f050ab 100644 (file)
@@ -34,6 +34,7 @@ static void Mod_MDLMD2MD3_TraceBox(model_t *model, int frame, trace_t *trace, co
        matrix4x4_t startmatrix, endmatrix;
        memset(trace, 0, sizeof(*trace));
        trace->fraction = 1;
+       trace->realfraction = 1;
        trace->hitsupercontentsmask = hitsupercontentsmask;
        segmentmins[0] = min(boxstartmins[0], boxendmins[0]);
        segmentmins[1] = min(boxstartmins[1], boxendmins[1]);
index 1ede5d8..4db80c9 100644 (file)
@@ -36,7 +36,8 @@ cvar_t r_lightmaprgba = {0, "r_lightmaprgba", "1"};
 cvar_t r_nosurftextures = {0, "r_nosurftextures", "0"};
 cvar_t mod_q3bsp_curves_subdivide_level = {0, "mod_q3bsp_curves_subdivide_level", "2"};
 cvar_t mod_q3bsp_curves_collisions = {0, "mod_q3bsp_curves_collisions", "1"};
-cvar_t mod_q3bsp_optimizedtraceline = {0, "mod_q3bsp_optimizedtraceline", "0"};
+cvar_t mod_q3bsp_optimizedtraceline = {0, "mod_q3bsp_optimizedtraceline", "1"};
+cvar_t mod_q3bsp_debugtracebrush = {0, "mod_q3bsp_debugtracebrush", "0"};
 
 static void Mod_Q1BSP_Collision_Init (void);
 void Mod_BrushInit(void)
@@ -50,6 +51,7 @@ void Mod_BrushInit(void)
        Cvar_RegisterVariable(&mod_q3bsp_curves_subdivide_level);
        Cvar_RegisterVariable(&mod_q3bsp_curves_collisions);
        Cvar_RegisterVariable(&mod_q3bsp_optimizedtraceline);
+       Cvar_RegisterVariable(&mod_q3bsp_debugtracebrush);
        memset(mod_q1bsp_novis, 0xff, sizeof(mod_q1bsp_novis));
        Mod_Q1BSP_Collision_Init();
 }
@@ -516,12 +518,15 @@ loc0:
                VectorCopy (plane->normal, t->trace->plane.normal);
        }
 
-       // bias away from surface a bit
-       t1 = DotProduct(t->trace->plane.normal, t->start) - (t->trace->plane.dist + DIST_EPSILON);
-       t2 = DotProduct(t->trace->plane.normal, t->end) - (t->trace->plane.dist + DIST_EPSILON);
-
+       // calculate the true fraction
+       t1 = DotProduct(t->trace->plane.normal, t->start) - t->trace->plane.dist;
+       t2 = DotProduct(t->trace->plane.normal, t->end) - t->trace->plane.dist;
        midf = t1 / (t1 - t2);
-       t->trace->fraction = bound(0.0f, midf, 1.0);
+       t->trace->realfraction = bound(0, midf, 1);
+
+       // calculate the return fraction which is nudged off the surface a bit
+       midf = (t1 - DIST_EPSILON) / (t1 - t2);
+       t->trace->fraction = bound(0, midf, 1);
 
 #if COLLISIONPARANOID >= 3
        Con_Printf("D");
@@ -564,6 +569,7 @@ static void Mod_Q1BSP_TraceBox(struct model_s *model, int frame, trace_t *trace,
        rhc.trace = trace;
        rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
        rhc.trace->fraction = 1;
+       rhc.trace->realfraction = 1;
        rhc.trace->allsolid = true;
        VectorSubtract(boxstartmaxs, boxstartmins, boxsize);
        if (boxsize[0] < 3)
@@ -668,6 +674,7 @@ void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cm
        memset(trace, 0, sizeof(trace_t));
        trace->hitsupercontentsmask = hitsupercontentsmask;
        trace->fraction = 1;
+       trace->realfraction = 1;
        Collision_TraceLineBrushFloat(trace, start, end, &cbox, &cbox);
 #else
        RecursiveHullCheckTraceInfo_t rhc;
@@ -692,12 +699,13 @@ void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cm
        rhc.trace = trace;
        rhc.trace->hitsupercontentsmask = hitsupercontentsmask;
        rhc.trace->fraction = 1;
+       rhc.trace->realfraction = 1;
        rhc.trace->allsolid = true;
        VectorCopy(start, rhc.start);
        VectorCopy(end, rhc.end);
        VectorSubtract(rhc.end, rhc.start, rhc.dist);
        Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end);
-       VectorMA(rhc.start, rhc.trace->fraction, rhc.dist, rhc.trace->endpos);
+       //VectorMA(rhc.start, rhc.trace->fraction, rhc.dist, rhc.trace->endpos);
        if (rhc.trace->startsupercontents)
                rhc.trace->startsupercontents = boxsupercontents;
 #endif
@@ -851,11 +859,12 @@ void Mod_Q1BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientcolor, v
 static void Mod_Q1BSP_DecompressVis(const qbyte *in, const qbyte *inend, qbyte *out, qbyte *outend)
 {
        int c;
+       qbyte *outstart = out;
        while (out < outend)
        {
                if (in == inend)
                {
-                       Con_DPrintf("Mod_Q1BSP_DecompressVis: input underrun on model \"%s\"\n", loadmodel->name);
+                       Con_DPrintf("Mod_Q1BSP_DecompressVis: input underrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
                        return;
                }
                c = *in++;
@@ -865,14 +874,14 @@ static void Mod_Q1BSP_DecompressVis(const qbyte *in, const qbyte *inend, qbyte *
                {
                        if (in == inend)
                        {
-                               Con_DPrintf("Mod_Q1BSP_DecompressVis: input underrun on model \"%s\"\n", loadmodel->name);
+                               Con_DPrintf("Mod_Q1BSP_DecompressVis: input underrun (during zero-run) on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
                                return;
                        }
                        for (c = *in++;c > 0;c--)
                        {
                                if (out == outend)
                                {
-                                       Con_DPrintf("Mod_Q1BSP_DecompressVis: output overrun on model \"%s\"\n", loadmodel->name);
+                                       Con_DPrintf("Mod_Q1BSP_DecompressVis: output overrun on model \"%s\" (decompressed %i of %i output bytes)\n", loadmodel->name, out - outstart, outend - outstart);
                                        return;
                                }
                                *out++ = 0;
@@ -1970,7 +1979,8 @@ static void Mod_Q1BSP_LoadLeafs(lump_t *l)
 
        loadmodel->brushq1.leafs = out;
        loadmodel->brushq1.numleafs = count;
-       pvschainbytes = ((loadmodel->brushq1.numleafs - 1)+7)>>3;
+       // get visleafs from the submodel data
+       pvschainbytes = (loadmodel->brushq1.submodels[0].visleafs+7)>>3;
        loadmodel->brushq1.data_decompressedpvs = pvs = Mem_Alloc(loadmodel->mempool, loadmodel->brushq1.numleafs * pvschainbytes);
 
        for ( i=0 ; i<count ; i++, in++, out++)
@@ -2732,7 +2742,7 @@ static void Mod_Q1BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org,
        }
        // FIXME: code!
        // if this is a leaf, accumulate the pvs bits
-       if (node->contents != CONTENTS_SOLID && ((mleaf_t *)node)->pvsdata)
+       if (/*node->contents != CONTENTS_SOLID && */((mleaf_t *)node)->pvsdata)
                for (i = 0;i < pvsbytes;i++)
                        pvsbuffer[i] |= ((mleaf_t *)node)->pvsdata[i];
 }
@@ -2743,6 +2753,11 @@ static int Mod_Q1BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, qbyt
 {
        int bytes = ((model->brushq1.numleafs - 1) + 7) >> 3;
        bytes = min(bytes, pvsbufferlength);
+       if (r_novis.integer)
+       {
+               memset(pvsbuffer, 0xFF, bytes);
+               return bytes;
+       }
        memset(pvsbuffer, 0, bytes);
        Mod_Q1BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brushq1.nodes);
        return bytes;
@@ -2862,10 +2877,11 @@ void Mod_Q1BSP_Load(model_t *mod, void *buffer)
        Mod_Q1BSP_LoadFaces(&header->lumps[LUMP_FACES]);
        Mod_Q1BSP_LoadMarksurfaces(&header->lumps[LUMP_MARKSURFACES]);
        Mod_Q1BSP_LoadVisibility(&header->lumps[LUMP_VISIBILITY]);
+       // load submodels before leafs because they contain the number of vis leafs
+       Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS]);
        Mod_Q1BSP_LoadLeafs(&header->lumps[LUMP_LEAFS]);
        Mod_Q1BSP_LoadNodes(&header->lumps[LUMP_NODES]);
        Mod_Q1BSP_LoadClipnodes(&header->lumps[LUMP_CLIPNODES]);
-       Mod_Q1BSP_LoadSubmodels(&header->lumps[LUMP_MODELS]);
 
        if (mod->brushq1.data_compressedpvs)
                Mem_Free(mod->brushq1.data_compressedpvs);
@@ -2875,9 +2891,6 @@ void Mod_Q1BSP_Load(model_t *mod, void *buffer)
        Mod_Q1BSP_MakeHull0();
        Mod_Q1BSP_MakePortals();
 
-       if (developer.integer)
-               Con_Printf("Some stats for q1bsp model \"%s\": %i faces, %i nodes, %i leafs, %i visleafs, %i visleafportals\n", loadmodel->name, loadmodel->brushq1.numsurfaces, loadmodel->brushq1.numnodes, loadmodel->brushq1.numleafs, loadmodel->brushq1.numleafs - 1, loadmodel->brushq1.numportals);
-
        mod->numframes = 2;             // regular and alternate animation
 
        mainmempool = mod->mempool;
@@ -2983,6 +2996,9 @@ void Mod_Q1BSP_Load(model_t *mod, void *buffer)
 
        loadmodel = originalloadmodel;
        //Mod_Q1BSP_ProcessLightList();
+
+       if (developer.integer)
+               Con_Printf("Some stats for q1bsp model \"%s\": %i faces, %i nodes, %i leafs, %i visleafs, %i visleafportals\n", loadmodel->name, loadmodel->brushq1.numsurfaces, loadmodel->brushq1.numnodes, loadmodel->brushq1.numleafs, loadmodel->brushq1.visleafs, loadmodel->brushq1.numportals);
 }
 
 static void Mod_Q2BSP_LoadEntities(lump_t *l)
@@ -4308,15 +4324,15 @@ static void Mod_Q3BSP_LoadLeafs(lump_t *l)
 
        for (i = 0;i < count;i++, in++, out++)
        {
-               out->isnode = false;
                out->parent = NULL;
+               out->plane = NULL;
                out->clusterindex = LittleLong(in->clusterindex);
                out->areaindex = LittleLong(in->areaindex);
                for (j = 0;j < 3;j++)
                {
                        // yes the mins/maxs are ints
-                       out->mins[j] = LittleLong(in->mins[j]);
-                       out->maxs[j] = LittleLong(in->maxs[j]);
+                       out->mins[j] = LittleLong(in->mins[j]) - 1;
+                       out->maxs[j] = LittleLong(in->maxs[j]) + 1;
                }
                n = LittleLong(in->firstleafface);
                c = LittleLong(in->numleaffaces);
@@ -4338,7 +4354,7 @@ static void Mod_Q3BSP_LoadNodes_RecursiveSetParent(q3mnode_t *node, q3mnode_t *p
        if (node->parent)
                Host_Error("Mod_Q3BSP_LoadNodes_RecursiveSetParent: runaway recursion\n");
        node->parent = parent;
-       if (node->isnode)
+       if (node->plane)
        {
                Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[0], node);
                Mod_Q3BSP_LoadNodes_RecursiveSetParent(node->children[1], node);
@@ -4362,7 +4378,6 @@ static void Mod_Q3BSP_LoadNodes(lump_t *l)
 
        for (i = 0;i < count;i++, in++, out++)
        {
-               out->isnode = true;
                out->parent = NULL;
                n = LittleLong(in->planeindex);
                if (n < 0 || n >= loadmodel->brushq3.num_planes)
@@ -4388,8 +4403,8 @@ static void Mod_Q3BSP_LoadNodes(lump_t *l)
                for (j = 0;j < 3;j++)
                {
                        // yes the mins/maxs are ints
-                       out->mins[j] = LittleLong(in->mins[j]);
-                       out->maxs[j] = LittleLong(in->maxs[j]);
+                       out->mins[j] = LittleLong(in->mins[j]) - 1;
+                       out->maxs[j] = LittleLong(in->maxs[j]) + 1;
                }
        }
 
@@ -4526,72 +4541,105 @@ static void Mod_Q3BSP_LightPoint(model_t *model, const vec3_t p, vec3_t ambientc
        //Con_Printf("result: ambient %f %f %f diffuse %f %f %f diffusenormal %f %f %f\n", ambientcolor[0], ambientcolor[1], ambientcolor[2], diffusecolor[0], diffusecolor[1], diffusecolor[2], diffusenormal[0], diffusenormal[1], diffusenormal[2]);
 }
 
-static void Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const vec3_t start, const vec3_t end, vec_t startfrac, vec_t endfrac, const vec3_t linestart, const vec3_t lineend, int markframe)
+static void Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const vec3_t point, int markframe)
+{
+       int i;
+       q3mleaf_t *leaf;
+       colbrushf_t *brush;
+       // find which leaf the point is in
+       while (node->plane)
+               node = node->children[DotProduct(point, node->plane->normal) < node->plane->dist];
+       // point trace the brushes
+       leaf = (q3mleaf_t *)node;
+       for (i = 0;i < leaf->numleafbrushes;i++)
+       {
+               brush = leaf->firstleafbrush[i]->colbrushf;
+               if (brush && brush->markframe != markframe && BoxesOverlap(point, point, brush->mins, brush->maxs))
+               {
+                       brush->markframe = markframe;
+                       Collision_TracePointBrushFloat(trace, point, leaf->firstleafbrush[i]->colbrushf);
+               }
+       }
+       // can't do point traces on curves (they have no thickness)
+}
+
+static void Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const vec3_t start, const vec3_t end, vec_t startfrac, vec_t endfrac, const vec3_t linestart, const vec3_t lineend, int markframe, const vec3_t segmentmins, const vec3_t segmentmaxs)
 {
        int i, startside, endside;
-       float dist1, dist2, midfrac, mid[3], segmentmins[3], segmentmaxs[3];
+       float dist1, dist2, midfrac, mid[3], nodesegmentmins[3], nodesegmentmaxs[3];
        q3mleaf_t *leaf;
        q3mface_t *face;
        colbrushf_t *brush;
-       if (startfrac >= trace->fraction)
+       if (startfrac > trace->realfraction)
                return;
        // note: all line fragments past first impact fraction are ignored
-       while (node->isnode)
-       {
-               // recurse down node sides
-               dist1 = PlaneDiff(start, node->plane);
-               dist2 = PlaneDiff(end, node->plane);
-               startside = dist1 < 0;
-               endside = dist2 < 0;
-               if (startside == endside)
-               {
-                       // most of the time the line fragment is on one side of the plane
-                       node = node->children[startside];
-               }
-               else
+       if (VectorCompare(start, end))
+       {
+               // find which leaf the point is in
+               while (node->plane)
+                       node = node->children[DotProduct(start, node->plane->normal) < node->plane->dist];
+       }
+       else
+       {
+               // find which nodes the line is in and recurse for them
+               while (node->plane)
                {
-                       // line crosses node plane, split the line
-                       midfrac = dist1 / (dist1 - dist2);
-                       VectorLerp(linestart, midfrac, lineend, mid);
-                       // take the near side first
-                       Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe);
-                       if (midfrac < trace->fraction)
-                               Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[endside], mid, end, midfrac, endfrac, linestart, lineend, markframe);
-                       return;
+                       // recurse down node sides
+                       dist1 = PlaneDiff(start, node->plane);
+                       dist2 = PlaneDiff(end, node->plane);
+                       startside = dist1 < 0;
+                       endside = dist2 < 0;
+                       if (startside == endside)
+                       {
+                               // most of the time the line fragment is on one side of the plane
+                               node = node->children[startside];
+                       }
+                       else
+                       {
+                               // line crosses node plane, split the line
+                               midfrac = dist1 / (dist1 - dist2);
+                               VectorLerp(start, midfrac, end, mid);
+                               // take the near side first
+                               Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
+                               if (midfrac <= trace->realfraction)
+                                       Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[endside], mid, end, midfrac, endfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
+                               return;
+                       }
                }
        }
        // hit a leaf
-       segmentmins[0] = min(start[0], end[0]);
-       segmentmins[1] = min(start[1], end[1]);
-       segmentmins[2] = min(start[2], end[2]);
-       segmentmaxs[0] = max(start[0], end[0]);
-       segmentmaxs[1] = max(start[1], end[1]);
-       segmentmaxs[2] = max(start[2], end[2]);
+       nodesegmentmins[0] = min(start[0], end[0]);
+       nodesegmentmins[1] = min(start[1], end[1]);
+       nodesegmentmins[2] = min(start[2], end[2]);
+       nodesegmentmaxs[0] = max(start[0], end[0]);
+       nodesegmentmaxs[1] = max(start[1], end[1]);
+       nodesegmentmaxs[2] = max(start[2], end[2]);
+       // line trace the brushes
        leaf = (q3mleaf_t *)node;
        for (i = 0;i < leaf->numleafbrushes;i++)
        {
-               if (startfrac >= trace->fraction)
-                       return;
                brush = leaf->firstleafbrush[i]->colbrushf;
-               if (brush && brush->markframe != markframe)
+               if (brush && brush->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, brush->mins, brush->maxs))
                {
                        brush->markframe = markframe;
-                       if (BoxesOverlap(segmentmins, segmentmaxs, brush->mins, brush->maxs))
-                               Collision_TraceLineBrushFloat(trace, linestart, lineend, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf);
+                       Collision_TraceLineBrushFloat(trace, linestart, lineend, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf);
+                       if (startfrac > trace->realfraction)
+                               return;
                }
        }
-       if (mod_q3bsp_curves_collisions.integer)
+       // can't do point traces on curves (they have no thickness)
+       if (mod_q3bsp_curves_collisions.integer && !VectorCompare(start, end))
        {
+               // line trace the curves
                for (i = 0;i < leaf->numleaffaces;i++)
                {
-                       if (startfrac >= trace->fraction)
-                               return;
                        face = leaf->firstleafface[i];
-                       if (face->collisions && face->collisionmarkframe != markframe)
+                       if (face->collisions && face->collisionmarkframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, face->mins, face->maxs))
                        {
                                face->collisionmarkframe = markframe;
-                               if (BoxesOverlap(segmentmins, segmentmaxs, face->mins, face->maxs))
-                                       Collision_TraceLineTriangleMeshFloat(trace, linestart, lineend, face->num_triangles, face->data_element3i, face->data_vertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
+                               Collision_TraceLineTriangleMeshFloat(trace, linestart, lineend, face->num_triangles, face->data_element3i, face->data_vertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
+                               if (startfrac > trace->realfraction)
+                                       return;
                        }
                }
        }
@@ -4604,78 +4652,295 @@ static void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, q3mnode_t *nod
        q3mleaf_t *leaf;
        colbrushf_t *brush;
        q3mface_t *face;
-       nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
-       nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
-       nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
-       nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
-       nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
-       nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
-       if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
-               return;
-       if (node->isnode)
-       {
-               // recurse down node sides
-               sides = BoxOnPlaneSide(segmentmins, segmentmaxs, node->plane);
-               if (sides == 3)
+       /*
+               // find which nodes the line is in and recurse for them
+               while (node->plane)
                {
-                       Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, nodesegmentmins, nodesegmentmaxs);
-                       Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[1], thisbrush_start, thisbrush_end, markframe, nodesegmentmins, nodesegmentmaxs);
+                       // recurse down node sides
+                       int startside, endside;
+                       float dist1near, dist1far, dist2near, dist2far;
+                       BoxPlaneCornerDistances(thisbrush_start->mins, thisbrush_start->maxs, node->plane, &dist1near, &dist1far);
+                       BoxPlaneCornerDistances(thisbrush_end->mins, thisbrush_end->maxs, node->plane, &dist2near, &dist2far);
+                       startside = dist1near < 0;
+                       startside = dist1near < 0 ? (dist1far < 0 ? 1 : 2) : (dist1far < 0 ? 2 : 0);
+                       endside = dist2near < 0 ? (dist2far < 0 ? 1 : 2) : (dist2far < 0 ? 2 : 0);
+                       if (startside == 2 || endside == 2)
+                       {
+                               // brushes cross plane
+                               // do not clip anything, just take both sides
+                               Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+                               node = node->children[1];
+                               continue;
+                       }
+                       if (startside == 0)
+                       {
+                               if (endside == 0)
+                               {
+                                       node = node->children[0];
+                                       continue;
+                               }
+                               else
+                               {
+                                       //midf0 = dist1near / (dist1near - dist2near);
+                                       //midf1 = dist1far / (dist1far - dist2far);
+                                       Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+                                       node = node->children[1];
+                                       continue;
+                               }
+                       }
+                       else
+                       {
+                               if (endside == 0)
+                               {
+                                       //midf0 = dist1near / (dist1near - dist2near);
+                                       //midf1 = dist1far / (dist1far - dist2far);
+                                       Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+                                       node = node->children[1];
+                                       continue;
+                               }
+                               else
+                               {
+                                       node = node->children[1];
+                                       continue;
+                               }
+                       }
+
+                       if (dist1near <  0 && dist2near <  0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
+                       if (dist1near <  0 && dist2near <  0 && dist1far <  0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
+                       if (dist1near <  0 && dist2near <  0 && dist1far >= 0 && dist2far <  0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
+                       if (dist1near <  0 && dist2near <  0 && dist1far >= 0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
+                       if (dist1near <  0 && dist2near >= 0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
+                       if (dist1near <  0 && dist2near >= 0 && dist1far <  0 && dist2far >= 0){}
+                       if (dist1near <  0 && dist2near >= 0 && dist1far >= 0 && dist2far <  0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
+                       if (dist1near <  0 && dist2near >= 0 && dist1far >= 0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
+                       if (dist1near >= 0 && dist2near <  0 && dist1far <  0 && dist2far <  0){node = node->children[1];continue;}
+                       if (dist1near >= 0 && dist2near <  0 && dist1far <  0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
+                       if (dist1near >= 0 && dist2near <  0 && dist1far >= 0 && dist2far <  0){}
+                       if (dist1near >= 0 && dist2near <  0 && dist1far >= 0 && dist2far >= 0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
+                       if (dist1near >= 0 && dist2near >= 0 && dist1far <  0 && dist2far <  0){Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);node = node->children[1];continue;}
+                       if (dist1near >= 0 && dist2near >= 0 && dist1far <  0 && dist2far >= 0){node = node->children[0];continue;}
+                       if (dist1near >= 0 && dist2near >= 0 && dist1far >= 0 && dist2far <  0){node = node->children[0];continue;}
+                       if (dist1near >= 0 && dist2near >= 0 && dist1far >= 0 && dist2far >= 0){node = node->children[0];continue;}
+                       {             
+                               if (dist2near < 0) // d1n<0 && d2n<0
+                               {
+                                       if (dist2near < 0) // d1n<0 && d2n<0
+                                       {
+                                               if (dist2near < 0) // d1n<0 && d2n<0
+                                               {
+                                               }
+                                               else // d1n<0 && d2n>0
+                                               {
+                                               }
+                                       }
+                                       else // d1n<0 && d2n>0
+                                       {
+                                               if (dist2near < 0) // d1n<0 && d2n<0
+                                               {
+                                               }
+                                               else // d1n<0 && d2n>0
+                                               {
+                                               }
+                                       }
+                               }
+                               else // d1n<0 && d2n>0
+                               {
+                               }
+                       }
+                       else // d1n>0
+                       {
+                               if (dist2near < 0) // d1n>0 && d2n<0
+                               {
+                               }
+                               else // d1n>0 && d2n>0
+                               {
+                               }
+                       }
+                       if (dist1near < 0 == dist1far < 0 == dist2near < 0 == dist2far < 0)
+                       {
+                               node = node->children[startside];
+                               continue;
+                       }
+                       if (dist1near < dist2near)
+                       {
+                               // out
+                               if (dist1near >= 0)
+                               {
+                                       node = node->children[0];
+                                       continue;
+                               }
+                               if (dist2far < 0)
+                               {
+                                       node = node->children[1];
+                                       continue;
+                               }
+                               // dist1near < 0 && dist2far >= 0
+                       }
+                       else
+                       {
+                               // in
+                       }
+                       startside = dist1near < 0 ? (dist1far < 0 ? 1 : 2) : (dist1far < 0 ? 2 : 0);
+                       endside = dist2near < 0 ? (dist2far < 0 ? 1 : 2) : (dist2far < 0 ? 2 : 0);
+                       if (startside == 2 || endside == 2)
+                       {
+                               // brushes cross plane
+                               // do not clip anything, just take both sides
+                               Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+                               node = node->children[1];
+                       }
+                       else if (startside == endside)
+                               node = node->children[startside];
+                       else if (startside == 0) // endside = 1 (start infront, end behind)
+                       {
+                       }
+                       else // startside == 1 endside = 0 (start behind, end infront)
+                       {
+                       }
+                       == endside)
+                       {
+                               if (startside < 2)
+                                       node = node->children[startside];
+                               else
+                               {
+                                       // start and end brush cross plane
+                               }
+                       }
+                       else
+                       {
+                       }
+                       if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
+                               node = node->children[1];
+                       else if (dist1near < 0 && dist1far < 0 && dist2near >= 0 && dist2far >= 0)
+                       else if (dist1near >= 0 && dist1far >= 0 && dist2near < 0 && dist2far < 0)
+                       else if (dist1near >= 0 && dist1far >= 0 && dist2near >= 0 && dist2far >= 0)
+                               node = node->children[0];
+                       else
+                       if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
+                       if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
+                       if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
+                       if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
+                       if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
+                       {
+                       }
+                       else if (dist1near >= 0 && dist1far >= 0)
+                       {
+                       }
+                       else // mixed (lying on plane)
+                       {
+                       }
+                       {
+                               if (dist2near < 0 && dist2far < 0)
+                               {
+                               }
+                               else
+                                       node = node->children[1];
+                       }
+                       if (dist1near < 0 && dist1far < 0 && dist2near < 0 && dist2far < 0)
+                               node = node->children[0];
+                       else if (dist1near >= 0 && dist1far >= 0 && dist2near >= 0 && dist2far >= 0)
+                               node = node->children[1];
+                       else
+                       {
+                               // both sides
+                               Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
+                               node = node->children[1];
+                       }
+                       sides = dist1near || dist1near < 0 | dist1far < 0 | dist2near < 0 | dist
+                       startside = dist1 < 0;
+                       endside = dist2 < 0;
+                       if (startside == endside)
+                       {
+                               // most of the time the line fragment is on one side of the plane
+                               node = node->children[startside];
+                       }
+                       else
+                       {
+                               // line crosses node plane, split the line
+                               midfrac = dist1 / (dist1 - dist2);
+                               VectorLerp(start, midfrac, end, mid);
+                               // take the near side first
+                               Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[startside], start, mid, startfrac, midfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
+                               if (midfrac <= trace->fraction)
+                                       Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, node->children[endside], mid, end, midfrac, endfrac, linestart, lineend, markframe, segmentmins, segmentmaxs);
+                               return;
+                       }
                }
-               else if (sides == 2)
-                       Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[1], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
-               else // sides == 1
+       */
+       // FIXME: could be made faster by copying TraceLine code and making it use
+       // box plane distances...  (variant on the BoxOnPlaneSide code)
+       for (;;)
+       {
+               nodesegmentmins[0] = max(segmentmins[0], node->mins[0]);
+               nodesegmentmins[1] = max(segmentmins[1], node->mins[1]);
+               nodesegmentmins[2] = max(segmentmins[2], node->mins[2]);
+               nodesegmentmaxs[0] = min(segmentmaxs[0], node->maxs[0]);
+               nodesegmentmaxs[1] = min(segmentmaxs[1], node->maxs[1]);
+               nodesegmentmaxs[2] = min(segmentmaxs[2], node->maxs[2]);
+               if (nodesegmentmins[0] > nodesegmentmaxs[0] || nodesegmentmins[1] > nodesegmentmaxs[1] || nodesegmentmins[2] > nodesegmentmaxs[2])
+                       return;
+               if (!node->plane)
+                       break;
+               if (mod_q3bsp_debugtracebrush.integer == 2)
+               {
                        Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
-               /*
-               dist = node->plane->dist - (1.0f / 8.0f);
-               for (i = 0, ps = thisbrush_start->points, pe = thisbrush_end->points;i < thisbrush_start->numpoints;i++, ps++, pe++)
+                       node = node->children[1];
+               }
+               else if (mod_q3bsp_debugtracebrush.integer == 1)
                {
-                       if (DotProduct(ps->v, node->plane->normal) >= dist || DotProduct(pe->v, node->plane->normal) >= dist)
+                       // recurse down node sides
+                       sides = BoxOnPlaneSide(segmentmins, segmentmaxs, node->plane);
+                       if (sides == 3)
                        {
-                               Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, nodesegmentmins, nodesegmentmaxs);
-                               break;
+                               // segment box crosses plane
+                               Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+                               node = node->children[1];
+                       }
+                       else
+                       {
+                               // take whichever side the segment box is on
+                               node = node->children[sides - 1];
                        }
                }
-               */
-               /*
-               dist = node->plane->dist + (1.0f / 8.0f);
-               for (i = 0, ps = thisbrush_start->points, pe = thisbrush_end->points;i < thisbrush_start->numpoints;i++, ps++, pe++)
+               else
                {
-                       if (DotProduct(ps->v, node->plane->normal) <= dist || DotProduct(pe->v, node->plane->normal) <= dist)
+                       // recurse down node sides
+                       sides = BoxOnPlaneSide(segmentmins, segmentmaxs, node->plane);
+                       if (sides == 3)
                        {
-                               Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[1], thisbrush_start, thisbrush_end, markframe, nodesegmentmins, nodesegmentmaxs);
-                               break;
+                               // segment box crosses plane
+                               // now check start and end brush boxes to handle a lot of 'diagonal' cases more efficiently...
+                               sides = BoxOnPlaneSide(thisbrush_start->mins, thisbrush_start->maxs, node->plane) | BoxOnPlaneSide(thisbrush_end->mins, thisbrush_end->maxs, node->plane);
+                               if (sides == 3)
+                               {
+                                       Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end, markframe, segmentmins, segmentmaxs);
+                                       sides = 2;
+                               }
                        }
+                       // take whichever side the segment box is on
+                       node = node->children[sides - 1];
                }
-               */
-               /*
-               sides = BoxOnPlaneSide(boxstartmins, boxstartmaxs, node->plane) | BoxOnPlaneSide(boxendmins, boxendmaxs, node->plane);
-               if (sides & 1)
-                       Mod_Q3BSP_TraceBox_RecursiveBSPNode(trace, node->children[0], boxstartmins, boxstartmaxs, boxendmins, boxendmaxs);
-               if (sides & 2)
-                       Mod_Q3BSP_TraceBox_RecursiveBSPNode(trace, node->children[1], boxstartmins, boxstartmaxs, boxendmins, boxendmaxs);
-               */
        }
-       else
+       // hit a leaf
+       leaf = (q3mleaf_t *)node;
+       for (i = 0;i < leaf->numleafbrushes;i++)
        {
-               // hit a leaf
-               leaf = (q3mleaf_t *)node;
-               for (i = 0;i < leaf->numleafbrushes;i++)
+               brush = leaf->firstleafbrush[i]->colbrushf;
+               if (brush && brush->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, brush->mins, brush->maxs))
                {
-                       brush = leaf->firstleafbrush[i]->colbrushf;
-                       if (brush && brush->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, brush->mins, brush->maxs))
-                       {
-                               brush->markframe = markframe;
-                               Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf);
-                       }
+                       brush->markframe = markframe;
+                       Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf);
                }
-               if (mod_q3bsp_curves_collisions.integer)
+       }
+       if (mod_q3bsp_curves_collisions.integer)
+       {
+               for (i = 0;i < leaf->numleaffaces;i++)
                {
-                       for (i = 0;i < leaf->numleaffaces;i++)
+                       face = leaf->firstleafface[i];
+                       if (face->collisions && face->markframe != markframe && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, face->mins, face->maxs))
                        {
-                               face = leaf->firstleafface[i];
-                               // note: this can not be optimized with a face->collisionmarkframe because each triangle of the face would need to be marked as done individually (because each one is bbox culled individually), and if all are marked, then the face could be marked as done
-                               if (face->collisions && BoxesOverlap(nodesegmentmins, nodesegmentmaxs, face->mins, face->maxs))
-                                       Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, face->num_triangles, face->data_element3i, face->data_vertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
+                               face->markframe = markframe;
+                               Collision_TraceBrushTriangleMeshFloat(trace, thisbrush_start, thisbrush_end, face->num_triangles, face->data_element3i, face->data_vertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
                        }
                }
        }
@@ -4691,6 +4956,7 @@ static void Mod_Q3BSP_TraceBox(model_t *model, int frame, trace_t *trace, const
        q3mface_t *face;
        memset(trace, 0, sizeof(*trace));
        trace->fraction = 1;
+       trace->realfraction = 1;
        trace->hitsupercontentsmask = hitsupercontentsmask;
        Matrix4x4_CreateIdentity(&startmatrix);
        Matrix4x4_CreateIdentity(&endmatrix);
@@ -4702,24 +4968,39 @@ static void Mod_Q3BSP_TraceBox(model_t *model, int frame, trace_t *trace, const
        segmentmaxs[2] = max(boxstartmaxs[2], boxendmaxs[2]);
        if (mod_q3bsp_optimizedtraceline.integer && VectorCompare(boxstartmins, boxstartmaxs) && VectorCompare(boxendmins, boxendmaxs))
        {
-               // line trace
-               if (model->brushq3.submodel)
+               if (VectorCompare(boxstartmins, boxendmins))
                {
-                       for (i = 0;i < model->brushq3.data_thismodel->numbrushes;i++)
-                               if (model->brushq3.data_thismodel->firstbrush[i].colbrushf)
-                                       Collision_TraceLineBrushFloat(trace, boxstartmins, boxendmins, model->brushq3.data_thismodel->firstbrush[i].colbrushf, model->brushq3.data_thismodel->firstbrush[i].colbrushf);
-                       if (mod_q3bsp_curves_collisions.integer)
+                       // point trace
+                       if (model->brushq3.submodel)
                        {
-                               for (i = 0;i < model->brushq3.data_thismodel->numfaces;i++)
+                               for (i = 0;i < model->brushq3.data_thismodel->numbrushes;i++)
+                                       if (model->brushq3.data_thismodel->firstbrush[i].colbrushf)
+                                               Collision_TracePointBrushFloat(trace, boxstartmins, model->brushq3.data_thismodel->firstbrush[i].colbrushf);
+                       }
+                       else
+                               Mod_Q3BSP_TracePoint_RecursiveBSPNode(trace, model->brushq3.data_nodes, boxstartmins, ++markframe);
+               }
+               else
+               {
+                       // line trace
+                       if (model->brushq3.submodel)
+                       {
+                               for (i = 0;i < model->brushq3.data_thismodel->numbrushes;i++)
+                                       if (model->brushq3.data_thismodel->firstbrush[i].colbrushf)
+                                               Collision_TraceLineBrushFloat(trace, boxstartmins, boxendmins, model->brushq3.data_thismodel->firstbrush[i].colbrushf, model->brushq3.data_thismodel->firstbrush[i].colbrushf);
+                               if (mod_q3bsp_curves_collisions.integer)
                                {
-                                       face = model->brushq3.data_thismodel->firstface + i;
-                                       if (face->collisions)
-                                               Collision_TraceLineTriangleMeshFloat(trace, boxstartmins, boxendmins, face->num_triangles, face->data_element3i, face->data_vertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
+                                       for (i = 0;i < model->brushq3.data_thismodel->numfaces;i++)
+                                       {
+                                               face = model->brushq3.data_thismodel->firstface + i;
+                                               if (face->collisions)
+                                                       Collision_TraceLineTriangleMeshFloat(trace, boxstartmins, boxendmins, face->num_triangles, face->data_element3i, face->data_vertex3f, face->texture->supercontents, segmentmins, segmentmaxs);
+                                       }
                                }
                        }
+                       else
+                               Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, model->brushq3.data_nodes, boxstartmins, boxendmins, 0, 1, boxstartmins, boxendmins, ++markframe, segmentmins, segmentmaxs);
                }
-               else
-                       Mod_Q3BSP_TraceLine_RecursiveBSPNode(trace, model->brushq3.data_nodes, boxstartmins, boxendmins, 0, 1, boxstartmins, boxendmins, ++markframe);
        }
        else
        {
@@ -4749,32 +5030,24 @@ static void Mod_Q3BSP_TraceBox(model_t *model, int frame, trace_t *trace, const
 
 static int Mod_Q3BSP_BoxTouchingPVS_RecursiveBSPNode(const model_t *model, const q3mnode_t *node, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
 {
-       int clusterindex;
-loc0:
-       if (!node->isnode)
+       int clusterindex, side;
+       while (node->plane)
        {
-               // leaf
-               clusterindex = ((q3mleaf_t *)node)->clusterindex;
-               return pvs[clusterindex >> 3] & (1 << (clusterindex & 7));
-       }
-
-       // node - recurse down the BSP tree
-       switch (BoxOnPlaneSide(mins, maxs, node->plane))
-       {
-       case 1: // front
-               node = node->children[0];
-               goto loc0;
-       case 2: // back
-               node = node->children[1];
-               goto loc0;
-       default: // crossing
-               if (Mod_Q3BSP_BoxTouchingPVS_RecursiveBSPNode(model, node->children[0], pvs, mins, maxs))
-                       return true;
-               node = node->children[1];
-               goto loc0;
+               // node - recurse down the BSP tree
+               side = BoxOnPlaneSide(mins, maxs, node->plane) - 1;
+               if (side < 2)
+                       node = node->children[side];
+               else
+               {
+                       // recurse for one child and loop for the other
+                       if (Mod_Q3BSP_BoxTouchingPVS_RecursiveBSPNode(model, node->children[0], pvs, mins, maxs))
+                               return true;
+                       node = node->children[1];
+               }
        }
-       // never reached
-       return false;
+       // leaf
+       clusterindex = ((q3mleaf_t *)node)->clusterindex;
+       return pvs[clusterindex >> 3] & (1 << (clusterindex & 7));
 }
 
 static int Mod_Q3BSP_BoxTouchingPVS(model_t *model, const qbyte *pvs, const vec3_t mins, const vec3_t maxs)
@@ -4789,7 +5062,7 @@ static qbyte *Mod_Q3BSP_GetPVS(model_t *model, const vec3_t p)
        q3mnode_t *node;
        Mod_CheckLoaded(model);
        node = model->brushq3.data_nodes;
-       while (node->isnode)
+       while (node->plane)
                node = node->children[(node->plane->type < 3 ? p[node->plane->type] : DotProduct(p,node->plane->normal)) < node->plane->dist];
        if (((q3mleaf_t *)node)->clusterindex >= 0)
                return model->brushq3.data_pvschains + ((q3mleaf_t *)node)->clusterindex * model->brushq3.num_pvschainlength;
@@ -4803,7 +5076,7 @@ static void Mod_Q3BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org,
        float d;
        qbyte *pvs;
 
-       while (node->isnode)
+       while (node->plane)
        {
                d = PlaneDiff(org, node->plane);
                if (d > radius)
@@ -4824,6 +5097,8 @@ static void Mod_Q3BSP_FatPVS_RecursiveBSPNode(model_t *model, const vec3_t org,
                for (i = 0;i < pvsbytes;i++)
                        pvsbuffer[i] |= pvs[i];
        }
+       else
+               memset(pvsbuffer, 0xFF, pvsbytes);
        return;
 }
 
@@ -4833,6 +5108,11 @@ static int Mod_Q3BSP_FatPVS(model_t *model, const vec3_t org, vec_t radius, qbyt
 {
        int bytes = model->brushq3.num_pvschainlength;
        bytes = min(bytes, pvsbufferlength);
+       if (r_novis.integer)
+       {
+               memset(pvsbuffer, 0xFF, bytes);
+               return bytes;
+       }
        memset(pvsbuffer, 0, bytes);
        Mod_Q3BSP_FatPVS_RecursiveBSPNode(model, org, radius, pvsbuffer, bytes, model->brushq3.data_nodes);
        return bytes;
index 4e02923..00a11b2 100644 (file)
@@ -344,12 +344,11 @@ q3mtexture_t;
 typedef struct q3mnode_s
 {
        //this part shared between node and leaf
-       int isnode; // true
+       struct mplane_s *plane; // != NULL
        struct q3mnode_s *parent;
        vec3_t mins;
        vec3_t maxs;
        // this part unique to nodes
-       struct mplane_s *plane;
        struct q3mnode_s *children[2];
 }
 q3mnode_t;
@@ -357,7 +356,7 @@ q3mnode_t;
 typedef struct q3mleaf_s
 {
        //this part shared between node and leaf
-       int isnode; // false
+       struct mplane_s *plane; // == NULL
        struct q3mnode_s *parent;
        vec3_t mins;
        vec3_t maxs;
diff --git a/todo b/todo
index 0dfb00f..617434b 100644 (file)
--- a/todo
+++ b/todo
 -n darkplaces: server is starting before the "port" cvar is set by commandline and scripts? (yummyluv)
 -n darkplaces: typing ip in join game menu should show 'trying' and 'no response' after a while, or 'no network' if networking is not initialized (yummyluv)
 -n dpmod: make grapple off-hand (joe hill)
+0 darkplaces: add lava-steam particle puff effect for bursting lava bubbles (Zombie) 
+0 darkplaces: remove the loop unrolling in Image_Resample32LerpLine and Image_Resample24LerpLine and related functions, as the loop is really too long to get much benefit, and it might even not fit in the L1 instruction cache on Pentium1 (fuh)
+0 darkplaces: make console editing allow cursoring left/right on the line and insert and delete, etc (Vic)
+0 darkplaces: make gl_texture_anisotropy take effect immediately rather than needing an r_restart (metlslime, zinx)
+2 darkplaces: fix 'fall to death in wedge corner' glitch from quake (Zombie)
+d darkplaces: add sv_freenonclients cvar (Vermeulen)
+5 darkplaces: add decals on models (Urre)
+d darkplaces: fix win32 bug where shift key types a character (Black, Sajt)
+2 darkplaces: add KDE/gnome icon somehow using a png version of the darkplaces.ico (de-we)
+2 darkplaces: add the darkplaces.ico to the executable during compilation, somehow, probably different for msvc and mingw (de-we)
+2 darkplaces: add fs_datapath and fs_userpath cvars to better support Linux, this can be done by making each gamedir add both the basepath and userpath variants of the gamedir, and making sure the userpath one is last so it is used for writing (Mercury)
+3 darkplaces: add fs_reload command to allow restarting the filesystem module, this would mean that it could check for new paks and such (Mercury)
+0 darkplaces: figure out what crashes when this sequence is done: r_speeds 1;map anything, crash (Stribbs)
+0 darkplaces: add vid_pixelaspect patch from Grisha Spivak's email
+0 darkplaces: upgrade punchangle protocol to 16bit angles for smoother motion (Urre)
+1 darkplaces: add md3 mesh name reporting to qc somehow when traceline does model tracing and hits the model
+d darkplaces: optimized ray-triangle collision code
+d darkplaces: don't crash if SOLID_BSP is used with modelindex 0 - TargetQuake does this...
+d darkplaces: reduce r_lightningbeam_repeatdistance to 128, 1024 is way too long
+d darkplaces: make most QC builtin give warnings instead of errors, so broken mods still run 
+-n darkplaces: fix vis decompression underrun/overrun warnings as the problem appears to be more visleafs than the data contains (Vic)
+d darkplaces: improve framerate limiting to sleep until next frame, instead of just sleeping a little 
+d darkplaces: fix the dedicated server timing, seems to be using host_maxfps instead of sys_ticrate
+d darkplaces: fix r_novis
+d darkplaces: figure out and fix vis problems when noclipping out of world in q1bsp and q3bsp
+d darkplaces: figure out and fix win32 networking problems
+2 darkplaces: make light checks use rtlights if in r_shadow_realtime_world 1 mode for consistency reasons on transparent models and such, as well as particles (romi)
+0 darkplaces: add back cl_particles_lighting cvar and add back the particle lighting (romi)
+5 darkplaces: lightshader files (probably loaded by the cubemap field already present in rtlights handling), these would indicate what attenuation textures to use for the light, what cubemap filter, whether to have a corona and so on (romi)
+1 darkplaces: shadow volumes from q3bsp brush models are broken, maybe inverted or something (Vermeulen)
+2 darkplaces: decal clipping (romi)
+7 darkplaces: shadow volume clipping (romi)
+0 dpmod: make run animation play back according to movement speed (along v_forward), instead of just playing a continuous loop based on time (Urre)
+1 darkplaces: q1bsp: parse submodels before leafs, so that the pvs can be allocated smaller (only enough for the world model's visleafs count) (Vic) 
+0 darkplaces: figure out the 'inverted bumps' bug on some texture orientations (see crate tops at end of e1m1, tenebrae1 does not suffer this problem somehow) (U8Poo) 
+0 darkplaces: fix the bug causing models in an unlit map to be black when they should be fullbright (Sajt)
 0 darkplaces: r_shadow_showtris messes up r_shadow_visiblevolumes color (jitspoe)
 0 darkplaces: make notify lines show based on cl.time, not realtime, so they last the proper length when using cl_avidemo (Urre)
 0 darkplaces: darkplaces is leaving a dead window button on the taskbar when closed?  this is odd as the window closing code in darkplaces is designed to prevent this (Urre)
@@ -324,7 +360,7 @@ d darkplaces: q1bsp trace bug: scrags frequently fly through ceilings - this nee
 d darkplaces: Quake3 bsp support (Vermeulen, Mitchell, SeienAbunae)
 7 darkplaces: add DP_ENT_DISTORTIONFIELD which visually pulls things inward/outward around an entity (Supajoe, SeienAbunae)
 7 darkplaces: add clientside quakec (KrimZon, FrikaC, SeienAbunae)
-7 darkplaces: figure out what is causing invalid entity numbers in TouchAreaGrid in world.c - suspicion: problem with reallocation of edicts?
+d darkplaces: figure out what is causing invalid entity numbers in TouchAreaGrid in world.c - suspicion: problem with reallocation of edicts?
 7 darkplaces: make it work on Savage4 again (Ender)
 7 darkplaces: mirrors (SeienAbunae)
 7 darkplaces: should add quake3 shader support even though the language is utterly insane
diff --git a/world.c b/world.c
index b337fe2..31fe0ae 100644 (file)
--- a/world.c
+++ b/world.c
@@ -460,23 +460,42 @@ trace_t SV_ClipMoveToEntity(edict_t *ent, const vec3_t start, const vec3_t mins,
        if ((int) ent->v->solid == SOLID_BSP || movetype == MOVE_HITMODEL)
        {
                i = ent->v->modelindex;
+               // if the modelindex is 0, it shouldn't be SOLID_BSP!
+               if (i == 0)
+               {
+                       Con_Printf("SV_ClipMoveToEntity: edict %i: SOLID_BSP with no model\n", NUM_FOR_EDICT(ent));
+                       memset(&trace, 0, sizeof(trace));
+                       return trace;
+               }
                if ((unsigned int) i >= MAX_MODELS)
-                       Host_Error("SV_ClipMoveToEntity: invalid modelindex\n");
+               {
+                       Con_Printf("SV_ClipMoveToEntity: edict %i: SOLID_BSP with invalid modelindex\n", NUM_FOR_EDICT(ent));
+                       memset(&trace, 0, sizeof(trace));
+                       return trace;
+               }
                model = sv.models[i];
                if (i != 0 && model == NULL)
-                       Host_Error("SV_ClipMoveToEntity: invalid modelindex\n");
+               {
+                       Con_Printf("SV_ClipMoveToEntity: edict %i: SOLID_BSP with invalid modelindex\n", NUM_FOR_EDICT(ent));
+                       memset(&trace, 0, sizeof(trace));
+                       return trace;
+               }
 
                Mod_CheckLoaded(model);
                if ((int) ent->v->solid == SOLID_BSP)
                {
                        if (!model->TraceBox)
                        {
-                               Con_Printf("SV_ClipMoveToEntity: SOLID_BSP with a non-collidable model, entity dump:\n");
-                               ED_Print(ent);
-                               Host_Error("SV_ClipMoveToEntity: SOLID_BSP with a non-collidable model\n");
+                               Con_Printf("SV_ClipMoveToEntity: edict %i: SOLID_BSP with a non-collidable model\n", NUM_FOR_EDICT(ent));
+                               memset(&trace, 0, sizeof(trace));
+                               return trace;
                        }
                        if (ent->v->movetype != MOVETYPE_PUSH)
-                               Host_Error("SV_ClipMoveToEntity: SOLID_BSP without MOVETYPE_PUSH");
+                       {
+                               Con_Printf("SV_ClipMoveToEntity: edict %i: SOLID_BSP without MOVETYPE_PUSH\n", NUM_FOR_EDICT(ent));
+                               memset(&trace, 0, sizeof(trace));
+                               return trace;
+                       }
                }
                Matrix4x4_CreateFromQuakeEntity(&matrix, ent->v->origin[0], ent->v->origin[1], ent->v->origin[2], ent->v->angles[0], ent->v->angles[1], ent->v->angles[2], 1);
        }
@@ -586,16 +605,17 @@ void SV_ClipToNode(moveclip_t *clip, link_t *list)
                if (trace.startsolid)
                {
                        clip->trace.startsolid = true;
-                       if (clip->trace.fraction == 1)
+                       if (clip->trace.realfraction == 1)
                                clip->trace.ent = touch;
                }
                if (trace.inopen)
                        clip->trace.inopen = true;
                if (trace.inwater)
                        clip->trace.inwater = true;
-               if (trace.fraction < clip->trace.fraction)
+               if (trace.realfraction < clip->trace.realfraction)
                {
                        clip->trace.fraction = trace.fraction;
+                       clip->trace.realfraction = trace.realfraction;
                        VectorCopy(trace.endpos, clip->trace.endpos);
                        clip->trace.plane = trace.plane;
                        clip->trace.ent = touch;