/* =========================================================================== Return to Castle Wolfenstein single player GPL Source Code Copyright (C) 1999-2010 id Software LLC, a ZeniMax Media company. This file is part of the Return to Castle Wolfenstein single player GPL Source Code (“RTCW SP Source Code”). RTCW SP 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 3 of the License, or (at your option) any later version. RTCW SP 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 RTCW SP Source Code. If not, see . In addition, the RTCW SP Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the RTCW SP Source Code. If not, please request a copy in writing from id Software at the address below. If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA. =========================================================================== */ //=========================================================================== // // Name: aas_store.c // Function: // Programmer: Mr Elusive (MrElusive@demigod.demon.nl) // Last update: 1997-12-04 // Tab Size: 3 //=========================================================================== #include "qbsp.h" #include "../botlib/aasfile.h" #include "aas_file.h" #include "aas_store.h" #include "aas_create.h" #include "aas_cfg.h" //#define NOTHREEVERTEXFACES #define STOREPLANESDOUBLE #define VERTEX_EPSILON 0.1 //NOTE: changed from 0.5 // MrE: use same epsilons as q3map! //NOTE: changed from 0.0001 #define NORMAL_EPSILON 0.00001 //NOTE: changed from 0.05 #define DIST_EPSILON 0.01 #define INTEGRAL_EPSILON 0.01 #define VEREX_EPSILON 0.1 //NOTE: changed from 0.5 #define VERTEX_HASHING #define VERTEX_HASH_SHIFT 7 #define VERTEX_HASH_SIZE ( ( MAX_MAP_BOUNDS >> ( VERTEX_HASH_SHIFT - 1 ) ) + 1 ) //was 64 // #define PLANE_HASHING #define PLANE_HASH_SIZE 1024 //must be power of 2 // #define EDGE_HASHING #define EDGE_HASH_SIZE 1024 //must be power of 2 // Ridah aas_t aasworlds[1]; aas_t( *aasworld ); // done. //vertex hash int *aas_vertexchain; // the next vertex in a hash chain int aas_hashverts[VERTEX_HASH_SIZE * VERTEX_HASH_SIZE]; // a vertex number, or 0 for no verts //plane hash int *aas_planechain; int aas_hashplanes[PLANE_HASH_SIZE]; //edge hash int *aas_edgechain; int aas_hashedges[EDGE_HASH_SIZE]; int allocatedaasmem = 0; int groundfacesonly = false; //true; // typedef struct max_aas_s { int max_bboxes; int max_vertexes; int max_planes; int max_edges; int max_edgeindexsize; int max_faces; int max_faceindexsize; int max_areas; int max_areasettings; int max_reachabilitysize; int max_nodes; int max_portals; int max_portalindexsize; int max_clusters; } max_aas_t; //maximums of everything max_aas_t max_aas; //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== int AAS_CountTmpNodes( tmp_node_t *tmpnode ) { if ( !tmpnode ) { return 0; } return AAS_CountTmpNodes( tmpnode->children[0] ) + AAS_CountTmpNodes( tmpnode->children[1] ) + 1; } //end of the function AAS_CountTmpNodes //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== void AAS_InitMaxAAS( void ) { int numfaces, numpoints, numareas; tmp_face_t *f; tmp_area_t *a; numpoints = 0; numfaces = 0; for ( f = tmpaasworld.faces; f; f = f->l_next ) { numfaces++; if ( f->winding ) { numpoints += f->winding->numpoints; } } //end for // numareas = 0; for ( a = tmpaasworld.areas; a; a = a->l_next ) { numareas++; } //end for max_aas.max_bboxes = AAS_MAX_BBOXES; max_aas.max_vertexes = numpoints + 1; max_aas.max_planes = nummapplanes; max_aas.max_edges = numpoints + 1; max_aas.max_edgeindexsize = ( numpoints + 1 ) * 3; max_aas.max_faces = numfaces + 10; max_aas.max_faceindexsize = ( numfaces + 10 ) * 2; max_aas.max_areas = numareas + 10; max_aas.max_areasettings = numareas + 10; max_aas.max_reachabilitysize = 0; max_aas.max_nodes = AAS_CountTmpNodes( tmpaasworld.nodes ) + 10; max_aas.max_portals = 0; max_aas.max_portalindexsize = 0; max_aas.max_clusters = 0; } //end of the function AAS_InitMaxAAS //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== void AAS_AllocMaxAAS( void ) { int i; AAS_InitMaxAAS(); //bounding boxes ( *aasworld ).numbboxes = 0; ( *aasworld ).bboxes = (aas_bbox_t *) GetClearedMemory( max_aas.max_bboxes * sizeof( aas_bbox_t ) ); allocatedaasmem += max_aas.max_bboxes * sizeof( aas_bbox_t ); //vertexes ( *aasworld ).numvertexes = 0; ( *aasworld ).vertexes = (aas_vertex_t *) GetClearedMemory( max_aas.max_vertexes * sizeof( aas_vertex_t ) ); allocatedaasmem += max_aas.max_vertexes * sizeof( aas_vertex_t ); //planes ( *aasworld ).numplanes = 0; ( *aasworld ).planes = (aas_plane_t *) GetClearedMemory( max_aas.max_planes * sizeof( aas_plane_t ) ); allocatedaasmem += max_aas.max_planes * sizeof( aas_plane_t ); //edges ( *aasworld ).numedges = 0; ( *aasworld ).edges = (aas_edge_t *) GetClearedMemory( max_aas.max_edges * sizeof( aas_edge_t ) ); allocatedaasmem += max_aas.max_edges * sizeof( aas_edge_t ); //edge index ( *aasworld ).edgeindexsize = 0; ( *aasworld ).edgeindex = (aas_edgeindex_t *) GetClearedMemory( max_aas.max_edgeindexsize * sizeof( aas_edgeindex_t ) ); allocatedaasmem += max_aas.max_edgeindexsize * sizeof( aas_edgeindex_t ); //faces ( *aasworld ).numfaces = 0; ( *aasworld ).faces = (aas_face_t *) GetClearedMemory( max_aas.max_faces * sizeof( aas_face_t ) ); allocatedaasmem += max_aas.max_faces * sizeof( aas_face_t ); //face index ( *aasworld ).faceindexsize = 0; ( *aasworld ).faceindex = (aas_faceindex_t *) GetClearedMemory( max_aas.max_faceindexsize * sizeof( aas_faceindex_t ) ); allocatedaasmem += max_aas.max_faceindexsize * sizeof( aas_faceindex_t ); //convex areas ( *aasworld ).numareas = 0; ( *aasworld ).areas = (aas_area_t *) GetClearedMemory( max_aas.max_areas * sizeof( aas_area_t ) ); allocatedaasmem += max_aas.max_areas * sizeof( aas_area_t ); //convex area settings ( *aasworld ).numareasettings = 0; ( *aasworld ).areasettings = (aas_areasettings_t *) GetClearedMemory( max_aas.max_areasettings * sizeof( aas_areasettings_t ) ); allocatedaasmem += max_aas.max_areasettings * sizeof( aas_areasettings_t ); //reachablity list ( *aasworld ).reachabilitysize = 0; ( *aasworld ).reachability = (aas_reachability_t *) GetClearedMemory( max_aas.max_reachabilitysize * sizeof( aas_reachability_t ) ); allocatedaasmem += max_aas.max_reachabilitysize * sizeof( aas_reachability_t ); //nodes of the bsp tree ( *aasworld ).numnodes = 0; ( *aasworld ).nodes = (aas_node_t *) GetClearedMemory( max_aas.max_nodes * sizeof( aas_node_t ) ); allocatedaasmem += max_aas.max_nodes * sizeof( aas_node_t ); //cluster portals ( *aasworld ).numportals = 0; ( *aasworld ).portals = (aas_portal_t *) GetClearedMemory( max_aas.max_portals * sizeof( aas_portal_t ) ); allocatedaasmem += max_aas.max_portals * sizeof( aas_portal_t ); //cluster portal index ( *aasworld ).portalindexsize = 0; ( *aasworld ).portalindex = (aas_portalindex_t *) GetClearedMemory( max_aas.max_portalindexsize * sizeof( aas_portalindex_t ) ); allocatedaasmem += max_aas.max_portalindexsize * sizeof( aas_portalindex_t ); //cluster ( *aasworld ).numclusters = 0; ( *aasworld ).clusters = (aas_cluster_t *) GetClearedMemory( max_aas.max_clusters * sizeof( aas_cluster_t ) ); allocatedaasmem += max_aas.max_clusters * sizeof( aas_cluster_t ); // Log_Print( "allocated " ); PrintMemorySize( allocatedaasmem ); Log_Print( " of AAS memory\n" ); //reset the has stuff aas_vertexchain = (int *) GetClearedMemory( max_aas.max_vertexes * sizeof( int ) ); aas_planechain = (int *) GetClearedMemory( max_aas.max_planes * sizeof( int ) ); aas_edgechain = (int *) GetClearedMemory( max_aas.max_edges * sizeof( int ) ); // for ( i = 0; i < max_aas.max_vertexes; i++ ) aas_vertexchain[i] = -1; for ( i = 0; i < VERTEX_HASH_SIZE * VERTEX_HASH_SIZE; i++ ) aas_hashverts[i] = -1; // for ( i = 0; i < max_aas.max_planes; i++ ) aas_planechain[i] = -1; for ( i = 0; i < PLANE_HASH_SIZE; i++ ) aas_hashplanes[i] = -1; // for ( i = 0; i < max_aas.max_edges; i++ ) aas_edgechain[i] = -1; for ( i = 0; i < EDGE_HASH_SIZE; i++ ) aas_hashedges[i] = -1; } //end of the function AAS_AllocMaxAAS //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== void AAS_FreeMaxAAS( void ) { //bounding boxes if ( ( *aasworld ).bboxes ) { FreeMemory( ( *aasworld ).bboxes ); } ( *aasworld ).bboxes = NULL; ( *aasworld ).numbboxes = 0; //vertexes if ( ( *aasworld ).vertexes ) { FreeMemory( ( *aasworld ).vertexes ); } ( *aasworld ).vertexes = NULL; ( *aasworld ).numvertexes = 0; //planes if ( ( *aasworld ).planes ) { FreeMemory( ( *aasworld ).planes ); } ( *aasworld ).planes = NULL; ( *aasworld ).numplanes = 0; //edges if ( ( *aasworld ).edges ) { FreeMemory( ( *aasworld ).edges ); } ( *aasworld ).edges = NULL; ( *aasworld ).numedges = 0; //edge index if ( ( *aasworld ).edgeindex ) { FreeMemory( ( *aasworld ).edgeindex ); } ( *aasworld ).edgeindex = NULL; ( *aasworld ).edgeindexsize = 0; //faces if ( ( *aasworld ).faces ) { FreeMemory( ( *aasworld ).faces ); } ( *aasworld ).faces = NULL; ( *aasworld ).numfaces = 0; //face index if ( ( *aasworld ).faceindex ) { FreeMemory( ( *aasworld ).faceindex ); } ( *aasworld ).faceindex = NULL; ( *aasworld ).faceindexsize = 0; //convex areas if ( ( *aasworld ).areas ) { FreeMemory( ( *aasworld ).areas ); } ( *aasworld ).areas = NULL; ( *aasworld ).numareas = 0; //convex area settings if ( ( *aasworld ).areasettings ) { FreeMemory( ( *aasworld ).areasettings ); } ( *aasworld ).areasettings = NULL; ( *aasworld ).numareasettings = 0; //reachablity list if ( ( *aasworld ).reachability ) { FreeMemory( ( *aasworld ).reachability ); } ( *aasworld ).reachability = NULL; ( *aasworld ).reachabilitysize = 0; //nodes of the bsp tree if ( ( *aasworld ).nodes ) { FreeMemory( ( *aasworld ).nodes ); } ( *aasworld ).nodes = NULL; ( *aasworld ).numnodes = 0; //cluster portals if ( ( *aasworld ).portals ) { FreeMemory( ( *aasworld ).portals ); } ( *aasworld ).portals = NULL; ( *aasworld ).numportals = 0; //cluster portal index if ( ( *aasworld ).portalindex ) { FreeMemory( ( *aasworld ).portalindex ); } ( *aasworld ).portalindex = NULL; ( *aasworld ).portalindexsize = 0; //clusters if ( ( *aasworld ).clusters ) { FreeMemory( ( *aasworld ).clusters ); } ( *aasworld ).clusters = NULL; ( *aasworld ).numclusters = 0; Log_Print( "freed " ); PrintMemorySize( allocatedaasmem ); Log_Print( " of AAS memory\n" ); allocatedaasmem = 0; // if ( aas_vertexchain ) { FreeMemory( aas_vertexchain ); } aas_vertexchain = NULL; if ( aas_planechain ) { FreeMemory( aas_planechain ); } aas_planechain = NULL; if ( aas_edgechain ) { FreeMemory( aas_edgechain ); } aas_edgechain = NULL; } //end of the function AAS_FreeMaxAAS //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== unsigned AAS_HashVec( vec3_t vec ) { int x, y; x = ( MAX_MAP_BOUNDS + (int)( vec[0] + 0.5 ) ) >> VERTEX_HASH_SHIFT; y = ( MAX_MAP_BOUNDS + (int)( vec[1] + 0.5 ) ) >> VERTEX_HASH_SHIFT; if ( x < 0 || x >= VERTEX_HASH_SIZE || y < 0 || y >= VERTEX_HASH_SIZE ) { Log_Print( "WARNING! HashVec: point %f %f %f outside valid range\n", vec[0], vec[1], vec[2] ); Log_Print( "This should never happen!\n" ); return -1; } //end if return y * VERTEX_HASH_SIZE + x; } //end of the function AAS_HashVec //=========================================================================== // returns true if the vertex was found in the list // stores the vertex number in *vnum // stores a new vertex if not stored already // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== qboolean AAS_GetVertex( vec3_t v, int *vnum ) { int i; #ifndef VERTEX_HASHING float diff; #endif //VERTEX_HASHING #ifdef VERTEX_HASHING int h, vn; vec3_t vert; for ( i = 0; i < 3; i++ ) { if ( fabs( v[i] - Q_rint( v[i] ) ) < INTEGRAL_EPSILON ) { vert[i] = Q_rint( v[i] ); } else { vert[i] = v[i]; } } //end for h = AAS_HashVec( vert ); //if the vertex was outside the valid range if ( h == -1 ) { *vnum = -1; return true; } //end if for ( vn = aas_hashverts[h]; vn >= 0; vn = aas_vertexchain[vn] ) { if ( fabs( ( *aasworld ).vertexes[vn][0] - vert[0] ) < VEREX_EPSILON && fabs( ( *aasworld ).vertexes[vn][1] - vert[1] ) < VEREX_EPSILON && fabs( ( *aasworld ).vertexes[vn][2] - vert[2] ) < VEREX_EPSILON ) { *vnum = vn; return true; } //end if } //end for #else //VERTEX_HASHING //check if the vertex is already stored //stupid linear search for ( i = 0; i < ( *aasworld ).numvertexes; i++ ) { diff = vert[0] - ( *aasworld ).vertexes[i][0]; if ( diff < VERTEX_EPSILON && diff > -VERTEX_EPSILON ) { diff = vert[1] - ( *aasworld ).vertexes[i][1]; if ( diff < VERTEX_EPSILON && diff > -VERTEX_EPSILON ) { diff = vert[2] - ( *aasworld ).vertexes[i][2]; if ( diff < VERTEX_EPSILON && diff > -VERTEX_EPSILON ) { *vnum = i; return true; } //end if } //end if } //end if } //end for #endif //VERTEX_HASHING if ( ( *aasworld ).numvertexes >= max_aas.max_vertexes ) { Error( "AAS_MAX_VERTEXES = %d", max_aas.max_vertexes ); } //end if VectorCopy( vert, ( *aasworld ).vertexes[( *aasworld ).numvertexes] ); *vnum = ( *aasworld ).numvertexes; #ifdef VERTEX_HASHING aas_vertexchain[( *aasworld ).numvertexes] = aas_hashverts[h]; aas_hashverts[h] = ( *aasworld ).numvertexes; #endif //VERTEX_HASHING ( *aasworld ).numvertexes++; return false; } //end of the function AAS_GetVertex //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== unsigned AAS_HashEdge( int v1, int v2 ) { int vnum1, vnum2; // if ( v1 < v2 ) { vnum1 = v1; vnum2 = v2; } //end if else { vnum1 = v2; vnum2 = v1; } //end else return ( vnum1 + vnum2 ) & ( EDGE_HASH_SIZE - 1 ); } //end of the function AAS_HashVec //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== void AAS_AddEdgeToHash( int edgenum ) { int hash; aas_edge_t *edge; edge = &( *aasworld ).edges[edgenum]; hash = AAS_HashEdge( edge->v[0], edge->v[1] ); aas_edgechain[edgenum] = aas_hashedges[hash]; aas_hashedges[hash] = edgenum; } //end of the function AAS_AddEdgeToHash //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== qboolean AAS_FindHashedEdge( int v1num, int v2num, int *edgenum ) { int e, hash; aas_edge_t *edge; hash = AAS_HashEdge( v1num, v2num ); for ( e = aas_hashedges[hash]; e >= 0; e = aas_edgechain[e] ) { edge = &( *aasworld ).edges[e]; if ( edge->v[0] == v1num ) { if ( edge->v[1] == v2num ) { *edgenum = e; return true; } //end if } //end if else if ( edge->v[1] == v1num ) { if ( edge->v[0] == v2num ) { //negative for a reversed edge *edgenum = -e; return true; } //end if } //end else } //end for return false; } //end of the function AAS_FindHashedPlane //=========================================================================== // returns true if the edge was found // stores the edge number in *edgenum (negative if reversed edge) // stores new edge if not stored already // returns zero when the edge is degenerate // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== qboolean AAS_GetEdge( vec3_t v1, vec3_t v2, int *edgenum ) { int v1num, v2num; qboolean found; //the first edge is a dummy if ( ( *aasworld ).numedges == 0 ) { ( *aasworld ).numedges = 1; } found = AAS_GetVertex( v1, &v1num ); found &= AAS_GetVertex( v2, &v2num ); //if one of the vertexes was outside the valid range if ( v1num == -1 || v2num == -1 ) { *edgenum = 0; return true; } //end if //if both vertexes are the same or snapped onto each other if ( v1num == v2num ) { *edgenum = 0; return true; } //end if //if both vertexes where already stored if ( found ) { #ifdef EDGE_HASHING if ( AAS_FindHashedEdge( v1num, v2num, edgenum ) ) { return true; } #else int i; for ( i = 1; i < ( *aasworld ).numedges; i++ ) { if ( ( *aasworld ).edges[i].v[0] == v1num ) { if ( ( *aasworld ).edges[i].v[1] == v2num ) { *edgenum = i; return true; } //end if } //end if else if ( ( *aasworld ).edges[i].v[1] == v1num ) { if ( ( *aasworld ).edges[i].v[0] == v2num ) { //negative for a reversed edge *edgenum = -i; return true; } //end if } //end else } //end for #endif //EDGE_HASHING } //end if if ( ( *aasworld ).numedges >= max_aas.max_edges ) { Error( "AAS_MAX_EDGES = %d", max_aas.max_edges ); } //end if ( *aasworld ).edges[( *aasworld ).numedges].v[0] = v1num; ( *aasworld ).edges[( *aasworld ).numedges].v[1] = v2num; *edgenum = ( *aasworld ).numedges; #ifdef EDGE_HASHING AAS_AddEdgeToHash( *edgenum ); #endif //EDGE_HASHING ( *aasworld ).numedges++; return false; } //end of the function AAS_GetEdge //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== int AAS_PlaneTypeForNormal( vec3_t normal ) { vec_t ax, ay, az; //NOTE: epsilon used if ( ( normal[0] >= 1.0 - NORMAL_EPSILON ) || ( normal[0] <= -1.0 + NORMAL_EPSILON ) ) { return PLANE_X; } if ( ( normal[1] >= 1.0 - NORMAL_EPSILON ) || ( normal[1] <= -1.0 + NORMAL_EPSILON ) ) { return PLANE_Y; } if ( ( normal[2] >= 1.0 - NORMAL_EPSILON ) || ( normal[2] <= -1.0 + NORMAL_EPSILON ) ) { return PLANE_Z; } ax = fabs( normal[0] ); ay = fabs( normal[1] ); az = fabs( normal[2] ); if ( ax >= ay && ax >= az ) { return PLANE_ANYX; } if ( ay >= ax && ay >= az ) { return PLANE_ANYY; } return PLANE_ANYZ; } //end of the function AAS_PlaneTypeForNormal //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== void AAS_AddPlaneToHash( int planenum ) { int hash; aas_plane_t *plane; plane = &( *aasworld ).planes[planenum]; hash = (int)fabs( plane->dist ) / 8; hash &= ( PLANE_HASH_SIZE - 1 ); aas_planechain[planenum] = aas_hashplanes[hash]; aas_hashplanes[hash] = planenum; } //end of the function AAS_AddPlaneToHash //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== int AAS_PlaneEqual( vec3_t normal, float dist, int planenum ) { float diff; diff = dist - ( *aasworld ).planes[planenum].dist; if ( diff > -DIST_EPSILON && diff < DIST_EPSILON ) { diff = normal[0] - ( *aasworld ).planes[planenum].normal[0]; if ( diff > -NORMAL_EPSILON && diff < NORMAL_EPSILON ) { diff = normal[1] - ( *aasworld ).planes[planenum].normal[1]; if ( diff > -NORMAL_EPSILON && diff < NORMAL_EPSILON ) { diff = normal[2] - ( *aasworld ).planes[planenum].normal[2]; if ( diff > -NORMAL_EPSILON && diff < NORMAL_EPSILON ) { return true; } //end if } //end if } //end if } //end if return false; } //end of the function AAS_PlaneEqual //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== qboolean AAS_FindPlane( vec3_t normal, float dist, int *planenum ) { int i; for ( i = 0; i < ( *aasworld ).numplanes; i++ ) { if ( AAS_PlaneEqual( normal, dist, i ) ) { *planenum = i; return true; } //end if } //end for return false; } //end of the function AAS_FindPlane //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== qboolean AAS_FindHashedPlane( vec3_t normal, float dist, int *planenum ) { int i, p; aas_plane_t *plane; int hash, h; hash = (int)fabs( dist ) / 8; hash &= ( PLANE_HASH_SIZE - 1 ); //search the border bins as well for ( i = -1; i <= 1; i++ ) { h = ( hash + i ) & ( PLANE_HASH_SIZE - 1 ); for ( p = aas_hashplanes[h]; p >= 0; p = aas_planechain[p] ) { plane = &( *aasworld ).planes[p]; if ( AAS_PlaneEqual( normal, dist, p ) ) { *planenum = p; return true; } //end if } //end for } //end for return false; } //end of the function AAS_FindHashedPlane //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== qboolean AAS_GetPlane( vec3_t normal, vec_t dist, int *planenum ) { aas_plane_t *plane, temp; //if (AAS_FindPlane(normal, dist, planenum)) return true; if ( AAS_FindHashedPlane( normal, dist, planenum ) ) { return true; } if ( ( *aasworld ).numplanes >= max_aas.max_planes - 1 ) { Error( "AAS_MAX_PLANES = %d", max_aas.max_planes ); } //end if #ifdef STOREPLANESDOUBLE plane = &( *aasworld ).planes[( *aasworld ).numplanes]; VectorCopy( normal, plane->normal ); plane->dist = dist; plane->type = ( plane + 1 )->type = PlaneTypeForNormal( plane->normal ); VectorCopy( normal, ( plane + 1 )->normal ); VectorNegate( ( plane + 1 )->normal, ( plane + 1 )->normal ); ( plane + 1 )->dist = -dist; ( *aasworld ).numplanes += 2; //allways put axial planes facing positive first if ( plane->type < 3 ) { if ( plane->normal[0] < 0 || plane->normal[1] < 0 || plane->normal[2] < 0 ) { // flip order temp = *plane; *plane = *( plane + 1 ); *( plane + 1 ) = temp; *planenum = ( *aasworld ).numplanes - 1; return false; } //end if } //end if *planenum = ( *aasworld ).numplanes - 2; //add the planes to the hash AAS_AddPlaneToHash( ( *aasworld ).numplanes - 1 ); AAS_AddPlaneToHash( ( *aasworld ).numplanes - 2 ); return false; #else plane = &( *aasworld ).planes[( *aasworld ).numplanes]; VectorCopy( normal, plane->normal ); plane->dist = dist; plane->type = AAS_PlaneTypeForNormal( normal ); *planenum = ( *aasworld ).numplanes; ( *aasworld ).numplanes++; //add the plane to the hash AAS_AddPlaneToHash( ( *aasworld ).numplanes - 1 ); return false; #endif //STOREPLANESDOUBLE } //end of the function AAS_GetPlane //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== qboolean AAS_GetFace( winding_t *w, plane_t *p, int side, int *facenum ) { int edgenum, i, j; aas_face_t *face; //face zero is a dummy, because of the face index with negative numbers if ( ( *aasworld ).numfaces == 0 ) { ( *aasworld ).numfaces = 1; } if ( ( *aasworld ).numfaces >= max_aas.max_faces ) { Error( "AAS_MAX_FACES = %d", max_aas.max_faces ); } //end if face = &( *aasworld ).faces[( *aasworld ).numfaces]; AAS_GetPlane( p->normal, p->dist, &face->planenum ); face->faceflags = 0; face->firstedge = ( *aasworld ).edgeindexsize; face->frontarea = 0; face->backarea = 0; face->numedges = 0; for ( i = 0; i < w->numpoints; i++ ) { if ( ( *aasworld ).edgeindexsize >= max_aas.max_edgeindexsize ) { Error( "AAS_MAX_EDGEINDEXSIZE = %d", max_aas.max_edgeindexsize ); } //end if j = ( i + 1 ) % w->numpoints; AAS_GetEdge( w->p[i], w->p[j], &edgenum ); //if the edge wasn't degenerate if ( edgenum ) { ( *aasworld ).edgeindex[( *aasworld ).edgeindexsize++] = edgenum; face->numedges++; } //end if else if ( verbose ) { Log_Write( "AAS_GetFace: face %d had degenerate edge %d-%d\r\n", ( *aasworld ).numfaces, i, j ); } //end else } //end for if ( face->numedges < 1 #ifdef NOTHREEVERTEXFACES || face->numedges < 3 #endif //NOTHREEVERTEXFACES ) { memset( &( *aasworld ).faces[( *aasworld ).numfaces], 0, sizeof( aas_face_t ) ); Log_Write( "AAS_GetFace: face %d was tiny\r\n", ( *aasworld ).numfaces ); return false; } //end if *facenum = ( *aasworld ).numfaces; ( *aasworld ).numfaces++; return true; } //end of the function AAS_GetFace //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== /* qboolean AAS_GetFace(winding_t *w, plane_t *p, int side, int *facenum) { aas_edgeindex_t edges[1024]; int planenum, numedges, i; int j, edgenum; qboolean foundplane, foundedges; aas_face_t *face; //face zero is a dummy, because of the face index with negative numbers if ((*aasworld).numfaces == 0) (*aasworld).numfaces = 1; foundplane = AAS_GetPlane(p->normal, p->dist, &planenum); foundedges = true; numedges = w->numpoints; for (i = 0; i < w->numpoints; i++) { if (i >= 1024) Error("AAS_GetFace: more than %d edges\n", 1024); foundedges &= AAS_GetEdge(w->p[i], w->p[(i+1 >= w->numpoints ? 0 : i+1)], &edges[i]); } //end for //FIXME: use portal number instead of a search //if the plane and all edges already existed if (foundplane && foundedges) { for (i = 0; i < (*aasworld).numfaces; i++) { face = &(*aasworld).faces[i]; if (planenum == face->planenum) { if (numedges == face->numedges) { for (j = 0; j < numedges; j++) { edgenum = abs((*aasworld).edgeindex[face->firstedge + j]); if (abs(edges[i]) != edgenum) break; } //end for if (j == numedges) { //jippy found the face *facenum = -i; return true; } //end if } //end if } //end if } //end for } //end if if ((*aasworld).numfaces >= max_aas.max_faces) { Error("AAS_MAX_FACES = %d", max_aas.max_faces); } //end if face = &(*aasworld).faces[(*aasworld).numfaces]; face->planenum = planenum; face->faceflags = 0; face->numedges = numedges; face->firstedge = (*aasworld).edgeindexsize; face->frontarea = 0; face->backarea = 0; for (i = 0; i < numedges; i++) { if ((*aasworld).edgeindexsize >= max_aas.max_edgeindexsize) { Error("AAS_MAX_EDGEINDEXSIZE = %d", max_aas.max_edgeindexsize); } //end if (*aasworld).edgeindex[(*aasworld).edgeindexsize++] = edges[i]; } //end for *facenum = (*aasworld).numfaces; (*aasworld).numfaces++; return false; } //end of the function AAS_GetFace*/ //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== void AAS_StoreAreaSettings( tmp_areasettings_t *tmpareasettings ) { aas_areasettings_t *areasettings; if ( ( *aasworld ).numareasettings == 0 ) { ( *aasworld ).numareasettings = 1; } areasettings = &( *aasworld ).areasettings[( *aasworld ).numareasettings++]; areasettings->areaflags = tmpareasettings->areaflags; areasettings->presencetype = tmpareasettings->presencetype; areasettings->contents = tmpareasettings->contents; areasettings->groundsteepness = tmpareasettings->groundsteepness; // Ridah if ( tmpareasettings->modelnum > AREACONTENTS_MAXMODELNUM ) { Log_Print( "WARNING: more than %d mover models\n", AREACONTENTS_MAXMODELNUM ); } areasettings->contents |= ( tmpareasettings->modelnum & AREACONTENTS_MAXMODELNUM ) << AREACONTENTS_MODELNUMSHIFT; } //end of the function AAS_StoreAreaSettings //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== int AAS_StoreArea( tmp_area_t *tmparea ) { int side, edgenum, i; plane_t *plane; tmp_face_t *tmpface; aas_area_t *aasarea; aas_edge_t *edge; aas_face_t *aasface; aas_faceindex_t aasfacenum; vec3_t facecenter; winding_t *w = NULL; // TTimo: init //when the area is merged go to the merged area //FIXME: this isn't necessary anymore because the tree // is refreshed after area merging while ( tmparea->mergedarea ) tmparea = tmparea->mergedarea; // if ( tmparea->invalid ) { Error( "AAS_StoreArea: tried to store invalid area" ); } //if there is an aas area already stored for this tmp area if ( tmparea->aasareanum ) { return -tmparea->aasareanum; } // if ( ( *aasworld ).numareas >= max_aas.max_areas ) { Error( "AAS_MAX_AREAS = %d", max_aas.max_areas ); } //end if //area zero is a dummy if ( ( *aasworld ).numareas == 0 ) { ( *aasworld ).numareas = 1; } //create an area from this leaf aasarea = &( *aasworld ).areas[( *aasworld ).numareas]; aasarea->areanum = ( *aasworld ).numareas; aasarea->numfaces = 0; aasarea->firstface = ( *aasworld ).faceindexsize; ClearBounds( aasarea->mins, aasarea->maxs ); VectorClear( aasarea->center ); // // Log_Write("tmparea %d became aasarea %d\r\n", tmparea->areanum, aasarea->areanum); //store the aas area number at the tmp area tmparea->aasareanum = aasarea->areanum; // for ( tmpface = tmparea->tmpfaces; tmpface; tmpface = tmpface->next[side] ) { side = tmpface->frontarea != tmparea; //if there's an aas face created for the tmp face already if ( tmpface->aasfacenum ) { //we're at the back of the face so use a negative index aasfacenum = -tmpface->aasfacenum; #ifdef DEBUG if ( tmpface->aasfacenum < 0 || tmpface->aasfacenum > max_aas.max_faces ) { Error( "AAS_CreateTree_r: face number out of range" ); } //end if #endif //DEBUG aasface = &( *aasworld ).faces[tmpface->aasfacenum]; aasface->backarea = aasarea->areanum; } //end if else { plane = &mapplanes[tmpface->planenum ^ side]; if ( side ) { w = tmpface->winding; tmpface->winding = ReverseWinding( tmpface->winding ); } //end if if ( !AAS_GetFace( tmpface->winding, plane, 0, &aasfacenum ) ) { continue; } if ( side ) { FreeWinding( tmpface->winding ); tmpface->winding = w; } //end if aasface = &( *aasworld ).faces[aasfacenum]; aasface->frontarea = aasarea->areanum; aasface->backarea = 0; aasface->faceflags = tmpface->faceflags; //set the face number at the tmp face tmpface->aasfacenum = aasfacenum; } //end else //add face points to the area bounds and //calculate the face 'center' VectorClear( facecenter ); for ( edgenum = 0; edgenum < aasface->numedges; edgenum++ ) { edge = &( *aasworld ).edges[abs( ( *aasworld ).edgeindex[aasface->firstedge + edgenum] )]; for ( i = 0; i < 2; i++ ) { AddPointToBounds( ( *aasworld ).vertexes[edge->v[i]], aasarea->mins, aasarea->maxs ); VectorAdd( ( *aasworld ).vertexes[edge->v[i]], facecenter, facecenter ); } //end for } //end for VectorScale( facecenter, 1.0 / ( aasface->numedges * 2.0 ), facecenter ); //add the face 'center' to the area 'center' VectorAdd( aasarea->center, facecenter, aasarea->center ); // if ( ( *aasworld ).faceindexsize >= max_aas.max_faceindexsize ) { Error( "AAS_MAX_FACEINDEXSIZE = %d", max_aas.max_faceindexsize ); } //end if ( *aasworld ).faceindex[( *aasworld ).faceindexsize++] = aasfacenum; aasarea->numfaces++; } //end for //if the area has no faces at all (return 0, = solid leaf) if ( !aasarea->numfaces ) { return 0; } // VectorScale( aasarea->center, 1.0 / aasarea->numfaces, aasarea->center ); //Log_Write("area %d center %f %f %f\r\n", (*aasworld).numareas, // aasarea->center[0], aasarea->center[1], aasarea->center[2]); //store the area settings AAS_StoreAreaSettings( tmparea->settings ); // //Log_Write("tmp area %d became aas area %d\r\n", tmpareanum, aasarea->areanum); qprintf( "\r%6d", aasarea->areanum ); // if ( ( *aasworld ).areasettings[aasarea->areanum].contents & AREACONTENTS_CLUSTERPORTAL ) { static int num; Log_Write( "***** area %d is a cluster portal %d\n", aasarea->areanum, num++ ); } //end if // ( *aasworld ).numareas++; return -( ( *aasworld ).numareas - 1 ); } //end of the function AAS_StoreArea //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== int AAS_StoreTree_r( tmp_node_t *tmpnode ) { int aasnodenum; plane_t *plane; aas_node_t *aasnode; //if it is a solid leaf if ( !tmpnode ) { return 0; } //negative so it's an area if ( tmpnode->tmparea ) { return AAS_StoreArea( tmpnode->tmparea ); } //it's another node //the first node is a dummy if ( ( *aasworld ).numnodes == 0 ) { ( *aasworld ).numnodes = 1; } if ( ( *aasworld ).numnodes >= max_aas.max_nodes ) { Error( "AAS_MAX_NODES = %d", max_aas.max_nodes ); } //end if aasnodenum = ( *aasworld ).numnodes; aasnode = &( *aasworld ).nodes[( *aasworld ).numnodes++]; plane = &mapplanes[tmpnode->planenum]; AAS_GetPlane( plane->normal, plane->dist, &aasnode->planenum ); aasnode->children[0] = AAS_StoreTree_r( tmpnode->children[0] ); aasnode->children[1] = AAS_StoreTree_r( tmpnode->children[1] ); return aasnodenum; } //end of the function AAS_StoreTree_r //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== void AAS_StoreBoundingBoxes( void ) { if ( cfg.numbboxes > max_aas.max_bboxes ) { Error( "more than %d bounding boxes", max_aas.max_bboxes ); } //end if ( *aasworld ).numbboxes = cfg.numbboxes; memcpy( ( *aasworld ).bboxes, cfg.bboxes, cfg.numbboxes * sizeof( aas_bbox_t ) ); } //end of the function AAS_StoreBoundingBoxes //=========================================================================== // // Parameter: - // Returns: - // Changes Globals: - //=========================================================================== void AAS_StoreFile( char *filename ) { AAS_AllocMaxAAS(); Log_Write( "AAS_StoreFile\r\n" ); // AAS_StoreBoundingBoxes(); // qprintf( "%6d areas stored", 0 ); //start with node 1 because node zero is a dummy AAS_StoreTree_r( tmpaasworld.nodes ); qprintf( "\n" ); Log_Write( "%6d areas stored\r\n", ( *aasworld ).numareas ); ( *aasworld ).loaded = true; } //end of the function AAS_StoreFile