tools/quake2/q2map/qvis.c

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