Draco §

https://github.com/google/draco

Compression Level §

通过模板参数进行自动配置 class 内参数

// 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;
};

量化 §

float32 -> int32_t

类似于 range image 方法将 $\theta$ 和 $\varphi$ 映射到栅格. 这个量化方法将 float32 映射到 $2^k$ 个格子里面

$$\text{index}=\frac{2^{\text{Q Bits}}}{\max (\text{bbox})}\ast (\text{xyz}-\min (\text{bbox}))$$

浮点数就会映射到 $1\sim 2^{32}$ 的无符号整型

// Class for quantizing single precision floating point values. The values
// should be centered around zero and be within interval (-range, +range), where
// the range is specified in the Init() method. Alternatively, the quantization
// can be defined by |delta| that specifies the distance between two quantized
// values. Note that the quantizer always snaps the values to the nearest
// integer value. E.g. for |delta| == 1.f, values -0.4f and 0.4f would be
// both quantized to 0 while value 0.6f would be quantized to 1. If a value
// lies exactly between two quantized states, it is always rounded up. E.g.,
// for |delta| == 1.f, value -0.5f would be quantized to 0 while 0.5f would be
// quantized to 1.
class Quantizer {
 public:
  Quantizer();
  void Init(float range, int32_t max_quantized_value);
  void Init(float delta);
  inline int32_t QuantizeFloat(float val) const {
    val *= inverse_delta_;
    return static_cast<int32_t>(floor(val + 0.5f));
  }
  inline int32_t operator()(float val) const { return QuantizeFloat(val); }
 
 private:
  float inverse_delta_;
};
 
 
Quantizer::Quantizer() : inverse_delta_(1.f) {}
 
void Quantizer::Init(float range, int32_t max_quantized_value) {
  inverse_delta_ = static_cast<float>(max_quantized_value) / range;
}
 
void Quantizer::Init(float delta) { inverse_delta_ = 1.f / delta; }

基于 KD-Tree 的方法 §

核心入口

主要分为

1. 将 float32 转为 int32_t LINK
2. 使用 kdtree encode axis LINK
3. 最后 encode 相对于二分轴的偏移量 LINK

例如在 5 bit 情况下的浪费 bit 位

工具方法 §

MostSignificantBit §

根据不同编译器优化计算 uint32_t 类型变量所用 bit 位, 这样可能可以找到比用户预设的 Quantizer bit 还要小的 bit 位数目

// Returns the location of the most significant bit in the input integer |n|.
// The functionality is not defined for |n == 0|.
inline int MostSignificantBit(uint32_t n) {
#if defined(__GNUC__)
  return 31 ^ __builtin_clz(n);
#elif defined(_MSC_VER)
 
  unsigned long where;
  _BitScanReverse(&where, n);
  return (int)where;
#else
  // TODO(fgalligan): Optimize this code.
  int msb = -1;
  while (n != 0) {
    msb++;
    n >>= 1;
  }
  return msb;
#endif
}

Encode §

使用 reinterpret_cast<const uint8_t *> 将任意数据类型编码为 Byte(8bit) 数组. buffer 为 std::vector<char> 类型, 通常情况下 len(bits) >= 8

  // Encode an arbitrary data type.
  // Can be used only when we are not encoding a bit-sequence.
  // Returns false when the value couldn't be encoded.
  template <typename T>
  bool Encode(const T &data) {
    if (bit_encoder_active()) {
      return false;
    }
    const uint8_t *src_data = reinterpret_cast<const uint8_t *>(&data);
    buffer_.insert(buffer_.end(), src_data, src_data + sizeof(T));
    return true;
  }
  bool Encode(const void *data, size_t data_size) {
    if (bit_encoder_active()) {
      return false;
    }
    const uint8_t *src_data = reinterpret_cast<const uint8_t *>(data);
    buffer_.insert(buffer_.end(), src_data, src_data + data_size);
    return true;
  }