2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
3 For a list of contributors, see the accompanying CONTRIBUTORS file.
5 This file is part of GtkRadiant.
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.
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.
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
24 #include "q2_threads.h"
36 int c_portaltest, c_portalpass, c_portalcheck;
38 byte *uncompressedvis;
40 byte *vismap, *vismap_p, *vismap_end; // past visfile
41 int originalvismapsize;
43 int leafbytes; // (portalclusters+63)>>3
46 int portalbytes, portallongs;
55 portal_t *sorted_portals[MAX_MAP_PORTALS * 2];
58 //=============================================================================
60 void PlaneFromWinding( winding_t *w, plane_t *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 );
77 winding_t *NewWinding( int points ){
81 if ( points > MAX_POINTS_ON_WINDING ) {
82 Error( "NewWinding: %i points", points );
85 size = (int)( (winding_t *)0 )->points[points];
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]);
101 void prl( leaf_t *l ){
106 for ( i = 0 ; i < l->numportals ; i++ )
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] );
115 //=============================================================================
121 Sorts the portals from the least complex, so the later ones can reuse
122 the earlier information.
125 int PComp( const void *a, const void *b ){
126 if ( ( *(portal_t **)a )->nummightsee == ( *(portal_t **)b )->nummightsee ) {
129 if ( ( *(portal_t **)a )->nummightsee < ( *(portal_t **)b )->nummightsee ) {
134 void SortPortals( void ){
137 for ( i = 0 ; i < numportals * 2 ; i++ )
138 sorted_portals[i] = &portals[i];
143 qsort( sorted_portals, numportals * 2, sizeof( sorted_portals[0] ), PComp );
149 LeafVectorFromPortalVector
152 int LeafVectorFromPortalVector( byte *portalbits, byte *leafbits ){
158 memset( leafbits, 0, leafbytes );
160 for ( i = 0 ; i < numportals * 2 ; i++ )
162 if ( portalbits[i >> 3] & ( 1 << ( i & 7 ) ) ) {
164 leafbits[p->leaf >> 3] |= ( 1 << ( p->leaf & 7 ) );
168 c_leafs = CountBits( leafbits, portalclusters );
178 Merges the portal visibility for a leaf
181 void ClusterMerge( int leafnum ){
183 byte portalvector[MAX_PORTALS / 8];
184 byte uncompressed[MAX_MAP_LEAFS / 8];
185 byte compressed[MAX_MAP_LEAFS / 8];
192 // OR together all the portalvis bits
194 memset( portalvector, 0, portalbytes );
195 leaf = &leafs[leafnum];
196 for ( i = 0 ; i < leaf->numportals ; i++ )
198 p = leaf->portals[i];
199 if ( p->status != stat_done ) {
200 Error( "portal not done" );
202 for ( j = 0 ; j < portallongs ; j++ )
203 ( (long *)portalvector )[j] |= ( (long *)p->portalvis )[j];
205 portalvector[pnum >> 3] |= 1 << ( pnum & 7 );
208 // convert portal bits to leaf bits
209 numvis = LeafVectorFromPortalVector( portalvector, uncompressed );
211 if ( uncompressed[leafnum >> 3] & ( 1 << ( leafnum & 7 ) ) ) {
212 Sys_FPrintf( SYS_WRN, "WARNING: Leaf portals saw into leaf\n" );
215 uncompressed[leafnum >> 3] |= ( 1 << ( leafnum & 7 ) );
216 numvis++; // count the leaf itself
218 // save uncompressed for PHS calculation
219 memcpy( uncompressedvis + leafnum * leafbytes, uncompressed, leafbytes );
222 // compress the bit string
224 Sys_FPrintf( SYS_VRB, "cluster %4i : %4i visible\n", leafnum, numvis );
227 i = CompressVis( uncompressed, compressed );
232 if ( vismap_p > vismap_end ) {
233 Error( "Vismap expansion overflow" );
236 dvis->bitofs[leafnum][DVIS_PVS] = dest - vismap;
238 memcpy( dest, compressed, i );
247 void CalcPortalVis( void ){
250 // fastvis just uses mightsee for a very loose bound
252 for ( i = 0 ; i < numportals * 2 ; i++ )
254 portals[i].portalvis = portals[i].portalflood;
255 portals[i].status = stat_done;
260 RunThreadsOnIndividual( numportals * 2, true, PortalFlow );
270 void CalcVis( void ){
273 RunThreadsOnIndividual( numportals * 2, true, BasePortalVis );
275 // RunThreadsOnIndividual (numportals*2, true, BetterPortalVis);
282 // assemble the leaf vis lists by oring and compressing the portal lists
284 for ( i = 0 ; i < portalclusters ; i++ )
287 Sys_Printf( "Average clusters visible: %i\n", totalvis / portalclusters );
291 void SetPortalSphere( portal_t *p ){
298 VectorCopy( vec3_origin, total );
299 for ( i = 0 ; i < w->numpoints ; i++ )
301 VectorAdd( total, w->points[i], total );
304 for ( i = 0 ; i < 3 ; i++ )
305 total[i] /= w->numpoints;
308 for ( i = 0 ; i < w->numpoints ; i++ )
310 VectorSubtract( w->points[i], total, dist );
311 r = VectorLength( dist );
316 VectorCopy( total, p->origin );
325 void LoadPortals( char *name ){
336 if ( !strcmp( name,"-" ) ) {
341 f = fopen( name, "r" );
343 Error( "LoadPortals: couldn't read %s\n",name );
347 if ( fscanf( f,"%79s\n%i\n%i\n",magic, &portalclusters, &numportals ) != 3 ) {
348 Error( "LoadPortals: failed to read header" );
350 if ( strcmp( magic,PORTALFILE ) ) {
351 Error( "LoadPortals: not a portal file" );
354 Sys_Printf( "%4i portalclusters\n", portalclusters );
355 Sys_Printf( "%4i numportals\n", numportals );
357 // these counts should take advantage of 64 bit systems automatically
358 leafbytes = ( ( portalclusters + 63 ) & ~63 ) >> 3;
359 leaflongs = leafbytes / sizeof( long );
361 portalbytes = ( ( numportals * 2 + 63 ) & ~63 ) >> 3;
362 portallongs = portalbytes / sizeof( long );
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 ) );
368 leafs = malloc( portalclusters * sizeof( leaf_t ) );
369 memset( leafs, 0, portalclusters * sizeof( leaf_t ) );
371 originalvismapsize = portalclusters * leafbytes;
372 uncompressedvis = malloc( originalvismapsize );
374 vismap = vismap_p = dvisdata;
375 dvis->numclusters = portalclusters;
376 vismap_p = (byte *)&dvis->bitofs[portalclusters];
378 vismap_end = vismap + MAX_MAP_VISIBILITY;
380 for ( i = 0, p = portals ; i < numportals ; i++ )
382 if ( fscanf( f, "%i %i %i ", &numpoints, &leafnums[0], &leafnums[1] )
384 Error( "LoadPortals: reading portal %i", i );
386 if ( numpoints > MAX_POINTS_ON_WINDING ) {
387 Error( "LoadPortals: portal %i has too many points", i );
389 if ( (unsigned)leafnums[0] > portalclusters
390 || (unsigned)leafnums[1] > portalclusters ) {
391 Error( "LoadPortals: reading portal %i", i );
394 w = p->winding = NewWinding( numpoints );
396 w->numpoints = numpoints;
398 for ( j = 0 ; j < numpoints ; j++ )
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 );
409 for ( k = 0 ; k < 3 ; k++ )
410 w->points[j][k] = v[k];
415 PlaneFromWinding( w, &plane );
417 // create forward portal
418 l = &leafs[leafnums[0]];
419 if ( l->numportals == MAX_PORTALS_ON_LEAF ) {
420 Error( "Leaf with too many portals" );
422 l->portals[l->numportals] = p;
426 VectorSubtract( vec3_origin, plane.normal, p->plane.normal );
427 p->plane.dist = -plane.dist;
428 p->leaf = leafnums[1];
429 SetPortalSphere( p );
432 // create backwards portal
433 l = &leafs[leafnums[1]];
434 if ( l->numportals == MAX_PORTALS_ON_LEAF ) {
435 Error( "Leaf with too many portals" );
437 l->portals[l->numportals] = p;
440 p->winding = NewWinding( w->numpoints );
441 p->winding->numpoints = w->numpoints;
442 for ( j = 0 ; j < w->numpoints ; j++ )
444 VectorCopy( w->points[w->numpoints - 1 - j], p->winding->points[j] );
448 p->leaf = leafnums[0];
449 SetPortalSphere( p );
462 Calculate the PHS (Potentially Hearable Set)
463 by ORing together all the PVS visible from a leaf
466 void CalcPHS( void ){
467 int i, j, k, l, index;
472 byte uncompressed[MAX_MAP_LEAFS / 8];
473 byte compressed[MAX_MAP_LEAFS / 8];
475 Sys_Printf( "Building PHS...\n" );
478 for ( i = 0 ; i < portalclusters ; i++ )
480 scan = uncompressedvis + i * leafbytes;
481 memcpy( uncompressed, scan, leafbytes );
482 for ( j = 0 ; j < leafbytes ; j++ )
488 for ( k = 0 ; k < 8 ; k++ )
490 if ( !( bitbyte & ( 1 << k ) ) ) {
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
498 src = (long *)( uncompressedvis + index * leafbytes );
499 dest = (long *)uncompressed;
500 for ( l = 0 ; l < leaflongs ; l++ )
501 ( (long *)uncompressed )[l] |= src[l];
504 for ( j = 0 ; j < portalclusters ; j++ )
505 if ( uncompressed[j >> 3] & ( 1 << ( j & 7 ) ) ) {
510 // compress the bit string
512 j = CompressVis( uncompressed, compressed );
514 dest = (long *)vismap_p;
517 if ( vismap_p > vismap_end ) {
518 Error( "Vismap expansion overflow" );
521 dvis->bitofs[i][DVIS_PHS] = (byte *)dest - vismap;
523 memcpy( dest, compressed, j );
526 Sys_Printf( "Average clusters hearable: %i\n", count / portalclusters );
535 char portalfile[1024];
541 Sys_Printf( "\n----- VIS ----\n\n" );
544 // Error ("usage: vis [-threads #] [-level 0-4] [-fast] [-v] bspfile");
546 start = I_FloatTime();
550 SetQdirFromPath( mapname );
551 strcpy( source, ExpandArg( mapname ) );
552 StripExtension( source );
553 DefaultExtension( source, ".bsp" );
555 sprintf( name, "%s%s", inbase, source );
556 Sys_Printf( "reading %s\n", name );
558 if ( numnodes == 0 || numfaces == 0 ) {
559 Error( "Empty map" );
562 sprintf( portalfile, "%s%s", inbase, ExpandArg( mapname ) );
563 StripExtension( portalfile );
564 strcat( portalfile, ".prt" );
566 Sys_Printf( "reading %s\n", portalfile );
567 LoadPortals( portalfile );
573 visdatasize = vismap_p - dvisdata;
574 Sys_Printf( "visdatasize:%i compressed from %i\n", visdatasize, originalvismapsize * 2 );
576 sprintf( name, "%s%s", outbase, source );
577 Sys_Printf( "writing %s\n", name );
578 WriteBSPFile( name );
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 );
586 Sys_Printf( "%d Seconds\n", total_vis_time % 60 );