--- /dev/null
+/*
+===========================================================================
+Copyright (C) 1997-2006 Id Software, Inc.
+
+This file is part of Quake 2 Tools source code.
+
+Quake 2 Tools source code 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.
+
+Quake 2 Tools source code 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 Quake 2 Tools source code; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+===========================================================================
+*/
+
+#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
+ qprintf ("---- snap verts ----\n");
+ memset (hashverts, 0, sizeof(hashverts));
+ c_totalverts = 0;
+ c_uniqueverts = 0;
+ c_faceoverflows = 0;
+ EmitVertexes_r (headnode);
+ qprintf ("%i unique from %i\n", c_uniqueverts, c_totalverts);
+
+ // break edges on tjunctions
+ qprintf ("---- tjunc ----\n");
+ c_tryedges = 0;
+ c_degenerate = 0;
+ c_facecollapse = 0;
+ c_tjunctions = 0;
+ if (!notjunc)
+ FixEdges_r (headnode);
+ qprintf ("%5i edges degenerated\n", c_degenerate);
+ qprintf ("%5i faces degenerated\n", c_facecollapse);
+ qprintf ("%5i edges added by tjunctions\n", c_tjunctions);
+ qprintf ("%5i faces added by tjunctions\n", c_faceoverflows);
+ qprintf ("%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])
+ // printf ("WARNING: multiple backward edge\n");
+ continue;
+ edgefaces[i][1] = f;
+ return -i;
+ }
+ #if 0
+ if (v1 == edge->v[0] && v2 == edge->v[1])
+ {
+ 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)
+{
+ qprintf ("--- MakeFaces ---\n");
+ c_merge = 0;
+ c_subdivide = 0;
+ c_nodefaces = 0;
+
+ MakeFaces_r (node);
+
+ qprintf ("%5i makefaces\n", c_nodefaces);
+ qprintf ("%5i merged\n", c_merge);
+ qprintf ("%5i subdivided\n", c_subdivide);
+}
projects / xonotic / netradiant.git / blobdiff