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 uintptr_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 uintptr_t mPos; /* "Positive" child */ \ 72 uintptr_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 { IMPLEMENT_TREE(AABBTreeNode,AABB)79 IMPLEMENT_TREE(AABBTreeNode, AABB) 80 public: 81 // Data access 82 inline_ const udword* GetPrimitives() const { return mNodePrimitives; } GetNbPrimitives()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 GetIndices()118 inline_ const udword* GetIndices() const { return mIndices; } //!< Catch the indices GetNbNodes()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__ 138