1 | // Copyright 2011 Google Inc. All Rights Reserved.
|
---|
2 | //
|
---|
3 | // Licensed under the Apache License, Version 2.0 (the "License"); you
|
---|
4 | // may not use this file except in compliance with the License. You
|
---|
5 | // 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
|
---|
12 | // implied. See the License for the specific language governing
|
---|
13 | // permissions and limitations under the License.
|
---|
14 |
|
---|
15 | #ifndef WEBGL_LOADER_OPTIMIZE_H_
|
---|
16 | #define WEBGL_LOADER_OPTIMIZE_H_
|
---|
17 |
|
---|
18 | #include <math.h>
|
---|
19 | #include <stdlib.h>
|
---|
20 | #include <string.h>
|
---|
21 |
|
---|
22 | #include "base.h"
|
---|
23 |
|
---|
24 | // TODO: since most vertices are part of 6 faces, you can optimize
|
---|
25 | // this by using a small inline buffer.
|
---|
26 | typedef std::vector<int> FaceList;
|
---|
27 |
|
---|
28 | // Linear-Speed Vertex Cache Optimisation, via:
|
---|
29 | // http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html
|
---|
30 | class VertexOptimizer {
|
---|
31 | public:
|
---|
32 | struct TriangleData {
|
---|
33 | bool active; // true iff triangle has not been optimized and emitted.
|
---|
34 | // TODO: eliminate some wasted computation by using this cache.
|
---|
35 | // float score;
|
---|
36 | };
|
---|
37 |
|
---|
38 | VertexOptimizer(const QuantizedAttribList& attribs)
|
---|
39 | : attribs_(attribs),
|
---|
40 | per_vertex_(attribs_.size() / 8),
|
---|
41 | next_unused_index_(0)
|
---|
42 | {
|
---|
43 | // The cache has an extra slot allocated to simplify the logic in
|
---|
44 | // InsertIndexToCache.
|
---|
45 | for (unsigned int i = 0; i < kCacheSize + 1; ++i) {
|
---|
46 | cache_[i] = kUnknownIndex;
|
---|
47 | }
|
---|
48 |
|
---|
49 | // Initialize per-vertex state.
|
---|
50 | for (size_t i = 0; i < per_vertex_.size(); ++i) {
|
---|
51 | VertexData& vertex_data = per_vertex_[i];
|
---|
52 | vertex_data.cache_tag = kCacheSize;
|
---|
53 | vertex_data.output_index = kMaxOutputIndex;
|
---|
54 | }
|
---|
55 | }
|
---|
56 |
|
---|
57 | void AddTriangles(const int* indices, size_t length,
|
---|
58 | WebGLMeshList* meshes) {
|
---|
59 | std::vector<TriangleData> per_tri(length / 3);
|
---|
60 |
|
---|
61 | // Loop through the triangles, updating vertex->face lists.
|
---|
62 | for (size_t i = 0; i < per_tri.size(); ++i) {
|
---|
63 | per_tri[i].active = true;
|
---|
64 | per_vertex_[indices[3*i + 0]].faces.push_back(i);
|
---|
65 | per_vertex_[indices[3*i + 1]].faces.push_back(i);
|
---|
66 | per_vertex_[indices[3*i + 2]].faces.push_back(i);
|
---|
67 | }
|
---|
68 |
|
---|
69 | // TODO: with index bounds, no need to recompute everything.
|
---|
70 | // Compute initial vertex scores.
|
---|
71 | for (size_t i = 0; i < per_vertex_.size(); ++i) {
|
---|
72 | VertexData& vertex_data = per_vertex_[i];
|
---|
73 | vertex_data.cache_tag = kCacheSize;
|
---|
74 | vertex_data.output_index = kMaxOutputIndex;
|
---|
75 | vertex_data.UpdateScore();
|
---|
76 | }
|
---|
77 |
|
---|
78 | // Prepare output.
|
---|
79 | if (meshes->empty()) {
|
---|
80 | meshes->push_back(WebGLMesh());
|
---|
81 | }
|
---|
82 | WebGLMesh* mesh = &meshes->back();
|
---|
83 |
|
---|
84 | // Consume indices, one triangle at a time.
|
---|
85 | for (size_t c = 0; c < per_tri.size(); ++c) {
|
---|
86 | const int best_triangle = FindBestTriangle(indices, per_tri);
|
---|
87 | per_tri[best_triangle].active = false;
|
---|
88 |
|
---|
89 | // Iterate through triangle indices.
|
---|
90 | for (size_t i = 0; i < 3; ++i) {
|
---|
91 | const int index = indices[3*best_triangle + i];
|
---|
92 | VertexData& vertex_data = per_vertex_[index];
|
---|
93 | vertex_data.RemoveFace(best_triangle);
|
---|
94 |
|
---|
95 | InsertIndexToCache(index);
|
---|
96 | const int cached_output_index = per_vertex_[index].output_index;
|
---|
97 | // Have we seen this index before?
|
---|
98 | if (cached_output_index != kMaxOutputIndex) {
|
---|
99 | mesh->indices.push_back(cached_output_index);
|
---|
100 | continue;
|
---|
101 | }
|
---|
102 | // The first time we see an index, not only do we increment
|
---|
103 | // next_unused_index_ counter, but we must also copy the
|
---|
104 | // corresponding attributes. TODO: do quantization here?
|
---|
105 | per_vertex_[index].output_index = next_unused_index_;
|
---|
106 | for (size_t j = 0; j < 8; ++j) {
|
---|
107 | mesh->attribs.push_back(attribs_[8*index + j]);
|
---|
108 | }
|
---|
109 | mesh->indices.push_back(next_unused_index_++);
|
---|
110 | }
|
---|
111 | // Check if there is room for another triangle.
|
---|
112 | if (next_unused_index_ > kMaxOutputIndex - 3) {
|
---|
113 | // Is it worth figuring out which other triangles can be added
|
---|
114 | // given the verties already added? Then, perhaps
|
---|
115 | // re-optimizing?
|
---|
116 | next_unused_index_ = 0;
|
---|
117 | meshes->push_back(WebGLMesh());
|
---|
118 | mesh = &meshes->back();
|
---|
119 | for (size_t i = 0; i <= kCacheSize; ++i) {
|
---|
120 | cache_[i] = kUnknownIndex;
|
---|
121 | }
|
---|
122 | for (size_t i = 0; i < per_vertex_.size(); ++i) {
|
---|
123 | per_vertex_[i].output_index = kMaxOutputIndex;
|
---|
124 | }
|
---|
125 | }
|
---|
126 | }
|
---|
127 | }
|
---|
128 | private:
|
---|
129 | static const int kUnknownIndex = -1;
|
---|
130 | static const uint16 kMaxOutputIndex = 0xD800;
|
---|
131 | static const size_t kCacheSize = 32; // Does larger improve compression?
|
---|
132 |
|
---|
133 | struct VertexData {
|
---|
134 | // Should this also update scores for incident triangles?
|
---|
135 | void UpdateScore() {
|
---|
136 | const size_t active_tris = faces.size();
|
---|
137 | if (active_tris <= 0) {
|
---|
138 | score = -1.f;
|
---|
139 | return;
|
---|
140 | }
|
---|
141 | // TODO: build initial score table.
|
---|
142 | if (cache_tag < 3) {
|
---|
143 | // The most recent triangle should has a fixed score to
|
---|
144 | // discourage generating nothing but really long strips. If we
|
---|
145 | // want strips, we should use a different optimizer.
|
---|
146 | const float kLastTriScore = 0.75f;
|
---|
147 | score = kLastTriScore;
|
---|
148 | } else if (cache_tag < kCacheSize) {
|
---|
149 | // Points for being recently used.
|
---|
150 | const float kScale = 1.f / (kCacheSize - 3);
|
---|
151 | const float kCacheDecayPower = 1.5f;
|
---|
152 | score = powf(1.f - kScale * (cache_tag - 3), kCacheDecayPower);
|
---|
153 | } else {
|
---|
154 | // Not in cache.
|
---|
155 | score = 0.f;
|
---|
156 | }
|
---|
157 |
|
---|
158 | // Bonus points for having a low number of tris still to use the
|
---|
159 | // vert, so we get rid of lone verts quickly.
|
---|
160 | const float kValenceBoostScale = 2.0f;
|
---|
161 | const float kValenceBoostPower = 0.5f;
|
---|
162 | // rsqrt?
|
---|
163 | const float valence_boost = powf(active_tris, -kValenceBoostPower);
|
---|
164 | score += valence_boost * kValenceBoostScale;
|
---|
165 | }
|
---|
166 |
|
---|
167 | // TODO: this assumes that "tri" is in the list!
|
---|
168 | void RemoveFace(int tri) {
|
---|
169 | FaceList::iterator face = faces.begin();
|
---|
170 | while (*face != tri) ++face;
|
---|
171 | *face = faces.back();
|
---|
172 | faces.pop_back();
|
---|
173 | }
|
---|
174 |
|
---|
175 | FaceList faces;
|
---|
176 | unsigned int cache_tag; // kCacheSize means not in cache.
|
---|
177 | float score;
|
---|
178 | uint16 output_index;
|
---|
179 | };
|
---|
180 |
|
---|
181 | int FindBestTriangle(const int* indices,
|
---|
182 | const std::vector<TriangleData>& per_tri) {
|
---|
183 | float best_score = -HUGE_VALF;
|
---|
184 | int best_triangle = -1;
|
---|
185 |
|
---|
186 | // The trick to making this algorithm run in linear time (with
|
---|
187 | // respect to the vertices) is to only scan the triangles incident
|
---|
188 | // on the simulated cache for the next triangle. It is an
|
---|
189 | // approximation, but the score is heuristic. Anyway, most of the
|
---|
190 | // time the best triangle will be found this way.
|
---|
191 | for (size_t i = 0; i < kCacheSize; ++i) {
|
---|
192 | if (cache_[i] == kUnknownIndex) {
|
---|
193 | break;
|
---|
194 | }
|
---|
195 | const VertexData& vertex_data = per_vertex_[cache_[i]];
|
---|
196 | for (size_t j = 0; j < vertex_data.faces.size(); ++j) {
|
---|
197 | const int tri_index = vertex_data.faces[j];
|
---|
198 | if (per_tri[tri_index].active) {
|
---|
199 | const float score =
|
---|
200 | per_vertex_[indices[3*tri_index + 0]].score +
|
---|
201 | per_vertex_[indices[3*tri_index + 1]].score +
|
---|
202 | per_vertex_[indices[3*tri_index + 2]].score;
|
---|
203 | if (score > best_score) {
|
---|
204 | best_score = score;
|
---|
205 | best_triangle = tri_index;
|
---|
206 | }
|
---|
207 | }
|
---|
208 | }
|
---|
209 | }
|
---|
210 | // TODO: keep a range of active triangles to make the slow scan a
|
---|
211 | // little faster. Does this ever happen?
|
---|
212 | if (best_triangle == -1) {
|
---|
213 | // If no triangles can be found through the cache (e.g. for the
|
---|
214 | // first triangle) go through all the active triangles and find
|
---|
215 | // the best one.
|
---|
216 | for (size_t i = 0; i < per_tri.size(); ++i) {
|
---|
217 | if (per_tri[i].active) {
|
---|
218 | const float score =
|
---|
219 | per_vertex_[indices[3*i + 0]].score +
|
---|
220 | per_vertex_[indices[3*i + 1]].score +
|
---|
221 | per_vertex_[indices[3*i + 2]].score;
|
---|
222 | if (score > best_score) {
|
---|
223 | best_score = score;
|
---|
224 | best_triangle = i;
|
---|
225 | }
|
---|
226 | }
|
---|
227 | }
|
---|
228 | CHECK(-1 != best_triangle);
|
---|
229 | }
|
---|
230 | return best_triangle;
|
---|
231 | }
|
---|
232 |
|
---|
233 | // TODO: faster to update an entire triangle.
|
---|
234 | // This also updates the vertex scores!
|
---|
235 | void InsertIndexToCache(int index) {
|
---|
236 | // Find how recently the vertex was used.
|
---|
237 | const unsigned int cache_tag = per_vertex_[index].cache_tag;
|
---|
238 |
|
---|
239 | // Don't do anything if the vertex is already at the head of the
|
---|
240 | // LRU list.
|
---|
241 | if (cache_tag == 0) return;
|
---|
242 |
|
---|
243 | // Loop through the cache, inserting the index at the front, and
|
---|
244 | // bubbling down to where the index was originally found. If the
|
---|
245 | // index was not originally in the cache, then it claims to be at
|
---|
246 | // the (kCacheSize + 1)th entry, and we use an extra slot to make
|
---|
247 | // that case simpler.
|
---|
248 | int to_insert = index;
|
---|
249 | for (unsigned int i = 0; i <= cache_tag; ++i) {
|
---|
250 | const int current_index = cache_[i];
|
---|
251 |
|
---|
252 | // Update cross references between the entry of the cache and
|
---|
253 | // the per-vertex data.
|
---|
254 | cache_[i] = to_insert;
|
---|
255 | per_vertex_[to_insert].cache_tag = i;
|
---|
256 | per_vertex_[to_insert].UpdateScore();
|
---|
257 |
|
---|
258 | // No need to continue if we find an empty entry.
|
---|
259 | if (current_index == kUnknownIndex) {
|
---|
260 | break;
|
---|
261 | }
|
---|
262 |
|
---|
263 | to_insert = current_index;
|
---|
264 | }
|
---|
265 | }
|
---|
266 |
|
---|
267 | const QuantizedAttribList& attribs_;
|
---|
268 | std::vector<VertexData> per_vertex_;
|
---|
269 | int cache_[kCacheSize + 1];
|
---|
270 | uint16 next_unused_index_;
|
---|
271 | };
|
---|
272 |
|
---|
273 | #endif // WEBGL_LOADER_OPTIMIZE_H_
|
---|