Vegastrike 0.5.1 rc1  1.0
Original sources for Vegastrike Evolved
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
OPC_AABBTree.h
Go to the documentation of this file.
1 /*
3  * OPCODE - Optimized Collision Detection
4  * Copyright (C) 2001 Pierre Terdiman
5  * Homepage: http://www.codercorner.com/Opcode.htm
6  */
8 
10 
16 
19 // Include Guard
20 #ifndef __OPC_AABBTREE_H__
21 #define __OPC_AABBTREE_H__
22 
23 #ifdef OPC_NO_NEG_VANILLA_TREE
24  #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  #define IMPLEMENT_TREE(base_class, volume) \
50  public: \
51  /* Constructor / Destructor */ \
52  base_class(); \
53  ~base_class(); \
54 
55  /* Data access */ \
56  inline_ const volume* Get##volume() const { return &mBV; } \
57  /* Clear the last bit */ \
58  inline_ const base_class* GetPos() const { return (const base_class*)(mPos&~1); } \
59  inline_ const base_class* GetNeg() const { return (const base_class*)(mNeg&~1); } \
60  \
61 /* inline_ bool IsLeaf() const { return (!GetPos() && !GetNeg()); } */ \
62  /* We don't need to test both nodes since we can't have one without the other */ \
63  inline_ bool IsLeaf() const { return !GetPos(); } \
64  \
65  /* Stats */ \
66  inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
67  protected: \
68  /* Tree-independent data */ \
69  /* Following data always belong to the BV-tree, regardless of what the tree actually contains.*/ \
70  /* Whatever happens we need the two children and the enclosing volume.*/ \
71  volume mBV; /* Global bounding-volume enclosing all the node-related primitives */ \
72  uintptr_t mPos; /* "Positive" child */ \
73  uintptr_t mNeg; /* "Negative" child */
74 #endif
75 
76  typedef void (*CullingCallback) (udword nb_primitives, udword* node_primitives, BOOL need_clipping, void* user_data);
77 
78  class OPCODE_API AABBTreeNode
79  {
80  IMPLEMENT_TREE(AABBTreeNode, AABB)
81  public:
82  // Data access
83  inline_ const udword* GetPrimitives() const { return mNodePrimitives; }
84  inline_ udword GetNbPrimitives() const { return mNbPrimitives; }
85 
86  protected:
87  // Tree-dependent data
88  udword* mNodePrimitives;
89  udword mNbPrimitives;
90  // Internal methods
91  udword Split(udword axis, AABBTreeBuilder* builder);
92  bool Subdivide(AABBTreeBuilder* builder);
93  void _BuildHierarchy(AABBTreeBuilder* builder);
94  void _Refit(AABBTreeBuilder* builder);
95  };
96 
98 
105  typedef bool (*WalkingCallback) (const AABBTreeNode* current, udword depth, void* user_data);
107 
108  class OPCODE_API AABBTree : public AABBTreeNode
109  {
110  public:
111  // Constructor / Destructor
112  AABBTree();
113  ~AABBTree();
114  // Build
115  bool Build(AABBTreeBuilder* builder);
116  void Release();
117 
118  // Data access
119  inline_ const udword* GetIndices() const { return mIndices; }
120  inline_ udword GetNbNodes() const { return mTotalNbNodes; }
121 
122  // Infos
123  bool IsComplete() const;
124  // Stats
125  udword ComputeDepth() const;
126  udword GetUsedBytes() const;
127  udword Walk(WalkingCallback callback, void* user_data) const;
128 
129  bool Refit(AABBTreeBuilder* builder);
130  bool Refit2(AABBTreeBuilder* builder);
131  private:
132  udword* mIndices;
133  AABBTreeNode* mPool;
134  // Stats
135  udword mTotalNbNodes;
136  };
137 
138 #endif // __OPC_AABBTREE_H__