OPC_OptimizedTree.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_OPTIMIZEDTREE_H__
21 #define __OPC_OPTIMIZEDTREE_H__
22 
23 #if (defined __x86_64) || (defined __aarch64__)
24 #define EXWORD uqword
25 #else
26 #define EXWORD udword
27 #endif
28 
30  #define IMPLEMENT_IMPLICIT_NODE(base_class, volume) \
31  public: \
32  /* Constructor / Destructor */ \
33  inline_ base_class() : mData(0) {} \
34  inline_ ~base_class() {} \
35  /* Leaf test */ \
36  inline_ BOOL IsLeaf() const { return mData&1; } \
37  /* Data access */ \
38  inline_ const base_class* GetPos() const { return (base_class*)mData; } \
39  inline_ const base_class* GetNeg() const { return ((base_class*)mData)+1; } \
40  /* Modified by S-cubed, Inc. */ \
41  inline_ const base_class* GetB() const { return mB; } \
42  inline_ udword GetPrimitive() const { return (mData>>1); } \
43  /* Stats */ \
44  inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
45  \
46  volume mAABB; \
47  EXWORD mData; \
48  /* Modified by S-cubed, Inc. */ \
49  base_class* mB;
50 
52  #define IMPLEMENT_NOLEAF_NODE(base_class, volume) \
53  public: \
54  /* Constructor / Destructor */ \
55  inline_ base_class() : mPosData(0), mNegData(0) {} \
56  inline_ ~base_class() {} \
57  /* Leaf tests */ \
58  inline_ BOOL HasPosLeaf() const { return mPosData&1; } \
59  inline_ BOOL HasNegLeaf() const { return mNegData&1; } \
60  /* Data access */ \
61  inline_ const base_class* GetPos() const { return (base_class*)mPosData; } \
62  inline_ const base_class* GetNeg() const { return (base_class*)mNegData; } \
63  /* Modified by S-cubed, Inc. */ \
64  inline_ const base_class* GetB() const { return mB; } \
65  inline_ udword GetPosPrimitive() const { return (mPosData>>1); } \
66  inline_ udword GetNegPrimitive() const { return (mNegData>>1); } \
67  /* Stats */ \
68  inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
69  \
70  volume mAABB; \
71  EXWORD mPosData; \
72  EXWORD mNegData; \
73  /* Modified by S-cubed, Inc. */ \
74  base_class* mB;
75 
76  class OPCODE_API AABBCollisionNode
77  {
78  IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB)
79 
80  inline_ float GetVolume() const { return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z; }
81  inline_ float GetSize() const { return mAABB.mExtents.SquareMagnitude(); }
82  inline_ udword GetRadius() const
83  {
84  udword* Bits = (udword*)&mAABB.mExtents.x;
85  udword Max = Bits[0];
86  if(Bits[1]>Max) Max = Bits[1];
87  if(Bits[2]>Max) Max = Bits[2];
88  return Max;
89  }
90 
91  // NB: using the square-magnitude or the true volume of the box, seems to yield better results
92  // (assuming UNC-like informed traversal methods). I borrowed this idea from PQP. The usual "size"
93  // otherwise, is the largest box extent. In SOLID that extent is computed on-the-fly each time it's
94  // needed (the best approach IMHO). In RAPID the rotation matrix is permuted so that Extent[0] is
95  // always the greatest, which saves looking for it at runtime. On the other hand, it yields matrices
96  // whose determinant is not 1, i.e. you can't encode them anymore as unit quaternions. Not a very
97  // good strategy.
98  };
99 
100  class OPCODE_API AABBQuantizedNode
101  {
102  IMPLEMENT_IMPLICIT_NODE(AABBQuantizedNode, QuantizedAABB)
103 
104  inline_ uword GetSize() const
105  {
106  const uword* Bits = mAABB.mExtents;
107  uword Max = Bits[0];
108  if(Bits[1]>Max) Max = Bits[1];
109  if(Bits[2]>Max) Max = Bits[2];
110  return Max;
111  }
112  // NB: for quantized nodes I don't feel like computing a square-magnitude with integers all
113  // over the place.......!
114  };
115 
116  class OPCODE_API AABBNoLeafNode
117  {
118  IMPLEMENT_NOLEAF_NODE(AABBNoLeafNode, CollisionAABB)
119  };
120 
121  class OPCODE_API AABBQuantizedNoLeafNode
122  {
123  IMPLEMENT_NOLEAF_NODE(AABBQuantizedNoLeafNode, QuantizedAABB)
124  };
125 
127  #define IMPLEMENT_COLLISION_TREE(base_class, node) \
128  public: \
129  /* Constructor / Destructor */ \
130  base_class(); \
131  virtual ~base_class(); \
132  /* Builds from a standard tree */ \
133  override(AABBOptimizedTree) bool Build(AABBTree* tree); \
134  /* Refits the tree */ \
135  override(AABBOptimizedTree) bool Refit(const MeshInterface* mesh_interface); \
136  /* Walks the tree */ \
137  override(AABBOptimizedTree) bool Walk(GenericWalkingCallback callback, void* user_data) const; \
138  /* Data access */ \
139  inline_ const node* GetNodes() const { return mNodes; } \
140  /* Stats */ \
141  override(AABBOptimizedTree) udword GetUsedBytes() const { return mNbNodes*sizeof(node); } \
142  private: \
143  node* mNodes;
144 
145  typedef bool (*GenericWalkingCallback) (const void* current, void* user_data);
146 
147  class OPCODE_API AABBOptimizedTree
148  {
149  public:
150  // Constructor / Destructor
151  AABBOptimizedTree() :
152  mNbNodes (0)
153  {}
154  virtual ~AABBOptimizedTree() {}
155 
157 
162  virtual bool Build(AABBTree* tree) = 0;
164 
166 
171  virtual bool Refit(const MeshInterface* mesh_interface) = 0;
173 
175 
181  virtual bool Walk(GenericWalkingCallback callback, void* user_data) const = 0;
183 
184  // Data access
185  virtual udword GetUsedBytes() const = 0;
186  inline_ udword GetNbNodes() const { return mNbNodes; }
187 
188  protected:
189  udword mNbNodes;
190  };
191 
192  class OPCODE_API AABBCollisionTree : public AABBOptimizedTree
193  {
194  IMPLEMENT_COLLISION_TREE(AABBCollisionTree, AABBCollisionNode)
195  };
196 
197  class OPCODE_API AABBNoLeafTree : public AABBOptimizedTree
198  {
199  IMPLEMENT_COLLISION_TREE(AABBNoLeafTree, AABBNoLeafNode)
200  };
201 
202  class OPCODE_API AABBQuantizedTree : public AABBOptimizedTree
203  {
204  IMPLEMENT_COLLISION_TREE(AABBQuantizedTree, AABBQuantizedNode)
205 
206  public:
207  Point mCenterCoeff;
208  Point mExtentsCoeff;
209  };
210 
211  class OPCODE_API AABBQuantizedNoLeafTree : public AABBOptimizedTree
212  {
213  IMPLEMENT_COLLISION_TREE(AABBQuantizedNoLeafTree, AABBQuantizedNoLeafNode)
214 
215  public:
216  Point mCenterCoeff;
217  Point mExtentsCoeff;
218  };
219 
220 #endif // __OPC_OPTIMIZEDTREE_H__
AABBCollisionTree
Definition: OPC_OptimizedTree.h:192
IMPLEMENT_NOLEAF_NODE
#define IMPLEMENT_NOLEAF_NODE(base_class, volume)
Common interface for a node of a no-leaf tree.
Definition: OPC_OptimizedTree.h:52
AABBQuantizedNoLeafTree::mExtentsCoeff
Point mExtentsCoeff
Definition: OPC_OptimizedTree.h:217
GenericWalkingCallback
bool(* GenericWalkingCallback)(const void *current, void *user_data)
Definition: OPC_OptimizedTree.h:145
udword
unsigned int udword
sizeof(udword) must be 4
Definition: IceTypes.h:65
AABBQuantizedTree::mExtentsCoeff
Point mExtentsCoeff
Definition: OPC_OptimizedTree.h:208
AABBOptimizedTree::mNbNodes
udword mNbNodes
Definition: OPC_OptimizedTree.h:189
AABBCollisionNode
Definition: OPC_OptimizedTree.h:76
AABBCollisionNode::GetRadius
inline_ udword GetRadius() const
Definition: OPC_OptimizedTree.h:82
IMPLEMENT_IMPLICIT_NODE
#define IMPLEMENT_IMPLICIT_NODE(base_class, volume)
Common interface for a node of an implicit tree.
Definition: OPC_OptimizedTree.h:30
AABBNoLeafNode
Definition: OPC_OptimizedTree.h:116
CollisionAABB
Definition: OPC_Common.h:30
AABBTree
Definition: OPC_AABBTree.h:113
AABBQuantizedTree::mCenterCoeff
Point mCenterCoeff
Definition: OPC_OptimizedTree.h:207
IMPLEMENT_COLLISION_TREE
#define IMPLEMENT_COLLISION_TREE(base_class, node)
Common interface for a collision tree.
Definition: OPC_OptimizedTree.h:127
AABBQuantizedNoLeafNode
Definition: OPC_OptimizedTree.h:121
AABBQuantizedTree
Definition: OPC_OptimizedTree.h:202
AABBCollisionNode::GetSize
inline_ float GetSize() const
Definition: OPC_OptimizedTree.h:81
AABBOptimizedTree
Definition: OPC_OptimizedTree.h:147
AABBOptimizedTree::AABBOptimizedTree
AABBOptimizedTree()
Definition: OPC_OptimizedTree.h:151
AABBQuantizedNoLeafTree::mCenterCoeff
Point mCenterCoeff
Definition: OPC_OptimizedTree.h:216
QuantizedAABB
Definition: OPC_Common.h:105
OPCODE_API
#define OPCODE_API
Definition: Opcode.h:68
AABBQuantizedNoLeafTree
Definition: OPC_OptimizedTree.h:211
Point
Definition: IcePoint.h:25
AABBQuantizedNode
Definition: OPC_OptimizedTree.h:100
MeshInterface
Definition: OPC_MeshInterface.h:53
AABBOptimizedTree::~AABBOptimizedTree
virtual ~AABBOptimizedTree()
Definition: OPC_OptimizedTree.h:154
AABBOptimizedTree::GetNbNodes
inline_ udword GetNbNodes() const
Definition: OPC_OptimizedTree.h:186
inline_
#define inline_
Definition: IcePreprocessor.h:103
uword
unsigned short uword
sizeof(uword) must be 2
Definition: IceTypes.h:63
AABBNoLeafTree
Definition: OPC_OptimizedTree.h:197

openhrp3
Author(s): AIST, General Robotix Inc., Nakamura Lab of Dept. of Mechano Informatics at University of Tokyo
autogenerated on Wed Sep 7 2022 02:51:03