DGtal  1.5.beta
Morton.ih
1 /**
2  * This program is free software: you can redistribute it and/or modify
3  * it under the terms of the GNU Lesser General Public License as
4  * published by the Free Software Foundation, either version 3 of the
5  * License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program. If not, see <http://www.gnu.org/licenses/>.
14  *
15  **/
16 
17 /**
18  * @file Morton.ih
19  * @author David Coeurjolly (\c david.coeurjolly@liris.cnrs.fr )
20  * Laboratoire d'InfoRmatique en Image et Systèmes d'information - LIRIS (CNRS, UMR 5205), CNRS, France
21  *
22  * @date 2010/09/10
23  *
24  * Header file for module Morton.cpp
25  *
26  * This file is part of the DGtal library.
27  */
28 
29 
30 //////////////////////////////////////////////////////////////////////////////
31 // Inclusions
32 #include <iostream>
33 //////////////////////////////////////////////////////////////////////////////
34 
35 namespace DGtal
36  {
37 
38  template <typename HashKey, typename Point >
39  Morton<HashKey,Point>::Morton()
40  {
41  // @todo precomputation of the dilate masks
42  //myDilateMasks[0] = 25;
43  }
44 
45 
46  template <typename HashKey, typename Point >
47  void Morton<HashKey,Point>:: interleaveBits ( const Point & aPoint, HashKey & output ) const
48  {
49  //number of bits of the input integers (casted according to the hashkeysize)
50  // max of this with sizeof(Coordinate)*8
51  unsigned int coordSize = ( sizeof ( HashKey ) <<3 ) / dimension;
52 
53  output = 0;
54  for ( unsigned int i = 0; i < coordSize; ++i )
55  for ( unsigned int n = 0; n < dimension; ++n )
56  {
57  if ( ( aPoint[n] ) & ( static_cast<Coordinate> ( 1 ) << i ) )
58  output |= static_cast<Coordinate> ( 1 ) << (( i*dimension ) +n);
59  }
60  }
61 
62 
63  template <typename HashKey, typename Point >
64  HashKey Morton<HashKey,Point>::keyFromCoordinates ( const std::size_t treeDepth,
65  const Point & coordinates ) const
66  {
67  HashKey result = 0;
68 
69  interleaveBits ( coordinates, result );
70  // by convention, the root node has the key 0..01
71  // it makes it easy to determine the depth of a node by it's key (looking
72  // at the position of the most significant bit that is equal to 1)
73  result |= ( static_cast<HashKey> ( 1 ) << dimension*treeDepth );
74 
75  return result;
76  }
77 
78 
79 
80  template <typename HashKey, typename Point >
81  void Morton<HashKey,Point>::childrenKeys ( const HashKey key, HashKey* result ) const
82  {
83  HashKey keycopy = key;
84 
85  keycopy <<= dimension;
86  //generate a mask of the form 1..111000 with dimension "0"
87  HashKey mask = ( static_cast<HashKey> ( ~0 ) << dimension );
88  for ( std::size_t i = 0;
89  i < POW<2,dimension>::VALUE;
90  ++i )
91  {
92  result[i] = ( keycopy & mask ) |i;
93  }
94  }
95 
96  template <typename HashKey, typename Point >
97  void Morton<HashKey,Point>::brotherKeys ( const HashKey key, HashKey* result ) const
98  {
99  //generate a mask of the form 1..111000 with dimension "0"
100  HashKey mask = ( static_cast<HashKey> ( ~0 ) << dimension );
101  std::size_t j = 0;
102  for ( std::size_t i = 0; i < POW<2,dimension>::VALUE; ++i )
103  {
104  HashKey key2 = ( key & mask ) |i;
105  if ( key2 != key )
106  {
107  result[j] = key2;
108  ++j;
109  }
110  }
111  }
112 
113  template <typename HashKey, typename Point >
114  void Morton<HashKey,Point>::coordinatesFromKey ( const HashKey key, Point & coordinates ) const
115  {
116  HashKey akey = key;
117  //remove the first bit equal 1
118  for ( int i = ( sizeof ( HashKey ) <<3 )-1; i >= 0; --i )
119  if ( akey & Bits::mask<HashKey> ( i ) )
120  {
121  akey &= ~Bits::mask<HashKey> ( i );
122  break;
123  }
124 
125  //deinterleave the bits
126  for ( std::size_t i = 0; i < dimension; ++i )
127  {
128  coordinates[(Dimension)i] = 0;
129 
130  for ( std::size_t bitPos = 0; bitPos < ( sizeof ( HashKey ) <<3 ) / dimension; ++bitPos )
131  {
132  if ( akey & Bits::mask<HashKey> ( (unsigned int)(bitPos*dimension+i) ) )
133  {
134  coordinates[(Dimension)i] |= Bits::mask<HashKey> ( (unsigned int)bitPos );
135  }
136  }
137  }
138  }
139 
140 }