aas_store.c (33328B)
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_file.h" 26 #include "aas_store.h" 27 #include "aas_create.h" 28 #include "aas_cfg.h" 29 30 31 //#define NOTHREEVERTEXFACES 32 33 #define STOREPLANESDOUBLE 34 35 #define VERTEX_EPSILON 0.1 //NOTE: changed from 0.5 36 #define DIST_EPSILON 0.05 //NOTE: changed from 0.9 37 #define NORMAL_EPSILON 0.0001 //NOTE: changed from 0.005 38 #define INTEGRAL_EPSILON 0.01 39 40 #define VERTEX_HASHING 41 #define VERTEX_HASH_SHIFT 7 42 #define VERTEX_HASH_SIZE ((MAX_MAP_BOUNDS>>(VERTEX_HASH_SHIFT-1))+1) //was 64 43 // 44 #define PLANE_HASHING 45 #define PLANE_HASH_SIZE 1024 //must be power of 2 46 // 47 #define EDGE_HASHING 48 #define EDGE_HASH_SIZE 1024 //must be power of 2 49 50 aas_t aasworld; 51 52 //vertex hash 53 int *aas_vertexchain; // the next vertex in a hash chain 54 int aas_hashverts[VERTEX_HASH_SIZE*VERTEX_HASH_SIZE]; // a vertex number, or 0 for no verts 55 //plane hash 56 int *aas_planechain; 57 int aas_hashplanes[PLANE_HASH_SIZE]; 58 //edge hash 59 int *aas_edgechain; 60 int aas_hashedges[EDGE_HASH_SIZE]; 61 62 int allocatedaasmem = 0; 63 64 int groundfacesonly = false;//true; 65 // 66 typedef struct max_aas_s 67 { 68 int max_bboxes; 69 int max_vertexes; 70 int max_planes; 71 int max_edges; 72 int max_edgeindexsize; 73 int max_faces; 74 int max_faceindexsize; 75 int max_areas; 76 int max_areasettings; 77 int max_reachabilitysize; 78 int max_nodes; 79 int max_portals; 80 int max_portalindexsize; 81 int max_clusters; 82 } max_aas_t; 83 //maximums of everything 84 max_aas_t max_aas; 85 86 //=========================================================================== 87 // 88 // Parameter: - 89 // Returns: - 90 // Changes Globals: - 91 //=========================================================================== 92 int AAS_CountTmpNodes(tmp_node_t *tmpnode) 93 { 94 if (!tmpnode) return 0; 95 return AAS_CountTmpNodes(tmpnode->children[0]) + 96 AAS_CountTmpNodes(tmpnode->children[1]) + 1; 97 } //end of the function AAS_CountTmpNodes 98 //=========================================================================== 99 // 100 // Parameter: - 101 // Returns: - 102 // Changes Globals: - 103 //=========================================================================== 104 void AAS_InitMaxAAS(void) 105 { 106 int numfaces, numpoints, numareas; 107 tmp_face_t *f; 108 tmp_area_t *a; 109 110 numpoints = 0; 111 numfaces = 0; 112 for (f = tmpaasworld.faces; f; f = f->l_next) 113 { 114 numfaces++; 115 if (f->winding) numpoints += f->winding->numpoints; 116 } //end for 117 // 118 numareas = 0; 119 for (a = tmpaasworld.areas; a; a = a->l_next) 120 { 121 numareas++; 122 } //end for 123 max_aas.max_bboxes = AAS_MAX_BBOXES; 124 max_aas.max_vertexes = numpoints + 1; 125 max_aas.max_planes = nummapplanes; 126 max_aas.max_edges = numpoints + 1; 127 max_aas.max_edgeindexsize = (numpoints + 1) * 3; 128 max_aas.max_faces = numfaces + 10; 129 max_aas.max_faceindexsize = (numfaces + 10) * 2; 130 max_aas.max_areas = numareas + 10; 131 max_aas.max_areasettings = numareas + 10; 132 max_aas.max_reachabilitysize = 0; 133 max_aas.max_nodes = AAS_CountTmpNodes(tmpaasworld.nodes) + 10; 134 max_aas.max_portals = 0; 135 max_aas.max_portalindexsize = 0; 136 max_aas.max_clusters = 0; 137 } //end of the function AAS_InitMaxAAS 138 //=========================================================================== 139 // 140 // Parameter: - 141 // Returns: - 142 // Changes Globals: - 143 //=========================================================================== 144 void AAS_AllocMaxAAS(void) 145 { 146 int i; 147 148 AAS_InitMaxAAS(); 149 //bounding boxes 150 aasworld.numbboxes = 0; 151 aasworld.bboxes = (aas_bbox_t *) GetClearedMemory(max_aas.max_bboxes * sizeof(aas_bbox_t)); 152 allocatedaasmem += max_aas.max_bboxes * sizeof(aas_bbox_t); 153 //vertexes 154 aasworld.numvertexes = 0; 155 aasworld.vertexes = (aas_vertex_t *) GetClearedMemory(max_aas.max_vertexes * sizeof(aas_vertex_t)); 156 allocatedaasmem += max_aas.max_vertexes * sizeof(aas_vertex_t); 157 //planes 158 aasworld.numplanes = 0; 159 aasworld.planes = (aas_plane_t *) GetClearedMemory(max_aas.max_planes * sizeof(aas_plane_t)); 160 allocatedaasmem += max_aas.max_planes * sizeof(aas_plane_t); 161 //edges 162 aasworld.numedges = 0; 163 aasworld.edges = (aas_edge_t *) GetClearedMemory(max_aas.max_edges * sizeof(aas_edge_t)); 164 allocatedaasmem += max_aas.max_edges * sizeof(aas_edge_t); 165 //edge index 166 aasworld.edgeindexsize = 0; 167 aasworld.edgeindex = (aas_edgeindex_t *) GetClearedMemory(max_aas.max_edgeindexsize * sizeof(aas_edgeindex_t)); 168 allocatedaasmem += max_aas.max_edgeindexsize * sizeof(aas_edgeindex_t); 169 //faces 170 aasworld.numfaces = 0; 171 aasworld.faces = (aas_face_t *) GetClearedMemory(max_aas.max_faces * sizeof(aas_face_t)); 172 allocatedaasmem += max_aas.max_faces * sizeof(aas_face_t); 173 //face index 174 aasworld.faceindexsize = 0; 175 aasworld.faceindex = (aas_faceindex_t *) GetClearedMemory(max_aas.max_faceindexsize * sizeof(aas_faceindex_t)); 176 allocatedaasmem += max_aas.max_faceindexsize * sizeof(aas_faceindex_t); 177 //convex areas 178 aasworld.numareas = 0; 179 aasworld.areas = (aas_area_t *) GetClearedMemory(max_aas.max_areas * sizeof(aas_area_t)); 180 allocatedaasmem += max_aas.max_areas * sizeof(aas_area_t); 181 //convex area settings 182 aasworld.numareasettings = 0; 183 aasworld.areasettings = (aas_areasettings_t *) GetClearedMemory(max_aas.max_areasettings * sizeof(aas_areasettings_t)); 184 allocatedaasmem += max_aas.max_areasettings * sizeof(aas_areasettings_t); 185 //reachablity list 186 aasworld.reachabilitysize = 0; 187 aasworld.reachability = (aas_reachability_t *) GetClearedMemory(max_aas.max_reachabilitysize * sizeof(aas_reachability_t)); 188 allocatedaasmem += max_aas.max_reachabilitysize * sizeof(aas_reachability_t); 189 //nodes of the bsp tree 190 aasworld.numnodes = 0; 191 aasworld.nodes = (aas_node_t *) GetClearedMemory(max_aas.max_nodes * sizeof(aas_node_t)); 192 allocatedaasmem += max_aas.max_nodes * sizeof(aas_node_t); 193 //cluster portals 194 aasworld.numportals = 0; 195 aasworld.portals = (aas_portal_t *) GetClearedMemory(max_aas.max_portals * sizeof(aas_portal_t)); 196 allocatedaasmem += max_aas.max_portals * sizeof(aas_portal_t); 197 //cluster portal index 198 aasworld.portalindexsize = 0; 199 aasworld.portalindex = (aas_portalindex_t *) GetClearedMemory(max_aas.max_portalindexsize * sizeof(aas_portalindex_t)); 200 allocatedaasmem += max_aas.max_portalindexsize * sizeof(aas_portalindex_t); 201 //cluster 202 aasworld.numclusters = 0; 203 aasworld.clusters = (aas_cluster_t *) GetClearedMemory(max_aas.max_clusters * sizeof(aas_cluster_t)); 204 allocatedaasmem += max_aas.max_clusters * sizeof(aas_cluster_t); 205 // 206 Log_Print("allocated "); 207 PrintMemorySize(allocatedaasmem); 208 Log_Print(" of AAS memory\n"); 209 //reset the has stuff 210 aas_vertexchain = (int *) GetClearedMemory(max_aas.max_vertexes * sizeof(int)); 211 aas_planechain = (int *) GetClearedMemory(max_aas.max_planes * sizeof(int)); 212 aas_edgechain = (int *) GetClearedMemory(max_aas.max_edges * sizeof(int)); 213 // 214 for (i = 0; i < max_aas.max_vertexes; i++) aas_vertexchain[i] = -1; 215 for (i = 0; i < VERTEX_HASH_SIZE * VERTEX_HASH_SIZE; i++) aas_hashverts[i] = -1; 216 // 217 for (i = 0; i < max_aas.max_planes; i++) aas_planechain[i] = -1; 218 for (i = 0; i < PLANE_HASH_SIZE; i++) aas_hashplanes[i] = -1; 219 // 220 for (i = 0; i < max_aas.max_edges; i++) aas_edgechain[i] = -1; 221 for (i = 0; i < EDGE_HASH_SIZE; i++) aas_hashedges[i] = -1; 222 } //end of the function AAS_AllocMaxAAS 223 //=========================================================================== 224 // 225 // Parameter: - 226 // Returns: - 227 // Changes Globals: - 228 //=========================================================================== 229 void AAS_FreeMaxAAS(void) 230 { 231 //bounding boxes 232 if (aasworld.bboxes) FreeMemory(aasworld.bboxes); 233 aasworld.bboxes = NULL; 234 aasworld.numbboxes = 0; 235 //vertexes 236 if (aasworld.vertexes) FreeMemory(aasworld.vertexes); 237 aasworld.vertexes = NULL; 238 aasworld.numvertexes = 0; 239 //planes 240 if (aasworld.planes) FreeMemory(aasworld.planes); 241 aasworld.planes = NULL; 242 aasworld.numplanes = 0; 243 //edges 244 if (aasworld.edges) FreeMemory(aasworld.edges); 245 aasworld.edges = NULL; 246 aasworld.numedges = 0; 247 //edge index 248 if (aasworld.edgeindex) FreeMemory(aasworld.edgeindex); 249 aasworld.edgeindex = NULL; 250 aasworld.edgeindexsize = 0; 251 //faces 252 if (aasworld.faces) FreeMemory(aasworld.faces); 253 aasworld.faces = NULL; 254 aasworld.numfaces = 0; 255 //face index 256 if (aasworld.faceindex) FreeMemory(aasworld.faceindex); 257 aasworld.faceindex = NULL; 258 aasworld.faceindexsize = 0; 259 //convex areas 260 if (aasworld.areas) FreeMemory(aasworld.areas); 261 aasworld.areas = NULL; 262 aasworld.numareas = 0; 263 //convex area settings 264 if (aasworld.areasettings) FreeMemory(aasworld.areasettings); 265 aasworld.areasettings = NULL; 266 aasworld.numareasettings = 0; 267 //reachablity list 268 if (aasworld.reachability) FreeMemory(aasworld.reachability); 269 aasworld.reachability = NULL; 270 aasworld.reachabilitysize = 0; 271 //nodes of the bsp tree 272 if (aasworld.nodes) FreeMemory(aasworld.nodes); 273 aasworld.nodes = NULL; 274 aasworld.numnodes = 0; 275 //cluster portals 276 if (aasworld.portals) FreeMemory(aasworld.portals); 277 aasworld.portals = NULL; 278 aasworld.numportals = 0; 279 //cluster portal index 280 if (aasworld.portalindex) FreeMemory(aasworld.portalindex); 281 aasworld.portalindex = NULL; 282 aasworld.portalindexsize = 0; 283 //clusters 284 if (aasworld.clusters) FreeMemory(aasworld.clusters); 285 aasworld.clusters = NULL; 286 aasworld.numclusters = 0; 287 288 Log_Print("freed "); 289 PrintMemorySize(allocatedaasmem); 290 Log_Print(" of AAS memory\n"); 291 allocatedaasmem = 0; 292 // 293 if (aas_vertexchain) FreeMemory(aas_vertexchain); 294 aas_vertexchain = NULL; 295 if (aas_planechain) FreeMemory(aas_planechain); 296 aas_planechain = NULL; 297 if (aas_edgechain) FreeMemory(aas_edgechain); 298 aas_edgechain = NULL; 299 } //end of the function AAS_FreeMaxAAS 300 //=========================================================================== 301 // 302 // Parameter: - 303 // Returns: - 304 // Changes Globals: - 305 //=========================================================================== 306 unsigned AAS_HashVec(vec3_t vec) 307 { 308 int x, y; 309 310 x = (MAX_MAP_BOUNDS + (int)(vec[0]+0.5)) >> VERTEX_HASH_SHIFT; 311 y = (MAX_MAP_BOUNDS + (int)(vec[1]+0.5)) >> VERTEX_HASH_SHIFT; 312 313 if (x < 0 || x >= VERTEX_HASH_SIZE || y < 0 || y >= VERTEX_HASH_SIZE) 314 { 315 Log_Print("WARNING! HashVec: point %f %f %f outside valid range\n", vec[0], vec[1], vec[2]); 316 Log_Print("This should never happen!\n"); 317 return -1; 318 } //end if 319 320 return y*VERTEX_HASH_SIZE + x; 321 } //end of the function AAS_HashVec 322 //=========================================================================== 323 // returns true if the vertex was found in the list 324 // stores the vertex number in *vnum 325 // stores a new vertex if not stored already 326 // 327 // Parameter: - 328 // Returns: - 329 // Changes Globals: - 330 //=========================================================================== 331 qboolean AAS_GetVertex(vec3_t v, int *vnum) 332 { 333 int i; 334 #ifndef VERTEX_HASHING 335 float diff; 336 #endif //VERTEX_HASHING 337 338 #ifdef VERTEX_HASHING 339 int h, vn; 340 vec3_t vert; 341 342 for (i = 0; i < 3; i++) 343 { 344 if ( fabs(v[i] - Q_rint(v[i])) < INTEGRAL_EPSILON) 345 vert[i] = Q_rint(v[i]); 346 else 347 vert[i] = v[i]; 348 } //end for 349 350 h = AAS_HashVec(vert); 351 //if the vertex was outside the valid range 352 if (h == -1) 353 { 354 *vnum = -1; 355 return true; 356 } //end if 357 358 for (vn = aas_hashverts[h]; vn >= 0; vn = aas_vertexchain[vn]) 359 { 360 if (fabs(aasworld.vertexes[vn][0] - vert[0]) < VERTEX_EPSILON 361 && fabs(aasworld.vertexes[vn][1] - vert[1]) < VERTEX_EPSILON 362 && fabs(aasworld.vertexes[vn][2] - vert[2]) < VERTEX_EPSILON) 363 { 364 *vnum = vn; 365 return true; 366 } //end if 367 } //end for 368 #else //VERTEX_HASHING 369 //check if the vertex is already stored 370 //stupid linear search 371 for (i = 0; i < aasworld.numvertexes; i++) 372 { 373 diff = vert[0] - aasworld.vertexes[i][0]; 374 if (diff < VERTEX_EPSILON && diff > -VERTEX_EPSILON) 375 { 376 diff = vert[1] - aasworld.vertexes[i][1]; 377 if (diff < VERTEX_EPSILON && diff > -VERTEX_EPSILON) 378 { 379 diff = vert[2] - aasworld.vertexes[i][2]; 380 if (diff < VERTEX_EPSILON && diff > -VERTEX_EPSILON) 381 { 382 *vnum = i; 383 return true; 384 } //end if 385 } //end if 386 } //end if 387 } //end for 388 #endif //VERTEX_HASHING 389 390 if (aasworld.numvertexes >= max_aas.max_vertexes) 391 { 392 Error("AAS_MAX_VERTEXES = %d", max_aas.max_vertexes); 393 } //end if 394 VectorCopy(vert, aasworld.vertexes[aasworld.numvertexes]); 395 *vnum = aasworld.numvertexes; 396 397 #ifdef VERTEX_HASHING 398 aas_vertexchain[aasworld.numvertexes] = aas_hashverts[h]; 399 aas_hashverts[h] = aasworld.numvertexes; 400 #endif //VERTEX_HASHING 401 402 aasworld.numvertexes++; 403 return false; 404 } //end of the function AAS_GetVertex 405 //=========================================================================== 406 // 407 // Parameter: - 408 // Returns: - 409 // Changes Globals: - 410 //=========================================================================== 411 unsigned AAS_HashEdge(int v1, int v2) 412 { 413 int vnum1, vnum2; 414 // 415 if (v1 < v2) 416 { 417 vnum1 = v1; 418 vnum2 = v2; 419 } //end if 420 else 421 { 422 vnum1 = v2; 423 vnum2 = v1; 424 } //end else 425 return (vnum1 + vnum2) & (EDGE_HASH_SIZE-1); 426 } //end of the function AAS_HashVec 427 //=========================================================================== 428 // 429 // Parameter: - 430 // Returns: - 431 // Changes Globals: - 432 //=========================================================================== 433 void AAS_AddEdgeToHash(int edgenum) 434 { 435 int hash; 436 aas_edge_t *edge; 437 438 edge = &aasworld.edges[edgenum]; 439 440 hash = AAS_HashEdge(edge->v[0], edge->v[1]); 441 442 aas_edgechain[edgenum] = aas_hashedges[hash]; 443 aas_hashedges[hash] = edgenum; 444 } //end of the function AAS_AddEdgeToHash 445 //=========================================================================== 446 // 447 // Parameter: - 448 // Returns: - 449 // Changes Globals: - 450 //=========================================================================== 451 qboolean AAS_FindHashedEdge(int v1num, int v2num, int *edgenum) 452 { 453 int e, hash; 454 aas_edge_t *edge; 455 456 hash = AAS_HashEdge(v1num, v2num); 457 for (e = aas_hashedges[hash]; e >= 0; e = aas_edgechain[e]) 458 { 459 edge = &aasworld.edges[e]; 460 if (edge->v[0] == v1num) 461 { 462 if (edge->v[1] == v2num) 463 { 464 *edgenum = e; 465 return true; 466 } //end if 467 } //end if 468 else if (edge->v[1] == v1num) 469 { 470 if (edge->v[0] == v2num) 471 { 472 //negative for a reversed edge 473 *edgenum = -e; 474 return true; 475 } //end if 476 } //end else 477 } //end for 478 return false; 479 } //end of the function AAS_FindHashedPlane 480 //=========================================================================== 481 // returns true if the edge was found 482 // stores the edge number in *edgenum (negative if reversed edge) 483 // stores new edge if not stored already 484 // returns zero when the edge is degenerate 485 // 486 // Parameter: - 487 // Returns: - 488 // Changes Globals: - 489 //=========================================================================== 490 qboolean AAS_GetEdge(vec3_t v1, vec3_t v2, int *edgenum) 491 { 492 int v1num, v2num; 493 qboolean found; 494 495 //the first edge is a dummy 496 if (aasworld.numedges == 0) aasworld.numedges = 1; 497 498 found = AAS_GetVertex(v1, &v1num); 499 found &= AAS_GetVertex(v2, &v2num); 500 //if one of the vertexes was outside the valid range 501 if (v1num == -1 || v2num == -1) 502 { 503 *edgenum = 0; 504 return true; 505 } //end if 506 //if both vertexes are the same or snapped onto each other 507 if (v1num == v2num) 508 { 509 *edgenum = 0; 510 return true; 511 } //end if 512 //if both vertexes where already stored 513 if (found) 514 { 515 #ifdef EDGE_HASHING 516 if (AAS_FindHashedEdge(v1num, v2num, edgenum)) return true; 517 #else 518 int i; 519 for (i = 1; i < aasworld.numedges; i++) 520 { 521 if (aasworld.edges[i].v[0] == v1num) 522 { 523 if (aasworld.edges[i].v[1] == v2num) 524 { 525 *edgenum = i; 526 return true; 527 } //end if 528 } //end if 529 else if (aasworld.edges[i].v[1] == v1num) 530 { 531 if (aasworld.edges[i].v[0] == v2num) 532 { 533 //negative for a reversed edge 534 *edgenum = -i; 535 return true; 536 } //end if 537 } //end else 538 } //end for 539 #endif //EDGE_HASHING 540 } //end if 541 if (aasworld.numedges >= max_aas.max_edges) 542 { 543 Error("AAS_MAX_EDGES = %d", max_aas.max_edges); 544 } //end if 545 aasworld.edges[aasworld.numedges].v[0] = v1num; 546 aasworld.edges[aasworld.numedges].v[1] = v2num; 547 *edgenum = aasworld.numedges; 548 #ifdef EDGE_HASHING 549 AAS_AddEdgeToHash(*edgenum); 550 #endif //EDGE_HASHING 551 aasworld.numedges++; 552 return false; 553 } //end of the function AAS_GetEdge 554 //=========================================================================== 555 // 556 // Parameter: - 557 // Returns: - 558 // Changes Globals: - 559 //=========================================================================== 560 int AAS_PlaneTypeForNormal(vec3_t normal) 561 { 562 vec_t ax, ay, az; 563 564 //NOTE: epsilon used 565 if ( (normal[0] >= 1.0 -NORMAL_EPSILON) || 566 (normal[0] <= -1.0 + NORMAL_EPSILON)) return PLANE_X; 567 if ( (normal[1] >= 1.0 -NORMAL_EPSILON) || 568 (normal[1] <= -1.0 + NORMAL_EPSILON)) return PLANE_Y; 569 if ( (normal[2] >= 1.0 -NORMAL_EPSILON) || 570 (normal[2] <= -1.0 + NORMAL_EPSILON)) return PLANE_Z; 571 572 ax = fabs(normal[0]); 573 ay = fabs(normal[1]); 574 az = fabs(normal[2]); 575 576 if (ax >= ay && ax >= az) return PLANE_ANYX; 577 if (ay >= ax && ay >= az) return PLANE_ANYY; 578 return PLANE_ANYZ; 579 } //end of the function AAS_PlaneTypeForNormal 580 //=========================================================================== 581 // 582 // Parameter: - 583 // Returns: - 584 // Changes Globals: - 585 //=========================================================================== 586 void AAS_AddPlaneToHash(int planenum) 587 { 588 int hash; 589 aas_plane_t *plane; 590 591 plane = &aasworld.planes[planenum]; 592 593 hash = (int)fabs(plane->dist) / 8; 594 hash &= (PLANE_HASH_SIZE-1); 595 596 aas_planechain[planenum] = aas_hashplanes[hash]; 597 aas_hashplanes[hash] = planenum; 598 } //end of the function AAS_AddPlaneToHash 599 //=========================================================================== 600 // 601 // Parameter: - 602 // Returns: - 603 // Changes Globals: - 604 //=========================================================================== 605 int AAS_PlaneEqual(vec3_t normal, float dist, int planenum) 606 { 607 float diff; 608 609 diff = dist - aasworld.planes[planenum].dist; 610 if (diff > -DIST_EPSILON && diff < DIST_EPSILON) 611 { 612 diff = normal[0] - aasworld.planes[planenum].normal[0]; 613 if (diff > -NORMAL_EPSILON && diff < NORMAL_EPSILON) 614 { 615 diff = normal[1] - aasworld.planes[planenum].normal[1]; 616 if (diff > -NORMAL_EPSILON && diff < NORMAL_EPSILON) 617 { 618 diff = normal[2] - aasworld.planes[planenum].normal[2]; 619 if (diff > -NORMAL_EPSILON && diff < NORMAL_EPSILON) 620 { 621 return true; 622 } //end if 623 } //end if 624 } //end if 625 } //end if 626 return false; 627 } //end of the function AAS_PlaneEqual 628 //=========================================================================== 629 // 630 // Parameter: - 631 // Returns: - 632 // Changes Globals: - 633 //=========================================================================== 634 qboolean AAS_FindPlane(vec3_t normal, float dist, int *planenum) 635 { 636 int i; 637 638 for (i = 0; i < aasworld.numplanes; i++) 639 { 640 if (AAS_PlaneEqual(normal, dist, i)) 641 { 642 *planenum = i; 643 return true; 644 } //end if 645 } //end for 646 return false; 647 } //end of the function AAS_FindPlane 648 //=========================================================================== 649 // 650 // Parameter: - 651 // Returns: - 652 // Changes Globals: - 653 //=========================================================================== 654 qboolean AAS_FindHashedPlane(vec3_t normal, float dist, int *planenum) 655 { 656 int i, p; 657 aas_plane_t *plane; 658 int hash, h; 659 660 hash = (int)fabs(dist) / 8; 661 hash &= (PLANE_HASH_SIZE-1); 662 663 //search the border bins as well 664 for (i = -1; i <= 1; i++) 665 { 666 h = (hash+i)&(PLANE_HASH_SIZE-1); 667 for (p = aas_hashplanes[h]; p >= 0; p = aas_planechain[p]) 668 { 669 plane = &aasworld.planes[p]; 670 if (AAS_PlaneEqual(normal, dist, p)) 671 { 672 *planenum = p; 673 return true; 674 } //end if 675 } //end for 676 } //end for 677 return false; 678 } //end of the function AAS_FindHashedPlane 679 //=========================================================================== 680 // 681 // Parameter: - 682 // Returns: - 683 // Changes Globals: - 684 //=========================================================================== 685 qboolean AAS_GetPlane(vec3_t normal, vec_t dist, int *planenum) 686 { 687 aas_plane_t *plane, temp; 688 689 //if (AAS_FindPlane(normal, dist, planenum)) return true; 690 if (AAS_FindHashedPlane(normal, dist, planenum)) return true; 691 692 if (aasworld.numplanes >= max_aas.max_planes-1) 693 { 694 Error("AAS_MAX_PLANES = %d", max_aas.max_planes); 695 } //end if 696 697 #ifdef STOREPLANESDOUBLE 698 plane = &aasworld.planes[aasworld.numplanes]; 699 VectorCopy(normal, plane->normal); 700 plane->dist = dist; 701 plane->type = (plane+1)->type = PlaneTypeForNormal(plane->normal); 702 703 VectorCopy(normal, (plane+1)->normal); 704 VectorNegate((plane+1)->normal, (plane+1)->normal); 705 (plane+1)->dist = -dist; 706 707 aasworld.numplanes += 2; 708 709 //allways put axial planes facing positive first 710 if (plane->type < 3) 711 { 712 if (plane->normal[0] < 0 || plane->normal[1] < 0 || plane->normal[2] < 0) 713 { 714 // flip order 715 temp = *plane; 716 *plane = *(plane+1); 717 *(plane+1) = temp; 718 *planenum = aasworld.numplanes - 1; 719 return false; 720 } //end if 721 } //end if 722 *planenum = aasworld.numplanes - 2; 723 //add the planes to the hash 724 AAS_AddPlaneToHash(aasworld.numplanes - 1); 725 AAS_AddPlaneToHash(aasworld.numplanes - 2); 726 return false; 727 #else 728 plane = &aasworld.planes[aasworld.numplanes]; 729 VectorCopy(normal, plane->normal); 730 plane->dist = dist; 731 plane->type = AAS_PlaneTypeForNormal(normal); 732 733 *planenum = aasworld.numplanes; 734 aasworld.numplanes++; 735 //add the plane to the hash 736 AAS_AddPlaneToHash(aasworld.numplanes - 1); 737 return false; 738 #endif //STOREPLANESDOUBLE 739 } //end of the function AAS_GetPlane 740 //=========================================================================== 741 // 742 // Parameter: - 743 // Returns: - 744 // Changes Globals: - 745 //=========================================================================== 746 qboolean AAS_GetFace(winding_t *w, plane_t *p, int side, int *facenum) 747 { 748 int edgenum, i, j; 749 aas_face_t *face; 750 751 //face zero is a dummy, because of the face index with negative numbers 752 if (aasworld.numfaces == 0) aasworld.numfaces = 1; 753 754 if (aasworld.numfaces >= max_aas.max_faces) 755 { 756 Error("AAS_MAX_FACES = %d", max_aas.max_faces); 757 } //end if 758 face = &aasworld.faces[aasworld.numfaces]; 759 AAS_GetPlane(p->normal, p->dist, &face->planenum); 760 face->faceflags = 0; 761 face->firstedge = aasworld.edgeindexsize; 762 face->frontarea = 0; 763 face->backarea = 0; 764 face->numedges = 0; 765 for (i = 0; i < w->numpoints; i++) 766 { 767 if (aasworld.edgeindexsize >= max_aas.max_edgeindexsize) 768 { 769 Error("AAS_MAX_EDGEINDEXSIZE = %d", max_aas.max_edgeindexsize); 770 } //end if 771 j = (i+1) % w->numpoints; 772 AAS_GetEdge(w->p[i], w->p[j], &edgenum); 773 //if the edge wasn't degenerate 774 if (edgenum) 775 { 776 aasworld.edgeindex[aasworld.edgeindexsize++] = edgenum; 777 face->numedges++; 778 } //end if 779 else if (verbose) 780 { 781 Log_Write("AAS_GetFace: face %d had degenerate edge %d-%d\r\n", 782 aasworld.numfaces, i, j); 783 } //end else 784 } //end for 785 if (face->numedges < 1 786 #ifdef NOTHREEVERTEXFACES 787 || face->numedges < 3 788 #endif //NOTHREEVERTEXFACES 789 ) 790 { 791 memset(&aasworld.faces[aasworld.numfaces], 0, sizeof(aas_face_t)); 792 Log_Write("AAS_GetFace: face %d was tiny\r\n", aasworld.numfaces); 793 return false; 794 } //end if 795 *facenum = aasworld.numfaces; 796 aasworld.numfaces++; 797 return true; 798 } //end of the function AAS_GetFace 799 //=========================================================================== 800 // 801 // Parameter: - 802 // Returns: - 803 // Changes Globals: - 804 //=========================================================================== 805 /* 806 qboolean AAS_GetFace(winding_t *w, plane_t *p, int side, int *facenum) 807 { 808 aas_edgeindex_t edges[1024]; 809 int planenum, numedges, i; 810 int j, edgenum; 811 qboolean foundplane, foundedges; 812 aas_face_t *face; 813 814 //face zero is a dummy, because of the face index with negative numbers 815 if (aasworld.numfaces == 0) aasworld.numfaces = 1; 816 817 foundplane = AAS_GetPlane(p->normal, p->dist, &planenum); 818 819 foundedges = true; 820 numedges = w->numpoints; 821 for (i = 0; i < w->numpoints; i++) 822 { 823 if (i >= 1024) Error("AAS_GetFace: more than %d edges\n", 1024); 824 foundedges &= AAS_GetEdge(w->p[i], w->p[(i+1 >= w->numpoints ? 0 : i+1)], &edges[i]); 825 } //end for 826 827 //FIXME: use portal number instead of a search 828 //if the plane and all edges already existed 829 if (foundplane && foundedges) 830 { 831 for (i = 0; i < aasworld.numfaces; i++) 832 { 833 face = &aasworld.faces[i]; 834 if (planenum == face->planenum) 835 { 836 if (numedges == face->numedges) 837 { 838 for (j = 0; j < numedges; j++) 839 { 840 edgenum = abs(aasworld.edgeindex[face->firstedge + j]); 841 if (abs(edges[i]) != edgenum) break; 842 } //end for 843 if (j == numedges) 844 { 845 //jippy found the face 846 *facenum = -i; 847 return true; 848 } //end if 849 } //end if 850 } //end if 851 } //end for 852 } //end if 853 if (aasworld.numfaces >= max_aas.max_faces) 854 { 855 Error("AAS_MAX_FACES = %d", max_aas.max_faces); 856 } //end if 857 face = &aasworld.faces[aasworld.numfaces]; 858 face->planenum = planenum; 859 face->faceflags = 0; 860 face->numedges = numedges; 861 face->firstedge = aasworld.edgeindexsize; 862 face->frontarea = 0; 863 face->backarea = 0; 864 for (i = 0; i < numedges; i++) 865 { 866 if (aasworld.edgeindexsize >= max_aas.max_edgeindexsize) 867 { 868 Error("AAS_MAX_EDGEINDEXSIZE = %d", max_aas.max_edgeindexsize); 869 } //end if 870 aasworld.edgeindex[aasworld.edgeindexsize++] = edges[i]; 871 } //end for 872 *facenum = aasworld.numfaces; 873 aasworld.numfaces++; 874 return false; 875 } //end of the function AAS_GetFace*/ 876 //=========================================================================== 877 // 878 // Parameter: - 879 // Returns: - 880 // Changes Globals: - 881 //=========================================================================== 882 void AAS_StoreAreaSettings(tmp_areasettings_t *tmpareasettings) 883 { 884 aas_areasettings_t *areasettings; 885 886 if (aasworld.numareasettings == 0) aasworld.numareasettings = 1; 887 areasettings = &aasworld.areasettings[aasworld.numareasettings++]; 888 areasettings->areaflags = tmpareasettings->areaflags; 889 areasettings->presencetype = tmpareasettings->presencetype; 890 areasettings->contents = tmpareasettings->contents; 891 if (tmpareasettings->modelnum > AREACONTENTS_MAXMODELNUM) 892 Log_Print("WARNING: more than %d mover models\n", AREACONTENTS_MAXMODELNUM); 893 areasettings->contents |= (tmpareasettings->modelnum & AREACONTENTS_MAXMODELNUM) << AREACONTENTS_MODELNUMSHIFT; 894 } //end of the function AAS_StoreAreaSettings 895 //=========================================================================== 896 // 897 // Parameter: - 898 // Returns: - 899 // Changes Globals: - 900 //=========================================================================== 901 int AAS_StoreArea(tmp_area_t *tmparea) 902 { 903 int side, edgenum, i; 904 plane_t *plane; 905 tmp_face_t *tmpface; 906 aas_area_t *aasarea; 907 aas_edge_t *edge; 908 aas_face_t *aasface; 909 aas_faceindex_t aasfacenum; 910 vec3_t facecenter; 911 winding_t *w; 912 913 //when the area is merged go to the merged area 914 //FIXME: this isn't necessary anymore because the tree 915 // is refreshed after area merging 916 while(tmparea->mergedarea) tmparea = tmparea->mergedarea; 917 // 918 if (tmparea->invalid) Error("AAS_StoreArea: tried to store invalid area"); 919 //if there is an aas area already stored for this tmp area 920 if (tmparea->aasareanum) return -tmparea->aasareanum; 921 // 922 if (aasworld.numareas >= max_aas.max_areas) 923 { 924 Error("AAS_MAX_AREAS = %d", max_aas.max_areas); 925 } //end if 926 //area zero is a dummy 927 if (aasworld.numareas == 0) aasworld.numareas = 1; 928 //create an area from this leaf 929 aasarea = &aasworld.areas[aasworld.numareas]; 930 aasarea->areanum = aasworld.numareas; 931 aasarea->numfaces = 0; 932 aasarea->firstface = aasworld.faceindexsize; 933 ClearBounds(aasarea->mins, aasarea->maxs); 934 VectorClear(aasarea->center); 935 // 936 // Log_Write("tmparea %d became aasarea %d\r\n", tmparea->areanum, aasarea->areanum); 937 //store the aas area number at the tmp area 938 tmparea->aasareanum = aasarea->areanum; 939 // 940 for (tmpface = tmparea->tmpfaces; tmpface; tmpface = tmpface->next[side]) 941 { 942 side = tmpface->frontarea != tmparea; 943 //if there's an aas face created for the tmp face already 944 if (tmpface->aasfacenum) 945 { 946 //we're at the back of the face so use a negative index 947 aasfacenum = -tmpface->aasfacenum; 948 #ifdef DEBUG 949 if (tmpface->aasfacenum < 0 || tmpface->aasfacenum > max_aas.max_faces) 950 { 951 Error("AAS_CreateTree_r: face number out of range"); 952 } //end if 953 #endif //DEBUG 954 aasface = &aasworld.faces[tmpface->aasfacenum]; 955 aasface->backarea = aasarea->areanum; 956 } //end if 957 else 958 { 959 plane = &mapplanes[tmpface->planenum ^ side]; 960 if (side) 961 { 962 w = tmpface->winding; 963 tmpface->winding = ReverseWinding(tmpface->winding); 964 } //end if 965 if (!AAS_GetFace(tmpface->winding, plane, 0, &aasfacenum)) continue; 966 if (side) 967 { 968 FreeWinding(tmpface->winding); 969 tmpface->winding = w; 970 } //end if 971 aasface = &aasworld.faces[aasfacenum]; 972 aasface->frontarea = aasarea->areanum; 973 aasface->backarea = 0; 974 aasface->faceflags = tmpface->faceflags; 975 //set the face number at the tmp face 976 tmpface->aasfacenum = aasfacenum; 977 } //end else 978 //add face points to the area bounds and 979 //calculate the face 'center' 980 VectorClear(facecenter); 981 for (edgenum = 0; edgenum < aasface->numedges; edgenum++) 982 { 983 edge = &aasworld.edges[abs(aasworld.edgeindex[aasface->firstedge + edgenum])]; 984 for (i = 0; i < 2; i++) 985 { 986 AddPointToBounds(aasworld.vertexes[edge->v[i]], aasarea->mins, aasarea->maxs); 987 VectorAdd(aasworld.vertexes[edge->v[i]], facecenter, facecenter); 988 } //end for 989 } //end for 990 VectorScale(facecenter, 1.0 / (aasface->numedges * 2.0), facecenter); 991 //add the face 'center' to the area 'center' 992 VectorAdd(aasarea->center, facecenter, aasarea->center); 993 // 994 if (aasworld.faceindexsize >= max_aas.max_faceindexsize) 995 { 996 Error("AAS_MAX_FACEINDEXSIZE = %d", max_aas.max_faceindexsize); 997 } //end if 998 aasworld.faceindex[aasworld.faceindexsize++] = aasfacenum; 999 aasarea->numfaces++; 1000 } //end for 1001 //if the area has no faces at all (return 0, = solid leaf) 1002 if (!aasarea->numfaces) return 0; 1003 // 1004 VectorScale(aasarea->center, 1.0 / aasarea->numfaces, aasarea->center); 1005 //Log_Write("area %d center %f %f %f\r\n", aasworld.numareas, 1006 // aasarea->center[0], aasarea->center[1], aasarea->center[2]); 1007 //store the area settings 1008 AAS_StoreAreaSettings(tmparea->settings); 1009 // 1010 //Log_Write("tmp area %d became aas area %d\r\n", tmpareanum, aasarea->areanum); 1011 qprintf("\r%6d", aasarea->areanum); 1012 // 1013 aasworld.numareas++; 1014 return -(aasworld.numareas - 1); 1015 } //end of the function AAS_StoreArea 1016 //=========================================================================== 1017 // 1018 // Parameter: - 1019 // Returns: - 1020 // Changes Globals: - 1021 //=========================================================================== 1022 int AAS_StoreTree_r(tmp_node_t *tmpnode) 1023 { 1024 int aasnodenum; 1025 plane_t *plane; 1026 aas_node_t *aasnode; 1027 1028 //if it is a solid leaf 1029 if (!tmpnode) return 0; 1030 //negative so it's an area 1031 if (tmpnode->tmparea) return AAS_StoreArea(tmpnode->tmparea); 1032 //it's another node 1033 //the first node is a dummy 1034 if (aasworld.numnodes == 0) aasworld.numnodes = 1; 1035 if (aasworld.numnodes >= max_aas.max_nodes) 1036 { 1037 Error("AAS_MAX_NODES = %d", max_aas.max_nodes); 1038 } //end if 1039 aasnodenum = aasworld.numnodes; 1040 aasnode = &aasworld.nodes[aasworld.numnodes++]; 1041 plane = &mapplanes[tmpnode->planenum]; 1042 AAS_GetPlane(plane->normal, plane->dist, &aasnode->planenum); 1043 aasnode->children[0] = AAS_StoreTree_r(tmpnode->children[0]); 1044 aasnode->children[1] = AAS_StoreTree_r(tmpnode->children[1]); 1045 return aasnodenum; 1046 } //end of the function AAS_StoreTree_r 1047 //=========================================================================== 1048 // 1049 // Parameter: - 1050 // Returns: - 1051 // Changes Globals: - 1052 //=========================================================================== 1053 void AAS_StoreBoundingBoxes(void) 1054 { 1055 if (cfg.numbboxes > max_aas.max_bboxes) 1056 { 1057 Error("more than %d bounding boxes", max_aas.max_bboxes); 1058 } //end if 1059 aasworld.numbboxes = cfg.numbboxes; 1060 memcpy(aasworld.bboxes, cfg.bboxes, cfg.numbboxes * sizeof(aas_bbox_t)); 1061 } //end of the function AAS_StoreBoundingBoxes 1062 //=========================================================================== 1063 // 1064 // Parameter: - 1065 // Returns: - 1066 // Changes Globals: - 1067 //=========================================================================== 1068 void AAS_StoreFile(char *filename) 1069 { 1070 AAS_AllocMaxAAS(); 1071 1072 Log_Write("AAS_StoreFile\r\n"); 1073 // 1074 AAS_StoreBoundingBoxes(); 1075 // 1076 qprintf("%6d areas stored", 0); 1077 //start with node 1 because node zero is a dummy 1078 AAS_StoreTree_r(tmpaasworld.nodes); 1079 qprintf("\n"); 1080 Log_Write("%6d areas stored\r\n", aasworld.numareas); 1081 aasworld.loaded = true; 1082 } //end of the function AAS_StoreFile