aabtree.h

Go to the documentation of this file.

/*
**  Command & Conquer Generals Zero Hour(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                              $*
 *                                                                                             *
 *                   Org Author:: Greg Hjelstrom                                               *
 *                                                                                             *
 *                       Author:: Kenny Mitchell                                               *
 *                                                                                             *
 *                     $Modtime:: 6/26/02 2:58p                                               $*
 *                                                                                             *
 *                    $Revision:: 4                                                           $*
 *                                                                                             *
 *---------------------------------------------------------------------------------------------*
 * 06/26/02 KM Integrating shader system
 * 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 W3DMPO, public RefCountClass
{
    W3DMPO_GLUE(AABTreeClass)
public:
 
    AABTreeClass(void);
    AABTreeClass(AABTreeBuilderClass * builder);
    AABTreeClass(const AABTreeClass & that);
    ~AABTreeClass(void);
 
    void                        Load_W3D(ChunkLoadClass & cload);
 
    // Uniformly scale the AABTree
    void                        Scale(float scale);
 
    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);
 
    void                        Set_Mesh(MeshGeometryClass * mesh);
 
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                        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;
    };

    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