tools/quake2/q2map/qvis.c

   1 /*
   2    Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3    For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5    This file is part of GtkRadiant.
   6
   7    GtkRadiant is free software; you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 2 of the License, or
  10    (at your option) any later version.
  11
  12    GtkRadiant is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with GtkRadiant; if not, write to the Free Software
  19    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20  */
  21 // qvis.c
  22
  23 #include "qvis.h"
  24 #include "q2_threads.h"
  25 #include "stdlib.h"
  26
  27 int numportals;
  28 int portalclusters;
  29
  30 char inbase[32];
  31 char outbase[32];
  32
  33 portal_t    *portals;
  34 leaf_t      *leafs;
  35
  36 int c_portaltest, c_portalpass, c_portalcheck;
  37
  38 byte        *uncompressedvis;
  39
  40 byte    *vismap, *vismap_p, *vismap_end;    // past visfile
  41 int originalvismapsize;
  42
  43 int leafbytes;                  // (portalclusters+63)>>3
  44 int leaflongs;
  45
  46 int portalbytes, portallongs;
  47
  48 qboolean fastvis;
  49 qboolean nosort;
  50
  51 int testlevel = 2;
  52
  53 int totalvis;
  54
  55 portal_t    *sorted_portals[MAX_MAP_PORTALS * 2];
  56
  57
  58 //=============================================================================
  59
  60 void PlaneFromWinding( winding_t *w, plane_t *plane ){
  61         vec3_t v1, v2;
  62
  63 // calc plane
  64         VectorSubtract( w->points[2], w->points[1], v1 );
  65         VectorSubtract( w->points[0], w->points[1], v2 );
  66         CrossProduct( v2, v1, plane->normal );
  67         VectorNormalize( plane->normal, plane->normal );
  68         plane->dist = DotProduct( w->points[0], plane->normal );
  69 }
  70
  71
  72 /*
  73    ==================
  74    NewWinding
  75    ==================
  76  */
  77 winding_t *NewWinding( int points ){
  78         winding_t   *w;
  79         int size;
  80
  81         if ( points > MAX_POINTS_ON_WINDING ) {
  82                 Error( "NewWinding: %i points", points );
  83         }
  84
  85         size = (int)( (winding_t *)0 )->points[points];
  86         w = malloc( size );
  87         memset( w, 0, size );
  88
  89         return w;
  90 }
  91
  92
  93 /*
  94    void pw(winding_t *w)
  95    {
  96     int         i;
  97     for (i=0 ; i<w->numpoints ; i++)
  98         Sys_Printf ("(%5.1f, %5.1f, %5.1f)\n",w->points[i][0], w->points[i][1],w->points[i][2]);
  99    }
 100  */
 101 void prl( leaf_t *l ){
 102         int i;
 103         portal_t    *p;
 104         plane_t pl;
 105
 106         for ( i = 0 ; i < l->numportals ; i++ )
 107         {
 108                 p = l->portals[i];
 109                 pl = p->plane;
 110                 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] );
 111         }
 112 }
 113
 114
 115 //=============================================================================
 116
 117 /*
 118    =============
 119    SortPortals
 120
 121    Sorts the portals from the least complex, so the later ones can reuse
 122    the earlier information.
 123    =============
 124  */
 125 int PComp( const void *a, const void *b ){
 126         if ( ( *(portal_t **)a )->nummightsee == ( *(portal_t **)b )->nummightsee ) {
 127                 return 0;
 128         }
 129         if ( ( *(portal_t **)a )->nummightsee < ( *(portal_t **)b )->nummightsee ) {
 130                 return -1;
 131         }
 132         return 1;
 133 }
 134 void SortPortals( void ){
 135         int i;
 136
 137         for ( i = 0 ; i < numportals * 2 ; i++ )
 138                 sorted_portals[i] = &portals[i];
 139
 140         if ( nosort ) {
 141                 return;
 142         }
 143         qsort( sorted_portals, numportals * 2, sizeof( sorted_portals[0] ), PComp );
 144 }
 145
 146
 147 /*
 148    ==============
 149    LeafVectorFromPortalVector
 150    ==============
 151  */
 152 int LeafVectorFromPortalVector( byte *portalbits, byte *leafbits ){
 153         int i;
 154         portal_t    *p;
 155         int c_leafs;
 156
 157
 158         memset( leafbits, 0, leafbytes );
 159
 160         for ( i = 0 ; i < numportals * 2 ; i++ )
 161         {
 162                 if ( portalbits[i >> 3] & ( 1 << ( i & 7 ) ) ) {
 163                         p = portals + i;
 164                         leafbits[p->leaf >> 3] |= ( 1 << ( p->leaf & 7 ) );
 165                 }
 166         }
 167
 168         c_leafs = CountBits( leafbits, portalclusters );
 169
 170         return c_leafs;
 171 }
 172
 173
 174 /*
 175    ===============
 176    ClusterMerge
 177
 178    Merges the portal visibility for a leaf
 179    ===============
 180  */
 181 void ClusterMerge( int leafnum ){
 182         leaf_t      *leaf;
 183         byte portalvector[MAX_PORTALS / 8];
 184         byte uncompressed[MAX_MAP_LEAFS / 8];
 185         byte compressed[MAX_MAP_LEAFS / 8];
 186         int i, j;
 187         int numvis;
 188         byte        *dest;
 189         portal_t    *p;
 190         int pnum;
 191
 192         // OR together all the portalvis bits
 193
 194         memset( portalvector, 0, portalbytes );
 195         leaf = &leafs[leafnum];
 196         for ( i = 0 ; i < leaf->numportals ; i++ )
 197         {
 198                 p = leaf->portals[i];
 199                 if ( p->status != stat_done ) {
 200                         Error( "portal not done" );
 201                 }
 202                 for ( j = 0 ; j < portallongs ; j++ )
 203                         ( (long *)portalvector )[j] |= ( (long *)p->portalvis )[j];
 204                 pnum = p - portals;
 205                 portalvector[pnum >> 3] |= 1 << ( pnum & 7 );
 206         }
 207
 208         // convert portal bits to leaf bits
 209         numvis = LeafVectorFromPortalVector( portalvector, uncompressed );
 210
 211         if ( uncompressed[leafnum >> 3] & ( 1 << ( leafnum & 7 ) ) ) {
 212                 Sys_FPrintf( SYS_WRN, "WARNING: Leaf portals saw into leaf\n" );
 213         }
 214
 215         uncompressed[leafnum >> 3] |= ( 1 << ( leafnum & 7 ) );
 216         numvis++;       // count the leaf itself
 217
 218         // save uncompressed for PHS calculation
 219         memcpy( uncompressedvis + leafnum * leafbytes, uncompressed, leafbytes );
 220
 221 //
 222 // compress the bit string
 223 //
 224         Sys_FPrintf( SYS_VRB, "cluster %4i : %4i visible\n", leafnum, numvis );
 225         totalvis += numvis;
 226
 227         i = CompressVis( uncompressed, compressed );
 228
 229         dest = vismap_p;
 230         vismap_p += i;
 231
 232         if ( vismap_p > vismap_end ) {
 233                 Error( "Vismap expansion overflow" );
 234         }
 235
 236         dvis->bitofs[leafnum][DVIS_PVS] = dest - vismap;
 237
 238         memcpy( dest, compressed, i );
 239 }
 240
 241
 242 /*
 243    ==================
 244    CalcPortalVis
 245    ==================
 246  */
 247 void CalcPortalVis( void ){
 248         int i;
 249
 250 // fastvis just uses mightsee for a very loose bound
 251         if ( fastvis ) {
 252                 for ( i = 0 ; i < numportals * 2 ; i++ )
 253                 {
 254                         portals[i].portalvis = portals[i].portalflood;
 255                         portals[i].status = stat_done;
 256                 }
 257                 return;
 258         }
 259
 260         RunThreadsOnIndividual( numportals * 2, true, PortalFlow );
 261
 262 }
 263
 264
 265 /*
 266    ==================
 267    CalcVis
 268    ==================
 269  */
 270 void CalcVis( void ){
 271         int i;
 272
 273         RunThreadsOnIndividual( numportals * 2, true, BasePortalVis );
 274
 275 //      RunThreadsOnIndividual (numportals*2, true, BetterPortalVis);
 276
 277         SortPortals();
 278
 279         CalcPortalVis();
 280
 281 //
 282 // assemble the leaf vis lists by oring and compressing the portal lists
 283 //
 284         for ( i = 0 ; i < portalclusters ; i++ )
 285                 ClusterMerge( i );
 286
 287         Sys_Printf( "Average clusters visible: %i\n", totalvis / portalclusters );
 288 }
 289
 290
 291 void SetPortalSphere( portal_t *p ){
 292         int i;
 293         vec3_t total, dist;
 294         winding_t   *w;
 295         float r, bestr;
 296
 297         w = p->winding;
 298         VectorCopy( vec3_origin, total );
 299         for ( i = 0 ; i < w->numpoints ; i++ )
 300         {
 301                 VectorAdd( total, w->points[i], total );
 302         }
 303
 304         for ( i = 0 ; i < 3 ; i++ )
 305                 total[i] /= w->numpoints;
 306
 307         bestr = 0;
 308         for ( i = 0 ; i < w->numpoints ; i++ )
 309         {
 310                 VectorSubtract( w->points[i], total, dist );
 311                 r = VectorLength( dist );
 312                 if ( r > bestr ) {
 313                         bestr = r;
 314                 }
 315         }
 316         VectorCopy( total, p->origin );
 317         p->radius = bestr;
 318 }
 319
 320 /*
 321    ============
 322    LoadPortals
 323    ============
 324  */
 325 void LoadPortals( char *name ){
 326         int i, j;
 327         portal_t    *p;
 328         leaf_t      *l;
 329         char magic[80];
 330         FILE        *f;
 331         int numpoints;
 332         winding_t   *w;
 333         int leafnums[2];
 334         plane_t plane;
 335
 336         if ( !strcmp( name,"-" ) ) {
 337                 f = stdin;
 338         }
 339         else
 340         {
 341                 f = fopen( name, "r" );
 342                 if ( !f ) {
 343                         Error( "LoadPortals: couldn't read %s\n",name );
 344                 }
 345         }
 346
 347         if ( fscanf( f,"%79s\n%i\n%i\n",magic, &portalclusters, &numportals ) != 3 ) {
 348                 Error( "LoadPortals: failed to read header" );
 349         }
 350         if ( strcmp( magic,PORTALFILE ) ) {
 351                 Error( "LoadPortals: not a portal file" );
 352         }
 353
 354         Sys_Printf( "%4i portalclusters\n", portalclusters );
 355         Sys_Printf( "%4i numportals\n", numportals );
 356
 357         // these counts should take advantage of 64 bit systems automatically
 358         leafbytes = ( ( portalclusters + 63 ) & ~63 ) >> 3;
 359         leaflongs = leafbytes / sizeof( long );
 360
 361         portalbytes = ( ( numportals * 2 + 63 ) & ~63 ) >> 3;
 362         portallongs = portalbytes / sizeof( long );
 363
 364 // each file portal is split into two memory portals
 365         portals = malloc( 2 * numportals * sizeof( portal_t ) );
 366         memset( portals, 0, 2 * numportals * sizeof( portal_t ) );
 367
 368         leafs = malloc( portalclusters * sizeof( leaf_t ) );
 369         memset( leafs, 0, portalclusters * sizeof( leaf_t ) );
 370
 371         originalvismapsize = portalclusters * leafbytes;
 372         uncompressedvis = malloc( originalvismapsize );
 373
 374         vismap = vismap_p = dvisdata;
 375         dvis->numclusters = portalclusters;
 376         vismap_p = (byte *)&dvis->bitofs[portalclusters];
 377
 378         vismap_end = vismap + MAX_MAP_VISIBILITY;
 379
 380         for ( i = 0, p = portals ; i < numportals ; i++ )
 381         {
 382                 if ( fscanf( f, "%i %i %i ", &numpoints, &leafnums[0], &leafnums[1] )
 383                          != 3 ) {
 384                         Error( "LoadPortals: reading portal %i", i );
 385                 }
 386                 if ( numpoints > MAX_POINTS_ON_WINDING ) {
 387                         Error( "LoadPortals: portal %i has too many points", i );
 388                 }
 389                 if ( (unsigned)leafnums[0] > portalclusters
 390                          || (unsigned)leafnums[1] > portalclusters ) {
 391                         Error( "LoadPortals: reading portal %i", i );
 392                 }
 393
 394                 w = p->winding = NewWinding( numpoints );
 395                 w->original = true;
 396                 w->numpoints = numpoints;
 397
 398                 for ( j = 0 ; j < numpoints ; j++ )
 399                 {
 400                         double v[3];
 401                         int k;
 402
 403                         // scanf into double, then assign to vec_t
 404                         // so we don't care what size vec_t is
 405                         if ( fscanf( f, "(%lf %lf %lf ) "
 406                                                  , &v[0], &v[1], &v[2] ) != 3 ) {
 407                                 Error( "LoadPortals: reading portal %i", i );
 408                         }
 409                         for ( k = 0 ; k < 3 ; k++ )
 410                                 w->points[j][k] = v[k];
 411                 }
 412                 fscanf( f, "\n" );
 413
 414                 // calc plane
 415                 PlaneFromWinding( w, &plane );
 416
 417                 // create forward portal
 418                 l = &leafs[leafnums[0]];
 419                 if ( l->numportals == MAX_PORTALS_ON_LEAF ) {
 420                         Error( "Leaf with too many portals" );
 421                 }
 422                 l->portals[l->numportals] = p;
 423                 l->numportals++;
 424
 425                 p->winding = w;
 426                 VectorSubtract( vec3_origin, plane.normal, p->plane.normal );
 427                 p->plane.dist = -plane.dist;
 428                 p->leaf = leafnums[1];
 429                 SetPortalSphere( p );
 430                 p++;
 431
 432                 // create backwards portal
 433                 l = &leafs[leafnums[1]];
 434                 if ( l->numportals == MAX_PORTALS_ON_LEAF ) {
 435                         Error( "Leaf with too many portals" );
 436                 }
 437                 l->portals[l->numportals] = p;
 438                 l->numportals++;
 439
 440                 p->winding = NewWinding( w->numpoints );
 441                 p->winding->numpoints = w->numpoints;
 442                 for ( j = 0 ; j < w->numpoints ; j++ )
 443                 {
 444                         VectorCopy( w->points[w->numpoints - 1 - j], p->winding->points[j] );
 445                 }
 446
 447                 p->plane = plane;
 448                 p->leaf = leafnums[0];
 449                 SetPortalSphere( p );
 450                 p++;
 451
 452         }
 453
 454         fclose( f );
 455 }
 456
 457
 458 /*
 459    ================
 460    CalcPHS
 461
 462    Calculate the PHS (Potentially Hearable Set)
 463    by ORing together all the PVS visible from a leaf
 464    ================
 465  */
 466 void CalcPHS( void ){
 467         int i, j, k, l, index;
 468         int bitbyte;
 469         long    *dest, *src;
 470         byte    *scan;
 471         int count;
 472         byte uncompressed[MAX_MAP_LEAFS / 8];
 473         byte compressed[MAX_MAP_LEAFS / 8];
 474
 475         Sys_Printf( "Building PHS...\n" );
 476
 477         count = 0;
 478         for ( i = 0 ; i < portalclusters ; i++ )
 479         {
 480                 scan = uncompressedvis + i * leafbytes;
 481                 memcpy( uncompressed, scan, leafbytes );
 482                 for ( j = 0 ; j < leafbytes ; j++ )
 483                 {
 484                         bitbyte = scan[j];
 485                         if ( !bitbyte ) {
 486                                 continue;
 487                         }
 488                         for ( k = 0 ; k < 8 ; k++ )
 489                         {
 490                                 if ( !( bitbyte & ( 1 << k ) ) ) {
 491                                         continue;
 492                                 }
 493                                 // OR this pvs row into the phs
 494                                 index = ( ( j << 3 ) + k );
 495                                 if ( index >= portalclusters ) {
 496                                         Error( "Bad bit in PVS" );   // pad bits should be 0
 497                                 }
 498                                 src = (long *)( uncompressedvis + index * leafbytes );
 499                                 dest = (long *)uncompressed;
 500                                 for ( l = 0 ; l < leaflongs ; l++ )
 501                                         ( (long *)uncompressed )[l] |= src[l];
 502                         }
 503                 }
 504                 for ( j = 0 ; j < portalclusters ; j++ )
 505                         if ( uncompressed[j >> 3] & ( 1 << ( j & 7 ) ) ) {
 506                                 count++;
 507                         }
 508
 509                 //
 510                 // compress the bit string
 511                 //
 512                 j = CompressVis( uncompressed, compressed );
 513
 514                 dest = (long *)vismap_p;
 515                 vismap_p += j;
 516
 517                 if ( vismap_p > vismap_end ) {
 518                         Error( "Vismap expansion overflow" );
 519                 }
 520
 521                 dvis->bitofs[i][DVIS_PHS] = (byte *)dest - vismap;
 522
 523                 memcpy( dest, compressed, j );
 524         }
 525
 526         Sys_Printf( "Average clusters hearable: %i\n", count / portalclusters );
 527 }
 528
 529 /*
 530    ===========
 531    main
 532    ===========
 533  */
 534 int VIS_Main(){
 535         char portalfile[1024];
 536         char source[1024];
 537         char name[1024];
 538         double start, end;
 539         int total_vis_time;
 540
 541         Sys_Printf( "\n----- VIS ----\n\n" );
 542
 543         //if (i != argc - 1)
 544         //      Error ("usage: vis [-threads #] [-level 0-4] [-fast] [-v] bspfile");
 545
 546         start = I_FloatTime();
 547
 548         ThreadSetDefault();
 549
 550         SetQdirFromPath( mapname );
 551         strcpy( source, ExpandArg( mapname ) );
 552         StripExtension( source );
 553         DefaultExtension( source, ".bsp" );
 554
 555         sprintf( name, "%s%s", inbase, source );
 556         Sys_Printf( "reading %s\n", name );
 557         LoadBSPFile( name );
 558         if ( numnodes == 0 || numfaces == 0 ) {
 559                 Error( "Empty map" );
 560         }
 561
 562         sprintf( portalfile, "%s%s", inbase, ExpandArg( mapname ) );
 563         StripExtension( portalfile );
 564         strcat( portalfile, ".prt" );
 565
 566         Sys_Printf( "reading %s\n", portalfile );
 567         LoadPortals( portalfile );
 568
 569         CalcVis();
 570
 571         CalcPHS();
 572
 573         visdatasize = vismap_p - dvisdata;
 574         Sys_Printf( "visdatasize:%i  compressed from %i\n", visdatasize, originalvismapsize * 2 );
 575
 576         sprintf( name, "%s%s", outbase, source );
 577         Sys_Printf( "writing %s\n", name );
 578         WriteBSPFile( name );
 579
 580         end = I_FloatTime();
 581         total_vis_time = (int) ( end - start );
 582         Sys_Printf( "\nVIS Time: " );
 583         if ( total_vis_time > 59 ) {
 584                 Sys_Printf( "%d Minutes ", total_vis_time / 60 );
 585         }
 586         Sys_Printf( "%d Seconds\n", total_vis_time % 60 );
 587
 588
 589         return 0;
 590 }