345 lines
12 KiB
C
345 lines
12 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 : WWMath *
|
||
|
|
* *
|
||
|
|
* $Archive:: /Commando/Code/wwmath/aabtreecull.h $*
|
||
|
|
* *
|
||
|
|
* Author:: Greg Hjelstrom *
|
||
|
|
* *
|
||
|
|
* $Modtime:: 7/24/01 10:00a $*
|
||
|
|
* *
|
||
|
|
* $Revision:: 15 $*
|
||
|
|
* *
|
||
|
|
*---------------------------------------------------------------------------------------------*
|
||
|
|
* Functions: *
|
||
|
|
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
|
||
|
|
|
||
|
|
|
||
|
|
#if defined(_MSC_VER)
|
||
|
|
#pragma once
|
||
|
|
#endif
|
||
|
|
|
||
|
|
#ifndef AABTREECULL_H
|
||
|
|
#define AABTREECULL_H
|
||
|
|
|
||
|
|
#include "cullsys.h"
|
||
|
|
#include "aaplane.h"
|
||
|
|
#include "wwmath.h"
|
||
|
|
#include "mempool.h"
|
||
|
|
#include "simplevec.h"
|
||
|
|
#include <math.h>
|
||
|
|
#include <float.h>
|
||
|
|
|
||
|
|
class AABTreeNodeClass;
|
||
|
|
class ChunkLoadClass;
|
||
|
|
class ChunkSaveClass;
|
||
|
|
class SphereClass;
|
||
|
|
|
||
|
|
/**
|
||
|
|
** AABTreeCullSystemClass
|
||
|
|
** Derived culling system that uses an Axis-Aligned Bounding Box Tree
|
||
|
|
*/
|
||
|
|
class AABTreeCullSystemClass : public CullSystemClass
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
|
||
|
|
AABTreeCullSystemClass(void);
|
||
|
|
virtual ~AABTreeCullSystemClass(void);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Re-partition the tree. Two methods can be used to accomplish this. The
|
||
|
|
** first re-partitions the tree based on the objects contained within, the second
|
||
|
|
** re-partitions the tree based solely on a set of input "seed" boxes. Each seed
|
||
|
|
** box will become a leaf; then the objects will be re-inserted in the new tree.
|
||
|
|
*/
|
||
|
|
void Re_Partition(void);
|
||
|
|
void Re_Partition(const AABoxClass & bounds,SimpleDynVecClass<AABoxClass> & boxes);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Update_Bounding_Boxes. This function causes all bounding boxes in the tree to update themselves.
|
||
|
|
** If any box is found to not bound the objects it is supposed to contain, the box is updated
|
||
|
|
** Note that this is normally not necessary, the reason this function existsis due to the fact
|
||
|
|
** that the renegade level editor tries to do everything possible to not discard the precalculated
|
||
|
|
** visibilty data for a level. In some cases, we want to load geometry that has been edited back
|
||
|
|
** into the same AABTree without re-partitioning.
|
||
|
|
*/
|
||
|
|
void Update_Bounding_Boxes(void);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Re-insert an object into the tree
|
||
|
|
*/
|
||
|
|
virtual void Update_Culling(CullableClass * obj);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Statistics about the AAB-Tree
|
||
|
|
*/
|
||
|
|
int Partition_Node_Count(void) const;
|
||
|
|
int Partition_Tree_Depth(void) const;
|
||
|
|
int Object_Count(void) const;
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Collect objects which overlap the given primitive
|
||
|
|
*/
|
||
|
|
virtual void Collect_Objects(const Vector3 & point);
|
||
|
|
virtual void Collect_Objects(const AABoxClass & box);
|
||
|
|
virtual void Collect_Objects(const OBBoxClass & box);
|
||
|
|
virtual void Collect_Objects(const FrustumClass & frustum);
|
||
|
|
virtual void Collect_Objects(const SphereClass & sphere);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Load and Save a description of this AAB-Tree and its contents
|
||
|
|
*/
|
||
|
|
virtual void Load(ChunkLoadClass & cload);
|
||
|
|
virtual void Save(ChunkSaveClass & csave);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Save an objects linkage, load the linkage and re-link the object
|
||
|
|
*/
|
||
|
|
void Load_Object_Linkage(ChunkLoadClass & cload,CullableClass * obj);
|
||
|
|
void Save_Object_Linkage(ChunkSaveClass & csave,CullableClass * obj);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Bounding box of the entire tree
|
||
|
|
*/
|
||
|
|
const AABoxClass & Get_Bounding_Box(void);
|
||
|
|
void Get_Node_Bounds(int node_id,AABoxClass * set_bounds);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Statistics
|
||
|
|
*/
|
||
|
|
struct StatsStruct
|
||
|
|
{
|
||
|
|
int NodeCount;
|
||
|
|
int NodesAccepted;
|
||
|
|
int NodesTriviallyAccepted;
|
||
|
|
int NodesRejected;
|
||
|
|
};
|
||
|
|
|
||
|
|
void Reset_Statistics(void);
|
||
|
|
const StatsStruct & Get_Statistics(void);
|
||
|
|
|
||
|
|
protected:
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Internal stat tracking
|
||
|
|
*/
|
||
|
|
#ifdef WWDEBUG
|
||
|
|
void NODE_ACCEPTED(void) { Stats.NodesAccepted ++; }
|
||
|
|
void NODE_TRIVIALLY_ACCEPTED(void) { Stats.NodesTriviallyAccepted ++; }
|
||
|
|
void NODE_REJECTED(void) { Stats.NodesRejected ++; }
|
||
|
|
#else
|
||
|
|
void NODE_ACCEPTED(void) { }
|
||
|
|
void NODE_TRIVIALLY_ACCEPTED(void) { }
|
||
|
|
void NODE_REJECTED(void) { }
|
||
|
|
#endif
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Internal functions
|
||
|
|
*/
|
||
|
|
void Add_Object_Internal(CullableClass * obj,int node_index = -1);
|
||
|
|
void Remove_Object_Internal(CullableClass * obj);
|
||
|
|
|
||
|
|
void Re_Index_Nodes(void);
|
||
|
|
void Re_Index_Nodes_Recursive(AABTreeNodeClass * node,int & counter);
|
||
|
|
|
||
|
|
int Partition_Node_Count_Recursive(AABTreeNodeClass * node) const;
|
||
|
|
void Partition_Tree_Depth_Recursive(AABTreeNodeClass * node,int cur_depth,int & max_depth) const;
|
||
|
|
void Add_Object_Recursive(AABTreeNodeClass * node,CullableClass * obj);
|
||
|
|
void Add_Loaded_Object(AABTreeNodeClass * node,CullableClass * obj);
|
||
|
|
|
||
|
|
void Collect_Objects_Recursive(AABTreeNodeClass * node);
|
||
|
|
void Collect_Objects_Recursive(AABTreeNodeClass * node,const Vector3 & point);
|
||
|
|
void Collect_Objects_Recursive(AABTreeNodeClass * node,const AABoxClass & box);
|
||
|
|
void Collect_Objects_Recursive(AABTreeNodeClass * node,const OBBoxClass & box);
|
||
|
|
void Collect_Objects_Recursive(AABTreeNodeClass * node,const FrustumClass & frustum);
|
||
|
|
void Collect_Objects_Recursive(AABTreeNodeClass * node,const FrustumClass & frustum,int planes_passed);
|
||
|
|
void Collect_Objects_Recursive(AABTreeNodeClass * node,const SphereClass & sphere);
|
||
|
|
|
||
|
|
void Update_Bounding_Boxes_Recursive(AABTreeNodeClass * node);
|
||
|
|
|
||
|
|
void Load_Nodes(AABTreeNodeClass * node,ChunkLoadClass & cload);
|
||
|
|
void Save_Nodes(AABTreeNodeClass * node,ChunkSaveClass & csave);
|
||
|
|
|
||
|
|
virtual void Load_Node_Contents(AABTreeNodeClass * /*node*/,ChunkLoadClass & /*cload*/) { }
|
||
|
|
virtual void Save_Node_Contents(AABTreeNodeClass * /*node*/,ChunkSaveClass & /*csave*/) { }
|
||
|
|
|
||
|
|
AABTreeNodeClass * RootNode; // root of the AAB-Tree
|
||
|
|
int ObjectCount; // number of objects in the system
|
||
|
|
|
||
|
|
int NodeCount; // number of nodes
|
||
|
|
AABTreeNodeClass ** IndexedNodes; // index access to the nodes
|
||
|
|
|
||
|
|
StatsStruct Stats;
|
||
|
|
|
||
|
|
friend class AABTreeIterator;
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
/**
|
||
|
|
** AABTreeIterator
|
||
|
|
** This iterator allows the user to walk a tree. It can return the index of the current
|
||
|
|
** node and the bounds of the current node.
|
||
|
|
*/
|
||
|
|
class AABTreeIterator
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
AABTreeIterator(AABTreeCullSystemClass * tree);
|
||
|
|
|
||
|
|
void Reset(void);
|
||
|
|
bool Enter_Parent(void);
|
||
|
|
bool Enter_Sibling(void);
|
||
|
|
bool Has_Front_Child(void);
|
||
|
|
bool Enter_Front_Child(void);
|
||
|
|
bool Has_Back_Child(void);
|
||
|
|
bool Enter_Back_Child(void);
|
||
|
|
|
||
|
|
int Get_Current_Node_Index(void);
|
||
|
|
void Get_Current_Box(AABoxClass * set_box);
|
||
|
|
|
||
|
|
private:
|
||
|
|
|
||
|
|
void validate(void);
|
||
|
|
|
||
|
|
AABTreeCullSystemClass * Tree;
|
||
|
|
int CurNodeIndex;
|
||
|
|
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
/**
|
||
|
|
** TypedAABTreeCullSystemClass
|
||
|
|
** This template adds type-safety to an AABTree. It allows you to create trees
|
||
|
|
** containing a particular type of object (the class must be derived from CullableClass though)
|
||
|
|
*/
|
||
|
|
template <class T> class TypedAABTreeCullSystemClass : public AABTreeCullSystemClass
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
|
||
|
|
virtual void Add_Object(T * obj,int node_index=-1) { Add_Object_Internal(obj,node_index); }
|
||
|
|
virtual void Remove_Object(T * obj) { Remove_Object_Internal(obj); }
|
||
|
|
|
||
|
|
T * Get_First_Collected_Object(void) { return (T*)Get_First_Collected_Object_Internal(); }
|
||
|
|
T * Get_Next_Collected_Object(T * obj) { return (T*)Get_Next_Collected_Object_Internal(obj); }
|
||
|
|
T * Peek_First_Collected_Object(void) { return (T*)Peek_First_Collected_Object_Internal(); }
|
||
|
|
T * Peek_Next_Collected_Object(T * obj) { return (T*)Peek_Next_Collected_Object_Internal(obj); }
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
/**
|
||
|
|
** AABTreeNodeClass - the aab-tree is built out of these objects
|
||
|
|
** CullableClass's can be linked into any of these nodes. Whenever the
|
||
|
|
** tree is re-built, all objects will end up in the leaf nodes. Between
|
||
|
|
** re-builds, as objects are added, they will be placed as deep into the
|
||
|
|
** tree as possible.
|
||
|
|
*/
|
||
|
|
class AABTreeNodeClass : public AutoPoolClass<AABTreeNodeClass,256>
|
||
|
|
{
|
||
|
|
|
||
|
|
public:
|
||
|
|
|
||
|
|
AABTreeNodeClass(void);
|
||
|
|
~AABTreeNodeClass(void);
|
||
|
|
|
||
|
|
void Add_Object(CullableClass * obj,bool update_bounds = true);
|
||
|
|
void Remove_Object(CullableClass * obj);
|
||
|
|
int Object_Count(void);
|
||
|
|
CullableClass * Peek_Object(int index);
|
||
|
|
|
||
|
|
uint32 Index; // Index of this node
|
||
|
|
AABoxClass Box; // Bounding box of the node
|
||
|
|
AABTreeNodeClass * Parent; // parent of this node
|
||
|
|
AABTreeNodeClass * Front; // front node
|
||
|
|
AABTreeNodeClass * Back; // back node
|
||
|
|
CullableClass * Object; // objects in this node
|
||
|
|
uint32 UserData; // 32bit field for the user, initialized to 0
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Construction support:
|
||
|
|
*/
|
||
|
|
struct SplitChoiceStruct
|
||
|
|
{
|
||
|
|
SplitChoiceStruct(void) : Cost(FLT_MAX),FrontCount(0),BackCount(0),Plane(AAPlaneClass::XNORMAL,0.0f)
|
||
|
|
{
|
||
|
|
FrontBox.Init_Empty();
|
||
|
|
BackBox.Init_Empty();
|
||
|
|
}
|
||
|
|
|
||
|
|
float Cost;
|
||
|
|
int FrontCount;
|
||
|
|
int BackCount;
|
||
|
|
MinMaxAABoxClass FrontBox;
|
||
|
|
MinMaxAABoxClass BackBox;
|
||
|
|
AAPlaneClass Plane;
|
||
|
|
};
|
||
|
|
|
||
|
|
void Compute_Bounding_Box(void);
|
||
|
|
void Compute_Local_Bounding_Box(void);
|
||
|
|
float Compute_Volume(void);
|
||
|
|
void Transfer_Objects(AABTreeNodeClass * dummy_node);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Partition the tree based on the objects contained.
|
||
|
|
*/
|
||
|
|
void Partition(void);
|
||
|
|
void Split_Objects( const SplitChoiceStruct & sc,
|
||
|
|
AABTreeNodeClass * front,
|
||
|
|
AABTreeNodeClass * back);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Partition the tree based on a set of input "seed" boxes.
|
||
|
|
*/
|
||
|
|
void Partition(const AABoxClass & bounds,SimpleDynVecClass<AABoxClass> & boxes);
|
||
|
|
void Split_Boxes( const SplitChoiceStruct & sc,
|
||
|
|
SimpleDynVecClass<AABoxClass> & boxes,
|
||
|
|
SimpleDynVecClass<AABoxClass> & frontboxes,
|
||
|
|
SimpleDynVecClass<AABoxClass> & backboxes);
|
||
|
|
|
||
|
|
/*
|
||
|
|
** Functions used by both partitioning algorithms
|
||
|
|
*/
|
||
|
|
void Select_Splitting_Plane(SplitChoiceStruct * sc,SimpleDynVecClass<AABoxClass> & boxes);
|
||
|
|
void Select_Splitting_Plane_Brute_Force(SplitChoiceStruct * sc,SimpleDynVecClass<AABoxClass> & boxes);
|
||
|
|
void Compute_Score(SplitChoiceStruct * sc,SimpleDynVecClass<AABoxClass> & boxes);
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
/*
|
||
|
|
** AABTreeLinkClass
|
||
|
|
** This structure is used to link objects into an AAB-Tree culling system.
|
||
|
|
*/
|
||
|
|
class AABTreeLinkClass : public CullLinkClass, public AutoPoolClass<AABTreeLinkClass,256>
|
||
|
|
{
|
||
|
|
public:
|
||
|
|
AABTreeLinkClass(AABTreeCullSystemClass * system) : CullLinkClass(system),Node(NULL), NextObject(NULL) { }
|
||
|
|
|
||
|
|
AABTreeNodeClass * Node; // partition node containing this object
|
||
|
|
CullableClass * NextObject; // next object in the node
|
||
|
|
};
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
|
||
|
|
#endif // AABTREECULL_H
|