Vegastrike 0.5.1 rc1  1.0
Original sources for Vegastrike Evolved
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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 
24  #define IMPLEMENT_IMPLICIT_NODE(base_class, volume) \
25  public: \
26  /* Constructor / Destructor */ \
27  inline_ base_class() : mData(0) {} \
28  inline_ ~base_class() {} \
29  /* Leaf test */ \
30  inline_ bool IsLeaf() const { return mData&1; } \
31  /* Data access */ \
32  inline_ const base_class* GetPos() const { return (base_class*)mData; } \
33  inline_ const base_class* GetNeg() const { return ((base_class*)mData)+1; } \
34  inline_ udword GetPrimitive() const { return (udword)(mData>>1); } \
35  /* Stats */ \
36  inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
37  \
38  volume mAABB; \
39  uintptr_t mData;
40 
42  #define IMPLEMENT_NOLEAF_NODE(base_class, volume) \
43  public: \
44  /* Constructor / Destructor */ \
45  inline_ base_class() : mPosData(0), mNegData(0) {} \
46  inline_ ~base_class() {} \
47  /* Leaf tests */ \
48  inline_ bool HasPosLeaf() const { return mPosData&1; } \
49  inline_ bool HasNegLeaf() const { return mNegData&1; } \
50  /* Data access */ \
51  inline_ const base_class* GetPos() const { return (base_class*)mPosData; } \
52  inline_ const base_class* GetNeg() const { return (base_class*)mNegData; } \
53  inline_ udword GetPosPrimitive() const { return (udword)(mPosData>>1); } \
54  inline_ udword GetNegPrimitive() const { return (udword)(mNegData>>1); } \
55  /* Stats */ \
56  inline_ udword GetNodeSize() const { return SIZEOFOBJECT; } \
57  \
58  volume mAABB; \
59  uintptr_t mPosData; \
60  uintptr_t mNegData;
61 
62  class OPCODE_API AABBCollisionNode
63  {
64  IMPLEMENT_IMPLICIT_NODE(AABBCollisionNode, CollisionAABB)
65 
66  inline_ float GetVolume() const { return mAABB.mExtents.x * mAABB.mExtents.y * mAABB.mExtents.z; }
67  inline_ float GetSize() const { return mAABB.mExtents.SquareMagnitude(); }
68  inline_ udword GetRadius() const
69  {
70  udword* Bits = (udword*)&mAABB.mExtents.x;
71  udword Max = Bits[0];
72  if(Bits[1]>Max) Max = Bits[1];
73  if(Bits[2]>Max) Max = Bits[2];
74  return Max;
75  }
76 
77  // NB: using the square-magnitude or the true volume of the box, seems to yield better results
78  // (assuming UNC-like informed traversal methods). I borrowed this idea from PQP. The usual "size"
79  // otherwise, is the largest box extent. In SOLID that extent is computed on-the-fly each time it's
80  // needed (the best approach IMHO). In RAPID the rotation matrix is permuted so that Extent[0] is
81  // always the greatest, which saves looking for it at runtime. On the other hand, it yields matrices
82  // whose determinant is not 1, i.e. you can't encode them anymore as unit quaternions. Not a very
83  // good strategy.
84  };
85 
86  class OPCODE_API AABBQuantizedNode
87  {
88  IMPLEMENT_IMPLICIT_NODE(AABBQuantizedNode, QuantizedAABB)
89 
90  inline_ uword GetSize() const
91  {
92  const uword* Bits = mAABB.mExtents;
93  uword Max = Bits[0];
94  if(Bits[1]>Max) Max = Bits[1];
95  if(Bits[2]>Max) Max = Bits[2];
96  return Max;
97  }
98  // NB: for quantized nodes I don't feel like computing a square-magnitude with integers all
99  // over the place.......!
100  };
101 
102  class OPCODE_API AABBNoLeafNode
103  {
104  IMPLEMENT_NOLEAF_NODE(AABBNoLeafNode, CollisionAABB)
105  };
106 
107  class OPCODE_API AABBQuantizedNoLeafNode
108  {
109  IMPLEMENT_NOLEAF_NODE(AABBQuantizedNoLeafNode, QuantizedAABB)
110  };
111 
113  #define IMPLEMENT_COLLISION_TREE(base_class, node) \
114  public: \
115  /* Constructor / Destructor */ \
116  base_class(); \
117  virtual ~base_class(); \
118  /* Builds from a standard tree */ \
119  override(AABBOptimizedTree) bool Build(AABBTree* tree); \
120  /* Refits the tree */ \
121  override(AABBOptimizedTree) bool Refit(const MeshInterface* mesh_interface); \
122  /* Walks the tree */ \
123  override(AABBOptimizedTree) bool Walk(GenericWalkingCallback callback, void* user_data) const; \
124  /* Data access */ \
125  inline_ const node* GetNodes() const { return mNodes; } \
126  /* Stats */ \
127  override(AABBOptimizedTree) udword GetUsedBytes() const { return mNbNodes*sizeof(node); } \
128  private: \
129  node* mNodes;
130 
131  typedef bool (*GenericWalkingCallback) (const void* current, void* user_data);
132 
133  class OPCODE_API AABBOptimizedTree
134  {
135  public:
136  // Constructor / Destructor
137  AABBOptimizedTree() :
138  mNbNodes (0)
139  {}
140  virtual ~AABBOptimizedTree() {}
141 
143 
148  virtual bool Build(AABBTree* tree) = 0;
150 
152 
157  virtual bool Refit(const MeshInterface* mesh_interface) = 0;
159 
161 
167  virtual bool Walk(GenericWalkingCallback callback, void* user_data) const = 0;
169 
170  // Data access
171  virtual udword GetUsedBytes() const = 0;
172  inline_ udword GetNbNodes() const { return mNbNodes; }
173 
174  protected:
175  udword mNbNodes;
176  };
177 
178  class OPCODE_API AABBCollisionTree : public AABBOptimizedTree
179  {
180  IMPLEMENT_COLLISION_TREE(AABBCollisionTree, AABBCollisionNode)
181  };
182 
183  class OPCODE_API AABBNoLeafTree : public AABBOptimizedTree
184  {
185  IMPLEMENT_COLLISION_TREE(AABBNoLeafTree, AABBNoLeafNode)
186  };
187 
188  class OPCODE_API AABBQuantizedTree : public AABBOptimizedTree
189  {
190  IMPLEMENT_COLLISION_TREE(AABBQuantizedTree, AABBQuantizedNode)
191 
192  public:
193  Point mCenterCoeff;
194  Point mExtentsCoeff;
195  };
196 
197  class OPCODE_API AABBQuantizedNoLeafTree : public AABBOptimizedTree
198  {
199  IMPLEMENT_COLLISION_TREE(AABBQuantizedNoLeafTree, AABBQuantizedNoLeafNode)
200 
201  public:
202  Point mCenterCoeff;
203  Point mExtentsCoeff;
204  };
205 
206 #endif // __OPC_OPTIMIZEDTREE_H__