tools/quake3/q3map2/vis.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 ----------------------------------------------------------------------------------\r
  22 \r
  23 This code has been altered significantly from its original form, to support\r
  24 several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
  25 \r
  26 ------------------------------------------------------------------------------- */\r
  27 \r
  28 \r
  29 \r
  30 /* marker */\r
  31 #define VIS_C\r
  32 \r
  33 \r
  34 \r
  35 /* dependencies */\r
  36 #include "q3map2.h"\r
  37 \r
  38 \r
  39 \r
  40 \r
  41 void PlaneFromWinding (fixedWinding_t *w, visPlane_t *plane)\r
  42 {\r
  43         vec3_t          v1, v2;\r
  44 \r
  45 // calc plane\r
  46         VectorSubtract (w->points[2], w->points[1], v1);\r
  47         VectorSubtract (w->points[0], w->points[1], v2);\r
  48         CrossProduct (v2, v1, plane->normal);\r
  49         VectorNormalize (plane->normal, plane->normal);\r
  50         plane->dist = DotProduct (w->points[0], plane->normal);\r
  51 }\r
  52 \r
  53 \r
  54 /*\r
  55 NewFixedWinding()\r
  56 returns a new fixed winding\r
  57 ydnar: altered this a bit to reconcile multiply-defined winding_t\r
  58 */\r
  59 \r
  60 fixedWinding_t *NewFixedWinding( int points )\r
  61 {\r
  62         fixedWinding_t  *w;\r
  63         int                     size;\r
  64         \r
  65         if (points > MAX_POINTS_ON_WINDING)\r
  66                 Error ("NewWinding: %i points", points);\r
  67         \r
  68         size = (int)((fixedWinding_t *)0)->points[points];\r
  69         w = safe_malloc (size);\r
  70         memset (w, 0, size);\r
  71         \r
  72         return w;\r
  73 }\r
  74 \r
  75 \r
  76 \r
  77 void prl(leaf_t *l)\r
  78 {\r
  79         int                     i;\r
  80         vportal_t       *p;\r
  81         visPlane_t      pl;\r
  82         \r
  83         for (i=0 ; i<l->numportals ; i++)\r
  84         {\r
  85                 p = l->portals[i];\r
  86                 pl = p->plane;\r
  87                 Sys_Printf ("portal %4i to leaf %4i : %7.1f : (%4.1f, %4.1f, %4.1f)\n",(int)(p-portals),p->leaf,pl.dist, pl.normal[0], pl.normal[1], pl.normal[2]);\r
  88         }\r
  89 }\r
  90 \r
  91 \r
  92 //=============================================================================\r
  93 \r
  94 /*\r
  95 =============\r
  96 SortPortals\r
  97 \r
  98 Sorts the portals from the least complex, so the later ones can reuse\r
  99 the earlier information.\r
 100 =============\r
 101 */\r
 102 int PComp (const void *a, const void *b)\r
 103 {\r
 104         if ( (*(vportal_t **)a)->nummightsee == (*(vportal_t **)b)->nummightsee)\r
 105                 return 0;\r
 106         if ( (*(vportal_t **)a)->nummightsee < (*(vportal_t **)b)->nummightsee)\r
 107                 return -1;\r
 108         return 1;\r
 109 }\r
 110 void SortPortals (void)\r
 111 {\r
 112         int             i;\r
 113         \r
 114         for (i=0 ; i<numportals*2 ; i++)\r
 115                 sorted_portals[i] = &portals[i];\r
 116 \r
 117         if (nosort)\r
 118                 return;\r
 119         qsort (sorted_portals, numportals*2, sizeof(sorted_portals[0]), PComp);\r
 120 }\r
 121 \r
 122 \r
 123 /*\r
 124 ==============\r
 125 LeafVectorFromPortalVector\r
 126 ==============\r
 127 */\r
 128 int LeafVectorFromPortalVector (byte *portalbits, byte *leafbits)\r
 129 {\r
 130         int                     i, j, leafnum;\r
 131         vportal_t       *p;\r
 132         int                     c_leafs;\r
 133 \r
 134 \r
 135         for (i=0 ; i<numportals*2 ; i++)\r
 136         {\r
 137                 if (portalbits[i>>3] & (1<<(i&7)) )\r
 138                 {\r
 139                         p = portals+i;\r
 140                         leafbits[p->leaf>>3] |= (1<<(p->leaf&7));\r
 141                 }\r
 142         }\r
 143 \r
 144         for (j = 0; j < portalclusters; j++)\r
 145         {\r
 146                 leafnum = j;\r
 147                 while (leafs[leafnum].merged >= 0)\r
 148                         leafnum = leafs[leafnum].merged;\r
 149                 //if the merged leaf is visible then the original leaf is visible\r
 150                 if (leafbits[leafnum>>3] & (1<<(leafnum&7)))\r
 151                 {\r
 152                         leafbits[j>>3] |= (1<<(j&7));\r
 153                 }\r
 154         }\r
 155 \r
 156         c_leafs = CountBits (leafbits, portalclusters);\r
 157 \r
 158         return c_leafs;\r
 159 }\r
 160 \r
 161 \r
 162 /*\r
 163 ===============\r
 164 ClusterMerge\r
 165 \r
 166 Merges the portal visibility for a leaf\r
 167 ===============\r
 168 */\r
 169 void ClusterMerge (int leafnum)\r
 170 {\r
 171         leaf_t          *leaf;\r
 172         byte            portalvector[MAX_PORTALS/8];\r
 173         byte            uncompressed[MAX_MAP_LEAFS/8];\r
 174         int                     i, j;\r
 175         int                     numvis, mergedleafnum;\r
 176         vportal_t       *p;\r
 177         int                     pnum;\r
 178 \r
 179         // OR together all the portalvis bits\r
 180 \r
 181         mergedleafnum = leafnum;\r
 182         while(leafs[mergedleafnum].merged >= 0)\r
 183                 mergedleafnum = leafs[mergedleafnum].merged;\r
 184 \r
 185         memset (portalvector, 0, portalbytes);\r
 186         leaf = &leafs[mergedleafnum];\r
 187         for (i = 0; i < leaf->numportals; i++)\r
 188         {\r
 189                 p = leaf->portals[i];\r
 190                 if (p->removed)\r
 191                         continue;\r
 192 \r
 193                 if (p->status != stat_done)\r
 194                         Error ("portal not done");\r
 195                 for (j=0 ; j<portallongs ; j++)\r
 196                         ((long *)portalvector)[j] |= ((long *)p->portalvis)[j];\r
 197                 pnum = p - portals;\r
 198                 portalvector[pnum>>3] |= 1<<(pnum&7);\r
 199         }\r
 200 \r
 201         memset (uncompressed, 0, leafbytes);\r
 202 \r
 203         uncompressed[mergedleafnum>>3] |= (1<<(mergedleafnum&7));\r
 204         // convert portal bits to leaf bits\r
 205         numvis = LeafVectorFromPortalVector (portalvector, uncompressed);\r
 206 \r
 207 //      if (uncompressed[leafnum>>3] & (1<<(leafnum&7)))\r
 208 //              Sys_Printf ("WARNING: Leaf portals saw into leaf\n");\r
 209                 \r
 210 //      uncompressed[leafnum>>3] |= (1<<(leafnum&7));\r
 211 \r
 212         numvis++;               // count the leaf itself\r
 213 \r
 214         totalvis += numvis;\r
 215 \r
 216         Sys_FPrintf (SYS_VRB,"cluster %4i : %4i visible\n", leafnum, numvis);\r
 217 \r
 218         memcpy (bspVisBytes + VIS_HEADER_SIZE + leafnum*leafbytes, uncompressed, leafbytes);\r
 219 }\r
 220 \r
 221 /*\r
 222 ==================\r
 223 CalcPortalVis\r
 224 ==================\r
 225 */\r
 226 void CalcPortalVis (void)\r
 227 {\r
 228 #ifdef MREDEBUG\r
 229         Sys_Printf("%6d portals out of %d", 0, numportals*2);\r
 230         //get rid of the counter\r
 231         RunThreadsOnIndividual (numportals*2, qfalse, PortalFlow);\r
 232 #else\r
 233         RunThreadsOnIndividual (numportals*2, qtrue, PortalFlow);\r
 234 #endif\r
 235 \r
 236 }\r
 237 \r
 238 /*\r
 239 ==================\r
 240 CalcPassageVis\r
 241 ==================\r
 242 */\r
 243 void CalcPassageVis(void)\r
 244 {\r
 245         PassageMemory();\r
 246 \r
 247 #ifdef MREDEBUG\r
 248         _printf("%6d portals out of %d", 0, numportals*2);\r
 249         RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages);\r
 250         _printf("\n");\r
 251         _printf("%6d portals out of %d", 0, numportals*2);\r
 252         RunThreadsOnIndividual (numportals*2, qfalse, PassageFlow);\r
 253         _printf("\n");\r
 254 #else\r
 255         Sys_Printf( "\n--- CreatePassages (%d) ---\n", numportals * 2 );\r
 256         RunThreadsOnIndividual( numportals*2, qtrue, CreatePassages );\r
 257         \r
 258         Sys_Printf( "\n--- PassageFlow (%d) ---\n", numportals * 2 );\r
 259         RunThreadsOnIndividual( numportals * 2, qtrue, PassageFlow );\r
 260 #endif\r
 261 }\r
 262 \r
 263 /*\r
 264 ==================\r
 265 CalcPassagePortalVis\r
 266 ==================\r
 267 */\r
 268 void CalcPassagePortalVis(void)\r
 269 {\r
 270         PassageMemory();\r
 271 \r
 272 #ifdef MREDEBUG\r
 273         Sys_Printf("%6d portals out of %d", 0, numportals*2);\r
 274         RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages);\r
 275         Sys_Printf("\n");\r
 276         Sys_Printf("%6d portals out of %d", 0, numportals*2);\r
 277         RunThreadsOnIndividual (numportals*2, qfalse, PassagePortalFlow);\r
 278         Sys_Printf("\n");\r
 279 #else\r
 280         Sys_Printf( "\n--- CreatePassages (%d) ---\n", numportals * 2 );\r
 281         RunThreadsOnIndividual( numportals * 2, qtrue, CreatePassages);\r
 282         \r
 283         Sys_Printf( "\n--- PassagePortalFlow (%d) ---\n", numportals * 2 );\r
 284         RunThreadsOnIndividual( numportals * 2, qtrue, PassagePortalFlow );\r
 285 #endif\r
 286 }\r
 287 \r
 288 /*\r
 289 ==================\r
 290 CalcFastVis\r
 291 ==================\r
 292 */\r
 293 void CalcFastVis(void)\r
 294 {\r
 295         int             i;\r
 296 \r
 297         // fastvis just uses mightsee for a very loose bound\r
 298         for (i=0 ; i<numportals*2 ; i++)\r
 299         {\r
 300                 portals[i].portalvis = portals[i].portalflood;\r
 301                 portals[i].status = stat_done;\r
 302         }\r
 303 }\r
 304 \r
 305 /*\r
 306 ==================\r
 307 CalcVis\r
 308 ==================\r
 309 */\r
 310 void CalcVis (void)\r
 311 {\r
 312         int                     i;\r
 313         const char      *value;\r
 314         \r
 315         \r
 316         /* ydnar: rr2do2's farplane code */\r
 317         farPlaneDist = 0.0f;\r
 318         value = ValueForKey( &entities[ 0 ], "_farplanedist" );         /* proper '_' prefixed key */\r
 319         if( value[ 0 ] == '\0' )\r
 320                 value = ValueForKey( &entities[ 0 ], "fogclip" );               /* wolf compatibility */\r
 321         if( value[ 0 ] == '\0' )\r
 322                 value = ValueForKey( &entities[ 0 ], "distancecull" );  /* sof2 compatibility */\r
 323         if( value[ 0 ] != '\0' )\r
 324         {\r
 325                 farPlaneDist = atof( value );\r
 326                 if( farPlaneDist > 0.0f )\r
 327                         Sys_Printf( "farplane distance = %.1f\n", farPlaneDist );\r
 328                 else\r
 329                         farPlaneDist = 0.0f;\r
 330         }\r
 331         \r
 332         \r
 333         \r
 334         Sys_Printf( "\n--- BasePortalVis (%d) ---\n", numportals * 2 );\r
 335         RunThreadsOnIndividual( numportals * 2, qtrue, BasePortalVis );\r
 336         \r
 337 //      RunThreadsOnIndividual (numportals*2, qtrue, BetterPortalVis);\r
 338 \r
 339         SortPortals ();\r
 340 \r
 341   if (fastvis) {\r
 342     CalcFastVis();\r
 343   }\r
 344   else if ( noPassageVis ) {\r
 345     CalcPortalVis();\r
 346   }\r
 347   else if ( passageVisOnly ) {\r
 348     CalcPassageVis();\r
 349   }\r
 350   else {\r
 351     CalcPassagePortalVis();\r
 352   }\r
 353         //\r
 354         // assemble the leaf vis lists by oring and compressing the portal lists\r
 355         //\r
 356         Sys_Printf("creating leaf vis...\n");\r
 357         for (i=0 ; i<portalclusters ; i++)\r
 358                 ClusterMerge (i);\r
 359 \r
 360   Sys_Printf( "Total visible clusters: %i\n", totalvis );\r
 361   Sys_Printf( "Average clusters visible: %i\n", totalvis / portalclusters );\r
 362 }\r
 363 \r
 364 /*\r
 365 ==================\r
 366 SetPortalSphere\r
 367 ==================\r
 368 */\r
 369 void SetPortalSphere (vportal_t *p)\r
 370 {\r
 371         int             i;\r
 372         vec3_t  total, dist;\r
 373         fixedWinding_t  *w;\r
 374         float   r, bestr;\r
 375 \r
 376         w = p->winding;\r
 377         VectorCopy (vec3_origin, total);\r
 378         for (i=0 ; i<w->numpoints ; i++)\r
 379         {\r
 380                 VectorAdd (total, w->points[i], total);\r
 381         }\r
 382         \r
 383         for (i=0 ; i<3 ; i++)\r
 384                 total[i] /= w->numpoints;\r
 385 \r
 386         bestr = 0;              \r
 387         for (i=0 ; i<w->numpoints ; i++)\r
 388         {\r
 389                 VectorSubtract (w->points[i], total, dist);\r
 390                 r = VectorLength (dist);\r
 391                 if (r > bestr)\r
 392                         bestr = r;\r
 393         }\r
 394         VectorCopy (total, p->origin);\r
 395         p->radius = bestr;\r
 396 }\r
 397 \r
 398 /*\r
 399 =============\r
 400 Winding_PlanesConcave\r
 401 =============\r
 402 */\r
 403 #define WCONVEX_EPSILON         0.2\r
 404 \r
 405 int Winding_PlanesConcave(fixedWinding_t *w1, fixedWinding_t *w2,\r
 406                                                          vec3_t normal1, vec3_t normal2,\r
 407                                                          float dist1, float dist2)\r
 408 {\r
 409         int i;\r
 410 \r
 411         if (!w1 || !w2) return qfalse;\r
 412 \r
 413         // check if one of the points of winding 1 is at the front of the plane of winding 2\r
 414         for (i = 0; i < w1->numpoints; i++)\r
 415         {\r
 416                 if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return qtrue;\r
 417         }\r
 418         // check if one of the points of winding 2 is at the front of the plane of winding 1\r
 419         for (i = 0; i < w2->numpoints; i++)\r
 420         {\r
 421                 if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return qtrue;\r
 422         }\r
 423 \r
 424         return qfalse;\r
 425 }\r
 426 \r
 427 /*\r
 428 ============\r
 429 TryMergeLeaves\r
 430 ============\r
 431 */\r
 432 int TryMergeLeaves(int l1num, int l2num)\r
 433 {\r
 434         int i, j, k, n, numportals;\r
 435         visPlane_t plane1, plane2;\r
 436         leaf_t *l1, *l2;\r
 437         vportal_t *p1, *p2;\r
 438         vportal_t *portals[MAX_PORTALS_ON_LEAF];\r
 439 \r
 440         for (k = 0; k < 2; k++)\r
 441         {\r
 442                 if (k) l1 = &leafs[l1num];\r
 443                 else l1 = &faceleafs[l1num];\r
 444                 for (i = 0; i < l1->numportals; i++)\r
 445                 {\r
 446                         p1 = l1->portals[i];\r
 447                         if (p1->leaf == l2num) continue;\r
 448                         for (n = 0; n < 2; n++)\r
 449                         {\r
 450                                 if (n) l2 = &leafs[l2num];\r
 451                                 else l2 = &faceleafs[l2num];\r
 452                                 for (j = 0; j < l2->numportals; j++)\r
 453                                 {\r
 454                                         p2 = l2->portals[j];\r
 455                                         if (p2->leaf == l1num) continue;\r
 456                                         //\r
 457                                         plane1 = p1->plane;\r
 458                                         plane2 = p2->plane;\r
 459                                         if (Winding_PlanesConcave(p1->winding, p2->winding, plane1.normal, plane2.normal, plane1.dist, plane2.dist))\r
 460                                                 return qfalse;\r
 461                                 }\r
 462                         }\r
 463                 }\r
 464         }\r
 465         for (k = 0; k < 2; k++)\r
 466         {\r
 467                 if (k)\r
 468                 {\r
 469                         l1 = &leafs[l1num];\r
 470                         l2 = &leafs[l2num];\r
 471                 }\r
 472                 else\r
 473                 {\r
 474                         l1 = &faceleafs[l1num];\r
 475                         l2 = &faceleafs[l2num];\r
 476                 }\r
 477                 numportals = 0;\r
 478                 //the leaves can be merged now\r
 479                 for (i = 0; i < l1->numportals; i++)\r
 480                 {\r
 481                         p1 = l1->portals[i];\r
 482                         if (p1->leaf == l2num)\r
 483                         {\r
 484                                 p1->removed = qtrue;\r
 485                                 continue;\r
 486                         }\r
 487                         portals[numportals++] = p1;\r
 488                 }\r
 489                 for (j = 0; j < l2->numportals; j++)\r
 490                 {\r
 491                         p2 = l2->portals[j];\r
 492                         if (p2->leaf == l1num)\r
 493                         {\r
 494                                 p2->removed = qtrue;\r
 495                                 continue;\r
 496                         }\r
 497                         portals[numportals++] = p2;\r
 498                 }\r
 499                 for (i = 0; i < numportals; i++)\r
 500                 {\r
 501                         l2->portals[i] = portals[i];\r
 502                 }\r
 503                 l2->numportals = numportals;\r
 504                 l1->merged = l2num;\r
 505         }\r
 506         return qtrue;\r
 507 }\r
 508 \r
 509 /*\r
 510 ============\r
 511 UpdatePortals\r
 512 ============\r
 513 */\r
 514 void UpdatePortals(void)\r
 515 {\r
 516         int i;\r
 517         vportal_t *p;\r
 518 \r
 519         for (i = 0; i < numportals * 2; i++)\r
 520         {\r
 521                 p = &portals[i];\r
 522                 if (p->removed)\r
 523                         continue;\r
 524                 while(leafs[p->leaf].merged >= 0)\r
 525                         p->leaf = leafs[p->leaf].merged;\r
 526         }\r
 527 }\r
 528 \r
 529 /*\r
 530 ============\r
 531 MergeLeaves\r
 532 \r
 533 try to merge leaves but don't merge through hint splitters\r
 534 ============\r
 535 */\r
 536 void MergeLeaves(void)\r
 537 {\r
 538         int i, j, nummerges, totalnummerges;\r
 539         leaf_t *leaf;\r
 540         vportal_t *p;\r
 541 \r
 542         totalnummerges = 0;\r
 543         do\r
 544         {\r
 545                 nummerges = 0;\r
 546                 for (i = 0; i < portalclusters; i++)\r
 547                 {\r
 548                         leaf = &leafs[i];\r
 549                         //if this leaf is merged already\r
 550 \r
 551                         /* ydnar: vmods: merge all non-hint portals */\r
 552                         if( leaf->merged >= 0 && hint == qfalse )\r
 553                                 continue;\r
 554 \r
 555 \r
 556                         for (j = 0; j < leaf->numportals; j++)\r
 557                         {\r
 558                                 p = leaf->portals[j];\r
 559                                 //\r
 560                                 if (p->removed)\r
 561                                         continue;\r
 562                                 //never merge through hint portals\r
 563                                 if (p->hint)\r
 564                                         continue;\r
 565                                 if (TryMergeLeaves(i, p->leaf))\r
 566                                 {\r
 567                                         UpdatePortals();\r
 568                                         nummerges++;\r
 569                                         break;\r
 570                                 }\r
 571                         }\r
 572                 }\r
 573                 totalnummerges += nummerges;\r
 574         } while (nummerges);\r
 575         Sys_Printf("%6d leaves merged\n", totalnummerges);\r
 576 }\r
 577 \r
 578 /*\r
 579 ============\r
 580 TryMergeWinding\r
 581 ============\r
 582 */\r
 583 #define CONTINUOUS_EPSILON      0.005\r
 584 \r
 585 fixedWinding_t *TryMergeWinding (fixedWinding_t *f1, fixedWinding_t *f2, vec3_t planenormal)\r
 586 {\r
 587         vec_t           *p1, *p2, *p3, *p4, *back;\r
 588         fixedWinding_t  *newf;\r
 589         int                     i, j, k, l;\r
 590         vec3_t          normal, delta;\r
 591         vec_t           dot;\r
 592         qboolean        keep1, keep2;\r
 593         \r
 594 \r
 595         //\r
 596         // find a common edge\r
 597         //      \r
 598         p1 = p2 = NULL; // stop compiler warning\r
 599         j = 0;                  // \r
 600         \r
 601         for (i = 0; i < f1->numpoints; i++)\r
 602         {\r
 603                 p1 = f1->points[i];\r
 604                 p2 = f1->points[(i+1) % f1->numpoints];\r
 605                 for (j = 0; j < f2->numpoints; j++)\r
 606                 {\r
 607                         p3 = f2->points[j];\r
 608                         p4 = f2->points[(j+1) % f2->numpoints];\r
 609                         for (k = 0; k < 3; k++)\r
 610                         {\r
 611                                 if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME\r
 612                                         break;\r
 613                                 if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME\r
 614                                         break;\r
 615                         } //end for\r
 616                         if (k==3)\r
 617                                 break;\r
 618                 } //end for\r
 619                 if (j < f2->numpoints)\r
 620                         break;\r
 621         } //end for\r
 622         \r
 623         if (i == f1->numpoints)\r
 624                 return NULL;                    // no matching edges\r
 625 \r
 626         //\r
 627         // check slope of connected lines\r
 628         // if the slopes are colinear, the point can be removed\r
 629         //\r
 630         back = f1->points[(i+f1->numpoints-1)%f1->numpoints];\r
 631         VectorSubtract (p1, back, delta);\r
 632         CrossProduct (planenormal, delta, normal);\r
 633         VectorNormalize (normal, normal);\r
 634         \r
 635         back = f2->points[(j+2)%f2->numpoints];\r
 636         VectorSubtract (back, p1, delta);\r
 637         dot = DotProduct (delta, normal);\r
 638         if (dot > CONTINUOUS_EPSILON)\r
 639                 return NULL;                    // not a convex polygon\r
 640         keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);\r
 641         \r
 642         back = f1->points[(i+2)%f1->numpoints];\r
 643         VectorSubtract (back, p2, delta);\r
 644         CrossProduct (planenormal, delta, normal);\r
 645         VectorNormalize (normal, normal);\r
 646 \r
 647         back = f2->points[(j+f2->numpoints-1)%f2->numpoints];\r
 648         VectorSubtract (back, p2, delta);\r
 649         dot = DotProduct (delta, normal);\r
 650         if (dot > CONTINUOUS_EPSILON)\r
 651                 return NULL;                    // not a convex polygon\r
 652         keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);\r
 653 \r
 654         //\r
 655         // build the new polygon\r
 656         //\r
 657         newf = NewFixedWinding (f1->numpoints + f2->numpoints);\r
 658         \r
 659         // copy first polygon\r
 660         for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)\r
 661         {\r
 662                 if (k==(i+1)%f1->numpoints && !keep2)\r
 663                         continue;\r
 664                 \r
 665                 VectorCopy (f1->points[k], newf->points[newf->numpoints]);\r
 666                 newf->numpoints++;\r
 667         }\r
 668         \r
 669         // copy second polygon\r
 670         for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)\r
 671         {\r
 672                 if (l==(j+1)%f2->numpoints && !keep1)\r
 673                         continue;\r
 674                 VectorCopy (f2->points[l], newf->points[newf->numpoints]);\r
 675                 newf->numpoints++;\r
 676         }\r
 677 \r
 678         return newf;\r
 679 }\r
 680 \r
 681 /*\r
 682 ============\r
 683 MergeLeafPortals\r
 684 ============\r
 685 */\r
 686 void MergeLeafPortals(void)\r
 687 {\r
 688         int i, j, k, nummerges, hintsmerged;\r
 689         leaf_t *leaf;\r
 690         vportal_t *p1, *p2;\r
 691         fixedWinding_t *w;\r
 692 \r
 693         nummerges = 0;\r
 694         hintsmerged = 0;\r
 695         for (i = 0; i < portalclusters; i++)\r
 696         {\r
 697                 leaf = &leafs[i];\r
 698                 if (leaf->merged >= 0) continue;\r
 699                 for (j = 0; j < leaf->numportals; j++)\r
 700                 {\r
 701                         p1 = leaf->portals[j];\r
 702                         if (p1->removed)\r
 703                                 continue;\r
 704                         for (k = j+1; k < leaf->numportals; k++)\r
 705                         {\r
 706                                 p2 = leaf->portals[k];\r
 707                                 if (p2->removed)\r
 708                                         continue;\r
 709                                 if (p1->leaf == p2->leaf)\r
 710                                 {\r
 711                                         w = TryMergeWinding(p1->winding, p2->winding, p1->plane.normal);\r
 712                                         if (w)\r
 713                                         {\r
 714                                                 free( p1->winding );    //% FreeWinding(p1->winding);\r
 715                                                 p1->winding = w;\r
 716                                                 if (p1->hint && p2->hint)\r
 717                                                         hintsmerged++;\r
 718                                                 p1->hint |= p2->hint;\r
 719                                                 SetPortalSphere(p1);\r
 720                                                 p2->removed = qtrue;\r
 721                                                 nummerges++;\r
 722                                                 i--;\r
 723                                                 break;\r
 724                                         }\r
 725                                 }\r
 726                         }\r
 727                         if (k < leaf->numportals)\r
 728                                 break;\r
 729                 }\r
 730         }\r
 731         Sys_Printf("%6d portals merged\n", nummerges);\r
 732         Sys_Printf("%6d hint portals merged\n", hintsmerged);\r
 733 }\r
 734 \r
 735 \r
 736 /*\r
 737 ============\r
 738 WritePortals\r
 739 ============\r
 740 */\r
 741 int CountActivePortals(void)\r
 742 {\r
 743         int num, hints, j;\r
 744         vportal_t *p;\r
 745 \r
 746         num = 0;\r
 747         hints = 0;\r
 748         for (j = 0; j < numportals * 2; j++)\r
 749         {\r
 750                 p = portals + j;\r
 751                 if (p->removed)\r
 752                         continue;\r
 753                 if (p->hint)\r
 754                         hints++;\r
 755                 num++;\r
 756         }\r
 757         Sys_Printf("%6d active portals\n", num);\r
 758         Sys_Printf("%6d hint portals\n", hints);\r
 759         return num;\r
 760 }\r
 761 \r
 762 /*\r
 763 ============\r
 764 WritePortals\r
 765 ============\r
 766 */\r
 767 void WriteFloat (FILE *f, vec_t v);\r
 768 \r
 769 void WritePortals(char *filename)\r
 770 {\r
 771         int i, j, num;\r
 772         FILE *pf;\r
 773         vportal_t *p;\r
 774         fixedWinding_t *w;\r
 775 \r
 776         // write the file\r
 777         pf = fopen (filename, "w");\r
 778         if (!pf)\r
 779                 Error ("Error opening %s", filename);\r
 780 \r
 781         num = 0;\r
 782         for (j = 0; j < numportals * 2; j++)\r
 783         {\r
 784                 p = portals + j;\r
 785                 if (p->removed)\r
 786                         continue;\r
 787 //              if (!p->hint)\r
 788 //                      continue;\r
 789                 num++;\r
 790         }\r
 791 \r
 792         fprintf (pf, "%s\n", PORTALFILE);\r
 793         fprintf (pf, "%i\n", 0);\r
 794         fprintf (pf, "%i\n", num);// + numfaces);\r
 795         fprintf (pf, "%i\n", 0);\r
 796 \r
 797         for (j = 0; j < numportals * 2; j++)\r
 798         {\r
 799                 p = portals + j;\r
 800                 if (p->removed)\r
 801                         continue;\r
 802 //              if (!p->hint)\r
 803 //                      continue;\r
 804                 w = p->winding;\r
 805                 fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);\r
 806                 fprintf (pf, "%d ", p->hint);\r
 807                 for (i=0 ; i<w->numpoints ; i++)\r
 808                 {\r
 809                         fprintf (pf,"(");\r
 810                         WriteFloat (pf, w->points[i][0]);\r
 811                         WriteFloat (pf, w->points[i][1]);\r
 812                         WriteFloat (pf, w->points[i][2]);\r
 813                         fprintf (pf,") ");\r
 814                 }\r
 815                 fprintf (pf,"\n");\r
 816         }\r
 817 \r
 818         /*\r
 819         for (j = 0; j < numfaces; j++)\r
 820         {\r
 821                 p = faces + j;\r
 822                 w = p->winding;\r
 823                 fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);\r
 824                 fprintf (pf, "0 ");\r
 825                 for (i=0 ; i<w->numpoints ; i++)\r
 826                 {\r
 827                         fprintf (pf,"(");\r
 828                         WriteFloat (pf, w->points[i][0]);\r
 829                         WriteFloat (pf, w->points[i][1]);\r
 830                         WriteFloat (pf, w->points[i][2]);\r
 831                         fprintf (pf,") ");\r
 832                 }\r
 833                 fprintf (pf,"\n");\r
 834         }*/\r
 835 \r
 836         fclose (pf);\r
 837 }\r
 838 \r
 839 /*\r
 840 ============\r
 841 LoadPortals\r
 842 ============\r
 843 */\r
 844 void LoadPortals (char *name)\r
 845 {\r
 846         int                     i, j, hint;\r
 847         vportal_t       *p;\r
 848         leaf_t          *l;\r
 849         char            magic[80];\r
 850         FILE            *f;\r
 851         int                     numpoints;\r
 852         fixedWinding_t  *w;\r
 853         int                     leafnums[2];\r
 854         visPlane_t      plane;\r
 855         \r
 856         if (!strcmp(name,"-"))\r
 857                 f = stdin;\r
 858         else\r
 859         {\r
 860                 f = fopen(name, "r");\r
 861                 if (!f)\r
 862                         Error ("LoadPortals: couldn't read %s\n",name);\r
 863         }\r
 864 \r
 865         if (fscanf (f,"%79s\n%i\n%i\n%i\n",magic, &portalclusters, &numportals, &numfaces) != 4)\r
 866                 Error ("LoadPortals: failed to read header");\r
 867         if (strcmp(magic,PORTALFILE))\r
 868                 Error ("LoadPortals: not a portal file");\r
 869 \r
 870         Sys_Printf ("%6i portalclusters\n", portalclusters);\r
 871         Sys_Printf ("%6i numportals\n", numportals);\r
 872         Sys_Printf ("%6i numfaces\n", numfaces);\r
 873 \r
 874         // these counts should take advantage of 64 bit systems automatically\r
 875         leafbytes = ((portalclusters+63)&~63)>>3;\r
 876         leaflongs = leafbytes/sizeof(long);\r
 877         \r
 878         portalbytes = ((numportals*2+63)&~63)>>3;\r
 879         portallongs = portalbytes/sizeof(long);\r
 880 \r
 881         // each file portal is split into two memory portals\r
 882         portals = safe_malloc(2*numportals*sizeof(vportal_t));\r
 883         memset (portals, 0, 2*numportals*sizeof(vportal_t));\r
 884         \r
 885         leafs = safe_malloc(portalclusters*sizeof(leaf_t));\r
 886         memset (leafs, 0, portalclusters*sizeof(leaf_t));\r
 887 \r
 888         for (i = 0; i < portalclusters; i++)\r
 889                 leafs[i].merged = -1;\r
 890 \r
 891         numBSPVisBytes = VIS_HEADER_SIZE + portalclusters*leafbytes;\r
 892 \r
 893         if (numBSPVisBytes > MAX_MAP_VISIBILITY)\r
 894           Error("MAX_MAP_VISIBILITY exceeded");\r
 895 \r
 896         ((int *)bspVisBytes)[0] = portalclusters;\r
 897         ((int *)bspVisBytes)[1] = leafbytes;\r
 898                 \r
 899         for (i=0, p=portals ; i<numportals ; i++)\r
 900         {\r
 901                 if (fscanf (f, "%i %i %i ", &numpoints, &leafnums[0], &leafnums[1]) != 3)\r
 902                         Error ("LoadPortals: reading portal %i", i);\r
 903                 if (numpoints > MAX_POINTS_ON_WINDING)\r
 904                         Error ("LoadPortals: portal %i has too many points", i);\r
 905                 if ( (unsigned)leafnums[0] > portalclusters\r
 906                 || (unsigned)leafnums[1] > portalclusters)\r
 907                         Error ("LoadPortals: reading portal %i", i);\r
 908                 if (fscanf (f, "%i ", &hint) != 1)\r
 909                         Error ("LoadPortals: reading hint state");\r
 910                 \r
 911                 w = p->winding = NewFixedWinding (numpoints);\r
 912                 w->numpoints = numpoints;\r
 913                 \r
 914                 for (j=0 ; j<numpoints ; j++)\r
 915                 {\r
 916                         double  v[3];\r
 917                         int             k;\r
 918 \r
 919                         // scanf into double, then assign to vec_t\r
 920                         // so we don't care what size vec_t is\r
 921                         if (fscanf (f, "(%lf %lf %lf ) "\r
 922                         , &v[0], &v[1], &v[2]) != 3)\r
 923                                 Error ("LoadPortals: reading portal %i", i);\r
 924                         for (k=0 ; k<3 ; k++)\r
 925                                 w->points[j][k] = v[k];\r
 926                 }\r
 927                 fscanf (f, "\n");\r
 928                 \r
 929                 // calc plane\r
 930                 PlaneFromWinding (w, &plane);\r
 931 \r
 932                 // create forward portal\r
 933                 l = &leafs[leafnums[0]];\r
 934                 if (l->numportals == MAX_PORTALS_ON_LEAF)\r
 935                         Error ("Leaf with too many portals");\r
 936                 l->portals[l->numportals] = p;\r
 937                 l->numportals++;\r
 938                 \r
 939                 p->num = i+1;\r
 940                 p->hint = hint;\r
 941                 p->winding = w;\r
 942                 VectorSubtract (vec3_origin, plane.normal, p->plane.normal);\r
 943                 p->plane.dist = -plane.dist;\r
 944                 p->leaf = leafnums[1];\r
 945                 SetPortalSphere (p);\r
 946                 p++;\r
 947                 \r
 948                 // create backwards portal\r
 949                 l = &leafs[leafnums[1]];\r
 950                 if (l->numportals == MAX_PORTALS_ON_LEAF)\r
 951                         Error ("Leaf with too many portals");\r
 952                 l->portals[l->numportals] = p;\r
 953                 l->numportals++;\r
 954                 \r
 955                 p->num = i+1;\r
 956                 p->hint = hint;\r
 957                 p->winding = NewFixedWinding(w->numpoints);\r
 958                 p->winding->numpoints = w->numpoints;\r
 959                 for (j=0 ; j<w->numpoints ; j++)\r
 960                 {\r
 961                         VectorCopy (w->points[w->numpoints-1-j], p->winding->points[j]);\r
 962                 }\r
 963 \r
 964                 p->plane = plane;\r
 965                 p->leaf = leafnums[0];\r
 966                 SetPortalSphere (p);\r
 967                 p++;\r
 968 \r
 969         }\r
 970 \r
 971         faces = safe_malloc(2*numfaces*sizeof(vportal_t));\r
 972         memset (faces, 0, 2*numfaces*sizeof(vportal_t));\r
 973 \r
 974         faceleafs = safe_malloc(portalclusters*sizeof(leaf_t));\r
 975         memset(faceleafs, 0, portalclusters*sizeof(leaf_t));\r
 976 \r
 977         for (i = 0, p = faces; i < numfaces; i++)\r
 978         {\r
 979                 if (fscanf (f, "%i %i ", &numpoints, &leafnums[0]) != 2)\r
 980                         Error ("LoadPortals: reading portal %i", i);\r
 981 \r
 982                 w = p->winding = NewFixedWinding (numpoints);\r
 983                 w->numpoints = numpoints;\r
 984                 \r
 985                 for (j=0 ; j<numpoints ; j++)\r
 986                 {\r
 987                         double  v[3];\r
 988                         int             k;\r
 989 \r
 990                         // scanf into double, then assign to vec_t\r
 991                         // so we don't care what size vec_t is\r
 992                         if (fscanf (f, "(%lf %lf %lf ) "\r
 993                         , &v[0], &v[1], &v[2]) != 3)\r
 994                                 Error ("LoadPortals: reading portal %i", i);\r
 995                         for (k=0 ; k<3 ; k++)\r
 996                                 w->points[j][k] = v[k];\r
 997                 }\r
 998                 fscanf (f, "\n");\r
 999                 \r
1000                 // calc plane\r
1001                 PlaneFromWinding (w, &plane);\r
1002 \r
1003                 l = &faceleafs[leafnums[0]];\r
1004                 l->merged = -1;\r
1005                 if (l->numportals == MAX_PORTALS_ON_LEAF)\r
1006                         Error ("Leaf with too many faces");\r
1007                 l->portals[l->numportals] = p;\r
1008                 l->numportals++;\r
1009                 \r
1010                 p->num = i+1;\r
1011                 p->winding = w;\r
1012                 // normal pointing out of the leaf\r
1013                 VectorSubtract (vec3_origin, plane.normal, p->plane.normal);\r
1014                 p->plane.dist = -plane.dist;\r
1015                 p->leaf = -1;\r
1016                 SetPortalSphere (p);\r
1017                 p++;\r
1018         }\r
1019         \r
1020         fclose (f);\r
1021 }\r
1022 \r
1023 \r
1024 \r
1025 /*\r
1026 ===========\r
1027 VisMain\r
1028 ===========\r
1029 */\r
1030 int VisMain (int argc, char **argv)\r
1031 {\r
1032         char            portalfile[1024];\r
1033         int                     i;\r
1034         \r
1035         \r
1036         /* note it */\r
1037         Sys_Printf( "--- Vis ---\n" );\r
1038         \r
1039         /* process arguments */\r
1040         for (i=1 ; i < (argc - 1) ; i++)\r
1041         {\r
1042                 if (!strcmp(argv[i], "-fast")) {\r
1043                         Sys_Printf ("fastvis = true\n");\r
1044                         fastvis = qtrue;\r
1045                 } else if (!strcmp(argv[i], "-merge")) {\r
1046                         Sys_Printf ("merge = true\n");\r
1047                         mergevis = qtrue;\r
1048                 } else if (!strcmp(argv[i], "-nopassage")) {\r
1049                         Sys_Printf ("nopassage = true\n");\r
1050                         noPassageVis = qtrue;\r
1051                 } else if (!strcmp(argv[i], "-passageOnly")) {\r
1052                         Sys_Printf ("passageOnly = true\n");\r
1053                         passageVisOnly = qtrue;\r
1054                 } else if (!strcmp (argv[i],"-nosort")) {\r
1055                         Sys_Printf ("nosort = true\n");\r
1056                         nosort = qtrue;\r
1057                 } else if (!strcmp (argv[i],"-saveprt")) {\r
1058                         Sys_Printf ("saveprt = true\n");\r
1059                         saveprt = qtrue;\r
1060                 } else if (!strcmp (argv[i],"-tmpin")) {\r
1061                         strcpy (inbase, "/tmp");\r
1062                 } else if (!strcmp (argv[i],"-tmpout")) {\r
1063                         strcpy (outbase, "/tmp");\r
1064                 }\r
1065                 \r
1066         \r
1067                 /* ydnar: -hint to merge all but hint portals */\r
1068                 else if( !strcmp( argv[ i ], "-hint" ) )\r
1069                 {\r
1070                         Sys_Printf( "hint = true\n" );\r
1071                         hint = qtrue;\r
1072                         mergevis = qtrue;\r
1073                 }\r
1074                 \r
1075                 else\r
1076                         Sys_Printf( "WARNING: Unknown option \"%s\"\n", argv[ i ] );\r
1077         }\r
1078 \r
1079         if( i != argc - 1 )\r
1080                 Error( "usage: vis [-threads #] [-level 0-4] [-fast] [-v] bspfile" );\r
1081         \r
1082 \r
1083         /* load the bsp */\r
1084         sprintf( source, "%s%s", inbase, ExpandArg( argv[ i ] ) );\r
1085         StripExtension( source );\r
1086         strcat( source, ".bsp" );\r
1087         Sys_Printf( "Loading %s\n", source );\r
1088         LoadBSPFile( source );\r
1089         \r
1090         /* load the portal file */\r
1091         sprintf( portalfile, "%s%s", inbase, ExpandArg( argv[ i ] ) );\r
1092         StripExtension( portalfile );\r
1093         strcat( portalfile, ".prt" );\r
1094         Sys_Printf( "Loading %s\n", portalfile );\r
1095         LoadPortals( portalfile );\r
1096         \r
1097         /* ydnar: for getting far plane */\r
1098         ParseEntities();\r
1099         \r
1100         if( mergevis )\r
1101         {\r
1102                 MergeLeaves();\r
1103                 MergeLeafPortals();\r
1104         }\r
1105         \r
1106         CountActivePortals();\r
1107         /* WritePortals( "maps/hints.prs" );*/\r
1108         \r
1109         Sys_Printf( "visdatasize:%i\n", numBSPVisBytes );\r
1110         \r
1111         CalcVis();\r
1112         \r
1113         /* delete the prt file */\r
1114         if( !saveprt )\r
1115                 remove( portalfile );\r
1116 \r
1117         /* write the bsp file */\r
1118         Sys_Printf( "Writing %s\n", source );\r
1119         WriteBSPFile( source );\r
1120 \r
1121         return 0;\r
1122 }\r