Octree.hpp
Go to the documentation of this file.
1 #ifndef Octree_hpp
2 #define Octree_hpp
3 
4 #include "CellHandle.hh"
5 #include "Location.hh"
6 #include "OctreeTables.hpp"
7 
8 #include <vector>
9 #include <float.h>
10 #include <iostream>
11 
12 //=============================================================================
13 namespace lvr2 {
14 //=============================================================================
15 
25 template <typename BaseVecT, typename BoxT, typename T_CellData>
26 class C_Octree
27 {
28 
29 public:
30  typedef Location::LocCode LocCode;
31  typedef float Scalar;
32 
34  static const int MAX_ROOT_LEVEL = sizeof(LocCode)*8-1;
35 
36  inline C_Octree() { }
37  inline ~C_Octree() { }
38 
40 
41  inline bool is_leaf ( CellHandle _ch ) const;
42  inline bool is_extraction_leaf ( CellHandle _ch ) const;
43  inline bool is_root ( CellHandle _ch ) const;
44  inline int level ( CellHandle _ch ) const;
45  inline int depth ( CellHandle _ch ) const;
46  inline bool is_inner_boundary( CellHandle _ch ) const;
47 
48  int getChildIndex( BaseVecT center, coord<float> *point );
49  int getChildIndex( BaseVecT center, BaseVecT point );
50 
52  void split( CellHandle _ch, const bool bGarbageCollectionOnTheFly=false );
53 
55  inline void SetPickedCell( CellHandle _ch )
56  {
57  m_PickedCell = _ch;
58  }
59 
61  inline void ResetPickedCell()
62  {
63  m_PickedCell = CellHandle();
64  }
65 
67  inline bool PickParentCell()
68  {
69  if (parent(m_PickedCell).is_valid())
70  {
71  m_PickedCell = parent(m_PickedCell);
72  return true;
73  }
74  return false;
75  }
76 
78  inline bool PickChildCell(int _idx)
79  {
80  if (child(m_PickedCell, _idx).is_valid())
81  {
82  m_PickedCell = child(m_PickedCell, _idx);
83  return true;
84  }
85  return false;
86  }
87 
89  inline void ResetNumberOfGeneratedCells() { m_NumberOfGeneratedCells = 1; }
90 
92  inline LocCode SetExtractionLevel(LocCode _level) { return m_ExtractionLevel=_level; }
94 
96 
97  inline CellHandle root() const;
98  inline CellHandle end() const { return CellHandle( size() ); }
100 
102 
103  inline CellHandle parent ( CellHandle _ch ) const;
104  inline CellHandle child ( CellHandle _ch, int _idx ) const;
105  inline CellHandle face_neighbor ( CellHandle _ch, int _idx ) const;
106  inline CellHandle edge_neighbor ( CellHandle _ch, int _idx ) const;
107  inline std::pair<std::vector<CellHandle>, std::vector<uint> > all_corner_neighbors( CellHandle _ch, int _idx ) const;
108  inline CellHandle corner_neighbor( CellHandle _ch, int _idx ) const;
109 
111  void MovePickedCell(int _key, double* _mvm);
112  void MovePickedCellLeft(double* _mvm);
113  void MovePickedCellRight(double* _mvm);
114  void MovePickedCellUp(double* _mvm);
115  void MovePickedCellDown(double* _mvm);
117 
119 
120  inline int size() const;
121  inline int nr_cells() const;
122  inline BaseVecT cell_corner( CellHandle _ch, int _idx ) const
123  {
124  Scalar x, y, z;
125  cell_corner( _ch, _idx, x, y, z );
126  BaseVecT point;
127  point[0] = x;
128  point[1] = y;
129  point[2] = z;
130  return point;
131  }
132  inline void cell_corner( CellHandle _ch,
133  Scalar & _x, Scalar & _y, Scalar & _z, Scalar & _size ) const;
134  inline void cell_corner( CellHandle _ch, int _idx,
135  Scalar & _x, Scalar & _y, Scalar & _z ) const;
136  inline void cell_corner( CellHandle _ch, int _idx,
137  Scalar & _x, Scalar & _y, Scalar & _z, Scalar & _size ) const;
138  inline BaseVecT cell_center( CellHandle _ch ) const
139  {
140  Scalar x, y, z;
141  cell_center( _ch, x, y, z );
142  BaseVecT point;
143  point[0] = x;
144  point[1] = y;
145  point[2] = z;
146  return point;
147  }
148  inline void cell_center( CellHandle _ch,
149  Scalar & _x, Scalar & _y, Scalar & _z ) const;
150  inline void cell_center( CellHandle _ch,
151  Scalar & _x, Scalar & _y, Scalar & _z, Scalar & _size ) const;
152  inline Scalar cell_size( CellHandle _ch ) const
153  {
154  const Location & locinfo = location( _ch );
155  LocCode binary_cell_size = 1 << locinfo.level();
156  return binary_cell_size;
157  }
158  Location & location( CellHandle _h )
159  {
160  return m_OctreeCell[_h.idx()].location;
161  }
162  const Location & location( CellHandle _h ) const
163  {
164  return m_OctreeCell[_h.idx()].location;
165  }
166  inline CellHandle cell( Scalar _x, Scalar _y, Scalar _z ) const;
167 
169  inline CellHandle GetPickedCell() const { return m_PickedCell; }
170 
172  inline int GetNumberOfGeneratedCells() const { return m_NumberOfGeneratedCells; }
173 
175  inline LocCode GetExtractionLevel() const { return m_ExtractionLevel; }
177 
179 
180  inline void reserve( unsigned int _size );
181  inline void resize ( unsigned int _size );
182 
184  void initialize( int _max_octree_level )
185  {
186  // Security check...
187  if ( _max_octree_level > MAX_ROOT_LEVEL )
188  {
189  fprintf( stderr, "Error: octree::initialize(): invalid root level\n" );
190  exit( EXIT_FAILURE );
191  }
192 
193  m_rootLevel = _max_octree_level;
194 
195  clear();
196  }
197 
198  inline void clear()
199  {
200  // clear cell vector
201  std::vector<T_CellData>().swap(m_OctreeCell);
202 
203  // 7 dummies and...
204  T_CellData dummy;
205  for (size_t i=0; i<7; ++i) m_OctreeCell.push_back( dummy );
206 
207  // ...the root cell at the beginning
208  dummy.location = Location( 0, 0, 0, m_rootLevel, CellHandle() );
209  m_OctreeCell.push_back( dummy );
210 
211  // Initialize the pointer to the next free block
212  m_nextFreeBlock = 8;
213 
214  // Reset the number of generated cells
215  ResetNumberOfGeneratedCells();
216 
217  // Reset the leaf-level
218  m_ExtractionLevel=0;
219  }
221 
222 protected:
223  inline int cell( int _i ) const
224  {
225  return m_OctreeCell[ _i ].next;
226  }
227 
228  inline void set_cell( int _i, int _cell )
229  {
230  m_OctreeCell[ _i ].next = _cell;
231  }
232 
233  inline CellHandle traverse( CellHandle _ch, LocCode _loc_x, LocCode _loc_y, LocCode _loc_z ) const;
234  inline CellHandle traverse_to_level( CellHandle _ch, LocCode _loc_x, LocCode _loc_y, LocCode _loc_z, LocCode _level ) const;
235 
236  inline CellHandle get_common_ancestor( CellHandle _ch, LocCode _diff ) const;
237  inline CellHandle get_common_ancestor( CellHandle _ch, LocCode _diff0, LocCode _diff1 ) const;
238  inline CellHandle get_common_ancestor( CellHandle _ch, LocCode _diff0, LocCode _diff1, LocCode _diff2 ) const;
239 
240  // ==================================================================================================== \/
241  // ============================================================================================= FIELDS \/
242  // ==================================================================================================== \/
243 protected:
244 
246  LocCode m_rootLevel;
247 
249  size_t m_nextFreeBlock;
250 
252  CellHandle m_PickedCell;
253 
255  int m_NumberOfGeneratedCells;
256 
258  LocCode m_ExtractionLevel;
259 
260 public:
262  std::vector<T_CellData> m_OctreeCell;
263 };
264 
265 template <typename BaseVecT, typename BoxT, typename T_CellData>
266 void C_Octree< BaseVecT, BoxT, T_CellData >::reserve( unsigned int _size )
267 {
268  m_OctreeCell.reserve( _size );
269 }
270 
271 //-----------------------------------------------------------------------------
272 
273 template <typename BaseVecT, typename BoxT, typename T_CellData>
274 void C_Octree< BaseVecT, BoxT, T_CellData >::resize( unsigned int _size )
275 {
276  m_OctreeCell.resize( _size );
277 }
278 
279 //-----------------------------------------------------------------------------
280 
281 template <typename BaseVecT, typename BoxT, typename T_CellData>
282 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::child( CellHandle _ch, int _idx ) const
283 {
284  return CellHandle( m_OctreeCell[ _ch.idx() ].next + _idx );
285 }
286 
287 //-----------------------------------------------------------------------------
288 
289 template <typename BaseVecT, typename BoxT, typename T_CellData>
290 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::parent( CellHandle _ch ) const
291 {
292  return location( _ch ).parent();
293 }
294 
295 //-----------------------------------------------------------------------------
296 
297 template <typename BaseVecT, typename BoxT, typename T_CellData>
298 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::root() const
299 {
300  return CellHandle( 7 );
301 }
302 
303 //-----------------------------------------------------------------------------
304 
305 template <typename BaseVecT, typename BoxT, typename T_CellData>
306 bool C_Octree< BaseVecT, BoxT, T_CellData >::is_leaf( CellHandle _ch ) const
307 {
308  return (m_OctreeCell[ _ch.idx() ].next<0);
309 }
310 
311 //-----------------------------------------------------------------------------
312 
313 template <typename BaseVecT, typename BoxT, typename T_CellData>
314 bool C_Octree< BaseVecT, BoxT, T_CellData >::is_extraction_leaf( CellHandle _ch ) const
315 {
316  return ((m_OctreeCell[ _ch.idx() ].next<0) || (level(_ch)==m_ExtractionLevel));
317 }
318 
319 //-----------------------------------------------------------------------------
320 
321 template <typename BaseVecT, typename BoxT, typename T_CellData>
322 bool C_Octree< BaseVecT, BoxT, T_CellData >::is_root( CellHandle _ch ) const
323 {
324  return _ch.idx() == 7;
325 }
326 
327 //-----------------------------------------------------------------------------
328 
329 template <typename BaseVecT, typename BoxT, typename T_CellData>
330 void C_Octree< BaseVecT, BoxT, T_CellData >::cell_corner( CellHandle _ch, Scalar & _x, Scalar & _y, Scalar & _z, Scalar & _size ) const
331 {
332  const Location & locinfo = location( _ch );
333 
334  LocCode binary_cell_size = 1 << locinfo.level();
335 
336  _size = ( Scalar ) binary_cell_size;
337  _x = ( Scalar ) locinfo.loc_x();
338  _y = ( Scalar ) locinfo.loc_y();
339  _z = ( Scalar ) locinfo.loc_z();
340 }
341 
342 //-----------------------------------------------------------------------------
343 
344 template <typename BaseVecT, typename BoxT, typename T_CellData>
345 void C_Octree< BaseVecT, BoxT, T_CellData >::cell_center( CellHandle _ch, Scalar & _x, Scalar & _y, Scalar & _z ) const
346 {
347  const Location & locinfo = location( _ch );
348  LocCode binary_cell_size = 1 << locinfo.level();
349 
350  Scalar size = ( Scalar ) binary_cell_size;
351 
352  _x = ( Scalar ) locinfo.loc_x() + ( Scalar ) 0.5 * size;
353  _y = ( Scalar ) locinfo.loc_y() + ( Scalar ) 0.5 * size;
354  _z = ( Scalar ) locinfo.loc_z() + ( Scalar ) 0.5 * size;
355 }
356 
357 //-----------------------------------------------------------------------------
358 
359 template <typename BaseVecT, typename BoxT, typename T_CellData>
360 void C_Octree< BaseVecT, BoxT, T_CellData >::cell_center( CellHandle _ch, Scalar & _x, Scalar & _y, Scalar & _z, Scalar & _s ) const
361 {
362  const Location & locinfo = location( _ch );
363  LocCode binary_cell_size = 1 << locinfo.level();
364 
365  _s = ( Scalar ) binary_cell_size;
366 
367  _x = ( Scalar ) locinfo.loc_x() + ( Scalar ) 0.5 * _s;
368  _y = ( Scalar ) locinfo.loc_y() + ( Scalar ) 0.5 * _s;
369  _z = ( Scalar ) locinfo.loc_z() + ( Scalar ) 0.5 * _s;
370 }
371 
372 //-----------------------------------------------------------------------------
373 
374 template <typename BaseVecT, typename BoxT, typename T_CellData>
375 void C_Octree< BaseVecT, BoxT, T_CellData >::cell_corner( CellHandle _ch, int _idx, Scalar & _x, Scalar & _y, Scalar & _z, Scalar & _size ) const
376 {
377  const Location & locinfo = location( _ch );
378 
379  LocCode binary_cell_size = 1 << locinfo.level();
380 
381  _size = ( Scalar ) binary_cell_size;
382  _x = ( Scalar ) locinfo.loc_x();
383  _y = ( Scalar ) locinfo.loc_y();
384  _z = ( Scalar ) locinfo.loc_z();
385 
386  switch ( _idx )
387  {
388  case 0 : break;
389  case 1 : _x += _size; break;
390  case 2 : _y += _size; break;
391  case 3 : _x += _size; _y += _size; break;
392  case 4 : _z += _size; break;
393  case 5 : _x += _size; _z += _size; break;
394  case 6 : _y += _size; _z += _size; break;
395  case 7 : _x += _size; _y += _size; _z += _size; break;
396  }
397 }
398 
399 //-----------------------------------------------------------------------------
400 
401 template <typename BaseVecT, typename BoxT, typename T_CellData>
402 void C_Octree< BaseVecT, BoxT, T_CellData >::cell_corner( CellHandle _ch, int _idx, Scalar & _x, Scalar & _y, Scalar & _z ) const
403 {
404  const Location & locinfo = location( _ch );
405 
406  LocCode binary_cell_size = 1 << locinfo.level();
407 
408  Scalar size = ( Scalar ) binary_cell_size;
409  _x = ( Scalar ) locinfo.loc_x();
410  _y = ( Scalar ) locinfo.loc_y();
411  _z = ( Scalar ) locinfo.loc_z();
412 
413  switch ( _idx )
414  {
415  case 0 : break;
416  case 1 : _x += size; break;
417  case 2 : _y += size; break;
418  case 3 : _x += size; _y += size; break;
419  case 4 : _z += size; break;
420  case 5 : _x += size; _z += size; break;
421  case 6 : _y += size; _z += size; break;
422  case 7 : _x += size; _y += size; _z += size; break;
423  }
424 }
425 
426 //-----------------------------------------------------------------------------
427 
428 template <typename BaseVecT, typename BoxT, typename T_CellData>
429 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::traverse(
430  CellHandle _ch,
431  LocCode _loc_x,
432  LocCode _loc_y,
433  LocCode _loc_z ) const
434 {
435  LocCode next_level = location( _ch ).level() - 1;
436 
437  while ( ! is_leaf( _ch ) )
438  {
439  LocCode child_branch_bit = 1 << next_level;
440  unsigned int child_index =
441  ( ( _loc_x & child_branch_bit ) >> ( next_level ) ) +
442  2 * ( ( _loc_y & child_branch_bit ) >> ( next_level ) ) +
443  4 * ( ( _loc_z & child_branch_bit ) >> ( next_level ) );
444  --next_level;
445  _ch = child( _ch, child_index );
446  }
447 
448  return _ch;
449 }
450 
451 //-----------------------------------------------------------------------------
452 
453 template <typename BaseVecT, typename BoxT, typename T_CellData>
454 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::traverse_to_level(
455  CellHandle _ch,
456  LocCode _loc_x,
457  LocCode _loc_y,
458  LocCode _loc_z,
459  LocCode _level ) const
460 {
461  LocCode next_level = level( _ch ) - 1;
462 
463  LocCode n = next_level - _level + 1;
464 
465  while ( n-- )
466  {
467  LocCode child_branch_bit = 1 << next_level;
468  unsigned int child_index =
469  1 * ( ( _loc_x & child_branch_bit ) >> ( next_level ) ) +
470  2 * ( ( _loc_y & child_branch_bit ) >> ( next_level ) ) +
471  4 * ( ( _loc_z & child_branch_bit ) >> ( next_level ) );
472  --next_level;
473  _ch = child( _ch, child_index );
474 
475  if ( is_leaf( _ch ) ) break;
476  }
477 
478  return _ch;
479 }
480 
481 //-----------------------------------------------------------------------------
482 
483 template <typename BaseVecT, typename BoxT, typename T_CellData>
484 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::face_neighbor( CellHandle _ch, int _idx ) const
485 {
486  const Location & locinfo = location( _ch );
487  const LocCode loc_x = locinfo.loc_x();
488  const LocCode loc_y = locinfo.loc_y();
489  const LocCode loc_z = locinfo.loc_z();
490  //std::cout << "Loc: " << locinfo.level() << " " << std::endl;
491  const LocCode binary_cell_size = ((int)1) << locinfo.level();
492 
493  LocCode new_loc_x = loc_x;
494  LocCode new_loc_y = loc_y;
495  LocCode new_loc_z = loc_z;
496  LocCode diff = 0;
497 
498  switch ( _idx )
499  {
500  case 0: // right
501  if ( loc_x + binary_cell_size >= ( 1 << m_rootLevel ) ) return CellHandle();
502  new_loc_x = loc_x + binary_cell_size;
503  diff = loc_x ^ new_loc_x;
504  break;
505 
506  case 1: // top
507  if ( loc_y + binary_cell_size >= ( 1 << m_rootLevel ) ) return CellHandle();
508  new_loc_y = loc_y + binary_cell_size;
509  diff = loc_y ^ new_loc_y;
510  break;
511 
512  case 2: // front
513  if ( loc_z + binary_cell_size >= ( 1 << m_rootLevel ) ) return CellHandle();
514  new_loc_z = loc_z + binary_cell_size;
515  diff = loc_z ^ new_loc_z;
516  break;
517 
518  case 3: // back
519  if ( loc_z == 0 ) return CellHandle();
520  new_loc_z = loc_z - 1;
521  diff = loc_z ^ new_loc_z;
522  break;
523 
524  case 4: // bottom
525  if ( loc_y == 0 ) return CellHandle();
526  new_loc_y = loc_y - 1;
527  diff = loc_y ^ new_loc_y;
528  break;
529 
530  case 5: // left
531  if ( loc_x == 0 ) return CellHandle();
532  new_loc_x = loc_x - 1;
533  diff = loc_x ^ new_loc_x;
534  break;
535  }
536 
537  CellHandle parent = get_common_ancestor( _ch, diff );
538 
539  return traverse_to_level( parent, new_loc_x, new_loc_y, new_loc_z, locinfo.level() );
540 }
541 
542 //-----------------------------------------------------------------------------
543 
544 template <typename BaseVecT, typename BoxT, typename T_CellData>
545 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::get_common_ancestor( CellHandle _ch, LocCode _binary_diff ) const
546 {
547  LocCode cell_level = level( _ch );
548 
549  while ( _binary_diff & ( 1 << cell_level ) )
550  {
551  _ch = parent( _ch );
552  ++cell_level;
553  }
554 
555  return _ch;
556 }
557 
558 //-----------------------------------------------------------------------------
559 
560 template <typename BaseVecT, typename BoxT, typename T_CellData>
561 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::get_common_ancestor(
562  CellHandle _ch,
563  LocCode _binary_diff0,
564  LocCode _binary_diff1 ) const
565 {
566  LocCode cell_level = level( _ch );
567 
568  while ( _binary_diff0 & _binary_diff1 & ( 1 << cell_level ) )
569  {
570  _ch = parent( _ch );
571  ++cell_level;
572  }
573 
574  if ( _binary_diff0 & ( 1 << cell_level ) )
575  while ( _binary_diff0 & ( 1 << cell_level ) )
576  {
577  _ch = parent( _ch );
578  ++cell_level;
579  }
580  else
581  while ( _binary_diff1 & ( 1 << cell_level ) )
582  {
583  _ch = parent( _ch );
584  ++cell_level;
585  }
586 
587  return _ch;
588 }
589 
590 //-----------------------------------------------------------------------------
591 
592 template <typename BaseVecT, typename BoxT, typename T_CellData>
593 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::get_common_ancestor(
594  CellHandle _ch,
595  LocCode _binary_diff0,
596  LocCode _binary_diff1,
597  LocCode _binary_diff2 ) const
598 {
599  return CellHandle( 0 );
600 }
601 
602 //-----------------------------------------------------------------------------
603 
604 template <typename BaseVecT, typename BoxT, typename T_CellData>
605 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::edge_neighbor( CellHandle _ch, int _idx ) const
606 {
607  const Location & locinfo = location( _ch );
608 
609  LocCode loc_x = locinfo.loc_x();
610  LocCode loc_y = locinfo.loc_y();
611  LocCode loc_z = locinfo.loc_z();
612 
613  LocCode binary_cell_size = 1 << locinfo.level();
614 
615  LocCode new_loc_x = loc_x;
616  LocCode new_loc_y = loc_y;
617  LocCode new_loc_z = loc_z;
618 
619  int extent = ( 1 << m_rootLevel );
620 
621  switch ( _idx )
622  {
623  case 0 :
624  {
625  if ( loc_y == 0 ) return CellHandle();
626  if ( loc_z == 0 ) return CellHandle();
627  new_loc_y = loc_y - 1;
628  new_loc_z = loc_z - 1;
629  break;
630  }
631  case 1 :
632  {
633  if ( loc_x == 0 ) return CellHandle();
634  if ( loc_z == 0 ) return CellHandle();
635  new_loc_x = loc_x - 1;
636  new_loc_z = loc_z - 1;
637  break;
638  }
639  case 2 :
640  {
641  if ( loc_x == 0 ) return CellHandle();
642  if ( loc_y == 0 ) return CellHandle();
643  new_loc_x = loc_x - 1;
644  new_loc_y = loc_y - 1;
645  break;
646  }
647  case 3 :
648  {
649  if ( loc_x + binary_cell_size >= extent ) return CellHandle();
650  if ( loc_z == 0 ) return CellHandle();
651  new_loc_x = loc_x + binary_cell_size;
652  new_loc_z = loc_z - 1;
653  break;
654  }
655  case 4 :
656  {
657  if ( loc_x == 0 ) return CellHandle();
658  if ( loc_y + binary_cell_size >= extent ) return CellHandle();
659  new_loc_x = loc_x - 1;
660  new_loc_y = loc_y + binary_cell_size;
661  break;
662  }
663  case 5 :
664  {
665  if ( loc_y == 0 ) return CellHandle();
666  if ( loc_z + binary_cell_size >= extent ) return CellHandle();
667  new_loc_y = loc_y - 1;
668  new_loc_z = loc_z + binary_cell_size;
669  break;
670  }
671  case 6 :
672  {
673  if ( loc_y + binary_cell_size >= extent ) return CellHandle();
674  if ( loc_z == 0 ) return CellHandle();
675  new_loc_y = loc_y + binary_cell_size;
676  new_loc_z = loc_z - 1;
677  break;
678  }
679  case 7 :
680  {
681  if ( loc_x + binary_cell_size >= extent ) return CellHandle();
682  if ( loc_y == 0 ) return CellHandle();
683  new_loc_x = loc_x + binary_cell_size;
684  new_loc_y = loc_y - 1;
685  break;
686  }
687  case 8 :
688  {
689  if ( loc_x == 0 ) return CellHandle();
690  if ( loc_z + binary_cell_size >= extent ) return CellHandle();
691  new_loc_x = loc_x - 1;
692  new_loc_z = loc_z + binary_cell_size;
693  break;
694  }
695  case 9 :
696  {
697  if ( loc_x + binary_cell_size >= extent ) return CellHandle();
698  if ( loc_y + binary_cell_size >= extent ) return CellHandle();
699  new_loc_x = loc_x + binary_cell_size;
700  new_loc_y = loc_y + binary_cell_size;
701  break;
702  }
703  case 10 :
704  {
705  if ( loc_x + binary_cell_size >= extent ) return CellHandle();
706  if ( loc_z + binary_cell_size >= extent ) return CellHandle();
707  new_loc_x = loc_x + binary_cell_size;
708  new_loc_z = loc_z + binary_cell_size;
709  break;
710  }
711  case 11 :
712  {
713  if ( loc_y + binary_cell_size >= extent ) return CellHandle();
714  if ( loc_z + binary_cell_size >= extent ) return CellHandle();
715  new_loc_y = loc_y + binary_cell_size;
716  new_loc_z = loc_z + binary_cell_size;
717  break;
718  }
719 
720  }
721 
722  CellHandle parent = root();
723 
724  return traverse_to_level( parent, new_loc_x, new_loc_y, new_loc_z, locinfo.level() );
725 }
726 
727 //-----------------------------------------------------------------------------
728 
729 template <typename BaseVecT, typename BoxT, typename T_CellData>
730 std::pair<std::vector<CellHandle>, std::vector<uint> > C_Octree< BaseVecT, BoxT, T_CellData >::all_corner_neighbors(CellHandle _ch, int _idx) const
731 {
732  std::vector<CellHandle> cellHandles;
733  std::vector<uint> markers;
734  std::vector<Location*> locations;
735 
736  // get lower left back corner of given cell
737  Location locinfo = location( _ch );
738  LocCode loc_x = locinfo.loc_x();
739  LocCode loc_y = locinfo.loc_y();
740  LocCode loc_z = locinfo.loc_z();
741  LocCode binary_cell_size = 1 << locinfo.level();
742  int extent = ( 1 << m_rootLevel );
743 
744  // shift loc_x, loc_y, loc_z to corresponding corner position
745  LocCode loc_X = loc_x + binary_cell_size * octreeVertexTable[_idx][0];
746  LocCode loc_Y = loc_y + binary_cell_size * octreeVertexTable[_idx][1];
747  LocCode loc_Z = loc_z + binary_cell_size * octreeVertexTable[_idx][2];
748 
749  // calculate the corner positions
750  for(unsigned char i = 0; i < 8; i++)
751  {
752  // marker is binary code for detailed overhang position
753  // z-axis-overhang y-axis-overhang x-axis-overhang
754  uint marker = 0;
755 
756  int new_loc_x = loc_X;
757  int new_loc_y = loc_Y;
758  int new_loc_z = loc_Z;
759 
760  new_loc_x = loc_X + octreeCornerNeighborTable[i][0];
761  if ( new_loc_x >= extent || new_loc_x < 0 )
762  {
763  new_loc_x = loc_x;
764  marker = 1;
765  }
766 
767  new_loc_y = loc_Y + octreeCornerNeighborTable[i][1];
768  if ( new_loc_y >= extent || new_loc_y < 0 )
769  {
770  new_loc_y = loc_y;
771  marker |= 1 << 1;
772  }
773 
774  new_loc_z = loc_Z + octreeCornerNeighborTable[i][2];
775  if ( new_loc_z >= extent || new_loc_z < 0 )
776  {
777  new_loc_z = loc_z;
778  marker |= 1 << 2;
779  }
780 
781  locations.push_back(new Location(new_loc_x, new_loc_y, new_loc_z, locinfo.level() + 1, locinfo.parent()));
782  markers.push_back(marker);
783  }
784 
785  for(Location * location : locations)
786  {
787  cellHandles.push_back(traverse(root(), location->loc_x(), location->loc_y(), location->loc_z()));
788  delete location;
789  }
790  locations.clear();
791  std::vector<Location*>().swap(locations);
792 
793  return make_pair(cellHandles, markers);
794 }
795 
796 //-----------------------------------------------------------------------------
797 
798 template <typename BaseVecT, typename BoxT, typename T_CellData>
799 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::corner_neighbor( CellHandle _ch, int _idx ) const
800 {
801  const Location & locinfo = location( _ch );
802 
803  LocCode loc_x = locinfo.loc_x();
804  LocCode loc_y = locinfo.loc_y();
805  LocCode loc_z = locinfo.loc_z();
806 
807  LocCode binary_cell_size = 1 << locinfo.level();
808 
809  LocCode new_loc_x = loc_x;
810  LocCode new_loc_y = loc_y;
811  LocCode new_loc_z = loc_z;
812 
813  int extent = ( 1 << m_rootLevel );
814 
815  switch ( _idx )
816  {
817  case 0 :
818  {
819  if ( loc_x == 0 ) return CellHandle();
820  if ( loc_y == 0 ) return CellHandle();
821  if ( loc_z == 0 ) return CellHandle();
822  new_loc_x = loc_x - 1;
823  new_loc_y = loc_y - 1;
824  new_loc_z = loc_z - 1;
825  break;
826  }
827  case 1 :
828  {
829  if ( loc_x + binary_cell_size >= extent ) return CellHandle();
830  if ( loc_y == 0 ) return CellHandle();
831  if ( loc_z == 0 ) return CellHandle();
832  new_loc_x = loc_x + binary_cell_size;
833  new_loc_y = loc_y - 1;
834  new_loc_z = loc_z - 1;
835  break;
836  }
837  case 2 :
838  {
839  if ( loc_x == 0 ) return CellHandle();
840  if ( loc_y + binary_cell_size >= extent ) return CellHandle();
841  if ( loc_z == 0 ) return CellHandle();
842  new_loc_x = loc_x - 1;
843  new_loc_y = loc_y + binary_cell_size;
844  new_loc_z = loc_z - 1;
845  break;
846  }
847  case 3 :
848  {
849  if ( loc_x + binary_cell_size >= extent ) return CellHandle();
850  if ( loc_y + binary_cell_size >= extent ) return CellHandle();
851  if ( loc_z == 0 ) return CellHandle();
852  new_loc_x = loc_x + binary_cell_size;
853  new_loc_y = loc_y + binary_cell_size;
854  new_loc_z = loc_z - 1;
855  break;
856  }
857  case 4 :
858  {
859  if ( loc_x == 0 ) return CellHandle();
860  if ( loc_y == 0 ) return CellHandle();
861  if ( loc_z + binary_cell_size >= extent ) return CellHandle();
862  new_loc_x = loc_x - 1;
863  new_loc_y = loc_y - 1;
864  new_loc_z = loc_z + binary_cell_size;
865  break;
866  }
867  case 5 :
868  {
869  if ( loc_x + binary_cell_size >= extent ) return CellHandle();
870  if ( loc_y == 0 ) return CellHandle();
871  if ( loc_z + binary_cell_size >= extent ) return CellHandle();
872  new_loc_x = loc_x + binary_cell_size;
873  new_loc_y = loc_y - 1;
874  new_loc_z = loc_z + binary_cell_size;
875  break;
876  }
877  case 6 :
878  {
879  if ( loc_x == 0 ) return CellHandle();
880  if ( loc_y + binary_cell_size >= extent ) return CellHandle();
881  if ( loc_z + binary_cell_size >= extent ) return CellHandle();
882  new_loc_x = loc_x - 1;
883  new_loc_y = loc_y + binary_cell_size;
884  new_loc_z = loc_z + binary_cell_size;
885  break;
886  }
887  case 7 :
888  {
889  if ( loc_x + binary_cell_size >= extent ) return CellHandle();
890  if ( loc_y + binary_cell_size >= extent ) return CellHandle();
891  if ( loc_z + binary_cell_size >= extent ) return CellHandle();
892  new_loc_x = loc_x + binary_cell_size;
893  new_loc_y = loc_y + binary_cell_size;
894  new_loc_z = loc_z + binary_cell_size;
895  break;
896  }
897  }
898 
899  CellHandle parent = root();
900 
901  return traverse_to_level( parent, new_loc_x, new_loc_y, new_loc_z, locinfo.level() );
902 }
903 
904 //-----------------------------------------------------------------------------
905 
906 template <typename BaseVecT, typename BoxT, typename T_CellData>
907 int C_Octree< BaseVecT, BoxT, T_CellData >::level( CellHandle _ch ) const
908 {
909  return location( _ch ).level();
910 }
911 
912 //-----------------------------------------------------------------------------
913 
914 template <typename BaseVecT, typename BoxT, typename T_CellData>
915 int C_Octree< BaseVecT, BoxT, T_CellData >::depth( CellHandle _ch ) const
916 {
917  return m_rootLevel - level( _ch );
918 }
919 
920 //-----------------------------------------------------------------------------
921 
922 template <typename BaseVecT, typename BoxT, typename T_CellData>
923 int C_Octree< BaseVecT, BoxT, T_CellData >::size() const
924 {
925  return m_OctreeCell.size();
926 }
927 
928 //-----------------------------------------------------------------------------
929 
930 template <typename BaseVecT, typename BoxT, typename T_CellData>
931 int C_Octree< BaseVecT, BoxT, T_CellData >::nr_cells() const
932 {
933  // #cells ~ #elements in the m_OctreeCell vector minus 7 dummies at the beginning
934  return m_OctreeCell.size()-7;
935 }
936 
937 //-----------------------------------------------------------------------------
938 
939 template <typename BaseVecT, typename BoxT, typename T_CellData>
940 bool C_Octree< BaseVecT, BoxT, T_CellData >::is_inner_boundary( CellHandle _ch ) const
941 {
942  const Location & locinfo = location( _ch );
943 
944  LocCode loc_x = locinfo.loc_x();
945  LocCode loc_y = locinfo.loc_y();
946  LocCode loc_z = locinfo.loc_z();
947 
948  LocCode binary_cell_size = 1 << locinfo.level();
949 
950  LocCode tree_size = 1 << m_rootLevel;
951 
952  return ( loc_x == 0 ||
953  loc_y == 0 ||
954  loc_z == 0 ||
955  loc_x + binary_cell_size == tree_size ||
956  loc_y + binary_cell_size == tree_size ||
957  loc_z + binary_cell_size == tree_size );
958 }
959 
960 //-----------------------------------------------------------------------------
961 
962 template <typename BaseVecT, typename BoxT, typename T_CellData>
963 CellHandle C_Octree< BaseVecT, BoxT, T_CellData >::cell( Scalar _x, Scalar _y, Scalar _z ) const
964 {
965  if ( _x < 0 ) return CellHandle();
966  if ( _y < 0 ) return CellHandle();
967  if ( _z < 0 ) return CellHandle();
968 
969  Scalar extent( 1 << m_rootLevel );
970 
971  if ( _x > extent ) return CellHandle();
972  if ( _y > extent ) return CellHandle();
973  if ( _z > extent ) return CellHandle();
974 
975  CellHandle ch = root();
976 
977  while ( ! is_leaf( ch ) )
978  {
979  Scalar cx, cy, cz;
980  cell_center( ch, cx, cy, cz );
981 
982  unsigned int cidx = ( _x < cx ? 0 : 1 )
983  + ( _y < cy ? 0 : 2 )
984  + ( _z < cz ? 0 : 4 );
985  ch = child( ch, cidx );
986  }
987 
988  return ch;
989 }
990 
991 //-----------------------------------------------------------------------------
992 
993 template <typename BaseVecT, typename BoxT, typename T_CellData>
994 void C_Octree< BaseVecT, BoxT, T_CellData >::MovePickedCellLeft(double* _mvm)
995 {
996  MovePickedCell(0, _mvm);
997 }
998 
999 //-----------------------------------------------------------------------------
1000 
1001 template <typename BaseVecT, typename BoxT, typename T_CellData>
1002 void C_Octree< BaseVecT, BoxT, T_CellData >::MovePickedCellRight(double* _mvm)
1003 {
1004  MovePickedCell(1, _mvm);
1005 }
1006 
1007 //-----------------------------------------------------------------------------
1008 
1009 template <typename BaseVecT, typename BoxT, typename T_CellData>
1010 void C_Octree< BaseVecT, BoxT, T_CellData >::MovePickedCellUp(double* _mvm)
1011 {
1012  MovePickedCell(2, _mvm);
1013 }
1014 
1015 //-----------------------------------------------------------------------------
1016 
1017 template <typename BaseVecT, typename BoxT, typename T_CellData>
1018 void C_Octree< BaseVecT, BoxT, T_CellData >::MovePickedCellDown(double* _mvm)
1019 {
1020  MovePickedCell(3, _mvm);
1021 }
1022 
1023 //-----------------------------------------------------------------------------
1024 
1033 template <typename BaseVecT, typename BoxT, typename T_CellData>
1034 void C_Octree< BaseVecT, BoxT, T_CellData >::MovePickedCell(int _direction, double* _mvm)
1035 {
1036  bool left = (_direction == 0);
1037  bool right = (_direction == 1);
1038  bool up = (_direction == 2);
1039  bool down = (_direction == 3);
1040 
1041  BaseVecT xAxis(_mvm[0], _mvm[4], _mvm[8]);
1042  BaseVecT yAxis(_mvm[1], _mvm[5], _mvm[9]);
1043 
1044  // ============================================================================================
1045  // 1) Determine the movement axes
1046  int xIndex=2;
1047  if (fabs(xAxis[0])>fabs(xAxis[1]))
1048  {
1049  if (fabs(xAxis[0])>fabs(xAxis[2]))
1050  xIndex=0;
1051  }
1052  else if (fabs(xAxis[1])>fabs(xAxis[2]))
1053  xIndex=1;
1054 
1055  int yIndex=2;
1056  if (fabs(yAxis[0])>fabs(yAxis[1]))
1057  {
1058  if (fabs(yAxis[0])>fabs(yAxis[2]))
1059  yIndex=0;
1060  }
1061  else if (fabs(yAxis[1])>fabs(yAxis[2]))
1062  yIndex=1;
1063 
1064  // ============================================================================================
1065  // 2) Move the cell along the x-axis
1066  CellHandle neighCell;
1067  if (xIndex==0)
1068  {
1069  if (xAxis[xIndex]<0)
1070  {
1071  if (left)
1072  neighCell = face_neighbor(m_PickedCell, 0);
1073  else if (right)
1074  neighCell = face_neighbor(m_PickedCell, 5);
1075  }
1076  else
1077  {
1078  if (left)
1079  neighCell = face_neighbor(m_PickedCell, 5);
1080  else if (right)
1081  neighCell = face_neighbor(m_PickedCell, 0);
1082  }
1083  }
1084  else if (xIndex==1)
1085  {
1086  if (xAxis[xIndex]<0)
1087  {
1088  if (left)
1089  neighCell = face_neighbor(m_PickedCell, 1);
1090  else if (right)
1091  neighCell = face_neighbor(m_PickedCell, 4);
1092  }
1093  else
1094  {
1095  if (left)
1096  neighCell = face_neighbor(m_PickedCell, 4);
1097  else if (right)
1098  neighCell = face_neighbor(m_PickedCell, 1);
1099  }
1100  }
1101  else // if (xIndex==2)
1102  {
1103  if (xAxis[xIndex]<0)
1104  {
1105  if (left)
1106  neighCell = face_neighbor(m_PickedCell, 2);
1107  else if (right)
1108  neighCell = face_neighbor(m_PickedCell, 3);
1109  }
1110  else
1111  {
1112  if (left)
1113  neighCell = face_neighbor(m_PickedCell, 3);
1114  else if (right)
1115  neighCell = face_neighbor(m_PickedCell, 2);
1116  }
1117  }
1118 
1119  // ============================================================================================
1120  // 3) Move the cell along the y-axis
1121  if (yIndex==0)
1122  {
1123  if (yAxis[yIndex]<0)
1124  {
1125  if (down)
1126  neighCell = face_neighbor(m_PickedCell, 0);
1127  else if (up)
1128  neighCell = face_neighbor(m_PickedCell, 5);
1129  }
1130  else
1131  {
1132  if (down)
1133  neighCell = face_neighbor(m_PickedCell, 5);
1134  else if (up)
1135  neighCell = face_neighbor(m_PickedCell, 0);
1136  }
1137  }
1138  else if (yIndex==1)
1139  {
1140  if (yAxis[yIndex]<0)
1141  {
1142  if (down)
1143  neighCell = face_neighbor(m_PickedCell, 1);
1144  else if (up)
1145  neighCell = face_neighbor(m_PickedCell, 4);
1146  }
1147  else
1148  {
1149  if (down)
1150  neighCell = face_neighbor(m_PickedCell, 4);
1151  else if (up)
1152  neighCell = face_neighbor(m_PickedCell, 1);
1153  }
1154  }
1155  else // if (yIndex==2)
1156  {
1157  if (yAxis[yIndex]<0)
1158  {
1159  if (down)
1160  neighCell = face_neighbor(m_PickedCell, 2);
1161  else if (up)
1162  neighCell = face_neighbor(m_PickedCell, 3);
1163  }
1164  else
1165  {
1166  if (down)
1167  neighCell = face_neighbor(m_PickedCell, 3);
1168  else if (up)
1169  neighCell = face_neighbor(m_PickedCell, 2);
1170  }
1171  }
1172 
1173  // ============================================================================================
1174  // 3) Check whether the movement can be done
1175  if ((neighCell.is_valid()) && (level(neighCell)==level(m_PickedCell)))
1176  {
1177  m_PickedCell = neighCell;
1178  }
1179 }
1180 
1181 //-----------------------------------------------------------------------------
1182 
1197 template <typename BaseVecT, typename BoxT, typename T_CellData>
1198 int C_Octree< BaseVecT, BoxT, T_CellData >::getChildIndex( BaseVecT center, coord<float> *point )
1199 {
1200  return (((*point)[0]) > center[0] ) | ((((*point)[1]) > center[1] ) << 1) | ((((*point)[2]) > center[2] ) << 2);
1201 }
1202 
1203 template <typename BaseVecT, typename BoxT, typename T_CellData>
1204 int C_Octree< BaseVecT, BoxT, T_CellData >::getChildIndex( BaseVecT center, BaseVecT point )
1205 {
1206  return ((point[0]) > center[0] ) | (((point[1]) > center[1] ) << 1) | (((point[2]) > center[2] ) << 2);
1207 }
1208 
1209 //-----------------------------------------------------------------------------
1210 
1221 template <typename BaseVecT, typename BoxT, typename T_CellData>
1222 void C_Octree< BaseVecT, BoxT, T_CellData >::split( CellHandle _parent, const bool bGarbageCollectionOnTheFly )
1223 {
1224  //
1225  // Split a cell into 8 sub-cells.
1226  //
1227  // 2---3
1228  // /| /|
1229  // 6---7 |
1230  // | 0-|-1
1231  // |/ |/
1232  // 4---5
1233  //
1234 
1235  // At the beginning do not forget the counter
1236  m_NumberOfGeneratedCells += 8;
1237 
1238  // If the next free block is at the end of the vector then splitting as usual
1239  LocCode cell_level = level( _parent ) - 1;
1240  LocCode cell_bit_mask = ( 1 << cell_level );
1241  LocCode par_loc_x = location( _parent ).loc_x();
1242  LocCode par_loc_y = location( _parent ).loc_y();
1243  LocCode par_loc_z = location( _parent ).loc_z();
1244 
1245  if (!bGarbageCollectionOnTheFly || (m_nextFreeBlock==m_OctreeCell.size()))
1246  {
1247  m_OctreeCell[ _parent.idx() ].next = m_OctreeCell.size();
1248 
1249  T_CellData dummy;
1250 
1251  dummy.location = Location( par_loc_x, par_loc_y, par_loc_z, cell_level, _parent );
1252  m_OctreeCell.push_back( dummy );
1253 
1254  dummy.location = Location( par_loc_x | cell_bit_mask, par_loc_y, par_loc_z, cell_level, _parent );
1255  m_OctreeCell.push_back( dummy );
1256 
1257  dummy.location = Location( par_loc_x, par_loc_y | cell_bit_mask, par_loc_z, cell_level, _parent );
1258  m_OctreeCell.push_back( dummy );
1259 
1260  dummy.location = Location( par_loc_x | cell_bit_mask, par_loc_y | cell_bit_mask, par_loc_z, cell_level, _parent );
1261  m_OctreeCell.push_back( dummy );
1262 
1263  dummy.location = Location( par_loc_x, par_loc_y, par_loc_z | cell_bit_mask, cell_level, _parent );
1264  m_OctreeCell.push_back( dummy );
1265 
1266  dummy.location = Location( par_loc_x | cell_bit_mask, par_loc_y, par_loc_z | cell_bit_mask, cell_level, _parent );
1267  m_OctreeCell.push_back( dummy );
1268 
1269  dummy.location = Location( par_loc_x, par_loc_y | cell_bit_mask, par_loc_z | cell_bit_mask, cell_level, _parent );
1270  m_OctreeCell.push_back( dummy );
1271 
1272  dummy.location = Location( par_loc_x | cell_bit_mask, par_loc_y | cell_bit_mask, par_loc_z | cell_bit_mask, cell_level, _parent );
1273  m_OctreeCell.push_back( dummy );
1274  }
1275  // ..else we do not push back but fill in the empty block
1276  else
1277  {
1278  m_OctreeCell[ _parent.idx() ].next = m_nextFreeBlock;
1279 
1280  m_OctreeCell[m_nextFreeBlock].location =
1281  Location( par_loc_x, par_loc_y, par_loc_z, cell_level, _parent );
1282  m_OctreeCell[m_nextFreeBlock+1].location =
1283  Location( par_loc_x | cell_bit_mask, par_loc_y, par_loc_z, cell_level, _parent );
1284  m_OctreeCell[m_nextFreeBlock+2].location =
1285  Location( par_loc_x, par_loc_y | cell_bit_mask, par_loc_z, cell_level, _parent );
1286  m_OctreeCell[m_nextFreeBlock+3].location =
1287  Location( par_loc_x | cell_bit_mask, par_loc_y | cell_bit_mask, par_loc_z, cell_level, _parent );
1288  m_OctreeCell[m_nextFreeBlock+4].location =
1289  Location( par_loc_x, par_loc_y, par_loc_z | cell_bit_mask, cell_level, _parent );
1290  m_OctreeCell[m_nextFreeBlock+5].location =
1291  Location( par_loc_x | cell_bit_mask, par_loc_y, par_loc_z | cell_bit_mask, cell_level, _parent );
1292  m_OctreeCell[m_nextFreeBlock+6].location =
1293  Location( par_loc_x, par_loc_y | cell_bit_mask, par_loc_z | cell_bit_mask, cell_level, _parent );
1294  m_OctreeCell[m_nextFreeBlock+7].location =
1295  Location( par_loc_x | cell_bit_mask, par_loc_y | cell_bit_mask, par_loc_z | cell_bit_mask, cell_level, _parent );
1296  }
1297 
1298  // Set the pointer to the next free block
1299  while ((m_nextFreeBlock<m_OctreeCell.size()) && m_OctreeCell[m_nextFreeBlock].location.parent().is_valid()) m_nextFreeBlock+=8;
1300 }
1301 
1302 //=============================================================================
1303 } // namespace octree
1304 //=============================================================================
1305 
1306 #endif
lvr2::C_Octree::location
Location & location(CellHandle _h)
Definition: Octree.hpp:158
lvr2::C_Octree::PickChildCell
bool PickChildCell(int _idx)
Pick the child cell of the currently picked cell.
Definition: Octree.hpp:78
lvr2::C_Octree::is_inner_boundary
bool is_inner_boundary(CellHandle _ch) const
Definition: Octree.hpp:940
lvr2::C_Octree::MAX_ROOT_LEVEL
static const int MAX_ROOT_LEVEL
Maximal root level defined by size of data type of the cell coordinates (leafs have side length 1) ...
Definition: Octree.hpp:34
lvr2::C_Octree::MovePickedCellUp
void MovePickedCellUp(double *_mvm)
Definition: Octree.hpp:1010
lvr2::C_Octree::level
int level(CellHandle _ch) const
Definition: Octree.hpp:907
lvr2::C_Octree::m_PickedCell
CellHandle m_PickedCell
The handle of the picked octree cell.
Definition: Octree.hpp:252
lvr2::C_Octree::MovePickedCellDown
void MovePickedCellDown(double *_mvm)
Definition: Octree.hpp:1018
lvr2::C_Octree::all_corner_neighbors
std::pair< std::vector< CellHandle >, std::vector< uint > > all_corner_neighbors(CellHandle _ch, int _idx) const
Definition: Octree.hpp:730
lvr2::C_Octree::cell
int cell(int _i) const
Definition: Octree.hpp:223
lvr2::C_Octree::size
int size() const
Definition: Octree.hpp:923
lvr2::C_Octree::m_OctreeCell
std::vector< T_CellData > m_OctreeCell
Vector containing the cells.
Definition: Octree.hpp:262
lvr2::C_Octree::parent
CellHandle parent(CellHandle _ch) const
Definition: Octree.hpp:290
lvr2::Location::loc_x
LocCode loc_x() const
Definition: Location.hh:40
lvr2::C_Octree::cell_size
Scalar cell_size(CellHandle _ch) const
Definition: Octree.hpp:152
lvr2::Location::loc_y
LocCode loc_y() const
Definition: Location.hh:41
lvr2::C_Octree
Definition: Octree.hpp:26
lvr2::C_Octree::~C_Octree
~C_Octree()
Definition: Octree.hpp:37
lvr2::C_Octree::GetExtractionLevel
LocCode GetExtractionLevel() const
Get the level to be treated as leaf level.
Definition: Octree.hpp:175
lvr2::C_Octree::is_leaf
bool is_leaf(CellHandle _ch) const
Definition: Octree.hpp:306
lvr2::C_Octree::getChildIndex
int getChildIndex(BaseVecT center, coord< float > *point)
Definition: Octree.hpp:1198
lvr2::C_Octree::GetPickedCell
CellHandle GetPickedCell() const
Get the handle of the picked cell.
Definition: Octree.hpp:169
lvr2::C_Octree::m_NumberOfGeneratedCells
int m_NumberOfGeneratedCells
Number of octree cells generated; this counter is adjusted in the split routine only.
Definition: Octree.hpp:255
lvr2::CellHandle::idx
int idx() const
Definition: CellHandle.hh:29
lvr2::C_Octree::MovePickedCellRight
void MovePickedCellRight(double *_mvm)
Definition: Octree.hpp:1002
lvr2::C_Octree::end
CellHandle end() const
Definition: Octree.hpp:98
lvr2::C_Octree::face_neighbor
CellHandle face_neighbor(CellHandle _ch, int _idx) const
Definition: Octree.hpp:484
lvr2::C_Octree::root
CellHandle root() const
Definition: Octree.hpp:298
lvr2::C_Octree::MovePickedCell
void MovePickedCell(int _key, double *_mvm)
Moving the picked cell, i.e. picking one of the neighbouring cells (if possible)
Definition: Octree.hpp:1034
lvr2::C_Octree::m_rootLevel
LocCode m_rootLevel
Root level.
Definition: Octree.hpp:246
lvr2::C_Octree::ResetNumberOfGeneratedCells
void ResetNumberOfGeneratedCells()
Reset the number of generated cells.
Definition: Octree.hpp:89
lvr2::C_Octree::traverse
CellHandle traverse(CellHandle _ch, LocCode _loc_x, LocCode _loc_y, LocCode _loc_z) const
Definition: Octree.hpp:429
lvr2::Location::LocCode
unsigned short LocCode
This datatype determines the maximal depth of the octree.
Definition: Location.hh:28
lvr2::C_Octree::Scalar
float Scalar
Definition: Octree.hpp:31
lvr2::C_Octree::resize
void resize(unsigned int _size)
Definition: Octree.hpp:274
lvr2::Location::parent
CellHandle parent() const
Definition: Location.hh:39
lvr2::C_Octree::PickParentCell
bool PickParentCell()
Pick the parent cell of the currently picked cell.
Definition: Octree.hpp:67
lvr2::C_Octree::traverse_to_level
CellHandle traverse_to_level(CellHandle _ch, LocCode _loc_x, LocCode _loc_y, LocCode _loc_z, LocCode _level) const
Definition: Octree.hpp:454
lvr2::Location::loc_z
LocCode loc_z() const
Definition: Location.hh:42
lvr2::C_Octree::C_Octree
C_Octree()
Definition: Octree.hpp:36
lvr2::C_Octree::ResetPickedCell
void ResetPickedCell()
Reset the cell handle of the picked cell.
Definition: Octree.hpp:61
lvr2::C_Octree::split
void split(CellHandle _ch, const bool bGarbageCollectionOnTheFly=false)
Split the cell, i.e. create eight children.
Definition: Octree.hpp:1222
lvr2::C_Octree::SetPickedCell
void SetPickedCell(CellHandle _ch)
Set the cell handle of the picked cell.
Definition: Octree.hpp:55
lvr2::C_Octree::nr_cells
int nr_cells() const
Definition: Octree.hpp:931
lvr2::C_Octree::is_root
bool is_root(CellHandle _ch) const
Definition: Octree.hpp:322
lvr2::C_Octree::m_nextFreeBlock
size_t m_nextFreeBlock
Pointer to the next free block (garbage collection)
Definition: Octree.hpp:249
lvr2::C_Octree::get_common_ancestor
CellHandle get_common_ancestor(CellHandle _ch, LocCode _diff) const
Definition: Octree.hpp:545
lvr2::C_Octree::set_cell
void set_cell(int _i, int _cell)
Definition: Octree.hpp:228
lvr2::C_Octree::cell
CellHandle cell(Scalar _x, Scalar _y, Scalar _z) const
Definition: Octree.hpp:963
lvr2::C_Octree::child
CellHandle child(CellHandle _ch, int _idx) const
Definition: Octree.hpp:282
lvr2::C_Octree::initialize
void initialize(int _max_octree_level)
Initializing the octree with maximal level = root level (leafs have level 0)
Definition: Octree.hpp:184
lvr2::C_Octree::cell_corner
BaseVecT cell_corner(CellHandle _ch, int _idx) const
Definition: Octree.hpp:122
lvr2::C_Octree::MovePickedCellLeft
void MovePickedCellLeft(double *_mvm)
Definition: Octree.hpp:994
lvr2::C_Octree::LocCode
Location::LocCode LocCode
Definition: Octree.hpp:30
lvr2::octreeVertexTable
static const int octreeVertexTable[8][3]
Definition: OctreeTables.hpp:70
uint
unsigned int uint
Definition: Model.hpp:46
lvr2::C_Octree::cell_center
BaseVecT cell_center(CellHandle _ch) const
Definition: Octree.hpp:138
lvr2::C_Octree::GetNumberOfGeneratedCells
int GetNumberOfGeneratedCells() const
Get number of generated cells.
Definition: Octree.hpp:172
lvr2::swap
void swap(T *&arr, size_t i1, size_t i2, size_t n)
Definition: PLYIO.cpp:414
lvr2::C_Octree::depth
int depth(CellHandle _ch) const
Definition: Octree.hpp:915
lvr2::octreeCornerNeighborTable
static const int octreeCornerNeighborTable[64][3]
Definition: OctreeTables.hpp:92
lvr2::C_Octree::corner_neighbor
CellHandle corner_neighbor(CellHandle _ch, int _idx) const
Definition: Octree.hpp:799
lvr2::C_Octree::reserve
void reserve(unsigned int _size)
Definition: Octree.hpp:266
lvr2::C_Octree::m_ExtractionLevel
LocCode m_ExtractionLevel
Level of the cells to be treated as leafs during surface extraction.
Definition: Octree.hpp:258
lvr2::C_Octree::SetExtractionLevel
LocCode SetExtractionLevel(LocCode _level)
Set the level to be treated as leaf level.
Definition: Octree.hpp:92
lvr2::CellHandle::is_valid
bool is_valid() const
Definition: CellHandle.hh:32
lvr2::C_Octree::location
const Location & location(CellHandle _h) const
Definition: Octree.hpp:162
lvr2::Location::level
LocCode level() const
Definition: Location.hh:43
lvr2::C_Octree::clear
void clear()
Definition: Octree.hpp:198
lvr2::C_Octree::is_extraction_leaf
bool is_extraction_leaf(CellHandle _ch) const
Definition: Octree.hpp:314
lvr2::C_Octree::edge_neighbor
CellHandle edge_neighbor(CellHandle _ch, int _idx) const
Definition: Octree.hpp:605

lvr2
Author(s): Thomas Wiemann , Sebastian Pütz , Alexander Mock , Lars Kiesow , Lukas Kalbertodt , Tristan Igelbrink , Johan M. von Behren , Dominik Feldschnieders , Alexander Löhr
autogenerated on Mon Feb 28 2022 22:46:08