ref: bea7b7bf8ccbc2bc41906517079e76fcfb31cb5a
dir: /code/bspc/aas_areamerging.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" #define CONVEX_EPSILON 0.3 //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== tmp_node_t *AAS_RefreshMergedTree_r(tmp_node_t *tmpnode) { tmp_area_t *tmparea; //if this is a solid leaf if (!tmpnode) return NULL; //if this is an area leaf if (tmpnode->tmparea) { tmparea = tmpnode->tmparea; while(tmparea->mergedarea) tmparea = tmparea->mergedarea; tmpnode->tmparea = tmparea; return tmpnode; } //end if //do the children recursively tmpnode->children[0] = AAS_RefreshMergedTree_r(tmpnode->children[0]); tmpnode->children[1] = AAS_RefreshMergedTree_r(tmpnode->children[1]); return tmpnode; } //end of the function AAS_RefreshMergedTree_r //=========================================================================== // returns true if the two given faces would create a non-convex area at // the given sides, otherwise false is returned // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== int NonConvex(tmp_face_t *face1, tmp_face_t *face2, int side1, int side2) { int i; winding_t *w1, *w2; plane_t *plane1, *plane2; w1 = face1->winding; w2 = face2->winding; plane1 = &mapplanes[face1->planenum ^ side1]; plane2 = &mapplanes[face2->planenum ^ side2]; //check if one of the points of face1 is at the back of the plane of face2 for (i = 0; i < w1->numpoints; i++) { if (DotProduct(plane2->normal, w1->p[i]) - plane2->dist < -CONVEX_EPSILON) return true; } //end for //check if one of the points of face2 is at the back of the plane of face1 for (i = 0; i < w2->numpoints; i++) { if (DotProduct(plane1->normal, w2->p[i]) - plane1->dist < -CONVEX_EPSILON) return true; } //end for return false; } //end of the function NonConvex //=========================================================================== // try to merge the areas at both sides of the given face // // Parameter: seperatingface : face that seperates two areas // Returns: - // Changes Globals: - //=========================================================================== int AAS_TryMergeFaceAreas(tmp_face_t *seperatingface) { int side1, side2, area1faceflags, area2faceflags; tmp_area_t *tmparea1, *tmparea2, *newarea; tmp_face_t *face1, *face2, *nextface1, *nextface2; tmparea1 = seperatingface->frontarea; tmparea2 = seperatingface->backarea; //areas must have the same presence type if (tmparea1->presencetype != tmparea2->presencetype) return false; //areas must have the same area contents if (tmparea1->contents != tmparea2->contents) return false; //areas must have the same bsp model inside (or both none) if (tmparea1->modelnum != tmparea2->modelnum) return false; area1faceflags = 0; area2faceflags = 0; for (face1 = tmparea1->tmpfaces; face1; face1 = face1->next[side1]) { side1 = (face1->frontarea != tmparea1); //debug: check if the area belongs to the area if (face1->frontarea != tmparea1 && face1->backarea != tmparea1) Error("face does not belong to area1"); //just continue if the face is seperating the two areas //NOTE: a result of this is that ground and gap areas can // be merged if the seperating face is the gap if ((face1->frontarea == tmparea1 && face1->backarea == tmparea2) || (face1->frontarea == tmparea2 && face1->backarea == tmparea1)) continue; //get area1 face flags area1faceflags |= face1->faceflags; if (AAS_GapFace(face1, side1)) area1faceflags |= FACE_GAP; // for (face2 = tmparea2->tmpfaces; face2; face2 = face2->next[side2]) { side2 = (face2->frontarea != tmparea2); //debug: check if the area belongs to the area if (face2->frontarea != tmparea2 && face2->backarea != tmparea2) Error("face does not belong to area2"); //just continue if the face is seperating the two areas //NOTE: a result of this is that ground and gap areas can // be merged if the seperating face is the gap if ((face2->frontarea == tmparea1 && face2->backarea == tmparea2) || (face2->frontarea == tmparea2 && face2->backarea == tmparea1)) continue; //get area2 face flags area2faceflags |= face2->faceflags; if (AAS_GapFace(face2, side2)) area2faceflags |= FACE_GAP; //if the two faces would create a non-convex area if (NonConvex(face1, face2, side1, side2)) return false; } //end for } //end for //if one area has gap faces (that aren't seperating the two areas) //and the other has ground faces (that aren't seperating the two areas), //the areas can't be merged if (((area1faceflags & FACE_GROUND) && (area2faceflags & FACE_GAP)) || ((area2faceflags & FACE_GROUND) && (area1faceflags & FACE_GAP))) { // Log_Print(" can't merge: ground/gap\n"); return false; } //end if // Log_Print("merged area %d & %d to %d with %d faces\n", tmparea1->areanum, tmparea2->areanum, newarea->areanum, numfaces); // return false; // //AAS_CheckArea(tmparea1); //AAS_CheckArea(tmparea2); //create the new area newarea = AAS_AllocTmpArea(); newarea->presencetype = tmparea1->presencetype; newarea->contents = tmparea1->contents; newarea->modelnum = tmparea1->modelnum; newarea->tmpfaces = NULL; //add all the faces (except the seperating ones) from the first area //to the new area for (face1 = tmparea1->tmpfaces; face1; face1 = nextface1) { side1 = (face1->frontarea != tmparea1); nextface1 = face1->next[side1]; //don't add seperating faces if ((face1->frontarea == tmparea1 && face1->backarea == tmparea2) || (face1->frontarea == tmparea2 && face1->backarea == tmparea1)) { continue; } //end if // AAS_RemoveFaceFromArea(face1, tmparea1); AAS_AddFaceSideToArea(face1, side1, newarea); } //end for //add all the faces (except the seperating ones) from the second area //to the new area for (face2 = tmparea2->tmpfaces; face2; face2 = nextface2) { side2 = (face2->frontarea != tmparea2); nextface2 = face2->next[side2]; //don't add seperating faces if ((face2->frontarea == tmparea1 && face2->backarea == tmparea2) || (face2->frontarea == tmparea2 && face2->backarea == tmparea1)) { continue; } //end if // AAS_RemoveFaceFromArea(face2, tmparea2); AAS_AddFaceSideToArea(face2, side2, newarea); } //end for //free all shared faces for (face1 = tmparea1->tmpfaces; face1; face1 = nextface1) { side1 = (face1->frontarea != tmparea1); nextface1 = face1->next[side1]; // AAS_RemoveFaceFromArea(face1, face1->frontarea); AAS_RemoveFaceFromArea(face1, face1->backarea); AAS_FreeTmpFace(face1); } //end for // tmparea1->mergedarea = newarea; tmparea1->invalid = true; tmparea2->mergedarea = newarea; tmparea2->invalid = true; // AAS_CheckArea(newarea); AAS_FlipAreaFaces(newarea); // Log_Print("merged area %d & %d to %d with %d faces\n", tmparea1->areanum, tmparea2->areanum, newarea->areanum); return true; } //end of the function AAS_TryMergeFaceAreas //=========================================================================== // try to merge areas // merged areas are added to the end of the convex area list so merging // will be tried for those areas as well // // Parameter: - // Returns: - // Changes Globals: tmpaasworld //=========================================================================== /* void AAS_MergeAreas(void) { int side, nummerges; tmp_area_t *tmparea, *othertmparea; tmp_face_t *face; nummerges = 0; Log_Write("AAS_MergeAreas\r\n"); qprintf("%6d areas merged", 1); //first merge grounded areas only //NOTE: this is useless because the area settings aren't available yet for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next) { // Log_Print("checking area %d\n", i); //if the area is invalid if (tmparea->invalid) { // Log_Print(" area invalid\n"); continue; } //end if // // if (!(tmparea->settings->areaflags & AREA_GROUNDED)) continue; // for (face = tmparea->tmpfaces; face; face = face->next[side]) { side = (face->frontarea != tmparea); //if the face has both a front and back area if (face->frontarea && face->backarea) { // if (face->frontarea == tmparea) othertmparea = face->backarea; else othertmparea = face->frontarea; // if (!(othertmparea->settings->areaflags & AREA_GROUNDED)) continue; // Log_Print(" checking area %d with %d\n", face->frontarea, face->backarea); if (AAS_TryMergeFaceAreas(face)) { qprintf("\r%6d", ++nummerges); break; } //end if } //end if } //end for } //end for //merge all areas for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next) { // Log_Print("checking area %d\n", i); //if the area is invalid if (tmparea->invalid) { // Log_Print(" area invalid\n"); continue; } //end if // for (face = tmparea->tmpfaces; face; face = face->next[side]) { side = (face->frontarea != tmparea); //if the face has both a front and back area if (face->frontarea && face->backarea) { // Log_Print(" checking area %d with %d\n", face->frontarea, face->backarea); if (AAS_TryMergeFaceAreas(face)) { qprintf("\r%6d", ++nummerges); break; } //end if } //end if } //end for } //end for Log_Print("\r%6d areas merged\n", nummerges); //refresh the merged tree AAS_RefreshMergedTree_r(tmpaasworld.nodes); } //end of the function AAS_MergeAreas*/ int AAS_GroundArea(tmp_area_t *tmparea) { tmp_face_t *face; int side; for (face = tmparea->tmpfaces; face; face = face->next[side]) { side = (face->frontarea != tmparea); if (face->faceflags & FACE_GROUND) return true; } //end for return false; } //end of the function AAS_GroundArea void AAS_MergeAreas(void) { int side, nummerges, merges, groundfirst; tmp_area_t *tmparea, *othertmparea; tmp_face_t *face; nummerges = 0; Log_Write("AAS_MergeAreas\r\n"); qprintf("%6d areas merged", 1); // groundfirst = true; //for (i = 0; i < 4 || merges; i++) while(1) { //if (i < 2) groundfirst = true; //else groundfirst = false; // merges = 0; //first merge grounded areas only for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next) { //if the area is invalid if (tmparea->invalid) { continue; } //end if // if (groundfirst) { if (!AAS_GroundArea(tmparea)) continue; } //end if // for (face = tmparea->tmpfaces; face; face = face->next[side]) { side = (face->frontarea != tmparea); //if the face has both a front and back area if (face->frontarea && face->backarea) { // if (face->frontarea == tmparea) othertmparea = face->backarea; else othertmparea = face->frontarea; // if (groundfirst) { if (!AAS_GroundArea(othertmparea)) continue; } //end if if (AAS_TryMergeFaceAreas(face)) { qprintf("\r%6d", ++nummerges); merges++; break; } //end if } //end if } //end for } //end for if (!merges) { if (groundfirst) groundfirst = false; else break; } //end if } //end for qprintf("\n"); Log_Write("%6d areas merged\r\n", nummerges); //refresh the merged tree AAS_RefreshMergedTree_r(tmpaasworld.nodes); } //end of the function AAS_MergeAreas