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