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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
|
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
* OPCODE - Optimized Collision Detection
* Copyright (C) 2001 Pierre Terdiman
* Homepage: http://www.codercorner.com/Opcode.htm
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Contains code for optimized trees.
* \file OPC_OptimizedTree.h
* \author Pierre Terdiman
* \date March, 20, 2001
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Include Guard
#ifndef __OPC_OPTIMIZEDTREE_H__
#define __OPC_OPTIMIZEDTREE_H__
//! Common interface for a node of an implicit tree
#define IMPLEMENT_IMPLICIT_NODE(base_class, volume) \
public: \
/* Constructor / Destructor */ \
inline_ base_class() : mData(0) {} \
inline_ ~base_class() {} \
/* Leaf test */ \
inline_ BOOL IsLeaf() const { return (mData&1)!=0; } \
/* Data access */ \
inline_ const base_class* GetPos() const { return (base_class*)mData; } \
inline_ const base_class* GetNeg() const { return ((base_class*)mData)+1; } \
inline_ size_t GetPrimitive() const { return (mData>>1); } \
/* Stats */ \
inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
\
volume mAABB; \
size_t mData;
//! Common interface for a node of a no-leaf tree
#define IMPLEMENT_NOLEAF_NODE(base_class, volume) \
public: \
/* Constructor / Destructor */ \
inline_ base_class() : mPosData(0), mNegData(0) {} \
inline_ ~base_class() {} \
/* Leaf tests */ \
inline_ BOOL HasPosLeaf() const { return (mPosData&1)!=0; } \
inline_ BOOL HasNegLeaf() const { return (mNegData&1)!=0; } \
/* Data access */ \
inline_ const base_class* GetPos() const { return (base_class*)mPosData; } \
inline_ const base_class* GetNeg() const { return (base_class*)mNegData; } \
inline_ size_t GetPosPrimitive() const { return (mPosData>>1); } \
inline_ size_t GetNegPrimitive() const { return (mNegData>>1); } \
/* Stats */ \
inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
\
volume mAABB; \
size_t mPosData; \
size_t mNegData;
class OPCODE_API AABBCollisionNode
{
IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB)
inline_ float GetVolume() const { return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z; }
inline_ float GetSize() const { return mAABB.mExtents.SquareMagnitude(); }
inline_ udword GetRadius() const
{
udword* Bits = (udword*)&mAABB.mExtents.x;
udword Max = Bits[0];
if(Bits[1]>Max) Max = Bits[1];
if(Bits[2]>Max) Max = Bits[2];
return Max;
}
// NB: using the square-magnitude or the true volume of the box, seems to yield better results
// (assuming UNC-like informed traversal methods). I borrowed this idea from PQP. The usual "size"
// otherwise, is the largest box extent. In SOLID that extent is computed on-the-fly each time it's
// needed (the best approach IMHO). In RAPID the rotation matrix is permuted so that Extent[0] is
// always the greatest, which saves looking for it at runtime. On the other hand, it yields matrices
// whose determinant is not 1, i.e. you can't encode them anymore as unit quaternions. Not a very
// good strategy.
};
class OPCODE_API AABBQuantizedNode
{
IMPLEMENT_IMPLICIT_NODE(AABBQuantizedNode, QuantizedAABB)
inline_ uword GetSize() const
{
const uword* Bits = mAABB.mExtents;
uword Max = Bits[0];
if(Bits[1]>Max) Max = Bits[1];
if(Bits[2]>Max) Max = Bits[2];
return Max;
}
// NB: for quantized nodes I don't feel like computing a square-magnitude with integers all
// over the place.......!
};
class OPCODE_API AABBNoLeafNode
{
IMPLEMENT_NOLEAF_NODE(AABBNoLeafNode, CollisionAABB)
};
class OPCODE_API AABBQuantizedNoLeafNode
{
IMPLEMENT_NOLEAF_NODE(AABBQuantizedNoLeafNode, QuantizedAABB)
};
//! Common interface for a collision tree
#define IMPLEMENT_COLLISION_TREE(base_class, node) \
public: \
/* Constructor / Destructor */ \
base_class(); \
virtual ~base_class(); \
/* Builds from a standard tree */ \
override(AABBOptimizedTree) bool Build(AABBTree* tree); \
/* Refits the tree */ \
override(AABBOptimizedTree) bool Refit(const MeshInterface* mesh_interface); \
/* Walks the tree */ \
override(AABBOptimizedTree) bool Walk(GenericWalkingCallback callback, void* user_data) const; \
/* Data access */ \
inline_ const node* GetNodes() const { return mNodes; } \
/* Stats */ \
override(AABBOptimizedTree) udword GetUsedBytes() const { return mNbNodes*sizeof(node); } \
private: \
node* mNodes;
typedef bool (*GenericWalkingCallback) (const void* current, void* user_data);
class OPCODE_API AABBOptimizedTree
{
public:
// Constructor / Destructor
AABBOptimizedTree() :
mNbNodes (0)
{}
virtual ~AABBOptimizedTree() {}
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Builds the collision tree from a generic AABB tree.
* \param tree [in] generic AABB tree
* \return true if success
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
virtual bool Build(AABBTree* tree) = 0;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Refits the collision tree after vertices have been modified.
* \param mesh_interface [in] mesh interface for current model
* \return true if success
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
virtual bool Refit(const MeshInterface* mesh_interface) = 0;
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/**
* Walks the tree and call the user back for each node.
* \param callback [in] walking callback
* \param user_data [in] callback's user data
* \return true if success
*/
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
virtual bool Walk(GenericWalkingCallback callback, void* user_data) const = 0;
// Data access
virtual udword GetUsedBytes() const = 0;
inline_ udword GetNbNodes() const { return mNbNodes; }
protected:
udword mNbNodes;
};
class OPCODE_API AABBCollisionTree : public AABBOptimizedTree
{
IMPLEMENT_COLLISION_TREE(AABBCollisionTree, AABBCollisionNode)
};
class OPCODE_API AABBNoLeafTree : public AABBOptimizedTree
{
IMPLEMENT_COLLISION_TREE(AABBNoLeafTree, AABBNoLeafNode)
};
class OPCODE_API AABBQuantizedTree : public AABBOptimizedTree
{
IMPLEMENT_COLLISION_TREE(AABBQuantizedTree, AABBQuantizedNode)
public:
Point mCenterCoeff;
Point mExtentsCoeff;
};
class OPCODE_API AABBQuantizedNoLeafTree : public AABBOptimizedTree
{
IMPLEMENT_COLLISION_TREE(AABBQuantizedNoLeafTree, AABBQuantizedNoLeafNode)
public:
Point mCenterCoeff;
Point mExtentsCoeff;
};
#endif // __OPC_OPTIMIZEDTREE_H__
|
