csg.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 "qbsp.h"

/*

tag all brushes with original contents
brushes may contain multiple contents
there will be no brush overlap after csg phase

*/

int minplanenums[3];
int maxplanenums[3];

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void CheckBSPBrush(bspbrush_t *brush)
{
    int i, j;
    plane_t *plane1, *plane2;

    //check if the brush is convex... flipped planes make a brush non-convex
    for (i = 0; i < brush->numsides; i++)
    {
        for (j = 0; j < brush->numsides; j++)
        {
            if (i == j) continue;
            plane1 = &mapplanes[brush->sides[i].planenum];
            plane2 = &mapplanes[brush->sides[j].planenum];
            //
            if (WindingsNonConvex(brush->sides[i].winding,
                                    brush->sides[j].winding,
                                    plane1->normal, plane2->normal,
                                    plane1->dist, plane2->dist))
            {
                Log_Print("non convex brush");
                break;
            } //end if
        } //end for
    } //end for
    BoundBrush(brush);
    //check for out of bound brushes
    for (i = 0; i < 3; i++)
    {
        if (brush->mins[i] < -MAX_MAP_BOUNDS || brush->maxs[i] > MAX_MAP_BOUNDS)
        {
            Log_Print("brush: bounds out of range\n");
            Log_Print("ob->mins[%d] = %f, ob->maxs[%d] = %f\n", i, brush->mins[i], i, brush->maxs[i]);
            break;
        } //end if
        if (brush->mins[i] > MAX_MAP_BOUNDS || brush->maxs[i] < -MAX_MAP_BOUNDS)
        {
            Log_Print("brush: no visible sides on brush\n");
            Log_Print("ob->mins[%d] = %f, ob->maxs[%d] = %f\n", i, brush->mins[i], i, brush->maxs[i]);
            break;
        } //end if
    } //end for
} //end of the function CheckBSPBrush
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void BSPBrushWindings(bspbrush_t *brush)
{
    int i, j;
    winding_t *w;
    plane_t *plane;

    for (i = 0; i < brush->numsides; i++)
    {
        plane = &mapplanes[brush->sides[i].planenum];
        w = BaseWindingForPlane(plane->normal, plane->dist);
        for (j = 0; j < brush->numsides && w; j++)
        {
            if (i == j) continue;
            plane = &mapplanes[brush->sides[j].planenum^1];
            ChopWindingInPlace(&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
        } //end for
        brush->sides[i].winding = w;
    } //end for
} //end of the function BSPBrushWindings
//===========================================================================
// NOTE: can't keep brush->original intact
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *TryMergeBrushes(bspbrush_t *brush1, bspbrush_t *brush2)
{
    int i, j, k, n, shared;
    side_t *side1, *side2, *cs;
    plane_t *plane1, *plane2;
    bspbrush_t *newbrush;

    //check for bounding box overlapp
    for (i = 0; i < 3; i++)
    {
        if (brush1->mins[i] > brush2->maxs[i] + 2
                || brush1->maxs[i] < brush2->mins[i] - 2)
        {
            return NULL;
        } //end if
    } //end for
    //
    shared = 0;
    //check if the brush is convex... flipped planes make a brush non-convex
    for (i = 0; i < brush1->numsides; i++)
    {
        side1 = &brush1->sides[i];
        //don't check the "shared" sides
        for (k = 0; k < brush2->numsides; k++)
        {
            side2 = &brush2->sides[k];
            if (side1->planenum == (side2->planenum^1))
            {
                shared++;
                //there may only be ONE shared side
                if (shared > 1) return NULL;
                break;
            } //end if
        } //end for
        if (k < brush2->numsides) continue;
        //
        for (j = 0; j < brush2->numsides; j++)
        {
            side2 = &brush2->sides[j];
            //don't check the "shared" sides
            for (n = 0; n < brush1->numsides; n++)
            {
                side1 = &brush1->sides[n];
                if (side1->planenum == (side2->planenum^1)) break;
            } //end for
            if (n < brush1->numsides) continue;
            //
            side1 = &brush1->sides[i];
            //if the side is in the same plane
            //*
            if (side1->planenum == side2->planenum)
            {
                if (side1->texinfo != TEXINFO_NODE &&
                    side2->texinfo != TEXINFO_NODE &&
                    side1->texinfo != side2->texinfo) return NULL;
                continue;
            } //end if
            //
            plane1 = &mapplanes[side1->planenum];
            plane2 = &mapplanes[side2->planenum];
            //
            if (WindingsNonConvex(side1->winding, side2->winding,
                                    plane1->normal, plane2->normal,
                                    plane1->dist, plane2->dist))
            {
                return NULL;
            } //end if
        } //end for
    } //end for
    newbrush = AllocBrush(brush1->numsides + brush2->numsides);
    newbrush->original = brush1->original;
    newbrush->numsides = 0;
    //newbrush->side = brush1->side;    //brush contents
    //fix texinfos for sides lying in the same plane
    for (i = 0; i < brush1->numsides; i++)
    {
        side1 = &brush1->sides[i];
        //
        for (n = 0; n < brush2->numsides; n++)
        {
            side2 = &brush2->sides[n];
            //if both sides are in the same plane get the texinfo right
            if (side1->planenum == side2->planenum)
            {
                if (side1->texinfo == TEXINFO_NODE) side1->texinfo = side2->texinfo;
                if (side2->texinfo == TEXINFO_NODE) side2->texinfo = side1->texinfo;
            } //end if
        } //end for
    } //end for
    //
    for (i = 0; i < brush1->numsides; i++)
    {
        side1 = &brush1->sides[i];
        //don't add the "shared" sides
        for (n = 0; n < brush2->numsides; n++)
        {
            side2 = &brush2->sides[n];
            if (side1->planenum == (side2->planenum ^ 1)) break;
        } //end for
        if (n < brush2->numsides) continue;
        //
        for (n = 0; n < newbrush->numsides; n++)
        {
            cs = &newbrush->sides[n];
            if (cs->planenum == side1->planenum)
            {
                Log_Print("brush duplicate plane\n");
                break;
            } //end if
        } //end if
        if (n < newbrush->numsides) continue;
        //add this side
        cs = &newbrush->sides[newbrush->numsides];
        newbrush->numsides++;
        *cs = *side1;
    } //end for
    for (j = 0; j < brush2->numsides; j++)
    {
        side2 = &brush2->sides[j];
        for (n = 0; n < brush1->numsides; n++)
        {
            side1 = &brush1->sides[n];
            //if the side is in the same plane
            if (side2->planenum == side1->planenum) break;
            //don't add the "shared" sides
            if (side2->planenum == (side1->planenum ^ 1)) break;
        } //end for
        if (n < brush1->numsides) continue;
        //
        for (n = 0; n < newbrush->numsides; n++)
        {
            cs = &newbrush->sides[n];
            if (cs->planenum == side2->planenum)
            {
                Log_Print("brush duplicate plane\n");
                break;
            } //end if
        } //end if
        if (n < newbrush->numsides) continue;
        //add this side
        cs = &newbrush->sides[newbrush->numsides];
        newbrush->numsides++;
        *cs = *side2;
    } //end for
    BSPBrushWindings(newbrush);
    BoundBrush(newbrush);
    CheckBSPBrush(newbrush);
    return newbrush;
} //end of the function TryMergeBrushes
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *MergeBrushes(bspbrush_t *brushlist)
{
    int nummerges, merged;
    bspbrush_t *b1, *b2, *tail, *newbrush, *newbrushlist;
    bspbrush_t *lastb2;

    if (!brushlist) return NULL;

    qprintf("%5d brushes merged", nummerges = 0);
    do
    {
        for (tail = brushlist; tail; tail = tail->next)
        {
            if (!tail->next) break;
        } //end for
        merged = 0;
        newbrushlist = NULL;
        for (b1 = brushlist; b1; b1 = brushlist)
        {
            lastb2 = b1;
            for (b2 = b1->next; b2; b2 = b2->next)
            {
                //if the brushes don't have the same contents
                if (b1->original->contents != b2->original->contents ||
                    b1->original->expansionbbox != b2->original->expansionbbox) newbrush = NULL;
                else newbrush = TryMergeBrushes(b1, b2);
                if (newbrush)
                {
                    tail->next = newbrush;
                    lastb2->next = b2->next;
                    brushlist = brushlist->next;
                    FreeBrush(b1);
                    FreeBrush(b2);
                    for (tail = brushlist; tail; tail = tail->next)
                    {
                        if (!tail->next) break;
                    } //end for
                    merged++;
                    qprintf("\r%5d", nummerges++);
                    break;
                } //end if
                lastb2 = b2;
            } //end for
            //if b1 can't be merged with any of the other brushes
            if (!b2)
            {
                brushlist = brushlist->next;
                //keep b1
                b1->next = newbrushlist;
                newbrushlist = b1;
            } //end else
        } //end for
        brushlist = newbrushlist;
    } while(merged);
    qprintf("\n");
    return newbrushlist;
} //end of the function MergeBrushes
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void SplitBrush2 (bspbrush_t *brush, int planenum,
    bspbrush_t **front, bspbrush_t **back)
{
    SplitBrush (brush, planenum, front, back);
#if 0
    if (*front && (*front)->sides[(*front)->numsides-1].texinfo == -1)
        (*front)->sides[(*front)->numsides-1].texinfo = (*front)->sides[0].texinfo; // not -1
    if (*back && (*back)->sides[(*back)->numsides-1].texinfo == -1)
        (*back)->sides[(*back)->numsides-1].texinfo = (*back)->sides[0].texinfo;    // not -1
#endif
} //end of the function SplitBrush2
//===========================================================================
// Returns a list of brushes that remain after B is subtracted from A.
// May by empty if A is contained inside B.
// The originals are undisturbed.
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *SubtractBrush (bspbrush_t *a, bspbrush_t *b)
{   // a - b = out (list)
    int     i;
    bspbrush_t  *front, *back;
    bspbrush_t  *out, *in;

    in = a;
    out = NULL;
    for (i = 0; i < b->numsides && in; i++)
    {
        SplitBrush2(in, b->sides[i].planenum, &front, &back);
        if (in != a) FreeBrush(in);
        if (front)
        {   // add to list
            front->next = out;
            out = front;
        } //end if
        in = back;
    } //end for
    if (in)
    {
        FreeBrush (in);
    } //end if
    else
    {   // didn't really intersect
        FreeBrushList (out);
        return a;
    } //end else
    return out;
} //end of the function SubtractBrush
//===========================================================================
// Returns a single brush made up by the intersection of the
// two provided brushes, or NULL if they are disjoint.
//
// The originals are undisturbed.
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *IntersectBrush (bspbrush_t *a, bspbrush_t *b)
{
    int     i;
    bspbrush_t  *front, *back;
    bspbrush_t  *in;

    in = a;
    for (i=0 ; i<b->numsides && in ; i++)
    {
        SplitBrush2(in, b->sides[i].planenum, &front, &back);
        if (in != a) FreeBrush(in);
        if (front) FreeBrush(front);
        in = back;
    } //end for

    if (in == a) return NULL;

    in->next = NULL;
    return in;
} //end of the function IntersectBrush
//===========================================================================
// Returns true if the two brushes definately do not intersect.
// There will be false negatives for some non-axial combinations.
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
qboolean BrushesDisjoint (bspbrush_t *a, bspbrush_t *b)
{
    int     i, j;

    // check bounding boxes
    for (i=0 ; i<3 ; i++)
        if (a->mins[i] >= b->maxs[i]
        || a->maxs[i] <= b->mins[i])
            return true;    // bounding boxes don't overlap

    // check for opposing planes
    for (i=0 ; i<a->numsides ; i++)
    {
        for (j=0 ; j<b->numsides ; j++)
        {
            if (a->sides[i].planenum ==
            (b->sides[j].planenum^1) )
                return true;    // opposite planes, so not touching
        }
    }

    return false;   // might intersect
} //end of the function BrushesDisjoint
//===========================================================================
// Returns a content word for the intersection of two brushes.
// Some combinations will generate a combination (water + clip),
// but most will be the stronger of the two contents.
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int IntersectionContents (int c1, int c2)
{
    int out;

    out = c1 | c2;

    if (out & CONTENTS_SOLID) out = CONTENTS_SOLID;

    return out;
} //end of the function IntersectionContents
//===========================================================================
// Any planes shared with the box edge will be set to no texinfo
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *ClipBrushToBox(bspbrush_t *brush, vec3_t clipmins, vec3_t clipmaxs)
{
    int     i, j;
    bspbrush_t  *front, *back;
    int     p;

    for (j=0 ; j<2 ; j++)
    {
        if (brush->maxs[j] > clipmaxs[j])
        {
            SplitBrush (brush, maxplanenums[j], &front, &back);
            if (front)
                FreeBrush (front);
            brush = back;
            if (!brush)
                return NULL;
        }
        if (brush->mins[j] < clipmins[j])
        {
            SplitBrush (brush, minplanenums[j], &front, &back);
            if (back)
                FreeBrush (back);
            brush = front;
            if (!brush)
                return NULL;
        }
    }

    // remove any colinear faces

    for (i=0 ; i<brush->numsides ; i++)
    {
        p = brush->sides[i].planenum & ~1;
        if (p == maxplanenums[0] || p == maxplanenums[1] 
            || p == minplanenums[0] || p == minplanenums[1])
        {
            brush->sides[i].texinfo = TEXINFO_NODE;
            brush->sides[i].flags &= ~SFL_VISIBLE;
        }
    }
    return brush;
} //end of the function ClipBrushToBox
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *MakeBspBrushList(int startbrush, int endbrush,
                                            vec3_t clipmins, vec3_t clipmaxs)
{
    mapbrush_t  *mb;
    bspbrush_t  *brushlist, *newbrush;
    int         i, j;
    int         c_faces;
    int         c_brushes;
    int         numsides;
    int         vis;
    vec3_t      normal;
    float       dist;

    for (i=0 ; i<2 ; i++)
    {
        VectorClear (normal);
        normal[i] = 1;
        dist = clipmaxs[i];
        maxplanenums[i] = FindFloatPlane(normal, dist);
        dist = clipmins[i];
        minplanenums[i] = FindFloatPlane(normal, dist);
    }

    brushlist = NULL;
    c_faces = 0;
    c_brushes = 0;

    for (i=startbrush ; i<endbrush ; i++)
    {
        mb = &mapbrushes[i];

        numsides = mb->numsides;
        if (!numsides)
            continue;

        // make sure the brush has at least one face showing
        vis = 0;
        for (j=0 ; j<numsides ; j++)
            if ((mb->original_sides[j].flags & SFL_VISIBLE) && mb->original_sides[j].winding)
                vis++;
#if 0
        if (!vis)
            continue;   // no faces at all
#endif
        // if the brush is outside the clip area, skip it
        for (j=0 ; j<3 ; j++)
            if (mb->mins[j] >= clipmaxs[j]
            || mb->maxs[j] <= clipmins[j])
            break;
        if (j != 3)
            continue;

        //
        // make a copy of the brush
        //
        newbrush = AllocBrush (mb->numsides);
        newbrush->original = mb;
        newbrush->numsides = mb->numsides;
        memcpy (newbrush->sides, mb->original_sides, numsides*sizeof(side_t));
        for (j=0 ; j<numsides ; j++)
        {
            if (newbrush->sides[j].winding)
                newbrush->sides[j].winding = CopyWinding (newbrush->sides[j].winding);
            if (newbrush->sides[j].surf & SURF_HINT)
                newbrush->sides[j].flags |= SFL_VISIBLE;    // hints are always visible
        }
        VectorCopy (mb->mins, newbrush->mins);
        VectorCopy (mb->maxs, newbrush->maxs);

        //
        // carve off anything outside the clip box
        //
        newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs);
        if (!newbrush)
            continue;

        c_faces += vis;
        c_brushes++;

        newbrush->next = brushlist;
        brushlist = newbrush;
    }

    return brushlist;
} //end of the function MakeBspBrushList
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail)
{
    bspbrush_t  *walk, *next;

    for (walk=list ; walk ; walk=next)
    {   // add to end of list
        next = walk->next;
        walk->next = NULL;
        tail->next = walk;
        tail = walk;
    } //end for
    return tail;
} //end of the function AddBrushListToTail
//===========================================================================
// Builds a new list that doesn't hold the given brush
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *CullList(bspbrush_t *list, bspbrush_t *skip1)
{
    bspbrush_t  *newlist;
    bspbrush_t  *next;

    newlist = NULL;

    for ( ; list ; list = next)
    {
        next = list->next;
        if (list == skip1)
        {
            FreeBrush (list);
            continue;
        }
        list->next = newlist;
        newlist = list;
    }
    return newlist;
} //end of the function CullList
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
/*
void WriteBrushMap(char *name, bspbrush_t *list)
{
    FILE    *f;
    side_t  *s;
    int     i;
    winding_t   *w;

    Log_Print("writing %s\n", name);
    f = fopen (name, "wb");
    if (!f)
        Error ("Can't write %s\b", name);

    fprintf (f, "{\n\"classname\" \"worldspawn\"\n");

    for ( ; list ; list=list->next )
    {
        fprintf (f, "{\n");
        for (i=0,s=list->sides ; i<list->numsides ; i++,s++)
        {
            w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist);

            fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]);
            fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]);
            fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]);

            fprintf (f, "%s 0 0 0 1 1\n", texinfo[s->texinfo].texture);
            FreeWinding (w);
        }
        fprintf (f, "}\n");
    }
    fprintf (f, "}\n");

    fclose (f);
} //end of the function WriteBrushMap
*/
//===========================================================================
// Returns true if b1 is allowed to bite b2
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2)
{
#ifdef ME
    if (create_aas)
    {
        if (b1->original->expansionbbox != b2->original->expansionbbox)
        {
            return false;
        } //end if
        //never have something else bite a ladder brush
        //never have a ladder brush bite something else
        if ( (b1->original->contents & CONTENTS_LADDER)
            && !(b2->original->contents & CONTENTS_LADDER))
        { 
            return false;
        } //end if
    } //end if
#endif //ME
    // detail brushes never bite structural brushes
    if ( (b1->original->contents & CONTENTS_DETAIL) 
        && !(b2->original->contents & CONTENTS_DETAIL) )
    {
        return false;
    } //end if
    if (b1->original->contents & CONTENTS_SOLID)
    {
        return true;
    } //end if
    return false;
} //end of the function BrushGE
//===========================================================================
// Carves any intersecting solid brushes into the minimum number
// of non-intersecting brushes.
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *ChopBrushes (bspbrush_t *head)
{
    bspbrush_t  *b1, *b2, *next;
    bspbrush_t  *tail;
    bspbrush_t  *keep;
    bspbrush_t  *sub, *sub2;
    int         c1, c2;
    int num_csg_iterations;

    Log_Print("-------- Brush CSG ---------\n");
    Log_Print("%6d original brushes\n", CountBrushList (head));

    num_csg_iterations = 0;
    qprintf("%6d output brushes", num_csg_iterations);

#if 0
    if (startbrush == 0)
        WriteBrushList ("before.gl", head, false);
#endif
    keep = NULL;

newlist:
    // find tail
    if (!head) return NULL;

    for (tail = head; tail->next; tail = tail->next)
        ;

    for (b1=head ; b1 ; b1=next)
    {
        next = b1->next;

        //if the conversion is cancelled
        if (cancelconversion)
        {
            b1->next = keep;
            keep = b1;
            continue;
        } //end if
        
        for (b2 = b1->next; b2; b2 = b2->next)
        {
            if (BrushesDisjoint (b1, b2))
                continue;

            sub = NULL;
            sub2 = NULL;
            c1 = 999999;
            c2 = 999999;

            if (BrushGE (b2, b1))
            {
                sub = SubtractBrush (b1, b2);
                if (sub == b1)
                {
                    continue;       // didn't really intersect
                } //end if
                if (!sub)
                {   // b1 is swallowed by b2
                    head = CullList (b1, b1);
                    goto newlist;
                }
                c1 = CountBrushList (sub);
            }

            if ( BrushGE (b1, b2) )
            {
                sub2 = SubtractBrush (b2, b1);
                if (sub2 == b2)
                    continue;       // didn't really intersect
                if (!sub2)
                {   // b2 is swallowed by b1
                    FreeBrushList (sub);
                    head = CullList (b1, b2);
                    goto newlist;
                }
                c2 = CountBrushList (sub2);
            }

            if (!sub && !sub2)
                continue;       // neither one can bite

            // only accept if it didn't fragment
            // (commenting this out allows full fragmentation)
            if (c1 > 1 && c2 > 1)
            {
                if (sub2)
                    FreeBrushList (sub2);
                if (sub)
                    FreeBrushList (sub);
                continue;
            }

            if (c1 < c2)
            {
                if (sub2) FreeBrushList (sub2);
                tail = AddBrushListToTail (sub, tail);
                head = CullList (b1, b1);
                goto newlist;
            } //end if
            else
            {
                if (sub) FreeBrushList (sub);
                tail = AddBrushListToTail (sub2, tail);
                head = CullList (b1, b2);
                goto newlist;
            } //end else
        } //end for

        if (!b2)
        {   // b1 is no longer intersecting anything, so keep it
            b1->next = keep;
            keep = b1;
        } //end if
        num_csg_iterations++;
        qprintf("\r%6d", num_csg_iterations);
    } //end for

    if (cancelconversion) return keep;
    //
    qprintf("\n");
    Log_Write("%6d output brushes\r\n", num_csg_iterations);

#if 0
    {
        WriteBrushList ("after.gl", keep, false);
        WriteBrushMap ("after.map", keep);
    }
#endif

    return keep;
} //end of the function ChopBrushes
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *InitialBrushList (bspbrush_t *list)
{
    bspbrush_t *b;
    bspbrush_t  *out, *newb;
    int         i;

    // only return brushes that have visible faces
    out = NULL;
    for (b=list ; b ; b=b->next)
    {
#if 0
        for (i=0 ; i<b->numsides ; i++)
            if (b->sides[i].flags & SFL_VISIBLE)
                break;
        if (i == b->numsides)
            continue;
#endif
        newb = CopyBrush (b);
        newb->next = out;
        out = newb;

        // clear visible, so it must be set by MarkVisibleFaces_r
        // to be used in the optimized list
        for (i=0 ; i<b->numsides ; i++)
        {
            newb->sides[i].original = &b->sides[i];
//          newb->sides[i].visible = true;
            b->sides[i].flags &= ~SFL_VISIBLE;
        }
    }

    return out;
} //end of the function InitialBrushList
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
bspbrush_t *OptimizedBrushList (bspbrush_t *list)
{
    bspbrush_t *b;
    bspbrush_t  *out, *newb;
    int         i;

    // only return brushes that have visible faces
    out = NULL;
    for (b=list ; b ; b=b->next)
    {
        for (i=0 ; i<b->numsides ; i++)
            if (b->sides[i].flags & SFL_VISIBLE)
                break;
        if (i == b->numsides)
            continue;
        newb = CopyBrush (b);
        newb->next = out;
        out = newb;
    } //end for

//  WriteBrushList ("vis.gl", out, true);
    return out;
} //end of the function OptimizeBrushList
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tree_t *ProcessWorldBrushes(int brush_start, int brush_end)
{
    bspbrush_t *brushes;
    tree_t *tree;
    node_t *node;
    vec3_t mins, maxs;

    //take the whole world
    mins[0] = map_mins[0] - 8;
    mins[1] = map_mins[1] - 8;
    mins[2] = map_mins[2] - 8;

    maxs[0] = map_maxs[0] + 8;
    maxs[1] = map_maxs[1] + 8;
    maxs[2] = map_maxs[2] + 8;

    //reset the brush bsp
    ResetBrushBSP();

    // the makelist and chopbrushes could be cached between the passes...

    //create a list with brushes that are within the given mins/maxs
    //some brushes will be cut and only the part that falls within the
    //mins/maxs will be in the bush list
    brushes = MakeBspBrushList(brush_start, brush_end, mins, maxs);
    //

    if (!brushes)
    {
        node = AllocNode ();
        node->planenum = PLANENUM_LEAF;
        node->contents = CONTENTS_SOLID;

        tree = Tree_Alloc();
        tree->headnode = node;
        VectorCopy(mins, tree->mins);
        VectorCopy(maxs, tree->maxs);
    } //end if
    else
    {
        //Carves any intersecting solid brushes into the minimum number
        //of non-intersecting brushes. 
        if (!nocsg)
        {
            brushes = ChopBrushes(brushes);
            /*
            if (create_aas)
            {
                brushes = MergeBrushes(brushes);
            } //end if*/
        } //end if
        //if the conversion is cancelled
        if (cancelconversion)
        {
            FreeBrushList(brushes);
            return NULL;
        } //end if
        //create the actual bsp tree
        tree = BrushBSP(brushes, mins, maxs);
    } //end else
    //return the tree
    return tree;
} //end of the function ProcessWorldBrushes

---