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