lmapgen.cpp

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

// ---------------------------------------------------------------------------------------------------------------------------------
//  _      __  __              _____                                 
// | |    |  \/  |            / ____|                                
// | |    | \  / | __ _ _ __ | |  __  ___ _ __       ___ _ __  _ __  
// | |    | |\/| |/ _` | '_ \| | |_ |/ _ \ '_ \     / __| '_ \| '_ \ 
// | |____| |  | | (_| | |_) | |__| |  __/ | | | _ | (__| |_) | |_) |
// |______|_|  |_|\__,_| .__/ \_____|\___|_| |_|(_) \___| .__/| .__/ 
//                     | |                              | |   | |    
//                     |_|                              |_|   |_|    
//
// Description:
//
//   Lightmap generation
//
// Notes:
//
//   Best viewed with 8-character tabs and (at least) 132 columns
//
// History:
//
//   10/10/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 "RadLMap.h"
#include "LMapGen.h"
#include "ProgressDlg.h"

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

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

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

static	const	float	epsilon = 0.00001f;
const	unsigned int	LMapGen::_borderPixels = 1;

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

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

	float	dist = a->plane().D() - b->plane().D();

	if (fstl::abs(dist) < epsilon) return 0;
	if (dist > 0) return 1;
	return -1;
}

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

	LMapGen::LMapGen()
{
}

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

	LMapGen::~LMapGen()
{
}

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

bool	LMapGen::generate(ProgressDlg & progress, RadPrimList & polygons, RadLMapArray & lightmaps)
{
	// Combine primitives into completely connected entities, even if concave

	CombinedPolyList	cpl;
	if (!buildCombinedPolygons(progress, polygons, cpl)) return false;

	// Clip any Combined polygons that extend beyond the lightmap dimensions

	if (!clipCombinedPolygons(progress, cpl, polygons, lightmapWidth(), lightmapHeight())) return false;

	// Start adding Combined polygons to the lightmaps, until none are left

	if (!populateLightmaps(progress, cpl, lightmaps, lightmapWidth(), lightmapHeight())) return false;

	// Debug code -- generate lightmaps so we can see where stuff is
	#if 0
	{
		RadLMapArray	lmaps;
		RadLMap		blank(lightmapWidth(),lightmapHeight());
		lmaps.populate(blank, lightmaps.size());

		for (CombinedPolyList::node *i = cpl.head(); i; i = i->next())
		{
			CombinedPoly &	cp = i->data();
			if (!cp.complete()) continue;
			RadLMap &	lm = lmaps[cp.lightmapID()];

			unsigned int	ptr = static_cast<unsigned int>(&cp);
			unsigned int	r = ((ptr >> 0)&0x7f) + 0x70;
			unsigned int	g = ((ptr >> 1)&0x7f) + 0x70;
			unsigned int	b = ((ptr >> 2)&0x7f) + 0x70;
			geom::Color3	clr(r, g, b);

			for (unsigned int j = 0; j < cp.primitives().size(); ++j)
			{
				RadPrim &	prim = *cp.primitives()[j];
				int	minX, maxX, minY, maxY;
				prim.calcIntegerUVExtents(minX, maxX, minY, maxY);

				for (unsigned int y = minY; y <= maxY; ++y)
				{
					for (unsigned int x = minX; x <= maxX; ++x)
					{
						lm.data()[y * lm.width() + x] = clr;
					}
				}
			}
		}

		{
			for (unsigned int i = 0; i < lightmaps.size(); ++i)
			{
				RadLMap &	lm = lmaps[i];
				lm.id() = i;
				lm.writeRaw("j:\\t");

			}
		}
	}
	#endif

	// Done

	return true;
}

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

bool	LMapGen::buildCombinedPolygons(ProgressDlg & progress, const RadPrimList & polygons, CombinedPolyList & cpl) const
{
	progress.setCurrentStatus("Preparing to generate lightmaps");
	progress.setCurrentPercent(0);

	// Start fresh

	cpl.erase();

	// We'll be sorting, so copy our polygon list into a list of polygon pointers for faster sorting

	RadPrimPointerArray	ptrArray;
	{
		// Reserve for speed

		ptrArray.reserve(polygons.size());

		for (RadPrimList::node *i = polygons.head(); i; i = i->next())
		{
			ptrArray += &i->data();
		}
	}

	// Sort the list

	qsort(static_cast<void *>(&ptrArray[0]), ptrArray.size(), sizeof(RadPrimPointer), planeCompare);

	progress.setCurrentPercent(20);

	// Build a primary list of Combined polygons... these are all polygons that share the same plane, but are not necessarily
	// connected
	{
		float	lastD = ptrArray[0]->plane().D() + 1000; // make sure the 'last' value is _not_ the same as the first

		for (unsigned int i = 0; i < ptrArray.size(); ++i)
		{
			RadPrim &	prim = *ptrArray[i];

			float	dist = fstl::abs(prim.plane().D() - lastD);
			if (dist > epsilon)
			{
				CombinedPoly	cp;
				cpl += cp;
				lastD = prim.plane().D();
			}

			// Add this poly to the last Combined primitive in the list

			cpl.tail()->data().primitives() += &prim;
		}
	}

	progress.setCurrentPercent(40);

	// The list of Combined polygons contains pieces with the same D, but not necessarily the same normal. We'll also separate
	// polygons that don't have the same material properties (like illumination color)...
	{
		for (CombinedPolyList::node *i = cpl.head(); i; i = i->next())
		{
			CombinedPoly &	cp = i->data();

			// We'll be setting some polygons aside in a new Combined polygon...

			CombinedPoly	keepCP;
			CombinedPoly	tossCP;

			// Visit each polygon in the list

			geom::Vector3	lastNormal = cp.primitives()[0]->plane().normal();
			geom::Color3	lastIllumination = cp.primitives()[0]->illuminationColor();
			geom::Color3	lastReflectance = cp.primitives()[0]->reflectanceColor();
			keepCP.primitives() += cp.primitives()[0];

			for (unsigned int j = 1; j < cp.primitives().size(); ++j)
			{
				RadPrim &	prim = *cp.primitives()[j];
				unsigned int	paIndex = prim.calcPrimaryAxisIndex();

				// If this primitive is very different from the last normal, shove it in a new Combined poly

				if ((prim.plane().normal() ^ lastNormal) > 1-epsilon && prim.illuminationColor() == lastIllumination && prim.reflectanceColor() == lastReflectance)
				{
					keepCP.primitives() += &prim;
				}
				else
				{
					tossCP.primitives() += &prim;
				}
			}

			// What's the jury say? Do we keep them all?

			if (!tossCP.primitives().size()) continue;

			// We're tossing some and keeping some...

			cp.primitives() = keepCP.primitives();
			cpl += tossCP;
		}
	}

	progress.setCurrentPercent(60);

	// Our list still isn't done yet... We need to go through and separate Combined polygons by those polygons that contain
	// connected points (yes, points, not edges -- fortunately, this is easier :)
	{
		for (CombinedPolyList::node *i = cpl.head(); i; i = i->next())
		{
			CombinedPoly &	cp = i->data();

			// We'll be setting some polygons aside in a new Combined polygon...

			CombinedPoly	keepCP;
			CombinedPoly	tossCP = cp;

			// First polygon into the keep list, the rest in the toss list

			keepCP.primitives() += tossCP.primitives()[0];
			tossCP.primitives().erase(0, 1);

			// List of points from the keep list

			geom::Vector3Array	points = keepCP.primitives()[0]->xyz();

			// Go through the toss list, over and over, adding any primitives to the keep list that match the points list.
			// Also, each time a toss polygon is added, we add its points to the points list, so that we compare future
			// primitives to those points. After all is said and done, we'll have a set of primitives that contain
			// connected points, even if the poitns are connected over a series of polygons (a connects to be, which
			// connects to c which connects do d, but a and d do not directly connect.) Hope that makes sense! :)

			while (tossCP.primitives().size())
			{
				// Visit each polygon in the toss list and see if it can be moved to the keep list

				bool	found = false;

				for (unsigned int j = 0; j < tossCP.primitives().size() && !found; ++j)
				{
					RadPrim &	prim = *tossCP.primitives()[j];

					for (unsigned int k = 0; k < points.size() && !found; ++k)
					{
						for (unsigned int l = 0; l < prim.xyz().size() && !found; ++l)
						{
							// If we found one, move this point over and start the process over again

							if (prim.xyz()[l] == points[k])
							{
								points += prim.xyz();
								keepCP.primitives() += &prim;
								tossCP.primitives().erase(j, 1);
								found = true;
							}
						}
					}
				}

				// If we never found one, we're done

				if (!found) break;
			}

			// What's the jury say? Do we keep them all?

			if (!tossCP.primitives().size()) continue;

			// We're tossing some and keeping some...

			cp.primitives() = keepCP.primitives();
			cpl += tossCP;
		}
	}

	progress.setCurrentPercent(80);

	// Generate mapping coordinates...
	{
		for (CombinedPolyList::node * i = cpl.head(); i; i = i->next())
		{
			CombinedPoly &	cp = i->data();
			cp.mapWorldTexture(uTexelsPerUnit(), vTexelsPerUnit());
		}
	}

	progress.setCurrentPercent(100);

	// Done

	return true;
}

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

bool	LMapGen::clipCombinedPolygons(ProgressDlg & progress, CombinedPolyList & cpl, RadPrimList & polygons, const unsigned int limitU, const unsigned int limitV) const
{
	// Scan the list of Combined polygons, looking for those that need to be clipped. Note that if we do clip, we'll be
	// adding them to the end of the list that we're currently scanning. But that's okay, because that works fine. :)

	progress.setCurrentStatus("Clipping polygons to lightmaps");

	unsigned int	idx = 0;
	for (CombinedPolyList::node * i = cpl.head(); i; i = i->next(), ++idx)
	{
		if (!(idx & 0xf))
		{
			progress.setCurrentPercent(static_cast<float>(idx) / static_cast<float>(cpl.size()) * 100.0f);
			if (progress.stopRequested()) throw "";
		}

		CombinedPoly &	cp = i->data();

		// Skip those that don't need clipping

		if (cp.widthIncludingBorder() <= limitU && cp.heightIncludingBorder() <= limitV) continue;

		// We'll need a primitive, any primitive, to work with

		RadPrim &	firstPrim = *cp.primitives()[0];

		// The actual upper-left-most part of the of the upper-left-most lightmap texel

		geom::Point2	minUV = geom::Point2(static_cast<float>(cp.minU()), static_cast<float>(cp.minV()));

		// The delta that goes from a vertex (any vertex) to the point in 3-space where the upper-left texel begins

		geom::Vector2	delta2 = minUV - firstPrim.uv()[0];

		// Find the upper-left 3D coordinate

		geom::Point3	minXYZ = firstPrim.xyz()[0] + firstPrim.uXFormVector() * delta2.u() + firstPrim.vXFormVector() * delta2.v();

		// Two planes: one horizontal and one vertical for slicing up a grid of patches and elements

		geom::Plane3	uPlane(minXYZ, firstPrim.plane().normal() % firstPrim.vXFormVector());
		geom::Plane3	vPlane(minXYZ, firstPrim.plane().normal() % firstPrim.uXFormVector());
		{
			// Make sure these planes face the interior of the primitive

			geom::Point3	primCenter = firstPrim.calcCenterOfMass();
			if (uPlane.halfplane(primCenter) < 0) uPlane.vector() = - uPlane.vector();
			if (vPlane.halfplane(primCenter) < 0) vPlane.vector() = - vPlane.vector();
		}

		// We'll shove our newly clipped polygons over here...

		CombinedPoly	newCPu;
		CombinedPoly	newCPv;

		// Slice and dice: first pass, uPlane...
		{
			// We move our vPlane far enough to cover the width of an entire lightmap. Note that we need to subtract
			// 2 for the pixel buffer, but we also need to subtract one more, because of the way the math works out.

			uPlane.origin() += firstPrim.uXFormVector() * static_cast<float>(lightmapWidth() - borderPixels()*2 - 1);

			for (unsigned int j = 0; j < cp.primitives().size();)
			{
				RadPrim &	prim = *cp.primitives()[j];

				// Slice it

				RadPrim	back;
				prim.bisect(uPlane, back);

				// If it's entirely on the back-side, put it back and skip it (it never got clipped)

				if (!prim.xyz().size())
				{
					prim = back;
					++j;
					continue;
				}

				// If it's entirely on the front side, it gets moved to the new CP

				if (!back.xyz().size())
				{
					cp.primitives().erase(j, 1);
					newCPu.primitives() += &prim;
					continue;
				}

				// We got a clip. We add the front side to the new CP and keep the back-side

				polygons += prim;
				newCPu.primitives() += &polygons.tail()->data();
				prim = back;
				++j;
			}
		}

		// ...second pass, vPlane
		{
			// We move our vPlane far enough to cover the width of an entire lightmap. Note that we need to subtract
			// 2 for the pixel buffer, but we also need to subtract one more, because of the way the math works out.

			vPlane.origin() += firstPrim.vXFormVector() * static_cast<float>(lightmapHeight() - borderPixels()*2 - 1);

			for (unsigned int j = 0; j < cp.primitives().size();)
			{
				RadPrim &	prim = *cp.primitives()[j];

				// Slice it

				RadPrim	back;
				prim.bisect(vPlane, back);