Renegade/Code/WWMath/aabtreecull.cpp

/*
**	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.cpp                       $*
 *                                                                                             *
 *                       Author:: Greg Hjelstrom                                               *
 *                                                                                             *
 *                     $Modtime:: 8/26/01 2:18p                                               $*
 *                                                                                             *
 *                    $Revision:: 25                                                          $*
 *                                                                                             *
 *---------------------------------------------------------------------------------------------*
 * Functions:                                                                                  *
 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */


#include "aabtreecull.h"
#include "chunkio.h"
#include "iostruct.h"
#include <string.h>
#include "sphere.h"
#include "colmath.h"
#include "colmathinlines.h"



/*
** Declare the pools
*/
DEFINE_AUTO_POOL(AABTreeLinkClass,256);
DEFINE_AUTO_POOL(AABTreeNodeClass,256);


/*
** Current version of the file format
*/
const uint32 AABTREE_CURRENT_VERSION = 0x00010000;


/*
** Chunk Id's used by the aabtree code to save itself into a file
*/
enum 
{
	AABTREE_CHUNK_VERSION					= 0x00000001,	// version wrapper, contains 32bit version #
	AABTREE_CHUNK_AABNODE					= 0x00000101,	// generic aab-node wrapper
		AABTREE_CHUNK_AABNODE_INFO,							// OBSOLETE! generic aab-node definition (IOAABNodeStruct)
		AABTREE_CHUNK_AABNODE_CONTENTS,						// wrapper around contents of the node
		AABTREE_CHUNK_AABNODE_VARIABLES,						// wrapper around variables for a node

	AABTREE_CHUNK_NODE_INDEX				= 0x00000200,	// wrapper around the node index for an object

	AABTREE_VARIABLE_NODESTRUCT			= 0x00,
	AABTREE_VARIABLE_USERDATA
};


/*
** IOAABNodeStruct
** Data structure for the contents of a node in the AAB-Tree
*/
#define AABNODE_ATTRIBUTE_FRONT_CHILD		0x00000001
#define AABNODE_ATTRIBUTE_BACK_CHILD		0x00000002

struct IOAABNodeStruct
{
	IOVector3Struct	Center;
	IOVector3Struct	Extent;
	uint32				Attributes;
};


/*************************************************************************
**
** Utility functions for walking the object list in an AABTree Node
**
*************************************************************************/
static inline CullableClass * get_first_object(AABTreeNodeClass * node)
{
	return node->Object;		
}

static inline CullableClass * get_next_object(CullableClass * obj)
{
	return ((AABTreeLinkClass *)obj->Get_Cull_Link())->NextObject;
}


/*************************************************************************
**
** AABTreeCullSystemClass Implementation
**
*************************************************************************/
AABTreeCullSystemClass::AABTreeCullSystemClass(void) :
	ObjectCount(0),
	NodeCount(0),
	IndexedNodes(NULL)
{
	RootNode = new AABTreeNodeClass;
	Re_Index_Nodes();
}

AABTreeCullSystemClass::~AABTreeCullSystemClass(void)
{
	// Delete all links and release-ref all cullables:
	int nidx;
	for (nidx = 0; nidx < NodeCount; nidx++) {
		while(IndexedNodes[nidx]->Object) Remove_Object_Internal(IndexedNodes[nidx]->Object);
	}

	// Delete node tree (deleting the root recursively deletes all nodes)
	delete RootNode;

	// Delete indexed node pointer array
	if (IndexedNodes) {
		delete[] IndexedNodes;
		IndexedNodes = NULL;
	}
}


void AABTreeCullSystemClass::Add_Object_Internal(CullableClass * obj,int node_index)
{
	WWASSERT_PRINT
	(
		(obj->Get_Culling_System() == NULL),
		"AABTreeCullSystemClass::Add -- Object is already in another culling system!\n"
	);

	AABTreeLinkClass * new_link = new AABTreeLinkClass(this);
	obj->Set_Cull_Link(new_link);

	if (node_index == -1) {
		Add_Object_Recursive(RootNode,obj);
	} else {
		WWASSERT(node_index < NodeCount);
		IndexedNodes[node_index]->Add_Object(obj,false);
		ObjectCount++;
	}

	obj->Add_Ref();
}


void AABTreeCullSystemClass::Remove_Object_Internal(CullableClass * obj)
{
	WWASSERT(obj);
	WWASSERT(obj->Get_Culling_System() == this);

	AABTreeLinkClass * link = (AABTreeLinkClass *)obj->Get_Cull_Link();
	WWASSERT(link);

	AABTreeNodeClass * node = link->Node;
	WWASSERT(node);

	node->Remove_Object(obj);
	link->Set_Culling_System(NULL);
	delete link;
	obj->Set_Cull_Link(NULL);
	
	ObjectCount--;
	WWASSERT(ObjectCount >= 0);
	obj->Release_Ref();
}

void AABTreeCullSystemClass::Update_Culling(CullableClass * obj)
{
	WWASSERT(obj);
	WWASSERT(obj->Get_Culling_System() == this);

	// unlink it from the node it is currently in
	AABTreeLinkClass * link = (AABTreeLinkClass *)obj->Get_Cull_Link();
	WWASSERT(link);
	AABTreeNodeClass * node = link->Node;
	WWASSERT(node);
	node->Remove_Object(obj);
	// decrement the object counter, the node can't
	// decrement it for us...
	ObjectCount--;

	// drop it into the tree again
	Add_Object_Recursive(RootNode,obj);
}

void AABTreeCullSystemClass::Collect_Objects(const Vector3 & point)
{
	Collect_Objects_Recursive(RootNode,point);
}

void AABTreeCullSystemClass::Collect_Objects(const AABoxClass & box)
{
	Collect_Objects_Recursive(RootNode,box);
}

void AABTreeCullSystemClass::Collect_Objects(const OBBoxClass & box)
{
	Collect_Objects_Recursive(RootNode,box);
}

void AABTreeCullSystemClass::Collect_Objects(const FrustumClass & frustum)
{
	Collect_Objects_Recursive(RootNode,frustum,0);
}

void AABTreeCullSystemClass::Collect_Objects(const SphereClass & sphere)
{
	Collect_Objects_Recursive(RootNode,sphere);
}

int AABTreeCullSystemClass::Partition_Node_Count(void) const
{
	return Partition_Node_Count_Recursive(RootNode);
}

int AABTreeCullSystemClass::Partition_Tree_Depth(void) const
{
	int get_max_depth = 0;
	Partition_Tree_Depth_Recursive(RootNode,0,get_max_depth);
	return get_max_depth;
}

int AABTreeCullSystemClass::Object_Count(void) const
{
	return ObjectCount;
}

int AABTreeCullSystemClass::Partition_Node_Count_Recursive(AABTreeNodeClass * node) const
{
	int curcount = 1;
	if (node->Front) {
		curcount += Partition_Node_Count_Recursive(node->Front);
	}
	if (node->Back) {
		curcount += Partition_Node_Count_Recursive(node->Back);
	}
	return curcount;
}

void AABTreeCullSystemClass::Partition_Tree_Depth_Recursive(AABTreeNodeClass * node,int cur_depth,int & max_depth) const
{
	cur_depth++;
	if (cur_depth > max_depth) {
		max_depth = cur_depth;
	}
	if (node->Front) {
		Partition_Tree_Depth_Recursive(node->Front,cur_depth,max_depth);
	} 
	if (node->Back) {
		Partition_Tree_Depth_Recursive(node->Back,cur_depth,max_depth);
	}
}

void AABTreeCullSystemClass::Add_Object_Recursive(AABTreeNodeClass * node,CullableClass * obj)
{
	// order the children in terms of size
	AABTreeNodeClass * big_child = node->Front;
	AABTreeNodeClass * small_child = node->Back;

	if (big_child && small_child && (big_child->Compute_Volume() < small_child->Compute_Volume())) {
		AABTreeNodeClass * tmp = big_child;
		big_child = small_child;
		small_child = tmp;
	}
	
	// Can we fit in the smaller child?
	if (small_child && small_child->Box.Contains(obj->Get_Cull_Box())) {
		Add_Object_Recursive(small_child,obj);
		return;
	}

	// Can we fit in the bigger child?
	if (big_child && big_child->Box.Contains(obj->Get_Cull_Box())) {
		Add_Object_Recursive(big_child,obj);
		return;
	}

	// Ok, we have to fit in this node.
	node->Add_Object(obj);
	ObjectCount++;
}

void AABTreeCullSystemClass::Add_Loaded_Object(AABTreeNodeClass * node,CullableClass * obj)
{
	WWASSERT(node);
	WWASSERT(obj);

	WWASSERT_PRINT
	(
		(obj->Get_Culling_System() == NULL),
		"AABTreeCullSystemClass::Add_Loaded_Object -- Object is already in another culling system!\n"
	);

	AABTreeLinkClass * new_link = new AABTreeLinkClass(this);
	obj->Set_Cull_Link(new_link);

	node->Add_Object(obj);
	ObjectCount++;
	obj->Add_Ref();
}

void AABTreeCullSystemClass::Re_Partition(void)
{
	/*
	** transfer all objects to a temporary node
	*/
	AABTreeNodeClass * dummy_node = new AABTreeNodeClass;
	RootNode->Transfer_Objects(dummy_node);

	/*
	** delete the old tree and make the dummy node the new root
	*/
	delete RootNode;
	RootNode = dummy_node;

	/*
	** partition the objects
	*/
	RootNode->Partition();

	/*
	** re-index the nodes
	*/
	Re_Index_Nodes();

	/*
	** reset the statistics
	*/
	Reset_Statistics();

}

void AABTreeCullSystemClass::Re_Partition(const AABoxClass & bounds,SimpleDynVecClass<AABoxClass> & boxes)
{
	/*
	** transfer all objects to a temporary node
	*/
	AABTreeNodeClass * dummy_node = new AABTreeNodeClass;
	RootNode->Transfer_Objects(dummy_node);

	/*
	** delete the old tree
	*/
	delete RootNode;

	/*
	** allocate a new root node and tell it to partition the given array of boxes
	*/
	RootNode = new AABTreeNodeClass;
	RootNode->Partition(bounds,boxes);

	/*
	** re-index the nodes
	*/
	Re_Index_Nodes();

	/*
	** reset statistics
	*/
	Reset_Statistics();

	/*
	** re-insert all objects and delete the temporary node
	*/
	dummy_node->Box.Extent.Set(0,0,0);
	CullableClass * obj = get_first_object(dummy_node);
	while (obj != NULL) {
		Update_Culling(obj);
		obj = get_first_object(dummy_node);
	}

	delete dummy_node;

	/*
	** Modify the root node so that any object can be added into the tree
	*/
	RootNode->Box.Extent.Set(FLT_MAX,FLT_MAX,FLT_MAX);
}

void AABTreeCullSystemClass::Update_Bounding_Boxes(void)
{
	Update_Bounding_Boxes_Recursive(RootNode);
}

const AABoxClass & AABTreeCullSystemClass::Get_Bounding_Box(void)
{
	WWASSERT(RootNode);
	return RootNode->Box;
}

void AABTreeCullSystemClass::Get_Node_Bounds(int node_id,AABoxClass * set_bounds)
{
	if ((node_id >= 0) && (node_id < NodeCount)) {
		*set_bounds = IndexedNodes[node_id]->Box;
	} else {
		*set_bounds = IndexedNodes[0]->Box;
	}
}

void AABTreeCullSystemClass::Reset_Statistics(void)
{
	Stats.NodeCount = NodeCount;
	Stats.NodesAccepted = 0;
	Stats.NodesTriviallyAccepted = 0;
	Stats.NodesRejected = 0;
}

const AABTreeCullSystemClass::StatsStruct & AABTreeCullSystemClass::Get_Statistics(void)
{
	return Stats;
}

void AABTreeCullSystemClass::Collect_Objects_Recursive(AABTreeNodeClass * node)
{
	/*
	** Collect any objects in this node
	*/
	if (node->Object) {
		CullableClass * obj = get_first_object(node);
		while (obj) {
			Add_To_Collection(obj);
			obj = get_next_object(obj);
		}
	}

	/*
	** Statistics
	*/
	NODE_TRIVIALLY_ACCEPTED();

	/*
	** Descend into the children
	*/
	if (node->Back) {
		Collect_Objects_Recursive(node->Back);
	}
	if (node->Front) {
		Collect_Objects_Recursive(node->Front);
	}
}


void AABTreeCullSystemClass::Collect_Objects_Recursive(AABTreeNodeClass * node,const Vector3 & point)
{
	/*
	** Is the point inside this volume?
	*/
	if (node->Box.Contains(point) == false) {
		NODE_REJECTED();
		return;
	} 

	NODE_ACCEPTED();

	/*
	** Collect any objects in this node
	*/
	if (node->Object) {
		CullableClass * obj = get_first_object(node);
		while (obj) {
			if (obj->Get_Cull_Box().Contains(point)) {
				Add_To_Collection(obj);
			}
			obj = get_next_object(obj);
		}
	}

	/*
	** Descend into the children
	*/
	if (node->Back) {
		Collect_Objects_Recursive(node->Back,point);
	}
	if (node->Front) {
		Collect_Objects_Recursive(node->Front,point);
	}
}

void AABTreeCullSystemClass::Collect_Objects_Recursive(AABTreeNodeClass * node,const AABoxClass & box)
{
	/*
	** Cull the given box against the bounding volume of this node
	** If it is culled, stop descending the tree.  If the current node is
	** completely contained inside the given box, jump into the collection function
	** that doesn't do any more volume checking...
	*/
	CollisionMath::OverlapType overlap = CollisionMath::Overlap_Test(box,node->Box);
	if (overlap == CollisionMath::OUTSIDE) {
		NODE_REJECTED();
		return;
	} else if (overlap == CollisionMath::INSIDE) {
		Collect_Objects_Recursive(node);
		return;
	}
	
	NODE_ACCEPTED();

	/*
	** Test any objects in this node
	*/
	if (node->Object) {
		CullableClass * obj = get_first_object(node);
		while (obj) {
			if (CollisionMath::Overlap_Test(box,obj->Get_Cull_Box()) != CollisionMath::OUTSIDE) {
				Add_To_Collection(obj);
			}
			obj = get_next_object(obj);
		}
	}

	/*
	** Recurse into any children
	*/
	if (node->Back) {
		Collect_Objects_Recursive(node->Back,box);
	}
	if (node->Front) {
		Collect_Objects_Recursive(node->Front,box);
	}
}


void AABTreeCullSystemClass::Collect_Objects_Recursive(AABTreeNodeClass * node,const OBBoxClass & box)
{
	/*
	** Cull the given box against the bounding volume of this node
	** If it is culled, stop descending the tree.  If the current node is
	** completely contained inside the given box, jump into the collection function
	** that doesn't do any more volume checking...
	*/
	CollisionMath::OverlapType overlap = CollisionMath::Overlap_Test(box,node->Box);
	if (overlap == CollisionMath::OUTSIDE) {
		NODE_REJECTED();
		return;
	} else if (overlap == CollisionMath::INSIDE) {
		Collect_Objects_Recursive(node);
		return;
	}
	
	NODE_ACCEPTED();

	/*
	** Test any objects in this node
	*/
	if (node->Object) {
		CullableClass * obj = get_first_object(node);
		while (obj) {
			if (CollisionMath::Overlap_Test(box,obj->Get_Cull_Box()) != CollisionMath::OUTSIDE) {
				Add_To_Collection(obj);
			}
			obj = get_next_object(obj);
		}
	}

	/*
	** Recurse into any children
	*/
	if (node->Back) {
		Collect_Objects_Recursive(node->Back,box);
	}
	if (node->Front) {
		Collect_Objects_Recursive(node->Front,box);
	}
}

void AABTreeCullSystemClass::Collect_Objects_Recursive
(
	AABTreeNodeClass * node,
	const FrustumClass & frustum,
	int planes_passed
)
{
	/*
	** Cull the bounding volume of this node against the frustum.
	** If it is culled, stop descending the tree.
	*/
	CollisionMath::OverlapType overlap = CollisionMath::Overlap_Test(frustum,node->Box,planes_passed);
	if (overlap == CollisionMath::OUTSIDE) {
		NODE_REJECTED();
		return;
	} else if (overlap == CollisionMath::INSIDE) {
		Collect_Objects_Recursive(node);
		return;
	}

	NODE_ACCEPTED();
	
	/*
	** Test any objects in this node
	*/
	if (node->Object) {
		CullableClass * obj = get_first_object(node);
		while (obj) {
			if (CollisionMath::Overlap_Test(frustum,obj->Get_Cull_Box()) != CollisionMath::OUTSIDE) {
				Add_To_Collection(obj);
			}
			obj = get_next_object(obj);
		}
	}

	/*
	** Recurse into any children
	*/
	if (node->Back) {
		Collect_Objects_Recursive(node->Back,frustum,planes_passed);
	}
	if (node->Front) {
		Collect_Objects_Recursive(node->Front,frustum,planes_passed);
	}
}


void AABTreeCullSystemClass::Collect_Objects_Recursive(AABTreeNodeClass * node,const SphereClass & sphere)
{
	/*
	** Is the point inside this volume?
	*/	
	if (CollisionMath::Overlap_Test (node->Box, sphere) == CollisionMath::OUTSIDE) {
		NODE_REJECTED();
		return;
	}
	NODE_ACCEPTED();

	/*
	** Collect any objects in this node
	*/
	if (node->Object) {
		CullableClass * obj = get_first_object(node);
		while (obj) {
			if (CollisionMath::Overlap_Test (obj->Get_Cull_Box(), sphere) != CollisionMath::OUTSIDE) {
				Add_To_Collection(obj);
			}
			obj = get_next_object(obj);
		}
	}

	/*
	** Descend into the children
	*/
	if (node->Back) {
		Collect_Objects_Recursive(node->Back,sphere);
	}
	if (node->Front) {
		Collect_Objects_Recursive(node->Front,sphere);
	}
}

void AABTreeCullSystemClass::Update_Bounding_Boxes_Recursive(AABTreeNodeClass * node)
{
	MinMaxAABoxClass minmaxbox(node->Box);

	/*
	** Update child boxes first and ensure that we bound them
	*/
	if (node->Front) {
		Update_Bounding_Boxes_Recursive(node->Front);
		minmaxbox.Add_Box(node->Front->Box);
	}
	if (node->Back) {
		Update_Bounding_Boxes_Recursive(node->Back);
		minmaxbox.Add_Box(node->Back->Box);
	}

	/*
	** Make sure we bound our contained objects
	*/
	if (node->Object) {
		CullableClass * obj = get_first_object(node);
		while (obj) {
			minmaxbox.Add_Box(obj->Get_Cull_Box());
			obj = get_next_object(obj);
		}
	}

	node->Box.Init_Min_Max(minmaxbox.MinCorner,minmaxbox.MaxCorner);
}


void AABTreeCullSystemClass::Load(ChunkLoadClass & cload)
{
	WWASSERT_PRINT(Object_Count() == 0, "Remove all objects from AAB-Culling system before loading!\n"); 
	
	delete RootNode;
	RootNode = new AABTreeNodeClass;

	// The first chunk should be a version chunk
	cload.Open_Chunk();
	if (cload.Cur_Chunk_ID() != AABTREE_CHUNK_VERSION) {
		WWDEBUG_ERROR(("Attempting to read an obsolete AAB-Tree!"));
		cload.Close_Chunk();
		return;
	}

	// read in the version and verify that it is the current version
	uint32 version;
	cload.Read(&version,sizeof(version));
	if (version != AABTREE_CURRENT_VERSION) {
		WWDEBUG_ERROR(("Attempting to read an obsolete AAB-Tree!"));
		cload.Close_Chunk();
		return;
	}
	cload.Close_Chunk();

	// read in the tree
	Load_Nodes(RootNode,cload);

	// re-index all nodes
	Re_Index_Nodes();

	// reset the statistics
	Reset_Statistics();
}

void AABTreeCullSystemClass::Load_Nodes(AABTreeNodeClass * node,ChunkLoadClass & cload)
{
	// Open the node description
	cload.Open_Chunk();
	WWASSERT(cload.Cur_Chunk_ID() == AABTREE_CHUNK_AABNODE);
	
	// Load the node description.  
	// Older files will contain a chunk named AABTREE_CHUNK_AABNODE_INFO while newer
	// files will contain AABTREE_CHUNK_AABNODE_VARIABLES which contains the IOAABNodeStruct
	// in a micro-chunk.
	IOAABNodeStruct node_desc;
	memset(&node_desc,0,sizeof(IOAABNodeStruct));
	
	cload.Open_Chunk(); 
	if (cload.Cur_Chunk_ID() == AABTREE_CHUNK_AABNODE_INFO) {

		// Loading the legacy format...
		WWASSERT(cload.Cur_Chunk_ID() == AABTREE_CHUNK_AABNODE_INFO);
		cload.Read(&node_desc,sizeof(node_desc));

	} else if (cload.Cur_Chunk_ID() == AABTREE_CHUNK_AABNODE_VARIABLES) {
	
		// Loading the new format, contains micro chunks...
		while (cload.Open_Micro_Chunk()) {
			switch(cload.Cur_Micro_Chunk_ID()) {
				READ_MICRO_CHUNK(cload,AABTREE_VARIABLE_NODESTRUCT,node_desc);
				READ_MICRO_CHUNK(cload,AABTREE_VARIABLE_USERDATA,node->UserData);
			}
			cload.Close_Micro_Chunk();	
		}
	}
	cload.Close_Chunk();

	// Initialize the node bounds.
	node->Box.Center.X = node_desc.Center.X;
	node->Box.Center.Y = node_desc.Center.Y;
	node->Box.Center.Z = node_desc.Center.Z;

	node->Box.Extent.X = node_desc.Extent.X;
	node->Box.Extent.Y = node_desc.Extent.Y;
	node->Box.Extent.Z = node_desc.Extent.Z;

	// Load the contents of the node.
	cload.Open_Chunk();
	WWASSERT(cload.Cur_Chunk_ID() == AABTREE_CHUNK_AABNODE_CONTENTS);
	Load_Node_Contents(node,cload);
	cload.Close_Chunk();

	// Close the node description
	cload.Close_Chunk(); 

	// if we are supposed to have a front child, load it
	if (node_desc.Attributes & AABNODE_ATTRIBUTE_FRONT_CHILD) {
		WWASSERT(node->Front == NULL);
		node->Front = new AABTreeNodeClass();
		node->Front->Parent = node;
		Load_Nodes(node->Front,cload);
	}
	
	// if we have a back child, load it
	if (node_desc.Attributes & AABNODE_ATTRIBUTE_BACK_CHILD) {
		WWASSERT(node->Back == NULL);
		node->Back = new AABTreeNodeClass();
		node->Back->Parent = node;
		Load_Nodes(node->Back,cload);
	}
}

void AABTreeCullSystemClass::Save(ChunkSaveClass & csave)
{
	csave.Begin_Chunk(AABTREE_CHUNK_VERSION);
	uint32 version = AABTREE_CURRENT_VERSION;
	csave.Write(&version,sizeof(uint32));
	csave.End_Chunk();

	Save_Nodes(RootNode,csave);
}

void AABTreeCullSystemClass::Save_Nodes(AABTreeNodeClass * node,ChunkSaveClass & csave)
{
	WWASSERT(node);
	csave.Begin_Chunk(AABTREE_CHUNK_AABNODE);

	csave.Begin_Chunk(AABTREE_CHUNK_AABNODE_VARIABLES);
	IOAABNodeStruct node_desc;
	memset(&node_desc,0,sizeof(node_desc));

	node_desc.Center.X = node->Box.Center.X;
	node_desc.Center.Y = node->Box.Center.Y;
	node_desc.Center.Z = node->Box.Center.Z;

	node_desc.Extent.X = node->Box.Extent.X;
	node_desc.Extent.Y = node->Box.Extent.Y;
	node_desc.Extent.Z = node->Box.Extent.Z;

	if (node->Front) {
		node_desc.Attributes |= AABNODE_ATTRIBUTE_FRONT_CHILD;
	}

	if (node->Back) {
		node_desc.Attributes |= AABNODE_ATTRIBUTE_BACK_CHILD;
	}
	
	WRITE_MICRO_CHUNK(csave,AABTREE_VARIABLE_NODESTRUCT,node_desc);
	WRITE_MICRO_CHUNK(csave,AABTREE_VARIABLE_USERDATA,node->UserData);
	csave.End_Chunk();

	csave.Begin_Chunk(AABTREE_CHUNK_AABNODE_CONTENTS);
	Save_Node_Contents(node,csave);
	csave.End_Chunk();

	csave.End_Chunk();

	if (node->Front) {
		Save_Nodes(node->Front,csave);
	}

	if (node->Back) {
		Save_Nodes(node->Back,csave);
	}
}

void AABTreeCullSystemClass::Load_Object_Linkage(ChunkLoadClass & cload,CullableClass * obj)
{
	uint32 index;
	cload.Open_Chunk();
	WWASSERT(cload.Cur_Chunk_ID() == AABTREE_CHUNK_NODE_INDEX);
	cload.Read(&index,sizeof(index));
	cload.Close_Chunk();

	Add_Object_Internal(obj,index);
}

void AABTreeCullSystemClass::Save_Object_Linkage(ChunkSaveClass & csave,CullableClass * obj)
{
	WWASSERT(obj);
	WWASSERT(obj->Get_Culling_System() == this);

	AABTreeLinkClass * link = (AABTreeLinkClass *)obj->Get_Cull_Link();
	WWASSERT(link);

	AABTreeNodeClass * node = link->Node;
	WWASSERT(node);

	uint32 index = node->Index;
	csave.Begin_Chunk(AABTREE_CHUNK_NODE_INDEX);
	csave.Write(&index,sizeof(index));
	csave.End_Chunk();
}


void AABTreeCullSystemClass::Re_Index_Nodes(void)
{
	if (IndexedNodes != NULL) {
		delete[] IndexedNodes;
		IndexedNodes = NULL;
	}
	NodeCount = Partition_Node_Count();
	WWASSERT(NodeCount > 0);
	IndexedNodes = new AABTreeNodeClass *[NodeCount];
	
	int counter = 0;
	Re_Index_Nodes_Recursive(RootNode,counter);
	WWASSERT(counter == NodeCount);
}


void AABTreeCullSystemClass::Re_Index_Nodes_Recursive(AABTreeNodeClass * node,int & counter)
{
	node->Index = counter;
	IndexedNodes[counter] = node;
	counter++;

	if (node->Front) {
		Re_Index_Nodes_Recursive(node->Front,counter);
	}
	if (node->Back) {
		Re_Index_Nodes_Recursive(node->Back,counter);
	}
}



/*************************************************************************
**
** AABTreeNodeClass Implementation
**
*************************************************************************/
AABTreeNodeClass::AABTreeNodeClass(void) :
	Index(0),	
	Box(Vector3(0,0,0),Vector3(0,0,0)),
	Parent(NULL),
	Front(NULL),
	Back(NULL),
	Object(NULL),
	UserData(0)
{
}

AABTreeNodeClass::~AABTreeNodeClass(void)
{
	// objects should be removed before deleting the partition tree
	WWASSERT(Object == NULL);
	
	// delete our children
	if (Front) {
		delete Front;
		Front = NULL;
	}
	if (Back) {
		delete Back;
		Back = NULL;
	}
}

void AABTreeNodeClass::Compute_Bounding_Box(void)
{
	/*
	** make the children update their boxes first
	*/
	if (Front) {
		Front->Compute_Bounding_Box();
	}

	if (Back) { 
		Back->Compute_Bounding_Box();
	}

	Compute_Local_Bounding_Box();
}

void AABTreeNodeClass::Compute_Local_Bounding_Box(void)
{
	/*
	** Now make sure we bound our children
	*/
	MinMaxAABoxClass box(Vector3(FLT_MAX,FLT_MAX,FLT_MAX),Vector3(-FLT_MAX,-FLT_MAX,-FLT_MAX));
	
	if (Front) {
		box.Add_Box(Front->Box);
	}

	if (Back) {
		box.Add_Box(Back->Box);
	}

	/*
	** bound the objects in this node
	*/
	CullableClass * obj = Object;
	while (obj) {
		box.Add_Box(obj->Get_Cull_Box());
		AABTreeLinkClass * link = (AABTreeLinkClass *)obj->Get_Cull_Link();
		obj = link->NextObject;
	}

	Box.Init(box);
}

float AABTreeNodeClass::Compute_Volume(void)
{
	return Box.Volume();
}

void AABTreeNodeClass::Add_Object(CullableClass * obj,bool update_bounds)
{
	AABTreeLinkClass * link = (AABTreeLinkClass *)obj->Get_Cull_Link();
	WWASSERT(link);
	
	link->Node = this;
	link->NextObject = Object;
	Object = obj;

	if (update_bounds) {
		// if this is the only object and we have no children, just copy 
		// the object's bounding box, otherwise, add it to what we have
		if ((Object_Count() == 1) && (Front == NULL) && (Back == NULL)) {
			Box = obj->Get_Cull_Box();
		} else {
			Box.Add_Box(obj->Get_Cull_Box());
		}
	}
}

void AABTreeNodeClass::Remove_Object(CullableClass * obj)
{
	WWASSERT(obj);

	// find the given object in our linked list
	CullableClass * prevobj = NULL;
	CullableClass * curobj = Object;
	
	while (curobj) {

		AABTreeLinkClass * link = (AABTreeLinkClass *)curobj->Get_Cull_Link();

		if (curobj == obj) {
			// found the object, unlink it.
			if (prevobj) {
				AABTreeLinkClass * prevlink = (AABTreeLinkClass *)prevobj->Get_Cull_Link();
				prevlink->NextObject = link->NextObject;
			} else {
				Object = link->NextObject;
			}

			link->NextObject = NULL;
			link->Node = NULL;
			return;
		}

		// move to the next object
		prevobj = curobj;
		curobj = link->NextObject;
	}
}

void AABTreeNodeClass::Transfer_Objects(AABTreeNodeClass * dummy_node)
{
	// unlink all of our objects, relinking them to the dummy_node
	while (Object) {
		CullableClass * obj = Object;
		Remove_Object(obj);
		dummy_node->Add_Object(obj);
	}

	// do the same with our children
	if (Front) {
		Front->Transfer_Objects(dummy_node);
	}
	
	if (Back) {
		Back->Transfer_Objects(dummy_node);
	}
}

int AABTreeNodeClass::Object_Count(void)
{
	CullableClass * obj = Object;
	int count = 0;

	while (obj) {
		count++;
		obj = ((AABTreeLinkClass *)obj->Get_Cull_Link())->NextObject;
	}

	return count;
}

CullableClass * AABTreeNodeClass::Peek_Object(int index)
{
	int count = 0;
	CullableClass * obj = Object;
	WWASSERT(obj != NULL);

	while (obj && (count != index)) {
		count++;				
		obj = ((AABTreeLinkClass *)obj->Get_Cull_Link())->NextObject;
	}
	WWASSERT(count == index);
	return obj;
}


/******************************************************************************************
**
** Partitioning code which partitions the objects in the tree and passes them into
** the new children
**
******************************************************************************************/

void AABTreeNodeClass::Partition(void)
{
	/*
	** if we're down to only 2 objects, we're done
	*/
	int obj_count = Object_Count();
	if (obj_count <= 2) return;

	/*
	** Create an array of the bounding boxes of our objects
	*/
	SimpleDynVecClass<AABoxClass> boxes(obj_count);
	CullableClass * obj = Object;
	while (obj != NULL) {
		boxes.Add(obj->Get_Cull_Box());		
		obj = get_next_object(obj);
	}

	/*
	** Select and assign the splitting plane
	** De-allocate the array of boxes to conserve memory
	*/
	SplitChoiceStruct sc;
	Select_Splitting_Plane(&sc,boxes);
	boxes.Resize(0);
	
	/*
	** If there was no good split, just leave all of
	** the objects in this node
	*/
	if (sc.Cost == FLT_MAX) {
		return;
	}

	/*
	** Split the tiles 
	*/
	AABTreeNodeClass * front = new AABTreeNodeClass;
	AABTreeNodeClass * back = new AABTreeNodeClass;
	Split_Objects(sc,front,back);

	/*
	** Build a front tree if necessary.
	*/
	if (front->Object_Count() > 0) {
		Front = front;
		Front->Parent = this;
		Front->Partition();
	} else {
		delete front;
		front = NULL;
	}
	
	/*
	** Build a back tree if necessary. 
	*/
	if (back->Object_Count() > 0) {
		Back = back;
		Back->Parent = this;
		Back->Partition();
	} else {
		delete back;
		back = NULL;
	}
}



void AABTreeNodeClass::Split_Objects(const AABTreeNodeClass::SplitChoiceStruct & sc,AABTreeNodeClass * front,AABTreeNodeClass * back)
{
	// This function assumes that this node is a leaf
	WWASSERT(Front == NULL);
	WWASSERT(Back == NULL);
	WWASSERT(Object_Count() == sc.FrontCount + sc.BackCount);

	int fcount = 0;
	int bcount = 0;
	
	// unlink all of our objects, relinking them to the appropriate node
	while (Object) {
		
		// pull the object out of this node
		CullableClass * obj = Object;
		Remove_Object(Object);
		
		// decide which node to add the object to, 
		// NOTE: we have to use the same convention as Compute_Score!
		const AABoxClass & box = obj->Get_Cull_Box();

		if (CollisionMath::Overlap_Test(sc.Plane,box.Center) == CollisionMath::FRONT) {

			front->Add_Object(obj);
			fcount++;

		} else {

			back->Add_Object(obj);
			bcount++;

		}
	}

	// copy the bounding boxes
	front->Box = sc.FrontBox;
	front->Box.Extent += Vector3(WWMATH_EPSILON,WWMATH_EPSILON,WWMATH_EPSILON);
	back->Box = sc.BackBox;
	back->Box.Extent += Vector3(WWMATH_EPSILON,WWMATH_EPSILON,WWMATH_EPSILON);

	// when we are all done, the counts should match. 
	WWASSERT(fcount == sc.FrontCount);
	WWASSERT(bcount == sc.BackCount);
}




/******************************************************************************************
**
** Partitioning code which generates the tree based on a set of input boxes
**
******************************************************************************************/
void AABTreeNodeClass::Partition(const AABoxClass & bounds,SimpleDynVecClass<AABoxClass> & boxes)
{
	Box = bounds;

	/*
	** if we're down to only 1 box, we're done
	*/
	if (boxes.Count() <= 1) return;

	/*
	** Select and assign the splitting plane
	*/
	SplitChoiceStruct sc;
	Select_Splitting_Plane(&sc,boxes);
	
	/*
	** If there was no good split, just leave all of
	** the objects in this node
	*/
	if (sc.Cost == FLT_MAX) {
		return;
	}

	/*
	** Split the boxes
	** Deallocate the input box array to conserve RAM
	*/
	SimpleDynVecClass<AABoxClass> frontboxes(sc.FrontCount);
	SimpleDynVecClass<AABoxClass> backboxes(sc.BackCount);
	Split_Boxes(sc,boxes,frontboxes,backboxes);
	boxes.Delete_All();

	/*
	** Build a front tree if necessary.
	*/
	if (frontboxes.Count() > 0) {
		Front = new AABTreeNodeClass;
		Front->Parent = this;
		Front->Partition(sc.FrontBox,frontboxes);
	} else {
		Front = NULL;
	}
	
	/*
	** Build a back tree if necessary. 
	*/
	if (backboxes.Count() > 0) {
		Back = new AABTreeNodeClass;
		Back->Parent = this;
		Back->Partition(sc.BackBox,backboxes);
	} else {
		Back = NULL;
	}
}

void AABTreeNodeClass::Split_Boxes
(
	const AABTreeNodeClass::SplitChoiceStruct & sc,
	SimpleDynVecClass<AABoxClass> & boxes,
	SimpleDynVecClass<AABoxClass> & frontboxes,
	SimpleDynVecClass<AABoxClass> & backboxes
)
{
	WWASSERT(boxes.Count() == sc.FrontCount + sc.BackCount);

	// copy each box in the input array into the appropriate output array
	for (int i=0; i<boxes.Count(); i++) {
		
		const AABoxClass & box = boxes[i];

		if (CollisionMath::Overlap_Test(sc.Plane,box.Center) == CollisionMath::FRONT) {

			frontboxes.Add(box);

		} else {

			backboxes.Add(box);

		}
	}

	// when we are all done, the counts should match. 
	WWASSERT(frontboxes.Count() == sc.FrontCount);
	WWASSERT(backboxes.Count() == sc.BackCount);
}



/******************************************************************************************
**
** Partitioning code which searches for the best split for a given set of boxes.  This
** code is re-used by both types of partitioning (partitioning contained objects or
** partitioning based on a set of "seed" boxes.)
**
******************************************************************************************/

void AABTreeNodeClass::Select_Splitting_Plane
(
	SplitChoiceStruct * sc,
	SimpleDynVecClass<AABoxClass> & boxes
)
{
	const int NUM_TRYS = 300;

	/*
	** Try putting axis-aligned planes through some random vertices
	*/
	int objcount = boxes.Count();	
	int trys = 0;
	for (trys = 0; trys < MIN(NUM_TRYS,objcount); trys++) {

		int obj_index;
		SplitChoiceStruct test;
		
		/*
		** Select a random object
		*/
		obj_index = rand() % objcount;
		const AABoxClass & box = boxes[obj_index];

		/*
		** Select a random plane which co-incides with one of the faces
		** of the object's bounding box
		*/
		switch(rand() % 6) {
			case 0:	test.Plane.Set(AAPlaneClass::XNORMAL,box.Center.X + box.Extent.X);	break;
			case 1:	test.Plane.Set(AAPlaneClass::XNORMAL,box.Center.X - box.Extent.X);	break;
			case 2:	test.Plane.Set(AAPlaneClass::YNORMAL,box.Center.Y + box.Extent.Y);	break;
			case 3:	test.Plane.Set(AAPlaneClass::YNORMAL,box.Center.Y - box.Extent.Y);	break;
			case 4:	test.Plane.Set(AAPlaneClass::ZNORMAL,box.Center.Z + box.Extent.Z);	break;
			case 5:	test.Plane.Set(AAPlaneClass::ZNORMAL,box.Center.Z - box.Extent.Z);	break;
		};

		/*
		** Get the score for this plane
		*/
		Compute_Score(&test,boxes);
		if (test.Cost < sc->Cost) {
			*sc = test;
		}

	}

	/*
	** Still haven't found a valid splitting plane, uh-oh.
	*/
	if ((trys >= MIN(NUM_TRYS,objcount)) && (sc->Cost == FLT_MAX)) {
		Select_Splitting_Plane_Brute_Force(sc,boxes);
		return;
	}
}

void AABTreeNodeClass::Select_Splitting_Plane_Brute_Force
(
	AABTreeNodeClass::SplitChoiceStruct * sc,
	SimpleDynVecClass<AABoxClass> & boxes
)
{ 
	/*
	** Try putting axis-aligned planes along each face of each box
	*/
	int objcount = boxes.Count();	
	for (int obj_index = 0; obj_index < objcount; obj_index++) {

		AAPlaneClass plane;
		const AABoxClass & box = boxes[obj_index];

		/*
		** Try each face of this box 
		*/
		for (int plane_index = 0; plane_index < 6; plane_index++) {
			SplitChoiceStruct test;
			switch(plane_index % 6) {
				case 0:	test.Plane.Set(AAPlaneClass::XNORMAL,box.Center.X + box.Extent.X);	break;
				case 1:	test.Plane.Set(AAPlaneClass::XNORMAL,box.Center.X - box.Center.Y);	break;
				case 2:	test.Plane.Set(AAPlaneClass::YNORMAL,box.Center.Y + box.Center.Y);	break;
				case 3:	test.Plane.Set(AAPlaneClass::YNORMAL,box.Center.Y - box.Center.Y);	break;
				case 4:	test.Plane.Set(AAPlaneClass::ZNORMAL,box.Center.Z + box.Center.Z);	break;
				case 5:	test.Plane.Set(AAPlaneClass::ZNORMAL,box.Center.Z - box.Center.Z);	break;
			};

			test.FrontBox.Init_Empty();
			test.BackBox.Init_Empty();

			/*
			** Get the score for this plane
			*/
			Compute_Score(&test,boxes);
			if (test.Cost < sc->Cost) {
				*sc = test;
			}
		}
	}

	/*
	** Notify user that we couldn't split this node
	*/
#ifdef WWDEBUG
	if (sc->Cost == FLT_MAX) {		
		WWDEBUG_SAY(("Unable to split node!  objcount = %d. (%.2f,%.2f,%.2f)\r\n",objcount,Box.Center.X, Box.Center.Y, Box.Center.Z));
	}
#endif
}


void AABTreeNodeClass::Compute_Score
(
	AABTreeNodeClass::SplitChoiceStruct * sc,
	SimpleDynVecClass<AABoxClass> & boxes
)
{
	/*
	** Suitability of a plane as a partition plane is based on the following factors:
	** - How many "tiles" are on each side of the plane,
	*/
	for (int i=0; i<boxes.Count(); i++) {

		const AABoxClass & box = boxes[i];

		if (CollisionMath::Overlap_Test(sc->Plane,box.Center) == CollisionMath::FRONT) {

			sc->FrontCount++;	
			sc->FrontBox.Add_Box(box);	

		} else {
			
			sc->BackCount++;	
			sc->BackBox.Add_Box(box);	

		}
	}

	/*
	** Compute the cost.
	*/
	float back_cost = sc->BackBox.Volume() * sc->BackCount;
	float front_cost = sc->FrontBox.Volume() * sc->FrontCount;
	
	sc->Cost = front_cost + back_cost;
	
	if ((sc->FrontCount == 0) || (sc->BackCount == 0)) {
		sc->Cost = FLT_MAX;
	}
}



/**************************************************************************************

  AABTreeIterator Implemenation

**************************************************************************************/


AABTreeIterator::AABTreeIterator(AABTreeCullSystemClass * tree) :
	Tree(tree),
	CurNodeIndex(0)
{
	WWASSERT(Tree != NULL);
}
	
void AABTreeIterator::Reset(void)
{
	CurNodeIndex = 0;
}

bool AABTreeIterator::Enter_Parent(void)						
{
	validate();
	if (CurNodeIndex != 0) {
		CurNodeIndex = Tree->IndexedNodes[CurNodeIndex]->Parent->Index;
		return true;
	} else {
		return false;
	}
}

bool AABTreeIterator::Enter_Sibling(void)
{
	validate();
	if (CurNodeIndex != 0) {
		
		/*
		** find which child of our parent we are
		*/
		AABTreeNodeClass * parent = Tree->IndexedNodes[CurNodeIndex]->Parent;
		AABTreeNodeClass * parent_front = parent->Front;
		AABTreeNodeClass * parent_back = parent->Back;

		/*
		** if our parent doesn't have two children, we don't have a sibling
		*/
		if ((parent_front == NULL) || (parent_back == NULL)) {
			return false;
		}

		/*
		** if we our our parent's front child, go to its back child
		*/
		if ((int)parent_front->Index == CurNodeIndex) {
			CurNodeIndex = parent_back->Index;
			return true;
		}

		/*
		** if we our our parent's back child, go to its front child
		*/
		if ((int)parent_back->Index == (int)CurNodeIndex) {
			CurNodeIndex = parent_front->Index;
			return true;
		}
	}
	return false;
}

bool AABTreeIterator::Has_Front_Child(void)
{
	validate();
	return (Tree->IndexedNodes[CurNodeIndex]->Front != NULL);
}

bool AABTreeIterator::Enter_Front_Child(void)
{
	validate();
	if (Has_Front_Child()) {
		CurNodeIndex = Tree->IndexedNodes[CurNodeIndex]->Front->Index;
		return true;
	}
	return false;
}

bool AABTreeIterator::Has_Back_Child(void)
{
	validate();
	return (Tree->IndexedNodes[CurNodeIndex]->Back != NULL);
}

bool AABTreeIterator::Enter_Back_Child(void)
{
	if (Has_Back_Child()) {
		CurNodeIndex = Tree->IndexedNodes[CurNodeIndex]->Back->Index;
		return true;
	}
	return false;
}

int AABTreeIterator::Get_Current_Node_Index(void)
{
	return CurNodeIndex;
}

void AABTreeIterator::Get_Current_Box(AABoxClass * set_box)
{
	Tree->Get_Node_Bounds(CurNodeIndex,set_box);	
}

void AABTreeIterator::validate(void)
{
	if ((CurNodeIndex < 0) || (CurNodeIndex >= Tree->NodeCount)) {
		CurNodeIndex = 0;
	}
}

/*

  Can we make a more compact AABTree?

  Here is the existing data in each Node:

	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

	Total Size:				48 bytes

	Here is a possible replacement:

	uint16					Index;
	short						x,y,z,w,l,h;		// Need origin and scale factors for the boxes stored in tree
	uint16					ParentIndex;
	uint16					FrontIndex;
	uint16					BackIndex;
	CullableClass *		Object;
	uint32					UserData;
	
	Total Size:				28 bytes

*/