mirror of https://github.com/TTimo/GtkRadiant.git
1097 lines
22 KiB
C
1097 lines
22 KiB
C
/*
|
|
Copyright (C) 1999-2007 id Software, Inc. and contributors.
|
|
For a list of contributors, see the accompanying CONTRIBUTORS file.
|
|
|
|
This file is part of GtkRadiant.
|
|
|
|
GtkRadiant is free software; you can redistribute it and/or modify
|
|
it under the terms of the GNU General Public License as published by
|
|
the Free Software Foundation; either version 2 of the License, or
|
|
(at your option) any later version.
|
|
|
|
GtkRadiant is distributed in the hope that it will be useful,
|
|
but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
GNU General Public License for more details.
|
|
|
|
You should have received a copy of the GNU General Public License
|
|
along with GtkRadiant; if not, write to the Free Software
|
|
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
|
|
*/
|
|
// faces.c
|
|
|
|
#include "qbsp.h"
|
|
|
|
/*
|
|
|
|
some faces will be removed before saving, but still form nodes:
|
|
|
|
the insides of sky volumes
|
|
meeting planes of different water current volumes
|
|
|
|
*/
|
|
|
|
// undefine for dumb linear searches
|
|
#define USE_HASHING
|
|
|
|
#define INTEGRAL_EPSILON 0.01
|
|
#define POINT_EPSILON 0.5
|
|
#define OFF_EPSILON 0.5
|
|
|
|
int c_merge;
|
|
int c_subdivide;
|
|
|
|
int c_totalverts;
|
|
int c_uniqueverts;
|
|
int c_degenerate;
|
|
int c_tjunctions;
|
|
int c_faceoverflows;
|
|
int c_facecollapse;
|
|
int c_badstartverts;
|
|
|
|
#define MAX_SUPERVERTS 512
|
|
int superverts[MAX_SUPERVERTS];
|
|
int numsuperverts;
|
|
|
|
face_t *edgefaces[MAX_MAP_EDGES][2];
|
|
int firstmodeledge = 1;
|
|
int firstmodelface;
|
|
|
|
int c_tryedges;
|
|
|
|
vec3_t edge_dir;
|
|
vec3_t edge_start;
|
|
vec_t edge_len;
|
|
|
|
int num_edge_verts;
|
|
int edge_verts[MAX_MAP_VERTS];
|
|
|
|
|
|
float subdivide_size = 240;
|
|
|
|
|
|
face_t *NewFaceFromFace( face_t *f );
|
|
|
|
//===========================================================================
|
|
|
|
typedef struct hashvert_s
|
|
{
|
|
struct hashvert_s *next;
|
|
int num;
|
|
} hashvert_t;
|
|
|
|
|
|
#define HASH_SIZE 64
|
|
|
|
|
|
int vertexchain[MAX_MAP_VERTS]; // the next vertex in a hash chain
|
|
int hashverts[HASH_SIZE * HASH_SIZE]; // a vertex number, or 0 for no verts
|
|
|
|
face_t *edgefaces[MAX_MAP_EDGES][2];
|
|
|
|
//============================================================================
|
|
|
|
|
|
unsigned HashVec( vec3_t vec ){
|
|
int x, y;
|
|
|
|
x = ( 4096 + (int)( vec[0] + 0.5 ) ) >> 7;
|
|
y = ( 4096 + (int)( vec[1] + 0.5 ) ) >> 7;
|
|
|
|
if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE ) {
|
|
Error( "HashVec: point outside valid range" );
|
|
}
|
|
|
|
return y * HASH_SIZE + x;
|
|
}
|
|
|
|
#ifdef USE_HASHING
|
|
/*
|
|
=============
|
|
GetVertex
|
|
|
|
Uses hashing
|
|
=============
|
|
*/
|
|
int GetVertexnum( vec3_t in ){
|
|
int h;
|
|
int i;
|
|
float *p;
|
|
vec3_t vert;
|
|
int vnum;
|
|
|
|
c_totalverts++;
|
|
|
|
for ( i = 0 ; i < 3 ; i++ )
|
|
{
|
|
if ( fabs( in[i] - Q_rint( in[i] ) ) < INTEGRAL_EPSILON ) {
|
|
vert[i] = Q_rint( in[i] );
|
|
}
|
|
else{
|
|
vert[i] = in[i];
|
|
}
|
|
}
|
|
|
|
h = HashVec( vert );
|
|
|
|
for ( vnum = hashverts[h] ; vnum ; vnum = vertexchain[vnum] )
|
|
{
|
|
p = dvertexes[vnum].point;
|
|
if ( fabs( p[0] - vert[0] ) < POINT_EPSILON
|
|
&& fabs( p[1] - vert[1] ) < POINT_EPSILON
|
|
&& fabs( p[2] - vert[2] ) < POINT_EPSILON ) {
|
|
return vnum;
|
|
}
|
|
}
|
|
|
|
// emit a vertex
|
|
if ( numvertexes == MAX_MAP_VERTS ) {
|
|
Error( "numvertexes == MAX_MAP_VERTS" );
|
|
}
|
|
|
|
dvertexes[numvertexes].point[0] = vert[0];
|
|
dvertexes[numvertexes].point[1] = vert[1];
|
|
dvertexes[numvertexes].point[2] = vert[2];
|
|
|
|
vertexchain[numvertexes] = hashverts[h];
|
|
hashverts[h] = numvertexes;
|
|
|
|
c_uniqueverts++;
|
|
|
|
numvertexes++;
|
|
|
|
return numvertexes - 1;
|
|
}
|
|
#else
|
|
/*
|
|
==================
|
|
GetVertexnum
|
|
|
|
Dumb linear search
|
|
==================
|
|
*/
|
|
int GetVertexnum( vec3_t v ){
|
|
int i, j;
|
|
dvertex_t *dv;
|
|
vec_t d;
|
|
|
|
c_totalverts++;
|
|
|
|
// make really close values exactly integral
|
|
for ( i = 0 ; i < 3 ; i++ )
|
|
{
|
|
if ( fabs( v[i] - (int)( v[i] + 0.5 ) ) < INTEGRAL_EPSILON ) {
|
|
v[i] = (int)( v[i] + 0.5 );
|
|
}
|
|
if ( v[i] < -4096 || v[i] > 4096 ) {
|
|
Error( "GetVertexnum: outside +/- 4096" );
|
|
}
|
|
}
|
|
|
|
// search for an existing vertex match
|
|
for ( i = 0, dv = dvertexes ; i < numvertexes ; i++, dv++ )
|
|
{
|
|
for ( j = 0 ; j < 3 ; j++ )
|
|
{
|
|
d = v[j] - dv->point[j];
|
|
if ( d > POINT_EPSILON || d < -POINT_EPSILON ) {
|
|
break;
|
|
}
|
|
}
|
|
if ( j == 3 ) {
|
|
return i; // a match
|
|
}
|
|
}
|
|
|
|
// new point
|
|
if ( numvertexes == MAX_MAP_VERTS ) {
|
|
Error( "MAX_MAP_VERTS" );
|
|
}
|
|
VectorCopy( v, dv->point );
|
|
numvertexes++;
|
|
c_uniqueverts++;
|
|
|
|
return numvertexes - 1;
|
|
}
|
|
#endif
|
|
|
|
|
|
/*
|
|
==================
|
|
FaceFromSuperverts
|
|
|
|
The faces vertexes have beeb added to the superverts[] array,
|
|
and there may be more there than can be held in a face (MAXEDGES).
|
|
|
|
If less, the faces vertexnums[] will be filled in, otherwise
|
|
face will reference a tree of split[] faces until all of the
|
|
vertexnums can be added.
|
|
|
|
superverts[base] will become face->vertexnums[0], and the others
|
|
will be circularly filled in.
|
|
==================
|
|
*/
|
|
void FaceFromSuperverts( node_t *node, face_t *f, int base ){
|
|
face_t *newf;
|
|
int remaining;
|
|
int i;
|
|
|
|
remaining = numsuperverts;
|
|
while ( remaining > MAXEDGES )
|
|
{ // must split into two faces, because of vertex overload
|
|
c_faceoverflows++;
|
|
|
|
newf = f->split[0] = NewFaceFromFace( f );
|
|
newf = f->split[0];
|
|
newf->next = node->faces;
|
|
node->faces = newf;
|
|
|
|
newf->numpoints = MAXEDGES;
|
|
for ( i = 0 ; i < MAXEDGES ; i++ )
|
|
newf->vertexnums[i] = superverts[( i + base ) % numsuperverts];
|
|
|
|
f->split[1] = NewFaceFromFace( f );
|
|
f = f->split[1];
|
|
f->next = node->faces;
|
|
node->faces = f;
|
|
|
|
remaining -= ( MAXEDGES - 2 );
|
|
base = ( base + MAXEDGES - 1 ) % numsuperverts;
|
|
}
|
|
|
|
// copy the vertexes back to the face
|
|
f->numpoints = remaining;
|
|
for ( i = 0 ; i < remaining ; i++ )
|
|
f->vertexnums[i] = superverts[( i + base ) % numsuperverts];
|
|
}
|
|
|
|
|
|
/*
|
|
==================
|
|
EmitFaceVertexes
|
|
==================
|
|
*/
|
|
void EmitFaceVertexes( node_t *node, face_t *f ){
|
|
winding_t *w;
|
|
int i;
|
|
|
|
if ( f->merged || f->split[0] || f->split[1] ) {
|
|
return;
|
|
}
|
|
|
|
w = f->w;
|
|
for ( i = 0 ; i < w->numpoints ; i++ )
|
|
{
|
|
if ( noweld ) { // make every point unique
|
|
if ( numvertexes == MAX_MAP_VERTS ) {
|
|
Error( "MAX_MAP_VERTS" );
|
|
}
|
|
superverts[i] = numvertexes;
|
|
VectorCopy( w->p[i], dvertexes[numvertexes].point );
|
|
numvertexes++;
|
|
c_uniqueverts++;
|
|
c_totalverts++;
|
|
}
|
|
else{
|
|
superverts[i] = GetVertexnum( w->p[i] );
|
|
}
|
|
}
|
|
numsuperverts = w->numpoints;
|
|
|
|
// this may fragment the face if > MAXEDGES
|
|
FaceFromSuperverts( node, f, 0 );
|
|
}
|
|
|
|
/*
|
|
==================
|
|
EmitVertexes_r
|
|
==================
|
|
*/
|
|
void EmitVertexes_r( node_t *node ){
|
|
int i;
|
|
face_t *f;
|
|
|
|
if ( node->planenum == PLANENUM_LEAF ) {
|
|
return;
|
|
}
|
|
|
|
for ( f = node->faces ; f ; f = f->next )
|
|
{
|
|
EmitFaceVertexes( node, f );
|
|
}
|
|
|
|
for ( i = 0 ; i < 2 ; i++ )
|
|
EmitVertexes_r( node->children[i] );
|
|
}
|
|
|
|
|
|
#ifdef USE_HASHING
|
|
/*
|
|
==========
|
|
FindEdgeVerts
|
|
|
|
Uses the hash tables to cut down to a small number
|
|
==========
|
|
*/
|
|
void FindEdgeVerts( vec3_t v1, vec3_t v2 ){
|
|
int x1, x2, y1, y2, t;
|
|
int x, y;
|
|
int vnum;
|
|
|
|
#if 0
|
|
{
|
|
int i;
|
|
num_edge_verts = numvertexes - 1;
|
|
for ( i = 0 ; i < numvertexes - 1 ; i++ )
|
|
edge_verts[i] = i + 1;
|
|
}
|
|
#endif
|
|
|
|
x1 = ( 4096 + (int)( v1[0] + 0.5 ) ) >> 7;
|
|
y1 = ( 4096 + (int)( v1[1] + 0.5 ) ) >> 7;
|
|
x2 = ( 4096 + (int)( v2[0] + 0.5 ) ) >> 7;
|
|
y2 = ( 4096 + (int)( v2[1] + 0.5 ) ) >> 7;
|
|
|
|
if ( x1 > x2 ) {
|
|
t = x1;
|
|
x1 = x2;
|
|
x2 = t;
|
|
}
|
|
if ( y1 > y2 ) {
|
|
t = y1;
|
|
y1 = y2;
|
|
y2 = t;
|
|
}
|
|
#if 0
|
|
x1--;
|
|
x2++;
|
|
y1--;
|
|
y2++;
|
|
if ( x1 < 0 ) {
|
|
x1 = 0;
|
|
}
|
|
if ( x2 >= HASH_SIZE ) {
|
|
x2 = HASH_SIZE;
|
|
}
|
|
if ( y1 < 0 ) {
|
|
y1 = 0;
|
|
}
|
|
if ( y2 >= HASH_SIZE ) {
|
|
y2 = HASH_SIZE;
|
|
}
|
|
#endif
|
|
num_edge_verts = 0;
|
|
for ( x = x1 ; x <= x2 ; x++ )
|
|
{
|
|
for ( y = y1 ; y <= y2 ; y++ )
|
|
{
|
|
for ( vnum = hashverts[y * HASH_SIZE + x] ; vnum ; vnum = vertexchain[vnum] )
|
|
{
|
|
edge_verts[num_edge_verts++] = vnum;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
#else
|
|
/*
|
|
==========
|
|
FindEdgeVerts
|
|
|
|
Forced a dumb check of everything
|
|
==========
|
|
*/
|
|
void FindEdgeVerts( vec3_t v1, vec3_t v2 ){
|
|
int i;
|
|
|
|
num_edge_verts = numvertexes - 1;
|
|
for ( i = 0 ; i < num_edge_verts ; i++ )
|
|
edge_verts[i] = i + 1;
|
|
}
|
|
#endif
|
|
|
|
/*
|
|
==========
|
|
TestEdge
|
|
|
|
Can be recursively reentered
|
|
==========
|
|
*/
|
|
void TestEdge( vec_t start, vec_t end, int p1, int p2, int startvert ){
|
|
int j, k;
|
|
vec_t dist;
|
|
vec3_t delta;
|
|
vec3_t exact;
|
|
vec3_t off;
|
|
vec_t error;
|
|
vec3_t p;
|
|
|
|
if ( p1 == p2 ) {
|
|
c_degenerate++;
|
|
return; // degenerate edge
|
|
}
|
|
|
|
for ( k = startvert ; k < num_edge_verts ; k++ )
|
|
{
|
|
j = edge_verts[k];
|
|
if ( j == p1 || j == p2 ) {
|
|
continue;
|
|
}
|
|
|
|
VectorCopy( dvertexes[j].point, p );
|
|
|
|
VectorSubtract( p, edge_start, delta );
|
|
dist = DotProduct( delta, edge_dir );
|
|
if ( dist <= start || dist >= end ) {
|
|
continue; // off an end
|
|
}
|
|
VectorMA( edge_start, dist, edge_dir, exact );
|
|
VectorSubtract( p, exact, off );
|
|
error = VectorLength( off );
|
|
|
|
if ( fabs( error ) > OFF_EPSILON ) {
|
|
continue; // not on the edge
|
|
|
|
}
|
|
// break the edge
|
|
c_tjunctions++;
|
|
TestEdge( start, dist, p1, j, k + 1 );
|
|
TestEdge( dist, end, j, p2, k + 1 );
|
|
return;
|
|
}
|
|
|
|
// the edge p1 to p2 is now free of tjunctions
|
|
if ( numsuperverts >= MAX_SUPERVERTS ) {
|
|
Error( "MAX_SUPERVERTS" );
|
|
}
|
|
superverts[numsuperverts] = p1;
|
|
numsuperverts++;
|
|
}
|
|
|
|
/*
|
|
==================
|
|
FixFaceEdges
|
|
|
|
==================
|
|
*/
|
|
void FixFaceEdges( node_t *node, face_t *f ){
|
|
int p1, p2;
|
|
int i;
|
|
vec3_t e2;
|
|
vec_t len;
|
|
int count[MAX_SUPERVERTS], start[MAX_SUPERVERTS];
|
|
int base;
|
|
|
|
if ( f->merged || f->split[0] || f->split[1] ) {
|
|
return;
|
|
}
|
|
|
|
numsuperverts = 0;
|
|
|
|
for ( i = 0 ; i < f->numpoints ; i++ )
|
|
{
|
|
p1 = f->vertexnums[i];
|
|
p2 = f->vertexnums[( i + 1 ) % f->numpoints];
|
|
|
|
VectorCopy( dvertexes[p1].point, edge_start );
|
|
VectorCopy( dvertexes[p2].point, e2 );
|
|
|
|
FindEdgeVerts( edge_start, e2 );
|
|
|
|
VectorSubtract( e2, edge_start, edge_dir );
|
|
len = VectorNormalize( edge_dir, edge_dir );
|
|
|
|
start[i] = numsuperverts;
|
|
TestEdge( 0, len, p1, p2, 0 );
|
|
|
|
count[i] = numsuperverts - start[i];
|
|
}
|
|
|
|
if ( numsuperverts < 3 ) { // entire face collapsed
|
|
f->numpoints = 0;
|
|
c_facecollapse++;
|
|
return;
|
|
}
|
|
|
|
// we want to pick a vertex that doesn't have tjunctions
|
|
// on either side, which can cause artifacts on trifans,
|
|
// especially underwater
|
|
for ( i = 0 ; i < f->numpoints ; i++ )
|
|
{
|
|
if ( count[i] == 1 && count[( i + f->numpoints - 1 ) % f->numpoints] == 1 ) {
|
|
break;
|
|
}
|
|
}
|
|
if ( i == f->numpoints ) {
|
|
f->badstartvert = true;
|
|
c_badstartverts++;
|
|
base = 0;
|
|
}
|
|
else
|
|
{ // rotate the vertex order
|
|
base = start[i];
|
|
}
|
|
|
|
// this may fragment the face if > MAXEDGES
|
|
FaceFromSuperverts( node, f, base );
|
|
}
|
|
|
|
/*
|
|
==================
|
|
FixEdges_r
|
|
==================
|
|
*/
|
|
void FixEdges_r( node_t *node ){
|
|
int i;
|
|
face_t *f;
|
|
|
|
if ( node->planenum == PLANENUM_LEAF ) {
|
|
return;
|
|
}
|
|
|
|
for ( f = node->faces ; f ; f = f->next )
|
|
FixFaceEdges( node, f );
|
|
|
|
for ( i = 0 ; i < 2 ; i++ )
|
|
FixEdges_r( node->children[i] );
|
|
}
|
|
|
|
/*
|
|
===========
|
|
FixTjuncs
|
|
|
|
===========
|
|
*/
|
|
void FixTjuncs( node_t *headnode ){
|
|
// snap and merge all vertexes
|
|
Sys_FPrintf( SYS_VRB, "---- snap verts ----\n" );
|
|
memset( hashverts, 0, sizeof( hashverts ) );
|
|
c_totalverts = 0;
|
|
c_uniqueverts = 0;
|
|
c_faceoverflows = 0;
|
|
EmitVertexes_r( headnode );
|
|
Sys_FPrintf( SYS_VRB, "%i unique from %i\n", c_uniqueverts, c_totalverts );
|
|
|
|
// break edges on tjunctions
|
|
Sys_FPrintf( SYS_VRB, "---- tjunc ----\n" );
|
|
c_tryedges = 0;
|
|
c_degenerate = 0;
|
|
c_facecollapse = 0;
|
|
c_tjunctions = 0;
|
|
if ( !notjunc ) {
|
|
FixEdges_r( headnode );
|
|
}
|
|
Sys_FPrintf( SYS_VRB, "%5i edges degenerated\n", c_degenerate );
|
|
Sys_FPrintf( SYS_VRB, "%5i faces degenerated\n", c_facecollapse );
|
|
Sys_FPrintf( SYS_VRB, "%5i edges added by tjunctions\n", c_tjunctions );
|
|
Sys_FPrintf( SYS_VRB, "%5i faces added by tjunctions\n", c_faceoverflows );
|
|
Sys_FPrintf( SYS_VRB, "%5i bad start verts\n", c_badstartverts );
|
|
}
|
|
|
|
|
|
//========================================================
|
|
|
|
int c_faces;
|
|
|
|
face_t *AllocFace( void ){
|
|
face_t *f;
|
|
|
|
f = malloc( sizeof( *f ) );
|
|
memset( f, 0, sizeof( *f ) );
|
|
c_faces++;
|
|
|
|
return f;
|
|
}
|
|
|
|
face_t *NewFaceFromFace( face_t *f ){
|
|
face_t *newf;
|
|
|
|
newf = AllocFace();
|
|
*newf = *f;
|
|
newf->merged = NULL;
|
|
newf->split[0] = newf->split[1] = NULL;
|
|
newf->w = NULL;
|
|
return newf;
|
|
}
|
|
|
|
void FreeFace( face_t *f ){
|
|
if ( f->w ) {
|
|
FreeWinding( f->w );
|
|
}
|
|
free( f );
|
|
c_faces--;
|
|
}
|
|
|
|
//========================================================
|
|
|
|
/*
|
|
==================
|
|
GetEdge
|
|
|
|
Called by writebsp.
|
|
Don't allow four way edges
|
|
==================
|
|
*/
|
|
int GetEdge2( int v1, int v2, face_t *f ){
|
|
dedge_t *edge;
|
|
int i;
|
|
|
|
c_tryedges++;
|
|
|
|
if ( !noshare ) {
|
|
for ( i = firstmodeledge ; i < numedges ; i++ )
|
|
{
|
|
edge = &dedges[i];
|
|
if ( v1 == edge->v[1] && v2 == edge->v[0]
|
|
&& edgefaces[i][0]->contents == f->contents ) {
|
|
if ( edgefaces[i][1] ) {
|
|
// Sys_Printf ("WARNING: multiple backward edge\n");
|
|
continue;
|
|
}
|
|
edgefaces[i][1] = f;
|
|
return -i;
|
|
}
|
|
#if 0
|
|
if ( v1 == edge->v[0] && v2 == edge->v[1] ) {
|
|
Sys_FPrintf( SYS_WRN, "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 );
|
|
}
|