/* ** 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 . */ /*********************************************************************************************** *** 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 #include 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 & apt); void Generate_APT(const OBBoxClass & box,const Vector3 & viewdir,SimpleDynVecClass & 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 & apt) : Box(box), APT(apt) { } OBBoxClass Box; SimpleDynVecClass & 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 & apt) : Box(box), ViewVector(viewdir), APT(apt) { } OBBoxClass Box; Vector3 ViewVector; SimpleDynVecClass & 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