voxelTerrain
 All Classes Functions Variables Typedefs Enumerations Pages
container.hpp
1 #ifndef OCTREE_CONTAINER_HPP
2 #define OCTREE_CONTAINER_HPP
3 
4 #include "blub/core/hashList.hpp"
5 #include "blub/core/hashMap.hpp"
6 #include "blub/core/list.hpp"
7 #include "blub/core/sharedPointer.hpp"
8 #include "blub/math/axisAlignedBoxInt32.hpp"
9 #include "blub/math/vector3.hpp"
10 #include "blub/math/vector3int.hpp"
11 
12 
13 namespace blub
14 {
15 namespace octree
16 {
17 
18 
19 template <typename dataType>
20 class container
21 {
22 public:
23  class node
24  {
25  public:
26  typedef node* t_nodePtr;
27 
28  node(const vector3int32& position, const vector3int32& size)
29  : m_position(position)
30  , m_size(size)
31  {
32  for (int8 ind = 0; ind < 8; ++ind)
33  {
34  m_nodes[ind] = nullptr;
35  }
36  }
37 
38  t_nodePtr getNode(const int32& index) const
39  {
40  BASSERT(index >= 0);
41  BASSERT(index < 8);
42 
43  return m_nodes[index];
44  }
45 
46  bool isInside(const vector3int32& pos) const
47  {
48  return pos >= m_position && pos < (m_position + m_size);
49  }
50 
51  const vector3int32& getPosition(void) const
52  {
53  return m_position;
54  }
55 
56  const vector3int32& getSize(void) const
57  {
58  return m_size;
59  }
60 
61  axisAlignedBoxInt32 getBoundingBox(void) const
62  {
63  return axisAlignedBoxInt32(m_position, m_position + m_size);
64  }
65 
66  protected:
67  friend class container;
68 
69  t_nodePtr m_nodes[8];
70  vector3int32 m_position;
71  vector3int32 m_size;
72  };
73 
74  class leaf : public node
75  {
76  public:
78 
79  leaf(const vector3int32& position, const vector3int32& size)
80  : node(position, size)
81  {
82  ;
83  }
84 
85  const t_dataList& getData() const
86  {
87  return m_data;
88  }
89 
90  protected:
91  friend class container;
92 
93  bool insert(const dataType& toAdd)
94  {
95  BASSERT(m_data.find(toAdd) == m_data.cend());
96  m_data.insert(toAdd);
97  return true;
98  }
99 
100  void remove(const dataType toRemove)
101  {
102  typename t_dataList::const_iterator it = m_data.find(toRemove);
103  BASSERT(it != m_data.cend());
104  m_data.erase(it);
105  }
106 
107  t_dataList m_data;
108 
109  };
110 
111  typedef node* t_nodePtr;
112  typedef leaf* t_leafPtr;
113  typedef dataType t_data;
120 
121 
122  container(const vector3int32& minNodeSize)
123  : m_minNodeSize(minNodeSize)
124  {
125  m_root = new node(-m_minNodeSize, m_minNodeSize*2);
126  }
127 
128  ~container()
129  {
130  destroyNodeAndChildren(m_root);
131  m_root = nullptr;
132  }
133 
134  bool insert(const dataType& data, const vector3& pos)
135  {
136  return insert(data, convertAbsolutVector3PositionToVectorInt32(pos));
137  }
138 
139  bool insert(const dataType& data, const vector3int32& pos)
140  {
141  typename t_dataLeafMap::const_iterator it = m_data.find(data);
142  if (it != m_data.cend())
143  {
144  return false;
145  }
146 
147  BASSERT(m_dataCoords.find(data) == m_dataCoords.cend());
148  m_dataCoords.insert(data, pos);
149 
150  const vector3int32 leafCoords(convertCoordToLeafCoord(pos));
151  // is root large enough?
152  {
153  const vector3int32 leafPosMinAbs(leafCoords*m_minNodeSize);
154  if (!m_root->isInside(leafPosMinAbs))
155  {
156  while (!m_root->isInside(leafPosMinAbs))
157  {
158  t_nodePtr rootCopy(m_root);
159  m_root = new node(rootCopy->getPosition()*2, rootCopy->getSize()*2);
160  for (int32 ind = 0; ind < 8; ++ind)
161  {
162  if (rootCopy->m_nodes[ind] != nullptr)
163  {
164  insertNodeInNode(rootCopy->m_nodes[ind], m_root);
165  }
166  }
167  delete rootCopy;
168  }
169  }
170  }
171 
172  const vector3int32& leafCoord(leafCoords);
173  t_leafPtr workLeaf;
174  {
175  typename t_coordLeafMap::const_iterator itLeaf(m_leafs.find(leafCoord));
176  if (itLeaf != m_leafs.cend())
177  {
178  workLeaf = itLeaf->second;
179  }
180  else
181  {
182  // leaf didn't get found - create it
183  workLeaf = new leaf(leafCoord*m_minNodeSize, m_minNodeSize);
184  insertNodeInNode(workLeaf, m_root);
185  m_leafs.insert(leafCoord, workLeaf);
186  }
187  }
188  BASSERT(workLeaf != nullptr);
189 
190  workLeaf->insert(data);
191  m_data.insert(data, workLeaf);
192 
193  return true;
194  }
195 
196  bool remove(const dataType data)
197  {
198  auto it_range = m_data.equal_range(data);
199  if (it_range.first == it_range.second)
200  {
201  return false;
202  }
203  for (auto it = it_range.first; it != it_range.second; ++it)
204  {
205  it->second->remove(data);
206  }
207  m_data.erase(data);
208  m_dataCoords.erase(data);
209 
210  return true;
211  }
212  bool update(const dataType& data, const vector3int32& updateCoord)
213  {
214  typename t_dataLeafMap::const_iterator it = m_data.find(data);
215  if (it == m_data.cend())
216  {
217  return false;
218  }
219  const t_leafPtr currentLeaf(it->second);
220  if (currentLeaf->isInside(updateCoord)) // same leaf
221  {
222  return false;
223  }
224  if (!remove(data))
225  {
226  return false;
227  }
228  return insert(data, updateCoord);
229  }
230  bool update(const dataType& data, const vector3& updateCoord)
231  {
232  return update(data, convertAbsolutVector3PositionToVectorInt32(updateCoord));
233  }
234 
235  t_nodeList getNodes(const dataType& data)
236  {
237  auto it_range = m_data.equal_range(data);
238  if (it_range.first == it_range.second)
239  {
240  return t_nodeList();
241  }
242  t_nodeList result;
243  for (auto it = it_range.first; it != it_range.second; ++it)
244  {
245  result.insert(it->second);
246  }
247  return result;
248  }
249 
250  void compact()
251  {
252  ; // TODO: impl this meth.
253  }
254 
255  t_nodePtr getRootNode() const
256  {
257  return m_root;
258  }
259 
260  t_leafPtr isLeaf(t_nodePtr nd) const
261  {
262  if (nd->getSize() == getMinNodeSize())
263  {
264  return static_cast<t_leafPtr>(nd);
265  }
266  else
267  {
268  return nullptr;
269  }
270  }
271 
272  const vector3int32& getMinNodeSize() const
273  {
274  return m_minNodeSize;
275  }
276 
277 protected:
278  void destroyNodeAndChildren(t_nodePtr toDestory)
279  {
280  BASSERT(toDestory != nullptr);
281 
282  for (int8 ind = 0; ind < 8; ++ind)
283  {
284  if (toDestory->m_nodes[ind] != nullptr)
285  {
286  destroyNodeAndChildren(toDestory->m_nodes[ind]);
287  toDestory->m_nodes[ind] = nullptr;
288  }
289  }
290  leaf *lf(isLeaf(toDestory));
291  if (lf)
292  {
293  while (!lf->m_data.empty())
294  {
295  #ifdef BLUB_DEBUG
296  const bool resultRemove =
297  #endif
298  remove(*lf->m_data.cbegin());
299  BASSERT(resultRemove);
300  }
301  delete lf;
302  }
303  else
304  {
305  delete toDestory;
306  }
307  }
308 
309  vector3int32 convertCoordToLeafCoord(const vector3int32& coord) const
310  {
311  return convertCoordToLeafCoord(coord, m_minNodeSize);
312  }
313  static vector3int32 convertCoordToLeafCoord(const vector3int32& coord, const vector3int32& size)
314  {
315  vector3int32 result(coord / size);
316  if (coord.x < 0 && coord.x%size.x != 0)
317  {
318  --result.x;
319  }
320  if (coord.y < 0 && coord.y%size.y != 0)
321  {
322  --result.y;
323  }
324  if (coord.z < 0 && coord.z%size.z != 0)
325  {
326  --result.z;
327  }
328  return result;
329  }
330  vector3int32 convertAbsolutVector3PositionToVectorInt32(const vector3& pos) const
331  {
332  const vector3int32 posResult(pos.getFloor());
333  return posResult;
334  }
335 
336  static bool insertNodeInNode(t_nodePtr toInsert, t_nodePtr into)
337  {
338  BASSERT(toInsert != nullptr);
339  BASSERT(into != nullptr);
340 
341  BASSERT(into->isInside(toInsert->getPosition()));
342  BASSERT(into->isInside(toInsert->getPosition() + (toInsert->getSize()-vector3int32(1, 1, 1))));
343 
344  // BASSERT(into->getSize() > m_minNodeSize);
345  BASSERT(into->getSize() > toInsert->getSize());
346 
347  // calc on witch node [0,8] it shall get inserted
348  int32 index;
349  vector3int32 posChild;
350  const vector3int32 intoCenter(into->getPosition() + into->getSize() / 2);
351 
352  if (toInsert->getPosition().x < intoCenter.x &&
353  toInsert->getPosition().y < intoCenter.y &&
354  toInsert->getPosition().z < intoCenter.z)
355  {
356  index = 0;
357  posChild = vector3int32(0, 0, 0);
358  }
359  if (toInsert->getPosition().x >= intoCenter.x &&
360  toInsert->getPosition().y < intoCenter.y &&
361  toInsert->getPosition().z < intoCenter.z)
362  {
363  index = 1;
364  posChild = vector3int32(1, 0, 0);
365  }
366  if (toInsert->getPosition().x < intoCenter.x &&
367  toInsert->getPosition().y >= intoCenter.y &&
368  toInsert->getPosition().z < intoCenter.z)
369  {
370  index = 2;
371  posChild = vector3int32(0, 1, 0);
372  }
373  if (toInsert->getPosition().x >= intoCenter.x &&
374  toInsert->getPosition().y >= intoCenter.y &&
375  toInsert->getPosition().z < intoCenter.z)
376  {
377  index = 3;
378  posChild = vector3int32(1, 1, 0);
379  }
380  if (toInsert->getPosition().x < intoCenter.x &&
381  toInsert->getPosition().y < intoCenter.y &&
382  toInsert->getPosition().z >= intoCenter.z)
383  {
384  index = 4;
385  posChild = vector3int32(0, 0, 1);
386  }
387  if (toInsert->getPosition().x >= intoCenter.x &&
388  toInsert->getPosition().y < intoCenter.y &&
389  toInsert->getPosition().z >= intoCenter.z)
390  {
391  index = 5;
392  posChild = vector3int32(1, 0, 1);
393  }
394  if (toInsert->getPosition().x < intoCenter.x &&
395  toInsert->getPosition().y >= intoCenter.y &&
396  toInsert->getPosition().z >= intoCenter.z)
397  {
398  index = 6;
399  posChild = vector3int32(0, 1, 1);
400  }
401  if (toInsert->getPosition().x >= intoCenter.x &&
402  toInsert->getPosition().y >= intoCenter.y &&
403  toInsert->getPosition().z >= intoCenter.z)
404  {
405  index = 7;
406  posChild = vector3int32(1, 1, 1);
407  }
408 
409  const vector3int32 sizeChild(into->getSize()/2);
410  if (into->m_nodes[index] == nullptr)
411  {
412  if (sizeChild == toInsert->getSize())
413  {
414  into->m_nodes[index] = toInsert;
415  return true;
416  }
417  into->m_nodes[index] = new node(into->getPosition() + posChild*sizeChild, sizeChild);
418  return insertNodeInNode(toInsert, into->m_nodes[index]);
419  }
420  else
421  {
422  return insertNodeInNode(toInsert, into->m_nodes[index]);
423  }
424  }
425 
426 private:
427  const vector3int32 m_minNodeSize;
428 
429  t_nodePtr m_root;
430  t_dataLeafMap m_data;
431  t_dataCoordsMap m_dataCoords;
432  t_coordLeafMap m_leafs;
433 };
434 
435 
436 }
437 }
438 
439 
440 #endif // OCTREE_CONTAINER_HPP
Definition: container.hpp:74
Definition: axisAlignedBoxInt32.hpp:12
Definition: container.hpp:20
Definition: vector3.hpp:26
Definition: container.hpp:23
Definition: deadlineTimer.hpp:10
Definition: customVertexInformation.cpp:177