/*
-Copyright (C) 1999-2007 id Software, Inc. and contributors.
-For a list of contributors, see the accompanying CONTRIBUTORS file.
+ 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.
+ 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 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.
+ 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
-*/
+ 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:
+ some faces will be removed before saving, but still form nodes:
- the insides of sky volumes
- meeting planes of different water current volumes
+ the insides of sky volumes
+ meeting planes of different water current volumes
-*/
+ */
// undefine for dumb linear searches
-#define USE_HASHING
+#define USE_HASHING
-#define INTEGRAL_EPSILON 0.01
-#define POINT_EPSILON 0.5
-#define OFF_EPSILON 0.5
+#define INTEGRAL_EPSILON 0.01
+#define POINT_EPSILON 0.5
+#define OFF_EPSILON 0.5
-int c_merge;
-int c_subdivide;
+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;
+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;
+#define MAX_SUPERVERTS 512
+int superverts[MAX_SUPERVERTS];
+int numsuperverts;
-face_t *edgefaces[MAX_MAP_EDGES][2];
-int firstmodeledge = 1;
-int firstmodelface;
+face_t *edgefaces[MAX_MAP_EDGES][2];
+int firstmodeledge = 1;
+int firstmodelface;
-int c_tryedges;
+int c_tryedges;
-vec3_t edge_dir;
-vec3_t edge_start;
-vec_t edge_len;
+vec3_t edge_dir;
+vec3_t edge_start;
+vec_t edge_len;
-int num_edge_verts;
-int edge_verts[MAX_MAP_VERTS];
+int num_edge_verts;
+int edge_verts[MAX_MAP_VERTS];
-float subdivide_size = 240;
+float subdivide_size = 240;
-face_t *NewFaceFromFace (face_t *f);
+face_t *NewFaceFromFace( face_t *f );
//===========================================================================
typedef struct hashvert_s
{
- struct hashvert_s *next;
- int num;
+ struct hashvert_s *next;
+ int num;
} hashvert_t;
-#define HASH_SIZE 64
+#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
+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];
+face_t *edgefaces[MAX_MAP_EDGES][2];
//============================================================================
-unsigned HashVec (vec3_t vec)
-{
- int x, y;
+unsigned HashVec( vec3_t vec ){
+ int x, y;
+
+ x = ( 4096 + (int)( vec[0] + 0.5 ) ) >> 7;
+ y = ( 4096 + (int)( vec[1] + 0.5 ) ) >> 7;
- 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" );
+ }
- if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE )
- Error ("HashVec: point outside valid range");
-
- return y*HASH_SIZE + x;
+ 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;
+ =============
+ 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++)
+ for ( i = 0 ; i < 3 ; i++ )
{
- if ( fabs(in[i] - Q_rint(in[i])) < INTEGRAL_EPSILON)
- vert[i] = Q_rint(in[i]);
- else
+ 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])
+
+ 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 )
+ 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");
+ if ( numvertexes == MAX_MAP_VERTS ) {
+ Error( "numvertexes == MAX_MAP_VERTS" );
+ }
dvertexes[numvertexes].point[0] = vert[0];
dvertexes[numvertexes].point[1] = vert[1];
c_uniqueverts++;
numvertexes++;
-
- return numvertexes-1;
+
+ return numvertexes - 1;
}
#else
/*
-==================
-GetVertexnum
+ ==================
+ GetVertexnum
-Dumb linear search
-==================
-*/
-int GetVertexnum (vec3_t v)
-{
- int i, j;
- dvertex_t *dv;
- vec_t d;
+ 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++)
+ 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");
+ 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 ( i = 0, dv = dvertexes ; i < numvertexes ; i++, dv++ )
{
- for (j=0 ; j<3 ; j++)
+ for ( j = 0 ; j < 3 ; j++ )
{
d = v[j] - dv->point[j];
- if ( d > POINT_EPSILON || d < -POINT_EPSILON)
+ if ( d > POINT_EPSILON || d < -POINT_EPSILON ) {
break;
+ }
+ }
+ if ( j == 3 ) {
+ return i; // a match
}
- if (j == 3)
- return i; // a match
}
// new point
- if (numvertexes == MAX_MAP_VERTS)
- Error ("MAX_MAP_VERTS");
- VectorCopy (v, dv->point);
+ if ( numvertexes == MAX_MAP_VERTS ) {
+ Error( "MAX_MAP_VERTS" );
+ }
+ VectorCopy( v, dv->point );
numvertexes++;
c_uniqueverts++;
- return numvertexes-1;
+ return numvertexes - 1;
}
#endif
/*
-==================
-FaceFromSuperverts
+ ==================
+ 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).
+ 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.
+ 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;
+ 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
+ while ( remaining > MAXEDGES )
+ { // must split into two faces, because of vertex overload
c_faceoverflows++;
- newf = f->split[0] = NewFaceFromFace (f);
+ 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];
+ for ( i = 0 ; i < MAXEDGES ; i++ )
+ newf->vertexnums[i] = superverts[( i + base ) % numsuperverts];
- f->split[1] = NewFaceFromFace (f);
+ f->split[1] = NewFaceFromFace( f );
f = f->split[1];
f->next = node->faces;
node->faces = f;
- remaining -= (MAXEDGES-2);
- base = (base+MAXEDGES-1)%numsuperverts;
+ 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];
+ 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])
+ ==================
+ 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++)
+ for ( i = 0 ; i < w->numpoints ; i++ )
{
- if (noweld)
- { // make every point unique
- if (numvertexes == MAX_MAP_VERTS)
- Error ("MAX_MAP_VERTS");
+ 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);
+ VectorCopy( w->p[i], dvertexes[numvertexes].point );
numvertexes++;
c_uniqueverts++;
c_totalverts++;
}
- else
- superverts[i] = GetVertexnum (w->p[i]);
+ else{
+ superverts[i] = GetVertexnum( w->p[i] );
+ }
}
numsuperverts = w->numpoints;
// this may fragment the face if > MAXEDGES
- FaceFromSuperverts (node, f, 0);
+ FaceFromSuperverts( node, f, 0 );
}
/*
-==================
-EmitVertexes_r
-==================
-*/
-void EmitVertexes_r (node_t *node)
-{
- int i;
- face_t *f;
-
- if (node->planenum == PLANENUM_LEAF)
+ ==================
+ 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)
+ for ( f = node->faces ; f ; f = f->next )
{
- EmitFaceVertexes (node, f);
+ EmitFaceVertexes( node, f );
}
- for (i=0 ; i<2 ; i++)
- EmitVertexes_r (node->children[i]);
+ for ( i = 0 ; i < 2 ; i++ )
+ EmitVertexes_r( node->children[i] );
}
#ifdef USE_HASHING
/*
-==========
-FindEdgeVerts
+ ==========
+ 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;
+ 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;
-}
+ {
+ 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;
+ 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)
- {
+ if ( x1 > x2 ) {
t = x1;
x1 = x2;
x2 = t;
}
- if (y1 > y2)
- {
+ if ( y1 > y2 ) {
t = y1;
y1 = y2;
y2 = t;
x2++;
y1--;
y2++;
- if (x1 < 0)
+ if ( x1 < 0 ) {
x1 = 0;
- if (x2 >= HASH_SIZE)
+ }
+ if ( x2 >= HASH_SIZE ) {
x2 = HASH_SIZE;
- if (y1 < 0)
+ }
+ if ( y1 < 0 ) {
y1 = 0;
- if (y2 >= HASH_SIZE)
+ }
+ if ( y2 >= HASH_SIZE ) {
y2 = HASH_SIZE;
+ }
#endif
num_edge_verts = 0;
- for (x=x1 ; x <= x2 ; x++)
+ for ( x = x1 ; x <= x2 ; x++ )
{
- for (y=y1 ; y <= y2 ; y++)
+ for ( y = y1 ; y <= y2 ; y++ )
{
- for (vnum=hashverts[y*HASH_SIZE+x] ; vnum ; vnum=vertexchain[vnum])
+ 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;
+ ==========
+ 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)
- {
+ ==========
+ 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
+ return; // degenerate edge
}
- for (k=startvert ; k<num_edge_verts ; k++)
+ for ( k = startvert ; k < num_edge_verts ; k++ )
{
j = edge_verts[k];
- if (j==p1 || j == p2)
+ if ( j == p1 || j == p2 ) {
continue;
+ }
- VectorCopy (dvertexes[j].point, p);
+ 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);
+ 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
+ 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);
+ 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");
+ 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])
+ ==================
+ 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++)
+ for ( i = 0 ; i < f->numpoints ; i++ )
{
p1 = f->vertexnums[i];
- p2 = f->vertexnums[(i+1)%f->numpoints];
+ p2 = f->vertexnums[( i + 1 ) % f->numpoints];
- VectorCopy (dvertexes[p1].point, edge_start);
- VectorCopy (dvertexes[p2].point, e2);
+ VectorCopy( dvertexes[p1].point, edge_start );
+ VectorCopy( dvertexes[p2].point, e2 );
- FindEdgeVerts (edge_start, e2);
+ FindEdgeVerts( edge_start, e2 );
- VectorSubtract (e2, edge_start, edge_dir);
- len = VectorNormalize (edge_dir, edge_dir);
+ VectorSubtract( e2, edge_start, edge_dir );
+ len = VectorNormalize( edge_dir, edge_dir );
start[i] = numsuperverts;
- TestEdge (0, len, p1, p2, 0);
+ TestEdge( 0, len, p1, p2, 0 );
count[i] = numsuperverts - start[i];
}
- if (numsuperverts < 3)
- { // entire face collapsed
+ 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++)
+ for ( i = 0 ; i < f->numpoints ; i++ )
{
- if (count[i] == 1 && count[(i+f->numpoints-1)%f->numpoints] == 1)
+ if ( count[i] == 1 && count[( i + f->numpoints - 1 ) % f->numpoints] == 1 ) {
break;
+ }
}
- if (i == f->numpoints)
- {
+ if ( i == f->numpoints ) {
f->badstartvert = true;
c_badstartverts++;
base = 0;
}
else
- { // rotate the vertex order
+ { // rotate the vertex order
base = start[i];
}
// this may fragment the face if > MAXEDGES
- FaceFromSuperverts (node, f, base);
+ FaceFromSuperverts( node, f, base );
}
/*
-==================
-FixEdges_r
-==================
-*/
-void FixEdges_r (node_t *node)
-{
- int i;
- face_t *f;
-
- if (node->planenum == PLANENUM_LEAF)
+ ==================
+ 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 ( f = node->faces ; f ; f = f->next )
+ FixFaceEdges( node, f );
- for (i=0 ; i<2 ; i++)
- FixEdges_r (node->children[i]);
+ for ( i = 0 ; i < 2 ; i++ )
+ FixEdges_r( node->children[i] );
}
/*
-===========
-FixTjuncs
+ ===========
+ FixTjuncs
-===========
-*/
-void FixTjuncs (node_t *headnode)
-{
+ ===========
+ */
+void FixTjuncs( node_t *headnode ){
// snap and merge all vertexes
- Sys_FPrintf( SYS_VRB, "---- snap verts ----\n");
- memset (hashverts, 0, sizeof(hashverts));
+ 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);
+ 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");
+ 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);
+ 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;
+int c_faces;
-face_t *AllocFace (void)
-{
- face_t *f;
+face_t *AllocFace( void ){
+ face_t *f;
- f = malloc(sizeof(*f));
- memset (f, 0, sizeof(*f));
+ f = malloc( sizeof( *f ) );
+ memset( f, 0, sizeof( *f ) );
c_faces++;
return f;
}
-face_t *NewFaceFromFace (face_t *f)
-{
- face_t *newf;
+face_t *NewFaceFromFace( face_t *f ){
+ face_t *newf;
- newf = AllocFace ();
+ newf = AllocFace();
*newf = *f;
newf->merged = NULL;
newf->split[0] = newf->split[1] = NULL;
return newf;
}
-void FreeFace (face_t *f)
-{
- if (f->w)
- FreeWinding (f->w);
- free (f);
+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;
+ ==================
+ 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++)
+ 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");
+ 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");
+ 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");
+ 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;
+ edgefaces[numedges - 1][0] = f;
+
+ return numedges - 1;
}
/*
-===========================================================================
+ ===========================================================================
-FACE MERGING
+ FACE MERGING
-===========================================================================
-*/
+ ===========================================================================
+ */
-#define CONTINUOUS_EPSILON 0.001
+#define CONTINUOUS_EPSILON 0.001
/*
-=============
-TryMergeWinding
+ =============
+ 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
+ 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;
-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 = 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++)
+ 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++)
+ p4 = f2->p[( j + 1 ) % f2->numpoints];
+ for ( k = 0 ; k < 3 ; k++ )
{
- if (fabs(p1[k] - p4[k]) > EQUAL_EPSILON)
+ if ( fabs( p1[k] - p4[k] ) > EQUAL_EPSILON ) {
break;
- if (fabs(p2[k] - p3[k]) > EQUAL_EPSILON)
+ }
+ if ( fabs( p2[k] - p3[k] ) > EQUAL_EPSILON ) {
break;
+ }
}
- if (k==3)
+ if ( k == 3 ) {
break;
+ }
}
- if (j < f2->numpoints)
+ if ( j < f2->numpoints ) {
break;
+ }
}
-
- if (i == f1->numpoints)
- return NULL; // no matching edges
+ 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);
+ 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);
-
+ newf = AllocWinding( f1->numpoints + f2->numpoints );
+
// copy first polygon
- for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
+ for ( k = ( i + 1 ) % f1->numpoints ; k != i ; k = ( k + 1 ) % f1->numpoints )
{
- if (k==(i+1)%f1->numpoints && !keep2)
+ if ( k == ( i + 1 ) % f1->numpoints && !keep2 ) {
continue;
-
- VectorCopy (f1->p[k], newf->p[newf->numpoints]);
+ }
+
+ 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)
+ for ( l = ( j + 1 ) % f2->numpoints ; l != j ; l = ( l + 1 ) % f2->numpoints )
{
- if (l==(j+1)%f2->numpoints && !keep1)
+ if ( l == ( j + 1 ) % f2->numpoints && !keep1 ) {
continue;
- VectorCopy (f2->p[l], newf->p[newf->numpoints]);
+ }
+ VectorCopy( f2->p[l], newf->p[newf->numpoints] );
newf->numpoints++;
}
}
/*
-=============
-TryMerge
+ =============
+ 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
+ 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;
+ 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)
+ if ( !f1->w || !f2->w ) {
return NULL;
- if (f1->texinfo != f2->texinfo)
+ }
+ if ( f1->texinfo != f2->texinfo ) {
return NULL;
- if (f1->planenum != f2->planenum) // on front and back sides
+ }
+ if ( f1->planenum != f2->planenum ) { // on front and back sides
return NULL;
- if (f1->contents != f2->contents)
+ }
+ if ( f1->contents != f2->contents ) {
return NULL;
-
+ }
- nw = TryMergeWinding (f1->w, f2->w, planenormal);
- if (!nw)
+
+ nw = TryMergeWinding( f1->w, f2->w, planenormal );
+ if ( !nw ) {
return NULL;
+ }
c_merge++;
- newf = NewFaceFromFace (f1);
+ newf = NewFaceFromFace( f1 );
newf->w = nw;
f1->merged = newf;
}
/*
-===============
-MergeNodeFaces
-===============
-*/
-void MergeNodeFaces (node_t *node)
-{
- face_t *f1, *f2, *end;
- face_t *merged;
- plane_t *plane;
+ ===============
+ 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)
+
+ for ( f1 = node->faces ; f1 ; f1 = f1->next )
{
- if (f1->merged || f1->split[0] || f1->split[1])
+ if ( f1->merged || f1->split[0] || f1->split[1] ) {
continue;
- for (f2 = node->faces ; f2 != f1 ; f2=f2->next)
+ }
+ for ( f2 = node->faces ; f2 != f1 ; f2 = f2->next )
{
- if (f2->merged || f2->split[0] || f2->split[1])
+ if ( f2->merged || f2->split[0] || f2->split[1] ) {
continue;
- merged = TryMerge (f1, f2, plane->normal);
- if (!merged)
+ }
+ merged = TryMerge( f1, f2, plane->normal );
+ if ( !merged ) {
continue;
+ }
- // add merged to the end of the node face list
+ // 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)
- ;
+ 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)
+ ===============
+ 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) )
- {
+ if ( tex->flags & ( SURF_WARP | SURF_SKY ) ) {
return;
}
- for (axis = 0 ; axis < 2 ; axis++)
+ for ( axis = 0 ; axis < 2 ; axis++ )
{
- while (1)
+ while ( 1 )
{
mins = 999999;
maxs = -999999;
-
- VectorCopy (tex->vecs[axis], temp);
+
+ VectorCopy( tex->vecs[axis], temp );
w = f->w;
- for (i=0 ; i<w->numpoints ; i++)
+ for ( i = 0 ; i < w->numpoints ; i++ )
{
- v = DotProduct (w->p[i], temp);
- if (v < mins)
+ v = DotProduct( w->p[i], temp );
+ if ( v < mins ) {
mins = v;
- if (v > maxs)
+ }
+ if ( v > maxs ) {
maxs = v;
+ }
}
#if 0
- if (maxs - mins <= 0)
- Error ("zero extents");
+ if ( maxs - mins <= 0 ) {
+ Error( "zero extents" );
+ }
#endif
- if (axis == 2)
- { // allow double high walls
- if (maxs - mins <= subdivide_size/* *2 */)
+ if ( axis == 2 ) { // allow double high walls
+ if ( maxs - mins <= subdivide_size /* *2 */ ) {
break;
+ }
}
- else if (maxs - mins <= subdivide_size)
+ else if ( maxs - mins <= subdivide_size ) {
break;
-
- // split it
+ }
+
+ // split it
c_subdivide++;
-
- v = VectorNormalize (temp, temp);
- dist = (mins + subdivide_size - 16)/v;
+ v = VectorNormalize( temp, temp );
- ClipWindingEpsilon (w, temp, dist, ON_EPSILON, &frontw, &backw);
- if (!frontw || !backw)
- Error ("SubdivideFace: didn't split the polygon");
+ dist = ( mins + subdivide_size - 16 ) / v;
- f->split[0] = NewFaceFromFace (f);
+ 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] = 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]);
+ SubdivideFace( node, f->split[0] );
+ SubdivideFace( node, f->split[1] );
return;
}
}
}
-void SubdivideNodeFaces (node_t *node)
-{
- face_t *f;
+void SubdivideNodeFaces( node_t *node ){
+ face_t *f;
- for (f = node->faces ; f ; f=f->next)
+ for ( f = node->faces ; f ; f = f->next )
{
- SubdivideFace (node, f);
+ SubdivideFace( node, f );
}
}
//===========================================================================
-int c_nodefaces;
+int c_nodefaces;
/*
-============
-FaceFromPortal
+ ============
+ FaceFromPortal
-============
-*/
-face_t *FaceFromPortal (portal_t *p, int pside)
-{
- face_t *f;
- side_t *side;
+ ============
+ */
+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
+ if ( !side ) {
+ return NULL; // portal does not bridge different visible contents
- f = AllocFace ();
+ }
+ f = AllocFace();
f->texinfo = side->texinfo;
- f->planenum = (side->planenum & ~1) | pside;
+ 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 ( ( 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);
+ }
+ if ( pside ) {
+ f->w = ReverseWinding( p->winding );
f->contents = p->nodes[1]->contents;
}
else
{
- f->w = CopyWinding(p->winding);
+ 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;
+ ===============
+ 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]);
+ 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);
+ if ( !nomerge ) {
+ MergeNodeFaces( node );
+ }
+ if ( !nosubdiv ) {
+ SubdivideNodeFaces( node );
+ }
return;
}
// solid leafs never have visible faces
- if (node->contents & CONTENTS_SOLID)
+ if ( node->contents & CONTENTS_SOLID ) {
return;
+ }
// see which portals are valid
- for (p=node->portals ; p ; p = p->next[s])
+ for ( p = node->portals ; p ; p = p->next[s] )
{
- s = (p->nodes[1] == node);
+ s = ( p->nodes[1] == node );
- p->face[s] = FaceFromPortal (p, s);
- if (p->face[s])
- {
+ 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");
+ ============
+ MakeFaces
+ ============
+ */
+void MakeFaces( node_t *node ){
+ Sys_FPrintf( SYS_VRB, "--- MakeFaces ---\n" );
c_merge = 0;
c_subdivide = 0;
c_nodefaces = 0;
- MakeFaces_r (node);
+ 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);
+ 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