| 128 | } |
| 129 | |
| 130 | void LongEdgeRemoval::triangulate_chain( |
| 131 | std::vector<VectorI>& faces, |
| 132 | const std::vector<size_t>& chain, |
| 133 | size_t v0_idx, size_t v1_idx, size_t v2_idx) { |
| 134 | const size_t chain_size = chain.size(); |
| 135 | auto next = [&](size_t i) { return (i+1) % chain_size; }; |
| 136 | auto prev = [&](size_t i) { return (i+chain_size-1) % chain_size; }; |
| 137 | auto length = [&](size_t vi, size_t vj) { |
| 138 | return (m_vertices.row(vi) - m_vertices.row(vj)).norm(); |
| 139 | }; |
| 140 | |
| 141 | MatrixIr visited = MatrixIr::Zero(chain_size, 3); |
| 142 | visited(v0_idx, 0) = 1; |
| 143 | visited(v1_idx, 1) = 1; |
| 144 | visited(v2_idx, 2) = 1; |
| 145 | MatrixIr candidates(3, 6); |
| 146 | candidates << v0_idx, next(v0_idx), prev(v0_idx), 0, 0, 0, |
| 147 | v1_idx, next(v1_idx), prev(v1_idx), 0, 0, 0, |
| 148 | v2_idx, next(v2_idx), prev(v2_idx), 0, 0, 0; |
| 149 | MatrixFr candidate_lengths(3, 2); |
| 150 | const Float NOT_USED = std::numeric_limits<Float>::max(); |
| 151 | candidate_lengths |
| 152 | << length(chain[candidates(0, 1)], chain[candidates(0, 2)]), |
| 153 | NOT_USED, |
| 154 | length(chain[candidates(1, 1)], chain[candidates(1, 2)]), |
| 155 | NOT_USED, |
| 156 | length(chain[candidates(2, 1)], chain[candidates(2, 2)]), |
| 157 | NOT_USED; |
| 158 | |
| 159 | auto index_comp = [&](size_t i, size_t j) { |
| 160 | // Use greater than operator so the queue is a min heap. |
| 161 | return candidate_lengths.row(i).minCoeff() > |
| 162 | candidate_lengths.row(j).minCoeff(); |
| 163 | }; |
| 164 | std::priority_queue<size_t, std::vector<size_t>, decltype(index_comp)> |
| 165 | Q(index_comp); |
| 166 | Q.push(0); |
| 167 | Q.push(1); |
| 168 | Q.push(2); |
| 169 | |
| 170 | while (!Q.empty()) { |
| 171 | size_t idx = Q.top(); |
| 172 | Q.pop(); |
| 173 | size_t selection; |
| 174 | if (candidate_lengths(idx, 0) != NOT_USED && |
| 175 | candidate_lengths(idx, 0) <= candidate_lengths(idx, 1)) { |
| 176 | selection = 0; |
| 177 | } else if (candidate_lengths(idx, 1) != NOT_USED && |
| 178 | candidate_lengths(idx, 1) < candidate_lengths(idx, 0)){ |
| 179 | selection = 1; |
| 180 | } else { |
| 181 | continue; |
| 182 | } |
| 183 | size_t base_v = candidates(idx, selection * 3 + 0); |
| 184 | size_t right_v = candidates(idx, selection * 3 + 1); |
| 185 | size_t left_v = candidates(idx, selection * 3 + 2); |
| 186 | assert(visited(base_v, idx) >= 1); |
| 187 | if (visited.row(base_v).sum() > 1 || |