1 /*
2  * Software License Agreement (BSD License)
3  *
4  *  Point Cloud Library (PCL) - www.pointclouds.org
5  *  Copyright (c) 2010-2012, Willow Garage, Inc.
6  *
7  *  All rights reserved.
8  *
9  *  Redistribution and use in source and binary forms, with or without
10  *  modification, are permitted provided that the following conditions
11  *  are met:
12  *
13  *   * Redistributions of source code must retain the above copyright
14  *     notice, this list of conditions and the following disclaimer.
15  *   * Redistributions in binary form must reproduce the above
16  *     copyright notice, this list of conditions and the following
17  *     disclaimer in the documentation and/or other materials provided
18  *     with the distribution.
19  *   * Neither the name of Willow Garage, Inc. nor the names of its
20  *     contributors may be used to endorse or promote products derived
21  *     from this software without specific prior written permission.
22  *
23  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26  *  FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27  *  COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29  *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30  *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31  *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33  *  ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34  *  POSSIBILITY OF SUCH DAMAGE.
35  *
36  */
37 
38 #pragma once
39 
40 #include <cstdint>
41 #include <cstring> // for memcpy
42 
43 namespace pcl {
44 namespace octree {
45 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
46 /** \brief @b Octree key class
47  *  \note Octree keys contain integer indices for each coordinate axis in order to
48  * address an octree leaf node.
49  * \author Julius Kammerl (julius@kammerl.de)
50  */
51 //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
52 class OctreeKey {
53 public:
54   /** \brief Empty constructor. */
OctreeKey()55   OctreeKey() : x(0), y(0), z(0) {}
56 
57   /** \brief Constructor for key initialization. */
OctreeKey(uindex_t keyX,uindex_t keyY,uindex_t keyZ)58   OctreeKey(uindex_t keyX, uindex_t keyY, uindex_t keyZ) : x(keyX), y(keyY), z(keyZ) {}
59 
60   /** \brief Copy constructor. */
OctreeKey(const OctreeKey & source)61   OctreeKey(const OctreeKey& source) { std::memcpy(key_, source.key_, sizeof(key_)); }
62 
63   OctreeKey&
64   operator=(const OctreeKey&) = default;
65 
66   /** \brief Operator== for comparing octree keys with each other.
67    *  \return "true" if leaf node indices are identical; "false" otherwise.
68    * */
69   bool
70   operator==(const OctreeKey& b) const
71   {
72     return ((b.x == this->x) && (b.y == this->y) && (b.z == this->z));
73   }
74 
75   /** \brief Inequal comparison operator
76    * \param[in] other OctreeIteratorBase to compare with
77    * \return "true" if the current and other iterators are different ; "false"
78    * otherwise.
79    */
80   bool
81   operator!=(const OctreeKey& other) const
82   {
83     return !operator==(other);
84   }
85 
86   /** \brief Operator<= for comparing octree keys with each other.
87    *  \return "true" if key indices are not greater than the key indices of b  ; "false"
88    * otherwise.
89    * */
90   bool
91   operator<=(const OctreeKey& b) const
92   {
93     return ((b.x >= this->x) && (b.y >= this->y) && (b.z >= this->z));
94   }
95 
96   /** \brief Operator>= for comparing octree keys with each other.
97    *  \return "true" if key indices are not smaller than the key indices of b  ; "false"
98    * otherwise.
99    * */
100   bool
101   operator>=(const OctreeKey& b) const
102   {
103     return ((b.x <= this->x) && (b.y <= this->y) && (b.z <= this->z));
104   }
105 
106   /** \brief push a child node to the octree key
107    *  \param[in] childIndex index of child node to be added (0-7)
108    * */
109   inline void
pushBranch(unsigned char childIndex)110   pushBranch(unsigned char childIndex)
111   {
112     this->x = (this->x << 1) | (!!(childIndex & (1 << 2)));
113     this->y = (this->y << 1) | (!!(childIndex & (1 << 1)));
114     this->z = (this->z << 1) | (!!(childIndex & (1 << 0)));
115   }
116 
117   /** \brief pop child node from octree key
118    * */
119   inline void
popBranch()120   popBranch()
121   {
122     this->x >>= 1;
123     this->y >>= 1;
124     this->z >>= 1;
125   }
126 
127   /** \brief get child node index using depthMask
128    *  \param[in] depthMask bit mask with single bit set at query depth
129    *  \return child node index
130    * */
131   inline unsigned char
getChildIdxWithDepthMask(uindex_t depthMask)132   getChildIdxWithDepthMask(uindex_t depthMask) const
133   {
134     return static_cast<unsigned char>(((!!(this->x & depthMask)) << 2) |
135                                       ((!!(this->y & depthMask)) << 1) |
136                                       (!!(this->z & depthMask)));
137   }
138 
139   /* \brief maximum depth that can be addressed */
140   static const unsigned char maxDepth =
141       static_cast<unsigned char>(sizeof(uindex_t) * 8);
142 
143   // Indices addressing a voxel at (X, Y, Z)
144 
145   union {
146     struct {
147       uindex_t x;
148       uindex_t y;
149       uindex_t z;
150     };
151     uindex_t key_[3];
152   };
153 };
154 } // namespace octree
155 } // namespace pcl
156