misc/mediasource/extra/netradiant-src/tools/quake2/q2map/faces.c

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