blob: 118687cc769f9f07b9db813d05f23d330eafbcfb (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
// Copyright 2016 The Draco Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
#ifndef DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_PREDICTIVE_ENCODER_H_
#define DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_PREDICTIVE_ENCODER_H_
#include "draco/compression/mesh/mesh_edgebreaker_traversal_encoder.h"
namespace draco {
// Encoder that tries to predict the edgebreaker traversal symbols based on the
// vertex valences of the unencoded portion of the mesh. The current prediction
// scheme assumes that each vertex has valence 6 which can be used to predict
// the symbol preceding the one that is currently encoded. Predictions are
// encoded using an arithmetic coding which can lead to less than 1 bit per
// triangle encoding for highly regular meshes.
class MeshEdgebreakerTraversalPredictiveEncoder
: public MeshEdgebreakerTraversalEncoder {
public:
MeshEdgebreakerTraversalPredictiveEncoder()
: corner_table_(nullptr),
prev_symbol_(-1),
num_split_symbols_(0),
last_corner_(kInvalidCornerIndex),
num_symbols_(0) {}
bool Init(MeshEdgebreakerEncoderImplInterface *encoder) {
if (!MeshEdgebreakerTraversalEncoder::Init(encoder))
return false;
corner_table_ = encoder->GetCornerTable();
// Initialize valences of all vertices.
vertex_valences_.resize(corner_table_->num_vertices());
for (uint32_t i = 0; i < vertex_valences_.size(); ++i) {
vertex_valences_[i] = corner_table_->Valence(VertexIndex(i));
}
return true;
}
inline void NewCornerReached(CornerIndex corner) { last_corner_ = corner; }
inline int32_t ComputePredictedSymbol(VertexIndex pivot) {
const int valence = vertex_valences_[pivot.value()];
if (valence < 0) {
// This situation can happen only for split vertices. Returning
// TOPOLOGY_INVALID always cases misprediction.
return TOPOLOGY_INVALID;
}
if (valence < 6) {
return TOPOLOGY_R;
}
return TOPOLOGY_C;
}
inline void EncodeSymbol(EdgebreakerTopologyBitPattern symbol) {
++num_symbols_;
// Update valences on the mesh. And compute the predicted preceding symbol.
// Note that the valences are computed for the so far unencoded part of the
// mesh. Adding a new symbol either reduces valences on the vertices or
// leaves the valence unchanged.
int32_t predicted_symbol = -1;
const CornerIndex next = corner_table_->Next(last_corner_);
const CornerIndex prev = corner_table_->Previous(last_corner_);
switch (symbol) {
case TOPOLOGY_C:
// Compute prediction.
predicted_symbol = ComputePredictedSymbol(corner_table_->Vertex(next));
FALLTHROUGH_INTENDED;
case TOPOLOGY_S:
// Update valences.
vertex_valences_[corner_table_->Vertex(next).value()] -= 1;
vertex_valences_[corner_table_->Vertex(prev).value()] -= 1;
if (symbol == TOPOLOGY_S) {
// Whenever we reach a split symbol, mark its tip vertex as invalid by
// setting the valence to a negative value. Any prediction that will
// use this vertex will then cause a misprediction. This is currently
// necessary because the decoding works in the reverse direction and
// the decoder doesn't know about these vertices until the split
// symbol is decoded at which point two vertices are merged into one.
// This can be most likely solved on the encoder side by splitting the
// tip vertex into two, but since split symbols are relatively rare,
// it's probably not worth doing it.
vertex_valences_[corner_table_->Vertex(last_corner_).value()] = -1;
++num_split_symbols_;
}
break;
case TOPOLOGY_R:
// Compute prediction.
predicted_symbol = ComputePredictedSymbol(corner_table_->Vertex(next));
// Update valences.
vertex_valences_[corner_table_->Vertex(last_corner_).value()] -= 1;
vertex_valences_[corner_table_->Vertex(next).value()] -= 1;
vertex_valences_[corner_table_->Vertex(prev).value()] -= 2;
break;
case TOPOLOGY_L:
vertex_valences_[corner_table_->Vertex(last_corner_).value()] -= 1;
vertex_valences_[corner_table_->Vertex(next).value()] -= 2;
vertex_valences_[corner_table_->Vertex(prev).value()] -= 1;
break;
case TOPOLOGY_E:
vertex_valences_[corner_table_->Vertex(last_corner_).value()] -= 2;
vertex_valences_[corner_table_->Vertex(next).value()] -= 2;
vertex_valences_[corner_table_->Vertex(prev).value()] -= 2;
break;
default:
break;
}
// Flag used when it's necessary to explicitly store the previous symbol.
bool store_prev_symbol = true;
if (predicted_symbol != -1) {
if (predicted_symbol == prev_symbol_) {
predictions_.push_back(true);
store_prev_symbol = false;
} else if (prev_symbol_ != -1) {
predictions_.push_back(false);
}
}
if (store_prev_symbol && prev_symbol_ != -1) {
MeshEdgebreakerTraversalEncoder::EncodeSymbol(
static_cast<EdgebreakerTopologyBitPattern>(prev_symbol_));
}
prev_symbol_ = symbol;
}
void Done() {
// We still need to store the last encoded symbol.
if (prev_symbol_ != -1) {
MeshEdgebreakerTraversalEncoder::EncodeSymbol(
static_cast<EdgebreakerTopologyBitPattern>(prev_symbol_));
}
// Store the init face configurations and the explicitly encoded symbols.
MeshEdgebreakerTraversalEncoder::Done();
// Encode the number of split symbols.
GetOutputBuffer()->Encode(num_split_symbols_);
// Store the predictions.
BinaryEncoder prediction_encoder;
prediction_encoder.StartEncoding();
for (int i = static_cast<int>(predictions_.size()) - 1; i >= 0; --i) {
prediction_encoder.EncodeBit(predictions_[i]);
}
prediction_encoder.EndEncoding(GetOutputBuffer());
}
int NumEncodedSymbols() const { return num_symbols_; }
private:
const CornerTable *corner_table_;
std::vector<int> vertex_valences_;
std::vector<bool> predictions_;
// Previously encoded symbol.
int32_t prev_symbol_;
// The total number of encoded split symbols.
int32_t num_split_symbols_;
CornerIndex last_corner_;
// Explicitly count the number of encoded symbols.
int num_symbols_;
};
} // namespace draco
#endif // DRACO_COMPRESSION_MESH_MESH_EDGEBREAKER_TRAVERSAL_PREDICTIVE_ENCODER_H_
|
