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