Differential D4501 Diff 14677 extern/draco/dracoenc/src/draco/compression/point_cloud/algorithms/dynamic_integer_points_kd_tree_encoder.h
Changeset View
Changeset View
Standalone View
Standalone View
extern/draco/dracoenc/src/draco/compression/point_cloud/algorithms/dynamic_integer_points_kd_tree_encoder.h
- This file was added.
| // Copyright 2016 The Draco Authors. | |||||
| // | |||||
| // Licensed under the Apache License, Version 2.0 (the "License"); | |||||
| // you may not use this file except in compliance with the License. | |||||
| // You may obtain a copy of the License at | |||||
| // | |||||
| // http://www.apache.org/licenses/LICENSE-2.0 | |||||
| // | |||||
| // Unless required by applicable law or agreed to in writing, software | |||||
| // distributed under the License is distributed on an "AS IS" BASIS, | |||||
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |||||
| // See the License for the specific language governing permissions and | |||||
| // limitations under the License. | |||||
| // | |||||
| #ifndef DRACO_COMPRESSION_POINT_CLOUD_ALGORITHMS_DYNAMIC_INTEGER_POINTS_KD_TREE_ENCODER_H_ | |||||
| #define DRACO_COMPRESSION_POINT_CLOUD_ALGORITHMS_DYNAMIC_INTEGER_POINTS_KD_TREE_ENCODER_H_ | |||||
| #include <algorithm> | |||||
| #include <array> | |||||
| #include <memory> | |||||
| #include <stack> | |||||
| #include <vector> | |||||
| #include "draco/compression/bit_coders/adaptive_rans_bit_encoder.h" | |||||
| #include "draco/compression/bit_coders/direct_bit_encoder.h" | |||||
| #include "draco/compression/bit_coders/folded_integer_bit_encoder.h" | |||||
| #include "draco/compression/bit_coders/rans_bit_encoder.h" | |||||
| #include "draco/compression/point_cloud/algorithms/point_cloud_types.h" | |||||
| #include "draco/core/bit_utils.h" | |||||
| #include "draco/core/encoder_buffer.h" | |||||
| #include "draco/core/math_utils.h" | |||||
| namespace draco { | |||||
| // This policy class provides several configurations for the encoder that allow | |||||
| // to trade speed vs compression rate. Level 0 is fastest while 6 is the best | |||||
| // compression rate. The decoder must select the same level. | |||||
| template <int compression_level_t> | |||||
| struct DynamicIntegerPointsKdTreeEncoderCompressionPolicy | |||||
| : public DynamicIntegerPointsKdTreeEncoderCompressionPolicy< | |||||
| compression_level_t - 1> {}; | |||||
| template <> | |||||
| struct DynamicIntegerPointsKdTreeEncoderCompressionPolicy<0> { | |||||
| typedef DirectBitEncoder NumbersEncoder; | |||||
| typedef DirectBitEncoder AxisEncoder; | |||||
| typedef DirectBitEncoder HalfEncoder; | |||||
| typedef DirectBitEncoder RemainingBitsEncoder; | |||||
| static constexpr bool select_axis = false; | |||||
| }; | |||||
| template <> | |||||
| struct DynamicIntegerPointsKdTreeEncoderCompressionPolicy<2> | |||||
| : public DynamicIntegerPointsKdTreeEncoderCompressionPolicy<1> { | |||||
| typedef RAnsBitEncoder NumbersEncoder; | |||||
| }; | |||||
| template <> | |||||
| struct DynamicIntegerPointsKdTreeEncoderCompressionPolicy<4> | |||||
| : public DynamicIntegerPointsKdTreeEncoderCompressionPolicy<3> { | |||||
| typedef FoldedBit32Encoder<RAnsBitEncoder> NumbersEncoder; | |||||
| }; | |||||
| template <> | |||||
| struct DynamicIntegerPointsKdTreeEncoderCompressionPolicy<6> | |||||
| : public DynamicIntegerPointsKdTreeEncoderCompressionPolicy<5> { | |||||
| static constexpr bool select_axis = true; | |||||
| }; | |||||
| // This class encodes a given integer point cloud based on the point cloud | |||||
| // compression algorithm in: | |||||
| // Olivier Devillers and Pierre-Marie Gandoin | |||||
| // "Geometric compression for interactive transmission" | |||||
| // | |||||
| // In principle the algorithm keeps on splitting the point cloud in the middle | |||||
| // while alternating the axes. In 3D this results in an Octree like structure. | |||||
| // In each step we encode the number of points in the first half. | |||||
| // The algorithm does not preserve the order of points. | |||||
| // | |||||
| // However, the algorithm here differs from the original as follows: | |||||
| // The algorithm keeps on splitting the point cloud in the middle of the axis | |||||
| // that keeps the point cloud as clustered as possible, which gives a better | |||||
| // compression rate. | |||||
| // The number of points is encode by the deviation from the half of the points | |||||
| // in the smaller half of the two. This results in a better compression rate as | |||||
| // there are more leading zeros, which is then compressed better by the | |||||
| // arithmetic encoding. | |||||
| template <int compression_level_t> | |||||
| class DynamicIntegerPointsKdTreeEncoder { | |||||
| static_assert(compression_level_t >= 0, "Compression level must in [0..6]."); | |||||
| static_assert(compression_level_t <= 6, "Compression level must in [0..6]."); | |||||
| typedef DynamicIntegerPointsKdTreeEncoderCompressionPolicy< | |||||
| compression_level_t> | |||||
| Policy; | |||||
| typedef typename Policy::NumbersEncoder NumbersEncoder; | |||||
| typedef typename Policy::AxisEncoder AxisEncoder; | |||||
| typedef typename Policy::HalfEncoder HalfEncoder; | |||||
| typedef typename Policy::RemainingBitsEncoder RemainingBitsEncoder; | |||||
| typedef std::vector<uint32_t> VectorUint32; | |||||
| public: | |||||
| explicit DynamicIntegerPointsKdTreeEncoder(uint32_t dimension) | |||||
| : bit_length_(0), | |||||
| dimension_(dimension), | |||||
| deviations_(dimension, 0), | |||||
| num_remaining_bits_(dimension, 0), | |||||
| axes_(dimension, 0), | |||||
| base_stack_(32 * dimension + 1, VectorUint32(dimension, 0)), | |||||
| levels_stack_(32 * dimension + 1, VectorUint32(dimension, 0)) {} | |||||
| // Encodes an integer point cloud given by [begin,end) into buffer. | |||||
| // |bit_length| gives the highest bit used for all coordinates. | |||||
| template <class RandomAccessIteratorT> | |||||
| bool EncodePoints(RandomAccessIteratorT begin, RandomAccessIteratorT end, | |||||
| const uint32_t &bit_length, EncoderBuffer *buffer); | |||||
| // Encodes an integer point cloud given by [begin,end) into buffer. | |||||
| template <class RandomAccessIteratorT> | |||||
| bool EncodePoints(RandomAccessIteratorT begin, RandomAccessIteratorT end, | |||||
| EncoderBuffer *buffer) { | |||||
| return EncodePoints(begin, end, 32, buffer); | |||||
| } | |||||
| const uint32_t dimension() const { return dimension_; } | |||||
| private: | |||||
| template <class RandomAccessIteratorT> | |||||
| uint32_t GetAndEncodeAxis(RandomAccessIteratorT begin, | |||||
| RandomAccessIteratorT end, | |||||
| const VectorUint32 &old_base, | |||||
| const VectorUint32 &levels, uint32_t last_axis); | |||||
| template <class RandomAccessIteratorT> | |||||
| void EncodeInternal(RandomAccessIteratorT begin, RandomAccessIteratorT end); | |||||
| class Splitter { | |||||
| public: | |||||
| Splitter(uint32_t axis, uint32_t value) : axis_(axis), value_(value) {} | |||||
| template <class PointT> | |||||
| bool operator()(const PointT &a) const { | |||||
| return a[axis_] < value_; | |||||
| } | |||||
| private: | |||||
| const uint32_t axis_; | |||||
| const uint32_t value_; | |||||
| }; | |||||
| void EncodeNumber(int nbits, uint32_t value) { | |||||
| numbers_encoder_.EncodeLeastSignificantBits32(nbits, value); | |||||
| } | |||||
| template <class RandomAccessIteratorT> | |||||
| struct EncodingStatus { | |||||
| EncodingStatus(RandomAccessIteratorT begin_, RandomAccessIteratorT end_, | |||||
| uint32_t last_axis_, uint32_t stack_pos_) | |||||
| : begin(begin_), | |||||
| end(end_), | |||||
| last_axis(last_axis_), | |||||
| stack_pos(stack_pos_) { | |||||
| num_remaining_points = static_cast<uint32_t>(end - begin); | |||||
| } | |||||
| RandomAccessIteratorT begin; | |||||
| RandomAccessIteratorT end; | |||||
| uint32_t last_axis; | |||||
| uint32_t num_remaining_points; | |||||
| uint32_t stack_pos; // used to get base and levels | |||||
| }; | |||||
| uint32_t bit_length_; | |||||
| uint32_t num_points_; | |||||
| uint32_t dimension_; | |||||
| NumbersEncoder numbers_encoder_; | |||||
| RemainingBitsEncoder remaining_bits_encoder_; | |||||
| AxisEncoder axis_encoder_; | |||||
| HalfEncoder half_encoder_; | |||||
| VectorUint32 deviations_; | |||||
| VectorUint32 num_remaining_bits_; | |||||
| VectorUint32 axes_; | |||||
| std::vector<VectorUint32> base_stack_; | |||||
| std::vector<VectorUint32> levels_stack_; | |||||
| }; | |||||
| template <int compression_level_t> | |||||
| template <class RandomAccessIteratorT> | |||||
| bool DynamicIntegerPointsKdTreeEncoder<compression_level_t>::EncodePoints( | |||||
| RandomAccessIteratorT begin, RandomAccessIteratorT end, | |||||
| const uint32_t &bit_length, EncoderBuffer *buffer) { | |||||
| bit_length_ = bit_length; | |||||
| num_points_ = static_cast<uint32_t>(end - begin); | |||||
| buffer->Encode(bit_length_); | |||||
| buffer->Encode(num_points_); | |||||
| if (num_points_ == 0) | |||||
| return true; | |||||
| numbers_encoder_.StartEncoding(); | |||||
| remaining_bits_encoder_.StartEncoding(); | |||||
| axis_encoder_.StartEncoding(); | |||||
| half_encoder_.StartEncoding(); | |||||
| EncodeInternal(begin, end); | |||||
| numbers_encoder_.EndEncoding(buffer); | |||||
| remaining_bits_encoder_.EndEncoding(buffer); | |||||
| axis_encoder_.EndEncoding(buffer); | |||||
| half_encoder_.EndEncoding(buffer); | |||||
| return true; | |||||
| } | |||||
| template <int compression_level_t> | |||||
| template <class RandomAccessIteratorT> | |||||
| uint32_t | |||||
| DynamicIntegerPointsKdTreeEncoder<compression_level_t>::GetAndEncodeAxis( | |||||
| RandomAccessIteratorT begin, RandomAccessIteratorT end, | |||||
| const VectorUint32 &old_base, const VectorUint32 &levels, | |||||
| uint32_t last_axis) { | |||||
| if (!Policy::select_axis) | |||||
| return DRACO_INCREMENT_MOD(last_axis, dimension_); | |||||
| // For many points this function selects the axis that should be used | |||||
| // for the split by keeping as many points as possible bundled. | |||||
| // In the best case we do not split the point cloud at all. | |||||
| // For lower number of points, we simply choose the axis that is refined the | |||||
| // least so far. | |||||
| DRACO_DCHECK_EQ(true, end - begin != 0); | |||||
| uint32_t best_axis = 0; | |||||
| if (end - begin < 64) { | |||||
| for (uint32_t axis = 1; axis < dimension_; ++axis) { | |||||
| if (levels[best_axis] > levels[axis]) { | |||||
| best_axis = axis; | |||||
| } | |||||
| } | |||||
| } else { | |||||
| const uint32_t size = static_cast<uint32_t>(end - begin); | |||||
| for (uint32_t i = 0; i < dimension_; i++) { | |||||
| deviations_[i] = 0; | |||||
| num_remaining_bits_[i] = bit_length_ - levels[i]; | |||||
| if (num_remaining_bits_[i] > 0) { | |||||
| const uint32_t split = | |||||
| old_base[i] + (1 << (num_remaining_bits_[i] - 1)); | |||||
| for (auto it = begin; it != end; ++it) { | |||||
| deviations_[i] += ((*it)[i] < split); | |||||
| } | |||||
| deviations_[i] = std::max(size - deviations_[i], deviations_[i]); | |||||
| } | |||||
| } | |||||
| uint32_t max_value = 0; | |||||
| best_axis = 0; | |||||
| for (uint32_t i = 0; i < dimension_; i++) { | |||||
| // If axis can be subdivided. | |||||
| if (num_remaining_bits_[i]) { | |||||
| // Check if this is the better axis. | |||||
| if (max_value < deviations_[i]) { | |||||
| max_value = deviations_[i]; | |||||
| best_axis = i; | |||||
| } | |||||
| } | |||||
| } | |||||
| axis_encoder_.EncodeLeastSignificantBits32(4, best_axis); | |||||
| } | |||||
| return best_axis; | |||||
| } | |||||
| template <int compression_level_t> | |||||
| template <class RandomAccessIteratorT> | |||||
| void DynamicIntegerPointsKdTreeEncoder<compression_level_t>::EncodeInternal( | |||||
| RandomAccessIteratorT begin, RandomAccessIteratorT end) { | |||||
| typedef EncodingStatus<RandomAccessIteratorT> Status; | |||||
| base_stack_[0] = VectorUint32(dimension_, 0); | |||||
| levels_stack_[0] = VectorUint32(dimension_, 0); | |||||
| Status init_status(begin, end, 0, 0); | |||||
| std::stack<Status> status_stack; | |||||
| status_stack.push(init_status); | |||||
| // TODO(hemmer): use preallocated vector instead of stack. | |||||
| while (!status_stack.empty()) { | |||||
| Status status = status_stack.top(); | |||||
| status_stack.pop(); | |||||
| begin = status.begin; | |||||
| end = status.end; | |||||
| const uint32_t last_axis = status.last_axis; | |||||
| const uint32_t stack_pos = status.stack_pos; | |||||
| const VectorUint32 &old_base = base_stack_[stack_pos]; | |||||
| const VectorUint32 &levels = levels_stack_[stack_pos]; | |||||
| const uint32_t axis = | |||||
| GetAndEncodeAxis(begin, end, old_base, levels, last_axis); | |||||
| const uint32_t level = levels[axis]; | |||||
| const uint32_t num_remaining_points = static_cast<uint32_t>(end - begin); | |||||
| // If this happens all axis are subdivided to the end. | |||||
| if ((bit_length_ - level) == 0) | |||||
| continue; | |||||
| // Fast encoding of remaining bits if number of points is 1 or 2. | |||||
| // Doing this also for 2 gives a slight additional speed up. | |||||
| if (num_remaining_points <= 2) { | |||||
| // TODO(hemmer): axes_ not necessary, remove would change bitstream! | |||||
| axes_[0] = axis; | |||||
| for (uint32_t i = 1; i < dimension_; i++) { | |||||
| axes_[i] = DRACO_INCREMENT_MOD(axes_[i - 1], dimension_); | |||||
| } | |||||
| for (uint32_t i = 0; i < num_remaining_points; ++i) { | |||||
| const auto &p = *(begin + i); | |||||
| for (uint32_t j = 0; j < dimension_; j++) { | |||||
| const uint32_t num_remaining_bits = bit_length_ - levels[axes_[j]]; | |||||
| if (num_remaining_bits) { | |||||
| remaining_bits_encoder_.EncodeLeastSignificantBits32( | |||||
| num_remaining_bits, p[axes_[j]]); | |||||
| } | |||||
| } | |||||
| } | |||||
| continue; | |||||
| } | |||||
| const uint32_t num_remaining_bits = bit_length_ - level; | |||||
| const uint32_t modifier = 1 << (num_remaining_bits - 1); | |||||
| base_stack_[stack_pos + 1] = old_base; // copy | |||||
| base_stack_[stack_pos + 1][axis] += modifier; | |||||
| const VectorUint32 &new_base = base_stack_[stack_pos + 1]; | |||||
| const RandomAccessIteratorT split = | |||||
| std::partition(begin, end, Splitter(axis, new_base[axis])); | |||||
| DRACO_DCHECK_EQ(true, (end - begin) > 0); | |||||
| // Encode number of points in first and second half. | |||||
| const int required_bits = MostSignificantBit(num_remaining_points); | |||||
| const uint32_t first_half = static_cast<uint32_t>(split - begin); | |||||
| const uint32_t second_half = static_cast<uint32_t>(end - split); | |||||
| const bool left = first_half < second_half; | |||||
| if (first_half != second_half) | |||||
| half_encoder_.EncodeBit(left); | |||||
| if (left) { | |||||
| EncodeNumber(required_bits, num_remaining_points / 2 - first_half); | |||||
| } else { | |||||
| EncodeNumber(required_bits, num_remaining_points / 2 - second_half); | |||||
| } | |||||
| levels_stack_[stack_pos][axis] += 1; | |||||
| levels_stack_[stack_pos + 1] = levels_stack_[stack_pos]; // copy | |||||
| if (split != begin) | |||||
| status_stack.push(Status(begin, split, axis, stack_pos)); | |||||
| if (split != end) | |||||
| status_stack.push(Status(split, end, axis, stack_pos + 1)); | |||||
| } | |||||
| } | |||||
| extern template class DynamicIntegerPointsKdTreeEncoder<0>; | |||||
| extern template class DynamicIntegerPointsKdTreeEncoder<2>; | |||||
| extern template class DynamicIntegerPointsKdTreeEncoder<4>; | |||||
| extern template class DynamicIntegerPointsKdTreeEncoder<6>; | |||||
| } // namespace draco | |||||
| #endif // DRACO_COMPRESSION_POINT_CLOUD_ALGORITHMS_DYNAMIC_INTEGER_POINTS_KD_TREE_ENCODER_H_ | |||||