[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 a tree collider. |
---|
| 12 | * \file OPC_TreeCollider.h |
---|
| 13 | * \author Pierre Terdiman |
---|
| 14 | * \date March, 20, 2001 |
---|
| 15 | */ |
---|
| 16 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 17 | |
---|
| 18 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 19 | // Include Guard |
---|
| 20 | #ifndef __OPC_TREECOLLIDER_H__ |
---|
| 21 | #define __OPC_TREECOLLIDER_H__ |
---|
| 22 | |
---|
| 23 | //! This structure holds cached information used by the algorithm. |
---|
| 24 | //! Two model pointers and two colliding primitives are cached. Model pointers are assigned |
---|
| 25 | //! to their respective meshes, and the pair of colliding primitives is used for temporal |
---|
| 26 | //! coherence. That is, in case temporal coherence is enabled, those two primitives are |
---|
| 27 | //! tested for overlap before everything else. If they still collide, we're done before |
---|
| 28 | //! even entering the recursive collision code. |
---|
| 29 | struct OPCODE_API BVTCache : Pair |
---|
| 30 | { |
---|
| 31 | //! Constructor |
---|
| 32 | inline_ BVTCache() |
---|
| 33 | { |
---|
| 34 | ResetCache(); |
---|
| 35 | ResetCountDown(); |
---|
| 36 | } |
---|
| 37 | |
---|
| 38 | void ResetCache() |
---|
| 39 | { |
---|
| 40 | Model0 = null; |
---|
| 41 | Model1 = null; |
---|
| 42 | id0 = 0; |
---|
| 43 | id1 = 1; |
---|
| 44 | #ifdef __MESHMERIZER_H__ // Collision hulls only supported within ICE ! |
---|
| 45 | HullTest = true; |
---|
| 46 | SepVector.pid = 0; |
---|
| 47 | SepVector.qid = 0; |
---|
| 48 | SepVector.SV = Point(1.0f, 0.0f, 0.0f); |
---|
| 49 | #endif // __MESHMERIZER_H__ |
---|
| 50 | } |
---|
| 51 | |
---|
| 52 | #ifdef __MESHMERIZER_H__ // Collision hulls only supported within ICE ! |
---|
| 53 | inline_ void ResetCountDown() |
---|
| 54 | { |
---|
| 55 | CountDown = 50; |
---|
| 56 | } |
---|
| 57 | #else |
---|
| 58 | void ResetCountDown(){}; |
---|
| 59 | #endif // __MESHMERIZER_H__ |
---|
| 60 | |
---|
| 61 | const Model* Model0; //!< Model for first object |
---|
| 62 | const Model* Model1; //!< Model for second object |
---|
| 63 | |
---|
| 64 | #ifdef __MESHMERIZER_H__ // Collision hulls only supported within ICE ! |
---|
| 65 | SVCache SepVector; |
---|
| 66 | udword CountDown; |
---|
| 67 | bool HullTest; |
---|
| 68 | #endif // __MESHMERIZER_H__ |
---|
| 69 | }; |
---|
| 70 | |
---|
| 71 | class OPCODE_API AABBTreeCollider : public Collider |
---|
| 72 | { |
---|
| 73 | public: |
---|
| 74 | // Constructor / Destructor |
---|
| 75 | AABBTreeCollider(); |
---|
| 76 | virtual ~AABBTreeCollider(); |
---|
| 77 | // Generic collision query |
---|
| 78 | |
---|
| 79 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 80 | /** |
---|
| 81 | * Generic collision query for generic OPCODE models. After the call, access the results with: |
---|
| 82 | * - GetContactStatus() |
---|
| 83 | * - GetNbPairs() |
---|
| 84 | * - GetPairs() |
---|
| 85 | * |
---|
| 86 | * \param cache [in] collision cache for model pointers and a colliding pair of primitives |
---|
| 87 | * \param world0 [in] world matrix for first object, or null |
---|
| 88 | * \param world1 [in] world matrix for second object, or null |
---|
| 89 | * \return true if success |
---|
| 90 | * \warning SCALE NOT SUPPORTED. The matrices must contain rotation & translation parts only. |
---|
| 91 | */ |
---|
| 92 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 93 | bool Collide(BVTCache& cache, const Matrix4x4* world0=null, const Matrix4x4* world1=null); |
---|
| 94 | |
---|
| 95 | // Collision queries |
---|
| 96 | bool Collide(const AABBCollisionTree* tree0, const AABBCollisionTree* tree1, const Matrix4x4* world0=null, const Matrix4x4* world1=null, Pair* cache=null); |
---|
| 97 | bool Collide(const AABBNoLeafTree* tree0, const AABBNoLeafTree* tree1, const Matrix4x4* world0=null, const Matrix4x4* world1=null, Pair* cache=null); |
---|
| 98 | bool Collide(const AABBQuantizedTree* tree0, const AABBQuantizedTree* tree1, const Matrix4x4* world0=null, const Matrix4x4* world1=null, Pair* cache=null); |
---|
| 99 | bool Collide(const AABBQuantizedNoLeafTree* tree0, const AABBQuantizedNoLeafTree* tree1, const Matrix4x4* world0=null, const Matrix4x4* world1=null, Pair* cache=null); |
---|
| 100 | // Settings |
---|
| 101 | |
---|
| 102 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 103 | /** |
---|
| 104 | * Settings: selects between full box-box tests or "SAT-lite" tests (where Class III axes are discarded) |
---|
| 105 | * \param flag [in] true for full tests, false for coarse tests |
---|
| 106 | * \see SetFullPrimBoxTest(bool flag) |
---|
| 107 | */ |
---|
| 108 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 109 | inline_ void SetFullBoxBoxTest(bool flag) { mFullBoxBoxTest = flag; } |
---|
| 110 | |
---|
| 111 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 112 | /** |
---|
| 113 | * Settings: selects between full triangle-box tests or "SAT-lite" tests (where Class III axes are discarded) |
---|
| 114 | * \param flag [in] true for full tests, false for coarse tests |
---|
| 115 | * \see SetFullBoxBoxTest(bool flag) |
---|
| 116 | */ |
---|
| 117 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 118 | inline_ void SetFullPrimBoxTest(bool flag) { mFullPrimBoxTest = flag; } |
---|
| 119 | |
---|
| 120 | // Stats |
---|
| 121 | |
---|
| 122 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 123 | /** |
---|
| 124 | * Stats: gets the number of BV-BV overlap tests after a collision query. |
---|
| 125 | * \see GetNbPrimPrimTests() |
---|
| 126 | * \see GetNbBVPrimTests() |
---|
| 127 | * \return the number of BV-BV tests performed during last query |
---|
| 128 | */ |
---|
| 129 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 130 | inline_ udword GetNbBVBVTests() const { return mNbBVBVTests; } |
---|
| 131 | |
---|
| 132 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 133 | /** |
---|
| 134 | * Stats: gets the number of Triangle-Triangle overlap tests after a collision query. |
---|
| 135 | * \see GetNbBVBVTests() |
---|
| 136 | * \see GetNbBVPrimTests() |
---|
| 137 | * \return the number of Triangle-Triangle tests performed during last query |
---|
| 138 | */ |
---|
| 139 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 140 | inline_ udword GetNbPrimPrimTests() const { return mNbPrimPrimTests; } |
---|
| 141 | |
---|
| 142 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 143 | /** |
---|
| 144 | * Stats: gets the number of BV-Triangle overlap tests after a collision query. |
---|
| 145 | * \see GetNbBVBVTests() |
---|
| 146 | * \see GetNbPrimPrimTests() |
---|
| 147 | * \return the number of BV-Triangle tests performed during last query |
---|
| 148 | */ |
---|
| 149 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 150 | inline_ udword GetNbBVPrimTests() const { return mNbBVPrimTests; } |
---|
| 151 | |
---|
| 152 | // Data access |
---|
| 153 | |
---|
| 154 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 155 | /** |
---|
| 156 | * Gets the number of contacts after a collision query. |
---|
| 157 | * \see GetContactStatus() |
---|
| 158 | * \see GetPairs() |
---|
| 159 | * \return the number of contacts / colliding pairs. |
---|
| 160 | */ |
---|
| 161 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 162 | inline_ udword GetNbPairs() const { return mPairs.GetNbEntries()>>1; } |
---|
| 163 | |
---|
| 164 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 165 | /** |
---|
| 166 | * Gets the pairs of colliding triangles after a collision query. |
---|
| 167 | * \see GetContactStatus() |
---|
| 168 | * \see GetNbPairs() |
---|
| 169 | * \return the list of colliding pairs (triangle indices) |
---|
| 170 | */ |
---|
| 171 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 172 | inline_ const Pair* GetPairs() const { return (const Pair*)mPairs.GetEntries(); } |
---|
| 173 | |
---|
| 174 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 175 | /** |
---|
| 176 | * Validates current settings. You should call this method after all the settings and callbacks have been defined for a collider. |
---|
| 177 | * \return null if everything is ok, else a string describing the problem |
---|
| 178 | */ |
---|
| 179 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
---|
| 180 | override(Collider) const char* ValidateSettings(); |
---|
| 181 | |
---|
| 182 | protected: |
---|
| 183 | // Colliding pairs |
---|
| 184 | Container mPairs; //!< Pairs of colliding primitives |
---|
| 185 | // User mesh interfaces |
---|
| 186 | const MeshInterface* mIMesh0; //!< User-defined mesh interface for object0 |
---|
| 187 | const MeshInterface* mIMesh1; //!< User-defined mesh interface for object1 |
---|
| 188 | // Stats |
---|
| 189 | udword mNbBVBVTests; //!< Number of BV-BV tests |
---|
| 190 | udword mNbPrimPrimTests; //!< Number of Primitive-Primitive tests |
---|
| 191 | udword mNbBVPrimTests; //!< Number of BV-Primitive tests |
---|
| 192 | // Precomputed data |
---|
| 193 | Matrix3x3 mAR; //!< Absolute rotation matrix |
---|
| 194 | Matrix3x3 mR0to1; //!< Rotation from object0 to object1 |
---|
| 195 | Matrix3x3 mR1to0; //!< Rotation from object1 to object0 |
---|
| 196 | Point mT0to1; //!< Translation from object0 to object1 |
---|
| 197 | Point mT1to0; //!< Translation from object1 to object0 |
---|
| 198 | // Dequantization coeffs |
---|
| 199 | Point mCenterCoeff0; |
---|
| 200 | Point mExtentsCoeff0; |
---|
| 201 | Point mCenterCoeff1; |
---|
| 202 | Point mExtentsCoeff1; |
---|
| 203 | // Leaf description |
---|
| 204 | Point mLeafVerts[3]; //!< Triangle vertices |
---|
| 205 | udword mLeafIndex; //!< Triangle index |
---|
| 206 | // Settings |
---|
| 207 | bool mFullBoxBoxTest; //!< Perform full BV-BV tests (true) or SAT-lite tests (false) |
---|
| 208 | bool mFullPrimBoxTest; //!< Perform full Primitive-BV tests (true) or SAT-lite tests (false) |
---|
| 209 | // Internal methods |
---|
| 210 | |
---|
| 211 | // Standard AABB trees |
---|
| 212 | void _Collide(const AABBCollisionNode* b0, const AABBCollisionNode* b1); |
---|
| 213 | // Quantized AABB trees |
---|
| 214 | void _Collide(const AABBQuantizedNode* b0, const AABBQuantizedNode* b1, const Point& a, const Point& Pa, const Point& b, const Point& Pb); |
---|
| 215 | // No-leaf AABB trees |
---|
| 216 | void _CollideTriBox(const AABBNoLeafNode* b); |
---|
| 217 | void _CollideBoxTri(const AABBNoLeafNode* b); |
---|
| 218 | void _Collide(const AABBNoLeafNode* a, const AABBNoLeafNode* b); |
---|
| 219 | // Quantized no-leaf AABB trees |
---|
| 220 | void _CollideTriBox(const AABBQuantizedNoLeafNode* b); |
---|
| 221 | void _CollideBoxTri(const AABBQuantizedNoLeafNode* b); |
---|
| 222 | void _Collide(const AABBQuantizedNoLeafNode* a, const AABBQuantizedNoLeafNode* b); |
---|
| 223 | // Overlap tests |
---|
| 224 | void PrimTest(udword id0, udword id1); |
---|
| 225 | inline_ void PrimTestTriIndex(udword id1); |
---|
| 226 | inline_ void PrimTestIndexTri(udword id0); |
---|
| 227 | |
---|
| 228 | inline_ BOOL BoxBoxOverlap(const Point& ea, const Point& ca, const Point& eb, const Point& cb); |
---|
| 229 | inline_ BOOL TriBoxOverlap(const Point& center, const Point& extents); |
---|
| 230 | inline_ BOOL TriTriOverlap(const Point& V0, const Point& V1, const Point& V2, const Point& U0, const Point& U1, const Point& U2); |
---|
| 231 | // Init methods |
---|
| 232 | void InitQuery(const Matrix4x4* world0=null, const Matrix4x4* world1=null); |
---|
| 233 | bool CheckTemporalCoherence(Pair* cache); |
---|
| 234 | |
---|
| 235 | inline_ BOOL Setup(const MeshInterface* mi0, const MeshInterface* mi1) |
---|
| 236 | { |
---|
| 237 | mIMesh0 = mi0; |
---|
| 238 | mIMesh1 = mi1; |
---|
| 239 | |
---|
| 240 | if(!mIMesh0 || !mIMesh1) return FALSE; |
---|
| 241 | |
---|
| 242 | return TRUE; |
---|
| 243 | } |
---|
| 244 | }; |
---|
| 245 | |
---|
| 246 | #endif // __OPC_TREECOLLIDER_H__ |
---|