Quake III Arena: code/bspc/aas_store.c File Reference

00434 {
00435     int hash;
00436     aas_edge_t *edge;
00437 
00438     edge = &aasworld.edges[edgenum];
00439 
00440     hash = AAS_HashEdge(edge->v[0], edge->v[1]);
00441 
00442     aas_edgechain[edgenum] = aas_hashedges[hash];
00443     aas_hashedges[hash] = edgenum;
00444 } //end of the function AAS_AddEdgeToHash

00587 {
00588     int hash;
00589     aas_plane_t *plane;
00590 
00591     plane = &aasworld.planes[planenum];
00592 
00593     hash = (int)fabs(plane->dist) / 8;
00594     hash &= (PLANE_HASH_SIZE-1);
00595 
00596     aas_planechain[planenum] = aas_hashplanes[hash];
00597     aas_hashplanes[hash] = planenum;
00598 } //end of the function AAS_AddPlaneToHash

00145 {
00146     int i;
00147 
00148     AAS_InitMaxAAS();
00149     //bounding boxes
00150     aasworld.numbboxes = 0;
00151     aasworld.bboxes = (aas_bbox_t *) GetClearedMemory(max_aas.max_bboxes * sizeof(aas_bbox_t));
00152     allocatedaasmem += max_aas.max_bboxes * sizeof(aas_bbox_t);
00153     //vertexes
00154     aasworld.numvertexes = 0;
00155     aasworld.vertexes = (aas_vertex_t *) GetClearedMemory(max_aas.max_vertexes * sizeof(aas_vertex_t));
00156     allocatedaasmem += max_aas.max_vertexes * sizeof(aas_vertex_t);
00157     //planes
00158     aasworld.numplanes = 0;
00159     aasworld.planes = (aas_plane_t *) GetClearedMemory(max_aas.max_planes * sizeof(aas_plane_t));
00160     allocatedaasmem += max_aas.max_planes * sizeof(aas_plane_t);
00161     //edges
00162     aasworld.numedges = 0;
00163     aasworld.edges = (aas_edge_t *) GetClearedMemory(max_aas.max_edges * sizeof(aas_edge_t));
00164     allocatedaasmem += max_aas.max_edges * sizeof(aas_edge_t);
00165     //edge index
00166     aasworld.edgeindexsize = 0;
00167     aasworld.edgeindex = (aas_edgeindex_t *) GetClearedMemory(max_aas.max_edgeindexsize * sizeof(aas_edgeindex_t));
00168     allocatedaasmem += max_aas.max_edgeindexsize * sizeof(aas_edgeindex_t);
00169     //faces
00170     aasworld.numfaces = 0;
00171     aasworld.faces = (aas_face_t *) GetClearedMemory(max_aas.max_faces * sizeof(aas_face_t));
00172     allocatedaasmem += max_aas.max_faces * sizeof(aas_face_t);
00173     //face index
00174     aasworld.faceindexsize = 0;
00175     aasworld.faceindex = (aas_faceindex_t *) GetClearedMemory(max_aas.max_faceindexsize * sizeof(aas_faceindex_t));
00176     allocatedaasmem += max_aas.max_faceindexsize * sizeof(aas_faceindex_t);
00177     //convex areas
00178     aasworld.numareas = 0;
00179     aasworld.areas = (aas_area_t *) GetClearedMemory(max_aas.max_areas * sizeof(aas_area_t));
00180     allocatedaasmem += max_aas.max_areas * sizeof(aas_area_t);
00181     //convex area settings
00182     aasworld.numareasettings = 0;
00183     aasworld.areasettings = (aas_areasettings_t *) GetClearedMemory(max_aas.max_areasettings * sizeof(aas_areasettings_t));
00184     allocatedaasmem += max_aas.max_areasettings * sizeof(aas_areasettings_t);
00185     //reachablity list
00186     aasworld.reachabilitysize = 0;
00187     aasworld.reachability = (aas_reachability_t *) GetClearedMemory(max_aas.max_reachabilitysize * sizeof(aas_reachability_t));
00188     allocatedaasmem += max_aas.max_reachabilitysize * sizeof(aas_reachability_t);
00189     //nodes of the bsp tree
00190     aasworld.numnodes = 0;
00191     aasworld.nodes = (aas_node_t *) GetClearedMemory(max_aas.max_nodes * sizeof(aas_node_t));
00192     allocatedaasmem += max_aas.max_nodes * sizeof(aas_node_t);
00193     //cluster portals
00194     aasworld.numportals = 0;
00195     aasworld.portals = (aas_portal_t *) GetClearedMemory(max_aas.max_portals * sizeof(aas_portal_t));
00196     allocatedaasmem += max_aas.max_portals * sizeof(aas_portal_t);
00197     //cluster portal index
00198     aasworld.portalindexsize = 0;
00199     aasworld.portalindex = (aas_portalindex_t *) GetClearedMemory(max_aas.max_portalindexsize * sizeof(aas_portalindex_t));
00200     allocatedaasmem += max_aas.max_portalindexsize * sizeof(aas_portalindex_t);
00201     //cluster
00202     aasworld.numclusters = 0;
00203     aasworld.clusters = (aas_cluster_t *) GetClearedMemory(max_aas.max_clusters * sizeof(aas_cluster_t));
00204     allocatedaasmem += max_aas.max_clusters * sizeof(aas_cluster_t);
00205     //
00206     Log_Print("allocated ");
00207     PrintMemorySize(allocatedaasmem);
00208     Log_Print(" of AAS memory\n");
00209     //reset the has stuff
00210     aas_vertexchain = (int *) GetClearedMemory(max_aas.max_vertexes * sizeof(int));
00211     aas_planechain = (int *) GetClearedMemory(max_aas.max_planes * sizeof(int));
00212     aas_edgechain = (int *) GetClearedMemory(max_aas.max_edges * sizeof(int));
00213     //
00214     for (i = 0; i < max_aas.max_vertexes; i++) aas_vertexchain[i] = -1;
00215     for (i = 0; i < VERTEX_HASH_SIZE * VERTEX_HASH_SIZE; i++) aas_hashverts[i] = -1;
00216     //
00217     for (i = 0; i < max_aas.max_planes; i++) aas_planechain[i] = -1;
00218     for (i = 0; i < PLANE_HASH_SIZE; i++) aas_hashplanes[i] = -1;
00219     //
00220     for (i = 0; i < max_aas.max_edges; i++) aas_edgechain[i] = -1;
00221     for (i = 0; i < EDGE_HASH_SIZE; i++) aas_hashedges[i] = -1;
00222 } //end of the function AAS_AllocMaxAAS

00093 {
00094     if (!tmpnode) return 0;
00095     return AAS_CountTmpNodes(tmpnode->children[0]) +
00096                 AAS_CountTmpNodes(tmpnode->children[1]) + 1;
00097 } //end of the function AAS_CountTmpNodes

00452 {
00453     int e, hash;
00454     aas_edge_t *edge;
00455 
00456     hash = AAS_HashEdge(v1num, v2num);
00457     for (e = aas_hashedges[hash]; e >= 0; e = aas_edgechain[e])
00458     {
00459         edge = &aasworld.edges[e];
00460         if (edge->v[0] == v1num)
00461         {
00462             if (edge->v[1] == v2num)
00463             {
00464                 *edgenum = e;
00465                 return true;
00466             } //end if
00467         } //end if
00468         else if (edge->v[1] == v1num)
00469         {
00470             if (edge->v[0] == v2num)
00471             {
00472                 //negative for a reversed edge
00473                 *edgenum = -e;
00474                 return true;
00475             } //end if
00476         } //end else
00477     } //end for
00478     return false;
00479 } //end of the function AAS_FindHashedPlane

00655 {
00656     int i, p;
00657     aas_plane_t *plane;
00658     int hash, h;
00659 
00660     hash = (int)fabs(dist) / 8;
00661     hash &= (PLANE_HASH_SIZE-1);
00662 
00663     //search the border bins as well
00664     for (i = -1; i <= 1; i++)
00665     {
00666         h = (hash+i)&(PLANE_HASH_SIZE-1);
00667         for (p = aas_hashplanes[h]; p >= 0; p = aas_planechain[p])
00668         {
00669             plane = &aasworld.planes[p];
00670             if (AAS_PlaneEqual(normal, dist, p))
00671             {
00672                 *planenum = p;
00673                 return true;
00674             } //end if
00675         } //end for
00676     } //end for
00677     return false;
00678 } //end of the function AAS_FindHashedPlane

00635 {
00636     int i;
00637 
00638     for (i = 0; i < aasworld.numplanes; i++)
00639     {
00640         if (AAS_PlaneEqual(normal, dist, i))
00641         {
00642             *planenum = i;
00643             return true;
00644         } //end if
00645     } //end for
00646     return false;
00647 } //end of the function AAS_FindPlane

00230 {
00231     //bounding boxes
00232     if (aasworld.bboxes) FreeMemory(aasworld.bboxes);
00233     aasworld.bboxes = NULL;
00234     aasworld.numbboxes = 0;
00235     //vertexes
00236     if (aasworld.vertexes) FreeMemory(aasworld.vertexes);
00237     aasworld.vertexes = NULL;
00238     aasworld.numvertexes = 0;
00239     //planes
00240     if (aasworld.planes) FreeMemory(aasworld.planes);
00241     aasworld.planes = NULL;
00242     aasworld.numplanes = 0;
00243     //edges
00244     if (aasworld.edges) FreeMemory(aasworld.edges);
00245     aasworld.edges = NULL;
00246     aasworld.numedges = 0;
00247     //edge index
00248     if (aasworld.edgeindex) FreeMemory(aasworld.edgeindex);
00249     aasworld.edgeindex = NULL;
00250     aasworld.edgeindexsize = 0;
00251     //faces
00252     if (aasworld.faces) FreeMemory(aasworld.faces);
00253     aasworld.faces = NULL;
00254     aasworld.numfaces = 0;
00255     //face index
00256     if (aasworld.faceindex) FreeMemory(aasworld.faceindex);
00257     aasworld.faceindex = NULL;
00258     aasworld.faceindexsize = 0;
00259     //convex areas
00260     if (aasworld.areas) FreeMemory(aasworld.areas);
00261     aasworld.areas = NULL;
00262     aasworld.numareas = 0;
00263     //convex area settings
00264     if (aasworld.areasettings) FreeMemory(aasworld.areasettings);
00265     aasworld.areasettings = NULL;
00266     aasworld.numareasettings = 0;
00267     //reachablity list
00268     if (aasworld.reachability) FreeMemory(aasworld.reachability);
00269     aasworld.reachability = NULL;
00270     aasworld.reachabilitysize = 0;
00271     //nodes of the bsp tree
00272     if (aasworld.nodes) FreeMemory(aasworld.nodes);
00273     aasworld.nodes = NULL;
00274     aasworld.numnodes = 0;
00275     //cluster portals
00276     if (aasworld.portals) FreeMemory(aasworld.portals);
00277     aasworld.portals = NULL;
00278     aasworld.numportals = 0;
00279     //cluster portal index
00280     if (aasworld.portalindex) FreeMemory(aasworld.portalindex);
00281     aasworld.portalindex = NULL;
00282     aasworld.portalindexsize = 0;
00283     //clusters
00284     if (aasworld.clusters) FreeMemory(aasworld.clusters);
00285     aasworld.clusters = NULL;
00286     aasworld.numclusters = 0;
00287     
00288     Log_Print("freed ");
00289     PrintMemorySize(allocatedaasmem);
00290     Log_Print(" of AAS memory\n");
00291     allocatedaasmem = 0;
00292     //
00293     if (aas_vertexchain) FreeMemory(aas_vertexchain);
00294     aas_vertexchain = NULL;
00295     if (aas_planechain) FreeMemory(aas_planechain);
00296     aas_planechain = NULL;
00297     if (aas_edgechain) FreeMemory(aas_edgechain);
00298     aas_edgechain = NULL;
00299 } //end of the function AAS_FreeMaxAAS

00491 {
00492     int v1num, v2num;
00493     qboolean found;
00494 
00495     //the first edge is a dummy
00496     if (aasworld.numedges == 0) aasworld.numedges = 1;
00497 
00498     found = AAS_GetVertex(v1, &v1num);
00499     found &= AAS_GetVertex(v2, &v2num);
00500     //if one of the vertexes was outside the valid range
00501     if (v1num == -1 || v2num == -1)
00502     {
00503         *edgenum = 0;
00504         return true;
00505     } //end if
00506     //if both vertexes are the same or snapped onto each other
00507     if (v1num == v2num)
00508     {
00509         *edgenum = 0;
00510         return true;
00511     } //end if
00512     //if both vertexes where already stored
00513     if (found)
00514     {
00515 #ifdef EDGE_HASHING
00516         if (AAS_FindHashedEdge(v1num, v2num, edgenum)) return true;
00517 #else
00518         int i;
00519         for (i = 1; i < aasworld.numedges; i++)
00520         {
00521             if (aasworld.edges[i].v[0] == v1num)
00522             {
00523                 if (aasworld.edges[i].v[1] == v2num)
00524                 {
00525                     *edgenum = i;
00526                     return true;
00527                 } //end if
00528             } //end if
00529             else if (aasworld.edges[i].v[1] == v1num)
00530             {
00531                 if (aasworld.edges[i].v[0] == v2num)
00532                 {
00533                     //negative for a reversed edge
00534                     *edgenum = -i;
00535                     return true;
00536                 } //end if
00537             } //end else
00538         } //end for
00539 #endif //EDGE_HASHING
00540     } //end if
00541     if (aasworld.numedges >= max_aas.max_edges)
00542     {
00543         Error("AAS_MAX_EDGES = %d", max_aas.max_edges);
00544     } //end if
00545     aasworld.edges[aasworld.numedges].v[0] = v1num;
00546     aasworld.edges[aasworld.numedges].v[1] = v2num;
00547     *edgenum = aasworld.numedges;
00548 #ifdef EDGE_HASHING
00549     AAS_AddEdgeToHash(*edgenum);
00550 #endif //EDGE_HASHING
00551     aasworld.numedges++;
00552     return false;
00553 } //end of the function AAS_GetEdge

00747 {
00748     int edgenum, i, j;
00749     aas_face_t *face;
00750 
00751     //face zero is a dummy, because of the face index with negative numbers
00752     if (aasworld.numfaces == 0) aasworld.numfaces = 1;
00753 
00754     if (aasworld.numfaces >= max_aas.max_faces)
00755     {
00756         Error("AAS_MAX_FACES = %d", max_aas.max_faces);
00757     } //end if
00758     face = &aasworld.faces[aasworld.numfaces];
00759     AAS_GetPlane(p->normal, p->dist, &face->planenum);
00760     face->faceflags = 0;
00761     face->firstedge = aasworld.edgeindexsize;
00762     face->frontarea = 0;
00763     face->backarea = 0;
00764     face->numedges = 0;
00765     for (i = 0; i < w->numpoints; i++)
00766     {
00767         if (aasworld.edgeindexsize >= max_aas.max_edgeindexsize)
00768         {
00769             Error("AAS_MAX_EDGEINDEXSIZE = %d", max_aas.max_edgeindexsize);
00770         } //end if
00771         j = (i+1) % w->numpoints;
00772         AAS_GetEdge(w->p[i], w->p[j], &edgenum);
00773         //if the edge wasn't degenerate
00774         if (edgenum)
00775         {
00776             aasworld.edgeindex[aasworld.edgeindexsize++] = edgenum;
00777             face->numedges++;
00778         } //end if
00779         else if (verbose)
00780         {
00781             Log_Write("AAS_GetFace: face %d had degenerate edge %d-%d\r\n",
00782                                                         aasworld.numfaces, i, j);
00783         } //end else
00784     } //end for
00785     if (face->numedges < 1
00786 #ifdef NOTHREEVERTEXFACES
00787         || face->numedges < 3
00788 #endif //NOTHREEVERTEXFACES
00789         )
00790     {
00791         memset(&aasworld.faces[aasworld.numfaces], 0, sizeof(aas_face_t));
00792         Log_Write("AAS_GetFace: face %d was tiny\r\n", aasworld.numfaces);
00793         return false;
00794     } //end if
00795     *facenum = aasworld.numfaces;
00796     aasworld.numfaces++;
00797     return true;
00798 } //end of the function AAS_GetFace

00686 {
00687     aas_plane_t *plane, temp;
00688 
00689     //if (AAS_FindPlane(normal, dist, planenum)) return true;
00690     if (AAS_FindHashedPlane(normal, dist, planenum)) return true;
00691 
00692     if (aasworld.numplanes >= max_aas.max_planes-1)
00693     {
00694         Error("AAS_MAX_PLANES = %d", max_aas.max_planes);
00695     } //end if
00696 
00697 #ifdef STOREPLANESDOUBLE
00698     plane = &aasworld.planes[aasworld.numplanes];
00699     VectorCopy(normal, plane->normal);
00700     plane->dist = dist;
00701     plane->type = (plane+1)->type = PlaneTypeForNormal(plane->normal);
00702 
00703     VectorCopy(normal, (plane+1)->normal);
00704     VectorNegate((plane+1)->normal, (plane+1)->normal);
00705     (plane+1)->dist = -dist;
00706 
00707     aasworld.numplanes += 2;
00708 
00709     //allways put axial planes facing positive first
00710     if (plane->type < 3)
00711     {
00712         if (plane->normal[0] < 0 || plane->normal[1] < 0 || plane->normal[2] < 0)
00713         {
00714             // flip order
00715             temp = *plane;
00716             *plane = *(plane+1);
00717             *(plane+1) = temp;
00718             *planenum = aasworld.numplanes - 1;
00719             return false;
00720         } //end if
00721     } //end if
00722     *planenum = aasworld.numplanes - 2;
00723     //add the planes to the hash
00724     AAS_AddPlaneToHash(aasworld.numplanes - 1);
00725     AAS_AddPlaneToHash(aasworld.numplanes - 2);
00726     return false;
00727 #else
00728     plane = &aasworld.planes[aasworld.numplanes];
00729     VectorCopy(normal, plane->normal);
00730     plane->dist = dist;
00731     plane->type = AAS_PlaneTypeForNormal(normal);
00732 
00733     *planenum = aasworld.numplanes;
00734     aasworld.numplanes++;
00735     //add the plane to the hash
00736     AAS_AddPlaneToHash(aasworld.numplanes - 1);
00737     return false;
00738 #endif //STOREPLANESDOUBLE
00739 } //end of the function AAS_GetPlane

00332 {
00333     int i;
00334 #ifndef VERTEX_HASHING
00335     float diff;
00336 #endif //VERTEX_HASHING
00337 
00338 #ifdef VERTEX_HASHING
00339     int h, vn;
00340     vec3_t vert;
00341     
00342     for (i = 0; i < 3; i++)
00343     {
00344         if ( fabs(v[i] - Q_rint(v[i])) < INTEGRAL_EPSILON)
00345             vert[i] = Q_rint(v[i]);
00346         else
00347             vert[i] = v[i];
00348     } //end for
00349 
00350     h = AAS_HashVec(vert);
00351     //if the vertex was outside the valid range
00352     if (h == -1)
00353     {
00354         *vnum = -1;
00355         return true;
00356     } //end if
00357 
00358     for (vn = aas_hashverts[h]; vn >= 0; vn = aas_vertexchain[vn])
00359     {
00360         if (fabs(aasworld.vertexes[vn][0] - vert[0]) < VERTEX_EPSILON
00361                 && fabs(aasworld.vertexes[vn][1] - vert[1]) < VERTEX_EPSILON
00362                 && fabs(aasworld.vertexes[vn][2] - vert[2]) < VERTEX_EPSILON)
00363         {
00364             *vnum


Data Structures
struct	max_aas_s
Defines
#define	DIST_EPSILON 0.05
#define	EDGE_HASH_SIZE 1024
#define	EDGE_HASHING
#define	INTEGRAL_EPSILON 0.01
#define	NORMAL_EPSILON 0.0001
#define	PLANE_HASH_SIZE 1024
#define	PLANE_HASHING
#define	STOREPLANESDOUBLE
#define	VERTEX_EPSILON 0.1
#define	VERTEX_HASH_SHIFT 7
#define	VERTEX_HASH_SIZE ((MAX_MAP_BOUNDS>>(VERTEX_HASH_SHIFT-1))+1)
#define	VERTEX_HASHING
Typedefs
typedef max_aas_s	max_aas_t
Functions
void	AAS_AddEdgeToHash (int edgenum)
void	AAS_AddPlaneToHash (int planenum)
void	AAS_AllocMaxAAS (void)
int	AAS_CountTmpNodes (tmp_node_t *tmpnode)
qboolean	AAS_FindHashedEdge (int v1num, int v2num, int *edgenum)
qboolean	AAS_FindHashedPlane (vec3_t normal, float dist, int *planenum)
qboolean	AAS_FindPlane (vec3_t normal, float dist, int *planenum)
void	AAS_FreeMaxAAS (void)
qboolean	AAS_GetEdge (vec3_t v1, vec3_t v2, int *edgenum)
qboolean	AAS_GetFace (winding_t w, plane_t p, int side, int *facenum)
qboolean	AAS_GetPlane (vec3_t normal, vec_t dist, int *planenum)
qboolean	AAS_GetVertex (vec3_t v, int *vnum)
unsigned	AAS_HashEdge (int v1, int v2)
unsigned	AAS_HashVec (vec3_t vec)
void	AAS_InitMaxAAS (void)
int	AAS_PlaneEqual (vec3_t normal, float dist, int planenum)
int	AAS_PlaneTypeForNormal (vec3_t normal)
int	AAS_StoreArea (tmp_area_t *tmparea)
void	AAS_StoreAreaSettings (tmp_areasettings_t *tmpareasettings)
void	AAS_StoreBoundingBoxes (void)
void	AAS_StoreFile (char *filename)
int	AAS_StoreTree_r (tmp_node_t *tmpnode)
Variables
int *	aas_edgechain
int	aas_hashedges [EDGE_HASH_SIZE]
int	aas_hashplanes [PLANE_HASH_SIZE]
int	aas_hashverts [VERTEX_HASH_SIZE *VERTEX_HASH_SIZE]
int *	aas_planechain
int *	aas_vertexchain
aas_t	aasworld
int	allocatedaasmem = 0
int	groundfacesonly = false
max_aas_t	max_aas

aas_store.c File Reference

Data Structures

Defines

Typedefs

Functions

Variables

Define Documentation

Typedef Documentation

Function Documentation