openhrp3: OPC_AABBTree.h Source File

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_AABBTREE_H__
00021 #define __OPC_AABBTREE_H__
00022 
00023 #if (defined __x86_64) || (defined __aarch64__)
00024 #define EXWORD uqword
00025 #else
00026 #define EXWORD udword
00027 #endif
00028 
00029 #ifdef OPC_NO_NEG_VANILLA_TREE
00030 
00031         #define IMPLEMENT_TREE(base_class, volume)                                                                                                                                                      \
00032                 public:                                                                                                                                                                                                                 \
00033                 /* Constructor / Destructor */                                                                                                                                                                  \
00034                                                                         base_class();                                                                                                                                           \
00035                                                                         ~base_class();                                                                                                                                          \
00036                 /* Data access */                                                                                                                                                                                               \
00037                 inline_ const volume*           Get##volume()   const   { return &mBV;                                                  }                                       \
00038                 /* Clear the last bit */                                                                                                                                                                                \
00039                 inline_ const base_class*       GetPos()                const   { return (const base_class*)(mPos&~1);  }                                       \
00040                 inline_ const base_class*       GetNeg()                const   { const base_class* P = GetPos(); return P ? P+1 : null;}       \
00041                                                                                                                                                                                                                                                 \
00042                 /* We don't need to test both nodes since we can't have one without the other   */                                                              \
00043                 inline_ bool                            IsLeaf()                const   { return !GetPos();                                             }                                       \
00044                                                                                                                                                                                                                                                 \
00045                 /* Stats */                                                                                                                                                                                                             \
00046                 inline_ udword                          GetNodeSize()   const   { return SIZEOFOBJECT;                                  }                                       \
00047                 protected:                                                                                                                                                                                                              \
00048                 /* Tree-independent data */                                                                                                                                                                             \
00049                 /* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/                                \
00050                 /* Whatever happens we need the two children and the enclosing volume.*/                                                                                \
00051                                 volume                          mBV;            /* Global bounding-volume enclosing all the node-related primitives */  \
00052                                 EXWORD                          mPos;           /* "Positive" & "Negative" children */
00053 #else
00054 
00055         #define IMPLEMENT_TREE(base_class, volume)                                                                                                                                                      \
00056                 public:                                                                                                                                                                                                                 \
00057                 /* Constructor / Destructor */                                                                                                                                                                  \
00058                                                                         base_class();                                                                                                                                           \
00059                                                                         ~base_class();                                                                                                                                          \
00060                 /* Data access */                                                                                                                                                                                               \
00061                 inline_ const volume*           Get##volume()   const   { return &mBV;                                                  }                                       \
00062                 /* Clear the last bit */                                                                                                                                                                                \
00063                 inline_ const base_class*       GetPos()                const   { return (const base_class*)(mPos&~1);  }                                       \
00064                 inline_ const base_class*       GetNeg()                const   { return (const base_class*)(mNeg&~1);  }                                       \
00065                                                                                                                                                                                                                                                 \
00066 /*              inline_ bool                            IsLeaf()                const   { return (!GetPos() && !GetNeg());      }       */                                      \
00067                 /* We don't need to test both nodes since we can't have one without the other   */                                                              \
00068                 inline_ bool                            IsLeaf()                const   { return !GetPos();                                             }                                       \
00069                                                                                                                                                                                                                                                 \
00070                 /* Stats */                                                                                                                                                                                                             \
00071                 inline_ udword                          GetNodeSize()   const   { return SIZEOFOBJECT;                                  }                                       \
00072                 protected:                                                                                                                                                                                                              \
00073                 /* Tree-independent data */                                                                                                                                                                             \
00074                 /* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/                                \
00075                 /* Whatever happens we need the two children and the enclosing volume.*/                                                                                \
00076                                 volume                          mBV;            /* Global bounding-volume enclosing all the node-related primitives */  \
00077                                 EXWORD                          mPos;           /* "Positive" child */                                                                                                  \
00078                                 EXOWRD                          mNeg;           /* "Negative" child */
00079 #endif
00080 
00081         typedef         void                            (*CullingCallback)              (udword nb_primitives, udword* node_primitives, BOOL need_clipping, void* user_data);
00082 
00083         class OPCODE_API AABBTreeNode
00084         {
00085                                                                         IMPLEMENT_TREE(AABBTreeNode, AABB)
00086                 public:
00087                 // Data access
00088                 inline_ const udword*           GetPrimitives()         const   { return mNodePrimitives;       }
00089                 inline_ udword                          GetNbPrimitives()       const   { return mNbPrimitives;         }
00090 
00091                 protected:
00092                 // Tree-dependent data
00093                                 udword*                         mNodePrimitives;        
00094                                 udword                          mNbPrimitives;          
00095                 // Internal methods
00096                                 udword                          Split(udword axis, AABBTreeBuilder* builder);
00097                                 bool                            Subdivide(AABBTreeBuilder* builder);
00098                                 void                            _BuildHierarchy(AABBTreeBuilder* builder);
00099                                 void                            _Refit(AABBTreeBuilder* builder);
00100         };
00101 
00103 
00110 
00111         typedef         bool                            (*WalkingCallback)      (const AABBTreeNode* current, udword depth, void* user_data);
00112 
00113         class OPCODE_API AABBTree : public AABBTreeNode
00114         {
00115                 public:
00116                 // Constructor / Destructor
00117                                                                         AABBTree();
00118                                                                         ~AABBTree();
00119                 // Build
00120                                 bool                            Build(AABBTreeBuilder* builder);
00121                                 void                            Release();
00122 
00123                 // Data access
00124                 inline_ const udword*           GetIndices()            const   { return mIndices;              }       
00125                 inline_ udword                          GetNbNodes()            const   { return mTotalNbNodes; }       
00126 
00127                 // Infos
00128                                 bool                            IsComplete()            const;
00129                 // Stats
00130                                 udword                          ComputeDepth()          const;
00131                                 udword                          GetUsedBytes()          const;
00132                                 udword                          Walk(WalkingCallback callback, void* user_data) const;
00133 
00134                                 bool                            Refit(AABBTreeBuilder* builder);
00135                                 bool                            Refit2(AABBTreeBuilder* builder);
00136                 private:
00137                                 udword*                         mIndices;                       
00138                                 AABBTreeNode*           mPool;                          
00139                 // Stats
00140                                 udword                          mTotalNbNodes;          
00141         };
00142 
00143 #endif // __OPC_AABBTREE_H__