portals.c

quakeIII源码这个不用我多说吧

		} //end else
		ChopWindingInPlace (&w, normal, dist, 0.1);
	} //end for

	if (!w)
	{
		return;
	} //end if

	if (WindingIsTiny (w))
	{
		c_tinyportals++;
		FreeWinding(w);
		return;
	} //end if

#ifdef DEBUG
/* //NOTE: don't use this winding ok check
	// all the invalid windings only have a degenerate edge
	if (WindingError(w))
	{
		Log_Print("MakeNodePortal: %s\n", WindingErrorString());
		FreeWinding(w);
		return;
	} //end if*/
#endif //DEBUG


	new_portal = AllocPortal();
	new_portal->plane = mapplanes[node->planenum];

#ifdef ME
	new_portal->planenum = node->planenum;
#endif //ME

	new_portal->onnode = node;
	new_portal->winding = w;
	AddPortalToNodes (new_portal, node->children[0], node->children[1]);
} //end of the function MakeNodePortal
//===========================================================================
// Move or split the portals that bound node so that the node's
// children have portals instead of node.
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void SplitNodePortals (node_t *node)
{
	portal_t	*p, *next_portal, *new_portal;
	node_t *f, *b, *other_node;
	int side;
	plane_t *plane;
	winding_t *frontwinding, *backwinding;

	plane = &mapplanes[node->planenum];
	f = node->children[0];
	b = node->children[1];

	for (p = node->portals ; p ; p = next_portal)	
	{
		if (p->nodes[0] == node) side = 0;
		else if (p->nodes[1] == node) side = 1;
		else Error ("SplitNodePortals: mislinked portal");
		next_portal = p->next[side];

		other_node = p->nodes[!side];
		RemovePortalFromNode (p, p->nodes[0]);
		RemovePortalFromNode (p, p->nodes[1]);

//
// cut the portal into two portals, one on each side of the cut plane
//
		ClipWindingEpsilon (p->winding, plane->normal, plane->dist,
				SPLIT_WINDING_EPSILON, &frontwinding, &backwinding);

		if (frontwinding && WindingIsTiny(frontwinding))
		{
			FreeWinding (frontwinding);
			frontwinding = NULL;
			c_tinyportals++;
		} //end if

		if (backwinding && WindingIsTiny(backwinding))
		{
			FreeWinding (backwinding);
			backwinding = NULL;
			c_tinyportals++;
		} //end if

#ifdef DEBUG
/* 	//NOTE: don't use this winding ok check
		// all the invalid windings only have a degenerate edge
		if (frontwinding && WindingError(frontwinding))
		{
			Log_Print("SplitNodePortals: front %s\n", WindingErrorString());
			FreeWinding(frontwinding);
			frontwinding = NULL;
		} //end if
		if (backwinding && WindingError(backwinding))
		{
			Log_Print("SplitNodePortals: back %s\n", WindingErrorString());
			FreeWinding(backwinding);
			backwinding = NULL;
		} //end if*/
#endif //DEBUG

		if (!frontwinding && !backwinding)
		{	// tiny windings on both sides
			continue;
		}

		if (!frontwinding)
		{
			FreeWinding (backwinding);
			if (side == 0) AddPortalToNodes (p, b, other_node);
			else AddPortalToNodes (p, other_node, b);
			continue;
		}
		if (!backwinding)
		{
			FreeWinding (frontwinding);
			if (side == 0) AddPortalToNodes (p, f, other_node);
			else AddPortalToNodes (p, other_node, f);
			continue;
		}
		
	// the winding is split
		new_portal = AllocPortal();
		*new_portal = *p;
		new_portal->winding = backwinding;
		FreeWinding (p->winding);
		p->winding = frontwinding;

		if (side == 0)
		{
			AddPortalToNodes (p, f, other_node);
			AddPortalToNodes (new_portal, b, other_node);
		} //end if
		else
		{
			AddPortalToNodes (p, other_node, f);
			AddPortalToNodes (new_portal, other_node, b);
		} //end else
	}

	node->portals = NULL;
} //end of the function SplitNodePortals
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void CalcNodeBounds (node_t *node)
{
	portal_t	*p;
	int			s;
	int			i;

	// calc mins/maxs for both leaves and nodes
	ClearBounds (node->mins, node->maxs);
	for (p = node->portals ; p ; p = p->next[s])	
	{
		s = (p->nodes[1] == node);
		for (i=0 ; i<p->winding->numpoints ; i++)
			AddPointToBounds (p->winding->p[i], node->mins, node->maxs);
	}
} //end of the function CalcNodeBounds
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int c_numportalizednodes;

void MakeTreePortals_r (node_t *node)
{
	int		i;

#ifdef ME
	qprintf("\r%6d", ++c_numportalizednodes);
	if (cancelconversion) return;
#endif //ME

	CalcNodeBounds (node);
	if (node->mins[0] >= node->maxs[0])
	{
		Log_Print("WARNING: node without a volume\n");
	}

	for (i=0 ; i<3 ; i++)
	{
		if (node->mins[i] < -MAX_MAP_BOUNDS || node->maxs[i] > MAX_MAP_BOUNDS)
		{
			Log_Print("WARNING: node with unbounded volume\n");
			break;
		}
	}
	if (node->planenum == PLANENUM_LEAF)
		return;

	MakeNodePortal (node);
	SplitNodePortals (node);

	MakeTreePortals_r (node->children[0]);
	MakeTreePortals_r (node->children[1]);
} //end of the function MakeTreePortals_r
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void MakeTreePortals(tree_t *tree)
{

#ifdef ME
	Log_Print("---- Node Portalization ----\n");
	c_numportalizednodes = 0;
	c_portalmemory = 0;
	qprintf("%6d nodes portalized", c_numportalizednodes);
#endif //ME

	MakeHeadnodePortals(tree);
	MakeTreePortals_r(tree->headnode);

#ifdef ME
	qprintf("\n");
	Log_Write("%6d nodes portalized\r\n", c_numportalizednodes);
	Log_Print("%6d tiny portals\r\n", c_tinyportals);
	Log_Print("%6d KB of portal memory\r\n", c_portalmemory >> 10);
	Log_Print("%6i KB of winding memory\r\n", WindingMemory() >> 10);
#endif //ME
} //end of the function MakeTreePortals

/*
=========================================================

FLOOD ENTITIES

=========================================================
*/
//#define P_NODESTACK

node_t *p_firstnode;
node_t *p_lastnode;

//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
#ifdef P_NODESTACK
void P_AddNodeToList(node_t *node)
{
	node->next = p_firstnode;
	p_firstnode = node;
	if (!p_lastnode) p_lastnode = node;
} //end of the function P_AddNodeToList
#else //it's a node queue
//add the node to the end of the node list
void P_AddNodeToList(node_t *node)
{
	node->next = NULL;
	if (p_lastnode) p_lastnode->next = node;
	else p_firstnode = node;
	p_lastnode = node;
} //end of the function P_AddNodeToList
#endif //P_NODESTACK
//===========================================================================
// get the first node from the front of the node list
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
node_t *P_NextNodeFromList(void)
{
	node_t *node;

	node = p_firstnode;
	if (p_firstnode) p_firstnode = p_firstnode->next;
	if (!p_firstnode) p_lastnode = NULL;
	return node;
} //end of the function P_NextNodeFromList
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
void FloodPortals(node_t *firstnode)
{
	node_t *node;
	portal_t *p;
	int s;

	firstnode->occupied = 1;
	P_AddNodeToList(firstnode);

	for (node = P_NextNodeFromList(); node; node = P_NextNodeFromList())
	{
		for (p = node->portals; p; p = p->next[s])
		{
			s = (p->nodes[1] == node);
			//if the node at the other side of the portal is occupied already
			if (p->nodes[!s]->occupied) continue;
			//if it isn't possible to flood through this portal
			if (!Portal_EntityFlood(p, s)) continue;
			//
			p->nodes[!s]->occupied = node->occupied + 1;
			//
			P_AddNodeToList(p->nodes[!s]);
		} //end for
	} //end for
} //end of the function FloodPortals
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
int numrec;

void FloodPortals_r (node_t *node, int dist)
{
	portal_t *p;
	int s;
//	int i;

	Log_Print("\r%6d", ++numrec);

	if (node->occupied) Error("FloodPortals_r: node already occupied\n");
	if (!node)
	{
		Error("FloodPortals_r: NULL node\n");
	} //end if*/
	node->occupied = dist;

	for (p = node->portals; p; p = p->next[s])
	{
		s = (p->nodes[1] == node);
		//if the node at the other side of the portal is occupied already
		if (p->nodes[!s]->occupied) continue;
		//if it isn't possible to flood through this portal
		if (!Portal_EntityFlood(p, s)) continue;
		//flood recursively through the current portal
		FloodPortals_r(p->nodes[!s], dist+1);
	} //end for
	Log_Print("\r%6d", --numrec);
} //end of the function FloodPortals_r
//===========================================================================
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
qboolean PlaceOccupant (node_t *headnode, vec3_t origin, entity_t *occupant)
{
	node_t *node;
	vec_t	d;
	plane_t *plane;

	//find the leaf to start in
	node = headnode;
	while(node->planenum != PLANENUM_LEAF)
	{
		if (node->planenum < 0 || node->planenum > nummapplanes)
		{
			Error("PlaceOccupant: invalid node->planenum\n");
		} //end if
		plane = &mapplanes[node->planenum];
		d = DotProduct(origin, plane->normal) - plane->dist;
		if (d >= 0) node = node->children[0];
		else node = node->children[1];
		if (!node)
		{
			Error("PlaceOccupant: invalid child %d\n", d < 0);
		} //end if
	} //end while
	//don't start in solid
//	if (node->contents == CONTENTS_SOLID)
	//ME: replaced because in LeafNode in brushbsp.c
	//    some nodes have contents solid with other contents
	if (node->contents & CONTENTS_SOLID) return false;
	//if the node is already occupied
	if (node->occupied) return false;

	//place the occupant in the first leaf
	node->occupant = occupant;

	numrec = 0;
//	Log_Print("%6d recurses", numrec);
//	FloodPortals_r(node, 1);
//	Log_Print("\n");
	FloodPortals(node);

	return true;
} //end of the function PlaceOccupant
//===========================================================================
// Marks all nodes that can be reached by entites
//
// Parameter:				-
// Returns:					-
// Changes Globals:		-
//===========================================================================
qboolean FloodEntities (tree_t *tree)
{
	int i;
	int x, y;
	vec3_t origin;
	char *cl;
	qboolean inside;
	node_t *headnode;

	headnode = tree->headnode;
	Log_Print("------ FloodEntities -------\n");
	inside = false;
	tree->outside_node.occupied = 0;

	//start at entity 1 not the world ( = 0)
	for (i = 1; i < num_entities; i++)
	{
		GetVectorForKey(&entities[i], "origin", origin);
		if (VectorCompare(origin, vec3_origin)) continue;

		cl = ValueForKey(&entities[i], "classname");
		origin[2] += 1;	//so objects on floor are ok

//		Log_Print("flooding from entity %d: %s\n", i, cl);