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