bsp.cpp

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

// ---------------------------------------------------------------------------------------------------------------------------------
//  ____   _____ _____                       
// |  _ \ / ____|  __ \                      
// | |_) | (___ | |__) |     ___ _ __  _ __  
// |  _ < \___ \|  ___/     / __| '_ \| '_ \ 
// | |_) |____) | |      _ | (__| |_) | |_) |
// |____/|_____/|_|     (_) \___| .__/| .__/ 
//                              | |   | |    
//                              |_|   |_|    
//
// Description:
//
//   BSP (binary space partitioning) tree
//
// Notes:
//
//   Best viewed with 8-character tabs and (at least) 132 columns
//
// History:
//
//   08/03/2001 by Paul Nettle: Original creation
//
// Restrictions & freedoms pertaining to usage and redistribution of this software:
//
//   This software is 100% free. If you use this software (in part or in whole) you must credit the author. This software may not be
//   re-distributed (in part or in whole) in a modified form without clear documentation on how to obtain a copy of the original
//   work. You may not use this software to directly or indirectly cause harm to others. This software is provided as-is and without
//   warrantee -- Use at your own risk. For more information, visit HTTP://www.FluidStudios.com/
//
// Copyright 2002, Fluid Studios, Inc., all rights reserved.
// ---------------------------------------------------------------------------------------------------------------------------------

#include "stdafx.h"
#include "FSRad.h"
#include "RadPrim.h"
#include "ProgressDlg.h"
#include "BSP.h"

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

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

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

static	const	float	EPSILON = 1.0e-5f;

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

static	int ppaCompare(const void *elem1, const void *elem2)
{
	const RadPrim &	a = **reinterpret_cast<const RadPrim * const *>(elem1);
	const RadPrim &	b = **reinterpret_cast<const RadPrim * const *>(elem2);

	if (a.plane().D() == b.plane().D()) return 0;
	if (a.plane().D() >  b.plane().D()) return 1;
	return -1;
}

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

static	int RadPrimCompare(const void *elem1, const void *elem2)
{
	const RadPrim &	a = *reinterpret_cast<const RadPrim *>(elem1);
	const RadPrim &	b = *reinterpret_cast<const RadPrim *>(elem2);

	if (a.plane().D() == b.plane().D()) return 0;
	if (a.plane().D() >  b.plane().D()) return 1;
	return -1;
}

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

static	int groupCompare(const void *elem1, const void *elem2)
{
	const BSP::sGroup &	a = *reinterpret_cast<const BSP::sGroup *>(elem1);
	const BSP::sGroup &	b = *reinterpret_cast<const BSP::sGroup *>(elem2);

	if (a.leastDepthRatio == b.leastDepthRatio) return 0;
	if (a.leastDepthRatio >  b.leastDepthRatio) return 1;
	return -1;
}

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

static	bool	classifyForQuantization(BSP::sBuildInfo & buildInfo)
{
	float	anglesPerLatStep = 90.0f / static_cast<float>(buildInfo.quantizeResolution) * 4;
	float	anglesPerLonStep = 360.0f / static_cast<float>(buildInfo.quantizeResolution);

	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];

		// The current poly's plane's normal

		geom::Vector3	normal = poly.plane().normal();

		// We're only interested in the top of the hemisphere...

		if (normal.y() < 0) normal.y() = -normal.y();

		// Calculate the angle between the apex of the classification hemisphere and the normal (latitude)

		double	tmp = acos(normal ^ geom::Vector3(0, 1, 0));
		float	latAngle = static_cast<float>(fstl::toDegrees(tmp));

		// Find the quantized step from the latitude

		unsigned int	latStep = static_cast<unsigned int>(latAngle / anglesPerLatStep);
		if (latStep >= buildInfo.quantizeResolution/4) latStep = buildInfo.quantizeResolution/4 - 1;

		// If the latStep is > 0, then we also need the longitude step...

		unsigned int	lonStep = 0;
		if (latStep)
		{
			// Generate a 2D unit vector from the normal

			geom::Vector2	v(normal.x(), normal.z());
			v.normalize();

			// Calculate the lonAngle

			double	tmp = acos(v ^ geom::Vector2(0, 1));
			float	lonAngle = static_cast<float>(fstl::toDegrees(tmp));
			if (v.x() < 0) lonAngle = 360 - lonAngle;

			// Find the quantized step from the longitude angle

			lonStep = static_cast<unsigned int>(lonAngle / anglesPerLonStep);
			if (lonStep >= buildInfo.quantizeResolution) lonStep = 0;
		}

		// Index into the quantized polys array...

		unsigned int	index = 0;
		if (latStep)
		{
			index = (latStep-1) * buildInfo.quantizeResolution + lonStep + 1;
		}

		poly.usageIndex() = index;
	}

	return true;
}

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

static	bool	classifyAndQuantize(BSP::sBuildInfo & buildInfo, BSP::GroupArray & groups)
{
	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];
		groups[poly.usageIndex()].polys += &poly;
	}

	return true;
}

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

static	bool	unifyGroups(BSP::sBuildInfo & buildInfo, BSP::GroupArray & groups)
{
	// Remove empty groups
	{
		// Create a new list and reserve for speed

		BSP::GroupArray	newList;
		newList.reserve(groups.size());

		for (unsigned int i = 0; i < groups.size(); ++i)
		{
			if (groups[i].polys.size()) newList += groups[i];
		}

		// Move the unique list over

		groups = newList;
	}

	// Sort the polygons in each group based on D from the plane equation
	{
		for (unsigned int i = 0; i < groups.size(); ++i)
		{
			if (buildInfo.progressDialog && buildInfo.progressDialog->stopRequested()) return false;

			RadPrimPointerArray &	ppa = groups[i].polys;

			// Must be something worth working on...

			if (ppa.size() <= 1) continue;

			// Remove duplicate planes
			{
				// Create a new list and reserve for speed

				RadPrimPointerArray	newList;
				newList.reserve(ppa.size());

				unsigned int	lastIndex = 0;
				newList += ppa[0];

				for (unsigned int i = 1; i < ppa.size(); ++i)
				{
					if (ppa[i]->plane().D()      != newList[lastIndex]->plane().D() ||
					    ppa[i]->plane().normal() != newList[lastIndex]->plane().normal())
					{
						newList += ppa[i];
						lastIndex++;
					}
				}

				// Move the unique list over (if it changed)

				if (ppa.size() != newList.size()) ppa = newList;
			}
		}	
	}	

	return true;
}

// ---------------------------------------------------------------------------------------------------------------------------------
// Tests all polys against a bisection plane. Returns the ratio of polygons that land on the front side as well as the number
// of polygons that are bisected by the plane.
// ---------------------------------------------------------------------------------------------------------------------------------

static	bool	tryBisectionPlane(BSP::sBuildInfo & buildInfo, const geom::Plane3 & plane, float & ratio, unsigned int & splitCount)
{
	splitCount = 0;
	unsigned int	fCount = 0;
	unsigned int	bCount = 0;

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

		const 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()) continue;

		bool	front = false;
		bool	back = false;
		for (unsigned int j = 0; j < poly.xyz().size(); ++j)
		{
			// Calculate the distance of this point to the plane

			float	dist = plane.distance(poly.xyz()[j]);
			if (dist > -EPSILON && dist < EPSILON) dist = 0.0f;

			if (dist > 0)	front = true;
			else		back = true;

			// If it's a split, we can early-out

			if (front && back)
			{
				splitCount++;
				break;
			}
		}

		if (front) fCount++;
		if (back) bCount++;
	}

	// Calculate the ratio of front-sided polytons

	ratio = static_cast<float>(fCount) / static_cast<float>(buildInfo.polys.size());

	return true;
}

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

static	bool	findOptimalSplitters(BSP::sBuildInfo & buildInfo, BSP::GroupArray & groups)
{
	// Binary search dataset for optimal splitters

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

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

		// Binary search this group...

		int	sIndex = 0;
		int	eIndex = g.polys.size();

		do
		{
			// The midpoint of the range

			g.leastDepthIndex = (sIndex + eIndex) / 2;

			// We're about to try a bisection by this plane. In order to follow the binary search
			// we'll need this plane to have a reference, so they always point outward from the center
			// of the hemisphere.

			geom::Plane3	plane = g.polys[g.leastDepthIndex]->plane();
			if (plane.vector().y() < 0) plane.vector().y() = -plane.vector().y();

			// Try this bisection

			if (!tryBisectionPlane(buildInfo, plane, g.leastDepthRatio, g.leastDepthSplits)) return false;

			// Convert the least depth ratio to a percent

			g.leastDepthRatio *= 100.0f;

			// At this point, it should be noted that a series of polygons in the least-depth range
			// will all have very close lesat-depth values, but a wide range of split counts...
			//
			// It may be possible to account for this...

			// Perfect?

			if (g.leastDepthRatio == 50.0f) break;

			// Binary search...

			if (g.leastDepthRatio < 50.0f)	eIndex = g.leastDepthIndex - 1;
			else				sIndex = g.leastDepthIndex + 1;
		} while (sIndex < eIndex);
	}

	return true;
}

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

static	bool	findBestSplitter(BSP::sBuildInfo & buildInfo, BSP::GroupArray & groups, RadPrim ** bestSplitter)
{
	// Sort the groups based on leastDepthRatio

	qsort(static_cast<void *>(&groups[0]), groups.size(), sizeof(BSP::sGroup), groupCompare);

	// Track the group with the fewest splits that falls within the bounds specified by the formal parameter
	// 'leastDepthErrorBoundsPercent'.

	float	minErrorBound = 50.0f - buildInfo.leastDepthErrorBoundsPercent;
	float	maxErrorBound = 50.0f + buildInfo.leastDepthErrorBoundsPercent;