1 // Copyright 2016 The Draco Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // TODO(b/199760123): Make this a wrapper using 16 // DynamicIntegerPointsKdTreeDecoder. 17 // 18 // See integer_points_kd_tree_encoder.h for documentation. 19 20 #ifndef DRACO_COMPRESSION_POINT_CLOUD_ALGORITHMS_INTEGER_POINTS_KD_TREE_DECODER_H_ 21 #define DRACO_COMPRESSION_POINT_CLOUD_ALGORITHMS_INTEGER_POINTS_KD_TREE_DECODER_H_ 22 23 #include <array> 24 #include <memory> 25 26 #include "draco/compression/bit_coders/adaptive_rans_bit_decoder.h" 27 #include "draco/compression/bit_coders/direct_bit_decoder.h" 28 #include "draco/compression/bit_coders/folded_integer_bit_decoder.h" 29 #include "draco/compression/bit_coders/rans_bit_decoder.h" 30 #include "draco/compression/point_cloud/algorithms/point_cloud_types.h" 31 #include "draco/compression/point_cloud/algorithms/queuing_policy.h" 32 #include "draco/core/bit_utils.h" 33 #include "draco/core/decoder_buffer.h" 34 #include "draco/core/math_utils.h" 35 36 namespace draco { 37 38 template <int compression_level_t> 39 struct IntegerPointsKdTreeDecoderCompressionPolicy 40 : public IntegerPointsKdTreeDecoderCompressionPolicy<compression_level_t - 41 1> {}; 42 43 template <> 44 struct IntegerPointsKdTreeDecoderCompressionPolicy<0> { 45 typedef DirectBitDecoder NumbersDecoder; 46 typedef DirectBitDecoder AxisDecoder; 47 typedef DirectBitDecoder HalfDecoder; 48 typedef DirectBitDecoder RemainingBitsDecoder; 49 static constexpr bool select_axis = false; 50 51 template <class T> 52 using QueuingStrategy = Stack<T>; 53 }; 54 55 template <> 56 struct IntegerPointsKdTreeDecoderCompressionPolicy<2> 57 : public IntegerPointsKdTreeDecoderCompressionPolicy<1> { 58 typedef RAnsBitDecoder NumbersDecoder; 59 }; 60 61 template <> 62 struct IntegerPointsKdTreeDecoderCompressionPolicy<4> 63 : public IntegerPointsKdTreeDecoderCompressionPolicy<3> { 64 typedef FoldedBit32Decoder<RAnsBitDecoder> NumbersDecoder; 65 }; 66 67 template <> 68 struct IntegerPointsKdTreeDecoderCompressionPolicy<6> 69 : public IntegerPointsKdTreeDecoderCompressionPolicy<5> { 70 static constexpr bool select_axis = true; 71 }; 72 73 template <> 74 struct IntegerPointsKdTreeDecoderCompressionPolicy<8> 75 : public IntegerPointsKdTreeDecoderCompressionPolicy<7> { 76 typedef FoldedBit32Decoder<AdaptiveRAnsBitDecoder> NumbersDecoder; 77 template <class T> 78 using QueuingStrategy = Queue<T>; 79 }; 80 81 template <> 82 struct IntegerPointsKdTreeDecoderCompressionPolicy<10> 83 : public IntegerPointsKdTreeDecoderCompressionPolicy<9> { 84 template <class T> 85 using QueuingStrategy = PriorityQueue<T>; 86 }; 87 88 // Decodes a point cloud encoded by IntegerPointsKdTreeEncoder. 89 // |PointDiT| is a type representing a point with uint32_t coordinates. 90 // must provide construction from three uint32_t and operator[]. 91 template <class PointDiT, int compression_level_t> 92 class IntegerPointsKdTreeDecoder { 93 typedef IntegerPointsKdTreeDecoderCompressionPolicy<compression_level_t> 94 Policy; 95 96 typedef typename Policy::NumbersDecoder NumbersDecoder; 97 typedef typename Policy::AxisDecoder AxisDecoder; 98 typedef typename Policy::HalfDecoder HalfDecoder; 99 typedef typename Policy::RemainingBitsDecoder RemainingBitsDecoder; 100 101 public: 102 IntegerPointsKdTreeDecoder() : bit_length_(0) {} 103 104 // Decodes a integer point cloud from |buffer|. 105 template <class OutputIteratorT> 106 bool DecodePoints(DecoderBuffer *buffer, OutputIteratorT oit); 107 108 private: 109 // For the sake of readability of code, we decided to make this exception 110 // from the naming scheme. 111 static constexpr int D = PointTraits<PointDiT>::Dimension(); 112 113 uint32_t GetAxis(uint32_t num_remaining_points, const PointDiT &base, 114 std::array<uint32_t, D> levels, uint32_t last_axis); 115 116 template <class OutputIteratorT> 117 void DecodeInternal(uint32_t num_remaining_points, PointDiT base, 118 std::array<uint32_t, D> levels, uint32_t last_axis, 119 OutputIteratorT oit); 120 121 void DecodeNumber(int nbits, uint32_t *value) { 122 numbers_decoder_.DecodeLeastSignificantBits32(nbits, value); 123 } 124 125 struct DecodingStatus { 126 DecodingStatus( 127 uint32_t num_remaining_points_, const PointDiT &old_base_, 128 std::array<uint32_t, PointTraits<PointDiT>::Dimension()> levels_, 129 uint32_t last_axis_) 130 : num_remaining_points(num_remaining_points_), 131 old_base(old_base_), 132 levels(levels_), 133 last_axis(last_axis_) {} 134 135 uint32_t num_remaining_points; 136 PointDiT old_base; 137 std::array<uint32_t, D> levels; 138 uint32_t last_axis; 139 friend bool operator<(const DecodingStatus &l, const DecodingStatus &r) { 140 return l.num_remaining_points < r.num_remaining_points; 141 } 142 }; 143 144 uint32_t bit_length_; 145 uint32_t num_points_; 146 NumbersDecoder numbers_decoder_; 147 RemainingBitsDecoder remaining_bits_decoder_; 148 AxisDecoder axis_decoder_; 149 HalfDecoder half_decoder_; 150 }; 151 152 // Decodes a point cloud from |buffer|. 153 template <class PointDiT, int compression_level_t> 154 template <class OutputIteratorT> 155 bool IntegerPointsKdTreeDecoder<PointDiT, compression_level_t>::DecodePoints( 156 DecoderBuffer *buffer, OutputIteratorT oit) { 157 if (!buffer->Decode(&bit_length_)) { 158 return false; 159 } 160 if (!buffer->Decode(&num_points_)) { 161 return false; 162 } 163 if (num_points_ == 0) { 164 return true; 165 } 166 167 if (!numbers_decoder_.StartDecoding(buffer)) { 168 return false; 169 } 170 if (!remaining_bits_decoder_.StartDecoding(buffer)) { 171 return false; 172 } 173 if (!axis_decoder_.StartDecoding(buffer)) { 174 return false; 175 } 176 if (!half_decoder_.StartDecoding(buffer)) { 177 return false; 178 } 179 180 DecodeInternal(num_points_, PointTraits<PointDiT>::Origin(), 181 PointTraits<PointDiT>::ZeroArray(), 0, oit); 182 183 numbers_decoder_.EndDecoding(); 184 remaining_bits_decoder_.EndDecoding(); 185 axis_decoder_.EndDecoding(); 186 half_decoder_.EndDecoding(); 187 188 return true; 189 } 190 191 template <class PointDiT, int compression_level_t> 192 uint32_t IntegerPointsKdTreeDecoder<PointDiT, compression_level_t>::GetAxis( 193 uint32_t num_remaining_points, const PointDiT & /* base */, 194 std::array<uint32_t, D> levels, uint32_t last_axis) { 195 if (!Policy::select_axis) { 196 return DRACO_INCREMENT_MOD(last_axis, D); 197 } 198 199 uint32_t best_axis = 0; 200 if (num_remaining_points < 64) { 201 for (uint32_t axis = 1; axis < D; ++axis) { 202 if (levels[best_axis] > levels[axis]) { 203 best_axis = axis; 204 } 205 } 206 } else { 207 axis_decoder_.DecodeLeastSignificantBits32(4, &best_axis); 208 } 209 210 return best_axis; 211 } 212 213 template <class PointDiT, int compression_level_t> 214 template <class OutputIteratorT> 215 void IntegerPointsKdTreeDecoder<PointDiT, compression_level_t>::DecodeInternal( 216 uint32_t num_remaining_points, PointDiT old_base, 217 std::array<uint32_t, D> levels, uint32_t last_axis, OutputIteratorT oit) { 218 DecodingStatus init_status(num_remaining_points, old_base, levels, last_axis); 219 typename Policy::template QueuingStrategy<DecodingStatus> status_q; 220 status_q.push(init_status); 221 222 while (!status_q.empty()) { 223 const DecodingStatus status = status_q.front(); 224 status_q.pop(); 225 226 num_remaining_points = status.num_remaining_points; 227 old_base = status.old_base; 228 levels = status.levels; 229 last_axis = status.last_axis; 230 231 const uint32_t axis = 232 GetAxis(num_remaining_points, old_base, levels, last_axis); 233 234 const uint32_t level = levels[axis]; 235 236 // All axes have been fully subdivided, just output points. 237 if ((bit_length_ - level) == 0) { 238 for (int i = 0; i < static_cast<int>(num_remaining_points); i++) { 239 *oit++ = old_base; 240 } 241 continue; 242 } 243 244 DRACO_DCHECK_EQ(true, num_remaining_points != 0); 245 if (num_remaining_points <= 2) { 246 std::array<uint32_t, D> axes; 247 axes[0] = axis; 248 for (int i = 1; i < D; i++) { 249 axes[i] = DRACO_INCREMENT_MOD(axes[i - 1], D); 250 } 251 252 std::array<uint32_t, D> num_remaining_bits; 253 for (int i = 0; i < D; i++) { 254 num_remaining_bits[i] = bit_length_ - levels[axes[i]]; 255 } 256 257 for (uint32_t i = 0; i < num_remaining_points; ++i) { 258 // Get remaining bits, mind the carry if not starting at x. 259 PointDiT p = PointTraits<PointDiT>::Origin(); 260 for (int j = 0; j < static_cast<int>(D); j++) { 261 if (num_remaining_bits[j]) { 262 remaining_bits_decoder_.DecodeLeastSignificantBits32( 263 num_remaining_bits[j], &p[axes[j]]); 264 } 265 p[axes[j]] = old_base[axes[j]] | p[axes[j]]; 266 } 267 *oit++ = p; 268 } 269 continue; 270 } 271 272 const int num_remaining_bits = bit_length_ - level; 273 const uint32_t modifier = 1 << (num_remaining_bits - 1); 274 PointDiT new_base(old_base); 275 new_base[axis] += modifier; 276 277 const int incoming_bits = MostSignificantBit(num_remaining_points); 278 279 uint32_t number = 0; 280 DecodeNumber(incoming_bits, &number); 281 282 uint32_t first_half = num_remaining_points / 2 - number; 283 uint32_t second_half = num_remaining_points - first_half; 284 285 if (first_half != second_half) { 286 if (!half_decoder_.DecodeNextBit()) { 287 std::swap(first_half, second_half); 288 } 289 } 290 291 levels[axis] += 1; 292 if (first_half) { 293 status_q.push(DecodingStatus(first_half, old_base, levels, axis)); 294 } 295 if (second_half) { 296 status_q.push(DecodingStatus(second_half, new_base, levels, axis)); 297 } 298 } 299 } 300 301 extern template class IntegerPointsKdTreeDecoder<Point3ui, 0>; 302 extern template class IntegerPointsKdTreeDecoder<Point3ui, 1>; 303 extern template class IntegerPointsKdTreeDecoder<Point3ui, 2>; 304 extern template class IntegerPointsKdTreeDecoder<Point3ui, 3>; 305 extern template class IntegerPointsKdTreeDecoder<Point3ui, 4>; 306 extern template class IntegerPointsKdTreeDecoder<Point3ui, 5>; 307 extern template class IntegerPointsKdTreeDecoder<Point3ui, 6>; 308 extern template class IntegerPointsKdTreeDecoder<Point3ui, 7>; 309 extern template class IntegerPointsKdTreeDecoder<Point3ui, 8>; 310 extern template class IntegerPointsKdTreeDecoder<Point3ui, 9>; 311 extern template class IntegerPointsKdTreeDecoder<Point3ui, 10>; 312 313 } // namespace draco 314 315 #endif // DRACO_COMPRESSION_POINT_CLOUD_ALGORITHMS_INTEGER_POINTS_KD_TREE_DECODER_H_ 316