aas_gsubdiv.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_cfg.h"

#define FACECLIP_EPSILON            0.2
#define FACE_EPSILON                    1.0

int numgravitationalsubdivisions = 0;
int numladdersubdivisions = 0;

//NOTE: only do gravitational subdivision BEFORE area merging!!!!!!!
//          because the bsp tree isn't refreshes like with ladder subdivision

//===========================================================================
// NOTE: the original face is invalid after splitting
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_SplitFace(tmp_face_t *face, vec3_t normal, float dist,
                            tmp_face_t **frontface, tmp_face_t **backface)
{
    winding_t *frontw, *backw;

    //
    *frontface = *backface = NULL;

    ClipWindingEpsilon(face->winding, normal, dist, FACECLIP_EPSILON, &frontw, &backw);

#ifdef DEBUG
    //
    if (frontw)
    {
        if (WindingIsTiny(frontw))
        {
            Log_Write("AAS_SplitFace: tiny back face\r\n");
            FreeWinding(frontw);
            frontw = NULL;
        } //end if
    } //end if
    if (backw)
    {
        if (WindingIsTiny(backw))
        {
            Log_Write("AAS_SplitFace: tiny back face\r\n");
            FreeWinding(backw);
            backw = NULL;
        } //end if
    } //end if
#endif //DEBUG
    //if the winding was split
    if (frontw)
    {
        //check bounds
        (*frontface) = AAS_AllocTmpFace();
        (*frontface)->planenum = face->planenum;
        (*frontface)->winding = frontw;
        (*frontface)->faceflags = face->faceflags;
    } //end if
    if (backw)
    {
        //check bounds
        (*backface) = AAS_AllocTmpFace();
        (*backface)->planenum = face->planenum;
        (*backface)->winding = backw;
        (*backface)->faceflags = face->faceflags;
    } //end if
} //end of the function AAS_SplitFace
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
winding_t *AAS_SplitWinding(tmp_area_t *tmparea, int planenum)
{
    tmp_face_t *face;
    plane_t *plane;
    int side;
    winding_t *splitwinding;

    //
    plane = &mapplanes[planenum];
    //create a split winding, first base winding for plane
    splitwinding = BaseWindingForPlane(plane->normal, plane->dist);
    //chop with all the faces of the area
    for (face = tmparea->tmpfaces; face && splitwinding; face = face->next[side])
    {
        //side of the face the original area was on
        side = face->frontarea != tmparea;
        plane = &mapplanes[face->planenum ^ side];
        ChopWindingInPlace(&splitwinding, plane->normal, plane->dist, 0); // PLANESIDE_EPSILON);
    } //end for
    return splitwinding;
} //end of the function AAS_SplitWinding
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_TestSplitPlane(tmp_area_t *tmparea, vec3_t normal, float dist,
                            int *facesplits, int *groundsplits, int *epsilonfaces)
{
    int j, side, front, back, planenum;
    float d, d_front, d_back;
    tmp_face_t *face;
    winding_t *w;

    *facesplits = *groundsplits = *epsilonfaces = 0;

    planenum = FindFloatPlane(normal, dist);

    w = AAS_SplitWinding(tmparea, planenum);
    if (!w) return false;
    FreeWinding(w);
    //
    for (face = tmparea->tmpfaces; face; face = face->next[side])
    {
        //side of the face the area is on
        side = face->frontarea != tmparea;

        if ((face->planenum & ~1) == (planenum & ~1))
        {
            Log_Print("AAS_TestSplitPlane: tried face plane as splitter\n");
            return false;
        } //end if
        w = face->winding;
        //reset distance at front and back side of plane
        d_front = d_back = 0;
        //reset front and back flags
        front = back = 0;
        for (j = 0; j < w->numpoints; j++)
        {
            d = DotProduct(w->p[j], normal) - dist;
            if (d > d_front) d_front = d;
            if (d < d_back) d_back = d;

            if (d > 0.4) // PLANESIDE_EPSILON)
                front = 1;
            if (d < -0.4) // PLANESIDE_EPSILON)
                back = 1;
        } //end for
        //check for an epsilon face
        if ( (d_front > FACECLIP_EPSILON && d_front < FACE_EPSILON)
            || (d_back < -FACECLIP_EPSILON && d_back > -FACE_EPSILON) )
        {
            (*epsilonfaces)++;
        } //end if
        //if the face has points at both sides of the plane
        if (front && back)
        {
            (*facesplits)++;
            if (face->faceflags & FACE_GROUND)
            {
                (*groundsplits)++;
            } //end if
        } //end if
    } //end for
    return true;
} //end of the function AAS_TestSplitPlane
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_SplitArea(tmp_area_t *tmparea, int planenum, tmp_area_t **frontarea, tmp_area_t **backarea)
{
    int side;
    tmp_area_t *facefrontarea, *facebackarea, *faceotherarea;
    tmp_face_t *face, *frontface, *backface, *splitface, *nextface;
    winding_t *splitwinding;
    plane_t *splitplane;

/*
#ifdef AW_DEBUG
    int facesplits, groundsplits, epsilonface;
    Log_Print("\n----------------------\n");
    Log_Print("splitting area %d\n", areanum);
    Log_Print("with normal = \'%f %f %f\', dist = %f\n", normal[0], normal[1], normal[2], dist);
    AAS_TestSplitPlane(areanum, normal, dist,
                                        &facesplits, &groundsplits, &epsilonface);
    Log_Print("face splits = %d\nground splits = %d\n", facesplits, groundsplits);
    if (epsilonface) Log_Print("aaahh epsilon face\n");
#endif //AW_DEBUG*/
    //the original area

    AAS_FlipAreaFaces(tmparea);
    AAS_CheckArea(tmparea);
    //
    splitplane = &mapplanes[planenum];
/*  //create a split winding, first base winding for plane
    splitwinding = BaseWindingForPlane(splitplane->normal, splitplane->dist);
    //chop with all the faces of the area
    for (face = tmparea->tmpfaces; face && splitwinding; face = face->next[side])
    {
        //side of the face the original area was on
        side = face->frontarea != tmparea->areanum;
        plane = &mapplanes[face->planenum ^ side];
        ChopWindingInPlace(&splitwinding, plane->normal, plane->dist, 0); // PLANESIDE_EPSILON);
    } //end for*/
    splitwinding = AAS_SplitWinding(tmparea, planenum);
    if (!splitwinding)
    {
/*
#ifdef DEBUG
        AAS_TestSplitPlane(areanum, normal, dist,
                                            &facesplits, &groundsplits, &epsilonface);
        Log_Print("\nface splits = %d\nground splits = %d\n", facesplits, groundsplits);
        if (epsilonface) Log_Print("aaahh epsilon face\n");
#endif //DEBUG*/
        Error("AAS_SplitArea: no split winding when splitting area %d\n", tmparea->areanum);
    } //end if
    //create a split face
    splitface = AAS_AllocTmpFace();
    //get the map plane
    splitface->planenum = planenum;
    //store the split winding
    splitface->winding = splitwinding;
    //the new front area
    (*frontarea) = AAS_AllocTmpArea();
    (*frontarea)->presencetype = tmparea->presencetype;
    (*frontarea)->contents = tmparea->contents;
    (*frontarea)->modelnum = tmparea->modelnum;
    (*frontarea)->tmpfaces = NULL;
    //the new back area
    (*backarea) = AAS_AllocTmpArea();
    (*backarea)->presencetype = tmparea->presencetype;
    (*backarea)->contents = tmparea->contents;
    (*backarea)->modelnum = tmparea->modelnum;
    (*backarea)->tmpfaces = NULL;
    //add the split face to the new areas
    AAS_AddFaceSideToArea(splitface, 0, (*frontarea));
    AAS_AddFaceSideToArea(splitface, 1, (*backarea));

    //split all the faces of the original area
    for (face = tmparea->tmpfaces; face; face = nextface)
    {
        //side of the face the original area was on
        side = face->frontarea != tmparea;
        //next face of the original area
        nextface = face->next[side];
        //front area of the face
        facefrontarea = face->frontarea;
        //back area of the face
        facebackarea = face->backarea;
        //remove the face from both the front and back areas
        if (facefrontarea) AAS_RemoveFaceFromArea(face, facefrontarea);
        if (facebackarea) AAS_RemoveFaceFromArea(face, facebackarea);
        //split the face
        AAS_SplitFace(face, splitplane->normal, splitplane->dist, &frontface, &backface);
        //free the original face
        AAS_FreeTmpFace(face);
        //get the number of the area at the other side of the face
        if (side) faceotherarea = facefrontarea;
        else faceotherarea = facebackarea;
        //if there is an area at the other side of the original face
        if (faceotherarea)
        {
            if (frontface) AAS_AddFaceSideToArea(frontface, !side, faceotherarea);
            if (backface) AAS_AddFaceSideToArea(backface, !side, faceotherarea);
        } //end if
        //add the front and back part left after splitting the original face to the new areas
        if (frontface) AAS_AddFaceSideToArea(frontface, side, (*frontarea));
        if (backface) AAS_AddFaceSideToArea(backface, side, (*backarea));
    } //end for

    if (!(*frontarea)->tmpfaces) Log_Print("AAS_SplitArea: front area without faces\n");
    if (!(*backarea)->tmpfaces) Log_Print("AAS_SplitArea: back area without faces\n");

    tmparea->invalid = true;
/*
#ifdef AW_DEBUG
    for (i = 0, face = frontarea->tmpfaces; face; face = face->next[side])
    {
        side = face->frontarea != frontarea->areanum;
        i++;
    } //end for
    Log_Print("created front area %d with %d faces\n", frontarea->areanum, i);

    for (i = 0, face = backarea->tmpfaces; face; face = face->next[side])
    {
        side = face->frontarea != backarea->areanum;
        i++;
    } //end for
    Log_Print("created back area %d with %d faces\n", backarea->areanum, i);
#endif //AW_DEBUG*/

    AAS_FlipAreaFaces((*frontarea));
    AAS_FlipAreaFaces((*backarea));
    //
    AAS_CheckArea((*frontarea));
    AAS_CheckArea((*backarea));
} //end of the function AAS_SplitArea
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
int AAS_FindBestAreaSplitPlane(tmp_area_t *tmparea, vec3_t normal, float *dist)
{
    int side1, side2;
    int foundsplitter, facesplits, groundsplits, epsilonfaces, bestepsilonfaces;
    float bestvalue, value;
    tmp_face_t *face1, *face2;
    vec3_t tmpnormal, invgravity;
    float tmpdist;

    //get inverse of gravity direction
    VectorCopy(cfg.phys_gravitydirection, invgravity);
    VectorInverse(invgravity);

    foundsplitter = false;
    bestvalue = -999999;
    bestepsilonfaces = 0;
    //
#ifdef AW_DEBUG
    Log_Print("finding split plane for area %d\n", tmparea->areanum);
#endif //AW_DEBUG
    for (face1 = tmparea->tmpfaces; face1; face1 = face1->next[side1])
    {
        //side of the face the area is on
        side1 = face1->frontarea != tmparea;
        //
        if (WindingIsTiny(face1->winding))
        {
            Log_Write("gsubdiv: area %d has a tiny winding\r\n", tmparea->areanum);
            continue;
        } //end if
        //if the face isn't a gap or ground there's no split edge
        if (!(face1->faceflags & FACE_GROUND) && !AAS_GapFace(face1, side1)) continue;
        //
        for (face2 = face1->next[side1]; face2; face2 = face2->next[side2])
        {
            //side of the face the area is on
            side2 = face2->frontarea != tmparea;
            //
            if (WindingIsTiny(face1->winding))
            {
                Log_Write("gsubdiv: area %d has a tiny winding\r\n", tmparea->areanum);
                continue;
            } //end if
            //if the face isn't a gap or ground there's no split edge
            if (!(face2->faceflags & FACE_GROUND) && !AAS_GapFace(face2, side2)) continue;
            //only split between gaps and ground
            if (!(((face1->faceflags & FACE_GROUND) && AAS_GapFace(face2, side2)) ||
                    ((face2->faceflags & FACE_GROUND) && AAS_GapFace(face1, side1)))) continue;
            //find a plane seperating the windings of the faces
            if (!FindPlaneSeperatingWindings(face1->winding, face2->winding, invgravity,
                                                        tmpnormal, &tmpdist)) continue;
#ifdef AW_DEBUG
            Log_Print("normal = \'%f %f %f\', dist = %f\n",
                            tmpnormal[0], tmpnormal[1], tmpnormal[2], tmpdist);
#endif //AW_DEBUG
            //get metrics for this vertical plane
            if (!AAS_TestSplitPlane(tmparea, tmpnormal, tmpdist,
                                        &facesplits, &groundsplits, &epsilonfaces))
            {
                continue;
            } //end if
#ifdef AW_DEBUG
            Log_Print("face splits = %d\nground splits = %d\n",
                            facesplits, groundsplits);
#endif //AW_DEBUG
            value = 100 - facesplits - 2 * groundsplits;
            //avoid epsilon faces
            value += epsilonfaces * -1000;
            if (value > bestvalue)
            {
                VectorCopy(tmpnormal, normal);
                *dist = tmpdist;
                bestvalue = value;
                bestepsilonfaces = epsilonfaces;
                foundsplitter = true;
            } //end if
        } //end for
    } //end for
    if (bestepsilonfaces)
    {
        Log_Write("found %d epsilon faces trying to split area %d\r\n",
                                    epsilonfaces, tmparea->areanum);
    } //end else
    return foundsplitter;
} //end of the function AAS_FindBestAreaSplitPlane
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_node_t *AAS_SubdivideArea_r(tmp_node_t *tmpnode)
{
    int planenum;
    tmp_area_t *frontarea, *backarea;
    tmp_node_t *tmpnode1, *tmpnode2;
    vec3_t normal;
    float dist;

    if (AAS_FindBestAreaSplitPlane(tmpnode->tmparea, normal, &dist))
    {
        qprintf("\r%6d", ++numgravitationalsubdivisions);
        //
        planenum = FindFloatPlane(normal, dist);
        //split the area
        AAS_SplitArea(tmpnode->tmparea, planenum, &frontarea, &backarea);
        //
        tmpnode->tmparea = NULL;
        tmpnode->planenum = FindFloatPlane(normal, dist);
        //
        tmpnode1 = AAS_AllocTmpNode();
        tmpnode1->planenum = 0;
        tmpnode1->tmparea = frontarea;
        //
        tmpnode2 = AAS_AllocTmpNode();
        tmpnode2->planenum = 0;
        tmpnode2->tmparea = backarea;
        //subdivide the areas created by splitting recursively
        tmpnode->children[0] = AAS_SubdivideArea_r(tmpnode1);
        tmpnode->children[1] = AAS_SubdivideArea_r(tmpnode2);
    } //end if
    return tmpnode;
} //end of the function AAS_SubdivideArea_r
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_node_t *AAS_GravitationalSubdivision_r(tmp_node_t *tmpnode)
{
    //if this is a solid leaf
    if (!tmpnode) return NULL;
    //negative so it's an area
    if (tmpnode->tmparea) return AAS_SubdivideArea_r(tmpnode);
    //do the children recursively
    tmpnode->children[0] = AAS_GravitationalSubdivision_r(tmpnode->children[0]);
    tmpnode->children[1] = AAS_GravitationalSubdivision_r(tmpnode->children[1]);
    return tmpnode;
} //end of the function AAS_GravitationalSubdivision_r
//===========================================================================
// NOTE: merge faces and melt edges first
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_GravitationalSubdivision(void)
{
    Log_Write("AAS_GravitationalSubdivision\r\n");
    numgravitationalsubdivisions = 0;
    qprintf("%6i gravitational subdivisions", numgravitationalsubdivisions);
    //start with the head node
    AAS_GravitationalSubdivision_r(tmpaasworld.nodes);
    qprintf("\n");
    Log_Write("%6i gravitational subdivisions\r\n", numgravitationalsubdivisions);
} //end of the function AAS_GravitationalSubdivision
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_node_t *AAS_RefreshLadderSubdividedTree_r(tmp_node_t *tmpnode, tmp_area_t *tmparea,
                                                  tmp_node_t *tmpnode1, tmp_node_t *tmpnode2, int planenum)
{
    //if this is a solid leaf
    if (!tmpnode) return NULL;
    //negative so it's an area
    if (tmpnode->tmparea)
    {
        if (tmpnode->tmparea == tmparea)
        {
            tmpnode->tmparea = NULL;
            tmpnode->planenum = planenum;
            tmpnode->children[0] = tmpnode1;
            tmpnode->children[1] = tmpnode2;
        } //end if
        return tmpnode;
    } //end if
    //do the children recursively
    tmpnode->children[0] = AAS_RefreshLadderSubdividedTree_r(tmpnode->children[0],
                                    tmparea, tmpnode1, tmpnode2, planenum);
    tmpnode->children[1] = AAS_RefreshLadderSubdividedTree_r(tmpnode->children[1],
                                    tmparea, tmpnode1, tmpnode2, planenum);
    return tmpnode;
} //end of the function AAS_RefreshLadderSubdividedTree_r
//===========================================================================
// find an area with ladder faces and ground faces that are not connected
// split the area with a horizontal plane at the lowest vertex of all
// ladder faces in the area
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_node_t *AAS_LadderSubdivideArea_r(tmp_node_t *tmpnode)
{
    int side1, i, planenum;
    int foundladderface, foundgroundface;
    float dist;
    tmp_area_t *tmparea, *frontarea, *backarea;
    tmp_face_t *face1;
    tmp_node_t *tmpnode1, *tmpnode2;
    vec3_t lowestpoint, normal = {0, 0, 1};
    plane_t *plane;
    winding_t *w;

    tmparea = tmpnode->tmparea;
    //skip areas with a liquid
    if (tmparea->contents & (AREACONTENTS_WATER
                                    | AREACONTENTS_LAVA
                                    | AREACONTENTS_SLIME)) return tmpnode;
    //must be possible to stand in the area
    if (!(tmparea->presencetype & PRESENCE_NORMAL)) return tmpnode;
    //
    foundladderface = false;
    foundgroundface = false;
    lowestpoint[2] = 99999;
    //
    for (face1 = tmparea->tmpfaces; face1; face1 = face1->next[side1])
    {
        //side of the face the area is on
        side1 = face1->frontarea != tmparea;
        //if the face is a ladder face
        if (face1->faceflags & FACE_LADDER)
        {
            plane = &mapplanes[face1->planenum];
            //the ladder face plane should be pretty much vertical
            if (DotProduct(plane->normal, normal) > -0.1)
            {
                foundladderface = true;
                //find lowest point
                for (i = 0; i < face1->winding->numpoints; i++)
                {
                    if (face1->winding->p[i][2] < lowestpoint[2])
                    {
                        VectorCopy(face1->winding->p[i], lowestpoint);
                    } //end if
                } //end for
            } //end if
        } //end if
        else if (face1->faceflags & FACE_GROUND)
        {
            foundgroundface = true;
        } //end else if
    } //end for
    //
    if ((!foundladderface) || (!foundgroundface)) return tmpnode;
    //
    for (face1 = tmparea->tmpfaces; face1; face1 = face1->next[side1])
    {
        //side of the face the area is on
        side1 = face1->frontarea != tmparea;
        //if the face isn't a ground face
        if (!(face1->faceflags & FACE_GROUND)) continue;
        //the ground plane
        plane = &mapplanes[face1->planenum];
        //get the difference between the ground plane and the lowest point
        dist = DotProduct(plane->normal, lowestpoint) - plane->dist;
        //if the lowest point is very near one of the ground planes
        if (dist > -1 && dist < 1)
        {
            return tmpnode;
        } //end if
    } //end for
    //
    dist = DotProduct(normal, lowestpoint);
    planenum = FindFloatPlane(normal, dist);
    //
    w = AAS_SplitWinding(tmparea, planenum);
    if (!w) return tmpnode;
    FreeWinding(w);
    //split the area with a horizontal plane through the lowest point
    qprintf("\r%6d", ++numladdersubdivisions);
    //
    AAS_SplitArea(tmparea, planenum, &frontarea, &backarea);
    //
    tmpnode->tmparea = NULL;
    tmpnode->planenum = planenum;
    //
    tmpnode1 = AAS_AllocTmpNode();
    tmpnode1->planenum = 0;
    tmpnode1->tmparea = frontarea;
    //
    tmpnode2 = AAS_AllocTmpNode();
    tmpnode2->planenum = 0;
    tmpnode2->tmparea = backarea;
    //subdivide the areas created by splitting recursively
    tmpnode->children[0] = AAS_LadderSubdivideArea_r(tmpnode1);
    tmpnode->children[1] = AAS_LadderSubdivideArea_r(tmpnode2);
    //refresh the tree
    AAS_RefreshLadderSubdividedTree_r(tmpaasworld.nodes, tmparea, tmpnode1, tmpnode2, planenum);
    //
    return tmpnode;
} //end of the function AAS_LadderSubdivideArea_r
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
tmp_node_t *AAS_LadderSubdivision_r(tmp_node_t *tmpnode)
{
    //if this is a solid leaf
    if (!tmpnode) return 0;
    //negative so it's an area
    if (tmpnode->tmparea) return AAS_LadderSubdivideArea_r(tmpnode);
    //do the children recursively
    tmpnode->children[0] = AAS_LadderSubdivision_r(tmpnode->children[0]);
    tmpnode->children[1] = AAS_LadderSubdivision_r(tmpnode->children[1]);
    return tmpnode;
} //end of the function AAS_LadderSubdivision_r
//===========================================================================
//
// Parameter:               -
// Returns:                 -
// Changes Globals:     -
//===========================================================================
void AAS_LadderSubdivision(void)
{
    Log_Write("AAS_LadderSubdivision\r\n");
    numladdersubdivisions = 0;
    qprintf("%6i ladder subdivisions", numladdersubdivisions);
    //start with the head node
    AAS_LadderSubdivision_r(tmpaasworld.nodes);
    //
    qprintf("\n");
    Log_Write("%6i ladder subdivisions\r\n", numladdersubdivisions);
} //end of the function AAS_LadderSubdivision

---