lmapgen.cpp

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

				// 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);
					newCPv.primitives() += &prim;
					continue;
				}

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

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

		// Our new Combined primitives

		if (newCPu.primitives().size())
		{
			newCPu.calcExtents();
			cpl += newCPu;
		}

		if (newCPv.primitives().size())
		{
			newCPv.calcExtents();
			cpl += newCPv;
		}

		// In case we updated the CP, recalc its extents

		cp.calcExtents();
	}

	// Remove empty Combined polygons
	{
		for (CombinedPolyList::node * i = cpl.head(); i;)
		{
			CombinedPoly &	cp = i->data();
			if (!cp.primitives().size())
			{
				CombinedPolyList::node * next = i->next();
				cpl.erase(i, 1);
				i = next;
			}
			else
			{
				i = i->next();
			}
		}
	}

	return true;
}

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

bool	LMapGen::populateLightmaps(ProgressDlg & progress, CombinedPolyList & cpl, RadLMapArray & lightmaps, const unsigned int limitU, const unsigned int limitV) const
{
	progress.setCurrentStatus("Populating lightmaps");

	unsigned int	total = 0;
	unsigned int	lightmapCount = 0;

	for(;;)
	{
		progress.setCurrentPercent(static_cast<float>(total) / static_cast<float>(cpl.size()) * 100.0f);
		if (progress.stopRequested()) throw "";

		unsigned int	count = populateLightmap(cpl, lightmapCount, Rect(0, 0, limitU, limitV));
		if (!count) break;
		total += count;
		++lightmapCount;
	}

	// Make sure we actually mapped all polygons

	if (total != cpl.size()) return false;

	// Generate lightmaps

	lightmaps.erase();
	RadLMap		blank(limitU, limitV);
	lightmaps.populate(blank, lightmapCount);

	for (unsigned int i = 0; i < lightmapCount; ++i)
	{
		lightmaps[i].id() = i;
	}

	// Done

	return true;
}

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

unsigned int	LMapGen::populateLightmap(CombinedPolyList & cpl, const unsigned int id, Rect rect) const
{
	// Get the width/height of this rectangle

	if (!rect.width() || !rect.height()) return 0;

	// We'll be building a list of available rects, the input rect is the primer

	Rect::RectList	availableRects;
	availableRects += rect;

	// Used to keep track of the number of Combined polygons assigned to this lightmap

	unsigned int	assignedCount = 0;

	// Loop until we run out of useful lightmap area

	while(availableRects.size())
	{
		// Find the largest rect

		Rect	workingRect;
		{
			Rect::RectList::node *	largestRect = static_cast<Rect::RectList::node *>(0);
			unsigned int		largestArea = 0;
			for (Rect::RectList::node * i = availableRects.head(); i; i = i->next())
			{
				Rect &		r = i->data();
				unsigned int	area = r.area();

				if (area > largestArea)
				{
					largestArea = area;
					largestRect = i;
				}
			}

			// If we didn't find one, bail (should never happen, but what the heck)

			if (!largestRect) break;

			// Get a working copy, because we're about to remove it from the list

			workingRect = largestRect->data();

			// Remove this rect from the list of available rects

			availableRects.erase(largestRect, 1);
		}

		// Is this rect primarily horizontal or vertical?

		bool	primarilyHorizontal = workingRect.width() >= workingRect.height();

		// Using the current rect, find the largest Combined polygon that fits

		Rect::RectList	occupiedRects;
		{
			unsigned int	maxArea = 0;
			CombinedPoly *	maxCP = static_cast<CombinedPoly *>(0);

			for (CombinedPolyList::node * i = cpl.head(); i; i = i->next())
			{
				CombinedPoly &	cp = i->data();
				if (cp.complete()) continue;

				// Make sure the orientation matches

				cp.setOrientation(primarilyHorizontal);

				// If it won't fit, skip it
				
				if (workingRect.width() < cp.widthIncludingBorder() || workingRect.height() < cp.heightIncludingBorder()) continue;

				// Track the piece with the most area

				if (cp.areaIncludingBorder() > maxArea)
				{
					maxArea = cp.areaIncludingBorder();
					maxCP = & cp;
				}
			}

			// If we didn't find a match, then this rect is too small, so skip it

			if (!maxCP) continue;

			// We found a match, set it up

			maxCP->offsetU() = workingRect.minX();
			maxCP->offsetV() = workingRect.minY();
			maxCP->lightmapID() = id;
			maxCP->complete() = true;

			// Remap it

			maxCP->remap();

			// Keep track of how many Combined polygons were assigned

			assignedCount++;

			// Add the rects from the primitives to the occupiedRects list

			RadPrimPointerArray &	primArray = maxCP->primitives();
			for (unsigned int j = 0; j < primArray.size(); ++j)
			{
				RadPrim &	prim = *primArray[j];

				// Get the rect for this primitive

				Rect		occupiedRect;
				prim.calcIntegerUVExtents(occupiedRect.minX(), occupiedRect.maxX(), occupiedRect.minY(), occupiedRect.maxY());

				// Account for the pixel border

				occupiedRect.minX() -= borderPixels();
				occupiedRect.minY() -= borderPixels();
				occupiedRect.maxX() += borderPixels() + 1;
				occupiedRect.maxY() += borderPixels() + 1;

				// Add it to the occupied list

				occupiedRects += occupiedRect;
			}
		}

		// -----------------------------------------------------------------------------------------------------------------
		// The following code is a bit cumbersome because we're working with multiple lists, so let's clarify what's going
		// on.
		//
		// We've got these lists:
		//
		//  * availableRects - this is a list of rectangular regions within the lightmap that are completely available.
		//
		//  * workingList - this list is the list of rectangles that have been removed from the available list because
		//    they overlap the Combined polygon that we're currently working with. However, the Combined polygon may not be
		//    completely covering this rectangle. So we want to take the pieces that are still available (within this
		//    workingList) and return them back to the availableRects list.
		//
		//  * occupiedRects - this is the list of rects from the Combined polygon. When all is said and done, these rects
		//    should not overlap any rects in the availableRects list. This, after all, is our goal.
		//
		// ** Note about the block of pseudo-code below: I wrote this to help keep it straight in my mind. Chances are, the
		//    actual implementation won't resemble this, or it may lose any resemblance over time and maintainence. Don't
		//    believe everything you read in this pseudo-code. I'm leaving it in here only because (1) it seems like a waste
		//    to remove it, and (2) it might give you some insight as to the original intent of this code. If you really
		//    want to know what's going on, read the actual code (below this comment block) and follow the comments.
		//
		//	// Keep slicing until we can't slice anything else
		//
		//	for (;;)
		//	{
		//		unsigned int		largestArea = 0;
		//		RectList::node *	largestOccupiedRect;
		//		RectList::node *	largestWorkingRect;
		//
		//		for (each rect in workingList)
		//		{
		//			Rect	workingRect = current rect from the workingList;
		//
		//			for (each rect in occupiedRects)
		//			{
		//				Rect	occupiedRect = current rect from the occupiedRects;
		//
		//				clip the occupiedRect to the workingRect, skip this occupied rect if no overlap;
		//
		//				Find the four pieces of working rect that extened past the four extents of occupiedRect;
		//
		//				Find the largest area of those four pieces;
		//
		//				if (any of those four pieces is larger than the current largestArea)
		//				{
		//					largestArea = largestPiece.area();
		//					largestOccupiedRect = occupiedRect's node from the list;
		//					largestWorkingRect = workingRect's node from the list;
		//				}
		//			}
		//		}
		//
		//		// If there were no overlaps, we're done
		//
		//		if (!largestArea) break;
		//
		//		// We now have the best cut from all of the working rects and occupied rects. We'll slice up the working rect
		//		// into four pieces (ignoring those pieces that have no area) and replace it in the list with the fragments.
		//
		//		[do what the comment above says :]
		//	}
		//
		//	// Okay.. at this point, we've sliced up the working list and removed those portions of it that contain the occupied
		//	// list. These pieces are now available... add them to the availableList.
		//
		//	availableList += workingList;
		//
		// -----------------------------------------------------------------------------------------------------------------
		
		// Our working list gets primed with the one rect that covers the entire region of the CombinedPoly's area within
		// the lightmap.

		Rect::RectList	workingRects;
		workingRects += workingRect;

		// Keep slicing until we can't slice anything else

		for (;;)
		{
			Rect::RectArray		largestPieces;
			unsigned int		largestArea = 0;
			Rect::RectList::node *	largestWorkingRect = static_cast<Rect::RectList::node *>(0);

			for (Rect::RectList::node * i = workingRects.head(); i; i = i->next())
			{
				Rect &	workingRect = i->data();

				for (Rect::RectList::node * j = occupiedRects.head(); j; j = j->next())
				{
					Rect	occupiedRect = j->data();

					// Find the (up to) four pieces of workingRect that extened past the four extents of
					// occupiedRect. This is effectively a boolean subtraction. Fortunately, these are
					// rects we're dealing with. :)

					bool	emptyResult;
					Rect::RectArray	nonOverlappingRects = workingRect.booleanSubtract(occupiedRect, emptyResult);

					// If we get an empty result, we need to remove it from the list without adding any
					// pieces.

					if (emptyResult)
					{
						largestWorkingRect = i;
						largestPieces.erase();
						break;
					}

					// If nothing exists, skip it

					if (!nonOverlappingRects.size()) continue;

					// Find the largest area the boolean result pieces

					unsigned int	maxArea = nonOverlappingRects[0].area();
					for (unsigned int k = 1; k < nonOverlappingRects.size(); ++k)
					{
						unsigned int	a = nonOverlappingRects[k].area();
						if (a > maxArea) maxArea = a;
					}

					// Is the largest of the four pieces larger than the largestArea thus far?

					if (maxArea > largestArea)
					{
						largestArea = maxArea;
        					largestWorkingRect = i;
						largestPieces = nonOverlappingRects;
					}
				}
			}

			// If there were no overlaps, we're done

			if (!largestWorkingRect) break;

			// We now have the best cut from all of the working rects and occupied rects. We also have the sliced-up
			// fragments of the working rect. So replace the working rect with those fragments that have any area.

			workingRects.erase(largestWorkingRect, 1);

			for (unsigned int j = 0; j < largestPieces.size(); j++)
			{
				Rect &	piece = largestPieces[j];
				if (piece.area()) workingRects += piece;
			}
		}

		// Okay.. at this point, we've sliced up the working list and removed those portions of it that contain the occupied
		// list. These pieces are now available... add them to the availableList.

		availableRects += workingRects;

		// Go through the available Rects and merge rects wherever possible. We merge based on largest area.

		for (;;)
		{
			// Find the largest result of two combined rects

			Rect::RectList::node *	aRect = static_cast<Rect::RectList::node *>(0);
			Rect::RectList::node *	bRect = static_cast<Rect::RectList::node *>(0);
			unsigned int		largestArea = 0;

			for (Rect::RectList::node * i = availableRects.head(); i; i = i->next())
			{
				Rect &	ar = i->data();

				for (Rect::RectList::node * j = i->next(); j; j = j->next())
				{
					Rect &	br = j->data();

					// Share vertical edge?

					if (!ar.canMergeWith(br)) continue;

					// What's the conbined area?

					unsigned int	combinedArea = ar.area() + br.area();

					// Largest area thus far?

					if (combinedArea > largestArea)
					{
						largestArea = combinedArea;
						aRect = i;
						bRect = j;
					}
				}
			}

			// Nothing to combine?

			if (!aRect || !bRect) break;

			// Get the combined rect

			Rect	combinedRect;
			combinedRect.boundingRect(aRect->data(), bRect->data());

			// Okay, we'll remove the two rects from the list and add their combined rect

			availableRects.erase(aRect, 1);
			bRect->data() = combinedRect;
		}
	}

	// Done

	return assignedCount;
}

// ---------------------------------------------------------------------------------------------------------------------------------
// LMapGen.cpp - End of file
// ---------------------------------------------------------------------------------------------------------------------------------