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