| 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 versatile AABB tree. |
|---|
| 12 | * \file OPC_AABBTree.h |
|---|
| 13 | * \author Pierre Terdiman |
|---|
| 14 | * \date March, 20, 2001 |
|---|
| 15 | */ |
|---|
| 16 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
|---|
| 17 | |
|---|
| 18 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
|---|
| 19 | // Include Guard |
|---|
| 20 | #ifndef __OPC_AABBTREE_H__ |
|---|
| 21 | #define __OPC_AABBTREE_H__ |
|---|
| 22 | |
|---|
| 23 | #ifdef OPC_NO_NEG_VANILLA_TREE |
|---|
| 24 | //! TO BE DOCUMENTED |
|---|
| 25 | #define IMPLEMENT_TREE(base_class, volume) \ |
|---|
| 26 | public: \ |
|---|
| 27 | /* Constructor / Destructor */ \ |
|---|
| 28 | base_class(); \ |
|---|
| 29 | ~base_class(); \ |
|---|
| 30 | /* Data access */ \ |
|---|
| 31 | inline_ const volume* Get##volume() const { return &mBV; } \ |
|---|
| 32 | /* Clear the last bit */ \ |
|---|
| 33 | inline_ const base_class* GetPos() const { return (const base_class*)(mPos&~1); } \ |
|---|
| 34 | inline_ const base_class* GetNeg() const { const base_class* P = GetPos(); return P ? P+1 : null;} \ |
|---|
| 35 | \ |
|---|
| 36 | /* We don't need to test both nodes since we can't have one without the other */ \ |
|---|
| 37 | inline_ bool IsLeaf() const { return !GetPos(); } \ |
|---|
| 38 | \ |
|---|
| 39 | /* Stats */ \ |
|---|
| 40 | inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \ |
|---|
| 41 | protected: \ |
|---|
| 42 | /* Tree-independent data */ \ |
|---|
| 43 | /* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/ \ |
|---|
| 44 | /* Whatever happens we need the two children and the enclosing volume.*/ \ |
|---|
| 45 | volume mBV; /* Global bounding-volume enclosing all the node-related primitives */ \ |
|---|
| 46 | size_t mPos; /* "Positive" & "Negative" children */ |
|---|
| 47 | #else |
|---|
| 48 | //! TO BE DOCUMENTED |
|---|
| 49 | #define IMPLEMENT_TREE(base_class, volume) \ |
|---|
| 50 | public: \ |
|---|
| 51 | /* Constructor / Destructor */ \ |
|---|
| 52 | base_class(); \ |
|---|
| 53 | ~base_class(); \ |
|---|
| 54 | /* Data access */ \ |
|---|
| 55 | inline_ const volume* Get##volume() const { return &mBV; } \ |
|---|
| 56 | /* Clear the last bit */ \ |
|---|
| 57 | inline_ const base_class* GetPos() const { return (const base_class*)(mPos&~1); } \ |
|---|
| 58 | inline_ const base_class* GetNeg() const { return (const base_class*)(mNeg&~1); } \ |
|---|
| 59 | \ |
|---|
| 60 | /* inline_ bool IsLeaf() const { return (!GetPos() && !GetNeg()); } */ \ |
|---|
| 61 | /* We don't need to test both nodes since we can't have one without the other */ \ |
|---|
| 62 | inline_ bool IsLeaf() const { return !GetPos(); } \ |
|---|
| 63 | \ |
|---|
| 64 | /* Stats */ \ |
|---|
| 65 | inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \ |
|---|
| 66 | protected: \ |
|---|
| 67 | /* Tree-independent data */ \ |
|---|
| 68 | /* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/ \ |
|---|
| 69 | /* Whatever happens we need the two children and the enclosing volume.*/ \ |
|---|
| 70 | volume mBV; /* Global bounding-volume enclosing all the node-related primitives */ \ |
|---|
| 71 | size_t mPos; /* "Positive" child */ \ |
|---|
| 72 | size_t mNeg; /* "Negative" child */ |
|---|
| 73 | #endif |
|---|
| 74 | |
|---|
| 75 | typedef void (*CullingCallback) (udword nb_primitives, udword* node_primitives, BOOL need_clipping, void* user_data); |
|---|
| 76 | |
|---|
| 77 | class OPCODE_API AABBTreeNode |
|---|
| 78 | { |
|---|
| 79 | IMPLEMENT_TREE(AABBTreeNode, AABB) |
|---|
| 80 | public: |
|---|
| 81 | // Data access |
|---|
| 82 | inline_ const udword* GetPrimitives() const { return mNodePrimitives; } |
|---|
| 83 | inline_ udword GetNbPrimitives() const { return mNbPrimitives; } |
|---|
| 84 | |
|---|
| 85 | protected: |
|---|
| 86 | // Tree-dependent data |
|---|
| 87 | udword* mNodePrimitives; //!< Node-related primitives (shortcut to a position in mIndices below) |
|---|
| 88 | udword mNbPrimitives; //!< Number of primitives for this node |
|---|
| 89 | // Internal methods |
|---|
| 90 | udword Split(udword axis, AABBTreeBuilder* builder); |
|---|
| 91 | bool Subdivide(AABBTreeBuilder* builder); |
|---|
| 92 | void _BuildHierarchy(AABBTreeBuilder* builder); |
|---|
| 93 | void _Refit(AABBTreeBuilder* builder); |
|---|
| 94 | }; |
|---|
| 95 | |
|---|
| 96 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
|---|
| 97 | /** |
|---|
| 98 | * User-callback, called for each node by the walking code. |
|---|
| 99 | * \param current [in] current node |
|---|
| 100 | * \param depth [in] current node's depth |
|---|
| 101 | * \param user_data [in] user-defined data |
|---|
| 102 | * \return true to recurse through children, else false to bypass them |
|---|
| 103 | */ |
|---|
| 104 | /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// |
|---|
| 105 | typedef bool (*WalkingCallback) (const AABBTreeNode* current, udword depth, void* user_data); |
|---|
| 106 | |
|---|
| 107 | class OPCODE_API AABBTree : public AABBTreeNode |
|---|
| 108 | { |
|---|
| 109 | public: |
|---|
| 110 | // Constructor / Destructor |
|---|
| 111 | AABBTree(); |
|---|
| 112 | ~AABBTree(); |
|---|
| 113 | // Build |
|---|
| 114 | bool Build(AABBTreeBuilder* builder); |
|---|
| 115 | void Release(); |
|---|
| 116 | |
|---|
| 117 | // Data access |
|---|
| 118 | inline_ const udword* GetIndices() const { return mIndices; } //!< Catch the indices |
|---|
| 119 | inline_ udword GetNbNodes() const { return mTotalNbNodes; } //!< Catch the number of nodes |
|---|
| 120 | |
|---|
| 121 | // Infos |
|---|
| 122 | bool IsComplete() const; |
|---|
| 123 | // Stats |
|---|
| 124 | udword ComputeDepth() const; |
|---|
| 125 | udword GetUsedBytes() const; |
|---|
| 126 | udword Walk(WalkingCallback callback, void* user_data) const; |
|---|
| 127 | |
|---|
| 128 | bool Refit(AABBTreeBuilder* builder); |
|---|
| 129 | bool Refit2(AABBTreeBuilder* builder); |
|---|
| 130 | private: |
|---|
| 131 | udword* mIndices; //!< Indices in the app list. Indices are reorganized during build (permutation). |
|---|
| 132 | AABBTreeNode* mPool; //!< Linear pool of nodes for complete trees. Null otherwise. [Opcode 1.3] |
|---|
| 133 | // Stats |
|---|
| 134 | udword mTotalNbNodes; //!< Number of nodes in the tree. |
|---|
| 135 | }; |
|---|
| 136 | |
|---|
| 137 | #endif // __OPC_AABBTREE_H__ |
|---|
