Merge by Distance: split code into more specialized functions
Split the algorithms that find duplicates. This improves readability and helps us find areas for optimization. It may also facilitate the implementation of generic utilities. No functional changes. Differential Revision: https://developer.blender.org/D16918
This commit is contained in:
Germano Cavalcante
parent
90c6674f28
commit
25ce705617
|
|
@ -15,7 +15,7 @@
|
|||
|
||||
#include "GEO_mesh_merge_by_distance.hh"
|
||||
|
||||
//#define USE_WELD_DEBUG
|
||||
// #define USE_WELD_DEBUG
|
||||
|
||||
namespace blender::geometry {
|
||||
|
||||
|
|
@ -404,13 +404,15 @@ static void weld_vert_groups_setup(Span<WeldVert> wvert,
|
|||
* \return r_edge_dest_map: First step to create map of indices pointing edges that will be merged.
|
||||
* \return r_edge_ctx_map: Map of indices pointing original edges to weld context edges.
|
||||
*/
|
||||
static Vector<WeldEdge> weld_edge_ctx_alloc(Span<MEdge> medge,
|
||||
Span<int> vert_dest_map,
|
||||
MutableSpan<int> r_edge_dest_map,
|
||||
MutableSpan<int> r_edge_ctx_map)
|
||||
static Vector<WeldEdge> weld_edge_ctx_alloc_and_find_collapsed(Span<MEdge> medge,
|
||||
Span<int> vert_dest_map,
|
||||
MutableSpan<int> r_edge_dest_map,
|
||||
MutableSpan<int> r_edge_ctx_map,
|
||||
int *r_edge_collapsed_len)
|
||||
{
|
||||
/* Edge Context. */
|
||||
int wedge_len = 0;
|
||||
int edge_collapsed_len = 0;
|
||||
|
||||
Vector<WeldEdge> wedge;
|
||||
wedge.reserve(medge.size());
|
||||
|
|
@ -426,8 +428,17 @@ static Vector<WeldEdge> weld_edge_ctx_alloc(Span<MEdge> medge,
|
|||
we.vert_b = (v_dest_2 != OUT_OF_CONTEXT) ? v_dest_2 : v2;
|
||||
we.edge_dest = OUT_OF_CONTEXT;
|
||||
we.edge_orig = i;
|
||||
|
||||
if (we.vert_a == we.vert_b) {
|
||||
we.flag = ELEM_COLLAPSED;
|
||||
edge_collapsed_len++;
|
||||
r_edge_dest_map[i] = ELEM_COLLAPSED;
|
||||
}
|
||||
else {
|
||||
r_edge_dest_map[i] = i;
|
||||
}
|
||||
|
||||
wedge.append(we);
|
||||
r_edge_dest_map[i] = i;
|
||||
r_edge_ctx_map[i] = wedge_len++;
|
||||
}
|
||||
else {
|
||||
|
|
@ -436,6 +447,7 @@ static Vector<WeldEdge> weld_edge_ctx_alloc(Span<MEdge> medge,
|
|||
}
|
||||
}
|
||||
|
||||
*r_edge_collapsed_len = edge_collapsed_len;
|
||||
return wedge;
|
||||
}
|
||||
|
||||
|
|
@ -449,30 +461,30 @@ static Vector<WeldEdge> weld_edge_ctx_alloc(Span<MEdge> medge,
|
|||
* \return r_wedge: Weld edges. `flag` and `edge_dest` members will be set here.
|
||||
* \return r_edge_kill_len: Number of edges to be destroyed by merging or collapsing.
|
||||
*/
|
||||
static void weld_edge_ctx_setup(MutableSpan<int> r_vlinks,
|
||||
MutableSpan<int> r_edge_dest_map,
|
||||
MutableSpan<WeldEdge> r_wedge,
|
||||
int *r_edge_kill_len)
|
||||
static void weld_edge_find_doubles(int remain_edge_ctx_len,
|
||||
MutableSpan<int> r_vlinks,
|
||||
MutableSpan<int> r_edge_dest_map,
|
||||
MutableSpan<WeldEdge> r_wedge,
|
||||
int *r_edge_kill_len)
|
||||
{
|
||||
if (remain_edge_ctx_len == 0) {
|
||||
return;
|
||||
}
|
||||
|
||||
/* Setup Edge Overlap. */
|
||||
int edge_kill_len = 0;
|
||||
int edge_double_len = 0;
|
||||
|
||||
r_vlinks.fill(0);
|
||||
|
||||
for (WeldEdge &we : r_wedge) {
|
||||
int dst_vert_a = we.vert_a;
|
||||
int dst_vert_b = we.vert_b;
|
||||
|
||||
if (dst_vert_a == dst_vert_b) {
|
||||
BLI_assert(we.edge_dest == OUT_OF_CONTEXT);
|
||||
r_edge_dest_map[we.edge_orig] = ELEM_COLLAPSED;
|
||||
we.flag = ELEM_COLLAPSED;
|
||||
edge_kill_len++;
|
||||
if (we.flag == ELEM_COLLAPSED) {
|
||||
BLI_assert(r_edge_dest_map[we.edge_orig] == ELEM_COLLAPSED);
|
||||
continue;
|
||||
}
|
||||
|
||||
r_vlinks[dst_vert_a]++;
|
||||
r_vlinks[dst_vert_b]++;
|
||||
BLI_assert(we.vert_a != we.vert_b);
|
||||
r_vlinks[we.vert_a]++;
|
||||
r_vlinks[we.vert_b]++;
|
||||
}
|
||||
|
||||
int link_len = 0;
|
||||
|
|
@ -482,80 +494,79 @@ static void weld_edge_ctx_setup(MutableSpan<int> r_vlinks,
|
|||
}
|
||||
r_vlinks.last() = link_len;
|
||||
|
||||
if (link_len > 0) {
|
||||
Array<int> link_edge_buffer(link_len);
|
||||
BLI_assert(link_len > 0);
|
||||
Array<int> link_edge_buffer(link_len);
|
||||
|
||||
/* Use a reverse for loop to ensure that indexes are assigned in ascending order. */
|
||||
for (int i = r_wedge.size(); i--;) {
|
||||
const WeldEdge &we = r_wedge[i];
|
||||
if (we.flag == ELEM_COLLAPSED) {
|
||||
continue;
|
||||
}
|
||||
|
||||
int dst_vert_a = we.vert_a;
|
||||
int dst_vert_b = we.vert_b;
|
||||
|
||||
link_edge_buffer[--r_vlinks[dst_vert_a]] = i;
|
||||
link_edge_buffer[--r_vlinks[dst_vert_b]] = i;
|
||||
/* Use a reverse for loop to ensure that indexes are assigned in ascending order. */
|
||||
for (int i = r_wedge.size(); i--;) {
|
||||
const WeldEdge &we = r_wedge[i];
|
||||
if (we.flag == ELEM_COLLAPSED) {
|
||||
continue;
|
||||
}
|
||||
|
||||
for (const int i : r_wedge.index_range()) {
|
||||
const WeldEdge &we = r_wedge[i];
|
||||
if (we.edge_dest != OUT_OF_CONTEXT) {
|
||||
/* No need to retest edges.
|
||||
* (Already includes collapsed edges). */
|
||||
continue;
|
||||
}
|
||||
int dst_vert_a = we.vert_a;
|
||||
int dst_vert_b = we.vert_b;
|
||||
|
||||
int dst_vert_a = we.vert_a;
|
||||
int dst_vert_b = we.vert_b;
|
||||
|
||||
const int link_a = r_vlinks[dst_vert_a];
|
||||
const int link_b = r_vlinks[dst_vert_b];
|
||||
|
||||
int edges_len_a = r_vlinks[dst_vert_a + 1] - link_a;
|
||||
int edges_len_b = r_vlinks[dst_vert_b + 1] - link_b;
|
||||
|
||||
if (edges_len_a <= 1 || edges_len_b <= 1) {
|
||||
continue;
|
||||
}
|
||||
|
||||
int *edges_ctx_a = &link_edge_buffer[link_a];
|
||||
int *edges_ctx_b = &link_edge_buffer[link_b];
|
||||
int edge_orig = we.edge_orig;
|
||||
|
||||
for (; edges_len_a--; edges_ctx_a++) {
|
||||
int e_ctx_a = *edges_ctx_a;
|
||||
if (e_ctx_a == i) {
|
||||
continue;
|
||||
}
|
||||
while (edges_len_b && *edges_ctx_b < e_ctx_a) {
|
||||
edges_ctx_b++;
|
||||
edges_len_b--;
|
||||
}
|
||||
if (edges_len_b == 0) {
|
||||
break;
|
||||
}
|
||||
int e_ctx_b = *edges_ctx_b;
|
||||
if (e_ctx_a == e_ctx_b) {
|
||||
WeldEdge *we_b = &r_wedge[e_ctx_b];
|
||||
BLI_assert(ELEM(we_b->vert_a, dst_vert_a, dst_vert_b));
|
||||
BLI_assert(ELEM(we_b->vert_b, dst_vert_a, dst_vert_b));
|
||||
BLI_assert(we_b->edge_dest == OUT_OF_CONTEXT);
|
||||
BLI_assert(we_b->edge_orig != edge_orig);
|
||||
r_edge_dest_map[we_b->edge_orig] = edge_orig;
|
||||
we_b->edge_dest = edge_orig;
|
||||
edge_kill_len++;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
#ifdef USE_WELD_DEBUG
|
||||
weld_assert_edge_kill_len(r_wedge, edge_kill_len);
|
||||
#endif
|
||||
link_edge_buffer[--r_vlinks[dst_vert_a]] = i;
|
||||
link_edge_buffer[--r_vlinks[dst_vert_b]] = i;
|
||||
}
|
||||
|
||||
*r_edge_kill_len = edge_kill_len;
|
||||
for (const int i : r_wedge.index_range()) {
|
||||
const WeldEdge &we = r_wedge[i];
|
||||
if (we.edge_dest != OUT_OF_CONTEXT) {
|
||||
/* No need to retest edges.
|
||||
* (Already includes collapsed edges). */
|
||||
continue;
|
||||
}
|
||||
|
||||
int dst_vert_a = we.vert_a;
|
||||
int dst_vert_b = we.vert_b;
|
||||
|
||||
const int link_a = r_vlinks[dst_vert_a];
|
||||
const int link_b = r_vlinks[dst_vert_b];
|
||||
|
||||
int edges_len_a = r_vlinks[dst_vert_a + 1] - link_a;
|
||||
int edges_len_b = r_vlinks[dst_vert_b + 1] - link_b;
|
||||
|
||||
if (edges_len_a <= 1 || edges_len_b <= 1) {
|
||||
continue;
|
||||
}
|
||||
|
||||
int *edges_ctx_a = &link_edge_buffer[link_a];
|
||||
int *edges_ctx_b = &link_edge_buffer[link_b];
|
||||
int edge_orig = we.edge_orig;
|
||||
|
||||
for (; edges_len_a--; edges_ctx_a++) {
|
||||
int e_ctx_a = *edges_ctx_a;
|
||||
if (e_ctx_a == i) {
|
||||
continue;
|
||||
}
|
||||
while (edges_len_b && *edges_ctx_b < e_ctx_a) {
|
||||
edges_ctx_b++;
|
||||
edges_len_b--;
|
||||
}
|
||||
if (edges_len_b == 0) {
|
||||
break;
|
||||
}
|
||||
int e_ctx_b = *edges_ctx_b;
|
||||
if (e_ctx_a == e_ctx_b) {
|
||||
WeldEdge *we_b = &r_wedge[e_ctx_b];
|
||||
BLI_assert(ELEM(we_b->vert_a, dst_vert_a, dst_vert_b));
|
||||
BLI_assert(ELEM(we_b->vert_b, dst_vert_a, dst_vert_b));
|
||||
BLI_assert(we_b->edge_dest == OUT_OF_CONTEXT);
|
||||
BLI_assert(we_b->edge_orig != edge_orig);
|
||||
r_edge_dest_map[we_b->edge_orig] = edge_orig;
|
||||
we_b->edge_dest = edge_orig;
|
||||
edge_double_len++;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
*r_edge_kill_len += edge_double_len;
|
||||
|
||||
#ifdef USE_WELD_DEBUG
|
||||
weld_assert_edge_kill_len(r_wedge, *r_edge_kill_len);
|
||||
#endif
|
||||
}
|
||||
|
||||
/**
|
||||
|
|
@ -995,204 +1006,225 @@ static void weld_poly_split_recursive(Span<int> vert_dest_map,
|
|||
* done to reduce allocations.
|
||||
* \return r_weld_mesh: Loop and poly members will be configured here.
|
||||
*/
|
||||
static void weld_poly_loop_ctx_setup(Span<MLoop> mloop,
|
||||
static void weld_poly_loop_ctx_setup_collapsed_and_split(Span<MLoop> mloop,
|
||||
#ifdef USE_WELD_DEBUG
|
||||
Span<MPoly> mpoly,
|
||||
Span<MPoly> mpoly,
|
||||
#endif
|
||||
const int mvert_len,
|
||||
Span<int> vert_dest_map,
|
||||
const int remain_edge_ctx_len,
|
||||
MutableSpan<int> r_vlinks,
|
||||
WeldMesh *r_weld_mesh)
|
||||
Span<int> vert_dest_map,
|
||||
const int remain_edge_ctx_len,
|
||||
WeldMesh *r_weld_mesh)
|
||||
{
|
||||
WeldPoly *wpoly = r_weld_mesh->wpoly.data();
|
||||
MutableSpan<WeldLoop> wloop = r_weld_mesh->wloop;
|
||||
int poly_kill_len = 0;
|
||||
int loop_kill_len = 0;
|
||||
|
||||
Span<int> loop_map = r_weld_mesh->loop_map;
|
||||
|
||||
if (remain_edge_ctx_len) {
|
||||
|
||||
/* Setup Poly/Loop. */
|
||||
/* `wpoly.size()` may change during the loop,
|
||||
* so make it clear that we are only working with the original wpolys. */
|
||||
IndexRange wpoly_original_range = r_weld_mesh->wpoly.index_range();
|
||||
for (const int i : wpoly_original_range) {
|
||||
WeldPoly &wp = wpoly[i];
|
||||
const int ctx_loops_len = wp.loops.len;
|
||||
const int ctx_loops_ofs = wp.loops.offs;
|
||||
|
||||
int poly_loop_len = wp.loop_len;
|
||||
int ctx_verts_len = 0;
|
||||
WeldLoop *wl = &wloop[ctx_loops_ofs];
|
||||
for (int l = ctx_loops_len; l--; wl++) {
|
||||
const int edge_dest = wl->edge;
|
||||
if (edge_dest == ELEM_COLLAPSED) {
|
||||
wl->flag = ELEM_COLLAPSED;
|
||||
if (poly_loop_len == 3) {
|
||||
wp.flag = ELEM_COLLAPSED;
|
||||
poly_kill_len++;
|
||||
loop_kill_len += 3;
|
||||
poly_loop_len = 0;
|
||||
break;
|
||||
}
|
||||
loop_kill_len++;
|
||||
poly_loop_len--;
|
||||
}
|
||||
else {
|
||||
const int vert_dst = wl->vert;
|
||||
if (vert_dest_map[vert_dst] != OUT_OF_CONTEXT) {
|
||||
ctx_verts_len++;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
if (poly_loop_len) {
|
||||
wp.loop_len = poly_loop_len;
|
||||
#ifdef USE_WELD_DEBUG
|
||||
weld_assert_poly_len(&wp, wloop);
|
||||
#endif
|
||||
|
||||
weld_poly_split_recursive(vert_dest_map,
|
||||
#ifdef USE_WELD_DEBUG
|
||||
mloop,
|
||||
#endif
|
||||
ctx_verts_len,
|
||||
&wp,
|
||||
r_weld_mesh,
|
||||
&poly_kill_len,
|
||||
&loop_kill_len);
|
||||
}
|
||||
}
|
||||
|
||||
#ifdef USE_WELD_DEBUG
|
||||
weld_assert_poly_and_loop_kill_len(r_weld_mesh, mloop, mpoly, poly_kill_len, loop_kill_len);
|
||||
#endif
|
||||
|
||||
/* Setup Polygon Overlap. */
|
||||
|
||||
r_vlinks.fill(0);
|
||||
|
||||
for (const WeldPoly &wp : r_weld_mesh->wpoly) {
|
||||
WeldLoopOfPolyIter iter;
|
||||
if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) {
|
||||
while (weld_iter_loop_of_poly_next(iter)) {
|
||||
r_vlinks[iter.v]++;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
int link_len = 0;
|
||||
for (const int i : IndexRange(mvert_len)) {
|
||||
link_len += r_vlinks[i];
|
||||
r_vlinks[i] = link_len;
|
||||
}
|
||||
r_vlinks[mvert_len] = link_len;
|
||||
|
||||
if (link_len) {
|
||||
Array<int> link_poly_buffer(link_len);
|
||||
|
||||
/* Use a reverse for loop to ensure that indexes are assigned in ascending order. */
|
||||
for (int i = r_weld_mesh->wpoly.size(); i--;) {
|
||||
const WeldPoly &wp = wpoly[i];
|
||||
WeldLoopOfPolyIter iter;
|
||||
if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) {
|
||||
while (weld_iter_loop_of_poly_next(iter)) {
|
||||
link_poly_buffer[--r_vlinks[iter.v]] = i;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
int polys_len_a, polys_len_b, *polys_ctx_a, *polys_ctx_b, p_ctx_a, p_ctx_b;
|
||||
polys_len_b = p_ctx_b = 0; /* silence warnings */
|
||||
|
||||
for (const int i : IndexRange(r_weld_mesh->wpoly.size())) {
|
||||
const WeldPoly &wp = wpoly[i];
|
||||
if (wp.poly_dst != OUT_OF_CONTEXT) {
|
||||
/* No need to retest poly.
|
||||
* (Already includes collapsed polygons). */
|
||||
continue;
|
||||
}
|
||||
|
||||
WeldLoopOfPolyIter iter;
|
||||
weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr);
|
||||
weld_iter_loop_of_poly_next(iter);
|
||||
const int link_a = r_vlinks[iter.v];
|
||||
polys_len_a = r_vlinks[iter.v + 1] - link_a;
|
||||
if (polys_len_a == 1) {
|
||||
BLI_assert(link_poly_buffer[link_a] == i);
|
||||
continue;
|
||||
}
|
||||
int wp_loop_len = wp.loop_len;
|
||||
polys_ctx_a = &link_poly_buffer[link_a];
|
||||
for (; polys_len_a--; polys_ctx_a++) {
|
||||
p_ctx_a = *polys_ctx_a;
|
||||
if (p_ctx_a == i) {
|
||||
continue;
|
||||
}
|
||||
|
||||
WeldPoly *wp_tmp = &wpoly[p_ctx_a];
|
||||
if (wp_tmp->loop_len != wp_loop_len) {
|
||||
continue;
|
||||
}
|
||||
|
||||
WeldLoopOfPolyIter iter_b = iter;
|
||||
while (weld_iter_loop_of_poly_next(iter_b)) {
|
||||
const int link_b = r_vlinks[iter_b.v];
|
||||
polys_len_b = r_vlinks[iter_b.v + 1] - link_b;
|
||||
if (polys_len_b == 1) {
|
||||
BLI_assert(link_poly_buffer[link_b] == i);
|
||||
polys_len_b = 0;
|
||||
break;
|
||||
}
|
||||
|
||||
polys_ctx_b = &link_poly_buffer[link_b];
|
||||
for (; polys_len_b; polys_len_b--, polys_ctx_b++) {
|
||||
p_ctx_b = *polys_ctx_b;
|
||||
if (p_ctx_b < p_ctx_a) {
|
||||
continue;
|
||||
}
|
||||
if (p_ctx_b >= p_ctx_a) {
|
||||
if (p_ctx_b > p_ctx_a) {
|
||||
polys_len_b = 0;
|
||||
}
|
||||
break;
|
||||
}
|
||||
}
|
||||
if (polys_len_b == 0) {
|
||||
break;
|
||||
}
|
||||
}
|
||||
if (polys_len_b == 0) {
|
||||
continue;
|
||||
}
|
||||
BLI_assert(p_ctx_a > i);
|
||||
BLI_assert(p_ctx_a == p_ctx_b);
|
||||
BLI_assert(wp_tmp->poly_dst == OUT_OF_CONTEXT);
|
||||
BLI_assert(wp_tmp != &wp);
|
||||
wp_tmp->poly_dst = wp.poly_orig;
|
||||
loop_kill_len += wp_tmp->loop_len;
|
||||
poly_kill_len++;
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
else {
|
||||
poly_kill_len = r_weld_mesh->wpoly.size();
|
||||
loop_kill_len = r_weld_mesh->wloop.size();
|
||||
if (remain_edge_ctx_len == 0) {
|
||||
r_weld_mesh->poly_kill_len = r_weld_mesh->wpoly.size();
|
||||
r_weld_mesh->loop_kill_len = r_weld_mesh->wloop.size();
|
||||
|
||||
for (WeldPoly &wp : r_weld_mesh->wpoly) {
|
||||
wp.flag = ELEM_COLLAPSED;
|
||||
}
|
||||
|
||||
return;
|
||||
}
|
||||
|
||||
WeldPoly *wpoly = r_weld_mesh->wpoly.data();
|
||||
MutableSpan<WeldLoop> wloop = r_weld_mesh->wloop;
|
||||
|
||||
int poly_kill_len = 0;
|
||||
int loop_kill_len = 0;
|
||||
|
||||
/* Setup Poly/Loop. */
|
||||
/* `wpoly.size()` may change during the loop,
|
||||
* so make it clear that we are only working with the original wpolys. */
|
||||
IndexRange wpoly_original_range = r_weld_mesh->wpoly.index_range();
|
||||
for (const int i : wpoly_original_range) {
|
||||
WeldPoly &wp = wpoly[i];
|
||||
const int ctx_loops_len = wp.loops.len;
|
||||
const int ctx_loops_ofs = wp.loops.offs;
|
||||
|
||||
int poly_loop_len = wp.loop_len;
|
||||
int ctx_verts_len = 0;
|
||||
WeldLoop *wl = &wloop[ctx_loops_ofs];
|
||||
for (int l = ctx_loops_len; l--; wl++) {
|
||||
const int edge_dest = wl->edge;
|
||||
if (edge_dest == ELEM_COLLAPSED) {
|
||||
wl->flag = ELEM_COLLAPSED;
|
||||
if (poly_loop_len == 3) {
|
||||
wp.flag = ELEM_COLLAPSED;
|
||||
poly_kill_len++;
|
||||
loop_kill_len += 3;
|
||||
poly_loop_len = 0;
|
||||
break;
|
||||
}
|
||||
loop_kill_len++;
|
||||
poly_loop_len--;
|
||||
}
|
||||
else {
|
||||
const int vert_dst = wl->vert;
|
||||
if (vert_dest_map[vert_dst] != OUT_OF_CONTEXT) {
|
||||
ctx_verts_len++;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
if (poly_loop_len) {
|
||||
wp.loop_len = poly_loop_len;
|
||||
#ifdef USE_WELD_DEBUG
|
||||
weld_assert_poly_and_loop_kill_len(r_weld_mesh, mloop, mpoly, poly_kill_len, loop_kill_len);
|
||||
weld_assert_poly_len(&wp, wloop);
|
||||
#endif
|
||||
|
||||
weld_poly_split_recursive(vert_dest_map,
|
||||
#ifdef USE_WELD_DEBUG
|
||||
mloop,
|
||||
#endif
|
||||
ctx_verts_len,
|
||||
&wp,
|
||||
r_weld_mesh,
|
||||
&poly_kill_len,
|
||||
&loop_kill_len);
|
||||
}
|
||||
}
|
||||
|
||||
r_weld_mesh->poly_kill_len = poly_kill_len;
|
||||
r_weld_mesh->loop_kill_len = loop_kill_len;
|
||||
|
||||
#ifdef USE_WELD_DEBUG
|
||||
weld_assert_poly_and_loop_kill_len(
|
||||
r_weld_mesh, mloop, mpoly, r_weld_mesh->poly_kill_len, r_weld_mesh->loop_kill_len);
|
||||
#endif
|
||||
}
|
||||
|
||||
static void weld_poly_find_doubles(Span<MLoop> mloop,
|
||||
#ifdef USE_WELD_DEBUG
|
||||
const Span<MPoly> mpoly,
|
||||
#endif
|
||||
const int mvert_len,
|
||||
MutableSpan<int> r_vlinks,
|
||||
WeldMesh *r_weld_mesh)
|
||||
{
|
||||
if (r_weld_mesh->poly_kill_len == r_weld_mesh->wpoly.size()) {
|
||||
return;
|
||||
}
|
||||
|
||||
WeldPoly *wpoly = r_weld_mesh->wpoly.data();
|
||||
MutableSpan<WeldLoop> wloop = r_weld_mesh->wloop;
|
||||
Span<int> loop_map = r_weld_mesh->loop_map;
|
||||
int poly_kill_len = r_weld_mesh->poly_kill_len;
|
||||
int loop_kill_len = r_weld_mesh->loop_kill_len;
|
||||
|
||||
/* Setup Polygon Overlap. */
|
||||
|
||||
r_vlinks.fill(0);
|
||||
|
||||
for (const WeldPoly &wp : r_weld_mesh->wpoly) {
|
||||
WeldLoopOfPolyIter iter;
|
||||
if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) {
|
||||
while (weld_iter_loop_of_poly_next(iter)) {
|
||||
r_vlinks[iter.v]++;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
int link_len = 0;
|
||||
for (const int i : IndexRange(mvert_len)) {
|
||||
link_len += r_vlinks[i];
|
||||
r_vlinks[i] = link_len;
|
||||
}
|
||||
r_vlinks[mvert_len] = link_len;
|
||||
|
||||
if (link_len) {
|
||||
Array<int> link_poly_buffer(link_len);
|
||||
|
||||
/* Use a reverse for loop to ensure that indexes are assigned in ascending order. */
|
||||
for (int i = r_weld_mesh->wpoly.size(); i--;) {
|
||||
const WeldPoly &wp = wpoly[i];
|
||||
WeldLoopOfPolyIter iter;
|
||||
if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) {
|
||||
while (weld_iter_loop_of_poly_next(iter)) {
|
||||
link_poly_buffer[--r_vlinks[iter.v]] = i;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
int polys_len_a, polys_len_b, *polys_ctx_a, *polys_ctx_b, p_ctx_a, p_ctx_b;
|
||||
polys_len_b = p_ctx_b = 0; /* silence warnings */
|
||||
|
||||
for (const int i : IndexRange(r_weld_mesh->wpoly.size())) {
|
||||
const WeldPoly &wp = wpoly[i];
|
||||
if (wp.poly_dst != OUT_OF_CONTEXT) {
|
||||
/* No need to retest poly.
|
||||
* (Already includes collapsed polygons). */
|
||||
continue;
|
||||
}
|
||||
|
||||
WeldLoopOfPolyIter iter;
|
||||
weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr);
|
||||
weld_iter_loop_of_poly_next(iter);
|
||||
const int link_a = r_vlinks[iter.v];
|
||||
polys_len_a = r_vlinks[iter.v + 1] - link_a;
|
||||
if (polys_len_a == 1) {
|
||||
BLI_assert(link_poly_buffer[link_a] == i);
|
||||
continue;
|
||||
}
|
||||
int wp_loop_len = wp.loop_len;
|
||||
polys_ctx_a = &link_poly_buffer[link_a];
|
||||
for (; polys_len_a--; polys_ctx_a++) {
|
||||
p_ctx_a = *polys_ctx_a;
|
||||
if (p_ctx_a == i) {
|
||||
continue;
|
||||
}
|
||||
|
||||
WeldPoly *wp_tmp = &wpoly[p_ctx_a];
|
||||
if (wp_tmp->loop_len != wp_loop_len) {
|
||||
continue;
|
||||
}
|
||||
|
||||
WeldLoopOfPolyIter iter_b = iter;
|
||||
while (weld_iter_loop_of_poly_next(iter_b)) {
|
||||
const int link_b = r_vlinks[iter_b.v];
|
||||
polys_len_b = r_vlinks[iter_b.v + 1] - link_b;
|
||||
if (polys_len_b == 1) {
|
||||
BLI_assert(link_poly_buffer[link_b] == i);
|
||||
polys_len_b = 0;
|
||||
break;
|
||||
}
|
||||
|
||||
polys_ctx_b = &link_poly_buffer[link_b];
|
||||
for (; polys_len_b; polys_len_b--, polys_ctx_b++) {
|
||||
p_ctx_b = *polys_ctx_b;
|
||||
if (p_ctx_b < p_ctx_a) {
|
||||
continue;
|
||||
}
|
||||
if (p_ctx_b >= p_ctx_a) {
|
||||
if (p_ctx_b > p_ctx_a) {
|
||||
polys_len_b = 0;
|
||||
}
|
||||
break;
|
||||
}
|
||||
}
|
||||
if (polys_len_b == 0) {
|
||||
break;
|
||||
}
|
||||
}
|
||||
if (polys_len_b == 0) {
|
||||
continue;
|
||||
}
|
||||
BLI_assert(p_ctx_a > i);
|
||||
BLI_assert(p_ctx_a == p_ctx_b);
|
||||
BLI_assert(wp_tmp->poly_dst == OUT_OF_CONTEXT);
|
||||
BLI_assert(wp_tmp != &wp);
|
||||
wp_tmp->poly_dst = wp.poly_orig;
|
||||
loop_kill_len += wp_tmp->loop_len;
|
||||
poly_kill_len++;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
r_weld_mesh->poly_kill_len = poly_kill_len;
|
||||
r_weld_mesh->loop_kill_len = loop_kill_len;
|
||||
|
||||
#ifdef USE_WELD_DEBUG
|
||||
weld_assert_poly_and_loop_kill_len(
|
||||
r_weld_mesh, mloop, mpoly, r_weld_mesh->poly_kill_len, r_weld_mesh->loop_kill_len);
|
||||
#endif
|
||||
}
|
||||
|
||||
/** \} */
|
||||
|
|
@ -1217,24 +1249,34 @@ static void weld_mesh_context_create(const Mesh &mesh,
|
|||
|
||||
Array<int> edge_dest_map(edges.size());
|
||||
Array<int> edge_ctx_map(edges.size());
|
||||
Vector<WeldEdge> wedge = weld_edge_ctx_alloc(edges, vert_dest_map, edge_dest_map, edge_ctx_map);
|
||||
Vector<WeldEdge> wedge = weld_edge_ctx_alloc_and_find_collapsed(
|
||||
edges, vert_dest_map, edge_dest_map, edge_ctx_map, &r_weld_mesh->edge_kill_len);
|
||||
|
||||
/* Add +1 to allow calculation of the length of the last group. */
|
||||
Array<int> v_links(mvert_len + 1);
|
||||
weld_edge_ctx_setup(v_links, edge_dest_map, wedge, &r_weld_mesh->edge_kill_len);
|
||||
weld_edge_find_doubles(wedge.size() - r_weld_mesh->edge_kill_len,
|
||||
v_links,
|
||||
edge_dest_map,
|
||||
wedge,
|
||||
&r_weld_mesh->edge_kill_len);
|
||||
|
||||
weld_poly_loop_ctx_alloc(polys, loops, vert_dest_map, edge_dest_map, r_weld_mesh);
|
||||
|
||||
weld_poly_loop_ctx_setup(loops,
|
||||
weld_poly_loop_ctx_setup_collapsed_and_split(loops,
|
||||
#ifdef USE_WELD_DEBUG
|
||||
polys,
|
||||
|
||||
polys,
|
||||
#endif
|
||||
mvert_len,
|
||||
vert_dest_map,
|
||||
wedge.size() - r_weld_mesh->edge_kill_len,
|
||||
v_links,
|
||||
r_weld_mesh);
|
||||
vert_dest_map,
|
||||
wedge.size() - r_weld_mesh->edge_kill_len,
|
||||
r_weld_mesh);
|
||||
|
||||
weld_poly_find_doubles(loops,
|
||||
#ifdef USE_WELD_DEBUG
|
||||
polys,
|
||||
#endif
|
||||
mvert_len,
|
||||
v_links,
|
||||
r_weld_mesh);
|
||||
|
||||
weld_vert_groups_setup(wvert,
|
||||
vert_dest_map,
|
||||
|
|
|
|||
Loading…
Reference in New Issue