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