[216] | 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 | { |
---|
| 64 | IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB) |
---|
| 65 | |
---|
| 66 | inline_ float GetVolume() const { return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z; } |
---|
| 67 | inline_ float GetSize() const { return mAABB.mExtents.SquareMagnitude(); } |
---|
| 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 | { |
---|
| 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 |
---|
| 137 | AABBOptimizedTree() : |
---|
| 138 | mNbNodes (0) |
---|
| 139 | {} |
---|
| 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; |
---|
| 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__ |
---|