bsp.cpp

使用stl技术,(还没看,是听说的)

	int	minSplits = -1;
	int	minRatio = -1;

	for (unsigned int i = 0; i < groups.size(); ++i)
	{
		if (buildInfo.progressDialog && buildInfo.progressDialog->stopRequested()) return false;

		BSP::sGroup &	g = groups[i];

		// Within the error bound?

		if (g.leastDepthRatio >= minErrorBound && g.leastDepthRatio <= maxErrorBound)
		{
			// Fewer splits?

			if (minSplits == -1 || g.leastDepthSplits < groups[minSplits].leastDepthSplits)
			{
				minSplits = i;
			}
		}

		// If we're outside of the error bounds, we'll get as close to 50% as we can, just in case
		// we never find one in range...

		else
		{
			if (minRatio == -1 || fstl::abs(50.0 - g.leastDepthRatio) < fstl::abs(50.0f - groups[minRatio].leastDepthRatio))
			{
				minRatio = i;
			}
		}
	}

	// If we found a min splits node, use it, otherwise use the minDepth node

	int	bestGroupIndex = (minSplits >= 0) ? minSplits : minRatio;
	BSP::sGroup &	bestGroup = groups[bestGroupIndex];
	*bestSplitter = bestGroup.polys[bestGroup.leastDepthIndex];

	return true;
}

// ---------------------------------------------------------------------------------------------------------------------------------

static	bool	bisectScene(BSP::sBuildInfo & buildInfo, const geom::Plane3 & plane, RadPrimPointerArray & frontList, RadPrimPointerArray & backList, RadPrimPointerArray & thisList)
{
	// Clear the lists

	frontList.erase();
	backList.erase();

	// Reserve for speed...

	frontList.reserve(buildInfo.polys.size());
	backList.reserve(buildInfo.polys.size());

	// Split the polys

	for (unsigned int i = 0; i < buildInfo.polys.size(); ++i)
	{
		if (!(i & 0xff) && buildInfo.progressDialog && buildInfo.progressDialog->stopRequested()) return false;

		RadPrim &	poly = *buildInfo.polys[i];

		// Skip all polygons whose plane match the splitter's

		if (poly.plane().D() == plane.D() && poly.plane().normal() == plane.normal())
		{
			thisList += &poly;
			continue;
		}

		// Bisect

		RadPrim	back;
		if (!poly.bisect(plane, back)) return false;
		if (poly.xyz().size())	frontList += &poly;

		// If we have a back-sided polygon, we need to do a bit more work...

		if (back.xyz().size())
		{
			// If we split the polygon, then we need to add the new piece

			if (poly.xyz().size())
			{
				// Add the new piece

				(*buildInfo.scenePolys) += back;

				// Finally, add it to the back list, making sure to reference the polygon from the scene polys

				backList += &buildInfo.scenePolys->tail()->data();

				// For stats

				buildInfo.totalPolys++;
			}

			// We didn't split the polygon, the whole thing is on the backside, so revert back to the original polygon
			// and just use the address of the original polygon

			else
			{
				poly = back;
				backList += &poly;
			}
		}
	}

	// Remove waste

	frontList.compact();
	backList.compact();

	return true;
}

// ---------------------------------------------------------------------------------------------------------------------------------

static	bool	updateDisplay(BSP::sBuildInfo &buildInfo, const unsigned int depth)
{
	if (!buildInfo.progressDialog) return true;

	// Update the display

	static	int	periodicUpdate;
	if (!(periodicUpdate & 0xf))
	{
		float	percent = static_cast<float>(buildInfo.polysUsed) / static_cast<float>(buildInfo.totalPolys) * 100.0f;

		// Sometimes the percent can move backwards (because of splits) -- let's not show that

		if (percent > buildInfo.lastPercent)
		{
			buildInfo.progressDialog->setCurrentPercent(percent);
			buildInfo.lastPercent = percent;
		}

		char	dsp[90];
		sprintf(dsp, "%d", buildInfo.totalNodes);
		buildInfo.progressDialog->setLabel2("Nodes:");
		buildInfo.progressDialog->setText2(dsp);

		sprintf(dsp, "%d", buildInfo.totalPolys - buildInfo.originalPolys);
		buildInfo.progressDialog->setLabel3("Splits:");
		buildInfo.progressDialog->setText3(dsp);

		sprintf(dsp, "%d", static_cast<int>(static_cast<float>(buildInfo.totalDepth) / static_cast<float>(buildInfo.totalNodes)));
		buildInfo.progressDialog->setLabel4("Average depth:");
		buildInfo.progressDialog->setText4(dsp);
	}
	periodicUpdate++;

	// Always check for this...

	if (buildInfo.progressDialog->stopRequested()) return false;

	// Track our max depth

	if (depth > buildInfo.maxDepth)
	{
		buildInfo.maxDepth = depth;
		char	dsp[90];
		sprintf(dsp, "%d", depth);
		buildInfo.progressDialog->setLabel5("Max depth:");
		buildInfo.progressDialog->setText5(dsp);
	}

	return true;
}

// ---------------------------------------------------------------------------------------------------------------------------------

bool	BSP::build(sBuildInfo & buildInfo)
{
	// Initialization

	buildInfo.maxDepth = 0;
	buildInfo.totalDepth = 0;
	buildInfo.polysUsed = 0;
	buildInfo.totalPolys = buildInfo.scenePolys->size();
	buildInfo.originalPolys = buildInfo.totalPolys;
	buildInfo.totalNodes = 0;
	buildInfo.lastPercent = 0.0f;

	if (buildInfo.progressDialog)
	{
		char	dsp[90];
		buildInfo.progressDialog->setCurrentPercent(0.0f);
		sprintf(dsp, "%d", buildInfo.originalPolys);
		buildInfo.progressDialog->setLabel1("Polygons:");
		buildInfo.progressDialog->setText1(dsp);

		buildInfo.progressDialog->setCurrentStatus("Sorting...");
	}

	// Convert the polys to pointers
	{
		RadPrimPointerArray &	ppa = buildInfo.polys;
		ppa.reserve(buildInfo.scenePolys->size());

		// Convert polys to poly pointers for faster sorting

		RadPrimList::node *	n = buildInfo.scenePolys->head();

		while(n)
		{
			ppa += &n->data();
			n = n->next();
		}
	}

	// Sort based on pointers (for speedier sorts)

	qsort(static_cast<void *>(&buildInfo.polys[0]), buildInfo.polys.size(), sizeof(RadPrim *), ppaCompare);

	// Pre-classify the polygons

	if (buildInfo.progressDialog) buildInfo.progressDialog->setCurrentStatus("Quantizing...");
	if (!classifyForQuantization(buildInfo)) return false;

	// Recursively build the tree

	if (buildInfo.progressDialog) buildInfo.progressDialog->setCurrentStatus("Building the BSP tree...");
	return recursiveBuild(buildInfo, 0);
}

// ---------------------------------------------------------------------------------------------------------------------------------

bool	BSP::recursiveBuild(sBuildInfo & buildInfo, const unsigned int depth)
{
	// Statistics

	buildInfo.totalNodes++;
	buildInfo.totalDepth += depth;

	// Update the display (statistics)

	if (!updateDisplay(buildInfo, depth)) return false;

	// Should never happen...

	if (!buildInfo.polys.size()) return false;

	// Only one poly?

	if (buildInfo.polys.size() == 1)
	{
		polys() = buildInfo.polys;
		buildInfo.polysUsed += 1;
		return true;
	}

	// Pre-populate the quantized polygon array
	//
	// Array size is half of a sphere (half the quantized resolution) latitude segments by
	// a full set of longitude segments. However, since everything in the top segment quantizes
	// to the apex of the hemisphere, then we have a few extra 1s in the code below...

	GroupArray	groups;
	groups.populate(sGroup(), buildInfo.quantizeResolution * (buildInfo.quantizeResolution / 4 - 1) + 1);

	// Classify all the polygons in the quantized hemisphere

	if (!classifyAndQuantize(buildInfo, groups)) return false;

	// Unify the quantized geometry (sort the polygons within them on D, and remove empty groups)

	if (!unifyGroups(buildInfo, groups)) return false;

	// Find the optimal splitters (one splitter per group)

	if (!findOptimalSplitters(buildInfo, groups)) return false;

	// Find the best splitter

	RadPrim *	bestSplitter;
	if (!findBestSplitter(buildInfo, groups, &bestSplitter)) return false;

	// Bisect the scene

	RadPrimPointerArray	frontList, backList;
	frontList.reserve(buildInfo.polys.size());
	backList.reserve(buildInfo.polys.size());
	if (!bisectScene(buildInfo, bestSplitter->plane(), frontList, backList, polys())) return false;

	// Keep track of how many polygons we've added to the scene (split) and removed (proccesed)

	buildInfo.polysUsed += polys().size();

	// Front

	if (frontList.size())
	{
		buildInfo.polys = frontList;
		front() = &buildInfo.bspNodeReservoir.get();
		if (!front()->recursiveBuild(buildInfo, depth+1)) return false;
	}

	// Back

	if (backList.size())
	{
		buildInfo.polys = backList;
		back() = &buildInfo.bspNodeReservoir.get();
		if (!back()->recursiveBuild(buildInfo, depth+1)) return false;
	}

	return true;
}

// ---------------------------------------------------------------------------------------------------------------------------------

void	BSP::getOrderedList(const geom::Point3 & viewpoint, RadPrimPointerListGrainy & orderedList)
{
	if (!polys().size()) return;

	// Which side is the viewpoint on?

	float	halfplane = polys()[0]->plane().halfplane(viewpoint);

	// Am I on the front side?

	if (halfplane > 0)
	{
		if (back()) back()->getOrderedList(viewpoint, orderedList);

		// Add the primitives...

		for (unsigned int i = 0; i < polys().size(); ++i)
		{
			// PDNDEBUG -- any way to avoid this situation?

			if (polys()[i]->plane().halfplane(viewpoint) > 0)
			{
				orderedList += polys()[i];
			}
		}

		if (front()) front()->getOrderedList(viewpoint, orderedList);
	}
	else
	{
		if (front()) front()->getOrderedList(viewpoint, orderedList);
		if (back()) back()->getOrderedList(viewpoint, orderedList);
	}
}

// ---------------------------------------------------------------------------------------------------------------------------------
// BSP.cpp - End of file
// ---------------------------------------------------------------------------------------------------------------------------------