From 6bf20c78f5b69d40bcc4931df93d29198435ab67 Mon Sep 17 00:00:00 2001 From: zakk Date: Fri, 26 Aug 2005 17:39:27 +0000 Subject: newlines fixed git-svn-id: svn://svn.icculus.org/quake3/trunk@6 edf5b092-35ff-0310-97b2-ce42778d08ea --- code/bspc/aas_gsubdiv.c | 1312 +++++++++++++++++++++++------------------------ 1 file changed, 656 insertions(+), 656 deletions(-) (limited to 'code/bspc/aas_gsubdiv.c') diff --git a/code/bspc/aas_gsubdiv.c b/code/bspc/aas_gsubdiv.c index d9ba597..4cfb194 100755 --- a/code/bspc/aas_gsubdiv.c +++ b/code/bspc/aas_gsubdiv.c @@ -1,656 +1,656 @@ -/* -=========================================================================== -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 +/* +=========================================================================== +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 -- cgit v1.2.3