Author: rambetter
[divverent/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 {
44         vec3_t          v1, v2;
45
46 // calc plane
47         VectorSubtract (w->points[2], w->points[1], v1);
48         VectorSubtract (w->points[0], w->points[1], v2);
49         CrossProduct (v2, v1, plane->normal);
50         VectorNormalize (plane->normal, plane->normal);
51         plane->dist = DotProduct (w->points[0], plane->normal);
52 }
53
54
55 /*
56 NewFixedWinding()
57 returns a new fixed winding
58 ydnar: altered this a bit to reconcile multiply-defined winding_t
59 */
60
61 fixedWinding_t *NewFixedWinding( int points )
62 {
63         fixedWinding_t  *w;
64         int                     size;
65         
66         if (points > MAX_POINTS_ON_WINDING)
67                 Error ("NewWinding: %i points", points);
68         
69         size = (int)((size_t)((fixedWinding_t *)0)->points[points]);
70         w = safe_malloc (size);
71         memset (w, 0, size);
72         
73         return w;
74 }
75
76
77
78 void prl(leaf_t *l)
79 {
80         int                     i;
81         vportal_t       *p;
82         visPlane_t      pl;
83         
84         for (i=0 ; i<l->numportals ; i++)
85         {
86                 p = l->portals[i];
87                 pl = p->plane;
88                 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]);
89         }
90 }
91
92
93 //=============================================================================
94
95 /*
96 =============
97 SortPortals
98
99 Sorts the portals from the least complex, so the later ones can reuse
100 the earlier information.
101 =============
102 */
103 int PComp (const void *a, const void *b)
104 {
105         if ( (*(const vportal_t *const *)a)->nummightsee == (*(const vportal_t *const *)b)->nummightsee)
106                 return 0;
107         if ( (*(const vportal_t *const *)a)->nummightsee < (*(const vportal_t *const *)b)->nummightsee)
108                 return -1;
109         return 1;
110 }
111 void SortPortals (void)
112 {
113         int             i;
114         
115         for (i=0 ; i<numportals*2 ; i++)
116                 sorted_portals[i] = &portals[i];
117
118         if (nosort)
119                 return;
120         qsort (sorted_portals, numportals*2, sizeof(sorted_portals[0]), PComp);
121 }
122
123
124 /*
125 ==============
126 LeafVectorFromPortalVector
127 ==============
128 */
129 int LeafVectorFromPortalVector (byte *portalbits, byte *leafbits)
130 {
131         int                     i, j, leafnum;
132         vportal_t       *p;
133         int                     c_leafs;
134
135
136         for (i=0 ; i<numportals*2 ; i++)
137         {
138                 if (portalbits[i>>3] & (1<<(i&7)) )
139                 {
140                         p = portals+i;
141                         leafbits[p->leaf>>3] |= (1<<(p->leaf&7));
142                 }
143         }
144
145         for (j = 0; j < portalclusters; j++)
146         {
147                 leafnum = j;
148                 while (leafs[leafnum].merged >= 0)
149                         leafnum = leafs[leafnum].merged;
150                 //if the merged leaf is visible then the original leaf is visible
151                 if (leafbits[leafnum>>3] & (1<<(leafnum&7)))
152                 {
153                         leafbits[j>>3] |= (1<<(j&7));
154                 }
155         }
156
157         c_leafs = CountBits (leafbits, portalclusters);
158
159         return c_leafs;
160 }
161
162
163 /*
164 ===============
165 ClusterMerge
166
167 Merges the portal visibility for a leaf
168 ===============
169 */
170 static int clustersizehistogram[MAX_MAP_LEAFS] = {0};
171 void ClusterMerge (int leafnum)
172 {
173         leaf_t          *leaf;
174         byte            portalvector[MAX_PORTALS/8];
175         byte            uncompressed[MAX_MAP_LEAFS/8];
176         int                     i, j;
177         int                     numvis, mergedleafnum;
178         vportal_t       *p;
179         int                     pnum;
180
181         // OR together all the portalvis bits
182
183         mergedleafnum = leafnum;
184         while(leafs[mergedleafnum].merged >= 0)
185                 mergedleafnum = leafs[mergedleafnum].merged;
186
187         memset (portalvector, 0, portalbytes);
188         leaf = &leafs[mergedleafnum];
189         for (i = 0; i < leaf->numportals; i++)
190         {
191                 p = leaf->portals[i];
192                 if (p->removed)
193                         continue;
194
195                 if (p->status != stat_done)
196                         Error ("portal not done");
197                 for (j=0 ; j<portallongs ; j++)
198                         ((long *)portalvector)[j] |= ((long *)p->portalvis)[j];
199                 pnum = p - portals;
200                 portalvector[pnum>>3] |= 1<<(pnum&7);
201         }
202
203         memset (uncompressed, 0, leafbytes);
204
205         uncompressed[mergedleafnum>>3] |= (1<<(mergedleafnum&7));
206         // convert portal bits to leaf bits
207         numvis = LeafVectorFromPortalVector (portalvector, uncompressed);
208
209 //      if (uncompressed[leafnum>>3] & (1<<(leafnum&7)))
210 //              Sys_Printf ("WARNING: Leaf portals saw into leaf\n");
211                 
212 //      uncompressed[leafnum>>3] |= (1<<(leafnum&7));
213
214         numvis++;               // count the leaf itself
215
216         //Sys_FPrintf (SYS_VRB,"cluster %4i : %4i visible\n", leafnum, numvis);
217         ++clustersizehistogram[numvis];
218
219         memcpy (bspVisBytes + VIS_HEADER_SIZE + leafnum*leafbytes, uncompressed, leafbytes);
220 }
221
222 /*
223 ==================
224 CalcPortalVis
225 ==================
226 */
227 void CalcPortalVis (void)
228 {
229 #ifdef MREDEBUG
230         Sys_Printf("%6d portals out of %d", 0, numportals*2);
231         //get rid of the counter
232         RunThreadsOnIndividual (numportals*2, qfalse, PortalFlow);
233 #else
234         RunThreadsOnIndividual (numportals*2, qtrue, PortalFlow);
235 #endif
236
237 }
238
239 /*
240 ==================
241 CalcPassageVis
242 ==================
243 */
244 void CalcPassageVis(void)
245 {
246         PassageMemory();
247
248 #ifdef MREDEBUG
249         _printf("%6d portals out of %d", 0, numportals*2);
250         RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages);
251         _printf("\n");
252         _printf("%6d portals out of %d", 0, numportals*2);
253         RunThreadsOnIndividual (numportals*2, qfalse, PassageFlow);
254         _printf("\n");
255 #else
256         Sys_Printf( "\n--- CreatePassages (%d) ---\n", numportals * 2 );
257         RunThreadsOnIndividual( numportals*2, qtrue, CreatePassages );
258         
259         Sys_Printf( "\n--- PassageFlow (%d) ---\n", numportals * 2 );
260         RunThreadsOnIndividual( numportals * 2, qtrue, PassageFlow );
261 #endif
262 }
263
264 /*
265 ==================
266 CalcPassagePortalVis
267 ==================
268 */
269 void CalcPassagePortalVis(void)
270 {
271         PassageMemory();
272
273 #ifdef MREDEBUG
274         Sys_Printf("%6d portals out of %d", 0, numportals*2);
275         RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages);
276         Sys_Printf("\n");
277         Sys_Printf("%6d portals out of %d", 0, numportals*2);
278         RunThreadsOnIndividual (numportals*2, qfalse, PassagePortalFlow);
279         Sys_Printf("\n");
280 #else
281         Sys_Printf( "\n--- CreatePassages (%d) ---\n", numportals * 2 );
282         RunThreadsOnIndividual( numportals * 2, qtrue, CreatePassages);
283         
284         Sys_Printf( "\n--- PassagePortalFlow (%d) ---\n", numportals * 2 );
285         RunThreadsOnIndividual( numportals * 2, qtrue, PassagePortalFlow );
286 #endif
287 }
288
289 /*
290 ==================
291 CalcFastVis
292 ==================
293 */
294 void CalcFastVis(void)
295 {
296         int             i;
297
298         // fastvis just uses mightsee for a very loose bound
299         for (i=0 ; i<numportals*2 ; i++)
300         {
301                 portals[i].portalvis = portals[i].portalflood;
302                 portals[i].status = stat_done;
303         }
304 }
305
306 /*
307 ==================
308 CalcVis
309 ==================
310 */
311 void CalcVis (void)
312 {
313         int                     i, minvis, maxvis;
314         const char      *value;
315         double mu, sigma, totalvis, totalvis2;
316         
317         
318         /* ydnar: rr2do2's farplane code */
319         farPlaneDist = 0.0f;
320         value = ValueForKey( &entities[ 0 ], "_farplanedist" );         /* proper '_' prefixed key */
321         if( value[ 0 ] == '\0' )
322                 value = ValueForKey( &entities[ 0 ], "fogclip" );               /* wolf compatibility */
323         if( value[ 0 ] == '\0' )
324                 value = ValueForKey( &entities[ 0 ], "distancecull" );  /* sof2 compatibility */
325         if( value[ 0 ] != '\0' )
326         {
327                 farPlaneDist = atof( value );
328                 if( farPlaneDist > 0.0f )
329                         Sys_Printf( "farplane distance = %.1f\n", farPlaneDist );
330                 else
331                         farPlaneDist = 0.0f;
332         }
333         
334         
335         
336         Sys_Printf( "\n--- BasePortalVis (%d) ---\n", numportals * 2 );
337         RunThreadsOnIndividual( numportals * 2, qtrue, BasePortalVis );
338         
339 //      RunThreadsOnIndividual (numportals*2, qtrue, BetterPortalVis);
340
341         SortPortals ();
342
343   if (fastvis) {
344     CalcFastVis();
345   }
346   else if ( noPassageVis ) {
347     CalcPortalVis();
348   }
349   else if ( passageVisOnly ) {
350     CalcPassageVis();
351   }
352   else {
353     CalcPassagePortalVis();
354   }
355         //
356         // assemble the leaf vis lists by oring and compressing the portal lists
357         //
358         Sys_Printf("creating leaf vis...\n");
359         for (i=0 ; i<portalclusters ; i++)
360                 ClusterMerge (i);
361         
362         totalvis = 0;
363         totalvis2 = 0;
364         minvis = -1;
365         maxvis = -1;
366         for(i = 0; i < MAX_MAP_LEAFS; ++i)
367                 if(clustersizehistogram[i])
368                 {
369                         if(debugCluster)
370                                 Sys_FPrintf(SYS_VRB, "%4i clusters have exactly %4i visible clusters\n", clustersizehistogram[i], i);
371                         /* cast is to prevent integer overflow */
372                         totalvis  += ((double) i)                * ((double) clustersizehistogram[i]);
373                         totalvis2 += ((double) i) * ((double) i) * ((double) clustersizehistogram[i]);
374
375                         if(minvis < 0)
376                                 minvis = i;
377                         maxvis = i;
378                 }
379         
380         mu = totalvis / portalclusters;
381         sigma = sqrt(totalvis2 / portalclusters - mu * mu);
382         
383   Sys_Printf( "Total clusters: %i\n", portalclusters );
384   Sys_Printf( "Total visible clusters: %.0f\n", totalvis );
385   Sys_Printf( "Average clusters visible: %.2f (%.3f%%/total)\n", mu, mu / portalclusters * 100.0);
386   Sys_Printf( "  Standard deviation: %.2f (%.3f%%/total, %.3f%%/avg)\n", sigma, sigma / portalclusters * 100.0, sigma / mu * 100.0);
387   Sys_Printf( "  Minimum: %i (%.3f%%/total, %.3f%%/avg)\n", minvis, minvis / (double) portalclusters * 100.0, minvis / mu * 100.0);
388   Sys_Printf( "  Maximum: %i (%.3f%%/total, %.3f%%/avg)\n", maxvis, maxvis / (double) portalclusters * 100.0, maxvis / mu * 100.0);
389 }
390
391 /*
392 ==================
393 SetPortalSphere
394 ==================
395 */
396 void SetPortalSphere (vportal_t *p)
397 {
398         int             i;
399         vec3_t  total, dist;
400         fixedWinding_t  *w;
401         float   r, bestr;
402
403         w = p->winding;
404         VectorCopy (vec3_origin, total);
405         for (i=0 ; i<w->numpoints ; i++)
406         {
407                 VectorAdd (total, w->points[i], total);
408         }
409         
410         for (i=0 ; i<3 ; i++)
411                 total[i] /= w->numpoints;
412
413         bestr = 0;              
414         for (i=0 ; i<w->numpoints ; i++)
415         {
416                 VectorSubtract (w->points[i], total, dist);
417                 r = VectorLength (dist);
418                 if (r > bestr)
419                         bestr = r;
420         }
421         VectorCopy (total, p->origin);
422         p->radius = bestr;
423 }
424
425 /*
426 =============
427 Winding_PlanesConcave
428 =============
429 */
430 #define WCONVEX_EPSILON         0.2
431
432 int Winding_PlanesConcave(fixedWinding_t *w1, fixedWinding_t *w2,
433                                                          vec3_t normal1, vec3_t normal2,
434                                                          float dist1, float dist2)
435 {
436         int i;
437
438         if (!w1 || !w2) return qfalse;
439
440         // check if one of the points of winding 1 is at the front of the plane of winding 2
441         for (i = 0; i < w1->numpoints; i++)
442         {
443                 if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return qtrue;
444         }
445         // check if one of the points of winding 2 is at the front of the plane of winding 1
446         for (i = 0; i < w2->numpoints; i++)
447         {
448                 if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return qtrue;
449         }
450
451         return qfalse;
452 }
453
454 /*
455 ============
456 TryMergeLeaves
457 ============
458 */
459 int TryMergeLeaves(int l1num, int l2num)
460 {
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) l1 = &leafs[l1num];
470                 else l1 = &faceleafs[l1num];
471                 for (i = 0; i < l1->numportals; i++)
472                 {
473                         p1 = l1->portals[i];
474                         if (p1->leaf == l2num) continue;
475                         for (n = 0; n < 2; n++)
476                         {
477                                 if (n) l2 = &leafs[l2num];
478                                 else l2 = &faceleafs[l2num];
479                                 for (j = 0; j < l2->numportals; j++)
480                                 {
481                                         p2 = l2->portals[j];
482                                         if (p2->leaf == l1num) continue;
483                                         //
484                                         plane1 = p1->plane;
485                                         plane2 = p2->plane;
486                                         if (Winding_PlanesConcave(p1->winding, p2->winding, plane1.normal, plane2.normal, plane1.dist, plane2.dist))
487                                                 return qfalse;
488                                 }
489                         }
490                 }
491         }
492         for (k = 0; k < 2; k++)
493         {
494                 if (k)
495                 {
496                         l1 = &leafs[l1num];
497                         l2 = &leafs[l2num];
498                 }
499                 else
500                 {
501                         l1 = &faceleafs[l1num];
502                         l2 = &faceleafs[l2num];
503                 }
504                 numportals = 0;
505                 //the leaves can be merged now
506                 for (i = 0; i < l1->numportals; i++)
507                 {
508                         p1 = l1->portals[i];
509                         if (p1->leaf == l2num)
510                         {
511                                 p1->removed = qtrue;
512                                 continue;
513                         }
514                         portals[numportals++] = p1;
515                 }
516                 for (j = 0; j < l2->numportals; j++)
517                 {
518                         p2 = l2->portals[j];
519                         if (p2->leaf == l1num)
520                         {
521                                 p2->removed = qtrue;
522                                 continue;
523                         }
524                         portals[numportals++] = p2;
525                 }
526                 for (i = 0; i < numportals; i++)
527                 {
528                         l2->portals[i] = portals[i];
529                 }
530                 l2->numportals = numportals;
531                 l1->merged = l2num;
532         }
533         return qtrue;
534 }
535
536 /*
537 ============
538 UpdatePortals
539 ============
540 */
541 void UpdatePortals(void)
542 {
543         int i;
544         vportal_t *p;
545
546         for (i = 0; i < numportals * 2; i++)
547         {
548                 p = &portals[i];
549                 if (p->removed)
550                         continue;
551                 while(leafs[p->leaf].merged >= 0)
552                         p->leaf = leafs[p->leaf].merged;
553         }
554 }
555
556 /*
557 ============
558 MergeLeaves
559
560 try to merge leaves but don't merge through hint splitters
561 ============
562 */
563 void MergeLeaves(void)
564 {
565         int i, j, nummerges, totalnummerges;
566         leaf_t *leaf;
567         vportal_t *p;
568
569         totalnummerges = 0;
570         do
571         {
572                 nummerges = 0;
573                 for (i = 0; i < portalclusters; i++)
574                 {
575                         leaf = &leafs[i];
576                         //if this leaf is merged already
577
578                         /* ydnar: vmods: merge all non-hint portals */
579                         if( leaf->merged >= 0 && hint == qfalse )
580                                 continue;
581
582
583                         for (j = 0; j < leaf->numportals; j++)
584                         {
585                                 p = leaf->portals[j];
586                                 //
587                                 if (p->removed)
588                                         continue;
589                                 //never merge through hint portals
590                                 if (p->hint)
591                                         continue;
592                                 if (TryMergeLeaves(i, p->leaf))
593                                 {
594                                         UpdatePortals();
595                                         nummerges++;
596                                         break;
597                                 }
598                         }
599                 }
600                 totalnummerges += nummerges;
601         } while (nummerges);
602         Sys_Printf("%6d leaves merged\n", totalnummerges);
603 }
604
605 /*
606 ============
607 TryMergeWinding
608 ============
609 */
610 #define CONTINUOUS_EPSILON      0.005
611
612 fixedWinding_t *TryMergeWinding (fixedWinding_t *f1, fixedWinding_t *f2, vec3_t planenormal)
613 {
614         vec_t           *p1, *p2, *p3, *p4, *back;
615         fixedWinding_t  *newf;
616         int                     i, j, k, l;
617         vec3_t          normal, delta;
618         vec_t           dot;
619         qboolean        keep1, keep2;
620         
621
622         //
623         // find a common edge
624         //      
625         p1 = p2 = NULL; // stop compiler warning
626         j = 0;                  // 
627         
628         for (i = 0; i < f1->numpoints; i++)
629         {
630                 p1 = f1->points[i];
631                 p2 = f1->points[(i+1) % f1->numpoints];
632                 for (j = 0; j < f2->numpoints; j++)
633                 {
634                         p3 = f2->points[j];
635                         p4 = f2->points[(j+1) % f2->numpoints];
636                         for (k = 0; k < 3; k++)
637                         {
638                                 if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME
639                                         break;
640                                 if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME
641                                         break;
642                         } //end for
643                         if (k==3)
644                                 break;
645                 } //end for
646                 if (j < f2->numpoints)
647                         break;
648         } //end for
649         
650         if (i == f1->numpoints)
651                 return NULL;                    // no matching edges
652
653         //
654         // check slope of connected lines
655         // if the slopes are colinear, the point can be removed
656         //
657         back = f1->points[(i+f1->numpoints-1)%f1->numpoints];
658         VectorSubtract (p1, back, delta);
659         CrossProduct (planenormal, delta, normal);
660         VectorNormalize (normal, normal);
661         
662         back = f2->points[(j+2)%f2->numpoints];
663         VectorSubtract (back, p1, delta);
664         dot = DotProduct (delta, normal);
665         if (dot > CONTINUOUS_EPSILON)
666                 return NULL;                    // not a convex polygon
667         keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
668         
669         back = f1->points[(i+2)%f1->numpoints];
670         VectorSubtract (back, p2, delta);
671         CrossProduct (planenormal, delta, normal);
672         VectorNormalize (normal, normal);
673
674         back = f2->points[(j+f2->numpoints-1)%f2->numpoints];
675         VectorSubtract (back, p2, delta);
676         dot = DotProduct (delta, normal);
677         if (dot > CONTINUOUS_EPSILON)
678                 return NULL;                    // not a convex polygon
679         keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);
680
681         //
682         // build the new polygon
683         //
684         newf = NewFixedWinding (f1->numpoints + f2->numpoints);
685         
686         // copy first polygon
687         for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
688         {
689                 if (k==(i+1)%f1->numpoints && !keep2)
690                         continue;
691                 
692                 VectorCopy (f1->points[k], newf->points[newf->numpoints]);
693                 newf->numpoints++;
694         }
695         
696         // copy second polygon
697         for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
698         {
699                 if (l==(j+1)%f2->numpoints && !keep1)
700                         continue;
701                 VectorCopy (f2->points[l], newf->points[newf->numpoints]);
702                 newf->numpoints++;
703         }
704
705         return newf;
706 }
707
708 /*
709 ============
710 MergeLeafPortals
711 ============
712 */
713 void MergeLeafPortals(void)
714 {
715         int i, j, k, nummerges, hintsmerged;
716         leaf_t *leaf;
717         vportal_t *p1, *p2;
718         fixedWinding_t *w;
719
720         nummerges = 0;
721         hintsmerged = 0;
722         for (i = 0; i < portalclusters; i++)
723         {
724                 leaf = &leafs[i];
725                 if (leaf->merged >= 0) continue;
726                 for (j = 0; j < leaf->numportals; j++)
727                 {
728                         p1 = leaf->portals[j];
729                         if (p1->removed)
730                                 continue;
731                         for (k = j+1; k < leaf->numportals; k++)
732                         {
733                                 p2 = leaf->portals[k];
734                                 if (p2->removed)
735                                         continue;
736                                 if (p1->leaf == p2->leaf)
737                                 {
738                                         w = TryMergeWinding(p1->winding, p2->winding, p1->plane.normal);
739                                         if (w)
740                                         {
741                                                 free( p1->winding );    //% FreeWinding(p1->winding);
742                                                 p1->winding = w;
743                                                 if (p1->hint && p2->hint)
744                                                         hintsmerged++;
745                                                 p1->hint |= p2->hint;
746                                                 SetPortalSphere(p1);
747                                                 p2->removed = qtrue;
748                                                 nummerges++;
749                                                 i--;
750                                                 break;
751                                         }
752                                 }
753                         }
754                         if (k < leaf->numportals)
755                                 break;
756                 }
757         }
758         Sys_Printf("%6d portals merged\n", nummerges);
759         Sys_Printf("%6d hint portals merged\n", hintsmerged);
760 }
761
762
763 /*
764 ============
765 WritePortals
766 ============
767 */
768 int CountActivePortals(void)
769 {
770         int num, hints, j;
771         vportal_t *p;
772
773         num = 0;
774         hints = 0;
775         for (j = 0; j < numportals * 2; j++)
776         {
777                 p = portals + j;
778                 if (p->removed)
779                         continue;
780                 if (p->hint)
781                         hints++;
782                 num++;
783         }
784         Sys_Printf("%6d active portals\n", num);
785         Sys_Printf("%6d hint portals\n", hints);
786         return num;
787 }
788
789 /*
790 ============
791 WritePortals
792 ============
793 */
794 void WriteFloat (FILE *f, vec_t v);
795
796 void WritePortals(char *filename)
797 {
798         int i, j, num;
799         FILE *pf;
800         vportal_t *p;
801         fixedWinding_t *w;
802
803         // write the file
804         pf = fopen (filename, "w");
805         if (!pf)
806                 Error ("Error opening %s", filename);
807
808         num = 0;
809         for (j = 0; j < numportals * 2; j++)
810         {
811                 p = portals + j;
812                 if (p->removed)
813                         continue;
814 //              if (!p->hint)
815 //                      continue;
816                 num++;
817         }
818
819         fprintf (pf, "%s\n", PORTALFILE);
820         fprintf (pf, "%i\n", 0);
821         fprintf (pf, "%i\n", num);// + numfaces);
822         fprintf (pf, "%i\n", 0);
823
824         for (j = 0; j < numportals * 2; j++)
825         {
826                 p = portals + j;
827                 if (p->removed)
828                         continue;
829 //              if (!p->hint)
830 //                      continue;
831                 w = p->winding;
832                 fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);
833                 fprintf (pf, "%d ", p->hint);
834                 for (i=0 ; i<w->numpoints ; i++)
835                 {
836                         fprintf (pf,"(");
837                         WriteFloat (pf, w->points[i][0]);
838                         WriteFloat (pf, w->points[i][1]);
839                         WriteFloat (pf, w->points[i][2]);
840                         fprintf (pf,") ");
841                 }
842                 fprintf (pf,"\n");
843         }
844
845         /*
846         for (j = 0; j < numfaces; j++)
847         {
848                 p = faces + j;
849                 w = p->winding;
850                 fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);
851                 fprintf (pf, "0 ");
852                 for (i=0 ; i<w->numpoints ; i++)
853                 {
854                         fprintf (pf,"(");
855                         WriteFloat (pf, w->points[i][0]);
856                         WriteFloat (pf, w->points[i][1]);
857                         WriteFloat (pf, w->points[i][2]);
858                         fprintf (pf,") ");
859                 }
860                 fprintf (pf,"\n");
861         }*/
862
863         fclose (pf);
864 }
865
866 /*
867 ============
868 LoadPortals
869 ============
870 */
871 void LoadPortals (char *name)
872 {
873         int                     i, j, hint;
874         vportal_t       *p;
875         leaf_t          *l;
876         char            magic[80];
877         FILE            *f;
878         int                     numpoints;
879         fixedWinding_t  *w;
880         int                     leafnums[2];
881         visPlane_t      plane;
882         
883         if (!strcmp(name,"-"))
884                 f = stdin;
885         else
886         {
887                 f = fopen(name, "r");
888                 if (!f)
889                         Error ("LoadPortals: couldn't read %s\n",name);
890         }
891
892         if (fscanf (f,"%79s\n%i\n%i\n%i\n",magic, &portalclusters, &numportals, &numfaces) != 4)
893                 Error ("LoadPortals: failed to read header");
894         if (strcmp(magic,PORTALFILE))
895                 Error ("LoadPortals: not a portal file");
896
897         Sys_Printf ("%6i portalclusters\n", portalclusters);
898         Sys_Printf ("%6i numportals\n", numportals);
899         Sys_Printf ("%6i numfaces\n", numfaces);
900
901         if(numportals > MAX_PORTALS)
902                 Error("MAX_PORTALS");
903         
904         // these counts should take advantage of 64 bit systems automatically
905         leafbytes = ((portalclusters+63)&~63)>>3;
906         leaflongs = leafbytes/sizeof(long);
907         
908         portalbytes = ((numportals*2+63)&~63)>>3;
909         portallongs = portalbytes/sizeof(long);
910
911         // each file portal is split into two memory portals
912         portals = safe_malloc(2*numportals*sizeof(vportal_t));
913         memset (portals, 0, 2*numportals*sizeof(vportal_t));
914         
915         leafs = safe_malloc(portalclusters*sizeof(leaf_t));
916         memset (leafs, 0, portalclusters*sizeof(leaf_t));
917
918         for (i = 0; i < portalclusters; i++)
919                 leafs[i].merged = -1;
920
921         numBSPVisBytes = VIS_HEADER_SIZE + portalclusters*leafbytes;
922
923         if (numBSPVisBytes > MAX_MAP_VISIBILITY)
924           Error("MAX_MAP_VISIBILITY exceeded");
925
926         ((int *)bspVisBytes)[0] = portalclusters;
927         ((int *)bspVisBytes)[1] = leafbytes;
928                 
929         for (i=0, p=portals ; i<numportals ; i++)
930         {
931                 if (fscanf (f, "%i %i %i ", &numpoints, &leafnums[0], &leafnums[1]) != 3)
932                         Error ("LoadPortals: reading portal %i", i);
933                 if (numpoints > MAX_POINTS_ON_WINDING)
934                         Error ("LoadPortals: portal %i has too many points", i);
935                 if (leafnums[0] > portalclusters
936                 || leafnums[1] > portalclusters)
937                         Error ("LoadPortals: reading portal %i", i);
938                 if (fscanf (f, "%i ", &hint) != 1)
939                         Error ("LoadPortals: reading hint state");
940                 
941                 w = p->winding = NewFixedWinding (numpoints);
942                 w->numpoints = numpoints;
943                 
944                 for (j=0 ; j<numpoints ; j++)
945                 {
946                         double  v[3];
947                         int             k;
948
949                         // scanf into double, then assign to vec_t
950                         // so we don't care what size vec_t is
951                         if (fscanf (f, "(%lf %lf %lf ) "
952                         , &v[0], &v[1], &v[2]) != 3)
953                                 Error ("LoadPortals: reading portal %i", i);
954                         for (k=0 ; k<3 ; k++)
955                                 w->points[j][k] = v[k];
956                 }
957                 if(fscanf (f, "\n") != 0)
958                 {
959                         // silence gcc warning
960                 }
961                 
962                 // calc plane
963                 PlaneFromWinding (w, &plane);
964
965                 // create forward portal
966                 l = &leafs[leafnums[0]];
967                 if (l->numportals == MAX_PORTALS_ON_LEAF)
968                         Error ("Leaf with too many portals");
969                 l->portals[l->numportals] = p;
970                 l->numportals++;
971                 
972                 p->num = i+1;
973                 p->hint = hint;
974                 p->winding = w;
975                 VectorSubtract (vec3_origin, plane.normal, p->plane.normal);
976                 p->plane.dist = -plane.dist;
977                 p->leaf = leafnums[1];
978                 SetPortalSphere (p);
979                 p++;
980                 
981                 // create backwards portal
982                 l = &leafs[leafnums[1]];
983                 if (l->numportals == MAX_PORTALS_ON_LEAF)
984                         Error ("Leaf with too many portals");
985                 l->portals[l->numportals] = p;
986                 l->numportals++;
987                 
988                 p->num = i+1;
989                 p->hint = hint;
990                 p->winding = NewFixedWinding(w->numpoints);
991                 p->winding->numpoints = w->numpoints;
992                 for (j=0 ; j<w->numpoints ; j++)
993                 {
994                         VectorCopy (w->points[w->numpoints-1-j], p->winding->points[j]);
995                 }
996
997                 p->plane = plane;
998                 p->leaf = leafnums[0];
999                 SetPortalSphere (p);
1000                 p++;
1001
1002         }
1003
1004         faces = safe_malloc(2*numfaces*sizeof(vportal_t));
1005         memset (faces, 0, 2*numfaces*sizeof(vportal_t));
1006
1007         faceleafs = safe_malloc(portalclusters*sizeof(leaf_t));
1008         memset(faceleafs, 0, portalclusters*sizeof(leaf_t));
1009
1010         for (i = 0, p = faces; i < numfaces; i++)
1011         {
1012                 if (fscanf (f, "%i %i ", &numpoints, &leafnums[0]) != 2)
1013                         Error ("LoadPortals: reading portal %i", i);
1014
1015                 w = p->winding = NewFixedWinding (numpoints);
1016                 w->numpoints = numpoints;
1017                 
1018                 for (j=0 ; j<numpoints ; j++)
1019                 {
1020                         double  v[3];
1021                         int             k;
1022
1023                         // scanf into double, then assign to vec_t
1024                         // so we don't care what size vec_t is
1025                         if (fscanf (f, "(%lf %lf %lf ) "
1026                         , &v[0], &v[1], &v[2]) != 3)
1027                                 Error ("LoadPortals: reading portal %i", i);
1028                         for (k=0 ; k<3 ; k++)
1029                                 w->points[j][k] = v[k];
1030                 }
1031                 if(fscanf (f, "\n") != 0)
1032                 {
1033                         // silence gcc warning
1034                 }
1035                 
1036                 // calc plane
1037                 PlaneFromWinding (w, &plane);
1038
1039                 l = &faceleafs[leafnums[0]];
1040                 l->merged = -1;
1041                 if (l->numportals == MAX_PORTALS_ON_LEAF)
1042                         Error ("Leaf with too many faces");
1043                 l->portals[l->numportals] = p;
1044                 l->numportals++;
1045                 
1046                 p->num = i+1;
1047                 p->winding = w;
1048                 // normal pointing out of the leaf
1049                 VectorSubtract (vec3_origin, plane.normal, p->plane.normal);
1050                 p->plane.dist = -plane.dist;
1051                 p->leaf = -1;
1052                 SetPortalSphere (p);
1053                 p++;
1054         }
1055         
1056         fclose (f);
1057 }
1058
1059
1060
1061 /*
1062 ===========
1063 VisMain
1064 ===========
1065 */
1066 int VisMain (int argc, char **argv)
1067 {
1068         char            portalfile[1024];
1069         int                     i;
1070         
1071         
1072         /* note it */
1073         Sys_Printf( "--- Vis ---\n" );
1074         
1075         /* process arguments */
1076         for (i=1 ; i < (argc - 1) ; i++)
1077         {
1078                 if (!strcmp(argv[i], "-fast")) {
1079                         Sys_Printf ("fastvis = true\n");
1080                         fastvis = qtrue;
1081                 } else if (!strcmp(argv[i], "-merge")) {
1082                         Sys_Printf ("merge = true\n");
1083                         mergevis = qtrue;
1084                 } else if (!strcmp(argv[i], "-mergeportals")) {
1085                         Sys_Printf ("mergeportals = true\n");
1086                         mergevisportals = qtrue;
1087                 } else if (!strcmp(argv[i], "-nopassage")) {
1088                         Sys_Printf ("nopassage = true\n");
1089                         noPassageVis = qtrue;
1090                 } else if (!strcmp(argv[i], "-passageOnly")) {
1091                         Sys_Printf ("passageOnly = true\n");
1092                         passageVisOnly = qtrue;
1093                 } else if (!strcmp (argv[i],"-nosort")) {
1094                         Sys_Printf ("nosort = true\n");
1095                         nosort = qtrue;
1096                 } else if (!strcmp (argv[i],"-saveprt")) {
1097                         Sys_Printf ("saveprt = true\n");
1098                         saveprt = qtrue;
1099                 } else if( !strcmp( argv[ i ], "-v" ) ) {
1100                         debugCluster = qtrue;
1101                         Sys_Printf( "Extra verbous mode enabled\n" );
1102                 } else if (!strcmp (argv[i],"-tmpin")) {
1103                         strcpy (inbase, "/tmp");
1104                 } else if (!strcmp (argv[i],"-tmpout")) {
1105                         strcpy (outbase, "/tmp");
1106                 }
1107                 
1108         
1109                 /* ydnar: -hint to merge all but hint portals */
1110                 else if( !strcmp( argv[ i ], "-hint" ) )
1111                 {
1112                         Sys_Printf( "hint = true\n" );
1113                         hint = qtrue;
1114                         mergevis = qtrue;
1115                 }
1116                 
1117                 else
1118                 {
1119                         Sys_Printf( "WARNING: Unknown option \"%s\"\n", argv[ i ] );
1120                 }
1121         }
1122
1123         if( i != argc - 1 )
1124                 Error( "usage: vis [-threads #] [-level 0-4] [-fast] [-v] bspfile" );
1125         
1126
1127         /* load the bsp */
1128         sprintf( source, "%s%s", inbase, ExpandArg( argv[ i ] ) );
1129         StripExtension( source );
1130         strcat( source, ".bsp" );
1131         Sys_Printf( "Loading %s\n", source );
1132         LoadBSPFile( source );
1133         
1134         /* load the portal file */
1135         sprintf( portalfile, "%s%s", inbase, ExpandArg( argv[ i ] ) );
1136         StripExtension( portalfile );
1137         strcat( portalfile, ".prt" );
1138         Sys_Printf( "Loading %s\n", portalfile );
1139         LoadPortals( portalfile );
1140         
1141         /* ydnar: exit if no portals, hence no vis */
1142         if( numportals == 0 )
1143         {
1144                 Sys_Printf( "No portals means no vis, exiting.\n" );
1145                 return 0;
1146         }
1147         
1148         /* ydnar: for getting far plane */
1149         ParseEntities();
1150         
1151         /* inject command line parameters */
1152         InjectCommandLine(argv, 0, argc - 1);
1153         UnparseEntities();
1154         
1155         if( mergevis )
1156                 MergeLeaves();
1157
1158         if( mergevis || mergevisportals )
1159                 MergeLeafPortals();
1160         
1161         CountActivePortals();
1162         /* WritePortals( "maps/hints.prs" );*/
1163         
1164         Sys_Printf( "visdatasize:%i\n", numBSPVisBytes );
1165         
1166         CalcVis();
1167         
1168         /* delete the prt file */
1169         if( !saveprt )
1170                 remove( portalfile );
1171
1172         /* write the bsp file */
1173         Sys_Printf( "Writing %s\n", source );
1174         WriteBSPFile( source );
1175
1176         return 0;
1177 }