X-Git-Url: http://de.git.xonotic.org/?a=blobdiff_plain;f=collision.c;h=7387a9e597a73f178aa57c4501b1562751022e7e;hb=8e199f361385dcd993117e6fb3b4e4fea0b22182;hp=1c4a4fe6b323149fe10be628f71c5b312c99c416;hpb=0db6270f9fdf1da680391fe0389d7ad6cfc48517;p=xonotic%2Fdarkplaces.git diff --git a/collision.c b/collision.c index 1c4a4fe6..7387a9e5 100644 --- a/collision.c +++ b/collision.c @@ -1,7 +1,17 @@ #include "quakedef.h" -#include "winding.h" +#include "polygon.h" +#define COLLISION_SNAPSCALE (32.0f) +#define COLLISION_SNAP (1.0f / COLLISION_SNAPSCALE) + +cvar_t collision_impactnudge = {0, "collision_impactnudge", "0.03125"}; +cvar_t collision_startnudge = {0, "collision_startnudge", "0"}; +cvar_t collision_endnudge = {0, "collision_endnudge", "0"}; +cvar_t collision_enternudge = {0, "collision_enternudge", "0"}; +cvar_t collision_leavenudge = {0, "collision_leavenudge", "0"}; + +#if 0 typedef struct { // the hull we're tracing through @@ -22,9 +32,6 @@ typedef struct } RecursiveHullCheckTraceInfo_t; -// 1/32 epsilon to keep floating point happy -#define DIST_EPSILON (0.03125) - #define HULLCHECKSTATE_EMPTY 0 #define HULLCHECKSTATE_SOLID 1 #define HULLCHECKSTATE_DONE 2 @@ -48,26 +55,32 @@ loc0: // check for empty if (num < 0) { - // translate the fake CONTENTS values in the box bsp tree - if (num == CONTENTS_SOLID) - num = t->boxsupercontents; - else - num = 0; + num = Mod_Q1BSP_SuperContentsFromNativeContents(NULL, num); if (!t->trace->startfound) { t->trace->startfound = true; t->trace->startsupercontents |= num; } + if (num & SUPERCONTENTS_LIQUIDSMASK) + t->trace->inwater = true; + if (num == 0) + t->trace->inopen = true; if (num & t->trace->hitsupercontentsmask) { // if the first leaf is solid, set startsolid if (t->trace->allsolid) t->trace->startsolid = true; +#if COLLISIONPARANOID >= 3 + Con_Print("S"); +#endif return HULLCHECKSTATE_SOLID; } else { t->trace->allsolid = false; +#if COLLISIONPARANOID >= 3 + Con_Print("E"); +#endif return HULLCHECKSTATE_EMPTY; } } @@ -91,6 +104,9 @@ loc0: { if (t2 < 0) { +#if COLLISIONPARANOID >= 3 + Con_Print("<"); +#endif num = node->children[1]; goto loc0; } @@ -100,6 +116,9 @@ loc0: { if (t2 >= 0) { +#if COLLISIONPARANOID >= 3 + Con_Print(">"); +#endif num = node->children[0]; goto loc0; } @@ -108,6 +127,9 @@ loc0: // the line intersects, find intersection point // LordHavoc: this uses the original trace for maximum accuracy +#if COLLISIONPARANOID >= 3 + Con_Print("M"); +#endif if (plane->type < 3) { t1 = t->start[plane->type] - plane->dist; @@ -146,15 +168,19 @@ 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 - collision_startnudge.value; + t2 = DotProduct(t->trace->plane.normal, t->end) - t->trace->plane.dist - collision_endnudge.value; midf = t1 / (t1 - t2); - t->trace->fraction = bound(0.0f, midf, 1.0); + t->trace->realfraction = bound(0, midf, 1); - VectorMA(t->start, t->trace->fraction, t->dist, t->trace->endpos); + // calculate the return fraction which is nudged off the surface a bit + midf = (t1 - collision_impactnudge.value) / (t1 - t2); + t->trace->fraction = bound(0, midf, 1); +#if COLLISIONPARANOID >= 3 + Con_Print("D"); +#endif return HULLCHECKSTATE_DONE; } @@ -203,7 +229,7 @@ static hull_t box_hull; static dclipnode_t box_clipnodes[6]; static mplane_t box_planes[6]; -void Collision_Init (void) +void Mod_Q1BSP_Collision_Init (void) { int i; int side; @@ -254,13 +280,26 @@ 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); - RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end); + Mod_Q1BSP_RecursiveHullCheck(&rhc, rhc.hull->firstclipnode, 0, 1, rhc.start, rhc.end); + VectorMA(rhc.start, rhc.trace->fraction, rhc.dist, rhc.trace->endpos); + if (rhc.trace->startsupercontents) + rhc.trace->startsupercontents = boxsupercontents; } +#endif +void Collision_Init (void) +{ + Cvar_RegisterVariable(&collision_impactnudge); + Cvar_RegisterVariable(&collision_startnudge); + Cvar_RegisterVariable(&collision_endnudge); + Cvar_RegisterVariable(&collision_enternudge); + Cvar_RegisterVariable(&collision_leavenudge); +} @@ -289,30 +328,33 @@ void Collision_PrintBrushAsQHull(colbrushf_t *brush, const char *name) void Collision_ValidateBrush(colbrushf_t *brush) { - int j, k, pointsoffplanes, printbrush; + int j, k, pointsoffplanes, pointonplanes, pointswithinsufficientplanes, printbrush; float d; printbrush = false; if (!brush->numpoints) { - Con_Printf("Collision_ValidateBrush: brush with no points!\n"); + Con_Print("Collision_ValidateBrush: brush with no points!\n"); printbrush = true; } #if 0 // it's ok for a brush to have one point and no planes... if (brush->numplanes == 0 && brush->numpoints != 1) { - Con_Printf("Collision_ValidateBrush: brush with no planes and more than one point!\n"); + Con_Print("Collision_ValidateBrush: brush with no planes and more than one point!\n"); printbrush = true; } #endif if (brush->numplanes) { pointsoffplanes = 0; + pointswithinsufficientplanes = 0; for (k = 0;k < brush->numplanes;k++) - { if (DotProduct(brush->planes[k].normal, brush->planes[k].normal) < 0.0001f) Con_Printf("Collision_ValidateBrush: plane #%i (%f %f %f %f) is degenerate\n", k, brush->planes[k].normal[0], brush->planes[k].normal[1], brush->planes[k].normal[2], brush->planes[k].dist); - for (j = 0;j < brush->numpoints;j++) + for (j = 0;j < brush->numpoints;j++) + { + pointonplanes = 0; + for (k = 0;k < brush->numplanes;k++) { d = DotProduct(brush->points[j].v, brush->planes[k].normal) - brush->planes[k].dist; if (d > (1.0f / 8.0f)) @@ -320,13 +362,22 @@ void Collision_ValidateBrush(colbrushf_t *brush) Con_Printf("Collision_ValidateBrush: point #%i (%f %f %f) infront of plane #%i (%f %f %f %f)\n", j, brush->points[j].v[0], brush->points[j].v[1], brush->points[j].v[2], k, brush->planes[k].normal[0], brush->planes[k].normal[1], brush->planes[k].normal[2], brush->planes[k].dist); printbrush = true; } - if (fabs(d) > 0.01f) + if (fabs(d) > 0.125f) pointsoffplanes++; + else + pointonplanes++; } + if (pointonplanes < 3) + pointswithinsufficientplanes++; + } + if (pointswithinsufficientplanes) + { + Con_Print("Collision_ValidateBrush: some points have insufficient planes, every point must be on at least 3 planes to form a corner.\n"); + printbrush = true; } if (pointsoffplanes == 0) // all points are on all planes { - Con_Printf("Collision_ValidateBrush: all points lie on all planes (degenerate, no brush volume!)\n"); + Con_Print("Collision_ValidateBrush: all points lie on all planes (degenerate, no brush volume!)\n"); printbrush = true; } } @@ -365,146 +416,184 @@ float furthestplanedist_float(const float *normal, const colpointf_t *points, in colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const mplane_t *originalplanes, int supercontents) { - int j, k, m; - int numpoints, maxpoints, numplanes, maxplanes, numelements, maxelements, numtriangles, numpolypoints, maxpolypoints; - winding_t *w; + int j, k, m, w; + int numpointsbuf = 0, maxpointsbuf = 256, numplanesbuf = 0, maxplanesbuf = 256, numelementsbuf = 0, maxelementsbuf = 256; colbrushf_t *brush; colpointf_t pointsbuf[256]; colplanef_t planesbuf[256]; int elementsbuf[1024]; int polypointbuf[256]; - float mins[3], maxs[3]; + int pmaxpoints = 64; + int pnumpoints; + double p[2][3*64]; +#if 0 + // enable these if debugging to avoid seeing garbage in unused data + memset(pointsbuf, 0, sizeof(pointsbuf)); + memset(planesbuf, 0, sizeof(planesbuf)); + memset(elementsbuf, 0, sizeof(elementsbuf)); + memset(polypointbuf, 0, sizeof(polypointbuf)); + memset(p, 0, sizeof(p)); +#endif // 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) - numpoints = 0;maxpoints = 256; - numplanes = 0;maxplanes = 256; - numelements = 0;maxelements = 1024; - numtriangles = 0; - maxpolypoints = 256; for (j = 0;j < numoriginalplanes;j++) { // add the plane uniquely (no duplicates) - for (k = 0;k < numplanes;k++) + for (k = 0;k < numplanesbuf;k++) if (VectorCompare(planesbuf[k].normal, originalplanes[j].normal) && planesbuf[k].dist == originalplanes[j].dist) break; // if the plane is a duplicate, skip it - if (k < numplanes) + if (k < numplanesbuf) continue; // check if there are too many and skip the brush - if (numplanes >= 256) + if (numplanesbuf >= maxplanesbuf) { - Con_Printf("Mod_Q3BSP_LoadBrushes: failed to build collision brush: too many planes for buffer\n"); + Con_Print("Mod_Q3BSP_LoadBrushes: failed to build collision brush: too many planes for buffer\n"); return NULL; } // create a large polygon from the plane - w = Winding_NewFromPlane(originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist); + w = 0; + PolygonD_QuadForPlane(p[w], originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist, 1024.0*1024.0*1024.0); + pnumpoints = 4; // clip it by all other planes - for (k = 0;k < numoriginalplanes && w;k++) + for (k = 0;k < numoriginalplanes && pnumpoints && pnumpoints <= pmaxpoints;k++) { if (k != j) { // we want to keep the inside of the brush plane so we flip // the cutting plane - w = Winding_Clip(w, -originalplanes[k].normal[0], -originalplanes[k].normal[1], -originalplanes[k].normal[2], -originalplanes[k].dist, true); + PolygonD_Divide(pnumpoints, p[w], -originalplanes[k].normal[0], -originalplanes[k].normal[1], -originalplanes[k].normal[2], -originalplanes[k].dist, 1.0/32.0, pmaxpoints, p[!w], &pnumpoints, 0, NULL, NULL); + w = !w; } } // if nothing is left, skip it - if (!w) + 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); continue; + } - // copy off the number of points for later when the winding is freed - numpolypoints = w->numpoints; + for (k = 0;k < pnumpoints;k++) + { + int l, m; + m = 0; + for (l = 0;l < numoriginalplanes;l++) + if (fabs(DotProduct(&p[w][k*3], originalplanes[l].normal) - originalplanes[l].dist) < 1.0/8.0) + m++; + if (m < 3) + break; + } + if (k < pnumpoints) + { + Con_Printf("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 (numpolypoints > maxpolypoints) + if (pnumpoints > pmaxpoints) { - Con_Printf("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n"); + Con_Print("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 (numelements + (w->numpoints - 2) * 3 > maxelements) + if (numelementsbuf + (pnumpoints - 2) * 3 > maxelementsbuf) { - Con_Printf("Collision_NewBrushFromPlanes: failed to build collision brush: too many triangle elements for buffer\n"); + Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many triangle elements for buffer\n"); return NULL; } - for (k = 0;k < w->numpoints;k++) + for (k = 0;k < pnumpoints;k++) { // check if there is already a matching point (no duplicates) - for (m = 0;m < numpoints;m++) - if (VectorDistance2(w->points[k], pointsbuf[m].v) < DIST_EPSILON) + for (m = 0;m < numpointsbuf;m++) + if (VectorDistance2(&p[w][k*3], pointsbuf[m].v) < COLLISION_SNAP) break; // if there is no match, add a new one - if (m == numpoints) + if (m == numpointsbuf) { // check if there are too many and skip the brush - if (numpoints >= 256) + if (numpointsbuf >= maxpointsbuf) { - Con_Printf("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n"); - Winding_Free(w); + Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many points for buffer\n"); return NULL; } // add the new one - VectorCopy(w->points[k], pointsbuf[numpoints].v); - numpoints++; + VectorCopy(&p[w][k*3], pointsbuf[numpointsbuf].v); + numpointsbuf++; } // store the index into a buffer polypointbuf[k] = m; } - Winding_Free(w); - w = NULL; // add the triangles for the polygon // (this particular code makes a triangle fan) - for (k = 0;k < numpolypoints - 2;k++) + for (k = 0;k < pnumpoints - 2;k++) { - numtriangles++; - elementsbuf[numelements++] = polypointbuf[0]; - elementsbuf[numelements++] = polypointbuf[k + 1]; - elementsbuf[numelements++] = polypointbuf[k + 2]; + elementsbuf[numelementsbuf++] = polypointbuf[0]; + elementsbuf[numelementsbuf++] = polypointbuf[k + 1]; + elementsbuf[numelementsbuf++] = polypointbuf[k + 2]; } // add the new plane - VectorCopy(originalplanes[j].normal, planesbuf[numplanes].normal); - planesbuf[numplanes].dist = originalplanes[j].dist; - numplanes++; + VectorCopy(originalplanes[j].normal, planesbuf[numplanesbuf].normal); + planesbuf[numplanesbuf].dist = originalplanes[j].dist; + numplanesbuf++; } - // recalc distances - for (j = 0;j < numplanes;j++) - planesbuf[j].dist = furthestplanedist_float(planesbuf[j].normal, pointsbuf, numpoints); - - if (numpoints) + // validate plane distances + for (j = 0;j < numplanesbuf;j++) { - 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]); - } + float d = furthestplanedist_float(planesbuf[j].normal, pointsbuf, numpointsbuf); + if (fabs(planesbuf[j].dist - d) > (1.0f/32.0f)) + 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 (numtriangles < 4 || numplanes < 4 || numpoints < 4) + 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; + } // allocate the brush and copy to it - brush = Collision_AllocBrushFloat(mempool, numpoints, numplanes, numtriangles, supercontents); - 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); + brush = Collision_AllocBrushFloat(mempool, numpointsbuf, numplanesbuf, numelementsbuf / 3, supercontents); + for (j = 0;j < brush->numpoints;j++) + { + brush->points[j].v[0] = pointsbuf[j].v[0]; + brush->points[j].v[1] = pointsbuf[j].v[1]; + brush->points[j].v[2] = pointsbuf[j].v[2]; + } + for (j = 0;j < brush->numplanes;j++) + { + brush->planes[j].normal[0] = planesbuf[j].normal[0]; + brush->planes[j].normal[1] = planesbuf[j].normal[1]; + brush->planes[j].normal[2] = planesbuf[j].normal[2]; + brush->planes[j].dist = planesbuf[j].dist; + } + 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++) + { + 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; + brush->mins[2] -= 1; + brush->maxs[0] += 1; + brush->maxs[1] += 1; + brush->maxs[2] += 1; Collision_ValidateBrush(brush); return brush; } @@ -528,7 +617,7 @@ colbrushf_t *Collision_AllocBrushFloat(mempool_t *mempool, int numpoints, int nu void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush) { int i; - float edge0[3], edge1[3], edge2[3], normal[3], dist, bestdist, temp[3]; + float edge0[3], edge1[3], edge2[3], normal[3], dist, bestdist; colpointf_t *p, *p2; if (brush->numpoints == 3) @@ -551,9 +640,42 @@ void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush) VectorSubtract(brush->points[2].v, brush->points[0].v, edge0); VectorSubtract(brush->points[0].v, brush->points[1].v, edge1); VectorSubtract(brush->points[1].v, brush->points[2].v, edge2); +#if 1 + { + float projectionnormal[3], projectionedge0[3], projectionedge1[3], projectionedge2[3]; + int i, best; + float dist, bestdist; + bestdist = fabs(brush->planes[0].normal[0]); + best = 0; + for (i = 1;i < 3;i++) + { + dist = fabs(brush->planes[0].normal[i]); + if (bestdist < dist) + { + bestdist = dist; + best = i; + } + } + VectorClear(projectionnormal); + if (brush->planes[0].normal[best] < 0) + projectionnormal[best] = -1; + else + projectionnormal[best] = 1; + VectorCopy(edge0, projectionedge0); + VectorCopy(edge1, projectionedge1); + VectorCopy(edge2, projectionedge2); + projectionedge0[best] = 0; + projectionedge1[best] = 0; + projectionedge2[best] = 0; + CrossProduct(projectionedge0, projectionnormal, brush->planes[2].normal); + CrossProduct(projectionedge1, projectionnormal, brush->planes[3].normal); + CrossProduct(projectionedge2, projectionnormal, brush->planes[4].normal); + } +#else CrossProduct(edge0, brush->planes->normal, brush->planes[2].normal); CrossProduct(edge1, brush->planes->normal, brush->planes[3].normal); CrossProduct(edge2, brush->planes->normal, brush->planes[4].normal); +#endif VectorNormalize(brush->planes[2].normal); VectorNormalize(brush->planes[3].normal); VectorNormalize(brush->planes[4].normal); @@ -564,15 +686,19 @@ void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush) if (developer.integer) { // validation code - //VectorSubtract(brush->points[0].v, brush->points[1].v, edge0); - //VectorSubtract(brush->points[2].v, brush->points[1].v, edge1); - CrossProduct(edge1, edge0, normal); +#if 0 + float temp[3]; + + VectorSubtract(brush->points[0].v, brush->points[1].v, edge0); + VectorSubtract(brush->points[2].v, brush->points[1].v, edge1); + CrossProduct(edge0, edge1, normal); VectorNormalize(normal); VectorSubtract(normal, brush->planes[0].normal, temp); if (VectorLength(temp) > 0.01f) Con_Printf("Collision_CalcPlanesForPolygonBrushFloat: TriangleNormal gave wrong answer (%f %f %f != correct answer %f %f %f)\n", brush->planes->normal[0], brush->planes->normal[1], brush->planes->normal[2], normal[0], normal[1], normal[2]); if (fabs(DotProduct(brush->planes[1].normal, brush->planes[0].normal) - -1.0f) > 0.01f || fabs(brush->planes[1].dist - -brush->planes[0].dist) > 0.01f) Con_Printf("Collision_CalcPlanesForPolygonBrushFloat: plane 1 (%f %f %f %f) is not opposite plane 0 (%f %f %f %f)\n", brush->planes[1].normal[0], brush->planes[1].normal[1], brush->planes[1].normal[2], brush->planes[1].dist, brush->planes[0].normal[0], brush->planes[0].normal[1], brush->planes[0].normal[2], brush->planes[0].dist); +#if 0 if (fabs(DotProduct(brush->planes[2].normal, brush->planes[0].normal)) > 0.01f) Con_Printf("Collision_CalcPlanesForPolygonBrushFloat: plane 2 (%f %f %f %f) is not perpendicular to plane 0 (%f %f %f %f)\n", brush->planes[2].normal[0], brush->planes[2].normal[1], brush->planes[2].normal[2], brush->planes[2].dist, brush->planes[0].normal[0], brush->planes[0].normal[1], brush->planes[0].normal[2], brush->planes[2].dist); if (fabs(DotProduct(brush->planes[3].normal, brush->planes[0].normal)) > 0.01f) @@ -585,6 +711,8 @@ void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush) Con_Printf("Collision_CalcPlanesForPolygonBrushFloat: plane 3 (%f %f %f %f) is not perpendicular to edge 1 (%f %f %f to %f %f %f)\n", brush->planes[3].normal[0], brush->planes[3].normal[1], brush->planes[3].normal[2], brush->planes[3].dist, brush->points[0].v[0], brush->points[0].v[1], brush->points[0].v[2], brush->points[1].v[0], brush->points[1].v[1], brush->points[1].v[2]); if (fabs(DotProduct(brush->planes[4].normal, edge2)) > 0.01f) Con_Printf("Collision_CalcPlanesForPolygonBrushFloat: plane 4 (%f %f %f %f) is not perpendicular to edge 2 (%f %f %f to %f %f %f)\n", brush->planes[4].normal[0], brush->planes[4].normal[1], brush->planes[4].normal[2], brush->planes[4].dist, brush->points[1].v[0], brush->points[1].v[1], brush->points[1].v[2], brush->points[2].v[0], brush->points[2].v[1], brush->points[2].v[2]); +#endif +#endif if (fabs(DotProduct(brush->points[0].v, brush->planes[0].normal) - brush->planes[0].dist) > 0.01f || fabs(DotProduct(brush->points[1].v, brush->planes[0].normal) - brush->planes[0].dist) > 0.01f || fabs(DotProduct(brush->points[2].v, brush->planes[0].normal) - brush->planes[0].dist) > 0.01f) Con_Printf("Collision_CalcPlanesForPolygonBrushFloat: edges (%f %f %f to %f %f %f to %f %f %f) off front plane 0 (%f %f %f %f)\n", brush->points[0].v[0], brush->points[0].v[1], brush->points[0].v[2], brush->points[1].v[0], brush->points[1].v[1], brush->points[1].v[2], brush->points[2].v[0], brush->points[2].v[1], brush->points[2].v[2], brush->planes[0].normal[0], brush->planes[0].normal[1], brush->planes[0].normal[2], brush->planes[0].dist); if (fabs(DotProduct(brush->points[0].v, brush->planes[1].normal) - brush->planes[1].dist) > 0.01f || fabs(DotProduct(brush->points[1].v, brush->planes[1].normal) - brush->planes[1].dist) > 0.01f || fabs(DotProduct(brush->points[2].v, brush->planes[1].normal) - brush->planes[1].dist) > 0.01f) @@ -667,17 +795,15 @@ colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, i return brush; } -#define COLLISIONEPSILON (1.0f / 32.0f) -#define COLLISIONEPSILON2 0//(1.0f / 32.0f) - // 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, fendsolid, brushsolid; - float enterfrac, leavefrac, d1, d2, f, newimpactnormal[3]; + float enterfrac, leavefrac, d1, d2, f, move, imove, newimpactnormal[3], enterfrac2; const colplanef_t *startplane, *endplane; enterfrac = -1; + enterfrac2 = -1; leavefrac = 1; fstartsolid = true; fendsolid = true; @@ -695,15 +821,15 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush // any brush with degenerate planes is not worth handling if (DotProduct(startplane->normal, startplane->normal) < 0.9f || DotProduct(endplane->normal, endplane->normal) < 0.9f) { - Con_Printf("Collision_TraceBrushBrushFloat: degenerate thisbrush plane!\n"); + Con_Print("Collision_TraceBrushBrushFloat: degenerate thisbrush plane!\n"); return; } f = furthestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints); - if (fabs(f - startplane->dist) > 0.01f) + if (fabs(f - startplane->dist) > 0.125f) Con_Printf("startplane->dist %f != calculated %f (thisbrush_start)\n", startplane->dist, f); } - d1 = nearestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints); - d2 = nearestplanedist_float(endplane->normal, thisbrush_end->points, thisbrush_end->numpoints) - furthestplanedist_float(endplane->normal, thatbrush_end->points, thatbrush_end->numpoints) - COLLISIONEPSILON2; + d1 = nearestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints) - collision_startnudge.value; + d2 = nearestplanedist_float(endplane->normal, thisbrush_end->points, thisbrush_end->numpoints) - furthestplanedist_float(endplane->normal, thatbrush_end->points, thatbrush_end->numpoints) - collision_endnudge.value; } else { @@ -714,50 +840,59 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush // any brush with degenerate planes is not worth handling if (DotProduct(startplane->normal, startplane->normal) < 0.9f || DotProduct(endplane->normal, endplane->normal) < 0.9f) { - Con_Printf("Collision_TraceBrushBrushFloat: degenerate thatbrush plane!\n"); + Con_Print("Collision_TraceBrushBrushFloat: degenerate thatbrush plane!\n"); return; } f = furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints); - if (fabs(f - startplane->dist) > 0.01f) + if (fabs(f - startplane->dist) > 0.125f) Con_Printf("startplane->dist %f != calculated %f (thatbrush_start)\n", startplane->dist, f); } - d1 = nearestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - startplane->dist; - d2 = nearestplanedist_float(endplane->normal, thisbrush_end->points, thisbrush_end->numpoints) - startplane->dist - COLLISIONEPSILON2; + d1 = nearestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - startplane->dist - collision_startnudge.value; + d2 = nearestplanedist_float(endplane->normal, thisbrush_end->points, thisbrush_end->numpoints) - endplane->dist - collision_endnudge.value; } //Con_Printf("%c%i: d1 = %f, d2 = %f, d1 / (d1 - d2) = %f\n", nplane2 != nplane ? 'b' : 'a', nplane2, d1, d2, d1 / (d1 - d2)); - f = d1 - d2; - if (f >= 0) + move = d1 - d2; + if (move > 0) { // moving into brush - if (d2 > 0) + if (d2 > collision_enternudge.value) return; if (d1 < 0) continue; // enter fstartsolid = false; - f = (d1 - COLLISIONEPSILON) / f; + imove = 1 / move; + f = (d1 - collision_enternudge.value) * imove; f = bound(0, f, 1); if (enterfrac < f) { enterfrac = f; + enterfrac2 = f - collision_impactnudge.value * imove; + enterfrac2 = bound(0, enterfrac2, 1); VectorLerp(startplane->normal, enterfrac, endplane->normal, newimpactnormal); } } - else + else if (move < 0) { // moving out of brush - if (d1 > 0) + if (d1 > collision_leavenudge.value) return; if (d2 < 0) continue; // leave fendsolid = false; - f = (d1 + COLLISIONEPSILON) / f; + f = (d1 + collision_leavenudge.value) / move; f = bound(0, f, 1); if (leavefrac > f) leavefrac = f; } + else + { + // sliding along plane + if (d1 > 0) + return; + } } brushsolid = trace->hitsupercontentsmask & thatbrush_start->supercontents; @@ -776,10 +911,35 @@ 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); - VectorCopy(newimpactnormal, trace->plane.normal); +#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->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->realfraction = bound(0, enterfrac, 1); + trace->fraction = bound(0, enterfrac2, 1); + VectorCopy(newimpactnormal, trace->plane.normal); + } } } @@ -787,10 +947,11 @@ 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, move, imove, newimpactnormal[3], enterfrac2; const colplanef_t *startplane, *endplane; enterfrac = -1; + enterfrac2 = -1; leavefrac = 1; fstartsolid = true; fendsolid = true; @@ -799,50 +960,53 @@ 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; + d1 = DotProduct(startplane->normal, linestart) - startplane->dist - collision_startnudge.value; + d2 = DotProduct(endplane->normal, lineend) - endplane->dist - collision_endnudge.value; if (developer.integer) { // any brush with degenerate planes is not worth handling if (DotProduct(startplane->normal, startplane->normal) < 0.9f || DotProduct(endplane->normal, endplane->normal) < 0.9f) { - Con_Printf("Collision_TraceLineBrushFloat: degenerate plane!\n"); + Con_Print("Collision_TraceLineBrushFloat: degenerate plane!\n"); return; } - f = furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints); - if (fabs(f - startplane->dist) > 0.01f) - Con_Printf("startplane->dist %f != calculated %f\n", startplane->dist, f); + if (thatbrush_start->numpoints) + { + f = furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints); + if (fabs(f - startplane->dist) > 0.125f) + Con_Printf("startplane->dist %f != calculated %f\n", startplane->dist, f); + } } - f = d1 - d2; - if (f >= 0) + move = d1 - d2; + if (move > 0) { // moving into brush - if (d2 > 0) + if (d2 >= 0) return; - if (d1 < 0) + if (d1 <= 0) continue; // enter fstartsolid = false; - f = (d1 - COLLISIONEPSILON) / f; - f = bound(0, f, 1); + imove = 1 / move; + f = (d1 - collision_enternudge.value) * imove; if (enterfrac < f) { enterfrac = f; + enterfrac2 = f - collision_impactnudge.value * imove; VectorLerp(startplane->normal, enterfrac, endplane->normal, newimpactnormal); } } else { // moving out of brush - if (d1 > 0) + if (d1 >= 0) return; - if (d2 < 0) + if (d2 <= 0) continue; // leave fendsolid = false; - f = (d1 + COLLISIONEPSILON) / f; - f = bound(0, f, 1); + f = (d1 - collision_leavenudge.value) / move; if (leavefrac > f) leavefrac = f; } @@ -864,10 +1028,52 @@ 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); - VectorCopy(newimpactnormal, trace->plane.normal); +#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->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->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; } } @@ -875,18 +1081,30 @@ static colpointf_t polyf_points[256]; static colplanef_t polyf_planes[256 + 2]; static colbrushf_t polyf_brush; +void Collision_SnapCopyPoints(int numpoints, const colpointf_t *in, colpointf_t *out, float fractionprecision, float invfractionprecision) +{ + while (numpoints--) + { + out->v[0] = floor(in->v[0] * fractionprecision + 0.5f) * invfractionprecision; + out->v[1] = floor(in->v[1] * fractionprecision + 0.5f) * invfractionprecision; + out->v[2] = floor(in->v[2] * fractionprecision + 0.5f) * invfractionprecision; + } +} + void Collision_TraceBrushPolygonFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, int supercontents) { if (numpoints > 256) { - Con_Printf("Polygon with more than 256 points not supported yet (fixme!)\n"); + Con_Print("Polygon with more than 256 points not supported yet (fixme!)\n"); return; } polyf_brush.numpoints = numpoints; polyf_brush.numplanes = numpoints + 2; - polyf_brush.points = (colpointf_t *)points; + //polyf_brush.points = (colpointf_t *)points; polyf_brush.planes = polyf_planes; polyf_brush.supercontents = supercontents; + polyf_brush.points = polyf_points; + Collision_SnapCopyPoints(numpoints, (colpointf_t *)points, polyf_points, COLLISION_SNAPSCALE, COLLISION_SNAP); Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); //Collision_PrintBrushAsQHull(&polyf_brush, "polyf_brush"); Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &polyf_brush, &polyf_brush); @@ -906,12 +1124,13 @@ void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *th 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); - facemins[0] = min(polyf_points[0].v[0], min(polyf_points[1].v[0], polyf_points[2].v[0])); - facemins[1] = min(polyf_points[0].v[1], min(polyf_points[1].v[1], polyf_points[2].v[1])); - facemins[2] = min(polyf_points[0].v[2], min(polyf_points[1].v[2], polyf_points[2].v[2])); - facemaxs[0] = max(polyf_points[0].v[0], max(polyf_points[1].v[0], polyf_points[2].v[0])); - facemaxs[1] = max(polyf_points[0].v[1], max(polyf_points[1].v[1], polyf_points[2].v[1])); - facemaxs[2] = max(polyf_points[0].v[2], max(polyf_points[1].v[2], polyf_points[2].v[2])); + Collision_SnapCopyPoints(3, polyf_points, polyf_points, COLLISION_SNAPSCALE, COLLISION_SNAP); + facemins[0] = min(polyf_points[0].v[0], min(polyf_points[1].v[0], polyf_points[2].v[0])) - 1; + facemins[1] = min(polyf_points[0].v[1], min(polyf_points[1].v[1], polyf_points[2].v[1])) - 1; + facemins[2] = min(polyf_points[0].v[2], min(polyf_points[1].v[2], polyf_points[2].v[2])) - 1; + facemaxs[0] = max(polyf_points[0].v[0], max(polyf_points[1].v[0], polyf_points[2].v[0])) + 1; + facemaxs[1] = max(polyf_points[0].v[1], max(polyf_points[1].v[1], polyf_points[2].v[1])) + 1; + facemaxs[2] = max(polyf_points[0].v[2], max(polyf_points[1].v[2], polyf_points[2].v[2])) + 1; if (BoxesOverlap(segmentmins, segmentmaxs, facemins, facemaxs)) { Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); @@ -925,12 +1144,14 @@ void Collision_TraceLinePolygonFloat(trace_t *trace, const vec3_t linestart, con { if (numpoints > 256) { - Con_Printf("Polygon with more than 256 points not supported yet (fixme!)\n"); + Con_Print("Polygon with more than 256 points not supported yet (fixme!)\n"); return; } polyf_brush.numpoints = numpoints; polyf_brush.numplanes = numpoints + 2; - polyf_brush.points = (colpointf_t *)points; + //polyf_brush.points = (colpointf_t *)points; + polyf_brush.points = polyf_points; + Collision_SnapCopyPoints(numpoints, (colpointf_t *)points, polyf_points, COLLISION_SNAPSCALE, COLLISION_SNAP); polyf_brush.planes = polyf_planes; polyf_brush.supercontents = supercontents; Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); @@ -941,7 +1162,11 @@ 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 + // FIXME: snap vertices? + 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; @@ -949,15 +1174,17 @@ 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); - facemins[0] = min(polyf_points[0].v[0], min(polyf_points[1].v[0], polyf_points[2].v[0])); - facemins[1] = min(polyf_points[0].v[1], min(polyf_points[1].v[1], polyf_points[2].v[1])); - facemins[2] = min(polyf_points[0].v[2], min(polyf_points[1].v[2], polyf_points[2].v[2])); - facemaxs[0] = max(polyf_points[0].v[0], max(polyf_points[1].v[0], polyf_points[2].v[0])); - facemaxs[1] = max(polyf_points[0].v[1], max(polyf_points[1].v[1], polyf_points[2].v[1])); - facemaxs[2] = max(polyf_points[0].v[2], max(polyf_points[1].v[2], polyf_points[2].v[2])); + Collision_SnapCopyPoints(numpoints, polyf_points, polyf_points, COLLISION_SNAPSCALE, COLLISION_SNAP); + facemins[0] = min(polyf_points[0].v[0], min(polyf_points[1].v[0], polyf_points[2].v[0])) - 1; + facemins[1] = min(polyf_points[0].v[1], min(polyf_points[1].v[1], polyf_points[2].v[1])) - 1; + facemins[2] = min(polyf_points[0].v[2], min(polyf_points[1].v[2], polyf_points[2].v[2])) - 1; + facemaxs[0] = max(polyf_points[0].v[0], max(polyf_points[1].v[0], polyf_points[2].v[0])) + 1; + facemaxs[1] = max(polyf_points[0].v[1], max(polyf_points[1].v[1], polyf_points[2].v[1])) + 1; + facemaxs[2] = max(polyf_points[0].v[2], max(polyf_points[1].v[2], polyf_points[2].v[2])) + 1; if (BoxesOverlap(segmentmins, segmentmaxs, facemins, facemaxs)) { Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); @@ -965,6 +1192,7 @@ void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart Collision_TraceLineBrushFloat(trace, linestart, lineend, &polyf_brush, &polyf_brush); } } +#endif } @@ -977,7 +1205,7 @@ void Collision_TraceBrushPolygonTransformFloat(trace_t *trace, const colbrushf_t int i; if (numpoints > 256) { - Con_Printf("Polygon with more than 256 points not supported yet (fixme!)\n"); + Con_Print("Polygon with more than 256 points not supported yet (fixme!)\n"); return; } polyf_brushstart.numpoints = numpoints; @@ -994,6 +1222,8 @@ void Collision_TraceBrushPolygonTransformFloat(trace_t *trace, const colbrushf_t polyf_brushend.supercontents = supercontents; for (i = 0;i < numpoints;i++) Matrix4x4_Transform(polygonmatrixend, points + i * 3, polyf_brushend.points[i].v); + Collision_SnapCopyPoints(numpoints, polyf_pointsstart, polyf_pointsstart, COLLISION_SNAPSCALE, COLLISION_SNAP); + Collision_SnapCopyPoints(numpoints, polyf_pointsend, polyf_pointsend, COLLISION_SNAPSCALE, COLLISION_SNAP); Collision_CalcPlanesForPolygonBrushFloat(&polyf_brushstart); Collision_CalcPlanesForPolygonBrushFloat(&polyf_brushend); @@ -1032,7 +1262,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) @@ -1061,9 +1291,27 @@ 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]); + } + brush->mins[0] -= 1; + brush->mins[1] -= 1; + brush->mins[2] -= 1; + brush->maxs[0] += 1; + brush->maxs[1] += 1; + brush->maxs[2] += 1; Collision_ValidateBrush(brush); return brush; } @@ -1087,6 +1335,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); } @@ -1160,6 +1409,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 - collision_impactnudge.value) * 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; @@ -1227,5 +1567,11 @@ void Collision_BoundingBoxOfBrushTraceSegment(const colbrushf_t *start, const co maxs[1] = min(maxs[1], min(tempstart[1], tempend[1])); maxs[2] = min(maxs[2], min(tempstart[2], tempend[2])); } + mins[0] -= 1; + mins[1] -= 1; + mins[2] -= 1; + maxs[0] += 1; + maxs[1] += 1; + maxs[2] += 1; }