+++ /dev/null
-/*
-Copyright (C) 1999-2006 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);
-}