tools/quake2/q2map/qvis.c

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