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 ( (*(vportal_t **)a)->nummightsee == (*(vportal_t **)b)->nummightsee)
 106                 return 0;
 107         if ( (*(vportal_t **)a)->nummightsee < (*(vportal_t **)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;
 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         for(i = 0; i < MAX_MAP_LEAFS; ++i)
 365                 if(clustersizehistogram[i])
 366                 {
 367                         Sys_FPrintf(SYS_VRB, "%4i clusters have exactly %4i visible clusters\n", clustersizehistogram[i], i);
 368                         totalvis  += ((double) i)                * ((double) clustersizehistogram[i]);
 369                         totalvis2 += ((double) i) * ((double) i) * ((double) clustersizehistogram[i]);
 370                         /* cast is to prevent integer overflow */
 371                 }
 372
 373         mu = totalvis / portalclusters;
 374         sigma = sqrt(totalvis2 / portalclusters - mu * mu);
 375
 376   Sys_Printf( "Total clusters: %i\n", portalclusters );
 377   Sys_Printf( "Total visible clusters: %.0f\n", totalvis );
 378   Sys_Printf( "Average clusters visible: %.2f sdev=%.2f\n", mu, sigma);
 379 }
 380
 381 /*
 382 ==================
 383 SetPortalSphere
 384 ==================
 385 */
 386 void SetPortalSphere (vportal_t *p)
 387 {
 388         int             i;
 389         vec3_t  total, dist;
 390         fixedWinding_t  *w;
 391         float   r, bestr;
 392
 393         w = p->winding;
 394         VectorCopy (vec3_origin, total);
 395         for (i=0 ; i<w->numpoints ; i++)
 396         {
 397                 VectorAdd (total, w->points[i], total);
 398         }
 399
 400         for (i=0 ; i<3 ; i++)
 401                 total[i] /= w->numpoints;
 402
 403         bestr = 0;
 404         for (i=0 ; i<w->numpoints ; i++)
 405         {
 406                 VectorSubtract (w->points[i], total, dist);
 407                 r = VectorLength (dist);
 408                 if (r > bestr)
 409                         bestr = r;
 410         }
 411         VectorCopy (total, p->origin);
 412         p->radius = bestr;
 413 }
 414
 415 /*
 416 =============
 417 Winding_PlanesConcave
 418 =============
 419 */
 420 #define WCONVEX_EPSILON         0.2
 421
 422 int Winding_PlanesConcave(fixedWinding_t *w1, fixedWinding_t *w2,
 423                                                          vec3_t normal1, vec3_t normal2,
 424                                                          float dist1, float dist2)
 425 {
 426         int i;
 427
 428         if (!w1 || !w2) return qfalse;
 429
 430         // check if one of the points of winding 1 is at the front of the plane of winding 2
 431         for (i = 0; i < w1->numpoints; i++)
 432         {
 433                 if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return qtrue;
 434         }
 435         // check if one of the points of winding 2 is at the front of the plane of winding 1
 436         for (i = 0; i < w2->numpoints; i++)
 437         {
 438                 if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return qtrue;
 439         }
 440
 441         return qfalse;
 442 }
 443
 444 /*
 445 ============
 446 TryMergeLeaves
 447 ============
 448 */
 449 int TryMergeLeaves(int l1num, int l2num)
 450 {
 451         int i, j, k, n, numportals;
 452         visPlane_t plane1, plane2;
 453         leaf_t *l1, *l2;
 454         vportal_t *p1, *p2;
 455         vportal_t *portals[MAX_PORTALS_ON_LEAF];
 456
 457         for (k = 0; k < 2; k++)
 458         {
 459                 if (k) l1 = &leafs[l1num];
 460                 else l1 = &faceleafs[l1num];
 461                 for (i = 0; i < l1->numportals; i++)
 462                 {
 463                         p1 = l1->portals[i];
 464                         if (p1->leaf == l2num) continue;
 465                         for (n = 0; n < 2; n++)
 466                         {
 467                                 if (n) l2 = &leafs[l2num];
 468                                 else l2 = &faceleafs[l2num];
 469                                 for (j = 0; j < l2->numportals; j++)
 470                                 {
 471                                         p2 = l2->portals[j];
 472                                         if (p2->leaf == l1num) continue;
 473                                         //
 474                                         plane1 = p1->plane;
 475                                         plane2 = p2->plane;
 476                                         if (Winding_PlanesConcave(p1->winding, p2->winding, plane1.normal, plane2.normal, plane1.dist, plane2.dist))
 477                                                 return qfalse;
 478                                 }
 479                         }
 480                 }
 481         }
 482         for (k = 0; k < 2; k++)
 483         {
 484                 if (k)
 485                 {
 486                         l1 = &leafs[l1num];
 487                         l2 = &leafs[l2num];
 488                 }
 489                 else
 490                 {
 491                         l1 = &faceleafs[l1num];
 492                         l2 = &faceleafs[l2num];
 493                 }
 494                 numportals = 0;
 495                 //the leaves can be merged now
 496                 for (i = 0; i < l1->numportals; i++)
 497                 {
 498                         p1 = l1->portals[i];
 499                         if (p1->leaf == l2num)
 500                         {
 501                                 p1->removed = qtrue;
 502                                 continue;
 503                         }
 504                         portals[numportals++] = p1;
 505                 }
 506                 for (j = 0; j < l2->numportals; j++)
 507                 {
 508                         p2 = l2->portals[j];
 509                         if (p2->leaf == l1num)
 510                         {
 511                                 p2->removed = qtrue;
 512                                 continue;
 513                         }
 514                         portals[numportals++] = p2;
 515                 }
 516                 for (i = 0; i < numportals; i++)
 517                 {
 518                         l2->portals[i] = portals[i];
 519                 }
 520                 l2->numportals = numportals;
 521                 l1->merged = l2num;
 522         }
 523         return qtrue;
 524 }
 525
 526 /*
 527 ============
 528 UpdatePortals
 529 ============
 530 */
 531 void UpdatePortals(void)
 532 {
 533         int i;
 534         vportal_t *p;
 535
 536         for (i = 0; i < numportals * 2; i++)
 537         {
 538                 p = &portals[i];
 539                 if (p->removed)
 540                         continue;
 541                 while(leafs[p->leaf].merged >= 0)
 542                         p->leaf = leafs[p->leaf].merged;
 543         }
 544 }
 545
 546 /*
 547 ============
 548 MergeLeaves
 549
 550 try to merge leaves but don't merge through hint splitters
 551 ============
 552 */
 553 void MergeLeaves(void)
 554 {
 555         int i, j, nummerges, totalnummerges;
 556         leaf_t *leaf;
 557         vportal_t *p;
 558
 559         totalnummerges = 0;
 560         do
 561         {
 562                 nummerges = 0;
 563                 for (i = 0; i < portalclusters; i++)
 564                 {
 565                         leaf = &leafs[i];
 566                         //if this leaf is merged already
 567
 568                         /* ydnar: vmods: merge all non-hint portals */
 569                         if( leaf->merged >= 0 && hint == qfalse )
 570                                 continue;
 571
 572
 573                         for (j = 0; j < leaf->numportals; j++)
 574                         {
 575                                 p = leaf->portals[j];
 576                                 //
 577                                 if (p->removed)
 578                                         continue;
 579                                 //never merge through hint portals
 580                                 if (p->hint)
 581                                         continue;
 582                                 if (TryMergeLeaves(i, p->leaf))
 583                                 {
 584                                         UpdatePortals();
 585                                         nummerges++;
 586                                         break;
 587                                 }
 588                         }
 589                 }
 590                 totalnummerges += nummerges;
 591         } while (nummerges);
 592         Sys_Printf("%6d leaves merged\n", totalnummerges);
 593 }
 594
 595 /*
 596 ============
 597 TryMergeWinding
 598 ============
 599 */
 600 #define CONTINUOUS_EPSILON      0.005
 601
 602 fixedWinding_t *TryMergeWinding (fixedWinding_t *f1, fixedWinding_t *f2, vec3_t planenormal)
 603 {
 604         vec_t           *p1, *p2, *p3, *p4, *back;
 605         fixedWinding_t  *newf;
 606         int                     i, j, k, l;
 607         vec3_t          normal, delta;
 608         vec_t           dot;
 609         qboolean        keep1, keep2;
 610
 611
 612         //
 613         // find a common edge
 614         //
 615         p1 = p2 = NULL; // stop compiler warning
 616         j = 0;                  //
 617
 618         for (i = 0; i < f1->numpoints; i++)
 619         {
 620                 p1 = f1->points[i];
 621                 p2 = f1->points[(i+1) % f1->numpoints];
 622                 for (j = 0; j < f2->numpoints; j++)
 623                 {
 624                         p3 = f2->points[j];
 625                         p4 = f2->points[(j+1) % f2->numpoints];
 626                         for (k = 0; k < 3; k++)
 627                         {
 628                                 if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME
 629                                         break;
 630                                 if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME
 631                                         break;
 632                         } //end for
 633                         if (k==3)
 634                                 break;
 635                 } //end for
 636                 if (j < f2->numpoints)
 637                         break;
 638         } //end for
 639
 640         if (i == f1->numpoints)
 641                 return NULL;                    // no matching edges
 642
 643         //
 644         // check slope of connected lines
 645         // if the slopes are colinear, the point can be removed
 646         //
 647         back = f1->points[(i+f1->numpoints-1)%f1->numpoints];
 648         VectorSubtract (p1, back, delta);
 649         CrossProduct (planenormal, delta, normal);
 650         VectorNormalize (normal, normal);
 651
 652         back = f2->points[(j+2)%f2->numpoints];
 653         VectorSubtract (back, p1, delta);
 654         dot = DotProduct (delta, normal);
 655         if (dot > CONTINUOUS_EPSILON)
 656                 return NULL;                    // not a convex polygon
 657         keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
 658
 659         back = f1->points[(i+2)%f1->numpoints];
 660         VectorSubtract (back, p2, delta);
 661         CrossProduct (planenormal, delta, normal);
 662         VectorNormalize (normal, normal);
 663
 664         back = f2->points[(j+f2->numpoints-1)%f2->numpoints];
 665         VectorSubtract (back, p2, delta);
 666         dot = DotProduct (delta, normal);
 667         if (dot > CONTINUOUS_EPSILON)
 668                 return NULL;                    // not a convex polygon
 669         keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);
 670
 671         //
 672         // build the new polygon
 673         //
 674         newf = NewFixedWinding (f1->numpoints + f2->numpoints);
 675
 676         // copy first polygon
 677         for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
 678         {
 679                 if (k==(i+1)%f1->numpoints && !keep2)
 680                         continue;
 681
 682                 VectorCopy (f1->points[k], newf->points[newf->numpoints]);
 683                 newf->numpoints++;
 684         }
 685
 686         // copy second polygon
 687         for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
 688         {
 689                 if (l==(j+1)%f2->numpoints && !keep1)
 690                         continue;
 691                 VectorCopy (f2->points[l], newf->points[newf->numpoints]);
 692                 newf->numpoints++;
 693         }
 694
 695         return newf;
 696 }
 697
 698 /*
 699 ============
 700 MergeLeafPortals
 701 ============
 702 */
 703 void MergeLeafPortals(void)
 704 {
 705         int i, j, k, nummerges, hintsmerged;
 706         leaf_t *leaf;
 707         vportal_t *p1, *p2;
 708         fixedWinding_t *w;
 709
 710         nummerges = 0;
 711         hintsmerged = 0;
 712         for (i = 0; i < portalclusters; i++)
 713         {
 714                 leaf = &leafs[i];
 715                 if (leaf->merged >= 0) continue;
 716                 for (j = 0; j < leaf->numportals; j++)
 717                 {
 718                         p1 = leaf->portals[j];
 719                         if (p1->removed)
 720                                 continue;
 721                         for (k = j+1; k < leaf->numportals; k++)
 722                         {
 723                                 p2 = leaf->portals[k];
 724                                 if (p2->removed)
 725                                         continue;
 726                                 if (p1->leaf == p2->leaf)
 727                                 {
 728                                         w = TryMergeWinding(p1->winding, p2->winding, p1->plane.normal);
 729                                         if (w)
 730                                         {
 731                                                 free( p1->winding );    //% FreeWinding(p1->winding);
 732                                                 p1->winding = w;
 733                                                 if (p1->hint && p2->hint)
 734                                                         hintsmerged++;
 735                                                 p1->hint |= p2->hint;
 736                                                 SetPortalSphere(p1);
 737                                                 p2->removed = qtrue;
 738                                                 nummerges++;
 739                                                 i--;
 740                                                 break;
 741                                         }
 742                                 }
 743                         }
 744                         if (k < leaf->numportals)
 745                                 break;
 746                 }
 747         }
 748         Sys_Printf("%6d portals merged\n", nummerges);
 749         Sys_Printf("%6d hint portals merged\n", hintsmerged);
 750 }
 751
 752
 753 /*
 754 ============
 755 WritePortals
 756 ============
 757 */
 758 int CountActivePortals(void)
 759 {
 760         int num, hints, j;
 761         vportal_t *p;
 762
 763         num = 0;
 764         hints = 0;
 765         for (j = 0; j < numportals * 2; j++)
 766         {
 767                 p = portals + j;
 768                 if (p->removed)
 769                         continue;
 770                 if (p->hint)
 771                         hints++;
 772                 num++;
 773         }
 774         Sys_Printf("%6d active portals\n", num);
 775         Sys_Printf("%6d hint portals\n", hints);
 776         return num;
 777 }
 778
 779 /*
 780 ============
 781 WritePortals
 782 ============
 783 */
 784 void WriteFloat (FILE *f, vec_t v);
 785
 786 void WritePortals(char *filename)
 787 {
 788         int i, j, num;
 789         FILE *pf;
 790         vportal_t *p;
 791         fixedWinding_t *w;
 792
 793         // write the file
 794         pf = fopen (filename, "w");
 795         if (!pf)
 796                 Error ("Error opening %s", filename);
 797
 798         num = 0;
 799         for (j = 0; j < numportals * 2; j++)
 800         {
 801                 p = portals + j;
 802                 if (p->removed)
 803                         continue;
 804 //              if (!p->hint)
 805 //                      continue;
 806                 num++;
 807         }
 808
 809         fprintf (pf, "%s\n", PORTALFILE);
 810         fprintf (pf, "%i\n", 0);
 811         fprintf (pf, "%i\n", num);// + numfaces);
 812         fprintf (pf, "%i\n", 0);
 813
 814         for (j = 0; j < numportals * 2; j++)
 815         {
 816                 p = portals + j;
 817                 if (p->removed)
 818                         continue;
 819 //              if (!p->hint)
 820 //                      continue;
 821                 w = p->winding;
 822                 fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);
 823                 fprintf (pf, "%d ", p->hint);
 824                 for (i=0 ; i<w->numpoints ; i++)
 825                 {
 826                         fprintf (pf,"(");
 827                         WriteFloat (pf, w->points[i][0]);
 828                         WriteFloat (pf, w->points[i][1]);
 829                         WriteFloat (pf, w->points[i][2]);
 830                         fprintf (pf,") ");
 831                 }
 832                 fprintf (pf,"\n");
 833         }
 834
 835         /*
 836         for (j = 0; j < numfaces; j++)
 837         {
 838                 p = faces + j;
 839                 w = p->winding;
 840                 fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);
 841                 fprintf (pf, "0 ");
 842                 for (i=0 ; i<w->numpoints ; i++)
 843                 {
 844                         fprintf (pf,"(");
 845                         WriteFloat (pf, w->points[i][0]);
 846                         WriteFloat (pf, w->points[i][1]);
 847                         WriteFloat (pf, w->points[i][2]);
 848                         fprintf (pf,") ");
 849                 }
 850                 fprintf (pf,"\n");
 851         }*/
 852
 853         fclose (pf);
 854 }
 855
 856 /*
 857 ============
 858 LoadPortals
 859 ============
 860 */
 861 void LoadPortals (char *name)
 862 {
 863         int                     i, j, hint;
 864         vportal_t       *p;
 865         leaf_t          *l;
 866         char            magic[80];
 867         FILE            *f;
 868         int                     numpoints;
 869         fixedWinding_t  *w;
 870         int                     leafnums[2];
 871         visPlane_t      plane;
 872
 873         if (!strcmp(name,"-"))
 874                 f = stdin;
 875         else
 876         {
 877                 f = fopen(name, "r");
 878                 if (!f)
 879                         Error ("LoadPortals: couldn't read %s\n",name);
 880         }
 881
 882         if (fscanf (f,"%79s\n%i\n%i\n%i\n",magic, &portalclusters, &numportals, &numfaces) != 4)
 883                 Error ("LoadPortals: failed to read header");
 884         if (strcmp(magic,PORTALFILE))
 885                 Error ("LoadPortals: not a portal file");
 886
 887         Sys_Printf ("%6i portalclusters\n", portalclusters);
 888         Sys_Printf ("%6i numportals\n", numportals);
 889         Sys_Printf ("%6i numfaces\n", numfaces);
 890
 891         // these counts should take advantage of 64 bit systems automatically
 892         leafbytes = ((portalclusters+63)&~63)>>3;
 893         leaflongs = leafbytes/sizeof(long);
 894
 895         portalbytes = ((numportals*2+63)&~63)>>3;
 896         portallongs = portalbytes/sizeof(long);
 897
 898         // each file portal is split into two memory portals
 899         portals = safe_malloc(2*numportals*sizeof(vportal_t));
 900         memset (portals, 0, 2*numportals*sizeof(vportal_t));
 901
 902         leafs = safe_malloc(portalclusters*sizeof(leaf_t));
 903         memset (leafs, 0, portalclusters*sizeof(leaf_t));
 904
 905         for (i = 0; i < portalclusters; i++)
 906                 leafs[i].merged = -1;
 907
 908         numBSPVisBytes = VIS_HEADER_SIZE + portalclusters*leafbytes;
 909
 910         if (numBSPVisBytes > MAX_MAP_VISIBILITY)
 911           Error("MAX_MAP_VISIBILITY exceeded");
 912
 913         ((int *)bspVisBytes)[0] = portalclusters;
 914         ((int *)bspVisBytes)[1] = leafbytes;
 915
 916         for (i=0, p=portals ; i<numportals ; i++)
 917         {
 918                 if (fscanf (f, "%i %i %i ", &numpoints, &leafnums[0], &leafnums[1]) != 3)
 919                         Error ("LoadPortals: reading portal %i", i);
 920                 if (numpoints > MAX_POINTS_ON_WINDING)
 921                         Error ("LoadPortals: portal %i has too many points", i);
 922                 if ( (unsigned)leafnums[0] > portalclusters
 923                 || (unsigned)leafnums[1] > portalclusters)
 924                         Error ("LoadPortals: reading portal %i", i);
 925                 if (fscanf (f, "%i ", &hint) != 1)
 926                         Error ("LoadPortals: reading hint state");
 927
 928                 w = p->winding = NewFixedWinding (numpoints);
 929                 w->numpoints = numpoints;
 930
 931                 for (j=0 ; j<numpoints ; j++)
 932                 {
 933                         double  v[3];
 934                         int             k;
 935
 936                         // scanf into double, then assign to vec_t
 937                         // so we don't care what size vec_t is
 938                         if (fscanf (f, "(%lf %lf %lf ) "
 939                         , &v[0], &v[1], &v[2]) != 3)
 940                                 Error ("LoadPortals: reading portal %i", i);
 941                         for (k=0 ; k<3 ; k++)
 942                                 w->points[j][k] = v[k];
 943                 }
 944                 fscanf (f, "\n");
 945
 946                 // calc plane
 947                 PlaneFromWinding (w, &plane);
 948
 949                 // create forward portal
 950                 l = &leafs[leafnums[0]];
 951                 if (l->numportals == MAX_PORTALS_ON_LEAF)
 952                         Error ("Leaf with too many portals");
 953                 l->portals[l->numportals] = p;
 954                 l->numportals++;
 955
 956                 p->num = i+1;
 957                 p->hint = hint;
 958                 p->winding = w;
 959                 VectorSubtract (vec3_origin, plane.normal, p->plane.normal);
 960                 p->plane.dist = -plane.dist;
 961                 p->leaf = leafnums[1];
 962                 SetPortalSphere (p);
 963                 p++;
 964
 965                 // create backwards portal
 966                 l = &leafs[leafnums[1]];
 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 = NewFixedWinding(w->numpoints);
 975                 p->winding->numpoints = w->numpoints;
 976                 for (j=0 ; j<w->numpoints ; j++)
 977                 {
 978                         VectorCopy (w->points[w->numpoints-1-j], p->winding->points[j]);
 979                 }
 980
 981                 p->plane = plane;
 982                 p->leaf = leafnums[0];
 983                 SetPortalSphere (p);
 984                 p++;
 985
 986         }
 987
 988         faces = safe_malloc(2*numfaces*sizeof(vportal_t));
 989         memset (faces, 0, 2*numfaces*sizeof(vportal_t));
 990
 991         faceleafs = safe_malloc(portalclusters*sizeof(leaf_t));
 992         memset(faceleafs, 0, portalclusters*sizeof(leaf_t));
 993
 994         for (i = 0, p = faces; i < numfaces; i++)
 995         {
 996                 if (fscanf (f, "%i %i ", &numpoints, &leafnums[0]) != 2)
 997                         Error ("LoadPortals: reading portal %i", i);
 998
 999                 w = p->winding = NewFixedWinding (numpoints);
1000                 w->numpoints = numpoints;
1001
1002                 for (j=0 ; j<numpoints ; j++)
1003                 {
1004                         double  v[3];
1005                         int             k;
1006
1007                         // scanf into double, then assign to vec_t
1008                         // so we don't care what size vec_t is
1009                         if (fscanf (f, "(%lf %lf %lf ) "
1010                         , &v[0], &v[1], &v[2]) != 3)
1011                                 Error ("LoadPortals: reading portal %i", i);
1012                         for (k=0 ; k<3 ; k++)
1013                                 w->points[j][k] = v[k];
1014                 }
1015                 fscanf (f, "\n");
1016
1017                 // calc plane
1018                 PlaneFromWinding (w, &plane);
1019
1020                 l = &faceleafs[leafnums[0]];
1021                 l->merged = -1;
1022                 if (l->numportals == MAX_PORTALS_ON_LEAF)
1023                         Error ("Leaf with too many faces");
1024                 l->portals[l->numportals] = p;
1025                 l->numportals++;
1026
1027                 p->num = i+1;
1028                 p->winding = w;
1029                 // normal pointing out of the leaf
1030                 VectorSubtract (vec3_origin, plane.normal, p->plane.normal);
1031                 p->plane.dist = -plane.dist;
1032                 p->leaf = -1;
1033                 SetPortalSphere (p);
1034                 p++;
1035         }
1036
1037         fclose (f);
1038 }
1039
1040
1041
1042 /*
1043 ===========
1044 VisMain
1045 ===========
1046 */
1047 int VisMain (int argc, char **argv)
1048 {
1049         char            portalfile[1024];
1050         int                     i;
1051
1052
1053         /* note it */
1054         Sys_Printf( "--- Vis ---\n" );
1055
1056         /* process arguments */
1057         for (i=1 ; i < (argc - 1) ; i++)
1058         {
1059                 if (!strcmp(argv[i], "-fast")) {
1060                         Sys_Printf ("fastvis = true\n");
1061                         fastvis = qtrue;
1062                 } else if (!strcmp(argv[i], "-merge")) {
1063                         Sys_Printf ("merge = true\n");
1064                         mergevis = qtrue;
1065                 } else if (!strcmp(argv[i], "-mergeportals")) {
1066                         Sys_Printf ("mergeportals = true\n");
1067                         mergevisportals = qtrue;
1068                 } else if (!strcmp(argv[i], "-nopassage")) {
1069                         Sys_Printf ("nopassage = true\n");
1070                         noPassageVis = qtrue;
1071                 } else if (!strcmp(argv[i], "-passageOnly")) {
1072                         Sys_Printf ("passageOnly = true\n");
1073                         passageVisOnly = qtrue;
1074                 } else if (!strcmp (argv[i],"-nosort")) {
1075                         Sys_Printf ("nosort = true\n");
1076                         nosort = qtrue;
1077                 } else if (!strcmp (argv[i],"-saveprt")) {
1078                         Sys_Printf ("saveprt = true\n");
1079                         saveprt = qtrue;
1080                 } else if (!strcmp (argv[i],"-tmpin")) {
1081                         strcpy (inbase, "/tmp");
1082                 } else if (!strcmp (argv[i],"-tmpout")) {
1083                         strcpy (outbase, "/tmp");
1084                 }
1085
1086
1087                 /* ydnar: -hint to merge all but hint portals */
1088                 else if( !strcmp( argv[ i ], "-hint" ) )
1089                 {
1090                         Sys_Printf( "hint = true\n" );
1091                         hint = qtrue;
1092                         mergevis = qtrue;
1093                 }
1094
1095                 else
1096                 {
1097                         Sys_Printf( "WARNING: Unknown option \"%s\"\n", argv[ i ] );
1098                 }
1099         }
1100
1101         if( i != argc - 1 )
1102                 Error( "usage: vis [-threads #] [-level 0-4] [-fast] [-v] bspfile" );
1103
1104
1105         /* load the bsp */
1106         sprintf( source, "%s%s", inbase, ExpandArg( argv[ i ] ) );
1107         StripExtension( source );
1108         strcat( source, ".bsp" );
1109         Sys_Printf( "Loading %s\n", source );
1110         LoadBSPFile( source );
1111
1112         /* load the portal file */
1113         sprintf( portalfile, "%s%s", inbase, ExpandArg( argv[ i ] ) );
1114         StripExtension( portalfile );
1115         strcat( portalfile, ".prt" );
1116         Sys_Printf( "Loading %s\n", portalfile );
1117         LoadPortals( portalfile );
1118
1119         /* ydnar: exit if no portals, hence no vis */
1120         if( numportals == 0 )
1121         {
1122                 Sys_Printf( "No portals means no vis, exiting.\n" );
1123                 return 0;
1124         }
1125
1126         /* ydnar: for getting far plane */
1127         ParseEntities();
1128
1129         /* inject command line parameters */
1130         InjectCommandLine(argv, 0, argc - 1);
1131         UnparseEntities();
1132
1133         if( mergevis )
1134                 MergeLeaves();
1135
1136         if( mergevis || mergevisportals )
1137                 MergeLeafPortals();
1138
1139         CountActivePortals();
1140         /* WritePortals( "maps/hints.prs" );*/
1141
1142         Sys_Printf( "visdatasize:%i\n", numBSPVisBytes );
1143
1144         CalcVis();
1145
1146         /* delete the prt file */
1147         if( !saveprt )
1148                 remove( portalfile );
1149
1150         /* write the bsp file */
1151         Sys_Printf( "Writing %s\n", source );
1152         WriteBSPFile( source );
1153
1154         return 0;
1155 }