2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
27 some faces will be removed before saving, but still form nodes:
29 the insides of sky volumes
30 meeting planes of different water current volumes
34 // undefine for dumb linear searches
37 #define INTEGRAL_EPSILON 0.01
38 #define POINT_EPSILON 0.5
39 #define OFF_EPSILON 0.5
52 #define MAX_SUPERVERTS 512
53 int superverts[MAX_SUPERVERTS];
56 face_t *edgefaces[MAX_MAP_EDGES][2];
57 int firstmodeledge = 1;
67 int edge_verts[MAX_MAP_VERTS];
70 float subdivide_size = 240;
73 face_t *NewFaceFromFace( face_t *f );
75 //===========================================================================
77 typedef struct hashvert_s
79 struct hashvert_s *next;
87 int vertexchain[MAX_MAP_VERTS]; // the next vertex in a hash chain
88 int hashverts[HASH_SIZE * HASH_SIZE]; // a vertex number, or 0 for no verts
90 face_t *edgefaces[MAX_MAP_EDGES][2];
92 //============================================================================
95 unsigned HashVec( vec3_t vec ){
98 x = ( 4096 + (int)( vec[0] + 0.5 ) ) >> 7;
99 y = ( 4096 + (int)( vec[1] + 0.5 ) ) >> 7;
101 if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE ) {
102 Error( "HashVec: point outside valid range" );
105 return y * HASH_SIZE + x;
116 int GetVertexnum( vec3_t in ){
125 for ( i = 0 ; i < 3 ; i++ )
127 if ( fabs( in[i] - Q_rint( in[i] ) ) < INTEGRAL_EPSILON ) {
128 vert[i] = Q_rint( in[i] );
137 for ( vnum = hashverts[h] ; vnum ; vnum = vertexchain[vnum] )
139 p = dvertexes[vnum].point;
140 if ( fabs( p[0] - vert[0] ) < POINT_EPSILON
141 && fabs( p[1] - vert[1] ) < POINT_EPSILON
142 && fabs( p[2] - vert[2] ) < POINT_EPSILON ) {
148 if ( numvertexes == MAX_MAP_VERTS ) {
149 Error( "numvertexes == MAX_MAP_VERTS" );
152 dvertexes[numvertexes].point[0] = vert[0];
153 dvertexes[numvertexes].point[1] = vert[1];
154 dvertexes[numvertexes].point[2] = vert[2];
156 vertexchain[numvertexes] = hashverts[h];
157 hashverts[h] = numvertexes;
163 return numvertexes - 1;
173 int GetVertexnum( vec3_t v ){
180 // make really close values exactly integral
181 for ( i = 0 ; i < 3 ; i++ )
183 if ( fabs( v[i] - (int)( v[i] + 0.5 ) ) < INTEGRAL_EPSILON ) {
184 v[i] = (int)( v[i] + 0.5 );
186 if ( v[i] < -4096 || v[i] > 4096 ) {
187 Error( "GetVertexnum: outside +/- 4096" );
191 // search for an existing vertex match
192 for ( i = 0, dv = dvertexes ; i < numvertexes ; i++, dv++ )
194 for ( j = 0 ; j < 3 ; j++ )
196 d = v[j] - dv->point[j];
197 if ( d > POINT_EPSILON || d < -POINT_EPSILON ) {
207 if ( numvertexes == MAX_MAP_VERTS ) {
208 Error( "MAX_MAP_VERTS" );
210 VectorCopy( v, dv->point );
214 return numvertexes - 1;
223 The faces vertexes have beeb added to the superverts[] array,
224 and there may be more there than can be held in a face (MAXEDGES).
226 If less, the faces vertexnums[] will be filled in, otherwise
227 face will reference a tree of split[] faces until all of the
228 vertexnums can be added.
230 superverts[base] will become face->vertexnums[0], and the others
231 will be circularly filled in.
234 void FaceFromSuperverts( node_t *node, face_t *f, int base ){
239 remaining = numsuperverts;
240 while ( remaining > MAXEDGES )
241 { // must split into two faces, because of vertex overload
244 newf = f->split[0] = NewFaceFromFace( f );
246 newf->next = node->faces;
249 newf->numpoints = MAXEDGES;
250 for ( i = 0 ; i < MAXEDGES ; i++ )
251 newf->vertexnums[i] = superverts[( i + base ) % numsuperverts];
253 f->split[1] = NewFaceFromFace( f );
255 f->next = node->faces;
258 remaining -= ( MAXEDGES - 2 );
259 base = ( base + MAXEDGES - 1 ) % numsuperverts;
262 // copy the vertexes back to the face
263 f->numpoints = remaining;
264 for ( i = 0 ; i < remaining ; i++ )
265 f->vertexnums[i] = superverts[( i + base ) % numsuperverts];
274 void EmitFaceVertexes( node_t *node, face_t *f ){
278 if ( f->merged || f->split[0] || f->split[1] ) {
283 for ( i = 0 ; i < w->numpoints ; i++ )
285 if ( noweld ) { // make every point unique
286 if ( numvertexes == MAX_MAP_VERTS ) {
287 Error( "MAX_MAP_VERTS" );
289 superverts[i] = numvertexes;
290 VectorCopy( w->p[i], dvertexes[numvertexes].point );
296 superverts[i] = GetVertexnum( w->p[i] );
299 numsuperverts = w->numpoints;
301 // this may fragment the face if > MAXEDGES
302 FaceFromSuperverts( node, f, 0 );
310 void EmitVertexes_r( node_t *node ){
314 if ( node->planenum == PLANENUM_LEAF ) {
318 for ( f = node->faces ; f ; f = f->next )
320 EmitFaceVertexes( node, f );
323 for ( i = 0 ; i < 2 ; i++ )
324 EmitVertexes_r( node->children[i] );
333 Uses the hash tables to cut down to a small number
336 void FindEdgeVerts( vec3_t v1, vec3_t v2 ){
337 int x1, x2, y1, y2, t;
344 num_edge_verts = numvertexes - 1;
345 for ( i = 0 ; i < numvertexes - 1 ; i++ )
346 edge_verts[i] = i + 1;
350 x1 = ( 4096 + (int)( v1[0] + 0.5 ) ) >> 7;
351 y1 = ( 4096 + (int)( v1[1] + 0.5 ) ) >> 7;
352 x2 = ( 4096 + (int)( v2[0] + 0.5 ) ) >> 7;
353 y2 = ( 4096 + (int)( v2[1] + 0.5 ) ) >> 7;
373 if ( x2 >= HASH_SIZE ) {
379 if ( y2 >= HASH_SIZE ) {
384 for ( x = x1 ; x <= x2 ; x++ )
386 for ( y = y1 ; y <= y2 ; y++ )
388 for ( vnum = hashverts[y * HASH_SIZE + x] ; vnum ; vnum = vertexchain[vnum] )
390 edge_verts[num_edge_verts++] = vnum;
401 Forced a dumb check of everything
404 void FindEdgeVerts( vec3_t v1, vec3_t v2 ){
407 num_edge_verts = numvertexes - 1;
408 for ( i = 0 ; i < num_edge_verts ; i++ )
409 edge_verts[i] = i + 1;
417 Can be recursively reentered
420 void TestEdge( vec_t start, vec_t end, int p1, int p2, int startvert ){
431 return; // degenerate edge
434 for ( k = startvert ; k < num_edge_verts ; k++ )
437 if ( j == p1 || j == p2 ) {
441 VectorCopy( dvertexes[j].point, p );
443 VectorSubtract( p, edge_start, delta );
444 dist = DotProduct( delta, edge_dir );
445 if ( dist <= start || dist >= end ) {
446 continue; // off an end
448 VectorMA( edge_start, dist, edge_dir, exact );
449 VectorSubtract( p, exact, off );
450 error = VectorLength( off );
452 if ( fabs( error ) > OFF_EPSILON ) {
453 continue; // not on the edge
458 TestEdge( start, dist, p1, j, k + 1 );
459 TestEdge( dist, end, j, p2, k + 1 );
463 // the edge p1 to p2 is now free of tjunctions
464 if ( numsuperverts >= MAX_SUPERVERTS ) {
465 Error( "MAX_SUPERVERTS" );
467 superverts[numsuperverts] = p1;
477 void FixFaceEdges( node_t *node, face_t *f ){
482 int count[MAX_SUPERVERTS], start[MAX_SUPERVERTS];
485 if ( f->merged || f->split[0] || f->split[1] ) {
491 for ( i = 0 ; i < f->numpoints ; i++ )
493 p1 = f->vertexnums[i];
494 p2 = f->vertexnums[( i + 1 ) % f->numpoints];
496 VectorCopy( dvertexes[p1].point, edge_start );
497 VectorCopy( dvertexes[p2].point, e2 );
499 FindEdgeVerts( edge_start, e2 );
501 VectorSubtract( e2, edge_start, edge_dir );
502 len = VectorNormalize( edge_dir, edge_dir );
504 start[i] = numsuperverts;
505 TestEdge( 0, len, p1, p2, 0 );
507 count[i] = numsuperverts - start[i];
510 if ( numsuperverts < 3 ) { // entire face collapsed
516 // we want to pick a vertex that doesn't have tjunctions
517 // on either side, which can cause artifacts on trifans,
518 // especially underwater
519 for ( i = 0 ; i < f->numpoints ; i++ )
521 if ( count[i] == 1 && count[( i + f->numpoints - 1 ) % f->numpoints] == 1 ) {
525 if ( i == f->numpoints ) {
526 f->badstartvert = true;
531 { // rotate the vertex order
535 // this may fragment the face if > MAXEDGES
536 FaceFromSuperverts( node, f, base );
544 void FixEdges_r( node_t *node ){
548 if ( node->planenum == PLANENUM_LEAF ) {
552 for ( f = node->faces ; f ; f = f->next )
553 FixFaceEdges( node, f );
555 for ( i = 0 ; i < 2 ; i++ )
556 FixEdges_r( node->children[i] );
565 void FixTjuncs( node_t *headnode ){
566 // snap and merge all vertexes
567 Sys_FPrintf( SYS_VRB, "---- snap verts ----\n" );
568 memset( hashverts, 0, sizeof( hashverts ) );
572 EmitVertexes_r( headnode );
573 Sys_FPrintf( SYS_VRB, "%i unique from %i\n", c_uniqueverts, c_totalverts );
575 // break edges on tjunctions
576 Sys_FPrintf( SYS_VRB, "---- tjunc ----\n" );
582 FixEdges_r( headnode );
584 Sys_FPrintf( SYS_VRB, "%5i edges degenerated\n", c_degenerate );
585 Sys_FPrintf( SYS_VRB, "%5i faces degenerated\n", c_facecollapse );
586 Sys_FPrintf( SYS_VRB, "%5i edges added by tjunctions\n", c_tjunctions );
587 Sys_FPrintf( SYS_VRB, "%5i faces added by tjunctions\n", c_faceoverflows );
588 Sys_FPrintf( SYS_VRB, "%5i bad start verts\n", c_badstartverts );
592 //========================================================
596 face_t *AllocFace( void ){
599 f = malloc( sizeof( *f ) );
600 memset( f, 0, sizeof( *f ) );
606 face_t *NewFaceFromFace( face_t *f ){
612 newf->split[0] = newf->split[1] = NULL;
617 void FreeFace( face_t *f ){
625 //========================================================
632 Don't allow four way edges
635 int GetEdge2( int v1, int v2, face_t *f ){
642 for ( i = firstmodeledge ; i < numedges ; i++ )
645 if ( v1 == edge->v[1] && v2 == edge->v[0]
646 && edgefaces[i][0]->contents == f->contents ) {
647 if ( edgefaces[i][1] ) {
648 // Sys_Printf ("WARNING: multiple backward edge\n");
655 if ( v1 == edge->v[0] && v2 == edge->v[1] ) {
656 Sys_FPrintf( SYS_WRN, "WARNING: multiple forward edge\n" );
664 if ( numedges >= MAX_MAP_EDGES ) {
665 Error( "numedges == MAX_MAP_EDGES" );
667 edge = &dedges[numedges];
671 edgefaces[numedges - 1][0] = f;
677 ===========================================================================
681 ===========================================================================
684 #define CONTINUOUS_EPSILON 0.001
690 If two polygons share a common edge and the edges that meet at the
691 common points are both inside the other polygons, merge them
693 Returns NULL if the faces couldn't be merged, or the new face.
694 The originals will NOT be freed.
697 winding_t *TryMergeWinding( winding_t *f1, winding_t *f2, vec3_t planenormal ){
698 vec_t *p1, *p2, *p3, *p4, *back;
701 vec3_t normal, delta;
703 qboolean keep1, keep2;
707 // find a common edge
709 p1 = p2 = NULL; // stop compiler warning
712 for ( i = 0 ; i < f1->numpoints ; i++ )
715 p2 = f1->p[( i + 1 ) % f1->numpoints];
716 for ( j = 0 ; j < f2->numpoints ; j++ )
719 p4 = f2->p[( j + 1 ) % f2->numpoints];
720 for ( k = 0 ; k < 3 ; k++ )
722 if ( fabs( p1[k] - p4[k] ) > EQUAL_EPSILON ) {
725 if ( fabs( p2[k] - p3[k] ) > EQUAL_EPSILON ) {
733 if ( j < f2->numpoints ) {
738 if ( i == f1->numpoints ) {
739 return NULL; // no matching edges
743 // check slope of connected lines
744 // if the slopes are colinear, the point can be removed
746 back = f1->p[( i + f1->numpoints - 1 ) % f1->numpoints];
747 VectorSubtract( p1, back, delta );
748 CrossProduct( planenormal, delta, normal );
749 VectorNormalize( normal, normal );
751 back = f2->p[( j + 2 ) % f2->numpoints];
752 VectorSubtract( back, p1, delta );
753 dot = DotProduct( delta, normal );
754 if ( dot > CONTINUOUS_EPSILON ) {
755 return NULL; // not a convex polygon
757 keep1 = (qboolean)( dot < -CONTINUOUS_EPSILON );
759 back = f1->p[( i + 2 ) % f1->numpoints];
760 VectorSubtract( back, p2, delta );
761 CrossProduct( planenormal, delta, normal );
762 VectorNormalize( normal, normal );
764 back = f2->p[( j + f2->numpoints - 1 ) % f2->numpoints];
765 VectorSubtract( back, p2, delta );
766 dot = DotProduct( delta, normal );
767 if ( dot > CONTINUOUS_EPSILON ) {
768 return NULL; // not a convex polygon
770 keep2 = (qboolean)( dot < -CONTINUOUS_EPSILON );
773 // build the new polygon
775 newf = AllocWinding( f1->numpoints + f2->numpoints );
777 // copy first polygon
778 for ( k = ( i + 1 ) % f1->numpoints ; k != i ; k = ( k + 1 ) % f1->numpoints )
780 if ( k == ( i + 1 ) % f1->numpoints && !keep2 ) {
784 VectorCopy( f1->p[k], newf->p[newf->numpoints] );
788 // copy second polygon
789 for ( l = ( j + 1 ) % f2->numpoints ; l != j ; l = ( l + 1 ) % f2->numpoints )
791 if ( l == ( j + 1 ) % f2->numpoints && !keep1 ) {
794 VectorCopy( f2->p[l], newf->p[newf->numpoints] );
805 If two polygons share a common edge and the edges that meet at the
806 common points are both inside the other polygons, merge them
808 Returns NULL if the faces couldn't be merged, or the new face.
809 The originals will NOT be freed.
812 face_t *TryMerge( face_t *f1, face_t *f2, vec3_t planenormal ){
816 if ( !f1->w || !f2->w ) {
819 if ( f1->texinfo != f2->texinfo ) {
822 if ( f1->planenum != f2->planenum ) { // on front and back sides
825 if ( f1->contents != f2->contents ) {
830 nw = TryMergeWinding( f1->w, f2->w, planenormal );
836 newf = NewFaceFromFace( f1 );
850 void MergeNodeFaces( node_t *node ){
851 face_t *f1, *f2, *end;
855 plane = &mapplanes[node->planenum];
858 for ( f1 = node->faces ; f1 ; f1 = f1->next )
860 if ( f1->merged || f1->split[0] || f1->split[1] ) {
863 for ( f2 = node->faces ; f2 != f1 ; f2 = f2->next )
865 if ( f2->merged || f2->split[0] || f2->split[1] ) {
868 merged = TryMerge( f1, f2, plane->normal );
873 // add merged to the end of the node face list
874 // so it will be checked against all the faces again
875 for ( end = node->faces ; end->next ; end = end->next )
884 //=====================================================================
890 Chop up faces that are larger than we want in the surface cache
893 void SubdivideFace( node_t *node, face_t *f ){
900 winding_t *w, *frontw, *backw;
906 // special (non-surface cached) faces don't need subdivision
907 tex = &texinfo[f->texinfo];
909 if ( tex->flags & ( SURF_WARP | SURF_SKY ) ) {
913 for ( axis = 0 ; axis < 2 ; axis++ )
920 VectorCopy( tex->vecs[axis], temp );
922 for ( i = 0 ; i < w->numpoints ; i++ )
924 v = DotProduct( w->p[i], temp );
933 if ( maxs - mins <= 0 ) {
934 Error( "zero extents" );
937 if ( axis == 2 ) { // allow double high walls
938 if ( maxs - mins <= subdivide_size /* *2 */ ) {
942 else if ( maxs - mins <= subdivide_size ) {
949 v = VectorNormalize( temp, temp );
951 dist = ( mins + subdivide_size - 16 ) / v;
953 ClipWindingEpsilon( w, temp, dist, ON_EPSILON, &frontw, &backw );
954 if ( !frontw || !backw ) {
955 Error( "SubdivideFace: didn't split the polygon" );
958 f->split[0] = NewFaceFromFace( f );
959 f->split[0]->w = frontw;
960 f->split[0]->next = node->faces;
961 node->faces = f->split[0];
963 f->split[1] = NewFaceFromFace( f );
964 f->split[1]->w = backw;
965 f->split[1]->next = node->faces;
966 node->faces = f->split[1];
968 SubdivideFace( node, f->split[0] );
969 SubdivideFace( node, f->split[1] );
975 void SubdivideNodeFaces( node_t *node ){
978 for ( f = node->faces ; f ; f = f->next )
980 SubdivideFace( node, f );
984 //===========================================================================
995 face_t *FaceFromPortal( portal_t *p, int pside ){
1001 return NULL; // portal does not bridge different visible contents
1006 f->texinfo = side->texinfo;
1007 f->planenum = ( side->planenum & ~1 ) | pside;
1010 if ( ( p->nodes[pside]->contents & CONTENTS_WINDOW )
1011 && VisibleContents( p->nodes[!pside]->contents ^ p->nodes[pside]->contents ) == CONTENTS_WINDOW ) {
1012 return NULL; // don't show insides of windows
1016 f->w = ReverseWinding( p->winding );
1017 f->contents = p->nodes[1]->contents;
1021 f->w = CopyWinding( p->winding );
1022 f->contents = p->nodes[0]->contents;
1032 If a portal will make a visible face,
1033 mark the side that originally created it
1035 solid / empty : solid
1036 solid / water : solid
1037 water / empty : water
1038 water / water : none
1041 void MakeFaces_r( node_t *node ){
1045 // recurse down to leafs
1046 if ( node->planenum != PLANENUM_LEAF ) {
1047 MakeFaces_r( node->children[0] );
1048 MakeFaces_r( node->children[1] );
1050 // merge together all visible faces on the node
1052 MergeNodeFaces( node );
1055 SubdivideNodeFaces( node );
1061 // solid leafs never have visible faces
1062 if ( node->contents & CONTENTS_SOLID ) {
1066 // see which portals are valid
1067 for ( p = node->portals ; p ; p = p->next[s] )
1069 s = ( p->nodes[1] == node );
1071 p->face[s] = FaceFromPortal( p, s );
1074 p->face[s]->next = p->onnode->faces;
1075 p->onnode->faces = p->face[s];
1085 void MakeFaces( node_t *node ){
1086 Sys_FPrintf( SYS_VRB, "--- MakeFaces ---\n" );
1091 MakeFaces_r( node );
1093 Sys_FPrintf( SYS_VRB, "%5i makefaces\n", c_nodefaces );
1094 Sys_FPrintf( SYS_VRB, "%5i merged\n", c_merge );
1095 Sys_FPrintf( SYS_VRB, "%5i subdivided\n", c_subdivide );