OPC_OptimizedTree.h
Go to the documentation of this file.
00001 
00002 /*
00003  *      OPCODE - Optimized Collision Detection
00004  *      Copyright (C) 2001 Pierre Terdiman
00005  *      Homepage: http://www.codercorner.com/Opcode.htm
00006  */
00008 
00010 
00016 
00017 
00019 // Include Guard
00020 #ifndef __OPC_OPTIMIZEDTREE_H__
00021 #define __OPC_OPTIMIZEDTREE_H__
00022 
00023 #if (defined __x86_64) || (defined __aarch64__)
00024 #define EXWORD uqword
00025 #else
00026 #define EXWORD udword
00027 #endif
00028 
00030         #define IMPLEMENT_IMPLICIT_NODE(base_class, volume)                                                                                                             \
00031                 public:                                                                                                                                                                                         \
00032                 /* Constructor / Destructor */                                                                                                                                          \
00033                 inline_                                                         base_class() : mData(0) {}                                                                              \
00034                 inline_                                                         ~base_class()                   {}                                                                              \
00035                 /* Leaf test */                                                                                                                                                                         \
00036                 inline_                 BOOL                            IsLeaf()                const   { return mData&1;                                       }       \
00037                 /* Data access */                                                                                                                                                                       \
00038                 inline_                 const base_class*       GetPos()                const   { return (base_class*)mData;            }       \
00039                 inline_                 const base_class*       GetNeg()                const   { return ((base_class*)mData)+1;        }       \
00040                 /* Modified by S-cubed, Inc. */                                                                                                                                         \
00041                 inline_                 const base_class*       GetB()                  const   { return                                mB;             }       \
00042                 inline_                 udword                          GetPrimitive()  const   { return (mData>>1);                            }       \
00043                 /* Stats */                                                                                                                                                                                     \
00044                 inline_                 udword                          GetNodeSize()   const   { return SIZEOFOBJECT;                          }       \
00045                                                                                                                                                                                                                         \
00046                                                 volume                          mAABB;                                                                                                                  \
00047                                                 EXWORD                          mData;                                                                                                                  \
00048                 /* Modified by S-cubed, Inc. */                                                                                                                                         \
00049                                                 base_class*                     mB;                                                                                                                             
00050 
00052         #define IMPLEMENT_NOLEAF_NODE(base_class, volume)                                                                                                               \
00053                 public:                                                                                                                                                                                         \
00054                 /* Constructor / Destructor */                                                                                                                                          \
00055                 inline_                                                         base_class() : mPosData(0), mNegData(0) {}                                              \
00056                 inline_                                                         ~base_class()                                                   {}                                              \
00057                 /* Leaf tests */                                                                                                                                                                        \
00058                 inline_                 BOOL                            HasPosLeaf()            const   { return mPosData&1;                    }       \
00059                 inline_                 BOOL                            HasNegLeaf()            const   { return mNegData&1;                    }       \
00060                 /* Data access */                                                                                                                                                                       \
00061                 inline_                 const base_class*       GetPos()                        const   { return (base_class*)mPosData; }       \
00062                 inline_                 const base_class*       GetNeg()                        const   { return (base_class*)mNegData; }       \
00063                 /* Modified by S-cubed, Inc. */                                                                                                                                         \
00064                 inline_                 const base_class*       GetB()                          const   { return                                mB;             }       \
00065                 inline_                 udword                          GetPosPrimitive()       const   { return (mPosData>>1);                 }       \
00066                 inline_                 udword                          GetNegPrimitive()       const   { return (mNegData>>1);                 }       \
00067                 /* Stats */                                                                                                                                                                                     \
00068                 inline_                 udword                          GetNodeSize()           const   { return SIZEOFOBJECT;                  }       \
00069                                                                                                                                                                                                                         \
00070                                                 volume                          mAABB;                                                                                                                  \
00071                                                 EXWORD                          mPosData;                                                                                                               \
00072                                                 EXWORD                          mNegData;                                                                                                               \
00073                 /* Modified by S-cubed, Inc. */                                                                                                                                         \
00074                                                 base_class*                     mB;                                                                                                                             
00075 
00076         class OPCODE_API AABBCollisionNode
00077         {
00078                 IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB)
00079 
00080                 inline_                 float                           GetVolume()             const   { return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z;        }
00081                 inline_                 float                           GetSize()               const   { return mAABB.mExtents.SquareMagnitude();      }
00082                 inline_                 udword                          GetRadius()             const
00083                                                                                         {
00084                                                                                                 udword* Bits = (udword*)&mAABB.mExtents.x;
00085                                                                                                 udword Max = Bits[0];
00086                                                                                                 if(Bits[1]>Max) Max = Bits[1];
00087                                                                                                 if(Bits[2]>Max) Max = Bits[2];
00088                                                                                                 return Max;
00089                                                                                         }
00090 
00091                 // NB: using the square-magnitude or the true volume of the box, seems to yield better results
00092                 // (assuming UNC-like informed traversal methods). I borrowed this idea from PQP. The usual "size"
00093                 // otherwise, is the largest box extent. In SOLID that extent is computed on-the-fly each time it's
00094                 // needed (the best approach IMHO). In RAPID the rotation matrix is permuted so that Extent[0] is
00095                 // always the greatest, which saves looking for it at runtime. On the other hand, it yields matrices
00096                 // whose determinant is not 1, i.e. you can't encode them anymore as unit quaternions. Not a very
00097                 // good strategy.
00098         };
00099 
00100         class OPCODE_API AABBQuantizedNode
00101         {
00102                 IMPLEMENT_IMPLICIT_NODE(AABBQuantizedNode, QuantizedAABB)
00103 
00104                 inline_                 uword                           GetSize()               const
00105                                                                                         {
00106                                                                                                 const uword* Bits = mAABB.mExtents;
00107                                                                                                 uword Max = Bits[0];
00108                                                                                                 if(Bits[1]>Max) Max = Bits[1];
00109                                                                                                 if(Bits[2]>Max) Max = Bits[2];
00110                                                                                                 return Max;
00111                                                                                         }
00112                 // NB: for quantized nodes I don't feel like computing a square-magnitude with integers all
00113                 // over the place.......!
00114         };
00115 
00116         class OPCODE_API AABBNoLeafNode
00117         {
00118                 IMPLEMENT_NOLEAF_NODE(AABBNoLeafNode, CollisionAABB)
00119         };
00120 
00121         class OPCODE_API AABBQuantizedNoLeafNode
00122         {
00123                 IMPLEMENT_NOLEAF_NODE(AABBQuantizedNoLeafNode, QuantizedAABB)
00124         };
00125 
00127         #define IMPLEMENT_COLLISION_TREE(base_class, node)                                                                                                                              \
00128                 public:                                                                                                                                                                                                         \
00129                 /* Constructor / Destructor */                                                                                                                                                          \
00130                                                                                                         base_class();                                                                                                   \
00131                 virtual                                                                         ~base_class();                                                                                                  \
00132                 /* Builds from a standard tree */                                                                                                                                                       \
00133                 override(AABBOptimizedTree)     bool                    Build(AABBTree* tree);                                                                                  \
00134                 /* Refits the tree */                                                                                                                                                                           \
00135                 override(AABBOptimizedTree)     bool                    Refit(const MeshInterface* mesh_interface);                                             \
00136                 /* Walks the tree */                                                                                                                                                                            \
00137                 override(AABBOptimizedTree)     bool                    Walk(GenericWalkingCallback callback, void* user_data) const;   \
00138                 /* Data access */                                                                                                                                                                                       \
00139                 inline_                                         const node*             GetNodes()              const   { return mNodes;                                        }       \
00140                 /* Stats */                                                                                                                                                                                                     \
00141                 override(AABBOptimizedTree)     udword                  GetUsedBytes()  const   { return mNbNodes*sizeof(node);         }       \
00142                 private:                                                                                                                                                                                                        \
00143                                                                         node*                   mNodes;
00144 
00145         typedef         bool                            (*GenericWalkingCallback)       (const void* current, void* user_data);
00146 
00147         class OPCODE_API AABBOptimizedTree
00148         {
00149                 public:
00150                 // Constructor / Destructor
00151                                                                                         AABBOptimizedTree() :
00152                                                                                                 mNbNodes        (0)
00153                                                                                                                                                                                         {}
00154                 virtual                                                         ~AABBOptimizedTree()                                                    {}
00155 
00157 
00162 
00163                 virtual                 bool                            Build(AABBTree* tree)                                                                                   = 0;
00164 
00166 
00171 
00172                 virtual                 bool                            Refit(const MeshInterface* mesh_interface)                                              = 0;
00173 
00175 
00181 
00182                 virtual                 bool                            Walk(GenericWalkingCallback callback, void* user_data) const    = 0;
00183 
00184                 // Data access
00185                 virtual                 udword                          GetUsedBytes()          const                                                                           = 0;
00186                 inline_                 udword                          GetNbNodes()            const                                           { return mNbNodes;      }
00187 
00188                 protected:
00189                                                 udword                          mNbNodes;
00190         };
00191 
00192         class OPCODE_API AABBCollisionTree : public AABBOptimizedTree
00193         {
00194                 IMPLEMENT_COLLISION_TREE(AABBCollisionTree, AABBCollisionNode)
00195         };
00196 
00197         class OPCODE_API AABBNoLeafTree : public AABBOptimizedTree
00198         {
00199                 IMPLEMENT_COLLISION_TREE(AABBNoLeafTree, AABBNoLeafNode)
00200         };
00201 
00202         class OPCODE_API AABBQuantizedTree : public AABBOptimizedTree
00203         {
00204                 IMPLEMENT_COLLISION_TREE(AABBQuantizedTree, AABBQuantizedNode)
00205 
00206                 public:
00207                                                 Point                           mCenterCoeff;
00208                                                 Point                           mExtentsCoeff;
00209         };
00210 
00211         class OPCODE_API AABBQuantizedNoLeafTree : public AABBOptimizedTree
00212         {
00213                 IMPLEMENT_COLLISION_TREE(AABBQuantizedNoLeafTree, AABBQuantizedNoLeafNode)
00214 
00215                 public:
00216                                                 Point                           mCenterCoeff;
00217                                                 Point                           mExtentsCoeff;
00218         };
00219 
00220 #endif // __OPC_OPTIMIZEDTREE_H__


openhrp3
Author(s): AIST, General Robotix Inc., Nakamura Lab of Dept. of Mechano Informatics at University of Tokyo
autogenerated on Sun Apr 2 2017 03:43:55