tools/quake3/q3map2/vis.c

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