ref: b8c0e4deccffcd668f7d08ffc1fe16147e9e894a
dir: /code/bspc/aas_gsubdiv.c/
/*
===========================================================================
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