aas_create.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"
#include "../botlib/aasfile.h"
#include "aas_create.h"
#include "aas_store.h"
#include "aas_gsubdiv.h"
#include "aas_facemerging.h"
#include "aas_areamerging.h"
#include "aas_edgemelting.h"
#include "aas_prunenodes.h"
#include "aas_cfg.h"
#include "../game/surfaceflags.h"

//#define AW_DEBUG
//#define L_DEBUG

#define AREAONFACESIDE(face, area)      (face->frontarea != area)

tmp_aas_t tmpaasworld;

//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_InitTmpAAS(void)
{
    //tmp faces
    tmpaasworld.numfaces = 0;
    tmpaasworld.facenum = 0;
    tmpaasworld.faces = NULL;
    //tmp convex areas
    tmpaasworld.numareas = 0;
    tmpaasworld.areanum = 0;
    tmpaasworld.areas = NULL;
    //tmp nodes
    tmpaasworld.numnodes = 0;
    tmpaasworld.nodes = NULL;
    //
    tmpaasworld.nodebuffer = NULL;
} //end of the function AAS_InitTmpAAS
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FreeTmpAAS(void)
{
    tmp_face_t *f, *nextf;
    tmp_area_t *a, *nexta;
    tmp_nodebuf_t *nb, *nextnb;

    //free all the faces
    for (f = tmpaasworld.faces; f; f = nextf)
    {
        nextf = f->l_next;
        if (f->winding) FreeWinding(f->winding);
        FreeMemory(f);
    } //end if
    //free all tmp areas
    for (a = tmpaasworld.areas; a; a = nexta)
    {
        nexta = a->l_next;
        if (a->settings) FreeMemory(a->settings);
        FreeMemory(a);
    } //end for
    //free all the tmp nodes
    for (nb = tmpaasworld.nodebuffer; nb; nb = nextnb)
    {
        nextnb = nb->next;
        FreeMemory(nb);
    } //end for
} //end of the function AAS_FreeTmpAAS
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_face_t *AAS_AllocTmpFace(void)
{
    tmp_face_t *tmpface;

    tmpface = (tmp_face_t *) GetClearedMemory(sizeof(tmp_face_t));
    tmpface->num = tmpaasworld.facenum++;
    tmpface->l_prev = NULL;
    tmpface->l_next = tmpaasworld.faces;
    if (tmpaasworld.faces) tmpaasworld.faces->l_prev = tmpface;
    tmpaasworld.faces = tmpface;
    tmpaasworld.numfaces++;
    return tmpface;
} //end of the function AAS_AllocTmpFace
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FreeTmpFace(tmp_face_t *tmpface)
{
    if (tmpface->l_next) tmpface->l_next->l_prev = tmpface->l_prev;
    if (tmpface->l_prev) tmpface->l_prev->l_next = tmpface->l_next;
    else tmpaasworld.faces = tmpface->l_next;
    //free the winding
    if (tmpface->winding) FreeWinding(tmpface->winding);
    //free the face
    FreeMemory(tmpface);
    tmpaasworld.numfaces--;
} //end of the function AAS_FreeTmpFace
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_area_t *AAS_AllocTmpArea(void)
{
    tmp_area_t *tmparea;

    tmparea = (tmp_area_t *) GetClearedMemory(sizeof(tmp_area_t));
    tmparea->areanum = tmpaasworld.areanum++;
    tmparea->l_prev = NULL;
    tmparea->l_next = tmpaasworld.areas;
    if (tmpaasworld.areas) tmpaasworld.areas->l_prev = tmparea;
    tmpaasworld.areas = tmparea;
    tmpaasworld.numareas++;
    return tmparea;
} //end of the function AAS_AllocTmpArea
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FreeTmpArea(tmp_area_t *tmparea)
{
    if (tmparea->l_next) tmparea->l_next->l_prev = tmparea->l_prev;
    if (tmparea->l_prev) tmparea->l_prev->l_next = tmparea->l_next;
    else tmpaasworld.areas = tmparea->l_next;
    if (tmparea->settings) FreeMemory(tmparea->settings);
    FreeMemory(tmparea);
    tmpaasworld.numareas--;
} //end of the function AAS_FreeTmpArea
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_node_t *AAS_AllocTmpNode(void)
{
    tmp_nodebuf_t *nodebuf;

    if (!tmpaasworld.nodebuffer ||
            tmpaasworld.nodebuffer->numnodes >= NODEBUF_SIZE)
    {
        nodebuf = (tmp_nodebuf_t *) GetClearedMemory(sizeof(tmp_nodebuf_t));
        nodebuf->next = tmpaasworld.nodebuffer;
        nodebuf->numnodes = 0;
        tmpaasworld.nodebuffer = nodebuf;
    } //end if
    tmpaasworld.numnodes++;
    return &tmpaasworld.nodebuffer->nodes[tmpaasworld.nodebuffer->numnodes++];
} //end of the function AAS_AllocTmpNode
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FreeTmpNode(tmp_node_t *tmpnode)
{
    tmpaasworld.numnodes--;
} //end of the function AAS_FreeTmpNode
//===========================================================================
// returns true if the face is a gap from the given side
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_GapFace(tmp_face_t *tmpface, int side)
{
    vec3_t invgravity;

    //if the face is a solid or ground face it can't be a gap
    if (tmpface->faceflags & (FACE_GROUND | FACE_SOLID)) return 0;

    VectorCopy(cfg.phys_gravitydirection, invgravity);
    VectorInverse(invgravity);

    return (DotProduct(invgravity, mapplanes[tmpface->planenum ^ side].normal) > cfg.phys_maxsteepness);
} //end of the function AAS_GapFace
//===========================================================================
// returns true if the face is a ground face
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_GroundFace(tmp_face_t *tmpface)
{
    vec3_t invgravity;

    //must be a solid face
    if (!(tmpface->faceflags & FACE_SOLID)) return 0;

    VectorCopy(cfg.phys_gravitydirection, invgravity);
    VectorInverse(invgravity);

    return (DotProduct(invgravity, mapplanes[tmpface->planenum].normal) > cfg.phys_maxsteepness);
} //end of the function AAS_GroundFace
//===========================================================================
// adds the side of a face to an area
//
// side :   0 = front side
//              1 = back side
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_AddFaceSideToArea(tmp_face_t *tmpface, int side, tmp_area_t *tmparea)
{
    int tmpfaceside;

    if (side)
    {
        if (tmpface->backarea) Error("AAS_AddFaceSideToArea: already a back area\n");
    } //end if
    else
    {
        if (tmpface->frontarea) Error("AAS_AddFaceSideToArea: already a front area\n");
    } //end else

    if (side) tmpface->backarea = tmparea;
    else tmpface->frontarea = tmparea;

    if (tmparea->tmpfaces)
    {
        tmpfaceside = tmparea->tmpfaces->frontarea != tmparea;
        tmparea->tmpfaces->prev[tmpfaceside] = tmpface;
    } //end if
    tmpface->next[side] = tmparea->tmpfaces;
    tmpface->prev[side] = NULL;
    tmparea->tmpfaces = tmpface;
} //end of the function AAS_AddFaceSideToArea
//===========================================================================
// remove (a side of) a face from an area
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_RemoveFaceFromArea(tmp_face_t *tmpface, tmp_area_t *tmparea)
{
    int side, prevside, nextside;

    if (tmpface->frontarea != tmparea &&
            tmpface->backarea != tmparea)
    {
        Error("AAS_RemoveFaceFromArea: face not part of the area");
    } //end if
    side = tmpface->frontarea != tmparea;
    if (tmpface->prev[side])
    {
        prevside = tmpface->prev[side]->frontarea != tmparea;
        tmpface->prev[side]->next[prevside] = tmpface->next[side];
    } //end if
    else
    {
        tmparea->tmpfaces = tmpface->next[side];
    } //end else
    if (tmpface->next[side])
    {
        nextside = tmpface->next[side]->frontarea != tmparea;
        tmpface->next[side]->prev[nextside] = tmpface->prev[side];
    } //end if
    //remove the area number from the face depending on the side
    if (side) tmpface->backarea = NULL;
    else tmpface->frontarea = NULL;
    tmpface->prev[side] = NULL;
    tmpface->next[side] = NULL;
} //end of the function AAS_RemoveFaceFromArea
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_CheckArea(tmp_area_t *tmparea)
{
    int side;
    tmp_face_t *face;
    plane_t *plane;
    vec3_t wcenter, acenter = {0, 0, 0};
    vec3_t normal;
    float n, dist;

    if (tmparea->invalid) Log_Print("AAS_CheckArea: invalid area\n");
    for (n = 0, face = tmparea->tmpfaces; face; face = face->next[side])
    {
        //side of the face the area is on
        side = face->frontarea != tmparea;
        WindingCenter(face->winding, wcenter);
        VectorAdd(acenter, wcenter, acenter);
        n++;
    } //end for
    n = 1 / n;
    VectorScale(acenter, n, acenter);
    for (face = tmparea->tmpfaces; face; face = face->next[side])
    {
        //side of the face the area is on
        side = face->frontarea != tmparea;

#ifdef L_DEBUG
        if (WindingError(face->winding))
        {
            Log_Write("AAS_CheckArea: area %d face %d: %s\r\n", tmparea->areanum,
                        face->num, WindingErrorString());
        } //end if
#endif L_DEBUG

        plane = &mapplanes[face->planenum ^ side];

        if (DotProduct(plane->normal, acenter) - plane->dist < 0)
        {
            Log_Print("AAS_CheckArea: area %d face %d is flipped\n", tmparea->areanum, face->num);
            Log_Print("AAS_CheckArea: area %d center is %f %f %f\n", tmparea->areanum, acenter[0], acenter[1], acenter[2]);
        } //end if
        //check if the winding plane is the same as the face plane
        WindingPlane(face->winding, normal, &dist);
        plane = &mapplanes[face->planenum];
#ifdef L_DEBUG
        if (fabs(dist - plane->dist) > 0.4 ||
                fabs(normal[0] - plane->normal[0]) > 0.0001 ||
                fabs(normal[1] - plane->normal[1]) > 0.0001 ||
                fabs(normal[2] - plane->normal[2]) > 0.0001)
        {
            Log_Write("AAS_CheckArea: area %d face %d winding plane unequal to face plane\r\n",
                                        tmparea->areanum, face->num);
        } //end if
#endif L_DEBUG
    } //end for
} //end of the function AAS_CheckArea
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_CheckFaceWindingPlane(tmp_face_t *face)
{
    float dist, sign1, sign2;
    vec3_t normal;
    plane_t *plane;
    winding_t *w;

    //check if the winding plane is the same as the face plane
    WindingPlane(face->winding, normal, &dist);
    plane = &mapplanes[face->planenum];
    //
    sign1 = DotProduct(plane->normal, normal);
    //
    if (fabs(dist - plane->dist) > 0.4 ||
            fabs(normal[0] - plane->normal[0]) > 0.0001 ||
            fabs(normal[1] - plane->normal[1]) > 0.0001 ||
            fabs(normal[2] - plane->normal[2]) > 0.0001)
    {
        VectorInverse(normal);
        dist = -dist;
        if (fabs(dist - plane->dist) > 0.4 ||
                fabs(normal[0] - plane->normal[0]) > 0.0001 ||
                fabs(normal[1] - plane->normal[1]) > 0.0001 ||
                fabs(normal[2] - plane->normal[2]) > 0.0001)
        {
            Log_Write("AAS_CheckFaceWindingPlane: face %d winding plane unequal to face plane\r\n",
                                    face->num);
            //
            sign2 = DotProduct(plane->normal, normal);
            if ((sign1 < 0 && sign2 > 0) ||
                    (sign1 > 0 && sign2 < 0))
            {
                Log_Write("AAS_CheckFaceWindingPlane: face %d winding reversed\r\n",
                                    face->num);
                w = face->winding;
                face->winding = ReverseWinding(w);
                FreeWinding(w);
            } //end if
        } //end if
        else
        {
            Log_Write("AAS_CheckFaceWindingPlane: face %d winding reversed\r\n",
                                    face->num);
            w = face->winding;
            face->winding = ReverseWinding(w);
            FreeWinding(w);
        } //end else
    } //end if
} //end of the function AAS_CheckFaceWindingPlane
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_CheckAreaWindingPlanes(void)
{
    int side;
    tmp_area_t *tmparea;
    tmp_face_t *face;

    Log_Write("AAS_CheckAreaWindingPlanes:\r\n");
    for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next)
    {
        if (tmparea->invalid) continue;
        for (face = tmparea->tmpfaces; face; face = face->next[side])
        {
            side = face->frontarea != tmparea;
            AAS_CheckFaceWindingPlane(face);
        } //end for
    } //end for
} //end of the function AAS_CheckAreaWindingPlanes
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FlipAreaFaces(tmp_area_t *tmparea)
{
    int side;
    tmp_face_t *face;
    plane_t *plane;
    vec3_t wcenter, acenter = {0, 0, 0};
    //winding_t *w;
    float n;

    for (n = 0, face = tmparea->tmpfaces; face; face = face->next[side])
    {
        if (!face->frontarea) Error("face %d has no front area\n", face->num);
        //side of the face the area is on
        side = face->frontarea != tmparea;
        WindingCenter(face->winding, wcenter);
        VectorAdd(acenter, wcenter, acenter);
        n++;
    } //end for
    n = 1 / n;
    VectorScale(acenter, n, acenter);
    for (face = tmparea->tmpfaces; face; face = face->next[side])
    {
        //side of the face the area is on
        side = face->frontarea != tmparea;

        plane = &mapplanes[face->planenum ^ side];

        if (DotProduct(plane->normal, acenter) - plane->dist < 0)
        {
            Log_Print("area %d face %d flipped: front area %d, back area %d\n", tmparea->areanum, face->num,
                    face->frontarea ? face->frontarea->areanum : 0,
                    face->backarea ? face->backarea->areanum : 0);
            /*
            face->planenum = face->planenum ^ 1;
            w = face->winding;
            face->winding = ReverseWinding(w);
            FreeWinding(w);
            */
        } //end if
#ifdef L_DEBUG
        {
            float dist;
            vec3_t normal;

            //check if the winding plane is the same as the face plane
            WindingPlane(face->winding, normal, &dist);
            plane = &mapplanes[face->planenum];
            if (fabs(dist - plane->dist) > 0.4 ||
                    fabs(normal[0] - plane->normal[0]) > 0.0001 ||
                    fabs(normal[1] - plane->normal[1]) > 0.0001 ||
                    fabs(normal[2] - plane->normal[2]) > 0.0001)
            {
                Log_Write("area %d face %d winding plane unequal to face plane\r\n",
                                            tmparea->areanum, face->num);
            } //end if
        }
#endif
    } //end for
} //end of the function AAS_FlipAreaFaces
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_RemoveAreaFaceColinearPoints(void)
{
    int side;
    tmp_face_t *face;
    tmp_area_t *tmparea;

    //FIXME: loop over the faces instead of area->faces
    for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next)
    {
        for (face = tmparea->tmpfaces; face; face = face->next[side])
        {
            side = face->frontarea != tmparea;
            RemoveColinearPoints(face->winding);
//          RemoveEqualPoints(face->winding, 0.1);
        } //end for
    } //end for
} //end of the function AAS_RemoveAreaFaceColinearPoints
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_RemoveTinyFaces(void)
{
    int side, num;
    tmp_face_t *face, *nextface;
    tmp_area_t *tmparea;

    //FIXME: loop over the faces instead of area->faces
    Log_Write("AAS_RemoveTinyFaces\r\n");
    num = 0;
    for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next)
    {
        for (face = tmparea->tmpfaces; face; face = nextface)
        {
            side = face->frontarea != tmparea;
            nextface = face->next[side];
            //
            if (WindingArea(face->winding) < 1)
            {
                if (face->frontarea) AAS_RemoveFaceFromArea(face, face->frontarea);
                if (face->backarea) AAS_RemoveFaceFromArea(face, face->backarea);
                AAS_FreeTmpFace(face);
                //Log_Write("area %d face %d is tiny\r\n", tmparea->areanum, face->num);
                num++;
            } //end if
        } //end for
    } //end for
    Log_Write("%d tiny faces removed\r\n", num);
} //end of the function AAS_RemoveTinyFaces
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_CreateAreaSettings(void)
{
    int i, flags, side, numgrounded, numladderareas, numliquidareas;
    tmp_face_t *face;
    tmp_area_t *tmparea;

    numgrounded = 0;
    numladderareas = 0;
    numliquidareas = 0;
    Log_Write("AAS_CreateAreaSettings\r\n");
    i = 0;
    qprintf("%6d areas provided with settings", i);
    for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next)
    {
        //if the area is invalid there no need to create settings for it
        if (tmparea->invalid) continue;

        tmparea->settings = (tmp_areasettings_t *) GetClearedMemory(sizeof(tmp_areasettings_t));
        tmparea->settings->contents = tmparea->contents;
        tmparea->settings->modelnum = tmparea->modelnum;
        flags = 0;
        for (face = tmparea->tmpfaces; face; face = face->next[side])
        {
            side = face->frontarea != tmparea;
            flags |= face->faceflags;
        } //end for
        tmparea->settings->areaflags = 0;
        if (flags & FACE_GROUND)
        {
            tmparea->settings->areaflags |= AREA_GROUNDED;
            numgrounded++;
        } //end if
        if (flags & FACE_LADDER)
        {
            tmparea->settings->areaflags |= AREA_LADDER;
            numladderareas++;
        } //end if
        if (tmparea->contents & (AREACONTENTS_WATER |
                                            AREACONTENTS_SLIME |
                                            AREACONTENTS_LAVA))
        {
            tmparea->settings->areaflags |= AREA_LIQUID;
            numliquidareas++;
        } //end if
        //presence type of the area
        tmparea->settings->presencetype = tmparea->presencetype;
        //
        qprintf("\r%6d", ++i);
    } //end for
    qprintf("\n");
#ifdef AASINFO
    Log_Print("%6d grounded areas\n", numgrounded);
    Log_Print("%6d ladder areas\n", numladderareas);
    Log_Print("%6d liquid areas\n", numliquidareas);
#endif //AASINFO
} //end of the function AAS_CreateAreaSettings
//===========================================================================
// create a tmp AAS area from a leaf node
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_node_t *AAS_CreateArea(node_t *node)
{
    int pside;
    int areafaceflags;
    portal_t    *p;
    tmp_face_t *tmpface;
    tmp_area_t *tmparea;
    tmp_node_t *tmpnode;
    vec3_t up = {0, 0, 1};

    //create an area from this leaf
    tmparea = AAS_AllocTmpArea();
    tmparea->tmpfaces = NULL;
    //clear the area face flags
    areafaceflags = 0;
    //make aas faces from the portals
    for (p = node->portals; p; p = p->next[pside])
    {
        pside = (p->nodes[1] == node);
        //don't create faces from very small portals
//      if (WindingArea(p->winding) < 1) continue;
        //if there's already a face created for this portal
        if (p->tmpface)
        {
            //add the back side of the face to the area
            AAS_AddFaceSideToArea(p->tmpface, 1, tmparea);
        } //end if
        else
        {
            tmpface = AAS_AllocTmpFace();
            //set the face pointer at the portal so we can see from
            //the portal there's a face created for it
            p->tmpface = tmpface;
            //FIXME: test this change
            //tmpface->planenum = (p->planenum & ~1) | pside;
            tmpface->planenum = p->planenum ^ pside;
            if (pside) tmpface->winding = ReverseWinding(p->winding);
            else tmpface->winding = CopyWinding(p->winding);
#ifdef L_DEBUG
            //
            AAS_CheckFaceWindingPlane(tmpface);
#endif //L_DEBUG
            //if there's solid at the other side of the portal
            if (p->nodes[!pside]->contents & (CONTENTS_SOLID | CONTENTS_PLAYERCLIP))
            {
                tmpface->faceflags |= FACE_SOLID;
            } //end if
            //else there is no solid at the other side and if there
            //is a liquid at this side
            else if (node->contents & (CONTENTS_WATER|CONTENTS_SLIME|CONTENTS_LAVA))
            {
                tmpface->faceflags |= FACE_LIQUID;
                //if there's no liquid at the other side
                if (!(p->nodes[!pside]->contents & (CONTENTS_WATER|CONTENTS_SLIME|CONTENTS_LAVA)))
                {
                    tmpface->faceflags |= FACE_LIQUIDSURFACE;
                } //end if
            } //end else
            //if there's ladder contents at other side of the portal
            if ((p->nodes[pside]->contents & CONTENTS_LADDER) ||
                    (p->nodes[!pside]->contents & CONTENTS_LADDER))
            {

                //NOTE: doesn't have to be solid at the other side because
                // when standing one can use a crouch area (which is not solid)
                // as a ladder
                // imagine a ladder one can walk underthrough,
                // under the ladder against the ladder is a crouch area
                // the (vertical) sides of this crouch area area also used as
                // ladder sides when standing (not crouched)
                tmpface->faceflags |= FACE_LADDER;
            } //end if
            //if it is possible to stand on the face
            if (AAS_GroundFace(tmpface))
            {
                tmpface->faceflags |= FACE_GROUND;
            } //end if
            //
            areafaceflags |= tmpface->faceflags;
            //no aas face number yet (zero is a dummy in the aasworld faces)
            tmpface->aasfacenum = 0;
            //add the front side of the face to the area
            AAS_AddFaceSideToArea(tmpface, 0, tmparea);
        } //end else
    } //end for
    qprintf("\r%6d", tmparea->areanum);
    //presence type in the area
    tmparea->presencetype = ~node->expansionbboxes & cfg.allpresencetypes;
    //
    tmparea->contents = 0;
    if (node->contents & CONTENTS_CLUSTERPORTAL) tmparea->contents |= AREACONTENTS_CLUSTERPORTAL;
    if (node->contents & CONTENTS_MOVER) tmparea->contents |= AREACONTENTS_MOVER;
    if (node->contents & CONTENTS_TELEPORTER) tmparea->contents |= AREACONTENTS_TELEPORTER;
    if (node->contents & CONTENTS_JUMPPAD) tmparea->contents |= AREACONTENTS_JUMPPAD;
    if (node->contents & CONTENTS_DONOTENTER) tmparea->contents |= AREACONTENTS_DONOTENTER;
    if (node->contents & CONTENTS_WATER) tmparea->contents |= AREACONTENTS_WATER;
    if (node->contents & CONTENTS_LAVA) tmparea->contents |= AREACONTENTS_LAVA;
    if (node->contents & CONTENTS_SLIME) tmparea->contents |= AREACONTENTS_SLIME;
    if (node->contents & CONTENTS_NOTTEAM1) tmparea->contents |= AREACONTENTS_NOTTEAM1;
    if (node->contents & CONTENTS_NOTTEAM2) tmparea->contents |= AREACONTENTS_NOTTEAM2;

    //store the bsp model that's inside this node
    tmparea->modelnum = node->modelnum;
    //sorta check for flipped area faces (remove??)
    AAS_FlipAreaFaces(tmparea);
    //check if the area is ok (remove??)
    AAS_CheckArea(tmparea);
    //
    tmpnode = AAS_AllocTmpNode();
    tmpnode->planenum = 0;
    tmpnode->children[0] = 0;
    tmpnode->children[1] = 0;
    tmpnode->tmparea = tmparea;
    //
    return tmpnode;
} //end of the function AAS_CreateArea
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_node_t *AAS_CreateAreas_r(node_t *node)
{
    tmp_node_t *tmpnode;

    //recurse down to leafs
    if (node->planenum != PLANENUM_LEAF)
    {
        //the first tmp node is a dummy
        tmpnode = AAS_AllocTmpNode();
        tmpnode->planenum = node->planenum;
        tmpnode->children[0] = AAS_CreateAreas_r(node->children[0]);
        tmpnode->children[1] = AAS_CreateAreas_r(node->children[1]);
        return tmpnode;
    } //end if
    //areas won't be created for solid leafs
    if (node->contents & CONTENTS_SOLID)
    {
        //just return zero for a solid leaf (in tmp AAS NULL is a solid leaf)
        return NULL;
    } //end if

    return AAS_CreateArea(node);
} //end of the function AAS_CreateAreas_r
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_CreateAreas(node_t *node)
{
    Log_Write("AAS_CreateAreas\r\n");
    qprintf("%6d areas created", 0);
    tmpaasworld.nodes = AAS_CreateAreas_r(node);
    qprintf("\n");
    Log_Write("%6d areas created\r\n", tmpaasworld.numareas);
} //end of the function AAS_CreateAreas
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_PrintNumGroundFaces(void)
{
    tmp_face_t *tmpface;
    int numgroundfaces = 0;

    for (tmpface = tmpaasworld.faces; tmpface; tmpface = tmpface->l_next)
    {
        if (tmpface->faceflags & FACE_GROUND)
        {
            numgroundfaces++;
        } //end if
    } //end for
    qprintf("%6d ground faces\n", numgroundfaces);
} //end of the function AAS_PrintNumGroundFaces
//===========================================================================
// checks the number of shared faces between the given two areas
// since areas are convex they should only have ONE shared face
// however due to crappy face merging there are sometimes several
// shared faces
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_CheckAreaSharedFaces(tmp_area_t *tmparea1, tmp_area_t *tmparea2)
{
    int numsharedfaces, side;
    tmp_face_t *face1, *sharedface;

    if (tmparea1->invalid || tmparea2->invalid) return;

    sharedface = NULL;
    numsharedfaces = 0;
    for (face1 = tmparea1->tmpfaces; face1; face1 = face1->next[side])
    {
        side = face1->frontarea != tmparea1;
        if (face1->backarea == tmparea2 || face1->frontarea == tmparea2)
        {
            sharedface = face1;
            numsharedfaces++;
        } //end if
    } //end if
    if (!sharedface) return;
    //the areas should only have one shared face
    if (numsharedfaces > 1)
    {
        Log_Write("---- tmp area %d and %d have %d shared faces\r\n",
                                    tmparea1->areanum, tmparea2->areanum, numsharedfaces);
        for (face1 = tmparea1->tmpfaces; face1; face1 = face1->next[side])
        {
            side = face1->frontarea != tmparea1;
            if (face1->backarea == tmparea2 || face1->frontarea == tmparea2)
            {
                Log_Write("face %d, planenum = %d, face->frontarea = %d face->backarea = %d\r\n",
                                face1->num, face1->planenum, face1->frontarea->areanum, face1->backarea->areanum);
            } //end if
        } //end if
    } //end if
} //end of the function AAS_CheckAreaSharedFaces
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_CheckSharedFaces(void)
{
    tmp_area_t *tmparea1, *tmparea2;

    for (tmparea1 = tmpaasworld.areas; tmparea1; tmparea1 = tmparea1->l_next)
    {
        for (tmparea2 = tmpaasworld.areas; tmparea2; tmparea2 = tmparea2->l_next)
        {
            if (tmparea1 == tmparea2) continue;
            AAS_CheckAreaSharedFaces(tmparea1, tmparea2);
        } //end for
    } //end for
} //end of the function AAS_CheckSharedFaces
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FlipFace(tmp_face_t *face)
{
    tmp_area_t *frontarea, *backarea;
    winding_t *w;

    frontarea = face->frontarea;
    backarea = face->backarea;
    //must have an area at both sides before flipping is allowed
    if (!frontarea || !backarea) return;
    //flip the face winding
    w = face->winding;
    face->winding = ReverseWinding(w);
    FreeWinding(w);
    //flip the face plane
    face->planenum ^= 1;
    //flip the face areas
    AAS_RemoveFaceFromArea(face, frontarea);
    AAS_RemoveFaceFromArea(face, backarea);
    AAS_AddFaceSideToArea(face, 1, frontarea);
    AAS_AddFaceSideToArea(face, 0, backarea);
} //end of the function AAS_FlipFace
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
/*
void AAS_FlipAreaSharedFaces(tmp_area_t *tmparea1, tmp_area_t *tmparea2)
{
    int numsharedfaces, side, area1facing, area2facing;
    tmp_face_t *face1, *sharedface;

    if (tmparea1->invalid || tmparea2->invalid) return;

    sharedface = NULL;
    numsharedfaces = 0;
    area1facing = 0;        //number of shared faces facing towards area 1
    area2facing = 0;        //number of shared faces facing towards area 2
    for (face1 = tmparea1->tmpfaces; face1; face1 = face1->next[side])
    {
        side = face1->frontarea != tmparea1;
        if (face1->backarea == tmparea2 || face1->frontarea == tmparea2)
        {
            sharedface = face1;
            numsharedfaces++;
            if (face1->frontarea == tmparea1) area1facing++;
            else area2facing++;
        } //end if
    } //end if
    if (!sharedface) return;
    //if there's only one shared face
    if (numsharedfaces <= 1) return;
    //if all the shared faces are facing to the same area
    if (numsharedfaces == area1facing || numsharedfaces == area2facing) return;
    //
    do
    {
        for (face1 = tmparea1->tmpfaces; face1; face1 = face1->next[side])
        {
            side = face1->frontarea != tmparea1;
            if (face1->backarea == tmparea2 || face1->frontarea == tmparea2)
            {
                if (face1->frontarea != tmparea1)
                {
                    AAS_FlipFace(face1);
                    break;
                } //end if
            } //end if
        } //end for
    } while(face1);
} //end of the function AAS_FlipAreaSharedFaces
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FlipSharedFaces(void)
{
    int i;
    tmp_area_t *tmparea1, *tmparea2;

    i = 0;
    qprintf("%6d areas checked for shared face flipping", i);
    for (tmparea1 = tmpaasworld.areas; tmparea1; tmparea1 = tmparea1->l_next)
    {
        if (tmparea1->invalid) continue;
        for (tmparea2 = tmpaasworld.areas; tmparea2; tmparea2 = tmparea2->l_next)
        {
            if (tmparea2->invalid) continue;
            if (tmparea1 == tmparea2) continue;
            AAS_FlipAreaSharedFaces(tmparea1, tmparea2);
        } //end for
        qprintf("\r%6d", ++i);
    } //end for
    Log_Print("\r%6d areas checked for shared face flipping\n", i);
} //end of the function AAS_FlipSharedFaces
*/
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_FlipSharedFaces(void)
{
    int i, side1, side2;
    tmp_area_t *tmparea1;
    tmp_face_t *face1, *face2;

    i = 0;
    qprintf("%6d areas checked for shared face flipping", i);
    for (tmparea1 = tmpaasworld.areas; tmparea1; tmparea1 = tmparea1->l_next)
    {
        if (tmparea1->invalid) continue;
        for (face1 = tmparea1->tmpfaces; face1; face1 = face1->next[side1])
        {
            side1 = face1->frontarea != tmparea1;
            if (!face1->frontarea || !face1->backarea) continue;
            //
            for (face2 = face1->next[side1]; face2; face2 = face2->next[side2])
            {
                side2 = face2->frontarea != tmparea1;
                if (!face2->frontarea || !face2->backarea) continue;
                //
                if (face1->frontarea == face2->backarea &&
                    face1->backarea == face2->frontarea)
                {
                    AAS_FlipFace(face2);
                } //end if
                //recheck side
                side2 = face2->frontarea != tmparea1;
            } //end for
        } //end for
        qprintf("\r%6d", ++i);
    } //end for
    qprintf("\n");
    Log_Write("%6d areas checked for shared face flipping\r\n", i);
} //end of the function AAS_FlipSharedFaces
//===========================================================================
// creates an .AAS file with the given name
// a MAP should be loaded before calling this
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_Create(char *aasfile)
{
    entity_t    *e;
    tree_t *tree;
    double start_time;

    //for a possible leak file
    strcpy(source, aasfile);
    StripExtension(source);
    //the time started
    start_time = I_FloatTime();
    //set the default number of threads (depends on number of processors)
    ThreadSetDefault();
    //set the global entity number to the world model
    entity_num = 0;
    //the world entity
    e = &entities[entity_num];
    //process the whole world
    tree = ProcessWorldBrushes(e->firstbrush, e->firstbrush + e->numbrushes);
    //if the conversion is cancelled
    if (cancelconversion)
    {
        Tree_Free(tree);
        return;
    } //end if
    //display BSP tree creation time
    Log_Print("BSP tree created in %5.0f seconds\n", I_FloatTime() - start_time);
    //prune the bsp tree
    Tree_PruneNodes(tree->headnode);
    //if the conversion is cancelled
    if (cancelconversion)
    {
        Tree_Free(tree);
        return;
    } //end if
    //create the tree portals
    MakeTreePortals(tree);
    //if the conversion is cancelled
    if (cancelconversion)
    {
        Tree_Free(tree);
        return;
    } //end if
    //Marks all nodes that can be reached by entites
    if (FloodEntities(tree))
    {
        //fill out nodes that can't be reached
        FillOutside(tree->headnode);
    } //end if
    else
    {
        LeakFile(tree);
        Error("**** leaked ****\n");
        return;
    } //end else
    //create AAS from the BSP tree
    //==========================================
    //initialize tmp aas
    AAS_InitTmpAAS();
    //create the convex areas from the leaves
    AAS_CreateAreas(tree->headnode);
    //free the BSP tree because it isn't used anymore
    if (freetree) Tree_Free(tree);
    //try to merge area faces
    AAS_MergeAreaFaces();
    //do gravitational subdivision
    AAS_GravitationalSubdivision();
    //merge faces if possible
    AAS_MergeAreaFaces();
    AAS_RemoveAreaFaceColinearPoints();
    //merge areas if possible
    AAS_MergeAreas();
    //NOTE: prune nodes directly after area merging
    AAS_PruneNodes();
    //flip shared faces so they are all facing to the same area
    AAS_FlipSharedFaces();
    AAS_RemoveAreaFaceColinearPoints();
    //merge faces if possible
    AAS_MergeAreaFaces();
    //merge area faces in the same plane
    AAS_MergeAreaPlaneFaces();
    //do ladder subdivision
    AAS_LadderSubdivision();
    //FIXME: melting is buggy
    AAS_MeltAreaFaceWindings();
    //remove tiny faces
    AAS_RemoveTinyFaces();
    //create area settings
    AAS_CreateAreaSettings();
    //check if the winding plane is equal to the face plane
    //AAS_CheckAreaWindingPlanes();
    //
    //AAS_CheckSharedFaces();
    //==========================================
    //if the conversion is cancelled
    if (cancelconversion)
    {
        Tree_Free(tree);
        AAS_FreeTmpAAS();
        return;
    } //end if
    //store the created AAS stuff in the AAS file format and write the file
    AAS_StoreFile(aasfile);
    //free the temporary AAS memory
    AAS_FreeTmpAAS();
    //display creation time
    Log_Print("\nAAS created in %5.0f seconds\n", I_FloatTime() - start_time);
} //end of the function AAS_Create

---