OPCODE/OPC_AABBTree.h

   1 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
   2 /*
   3  *      OPCODE - Optimized Collision Detection
   4  *      Copyright (C) 2001 Pierre Terdiman
   5  *      Homepage: http://www.codercorner.com/Opcode.htm
   6  */
   7 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
   8
   9 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  10 /**
  11  *      Contains code for a versatile AABB tree.
  12  *      \file           OPC_AABBTree.h
  13  *      \author         Pierre Terdiman
  14  *      \date           March, 20, 2001
  15  */
  16 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  17
  18 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  19 // Include Guard
  20 #ifndef __OPC_AABBTREE_H__
  21 #define __OPC_AABBTREE_H__
  22
  23 #ifdef OPC_NO_NEG_VANILLA_TREE
  24         //! TO BE DOCUMENTED
  25         #define IMPLEMENT_TREE(base_class, volume)                                                                                                                                                      \
  26                 public:                                                                                                                                                                                                                 \
  27                 /* Constructor / Destructor */                                                                                                                                                                  \
  28                                                                         base_class();                                                                                                                                           \
  29                                                                         ~base_class();                                                                                                                                          \
  30                 /* Data access */                                                                                                                                                                                               \
  31                 inline_ const volume*           Get##volume()   const   { return &mBV;                                                  }                                       \
  32                 /* Clear the last bit */                                                                                                                                                                                \
  33                 inline_ const base_class*       GetPos()                const   { return (const base_class*)(mPos&~1);  }                                       \
  34                 inline_ const base_class*       GetNeg()                const   { const base_class* P = GetPos(); return P ? P+1 : null;}       \
  35                                                                                                                                                                                                                                                 \
  36                 /* We don't need to test both nodes since we can't have one without the other   */                                                              \
  37                 inline_ bool                            IsLeaf()                const   { return !GetPos();                                             }                                       \
  38                                                                                                                                                                                                                                                 \
  39                 /* Stats */                                                                                                                                                                                                             \
  40                 inline_ udword                          GetNodeSize()   const   { return SIZEOFOBJECT;                                  }                                       \
  41                 protected:                                                                                                                                                                                                              \
  42                 /* Tree-independent data */                                                                                                                                                                             \
  43                 /* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/                                \
  44                 /* Whatever happens we need the two children and the enclosing volume.*/                                                                                \
  45                                 volume                          mBV;            /* Global bounding-volume enclosing all the node-related primitives */  \
  46                                 size_t                          mPos;           /* "Positive" & "Negative" children */
  47 #else
  48         //! TO BE DOCUMENTED
  49         #define IMPLEMENT_TREE(base_class, volume)                                                                                                                                                      \
  50                 public:                                                                                                                                                                                                                 \
  51                 /* Constructor / Destructor */                                                                                                                                                                  \
  52                                                                         base_class();                                                                                                                                           \
  53                                                                         ~base_class();                                                                                                                                          \
  54                 /* Data access */                                                                                                                                                                                               \
  55                 inline_ const volume*           Get##volume()   const   { return &mBV;                                                  }                                       \
  56                 /* Clear the last bit */                                                                                                                                                                                \
  57                 inline_ const base_class*       GetPos()                const   { return (const base_class*)(mPos&~1);  }                                       \
  58                 inline_ const base_class*       GetNeg()                const   { return (const base_class*)(mNeg&~1);  }                                       \
  59                                                                                                                                                                                                                                                 \
  60 /*              inline_ bool                            IsLeaf()                const   { return (!GetPos() && !GetNeg());      }       */                                      \
  61                 /* We don't need to test both nodes since we can't have one without the other   */                                                              \
  62                 inline_ bool                            IsLeaf()                const   { return !GetPos();                                             }                                       \
  63                                                                                                                                                                                                                                                 \
  64                 /* Stats */                                                                                                                                                                                                             \
  65                 inline_ udword                          GetNodeSize()   const   { return SIZEOFOBJECT;                                  }                                       \
  66                 protected:                                                                                                                                                                                                              \
  67                 /* Tree-independent data */                                                                                                                                                                             \
  68                 /* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/                                \
  69                 /* Whatever happens we need the two children and the enclosing volume.*/                                                                                \
  70                                 volume                          mBV;            /* Global bounding-volume enclosing all the node-related primitives */  \
  71                                 size_t                          mPos;           /* "Positive" child */                                                                                                  \
  72                                 size_t                          mNeg;           /* "Negative" child */
  73 #endif
  74
  75         typedef         void                            (*CullingCallback)              (udword nb_primitives, udword* node_primitives, BOOL need_clipping, void* user_data);
  76
  77         class OPCODE_API AABBTreeNode
  78         {
  79                                                                         IMPLEMENT_TREE(AABBTreeNode, AABB)
  80                 public:
  81                 // Data access
  82                 inline_ const dTriIndex*                GetPrimitives()         const   { return mNodePrimitives;       }
  83                 inline_ udword                          GetNbPrimitives()       const   { return mNbPrimitives;         }
  84
  85                 protected:
  86                 // Tree-dependent data
  87                                 dTriIndex*      mNodePrimitives;        //!< Node-related primitives (shortcut to a position in mIndices below)
  88                                 udword                          mNbPrimitives;          //!< Number of primitives for this node
  89                 // Internal methods
  90                                 udword                          Split(udword axis, AABBTreeBuilder* builder);
  91                                 bool                            Subdivide(AABBTreeBuilder* builder);
  92                                 void                            _BuildHierarchy(AABBTreeBuilder* builder);
  93                                 void                            _Refit(AABBTreeBuilder* builder);
  94         };
  95
  96         ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  97         /**
  98          *      User-callback, called for each node by the walking code.
  99          *      \param          current         [in] current node
 100          *      \param          depth           [in] current node's depth
 101          *      \param          user_data       [in] user-defined data
 102          *      \return         true to recurse through children, else false to bypass them
 103          */
 104         ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 105         typedef         bool                            (*WalkingCallback)      (const AABBTreeNode* current, udword depth, void* user_data);
 106
 107         class OPCODE_API AABBTree : public AABBTreeNode
 108         {
 109                 public:
 110                 // Constructor / Destructor
 111                                                                         AABBTree();
 112                                                                         ~AABBTree();
 113                 // Build
 114                                 bool                            Build(AABBTreeBuilder* builder);
 115                                 void                            Release();
 116
 117                 // Data access
 118                 inline_ const dTriIndex*                GetIndices()            const   { return mIndices;              }       //!< Catch the indices
 119                 inline_ udword                          GetNbNodes()            const   { return mTotalNbNodes; }       //!< Catch the number of nodes
 120
 121                 // Infos
 122                                 bool                            IsComplete()            const;
 123                 // Stats
 124                                 udword                          ComputeDepth()          const;
 125                                 udword                          GetUsedBytes()          const;
 126                                 udword                          Walk(WalkingCallback callback, void* user_data) const;
 127
 128                                 bool                            Refit(AABBTreeBuilder* builder);
 129                                 bool                            Refit2(AABBTreeBuilder* builder);
 130                 private:
 131                                 dTriIndex*                              mIndices;                       //!< Indices in the app list. Indices are reorganized during build (permutation).
 132                                 AABBTreeNode*           mPool;                          //!< Linear pool of nodes for complete trees. Null otherwise. [Opcode 1.3]
 133                 // Stats
 134                                 udword                          mTotalNbNodes;          //!< Number of nodes in the tree.
 135         };
 136
 137 #endif // __OPC_AABBTREE_H__