From 19fc2b9ed255622fe0bad9841c9fd0b7383988d7 Mon Sep 17 00:00:00 2001 From: havoc Date: Wed, 8 Oct 2003 20:50:28 +0000 Subject: [PATCH] collision brush generation in q3bsp is now *MUCH* faster and uses a lot less memory (technical: now uses two temp windings, repeatedly swapping between them, avoiding all the temporary allocs, to achieve this BufWinding_NewFromPlane and BufWinding_Divide were added) git-svn-id: svn://svn.icculus.org/twilight/trunk/darkplaces@3553 d7cf8633-e32d-0410-b094-e92efae38249 --- collision.c | 20 ++- collision.h | 4 +- model_brush.c | 26 ++-- winding.c | 354 ++++++++++++++++++++++++++++++++++++-------------- winding.h | 4 +- 5 files changed, 291 insertions(+), 117 deletions(-) diff --git a/collision.c b/collision.c index 1c4a4fe6..c05dcbcb 100644 --- a/collision.c +++ b/collision.c @@ -363,11 +363,11 @@ 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) +colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const mplane_t *originalplanes, int supercontents, winding_t *temp1, winding_t *temp2) { int j, k, m; int numpoints, maxpoints, numplanes, maxplanes, numelements, maxelements, numtriangles, numpolypoints, maxpolypoints; - winding_t *w; + winding_t *w, *temp, *othertemp; colbrushf_t *brush; colpointf_t pointsbuf[256]; colplanef_t planesbuf[256]; @@ -399,19 +399,24 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla } // 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 = temp1; + othertemp = temp2; + BufWinding_NewFromPlane(w, originalplanes[j].normal[0], originalplanes[j].normal[1], originalplanes[j].normal[2], originalplanes[j].dist); // clip it by all other planes - for (k = 0;k < numoriginalplanes && w;k++) + for (k = 0;k < numoriginalplanes && w->numpoints;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); + BufWinding_Divide(w, -originalplanes[k].normal[0], -originalplanes[k].normal[1], -originalplanes[k].normal[2], -originalplanes[k].dist, othertemp, NULL, NULL, NULL); + temp = w; + w = othertemp; + othertemp = temp; } } // if nothing is left, skip it - if (!w) + if (!w->numpoints) continue; // copy off the number of points for later when the winding is freed @@ -456,8 +461,9 @@ colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalpla // store the index into a buffer polypointbuf[k] = m; } - Winding_Free(w); w = NULL; + othertemp = NULL; + temp = NULL; // add the triangles for the polygon // (this particular code makes a triangle fan) diff --git a/collision.h b/collision.h index ad391c66..030554ac 100644 --- a/collision.h +++ b/collision.h @@ -2,6 +2,8 @@ #ifndef COLLISION_H #define COLLISION_H +#include "winding.h" + typedef struct plane_s { vec3_t normal; @@ -85,7 +87,7 @@ colbrushf_t; colbrushf_t *Collision_AllocBrushFloat(mempool_t *mempool, int numpoints, int numplanes, int numtriangles, int supercontents); void Collision_CalcPlanesForPolygonBrushFloat(colbrushf_t *brush); colbrushf_t *Collision_AllocBrushFromPermanentPolygonFloat(mempool_t *mempool, int numpoints, float *points, int supercontents); -colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const mplane_t *originalplanes, int supercontents); +colbrushf_t *Collision_NewBrushFromPlanes(mempool_t *mempool, int numoriginalplanes, const mplane_t *originalplanes, int supercontents, winding_t *temp1, winding_t *temp2); 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, int supercontents); void Collision_TraceBrushTriangleMeshFloat(trace_t *trace, const colbrushf_t *thisbrush_start, const colbrushf_t *thisbrush_end, int numtriangles, const int *element3i, const float *vertex3f, int supercontents, const vec3_t segmentmins, const vec3_t segmentmaxs); diff --git a/model_brush.c b/model_brush.c index 2af3492e..19aaf6aa 100644 --- a/model_brush.c +++ b/model_brush.c @@ -3389,6 +3389,7 @@ static void Mod_Q3BSP_LoadBrushes(lump_t *l) q3mbrush_t *out; int i, j, n, c, count, maxplanes; mplane_t *planes; + winding_t *temp1, *temp2; in = (void *)(mod_base + l->fileofs); if (l->filelen % sizeof(*in)) @@ -3399,6 +3400,9 @@ static void Mod_Q3BSP_LoadBrushes(lump_t *l) loadmodel->brushq3.data_brushes = out; loadmodel->brushq3.num_brushes = count; + temp1 = Winding_New(64); + temp2 = Winding_New(64); + maxplanes = 0; planes = NULL; @@ -3429,10 +3433,12 @@ static void Mod_Q3BSP_LoadBrushes(lump_t *l) planes[j].dist = out->firstbrushside[j].plane->dist; } // make the colbrush from the planes - out->colbrushf = Collision_NewBrushFromPlanes(loadmodel->mempool, out->numbrushsides, planes, out->texture->supercontents); + out->colbrushf = Collision_NewBrushFromPlanes(loadmodel->mempool, out->numbrushsides, planes, out->texture->supercontents, temp1, temp2); } if (planes) Mem_Free(planes); + Winding_Free(temp1); + Winding_Free(temp2); } static void Mod_Q3BSP_LoadEffects(lump_t *l) @@ -3470,13 +3476,13 @@ static void Mod_Q3BSP_LoadVertices(lump_t *l) if (l->filelen % sizeof(*in)) Host_Error("Mod_Q3BSP_LoadVertices: funny lump size in %s",loadmodel->name); loadmodel->brushq3.num_vertices = count = l->filelen / sizeof(*in); - loadmodel->brushq3.data_vertex3f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[3])); - loadmodel->brushq3.data_texcoordtexture2f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[2])); - loadmodel->brushq3.data_texcoordlightmap2f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[2])); - loadmodel->brushq3.data_svector3f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[3])); - loadmodel->brushq3.data_tvector3f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[3])); - loadmodel->brushq3.data_normal3f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[3])); - loadmodel->brushq3.data_color4f = Mem_Alloc(loadmodel->mempool, count * sizeof(float[4])); + loadmodel->brushq3.data_vertex3f = Mem_Alloc(loadmodel->mempool, count * (sizeof(float) * (3 + 2 + 2 + 3 + 3 + 3 + 4))); + loadmodel->brushq3.data_texcoordtexture2f = loadmodel->brushq3.data_vertex3f + count * 3; + loadmodel->brushq3.data_texcoordlightmap2f = loadmodel->brushq3.data_texcoordtexture2f + count * 2; + loadmodel->brushq3.data_svector3f = loadmodel->brushq3.data_texcoordlightmap2f + count * 2; + loadmodel->brushq3.data_tvector3f = loadmodel->brushq3.data_svector3f + count * 3; + loadmodel->brushq3.data_normal3f = loadmodel->brushq3.data_tvector3f + count * 3; + loadmodel->brushq3.data_color4f = loadmodel->brushq3.data_normal3f + count * 3; for (i = 0;i < count;i++, in++) { @@ -3514,11 +3520,11 @@ static void Mod_Q3BSP_LoadTriangles(lump_t *l) if (l->filelen % sizeof(int[3])) Host_Error("Mod_Q3BSP_LoadTriangles: funny lump size in %s",loadmodel->name); count = l->filelen / sizeof(*in); - out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out)); + out = Mem_Alloc(loadmodel->mempool, count * sizeof(*out) * 2); loadmodel->brushq3.num_triangles = count / 3; loadmodel->brushq3.data_element3i = out; - loadmodel->brushq3.data_neighbor3i = Mem_Alloc(loadmodel->mempool, count * sizeof(*out)); + loadmodel->brushq3.data_neighbor3i = out + count; for (i = 0;i < count;i++, in++, out++) { diff --git a/winding.c b/winding.c index 24409026..2533224a 100644 --- a/winding.c +++ b/winding.c @@ -9,16 +9,8 @@ winding_t *Winding_New(int points) { winding_t *w; - int size; - - if (points > MAX_POINTS_ON_WINDING) - Sys_Error("Winding_New: too many points\n"); - - size = sizeof(winding_t) + sizeof(double[3]) * (points - 8); - w = Mem_Alloc(loadmodel->mempool, size); - //Mem_Alloc clears - //memset(w, 0, size); - + w = Mem_Alloc(loadmodel->mempool, sizeof(winding_t) + sizeof(double[3]) * (points - 8)); + w->maxpoints = points; return w; } @@ -29,83 +21,9 @@ void Winding_Free(winding_t *w) winding_t *Winding_NewFromPlane(double normalx, double normaly, double normalz, double dist) { - int x; - double max, v, org[3], vright[3], vup[3], normal[3]; winding_t *w; - - normal[0] = normalx; - normal[1] = normaly; - normal[2] = normalz; -#if 0 - VectorVectorsDouble(normal, vright, vup); -#else - // find the major axis - x = 0; - max = fabs(normal[0]); - v = fabs(normal[1]); - if(v > max) - { - x = 1; - max = v; - } - v = fabs(normal[2]); - if(v > max) - { - x = 2; - max = v; - } - - VectorClear(vup); - switch(x) - { - case 0: - case 1: - vup[2] = 1; - break; - case 2: - vup[0] = 1; - break; - } - - v = DotProduct(vup, normal); - VectorMA(vup, -v, normal, vup); - VectorNormalize(vup); -#endif - - VectorScale(normal, dist, org); - - CrossProduct(vup, normal, vright); - - VectorScale(vup, 1024.0*1024.0*1024.0, vup); - VectorScale(vright, 1024.0*1024.0*1024.0, vright); - - // project a really big axis aligned box onto the plane w = Winding_New(4); - - VectorSubtract(org, vright, w->points[0]); - VectorAdd(w->points[0], vup, w->points[0]); - - VectorAdd(org, vright, w->points[1]); - VectorAdd(w->points[1], vup, w->points[1]); - - VectorAdd(org, vright, w->points[2]); - VectorSubtract(w->points[2], vup, w->points[2]); - - VectorSubtract(org, vright, w->points[3]); - VectorSubtract(w->points[3], vup, w->points[3]); - -#if 0 - { - double n[3]; - TriangleNormal(w->points[0], w->points[1], w->points[2], n); - VectorNormalize(n); - if (fabs(DotProduct(n, normal) - 1) > 0.01f) - Con_Printf("%.0f %.0f %.0f (%.0f %.0f %.0f, %.0f %.0f %.0f) != %.0f %.0f %.0f (%.0f %.0f %.0f, %.0f %.0f %.0f, %.0f %.0f %.0f, %.0f %.0f %.0f)\n", normal[0], normal[1], normal[2], vright[0], vright[1], vright[2], vup[0], vup[1], vup[2], n[0], n[1], n[2], w->points[0][0], w->points[0][1], w->points[0][2], w->points[1][0], w->points[1][1], w->points[1][2], w->points[2][0], w->points[2][1], w->points[2][2], w->points[3][0], w->points[3][1], w->points[3][2]); - } -#endif - - w->numpoints = 4; - + BufWinding_NewFromPlane(w, normalx, normaly, normalz, dist); return w; } @@ -150,7 +68,21 @@ winding_t *Winding_Clip(winding_t *in, double splitnormalx, double splitnormaly, if (!counts[1]) return in; - maxpts = in->numpoints+4; // can't use counts[0]+2 because of fp grouping errors + maxpts = 0; + for (i = 0;i < in->numpoints;i++) + { + if (sides[i] == SIDE_ON) + { + maxpts++; + continue; + } + if (sides[i] == SIDE_FRONT) + maxpts++; + if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) + continue; + maxpts++; + } + if (maxpts > MAX_POINTS_ON_WINDING) Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING"); @@ -158,9 +90,6 @@ winding_t *Winding_Clip(winding_t *in, double splitnormalx, double splitnormaly, for (i = 0;i < in->numpoints;i++) { - if (neww->numpoints >= maxpts) - Sys_Error("Winding_Clip: points exceeded estimate"); - p1 = in->points[i]; if (sides[i] == SIDE_ON) @@ -212,7 +141,7 @@ void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, dou { winding_t *f, *b; double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1]; - int i, j, maxpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1]; + int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1]; splitnormal[0] = splitnormalx; splitnormal[1] = splitnormaly; @@ -247,19 +176,37 @@ void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, dou return; } - maxpts = in->numpoints+4; // can't use counts[0]+2 because of fp grouping errors + frontpts = 0; + backpts = 0; - if (maxpts > MAX_POINTS_ON_WINDING) - Sys_Error("Winding_Clip: maxpts > MAX_POINTS_ON_WINDING"); + for (i = 0;i < in->numpoints;i++) + { + if (sides[i] == SIDE_ON) + { + frontpts++; + backpts++; + continue; + } + if (sides[i] == SIDE_FRONT) + frontpts++; + else if (sides[i] == SIDE_BACK) + backpts++; + if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) + continue; + frontpts++; + backpts++; + } - *front = f = Winding_New(maxpts); - *back = b = Winding_New(maxpts); + if (frontpts > MAX_POINTS_ON_WINDING) + Sys_Error("Winding_Clip: frontpts > MAX_POINTS_ON_WINDING"); + if (backpts > MAX_POINTS_ON_WINDING) + Sys_Error("Winding_Clip: backpts > MAX_POINTS_ON_WINDING"); + + *front = f = Winding_New(frontpts); + *back = b = Winding_New(backpts); for (i = 0;i < in->numpoints;i++) { - if (f->numpoints >= maxpts || b->numpoints >= maxpts) - Sys_Error("Winding_Divide: points exceeded estimate"); - p1 = in->points[i]; if (sides[i] == SIDE_ON) @@ -306,4 +253,215 @@ void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, dou } } +// LordHavoc: these functions are more efficient by not allocating/freeing memory all the time + +void BufWinding_NewFromPlane(winding_t *w, double normalx, double normaly, double normalz, double dist) +{ + int x; + double max, v, org[3], vright[3], vup[3], normal[3]; + + w->numpoints = 0; + if (w->maxpoints < 4) + return; + + w->numpoints = 4; + + normal[0] = normalx; + normal[1] = normaly; + normal[2] = normalz; +#if 0 + VectorVectorsDouble(normal, vright, vup); +#else + // find the major axis + x = 0; + max = fabs(normal[0]); + v = fabs(normal[1]); + if(v > max) + { + x = 1; + max = v; + } + v = fabs(normal[2]); + if(v > max) + { + x = 2; + max = v; + } + + VectorClear(vup); + switch(x) + { + case 0: + case 1: + vup[2] = 1; + break; + case 2: + vup[0] = 1; + break; + } + + v = DotProduct(vup, normal); + VectorMA(vup, -v, normal, vup); + VectorNormalize(vup); +#endif + + VectorScale(normal, dist, org); + + CrossProduct(vup, normal, vright); + + VectorScale(vup, 1024.0*1024.0*1024.0, vup); + VectorScale(vright, 1024.0*1024.0*1024.0, vright); + + // project a really big axis aligned box onto the plane + VectorSubtract(org, vright, w->points[0]); + VectorAdd(w->points[0], vup, w->points[0]); + + VectorAdd(org, vright, w->points[1]); + VectorAdd(w->points[1], vup, w->points[1]); + + VectorAdd(org, vright, w->points[2]); + VectorSubtract(w->points[2], vup, w->points[2]); + + VectorSubtract(org, vright, w->points[3]); + VectorSubtract(w->points[3], vup, w->points[3]); + +#if 0 + { + double n[3]; + TriangleNormal(w->points[0], w->points[1], w->points[2], n); + VectorNormalize(n); + if (fabs(DotProduct(n, normal) - 1) > 0.01f) + Con_Printf("%.0f %.0f %.0f (%.0f %.0f %.0f, %.0f %.0f %.0f) != %.0f %.0f %.0f (%.0f %.0f %.0f, %.0f %.0f %.0f, %.0f %.0f %.0f, %.0f %.0f %.0f)\n", normal[0], normal[1], normal[2], vright[0], vright[1], vright[2], vup[0], vup[1], vup[2], n[0], n[1], n[2], w->points[0][0], w->points[0][1], w->points[0][2], w->points[1][0], w->points[1][1], w->points[1][2], w->points[2][0], w->points[2][1], w->points[2][2], w->points[3][0], w->points[3][1], w->points[3][2]); + } +#endif +} + +void BufWinding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t *outfront, int *neededfrontpoints, winding_t *outback, int *neededbackpoints) +{ + double dot, *p1, *p2, mid[3], splitnormal[3], dists[MAX_POINTS_ON_WINDING + 1]; + int i, j, frontpts, backpts, counts[3], sides[MAX_POINTS_ON_WINDING + 1]; + + if (outfront) + outfront->numpoints = 0; + if (outback) + outback->numpoints = 0; + + if (in->numpoints > MAX_POINTS_ON_WINDING || (!outfront && !outback)) + { + if (neededfrontpoints) + *neededfrontpoints = 0; + if (neededbackpoints) + *neededbackpoints = 0; + return; + } + + splitnormal[0] = splitnormalx; + splitnormal[1] = splitnormaly; + splitnormal[2] = splitnormalz; + + counts[SIDE_FRONT] = counts[SIDE_BACK] = counts[SIDE_ON] = 0; + + // determine sides for each point + for (i = 0;i < in->numpoints;i++) + { + dot = DotProduct(in->points[i], splitnormal); + dot -= splitdist; + dists[i] = dot; + if (dot > ON_EPSILON) sides[i] = SIDE_FRONT; + else if (dot < -ON_EPSILON) sides[i] = SIDE_BACK; + else sides[i] = SIDE_ON; + counts[sides[i]]++; + } + sides[i] = sides[0]; + dists[i] = dists[0]; + + frontpts = 0; + backpts = 0; + for (i = 0;i < in->numpoints;i++) + { + if (sides[i] != SIDE_ON) + { + if (sides[i] == SIDE_FRONT) + frontpts++; + else if (sides[i] == SIDE_BACK) + backpts++; + if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) + continue; + } + frontpts++; + backpts++; + } + + if (neededfrontpoints) + *neededfrontpoints = frontpts; + if (neededbackpoints) + *neededbackpoints = backpts; + if ((outfront && outfront->maxpoints < frontpts) || (outback && outback->maxpoints < backpts)) + return; + + for (i = 0;i < in->numpoints;i++) + { + p1 = in->points[i]; + + if (sides[i] == SIDE_ON) + { + if (outfront) + { + VectorCopy(p1, outfront->points[outfront->numpoints]); + outfront->numpoints++; + } + if (outback) + { + VectorCopy(p1, outback->points[outback->numpoints]); + outback->numpoints++; + } + continue; + } + + if (sides[i] == SIDE_FRONT) + { + if (outfront) + { + VectorCopy(p1, outfront->points[outfront->numpoints]); + outfront->numpoints++; + } + } + else if (sides[i] == SIDE_BACK) + { + if (outback) + { + VectorCopy(p1, outback->points[outback->numpoints]); + outback->numpoints++; + } + } + + if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i]) + continue; + + // generate a split point + p2 = in->points[(i+1)%in->numpoints]; + + dot = dists[i] / (dists[i]-dists[i+1]); + for (j = 0;j < 3;j++) + { // avoid round off error when possible + if (splitnormal[j] == 1) + mid[j] = splitdist; + else if (splitnormal[j] == -1) + mid[j] = -splitdist; + else + mid[j] = p1[j] + dot* (p2[j]-p1[j]); + } + + if (outfront) + { + VectorCopy(mid, outfront->points[outfront->numpoints]); + outfront->numpoints++; + } + if (outback) + { + VectorCopy(mid, outback->points[outback->numpoints]); + outback->numpoints++; + } + } +} diff --git a/winding.h b/winding.h index c026d40f..42a54ddb 100644 --- a/winding.h +++ b/winding.h @@ -5,7 +5,7 @@ typedef struct { int numpoints; - int padding; + int maxpoints; double points[8][3]; // variable sized } winding_t; @@ -15,6 +15,8 @@ void Winding_Free(winding_t *w); winding_t *Winding_NewFromPlane(double normalx, double normaly, double normalz, double dist); winding_t *Winding_Clip(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, int keepon); void Winding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t **front, winding_t **back); +void BufWinding_NewFromPlane(winding_t *w, double normalx, double normaly, double normalz, double dist); +void BufWinding_Divide(winding_t *in, double splitnormalx, double splitnormaly, double splitnormalz, double splitdist, winding_t *outfront, int *neededfrontpoints, winding_t *outback, int *neededbackpoints); #endif -- 2.39.2