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
21 ----------------------------------------------------------------------------------
23 This code has been altered significantly from its original form, to support
24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
26 ------------------------------------------------------------------------------- */
41 void PlaneFromWinding (fixedWinding_t *w, visPlane_t *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);
56 returns a new fixed winding
57 ydnar: altered this a bit to reconcile multiply-defined winding_t
60 fixedWinding_t *NewFixedWinding( int points )
65 if (points > MAX_POINTS_ON_WINDING)
66 Error ("NewWinding: %i points", points);
68 size = (int)((fixedWinding_t *)0)->points[points];
69 w = safe_malloc (size);
83 for (i=0 ; i<l->numportals ; i++)
87 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]);
92 //=============================================================================
98 Sorts the portals from the least complex, so the later ones can reuse
99 the earlier information.
102 int PComp (const void *a, const void *b)
104 if ( (*(vportal_t **)a)->nummightsee == (*(vportal_t **)b)->nummightsee)
106 if ( (*(vportal_t **)a)->nummightsee < (*(vportal_t **)b)->nummightsee)
110 void SortPortals (void)
114 for (i=0 ; i<numportals*2 ; i++)
115 sorted_portals[i] = &portals[i];
119 qsort (sorted_portals, numportals*2, sizeof(sorted_portals[0]), PComp);
125 LeafVectorFromPortalVector
128 int LeafVectorFromPortalVector (byte *portalbits, byte *leafbits)
135 for (i=0 ; i<numportals*2 ; i++)
137 if (portalbits[i>>3] & (1<<(i&7)) )
140 leafbits[p->leaf>>3] |= (1<<(p->leaf&7));
144 for (j = 0; j < portalclusters; j++)
147 while (leafs[leafnum].merged >= 0)
148 leafnum = leafs[leafnum].merged;
149 //if the merged leaf is visible then the original leaf is visible
150 if (leafbits[leafnum>>3] & (1<<(leafnum&7)))
152 leafbits[j>>3] |= (1<<(j&7));
156 c_leafs = CountBits (leafbits, portalclusters);
166 Merges the portal visibility for a leaf
169 void ClusterMerge (int leafnum)
172 byte portalvector[MAX_PORTALS/8];
173 byte uncompressed[MAX_MAP_LEAFS/8];
175 int numvis, mergedleafnum;
179 // OR together all the portalvis bits
181 mergedleafnum = leafnum;
182 while(leafs[mergedleafnum].merged >= 0)
183 mergedleafnum = leafs[mergedleafnum].merged;
185 memset (portalvector, 0, portalbytes);
186 leaf = &leafs[mergedleafnum];
187 for (i = 0; i < leaf->numportals; i++)
189 p = leaf->portals[i];
193 if (p->status != stat_done)
194 Error ("portal not done");
195 for (j=0 ; j<portallongs ; j++)
196 ((long *)portalvector)[j] |= ((long *)p->portalvis)[j];
198 portalvector[pnum>>3] |= 1<<(pnum&7);
201 memset (uncompressed, 0, leafbytes);
203 uncompressed[mergedleafnum>>3] |= (1<<(mergedleafnum&7));
204 // convert portal bits to leaf bits
205 numvis = LeafVectorFromPortalVector (portalvector, uncompressed);
207 // if (uncompressed[leafnum>>3] & (1<<(leafnum&7)))
208 // Sys_Printf ("WARNING: Leaf portals saw into leaf\n");
210 // uncompressed[leafnum>>3] |= (1<<(leafnum&7));
212 numvis++; // count the leaf itself
216 Sys_FPrintf (SYS_VRB,"cluster %4i : %4i visible\n", leafnum, numvis);
218 memcpy (bspVisBytes + VIS_HEADER_SIZE + leafnum*leafbytes, uncompressed, leafbytes);
226 void CalcPortalVis (void)
229 Sys_Printf("%6d portals out of %d", 0, numportals*2);
230 //get rid of the counter
231 RunThreadsOnIndividual (numportals*2, qfalse, PortalFlow);
233 RunThreadsOnIndividual (numportals*2, qtrue, PortalFlow);
243 void CalcPassageVis(void)
248 _printf("%6d portals out of %d", 0, numportals*2);
249 RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages);
251 _printf("%6d portals out of %d", 0, numportals*2);
252 RunThreadsOnIndividual (numportals*2, qfalse, PassageFlow);
255 Sys_Printf( "\n--- CreatePassages (%d) ---\n", numportals * 2 );
256 RunThreadsOnIndividual( numportals*2, qtrue, CreatePassages );
258 Sys_Printf( "\n--- PassageFlow (%d) ---\n", numportals * 2 );
259 RunThreadsOnIndividual( numportals * 2, qtrue, PassageFlow );
268 void CalcPassagePortalVis(void)
273 Sys_Printf("%6d portals out of %d", 0, numportals*2);
274 RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages);
276 Sys_Printf("%6d portals out of %d", 0, numportals*2);
277 RunThreadsOnIndividual (numportals*2, qfalse, PassagePortalFlow);
280 Sys_Printf( "\n--- CreatePassages (%d) ---\n", numportals * 2 );
281 RunThreadsOnIndividual( numportals * 2, qtrue, CreatePassages);
283 Sys_Printf( "\n--- PassagePortalFlow (%d) ---\n", numportals * 2 );
284 RunThreadsOnIndividual( numportals * 2, qtrue, PassagePortalFlow );
293 void CalcFastVis(void)
297 // fastvis just uses mightsee for a very loose bound
298 for (i=0 ; i<numportals*2 ; i++)
300 portals[i].portalvis = portals[i].portalflood;
301 portals[i].status = stat_done;
316 /* ydnar: rr2do2's farplane code */
318 value = ValueForKey( &entities[ 0 ], "_farplanedist" ); /* proper '_' prefixed key */
319 if( value[ 0 ] == '\0' )
320 value = ValueForKey( &entities[ 0 ], "fogclip" ); /* wolf compatibility */
321 if( value[ 0 ] == '\0' )
322 value = ValueForKey( &entities[ 0 ], "distancecull" ); /* sof2 compatibility */
323 if( value[ 0 ] != '\0' )
325 farPlaneDist = atof( value );
326 if( farPlaneDist > 0.0f )
327 Sys_Printf( "farplane distance = %.1f\n", farPlaneDist );
334 Sys_Printf( "\n--- BasePortalVis (%d) ---\n", numportals * 2 );
335 RunThreadsOnIndividual( numportals * 2, qtrue, BasePortalVis );
337 // RunThreadsOnIndividual (numportals*2, qtrue, BetterPortalVis);
344 else if ( noPassageVis ) {
347 else if ( passageVisOnly ) {
351 CalcPassagePortalVis();
354 // assemble the leaf vis lists by oring and compressing the portal lists
356 Sys_Printf("creating leaf vis...\n");
357 for (i=0 ; i<portalclusters ; i++)
360 Sys_Printf( "Total visible clusters: %i\n", totalvis );
361 Sys_Printf( "Average clusters visible: %i\n", totalvis / portalclusters );
369 void SetPortalSphere (vportal_t *p)
377 VectorCopy (vec3_origin, total);
378 for (i=0 ; i<w->numpoints ; i++)
380 VectorAdd (total, w->points[i], total);
383 for (i=0 ; i<3 ; i++)
384 total[i] /= w->numpoints;
387 for (i=0 ; i<w->numpoints ; i++)
389 VectorSubtract (w->points[i], total, dist);
390 r = VectorLength (dist);
394 VectorCopy (total, p->origin);
400 Winding_PlanesConcave
403 #define WCONVEX_EPSILON 0.2
405 int Winding_PlanesConcave(fixedWinding_t *w1, fixedWinding_t *w2,
406 vec3_t normal1, vec3_t normal2,
407 float dist1, float dist2)
411 if (!w1 || !w2) return qfalse;
413 // check if one of the points of winding 1 is at the front of the plane of winding 2
414 for (i = 0; i < w1->numpoints; i++)
416 if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return qtrue;
418 // check if one of the points of winding 2 is at the front of the plane of winding 1
419 for (i = 0; i < w2->numpoints; i++)
421 if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return qtrue;
432 int TryMergeLeaves(int l1num, int l2num)
434 int i, j, k, n, numportals;
435 visPlane_t plane1, plane2;
438 vportal_t *portals[MAX_PORTALS_ON_LEAF];
440 for (k = 0; k < 2; k++)
442 if (k) l1 = &leafs[l1num];
443 else l1 = &faceleafs[l1num];
444 for (i = 0; i < l1->numportals; i++)
447 if (p1->leaf == l2num) continue;
448 for (n = 0; n < 2; n++)
450 if (n) l2 = &leafs[l2num];
451 else l2 = &faceleafs[l2num];
452 for (j = 0; j < l2->numportals; j++)
455 if (p2->leaf == l1num) continue;
459 if (Winding_PlanesConcave(p1->winding, p2->winding, plane1.normal, plane2.normal, plane1.dist, plane2.dist))
465 for (k = 0; k < 2; k++)
474 l1 = &faceleafs[l1num];
475 l2 = &faceleafs[l2num];
478 //the leaves can be merged now
479 for (i = 0; i < l1->numportals; i++)
482 if (p1->leaf == l2num)
487 portals[numportals++] = p1;
489 for (j = 0; j < l2->numportals; j++)
492 if (p2->leaf == l1num)
497 portals[numportals++] = p2;
499 for (i = 0; i < numportals; i++)
501 l2->portals[i] = portals[i];
503 l2->numportals = numportals;
514 void UpdatePortals(void)
519 for (i = 0; i < numportals * 2; i++)
524 while(leafs[p->leaf].merged >= 0)
525 p->leaf = leafs[p->leaf].merged;
533 try to merge leaves but don't merge through hint splitters
536 void MergeLeaves(void)
538 int i, j, nummerges, totalnummerges;
546 for (i = 0; i < portalclusters; i++)
549 //if this leaf is merged already
551 /* ydnar: vmods: merge all non-hint portals */
552 if( leaf->merged >= 0 && hint == qfalse )
556 for (j = 0; j < leaf->numportals; j++)
558 p = leaf->portals[j];
562 //never merge through hint portals
565 if (TryMergeLeaves(i, p->leaf))
573 totalnummerges += nummerges;
575 Sys_Printf("%6d leaves merged\n", totalnummerges);
583 #define CONTINUOUS_EPSILON 0.005
585 fixedWinding_t *TryMergeWinding (fixedWinding_t *f1, fixedWinding_t *f2, vec3_t planenormal)
587 vec_t *p1, *p2, *p3, *p4, *back;
588 fixedWinding_t *newf;
590 vec3_t normal, delta;
592 qboolean keep1, keep2;
596 // find a common edge
598 p1 = p2 = NULL; // stop compiler warning
601 for (i = 0; i < f1->numpoints; i++)
604 p2 = f1->points[(i+1) % f1->numpoints];
605 for (j = 0; j < f2->numpoints; j++)
608 p4 = f2->points[(j+1) % f2->numpoints];
609 for (k = 0; k < 3; k++)
611 if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME
613 if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME
619 if (j < f2->numpoints)
623 if (i == f1->numpoints)
624 return NULL; // no matching edges
627 // check slope of connected lines
628 // if the slopes are colinear, the point can be removed
630 back = f1->points[(i+f1->numpoints-1)%f1->numpoints];
631 VectorSubtract (p1, back, delta);
632 CrossProduct (planenormal, delta, normal);
633 VectorNormalize (normal, normal);
635 back = f2->points[(j+2)%f2->numpoints];
636 VectorSubtract (back, p1, delta);
637 dot = DotProduct (delta, normal);
638 if (dot > CONTINUOUS_EPSILON)
639 return NULL; // not a convex polygon
640 keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
642 back = f1->points[(i+2)%f1->numpoints];
643 VectorSubtract (back, p2, delta);
644 CrossProduct (planenormal, delta, normal);
645 VectorNormalize (normal, normal);
647 back = f2->points[(j+f2->numpoints-1)%f2->numpoints];
648 VectorSubtract (back, p2, delta);
649 dot = DotProduct (delta, normal);
650 if (dot > CONTINUOUS_EPSILON)
651 return NULL; // not a convex polygon
652 keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);
655 // build the new polygon
657 newf = NewFixedWinding (f1->numpoints + f2->numpoints);
659 // copy first polygon
660 for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
662 if (k==(i+1)%f1->numpoints && !keep2)
665 VectorCopy (f1->points[k], newf->points[newf->numpoints]);
669 // copy second polygon
670 for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
672 if (l==(j+1)%f2->numpoints && !keep1)
674 VectorCopy (f2->points[l], newf->points[newf->numpoints]);
686 void MergeLeafPortals(void)
688 int i, j, k, nummerges, hintsmerged;
695 for (i = 0; i < portalclusters; i++)
698 if (leaf->merged >= 0) continue;
699 for (j = 0; j < leaf->numportals; j++)
701 p1 = leaf->portals[j];
704 for (k = j+1; k < leaf->numportals; k++)
706 p2 = leaf->portals[k];
709 if (p1->leaf == p2->leaf)
711 w = TryMergeWinding(p1->winding, p2->winding, p1->plane.normal);
714 free( p1->winding ); //% FreeWinding(p1->winding);
716 if (p1->hint && p2->hint)
718 p1->hint |= p2->hint;
727 if (k < leaf->numportals)
731 Sys_Printf("%6d portals merged\n", nummerges);
732 Sys_Printf("%6d hint portals merged\n", hintsmerged);
741 int CountActivePortals(void)
748 for (j = 0; j < numportals * 2; j++)
757 Sys_Printf("%6d active portals\n", num);
758 Sys_Printf("%6d hint portals\n", hints);
767 void WriteFloat (FILE *f, vec_t v);
769 void WritePortals(char *filename)
777 pf = fopen (filename, "w");
779 Error ("Error opening %s", filename);
782 for (j = 0; j < numportals * 2; j++)
792 fprintf (pf, "%s\n", PORTALFILE);
793 fprintf (pf, "%i\n", 0);
794 fprintf (pf, "%i\n", num);// + numfaces);
795 fprintf (pf, "%i\n", 0);
797 for (j = 0; j < numportals * 2; j++)
805 fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);
806 fprintf (pf, "%d ", p->hint);
807 for (i=0 ; i<w->numpoints ; i++)
810 WriteFloat (pf, w->points[i][0]);
811 WriteFloat (pf, w->points[i][1]);
812 WriteFloat (pf, w->points[i][2]);
819 for (j = 0; j < numfaces; j++)
823 fprintf (pf,"%i %i %i ",w->numpoints, 0, 0);
825 for (i=0 ; i<w->numpoints ; i++)
828 WriteFloat (pf, w->points[i][0]);
829 WriteFloat (pf, w->points[i][1]);
830 WriteFloat (pf, w->points[i][2]);
844 void LoadPortals (char *name)
856 if (!strcmp(name,"-"))
860 f = fopen(name, "r");
862 Error ("LoadPortals: couldn't read %s\n",name);
865 if (fscanf (f,"%79s\n%i\n%i\n%i\n",magic, &portalclusters, &numportals, &numfaces) != 4)
866 Error ("LoadPortals: failed to read header");
867 if (strcmp(magic,PORTALFILE))
868 Error ("LoadPortals: not a portal file");
870 Sys_Printf ("%6i portalclusters\n", portalclusters);
871 Sys_Printf ("%6i numportals\n", numportals);
872 Sys_Printf ("%6i numfaces\n", numfaces);
874 // these counts should take advantage of 64 bit systems automatically
875 leafbytes = ((portalclusters+63)&~63)>>3;
876 leaflongs = leafbytes/sizeof(long);
878 portalbytes = ((numportals*2+63)&~63)>>3;
879 portallongs = portalbytes/sizeof(long);
881 // each file portal is split into two memory portals
882 portals = safe_malloc(2*numportals*sizeof(vportal_t));
883 memset (portals, 0, 2*numportals*sizeof(vportal_t));
885 leafs = safe_malloc(portalclusters*sizeof(leaf_t));
886 memset (leafs, 0, portalclusters*sizeof(leaf_t));
888 for (i = 0; i < portalclusters; i++)
889 leafs[i].merged = -1;
891 numBSPVisBytes = VIS_HEADER_SIZE + portalclusters*leafbytes;
893 if (numBSPVisBytes > MAX_MAP_VISIBILITY)
894 Error("MAX_MAP_VISIBILITY exceeded");
896 ((int *)bspVisBytes)[0] = portalclusters;
897 ((int *)bspVisBytes)[1] = leafbytes;
899 for (i=0, p=portals ; i<numportals ; i++)
901 if (fscanf (f, "%i %i %i ", &numpoints, &leafnums[0], &leafnums[1]) != 3)
902 Error ("LoadPortals: reading portal %i", i);
903 if (numpoints > MAX_POINTS_ON_WINDING)
904 Error ("LoadPortals: portal %i has too many points", i);
905 if ( (unsigned)leafnums[0] > portalclusters
906 || (unsigned)leafnums[1] > portalclusters)
907 Error ("LoadPortals: reading portal %i", i);
908 if (fscanf (f, "%i ", &hint) != 1)
909 Error ("LoadPortals: reading hint state");
911 w = p->winding = NewFixedWinding (numpoints);
912 w->numpoints = numpoints;
914 for (j=0 ; j<numpoints ; j++)
919 // scanf into double, then assign to vec_t
920 // so we don't care what size vec_t is
921 if (fscanf (f, "(%lf %lf %lf ) "
922 , &v[0], &v[1], &v[2]) != 3)
923 Error ("LoadPortals: reading portal %i", i);
924 for (k=0 ; k<3 ; k++)
925 w->points[j][k] = v[k];
930 PlaneFromWinding (w, &plane);
932 // create forward portal
933 l = &leafs[leafnums[0]];
934 if (l->numportals == MAX_PORTALS_ON_LEAF)
935 Error ("Leaf with too many portals");
936 l->portals[l->numportals] = p;
942 VectorSubtract (vec3_origin, plane.normal, p->plane.normal);
943 p->plane.dist = -plane.dist;
944 p->leaf = leafnums[1];
948 // create backwards portal
949 l = &leafs[leafnums[1]];
950 if (l->numportals == MAX_PORTALS_ON_LEAF)
951 Error ("Leaf with too many portals");
952 l->portals[l->numportals] = p;
957 p->winding = NewFixedWinding(w->numpoints);
958 p->winding->numpoints = w->numpoints;
959 for (j=0 ; j<w->numpoints ; j++)
961 VectorCopy (w->points[w->numpoints-1-j], p->winding->points[j]);
965 p->leaf = leafnums[0];
971 faces = safe_malloc(2*numfaces*sizeof(vportal_t));
972 memset (faces, 0, 2*numfaces*sizeof(vportal_t));
974 faceleafs = safe_malloc(portalclusters*sizeof(leaf_t));
975 memset(faceleafs, 0, portalclusters*sizeof(leaf_t));
977 for (i = 0, p = faces; i < numfaces; i++)
979 if (fscanf (f, "%i %i ", &numpoints, &leafnums[0]) != 2)
980 Error ("LoadPortals: reading portal %i", i);
982 w = p->winding = NewFixedWinding (numpoints);
983 w->numpoints = numpoints;
985 for (j=0 ; j<numpoints ; j++)
990 // scanf into double, then assign to vec_t
991 // so we don't care what size vec_t is
992 if (fscanf (f, "(%lf %lf %lf ) "
993 , &v[0], &v[1], &v[2]) != 3)
994 Error ("LoadPortals: reading portal %i", i);
995 for (k=0 ; k<3 ; k++)
996 w->points[j][k] = v[k];
1001 PlaneFromWinding (w, &plane);
1003 l = &faceleafs[leafnums[0]];
1005 if (l->numportals == MAX_PORTALS_ON_LEAF)
1006 Error ("Leaf with too many faces");
1007 l->portals[l->numportals] = p;
1012 // normal pointing out of the leaf
1013 VectorSubtract (vec3_origin, plane.normal, p->plane.normal);
1014 p->plane.dist = -plane.dist;
1016 SetPortalSphere (p);
1030 int VisMain (int argc, char **argv)
1032 char portalfile[1024];
1037 Sys_Printf( "--- Vis ---\n" );
1039 /* process arguments */
1040 for (i=1 ; i < (argc - 1) ; i++)
1042 if (!strcmp(argv[i], "-fast")) {
1043 Sys_Printf ("fastvis = true\n");
1045 } else if (!strcmp(argv[i], "-merge")) {
1046 Sys_Printf ("merge = true\n");
1048 } else if (!strcmp(argv[i], "-nopassage")) {
1049 Sys_Printf ("nopassage = true\n");
1050 noPassageVis = qtrue;
1051 } else if (!strcmp(argv[i], "-passageOnly")) {
1052 Sys_Printf ("passageOnly = true\n");
1053 passageVisOnly = qtrue;
1054 } else if (!strcmp (argv[i],"-nosort")) {
1055 Sys_Printf ("nosort = true\n");
1057 } else if (!strcmp (argv[i],"-saveprt")) {
1058 Sys_Printf ("saveprt = true\n");
1060 } else if (!strcmp (argv[i],"-tmpin")) {
1061 strcpy (inbase, "/tmp");
1062 } else if (!strcmp (argv[i],"-tmpout")) {
1063 strcpy (outbase, "/tmp");
1067 /* ydnar: -hint to merge all but hint portals */
1068 else if( !strcmp( argv[ i ], "-hint" ) )
1070 Sys_Printf( "hint = true\n" );
1076 Sys_Printf( "WARNING: Unknown option \"%s\"\n", argv[ i ] );
1080 Error( "usage: vis [-threads #] [-level 0-4] [-fast] [-v] bspfile" );
1084 sprintf( source, "%s%s", inbase, ExpandArg( argv[ i ] ) );
1085 StripExtension( source );
1086 strcat( source, ".bsp" );
1087 Sys_Printf( "Loading %s\n", source );
1088 LoadBSPFile( source );
1090 /* load the portal file */
1091 sprintf( portalfile, "%s%s", inbase, ExpandArg( argv[ i ] ) );
1092 StripExtension( portalfile );
1093 strcat( portalfile, ".prt" );
1094 Sys_Printf( "Loading %s\n", portalfile );
1095 LoadPortals( portalfile );
1097 /* ydnar: for getting far plane */
1106 CountActivePortals();
1107 /* WritePortals( "maps/hints.prs" );*/
1109 Sys_Printf( "visdatasize:%i\n", numBSPVisBytes );
1113 /* delete the prt file */
1115 remove( portalfile );
1117 /* write the bsp file */
1118 Sys_Printf( "Writing %s\n", source );
1119 WriteBSPFile( source );