tools/quake2/q2map/faces.c

   1 /*
   2    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3    For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5    This file is part of GtkRadiant.
   6
   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.
  11
  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.
  16
  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
  20  */
  21 // faces.c
  22
  23 #include "qbsp.h"
  24
  25 /*
  26
  27    some faces will be removed before saving, but still form nodes:
  28
  29    the insides of sky volumes
  30    meeting planes of different water current volumes
  31
  32  */
  33
  34 // undefine for dumb linear searches
  35 #define USE_HASHING
  36
  37 #define INTEGRAL_EPSILON    0.01
  38 #define POINT_EPSILON       0.5
  39 #define OFF_EPSILON         0.5
  40
  41 int c_merge;
  42 int c_subdivide;
  43
  44 int c_totalverts;
  45 int c_uniqueverts;
  46 int c_degenerate;
  47 int c_tjunctions;
  48 int c_faceoverflows;
  49 int c_facecollapse;
  50 int c_badstartverts;
  51
  52 #define MAX_SUPERVERTS  512
  53 int superverts[MAX_SUPERVERTS];
  54 int numsuperverts;
  55
  56 face_t      *edgefaces[MAX_MAP_EDGES][2];
  57 int firstmodeledge = 1;
  58 int firstmodelface;
  59
  60 int c_tryedges;
  61
  62 vec3_t edge_dir;
  63 vec3_t edge_start;
  64 vec_t edge_len;
  65
  66 int num_edge_verts;
  67 int edge_verts[MAX_MAP_VERTS];
  68
  69
  70 float subdivide_size = 240;
  71
  72
  73 face_t *NewFaceFromFace( face_t *f );
  74
  75 //===========================================================================
  76
  77 typedef struct hashvert_s
  78 {
  79         struct hashvert_s   *next;
  80         int num;
  81 } hashvert_t;
  82
  83
  84 #define HASH_SIZE   64
  85
  86
  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
  89
  90 face_t      *edgefaces[MAX_MAP_EDGES][2];
  91
  92 //============================================================================
  93
  94
  95 unsigned HashVec( vec3_t vec ){
  96         int x, y;
  97
  98         x = ( 4096 + (int)( vec[0] + 0.5 ) ) >> 7;
  99         y = ( 4096 + (int)( vec[1] + 0.5 ) ) >> 7;
 100
 101         if ( x < 0 || x >= HASH_SIZE || y < 0 || y >= HASH_SIZE ) {
 102                 Error( "HashVec: point outside valid range" );
 103         }
 104
 105         return y * HASH_SIZE + x;
 106 }
 107
 108 #ifdef USE_HASHING
 109 /*
 110    =============
 111    GetVertex
 112
 113    Uses hashing
 114    =============
 115  */
 116 int GetVertexnum( vec3_t in ){
 117         int h;
 118         int i;
 119         float       *p;
 120         vec3_t vert;
 121         int vnum;
 122
 123         c_totalverts++;
 124
 125         for ( i = 0 ; i < 3 ; i++ )
 126         {
 127                 if ( fabs( in[i] - Q_rint( in[i] ) ) < INTEGRAL_EPSILON ) {
 128                         vert[i] = Q_rint( in[i] );
 129                 }
 130                 else{
 131                         vert[i] = in[i];
 132                 }
 133         }
 134
 135         h = HashVec( vert );
 136
 137         for ( vnum = hashverts[h] ; vnum ; vnum = vertexchain[vnum] )
 138         {
 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 ) {
 143                         return vnum;
 144                 }
 145         }
 146
 147 // emit a vertex
 148         if ( numvertexes == MAX_MAP_VERTS ) {
 149                 Error( "numvertexes == MAX_MAP_VERTS" );
 150         }
 151
 152         dvertexes[numvertexes].point[0] = vert[0];
 153         dvertexes[numvertexes].point[1] = vert[1];
 154         dvertexes[numvertexes].point[2] = vert[2];
 155
 156         vertexchain[numvertexes] = hashverts[h];
 157         hashverts[h] = numvertexes;
 158
 159         c_uniqueverts++;
 160
 161         numvertexes++;
 162
 163         return numvertexes - 1;
 164 }
 165 #else
 166 /*
 167    ==================
 168    GetVertexnum
 169
 170    Dumb linear search
 171    ==================
 172  */
 173 int GetVertexnum( vec3_t v ){
 174         int i, j;
 175         dvertex_t   *dv;
 176         vec_t d;
 177
 178         c_totalverts++;
 179
 180         // make really close values exactly integral
 181         for ( i = 0 ; i < 3 ; i++ )
 182         {
 183                 if ( fabs( v[i] - (int)( v[i] + 0.5 ) ) < INTEGRAL_EPSILON ) {
 184                         v[i] = (int)( v[i] + 0.5 );
 185                 }
 186                 if ( v[i] < -4096 || v[i] > 4096 ) {
 187                         Error( "GetVertexnum: outside +/- 4096" );
 188                 }
 189         }
 190
 191         // search for an existing vertex match
 192         for ( i = 0, dv = dvertexes ; i < numvertexes ; i++, dv++ )
 193         {
 194                 for ( j = 0 ; j < 3 ; j++ )
 195                 {
 196                         d = v[j] - dv->point[j];
 197                         if ( d > POINT_EPSILON || d < -POINT_EPSILON ) {
 198                                 break;
 199                         }
 200                 }
 201                 if ( j == 3 ) {
 202                         return i;       // a match
 203                 }
 204         }
 205
 206         // new point
 207         if ( numvertexes == MAX_MAP_VERTS ) {
 208                 Error( "MAX_MAP_VERTS" );
 209         }
 210         VectorCopy( v, dv->point );
 211         numvertexes++;
 212         c_uniqueverts++;
 213
 214         return numvertexes - 1;
 215 }
 216 #endif
 217
 218
 219 /*
 220    ==================
 221    FaceFromSuperverts
 222
 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).
 225
 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.
 229
 230    superverts[base] will become face->vertexnums[0], and the others
 231    will be circularly filled in.
 232    ==================
 233  */
 234 void FaceFromSuperverts( node_t *node, face_t *f, int base ){
 235         face_t  *newf;
 236         int remaining;
 237         int i;
 238
 239         remaining = numsuperverts;
 240         while ( remaining > MAXEDGES )
 241         {   // must split into two faces, because of vertex overload
 242                 c_faceoverflows++;
 243
 244                 newf = f->split[0] = NewFaceFromFace( f );
 245                 newf = f->split[0];
 246                 newf->next = node->faces;
 247                 node->faces = newf;
 248
 249                 newf->numpoints = MAXEDGES;
 250                 for ( i = 0 ; i < MAXEDGES ; i++ )
 251                         newf->vertexnums[i] = superverts[( i + base ) % numsuperverts];
 252
 253                 f->split[1] = NewFaceFromFace( f );
 254                 f = f->split[1];
 255                 f->next = node->faces;
 256                 node->faces = f;
 257
 258                 remaining -= ( MAXEDGES - 2 );
 259                 base = ( base + MAXEDGES - 1 ) % numsuperverts;
 260         }
 261
 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];
 266 }
 267
 268
 269 /*
 270    ==================
 271    EmitFaceVertexes
 272    ==================
 273  */
 274 void EmitFaceVertexes( node_t *node, face_t *f ){
 275         winding_t   *w;
 276         int i;
 277
 278         if ( f->merged || f->split[0] || f->split[1] ) {
 279                 return;
 280         }
 281
 282         w = f->w;
 283         for ( i = 0 ; i < w->numpoints ; i++ )
 284         {
 285                 if ( noweld ) { // make every point unique
 286                         if ( numvertexes == MAX_MAP_VERTS ) {
 287                                 Error( "MAX_MAP_VERTS" );
 288                         }
 289                         superverts[i] = numvertexes;
 290                         VectorCopy( w->p[i], dvertexes[numvertexes].point );
 291                         numvertexes++;
 292                         c_uniqueverts++;
 293                         c_totalverts++;
 294                 }
 295                 else{
 296                         superverts[i] = GetVertexnum( w->p[i] );
 297                 }
 298         }
 299         numsuperverts = w->numpoints;
 300
 301         // this may fragment the face if > MAXEDGES
 302         FaceFromSuperverts( node, f, 0 );
 303 }
 304
 305 /*
 306    ==================
 307    EmitVertexes_r
 308    ==================
 309  */
 310 void EmitVertexes_r( node_t *node ){
 311         int i;
 312         face_t  *f;
 313
 314         if ( node->planenum == PLANENUM_LEAF ) {
 315                 return;
 316         }
 317
 318         for ( f = node->faces ; f ; f = f->next )
 319         {
 320                 EmitFaceVertexes( node, f );
 321         }
 322
 323         for ( i = 0 ; i < 2 ; i++ )
 324                 EmitVertexes_r( node->children[i] );
 325 }
 326
 327
 328 #ifdef USE_HASHING
 329 /*
 330    ==========
 331    FindEdgeVerts
 332
 333    Uses the hash tables to cut down to a small number
 334    ==========
 335  */
 336 void FindEdgeVerts( vec3_t v1, vec3_t v2 ){
 337         int x1, x2, y1, y2, t;
 338         int x, y;
 339         int vnum;
 340
 341 #if 0
 342         {
 343                 int i;
 344                 num_edge_verts = numvertexes - 1;
 345                 for ( i = 0 ; i < numvertexes - 1 ; i++ )
 346                         edge_verts[i] = i + 1;
 347         }
 348 #endif
 349
 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;
 354
 355         if ( x1 > x2 ) {
 356                 t = x1;
 357                 x1 = x2;
 358                 x2 = t;
 359         }
 360         if ( y1 > y2 ) {
 361                 t = y1;
 362                 y1 = y2;
 363                 y2 = t;
 364         }
 365 #if 0
 366         x1--;
 367         x2++;
 368         y1--;
 369         y2++;
 370         if ( x1 < 0 ) {
 371                 x1 = 0;
 372         }
 373         if ( x2 >= HASH_SIZE ) {
 374                 x2 = HASH_SIZE;
 375         }
 376         if ( y1 < 0 ) {
 377                 y1 = 0;
 378         }
 379         if ( y2 >= HASH_SIZE ) {
 380                 y2 = HASH_SIZE;
 381         }
 382 #endif
 383         num_edge_verts = 0;
 384         for ( x = x1 ; x <= x2 ; x++ )
 385         {
 386                 for ( y = y1 ; y <= y2 ; y++ )
 387                 {
 388                         for ( vnum = hashverts[y * HASH_SIZE + x] ; vnum ; vnum = vertexchain[vnum] )
 389                         {
 390                                 edge_verts[num_edge_verts++] = vnum;
 391                         }
 392                 }
 393         }
 394 }
 395
 396 #else
 397 /*
 398    ==========
 399    FindEdgeVerts
 400
 401    Forced a dumb check of everything
 402    ==========
 403  */
 404 void FindEdgeVerts( vec3_t v1, vec3_t v2 ){
 405         int i;
 406
 407         num_edge_verts = numvertexes - 1;
 408         for ( i = 0 ; i < num_edge_verts ; i++ )
 409                 edge_verts[i] = i + 1;
 410 }
 411 #endif
 412
 413 /*
 414    ==========
 415    TestEdge
 416
 417    Can be recursively reentered
 418    ==========
 419  */
 420 void TestEdge( vec_t start, vec_t end, int p1, int p2, int startvert ){
 421         int j, k;
 422         vec_t dist;
 423         vec3_t delta;
 424         vec3_t exact;
 425         vec3_t off;
 426         vec_t error;
 427         vec3_t p;
 428
 429         if ( p1 == p2 ) {
 430                 c_degenerate++;
 431                 return;     // degenerate edge
 432         }
 433
 434         for ( k = startvert ; k < num_edge_verts ; k++ )
 435         {
 436                 j = edge_verts[k];
 437                 if ( j == p1 || j == p2 ) {
 438                         continue;
 439                 }
 440
 441                 VectorCopy( dvertexes[j].point, p );
 442
 443                 VectorSubtract( p, edge_start, delta );
 444                 dist = DotProduct( delta, edge_dir );
 445                 if ( dist <= start || dist >= end ) {
 446                         continue;       // off an end
 447                 }
 448                 VectorMA( edge_start, dist, edge_dir, exact );
 449                 VectorSubtract( p, exact, off );
 450                 error = VectorLength( off );
 451
 452                 if ( fabs( error ) > OFF_EPSILON ) {
 453                         continue;       // not on the edge
 454
 455                 }
 456                 // break the edge
 457                 c_tjunctions++;
 458                 TestEdge( start, dist, p1, j, k + 1 );
 459                 TestEdge( dist, end, j, p2, k + 1 );
 460                 return;
 461         }
 462
 463         // the edge p1 to p2 is now free of tjunctions
 464         if ( numsuperverts >= MAX_SUPERVERTS ) {
 465                 Error( "MAX_SUPERVERTS" );
 466         }
 467         superverts[numsuperverts] = p1;
 468         numsuperverts++;
 469 }
 470
 471 /*
 472    ==================
 473    FixFaceEdges
 474
 475    ==================
 476  */
 477 void FixFaceEdges( node_t *node, face_t *f ){
 478         int p1, p2;
 479         int i;
 480         vec3_t e2;
 481         vec_t len;
 482         int count[MAX_SUPERVERTS], start[MAX_SUPERVERTS];
 483         int base;
 484
 485         if ( f->merged || f->split[0] || f->split[1] ) {
 486                 return;
 487         }
 488
 489         numsuperverts = 0;
 490
 491         for ( i = 0 ; i < f->numpoints ; i++ )
 492         {
 493                 p1 = f->vertexnums[i];
 494                 p2 = f->vertexnums[( i + 1 ) % f->numpoints];
 495
 496                 VectorCopy( dvertexes[p1].point, edge_start );
 497                 VectorCopy( dvertexes[p2].point, e2 );
 498
 499                 FindEdgeVerts( edge_start, e2 );
 500
 501                 VectorSubtract( e2, edge_start, edge_dir );
 502                 len = VectorNormalize( edge_dir, edge_dir );
 503
 504                 start[i] = numsuperverts;
 505                 TestEdge( 0, len, p1, p2, 0 );
 506
 507                 count[i] = numsuperverts - start[i];
 508         }
 509
 510         if ( numsuperverts < 3 ) { // entire face collapsed
 511                 f->numpoints = 0;
 512                 c_facecollapse++;
 513                 return;
 514         }
 515
 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++ )
 520         {
 521                 if ( count[i] == 1 && count[( i + f->numpoints - 1 ) % f->numpoints] == 1 ) {
 522                         break;
 523                 }
 524         }
 525         if ( i == f->numpoints ) {
 526                 f->badstartvert = true;
 527                 c_badstartverts++;
 528                 base = 0;
 529         }
 530         else
 531         {   // rotate the vertex order
 532                 base = start[i];
 533         }
 534
 535         // this may fragment the face if > MAXEDGES
 536         FaceFromSuperverts( node, f, base );
 537 }
 538
 539 /*
 540    ==================
 541    FixEdges_r
 542    ==================
 543  */
 544 void FixEdges_r( node_t *node ){
 545         int i;
 546         face_t  *f;
 547
 548         if ( node->planenum == PLANENUM_LEAF ) {
 549                 return;
 550         }
 551
 552         for ( f = node->faces ; f ; f = f->next )
 553                 FixFaceEdges( node, f );
 554
 555         for ( i = 0 ; i < 2 ; i++ )
 556                 FixEdges_r( node->children[i] );
 557 }
 558
 559 /*
 560    ===========
 561    FixTjuncs
 562
 563    ===========
 564  */
 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 ) );
 569         c_totalverts = 0;
 570         c_uniqueverts = 0;
 571         c_faceoverflows = 0;
 572         EmitVertexes_r( headnode );
 573         Sys_FPrintf( SYS_VRB, "%i unique from %i\n", c_uniqueverts, c_totalverts );
 574
 575         // break edges on tjunctions
 576         Sys_FPrintf( SYS_VRB, "---- tjunc ----\n" );
 577         c_tryedges = 0;
 578         c_degenerate = 0;
 579         c_facecollapse = 0;
 580         c_tjunctions = 0;
 581         if ( !notjunc ) {
 582                 FixEdges_r( headnode );
 583         }
 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 );
 589 }
 590
 591
 592 //========================================================
 593
 594 int c_faces;
 595
 596 face_t  *AllocFace( void ){
 597         face_t  *f;
 598
 599         f = malloc( sizeof( *f ) );
 600         memset( f, 0, sizeof( *f ) );
 601         c_faces++;
 602
 603         return f;
 604 }
 605
 606 face_t *NewFaceFromFace( face_t *f ){
 607         face_t  *newf;
 608
 609         newf = AllocFace();
 610         *newf = *f;
 611         newf->merged = NULL;
 612         newf->split[0] = newf->split[1] = NULL;
 613         newf->w = NULL;
 614         return newf;
 615 }
 616
 617 void FreeFace( face_t *f ){
 618         if ( f->w ) {
 619                 FreeWinding( f->w );
 620         }
 621         free( f );
 622         c_faces--;
 623 }
 624
 625 //========================================================
 626
 627 /*
 628    ==================
 629    GetEdge
 630
 631    Called by writebsp.
 632    Don't allow four way edges
 633    ==================
 634  */
 635 int GetEdge2( int v1, int v2,  face_t *f ){
 636         dedge_t *edge;
 637         int i;
 638
 639         c_tryedges++;
 640
 641         if ( !noshare ) {
 642                 for ( i = firstmodeledge ; i < numedges ; i++ )
 643                 {
 644                         edge = &dedges[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");
 649                                         continue;
 650                                 }
 651                                 edgefaces[i][1] = f;
 652                                 return -i;
 653                         }
 654         #if 0
 655                         if ( v1 == edge->v[0] && v2 == edge->v[1] ) {
 656                                 Sys_FPrintf( SYS_WRN, "WARNING: multiple forward edge\n" );
 657                                 return i;
 658                         }
 659         #endif
 660                 }
 661         }
 662
 663 // emit an edge
 664         if ( numedges >= MAX_MAP_EDGES ) {
 665                 Error( "numedges == MAX_MAP_EDGES" );
 666         }
 667         edge = &dedges[numedges];
 668         numedges++;
 669         edge->v[0] = v1;
 670         edge->v[1] = v2;
 671         edgefaces[numedges - 1][0] = f;
 672
 673         return numedges - 1;
 674 }
 675
 676 /*
 677    ===========================================================================
 678
 679    FACE MERGING
 680
 681    ===========================================================================
 682  */
 683
 684 #define CONTINUOUS_EPSILON  0.001
 685
 686 /*
 687    =============
 688    TryMergeWinding
 689
 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
 692
 693    Returns NULL if the faces couldn't be merged, or the new face.
 694    The originals will NOT be freed.
 695    =============
 696  */
 697 winding_t *TryMergeWinding( winding_t *f1, winding_t *f2, vec3_t planenormal ){
 698         vec_t       *p1, *p2, *p3, *p4, *back;
 699         winding_t   *newf;
 700         int i, j, k, l;
 701         vec3_t normal, delta;
 702         vec_t dot;
 703         qboolean keep1, keep2;
 704
 705
 706         //
 707         // find a common edge
 708         //
 709         p1 = p2 = NULL; // stop compiler warning
 710         j = 0;          //
 711
 712         for ( i = 0 ; i < f1->numpoints ; i++ )
 713         {
 714                 p1 = f1->p[i];
 715                 p2 = f1->p[( i + 1 ) % f1->numpoints];
 716                 for ( j = 0 ; j < f2->numpoints ; j++ )
 717                 {
 718                         p3 = f2->p[j];
 719                         p4 = f2->p[( j + 1 ) % f2->numpoints];
 720                         for ( k = 0 ; k < 3 ; k++ )
 721                         {
 722                                 if ( fabs( p1[k] - p4[k] ) > EQUAL_EPSILON ) {
 723                                         break;
 724                                 }
 725                                 if ( fabs( p2[k] - p3[k] ) > EQUAL_EPSILON ) {
 726                                         break;
 727                                 }
 728                         }
 729                         if ( k == 3 ) {
 730                                 break;
 731                         }
 732                 }
 733                 if ( j < f2->numpoints ) {
 734                         break;
 735                 }
 736         }
 737
 738         if ( i == f1->numpoints ) {
 739                 return NULL;            // no matching edges
 740
 741         }
 742         //
 743         // check slope of connected lines
 744         // if the slopes are colinear, the point can be removed
 745         //
 746         back = f1->p[( i + f1->numpoints - 1 ) % f1->numpoints];
 747         VectorSubtract( p1, back, delta );
 748         CrossProduct( planenormal, delta, normal );
 749         VectorNormalize( normal, normal );
 750
 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
 756         }
 757         keep1 = (qboolean)( dot < -CONTINUOUS_EPSILON );
 758
 759         back = f1->p[( i + 2 ) % f1->numpoints];
 760         VectorSubtract( back, p2, delta );
 761         CrossProduct( planenormal, delta, normal );
 762         VectorNormalize( normal, normal );
 763
 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
 769         }
 770         keep2 = (qboolean)( dot < -CONTINUOUS_EPSILON );
 771
 772         //
 773         // build the new polygon
 774         //
 775         newf = AllocWinding( f1->numpoints + f2->numpoints );
 776
 777         // copy first polygon
 778         for ( k = ( i + 1 ) % f1->numpoints ; k != i ; k = ( k + 1 ) % f1->numpoints )
 779         {
 780                 if ( k == ( i + 1 ) % f1->numpoints && !keep2 ) {
 781                         continue;
 782                 }
 783
 784                 VectorCopy( f1->p[k], newf->p[newf->numpoints] );
 785                 newf->numpoints++;
 786         }
 787
 788         // copy second polygon
 789         for ( l = ( j + 1 ) % f2->numpoints ; l != j ; l = ( l + 1 ) % f2->numpoints )
 790         {
 791                 if ( l == ( j + 1 ) % f2->numpoints && !keep1 ) {
 792                         continue;
 793                 }
 794                 VectorCopy( f2->p[l], newf->p[newf->numpoints] );
 795                 newf->numpoints++;
 796         }
 797
 798         return newf;
 799 }
 800
 801 /*
 802    =============
 803    TryMerge
 804
 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
 807
 808    Returns NULL if the faces couldn't be merged, or the new face.
 809    The originals will NOT be freed.
 810    =============
 811  */
 812 face_t *TryMerge( face_t *f1, face_t *f2, vec3_t planenormal ){
 813         face_t      *newf;
 814         winding_t   *nw;
 815
 816         if ( !f1->w || !f2->w ) {
 817                 return NULL;
 818         }
 819         if ( f1->texinfo != f2->texinfo ) {
 820                 return NULL;
 821         }
 822         if ( f1->planenum != f2->planenum ) { // on front and back sides
 823                 return NULL;
 824         }
 825         if ( f1->contents != f2->contents ) {
 826                 return NULL;
 827         }
 828
 829
 830         nw = TryMergeWinding( f1->w, f2->w, planenormal );
 831         if ( !nw ) {
 832                 return NULL;
 833         }
 834
 835         c_merge++;
 836         newf = NewFaceFromFace( f1 );
 837         newf->w = nw;
 838
 839         f1->merged = newf;
 840         f2->merged = newf;
 841
 842         return newf;
 843 }
 844
 845 /*
 846    ===============
 847    MergeNodeFaces
 848    ===============
 849  */
 850 void MergeNodeFaces( node_t *node ){
 851         face_t  *f1, *f2, *end;
 852         face_t  *merged;
 853         plane_t *plane;
 854
 855         plane = &mapplanes[node->planenum];
 856         merged = NULL;
 857
 858         for ( f1 = node->faces ; f1 ; f1 = f1->next )
 859         {
 860                 if ( f1->merged || f1->split[0] || f1->split[1] ) {
 861                         continue;
 862                 }
 863                 for ( f2 = node->faces ; f2 != f1 ; f2 = f2->next )
 864                 {
 865                         if ( f2->merged || f2->split[0] || f2->split[1] ) {
 866                                 continue;
 867                         }
 868                         merged = TryMerge( f1, f2, plane->normal );
 869                         if ( !merged ) {
 870                                 continue;
 871                         }
 872
 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 )
 876                                 ;
 877                         merged->next = NULL;
 878                         end->next = merged;
 879                         break;
 880                 }
 881         }
 882 }
 883
 884 //=====================================================================
 885
 886 /*
 887    ===============
 888    SubdivideFace
 889
 890    Chop up faces that are larger than we want in the surface cache
 891    ===============
 892  */
 893 void SubdivideFace( node_t *node, face_t *f ){
 894         float mins, maxs;
 895         vec_t v;
 896         int axis, i;
 897         texinfo_t   *tex;
 898         vec3_t temp;
 899         vec_t dist;
 900         winding_t   *w, *frontw, *backw;
 901
 902         if ( f->merged ) {
 903                 return;
 904         }
 905
 906 // special (non-surface cached) faces don't need subdivision
 907         tex = &texinfo[f->texinfo];
 908
 909         if ( tex->flags & ( SURF_WARP | SURF_SKY ) ) {
 910                 return;
 911         }
 912
 913         for ( axis = 0 ; axis < 2 ; axis++ )
 914         {
 915                 while ( 1 )
 916                 {
 917                         mins = 999999;
 918                         maxs = -999999;
 919
 920                         VectorCopy( tex->vecs[axis], temp );
 921                         w = f->w;
 922                         for ( i = 0 ; i < w->numpoints ; i++ )
 923                         {
 924                                 v = DotProduct( w->p[i], temp );
 925                                 if ( v < mins ) {
 926                                         mins = v;
 927                                 }
 928                                 if ( v > maxs ) {
 929                                         maxs = v;
 930                                 }
 931                         }
 932 #if 0
 933                         if ( maxs - mins <= 0 ) {
 934                                 Error( "zero extents" );
 935                         }
 936 #endif
 937                         if ( axis == 2 ) { // allow double high walls
 938                                 if ( maxs - mins <= subdivide_size /* *2 */ ) {
 939                                         break;
 940                                 }
 941                         }
 942                         else if ( maxs - mins <= subdivide_size ) {
 943                                 break;
 944                         }
 945
 946                         // split it
 947                         c_subdivide++;
 948
 949                         v = VectorNormalize( temp, temp );
 950
 951                         dist = ( mins + subdivide_size - 16 ) / v;
 952
 953                         ClipWindingEpsilon( w, temp, dist, ON_EPSILON, &frontw, &backw );
 954                         if ( !frontw || !backw ) {
 955                                 Error( "SubdivideFace: didn't split the polygon" );
 956                         }
 957
 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];
 962
 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];
 967
 968                         SubdivideFace( node, f->split[0] );
 969                         SubdivideFace( node, f->split[1] );
 970                         return;
 971                 }
 972         }
 973 }
 974
 975 void SubdivideNodeFaces( node_t *node ){
 976         face_t  *f;
 977
 978         for ( f = node->faces ; f ; f = f->next )
 979         {
 980                 SubdivideFace( node, f );
 981         }
 982 }
 983
 984 //===========================================================================
 985
 986 int c_nodefaces;
 987
 988
 989 /*
 990    ============
 991    FaceFromPortal
 992
 993    ============
 994  */
 995 face_t *FaceFromPortal( portal_t *p, int pside ){
 996         face_t  *f;
 997         side_t  *side;
 998
 999         side = p->side;
1000         if ( !side ) {
1001                 return NULL;    // portal does not bridge different visible contents
1002
1003         }
1004         f = AllocFace();
1005
1006         f->texinfo = side->texinfo;
1007         f->planenum = ( side->planenum & ~1 ) | pside;
1008         f->portal = p;
1009
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
1013
1014         }
1015         if ( pside ) {
1016                 f->w = ReverseWinding( p->winding );
1017                 f->contents = p->nodes[1]->contents;
1018         }
1019         else
1020         {
1021                 f->w = CopyWinding( p->winding );
1022                 f->contents = p->nodes[0]->contents;
1023         }
1024         return f;
1025 }
1026
1027
1028 /*
1029    ===============
1030    MakeFaces_r
1031
1032    If a portal will make a visible face,
1033    mark the side that originally created it
1034
1035    solid / empty : solid
1036    solid / water : solid
1037    water / empty : water
1038    water / water : none
1039    ===============
1040  */
1041 void MakeFaces_r( node_t *node ){
1042         portal_t    *p;
1043         int s;
1044
1045         // recurse down to leafs
1046         if ( node->planenum != PLANENUM_LEAF ) {
1047                 MakeFaces_r( node->children[0] );
1048                 MakeFaces_r( node->children[1] );
1049
1050                 // merge together all visible faces on the node
1051                 if ( !nomerge ) {
1052                         MergeNodeFaces( node );
1053                 }
1054                 if ( !nosubdiv ) {
1055                         SubdivideNodeFaces( node );
1056                 }
1057
1058                 return;
1059         }
1060
1061         // solid leafs never have visible faces
1062         if ( node->contents & CONTENTS_SOLID ) {
1063                 return;
1064         }
1065
1066         // see which portals are valid
1067         for ( p = node->portals ; p ; p = p->next[s] )
1068         {
1069                 s = ( p->nodes[1] == node );
1070
1071                 p->face[s] = FaceFromPortal( p, s );
1072                 if ( p->face[s] ) {
1073                         c_nodefaces++;
1074                         p->face[s]->next = p->onnode->faces;
1075                         p->onnode->faces = p->face[s];
1076                 }
1077         }
1078 }
1079
1080 /*
1081    ============
1082    MakeFaces
1083    ============
1084  */
1085 void MakeFaces( node_t *node ){
1086         Sys_FPrintf( SYS_VRB, "--- MakeFaces ---\n" );
1087         c_merge = 0;
1088         c_subdivide = 0;
1089         c_nodefaces = 0;
1090
1091         MakeFaces_r( node );
1092
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 );
1096 }