diff options
Diffstat (limited to 'extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.cc')
| -rw-r--r-- | extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.cc | 1216 |
1 files changed, 1216 insertions, 0 deletions
diff --git a/extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.cc b/extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.cc new file mode 100644 index 00000000000..50d1971c15b --- /dev/null +++ b/extern/draco/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.cc @@ -0,0 +1,1216 @@ +// 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 |