aas_store.c

quakeIII源码这个不用我多说吧

				&& fabs(aasworld.vertexes[vn][2] - vert[2]) < VERTEX_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;