This repository has been archived on 2025-02-27. You can view files and clone it, but cannot push or open issues or pull requests.
CnC_Renegade/Code/ww3d2/predlod.cpp

406 lines
16 KiB
C++

/*
** 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 <http://www.gnu.org/licenses/>.
*/
/***************************************************************************
*** C O N F I D E N T I A L --- W E S T W O O D S T U D I O S ***
***************************************************************************
* *
* Project Name : G *
* *
* $Archive:: /Commando/Code/ww3d2/predlod.cpp $*
* *
* $Author:: Jani_p $*
* *
* $Modtime:: 9/20/01 10:10a $*
* *
* $Revision:: 5 $*
* *
*-------------------------------------------------------------------------*
* Functions: *
* PredictiveLODOptimizerClass::Clear -- clear object list and total cost*
* PredictiveLODOptimizerClass::Add_Object -- adds object to list, cost *
* PredictiveLODOptimizerClass::Optimize_LODs -- does LOD optimization *
* PredictiveLODOptimizerClass::Free -- releases all memory used. *
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
#include "predlod.h"
#include <memory.h>
/* NOTE: The LODHeapNode and LODHeap classes are defined here for use in the
* Optimize_LODs() member function. */
// A node entry for a heap. It has no son/father pointers since it will be
// used in an array implementation of a heap.
/*
** NOTE: LODHeapNodes contain pointers to RenderObjClass, but these pointers
** are NOT tracked via refcounting. This is because the heaps are created and
** destroyed within one function, so all references created are necessary;
** and performing Add_Ref and Release_Ref every time a pointer is copied
** would hurt performance.
*/
class LODHeapNode {
public:
LODHeapNode(void) { Item = NULL; }
LODHeapNode (float key) { Item = NULL; Key = key; }
LODHeapNode (RenderObjClass * item, float key) { Item = item; Key = key; }
~LODHeapNode(void) { }
RenderObjClass * Get_Item(void) { return(Item); }
float Get_Key(void) { return(Key); }
void Set_Key(float key) { Key = key; }
int operator < (const LODHeapNode& node) { return(Key < node.Key); }
int operator <= (const LODHeapNode& node) { return(Key <= node.Key); }
int operator > (const LODHeapNode& node) { return(Key > node.Key); }
int operator >= (const LODHeapNode& node) { return(Key >= node.Key); }
int operator == (const LODHeapNode& node) { return(Key == node.Key); }
int operator != (const LODHeapNode& node) { return(Key != node.Key); }
private:
RenderObjClass *Item;
float Key;
};
// A Heap implemented as a complete binary tree in an array.
class LODHeap {
public:
// This constructor receives an array of HeapNodes and arranges it to
// fulfil the heap condition. Note: the array will be used inside the
// heap, so it should never be used or deleted outside. The resulting
// heap is full - no nodes can be added until some are removed.
LODHeap(int count, LODHeapNode *NodeArray) {
Nodes = NodeArray;
Num = Max = count;
// Now build a heap from the array by working backwards, building
// subheaps from the bottom up. (starting at the middle of the array
// since the single-node subtrees at the leaves are already heaps)
int index;
for (index = Num/2; index >= 1; index--) Downheap(index);
}
~LODHeap(void) {
// delete []Nodes;
}
LODHeapNode *Top(void) {
return &(Nodes[1]);
}
// This changes the key value of the entry at the top of the heap and
// adjusts the heap accordingly.
void Change_Key_Top(float new_key) {
Nodes[1].Set_Key(new_key);
Downheap(1);
}
// This searches for an entry which has a certain Item value, and
// changes its key to a new one. The heap is then adjusted accordingly.
void Change_Key(RenderObjClass *item, float new_key) {
for (int i=1; i <= Num; i++) {
if (Nodes[i].Get_Item() == item) {
float old_key = Nodes[i].Get_Key();
Nodes[i].Set_Key(new_key);
// If the key has been decreased, adjust the node downwards.
// Otherwise, adjust it upwards.
if (new_key < old_key) Downheap(i);
else Upheap(i);
break;
}
}
}
private:
LODHeap(void) {} // Just to ensure the default constructor is not used.
// The node and key arrays have one extra entry because entry [0] is
// reserved for various uses.
LODHeapNode * Nodes; // The nodes
int Max; // The maximum number of nodes
int Num; // the current number of nodes
// Two utility methods used by various other methods: both take a
// single entry which violates the heap condition and moves it in the
// heap until the heap condition is fulfilled.
// Upheap takes an entry with a (possibly) overlarge key and moves it
// up until the heap condition is satisfied. (this is a private
// method, so no error checking is needed).
// Note that Upheap puts a sentinel in Nodes[0].
void Upheap(int index) {
LODHeapNode node = Nodes[index];
Nodes[0].Set_Key(FLT_MAX);
while (Nodes[index/2] <= node) {
Nodes[index] = Nodes[index/2];
index = index/2;
}
Nodes[index] = node;
}
// Downheap takes an entry with a (possibly) oversmall key and moves it
// down until the heap condition is satisfied. (this is a private
// method, so no error checking is needed).
void Downheap(int index) {
LODHeapNode node = Nodes[index];
while (index <= Num/2) {
int child_index = index + index;
if ((child_index < Num) && (Nodes[child_index] < Nodes[child_index+1])) child_index++;
if (node >= Nodes[child_index]) break;
Nodes[index] = Nodes[child_index];
index = child_index;
}
Nodes[index] = node;
}
};
// Static PredictiveLODOptimizerClass data members:
RenderObjClass ** PredictiveLODOptimizerClass::ObjectArray = NULL;
int PredictiveLODOptimizerClass::ArraySize = 0;
int PredictiveLODOptimizerClass::NumObjects = 0;
float PredictiveLODOptimizerClass::TotalCost = 0.0f;
LODHeapNode * PredictiveLODOptimizerClass::VisibleObjArray1;
LODHeapNode * PredictiveLODOptimizerClass::VisibleObjArray2;
int PredictiveLODOptimizerClass::VisibleObjArraySize;
/**************************************************************************
* PredictiveLODOptimizerClass::Clear -- clear object list and total cost *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 03/12/1999 NH : Created. *
*========================================================================*/
void PredictiveLODOptimizerClass::Clear(void)
{
if (ObjectArray) {
// Release refs to all objects in the list:
for (int i = 0; i < NumObjects; i++) {
if (ObjectArray[i]) {
ObjectArray[i]->Release_Ref();
ObjectArray[i] = NULL;
}
}
}
TotalCost = 0.0f;
NumObjects = 0;
}
/**************************************************************************
* PredictiveLODOptimizerClass::Add_Object -- adds object to list, cost *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 03/12/1999 NH : Created. *
*========================================================================*/
void PredictiveLODOptimizerClass::Add_Object(RenderObjClass *robj)
{
// If array present but too small, free it and copy it to new array.
if (ObjectArray) {
if (ArraySize <= NumObjects) {
int new_array_size = NumObjects + 100;
RenderObjClass **new_array = new RenderObjClass *[new_array_size];
memcpy(new_array, ObjectArray, sizeof(RenderObjClass *) * NumObjects);
delete [] ObjectArray;
ObjectArray = new_array;
ArraySize = new_array_size;
}
} else {
// Create new object array.
ObjectArray = new RenderObjClass *[100];
}
// Copy pointer and add ref
ObjectArray[NumObjects] = robj;
ObjectArray[NumObjects]->Add_Ref();
NumObjects++;
float cost = robj->Get_Cost();
// Some sanity checking so one object doesn't mess up the entire scene
WWASSERT (cost >= 0.0f);
WWASSERT (cost < 1.0e6);
TotalCost += cost;
}
/**************************************************************************
* PredictiveLODOptimizerClass::Optimize_LODs -- does LOD optimization *
* *
* INPUT: float max_cost - the upper bound on the total scene Cost. *
* *
* OUTPUT: none. *
* *
* WARNINGS: *
* *
* HISTORY: *
* 12/08/1997 NH : Created. *
* 04/23/1997 NH : Ported to SR 1.3. *
* 03/12/1999 NH : Moved to PredictiveLODOptimizerClass. *
* *
* COMMENTS: *
* This function implements the algorithm outlined in "Adaptive *
* Display Algorithm for Interactive Frame Rates During Visualization *
* of Complex Virtual Environments", Thomas Funkhouser & Carlo Sequin, *
* SIGGRAPH '93 Proceedings, pp. 247-253. *
* Modifications have been made to support screensize clamping of LODs. *
*========================================================================*/
void PredictiveLODOptimizerClass::Optimize_LODs(float max_cost)
{
if (!ObjectArray || NumObjects == 0) return;
AllocVisibleObjArrays(NumObjects);
// Allocate and fill arrays. (one extra entry since the zeroth entry is not used).
// LODHeapNode *visible_obj_array1 = new LODHeapNode[NumObjects + 1];
// LODHeapNode *visible_obj_array2 = new LODHeapNode[NumObjects + 1];
// Insert objects into arrays: (0th entry reserved for sentinel values)
for (int i = 0; i < NumObjects; i++) {
RenderObjClass *robj = ObjectArray[i];
// We use minus Value for the first queue to make it ordered by minimum Value.
VisibleObjArray1[i + 1] = LODHeapNode(robj, -(robj->Get_Value()));
VisibleObjArray2[i + 1] = LODHeapNode(robj, robj->Get_Post_Increment_Value());
}
// Build priority queues:
LODHeap min_current_value_queue(NumObjects, VisibleObjArray1);
LODHeap max_post_increment_value_queue(NumObjects, VisibleObjArray2);
// These memory areas now are pointed to within the heaps:
// visible_obj_array1 = NULL;
// visible_obj_array2 = NULL;
// Main loop: iteratively increment/decrement tuples.
bool done = false;
RenderObjClass *max_data, *min_data;
while (!done) {
// Initialize max_data and min_data so comparison at end of loop uses correct values.
max_data = NULL;
min_data = NULL;
// Increment incrementable tuple with maximum next value.
if (TotalCost <= max_cost) {
// If tuple with maximum next value is already at maximum lod, all
// tuples are (since AT_MAX_LOD is smaller than any Value), so stop.
if (max_post_increment_value_queue.Top()->Get_Key() == RenderObjClass::AT_MAX_LOD) {
done = true;
break;
}
// Get (incrementable) tuple with maximum next value.
max_data = max_post_increment_value_queue.Top()->Get_Item();
// Increment tuple (and update TotalCost accordingly).
TotalCost -= max_data->Get_Cost();
max_data->Increment_LOD();
TotalCost += max_data->Get_Cost();
// Update priority queues with incremented tuple.
max_post_increment_value_queue.Change_Key_Top(max_data->Get_Post_Increment_Value());
min_current_value_queue.Change_Key(max_data, -(max_data->Get_Value()));
}
// Decrement decerementable tuples with minimum current value.
while (TotalCost > max_cost) {
// If tuple with minimum current value is already at minimum lod, all
// tuples are (since AT_MIN_LOD is smaller than any (negated) Value),
// so stop.
if (min_current_value_queue.Top()->Get_Key() == -RenderObjClass::AT_MIN_LOD) {
done = true;
break;
}
// Get (decrementable) tuple with minimum current value.
min_data = min_current_value_queue.Top()->Get_Item();
// Decrement tuple (and update TotalCost accordingly).
TotalCost -= min_data->Get_Cost();
min_data->Decrement_LOD();
TotalCost += min_data->Get_Cost();
// Update priority queues with incremented tuple.
min_current_value_queue.Change_Key_Top(-(min_data->Get_Value()));
max_post_increment_value_queue.Change_Key(min_data, min_data->Get_Post_Increment_Value());
// Check termination criterion (same tuple incremented and decremented).
if (max_data == min_data) {
done = true;
break;
}
}
}
// Clear optimizer:
Clear();
}
/**************************************************************************
* PredictiveLODOptimizerClass::Free -- releases all memory used. *
* *
* INPUT: *
* *
* OUTPUT: *
* *
* WARNINGS: *
* *
* HISTORY: *
* 03/12/1999 NH : Created. *
*========================================================================*/
void PredictiveLODOptimizerClass::Free(void)
{
Clear();
if (ObjectArray) {
delete [] ObjectArray;
ObjectArray = NULL;
ArraySize = 0;
}
// Only the array number one has been allocated...
if (VisibleObjArray1) delete[] VisibleObjArray1;
VisibleObjArray1=NULL;
VisibleObjArray2=NULL;
VisibleObjArraySize = 0;
}
void PredictiveLODOptimizerClass::AllocVisibleObjArrays(int num_objects)
{
if (VisibleObjArraySize<num_objects) {
VisibleObjArraySize=num_objects;
if (VisibleObjArray1) delete[] VisibleObjArray1; // Only the first array is actually allocated
VisibleObjArray1=new LODHeapNode[2*(num_objects + 1)];
VisibleObjArray2=VisibleObjArray1+(num_objects + 1);
}
}