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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
|
// 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_TRAVERSER_MAX_PREDICTION_DEGREE_TRAVERSER_H_
#define DRACO_COMPRESSION_MESH_TRAVERSER_MAX_PREDICTION_DEGREE_TRAVERSER_H_
#include <vector>
#include "draco/compression/mesh/traverser/traverser_base.h"
#include "draco/mesh/corner_table.h"
namespace draco {
// PredictionDegreeTraverser provides framework for traversal over a corner
// table data structure following paper "Multi-way Geometry Encoding" by
// Cohen-or at al.'02. The traversal is implicitly guided by prediction degree
// of the destination vertices. A prediction degree is computed as the number of
// possible faces that can be used as source points for traversal to the given
// destination vertex (see image below, where faces F1 and F2 are already
// traversed and face F0 is not traversed yet. The prediction degree of vertex
// V is then equal to two).
//
// X-----V-----o
// / \ / \ / \
// / F0\ / \ / F2\
// X-----o-----o-----B
// \ F1/
// \ /
// A
//
// The class implements the same interface as the DepthFirstTraverser
// (depth_first_traverser.h) and it can be controlled via the same template
// trait classes |CornerTableT| and |TraversalObserverT|, that are used
// for controlling and monitoring of the traversal respectively. For details,
// please see depth_first_traverser.h.
template <class CornerTableT, class TraversalObserverT>
class MaxPredictionDegreeTraverser
: public TraverserBase<CornerTable, TraversalObserverT> {
public:
typedef CornerTableT CornerTable;
typedef TraversalObserverT TraversalObserver;
typedef TraverserBase<CornerTable, TraversalObserver> Base;
MaxPredictionDegreeTraverser() {}
// Called before any traversing starts.
void OnTraversalStart() {
prediction_degree_.resize(this->corner_table()->num_vertices(), 0);
}
// Called when all the traversing is done.
void OnTraversalEnd() {}
bool TraverseFromCorner(CornerIndex corner_id) {
if (prediction_degree_.size() == 0) {
return true;
}
// Traversal starts from the |corner_id|. It's going to follow either the
// right or the left neighboring faces to |corner_id| based on their
// prediction degree.
traversal_stacks_[0].push_back(corner_id);
best_priority_ = 0;
// For the first face, check the remaining corners as they may not be
// processed yet.
const VertexIndex next_vert =
this->corner_table()->Vertex(this->corner_table()->Next(corner_id));
const VertexIndex prev_vert =
this->corner_table()->Vertex(this->corner_table()->Previous(corner_id));
if (!this->IsVertexVisited(next_vert)) {
this->MarkVertexVisited(next_vert);
this->traversal_observer().OnNewVertexVisited(
next_vert, this->corner_table()->Next(corner_id));
}
if (!this->IsVertexVisited(prev_vert)) {
this->MarkVertexVisited(prev_vert);
this->traversal_observer().OnNewVertexVisited(
prev_vert, this->corner_table()->Previous(corner_id));
}
const VertexIndex tip_vertex = this->corner_table()->Vertex(corner_id);
if (!this->IsVertexVisited(tip_vertex)) {
this->MarkVertexVisited(tip_vertex);
this->traversal_observer().OnNewVertexVisited(tip_vertex, corner_id);
}
// Start the actual traversal.
while ((corner_id = PopNextCornerToTraverse()) != kInvalidCornerIndex) {
FaceIndex face_id(corner_id.value() / 3);
// Make sure the face hasn't been visited yet.
if (this->IsFaceVisited(face_id)) {
// This face has been already traversed.
continue;
}
while (true) {
face_id = FaceIndex(corner_id.value() / 3);
this->MarkFaceVisited(face_id);
this->traversal_observer().OnNewFaceVisited(face_id);
// If the newly reached vertex hasn't been visited, mark it and notify
// the observer.
const VertexIndex vert_id = this->corner_table()->Vertex(corner_id);
if (!this->IsVertexVisited(vert_id)) {
this->MarkVertexVisited(vert_id);
this->traversal_observer().OnNewVertexVisited(vert_id, corner_id);
}
// Check whether we can traverse to the right and left neighboring
// faces.
const CornerIndex right_corner_id =
this->corner_table()->GetRightCorner(corner_id);
const CornerIndex left_corner_id =
this->corner_table()->GetLeftCorner(corner_id);
const FaceIndex right_face_id(
(right_corner_id == kInvalidCornerIndex
? kInvalidFaceIndex
: FaceIndex(right_corner_id.value() / 3)));
const FaceIndex left_face_id(
(left_corner_id == kInvalidCornerIndex
? kInvalidFaceIndex
: FaceIndex(left_corner_id.value() / 3)));
const bool is_right_face_visited = this->IsFaceVisited(right_face_id);
const bool is_left_face_visited = this->IsFaceVisited(left_face_id);
if (!is_left_face_visited) {
// We can go to the left face.
const int priority = ComputePriority(left_corner_id);
if (is_right_face_visited && priority <= best_priority_) {
// Right face has been already visited and the priority is equal or
// better than the best priority. We are sure that the left face
// would be traversed next so there is no need to put it onto the
// stack.
corner_id = left_corner_id;
continue;
} else {
AddCornerToTraversalStack(left_corner_id, priority);
}
}
if (!is_right_face_visited) {
// Go to the right face.
const int priority = ComputePriority(right_corner_id);
if (priority <= best_priority_) {
// We are sure that the right face would be traversed next so there
// is no need to put it onto the stack.
corner_id = right_corner_id;
continue;
} else {
AddCornerToTraversalStack(right_corner_id, priority);
}
}
// Couldn't proceed directly to the next corner
break;
}
}
return true;
}
private:
// Retrieves the next available corner (edge) to traverse. Edges are processed
// based on their priorities.
// Returns kInvalidCornerIndex when there is no edge available.
CornerIndex PopNextCornerToTraverse() {
for (int i = best_priority_; i < kMaxPriority; ++i) {
if (!traversal_stacks_[i].empty()) {
const CornerIndex ret = traversal_stacks_[i].back();
traversal_stacks_[i].pop_back();
best_priority_ = i;
return ret;
}
}
return kInvalidCornerIndex;
}
inline void AddCornerToTraversalStack(CornerIndex ci, int priority) {
traversal_stacks_[priority].push_back(ci);
// Make sure that the best available priority is up to date.
if (priority < best_priority_) {
best_priority_ = priority;
}
}
// Returns the priority of traversing edge leading to |corner_id|.
inline int ComputePriority(CornerIndex corner_id) {
const VertexIndex v_tip = this->corner_table()->Vertex(corner_id);
// Priority 0 when traversing to already visited vertices.
int priority = 0;
if (!this->IsVertexVisited(v_tip)) {
const int degree = ++prediction_degree_[v_tip];
// Priority 1 when prediction degree > 1, otherwise 2.
priority = (degree > 1 ? 1 : 2);
}
// Clamp the priority to the maximum number of buckets.
if (priority >= kMaxPriority) {
priority = kMaxPriority - 1;
}
return priority;
}
// For efficiency reasons, the priority traversal is implemented using buckets
// where each buckets represent a stack of available corners for a given
// priority. Corners with the highest priority are always processed first.
static constexpr int kMaxPriority = 3;
std::vector<CornerIndex> traversal_stacks_[kMaxPriority];
// Keep the track of the best available priority to improve the performance
// of PopNextCornerToTraverse() method.
int best_priority_;
// Prediction degree available for each vertex.
IndexTypeVector<VertexIndex, int> prediction_degree_;
};
} // namespace draco
#endif // DRACO_COMPRESSION_MESH_TRAVERSER_MAX_PREDICTION_DEGREE_TRAVERSER_H_
|
