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