| 1 |
|
/*========================================================================= |
| 2 |
|
|
| 3 |
|
Program: Insight Segmentation & Registration Toolkit |
| 4 |
|
Module: $RCSfile: itkOctree.txx.html,v $ |
| 5 |
|
Language: C++ |
| 6 |
|
Date: $Date: 2006/01/17 19:15:43 $ |
| 7 |
|
Version: $Revision: 1.4 $ |
| 8 |
|
|
| 9 |
|
Copyright (c) Insight Software Consortium. All rights reserved. |
| 10 |
|
See ITKCopyright.txt or http://www.itk.org/HTML/Copyright.htm for details. |
| 11 |
|
|
| 12 |
|
Portions of this code are covered under the VTK copyright. |
| 13 |
|
See VTKCopyright.txt or http://www.kitware.com/VTKCopyright.htm for details. |
| 14 |
|
|
| 15 |
HRD |
This software is distributed WITHOUT ANY WARRANTY; without even |
| 16 |
HRD |
the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR |
| 17 |
|
PURPOSE. See the above copyright notices for more information. |
| 18 |
|
|
| 19 |
|
=========================================================================*/ |
| 20 |
DEF |
#ifndef _itkOctree_txx |
| 21 |
DEF |
#define _itkOctree_txx |
| 22 |
|
#include "itkOctree.h" |
| 23 |
|
|
| 24 |
|
namespace itk |
| 25 |
|
{ |
| 26 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 27 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 28 |
|
Octree(void): m_Plane(UNKNOWN_PLANE), m_Width(0),m_Depth(0),m_Tree() |
| 29 |
|
{ |
| 30 |
|
m_TrueDims[0]=0; |
| 31 |
|
m_TrueDims[1]=1; |
| 32 |
|
m_TrueDims[2]=2; |
| 33 |
|
m_Tree.SetParentOctree(this); |
| 34 |
|
} |
| 35 |
|
|
| 36 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 37 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 38 |
|
~Octree(void) {/*Nothing to be done here*/}; |
| 39 |
|
|
| 40 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 41 |
|
void |
| 42 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 43 |
|
SetTrueDims(const unsigned int Dim0, const unsigned int Dim1, |
| 44 |
|
const unsigned int Dim2) |
| 45 |
|
{ |
| 46 |
|
this->m_TrueDims[0]=Dim0; |
| 47 |
|
this->m_TrueDims[1]=Dim1; |
| 48 |
|
this->m_TrueDims[2]=Dim2; |
| 49 |
|
} |
| 50 |
|
|
| 51 |
|
/*This is moving bits to get the values of the 8 octants |
| 52 |
IND |
****Possible values are the 3 bits to be set. |
| 53 |
IND |
****0 000 Contains origin |
| 54 |
IND |
****1 001 |
| 55 |
IND |
****2 010 |
| 56 |
IND |
****3 011 |
| 57 |
IND |
****4 100 |
| 58 |
IND |
****5 101 |
| 59 |
IND |
****6 110 |
| 60 |
IND |
****7 111 Contains extents |
| 61 |
IND |
****....^^^ |
| 62 |
IND |
****....|| \This value is 1 if requested X voxel is greater than X |
| 63 |
IND |
****.... centerline of subcube |
| 64 |
IND |
****....| \This value is 1 if requested Y voxel is greater than Y |
| 65 |
IND |
****.......centerline of subcube |
| 66 |
IND |
****.... \This value is 1 if requested Z voxel is greater than Z centerline |
| 67 |
IND |
****.......of subcube |
| 68 |
IND |
****\author Hans J. Johnson, adapted from Vincent A. Magnotta |
| 69 |
IND |
****\param VoxX The desired voxel |
| 70 |
IND |
****\param VoxY The desired voxel |
| 71 |
IND |
****\param VoxZ The desired voxel |
| 72 |
IND |
****\param CenterLineX The division line between octants |
| 73 |
IND |
****\param CenterLineY The division line between octants |
| 74 |
IND |
****\param CenterLineZ The division line between octants |
| 75 |
IND |
****\return The octant that the voxel falls into. |
| 76 |
IND |
***/ |
| 77 |
|
inline unsigned int OCTREE_OCTANT(const int VoxX, const int CenterLineX, |
| 78 |
|
const int VoxY, const int CenterLineY, |
| 79 |
|
const int VoxZ, const int CenterLineZ) |
| 80 |
|
{ |
| 81 |
|
return ( |
| 82 |
|
( |
| 83 |
|
(static_cast<unsigned int>(((VoxZ)>=(CenterLineZ)))<<2) |
| 84 |
|
| (static_cast<unsigned int>(((VoxY)>=(CenterLineY)))<<1) |
| 85 |
|
) |
| 86 |
|
| (static_cast<unsigned int>((VoxX)>=(CenterLineX))) |
| 87 |
IND |
****); |
| 88 |
|
} |
| 89 |
|
/** |
| 90 |
IND |
**** \defgroup Octant directional identifying functions |
| 91 |
IND |
**** These functions determine if the directions are in the "lower" or |
| 92 |
IND |
**** "upper" portion of the Octree in the given directions. |
| 93 |
IND |
**** @{ |
| 94 |
|
*/ |
| 95 |
IND |
inline unsigned int XF(const unsigned int octantID) |
| 96 |
IND |
{ |
| 97 |
IND |
**return octantID&1; //Just return 1 if 0th bit is a one |
| 98 |
IND |
} |
| 99 |
IND |
inline unsigned int YF(const unsigned int octantID) |
| 100 |
IND |
{ |
| 101 |
IND |
**return (octantID>>1)&1; //Just return 1 if 1st bit is a one |
| 102 |
IND |
} |
| 103 |
IND |
inline unsigned int ZF(const unsigned int octantID) |
| 104 |
IND |
{ |
| 105 |
IND |
**return (octantID>>2)&1; //Just return 1 if 2nd bit is a one |
| 106 |
IND |
} |
| 107 |
IND |
/** @} */ // End of defgroup |
| 108 |
|
|
| 109 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 110 |
|
unsigned int |
| 111 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 112 |
|
GetValue(const unsigned int Dim0, |
| 113 |
|
const unsigned int Dim1, |
| 114 |
|
const unsigned int Dim2) |
| 115 |
|
{ |
| 116 |
|
if ((Dim2 >= this->m_TrueDims[2]) || |
| 117 |
IND |
******(Dim1 >= this->m_TrueDims[1]) || (Dim0 >= this->m_TrueDims[0])) |
| 118 |
|
{ |
| 119 |
|
return 0; |
| 120 |
|
} |
| 121 |
|
|
| 122 |
|
//Define CurrentOctreeNode at the Octree head Node |
| 123 |
|
OctreeNode * CurrentOctreeNode = &m_Tree; |
| 124 |
|
//Define the origin of current OctreeNode |
| 125 |
|
unsigned int ox = 0, oy = 0, oz = 0; |
| 126 |
|
//Define the halfwidth, this will be changed inside of while loop |
| 127 |
|
unsigned int halfwidth = this->m_Width; |
| 128 |
|
|
| 129 |
|
|
| 130 |
|
while ((CurrentOctreeNode->IsNodeColored())==false) |
| 131 |
|
{ |
| 132 |
|
//NOTE: halfwidth=halfwidth/2 is the same as halfwidth >> 1 |
| 133 |
|
halfwidth=halfwidth >> 1; |
| 134 |
|
const unsigned int octantID = |
| 135 |
IND |
******OCTREE_OCTANT (Dim0, ox + halfwidth, Dim1, |
| 136 |
|
oy + halfwidth, Dim2, oz + halfwidth); |
| 137 |
|
//Determine new origin for next child. |
| 138 |
|
ox = ox + XF(octantID) * halfwidth; |
| 139 |
|
oy = oy + YF(octantID) * halfwidth; |
| 140 |
|
oz = oz + ZF(octantID) * halfwidth; |
| 141 |
|
|
| 142 |
|
CurrentOctreeNode = |
| 143 |
IND |
******&CurrentOctreeNode->GetChild(static_cast<enum LeafIdentifier>(octantID)); |
| 144 |
|
} |
| 145 |
|
return CurrentOctreeNode->GetColor(); |
| 146 |
|
} |
| 147 |
|
|
| 148 |
|
|
| 149 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 150 |
|
OctreeNodeBranch * |
| 151 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 152 |
|
maskToOctree (const TPixel* Mask, unsigned width, unsigned x, |
| 153 |
|
unsigned y, unsigned z, unsigned xsize, |
| 154 |
|
unsigned ysize, unsigned zsize) |
| 155 |
|
{ |
| 156 |
|
if ((x >= xsize) || (y >= ysize) || (z >= zsize)) |
| 157 |
|
{ |
| 158 |
|
return reinterpret_cast<OctreeNodeBranch *>(m_ColorTable |
| 159 |
|
+B2_MASKFILE_BLACK); |
| 160 |
|
} |
| 161 |
|
if (width == 1) |
| 162 |
|
{ |
| 163 |
|
return reinterpret_cast<OctreeNodeBranch *> |
| 164 |
LEN,IND |
******(m_ColorTable + m_MappingFunction.Evaluate(&Mask[z * ysize * xsize + y * xsize + x])); |
| 165 |
|
} |
| 166 |
|
width /= 2; |
| 167 |
|
OctreeNodeBranch *nodeArray[8]; |
| 168 |
|
nodeArray[0] = this->maskToOctree (Mask, width, x, y, z, |
| 169 |
|
xsize, ysize, zsize); |
| 170 |
|
nodeArray[1] = this->maskToOctree (Mask, width, x + width, y, z, |
| 171 |
|
xsize, ysize, zsize); |
| 172 |
|
nodeArray[2] = this->maskToOctree (Mask, width, x, y + width, z, |
| 173 |
|
xsize, ysize, zsize); |
| 174 |
|
nodeArray[3] = this->maskToOctree (Mask, width, x + width, y + width, z, |
| 175 |
|
xsize, ysize, zsize); |
| 176 |
|
nodeArray[4] = this->maskToOctree (Mask, width, x, y, z + width, |
| 177 |
|
xsize, ysize, zsize); |
| 178 |
|
nodeArray[5] = this->maskToOctree (Mask, width, x + width, y, z + width, |
| 179 |
|
xsize, ysize, zsize); |
| 180 |
|
nodeArray[6] = this->maskToOctree (Mask, width, x, y + width, z + width, |
| 181 |
|
xsize, ysize, zsize); |
| 182 |
|
nodeArray[7] = this->maskToOctree (Mask, width, x + width, y + width, |
| 183 |
|
z + width, xsize, ysize, zsize); |
| 184 |
|
|
| 185 |
|
if((nodeArray[0] == nodeArray[1]) && |
| 186 |
IND |
*****(nodeArray[0] == nodeArray[2]) && |
| 187 |
IND |
*****(nodeArray[0] == nodeArray[3]) && |
| 188 |
IND |
*****(nodeArray[0] == nodeArray[4]) && |
| 189 |
IND |
*****(nodeArray[0] == nodeArray[5]) && |
| 190 |
IND |
*****(nodeArray[0] == nodeArray[6]) && |
| 191 |
IND |
*****(nodeArray[0] == nodeArray[7])) |
| 192 |
|
{ |
| 193 |
|
return nodeArray[0]; |
| 194 |
|
} |
| 195 |
|
else |
| 196 |
|
{ |
| 197 |
|
OctreeNodeBranch *q = new OctreeNodeBranch(this); |
| 198 |
|
OctreeNode *newbranch; |
| 199 |
|
|
| 200 |
|
newbranch = q->GetLeaf(ZERO); |
| 201 |
|
newbranch->SetBranch(nodeArray[ZERO]); |
| 202 |
|
|
| 203 |
|
newbranch = q->GetLeaf(ONE); |
| 204 |
|
newbranch->SetBranch(nodeArray[ONE]); |
| 205 |
|
|
| 206 |
|
newbranch = q->GetLeaf(TWO); |
| 207 |
|
newbranch->SetBranch(nodeArray[TWO]); |
| 208 |
|
|
| 209 |
|
newbranch = q->GetLeaf(THREE); |
| 210 |
|
newbranch->SetBranch(nodeArray[THREE]); |
| 211 |
|
|
| 212 |
|
newbranch = q->GetLeaf(FOUR); |
| 213 |
|
newbranch->SetBranch(nodeArray[FOUR]); |
| 214 |
|
|
| 215 |
|
newbranch = q->GetLeaf(FIVE); |
| 216 |
|
newbranch->SetBranch(nodeArray[FIVE]); |
| 217 |
|
|
| 218 |
|
newbranch = q->GetLeaf(SIX); |
| 219 |
|
newbranch->SetBranch(nodeArray[SIX]); |
| 220 |
|
|
| 221 |
|
newbranch = q->GetLeaf(SEVEN); |
| 222 |
|
newbranch->SetBranch(nodeArray[SEVEN]); |
| 223 |
|
|
| 224 |
|
return (q); |
| 225 |
|
} |
| 226 |
|
} |
| 227 |
|
|
| 228 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 229 |
|
void |
| 230 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 231 |
LEN |
BuildFromBuffer(const void *frombuffer,const int xsize,const int ysize,const int zsize) |
| 232 |
|
{ |
| 233 |
|
unsigned maxSize = xsize >= ysize ? |
| 234 |
IND |
****(xsize >= zsize ? xsize : zsize) : |
| 235 |
IND |
****(ysize >= zsize ? ysize : zsize); |
| 236 |
|
unsigned width = 1; |
| 237 |
|
unsigned depth = 0; |
| 238 |
|
while(width < maxSize) |
| 239 |
|
{ |
| 240 |
|
width *= 2; |
| 241 |
|
depth++; |
| 242 |
|
} |
| 243 |
|
this->SetDepth(depth); |
| 244 |
|
this->SetWidth(width); |
| 245 |
|
m_TrueDims[0] = xsize; |
| 246 |
|
m_TrueDims[1] = ysize; |
| 247 |
|
m_TrueDims[2] = zsize; |
| 248 |
|
const TPixel *bufcast = static_cast<const TPixel *>(frombuffer); |
| 249 |
|
OctreeNodeBranch *branch = |
| 250 |
IND |
****this->maskToOctree(bufcast,width,0,0,0, |
| 251 |
|
xsize,ysize,zsize); |
| 252 |
|
m_Tree.SetBranch(branch); |
| 253 |
|
} |
| 254 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 255 |
|
void |
| 256 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 257 |
|
BuildFromImage(ImageType *fromImage) |
| 258 |
|
{ |
| 259 |
|
const typename Image<TPixel,3>::RegionType ®ion = |
| 260 |
IND |
****fromImage->GetLargestPossibleRegion(); |
| 261 |
|
unsigned int xsize,ysize,zsize; |
| 262 |
|
xsize = region.GetSize(0); |
| 263 |
|
ysize = region.GetSize(1); |
| 264 |
|
zsize = region.GetSize(2); |
| 265 |
|
this->BuildFromBuffer(static_cast<void *>(fromImage->GetBufferPointer()), |
| 266 |
IND |
************************xsize,ysize,zsize); |
| 267 |
|
} |
| 268 |
|
|
| 269 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 270 |
|
typename Octree<TPixel,ColorTableSize,MappingFunctionType>::ImageTypePointer |
| 271 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 272 |
|
GetImage() |
| 273 |
|
{ |
| 274 |
|
unsigned int i,j,k; |
| 275 |
|
typename ImageType::SizeType imageSize = {{0,0,0}}; |
| 276 |
|
typedef typename ImageType::SizeType::SizeValueType SizeValueType; |
| 277 |
|
SizeValueType sizes[3]; |
| 278 |
|
sizes[0] = m_TrueDims[0]; |
| 279 |
|
sizes[1] = m_TrueDims[1]; |
| 280 |
|
sizes[2] = m_TrueDims[2]; |
| 281 |
|
imageSize.SetSize(sizes); |
| 282 |
|
const typename ImageType::IndexType imageIndex = {{0,0,0}}; |
| 283 |
|
typename ImageType::RegionType region; |
| 284 |
|
region.SetSize(imageSize); |
| 285 |
|
region.SetIndex(imageIndex); |
| 286 |
|
typename ImageType::Pointer img = ImageType::New(); |
| 287 |
|
img->SetLargestPossibleRegion(region); |
| 288 |
|
img->SetBufferedRegion(region); |
| 289 |
|
img->SetRequestedRegion(region); |
| 290 |
|
img->Allocate(); |
| 291 |
|
typename ImageType::IndexType setIndex; |
| 292 |
|
for(i = 0; i < m_TrueDims[0]; i++) |
| 293 |
|
{ |
| 294 |
|
setIndex[0] = i; |
| 295 |
|
for(j = 0; j < m_TrueDims[0]; j++) |
| 296 |
|
{ |
| 297 |
|
setIndex[1] = j; |
| 298 |
|
for(k = 0; k < m_TrueDims[0]; k++) |
| 299 |
|
{ |
| 300 |
|
setIndex[2] = k; |
| 301 |
|
img->SetPixel(setIndex,(TPixel)this->GetValue(i,j,k)); |
| 302 |
|
} |
| 303 |
|
} |
| 304 |
|
} |
| 305 |
|
return img; |
| 306 |
|
} |
| 307 |
|
|
| 308 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 309 |
|
OctreeNode * |
| 310 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 311 |
|
GetTree() |
| 312 |
|
{ |
| 313 |
|
return &m_Tree; |
| 314 |
|
} |
| 315 |
|
|
| 316 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 317 |
|
void |
| 318 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 319 |
|
SetWidth(unsigned int width) |
| 320 |
|
{ |
| 321 |
|
m_Width = width; |
| 322 |
|
} |
| 323 |
|
|
| 324 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 325 |
|
void |
| 326 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 327 |
|
SetDepth(unsigned int depth) |
| 328 |
|
{ |
| 329 |
|
m_Depth = depth; |
| 330 |
|
} |
| 331 |
|
|
| 332 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 333 |
|
unsigned int |
| 334 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 335 |
|
GetWidth() |
| 336 |
|
{ |
| 337 |
|
return m_Width; |
| 338 |
|
} |
| 339 |
|
|
| 340 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 341 |
|
unsigned int |
| 342 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 343 |
|
GetDepth() |
| 344 |
|
{ |
| 345 |
|
return m_Depth; |
| 346 |
|
} |
| 347 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 348 |
|
const char * |
| 349 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 350 |
|
GetColorTable() const |
| 351 |
|
{ |
| 352 |
|
return m_ColorTable; |
| 353 |
|
} |
| 354 |
|
template <class TPixel,unsigned int ColorTableSize,class MappingFunctionType> |
| 355 |
|
int |
| 356 |
|
Octree<TPixel,ColorTableSize,MappingFunctionType>:: |
| 357 |
|
GetColorTableSize() const |
| 358 |
|
{ |
| 359 |
|
return ColorTableSize; |
| 360 |
|
} |
| 361 |
|
|
| 362 |
|
} |
| 363 |
|
|
| 364 |
|
|
| 365 |
|
#endif |
| 366 |
|
|
