be_aas_sample.c

quakeIII源码这个不用我多说吧

	aas_edge_t *edge;
#ifdef AAS_SAMPLE_DEBUG
	int lastvertex = 0;
#endif //AAS_SAMPLE_DEBUG

	if (!aasworld.loaded) return qfalse;

	for (i = 0; i < face->numedges; i++)
	{
		edgenum = aasworld.edgeindex[face->firstedge + i];
		edge = &aasworld.edges[abs(edgenum)];
		//get the first vertex of the edge
		firstvertex = edgenum < 0;
		VectorCopy(aasworld.vertexes[edge->v[firstvertex]], v0);
		//edge vector
		VectorSubtract(aasworld.vertexes[edge->v[!firstvertex]], v0, edgevec);
		//
#ifdef AAS_SAMPLE_DEBUG
		if (lastvertex && lastvertex != edge->v[firstvertex])
		{
			botimport.Print(PRT_MESSAGE, "winding not counter clockwise\n");
		} //end if
		lastvertex = edge->v[!firstvertex];
#endif //AAS_SAMPLE_DEBUG
		//vector from first edge point to point possible in face
		VectorSubtract(point, v0, pointvec);
		//get a vector pointing inside the face orthogonal to both the
		//edge vector and the normal vector of the plane the face is in
		//this vector defines a plane through the origin (first vertex of
		//edge) and through both the edge vector and the normal vector
		//of the plane
		AAS_OrthogonalToVectors(edgevec, pnormal, sepnormal);
		//check on wich side of the above plane the point is
		//this is done by checking the sign of the dot product of the
		//vector orthogonal vector from above and the vector from the
		//origin (first vertex of edge) to the point 
		//if the dotproduct is smaller than zero the point is outside the face
		if (DotProduct(pointvec, sepnormal) < -epsilon) return qfalse;
	} //end for
	return qtrue;
} //end of the function AAS_InsideFace
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
qboolean AAS_PointInsideFace(int facenum, vec3_t point, float epsilon)
{
	int i, firstvertex, edgenum;
	vec_t *v1, *v2;
	vec3_t edgevec, pointvec, sepnormal;
	aas_edge_t *edge;
	aas_plane_t *plane;
	aas_face_t *face;

	if (!aasworld.loaded) return qfalse;

	face = &aasworld.faces[facenum];
	plane = &aasworld.planes[face->planenum];
	//
	for (i = 0; i < face->numedges; i++)
	{
		edgenum = aasworld.edgeindex[face->firstedge + i];
		edge = &aasworld.edges[abs(edgenum)];
		//get the first vertex of the edge
		firstvertex = edgenum < 0;
		v1 = aasworld.vertexes[edge->v[firstvertex]];
		v2 = aasworld.vertexes[edge->v[!firstvertex]];
		//edge vector
		VectorSubtract(v2, v1, edgevec);
		//vector from first edge point to point possible in face
		VectorSubtract(point, v1, pointvec);
		//
		CrossProduct(edgevec, plane->normal, sepnormal);
		//
		if (DotProduct(pointvec, sepnormal) < -epsilon) return qfalse;
	} //end for
	return qtrue;
} //end of the function AAS_PointInsideFace
//===========================================================================
// returns the ground face the given point is above in the given area
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
aas_face_t *AAS_AreaGroundFace(int areanum, vec3_t point)
{
	int i, facenum;
	vec3_t up = {0, 0, 1};
	vec3_t normal;
	aas_area_t *area;
	aas_face_t *face;

	if (!aasworld.loaded) return NULL;

	area = &aasworld.areas[areanum];
	for (i = 0; i < area->numfaces; i++)
	{
		facenum = aasworld.faceindex[area->firstface + i];
		face = &aasworld.faces[abs(facenum)];
		//if this is a ground face
		if (face->faceflags & FACE_GROUND)
		{
			//get the up or down normal
			if (aasworld.planes[face->planenum].normal[2] < 0) VectorNegate(up, normal);
			else VectorCopy(up, normal);
			//check if the point is in the face
			if (AAS_InsideFace(face, normal, point, 0.01f)) return face;
		} //end if
	} //end for
	return NULL;
} //end of the function AAS_AreaGroundFace
//===========================================================================
// returns the face the trace end position is situated in
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_FacePlane(int facenum, vec3_t normal, float *dist)
{
	aas_plane_t *plane;

	plane = &aasworld.planes[aasworld.faces[facenum].planenum];
	VectorCopy(plane->normal, normal);
	*dist = plane->dist;
} //end of the function AAS_FacePlane
//===========================================================================
// returns the face the trace end position is situated in
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
aas_face_t *AAS_TraceEndFace(aas_trace_t *trace)
{
	int i, facenum;
	aas_area_t *area;
	aas_face_t *face, *firstface = NULL;

	if (!aasworld.loaded) return NULL;

	//if started in solid no face was hit
	if (trace->startsolid) return NULL;
	//trace->lastarea is the last area the trace was in
	area = &aasworld.areas[trace->lastarea];
	//check which face the trace.endpos was in
	for (i = 0; i < area->numfaces; i++)
	{
		facenum = aasworld.faceindex[area->firstface + i];
		face = &aasworld.faces[abs(facenum)];
		//if the face is in the same plane as the trace end point
		if ((face->planenum & ~1) == (trace->planenum & ~1))
		{
			//firstface is used for optimization, if theres only one
			//face in the plane then it has to be the good one
			//if there are more faces in the same plane then always
			//check the one with the fewest edges first
/*			if (firstface)
			{
				if (firstface->numedges < face->numedges)
				{
					if (AAS_InsideFace(firstface,
						aasworld.planes[face->planenum].normal, trace->endpos))
					{
						return firstface;
					} //end if
					firstface = face;
				} //end if
				else
				{
					if (AAS_InsideFace(face,
						aasworld.planes[face->planenum].normal, trace->endpos))
					{
						return face;
					} //end if
				} //end else
			} //end if
			else
			{
				firstface = face;
			} //end else*/
			if (AAS_InsideFace(face,
						aasworld.planes[face->planenum].normal, trace->endpos, 0.01f)) return face;
		} //end if
	} //end for
	return firstface;
} //end of the function AAS_TraceEndFace
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_BoxOnPlaneSide2(vec3_t absmins, vec3_t absmaxs, aas_plane_t *p)
{
	int i, sides;
	float dist1, dist2;
	vec3_t corners[2];

	for (i = 0; i < 3; i++)
	{
		if (p->normal[i] < 0)
		{
			corners[0][i] = absmins[i];
			corners[1][i] = absmaxs[i];
		} //end if
		else
		{
			corners[1][i] = absmins[i];
			corners[0][i] = absmaxs[i];
		} //end else
	} //end for
	dist1 = DotProduct(p->normal, corners[0]) - p->dist;
	dist2 = DotProduct(p->normal, corners[1]) - p->dist;
	sides = 0;
	if (dist1 >= 0) sides = 1;
	if (dist2 < 0) sides |= 2;

	return sides;
} //end of the function AAS_BoxOnPlaneSide2
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
//int AAS_BoxOnPlaneSide(vec3_t absmins, vec3_t absmaxs, aas_plane_t *p)
#define AAS_BoxOnPlaneSide(absmins, absmaxs, p) (\
	( (p)->type < 3) ?\
	(\
		( (p)->dist <= (absmins)[(p)->type]) ?\
		(\
			1\
		)\
		:\
		(\
			( (p)->dist >= (absmaxs)[(p)->type]) ?\
			(\
				2\
			)\
			:\
			(\
				3\
			)\
		)\
	)\
	:\
	(\
		AAS_BoxOnPlaneSide2((absmins), (absmaxs), (p))\
	)\
) //end of the function AAS_BoxOnPlaneSide
//===========================================================================
// remove the links to this entity from all areas
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void AAS_UnlinkFromAreas(aas_link_t *areas)
{
	aas_link_t *link, *nextlink;

	for (link = areas; link; link = nextlink)
	{
		//next area the entity is linked in
		nextlink = link->next_area;
		//remove the entity from the linked list of this area
		if (link->prev_ent) link->prev_ent->next_ent = link->next_ent;
		else aasworld.arealinkedentities[link->areanum] = link->next_ent;
		if (link->next_ent) link->next_ent->prev_ent = link->prev_ent;
		//deallocate the link structure
		AAS_DeAllocAASLink(link);
	} //end for
} //end of the function AAS_UnlinkFromAreas
//===========================================================================
// link the entity to the areas the bounding box is totally or partly
// situated in. This is done with recursion down the tree using the
// bounding box to test for plane sides
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================

typedef struct
{
	int nodenum;		//node found after splitting
} aas_linkstack_t;

aas_link_t *AAS_AASLinkEntity(vec3_t absmins, vec3_t absmaxs, int entnum)
{
	int side, nodenum;
	aas_linkstack_t linkstack[128];
	aas_linkstack_t *lstack_p;
	aas_node_t *aasnode;
	aas_plane_t *plane;
	aas_link_t *link, *areas;

	if (!aasworld.loaded)
	{
		botimport.Print(PRT_ERROR, "AAS_LinkEntity: aas not loaded\n");
		return NULL;
	} //end if

	areas = NULL;
	//
	lstack_p = linkstack;
	//we start with the whole line on the stack
	//start with node 1 because node zero is a dummy used for solid leafs
	lstack_p->nodenum = 1;		//starting at the root of the tree
	lstack_p++;
	
	while (1)
	{
		//pop up the stack
		lstack_p--;
		//if the trace stack is empty (ended up with a piece of the
		//line to be traced in an area)
		if (lstack_p < linkstack) break;
		//number of the current node to test the line against
		nodenum = lstack_p->nodenum;
		//if it is an area
		if (nodenum < 0)
		{
			//NOTE: the entity might have already been linked into this area
			// because several node children can point to the same area
			for (link = aasworld.arealinkedentities[-nodenum]; link; link = link->next_ent)
			{
				if (link->entnum == entnum) break;
			} //end for
			if (link) continue;
			//
			link = AAS_AllocAASLink();
			if (!link) return areas;
			link->entnum = entnum;
			link->areanum = -nodenum;
			//put the link into the double linked area list of the entity
			link->prev_area = NULL;
			link->next_area = areas;
			if (areas) areas->prev_area = link;
			areas = link;
			//put the link into the double linked entity list of the area
			link->prev_ent = NULL;
			link->next_ent = aasworld.arealinkedentities[-nodenum];
			if (aasworld.arealinkedentities[-nodenum])
					aasworld.arealinkedentities[-nodenum]->prev_ent = link;
			aasworld.arealinkedentities[-nodenum] = link;
			//
			continue;
		} //end if
		//if solid leaf
		if (!nodenum) continue;
		//the node to test against
		aasnode = &aasworld.nodes[nodenum];
		//the current node plane
		plane = &aasworld.planes[aasnode->planenum];
		//get the side(s) the box is situated relative to the plane
		side = AAS_BoxOnPlaneSide2(absmins, absmaxs, plane);
		//if on the front side of the node
		if (side & 1)
		{
			lstack_p->nodenum = aasnode->children[0];
			lstack_p++;
		} //end if
		if (lstack_p >= &linkstack[127])
		{
			botimport.Print(PRT_ERROR, "AAS_LinkEntity: stack overflow\n");
			break;
		} //end if
		//if on the back side of the node
		if (side & 2)
		{
			lstack_p->nodenum = aasnode->children[1];
			lstack_p++;
		} //end if
		if (lstack_p >= &linkstack[127])
		{
			botimport.Print(PRT_ERROR, "AAS_LinkEntity: stack overflow\n");
			break;
		} //end if
	} //end while
	return areas;
} //end of the function AAS_AASLinkEntity
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
aas_link_t *AAS_LinkEntityClientBBox(vec3_t absmins, vec3_t absmaxs, int entnum, int presencetype)
{
	vec3_t mins, maxs;
	vec3_t newabsmins, newabsmaxs;

	AAS_PresenceTypeBoundingBox(presencetype, mins, maxs);
	VectorSubtract(absmins, maxs, newabsmins);
	VectorSubtract(absmaxs, mins, newabsmaxs);
	//relink the entity
	return AAS_AASLinkEntity(newabsmins, newabsmaxs, entnum);
} //end of the function AAS_LinkEntityClientBBox
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_BBoxAreas(vec3_t absmins, vec3_t absmaxs, int *areas, int maxareas)
{
	aas_link_t *linkedareas, *link;
	int num;

	linkedareas = AAS_AASLinkEntity(absmins, absmaxs, -1);
	num = 0;
	for (link = linkedareas; link; link = link->next_area)
	{
		areas[num] = link->areanum;
		num++;
		if (num >= maxareas)
			break;
	} //end for
	AAS_UnlinkFromAreas(linkedareas);
	return num;
} //end of the function AAS_BBoxAreas
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int AAS_AreaInfo( int areanum, aas_areainfo_t *info )
{
	aas_areasettings_t *settings;
	if (!info)
		return 0;
	if (areanum <= 0 || areanum >= aasworld.numareas)
	{
		botimport.Print(PRT_ERROR, "AAS_AreaInfo: areanum %d out of range\n", areanum);
		return 0;
	} //end if
	settings = &aasworld.areasettings[areanum];
	info->cluster = settings->cluster;
	info->contents = settings->contents;
	info->flags = settings->areaflags;
	info->presencetype = settings->presencetype;
	VectorCopy(aasworld.areas[areanum].mins, info->mins);
	VectorCopy(aasworld.areas[areanum].maxs, info->maxs);
	VectorCopy(aasworld.areas[areanum].center, info->center);
	return sizeof(aas_areainfo_t);
} //end of the function AAS_AreaInfo
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
aas_plane_t *AAS_PlaneFromNum(int planenum)
{
	if (!aasworld.loaded) return 0;

	return &aasworld.planes[planenum];
} //end of the function AAS_PlaneFromNum