OpenStructure
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
map_octree.hh
Go to the documentation of this file.
1 //------------------------------------------------------------------------------
2 // This file is part of the OpenStructure project <www.openstructure.org>
3 //
4 // Copyright (C) 2008-2011 by the OpenStructure authors
5 //
6 // This library is free software; you can redistribute it and/or modify it under
7 // the terms of the GNU Lesser General Public License as published by the Free
8 // Software Foundation; either version 3.0 of the License, or (at your option)
9 // any later version.
10 // This library is distributed in the hope that it will be useful, but WITHOUT
11 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
12 // FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
13 // details.
14 //
15 // You should have received a copy of the GNU Lesser General Public License
16 // along with this library; if not, write to the Free Software Foundation, Inc.,
17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18 //------------------------------------------------------------------------------
19 #ifndef OST_GFX_IMPL_MAP_OCTREE_HH
20 #define OST_GFX_IMPL_MAP_OCTREE_HH
21 
22 #include <ost/img/image_handle.hh>
23 #include <ost/img/image_state.hh>
24 #include <ost/gfx/module_config.hh>
25 #include <ost/stdint.hh>
26 /*
27  Author: Marco Biasini
28  */
29 namespace ost { namespace gfx { namespace impl {
30 
31 typedef uint16_t OcRange;
32 
33 struct OcRangeVector {
35  x(px), y(py), z(pz)
36  { }
40 };
41 
46 class OctreeNode {
47 public:
48  OctreeNode(uint32_t first_child, bool branch_x, bool branch_y, bool branch_z):
49  first_child_(first_child), branch_x_(branch_x),
50  branch_y_(branch_y), branch_z_(branch_z), is_leaf_(false),
51  min_(0.0), max_(0.0)
52  { }
53  OctreeNode(): first_child_(0),
54  branch_x_(false), branch_y_(false), branch_z_(false), is_leaf_(false),
55  min_(0.0), max_(0.0)
56  { }
58  bool BranchInX() const { return branch_x_; }
60  bool BranchInY() const { return branch_y_; }
62  bool BranchInZ() const { return branch_z_; }
63 
66  uint8_t sum=(uint8_t(branch_x_)+uint8_t(branch_y_)+uint8_t(branch_z_));
67  switch (sum) {
68  case 0:
69  return 0;
70  case 1:
71  return 2;
72  case 2:
73  return 4;
74  case 3:
75  return 8;
76  default:
77  assert(0 && "what the heck?");
78  }
79  return 0;
80  }
82  return first_child_;
83  }
84  float GetMin() const { return min_; }
85  float GetMax() const { return max_; }
86  bool IsLeaf() const { return is_leaf_; }
87  void SetLeaf() { is_leaf_=true; }
88  void SetMin(float m) { min_=m; }
89  void SetMax(float m) { max_=m; }
90 private:
91  uint32_t first_child_ : 28; // < index of left-most child
92  bool branch_x_ : 1; // < whether to branch in x
93  bool branch_y_ : 1; // < whether to branch in y
94  bool branch_z_ : 1; // < whether to branch in z
95  bool is_leaf_ : 1; // < whether the child nodes are leafs
96  float min_; // < minimum value of voxels inside OctreeNode
97  float max_; // < maximum value of voxels inside OctreeNode
98 };
99 
100 typedef std::vector<OctreeNode> OcNodeEntryList;
101 
102 
110 public:
111  MapOctree(const img::ImageHandle& map);
112  void Initialize();
113  uint32_t GetNumNodesForLevel(uint8_t level) const;
114  void SetNewMap(const img::ImageHandle& ih);
115  static bool IsMapManageable (const img::ImageHandle ih);
116 
118  template <typename F>
119  void VisitDF(F& f) const
120  {
121  if (levels_.empty()) {
122  return;
123  }
124  img::Extent ext=map_.GetExtent();
125  img::RealSpatialImageState* map=NULL;
126  map=dynamic_cast<img::RealSpatialImageState*>(map_.ImageStatePtr().get());
127  assert(levels_[0].size()==1);
128  if (f.VisitNode(levels_[0][0], 0, ext)) {
129  this->VisitDFRec<F>(levels_[0][0], f, 1, ext, map);
130  }
131  }
132 
133 protected:
134  static inline int LastSetBit(uint16_t ch)
135  {
136  for (char i=15; i>=0; --i) {
137  uint16_t m=1<<i;
138  if (ch & m) {
139  return i;
140  }
141  }
142  return -1;
143  }
144 
145  template <typename F>
146  void VisitDFRec(const OctreeNode& node, F& f, uint8_t level,
147  const img::Extent& ext,
148  img::RealSpatialImageState* map) const
149  {
150  if (node.GetChildCount()==0) { return; }
151  uint32_t c=node.GetFirstChild();
152  int cx=1+int(node.BranchInX());
153  int cy=1+int(node.BranchInY());
154  int cz=1+int(node.BranchInZ());
155  int range_x[2][2];
156  int range_y[2][2];
157  int range_z[2][2];
158  // update ranges. this is basically the same code as in BuildOctreeRec()
159  if (node.BranchInX()) {
160  uint16_t ems=ext.GetEnd()[0]-ext.GetStart()[0];
161  uint16_t bit_mask=1<<(LastSetBit(ems));
162  range_x[0][0]=ext.GetStart()[0];
163  range_x[0][1]=range_x[0][0]+bit_mask-1;
164  range_x[1][0]=ext.GetEnd()[0]-(ems & ~bit_mask);
165  range_x[1][1]=ext.GetEnd()[0];
166  } else {
167  range_x[0][0]=ext.GetStart()[0];
168  range_x[0][1]=ext.GetEnd()[0];
169  }
170  if (node.BranchInY()) {
171  uint16_t ems=ext.GetEnd()[1]-ext.GetStart()[1];
172  uint16_t bit_mask=1<<(LastSetBit(ems));
173  range_y[0][0]=ext.GetStart()[1];
174  range_y[0][1]=range_y[0][0]+bit_mask-1;
175  range_y[1][0]=ext.GetEnd()[1]-(ems & ~bit_mask);
176  range_y[1][1]=ext.GetEnd()[1];
177  } else {
178  range_y[0][0]=ext.GetStart()[1];
179  range_y[0][1]=ext.GetEnd()[1];
180  }
181  if (node.BranchInZ()) {
182  uint16_t ems=ext.GetEnd()[2]-ext.GetStart()[2];
183  uint16_t bit_mask=1<<(LastSetBit(ems));
184  range_z[0][0]=ext.GetStart()[2];
185  range_z[0][1]=range_z[0][0]+bit_mask-1;
186  range_z[1][0]=ext.GetEnd()[2]-(ems & ~bit_mask);
187  range_z[1][1]=ext.GetEnd()[2];
188  } else {
189  range_z[0][0]=ext.GetStart()[2];
190  range_z[0][1]=ext.GetEnd()[2];
191  }
192  for (int i=0; i<cx; ++i) {
193  for (int j=0; j<cy; ++j) {
194  for (int k=0; k<cz; ++k, ++c) {
195  if (node.IsLeaf()) {
196  f.VisitLeaf(map, img::Point(range_x[i][0], range_y[j][0],
197  range_z[k][0]));
198  } else {
199  const OctreeNode& cn=levels_[level][c];
200  img::Extent ext(img::Point(range_x[i][0], range_y[j][0],
201  range_z[k][0]),
202  img::Point(range_x[i][1], range_y[j][1],
203  range_z[k][1]));
204  if (f.VisitNode(cn, level, ext)) {
205  this->VisitDFRec<F>(cn, f, level+1, ext, map);
206  }
207  }
208  }
209  }
210  }
211  }
212 private:
213  void BuildOctree();
214  std::pair<float, float> BuildOctreeRec(const OcRangeVector& range_vec,
215  uint16_t level,
217  const img::Extent& ext,
218  OctreeNode& parent);
219 
220  img::ImageHandle map_;
221  std::vector<OcNodeEntryList> levels_;
222  bool built_;
223 };
224 
225 }}}
226 
227 #endif
OctreeNode(uint32_t first_child, bool branch_x, bool branch_y, bool branch_z)
Definition: map_octree.hh:48
bool BranchInZ() const
whether the node branches in z direction
Definition: map_octree.hh:62
Octree datastructure for 3D images.
Definition: map_octree.hh:109
static int LastSetBit(uint16_t ch)
Definition: map_octree.hh:134
unsigned int uint32_t
Definition: stdint_msc.hh:80
unsigned char uint8_t
Definition: stdint_msc.hh:78
const Point & GetEnd() const
Return upper/right/back corner.
#define DLLEXPORT_OST_GFX
Defines lower and upper valid indices.
Definition: extent.hh:60
uint32_t GetFirstChild() const
Definition: map_octree.hh:81
void VisitDFRec(const OctreeNode &node, F &f, uint8_t level, const img::Extent &ext, img::RealSpatialImageState *map) const
Definition: map_octree.hh:146
bool BranchInY() const
whether the node branches in y direction
Definition: map_octree.hh:60
const Point & GetStart() const
Return lower/left/front corner.
uint8_t GetChildCount() const
get number of children
Definition: map_octree.hh:65
unsigned short uint16_t
Definition: stdint_msc.hh:79
ImageStateImpl< Real, SpatialDomain > RealSpatialImageState
Manage shared instances of images.
std::vector< OctreeNode > OcNodeEntryList
Definition: map_octree.hh:100
OcRangeVector(uint16_t px, uint16_t py, uint16_t pz)
Definition: map_octree.hh:34
void VisitDF(F &f) const
depth-first visit of octree nodes
Definition: map_octree.hh:119
uint16_t OcRange
Definition: map_octree.hh:31
class encapsulating 1D to 3D point
Definition: point.hh:43
bool BranchInX() const
whether the node branches in x direction
Definition: map_octree.hh:58