brushbsp.c

quakeIII源码这个不用我多说吧

// Returns:				-
// Changes Globals:		-
//===========================================================================
void CheckBrushLists(bspbrush_t *brushlist1, bspbrush_t *brushlist2)
{
	bspbrush_t *brush1, *brush2;

	for (brush1 = brushlist1; brush1; brush1 = brush1->next)
	{
		for (brush2 = brushlist2; brush2; brush2 = brush2->next)
		{
			assert(brush1 != brush2);
		} //end for
	} //end for
} //end of the function CheckBrushLists
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
int numrecurse = 0;

node_t *BuildTree_r (node_t *node, bspbrush_t *brushes)
{
	node_t		*newnode;
	side_t		*bestside;
	int			i, totalmem;
	bspbrush_t	*children[2];

	qprintf("\r%6d", numrecurse);
	numrecurse++;

	if (numthreads == 1)
	{
		totalmem = WindingMemory() + c_nodememory + c_brushmemory;
		if (totalmem > c_peak_totalbspmemory)
			c_peak_totalbspmemory = totalmem;
		c_nodes++;
	} //endif

	if (drawflag)
		DrawBrushList(brushes, node);

	// find the best plane to use as a splitter
	bestside = SelectSplitSide (brushes, node);
	if (!bestside)
	{
		// leaf node
		node->side = NULL;
		node->planenum = -1;
		LeafNode(node, brushes);
		if (node->contents & CONTENTS_SOLID) c_solidleafnodes++;
		if (create_aas)
		{
			//free up memory!!!
			FreeBrushList(node->brushlist);
			node->brushlist = NULL;
			//free the node volume brush
			if (node->volume)
			{
				FreeBrush(node->volume);
				node->volume = NULL;
			} //end if
		} //end if
		return node;
	} //end if

	// this is a splitplane node
	node->side = bestside;
	node->planenum = bestside->planenum & ~1;	// always use front facing

	//split the brush list in two for both children
	SplitBrushList (brushes, node, &children[0], &children[1]);
	//free the old brush list
	FreeBrushList (brushes);

	// allocate children before recursing
	for (i = 0; i < 2; i++)
	{
		newnode = AllocNode ();
		newnode->parent = node;
		node->children[i] = newnode;
	} //end for

	//split the volume brush of the node for the children
	SplitBrush (node->volume, node->planenum, &node->children[0]->volume,
		&node->children[1]->volume);

	if (create_aas)
	{
		//free the volume brush
		if (node->volume)
		{
			FreeBrush(node->volume);
			node->volume = NULL;
		} //end if
	} //end if
	// recursively process children
	for (i = 0; i < 2; i++)
	{
		node->children[i] = BuildTree_r(node->children[i], children[i]);
	} //end for

	return node;
} //end of the function BuildTree_r
//===========================================================================
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
node_t *firstnode;		//first node in the list
node_t *lastnode;			//last node in the list
int nodelistsize;			//number of nodes in the list
int use_nodequeue = 0;	//use nodequeue, otherwise a node stack is used
int numwaiting = 0;

void (*AddNodeToList)(node_t *node);

//add the node to the front of the node list
//(effectively using a node stack)
void AddNodeToStack(node_t *node)
{
	ThreadLock();

	node->next = firstnode;
	firstnode = node;
	if (!lastnode) lastnode = node;
	nodelistsize++;

	ThreadUnlock();
	//
	ThreadSemaphoreIncrease(1);
} //end of the function AddNodeToStack
//add the node to the end of the node list
//(effectively using a node queue)
void AddNodeToQueue(node_t *node)
{
	ThreadLock();

	node->next = NULL;
	if (lastnode) lastnode->next = node;
	else firstnode = node;
	lastnode = node;
	nodelistsize++;

	ThreadUnlock();
	//
	ThreadSemaphoreIncrease(1);
} //end of the function AddNodeToQueue
//get the first node from the front of the node list
node_t *NextNodeFromList(void)
{
	node_t *node;

	ThreadLock();
	numwaiting++;
	if (!firstnode)
	{
		if (numwaiting >= GetNumThreads()) ThreadSemaphoreIncrease(GetNumThreads());
	} //end if
	ThreadUnlock();

	ThreadSemaphoreWait();

	ThreadLock();

	numwaiting--;

	node = firstnode;
	if (firstnode)
	{
		firstnode = firstnode->next;
		nodelistsize--;
	} //end if
	if (!firstnode) lastnode = NULL;

	ThreadUnlock();

	return node;
} //end of the function NextNodeFromList
//returns the size of the node list
int NodeListSize(void)
{
	int size;

	ThreadLock();
	size = nodelistsize;
	ThreadUnlock();

	return size;
} //end of the function NodeListSize
//
void IncreaseNodeCounter(void)
{
	ThreadLock();
	//if (verbose) printf("\r%6d", numrecurse++);
	qprintf("\r%6d", numrecurse++);
	//qprintf("\r%6d %d, %5d ", numrecurse++, GetNumThreads(), nodelistsize);
	ThreadUnlock();
} //end of the function IncreaseNodeCounter
//thread function, gets nodes from the nodelist and processes them
void BuildTreeThread(int threadid)
{
	node_t *newnode, *node;
	side_t *bestside;
	int i, totalmem;
	bspbrush_t *brushes;

	for (node = NextNodeFromList(); node; )
	{
		//if the nodelist isn't empty try to add another thread
		//if (NodeListSize() > 10) AddThread(BuildTreeThread);
		//display the number of nodes processed so far
		if (numthreads == 1)
			IncreaseNodeCounter();

		brushes = node->brushlist;

		if (numthreads == 1)
		{
			totalmem = WindingMemory() + c_nodememory + c_brushmemory;
			if (totalmem > c_peak_totalbspmemory)
			{
				c_peak_totalbspmemory = totalmem;
			} //end if
			c_nodes++;
		} //endif

		if (drawflag)
		{
			DrawBrushList(brushes, node);
		} //end if

		if (cancelconversion)
		{
			bestside = NULL;
		} //end if
		else
		{
			// find the best plane to use as a splitter
			bestside = SelectSplitSide(brushes, node);
		} //end else
		//if there's no split side left
		if (!bestside)
		{
			//create a leaf out of the node
			LeafNode(node, brushes);
			if (node->contents & CONTENTS_SOLID) c_solidleafnodes++;
			if (create_aas)
			{
				//free up memory!!!
				FreeBrushList(node->brushlist);
				node->brushlist = NULL;
			} //end if
			//free the node volume brush (it is not used anymore)
			if (node->volume)
			{
				FreeBrush(node->volume);
				node->volume = NULL;
			} //end if
			node = NextNodeFromList();
			continue;
		} //end if

		// this is a splitplane node
		node->side = bestside;
		node->planenum = bestside->planenum & ~1;	//always use front facing

		//allocate children
		for (i = 0; i < 2; i++)
		{
			newnode = AllocNode();
			newnode->parent = node;
			node->children[i] = newnode;
		} //end for

		//split the brush list in two for both children
		SplitBrushList(brushes, node, &node->children[0]->brushlist, &node->children[1]->brushlist);

		CheckBrushLists(node->children[0]->brushlist, node->children[1]->brushlist);
		//free the old brush list
		FreeBrushList(brushes);
		node->brushlist = NULL;

		//split the volume brush of the node for the children
		SplitBrush(node->volume, node->planenum, &node->children[0]->volume,
								&node->children[1]->volume);

		if (!node->children[0]->volume || !node->children[1]->volume)
		{
			Error("child without volume brush");
		} //end if

		//free the volume brush
		if (node->volume)
		{
			FreeBrush(node->volume);
			node->volume = NULL;
		} //end if
		//add both children to the node list
		//AddNodeToList(node->children[0]);
		AddNodeToList(node->children[1]);
		node = node->children[0];
	} //end while
	RemoveThread(threadid);
} //end of the function BuildTreeThread
//===========================================================================
// build the bsp tree using a node list
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
void BuildTree(tree_t *tree)
{
	int i;

	firstnode = NULL;
	lastnode = NULL;
	//use a node queue or node stack
	if (use_nodequeue) AddNodeToList = AddNodeToQueue;
	else AddNodeToList = AddNodeToStack;
	//setup thread locking
	ThreadSetupLock();
	ThreadSetupSemaphore();
	numwaiting = 0;
	//
	Log_Print("%6d threads max\n", numthreads);
	if (use_nodequeue) Log_Print("breadth first bsp building\n");
	else Log_Print("depth first bsp building\n");
	qprintf("%6d splits", 0);
	//add the first node to the list
	AddNodeToList(tree->headnode);
	//start the threads
	for (i = 0; i < numthreads; i++)
		AddThread(BuildTreeThread);
	//wait for all added threads to be finished
	WaitForAllThreadsFinished();
	//shutdown the thread locking
	ThreadShutdownLock();
	ThreadShutdownSemaphore();
} //end of the function BuildTree
//===========================================================================
// The incoming brush list will be freed before exiting
//
// Parameter:			-
// Returns:				-
// Changes Globals:		-
//===========================================================================
tree_t *BrushBSP(bspbrush_t *brushlist, vec3_t mins, vec3_t maxs)
{
	int i, c_faces, c_nonvisfaces, c_brushes;
	bspbrush_t *b;
	node_t *node;
	tree_t *tree;
	vec_t volume;
//	vec3_t point;

	Log_Print("-------- Brush BSP ---------\n");

	tree = Tree_Alloc();

	c_faces = 0;
	c_nonvisfaces = 0;
	c_brushes = 0;
	c_totalsides = 0;
	for (b = brushlist; b; b = b->next)
	{
		c_brushes++;

		volume = BrushVolume(b);
		if (volume < microvolume)
		{
			Log_Print("WARNING: entity %i, brush %i: microbrush\n",
				b->original->entitynum, b->original->brushnum);
		} //end if

		for (i=0 ; i<b->numsides ; i++)
		{
			if (b->sides[i].flags & SFL_BEVEL)
				continue;
			if (!b->sides[i].winding)
				continue;
			if (b->sides[i].texinfo == TEXINFO_NODE)
				continue;
			if (b->sides[i].flags & SFL_VISIBLE)
			{
				c_faces++;
			} //end if
			else
			{
				c_nonvisfaces++;
				//if (create_aas) b->sides[i].texinfo = TEXINFO_NODE;
			} //end if
		} //end for
		c_totalsides += b->numsides;

		AddPointToBounds (b->mins, tree->mins, tree->maxs);
		AddPointToBounds (b->maxs, tree->mins, tree->maxs);
	} //end for

	Log_Print("%6i brushes\n", c_brushes);
	Log_Print("%6i visible faces\n", c_faces);
	Log_Print("%6i nonvisible faces\n", c_nonvisfaces);
	Log_Print("%6i total sides\n", c_totalsides);

	c_active_brushes = c_brushes;
	c_nodememory = 0;
	c_brushmemory = 0;
	c_peak_brushmemory = 0;

	c_nodes = 0;
	c_nonvis = 0;
	node = AllocNode ();

	//volume of first node (head node)
	node->volume = BrushFromBounds (mins, maxs);
	//
	tree->headnode = node;
	//just get some statistics and the mins/maxs of the node
	numrecurse = 0;
//	qprintf("%6d splits", numrecurse);

	tree->headnode->brushlist = brushlist;
	BuildTree(tree);

	//build the bsp tree with the start node from the brushlist
//	node = BuildTree_r(node, brushlist);

	//if the conversion is cancelled
	if (cancelconversion) return tree;

	qprintf("\n");
	Log_Write("%6d splits\r\n", numrecurse);
//	Log_Print("%6i visible nodes\n", c_nodes/2 - c_nonvis);
//	Log_Print("%6i nonvis nodes\n", c_nonvis);
//	Log_Print("%6i leaves\n", (c_nodes+1)/2);
//	Log_Print("%6i solid leaf nodes\n", c_solidleafnodes);
//	Log_Print("%6i active brushes\n", c_active_brushes);
	if (numthreads == 1)
	{
//		Log_Print("%6i KB of node memory\n", c_nodememory >> 10);
//		Log_Print("%6i KB of brush memory\n", c_brushmemory >> 10);
//		Log_Print("%6i KB of peak brush memory\n", c_peak_brushmemory >> 10);
//		Log_Print("%6i KB of winding memory\n", WindingMemory() >> 10);
//		Log_Print("%6i KB of peak winding memory\n", WindingPeakMemory() >> 10);
		Log_Print("%6i KB of peak total bsp memory\n", c_peak_totalbspmemory >> 10);
	} //end if

	/*
	point[0] = 1485;
	point[1] = 956.125;
	point[2] = 352.125;
	node = PointInLeaf(tree->headnode, point);
	if (node->planenum != PLANENUM_LEAF)
	{
		Log_Print("node not a leaf\n");
	} //end if
	Log_Print("at %f %f %f:\n", point[0], point[1], point[2]);
	PrintContents(node->contents);
	Log_Print("node->expansionbboxes = %d\n", node->expansionbboxes);
	//*/
	return tree;
} //end of the function BrushBSP