Extras/CDTestFramework/Opcode/OPC_OptimizedTree.h

   1 /*
   2  *      OPCODE - Optimized Collision Detection
   3  * http://www.codercorner.com/Opcode.htm
   4  *
   5  * Copyright (c) 2001-2008 Pierre Terdiman,  pierre@codercorner.com
   6
   7 This software is provided 'as-is', without any express or implied warranty.
   8 In no event will the authors be held liable for any damages arising from the use of this software.
   9 Permission is granted to anyone to use this software for any purpose,
  10 including commercial applications, and to alter it and redistribute it freely,
  11 subject to the following restrictions:
  12
  13 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required.
  14 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
  15 3. This notice may not be removed or altered from any source distribution.
  16 */
  17
  18 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  19 /**
  20  *      Contains code for optimized trees.
  21  *      \file           OPC_OptimizedTree.h
  22  *      \author         Pierre Terdiman
  23  *      \date           March, 20, 2001
  24  */
  25 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  26
  27 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  28 // Include Guard
  29 #ifndef __OPC_OPTIMIZEDTREE_H__
  30 #define __OPC_OPTIMIZEDTREE_H__
  31
  32         //! Common interface for a node of an implicit tree
  33         #define IMPLEMENT_IMPLICIT_NODE(base_class, volume)                                                                                                             \
  34                 public:                                                                                                                                                                                         \
  35                 /* Constructor / Destructor */                                                                                                                                          \
  36                 inline_                                                         base_class() : mData(0) {}                                                                              \
  37                 inline_                                                         ~base_class()                   {}                                                                              \
  38                 /* Leaf test */                                                                                                                                                                         \
  39                 inline_                 BOOL                            IsLeaf()                const   { return mData&1;                                       }       \
  40                 /* Data access */                                                                                                                                                                       \
  41                 inline_                 const base_class*       GetPos()                const   { return (base_class*)mData;            }       \
  42                 inline_                 const base_class*       GetNeg()                const   { return ((base_class*)mData)+1;        }       \
  43                 inline_                 udword                          GetPrimitive()  const   { return (mData>>1);                            }       \
  44                 /* Stats */                                                                                                                                                                                     \
  45                 inline_                 udword                          GetNodeSize()   const   { return SIZEOFOBJECT;                          }       \
  46                                                                                                                                                                                                                         \
  47                                                 volume                          mAABB;                                                                                                                  \
  48                                                 udword                          mData;
  49
  50         //! Common interface for a node of a no-leaf tree
  51         #define IMPLEMENT_NOLEAF_NODE(base_class, volume)                                                                                                               \
  52                 public:                                                                                                                                                                                         \
  53                 /* Constructor / Destructor */                                                                                                                                          \
  54                 inline_                                                         base_class() : mPosData(0), mNegData(0) {}                                              \
  55                 inline_                                                         ~base_class()                                                   {}                                              \
  56                 /* Leaf tests */                                                                                                                                                                        \
  57                 inline_                 BOOL                            HasPosLeaf()            const   { return mPosData&1;                    }       \
  58                 inline_                 BOOL                            HasNegLeaf()            const   { return mNegData&1;                    }       \
  59                 /* Data access */                                                                                                                                                                       \
  60                 inline_                 const base_class*       GetPos()                        const   { return (base_class*)mPosData; }       \
  61                 inline_                 const base_class*       GetNeg()                        const   { return (base_class*)mNegData; }       \
  62                 inline_                 udword                          GetPosPrimitive()       const   { return (mPosData>>1);                 }       \
  63                 inline_                 udword                          GetNegPrimitive()       const   { return (mNegData>>1);                 }       \
  64                 /* Stats */                                                                                                                                                                                     \
  65                 inline_                 udword                          GetNodeSize()           const   { return SIZEOFOBJECT;                  }       \
  66                                                                                                                                                                                                                         \
  67                                                 volume                          mAABB;                                                                                                                  \
  68                                                 udword                          mPosData;                                                                                                               \
  69                                                 udword                          mNegData;
  70
  71         class OPCODE_API AABBCollisionNode
  72         {
  73                 IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB)
  74
  75                 inline_                 float                           GetVolume()             const   { return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z;        }
  76                 inline_                 float                           GetSize()               const   { return mAABB.mExtents.SquareMagnitude();      }
  77                 inline_                 udword                          GetRadius()             const
  78                                                                                         {
  79                                                                                                 udword* Bits = (udword*)&mAABB.mExtents.x;
  80                                                                                                 udword Max = Bits[0];
  81                                                                                                 if(Bits[1]>Max) Max = Bits[1];
  82                                                                                                 if(Bits[2]>Max) Max = Bits[2];
  83                                                                                                 return Max;
  84                                                                                         }
  85
  86                 // NB: using the square-magnitude or the true volume of the box, seems to yield better results
  87                 // (assuming UNC-like informed traversal methods). I borrowed this idea from PQP. The usual "size"
  88                 // otherwise, is the largest box extent. In SOLID that extent is computed on-the-fly each time it's
  89                 // needed (the best approach IMHO). In RAPID the rotation matrix is permuted so that Extent[0] is
  90                 // always the greatest, which saves looking for it at runtime. On the other hand, it yields matrices
  91                 // whose determinant is not 1, i.e. you can't encode them anymore as unit quaternions. Not a very
  92                 // good strategy.
  93         };
  94
  95         class OPCODE_API AABBQuantizedNode
  96         {
  97                 IMPLEMENT_IMPLICIT_NODE(AABBQuantizedNode, QuantizedAABB)
  98
  99                 inline_                 uword                           GetSize()               const
 100                                                                                         {
 101                                                                                                 const uword* Bits = mAABB.mExtents;
 102                                                                                                 uword Max = Bits[0];
 103                                                                                                 if(Bits[1]>Max) Max = Bits[1];
 104                                                                                                 if(Bits[2]>Max) Max = Bits[2];
 105                                                                                                 return Max;
 106                                                                                         }
 107                 // NB: for quantized nodes I don't feel like computing a square-magnitude with integers all
 108                 // over the place.......!
 109         };
 110
 111         class OPCODE_API AABBNoLeafNode
 112         {
 113                 IMPLEMENT_NOLEAF_NODE(AABBNoLeafNode, CollisionAABB)
 114         };
 115
 116         class OPCODE_API AABBQuantizedNoLeafNode
 117         {
 118                 IMPLEMENT_NOLEAF_NODE(AABBQuantizedNoLeafNode, QuantizedAABB)
 119         };
 120
 121         //! Common interface for a collision tree
 122         #define IMPLEMENT_COLLISION_TREE(base_class, node)                                                                                                                              \
 123                 public:                                                                                                                                                                                                         \
 124                 /* Constructor / Destructor */                                                                                                                                                          \
 125                                                                                                         base_class();                                                                                                   \
 126                 virtual                                                                         ~base_class();                                                                                                  \
 127                 /* Builds from a standard tree */                                                                                                                                                       \
 128                 override(AABBOptimizedTree)     bool                    Build(AABBTree* tree);                                                                                  \
 129                 /* Refits the tree */                                                                                                                                                                           \
 130                 override(AABBOptimizedTree)     bool                    Refit(const MeshInterface* mesh_interface);                                             \
 131                 /* Walks the tree */                                                                                                                                                                            \
 132                 override(AABBOptimizedTree)     bool                    Walk(GenericWalkingCallback callback, void* user_data) const;   \
 133                 /* Data access */                                                                                                                                                                                       \
 134                 inline_                                         const node*             GetNodes()              const   { return mNodes;                                        }       \
 135                 /* Stats */                                                                                                                                                                                                     \
 136                 override(AABBOptimizedTree)     udword                  GetUsedBytes()  const   { return mNbNodes*sizeof(node);         }       \
 137                 private:                                                                                                                                                                                                        \
 138                                                                         node*                   mNodes;
 139
 140         typedef         bool                            (*GenericWalkingCallback)       (const void* current, void* user_data);
 141
 142         class OPCODE_API AABBOptimizedTree
 143         {
 144                 public:
 145                 // Constructor / Destructor
 146                                                                                         AABBOptimizedTree() :
 147                                                                                                 mNbNodes        (0)
 148                                                                                                                                                                                         {}
 149                 virtual                                                         ~AABBOptimizedTree()                                                    {}
 150
 151                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 152                 /**
 153                  *      Builds the collision tree from a generic AABB tree.
 154                  *      \param          tree                    [in] generic AABB tree
 155                  *      \return         true if success
 156                  */
 157                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 158                 virtual                 bool                            Build(AABBTree* tree)                                                                                   = 0;
 159
 160                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 161                 /**
 162                  *      Refits the collision tree after vertices have been modified.
 163                  *      \param          mesh_interface  [in] mesh interface for current model
 164                  *      \return         true if success
 165                  */
 166                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 167                 virtual                 bool                            Refit(const MeshInterface* mesh_interface)                                              = 0;
 168
 169                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 170                 /**
 171                  *      Walks the tree and call the user back for each node.
 172                  *      \param          callback        [in] walking callback
 173                  *      \param          user_data       [in] callback's user data
 174                  *      \return         true if success
 175                  */
 176                 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 177                 virtual                 bool                            Walk(GenericWalkingCallback callback, void* user_data) const    = 0;
 178
 179                 // Data access
 180                 virtual                 udword                          GetUsedBytes()          const                                                                           = 0;
 181                 inline_                 udword                          GetNbNodes()            const                                           { return mNbNodes;      }
 182
 183                 protected:
 184                                                 udword                          mNbNodes;
 185         };
 186
 187         class OPCODE_API AABBCollisionTree : public AABBOptimizedTree
 188         {
 189                 IMPLEMENT_COLLISION_TREE(AABBCollisionTree, AABBCollisionNode)
 190         };
 191
 192         class OPCODE_API AABBNoLeafTree : public AABBOptimizedTree
 193         {
 194                 IMPLEMENT_COLLISION_TREE(AABBNoLeafTree, AABBNoLeafNode)
 195         };
 196
 197         class OPCODE_API AABBQuantizedTree : public AABBOptimizedTree
 198         {
 199                 IMPLEMENT_COLLISION_TREE(AABBQuantizedTree, AABBQuantizedNode)
 200
 201                 public:
 202                                                 Point                           mCenterCoeff;
 203                                                 Point                           mExtentsCoeff;
 204         };
 205
 206         class OPCODE_API AABBQuantizedNoLeafTree : public AABBOptimizedTree
 207         {
 208                 IMPLEMENT_COLLISION_TREE(AABBQuantizedNoLeafTree, AABBQuantizedNoLeafNode)
 209
 210                 public:
 211                                                 Point                           mCenterCoeff;
 212                                                 Point                           mExtentsCoeff;
 213         };
 214
 215 #endif // __OPC_OPTIMIZEDTREE_H__