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