1 /*
2 reorder.cpp: Reorder mesh face/vertex indices to improve coherence in various
3 applications
4
5 This file is part of the implementation of
6
7 Instant Field-Aligned Meshes
8 Wenzel Jakob, Daniele Panozzo, Marco Tarini, and Olga Sorkine-Hornung
9 In ACM Transactions on Graphics (Proc. SIGGRAPH Asia 2015)
10
11 All rights reserved. Use of this source code is governed by a
12 BSD-style license that can be found in the LICENSE.txt file.
13 */
14
15 #include "reorder.h"
16 #include "dedge.h"
17
18 #include <unordered_set>
19 #include <unordered_map>
20 #include <queue>
21
reorder_mesh(MatrixXu & F,std::vector<MatrixXf> & V_vec,std::vector<MatrixXf> & F_vec,const ProgressCallback & progress)22 void reorder_mesh(MatrixXu &F, std::vector<MatrixXf> &V_vec, std::vector<MatrixXf> &F_vec,
23 const ProgressCallback &progress) {
24 /* Build a directed edge data structure */
25 VectorXu V2E, E2E;
26 VectorXb boundary, nonManifold;
27 build_dedge(F, V_vec[0], V2E, E2E, boundary, nonManifold, progress, true);
28
29 std::unordered_set<uint32_t> unprocessed(F.cols());
30 for (uint32_t i=0; i<F.cols(); ++i)
31 unprocessed.insert(i);
32
33 std::queue<uint32_t> queue;
34 std::unordered_map<uint32_t, uint32_t> v_map(V_vec[0].cols());
35
36 uint32_t nF = 0, nV = 0;
37
38 MatrixXu Fp(F.rows(), F.cols());
39 std::vector<MatrixXf> V_new(V_vec.size()), F_new(F_vec.size());
40
41 for (uint32_t i=0; i<V_vec.size(); ++i) {
42 if (V_vec[i].cols() != V_vec[0].cols())
43 throw std::runtime_error("reorder_mesh: inconsistent input!");
44 V_new[i].resize(V_vec[i].rows(), V_vec[i].cols());
45 }
46
47 for (uint32_t i=0; i<F_vec.size(); ++i) {
48 if (F_vec[i].cols() != F.cols())
49 throw std::runtime_error("reorder_mesh: inconsistent input!");
50 F_new[i].resize(F_vec[i].rows(), F_vec[i].cols());
51 }
52
53 while (!unprocessed.empty()) {
54 if (queue.empty()) {
55 auto it = unprocessed.begin();
56 queue.push(*it);
57 unprocessed.erase(it);
58 }
59
60 while (!queue.empty()) {
61 uint32_t f_old = queue.front();
62 uint32_t f_new = nF++;
63 queue.pop();
64 for (uint32_t j=0; j<F_vec.size(); ++j)
65 F_new[j].col(f_new) = F_vec[j].col(f_old);
66
67 for (uint32_t i=0; i<F.rows(); ++i) {
68 uint32_t v_old = F(i, f_old);
69
70 uint32_t v_new;
71 auto it_v = v_map.find(v_old);
72 if (it_v != v_map.end()) {
73 v_new = it_v->second;
74 } else {
75 v_new = v_map[v_old] = nV++;
76 for (uint32_t j=0; j<V_vec.size(); ++j)
77 V_new[j].col(v_new) = V_vec[j].col(v_old);
78 }
79
80 Fp(i, f_new) = v_new;
81
82 uint32_t edge_other = E2E[f_old * F.rows() + i];
83 if (edge_other != INVALID) {
84 uint32_t f_neighbor = edge_other / F.rows();
85 auto it_f = unprocessed.find(f_neighbor);
86 if (it_f != unprocessed.end()) {
87 queue.push(f_neighbor);
88 unprocessed.erase(f_neighbor);
89 }
90 }
91 }
92
93 if (progress && unprocessed.size() % 10000 == 0)
94 progress("Reordering mesh indices", 1-unprocessed.size() / (Float) F.cols());
95 }
96 }
97
98 F = std::move(Fp);
99 for (uint32_t i=0; i<V_vec.size(); ++i) {
100 V_vec[i] = std::move(V_new[i]);
101 V_vec[i].conservativeResize(V_vec[i].rows(), nV);
102 }
103 for (uint32_t i=0; i<F_vec.size(); ++i) {
104 F_vec[i] = std::move(F_new[i]);
105 F_vec[i].conservativeResize(F_vec[i].rows(), nF);
106 }
107 }
108
replicate_vertices(MatrixXu & F,std::vector<MatrixXf> & V)109 void replicate_vertices(MatrixXu &F, std::vector<MatrixXf> &V) {
110 std::vector<MatrixXf> R(V.size());
111
112 for (uint32_t i=0; i<V.size(); ++i)
113 R[i].resize(V[i].rows(), F.size());
114
115 for (uint32_t i=0; i<F.size(); ++i) {
116 uint32_t &idx = F.data()[i];
117 for (uint32_t j=0; j<V.size(); ++j)
118 R[j].col(i) = V[j].col(idx);
119 idx = i;
120 }
121
122 V = std::move(R);
123 }
124