123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077 |
- /*
- ===========================================================================
- 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);
- }
|