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
|
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/*
* 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(baseclass, volume) \
public: \
/* Constructor / Destructor */ \
__forceinline baseclass() : mData(0) {} \
__forceinline ~baseclass() {} \
/* Leaf test */ \
__forceinline BOOL IsLeaf() const { return mData&1; } \
/* Data access */ \
__forceinline const baseclass* GetPos() const { return (baseclass*)mData; } \
__forceinline const baseclass* GetNeg() const { return ((baseclass*)mData)+1; } \
__forceinline udword GetPrimitive() const { return (mData>>1); } \
/* Stats */ \
__forceinline udword GetNodeSize() const { return SIZEOFOBJECT; } \
\
volume mAABB; \
udword mData;
//! Common interface for a node of a no-leaf tree
#define IMPLEMENT_NOLEAF_NODE(baseclass, volume) \
public: \
/* Constructor / Destructor */ \
__forceinline baseclass() : mData(0), mData2(0) {} \
__forceinline ~baseclass() {} \
/* Leaf tests */ \
__forceinline BOOL HasLeaf() const { return mData&1; } \
__forceinline BOOL HasLeaf2() const { return mData2&1; } \
/* Data access */ \
__forceinline const baseclass* GetPos() const { return (baseclass*)mData; } \
__forceinline const baseclass* GetNeg() const { return (baseclass*)mData2; } \
__forceinline udword GetPrimitive() const { return (mData>>1); } \
__forceinline udword GetPrimitive2() const { return (mData2>>1); } \
/* Stats */ \
__forceinline udword GetNodeSize() const { return SIZEOFOBJECT; } \
\
volume mAABB; \
udword mData; \
udword mData2;
class OPCODE_API AABBCollisionNode
{
IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB)
__forceinline float GetVolume() const { return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z; }
__forceinline float GetSize() const { return mAABB.mExtents.SquareMagnitude(); }
__forceinline 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)
__forceinline 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(baseclass, volume) \
public: \
/* Constructor / Destructor */ \
baseclass(); \
virtual ~baseclass(); \
/* Build from a standard tree */ \
virtual bool Build(AABBTree* tree); \
/* Data access */ \
__forceinline const volume* GetNodes() const { return mNodes; } \
/* Stats */ \
virtual udword GetUsedBytes() const { return mNbNodes*sizeof(volume); } \
private: \
volume* mNodes;
class OPCODE_API AABBOptimizedTree
{
public:
// Constructor / Destructor
AABBOptimizedTree() : mNbNodes(0) {}
virtual ~AABBOptimizedTree() {}
// Data access
__forceinline udword GetNbNodes() const { return mNbNodes; }
virtual udword GetUsedBytes() const = 0;
virtual bool Build(AABBTree* tree) = 0;
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__
// END-OF-FILE\n
|
