Renegade/Code/ww3d2/aabtree.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 : WW3D                                                         *
 *                                                                                             *
 *                     $Archive:: /Commando/Code/ww3d2/aabtree.cpp                            $*
 *                                                                                             *
 *                       Author:: Greg Hjelstrom                                               *
 *                                                                                             *
 *                     $Modtime:: 11/24/01 5:34p                                              $*
 *                                                                                             *
 *                    $Revision:: 4                                                           $*
 *                                                                                             *
 *---------------------------------------------------------------------------------------------*
 * Functions:                                                                                  *
 *   AABTreeClass::AABTreeClass -- Constructor                                                 *
 *   AABTreeClass::AABTreeClass -- Constructor                                                 *
 *   AABTreeClass::AABTreeClass -- copy constructor                                            *
 *   AABTreeClass::~AABTreeClass -- Destructor                                                 *
 *   AABTreeClass::operator =  -- assignment operator                                          *
 *   AABTreeClass::Reset -- reset this tree, releases all allocated resources                  *
 *   AABTreeClass::Build_Tree_Recursive -- Initializes this tree from the given builder        *
 *   AABTreeClass::Set_Mesh -- set the mesh pointer                                            *
 *   AABTreeClass::Generate_APT -- Generate an active poly table for the mesh                  *
 *   AABTreeClass::Generate_OBBox_APT_Recursive -- recursively generate the apt                *
 *   AABTreeClass::Cast_Ray_Recursive -- Internal implementation of Cast_Ray                   *
 *   AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive -- Internal implementation    *
 *   AABTreeClass::Cast_AABox_Recursive -- internal implementation of Cast_AABox               *
 *   AABTreeClass::Cast_OBBox_Recursive -- Internal implementation of Cast_OBBox               *
 *   AABTreeClass::Intersect_OBBox_Recursive -- internal implementation of Intersect_OBBox     *
 *   AABTreeClass::Cast_Ray_To_Polys -- cast the ray to polys in the given node                *
 *   AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys -- cast ray to polys in the nod*
 *   AABTreeClass::Cast_AABox_To_Polys -- cast aabox to polys in the given node                *
 *   AABTreeClass::Cast_OBBox_To_Polys -- cast obbox to polys in the given node                *
 *   AABTreeClass::Intersect_OBBox_With_Polys -- Test polys for intersection                   *
 *   AABTreeClass::Update_Bounding_Boxes_Recursive -- recompute the bounding boxes             *
 *   AABTreeClass::Update_Min_Max -- updates min and max given a polygon index                 *
 *   AABTreeClass::Load_W3D -- Load a W3D description of an AABTree                            *
 *   AABTreeClass::Read_Poly_Indices -- load the polygon index array                           *
 *   AABTreeClass::Read_Nodes -- Load the node array                                           *
 *   AABTreeClass::Generate_APT -- generate an apt from a box and viewdir                      *
 *   AABTreeClass::Generate_OBBox_APT_Recursive -- recurse, generate the apt for a box and vie *
 * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */


#include "aabtree.h"
#include "aabtreebuilder.h"
#include "wwdebug.h"
#include "tri.h"
#include "meshgeometry.h"
#include "camera.h"
#include "coltest.h"
#include "inttest.h"
#include "colmathinlines.h"
#include "w3d_file.h"
#include "chunkio.h"



/***********************************************************************************************
 * AABTreeClass::AABTreeClass -- Constructor                                                   *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *=============================================================================================*/
AABTreeClass::AABTreeClass(void) :
	NodeCount(0),
	Nodes(NULL),
	PolyCount(0),
	PolyIndices(NULL),
	Mesh(NULL)
{
}

/***********************************************************************************************
 * AABTreeClass::AABTreeClass -- Constructor                                                   *
 *                                                                                             *
 *  Builds an AABTree from the contents of an AABTreeBuilderClass.                             *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/19/98    GTH : Created.                                                                 *
 *   5/23/2000  gth : Created.                                                                 *
 *=============================================================================================*/
AABTreeClass::AABTreeClass(AABTreeBuilderClass * builder)
{
	NodeCount = builder->Node_Count();
	Nodes = new AABTreeClass::CullNodeStruct[NodeCount];

	PolyCount = builder->Poly_Count();
	PolyIndices = new uint32[PolyCount];

	int curpolyindex = 0;
	Build_Tree_Recursive(builder->Root,curpolyindex);
}


/***********************************************************************************************
 * AABTreeClass::AABTreeClass -- copy constructor                                              *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/22/99    GTH : Created.                                                                 *
 *=============================================================================================*/
AABTreeClass::AABTreeClass(const AABTreeClass & that) :
	NodeCount(0),
	Nodes(NULL),
	PolyCount(0),
	PolyIndices(0),
	Mesh(NULL)
{ 
	*this = that; 
}

/***********************************************************************************************
 * AABTreeClass::~AABTreeClass -- Destructor                                                   *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/19/98    GTH : Created.                                                                 *
 *=============================================================================================*/
AABTreeClass::~AABTreeClass(void)
{
	Reset();
}

/***********************************************************************************************
 * AABTreeClass::operator =  -- assignment operator                                            *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/22/99    GTH : Created.                                                                 *
 *=============================================================================================*/
AABTreeClass & AABTreeClass::operator = (const AABTreeClass & that)
{
	Reset();
	
	NodeCount = that.NodeCount;
	if (NodeCount > 0) {
		Nodes = new CullNodeStruct[NodeCount];
		memcpy(Nodes,that.Nodes,NodeCount * sizeof(CullNodeStruct));
	}

	PolyCount = that.PolyCount;
	if (PolyCount > 0) {
		PolyIndices = new uint32[PolyCount];
		memcpy(PolyIndices,that.PolyIndices,PolyCount * sizeof(uint32));
	}

	Mesh = that.Mesh;

	return *this;
}


/***********************************************************************************************
 * AABTreeClass::Reset -- reset this tree, releases all allocated resources                    *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/22/99    GTH : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Reset(void)
{
	NodeCount = 0;
	if (Nodes) {
		delete[] Nodes;
		Nodes = NULL;
	}
	PolyCount = 0;
	if (PolyIndices) {
		delete[] PolyIndices;
		PolyIndices = NULL;
	}
	if (Mesh) {
		Mesh = NULL;
	}
}


/***********************************************************************************************
 * AABTreeClass::Build_Tree_Recursive -- Initializes this tree from the given builder          *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   5/19/2000  gth : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Build_Tree_Recursive(AABTreeBuilderClass::CullNodeStruct * node,int & curpolyindex)
{
	/*
	** Copy data from the builder's node into our node
	*/
	CullNodeStruct * newnode = &(Nodes[node->Index]);

	newnode->Min = node->Min;
	newnode->Max = node->Max;
	
	/*
	** If this is a non-leaf node, set up the child indices, otherwise set up the polygon indices
	*/
	if (node->Front != NULL) {

		WWASSERT(node->Back != NULL);		// if we have one child, we better have both!
		newnode->Set_Front_Child(node->Front->Index);
		newnode->Set_Back_Child(node->Back->Index);
	
	} else {

		newnode->Set_Poly0(curpolyindex);
		newnode->Set_Poly_Count(node->PolyCount);

	}

	/*
	** Copy the polygon indices for this node into our array
	*/
	for (int pcounter = 0; pcounter < node->PolyCount; pcounter++) {
		PolyIndices[curpolyindex++] = node->PolyIndices[pcounter];
	}

	/*
	** Install the children
	*/
	if (node->Front) {
		Build_Tree_Recursive(node->Front,curpolyindex);
	}
	if (node->Back) {
		Build_Tree_Recursive(node->Back,curpolyindex);
	}
}


/***********************************************************************************************
 * AABTreeClass::Set_Mesh -- set the mesh pointer                                              *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/22/99    GTH : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Set_Mesh(MeshGeometryClass * mesh)
{
	Mesh = mesh;
}


/***********************************************************************************************
 * AABTreeClass::Generate_APT -- Generate an active poly table for the mesh                    *
 *                                                                                             *
 * INPUT:                                                                                      *
 * box - oriented box to cull the mesh against (in the mesh's coordinate system!!!)            *
 * apt - vector of ints to fill the apt into                                                   *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *=============================================================================================*/
void AABTreeClass::Generate_APT(const OBBoxClass & box,SimpleDynVecClass<uint32> & apt)
{
	OBBoxAPTContextStruct context(box,apt);
	Generate_OBBox_APT_Recursive(&(Nodes[0]),context);
}



/***********************************************************************************************
 * AABTreeClass::Generate_OBBox_APT_Recursive -- recursively generate the apt                  *
 *                                                                                             *
 * INPUT:                                                                                      *
 * node - current node in the recursion                                                        *
 * context - structure containing the results/current state                                    *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   1/25/00    gth : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Generate_OBBox_APT_Recursive(CullNodeStruct * node,OBBoxAPTContextStruct & context)
{
	/*
	** Test the volume against the bounding volume of this node
	** If it is outside, stop descending the tree.
	*/
	AABoxClass nodebox;
	nodebox.Init_Min_Max(node->Min,node->Max);				// NOTE: too bad we have to compute the nodebox!!!
	
	if (!CollisionMath::Intersection_Test(context.Box,nodebox)) {
		return;
	}
	
	/*
	** If this is a leaf, test its polygons, otherwise recurse into the children
	*/
	if (node->Is_Leaf()) {

		int polycount = node->Get_Poly_Count();
		int poly0 = node->Get_Poly0();

		if (polycount > 0) {
			TriClass tri;
			const Vector3 * loc = Mesh->Get_Vertex_Array();
			const TriIndex * polys = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
			const Vector4 * norms = Mesh->Get_Plane_Array();
#endif
			for (int poly_counter=0; poly_counter<polycount; poly_counter++) {

				int poly_index = PolyIndices[poly0 + poly_counter];
				
				tri.V[0] = &(loc[ polys[poly_index][0] ]);
				tri.V[1] = &(loc[ polys[poly_index][1] ]);
				tri.V[2] = &(loc[ polys[poly_index][2] ]);
#if (!OPTIMIZE_PLANEEQ_RAM)
				tri.N = (Vector3*)&(norms[poly_index]);
#else
				Vector3 normal;
				tri.N = &normal;
				tri.Compute_Normal();
#endif
				if (CollisionMath::Intersection_Test(context.Box,tri)) {;
					context.APT.Add(poly_index);
				} 
			}
		}

	} else {

		Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Front_Child()]),context);
		Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Back_Child()]),context);
	}
}


/***********************************************************************************************
 * AABTreeClass::Generate_APT -- generate an apt from a box and viewdir                        *
 *                                                                                             *
 * Indices of the polys which intersect the box and are not backfacing to the given viewdir    *
 * will be added to the passed in apt.                                                         *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   5/10/2001  gth : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Generate_APT
(
	const OBBoxClass & box,
	const Vector3 & viewdir,
	SimpleDynVecClass<uint32> & apt
)
{
	OBBoxRayAPTContextStruct context(box,viewdir,apt);
	Generate_OBBox_APT_Recursive(&(Nodes[0]),context);
}


/***********************************************************************************************
 * AABTreeClass::Generate_OBBox_APT_Recursive -- recurse, generate the apt for a box and viewd *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   5/10/2001  gth : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Generate_OBBox_APT_Recursive(CullNodeStruct * node, OBBoxRayAPTContextStruct & context)
{
	/*
	** Test the volume against the bounding volume of this node
	** If it is outside, stop descending the tree.
	*/
	AABoxClass nodebox;
	nodebox.Init_Min_Max(node->Min,node->Max);				// NOTE: too bad we have to compute the nodebox!!!
	
	if (!CollisionMath::Intersection_Test(context.Box,nodebox)) {
		return;
	}
	
	/*
	** If this is a leaf, test its polygons, otherwise recurse into the children
	*/
	if (node->Is_Leaf()) {

		int polycount = node->Get_Poly_Count();
		int poly0 = node->Get_Poly0();

		if (polycount > 0) {
			TriClass tri;
			const Vector3 * loc = Mesh->Get_Vertex_Array();
			const TriIndex * polys = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
			const Vector4 * norms = Mesh->Get_Plane_Array();
#endif

			for (int poly_counter=0; poly_counter<polycount; poly_counter++) {

				int poly_index = PolyIndices[poly0 + poly_counter];
				
				tri.V[0] = &(loc[ polys[poly_index][0] ]);
				tri.V[1] = &(loc[ polys[poly_index][1] ]);
				tri.V[2] = &(loc[ polys[poly_index][2] ]);
#if (!OPTIMIZE_PLANEEQ_RAM)
				tri.N = (Vector3*)&(norms[poly_index]);
#else
				Vector3 normal;
				tri.N = &normal;
				tri.Compute_Normal();
#endif
				if (Vector3::Dot_Product(*tri.N,context.ViewVector) < 0.0f) {
					if (CollisionMath::Intersection_Test(context.Box,tri)) {
						context.APT.Add(poly_index);
					} 
				}
			}
		}

	} else {

		Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Front_Child()]),context);
		Generate_OBBox_APT_Recursive(&(Nodes[node->Get_Back_Child()]),context);
	}
}


/***********************************************************************************************
 * AABTreeClass::Cast_Ray_Recursive -- Internal implementation of Cast_Ray                     *
 *                                                                                             *
 * INPUT:                                                                                      *
 * raytest - contains all of the ray test information                                          *
 * node - current cull node being processed                                                    *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/19/98    GTH : Created.                                                                 *
 *=============================================================================================*/
bool AABTreeClass::Cast_Ray_Recursive(CullNodeStruct * node,RayCollisionTestClass & raytest)
{
	/*
	** Cull the collision test against the bounding volume of this node
	** If it is culled, stop descending the tree.
	*/
	if (raytest.Cull(node->Min,node->Max)) {
		return false;
	}
	
	bool res = false;
	if (node->Is_Leaf()) {
	
		return Cast_Ray_To_Polys(node,raytest);
	
	} else {

		res = res | Cast_Ray_Recursive(&(Nodes[node->Get_Front_Child()]),raytest);
		res = res | Cast_Ray_Recursive(&(Nodes[node->Get_Back_Child()]),raytest);

	}
	
	return res;
}


/***********************************************************************************************
 * AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive -- Internal implementation      *
 *                                                                                             *
 * INPUT:                                                                                      *
 * node - current cull node being processed                                                    *
 * start_point - starting point                                                                *
 * axis_r - the axis along which the ray is projected                                          *
 * axis_1, axis_2 - the other two axes                                                         *
 * direction - 0 means the ray goes toward the negative axis, 1 means positive.                *
 * flags - reference bitfield for result flags (ray hit edge, start point embedded in tri, etc)*
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   8/30/00    NH : Created.                                                                  *
 *=============================================================================================*/
int AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(CullNodeStruct * node,
	const Vector3 & start_point, int axis_r, int axis_1, int axis_2, int direction,
	unsigned char & flags)
{
	/*
	** Cull the ray against the bounding volume of this node
	** If it is culled, stop descending the tree.
	** We do two main tests: a 2D test against axis1 and axis2 to see if the starting point (and
	** hence the ray) falls within the 2D projection of the bbox, and a 1D test to see if the ray
	** is completely above or below the bbox. The second test checks (start > max) or (start < min)
	** depending on the direction of the ray - we do this in a branchless fashion by turning
	** (start < min) into (-start > -min). Then we can use tables to perform the correct check.
	*/
	static const float sign[2] = { -1.0f, 1.0f };
	float bounds[2], start[2];
	bounds[0] = -node->Min[axis_r];
	bounds[1] = node->Max[axis_r];
	start[0] = -start_point[axis_r];
	start[1] = start_point[axis_r];
	if (	start_point[axis_1] < node->Min[axis_1] || start_point[axis_2] < node->Min[axis_2] ||
			start_point[axis_1] > node->Max[axis_1] || start_point[axis_2] > node->Max[axis_2] ||
			start[direction] > bounds[direction] ) {
		return 0;
	}

	int count = 0;
	if (node->Is_Leaf()) {
	
		return Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys(node, start_point, axis_r, axis_1,
			axis_2, direction, flags);
	
	} else {

		count += Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(&(Nodes[node->Get_Front_Child()]),
			start_point, axis_r, axis_1, axis_2, direction, flags);
		count += Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(&(Nodes[node->Get_Back_Child()]),
			start_point, axis_r, axis_1, axis_2, direction, flags);

	}
	
	return count;
}


/***********************************************************************************************
 * AABTreeClass::Cast_AABox_Recursive -- internal implementation of Cast_AABox                 *
 *                                                                                             *
 * INPUT:                                                                                      *
 * boxtest - contains description of the collision operation to be performed                   *
 * node - current cull node being processed                                                    *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/19/98    GTH : Created.                                                                 *
 *=============================================================================================*/
bool AABTreeClass::Cast_AABox_Recursive(CullNodeStruct * node,AABoxCollisionTestClass & boxtest)
{
	/*
	** First, check the bounding box of the move against the bounding box
	** of this tree, if they don't intersect, bail out
	*/
	if (boxtest.Cull(node->Min,node->Max)) {
		return false;
	}

	bool res = false;
	if (node->Is_Leaf()) {

		return Cast_AABox_To_Polys(node,boxtest);

	} else {

		res = res | Cast_AABox_Recursive(&(Nodes[node->Get_Front_Child()]),boxtest);
		res = res | Cast_AABox_Recursive(&(Nodes[node->Get_Back_Child()]),boxtest);

	}
	
	return res;
}


/***********************************************************************************************
 * AABTreeClass::Cast_OBBox_Recursive -- Internal implementation of Cast_OBBox                 *
 *                                                                                             *
 * INPUT:                                                                                      *
 * boxtest - contains description of the collision test to be performed                        *
 * node - current cull node being processed                                                    *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/19/98    GTH : Created.                                                                 *
 *=============================================================================================*/
bool AABTreeClass::Cast_OBBox_Recursive(CullNodeStruct * node,OBBoxCollisionTestClass & boxtest)
{
	/*
	** First, check the bounding box of the move against the bounding box
	** of this tree, if they don't intersect, bail out
	*/
	if (boxtest.Cull(node->Min,node->Max)) {
		return false;
	}

	bool res = false;
	if (node->Is_Leaf()) {

		return Cast_OBBox_To_Polys(node,boxtest);
	
	} else {

		res = res | Cast_OBBox_Recursive(&(Nodes[node->Get_Front_Child()]),boxtest);
		res = res | Cast_OBBox_Recursive(&(Nodes[node->Get_Back_Child()]),boxtest);

	}

	return res;
}


/***********************************************************************************************
 * AABTreeClass::Intersect_OBBox_Recursive -- internal implementation of Intersect_OBBox       *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   1/20/00    gth : Created.                                                                 *
 *=============================================================================================*/
bool AABTreeClass::Intersect_OBBox_Recursive(AABTreeClass::CullNodeStruct * node,OBBoxIntersectionTestClass & test)
{
	/*
	** Cull the collision test against the bounding volume of this node
	** If it is culled, stop descending the tree.
	*/
	if (test.Cull(node->Min,node->Max)) {
		return false;
	}

	bool res = false;
	if (node->Is_Leaf()) {

		return Intersect_OBBox_With_Polys(node,test);
		
	} else {

		res = res | Intersect_OBBox_Recursive(&(Nodes[node->Get_Front_Child()]),test);
		res = res | Intersect_OBBox_Recursive(&(Nodes[node->Get_Back_Child()]),test);
	}

	return res;
}


/***********************************************************************************************
 * AABTreeClass::Cast_Ray_To_Polys -- cast the ray to polys in the given node                  *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/19/98    GTH : Created.                                                                 *
 *=============================================================================================*/
bool AABTreeClass::Cast_Ray_To_Polys(CullNodeStruct * node,RayCollisionTestClass & raytest)
{
	if (node->Get_Poly_Count() > 0) {
		/*
		** Simply loop through the polys in this node, checking each for collision
		*/
		TriClass tri;

		const Vector3 * loc = Mesh->Get_Vertex_Array();
		const TriIndex * polyverts = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
		const Vector4 * norms = Mesh->Get_Plane_Array();
#endif

		int polyhit = -1;
		int poly0 = node->Get_Poly0();
		int polycount = node->Get_Poly_Count();

		for (int poly_counter=0; poly_counter<polycount; poly_counter++) {

			int poly_index = PolyIndices[poly0 + poly_counter];

			tri.V[0] = &(loc[ polyverts[poly_index][0] ]);
			tri.V[1] = &(loc[ polyverts[poly_index][1] ]);
			tri.V[2] = &(loc[ polyverts[poly_index][2] ]);
#if (!OPTIMIZE_PLANEEQ_RAM)
			tri.N = (Vector3*)&(norms[poly_index]);
#else
			Vector3 normal;
			tri.N = &normal;
			tri.Compute_Normal();
#endif
			if (CollisionMath::Collide(raytest.Ray,tri,raytest.Result)) {;
				polyhit = poly_index;
			}

			if (raytest.Result->StartBad) {
				return true;
			}
		}
		if (polyhit != -1) {
			raytest.Result->SurfaceType = Mesh->Get_Poly_Surface_Type (polyhit);
			return true;
		}
	}
	return false;
}


/***********************************************************************************************
 * AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys -- cast ray to polys in the node *
 *                                                                                             *
 * INPUT:                                                                                      *
 * node - current cull node being processed                                                    *
 * start_point - starting point                                                                *
 * axis_r - the axis along which the ray is projected                                          *
 * axis_1, axis_2 - the other two axes                                                         *
 * direction - 0 means the ray goes toward the negative axis, 1 means positive.                *
 * flags - reference bitfield for result flags (ray hit edge, start point embedded in tri, etc)*
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   8/30/00    NH : Created.                                                                  *
 *=============================================================================================*/
int AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray_To_Polys(CullNodeStruct * node,
	const Vector3 & start_point, int axis_r, int axis_1, int axis_2, int direction,
	unsigned char & flags)
{
	int count = 0;

	if (node->Get_Poly_Count() > 0) {

		/*
		** Simply loop through the polys in this node, checking each for collision
		*/

		const Vector3 * loc = Mesh->Get_Vertex_Array();
		const TriIndex * polyverts = Mesh->Get_Polygon_Array();
		const Vector4 * plane = Mesh->Get_Plane_Array();
		int poly0 = node->Get_Poly0();
		int polycount = node->Get_Poly_Count();
		
		for (int poly_counter=0; poly_counter < polycount; poly_counter++) {

			int poly_index = PolyIndices[poly0 + poly_counter];

			const Vector3 &v0 = loc[ polyverts[poly_index][0] ];
			const Vector3 &v1 = loc[ polyverts[poly_index][1] ];
			const Vector3 &v2 = loc[ polyverts[poly_index][2] ];
			const Vector4 &tri_plane = plane[poly_index];

			// Since (int)true is defined as 1, and (int)false as 0:
			count += (unsigned int)Cast_Semi_Infinite_Axis_Aligned_Ray_To_Triangle(v0,	v1, v2,
				tri_plane, start_point, axis_r, axis_1, axis_2, direction, flags);
		}
	}

	return count;
}


/***********************************************************************************************
 * AABTreeClass::Cast_AABox_To_Polys -- cast aabox to polys in the given node                  *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/19/98    GTH : Created.                                                                 *
 *=============================================================================================*/
bool AABTreeClass::Cast_AABox_To_Polys(CullNodeStruct * node,AABoxCollisionTestClass & boxtest)
{
	if (node->Get_Poly_Count() > 0) {
		/*
		** Simply loop through the polys in this node, checking each for collision
		*/	  
		TriClass tri;

		const Vector3 * loc = Mesh->Get_Vertex_Array();
		const TriIndex * polyverts = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
		const Vector4 * norms = Mesh->Get_Plane_Array();
#endif

		int polyhit = -1;
		int poly0 = node->Get_Poly0();
		int polycount = node->Get_Poly_Count();

		for (int poly_counter=0; poly_counter<polycount; poly_counter++) {

			int poly_index = PolyIndices[poly0 + poly_counter];

			tri.V[0] = &(loc[ polyverts[poly_index][0] ]);
			tri.V[1] = &(loc[ polyverts[poly_index][1] ]);
			tri.V[2] = &(loc[ polyverts[poly_index][2] ]);
#if (!OPTIMIZE_PLANEEQ_RAM)
			tri.N = (Vector3*)&(norms[poly_index]);
#else
			Vector3 normal;
			tri.N = &normal;
			tri.Compute_Normal();
#endif
			if (CollisionMath::Collide(boxtest.Box,boxtest.Move,tri,boxtest.Result)) {
				polyhit = poly_index;
			}

			if (boxtest.Result->StartBad) {
				return true;
			}
		}
		if (polyhit != -1) {
			boxtest.Result->SurfaceType = Mesh->Get_Poly_Surface_Type (polyhit);
			return true;
		}
	}
	return false;
}


/***********************************************************************************************
 * AABTreeClass::Cast_OBBox_To_Polys -- cast obbox to polys in the given node                  *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/19/98    GTH : Created.                                                                 *
 *=============================================================================================*/
bool AABTreeClass::Cast_OBBox_To_Polys(CullNodeStruct * node,OBBoxCollisionTestClass & boxtest)
{
	int polycount = node->Get_Poly_Count();
	int poly0 = node->Get_Poly0();

	if (polycount > 0) {
		/*
		** Simply loop through the polys in this node, checking each for collision
		*/	  
		TriClass tri;

		const Vector3 * loc = Mesh->Get_Vertex_Array();
		const TriIndex * polyverts = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
		const Vector4 * norms = Mesh->Get_Plane_Array();
#endif

		int polyhit = -1;

		for (int poly_counter=0; poly_counter<polycount; poly_counter++) {

			int poly_index = PolyIndices[poly0 + poly_counter];

			tri.V[0] = &(loc[ polyverts[poly_index][0] ]);
			tri.V[1] = &(loc[ polyverts[poly_index][1] ]);
			tri.V[2] = &(loc[ polyverts[poly_index][2] ]);
#if (!OPTIMIZE_PLANEEQ_RAM)
			tri.N = (Vector3*)&(norms[poly_index]);
#else
			Vector3 normal;
			tri.N = &normal;
			tri.Compute_Normal();
#endif

			if (CollisionMath::Collide(boxtest.Box,boxtest.Move,tri,Vector3(0,0,0),boxtest.Result)) {
				polyhit = poly_index;
			}

			if (boxtest.Result->StartBad) {
				return true;
			}
		}
		if (polyhit != -1) {
			boxtest.Result->SurfaceType = Mesh->Get_Poly_Surface_Type (polyhit);
			return true;
		}
	}
	return false;

}


/***********************************************************************************************
 * AABTreeClass::Intersect_OBBox_With_Polys -- Test polys for intersection                     *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   1/20/00    gth : Created.                                                                 *
 *=============================================================================================*/
bool AABTreeClass::Intersect_OBBox_With_Polys
(
	CullNodeStruct * node,
	OBBoxIntersectionTestClass & test
)
{
	int poly0 = node->Get_Poly0();
	int polycount = node->Get_Poly_Count();

	if (polycount > 0) {
		/*
		** Simply loop through the polys in this node, checking each for collision
		*/	  
		TriClass tri;

		const Vector3 * loc = Mesh->Get_Vertex_Array();
		const TriIndex * polyverts = Mesh->Get_Polygon_Array();
#if (!OPTIMIZE_PLANEEQ_RAM)
		const Vector4 * norms = Mesh->Get_Plane_Array();
#endif

		for (int poly_counter=0; poly_counter<polycount; poly_counter++) {

			int poly_index = PolyIndices[poly0 + poly_counter];

			tri.V[0] = &(loc[ polyverts[poly_index][0] ]);
			tri.V[1] = &(loc[ polyverts[poly_index][1] ]);
			tri.V[2] = &(loc[ polyverts[poly_index][2] ]);
#if (!OPTIMIZE_PLANEEQ_RAM)
			tri.N = (Vector3*)&(norms[poly_index]);
#else
			Vector3 normal;
			tri.N = &normal;
			tri.Compute_Normal();
#endif

			if (CollisionMath::Intersection_Test(test.Box,tri)) {
				return true;
			}
		}
	}
	return false;
}


/***********************************************************************************************
 * AABTreeClass::Update_Bounding_Boxes_Recursive -- recompute the bounding boxes               *
 *                                                                                             *
 * Typically this function will be used when you have modified the mesh slightly and you need  *
 * to update the bounding boxes but you want to keep the structure of the tree.                *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/22/99    GTH : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Update_Bounding_Boxes_Recursive(CullNodeStruct * node)
{
	node->Min.Set(100000.0f,100000.0f,100000.0f);
	node->Max.Set(-100000.0f,-100000.0f,-100000.0f);

	/*
	** Recurse to the children first
	*/
	if (node->Is_Leaf() == false) {

		Update_Bounding_Boxes_Recursive(&(Nodes[node->Get_Front_Child()]));
		Update_Bounding_Boxes_Recursive(&(Nodes[node->Get_Back_Child()]));

		/*
		** Bound our children
		*/
		int front = node->Get_Front_Child();
		int back = node->Get_Back_Child();

		if (Nodes[front].Min.X < node->Min.X) node->Min.X = Nodes[front].Min.X;
		if (Nodes[front].Max.X > node->Max.X) node->Max.X = Nodes[front].Max.X;

		if (Nodes[front].Min.Y < node->Min.Y) node->Min.Y = Nodes[front].Min.Y;
		if (Nodes[front].Max.Y > node->Max.Y) node->Max.Y = Nodes[front].Max.Y;
		
		if (Nodes[front].Min.Z < node->Min.Z) node->Min.Z = Nodes[front].Min.Z;
		if (Nodes[front].Max.Z > node->Max.Z) node->Max.Z = Nodes[front].Max.Z;

		if (Nodes[back].Min.X < node->Min.X) node->Min.X = Nodes[back].Min.X;
		if (Nodes[back].Max.X > node->Max.X) node->Max.X = Nodes[back].Max.X;

		if (Nodes[back].Min.Y < node->Min.Y) node->Min.Y = Nodes[back].Min.Y;
		if (Nodes[back].Max.Y > node->Max.Y) node->Max.Y = Nodes[back].Max.Y;
		
		if (Nodes[back].Min.Z < node->Min.Z) node->Min.Z = Nodes[back].Min.Z;
		if (Nodes[back].Max.Z > node->Max.Z) node->Max.Z = Nodes[back].Max.Z;

	} else {
		
		/*
		** Bound our polygons
		*/
		int poly0 = node->Get_Poly0();
		int polycount = node->Get_Poly_Count();

		for (int poly_index = 0; poly_index < polycount; poly_index++) {
			int pi = PolyIndices[poly0 + poly_index];
			Update_Min_Max(pi,node->Min,node->Max );
		}

	}

	WWASSERT(node->Min.X != 100000.0f);
	WWASSERT(node->Min.Y != 100000.0f);
	WWASSERT(node->Min.Z != 100000.0f);
	WWASSERT(node->Max.X != -100000.0f);
	WWASSERT(node->Max.Y != -100000.0f);
	WWASSERT(node->Max.Z != -100000.0f);
}


/***********************************************************************************************
 * AABTreeClass::Update_Min_Max -- updates min and max given a polygon index                   *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   6/22/99    GTH : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Update_Min_Max(int poly_index,Vector3 & min,Vector3 & max)
{
	for (int vert_index = 0; vert_index < 3; vert_index++) {

		const TriIndex * polyverts = Mesh->Get_Polygon_Array() + poly_index;
		const Vector3 * point = Mesh->Get_Vertex_Array() + (*polyverts)[vert_index];

		if (point->X  < min.X) min.X = point->X;
		if (point->Y  < min.Y) min.Y = point->Y;
		if (point->Z  < min.Z) min.Z = point->Z;

		if (point->X  > max.X) max.X = point->X;
		if (point->Y  > max.Y) max.Y = point->Y;
		if (point->Z  > max.Z) max.Z = point->Z;
	}
}


/***********************************************************************************************
 * AABTreeClass::Load_W3D -- Load a W3D description of an AABTree                              *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   5/22/2000  gth : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Load_W3D(ChunkLoadClass & cload)
{
	Reset();
	
	W3dMeshAABTreeHeader header;
	cload.Open_Chunk();
	WWASSERT(cload.Cur_Chunk_ID() == W3D_CHUNK_AABTREE_HEADER);
	cload.Read(&header,sizeof(header));
	cload.Close_Chunk();

	NodeCount = header.NodeCount;
	PolyCount = header.PolyCount;
	Nodes = new CullNodeStruct[NodeCount];
	PolyIndices = new uint32[PolyCount];

	while (cload.Open_Chunk()) {
		switch (cload.Cur_Chunk_ID()) 
		{
		case W3D_CHUNK_AABTREE_POLYINDICES:
			Read_Poly_Indices(cload);
			break;

		case W3D_CHUNK_AABTREE_NODES:
			Read_Nodes(cload);
			break;
		}
		cload.Close_Chunk();
	}
}


/***********************************************************************************************
 * AABTreeClass::Read_Poly_Indices -- load the polygon index array                             *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   5/22/2000  gth : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Read_Poly_Indices(ChunkLoadClass & cload)
{
	cload.Read(PolyIndices,sizeof(uint32) * PolyCount);
}


/***********************************************************************************************
 * AABTreeClass::Read_Nodes -- Load the node array                                             *
 *                                                                                             *
 * INPUT:                                                                                      *
 *                                                                                             *
 * OUTPUT:                                                                                     *
 *                                                                                             *
 * WARNINGS:                                                                                   *
 *                                                                                             *
 * HISTORY:                                                                                    *
 *   5/22/2000  gth : Created.                                                                 *
 *=============================================================================================*/
void AABTreeClass::Read_Nodes(ChunkLoadClass & cload)
{
	W3dMeshAABTreeNode w3dnode;

	for (int i=0; i<NodeCount; i++) {
		cload.Read(&w3dnode,sizeof(w3dnode));

		Nodes[i].Min.X = w3dnode.Min.X;
		Nodes[i].Min.Y = w3dnode.Min.Y;
		Nodes[i].Min.Z = w3dnode.Min.Z;

		Nodes[i].Max.X = w3dnode.Max.X;
		Nodes[i].Max.Y = w3dnode.Max.Y;
		Nodes[i].Max.Z = w3dnode.Max.Z;

		Nodes[i].FrontOrPoly0 = w3dnode.FrontOrPoly0;
		Nodes[i].BackOrPolyCount = w3dnode.BackOrPolyCount;
	}
}