/*
** Command & Conquer Renegade(tm)
** Copyright 2025 Electronic Arts Inc.
**
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation, either version 3 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program. If not, see .
*/
/***********************************************************************************************
*** Confidential - Westwood Studios ***
***********************************************************************************************
* *
* Project Name : LightMap *
* *
* $Archive:: /Commando/Code/Tool $*
* *
* $Author:: Ian_l $*
* *
* $Modtime:: 7/09/01 4:30p $*
* *
* $Revision:: 50 $*
* *
*---------------------------------------------------------------------------------------------*
* Functions: *
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
// Includes.
#include "StdAfx.h"
#include "LightMap.h"
#include "LightmapPacker.h"
#include "OptionsDialog.h"
#include "StringBuilder.h"
#include "Targa.h"
#include "TextureNameNode.h"
#include "srFilter.hpp"
#include
#include
#include
#include
// Defines.
#define TEMPORARY_DIRECTORY_NAME "~L" // Name of temporary directory used to store packed lightmaps.
#define PAGE_WIDTH 256 // Width & height of page in texels.
#define PAGE_HEIGHT 256 // NOTE: Elected to use the biggest texture size that is
// supported by the gamut of PC 3D graphics hardware in order
// to maximize no. of lightmaps packed per page and therefore
// minimize no. of texture swaps per rendered polygon.
#define PACKING_BYTES (1024 * 1024) // No. of page bytes to consider for packing the current lightmap.
#define ASSET_EXTENSION ".tga" // Extension (and file type) of lightmap assets.
// Static data.
unsigned LightmapPacker::_BasePageIndex = 0;
char LightmapPacker::_Statistics [LightmapPacker::STATISTICS_COUNT][LightmapPacker::STATISTICS_STRING_SIZE] = {
"No data available",
"No data available",
"No data available",
"No data available",
"No data available",
"No data available",
"No data available",
"No data available",
"No data available",
"No data available"
};
/***********************************************************************************************
* LightmapPacker::LightmapPacker -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
LightmapPacker::LightmapPacker()
{
char pathname [_MAX_PATH];
OptionsDialog options;
// Initialize.
FillColor = options.Get_Fill_Color();
FilterError = pow (options.Get_Filter_Error() * 4.919e-3l, 2.5l); // Map s.t. 50th percentile -> 0.03% RGB error.
SampleRate = options.Get_Sample_Rate();
PageBitDepth = options.Get_Bit_Depth();
CurrentPageIndex = -1;
Reset_Statistics();
// Recreate the asset directory.
strcpy (pathname, theApp.Working_Path());
strcat (pathname, Asset_Directory());
// Can the asset directory can be successfully created?
if (_mkdir (pathname) == 0) {
_BasePageIndex = 0;
}
// Create the placeholder texture name node.
strcpy (pathname, theApp.Working_Path());
strcat (pathname, "Placeholder.tga");
PlaceholderTextureNameNodePtr = new TextureNameNode (pathname);
ASSERT (PlaceholderTextureNameNodePtr != NULL);
}
/***********************************************************************************************
* LightmapPacker::Finish -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
LightmapPacker::Finish()
{
// For each page...
for (int pageindex = 0; pageindex < PagePtrs.Count(); pageindex++) {
char pagepathname [_MAX_PATH];
char *errormessage;
// Pad fill color.
PagePtrs [pageindex]->Fill (FillColor);
// Update statistics about the page.
Update_Statistics (*PagePtrs [pageindex]);
// Save the page. Report any error.
strcpy (pagepathname, theApp.Working_Path());
strcat (pagepathname, Lightmap_Pathname (pageindex));
errormessage = PagePtrs [pageindex]->Save (pagepathname);
if (errormessage != NULL) throw (errormessage);
}
_BasePageIndex += PagePtrs.Count();
Collate_Statistics();
}
/***********************************************************************************************
* LightmapPacker::~LightmapPacker -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: Do not throw any exceptions in this (and any other) destructor because this *
* destructor can itself be called during the exception as part of its 'clean-up'. *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
LightmapPacker::~LightmapPacker()
{
// For each page...
for (int pageindex = 0; pageindex < PagePtrs.Count(); pageindex++) {
delete PagePtrs [pageindex];
}
delete PlaceholderTextureNameNodePtr;
}
/***********************************************************************************************
* LightmapPacker::Submit -- Submit a triangular region of a lightmap for packing. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/28/00 IML : Created. *
*=============================================================================================*/
void LightmapPacker::Submit (PackingTriangle *principaltriangleptr, const DynamicVectorClass &adjtriangles)
{
const unsigned normalgroupid = 0;
const unsigned placeholdergroupid = 1;
TrianglePacker *trianglepackerptr, *mergedpackerptr;
ASSERT (principaltriangleptr != NULL);
// Is there an associated texture?
if (principaltriangleptr->TextureNameNodePtr == NULL) {
static const float _placeholderuvs [Triangle::VERTICES_COUNT][2] =
{
{0.0f, 0.0f},
{1.0f, 0.0f},
{0.0f, 1.0f},
};
DynamicVectorClass noadjtriangles;
// Substitute a placeholder texture.
principaltriangleptr->TextureNameNodePtr = PlaceholderTextureNameNodePtr;
for (unsigned v = 0; v < Triangle::VERTICES_COUNT; v++) {
principaltriangleptr->Vertices [v].UV.X = _placeholderuvs [v][0];
principaltriangleptr->Vertices [v].UV.Y = _placeholderuvs [v][1];
}
// Create a triangle packer from the modified principal triangle with no adjacent triangles.
// NOTE: Use a 'placeholder group' ID to indicate to the triangle packer that it should not be merged with non-placeholder triangles.
trianglepackerptr = new TrianglePacker (principaltriangleptr, noadjtriangles, placeholdergroupid, EDGE_BLEND_THICKNESS, SampleRate, FillColor);
ASSERT (trianglepackerptr != NULL);
} else {
// Create a triangle packer from the principal and adjacent triangles.
trianglepackerptr = new TrianglePacker (principaltriangleptr, adjtriangles, normalgroupid, EDGE_BLEND_THICKNESS, SampleRate, FillColor);
ASSERT (trianglepackerptr != NULL);
}
while (trianglepackerptr != NULL) {
mergedpackerptr = trianglepackerptr;
trianglepackerptr = Merge (mergedpackerptr);
}
TrianglePackerPtrs.Add (mergedpackerptr);
// Statistics: each submission contains one triangular principal face.
FaceCount++;
}
/***********************************************************************************************
* LightmapPacker::Merge -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/28/00 IML : Created. *
*=============================================================================================*/
TrianglePacker *LightmapPacker::Merge (TrianglePacker *trianglepackerptr)
{
TrianglePacker *resultantpackerptr;
// See if the triangle packer can be merged with an existing triangle packer.
resultantpackerptr = NULL;
for (int t = 0; t < TrianglePackerPtrs.Count(); t++) {
TrianglePacker *mergedpackerptr;
mergedpackerptr = TrianglePackerPtrs [t]->Merge (*trianglepackerptr);
if (mergedpackerptr != NULL) {
// Does the merged packer fit within the maximum page size?
if ((mergedpackerptr->Width() <= PAGE_WIDTH) && (mergedpackerptr->Height() <= PAGE_HEIGHT)) {
unsigned mergedarea, unmergedarea;
// Is the merged packer smaller in area than the sum of the two unmerged packers?
mergedarea = mergedpackerptr->Width() * mergedpackerptr->Height();
unmergedarea = (trianglepackerptr->Width() * trianglepackerptr->Height()) + (TrianglePackerPtrs [t]->Width() * TrianglePackerPtrs [t]->Height());
if (mergedarea <= unmergedarea) {
bool success;
// Replace the two unmerged packers with the merged packer.
delete trianglepackerptr;
delete TrianglePackerPtrs [t];
success = TrianglePackerPtrs.Delete (t);
ASSERT (success);
resultantpackerptr = mergedpackerptr;
break;
}
}
}
}
return (resultantpackerptr);
}
/***********************************************************************************************
* LightmapPacker::Pack -- Pack all the triangular regions submitted thus far. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 05/18/00 IML : Created. *
*=============================================================================================*/
void LightmapPacker::Pack (ProceduralTexture *proceduraltexture)
{
TargaLoader targaloader (SampleRate, FillColor);
// For each triangle packer...
for (int t = 0; t < TrianglePackerPtrs.Count(); t++) {
const unsigned rescalethreshold = 16; // When snapping to even dimension, 'round down' if above this size -
// otherwise 'round up'.
TrueColorTarga rasterizedtarga;
unsigned unscaledwidth, unscaledheight;
unsigned clampedwidth, clampedheight;
unsigned padwidth, padheight;
// Rasterize the triangle packer.
TrianglePackerPtrs [t]->Rasterize (targaloader, proceduraltexture, rasterizedtarga);
// Scale targa according to user-specified filter error.
unscaledwidth = rasterizedtarga.Width();
unscaledheight = rasterizedtarga.Height();
rasterizedtarga.Scale (FilterError);
// Scale targa to maximum page size (taking into account edge thickness).
ASSERT (PAGE_WIDTH > (EDGE_BLEND_THICKNESS * 2));
ASSERT (PAGE_HEIGHT > (EDGE_BLEND_THICKNESS * 2));
clampedwidth = MIN (PAGE_WIDTH - (EDGE_BLEND_THICKNESS * 2), rasterizedtarga.Width());
clampedheight = MIN (PAGE_HEIGHT - (EDGE_BLEND_THICKNESS * 2), rasterizedtarga.Height());
if ((clampedwidth < rasterizedtarga.Width()) || (clampedheight < rasterizedtarga.Height())) {
// Statistics: update no. of oversize targas.
OversizeCount++;
}
// Snap to even dimensions.
// NOTE: This will reduce texel bleeding as a side effect of mip-mapping or rendering at reduced resolutions.
ASSERT (rescalethreshold < PAGE_WIDTH);
ASSERT (rescalethreshold < PAGE_HEIGHT);
if (clampedwidth > rescalethreshold) {
clampedwidth -= (clampedwidth & 0x1);
} else {
clampedwidth += (clampedwidth & 0x1);
}
if (clampedheight > rescalethreshold) {
clampedheight -= (clampedheight & 0x1);
} else {
clampedheight += (clampedheight & 0x1);
}
if (clampedwidth != rasterizedtarga.Width() || clampedheight != rasterizedtarga.Height()) {
rasterizedtarga.Scale (clampedwidth, clampedheight);
}
// Add pad texels to compensate for edge texels that may have been lost due to filtered scaling and scaling to clamp to maximum page size.
// NOTE: Pad to a multiple of 2 to maintain 'even' dimensions.
padwidth = 2 * ceilf (EDGE_BLEND_THICKNESS * (1.0f - (((float) rasterizedtarga.Width()) / ((float) unscaledwidth))));
padheight = 2 * ceilf (EDGE_BLEND_THICKNESS * (1.0f - (((float) rasterizedtarga.Height()) / ((float) unscaledheight))));
rasterizedtarga.Pad (padwidth, padheight, FillColor, TrianglePackerPtrs [t]->Principal_Triangles());
// Pack the targa into a lightmap page.
Pack (rasterizedtarga, TrianglePackerPtrs [t]->Principal_Triangles());
// Statistics: add targa's area before and after scaling.
// NOTE: Although this is not desirable, it is possible for scaling to increase the targa's area.
UnscaledTexelCount += unscaledwidth * unscaledheight;
ScaledTexelCount += rasterizedtarga.Width() * rasterizedtarga.Height();
// Update statistics about the triangle packer.
Update_Statistics (*TrianglePackerPtrs [t]);
// Clean-up.
delete TrianglePackerPtrs [t];
}
// Reset.
TrianglePackerPtrs.Clear();
}
/***********************************************************************************************
* TargaLoader::TargaLoader -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/30/00 IML : Created. *
*=============================================================================================*/
TargaLoader::TargaLoader (float samplerate, W3dRGBStruct fillcolor)
{
const unsigned cachesize = 1024; // Maximum no. of entries in cache.
const unsigned cleanuplistsize = 256; // Initial size of clean-up list.
SampleRate = samplerate;
FillColor = fillcolor;
// Size the cache and the clean-up list.
Cache.Resize (cachesize);
CleanupList.Set_Growth_Step (cleanuplistsize);
}
/***********************************************************************************************
* TargaLoader::~TargaLoader -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/30/00 IML : Created. *
*=============================================================================================*/
TargaLoader::~TargaLoader()
{
// Delete the targas in the clean-up list.
for (int c = 0; c < CleanupList.Count(); c++) {
ASSERT (CleanupList [c] != NULL);
delete CleanupList [c];
}
}
/***********************************************************************************************
* TargaLoader::Load -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/08/00 IML : Created. *
*=============================================================================================*/
TrueColorTarga *TargaLoader::Load (const Triangle &triangle)
{
TrueColorTarga *targaptr;
unsigned index;
index = Index (triangle.TextureID);
// Is there a cache miss?
if ((Cache [index].Ptr == NULL) || (Cache [index].ID != triangle.TextureID)) {
char *errormessage;
TextureNameNode *pathnamenodeptr;
Vector2 t;
Vector3 p;
float length, localsamplerate, scalefactor;
// There must be a texture pathname.
pathnamenodeptr = triangle.TextureNameNodePtr;
ASSERT (pathnamenodeptr != NULL);
targaptr = new TrueColorTarga;
ASSERT (targaptr != NULL);
// Read the first targa asset file. Report any error.
errormessage = targaptr->Load (pathnamenodeptr->TextureName);
if (errormessage != NULL) throw (errormessage);
// Replace fill texel with padding. If the targa is all fill color substitute the replacement targa.
targaptr->Fill (FillColor);
// Read all remaining targa asset files and add them to the first.
pathnamenodeptr = pathnamenodeptr->Next;
while (pathnamenodeptr != NULL) {
TrueColorTarga additivetarga;
errormessage = additivetarga.Load (pathnamenodeptr->TextureName);
if (errormessage != NULL) throw (errormessage);
// Replace fill texel with padding.
additivetarga.Fill (FillColor);
targaptr->Add (additivetarga);
// Advance to next targa asset.
pathnamenodeptr = pathnamenodeptr->Next;
}
// Calculate the sample rate of the targa (no. of texels per unit length).
// NOTE: A typical length unit is metres (it does not matter which it is).
t = triangle.Vertices [1].UV - triangle.Vertices [0].UV;
t.Scale (targaptr->Width(), targaptr->Height());
p = triangle.Vertices [1].Point - triangle.Vertices [0].Point;
length = p.Length();
// Degenerate triangles are not allowed!
ASSERT (length > 0.0f);
localsamplerate = t.Length() / length;
// In the event that the targa is sampled, maximize sampling accuracy by scaling
// to match the global sample rate.
// NOTE: There is no advantage to scaling-up.
scalefactor = SampleRate / localsamplerate;
if (scalefactor < 1.0f) {
targaptr->Scale (targaptr->Width() * scalefactor, targaptr->Height() * scalefactor);
}
// Add the existing targa to the clean-up list for removal later (in the destructor).
// NOTE: It cannot be deleted yet because another object may be referencing it.
if (Cache [index].Ptr != NULL) {
CleanupList.Add (Cache [index].Ptr);
}
// Update the cache entry.
Cache [index].ID = triangle.TextureID;
Cache [index].Ptr = targaptr;
} else {
// Cache hit.
targaptr = Cache [index].Ptr;
}
return (targaptr);
}
/***********************************************************************************************
* LightmapPacker::Pack -- Pack a targa into a lightmap page. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 05/19/00 IML : Created. *
*=============================================================================================*/
void LightmapPacker::Pack (TrueColorTarga &targa, DynamicVectorClass &triangleptrs)
{
const float packingerror = FilterError * 0.5f;
bool packed;
// Attempt to pack the lightmap in the current page.
if (CurrentPageIndex != -1) {
packed = PagePtrs [CurrentPageIndex]->Pack (targa, packingerror, triangleptrs);
} else {
packed = false;
}
if (!packed) {
const unsigned packingwindowsize = PACKING_BYTES / ((PAGE_WIDTH * PAGE_HEIGHT * PageBitDepth) / CHAR_BIT);
int firstpage, lastpage;
// Iterate over all existing pages (except the current page) that are in the packing window.
firstpage = PagePtrs.Count() - 1;
lastpage = MAX (firstpage - ((int) packingwindowsize) + 1, 0);
for (int pageindex = firstpage; pageindex >= lastpage; pageindex--) {
if (pageindex != CurrentPageIndex) {
packed = PagePtrs [pageindex]->Pack (targa, packingerror, triangleptrs);
if (packed) {
CurrentPageIndex = pageindex;
break;
}
}
}
// If still not packed then create a new page.
if (!packed) {
Page *pageptr;
pageptr = new Page (PageBitDepth, FillColor);
ASSERT (pageptr != NULL);
PagePtrs.Add (pageptr);
packed = pageptr->Pack (targa, packingerror, triangleptrs);
// The first lightmap packed into a page must always succeed.
ASSERT (packed);
CurrentPageIndex = PagePtrs.Count() - 1;
}
// The current page index has changed so this will incur a texture swap.
TextureSwapCount++;
}
LightmapCount++;
// Store the page index in the triangles.
for (int t = 0; t < triangleptrs.Count(); t++) {
triangleptrs [t]->PackedTextureID = CurrentPageIndex;
}
}
/***********************************************************************************************
* LightmapPacker::Lightmap_Pathname -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
const char *LightmapPacker::Lightmap_Pathname (unsigned pageindex)
{
static char _pathname [_MAX_PATH];
char filename [_MAX_FNAME];
// Build pathname of lightmap based on lightmap's index.
strcpy (_pathname, Asset_Directory());
_ultoa (_BasePageIndex + pageindex, filename, 10);
strcat (filename, ASSET_EXTENSION);
strcat (_pathname, filename);
return (_pathname);
}
/***********************************************************************************************
* LightmapPacker::Asset_Directory -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 05/15/00 IML : Created. *
*=============================================================================================*/
const char *LightmapPacker::Asset_Directory()
{
static bool _called = false;
static char _assetdirectory [_MAX_PATH];
// Optimization: only required to build asset directory once because it is invariant over
// lifetime of application.
if (!_called) {
strcpy (_assetdirectory, TEMPORARY_DIRECTORY_NAME);
strcat (_assetdirectory, theApp.Instance_Name());
strcat (_assetdirectory, "\\");
_called = true;
}
return (_assetdirectory);
}
/***********************************************************************************************
* LightmapPacker::Asset_Directory -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
const char *LightmapPacker::Asset_Directory (const char *filename)
{
static char _pathname [_MAX_PATH];
strcpy (_pathname, filename);
strcat (_pathname, "+\\");
return (_pathname);
}
/***********************************************************************************************
* LightmapPacker::Delete_Assets -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
void LightmapPacker::Delete_Assets()
{
char pathname [_MAX_PATH];
long handle;
_finddata_t fileinfo;
// Attempt to delete every file in the asset directory.
strcpy (pathname, theApp.Working_Path());
strcat (pathname, Asset_Directory());
strcat (pathname, "*");
strcat (pathname, ASSET_EXTENSION);
handle = _findfirst (pathname, &fileinfo);
if (handle != -1) {
do {
strcpy (pathname, theApp.Working_Path());
strcat (pathname, Asset_Directory());
strcat (pathname, fileinfo.name);
DeleteFile (pathname);
} while (_findnext (handle, &fileinfo) == 0);
}
// Clean-up.
_findclose (handle);
// Attempt to remove the asset directory.
strcpy (pathname, theApp.Working_Path());
strcat (pathname, Asset_Directory());
_rmdir (pathname);
}
/***********************************************************************************************
* LightmapPacker::Copy_Assets -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
void LightmapPacker::Copy_Assets (const char *pathname)
{
char savedrivename [_MAX_DRIVE];
char savedirectoryname [_MAX_DIR];
char savefilename [_MAX_FNAME];
char loadpathname [_MAX_PATH];
char savepath [_MAX_PATH];
char savepathname [_MAX_PATH];
long handle;
_finddata_t fileinfo;
// Attempt to copy every file in the load directory to the save directory.
strcpy (loadpathname, theApp.Working_Path());
strcat (loadpathname, Asset_Directory());
strcat (loadpathname, "*");
strcat (loadpathname, ASSET_EXTENSION);
handle = _findfirst (loadpathname, &fileinfo);
if (handle != -1) {
// Now we know that there are assets so create the save directory.
_splitpath (pathname, savedrivename, savedirectoryname, savefilename, NULL);
strcpy (savepath, savedrivename);
strcat (savepath, savedirectoryname);
strcat (savepath, Asset_Directory (savefilename));
_mkdir (savepath);
do {
strcpy (loadpathname, theApp.Working_Path());
strcat (loadpathname, Asset_Directory());
strcat (loadpathname, fileinfo.name);
strcpy (savepathname, savepath);
strcat (savepathname, fileinfo.name);
CopyFile (loadpathname, savepathname, FALSE);
} while (_findnext (handle, &fileinfo) == 0);
}
// Clean-up.
_findclose (handle);
}
/***********************************************************************************************
* LightmapPacker::Reset_Statistics -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
void LightmapPacker::Reset_Statistics()
{
FaceCount = 0;
LightmapCount = 0;
AdjacentFaceCount = 0;
BlendedFaceCount = 0;
EdgeBlendAreaSum = 0.0;
UnscaledTexelCount = 0;
ScaledTexelCount = 0;
ReplicaEfficiencySum = 0.0;
PackingEfficiencySum = 0.0;
TextureSwapCount = 0;
OversizeCount = 0;
AllFillColorCount = 0;
}
/***********************************************************************************************
* LightmapPacker::Update_Statistics -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
void LightmapPacker::Update_Statistics (const Page &page)
{
PackingEfficiencySum += page.Packing_Efficiency();
ReplicaEfficiencySum += page.Replica_Efficiency();
}
/***********************************************************************************************
* LightmapPacker::Update_Statistics -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/31/00 IML : Created. *
*=============================================================================================*/
void LightmapPacker::Update_Statistics (const TrianglePacker &trianglepacker)
{
AdjacentFaceCount += trianglepacker.Adjacent_Face_Count();
BlendedFaceCount += trianglepacker.Blended_Face_Count();
EdgeBlendAreaSum += trianglepacker.Edge_Blend_Area();
}
/***********************************************************************************************
* LightmapPacker::Collate_Statistics -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
void LightmapPacker::Collate_Statistics()
{
unsigned pagecount;
float adjacentfaceblendfraction, edgeblendefficiency, scalingefficiency, packingefficiency, cullingefficiency, swappingefficiency;
// Build statistics string.
adjacentfaceblendfraction = (AdjacentFaceCount > 0) ? ((float) BlendedFaceCount) / ((float) AdjacentFaceCount) : 0.0f;
edgeblendefficiency = (UnscaledTexelCount > 0) ? 1.0f - (EdgeBlendAreaSum / UnscaledTexelCount) : 0.0f;
scalingefficiency = (UnscaledTexelCount > 0) ? 1.0f - (((float) ScaledTexelCount) / ((float) UnscaledTexelCount)) : 0.0f;
pagecount = PagePtrs.Count();
packingefficiency = (pagecount > 0) ? PackingEfficiencySum / pagecount : 0.0f;
cullingefficiency = (pagecount > 0) ? ReplicaEfficiencySum / pagecount : 0.0f;
swappingefficiency = (FaceCount > 0) ? 1.0f - (((float)TextureSwapCount) / FaceCount) : 0.0f;
_snprintf (_Statistics [STATISTICS_PAGE_FORMAT], sizeof (_Statistics [STATISTICS_PAGE_FORMAT]) - 1, "%d x %d x %dbpp", PAGE_WIDTH, PAGE_HEIGHT, PageBitDepth);
_snprintf (_Statistics [STATISTICS_LIGHTMAPS_PROCESSED], sizeof (_Statistics [STATISTICS_LIGHTMAPS_PROCESSED]) - 1, "%d", LightmapCount);
_snprintf (_Statistics [STATISTICS_ADJACENT_FACE_BLEND_PERCENTAGE], sizeof (_Statistics [STATISTICS_ADJACENT_FACE_BLEND_PERCENTAGE]) - 1, "%.1f%%", adjacentfaceblendfraction * 100.0f);
_snprintf (_Statistics [STATISTICS_EDGE_BLEND_EFFICIENCY], sizeof (_Statistics [STATISTICS_EDGE_BLEND_EFFICIENCY]) - 1, "%.1f%%", edgeblendefficiency * 100.0f);
_snprintf (_Statistics [STATISTICS_SCALING_EFFICIENCY], sizeof (_Statistics [STATISTICS_SCALING_EFFICIENCY]) - 1, "%.1f%%", scalingefficiency * 100.0f);
_snprintf (_Statistics [STATISTICS_PAGES_CREATED], sizeof (_Statistics [STATISTICS_PAGES_CREATED]) - 1, "%d", pagecount);
_snprintf (_Statistics [STATISTICS_PACKING_EFFICIENCY], sizeof (_Statistics [STATISTICS_PACKING_EFFICIENCY]) - 1, "%.1f%%", packingefficiency * 100.0f);
_snprintf (_Statistics [STATISTICS_CULLING_EFFICIENCY], sizeof (_Statistics [STATISTICS_CULLING_EFFICIENCY]) - 1, "%.1f%%", cullingefficiency * 100.0f);
_snprintf (_Statistics [STATISTICS_TEXTURE_SWAP_EFFICIENCY], sizeof (_Statistics [STATISTICS_TEXTURE_SWAP_EFFICIENCY]) - 1, "%.1f%%", swappingefficiency * 100.0f);
_snprintf (_Statistics [STATISTICS_OVERSIZE_LIGHTMAPS], sizeof (_Statistics [STATISTICS_TEXTURE_SWAP_EFFICIENCY]) - 1, "%d", OversizeCount);
}
/***********************************************************************************************
* TrianglePacker::TrianglePacker -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/28/00 IML : Created. *
*=============================================================================================*/
TrianglePacker::TrianglePacker (const PackingTriangle *principaltriangleptr, const DynamicVectorClass &adjtriangles, unsigned groupid, unsigned edgeblendthickness, float samplerate, W3dRGBStruct fillcolor)
{
Projection = Get_Projection (principaltriangleptr->Normal);
GroupID = groupid;
EdgeBlendThickness = edgeblendthickness;
SampleRate = samplerate;
FillColor = fillcolor;
// Add the principal triangle.
PrincipalTriangles.Add ((PackingTriangle*) principaltriangleptr);
// Add the adjacent triangles, sorting them into the three groups COMMON, VALID & NONE.
for (int a = 0; a < adjtriangles.Count(); a++) {
if (Get_Projection (adjtriangles [a].Normal) == Projection) {
AdjacentTriangles [ADJACENT_PROJECTION_COMMON].Add (adjtriangles [a]);
} else {
if (Can_Project (adjtriangles [a].Normal)) {
AdjacentTriangles [ADJACENT_PROJECTION_VALID].Add (adjtriangles [a]);
} else {
AdjacentTriangles [ADJACENT_PROJECTION_NONE].Add (adjtriangles [a]);
}
}
}
// The triangle sets have been modifed - therefore set bounds.
Set_Bounds();
}
/***********************************************************************************************
* TrianglePacker::TrianglePacker -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/28/00 IML : Created. *
*=============================================================================================*/
TrianglePacker::TrianglePacker (const TrianglePacker &trianglepacker)
{
int t, a;
Projection = trianglepacker.Projection;
GroupID = trianglepacker.GroupID;
EdgeBlendThickness = trianglepacker.EdgeBlendThickness;
SampleRate = trianglepacker.SampleRate;
FillColor = trianglepacker.FillColor;
LowerBound = trianglepacker.LowerBound;
UpperBound = trianglepacker.UpperBound;
// Copy the principal triangles.
for (t = 0; t < trianglepacker.PrincipalTriangles.Count(); t++) {
PrincipalTriangles.Add (trianglepacker.PrincipalTriangles [t]);
}
// Copy the adjacent triangles.
for (a = 0; a < ADJACENT_PROJECTION_COUNT; a++) {
for (t = 0; t < trianglepacker.AdjacentTriangles [a].Count(); t++) {
AdjacentTriangles [a].Add (trianglepacker.AdjacentTriangles [a] [t]);
}
}
}
/***********************************************************************************************
* TrianglePacker::Reset -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/28/00 IML : Created. *
*=============================================================================================*/
void TrianglePacker::Set_Bounds()
{
const Vector2 edge (EdgeBlendThickness, EdgeBlendThickness);
Vector2 lowerbound (+FLT_MAX, +FLT_MAX);
Vector2 upperbound (-FLT_MAX, -FLT_MAX);
// Calculate the smallest bounding rectangle that will contain the projected principal triangles.
for (int t = 0; t < PrincipalTriangles.Count(); t++) {
for (int v = 0; v < Triangle::VERTICES_COUNT; v++) {
Vector2 uv;
uv = Project (PrincipalTriangles [t]->Vertices [v].Point);
lowerbound.Update_Min (uv);
upperbound.Update_Max (uv);
}
}
// Increase the bounds by the edge thickness to account for edge blending and snap to integer coordinates.
lowerbound -= edge;
upperbound += edge;
LowerBound.Set (floorf (lowerbound.U), floorf (lowerbound.V));
UpperBound.Set (ceilf (upperbound.U), ceilf (upperbound.V));
}
/***********************************************************************************************
* TrianglePacker::Edge_Blend_Area -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/28/00 IML : Created. *
*=============================================================================================*/
float TrianglePacker::Edge_Blend_Area() const
{
float principalareasum;
unsigned width, height;
principalareasum = 0.0f;
for (int t = 0; t < PrincipalTriangles.Count(); t++) {
Vector2 o, a, b;
o = Project (PrincipalTriangles [t]->Vertices [0].Point);
a = Project (PrincipalTriangles [t]->Vertices [1].Point) - o;
b = Project (PrincipalTriangles [t]->Vertices [2].Point) - o;
principalareasum += 0.5f * WWMath::Fabs (a.U * b.V - b.U * a.V);
}
width = Width();
height = Height();
ASSERT ((width * height) >= principalareasum);
return ((width * height) - principalareasum);
}
/***********************************************************************************************
* TrianglePacker::Merge -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 07/28/00 IML : Created. *
*=============================================================================================*/
TrianglePacker *TrianglePacker::Merge (const TrianglePacker &trianglepacker)
{
TrianglePacker *mergedpackerptr;
mergedpackerptr = NULL;
// Do both triangle packers have the same projection, group ID, edge blend thickness, sample rate, and fill color?
// If not, then they are not compatible packers and cannot be merged.
if ((Projection == trianglepacker.Projection) &&
(GroupID == trianglepacker.GroupID) &&
(EdgeBlendThickness == trianglepacker.EdgeBlendThickness) &&
(SampleRate == trianglepacker.SampleRate) &&
(FillColor == trianglepacker.FillColor)) {
// For each principal triangle in triangle packer...
for (int p = 0; p < trianglepacker.PrincipalTriangles.Count(); p++) {
// For each principal triangle in this...
for (int q = 0; q < PrincipalTriangles.Count(); q++) {
// Does one principal triangle abut the other?
if (trianglepacker.PrincipalTriangles [p]->Abuts (*PrincipalTriangles [q])) {
// Copy this.
mergedpackerptr = new TrianglePacker (*this);
ASSERT (mergedpackerptr != NULL);
break;
}
}
if (mergedpackerptr != NULL) break;
}
if (mergedpackerptr != NULL) {
// For each principal triangle in triangle packer...
for (int p = 0; p < trianglepacker.PrincipalTriangles.Count(); p++) {
// Add it to the merged packer.
mergedpackerptr->PrincipalTriangles.Add (trianglepacker.PrincipalTriangles [p]);
}
// Merge the adjacent triangles (do not allow duplicates).
for (int a = 0; a < ADJACENT_PROJECTION_COUNT; a++) {
for (int t = 0; t < trianglepacker.AdjacentTriangles [a].Count(); t++) {
const Triangle *triangleptr;
bool foundadjacent;
triangleptr = &(trianglepacker.AdjacentTriangles [a][t]);
foundadjacent = false;
for (int m = 0; m < AdjacentTriangles [a].Count(); m++) {
if (triangleptr->Is_Equivalent ((AdjacentTriangles [a]) [m])) {
foundadjacent = true;
break;
}
}
if (!foundadjacent) {
mergedpackerptr->AdjacentTriangles [a].Add ((trianglepacker.AdjacentTriangles [a]) [t]);
}
}
}
// The triangle sets have been modifed - therefore set bounds.
mergedpackerptr->Set_Bounds();
}
}
return (mergedpackerptr);
}
/***********************************************************************************************
* TrianglePacker::Get_Projection -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/19/00 IML : Created. *
*=============================================================================================*/
TrianglePacker::ProjectionEnum TrianglePacker::Get_Projection (const Vector3 &normal)
{
float x, y, z;
x = WWMath::Fabs (normal.X);
y = WWMath::Fabs (normal.Y);
z = WWMath::Fabs (normal.Z);
if (y >= x) {
if (y >= z) {
if (normal.Y >= 0.0f) {
return (PROJECTION_Y_POSITIVE);
} else {
return (PROJECTION_Y_NEGATIVE);
}
} else {
if (normal.Z >= 0.0f) {
return (PROJECTION_Z_POSITIVE);
} else {
return (PROJECTION_Z_NEGATIVE);
}
}
} else {
if (x >= z) {
if (normal.X >= 0.0f) {
return (PROJECTION_X_POSITIVE);
} else {
return (PROJECTION_X_NEGATIVE);
}
} else {
if (normal.Z >= 0.0f) {
return (PROJECTION_Z_POSITIVE);
} else {
return (PROJECTION_Z_NEGATIVE);
}
}
}
}
/***********************************************************************************************
* TrianglePacker::Can_Project -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/19/00 IML : Created. *
*=============================================================================================*/
bool TrianglePacker::Can_Project (const Vector3 &normal)
{
static const float _projectionnormals [PROJECTION_COUNT][3] =
{{ 0.0f, 1.0f, 0.0f},
{ 0.0f, -1.0f, 0.0f},
{ 0.0f, 0.0f, 1.0f},
{ 0.0f, 0.0f, -1.0f},
{ 1.0f, 0.0f, 0.0f},
{-1.0f, 0.0f, 0.0f}
};
const float maxprojectionangle = (80.0f * WWMATH_PI) / 180.0f; // Max. allowed angle between triangle and projection plane.
Vector3 projectionnormal;
float angle;
projectionnormal.Set (_projectionnormals [Projection][0], _projectionnormals [Projection][1], _projectionnormals [Projection][2]);
angle = acosf (Vector3::Dot_Product (normal, projectionnormal));
return (angle < maxprojectionangle);
}
/***********************************************************************************************
* TrianglePacker::Project -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/19/00 IML : Created. *
*=============================================================================================*/
Vector2 TrianglePacker::Project (const Vector3 &point) const
{
Vector2 t;
switch (Projection) {
case PROJECTION_Y_POSITIVE:
case PROJECTION_Y_NEGATIVE:
t.Set (point.X, point.Z);
break;
case PROJECTION_Z_POSITIVE:
case PROJECTION_Z_NEGATIVE:
t.Set (point.X, point.Y);
break;
case PROJECTION_X_POSITIVE:
case PROJECTION_X_NEGATIVE:
t.Set (point.Y, point.Z);
break;
}
t *= SampleRate;
return (t);
}
/***********************************************************************************************
* TrianglePacker::Rasterize -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/08/00 IML : Created. *
*=============================================================================================*/
void TrianglePacker::Rasterize (TargaLoader &targaloader, ProceduralTexture *proceduraltexture, TrueColorTarga &rasterizedtarga)
{
const unsigned pixeldepth = 24;
const unsigned sqrtforwardsamplespertexel = 4;
const unsigned sqrtbackwardsamplespertexel = 4;
const unsigned principalpriority = 2;
const unsigned adjacentpriority = 1;
// There must be at least one principal triangle to rasterize.
ASSERT (PrincipalTriangles.Count() >= 1);
unsigned width, height;
SampleSurface *forwardsurfaceptr, *backwardsurfaceptr;
int t;
unsigned projectiontrianglecount;
float right, top;
ProjectionTriangle *projectiontriangles;
Vector3 points [Triangle::VERTICES_COUNT];
Vector2 sourceuvs [Triangle::VERTICES_COUNT];
Vector2 projectionuvs [Triangle::VERTICES_COUNT];
TrueColorTarga *sourcetargaptr;
float oosqrtsamplespertexel;
Vector2 samplepoint;
int sampledt;
unsigned x, y, u, v;
float oowidth, ooheight;
width = Width();
height = Height();
// Allocate a sample surface to store destination->source (backward) samples.
backwardsurfaceptr = new SampleSurface (width, height, proceduraltexture);
ASSERT (backwardsurfaceptr != NULL);
// Allocate enough projection triangles to cover the principal triangles and those triangles that can be projected.
projectiontriangles = new ProjectionTriangle [PrincipalTriangles.Count() + AdjacentTriangles [ADJACENT_PROJECTION_COMMON].Count() + AdjacentTriangles [ADJACENT_PROJECTION_VALID].Count()];
ASSERT (projectiontriangles != NULL);
// For each principal triangle...
projectiontrianglecount = PrincipalTriangles.Count();
for (t = 0; t < (int) projectiontrianglecount; t++) {
for (int v = 0; v < Triangle::VERTICES_COUNT; v++) {
points [v] = PrincipalTriangles [t]->Vertices [v].Point;
sourceuvs [v] = PrincipalTriangles [t]->Vertices [v].UV;
projectionuvs [v] = Project (PrincipalTriangles [t]->Vertices [v].Point) - LowerBound;
}
sourcetargaptr = targaloader.Load (*PrincipalTriangles [t]);
projectiontriangles [t] = ProjectionTriangle (points, sourceuvs, sourcetargaptr, projectionuvs);
}
// For each adjacent triangle that is common or valid...
right = width;
top = height;
for (int a = ADJACENT_PROJECTION_COMMON; a <= ADJACENT_PROJECTION_VALID; a++) {
for (t = 0; t < AdjacentTriangles [a].Count(); t++) {
unsigned outcode, outcodeu, outcodev;
// Test the triangle for trivial rejection.
outcode = 0xf;
for (int v = 0; v < Triangle::VERTICES_COUNT; v++) {
projectionuvs [v] = Project (AdjacentTriangles [a] [t].Vertices [v].Point) - LowerBound;
outcodeu = (projectionuvs [v].U < 0.0f) | ((projectionuvs [v].U >= right) << 1);
outcodev = (projectionuvs [v].V < 0.0f) | ((projectionuvs [v].V >= top) << 1);
outcode &= (outcodeu | (outcodev << 2));
}
// Should the triangle be accepted (ie. not trivially rejected)?
if (outcode == 0) {
for (int v = 0; v < Triangle::VERTICES_COUNT; v++) {
points [v] = AdjacentTriangles [a] [t].Vertices [v].Point;
sourceuvs [v] = AdjacentTriangles [a] [t].Vertices [v].UV;
}
sourcetargaptr = targaloader.Load (AdjacentTriangles [a] [t]);
projectiontriangles [projectiontrianglecount] = ProjectionTriangle (points, sourceuvs, sourcetargaptr, projectionuvs);
projectiontrianglecount++;
}
}
}
// Sample the projection triangles into the backward surface.
oosqrtsamplespertexel = 1.0f / sqrtbackwardsamplespertexel;
sampledt = 0;
for (y = 0; y < height; y++) {
for (x = 0; x < width; x++) {
for (v = 0; v < sqrtbackwardsamplespertexel; v++) {
samplepoint.V = y + (v * oosqrtsamplespertexel);
for (u = 0; u < sqrtbackwardsamplespertexel; u++) {
samplepoint.U = x + (u * oosqrtsamplespertexel);
if (sampledt < PrincipalTriangles.Count()) {
if (backwardsurfaceptr->Sample (samplepoint, projectiontriangles [sampledt], principalpriority)) goto nextsample;
}
for (t = 0; t < PrincipalTriangles.Count(); t++) {
if (t != sampledt) {
if (backwardsurfaceptr->Sample (samplepoint, projectiontriangles [t], principalpriority)) {
sampledt = t;
goto nextsample;
}
}
}
if ((sampledt >= PrincipalTriangles.Count()) && (sampledt < (int) projectiontrianglecount)) {
if (backwardsurfaceptr->Sample (samplepoint, projectiontriangles [sampledt], adjacentpriority)) goto nextsample;
}
for (t = PrincipalTriangles.Count(); t < (int) projectiontrianglecount; t++) {
if (t != sampledt) {
if (backwardsurfaceptr->Sample (samplepoint, projectiontriangles [t], adjacentpriority)) {
sampledt = t;
goto nextsample;
}
}
}
nextsample:;
}
}
}
}
// If less than 50% of the texels were sampled in the backward rasterization prepare a forward rasterization.
forwardsurfaceptr = NULL;
if (backwardsurfaceptr->Sampling_Ratio() < 0.5f) {
// Allocate a sample surface to store source->destination (forward) samples.
forwardsurfaceptr = new SampleSurface (width, height, proceduraltexture);
ASSERT (forwardsurfaceptr != NULL);
for (t = 0; t < PrincipalTriangles.Count(); t++) {
Vector2 d, d0, d1, d2;
float projectionarea, maxlength, pseudoarea;
unsigned sqrtsamplecount;
float oosqrtsamplecount;
unsigned a, b;
float alpha, beta;
// Calculate the sample rate based on the triangle's projected area.
// NOTE: If the area is small relative to its longest edge use the edge length instead.
d = projectionuvs [2] - projectionuvs [0];
d0 = projectionuvs [1] - projectionuvs [0];
d1 = projectionuvs [2] - projectionuvs [1];
d2 = projectionuvs [0] - projectionuvs [2];
projectionarea = 0.5f * WWMath::Fabs (d.U * d0.V - d0.U * d.V);
maxlength = (float) WWMath::Sqrt (MAX (MAX (d0.Length2(), d1.Length2()), d2.Length2()));
pseudoarea = MAX (projectionarea, maxlength);
sqrtsamplecount = ceilf (WWMath::Sqrt (sqrtforwardsamplespertexel * sqrtforwardsamplespertexel * pseudoarea));
// Sample the projection triangle into the forward surface.
oosqrtsamplecount = 1.0f / sqrtsamplecount;
for (b = 0; b < sqrtsamplecount; b++) {
beta = b * oosqrtsamplecount;
for (a = 0; a < sqrtsamplecount; a++) {
alpha = a * oosqrtsamplecount;
if (alpha + beta <= 1.0f) {
forwardsurfaceptr->Sample (alpha, beta, projectiontriangles [t], principalpriority);
}
}
}
}
}
// Resize the targa which holds the resulting rasterization.
rasterizedtarga.Reformat (width, height, pixeldepth);
// Iterate over the backward (and possibly forward) surface and translate it into the rasterized targa.
for (y = 0; y < height; y++) {
unsigned miny, maxy, minx, maxx;
bool inrangeofprincipal;
unsigned a, b;
miny = MAX ((int) 0, ((int) y) - ((int) EdgeBlendThickness));
maxy = MIN (height - 1, y + EdgeBlendThickness);
for (x = 0; x < width; x++) {
W3dRGBStruct color;
minx = MAX ((int) 0, ((int) x) - ((int) EdgeBlendThickness));
maxx = MIN (width - 1, x + EdgeBlendThickness);
// Find out if this texel is within edge blend texels of a texel that has a 'principal sample'.
// NOTE: If so then this texel can potentially be read and therefore must contain valid data.
// Otherwise fill color will suffice.
inrangeofprincipal = false;
for (b = miny; b <= maxy; b++) {
for (a = minx; a <= maxx; a++) {
if (backwardsurfaceptr->Priority (a, b) >= principalpriority) {
inrangeofprincipal = true;
break;
}
if (forwardsurfaceptr != NULL) {
if (forwardsurfaceptr->Priority (a, b) >= principalpriority) {
inrangeofprincipal = true;
break;
}
}
}
if (inrangeofprincipal) break;
}
// Is texel within range of 'principal texel'?
if (inrangeofprincipal) {
// Does the backward surface's texel have a sample?
if (backwardsurfaceptr->Get_Color (x, y, color)) {
rasterizedtarga.Set_Color (x, y, color);
} else {
if (forwardsurfaceptr != NULL) {
if (forwardsurfaceptr->Get_Color (x, y, color)) {
rasterizedtarga.Set_Color (x, y, color);
} else {
rasterizedtarga.Set_Color (x, y, FillColor);
}
} else {
rasterizedtarga.Set_Color (x, y, FillColor);
}
}
} else {
rasterizedtarga.Set_Color (x, y, FillColor);
}
}
}
// Pad any fill color texels.
rasterizedtarga.Fill (FillColor);
// Set the packed UV's of each principal triangle to normalized projection UV's.
oowidth = 1.0f / width;
ooheight = 1.0f / height;
for (t = 0; t < PrincipalTriangles.Count(); t++) {
for (unsigned v = 0; v < Triangle::VERTICES_COUNT; v++) {
Vector2 uv;
uv = Project (PrincipalTriangles [t]->Vertices [v].Point) - LowerBound;
uv.Scale (oowidth, ooheight);
PrincipalTriangles [t]->PackedUVs [v] = uv;
}
}
// Clean-up.
if (forwardsurfaceptr != NULL) delete forwardsurfaceptr;
delete [] projectiontriangles;
delete backwardsurfaceptr;
}
/***********************************************************************************************
* ProjectionTriangle::ProjectionTriangle -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/08/00 IML : Created. *
*=============================================================================================*/
TrianglePacker::ProjectionTriangle::ProjectionTriangle (const Vector3 *points, const Vector2 *sourceuvs, const TrueColorTarga *sourcetargaptr, const Vector2 *projectionuvs)
{
Points [0] = points [0];
Points [1] = points [1] - points [0];
Points [2] = points [2] - points [0];
SourceUVs [0] = sourceuvs [0];
SourceUVs [1] = sourceuvs [1] - sourceuvs [0];
SourceUVs [2] = sourceuvs [2] - sourceuvs [0];
ProjectionUVs [0] = projectionuvs [0];
ProjectionUVs [1] = projectionuvs [1] - projectionuvs [0];
ProjectionUVs [2] = projectionuvs [2] - projectionuvs [0];
SourceTargaPtr = (TrueColorTarga*) sourcetargaptr;
}
/***********************************************************************************************
* TrueColorTarga::TrueColorTarga -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
TrueColorTarga::TrueColorTarga()
: Targa()
{
const unsigned width = 1;
const unsigned height = 1;
const unsigned pixeldepth = 24;
// Check that width, height and pixel depth will fit into the Targa internal storage types.
ASSERT (width <= SHRT_MAX);
ASSERT (height <= SHRT_MAX);
ASSERT (pixeldepth <= SCHAR_MAX);
mFlags = TGAF_IMAGE;
Header.ImageType = TGA_TRUECOLOR;
Reformat (width, height, pixeldepth);
}
/***********************************************************************************************
* TrueColorTarga::TrueColorTarga -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
TrueColorTarga::TrueColorTarga (unsigned width, unsigned height, unsigned pixeldepth)
: Targa()
{
// Check that width, height and pixel depth will fit into the Targa internal storage types.
ASSERT (width <= SHRT_MAX);
ASSERT (height <= SHRT_MAX);
ASSERT (pixeldepth <= SCHAR_MAX);
mFlags = TGAF_IMAGE;
Header.ImageType = TGA_TRUECOLOR;
Reformat (width, height, pixeldepth);
}
/***********************************************************************************************
* TrueColorTarga::TrueColorTarga -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
TrueColorTarga::TrueColorTarga (unsigned width, unsigned height, unsigned pixeldepth, const W3dRGBStruct &clearcolor)
: Targa()
{
// Check that width, height and pixel depth will fit into the Targa internal storage types.
ASSERT (width <= SHRT_MAX);
ASSERT (height <= SHRT_MAX);
ASSERT (pixeldepth <= SCHAR_MAX);
mFlags = TGAF_IMAGE;
Header.ImageType = TGA_TRUECOLOR;
Reformat (width, height, pixeldepth, clearcolor);
}
/***********************************************************************************************
* TrueColorTarga::Reformat -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
void TrueColorTarga::Reformat (unsigned width, unsigned height, unsigned pixeldepth)
{
size_t size;
Header.Width = width;
Header.Height = height;
Header.PixelDepth = pixeldepth;
size = width * height * TGA_BytesPerPixel (pixeldepth);
if (size > 0) {
// NOTE: Use malloc() or realloc() here because destructor will use free().
mImage = (char*) realloc (mImage, size);
ASSERT (mImage != NULL);
}
}
/***********************************************************************************************
* TrueColorTarga::Reformat -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
void TrueColorTarga::Reformat (unsigned width, unsigned height, unsigned pixeldepth, const W3dRGBStruct &clearcolor)
{
UnpackedTexelStruct cleartexel (clearcolor.R, clearcolor.G, clearcolor.B, 0);
Reformat (width, height, pixeldepth);
Clear (cleartexel);
}
/***********************************************************************************************
* TrueColorTarga::Pixel_Format -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
srPixelConvert::e_surfaceType TrueColorTarga::Pixel_Format (unsigned pixeldepth)
{
// Map a pixel depth (in bits) to a Targa supported pixel format.
switch (pixeldepth) {
case 16:
return (srPixelConvert::ARGB1555);
case 24:
return (srPixelConvert::RGB888);
case 32:
return (srPixelConvert::ARGB8888);
default:
ASSERT (FALSE);
break;
}
ASSERT (FALSE);
return (srPixelConvert::e_surfaceType (0));
}
/***********************************************************************************************
* TrueColorTarga::Clear -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
void TrueColorTarga::Clear (const TrueColorTarga::UnpackedTexelStruct &cleartexel)
{
const unsigned bytespertexel = TGA_BytesPerPixel (Pixel_Depth());
unsigned char *texelptr;
for (unsigned y = 0; y < Height(); y++) {
texelptr = ((unsigned char*) GetImage()) + (Width() * y * bytespertexel);
for (unsigned x = 0; x < Width(); x++) {
Pack_Texel (cleartexel, texelptr, bytespertexel);
texelptr += bytespertexel;
}
}
}
/***********************************************************************************************
* TrueColorTarga::Load -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
char *TrueColorTarga::Load (const char *pathname)
{
const char *loaderrormessage = "The image file ""%s"" cannot be loaded (load error: %d).\
Please ensure that the image file exists and is in TGA (Truevision TARGA) format.";
const char *formaterrormessage = "The image file ""%s"" is not in a suitable TGA format.\
Please ensure that the image file is in true color format (16, 24 or 32 bit).";
static char _messagebuffer [256];
long error;
bool valid;
StringBuilder errormessage (_messagebuffer, sizeof (_messagebuffer));
error = Targa::Load (pathname, TGAF_IMAGE);
if (error != 0) {
errormessage.Copy (loaderrormessage, pathname, error);
return (errormessage.String());
}
// Check for a specific subset of the available .TGA texel formats which are suitable for
// true color targas (ie. true color, not paletted, not monochrome).
valid = (Header.ImageType == TGA_TRUECOLOR) || (Header.ImageType == TGA_TRUECOLOR_ENCODED);
valid &= (Header.PixelDepth == 16) || (Header.PixelDepth == 24) || (Header.PixelDepth == 32);
if (!valid) {
errormessage.Copy (formaterrormessage, pathname);
return (errormessage.String());
}
// No error message.
return (NULL);
}
/***********************************************************************************************
* TrueColorTarga::Save -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 8/18/99 IML : Created. *
*=============================================================================================*/
char *TrueColorTarga::Save (const char *pathname)
{
const char *saveerrormessage = "Cannot save the image file ""%s"" (save error: %d).";
static char _messagebuffer [256];
long error;
StringBuilder errormessage (_messagebuffer, sizeof (_messagebuffer));
error = Targa::Save (pathname, TGAF_IMAGE);
if (error != 0) {
errormessage.Copy (saveerrormessage, pathname, error);
return (errormessage.String());
}
// No error message.
return (NULL);
}
/***********************************************************************************************
* TrueColorTarga::Blit -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
void TrueColorTarga::Blit (TrueColorTarga &destination, unsigned x, unsigned y)
{
unsigned sourcebytespertexel, destbytespertexel;
unsigned maxc, maxr;
unsigned char *sourceptr, *destptr;
sourcebytespertexel = TGA_BytesPerPixel (Pixel_Depth());
destbytespertexel = TGA_BytesPerPixel (destination.Pixel_Depth());
// Currently, a true color targa cannot blit to itself.
ASSERT (this != &destination);
ASSERT (GetImage() != NULL);
ASSERT (destination.GetImage() != NULL);
// Sanity checks.
if ((x >= destination.Width()) || (y >= destination.Height())) return;
// Clip to destination.
if (x + Width() <= destination.Width()) {
maxc = Width();
} else {
maxc = destination.Width() - x;
}
if (y + Height() <= destination.Height()) {
maxr = Height();
} else {
maxr = destination.Height() - y;
}
// For each row...
for (unsigned r = 0; r < maxr; r++) {
sourceptr = ((unsigned char*) GetImage()) + (Width() * r * sourcebytespertexel);
destptr = ((unsigned char*) destination.GetImage()) + (((destination.Width() * (y + r)) + x) * destbytespertexel);
// For each column...
for (unsigned c = 0; c < maxc; c++) {
UnpackedTexelStruct unpackedtexel;
Pack_Texel (*Unpack_Texel (sourceptr, sourcebytespertexel, unpackedtexel), destptr, destbytespertexel);
// Advance to next texel.
sourceptr += sourcebytespertexel;
destptr += destbytespertexel;
}
}
}
/***********************************************************************************************
* TrueColorTarga::Scale -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
void TrueColorTarga::Scale (TrueColorTarga &destination, unsigned width, unsigned height)
{
size_t size, newsize;
ColorSurface surface (Pixel_Format (Pixel_Depth()), Width(), Height());
SRBOOL success;
// Image data must exist.
ASSERT (GetImage() != NULL);
// Currently, source and destination pixel depths must match.
ASSERT (Pixel_Depth() == destination.Pixel_Depth());
// Clamp width, height.
if (width < 1) width = 1;
if (height < 1) height = 1;
// Define highest quality filter.
surface.setFilter (&srBSplineFilter);
// Enable clamping.
surface.setHClampMode (true);
surface.setVClampMode (true);
// Copy the targa source texel data to the Surrender surface.
size = Width() * Height() * TGA_BytesPerPixel (Pixel_Depth());
memcpy (surface.getDataPtr(), GetImage(), size);
// Scale.
success = surface.rescale (width, height);
ASSERT (success);
// Resize the destination to match that of the rescaled Surrender surface.
destination.Reformat (width, height, destination.Pixel_Depth());
// Copy the rescaled Surrender surface to the targa destination.
newsize = width * height * TGA_BytesPerPixel (destination.Pixel_Depth());
memcpy (destination.GetImage(), surface.getDataPtr(), newsize);
}
/***********************************************************************************************
* TrueColorTarga::Scale -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 10/11/99 IML : Created. *
*=============================================================================================*/
#define AVERAGE(a, b) \
(((a) + (b)) / 2) + (((a) + (b)) % 2)
#define BINARY_CHOP \
if (result == -1) { \
maxdimension = dimension; \
dimension = AVERAGE (dimension, mindimension); \
if (maxdimension == dimension) break; \
} else { \
if (result == 1) { \
mindimension = dimension; \
dimension = AVERAGE (dimension, maxdimension); \
if (mindimension == dimension) break; \
} else { \
break; \
} \
} \
void TrueColorTarga::Scale (TrueColorTarga &destination, float error)
{
const unsigned attemptcount = 8;
unsigned attempt, maxdimension, mindimension, dimension;
int result;
unsigned width, height;
TrueColorTarga *scaledtargaptr;
// Calculate width.
maxdimension = Width();
mindimension = 1;
dimension = AVERAGE (maxdimension, mindimension);
for (attempt = 0; attempt < attemptcount; attempt++) {
scaledtargaptr = new TrueColorTarga (dimension, Height(), Pixel_Depth());
ASSERT (scaledtargaptr != NULL);
Scale (*scaledtargaptr);
result = Compare (*scaledtargaptr, error);
delete scaledtargaptr;
BINARY_CHOP;
}
width = dimension;
// Calculate height.
maxdimension = Height();
mindimension = 1;
dimension = AVERAGE (maxdimension, mindimension);
for (attempt = 0; attempt < attemptcount; attempt++) {
scaledtargaptr = new TrueColorTarga (Width(), dimension, Pixel_Depth());
ASSERT (scaledtargaptr != NULL);
Scale (*scaledtargaptr);
result = Compare (*scaledtargaptr, error);
delete scaledtargaptr;
BINARY_CHOP;
}
height = dimension;
// Scale targa.
Scale (destination, width, height);
}
#undef AVERAGE
#undef BINARY_CHOP
/***********************************************************************************************
* TrueColorTarga::Transpose -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 10/07/99 IML : Created. *
*=============================================================================================*/
void TrueColorTarga::Transpose (TrueColorTarga &destination)
{
unsigned bytespertexel;
size_t size;
unsigned sourcestride;
unsigned char *sourceptr, *destinationptr, *stagingbuffer;
// Image data must exist.
ASSERT (GetImage() != NULL);
// Currently, source and destination pixel depths must match.
ASSERT (Pixel_Depth() == destination.Pixel_Depth());
bytespertexel = TGA_BytesPerPixel (Pixel_Depth());
size = Width() * Height() * bytespertexel;
stagingbuffer = new unsigned char [size];
ASSERT (stagingbuffer != NULL);
// Write transposed image data to staging buffer.
sourcestride = Width() * bytespertexel;
destinationptr = stagingbuffer;
for (unsigned y = 0; y < Width(); y++) {
sourceptr = ((unsigned char*) GetImage()) + (y * bytespertexel);
for (unsigned x = 0; x < Height(); x++) {
for (unsigned b = 0; b < bytespertexel; b++) {
*destinationptr++ = *(sourceptr + b);
}
sourceptr += sourcestride;
}
}
// Resize the destination to match that of the transposed source.
destination.Reformat (Height(), Width(), destination.Pixel_Depth());
// Copy transposed image data to destination.
memcpy (destination.GetImage(), stagingbuffer, size);
// Clean-up.
delete [] stagingbuffer;
}
/***********************************************************************************************
* TrueColorTarga::Compare -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 10/11/99 IML : Created. *
*=============================================================================================*/
int TrueColorTarga::Compare (TrueColorTarga &comparison, float epsilon)
{
unsigned bytespertexel, comparisonbytespertexel;
int epsilondelta;
float xscale, yscale;
int result;
unsigned char *imageptr;
ASSERT ((epsilon >= 0.0f) && (epsilon <= 1.0f));
bytespertexel = (size_t) TGA_BytesPerPixel (Pixel_Depth());
comparisonbytespertexel = (size_t) TGA_BytesPerPixel (comparison.Pixel_Depth());
epsilondelta = MAX (0, epsilon * 255.0f);
result = -1;
// Calculate destination:source scaling factors.
xscale = ((float) comparison.Width()) / Width();
yscale = ((float) comparison.Height()) / Height();
// For each texel in this targa measure the delta for the corresponding texel in the comparison targa.
imageptr = (unsigned char*) GetImage();
for (unsigned y = 0; y < Height(); y++) {
unsigned ys;
// NOTE: Position sample point at center of texel.
ys = MIN ((unsigned) ((y + 0.5f) * yscale), (unsigned) comparison.Height() - 1);
for (unsigned x = 0; x < Width(); x++) {
unsigned xs;
unsigned char *comparisonimageptr;
int delta;
UnpackedTexelStruct texel, comparisontexel;
// NOTE: Position sample point at center of texel.
xs = MIN ((unsigned) ((x + 0.5f) * xscale), (unsigned) comparison.Width() - 1);
comparisonimageptr = ((unsigned char*) comparison.GetImage()) + (((ys * comparison.Width()) + xs) * comparisonbytespertexel);
Unpack_Texel (imageptr, bytespertexel, texel);
Unpack_Texel (comparisonimageptr, comparisonbytespertexel, comparisontexel);
delta = abs (((int) texel.Byte [0]) - ((int) comparisontexel.Byte [0]));
for (unsigned b = 1; b < sizeof (texel.Byte); b++) {
delta = MAX (delta, abs (((int) texel.Byte [b]) - ((int) comparisontexel.Byte [b])));
}
if (delta > epsilondelta) {
// Return result.
return (1);
}
if (delta == epsilondelta) {
result = 0;
}
// Advance.
imageptr += bytespertexel;
}
}
// Return result.
return (result);
}
/***********************************************************************************************
* TrueColorTarga::Compare -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 10/11/99 IML : Created. *
*=============================================================================================*/
int TrueColorTarga::Compare (TrueColorTarga &comparison, unsigned x, unsigned y, float epsilon)
{
unsigned bytespertexel, comparisonbytespertexel;
int epsilondelta;
int result;
unsigned char *imageptr, *comparisonptr;
ASSERT ((epsilon >= 0.0f) && (epsilon <= 1.0f));
bytespertexel = (size_t) TGA_BytesPerPixel (Pixel_Depth());
comparisonbytespertexel = (size_t) TGA_BytesPerPixel (comparison.Pixel_Depth());
epsilondelta = MAX (0, epsilon * 255.0f);
result = -1;
// This targa must be contained by comparison targa.
if (x + Width() >= comparison.Width()) return (1);
if (y + Height() >= comparison.Height()) return (1);
// For each row...
for (unsigned r = 0; r < Height(); r++) {
imageptr = ((unsigned char*) GetImage()) + (Width() * r * bytespertexel);
comparisonptr = ((unsigned char*) comparison.GetImage()) + (((comparison.Width() * (y + r)) + x) * comparisonbytespertexel);
// For each column...
for (unsigned c = 0; c < Width(); c++) {
UnpackedTexelStruct texel, comparisontexel;
int delta;
Unpack_Texel (imageptr, bytespertexel, texel);
Unpack_Texel (comparisonptr, comparisonbytespertexel, comparisontexel);
delta = abs (((int) texel.Byte [0]) - ((int) comparisontexel.Byte [0]));
for (unsigned b = 1; b < sizeof (texel.Byte); b++) {
delta = MAX (delta, abs (((int) texel.Byte [b]) - ((int) comparisontexel.Byte [b])));
}
if (delta > epsilondelta) {
// Return result.
return (1);
}
if (delta == epsilondelta) {
result = 0;
}
// Advance.
imageptr += bytespertexel;
comparisonptr += comparisonbytespertexel;
}
}
// Return result.
return (result);
}
/***********************************************************************************************
* TrueColorTarga::Fill -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
bool TrueColorTarga::Fill (const W3dRGBStruct &fillcolor)
{
const unsigned growthstep = 2048;
const UnpackedTexelStruct filltexel (fillcolor.R, fillcolor.G, fillcolor.B, 0);
DynamicVectorClass *fourconnectedarrays;
unsigned index;
bool allfillcolor;
// Allocate dynamic arrays and initialize.
fourconnectedarrays = new DynamicVectorClass [2];
ASSERT (fourconnectedarrays != NULL);
fourconnectedarrays [0].Set_Growth_Step (growthstep);
fourconnectedarrays [1].Set_Growth_Step (growthstep);
// Step thru all texels and pad all existing four-connected texels, and add new four-connected texel coordinates to dynamic array.
index = 0;
allfillcolor = true;
for (unsigned y = 0; y < Height(); y++) {
for (unsigned x = 0; x < Width(); x++) {
allfillcolor &= Fill_Four_Connected (x, y, filltexel, fourconnectedarrays [index]);
}
}
if (!allfillcolor) {
// While there are still unpadded texels...
while (fourconnectedarrays [index].Count() > 0) {
// For each four connected texel...
for (int e = 0; e < fourconnectedarrays [index].Count(); e++) {
Fill_Four_Connected ((fourconnectedarrays [index])[e].X, (fourconnectedarrays [index])[e].Y, filltexel, fourconnectedarrays [index ^ 1]);
}
fourconnectedarrays [index].Clear();
// Toggle dynamic array in which to place new four-connected texel coordinates.
index ^= 1;
}
}
// Clean-up.
delete [] fourconnectedarrays;
return (allfillcolor);
}
/***********************************************************************************************
* TrueColorTarga::Fill_Four_Connected -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
bool TrueColorTarga::Fill_Four_Connected (unsigned x, unsigned y, const UnpackedTexelStruct &filltexel, DynamicVectorClass &fourconnectedarray)
{
const unsigned fourconnectedcount = 4;
const unsigned bytespertexel = TGA_BytesPerPixel (Pixel_Depth());
static const int offsetx [fourconnectedcount] = {-1, +1, 0, 0};
static const int offsety [fourconnectedcount] = { 0, 0, -1, +1};
UnpackedTexelStruct unpackedtexel;
unsigned char *texelptr;
// Is texel (x, y) the fill color (ie. not already filled)?
texelptr = Get_Texel (x, y);
ASSERT (texelptr != NULL);
Unpack_Texel (texelptr, bytespertexel, unpackedtexel);
if (unpackedtexel == filltexel) {
unsigned adj;
bool fourconnected [fourconnectedcount];
unsigned fillcount, r, g, b;
// Initialize.
fillcount = 0;
r = g = b = 0;
// Fill the texel by averaging its non-fill color four-connected neighbors.
for (adj = 0; adj < fourconnectedcount; adj++) {
int adjx, adjy;
unsigned char *adjtexelptr;
fourconnected [adj] = false;
adjx = ((int) x) + offsetx [adj];
adjy = ((int) y) + offsety [adj];
adjtexelptr = Get_Texel (adjx, adjy);
if (adjtexelptr != NULL) {
Unpack_Texel (adjtexelptr, bytespertexel, unpackedtexel);
if (unpackedtexel == filltexel) {
fourconnected [adj] = true;
} else {
r += unpackedtexel.Red();
g += unpackedtexel.Green();
b += unpackedtexel.Blue();
fillcount++;
}
}
}
if (fillcount > 0) {
float oofillcount;
// Fill texel (x, y) with average of neighboring non-fill colors.
oofillcount = 1.0f / fillcount;
r = MIN (r * oofillcount, UCHAR_MAX);
g = MIN (g * oofillcount, UCHAR_MAX);
b = MIN (b * oofillcount, UCHAR_MAX);
UnpackedTexelStruct texel (r, g, b, 0);
Pack_Texel (texel, texelptr, bytespertexel);
// Add the coordinates of any neighboring fill colors.
for (adj = 0; adj < fourconnectedcount; adj++) {
if (fourconnected [adj]) {
PointStruct p;
p.X = ((int) x) + offsetx [adj];
p.Y = ((int) y) + offsety [adj];
fourconnectedarray.Add (p);
}
}
}
return (true);
} else {
return (false);
}
}
/***********************************************************************************************
* TrueColorTarga::Add -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
void TrueColorTarga::Add (TrueColorTarga &targa)
{
unsigned width, height;
unsigned thisbytespertexel, targabytespertexel;
// Scale both targas to maximum width & height of both.
width = MAX (Width(), targa.Width());
height = MAX (Height(), targa.Height());
Scale (width, height);
targa.Scale (width, height);
// Step thru both targas and add the pixel data. Store result in this targa.
// For each row...
thisbytespertexel = TGA_BytesPerPixel (Pixel_Depth());
targabytespertexel = TGA_BytesPerPixel (targa.Pixel_Depth());
for (unsigned r = 0; r < height; r++) {
unsigned char *thisptr, *targaptr;
thisptr = ((unsigned char*) GetImage()) + (width * r * thisbytespertexel);
targaptr = ((unsigned char*) targa.GetImage()) + (width * r * targabytespertexel);
// For each column...
for (unsigned c = 0; c < width; c++) {
UnpackedTexelStruct thisunpackedtexel, targaunpackedtexel;
Unpack_Texel (thisptr, thisbytespertexel, thisunpackedtexel);
Unpack_Texel (targaptr, targabytespertexel, targaunpackedtexel);
thisunpackedtexel += targaunpackedtexel;
Pack_Texel (thisunpackedtexel, thisptr, thisbytespertexel);
// Advance to next texel.
thisptr += thisbytespertexel;
targaptr += targabytespertexel;
}
}
}
/***********************************************************************************************
* TrueColorTarga::Rasterize -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 05/22/00 IML : Created. *
*=============================================================================================*/
void TrueColorTarga::Rasterize (TrueColorTarga &destination, const W3dRGBStruct &fillcolor, unsigned vertexcount, const W3dRGBStruct *vertexcolors, Vector2 *vertexuvs)
{
const unsigned edgecount = 3;
const static float _vertexuvs [edgecount][2] =
{
{1.0f, 0.0f},
{0.0f, 0.0f},
{0.0f, 1.0f}
};
const UnpackedTexelStruct filltexel (fillcolor.R, fillcolor.G, fillcolor.B, 0);
const unsigned sqrtsamplecountminusone = 3;
const float oosqrtsamplecountminusone = 1.0f / sqrtsamplecountminusone;
const unsigned mindimension = 3;
Vector2 edges [edgecount];
float longestlength2, r, w, h;
unsigned longestedge;
Vector2 i, j;
float oowidthminustwo, ooheightminustwo;
unsigned bytespertexel;
unsigned char *destptr;
W3dRGBStruct colors [edgecount];
float oowidth, ooheight;
unsigned n;
// UV's must define a triangle.
ASSERT (vertexcount == edgecount);
// Define edges of source triangle.
edges [0] = vertexuvs [1] - vertexuvs [0];
edges [1] = vertexuvs [2] - vertexuvs [1];
edges [2] = vertexuvs [0] - vertexuvs [2];
// The destination triangle is a right-angled triangle that occupies one half of the
// destination targa. Size the destination targa usinh the following rules:
// (a) length of longest edge equals length of targa's diagonal (hypotenuse of destination triangle)
// (b) ratio of lengths of remaining two edges of source triangle equals ratio of dimensions of targa.
// Identify the longest edge.
longestlength2 = 0.0f;
for (unsigned e = 0; e < edgecount; e++) {
float length2 = edges [e].Length2();
if (length2 > longestlength2) {
longestedge = e;
longestlength2 = length2;
}
}
// Calculate width and height of destination targa.
r = edges [(longestedge + 1) % edgecount].Length() / edges [(longestedge + 2) % edgecount].Length();
w = WWMath::Sqrt (longestlength2 / (1.0f + r));
h = w / r;
// Resize the destination targa.
destination.Reformat (MAX (mindimension, (unsigned) (w * Width())), MAX (mindimension, (unsigned) (h * Height())), Pixel_Depth());
// Set up a coordinate system to define the source triangle in terms of the destination triangle.
i = -edges [(longestedge + 1) % edgecount];
j = edges [(longestedge + 2) % edgecount];
// Define colors that correspond to each vertex;
for (n = 0; n < vertexcount; n++) {
if (vertexcolors != NULL) {
colors [n] = vertexcolors [(n + longestedge) % edgecount];
} else {
colors [n] = fillcolor;
}
}
// Iterate over the destination triangle, sampling the source triangle at regular intervals.
// Also insert a one pixel wide filtered edge comprising interpolated vertex colors.
// For each destination texel...
bytespertexel = TGA_BytesPerPixel (Pixel_Depth());
oowidthminustwo = 1.0f / (destination.Width() - 2);
ooheightminustwo = 1.0f / (destination.Height() - 2);
destptr = (unsigned char*) destination.GetImage();
for (unsigned v = 0; v < destination.Height(); v++) {
for (unsigned u = 0; u < destination.Width(); u++) {
unsigned validsamplecount;
float r, g, b;
float fu, fv;
float oovalidsamplecount;
UnpackedTexelStruct averagetexel;
float clamped;
// For given destination texel subsample the source triangle.
validsamplecount = 0;
r = g = b = 0.0f;
for (unsigned sv = 0; sv <= sqrtsamplecountminusone; sv++) {
fv = (v + (sv * oosqrtsamplecountminusone) - 1.0f) * ooheightminustwo;
for (unsigned su = 0; su <= sqrtsamplecountminusone; su++) {
fu = (u + (su * oosqrtsamplecountminusone) - 1.0f) * oowidthminustwo;
// Which region does (fu, fv) fall in?
clamped = false;
if (fu < 0.0f) {
fu = 0.0f;
clamped = true;
} else {
if (fu > 1.0f) {
fu = 1.0f;
clamped = true;
}
}
if (fv < 0.0f) {
fv = 0.0f;
clamped = true;
} else {
if (fv > 1.0f) {
fv = 1.0f;
clamped = true;
}
}
if ((fu + fv) >= 1.0f) {
float ood = 1.0f / (fu + fv);
fu = fu * ood;
fv = fv * ood;
clamped = true;
}
if (!clamped) {
Vector2 p;
unsigned x, y;
UnpackedTexelStruct unpackedtexel;
unsigned char *sourceptr;
// Calculate source coordinates.
p = vertexuvs [(longestedge + 2) % 3] + (fu * i) + (fv * j);
x = (unsigned) MIN (MAX ((int) (p.X * Width()), 0), ((int) Width()) - 1);
y = (unsigned) MIN (MAX ((int) (p.Y * Height()), 0), ((int) Height()) - 1);
// Sample the source.
sourceptr = ((unsigned char*) GetImage()) + (((Width() * y) + x) * bytespertexel);
Unpack_Texel (sourceptr, bytespertexel, unpackedtexel);
r += unpackedtexel.Red();
g += unpackedtexel.Green();
b += unpackedtexel.Blue();
} else {
// Calculate source color.
r += 0.5f * ((colors [1].R * fu) + (colors [2].R * (1.0f - fu)) + (colors [2].R * (1.0f - fv)) + (colors [0].R * fv));
g += 0.5f * ((colors [1].G * fu) + (colors [2].G * (1.0f - fu)) + (colors [2].G * (1.0f - fv)) + (colors [0].G * fv));
b += 0.5f * ((colors [1].B * fu) + (colors [2].B * (1.0f - fu)) + (colors [2].B * (1.0f - fv)) + (colors [0].B * fv));
}
validsamplecount++;
}
}
// One or more samples must have been taken.
ASSERT (validsamplecount > 0);
// Destination texel = average of samples.
oovalidsamplecount = 1.0f / validsamplecount;
averagetexel.Set (r * oovalidsamplecount, g * oovalidsamplecount, b * oovalidsamplecount, 0);
Pack_Texel (averagetexel, destptr, bytespertexel);
// Advance.
destptr += bytespertexel;
}
}
// Replace source UV's with destination coordinates for caller.
oowidth = 1.0f / destination.Width();
ooheight = 1.0f / destination.Height();
for (n = 0; n < vertexcount; n++) {
vertexuvs [n].Set (_vertexuvs [((edgecount - 1 - longestedge) + n) % edgecount][0], _vertexuvs [((edgecount - 1 - longestedge) + n) % edgecount][1]);
// Scale and translate UV's to accomodate one texel wide filtered edge.
vertexuvs [n].U *= (destination.Width() - 2) * oowidth;
vertexuvs [n].V *= (destination.Height() - 2) * ooheight;
vertexuvs [n].U += oowidth;
vertexuvs [n].V += ooheight;
}
}
/***********************************************************************************************
* TrueColorTarga::Pad -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 05/22/00 IML : Created. *
*=============================================================================================*/
void TrueColorTarga::Pad (TrueColorTarga &destination, unsigned padwidth, unsigned padheight, const W3dRGBStruct &padcolor, DynamicVectorClass &triangleptrs)
{
unsigned w, h;
float oobw, oobh;
UnpackedTexelStruct padtexel (padcolor.R, padcolor.G, padcolor.B, 0);
Matrix3 uvmatrix;
// Optimization: was a non-zero pad thickness specified?
if ((padwidth > 0) || (padheight > 0)) {
// Round pad width and height to even no. to ensure that there is an equal amount of padding on each side.
padwidth += (padwidth & 0x1);
padheight += (padheight & 0x1);
// Calculate scaling and translation factors.
w = Width();
h = Height();
oobw = 1.0f / (w + padwidth);
oobh = 1.0f / (h + padheight);
if (this == &destination) {
TrueColorTarga targacopy (w, h, Pixel_Depth());
Blit (targacopy, 0, 0);
// Resize to match that of the padded targa.
Reformat (w + padwidth, h + padheight, Pixel_Depth());
// Clear to pad color.
Clear (padtexel);
// Blit copy to this targa. Offset by pad thickness.
targacopy.Blit (*this, padwidth >> 1, padheight >> 1);
} else {
// Resize the destination to match that of the padded targa.
destination.Reformat (w + padwidth, h + padheight, Pixel_Depth());
// Clear destination to pad color.
destination.Clear (padtexel);
// Blit this to destination. Offset by pad thickness.
Blit (destination, padwidth >> 1, padheight >> 1);
}
// Pad pad color.
destination.Fill (padcolor);
// Calculate scaling and translation matrix.
uvmatrix [0].Set (w * oobw, 0.0f, 0.0f);
uvmatrix [1].Set (0.0f, h * oobh, 0.0f);
uvmatrix [2].Set ((padwidth >> 1) * oobw, (padheight >> 1) * oobh, 1.0f);
// Transpose transform matrix.
// NOTE: This matrix is set up for post multiplication (ie. V' = M X V, matrix M, vector V).
uvmatrix = uvmatrix.Transpose();
// Apply transform to all triangles...
for (int t = 0; t < triangleptrs.Count(); t++) {
for (unsigned v = 0; v < Triangle::VERTICES_COUNT; v++) {
Vector3 uv;
// NOTE: Create a homogeneous vector (3-components) from the UV vector so that it can be transformed by the matrix.
uv.Set (triangleptrs [t]->PackedUVs [v].X, triangleptrs [t]->PackedUVs [v].Y, 1.0f);
uv = uvmatrix * uv;
triangleptrs [t]->PackedUVs [v].Set (uv.X, uv.Y);
}
}
}
}
/***********************************************************************************************
* TrianglePacker::SampleSurface::SampleSurface -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/12/00 IML : Created. *
*=============================================================================================*/
TrianglePacker::SampleSurface::SampleSurface (unsigned width, unsigned height, ProceduralTexture *blendtexture)
{
SampleStruct *sampleptr;
Width = width;
Height = height;
SampledTexelCount = 0;
Surface = new SampleStruct [width * height];
ASSERT (Surface != NULL);
// Initialize surface.
sampleptr = Surface;
for (unsigned s = 0; s < width * height; s++) {
sampleptr->Red = 0;
sampleptr->Green = 0;
sampleptr->Blue = 0;
sampleptr->Count = 0;
sampleptr->Priority = 0;
sampleptr++;
}
BlendTexture = blendtexture;
}
/***********************************************************************************************
* TrianglePacker::SampleSurface::Sample -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/12/00 IML : Created. *
*=============================================================================================*/
bool TrianglePacker::SampleSurface::Sample (const Vector2 &samplepoint, const ProjectionTriangle &projectiontriangle, unsigned priority)
{
const float epsilon = 0.0001f;
int u, v;
Vector2 t0, t1, t2;
float alpha, beta;
u = floorf (samplepoint.U);
v = floorf (samplepoint.V);
// NOTE: Sample point must be in range.
if ((u < 0) || (u >= (int) Width)) return (false);
if ((v < 0) || (v >= (int) Height)) return (false);
// Use the baricentric method to determine if the sample point lies inside
// the triangle (see Graphics Gems I p390).
t0 = samplepoint - projectiontriangle.ProjectionUVs [0];
t1 = projectiontriangle.ProjectionUVs [1];
t2 = projectiontriangle.ProjectionUVs [2];
if (WWMath::Fabs (t1.U) <= epsilon) {
beta = t0.U / t2.U;
if (beta <= 0.0f || beta >= 1.0f) return (false);
alpha = (t0.V - (beta * t2.V)) / t1.V;
} else {
beta = (t0.V * t1.U - t0.U * t1.V) / (t2.V * t1.U - t2.U * t1.V);
if (beta <= 0.0f || beta >= 1.0f) return (false);
alpha = (t0.U - beta * t2.U) / t1.U;
}
// Does the projection triangle contain the sample point?
if ((alpha > 0.0f) && ((alpha + beta) < 1.0f)) {
Vector2 uv;
W3dRGBStruct color;
SampleStruct *sampleptr;
// Use the baricentric coordinates (alpha, beta) to calculate the texture coordinates.
uv = (alpha * projectiontriangle.SourceUVs [1]) + (beta * projectiontriangle.SourceUVs [2]) + projectiontriangle.SourceUVs [0];
if (!projectiontriangle.SourceTargaPtr->Get_Color (uv, color)) return (false);
// Should the texel color be blended with a procedural texture?
if (BlendTexture != NULL) {
Vector3 p;
float v;
p = (alpha * projectiontriangle.Points [1]) + (beta * projectiontriangle.Points [2]) + projectiontriangle.Points [0];
v = BlendTexture->Value (p);
color.Set ((uint8) (color.R * v), (uint8) (color.G * v), (uint8) (color.B * v));
}
// Add the sample.
sampleptr = Surface + (v * Width + u);
sampleptr->Red += color.R;
sampleptr->Green += color.G;
sampleptr->Blue += color.B;
if (sampleptr->Count == 0) SampledTexelCount++;
sampleptr->Count++;
// Update priority.
if (priority > sampleptr->Priority) sampleptr->Priority = priority;
return (true);
} else {
return (false);
}
}
/***********************************************************************************************
* TrianglePacker::SampleSurface::Sample -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 06/12/00 IML : Created. *
*=============================================================================================*/
bool TrianglePacker::SampleSurface::Sample (float alpha, float beta, const ProjectionTriangle &projectiontriangle, unsigned priority)
{
Vector2 samplepoint;
int u, v;
Vector2 uv;
W3dRGBStruct color;
SampleStruct *sampleptr;
// Use the baricentric coordinates (alpha, beta) to calculate the sample point.
samplepoint = (alpha * projectiontriangle.ProjectionUVs [1]) + (beta * projectiontriangle.ProjectionUVs [2]) + projectiontriangle.ProjectionUVs [0];
u = floorf (samplepoint.U);
v = floorf (samplepoint.V);
// NOTE: Sample point must be in range.
if ((u < 0) || (u >= (int) Width)) return (false);
if ((v < 0) || (v >= (int) Height)) return (false);
// Use the baricentric coordinates (alpha, beta) to calculate the texture coordinates.
uv = (alpha * projectiontriangle.SourceUVs [1]) + (beta * projectiontriangle.SourceUVs [2]) + projectiontriangle.SourceUVs [0];
if (!projectiontriangle.SourceTargaPtr->Get_Color (uv, color)) return (false);
// Should the texel color be blended with a procedural texture?
if (BlendTexture != NULL) {
Vector3 p;
float v;
p = (alpha * projectiontriangle.Points [1]) + (beta * projectiontriangle.Points [2]) + projectiontriangle.Points [0];
v = BlendTexture->Value (p);
color.Set ((uint8) (color.R * v), (uint8) (color.G * v), (uint8) (color.B * v));
}
// Add the sample.
sampleptr = Surface + (v * Width + u);
sampleptr->Red += color.R;
sampleptr->Green += color.G;
sampleptr->Blue += color.B;
if (sampleptr->Count == 0) SampledTexelCount++;
sampleptr->Count++;
// Update priority.
if (priority > sampleptr->Priority) sampleptr->Priority = priority;
return (true);
}
/***********************************************************************************************
* Page::Page -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
Page::Page (unsigned bitdepth, const W3dRGBStruct &clearcolor)
: TrueColorTarga (PAGE_WIDTH, PAGE_HEIGHT, bitdepth)
{
const UnpackedTexelStruct cleartexel (clearcolor.R, clearcolor.G, clearcolor.B, 0);
Region *regionptr;
// Clear this page to a recognizable color.
Clear (cleartexel);
// Create a single region for the entire page.
regionptr = new Region;
ASSERT (regionptr != NULL);
regionptr->Set (0, 0, PAGE_WIDTH - 1, PAGE_HEIGHT - 1);
VacantRegionList.Add_Head (regionptr);
Reset_Statistics();
}
/***********************************************************************************************
* Page::Page -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
Page::~Page()
{
// Delete the used region list.
while (UsedRegionList.First_Valid()) {
delete UsedRegionList.First_Valid();
}
// Delete the region list.
while (VacantRegionList.First_Valid()) {
delete VacantRegionList.First_Valid();
}
}
/***********************************************************************************************
* Page::Reset_Statisitcs -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
void Page::Reset_Statistics()
{
AssetCount = 0;
UsedTexelCount = 0;
ReplicaTexelCount = 0;
}
/***********************************************************************************************
* Page::Pack -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 05/19/00 IML : Created. *
*=============================================================================================*/
bool Page::Pack (TrueColorTarga &targa, float epsilon, DynamicVectorClass &triangleptrs)
{
TrueColorTarga *targaptr [TRANSPOSE_COUNT];
bool replica, packed;
TransposeEnum transposed;
unsigned cost;
Region targetregion;
// Targa must fit on this page.
ASSERT (targa.Width() <= Width());
ASSERT (targa.Height() <= Height());
targaptr [UNTRANSPOSED] = &targa;
// Create a transposed version of the targa.
targaptr [TRANSPOSED] = new TrueColorTarga (targaptr [UNTRANSPOSED]->Width(), targaptr [UNTRANSPOSED]->Height(), targaptr [UNTRANSPOSED]->Pixel_Depth());
ASSERT (targaptr [TRANSPOSED] != NULL);
targaptr [UNTRANSPOSED]->Blit (*targaptr [TRANSPOSED], 0, 0);
targaptr [TRANSPOSED]->Transpose();
// Attempt to find a replica targa on this page.
transposed = (targaptr [UNTRANSPOSED]->Width() >= targaptr [UNTRANSPOSED]->Height()) ? UNTRANSPOSED : TRANSPOSED;
replica = Replica_Region (*targaptr [transposed], epsilon, targetregion);
if (!replica) {
transposed = (transposed == UNTRANSPOSED) ? TRANSPOSED : UNTRANSPOSED;
replica = Replica_Region (*targaptr [transposed], epsilon, targetregion);
}
if (replica) {
// Update statistics.
ReplicaTexelCount += targaptr [transposed]->Width() * targaptr [transposed]->Height();
} else {
// Attempt to pack targa with width >= height first.
transposed = (targaptr [UNTRANSPOSED]->Width() >= targaptr [UNTRANSPOSED]->Height()) ? UNTRANSPOSED : TRANSPOSED;
// Can the targa be packed?
packed = Lowest_Cost_Region (*targaptr [transposed], cost, targetregion);
// If not packed then transpose the targa and attempt to pack it again.
if (!packed) {
transposed = (transposed == UNTRANSPOSED) ? TRANSPOSED : UNTRANSPOSED;
packed = Lowest_Cost_Region (*targaptr [transposed], cost, targetregion);
}
if (packed) {
// Region must be aligned on an even boundary. This will reduce texel bleeding as a result of mip-mapping.
ASSERT ((targetregion.X0 & 0x1) == 0x0);
ASSERT ((targetregion.Y0 & 0x1) == 0x0);
ASSERT ((targetregion.X1 & 0x1) == 0x1);
ASSERT ((targetregion.Y1 & 0x1) == 0x1);
Insert_Region (targetregion);
// Blit the targa onto this page.
targaptr [transposed]->Blit (*this, targetregion.X0, targetregion.Y0);
// Update statistics.
UsedTexelCount += targaptr [transposed]->Width() * targaptr [transposed]->Height();
}
}
// Transform the UV's to reflect the packing.
if (replica || packed) {
float su, sv; // Scaling factors of the targa within this page.
float tu, tv; // Translation of the targa within this page.
Matrix3 uvmatrix;
// Calculate scaling and translation factors.
su = ((float) (targaptr [UNTRANSPOSED]->Width())) / Width();
sv = ((float) (targaptr [UNTRANSPOSED]->Height())) / Height();
tu = ((float) targetregion.X0) / Width();
tv = ((float) targetregion.Y0) / Height();
// Was the targa transposed?
if (transposed == TRANSPOSED) {
// Define scaling/rotation vectors in transform matrix.
uvmatrix [0].Set (0.0f, su , 0.0f);
uvmatrix [1].Set (sv , 0.0f, 0.0f);
} else {
// Define scaling/rotation vectors in transform matrix.
uvmatrix [0].Set (su , 0.0f, 0.0f);
uvmatrix [1].Set (0.0f, sv , 0.0f);
}
// Define translation vector in transform matrix.
uvmatrix [2].Set (tu, tv, 1.0f);
// Transpose transform matrix.
// NOTE: Thus matrix is set up for post multiplication (ie. V' = M X V, matrix M, vector V).
uvmatrix = uvmatrix.Transpose();
// Iterate over all triangles and transform their packed UV's.
for (int t = 0; t < triangleptrs.Count(); t++) {
for (unsigned v = 0; v < Triangle::VERTICES_COUNT; v++) {
Vector3 uv;
// NOTE: Create a homogeneous vector (3-components) from the UV vector so that it can be transformed by the matrix.
uv.Set (triangleptrs [t]->PackedUVs [v].X, triangleptrs [t]->PackedUVs [v].Y, 1.0f);
uv = uvmatrix * uv;
triangleptrs [t]->PackedUVs [v].Set (uv.X, uv.Y);
}
}
// Update statistics.
AssetCount++;
}
// Clean-up.
delete targaptr [TRANSPOSED];
// Return success.
return (replica || packed);
}
/***********************************************************************************************
* Page::Replica_Region -- *
* * *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 11/17/99 IML : Created. *
*=============================================================================================*/
bool Page::Replica_Region (TrueColorTarga &targa, float epsilon, Region &replicaregion)
{
bool replica;
Region *regionptr;
unsigned regionwidth, regionheight;
// Iterate over all used regions to see if one matches the targa to within tolerance.
replica = false;
regionptr = (Region*) UsedRegionList.First_Valid();
while (regionptr != NULL) {
regionwidth = regionptr->X1 - regionptr->X0 + 1;
regionheight = regionptr->Y1 - regionptr->Y0 + 1;
// If regions are the same size...
if ((regionwidth == targa.Width()) && (regionheight == targa.Height())) {
// If regions are deemed equal to within epsilon...
if (targa.Compare (*this, regionptr->X0, regionptr->Y0, epsilon) <= 0) {
replica = true;
replicaregion = *regionptr;
break;
}
}
// Next region.
regionptr = (Region*) regionptr->Next_Valid();
}
return (replica);
}
/***********************************************************************************************
* Page::Lowest_Cost_Region -- *
* * *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 10/8/99 IML : Created. *
*=============================================================================================*/
bool Page::Lowest_Cost_Region (TrueColorTarga &targa, unsigned &lowestcost, Region &lowestcostregion)
{
unsigned width, height;
bool packed;
unsigned mintotalsubregioncount;
Region *regionptr;
// Find a vacant region in the page that will incur the lowest cost if it contains the targa asset.
width = targa.Width();
height = targa.Height();
packed = false;
mintotalsubregioncount = UINT_MAX;
regionptr = (Region*) VacantRegionList.First_Valid();
while (regionptr != NULL) {
Region candidateregion;
// Does the asset fit inside the region?
if (regionptr->Accomodates (width, height, candidateregion)) {
unsigned totalsubregioncount, subregioncount;
Region *fragmentregionptr, *subregions;
fragmentregionptr = (Region*) VacantRegionList.First_Valid();
totalsubregioncount = 0;
while (fragmentregionptr != NULL) {
// Calculate the fragmentation count for the fragment region.
if (fragmentregionptr->Intersects (candidateregion, subregioncount, &subregions)) {
totalsubregioncount += subregioncount;
}
// Next region.
fragmentregionptr = (Region*) fragmentregionptr->Next_Valid();
}
// Is this the minimum total subregion count?
if (totalsubregioncount < mintotalsubregioncount) {
packed = true;
lowestcostregion = candidateregion;
mintotalsubregioncount = totalsubregioncount;
}
}
// Next region.
regionptr = (Region*) regionptr->Next_Valid();
}
lowestcost = mintotalsubregioncount;
// Can the asset be packed on this page?
return (packed);
}
/***********************************************************************************************
* Page::Insert_Region -- *
* * *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 10/8/99 IML : Created. *
*=============================================================================================*/
void Page::Insert_Region (const Region &insertionregion)
{
Region *regionptr;
// First, add the insertion region to the used region list.
regionptr = new Region (insertionregion);
ASSERT (regionptr != NULL);
UsedRegionList.Add_Head (regionptr);
// Walk down the vacant list. If any region intersects the target region, fragment it into
// 0 to 4 sub-regions, depending on the relative location of the clipped region.
regionptr = (Region*) VacantRegionList.First_Valid();
while (regionptr != NULL) {
unsigned subregioncount;
Region *subregions, *removalptr;
// If there is an intersection between the region and target region...
if (regionptr->Intersects (insertionregion, subregioncount, &subregions)) {
// Remove the original region, advance to next region.
removalptr = regionptr;
regionptr = (Region*) regionptr->Next_Valid();
delete removalptr;
// Add the subregions to the head of the list.
// NOTE: Adding to the head of the list will ensure that they will not get re-processed by the current 'list walker'.
for (int s = ((int) subregioncount) - 1; s >= 0; s--) {
// Only add the subregion if it is not contained by another region ie. avoid redundancy.
if (!Contains (subregions [s])) {
Region *newregionptr;
newregionptr = new Region (subregions [s]);
ASSERT (newregionptr != NULL);
VacantRegionList.Add_Head (newregionptr);
}
}
} else {
// Advance to next region.
regionptr = (Region*) regionptr->Next_Valid();
}
}
}
/***********************************************************************************************
* Page::Region::Accomodates -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
bool Page::Region::Accomodates (unsigned width, unsigned height, Region &targetregion)
{
if ((width <= Width()) && (height <= Height())) {
// Locate the target region in the top-left corner of this region.
targetregion.Set (X0, Y0, X0 + width - 1, Y0 + height - 1);
return (true);
} else {
return (false);
}
}
/***********************************************************************************************
* Page::Region::Intersects -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
bool Page::Region::Intersects (const Region &targetregion, unsigned &subregioncount, Region **subregions)
{
const unsigned maxsubregioncount = 4; // Maximum no. of fragmented subregions.
static Region _subregions [maxsubregioncount];
unsigned s;
// First, test the target region for trivial rejection against the left, right, top and bottom
// sides of this region respectively.
if (targetregion.X1 < X0) return (false);
if (targetregion.X0 > X1) return (false);
if (targetregion.Y1 < Y0) return (false);
if (targetregion.Y0 > Y1) return (false);
// Now it is known that the target region intersects this region in some way.
// Count and generate the subregions between the target region and this region.
s = 0;
if (targetregion.X0 > X0) {
_subregions [s].Set (X0, Y0, targetregion.X0 - 1, Y1);
s++;
}
if (targetregion.X1 < X1) {
_subregions [s].Set (targetregion.X1 + 1, Y0, X1, Y1);
s++;
}
if (targetregion.Y0 > Y0) {
_subregions [s].Set (X0, Y0, X1, targetregion.Y0 - 1);
s++;
}
if (targetregion.Y1 < Y1) {
_subregions [s].Set (X0, targetregion.Y1 + 1, X1, Y1);
s++;
}
subregioncount = s;
*subregions = _subregions;
return (true);
}
/***********************************************************************************************
* Page::Region::Contains -- *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 9/27/99 IML : Created. *
*=============================================================================================*/
bool Page::Contains (const Region &testregion)
{
Region *regionptr;
// Step down the vacant list until a region is found that contains the test region or end of list.
regionptr = (Region*) VacantRegionList.First_Valid();
while (regionptr != NULL) {
if ((testregion.X0 >= regionptr->X0) && (testregion.X1 <= regionptr->X1) && (testregion.Y0 >= regionptr->Y0) && (testregion.Y1 <= regionptr->Y1)) {
// Test region is contained by a region in the list.
return (true);
}
regionptr = (Region*) regionptr->Next_Valid();
}
// Test region is not contained by a region in the list.
return (false);
}