Coverage Report

Created: 2024-09-08 06:47

/src/draco/src/draco/compression/mesh/mesh_edgebreaker_decoder_impl.cc
Line
Count
Source (jump to first uncovered line)
1
// Copyright 2016 The Draco Authors.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//      http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14
//
15
#include "draco/compression/mesh/mesh_edgebreaker_decoder_impl.h"
16
17
#include <algorithm>
18
#include <cstdint>
19
20
#include "draco/compression/attributes/sequential_attribute_decoders_controller.h"
21
#include "draco/compression/mesh/mesh_edgebreaker_decoder.h"
22
#include "draco/compression/mesh/mesh_edgebreaker_traversal_predictive_decoder.h"
23
#include "draco/compression/mesh/mesh_edgebreaker_traversal_valence_decoder.h"
24
#include "draco/compression/mesh/traverser/depth_first_traverser.h"
25
#include "draco/compression/mesh/traverser/max_prediction_degree_traverser.h"
26
#include "draco/compression/mesh/traverser/mesh_attribute_indices_encoding_observer.h"
27
#include "draco/compression/mesh/traverser/mesh_traversal_sequencer.h"
28
#include "draco/compression/mesh/traverser/traverser_base.h"
29
#include "draco/mesh/corner_table_iterators.h"
30
31
namespace draco {
32
33
// Types of "free" edges that are used during topology decoding.
34
// A free edge is an edge that is connected to one face only.
35
// All edge types are stored in the opposite_corner_id_ array, where each
36
// edge "e" is uniquely identified by the opposite corner "C" in its parent
37
// triangle:
38
//          *
39
//         /C\
40
//        /   \
41
//       /  e  \
42
//      *-------*
43
// For more description about how the edges are used, see comment inside
44
// ZipConnectivity() method.
45
46
template <class TraversalDecoder>
47
MeshEdgebreakerDecoderImpl<TraversalDecoder>::MeshEdgebreakerDecoderImpl()
48
    : decoder_(nullptr),
49
      last_symbol_id_(-1),
50
      last_vert_id_(-1),
51
      last_face_id_(-1),
52
      num_new_vertices_(0),
53
      num_encoded_vertices_(0),
54
847
      pos_data_decoder_id_(-1) {}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::MeshEdgebreakerDecoderImpl()
Line
Count
Source
54
312
      pos_data_decoder_id_(-1) {}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::MeshEdgebreakerDecoderImpl()
Line
Count
Source
54
187
      pos_data_decoder_id_(-1) {}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::MeshEdgebreakerDecoderImpl()
Line
Count
Source
54
348
      pos_data_decoder_id_(-1) {}
55
56
template <class TraversalDecoder>
57
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::Init(
58
847
    MeshEdgebreakerDecoder *decoder) {
59
847
  decoder_ = decoder;
60
847
  return true;
61
847
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::Init(draco::MeshEdgebreakerDecoder*)
Line
Count
Source
58
312
    MeshEdgebreakerDecoder *decoder) {
59
312
  decoder_ = decoder;
60
312
  return true;
61
312
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::Init(draco::MeshEdgebreakerDecoder*)
Line
Count
Source
58
187
    MeshEdgebreakerDecoder *decoder) {
59
187
  decoder_ = decoder;
60
187
  return true;
61
187
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::Init(draco::MeshEdgebreakerDecoder*)
Line
Count
Source
58
348
    MeshEdgebreakerDecoder *decoder) {
59
348
  decoder_ = decoder;
60
348
  return true;
61
348
}
62
63
template <class TraversalDecoder>
64
const MeshAttributeCornerTable *
65
MeshEdgebreakerDecoderImpl<TraversalDecoder>::GetAttributeCornerTable(
66
517
    int att_id) const {
67
634
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
68
426
    const int decoder_id = attribute_data_[i].decoder_id;
69
426
    if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) {
70
115
      continue;
71
115
    }
72
311
    const AttributesDecoderInterface *const dec =
73
311
        decoder_->attributes_decoder(decoder_id);
74
978
    for (int j = 0; j < dec->GetNumAttributes(); ++j) {
75
976
      if (dec->GetAttributeId(j) == att_id) {
76
309
        if (attribute_data_[i].is_connectivity_used) {
77
201
          return &attribute_data_[i].connectivity_data;
78
201
        }
79
108
        return nullptr;
80
309
      }
81
976
    }
82
311
  }
83
208
  return nullptr;
84
517
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::GetAttributeCornerTable(int) const
Line
Count
Source
66
206
    int att_id) const {
67
251
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
68
223
    const int decoder_id = attribute_data_[i].decoder_id;
69
223
    if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) {
70
45
      continue;
71
45
    }
72
178
    const AttributesDecoderInterface *const dec =
73
178
        decoder_->attributes_decoder(decoder_id);
74
721
    for (int j = 0; j < dec->GetNumAttributes(); ++j) {
75
721
      if (dec->GetAttributeId(j) == att_id) {
76
178
        if (attribute_data_[i].is_connectivity_used) {
77
107
          return &attribute_data_[i].connectivity_data;
78
107
        }
79
71
        return nullptr;
80
178
      }
81
721
    }
82
178
  }
83
28
  return nullptr;
84
206
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::GetAttributeCornerTable(int) const
Line
Count
Source
66
188
    int att_id) const {
67
241
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
68
178
    const int decoder_id = attribute_data_[i].decoder_id;
69
178
    if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) {
70
51
      continue;
71
51
    }
72
127
    const AttributesDecoderInterface *const dec =
73
127
        decoder_->attributes_decoder(decoder_id);
74
251
    for (int j = 0; j < dec->GetNumAttributes(); ++j) {
75
249
      if (dec->GetAttributeId(j) == att_id) {
76
125
        if (attribute_data_[i].is_connectivity_used) {
77
89
          return &attribute_data_[i].connectivity_data;
78
89
        }
79
36
        return nullptr;
80
125
      }
81
249
    }
82
127
  }
83
63
  return nullptr;
84
188
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::GetAttributeCornerTable(int) const
Line
Count
Source
66
123
    int att_id) const {
67
142
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
68
25
    const int decoder_id = attribute_data_[i].decoder_id;
69
25
    if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) {
70
19
      continue;
71
19
    }
72
6
    const AttributesDecoderInterface *const dec =
73
6
        decoder_->attributes_decoder(decoder_id);
74
6
    for (int j = 0; j < dec->GetNumAttributes(); ++j) {
75
6
      if (dec->GetAttributeId(j) == att_id) {
76
6
        if (attribute_data_[i].is_connectivity_used) {
77
5
          return &attribute_data_[i].connectivity_data;
78
5
        }
79
1
        return nullptr;
80
6
      }
81
6
    }
82
6
  }
83
117
  return nullptr;
84
123
}
85
86
template <class TraversalDecoder>
87
const MeshAttributeIndicesEncodingData *
88
MeshEdgebreakerDecoderImpl<TraversalDecoder>::GetAttributeEncodingData(
89
517
    int att_id) const {
90
634
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
91
426
    const int decoder_id = attribute_data_[i].decoder_id;
92
426
    if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) {
93
115
      continue;
94
115
    }
95
311
    const AttributesDecoderInterface *const dec =
96
311
        decoder_->attributes_decoder(decoder_id);
97
978
    for (int j = 0; j < dec->GetNumAttributes(); ++j) {
98
976
      if (dec->GetAttributeId(j) == att_id) {
99
309
        return &attribute_data_[i].encoding_data;
100
309
      }
101
976
    }
102
311
  }
103
208
  return &pos_encoding_data_;
104
517
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::GetAttributeEncodingData(int) const
Line
Count
Source
89
206
    int att_id) const {
90
251
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
91
223
    const int decoder_id = attribute_data_[i].decoder_id;
92
223
    if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) {
93
45
      continue;
94
45
    }
95
178
    const AttributesDecoderInterface *const dec =
96
178
        decoder_->attributes_decoder(decoder_id);
97
721
    for (int j = 0; j < dec->GetNumAttributes(); ++j) {
98
721
      if (dec->GetAttributeId(j) == att_id) {
99
178
        return &attribute_data_[i].encoding_data;
100
178
      }
101
721
    }
102
178
  }
103
28
  return &pos_encoding_data_;
104
206
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::GetAttributeEncodingData(int) const
Line
Count
Source
89
188
    int att_id) const {
90
241
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
91
178
    const int decoder_id = attribute_data_[i].decoder_id;
92
178
    if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) {
93
51
      continue;
94
51
    }
95
127
    const AttributesDecoderInterface *const dec =
96
127
        decoder_->attributes_decoder(decoder_id);
97
251
    for (int j = 0; j < dec->GetNumAttributes(); ++j) {
98
249
      if (dec->GetAttributeId(j) == att_id) {
99
125
        return &attribute_data_[i].encoding_data;
100
125
      }
101
249
    }
102
127
  }
103
63
  return &pos_encoding_data_;
104
188
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::GetAttributeEncodingData(int) const
Line
Count
Source
89
123
    int att_id) const {
90
142
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
91
25
    const int decoder_id = attribute_data_[i].decoder_id;
92
25
    if (decoder_id < 0 || decoder_id >= decoder_->num_attributes_decoders()) {
93
19
      continue;
94
19
    }
95
6
    const AttributesDecoderInterface *const dec =
96
6
        decoder_->attributes_decoder(decoder_id);
97
6
    for (int j = 0; j < dec->GetNumAttributes(); ++j) {
98
6
      if (dec->GetAttributeId(j) == att_id) {
99
6
        return &attribute_data_[i].encoding_data;
100
6
      }
101
6
    }
102
6
  }
103
117
  return &pos_encoding_data_;
104
123
}
105
106
template <class TraversalDecoder>
107
template <class TraverserT>
108
std::unique_ptr<PointsSequencer>
109
MeshEdgebreakerDecoderImpl<TraversalDecoder>::CreateVertexTraversalSequencer(
110
206
    MeshAttributeIndicesEncodingData *encoding_data) {
111
206
  typedef typename TraverserT::TraversalObserver AttObserver;
112
206
  typedef typename TraverserT::CornerTable CornerTable;
113
114
206
  const Mesh *mesh = decoder_->mesh();
115
206
  std::unique_ptr<MeshTraversalSequencer<TraverserT>> traversal_sequencer(
116
206
      new MeshTraversalSequencer<TraverserT>(mesh, encoding_data));
117
118
206
  AttObserver att_observer(corner_table_.get(), mesh, traversal_sequencer.get(),
119
206
                           encoding_data);
120
121
206
  TraverserT att_traverser;
122
206
  att_traverser.Init(corner_table_.get(), att_observer);
123
124
206
  traversal_sequencer->SetTraverser(att_traverser);
125
206
  return std::move(traversal_sequencer);
126
206
}
std::__1::unique_ptr<draco::PointsSequencer, std::__1::default_delete<draco::PointsSequencer> > draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::CreateVertexTraversalSequencer<draco::MaxPredictionDegreeTraverser<draco::CornerTable, draco::MeshAttributeIndicesEncodingObserver<draco::CornerTable> > >(draco::MeshAttributeIndicesEncodingData*)
Line
Count
Source
110
9
    MeshAttributeIndicesEncodingData *encoding_data) {
111
9
  typedef typename TraverserT::TraversalObserver AttObserver;
112
9
  typedef typename TraverserT::CornerTable CornerTable;
113
114
9
  const Mesh *mesh = decoder_->mesh();
115
9
  std::unique_ptr<MeshTraversalSequencer<TraverserT>> traversal_sequencer(
116
9
      new MeshTraversalSequencer<TraverserT>(mesh, encoding_data));
117
118
9
  AttObserver att_observer(corner_table_.get(), mesh, traversal_sequencer.get(),
119
9
                           encoding_data);
120
121
9
  TraverserT att_traverser;
122
9
  att_traverser.Init(corner_table_.get(), att_observer);
123
124
9
  traversal_sequencer->SetTraverser(att_traverser);
125
9
  return std::move(traversal_sequencer);
126
9
}
std::__1::unique_ptr<draco::PointsSequencer, std::__1::default_delete<draco::PointsSequencer> > draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::CreateVertexTraversalSequencer<draco::DepthFirstTraverser<draco::CornerTable, draco::MeshAttributeIndicesEncodingObserver<draco::CornerTable> > >(draco::MeshAttributeIndicesEncodingData*)
Line
Count
Source
110
75
    MeshAttributeIndicesEncodingData *encoding_data) {
111
75
  typedef typename TraverserT::TraversalObserver AttObserver;
112
75
  typedef typename TraverserT::CornerTable CornerTable;
113
114
75
  const Mesh *mesh = decoder_->mesh();
115
75
  std::unique_ptr<MeshTraversalSequencer<TraverserT>> traversal_sequencer(
116
75
      new MeshTraversalSequencer<TraverserT>(mesh, encoding_data));
117
118
75
  AttObserver att_observer(corner_table_.get(), mesh, traversal_sequencer.get(),
119
75
                           encoding_data);
120
121
75
  TraverserT att_traverser;
122
75
  att_traverser.Init(corner_table_.get(), att_observer);
123
124
75
  traversal_sequencer->SetTraverser(att_traverser);
125
75
  return std::move(traversal_sequencer);
126
75
}
std::__1::unique_ptr<draco::PointsSequencer, std::__1::default_delete<draco::PointsSequencer> > draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::CreateVertexTraversalSequencer<draco::MaxPredictionDegreeTraverser<draco::CornerTable, draco::MeshAttributeIndicesEncodingObserver<draco::CornerTable> > >(draco::MeshAttributeIndicesEncodingData*)
Line
Count
Source
110
6
    MeshAttributeIndicesEncodingData *encoding_data) {
111
6
  typedef typename TraverserT::TraversalObserver AttObserver;
112
6
  typedef typename TraverserT::CornerTable CornerTable;
113
114
6
  const Mesh *mesh = decoder_->mesh();
115
6
  std::unique_ptr<MeshTraversalSequencer<TraverserT>> traversal_sequencer(
116
6
      new MeshTraversalSequencer<TraverserT>(mesh, encoding_data));
117
118
6
  AttObserver att_observer(corner_table_.get(), mesh, traversal_sequencer.get(),
119
6
                           encoding_data);
120
121
6
  TraverserT att_traverser;
122
6
  att_traverser.Init(corner_table_.get(), att_observer);
123
124
6
  traversal_sequencer->SetTraverser(att_traverser);
125
6
  return std::move(traversal_sequencer);
126
6
}
std::__1::unique_ptr<draco::PointsSequencer, std::__1::default_delete<draco::PointsSequencer> > draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::CreateVertexTraversalSequencer<draco::DepthFirstTraverser<draco::CornerTable, draco::MeshAttributeIndicesEncodingObserver<draco::CornerTable> > >(draco::MeshAttributeIndicesEncodingData*)
Line
Count
Source
110
52
    MeshAttributeIndicesEncodingData *encoding_data) {
111
52
  typedef typename TraverserT::TraversalObserver AttObserver;
112
52
  typedef typename TraverserT::CornerTable CornerTable;
113
114
52
  const Mesh *mesh = decoder_->mesh();
115
52
  std::unique_ptr<MeshTraversalSequencer<TraverserT>> traversal_sequencer(
116
52
      new MeshTraversalSequencer<TraverserT>(mesh, encoding_data));
117
118
52
  AttObserver att_observer(corner_table_.get(), mesh, traversal_sequencer.get(),
119
52
                           encoding_data);
120
121
52
  TraverserT att_traverser;
122
52
  att_traverser.Init(corner_table_.get(), att_observer);
123
124
52
  traversal_sequencer->SetTraverser(att_traverser);
125
52
  return std::move(traversal_sequencer);
126
52
}
std::__1::unique_ptr<draco::PointsSequencer, std::__1::default_delete<draco::PointsSequencer> > draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::CreateVertexTraversalSequencer<draco::MaxPredictionDegreeTraverser<draco::CornerTable, draco::MeshAttributeIndicesEncodingObserver<draco::CornerTable> > >(draco::MeshAttributeIndicesEncodingData*)
Line
Count
Source
110
17
    MeshAttributeIndicesEncodingData *encoding_data) {
111
17
  typedef typename TraverserT::TraversalObserver AttObserver;
112
17
  typedef typename TraverserT::CornerTable CornerTable;
113
114
17
  const Mesh *mesh = decoder_->mesh();
115
17
  std::unique_ptr<MeshTraversalSequencer<TraverserT>> traversal_sequencer(
116
17
      new MeshTraversalSequencer<TraverserT>(mesh, encoding_data));
117
118
17
  AttObserver att_observer(corner_table_.get(), mesh, traversal_sequencer.get(),
119
17
                           encoding_data);
120
121
17
  TraverserT att_traverser;
122
17
  att_traverser.Init(corner_table_.get(), att_observer);
123
124
17
  traversal_sequencer->SetTraverser(att_traverser);
125
17
  return std::move(traversal_sequencer);
126
17
}
std::__1::unique_ptr<draco::PointsSequencer, std::__1::default_delete<draco::PointsSequencer> > draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::CreateVertexTraversalSequencer<draco::DepthFirstTraverser<draco::CornerTable, draco::MeshAttributeIndicesEncodingObserver<draco::CornerTable> > >(draco::MeshAttributeIndicesEncodingData*)
Line
Count
Source
110
47
    MeshAttributeIndicesEncodingData *encoding_data) {
111
47
  typedef typename TraverserT::TraversalObserver AttObserver;
112
47
  typedef typename TraverserT::CornerTable CornerTable;
113
114
47
  const Mesh *mesh = decoder_->mesh();
115
47
  std::unique_ptr<MeshTraversalSequencer<TraverserT>> traversal_sequencer(
116
47
      new MeshTraversalSequencer<TraverserT>(mesh, encoding_data));
117
118
47
  AttObserver att_observer(corner_table_.get(), mesh, traversal_sequencer.get(),
119
47
                           encoding_data);
120
121
47
  TraverserT att_traverser;
122
47
  att_traverser.Init(corner_table_.get(), att_observer);
123
124
47
  traversal_sequencer->SetTraverser(att_traverser);
125
47
  return std::move(traversal_sequencer);
126
47
}
127
128
template <class TraversalDecoder>
129
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::CreateAttributesDecoder(
130
417
    int32_t att_decoder_id) {
131
417
  int8_t att_data_id;
132
417
  if (!decoder_->buffer()->Decode(&att_data_id)) {
133
1
    return false;
134
1
  }
135
416
  uint8_t decoder_type;
136
416
  if (!decoder_->buffer()->Decode(&decoder_type)) {
137
0
    return false;
138
0
  }
139
140
416
  if (att_data_id >= 0) {
141
282
    if (att_data_id >= attribute_data_.size()) {
142
22
      return false;  // Unexpected attribute data.
143
22
    }
144
145
    // Ensure that the attribute data is not mapped to a different attributes
146
    // decoder already.
147
260
    if (attribute_data_[att_data_id].decoder_id >= 0) {
148
1
      return false;
149
1
    }
150
151
259
    attribute_data_[att_data_id].decoder_id = att_decoder_id;
152
259
  } else {
153
    // Assign the attributes decoder to |pos_encoding_data_|.
154
134
    if (pos_data_decoder_id_ >= 0) {
155
1
      return false;  // Some other decoder is already using the data. Error.
156
1
    }
157
133
    pos_data_decoder_id_ = att_decoder_id;
158
133
  }
159
160
392
  MeshTraversalMethod traversal_method = MESH_TRAVERSAL_DEPTH_FIRST;
161
392
  if (decoder_->bitstream_version() >= DRACO_BITSTREAM_VERSION(1, 2)) {
162
391
    uint8_t traversal_method_encoded;
163
391
    if (!decoder_->buffer()->Decode(&traversal_method_encoded)) {
164
0
      return false;
165
0
    }
166
    // Check that decoded traversal method is valid.
167
391
    if (traversal_method_encoded >= NUM_TRAVERSAL_METHODS) {
168
9
      return false;
169
9
    }
170
382
    traversal_method =
171
382
        static_cast<MeshTraversalMethod>(traversal_method_encoded);
172
382
  }
173
174
383
  const Mesh *mesh = decoder_->mesh();
175
383
  std::unique_ptr<PointsSequencer> sequencer;
176
177
383
  if (decoder_type == MESH_VERTEX_ATTRIBUTE) {
178
    // Per-vertex attribute decoder.
179
180
206
    MeshAttributeIndicesEncodingData *encoding_data = nullptr;
181
206
    if (att_data_id < 0) {
182
126
      encoding_data = &pos_encoding_data_;
183
126
    } else {
184
80
      encoding_data = &attribute_data_[att_data_id].encoding_data;
185
      // Mark the attribute connectivity data invalid to ensure it's not used
186
      // later on.
187
80
      attribute_data_[att_data_id].is_connectivity_used = false;
188
80
    }
189
    // Defining sequencer via a traversal scheme.
190
206
    if (traversal_method == MESH_TRAVERSAL_PREDICTION_DEGREE) {
191
32
      typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver;
192
32
      typedef MaxPredictionDegreeTraverser<CornerTable, AttObserver>
193
32
          AttTraverser;
194
32
      sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data);
195
174
    } else if (traversal_method == MESH_TRAVERSAL_DEPTH_FIRST) {
196
174
      typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver;
197
174
      typedef DepthFirstTraverser<CornerTable, AttObserver> AttTraverser;
198
174
      sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data);
199
174
    } else {
200
0
      return false;  // Unsupported method
201
0
    }
202
206
  } else {
203
177
    if (traversal_method != MESH_TRAVERSAL_DEPTH_FIRST) {
204
5
      return false;  // Unsupported method.
205
5
    }
206
172
    if (att_data_id < 0) {
207
1
      return false;  // Attribute data must be specified.
208
1
    }
209
210
    // Per-corner attribute decoder.
211
212
171
    typedef MeshAttributeIndicesEncodingObserver<MeshAttributeCornerTable>
213
171
        AttObserver;
214
171
    typedef DepthFirstTraverser<MeshAttributeCornerTable, AttObserver>
215
171
        AttTraverser;
216
217
171
    MeshAttributeIndicesEncodingData *const encoding_data =
218
171
        &attribute_data_[att_data_id].encoding_data;
219
171
    const MeshAttributeCornerTable *const corner_table =
220
171
        &attribute_data_[att_data_id].connectivity_data;
221
222
171
    std::unique_ptr<MeshTraversalSequencer<AttTraverser>> traversal_sequencer(
223
171
        new MeshTraversalSequencer<AttTraverser>(mesh, encoding_data));
224
225
171
    AttObserver att_observer(corner_table, mesh, traversal_sequencer.get(),
226
171
                             encoding_data);
227
228
171
    AttTraverser att_traverser;
229
171
    att_traverser.Init(corner_table, att_observer);
230
231
171
    traversal_sequencer->SetTraverser(att_traverser);
232
171
    sequencer = std::move(traversal_sequencer);
233
171
  }
234
235
377
  if (!sequencer) {
236
0
    return false;
237
0
  }
238
239
377
  std::unique_ptr<SequentialAttributeDecodersController> att_controller(
240
377
      new SequentialAttributeDecodersController(std::move(sequencer)));
241
242
377
  return decoder_->SetAttributesDecoder(att_decoder_id,
243
377
                                        std::move(att_controller));
244
377
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::CreateAttributesDecoder(int)
Line
Count
Source
130
212
    int32_t att_decoder_id) {
131
212
  int8_t att_data_id;
132
212
  if (!decoder_->buffer()->Decode(&att_data_id)) {
133
1
    return false;
134
1
  }
135
211
  uint8_t decoder_type;
136
211
  if (!decoder_->buffer()->Decode(&decoder_type)) {
137
0
    return false;
138
0
  }
139
140
211
  if (att_data_id >= 0) {
141
179
    if (att_data_id >= attribute_data_.size()) {
142
18
      return false;  // Unexpected attribute data.
143
18
    }
144
145
    // Ensure that the attribute data is not mapped to a different attributes
146
    // decoder already.
147
161
    if (attribute_data_[att_data_id].decoder_id >= 0) {
148
0
      return false;
149
0
    }
150
151
161
    attribute_data_[att_data_id].decoder_id = att_decoder_id;
152
161
  } else {
153
    // Assign the attributes decoder to |pos_encoding_data_|.
154
32
    if (pos_data_decoder_id_ >= 0) {
155
0
      return false;  // Some other decoder is already using the data. Error.
156
0
    }
157
32
    pos_data_decoder_id_ = att_decoder_id;
158
32
  }
159
160
193
  MeshTraversalMethod traversal_method = MESH_TRAVERSAL_DEPTH_FIRST;
161
193
  if (decoder_->bitstream_version() >= DRACO_BITSTREAM_VERSION(1, 2)) {
162
192
    uint8_t traversal_method_encoded;
163
192
    if (!decoder_->buffer()->Decode(&traversal_method_encoded)) {
164
0
      return false;
165
0
    }
166
    // Check that decoded traversal method is valid.
167
192
    if (traversal_method_encoded >= NUM_TRAVERSAL_METHODS) {
168
5
      return false;
169
5
    }
170
187
    traversal_method =
171
187
        static_cast<MeshTraversalMethod>(traversal_method_encoded);
172
187
  }
173
174
188
  const Mesh *mesh = decoder_->mesh();
175
188
  std::unique_ptr<PointsSequencer> sequencer;
176
177
188
  if (decoder_type == MESH_VERTEX_ATTRIBUTE) {
178
    // Per-vertex attribute decoder.
179
180
84
    MeshAttributeIndicesEncodingData *encoding_data = nullptr;
181
84
    if (att_data_id < 0) {
182
28
      encoding_data = &pos_encoding_data_;
183
56
    } else {
184
56
      encoding_data = &attribute_data_[att_data_id].encoding_data;
185
      // Mark the attribute connectivity data invalid to ensure it's not used
186
      // later on.
187
56
      attribute_data_[att_data_id].is_connectivity_used = false;
188
56
    }
189
    // Defining sequencer via a traversal scheme.
190
84
    if (traversal_method == MESH_TRAVERSAL_PREDICTION_DEGREE) {
191
9
      typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver;
192
9
      typedef MaxPredictionDegreeTraverser<CornerTable, AttObserver>
193
9
          AttTraverser;
194
9
      sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data);
195
75
    } else if (traversal_method == MESH_TRAVERSAL_DEPTH_FIRST) {
196
75
      typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver;
197
75
      typedef DepthFirstTraverser<CornerTable, AttObserver> AttTraverser;
198
75
      sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data);
199
75
    } else {
200
0
      return false;  // Unsupported method
201
0
    }
202
104
  } else {
203
104
    if (traversal_method != MESH_TRAVERSAL_DEPTH_FIRST) {
204
5
      return false;  // Unsupported method.
205
5
    }
206
99
    if (att_data_id < 0) {
207
1
      return false;  // Attribute data must be specified.
208
1
    }
209
210
    // Per-corner attribute decoder.
211
212
98
    typedef MeshAttributeIndicesEncodingObserver<MeshAttributeCornerTable>
213
98
        AttObserver;
214
98
    typedef DepthFirstTraverser<MeshAttributeCornerTable, AttObserver>
215
98
        AttTraverser;
216
217
98
    MeshAttributeIndicesEncodingData *const encoding_data =
218
98
        &attribute_data_[att_data_id].encoding_data;
219
98
    const MeshAttributeCornerTable *const corner_table =
220
98
        &attribute_data_[att_data_id].connectivity_data;
221
222
98
    std::unique_ptr<MeshTraversalSequencer<AttTraverser>> traversal_sequencer(
223
98
        new MeshTraversalSequencer<AttTraverser>(mesh, encoding_data));
224
225
98
    AttObserver att_observer(corner_table, mesh, traversal_sequencer.get(),
226
98
                             encoding_data);
227
228
98
    AttTraverser att_traverser;
229
98
    att_traverser.Init(corner_table, att_observer);
230
231
98
    traversal_sequencer->SetTraverser(att_traverser);
232
98
    sequencer = std::move(traversal_sequencer);
233
98
  }
234
235
182
  if (!sequencer) {
236
0
    return false;
237
0
  }
238
239
182
  std::unique_ptr<SequentialAttributeDecodersController> att_controller(
240
182
      new SequentialAttributeDecodersController(std::move(sequencer)));
241
242
182
  return decoder_->SetAttributesDecoder(att_decoder_id,
243
182
                                        std::move(att_controller));
244
182
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::CreateAttributesDecoder(int)
Line
Count
Source
130
129
    int32_t att_decoder_id) {
131
129
  int8_t att_data_id;
132
129
  if (!decoder_->buffer()->Decode(&att_data_id)) {
133
0
    return false;
134
0
  }
135
129
  uint8_t decoder_type;
136
129
  if (!decoder_->buffer()->Decode(&decoder_type)) {
137
0
    return false;
138
0
  }
139
140
129
  if (att_data_id >= 0) {
141
92
    if (att_data_id >= attribute_data_.size()) {
142
0
      return false;  // Unexpected attribute data.
143
0
    }
144
145
    // Ensure that the attribute data is not mapped to a different attributes
146
    // decoder already.
147
92
    if (attribute_data_[att_data_id].decoder_id >= 0) {
148
1
      return false;
149
1
    }
150
151
91
    attribute_data_[att_data_id].decoder_id = att_decoder_id;
152
91
  } else {
153
    // Assign the attributes decoder to |pos_encoding_data_|.
154
37
    if (pos_data_decoder_id_ >= 0) {
155
0
      return false;  // Some other decoder is already using the data. Error.
156
0
    }
157
37
    pos_data_decoder_id_ = att_decoder_id;
158
37
  }
159
160
128
  MeshTraversalMethod traversal_method = MESH_TRAVERSAL_DEPTH_FIRST;
161
128
  if (decoder_->bitstream_version() >= DRACO_BITSTREAM_VERSION(1, 2)) {
162
128
    uint8_t traversal_method_encoded;
163
128
    if (!decoder_->buffer()->Decode(&traversal_method_encoded)) {
164
0
      return false;
165
0
    }
166
    // Check that decoded traversal method is valid.
167
128
    if (traversal_method_encoded >= NUM_TRAVERSAL_METHODS) {
168
2
      return false;
169
2
    }
170
126
    traversal_method =
171
126
        static_cast<MeshTraversalMethod>(traversal_method_encoded);
172
126
  }
173
174
126
  const Mesh *mesh = decoder_->mesh();
175
126
  std::unique_ptr<PointsSequencer> sequencer;
176
177
126
  if (decoder_type == MESH_VERTEX_ATTRIBUTE) {
178
    // Per-vertex attribute decoder.
179
180
58
    MeshAttributeIndicesEncodingData *encoding_data = nullptr;
181
58
    if (att_data_id < 0) {
182
36
      encoding_data = &pos_encoding_data_;
183
36
    } else {
184
22
      encoding_data = &attribute_data_[att_data_id].encoding_data;
185
      // Mark the attribute connectivity data invalid to ensure it's not used
186
      // later on.
187
22
      attribute_data_[att_data_id].is_connectivity_used = false;
188
22
    }
189
    // Defining sequencer via a traversal scheme.
190
58
    if (traversal_method == MESH_TRAVERSAL_PREDICTION_DEGREE) {
191
6
      typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver;
192
6
      typedef MaxPredictionDegreeTraverser<CornerTable, AttObserver>
193
6
          AttTraverser;
194
6
      sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data);
195
52
    } else if (traversal_method == MESH_TRAVERSAL_DEPTH_FIRST) {
196
52
      typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver;
197
52
      typedef DepthFirstTraverser<CornerTable, AttObserver> AttTraverser;
198
52
      sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data);
199
52
    } else {
200
0
      return false;  // Unsupported method
201
0
    }
202
68
  } else {
203
68
    if (traversal_method != MESH_TRAVERSAL_DEPTH_FIRST) {
204
0
      return false;  // Unsupported method.
205
0
    }
206
68
    if (att_data_id < 0) {
207
0
      return false;  // Attribute data must be specified.
208
0
    }
209
210
    // Per-corner attribute decoder.
211
212
68
    typedef MeshAttributeIndicesEncodingObserver<MeshAttributeCornerTable>
213
68
        AttObserver;
214
68
    typedef DepthFirstTraverser<MeshAttributeCornerTable, AttObserver>
215
68
        AttTraverser;
216
217
68
    MeshAttributeIndicesEncodingData *const encoding_data =
218
68
        &attribute_data_[att_data_id].encoding_data;
219
68
    const MeshAttributeCornerTable *const corner_table =
220
68
        &attribute_data_[att_data_id].connectivity_data;
221
222
68
    std::unique_ptr<MeshTraversalSequencer<AttTraverser>> traversal_sequencer(
223
68
        new MeshTraversalSequencer<AttTraverser>(mesh, encoding_data));
224
225
68
    AttObserver att_observer(corner_table, mesh, traversal_sequencer.get(),
226
68
                             encoding_data);
227
228
68
    AttTraverser att_traverser;
229
68
    att_traverser.Init(corner_table, att_observer);
230
231
68
    traversal_sequencer->SetTraverser(att_traverser);
232
68
    sequencer = std::move(traversal_sequencer);
233
68
  }
234
235
126
  if (!sequencer) {
236
0
    return false;
237
0
  }
238
239
126
  std::unique_ptr<SequentialAttributeDecodersController> att_controller(
240
126
      new SequentialAttributeDecodersController(std::move(sequencer)));
241
242
126
  return decoder_->SetAttributesDecoder(att_decoder_id,
243
126
                                        std::move(att_controller));
244
126
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::CreateAttributesDecoder(int)
Line
Count
Source
130
76
    int32_t att_decoder_id) {
131
76
  int8_t att_data_id;
132
76
  if (!decoder_->buffer()->Decode(&att_data_id)) {
133
0
    return false;
134
0
  }
135
76
  uint8_t decoder_type;
136
76
  if (!decoder_->buffer()->Decode(&decoder_type)) {
137
0
    return false;
138
0
  }
139
140
76
  if (att_data_id >= 0) {
141
11
    if (att_data_id >= attribute_data_.size()) {
142
4
      return false;  // Unexpected attribute data.
143
4
    }
144
145
    // Ensure that the attribute data is not mapped to a different attributes
146
    // decoder already.
147
7
    if (attribute_data_[att_data_id].decoder_id >= 0) {
148
0
      return false;
149
0
    }
150
151
7
    attribute_data_[att_data_id].decoder_id = att_decoder_id;
152
65
  } else {
153
    // Assign the attributes decoder to |pos_encoding_data_|.
154
65
    if (pos_data_decoder_id_ >= 0) {
155
1
      return false;  // Some other decoder is already using the data. Error.
156
1
    }
157
64
    pos_data_decoder_id_ = att_decoder_id;
158
64
  }
159
160
71
  MeshTraversalMethod traversal_method = MESH_TRAVERSAL_DEPTH_FIRST;
161
71
  if (decoder_->bitstream_version() >= DRACO_BITSTREAM_VERSION(1, 2)) {
162
71
    uint8_t traversal_method_encoded;
163
71
    if (!decoder_->buffer()->Decode(&traversal_method_encoded)) {
164
0
      return false;
165
0
    }
166
    // Check that decoded traversal method is valid.
167
71
    if (traversal_method_encoded >= NUM_TRAVERSAL_METHODS) {
168
2
      return false;
169
2
    }
170
69
    traversal_method =
171
69
        static_cast<MeshTraversalMethod>(traversal_method_encoded);
172
69
  }
173
174
69
  const Mesh *mesh = decoder_->mesh();
175
69
  std::unique_ptr<PointsSequencer> sequencer;
176
177
69
  if (decoder_type == MESH_VERTEX_ATTRIBUTE) {
178
    // Per-vertex attribute decoder.
179
180
64
    MeshAttributeIndicesEncodingData *encoding_data = nullptr;
181
64
    if (att_data_id < 0) {
182
62
      encoding_data = &pos_encoding_data_;
183
62
    } else {
184
2
      encoding_data = &attribute_data_[att_data_id].encoding_data;
185
      // Mark the attribute connectivity data invalid to ensure it's not used
186
      // later on.
187
2
      attribute_data_[att_data_id].is_connectivity_used = false;
188
2
    }
189
    // Defining sequencer via a traversal scheme.
190
64
    if (traversal_method == MESH_TRAVERSAL_PREDICTION_DEGREE) {
191
17
      typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver;
192
17
      typedef MaxPredictionDegreeTraverser<CornerTable, AttObserver>
193
17
          AttTraverser;
194
17
      sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data);
195
47
    } else if (traversal_method == MESH_TRAVERSAL_DEPTH_FIRST) {
196
47
      typedef MeshAttributeIndicesEncodingObserver<CornerTable> AttObserver;
197
47
      typedef DepthFirstTraverser<CornerTable, AttObserver> AttTraverser;
198
47
      sequencer = CreateVertexTraversalSequencer<AttTraverser>(encoding_data);
199
47
    } else {
200
0
      return false;  // Unsupported method
201
0
    }
202
64
  } else {
203
5
    if (traversal_method != MESH_TRAVERSAL_DEPTH_FIRST) {
204
0
      return false;  // Unsupported method.
205
0
    }
206
5
    if (att_data_id < 0) {
207
0
      return false;  // Attribute data must be specified.
208
0
    }
209
210
    // Per-corner attribute decoder.
211
212
5
    typedef MeshAttributeIndicesEncodingObserver<MeshAttributeCornerTable>
213
5
        AttObserver;
214
5
    typedef DepthFirstTraverser<MeshAttributeCornerTable, AttObserver>
215
5
        AttTraverser;
216
217
5
    MeshAttributeIndicesEncodingData *const encoding_data =
218
5
        &attribute_data_[att_data_id].encoding_data;
219
5
    const MeshAttributeCornerTable *const corner_table =
220
5
        &attribute_data_[att_data_id].connectivity_data;
221
222
5
    std::unique_ptr<MeshTraversalSequencer<AttTraverser>> traversal_sequencer(
223
5
        new MeshTraversalSequencer<AttTraverser>(mesh, encoding_data));
224
225
5
    AttObserver att_observer(corner_table, mesh, traversal_sequencer.get(),
226
5
                             encoding_data);
227
228
5
    AttTraverser att_traverser;
229
5
    att_traverser.Init(corner_table, att_observer);
230
231
5
    traversal_sequencer->SetTraverser(att_traverser);
232
5
    sequencer = std::move(traversal_sequencer);
233
5
  }
234
235
69
  if (!sequencer) {
236
0
    return false;
237
0
  }
238
239
69
  std::unique_ptr<SequentialAttributeDecodersController> att_controller(
240
69
      new SequentialAttributeDecodersController(std::move(sequencer)));
241
242
69
  return decoder_->SetAttributesDecoder(att_decoder_id,
243
69
                                        std::move(att_controller));
244
69
}
245
246
template <class TraversalDecoder>
247
847
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::DecodeConnectivity() {
248
847
  num_new_vertices_ = 0;
249
847
  new_to_parent_vertex_map_.clear();
250
847
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
251
847
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
252
344
    uint32_t num_new_verts;
253
344
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
254
190
      if (!decoder_->buffer()->Decode(&num_new_verts)) {
255
0
        return false;
256
0
      }
257
190
    } else {
258
154
      if (!DecodeVarint(&num_new_verts, decoder_->buffer())) {
259
0
        return false;
260
0
      }
261
154
    }
262
344
    num_new_vertices_ = num_new_verts;
263
344
  }
264
847
#endif
265
266
847
  uint32_t num_encoded_vertices;
267
847
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
268
847
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
269
190
    if (!decoder_->buffer()->Decode(&num_encoded_vertices)) {
270
0
      return false;
271
0
    }
272
273
190
  } else
274
657
#endif
275
657
  {
276
657
    if (!DecodeVarint(&num_encoded_vertices, decoder_->buffer())) {
277
0
      return false;
278
0
    }
279
657
  }
280
847
  num_encoded_vertices_ = num_encoded_vertices;
281
282
847
  uint32_t num_faces;
283
847
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
284
847
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
285
190
    if (!decoder_->buffer()->Decode(&num_faces)) {
286
0
      return false;
287
0
    }
288
289
190
  } else
290
657
#endif
291
657
  {
292
657
    if (!DecodeVarint(&num_faces, decoder_->buffer())) {
293
0
      return false;
294
0
    }
295
657
  }
296
847
  if (num_faces > std::numeric_limits<CornerIndex::ValueType>::max() / 3) {
297
0
    return false;  // Draco cannot handle this many faces.
298
0
  }
299
300
847
  if (static_cast<uint32_t>(num_encoded_vertices_) > num_faces * 3) {
301
3
    return false;  // There cannot be more vertices than 3 * num_faces.
302
3
  }
303
304
  // Minimum number of edges of the mesh assuming each edge is shared between
305
  // two faces.
306
844
  const uint32_t min_num_face_edges = 3 * num_faces / 2;
307
308
  // Maximum number of edges that can exist between |num_encoded_vertices_|.
309
  // This is based on graph theory assuming simple connected graph.
310
844
  const uint64_t num_encoded_vertices_64 =
311
844
      static_cast<uint64_t>(num_encoded_vertices_);
312
844
  const uint64_t max_num_vertex_edges =
313
844
      num_encoded_vertices_64 * (num_encoded_vertices_64 - 1) / 2;
314
844
  if (max_num_vertex_edges < min_num_face_edges) {
315
    // It is impossible to construct a manifold mesh with these properties.
316
0
    return false;
317
0
  }
318
319
844
  uint8_t num_attribute_data;
320
844
  if (!decoder_->buffer()->Decode(&num_attribute_data)) {
321
0
    return false;
322
0
  }
323
324
844
  uint32_t num_encoded_symbols;
325
844
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
326
844
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
327
187
    if (!decoder_->buffer()->Decode(&num_encoded_symbols)) {
328
0
      return false;
329
0
    }
330
331
187
  } else
332
657
#endif
333
657
  {
334
657
    if (!DecodeVarint(&num_encoded_symbols, decoder_->buffer())) {
335
0
      return false;
336
0
    }
337
657
  }
338
339
844
  if (num_faces < num_encoded_symbols) {
340
    // Number of faces needs to be the same or greater than the number of
341
    // symbols (it can be greater because the initial face may not be encoded as
342
    // a symbol).
343
5
    return false;
344
5
  }
345
839
  const uint32_t max_encoded_faces =
346
839
      num_encoded_symbols + (num_encoded_symbols / 3);
347
839
  if (num_faces > max_encoded_faces) {
348
    // Faces can only be 1 1/3 times bigger than number of encoded symbols. This
349
    // could only happen if all new encoded components started with interior
350
    // triangles. E.g. A mesh with multiple tetrahedrons.
351
2
    return false;
352
2
  }
353
354
837
  uint32_t num_encoded_split_symbols;
355
837
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
356
837
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
357
182
    if (!decoder_->buffer()->Decode(&num_encoded_split_symbols)) {
358
0
      return false;
359
0
    }
360
361
182
  } else
362
655
#endif
363
655
  {
364
655
    if (!DecodeVarint(&num_encoded_split_symbols, decoder_->buffer())) {
365
0
      return false;
366
0
    }
367
655
  }
368
369
837
  if (num_encoded_split_symbols > num_encoded_symbols) {
370
4
    return false;  // Split symbols are a sub-set of all symbols.
371
4
  }
372
373
  // Decode topology (connectivity).
374
833
  vertex_traversal_length_.clear();
375
833
  corner_table_ = std::unique_ptr<CornerTable>(new CornerTable());
376
833
  if (corner_table_ == nullptr) {
377
0
    return false;
378
0
  }
379
833
  processed_corner_ids_.clear();
380
833
  processed_corner_ids_.reserve(num_faces);
381
833
  processed_connectivity_corners_.clear();
382
833
  processed_connectivity_corners_.reserve(num_faces);
383
833
  topology_split_data_.clear();
384
833
  hole_event_data_.clear();
385
833
  init_face_configurations_.clear();
386
833
  init_corners_.clear();
387
388
833
  last_symbol_id_ = -1;
389
833
  last_face_id_ = -1;
390
833
  last_vert_id_ = -1;
391
392
833
  attribute_data_.clear();
393
  // Add one attribute data for each attribute decoder.
394
833
  attribute_data_.resize(num_attribute_data);
395
396
833
  if (!corner_table_->Reset(
397
833
          num_faces, num_encoded_vertices_ + num_encoded_split_symbols)) {
398
0
    return false;
399
0
  }
400
401
  // Start with all vertices marked as holes (boundaries).
402
  // Only vertices decoded with TOPOLOGY_C symbol (and the initial face) will
403
  // be marked as non hole vertices. We need to allocate the array larger
404
  // because split symbols can create extra vertices during the decoding
405
  // process (these extra vertices are then eliminated during deduplication).
406
833
  is_vert_hole_.assign(num_encoded_vertices_ + num_encoded_split_symbols, true);
407
408
833
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
409
833
  int32_t topology_split_decoded_bytes = -1;
410
833
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
411
333
    uint32_t encoded_connectivity_size;
412
333
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
413
180
      if (!decoder_->buffer()->Decode(&encoded_connectivity_size)) {
414
0
        return false;
415
0
      }
416
180
    } else {
417
153
      if (!DecodeVarint(&encoded_connectivity_size, decoder_->buffer())) {
418
0
        return false;
419
0
      }
420
153
    }
421
333
    if (encoded_connectivity_size == 0 ||
422
333
        encoded_connectivity_size > decoder_->buffer()->remaining_size()) {
423
9
      return false;
424
9
    }
425
324
    DecoderBuffer event_buffer;
426
324
    event_buffer.Init(
427
324
        decoder_->buffer()->data_head() + encoded_connectivity_size,
428
324
        decoder_->buffer()->remaining_size() - encoded_connectivity_size,
429
324
        decoder_->buffer()->bitstream_version());
430
    // Decode hole and topology split events.
431
324
    topology_split_decoded_bytes =
432
324
        DecodeHoleAndTopologySplitEvents(&event_buffer);
433
324
    if (topology_split_decoded_bytes == -1) {
434
79
      return false;
435
79
    }
436
437
324
  } else
438
500
#endif
439
500
  {
440
500
    if (DecodeHoleAndTopologySplitEvents(decoder_->buffer()) == -1) {
441
2
      return false;
442
2
    }
443
500
  }
444
445
743
  traversal_decoder_.Init(this);
446
  // Add one extra vertex for each split symbol.
447
743
  traversal_decoder_.SetNumEncodedVertices(num_encoded_vertices_ +
448
743
                                           num_encoded_split_symbols);
449
743
  traversal_decoder_.SetNumAttributeData(num_attribute_data);
450
451
743
  DecoderBuffer traversal_end_buffer;
452
743
  if (!traversal_decoder_.Start(&traversal_end_buffer)) {
453
154
    return false;
454
154
  }
455
456
589
  const int num_connectivity_verts = DecodeConnectivity(num_encoded_symbols);
457
589
  if (num_connectivity_verts == -1) {
458
169
    return false;
459
169
  }
460
461
  // Set the main buffer to the end of the traversal.
462
420
  decoder_->buffer()->Init(traversal_end_buffer.data_head(),
463
420
                           traversal_end_buffer.remaining_size(),
464
420
                           decoder_->buffer()->bitstream_version());
465
466
420
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
467
420
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
468
    // Skip topology split data that was already decoded earlier.
469
115
    decoder_->buffer()->Advance(topology_split_decoded_bytes);
470
115
  }
471
420
#endif
472
473
  // Decode connectivity of non-position attributes.
474
420
  if (!attribute_data_.empty()) {
475
338
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
476
338
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) {
477
163k
      for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) {
478
162k
        if (!DecodeAttributeConnectivitiesOnFaceLegacy(ci)) {
479
0
          return false;
480
0
        }
481
162k
      }
482
483
107
    } else
484
231
#endif
485
231
    {
486
333k
      for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) {
487
333k
        if (!DecodeAttributeConnectivitiesOnFace(ci)) {
488
0
          return false;
489
0
        }
490
333k
      }
491
231
    }
492
338
  }
493
420
  traversal_decoder_.Done();
494
495
  // Decode attribute connectivity.
496
  // Prepare data structure for decoding non-position attribute connectivity.
497
2.07k
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
498
1.65k
    attribute_data_[i].connectivity_data.InitEmpty(corner_table_.get());
499
    // Add all seams.
500
765k
    for (int32_t c : attribute_data_[i].attribute_seam_corners) {
501
765k
      attribute_data_[i].connectivity_data.AddSeamEdge(CornerIndex(c));
502
765k
    }
503
    // Recompute vertices from the newly added seam edges.
504
1.65k
    if (!attribute_data_[i].connectivity_data.RecomputeVertices(nullptr,
505
1.65k
                                                                nullptr)) {
506
0
      return false;
507
0
    }
508
1.65k
  }
509
510
420
  pos_encoding_data_.Init(corner_table_->num_vertices());
511
2.07k
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
512
    // For non-position attributes, preallocate the vertex to value mapping
513
    // using the maximum number of vertices from the base corner table and the
514
    // attribute corner table (since the attribute decoder may use either of
515
    // it).
516
1.65k
    int32_t att_connectivity_verts =
517
1.65k
        attribute_data_[i].connectivity_data.num_vertices();
518
1.65k
    if (att_connectivity_verts < corner_table_->num_vertices()) {
519
173
      att_connectivity_verts = corner_table_->num_vertices();
520
173
    }
521
1.65k
    attribute_data_[i].encoding_data.Init(att_connectivity_verts);
522
1.65k
  }
523
420
  if (!AssignPointsToCorners(num_connectivity_verts)) {
524
1
    return false;
525
1
  }
526
419
  return true;
527
420
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::DecodeConnectivity()
Line
Count
Source
247
312
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::DecodeConnectivity() {
248
312
  num_new_vertices_ = 0;
249
312
  new_to_parent_vertex_map_.clear();
250
312
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
251
312
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
252
46
    uint32_t num_new_verts;
253
46
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
254
33
      if (!decoder_->buffer()->Decode(&num_new_verts)) {
255
0
        return false;
256
0
      }
257
33
    } else {
258
13
      if (!DecodeVarint(&num_new_verts, decoder_->buffer())) {
259
0
        return false;
260
0
      }
261
13
    }
262
46
    num_new_vertices_ = num_new_verts;
263
46
  }
264
312
#endif
265
266
312
  uint32_t num_encoded_vertices;
267
312
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
268
312
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
269
33
    if (!decoder_->buffer()->Decode(&num_encoded_vertices)) {
270
0
      return false;
271
0
    }
272
273
33
  } else
274
279
#endif
275
279
  {
276
279
    if (!DecodeVarint(&num_encoded_vertices, decoder_->buffer())) {
277
0
      return false;
278
0
    }
279
279
  }
280
312
  num_encoded_vertices_ = num_encoded_vertices;
281
282
312
  uint32_t num_faces;
283
312
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
284
312
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
285
33
    if (!decoder_->buffer()->Decode(&num_faces)) {
286
0
      return false;
287
0
    }
288
289
33
  } else
290
279
#endif
291
279
  {
292
279
    if (!DecodeVarint(&num_faces, decoder_->buffer())) {
293
0
      return false;
294
0
    }
295
279
  }
296
312
  if (num_faces > std::numeric_limits<CornerIndex::ValueType>::max() / 3) {
297
0
    return false;  // Draco cannot handle this many faces.
298
0
  }
299
300
312
  if (static_cast<uint32_t>(num_encoded_vertices_) > num_faces * 3) {
301
1
    return false;  // There cannot be more vertices than 3 * num_faces.
302
1
  }
303
304
  // Minimum number of edges of the mesh assuming each edge is shared between
305
  // two faces.
306
311
  const uint32_t min_num_face_edges = 3 * num_faces / 2;
307
308
  // Maximum number of edges that can exist between |num_encoded_vertices_|.
309
  // This is based on graph theory assuming simple connected graph.
310
311
  const uint64_t num_encoded_vertices_64 =
311
311
      static_cast<uint64_t>(num_encoded_vertices_);
312
311
  const uint64_t max_num_vertex_edges =
313
311
      num_encoded_vertices_64 * (num_encoded_vertices_64 - 1) / 2;
314
311
  if (max_num_vertex_edges < min_num_face_edges) {
315
    // It is impossible to construct a manifold mesh with these properties.
316
0
    return false;
317
0
  }
318
319
311
  uint8_t num_attribute_data;
320
311
  if (!decoder_->buffer()->Decode(&num_attribute_data)) {
321
0
    return false;
322
0
  }
323
324
311
  uint32_t num_encoded_symbols;
325
311
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
326
311
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
327
32
    if (!decoder_->buffer()->Decode(&num_encoded_symbols)) {
328
0
      return false;
329
0
    }
330
331
32
  } else
332
279
#endif
333
279
  {
334
279
    if (!DecodeVarint(&num_encoded_symbols, decoder_->buffer())) {
335
0
      return false;
336
0
    }
337
279
  }
338
339
311
  if (num_faces < num_encoded_symbols) {
340
    // Number of faces needs to be the same or greater than the number of
341
    // symbols (it can be greater because the initial face may not be encoded as
342
    // a symbol).
343
2
    return false;
344
2
  }
345
309
  const uint32_t max_encoded_faces =
346
309
      num_encoded_symbols + (num_encoded_symbols / 3);
347
309
  if (num_faces > max_encoded_faces) {
348
    // Faces can only be 1 1/3 times bigger than number of encoded symbols. This
349
    // could only happen if all new encoded components started with interior
350
    // triangles. E.g. A mesh with multiple tetrahedrons.
351
1
    return false;
352
1
  }
353
354
308
  uint32_t num_encoded_split_symbols;
355
308
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
356
308
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
357
30
    if (!decoder_->buffer()->Decode(&num_encoded_split_symbols)) {
358
0
      return false;
359
0
    }
360
361
30
  } else
362
278
#endif
363
278
  {
364
278
    if (!DecodeVarint(&num_encoded_split_symbols, decoder_->buffer())) {
365
0
      return false;
366
0
    }
367
278
  }
368
369
308
  if (num_encoded_split_symbols > num_encoded_symbols) {
370
1
    return false;  // Split symbols are a sub-set of all symbols.
371
1
  }
372
373
  // Decode topology (connectivity).
374
307
  vertex_traversal_length_.clear();
375
307
  corner_table_ = std::unique_ptr<CornerTable>(new CornerTable());
376
307
  if (corner_table_ == nullptr) {
377
0
    return false;
378
0
  }
379
307
  processed_corner_ids_.clear();
380
307
  processed_corner_ids_.reserve(num_faces);
381
307
  processed_connectivity_corners_.clear();
382
307
  processed_connectivity_corners_.reserve(num_faces);
383
307
  topology_split_data_.clear();
384
307
  hole_event_data_.clear();
385
307
  init_face_configurations_.clear();
386
307
  init_corners_.clear();
387
388
307
  last_symbol_id_ = -1;
389
307
  last_face_id_ = -1;
390
307
  last_vert_id_ = -1;
391
392
307
  attribute_data_.clear();
393
  // Add one attribute data for each attribute decoder.
394
307
  attribute_data_.resize(num_attribute_data);
395
396
307
  if (!corner_table_->Reset(
397
307
          num_faces, num_encoded_vertices_ + num_encoded_split_symbols)) {
398
0
    return false;
399
0
  }
400
401
  // Start with all vertices marked as holes (boundaries).
402
  // Only vertices decoded with TOPOLOGY_C symbol (and the initial face) will
403
  // be marked as non hole vertices. We need to allocate the array larger
404
  // because split symbols can create extra vertices during the decoding
405
  // process (these extra vertices are then eliminated during deduplication).
406
307
  is_vert_hole_.assign(num_encoded_vertices_ + num_encoded_split_symbols, true);
407
408
307
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
409
307
  int32_t topology_split_decoded_bytes = -1;
410
307
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
411
42
    uint32_t encoded_connectivity_size;
412
42
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
413
30
      if (!decoder_->buffer()->Decode(&encoded_connectivity_size)) {
414
0
        return false;
415
0
      }
416
30
    } else {
417
12
      if (!DecodeVarint(&encoded_connectivity_size, decoder_->buffer())) {
418
0
        return false;
419
0
      }
420
12
    }
421
42
    if (encoded_connectivity_size == 0 ||
422
42
        encoded_connectivity_size > decoder_->buffer()->remaining_size()) {
423
5
      return false;
424
5
    }
425
37
    DecoderBuffer event_buffer;
426
37
    event_buffer.Init(
427
37
        decoder_->buffer()->data_head() + encoded_connectivity_size,
428
37
        decoder_->buffer()->remaining_size() - encoded_connectivity_size,
429
37
        decoder_->buffer()->bitstream_version());
430
    // Decode hole and topology split events.
431
37
    topology_split_decoded_bytes =
432
37
        DecodeHoleAndTopologySplitEvents(&event_buffer);
433
37
    if (topology_split_decoded_bytes == -1) {
434
29
      return false;
435
29
    }
436
437
37
  } else
438
265
#endif
439
265
  {
440
265
    if (DecodeHoleAndTopologySplitEvents(decoder_->buffer()) == -1) {
441
0
      return false;
442
0
    }
443
265
  }
444
445
273
  traversal_decoder_.Init(this);
446
  // Add one extra vertex for each split symbol.
447
273
  traversal_decoder_.SetNumEncodedVertices(num_encoded_vertices_ +
448
273
                                           num_encoded_split_symbols);
449
273
  traversal_decoder_.SetNumAttributeData(num_attribute_data);
450
451
273
  DecoderBuffer traversal_end_buffer;
452
273
  if (!traversal_decoder_.Start(&traversal_end_buffer)) {
453
10
    return false;
454
10
  }
455
456
263
  const int num_connectivity_verts = DecodeConnectivity(num_encoded_symbols);
457
263
  if (num_connectivity_verts == -1) {
458
51
    return false;
459
51
  }
460
461
  // Set the main buffer to the end of the traversal.
462
212
  decoder_->buffer()->Init(traversal_end_buffer.data_head(),
463
212
                           traversal_end_buffer.remaining_size(),
464
212
                           decoder_->buffer()->bitstream_version());
465
466
212
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
467
212
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
468
    // Skip topology split data that was already decoded earlier.
469
3
    decoder_->buffer()->Advance(topology_split_decoded_bytes);
470
3
  }
471
212
#endif
472
473
  // Decode connectivity of non-position attributes.
474
212
  if (!attribute_data_.empty()) {
475
203
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
476
203
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) {
477
50
      for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) {
478
48
        if (!DecodeAttributeConnectivitiesOnFaceLegacy(ci)) {
479
0
          return false;
480
0
        }
481
48
      }
482
483
2
    } else
484
201
#endif
485
201
    {
486
135k
      for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) {
487
135k
        if (!DecodeAttributeConnectivitiesOnFace(ci)) {
488
0
          return false;
489
0
        }
490
135k
      }
491
201
    }
492
203
  }
493
212
  traversal_decoder_.Done();
494
495
  // Decode attribute connectivity.
496
  // Prepare data structure for decoding non-position attribute connectivity.
497
1.70k
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
498
1.49k
    attribute_data_[i].connectivity_data.InitEmpty(corner_table_.get());
499
    // Add all seams.
500
260k
    for (int32_t c : attribute_data_[i].attribute_seam_corners) {
501
260k
      attribute_data_[i].connectivity_data.AddSeamEdge(CornerIndex(c));
502
260k
    }
503
    // Recompute vertices from the newly added seam edges.
504
1.49k
    if (!attribute_data_[i].connectivity_data.RecomputeVertices(nullptr,
505
1.49k
                                                                nullptr)) {
506
0
      return false;
507
0
    }
508
1.49k
  }
509
510
212
  pos_encoding_data_.Init(corner_table_->num_vertices());
511
1.70k
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
512
    // For non-position attributes, preallocate the vertex to value mapping
513
    // using the maximum number of vertices from the base corner table and the
514
    // attribute corner table (since the attribute decoder may use either of
515
    // it).
516
1.49k
    int32_t att_connectivity_verts =
517
1.49k
        attribute_data_[i].connectivity_data.num_vertices();
518
1.49k
    if (att_connectivity_verts < corner_table_->num_vertices()) {
519
145
      att_connectivity_verts = corner_table_->num_vertices();
520
145
    }
521
1.49k
    attribute_data_[i].encoding_data.Init(att_connectivity_verts);
522
1.49k
  }
523
212
  if (!AssignPointsToCorners(num_connectivity_verts)) {
524
1
    return false;
525
1
  }
526
211
  return true;
527
212
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::DecodeConnectivity()
Line
Count
Source
247
187
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::DecodeConnectivity() {
248
187
  num_new_vertices_ = 0;
249
187
  new_to_parent_vertex_map_.clear();
250
187
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
251
187
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
252
163
    uint32_t num_new_verts;
253
163
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
254
38
      if (!decoder_->buffer()->Decode(&num_new_verts)) {
255
0
        return false;
256
0
      }
257
125
    } else {
258
125
      if (!DecodeVarint(&num_new_verts, decoder_->buffer())) {
259
0
        return false;
260
0
      }
261
125
    }
262
163
    num_new_vertices_ = num_new_verts;
263
163
  }
264
187
#endif
265
266
187
  uint32_t num_encoded_vertices;
267
187
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
268
187
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
269
38
    if (!decoder_->buffer()->Decode(&num_encoded_vertices)) {
270
0
      return false;
271
0
    }
272
273
38
  } else
274
149
#endif
275
149
  {
276
149
    if (!DecodeVarint(&num_encoded_vertices, decoder_->buffer())) {
277
0
      return false;
278
0
    }
279
149
  }
280
187
  num_encoded_vertices_ = num_encoded_vertices;
281
282
187
  uint32_t num_faces;
283
187
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
284
187
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
285
38
    if (!decoder_->buffer()->Decode(&num_faces)) {
286
0
      return false;
287
0
    }
288
289
38
  } else
290
149
#endif
291
149
  {
292
149
    if (!DecodeVarint(&num_faces, decoder_->buffer())) {
293
0
      return false;
294
0
    }
295
149
  }
296
187
  if (num_faces > std::numeric_limits<CornerIndex::ValueType>::max() / 3) {
297
0
    return false;  // Draco cannot handle this many faces.
298
0
  }
299
300
187
  if (static_cast<uint32_t>(num_encoded_vertices_) > num_faces * 3) {
301
0
    return false;  // There cannot be more vertices than 3 * num_faces.
302
0
  }
303
304
  // Minimum number of edges of the mesh assuming each edge is shared between
305
  // two faces.
306
187
  const uint32_t min_num_face_edges = 3 * num_faces / 2;
307
308
  // Maximum number of edges that can exist between |num_encoded_vertices_|.
309
  // This is based on graph theory assuming simple connected graph.
310
187
  const uint64_t num_encoded_vertices_64 =
311
187
      static_cast<uint64_t>(num_encoded_vertices_);
312
187
  const uint64_t max_num_vertex_edges =
313
187
      num_encoded_vertices_64 * (num_encoded_vertices_64 - 1) / 2;
314
187
  if (max_num_vertex_edges < min_num_face_edges) {
315
    // It is impossible to construct a manifold mesh with these properties.
316
0
    return false;
317
0
  }
318
319
187
  uint8_t num_attribute_data;
320
187
  if (!decoder_->buffer()->Decode(&num_attribute_data)) {
321
0
    return false;
322
0
  }
323
324
187
  uint32_t num_encoded_symbols;
325
187
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
326
187
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
327
38
    if (!decoder_->buffer()->Decode(&num_encoded_symbols)) {
328
0
      return false;
329
0
    }
330
331
38
  } else
332
149
#endif
333
149
  {
334
149
    if (!DecodeVarint(&num_encoded_symbols, decoder_->buffer())) {
335
0
      return false;
336
0
    }
337
149
  }
338
339
187
  if (num_faces < num_encoded_symbols) {
340
    // Number of faces needs to be the same or greater than the number of
341
    // symbols (it can be greater because the initial face may not be encoded as
342
    // a symbol).
343
2
    return false;
344
2
  }
345
185
  const uint32_t max_encoded_faces =
346
185
      num_encoded_symbols + (num_encoded_symbols / 3);
347
185
  if (num_faces > max_encoded_faces) {
348
    // Faces can only be 1 1/3 times bigger than number of encoded symbols. This
349
    // could only happen if all new encoded components started with interior
350
    // triangles. E.g. A mesh with multiple tetrahedrons.
351
1
    return false;
352
1
  }
353
354
184
  uint32_t num_encoded_split_symbols;
355
184
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
356
184
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
357
35
    if (!decoder_->buffer()->Decode(&num_encoded_split_symbols)) {
358
0
      return false;
359
0
    }
360
361
35
  } else
362
149
#endif
363
149
  {
364
149
    if (!DecodeVarint(&num_encoded_split_symbols, decoder_->buffer())) {
365
0
      return false;
366
0
    }
367
149
  }
368
369
184
  if (num_encoded_split_symbols > num_encoded_symbols) {
370
3
    return false;  // Split symbols are a sub-set of all symbols.
371
3
  }
372
373
  // Decode topology (connectivity).
374
181
  vertex_traversal_length_.clear();
375
181
  corner_table_ = std::unique_ptr<CornerTable>(new CornerTable());
376
181
  if (corner_table_ == nullptr) {
377
0
    return false;
378
0
  }
379
181
  processed_corner_ids_.clear();
380
181
  processed_corner_ids_.reserve(num_faces);
381
181
  processed_connectivity_corners_.clear();
382
181
  processed_connectivity_corners_.reserve(num_faces);
383
181
  topology_split_data_.clear();
384
181
  hole_event_data_.clear();
385
181
  init_face_configurations_.clear();
386
181
  init_corners_.clear();
387
388
181
  last_symbol_id_ = -1;
389
181
  last_face_id_ = -1;
390
181
  last_vert_id_ = -1;
391
392
181
  attribute_data_.clear();
393
  // Add one attribute data for each attribute decoder.
394
181
  attribute_data_.resize(num_attribute_data);
395
396
181
  if (!corner_table_->Reset(
397
181
          num_faces, num_encoded_vertices_ + num_encoded_split_symbols)) {
398
0
    return false;
399
0
  }
400
401
  // Start with all vertices marked as holes (boundaries).
402
  // Only vertices decoded with TOPOLOGY_C symbol (and the initial face) will
403
  // be marked as non hole vertices. We need to allocate the array larger
404
  // because split symbols can create extra vertices during the decoding
405
  // process (these extra vertices are then eliminated during deduplication).
406
181
  is_vert_hole_.assign(num_encoded_vertices_ + num_encoded_split_symbols, true);
407
408
181
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
409
181
  int32_t topology_split_decoded_bytes = -1;
410
181
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
411
158
    uint32_t encoded_connectivity_size;
412
158
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
413
33
      if (!decoder_->buffer()->Decode(&encoded_connectivity_size)) {
414
0
        return false;
415
0
      }
416
125
    } else {
417
125
      if (!DecodeVarint(&encoded_connectivity_size, decoder_->buffer())) {
418
0
        return false;
419
0
      }
420
125
    }
421
158
    if (encoded_connectivity_size == 0 ||
422
158
        encoded_connectivity_size > decoder_->buffer()->remaining_size()) {
423
3
      return false;
424
3
    }
425
155
    DecoderBuffer event_buffer;
426
155
    event_buffer.Init(
427
155
        decoder_->buffer()->data_head() + encoded_connectivity_size,
428
155
        decoder_->buffer()->remaining_size() - encoded_connectivity_size,
429
155
        decoder_->buffer()->bitstream_version());
430
    // Decode hole and topology split events.
431
155
    topology_split_decoded_bytes =
432
155
        DecodeHoleAndTopologySplitEvents(&event_buffer);
433
155
    if (topology_split_decoded_bytes == -1) {
434
28
      return false;
435
28
    }
436
437
155
  } else
438
23
#endif
439
23
  {
440
23
    if (DecodeHoleAndTopologySplitEvents(decoder_->buffer()) == -1) {
441
1
      return false;
442
1
    }
443
23
  }
444
445
149
  traversal_decoder_.Init(this);
446
  // Add one extra vertex for each split symbol.
447
149
  traversal_decoder_.SetNumEncodedVertices(num_encoded_vertices_ +
448
149
                                           num_encoded_split_symbols);
449
149
  traversal_decoder_.SetNumAttributeData(num_attribute_data);
450
451
149
  DecoderBuffer traversal_end_buffer;
452
149
  if (!traversal_decoder_.Start(&traversal_end_buffer)) {
453
10
    return false;
454
10
  }
455
456
139
  const int num_connectivity_verts = DecodeConnectivity(num_encoded_symbols);
457
139
  if (num_connectivity_verts == -1) {
458
9
    return false;
459
9
  }
460
461
  // Set the main buffer to the end of the traversal.
462
130
  decoder_->buffer()->Init(traversal_end_buffer.data_head(),
463
130
                           traversal_end_buffer.remaining_size(),
464
130
                           decoder_->buffer()->bitstream_version());
465
466
130
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
467
130
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
468
    // Skip topology split data that was already decoded earlier.
469
112
    decoder_->buffer()->Advance(topology_split_decoded_bytes);
470
112
  }
471
130
#endif
472
473
  // Decode connectivity of non-position attributes.
474
130
  if (!attribute_data_.empty()) {
475
117
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
476
117
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) {
477
162k
      for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) {
478
162k
        if (!DecodeAttributeConnectivitiesOnFaceLegacy(ci)) {
479
0
          return false;
480
0
        }
481
162k
      }
482
483
105
    } else
484
12
#endif
485
12
    {
486
95.6k
      for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) {
487
95.6k
        if (!DecodeAttributeConnectivitiesOnFace(ci)) {
488
0
          return false;
489
0
        }
490
95.6k
      }
491
12
    }
492
117
  }
493
130
  traversal_decoder_.Done();
494
495
  // Decode attribute connectivity.
496
  // Prepare data structure for decoding non-position attribute connectivity.
497
253
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
498
123
    attribute_data_[i].connectivity_data.InitEmpty(corner_table_.get());
499
    // Add all seams.
500
340k
    for (int32_t c : attribute_data_[i].attribute_seam_corners) {
501
340k
      attribute_data_[i].connectivity_data.AddSeamEdge(CornerIndex(c));
502
340k
    }
503
    // Recompute vertices from the newly added seam edges.
504
123
    if (!attribute_data_[i].connectivity_data.RecomputeVertices(nullptr,
505
123
                                                                nullptr)) {
506
0
      return false;
507
0
    }
508
123
  }
509
510
130
  pos_encoding_data_.Init(corner_table_->num_vertices());
511
253
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
512
    // For non-position attributes, preallocate the vertex to value mapping
513
    // using the maximum number of vertices from the base corner table and the
514
    // attribute corner table (since the attribute decoder may use either of
515
    // it).
516
123
    int32_t att_connectivity_verts =
517
123
        attribute_data_[i].connectivity_data.num_vertices();
518
123
    if (att_connectivity_verts < corner_table_->num_vertices()) {
519
28
      att_connectivity_verts = corner_table_->num_vertices();
520
28
    }
521
123
    attribute_data_[i].encoding_data.Init(att_connectivity_verts);
522
123
  }
523
130
  if (!AssignPointsToCorners(num_connectivity_verts)) {
524
0
    return false;
525
0
  }
526
130
  return true;
527
130
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::DecodeConnectivity()
Line
Count
Source
247
348
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::DecodeConnectivity() {
248
348
  num_new_vertices_ = 0;
249
348
  new_to_parent_vertex_map_.clear();
250
348
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
251
348
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
252
135
    uint32_t num_new_verts;
253
135
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
254
119
      if (!decoder_->buffer()->Decode(&num_new_verts)) {
255
0
        return false;
256
0
      }
257
119
    } else {
258
16
      if (!DecodeVarint(&num_new_verts, decoder_->buffer())) {
259
0
        return false;
260
0
      }
261
16
    }
262
135
    num_new_vertices_ = num_new_verts;
263
135
  }
264
348
#endif
265
266
348
  uint32_t num_encoded_vertices;
267
348
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
268
348
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
269
119
    if (!decoder_->buffer()->Decode(&num_encoded_vertices)) {
270
0
      return false;
271
0
    }
272
273
119
  } else
274
229
#endif
275
229
  {
276
229
    if (!DecodeVarint(&num_encoded_vertices, decoder_->buffer())) {
277
0
      return false;
278
0
    }
279
229
  }
280
348
  num_encoded_vertices_ = num_encoded_vertices;
281
282
348
  uint32_t num_faces;
283
348
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
284
348
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
285
119
    if (!decoder_->buffer()->Decode(&num_faces)) {
286
0
      return false;
287
0
    }
288
289
119
  } else
290
229
#endif
291
229
  {
292
229
    if (!DecodeVarint(&num_faces, decoder_->buffer())) {
293
0
      return false;
294
0
    }
295
229
  }
296
348
  if (num_faces > std::numeric_limits<CornerIndex::ValueType>::max() / 3) {
297
0
    return false;  // Draco cannot handle this many faces.
298
0
  }
299
300
348
  if (static_cast<uint32_t>(num_encoded_vertices_) > num_faces * 3) {
301
2
    return false;  // There cannot be more vertices than 3 * num_faces.
302
2
  }
303
304
  // Minimum number of edges of the mesh assuming each edge is shared between
305
  // two faces.
306
346
  const uint32_t min_num_face_edges = 3 * num_faces / 2;
307
308
  // Maximum number of edges that can exist between |num_encoded_vertices_|.
309
  // This is based on graph theory assuming simple connected graph.
310
346
  const uint64_t num_encoded_vertices_64 =
311
346
      static_cast<uint64_t>(num_encoded_vertices_);
312
346
  const uint64_t max_num_vertex_edges =
313
346
      num_encoded_vertices_64 * (num_encoded_vertices_64 - 1) / 2;
314
346
  if (max_num_vertex_edges < min_num_face_edges) {
315
    // It is impossible to construct a manifold mesh with these properties.
316
0
    return false;
317
0
  }
318
319
346
  uint8_t num_attribute_data;
320
346
  if (!decoder_->buffer()->Decode(&num_attribute_data)) {
321
0
    return false;
322
0
  }
323
324
346
  uint32_t num_encoded_symbols;
325
346
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
326
346
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
327
117
    if (!decoder_->buffer()->Decode(&num_encoded_symbols)) {
328
0
      return false;
329
0
    }
330
331
117
  } else
332
229
#endif
333
229
  {
334
229
    if (!DecodeVarint(&num_encoded_symbols, decoder_->buffer())) {
335
0
      return false;
336
0
    }
337
229
  }
338
339
346
  if (num_faces < num_encoded_symbols) {
340
    // Number of faces needs to be the same or greater than the number of
341
    // symbols (it can be greater because the initial face may not be encoded as
342
    // a symbol).
343
1
    return false;
344
1
  }
345
345
  const uint32_t max_encoded_faces =
346
345
      num_encoded_symbols + (num_encoded_symbols / 3);
347
345
  if (num_faces > max_encoded_faces) {
348
    // Faces can only be 1 1/3 times bigger than number of encoded symbols. This
349
    // could only happen if all new encoded components started with interior
350
    // triangles. E.g. A mesh with multiple tetrahedrons.
351
0
    return false;
352
0
  }
353
354
345
  uint32_t num_encoded_split_symbols;
355
345
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
356
345
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
357
117
    if (!decoder_->buffer()->Decode(&num_encoded_split_symbols)) {
358
0
      return false;
359
0
    }
360
361
117
  } else
362
228
#endif
363
228
  {
364
228
    if (!DecodeVarint(&num_encoded_split_symbols, decoder_->buffer())) {
365
0
      return false;
366
0
    }
367
228
  }
368
369
345
  if (num_encoded_split_symbols > num_encoded_symbols) {
370
0
    return false;  // Split symbols are a sub-set of all symbols.
371
0
  }
372
373
  // Decode topology (connectivity).
374
345
  vertex_traversal_length_.clear();
375
345
  corner_table_ = std::unique_ptr<CornerTable>(new CornerTable());
376
345
  if (corner_table_ == nullptr) {
377
0
    return false;
378
0
  }
379
345
  processed_corner_ids_.clear();
380
345
  processed_corner_ids_.reserve(num_faces);
381
345
  processed_connectivity_corners_.clear();
382
345
  processed_connectivity_corners_.reserve(num_faces);
383
345
  topology_split_data_.clear();
384
345
  hole_event_data_.clear();
385
345
  init_face_configurations_.clear();
386
345
  init_corners_.clear();
387
388
345
  last_symbol_id_ = -1;
389
345
  last_face_id_ = -1;
390
345
  last_vert_id_ = -1;
391
392
345
  attribute_data_.clear();
393
  // Add one attribute data for each attribute decoder.
394
345
  attribute_data_.resize(num_attribute_data);
395
396
345
  if (!corner_table_->Reset(
397
345
          num_faces, num_encoded_vertices_ + num_encoded_split_symbols)) {
398
0
    return false;
399
0
  }
400
401
  // Start with all vertices marked as holes (boundaries).
402
  // Only vertices decoded with TOPOLOGY_C symbol (and the initial face) will
403
  // be marked as non hole vertices. We need to allocate the array larger
404
  // because split symbols can create extra vertices during the decoding
405
  // process (these extra vertices are then eliminated during deduplication).
406
345
  is_vert_hole_.assign(num_encoded_vertices_ + num_encoded_split_symbols, true);
407
408
345
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
409
345
  int32_t topology_split_decoded_bytes = -1;
410
345
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
411
133
    uint32_t encoded_connectivity_size;
412
133
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
413
117
      if (!decoder_->buffer()->Decode(&encoded_connectivity_size)) {
414
0
        return false;
415
0
      }
416
117
    } else {
417
16
      if (!DecodeVarint(&encoded_connectivity_size, decoder_->buffer())) {
418
0
        return false;
419
0
      }
420
16
    }
421
133
    if (encoded_connectivity_size == 0 ||
422
133
        encoded_connectivity_size > decoder_->buffer()->remaining_size()) {
423
1
      return false;
424
1
    }
425
132
    DecoderBuffer event_buffer;
426
132
    event_buffer.Init(
427
132
        decoder_->buffer()->data_head() + encoded_connectivity_size,
428
132
        decoder_->buffer()->remaining_size() - encoded_connectivity_size,
429
132
        decoder_->buffer()->bitstream_version());
430
    // Decode hole and topology split events.
431
132
    topology_split_decoded_bytes =
432
132
        DecodeHoleAndTopologySplitEvents(&event_buffer);
433
132
    if (topology_split_decoded_bytes == -1) {
434
22
      return false;
435
22
    }
436
437
132
  } else
438
212
#endif
439
212
  {
440
212
    if (DecodeHoleAndTopologySplitEvents(decoder_->buffer()) == -1) {
441
1
      return false;
442
1
    }
443
212
  }
444
445
321
  traversal_decoder_.Init(this);
446
  // Add one extra vertex for each split symbol.
447
321
  traversal_decoder_.SetNumEncodedVertices(num_encoded_vertices_ +
448
321
                                           num_encoded_split_symbols);
449
321
  traversal_decoder_.SetNumAttributeData(num_attribute_data);
450
451
321
  DecoderBuffer traversal_end_buffer;
452
321
  if (!traversal_decoder_.Start(&traversal_end_buffer)) {
453
134
    return false;
454
134
  }
455
456
187
  const int num_connectivity_verts = DecodeConnectivity(num_encoded_symbols);
457
187
  if (num_connectivity_verts == -1) {
458
109
    return false;
459
109
  }
460
461
  // Set the main buffer to the end of the traversal.
462
78
  decoder_->buffer()->Init(traversal_end_buffer.data_head(),
463
78
                           traversal_end_buffer.remaining_size(),
464
78
                           decoder_->buffer()->bitstream_version());
465
466
78
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
467
78
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
468
    // Skip topology split data that was already decoded earlier.
469
0
    decoder_->buffer()->Advance(topology_split_decoded_bytes);
470
0
  }
471
78
#endif
472
473
  // Decode connectivity of non-position attributes.
474
78
  if (!attribute_data_.empty()) {
475
18
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
476
18
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) {
477
0
      for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) {
478
0
        if (!DecodeAttributeConnectivitiesOnFaceLegacy(ci)) {
479
0
          return false;
480
0
        }
481
0
      }
482
483
0
    } else
484
18
#endif
485
18
    {
486
102k
      for (CornerIndex ci(0); ci < corner_table_->num_corners(); ci += 3) {
487
102k
        if (!DecodeAttributeConnectivitiesOnFace(ci)) {
488
0
          return false;
489
0
        }
490
102k
      }
491
18
    }
492
18
  }
493
78
  traversal_decoder_.Done();
494
495
  // Decode attribute connectivity.
496
  // Prepare data structure for decoding non-position attribute connectivity.
497
116
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
498
38
    attribute_data_[i].connectivity_data.InitEmpty(corner_table_.get());
499
    // Add all seams.
500
164k
    for (int32_t c : attribute_data_[i].attribute_seam_corners) {
501
164k
      attribute_data_[i].connectivity_data.AddSeamEdge(CornerIndex(c));
502
164k
    }
503
    // Recompute vertices from the newly added seam edges.
504
38
    if (!attribute_data_[i].connectivity_data.RecomputeVertices(nullptr,
505
38
                                                                nullptr)) {
506
0
      return false;
507
0
    }
508
38
  }
509
510
78
  pos_encoding_data_.Init(corner_table_->num_vertices());
511
116
  for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
512
    // For non-position attributes, preallocate the vertex to value mapping
513
    // using the maximum number of vertices from the base corner table and the
514
    // attribute corner table (since the attribute decoder may use either of
515
    // it).
516
38
    int32_t att_connectivity_verts =
517
38
        attribute_data_[i].connectivity_data.num_vertices();
518
38
    if (att_connectivity_verts < corner_table_->num_vertices()) {
519
0
      att_connectivity_verts = corner_table_->num_vertices();
520
0
    }
521
38
    attribute_data_[i].encoding_data.Init(att_connectivity_verts);
522
38
  }
523
78
  if (!AssignPointsToCorners(num_connectivity_verts)) {
524
0
    return false;
525
0
  }
526
78
  return true;
527
78
}
528
529
template <class TraversalDecoder>
530
55
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::OnAttributesDecoded() {
531
55
  return true;
532
55
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::OnAttributesDecoded()
Line
Count
Source
530
32
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::OnAttributesDecoded() {
531
32
  return true;
532
32
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::OnAttributesDecoded()
Line
Count
Source
530
13
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::OnAttributesDecoded() {
531
13
  return true;
532
13
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::OnAttributesDecoded()
Line
Count
Source
530
10
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::OnAttributesDecoded() {
531
10
  return true;
532
10
}
533
534
template <class TraversalDecoder>
535
int MeshEdgebreakerDecoderImpl<TraversalDecoder>::DecodeConnectivity(
536
589
    int num_symbols) {
537
  // Algorithm does the reverse decoding of the symbols encoded with the
538
  // edgebreaker method. The reverse decoding always keeps track of the active
539
  // edge identified by its opposite corner (active corner). New faces are
540
  // always added to this active edge. There may be multiple active corners at
541
  // one time that either correspond to separate mesh components or to
542
  // sub-components of one mesh that are going to be merged together using the
543
  // TOPOLOGY_S symbol. We can store these active edges on a stack, because the
544
  // decoder always processes only the latest active edge. TOPOLOGY_S then
545
  // removes the top edge from the stack and TOPOLOGY_E adds a new edge to the
546
  // stack.
547
589
  std::vector<CornerIndex> active_corner_stack;
548
549
  // Additional active edges may be added as a result of topology split events.
550
  // They can be added in arbitrary order, but we always know the split symbol
551
  // id they belong to, so we can address them using this symbol id.
552
589
  std::unordered_map<int, CornerIndex> topology_split_active_corners;
553
554
  // Vector used for storing vertices that were marked as isolated during the
555
  // decoding process. Currently used only when the mesh doesn't contain any
556
  // non-position connectivity data.
557
589
  std::vector<VertexIndex> invalid_vertices;
558
589
  const bool remove_invalid_vertices = attribute_data_.empty();
559
560
589
  int max_num_vertices = static_cast<int>(is_vert_hole_.size());
561
589
  int num_faces = 0;
562
60.9M
  for (int symbol_id = 0; symbol_id < num_symbols; ++symbol_id) {
563
60.9M
    const FaceIndex face(num_faces++);
564
    // Used to flag cases where we need to look for topology split events.
565
60.9M
    bool check_topology_split = false;
566
60.9M
    const uint32_t symbol = traversal_decoder_.DecodeSymbol();
567
60.9M
    if (symbol == TOPOLOGY_C) {
568
      // Create a new face between two edges on the open boundary.
569
      // The first edge is opposite to the corner "a" from the image below.
570
      // The other edge is opposite to the corner "b" that can be reached
571
      // through a CCW traversal around the vertex "v".
572
      // One new active boundary edge is created, opposite to the new corner
573
      // "x".
574
      //
575
      //     *-------*
576
      //    / \     / \
577
      //   /   \   /   \
578
      //  /     \ /     \
579
      // *-------v-------*
580
      //  \b    /x\    a/
581
      //   \   /   \   /
582
      //    \ /  C  \ /
583
      //     *.......*
584
585
      // Find the corner "b" from the corner "a" which is the corner on the
586
      // top of the active stack.
587
29.9M
      if (active_corner_stack.empty()) {
588
45
        return -1;
589
45
      }
590
591
29.9M
      const CornerIndex corner_a = active_corner_stack.back();
592
29.9M
      const VertexIndex vertex_x =
593
29.9M
          corner_table_->Vertex(corner_table_->Next(corner_a));
594
29.9M
      const CornerIndex corner_b =
595
29.9M
          corner_table_->Next(corner_table_->LeftMostCorner(vertex_x));
596
597
29.9M
      if (corner_a == corner_b) {
598
        // All matched corners must be different.
599
68
        return -1;
600
68
      }
601
29.9M
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex ||
602
29.9M
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex) {
603
        // One of the corners is already opposite to an existing face, which
604
        // should not happen unless the input was tampered with.
605
0
        return -1;
606
0
      }
607
608
      // New tip corner.
609
29.9M
      const CornerIndex corner(3 * face.value());
610
      // Update opposite corner mappings.
611
29.9M
      SetOppositeCorners(corner_a, corner + 1);
612
29.9M
      SetOppositeCorners(corner_b, corner + 2);
613
614
      // Update vertex mapping.
615
29.9M
      const VertexIndex vert_a_prev =
616
29.9M
          corner_table_->Vertex(corner_table_->Previous(corner_a));
617
29.9M
      const VertexIndex vert_b_next =
618
29.9M
          corner_table_->Vertex(corner_table_->Next(corner_b));
619
29.9M
      if (vertex_x == vert_a_prev || vertex_x == vert_b_next) {
620
        // Encoding is invalid, because face vertices are degenerate.
621
0
        return -1;
622
0
      }
623
29.9M
      corner_table_->MapCornerToVertex(corner, vertex_x);
624
29.9M
      corner_table_->MapCornerToVertex(corner + 1, vert_b_next);
625
29.9M
      corner_table_->MapCornerToVertex(corner + 2, vert_a_prev);
626
29.9M
      corner_table_->SetLeftMostCorner(vert_a_prev, corner + 2);
627
      // Mark the vertex |x| as interior.
628
29.9M
      is_vert_hole_[vertex_x.value()] = false;
629
      // Update the corner on the active stack.
630
29.9M
      active_corner_stack.back() = corner;
631
31.0M
    } else if (symbol == TOPOLOGY_R || symbol == TOPOLOGY_L) {
632
      // Create a new face extending from the open boundary edge opposite to the
633
      // corner "a" from the image below. Two new boundary edges are created
634
      // opposite to corners "r" and "l". New active corner is set to either "r"
635
      // or "l" depending on the decoded symbol. One new vertex is created
636
      // at the opposite corner to corner "a".
637
      //     *-------*
638
      //    /a\     / \
639
      //   /   \   /   \
640
      //  /     \ /     \
641
      // *-------v-------*
642
      //  .l   r.
643
      //   .   .
644
      //    . .
645
      //     *
646
29.5M
      if (active_corner_stack.empty()) {
647
0
        return -1;
648
0
      }
649
29.5M
      const CornerIndex corner_a = active_corner_stack.back();
650
29.5M
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex) {
651
        // Active corner is already opposite to an existing face, which should
652
        // not happen unless the input was tampered with.
653
0
        return -1;
654
0
      }
655
656
      // First corner on the new face is either corner "l" or "r".
657
29.5M
      const CornerIndex corner(3 * face.value());
658
29.5M
      CornerIndex opp_corner, corner_l, corner_r;
659
29.5M
      if (symbol == TOPOLOGY_R) {
660
        // "r" is the new first corner.
661
28.1M
        opp_corner = corner + 2;
662
28.1M
        corner_l = corner + 1;
663
28.1M
        corner_r = corner;
664
28.1M
      } else {
665
        // "l" is the new first corner.
666
1.37M
        opp_corner = corner + 1;
667
1.37M
        corner_l = corner;
668
1.37M
        corner_r = corner + 2;
669
1.37M
      }
670
29.5M
      SetOppositeCorners(opp_corner, corner_a);
671
      // Update vertex mapping.
672
29.5M
      const VertexIndex new_vert_index = corner_table_->AddNewVertex();
673
674
29.5M
      if (corner_table_->num_vertices() > max_num_vertices) {
675
1
        return -1;  // Unexpected number of decoded vertices.
676
1
      }
677
678
29.5M
      corner_table_->MapCornerToVertex(opp_corner, new_vert_index);
679
29.5M
      corner_table_->SetLeftMostCorner(new_vert_index, opp_corner);
680
681
29.5M
      const VertexIndex vertex_r =
682
29.5M
          corner_table_->Vertex(corner_table_->Previous(corner_a));
683
29.5M
      corner_table_->MapCornerToVertex(corner_r, vertex_r);
684
      // Update left-most corner on the vertex on the |corner_r|.
685
29.5M
      corner_table_->SetLeftMostCorner(vertex_r, corner_r);
686
687
29.5M
      corner_table_->MapCornerToVertex(
688
29.5M
          corner_l, corner_table_->Vertex(corner_table_->Next(corner_a)));
689
29.5M
      active_corner_stack.back() = corner;
690
29.5M
      check_topology_split = true;
691
29.5M
    } else if (symbol == TOPOLOGY_S) {
692
      // Create a new face that merges two last active edges from the active
693
      // stack. No new vertex is created, but two vertices at corners "p" and
694
      // "n" need to be merged into a single vertex.
695
      //
696
      // *-------v-------*
697
      //  \a   p/x\n   b/
698
      //   \   /   \   /
699
      //    \ /  S  \ /
700
      //     *.......*
701
      //
702
520k
      if (active_corner_stack.empty()) {
703
0
        return -1;
704
0
      }
705
520k
      const CornerIndex corner_b = active_corner_stack.back();
706
520k
      active_corner_stack.pop_back();
707
708
      // Corner "a" can correspond either to a normal active edge, or to an edge
709
      // created from the topology split event.
710
520k
      const auto it = topology_split_active_corners.find(symbol_id);
711
520k
      if (it != topology_split_active_corners.end()) {
712
        // Topology split event. Move the retrieved edge to the stack.
713
2
        active_corner_stack.push_back(it->second);
714
2
      }
715
520k
      if (active_corner_stack.empty()) {
716
3
        return -1;
717
3
      }
718
520k
      const CornerIndex corner_a = active_corner_stack.back();
719
720
520k
      if (corner_a == corner_b) {
721
        // All matched corners must be different.
722
0
        return -1;
723
0
      }
724
520k
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex ||
725
520k
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex) {
726
        // One of the corners is already opposite to an existing face, which
727
        // should not happen unless the input was tampered with.
728
1
        return -1;
729
1
      }
730
731
      // First corner on the new face is corner "x" from the image above.
732
520k
      const CornerIndex corner(3 * face.value());
733
      // Update the opposite corner mapping.
734
520k
      SetOppositeCorners(corner_a, corner + 2);
735
520k
      SetOppositeCorners(corner_b, corner + 1);
736
      // Update vertices. For the vertex at corner "x", use the vertex id from
737
      // the corner "p".
738
520k
      const VertexIndex vertex_p =
739
520k
          corner_table_->Vertex(corner_table_->Previous(corner_a));
740
520k
      corner_table_->MapCornerToVertex(corner, vertex_p);
741
520k
      corner_table_->MapCornerToVertex(
742
520k
          corner + 1, corner_table_->Vertex(corner_table_->Next(corner_a)));
743
520k
      const VertexIndex vert_b_prev =
744
520k
          corner_table_->Vertex(corner_table_->Previous(corner_b));
745
520k
      corner_table_->MapCornerToVertex(corner + 2, vert_b_prev);
746
520k
      corner_table_->SetLeftMostCorner(vert_b_prev, corner + 2);
747
520k
      CornerIndex corner_n = corner_table_->Next(corner_b);
748
520k
      const VertexIndex vertex_n = corner_table_->Vertex(corner_n);
749
520k
      traversal_decoder_.MergeVertices(vertex_p, vertex_n);
750
      // Update the left most corner on the newly merged vertex.
751
520k
      corner_table_->SetLeftMostCorner(vertex_p,
752
520k
                                       corner_table_->LeftMostCorner(vertex_n));
753
754
      // Also update the vertex id at corner "n" and all corners that are
755
      // connected to it in the CCW direction.
756
520k
      const CornerIndex first_corner = corner_n;
757
29.3M
      while (corner_n != kInvalidCornerIndex) {
758
28.7M
        corner_table_->MapCornerToVertex(corner_n, vertex_p);
759
28.7M
        corner_n = corner_table_->SwingLeft(corner_n);
760
28.7M
        if (corner_n == first_corner) {
761
          // We reached the start again which should not happen for split
762
          // symbols.
763
0
          return -1;
764
0
        }
765
28.7M
      }
766
      // Make sure the old vertex n is now mapped to an invalid corner (make it
767
      // isolated).
768
520k
      corner_table_->MakeVertexIsolated(vertex_n);
769
520k
      if (remove_invalid_vertices) {
770
507k
        invalid_vertices.push_back(vertex_n);
771
507k
      }
772
520k
      active_corner_stack.back() = corner;
773
966k
    } else if (symbol == TOPOLOGY_E) {
774
966k
      const CornerIndex corner(3 * face.value());
775
966k
      const VertexIndex first_vert_index = corner_table_->AddNewVertex();
776
      // Create three new vertices at the corners of the new face.
777
966k
      corner_table_->MapCornerToVertex(corner, first_vert_index);
778
966k
      corner_table_->MapCornerToVertex(corner + 1,
779
966k
                                       corner_table_->AddNewVertex());
780
966k
      corner_table_->MapCornerToVertex(corner + 2,
781
966k
                                       corner_table_->AddNewVertex());
782
783
966k
      if (corner_table_->num_vertices() > max_num_vertices) {
784
1
        return -1;  // Unexpected number of decoded vertices.
785
1
      }
786
787
966k
      corner_table_->SetLeftMostCorner(first_vert_index, corner);
788
966k
      corner_table_->SetLeftMostCorner(first_vert_index + 1, corner + 1);
789
966k
      corner_table_->SetLeftMostCorner(first_vert_index + 2, corner + 2);
790
      // Add the tip corner to the active stack.
791
966k
      active_corner_stack.push_back(corner);
792
966k
      check_topology_split = true;
793
966k
    } else {
794
      // Error. Unknown symbol decoded.
795
25
      return -1;
796
25
    }
797
    // Inform the traversal decoder that a new corner has been reached.
798
60.9M
    traversal_decoder_.NewActiveCornerReached(active_corner_stack.back());
799
800
60.9M
    if (check_topology_split) {
801
      // Check for topology splits happens only for TOPOLOGY_L, TOPOLOGY_R and
802
      // TOPOLOGY_E symbols because those are the symbols that correspond to
803
      // faces that can be directly connected a TOPOLOGY_S face through the
804
      // topology split event.
805
      // If a topology split is detected, we need to add a new active edge
806
      // onto the active_corner_stack because it will be used later when the
807
      // corresponding TOPOLOGY_S event is decoded.
808
809
      // Symbol id used by the encoder (reverse).
810
30.5M
      const int encoder_symbol_id = num_symbols - symbol_id - 1;
811
30.5M
      EdgeFaceName split_edge;
812
30.5M
      int encoder_split_symbol_id;
813
30.5M
      while (IsTopologySplit(encoder_symbol_id, &split_edge,
814
30.5M
                             &encoder_split_symbol_id)) {
815
1.28k
        if (encoder_split_symbol_id < 0) {
816
7
          return -1;  // Wrong split symbol id.
817
7
        }
818
        // Symbol was part of a topology split. Now we need to determine which
819
        // edge should be added to the active edges stack.
820
1.27k
        const CornerIndex act_top_corner = active_corner_stack.back();
821
        // The current symbol has one active edge (stored in act_top_corner) and
822
        // two remaining inactive edges that are attached to it.
823
        //              *
824
        //             / \
825
        //  left_edge /   \ right_edge
826
        //           /     \
827
        //          *.......*
828
        //         active_edge
829
830
1.27k
        CornerIndex new_active_corner;
831
1.27k
        if (split_edge == RIGHT_FACE_EDGE) {
832
391
          new_active_corner = corner_table_->Next(act_top_corner);
833
882
        } else {
834
882
          new_active_corner = corner_table_->Previous(act_top_corner);
835
882
        }
836
        // Add the new active edge.
837
        // Convert the encoder split symbol id to decoder symbol id.
838
1.27k
        const int decoder_split_symbol_id =
839
1.27k
            num_symbols - encoder_split_symbol_id - 1;
840
1.27k
        topology_split_active_corners[decoder_split_symbol_id] =
841
1.27k
            new_active_corner;
842
1.27k
      }
843
30.5M
    }
844
60.9M
  }
845
438
  if (corner_table_->num_vertices() > max_num_vertices) {
846
0
    return -1;  // Unexpected number of decoded vertices.
847
0
  }
848
  // Decode start faces and connect them to the faces from the active stack.
849
6.60k
  while (!active_corner_stack.empty()) {
850
6.18k
    const CornerIndex corner = active_corner_stack.back();
851
6.18k
    active_corner_stack.pop_back();
852
6.18k
    const bool interior_face =
853
6.18k
        traversal_decoder_.DecodeStartFaceConfiguration();
854
6.18k
    if (interior_face) {
855
      // The start face is interior, we need to find three corners that are
856
      // opposite to it. The first opposite corner "a" is the corner from the
857
      // top of the active corner stack and the remaining two corners "b" and
858
      // "c" are then the next corners from the left-most corners of vertices
859
      // "n" and "x" respectively.
860
      //
861
      //           *-------*
862
      //          / \     / \
863
      //         /   \   /   \
864
      //        /     \ /     \
865
      //       *-------p-------*
866
      //      / \a    . .    c/ \
867
      //     /   \   .   .   /   \
868
      //    /     \ .  I  . /     \
869
      //   *-------n.......x------*
870
      //    \     / \     / \     /
871
      //     \   /   \   /   \   /
872
      //      \ /     \b/     \ /
873
      //       *-------*-------*
874
      //
875
876
3.57k
      if (num_faces >= corner_table_->num_faces()) {
877
1
        return -1;  // More faces than expected added to the mesh.
878
1
      }
879
880
3.57k
      const CornerIndex corner_a = corner;
881
3.57k
      const VertexIndex vert_n =
882
3.57k
          corner_table_->Vertex(corner_table_->Next(corner_a));
883
3.57k
      const CornerIndex corner_b =
884
3.57k
          corner_table_->Next(corner_table_->LeftMostCorner(vert_n));
885
886
3.57k
      const VertexIndex vert_x =
887
3.57k
          corner_table_->Vertex(corner_table_->Next(corner_b));
888
3.57k
      const CornerIndex corner_c =
889
3.57k
          corner_table_->Next(corner_table_->LeftMostCorner(vert_x));
890
891
3.57k
      if (corner == corner_b || corner == corner_c || corner_b == corner_c) {
892
        // All matched corners must be different.
893
13
        return -1;
894
13
      }
895
3.55k
      if (corner_table_->Opposite(corner) != kInvalidCornerIndex ||
896
3.55k
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex ||
897
3.55k
          corner_table_->Opposite(corner_c) != kInvalidCornerIndex) {
898
        // One of the corners is already opposite to an existing face, which
899
        // should not happen unless the input was tampered with.
900
0
        return -1;
901
0
      }
902
903
3.55k
      const VertexIndex vert_p =
904
3.55k
          corner_table_->Vertex(corner_table_->Next(corner_c));
905
906
3.55k
      const FaceIndex face(num_faces++);
907
      // The first corner of the initial face is the corner opposite to "a".
908
3.55k
      const CornerIndex new_corner(3 * face.value());
909
3.55k
      SetOppositeCorners(new_corner, corner);
910
3.55k
      SetOppositeCorners(new_corner + 1, corner_b);
911
3.55k
      SetOppositeCorners(new_corner + 2, corner_c);
912
913
      // Map new corners to existing vertices.
914
3.55k
      corner_table_->MapCornerToVertex(new_corner, vert_x);
915
3.55k
      corner_table_->MapCornerToVertex(new_corner + 1, vert_p);
916
3.55k
      corner_table_->MapCornerToVertex(new_corner + 2, vert_n);
917
918
      // Mark all three vertices as interior.
919
14.2k
      for (int ci = 0; ci < 3; ++ci) {
920
10.6k
        is_vert_hole_[corner_table_->Vertex(new_corner + ci).value()] = false;
921
10.6k
      }
922
923
3.55k
      init_face_configurations_.push_back(true);
924
3.55k
      init_corners_.push_back(new_corner);
925
3.55k
    } else {
926
      // The initial face wasn't interior and the traversal had to start from
927
      // an open boundary. In this case no new face is added, but we need to
928
      // keep record about the first opposite corner to this boundary.
929
2.61k
      init_face_configurations_.push_back(false);
930
2.61k
      init_corners_.push_back(corner);
931
2.61k
    }
932
6.18k
  }
933
424
  if (num_faces != corner_table_->num_faces()) {
934
4
    return -1;  // Unexpected number of decoded faces.
935
4
  }
936
937
420
  int num_vertices = corner_table_->num_vertices();
938
  // If any vertex was marked as isolated, we want to remove it from the corner
939
  // table to ensure that all vertices in range <0, num_vertices> are valid.
940
9.08k
  for (const VertexIndex invalid_vert : invalid_vertices) {
941
    // Find the last valid vertex and swap it with the isolated vertex.
942
9.08k
    VertexIndex src_vert(num_vertices - 1);
943
10.5k
    while (corner_table_->LeftMostCorner(src_vert) == kInvalidCornerIndex) {
944
      // The last vertex is invalid, proceed to the previous one.
945
1.41k
      src_vert = VertexIndex(--num_vertices - 1);
946
1.41k
    }
947
9.08k
    if (src_vert < invalid_vert) {
948
1.41k
      continue;  // No need to swap anything.
949
1.41k
    }
950
951
    // Remap all corners mapped to |src_vert| to |invalid_vert|.
952
7.67k
    VertexCornersIterator<CornerTable> vcit(corner_table_.get(), src_vert);
953
52.3k
    for (; !vcit.End(); ++vcit) {
954
44.6k
      const CornerIndex cid = vcit.Corner();
955
44.6k
      if (corner_table_->Vertex(cid) != src_vert) {
956
        // Vertex mapped to |cid| was not |src_vert|. This indicates corrupted
957
        // data and we should terminate the decoding.
958
0
        return -1;
959
0
      }
960
44.6k
      corner_table_->MapCornerToVertex(cid, invalid_vert);
961
44.6k
    }
962
7.67k
    corner_table_->SetLeftMostCorner(invalid_vert,
963
7.67k
                                     corner_table_->LeftMostCorner(src_vert));
964
965
    // Make the |src_vert| invalid.
966
7.67k
    corner_table_->MakeVertexIsolated(src_vert);
967
7.67k
    is_vert_hole_[invalid_vert.value()] = is_vert_hole_[src_vert.value()];
968
7.67k
    is_vert_hole_[src_vert.value()] = false;
969
970
    // The last vertex is now invalid.
971
7.67k
    num_vertices--;
972
7.67k
  }
973
420
  return num_vertices;
974
420
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::DecodeConnectivity(int)
Line
Count
Source
536
263
    int num_symbols) {
537
  // Algorithm does the reverse decoding of the symbols encoded with the
538
  // edgebreaker method. The reverse decoding always keeps track of the active
539
  // edge identified by its opposite corner (active corner). New faces are
540
  // always added to this active edge. There may be multiple active corners at
541
  // one time that either correspond to separate mesh components or to
542
  // sub-components of one mesh that are going to be merged together using the
543
  // TOPOLOGY_S symbol. We can store these active edges on a stack, because the
544
  // decoder always processes only the latest active edge. TOPOLOGY_S then
545
  // removes the top edge from the stack and TOPOLOGY_E adds a new edge to the
546
  // stack.
547
263
  std::vector<CornerIndex> active_corner_stack;
548
549
  // Additional active edges may be added as a result of topology split events.
550
  // They can be added in arbitrary order, but we always know the split symbol
551
  // id they belong to, so we can address them using this symbol id.
552
263
  std::unordered_map<int, CornerIndex> topology_split_active_corners;
553
554
  // Vector used for storing vertices that were marked as isolated during the
555
  // decoding process. Currently used only when the mesh doesn't contain any
556
  // non-position connectivity data.
557
263
  std::vector<VertexIndex> invalid_vertices;
558
263
  const bool remove_invalid_vertices = attribute_data_.empty();
559
560
263
  int max_num_vertices = static_cast<int>(is_vert_hole_.size());
561
263
  int num_faces = 0;
562
4.25M
  for (int symbol_id = 0; symbol_id < num_symbols; ++symbol_id) {
563
4.25M
    const FaceIndex face(num_faces++);
564
    // Used to flag cases where we need to look for topology split events.
565
4.25M
    bool check_topology_split = false;
566
4.25M
    const uint32_t symbol = traversal_decoder_.DecodeSymbol();
567
4.25M
    if (symbol == TOPOLOGY_C) {
568
      // Create a new face between two edges on the open boundary.
569
      // The first edge is opposite to the corner "a" from the image below.
570
      // The other edge is opposite to the corner "b" that can be reached
571
      // through a CCW traversal around the vertex "v".
572
      // One new active boundary edge is created, opposite to the new corner
573
      // "x".
574
      //
575
      //     *-------*
576
      //    / \     / \
577
      //   /   \   /   \
578
      //  /     \ /     \
579
      // *-------v-------*
580
      //  \b    /x\    a/
581
      //   \   /   \   /
582
      //    \ /  C  \ /
583
      //     *.......*
584
585
      // Find the corner "b" from the corner "a" which is the corner on the
586
      // top of the active stack.
587
2.04M
      if (active_corner_stack.empty()) {
588
0
        return -1;
589
0
      }
590
591
2.04M
      const CornerIndex corner_a = active_corner_stack.back();
592
2.04M
      const VertexIndex vertex_x =
593
2.04M
          corner_table_->Vertex(corner_table_->Next(corner_a));
594
2.04M
      const CornerIndex corner_b =
595
2.04M
          corner_table_->Next(corner_table_->LeftMostCorner(vertex_x));
596
597
2.04M
      if (corner_a == corner_b) {
598
        // All matched corners must be different.
599
33
        return -1;
600
33
      }
601
2.04M
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex ||
602
2.04M
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex) {
603
        // One of the corners is already opposite to an existing face, which
604
        // should not happen unless the input was tampered with.
605
0
        return -1;
606
0
      }
607
608
      // New tip corner.
609
2.04M
      const CornerIndex corner(3 * face.value());
610
      // Update opposite corner mappings.
611
2.04M
      SetOppositeCorners(corner_a, corner + 1);
612
2.04M
      SetOppositeCorners(corner_b, corner + 2);
613
614
      // Update vertex mapping.
615
2.04M
      const VertexIndex vert_a_prev =
616
2.04M
          corner_table_->Vertex(corner_table_->Previous(corner_a));
617
2.04M
      const VertexIndex vert_b_next =
618
2.04M
          corner_table_->Vertex(corner_table_->Next(corner_b));
619
2.04M
      if (vertex_x == vert_a_prev || vertex_x == vert_b_next) {
620
        // Encoding is invalid, because face vertices are degenerate.
621
0
        return -1;
622
0
      }
623
2.04M
      corner_table_->MapCornerToVertex(corner, vertex_x);
624
2.04M
      corner_table_->MapCornerToVertex(corner + 1, vert_b_next);
625
2.04M
      corner_table_->MapCornerToVertex(corner + 2, vert_a_prev);
626
2.04M
      corner_table_->SetLeftMostCorner(vert_a_prev, corner + 2);
627
      // Mark the vertex |x| as interior.
628
2.04M
      is_vert_hole_[vertex_x.value()] = false;
629
      // Update the corner on the active stack.
630
2.04M
      active_corner_stack.back() = corner;
631
2.21M
    } else if (symbol == TOPOLOGY_R || symbol == TOPOLOGY_L) {
632
      // Create a new face extending from the open boundary edge opposite to the
633
      // corner "a" from the image below. Two new boundary edges are created
634
      // opposite to corners "r" and "l". New active corner is set to either "r"
635
      // or "l" depending on the decoded symbol. One new vertex is created
636
      // at the opposite corner to corner "a".
637
      //     *-------*
638
      //    /a\     / \
639
      //   /   \   /   \
640
      //  /     \ /     \
641
      // *-------v-------*
642
      //  .l   r.
643
      //   .   .
644
      //    . .
645
      //     *
646
727k
      if (active_corner_stack.empty()) {
647
0
        return -1;
648
0
      }
649
727k
      const CornerIndex corner_a = active_corner_stack.back();
650
727k
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex) {
651
        // Active corner is already opposite to an existing face, which should
652
        // not happen unless the input was tampered with.
653
0
        return -1;
654
0
      }
655
656
      // First corner on the new face is either corner "l" or "r".
657
727k
      const CornerIndex corner(3 * face.value());
658
727k
      CornerIndex opp_corner, corner_l, corner_r;
659
727k
      if (symbol == TOPOLOGY_R) {
660
        // "r" is the new first corner.
661
277k
        opp_corner = corner + 2;
662
277k
        corner_l = corner + 1;
663
277k
        corner_r = corner;
664
449k
      } else {
665
        // "l" is the new first corner.
666
449k
        opp_corner = corner + 1;
667
449k
        corner_l = corner;
668
449k
        corner_r = corner + 2;
669
449k
      }
670
727k
      SetOppositeCorners(opp_corner, corner_a);
671
      // Update vertex mapping.
672
727k
      const VertexIndex new_vert_index = corner_table_->AddNewVertex();
673
674
727k
      if (corner_table_->num_vertices() > max_num_vertices) {
675
0
        return -1;  // Unexpected number of decoded vertices.
676
0
      }
677
678
727k
      corner_table_->MapCornerToVertex(opp_corner, new_vert_index);
679
727k
      corner_table_->SetLeftMostCorner(new_vert_index, opp_corner);
680
681
727k
      const VertexIndex vertex_r =
682
727k
          corner_table_->Vertex(corner_table_->Previous(corner_a));
683
727k
      corner_table_->MapCornerToVertex(corner_r, vertex_r);
684
      // Update left-most corner on the vertex on the |corner_r|.
685
727k
      corner_table_->SetLeftMostCorner(vertex_r, corner_r);
686
687
727k
      corner_table_->MapCornerToVertex(
688
727k
          corner_l, corner_table_->Vertex(corner_table_->Next(corner_a)));
689
727k
      active_corner_stack.back() = corner;
690
727k
      check_topology_split = true;
691
1.48M
    } else if (symbol == TOPOLOGY_S) {
692
      // Create a new face that merges two last active edges from the active
693
      // stack. No new vertex is created, but two vertices at corners "p" and
694
      // "n" need to be merged into a single vertex.
695
      //
696
      // *-------v-------*
697
      //  \a   p/x\n   b/
698
      //   \   /   \   /
699
      //    \ /  S  \ /
700
      //     *.......*
701
      //
702
519k
      if (active_corner_stack.empty()) {
703
0
        return -1;
704
0
      }
705
519k
      const CornerIndex corner_b = active_corner_stack.back();
706
519k
      active_corner_stack.pop_back();
707
708
      // Corner "a" can correspond either to a normal active edge, or to an edge
709
      // created from the topology split event.
710
519k
      const auto it = topology_split_active_corners.find(symbol_id);
711
519k
      if (it != topology_split_active_corners.end()) {
712
        // Topology split event. Move the retrieved edge to the stack.
713
2
        active_corner_stack.push_back(it->second);
714
2
      }
715
519k
      if (active_corner_stack.empty()) {
716
1
        return -1;
717
1
      }
718
519k
      const CornerIndex corner_a = active_corner_stack.back();
719
720
519k
      if (corner_a == corner_b) {
721
        // All matched corners must be different.
722
0
        return -1;
723
0
      }
724
519k
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex ||
725
519k
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex) {
726
        // One of the corners is already opposite to an existing face, which
727
        // should not happen unless the input was tampered with.
728
1
        return -1;
729
1
      }
730
731
      // First corner on the new face is corner "x" from the image above.
732
519k
      const CornerIndex corner(3 * face.value());
733
      // Update the opposite corner mapping.
734
519k
      SetOppositeCorners(corner_a, corner + 2);
735
519k
      SetOppositeCorners(corner_b, corner + 1);
736
      // Update vertices. For the vertex at corner "x", use the vertex id from
737
      // the corner "p".
738
519k
      const VertexIndex vertex_p =
739
519k
          corner_table_->Vertex(corner_table_->Previous(corner_a));
740
519k
      corner_table_->MapCornerToVertex(corner, vertex_p);
741
519k
      corner_table_->MapCornerToVertex(
742
519k
          corner + 1, corner_table_->Vertex(corner_table_->Next(corner_a)));
743
519k
      const VertexIndex vert_b_prev =
744
519k
          corner_table_->Vertex(corner_table_->Previous(corner_b));
745
519k
      corner_table_->MapCornerToVertex(corner + 2, vert_b_prev);
746
519k
      corner_table_->SetLeftMostCorner(vert_b_prev, corner + 2);
747
519k
      CornerIndex corner_n = corner_table_->Next(corner_b);
748
519k
      const VertexIndex vertex_n = corner_table_->Vertex(corner_n);
749
519k
      traversal_decoder_.MergeVertices(vertex_p, vertex_n);
750
      // Update the left most corner on the newly merged vertex.
751
519k
      corner_table_->SetLeftMostCorner(vertex_p,
752
519k
                                       corner_table_->LeftMostCorner(vertex_n));
753
754
      // Also update the vertex id at corner "n" and all corners that are
755
      // connected to it in the CCW direction.
756
519k
      const CornerIndex first_corner = corner_n;
757
29.3M
      while (corner_n != kInvalidCornerIndex) {
758
28.7M
        corner_table_->MapCornerToVertex(corner_n, vertex_p);
759
28.7M
        corner_n = corner_table_->SwingLeft(corner_n);
760
28.7M
        if (corner_n == first_corner) {
761
          // We reached the start again which should not happen for split
762
          // symbols.
763
0
          return -1;
764
0
        }
765
28.7M
      }
766
      // Make sure the old vertex n is now mapped to an invalid corner (make it
767
      // isolated).
768
519k
      corner_table_->MakeVertexIsolated(vertex_n);
769
519k
      if (remove_invalid_vertices) {
770
507k
        invalid_vertices.push_back(vertex_n);
771
507k
      }
772
519k
      active_corner_stack.back() = corner;
773
964k
    } else if (symbol == TOPOLOGY_E) {
774
964k
      const CornerIndex corner(3 * face.value());
775
964k
      const VertexIndex first_vert_index = corner_table_->AddNewVertex();
776
      // Create three new vertices at the corners of the new face.
777
964k
      corner_table_->MapCornerToVertex(corner, first_vert_index);
778
964k
      corner_table_->MapCornerToVertex(corner + 1,
779
964k
                                       corner_table_->AddNewVertex());
780
964k
      corner_table_->MapCornerToVertex(corner + 2,
781
964k
                                       corner_table_->AddNewVertex());
782
783
964k
      if (corner_table_->num_vertices() > max_num_vertices) {
784
1
        return -1;  // Unexpected number of decoded vertices.
785
1
      }
786
787
964k
      corner_table_->SetLeftMostCorner(first_vert_index, corner);
788
964k
      corner_table_->SetLeftMostCorner(first_vert_index + 1, corner + 1);
789
964k
      corner_table_->SetLeftMostCorner(first_vert_index + 2, corner + 2);
790
      // Add the tip corner to the active stack.
791
964k
      active_corner_stack.push_back(corner);
792
964k
      check_topology_split = true;
793
964k
    } else {
794
      // Error. Unknown symbol decoded.
795
0
      return -1;
796
0
    }
797
    // Inform the traversal decoder that a new corner has been reached.
798
4.25M
    traversal_decoder_.NewActiveCornerReached(active_corner_stack.back());
799
800
4.25M
    if (check_topology_split) {
801
      // Check for topology splits happens only for TOPOLOGY_L, TOPOLOGY_R and
802
      // TOPOLOGY_E symbols because those are the symbols that correspond to
803
      // faces that can be directly connected a TOPOLOGY_S face through the
804
      // topology split event.
805
      // If a topology split is detected, we need to add a new active edge
806
      // onto the active_corner_stack because it will be used later when the
807
      // corresponding TOPOLOGY_S event is decoded.
808
809
      // Symbol id used by the encoder (reverse).
810
1.69M
      const int encoder_symbol_id = num_symbols - symbol_id - 1;
811
1.69M
      EdgeFaceName split_edge;
812
1.69M
      int encoder_split_symbol_id;
813
1.69M
      while (IsTopologySplit(encoder_symbol_id, &split_edge,
814
1.69M
                             &encoder_split_symbol_id)) {
815
103
        if (encoder_split_symbol_id < 0) {
816
2
          return -1;  // Wrong split symbol id.
817
2
        }
818
        // Symbol was part of a topology split. Now we need to determine which
819
        // edge should be added to the active edges stack.
820
101
        const CornerIndex act_top_corner = active_corner_stack.back();
821
        // The current symbol has one active edge (stored in act_top_corner) and
822
        // two remaining inactive edges that are attached to it.
823
        //              *
824
        //             / \
825
        //  left_edge /   \ right_edge
826
        //           /     \
827
        //          *.......*
828
        //         active_edge
829
830
101
        CornerIndex new_active_corner;
831
101
        if (split_edge == RIGHT_FACE_EDGE) {
832
61
          new_active_corner = corner_table_->Next(act_top_corner);
833
61
        } else {
834
40
          new_active_corner = corner_table_->Previous(act_top_corner);
835
40
        }
836
        // Add the new active edge.
837
        // Convert the encoder split symbol id to decoder symbol id.
838
101
        const int decoder_split_symbol_id =
839
101
            num_symbols - encoder_split_symbol_id - 1;
840
101
        topology_split_active_corners[decoder_split_symbol_id] =
841
101
            new_active_corner;
842
101
      }
843
1.69M
    }
844
4.25M
  }
845
225
  if (corner_table_->num_vertices() > max_num_vertices) {
846
0
    return -1;  // Unexpected number of decoded vertices.
847
0
  }
848
  // Decode start faces and connect them to the faces from the active stack.
849
5.72k
  while (!active_corner_stack.empty()) {
850
5.51k
    const CornerIndex corner = active_corner_stack.back();
851
5.51k
    active_corner_stack.pop_back();
852
5.51k
    const bool interior_face =
853
5.51k
        traversal_decoder_.DecodeStartFaceConfiguration();
854
5.51k
    if (interior_face) {
855
      // The start face is interior, we need to find three corners that are
856
      // opposite to it. The first opposite corner "a" is the corner from the
857
      // top of the active corner stack and the remaining two corners "b" and
858
      // "c" are then the next corners from the left-most corners of vertices
859
      // "n" and "x" respectively.
860
      //
861
      //           *-------*
862
      //          / \     / \
863
      //         /   \   /   \
864
      //        /     \ /     \
865
      //       *-------p-------*
866
      //      / \a    . .    c/ \
867
      //     /   \   .   .   /   \
868
      //    /     \ .  I  . /     \
869
      //   *-------n.......x------*
870
      //    \     / \     / \     /
871
      //     \   /   \   /   \   /
872
      //      \ /     \b/     \ /
873
      //       *-------*-------*
874
      //
875
876
3.55k
      if (num_faces >= corner_table_->num_faces()) {
877
0
        return -1;  // More faces than expected added to the mesh.
878
0
      }
879
880
3.55k
      const CornerIndex corner_a = corner;
881
3.55k
      const VertexIndex vert_n =
882
3.55k
          corner_table_->Vertex(corner_table_->Next(corner_a));
883
3.55k
      const CornerIndex corner_b =
884
3.55k
          corner_table_->Next(corner_table_->LeftMostCorner(vert_n));
885
886
3.55k
      const VertexIndex vert_x =
887
3.55k
          corner_table_->Vertex(corner_table_->Next(corner_b));
888
3.55k
      const CornerIndex corner_c =
889
3.55k
          corner_table_->Next(corner_table_->LeftMostCorner(vert_x));
890
891
3.55k
      if (corner == corner_b || corner == corner_c || corner_b == corner_c) {
892
        // All matched corners must be different.
893
13
        return -1;
894
13
      }
895
3.54k
      if (corner_table_->Opposite(corner) != kInvalidCornerIndex ||
896
3.54k
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex ||
897
3.54k
          corner_table_->Opposite(corner_c) != kInvalidCornerIndex) {
898
        // One of the corners is already opposite to an existing face, which
899
        // should not happen unless the input was tampered with.
900
0
        return -1;
901
0
      }
902
903
3.54k
      const VertexIndex vert_p =
904
3.54k
          corner_table_->Vertex(corner_table_->Next(corner_c));
905
906
3.54k
      const FaceIndex face(num_faces++);
907
      // The first corner of the initial face is the corner opposite to "a".
908
3.54k
      const CornerIndex new_corner(3 * face.value());
909
3.54k
      SetOppositeCorners(new_corner, corner);
910
3.54k
      SetOppositeCorners(new_corner + 1, corner_b);
911
3.54k
      SetOppositeCorners(new_corner + 2, corner_c);
912
913
      // Map new corners to existing vertices.
914
3.54k
      corner_table_->MapCornerToVertex(new_corner, vert_x);
915
3.54k
      corner_table_->MapCornerToVertex(new_corner + 1, vert_p);
916
3.54k
      corner_table_->MapCornerToVertex(new_corner + 2, vert_n);
917
918
      // Mark all three vertices as interior.
919
14.1k
      for (int ci = 0; ci < 3; ++ci) {
920
10.6k
        is_vert_hole_[corner_table_->Vertex(new_corner + ci).value()] = false;
921
10.6k
      }
922
923
3.54k
      init_face_configurations_.push_back(true);
924
3.54k
      init_corners_.push_back(new_corner);
925
3.54k
    } else {
926
      // The initial face wasn't interior and the traversal had to start from
927
      // an open boundary. In this case no new face is added, but we need to
928
      // keep record about the first opposite corner to this boundary.
929
1.95k
      init_face_configurations_.push_back(false);
930
1.95k
      init_corners_.push_back(corner);
931
1.95k
    }
932
5.51k
  }
933
212
  if (num_faces != corner_table_->num_faces()) {
934
0
    return -1;  // Unexpected number of decoded faces.
935
0
  }
936
937
212
  int num_vertices = corner_table_->num_vertices();
938
  // If any vertex was marked as isolated, we want to remove it from the corner
939
  // table to ensure that all vertices in range <0, num_vertices> are valid.
940
8.54k
  for (const VertexIndex invalid_vert : invalid_vertices) {
941
    // Find the last valid vertex and swap it with the isolated vertex.
942
8.54k
    VertexIndex src_vert(num_vertices - 1);
943
9.87k
    while (corner_table_->LeftMostCorner(src_vert) == kInvalidCornerIndex) {
944
      // The last vertex is invalid, proceed to the previous one.
945
1.33k
      src_vert = VertexIndex(--num_vertices - 1);
946
1.33k
    }
947
8.54k
    if (src_vert < invalid_vert) {
948
1.33k
      continue;  // No need to swap anything.
949
1.33k
    }
950
951
    // Remap all corners mapped to |src_vert| to |invalid_vert|.
952
7.21k
    VertexCornersIterator<CornerTable> vcit(corner_table_.get(), src_vert);
953
50.2k
    for (; !vcit.End(); ++vcit) {
954
43.0k
      const CornerIndex cid = vcit.Corner();
955
43.0k
      if (corner_table_->Vertex(cid) != src_vert) {
956
        // Vertex mapped to |cid| was not |src_vert|. This indicates corrupted
957
        // data and we should terminate the decoding.
958
0
        return -1;
959
0
      }
960
43.0k
      corner_table_->MapCornerToVertex(cid, invalid_vert);
961
43.0k
    }
962
7.21k
    corner_table_->SetLeftMostCorner(invalid_vert,
963
7.21k
                                     corner_table_->LeftMostCorner(src_vert));
964
965
    // Make the |src_vert| invalid.
966
7.21k
    corner_table_->MakeVertexIsolated(src_vert);
967
7.21k
    is_vert_hole_[invalid_vert.value()] = is_vert_hole_[src_vert.value()];
968
7.21k
    is_vert_hole_[src_vert.value()] = false;
969
970
    // The last vertex is now invalid.
971
7.21k
    num_vertices--;
972
7.21k
  }
973
212
  return num_vertices;
974
212
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::DecodeConnectivity(int)
Line
Count
Source
536
139
    int num_symbols) {
537
  // Algorithm does the reverse decoding of the symbols encoded with the
538
  // edgebreaker method. The reverse decoding always keeps track of the active
539
  // edge identified by its opposite corner (active corner). New faces are
540
  // always added to this active edge. There may be multiple active corners at
541
  // one time that either correspond to separate mesh components or to
542
  // sub-components of one mesh that are going to be merged together using the
543
  // TOPOLOGY_S symbol. We can store these active edges on a stack, because the
544
  // decoder always processes only the latest active edge. TOPOLOGY_S then
545
  // removes the top edge from the stack and TOPOLOGY_E adds a new edge to the
546
  // stack.
547
139
  std::vector<CornerIndex> active_corner_stack;
548
549
  // Additional active edges may be added as a result of topology split events.
550
  // They can be added in arbitrary order, but we always know the split symbol
551
  // id they belong to, so we can address them using this symbol id.
552
139
  std::unordered_map<int, CornerIndex> topology_split_active_corners;
553
554
  // Vector used for storing vertices that were marked as isolated during the
555
  // decoding process. Currently used only when the mesh doesn't contain any
556
  // non-position connectivity data.
557
139
  std::vector<VertexIndex> invalid_vertices;
558
139
  const bool remove_invalid_vertices = attribute_data_.empty();
559
560
139
  int max_num_vertices = static_cast<int>(is_vert_hole_.size());
561
139
  int num_faces = 0;
562
55.7M
  for (int symbol_id = 0; symbol_id < num_symbols; ++symbol_id) {
563
55.7M
    const FaceIndex face(num_faces++);
564
    // Used to flag cases where we need to look for topology split events.
565
55.7M
    bool check_topology_split = false;
566
55.7M
    const uint32_t symbol = traversal_decoder_.DecodeSymbol();
567
55.7M
    if (symbol == TOPOLOGY_C) {
568
      // Create a new face between two edges on the open boundary.
569
      // The first edge is opposite to the corner "a" from the image below.
570
      // The other edge is opposite to the corner "b" that can be reached
571
      // through a CCW traversal around the vertex "v".
572
      // One new active boundary edge is created, opposite to the new corner
573
      // "x".
574
      //
575
      //     *-------*
576
      //    / \     / \
577
      //   /   \   /   \
578
      //  /     \ /     \
579
      // *-------v-------*
580
      //  \b    /x\    a/
581
      //   \   /   \   /
582
      //    \ /  C  \ /
583
      //     *.......*
584
585
      // Find the corner "b" from the corner "a" which is the corner on the
586
      // top of the active stack.
587
27.8M
      if (active_corner_stack.empty()) {
588
0
        return -1;
589
0
      }
590
591
27.8M
      const CornerIndex corner_a = active_corner_stack.back();
592
27.8M
      const VertexIndex vertex_x =
593
27.8M
          corner_table_->Vertex(corner_table_->Next(corner_a));
594
27.8M
      const CornerIndex corner_b =
595
27.8M
          corner_table_->Next(corner_table_->LeftMostCorner(vertex_x));
596
597
27.8M
      if (corner_a == corner_b) {
598
        // All matched corners must be different.
599
0
        return -1;
600
0
      }
601
27.8M
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex ||
602
27.8M
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex) {
603
        // One of the corners is already opposite to an existing face, which
604
        // should not happen unless the input was tampered with.
605
0
        return -1;
606
0
      }
607
608
      // New tip corner.
609
27.8M
      const CornerIndex corner(3 * face.value());
610
      // Update opposite corner mappings.
611
27.8M
      SetOppositeCorners(corner_a, corner + 1);
612
27.8M
      SetOppositeCorners(corner_b, corner + 2);
613
614
      // Update vertex mapping.
615
27.8M
      const VertexIndex vert_a_prev =
616
27.8M
          corner_table_->Vertex(corner_table_->Previous(corner_a));
617
27.8M
      const VertexIndex vert_b_next =
618
27.8M
          corner_table_->Vertex(corner_table_->Next(corner_b));
619
27.8M
      if (vertex_x == vert_a_prev || vertex_x == vert_b_next) {
620
        // Encoding is invalid, because face vertices are degenerate.
621
0
        return -1;
622
0
      }
623
27.8M
      corner_table_->MapCornerToVertex(corner, vertex_x);
624
27.8M
      corner_table_->MapCornerToVertex(corner + 1, vert_b_next);
625
27.8M
      corner_table_->MapCornerToVertex(corner + 2, vert_a_prev);
626
27.8M
      corner_table_->SetLeftMostCorner(vert_a_prev, corner + 2);
627
      // Mark the vertex |x| as interior.
628
27.8M
      is_vert_hole_[vertex_x.value()] = false;
629
      // Update the corner on the active stack.
630
27.8M
      active_corner_stack.back() = corner;
631
27.8M
    } else if (symbol == TOPOLOGY_R || symbol == TOPOLOGY_L) {
632
      // Create a new face extending from the open boundary edge opposite to the
633
      // corner "a" from the image below. Two new boundary edges are created
634
      // opposite to corners "r" and "l". New active corner is set to either "r"
635
      // or "l" depending on the decoded symbol. One new vertex is created
636
      // at the opposite corner to corner "a".
637
      //     *-------*
638
      //    /a\     / \
639
      //   /   \   /   \
640
      //  /     \ /     \
641
      // *-------v-------*
642
      //  .l   r.
643
      //   .   .
644
      //    . .
645
      //     *
646
27.8M
      if (active_corner_stack.empty()) {
647
0
        return -1;
648
0
      }
649
27.8M
      const CornerIndex corner_a = active_corner_stack.back();
650
27.8M
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex) {
651
        // Active corner is already opposite to an existing face, which should
652
        // not happen unless the input was tampered with.
653
0
        return -1;
654
0
      }
655
656
      // First corner on the new face is either corner "l" or "r".
657
27.8M
      const CornerIndex corner(3 * face.value());
658
27.8M
      CornerIndex opp_corner, corner_l, corner_r;
659
27.8M
      if (symbol == TOPOLOGY_R) {
660
        // "r" is the new first corner.
661
27.8M
        opp_corner = corner + 2;
662
27.8M
        corner_l = corner + 1;
663
27.8M
        corner_r = corner;
664
27.8M
      } else {
665
        // "l" is the new first corner.
666
420
        opp_corner = corner + 1;
667
420
        corner_l = corner;
668
420
        corner_r = corner + 2;
669
420
      }
670
27.8M
      SetOppositeCorners(opp_corner, corner_a);
671
      // Update vertex mapping.
672
27.8M
      const VertexIndex new_vert_index = corner_table_->AddNewVertex();
673
674
27.8M
      if (corner_table_->num_vertices() > max_num_vertices) {
675
0
        return -1;  // Unexpected number of decoded vertices.
676
0
      }
677
678
27.8M
      corner_table_->MapCornerToVertex(opp_corner, new_vert_index);
679
27.8M
      corner_table_->SetLeftMostCorner(new_vert_index, opp_corner);
680
681
27.8M
      const VertexIndex vertex_r =
682
27.8M
          corner_table_->Vertex(corner_table_->Previous(corner_a));
683
27.8M
      corner_table_->MapCornerToVertex(corner_r, vertex_r);
684
      // Update left-most corner on the vertex on the |corner_r|.
685
27.8M
      corner_table_->SetLeftMostCorner(vertex_r, corner_r);
686
687
27.8M
      corner_table_->MapCornerToVertex(
688
27.8M
          corner_l, corner_table_->Vertex(corner_table_->Next(corner_a)));
689
27.8M
      active_corner_stack.back() = corner;
690
27.8M
      check_topology_split = true;
691
27.8M
    } else if (symbol == TOPOLOGY_S) {
692
      // Create a new face that merges two last active edges from the active
693
      // stack. No new vertex is created, but two vertices at corners "p" and
694
      // "n" need to be merged into a single vertex.
695
      //
696
      // *-------v-------*
697
      //  \a   p/x\n   b/
698
      //   \   /   \   /
699
      //    \ /  S  \ /
700
      //     *.......*
701
      //
702
708
      if (active_corner_stack.empty()) {
703
0
        return -1;
704
0
      }
705
708
      const CornerIndex corner_b = active_corner_stack.back();
706
708
      active_corner_stack.pop_back();
707
708
      // Corner "a" can correspond either to a normal active edge, or to an edge
709
      // created from the topology split event.
710
708
      const auto it = topology_split_active_corners.find(symbol_id);
711
708
      if (it != topology_split_active_corners.end()) {
712
        // Topology split event. Move the retrieved edge to the stack.
713
0
        active_corner_stack.push_back(it->second);
714
0
      }
715
708
      if (active_corner_stack.empty()) {
716
0
        return -1;
717
0
      }
718
708
      const CornerIndex corner_a = active_corner_stack.back();
719
720
708
      if (corner_a == corner_b) {
721
        // All matched corners must be different.
722
0
        return -1;
723
0
      }
724
708
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex ||
725
708
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex) {
726
        // One of the corners is already opposite to an existing face, which
727
        // should not happen unless the input was tampered with.
728
0
        return -1;
729
0
      }
730
731
      // First corner on the new face is corner "x" from the image above.
732
708
      const CornerIndex corner(3 * face.value());
733
      // Update the opposite corner mapping.
734
708
      SetOppositeCorners(corner_a, corner + 2);
735
708
      SetOppositeCorners(corner_b, corner + 1);
736
      // Update vertices. For the vertex at corner "x", use the vertex id from
737
      // the corner "p".
738
708
      const VertexIndex vertex_p =
739
708
          corner_table_->Vertex(corner_table_->Previous(corner_a));
740
708
      corner_table_->MapCornerToVertex(corner, vertex_p);
741
708
      corner_table_->MapCornerToVertex(
742
708
          corner + 1, corner_table_->Vertex(corner_table_->Next(corner_a)));
743
708
      const VertexIndex vert_b_prev =
744
708
          corner_table_->Vertex(corner_table_->Previous(corner_b));
745
708
      corner_table_->MapCornerToVertex(corner + 2, vert_b_prev);
746
708
      corner_table_->SetLeftMostCorner(vert_b_prev, corner + 2);
747
708
      CornerIndex corner_n = corner_table_->Next(corner_b);
748
708
      const VertexIndex vertex_n = corner_table_->Vertex(corner_n);
749
708
      traversal_decoder_.MergeVertices(vertex_p, vertex_n);
750
      // Update the left most corner on the newly merged vertex.
751
708
      corner_table_->SetLeftMostCorner(vertex_p,
752
708
                                       corner_table_->LeftMostCorner(vertex_n));
753
754
      // Also update the vertex id at corner "n" and all corners that are
755
      // connected to it in the CCW direction.
756
708
      const CornerIndex first_corner = corner_n;
757
2.62k
      while (corner_n != kInvalidCornerIndex) {
758
1.91k
        corner_table_->MapCornerToVertex(corner_n, vertex_p);
759
1.91k
        corner_n = corner_table_->SwingLeft(corner_n);
760
1.91k
        if (corner_n == first_corner) {
761
          // We reached the start again which should not happen for split
762
          // symbols.
763
0
          return -1;
764
0
        }
765
1.91k
      }
766
      // Make sure the old vertex n is now mapped to an invalid corner (make it
767
      // isolated).
768
708
      corner_table_->MakeVertexIsolated(vertex_n);
769
708
      if (remove_invalid_vertices) {
770
559
        invalid_vertices.push_back(vertex_n);
771
559
      }
772
708
      active_corner_stack.back() = corner;
773
1.33k
    } else if (symbol == TOPOLOGY_E) {
774
1.33k
      const CornerIndex corner(3 * face.value());
775
1.33k
      const VertexIndex first_vert_index = corner_table_->AddNewVertex();
776
      // Create three new vertices at the corners of the new face.
777
1.33k
      corner_table_->MapCornerToVertex(corner, first_vert_index);
778
1.33k
      corner_table_->MapCornerToVertex(corner + 1,
779
1.33k
                                       corner_table_->AddNewVertex());
780
1.33k
      corner_table_->MapCornerToVertex(corner + 2,
781
1.33k
                                       corner_table_->AddNewVertex());
782
783
1.33k
      if (corner_table_->num_vertices() > max_num_vertices) {
784
0
        return -1;  // Unexpected number of decoded vertices.
785
0
      }
786
787
1.33k
      corner_table_->SetLeftMostCorner(first_vert_index, corner);
788
1.33k
      corner_table_->SetLeftMostCorner(first_vert_index + 1, corner + 1);
789
1.33k
      corner_table_->SetLeftMostCorner(first_vert_index + 2, corner + 2);
790
      // Add the tip corner to the active stack.
791
1.33k
      active_corner_stack.push_back(corner);
792
1.33k
      check_topology_split = true;
793
1.33k
    } else {
794
      // Error. Unknown symbol decoded.
795
0
      return -1;
796
0
    }
797
    // Inform the traversal decoder that a new corner has been reached.
798
55.7M
    traversal_decoder_.NewActiveCornerReached(active_corner_stack.back());
799
800
55.7M
    if (check_topology_split) {
801
      // Check for topology splits happens only for TOPOLOGY_L, TOPOLOGY_R and
802
      // TOPOLOGY_E symbols because those are the symbols that correspond to
803
      // faces that can be directly connected a TOPOLOGY_S face through the
804
      // topology split event.
805
      // If a topology split is detected, we need to add a new active edge
806
      // onto the active_corner_stack because it will be used later when the
807
      // corresponding TOPOLOGY_S event is decoded.
808
809
      // Symbol id used by the encoder (reverse).
810
27.8M
      const int encoder_symbol_id = num_symbols - symbol_id - 1;
811
27.8M
      EdgeFaceName split_edge;
812
27.8M
      int encoder_split_symbol_id;
813
27.8M
      while (IsTopologySplit(encoder_symbol_id, &split_edge,
814
27.8M
                             &encoder_split_symbol_id)) {
815
801
        if (encoder_split_symbol_id < 0) {
816
5
          return -1;  // Wrong split symbol id.
817
5
        }
818
        // Symbol was part of a topology split. Now we need to determine which
819
        // edge should be added to the active edges stack.
820
796
        const CornerIndex act_top_corner = active_corner_stack.back();
821
        // The current symbol has one active edge (stored in act_top_corner) and
822
        // two remaining inactive edges that are attached to it.
823
        //              *
824
        //             / \
825
        //  left_edge /   \ right_edge
826
        //           /     \
827
        //          *.......*
828
        //         active_edge
829
830
796
        CornerIndex new_active_corner;
831
796
        if (split_edge == RIGHT_FACE_EDGE) {
832
230
          new_active_corner = corner_table_->Next(act_top_corner);
833
566
        } else {
834
566
          new_active_corner = corner_table_->Previous(act_top_corner);
835
566
        }
836
        // Add the new active edge.
837
        // Convert the encoder split symbol id to decoder symbol id.
838
796
        const int decoder_split_symbol_id =
839
796
            num_symbols - encoder_split_symbol_id - 1;
840
796
        topology_split_active_corners[decoder_split_symbol_id] =
841
796
            new_active_corner;
842
796
      }
843
27.8M
    }
844
55.7M
  }
845
134
  if (corner_table_->num_vertices() > max_num_vertices) {
846
0
    return -1;  // Unexpected number of decoded vertices.
847
0
  }
848
  // Decode start faces and connect them to the faces from the active stack.
849
725
  while (!active_corner_stack.empty()) {
850
591
    const CornerIndex corner = active_corner_stack.back();
851
591
    active_corner_stack.pop_back();
852
591
    const bool interior_face =
853
591
        traversal_decoder_.DecodeStartFaceConfiguration();
854
591
    if (interior_face) {
855
      // The start face is interior, we need to find three corners that are
856
      // opposite to it. The first opposite corner "a" is the corner from the
857
      // top of the active corner stack and the remaining two corners "b" and
858
      // "c" are then the next corners from the left-most corners of vertices
859
      // "n" and "x" respectively.
860
      //
861
      //           *-------*
862
      //          / \     / \
863
      //         /   \   /   \
864
      //        /     \ /     \
865
      //       *-------p-------*
866
      //      / \a    . .    c/ \
867
      //     /   \   .   .   /   \
868
      //    /     \ .  I  . /     \
869
      //   *-------n.......x------*
870
      //    \     / \     / \     /
871
      //     \   /   \   /   \   /
872
      //      \ /     \b/     \ /
873
      //       *-------*-------*
874
      //
875
876
14
      if (num_faces >= corner_table_->num_faces()) {
877
0
        return -1;  // More faces than expected added to the mesh.
878
0
      }
879
880
14
      const CornerIndex corner_a = corner;
881
14
      const VertexIndex vert_n =
882
14
          corner_table_->Vertex(corner_table_->Next(corner_a));
883
14
      const CornerIndex corner_b =
884
14
          corner_table_->Next(corner_table_->LeftMostCorner(vert_n));
885
886
14
      const VertexIndex vert_x =
887
14
          corner_table_->Vertex(corner_table_->Next(corner_b));
888
14
      const CornerIndex corner_c =
889
14
          corner_table_->Next(corner_table_->LeftMostCorner(vert_x));
890
891
14
      if (corner == corner_b || corner == corner_c || corner_b == corner_c) {
892
        // All matched corners must be different.
893
0
        return -1;
894
0
      }
895
14
      if (corner_table_->Opposite(corner) != kInvalidCornerIndex ||
896
14
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex ||
897
14
          corner_table_->Opposite(corner_c) != kInvalidCornerIndex) {
898
        // One of the corners is already opposite to an existing face, which
899
        // should not happen unless the input was tampered with.
900
0
        return -1;
901
0
      }
902
903
14
      const VertexIndex vert_p =
904
14
          corner_table_->Vertex(corner_table_->Next(corner_c));
905
906
14
      const FaceIndex face(num_faces++);
907
      // The first corner of the initial face is the corner opposite to "a".
908
14
      const CornerIndex new_corner(3 * face.value());
909
14
      SetOppositeCorners(new_corner, corner);
910
14
      SetOppositeCorners(new_corner + 1, corner_b);
911
14
      SetOppositeCorners(new_corner + 2, corner_c);
912
913
      // Map new corners to existing vertices.
914
14
      corner_table_->MapCornerToVertex(new_corner, vert_x);
915
14
      corner_table_->MapCornerToVertex(new_corner + 1, vert_p);
916
14
      corner_table_->MapCornerToVertex(new_corner + 2, vert_n);
917
918
      // Mark all three vertices as interior.
919
56
      for (int ci = 0; ci < 3; ++ci) {
920
42
        is_vert_hole_[corner_table_->Vertex(new_corner + ci).value()] = false;
921
42
      }
922
923
14
      init_face_configurations_.push_back(true);
924
14
      init_corners_.push_back(new_corner);
925
577
    } else {
926
      // The initial face wasn't interior and the traversal had to start from
927
      // an open boundary. In this case no new face is added, but we need to
928
      // keep record about the first opposite corner to this boundary.
929
577
      init_face_configurations_.push_back(false);
930
577
      init_corners_.push_back(corner);
931
577
    }
932
591
  }
933
134
  if (num_faces != corner_table_->num_faces()) {
934
4
    return -1;  // Unexpected number of decoded faces.
935
4
  }
936
937
130
  int num_vertices = corner_table_->num_vertices();
938
  // If any vertex was marked as isolated, we want to remove it from the corner
939
  // table to ensure that all vertices in range <0, num_vertices> are valid.
940
540
  for (const VertexIndex invalid_vert : invalid_vertices) {
941
    // Find the last valid vertex and swap it with the isolated vertex.
942
540
    VertexIndex src_vert(num_vertices - 1);
943
622
    while (corner_table_->LeftMostCorner(src_vert) == kInvalidCornerIndex) {
944
      // The last vertex is invalid, proceed to the previous one.
945
82
      src_vert = VertexIndex(--num_vertices - 1);
946
82
    }
947
540
    if (src_vert < invalid_vert) {
948
82
      continue;  // No need to swap anything.
949
82
    }
950
951
    // Remap all corners mapped to |src_vert| to |invalid_vert|.
952
458
    VertexCornersIterator<CornerTable> vcit(corner_table_.get(), src_vert);
953
2.06k
    for (; !vcit.End(); ++vcit) {
954
1.60k
      const CornerIndex cid = vcit.Corner();
955
1.60k
      if (corner_table_->Vertex(cid) != src_vert) {
956
        // Vertex mapped to |cid| was not |src_vert|. This indicates corrupted
957
        // data and we should terminate the decoding.
958
0
        return -1;
959
0
      }
960
1.60k
      corner_table_->MapCornerToVertex(cid, invalid_vert);
961
1.60k
    }
962
458
    corner_table_->SetLeftMostCorner(invalid_vert,
963
458
                                     corner_table_->LeftMostCorner(src_vert));
964
965
    // Make the |src_vert| invalid.
966
458
    corner_table_->MakeVertexIsolated(src_vert);
967
458
    is_vert_hole_[invalid_vert.value()] = is_vert_hole_[src_vert.value()];
968
458
    is_vert_hole_[src_vert.value()] = false;
969
970
    // The last vertex is now invalid.
971
458
    num_vertices--;
972
458
  }
973
130
  return num_vertices;
974
130
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::DecodeConnectivity(int)
Line
Count
Source
536
187
    int num_symbols) {
537
  // Algorithm does the reverse decoding of the symbols encoded with the
538
  // edgebreaker method. The reverse decoding always keeps track of the active
539
  // edge identified by its opposite corner (active corner). New faces are
540
  // always added to this active edge. There may be multiple active corners at
541
  // one time that either correspond to separate mesh components or to
542
  // sub-components of one mesh that are going to be merged together using the
543
  // TOPOLOGY_S symbol. We can store these active edges on a stack, because the
544
  // decoder always processes only the latest active edge. TOPOLOGY_S then
545
  // removes the top edge from the stack and TOPOLOGY_E adds a new edge to the
546
  // stack.
547
187
  std::vector<CornerIndex> active_corner_stack;
548
549
  // Additional active edges may be added as a result of topology split events.
550
  // They can be added in arbitrary order, but we always know the split symbol
551
  // id they belong to, so we can address them using this symbol id.
552
187
  std::unordered_map<int, CornerIndex> topology_split_active_corners;
553
554
  // Vector used for storing vertices that were marked as isolated during the
555
  // decoding process. Currently used only when the mesh doesn't contain any
556
  // non-position connectivity data.
557
187
  std::vector<VertexIndex> invalid_vertices;
558
187
  const bool remove_invalid_vertices = attribute_data_.empty();
559
560
187
  int max_num_vertices = static_cast<int>(is_vert_hole_.size());
561
187
  int num_faces = 0;
562
953k
  for (int symbol_id = 0; symbol_id < num_symbols; ++symbol_id) {
563
953k
    const FaceIndex face(num_faces++);
564
    // Used to flag cases where we need to look for topology split events.
565
953k
    bool check_topology_split = false;
566
953k
    const uint32_t symbol = traversal_decoder_.DecodeSymbol();
567
953k
    if (symbol == TOPOLOGY_C) {
568
      // Create a new face between two edges on the open boundary.
569
      // The first edge is opposite to the corner "a" from the image below.
570
      // The other edge is opposite to the corner "b" that can be reached
571
      // through a CCW traversal around the vertex "v".
572
      // One new active boundary edge is created, opposite to the new corner
573
      // "x".
574
      //
575
      //     *-------*
576
      //    / \     / \
577
      //   /   \   /   \
578
      //  /     \ /     \
579
      // *-------v-------*
580
      //  \b    /x\    a/
581
      //   \   /   \   /
582
      //    \ /  C  \ /
583
      //     *.......*
584
585
      // Find the corner "b" from the corner "a" which is the corner on the
586
      // top of the active stack.
587
27.7k
      if (active_corner_stack.empty()) {
588
45
        return -1;
589
45
      }
590
591
27.6k
      const CornerIndex corner_a = active_corner_stack.back();
592
27.6k
      const VertexIndex vertex_x =
593
27.6k
          corner_table_->Vertex(corner_table_->Next(corner_a));
594
27.6k
      const CornerIndex corner_b =
595
27.6k
          corner_table_->Next(corner_table_->LeftMostCorner(vertex_x));
596
597
27.6k
      if (corner_a == corner_b) {
598
        // All matched corners must be different.
599
35
        return -1;
600
35
      }
601
27.6k
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex ||
602
27.6k
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex) {
603
        // One of the corners is already opposite to an existing face, which
604
        // should not happen unless the input was tampered with.
605
0
        return -1;
606
0
      }
607
608
      // New tip corner.
609
27.6k
      const CornerIndex corner(3 * face.value());
610
      // Update opposite corner mappings.
611
27.6k
      SetOppositeCorners(corner_a, corner + 1);
612
27.6k
      SetOppositeCorners(corner_b, corner + 2);
613
614
      // Update vertex mapping.
615
27.6k
      const VertexIndex vert_a_prev =
616
27.6k
          corner_table_->Vertex(corner_table_->Previous(corner_a));
617
27.6k
      const VertexIndex vert_b_next =
618
27.6k
          corner_table_->Vertex(corner_table_->Next(corner_b));
619
27.6k
      if (vertex_x == vert_a_prev || vertex_x == vert_b_next) {
620
        // Encoding is invalid, because face vertices are degenerate.
621
0
        return -1;
622
0
      }
623
27.6k
      corner_table_->MapCornerToVertex(corner, vertex_x);
624
27.6k
      corner_table_->MapCornerToVertex(corner + 1, vert_b_next);
625
27.6k
      corner_table_->MapCornerToVertex(corner + 2, vert_a_prev);
626
27.6k
      corner_table_->SetLeftMostCorner(vert_a_prev, corner + 2);
627
      // Mark the vertex |x| as interior.
628
27.6k
      is_vert_hole_[vertex_x.value()] = false;
629
      // Update the corner on the active stack.
630
27.6k
      active_corner_stack.back() = corner;
631
925k
    } else if (symbol == TOPOLOGY_R || symbol == TOPOLOGY_L) {
632
      // Create a new face extending from the open boundary edge opposite to the
633
      // corner "a" from the image below. Two new boundary edges are created
634
      // opposite to corners "r" and "l". New active corner is set to either "r"
635
      // or "l" depending on the decoded symbol. One new vertex is created
636
      // at the opposite corner to corner "a".
637
      //     *-------*
638
      //    /a\     / \
639
      //   /   \   /   \
640
      //  /     \ /     \
641
      // *-------v-------*
642
      //  .l   r.
643
      //   .   .
644
      //    . .
645
      //     *
646
924k
      if (active_corner_stack.empty()) {
647
0
        return -1;
648
0
      }
649
924k
      const CornerIndex corner_a = active_corner_stack.back();
650
924k
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex) {
651
        // Active corner is already opposite to an existing face, which should
652
        // not happen unless the input was tampered with.
653
0
        return -1;
654
0
      }
655
656
      // First corner on the new face is either corner "l" or "r".
657
924k
      const CornerIndex corner(3 * face.value());
658
924k
      CornerIndex opp_corner, corner_l, corner_r;
659
924k
      if (symbol == TOPOLOGY_R) {
660
        // "r" is the new first corner.
661
75
        opp_corner = corner + 2;
662
75
        corner_l = corner + 1;
663
75
        corner_r = corner;
664
923k
      } else {
665
        // "l" is the new first corner.
666
923k
        opp_corner = corner + 1;
667
923k
        corner_l = corner;
668
923k
        corner_r = corner + 2;
669
923k
      }
670
924k
      SetOppositeCorners(opp_corner, corner_a);
671
      // Update vertex mapping.
672
924k
      const VertexIndex new_vert_index = corner_table_->AddNewVertex();
673
674
924k
      if (corner_table_->num_vertices() > max_num_vertices) {
675
1
        return -1;  // Unexpected number of decoded vertices.
676
1
      }
677
678
924k
      corner_table_->MapCornerToVertex(opp_corner, new_vert_index);
679
924k
      corner_table_->SetLeftMostCorner(new_vert_index, opp_corner);
680
681
924k
      const VertexIndex vertex_r =
682
924k
          corner_table_->Vertex(corner_table_->Previous(corner_a));
683
924k
      corner_table_->MapCornerToVertex(corner_r, vertex_r);
684
      // Update left-most corner on the vertex on the |corner_r|.
685
924k
      corner_table_->SetLeftMostCorner(vertex_r, corner_r);
686
687
924k
      corner_table_->MapCornerToVertex(
688
924k
          corner_l, corner_table_->Vertex(corner_table_->Next(corner_a)));
689
924k
      active_corner_stack.back() = corner;
690
924k
      check_topology_split = true;
691
924k
    } else if (symbol == TOPOLOGY_S) {
692
      // Create a new face that merges two last active edges from the active
693
      // stack. No new vertex is created, but two vertices at corners "p" and
694
      // "n" need to be merged into a single vertex.
695
      //
696
      // *-------v-------*
697
      //  \a   p/x\n   b/
698
      //   \   /   \   /
699
      //    \ /  S  \ /
700
      //     *.......*
701
      //
702
4
      if (active_corner_stack.empty()) {
703
0
        return -1;
704
0
      }
705
4
      const CornerIndex corner_b = active_corner_stack.back();
706
4
      active_corner_stack.pop_back();
707
708
      // Corner "a" can correspond either to a normal active edge, or to an edge
709
      // created from the topology split event.
710
4
      const auto it = topology_split_active_corners.find(symbol_id);
711
4
      if (it != topology_split_active_corners.end()) {
712
        // Topology split event. Move the retrieved edge to the stack.
713
0
        active_corner_stack.push_back(it->second);
714
0
      }
715
4
      if (active_corner_stack.empty()) {
716
2
        return -1;
717
2
      }
718
2
      const CornerIndex corner_a = active_corner_stack.back();
719
720
2
      if (corner_a == corner_b) {
721
        // All matched corners must be different.
722
0
        return -1;
723
0
      }
724
2
      if (corner_table_->Opposite(corner_a) != kInvalidCornerIndex ||
725
2
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex) {
726
        // One of the corners is already opposite to an existing face, which
727
        // should not happen unless the input was tampered with.
728
0
        return -1;
729
0
      }
730
731
      // First corner on the new face is corner "x" from the image above.
732
2
      const CornerIndex corner(3 * face.value());
733
      // Update the opposite corner mapping.
734
2
      SetOppositeCorners(corner_a, corner + 2);
735
2
      SetOppositeCorners(corner_b, corner + 1);
736
      // Update vertices. For the vertex at corner "x", use the vertex id from
737
      // the corner "p".
738
2
      const VertexIndex vertex_p =
739
2
          corner_table_->Vertex(corner_table_->Previous(corner_a));
740
2
      corner_table_->MapCornerToVertex(corner, vertex_p);
741
2
      corner_table_->MapCornerToVertex(
742
2
          corner + 1, corner_table_->Vertex(corner_table_->Next(corner_a)));
743
2
      const VertexIndex vert_b_prev =
744
2
          corner_table_->Vertex(corner_table_->Previous(corner_b));
745
2
      corner_table_->MapCornerToVertex(corner + 2, vert_b_prev);
746
2
      corner_table_->SetLeftMostCorner(vert_b_prev, corner + 2);
747
2
      CornerIndex corner_n = corner_table_->Next(corner_b);
748
2
      const VertexIndex vertex_n = corner_table_->Vertex(corner_n);
749
2
      traversal_decoder_.MergeVertices(vertex_p, vertex_n);
750
      // Update the left most corner on the newly merged vertex.
751
2
      corner_table_->SetLeftMostCorner(vertex_p,
752
2
                                       corner_table_->LeftMostCorner(vertex_n));
753
754
      // Also update the vertex id at corner "n" and all corners that are
755
      // connected to it in the CCW direction.
756
2
      const CornerIndex first_corner = corner_n;
757
6
      while (corner_n != kInvalidCornerIndex) {
758
4
        corner_table_->MapCornerToVertex(corner_n, vertex_p);
759
4
        corner_n = corner_table_->SwingLeft(corner_n);
760
4
        if (corner_n == first_corner) {
761
          // We reached the start again which should not happen for split
762
          // symbols.
763
0
          return -1;
764
0
        }
765
4
      }
766
      // Make sure the old vertex n is now mapped to an invalid corner (make it
767
      // isolated).
768
2
      corner_table_->MakeVertexIsolated(vertex_n);
769
2
      if (remove_invalid_vertices) {
770
2
        invalid_vertices.push_back(vertex_n);
771
2
      }
772
2
      active_corner_stack.back() = corner;
773
1.41k
    } else if (symbol == TOPOLOGY_E) {
774
1.39k
      const CornerIndex corner(3 * face.value());
775
1.39k
      const VertexIndex first_vert_index = corner_table_->AddNewVertex();
776
      // Create three new vertices at the corners of the new face.
777
1.39k
      corner_table_->MapCornerToVertex(corner, first_vert_index);
778
1.39k
      corner_table_->MapCornerToVertex(corner + 1,
779
1.39k
                                       corner_table_->AddNewVertex());
780
1.39k
      corner_table_->MapCornerToVertex(corner + 2,
781
1.39k
                                       corner_table_->AddNewVertex());
782
783
1.39k
      if (corner_table_->num_vertices() > max_num_vertices) {
784
0
        return -1;  // Unexpected number of decoded vertices.
785
0
      }
786
787
1.39k
      corner_table_->SetLeftMostCorner(first_vert_index, corner);
788
1.39k
      corner_table_->SetLeftMostCorner(first_vert_index + 1, corner + 1);
789
1.39k
      corner_table_->SetLeftMostCorner(first_vert_index + 2, corner + 2);
790
      // Add the tip corner to the active stack.
791
1.39k
      active_corner_stack.push_back(corner);
792
1.39k
      check_topology_split = true;
793
1.39k
    } else {
794
      // Error. Unknown symbol decoded.
795
25
      return -1;
796
25
    }
797
    // Inform the traversal decoder that a new corner has been reached.
798
953k
    traversal_decoder_.NewActiveCornerReached(active_corner_stack.back());
799
800
953k
    if (check_topology_split) {
801
      // Check for topology splits happens only for TOPOLOGY_L, TOPOLOGY_R and
802
      // TOPOLOGY_E symbols because those are the symbols that correspond to
803
      // faces that can be directly connected a TOPOLOGY_S face through the
804
      // topology split event.
805
      // If a topology split is detected, we need to add a new active edge
806
      // onto the active_corner_stack because it will be used later when the
807
      // corresponding TOPOLOGY_S event is decoded.
808
809
      // Symbol id used by the encoder (reverse).
810
925k
      const int encoder_symbol_id = num_symbols - symbol_id - 1;
811
925k
      EdgeFaceName split_edge;
812
925k
      int encoder_split_symbol_id;
813
925k
      while (IsTopologySplit(encoder_symbol_id, &split_edge,
814
925k
                             &encoder_split_symbol_id)) {
815
376
        if (encoder_split_symbol_id < 0) {
816
0
          return -1;  // Wrong split symbol id.
817
0
        }
818
        // Symbol was part of a topology split. Now we need to determine which
819
        // edge should be added to the active edges stack.
820
376
        const CornerIndex act_top_corner = active_corner_stack.back();
821
        // The current symbol has one active edge (stored in act_top_corner) and
822
        // two remaining inactive edges that are attached to it.
823
        //              *
824
        //             / \
825
        //  left_edge /   \ right_edge
826
        //           /     \
827
        //          *.......*
828
        //         active_edge
829
830
376
        CornerIndex new_active_corner;
831
376
        if (split_edge == RIGHT_FACE_EDGE) {
832
100
          new_active_corner = corner_table_->Next(act_top_corner);
833
276
        } else {
834
276
          new_active_corner = corner_table_->Previous(act_top_corner);
835
276
        }
836
        // Add the new active edge.
837
        // Convert the encoder split symbol id to decoder symbol id.
838
376
        const int decoder_split_symbol_id =
839
376
            num_symbols - encoder_split_symbol_id - 1;
840
376
        topology_split_active_corners[decoder_split_symbol_id] =
841
376
            new_active_corner;
842
376
      }
843
925k
    }
844
953k
  }
845
79
  if (corner_table_->num_vertices() > max_num_vertices) {
846
0
    return -1;  // Unexpected number of decoded vertices.
847
0
  }
848
  // Decode start faces and connect them to the faces from the active stack.
849
156
  while (!active_corner_stack.empty()) {
850
78
    const CornerIndex corner = active_corner_stack.back();
851
78
    active_corner_stack.pop_back();
852
78
    const bool interior_face =
853
78
        traversal_decoder_.DecodeStartFaceConfiguration();
854
78
    if (interior_face) {
855
      // The start face is interior, we need to find three corners that are
856
      // opposite to it. The first opposite corner "a" is the corner from the
857
      // top of the active corner stack and the remaining two corners "b" and
858
      // "c" are then the next corners from the left-most corners of vertices
859
      // "n" and "x" respectively.
860
      //
861
      //           *-------*
862
      //          / \     / \
863
      //         /   \   /   \
864
      //        /     \ /     \
865
      //       *-------p-------*
866
      //      / \a    . .    c/ \
867
      //     /   \   .   .   /   \
868
      //    /     \ .  I  . /     \
869
      //   *-------n.......x------*
870
      //    \     / \     / \     /
871
      //     \   /   \   /   \   /
872
      //      \ /     \b/     \ /
873
      //       *-------*-------*
874
      //
875
876
1
      if (num_faces >= corner_table_->num_faces()) {
877
1
        return -1;  // More faces than expected added to the mesh.
878
1
      }
879
880
0
      const CornerIndex corner_a = corner;
881
0
      const VertexIndex vert_n =
882
0
          corner_table_->Vertex(corner_table_->Next(corner_a));
883
0
      const CornerIndex corner_b =
884
0
          corner_table_->Next(corner_table_->LeftMostCorner(vert_n));
885
886
0
      const VertexIndex vert_x =
887
0
          corner_table_->Vertex(corner_table_->Next(corner_b));
888
0
      const CornerIndex corner_c =
889
0
          corner_table_->Next(corner_table_->LeftMostCorner(vert_x));
890
891
0
      if (corner == corner_b || corner == corner_c || corner_b == corner_c) {
892
        // All matched corners must be different.
893
0
        return -1;
894
0
      }
895
0
      if (corner_table_->Opposite(corner) != kInvalidCornerIndex ||
896
0
          corner_table_->Opposite(corner_b) != kInvalidCornerIndex ||
897
0
          corner_table_->Opposite(corner_c) != kInvalidCornerIndex) {
898
        // One of the corners is already opposite to an existing face, which
899
        // should not happen unless the input was tampered with.
900
0
        return -1;
901
0
      }
902
903
0
      const VertexIndex vert_p =
904
0
          corner_table_->Vertex(corner_table_->Next(corner_c));
905
906
0
      const FaceIndex face(num_faces++);
907
      // The first corner of the initial face is the corner opposite to "a".
908
0
      const CornerIndex new_corner(3 * face.value());
909
0
      SetOppositeCorners(new_corner, corner);
910
0
      SetOppositeCorners(new_corner + 1, corner_b);
911
0
      SetOppositeCorners(new_corner + 2, corner_c);
912
913
      // Map new corners to existing vertices.
914
0
      corner_table_->MapCornerToVertex(new_corner, vert_x);
915
0
      corner_table_->MapCornerToVertex(new_corner + 1, vert_p);
916
0
      corner_table_->MapCornerToVertex(new_corner + 2, vert_n);
917
918
      // Mark all three vertices as interior.
919
0
      for (int ci = 0; ci < 3; ++ci) {
920
0
        is_vert_hole_[corner_table_->Vertex(new_corner + ci).value()] = false;
921
0
      }
922
923
0
      init_face_configurations_.push_back(true);
924
0
      init_corners_.push_back(new_corner);
925
77
    } else {
926
      // The initial face wasn't interior and the traversal had to start from
927
      // an open boundary. In this case no new face is added, but we need to
928
      // keep record about the first opposite corner to this boundary.
929
77
      init_face_configurations_.push_back(false);
930
77
      init_corners_.push_back(corner);
931
77
    }
932
78
  }
933
78
  if (num_faces != corner_table_->num_faces()) {
934
0
    return -1;  // Unexpected number of decoded faces.
935
0
  }
936
937
78
  int num_vertices = corner_table_->num_vertices();
938
  // If any vertex was marked as isolated, we want to remove it from the corner
939
  // table to ensure that all vertices in range <0, num_vertices> are valid.
940
78
  for (const VertexIndex invalid_vert : invalid_vertices) {
941
    // Find the last valid vertex and swap it with the isolated vertex.
942
2
    VertexIndex src_vert(num_vertices - 1);
943
2
    while (corner_table_->LeftMostCorner(src_vert) == kInvalidCornerIndex) {
944
      // The last vertex is invalid, proceed to the previous one.
945
0
      src_vert = VertexIndex(--num_vertices - 1);
946
0
    }
947
2
    if (src_vert < invalid_vert) {
948
0
      continue;  // No need to swap anything.
949
0
    }
950
951
    // Remap all corners mapped to |src_vert| to |invalid_vert|.
952
2
    VertexCornersIterator<CornerTable> vcit(corner_table_.get(), src_vert);
953
20
    for (; !vcit.End(); ++vcit) {
954
18
      const CornerIndex cid = vcit.Corner();
955
18
      if (corner_table_->Vertex(cid) != src_vert) {
956
        // Vertex mapped to |cid| was not |src_vert|. This indicates corrupted
957
        // data and we should terminate the decoding.
958
0
        return -1;
959
0
      }
960
18
      corner_table_->MapCornerToVertex(cid, invalid_vert);
961
18
    }
962
2
    corner_table_->SetLeftMostCorner(invalid_vert,
963
2
                                     corner_table_->LeftMostCorner(src_vert));
964
965
    // Make the |src_vert| invalid.
966
2
    corner_table_->MakeVertexIsolated(src_vert);
967
2
    is_vert_hole_[invalid_vert.value()] = is_vert_hole_[src_vert.value()];
968
2
    is_vert_hole_[src_vert.value()] = false;
969
970
    // The last vertex is now invalid.
971
2
    num_vertices--;
972
2
  }
973
78
  return num_vertices;
974
78
}
975
976
template <class TraversalDecoder>
977
int32_t
978
MeshEdgebreakerDecoderImpl<TraversalDecoder>::DecodeHoleAndTopologySplitEvents(
979
824
    DecoderBuffer *decoder_buffer) {
980
  // Prepare a new decoder from the provided buffer offset.
981
824
  uint32_t num_topology_splits;
982
824
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
983
824
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
984
171
    if (!decoder_buffer->Decode(&num_topology_splits)) {
985
0
      return -1;
986
0
    }
987
988
171
  } else
989
653
#endif
990
653
  {
991
653
    if (!DecodeVarint(&num_topology_splits, decoder_buffer)) {
992
0
      return -1;
993
0
    }
994
653
  }
995
824
  if (num_topology_splits > 0) {
996
296
    if (num_topology_splits >
997
296
        static_cast<uint32_t>(corner_table_->num_faces())) {
998
7
      return -1;
999
7
    }
1000
289
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1001
289
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) {
1002
190k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1003
190k
        TopologySplitEventData event_data;
1004
190k
        if (!decoder_buffer->Decode(&event_data.split_symbol_id)) {
1005
14
          return -1;
1006
14
        }
1007
190k
        if (!decoder_buffer->Decode(&event_data.source_symbol_id)) {
1008
11
          return -1;
1009
11
        }
1010
190k
        uint8_t edge_data;
1011
190k
        if (!decoder_buffer->Decode(&edge_data)) {
1012
1
          return -1;
1013
1
        }
1014
190k
        event_data.source_edge = edge_data & 1;
1015
190k
        topology_split_data_.push_back(event_data);
1016
190k
      }
1017
1018
38
    } else
1019
251
#endif
1020
251
    {
1021
      // Decode source and split symbol ids using delta and varint coding. See
1022
      // description in mesh_edgebreaker_encoder_impl.cc for more details.
1023
251
      int last_source_symbol_id = 0;
1024
3.75k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1025
3.50k
        TopologySplitEventData event_data;
1026
3.50k
        uint32_t delta;
1027
3.50k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1028
0
          return -1;
1029
0
        }
1030
3.50k
        event_data.source_symbol_id = delta + last_source_symbol_id;
1031
3.50k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1032
1
          return -1;
1033
1
        }
1034
3.50k
        if (delta > event_data.source_symbol_id) {
1035
2
          return -1;
1036
2
        }
1037
3.50k
        event_data.split_symbol_id =
1038
3.50k
            event_data.source_symbol_id - static_cast<int32_t>(delta);
1039
3.50k
        last_source_symbol_id = event_data.source_symbol_id;
1040
3.50k
        topology_split_data_.push_back(event_data);
1041
3.50k
      }
1042
      // Split edges are decoded from a direct bit decoder.
1043
248
      decoder_buffer->StartBitDecoding(false, nullptr);
1044
3.25k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1045
3.00k
        uint32_t edge_data;
1046
3.00k
        if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
1047
1.90k
          decoder_buffer->DecodeLeastSignificantBits32(2, &edge_data);
1048
1.90k
        } else {
1049
1.10k
          decoder_buffer->DecodeLeastSignificantBits32(1, &edge_data);
1050
1.10k
        }
1051
3.00k
        TopologySplitEventData &event_data = topology_split_data_[i];
1052
3.00k
        event_data.source_edge = edge_data & 1;
1053
3.00k
      }
1054
248
      decoder_buffer->EndBitDecoding();
1055
248
    }
1056
289
  }
1057
788
  uint32_t num_hole_events = 0;
1058
788
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1059
788
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
1060
140
    if (!decoder_buffer->Decode(&num_hole_events)) {
1061
0
      return -1;
1062
0
    }
1063
648
  } else if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) {
1064
143
    if (!DecodeVarint(&num_hole_events, decoder_buffer)) {
1065
3
      return -1;
1066
3
    }
1067
143
  }
1068
785
#endif
1069
785
  if (num_hole_events > 0) {
1070
55
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1071
55
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) {
1072
596k
      for (uint32_t i = 0; i < num_hole_events; ++i) {
1073
596k
        HoleEventData event_data;
1074
596k
        if (!decoder_buffer->Decode(&event_data)) {
1075
31
          return -1;
1076
31
        }
1077
596k
        hole_event_data_.push_back(event_data);
1078
596k
      }
1079
1080
34
    } else
1081
21
#endif
1082
21
    {
1083
      // Decode hole symbol ids using delta and varint coding.
1084
21
      int last_symbol_id = 0;
1085
114k
      for (uint32_t i = 0; i < num_hole_events; ++i) {
1086
114k
        HoleEventData event_data;
1087
114k
        uint32_t delta;
1088
114k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1089
11
          return -1;
1090
11
        }
1091
114k
        event_data.symbol_id = delta + last_symbol_id;
1092
114k
        last_symbol_id = event_data.symbol_id;
1093
114k
        hole_event_data_.push_back(event_data);
1094
114k
      }
1095
21
    }
1096
55
  }
1097
743
  return static_cast<int32_t>(decoder_buffer->decoded_size());
1098
785
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::DecodeHoleAndTopologySplitEvents(draco::DecoderBuffer*)
Line
Count
Source
979
302
    DecoderBuffer *decoder_buffer) {
980
  // Prepare a new decoder from the provided buffer offset.
981
302
  uint32_t num_topology_splits;
982
302
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
983
302
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
984
25
    if (!decoder_buffer->Decode(&num_topology_splits)) {
985
0
      return -1;
986
0
    }
987
988
25
  } else
989
277
#endif
990
277
  {
991
277
    if (!DecodeVarint(&num_topology_splits, decoder_buffer)) {
992
0
      return -1;
993
0
    }
994
277
  }
995
302
  if (num_topology_splits > 0) {
996
65
    if (num_topology_splits >
997
65
        static_cast<uint32_t>(corner_table_->num_faces())) {
998
1
      return -1;
999
1
    }
1000
64
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1001
64
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) {
1002
151k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1003
151k
        TopologySplitEventData event_data;
1004
151k
        if (!decoder_buffer->Decode(&event_data.split_symbol_id)) {
1005
8
          return -1;
1006
8
        }
1007
151k
        if (!decoder_buffer->Decode(&event_data.source_symbol_id)) {
1008
2
          return -1;
1009
2
        }
1010
151k
        uint8_t edge_data;
1011
151k
        if (!decoder_buffer->Decode(&edge_data)) {
1012
1
          return -1;
1013
1
        }
1014
151k
        event_data.source_edge = edge_data & 1;
1015
151k
        topology_split_data_.push_back(event_data);
1016
151k
      }
1017
1018
15
    } else
1019
49
#endif
1020
49
    {
1021
      // Decode source and split symbol ids using delta and varint coding. See
1022
      // description in mesh_edgebreaker_encoder_impl.cc for more details.
1023
49
      int last_source_symbol_id = 0;
1024
525
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1025
476
        TopologySplitEventData event_data;
1026
476
        uint32_t delta;
1027
476
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1028
0
          return -1;
1029
0
        }
1030
476
        event_data.source_symbol_id = delta + last_source_symbol_id;
1031
476
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1032
0
          return -1;
1033
0
        }
1034
476
        if (delta > event_data.source_symbol_id) {
1035
0
          return -1;
1036
0
        }
1037
476
        event_data.split_symbol_id =
1038
476
            event_data.source_symbol_id - static_cast<int32_t>(delta);
1039
476
        last_source_symbol_id = event_data.source_symbol_id;
1040
476
        topology_split_data_.push_back(event_data);
1041
476
      }
1042
      // Split edges are decoded from a direct bit decoder.
1043
49
      decoder_buffer->StartBitDecoding(false, nullptr);
1044
525
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1045
476
        uint32_t edge_data;
1046
476
        if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
1047
220
          decoder_buffer->DecodeLeastSignificantBits32(2, &edge_data);
1048
256
        } else {
1049
256
          decoder_buffer->DecodeLeastSignificantBits32(1, &edge_data);
1050
256
        }
1051
476
        TopologySplitEventData &event_data = topology_split_data_[i];
1052
476
        event_data.source_edge = edge_data & 1;
1053
476
      }
1054
49
      decoder_buffer->EndBitDecoding();
1055
49
    }
1056
64
  }
1057
290
  uint32_t num_hole_events = 0;
1058
290
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1059
290
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
1060
13
    if (!decoder_buffer->Decode(&num_hole_events)) {
1061
0
      return -1;
1062
0
    }
1063
277
  } else if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) {
1064
12
    if (!DecodeVarint(&num_hole_events, decoder_buffer)) {
1065
1
      return -1;
1066
1
    }
1067
12
  }
1068
289
#endif
1069
289
  if (num_hole_events > 0) {
1070
17
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1071
17
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) {
1072
9.40k
      for (uint32_t i = 0; i < num_hole_events; ++i) {
1073
9.40k
        HoleEventData event_data;
1074
9.40k
        if (!decoder_buffer->Decode(&event_data)) {
1075
7
          return -1;
1076
7
        }
1077
9.39k
        hole_event_data_.push_back(event_data);
1078
9.39k
      }
1079
1080
8
    } else
1081
9
#endif
1082
9
    {
1083
      // Decode hole symbol ids using delta and varint coding.
1084
9
      int last_symbol_id = 0;
1085
102k
      for (uint32_t i = 0; i < num_hole_events; ++i) {
1086
102k
        HoleEventData event_data;
1087
102k
        uint32_t delta;
1088
102k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1089
9
          return -1;
1090
9
        }
1091
102k
        event_data.symbol_id = delta + last_symbol_id;
1092
102k
        last_symbol_id = event_data.symbol_id;
1093
102k
        hole_event_data_.push_back(event_data);
1094
102k
      }
1095
9
    }
1096
17
  }
1097
273
  return static_cast<int32_t>(decoder_buffer->decoded_size());
1098
289
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::DecodeHoleAndTopologySplitEvents(draco::DecoderBuffer*)
Line
Count
Source
979
178
    DecoderBuffer *decoder_buffer) {
980
  // Prepare a new decoder from the provided buffer offset.
981
178
  uint32_t num_topology_splits;
982
178
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
983
178
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
984
30
    if (!decoder_buffer->Decode(&num_topology_splits)) {
985
0
      return -1;
986
0
    }
987
988
30
  } else
989
148
#endif
990
148
  {
991
148
    if (!DecodeVarint(&num_topology_splits, decoder_buffer)) {
992
0
      return -1;
993
0
    }
994
148
  }
995
178
  if (num_topology_splits > 0) {
996
132
    if (num_topology_splits >
997
132
        static_cast<uint32_t>(corner_table_->num_faces())) {
998
5
      return -1;
999
5
    }
1000
127
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1001
127
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) {
1002
4.87k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1003
4.87k
        TopologySplitEventData event_data;
1004
4.87k
        if (!decoder_buffer->Decode(&event_data.split_symbol_id)) {
1005
3
          return -1;
1006
3
        }
1007
4.86k
        if (!decoder_buffer->Decode(&event_data.source_symbol_id)) {
1008
4
          return -1;
1009
4
        }
1010
4.86k
        uint8_t edge_data;
1011
4.86k
        if (!decoder_buffer->Decode(&edge_data)) {
1012
0
          return -1;
1013
0
        }
1014
4.86k
        event_data.source_edge = edge_data & 1;
1015
4.86k
        topology_split_data_.push_back(event_data);
1016
4.86k
      }
1017
1018
10
    } else
1019
117
#endif
1020
117
    {
1021
      // Decode source and split symbol ids using delta and varint coding. See
1022
      // description in mesh_edgebreaker_encoder_impl.cc for more details.
1023
117
      int last_source_symbol_id = 0;
1024
1.35k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1025
1.23k
        TopologySplitEventData event_data;
1026
1.23k
        uint32_t delta;
1027
1.23k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1028
0
          return -1;
1029
0
        }
1030
1.23k
        event_data.source_symbol_id = delta + last_source_symbol_id;
1031
1.23k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1032
0
          return -1;
1033
0
        }
1034
1.23k
        if (delta > event_data.source_symbol_id) {
1035
2
          return -1;
1036
2
        }
1037
1.23k
        event_data.split_symbol_id =
1038
1.23k
            event_data.source_symbol_id - static_cast<int32_t>(delta);
1039
1.23k
        last_source_symbol_id = event_data.source_symbol_id;
1040
1.23k
        topology_split_data_.push_back(event_data);
1041
1.23k
      }
1042
      // Split edges are decoded from a direct bit decoder.
1043
115
      decoder_buffer->StartBitDecoding(false, nullptr);
1044
1.34k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1045
1.23k
        uint32_t edge_data;
1046
1.23k
        if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
1047
1.23k
          decoder_buffer->DecodeLeastSignificantBits32(2, &edge_data);
1048
1.23k
        } else {
1049
0
          decoder_buffer->DecodeLeastSignificantBits32(1, &edge_data);
1050
0
        }
1051
1.23k
        TopologySplitEventData &event_data = topology_split_data_[i];
1052
1.23k
        event_data.source_edge = edge_data & 1;
1053
1.23k
      }
1054
115
      decoder_buffer->EndBitDecoding();
1055
115
    }
1056
127
  }
1057
164
  uint32_t num_hole_events = 0;
1058
164
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1059
164
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
1060
20
    if (!decoder_buffer->Decode(&num_hole_events)) {
1061
0
      return -1;
1062
0
    }
1063
144
  } else if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) {
1064
115
    if (!DecodeVarint(&num_hole_events, decoder_buffer)) {
1065
1
      return -1;
1066
1
    }
1067
115
  }
1068
163
#endif
1069
163
  if (num_hole_events > 0) {
1070
24
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1071
24
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) {
1072
451k
      for (uint32_t i = 0; i < num_hole_events; ++i) {
1073
451k
        HoleEventData event_data;
1074
451k
        if (!decoder_buffer->Decode(&event_data)) {
1075
13
          return -1;
1076
13
        }
1077
451k
        hole_event_data_.push_back(event_data);
1078
451k
      }
1079
1080
15
    } else
1081
9
#endif
1082
9
    {
1083
      // Decode hole symbol ids using delta and varint coding.
1084
9
      int last_symbol_id = 0;
1085
2.43k
      for (uint32_t i = 0; i < num_hole_events; ++i) {
1086
2.42k
        HoleEventData event_data;
1087
2.42k
        uint32_t delta;
1088
2.42k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1089
1
          return -1;
1090
1
        }
1091
2.42k
        event_data.symbol_id = delta + last_symbol_id;
1092
2.42k
        last_symbol_id = event_data.symbol_id;
1093
2.42k
        hole_event_data_.push_back(event_data);
1094
2.42k
      }
1095
9
    }
1096
24
  }
1097
149
  return static_cast<int32_t>(decoder_buffer->decoded_size());
1098
163
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::DecodeHoleAndTopologySplitEvents(draco::DecoderBuffer*)
Line
Count
Source
979
344
    DecoderBuffer *decoder_buffer) {
980
  // Prepare a new decoder from the provided buffer offset.
981
344
  uint32_t num_topology_splits;
982
344
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
983
344
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
984
116
    if (!decoder_buffer->Decode(&num_topology_splits)) {
985
0
      return -1;
986
0
    }
987
988
116
  } else
989
228
#endif
990
228
  {
991
228
    if (!DecodeVarint(&num_topology_splits, decoder_buffer)) {
992
0
      return -1;
993
0
    }
994
228
  }
995
344
  if (num_topology_splits > 0) {
996
99
    if (num_topology_splits >
997
99
        static_cast<uint32_t>(corner_table_->num_faces())) {
998
1
      return -1;
999
1
    }
1000
98
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1001
98
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) {
1002
33.5k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1003
33.5k
        TopologySplitEventData event_data;
1004
33.5k
        if (!decoder_buffer->Decode(&event_data.split_symbol_id)) {
1005
3
          return -1;
1006
3
        }
1007
33.5k
        if (!decoder_buffer->Decode(&event_data.source_symbol_id)) {
1008
5
          return -1;
1009
5
        }
1010
33.5k
        uint8_t edge_data;
1011
33.5k
        if (!decoder_buffer->Decode(&edge_data)) {
1012
0
          return -1;
1013
0
        }
1014
33.5k
        event_data.source_edge = edge_data & 1;
1015
33.5k
        topology_split_data_.push_back(event_data);
1016
33.5k
      }
1017
1018
13
    } else
1019
85
#endif
1020
85
    {
1021
      // Decode source and split symbol ids using delta and varint coding. See
1022
      // description in mesh_edgebreaker_encoder_impl.cc for more details.
1023
85
      int last_source_symbol_id = 0;
1024
1.87k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1025
1.79k
        TopologySplitEventData event_data;
1026
1.79k
        uint32_t delta;
1027
1.79k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1028
0
          return -1;
1029
0
        }
1030
1.79k
        event_data.source_symbol_id = delta + last_source_symbol_id;
1031
1.79k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1032
1
          return -1;
1033
1
        }
1034
1.79k
        if (delta > event_data.source_symbol_id) {
1035
0
          return -1;
1036
0
        }
1037
1.79k
        event_data.split_symbol_id =
1038
1.79k
            event_data.source_symbol_id - static_cast<int32_t>(delta);
1039
1.79k
        last_source_symbol_id = event_data.source_symbol_id;
1040
1.79k
        topology_split_data_.push_back(event_data);
1041
1.79k
      }
1042
      // Split edges are decoded from a direct bit decoder.
1043
84
      decoder_buffer->StartBitDecoding(false, nullptr);
1044
1.38k
      for (uint32_t i = 0; i < num_topology_splits; ++i) {
1045
1.30k
        uint32_t edge_data;
1046
1.30k
        if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 2)) {
1047
456
          decoder_buffer->DecodeLeastSignificantBits32(2, &edge_data);
1048
846
        } else {
1049
846
          decoder_buffer->DecodeLeastSignificantBits32(1, &edge_data);
1050
846
        }
1051
1.30k
        TopologySplitEventData &event_data = topology_split_data_[i];
1052
1.30k
        event_data.source_edge = edge_data & 1;
1053
1.30k
      }
1054
84
      decoder_buffer->EndBitDecoding();
1055
84
    }
1056
98
  }
1057
334
  uint32_t num_hole_events = 0;
1058
334
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1059
334
  if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 0)) {
1060
107
    if (!decoder_buffer->Decode(&num_hole_events)) {
1061
0
      return -1;
1062
0
    }
1063
227
  } else if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(2, 1)) {
1064
16
    if (!DecodeVarint(&num_hole_events, decoder_buffer)) {
1065
1
      return -1;
1066
1
    }
1067
16
  }
1068
333
#endif
1069
333
  if (num_hole_events > 0) {
1070
14
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1071
14
    if (decoder_->bitstream_version() < DRACO_BITSTREAM_VERSION(1, 2)) {
1072
135k
      for (uint32_t i = 0; i < num_hole_events; ++i) {
1073
135k
        HoleEventData event_data;
1074
135k
        if (!decoder_buffer->Decode(&event_data)) {
1075
11
          return -1;
1076
11
        }
1077
135k
        hole_event_data_.push_back(event_data);
1078
135k
      }
1079
1080
11
    } else
1081
3
#endif
1082
3
    {
1083
      // Decode hole symbol ids using delta and varint coding.
1084
3
      int last_symbol_id = 0;
1085
9.47k
      for (uint32_t i = 0; i < num_hole_events; ++i) {
1086
9.47k
        HoleEventData event_data;
1087
9.47k
        uint32_t delta;
1088
9.47k
        if (!DecodeVarint<uint32_t>(&delta, decoder_buffer)) {
1089
1
          return -1;
1090
1
        }
1091
9.47k
        event_data.symbol_id = delta + last_symbol_id;
1092
9.47k
        last_symbol_id = event_data.symbol_id;
1093
9.47k
        hole_event_data_.push_back(event_data);
1094
9.47k
      }
1095
3
    }
1096
14
  }
1097
321
  return static_cast<int32_t>(decoder_buffer->decoded_size());
1098
333
}
1099
1100
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1101
template <class TraversalDecoder>
1102
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::
1103
162k
    DecodeAttributeConnectivitiesOnFaceLegacy(CornerIndex corner) {
1104
  // Three corners of the face.
1105
162k
  const CornerIndex corners[3] = {corner, corner_table_->Next(corner),
1106
162k
                                  corner_table_->Previous(corner)};
1107
1108
651k
  for (int c = 0; c < 3; ++c) {
1109
488k
    const CornerIndex opp_corner = corner_table_->Opposite(corners[c]);
1110
488k
    if (opp_corner == kInvalidCornerIndex) {
1111
      // Don't decode attribute seams on boundary edges (every boundary edge
1112
      // is automatically an attribute seam).
1113
4.25k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1114
2.13k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1115
2.13k
      }
1116
2.11k
      continue;
1117
2.11k
    }
1118
1119
973k
    for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1120
486k
      const bool is_seam = traversal_decoder_.DecodeAttributeSeam(i);
1121
486k
      if (is_seam) {
1122
166k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1123
166k
      }
1124
486k
    }
1125
486k
  }
1126
162k
  return true;
1127
162k
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::DecodeAttributeConnectivitiesOnFaceLegacy(draco::IndexType<unsigned int, draco::CornerIndex_tag_type_>)
Line
Count
Source
1103
48
    DecodeAttributeConnectivitiesOnFaceLegacy(CornerIndex corner) {
1104
  // Three corners of the face.
1105
48
  const CornerIndex corners[3] = {corner, corner_table_->Next(corner),
1106
48
                                  corner_table_->Previous(corner)};
1107
1108
192
  for (int c = 0; c < 3; ++c) {
1109
144
    const CornerIndex opp_corner = corner_table_->Opposite(corners[c]);
1110
144
    if (opp_corner == kInvalidCornerIndex) {
1111
      // Don't decode attribute seams on boundary edges (every boundary edge
1112
      // is automatically an attribute seam).
1113
21
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1114
13
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1115
13
      }
1116
8
      continue;
1117
8
    }
1118
1119
408
    for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1120
272
      const bool is_seam = traversal_decoder_.DecodeAttributeSeam(i);
1121
272
      if (is_seam) {
1122
116
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1123
116
      }
1124
272
    }
1125
136
  }
1126
48
  return true;
1127
48
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::DecodeAttributeConnectivitiesOnFaceLegacy(draco::IndexType<unsigned int, draco::CornerIndex_tag_type_>)
Line
Count
Source
1103
162k
    DecodeAttributeConnectivitiesOnFaceLegacy(CornerIndex corner) {
1104
  // Three corners of the face.
1105
162k
  const CornerIndex corners[3] = {corner, corner_table_->Next(corner),
1106
162k
                                  corner_table_->Previous(corner)};
1107
1108
651k
  for (int c = 0; c < 3; ++c) {
1109
488k
    const CornerIndex opp_corner = corner_table_->Opposite(corners[c]);
1110
488k
    if (opp_corner == kInvalidCornerIndex) {
1111
      // Don't decode attribute seams on boundary edges (every boundary edge
1112
      // is automatically an attribute seam).
1113
4.23k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1114
2.12k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1115
2.12k
      }
1116
2.10k
      continue;
1117
2.10k
    }
1118
1119
973k
    for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1120
486k
      const bool is_seam = traversal_decoder_.DecodeAttributeSeam(i);
1121
486k
      if (is_seam) {
1122
165k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1123
165k
      }
1124
486k
    }
1125
486k
  }
1126
162k
  return true;
1127
162k
}
Unexecuted instantiation: draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::DecodeAttributeConnectivitiesOnFaceLegacy(draco::IndexType<unsigned int, draco::CornerIndex_tag_type_>)
1128
#endif
1129
1130
template <class TraversalDecoder>
1131
bool MeshEdgebreakerDecoderImpl<
1132
333k
    TraversalDecoder>::DecodeAttributeConnectivitiesOnFace(CornerIndex corner) {
1133
  // Three corners of the face.
1134
333k
  const CornerIndex corners[3] = {corner, corner_table_->Next(corner),
1135
333k
                                  corner_table_->Previous(corner)};
1136
1137
333k
  const FaceIndex src_face_id = corner_table_->Face(corner);
1138
1.33M
  for (int c = 0; c < 3; ++c) {
1139
1.00M
    const CornerIndex opp_corner = corner_table_->Opposite(corners[c]);
1140
1.00M
    if (opp_corner == kInvalidCornerIndex) {
1141
      // Don't decode attribute seams on boundary edges (every boundary edge
1142
      // is automatically an attribute seam).
1143
218k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1144
152k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1145
152k
      }
1146
66.2k
      continue;
1147
66.2k
    }
1148
934k
    const FaceIndex opp_face_id = corner_table_->Face(opp_corner);
1149
    // Don't decode edges when the opposite face has been already processed.
1150
934k
    if (opp_face_id < src_face_id) {
1151
467k
      continue;
1152
467k
    }
1153
1154
1.35M
    for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1155
889k
      const bool is_seam = traversal_decoder_.DecodeAttributeSeam(i);
1156
889k
      if (is_seam) {
1157
444k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1158
444k
      }
1159
889k
    }
1160
467k
  }
1161
333k
  return true;
1162
333k
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::DecodeAttributeConnectivitiesOnFace(draco::IndexType<unsigned int, draco::CornerIndex_tag_type_>)
Line
Count
Source
1132
135k
    TraversalDecoder>::DecodeAttributeConnectivitiesOnFace(CornerIndex corner) {
1133
  // Three corners of the face.
1134
135k
  const CornerIndex corners[3] = {corner, corner_table_->Next(corner),
1135
135k
                                  corner_table_->Previous(corner)};
1136
1137
135k
  const FaceIndex src_face_id = corner_table_->Face(corner);
1138
540k
  for (int c = 0; c < 3; ++c) {
1139
405k
    const CornerIndex opp_corner = corner_table_->Opposite(corners[c]);
1140
405k
    if (opp_corner == kInvalidCornerIndex) {
1141
      // Don't decode attribute seams on boundary edges (every boundary edge
1142
      // is automatically an attribute seam).
1143
59.6k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1144
46.8k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1145
46.8k
      }
1146
12.7k
      continue;
1147
12.7k
    }
1148
392k
    const FaceIndex opp_face_id = corner_table_->Face(opp_corner);
1149
    // Don't decode edges when the opposite face has been already processed.
1150
392k
    if (opp_face_id < src_face_id) {
1151
196k
      continue;
1152
196k
    }
1153
1154
607k
    for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1155
410k
      const bool is_seam = traversal_decoder_.DecodeAttributeSeam(i);
1156
410k
      if (is_seam) {
1157
213k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1158
213k
      }
1159
410k
    }
1160
196k
  }
1161
135k
  return true;
1162
135k
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::DecodeAttributeConnectivitiesOnFace(draco::IndexType<unsigned int, draco::CornerIndex_tag_type_>)
Line
Count
Source
1132
95.6k
    TraversalDecoder>::DecodeAttributeConnectivitiesOnFace(CornerIndex corner) {
1133
  // Three corners of the face.
1134
95.6k
  const CornerIndex corners[3] = {corner, corner_table_->Next(corner),
1135
95.6k
                                  corner_table_->Previous(corner)};
1136
1137
95.6k
  const FaceIndex src_face_id = corner_table_->Face(corner);
1138
382k
  for (int c = 0; c < 3; ++c) {
1139
286k
    const CornerIndex opp_corner = corner_table_->Opposite(corners[c]);
1140
286k
    if (opp_corner == kInvalidCornerIndex) {
1141
      // Don't decode attribute seams on boundary edges (every boundary edge
1142
      // is automatically an attribute seam).
1143
7.70k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1144
4.72k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1145
4.72k
      }
1146
2.97k
      continue;
1147
2.97k
    }
1148
283k
    const FaceIndex opp_face_id = corner_table_->Face(opp_corner);
1149
    // Don't decode edges when the opposite face has been already processed.
1150
283k
    if (opp_face_id < src_face_id) {
1151
141k
      continue;
1152
141k
    }
1153
1154
362k
    for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1155
220k
      const bool is_seam = traversal_decoder_.DecodeAttributeSeam(i);
1156
220k
      if (is_seam) {
1157
167k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1158
167k
      }
1159
220k
    }
1160
141k
  }
1161
95.6k
  return true;
1162
95.6k
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::DecodeAttributeConnectivitiesOnFace(draco::IndexType<unsigned int, draco::CornerIndex_tag_type_>)
Line
Count
Source
1132
102k
    TraversalDecoder>::DecodeAttributeConnectivitiesOnFace(CornerIndex corner) {
1133
  // Three corners of the face.
1134
102k
  const CornerIndex corners[3] = {corner, corner_table_->Next(corner),
1135
102k
                                  corner_table_->Previous(corner)};
1136
1137
102k
  const FaceIndex src_face_id = corner_table_->Face(corner);
1138
411k
  for (int c = 0; c < 3; ++c) {
1139
308k
    const CornerIndex opp_corner = corner_table_->Opposite(corners[c]);
1140
308k
    if (opp_corner == kInvalidCornerIndex) {
1141
      // Don't decode attribute seams on boundary edges (every boundary edge
1142
      // is automatically an attribute seam).
1143
151k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1144
100k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1145
100k
      }
1146
50.4k
      continue;
1147
50.4k
    }
1148
258k
    const FaceIndex opp_face_id = corner_table_->Face(opp_corner);
1149
    // Don't decode edges when the opposite face has been already processed.
1150
258k
    if (opp_face_id < src_face_id) {
1151
129k
      continue;
1152
129k
    }
1153
1154
387k
    for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1155
258k
      const bool is_seam = traversal_decoder_.DecodeAttributeSeam(i);
1156
258k
      if (is_seam) {
1157
63.6k
        attribute_data_[i].attribute_seam_corners.push_back(corners[c].value());
1158
63.6k
      }
1159
258k
    }
1160
129k
  }
1161
102k
  return true;
1162
102k
}
1163
1164
template <class TraversalDecoder>
1165
bool MeshEdgebreakerDecoderImpl<TraversalDecoder>::AssignPointsToCorners(
1166
420
    int num_connectivity_verts) {
1167
  // Map between the existing and deduplicated point ids.
1168
  // Note that at this point we have one point id for each corner of the
1169
  // mesh so there is corner_table_->num_corners() point ids.
1170
420
  decoder_->mesh()->SetNumFaces(corner_table_->num_faces());
1171
1172
420
  if (attribute_data_.empty()) {
1173
    // We have connectivity for position only. In this case all vertex indices
1174
    // are equal to point indices.
1175
216k
    for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) {
1176
215k
      Mesh::Face face;
1177
215k
      const CornerIndex start_corner(3 * f.value());
1178
863k
      for (int c = 0; c < 3; ++c) {
1179
        // Get the vertex index on the corner and use it as a point index.
1180
647k
        const int32_t vert_id = corner_table_->Vertex(start_corner + c).value();
1181
647k
        face[c] = vert_id;
1182
647k
      }
1183
215k
      decoder_->mesh()->SetFace(f, face);
1184
215k
    }
1185
82
    decoder_->point_cloud()->set_num_points(num_connectivity_verts);
1186
82
    return true;
1187
82
  }
1188
  // Else we need to deduplicate multiple attributes.
1189
1190
  // Map between point id and an associated corner id. Only one corner for
1191
  // each point is stored. The corners are used to sample the attribute values
1192
  // in the last stage of the deduplication.
1193
338
  std::vector<int32_t> point_to_corner_map;
1194
  // Map between every corner and their new point ids.
1195
338
  std::vector<int32_t> corner_to_point_map(corner_table_->num_corners());
1196
296k
  for (int v = 0; v < corner_table_->num_vertices(); ++v) {
1197
295k
    CornerIndex c = corner_table_->LeftMostCorner(VertexIndex(v));
1198
295k
    if (c == kInvalidCornerIndex) {
1199
12.1k
      continue;  // Isolated vertex.
1200
12.1k
    }
1201
283k
    CornerIndex deduplication_first_corner = c;
1202
283k
    if (is_vert_hole_[v]) {
1203
      // If the vertex is on a boundary, start deduplication from the left most
1204
      // corner that is guaranteed to lie on the boundary.
1205
68.3k
      deduplication_first_corner = c;
1206
215k
    } else {
1207
      // If we are not on the boundary we need to find the first seam (of any
1208
      // attribute).
1209
378k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1210
298k
        if (!attribute_data_[i].connectivity_data.IsCornerOnSeam(c)) {
1211
157k
          continue;  // No seam for this attribute, ignore it.
1212
157k
        }
1213
        // Else there needs to be at least one seam edge.
1214
1215
        // At this point, we use identity mapping between corners and point ids.
1216
141k
        const VertexIndex vert_id =
1217
141k
            attribute_data_[i].connectivity_data.Vertex(c);
1218
141k
        CornerIndex act_c = corner_table_->SwingRight(c);
1219
141k
        bool seam_found = false;
1220
182k
        while (act_c != c) {
1221
176k
          if (act_c == kInvalidCornerIndex) {
1222
1
            return false;
1223
1
          }
1224
176k
          if (attribute_data_[i].connectivity_data.Vertex(act_c) != vert_id) {
1225
            // Attribute seam found. Stop.
1226
135k
            deduplication_first_corner = act_c;
1227
135k
            seam_found = true;
1228
135k
            break;
1229
135k
          }
1230
40.9k
          act_c = corner_table_->SwingRight(act_c);
1231
40.9k
        }
1232
141k
        if (seam_found) {
1233
135k
          break;  // No reason to process other attributes if we found a seam.
1234
135k
        }
1235
141k
      }
1236
215k
    }
1237
1238
    // Do a deduplication pass over the corners on the processed vertex.
1239
    // At this point each corner corresponds to one point id and our goal is to
1240
    // merge similar points into a single point id.
1241
    // We do a single pass in a clockwise direction over the corners and we add
1242
    // a new point id whenever one of the attributes change.
1243
283k
    c = deduplication_first_corner;
1244
    // Create a new point.
1245
283k
    corner_to_point_map[c.value()] =
1246
283k
        static_cast<uint32_t>(point_to_corner_map.size());
1247
283k
    point_to_corner_map.push_back(c.value());
1248
    // Traverse in CW direction.
1249
283k
    CornerIndex prev_c = c;
1250
283k
    c = corner_table_->SwingRight(c);
1251
1.48M
    while (c != kInvalidCornerIndex && c != deduplication_first_corner) {
1252
1.20M
      bool attribute_seam = false;
1253
2.19M
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1254
1.73M
        if (attribute_data_[i].connectivity_data.Vertex(c) !=
1255
1.73M
            attribute_data_[i].connectivity_data.Vertex(prev_c)) {
1256
          // Attribute index changed from the previous corner. We need to add a
1257
          // new point here.
1258
745k
          attribute_seam = true;
1259
745k
          break;
1260
745k
        }
1261
1.73M
      }
1262
1.20M
      if (attribute_seam) {
1263
745k
        corner_to_point_map[c.value()] =
1264
745k
            static_cast<uint32_t>(point_to_corner_map.size());
1265
745k
        point_to_corner_map.push_back(c.value());
1266
745k
      } else {
1267
460k
        corner_to_point_map[c.value()] = corner_to_point_map[prev_c.value()];
1268
460k
      }
1269
1.20M
      prev_c = c;
1270
1.20M
      c = corner_table_->SwingRight(c);
1271
1.20M
    }
1272
283k
  }
1273
  // Add faces.
1274
496k
  for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) {
1275
496k
    Mesh::Face face;
1276
1.98M
    for (int c = 0; c < 3; ++c) {
1277
      // Remap old points to the new ones.
1278
1.48M
      face[c] = corner_to_point_map[3 * f.value() + c];
1279
1.48M
    }
1280
496k
    decoder_->mesh()->SetFace(f, face);
1281
496k
  }
1282
337
  decoder_->point_cloud()->set_num_points(
1283
337
      static_cast<uint32_t>(point_to_corner_map.size()));
1284
337
  return true;
1285
338
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalDecoder>::AssignPointsToCorners(int)
Line
Count
Source
1166
212
    int num_connectivity_verts) {
1167
  // Map between the existing and deduplicated point ids.
1168
  // Note that at this point we have one point id for each corner of the
1169
  // mesh so there is corner_table_->num_corners() point ids.
1170
212
  decoder_->mesh()->SetNumFaces(corner_table_->num_faces());
1171
1172
212
  if (attribute_data_.empty()) {
1173
    // We have connectivity for position only. In this case all vertex indices
1174
    // are equal to point indices.
1175
73.8k
    for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) {
1176
73.8k
      Mesh::Face face;
1177
73.8k
      const CornerIndex start_corner(3 * f.value());
1178
295k
      for (int c = 0; c < 3; ++c) {
1179
        // Get the vertex index on the corner and use it as a point index.
1180
221k
        const int32_t vert_id = corner_table_->Vertex(start_corner + c).value();
1181
221k
        face[c] = vert_id;
1182
221k
      }
1183
73.8k
      decoder_->mesh()->SetFace(f, face);
1184
73.8k
    }
1185
9
    decoder_->point_cloud()->set_num_points(num_connectivity_verts);
1186
9
    return true;
1187
9
  }
1188
  // Else we need to deduplicate multiple attributes.
1189
1190
  // Map between point id and an associated corner id. Only one corner for
1191
  // each point is stored. The corners are used to sample the attribute values
1192
  // in the last stage of the deduplication.
1193
203
  std::vector<int32_t> point_to_corner_map;
1194
  // Map between every corner and their new point ids.
1195
203
  std::vector<int32_t> corner_to_point_map(corner_table_->num_corners());
1196
87.2k
  for (int v = 0; v < corner_table_->num_vertices(); ++v) {
1197
87.0k
    CornerIndex c = corner_table_->LeftMostCorner(VertexIndex(v));
1198
87.0k
    if (c == kInvalidCornerIndex) {
1199
12.0k
      continue;  // Isolated vertex.
1200
12.0k
    }
1201
75.0k
    CornerIndex deduplication_first_corner = c;
1202
75.0k
    if (is_vert_hole_[v]) {
1203
      // If the vertex is on a boundary, start deduplication from the left most
1204
      // corner that is guaranteed to lie on the boundary.
1205
12.7k
      deduplication_first_corner = c;
1206
62.2k
    } else {
1207
      // If we are not on the boundary we need to find the first seam (of any
1208
      // attribute).
1209
124k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1210
114k
        if (!attribute_data_[i].connectivity_data.IsCornerOnSeam(c)) {
1211
57.6k
          continue;  // No seam for this attribute, ignore it.
1212
57.6k
        }
1213
        // Else there needs to be at least one seam edge.
1214
1215
        // At this point, we use identity mapping between corners and point ids.
1216
56.6k
        const VertexIndex vert_id =
1217
56.6k
            attribute_data_[i].connectivity_data.Vertex(c);
1218
56.6k
        CornerIndex act_c = corner_table_->SwingRight(c);
1219
56.6k
        bool seam_found = false;
1220
91.2k
        while (act_c != c) {
1221
86.2k
          if (act_c == kInvalidCornerIndex) {
1222
1
            return false;
1223
1
          }
1224
86.2k
          if (attribute_data_[i].connectivity_data.Vertex(act_c) != vert_id) {
1225
            // Attribute seam found. Stop.
1226
51.6k
            deduplication_first_corner = act_c;
1227
51.6k
            seam_found = true;
1228
51.6k
            break;
1229
51.6k
          }
1230
34.5k
          act_c = corner_table_->SwingRight(act_c);
1231
34.5k
        }
1232
56.6k
        if (seam_found) {
1233
51.6k
          break;  // No reason to process other attributes if we found a seam.
1234
51.6k
        }
1235
56.6k
      }
1236
62.2k
    }
1237
1238
    // Do a deduplication pass over the corners on the processed vertex.
1239
    // At this point each corner corresponds to one point id and our goal is to
1240
    // merge similar points into a single point id.
1241
    // We do a single pass in a clockwise direction over the corners and we add
1242
    // a new point id whenever one of the attributes change.
1243
75.0k
    c = deduplication_first_corner;
1244
    // Create a new point.
1245
75.0k
    corner_to_point_map[c.value()] =
1246
75.0k
        static_cast<uint32_t>(point_to_corner_map.size());
1247
75.0k
    point_to_corner_map.push_back(c.value());
1248
    // Traverse in CW direction.
1249
75.0k
    CornerIndex prev_c = c;
1250
75.0k
    c = corner_table_->SwingRight(c);
1251
405k
    while (c != kInvalidCornerIndex && c != deduplication_first_corner) {
1252
330k
      bool attribute_seam = false;
1253
655k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1254
599k
        if (attribute_data_[i].connectivity_data.Vertex(c) !=
1255
599k
            attribute_data_[i].connectivity_data.Vertex(prev_c)) {
1256
          // Attribute index changed from the previous corner. We need to add a
1257
          // new point here.
1258
274k
          attribute_seam = true;
1259
274k
          break;
1260
274k
        }
1261
599k
      }
1262
330k
      if (attribute_seam) {
1263
274k
        corner_to_point_map[c.value()] =
1264
274k
            static_cast<uint32_t>(point_to_corner_map.size());
1265
274k
        point_to_corner_map.push_back(c.value());
1266
274k
      } else {
1267
55.0k
        corner_to_point_map[c.value()] = corner_to_point_map[prev_c.value()];
1268
55.0k
      }
1269
330k
      prev_c = c;
1270
330k
      c = corner_table_->SwingRight(c);
1271
330k
    }
1272
75.0k
  }
1273
  // Add faces.
1274
135k
  for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) {
1275
134k
    Mesh::Face face;
1276
539k
    for (int c = 0; c < 3; ++c) {
1277
      // Remap old points to the new ones.
1278
404k
      face[c] = corner_to_point_map[3 * f.value() + c];
1279
404k
    }
1280
134k
    decoder_->mesh()->SetFace(f, face);
1281
134k
  }
1282
202
  decoder_->point_cloud()->set_num_points(
1283
202
      static_cast<uint32_t>(point_to_corner_map.size()));
1284
202
  return true;
1285
203
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalPredictiveDecoder>::AssignPointsToCorners(int)
Line
Count
Source
1166
130
    int num_connectivity_verts) {
1167
  // Map between the existing and deduplicated point ids.
1168
  // Note that at this point we have one point id for each corner of the
1169
  // mesh so there is corner_table_->num_corners() point ids.
1170
130
  decoder_->mesh()->SetNumFaces(corner_table_->num_faces());
1171
1172
130
  if (attribute_data_.empty()) {
1173
    // We have connectivity for position only. In this case all vertex indices
1174
    // are equal to point indices.
1175
137k
    for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) {
1176
137k
      Mesh::Face face;
1177
137k
      const CornerIndex start_corner(3 * f.value());
1178
548k
      for (int c = 0; c < 3; ++c) {
1179
        // Get the vertex index on the corner and use it as a point index.
1180
411k
        const int32_t vert_id = corner_table_->Vertex(start_corner + c).value();
1181
411k
        face[c] = vert_id;
1182
411k
      }
1183
137k
      decoder_->mesh()->SetFace(f, face);
1184
137k
    }
1185
13
    decoder_->point_cloud()->set_num_points(num_connectivity_verts);
1186
13
    return true;
1187
13
  }
1188
  // Else we need to deduplicate multiple attributes.
1189
1190
  // Map between point id and an associated corner id. Only one corner for
1191
  // each point is stored. The corners are used to sample the attribute values
1192
  // in the last stage of the deduplication.
1193
117
  std::vector<int32_t> point_to_corner_map;
1194
  // Map between every corner and their new point ids.
1195
117
  std::vector<int32_t> corner_to_point_map(corner_table_->num_corners());
1196
132k
  for (int v = 0; v < corner_table_->num_vertices(); ++v) {
1197
132k
    CornerIndex c = corner_table_->LeftMostCorner(VertexIndex(v));
1198
132k
    if (c == kInvalidCornerIndex) {
1199
144
      continue;  // Isolated vertex.
1200
144
    }
1201
132k
    CornerIndex deduplication_first_corner = c;
1202
132k
    if (is_vert_hole_[v]) {
1203
      // If the vertex is on a boundary, start deduplication from the left most
1204
      // corner that is guaranteed to lie on the boundary.
1205
5.08k
      deduplication_first_corner = c;
1206
126k
    } else {
1207
      // If we are not on the boundary we need to find the first seam (of any
1208
      // attribute).
1209
187k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1210
132k
        if (!attribute_data_[i].connectivity_data.IsCornerOnSeam(c)) {
1211
59.9k
          continue;  // No seam for this attribute, ignore it.
1212
59.9k
        }
1213
        // Else there needs to be at least one seam edge.
1214
1215
        // At this point, we use identity mapping between corners and point ids.
1216
72.2k
        const VertexIndex vert_id =
1217
72.2k
            attribute_data_[i].connectivity_data.Vertex(c);
1218
72.2k
        CornerIndex act_c = corner_table_->SwingRight(c);
1219
72.2k
        bool seam_found = false;
1220
78.6k
        while (act_c != c) {
1221
77.8k
          if (act_c == kInvalidCornerIndex) {
1222
0
            return false;
1223
0
          }
1224
77.8k
          if (attribute_data_[i].connectivity_data.Vertex(act_c) != vert_id) {
1225
            // Attribute seam found. Stop.
1226
71.4k
            deduplication_first_corner = act_c;
1227
71.4k
            seam_found = true;
1228
71.4k
            break;
1229
71.4k
          }
1230
6.42k
          act_c = corner_table_->SwingRight(act_c);
1231
6.42k
        }
1232
72.2k
        if (seam_found) {
1233
71.4k
          break;  // No reason to process other attributes if we found a seam.
1234
71.4k
        }
1235
72.2k
      }
1236
126k
    }
1237
1238
    // Do a deduplication pass over the corners on the processed vertex.
1239
    // At this point each corner corresponds to one point id and our goal is to
1240
    // merge similar points into a single point id.
1241
    // We do a single pass in a clockwise direction over the corners and we add
1242
    // a new point id whenever one of the attributes change.
1243
132k
    c = deduplication_first_corner;
1244
    // Create a new point.
1245
132k
    corner_to_point_map[c.value()] =
1246
132k
        static_cast<uint32_t>(point_to_corner_map.size());
1247
132k
    point_to_corner_map.push_back(c.value());
1248
    // Traverse in CW direction.
1249
132k
    CornerIndex prev_c = c;
1250
132k
    c = corner_table_->SwingRight(c);
1251
775k
    while (c != kInvalidCornerIndex && c != deduplication_first_corner) {
1252
643k
      bool attribute_seam = false;
1253
958k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1254
669k
        if (attribute_data_[i].connectivity_data.Vertex(c) !=
1255
669k
            attribute_data_[i].connectivity_data.Vertex(prev_c)) {
1256
          // Attribute index changed from the previous corner. We need to add a
1257
          // new point here.
1258
355k
          attribute_seam = true;
1259
355k
          break;
1260
355k
        }
1261
669k
      }
1262
643k
      if (attribute_seam) {
1263
355k
        corner_to_point_map[c.value()] =
1264
355k
            static_cast<uint32_t>(point_to_corner_map.size());
1265
355k
        point_to_corner_map.push_back(c.value());
1266
355k
      } else {
1267
288k
        corner_to_point_map[c.value()] = corner_to_point_map[prev_c.value()];
1268
288k
      }
1269
643k
      prev_c = c;
1270
643k
      c = corner_table_->SwingRight(c);
1271
643k
    }
1272
132k
  }
1273
  // Add faces.
1274
258k
  for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) {
1275
258k
    Mesh::Face face;
1276
1.03M
    for (int c = 0; c < 3; ++c) {
1277
      // Remap old points to the new ones.
1278
775k
      face[c] = corner_to_point_map[3 * f.value() + c];
1279
775k
    }
1280
258k
    decoder_->mesh()->SetFace(f, face);
1281
258k
  }
1282
117
  decoder_->point_cloud()->set_num_points(
1283
117
      static_cast<uint32_t>(point_to_corner_map.size()));
1284
117
  return true;
1285
117
}
draco::MeshEdgebreakerDecoderImpl<draco::MeshEdgebreakerTraversalValenceDecoder>::AssignPointsToCorners(int)
Line
Count
Source
1166
78
    int num_connectivity_verts) {
1167
  // Map between the existing and deduplicated point ids.
1168
  // Note that at this point we have one point id for each corner of the
1169
  // mesh so there is corner_table_->num_corners() point ids.
1170
78
  decoder_->mesh()->SetNumFaces(corner_table_->num_faces());
1171
1172
78
  if (attribute_data_.empty()) {
1173
    // We have connectivity for position only. In this case all vertex indices
1174
    // are equal to point indices.
1175
5.01k
    for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) {
1176
4.95k
      Mesh::Face face;
1177
4.95k
      const CornerIndex start_corner(3 * f.value());
1178
19.8k
      for (int c = 0; c < 3; ++c) {
1179
        // Get the vertex index on the corner and use it as a point index.
1180
14.8k
        const int32_t vert_id = corner_table_->Vertex(start_corner + c).value();
1181
14.8k
        face[c] = vert_id;
1182
14.8k
      }
1183
4.95k
      decoder_->mesh()->SetFace(f, face);
1184
4.95k
    }
1185
60
    decoder_->point_cloud()->set_num_points(num_connectivity_verts);
1186
60
    return true;
1187
60
  }
1188
  // Else we need to deduplicate multiple attributes.
1189
1190
  // Map between point id and an associated corner id. Only one corner for
1191
  // each point is stored. The corners are used to sample the attribute values
1192
  // in the last stage of the deduplication.
1193
18
  std::vector<int32_t> point_to_corner_map;
1194
  // Map between every corner and their new point ids.
1195
18
  std::vector<int32_t> corner_to_point_map(corner_table_->num_corners());
1196
76.7k
  for (int v = 0; v < corner_table_->num_vertices(); ++v) {
1197
76.6k
    CornerIndex c = corner_table_->LeftMostCorner(VertexIndex(v));
1198
76.6k
    if (c == kInvalidCornerIndex) {
1199
0
      continue;  // Isolated vertex.
1200
0
    }
1201
76.6k
    CornerIndex deduplication_first_corner = c;
1202
76.6k
    if (is_vert_hole_[v]) {
1203
      // If the vertex is on a boundary, start deduplication from the left most
1204
      // corner that is guaranteed to lie on the boundary.
1205
50.4k
      deduplication_first_corner = c;
1206
50.4k
    } else {
1207
      // If we are not on the boundary we need to find the first seam (of any
1208
      // attribute).
1209
66.3k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1210
52.4k
        if (!attribute_data_[i].connectivity_data.IsCornerOnSeam(c)) {
1211
40.1k
          continue;  // No seam for this attribute, ignore it.
1212
40.1k
        }
1213
        // Else there needs to be at least one seam edge.
1214
1215
        // At this point, we use identity mapping between corners and point ids.
1216
12.2k
        const VertexIndex vert_id =
1217
12.2k
            attribute_data_[i].connectivity_data.Vertex(c);
1218
12.2k
        CornerIndex act_c = corner_table_->SwingRight(c);
1219
12.2k
        bool seam_found = false;
1220
12.2k
        while (act_c != c) {
1221
12.2k
          if (act_c == kInvalidCornerIndex) {
1222
0
            return false;
1223
0
          }
1224
12.2k
          if (attribute_data_[i].connectivity_data.Vertex(act_c) != vert_id) {
1225
            // Attribute seam found. Stop.
1226
12.2k
            deduplication_first_corner = act_c;
1227
12.2k
            seam_found = true;
1228
12.2k
            break;
1229
12.2k
          }
1230
0
          act_c = corner_table_->SwingRight(act_c);
1231
0
        }
1232
12.2k
        if (seam_found) {
1233
12.2k
          break;  // No reason to process other attributes if we found a seam.
1234
12.2k
        }
1235
12.2k
      }
1236
26.2k
    }
1237
1238
    // Do a deduplication pass over the corners on the processed vertex.
1239
    // At this point each corner corresponds to one point id and our goal is to
1240
    // merge similar points into a single point id.
1241
    // We do a single pass in a clockwise direction over the corners and we add
1242
    // a new point id whenever one of the attributes change.
1243
76.6k
    c = deduplication_first_corner;
1244
    // Create a new point.
1245
76.6k
    corner_to_point_map[c.value()] =
1246
76.6k
        static_cast<uint32_t>(point_to_corner_map.size());
1247
76.6k
    point_to_corner_map.push_back(c.value());
1248
    // Traverse in CW direction.
1249
76.6k
    CornerIndex prev_c = c;
1250
76.6k
    c = corner_table_->SwingRight(c);
1251
308k
    while (c != kInvalidCornerIndex && c != deduplication_first_corner) {
1252
231k
      bool attribute_seam = false;
1253
580k
      for (uint32_t i = 0; i < attribute_data_.size(); ++i) {
1254
463k
        if (attribute_data_[i].connectivity_data.Vertex(c) !=
1255
463k
            attribute_data_[i].connectivity_data.Vertex(prev_c)) {
1256
          // Attribute index changed from the previous corner. We need to add a
1257
          // new point here.
1258
115k
          attribute_seam = true;
1259
115k
          break;
1260
115k
        }
1261
463k
      }
1262
231k
      if (attribute_seam) {
1263
115k
        corner_to_point_map[c.value()] =
1264
115k
            static_cast<uint32_t>(point_to_corner_map.size());
1265
115k
        point_to_corner_map.push_back(c.value());
1266
116k
      } else {
1267
116k
        corner_to_point_map[c.value()] = corner_to_point_map[prev_c.value()];
1268
116k
      }
1269
231k
      prev_c = c;
1270
231k
      c = corner_table_->SwingRight(c);
1271
231k
    }
1272
76.6k
  }
1273
  // Add faces.
1274
102k
  for (FaceIndex f(0); f < decoder_->mesh()->num_faces(); ++f) {
1275
102k
    Mesh::Face face;
1276
411k
    for (int c = 0; c < 3; ++c) {
1277
      // Remap old points to the new ones.
1278
308k
      face[c] = corner_to_point_map[3 * f.value() + c];
1279
308k
    }
1280
102k
    decoder_->mesh()->SetFace(f, face);
1281
102k
  }
1282
18
  decoder_->point_cloud()->set_num_points(
1283
18
      static_cast<uint32_t>(point_to_corner_map.size()));
1284
18
  return true;
1285
18
}
1286
1287
template class MeshEdgebreakerDecoderImpl<MeshEdgebreakerTraversalDecoder>;
1288
#ifdef DRACO_BACKWARDS_COMPATIBILITY_SUPPORTED
1289
template class MeshEdgebreakerDecoderImpl<
1290
    MeshEdgebreakerTraversalPredictiveDecoder>;
1291
#endif
1292
template class MeshEdgebreakerDecoderImpl<
1293
    MeshEdgebreakerTraversalValenceDecoder>;
1294
}  // namespace draco