From 6bf20c78f5b69d40bcc4931df93d29198435ab67 Mon Sep 17 00:00:00 2001 From: zakk Date: Fri, 26 Aug 2005 17:39:27 +0000 Subject: newlines fixed git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea --- q3map/vis.c | 2352 +++++++++++++++++++++++++++++------------------------------ 1 file changed, 1176 insertions(+), 1176 deletions(-) (limited to 'q3map/vis.c') diff --git a/q3map/vis.c b/q3map/vis.c index 6baab38..329d192 100755 --- a/q3map/vis.c +++ b/q3map/vis.c @@ -19,1179 +19,1179 @@ along with Foobar; if not, write to the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA =========================================================================== */ -// vis.c - -#include "vis.h" -#include "threads.h" -#include "stdlib.h" -#ifdef _WIN32 -#include "../libs/pakstuff.h" -#endif - - -#define VIS_HEADER_SIZE 8 - -extern char outbase[32]; - -int numportals; -int portalclusters; -int numfaces; - -char inbase[32]; - -vportal_t *portals; -leaf_t *leafs; - -vportal_t *faces; -leaf_t *faceleafs; - -int c_portaltest, c_portalpass, c_portalcheck; - -int leafbytes; // (portalclusters+63)>>3 -int leaflongs; - -int portalbytes, portallongs; - -qboolean fastvis; -qboolean noPassageVis; -qboolean passageVisOnly; -qboolean mergevis; -qboolean nosort; -qboolean saveprt; - -int testlevel = 2; - -int totalvis; - -vportal_t *sorted_portals[MAX_MAP_PORTALS*2]; - -void PassageMemory(void); - - -//============================================================================= - -void PlaneFromWinding (winding_t *w, plane_t *plane) -{ - vec3_t v1, v2; - -// calc plane - VectorSubtract (w->points[2], w->points[1], v1); - VectorSubtract (w->points[0], w->points[1], v2); - CrossProduct (v2, v1, plane->normal); - VectorNormalize (plane->normal, plane->normal); - plane->dist = DotProduct (w->points[0], plane->normal); -} - - -/* -================== -NewWinding -================== -*/ -winding_t *NewWinding (int points) -{ - winding_t *w; - int size; - - if (points > MAX_POINTS_ON_WINDING) - Error ("NewWinding: %i points", points); - - size = (int)((winding_t *)0)->points[points]; - w = malloc (size); - memset (w, 0, size); - - return w; -} - - - -void prl(leaf_t *l) -{ - int i; - vportal_t *p; - plane_t pl; - - for (i=0 ; inumportals ; i++) - { - p = l->portals[i]; - pl = p->plane; - _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]); - } -} - - -//============================================================================= - -/* -============= -SortPortals - -Sorts the portals from the least complex, so the later ones can reuse -the earlier information. -============= -*/ -int PComp (const void *a, const void *b) -{ - if ( (*(vportal_t **)a)->nummightsee == (*(vportal_t **)b)->nummightsee) - return 0; - if ( (*(vportal_t **)a)->nummightsee < (*(vportal_t **)b)->nummightsee) - return -1; - return 1; -} -void SortPortals (void) -{ - int i; - - for (i=0 ; i>3] & (1<<(i&7)) ) - { - p = portals+i; - leafbits[p->leaf>>3] |= (1<<(p->leaf&7)); - } - } - - for (j = 0; j < portalclusters; j++) - { - leafnum = j; - while (leafs[leafnum].merged >= 0) - leafnum = leafs[leafnum].merged; - //if the merged leaf is visible then the original leaf is visible - if (leafbits[leafnum>>3] & (1<<(leafnum&7))) - { - leafbits[j>>3] |= (1<<(j&7)); - } - } - - c_leafs = CountBits (leafbits, portalclusters); - - return c_leafs; -} - - -/* -=============== -ClusterMerge - -Merges the portal visibility for a leaf -=============== -*/ -void ClusterMerge (int leafnum) -{ - leaf_t *leaf; - byte portalvector[MAX_PORTALS/8]; - byte uncompressed[MAX_MAP_LEAFS/8]; - int i, j; - int numvis, mergedleafnum; - vportal_t *p; - int pnum; - - // OR together all the portalvis bits - - mergedleafnum = leafnum; - while(leafs[mergedleafnum].merged >= 0) - mergedleafnum = leafs[mergedleafnum].merged; - - memset (portalvector, 0, portalbytes); - leaf = &leafs[mergedleafnum]; - for (i = 0; i < leaf->numportals; i++) - { - p = leaf->portals[i]; - if (p->removed) - continue; - - if (p->status != stat_done) - Error ("portal not done"); - for (j=0 ; jportalvis)[j]; - pnum = p - portals; - portalvector[pnum>>3] |= 1<<(pnum&7); - } - - memset (uncompressed, 0, leafbytes); - - uncompressed[mergedleafnum>>3] |= (1<<(mergedleafnum&7)); - // convert portal bits to leaf bits - numvis = LeafVectorFromPortalVector (portalvector, uncompressed); - -// if (uncompressed[leafnum>>3] & (1<<(leafnum&7))) -// _printf ("WARNING: Leaf portals saw into leaf\n"); - -// uncompressed[leafnum>>3] |= (1<<(leafnum&7)); - - numvis++; // count the leaf itself - - totalvis += numvis; - - qprintf ("cluster %4i : %4i visible\n", leafnum, numvis); - - memcpy (visBytes + VIS_HEADER_SIZE + leafnum*leafbytes, uncompressed, leafbytes); -} - -/* -================== -CalcPortalVis -================== -*/ -void CalcPortalVis (void) -{ -#ifdef MREDEBUG - _printf("%6d portals out of %d", 0, numportals*2); - //get rid of the counter - RunThreadsOnIndividual (numportals*2, qfalse, PortalFlow); -#else - RunThreadsOnIndividual (numportals*2, qtrue, PortalFlow); -#endif - -} - -/* -================== -CalcPassageVis -================== -*/ -void CalcPassageVis(void) -{ - PassageMemory(); - -#ifdef MREDEBUG - _printf("%6d portals out of %d", 0, numportals*2); - RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages); - _printf("\n"); - _printf("%6d portals out of %d", 0, numportals*2); - RunThreadsOnIndividual (numportals*2, qfalse, PassageFlow); - _printf("\n"); -#else - RunThreadsOnIndividual (numportals*2, qtrue, CreatePassages); - RunThreadsOnIndividual (numportals*2, qtrue, PassageFlow); -#endif -} - -/* -================== -CalcPassagePortalVis -================== -*/ -void CalcPassagePortalVis(void) -{ - PassageMemory(); - -#ifdef MREDEBUG - _printf("%6d portals out of %d", 0, numportals*2); - RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages); - _printf("\n"); - _printf("%6d portals out of %d", 0, numportals*2); - RunThreadsOnIndividual (numportals*2, qfalse, PassagePortalFlow); - _printf("\n"); -#else - RunThreadsOnIndividual (numportals*2, qtrue, CreatePassages); - RunThreadsOnIndividual (numportals*2, qtrue, PassagePortalFlow); -#endif -} - -/* -================== -CalcFastVis -================== -*/ -void CalcFastVis(void) -{ - int i; - - // fastvis just uses mightsee for a very loose bound - for (i=0 ; iwinding; - VectorCopy (vec3_origin, total); - for (i=0 ; inumpoints ; i++) - { - VectorAdd (total, w->points[i], total); - } - - for (i=0 ; i<3 ; i++) - total[i] /= w->numpoints; - - bestr = 0; - for (i=0 ; inumpoints ; i++) - { - VectorSubtract (w->points[i], total, dist); - r = VectorLength (dist); - if (r > bestr) - bestr = r; - } - VectorCopy (total, p->origin); - p->radius = bestr; -} - -/* -============= -Winding_PlanesConcave -============= -*/ -#define WCONVEX_EPSILON 0.2 - -int Winding_PlanesConcave(winding_t *w1, winding_t *w2, - vec3_t normal1, vec3_t normal2, - float dist1, float dist2) -{ - int i; - - if (!w1 || !w2) return qfalse; - - // check if one of the points of winding 1 is at the front of the plane of winding 2 - for (i = 0; i < w1->numpoints; i++) - { - if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return qtrue; - } - // check if one of the points of winding 2 is at the front of the plane of winding 1 - for (i = 0; i < w2->numpoints; i++) - { - if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return qtrue; - } - - return qfalse; -} - -/* -============ -TryMergeLeaves -============ -*/ -int TryMergeLeaves(int l1num, int l2num) -{ - int i, j, k, n, numportals; - plane_t plane1, plane2; - leaf_t *l1, *l2; - vportal_t *p1, *p2; - vportal_t *portals[MAX_PORTALS_ON_LEAF]; - - for (k = 0; k < 2; k++) - { - if (k) l1 = &leafs[l1num]; - else l1 = &faceleafs[l1num]; - for (i = 0; i < l1->numportals; i++) - { - p1 = l1->portals[i]; - if (p1->leaf == l2num) continue; - for (n = 0; n < 2; n++) - { - if (n) l2 = &leafs[l2num]; - else l2 = &faceleafs[l2num]; - for (j = 0; j < l2->numportals; j++) - { - p2 = l2->portals[j]; - if (p2->leaf == l1num) continue; - // - plane1 = p1->plane; - plane2 = p2->plane; - if (Winding_PlanesConcave(p1->winding, p2->winding, plane1.normal, plane2.normal, plane1.dist, plane2.dist)) - return qfalse; - } - } - } - } - for (k = 0; k < 2; k++) - { - if (k) - { - l1 = &leafs[l1num]; - l2 = &leafs[l2num]; - } - else - { - l1 = &faceleafs[l1num]; - l2 = &faceleafs[l2num]; - } - numportals = 0; - //the leaves can be merged now - for (i = 0; i < l1->numportals; i++) - { - p1 = l1->portals[i]; - if (p1->leaf == l2num) - { - p1->removed = qtrue; - continue; - } - portals[numportals++] = p1; - } - for (j = 0; j < l2->numportals; j++) - { - p2 = l2->portals[j]; - if (p2->leaf == l1num) - { - p2->removed = qtrue; - continue; - } - portals[numportals++] = p2; - } - for (i = 0; i < numportals; i++) - { - l2->portals[i] = portals[i]; - } - l2->numportals = numportals; - l1->merged = l2num; - } - return qtrue; -} - -/* -============ -UpdatePortals -============ -*/ -void UpdatePortals(void) -{ - int i; - vportal_t *p; - - for (i = 0; i < numportals * 2; i++) - { - p = &portals[i]; - if (p->removed) - continue; - while(leafs[p->leaf].merged >= 0) - p->leaf = leafs[p->leaf].merged; - } -} - -/* -============ -MergeLeaves - -try to merge leaves but don't merge through hint splitters -============ -*/ -void MergeLeaves(void) -{ - int i, j, nummerges, totalnummerges; - leaf_t *leaf; - vportal_t *p; - - totalnummerges = 0; - do - { - nummerges = 0; - for (i = 0; i < portalclusters; i++) - { - leaf = &leafs[i]; - //if this leaf is merged already - if (leaf->merged >= 0) - continue; - // - for (j = 0; j < leaf->numportals; j++) - { - p = leaf->portals[j]; - // - if (p->removed) - continue; - //never merge through hint portals - if (p->hint) - continue; - if (TryMergeLeaves(i, p->leaf)) - { - UpdatePortals(); - nummerges++; - break; - } - } - } - totalnummerges += nummerges; - } while (nummerges); - _printf("%6d leaves merged\n", totalnummerges); -} - -/* -============ -TryMergeWinding -============ -*/ -#define CONTINUOUS_EPSILON 0.005 - -winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, vec3_t planenormal) -{ - vec_t *p1, *p2, *p3, *p4, *back; - winding_t *newf; - int i, j, k, l; - vec3_t normal, delta; - vec_t dot; - qboolean keep1, keep2; - - - // - // find a common edge - // - p1 = p2 = NULL; // stop compiler warning - j = 0; // - - for (i = 0; i < f1->numpoints; i++) - { - p1 = f1->points[i]; - p2 = f1->points[(i+1) % f1->numpoints]; - for (j = 0; j < f2->numpoints; j++) - { - p3 = f2->points[j]; - p4 = f2->points[(j+1) % f2->numpoints]; - for (k = 0; k < 3; k++) - { - if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME - break; - if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME - break; - } //end for - if (k==3) - break; - } //end for - if (j < f2->numpoints) - break; - } //end for - - if (i == f1->numpoints) - return NULL; // no matching edges - - // - // check slope of connected lines - // if the slopes are colinear, the point can be removed - // - back = f1->points[(i+f1->numpoints-1)%f1->numpoints]; - VectorSubtract (p1, back, delta); - CrossProduct (planenormal, delta, normal); - VectorNormalize (normal, normal); - - back = f2->points[(j+2)%f2->numpoints]; - VectorSubtract (back, p1, delta); - dot = DotProduct (delta, normal); - if (dot > CONTINUOUS_EPSILON) - return NULL; // not a convex polygon - keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON); - - back = f1->points[(i+2)%f1->numpoints]; - VectorSubtract (back, p2, delta); - CrossProduct (planenormal, delta, normal); - VectorNormalize (normal, normal); - - back = f2->points[(j+f2->numpoints-1)%f2->numpoints]; - VectorSubtract (back, p2, delta); - dot = DotProduct (delta, normal); - if (dot > CONTINUOUS_EPSILON) - return NULL; // not a convex polygon - keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON); - - // - // build the new polygon - // - newf = NewWinding (f1->numpoints + f2->numpoints); - - // copy first polygon - for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints) - { - if (k==(i+1)%f1->numpoints && !keep2) - continue; - - VectorCopy (f1->points[k], newf->points[newf->numpoints]); - newf->numpoints++; - } - - // copy second polygon - for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints) - { - if (l==(j+1)%f2->numpoints && !keep1) - continue; - VectorCopy (f2->points[l], newf->points[newf->numpoints]); - newf->numpoints++; - } - - return newf; -} - -/* -============ -MergeLeafPortals -============ -*/ -void MergeLeafPortals(void) -{ - int i, j, k, nummerges, hintsmerged; - leaf_t *leaf; - vportal_t *p1, *p2; - winding_t *w; - - nummerges = 0; - hintsmerged = 0; - for (i = 0; i < portalclusters; i++) - { - leaf = &leafs[i]; - if (leaf->merged >= 0) continue; - for (j = 0; j < leaf->numportals; j++) - { - p1 = leaf->portals[j]; - if (p1->removed) - continue; - for (k = j+1; k < leaf->numportals; k++) - { - p2 = leaf->portals[k]; - if (p2->removed) - continue; - if (p1->leaf == p2->leaf) - { - w = TryMergeWinding(p1->winding, p2->winding, p1->plane.normal); - if (w) - { - FreeWinding(p1->winding); - p1->winding = w; - if (p1->hint && p2->hint) - hintsmerged++; - p1->hint |= p2->hint; - SetPortalSphere(p1); - p2->removed = qtrue; - nummerges++; - i--; - break; - } - } - } - if (k < leaf->numportals) - break; - } - } - _printf("%6d portals merged\n", nummerges); - _printf("%6d hint portals merged\n", hintsmerged); -} - - -/* -============ -WritePortals -============ -*/ -int CountActivePortals(void) -{ - int num, hints, j; - vportal_t *p; - - num = 0; - hints = 0; - for (j = 0; j < numportals * 2; j++) - { - p = portals + j; - if (p->removed) - continue; - if (p->hint) - hints++; - num++; - } - _printf("%6d active portals\n", num); - _printf("%6d hint portals\n", hints); - return num; -} - -/* -============ -WritePortals -============ -*/ -void WriteFloat (FILE *f, vec_t v); - -void WritePortals(char *filename) -{ - int i, j, num; - FILE *pf; - vportal_t *p; - winding_t *w; - - // write the file - pf = fopen (filename, "w"); - if (!pf) - Error ("Error opening %s", filename); - - num = 0; - for (j = 0; j < numportals * 2; j++) - { - p = portals + j; - if (p->removed) - continue; -// if (!p->hint) -// continue; - num++; - } - - fprintf (pf, "%s\n", PORTALFILE); - fprintf (pf, "%i\n", 0); - fprintf (pf, "%i\n", num);// + numfaces); - fprintf (pf, "%i\n", 0); - - for (j = 0; j < numportals * 2; j++) - { - p = portals + j; - if (p->removed) - continue; -// if (!p->hint) -// continue; - w = p->winding; - fprintf (pf,"%i %i %i ",w->numpoints, 0, 0); - fprintf (pf, "%d ", p->hint); - for (i=0 ; inumpoints ; i++) - { - fprintf (pf,"("); - WriteFloat (pf, w->points[i][0]); - WriteFloat (pf, w->points[i][1]); - WriteFloat (pf, w->points[i][2]); - fprintf (pf,") "); - } - fprintf (pf,"\n"); - } - - /* - for (j = 0; j < numfaces; j++) - { - p = faces + j; - w = p->winding; - fprintf (pf,"%i %i %i ",w->numpoints, 0, 0); - fprintf (pf, "0 "); - for (i=0 ; inumpoints ; i++) - { - fprintf (pf,"("); - WriteFloat (pf, w->points[i][0]); - WriteFloat (pf, w->points[i][1]); - WriteFloat (pf, w->points[i][2]); - fprintf (pf,") "); - } - fprintf (pf,"\n"); - }*/ - - fclose (pf); -} - -/* -============ -LoadPortals -============ -*/ -void LoadPortals (char *name) -{ - int i, j, hint; - vportal_t *p; - leaf_t *l; - char magic[80]; - FILE *f; - int numpoints; - winding_t *w; - int leafnums[2]; - plane_t plane; - - if (!strcmp(name,"-")) - f = stdin; - else - { - f = fopen(name, "r"); - if (!f) - Error ("LoadPortals: couldn't read %s\n",name); - } - - if (fscanf (f,"%79s\n%i\n%i\n%i\n",magic, &portalclusters, &numportals, &numfaces) != 4) - Error ("LoadPortals: failed to read header"); - if (strcmp(magic,PORTALFILE)) - Error ("LoadPortals: not a portal file"); - - _printf ("%6i portalclusters\n", portalclusters); - _printf ("%6i numportals\n", numportals); - _printf ("%6i numfaces\n", numfaces); - - // these counts should take advantage of 64 bit systems automatically - leafbytes = ((portalclusters+63)&~63)>>3; - leaflongs = leafbytes/sizeof(long); - - portalbytes = ((numportals*2+63)&~63)>>3; - portallongs = portalbytes/sizeof(long); - - // each file portal is split into two memory portals - portals = malloc(2*numportals*sizeof(vportal_t)); - memset (portals, 0, 2*numportals*sizeof(vportal_t)); - - leafs = malloc(portalclusters*sizeof(leaf_t)); - memset (leafs, 0, portalclusters*sizeof(leaf_t)); - - for (i = 0; i < portalclusters; i++) - leafs[i].merged = -1; - - numVisBytes = VIS_HEADER_SIZE + portalclusters*leafbytes; - - ((int *)visBytes)[0] = portalclusters; - ((int *)visBytes)[1] = leafbytes; - - for (i=0, p=portals ; i MAX_POINTS_ON_WINDING) - Error ("LoadPortals: portal %i has too many points", i); - if ( (unsigned)leafnums[0] > portalclusters - || (unsigned)leafnums[1] > portalclusters) - Error ("LoadPortals: reading portal %i", i); - if (fscanf (f, "%i ", &hint) != 1) - Error ("LoadPortals: reading hint state"); - - w = p->winding = NewWinding (numpoints); - w->numpoints = numpoints; - - for (j=0 ; jpoints[j][k] = v[k]; - } - fscanf (f, "\n"); - - // calc plane - PlaneFromWinding (w, &plane); - - // create forward portal - l = &leafs[leafnums[0]]; - if (l->numportals == MAX_PORTALS_ON_LEAF) - Error ("Leaf with too many portals"); - l->portals[l->numportals] = p; - l->numportals++; - - p->num = i+1; - p->hint = hint; - p->winding = w; - VectorSubtract (vec3_origin, plane.normal, p->plane.normal); - p->plane.dist = -plane.dist; - p->leaf = leafnums[1]; - SetPortalSphere (p); - p++; - - // create backwards portal - l = &leafs[leafnums[1]]; - if (l->numportals == MAX_PORTALS_ON_LEAF) - Error ("Leaf with too many portals"); - l->portals[l->numportals] = p; - l->numportals++; - - p->num = i+1; - p->hint = hint; - p->winding = NewWinding(w->numpoints); - p->winding->numpoints = w->numpoints; - for (j=0 ; jnumpoints ; j++) - { - VectorCopy (w->points[w->numpoints-1-j], p->winding->points[j]); - } - - p->plane = plane; - p->leaf = leafnums[0]; - SetPortalSphere (p); - p++; - - } - - faces = malloc(2*numfaces*sizeof(vportal_t)); - memset (faces, 0, 2*numfaces*sizeof(vportal_t)); - - faceleafs = malloc(portalclusters*sizeof(leaf_t)); - memset(faceleafs, 0, portalclusters*sizeof(leaf_t)); - - for (i = 0, p = faces; i < numfaces; i++) - { - if (fscanf (f, "%i %i ", &numpoints, &leafnums[0]) != 2) - Error ("LoadPortals: reading portal %i", i); - - w = p->winding = NewWinding (numpoints); - w->numpoints = numpoints; - - for (j=0 ; jpoints[j][k] = v[k]; - } - fscanf (f, "\n"); - - // calc plane - PlaneFromWinding (w, &plane); - - l = &faceleafs[leafnums[0]]; - l->merged = -1; - if (l->numportals == MAX_PORTALS_ON_LEAF) - Error ("Leaf with too many faces"); - l->portals[l->numportals] = p; - l->numportals++; - - p->num = i+1; - p->winding = w; - // normal pointing out of the leaf - VectorSubtract (vec3_origin, plane.normal, p->plane.normal); - p->plane.dist = -plane.dist; - p->leaf = -1; - SetPortalSphere (p); - p++; - } - - fclose (f); -} - - -/* -================ -CalcPHS - -Calculate the PHS (Potentially Hearable Set) -by ORing together all the PVS visible from a leaf -================ -*/ -void CalcPHS (void) -{ - int i, j, k, l, index; - int bitbyte; - long *dest, *src; - byte *scan; - int count; - byte uncompressed[MAX_MAP_LEAFS/8]; - - _printf ("Building PHS...\n"); - - count = 0; - for (i=0 ; i= portalclusters) - Error ("Bad bit in PVS"); // pad bits should be 0 - src = (long *)(visBytes + index*leafbytes); - dest = (long *)uncompressed; - for (l=0 ; l>3] & (1<<(j&7)) ) - count++; - - // FIXME: copy it off - } - - _printf ("Average clusters hearable: %i\n", count/portalclusters); -} - -/* -=========== -VisMain -=========== -*/ -int VisMain (int argc, char **argv) -{ - char portalfile[1024]; - char name[1024]; - int i; - double start, end; - - _printf ("---- vis ----\n"); - - verbose = qfalse; - for (i=1 ; i>3 +int leaflongs; + +int portalbytes, portallongs; + +qboolean fastvis; +qboolean noPassageVis; +qboolean passageVisOnly; +qboolean mergevis; +qboolean nosort; +qboolean saveprt; + +int testlevel = 2; + +int totalvis; + +vportal_t *sorted_portals[MAX_MAP_PORTALS*2]; + +void PassageMemory(void); + + +//============================================================================= + +void PlaneFromWinding (winding_t *w, plane_t *plane) +{ + vec3_t v1, v2; + +// calc plane + VectorSubtract (w->points[2], w->points[1], v1); + VectorSubtract (w->points[0], w->points[1], v2); + CrossProduct (v2, v1, plane->normal); + VectorNormalize (plane->normal, plane->normal); + plane->dist = DotProduct (w->points[0], plane->normal); +} + + +/* +================== +NewWinding +================== +*/ +winding_t *NewWinding (int points) +{ + winding_t *w; + int size; + + if (points > MAX_POINTS_ON_WINDING) + Error ("NewWinding: %i points", points); + + size = (int)((winding_t *)0)->points[points]; + w = malloc (size); + memset (w, 0, size); + + return w; +} + + + +void prl(leaf_t *l) +{ + int i; + vportal_t *p; + plane_t pl; + + for (i=0 ; inumportals ; i++) + { + p = l->portals[i]; + pl = p->plane; + _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]); + } +} + + +//============================================================================= + +/* +============= +SortPortals + +Sorts the portals from the least complex, so the later ones can reuse +the earlier information. +============= +*/ +int PComp (const void *a, const void *b) +{ + if ( (*(vportal_t **)a)->nummightsee == (*(vportal_t **)b)->nummightsee) + return 0; + if ( (*(vportal_t **)a)->nummightsee < (*(vportal_t **)b)->nummightsee) + return -1; + return 1; +} +void SortPortals (void) +{ + int i; + + for (i=0 ; i>3] & (1<<(i&7)) ) + { + p = portals+i; + leafbits[p->leaf>>3] |= (1<<(p->leaf&7)); + } + } + + for (j = 0; j < portalclusters; j++) + { + leafnum = j; + while (leafs[leafnum].merged >= 0) + leafnum = leafs[leafnum].merged; + //if the merged leaf is visible then the original leaf is visible + if (leafbits[leafnum>>3] & (1<<(leafnum&7))) + { + leafbits[j>>3] |= (1<<(j&7)); + } + } + + c_leafs = CountBits (leafbits, portalclusters); + + return c_leafs; +} + + +/* +=============== +ClusterMerge + +Merges the portal visibility for a leaf +=============== +*/ +void ClusterMerge (int leafnum) +{ + leaf_t *leaf; + byte portalvector[MAX_PORTALS/8]; + byte uncompressed[MAX_MAP_LEAFS/8]; + int i, j; + int numvis, mergedleafnum; + vportal_t *p; + int pnum; + + // OR together all the portalvis bits + + mergedleafnum = leafnum; + while(leafs[mergedleafnum].merged >= 0) + mergedleafnum = leafs[mergedleafnum].merged; + + memset (portalvector, 0, portalbytes); + leaf = &leafs[mergedleafnum]; + for (i = 0; i < leaf->numportals; i++) + { + p = leaf->portals[i]; + if (p->removed) + continue; + + if (p->status != stat_done) + Error ("portal not done"); + for (j=0 ; jportalvis)[j]; + pnum = p - portals; + portalvector[pnum>>3] |= 1<<(pnum&7); + } + + memset (uncompressed, 0, leafbytes); + + uncompressed[mergedleafnum>>3] |= (1<<(mergedleafnum&7)); + // convert portal bits to leaf bits + numvis = LeafVectorFromPortalVector (portalvector, uncompressed); + +// if (uncompressed[leafnum>>3] & (1<<(leafnum&7))) +// _printf ("WARNING: Leaf portals saw into leaf\n"); + +// uncompressed[leafnum>>3] |= (1<<(leafnum&7)); + + numvis++; // count the leaf itself + + totalvis += numvis; + + qprintf ("cluster %4i : %4i visible\n", leafnum, numvis); + + memcpy (visBytes + VIS_HEADER_SIZE + leafnum*leafbytes, uncompressed, leafbytes); +} + +/* +================== +CalcPortalVis +================== +*/ +void CalcPortalVis (void) +{ +#ifdef MREDEBUG + _printf("%6d portals out of %d", 0, numportals*2); + //get rid of the counter + RunThreadsOnIndividual (numportals*2, qfalse, PortalFlow); +#else + RunThreadsOnIndividual (numportals*2, qtrue, PortalFlow); +#endif + +} + +/* +================== +CalcPassageVis +================== +*/ +void CalcPassageVis(void) +{ + PassageMemory(); + +#ifdef MREDEBUG + _printf("%6d portals out of %d", 0, numportals*2); + RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages); + _printf("\n"); + _printf("%6d portals out of %d", 0, numportals*2); + RunThreadsOnIndividual (numportals*2, qfalse, PassageFlow); + _printf("\n"); +#else + RunThreadsOnIndividual (numportals*2, qtrue, CreatePassages); + RunThreadsOnIndividual (numportals*2, qtrue, PassageFlow); +#endif +} + +/* +================== +CalcPassagePortalVis +================== +*/ +void CalcPassagePortalVis(void) +{ + PassageMemory(); + +#ifdef MREDEBUG + _printf("%6d portals out of %d", 0, numportals*2); + RunThreadsOnIndividual (numportals*2, qfalse, CreatePassages); + _printf("\n"); + _printf("%6d portals out of %d", 0, numportals*2); + RunThreadsOnIndividual (numportals*2, qfalse, PassagePortalFlow); + _printf("\n"); +#else + RunThreadsOnIndividual (numportals*2, qtrue, CreatePassages); + RunThreadsOnIndividual (numportals*2, qtrue, PassagePortalFlow); +#endif +} + +/* +================== +CalcFastVis +================== +*/ +void CalcFastVis(void) +{ + int i; + + // fastvis just uses mightsee for a very loose bound + for (i=0 ; iwinding; + VectorCopy (vec3_origin, total); + for (i=0 ; inumpoints ; i++) + { + VectorAdd (total, w->points[i], total); + } + + for (i=0 ; i<3 ; i++) + total[i] /= w->numpoints; + + bestr = 0; + for (i=0 ; inumpoints ; i++) + { + VectorSubtract (w->points[i], total, dist); + r = VectorLength (dist); + if (r > bestr) + bestr = r; + } + VectorCopy (total, p->origin); + p->radius = bestr; +} + +/* +============= +Winding_PlanesConcave +============= +*/ +#define WCONVEX_EPSILON 0.2 + +int Winding_PlanesConcave(winding_t *w1, winding_t *w2, + vec3_t normal1, vec3_t normal2, + float dist1, float dist2) +{ + int i; + + if (!w1 || !w2) return qfalse; + + // check if one of the points of winding 1 is at the front of the plane of winding 2 + for (i = 0; i < w1->numpoints; i++) + { + if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return qtrue; + } + // check if one of the points of winding 2 is at the front of the plane of winding 1 + for (i = 0; i < w2->numpoints; i++) + { + if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return qtrue; + } + + return qfalse; +} + +/* +============ +TryMergeLeaves +============ +*/ +int TryMergeLeaves(int l1num, int l2num) +{ + int i, j, k, n, numportals; + plane_t plane1, plane2; + leaf_t *l1, *l2; + vportal_t *p1, *p2; + vportal_t *portals[MAX_PORTALS_ON_LEAF]; + + for (k = 0; k < 2; k++) + { + if (k) l1 = &leafs[l1num]; + else l1 = &faceleafs[l1num]; + for (i = 0; i < l1->numportals; i++) + { + p1 = l1->portals[i]; + if (p1->leaf == l2num) continue; + for (n = 0; n < 2; n++) + { + if (n) l2 = &leafs[l2num]; + else l2 = &faceleafs[l2num]; + for (j = 0; j < l2->numportals; j++) + { + p2 = l2->portals[j]; + if (p2->leaf == l1num) continue; + // + plane1 = p1->plane; + plane2 = p2->plane; + if (Winding_PlanesConcave(p1->winding, p2->winding, plane1.normal, plane2.normal, plane1.dist, plane2.dist)) + return qfalse; + } + } + } + } + for (k = 0; k < 2; k++) + { + if (k) + { + l1 = &leafs[l1num]; + l2 = &leafs[l2num]; + } + else + { + l1 = &faceleafs[l1num]; + l2 = &faceleafs[l2num]; + } + numportals = 0; + //the leaves can be merged now + for (i = 0; i < l1->numportals; i++) + { + p1 = l1->portals[i]; + if (p1->leaf == l2num) + { + p1->removed = qtrue; + continue; + } + portals[numportals++] = p1; + } + for (j = 0; j < l2->numportals; j++) + { + p2 = l2->portals[j]; + if (p2->leaf == l1num) + { + p2->removed = qtrue; + continue; + } + portals[numportals++] = p2; + } + for (i = 0; i < numportals; i++) + { + l2->portals[i] = portals[i]; + } + l2->numportals = numportals; + l1->merged = l2num; + } + return qtrue; +} + +/* +============ +UpdatePortals +============ +*/ +void UpdatePortals(void) +{ + int i; + vportal_t *p; + + for (i = 0; i < numportals * 2; i++) + { + p = &portals[i]; + if (p->removed) + continue; + while(leafs[p->leaf].merged >= 0) + p->leaf = leafs[p->leaf].merged; + } +} + +/* +============ +MergeLeaves + +try to merge leaves but don't merge through hint splitters +============ +*/ +void MergeLeaves(void) +{ + int i, j, nummerges, totalnummerges; + leaf_t *leaf; + vportal_t *p; + + totalnummerges = 0; + do + { + nummerges = 0; + for (i = 0; i < portalclusters; i++) + { + leaf = &leafs[i]; + //if this leaf is merged already + if (leaf->merged >= 0) + continue; + // + for (j = 0; j < leaf->numportals; j++) + { + p = leaf->portals[j]; + // + if (p->removed) + continue; + //never merge through hint portals + if (p->hint) + continue; + if (TryMergeLeaves(i, p->leaf)) + { + UpdatePortals(); + nummerges++; + break; + } + } + } + totalnummerges += nummerges; + } while (nummerges); + _printf("%6d leaves merged\n", totalnummerges); +} + +/* +============ +TryMergeWinding +============ +*/ +#define CONTINUOUS_EPSILON 0.005 + +winding_t *TryMergeWinding (winding_t *f1, winding_t *f2, vec3_t planenormal) +{ + vec_t *p1, *p2, *p3, *p4, *back; + winding_t *newf; + int i, j, k, l; + vec3_t normal, delta; + vec_t dot; + qboolean keep1, keep2; + + + // + // find a common edge + // + p1 = p2 = NULL; // stop compiler warning + j = 0; // + + for (i = 0; i < f1->numpoints; i++) + { + p1 = f1->points[i]; + p2 = f1->points[(i+1) % f1->numpoints]; + for (j = 0; j < f2->numpoints; j++) + { + p3 = f2->points[j]; + p4 = f2->points[(j+1) % f2->numpoints]; + for (k = 0; k < 3; k++) + { + if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME + break; + if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME + break; + } //end for + if (k==3) + break; + } //end for + if (j < f2->numpoints) + break; + } //end for + + if (i == f1->numpoints) + return NULL; // no matching edges + + // + // check slope of connected lines + // if the slopes are colinear, the point can be removed + // + back = f1->points[(i+f1->numpoints-1)%f1->numpoints]; + VectorSubtract (p1, back, delta); + CrossProduct (planenormal, delta, normal); + VectorNormalize (normal, normal); + + back = f2->points[(j+2)%f2->numpoints]; + VectorSubtract (back, p1, delta); + dot = DotProduct (delta, normal); + if (dot > CONTINUOUS_EPSILON) + return NULL; // not a convex polygon + keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON); + + back = f1->points[(i+2)%f1->numpoints]; + VectorSubtract (back, p2, delta); + CrossProduct (planenormal, delta, normal); + VectorNormalize (normal, normal); + + back = f2->points[(j+f2->numpoints-1)%f2->numpoints]; + VectorSubtract (back, p2, delta); + dot = DotProduct (delta, normal); + if (dot > CONTINUOUS_EPSILON) + return NULL; // not a convex polygon + keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON); + + // + // build the new polygon + // + newf = NewWinding (f1->numpoints + f2->numpoints); + + // copy first polygon + for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints) + { + if (k==(i+1)%f1->numpoints && !keep2) + continue; + + VectorCopy (f1->points[k], newf->points[newf->numpoints]); + newf->numpoints++; + } + + // copy second polygon + for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints) + { + if (l==(j+1)%f2->numpoints && !keep1) + continue; + VectorCopy (f2->points[l], newf->points[newf->numpoints]); + newf->numpoints++; + } + + return newf; +} + +/* +============ +MergeLeafPortals +============ +*/ +void MergeLeafPortals(void) +{ + int i, j, k, nummerges, hintsmerged; + leaf_t *leaf; + vportal_t *p1, *p2; + winding_t *w; + + nummerges = 0; + hintsmerged = 0; + for (i = 0; i < portalclusters; i++) + { + leaf = &leafs[i]; + if (leaf->merged >= 0) continue; + for (j = 0; j < leaf->numportals; j++) + { + p1 = leaf->portals[j]; + if (p1->removed) + continue; + for (k = j+1; k < leaf->numportals; k++) + { + p2 = leaf->portals[k]; + if (p2->removed) + continue; + if (p1->leaf == p2->leaf) + { + w = TryMergeWinding(p1->winding, p2->winding, p1->plane.normal); + if (w) + { + FreeWinding(p1->winding); + p1->winding = w; + if (p1->hint && p2->hint) + hintsmerged++; + p1->hint |= p2->hint; + SetPortalSphere(p1); + p2->removed = qtrue; + nummerges++; + i--; + break; + } + } + } + if (k < leaf->numportals) + break; + } + } + _printf("%6d portals merged\n", nummerges); + _printf("%6d hint portals merged\n", hintsmerged); +} + + +/* +============ +WritePortals +============ +*/ +int CountActivePortals(void) +{ + int num, hints, j; + vportal_t *p; + + num = 0; + hints = 0; + for (j = 0; j < numportals * 2; j++) + { + p = portals + j; + if (p->removed) + continue; + if (p->hint) + hints++; + num++; + } + _printf("%6d active portals\n", num); + _printf("%6d hint portals\n", hints); + return num; +} + +/* +============ +WritePortals +============ +*/ +void WriteFloat (FILE *f, vec_t v); + +void WritePortals(char *filename) +{ + int i, j, num; + FILE *pf; + vportal_t *p; + winding_t *w; + + // write the file + pf = fopen (filename, "w"); + if (!pf) + Error ("Error opening %s", filename); + + num = 0; + for (j = 0; j < numportals * 2; j++) + { + p = portals + j; + if (p->removed) + continue; +// if (!p->hint) +// continue; + num++; + } + + fprintf (pf, "%s\n", PORTALFILE); + fprintf (pf, "%i\n", 0); + fprintf (pf, "%i\n", num);// + numfaces); + fprintf (pf, "%i\n", 0); + + for (j = 0; j < numportals * 2; j++) + { + p = portals + j; + if (p->removed) + continue; +// if (!p->hint) +// continue; + w = p->winding; + fprintf (pf,"%i %i %i ",w->numpoints, 0, 0); + fprintf (pf, "%d ", p->hint); + for (i=0 ; inumpoints ; i++) + { + fprintf (pf,"("); + WriteFloat (pf, w->points[i][0]); + WriteFloat (pf, w->points[i][1]); + WriteFloat (pf, w->points[i][2]); + fprintf (pf,") "); + } + fprintf (pf,"\n"); + } + + /* + for (j = 0; j < numfaces; j++) + { + p = faces + j; + w = p->winding; + fprintf (pf,"%i %i %i ",w->numpoints, 0, 0); + fprintf (pf, "0 "); + for (i=0 ; inumpoints ; i++) + { + fprintf (pf,"("); + WriteFloat (pf, w->points[i][0]); + WriteFloat (pf, w->points[i][1]); + WriteFloat (pf, w->points[i][2]); + fprintf (pf,") "); + } + fprintf (pf,"\n"); + }*/ + + fclose (pf); +} + +/* +============ +LoadPortals +============ +*/ +void LoadPortals (char *name) +{ + int i, j, hint; + vportal_t *p; + leaf_t *l; + char magic[80]; + FILE *f; + int numpoints; + winding_t *w; + int leafnums[2]; + plane_t plane; + + if (!strcmp(name,"-")) + f = stdin; + else + { + f = fopen(name, "r"); + if (!f) + Error ("LoadPortals: couldn't read %s\n",name); + } + + if (fscanf (f,"%79s\n%i\n%i\n%i\n",magic, &portalclusters, &numportals, &numfaces) != 4) + Error ("LoadPortals: failed to read header"); + if (strcmp(magic,PORTALFILE)) + Error ("LoadPortals: not a portal file"); + + _printf ("%6i portalclusters\n", portalclusters); + _printf ("%6i numportals\n", numportals); + _printf ("%6i numfaces\n", numfaces); + + // these counts should take advantage of 64 bit systems automatically + leafbytes = ((portalclusters+63)&~63)>>3; + leaflongs = leafbytes/sizeof(long); + + portalbytes = ((numportals*2+63)&~63)>>3; + portallongs = portalbytes/sizeof(long); + + // each file portal is split into two memory portals + portals = malloc(2*numportals*sizeof(vportal_t)); + memset (portals, 0, 2*numportals*sizeof(vportal_t)); + + leafs = malloc(portalclusters*sizeof(leaf_t)); + memset (leafs, 0, portalclusters*sizeof(leaf_t)); + + for (i = 0; i < portalclusters; i++) + leafs[i].merged = -1; + + numVisBytes = VIS_HEADER_SIZE + portalclusters*leafbytes; + + ((int *)visBytes)[0] = portalclusters; + ((int *)visBytes)[1] = leafbytes; + + for (i=0, p=portals ; i MAX_POINTS_ON_WINDING) + Error ("LoadPortals: portal %i has too many points", i); + if ( (unsigned)leafnums[0] > portalclusters + || (unsigned)leafnums[1] > portalclusters) + Error ("LoadPortals: reading portal %i", i); + if (fscanf (f, "%i ", &hint) != 1) + Error ("LoadPortals: reading hint state"); + + w = p->winding = NewWinding (numpoints); + w->numpoints = numpoints; + + for (j=0 ; jpoints[j][k] = v[k]; + } + fscanf (f, "\n"); + + // calc plane + PlaneFromWinding (w, &plane); + + // create forward portal + l = &leafs[leafnums[0]]; + if (l->numportals == MAX_PORTALS_ON_LEAF) + Error ("Leaf with too many portals"); + l->portals[l->numportals] = p; + l->numportals++; + + p->num = i+1; + p->hint = hint; + p->winding = w; + VectorSubtract (vec3_origin, plane.normal, p->plane.normal); + p->plane.dist = -plane.dist; + p->leaf = leafnums[1]; + SetPortalSphere (p); + p++; + + // create backwards portal + l = &leafs[leafnums[1]]; + if (l->numportals == MAX_PORTALS_ON_LEAF) + Error ("Leaf with too many portals"); + l->portals[l->numportals] = p; + l->numportals++; + + p->num = i+1; + p->hint = hint; + p->winding = NewWinding(w->numpoints); + p->winding->numpoints = w->numpoints; + for (j=0 ; jnumpoints ; j++) + { + VectorCopy (w->points[w->numpoints-1-j], p->winding->points[j]); + } + + p->plane = plane; + p->leaf = leafnums[0]; + SetPortalSphere (p); + p++; + + } + + faces = malloc(2*numfaces*sizeof(vportal_t)); + memset (faces, 0, 2*numfaces*sizeof(vportal_t)); + + faceleafs = malloc(portalclusters*sizeof(leaf_t)); + memset(faceleafs, 0, portalclusters*sizeof(leaf_t)); + + for (i = 0, p = faces; i < numfaces; i++) + { + if (fscanf (f, "%i %i ", &numpoints, &leafnums[0]) != 2) + Error ("LoadPortals: reading portal %i", i); + + w = p->winding = NewWinding (numpoints); + w->numpoints = numpoints; + + for (j=0 ; jpoints[j][k] = v[k]; + } + fscanf (f, "\n"); + + // calc plane + PlaneFromWinding (w, &plane); + + l = &faceleafs[leafnums[0]]; + l->merged = -1; + if (l->numportals == MAX_PORTALS_ON_LEAF) + Error ("Leaf with too many faces"); + l->portals[l->numportals] = p; + l->numportals++; + + p->num = i+1; + p->winding = w; + // normal pointing out of the leaf + VectorSubtract (vec3_origin, plane.normal, p->plane.normal); + p->plane.dist = -plane.dist; + p->leaf = -1; + SetPortalSphere (p); + p++; + } + + fclose (f); +} + + +/* +================ +CalcPHS + +Calculate the PHS (Potentially Hearable Set) +by ORing together all the PVS visible from a leaf +================ +*/ +void CalcPHS (void) +{ + int i, j, k, l, index; + int bitbyte; + long *dest, *src; + byte *scan; + int count; + byte uncompressed[MAX_MAP_LEAFS/8]; + + _printf ("Building PHS...\n"); + + count = 0; + for (i=0 ; i= portalclusters) + Error ("Bad bit in PVS"); // pad bits should be 0 + src = (long *)(visBytes + index*leafbytes); + dest = (long *)uncompressed; + for (l=0 ; l>3] & (1<<(j&7)) ) + count++; + + // FIXME: copy it off + } + + _printf ("Average clusters hearable: %i\n", count/portalclusters); +} + +/* +=========== +VisMain +=========== +*/ +int VisMain (int argc, char **argv) +{ + char portalfile[1024]; + char name[1024]; + int i; + double start, end; + + _printf ("---- vis ----\n"); + + verbose = qfalse; + for (i=1 ; i