tools/quake2/q2map/faces.c

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