vis.c

Go to the documentation of this file.

/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.

This file is part of Quake III Arena source code.

Quake III Arena source code is free software; you can redistribute it
and/or modify it under the terms of the GNU General Public License as
published by the Free Software Foundation; either version 2 of the License,
or (at your option) any later version.

Quake III Arena source code is distributed in the hope that it will be
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
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 ; i<l->numportals ; 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<numportals*2 ; i++)
        sorted_portals[i] = &portals[i];

    if (nosort)
        return;
    qsort (sorted_portals, numportals*2, sizeof(sorted_portals[0]), PComp);
}


/*
==============
LeafVectorFromPortalVector
==============
*/
int LeafVectorFromPortalVector (byte *portalbits, byte *leafbits)
{
    int         i, j, leafnum;
    vportal_t   *p;
    int         c_leafs;


    for (i=0 ; i<numportals*2 ; i++)
    {
        if (portalbits[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 ; j<portallongs ; j++)
            ((long *)portalvector)[j] |= ((long *)p->portalvis)[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 ; i<numportals*2 ; i++)
    {
        portals[i].portalvis = portals[i].portalflood;
        portals[i].status = stat_done;
    }
}

/*
==================
CalcVis
==================
*/
void CalcVis (void)
{
    int     i;

    RunThreadsOnIndividual (numportals*2, qtrue, BasePortalVis);

//  RunThreadsOnIndividual (numportals*2, qtrue, BetterPortalVis);

    SortPortals ();

    if (fastvis) {
        CalcFastVis();
    }
    else if ( noPassageVis ) {
        CalcPortalVis();
    }
    else if ( passageVisOnly ) {
        CalcPassageVis();
    }
    else {
        CalcPassagePortalVis();
    }
    //
    // assemble the leaf vis lists by oring and compressing the portal lists
    //
    _printf("creating leaf vis...\n");
    for (i=0 ; i<portalclusters ; i++)
        ClusterMerge (i);

    _printf( "Total visible clusters: %i\n", totalvis );
    _printf( "Average clusters visible: %i\n", totalvis / portalclusters );
}

/*
==================
SetPortalSphere
==================
*/
void SetPortalSphere (vportal_t *p)
{
    int     i;
    vec3_t  total, dist;
    winding_t   *w;
    float   r, bestr;

    w = p->winding;
    VectorCopy (vec3_origin, total);
    for (i=0 ; i<w->numpoints ; i++)
    {
        VectorAdd (total, w->points[i], total);
    }
    
    for (i=0 ; i<3 ; i++)
        total[i] /= w->numpoints;

    bestr = 0;      
    for (i=0 ; i<w->numpoints ; 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 ; i<w->numpoints ; 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 ; i<w->numpoints ; 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<numportals ; i++)
    {
        if (fscanf (f, "%i %i %i ", &numpoints, &leafnums[0], &leafnums[1]) != 3)
            Error ("LoadPortals: reading portal %i", i);
        if (numpoints > 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 ; j<numpoints ; j++)
        {
            double  v[3];
            int     k;

            // scanf into double, then assign to vec_t
            // so we don't care what size vec_t is
            if (fscanf (f, "(%lf %lf %lf ) "
            , &v[0], &v[1], &v[2]) != 3)
                Error ("LoadPortals: reading portal %i", i);
            for (k=0 ; k<3 ; k++)
                w->points[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 ; j<w->numpoints ; 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 ; j<numpoints ; j++)
        {
            double  v[3];
            int     k;

            // scanf into double, then assign to vec_t
            // so we don't care what size vec_t is
            if (fscanf (f, "(%lf %lf %lf ) "
            , &v[0], &v[1], &v[2]) != 3)
                Error ("LoadPortals: reading portal %i", i);
            for (k=0 ; k<3 ; k++)
                w->points[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 ; i++)
    {
        scan = visBytes + i*leafbytes;
        memcpy (uncompressed, scan, leafbytes);
        for (j=0 ; j<leafbytes ; j++)
        {
            bitbyte = scan[j];
            if (!bitbyte)
                continue;
            for (k=0 ; k<8 ; k++)
            {
                if (! (bitbyte & (1<<k)) )
                    continue;
                // OR this pvs row into the phs
                index = ((j<<3)+k);
                if (index >= portalclusters)
                    Error ("Bad bit in PVS");   // pad bits should be 0
                src = (long *)(visBytes + index*leafbytes);
                dest = (long *)uncompressed;
                for (l=0 ; l<leaflongs ; l++)
                    ((long *)uncompressed)[l] |= src[l];
            }
        }
        for (j=0 ; j<portalclusters ; j++)
            if (uncompressed[j>>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<argc ; i++) {
        if (!strcmp(argv[i],"-threads")) {
            numthreads = atoi (argv[i+1]);
            i++;
        } else if (!strcmp(argv[i],"-threads")) {
            numthreads = atoi (argv[i+1]);
            i++;
        } else if (!strcmp(argv[i], "-fast")) {
            _printf ("fastvis = true\n");
            fastvis = qtrue;
        } else if (!strcmp(argv[i], "-merge")) {
            _printf ("merge = true\n");
            mergevis = qtrue;
        } else if (!strcmp(argv[i], "-nopassage")) {
            _printf ("nopassage = true\n");
            noPassageVis = qtrue;
        } else if (!strcmp(argv[i], "-passageOnly")) {
            _printf("passageOnly = true\n");
            passageVisOnly = qtrue;
        } else if (!strcmp(argv[i], "-level")) {
            testlevel = atoi(argv[i+1]);
            _printf ("testlevel = %i\n", testlevel);
            i++;
        } else if (!strcmp(argv[i], "-v")) {
            _printf ("verbose = true\n");
            verbose = qtrue;
        } else if (!strcmp (argv[i],"-nosort")) {
            _printf ("nosort = true\n");
            nosort = qtrue;
        } else if (!strcmp (argv[i],"-saveprt")) {
            _printf ("saveprt = true\n");
            saveprt = qtrue;
        } else if (!strcmp (argv[i],"-tmpin")) {
            strcpy (inbase, "/tmp");
        } else if (!strcmp (argv[i],"-tmpout")) {
            strcpy (outbase, "/tmp");
        } else if (argv[i][0] == '-') {
            Error ("Unknown option \"%s\"", argv[i]);
        } else {
            break;
        }
    }

    if (i != argc - 1)
        Error ("usage: vis [-threads #] [-level 0-4] [-fast] [-v] bspfile");

#ifdef MREDEBUG
    start = clock();
#else
    start = I_FloatTime ();
#endif
    
    ThreadSetDefault ();

    SetQdirFromPath (argv[i]);  

#ifdef _WIN32
  InitPakFile(gamedir, NULL);
#endif

    // load the bsp
    sprintf (name, "%s%s", inbase, ExpandArg(argv[i]));
    StripExtension (name);
    strcat (name, ".bsp");
    _printf ("reading %s\n", name);
    LoadBSPFile (name);

    // load the portal file
    sprintf (portalfile, "%s%s", inbase, ExpandArg(argv[i]));
    StripExtension (portalfile);
    strcat (portalfile, ".prt");
    _printf ("reading %s\n", portalfile);
    LoadPortals (portalfile);

    if (mergevis)
    {
        MergeLeaves();
        MergeLeafPortals();
    }

    CountActivePortals();
//  WritePortals("maps/hints.prs");

    _printf ("visdatasize:%i\n", numVisBytes);

    CalcVis ();

//  CalcPHS ();

    // delete the prt file
    if ( !saveprt ) {
        remove( portalfile );
    }

    // write the bsp file
    _printf ("writing %s\n", name);
    WriteBSPFile (name);

#ifdef MREDEBUG
    end = clock();
    _printf ("%5.2f seconds elapsed\n", (end-start) / CLK_TCK);
#else
    end = I_FloatTime ();
    _printf ("%5.2f seconds elapsed\n", end-start);
#endif
    return 0;
}

---