X-Git-Url: http://de.git.xonotic.org/?a=blobdiff_plain;f=collision.c;h=e132341bd356ec9ac345ac4f572e31f4156dd502;hb=eacd06327dd5ac3be3800d102e5b56a1efd051b0;hp=c0b930675d39a8fd25e8546ec75feadab38e1d90;hpb=8ab34e35efc54ec4a79788d969d40bf0f16e408f;p=xonotic%2Fdarkplaces.git diff --git a/collision.c b/collision.c index c0b93067..e132341b 100644 --- a/collision.c +++ b/collision.c @@ -5,292 +5,11 @@ #define COLLISION_SNAPSCALE (8.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 - const hull_t *hull; - - // the trace structure to fill in - trace_t *trace; - - // start and end of the trace (in model space) - double start[3]; - double end[3]; - - // end - start - double dist[3]; - - // overrides the CONTENTS_SOLID in the box bsp tree - int boxsupercontents; -} -RecursiveHullCheckTraceInfo_t; - -#define HULLCHECKSTATE_EMPTY 0 -#define HULLCHECKSTATE_SOLID 1 -#define HULLCHECKSTATE_DONE 2 - -static int RecursiveHullCheck(RecursiveHullCheckTraceInfo_t *t, int num, double p1f, double p2f, double p1[3], double p2[3]) -{ - // status variables, these don't need to be saved on the stack when - // recursing... but are because this should be thread-safe - // (note: tracing against a bbox is not thread-safe, yet) - int ret; - mplane_t *plane; - double t1, t2; - - // variables that need to be stored on the stack when recursing - dclipnode_t *node; - int side; - double midf, mid[3]; - - // LordHavoc: a goto! everyone flee in terror... :) -loc0: - // check for empty - if (num < 0) - { - 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; - } - } - - // find the point distances - node = t->hull->clipnodes + num; - - plane = t->hull->planes + node->planenum; - if (plane->type < 3) - { - t1 = p1[plane->type] - plane->dist; - t2 = p2[plane->type] - plane->dist; - } - else - { - t1 = DotProduct (plane->normal, p1) - plane->dist; - t2 = DotProduct (plane->normal, p2) - plane->dist; - } - - if (t1 < 0) - { - if (t2 < 0) - { -#if COLLISIONPARANOID >= 3 - Con_Print("<"); -#endif - num = node->children[1]; - goto loc0; - } - side = 1; - } - else - { - if (t2 >= 0) - { -#if COLLISIONPARANOID >= 3 - Con_Print(">"); -#endif - num = node->children[0]; - goto loc0; - } - side = 0; - } - - // 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; - t2 = t->end[plane->type] - plane->dist; - } - else - { - t1 = DotProduct (plane->normal, t->start) - plane->dist; - t2 = DotProduct (plane->normal, t->end) - plane->dist; - } - - midf = t1 / (t1 - t2); - midf = bound(p1f, midf, p2f); - VectorMA(t->start, midf, t->dist, mid); - - // recurse both sides, front side first - ret = RecursiveHullCheck (t, node->children[side], p1f, midf, p1, mid); - // if this side is not empty, return what it is (solid or done) - if (ret != HULLCHECKSTATE_EMPTY) - return ret; - - ret = RecursiveHullCheck (t, node->children[side ^ 1], midf, p2f, mid, p2); - // if other side is not solid, return what it is (empty or done) - if (ret != HULLCHECKSTATE_SOLID) - return ret; - - // front is air and back is solid, this is the impact point... - if (side) - { - t->trace->plane.dist = -plane->dist; - VectorNegate (plane->normal, t->trace->plane.normal); - } - else - { - t->trace->plane.dist = plane->dist; - VectorCopy (plane->normal, t->trace->plane.normal); - } - - // 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->realfraction = bound(0, midf, 1); - - // 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; -} - -#if 0 -// used if start and end are the same -static void RecursiveHullCheckPoint (RecursiveHullCheckTraceInfo_t *t, int num) -{ - // If you can read this, you understand BSP trees - while (num >= 0) - num = t->hull->clipnodes[num].children[((t->hull->planes[t->hull->clipnodes[num].planenum].type < 3) ? (t->start[t->hull->planes[t->hull->clipnodes[num].planenum].type]) : (DotProduct(t->hull->planes[t->hull->clipnodes[num].planenum].normal, t->start))) < t->hull->planes[t->hull->clipnodes[num].planenum].dist]; - - // check for empty - t->trace->endcontents = num; - if (t->trace->thiscontents) - { - if (num == t->trace->thiscontents) - t->trace->allsolid = false; - else - { - // if the first leaf is solid, set startsolid - if (t->trace->allsolid) - t->trace->startsolid = true; - } - } - else - { - if (num != CONTENTS_SOLID) - { - t->trace->allsolid = false; - if (num == CONTENTS_EMPTY) - t->trace->inopen = true; - else - t->trace->inwater = true; - } - else - { - // if the first leaf is solid, set startsolid - if (t->trace->allsolid) - t->trace->startsolid = true; - } - } -} -#endif - -static hull_t box_hull; -static dclipnode_t box_clipnodes[6]; -static mplane_t box_planes[6]; - -void Mod_Q1BSP_Collision_Init (void) -{ - int i; - int side; - - //Set up the planes and clipnodes so that the six floats of a bounding box - //can just be stored out and get a proper hull_t structure. - - box_hull.clipnodes = box_clipnodes; - box_hull.planes = box_planes; - box_hull.firstclipnode = 0; - box_hull.lastclipnode = 5; - - for (i = 0;i < 6;i++) - { - box_clipnodes[i].planenum = i; - - side = i&1; - - box_clipnodes[i].children[side] = CONTENTS_EMPTY; - if (i != 5) - box_clipnodes[i].children[side^1] = i + 1; - else - box_clipnodes[i].children[side^1] = CONTENTS_SOLID; - - box_planes[i].type = i>>1; - box_planes[i].normal[i>>1] = 1; - } -} - -void Collision_ClipTrace_Box(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask, int boxsupercontents) -{ - RecursiveHullCheckTraceInfo_t rhc; - // fill in a default trace - memset(&rhc, 0, sizeof(rhc)); - memset(trace, 0, sizeof(trace_t)); - //To keep everything totally uniform, bounding boxes are turned into small - //BSP trees instead of being compared directly. - // create a temp hull from bounding box sizes - box_planes[0].dist = cmaxs[0] - mins[0]; - box_planes[1].dist = cmins[0] - maxs[0]; - box_planes[2].dist = cmaxs[1] - mins[1]; - box_planes[3].dist = cmins[1] - maxs[1]; - box_planes[4].dist = cmaxs[2] - mins[2]; - box_planes[5].dist = cmins[2] - maxs[2]; - // trace a line through the generated clipping hull - rhc.boxsupercontents = boxsupercontents; - rhc.hull = &box_hull; - 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); - if (rhc.trace->startsupercontents) - rhc.trace->startsupercontents = boxsupercontents; -} -#endif +cvar_t collision_impactnudge = {0, "collision_impactnudge", "0.03125", "how much to back off from the impact"}; +cvar_t collision_startnudge = {0, "collision_startnudge", "0", "how much to bias collision trace start"}; +cvar_t collision_endnudge = {0, "collision_endnudge", "0", "how much to bias collision trace end"}; +cvar_t collision_enternudge = {0, "collision_enternudge", "0", "how much to bias collision entry fraction"}; +cvar_t collision_leavenudge = {0, "collision_leavenudge", "0", "how much to bias collision exit fraction"}; void Collision_Init (void) { @@ -449,7 +168,7 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla // check if there are too many and skip the brush if (numplanesbuf >= maxplanesbuf) { - Con_Print("Mod_Q3BSP_LoadBrushes: failed to build collision brush: too many planes for buffer\n"); + Con_Print("Collision_NewBrushFromPlanes: failed to build collision brush: too many planes for buffer\n"); return NULL; } @@ -464,7 +183,7 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla { // we want to keep the inside of the brush plane so we flip // the cutting plane - 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); + 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, NULL); w = !w; } } @@ -603,14 +322,14 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla colbrushf_t *Collision_AllocBrushFloat(mempool_t *mempool, int numpoints, int numplanes, int numtriangles, int supercontents) { colbrushf_t *brush; - brush = Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colpointf_t) * numpoints + sizeof(colplanef_t) * numplanes + sizeof(int[3]) * numtriangles); + brush = (colbrushf_t *)Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colpointf_t) * numpoints + sizeof(colplanef_t) * numplanes + sizeof(int[3]) * numtriangles); brush->supercontents = supercontents; brush->numplanes = numplanes; brush->numpoints = numpoints; brush->numtriangles = numtriangles; - brush->planes = (void *)(brush + 1); - brush->points = (void *)(brush->planes + brush->numplanes); - brush->elements = (void *)(brush->points + brush->numpoints); + brush->planes = (colplanef_t *)(brush + 1); + brush->points = (colpointf_t *)(brush->planes + brush->numplanes); + brush->elements = (int *)(brush->points + brush->numpoints); return brush; } @@ -620,6 +339,7 @@ void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush) float edge0[3], edge1[3], edge2[3], normal[3], dist, bestdist; colpointf_t *p, *p2; + // FIXME: these probably don't actually need to be normalized if the collision code does not care if (brush->numpoints == 3) { // optimized triangle case @@ -785,13 +505,13 @@ void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush) colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points, int supercontents) { colbrushf_t *brush; - brush = Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colplanef_t) * (numpoints + 2)); + brush = (colbrushf_t *)Mem_Alloc(mempool, sizeof(colbrushf_t) + sizeof(colplanef_t) * (numpoints + 2)); brush->supercontents = supercontents; brush->numpoints = numpoints; brush->numplanes = numpoints + 2; - brush->planes = (void *)(brush + 1); + brush->planes = (colplanef_t *)(brush + 1); brush->points = (colpointf_t *)points; - Host_Error("Collision_AllocBrushFromPermanentPolygonFloat: FIXME: this code needs to be updated to generate a mesh...\n"); + Sys_Error("Collision_AllocBrushFromPermanentPolygonFloat: FIXME: this code needs to be updated to generate a mesh..."); return brush; } @@ -802,6 +522,7 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush float enterfrac, leavefrac, d1, d2, f, imove, newimpactnormal[3], enterfrac2; const colplanef_t *startplane, *endplane; + VectorClear(newimpactnormal); enterfrac = -1; enterfrac2 = -1; leavefrac = 1; @@ -942,6 +663,7 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const float enterfrac, leavefrac, d1, d2, f, imove, newimpactnormal[3], enterfrac2; const colplanef_t *startplane, *endplane; + VectorClear(newimpactnormal); enterfrac = -1; enterfrac2 = -1; leavefrac = 1; @@ -1021,7 +743,7 @@ 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->realfraction && enterfrac - (1.0f / 1024.0f) <= leavefrac) + if (brushsolid && enterfrac > -1 && enterfrac < trace->realfraction && enterfrac <= leavefrac) { #if 0 // broken @@ -1118,12 +840,12 @@ void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *th VectorCopy(vertex3f + element3i[1] * 3, polyf_points[1].v); VectorCopy(vertex3f + element3i[2] * 3, polyf_points[2].v); 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; + 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])); if (BoxesOverlap(segmentmins, segmentmaxs, facemins, facemaxs)) { Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); @@ -1172,12 +894,12 @@ void Collision_TraceLineTriangleMeshFloat(trace_t *trace, const vec3_t linestart VectorCopy(vertex3f + element3i[1] * 3, polyf_points[1].v); VectorCopy(vertex3f + element3i[2] * 3, polyf_points[2].v); 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; + 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])); if (BoxesOverlap(segmentmins, segmentmaxs, facemins, facemaxs)) { Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); @@ -1260,6 +982,7 @@ colbrushf_t *Collision_BrushForBox(const matrix4x4_t *matrix, const vec3_t mins, colbrushf_t *brush; if (brushforbox_brush[0].numpoints == 0) Collision_InitBrushForBox(); + // FIXME: these probably don't actually need to be normalized if the collision code does not care if (VectorCompare(mins, maxs)) { // point brush @@ -1312,7 +1035,6 @@ colbrushf_t *Collision_BrushForBox(const matrix4x4_t *matrix, const vec3_t mins, void Collision_ClipTrace_BrushBox(trace_t *trace, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end, int hitsupercontentsmask) { colbrushf_t *boxbrush, *thisbrush_start, *thisbrush_end; - matrix4x4_t identitymatrix; vec3_t startmins, startmaxs, endmins, endmaxs; // create brushes for the collision @@ -1320,7 +1042,6 @@ void Collision_ClipTrace_BrushBox(trace_t *trace, const vec3_t cmins, const vec3 VectorAdd(start, maxs, startmaxs); VectorAdd(end, mins, endmins); VectorAdd(end, maxs, endmaxs); - Matrix4x4_CreateIdentity(&identitymatrix); boxbrush = Collision_BrushForBox(&identitymatrix, cmins, cmaxs); thisbrush_start = Collision_BrushForBox(&identitymatrix, startmins, startmaxs); thisbrush_end = Collision_BrushForBox(&identitymatrix, endmins, endmaxs); @@ -1333,7 +1054,10 @@ void Collision_ClipTrace_BrushBox(trace_t *trace, const vec3_t cmins, const vec3 Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, boxbrush, boxbrush); } -// LordHavoc: currently unused and not yet tested +//pseudocode for detecting line/sphere overlap without calculating an impact point +//linesphereorigin = sphereorigin - linestart;linediff = lineend - linestart;linespherefrac = DotProduct(linesphereorigin, linediff) / DotProduct(linediff, linediff);return VectorLength2(linesphereorigin - bound(0, linespherefrac, 1) * linediff) >= sphereradius*sphereradius; + +// LordHavoc: currently unused, but tested // note: this can be used for tracing a moving sphere vs a stationary sphere, // by simply adding the moving sphere's radius to the sphereradius parameter, // all the results are correct (impactpoint, impactnormal, and fraction) @@ -1342,68 +1066,158 @@ float Collision_ClipTrace_Line_Sphere(double *linestart, double *lineend, double double dir[3], scale, v[3], deviationdist, impactdist, linelength; // make sure the impactpoint and impactnormal are valid even if there is // no collision - impactpoint[0] = lineend[0]; - impactpoint[1] = lineend[1]; - impactpoint[2] = lineend[2]; - impactnormal[0] = 0; - impactnormal[1] = 0; - impactnormal[2] = 0; + VectorCopy(lineend, impactpoint); + VectorClear(impactnormal); // calculate line direction - dir[0] = lineend[0] - linestart[0]; - dir[1] = lineend[1] - linestart[1]; - dir[2] = lineend[2] - linestart[2]; + VectorSubtract(lineend, linestart, dir); // normalize direction - linelength = sqrt(dir[0] * dir[0] + dir[1] * dir[1] + dir[2] * dir[2]); + linelength = VectorLength(dir); if (linelength) { scale = 1.0 / linelength; - dir[0] *= scale; - dir[1] *= scale; - dir[2] *= scale; + VectorScale(dir, scale, dir); } // this dotproduct calculates the distance along the line at which the // sphere origin is (nearest point to the sphere origin on the line) - impactdist = dir[0] * (sphereorigin[0] - linestart[0]) + dir[1] * (sphereorigin[1] - linestart[1]) + dir[2] * (sphereorigin[2] - linestart[2]); + impactdist = DotProduct(sphereorigin, dir) - DotProduct(linestart, dir); // calculate point on line at that distance, and subtract the // sphereorigin from it, so we have a vector to measure for the distance // of the line from the sphereorigin (deviation, how off-center it is) - v[0] = linestart[0] + impactdist * dir[0] - sphereorigin[0]; - v[1] = linestart[1] + impactdist * dir[1] - sphereorigin[1]; - v[2] = linestart[2] + impactdist * dir[2] - sphereorigin[2]; - deviationdist = v[0] * v[0] + v[1] * v[1] + v[2] * v[2]; + VectorMA(linestart, impactdist, dir, v); + VectorSubtract(v, sphereorigin, v); + deviationdist = VectorLength2(v); // if outside the radius, it's a miss for sure // (we do this comparison using squared radius to avoid a sqrt) if (deviationdist > sphereradius*sphereradius) return 1; // miss (off to the side) // nudge back to find the correct impact distance - impactdist += (sqrt(deviationdist) - sphereradius); + impactdist += deviationdist - sphereradius; if (impactdist >= linelength) return 1; // miss (not close enough) if (impactdist < 0) return 1; // miss (linestart is past or inside sphere) // calculate new impactpoint - impactpoint[0] = linestart[0] + impactdist * dir[0]; - impactpoint[1] = linestart[1] + impactdist * dir[1]; - impactpoint[2] = linestart[2] + impactdist * dir[2]; + VectorMA(linestart, impactdist, dir, impactpoint); // calculate impactnormal (surface normal at point of impact) - impactnormal[0] = impactpoint[0] - sphereorigin[0]; - impactnormal[1] = impactpoint[1] - sphereorigin[1]; - impactnormal[2] = impactpoint[2] - sphereorigin[2]; + VectorSubtract(impactpoint, sphereorigin, impactnormal); // normalize impactnormal - scale = impactnormal[0] * impactnormal[0] + impactnormal[1] * impactnormal[1] + impactnormal[2] * impactnormal[2]; - if (scale) - { - scale = 1.0 / sqrt(scale); - impactnormal[0] *= scale; - impactnormal[1] *= scale; - impactnormal[2] *= scale; - } + VectorNormalize(impactnormal); // return fraction of movement distance 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) { +#if 1 + // more optimized + float d1, d2, d, f, impact[3], edgenormal[3], faceplanenormal[3], faceplanedist, faceplanenormallength2, edge01[3], edge21[3], edge02[3]; + + // this function executes: + // 32 ops when line starts behind triangle + // 38 ops when line ends infront of triangle + // 43 ops when line fraction is already closer than this triangle + // 72 ops when line is outside edge 01 + // 92 ops when line is outside edge 21 + // 115 ops when line is outside edge 02 + // 123 ops when line impacts triangle and updates trace results + + // 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 + // 15 ops + VectorSubtract(point0, point1, edge01); + VectorSubtract(point2, point1, edge21); + CrossProduct(edge01, edge21, faceplanenormal); + // there's no point in processing a degenerate triangle (GIGO - Garbage In, Garbage Out) + // 6 ops + faceplanenormallength2 = DotProduct(faceplanenormal, faceplanenormal); + if (faceplanenormallength2 < 0.0001f) + return; + // calculate the distance + // 5 ops + faceplanedist = DotProduct(point0, faceplanenormal); + + // 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) + + // calculate the start distance + // 6 ops + d1 = DotProduct(faceplanenormal, linestart); + if (d1 <= faceplanedist) + return; + + // calculate the end distance + // 6 ops + d2 = DotProduct(faceplanenormal, lineend); + // if both are in front, there is no collision + if (d2 >= faceplanedist) + 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) + // 2 ops + 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 + // 2 ops + f = (d1 - faceplanedist) * d; + // skip out if this impact is further away than previous ones + // 1 ops + if (f > trace->realfraction) + return; + // calculate the perfect impact point for classification of insidedness + // 9 ops + 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) + + // first use the two edges from the triangle plane math + // the other edge only gets calculated if the point survives that long + + // 20 ops + CrossProduct(edge01, faceplanenormal, edgenormal); + if (DotProduct(impact, edgenormal) > DotProduct(point1, edgenormal)) + return; + + // 20 ops + CrossProduct(faceplanenormal, edge21, edgenormal); + if (DotProduct(impact, edgenormal) > DotProduct(point2, edgenormal)) + return; + + // 23 ops + VectorSubtract(point0, point2, edge02); + CrossProduct(faceplanenormal, edge02, edgenormal); + if (DotProduct(impact, edgenormal) > DotProduct(point0, edgenormal)) + return; + + // 8 ops (rare) + + // store the new trace fraction + trace->realfraction = f; + + // calculate a nudged fraction to keep it out of the surface + // (the main fraction remains perfect) + trace->fraction = f - collision_impactnudge.value * d; + + // store the new trace plane (because collisions only happen from + // the front this is always simply the triangle normal, never flipped) + d = 1.0 / sqrt(faceplanenormallength2); + VectorScale(faceplanenormal, d, trace->plane.normal); + trace->plane.dist = faceplanedist * d; +#else float d1, d2, d, f, fnudged, impact[3], edgenormal[3], faceplanenormal[3], faceplanedist, edge[3]; // this code is designed for clockwise triangles, conversion to @@ -1425,7 +1239,7 @@ void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, co 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) + if (d1 <= 0) return; // calculate the unnormalized end distance @@ -1457,7 +1271,7 @@ void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, co // (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)) @@ -1496,6 +1310,7 @@ void Collision_TraceLineTriangleFloat(trace_t *trace, const vec3_t linestart, co //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]); +#endif } typedef struct colbspnode_s @@ -1522,9 +1337,9 @@ colbsp_t; colbsp_t *Collision_CreateCollisionBSP(mempool_t *mempool) { colbsp_t *bsp; - bsp = Mem_Alloc(mempool, sizeof(colbsp_t)); + bsp = (colbsp_t *)Mem_Alloc(mempool, sizeof(colbsp_t)); bsp->mempool = mempool; - bsp->nodes = Mem_Alloc(bsp->mempool, sizeof(colbspnode_t)); + bsp->nodes = (colbspnode_t *)Mem_Alloc(bsp->mempool, sizeof(colbspnode_t)); return bsp; }