From 1ca72567ff491c3ef09329d3373802ed6cdb9a38 Mon Sep 17 00:00:00 2001 From: havoc Date: Mon, 31 Jul 2006 09:59:14 +0000 Subject: [PATCH] improved plane distance epsilon checking and improved precision when converting brush planes to polygons (by finding a roughly minimal bounding box for the plane to polygon projection), this should reduce collision brush issues on modeled terrain in q3bsp maps git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@6537 d7cf8633-e32d-0410-b094-e92efae38249 --- collision.c | 30 +++++++++++++++++++----------- gl_rmain.c | 47 +++++++++++++++++++++++++++++++++++++++-------- model_brush.c | 6 ++++-- 3 files changed, 62 insertions(+), 21 deletions(-) diff --git a/collision.c b/collision.c index 82e65b0a..ca95a54b 100644 --- a/collision.c +++ b/collision.c @@ -2,8 +2,9 @@ #include "quakedef.h" #include "polygon.h" -#define COLLISION_SNAPSCALE (8.0f) +#define COLLISION_SNAPSCALE (32.0f) #define COLLISION_SNAP (1.0f / COLLISION_SNAPSCALE) +#define COLLISION_PLANE_DIST_EPSILON (1.0f / 32.0f) 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"}; @@ -76,12 +77,12 @@ void Collision_ValidateBrush(colbrushf_t *brush) 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)) + if (d > COLLISION_PLANE_DIST_EPSILON) { 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.125f) + if (fabs(d) > COLLISION_PLANE_DIST_EPSILON) pointsoffplanes++; else pointonplanes++; @@ -138,6 +139,7 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla // TODO: planesbuf could be replaced by a remapping table int j, k, m, w; int numpointsbuf = 0, maxpointsbuf = 256, numplanesbuf = 0, maxplanesbuf = 256, numelementsbuf = 0, maxelementsbuf = 256; + double maxdist; colbrushf_t *brush; colpointf_t pointsbuf[256]; colplanef_t planesbuf[256]; @@ -154,6 +156,12 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla memset(polypointbuf, 0, sizeof(polypointbuf)); memset(p, 0, sizeof(p)); #endif + // figure out how large a bounding box we need to properly compute this brush + maxdist = 0; + for (j = 0;j < numoriginalplanes;j++) + maxdist = max(maxdist, originalplanes[j].dist); + // now make it large enough to enclose the entire brush, and round it off to a reasonable multiple of 1024 + maxdist = floor(maxdist * (4.0 / 1024.0) + 1) * 1024.0; // 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) @@ -175,7 +183,7 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla // create a large polygon from the plane w = 0; - PolygonD_QuadForPlane(p[w], originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist, 1024.0*1024.0*1024.0); + PolygonD_QuadForPlane(p[w], originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist, maxdist); pnumpoints = 4; // clip it by all other planes for (k = 0;k < numoriginalplanes && pnumpoints && pnumpoints <= pmaxpoints;k++) @@ -184,7 +192,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, NULL); + PolygonD_Divide(pnumpoints, p[w], -originalplanes[k].normal[0], -originalplanes[k].normal[1], -originalplanes[k].normal[2], -originalplanes[k].dist, COLLISION_PLANE_DIST_EPSILON, pmaxpoints, p[!w], &pnumpoints, 0, NULL, NULL, NULL); w = !w; } } @@ -200,7 +208,7 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla 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) + if (fabs(DotProduct(&p[w][k*3], originalplanes[l].normal) - originalplanes[l].dist) < COLLISION_PLANE_DIST_EPSILON) m++; if (m < 3) break; @@ -271,7 +279,7 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla for (j = 0;j < numplanesbuf;j++) { float d = furthestplanedist_float(planesbuf[j].normal, pointsbuf, numpointsbuf); - if (fabs(planesbuf[j].dist - d) > (1.0f/32.0f)) + if (fabs(planesbuf[j].dist - d) > COLLISION_PLANE_DIST_EPSILON) Con_Printf("plane %f %f %f %f mismatches dist %f\n", planesbuf[j].normal[0], planesbuf[j].normal[1], planesbuf[j].normal[2], planesbuf[j].dist, d); } @@ -494,7 +502,7 @@ void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush) { int j; for (j = 0, p = brush->points;j < brush->numpoints;j++, p++) - if (DotProduct(p->v, brush->planes[i].normal) > brush->planes[i].dist + (1.0 / 32.0)) + if (DotProduct(p->v, brush->planes[i].normal) > brush->planes[i].dist + COLLISION_PLANE_DIST_EPSILON) Con_Printf("Error in brush plane generation, plane %i\n", i); } } @@ -540,7 +548,7 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush return; } f = furthestplanedist_float(startplane->normal, thisbrush_start->points, thisbrush_start->numpoints); - if (fabs(f - startplane->dist) > 0.125f) + if (fabs(f - startplane->dist) > COLLISION_PLANE_DIST_EPSILON) 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) - collision_startnudge.value; @@ -559,7 +567,7 @@ void Collision_TraceBrushBrushFloat(trace_t *trace, const colbrushf_t *thisbrush return; } f = furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints); - if (fabs(f - startplane->dist) > 0.125f) + if (fabs(f - startplane->dist) > COLLISION_PLANE_DIST_EPSILON) 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 - collision_startnudge.value; @@ -685,7 +693,7 @@ void Collision_TraceLineBrushFloat(trace_t *trace, const vec3_t linestart, const if (thatbrush_start->numpoints) { f = furthestplanedist_float(startplane->normal, thatbrush_start->points, thatbrush_start->numpoints); - if (fabs(f - startplane->dist) > 0.125f) + if (fabs(f - startplane->dist) > COLLISION_PLANE_DIST_EPSILON) Con_Printf("startplane->dist %f != calculated %f\n", startplane->dist, f); } } diff --git a/gl_rmain.c b/gl_rmain.c index 7f3c26b0..f760fa9d 100644 --- a/gl_rmain.c +++ b/gl_rmain.c @@ -2225,10 +2225,12 @@ void R_DrawSprite(int blendfunc1, int blendfunc2, rtexture_t *texture, rtexture_ } } -int R_Mesh_AddVertex3f(rmesh_t *mesh, const float *v) +int R_Mesh_AddVertex(rmesh_t *mesh, float x, float y, float z) { int i; float *vertex3f; + float v[3]; + VectorSet(v, x, y, z); for (i = 0, vertex3f = mesh->vertex3f;i < mesh->numvertices;i++, vertex3f += 3) if (VectorDistance2(v, vertex3f) < mesh->epsilon2) break; @@ -2249,12 +2251,12 @@ void R_Mesh_AddPolygon3f(rmesh_t *mesh, int numvertices, float *vertex3f) { int i; int *e, element[3]; - element[0] = R_Mesh_AddVertex3f(mesh, vertex3f);vertex3f += 3; - element[1] = R_Mesh_AddVertex3f(mesh, vertex3f);vertex3f += 3; + element[0] = R_Mesh_AddVertex(mesh, vertex3f[0], vertex3f[1], vertex3f[2]);vertex3f += 3; + element[1] = R_Mesh_AddVertex(mesh, vertex3f[0], vertex3f[1], vertex3f[2]);vertex3f += 3; e = mesh->element3i + mesh->numtriangles * 3; for (i = 0;i < numvertices - 2;i++, vertex3f += 3) { - element[2] = R_Mesh_AddVertex3f(mesh, vertex3f); + element[2] = R_Mesh_AddVertex(mesh, vertex3f[0], vertex3f[1], vertex3f[2]); if (mesh->numtriangles < mesh->maxtriangles) { *e++ = element[0]; @@ -2266,29 +2268,58 @@ void R_Mesh_AddPolygon3f(rmesh_t *mesh, int numvertices, float *vertex3f) } } +void R_Mesh_AddPolygon3d(rmesh_t *mesh, int numvertices, double *vertex3d) +{ + int i; + int *e, element[3]; + element[0] = R_Mesh_AddVertex(mesh, vertex3d[0], vertex3d[1], vertex3d[2]);vertex3d += 3; + element[1] = R_Mesh_AddVertex(mesh, vertex3d[0], vertex3d[1], vertex3d[2]);vertex3d += 3; + e = mesh->element3i + mesh->numtriangles * 3; + for (i = 0;i < numvertices - 2;i++, vertex3d += 3) + { + element[2] = R_Mesh_AddVertex(mesh, vertex3d[0], vertex3d[1], vertex3d[2]); + if (mesh->numtriangles < mesh->maxtriangles) + { + *e++ = element[0]; + *e++ = element[1]; + *e++ = element[2]; + mesh->numtriangles++; + } + element[1] = element[2]; + } +} + +#define R_MESH_PLANE_DIST_EPSILON (1.0 / 32.0) void R_Mesh_AddBrushMeshFromPlanes(rmesh_t *mesh, int numplanes, mplane_t *planes) { int planenum, planenum2; int w; int tempnumpoints; mplane_t *plane, *plane2; - float temppoints[2][256*3]; + double maxdist; + double temppoints[2][256*3]; + // figure out how large a bounding box we need to properly compute this brush + maxdist = 0; + for (w = 0;w < numplanes;w++) + maxdist = max(maxdist, planes[w].dist); + // now make it large enough to enclose the entire brush, and round it off to a reasonable multiple of 1024 + maxdist = floor(maxdist * (4.0 / 1024.0) + 1) * 1024.0; for (planenum = 0, plane = planes;planenum < numplanes;planenum++, plane++) { w = 0; tempnumpoints = 4; - PolygonF_QuadForPlane(temppoints[w], plane->normal[0], plane->normal[1], plane->normal[2], plane->normal[3], 1024.0*1024.0*1024.0); + PolygonD_QuadForPlane(temppoints[w], plane->normal[0], plane->normal[1], plane->normal[2], plane->normal[3], maxdist); for (planenum2 = 0, plane2 = planes;planenum2 < numplanes && tempnumpoints >= 3;planenum2++, plane2++) { if (planenum2 == planenum) continue; - PolygonF_Divide(tempnumpoints, temppoints[w], plane2->normal[0], plane2->normal[1], plane2->normal[2], plane2->dist, 1.0/32.0, 0, NULL, NULL, 256, temppoints[!w], &tempnumpoints, NULL); + PolygonD_Divide(tempnumpoints, temppoints[w], plane2->normal[0], plane2->normal[1], plane2->normal[2], plane2->dist, R_MESH_PLANE_DIST_EPSILON, 0, NULL, NULL, 256, temppoints[!w], &tempnumpoints, NULL); w = !w; } if (tempnumpoints < 3) continue; // generate elements forming a triangle fan for this polygon - R_Mesh_AddPolygon3f(mesh, tempnumpoints, temppoints[w]); + R_Mesh_AddPolygon3d(mesh, tempnumpoints, temppoints[w]); } } diff --git a/model_brush.c b/model_brush.c index d84967f8..c6caa6bd 100644 --- a/model_brush.c +++ b/model_brush.c @@ -2832,6 +2832,7 @@ static void RemovePortalFromNodes(portal_t *portal) } } +#define PORTAL_DIST_EPSILON (1.0 / 32.0) static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node) { int i, side; @@ -2857,6 +2858,7 @@ static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node) nodeportal = AllocPortal(); nodeportal->plane = *plane; + // TODO: calculate node bounding boxes during recursion and calculate a maximum plane size accordingly to improve precision (as most maps do not need 1 billion unit plane polygons) PolygonD_QuadForPlane(nodeportal->points, nodeportal->plane.normal[0], nodeportal->plane.normal[1], nodeportal->plane.normal[2], nodeportal->plane.dist, 1024.0*1024.0*1024.0); nodeportal->numpoints = 4; side = 0; // shut up compiler warning @@ -2878,7 +2880,7 @@ static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node) for (i = 0;i < nodeportal->numpoints*3;i++) frontpoints[i] = nodeportal->points[i]; - PolygonD_Divide(nodeportal->numpoints, frontpoints, clipplane.normal[0], clipplane.normal[1], clipplane.normal[2], clipplane.dist, 1.0/32.0, MAX_PORTALPOINTS, nodeportal->points, &nodeportal->numpoints, 0, NULL, NULL, NULL); + PolygonD_Divide(nodeportal->numpoints, frontpoints, clipplane.normal[0], clipplane.normal[1], clipplane.normal[2], clipplane.dist, PORTAL_DIST_EPSILON, MAX_PORTALPOINTS, nodeportal->points, &nodeportal->numpoints, 0, NULL, NULL, NULL); if (nodeportal->numpoints <= 0 || nodeportal->numpoints >= MAX_PORTALPOINTS) break; } @@ -2916,7 +2918,7 @@ static void Mod_Q1BSP_RecursiveNodePortals(mnode_t *node) RemovePortalFromNodes(portal); // cut the portal into two portals, one on each side of the node plane - PolygonD_Divide(portal->numpoints, portal->points, plane->normal[0], plane->normal[1], plane->normal[2], plane->dist, 1.0/32.0, MAX_PORTALPOINTS, frontpoints, &numfrontpoints, MAX_PORTALPOINTS, backpoints, &numbackpoints, NULL); + PolygonD_Divide(portal->numpoints, portal->points, plane->normal[0], plane->normal[1], plane->normal[2], plane->dist, PORTAL_DIST_EPSILON, MAX_PORTALPOINTS, frontpoints, &numfrontpoints, MAX_PORTALPOINTS, backpoints, &numbackpoints, NULL); if (!numfrontpoints) { -- 2.39.2