Differential D16918 Diff 59095 source/blender/geometry/intern/mesh_merge_by_distance.cc

Changeset 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