#include "bsp5.h" // SubdivideFace // InitHash // HashVec // GetVertex // GetEdge // MakeFaceEdges static int subdivides; /* a surface has all of the faces that could be drawn on a given plane the outside filling stage can remove some of them so a better bsp can be generated */ // ===================================================================================== // SubdivideFace // If the face is >256 in either texture direction, carve a valid sized // piece off and insert the remainder in the next link // ===================================================================================== void SubdivideFace(face_t* f, face_t** prevptr) { vec_t mins, maxs; vec_t v; int axis; int i; dplane_t plane; face_t* front; face_t* back; face_t* next; texinfo_t* tex; vec3_t temp; // special (non-surface cached) faces don't need subdivision tex = &g_texinfo[f->texturenum]; if (tex->flags & TEX_SPECIAL) { return; } if (f->facestyle == face_hint) { return; } if (f->facestyle == face_skip) { return; } #ifdef ZHLT_NULLTEX // AJM if (f->facestyle == face_null) return; // ideally these should have their tex_special flag set, so its here jic #endif //SILENCER: Not yet implemented - just altered copypasta here /*if (f->facestyle == face_blocklight) return;*/ for (axis = 0; axis < 2; axis++) { while (1) { mins = 999999; maxs = -999999; for (i = 0; i < f->numpoints; i++) { v = DotProduct(f->pts[i], tex->vecs[axis]); if (v < mins) { mins = v; } if (v > maxs) { maxs = v; } } if ((maxs - mins) <= g_subdivide_size) { break; } // split it subdivides++; VectorCopy(tex->vecs[axis], temp); v = VectorNormalize(temp); VectorCopy(temp, plane.normal); plane.dist = (mins + g_subdivide_size - 16) / v; next = f->next; SplitFace(f, &plane, &front, &back); if (!front || !back) { Developer(DEVELOPER_LEVEL_SPAM, "SubdivideFace: didn't split the %d-sided polygon @(%.0f,%.0f,%.0f)", f->numpoints, f->pts[0][0], f->pts[0][1], f->pts[0][2]); break; } *prevptr = back; back->next = front; front->next = next; f = back; } } } //=========================================================================== typedef struct hashvert_s { struct hashvert_s* next; vec3_t point; int num; int numplanes; // for corner determination int planenums[2]; int numedges; } hashvert_t; // #define POINT_EPSILON 0.01 #define POINT_EPSILON ON_EPSILON static hashvert_t hvertex[MAX_MAP_VERTS]; static hashvert_t* hvert_p; static face_t* edgefaces[MAX_MAP_EDGES][2]; static int firstmodeledge = 1; static int firstmodelface; //============================================================================ #define NUM_HASH 4096 static hashvert_t* hashverts[NUM_HASH]; static vec3_t hash_min; static vec3_t hash_scale; // ===================================================================================== // InitHash // ===================================================================================== static void InitHash() { vec3_t size; vec_t volume; vec_t scale; int newsize[2]; int i; memset(hashverts, 0, sizeof(hashverts)); for (i = 0; i < 3; i++) { hash_min[i] = -8000; size[i] = 16000; } volume = size[0] * size[1]; scale = sqrt(volume / NUM_HASH); newsize[0] = size[0] / scale; newsize[1] = size[1] / scale; hash_scale[0] = newsize[0] / size[0]; hash_scale[1] = newsize[1] / size[1]; hash_scale[2] = newsize[1]; hvert_p = hvertex; } // ===================================================================================== // HashVec // ===================================================================================== static unsigned HashVec(const vec3_t vec) { unsigned h; h = hash_scale[0] * (vec[0] - hash_min[0]) * hash_scale[2] + hash_scale[1] * (vec[1] - hash_min[1]); if (h >= NUM_HASH) { return NUM_HASH - 1; } return h; } // ===================================================================================== // GetVertex // ===================================================================================== static int GetVertex(const vec3_t in, const int planenum) { int h; int i; hashvert_t* hv; vec3_t vert; for (i = 0; i < 3; i++) { if (fabs(in[i] - VectorRound(in[i])) < 0.001) { vert[i] = VectorRound(in[i]); } else { vert[i] = in[i]; } } h = HashVec(vert); for (hv = hashverts[h]; hv; hv = hv->next) { if (fabs(hv->point[0] - vert[0]) < POINT_EPSILON && fabs(hv->point[1] - vert[1]) < POINT_EPSILON && fabs(hv->point[2] - vert[2]) < POINT_EPSILON) { hv->numedges++; if (hv->numplanes == 3) { return hv->num; // allready known to be a corner } for (i = 0; i < hv->numplanes; i++) { if (hv->planenums[i] == planenum) { return hv->num; // allready know this plane } } if (hv->numplanes != 2) { hv->planenums[hv->numplanes] = planenum; } hv->numplanes++; return hv->num; } } hv = hvert_p; hv->numedges = 1; hv->numplanes = 1; hv->planenums[0] = planenum; hv->next = hashverts[h]; hashverts[h] = hv; VectorCopy(vert, hv->point); hv->num = g_numvertexes; hlassume(hv->num != MAX_MAP_VERTS, assume_MAX_MAP_VERTS); hvert_p++; // emit a vertex hlassume(g_numvertexes < MAX_MAP_VERTS, assume_MAX_MAP_VERTS); g_dvertexes[g_numvertexes].point[0] = vert[0]; g_dvertexes[g_numvertexes].point[1] = vert[1]; g_dvertexes[g_numvertexes].point[2] = vert[2]; g_numvertexes++; return hv->num; } //=========================================================================== // ===================================================================================== // GetEdge // Don't allow four way edges // ===================================================================================== int GetEdge(const vec3_t p1, const vec3_t p2, face_t* f) { int v1; int v2; dedge_t* edge; int i; hlassert(f->contents); v1 = GetVertex(p1, f->planenum); v2 = GetVertex(p2, f->planenum); for (i = firstmodeledge; i < g_numedges; i++) { edge = &g_dedges[i]; if (v1 == edge->v[1] && v2 == edge->v[0] && !edgefaces[i][1] && edgefaces[i][0]->contents == f->contents) { edgefaces[i][1] = f; return -i; } } // emit an edge hlassume(g_numedges < MAX_MAP_EDGES, assume_MAX_MAP_EDGES); edge = &g_dedges[g_numedges]; g_numedges++; edge->v[0] = v1; edge->v[1] = v2; edgefaces[i][0] = f; return i; } // ===================================================================================== // MakeFaceEdges // ===================================================================================== void MakeFaceEdges() { InitHash(); firstmodeledge = g_numedges; firstmodelface = g_numfaces; }