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
|
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
* 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 SIZEOFOBJECT; } \
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 SIZEOFOBJECT; } \
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, AABB)
public:
// Data access
inline_ const dTriIndex* GetPrimitives() const { return mNodePrimitives; }
inline_ udword GetNbPrimitives() const { return mNbPrimitives; }
protected:
// Tree-dependent data
dTriIndex* 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 dTriIndex* 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:
dTriIndex* 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__
|
