Changeset View
Changeset View
Standalone View
Standalone View
source/blender/geometry/intern/mesh_merge_by_distance.cc
| Show All 9 Lines | |||||
| #include "DNA_mesh_types.h" | #include "DNA_mesh_types.h" | ||||
| #include "DNA_meshdata_types.h" | #include "DNA_meshdata_types.h" | ||||
| #include "BKE_customdata.h" | #include "BKE_customdata.h" | ||||
| #include "BKE_mesh.h" | #include "BKE_mesh.h" | ||||
| #include "GEO_mesh_merge_by_distance.hh" | #include "GEO_mesh_merge_by_distance.hh" | ||||
| //#define USE_WELD_DEBUG | // #define USE_WELD_DEBUG | ||||
| namespace blender::geometry { | namespace blender::geometry { | ||||
| /* Indicates when the element was not computed. */ | /* Indicates when the element was not computed. */ | ||||
| #define OUT_OF_CONTEXT int(-1) | #define OUT_OF_CONTEXT int(-1) | ||||
| /* Indicates if the edge or face will be collapsed. */ | /* Indicates if the edge or face will be collapsed. */ | ||||
| #define ELEM_COLLAPSED int(-2) | #define ELEM_COLLAPSED int(-2) | ||||
| /* indicates whether an edge or vertex in groups_map will be merged. */ | /* indicates whether an edge or vertex in groups_map will be merged. */ | ||||
| ▲ Show 20 Lines • Show All 372 Lines • ▼ Show 20 Lines | |||||
| * \{ */ | * \{ */ | ||||
| /** | /** | ||||
| * Alloc Weld Edges. | * Alloc Weld Edges. | ||||
| * | * | ||||
| * \return r_edge_dest_map: First step to create map of indices pointing edges that will be merged. | * \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. | * \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, | static Vector<WeldEdge> weld_edge_ctx_alloc_and_find_collapsed(Span<MEdge> medge, | ||||
| Span<int> vert_dest_map, | Span<int> vert_dest_map, | ||||
| MutableSpan<int> r_edge_dest_map, | MutableSpan<int> r_edge_dest_map, | ||||
| MutableSpan<int> r_edge_ctx_map) | MutableSpan<int> r_edge_ctx_map, | ||||
| int *r_edge_collapsed_len) | |||||
| { | { | ||||
| /* Edge Context. */ | /* Edge Context. */ | ||||
| int wedge_len = 0; | int wedge_len = 0; | ||||
| int edge_collapsed_len = 0; | |||||
| Vector<WeldEdge> wedge; | Vector<WeldEdge> wedge; | ||||
| wedge.reserve(medge.size()); | wedge.reserve(medge.size()); | ||||
| for (const int i : medge.index_range()) { | for (const int i : medge.index_range()) { | ||||
| int v1 = medge[i].v1; | int v1 = medge[i].v1; | ||||
| int v2 = medge[i].v2; | int v2 = medge[i].v2; | ||||
| int v_dest_1 = vert_dest_map[v1]; | int v_dest_1 = vert_dest_map[v1]; | ||||
| int v_dest_2 = vert_dest_map[v2]; | int v_dest_2 = vert_dest_map[v2]; | ||||
| if ((v_dest_1 != OUT_OF_CONTEXT) || (v_dest_2 != OUT_OF_CONTEXT)) { | if ((v_dest_1 != OUT_OF_CONTEXT) || (v_dest_2 != OUT_OF_CONTEXT)) { | ||||
| WeldEdge we{}; | WeldEdge we{}; | ||||
| we.vert_a = (v_dest_1 != OUT_OF_CONTEXT) ? v_dest_1 : v1; | we.vert_a = (v_dest_1 != OUT_OF_CONTEXT) ? v_dest_1 : v1; | ||||
| we.vert_b = (v_dest_2 != OUT_OF_CONTEXT) ? v_dest_2 : v2; | we.vert_b = (v_dest_2 != OUT_OF_CONTEXT) ? v_dest_2 : v2; | ||||
| we.edge_dest = OUT_OF_CONTEXT; | we.edge_dest = OUT_OF_CONTEXT; | ||||
| we.edge_orig = i; | we.edge_orig = i; | ||||
| wedge.append(we); | |||||
| if (we.vert_a != we.vert_b) { | |||||
| r_edge_dest_map[i] = i; | r_edge_dest_map[i] = i; | ||||
| r_edge_ctx_map[i] = wedge_len++; | r_edge_ctx_map[i] = wedge_len; | ||||
| we.flag = ELEM_COLLAPSED; | |||||
| edge_collapsed_len++; | |||||
| } | |||||
| else { | |||||
| r_edge_dest_map[i] = OUT_OF_CONTEXT; | |||||
| r_edge_ctx_map[i] = OUT_OF_CONTEXT; | |||||
| } | |||||
| wedge.append(we); | |||||
| wedge_len++; | |||||
| } | } | ||||
| else { | else { | ||||
| r_edge_dest_map[i] = OUT_OF_CONTEXT; | r_edge_dest_map[i] = OUT_OF_CONTEXT; | ||||
| r_edge_ctx_map[i] = OUT_OF_CONTEXT; | r_edge_ctx_map[i] = OUT_OF_CONTEXT; | ||||
| } | } | ||||
| } | } | ||||
| *r_edge_collapsed_len = edge_collapsed_len; | |||||
| return wedge; | return wedge; | ||||
| } | } | ||||
| /** | /** | ||||
| * Configure Weld Edges. | * Configure Weld Edges. | ||||
| * | * | ||||
| * \param r_vlinks: An uninitialized buffer used to compute groups of WeldEdges attached to each | * \param r_vlinks: An uninitialized buffer used to compute groups of WeldEdges attached to each | ||||
| * weld target vertex. It doesn't need to be passed as a parameter but this is | * weld target vertex. It doesn't need to be passed as a parameter but this is | ||||
| * done to reduce allocations. | * done to reduce allocations. | ||||
| * \return r_edge_dest_map: Map of indices pointing edges that will be merged. | * \return r_edge_dest_map: Map of indices pointing edges that will be merged. | ||||
| * \return r_wedge: Weld edges. `flag` and `edge_dest` members will be set here. | * \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. | * \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, | static void weld_edge_find_doubles(int remain_edge_ctx_len, | ||||
| MutableSpan<int> r_vlinks, | |||||
| MutableSpan<int> r_edge_dest_map, | MutableSpan<int> r_edge_dest_map, | ||||
| MutableSpan<WeldEdge> r_wedge, | MutableSpan<WeldEdge> r_wedge, | ||||
| int *r_edge_kill_len) | int *r_edge_kill_len) | ||||
| { | { | ||||
| if (remain_edge_ctx_len == 0) { | |||||
| return; | |||||
| } | |||||
| /* Setup Edge Overlap. */ | /* Setup Edge Overlap. */ | ||||
| int edge_kill_len = 0; | int edge_double_len = 0; | ||||
| r_vlinks.fill(0); | r_vlinks.fill(0); | ||||
| for (WeldEdge &we : r_wedge) { | for (WeldEdge &we : r_wedge) { | ||||
| int dst_vert_a = we.vert_a; | if (we.flag == ELEM_COLLAPSED) { | ||||
| int dst_vert_b = we.vert_b; | |||||
| if (dst_vert_a == dst_vert_b) { | |||||
| BLI_assert(we.edge_dest == OUT_OF_CONTEXT); | BLI_assert(we.edge_dest == OUT_OF_CONTEXT); | ||||
| r_edge_dest_map[we.edge_orig] = ELEM_COLLAPSED; | BLI_assert(r_edge_dest_map[we.edge_orig] == ELEM_COLLAPSED); | ||||
| we.flag = ELEM_COLLAPSED; | |||||
| edge_kill_len++; | |||||
| continue; | continue; | ||||
| } | } | ||||
| r_vlinks[dst_vert_a]++; | BLI_assert(we.vert_a != we.vert_b); | ||||
| r_vlinks[dst_vert_b]++; | r_vlinks[we.vert_a]++; | ||||
| r_vlinks[we.vert_b]++; | |||||
| } | } | ||||
| int link_len = 0; | int link_len = 0; | ||||
| for (const int i : IndexRange(r_vlinks.size() - 1)) { | for (const int i : IndexRange(r_vlinks.size() - 1)) { | ||||
| link_len += r_vlinks[i]; | link_len += r_vlinks[i]; | ||||
| r_vlinks[i] = link_len; | r_vlinks[i] = link_len; | ||||
| } | } | ||||
| r_vlinks.last() = link_len; | r_vlinks.last() = link_len; | ||||
| if (link_len > 0) { | BLI_assert(link_len > 0); | ||||
| Array<int> link_edge_buffer(link_len); | Array<int> link_edge_buffer(link_len); | ||||
| /* Use a reverse for loop to ensure that indexes are assigned in ascending order. */ | /* Use a reverse for loop to ensure that indexes are assigned in ascending order. */ | ||||
| for (int i = r_wedge.size(); i--;) { | for (int i = r_wedge.size(); i--;) { | ||||
| const WeldEdge &we = r_wedge[i]; | const WeldEdge &we = r_wedge[i]; | ||||
| if (we.flag == ELEM_COLLAPSED) { | if (we.flag == ELEM_COLLAPSED) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| int dst_vert_a = we.vert_a; | int dst_vert_a = we.vert_a; | ||||
| int dst_vert_b = we.vert_b; | int dst_vert_b = we.vert_b; | ||||
| link_edge_buffer[--r_vlinks[dst_vert_a]] = i; | link_edge_buffer[--r_vlinks[dst_vert_a]] = i; | ||||
| link_edge_buffer[--r_vlinks[dst_vert_b]] = i; | link_edge_buffer[--r_vlinks[dst_vert_b]] = i; | ||||
| } | } | ||||
| for (const int i : r_wedge.index_range()) { | for (const int i : r_wedge.index_range()) { | ||||
| const WeldEdge &we = r_wedge[i]; | const WeldEdge &we = r_wedge[i]; | ||||
| if (we.edge_dest != OUT_OF_CONTEXT) { | if (we.edge_dest != OUT_OF_CONTEXT) { | ||||
| /* No need to retest edges. | /* No need to retest edges. | ||||
| * (Already includes collapsed edges). */ | * (Already includes collapsed edges). */ | ||||
| continue; | continue; | ||||
| } | } | ||||
| int dst_vert_a = we.vert_a; | int dst_vert_a = we.vert_a; | ||||
| int dst_vert_b = we.vert_b; | int dst_vert_b = we.vert_b; | ||||
| const int link_a = r_vlinks[dst_vert_a]; | const int link_a = r_vlinks[dst_vert_a]; | ||||
| const int link_b = r_vlinks[dst_vert_b]; | const int link_b = r_vlinks[dst_vert_b]; | ||||
| int edges_len_a = r_vlinks[dst_vert_a + 1] - link_a; | int edges_len_a = r_vlinks[dst_vert_a + 1] - link_a; | ||||
| int edges_len_b = r_vlinks[dst_vert_b + 1] - link_b; | int edges_len_b = r_vlinks[dst_vert_b + 1] - link_b; | ||||
| if (edges_len_a <= 1 || edges_len_b <= 1) { | if (edges_len_a <= 1 || edges_len_b <= 1) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| int *edges_ctx_a = &link_edge_buffer[link_a]; | int *edges_ctx_a = &link_edge_buffer[link_a]; | ||||
| int *edges_ctx_b = &link_edge_buffer[link_b]; | int *edges_ctx_b = &link_edge_buffer[link_b]; | ||||
| int edge_orig = we.edge_orig; | int edge_orig = we.edge_orig; | ||||
| for (; edges_len_a--; edges_ctx_a++) { | for (; edges_len_a--; edges_ctx_a++) { | ||||
| int e_ctx_a = *edges_ctx_a; | int e_ctx_a = *edges_ctx_a; | ||||
| if (e_ctx_a == i) { | if (e_ctx_a == i) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| while (edges_len_b && *edges_ctx_b < e_ctx_a) { | while (edges_len_b && *edges_ctx_b < e_ctx_a) { | ||||
| edges_ctx_b++; | edges_ctx_b++; | ||||
| edges_len_b--; | edges_len_b--; | ||||
| } | } | ||||
| if (edges_len_b == 0) { | if (edges_len_b == 0) { | ||||
| break; | break; | ||||
| } | } | ||||
| int e_ctx_b = *edges_ctx_b; | int e_ctx_b = *edges_ctx_b; | ||||
| if (e_ctx_a == e_ctx_b) { | if (e_ctx_a == e_ctx_b) { | ||||
| WeldEdge *we_b = &r_wedge[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_a, dst_vert_a, dst_vert_b)); | ||||
| BLI_assert(ELEM(we_b->vert_b, 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_dest == OUT_OF_CONTEXT); | ||||
| BLI_assert(we_b->edge_orig != edge_orig); | BLI_assert(we_b->edge_orig != edge_orig); | ||||
| r_edge_dest_map[we_b->edge_orig] = edge_orig; | r_edge_dest_map[we_b->edge_orig] = edge_orig; | ||||
| we_b->edge_dest = edge_orig; | we_b->edge_dest = edge_orig; | ||||
| edge_kill_len++; | edge_double_len++; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| *r_edge_kill_len += edge_double_len; | |||||
| #ifdef USE_WELD_DEBUG | #ifdef USE_WELD_DEBUG | ||||
| weld_assert_edge_kill_len(r_wedge, edge_kill_len); | weld_assert_edge_kill_len(r_wedge, *r_edge_kill_len); | ||||
| #endif | #endif | ||||
| } | } | ||||
| *r_edge_kill_len = edge_kill_len; | |||||
| } | |||||
| /** | /** | ||||
| * Create groups of edges to merge. | * Create groups of edges to merge. | ||||
| * | * | ||||
| * \return r_edge_groups_map: Map that points out the group of edges that an edge belongs to. | * \return r_edge_groups_map: Map that points out the group of edges that an edge belongs to. | ||||
| * \return r_edge_groups_buffer: Buffer containing the indices of all edges that merge. | * \return r_edge_groups_buffer: Buffer containing the indices of all edges that merge. | ||||
| * \return r_edge_groups_offs: Array that indicates where each edge group starts in the buffer. | * \return r_edge_groups_offs: Array that indicates where each edge group starts in the buffer. | ||||
| */ | */ | ||||
| static void weld_edge_groups_setup(const int medge_len, | static void weld_edge_groups_setup(const int medge_len, | ||||
| ▲ Show 20 Lines • Show All 421 Lines • ▼ Show 20 Lines | |||||
| * Alloc Weld Polygons and Weld Loops. | * Alloc Weld Polygons and Weld Loops. | ||||
| * | * | ||||
| * \param remain_edge_ctx_len: Context weld edges that won't be destroyed by merging or collapsing. | * \param remain_edge_ctx_len: Context weld edges that won't be destroyed by merging or collapsing. | ||||
| * \param r_vlinks: An uninitialized buffer used to compute groups of WeldPolys attached to each | * \param r_vlinks: An uninitialized buffer used to compute groups of WeldPolys attached to each | ||||
| * weld target vertex. It doesn't need to be passed as a parameter but this is | * weld target vertex. It doesn't need to be passed as a parameter but this is | ||||
| * done to reduce allocations. | * done to reduce allocations. | ||||
| * \return r_weld_mesh: Loop and poly members will be configured here. | * \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 | #ifdef USE_WELD_DEBUG | ||||
| Span<MPoly> mpoly, | Span<MPoly> mpoly, | ||||
| #endif | #endif | ||||
| const int mvert_len, | |||||
| Span<int> vert_dest_map, | Span<int> vert_dest_map, | ||||
| const int remain_edge_ctx_len, | const int remain_edge_ctx_len, | ||||
| MutableSpan<int> r_vlinks, | |||||
| WeldMesh *r_weld_mesh) | WeldMesh *r_weld_mesh) | ||||
| { | { | ||||
| 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(); | WeldPoly *wpoly = r_weld_mesh->wpoly.data(); | ||||
| MutableSpan<WeldLoop> wloop = r_weld_mesh->wloop; | 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; | BLI_assert(r_weld_mesh->poly_kill_len == 0); | ||||
| BLI_assert(r_weld_mesh->poly_kill_len == 0); | |||||
| if (remain_edge_ctx_len) { | int poly_kill_len = 0; | ||||
| int loop_kill_len = 0; | |||||
| /* Setup Poly/Loop. */ | /* Setup Poly/Loop. */ | ||||
| /* `wpoly.size()` may change during the loop, | /* `wpoly.size()` may change during the loop, | ||||
| * so make it clear that we are only working with the original wpolys. */ | * so make it clear that we are only working with the original wpolys. */ | ||||
| IndexRange wpoly_original_range = r_weld_mesh->wpoly.index_range(); | IndexRange wpoly_original_range = r_weld_mesh->wpoly.index_range(); | ||||
| for (const int i : wpoly_original_range) { | for (const int i : wpoly_original_range) { | ||||
| WeldPoly &wp = wpoly[i]; | WeldPoly &wp = wpoly[i]; | ||||
| const int ctx_loops_len = wp.loops.len; | const int ctx_loops_len = wp.loops.len; | ||||
| const int ctx_loops_ofs = wp.loops.offs; | const int ctx_loops_ofs = wp.loops.offs; | ||||
| int poly_loop_len = wp.loop_len; | int poly_loop_len = wp.loop_len; | ||||
| int ctx_verts_len = 0; | int ctx_verts_len = 0; | ||||
| WeldLoop *wl = &wloop[ctx_loops_ofs]; | WeldLoop *wl = &wloop[ctx_loops_ofs]; | ||||
| for (int l = ctx_loops_len; l--; wl++) { | for (int l = ctx_loops_len; l--; wl++) { | ||||
| const int edge_dest = wl->edge; | const int edge_dest = wl->edge; | ||||
| if (edge_dest == ELEM_COLLAPSED) { | if (edge_dest == ELEM_COLLAPSED) { | ||||
| wl->flag = ELEM_COLLAPSED; | wl->flag = ELEM_COLLAPSED; | ||||
| if (poly_loop_len == 3) { | if (poly_loop_len == 3) { | ||||
| wp.flag = ELEM_COLLAPSED; | wp.flag = ELEM_COLLAPSED; | ||||
| poly_kill_len++; | poly_kill_len++; | ||||
| loop_kill_len += 3; | loop_kill_len += 3; | ||||
| poly_loop_len = 0; | poly_loop_len = 0; | ||||
| break; | break; | ||||
| } | } | ||||
| loop_kill_len++; | loop_kill_len++; | ||||
| poly_loop_len--; | poly_loop_len--; | ||||
| } | } | ||||
| else { | else { | ||||
| const int vert_dst = wl->vert; | const int vert_dst = wl->vert; | ||||
| if (vert_dest_map[vert_dst] != OUT_OF_CONTEXT) { | if (vert_dest_map[vert_dst] != OUT_OF_CONTEXT) { | ||||
| ctx_verts_len++; | ctx_verts_len++; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| if (poly_loop_len) { | if (poly_loop_len) { | ||||
| wp.loop_len = poly_loop_len; | wp.loop_len = poly_loop_len; | ||||
| #ifdef USE_WELD_DEBUG | #ifdef USE_WELD_DEBUG | ||||
| weld_assert_poly_len(&wp, wloop); | weld_assert_poly_len(&wp, wloop); | ||||
| #endif | #endif | ||||
| weld_poly_split_recursive(vert_dest_map, | weld_poly_split_recursive(vert_dest_map, | ||||
| #ifdef USE_WELD_DEBUG | #ifdef USE_WELD_DEBUG | ||||
| mloop, | mloop, | ||||
| #endif | #endif | ||||
| ctx_verts_len, | ctx_verts_len, | ||||
| &wp, | &wp, | ||||
| r_weld_mesh, | r_weld_mesh, | ||||
| &poly_kill_len, | &poly_kill_len, | ||||
| &loop_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 | #ifdef USE_WELD_DEBUG | ||||
| weld_assert_poly_and_loop_kill_len(r_weld_mesh, mloop, mpoly, poly_kill_len, loop_kill_len); | const Span<MPoly> mpoly, | ||||
| #endif | #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. */ | /* Setup Polygon Overlap. */ | ||||
| r_vlinks.fill(0); | r_vlinks.fill(0); | ||||
| for (const WeldPoly &wp : r_weld_mesh->wpoly) { | for (const WeldPoly &wp : r_weld_mesh->wpoly) { | ||||
| WeldLoopOfPolyIter iter; | WeldLoopOfPolyIter iter; | ||||
| if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) { | if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) { | ||||
| while (weld_iter_loop_of_poly_next(iter)) { | while (weld_iter_loop_of_poly_next(iter)) { | ||||
| r_vlinks[iter.v]++; | r_vlinks[iter.v]++; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| int link_len = 0; | int link_len = 0; | ||||
| for (const int i : IndexRange(mvert_len)) { | for (const int i : IndexRange(mvert_len)) { | ||||
| link_len += r_vlinks[i]; | link_len += r_vlinks[i]; | ||||
| r_vlinks[i] = link_len; | r_vlinks[i] = link_len; | ||||
| } | } | ||||
| r_vlinks[mvert_len] = link_len; | r_vlinks[mvert_len] = link_len; | ||||
| if (link_len) { | if (link_len) { | ||||
| Array<int> link_poly_buffer(link_len); | Array<int> link_poly_buffer(link_len); | ||||
| /* Use a reverse for loop to ensure that indexes are assigned in ascending order. */ | /* Use a reverse for loop to ensure that indexes are assigned in ascending order. */ | ||||
| for (int i = r_weld_mesh->wpoly.size(); i--;) { | for (int i = r_weld_mesh->wpoly.size(); i--;) { | ||||
| const WeldPoly &wp = wpoly[i]; | const WeldPoly &wp = wpoly[i]; | ||||
| WeldLoopOfPolyIter iter; | WeldLoopOfPolyIter iter; | ||||
| if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) { | if (weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr)) { | ||||
| while (weld_iter_loop_of_poly_next(iter)) { | while (weld_iter_loop_of_poly_next(iter)) { | ||||
| link_poly_buffer[--r_vlinks[iter.v]] = i; | 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; | 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 */ | polys_len_b = p_ctx_b = 0; /* silence warnings */ | ||||
| for (const int i : IndexRange(r_weld_mesh->wpoly.size())) { | for (const int i : IndexRange(r_weld_mesh->wpoly.size())) { | ||||
| const WeldPoly &wp = wpoly[i]; | const WeldPoly &wp = wpoly[i]; | ||||
| if (wp.poly_dst != OUT_OF_CONTEXT) { | if (wp.poly_dst != OUT_OF_CONTEXT) { | ||||
| /* No need to retest poly. | /* No need to retest poly. | ||||
| * (Already includes collapsed polygons). */ | * (Already includes collapsed polygons). */ | ||||
| continue; | continue; | ||||
| } | } | ||||
| WeldLoopOfPolyIter iter; | WeldLoopOfPolyIter iter; | ||||
| weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr); | weld_iter_loop_of_poly_begin(iter, wp, wloop, mloop, loop_map, nullptr); | ||||
| weld_iter_loop_of_poly_next(iter); | weld_iter_loop_of_poly_next(iter); | ||||
| const int link_a = r_vlinks[iter.v]; | const int link_a = r_vlinks[iter.v]; | ||||
| polys_len_a = r_vlinks[iter.v + 1] - link_a; | polys_len_a = r_vlinks[iter.v + 1] - link_a; | ||||
| if (polys_len_a == 1) { | if (polys_len_a == 1) { | ||||
| BLI_assert(link_poly_buffer[link_a] == i); | BLI_assert(link_poly_buffer[link_a] == i); | ||||
| continue; | continue; | ||||
| } | } | ||||
| int wp_loop_len = wp.loop_len; | int wp_loop_len = wp.loop_len; | ||||
| polys_ctx_a = &link_poly_buffer[link_a]; | polys_ctx_a = &link_poly_buffer[link_a]; | ||||
| for (; polys_len_a--; polys_ctx_a++) { | for (; polys_len_a--; polys_ctx_a++) { | ||||
| p_ctx_a = *polys_ctx_a; | p_ctx_a = *polys_ctx_a; | ||||
| if (p_ctx_a == i) { | if (p_ctx_a == i) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| WeldPoly *wp_tmp = &wpoly[p_ctx_a]; | WeldPoly *wp_tmp = &wpoly[p_ctx_a]; | ||||
| if (wp_tmp->loop_len != wp_loop_len) { | if (wp_tmp->loop_len != wp_loop_len) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| WeldLoopOfPolyIter iter_b = iter; | WeldLoopOfPolyIter iter_b = iter; | ||||
| while (weld_iter_loop_of_poly_next(iter_b)) { | while (weld_iter_loop_of_poly_next(iter_b)) { | ||||
| const int link_b = r_vlinks[iter_b.v]; | const int link_b = r_vlinks[iter_b.v]; | ||||
| polys_len_b = r_vlinks[iter_b.v + 1] - link_b; | polys_len_b = r_vlinks[iter_b.v + 1] - link_b; | ||||
| if (polys_len_b == 1) { | if (polys_len_b == 1) { | ||||
| BLI_assert(link_poly_buffer[link_b] == i); | BLI_assert(link_poly_buffer[link_b] == i); | ||||
| polys_len_b = 0; | polys_len_b = 0; | ||||
| break; | break; | ||||
| } | } | ||||
| polys_ctx_b = &link_poly_buffer[link_b]; | polys_ctx_b = &link_poly_buffer[link_b]; | ||||
| for (; polys_len_b; polys_len_b--, polys_ctx_b++) { | for (; polys_len_b; polys_len_b--, polys_ctx_b++) { | ||||
| p_ctx_b = *polys_ctx_b; | p_ctx_b = *polys_ctx_b; | ||||
| if (p_ctx_b < p_ctx_a) { | if (p_ctx_b < p_ctx_a) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| if (p_ctx_b >= p_ctx_a) { | if (p_ctx_b >= p_ctx_a) { | ||||
| if (p_ctx_b > p_ctx_a) { | if (p_ctx_b > p_ctx_a) { | ||||
| polys_len_b = 0; | polys_len_b = 0; | ||||
| } | } | ||||
| break; | break; | ||||
| } | } | ||||
| } | } | ||||
| if (polys_len_b == 0) { | if (polys_len_b == 0) { | ||||
| break; | break; | ||||
| } | } | ||||
| } | } | ||||
| if (polys_len_b == 0) { | if (polys_len_b == 0) { | ||||
| continue; | continue; | ||||
| } | } | ||||
| BLI_assert(p_ctx_a > i); | BLI_assert(p_ctx_a > i); | ||||
| BLI_assert(p_ctx_a == p_ctx_b); | BLI_assert(p_ctx_a == p_ctx_b); | ||||
| BLI_assert(wp_tmp->poly_dst == OUT_OF_CONTEXT); | BLI_assert(wp_tmp->poly_dst == OUT_OF_CONTEXT); | ||||
| BLI_assert(wp_tmp != &wp); | BLI_assert(wp_tmp != &wp); | ||||
| wp_tmp->poly_dst = wp.poly_orig; | wp_tmp->poly_dst = wp.poly_orig; | ||||
| loop_kill_len += wp_tmp->loop_len; | loop_kill_len += wp_tmp->loop_len; | ||||
| poly_kill_len++; | poly_kill_len++; | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| } | |||||
| else { | |||||
| poly_kill_len = r_weld_mesh->wpoly.size(); | |||||
| loop_kill_len = r_weld_mesh->wloop.size(); | |||||
| for (WeldPoly &wp : r_weld_mesh->wpoly) { | r_weld_mesh->poly_kill_len = poly_kill_len; | ||||
| wp.flag = ELEM_COLLAPSED; | r_weld_mesh->loop_kill_len = loop_kill_len; | ||||
| } | |||||
| } | |||||
| #ifdef USE_WELD_DEBUG | #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_and_loop_kill_len( | ||||
| r_weld_mesh, mloop, mpoly, r_weld_mesh->poly_kill_len, r_weld_mesh->loop_kill_len); | |||||
| #endif | #endif | ||||
| r_weld_mesh->poly_kill_len = poly_kill_len; | |||||
| r_weld_mesh->loop_kill_len = loop_kill_len; | |||||
| } | } | ||||
| /** \} */ | /** \} */ | ||||
| /* -------------------------------------------------------------------- */ | /* -------------------------------------------------------------------- */ | ||||
| /** \name Mesh API | /** \name Mesh API | ||||
| * \{ */ | * \{ */ | ||||
| static void weld_mesh_context_create(const Mesh &mesh, | static void weld_mesh_context_create(const Mesh &mesh, | ||||
| MutableSpan<int> vert_dest_map, | MutableSpan<int> vert_dest_map, | ||||
| const int vert_kill_len, | const int vert_kill_len, | ||||
| MutableSpan<int> r_vert_group_map, | MutableSpan<int> r_vert_group_map, | ||||
| WeldMesh *r_weld_mesh) | WeldMesh *r_weld_mesh) | ||||
| { | { | ||||
| const int mvert_len = mesh.totvert; | const int mvert_len = mesh.totvert; | ||||
| const Span<MEdge> edges = mesh.edges(); | const Span<MEdge> edges = mesh.edges(); | ||||
| const Span<MPoly> polys = mesh.polys(); | const Span<MPoly> polys = mesh.polys(); | ||||
| const Span<MLoop> loops = mesh.loops(); | const Span<MLoop> loops = mesh.loops(); | ||||
| Vector<WeldVert> wvert = weld_vert_ctx_alloc_and_setup(vert_dest_map, vert_kill_len); | Vector<WeldVert> wvert = weld_vert_ctx_alloc_and_setup(vert_dest_map, vert_kill_len); | ||||
| r_weld_mesh->vert_kill_len = vert_kill_len; | r_weld_mesh->vert_kill_len = vert_kill_len; | ||||
| Array<int> edge_dest_map(edges.size()); | Array<int> edge_dest_map(edges.size()); | ||||
| Array<int> edge_ctx_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. */ | /* Add +1 to allow calculation of the length of the last group. */ | ||||
| Array<int> v_links(mvert_len + 1); | 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_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 | #ifdef USE_WELD_DEBUG | ||||
| polys, | polys, | ||||
| #endif | #endif | ||||
| mvert_len, | |||||
| vert_dest_map, | vert_dest_map, | ||||
| wedge.size() - r_weld_mesh->edge_kill_len, | 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, | v_links, | ||||
| r_weld_mesh); | r_weld_mesh); | ||||
| weld_vert_groups_setup(wvert, | weld_vert_groups_setup(wvert, | ||||
| vert_dest_map, | vert_dest_map, | ||||
| vert_kill_len, | vert_kill_len, | ||||
| r_vert_group_map, | r_vert_group_map, | ||||
| r_weld_mesh->vert_groups_buffer, | r_weld_mesh->vert_groups_buffer, | ||||
| r_weld_mesh->vert_groups_offs); | r_weld_mesh->vert_groups_offs); | ||||
| ▲ Show 20 Lines • Show All 454 Lines • Show Last 20 Lines | |||||