-/*\r
-Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
-For a list of contributors, see the accompanying CONTRIBUTORS file.\r
-\r
-This file is part of GtkRadiant.\r
-\r
-GtkRadiant is free software; you can redistribute it and/or modify\r
-it under the terms of the GNU General Public License as published by\r
-the Free Software Foundation; either version 2 of the License, or\r
-(at your option) any later version.\r
-\r
-GtkRadiant is distributed in the hope that it will be useful,\r
-but WITHOUT ANY WARRANTY; without even the implied warranty of\r
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\r
-GNU General Public License for more details.\r
-\r
-You should have received a copy of the GNU General Public License\r
-along with GtkRadiant; if not, write to the Free Software\r
-Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA\r
-*/\r
-// faces.c\r
-\r
-#include "qbsp.h"\r
-\r
-/*\r
-\r
- some faces will be removed before saving, but still form nodes:\r
-\r
- the insides of sky volumes\r
- meeting planes of different water current volumes\r
-\r
-*/\r
-\r
-// undefine for dumb linear searches\r
-#define USE_HASHING\r
-\r
-#define INTEGRAL_EPSILON 0.01\r
-#define POINT_EPSILON 0.5\r
-#define OFF_EPSILON 0.5\r
-\r
-int c_merge;\r
-int c_subdivide;\r
-\r
-int c_totalverts;\r
-int c_uniqueverts;\r
-int c_degenerate;\r
-int c_tjunctions;\r
-int c_faceoverflows;\r
-int c_facecollapse;\r
-int c_badstartverts;\r
-\r
-#define MAX_SUPERVERTS 512\r
-int superverts[MAX_SUPERVERTS];\r
-int numsuperverts;\r
-\r
-face_t *edgefaces[MAX_MAP_EDGES][2];\r
-int firstmodeledge = 1;\r
-int firstmodelface;\r
-\r
-int c_tryedges;\r
-\r
-vec3_t edge_dir;\r
-vec3_t edge_start;\r
-vec_t edge_len;\r
-\r
-int num_edge_verts;\r
-int edge_verts[MAX_MAP_VERTS];\r
-\r
-\r
-float subdivide_size = 240;\r
-\r
-\r
-face_t *NewFaceFromFace (face_t *f);\r
-\r
-//===========================================================================\r
-\r
-typedef struct hashvert_s\r
-{\r
- struct hashvert_s *next;\r
- int num;\r
-} hashvert_t;\r
-\r
-\r
-#define HASH_SIZE 64\r
-\r
-\r
-int vertexchain[MAX_MAP_VERTS]; // the next vertex in a hash chain\r
-int hashverts[HASH_SIZE*HASH_SIZE]; // a vertex number, or 0 for no verts\r
-\r
-face_t *edgefaces[MAX_MAP_EDGES][2];\r
-\r
-//============================================================================\r
-\r
-\r
-unsigned HashVec (vec3_t vec)\r
-{\r
- int x, y;\r
-\r
- x = (4096 + (int)(vec[0]+0.5)) >> 7;\r
- y = (4096 + (int)(vec[1]+0.5)) >> 7;\r
-\r
- if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE )\r
- Error ("HashVec: point outside valid range");\r
- \r
- return y*HASH_SIZE + x;\r
-}\r
-\r
-#ifdef USE_HASHING\r
-/*\r
-=============\r
-GetVertex\r
-\r
-Uses hashing\r
-=============\r
-*/\r
-int GetVertexnum (vec3_t in)\r
-{\r
- int h;\r
- int i;\r
- float *p;\r
- vec3_t vert;\r
- int vnum;\r
-\r
- c_totalverts++;\r
-\r
- for (i=0 ; i<3 ; i++)\r
- {\r
- if ( fabs(in[i] - Q_rint(in[i])) < INTEGRAL_EPSILON)\r
- vert[i] = Q_rint(in[i]);\r
- else\r
- vert[i] = in[i];\r
- }\r
- \r
- h = HashVec (vert);\r
- \r
- for (vnum=hashverts[h] ; vnum ; vnum=vertexchain[vnum])\r
- {\r
- p = dvertexes[vnum].point;\r
- if ( fabs(p[0]-vert[0])<POINT_EPSILON\r
- && fabs(p[1]-vert[1])<POINT_EPSILON\r
- && fabs(p[2]-vert[2])<POINT_EPSILON )\r
- return vnum;\r
- }\r
- \r
-// emit a vertex\r
- if (numvertexes == MAX_MAP_VERTS)\r
- Error ("numvertexes == MAX_MAP_VERTS");\r
-\r
- dvertexes[numvertexes].point[0] = vert[0];\r
- dvertexes[numvertexes].point[1] = vert[1];\r
- dvertexes[numvertexes].point[2] = vert[2];\r
-\r
- vertexchain[numvertexes] = hashverts[h];\r
- hashverts[h] = numvertexes;\r
-\r
- c_uniqueverts++;\r
-\r
- numvertexes++;\r
- \r
- return numvertexes-1;\r
-}\r
-#else\r
-/*\r
-==================\r
-GetVertexnum\r
-\r
-Dumb linear search\r
-==================\r
-*/\r
-int GetVertexnum (vec3_t v)\r
-{\r
- int i, j;\r
- dvertex_t *dv;\r
- vec_t d;\r
-\r
- c_totalverts++;\r
-\r
- // make really close values exactly integral\r
- for (i=0 ; i<3 ; i++)\r
- {\r
- if ( fabs(v[i] - (int)(v[i]+0.5)) < INTEGRAL_EPSILON )\r
- v[i] = (int)(v[i]+0.5);\r
- if (v[i] < -4096 || v[i] > 4096)\r
- Error ("GetVertexnum: outside +/- 4096");\r
- }\r
-\r
- // search for an existing vertex match\r
- for (i=0, dv=dvertexes ; i<numvertexes ; i++, dv++)\r
- {\r
- for (j=0 ; j<3 ; j++)\r
- {\r
- d = v[j] - dv->point[j];\r
- if ( d > POINT_EPSILON || d < -POINT_EPSILON)\r
- break;\r
- }\r
- if (j == 3)\r
- return i; // a match\r
- }\r
-\r
- // new point\r
- if (numvertexes == MAX_MAP_VERTS)\r
- Error ("MAX_MAP_VERTS");\r
- VectorCopy (v, dv->point);\r
- numvertexes++;\r
- c_uniqueverts++;\r
-\r
- return numvertexes-1;\r
-}\r
-#endif\r
-\r
-\r
-/*\r
-==================\r
-FaceFromSuperverts\r
-\r
-The faces vertexes have beeb added to the superverts[] array,\r
-and there may be more there than can be held in a face (MAXEDGES).\r
-\r
-If less, the faces vertexnums[] will be filled in, otherwise\r
-face will reference a tree of split[] faces until all of the\r
-vertexnums can be added.\r
-\r
-superverts[base] will become face->vertexnums[0], and the others\r
-will be circularly filled in.\r
-==================\r
-*/\r
-void FaceFromSuperverts (node_t *node, face_t *f, int base)\r
-{\r
- face_t *newf;\r
- int remaining;\r
- int i;\r
-\r
- remaining = numsuperverts;\r
- while (remaining > MAXEDGES)\r
- { // must split into two faces, because of vertex overload\r
- c_faceoverflows++;\r
-\r
- newf = f->split[0] = NewFaceFromFace (f);\r
- newf = f->split[0];\r
- newf->next = node->faces;\r
- node->faces = newf;\r
-\r
- newf->numpoints = MAXEDGES;\r
- for (i=0 ; i<MAXEDGES ; i++)\r
- newf->vertexnums[i] = superverts[(i+base)%numsuperverts];\r
-\r
- f->split[1] = NewFaceFromFace (f);\r
- f = f->split[1];\r
- f->next = node->faces;\r
- node->faces = f;\r
-\r
- remaining -= (MAXEDGES-2);\r
- base = (base+MAXEDGES-1)%numsuperverts;\r
- }\r
-\r
- // copy the vertexes back to the face\r
- f->numpoints = remaining;\r
- for (i=0 ; i<remaining ; i++)\r
- f->vertexnums[i] = superverts[(i+base)%numsuperverts];\r
-}\r
-\r
-\r
-/*\r
-==================\r
-EmitFaceVertexes\r
-==================\r
-*/\r
-void EmitFaceVertexes (node_t *node, face_t *f)\r
-{\r
- winding_t *w;\r
- int i;\r
-\r
- if (f->merged || f->split[0] || f->split[1])\r
- return;\r
-\r
- w = f->w;\r
- for (i=0 ; i<w->numpoints ; i++)\r
- {\r
- if (noweld)\r
- { // make every point unique\r
- if (numvertexes == MAX_MAP_VERTS)\r
- Error ("MAX_MAP_VERTS");\r
- superverts[i] = numvertexes;\r
- VectorCopy (w->p[i], dvertexes[numvertexes].point);\r
- numvertexes++;\r
- c_uniqueverts++;\r
- c_totalverts++;\r
- }\r
- else\r
- superverts[i] = GetVertexnum (w->p[i]);\r
- }\r
- numsuperverts = w->numpoints;\r
-\r
- // this may fragment the face if > MAXEDGES\r
- FaceFromSuperverts (node, f, 0);\r
-}\r
-\r
-/*\r
-==================\r
-EmitVertexes_r\r
-==================\r
-*/\r
-void EmitVertexes_r (node_t *node)\r
-{\r
- int i;\r
- face_t *f;\r
-\r
- if (node->planenum == PLANENUM_LEAF)\r
- return;\r
-\r
- for (f=node->faces ; f ; f=f->next)\r
- {\r
- EmitFaceVertexes (node, f);\r
- }\r
-\r
- for (i=0 ; i<2 ; i++)\r
- EmitVertexes_r (node->children[i]);\r
-}\r
-\r
-\r
-#ifdef USE_HASHING\r
-/*\r
-==========\r
-FindEdgeVerts\r
-\r
-Uses the hash tables to cut down to a small number\r
-==========\r
-*/\r
-void FindEdgeVerts (vec3_t v1, vec3_t v2)\r
-{\r
- int x1, x2, y1, y2, t;\r
- int x, y;\r
- int vnum;\r
-\r
-#if 0\r
-{\r
- int i;\r
- num_edge_verts = numvertexes-1;\r
- for (i=0 ; i<numvertexes-1 ; i++)\r
- edge_verts[i] = i+1;\r
-}\r
-#endif\r
-\r
- x1 = (4096 + (int)(v1[0]+0.5)) >> 7;\r
- y1 = (4096 + (int)(v1[1]+0.5)) >> 7;\r
- x2 = (4096 + (int)(v2[0]+0.5)) >> 7;\r
- y2 = (4096 + (int)(v2[1]+0.5)) >> 7;\r
-\r
- if (x1 > x2)\r
- {\r
- t = x1;\r
- x1 = x2;\r
- x2 = t;\r
- }\r
- if (y1 > y2)\r
- {\r
- t = y1;\r
- y1 = y2;\r
- y2 = t;\r
- }\r
-#if 0\r
- x1--;\r
- x2++;\r
- y1--;\r
- y2++;\r
- if (x1 < 0)\r
- x1 = 0;\r
- if (x2 >= HASH_SIZE)\r
- x2 = HASH_SIZE;\r
- if (y1 < 0)\r
- y1 = 0;\r
- if (y2 >= HASH_SIZE)\r
- y2 = HASH_SIZE;\r
-#endif\r
- num_edge_verts = 0;\r
- for (x=x1 ; x <= x2 ; x++)\r
- {\r
- for (y=y1 ; y <= y2 ; y++)\r
- {\r
- for (vnum=hashverts[y*HASH_SIZE+x] ; vnum ; vnum=vertexchain[vnum])\r
- {\r
- edge_verts[num_edge_verts++] = vnum;\r
- }\r
- }\r
- }\r
-}\r
-\r
-#else\r
-/*\r
-==========\r
-FindEdgeVerts\r
-\r
-Forced a dumb check of everything\r
-==========\r
-*/\r
-void FindEdgeVerts (vec3_t v1, vec3_t v2)\r
-{\r
- int i;\r
-\r
- num_edge_verts = numvertexes-1;\r
- for (i=0 ; i<num_edge_verts ; i++)\r
- edge_verts[i] = i+1;\r
-}\r
-#endif\r
-\r
-/*\r
-==========\r
-TestEdge\r
-\r
-Can be recursively reentered\r
-==========\r
-*/\r
-void TestEdge (vec_t start, vec_t end, int p1, int p2, int startvert)\r
-{\r
- int j, k;\r
- vec_t dist;\r
- vec3_t delta;\r
- vec3_t exact;\r
- vec3_t off;\r
- vec_t error;\r
- vec3_t p;\r
-\r
- if (p1 == p2)\r
- {\r
- c_degenerate++;\r
- return; // degenerate edge\r
- }\r
-\r
- for (k=startvert ; k<num_edge_verts ; k++)\r
- {\r
- j = edge_verts[k];\r
- if (j==p1 || j == p2)\r
- continue;\r
-\r
- VectorCopy (dvertexes[j].point, p);\r
-\r
- VectorSubtract (p, edge_start, delta);\r
- dist = DotProduct (delta, edge_dir);\r
- if (dist <=start || dist >= end)\r
- continue; // off an end\r
- VectorMA (edge_start, dist, edge_dir, exact);\r
- VectorSubtract (p, exact, off);\r
- error = VectorLength (off);\r
-\r
- if (fabs(error) > OFF_EPSILON)\r
- continue; // not on the edge\r
-\r
- // break the edge\r
- c_tjunctions++;\r
- TestEdge (start, dist, p1, j, k+1);\r
- TestEdge (dist, end, j, p2, k+1);\r
- return;\r
- }\r
-\r
- // the edge p1 to p2 is now free of tjunctions\r
- if (numsuperverts >= MAX_SUPERVERTS)\r
- Error ("MAX_SUPERVERTS");\r
- superverts[numsuperverts] = p1;\r
- numsuperverts++;\r
-}\r
-\r
-/*\r
-==================\r
-FixFaceEdges\r
-\r
-==================\r
-*/\r
-void FixFaceEdges (node_t *node, face_t *f)\r
-{\r
- int p1, p2;\r
- int i;\r
- vec3_t e2;\r
- vec_t len;\r
- int count[MAX_SUPERVERTS], start[MAX_SUPERVERTS];\r
- int base;\r
-\r
- if (f->merged || f->split[0] || f->split[1])\r
- return;\r
-\r
- numsuperverts = 0;\r
-\r
- for (i=0 ; i<f->numpoints ; i++)\r
- {\r
- p1 = f->vertexnums[i];\r
- p2 = f->vertexnums[(i+1)%f->numpoints];\r
-\r
- VectorCopy (dvertexes[p1].point, edge_start);\r
- VectorCopy (dvertexes[p2].point, e2);\r
-\r
- FindEdgeVerts (edge_start, e2);\r
-\r
- VectorSubtract (e2, edge_start, edge_dir);\r
- len = VectorNormalize (edge_dir, edge_dir);\r
-\r
- start[i] = numsuperverts;\r
- TestEdge (0, len, p1, p2, 0);\r
-\r
- count[i] = numsuperverts - start[i];\r
- }\r
-\r
- if (numsuperverts < 3)\r
- { // entire face collapsed\r
- f->numpoints = 0;\r
- c_facecollapse++;\r
- return;\r
- }\r
-\r
- // we want to pick a vertex that doesn't have tjunctions\r
- // on either side, which can cause artifacts on trifans,\r
- // especially underwater\r
- for (i=0 ; i<f->numpoints ; i++)\r
- {\r
- if (count[i] == 1 && count[(i+f->numpoints-1)%f->numpoints] == 1)\r
- break;\r
- }\r
- if (i == f->numpoints)\r
- {\r
- f->badstartvert = true;\r
- c_badstartverts++;\r
- base = 0;\r
- }\r
- else\r
- { // rotate the vertex order\r
- base = start[i];\r
- }\r
-\r
- // this may fragment the face if > MAXEDGES\r
- FaceFromSuperverts (node, f, base);\r
-}\r
-\r
-/*\r
-==================\r
-FixEdges_r\r
-==================\r
-*/\r
-void FixEdges_r (node_t *node)\r
-{\r
- int i;\r
- face_t *f;\r
-\r
- if (node->planenum == PLANENUM_LEAF)\r
- return;\r
-\r
- for (f=node->faces ; f ; f=f->next)\r
- FixFaceEdges (node, f);\r
-\r
- for (i=0 ; i<2 ; i++)\r
- FixEdges_r (node->children[i]);\r
-}\r
-\r
-/*\r
-===========\r
-FixTjuncs\r
-\r
-===========\r
-*/\r
-void FixTjuncs (node_t *headnode)\r
-{\r
- // snap and merge all vertexes\r
- Sys_FPrintf( SYS_VRB, "---- snap verts ----\n");\r
- memset (hashverts, 0, sizeof(hashverts));\r
- c_totalverts = 0;\r
- c_uniqueverts = 0;\r
- c_faceoverflows = 0;\r
- EmitVertexes_r (headnode);\r
- Sys_FPrintf( SYS_VRB, "%i unique from %i\n", c_uniqueverts, c_totalverts);\r
-\r
- // break edges on tjunctions\r
- Sys_FPrintf( SYS_VRB, "---- tjunc ----\n");\r
- c_tryedges = 0;\r
- c_degenerate = 0;\r
- c_facecollapse = 0;\r
- c_tjunctions = 0;\r
- if (!notjunc)\r
- FixEdges_r (headnode);\r
- Sys_FPrintf( SYS_VRB, "%5i edges degenerated\n", c_degenerate);\r
- Sys_FPrintf( SYS_VRB, "%5i faces degenerated\n", c_facecollapse);\r
- Sys_FPrintf( SYS_VRB, "%5i edges added by tjunctions\n", c_tjunctions);\r
- Sys_FPrintf( SYS_VRB, "%5i faces added by tjunctions\n", c_faceoverflows);\r
- Sys_FPrintf( SYS_VRB, "%5i bad start verts\n", c_badstartverts);\r
-}\r
-\r
-\r
-//========================================================\r
-\r
-int c_faces;\r
-\r
-face_t *AllocFace (void)\r
-{\r
- face_t *f;\r
-\r
- f = malloc(sizeof(*f));\r
- memset (f, 0, sizeof(*f));\r
- c_faces++;\r
-\r
- return f;\r
-}\r
-\r
-face_t *NewFaceFromFace (face_t *f)\r
-{\r
- face_t *newf;\r
-\r
- newf = AllocFace ();\r
- *newf = *f;\r
- newf->merged = NULL;\r
- newf->split[0] = newf->split[1] = NULL;\r
- newf->w = NULL;\r
- return newf;\r
-}\r
-\r
-void FreeFace (face_t *f)\r
-{\r
- if (f->w)\r
- FreeWinding (f->w);\r
- free (f);\r
- c_faces--;\r
-}\r
-\r
-//========================================================\r
-\r
-/*\r
-==================\r
-GetEdge\r
-\r
-Called by writebsp.\r
-Don't allow four way edges\r
-==================\r
-*/\r
-int GetEdge2 (int v1, int v2, face_t *f)\r
-{\r
- dedge_t *edge;\r
- int i;\r
-\r
- c_tryedges++;\r
-\r
- if (!noshare)\r
- {\r
- for (i=firstmodeledge ; i < numedges ; i++)\r
- {\r
- edge = &dedges[i];\r
- if (v1 == edge->v[1] && v2 == edge->v[0]\r
- && edgefaces[i][0]->contents == f->contents)\r
- {\r
- if (edgefaces[i][1])\r
- // Sys_Printf ("WARNING: multiple backward edge\n");\r
- continue;\r
- edgefaces[i][1] = f;\r
- return -i;\r
- }\r
- #if 0\r
- if (v1 == edge->v[0] && v2 == edge->v[1])\r
- {\r
- Sys_Printf ("WARNING: multiple forward edge\n");\r
- return i;\r
- }\r
- #endif\r
- }\r
- }\r
-\r
-// emit an edge\r
- if (numedges >= MAX_MAP_EDGES)\r
- Error ("numedges == MAX_MAP_EDGES");\r
- edge = &dedges[numedges];\r
- numedges++;\r
- edge->v[0] = v1;\r
- edge->v[1] = v2;\r
- edgefaces[numedges-1][0] = f;\r
- \r
- return numedges-1;\r
-}\r
-\r
-/*\r
-===========================================================================\r
-\r
-FACE MERGING\r
-\r
-===========================================================================\r
-*/\r
-\r
-#define CONTINUOUS_EPSILON 0.001\r
-\r
-/*\r
-=============\r
-TryMergeWinding\r
-\r
-If two polygons share a common edge and the edges that meet at the\r
-common points are both inside the other polygons, merge them\r
-\r
-Returns NULL if the faces couldn't be merged, or the new face.\r
-The originals will NOT be freed.\r
-=============\r
-*/\r
-winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, vec3_t planenormal)\r
-{\r
- vec_t *p1, *p2, *p3, *p4, *back;\r
- winding_t *newf;\r
- int i, j, k, l;\r
- vec3_t normal, delta;\r
- vec_t dot;\r
- qboolean keep1, keep2;\r
- \r
-\r
- //\r
- // find a common edge\r
- // \r
- p1 = p2 = NULL; // stop compiler warning\r
- j = 0; // \r
- \r
- for (i=0 ; i<f1->numpoints ; i++)\r
- {\r
- p1 = f1->p[i];\r
- p2 = f1->p[(i+1)%f1->numpoints];\r
- for (j=0 ; j<f2->numpoints ; j++)\r
- {\r
- p3 = f2->p[j];\r
- p4 = f2->p[(j+1)%f2->numpoints];\r
- for (k=0 ; k<3 ; k++)\r
- {\r
- if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)\r
- break;\r
- if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)\r
- break;\r
- }\r
- if (k==3)\r
- break;\r
- }\r
- if (j < f2->numpoints)\r
- break;\r
- }\r
- \r
- if (i == f1->numpoints)\r
- return NULL; // no matching edges\r
-\r
- //\r
- // check slope of connected lines\r
- // if the slopes are colinear, the point can be removed\r
- //\r
- back = f1->p[(i+f1->numpoints-1)%f1->numpoints];\r
- VectorSubtract (p1, back, delta);\r
- CrossProduct (planenormal, delta, normal);\r
- VectorNormalize (normal, normal);\r
- \r
- back = f2->p[(j+2)%f2->numpoints];\r
- VectorSubtract (back, p1, delta);\r
- dot = DotProduct (delta, normal);\r
- if (dot > CONTINUOUS_EPSILON)\r
- return NULL; // not a convex polygon\r
- keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);\r
- \r
- back = f1->p[(i+2)%f1->numpoints];\r
- VectorSubtract (back, p2, delta);\r
- CrossProduct (planenormal, delta, normal);\r
- VectorNormalize (normal, normal);\r
-\r
- back = f2->p[(j+f2->numpoints-1)%f2->numpoints];\r
- VectorSubtract (back, p2, delta);\r
- dot = DotProduct (delta, normal);\r
- if (dot > CONTINUOUS_EPSILON)\r
- return NULL; // not a convex polygon\r
- keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);\r
-\r
- //\r
- // build the new polygon\r
- //\r
- newf = AllocWinding (f1->numpoints + f2->numpoints);\r
- \r
- // copy first polygon\r
- for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)\r
- {\r
- if (k==(i+1)%f1->numpoints && !keep2)\r
- continue;\r
- \r
- VectorCopy (f1->p[k], newf->p[newf->numpoints]);\r
- newf->numpoints++;\r
- }\r
- \r
- // copy second polygon\r
- for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)\r
- {\r
- if (l==(j+1)%f2->numpoints && !keep1)\r
- continue;\r
- VectorCopy (f2->p[l], newf->p[newf->numpoints]);\r
- newf->numpoints++;\r
- }\r
-\r
- return newf;\r
-}\r
-\r
-/*\r
-=============\r
-TryMerge\r
-\r
-If two polygons share a common edge and the edges that meet at the\r
-common points are both inside the other polygons, merge them\r
-\r
-Returns NULL if the faces couldn't be merged, or the new face.\r
-The originals will NOT be freed.\r
-=============\r
-*/\r
-face_t *TryMerge (face_t *f1, face_t *f2, vec3_t planenormal)\r
-{\r
- face_t *newf;\r
- winding_t *nw;\r
-\r
- if (!f1->w || !f2->w)\r
- return NULL;\r
- if (f1->texinfo != f2->texinfo)\r
- return NULL;\r
- if (f1->planenum != f2->planenum) // on front and back sides\r
- return NULL;\r
- if (f1->contents != f2->contents)\r
- return NULL;\r
- \r
-\r
- nw = TryMergeWinding (f1->w, f2->w, planenormal);\r
- if (!nw)\r
- return NULL;\r
-\r
- c_merge++;\r
- newf = NewFaceFromFace (f1);\r
- newf->w = nw;\r
-\r
- f1->merged = newf;\r
- f2->merged = newf;\r
-\r
- return newf;\r
-}\r
-\r
-/*\r
-===============\r
-MergeNodeFaces\r
-===============\r
-*/\r
-void MergeNodeFaces (node_t *node)\r
-{\r
- face_t *f1, *f2, *end;\r
- face_t *merged;\r
- plane_t *plane;\r
-\r
- plane = &mapplanes[node->planenum];\r
- merged = NULL;\r
- \r
- for (f1 = node->faces ; f1 ; f1 = f1->next)\r
- {\r
- if (f1->merged || f1->split[0] || f1->split[1])\r
- continue;\r
- for (f2 = node->faces ; f2 != f1 ; f2=f2->next)\r
- {\r
- if (f2->merged || f2->split[0] || f2->split[1])\r
- continue;\r
- merged = TryMerge (f1, f2, plane->normal);\r
- if (!merged)\r
- continue;\r
-\r
- // add merged to the end of the node face list \r
- // so it will be checked against all the faces again\r
- for (end = node->faces ; end->next ; end = end->next)\r
- ;\r
- merged->next = NULL;\r
- end->next = merged;\r
- break;\r
- }\r
- }\r
-}\r
-\r
-//=====================================================================\r
-\r
-/*\r
-===============\r
-SubdivideFace\r
-\r
-Chop up faces that are larger than we want in the surface cache\r
-===============\r
-*/\r
-void SubdivideFace (node_t *node, face_t *f)\r
-{\r
- float mins, maxs;\r
- vec_t v;\r
- int axis, i;\r
- texinfo_t *tex;\r
- vec3_t temp;\r
- vec_t dist;\r
- winding_t *w, *frontw, *backw;\r
-\r
- if (f->merged)\r
- return;\r
-\r
-// special (non-surface cached) faces don't need subdivision\r
- tex = &texinfo[f->texinfo];\r
-\r
- if ( tex->flags & (SURF_WARP|SURF_SKY) )\r
- {\r
- return;\r
- }\r
-\r
- for (axis = 0 ; axis < 2 ; axis++)\r
- {\r
- while (1)\r
- {\r
- mins = 999999;\r
- maxs = -999999;\r
- \r
- VectorCopy (tex->vecs[axis], temp);\r
- w = f->w;\r
- for (i=0 ; i<w->numpoints ; i++)\r
- {\r
- v = DotProduct (w->p[i], temp);\r
- if (v < mins)\r
- mins = v;\r
- if (v > maxs)\r
- maxs = v;\r
- }\r
-#if 0\r
- if (maxs - mins <= 0)\r
- Error ("zero extents");\r
-#endif\r
- if (axis == 2)\r
- { // allow double high walls\r
- if (maxs - mins <= subdivide_size/* *2 */)\r
- break;\r
- }\r
- else if (maxs - mins <= subdivide_size)\r
- break;\r
- \r
- // split it\r
- c_subdivide++;\r
- \r
- v = VectorNormalize (temp, temp); \r
-\r
- dist = (mins + subdivide_size - 16)/v;\r
-\r
- ClipWindingEpsilon (w, temp, dist, ON_EPSILON, &frontw, &backw);\r
- if (!frontw || !backw)\r
- Error ("SubdivideFace: didn't split the polygon");\r
-\r
- f->split[0] = NewFaceFromFace (f);\r
- f->split[0]->w = frontw;\r
- f->split[0]->next = node->faces;\r
- node->faces = f->split[0];\r
-\r
- f->split[1] = NewFaceFromFace (f);\r
- f->split[1]->w = backw;\r
- f->split[1]->next = node->faces;\r
- node->faces = f->split[1];\r
-\r
- SubdivideFace (node, f->split[0]);\r
- SubdivideFace (node, f->split[1]);\r
- return;\r
- }\r
- }\r
-}\r
-\r
-void SubdivideNodeFaces (node_t *node)\r
-{\r
- face_t *f;\r
-\r
- for (f = node->faces ; f ; f=f->next)\r
- {\r
- SubdivideFace (node, f);\r
- }\r
-}\r
-\r
-//===========================================================================\r
-\r
-int c_nodefaces;\r
-\r
-\r
-/*\r
-============\r
-FaceFromPortal\r
-\r
-============\r
-*/\r
-face_t *FaceFromPortal (portal_t *p, int pside)\r
-{\r
- face_t *f;\r
- side_t *side;\r
-\r
- side = p->side;\r
- if (!side)\r
- return NULL; // portal does not bridge different visible contents\r
-\r
- f = AllocFace ();\r
-\r
- f->texinfo = side->texinfo;\r
- f->planenum = (side->planenum & ~1) | pside;\r
- f->portal = p;\r
-\r
- if ( (p->nodes[pside]->contents & CONTENTS_WINDOW)\r
- && VisibleContents(p->nodes[!pside]->contents^p->nodes[pside]->contents) == CONTENTS_WINDOW )\r
- return NULL; // don't show insides of windows\r
-\r
- if (pside)\r
- {\r
- f->w = ReverseWinding(p->winding);\r
- f->contents = p->nodes[1]->contents;\r
- }\r
- else\r
- {\r
- f->w = CopyWinding(p->winding);\r
- f->contents = p->nodes[0]->contents;\r
- }\r
- return f;\r
-}\r
-\r
-\r
-/*\r
-===============\r
-MakeFaces_r\r
-\r
-If a portal will make a visible face,\r
-mark the side that originally created it\r
-\r
- solid / empty : solid\r
- solid / water : solid\r
- water / empty : water\r
- water / water : none\r
-===============\r
-*/\r
-void MakeFaces_r (node_t *node)\r
-{\r
- portal_t *p;\r
- int s;\r
-\r
- // recurse down to leafs\r
- if (node->planenum != PLANENUM_LEAF)\r
- {\r
- MakeFaces_r (node->children[0]);\r
- MakeFaces_r (node->children[1]);\r
-\r
- // merge together all visible faces on the node\r
- if (!nomerge)\r
- MergeNodeFaces (node);\r
- if (!nosubdiv)\r
- SubdivideNodeFaces (node);\r
-\r
- return;\r
- }\r
-\r
- // solid leafs never have visible faces\r
- if (node->contents & CONTENTS_SOLID)\r
- return;\r
-\r
- // see which portals are valid\r
- for (p=node->portals ; p ; p = p->next[s])\r
- {\r
- s = (p->nodes[1] == node);\r
-\r
- p->face[s] = FaceFromPortal (p, s);\r
- if (p->face[s])\r
- {\r
- c_nodefaces++;\r
- p->face[s]->next = p->onnode->faces;\r
- p->onnode->faces = p->face[s];\r
- }\r
- }\r
-}\r
-\r
-/*\r
-============\r
-MakeFaces\r
-============\r
-*/\r
-void MakeFaces (node_t *node)\r
-{\r
- Sys_FPrintf( SYS_VRB, "--- MakeFaces ---\n");\r
- c_merge = 0;\r
- c_subdivide = 0;\r
- c_nodefaces = 0;\r
-\r
- MakeFaces_r (node);\r
-\r
- Sys_FPrintf( SYS_VRB, "%5i makefaces\n", c_nodefaces);\r
- Sys_FPrintf( SYS_VRB, "%5i merged\n", c_merge);\r
- Sys_FPrintf( SYS_VRB, "%5i subdivided\n", c_subdivide);\r
-}\r
+/*
+Copyright (C) 1999-2007 id Software, Inc. and contributors.
+For a list of contributors, see the accompanying CONTRIBUTORS file.
+
+This file is part of GtkRadiant.
+
+GtkRadiant is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+GtkRadiant is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GtkRadiant; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+*/
+// faces.c
+
+#include "qbsp.h"
+
+/*
+
+ some faces will be removed before saving, but still form nodes:
+
+ the insides of sky volumes
+ meeting planes of different water current volumes
+
+*/
+
+// undefine for dumb linear searches
+#define USE_HASHING
+
+#define INTEGRAL_EPSILON 0.01
+#define POINT_EPSILON 0.5
+#define OFF_EPSILON 0.5
+
+int c_merge;
+int c_subdivide;
+
+int c_totalverts;
+int c_uniqueverts;
+int c_degenerate;
+int c_tjunctions;
+int c_faceoverflows;
+int c_facecollapse;
+int c_badstartverts;
+
+#define MAX_SUPERVERTS 512
+int superverts[MAX_SUPERVERTS];
+int numsuperverts;
+
+face_t *edgefaces[MAX_MAP_EDGES][2];
+int firstmodeledge = 1;
+int firstmodelface;
+
+int c_tryedges;
+
+vec3_t edge_dir;
+vec3_t edge_start;
+vec_t edge_len;
+
+int num_edge_verts;
+int edge_verts[MAX_MAP_VERTS];
+
+
+float subdivide_size = 240;
+
+
+face_t *NewFaceFromFace (face_t *f);
+
+//===========================================================================
+
+typedef struct hashvert_s
+{
+ struct hashvert_s *next;
+ int num;
+} hashvert_t;
+
+
+#define HASH_SIZE 64
+
+
+int vertexchain[MAX_MAP_VERTS]; // the next vertex in a hash chain
+int hashverts[HASH_SIZE*HASH_SIZE]; // a vertex number, or 0 for no verts
+
+face_t *edgefaces[MAX_MAP_EDGES][2];
+
+//============================================================================
+
+
+unsigned HashVec (vec3_t vec)
+{
+ int x, y;
+
+ x = (4096 + (int)(vec[0]+0.5)) >> 7;
+ y = (4096 + (int)(vec[1]+0.5)) >> 7;
+
+ if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE )
+ Error ("HashVec: point outside valid range");
+
+ return y*HASH_SIZE + x;
+}
+
+#ifdef USE_HASHING
+/*
+=============
+GetVertex
+
+Uses hashing
+=============
+*/
+int GetVertexnum (vec3_t in)
+{
+ int h;
+ int i;
+ float *p;
+ vec3_t vert;
+ int vnum;
+
+ c_totalverts++;
+
+ for (i=0 ; i<3 ; i++)
+ {
+ if ( fabs(in[i] - Q_rint(in[i])) < INTEGRAL_EPSILON)
+ vert[i] = Q_rint(in[i]);
+ else
+ vert[i] = in[i];
+ }
+
+ h = HashVec (vert);
+
+ for (vnum=hashverts[h] ; vnum ; vnum=vertexchain[vnum])
+ {
+ p = dvertexes[vnum].point;
+ if ( fabs(p[0]-vert[0])<POINT_EPSILON
+ && fabs(p[1]-vert[1])<POINT_EPSILON
+ && fabs(p[2]-vert[2])<POINT_EPSILON )
+ return vnum;
+ }
+
+// emit a vertex
+ if (numvertexes == MAX_MAP_VERTS)
+ Error ("numvertexes == MAX_MAP_VERTS");
+
+ dvertexes[numvertexes].point[0] = vert[0];
+ dvertexes[numvertexes].point[1] = vert[1];
+ dvertexes[numvertexes].point[2] = vert[2];
+
+ vertexchain[numvertexes] = hashverts[h];
+ hashverts[h] = numvertexes;
+
+ c_uniqueverts++;
+
+ numvertexes++;
+
+ return numvertexes-1;
+}
+#else
+/*
+==================
+GetVertexnum
+
+Dumb linear search
+==================
+*/
+int GetVertexnum (vec3_t v)
+{
+ int i, j;
+ dvertex_t *dv;
+ vec_t d;
+
+ c_totalverts++;
+
+ // make really close values exactly integral
+ for (i=0 ; i<3 ; i++)
+ {
+ if ( fabs(v[i] - (int)(v[i]+0.5)) < INTEGRAL_EPSILON )
+ v[i] = (int)(v[i]+0.5);
+ if (v[i] < -4096 || v[i] > 4096)
+ Error ("GetVertexnum: outside +/- 4096");
+ }
+
+ // search for an existing vertex match
+ for (i=0, dv=dvertexes ; i<numvertexes ; i++, dv++)
+ {
+ for (j=0 ; j<3 ; j++)
+ {
+ d = v[j] - dv->point[j];
+ if ( d > POINT_EPSILON || d < -POINT_EPSILON)
+ break;
+ }
+ if (j == 3)
+ return i; // a match
+ }
+
+ // new point
+ if (numvertexes == MAX_MAP_VERTS)
+ Error ("MAX_MAP_VERTS");
+ VectorCopy (v, dv->point);
+ numvertexes++;
+ c_uniqueverts++;
+
+ return numvertexes-1;
+}
+#endif
+
+
+/*
+==================
+FaceFromSuperverts
+
+The faces vertexes have beeb added to the superverts[] array,
+and there may be more there than can be held in a face (MAXEDGES).
+
+If less, the faces vertexnums[] will be filled in, otherwise
+face will reference a tree of split[] faces until all of the
+vertexnums can be added.
+
+superverts[base] will become face->vertexnums[0], and the others
+will be circularly filled in.
+==================
+*/
+void FaceFromSuperverts (node_t *node, face_t *f, int base)
+{
+ face_t *newf;
+ int remaining;
+ int i;
+
+ remaining = numsuperverts;
+ while (remaining > MAXEDGES)
+ { // must split into two faces, because of vertex overload
+ c_faceoverflows++;
+
+ newf = f->split[0] = NewFaceFromFace (f);
+ newf = f->split[0];
+ newf->next = node->faces;
+ node->faces = newf;
+
+ newf->numpoints = MAXEDGES;
+ for (i=0 ; i<MAXEDGES ; i++)
+ newf->vertexnums[i] = superverts[(i+base)%numsuperverts];
+
+ f->split[1] = NewFaceFromFace (f);
+ f = f->split[1];
+ f->next = node->faces;
+ node->faces = f;
+
+ remaining -= (MAXEDGES-2);
+ base = (base+MAXEDGES-1)%numsuperverts;
+ }
+
+ // copy the vertexes back to the face
+ f->numpoints = remaining;
+ for (i=0 ; i<remaining ; i++)
+ f->vertexnums[i] = superverts[(i+base)%numsuperverts];
+}
+
+
+/*
+==================
+EmitFaceVertexes
+==================
+*/
+void EmitFaceVertexes (node_t *node, face_t *f)
+{
+ winding_t *w;
+ int i;
+
+ if (f->merged || f->split[0] || f->split[1])
+ return;
+
+ w = f->w;
+ for (i=0 ; i<w->numpoints ; i++)
+ {
+ if (noweld)
+ { // make every point unique
+ if (numvertexes == MAX_MAP_VERTS)
+ Error ("MAX_MAP_VERTS");
+ superverts[i] = numvertexes;
+ VectorCopy (w->p[i], dvertexes[numvertexes].point);
+ numvertexes++;
+ c_uniqueverts++;
+ c_totalverts++;
+ }
+ else
+ superverts[i] = GetVertexnum (w->p[i]);
+ }
+ numsuperverts = w->numpoints;
+
+ // this may fragment the face if > MAXEDGES
+ FaceFromSuperverts (node, f, 0);
+}
+
+/*
+==================
+EmitVertexes_r
+==================
+*/
+void EmitVertexes_r (node_t *node)
+{
+ int i;
+ face_t *f;
+
+ if (node->planenum == PLANENUM_LEAF)
+ return;
+
+ for (f=node->faces ; f ; f=f->next)
+ {
+ EmitFaceVertexes (node, f);
+ }
+
+ for (i=0 ; i<2 ; i++)
+ EmitVertexes_r (node->children[i]);
+}
+
+
+#ifdef USE_HASHING
+/*
+==========
+FindEdgeVerts
+
+Uses the hash tables to cut down to a small number
+==========
+*/
+void FindEdgeVerts (vec3_t v1, vec3_t v2)
+{
+ int x1, x2, y1, y2, t;
+ int x, y;
+ int vnum;
+
+#if 0
+{
+ int i;
+ num_edge_verts = numvertexes-1;
+ for (i=0 ; i<numvertexes-1 ; i++)
+ edge_verts[i] = i+1;
+}
+#endif
+
+ x1 = (4096 + (int)(v1[0]+0.5)) >> 7;
+ y1 = (4096 + (int)(v1[1]+0.5)) >> 7;
+ x2 = (4096 + (int)(v2[0]+0.5)) >> 7;
+ y2 = (4096 + (int)(v2[1]+0.5)) >> 7;
+
+ if (x1 > x2)
+ {
+ t = x1;
+ x1 = x2;
+ x2 = t;
+ }
+ if (y1 > y2)
+ {
+ t = y1;
+ y1 = y2;
+ y2 = t;
+ }
+#if 0
+ x1--;
+ x2++;
+ y1--;
+ y2++;
+ if (x1 < 0)
+ x1 = 0;
+ if (x2 >= HASH_SIZE)
+ x2 = HASH_SIZE;
+ if (y1 < 0)
+ y1 = 0;
+ if (y2 >= HASH_SIZE)
+ y2 = HASH_SIZE;
+#endif
+ num_edge_verts = 0;
+ for (x=x1 ; x <= x2 ; x++)
+ {
+ for (y=y1 ; y <= y2 ; y++)
+ {
+ for (vnum=hashverts[y*HASH_SIZE+x] ; vnum ; vnum=vertexchain[vnum])
+ {
+ edge_verts[num_edge_verts++] = vnum;
+ }
+ }
+ }
+}
+
+#else
+/*
+==========
+FindEdgeVerts
+
+Forced a dumb check of everything
+==========
+*/
+void FindEdgeVerts (vec3_t v1, vec3_t v2)
+{
+ int i;
+
+ num_edge_verts = numvertexes-1;
+ for (i=0 ; i<num_edge_verts ; i++)
+ edge_verts[i] = i+1;
+}
+#endif
+
+/*
+==========
+TestEdge
+
+Can be recursively reentered
+==========
+*/
+void TestEdge (vec_t start, vec_t end, int p1, int p2, int startvert)
+{
+ int j, k;
+ vec_t dist;
+ vec3_t delta;
+ vec3_t exact;
+ vec3_t off;
+ vec_t error;
+ vec3_t p;
+
+ if (p1 == p2)
+ {
+ c_degenerate++;
+ return; // degenerate edge
+ }
+
+ for (k=startvert ; k<num_edge_verts ; k++)
+ {
+ j = edge_verts[k];
+ if (j==p1 || j == p2)
+ continue;
+
+ VectorCopy (dvertexes[j].point, p);
+
+ VectorSubtract (p, edge_start, delta);
+ dist = DotProduct (delta, edge_dir);
+ if (dist <=start || dist >= end)
+ continue; // off an end
+ VectorMA (edge_start, dist, edge_dir, exact);
+ VectorSubtract (p, exact, off);
+ error = VectorLength (off);
+
+ if (fabs(error) > OFF_EPSILON)
+ continue; // not on the edge
+
+ // break the edge
+ c_tjunctions++;
+ TestEdge (start, dist, p1, j, k+1);
+ TestEdge (dist, end, j, p2, k+1);
+ return;
+ }
+
+ // the edge p1 to p2 is now free of tjunctions
+ if (numsuperverts >= MAX_SUPERVERTS)
+ Error ("MAX_SUPERVERTS");
+ superverts[numsuperverts] = p1;
+ numsuperverts++;
+}
+
+/*
+==================
+FixFaceEdges
+
+==================
+*/
+void FixFaceEdges (node_t *node, face_t *f)
+{
+ int p1, p2;
+ int i;
+ vec3_t e2;
+ vec_t len;
+ int count[MAX_SUPERVERTS], start[MAX_SUPERVERTS];
+ int base;
+
+ if (f->merged || f->split[0] || f->split[1])
+ return;
+
+ numsuperverts = 0;
+
+ for (i=0 ; i<f->numpoints ; i++)
+ {
+ p1 = f->vertexnums[i];
+ p2 = f->vertexnums[(i+1)%f->numpoints];
+
+ VectorCopy (dvertexes[p1].point, edge_start);
+ VectorCopy (dvertexes[p2].point, e2);
+
+ FindEdgeVerts (edge_start, e2);
+
+ VectorSubtract (e2, edge_start, edge_dir);
+ len = VectorNormalize (edge_dir, edge_dir);
+
+ start[i] = numsuperverts;
+ TestEdge (0, len, p1, p2, 0);
+
+ count[i] = numsuperverts - start[i];
+ }
+
+ if (numsuperverts < 3)
+ { // entire face collapsed
+ f->numpoints = 0;
+ c_facecollapse++;
+ return;
+ }
+
+ // we want to pick a vertex that doesn't have tjunctions
+ // on either side, which can cause artifacts on trifans,
+ // especially underwater
+ for (i=0 ; i<f->numpoints ; i++)
+ {
+ if (count[i] == 1 && count[(i+f->numpoints-1)%f->numpoints] == 1)
+ break;
+ }
+ if (i == f->numpoints)
+ {
+ f->badstartvert = true;
+ c_badstartverts++;
+ base = 0;
+ }
+ else
+ { // rotate the vertex order
+ base = start[i];
+ }
+
+ // this may fragment the face if > MAXEDGES
+ FaceFromSuperverts (node, f, base);
+}
+
+/*
+==================
+FixEdges_r
+==================
+*/
+void FixEdges_r (node_t *node)
+{
+ int i;
+ face_t *f;
+
+ if (node->planenum == PLANENUM_LEAF)
+ return;
+
+ for (f=node->faces ; f ; f=f->next)
+ FixFaceEdges (node, f);
+
+ for (i=0 ; i<2 ; i++)
+ FixEdges_r (node->children[i]);
+}
+
+/*
+===========
+FixTjuncs
+
+===========
+*/
+void FixTjuncs (node_t *headnode)
+{
+ // snap and merge all vertexes
+ Sys_FPrintf( SYS_VRB, "---- snap verts ----\n");
+ memset (hashverts, 0, sizeof(hashverts));
+ c_totalverts = 0;
+ c_uniqueverts = 0;
+ c_faceoverflows = 0;
+ EmitVertexes_r (headnode);
+ Sys_FPrintf( SYS_VRB, "%i unique from %i\n", c_uniqueverts, c_totalverts);
+
+ // break edges on tjunctions
+ Sys_FPrintf( SYS_VRB, "---- tjunc ----\n");
+ c_tryedges = 0;
+ c_degenerate = 0;
+ c_facecollapse = 0;
+ c_tjunctions = 0;
+ if (!notjunc)
+ FixEdges_r (headnode);
+ Sys_FPrintf( SYS_VRB, "%5i edges degenerated\n", c_degenerate);
+ Sys_FPrintf( SYS_VRB, "%5i faces degenerated\n", c_facecollapse);
+ Sys_FPrintf( SYS_VRB, "%5i edges added by tjunctions\n", c_tjunctions);
+ Sys_FPrintf( SYS_VRB, "%5i faces added by tjunctions\n", c_faceoverflows);
+ Sys_FPrintf( SYS_VRB, "%5i bad start verts\n", c_badstartverts);
+}
+
+
+//========================================================
+
+int c_faces;
+
+face_t *AllocFace (void)
+{
+ face_t *f;
+
+ f = malloc(sizeof(*f));
+ memset (f, 0, sizeof(*f));
+ c_faces++;
+
+ return f;
+}
+
+face_t *NewFaceFromFace (face_t *f)
+{
+ face_t *newf;
+
+ newf = AllocFace ();
+ *newf = *f;
+ newf->merged = NULL;
+ newf->split[0] = newf->split[1] = NULL;
+ newf->w = NULL;
+ return newf;
+}
+
+void FreeFace (face_t *f)
+{
+ if (f->w)
+ FreeWinding (f->w);
+ free (f);
+ c_faces--;
+}
+
+//========================================================
+
+/*
+==================
+GetEdge
+
+Called by writebsp.
+Don't allow four way edges
+==================
+*/
+int GetEdge2 (int v1, int v2, face_t *f)
+{
+ dedge_t *edge;
+ int i;
+
+ c_tryedges++;
+
+ if (!noshare)
+ {
+ for (i=firstmodeledge ; i < numedges ; i++)
+ {
+ edge = &dedges[i];
+ if (v1 == edge->v[1] && v2 == edge->v[0]
+ && edgefaces[i][0]->contents == f->contents)
+ {
+ if (edgefaces[i][1])
+ // Sys_Printf ("WARNING: multiple backward edge\n");
+ continue;
+ edgefaces[i][1] = f;
+ return -i;
+ }
+ #if 0
+ if (v1 == edge->v[0] && v2 == edge->v[1])
+ {
+ Sys_Printf ("WARNING: multiple forward edge\n");
+ return i;
+ }
+ #endif
+ }
+ }
+
+// emit an edge
+ if (numedges >= MAX_MAP_EDGES)
+ Error ("numedges == MAX_MAP_EDGES");
+ edge = &dedges[numedges];
+ numedges++;
+ edge->v[0] = v1;
+ edge->v[1] = v2;
+ edgefaces[numedges-1][0] = f;
+
+ return numedges-1;
+}
+
+/*
+===========================================================================
+
+FACE MERGING
+
+===========================================================================
+*/
+
+#define CONTINUOUS_EPSILON 0.001
+
+/*
+=============
+TryMergeWinding
+
+If two polygons share a common edge and the edges that meet at the
+common points are both inside the other polygons, merge them
+
+Returns NULL if the faces couldn't be merged, or the new face.
+The originals will NOT be freed.
+=============
+*/
+winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, vec3_t planenormal)
+{
+ vec_t *p1, *p2, *p3, *p4, *back;
+ winding_t *newf;
+ int i, j, k, l;
+ vec3_t normal, delta;
+ vec_t dot;
+ qboolean keep1, keep2;
+
+
+ //
+ // find a common edge
+ //
+ p1 = p2 = NULL; // stop compiler warning
+ j = 0; //
+
+ for (i=0 ; i<f1->numpoints ; i++)
+ {
+ p1 = f1->p[i];
+ p2 = f1->p[(i+1)%f1->numpoints];
+ for (j=0 ; j<f2->numpoints ; j++)
+ {
+ p3 = f2->p[j];
+ p4 = f2->p[(j+1)%f2->numpoints];
+ for (k=0 ; k<3 ; k++)
+ {
+ if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
+ break;
+ if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
+ break;
+ }
+ if (k==3)
+ break;
+ }
+ if (j < f2->numpoints)
+ break;
+ }
+
+ if (i == f1->numpoints)
+ return NULL; // no matching edges
+
+ //
+ // check slope of connected lines
+ // if the slopes are colinear, the point can be removed
+ //
+ back = f1->p[(i+f1->numpoints-1)%f1->numpoints];
+ VectorSubtract (p1, back, delta);
+ CrossProduct (planenormal, delta, normal);
+ VectorNormalize (normal, normal);
+
+ back = f2->p[(j+2)%f2->numpoints];
+ VectorSubtract (back, p1, delta);
+ dot = DotProduct (delta, normal);
+ if (dot > CONTINUOUS_EPSILON)
+ return NULL; // not a convex polygon
+ keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
+
+ back = f1->p[(i+2)%f1->numpoints];
+ VectorSubtract (back, p2, delta);
+ CrossProduct (planenormal, delta, normal);
+ VectorNormalize (normal, normal);
+
+ back = f2->p[(j+f2->numpoints-1)%f2->numpoints];
+ VectorSubtract (back, p2, delta);
+ dot = DotProduct (delta, normal);
+ if (dot > CONTINUOUS_EPSILON)
+ return NULL; // not a convex polygon
+ keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);
+
+ //
+ // build the new polygon
+ //
+ newf = AllocWinding (f1->numpoints + f2->numpoints);
+
+ // copy first polygon
+ for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
+ {
+ if (k==(i+1)%f1->numpoints && !keep2)
+ continue;
+
+ VectorCopy (f1->p[k], newf->p[newf->numpoints]);
+ newf->numpoints++;
+ }
+
+ // copy second polygon
+ for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
+ {
+ if (l==(j+1)%f2->numpoints && !keep1)
+ continue;
+ VectorCopy (f2->p[l], newf->p[newf->numpoints]);
+ newf->numpoints++;
+ }
+
+ return newf;
+}
+
+/*
+=============
+TryMerge
+
+If two polygons share a common edge and the edges that meet at the
+common points are both inside the other polygons, merge them
+
+Returns NULL if the faces couldn't be merged, or the new face.
+The originals will NOT be freed.
+=============
+*/
+face_t *TryMerge (face_t *f1, face_t *f2, vec3_t planenormal)
+{
+ face_t *newf;
+ winding_t *nw;
+
+ if (!f1->w || !f2->w)
+ return NULL;
+ if (f1->texinfo != f2->texinfo)
+ return NULL;
+ if (f1->planenum != f2->planenum) // on front and back sides
+ return NULL;
+ if (f1->contents != f2->contents)
+ return NULL;
+
+
+ nw = TryMergeWinding (f1->w, f2->w, planenormal);
+ if (!nw)
+ return NULL;
+
+ c_merge++;
+ newf = NewFaceFromFace (f1);
+ newf->w = nw;
+
+ f1->merged = newf;
+ f2->merged = newf;
+
+ return newf;
+}
+
+/*
+===============
+MergeNodeFaces
+===============
+*/
+void MergeNodeFaces (node_t *node)
+{
+ face_t *f1, *f2, *end;
+ face_t *merged;
+ plane_t *plane;
+
+ plane = &mapplanes[node->planenum];
+ merged = NULL;
+
+ for (f1 = node->faces ; f1 ; f1 = f1->next)
+ {
+ if (f1->merged || f1->split[0] || f1->split[1])
+ continue;
+ for (f2 = node->faces ; f2 != f1 ; f2=f2->next)
+ {
+ if (f2->merged || f2->split[0] || f2->split[1])
+ continue;
+ merged = TryMerge (f1, f2, plane->normal);
+ if (!merged)
+ continue;
+
+ // add merged to the end of the node face list
+ // so it will be checked against all the faces again
+ for (end = node->faces ; end->next ; end = end->next)
+ ;
+ merged->next = NULL;
+ end->next = merged;
+ break;
+ }
+ }
+}
+
+//=====================================================================
+
+/*
+===============
+SubdivideFace
+
+Chop up faces that are larger than we want in the surface cache
+===============
+*/
+void SubdivideFace (node_t *node, face_t *f)
+{
+ float mins, maxs;
+ vec_t v;
+ int axis, i;
+ texinfo_t *tex;
+ vec3_t temp;
+ vec_t dist;
+ winding_t *w, *frontw, *backw;
+
+ if (f->merged)
+ return;
+
+// special (non-surface cached) faces don't need subdivision
+ tex = &texinfo[f->texinfo];
+
+ if ( tex->flags & (SURF_WARP|SURF_SKY) )
+ {
+ return;
+ }
+
+ for (axis = 0 ; axis < 2 ; axis++)
+ {
+ while (1)
+ {
+ mins = 999999;
+ maxs = -999999;
+
+ VectorCopy (tex->vecs[axis], temp);
+ w = f->w;
+ for (i=0 ; i<w->numpoints ; i++)
+ {
+ v = DotProduct (w->p[i], temp);
+ if (v < mins)
+ mins = v;
+ if (v > maxs)
+ maxs = v;
+ }
+#if 0
+ if (maxs - mins <= 0)
+ Error ("zero extents");
+#endif
+ if (axis == 2)
+ { // allow double high walls
+ if (maxs - mins <= subdivide_size/* *2 */)
+ break;
+ }
+ else if (maxs - mins <= subdivide_size)
+ break;
+
+ // split it
+ c_subdivide++;
+
+ v = VectorNormalize (temp, temp);
+
+ dist = (mins + subdivide_size - 16)/v;
+
+ ClipWindingEpsilon (w, temp, dist, ON_EPSILON, &frontw, &backw);
+ if (!frontw || !backw)
+ Error ("SubdivideFace: didn't split the polygon");
+
+ f->split[0] = NewFaceFromFace (f);
+ f->split[0]->w = frontw;
+ f->split[0]->next = node->faces;
+ node->faces = f->split[0];
+
+ f->split[1] = NewFaceFromFace (f);
+ f->split[1]->w = backw;
+ f->split[1]->next = node->faces;
+ node->faces = f->split[1];
+
+ SubdivideFace (node, f->split[0]);
+ SubdivideFace (node, f->split[1]);
+ return;
+ }
+ }
+}
+
+void SubdivideNodeFaces (node_t *node)
+{
+ face_t *f;
+
+ for (f = node->faces ; f ; f=f->next)
+ {
+ SubdivideFace (node, f);
+ }
+}
+
+//===========================================================================
+
+int c_nodefaces;
+
+
+/*
+============
+FaceFromPortal
+
+============
+*/
+face_t *FaceFromPortal (portal_t *p, int pside)
+{
+ face_t *f;
+ side_t *side;
+
+ side = p->side;
+ if (!side)
+ return NULL; // portal does not bridge different visible contents
+
+ f = AllocFace ();
+
+ f->texinfo = side->texinfo;
+ f->planenum = (side->planenum & ~1) | pside;
+ f->portal = p;
+
+ if ( (p->nodes[pside]->contents & CONTENTS_WINDOW)
+ && VisibleContents(p->nodes[!pside]->contents^p->nodes[pside]->contents) == CONTENTS_WINDOW )
+ return NULL; // don't show insides of windows
+
+ if (pside)
+ {
+ f->w = ReverseWinding(p->winding);
+ f->contents = p->nodes[1]->contents;
+ }
+ else
+ {
+ f->w = CopyWinding(p->winding);
+ f->contents = p->nodes[0]->contents;
+ }
+ return f;
+}
+
+
+/*
+===============
+MakeFaces_r
+
+If a portal will make a visible face,
+mark the side that originally created it
+
+ solid / empty : solid
+ solid / water : solid
+ water / empty : water
+ water / water : none
+===============
+*/
+void MakeFaces_r (node_t *node)
+{
+ portal_t *p;
+ int s;
+
+ // recurse down to leafs
+ if (node->planenum != PLANENUM_LEAF)
+ {
+ MakeFaces_r (node->children[0]);
+ MakeFaces_r (node->children[1]);
+
+ // merge together all visible faces on the node
+ if (!nomerge)
+ MergeNodeFaces (node);
+ if (!nosubdiv)
+ SubdivideNodeFaces (node);
+
+ return;
+ }
+
+ // solid leafs never have visible faces
+ if (node->contents & CONTENTS_SOLID)
+ return;
+
+ // see which portals are valid
+ for (p=node->portals ; p ; p = p->next[s])
+ {
+ s = (p->nodes[1] == node);
+
+ p->face[s] = FaceFromPortal (p, s);
+ if (p->face[s])
+ {
+ c_nodefaces++;
+ p->face[s]->next = p->onnode->faces;
+ p->onnode->faces = p->face[s];
+ }
+ }
+}
+
+/*
+============
+MakeFaces
+============
+*/
+void MakeFaces (node_t *node)
+{
+ Sys_FPrintf( SYS_VRB, "--- MakeFaces ---\n");
+ c_merge = 0;
+ c_subdivide = 0;
+ c_nodefaces = 0;
+
+ MakeFaces_r (node);
+
+ Sys_FPrintf( SYS_VRB, "%5i makefaces\n", c_nodefaces);
+ Sys_FPrintf( SYS_VRB, "%5i merged\n", c_merge);
+ Sys_FPrintf( SYS_VRB, "%5i subdivided\n", c_subdivide);
+}
projects / xonotic / netradiant.git / blobdiff