visflow.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
===========================================================================
*/
#include "vis.h"

/*

  each portal will have a list of all possible to see from first portal

  if (!thread->portalmightsee[portalnum])

  portal mightsee

  for p2 = all other portals in leaf
    get sperating planes
    for all portals that might be seen by p2
        mark as unseen if not present in seperating plane
    flood fill a new mightsee
    save as passagemightsee


  void CalcMightSee (leaf_t *leaf, 
*/

int CountBits (byte *bits, int numbits)
{
    int     i;
    int     c;

    c = 0;
    for (i=0 ; i<numbits ; i++)
        if (bits[i>>3] & (1<<(i&7)) )
            c++;

    return c;
}

int     c_fullskip;
int     c_portalskip, c_leafskip;
int     c_vistest, c_mighttest;

int     c_chop, c_nochop;

int     active;

void CheckStack (leaf_t *leaf, threaddata_t *thread)
{
    pstack_t    *p, *p2;

    for (p=thread->pstack_head.next ; p ; p=p->next)
    {
//      _printf ("=");
        if (p->leaf == leaf)
            Error ("CheckStack: leaf recursion");
        for (p2=thread->pstack_head.next ; p2 != p ; p2=p2->next)
            if (p2->leaf == p->leaf)
                Error ("CheckStack: late leaf recursion");
    }
//  _printf ("\n");
}


winding_t *AllocStackWinding (pstack_t *stack)
{
    int     i;

    for (i=0 ; i<3 ; i++)
    {
        if (stack->freewindings[i])
        {
            stack->freewindings[i] = 0;
            return &stack->windings[i];
        }
    }

    Error ("AllocStackWinding: failed");

    return NULL;
}

void FreeStackWinding (winding_t *w, pstack_t *stack)
{
    int     i;

    i = w - stack->windings;

    if (i<0 || i>2)
        return;     // not from local

    if (stack->freewindings[i])
        Error ("FreeStackWinding: allready free");
    stack->freewindings[i] = 1;
}

/*
==============
VisChopWinding

==============
*/
winding_t   *VisChopWinding (winding_t *in, pstack_t *stack, plane_t *split)
{
    vec_t   dists[128];
    int     sides[128];
    int     counts[3];
    vec_t   dot;
    int     i, j;
    vec_t   *p1, *p2;
    vec3_t  mid;
    winding_t   *neww;

    counts[0] = counts[1] = counts[2] = 0;

    // determine sides for each point
    for (i=0 ; i<in->numpoints ; i++)
    {
        dot = DotProduct (in->points[i], split->normal);
        dot -= split->dist;
        dists[i] = dot;
        if (dot > ON_EPSILON)
            sides[i] = SIDE_FRONT;
        else if (dot < -ON_EPSILON)
            sides[i] = SIDE_BACK;
        else
        {
            sides[i] = SIDE_ON;
        }
        counts[sides[i]]++;
    }

    if (!counts[1])
        return in;      // completely on front side
    
    if (!counts[0])
    {
        FreeStackWinding (in, stack);
        return NULL;
    }

    sides[i] = sides[0];
    dists[i] = dists[0];
    
    neww = AllocStackWinding (stack);

    neww->numpoints = 0;

    for (i=0 ; i<in->numpoints ; i++)
    {
        p1 = in->points[i];

        if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
        {
            FreeStackWinding (neww, stack);
            return in;      // can't chop -- fall back to original
        }

        if (sides[i] == SIDE_ON)
        {
            VectorCopy (p1, neww->points[neww->numpoints]);
            neww->numpoints++;
            continue;
        }
    
        if (sides[i] == SIDE_FRONT)
        {
            VectorCopy (p1, neww->points[neww->numpoints]);
            neww->numpoints++;
        }
        
        if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
            continue;
            
        if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
        {
            FreeStackWinding (neww, stack);
            return in;      // can't chop -- fall back to original
        }

        // generate a split point
        p2 = in->points[(i+1)%in->numpoints];
        
        dot = dists[i] / (dists[i]-dists[i+1]);
        for (j=0 ; j<3 ; j++)
        {   // avoid round off error when possible
            if (split->normal[j] == 1)
                mid[j] = split->dist;
            else if (split->normal[j] == -1)
                mid[j] = -split->dist;
            else
                mid[j] = p1[j] + dot*(p2[j]-p1[j]);
        }
            
        VectorCopy (mid, neww->points[neww->numpoints]);
        neww->numpoints++;
    }
    
    // free the original winding
    FreeStackWinding (in, stack);
    
    return neww;
}

/*
==============
ClipToSeperators

Source, pass, and target are an ordering of portals.

Generates seperating planes canidates by taking two points from source and one
point from pass, and clips target by them.

If target is totally clipped away, that portal can not be seen through.

Normal clip keeps target on the same side as pass, which is correct if the
order goes source, pass, target.  If the order goes pass, source, target then
flipclip should be set.
==============
*/
winding_t   *ClipToSeperators (winding_t *source, winding_t *pass, winding_t *target, qboolean flipclip, pstack_t *stack)
{
    int         i, j, k, l;
    plane_t     plane;
    vec3_t      v1, v2;
    float       d;
    vec_t       length;
    int         counts[3];
    qboolean        fliptest;

    // check all combinations   
    for (i=0 ; i<source->numpoints ; i++)
    {
        l = (i+1)%source->numpoints;
        VectorSubtract (source->points[l] , source->points[i], v1);

        // find a vertex of pass that makes a plane that puts all of the
        // vertexes of pass on the front side and all of the vertexes of
        // source on the back side
        for (j=0 ; j<pass->numpoints ; j++)
        {
            VectorSubtract (pass->points[j], source->points[i], v2);

            plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
            plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
            plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
            
            // if points don't make a valid plane, skip it

            length = plane.normal[0] * plane.normal[0]
            + plane.normal[1] * plane.normal[1]
            + plane.normal[2] * plane.normal[2];
            
            if (length < ON_EPSILON)
                continue;

            length = 1/sqrt(length);
            
            plane.normal[0] *= length;
            plane.normal[1] *= length;
            plane.normal[2] *= length;

            plane.dist = DotProduct (pass->points[j], plane.normal);

            //
            // find out which side of the generated seperating plane has the
            // source portal
            //
#if 1
            fliptest = qfalse;
            for (k=0 ; k<source->numpoints ; k++)
            {
                if (k == i || k == l)
                    continue;
                d = DotProduct (source->points[k], plane.normal) - plane.dist;
                if (d < -ON_EPSILON)
                {   // source is on the negative side, so we want all
                    // pass and target on the positive side
                    fliptest = qfalse;
                    break;
                }
                else if (d > ON_EPSILON)
                {   // source is on the positive side, so we want all
                    // pass and target on the negative side
                    fliptest = qtrue;
                    break;
                }
            }
            if (k == source->numpoints)
                continue;       // planar with source portal
#else
            fliptest = flipclip;
#endif
            //
            // flip the normal if the source portal is backwards
            //
            if (fliptest)
            {
                VectorSubtract (vec3_origin, plane.normal, plane.normal);
                plane.dist = -plane.dist;
            }
#if 1
            //
            // if all of the pass portal points are now on the positive side,
            // this is the seperating plane
            //
            counts[0] = counts[1] = counts[2] = 0;
            for (k=0 ; k<pass->numpoints ; k++)
            {
                if (k==j)
                    continue;
                d = DotProduct (pass->points[k], plane.normal) - plane.dist;
                if (d < -ON_EPSILON)
                    break;
                else if (d > ON_EPSILON)
                    counts[0]++;
                else
                    counts[2]++;
            }
            if (k != pass->numpoints)
                continue;   // points on negative side, not a seperating plane
                
            if (!counts[0])
                continue;   // planar with seperating plane
#else
            k = (j+1)%pass->numpoints;
            d = DotProduct (pass->points[k], plane.normal) - plane.dist;
            if (d < -ON_EPSILON)
                continue;
            k = (j+pass->numpoints-1)%pass->numpoints;
            d = DotProduct (pass->points[k], plane.normal) - plane.dist;
            if (d < -ON_EPSILON)
                continue;           
#endif
            //
            // flip the normal if we want the back side
            //
            if (flipclip)
            {
                VectorSubtract (vec3_origin, plane.normal, plane.normal);
                plane.dist = -plane.dist;
            }

#ifdef SEPERATORCACHE
            stack->seperators[flipclip][stack->numseperators[flipclip]] = plane;
            if (++stack->numseperators[flipclip] >= MAX_SEPERATORS)
                Error("MAX_SEPERATORS");
#endif
            //MrE: fast check first
            d = DotProduct (stack->portal->origin, plane.normal) - plane.dist;
            //if completely at the back of the seperator plane
            if (d < -stack->portal->radius)
                return NULL;
            //if completely on the front of the seperator plane
            if (d > stack->portal->radius)
                break;

            //
            // clip target by the seperating plane
            //
            target = VisChopWinding (target, stack, &plane);
            if (!target)
                return NULL;        // target is not visible

            break;      // optimization by Antony Suter
        }
    }
    
    return target;
}

/*
==================
RecursiveLeafFlow

Flood fill through the leafs
If src_portal is NULL, this is the originating leaf
==================
*/
void RecursiveLeafFlow (int leafnum, threaddata_t *thread, pstack_t *prevstack)
{
    pstack_t    stack;
    vportal_t   *p;
    plane_t     backplane;
    leaf_t      *leaf;
    int         i, j, n;
    long        *test, *might, *prevmight, *vis, more;
    int         pnum;

    thread->c_chains++;

    leaf = &leafs[leafnum];
//  CheckStack (leaf, thread);

    prevstack->next = &stack;

    stack.next = NULL;
    stack.leaf = leaf;
    stack.portal = NULL;
    stack.depth = prevstack->depth + 1;

#ifdef SEPERATORCACHE
    stack.numseperators[0] = 0;
    stack.numseperators[1] = 0;
#endif

    might = (long *)stack.mightsee;
    vis = (long *)thread->base->portalvis;
    
    // check all portals for flowing into other leafs   
    for (i = 0; i < leaf->numportals; i++)
    {
        p = leaf->portals[i];
        if (p->removed)
            continue;
        pnum = p - portals;

        /* MrE: portal trace debug code
        {
            int portaltrace[] = {13, 16, 17, 37};
            pstack_t *s;

            s = &thread->pstack_head;
            for (j = 0; s->next && j < sizeof(portaltrace)/sizeof(int) - 1; j++, s = s->next)
            {
                if (s->portal->num != portaltrace[j])
                    break;
            }
            if (j >= sizeof(portaltrace)/sizeof(int) - 1)
            {
                if (p->num == portaltrace[j])
                    n = 0; //traced through all the portals
            }
        }
        */

        if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
        {
            continue;   // can't possibly see it
        }

        // if the portal can't see anything we haven't allready seen, skip it
        if (p->status == stat_done)
        {
            test = (long *)p->portalvis;
        }
        else
        {
            test = (long *)p->portalflood;
        }

        more = 0;
        prevmight = (long *)prevstack->mightsee;
        for (j=0 ; j<portallongs ; j++)
        {
            might[j] = prevmight[j] & test[j];
            more |= (might[j] & ~vis[j]);
        }
        
        if (!more && 
            (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
        {   // can't see anything new
            continue;
        }

        // get plane of portal, point normal into the neighbor leaf
        stack.portalplane = p->plane;
        VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
        backplane.dist = -p->plane.dist;
        
//      c_portalcheck++;
        
        stack.portal = p;
        stack.next = NULL;
        stack.freewindings[0] = 1;
        stack.freewindings[1] = 1;
        stack.freewindings[2] = 1;
        
#if 1
        {
            float d;

            d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
            d -= thread->pstack_head.portalplane.dist;
            if (d < -p->radius)
            {
                continue;
            }
            else if (d > p->radius)
            {
                stack.pass = p->winding;
            }
            else    
            {
                stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
                if (!stack.pass)
                    continue;
            }
        }
#else
        stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
        if (!stack.pass)
            continue;
#endif

    
#if 1
        {
            float d;

            d = DotProduct (thread->base->origin, p->plane.normal);
            d -= p->plane.dist;
            //MrE: vis-bug fix
            //if (d > p->radius)
            if (d > thread->base->radius)
            {
                continue;
            }
            //MrE: vis-bug fix
            //if (d < -p->radius)
            else if (d < -thread->base->radius)
            {
                stack.source = prevstack->source;
            }
            else    
            {
                stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
                //FIXME: shouldn't we create a new source origin and radius for fast checks?
                if (!stack.source)
                    continue;
            }
        }
#else
        stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
        if (!stack.source)
            continue;
#endif

        if (!prevstack->pass)
        {   // the second leaf can only be blocked if coplanar

            // mark the portal as visible
            thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

            RecursiveLeafFlow (p->leaf, thread, &stack);
            continue;
        }

#ifdef SEPERATORCACHE
        if (stack.numseperators[0])
        {
            for (n = 0; n < stack.numseperators[0]; n++)
            {
                stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
                if (!stack.pass)
                    break;      // target is not visible
            }
            if (n < stack.numseperators[0])
                continue;
        }
        else
        {
            stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
        }
#else
        stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
#endif
        if (!stack.pass)
            continue;

#ifdef SEPERATORCACHE
        if (stack.numseperators[1])
        {
            for (n = 0; n < stack.numseperators[1]; n++)
            {
                stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
                if (!stack.pass)
                    break;      // target is not visible
            }
        }
        else
        {
            stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
        }
#else
        stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
#endif
        if (!stack.pass)
            continue;

        // mark the portal as visible
        thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

        // flow through it for real
        RecursiveLeafFlow (p->leaf, thread, &stack);
        //
        stack.next = NULL;
    }   
}

/*
===============
PortalFlow

generates the portalvis bit vector
===============
*/
void PortalFlow (int portalnum)
{
    threaddata_t    data;
    int             i;
    vportal_t       *p;
    int             c_might, c_can;

#ifdef MREDEBUG
    _printf("\r%6d", portalnum);
#endif

    p = sorted_portals[portalnum];

    if (p->removed)
    {
        p->status = stat_done;
        return;
    }

    p->status = stat_working;

    c_might = CountBits (p->portalflood, numportals*2);

    memset (&data, 0, sizeof(data));
    data.base = p;
    
    data.pstack_head.portal = p;
    data.pstack_head.source = p->winding;
    data.pstack_head.portalplane = p->plane;
    data.pstack_head.depth = 0;
    for (i=0 ; i<portallongs ; i++)
        ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];

    RecursiveLeafFlow (p->leaf, &data, &data.pstack_head);

    p->status = stat_done;

    c_can = CountBits (p->portalvis, numportals*2);

    qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
        (int)(p - portals), c_might, c_can, data.c_chains);
}

/*
==================
RecursivePassageFlow
==================
*/
void RecursivePassageFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
{
    pstack_t    stack;
    vportal_t   *p;
    leaf_t      *leaf;
    passage_t   *passage, *nextpassage;
    int         i, j;
    long        *might, *vis, *prevmight, *cansee, *portalvis, more;
    int         pnum;

    leaf = &leafs[portal->leaf];

    prevstack->next = &stack;

    stack.next = NULL;
    stack.depth = prevstack->depth + 1;

    vis = (long *)thread->base->portalvis;

    passage = portal->passages;
    nextpassage = passage;
    // check all portals for flowing into other leafs   
    for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
    {
        p = leaf->portals[i];
        if ( p->removed ) {
            continue;
        }
        nextpassage = passage->next;
        pnum = p - portals;

        if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) ) {
            continue;   // can't possibly see it
        }

        // mark the portal as visible
        thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

        prevmight = (long *)prevstack->mightsee;
        cansee = (long *)passage->cansee;
        might = (long *)stack.mightsee;
        memcpy(might, prevmight, portalbytes);
        if (p->status == stat_done)
            portalvis = (long *) p->portalvis;
        else
            portalvis = (long *) p->portalflood;
        more = 0;
        for (j = 0; j < portallongs; j++)
        {
            if (*might)
            {
                *might &= *cansee++ & *portalvis++;
                more |= (*might & ~vis[j]);
            }
            else
            {
                cansee++;
                portalvis++;
            }
            might++;
        }

        if ( !more ) {
            // can't see anything new
            continue;
        }

        // flow through it for real
        RecursivePassageFlow(p, thread, &stack);

        stack.next = NULL;
    }
}

/*
===============
PassageFlow
===============
*/
void PassageFlow (int portalnum)
{
    threaddata_t    data;
    int             i;
    vportal_t       *p;
//  int             c_might, c_can;

#ifdef MREDEBUG
    _printf("\r%6d", portalnum);
#endif

    p = sorted_portals[portalnum];

    if (p->removed)
    {
        p->status = stat_done;
        return;
    }

    p->status = stat_working;

//  c_might = CountBits (p->portalflood, numportals*2);

    memset (&data, 0, sizeof(data));
    data.base = p;
    
    data.pstack_head.portal = p;
    data.pstack_head.source = p->winding;
    data.pstack_head.portalplane = p->plane;
    data.pstack_head.depth = 0;
    for (i=0 ; i<portallongs ; i++)
        ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];

    RecursivePassageFlow (p, &data, &data.pstack_head);

    p->status = stat_done;

    /*
    c_can = CountBits (p->portalvis, numportals*2);

    qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
        (int)(p - portals), c_might, c_can, data.c_chains);
    */
}

/*
==================
RecursivePassagePortalFlow
==================
*/
void RecursivePassagePortalFlow (vportal_t *portal, threaddata_t *thread, pstack_t *prevstack)
{
    pstack_t    stack;
    vportal_t   *p;
    leaf_t      *leaf;
    plane_t     backplane;
    passage_t   *passage, *nextpassage;
    int         i, j, n;
    long        *might, *vis, *prevmight, *cansee, *portalvis, more;
    int         pnum;

//  thread->c_chains++;

    leaf = &leafs[portal->leaf];
//  CheckStack (leaf, thread);

    prevstack->next = &stack;

    stack.next = NULL;
    stack.leaf = leaf;
    stack.portal = NULL;
    stack.depth = prevstack->depth + 1;

#ifdef SEPERATORCACHE
    stack.numseperators[0] = 0;
    stack.numseperators[1] = 0;
#endif

    vis = (long *)thread->base->portalvis;

    passage = portal->passages;
    nextpassage = passage;
    // check all portals for flowing into other leafs   
    for (i = 0; i < leaf->numportals; i++, passage = nextpassage)
    {
        p = leaf->portals[i];
        if (p->removed)
            continue;
        nextpassage = passage->next;
        pnum = p - portals;

        if ( ! (prevstack->mightsee[pnum >> 3] & (1<<(pnum&7)) ) )
            continue;   // can't possibly see it

        prevmight = (long *)prevstack->mightsee;
        cansee = (long *)passage->cansee;
        might = (long *)stack.mightsee;
        memcpy(might, prevmight, portalbytes);
        if (p->status == stat_done)
            portalvis = (long *) p->portalvis;
        else
            portalvis = (long *) p->portalflood;
        more = 0;
        for (j = 0; j < portallongs; j++)
        {
            if (*might)
            {
                *might &= *cansee++ & *portalvis++;
                more |= (*might & ~vis[j]);
            }
            else
            {
                cansee++;
                portalvis++;
            }
            might++;
        }

        if (!more && (thread->base->portalvis[pnum>>3] & (1<<(pnum&7))) )
        {   // can't see anything new
            continue;
        }

        // get plane of portal, point normal into the neighbor leaf
        stack.portalplane = p->plane;
        VectorSubtract (vec3_origin, p->plane.normal, backplane.normal);
        backplane.dist = -p->plane.dist;
        
//      c_portalcheck++;
        
        stack.portal = p;
        stack.next = NULL;
        stack.freewindings[0] = 1;
        stack.freewindings[1] = 1;
        stack.freewindings[2] = 1;

#if 1
        {
            float d;

            d = DotProduct (p->origin, thread->pstack_head.portalplane.normal);
            d -= thread->pstack_head.portalplane.dist;
            if (d < -p->radius)
            {
                continue;
            }
            else if (d > p->radius)
            {
                stack.pass = p->winding;
            }
            else    
            {
                stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
                if (!stack.pass)
                    continue;
            }
        }
#else
        stack.pass = VisChopWinding (p->winding, &stack, &thread->pstack_head.portalplane);
        if (!stack.pass)
            continue;
#endif

    
#if 1
        {
            float d;

            d = DotProduct (thread->base->origin, p->plane.normal);
            d -= p->plane.dist;
            //MrE: vis-bug fix
            //if (d > p->radius)
            if (d > thread->base->radius)
            {
                continue;
            }
            //MrE: vis-bug fix
            //if (d < -p->radius)
            else if (d < -thread->base->radius)
            {
                stack.source = prevstack->source;
            }
            else    
            {
                stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
                //FIXME: shouldn't we create a new source origin and radius for fast checks?
                if (!stack.source)
                    continue;
            }
        }
#else
        stack.source = VisChopWinding (prevstack->source, &stack, &backplane);
        if (!stack.source)
            continue;
#endif

        if (!prevstack->pass)
        {   // the second leaf can only be blocked if coplanar

            // mark the portal as visible
            thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

            RecursivePassagePortalFlow (p, thread, &stack);
            continue;
        }

#ifdef SEPERATORCACHE
        if (stack.numseperators[0])
        {
            for (n = 0; n < stack.numseperators[0]; n++)
            {
                stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[0][n]);
                if (!stack.pass)
                    break;      // target is not visible
            }
            if (n < stack.numseperators[0])
                continue;
        }
        else
        {
            stack.pass = ClipToSeperators (prevstack->source, prevstack->pass, stack.pass, qfalse, &stack);
        }
#else
        stack.pass = ClipToSeperators (stack.source, prevstack->pass, stack.pass, qfalse, &stack);
#endif
        if (!stack.pass)
            continue;

#ifdef SEPERATORCACHE
        if (stack.numseperators[1])
        {
            for (n = 0; n < stack.numseperators[1]; n++)
            {
                stack.pass = VisChopWinding (stack.pass, &stack, &stack.seperators[1][n]);
                if (!stack.pass)
                    break;      // target is not visible
            }
        }
        else
        {
            stack.pass = ClipToSeperators (prevstack->pass, prevstack->source, stack.pass, qtrue, &stack);
        }
#else
        stack.pass = ClipToSeperators (prevstack->pass, stack.source, stack.pass, qtrue, &stack);
#endif
        if (!stack.pass)
            continue;

        // mark the portal as visible
        thread->base->portalvis[pnum>>3] |= (1<<(pnum&7));

        // flow through it for real
        RecursivePassagePortalFlow(p, thread, &stack);
        //
        stack.next = NULL;
    }
}

/*
===============
PassagePortalFlow
===============
*/
void PassagePortalFlow (int portalnum)
{
    threaddata_t    data;
    int             i;
    vportal_t       *p;
//  int             c_might, c_can;

#ifdef MREDEBUG
    _printf("\r%6d", portalnum);
#endif

    p = sorted_portals[portalnum];

    if (p->removed)
    {
        p->status = stat_done;
        return;
    }

    p->status = stat_working;

//  c_might = CountBits (p->portalflood, numportals*2);

    memset (&data, 0, sizeof(data));
    data.base = p;
    
    data.pstack_head.portal = p;
    data.pstack_head.source = p->winding;
    data.pstack_head.portalplane = p->plane;
    data.pstack_head.depth = 0;
    for (i=0 ; i<portallongs ; i++)
        ((long *)data.pstack_head.mightsee)[i] = ((long *)p->portalflood)[i];

    RecursivePassagePortalFlow (p, &data, &data.pstack_head);

    p->status = stat_done;

    /*
    c_can = CountBits (p->portalvis, numportals*2);

    qprintf ("portal:%4i  mightsee:%4i  cansee:%4i (%i chains)\n", 
        (int)(p - portals), c_might, c_can, data.c_chains);
    */
}

winding_t *PassageChopWinding (winding_t *in, winding_t *out, plane_t *split)
{
    vec_t   dists[128];
    int     sides[128];
    int     counts[3];
    vec_t   dot;
    int     i, j;
    vec_t   *p1, *p2;
    vec3_t  mid;
    winding_t   *neww;

    counts[0] = counts[1] = counts[2] = 0;

    // determine sides for each point
    for (i=0 ; i<in->numpoints ; i++)
    {
        dot = DotProduct (in->points[i], split->normal);
        dot -= split->dist;
        dists[i] = dot;
        if (dot > ON_EPSILON)
            sides[i] = SIDE_FRONT;
        else if (dot < -ON_EPSILON)
            sides[i] = SIDE_BACK;
        else
        {
            sides[i] = SIDE_ON;
        }
        counts[sides[i]]++;
    }

    if (!counts[1])
        return in;      // completely on front side
    
    if (!counts[0])
    {
        return NULL;
    }

    sides[i] = sides[0];
    dists[i] = dists[0];
    
    neww = out;

    neww->numpoints = 0;

    for (i=0 ; i<in->numpoints ; i++)
    {
        p1 = in->points[i];

        if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
        {
            return in;      // can't chop -- fall back to original
        }

        if (sides[i] == SIDE_ON)
        {
            VectorCopy (p1, neww->points[neww->numpoints]);
            neww->numpoints++;
            continue;
        }
    
        if (sides[i] == SIDE_FRONT)
        {
            VectorCopy (p1, neww->points[neww->numpoints]);
            neww->numpoints++;
        }
        
        if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
            continue;
            
        if (neww->numpoints == MAX_POINTS_ON_FIXED_WINDING)
        {
            return in;      // can't chop -- fall back to original
        }

        // generate a split point
        p2 = in->points[(i+1)%in->numpoints];
        
        dot = dists[i] / (dists[i]-dists[i+1]);
        for (j=0 ; j<3 ; j++)
        {   // avoid round off error when possible
            if (split->normal[j] == 1)
                mid[j] = split->dist;
            else if (split->normal[j] == -1)
                mid[j] = -split->dist;
            else
                mid[j] = p1[j] + dot*(p2[j]-p1[j]);
        }
            
        VectorCopy (mid, neww->points[neww->numpoints]);
        neww->numpoints++;
    }
    
    return neww;
}

/*
===============
AddSeperators
===============
*/
int AddSeperators (winding_t *source, winding_t *pass, qboolean flipclip, plane_t *seperators, int maxseperators)
{
    int         i, j, k, l;
    plane_t     plane;
    vec3_t      v1, v2;
    float       d;
    vec_t       length;
    int         counts[3], numseperators;
    qboolean    fliptest;

    numseperators = 0;
    // check all combinations   
    for (i=0 ; i<source->numpoints ; i++)
    {
        l = (i+1)%source->numpoints;
        VectorSubtract (source->points[l] , source->points[i], v1);

        // find a vertex of pass that makes a plane that puts all of the
        // vertexes of pass on the front side and all of the vertexes of
        // source on the back side
        for (j=0 ; j<pass->numpoints ; j++)
        {
            VectorSubtract (pass->points[j], source->points[i], v2);

            plane.normal[0] = v1[1]*v2[2] - v1[2]*v2[1];
            plane.normal[1] = v1[2]*v2[0] - v1[0]*v2[2];
            plane.normal[2] = v1[0]*v2[1] - v1[1]*v2[0];
            
            // if points don't make a valid plane, skip it

            length = plane.normal[0] * plane.normal[0]
            + plane.normal[1] * plane.normal[1]
            + plane.normal[2] * plane.normal[2];
            
            if (length < ON_EPSILON)
                continue;

            length = 1/sqrt(length);
            
            plane.normal[0] *= length;
            plane.normal[1] *= length;
            plane.normal[2] *= length;

            plane.dist = DotProduct (pass->points[j], plane.normal);

            //
            // find out which side of the generated seperating plane has the
            // source portal
            //
#if 1
            fliptest = qfalse;
            for (k=0 ; k<source->numpoints ; k++)
            {
                if (k == i || k == l)
                    continue;
                d = DotProduct (source->points[k], plane.normal) - plane.dist;
                if (d < -ON_EPSILON)
                {   // source is on the negative side, so we want all
                    // pass and target on the positive side
                    fliptest = qfalse;
                    break;
                }
                else if (d > ON_EPSILON)
                {   // source is on the positive side, so we want all
                    // pass and target on the negative side
                    fliptest = qtrue;
                    break;
                }
            }
            if (k == source->numpoints)
                continue;       // planar with source portal
#else
            fliptest = flipclip;
#endif
            //
            // flip the normal if the source portal is backwards
            //
            if (fliptest)
            {
                VectorSubtract (vec3_origin, plane.normal, plane.normal);
                plane.dist = -plane.dist;
            }
#if 1
            //
            // if all of the pass portal points are now on the positive side,
            // this is the seperating plane
            //
            counts[0] = counts[1] = counts[2] = 0;
            for (k=0 ; k<pass->numpoints ; k++)
            {
                if (k==j)
                    continue;
                d = DotProduct (pass->points[k], plane.normal) - plane.dist;
                if (d < -ON_EPSILON)
                    break;
                else if (d > ON_EPSILON)
                    counts[0]++;
                else
                    counts[2]++;
            }
            if (k != pass->numpoints)
                continue;   // points on negative side, not a seperating plane
                
            if (!counts[0])
                continue;   // planar with seperating plane
#else
            k = (j+1)%pass->numpoints;
            d = DotProduct (pass->points[k], plane.normal) - plane.dist;
            if (d < -ON_EPSILON)
                continue;
            k = (j+pass->numpoints-1)%pass->numpoints;
            d = DotProduct (pass->points[k], plane.normal) - plane.dist;
            if (d < -ON_EPSILON)
                continue;           
#endif
            //
            // flip the normal if we want the back side
            //
            if (flipclip)
            {
                VectorSubtract (vec3_origin, plane.normal, plane.normal);
                plane.dist = -plane.dist;
            }

            if (numseperators >= maxseperators)
                Error("max seperators");
            seperators[numseperators] = plane;
            numseperators++;
            break;
        }
    }
    return numseperators;
}

/*
===============
CreatePassages

MrE: create passages from one portal to all the portals in the leaf the portal leads to
     every passage has a cansee bit string with all the portals that can be
     seen through the passage
===============
*/
void CreatePassages(int portalnum)
{
    int i, j, k, n, numseperators, numsee;
    float d;
    vportal_t *portal, *p, *target;
    leaf_t *leaf;
    passage_t   *passage, *lastpassage;
    plane_t seperators[MAX_SEPERATORS*2];
    winding_t *w;
    winding_t in, out, *res;

#ifdef MREDEBUG
    _printf("\r%6d", portalnum);
#endif

    portal = sorted_portals[portalnum];

    if (portal->removed)
    {
        portal->status = stat_done;
        return;
    }

    lastpassage = NULL;
    leaf = &leafs[portal->leaf];
    for (i = 0; i < leaf->numportals; i++)
    {
        target = leaf->portals[i];
        if (target->removed)
            continue;

        passage = (passage_t *) malloc(sizeof(passage_t) + portalbytes);
        memset(passage, 0, sizeof(passage_t) + portalbytes);
        numseperators = AddSeperators(portal->winding, target->winding, qfalse, seperators, MAX_SEPERATORS*2);
        numseperators += AddSeperators(target->winding, portal->winding, qtrue, &seperators[numseperators], MAX_SEPERATORS*2-numseperators);

        passage->next = NULL;
        if (lastpassage)
            lastpassage->next = passage;
        else
            portal->passages = passage;
        lastpassage = passage;

        numsee = 0;
        //create the passage->cansee
        for (j = 0; j < numportals * 2; j++)
        {
            p = &portals[j];
            if (p->removed)
                continue;
            if ( ! (target->portalflood[j >> 3] & (1<<(j&7)) ) )
                continue;
            if ( ! (portal->portalflood[j >> 3] & (1<<(j&7)) ) )
                continue;
            for (k = 0; k < numseperators; k++)
            {
                //
                d = DotProduct (p->origin, seperators[k].normal) - seperators[k].dist;
                //if completely at the back of the seperator plane
                if (d < -p->radius + ON_EPSILON)
                    break;
                w = p->winding;
                for (n = 0; n < w->numpoints; n++)
                {