X-Git-Url: https://git.xonotic.org/?a=blobdiff_plain;f=collision.c;h=c41a2ff417246121e5b7e71e3d6cd741a9ceb43f;hb=b3e8885515ca1f52e46be713d16da7106ca93da7;hp=120809642e03ec90c96e75db75b27401c8107114;hpb=5b7ad43049de22dd99890c2f449ea0c096da75e0;p=xonotic%2Fdarkplaces.git diff --git a/collision.c b/collision.c index 12080964..c41a2ff4 100644 --- a/collision.c +++ b/collision.c @@ -109,6 +109,8 @@ void Collision_ValidateBrush(colbrushf_t *brush) float nearestplanedist_float(const float *normal, const colpointf_t *points, int numpoints) { float dist, bestdist; + if (!numpoints) + return 0; bestdist = DotProduct(points->v, normal); points++; while(--numpoints) @@ -123,6 +125,8 @@ float nearestplanedist_float(const float *normal, const colpointf_t *points, int float furthestplanedist_float(const float *normal, const colpointf_t *points, int numpoints) { float dist, bestdist; + if (!numpoints) + return 0; bestdist = DotProduct(points->v, normal); points++; while(--numpoints) @@ -138,7 +142,7 @@ float furthestplanedist_float(const float *normal, const colpointf_t *points, in colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const colplanef_t *originalplanes, int supercontents) { // TODO: planesbuf could be replaced by a remapping table - int j, k, m, w; + int j, k, m, w, xyzflags; int numpointsbuf = 0, maxpointsbuf = 256, numplanesbuf = 0, maxplanesbuf = 256, numelementsbuf = 0, maxelementsbuf = 256; double maxdist; colbrushf_t *brush; @@ -160,9 +164,9 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla // figure out how large a bounding box we need to properly compute this brush maxdist = 0; for (j = 0;j < numoriginalplanes;j++) - maxdist = max(maxdist, originalplanes[j].dist); + maxdist = max(maxdist, fabs(originalplanes[j].dist)); // now make it large enough to enclose the entire brush, and round it off to a reasonable multiple of 1024 - maxdist = floor(maxdist * (4.0 / 1024.0) + 1) * 1024.0; + maxdist = floor(maxdist * (4.0 / 1024.0) + 2) * 1024.0; // 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) @@ -178,16 +182,23 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla // check if there are too many and skip the brush if (numplanesbuf >= maxplanesbuf) { - Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many planes for buffer\n"); + Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many planes for buffer\n"); return NULL; } + // add the new plane + VectorCopy(originalplanes[j].normal, planesbuf[numplanesbuf].normal); + planesbuf[numplanesbuf].dist = originalplanes[j].dist; + planesbuf[numplanesbuf].q3surfaceflags = originalplanes[j].q3surfaceflags; + planesbuf[numplanesbuf].texture = originalplanes[j].texture; + numplanesbuf++; + // create a large polygon from the plane w = 0; PolygonD_QuadForPlane(p[w], originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist, maxdist); pnumpoints = 4; // clip it by all other planes - for (k = 0;k < numoriginalplanes && pnumpoints && pnumpoints <= pmaxpoints;k++) + for (k = 0;k < numoriginalplanes && pnumpoints >= 3 && pnumpoints <= pmaxpoints;k++) { // skip the plane this polygon // (nothing happens if it is processed, this is just an optimization) @@ -199,10 +210,11 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla w = !w; } } + // if nothing is left, skip it if (pnumpoints < 3) { - //Con_Printf("Collision_NewBrushFromPlanes: warning: polygon for plane %f %f %f %f clipped away\n", originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist); + //Con_DPrintf("Collision_NewBrushFromPlanes: warning: polygon for plane %f %f %f %f clipped away\n", originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist); continue; } @@ -218,29 +230,33 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla } if (k < pnumpoints) { - Con_Printf("Collision_NewBrushFromPlanes: warning: polygon point does not lie on at least 3 planes\n"); + Con_DPrintf("Collision_NewBrushFromPlanes: warning: polygon point does not lie on at least 3 planes\n"); //return NULL; } // check if there are too many polygon vertices for buffer if (pnumpoints > pmaxpoints) { - Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n"); + Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n"); return NULL; } // check if there are too many triangle elements for buffer if (numelementsbuf + (pnumpoints - 2) * 3 > maxelementsbuf) { - Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many triangle elements for buffer\n"); + Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many triangle elements for buffer\n"); return NULL; } for (k = 0;k < pnumpoints;k++) { + float v[3]; + // downgrade to float precision before comparing + VectorCopy(&p[w][k*3], v); + // check if there is already a matching point (no duplicates) for (m = 0;m < numpointsbuf;m++) - if (VectorDistance2(&p[w][k*3], pointsbuf[m].v) < COLLISION_SNAP2) + if (VectorDistance2(v, pointsbuf[m].v) < COLLISION_SNAP2) break; // if there is no match, add a new one @@ -249,7 +265,7 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla // check if there are too many and skip the brush if (numpointsbuf >= maxpointsbuf) { - Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n"); + Con_DPrint("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n"); return NULL; } // add the new one @@ -269,28 +285,25 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla elementsbuf[numelementsbuf++] = polypointbuf[k + 1]; elementsbuf[numelementsbuf++] = polypointbuf[k + 2]; } + } - // add the new plane - VectorCopy(originalplanes[j].normal, planesbuf[numplanesbuf].normal); - planesbuf[numplanesbuf].dist = originalplanes[j].dist; - planesbuf[numplanesbuf].q3surfaceflags = originalplanes[j].q3surfaceflags; - planesbuf[numplanesbuf].texture = originalplanes[j].texture; - numplanesbuf++; + // if nothing is left, there's nothing to allocate + if (numplanesbuf < 4) + { + Con_DPrintf("Collision_NewBrushFromPlanes: failed to build collision brush: %i triangles, %i planes (input was %i planes), %i vertices\n", numelementsbuf / 3, numplanesbuf, numoriginalplanes, numpointsbuf); + return NULL; } + // if no triangles or points could be constructed, then this routine failed but the brush is not discarded + if (numelementsbuf < 12 || numpointsbuf < 4) + Con_DPrintf("Collision_NewBrushFromPlanes: unable to rebuild triangles/points for collision brush: %i triangles, %i planes (input was %i planes), %i vertices\n", numelementsbuf / 3, numplanesbuf, numoriginalplanes, numpointsbuf); + // validate plane distances for (j = 0;j < numplanesbuf;j++) { float d = furthestplanedist_float(planesbuf[j].normal, pointsbuf, numpointsbuf); if (fabs(planesbuf[j].dist - d) > COLLISION_PLANE_DIST_EPSILON) - Con_Printf("plane %f %f %f %f mismatches dist %f\n", planesbuf[j].normal[0], planesbuf[j].normal[1], planesbuf[j].normal[2], planesbuf[j].dist, d); - } - - // if nothing is left, there's nothing to allocate - if (numelementsbuf < 12 || numplanesbuf < 4 || numpointsbuf < 4) - { - Con_Printf("Collision_NewBrushFromPlanes: failed to build collision brush: %i triangles, %i planes (input was %i planes), %i vertices\n", numelementsbuf / 3, numplanesbuf, numoriginalplanes, numpointsbuf); - return NULL; + Con_DPrintf("plane %f %f %f %f mismatches dist %f\n", planesbuf[j].normal[0], planesbuf[j].normal[1], planesbuf[j].normal[2], planesbuf[j].dist, d); } // allocate the brush and copy to it @@ -319,16 +332,34 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla } for (j = 0;j < brush->numtriangles * 3;j++) brush->elements[j] = elementsbuf[j]; - VectorCopy(brush->points[0].v, brush->mins); - VectorCopy(brush->points[0].v, brush->maxs); - for (j = 1;j < brush->numpoints;j++) + + xyzflags = 0; + VectorClear(brush->mins); + VectorClear(brush->maxs); + for (j = 0;j < min(6, numoriginalplanes);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]); + if (originalplanes[j].normal[0] == 1) {xyzflags |= 1;brush->maxs[0] = originalplanes[j].dist;} + else if (originalplanes[j].normal[0] == -1) {xyzflags |= 2;brush->mins[0] = -originalplanes[j].dist;} + else if (originalplanes[j].normal[1] == 1) {xyzflags |= 4;brush->maxs[1] = originalplanes[j].dist;} + else if (originalplanes[j].normal[1] == -1) {xyzflags |= 8;brush->mins[1] = -originalplanes[j].dist;} + else if (originalplanes[j].normal[2] == 1) {xyzflags |= 16;brush->maxs[2] = originalplanes[j].dist;} + else if (originalplanes[j].normal[2] == -1) {xyzflags |= 32;brush->mins[2] = -originalplanes[j].dist;} + } + // if not all xyzflags were set, then this is not a brush from q3map/q3map2, and needs reconstruction of the bounding box + // (this case works for any brush with valid points, but sometimes brushes are not reconstructed properly and hence the points are not valid, so this is reserved as a fallback case) + if (xyzflags != 63) + { + 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]); + } } brush->mins[0] -= 1; brush->mins[1] -= 1; @@ -527,7 +558,7 @@ colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, i // NOTE: start and end of each brush pair must have same numplanes/numpoints 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 = true, fendsolid = true, brushsolid, hitq3surfaceflags = 0; + int nplane, nplane2, hitq3surfaceflags = 0; float enterfrac = -1, leavefrac = 1, d1, d2, f, imove, newimpactnormal[3], enterfrac2 = -1; const colplanef_t *startplane, *endplane; texture_t *hittexture = NULL; @@ -578,20 +609,31 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush } //Con_Printf("%c%i: d1 = %f, d2 = %f, d1 / (d1 - d2) = %f\n", nplane2 != nplane ? 'b' : 'a', nplane2, d1, d2, d1 / (d1 - d2)); - if(d1 > d2) + if (d1 > d2) { // moving into brush - if(d2 > 0) + if (d2 > 0) return; - if(d1 > 0) + if (d1 > 0) { // enter - fstartsolid = false; imove = 1 / (d1 - d2); f = (d1 - collision_enternudge.value) * imove; + // check if this will reduce the collision time range if (enterfrac < f) { + // reduced collision time range enterfrac = f; + // if the collision time range is now empty, no collision + if (enterfrac > leavefrac) + return; + // if the collision would be further away than the trace's + // existing collision data, we don't care about this + // collision + if (enterfrac > trace->realfraction) + return; + // calculate the nudged fraction and impact normal we'll + // need if we accept this collision later enterfrac2 = f - collision_impactnudge.value * imove; VectorLerp(startplane->normal, enterfrac, endplane->normal, newimpactnormal); hitq3surfaceflags = startplane->q3surfaceflags; @@ -602,77 +644,58 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush else { // moving out of brush - if(d1 > 0) + if (d1 > 0) return; - if(d2 > 0) + if (d2 > 0) { // leave - fendsolid = false; f = (d1 + collision_leavenudge.value) / (d1 - d2); + // check if this will reduce the collision time range if (leavefrac > f) + { + // reduced collision time range leavefrac = f; + // if the collision time range is now empty, no collision + if (enterfrac > leavefrac) + return; + } } } } - brushsolid = trace->hitsupercontentsmask & thatbrush_start->supercontents; - if (fstartsolid) + // at this point we know the trace overlaps the brush because it was not + // rejected at any point in the loop above + + // see if this brush can block the trace or not according to contents + if (trace->hitsupercontentsmask & thatbrush_start->supercontents) { - trace->startsupercontents |= thatbrush_start->supercontents; - if (brushsolid) + if (enterfrac == -1) { + trace->startsupercontents |= thatbrush_start->supercontents; trace->startsolid = true; - if (fendsolid) + if (leavefrac < 1) trace->allsolid = true; } + // store out the impact information + trace->hitsupercontents = thatbrush_start->supercontents; + trace->hitq3surfaceflags = hitq3surfaceflags; + trace->hittexture = hittexture; + trace->realfraction = bound(0, enterfrac, 1); + trace->fraction = bound(0, enterfrac2, 1); + VectorCopy(newimpactnormal, trace->plane.normal); } - - // LordHavoc: we need an epsilon nudge here because for a point trace the - // 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->realfraction && enterfrac - (1.0f / 1024.0f) <= leavefrac) + else { -#if 0 - // broken - if (thatbrush_start->ispolygon) - { - d1 = nearestplanedist_float(thatbrush_start->planes[0].normal, thisbrush_start->points, thisbrush_start->numpoints) - thatbrush_start->planes[0].dist - collision_startnudge.value; - d2 = nearestplanedist_float(thatbrush_end->planes[0].normal, thisbrush_end->points, thisbrush_end->numpoints) - thatbrush_end->planes[0].dist - collision_endnudge.value; - move = d1 - d2; - if (move <= 0 || d2 > collision_enternudge.value || d1 < 0) - return; - // enter - imove = 1 / move; - enterfrac = (d1 - collision_enternudge.value) * imove; - if (enterfrac < trace->realfraction) - { - enterfrac2 = enterfrac - collision_impactnudge.value * imove; - trace->hitsupercontents = thatbrush_start->supercontents; - trace->hitq3surfaceflags = thatbrush_start->planes[0].q3surfaceflags; - trace->hittexture = thatbrush_start->planes[0].texture; - trace->realfraction = bound(0, enterfrac, 1); - trace->fraction = bound(0, enterfrac2, 1); - VectorLerp(thatbrush_start->planes[0].normal, enterfrac, thatbrush_end->planes[0].normal, trace->plane.normal); - } - } - else -#endif - { - trace->hitsupercontents = thatbrush_start->supercontents; - trace->hitq3surfaceflags = hitq3surfaceflags; - trace->hittexture = hittexture; - trace->realfraction = bound(0, enterfrac, 1); - trace->fraction = bound(0, enterfrac2, 1); - VectorCopy(newimpactnormal, trace->plane.normal); - } + // this brush can not block the trace, but it can update start contents + if (enterfrac == -1) + trace->startsupercontents |= thatbrush_start->supercontents; } } // NOTE: start and end brush pair must have same numplanes/numpoints 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 = true, fendsolid = true, brushsolid, hitq3surfaceflags = 0; + int nplane, hitq3surfaceflags = 0; float enterfrac = -1, leavefrac = 1, d1, d2, f, imove, newimpactnormal[3], enterfrac2 = -1; const colplanef_t *startplane, *endplane; texture_t *hittexture = NULL; @@ -709,12 +732,23 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const if (d1 > 0) { // enter - fstartsolid = false; imove = 1 / (d1 - d2); f = (d1 - collision_enternudge.value) * imove; + // check if this will reduce the collision time range if (enterfrac < f) { + // reduced collision time range enterfrac = f; + // if the collision time range is now empty, no collision + if (enterfrac > leavefrac) + return; + // if the collision would be further away than the trace's + // existing collision data, we don't care about this + // collision + if (enterfrac > trace->realfraction) + return; + // calculate the nudged fraction and impact normal we'll + // need if we accept this collision later enterfrac2 = f - collision_impactnudge.value * imove; VectorLerp(startplane->normal, enterfrac, endplane->normal, newimpactnormal); hitq3surfaceflags = startplane->q3surfaceflags; @@ -730,65 +764,46 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const if (d2 > 0) { // leave - fendsolid = false; f = (d1 + collision_leavenudge.value) / (d1 - d2); + // check if this will reduce the collision time range if (leavefrac > f) + { + // reduced collision time range leavefrac = f; + // if the collision time range is now empty, no collision + if (enterfrac > leavefrac) + return; + } } } } - brushsolid = trace->hitsupercontentsmask & thatbrush_start->supercontents; - if (fstartsolid) + // at this point we know the trace overlaps the brush because it was not + // rejected at any point in the loop above + + // see if this brush can block the trace or not according to contents + if (trace->hitsupercontentsmask & thatbrush_start->supercontents) { - trace->startsupercontents |= thatbrush_start->supercontents; - if (brushsolid) + if (enterfrac == -1) { + trace->startsupercontents |= thatbrush_start->supercontents; trace->startsolid = true; - if (fendsolid) + if (leavefrac < 1) trace->allsolid = true; } + // store out the impact information + trace->hitsupercontents = thatbrush_start->supercontents; + trace->hitq3surfaceflags = hitq3surfaceflags; + trace->hittexture = hittexture; + trace->realfraction = bound(0, enterfrac, 1); + trace->fraction = bound(0, enterfrac2, 1); + VectorCopy(newimpactnormal, trace->plane.normal); } - - // LordHavoc: we need an epsilon nudge here because for a point trace the - // 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->realfraction && enterfrac <= leavefrac) + else { -#if 0 - // broken - if (thatbrush_start->ispolygon) - { - d1 = DotProduct(thatbrush_start->planes[0].normal, linestart) - thatbrush_start->planes[0].dist - collision_startnudge.value; - d2 = DotProduct(thatbrush_end->planes[0].normal, lineend) - thatbrush_end->planes[0].dist - collision_endnudge.value; - move = d1 - d2; - if (move <= 0 || d2 > collision_enternudge.value || d1 < 0) - return; - // enter - imove = 1 / move; - enterfrac = (d1 - collision_enternudge.value) * imove; - if (enterfrac < trace->realfraction) - { - enterfrac2 = enterfrac - collision_impactnudge.value * imove; - trace->hitsupercontents = thatbrush_start->supercontents; - trace->hitq3surfaceflags = hitq3surfaceflags; - trace->hittexture = hittexture; - trace->realfraction = bound(0, enterfrac, 1); - trace->fraction = bound(0, enterfrac2, 1); - VectorLerp(thatbrush_start->planes[0].normal, enterfrac, thatbrush_end->planes[0].normal, trace->plane.normal); - } - } - else -#endif - { - trace->hitsupercontents = thatbrush_start->supercontents; - trace->hitq3surfaceflags = hitq3surfaceflags; - trace->hittexture = hittexture; - trace->realfraction = bound(0, enterfrac, 1); - trace->fraction = bound(0, enterfrac2, 1); - VectorCopy(newimpactnormal, trace->plane.normal); - } + // this brush can not block the trace, but it can update start contents + if (enterfrac == -1) + trace->startsupercontents |= thatbrush_start->supercontents; } }