346 lines
13 KiB
C++
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
|