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 #include "draco/compression/attributes/kd_tree_attributes_encoder.h"
16 #include "draco/compression/attributes/kd_tree_attributes_shared.h"
17 #include "draco/compression/attributes/point_d_vector.h"
18 #include "draco/compression/point_cloud/algorithms/dynamic_integer_points_kd_tree_encoder.h"
19 #include "draco/compression/point_cloud/algorithms/float_points_tree_encoder.h"
20 #include "draco/compression/point_cloud/point_cloud_encoder.h"
21 #include "draco/core/varint_encoding.h"
22
23 namespace draco {
24
KdTreeAttributesEncoder()25 KdTreeAttributesEncoder::KdTreeAttributesEncoder() : num_components_(0) {}
26
KdTreeAttributesEncoder(int att_id)27 KdTreeAttributesEncoder::KdTreeAttributesEncoder(int att_id)
28 : AttributesEncoder(att_id), num_components_(0) {}
29
TransformAttributesToPortableFormat()30 bool KdTreeAttributesEncoder::TransformAttributesToPortableFormat() {
31 // Convert any of the input attributes into a format that can be processed by
32 // the kd tree encoder (quantization of floating attributes for now).
33 const size_t num_points = encoder()->point_cloud()->num_points();
34 int num_components = 0;
35 for (uint32_t i = 0; i < num_attributes(); ++i) {
36 const int att_id = GetAttributeId(i);
37 const PointAttribute *const att =
38 encoder()->point_cloud()->attribute(att_id);
39 num_components += att->num_components();
40 }
41 num_components_ = num_components;
42
43 // Go over all attributes and quantize them if needed.
44 for (uint32_t i = 0; i < num_attributes(); ++i) {
45 const int att_id = GetAttributeId(i);
46 const PointAttribute *const att =
47 encoder()->point_cloud()->attribute(att_id);
48 if (att->data_type() == DT_FLOAT32) {
49 // Quantization path.
50 AttributeQuantizationTransform attribute_quantization_transform;
51 const int quantization_bits = encoder()->options()->GetAttributeInt(
52 att_id, "quantization_bits", -1);
53 if (quantization_bits < 1)
54 return false;
55 if (encoder()->options()->IsAttributeOptionSet(att_id,
56 "quantization_origin") &&
57 encoder()->options()->IsAttributeOptionSet(att_id,
58 "quantization_range")) {
59 // Quantization settings are explicitly specified in the provided
60 // options.
61 std::vector<float> quantization_origin(att->num_components());
62 encoder()->options()->GetAttributeVector(att_id, "quantization_origin",
63 att->num_components(),
64 &quantization_origin[0]);
65 const float range = encoder()->options()->GetAttributeFloat(
66 att_id, "quantization_range", 1.f);
67 attribute_quantization_transform.SetParameters(
68 quantization_bits, quantization_origin.data(),
69 att->num_components(), range);
70 } else {
71 // Compute quantization settings from the attribute values.
72 attribute_quantization_transform.ComputeParameters(*att,
73 quantization_bits);
74 }
75 attribute_quantization_transforms_.push_back(
76 attribute_quantization_transform);
77 // Store the quantized attribute in an array that will be used when we do
78 // the actual encoding of the data.
79 quantized_portable_attributes_.push_back(
80 attribute_quantization_transform.GeneratePortableAttribute(
81 *att, static_cast<int>(num_points)));
82 } else if (att->data_type() == DT_INT32 || att->data_type() == DT_INT16 ||
83 att->data_type() == DT_INT8) {
84 // For signed types, find the minimum value for each component. These
85 // values are going to be used to transform the attribute values to
86 // unsigned integers that can be processed by the core kd tree algorithm.
87 std::vector<int32_t> min_value(att->num_components(),
88 std::numeric_limits<int32_t>::max());
89 std::vector<int32_t> act_value(att->num_components());
90 for (AttributeValueIndex avi(0); avi < static_cast<uint32_t>(att->size());
91 ++avi) {
92 att->ConvertValue<int32_t>(avi, &act_value[0]);
93 for (int c = 0; c < att->num_components(); ++c) {
94 if (min_value[c] > act_value[c])
95 min_value[c] = act_value[c];
96 }
97 }
98 for (int c = 0; c < att->num_components(); ++c) {
99 min_signed_values_.push_back(min_value[c]);
100 }
101 }
102 }
103 return true;
104 }
105
EncodeDataNeededByPortableTransforms(EncoderBuffer * out_buffer)106 bool KdTreeAttributesEncoder::EncodeDataNeededByPortableTransforms(
107 EncoderBuffer *out_buffer) {
108 // Store quantization settings for all attributes that need it.
109 for (int i = 0; i < attribute_quantization_transforms_.size(); ++i) {
110 attribute_quantization_transforms_[i].EncodeParameters(out_buffer);
111 }
112
113 // Encode data needed for transforming signed integers to unsigned ones.
114 for (int i = 0; i < min_signed_values_.size(); ++i) {
115 EncodeVarint<int32_t>(min_signed_values_[i], out_buffer);
116 }
117 return true;
118 }
119
EncodePortableAttributes(EncoderBuffer * out_buffer)120 bool KdTreeAttributesEncoder::EncodePortableAttributes(
121 EncoderBuffer *out_buffer) {
122 // Encode the data using the kd tree encoder algorithm. The data is first
123 // copied to a PointDVector that provides all the API expected by the core
124 // encoding algorithm.
125
126 // We limit the maximum value of compression_level to 6 as we don't currently
127 // have viable algorithms for higher compression levels.
128 uint8_t compression_level =
129 std::min(10 - encoder()->options()->GetSpeed(), 6);
130 DRACO_DCHECK_LE(compression_level, 6);
131
132 if (compression_level == 6 && num_components_ > 15) {
133 // Don't use compression level for CL >= 6. Axis selection is currently
134 // encoded using 4 bits.
135 compression_level = 5;
136 }
137
138 out_buffer->Encode(compression_level);
139
140 // Init PointDVector. The number of dimensions is equal to the total number
141 // of dimensions across all attributes.
142 const int num_points = encoder()->point_cloud()->num_points();
143 PointDVector<uint32_t> point_vector(num_points, num_components_);
144
145 int num_processed_components = 0;
146 int num_processed_quantized_attributes = 0;
147 int num_processed_signed_components = 0;
148 // Copy data to the point vector.
149 for (uint32_t i = 0; i < num_attributes(); ++i) {
150 const int att_id = GetAttributeId(i);
151 const PointAttribute *const att =
152 encoder()->point_cloud()->attribute(att_id);
153 const PointAttribute *source_att = nullptr;
154 if (att->data_type() == DT_UINT32 || att->data_type() == DT_UINT16 ||
155 att->data_type() == DT_UINT8 || att->data_type() == DT_INT32 ||
156 att->data_type() == DT_INT16 || att->data_type() == DT_INT8) {
157 // Use the original attribute.
158 source_att = att;
159 } else if (att->data_type() == DT_FLOAT32) {
160 // Use the portable (quantized) attribute instead.
161 source_att =
162 quantized_portable_attributes_[num_processed_quantized_attributes]
163 .get();
164 num_processed_quantized_attributes++;
165 } else {
166 // Unsupported data type.
167 return false;
168 }
169
170 if (source_att == nullptr)
171 return false;
172
173 // Copy source_att to the vector.
174 if (source_att->data_type() == DT_UINT32) {
175 // If the data type is the same as the one used by the point vector, we
176 // can directly copy individual elements.
177 for (PointIndex pi(0); pi < num_points; ++pi) {
178 const AttributeValueIndex avi = source_att->mapped_index(pi);
179 const uint8_t *const att_value_address = source_att->GetAddress(avi);
180 point_vector.CopyAttribute(source_att->num_components(),
181 num_processed_components, pi.value(),
182 att_value_address);
183 }
184 } else if (source_att->data_type() == DT_INT32 ||
185 source_att->data_type() == DT_INT16 ||
186 source_att->data_type() == DT_INT8) {
187 // Signed values need to be converted to unsigned before they are stored
188 // in the point vector.
189 std::vector<int32_t> signed_point(source_att->num_components());
190 std::vector<uint32_t> unsigned_point(source_att->num_components());
191 for (PointIndex pi(0); pi < num_points; ++pi) {
192 const AttributeValueIndex avi = source_att->mapped_index(pi);
193 source_att->ConvertValue<int32_t>(avi, &signed_point[0]);
194 for (int c = 0; c < source_att->num_components(); ++c) {
195 unsigned_point[c] =
196 signed_point[c] -
197 min_signed_values_[num_processed_signed_components + c];
198 }
199
200 point_vector.CopyAttribute(source_att->num_components(),
201 num_processed_components, pi.value(),
202 &unsigned_point[0]);
203 }
204 num_processed_signed_components += source_att->num_components();
205 } else {
206 // If the data type of the attribute is different, we have to convert the
207 // value before we put it to the point vector.
208 std::vector<uint32_t> point(source_att->num_components());
209 for (PointIndex pi(0); pi < num_points; ++pi) {
210 const AttributeValueIndex avi = source_att->mapped_index(pi);
211 source_att->ConvertValue<uint32_t>(avi, &point[0]);
212 point_vector.CopyAttribute(source_att->num_components(),
213 num_processed_components, pi.value(),
214 point.data());
215 }
216 }
217 num_processed_components += source_att->num_components();
218 }
219
220 // Compute the maximum bit length needed for the kd tree encoding.
221 int num_bits = 0;
222 const uint32_t *data = point_vector[0];
223 for (int i = 0; i < num_points * num_components_; ++i) {
224 if (data[i] > 0) {
225 const int msb = MostSignificantBit(data[i]) + 1;
226 if (msb > num_bits) {
227 num_bits = msb;
228 }
229 }
230 }
231
232 switch (compression_level) {
233 case 6: {
234 DynamicIntegerPointsKdTreeEncoder<6> points_encoder(num_components_);
235 if (!points_encoder.EncodePoints(point_vector.begin(), point_vector.end(),
236 num_bits, out_buffer))
237 return false;
238 break;
239 }
240 case 5: {
241 DynamicIntegerPointsKdTreeEncoder<5> points_encoder(num_components_);
242 if (!points_encoder.EncodePoints(point_vector.begin(), point_vector.end(),
243 num_bits, out_buffer))
244 return false;
245 break;
246 }
247 case 4: {
248 DynamicIntegerPointsKdTreeEncoder<4> points_encoder(num_components_);
249 if (!points_encoder.EncodePoints(point_vector.begin(), point_vector.end(),
250 num_bits, out_buffer))
251 return false;
252 break;
253 }
254 case 3: {
255 DynamicIntegerPointsKdTreeEncoder<3> points_encoder(num_components_);
256 if (!points_encoder.EncodePoints(point_vector.begin(), point_vector.end(),
257 num_bits, out_buffer))
258 return false;
259 break;
260 }
261 case 2: {
262 DynamicIntegerPointsKdTreeEncoder<2> points_encoder(num_components_);
263 if (!points_encoder.EncodePoints(point_vector.begin(), point_vector.end(),
264 num_bits, out_buffer))
265 return false;
266 break;
267 }
268 case 1: {
269 DynamicIntegerPointsKdTreeEncoder<1> points_encoder(num_components_);
270 if (!points_encoder.EncodePoints(point_vector.begin(), point_vector.end(),
271 num_bits, out_buffer))
272 return false;
273 break;
274 }
275 case 0: {
276 DynamicIntegerPointsKdTreeEncoder<0> points_encoder(num_components_);
277 if (!points_encoder.EncodePoints(point_vector.begin(), point_vector.end(),
278 num_bits, out_buffer))
279 return false;
280 break;
281 }
282 // Compression level and/or encoding speed seem wrong.
283 default:
284 return false;
285 }
286 return true;
287 }
288
289 } // namespace draco
290