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

346 lines
13 KiB
C++

/*
** Command & Conquer Renegade(tm)
** Copyright 2025 Electronic Arts Inc.
**
** This program is free software: you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation, either version 3 of the License, or
** (at your option) any later version.
**
** This program is distributed in the hope that it will be useful,
** but WITHOUT ANY WARRANTY; without even the implied warranty of
** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
** GNU General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
/***********************************************************************************************
*** C O N F I D E N T I A L --- W E S T W O O D S T U D I O S ***
***********************************************************************************************
* *
* Project Name : WW3D *
* *
* $Archive:: /Commando/Code/ww3d2/aabtree.h $*
* *
* Author:: Greg Hjelstrom *
* *
* $Modtime:: 6/14/01 9:42a $*
* *
* $Revision:: 3 $*
* *
*---------------------------------------------------------------------------------------------*
* Functions: *
* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
#if defined(_MSC_VER)
#pragma once
#endif
#ifndef AABTREE_H
#define AABTREE_H
#include "always.h"
#include "refcount.h"
#include "simplevec.h"
#include "vector3.h"
#include "vector3i.h"
#include "aaplane.h"
#include "bittype.h"
#include "colmath.h"
#include "wwdebug.h"
#include "aabtreebuilder.h"
#include "obbox.h"
#include <tri.h>
#include <float.h>
class MeshClass;
class CameraClass;
class RayCollisionTestClass;
class AABoxCollisionTestClass;
class OBBoxCollisionTestClass;
class OBBoxIntersectionTestClass;
class ChunkLoadClass;
class ChunkSaveClass;
class MeshGeometryClass;
class OBBoxClass;
class ChunkLoadClass;
struct BoxRayAPTContextStruct;
#define AABTREE_LEAF_FLAG 0x80000000
/*
** AABTreeClass
** This class encapsulates an Axis-Aligned Bounding Box Tree for a mesh. This tree
** can be used to perform hierarchical culling for collision detection. Note that
** this class is constructed using the AABTreeBuilderClass; these two classes are
** very tightly coupled. Pretty much the only code which needs to know about the AABTreeClass
** is in MeshGeometryClass. I moved these out into a separate file just to reduce the
** size of meshmdl.cpp.
*/
class AABTreeClass : public RefCountClass
{
public:
AABTreeClass(void);
AABTreeClass(AABTreeBuilderClass * builder);
AABTreeClass(const AABTreeClass & that);
~AABTreeClass(void);
void Load_W3D(ChunkLoadClass & cload);
int Get_Node_Count(void) { return NodeCount; }
int Get_Poly_Count(void) { return PolyCount; }
int Compute_Ram_Size(void);
void Generate_APT(const OBBoxClass & box,SimpleDynVecClass<uint32> & apt);
void Generate_APT(const OBBoxClass & box,const Vector3 & viewdir,SimpleDynVecClass<uint32> & apt);
bool Cast_Ray(RayCollisionTestClass & raytest);
int Cast_Semi_Infinite_Axis_Aligned_Ray(const Vector3 & start_point,
int axis_dir, unsigned char & flags);
bool Cast_AABox(AABoxCollisionTestClass & boxtest);
bool Cast_OBBox(OBBoxCollisionTestClass & boxtest);
bool Intersect_OBBox(OBBoxIntersectionTestClass & boxtest);
private:
AABTreeClass & operator = (const AABTreeClass & that);
void Read_Poly_Indices(ChunkLoadClass & cload);
void Read_Nodes(ChunkLoadClass & cload);
void Build_Tree_Recursive(AABTreeBuilderClass::CullNodeStruct * node,int &curpolyindex);
void Reset(void);
void Set_Mesh(MeshGeometryClass * mesh);
void Update_Bounding_Boxes(void);
void Update_Min_Max(int index,Vector3 & min,Vector3 & max);
/*
** CullNodeStruct - the culling tree is built out of an array of these structures
** They contain the extents of an axis-aligned box, indices to children nodes,
** and indices into the polygon array
** (05/22/2000 gth - changed this structure to support either child nodes -or-
** a polygon array but not both at the same time. Also switched to 32bit indices
** so that the code doesn't become useless as quickly )
*/
struct CullNodeStruct
{
Vector3 Min;
Vector3 Max;
uint32 FrontOrPoly0;
uint32 BackOrPolyCount;
// accessors
inline bool Is_Leaf(void);
inline int Get_Back_Child(void); // returns index of back child (only call for non-LEAFs!!!)
inline int Get_Front_Child(void); // returns index of front child (only call for non-LEAFs!!!)
inline int Get_Poly0(void); // returns index of first polygon (only call on LEAFs)
inline int Get_Poly_Count(void); // returns polygon count (only call on LEAFs)
// initialization
inline void Set_Front_Child(uint32 index);
inline void Set_Back_Child(uint32 index);
inline void Set_Poly0(uint32 index);
inline void Set_Poly_Count(uint32 count);
};
/*
** OBBoxAPTContextStruct - this is a temporary datastructure used in building
** an APT by culling the mesh to an oriented bounding box.
*/
struct OBBoxAPTContextStruct
{
OBBoxAPTContextStruct(const OBBoxClass & box,SimpleDynVecClass<uint32> & apt) :
Box(box), APT(apt)
{ }
OBBoxClass Box;
SimpleDynVecClass<uint32> & APT;
};
/**
** OBBoxRayAPTContextStruct - temporary datastructure used in building an APT
** by culling the mesh to a oriented box and eliminating backfaces to a ray.
*/
struct OBBoxRayAPTContextStruct
{
OBBoxRayAPTContextStruct(const OBBoxClass & box,const Vector3 & viewdir,SimpleDynVecClass<uint32> & apt) :
Box(box),
ViewVector(viewdir),
APT(apt)
{ }
OBBoxClass Box;
Vector3 ViewVector;
SimpleDynVecClass<uint32> & APT;
};
void Generate_OBBox_APT_Recursive(CullNodeStruct * node,OBBoxAPTContextStruct & context);
void Generate_OBBox_APT_Recursive(CullNodeStruct * node, OBBoxRayAPTContextStruct & context);
bool Cast_Ray_Recursive(CullNodeStruct * node,RayCollisionTestClass & raytest);
int 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);
bool Cast_AABox_Recursive(CullNodeStruct * node,AABoxCollisionTestClass & boxtest);
bool Cast_OBBox_Recursive(CullNodeStruct * node,OBBoxCollisionTestClass & boxtest);
bool Intersect_OBBox_Recursive(CullNodeStruct * node,OBBoxIntersectionTestClass & boxtest);
bool Cast_Ray_To_Polys(CullNodeStruct * node,RayCollisionTestClass & raytest);
int 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);
bool Cast_AABox_To_Polys(CullNodeStruct * node,AABoxCollisionTestClass & boxtest);
bool Cast_OBBox_To_Polys(CullNodeStruct * node,OBBoxCollisionTestClass & boxtest);
bool Intersect_OBBox_With_Polys(CullNodeStruct * node,OBBoxIntersectionTestClass & boxtest);
void Update_Bounding_Boxes_Recursive(CullNodeStruct * node);
int NodeCount; // number of nodes in the tree
CullNodeStruct * Nodes; // array of nodes
int PolyCount; // number of polygons in the parent mesh (and the number of indexes in our array)
uint32 * PolyIndices; // linear array of polygon indices, nodes index into this array
MeshGeometryClass * Mesh; // pointer to the parent mesh (non-ref-counted; we are a member of this mesh)
friend class MeshClass;
friend class MeshGeometryClass;
friend class AuxMeshDataClass;
friend class AABTreeBuilderClass;
};
inline int AABTreeClass::Compute_Ram_Size(void)
{
return NodeCount * sizeof(CullNodeStruct) +
PolyCount * sizeof(int) +
sizeof(AABTreeClass);
}
inline bool AABTreeClass::Cast_Ray(RayCollisionTestClass & raytest)
{
WWASSERT(Nodes != NULL);
return Cast_Ray_Recursive(&(Nodes[0]),raytest);
}
inline int AABTreeClass::Cast_Semi_Infinite_Axis_Aligned_Ray(const Vector3 & start_point,
int axis_dir, unsigned char & flags)
{
// These tables translate between the axis_dir representation (which is an integer in which 0
// indicates a ray along the positive x axis, 1 along the negative x axis, 2 the positive y
// axis, 3 negative y axis, 4 positive z axis, 5 negative z axis) and a four-integer
// representation (axis_r is the axis number - 0, 1 or 2 - of the axis along which the ray is
// cast; axis_1 and axis_2 are the axis numbers of the other two axes; direction is 0 for
// negative and 1 for positive direction of the ray).
static const int axis_r[6] = { 0, 0, 1, 1, 2, 2 };
static const int axis_1[6] = { 1, 1, 2, 2, 0, 0 };
static const int axis_2[6] = { 2, 2, 0, 0, 1, 1 };
static const int direction[6] = { 1, 0, 1, 0, 1, 0 };
WWASSERT(Nodes != NULL);
WWASSERT(axis_dir >= 0);
WWASSERT(axis_dir < 6);
// The functions called after this point will 'or' bits into this variable, so it needs to
// be initialized here to TRI_RAYCAST_FLAG_NONE.
flags = TRI_RAYCAST_FLAG_NONE;
return Cast_Semi_Infinite_Axis_Aligned_Ray_Recursive(&(Nodes[0]), start_point,
axis_r[axis_dir], axis_1[axis_dir], axis_2[axis_dir], direction[axis_dir], flags);
}
inline bool AABTreeClass::Cast_AABox(AABoxCollisionTestClass & boxtest)
{
WWASSERT(Nodes != NULL);
return Cast_AABox_Recursive(&(Nodes[0]),boxtest);
}
inline bool AABTreeClass::Cast_OBBox(OBBoxCollisionTestClass & boxtest)
{
WWASSERT(Nodes != NULL);
return Cast_OBBox_Recursive(&(Nodes[0]),boxtest);
}
inline bool AABTreeClass::Intersect_OBBox(OBBoxIntersectionTestClass & boxtest)
{
WWASSERT(Nodes != NULL);
return Intersect_OBBox_Recursive(&(Nodes[0]),boxtest);
}
inline void AABTreeClass::Update_Bounding_Boxes(void)
{
WWASSERT(Nodes != NULL);
Update_Bounding_Boxes_Recursive(&(Nodes[0]));
}
/***********************************************************************************************
AABTreeClass::CullNodeStruct implementation
These nodes can be either leaf nodes or non-leaf nodes. If they are leaf nodes, they
will contain an index to their first polygon index and a polygon count. If they are
non-leafs they will contain indices to their front and back children. Since I'm re-using
the same variables for the child indices and the polygon indices, you have to call
the Is_Leaf function then only call the appropriate functions. The flag indicating whether
this node is a leaf is stored in the MSB of the FrontOrPoly0 variable. It will always
be stripped off by these accessor functions
***********************************************************************************************/
inline bool AABTreeClass::CullNodeStruct::Is_Leaf(void)
{
return ((FrontOrPoly0 & AABTREE_LEAF_FLAG) != 0);
}
inline int AABTreeClass::CullNodeStruct::Get_Front_Child(void)
{
WWASSERT(!Is_Leaf());
return FrontOrPoly0; // we shouldn't be calling this on a leaf and the leaf bit should be zero...
}
inline int AABTreeClass::CullNodeStruct::Get_Back_Child(void)
{
WWASSERT(!Is_Leaf());
return BackOrPolyCount;
}
inline int AABTreeClass::CullNodeStruct::Get_Poly0(void)
{
WWASSERT(Is_Leaf());
return (FrontOrPoly0 & ~AABTREE_LEAF_FLAG);
}
inline int AABTreeClass::CullNodeStruct::Get_Poly_Count(void)
{
WWASSERT(Is_Leaf());
return BackOrPolyCount;
}
inline void AABTreeClass::CullNodeStruct::Set_Front_Child(uint32 index)
{
WWASSERT(index < 0x7FFFFFFF);
FrontOrPoly0 = index;
}
inline void AABTreeClass::CullNodeStruct::Set_Back_Child(uint32 index)
{
WWASSERT(index < 0x7FFFFFFF);
BackOrPolyCount = index;
}
inline void AABTreeClass::CullNodeStruct::Set_Poly0(uint32 index)
{
WWASSERT(index < 0x7FFFFFFF);
FrontOrPoly0 = (index | AABTREE_LEAF_FLAG);
}
inline void AABTreeClass::CullNodeStruct::Set_Poly_Count(uint32 count)
{
WWASSERT(count < 0x7FFFFFFF);
BackOrPolyCount = count;
}
#endif