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