108{
110 const size_t n = geometry.
pos.size();
111 if (n < 3) {
113 return result;
114 }
115
116
117
119 std::vector<Vec3d> pos;
120 std::vector<int> remap(n);
121 for (size_t i = 0; i < n; ++i) {
122 const int idx = vert_map.get_or_set(geometry.
pos[i],
int(pos.size()));
123 if (vert_map.inserted())
124 pos.push_back(geometry.
pos[i].cast<
double>());
125 remap[i] = idx;
126 }
127 const size_t vert_count = pos.size();
128 const size_t face_count = n / 3;
129 std::vector<int> faces(face_count * 3);
130 for (size_t i = 0; i < n; ++i)
131 faces[i] = remap[i];
132
133 if (face_count <= target_triangles && !harvest_flat) {
135 return result;
136 }
137
138
139 std::vector<uint8_t> locked_vert;
140 size_t locked_face_count = 0;
141 if (!locked_faces.empty()) {
142 locked_vert.assign(vert_count, 0);
143 for (
size_t f = 0;
f < face_count &&
f < locked_faces.size(); ++
f) {
144 if (!locked_faces[
f])
145 continue;
146 ++locked_face_count;
147 for (int k = 0; k < 3; ++k)
148 locked_vert[
size_t(faces[
f * 3 +
size_t(k)])] = 1;
149 }
150 }
151
152
153 const bool locked_over_budget =
154 !locked_vert.empty() && face_count > target_triangles && locked_face_count >= target_triangles;
156 if (locked_over_budget && !harvest_flat) {
158 return result;
159 }
160
161 std::vector<Quadric> quadrics(vert_count);
162 {
163
164
165 std::vector<Vec4d> planes(face_count, Vec4d::Zero());
166 tbb::parallel_for(tbb::blocked_range<size_t>(0, face_count),
167 [&](
const tbb::blocked_range<size_t> &
range) {
169 const int a = faces[
f * 3], b = faces[
f * 3 + 1], c = faces[
f * 3 + 2];
170 if (a < 0)
171 continue;
173 if (nrm.isZero())
174 continue;
175 planes[
f] =
Vec4d(nrm.x(), nrm.y(), nrm.z(), -nrm.dot(pos[
size_t(a)]));
176 }
177 });
178 for (
size_t f = 0;
f < face_count; ++
f) {
179 const Vec4d &pl = planes[
f];
180 if (pl.head<3>().isZero())
181 continue;
182 for (int k = 0; k < 3; ++k)
183 quadrics[
size_t(faces[
f * 3 +
size_t(k)])].add_plane(pl.x(), pl.y(), pl.z(), pl.w());
184 }
185 }
186
187
188
189 {
190 struct EdgeRec {
int va, vb, f0, f1; uint8_t
count; };
191 std::vector<EdgeRec> edges;
193 for (
size_t f = 0;
f < face_count; ++
f) {
194 if (faces[
f * 3] < 0)
195 continue;
196 for (int e = 0; e < 3; ++e) {
197 const int va = faces[
f * 3 + size_t(e)];
198 const int vb = faces[
f * 3 + size_t((e + 1) % 3)];
199 const int lo = std::min(va, vb), hi = std::max(va, vb);
200 const int ei = edge_idx.get_or_set_key(lo, hi, 0, int(edges.size()));
201 if (edge_idx.inserted())
202 edges.push_back({ lo, hi, int(
f), -1, 1 });
203 else if (edges[
size_t(ei)].
count == 1) {
204 edges[size_t(ei)].f1 = int(
f);
205 edges[size_t(ei)].count = 2;
206 } else
207
208 edges[size_t(ei)].count = 3;
209 }
210 }
211
213 for (const EdgeRec &er : edges) {
214 if (er.count != 2)
215 continue;
217 faces[size_t(er.f0) * 3 + 2]);
219 faces[size_t(er.f1) * 3 + 2]);
220 const bool color_edge = face_color.size() > std::max(size_t(er.f0), size_t(er.f1)) &&
221 face_color[size_t(er.f0)] != face_color[size_t(er.f1)];
223 continue;
224
225 const Vec3d e =
pos[size_t(er.vb)] -
pos[size_t(er.va)];
226 const double elen = e.norm();
227 if (elen <= 0.0)
228 continue;
229 const Vec3d ed = e / elen;
230 for (
const Vec3d &fn : { n0, n1 }) {
231 Vec3d pn = fn.cross(ed);
232 const double plen = pn.norm();
233 if (plen < 1e-10)
234 continue;
235 pn /= plen;
236 const double d = -pn.dot(pos[size_t(er.va)]);
237
238 for (const int v : { er.va, er.vb })
239 quadrics[size_t(v)].add_plane(pn.x() * sqrt_w, pn.y() * sqrt_w, pn.z() * sqrt_w,
240 d * sqrt_w);
241 }
242 }
243 }
244
245
246 const size_t S = face_count * 3;
247 std::vector<int> vf_head(vert_count, -1), vf_count(vert_count, 0), slot_face(S), slot_vert(S),
248 slot_next(S, -1), slot_prev(S, -1), face_slot(S, -1);
249 for (
size_t f = 0;
f < face_count; ++
f)
250 for (int k = 0; k < 3; ++k) {
251 const int s = int(
f) * 3 + k;
252 const int v = faces[size_t(s)];
253 slot_face[size_t(s)] = int(
f);
254 slot_vert[size_t(s)] = v;
255 slot_next[size_t(s)] = vf_head[size_t(v)];
256 slot_prev[size_t(s)] = -1;
257 if (vf_head[size_t(v)] >= 0)
258 slot_prev[size_t(vf_head[size_t(v)])] = s;
259 vf_head[size_t(v)] = s;
260 face_slot[size_t(s)] = s;
261 ++vf_count[size_t(v)];
262 }
263 const auto unlink_slot = [&](int s) {
264 const int p = slot_prev[size_t(s)], nx = slot_next[size_t(s)], v = slot_vert[size_t(s)];
265 if (p >= 0) slot_next[size_t(p)] = nx;
266 else vf_head[size_t(v)] = nx;
267 if (nx >= 0) slot_prev[size_t(nx)] = p;
268 --vf_count[size_t(v)];
269 };
270 const auto move_slot = [&](int s, int nv) {
271 unlink_slot(s);
272 slot_next[size_t(s)] = vf_head[size_t(nv)];
273 slot_prev[size_t(s)] = -1;
274 if (vf_head[size_t(nv)] >= 0)
275 slot_prev[size_t(vf_head[size_t(nv)])] = s;
276 vf_head[size_t(nv)] = s;
277 slot_vert[size_t(s)] = nv;
278 ++vf_count[size_t(nv)];
279 };
280
281 std::vector<uint8_t> active(vert_count, 1);
282 std::vector<uint32_t> version(vert_count, 0);
283 std::vector<uint32_t> nb_stamp(vert_count, 0), lk_stamp(vert_count, 0);
284 uint32_t epoch = 1, lk_epoch = 1;
285 size_t active_faces = face_count;
286
287
288
289
290 std::vector<HeapEntry> heap;
291 heap.reserve(std::min<size_t>(face_count * 3, size_t(1) << 24));
292 const auto heap_push = [&](HeapEntry e) {
293 heap.push_back(e);
294 std::push_heap(heap.begin(), heap.end(), std::greater<HeapEntry>());
295 };
296 const auto heap_pop = [&]() {
297 std::pop_heap(heap.begin(), heap.end(), std::greater<HeapEntry>());
298 const HeapEntry e = heap.back();
299 heap.pop_back();
300 return e;
301 };
302 size_t pops = 0, stale_pops = 0, compactions = 0;
303
304
305 const auto is_stale = [&](const HeapEntry &e) {
306 return !active[size_t(e.v1)] || !active[size_t(e.v2)] || version[size_t(e.v1)] != e.ver1 ||
307 version[size_t(e.v2)] != e.ver2;
308 };
309
310
311
312
313
314
315
316
317 const auto maybe_compact = [&]() {
318 if (heap.size() < std::max<size_t>(size_t(1) << 16, active_faces * 3))
319 return;
320 heap.erase(std::remove_if(heap.begin(), heap.end(), is_stale), heap.end());
321 std::make_heap(heap.begin(), heap.end(), std::greater<HeapEntry>());
322 ++compactions;
323 };
324
325
326 const auto collapse_target = [&](
int v1,
int v2) ->
Vec3d {
328 if (!
solve_q(quadrics, v1, v2, p)) {
329 const Vec3d mid = (
pos[size_t(v1)] +
pos[size_t(v2)]) * 0.5;
330 const double e1 =
eval_sum(quadrics, v1, v2, pos[
size_t(v1)]);
331 const double e2 =
eval_sum(quadrics, v1, v2, pos[
size_t(v2)]);
332 const double em =
eval_sum(quadrics, v1, v2, mid);
333 const double emin = std::min({ e1, e2, em });
334 const double etol = emin * 1e-2 + 1e-12;
335
336
337 if (em <= emin + etol) p = mid;
338 else if (e1 <= e2) p =
pos[size_t(v1)];
339 else p =
pos[size_t(v2)];
340 }
341 return p;
342 };
343 const auto push_edge = [&](int v1, int v2) {
344 const Vec3d p = collapse_target(v1, v2);
345
346
347
348 const double len2 = (
pos[size_t(v2)] -
pos[size_t(v1)]).squaredNorm();
349 heap_push({
eval_sum(quadrics, v1, v2, p) + len2 * 1e-8, v1, v2, version[size_t(v1)],
350 version[size_t(v2)] });
351 };
352
353 {
355 for (
size_t f = 0;
f < face_count; ++
f) {
356 if (faces[
f * 3] < 0)
357 continue;
358 for (int e = 0; e < 3; ++e) {
359 const int va = faces[
f * 3 + size_t(e)];
360 const int vb = faces[
f * 3 + size_t((e + 1) % 3)];
361 if (!locked_vert.empty() && (locked_vert[size_t(va)] || locked_vert[size_t(vb)]))
362 continue;
363 seed_seen.get_or_set_key(std::min(va, vb), std::max(va, vb), 0, 1);
364 if (seed_seen.inserted())
365 push_edge(va, vb);
366 }
367 }
368 }
369
370
371 const auto shared_face_count = [&](int v1, int v2) {
373 for (int s = vf_head[size_t(v1)]; s >= 0; s = slot_next[size_t(s)]) {
374 const int f = slot_face[size_t(s)];
375 if (faces[
size_t(
f) * 3] < 0)
376 continue;
377 for (int k = 0; k < 3; ++k)
378 if (faces[
size_t(
f) * 3 +
size_t(k)] == v2) {
380 return 2;
381 break;
382 }
383 }
385 };
386
387
388
389 const auto has_link_violation = [&](int v1, int v2, uint32_t ep) {
390 for (int s = vf_head[size_t(v1)]; s >= 0; s = slot_next[size_t(s)]) {
391 const int f = slot_face[size_t(s)];
392 if (faces[
size_t(
f) * 3] < 0)
393 continue;
394 for (int k = 0; k < 3; ++k)
395 if (
const int x = faces[
size_t(
f) * 3 +
size_t(k)]; x != v1)
396 lk_stamp[size_t(x)] = ep;
397 }
398 int shared = 0;
399 for (int s = vf_head[size_t(v1)]; s >= 0; s = slot_next[size_t(s)]) {
400 const int f = slot_face[size_t(s)];
401 if (faces[
size_t(
f) * 3] < 0)
402 continue;
403 const int a = faces[size_t(
f) * 3], b = faces[size_t(
f) * 3 + 1], c = faces[size_t(
f) * 3 + 2];
404 if (a == v2 || b == v2 || c == v2) {
405 ++shared;
406 const int apex = (a != v1 && a != v2) ? a : (b != v1 && b != v2) ? b : c;
407 lk_stamp[size_t(apex)] = ep + 1;
408 }
409 }
410 if (shared > 2)
411 return true;
412 for (int s = vf_head[size_t(v2)]; s >= 0; s = slot_next[size_t(s)]) {
413 const int f = slot_face[size_t(s)];
414 if (faces[
size_t(
f) * 3] < 0)
415 continue;
416 for (int k = 0; k < 3; ++k) {
417 const int x = faces[size_t(
f) * 3 + size_t(k)];
418 if (x != v2 && x != v1 && lk_stamp[size_t(x)] == ep)
419 return true;
420 }
421 }
422 return false;
423 };
424
425
426
427 const auto check_flipped = [&](
int vc,
int vo,
const Vec3d &np) {
428 for (int s = vf_head[size_t(vc)]; s >= 0; s = slot_next[size_t(s)]) {
429 const size_t f = size_t(slot_face[
size_t(s)]);
430 if (faces[
f * 3] < 0)
431 continue;
432 const int fa = faces[
f * 3], fb = faces[
f * 3 + 1], fc = faces[
f * 3 + 2];
433 if (fa == vo || fb == vo || fc == vo)
434 continue;
435 const Vec3d oa =
pos[size_t(fa)], ob =
pos[size_t(fb)], oc =
pos[size_t(fc)];
437 const Vec3d na = (fa == vc) ? np : oa;
438 const Vec3d nb = (fb == vc) ? np : ob;
439 const Vec3d nc = (fc == vc) ? np : oc;
441 const double raw = on.dot(nn);
442 if (raw < 0.0)
443 return true;
445 return true;
446 }
447 return false;
448 };
449
450 const size_t init_faces = active_faces;
451 const size_t to_remove = std::max<size_t>(1, init_faces > target_triangles
452 ? init_faces - target_triangles : init_faces);
453 const double harvest_ceil = harvest_tol * harvest_tol;
454 bool reached_target = locked_over_budget;
455 double last_progress = 0.0;
456
457 while (!heap.empty()) {
458 if (active_faces <= target_triangles) {
459 if (!harvest_flat)
460 break;
461 reached_target = true;
462 }
463
464 const HeapEntry top = heap_pop();
465 ++pops;
466 if (on_progress) {
467
468
469 const double p = std::min(1.0, double(init_faces - active_faces) / double(to_remove));
470 if (p - last_progress > 0.005 || (pops & 0x3fff) == 0) {
471 last_progress = p;
472 if (!on_progress(p))
473 break;
474 }
475 }
476
477 if (reached_target && top.cost > harvest_ceil)
478 break;
479
480 const int v1 = top.v1, v2 = top.v2;
481 if (is_stale(top)) {
482 ++stale_pops;
483 continue;
484 }
485
486
488 continue;
489 if (shared_face_count(v1, v2) < 2)
490 continue;
491 lk_epoch += 2;
492 if (has_link_violation(v1, v2, lk_epoch))
493 continue;
495 if (check_flipped(v1, v2, target) || check_flipped(v2, v1, target))
496 continue;
497 if (!reached_target && top.cost > harvest_ceil)
499
500
501 pos[size_t(v1)] = target;
502 quadrics[size_t(v1)] += quadrics[size_t(v2)];
503 ++version[size_t(v1)];
504
505 for (int s = vf_head[size_t(v2)]; s >= 0;) {
506 const size_t f = size_t(slot_face[
size_t(s)]);
507 const int s_next = slot_next[size_t(s)];
508 if (faces[
f * 3] >= 0) {
509 for (int k = 0; k < 3; ++k)
510 if (faces[
f * 3 +
size_t(k)] == v2) {
511 faces[
f * 3 + size_t(k)] = v1;
512 break;
513 }
514 const int fa = faces[
f * 3], fb = faces[
f * 3 + 1], fc = faces[
f * 3 + 2];
515 if (fa == fb || fb == fc || fa == fc) {
516 for (int k = 0; k < 3; ++k)
517 if (
const int sk = face_slot[
f * 3 +
size_t(k)]; sk >= 0) {
518 unlink_slot(sk);
519 face_slot[
f * 3 + size_t(k)] = -1;
520 }
521 faces[
f * 3] = faces[
f * 3 + 1] = faces[
f * 3 + 2] = -1;
522 --active_faces;
523 } else
524 move_slot(s, v1);
525 }
526 s = s_next;
527 }
528 active[size_t(v2)] = 0;
529
530 ++epoch;
531 for (int sv = vf_head[size_t(v1)]; sv >= 0; sv = slot_next[size_t(sv)]) {
532 const size_t f = size_t(slot_face[
size_t(sv)]);
533 if (faces[
f * 3] < 0)
534 continue;
535 for (int k = 0; k < 3; ++k) {
536 const int nb = faces[
f * 3 + size_t(k)];
537 if (nb == v1 || nb_stamp[size_t(nb)] == epoch)
538 continue;
539 nb_stamp[size_t(nb)] = epoch;
540
541 if (active[size_t(nb)] && (locked_vert.empty() || !locked_vert[size_t(nb)]))
542 push_edge(v1, nb);
543 }
544 }
545 maybe_compact();
546 }
547
548 BOOST_LOG_TRIVIAL(info) << "TextureBake decimate: pops=" << pops << " stale=" << stale_pops
549 << " compactions=" << compactions << " heap_peak=" << heap.capacity()
550 << " faces=" << active_faces;
551
552
554 if (!face_color.empty())
556 for (
size_t f = 0;
f < face_count; ++
f) {
557 if (faces[
f * 3] < 0)
558 continue;
559 if (!face_color.empty())
560 result.
face_color.push_back(
f < face_color.size() ? face_color[
f] : -1);
561 const Vec3f a =
pos[size_t(faces[
f * 3])].cast<
float>();
562 const Vec3f b =
pos[size_t(faces[
f * 3 + 1])].cast<
float>();
563 const Vec3f c =
pos[size_t(faces[
f * 3 + 2])].cast<
float>();
564 const Vec3f nrm = (b - a).
cross(c - a).normalized();
565 out.pos.insert(out.pos.end(), { a, b, c });
566 out.nrm.insert(out.nrm.end(), { nrm, nrm, nrm });
567 }
568 return result;
569}
Vec3d face_normal_unit(const std::vector< Vec3d > &pos, int a, int b, int c)
Definition TextureBakeDecimate.cpp:80
bool solve_q(const std::vector< Quadric > &qs, int v1, int v2, Vec3d &out)
Definition TextureBakeDecimate.cpp:56
double eval_sum(const std::vector< Quadric > &qs, int v1, int v2, const Vec3d &p)
Definition TextureBakeDecimate.cpp:50
static constexpr double DECIMATE_CREASE_WEIGHT
Definition TextureBakeDecimate.hpp:28
static constexpr int DECIMATE_MAX_VALENCE
Definition TextureBakeDecimate.hpp:33
TriSoup geometry
Definition TextureBakeDecimate.hpp:48
static constexpr double DECIMATE_FLIP_DOT
Definition TextureBakeDecimate.hpp:24
std::vector< int > face_color
Definition TextureBakeDecimate.hpp:55
bool target_cost_detail
Definition TextureBakeDecimate.hpp:61
static constexpr double WELD_GRID_DECIMATION
Definition TextureBakeIndex.hpp:26
bool locked_over_budget
Definition TextureBakeDecimate.hpp:58
static constexpr double DECIMATE_CREASE_COS
Definition TextureBakeDecimate.hpp:26
Definition TextureBakeDecimate.hpp:47
Vec3d pos(const Pt &p)
Definition ReprojectPointsOnMesh.hpp:16
Eigen::Matrix< double, 4, 1, Eigen::DontAlign > Vec4d
Definition Point.hpp:69
1.15.0 