diff options
Diffstat (limited to 'extern/draco/dracoenc/src/draco/compression/mesh')
34 files changed, 5856 insertions, 0 deletions
diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_decoder.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_decoder.cc new file mode 100644 index 00000000000..01913dcd047 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_decoder.cc @@ -0,0 +1,35 @@ +// 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. +// +#include "draco/compression/mesh/mesh_decoder.h" + +namespace draco { + +MeshDecoder::MeshDecoder() : mesh_(nullptr) {} + +Status MeshDecoder::Decode(const DecoderOptions &options, + DecoderBuffer *in_buffer, Mesh *out_mesh) { + mesh_ = out_mesh; + return PointCloudDecoder::Decode(options, in_buffer, out_mesh); +} + +bool MeshDecoder::DecodeGeometryData() { + if (mesh_ == nullptr) + return false; + if (!DecodeConnectivity()) + return false; + return PointCloudDecoder::DecodeGeometryData(); +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_decoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_decoder.h new file mode 100644 index 00000000000..397a679d440 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_decoder.h @@ -0,0 +1,68 @@ +// 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_MESH_MESH_DECODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_DECODER_H_ + +#include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h" +#include "draco/compression/point_cloud/point_cloud_decoder.h" +#include "draco/mesh/mesh.h" +#include "draco/mesh/mesh_attribute_corner_table.h" + +namespace draco { + +// Class that reconstructs a 3D mesh from input data that was encoded by +// MeshEncoder. +class MeshDecoder : public PointCloudDecoder { + public: + MeshDecoder(); + + EncodedGeometryType GetGeometryType() const override { + return TRIANGULAR_MESH; + } + + // The main entry point for mesh decoding. + Status Decode(const DecoderOptions &options, DecoderBuffer *in_buffer, + Mesh *out_mesh); + + // Returns the base connectivity of the decoded mesh (or nullptr if it is not + // initialized). + virtual const CornerTable *GetCornerTable() const { return nullptr; } + + // Returns the attribute connectivity data or nullptr if it does not exist. + virtual const MeshAttributeCornerTable *GetAttributeCornerTable( + int /* att_id */) const { + return nullptr; + } + + // Returns the decoding data for a given attribute or nullptr when the data + // does not exist. + virtual const MeshAttributeIndicesEncodingData *GetAttributeEncodingData( + int /* att_id */) const { + return nullptr; + } + + Mesh *mesh() const { return mesh_; } + + protected: + bool DecodeGeometryData() override; + virtual bool DecodeConnectivity() = 0; + + private: + Mesh *mesh_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_DECODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_decoder_helpers.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_decoder_helpers.h new file mode 100644 index 00000000000..12ac46b3698 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_decoder_helpers.h @@ -0,0 +1,84 @@ +// 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_MESH_MESH_DECODER_HELPERS_H_ +#define DRACO_COMPRESSION_MESH_MESH_DECODER_HELPERS_H_ + +#include "draco/compression/mesh/mesh_decoder.h" + +namespace draco { + +// Function for decoding a stream previously encoded by a MeshEncoder. The +// result is stored into a stream of single precision floating point numbers +// in a XYZ|UV format, where one value is stored for every corner of each +// triangle. +// On error, the function sets the input stream "is" to an invalid state. +template <typename InStreamT> +InStreamT &DecodePos3Tex2DataFromStream(InStreamT &&is, + std::vector<float> *out_data) { + // Determine the size of the encoded data and write it into a vector. + const auto start_pos = is.tellg(); + is.seekg(0, std::ios::end); + const std::streampos is_size = is.tellg() - start_pos; + is.seekg(start_pos); + std::vector<char> data(is_size); + is.read(&data[0], is_size); + + // Create a mesh from the data. + std::unique_ptr<Mesh> mesh = draco::DecodeMesh(&data[0], data.size()); + + if (mesh == nullptr) { + is.setstate(ios_base::badbit); + return is; + } + + const PointAttribute *pos_att = + mesh->GetNamedAttribute(GeometryAttribute::POSITION); + const PointAttribute *tex_att = + mesh->GetNamedAttribute(GeometryAttribute::TEX_COORD_0); + + // Both position and texture attributes must be present. + if (pos_att == nullptr || tex_att == nullptr) { + is.setstate(ios_base::badbit); + return is; + } + + // Copy the mesh data into the provided output. + constexpr int data_stride = 5; + // Prepare the output storage for 3 output values per face. + out_data->resize(mesh->num_faces() * 3 * data_stride); + + std::array<float, 3> pos_val; + std::array<float, 2> tex_val; + int out_it = 0; + for (int f = 0; f < mesh->num_faces(); ++f) { + const Mesh::Face &face = mesh->face(f); + for (int p = 0; p < 3; ++p) { + pos_att->ConvertValue<float, 3>(pos_att->mapped_index(face[p]), + &pos_val[0]); + memcpy(&out_data->at(0) + out_it, &pos_val[0], sizeof(pos_val)); + out_it += 3; + tex_att->ConvertValue<float, 2>(tex_att->mapped_index(face[p]), + &tex_val[0]); + memcpy(&out_data->at(0) + out_it, &tex_val[0], sizeof(tex_val)); + out_it += 2; + } + } + + return is; +} + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_DECODER_HELPERS_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder.cc new file mode 100644 index 00000000000..e164f82b12b --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder.cc @@ -0,0 +1,67 @@ +// 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. +// +#include "draco/compression/mesh/mesh_edgebreaker_decoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_decoder_impl.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_predictive_decoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_valence_decoder.h" + +namespace draco { + +MeshEdgebreakerDecoder::MeshEdgebreakerDecoder() {} + +bool MeshEdgebreakerDecoder::CreateAttributesDecoder(int32_t att_decoder_id) { + return impl_->CreateAttributesDecoder(att_decoder_id); +} + +bool MeshEdgebreakerDecoder::InitializeDecoder() { + uint8_t traversal_decoder_type; + if (!buffer()->Decode(&traversal_decoder_type)) + return false; + impl_ = nullptr; + if (traversal_decoder_type == MESH_EDGEBREAKER_STANDARD_ENCODING) { +#ifdef DRACO_STANDARD_EDGEBREAKER_SUPPORTED + impl_ = std::unique_ptr<MeshEdgebreakerDecoderImplInterface>( + new MeshEdgebreakerDecoderImpl<MeshEdgebreakerTraversalDecoder>()); +#endif + } else if (traversal_decoder_type == MESH_EDGEBREAKER_PREDICTIVE_ENCODING) { +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED +#ifdef DRACO_PREDICTIVE_EDGEBREAKER_SUPPORTED + impl_ = std::unique_ptr<MeshEdgebreakerDecoderImplInterface>( + new MeshEdgebreakerDecoderImpl< + MeshEdgebreakerTraversalPredictiveDecoder>()); +#endif +#endif + } else if (traversal_decoder_type == MESH_EDGEBREAKER_VALENCE_ENCODING) { + impl_ = std::unique_ptr<MeshEdgebreakerDecoderImplInterface>( + new MeshEdgebreakerDecoderImpl< + MeshEdgebreakerTraversalValenceDecoder>()); + } + if (!impl_) { + return false; + } + if (!impl_->Init(this)) + return false; + return true; +} + +bool MeshEdgebreakerDecoder::DecodeConnectivity() { + return impl_->DecodeConnectivity(); +} + +bool MeshEdgebreakerDecoder::OnAttributesDecoded() { + return impl_->OnAttributesDecoded(); +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder.h new file mode 100644 index 00000000000..c3569405220 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder.h @@ -0,0 +1,55 @@ +// 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_MESH_MESH_EDGEBREAKER_DECODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_H_ + +#include "draco/draco_features.h" + +#include "draco/compression/mesh/mesh_decoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_decoder_impl_interface.h" + +namespace draco { + +// Class for decoding data encoded by MeshEdgebreakerEncoder. +class MeshEdgebreakerDecoder : public MeshDecoder { + public: + MeshEdgebreakerDecoder(); + + const CornerTable *GetCornerTable() const override { + return impl_->GetCornerTable(); + } + + const MeshAttributeCornerTable *GetAttributeCornerTable( + int att_id) const override { + return impl_->GetAttributeCornerTable(att_id); + } + + const MeshAttributeIndicesEncodingData *GetAttributeEncodingData( + int att_id) const override { + return impl_->GetAttributeEncodingData(att_id); + } + + protected: + bool InitializeDecoder() override; + bool CreateAttributesDecoder(int32_t att_decoder_id) override; + bool DecodeConnectivity() override; + bool OnAttributesDecoded() override; + + std::unique_ptr<MeshEdgebreakerDecoderImplInterface> impl_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.cc new file mode 100644 index 00000000000..9b91a6f07c4 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.cc @@ -0,0 +1,1150 @@ +// 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. +// +#include "draco/compression/mesh/mesh_edgebreaker_decoder_impl.h" + +#include <algorithm> + +#include "draco/compression/attributes/sequential_attribute_decoders_controller.h" +#include "draco/compression/mesh/mesh_edgebreaker_decoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_predictive_decoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_valence_decoder.h" +#include "draco/compression/mesh/traverser/depth_first_traverser.h" +#include "draco/compression/mesh/traverser/max_prediction_degree_traverser.h" +#include "draco/compression/mesh/traverser/mesh_attribute_indices_encoding_observer.h" +#include "draco/compression/mesh/traverser/mesh_traversal_sequencer.h" +#include "draco/compression/mesh/traverser/traverser_base.h" +#include "draco/mesh/corner_table_iterators.h" + +namespace draco { + +// Types of "free" edges that are used during topology decoding. +// A free edge is an edge that is connected to one face only. +// All edge types are stored in the opposite_corner_id_ array, where each +// edge "e" is uniquely identified by the opposite corner "C" in its parent +// triangle: +// * +// /C\ +// / \ +// / e \ +// *-------* +// For more description about how the edges are used, see comment inside +// ZipConnectivity() method. + +template <class TraversalDecoder> +MeshEdgebreakerDecoderImpl<TraversalDecoder>::MeshEdgebreakerDecoderImpl() + : decoder_(nullptr), + last_symbol_id_(-1), + last_vert_id_(-1), + last_face_id_(-1), + num_new_vertices_(0), + num_encoded_vertices_(0), + pos_data_decoder_id_(-1) {} + +template <class TraversalDecoder> +bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::Init( + MeshEdgebreakerDecoder *decoder) { + decoder_ = decoder; + return true; +} + +template <class TraversalDecoder> +const MeshAttributeCornerTable * +MeshEdgebreakerDecoderImpl<TraversalDecoder>::GetAttributeCornerTable( + int att_id) const { + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + const int decoder_id = attribute_data_[i].decoder_id; + if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) + continue; + const AttributesDecoderInterface *const dec = + decoder_->attributes_decoder(decoder_id); + for (int j = 0; j < dec->GetNumAttributes(); ++j) { + if (dec->GetAttributeId(j) == att_id) { + if (attribute_data_[i].is_connectivity_used) + return &attribute_data_[i].connectivity_data; + return nullptr; + } + } + } + return nullptr; +} + +template <class TraversalDecoder> +const MeshAttributeIndicesEncodingData * +MeshEdgebreakerDecoderImpl<TraversalDecoder>::GetAttributeEncodingData( + int att_id) const { + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + const int decoder_id = attribute_data_[i].decoder_id; + if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) + continue; + const AttributesDecoderInterface *const dec = + decoder_->attributes_decoder(decoder_id); + for (int j = 0; j < dec->GetNumAttributes(); ++j) { + if (dec->GetAttributeId(j) == att_id) + return &attribute_data_[i].encoding_data; + } + } + return &pos_encoding_data_; +} + +template <class TraversalDecoder> +template <class TraverserT> +std::unique_ptr<PointsSequencer> +MeshEdgebreakerDecoderImpl<TraversalDecoder>::CreateVertexTraversalSequencer( + MeshAttributeIndicesEncodingData *encoding_data) { + typedef typename TraverserT::TraversalObserver AttObserver; + typedef typename TraverserT::CornerTable CornerTable; + + const Mesh *mesh = decoder_->mesh(); + std::unique_ptr<MeshTraversalSequencer<TraverserT>> traversal_sequencer( + new MeshTraversalSequencer<TraverserT>(mesh, encoding_data)); + + AttObserver att_observer(corner_table_.get(), mesh, traversal_sequencer.get(), + encoding_data); + + TraverserT att_traverser; + att_traverser.Init(corner_table_.get(), att_observer); + + traversal_sequencer->SetTraverser(att_traverser); + return std::move(traversal_sequencer); +} + +template <class TraversalDecoder> +bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::CreateAttributesDecoder( + int32_t att_decoder_id) { + int8_t att_data_id; + if (!decoder_->buffer()->Decode(&att_data_id)) + return false; + uint8_t decoder_type; + if (!decoder_->buffer()->Decode(&decoder_type)) + return false; + + if (att_data_id >= 0) { + if (att_data_id >= attribute_data_.size()) { + return false; // Unexpected attribute data. + } + + // Ensure that the attribute data is not mapped to a different attributes + // decoder already. + if (attribute_data_[att_data_id].decoder_id >= 0) + return false; + + attribute_data_[att_data_id].decoder_id = att_decoder_id; + } else { + // Assign the attributes decoder to |pos_encoding_data_|. + if (pos_data_decoder_id_ >= 0) + return false; // Some other decoder is already using the data. Error. + pos_data_decoder_id_ = att_decoder_id; + } + + MeshTraversalMethod traversal_method = MESH_TRAVERSAL_DEPTH_FIRST; + if (decoder_->bitstream_version() >= DRACO_BITSTREAM_VERSION(1, 2)) { + uint8_t traversal_method_encoded; + if (!decoder_->buffer()->Decode(&traversal_method_encoded)) + return false; + traversal_method = + static_cast<MeshTraversalMethod>(traversal_method_encoded); + } + + const Mesh *mesh = decoder_->mesh(); + std::unique_ptr<PointsSequencer> sequencer; + + if (decoder_type == MESH_VERTEX_ATTRIBUTE) { + // Per-vertex attribute decoder. + + MeshAttributeIndicesEncodingData *encoding_data = nullptr; + if (att_data_id < 0) { + encoding_data = &pos_encoding_data_; + } else { + encoding_data = &attribute_data_[att_data_id].encoding_data; + // Mark the attribute connectivity data invalid to ensure it's not used + // later on. + attribute_data_[att_data_id].is_connectivity_used = false; + } + // Defining sequencer via a traversal scheme. + if (traversal_method == MESH_TRAVERSAL_PREDICTION_DEGREE) { + typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver; + typedef MaxPredictionDegreeTraverser<CornerTable, AttObserver> + AttTraverser; + sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data); + } else if (traversal_method == MESH_TRAVERSAL_DEPTH_FIRST) { + typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver; + typedef DepthFirstTraverser<CornerTable, AttObserver> AttTraverser; + sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data); + } else { + return false; // Unsupported method + } + } else { + if (traversal_method != MESH_TRAVERSAL_DEPTH_FIRST) + return false; // Unsupported method. + if (att_data_id < 0) + return false; // Attribute data must be specified. + + // Per-corner attribute decoder. + + typedef MeshAttributeIndicesEncodingObserver<MeshAttributeCornerTable> + AttObserver; + typedef DepthFirstTraverser<MeshAttributeCornerTable, AttObserver> + AttTraverser; + + MeshAttributeIndicesEncodingData *const encoding_data = + &attribute_data_[att_data_id].encoding_data; + const MeshAttributeCornerTable *const corner_table = + &attribute_data_[att_data_id].connectivity_data; + + std::unique_ptr<MeshTraversalSequencer<AttTraverser>> traversal_sequencer( + new MeshTraversalSequencer<AttTraverser>(mesh, encoding_data)); + + AttObserver att_observer(corner_table, mesh, traversal_sequencer.get(), + encoding_data); + + AttTraverser att_traverser; + att_traverser.Init(corner_table, att_observer); + + traversal_sequencer->SetTraverser(att_traverser); + sequencer = std::move(traversal_sequencer); + } + + if (!sequencer) + return false; + + std::unique_ptr<SequentialAttributeDecodersController> att_controller( + new SequentialAttributeDecodersController(std::move(sequencer))); + + return decoder_->SetAttributesDecoder(att_decoder_id, + std::move(att_controller)); +} + +template <class TraversalDecoder> +bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::DecodeConnectivity() { + num_new_vertices_ = 0; + new_to_parent_vertex_map_.clear(); +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) { + uint32_t num_new_verts; + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) { + if (!decoder_->buffer()->Decode(&num_new_verts)) + return false; + } else { + if (!DecodeVarint(&num_new_verts, decoder_->buffer())) + return false; + } + num_new_vertices_ = num_new_verts; + } +#endif + + uint32_t num_encoded_vertices; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) { + if (!decoder_->buffer()->Decode(&num_encoded_vertices)) + return false; + + } else +#endif + { + if (!DecodeVarint(&num_encoded_vertices, decoder_->buffer())) + return false; + } + num_encoded_vertices_ = num_encoded_vertices; + + uint32_t num_faces; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) { + if (!decoder_->buffer()->Decode(&num_faces)) + return false; + + } else +#endif + { + if (!DecodeVarint(&num_faces, decoder_->buffer())) + return false; + } + if (num_faces > std::numeric_limits<CornerIndex::ValueType>::max() / 3) + return false; // Draco cannot handle this many faces. + + if (static_cast<uint32_t>(num_encoded_vertices_) > num_faces * 3) { + return false; // There cannot be more vertices than 3 * num_faces. + } + uint8_t num_attribute_data; + if (!decoder_->buffer()->Decode(&num_attribute_data)) + return false; + + uint32_t num_encoded_symbols; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) { + if (!decoder_->buffer()->Decode(&num_encoded_symbols)) + return false; + + } else +#endif + { + if (!DecodeVarint(&num_encoded_symbols, decoder_->buffer())) + return false; + } + + if (num_faces < num_encoded_symbols) { + // Number of faces needs to be the same or greater than the number of + // symbols (it can be greater because the initial face may not be encoded as + // a symbol). + return false; + } + const uint32_t max_encoded_faces = + num_encoded_symbols + (num_encoded_symbols / 3); + if (num_faces > max_encoded_faces) { + // Faces can only be 1 1/3 times bigger than number of encoded symbols. This + // could only happen if all new encoded components started with interior + // triangles. E.g. A mesh with multiple tetrahedrons. + return false; + } + + uint32_t num_encoded_split_symbols; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) { + if (!decoder_->buffer()->Decode(&num_encoded_split_symbols)) + return false; + + } else +#endif + { + if (!DecodeVarint(&num_encoded_split_symbols, decoder_->buffer())) + return false; + } + + if (num_encoded_split_symbols > num_encoded_symbols) { + return false; // Split symbols are a sub-set of all symbols. + } + + // Decode topology (connectivity). + vertex_traversal_length_.clear(); + corner_table_ = std::unique_ptr<CornerTable>(new CornerTable()); + if (corner_table_ == nullptr) + return false; + processed_corner_ids_.clear(); + processed_corner_ids_.reserve(num_faces); + processed_connectivity_corners_.clear(); + processed_connectivity_corners_.reserve(num_faces); + topology_split_data_.clear(); + hole_event_data_.clear(); + init_face_configurations_.clear(); + init_corners_.clear(); + + last_symbol_id_ = -1; + last_face_id_ = -1; + last_vert_id_ = -1; + + attribute_data_.clear(); + // Add one attribute data for each attribute decoder. + attribute_data_.resize(num_attribute_data); + + if (!corner_table_->Reset(num_faces, + num_encoded_vertices_ + num_encoded_split_symbols)) + return false; + + // Start with all vertices marked as holes (boundaries). + // Only vertices decoded with TOPOLOGY_C symbol (and the initial face) will + // be marked as non hole vertices. We need to allocate the array larger + // because split symbols can create extra vertices during the decoding + // process (these extra vertices are then eliminated during deduplication). + is_vert_hole_.assign(num_encoded_vertices_ + num_encoded_split_symbols, true); + +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + int32_t topology_split_decoded_bytes = -1; + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) { + uint32_t encoded_connectivity_size; + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) { + if (!decoder_->buffer()->Decode(&encoded_connectivity_size)) + return false; + } else { + if (!DecodeVarint(&encoded_connectivity_size, decoder_->buffer())) + return false; + } + if (encoded_connectivity_size == 0 || + encoded_connectivity_size > decoder_->buffer()->remaining_size()) + return false; + DecoderBuffer event_buffer; + event_buffer.Init( + decoder_->buffer()->data_head() + encoded_connectivity_size, + decoder_->buffer()->remaining_size() - encoded_connectivity_size, + decoder_->buffer()->bitstream_version()); + // Decode hole and topology split events. + topology_split_decoded_bytes = + DecodeHoleAndTopologySplitEvents(&event_buffer); + if (topology_split_decoded_bytes == -1) + return false; + + } else +#endif + { + if (DecodeHoleAndTopologySplitEvents(decoder_->buffer()) == -1) + return false; + } + + traversal_decoder_.Init(this); + // Add one extra vertex for each split symbol. + traversal_decoder_.SetNumEncodedVertices(num_encoded_vertices_ + + num_encoded_split_symbols); + traversal_decoder_.SetNumAttributeData(num_attribute_data); + + DecoderBuffer traversal_end_buffer; + if (!traversal_decoder_.Start(&traversal_end_buffer)) + return false; + + const int num_connectivity_verts = DecodeConnectivity(num_encoded_symbols); + if (num_connectivity_verts == -1) + return false; + + // Set the main buffer to the end of the traversal. + decoder_->buffer()->Init(traversal_end_buffer.data_head(), + traversal_end_buffer.remaining_size(), + decoder_->buffer()->bitstream_version()); + +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) { + // Skip topology split data that was already decoded earlier. + decoder_->buffer()->Advance(topology_split_decoded_bytes); + } +#endif + + // Decode connectivity of non-position attributes. + if (attribute_data_.size() > 0) { +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) { + for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) { + if (!DecodeAttributeConnectivitiesOnFaceLegacy(ci)) + return false; + } + + } else +#endif + { + for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) { + if (!DecodeAttributeConnectivitiesOnFace(ci)) + return false; + } + } + } + traversal_decoder_.Done(); + + // Decode attribute connectivity. + // Prepare data structure for decoding non-position attribute connectivity. + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + attribute_data_[i].connectivity_data.InitEmpty(corner_table_.get()); + // Add all seams. + for (int32_t c : attribute_data_[i].attribute_seam_corners) { + attribute_data_[i].connectivity_data.AddSeamEdge(CornerIndex(c)); + } + // Recompute vertices from the newly added seam edges. + attribute_data_[i].connectivity_data.RecomputeVertices(nullptr, nullptr); + } + + pos_encoding_data_.Init(corner_table_->num_vertices()); + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + // For non-position attributes, preallocate the vertex to value mapping + // using the maximum number of vertices from the base corner table and the + // attribute corner table (since the attribute decoder may use either of + // it). + int32_t att_connectivity_verts = + attribute_data_[i].connectivity_data.num_vertices(); + if (att_connectivity_verts < corner_table_->num_vertices()) + att_connectivity_verts = corner_table_->num_vertices(); + attribute_data_[i].encoding_data.Init(att_connectivity_verts); + } + if (!AssignPointsToCorners(num_connectivity_verts)) + return false; + return true; +} + +template <class TraversalDecoder> +bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::OnAttributesDecoded() { + return true; +} + +template <class TraversalDecoder> +int MeshEdgebreakerDecoderImpl<TraversalDecoder>::DecodeConnectivity( + int num_symbols) { + // Algorithm does the reverse decoding of the symbols encoded with the + // edgebreaker method. The reverse decoding always keeps track of the active + // edge identified by its opposite corner (active corner). New faces are + // always added to this active edge. There may be multiple active corners at + // one time that either correspond to separate mesh components or to + // sub-components of one mesh that are going to be merged together using the + // TOPOLOGY_S symbol. We can store these active edges on a stack, because the + // decoder always processes only the latest active edge. TOPOLOGY_S then + // removes the top edge from the stack and TOPOLOGY_E adds a new edge to the + // stack. + std::vector<CornerIndex> active_corner_stack; + + // Additional active edges may be added as a result of topology split events. + // They can be added in arbitrary order, but we always know the split symbol + // id they belong to, so we can address them using this symbol id. + std::unordered_map<int, CornerIndex> topology_split_active_corners; + + // Vector used for storing vertices that were marked as isolated during the + // decoding process. Currently used only when the mesh doesn't contain any + // non-position connectivity data. + std::vector<VertexIndex> invalid_vertices; + const bool remove_invalid_vertices = attribute_data_.empty(); + + int max_num_vertices = static_cast<int>(is_vert_hole_.size()); + int num_faces = 0; + for (int symbol_id = 0; symbol_id < num_symbols; ++symbol_id) { + const FaceIndex face(num_faces++); + // Used to flag cases where we need to look for topology split events. + bool check_topology_split = false; + const uint32_t symbol = traversal_decoder_.DecodeSymbol(); + if (symbol == TOPOLOGY_C) { + // Create a new face between two edges on the open boundary. + // The first edge is opposite to the corner "a" from the image below. + // The other edge is opposite to the corner "b" that can be reached + // through a CCW traversal around the vertex "v". + // One new active boundary edge is created, opposite to the new corner + // "x". + // + // *-------* + // / \ / \ + // / \ / \ + // / \ / \ + // *-------v-------* + // \b /x\ a/ + // \ / \ / + // \ / C \ / + // *.......* + + // Find the corner "b" from the corner "a" which is the corner on the + // top of the active stack. + if (active_corner_stack.empty()) + return -1; + + const CornerIndex corner_a = active_corner_stack.back(); + const VertexIndex vertex_x = + corner_table_->Vertex(corner_table_->Next(corner_a)); + const CornerIndex corner_b = + corner_table_->Next(corner_table_->LeftMostCorner(vertex_x)); + + // New tip corner. + const CornerIndex corner(3 * face.value()); + // Update opposite corner mappings. + SetOppositeCorners(corner_a, corner + 1); + SetOppositeCorners(corner_b, corner + 2); + + // Update vertex mapping. + corner_table_->MapCornerToVertex(corner, vertex_x); + corner_table_->MapCornerToVertex( + corner + 1, corner_table_->Vertex(corner_table_->Next(corner_b))); + const VertexIndex vert_a_prev = + corner_table_->Vertex(corner_table_->Previous(corner_a)); + corner_table_->MapCornerToVertex(corner + 2, vert_a_prev); + corner_table_->SetLeftMostCorner(vert_a_prev, corner + 2); + // Mark the vertex |x| as interior. + is_vert_hole_[vertex_x.value()] = false; + // Update the corner on the active stack. + active_corner_stack.back() = corner; + } else if (symbol == TOPOLOGY_R || symbol == TOPOLOGY_L) { + // Create a new face extending from the open boundary edge opposite to the + // corner "a" from the image below. Two new boundary edges are created + // opposite to corners "r" and "l". New active corner is set to either "r" + // or "l" depending on the decoded symbol. One new vertex is created + // at the opposite corner to corner "a". + // *-------* + // /a\ / \ + // / \ / \ + // / \ / \ + // *-------v-------* + // .l r. + // . . + // . . + // * + if (active_corner_stack.empty()) + return -1; + const CornerIndex corner_a = active_corner_stack.back(); + + // First corner on the new face is either corner "l" or "r". + const CornerIndex corner(3 * face.value()); + CornerIndex opp_corner, corner_l, corner_r; + if (symbol == TOPOLOGY_R) { + // "r" is the new first corner. + opp_corner = corner + 2; + corner_l = corner + 1; + corner_r = corner; + } else { + // "l" is the new first corner. + opp_corner = corner + 1; + corner_l = corner; + corner_r = corner + 2; + } + SetOppositeCorners(opp_corner, corner_a); + // Update vertex mapping. + const VertexIndex new_vert_index = corner_table_->AddNewVertex(); + + if (corner_table_->num_vertices() > max_num_vertices) + return -1; // Unexpected number of decoded vertices. + + corner_table_->MapCornerToVertex(opp_corner, new_vert_index); + corner_table_->SetLeftMostCorner(new_vert_index, opp_corner); + + const VertexIndex vertex_r = + corner_table_->Vertex(corner_table_->Previous(corner_a)); + corner_table_->MapCornerToVertex(corner_r, vertex_r); + // Update left-most corner on the vertex on the |corner_r|. + corner_table_->SetLeftMostCorner(vertex_r, corner_r); + + corner_table_->MapCornerToVertex( + corner_l, corner_table_->Vertex(corner_table_->Next(corner_a))); + active_corner_stack.back() = corner; + check_topology_split = true; + } else if (symbol == TOPOLOGY_S) { + // Create a new face that merges two last active edges from the active + // stack. No new vertex is created, but two vertices at corners "p" and + // "n" need to be merged into a single vertex. + // + // *-------v-------* + // \a p/x\n b/ + // \ / \ / + // \ / S \ / + // *.......* + // + if (active_corner_stack.empty()) + return -1; + const CornerIndex corner_b = active_corner_stack.back(); + active_corner_stack.pop_back(); + + // Corner "a" can correspond either to a normal active edge, or to an edge + // created from the topology split event. + const auto it = topology_split_active_corners.find(symbol_id); + if (it != topology_split_active_corners.end()) { + // Topology split event. Move the retrieved edge to the stack. + active_corner_stack.push_back(it->second); + } + if (active_corner_stack.empty()) + return -1; + const CornerIndex corner_a = active_corner_stack.back(); + + if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex || + corner_table_->Opposite(corner_b) != kInvalidCornerIndex) { + // One of the corners is already opposite to an existing face, which + // should not happen unless the input was tempered with. + return -1; + } + + // First corner on the new face is corner "x" from the image above. + const CornerIndex corner(3 * face.value()); + // Update the opposite corner mapping. + SetOppositeCorners(corner_a, corner + 2); + SetOppositeCorners(corner_b, corner + 1); + // Update vertices. For the vertex at corner "x", use the vertex id from + // the corner "p". + const VertexIndex vertex_p = + corner_table_->Vertex(corner_table_->Previous(corner_a)); + corner_table_->MapCornerToVertex(corner, vertex_p); + corner_table_->MapCornerToVertex( + corner + 1, corner_table_->Vertex(corner_table_->Next(corner_a))); + const VertexIndex vert_b_prev = + corner_table_->Vertex(corner_table_->Previous(corner_b)); + corner_table_->MapCornerToVertex(corner + 2, vert_b_prev); + corner_table_->SetLeftMostCorner(vert_b_prev, corner + 2); + CornerIndex corner_n = corner_table_->Next(corner_b); + const VertexIndex vertex_n = corner_table_->Vertex(corner_n); + traversal_decoder_.MergeVertices(vertex_p, vertex_n); + // Update the left most corner on the newly merged vertex. + corner_table_->SetLeftMostCorner(vertex_p, + corner_table_->LeftMostCorner(vertex_n)); + + // Also update the vertex id at corner "n" and all corners that are + // connected to it in the CCW direction. + while (corner_n != kInvalidCornerIndex) { + corner_table_->MapCornerToVertex(corner_n, vertex_p); + corner_n = corner_table_->SwingLeft(corner_n); + } + // Make sure the old vertex n is now mapped to an invalid corner (make it + // isolated). + corner_table_->MakeVertexIsolated(vertex_n); + if (remove_invalid_vertices) + invalid_vertices.push_back(vertex_n); + active_corner_stack.back() = corner; + } else if (symbol == TOPOLOGY_E) { + const CornerIndex corner(3 * face.value()); + const VertexIndex first_vert_index = corner_table_->AddNewVertex(); + // Create three new vertices at the corners of the new face. + corner_table_->MapCornerToVertex(corner, first_vert_index); + corner_table_->MapCornerToVertex(corner + 1, + corner_table_->AddNewVertex()); + corner_table_->MapCornerToVertex(corner + 2, + corner_table_->AddNewVertex()); + + if (corner_table_->num_vertices() > max_num_vertices) + return -1; // Unexpected number of decoded vertices. + + corner_table_->SetLeftMostCorner(first_vert_index, corner); + corner_table_->SetLeftMostCorner(first_vert_index + 1, corner + 1); + corner_table_->SetLeftMostCorner(first_vert_index + 2, corner + 2); + // Add the tip corner to the active stack. + active_corner_stack.push_back(corner); + check_topology_split = true; + } else { + // Error. Unknown symbol decoded. + return -1; + } + // Inform the traversal decoder that a new corner has been reached. + traversal_decoder_.NewActiveCornerReached(active_corner_stack.back()); + + if (check_topology_split) { + // Check for topology splits happens only for TOPOLOGY_L, TOPOLOGY_R and + // TOPOLOGY_E symbols because those are the symbols that correspond to + // faces that can be directly connected a TOPOLOGY_S face through the + // topology split event. + // If a topology split is detected, we need to add a new active edge + // onto the active_corner_stack because it will be used later when the + // corresponding TOPOLOGY_S event is decoded. + + // Symbol id used by the encoder (reverse). + const int encoder_symbol_id = num_symbols - symbol_id - 1; + EdgeFaceName split_edge; + int encoder_split_symbol_id; + while (IsTopologySplit(encoder_symbol_id, &split_edge, + &encoder_split_symbol_id)) { + if (encoder_split_symbol_id < 0) + return -1; // Wrong split symbol id. + // Symbol was part of a topology split. Now we need to determine which + // edge should be added to the active edges stack. + const CornerIndex act_top_corner = active_corner_stack.back(); + // The current symbol has one active edge (stored in act_top_corner) and + // two remaining inactive edges that are attached to it. + // * + // / \ + // left_edge / \ right_edge + // / \ + // *.......* + // active_edge + + CornerIndex new_active_corner; + if (split_edge == RIGHT_FACE_EDGE) { + new_active_corner = corner_table_->Next(act_top_corner); + } else { + new_active_corner = corner_table_->Previous(act_top_corner); + } + // Add the new active edge. + // Convert the encoder split symbol id to decoder symbol id. + const int decoder_split_symbol_id = + num_symbols - encoder_split_symbol_id - 1; + topology_split_active_corners[decoder_split_symbol_id] = + new_active_corner; + } + } + } + if (corner_table_->num_vertices() > max_num_vertices) + return -1; // Unexpected number of decoded vertices. + // Decode start faces and connect them to the faces from the active stack. + while (active_corner_stack.size() > 0) { + const CornerIndex corner = active_corner_stack.back(); + active_corner_stack.pop_back(); + const bool interior_face = + traversal_decoder_.DecodeStartFaceConfiguration(); + if (interior_face) { + // The start face is interior, we need to find three corners that are + // opposite to it. The first opposite corner "a" is the corner from the + // top of the active corner stack and the remaining two corners "b" and + // "c" are then the next corners from the left-most corners of vertices + // "n" and "x" respectively. + // + // *-------* + // / \ / \ + // / \ / \ + // / \ / \ + // *-------p-------* + // / \a . . c/ \ + // / \ . . / \ + // / \ . I . / \ + // *-------n.......x------* + // \ / \ / \ / + // \ / \ / \ / + // \ / \b/ \ / + // *-------*-------* + // + + if (num_faces >= corner_table_->num_faces()) { + return -1; // More faces than expected added to the mesh. + } + + const CornerIndex corner_a = corner; + const VertexIndex vert_n = + corner_table_->Vertex(corner_table_->Next(corner_a)); + const CornerIndex corner_b = + corner_table_->Next(corner_table_->LeftMostCorner(vert_n)); + + const VertexIndex vert_x = + corner_table_->Vertex(corner_table_->Next(corner_b)); + const CornerIndex corner_c = + corner_table_->Next(corner_table_->LeftMostCorner(vert_x)); + + const VertexIndex vert_p = + corner_table_->Vertex(corner_table_->Next(corner_c)); + + const FaceIndex face(num_faces++); + // The first corner of the initial face is the corner opposite to "a". + const CornerIndex new_corner(3 * face.value()); + SetOppositeCorners(new_corner, corner); + SetOppositeCorners(new_corner + 1, corner_b); + SetOppositeCorners(new_corner + 2, corner_c); + + // Map new corners to existing vertices. + corner_table_->MapCornerToVertex(new_corner, vert_x); + corner_table_->MapCornerToVertex(new_corner + 1, vert_p); + corner_table_->MapCornerToVertex(new_corner + 2, vert_n); + + // Mark all three vertices as interior. + for (int ci = 0; ci < 3; ++ci) { + is_vert_hole_[corner_table_->Vertex(new_corner + ci).value()] = false; + } + + init_face_configurations_.push_back(true); + init_corners_.push_back(new_corner); + } else { + // The initial face wasn't interior and the traversal had to start from + // an open boundary. In this case no new face is added, but we need to + // keep record about the first opposite corner to this boundary. + init_face_configurations_.push_back(false); + init_corners_.push_back(corner); + } + } + if (num_faces != corner_table_->num_faces()) + return -1; // Unexpected number of decoded faces. + + int num_vertices = corner_table_->num_vertices(); + // If any vertex was marked as isolated, we want to remove it from the corner + // table to ensure that all vertices in range <0, num_vertices> are valid. + for (const VertexIndex invalid_vert : invalid_vertices) { + // Find the last valid vertex and swap it with the isolated vertex. + VertexIndex src_vert(num_vertices - 1); + while (corner_table_->LeftMostCorner(src_vert) == kInvalidCornerIndex) { + // The last vertex is invalid, proceed to the previous one. + src_vert = VertexIndex(--num_vertices - 1); + } + if (src_vert < invalid_vert) + continue; // No need to swap anything. + + // Remap all corners mapped to |src_vert| to |invalid_vert|. + VertexCornersIterator<CornerTable> vcit(corner_table_.get(), src_vert); + for (; !vcit.End(); ++vcit) { + const CornerIndex cid = vcit.Corner(); + corner_table_->MapCornerToVertex(cid, invalid_vert); + } + corner_table_->SetLeftMostCorner(invalid_vert, + corner_table_->LeftMostCorner(src_vert)); + + // Make the |src_vert| invalid. + corner_table_->MakeVertexIsolated(src_vert); + is_vert_hole_[invalid_vert.value()] = is_vert_hole_[src_vert.value()]; + is_vert_hole_[src_vert.value()] = false; + + // The last vertex is now invalid. + num_vertices--; + } + return num_vertices; +} + +template <class TraversalDecoder> +int32_t +MeshEdgebreakerDecoderImpl<TraversalDecoder>::DecodeHoleAndTopologySplitEvents( + DecoderBuffer *decoder_buffer) { + // Prepare a new decoder from the provided buffer offset. + uint32_t num_topology_splits; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) { + if (!decoder_buffer->Decode(&num_topology_splits)) + return -1; + + } else +#endif + { + if (!DecodeVarint(&num_topology_splits, decoder_buffer)) + return -1; + } + if (num_topology_splits > 0) { + if (num_topology_splits > static_cast<uint32_t>(corner_table_->num_faces())) + return -1; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) { + for (uint32_t i = 0; i < num_topology_splits; ++i) { + TopologySplitEventData event_data; + if (!decoder_buffer->Decode(&event_data.split_symbol_id)) + return -1; + if (!decoder_buffer->Decode(&event_data.source_symbol_id)) + return -1; + uint8_t edge_data; + if (!decoder_buffer->Decode(&edge_data)) + return -1; + event_data.source_edge = edge_data & 1; + topology_split_data_.push_back(event_data); + } + + } else +#endif + { + // Decode source and split symbol ids using delta and varint coding. See + // description in mesh_edgebreaker_encoder_impl.cc for more details. + int last_source_symbol_id = 0; + for (uint32_t i = 0; i < num_topology_splits; ++i) { + TopologySplitEventData event_data; + uint32_t delta; + DecodeVarint<uint32_t>(&delta, decoder_buffer); + event_data.source_symbol_id = delta + last_source_symbol_id; + DecodeVarint<uint32_t>(&delta, decoder_buffer); + if (delta > event_data.source_symbol_id) + return -1; + event_data.split_symbol_id = + event_data.source_symbol_id - static_cast<int32_t>(delta); + last_source_symbol_id = event_data.source_symbol_id; + topology_split_data_.push_back(event_data); + } + // Split edges are decoded from a direct bit decoder. + decoder_buffer->StartBitDecoding(false, nullptr); + for (uint32_t i = 0; i < num_topology_splits; ++i) { + uint32_t edge_data; + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) { + decoder_buffer->DecodeLeastSignificantBits32(2, &edge_data); + } else { + decoder_buffer->DecodeLeastSignificantBits32(1, &edge_data); + } + TopologySplitEventData &event_data = topology_split_data_[i]; + event_data.source_edge = edge_data & 1; + } + decoder_buffer->EndBitDecoding(); + } + } + uint32_t num_hole_events = 0; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) { + if (!decoder_buffer->Decode(&num_hole_events)) + return -1; + } else if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) { + if (!DecodeVarint(&num_hole_events, decoder_buffer)) + return -1; + } +#endif + if (num_hole_events > 0) { +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) { + for (uint32_t i = 0; i < num_hole_events; ++i) { + HoleEventData event_data; + if (!decoder_buffer->Decode(&event_data)) + return -1; + hole_event_data_.push_back(event_data); + } + + } else +#endif + { + // Decode hole symbol ids using delta and varint coding. + int last_symbol_id = 0; + for (uint32_t i = 0; i < num_hole_events; ++i) { + HoleEventData event_data; + uint32_t delta; + DecodeVarint<uint32_t>(&delta, decoder_buffer); + event_data.symbol_id = delta + last_symbol_id; + last_symbol_id = event_data.symbol_id; + hole_event_data_.push_back(event_data); + } + } + } + return static_cast<int32_t>(decoder_buffer->decoded_size()); +} + +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED +template <class TraversalDecoder> +bool MeshEdgebreakerDecoderImpl<TraversalDecoder>:: + DecodeAttributeConnectivitiesOnFaceLegacy(CornerIndex corner) { + // Three corners of the face. + const CornerIndex corners[3] = {corner, corner_table_->Next(corner), + corner_table_->Previous(corner)}; + + for (int c = 0; c < 3; ++c) { + const CornerIndex opp_corner = corner_table_->Opposite(corners[c]); + if (opp_corner == kInvalidCornerIndex) { + // Don't decode attribute seams on boundary edges (every boundary edge + // is automatically an attribute seam). + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + attribute_data_[i].attribute_seam_corners.push_back(corners[c].value()); + } + continue; + } + + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + const bool is_seam = traversal_decoder_.DecodeAttributeSeam(i); + if (is_seam) + attribute_data_[i].attribute_seam_corners.push_back(corners[c].value()); + } + } + return true; +} +#endif + +template <class TraversalDecoder> +bool MeshEdgebreakerDecoderImpl< + TraversalDecoder>::DecodeAttributeConnectivitiesOnFace(CornerIndex corner) { + // Three corners of the face. + const CornerIndex corners[3] = {corner, corner_table_->Next(corner), + corner_table_->Previous(corner)}; + + const FaceIndex src_face_id = corner_table_->Face(corner); + for (int c = 0; c < 3; ++c) { + const CornerIndex opp_corner = corner_table_->Opposite(corners[c]); + if (opp_corner == kInvalidCornerIndex) { + // Don't decode attribute seams on boundary edges (every boundary edge + // is automatically an attribute seam). + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + attribute_data_[i].attribute_seam_corners.push_back(corners[c].value()); + } + continue; + } + const FaceIndex opp_face_id = corner_table_->Face(opp_corner); + // Don't decode edges when the opposite face has been already processed. + if (opp_face_id < src_face_id) + continue; + + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + const bool is_seam = traversal_decoder_.DecodeAttributeSeam(i); + if (is_seam) + attribute_data_[i].attribute_seam_corners.push_back(corners[c].value()); + } + } + return true; +} + +template <class TraversalDecoder> +bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::AssignPointsToCorners( + int num_connectivity_verts) { + // Map between the existing and deduplicated point ids. + // Note that at this point we have one point id for each corner of the + // mesh so there is corner_table_->num_corners() point ids. + decoder_->mesh()->SetNumFaces(corner_table_->num_faces()); + + if (attribute_data_.empty()) { + // We have connectivity for position only. In this case all vertex indices + // are equal to point indices. + for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) { + Mesh::Face face; + const CornerIndex start_corner(3 * f.value()); + for (int c = 0; c < 3; ++c) { + // Get the vertex index on the corner and use it as a point index. + const int32_t vert_id = corner_table_->Vertex(start_corner + c).value(); + face[c] = vert_id; + } + decoder_->mesh()->SetFace(f, face); + } + decoder_->point_cloud()->set_num_points(num_connectivity_verts); + return true; + } + // Else we need to deduplicate multiple attributes. + + // Map between point id and an associated corner id. Only one corner for + // each point is stored. The corners are used to sample the attribute values + // in the last stage of the deduplication. + std::vector<int32_t> point_to_corner_map; + // Map between every corner and their new point ids. + std::vector<int32_t> corner_to_point_map(corner_table_->num_corners()); + for (int v = 0; v < corner_table_->num_vertices(); ++v) { + CornerIndex c = corner_table_->LeftMostCorner(VertexIndex(v)); + if (c == kInvalidCornerIndex) + continue; // Isolated vertex. + CornerIndex deduplication_first_corner = c; + if (is_vert_hole_[v]) { + // If the vertex is on a boundary, start deduplication from the left most + // corner that is guaranteed to lie on the boundary. + deduplication_first_corner = c; + } else { + // If we are not on the boundary we need to find the first seam (of any + // attribute). + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + if (!attribute_data_[i].connectivity_data.IsCornerOnSeam(c)) + continue; // No seam for this attribute, ignore it. + // Else there needs to be at least one seam edge. + + // At this point, we use identity mapping between corners and point ids. + const VertexIndex vert_id = + attribute_data_[i].connectivity_data.Vertex(c); + CornerIndex act_c = corner_table_->SwingRight(c); + bool seam_found = false; + while (act_c != c) { + if (act_c == kInvalidCornerIndex) + return false; + if (attribute_data_[i].connectivity_data.Vertex(act_c) != vert_id) { + // Attribute seam found. Stop. + deduplication_first_corner = act_c; + seam_found = true; + break; + } + act_c = corner_table_->SwingRight(act_c); + } + if (seam_found) + break; // No reason to process other attributes if we found a seam. + } + } + + // Do a deduplication pass over the corners on the processed vertex. + // At this point each corner corresponds to one point id and our goal is to + // merge similar points into a single point id. + // We do a single pass in a clockwise direction over the corners and we add + // a new point id whenever one of the attributes change. + c = deduplication_first_corner; + // Create a new point. + corner_to_point_map[c.value()] = + static_cast<uint32_t>(point_to_corner_map.size()); + point_to_corner_map.push_back(c.value()); + // Traverse in CW direction. + CornerIndex prev_c = c; + c = corner_table_->SwingRight(c); + while (c != kInvalidCornerIndex && c != deduplication_first_corner) { + bool attribute_seam = false; + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + if (attribute_data_[i].connectivity_data.Vertex(c) != + attribute_data_[i].connectivity_data.Vertex(prev_c)) { + // Attribute index changed from the previous corner. We need to add a + // new point here. + attribute_seam = true; + break; + } + } + if (attribute_seam) { + corner_to_point_map[c.value()] = + static_cast<uint32_t>(point_to_corner_map.size()); + point_to_corner_map.push_back(c.value()); + } else { + corner_to_point_map[c.value()] = corner_to_point_map[prev_c.value()]; + } + prev_c = c; + c = corner_table_->SwingRight(c); + } + } + // Add faces. + for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) { + Mesh::Face face; + for (int c = 0; c < 3; ++c) { + // Remap old points to the new ones. + face[c] = corner_to_point_map[3 * f.value() + c]; + } + decoder_->mesh()->SetFace(f, face); + } + decoder_->point_cloud()->set_num_points( + static_cast<uint32_t>(point_to_corner_map.size())); + return true; +} + +template class MeshEdgebreakerDecoderImpl<MeshEdgebreakerTraversalDecoder>; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED +template class MeshEdgebreakerDecoderImpl< + MeshEdgebreakerTraversalPredictiveDecoder>; +#endif +template class MeshEdgebreakerDecoderImpl< + MeshEdgebreakerTraversalValenceDecoder>; +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.h new file mode 100644 index 00000000000..5299a189d48 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.h @@ -0,0 +1,226 @@ +// 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_MESH_MESH_EDGEBREAKER_DECODER_IMPL_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_H_ + +#include <unordered_map> +#include <unordered_set> +#include "draco/compression/mesh/traverser/mesh_traversal_sequencer.h" + +#include "draco/draco_features.h" + +#include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h" +#include "draco/compression/mesh/mesh_edgebreaker_decoder_impl_interface.h" +#include "draco/compression/mesh/mesh_edgebreaker_shared.h" +#include "draco/core/decoder_buffer.h" +#include "draco/mesh/corner_table.h" +#include "draco/mesh/mesh_attribute_corner_table.h" + +namespace draco { + +// Implementation of the edgebreaker decoder that decodes data encoded with the +// MeshEdgebreakerEncoderImpl class. The implementation of the decoder is based +// on the algorithm presented in Isenburg et al'02 "Spirale Reversi: Reverse +// decoding of the Edgebreaker encoding". Note that the encoding is still based +// on the standard edgebreaker method as presented in "3D Compression +// Made Simple: Edgebreaker on a Corner-Table" by Rossignac at al.'01. +// http://www.cc.gatech.edu/~jarek/papers/CornerTableSMI.pdf. One difference is +// caused by the properties of the spirale reversi algorithm that decodes the +// symbols from the last one to the first one. To make the decoding more +// efficient, we encode all symbols in the reverse order, therefore the decoder +// can process them one by one. +// The main advantage of the spirale reversi method is that the partially +// decoded mesh has valid connectivity data at any time during the decoding +// process (valid with respect to the decoded portion of the mesh). The standard +// Edgebreaker decoder used two passes (forward decoding + zipping) which not +// only prevented us from having a valid connectivity but it was also slower. +// The main benefit of having the valid connectivity is that we can use the +// known connectivity to predict encoded symbols that can improve the +// compression rate. +template <class TraversalDecoderT> +class MeshEdgebreakerDecoderImpl : public MeshEdgebreakerDecoderImplInterface { + public: + MeshEdgebreakerDecoderImpl(); + bool Init(MeshEdgebreakerDecoder *decoder) override; + + const MeshAttributeCornerTable *GetAttributeCornerTable( + int att_id) const override; + const MeshAttributeIndicesEncodingData *GetAttributeEncodingData( + int att_id) const override; + + bool CreateAttributesDecoder(int32_t att_decoder_id) override; + bool DecodeConnectivity() override; + bool OnAttributesDecoded() override; + MeshEdgebreakerDecoder *GetDecoder() const override { return decoder_; } + const CornerTable *GetCornerTable() const override { + return corner_table_.get(); + } + + private: + // Creates a vertex traversal sequencer for the specified |TraverserT| type. + template <class TraverserT> + std::unique_ptr<PointsSequencer> CreateVertexTraversalSequencer( + MeshAttributeIndicesEncodingData *encoding_data); + + // Decodes connectivity between vertices (vertex indices). + // Returns the number of vertices created by the decoder or -1 on error. + int DecodeConnectivity(int num_symbols); + + // Returns true if the current symbol was part of a topology split event. This + // means that the current face was connected to the left edge of a face + // encoded with the TOPOLOGY_S symbol. |out_symbol_edge| can be used to + // identify which edge of the source symbol was connected to the TOPOLOGY_S + // symbol. + bool IsTopologySplit(int encoder_symbol_id, EdgeFaceName *out_face_edge, + int *out_encoder_split_symbol_id) { + if (topology_split_data_.size() == 0) + return false; + if (topology_split_data_.back().source_symbol_id > + static_cast<uint32_t>(encoder_symbol_id)) { + // Something is wrong; if the desired source symbol is greater than the + // current encoder_symbol_id, we missed it, or the input was tampered + // (|encoder_symbol_id| keeps decreasing). + // Return invalid symbol id to notify the decoder that there was an + // error. + *out_encoder_split_symbol_id = -1; + return true; + } + if (topology_split_data_.back().source_symbol_id != encoder_symbol_id) + return false; + *out_face_edge = + static_cast<EdgeFaceName>(topology_split_data_.back().source_edge); + *out_encoder_split_symbol_id = topology_split_data_.back().split_symbol_id; + // Remove the latest split event. + topology_split_data_.pop_back(); + return true; + } + + // Decodes event data for hole and topology split events and stores them for + // future use. + // Returns the number of parsed bytes, or -1 on error. + int32_t DecodeHoleAndTopologySplitEvents(DecoderBuffer *decoder_buffer); + + // Decodes all non-position attribute connectivity on the currently + // processed face. +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + bool DecodeAttributeConnectivitiesOnFaceLegacy(CornerIndex corner); +#endif + bool DecodeAttributeConnectivitiesOnFace(CornerIndex corner); + + // Initializes mapping between corners and point ids. + bool AssignPointsToCorners(int num_connectivity_verts); + + bool IsFaceVisited(CornerIndex corner_id) const { + if (corner_id < 0) + return true; // Invalid corner signalizes that the face does not exist. + return visited_faces_[corner_table_->Face(corner_id).value()]; + } + + void SetOppositeCorners(CornerIndex corner_0, CornerIndex corner_1) { + corner_table_->SetOppositeCorner(corner_0, corner_1); + corner_table_->SetOppositeCorner(corner_1, corner_0); + } + + MeshEdgebreakerDecoder *decoder_; + + std::unique_ptr<CornerTable> corner_table_; + + // Stack used for storing corners that need to be traversed when decoding + // mesh vertices. New corner is added for each initial face and a split + // symbol, and one corner is removed when the end symbol is reached. + // Stored as member variable to prevent frequent memory reallocations when + // handling meshes with lots of disjoint components. Originally, we used + // recursive functions to handle this behavior, but that can cause stack + // memory overflow when compressing huge meshes. + std::vector<CornerIndex> corner_traversal_stack_; + + // Array stores the number of visited visited for each mesh traversal. + std::vector<int> vertex_traversal_length_; + + // List of decoded topology split events. + std::vector<TopologySplitEventData> topology_split_data_; + + // List of decoded hole events. + std::vector<HoleEventData> hole_event_data_; + + // Configuration of the initial face for each mesh component. + std::vector<bool> init_face_configurations_; + + // Initial corner for each traversal. + std::vector<CornerIndex> init_corners_; + + // Id of the last processed input symbol. + int last_symbol_id_; + + // Id of the last decoded vertex. + int last_vert_id_; + + // Id of the last decoded face. + int last_face_id_; + + // Array for marking visited faces. + std::vector<bool> visited_faces_; + // Array for marking visited vertices. + std::vector<bool> visited_verts_; + // Array for marking vertices on open boundaries. + std::vector<bool> is_vert_hole_; + + // The number of new vertices added by the encoder (because of non-manifold + // vertices on the input mesh). + // If there are no non-manifold edges/vertices on the input mesh, this should + // be 0. + int num_new_vertices_; + // For every newly added vertex, this array stores it's mapping to the + // parent vertex id of the encoded mesh. + std::unordered_map<int, int> new_to_parent_vertex_map_; + // The number of vertices that were encoded (can be different from the number + // of vertices of the input mesh). + int num_encoded_vertices_; + + // Array for storing the encoded corner ids in the order their associated + // vertices were decoded. + std::vector<int32_t> processed_corner_ids_; + + // Array storing corners in the order they were visited during the + // connectivity decoding (always storing the tip corner of each newly visited + // face). + std::vector<int> processed_connectivity_corners_; + + MeshAttributeIndicesEncodingData pos_encoding_data_; + + // Id of an attributes decoder that uses |pos_encoding_data_|. + int pos_data_decoder_id_; + + // Data for non-position attributes used by the decoder. + struct AttributeData { + AttributeData() : decoder_id(-1), is_connectivity_used(true) {} + // Id of the attribute decoder that was used to decode this attribute data. + int decoder_id; + MeshAttributeCornerTable connectivity_data; + // Flag that can mark the connectivity_data invalid. In such case the base + // corner table of the mesh should be used instead. + bool is_connectivity_used; + MeshAttributeIndicesEncodingData encoding_data; + // Opposite corners to attribute seam edges. + std::vector<int32_t> attribute_seam_corners; + }; + std::vector<AttributeData> attribute_data_; + + TraversalDecoderT traversal_decoder_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl_interface.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl_interface.h new file mode 100644 index 00000000000..31fabf252d8 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl_interface.h @@ -0,0 +1,47 @@ +// 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_MESH_MESH_EDGEBREAKER_DECODER_IMPL_INTERFACE_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_INTERFACE_H_ + +#include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h" +#include "draco/mesh/mesh_attribute_corner_table.h" + +namespace draco { + +// Forward declaration is necessary here to avoid circular dependencies. +class MeshEdgebreakerDecoder; + +// Abstract interface used by MeshEdgebreakerDecoder to interact with the actual +// implementation of the edgebreaker decoding method. +class MeshEdgebreakerDecoderImplInterface { + public: + virtual ~MeshEdgebreakerDecoderImplInterface() = default; + virtual bool Init(MeshEdgebreakerDecoder *decoder) = 0; + + virtual const MeshAttributeCornerTable *GetAttributeCornerTable( + int att_id) const = 0; + virtual const MeshAttributeIndicesEncodingData *GetAttributeEncodingData( + int att_id) const = 0; + virtual bool CreateAttributesDecoder(int32_t att_decoder_id) = 0; + virtual bool DecodeConnectivity() = 0; + virtual bool OnAttributesDecoded() = 0; + + virtual MeshEdgebreakerDecoder *GetDecoder() const = 0; + virtual const CornerTable *GetCornerTable() const = 0; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_INTERFACE_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder.cc new file mode 100644 index 00000000000..ad87f9403af --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder.cc @@ -0,0 +1,184 @@ +// 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. +// +#include "draco/compression/mesh/mesh_edgebreaker_encoder.h" + +#include "draco/compression/mesh/mesh_edgebreaker_encoder_impl.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_predictive_encoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_valence_encoder.h" + +namespace draco { + +MeshEdgebreakerEncoder::MeshEdgebreakerEncoder() {} + +bool MeshEdgebreakerEncoder::InitializeEncoder() { + const bool is_standard_edgebreaker_available = + options()->IsFeatureSupported(features::kEdgebreaker); + const bool is_predictive_edgebreaker_available = + options()->IsFeatureSupported(features::kPredictiveEdgebreaker); + + impl_ = nullptr; + // For tiny meshes it's usually better to use the basic edgebreaker as the + // overhead of the predictive one may turn out to be too big. + // TODO(ostava): For now we have a set limit for forcing the basic edgebreaker + // based on the number of faces, but a more complex heuristic may be used if + // needed. + const bool is_tiny_mesh = mesh()->num_faces() < 1000; + + int selected_edgebreaker_method = + options()->GetGlobalInt("edgebreaker_method", -1); + if (selected_edgebreaker_method == -1) { + if (is_standard_edgebreaker_available && + (options()->GetSpeed() >= 5 || !is_predictive_edgebreaker_available || + is_tiny_mesh)) { + selected_edgebreaker_method = MESH_EDGEBREAKER_STANDARD_ENCODING; + } else { + selected_edgebreaker_method = MESH_EDGEBREAKER_VALENCE_ENCODING; + } + } + + if (selected_edgebreaker_method == MESH_EDGEBREAKER_STANDARD_ENCODING) { + if (is_standard_edgebreaker_available) { + buffer()->Encode( + static_cast<uint8_t>(MESH_EDGEBREAKER_STANDARD_ENCODING)); + impl_ = std::unique_ptr<MeshEdgebreakerEncoderImplInterface>( + new MeshEdgebreakerEncoderImpl<MeshEdgebreakerTraversalEncoder>()); + } + } else if (selected_edgebreaker_method == MESH_EDGEBREAKER_VALENCE_ENCODING) { + buffer()->Encode(static_cast<uint8_t>(MESH_EDGEBREAKER_VALENCE_ENCODING)); + impl_ = std::unique_ptr<MeshEdgebreakerEncoderImplInterface>( + new MeshEdgebreakerEncoderImpl< + MeshEdgebreakerTraversalValenceEncoder>()); + } + if (!impl_) + return false; + if (!impl_->Init(this)) + return false; + return true; +} + +bool MeshEdgebreakerEncoder::GenerateAttributesEncoder(int32_t att_id) { + if (!impl_->GenerateAttributesEncoder(att_id)) + return false; + return true; +} + +bool MeshEdgebreakerEncoder::EncodeAttributesEncoderIdentifier( + int32_t att_encoder_id) { + if (!impl_->EncodeAttributesEncoderIdentifier(att_encoder_id)) + return false; + return true; +} + +bool MeshEdgebreakerEncoder::EncodeConnectivity() { + return impl_->EncodeConnectivity(); +} + +void MeshEdgebreakerEncoder::ComputeNumberOfEncodedPoints() { + if (!impl_) + return; + const CornerTable *const corner_table = impl_->GetCornerTable(); + if (!corner_table) + return; + size_t num_points = + corner_table->num_vertices() - corner_table->NumIsolatedVertices(); + + if (mesh()->num_attributes() > 1) { + // Gather all corner tables for all non-position attributes. + std::vector<const MeshAttributeCornerTable *> attribute_corner_tables; + for (int i = 0; i < mesh()->num_attributes(); ++i) { + if (mesh()->attribute(i)->attribute_type() == GeometryAttribute::POSITION) + continue; + const MeshAttributeCornerTable *const att_corner_table = + GetAttributeCornerTable(i); + // Attribute corner table may not be used in some configurations. For + // these cases we can assume the attribute connectivity to be the same as + // the connectivity of the position data. + if (att_corner_table) + attribute_corner_tables.push_back(att_corner_table); + } + + // Add a new point based on the configuration of interior attribute seams + // (replicating what the decoder would do). + for (VertexIndex vi(0); vi < corner_table->num_vertices(); ++vi) { + if (corner_table->IsVertexIsolated(vi)) + continue; + // Go around all corners of the vertex and keep track of the observed + // attribute seams. + const CornerIndex first_corner_index = corner_table->LeftMostCorner(vi); + const PointIndex first_point_index = + mesh()->CornerToPointId(first_corner_index); + + PointIndex last_point_index = first_point_index; + CornerIndex last_corner_index = first_corner_index; + CornerIndex corner_index = corner_table->SwingRight(first_corner_index); + size_t num_attribute_seams = 0; + while (corner_index != kInvalidCornerIndex) { + const PointIndex point_index = mesh()->CornerToPointId(corner_index); + bool seam_found = false; + if (point_index != last_point_index) { + // Point index changed - new attribute seam detected. + seam_found = true; + last_point_index = point_index; + } else { + // Even though point indices matches, there still may be a seam caused + // by non-manifold connectivity of non-position attribute data. + for (int i = 0; i < attribute_corner_tables.size(); ++i) { + if (attribute_corner_tables[i]->Vertex(corner_index) != + attribute_corner_tables[i]->Vertex(last_corner_index)) { + seam_found = true; + break; // No need to process other attributes. + } + } + } + if (seam_found) { + ++num_attribute_seams; + } + + if (corner_index == first_corner_index) + break; + + // Proceed to the next corner + last_corner_index = corner_index; + corner_index = corner_table->SwingRight(corner_index); + } + + if (!corner_table->IsOnBoundary(vi) && num_attribute_seams > 0) { + // If the last visited point index is the same as the first point index + // we traveled all the way around the vertex. In this case the number of + // new points should be num_attribute_seams - 1 + num_points += num_attribute_seams - 1; + } else { + // Else the vertex was either on a boundary (i.e. we couldn't travel all + // around the vertex), or we ended up at a different point. In both of + // these cases, the number of new points is equal to the number of + // attribute seams. + num_points += num_attribute_seams; + } + } + } + set_num_encoded_points(num_points); +} + +void MeshEdgebreakerEncoder::ComputeNumberOfEncodedFaces() { + if (!impl_) + return; + const CornerTable *const corner_table = impl_->GetCornerTable(); + if (!corner_table) + return; + set_num_encoded_faces(corner_table->num_faces() - + corner_table->NumDegeneratedFaces()); +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder.h new file mode 100644 index 00000000000..78615fb0287 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder.h @@ -0,0 +1,73 @@ +// 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_MESH_MESH_EDGEBREAKER_ENCODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_ENCODER_H_ + +#include <unordered_map> + +#include "draco/compression/mesh/mesh_edgebreaker_encoder_impl_interface.h" +#include "draco/compression/mesh/mesh_edgebreaker_shared.h" +#include "draco/compression/mesh/mesh_encoder.h" +#include "draco/mesh/corner_table.h" + +namespace draco { + +// Class implements the edge breaker geometry compression method as described +// in "3D Compression Made Simple: Edgebreaker on a Corner-Table" by Rossignac +// at al.'01. http://www.cc.gatech.edu/~jarek/papers/CornerTableSMI.pdf +class MeshEdgebreakerEncoder : public MeshEncoder { + public: + MeshEdgebreakerEncoder(); + + const CornerTable *GetCornerTable() const override { + return impl_->GetCornerTable(); + } + + const MeshAttributeCornerTable *GetAttributeCornerTable( + int att_id) const override { + return impl_->GetAttributeCornerTable(att_id); + } + + const MeshAttributeIndicesEncodingData *GetAttributeEncodingData( + int att_id) const override { + return impl_->GetAttributeEncodingData(att_id); + } + + uint8_t GetEncodingMethod() const override { + return MESH_EDGEBREAKER_ENCODING; + } + + protected: + bool InitializeEncoder() override; + bool EncodeConnectivity() override; + bool GenerateAttributesEncoder(int32_t att_id) override; + bool EncodeAttributesEncoderIdentifier(int32_t att_encoder_id) override; + void ComputeNumberOfEncodedPoints() override; + void ComputeNumberOfEncodedFaces() override; + + private: + // The actual implementation of the edge breaker method. The implementations + // are in general specializations of a template class + // MeshEdgebreakerEncoderImpl where the template arguments control encoding + // of the connectivity data. The actual implementation is selected in this + // class based on the provided encoding options. Because this choice is done + // in run-time, the actual implementation has to be hidden behind the + // abstract interface MeshEdgebreakerEncoderImplInterface. + std::unique_ptr<MeshEdgebreakerEncoderImplInterface> impl_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_ENCODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder_impl.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder_impl.cc new file mode 100644 index 00000000000..89e6f0b5b12 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder_impl.cc @@ -0,0 +1,830 @@ +// 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. +// +#include "draco/compression/mesh/mesh_edgebreaker_encoder_impl.h" + +#include <algorithm> + +#include "draco/compression/attributes/sequential_attribute_encoders_controller.h" +#include "draco/compression/mesh/mesh_edgebreaker_encoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_predictive_encoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_valence_encoder.h" +#include "draco/compression/mesh/traverser/depth_first_traverser.h" +#include "draco/compression/mesh/traverser/max_prediction_degree_traverser.h" +#include "draco/compression/mesh/traverser/mesh_attribute_indices_encoding_observer.h" +#include "draco/compression/mesh/traverser/mesh_traversal_sequencer.h" +#include "draco/compression/mesh/traverser/traverser_base.h" +#include "draco/mesh/corner_table_iterators.h" +#include "draco/mesh/mesh_misc_functions.h" + +namespace draco { +// TODO(draco-eng) consider converting 'typedef' to 'using' and deduplicate. +typedef CornerIndex CornerIndex; +typedef FaceIndex FaceIndex; +typedef VertexIndex VertexIndex; + +template <class TraversalEncoder> +MeshEdgebreakerEncoderImpl<TraversalEncoder>::MeshEdgebreakerEncoderImpl() + : encoder_(nullptr), + mesh_(nullptr), + last_encoded_symbol_id_(-1), + num_split_symbols_(0), + use_single_connectivity_(false) {} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::Init( + MeshEdgebreakerEncoder *encoder) { + encoder_ = encoder; + mesh_ = encoder->mesh(); + attribute_encoder_to_data_id_map_.clear(); + + if (encoder_->options()->IsGlobalOptionSet("split_mesh_on_seams")) { + use_single_connectivity_ = + encoder_->options()->GetGlobalBool("split_mesh_on_seams", false); + } else if (encoder_->options()->GetSpeed() >= 6) { + // Else use default setting based on speed. + use_single_connectivity_ = true; + } else { + use_single_connectivity_ = false; + } + return true; +} + +template <class TraversalEncoder> +const MeshAttributeCornerTable * +MeshEdgebreakerEncoderImpl<TraversalEncoder>::GetAttributeCornerTable( + int att_id) const { + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + if (attribute_data_[i].attribute_index == att_id) { + if (attribute_data_[i].is_connectivity_used) + return &attribute_data_[i].connectivity_data; + return nullptr; + } + } + return nullptr; +} + +template <class TraversalEncoder> +const MeshAttributeIndicesEncodingData * +MeshEdgebreakerEncoderImpl<TraversalEncoder>::GetAttributeEncodingData( + int att_id) const { + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + if (attribute_data_[i].attribute_index == att_id) + return &attribute_data_[i].encoding_data; + } + return &pos_encoding_data_; +} + +template <class TraversalEncoder> +template <class TraverserT> +std::unique_ptr<PointsSequencer> +MeshEdgebreakerEncoderImpl<TraversalEncoder>::CreateVertexTraversalSequencer( + MeshAttributeIndicesEncodingData *encoding_data) { + typedef typename TraverserT::TraversalObserver AttObserver; + typedef typename TraverserT::CornerTable CornerTable; + + std::unique_ptr<MeshTraversalSequencer<TraverserT>> traversal_sequencer( + new MeshTraversalSequencer<TraverserT>(mesh_, encoding_data)); + + AttObserver att_observer(corner_table_.get(), mesh_, + traversal_sequencer.get(), encoding_data); + + TraverserT att_traverser; + att_traverser.Init(corner_table_.get(), att_observer); + + // Set order of corners to simulate the corner order of the decoder. + traversal_sequencer->SetCornerOrder(processed_connectivity_corners_); + traversal_sequencer->SetTraverser(att_traverser); + return std::move(traversal_sequencer); +} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::GenerateAttributesEncoder( + int32_t att_id) { + // For now, either create one encoder for each attribute or use a single + // encoder for all attributes. Ideally we can share the same encoder for + // a sub-set of attributes with the same connectivity (this is especially true + // for per-vertex attributes). + if (use_single_connectivity_ && GetEncoder()->num_attributes_encoders() > 0) { + // We are using single connectivity and we already have an attribute + // encoder. Add the attribute to the encoder and return. + GetEncoder()->attributes_encoder(0)->AddAttributeId(att_id); + return true; + } + const int32_t element_type = + GetEncoder()->mesh()->GetAttributeElementType(att_id); + const PointAttribute *const att = + GetEncoder()->point_cloud()->attribute(att_id); + int32_t att_data_id = -1; + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + if (attribute_data_[i].attribute_index == att_id) { + att_data_id = i; + break; + } + } + MeshTraversalMethod traversal_method = MESH_TRAVERSAL_DEPTH_FIRST; + std::unique_ptr<PointsSequencer> sequencer; + if (use_single_connectivity_ || + att->attribute_type() == GeometryAttribute::POSITION || + element_type == MESH_VERTEX_ATTRIBUTE || + (element_type == MESH_CORNER_ATTRIBUTE && + attribute_data_[att_data_id].connectivity_data.no_interior_seams())) { + // Per-vertex attribute reached, use the basic corner table to traverse the + // mesh. + MeshAttributeIndicesEncodingData *encoding_data; + if (use_single_connectivity_ || + att->attribute_type() == GeometryAttribute::POSITION) { + encoding_data = &pos_encoding_data_; + } else { + encoding_data = &attribute_data_[att_data_id].encoding_data; + + // Ensure we use the correct number of vertices in the encoding data. + encoding_data->vertex_to_encoded_attribute_value_index_map.assign( + corner_table_->num_vertices(), -1); + + // Mark the attribute specific connectivity data as not used as we use the + // position attribute connectivity data. + attribute_data_[att_data_id].is_connectivity_used = false; + } + + if (GetEncoder()->options()->GetSpeed() == 0 && + att->attribute_type() == GeometryAttribute::POSITION) { + traversal_method = MESH_TRAVERSAL_PREDICTION_DEGREE; + if (use_single_connectivity_ && mesh_->num_attributes() > 1) { + // Make sure we don't use the prediction degree traversal when we encode + // multiple attributes using the same connectivity. + // TODO(ostava): We should investigate this and see if the prediction + // degree can be actually used efficiently for non-position attributes. + traversal_method = MESH_TRAVERSAL_DEPTH_FIRST; + } + } + // Defining sequencer via a traversal scheme. + if (traversal_method == MESH_TRAVERSAL_PREDICTION_DEGREE) { + typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver; + typedef MaxPredictionDegreeTraverser<CornerTable, AttObserver> + AttTraverser; + sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data); + } else if (traversal_method == MESH_TRAVERSAL_DEPTH_FIRST) { + typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver; + typedef DepthFirstTraverser<CornerTable, AttObserver> AttTraverser; + sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data); + } + } else { + // Per-corner attribute encoder. + typedef MeshAttributeIndicesEncodingObserver<MeshAttributeCornerTable> + AttObserver; + typedef DepthFirstTraverser<MeshAttributeCornerTable, AttObserver> + AttTraverser; + + MeshAttributeIndicesEncodingData *const encoding_data = + &attribute_data_[att_data_id].encoding_data; + const MeshAttributeCornerTable *const corner_table = + &attribute_data_[att_data_id].connectivity_data; + + // Ensure we use the correct number of vertices in the encoding data. + attribute_data_[att_data_id] + .encoding_data.vertex_to_encoded_attribute_value_index_map.assign( + attribute_data_[att_data_id].connectivity_data.num_vertices(), -1); + + std::unique_ptr<MeshTraversalSequencer<AttTraverser>> traversal_sequencer( + new MeshTraversalSequencer<AttTraverser>(mesh_, encoding_data)); + + AttObserver att_observer(corner_table, mesh_, traversal_sequencer.get(), + encoding_data); + + AttTraverser att_traverser; + att_traverser.Init(corner_table, att_observer); + + // Set order of corners to simulate the corner order of the decoder. + traversal_sequencer->SetCornerOrder(processed_connectivity_corners_); + traversal_sequencer->SetTraverser(att_traverser); + sequencer = std::move(traversal_sequencer); + } + + if (!sequencer) + return false; + + if (att_data_id == -1) { + pos_traversal_method_ = traversal_method; + } else { + attribute_data_[att_data_id].traversal_method = traversal_method; + } + + std::unique_ptr<SequentialAttributeEncodersController> att_controller( + new SequentialAttributeEncodersController(std::move(sequencer), att_id)); + + // Update the mapping between the encoder id and the attribute data id. + // This will be used by the decoder to select the appropriate attribute + // decoder and the correct connectivity. + attribute_encoder_to_data_id_map_.push_back(att_data_id); + GetEncoder()->AddAttributesEncoder(std::move(att_controller)); + return true; +} // namespace draco + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>:: + EncodeAttributesEncoderIdentifier(int32_t att_encoder_id) { + const int8_t att_data_id = attribute_encoder_to_data_id_map_[att_encoder_id]; + encoder_->buffer()->Encode(att_data_id); + + // Also encode the type of the encoder that we used. + int32_t element_type = MESH_VERTEX_ATTRIBUTE; + MeshTraversalMethod traversal_method; + if (att_data_id >= 0) { + const int32_t att_id = attribute_data_[att_data_id].attribute_index; + element_type = GetEncoder()->mesh()->GetAttributeElementType(att_id); + traversal_method = attribute_data_[att_data_id].traversal_method; + } else { + traversal_method = pos_traversal_method_; + } + if (element_type == MESH_VERTEX_ATTRIBUTE || + (element_type == MESH_CORNER_ATTRIBUTE && + attribute_data_[att_data_id].connectivity_data.no_interior_seams())) { + // Per-vertex encoder. + encoder_->buffer()->Encode(static_cast<uint8_t>(MESH_VERTEX_ATTRIBUTE)); + } else { + // Per-corner encoder. + encoder_->buffer()->Encode(static_cast<uint8_t>(MESH_CORNER_ATTRIBUTE)); + } + // Encode the mesh traversal method. + encoder_->buffer()->Encode(static_cast<uint8_t>(traversal_method)); + return true; +} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::EncodeConnectivity() { + // To encode the mesh, we need face connectivity data stored in a corner + // table. To compute the connectivity we must use indices associated with + // POSITION attribute, because they define which edges can be connected + // together, unless the option |use_single_connectivity_| is set in which case + // we break the mesh along attribute seams and use the same connectivity for + // all attributes. + if (use_single_connectivity_) { + corner_table_ = CreateCornerTableFromAllAttributes(mesh_); + } else { + corner_table_ = CreateCornerTableFromPositionAttribute(mesh_); + } + if (corner_table_ == nullptr || + corner_table_->num_faces() == corner_table_->NumDegeneratedFaces()) { + // Failed to construct the corner table. + // TODO(ostava): Add better error reporting. + return false; + } + + traversal_encoder_.Init(this); + + // Also encode the total number of vertices that is going to be encoded. + // This can be different from the mesh_->num_points() + num_new_vertices, + // because some of the vertices of the input mesh can be ignored (e.g. + // vertices on degenerated faces or isolated vertices not attached to any + // face). + const uint32_t num_vertices_to_be_encoded = + corner_table_->num_vertices() - corner_table_->NumIsolatedVertices(); + EncodeVarint(num_vertices_to_be_encoded, encoder_->buffer()); + + const uint32_t num_faces = + corner_table_->num_faces() - corner_table_->NumDegeneratedFaces(); + EncodeVarint(num_faces, encoder_->buffer()); + + // Reset encoder data that may have been initialized in previous runs. + visited_faces_.assign(mesh_->num_faces(), false); + pos_encoding_data_.vertex_to_encoded_attribute_value_index_map.assign( + corner_table_->num_vertices(), -1); + pos_encoding_data_.encoded_attribute_value_index_to_corner_map.clear(); + pos_encoding_data_.encoded_attribute_value_index_to_corner_map.reserve( + corner_table_->num_faces() * 3); + visited_vertex_ids_.assign(corner_table_->num_vertices(), false); + vertex_traversal_length_.clear(); + last_encoded_symbol_id_ = -1; + num_split_symbols_ = 0; + topology_split_event_data_.clear(); + face_to_split_symbol_map_.clear(); + visited_holes_.clear(); + vertex_hole_id_.assign(corner_table_->num_vertices(), -1); + processed_connectivity_corners_.clear(); + processed_connectivity_corners_.reserve(corner_table_->num_faces()); + pos_encoding_data_.num_values = 0; + + if (!FindHoles()) + return false; + + if (!InitAttributeData()) + return false; + + const uint8_t num_attribute_data = + static_cast<uint8_t>(attribute_data_.size()); + encoder_->buffer()->Encode(num_attribute_data); + traversal_encoder_.SetNumAttributeData(num_attribute_data); + + const int num_corners = corner_table_->num_corners(); + + traversal_encoder_.Start(); + + std::vector<CornerIndex> init_face_connectivity_corners; + // Traverse the surface starting from each unvisited corner. + for (int c_id = 0; c_id < num_corners; ++c_id) { + CornerIndex corner_index(c_id); + const FaceIndex face_id = corner_table_->Face(corner_index); + if (visited_faces_[face_id.value()]) + continue; // Face has been already processed. + if (corner_table_->IsDegenerated(face_id)) + continue; // Ignore degenerated faces. + + CornerIndex start_corner; + const bool interior_config = + FindInitFaceConfiguration(face_id, &start_corner); + traversal_encoder_.EncodeStartFaceConfiguration(interior_config); + + if (interior_config) { + // Select the correct vertex on the face as the root. + corner_index = start_corner; + const VertexIndex vert_id = corner_table_->Vertex(corner_index); + // Mark all vertices of a given face as visited. + const VertexIndex next_vert_id = + corner_table_->Vertex(corner_table_->Next(corner_index)); + const VertexIndex prev_vert_id = + corner_table_->Vertex(corner_table_->Previous(corner_index)); + + visited_vertex_ids_[vert_id.value()] = true; + visited_vertex_ids_[next_vert_id.value()] = true; + visited_vertex_ids_[prev_vert_id.value()] = true; + // New traversal started. Initiate it's length with the first vertex. + vertex_traversal_length_.push_back(1); + + // Mark the face as visited. + visited_faces_[face_id.value()] = true; + // Start compressing from the opposite face of the "next" corner. This way + // the first encoded corner corresponds to the tip corner of the regular + // edgebreaker traversal (essentially the initial face can be then viewed + // as a TOPOLOGY_C face). + init_face_connectivity_corners.push_back( + corner_table_->Next(corner_index)); + const CornerIndex opp_id = + corner_table_->Opposite(corner_table_->Next(corner_index)); + const FaceIndex opp_face_id = corner_table_->Face(opp_id); + if (opp_face_id != kInvalidFaceIndex && + !visited_faces_[opp_face_id.value()]) { + if (!EncodeConnectivityFromCorner(opp_id)) + return false; + } + } else { + // Boundary configuration. We start on a boundary rather than on a face. + // First encode the hole that's opposite to the start_corner. + EncodeHole(corner_table_->Next(start_corner), true); + // Start processing the face opposite to the boundary edge (the face + // containing the start_corner). + if (!EncodeConnectivityFromCorner(start_corner)) + return false; + } + } + // Reverse the order of connectivity corners to match the order in which + // they are going to be decoded. + std::reverse(processed_connectivity_corners_.begin(), + processed_connectivity_corners_.end()); + // Append the init face connectivity corners (which are processed in order by + // the decoder after the regular corners. + processed_connectivity_corners_.insert(processed_connectivity_corners_.end(), + init_face_connectivity_corners.begin(), + init_face_connectivity_corners.end()); + // Encode connectivity for all non-position attributes. + if (attribute_data_.size() > 0) { + // Use the same order of corner that will be used by the decoder. + visited_faces_.assign(mesh_->num_faces(), false); + for (CornerIndex ci : processed_connectivity_corners_) { + EncodeAttributeConnectivitiesOnFace(ci); + } + } + traversal_encoder_.Done(); + + // Encode the number of symbols. + const uint32_t num_encoded_symbols = + static_cast<uint32_t>(traversal_encoder_.NumEncodedSymbols()); + EncodeVarint(num_encoded_symbols, encoder_->buffer()); + + // Encode the number of split symbols. + EncodeVarint(num_split_symbols_, encoder_->buffer()); + + // Append the traversal buffer. + if (!EncodeSplitData()) + return false; + encoder_->buffer()->Encode(traversal_encoder_.buffer().data(), + traversal_encoder_.buffer().size()); + + return true; +} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::EncodeSplitData() { + uint32_t num_events = + static_cast<uint32_t>(topology_split_event_data_.size()); + EncodeVarint(num_events, encoder_->buffer()); + if (num_events > 0) { + // Encode split symbols using delta and varint coding. Split edges are + // encoded using direct bit coding. + int last_source_symbol_id = 0; // Used for delta coding. + for (uint32_t i = 0; i < num_events; ++i) { + const TopologySplitEventData &event_data = topology_split_event_data_[i]; + // Encode source symbol id as delta from the previous source symbol id. + // Source symbol ids are always stored in increasing order so the delta is + // going to be positive. + EncodeVarint<uint32_t>( + event_data.source_symbol_id - last_source_symbol_id, + encoder_->buffer()); + // Encode split symbol id as delta from the current source symbol id. + // Split symbol id is always smaller than source symbol id so the below + // delta is going to be positive. + EncodeVarint<uint32_t>( + event_data.source_symbol_id - event_data.split_symbol_id, + encoder_->buffer()); + last_source_symbol_id = event_data.source_symbol_id; + } + encoder_->buffer()->StartBitEncoding(num_events, false); + for (uint32_t i = 0; i < num_events; ++i) { + const TopologySplitEventData &event_data = topology_split_event_data_[i]; + encoder_->buffer()->EncodeLeastSignificantBits32(1, + event_data.source_edge); + } + encoder_->buffer()->EndBitEncoding(); + } + return true; +} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::FindInitFaceConfiguration( + FaceIndex face_id, CornerIndex *out_corner) const { + CornerIndex corner_index = CornerIndex(3 * face_id.value()); + for (int i = 0; i < 3; ++i) { + if (corner_table_->Opposite(corner_index) == kInvalidCornerIndex) { + // If there is a boundary edge, the configuration is exterior and return + // the CornerIndex opposite to the first boundary edge. + *out_corner = corner_index; + return false; + } + if (vertex_hole_id_[corner_table_->Vertex(corner_index).value()] != -1) { + // Boundary vertex found. Find the first boundary edge attached to the + // point and return the corner opposite to it. + CornerIndex right_corner = corner_index; + while (right_corner != kInvalidCornerIndex) { + corner_index = right_corner; + right_corner = corner_table_->SwingRight(right_corner); + } + // |corner_index| now lies on a boundary edge and its previous corner is + // guaranteed to be the opposite corner of the boundary edge. + *out_corner = corner_table_->Previous(corner_index); + return false; + } + corner_index = corner_table_->Next(corner_index); + } + // Else we have an interior configuration. Return the first corner id. + *out_corner = corner_index; + return true; +} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::EncodeConnectivityFromCorner( + CornerIndex corner_id) { + corner_traversal_stack_.clear(); + corner_traversal_stack_.push_back(corner_id); + const int num_faces = mesh_->num_faces(); + while (!corner_traversal_stack_.empty()) { + // Currently processed corner. + corner_id = corner_traversal_stack_.back(); + // Make sure the face hasn't been visited yet. + if (corner_id == kInvalidCornerIndex || + visited_faces_[corner_table_->Face(corner_id).value()]) { + // This face has been already traversed. + corner_traversal_stack_.pop_back(); + continue; + } + int num_visited_faces = 0; + while (num_visited_faces < num_faces) { + // Mark the current face as visited. + ++num_visited_faces; + ++last_encoded_symbol_id_; + + const FaceIndex face_id = corner_table_->Face(corner_id); + visited_faces_[face_id.value()] = true; + processed_connectivity_corners_.push_back(corner_id); + traversal_encoder_.NewCornerReached(corner_id); + const VertexIndex vert_id = corner_table_->Vertex(corner_id); + const bool on_boundary = (vertex_hole_id_[vert_id.value()] != -1); + if (!IsVertexVisited(vert_id)) { + // A new unvisited vertex has been reached. We need to store its + // position difference using next, prev, and opposite vertices. + visited_vertex_ids_[vert_id.value()] = true; + if (!on_boundary) { + // If the vertex is on boundary it must correspond to an unvisited + // hole and it will be encoded with TOPOLOGY_S symbol later). + traversal_encoder_.EncodeSymbol(TOPOLOGY_C); + // Move to the right triangle. + corner_id = GetRightCorner(corner_id); + continue; + } + } + // The current vertex has been already visited or it was on a boundary. + // We need to determine whether we can visit any of it's neighboring + // faces. + const CornerIndex right_corner_id = GetRightCorner(corner_id); + const CornerIndex left_corner_id = GetLeftCorner(corner_id); + const FaceIndex right_face_id = corner_table_->Face(right_corner_id); + const FaceIndex left_face_id = corner_table_->Face(left_corner_id); + if (IsRightFaceVisited(corner_id)) { + // Right face has been already visited. + // Check whether there is a topology split event. + if (right_face_id != kInvalidFaceIndex) + CheckAndStoreTopologySplitEvent(last_encoded_symbol_id_, + face_id.value(), RIGHT_FACE_EDGE, + right_face_id.value()); + if (IsLeftFaceVisited(corner_id)) { + // Both neighboring faces are visited. End reached. + // Check whether there is a topology split event on the left face. + if (left_face_id != kInvalidFaceIndex) + CheckAndStoreTopologySplitEvent(last_encoded_symbol_id_, + face_id.value(), LEFT_FACE_EDGE, + left_face_id.value()); + traversal_encoder_.EncodeSymbol(TOPOLOGY_E); + corner_traversal_stack_.pop_back(); + break; // Break from the while (num_visited_faces < num_faces) loop. + } else { + traversal_encoder_.EncodeSymbol(TOPOLOGY_R); + // Go to the left face. + corner_id = left_corner_id; + } + } else { + // Right face was not visited. + if (IsLeftFaceVisited(corner_id)) { + // Check whether there is a topology split event on the left face. + if (left_face_id != kInvalidFaceIndex) + CheckAndStoreTopologySplitEvent(last_encoded_symbol_id_, + face_id.value(), LEFT_FACE_EDGE, + left_face_id.value()); + traversal_encoder_.EncodeSymbol(TOPOLOGY_L); + // Left face visited, go to the right one. + corner_id = right_corner_id; + } else { + traversal_encoder_.EncodeSymbol(TOPOLOGY_S); + ++num_split_symbols_; + // Both neighboring faces are unvisited, we need to visit both of + // them. + if (on_boundary) { + // The tip vertex is on a hole boundary. If the hole hasn't been + // visited yet we need to encode it. + const int hole_id = vertex_hole_id_[vert_id.value()]; + if (!visited_holes_[hole_id]) { + EncodeHole(corner_id, false); + } + } + face_to_split_symbol_map_[face_id.value()] = last_encoded_symbol_id_; + // Split the traversal. + // First make the top of the current corner stack point to the left + // face (this one will be processed second). + corner_traversal_stack_.back() = left_corner_id; + // Add a new corner to the top of the stack (right face needs to + // be traversed first). + corner_traversal_stack_.push_back(right_corner_id); + // Break from the while (num_visited_faces < num_faces) loop. + break; + } + } + } + } + return true; // All corners have been processed. +} + +template <class TraversalEncoder> +int MeshEdgebreakerEncoderImpl<TraversalEncoder>::EncodeHole( + CornerIndex start_corner_id, bool encode_first_vertex) { + // We know that the start corner lies on a hole but we first need to find the + // boundary edge going from that vertex. It is the first edge in CW + // direction. + CornerIndex corner_id = start_corner_id; + corner_id = corner_table_->Previous(corner_id); + while (corner_table_->Opposite(corner_id) != kInvalidCornerIndex) { + corner_id = corner_table_->Opposite(corner_id); + corner_id = corner_table_->Next(corner_id); + } + const VertexIndex start_vertex_id = corner_table_->Vertex(start_corner_id); + + int num_encoded_hole_verts = 0; + if (encode_first_vertex) { + visited_vertex_ids_[start_vertex_id.value()] = true; + ++num_encoded_hole_verts; + } + + // corner_id is now opposite to the boundary edge. + // Mark the hole as visited. + visited_holes_[vertex_hole_id_[start_vertex_id.value()]] = true; + // Get the start vertex of the edge and use it as a reference. + VertexIndex start_vert_id = + corner_table_->Vertex(corner_table_->Next(corner_id)); + // Get the end vertex of the edge. + VertexIndex act_vertex_id = + corner_table_->Vertex(corner_table_->Previous(corner_id)); + while (act_vertex_id != start_vertex_id) { + // Encode the end vertex of the boundary edge. + + start_vert_id = act_vertex_id; + + // Mark the vertex as visited. + visited_vertex_ids_[act_vertex_id.value()] = true; + ++num_encoded_hole_verts; + corner_id = corner_table_->Next(corner_id); + // Look for the next attached open boundary edge. + while (corner_table_->Opposite(corner_id) != kInvalidCornerIndex) { + corner_id = corner_table_->Opposite(corner_id); + corner_id = corner_table_->Next(corner_id); + } + act_vertex_id = corner_table_->Vertex(corner_table_->Previous(corner_id)); + } + return num_encoded_hole_verts; +} + +template <class TraversalEncoder> +CornerIndex MeshEdgebreakerEncoderImpl<TraversalEncoder>::GetRightCorner( + CornerIndex corner_id) const { + const CornerIndex next_corner_id = corner_table_->Next(corner_id); + return corner_table_->Opposite(next_corner_id); +} + +template <class TraversalEncoder> +CornerIndex MeshEdgebreakerEncoderImpl<TraversalEncoder>::GetLeftCorner( + CornerIndex corner_id) const { + const CornerIndex prev_corner_id = corner_table_->Previous(corner_id); + return corner_table_->Opposite(prev_corner_id); +} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::IsRightFaceVisited( + CornerIndex corner_id) const { + const CornerIndex next_corner_id = corner_table_->Next(corner_id); + const CornerIndex opp_corner_id = corner_table_->Opposite(next_corner_id); + if (opp_corner_id != kInvalidCornerIndex) + return visited_faces_[corner_table_->Face(opp_corner_id).value()]; + // Else we are on a boundary. + return true; +} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::IsLeftFaceVisited( + CornerIndex corner_id) const { + const CornerIndex prev_corner_id = corner_table_->Previous(corner_id); + const CornerIndex opp_corner_id = corner_table_->Opposite(prev_corner_id); + if (opp_corner_id != kInvalidCornerIndex) + return visited_faces_[corner_table_->Face(opp_corner_id).value()]; + // Else we are on a boundary. + return true; +} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::FindHoles() { + // TODO(ostava): Add more error checking for invalid geometry data. + const int num_corners = corner_table_->num_corners(); + // Go over all corners and detect non-visited open boundaries + for (CornerIndex i(0); i < num_corners; ++i) { + if (corner_table_->IsDegenerated(corner_table_->Face(i))) + continue; // Don't process corners assigned to degenerated faces. + if (corner_table_->Opposite(i) == kInvalidCornerIndex) { + // No opposite corner means no opposite face, so the opposite edge + // of the corner is an open boundary. + // Check whether we have already traversed the boundary. + VertexIndex boundary_vert_id = + corner_table_->Vertex(corner_table_->Next(i)); + if (vertex_hole_id_[boundary_vert_id.value()] != -1) { + // The start vertex of the boundary edge is already assigned to an + // open boundary. No need to traverse it again. + continue; + } + // Else we found a new open boundary and we are going to traverse along it + // and mark all visited vertices. + const int boundary_id = static_cast<int>(visited_holes_.size()); + visited_holes_.push_back(false); + + CornerIndex corner_id = i; + while (vertex_hole_id_[boundary_vert_id.value()] == -1) { + // Mark the first vertex on the open boundary. + vertex_hole_id_[boundary_vert_id.value()] = boundary_id; + corner_id = corner_table_->Next(corner_id); + // Look for the next attached open boundary edge. + while (corner_table_->Opposite(corner_id) != kInvalidCornerIndex) { + corner_id = corner_table_->Opposite(corner_id); + corner_id = corner_table_->Next(corner_id); + } + // Id of the next vertex in the vertex on the hole. + boundary_vert_id = + corner_table_->Vertex(corner_table_->Next(corner_id)); + } + } + } + return true; +} + +template <class TraversalEncoder> +int MeshEdgebreakerEncoderImpl<TraversalEncoder>::GetSplitSymbolIdOnFace( + int face_id) const { + auto it = face_to_split_symbol_map_.find(face_id); + if (it == face_to_split_symbol_map_.end()) + return -1; + return it->second; +} + +template <class TraversalEncoder> +void MeshEdgebreakerEncoderImpl< + TraversalEncoder>::CheckAndStoreTopologySplitEvent(int src_symbol_id, + int /* src_face_id */, + EdgeFaceName src_edge, + int neighbor_face_id) { + const int symbol_id = GetSplitSymbolIdOnFace(neighbor_face_id); + if (symbol_id == -1) + return; // Not a split symbol, no topology split event could happen. + TopologySplitEventData event_data; + + event_data.split_symbol_id = symbol_id; + event_data.source_symbol_id = src_symbol_id; + event_data.source_edge = src_edge; + topology_split_event_data_.push_back(event_data); +} + +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl<TraversalEncoder>::InitAttributeData() { + if (use_single_connectivity_) + return true; // All attributes use the same connectivity. + + const int num_attributes = mesh_->num_attributes(); + // Ignore the position attribute. It's decoded separately. + attribute_data_.resize(num_attributes - 1); + if (num_attributes == 1) + return true; + int data_index = 0; + for (int i = 0; i < num_attributes; ++i) { + const int32_t att_index = i; + if (mesh_->attribute(att_index)->attribute_type() == + GeometryAttribute::POSITION) + continue; + const PointAttribute *const att = mesh_->attribute(att_index); + attribute_data_[data_index].attribute_index = att_index; + attribute_data_[data_index] + .encoding_data.encoded_attribute_value_index_to_corner_map.clear(); + attribute_data_[data_index] + .encoding_data.encoded_attribute_value_index_to_corner_map.reserve( + corner_table_->num_corners()); + attribute_data_[data_index].encoding_data.num_values = 0; + attribute_data_[data_index].connectivity_data.InitFromAttribute( + mesh_, corner_table_.get(), att); + ++data_index; + } + return true; +} + +// TODO(ostava): Note that if the input mesh used the same attribute index on +// multiple different vertices, such attribute will be duplicated using the +// encoding below. Eventually, we may consider either using a different encoding +// scheme for such cases, or at least deduplicating the attributes in the +// decoder. +template <class TraversalEncoder> +bool MeshEdgebreakerEncoderImpl< + TraversalEncoder>::EncodeAttributeConnectivitiesOnFace(CornerIndex corner) { + // Three corners of the face. + const CornerIndex corners[3] = {corner, corner_table_->Next(corner), + corner_table_->Previous(corner)}; + + const FaceIndex src_face_id = corner_table_->Face(corner); + visited_faces_[src_face_id.value()] = true; + for (int c = 0; c < 3; ++c) { + const CornerIndex opp_corner = corner_table_->Opposite(corners[c]); + if (opp_corner == kInvalidCornerIndex) + continue; // Don't encode attribute seams on boundary edges. + const FaceIndex opp_face_id = corner_table_->Face(opp_corner); + // Don't encode edges when the opposite face has been already processed. + if (visited_faces_[opp_face_id.value()]) + continue; + + for (uint32_t i = 0; i < attribute_data_.size(); ++i) { + if (attribute_data_[i].connectivity_data.IsCornerOppositeToSeamEdge( + corners[c])) { + traversal_encoder_.EncodeAttributeSeam(i, true); + } else { + traversal_encoder_.EncodeAttributeSeam(i, false); + } + } + } + return true; +} + +template class MeshEdgebreakerEncoderImpl<MeshEdgebreakerTraversalEncoder>; +template class MeshEdgebreakerEncoderImpl< + MeshEdgebreakerTraversalPredictiveEncoder>; +template class MeshEdgebreakerEncoderImpl< + MeshEdgebreakerTraversalValenceEncoder>; + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder_impl.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder_impl.h new file mode 100644 index 00000000000..997bd1565e3 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder_impl.h @@ -0,0 +1,210 @@ +// 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_MESH_MESH_EDGEBREAKER_ENCODER_IMPL_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_ENCODER_IMPL_H_ + +#include <unordered_map> + +#include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h" +#include "draco/compression/config/compression_shared.h" +#include "draco/compression/mesh/mesh_edgebreaker_encoder_impl_interface.h" +#include "draco/compression/mesh/mesh_edgebreaker_shared.h" +#include "draco/compression/mesh/traverser/mesh_traversal_sequencer.h" +#include "draco/core/encoder_buffer.h" +#include "draco/mesh/mesh_attribute_corner_table.h" + +namespace draco { + +// Class implementing the edgebreaker encoding as described in "3D Compression +// Made Simple: Edgebreaker on a Corner-Table" by Rossignac at al.'01. +// http://www.cc.gatech.edu/~jarek/papers/CornerTableSMI.pdf +template <class TraversalEncoderT> +class MeshEdgebreakerEncoderImpl : public MeshEdgebreakerEncoderImplInterface { + public: + MeshEdgebreakerEncoderImpl(); + explicit MeshEdgebreakerEncoderImpl( + const TraversalEncoderT &traversal_encoder); + bool Init(MeshEdgebreakerEncoder *encoder) override; + + const MeshAttributeCornerTable *GetAttributeCornerTable( + int att_id) const override; + const MeshAttributeIndicesEncodingData *GetAttributeEncodingData( + int att_id) const override; + + bool GenerateAttributesEncoder(int32_t att_id) override; + bool EncodeAttributesEncoderIdentifier(int32_t att_encoder_id) override; + bool EncodeConnectivity() override; + + const CornerTable *GetCornerTable() const override { + return corner_table_.get(); + } + bool IsFaceEncoded(FaceIndex fi) const override { + return visited_faces_[fi.value()]; + } + MeshEdgebreakerEncoder *GetEncoder() const override { return encoder_; } + + private: + // Initializes data needed for encoding non-position attributes. + // Returns false on error. + bool InitAttributeData(); + + // Creates a vertex traversal sequencer for the specified |TraverserT| type. + template <class TraverserT> + std::unique_ptr<PointsSequencer> CreateVertexTraversalSequencer( + MeshAttributeIndicesEncodingData *encoding_data); + + // Finds the configuration of the initial face that starts the traversal. + // Configurations are determined by location of holes around the init face + // and they are described in mesh_edgebreaker_shared.h. + // Returns true if the face configuration is interior and false if it is + // exterior. + bool FindInitFaceConfiguration(FaceIndex face_id, + CornerIndex *out_corner_id) const; + + // Encodes the connectivity between vertices. + bool EncodeConnectivityFromCorner(CornerIndex corner_id); + + // Encodes all vertices of a hole starting at start_corner_id. + // The vertex associated with the first corner is encoded only if + // |encode_first_vertex| is true. + // Returns the number of encoded hole vertices. + int EncodeHole(CornerIndex start_corner_id, bool encode_first_vertex); + + // Encodes topology split data. + // Returns nullptr on error. + bool EncodeSplitData(); + + CornerIndex GetRightCorner(CornerIndex corner_id) const; + CornerIndex GetLeftCorner(CornerIndex corner_id) const; + + bool IsRightFaceVisited(CornerIndex corner_id) const; + bool IsLeftFaceVisited(CornerIndex corner_id) const; + bool IsVertexVisited(VertexIndex vert_id) const { + return visited_vertex_ids_[vert_id.value()]; + } + + // Finds and stores data about all holes in the input mesh. + bool FindHoles(); + + // For faces encoded with symbol TOPOLOGY_S (split), this method returns + // the encoded symbol id or -1 if the face wasn't encoded by a split symbol. + int GetSplitSymbolIdOnFace(int face_id) const; + + // Checks whether there is a topology split event on a neighboring face and + // stores the event data if necessary. For more info about topology split + // events, see description of TopologySplitEventData in + // mesh_edgebreaker_shared.h. + void CheckAndStoreTopologySplitEvent(int src_symbol_id, int src_face_id, + EdgeFaceName src_edge, + int neighbor_face_id); + + // Encodes connectivity of all attributes on a newly traversed face. + bool EncodeAttributeConnectivitiesOnFace(CornerIndex corner); + + // This function is used to to assign correct encoding order of attributes + // to unprocessed corners. The encoding order is equal to the order in which + // the attributes are going to be processed by the decoder and it is necessary + // for proper prediction of attribute values. + bool AssignPositionEncodingOrderToAllCorners(); + + // This function is used to generate encoding order for all non-position + // attributes. + // Returns false when one or more attributes failed to be processed. + bool GenerateEncodingOrderForAttributes(); + + // The main encoder that owns this class. + MeshEdgebreakerEncoder *encoder_; + // Mesh that's being encoded. + const Mesh *mesh_; + // Corner table stores the mesh face connectivity data. + std::unique_ptr<CornerTable> corner_table_; + // Stack used for storing corners that need to be traversed when encoding + // the connectivity. New corner is added for each initial face and a split + // symbol, and one corner is removed when the end symbol is reached. + // Stored as member variable to prevent frequent memory reallocations when + // handling meshes with lots of disjoint components. Originally, we used + // recursive functions to handle this behavior, but that can cause stack + // memory overflow when compressing huge meshes. + std::vector<CornerIndex> corner_traversal_stack_; + // Array for marking visited faces. + std::vector<bool> visited_faces_; + + // Attribute data for position encoding. + MeshAttributeIndicesEncodingData pos_encoding_data_; + + // Traversal method used for the position attribute. + MeshTraversalMethod pos_traversal_method_; + + // Array storing corners in the order they were visited during the + // connectivity encoding (always storing the tip corner of each newly visited + // face). + std::vector<CornerIndex> processed_connectivity_corners_; + + // Array for storing visited vertex ids of all input vertices. + std::vector<bool> visited_vertex_ids_; + + // For each traversal, this array stores the number of visited vertices. + std::vector<int> vertex_traversal_length_; + // Array for storing all topology split events encountered during the mesh + // traversal. + std::vector<TopologySplitEventData> topology_split_event_data_; + // Map between face_id and symbol_id. Contains entries only for faces that + // were encoded with TOPOLOGY_S symbol. + std::unordered_map<int, int> face_to_split_symbol_map_; + + // Array for marking holes that has been reached during the traversal. + std::vector<bool> visited_holes_; + // Array for mapping vertices to hole ids. If a vertex is not on a hole, the + // stored value is -1. + std::vector<int> vertex_hole_id_; + + // Id of the last encoded symbol. + int last_encoded_symbol_id_; + + // The number of encoded split symbols. + uint32_t num_split_symbols_; + + // Struct holding data used for encoding each non-position attribute. + // TODO(ostava): This should be probably renamed to something better. + struct AttributeData { + AttributeData() : attribute_index(-1), is_connectivity_used(true) {} + int attribute_index; + MeshAttributeCornerTable connectivity_data; + // Flag that can mark the connectivity_data invalid. In such case the base + // corner table of the mesh should be used instead. + bool is_connectivity_used; + // Data about attribute encoding order. + MeshAttributeIndicesEncodingData encoding_data; + // Traversal method used to generate the encoding data for this attribute. + MeshTraversalMethod traversal_method; + }; + std::vector<AttributeData> attribute_data_; + + // Array storing mapping between attribute encoder id and attribute data id. + std::vector<int32_t> attribute_encoder_to_data_id_map_; + + TraversalEncoderT traversal_encoder_; + + // If set, the encoder is going to use the same connectivity for all + // attributes. This effectively breaks the mesh along all attribute seams. + // In general, this approach should be much faster compared to encoding each + // connectivity separately, but the decoded model may contain higher number of + // duplicate attribute values which may decrease the compression ratio. + bool use_single_connectivity_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_ENCODER_IMPL_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder_impl_interface.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder_impl_interface.h new file mode 100644 index 00000000000..8da3541ec86 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoder_impl_interface.h @@ -0,0 +1,57 @@ +// 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_MESH_MESH_EDGEBREAKER_ENCODER_IMPL_INTERFACE_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_ENCODER_IMPL_INTERFACE_H_ + +#include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h" +#include "draco/mesh/corner_table.h" +#include "draco/mesh/mesh_attribute_corner_table.h" + +namespace draco { + +// Forward declaration is necessary here to avoid circular dependencies. +class MeshEdgebreakerEncoder; + +// Abstract interface used by MeshEdgebreakerEncoder to interact with the actual +// implementation of the edgebreaker method. The implementations are in general +// specializations of a template class MeshEdgebreakerEncoderImpl where the +// template arguments control encoding of the connectivity data. Because the +// choice of the implementation is done in run-time, we need to hide it behind +// the abstract interface MeshEdgebreakerEncoderImplInterface. +class MeshEdgebreakerEncoderImplInterface { + public: + virtual ~MeshEdgebreakerEncoderImplInterface() = default; + virtual bool Init(MeshEdgebreakerEncoder *encoder) = 0; + + virtual const MeshAttributeCornerTable *GetAttributeCornerTable( + int att_id) const = 0; + virtual const MeshAttributeIndicesEncodingData *GetAttributeEncodingData( + int att_id) const = 0; + virtual bool GenerateAttributesEncoder(int32_t att_id) = 0; + virtual bool EncodeAttributesEncoderIdentifier(int32_t att_encoder_id) = 0; + virtual bool EncodeConnectivity() = 0; + + // Returns corner table of the encoded mesh. + virtual const CornerTable *GetCornerTable() const = 0; + + // Returns true if a given face has been already encoded. + virtual bool IsFaceEncoded(FaceIndex fi) const = 0; + + virtual MeshEdgebreakerEncoder *GetEncoder() const = 0; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_ENCODER_IMPL_INTERFACE_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoding_test.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoding_test.cc new file mode 100644 index 00000000000..8313882455b --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_encoding_test.cc @@ -0,0 +1,247 @@ +// 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. +// +#include <sstream> + +#include "draco/compression/encode.h" +#include "draco/compression/mesh/mesh_edgebreaker_decoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_encoder.h" +#include "draco/core/draco_test_base.h" +#include "draco/core/draco_test_utils.h" +#include "draco/io/mesh_io.h" +#include "draco/io/obj_decoder.h" +#include "draco/mesh/mesh_are_equivalent.h" +#include "draco/mesh/mesh_cleanup.h" +#include "draco/mesh/triangle_soup_mesh_builder.h" + +namespace draco { + +class MeshEdgebreakerEncodingTest : public ::testing::Test { + protected: + void TestFile(const std::string &file_name) { TestFile(file_name, -1); } + + void TestFile(const std::string &file_name, int compression_level) { + const std::unique_ptr<Mesh> mesh(ReadMeshFromTestFile(file_name)); + ASSERT_NE(mesh, nullptr) << "Failed to load test model " << file_name; + + TestMesh(mesh.get(), compression_level); + } + + void TestMesh(Mesh *mesh, int compression_level) { + EncoderBuffer buffer; + MeshEdgebreakerEncoder encoder; + EncoderOptions encoder_options = EncoderOptions::CreateDefaultOptions(); + encoder_options.SetSpeed(10 - compression_level, 10 - compression_level); + encoder.SetMesh(*mesh); + ASSERT_TRUE(encoder.Encode(encoder_options, &buffer).ok()); + + DecoderBuffer dec_buffer; + dec_buffer.Init(buffer.data(), buffer.size()); + MeshEdgebreakerDecoder decoder; + + std::unique_ptr<Mesh> decoded_mesh(new Mesh()); + DecoderOptions dec_options; + ASSERT_TRUE( + decoder.Decode(dec_options, &dec_buffer, decoded_mesh.get()).ok()); + + // Cleanup the input mesh to make sure that input and output can be + // compared (edgebreaker method discards degenerated triangles and isolated + // vertices). + const MeshCleanupOptions options; + MeshCleanup cleanup; + ASSERT_TRUE(cleanup(mesh, options)) << "Failed to clean the input mesh."; + + MeshAreEquivalent eq; + ASSERT_TRUE(eq(*mesh, *decoded_mesh.get())) + << "Decoded mesh is not the same as the input"; + } +}; + +TEST_F(MeshEdgebreakerEncodingTest, TestNmOBJ) { + const std::string file_name = "test_nm.obj"; + TestFile(file_name); +} + +TEST_F(MeshEdgebreakerEncodingTest, ThreeFacesOBJ) { + const std::string file_name = "extra_vertex.obj"; + TestFile(file_name); +} + +TEST_F(MeshEdgebreakerEncodingTest, TestPly) { + // Tests whether the edgebreaker successfully encodes and decodes the test + // file (ply with color). + const std::string file_name = "test_pos_color.ply"; + TestFile(file_name); +} + +TEST_F(MeshEdgebreakerEncodingTest, TestMultiAttributes) { + // Tests encoding of model with many attributes. + const std::string file_name = "cube_att.obj"; + TestFile(file_name, 10); +} + +TEST_F(MeshEdgebreakerEncodingTest, TestEncoderReuse) { + // Tests whether the edgebreaker encoder can be reused multiple times to + // encode a given mesh. + const std::string file_name = "test_pos_color.ply"; + const std::unique_ptr<Mesh> mesh(ReadMeshFromTestFile(file_name)); + ASSERT_NE(mesh, nullptr) << "Failed to load test model " << file_name; + + MeshEdgebreakerEncoder encoder; + EncoderOptions encoder_options = EncoderOptions::CreateDefaultOptions(); + encoder.SetMesh(*mesh); + EncoderBuffer buffer_0, buffer_1; + ASSERT_TRUE(encoder.Encode(encoder_options, &buffer_0).ok()); + ASSERT_TRUE(encoder.Encode(encoder_options, &buffer_1).ok()); + + // Make sure both buffer are identical. + ASSERT_EQ(buffer_0.size(), buffer_1.size()); + for (int i = 0; i < buffer_0.size(); ++i) { + ASSERT_EQ(buffer_0.data()[i], buffer_1.data()[i]); + } +} + +TEST_F(MeshEdgebreakerEncodingTest, TestDecoderReuse) { + // Tests whether the edgebreaker decoder can be reused multiple times to + // decode a given mesh. + const std::string file_name = "test_pos_color.ply"; + const std::unique_ptr<Mesh> mesh(ReadMeshFromTestFile(file_name)); + ASSERT_NE(mesh, nullptr) << "Failed to load test model " << file_name; + + MeshEdgebreakerEncoder encoder; + EncoderOptions encoder_options = EncoderOptions::CreateDefaultOptions(); + encoder.SetMesh(*mesh); + EncoderBuffer buffer; + ASSERT_TRUE(encoder.Encode(encoder_options, &buffer).ok()); + + DecoderBuffer dec_buffer; + dec_buffer.Init(buffer.data(), buffer.size()); + + MeshEdgebreakerDecoder decoder; + + // Decode the mesh two times. + std::unique_ptr<Mesh> decoded_mesh_0(new Mesh()); + DecoderOptions dec_options; + ASSERT_TRUE( + decoder.Decode(dec_options, &dec_buffer, decoded_mesh_0.get()).ok()); + + dec_buffer.Init(buffer.data(), buffer.size()); + std::unique_ptr<Mesh> decoded_mesh_1(new Mesh()); + ASSERT_TRUE( + decoder.Decode(dec_options, &dec_buffer, decoded_mesh_1.get()).ok()); + + // Make sure both of the meshes are identical. + MeshAreEquivalent eq; + ASSERT_TRUE(eq(*decoded_mesh_0.get(), *decoded_mesh_1.get())) + << "Decoded meshes are not the same"; +} + +TEST_F(MeshEdgebreakerEncodingTest, TestSingleConnectivityEncoding) { + // Tests whether the edgebreaker method successfully encodes a mesh with + // multiple attributes using single connectivity by breaking the mesh along + // attribute seams. + const std::string file_name = "cube_att.obj"; + const std::unique_ptr<Mesh> mesh(ReadMeshFromTestFile(file_name)); + ASSERT_NE(mesh, nullptr) << "Failed to load test model " << file_name; + + for (int i = 0; i < 2; ++i) { + // Set the option to enable/disable single connectivity encoding. + EncoderOptionsBase<GeometryAttribute::Type> options = + EncoderOptionsBase<GeometryAttribute::Type>::CreateDefaultOptions(); + options.SetGlobalBool("split_mesh_on_seams", i == 0 ? true : false); + + EncoderBuffer buffer; + draco::Encoder encoder; + encoder.Reset(options); + encoder.SetSpeedOptions(0, 0); + encoder.SetAttributeQuantization(GeometryAttribute::POSITION, 8); + encoder.SetAttributeQuantization(GeometryAttribute::TEX_COORD, 8); + encoder.SetAttributeQuantization(GeometryAttribute::NORMAL, 8); + encoder.SetEncodingMethod(MESH_EDGEBREAKER_ENCODING); + ASSERT_TRUE(encoder.EncodeMeshToBuffer(*mesh, &buffer).ok()); + + DecoderBuffer dec_buffer; + dec_buffer.Init(buffer.data(), buffer.size()); + + Decoder decoder; + auto dec_mesh = decoder.DecodeMeshFromBuffer(&dec_buffer).value(); + ASSERT_NE(dec_mesh, nullptr); + ASSERT_EQ(dec_mesh->num_points(), 24); + ASSERT_EQ(dec_mesh->num_attributes(), 3); + ASSERT_EQ(dec_mesh->attribute(0)->size(), i == 0 ? 24 : 8); + ASSERT_EQ(dec_mesh->attribute(1)->size(), 24); + ASSERT_EQ(dec_mesh->attribute(2)->size(), 24); + } +} + +TEST_F(MeshEdgebreakerEncodingTest, TestWrongAttributeOrder) { + // Tests whether the edgebreaker method successfully encodes a mesh where the + // input attributes are in wrong order (because of their internal + // dependencies). In such case the attributes should be rearranged to the + // correct order. + TriangleSoupMeshBuilder mb; + mb.Start(1); + const int32_t norm_att_id = + mb.AddAttribute(GeometryAttribute::NORMAL, 3, DT_FLOAT32); + const int32_t pos_att_id = + mb.AddAttribute(GeometryAttribute::POSITION, 3, DT_FLOAT32); + + mb.SetAttributeValuesForFace( + pos_att_id, FaceIndex(0), Vector3f(0.f, 0.f, 0.f).data(), + Vector3f(1.f, 0.f, 0.f).data(), Vector3f(0.f, 1.f, 0.f).data()); + + mb.SetAttributeValuesForFace( + norm_att_id, FaceIndex(0), Vector3f(0.f, 0.f, 1.f).data(), + Vector3f(0.f, 0.f, 0.f).data(), Vector3f(0.f, 0.f, 1.f).data()); + std::unique_ptr<Mesh> mesh = mb.Finalize(); + ASSERT_NE(mesh, nullptr); + ASSERT_EQ(mesh->num_attributes(), 2); + ASSERT_EQ(mesh->attribute(0)->attribute_type(), GeometryAttribute::NORMAL); + ASSERT_EQ(mesh->attribute(1)->attribute_type(), GeometryAttribute::POSITION); + + EncoderBuffer buffer; + draco::Encoder encoder; + encoder.SetSpeedOptions(3, 3); + encoder.SetAttributeQuantization(GeometryAttribute::POSITION, 8); + encoder.SetAttributeQuantization(GeometryAttribute::NORMAL, 8); + encoder.SetEncodingMethod(MESH_EDGEBREAKER_ENCODING); + ASSERT_TRUE(encoder.EncodeMeshToBuffer(*mesh, &buffer).ok()); + + DecoderBuffer dec_buffer; + dec_buffer.Init(buffer.data(), buffer.size()); + + Decoder decoder; + auto dec_mesh = decoder.DecodeMeshFromBuffer(&dec_buffer).value(); + ASSERT_NE(dec_mesh, nullptr); + ASSERT_EQ(dec_mesh->num_attributes(), 2); + ASSERT_EQ(dec_mesh->attribute(0)->attribute_type(), + GeometryAttribute::POSITION); + ASSERT_EQ(dec_mesh->attribute(1)->attribute_type(), + GeometryAttribute::NORMAL); +} + +TEST_F(MeshEdgebreakerEncodingTest, TestDegenerateMesh) { + // Tests whether we can process a mesh that contains degenerate faces only. + const std::string file_name = "degenerate_mesh.obj"; + const std::unique_ptr<Mesh> mesh(ReadMeshFromTestFile(file_name)); + ASSERT_NE(mesh, nullptr) << "Failed to load test model " << file_name; + EncoderBuffer buffer; + MeshEdgebreakerEncoder encoder; + EncoderOptions encoder_options = EncoderOptions::CreateDefaultOptions(); + encoder.SetMesh(*mesh); + // We expect the encoding to fail as edgebreaker can only process valid faces. + ASSERT_FALSE(encoder.Encode(encoder_options, &buffer).ok()); +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_shared.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_shared.h new file mode 100644 index 00000000000..cb3c29dd669 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_shared.h @@ -0,0 +1,131 @@ +// 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_MESH_MESH_EDGEBREAKER_SHARED_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_SHARED_H_ + +#include <stdint.h> + +namespace draco { + +// Shared declarations used by both edgebreaker encoder and decoder. + +// A variable length encoding for storing all possible topology configurations +// during traversal of mesh's surface. The configurations are based on visited +// state of neighboring triangles around a currently processed face corner. +// Note that about half of the encountered configurations is expected to be of +// type TOPOLOGY_C. It's guaranteed that the encoding will use at most 2 bits +// per triangle for meshes with no holes and up to 6 bits per triangle for +// general meshes. In addition, the encoding will take up to 4 bits per triangle +// for each non-position attribute attached to the mesh. +// +// *-------* *-------* *-------* +// / \ / \ / \ / \ / \ / \ +// / \ / \ / \ / \ / \ / \ +// / \ / \ / \ / \ / \ / \ +// *-------v-------* *-------v-------* *-------v-------* +// \ /x\ / /x\ / \ /x\ +// \ / \ / / \ / \ / \ +// \ / C \ / / L \ / \ / R \ +// *-------* *-------* *-------* +// +// * * +// / \ / \ +// / \ / \ +// / \ / \ +// *-------v-------* v +// \ /x\ / /x\ +// \ / \ / / \ +// \ / S \ / / E \ +// *-------* *-------* +// +// TODO(ostava): Get rid of the topology bit pattern. It's important only for +// encoding but the algorithms should use EdgebreakerSymbol instead. +enum EdgebreakerTopologyBitPattern { + TOPOLOGY_C = 0x0, // 0 + TOPOLOGY_S = 0x1, // 1 0 0 + TOPOLOGY_L = 0x3, // 1 1 0 + TOPOLOGY_R = 0x5, // 1 0 1 + TOPOLOGY_E = 0x7, // 1 1 1 + // A special symbol that's not actually encoded, but it can be used to mark + // the initial face that triggers the mesh encoding of a single connected + // component. + TOPOLOGY_INIT_FACE, + // A special value used to indicate an invalid symbol. + TOPOLOGY_INVALID +}; + +enum EdgebreakerSymbol { + EDGEBREAKER_SYMBOL_C = 0, + EDGEBREAKER_SYMBOL_S, + EDGEBREAKER_SYMBOL_L, + EDGEBREAKER_SYMBOL_R, + EDGEBREAKER_SYMBOL_E, + EDGEBREAKER_SYMBOL_INVALID +}; + +// Bit-length of symbols in the EdgebreakerTopologyBitPattern stored as a +// lookup table for faster indexing. +constexpr int32_t edge_breaker_topology_bit_pattern_length[] = {1, 3, 0, 3, + 0, 3, 0, 3}; + +// Zero-indexed symbol id for each of topology pattern. +constexpr EdgebreakerSymbol edge_breaker_topology_to_symbol_id[] = { + EDGEBREAKER_SYMBOL_C, EDGEBREAKER_SYMBOL_S, + EDGEBREAKER_SYMBOL_INVALID, EDGEBREAKER_SYMBOL_L, + EDGEBREAKER_SYMBOL_INVALID, EDGEBREAKER_SYMBOL_R, + EDGEBREAKER_SYMBOL_INVALID, EDGEBREAKER_SYMBOL_E}; + +// Reverse mapping between symbol id and topology pattern symbol. +constexpr EdgebreakerTopologyBitPattern edge_breaker_symbol_to_topology_id[] = { + TOPOLOGY_C, TOPOLOGY_S, TOPOLOGY_L, TOPOLOGY_R, TOPOLOGY_E}; + +// Types of edges used during mesh traversal relative to the tip vertex of a +// visited triangle. +enum EdgeFaceName : uint8_t { LEFT_FACE_EDGE = 0, RIGHT_FACE_EDGE = 1 }; + +// Struct used for storing data about a source face that connects to an +// already traversed face that was either the initial face or a face encoded +// with either topology S (split) symbol. Such connection can be only caused by +// topology changes on the traversed surface (if its genus != 0, i.e. when the +// surface has topological handles or holes). +// For each occurrence of such event we always encode the split symbol id, +// source symbol id and source edge id (left, or right). There will be always +// exactly two occurrences of this event for every topological handle on the +// traversed mesh and one occurrence for a hole. +struct TopologySplitEventData { + uint32_t split_symbol_id; + uint32_t source_symbol_id; + // We need to use uint32_t instead of EdgeFaceName because the most recent + // version of gcc does not allow that when optimizations are turned on. + uint32_t source_edge : 1; +}; + +// Hole event is used to store info about the first symbol that reached a +// vertex of so far unvisited hole. This can happen only on either the initial +// face or during a regular traversal when TOPOLOGY_S is encountered. +struct HoleEventData { + int32_t symbol_id; + HoleEventData() : symbol_id(0) {} + explicit HoleEventData(int32_t sym_id) : symbol_id(sym_id) {} +}; + +// List of supported modes for valence based edgebreaker coding. +enum EdgebreakerValenceCodingMode { + EDGEBREAKER_VALENCE_MODE_2_7 = 0, // Use contexts for valences in range 2-7. +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_SHARED_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_decoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_decoder.h new file mode 100644 index 00000000000..128d7f5d988 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_decoder.h @@ -0,0 +1,193 @@ +// 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_MESH_MESH_EDGEBREAKER_TRAVERSAL_DECODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_DECODER_H_ + +#include "draco/draco_features.h" + +#include "draco/compression/bit_coders/rans_bit_decoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_decoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_decoder_impl_interface.h" +#include "draco/compression/mesh/mesh_edgebreaker_shared.h" + +namespace draco { + +typedef RAnsBitDecoder BinaryDecoder; + +// Default implementation of the edgebreaker traversal decoder that reads the +// traversal data directly from a buffer. +class MeshEdgebreakerTraversalDecoder { + public: + MeshEdgebreakerTraversalDecoder() + : attribute_connectivity_decoders_(nullptr), + num_attribute_data_(0), + decoder_impl_(nullptr) {} + void Init(MeshEdgebreakerDecoderImplInterface *decoder) { + decoder_impl_ = decoder; + buffer_.Init(decoder->GetDecoder()->buffer()->data_head(), + decoder->GetDecoder()->buffer()->remaining_size(), + decoder->GetDecoder()->buffer()->bitstream_version()); + } + + // Returns the Draco bitstream version. + uint16_t BitstreamVersion() const { + return decoder_impl_->GetDecoder()->bitstream_version(); + } + + // Used to tell the decoder what is the number of expected decoded vertices. + // Ignored by default. + void SetNumEncodedVertices(int /* num_vertices */) {} + + // Set the number of non-position attribute data for which we need to decode + // the connectivity. + void SetNumAttributeData(int num_data) { num_attribute_data_ = num_data; } + + // Called before the traversal decoding is started. + // Returns a buffer decoder that points to data that was encoded after the + // traversal. + bool Start(DecoderBuffer *out_buffer) { + // Decode symbols from the main buffer decoder and face configurations from + // the start_face_buffer decoder. + if (!DecodeTraversalSymbols()) + return false; + + if (!DecodeStartFaces()) + return false; + + if (!DecodeAttributeSeams()) + return false; + *out_buffer = buffer_; + return true; + } + + // Returns the configuration of a new initial face. + inline bool DecodeStartFaceConfiguration() { + uint32_t face_configuration; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (buffer_.bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) { + start_face_buffer_.DecodeLeastSignificantBits32(1, &face_configuration); + + } else +#endif + { + face_configuration = start_face_decoder_.DecodeNextBit(); + } + return face_configuration; + } + + // Returns the next edgebreaker symbol that was reached during the traversal. + inline uint32_t DecodeSymbol() { + uint32_t symbol; + symbol_buffer_.DecodeLeastSignificantBits32(1, &symbol); + if (symbol == TOPOLOGY_C) { + return symbol; + } + // Else decode two additional bits. + uint32_t symbol_suffix; + symbol_buffer_.DecodeLeastSignificantBits32(2, &symbol_suffix); + symbol |= (symbol_suffix << 1); + return symbol; + } + + // Called whenever a new active corner is set in the decoder. + inline void NewActiveCornerReached(CornerIndex /* corner */) {} + + // Called whenever |source| vertex is about to be merged into the |dest| + // vertex. + inline void MergeVertices(VertexIndex /* dest */, VertexIndex /* source */) {} + + // Returns true if there is an attribute seam for the next processed pair + // of visited faces. + // |attribute| is used to mark the id of the non-position attribute (in range + // of <0, num_attributes - 1>). + inline bool DecodeAttributeSeam(int attribute) { + return attribute_connectivity_decoders_[attribute].DecodeNextBit(); + } + + // Called when the traversal is finished. + void Done() { + if (symbol_buffer_.bit_decoder_active()) + symbol_buffer_.EndBitDecoding(); +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (buffer_.bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) { + start_face_buffer_.EndBitDecoding(); + + } else +#endif + { + start_face_decoder_.EndDecoding(); + } + } + + protected: + DecoderBuffer *buffer() { return &buffer_; } + + bool DecodeTraversalSymbols() { + uint64_t traversal_size; + symbol_buffer_ = buffer_; + if (!symbol_buffer_.StartBitDecoding(true, &traversal_size)) + return false; + buffer_ = symbol_buffer_; + if (traversal_size > static_cast<uint64_t>(buffer_.remaining_size())) + return false; + buffer_.Advance(traversal_size); + return true; + } + + bool DecodeStartFaces() { + // Create a decoder that is set to the end of the encoded traversal data. +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (buffer_.bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) { + start_face_buffer_ = buffer_; + uint64_t traversal_size; + if (!start_face_buffer_.StartBitDecoding(true, &traversal_size)) + return false; + buffer_ = start_face_buffer_; + if (traversal_size > static_cast<uint64_t>(buffer_.remaining_size())) + return false; + buffer_.Advance(traversal_size); + return true; + } +#endif + return start_face_decoder_.StartDecoding(&buffer_); + } + + bool DecodeAttributeSeams() { + // Prepare attribute decoding. + if (num_attribute_data_ > 0) { + attribute_connectivity_decoders_ = std::unique_ptr<BinaryDecoder[]>( + new BinaryDecoder[num_attribute_data_]); + for (int i = 0; i < num_attribute_data_; ++i) { + if (!attribute_connectivity_decoders_[i].StartDecoding(&buffer_)) + return false; + } + } + return true; + } + + private: + // Buffer that contains the encoded data. + DecoderBuffer buffer_; + DecoderBuffer symbol_buffer_; + BinaryDecoder start_face_decoder_; + DecoderBuffer start_face_buffer_; + std::unique_ptr<BinaryDecoder[]> attribute_connectivity_decoders_; + int num_attribute_data_; + const MeshEdgebreakerDecoderImplInterface *decoder_impl_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_DECODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_encoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_encoder.h new file mode 100644 index 00000000000..08cb66e4cdc --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_encoder.h @@ -0,0 +1,139 @@ +// 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_MESH_MESH_EDGEBREAKER_TRAVERSAL_ENCODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_ENCODER_H_ + +#include "draco/compression/bit_coders/rans_bit_encoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_encoder.h" +#include "draco/compression/mesh/mesh_edgebreaker_encoder_impl_interface.h" +#include "draco/core/macros.h" + +namespace draco { + +typedef RAnsBitEncoder BinaryEncoder; + +// Default implementation of the edgebreaker traversal encoder. Face +// configurations are stored directly into the output buffer and the symbols +// are first collected and then encoded in the reverse order to make the +// decoding faster. +class MeshEdgebreakerTraversalEncoder { + public: + MeshEdgebreakerTraversalEncoder() + : encoder_impl_(nullptr), + attribute_connectivity_encoders_(nullptr), + num_attribute_data_(0) {} + bool Init(MeshEdgebreakerEncoderImplInterface *encoder) { + encoder_impl_ = encoder; + return true; + } + + // Set the number of non-position attribute data for which we need to encode + // the connectivity. + void SetNumAttributeData(int num_data) { num_attribute_data_ = num_data; } + + // Called before the traversal encoding is started. + void Start() { + start_face_encoder_.StartEncoding(); + if (num_attribute_data_ > 0) { + // Init and start arithmetic encoders for storing configuration types + // of non-position attributes. + attribute_connectivity_encoders_ = std::unique_ptr<BinaryEncoder[]>( + new BinaryEncoder[num_attribute_data_]); + for (int i = 0; i < num_attribute_data_; ++i) { + attribute_connectivity_encoders_[i].StartEncoding(); + } + } + } + + // Called when a traversal starts from a new initial face. + inline void EncodeStartFaceConfiguration(bool interior) { + start_face_encoder_.EncodeBit(interior); + } + + // Called when a new corner is reached during the traversal. No-op for the + // default encoder. + inline void NewCornerReached(CornerIndex /* corner */) {} + + // Called whenever a new symbol is reached during the edgebreaker traversal. + inline void EncodeSymbol(EdgebreakerTopologyBitPattern symbol) { + // Store the symbol. It will be encoded after all symbols are processed. + symbols_.push_back(symbol); + } + + // Called for every pair of connected and visited faces. |is_seam| specifies + // whether there is an attribute seam between the two faces. + + inline void EncodeAttributeSeam(int attribute, bool is_seam) { + attribute_connectivity_encoders_[attribute].EncodeBit(is_seam ? 1 : 0); + } + + // Called when the traversal is finished. + void Done() { + EncodeTraversalSymbols(); + EncodeStartFaces(); + EncodeAttributeSeams(); + } + + // Returns the number of encoded symbols. + int NumEncodedSymbols() const { return static_cast<int>(symbols_.size()); } + + const EncoderBuffer &buffer() const { return traversal_buffer_; } + + protected: + void EncodeTraversalSymbols() { + // Bit encode the collected symbols. + // Allocate enough storage for the bit encoder. + // It's guaranteed that each face will need only up to 3 bits. + traversal_buffer_.StartBitEncoding( + encoder_impl_->GetEncoder()->mesh()->num_faces() * 3, true); + for (int i = static_cast<int>(symbols_.size() - 1); i >= 0; --i) { + traversal_buffer_.EncodeLeastSignificantBits32( + edge_breaker_topology_bit_pattern_length[symbols_[i]], symbols_[i]); + } + traversal_buffer_.EndBitEncoding(); + } + + void EncodeStartFaces() { + start_face_encoder_.EndEncoding(&traversal_buffer_); + } + + void EncodeAttributeSeams() { + if (attribute_connectivity_encoders_ != nullptr) { + for (int i = 0; i < num_attribute_data_; ++i) { + attribute_connectivity_encoders_[i].EndEncoding(&traversal_buffer_); + } + } + } + + EncoderBuffer *GetOutputBuffer() { return &traversal_buffer_; } + const MeshEdgebreakerEncoderImplInterface *encoder_impl() const { + return encoder_impl_; + } + + private: + BinaryEncoder start_face_encoder_; + EncoderBuffer traversal_buffer_; + const MeshEdgebreakerEncoderImplInterface *encoder_impl_; + // Symbols collected during the traversal. + std::vector<EdgebreakerTopologyBitPattern> symbols_; + // Arithmetic encoder for encoding attribute seams. + // One context for each non-position attribute. + std::unique_ptr<BinaryEncoder[]> attribute_connectivity_encoders_; + int num_attribute_data_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_ENCODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_predictive_decoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_predictive_decoder.h new file mode 100644 index 00000000000..d3289e28c76 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_predictive_decoder.h @@ -0,0 +1,132 @@ +// 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. +// +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED +#ifndef DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_PREDICTIVE_DECODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_PREDICTIVE_DECODER_H_ + +#include "draco/draco_features.h" + +#include "draco/compression/mesh/mesh_edgebreaker_traversal_decoder.h" + +namespace draco { + +// Decoder for traversal encoded with the +// MeshEdgebreakerTraversalPredictiveEncoder. The decoder maintains valences +// of the decoded portion of the traversed mesh and it uses them to predict +// symbols that are about to be decoded. +class MeshEdgebreakerTraversalPredictiveDecoder + : public MeshEdgebreakerTraversalDecoder { + public: + MeshEdgebreakerTraversalPredictiveDecoder() + : corner_table_(nullptr), + num_vertices_(0), + last_symbol_(-1), + predicted_symbol_(-1) {} + void Init(MeshEdgebreakerDecoderImplInterface *decoder) { + MeshEdgebreakerTraversalDecoder::Init(decoder); + corner_table_ = decoder->GetCornerTable(); + } + void SetNumEncodedVertices(int num_vertices) { num_vertices_ = num_vertices; } + + bool Start(DecoderBuffer *out_buffer) { + if (!MeshEdgebreakerTraversalDecoder::Start(out_buffer)) + return false; + int32_t num_split_symbols; + if (!out_buffer->Decode(&num_split_symbols) || num_split_symbols < 0) + return false; + if (num_split_symbols >= num_vertices_) + return false; + // Set the valences of all initial vertices to 0. + vertex_valences_.resize(num_vertices_, 0); + if (!prediction_decoder_.StartDecoding(out_buffer)) + return false; + return true; + } + + inline uint32_t DecodeSymbol() { + // First check if we have a predicted symbol. + if (predicted_symbol_ != -1) { + // Double check that the predicted symbol was predicted correctly. + if (prediction_decoder_.DecodeNextBit()) { + last_symbol_ = predicted_symbol_; + return predicted_symbol_; + } + } + // We don't have a predicted symbol or the symbol was mis-predicted. + // Decode it directly. + last_symbol_ = MeshEdgebreakerTraversalDecoder::DecodeSymbol(); + return last_symbol_; + } + + inline void NewActiveCornerReached(CornerIndex corner) { + const CornerIndex next = corner_table_->Next(corner); + const CornerIndex prev = corner_table_->Previous(corner); + // Update valences. + switch (last_symbol_) { + case TOPOLOGY_C: + case TOPOLOGY_S: + vertex_valences_[corner_table_->Vertex(next).value()] += 1; + vertex_valences_[corner_table_->Vertex(prev).value()] += 1; + break; + case TOPOLOGY_R: + vertex_valences_[corner_table_->Vertex(corner).value()] += 1; + vertex_valences_[corner_table_->Vertex(next).value()] += 1; + vertex_valences_[corner_table_->Vertex(prev).value()] += 2; + break; + case TOPOLOGY_L: + vertex_valences_[corner_table_->Vertex(corner).value()] += 1; + vertex_valences_[corner_table_->Vertex(next).value()] += 2; + vertex_valences_[corner_table_->Vertex(prev).value()] += 1; + break; + case TOPOLOGY_E: + vertex_valences_[corner_table_->Vertex(corner).value()] += 2; + vertex_valences_[corner_table_->Vertex(next).value()] += 2; + vertex_valences_[corner_table_->Vertex(prev).value()] += 2; + break; + default: + break; + } + // Compute the new predicted symbol. + if (last_symbol_ == TOPOLOGY_C || last_symbol_ == TOPOLOGY_R) { + const VertexIndex pivot = + corner_table_->Vertex(corner_table_->Next(corner)); + if (vertex_valences_[pivot.value()] < 6) { + predicted_symbol_ = TOPOLOGY_R; + } else { + predicted_symbol_ = TOPOLOGY_C; + } + } else { + predicted_symbol_ = -1; + } + } + + inline void MergeVertices(VertexIndex dest, VertexIndex source) { + // Update valences on the merged vertices. + vertex_valences_[dest.value()] += vertex_valences_[source.value()]; + } + + private: + const CornerTable *corner_table_; + int num_vertices_; + std::vector<int> vertex_valences_; + BinaryDecoder prediction_decoder_; + int last_symbol_; + int predicted_symbol_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_PREDICTIVE_DECODER_H_ +#endif diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_predictive_encoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_predictive_encoder.h new file mode 100644 index 00000000000..118687cc769 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_predictive_encoder.h @@ -0,0 +1,171 @@ +// 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_MESH_MESH_EDGEBREAKER_TRAVERSAL_PREDICTIVE_ENCODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_PREDICTIVE_ENCODER_H_ + +#include "draco/compression/mesh/mesh_edgebreaker_traversal_encoder.h" + +namespace draco { + +// Encoder that tries to predict the edgebreaker traversal symbols based on the +// vertex valences of the unencoded portion of the mesh. The current prediction +// scheme assumes that each vertex has valence 6 which can be used to predict +// the symbol preceding the one that is currently encoded. Predictions are +// encoded using an arithmetic coding which can lead to less than 1 bit per +// triangle encoding for highly regular meshes. +class MeshEdgebreakerTraversalPredictiveEncoder + : public MeshEdgebreakerTraversalEncoder { + public: + MeshEdgebreakerTraversalPredictiveEncoder() + : corner_table_(nullptr), + prev_symbol_(-1), + num_split_symbols_(0), + last_corner_(kInvalidCornerIndex), + num_symbols_(0) {} + + bool Init(MeshEdgebreakerEncoderImplInterface *encoder) { + if (!MeshEdgebreakerTraversalEncoder::Init(encoder)) + return false; + corner_table_ = encoder->GetCornerTable(); + // Initialize valences of all vertices. + vertex_valences_.resize(corner_table_->num_vertices()); + for (uint32_t i = 0; i < vertex_valences_.size(); ++i) { + vertex_valences_[i] = corner_table_->Valence(VertexIndex(i)); + } + return true; + } + + inline void NewCornerReached(CornerIndex corner) { last_corner_ = corner; } + + inline int32_t ComputePredictedSymbol(VertexIndex pivot) { + const int valence = vertex_valences_[pivot.value()]; + if (valence < 0) { + // This situation can happen only for split vertices. Returning + // TOPOLOGY_INVALID always cases misprediction. + return TOPOLOGY_INVALID; + } + if (valence < 6) { + return TOPOLOGY_R; + } + return TOPOLOGY_C; + } + + inline void EncodeSymbol(EdgebreakerTopologyBitPattern symbol) { + ++num_symbols_; + // Update valences on the mesh. And compute the predicted preceding symbol. + // Note that the valences are computed for the so far unencoded part of the + // mesh. Adding a new symbol either reduces valences on the vertices or + // leaves the valence unchanged. + int32_t predicted_symbol = -1; + const CornerIndex next = corner_table_->Next(last_corner_); + const CornerIndex prev = corner_table_->Previous(last_corner_); + switch (symbol) { + case TOPOLOGY_C: + // Compute prediction. + predicted_symbol = ComputePredictedSymbol(corner_table_->Vertex(next)); + FALLTHROUGH_INTENDED; + case TOPOLOGY_S: + // Update valences. + vertex_valences_[corner_table_->Vertex(next).value()] -= 1; + vertex_valences_[corner_table_->Vertex(prev).value()] -= 1; + if (symbol == TOPOLOGY_S) { + // Whenever we reach a split symbol, mark its tip vertex as invalid by + // setting the valence to a negative value. Any prediction that will + // use this vertex will then cause a misprediction. This is currently + // necessary because the decoding works in the reverse direction and + // the decoder doesn't know about these vertices until the split + // symbol is decoded at which point two vertices are merged into one. + // This can be most likely solved on the encoder side by splitting the + // tip vertex into two, but since split symbols are relatively rare, + // it's probably not worth doing it. + vertex_valences_[corner_table_->Vertex(last_corner_).value()] = -1; + ++num_split_symbols_; + } + break; + case TOPOLOGY_R: + // Compute prediction. + predicted_symbol = ComputePredictedSymbol(corner_table_->Vertex(next)); + // Update valences. + vertex_valences_[corner_table_->Vertex(last_corner_).value()] -= 1; + vertex_valences_[corner_table_->Vertex(next).value()] -= 1; + vertex_valences_[corner_table_->Vertex(prev).value()] -= 2; + break; + case TOPOLOGY_L: + vertex_valences_[corner_table_->Vertex(last_corner_).value()] -= 1; + vertex_valences_[corner_table_->Vertex(next).value()] -= 2; + vertex_valences_[corner_table_->Vertex(prev).value()] -= 1; + break; + case TOPOLOGY_E: + vertex_valences_[corner_table_->Vertex(last_corner_).value()] -= 2; + vertex_valences_[corner_table_->Vertex(next).value()] -= 2; + vertex_valences_[corner_table_->Vertex(prev).value()] -= 2; + break; + default: + break; + } + // Flag used when it's necessary to explicitly store the previous symbol. + bool store_prev_symbol = true; + if (predicted_symbol != -1) { + if (predicted_symbol == prev_symbol_) { + predictions_.push_back(true); + store_prev_symbol = false; + } else if (prev_symbol_ != -1) { + predictions_.push_back(false); + } + } + if (store_prev_symbol && prev_symbol_ != -1) { + MeshEdgebreakerTraversalEncoder::EncodeSymbol( + static_cast<EdgebreakerTopologyBitPattern>(prev_symbol_)); + } + prev_symbol_ = symbol; + } + + void Done() { + // We still need to store the last encoded symbol. + if (prev_symbol_ != -1) { + MeshEdgebreakerTraversalEncoder::EncodeSymbol( + static_cast<EdgebreakerTopologyBitPattern>(prev_symbol_)); + } + // Store the init face configurations and the explicitly encoded symbols. + MeshEdgebreakerTraversalEncoder::Done(); + // Encode the number of split symbols. + GetOutputBuffer()->Encode(num_split_symbols_); + // Store the predictions. + BinaryEncoder prediction_encoder; + prediction_encoder.StartEncoding(); + for (int i = static_cast<int>(predictions_.size()) - 1; i >= 0; --i) { + prediction_encoder.EncodeBit(predictions_[i]); + } + prediction_encoder.EndEncoding(GetOutputBuffer()); + } + + int NumEncodedSymbols() const { return num_symbols_; } + + private: + const CornerTable *corner_table_; + std::vector<int> vertex_valences_; + std::vector<bool> predictions_; + // Previously encoded symbol. + int32_t prev_symbol_; + // The total number of encoded split symbols. + int32_t num_split_symbols_; + CornerIndex last_corner_; + // Explicitly count the number of encoded symbols. + int num_symbols_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_PREDICTIVE_ENCODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_valence_decoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_valence_decoder.h new file mode 100644 index 00000000000..4da9d0e3a8b --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_valence_decoder.h @@ -0,0 +1,202 @@ +// 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_MESH_MESH_EDGEBREAKER_TRAVERSAL_VALENCE_DECODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_VALENCE_DECODER_H_ + +#include "draco/draco_features.h" + +#include "draco/compression/entropy/symbol_decoding.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_decoder.h" +#include "draco/core/varint_decoding.h" + +namespace draco { + +// Decoder for traversal encoded with MeshEdgebreakerTraversalValenceEncoder. +// The decoder maintains valences of the decoded portion of the traversed mesh +// and it uses them to select entropy context used for decoding of the actual +// symbols. +class MeshEdgebreakerTraversalValenceDecoder + : public MeshEdgebreakerTraversalDecoder { + public: + MeshEdgebreakerTraversalValenceDecoder() + : corner_table_(nullptr), + num_vertices_(0), + last_symbol_(-1), + active_context_(-1), + min_valence_(2), + max_valence_(7) {} + void Init(MeshEdgebreakerDecoderImplInterface *decoder) { + MeshEdgebreakerTraversalDecoder::Init(decoder); + corner_table_ = decoder->GetCornerTable(); + } + void SetNumEncodedVertices(int num_vertices) { num_vertices_ = num_vertices; } + + bool Start(DecoderBuffer *out_buffer) { +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (BitstreamVersion() < DRACO_BITSTREAM_VERSION(2, 2)) { + if (!MeshEdgebreakerTraversalDecoder::DecodeTraversalSymbols()) + return false; + } +#endif + if (!MeshEdgebreakerTraversalDecoder::DecodeStartFaces()) + return false; + if (!MeshEdgebreakerTraversalDecoder::DecodeAttributeSeams()) + return false; + *out_buffer = *buffer(); + +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (BitstreamVersion() < DRACO_BITSTREAM_VERSION(2, 2)) { + uint32_t num_split_symbols; + if (BitstreamVersion() < DRACO_BITSTREAM_VERSION(2, 0)) { + if (!out_buffer->Decode(&num_split_symbols)) + return false; + } else { + if (!DecodeVarint(&num_split_symbols, out_buffer)) + return false; + } + if (num_split_symbols >= static_cast<uint32_t>(num_vertices_)) + return false; + + int8_t mode; + if (!out_buffer->Decode(&mode)) + return false; + if (mode == EDGEBREAKER_VALENCE_MODE_2_7) { + min_valence_ = 2; + max_valence_ = 7; + } else { + // Unsupported mode. + return false; + } + + } else +#endif + { + min_valence_ = 2; + max_valence_ = 7; + } + + if (num_vertices_ < 0) + return false; + // Set the valences of all initial vertices to 0. + vertex_valences_.resize(num_vertices_, 0); + + const int num_unique_valences = max_valence_ - min_valence_ + 1; + + // Decode all symbols for all contexts. + context_symbols_.resize(num_unique_valences); + context_counters_.resize(context_symbols_.size()); + for (int i = 0; i < context_symbols_.size(); ++i) { + uint32_t num_symbols; + DecodeVarint<uint32_t>(&num_symbols, out_buffer); + if (num_symbols > 0) { + context_symbols_[i].resize(num_symbols); + DecodeSymbols(num_symbols, 1, out_buffer, context_symbols_[i].data()); + // All symbols are going to be processed from the back. + context_counters_[i] = num_symbols; + } + } + return true; + } + + inline uint32_t DecodeSymbol() { + // First check if we have a valid context. + if (active_context_ != -1) { + const int context_counter = --context_counters_[active_context_]; + if (context_counter < 0) + return TOPOLOGY_INVALID; + const int symbol_id = context_symbols_[active_context_][context_counter]; + last_symbol_ = edge_breaker_symbol_to_topology_id[symbol_id]; + } else { +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (BitstreamVersion() < DRACO_BITSTREAM_VERSION(2, 2)) { + // We don't have a predicted symbol or the symbol was mis-predicted. + // Decode it directly. + last_symbol_ = MeshEdgebreakerTraversalDecoder::DecodeSymbol(); + + } else +#endif + { + // The first symbol must be E. + last_symbol_ = TOPOLOGY_E; + } + } + return last_symbol_; + } + + inline void NewActiveCornerReached(CornerIndex corner) { + const CornerIndex next = corner_table_->Next(corner); + const CornerIndex prev = corner_table_->Previous(corner); + // Update valences. + switch (last_symbol_) { + case TOPOLOGY_C: + case TOPOLOGY_S: + vertex_valences_[corner_table_->Vertex(next)] += 1; + vertex_valences_[corner_table_->Vertex(prev)] += 1; + break; + case TOPOLOGY_R: + vertex_valences_[corner_table_->Vertex(corner)] += 1; + vertex_valences_[corner_table_->Vertex(next)] += 1; + vertex_valences_[corner_table_->Vertex(prev)] += 2; + break; + case TOPOLOGY_L: + vertex_valences_[corner_table_->Vertex(corner)] += 1; + vertex_valences_[corner_table_->Vertex(next)] += 2; + vertex_valences_[corner_table_->Vertex(prev)] += 1; + break; + case TOPOLOGY_E: + vertex_valences_[corner_table_->Vertex(corner)] += 2; + vertex_valences_[corner_table_->Vertex(next)] += 2; + vertex_valences_[corner_table_->Vertex(prev)] += 2; + break; + default: + break; + } + // Compute the new context that is going to be used to decode the next + // symbol. + const int active_valence = vertex_valences_[corner_table_->Vertex(next)]; + int clamped_valence; + if (active_valence < min_valence_) { + clamped_valence = min_valence_; + } else if (active_valence > max_valence_) { + clamped_valence = max_valence_; + } else { + clamped_valence = active_valence; + } + + active_context_ = (clamped_valence - min_valence_); + } + + inline void MergeVertices(VertexIndex dest, VertexIndex source) { + // Update valences on the merged vertices. + vertex_valences_[dest] += vertex_valences_[source]; + } + + private: + const CornerTable *corner_table_; + int num_vertices_; + IndexTypeVector<VertexIndex, int> vertex_valences_; + int last_symbol_; + int active_context_; + + int min_valence_; + int max_valence_; + std::vector<std::vector<uint32_t>> context_symbols_; + // Points to the active symbol in each context. + std::vector<int> context_counters_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_VALENCE_DECODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_valence_encoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_valence_encoder.h new file mode 100644 index 00000000000..ef3a86bf983 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_edgebreaker_traversal_valence_encoder.h @@ -0,0 +1,223 @@ +// 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_MESH_MESH_EDGEBREAKER_TRAVERSAL_VALENCE_ENCODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_VALENCE_ENCODER_H_ + +#include "draco/compression/entropy/symbol_encoding.h" +#include "draco/compression/mesh/mesh_edgebreaker_traversal_encoder.h" +#include "draco/core/varint_encoding.h" + +namespace draco { + +// Predictive encoder for the Edgebreaker symbols based on valences of the +// previously encoded vertices, following the method described in: Szymczak'02, +// "Optimized Edgebreaker Encoding for Large and Regular Triangle Meshes". Each +// valence is used to specify a different entropy context for encoding of the +// symbols. +// Encoder can operate in various predefined modes that can be used to select +// the way in which the entropy contexts are computed (e.g. using different +// clamping for valences, or even using different inputs to compute the +// contexts), see EdgebreakerValenceCodingMode in mesh_edgebreaker_shared.h for +// a list of supported modes. +class MeshEdgebreakerTraversalValenceEncoder + : public MeshEdgebreakerTraversalEncoder { + public: + MeshEdgebreakerTraversalValenceEncoder() + : corner_table_(nullptr), + prev_symbol_(-1), + last_corner_(kInvalidCornerIndex), + num_symbols_(0), + min_valence_(2), + max_valence_(7) {} + + bool Init(MeshEdgebreakerEncoderImplInterface *encoder) { + if (!MeshEdgebreakerTraversalEncoder::Init(encoder)) + return false; + min_valence_ = 2; + max_valence_ = 7; + corner_table_ = encoder->GetCornerTable(); + + // Initialize valences of all vertices. + vertex_valences_.resize(corner_table_->num_vertices()); + for (VertexIndex i(0); i < static_cast<uint32_t>(vertex_valences_.size()); + ++i) { + vertex_valences_[i] = corner_table_->Valence(VertexIndex(i)); + } + + // Replicate the corner to vertex map from the corner table. We need to do + // this because the map may get updated during encoding because we add new + // vertices when we encounter split symbols. + corner_to_vertex_map_.resize(corner_table_->num_corners()); + for (CornerIndex i(0); i < corner_table_->num_corners(); ++i) { + corner_to_vertex_map_[i] = corner_table_->Vertex(i); + } + const int32_t num_unique_valences = max_valence_ - min_valence_ + 1; + + context_symbols_.resize(num_unique_valences); + return true; + } + + inline void NewCornerReached(CornerIndex corner) { last_corner_ = corner; } + + inline void EncodeSymbol(EdgebreakerTopologyBitPattern symbol) { + ++num_symbols_; + // Update valences on the mesh and compute the context that is going to be + // used to encode the processed symbol. + // Note that the valences are computed for the so far unencoded part of the + // mesh (i.e. the decoding is reverse). Adding a new symbol either reduces + // valences on the vertices or leaves the valence unchanged. + + const CornerIndex next = corner_table_->Next(last_corner_); + const CornerIndex prev = corner_table_->Previous(last_corner_); + + // Get valence on the tip corner of the active edge (outgoing edge that is + // going to be used in reverse decoding of the connectivity to predict the + // next symbol). + const int active_valence = vertex_valences_[corner_to_vertex_map_[next]]; + switch (symbol) { + case TOPOLOGY_C: + // Compute prediction. + FALLTHROUGH_INTENDED; + case TOPOLOGY_S: + // Update valences. + vertex_valences_[corner_to_vertex_map_[next]] -= 1; + vertex_valences_[corner_to_vertex_map_[prev]] -= 1; + if (symbol == TOPOLOGY_S) { + // Whenever we reach a split symbol, we need to split the vertex into + // two and attach all corners on the left and right sides of the split + // vertex to the respective vertices (see image below). This is + // necessary since the decoder works in the reverse order and it + // merges the two vertices only after the split symbol is processed. + // + // * ----- + // / \-------- + // / \-------- + // / \------- + // *-------v-------* + // \ /c\ / + // \ / \ / + // \ /n S p\ / + // *.......* + // + + // Count the number of faces on the left side of the split vertex and + // update the valence on the "left vertex". + int num_left_faces = 0; + CornerIndex act_c = corner_table_->Opposite(prev); + while (act_c != kInvalidCornerIndex) { + if (encoder_impl()->IsFaceEncoded(corner_table_->Face(act_c))) + break; // Stop when we reach the first visited face. + ++num_left_faces; + act_c = corner_table_->Opposite(corner_table_->Next(act_c)); + } + vertex_valences_[corner_to_vertex_map_[last_corner_]] = + num_left_faces + 1; + + // Create a new vertex for the right side and count the number of + // faces that should be attached to this vertex. + const int new_vert_id = static_cast<int>(vertex_valences_.size()); + int num_right_faces = 0; + + act_c = corner_table_->Opposite(next); + while (act_c != kInvalidCornerIndex) { + if (encoder_impl()->IsFaceEncoded(corner_table_->Face(act_c))) + break; // Stop when we reach the first visited face. + ++num_right_faces; + // Map corners on the right side to the newly created vertex. + corner_to_vertex_map_[corner_table_->Next(act_c)] = new_vert_id; + act_c = corner_table_->Opposite(corner_table_->Previous(act_c)); + } + vertex_valences_.push_back(num_right_faces + 1); + } + break; + case TOPOLOGY_R: + // Update valences. + vertex_valences_[corner_to_vertex_map_[last_corner_]] -= 1; + vertex_valences_[corner_to_vertex_map_[next]] -= 1; + vertex_valences_[corner_to_vertex_map_[prev]] -= 2; + break; + case TOPOLOGY_L: + + vertex_valences_[corner_to_vertex_map_[last_corner_]] -= 1; + vertex_valences_[corner_to_vertex_map_[next]] -= 2; + vertex_valences_[corner_to_vertex_map_[prev]] -= 1; + break; + case TOPOLOGY_E: + vertex_valences_[corner_to_vertex_map_[last_corner_]] -= 2; + vertex_valences_[corner_to_vertex_map_[next]] -= 2; + vertex_valences_[corner_to_vertex_map_[prev]] -= 2; + break; + default: + break; + } + + if (prev_symbol_ != -1) { + int clamped_valence; + if (active_valence < min_valence_) { + clamped_valence = min_valence_; + } else if (active_valence > max_valence_) { + clamped_valence = max_valence_; + } else { + clamped_valence = active_valence; + } + + const int context = clamped_valence - min_valence_; + context_symbols_[context].push_back( + edge_breaker_topology_to_symbol_id[prev_symbol_]); + } + + prev_symbol_ = symbol; + } + + void Done() { + // Store the init face configurations and attribute seam data + MeshEdgebreakerTraversalEncoder::EncodeStartFaces(); + MeshEdgebreakerTraversalEncoder::EncodeAttributeSeams(); + + // Store the contexts. + for (int i = 0; i < context_symbols_.size(); ++i) { + EncodeVarint<uint32_t>(static_cast<uint32_t>(context_symbols_[i].size()), + GetOutputBuffer()); + if (context_symbols_[i].size() > 0) { + EncodeSymbols(context_symbols_[i].data(), + static_cast<int>(context_symbols_[i].size()), 1, nullptr, + GetOutputBuffer()); + } + } + } + + int NumEncodedSymbols() const { return num_symbols_; } + + private: + const CornerTable *corner_table_; + // Explicit map between corners and vertices. We cannot use the one stored + // in the |corner_table_| because we may need to add additional vertices to + // handle split symbols. + IndexTypeVector<CornerIndex, VertexIndex> corner_to_vertex_map_; + IndexTypeVector<VertexIndex, int> vertex_valences_; + // Previously encoded symbol. + int32_t prev_symbol_; + CornerIndex last_corner_; + // Explicitly count the number of encoded symbols. + int num_symbols_; + + int min_valence_; + int max_valence_; + std::vector<std::vector<uint32_t>> context_symbols_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_VALENCE_ENCODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder.cc new file mode 100644 index 00000000000..19d1355a443 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder.cc @@ -0,0 +1,34 @@ +// 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. +// +#include "draco/compression/mesh/mesh_encoder.h" + +namespace draco { + +MeshEncoder::MeshEncoder() : mesh_(nullptr), num_encoded_faces_(0) {} + +void MeshEncoder::SetMesh(const Mesh &m) { + mesh_ = &m; + SetPointCloud(m); +} + +bool MeshEncoder::EncodeGeometryData() { + if (!EncodeConnectivity()) + return false; + if (options()->GetGlobalBool("store_number_of_encoded_faces", false)) + ComputeNumberOfEncodedFaces(); + return true; +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder.h new file mode 100644 index 00000000000..41387d569c6 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder.h @@ -0,0 +1,84 @@ +// 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_MESH_MESH_ENCODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_ENCODER_H_ + +#include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h" +#include "draco/compression/point_cloud/point_cloud_encoder.h" +#include "draco/mesh/mesh.h" +#include "draco/mesh/mesh_attribute_corner_table.h" + +namespace draco { + +// Abstract base class for all mesh encoders. It provides some basic +// functionality that's shared between different encoders. +class MeshEncoder : public PointCloudEncoder { + public: + MeshEncoder(); + + // Sets the mesh that is going be encoded. Must be called before the Encode() + // method. + void SetMesh(const Mesh &m); + + EncodedGeometryType GetGeometryType() const override { + return TRIANGULAR_MESH; + } + + // Returns the number of faces that were encoded during the last Encode(). + // function call. Valid only if "store_number_of_encoded_faces" flag was set + // in the provided EncoderOptions. + size_t num_encoded_faces() const { return num_encoded_faces_; } + + // Returns the base connectivity of the encoded mesh (or nullptr if it is not + // initialized). + virtual const CornerTable *GetCornerTable() const { return nullptr; } + + // Returns the attribute connectivity data or nullptr if it does not exist. + virtual const MeshAttributeCornerTable *GetAttributeCornerTable( + int /* att_id */) const { + return nullptr; + } + + // Returns the encoding data for a given attribute or nullptr when the data + // does not exist. + virtual const MeshAttributeIndicesEncodingData *GetAttributeEncodingData( + int /* att_id */) const { + return nullptr; + } + + const Mesh *mesh() const { return mesh_; } + + protected: + bool EncodeGeometryData() override; + + // Needs to be implemented by the derived classes. + virtual bool EncodeConnectivity() = 0; + + // Computes and sets the num_encoded_faces_ for the encoder. + virtual void ComputeNumberOfEncodedFaces() = 0; + + void set_mesh(const Mesh *mesh) { mesh_ = mesh; } + void set_num_encoded_faces(size_t num_faces) { + num_encoded_faces_ = num_faces; + } + + private: + const Mesh *mesh_; + size_t num_encoded_faces_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_ENCODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder_helpers.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder_helpers.h new file mode 100644 index 00000000000..d809a521369 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder_helpers.h @@ -0,0 +1,81 @@ +// 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_MESH_MESH_ENCODER_HELPERS_H_ +#define DRACO_COMPRESSION_MESH_MESH_ENCODER_HELPERS_H_ + +#include "draco/compression/mesh/mesh_encoder.h" +#include "draco/mesh/triangle_soup_mesh_builder.h" + +namespace draco { + +// Helper class for encoding data supplied in a stream of single precision +// floating point numbers formatted as XYZ|UV. The stream must contain three +// XYZ|UV values for every face of the mesh. +// The encoded data is written into the output stream "os". +// In case of error, the stream is set to an invalid state (ios_base::bad_bit). +template <typename OStreamT> +OStreamT EncodePos3Tex2DataToStream( + const float *data, int num_faces, CompressionMethod method, + const MeshCompressionOptions &compression_options, + const MeshAttributeCompressionOptions &pos_options, + const MeshAttributeCompressionOptions &tex_options, OStreamT &&os) { + // Build the mesh. + TriangleSoupMeshBuilder mb; + mb.Start(num_faces); + const int pos_att_id = + mb.AddAttribute(GeometryAttribute::POSITION, 3, DT_FLOAT32); + const int tex_att_id = + mb.AddAttribute(GeometryAttribute::TEX_COORD_0, 2, DT_FLOAT32); + constexpr int data_stride = 5; + constexpr int tex_offset = 3; + for (int f = 0; f < num_faces; ++f) { + int offset = 3 * f * data_stride; + // Add position data for the face. + mb.SetAttributeValuesForFace(pos_att_id, f, data + offset, + data + offset + data_stride, + data + offset + 2 * data_stride); + // Add texture data for the face. + offset += tex_offset; + mb.SetAttributeValuesForFace(tex_att_id, f, data + offset, + data + offset + data_stride, + data + offset + 2 * data_stride); + } + std::unique_ptr<Mesh> mesh = mb.Finalize(); + if (mesh == nullptr) { + os.setstate(ios_base::badbit); + return os; + } + + // Set up the encoder. + std::unique_ptr<MeshEncoder> encoder = + MeshEncoder::CreateEncoderForMethod(method); + encoder->SetGlobalOptions(compression_options); + encoder->SetAttributeOptions(GeometryAttribute::POSITION, pos_options); + encoder->SetAttributeOptions(GeometryAttribute::TEX_COORD_0, tex_options); + + if (!encoder->EncodeMesh(mesh.get())) { + os.setstate(ios_base::badbit); + return os; + } + + // Write the encoded data into the stream. + os.write(static_cast<const char *>(encoder->buffer()->data()), + encoder->buffer()->size()); + return os; +} + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_ENCODER_HELPERS_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder_test.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder_test.cc new file mode 100644 index 00000000000..e67861a2ec2 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_encoder_test.cc @@ -0,0 +1,93 @@ +// 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. +// +#include "draco/compression/mesh/mesh_encoder.h" + +#include "draco/compression/expert_encode.h" +#include "draco/core/decoder_buffer.h" +#include "draco/core/draco_test_base.h" +#include "draco/core/draco_test_utils.h" +#include "draco/io/obj_decoder.h" + +namespace draco { + +class MeshEncoderTest : public ::testing::TestWithParam<const char *> { + protected: + MeshEncoderTest() {} + + // Fills out_method with id of the encoding method used for the test. + // Returns false if the encoding method is not set properly. + bool GetMethod(MeshEncoderMethod *out_method) const { + if (strcmp(GetParam(), "sequential") == 0) { + *out_method = MESH_SEQUENTIAL_ENCODING; + return true; + } + if (strcmp(GetParam(), "edgebreaker") == 0) { + *out_method = MESH_EDGEBREAKER_ENCODING; + return true; + } + return false; + } +}; + +TEST_P(MeshEncoderTest, EncodeGoldenMesh) { + // This test verifies that a given set of meshes are encoded to an expected + // output. This is useful for catching bugs in code changes that are not + // supposed to change the encoding. + // The test is expected to fail when the encoding is modified. In such case, + // the golden files need to be updated to reflect the changes. + MeshEncoderMethod method; + ASSERT_TRUE(GetMethod(&method)) + << "Test is run for an unknown encoding method"; + + const std::string file_name = "test_nm.obj"; + std::string golden_file_name = file_name; + golden_file_name += '.'; + golden_file_name += GetParam(); + golden_file_name += ".1.2.0.drc"; + const std::unique_ptr<Mesh> mesh(ReadMeshFromTestFile(file_name)); + ASSERT_NE(mesh, nullptr) << "Failed to load test model " << file_name; + + ExpertEncoder encoder(*mesh.get()); + encoder.SetEncodingMethod(method); + encoder.SetAttributeQuantization(0, 20); + EncoderBuffer buffer; + ASSERT_TRUE(encoder.EncodeToBuffer(&buffer).ok()) + << "Failed encoding test mesh " << file_name << " with method " + << GetParam(); + // Check that the encoded mesh was really encoded with the selected method. + DecoderBuffer decoder_buffer; + decoder_buffer.Init(buffer.data(), buffer.size()); + decoder_buffer.Advance(8); // Skip the header to the encoding method id. + uint8_t encoded_method; + decoder_buffer.Decode(&encoded_method); + ASSERT_EQ(encoded_method, method); + if (!FLAGS_update_golden_files) { + EXPECT_TRUE( + CompareGoldenFile(golden_file_name, buffer.data(), buffer.size())) + << "Encoded data is different from the golden file. Please verify that " + "the encoding works as expected and update the golden file if " + "necessary (run the test with --update_golden_files flag)."; + } else { + // Save the files into the local folder. + EXPECT_TRUE( + GenerateGoldenFile(golden_file_name, buffer.data(), buffer.size())) + << "Failed to generate new golden file for " << file_name; + } +} + +INSTANTIATE_TEST_CASE_P(MeshEncoderTests, MeshEncoderTest, + ::testing::Values("sequential", "edgebreaker")); + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_decoder.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_decoder.cc new file mode 100644 index 00000000000..de71700e160 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_decoder.cc @@ -0,0 +1,150 @@ +// 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. +// +#include "draco/compression/mesh/mesh_sequential_decoder.h" + +#include "draco/compression/attributes/linear_sequencer.h" +#include "draco/compression/attributes/sequential_attribute_decoders_controller.h" +#include "draco/compression/entropy/symbol_decoding.h" +#include "draco/core/varint_decoding.h" + +namespace draco { + +MeshSequentialDecoder::MeshSequentialDecoder() {} + +bool MeshSequentialDecoder::DecodeConnectivity() { + uint32_t num_faces; + uint32_t num_points; +#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED + if (bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) { + if (!buffer()->Decode(&num_faces)) + return false; + if (!buffer()->Decode(&num_points)) + return false; + + } else +#endif + { + if (!DecodeVarint(&num_faces, buffer())) + return false; + if (!DecodeVarint(&num_points, buffer())) + return false; + } + + // Check that num_faces and num_points are valid values. + const uint64_t faces_64 = static_cast<uint64_t>(num_faces); + const uint64_t points_64 = static_cast<uint64_t>(num_points); + // Compressed sequential encoding can only handle (2^32 - 1) / 3 indices. + if (faces_64 > 0xffffffff / 3) + return false; + if (points_64 > faces_64 * 3) + return false; + uint8_t connectivity_method; + if (!buffer()->Decode(&connectivity_method)) + return false; + if (connectivity_method == 0) { + if (!DecodeAndDecompressIndices(num_faces)) + return false; + } else { + if (num_points < 256) { + // Decode indices as uint8_t. + for (uint32_t i = 0; i < num_faces; ++i) { + Mesh::Face face; + for (int j = 0; j < 3; ++j) { + uint8_t val; + if (!buffer()->Decode(&val)) + return false; + face[j] = val; + } + mesh()->AddFace(face); + } + } else if (num_points < (1 << 16)) { + // Decode indices as uint16_t. + for (uint32_t i = 0; i < num_faces; ++i) { + Mesh::Face face; + for (int j = 0; j < 3; ++j) { + uint16_t val; + if (!buffer()->Decode(&val)) + return false; + face[j] = val; + } + mesh()->AddFace(face); + } + } else if (mesh()->num_points() < (1 << 21) && + bitstream_version() >= DRACO_BITSTREAM_VERSION(2, 2)) { + // Decode indices as uint32_t. + for (uint32_t i = 0; i < num_faces; ++i) { + Mesh::Face face; + for (int j = 0; j < 3; ++j) { + uint32_t val; + if (!DecodeVarint(&val, buffer())) + return false; + face[j] = val; + } + mesh()->AddFace(face); + } + } else { + // Decode faces as uint32_t (default). + for (uint32_t i = 0; i < num_faces; ++i) { + Mesh::Face face; + for (int j = 0; j < 3; ++j) { + uint32_t val; + if (!buffer()->Decode(&val)) + return false; + face[j] = val; + } + mesh()->AddFace(face); + } + } + } + point_cloud()->set_num_points(num_points); + return true; +} + +bool MeshSequentialDecoder::CreateAttributesDecoder(int32_t att_decoder_id) { + // Always create the basic attribute decoder. + return SetAttributesDecoder( + att_decoder_id, + std::unique_ptr<AttributesDecoder>( + new SequentialAttributeDecodersController( + std::unique_ptr<PointsSequencer>( + new LinearSequencer(point_cloud()->num_points()))))); +} + +bool MeshSequentialDecoder::DecodeAndDecompressIndices(uint32_t num_faces) { + // Get decoded indices differences that were encoded with an entropy code. + std::vector<uint32_t> indices_buffer(num_faces * 3); + if (!DecodeSymbols(num_faces * 3, 1, buffer(), indices_buffer.data())) + return false; + // Reconstruct the indices from the differences. + // See MeshSequentialEncoder::CompressAndEncodeIndices() for more details. + int32_t last_index_value = 0; + int vertex_index = 0; + for (uint32_t i = 0; i < num_faces; ++i) { + Mesh::Face face; + for (int j = 0; j < 3; ++j) { + const uint32_t encoded_val = indices_buffer[vertex_index++]; + int32_t index_diff = (encoded_val >> 1); + if (encoded_val & 1) + index_diff = -index_diff; + const int32_t index_value = index_diff + last_index_value; + face[j] = index_value; + last_index_value = index_value; + } + mesh()->AddFace(face); + } + return true; +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_decoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_decoder.h new file mode 100644 index 00000000000..3a86c75d5e9 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_decoder.h @@ -0,0 +1,39 @@ +// 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_MESH_MESH_SEQUENTIAL_DECODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_SEQUENTIAL_DECODER_H_ + +#include "draco/compression/mesh/mesh_decoder.h" + +namespace draco { + +// Class for decoding data encoded by MeshSequentialEncoder. +class MeshSequentialDecoder : public MeshDecoder { + public: + MeshSequentialDecoder(); + + protected: + bool DecodeConnectivity() override; + bool CreateAttributesDecoder(int32_t att_decoder_id) override; + + private: + // Decodes face indices that were compressed with an entropy code. + // Returns false on error. + bool DecodeAndDecompressIndices(uint32_t num_faces); +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_SEQUENTIAL_DECODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_encoder.cc b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_encoder.cc new file mode 100644 index 00000000000..44b3b20b63c --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_encoder.cc @@ -0,0 +1,131 @@ +// 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. +// +#include "draco/compression/mesh/mesh_sequential_encoder.h" + +#include <cstdlib> + +#include "draco/compression/attributes/linear_sequencer.h" +#include "draco/compression/attributes/sequential_attribute_encoders_controller.h" +#include "draco/compression/entropy/symbol_encoding.h" +#include "draco/core/varint_encoding.h" + +namespace draco { + +MeshSequentialEncoder::MeshSequentialEncoder() {} + +bool MeshSequentialEncoder::EncodeConnectivity() { + // Serialize indices. + const uint32_t num_faces = mesh()->num_faces(); + EncodeVarint(num_faces, buffer()); + EncodeVarint(static_cast<uint32_t>(mesh()->num_points()), buffer()); + + // We encode all attributes in the original (possibly duplicated) format. + // TODO(ostava): This may not be optimal if we have only one attribute or if + // all attributes share the same index mapping. + if (options()->GetGlobalBool("compress_connectivity", false)) { + // 0 = Encode compressed indices. + buffer()->Encode(static_cast<uint8_t>(0)); + if (!CompressAndEncodeIndices()) + return false; + } else { + // 1 = Encode indices directly. + buffer()->Encode(static_cast<uint8_t>(1)); + // Store vertex indices using a smallest data type that fits their range. + // TODO(ostava): This can be potentially improved by using a tighter + // fit that is not bound by a bit-length of any particular data type. + if (mesh()->num_points() < 256) { + // Serialize indices as uint8_t. + for (FaceIndex i(0); i < num_faces; ++i) { + const auto &face = mesh()->face(i); + buffer()->Encode(static_cast<uint8_t>(face[0].value())); + buffer()->Encode(static_cast<uint8_t>(face[1].value())); + buffer()->Encode(static_cast<uint8_t>(face[2].value())); + } + } else if (mesh()->num_points() < (1 << 16)) { + // Serialize indices as uint16_t. + for (FaceIndex i(0); i < num_faces; ++i) { + const auto &face = mesh()->face(i); + buffer()->Encode(static_cast<uint16_t>(face[0].value())); + buffer()->Encode(static_cast<uint16_t>(face[1].value())); + buffer()->Encode(static_cast<uint16_t>(face[2].value())); + } + } else if (mesh()->num_points() < (1 << 21)) { + // Serialize indices as varint. + for (FaceIndex i(0); i < num_faces; ++i) { + const auto &face = mesh()->face(i); + EncodeVarint(static_cast<uint32_t>(face[0].value()), buffer()); + EncodeVarint(static_cast<uint32_t>(face[1].value()), buffer()); + EncodeVarint(static_cast<uint32_t>(face[2].value()), buffer()); + } + } else { + // Serialize faces as uint32_t (default). + for (FaceIndex i(0); i < num_faces; ++i) { + const auto &face = mesh()->face(i); + buffer()->Encode(face); + } + } + } + return true; +} + +bool MeshSequentialEncoder::GenerateAttributesEncoder(int32_t att_id) { + // Create only one attribute encoder that is going to encode all points in a + // linear sequence. + if (att_id == 0) { + // Create a new attribute encoder only for the first attribute. + AddAttributesEncoder(std::unique_ptr<AttributesEncoder>( + new SequentialAttributeEncodersController( + std::unique_ptr<PointsSequencer>( + new LinearSequencer(point_cloud()->num_points())), + att_id))); + } else { + // Reuse the existing attribute encoder for other attributes. + attributes_encoder(0)->AddAttributeId(att_id); + } + return true; +} + +bool MeshSequentialEncoder::CompressAndEncodeIndices() { + // Collect all indices to a buffer and encode them. + // Each new index is a difference from the previous value. + std::vector<uint32_t> indices_buffer; + int32_t last_index_value = 0; + const int num_faces = mesh()->num_faces(); + for (FaceIndex i(0); i < num_faces; ++i) { + const auto &face = mesh()->face(i); + for (int j = 0; j < 3; ++j) { + const int32_t index_value = face[j].value(); + const int32_t index_diff = index_value - last_index_value; + // Encode signed value to an unsigned one (put the sign to lsb pos). + const uint32_t encoded_val = + (abs(index_diff) << 1) | (index_diff < 0 ? 1 : 0); + indices_buffer.push_back(encoded_val); + last_index_value = index_value; + } + } + EncodeSymbols(indices_buffer.data(), static_cast<int>(indices_buffer.size()), + 1, nullptr, buffer()); + return true; +} + +void MeshSequentialEncoder::ComputeNumberOfEncodedPoints() { + set_num_encoded_points(mesh()->num_points()); +} + +void MeshSequentialEncoder::ComputeNumberOfEncodedFaces() { + set_num_encoded_faces(mesh()->num_faces()); +} + +} // namespace draco diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_encoder.h b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_encoder.h new file mode 100644 index 00000000000..47a4fec837c --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/mesh_sequential_encoder.h @@ -0,0 +1,57 @@ +// 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. +// +// The encoder compresses all attribute values using an order preserving +// attribute encoder (that can still support quantization, prediction schemes, +// and other features). +// The mesh connectivity data can be encoded using two modes that are controlled +// using a global encoder options flag called "compress_connectivity" +// 1. When "compress_connectivity" == true: +// All point ids are first delta coded and then compressed using an entropy +// coding. +// 2. When "compress_connectivity" == false: +// All point ids are encoded directly using either 8, 16, or 32 bits per +// value based on the maximum point id value. + +#ifndef DRACO_COMPRESSION_MESH_MESH_SEQUENTIAL_ENCODER_H_ +#define DRACO_COMPRESSION_MESH_MESH_SEQUENTIAL_ENCODER_H_ + +#include "draco/compression/mesh/mesh_encoder.h" + +namespace draco { + +// Class that encodes mesh data using a simple binary representation of mesh's +// connectivity and geometry. +// TODO(ostava): Use a better name. +class MeshSequentialEncoder : public MeshEncoder { + public: + MeshSequentialEncoder(); + uint8_t GetEncodingMethod() const override { + return MESH_SEQUENTIAL_ENCODING; + } + + protected: + bool EncodeConnectivity() override; + bool GenerateAttributesEncoder(int32_t att_id) override; + void ComputeNumberOfEncodedPoints() override; + void ComputeNumberOfEncodedFaces() override; + + private: + // Returns false on error. + bool CompressAndEncodeIndices(); +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_MESH_SEQUENTIAL_ENCODER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/traverser/depth_first_traverser.h b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/depth_first_traverser.h new file mode 100644 index 00000000000..84420cb3888 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/depth_first_traverser.h @@ -0,0 +1,169 @@ +// 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_MESH_TRAVERSER_DEPTH_FIRST_TRAVERSER_H_ +#define DRACO_COMPRESSION_MESH_TRAVERSER_DEPTH_FIRST_TRAVERSER_H_ + +#include <vector> + +#include "draco/compression/mesh/traverser/traverser_base.h" +#include "draco/mesh/corner_table.h" + +namespace draco { + +// Basic traverser that traverses a mesh in a DFS like fashion using the +// CornerTable data structure. The necessary bookkeeping is available via the +// TraverserBase. Callbacks are handled through template argument +// TraversalObserverT. +// +// TraversalObserverT can perform an action on a traversal event such as newly +// visited face, or corner, but it does not affect the traversal itself. +// +// Concept TraversalObserverT requires: +// +// public: +// void OnNewFaceVisited(FaceIndex face); +// - Called whenever a previously unvisited face is reached. +// +// void OnNewVertexVisited(VertexIndex vert, CornerIndex corner) +// - Called when a new vertex is visited. |corner| is used to indicate the +// which of the vertex's corners has been reached. + +template <class CornerTableT, class TraversalObserverT> +class DepthFirstTraverser + : public TraverserBase<CornerTableT, TraversalObserverT> { + public: + typedef CornerTableT CornerTable; + typedef TraversalObserverT TraversalObserver; + typedef TraverserBase<CornerTable, TraversalObserver> Base; + + DepthFirstTraverser() {} + + // Called before any traversing starts. + void OnTraversalStart() {} + + // Called when all the traversing is done. + void OnTraversalEnd() {} + + bool TraverseFromCorner(CornerIndex corner_id) { + if (this->IsFaceVisited(corner_id)) + return true; // Already traversed. + + corner_traversal_stack_.clear(); + corner_traversal_stack_.push_back(corner_id); + // For the first face, check the remaining corners as they may not be + // processed yet. + const VertexIndex next_vert = + this->corner_table()->Vertex(this->corner_table()->Next(corner_id)); + const VertexIndex prev_vert = + this->corner_table()->Vertex(this->corner_table()->Previous(corner_id)); + if (next_vert == kInvalidVertexIndex || prev_vert == kInvalidVertexIndex) + return false; + if (!this->IsVertexVisited(next_vert)) { + this->MarkVertexVisited(next_vert); + this->traversal_observer().OnNewVertexVisited( + next_vert, this->corner_table()->Next(corner_id)); + } + if (!this->IsVertexVisited(prev_vert)) { + this->MarkVertexVisited(prev_vert); + this->traversal_observer().OnNewVertexVisited( + prev_vert, this->corner_table()->Previous(corner_id)); + } + + // Start the actual traversal. + while (!corner_traversal_stack_.empty()) { + // Currently processed corner. + corner_id = corner_traversal_stack_.back(); + FaceIndex face_id(corner_id.value() / 3); + // Make sure the face hasn't been visited yet. + if (corner_id == kInvalidCornerIndex || this->IsFaceVisited(face_id)) { + // This face has been already traversed. + corner_traversal_stack_.pop_back(); + continue; + } + while (true) { + this->MarkFaceVisited(face_id); + this->traversal_observer().OnNewFaceVisited(face_id); + const VertexIndex vert_id = this->corner_table()->Vertex(corner_id); + if (vert_id == kInvalidVertexIndex) + return false; + if (!this->IsVertexVisited(vert_id)) { + const bool on_boundary = this->corner_table()->IsOnBoundary(vert_id); + this->MarkVertexVisited(vert_id); + this->traversal_observer().OnNewVertexVisited(vert_id, corner_id); + if (!on_boundary) { + corner_id = this->corner_table()->GetRightCorner(corner_id); + face_id = FaceIndex(corner_id.value() / 3); + continue; + } + } + // The current vertex has been already visited or it was on a boundary. + // We need to determine whether we can visit any of it's neighboring + // faces. + const CornerIndex right_corner_id = + this->corner_table()->GetRightCorner(corner_id); + const CornerIndex left_corner_id = + this->corner_table()->GetLeftCorner(corner_id); + const FaceIndex right_face_id( + (right_corner_id == kInvalidCornerIndex + ? kInvalidFaceIndex + : FaceIndex(right_corner_id.value() / 3))); + const FaceIndex left_face_id( + (left_corner_id == kInvalidCornerIndex + ? kInvalidFaceIndex + : FaceIndex(left_corner_id.value() / 3))); + if (this->IsFaceVisited(right_face_id)) { + // Right face has been already visited. + if (this->IsFaceVisited(left_face_id)) { + // Both neighboring faces are visited. End reached. + corner_traversal_stack_.pop_back(); + break; // Break from the while (true) loop. + } else { + // Go to the left face. + corner_id = left_corner_id; + face_id = left_face_id; + } + } else { + // Right face was not visited. + if (this->IsFaceVisited(left_face_id)) { + // Left face visited, go to the right one. + corner_id = right_corner_id; + face_id = right_face_id; + } else { + // Both neighboring faces are unvisited, we need to visit both of + // them. + + // Split the traversal. + // First make the top of the current corner stack point to the left + // face (this one will be processed second). + corner_traversal_stack_.back() = left_corner_id; + // Add a new corner to the top of the stack (right face needs to + // be traversed first). + corner_traversal_stack_.push_back(right_corner_id); + // Break from the while (true) loop. + break; + } + } + } + } + return true; + } + + private: + std::vector<CornerIndex> corner_traversal_stack_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_TRAVERSER_DEPTH_FIRST_TRAVERSER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/traverser/max_prediction_degree_traverser.h b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/max_prediction_degree_traverser.h new file mode 100644 index 00000000000..b60d2c159f2 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/max_prediction_degree_traverser.h @@ -0,0 +1,223 @@ +// 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_MESH_TRAVERSER_MAX_PREDICTION_DEGREE_TRAVERSER_H_ +#define DRACO_COMPRESSION_MESH_TRAVERSER_MAX_PREDICTION_DEGREE_TRAVERSER_H_ + +#include <vector> + +#include "draco/compression/mesh/traverser/traverser_base.h" +#include "draco/mesh/corner_table.h" + +namespace draco { + +// PredictionDegreeTraverser provides framework for traversal over a corner +// table data structure following paper "Multi-way Geometry Encoding" by +// Cohen-or at al.'02. The traversal is implicitly guided by prediction degree +// of the destination vertices. A prediction degree is computed as the number of +// possible faces that can be used as source points for traversal to the given +// destination vertex (see image below, where faces F1 and F2 are already +// traversed and face F0 is not traversed yet. The prediction degree of vertex +// V is then equal to two). +// +// X-----V-----o +// / \ / \ / \ +// / F0\ / \ / F2\ +// X-----o-----o-----B +// \ F1/ +// \ / +// A +// +// The class implements the same interface as the DepthFirstTraverser +// (depth_first_traverser.h) and it can be controlled via the same template +// trait classes |CornerTableT| and |TraversalObserverT|, that are used +// for controlling and monitoring of the traversal respectively. For details, +// please see depth_first_traverser.h. +template <class CornerTableT, class TraversalObserverT> +class MaxPredictionDegreeTraverser + : public TraverserBase<CornerTable, TraversalObserverT> { + public: + typedef CornerTableT CornerTable; + typedef TraversalObserverT TraversalObserver; + typedef TraverserBase<CornerTable, TraversalObserver> Base; + + MaxPredictionDegreeTraverser() {} + + // Called before any traversing starts. + void OnTraversalStart() { + prediction_degree_.resize(this->corner_table()->num_vertices(), 0); + } + + // Called when all the traversing is done. + void OnTraversalEnd() {} + + bool TraverseFromCorner(CornerIndex corner_id) { + if (prediction_degree_.size() == 0) + return true; + + // Traversal starts from the |corner_id|. It's going to follow either the + // right or the left neighboring faces to |corner_id| based on their + // prediction degree. + traversal_stacks_[0].push_back(corner_id); + best_priority_ = 0; + // For the first face, check the remaining corners as they may not be + // processed yet. + const VertexIndex next_vert = + this->corner_table()->Vertex(this->corner_table()->Next(corner_id)); + const VertexIndex prev_vert = + this->corner_table()->Vertex(this->corner_table()->Previous(corner_id)); + if (!this->IsVertexVisited(next_vert)) { + this->MarkVertexVisited(next_vert); + this->traversal_observer().OnNewVertexVisited( + next_vert, this->corner_table()->Next(corner_id)); + } + if (!this->IsVertexVisited(prev_vert)) { + this->MarkVertexVisited(prev_vert); + this->traversal_observer().OnNewVertexVisited( + prev_vert, this->corner_table()->Previous(corner_id)); + } + const VertexIndex tip_vertex = this->corner_table()->Vertex(corner_id); + if (!this->IsVertexVisited(tip_vertex)) { + this->MarkVertexVisited(tip_vertex); + this->traversal_observer().OnNewVertexVisited(tip_vertex, corner_id); + } + // Start the actual traversal. + while ((corner_id = PopNextCornerToTraverse()) != kInvalidCornerIndex) { + FaceIndex face_id(corner_id.value() / 3); + // Make sure the face hasn't been visited yet. + if (this->IsFaceVisited(face_id)) { + // This face has been already traversed. + continue; + } + + while (true) { + face_id = FaceIndex(corner_id.value() / 3); + this->MarkFaceVisited(face_id); + this->traversal_observer().OnNewFaceVisited(face_id); + + // If the newly reached vertex hasn't been visited, mark it and notify + // the observer. + const VertexIndex vert_id = this->corner_table()->Vertex(corner_id); + if (!this->IsVertexVisited(vert_id)) { + this->MarkVertexVisited(vert_id); + this->traversal_observer().OnNewVertexVisited(vert_id, corner_id); + } + + // Check whether we can traverse to the right and left neighboring + // faces. + const CornerIndex right_corner_id = + this->corner_table()->GetRightCorner(corner_id); + const CornerIndex left_corner_id = + this->corner_table()->GetLeftCorner(corner_id); + const FaceIndex right_face_id( + (right_corner_id == kInvalidCornerIndex + ? kInvalidFaceIndex + : FaceIndex(right_corner_id.value() / 3))); + const FaceIndex left_face_id( + (left_corner_id == kInvalidCornerIndex + ? kInvalidFaceIndex + : FaceIndex(left_corner_id.value() / 3))); + const bool is_right_face_visited = this->IsFaceVisited(right_face_id); + const bool is_left_face_visited = this->IsFaceVisited(left_face_id); + + if (!is_left_face_visited) { + // We can go to the left face. + const int priority = ComputePriority(left_corner_id); + if (is_right_face_visited && priority <= best_priority_) { + // Right face has been already visited and the priority is equal or + // better than the best priority. We are sure that the left face + // would be traversed next so there is no need to put it onto the + // stack. + corner_id = left_corner_id; + continue; + } else { + AddCornerToTraversalStack(left_corner_id, priority); + } + } + if (!is_right_face_visited) { + // Go to the right face. + const int priority = ComputePriority(right_corner_id); + if (priority <= best_priority_) { + // We are sure that the right face would be traversed next so there + // is no need to put it onto the stack. + corner_id = right_corner_id; + continue; + } else { + AddCornerToTraversalStack(right_corner_id, priority); + } + } + + // Couldn't proceed directly to the next corner + break; + } + } + return true; + } + + private: + // Retrieves the next available corner (edge) to traverse. Edges are processed + // based on their priorities. + // Returns kInvalidCornerIndex when there is no edge available. + CornerIndex PopNextCornerToTraverse() { + for (int i = best_priority_; i < kMaxPriority; ++i) { + if (!traversal_stacks_[i].empty()) { + const CornerIndex ret = traversal_stacks_[i].back(); + traversal_stacks_[i].pop_back(); + best_priority_ = i; + return ret; + } + } + return kInvalidCornerIndex; + } + + inline void AddCornerToTraversalStack(CornerIndex ci, int priority) { + traversal_stacks_[priority].push_back(ci); + // Make sure that the best available priority is up to date. + if (priority < best_priority_) + best_priority_ = priority; + } + + // Returns the priority of traversing edge leading to |corner_id|. + inline int ComputePriority(CornerIndex corner_id) { + const VertexIndex v_tip = this->corner_table()->Vertex(corner_id); + // Priority 0 when traversing to already visited vertices. + int priority = 0; + if (!this->IsVertexVisited(v_tip)) { + const int degree = ++prediction_degree_[v_tip]; + // Priority 1 when prediction degree > 1, otherwise 2. + priority = (degree > 1 ? 1 : 2); + } + // Clamp the priority to the maximum number of buckets. + if (priority >= kMaxPriority) + priority = kMaxPriority - 1; + return priority; + } + + // For efficiency reasons, the priority traversal is implemented using buckets + // where each buckets represent a stack of available corners for a given + // priority. Corners with the highest priority are always processed first. + static constexpr int kMaxPriority = 3; + std::vector<CornerIndex> traversal_stacks_[kMaxPriority]; + + // Keep the track of the best available priority to improve the performance + // of PopNextCornerToTraverse() method. + int best_priority_; + + // Prediction degree available for each vertex. + IndexTypeVector<VertexIndex, int> prediction_degree_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_TRAVERSER_MAX_PREDICTION_DEGREE_TRAVERSER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/traverser/mesh_attribute_indices_encoding_observer.h b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/mesh_attribute_indices_encoding_observer.h new file mode 100644 index 00000000000..e66dd14b238 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/mesh_attribute_indices_encoding_observer.h @@ -0,0 +1,76 @@ +// 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_MESH_TRAVERSER_MESH_ATTRIBUTE_INDICES_ENCODING_OBSERVER_H_ +#define DRACO_COMPRESSION_MESH_TRAVERSER_MESH_ATTRIBUTE_INDICES_ENCODING_OBSERVER_H_ + +#include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h" +#include "draco/compression/attributes/points_sequencer.h" +#include "draco/mesh/mesh.h" + +namespace draco { + +// Class that can be used to generate encoding (and decoding) order of attribute +// values based on the traversal of the encoded mesh. The class should be used +// as the TraversalObserverT member of a Traverser class such as the +// DepthFirstTraverser (depth_first_traverser.h). +// TODO(hemmer): rename to AttributeIndicesCodingTraverserObserver +template <class CornerTableT> +class MeshAttributeIndicesEncodingObserver { + public: + MeshAttributeIndicesEncodingObserver() + : att_connectivity_(nullptr), + encoding_data_(nullptr), + mesh_(nullptr), + sequencer_(nullptr) {} + MeshAttributeIndicesEncodingObserver( + const CornerTableT *connectivity, const Mesh *mesh, + PointsSequencer *sequencer, + MeshAttributeIndicesEncodingData *encoding_data) + : att_connectivity_(connectivity), + encoding_data_(encoding_data), + mesh_(mesh), + sequencer_(sequencer) {} + + // Interface for TraversalObserverT + + void OnNewFaceVisited(FaceIndex /* face */) {} + + inline void OnNewVertexVisited(VertexIndex vertex, CornerIndex corner) { + const PointIndex point_id = + mesh_->face(FaceIndex(corner.value() / 3))[corner.value() % 3]; + // Append the visited attribute to the encoding order. + sequencer_->AddPointId(point_id); + + // Keep track of visited corners. + encoding_data_->encoded_attribute_value_index_to_corner_map.push_back( + corner); + + encoding_data_ + ->vertex_to_encoded_attribute_value_index_map[vertex.value()] = + encoding_data_->num_values; + + encoding_data_->num_values++; + } + + private: + const CornerTableT *att_connectivity_; + MeshAttributeIndicesEncodingData *encoding_data_; + const Mesh *mesh_; + PointsSequencer *sequencer_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_TRAVERSER_MESH_ATTRIBUTE_INDICES_ENCODING_OBSERVER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/traverser/mesh_traversal_sequencer.h b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/mesh_traversal_sequencer.h new file mode 100644 index 00000000000..fbcda53b792 --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/mesh_traversal_sequencer.h @@ -0,0 +1,110 @@ +// 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_MESH_TRAVERSER_MESH_TRAVERSAL_SEQUENCER_H_ +#define DRACO_COMPRESSION_MESH_TRAVERSER_MESH_TRAVERSAL_SEQUENCER_H_ + +#include "draco/attributes/geometry_indices.h" +#include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h" +#include "draco/compression/attributes/points_sequencer.h" +#include "draco/mesh/mesh.h" + +namespace draco { + +// Sequencer that generates point sequence in an order given by a deterministic +// traversal on the mesh surface. Note that all attributes encoded with this +// sequence must share the same connectivity. +// TODO(hemmer): Consider refactoring such that this is an observer. +template <class TraverserT> +class MeshTraversalSequencer : public PointsSequencer { + public: + MeshTraversalSequencer(const Mesh *mesh, + const MeshAttributeIndicesEncodingData *encoding_data) + : mesh_(mesh), encoding_data_(encoding_data), corner_order_(nullptr) {} + void SetTraverser(const TraverserT &t) { traverser_ = t; } + + // Function that can be used to set an order in which the mesh corners should + // be processed. This is an optional flag used usually only by the encoder + // to match the same corner order that is going to be used by the decoder. + // Note that |corner_order| should contain only one corner per face (it can + // have all corners but only the first encountered corner for each face is + // going to be used to start a traversal). If the corner order is not set, the + // corners are processed sequentially based on their ids. + void SetCornerOrder(const std::vector<CornerIndex> &corner_order) { + corner_order_ = &corner_order; + } + + bool UpdatePointToAttributeIndexMapping(PointAttribute *attribute) override { + const auto *corner_table = traverser_.corner_table(); + attribute->SetExplicitMapping(mesh_->num_points()); + const size_t num_faces = mesh_->num_faces(); + const size_t num_points = mesh_->num_points(); + for (FaceIndex f(0); f < static_cast<uint32_t>(num_faces); ++f) { + const auto &face = mesh_->face(f); + for (int p = 0; p < 3; ++p) { + const PointIndex point_id = face[p]; + const VertexIndex vert_id = + corner_table->Vertex(CornerIndex(3 * f.value() + p)); + if (vert_id == kInvalidVertexIndex) + return false; + const AttributeValueIndex att_entry_id( + encoding_data_ + ->vertex_to_encoded_attribute_value_index_map[vert_id.value()]); + if (att_entry_id.value() >= num_points) { + // There cannot be more attribute values than the number of points. + return false; + } + attribute->SetPointMapEntry(point_id, att_entry_id); + } + } + return true; + } + + protected: + bool GenerateSequenceInternal() override { + // Preallocate memory for storing point indices. We expect the number of + // points to be the same as the number of corner table vertices. + out_point_ids()->reserve(traverser_.corner_table()->num_vertices()); + + traverser_.OnTraversalStart(); + if (corner_order_) { + for (uint32_t i = 0; i < corner_order_->size(); ++i) { + if (!ProcessCorner(corner_order_->at(i))) + return false; + } + } else { + const int32_t num_faces = traverser_.corner_table()->num_faces(); + for (int i = 0; i < num_faces; ++i) { + if (!ProcessCorner(CornerIndex(3 * i))) + return false; + } + } + traverser_.OnTraversalEnd(); + return true; + } + + private: + bool ProcessCorner(CornerIndex corner_id) { + return traverser_.TraverseFromCorner(corner_id); + } + + TraverserT traverser_; + const Mesh *mesh_; + const MeshAttributeIndicesEncodingData *encoding_data_; + const std::vector<CornerIndex> *corner_order_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_TRAVERSER_MESH_TRAVERSAL_SEQUENCER_H_ diff --git a/extern/draco/dracoenc/src/draco/compression/mesh/traverser/traverser_base.h b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/traverser_base.h new file mode 100644 index 00000000000..643c5db565b --- /dev/null +++ b/extern/draco/dracoenc/src/draco/compression/mesh/traverser/traverser_base.h @@ -0,0 +1,85 @@ +// 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_MESH_TRAVERSER_TRAVERSER_BASE_H_ +#define DRACO_COMPRESSION_MESH_TRAVERSER_TRAVERSER_BASE_H_ + +#include "draco/mesh/corner_table.h" + +namespace draco { + +// Class providing the basic traversal functionality needed by traversers (such +// as the DepthFirstTraverser, see depth_first_traverser.h). It keeps a pointer +// to the corner table that is used for the traversal, plus it provides a basic +// bookkeeping of visited faces and vertices during the traversal. +template <class CornerTableT, class TraversalObserverT> +class TraverserBase { + public: + typedef CornerTableT CornerTable; + typedef TraversalObserverT TraversalObserver; + + TraverserBase() : corner_table_(nullptr) {} + virtual ~TraverserBase() = default; + + virtual void Init(const CornerTable *corner_table, + TraversalObserver traversal_observer) { + corner_table_ = corner_table; + is_face_visited_.assign(corner_table->num_faces(), false); + is_vertex_visited_.assign(corner_table_->num_vertices(), false); + traversal_observer_ = traversal_observer; + } + + const CornerTable &GetCornerTable() const { return *corner_table_; } + + inline bool IsFaceVisited(FaceIndex face_id) const { + if (face_id == kInvalidFaceIndex) + return true; // Invalid faces are always considered as visited. + return is_face_visited_[face_id.value()]; + } + + // Returns true if the face containing the given corner was visited. + inline bool IsFaceVisited(CornerIndex corner_id) const { + if (corner_id == kInvalidCornerIndex) + return true; // Invalid faces are always considered as visited. + return is_face_visited_[corner_id.value() / 3]; + } + + inline void MarkFaceVisited(FaceIndex face_id) { + is_face_visited_[face_id.value()] = true; + } + inline bool IsVertexVisited(VertexIndex vert_id) const { + return is_vertex_visited_[vert_id.value()]; + } + inline void MarkVertexVisited(VertexIndex vert_id) { + is_vertex_visited_[vert_id.value()] = true; + } + + inline const CornerTable *corner_table() const { return corner_table_; } + inline const TraversalObserverT &traversal_observer() const { + return traversal_observer_; + } + inline TraversalObserverT &traversal_observer() { + return traversal_observer_; + } + + private: + const CornerTable *corner_table_; + TraversalObserverT traversal_observer_; + std::vector<bool> is_face_visited_; + std::vector<bool> is_vertex_visited_; +}; + +} // namespace draco + +#endif // DRACO_COMPRESSION_MESH_TRAVERSER_TRAVERSER_BASE_H_ |