1 // Copyright 2016 The Draco Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 #ifndef DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_H_ 16 #define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_H_ 17 18 #include <unordered_map> 19 #include <unordered_set> 20 21 #include "draco/compression/attributes/mesh_attribute_indices_encoding_data.h" 22 #include "draco/compression/mesh/mesh_edgebreaker_decoder_impl_interface.h" 23 #include "draco/compression/mesh/mesh_edgebreaker_shared.h" 24 #include "draco/compression/mesh/traverser/mesh_traversal_sequencer.h" 25 #include "draco/core/decoder_buffer.h" 26 #include "draco/draco_features.h" 27 #include "draco/mesh/corner_table.h" 28 #include "draco/mesh/mesh_attribute_corner_table.h" 29 30 namespace draco { 31 32 // Implementation of the edgebreaker decoder that decodes data encoded with the 33 // MeshEdgebreakerEncoderImpl class. The implementation of the decoder is based 34 // on the algorithm presented in Isenburg et al'02 "Spirale Reversi: Reverse 35 // decoding of the Edgebreaker encoding". Note that the encoding is still based 36 // on the standard edgebreaker method as presented in "3D Compression 37 // Made Simple: Edgebreaker on a Corner-Table" by Rossignac at al.'01. 38 // http://www.cc.gatech.edu/~jarek/papers/CornerTableSMI.pdf. One difference is 39 // caused by the properties of the spirale reversi algorithm that decodes the 40 // symbols from the last one to the first one. To make the decoding more 41 // efficient, we encode all symbols in the reverse order, therefore the decoder 42 // can process them one by one. 43 // The main advantage of the spirale reversi method is that the partially 44 // decoded mesh has valid connectivity data at any time during the decoding 45 // process (valid with respect to the decoded portion of the mesh). The standard 46 // Edgebreaker decoder used two passes (forward decoding + zipping) which not 47 // only prevented us from having a valid connectivity but it was also slower. 48 // The main benefit of having the valid connectivity is that we can use the 49 // known connectivity to predict encoded symbols that can improve the 50 // compression rate. 51 template <class TraversalDecoderT> 52 class MeshEdgebreakerDecoderImpl : public MeshEdgebreakerDecoderImplInterface { 53 public: 54 MeshEdgebreakerDecoderImpl(); 55 bool Init(MeshEdgebreakerDecoder *decoder) override; 56 57 const MeshAttributeCornerTable *GetAttributeCornerTable( 58 int att_id) const override; 59 const MeshAttributeIndicesEncodingData *GetAttributeEncodingData( 60 int att_id) const override; 61 62 bool CreateAttributesDecoder(int32_t att_decoder_id) override; 63 bool DecodeConnectivity() override; 64 bool OnAttributesDecoded() override; GetDecoder()65 MeshEdgebreakerDecoder *GetDecoder() const override { return decoder_; } GetCornerTable()66 const CornerTable *GetCornerTable() const override { 67 return corner_table_.get(); 68 } 69 70 private: 71 // Creates a vertex traversal sequencer for the specified |TraverserT| type. 72 template <class TraverserT> 73 std::unique_ptr<PointsSequencer> CreateVertexTraversalSequencer( 74 MeshAttributeIndicesEncodingData *encoding_data); 75 76 // Decodes connectivity between vertices (vertex indices). 77 // Returns the number of vertices created by the decoder or -1 on error. 78 int DecodeConnectivity(int num_symbols); 79 80 // Returns true if the current symbol was part of a topology split event. This 81 // means that the current face was connected to the left edge of a face 82 // encoded with the TOPOLOGY_S symbol. |out_symbol_edge| can be used to 83 // identify which edge of the source symbol was connected to the TOPOLOGY_S 84 // symbol. IsTopologySplit(int encoder_symbol_id,EdgeFaceName * out_face_edge,int * out_encoder_split_symbol_id)85 bool IsTopologySplit(int encoder_symbol_id, EdgeFaceName *out_face_edge, 86 int *out_encoder_split_symbol_id) { 87 if (topology_split_data_.size() == 0) { 88 return false; 89 } 90 if (topology_split_data_.back().source_symbol_id > 91 static_cast<uint32_t>(encoder_symbol_id)) { 92 // Something is wrong; if the desired source symbol is greater than the 93 // current encoder_symbol_id, we missed it, or the input was tampered 94 // (|encoder_symbol_id| keeps decreasing). 95 // Return invalid symbol id to notify the decoder that there was an 96 // error. 97 *out_encoder_split_symbol_id = -1; 98 return true; 99 } 100 if (topology_split_data_.back().source_symbol_id != encoder_symbol_id) { 101 return false; 102 } 103 *out_face_edge = 104 static_cast<EdgeFaceName>(topology_split_data_.back().source_edge); 105 *out_encoder_split_symbol_id = topology_split_data_.back().split_symbol_id; 106 // Remove the latest split event. 107 topology_split_data_.pop_back(); 108 return true; 109 } 110 111 // Decodes event data for hole and topology split events and stores them for 112 // future use. 113 // Returns the number of parsed bytes, or -1 on error. 114 int32_t DecodeHoleAndTopologySplitEvents(DecoderBuffer *decoder_buffer); 115 116 // Decodes all non-position attribute connectivity on the currently 117 // processed face. 118 #ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED 119 bool DecodeAttributeConnectivitiesOnFaceLegacy(CornerIndex corner); 120 #endif 121 bool DecodeAttributeConnectivitiesOnFace(CornerIndex corner); 122 123 // Initializes mapping between corners and point ids. 124 bool AssignPointsToCorners(int num_connectivity_verts); 125 IsFaceVisited(CornerIndex corner_id)126 bool IsFaceVisited(CornerIndex corner_id) const { 127 if (corner_id < 0) { 128 return true; // Invalid corner signalizes that the face does not exist. 129 } 130 return visited_faces_[corner_table_->Face(corner_id).value()]; 131 } 132 SetOppositeCorners(CornerIndex corner_0,CornerIndex corner_1)133 void SetOppositeCorners(CornerIndex corner_0, CornerIndex corner_1) { 134 corner_table_->SetOppositeCorner(corner_0, corner_1); 135 corner_table_->SetOppositeCorner(corner_1, corner_0); 136 } 137 138 MeshEdgebreakerDecoder *decoder_; 139 140 std::unique_ptr<CornerTable> corner_table_; 141 142 // Stack used for storing corners that need to be traversed when decoding 143 // mesh vertices. New corner is added for each initial face and a split 144 // symbol, and one corner is removed when the end symbol is reached. 145 // Stored as member variable to prevent frequent memory reallocations when 146 // handling meshes with lots of disjoint components. Originally, we used 147 // recursive functions to handle this behavior, but that can cause stack 148 // memory overflow when compressing huge meshes. 149 std::vector<CornerIndex> corner_traversal_stack_; 150 151 // Array stores the number of visited visited for each mesh traversal. 152 std::vector<int> vertex_traversal_length_; 153 154 // List of decoded topology split events. 155 std::vector<TopologySplitEventData> topology_split_data_; 156 157 // List of decoded hole events. 158 std::vector<HoleEventData> hole_event_data_; 159 160 // Configuration of the initial face for each mesh component. 161 std::vector<bool> init_face_configurations_; 162 163 // Initial corner for each traversal. 164 std::vector<CornerIndex> init_corners_; 165 166 // Id of the last processed input symbol. 167 int last_symbol_id_; 168 169 // Id of the last decoded vertex. 170 int last_vert_id_; 171 172 // Id of the last decoded face. 173 int last_face_id_; 174 175 // Array for marking visited faces. 176 std::vector<bool> visited_faces_; 177 // Array for marking visited vertices. 178 std::vector<bool> visited_verts_; 179 // Array for marking vertices on open boundaries. 180 std::vector<bool> is_vert_hole_; 181 182 // The number of new vertices added by the encoder (because of non-manifold 183 // vertices on the input mesh). 184 // If there are no non-manifold edges/vertices on the input mesh, this should 185 // be 0. 186 int num_new_vertices_; 187 // For every newly added vertex, this array stores it's mapping to the 188 // parent vertex id of the encoded mesh. 189 std::unordered_map<int, int> new_to_parent_vertex_map_; 190 // The number of vertices that were encoded (can be different from the number 191 // of vertices of the input mesh). 192 int num_encoded_vertices_; 193 194 // Array for storing the encoded corner ids in the order their associated 195 // vertices were decoded. 196 std::vector<int32_t> processed_corner_ids_; 197 198 // Array storing corners in the order they were visited during the 199 // connectivity decoding (always storing the tip corner of each newly visited 200 // face). 201 std::vector<int> processed_connectivity_corners_; 202 203 MeshAttributeIndicesEncodingData pos_encoding_data_; 204 205 // Id of an attributes decoder that uses |pos_encoding_data_|. 206 int pos_data_decoder_id_; 207 208 // Data for non-position attributes used by the decoder. 209 struct AttributeData { AttributeDataAttributeData210 AttributeData() : decoder_id(-1), is_connectivity_used(true) {} 211 // Id of the attribute decoder that was used to decode this attribute data. 212 int decoder_id; 213 MeshAttributeCornerTable connectivity_data; 214 // Flag that can mark the connectivity_data invalid. In such case the base 215 // corner table of the mesh should be used instead. 216 bool is_connectivity_used; 217 MeshAttributeIndicesEncodingData encoding_data; 218 // Opposite corners to attribute seam edges. 219 std::vector<int32_t> attribute_seam_corners; 220 }; 221 std::vector<AttributeData> attribute_data_; 222 223 TraversalDecoderT traversal_decoder_; 224 }; 225 226 } // namespace draco 227 228 #endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_DECODER_IMPL_H_ 229