diff options
Diffstat (limited to 'extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.h')
| -rw-r--r-- | extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.h | 228 |
1 files changed, 228 insertions, 0 deletions
diff --git a/extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.h b/extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.h new file mode 100644 index 00000000000..78053f91dbe --- /dev/null +++ b/extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.h @@ -0,0 +1,228 @@ +// 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/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/compression/mesh/traverser/mesh_traversal_sequencer.h" +#include "draco/core/decoder_buffer.h" +#include "draco/draco_features.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_ |