aas_areamerging.c (12414B)
1 /* 2 =========================================================================== 3 Copyright (C) 1999-2005 Id Software, Inc. 4 5 This file is part of Quake III Arena source code. 6 7 Quake III Arena source code is free software; you can redistribute it 8 and/or modify it under the terms of the GNU General Public License as 9 published by the Free Software Foundation; either version 2 of the License, 10 or (at your option) any later version. 11 12 Quake III Arena source code is distributed in the hope that it will be 13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with Foobar; if not, write to the Free Software 19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 20 =========================================================================== 21 */ 22 23 #include "qbsp.h" 24 #include "../botlib/aasfile.h" 25 #include "aas_create.h" 26 #include "aas_store.h" 27 28 #define CONVEX_EPSILON 0.3 29 30 //=========================================================================== 31 // 32 // Parameter: - 33 // Returns: - 34 // Changes Globals: - 35 //=========================================================================== 36 tmp_node_t *AAS_RefreshMergedTree_r(tmp_node_t *tmpnode) 37 { 38 tmp_area_t *tmparea; 39 40 //if this is a solid leaf 41 if (!tmpnode) return NULL; 42 //if this is an area leaf 43 if (tmpnode->tmparea) 44 { 45 tmparea = tmpnode->tmparea; 46 while(tmparea->mergedarea) tmparea = tmparea->mergedarea; 47 tmpnode->tmparea = tmparea; 48 return tmpnode; 49 } //end if 50 //do the children recursively 51 tmpnode->children[0] = AAS_RefreshMergedTree_r(tmpnode->children[0]); 52 tmpnode->children[1] = AAS_RefreshMergedTree_r(tmpnode->children[1]); 53 return tmpnode; 54 } //end of the function AAS_RefreshMergedTree_r 55 //=========================================================================== 56 // returns true if the two given faces would create a non-convex area at 57 // the given sides, otherwise false is returned 58 // 59 // Parameter: - 60 // Returns: - 61 // Changes Globals: - 62 //=========================================================================== 63 int NonConvex(tmp_face_t *face1, tmp_face_t *face2, int side1, int side2) 64 { 65 int i; 66 winding_t *w1, *w2; 67 plane_t *plane1, *plane2; 68 69 w1 = face1->winding; 70 w2 = face2->winding; 71 72 plane1 = &mapplanes[face1->planenum ^ side1]; 73 plane2 = &mapplanes[face2->planenum ^ side2]; 74 75 //check if one of the points of face1 is at the back of the plane of face2 76 for (i = 0; i < w1->numpoints; i++) 77 { 78 if (DotProduct(plane2->normal, w1->p[i]) - plane2->dist < -CONVEX_EPSILON) return true; 79 } //end for 80 //check if one of the points of face2 is at the back of the plane of face1 81 for (i = 0; i < w2->numpoints; i++) 82 { 83 if (DotProduct(plane1->normal, w2->p[i]) - plane1->dist < -CONVEX_EPSILON) return true; 84 } //end for 85 86 return false; 87 } //end of the function NonConvex 88 //=========================================================================== 89 // try to merge the areas at both sides of the given face 90 // 91 // Parameter: seperatingface : face that seperates two areas 92 // Returns: - 93 // Changes Globals: - 94 //=========================================================================== 95 int AAS_TryMergeFaceAreas(tmp_face_t *seperatingface) 96 { 97 int side1, side2, area1faceflags, area2faceflags; 98 tmp_area_t *tmparea1, *tmparea2, *newarea; 99 tmp_face_t *face1, *face2, *nextface1, *nextface2; 100 101 tmparea1 = seperatingface->frontarea; 102 tmparea2 = seperatingface->backarea; 103 104 //areas must have the same presence type 105 if (tmparea1->presencetype != tmparea2->presencetype) return false; 106 //areas must have the same area contents 107 if (tmparea1->contents != tmparea2->contents) return false; 108 //areas must have the same bsp model inside (or both none) 109 if (tmparea1->modelnum != tmparea2->modelnum) return false; 110 111 area1faceflags = 0; 112 area2faceflags = 0; 113 for (face1 = tmparea1->tmpfaces; face1; face1 = face1->next[side1]) 114 { 115 side1 = (face1->frontarea != tmparea1); 116 //debug: check if the area belongs to the area 117 if (face1->frontarea != tmparea1 && 118 face1->backarea != tmparea1) Error("face does not belong to area1"); 119 //just continue if the face is seperating the two areas 120 //NOTE: a result of this is that ground and gap areas can 121 // be merged if the seperating face is the gap 122 if ((face1->frontarea == tmparea1 && 123 face1->backarea == tmparea2) || 124 (face1->frontarea == tmparea2 && 125 face1->backarea == tmparea1)) continue; 126 //get area1 face flags 127 area1faceflags |= face1->faceflags; 128 if (AAS_GapFace(face1, side1)) area1faceflags |= FACE_GAP; 129 // 130 for (face2 = tmparea2->tmpfaces; face2; face2 = face2->next[side2]) 131 { 132 side2 = (face2->frontarea != tmparea2); 133 //debug: check if the area belongs to the area 134 if (face2->frontarea != tmparea2 && 135 face2->backarea != tmparea2) Error("face does not belong to area2"); 136 //just continue if the face is seperating the two areas 137 //NOTE: a result of this is that ground and gap areas can 138 // be merged if the seperating face is the gap 139 if ((face2->frontarea == tmparea1 && 140 face2->backarea == tmparea2) || 141 (face2->frontarea == tmparea2 && 142 face2->backarea == tmparea1)) continue; 143 //get area2 face flags 144 area2faceflags |= face2->faceflags; 145 if (AAS_GapFace(face2, side2)) area2faceflags |= FACE_GAP; 146 //if the two faces would create a non-convex area 147 if (NonConvex(face1, face2, side1, side2)) return false; 148 } //end for 149 } //end for 150 //if one area has gap faces (that aren't seperating the two areas) 151 //and the other has ground faces (that aren't seperating the two areas), 152 //the areas can't be merged 153 if (((area1faceflags & FACE_GROUND) && (area2faceflags & FACE_GAP)) || 154 ((area2faceflags & FACE_GROUND) && (area1faceflags & FACE_GAP))) 155 { 156 // Log_Print(" can't merge: ground/gap\n"); 157 return false; 158 } //end if 159 160 // Log_Print("merged area %d & %d to %d with %d faces\n", tmparea1->areanum, tmparea2->areanum, newarea->areanum, numfaces); 161 // return false; 162 // 163 //AAS_CheckArea(tmparea1); 164 //AAS_CheckArea(tmparea2); 165 //create the new area 166 newarea = AAS_AllocTmpArea(); 167 newarea->presencetype = tmparea1->presencetype; 168 newarea->contents = tmparea1->contents; 169 newarea->modelnum = tmparea1->modelnum; 170 newarea->tmpfaces = NULL; 171 172 //add all the faces (except the seperating ones) from the first area 173 //to the new area 174 for (face1 = tmparea1->tmpfaces; face1; face1 = nextface1) 175 { 176 side1 = (face1->frontarea != tmparea1); 177 nextface1 = face1->next[side1]; 178 //don't add seperating faces 179 if ((face1->frontarea == tmparea1 && 180 face1->backarea == tmparea2) || 181 (face1->frontarea == tmparea2 && 182 face1->backarea == tmparea1)) 183 { 184 continue; 185 } //end if 186 // 187 AAS_RemoveFaceFromArea(face1, tmparea1); 188 AAS_AddFaceSideToArea(face1, side1, newarea); 189 } //end for 190 //add all the faces (except the seperating ones) from the second area 191 //to the new area 192 for (face2 = tmparea2->tmpfaces; face2; face2 = nextface2) 193 { 194 side2 = (face2->frontarea != tmparea2); 195 nextface2 = face2->next[side2]; 196 //don't add seperating faces 197 if ((face2->frontarea == tmparea1 && 198 face2->backarea == tmparea2) || 199 (face2->frontarea == tmparea2 && 200 face2->backarea == tmparea1)) 201 { 202 continue; 203 } //end if 204 // 205 AAS_RemoveFaceFromArea(face2, tmparea2); 206 AAS_AddFaceSideToArea(face2, side2, newarea); 207 } //end for 208 //free all shared faces 209 for (face1 = tmparea1->tmpfaces; face1; face1 = nextface1) 210 { 211 side1 = (face1->frontarea != tmparea1); 212 nextface1 = face1->next[side1]; 213 // 214 AAS_RemoveFaceFromArea(face1, face1->frontarea); 215 AAS_RemoveFaceFromArea(face1, face1->backarea); 216 AAS_FreeTmpFace(face1); 217 } //end for 218 // 219 tmparea1->mergedarea = newarea; 220 tmparea1->invalid = true; 221 tmparea2->mergedarea = newarea; 222 tmparea2->invalid = true; 223 // 224 AAS_CheckArea(newarea); 225 AAS_FlipAreaFaces(newarea); 226 // Log_Print("merged area %d & %d to %d with %d faces\n", tmparea1->areanum, tmparea2->areanum, newarea->areanum); 227 return true; 228 } //end of the function AAS_TryMergeFaceAreas 229 //=========================================================================== 230 // try to merge areas 231 // merged areas are added to the end of the convex area list so merging 232 // will be tried for those areas as well 233 // 234 // Parameter: - 235 // Returns: - 236 // Changes Globals: tmpaasworld 237 //=========================================================================== 238 /* 239 void AAS_MergeAreas(void) 240 { 241 int side, nummerges; 242 tmp_area_t *tmparea, *othertmparea; 243 tmp_face_t *face; 244 245 nummerges = 0; 246 Log_Write("AAS_MergeAreas\r\n"); 247 qprintf("%6d areas merged", 1); 248 //first merge grounded areas only 249 //NOTE: this is useless because the area settings aren't available yet 250 for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next) 251 { 252 // Log_Print("checking area %d\n", i); 253 //if the area is invalid 254 if (tmparea->invalid) 255 { 256 // Log_Print(" area invalid\n"); 257 continue; 258 } //end if 259 // 260 // if (!(tmparea->settings->areaflags & AREA_GROUNDED)) continue; 261 // 262 for (face = tmparea->tmpfaces; face; face = face->next[side]) 263 { 264 side = (face->frontarea != tmparea); 265 //if the face has both a front and back area 266 if (face->frontarea && face->backarea) 267 { 268 // 269 if (face->frontarea == tmparea) othertmparea = face->backarea; 270 else othertmparea = face->frontarea; 271 // if (!(othertmparea->settings->areaflags & AREA_GROUNDED)) continue; 272 // Log_Print(" checking area %d with %d\n", face->frontarea, face->backarea); 273 if (AAS_TryMergeFaceAreas(face)) 274 { 275 qprintf("\r%6d", ++nummerges); 276 break; 277 } //end if 278 } //end if 279 } //end for 280 } //end for 281 //merge all areas 282 for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next) 283 { 284 // Log_Print("checking area %d\n", i); 285 //if the area is invalid 286 if (tmparea->invalid) 287 { 288 // Log_Print(" area invalid\n"); 289 continue; 290 } //end if 291 // 292 for (face = tmparea->tmpfaces; face; face = face->next[side]) 293 { 294 side = (face->frontarea != tmparea); 295 //if the face has both a front and back area 296 if (face->frontarea && face->backarea) 297 { 298 // Log_Print(" checking area %d with %d\n", face->frontarea, face->backarea); 299 if (AAS_TryMergeFaceAreas(face)) 300 { 301 qprintf("\r%6d", ++nummerges); 302 break; 303 } //end if 304 } //end if 305 } //end for 306 } //end for 307 Log_Print("\r%6d areas merged\n", nummerges); 308 //refresh the merged tree 309 AAS_RefreshMergedTree_r(tmpaasworld.nodes); 310 } //end of the function AAS_MergeAreas*/ 311 312 int AAS_GroundArea(tmp_area_t *tmparea) 313 { 314 tmp_face_t *face; 315 int side; 316 317 for (face = tmparea->tmpfaces; face; face = face->next[side]) 318 { 319 side = (face->frontarea != tmparea); 320 if (face->faceflags & FACE_GROUND) return true; 321 } //end for 322 return false; 323 } //end of the function AAS_GroundArea 324 325 void AAS_MergeAreas(void) 326 { 327 int side, nummerges, merges, groundfirst; 328 tmp_area_t *tmparea, *othertmparea; 329 tmp_face_t *face; 330 331 nummerges = 0; 332 Log_Write("AAS_MergeAreas\r\n"); 333 qprintf("%6d areas merged", 1); 334 // 335 groundfirst = true; 336 //for (i = 0; i < 4 || merges; i++) 337 while(1) 338 { 339 //if (i < 2) groundfirst = true; 340 //else groundfirst = false; 341 // 342 merges = 0; 343 //first merge grounded areas only 344 for (tmparea = tmpaasworld.areas; tmparea; tmparea = tmparea->l_next) 345 { 346 //if the area is invalid 347 if (tmparea->invalid) 348 { 349 continue; 350 } //end if 351 // 352 if (groundfirst) 353 { 354 if (!AAS_GroundArea(tmparea)) continue; 355 } //end if 356 // 357 for (face = tmparea->tmpfaces; face; face = face->next[side]) 358 { 359 side = (face->frontarea != tmparea); 360 //if the face has both a front and back area 361 if (face->frontarea && face->backarea) 362 { 363 // 364 if (face->frontarea == tmparea) othertmparea = face->backarea; 365 else othertmparea = face->frontarea; 366 // 367 if (groundfirst) 368 { 369 if (!AAS_GroundArea(othertmparea)) continue; 370 } //end if 371 if (AAS_TryMergeFaceAreas(face)) 372 { 373 qprintf("\r%6d", ++nummerges); 374 merges++; 375 break; 376 } //end if 377 } //end if 378 } //end for 379 } //end for 380 if (!merges) 381 { 382 if (groundfirst) groundfirst = false; 383 else break; 384 } //end if 385 } //end for 386 qprintf("\n"); 387 Log_Write("%6d areas merged\r\n", nummerges); 388 //refresh the merged tree 389 AAS_RefreshMergedTree_r(tmpaasworld.nodes); 390 } //end of the function AAS_MergeAreas