From d3135507efcf1249b03e440b62bd07b0f935ca39 Mon Sep 17 00:00:00 2001 From: havoc Date: Sun, 10 Aug 2003 13:50:00 +0000 Subject: [PATCH] Q3BSP collisions implemented (although not for patches, which aren't supported anyway, yet, and this is definitely not tested yet) git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@3387 d7cf8633-e32d-0410-b094-e92efae38249 --- collision.c | 197 ++++++++++++++++++------------------------------- collision.h | 16 ++-- model_brush.c | 151 ++++++++++++++++++++++++++++++++++++- model_shared.h | 1 + 4 files changed, 230 insertions(+), 135 deletions(-) diff --git a/collision.c b/collision.c index 7a7045cf..ef8e06f0 100644 --- a/collision.c +++ b/collision.c @@ -429,7 +429,7 @@ float furthestplanedist_float(const float *normal, const colpointf_t *points, in #define COLLISIONEPSILON2 0//(1.0f / 32.0f) // NOTE: start and end of each brush pair must have same numplanes/numpoints -float Collision_TraceBrushBrushFloat(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const colbrushf_t *thatbrush_start, const colbrushf_t *thatbrush_end, float *impactnormal, int *startsolid, int *allsolid) +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; float enterfrac, leavefrac, d1, d2, f, newimpactnormal[3]; @@ -463,7 +463,7 @@ float Collision_TraceBrushBrushFloat(const colbrushf_t *thisbrush_start, const c { // moving into brush if (d2 > 0) - return 1; + return; if (d1 < 0) continue; // enter @@ -480,7 +480,7 @@ float Collision_TraceBrushBrushFloat(const colbrushf_t *thisbrush_start, const c { // moving out of brush if (d1 > 0) - return 1; + return; if (d2 < 0) continue; // leave @@ -494,36 +494,31 @@ float Collision_TraceBrushBrushFloat(const colbrushf_t *thisbrush_start, const c if (fstartsolid) { - if (startsolid) - *startsolid = true; - if (fendsolid && allsolid) - *allsolid = true; + trace->startsolid = true; + if (fendsolid) + trace->allsolid = true; } // 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 (enterfrac > -1 && enterfrac < 1 && enterfrac - (1.0f / 1024.0f) <= leavefrac) + if (enterfrac > -1 && enterfrac < trace->fraction && enterfrac - (1.0f / 1024.0f) <= leavefrac) { - //if (enterfrac < (1.0f / 1024.0f)) - // enterfrac = 0; - enterfrac = bound(0, enterfrac, 1); - VectorCopy(newimpactnormal, impactnormal); - return enterfrac; + trace->fraction = bound(0, enterfrac, 1); + VectorCopy(newimpactnormal, trace->plane.normal); } - return 1; } static colplanef_t polyf_planes[256 + 2]; static colbrushf_t polyf_brush; -float Collision_TraceBrushPolygonFloat(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, float *impactnormal, int *startsolid, int *allsolid) +void Collision_TraceBrushPolygonFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points) { if (numpoints > 256) { Con_Printf("Polygon with more than 256 points not supported yet (fixme!)\n"); - return 1; + return; } polyf_brush.numpoints = numpoints; polyf_brush.numplanes = numpoints + 2; @@ -531,20 +526,20 @@ float Collision_TraceBrushPolygonFloat(const colbrushf_t *thisbrush_start, const polyf_brush.planes = polyf_planes; Collision_CalcPlanesForPolygonBrushFloat(&polyf_brush); //Collision_PrintBrushAsQHull(&polyf_brush, "polyf_brush"); - return Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, &polyf_brush, &polyf_brush, impactnormal, startsolid, allsolid); + Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &polyf_brush, &polyf_brush); } static colpointf_t polyf_pointsstart[256], polyf_pointsend[256]; static colplanef_t polyf_planesstart[256 + 2], polyf_planesend[256 + 2]; static colbrushf_t polyf_brushstart, polyf_brushend; -float Collision_TraceBrushPolygonTransformFloat(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, float *impactnormal, const matrix4x4_t *polygonmatrixstart, const matrix4x4_t *polygonmatrixend, int *startsolid, int *allsolid) +void Collision_TraceBrushPolygonTransformFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, const matrix4x4_t *polygonmatrixstart, const matrix4x4_t *polygonmatrixend) { int i; if (numpoints > 256) { Con_Printf("Polygon with more than 256 points not supported yet (fixme!)\n"); - return 1; + return; } polyf_brushstart.numpoints = numpoints; polyf_brushstart.numplanes = numpoints + 2; @@ -564,7 +559,7 @@ float Collision_TraceBrushPolygonTransformFloat(const colbrushf_t *thisbrush_sta //Collision_PrintBrushAsQHull(&polyf_brushstart, "polyf_brushstart"); //Collision_PrintBrushAsQHull(&polyf_brushend, "polyf_brushend"); - return Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, &polyf_brushstart, &polyf_brushend, impactnormal, startsolid, allsolid); + Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, &polyf_brushstart, &polyf_brushend); } colbrushd_t *Collision_AllocBrushDouble(mempool_t *mempool, int numpoints, int numplanes) @@ -668,120 +663,102 @@ double furthestplanedist_double(const double *normal, const colpointd_t *points, } // NOTE: start and end of each brush pair must have same numplanes/numpoints -double Collision_TraceBrushBrushDouble(const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, const colbrushd_t *thatbrush_start, const colbrushd_t *thatbrush_end, double *impactnormal) +void Collision_TraceBrushBrushDouble(trace_t *trace, const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, const colbrushd_t *thatbrush_start, const colbrushd_t *thatbrush_end) { - int nplane; + int nplane, nplane2, fstartsolid, fendsolid; double enterfrac, leavefrac, d1, d2, f, newimpactnormal[3]; const colplaned_t *startplane, *endplane; enterfrac = -1; leavefrac = 1; + fstartsolid = true; + fendsolid = true; - for (nplane = 0;nplane < thatbrush_start->numplanes;nplane++) + for (nplane = 0;nplane < thatbrush_start->numplanes + thisbrush_start->numplanes;nplane++) { - startplane = thatbrush_start->planes + nplane; - endplane = thatbrush_end->planes + nplane; - d1 = nearestplanedist_double(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - furthestplanedist_double(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints); - d2 = nearestplanedist_double(endplane->normal, thisbrush_end->points, thisbrush_start->numpoints) - furthestplanedist_double(endplane->normal, thatbrush_end->points, thatbrush_start->numpoints) - (1.0 / 32.0); - - f = d1 - d2; - if (f >= 0) + nplane2 = nplane; + if (nplane2 >= thatbrush_start->numplanes) { - // moving into brush - if (d2 > 0) - return 1; - if (d1 < 0) - continue; - // enter - f = d1 / f; - if (enterfrac < f) - { - enterfrac = f; - VectorSubtract(endplane->normal, startplane->normal, newimpactnormal); - VectorMA(startplane->normal, enterfrac, impactnormal, newimpactnormal); - } + nplane2 -= thatbrush_start->numplanes; + startplane = thisbrush_start->planes + nplane2; + endplane = thisbrush_end->planes + nplane2; } else { - // moving out of brush - if (d1 > 0) - return 1; - if (d2 < 0) - continue; - // leave - f = d1 / f; - if (leavefrac > f) - leavefrac = f; + startplane = thatbrush_start->planes + nplane2; + endplane = thatbrush_end->planes + nplane2; } - } - - for (nplane = 0;nplane < thisbrush_start->numplanes;nplane++) - { - startplane = thisbrush_start->planes + nplane; - endplane = thisbrush_end->planes + nplane; d1 = nearestplanedist_double(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints) - furthestplanedist_double(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints); - d2 = nearestplanedist_double(endplane->normal, thisbrush_end->points, thisbrush_start->numpoints) - furthestplanedist_double(endplane->normal, thatbrush_end->points, thatbrush_start->numpoints) - (1.0 / 32.0); + d2 = nearestplanedist_double(endplane->normal, thisbrush_end->points, thisbrush_end->numpoints) - furthestplanedist_double(endplane->normal, thatbrush_end->points, thatbrush_end->numpoints) - COLLISIONEPSILON2; + //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) { // moving into brush if (d2 > 0) - return 1; + return; if (d1 < 0) continue; // enter - f = d1 / f; + fstartsolid = false; + f = (d1 - COLLISIONEPSILON) / f; + f = bound(0, f, 1); if (enterfrac < f) { enterfrac = f; - VectorSubtract(endplane->normal, startplane->normal, newimpactnormal); - VectorMA(startplane->normal, enterfrac, impactnormal, newimpactnormal); + VectorBlend(startplane->normal, endplane->normal, enterfrac, newimpactnormal); } } - else + else if (f < 0) { // moving out of brush if (d1 > 0) - return 1; + return; if (d2 < 0) continue; // leave - f = d1 / f; + fendsolid = false; + f = (d1 + COLLISIONEPSILON) / f; + f = bound(0, f, 1); if (leavefrac > f) leavefrac = f; } } + if (fstartsolid) + { + trace->startsolid = true; + if (fendsolid) + trace->allsolid = true; + } + // 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. - enterfrac -= (1.0 / 16384.0); - if (leavefrac - enterfrac >= 0 && enterfrac > -1) + if (enterfrac > -1 && enterfrac < trace->fraction && enterfrac - (1.0f / 1024.0f) <= leavefrac) { - VectorCopy(newimpactnormal, impactnormal); - enterfrac = bound(0, enterfrac, 1); - return enterfrac; + trace->fraction = bound(0, enterfrac, 1); + VectorCopy(newimpactnormal, trace->plane.normal); } - return 1; } static colplaned_t polyd_planes[256 + 2]; static colbrushd_t polyd_brush; -double Collision_TraceBrushPolygonDouble(const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, int numpoints, const double *points, double *impactnormal) +void Collision_TraceBrushPolygonDouble(trace_t *trace, const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, int numpoints, const double *points) { if (numpoints > 256) { Con_Printf("Polygon with more than 256 points not supported yet (fixme!)\n"); - return 1; + return; } polyd_brush.numpoints = numpoints; polyd_brush.numplanes = numpoints + 2; polyd_brush.points = (colpointd_t *)points; polyd_brush.planes = polyd_planes; Collision_CalcPlanesForPolygonBrushDouble(&polyd_brush); - return Collision_TraceBrushBrushDouble(thisbrush_start, thisbrush_end, &polyd_brush, &polyd_brush, impactnormal); + Collision_TraceBrushBrushDouble(trace, thisbrush_start, thisbrush_end, &polyd_brush, &polyd_brush); } @@ -790,15 +767,11 @@ double Collision_TraceBrushPolygonDouble(const colbrushd_t *thisbrush_start, con typedef struct colbrushbmodelinfo_s { model_t *model; + trace_t *trace; const matrix4x4_t *modelmatrixstart; const matrix4x4_t *modelmatrixend; const colbrushf_t *thisbrush_start; const colbrushf_t *thisbrush_end; - float impactnormal[3]; - float tempimpactnormal[3]; - float fraction; - int startsolid; - int allsolid; } colbrushbmodelinfo_t; @@ -810,7 +783,6 @@ void Collision_RecursiveTraceBrushNode(colbrushbmodelinfo_t *info, mnode_t *node { // collide with surfaces marked by this leaf int i, *mark; - float result; mleaf_t *leaf = (mleaf_t *)node; msurface_t *surf; for (i = 0, mark = leaf->firstmarksurface;i < leaf->nummarksurfaces;i++, mark++) @@ -822,22 +794,8 @@ void Collision_RecursiveTraceBrushNode(colbrushbmodelinfo_t *info, mnode_t *node surf->colframe = colframecount; if (surf->flags & SURF_SOLIDCLIP) { - result = Collision_TraceBrushPolygonFloat(info->thisbrush_start, info->thisbrush_end, surf->poly_numverts, surf->poly_verts, info->tempimpactnormal, &info->startsolid, &info->allsolid); - //result = Collision_TraceBrushPolygonTransformFloat(info->thisbrush_start, info->thisbrush_end, surf->poly_numverts, surf->poly_verts, info->tempimpactnormal, info->modelmatrixstart, info->modelmatrixend, &info->startsolid, &info->allsolid); - if (info->fraction > result) - { - info->fraction = result; - // use the surface's plane instead of the actual - // collision plane because the actual collision plane - // might be to the side (on a seam between polygons) - // or something, we want objects to bounce off the - // front... - //if (surf->flags & SURF_PLANEBACK) - // VectorNegate(surf->plane->normal, info->impactnormal); - //else - // VectorCopy(surf->plane->normal, info->impactnormal); - VectorCopy(info->tempimpactnormal, info->impactnormal); - } + Collision_TraceBrushPolygonFloat(info->trace, info->thisbrush_start, info->thisbrush_end, surf->poly_numverts, surf->poly_verts); + //Collision_TraceBrushPolygonTransformFloat(info->trace, info->thisbrush_start, info->thisbrush_end, surf->poly_numverts, surf->poly_verts, info->modelmatrixstart, info->modelmatrixend); } } } @@ -871,46 +829,32 @@ void Collision_RecursiveTraceBrushNode(colbrushbmodelinfo_t *info, mnode_t *node } } -float Collision_TraceBrushBModel(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, float *impactnormal, int *startsolid, int *allsolid) +void Collision_TraceBrushBModel(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model) { colbrushbmodelinfo_t info; colframecount++; + memset(trace, 0, sizeof(*trace)); + trace->fraction = 1; + info.trace = trace; info.model = model; info.thisbrush_start = thisbrush_start; info.thisbrush_end = thisbrush_end; - info.fraction = 1; - info.startsolid = false; - info.allsolid = false; Collision_RecursiveTraceBrushNode(&info, model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode); - if (info.fraction < 1) - VectorCopy(info.impactnormal, impactnormal); - if (startsolid) - *startsolid = info.startsolid; - if (allsolid) - *allsolid = info.allsolid; - return info.fraction; } -float Collision_TraceBrushBModelTransform(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, float *impactnormal, const matrix4x4_t *modelmatrixstart, const matrix4x4_t *modelmatrixend, int *startsolid, int *allsolid) +void Collision_TraceBrushBModelTransform(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, const matrix4x4_t *modelmatrixstart, const matrix4x4_t *modelmatrixend) { colbrushbmodelinfo_t info; colframecount++; + memset(trace, 0, sizeof(*trace)); + trace->fraction = 1; + info.trace = trace; info.model = model; info.modelmatrixstart = modelmatrixstart; info.modelmatrixend = modelmatrixend; info.thisbrush_start = thisbrush_start; info.thisbrush_end = thisbrush_end; - info.fraction = 1; - info.startsolid = false; - info.allsolid = false; - Collision_RecursiveTraceBrushNode(&info, model->brushq1.nodes); - if (info.fraction < 1) - VectorCopy(info.impactnormal, impactnormal); - if (startsolid) - *startsolid = info.startsolid; - if (allsolid) - *allsolid = info.allsolid; - return info.fraction; + Collision_RecursiveTraceBrushNode(&info, model->brushq1.nodes + model->brushq1.hulls[0].firstclipnode); } @@ -988,31 +932,30 @@ void Collision_PolygonClipTrace (trace_t *trace, const void *cent, model_t *cmod if (cmodel && cmodel->type == mod_brush) { // brush model - trace->fraction = Collision_TraceBrushBModel(thisbrush_start, thisbrush_end, cmodel, impactnormal, &trace->startsolid, &trace->allsolid); - //trace->fraction = Collision_TraceBrushBModelTransform(thisbrush_start, thisbrush_end, cmodel, trace->plane.normal, &cmatrix, &cmatrix, &trace->startsolid, &trace->allsolid); + Collision_TraceBrushBModel(trace, thisbrush_start, thisbrush_end, cmodel); + //Collision_TraceBrushBModelTransform(trace, thisbrush_start, thisbrush_end, cmodel, &cmatrix, &cmatrix); } else { // bounding box cbrush = Collision_BrushForBox(&identitymatrix, cmins, cmaxs); - trace->fraction = Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, cbrush, cbrush, impactnormal, &trace->startsolid, &trace->allsolid); + Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, cbrush, cbrush); //cbrush = Collision_BrushForBox(&cmatrix, cmins, cmaxs); - //trace->fraction = Collision_TraceBrushBrushFloat(thisbrush_start, thisbrush_end, cbrush, cbrush, trace->plane.normal, &trace->startsolid, &trace->allsolid); + //trace->fraction = Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, cbrush, cbrush); } if (trace->fraction < 0 || trace->fraction > 1) Con_Printf("fraction out of bounds %f %s:%d\n", trace->fraction, __FILE__, __LINE__); + VectorBlend(start, end, trace->fraction, trace->endpos); if (trace->fraction < 1) { trace->ent = (void *) cent; - VectorBlend(start, end, trace->fraction, trace->endpos); + VectorCopy(trace->plane.normal, impactnormal); Matrix4x4_Transform(&cmatrix, impactnormal, trace->plane.normal); VectorNormalize(trace->plane.normal); //Con_Printf("fraction %f normal %f %f %f\n", trace->fraction, trace->plane.normal[0], trace->plane.normal[1], trace->plane.normal[2]); } - else - VectorCopy(end, trace->endpos); } diff --git a/collision.h b/collision.h index 90f5df7d..0e746e4e 100644 --- a/collision.h +++ b/collision.h @@ -65,9 +65,9 @@ colbrushf_t; colbrushf_t *Collision_AllocBrushFloat(mempool_t *mempool, int numpoints, int numplanes); void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush); colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points); -float Collision_TraceBrushBrushFloat(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, const colbrushf_t *thatbrush_start, const colbrushf_t *thatbrush_end, float *impactnormal, int *startsolid, int *allsolid); -float Collision_TraceBrushPolygonFloat(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, float *impactnormal, int *startsolid, int *allsolid); -float Collision_TraceBrushPolygonTransformFloat(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, float *impactnormal, const matrix4x4_t *polygonmatrixstart, const matrix4x4_t *polygonmatrixend, int *startsolid, int *allsolid); +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); +void Collision_TraceBrushPolygonFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points); +void Collision_TraceBrushPolygonTransformFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numpoints, const float *points, const matrix4x4_t *polygonmatrixstart, const matrix4x4_t *polygonmatrixend); typedef struct colpointd_s { @@ -94,12 +94,14 @@ colbrushd_t; colbrushd_t *Collision_AllocBrushDouble(mempool_t *mempool, int numpoints, int numplanes); void Collision_CalcPlanesForPolygonBrushDouble(colbrushd_t *brush); colbrushd_t *Collision_AllocBrushFromPermanentPolygonDouble(mempool_t *mempool, int numpoints, double *points); -double Collision_TraceBrushBrushDouble(const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, const colbrushd_t *thatbrush_start, const colbrushd_t *thatbrush_end, double *impactnormal); -double Collision_TraceBrushPolygonDouble(const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, int numpoints, const double *points, double *impactnormal); +void Collision_TraceBrushBrushDouble(trace_t *trace, const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, const colbrushd_t *thatbrush_start, const colbrushd_t *thatbrush_end); +void Collision_TraceBrushPolygonDouble(trace_t *trace, const colbrushd_t *thisbrush_start, const colbrushd_t *thisbrush_end, int numpoints, const double *points); -float Collision_TraceBrushBModel(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, float *impactnormal, int *startsolid, int *allsolid); -float Collision_TraceBrushBModelTransform(const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, float *impactnormal, const matrix4x4_t *modelmatrixstart, const matrix4x4_t *modelmatrixend, int *startsolid, int *allsolid); +void Collision_TraceBrushBModel(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model); +void Collision_TraceBrushBModelTransform(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, model_t *model, const matrix4x4_t *modelmatrixstart, const matrix4x4_t *modelmatrixend); void Collision_PolygonClipTrace(trace_t *trace, const void *cent, model_t *cmodel, const vec3_t corigin, const vec3_t cangles, const vec3_t cmins, const vec3_t cmaxs, const vec3_t start, const vec3_t mins, const vec3_t maxs, const vec3_t end); +colbrushf_t *Collision_BrushForBox(const matrix4x4_t *matrix, const vec3_t mins, const vec3_t maxs); + #endif diff --git a/model_brush.c b/model_brush.c index df7b4dce..5b36c156 100644 --- a/model_brush.c +++ b/model_brush.c @@ -3587,7 +3587,10 @@ static void Mod_Q3BSP_LoadBrushes(lump_t *l) { q3dbrush_t *in; q3mbrush_t *out; - int i, n, c, count; + int i, j, k, m, n, c, count, numpoints, numplanes; + winding_t *w; + colpointf_t pointsbuf[256*3]; + colplanef_t planesbuf[256], colplanef; in = (void *)(mod_base + l->fileofs); if (l->filelen % sizeof(*in)) @@ -3610,6 +3613,75 @@ static void Mod_Q3BSP_LoadBrushes(lump_t *l) if (n < 0 || n >= loadmodel->brushq3.num_textures) Host_Error("Mod_Q3BSP_LoadBrushes: invalid textureindex %i (%i textures)\n", n, loadmodel->brushq3.num_textures); out->texture = loadmodel->brushq3.data_textures + n; + + // construct a collision brush, which needs points and planes... + // each point and plane should be unique, and they don't refer to + // eachother in any way, so keeping them unique is fairly easy + numpoints = 0; + numplanes = 0; + for (j = 0;j < out->numbrushsides;j++) + { + // create a huge polygon for the plane + w = BaseWindingForPlane(out->firstbrushside[j].plane); + // clip it by all other planes + for (k = 0;k < out->numbrushsides && w;k++) + if (k != j) + w = ClipWinding(w, out->firstbrushside[k].plane, true); + // if nothing is left, skip it + // FIXME: should keep count of how many were skipped and report + // it, just for sake of statistics + if (!w) + continue; + // add the points uniquely (no duplicates) + for (k = 0;k < w->numpoints;k++) + { + for (m = 0;m < numpoints;m++) + if (VectorDistance2(w->points[k * 3], pointsbuf[m * 3].v) < DIST_EPSILON) + break; + if (m == numpoints) + { + // check if there are too many and skip the brush + if (numpoints >= 256) + { + Con_Printf("Mod_Q3BSP_LoadBrushes: failed to build collision brush: too many points for buffer\n"); + FreeWinding(w); + goto failedtomakecolbrush; + } + // add the new one + VectorCopy(w->points[k * 3], pointsbuf[numpoints * 3].v); + numpoints++; + } + } + // add the plane uniquely (no duplicates) + memset(&colplanef, 0, sizeof(colplanef)); + VectorCopy(out->firstbrushside[k].plane->normal, colplanef.normal); + colplanef.dist = out->firstbrushside[k].plane->dist; + for (k = 0;k < numplanes;k++) + if (VectorCompare(planesbuf[k].normal, colplanef.normal) && planesbuf[k].dist == colplanef.dist) + break; + if (k == numplanes) + { + // check if there are too many and skip the brush + if (numplanes >= 256) + { + Con_Printf("Mod_Q3BSP_LoadBrushes: failed to build collision brush: too many planes for buffer\n"); + FreeWinding(w); + goto failedtomakecolbrush; + } + // add the new one + planesbuf[numplanes++] = colplanef; + } + FreeWinding(w); + } + // if anything is left, create the collision brush + if (numplanes && numpoints) + { + out->colbrushf = Collision_AllocBrushFloat(loadmodel->mempool, numpoints, numplanes); + memcpy(out->colbrushf->points, pointsbuf, numpoints * sizeof(float[3])); + memcpy(out->colbrushf->planes, planesbuf, numplanes * sizeof(mplane_t)); + } + // return from errors to here + failedtomakecolbrush:; } } @@ -4103,6 +4175,77 @@ static void Mod_Q3BSP_LoadPVS(lump_t *l) memcpy(loadmodel->brushq3.data_pvschains, (qbyte *)(in + 1), totalchains); } +void Mod_Q3BSP_FindNonSolidLocation(model_t *model, const vec3_t in, vec3_t out, vec_t radius) +{ + // FIXME: finish this code + VectorCopy(in, out); +} + +void Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace_t *trace, q3mnode_t *node, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end) +{ + if (node->isnode) + { + // recurse down node sides + int i; + float dist; + colpointf_t *ps, *pe; + // FIXME? if TraceBrushPolygonTransform were to be made usable, the + // node planes would need to be transformed too + dist = node->plane->dist - (1.0f / 8.0f); + for (i = 0, ps = thisbrush_start->points, pe = thisbrush_end->points;i < thisbrush_start->numpoints;i++, ps++, pe++) + { + if (DotProduct(ps->v, node->plane->normal) > dist || DotProduct(pe->v, node->plane->normal) > dist) + { + Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[0], thisbrush_start, thisbrush_end); + break; + } + } + dist = node->plane->dist + (1.0f / 8.0f); + for (i = 0, ps = thisbrush_start->points, pe = thisbrush_end->points;i < thisbrush_start->numpoints;i++, ps++, pe++) + { + if (DotProduct(ps->v, node->plane->normal) < dist || DotProduct(pe->v, node->plane->normal) < dist) + { + Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, node->children[1], thisbrush_start, thisbrush_end); + break; + } + } + /* + sides = BoxOnPlaneSide(boxstartmins, boxstartmaxs, node->plane) | BoxOnPlaneSide(boxendmins, boxendmaxs, node->plane); + if (sides & 1) + Mod_Q3BSP_TraceBox_RecursiveBSPNode(trace, node->children[0], boxstartmins, boxstartmaxs, boxendmins, boxendmaxs); + if (sides & 2) + Mod_Q3BSP_TraceBox_RecursiveBSPNode(trace, node->children[1], boxstartmins, boxstartmaxs, boxendmins, boxendmaxs); + */ + } + else + { + int i; + q3mleaf_t *leaf; + leaf = (q3mleaf_t *)node; + for (i = 0;i < leaf->numleafbrushes;i++) + Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, leaf->firstleafbrush[i]->colbrushf, leaf->firstleafbrush[i]->colbrushf); + } +} + +void Mod_Q3BSP_TraceBox(model_t *model, trace_t *trace, const vec3_t boxstartmins, const vec3_t boxstartmaxs, const vec3_t boxendmins, const vec3_t boxendmaxs) +{ + int i; + colbrushf_t *thisbrush_start, *thisbrush_end; + matrix4x4_t startmatrix, endmatrix; + // FIXME: finish this code + Matrix4x4_CreateIdentity(&startmatrix); + Matrix4x4_CreateIdentity(&endmatrix); + thisbrush_start = Collision_BrushForBox(&startmatrix, boxstartmins, boxstartmaxs); + thisbrush_end = Collision_BrushForBox(&endmatrix, boxendmins, boxendmaxs); + memset(trace, 0, sizeof(*trace)); + trace->fraction = 1; + if (model->brushq3.num_nodes) + Mod_Q3BSP_TraceBrush_RecursiveBSPNode(trace, model->brushq3.data_nodes, thisbrush_start, thisbrush_end); + else + for (i = 0;i < model->brushq3.num_brushes;i++) + Collision_TraceBrushBrushFloat(trace, thisbrush_start, thisbrush_end, model->brushq3.data_brushes[i].colbrushf, model->brushq3.data_brushes[i].colbrushf); +} + void Mod_Q3BSP_Load(model_t *mod, void *buffer) { int i; @@ -4122,6 +4265,12 @@ void Mod_Q3BSP_Load(model_t *mod, void *buffer) R_ResetQuakeSky(); } + mod->brush.FindNonSolidLocation = Mod_Q3BSP_FindNonSolidLocation; + mod->brush.TraceBox = Mod_Q3BSP_TraceBox; + //mod->brushq1.PointInLeaf = Mod_Q1BSP_PointInLeaf; + //mod->brushq1.LeafPVS = Mod_Q1BSP_LeafPVS; + //mod->brushq1.BuildPVSTextureChains = Mod_Q1BSP_BuildPVSTextureChains; + mod_base = (qbyte *)header; // swap all the lumps diff --git a/model_shared.h b/model_shared.h index 0d22a501..fd989b5c 100644 --- a/model_shared.h +++ b/model_shared.h @@ -299,6 +299,7 @@ q3mmodel_t; typedef struct q3mbrush_s { + struct colbrushf_s *colbrushf; int numbrushsides; struct q3mbrushside_s *firstbrushside; struct q3mtexture_s *texture; -- 2.39.2