Differential D16893 Diff 59975 source/blender/blenkernel/intern/mesh_merge.c

Changeset View

Standalone View

source/blender/blenkernel/intern/mesh_merge.c

Show All 27 Lines
* Function used by #BKE_mesh_merge_verts.		* Function used by #BKE_mesh_merge_verts.
* The function compares poly_source after applying vtargetmap, with poly_target.		* The function compares poly_source after applying vtargetmap, with poly_target.
* The two polys are identical if they share the same vertices in the same order,		* The two polys are identical if they share the same vertices in the same order,
* or in reverse order, but starting position loopstart may be different.		* or in reverse order, but starting position loopstart may be different.
* The function is called with direct_reverse=1 for same order (i.e. same normal),		* The function is called with direct_reverse=1 for same order (i.e. same normal),
* and may be called again with direct_reverse=-1 for reverse order.		* and may be called again with direct_reverse=-1 for reverse order.
* \return 1 if polys are identical, 0 if polys are different.		* \return 1 if polys are identical, 0 if polys are different.
*/		*/
static int cddm_poly_compare(const MLoop *mloop_array,		static int cddm_poly_compare(const int *corner_verts,
const MPoly *mpoly_source,		const MPoly *mpoly_source,
const MPoly *mpoly_target,		const MPoly *mpoly_target,
const int *vtargetmap,		const int *vtargetmap,
const int direct_reverse)		const int direct_reverse)
{		{
int vert_source, first_vert_source, vert_target;		int vert_source, first_vert_source, vert_target;
int i_loop_source;		int i_loop_source;
int i_loop_target, i_loop_target_start, i_loop_target_offset, i_loop_target_adjusted;		int i_loop_target, i_loop_target_start, i_loop_target_offset, i_loop_target_adjusted;
bool compare_completed = false;		bool compare_completed = false;
bool same_loops = false;		bool same_loops = false;

const MLoop mloop_source, mloop_target;		const int corner_vert_source, corner_vert_target;

BLI_assert(ELEM(direct_reverse, 1, -1));		BLI_assert(ELEM(direct_reverse, 1, -1));

i_loop_source = 0;		i_loop_source = 0;
mloop_source = mloop_array + mpoly_source->loopstart;		corner_vert_source = corner_verts + mpoly_source->loopstart;
vert_source = mloop_source->v;		vert_source = *corner_vert_source;

if (vtargetmap[vert_source] != -1) {		if (vtargetmap[vert_source] != -1) {
vert_source = vtargetmap[vert_source];		vert_source = vtargetmap[vert_source];
}		}
else {		else {
/* All source loop vertices should be mapped */		/* All source loop vertices should be mapped */
BLI_assert(false);		BLI_assert(false);
}		}

/* Find same vertex within mpoly_target's loops */		/* Find same vertex within mpoly_target's loops */
mloop_target = mloop_array + mpoly_target->loopstart;		corner_vert_target = corner_verts + mpoly_target->loopstart;
for (i_loop_target = 0; i_loop_target < mpoly_target->totloop; i_loop_target++, mloop_target++) {		for (i_loop_target = 0; i_loop_target < mpoly_target->totloop;
if (mloop_target->v == vert_source) {		i_loop_target++, corner_vert_target++) {
		if (*corner_vert_target == vert_source) {
break;		break;
}		}
}		}

/* If same vertex not found, then polys cannot be equal */		/* If same vertex not found, then polys cannot be equal */
if (i_loop_target >= mpoly_target->totloop) {		if (i_loop_target >= mpoly_target->totloop) {
return false;		return false;
}		}

/* Now mloop_source and m_loop_target have one identical vertex */		/* Now corner_vert_source and m_loop_target have one identical vertex */
/* mloop_source is at position 0, while m_loop_target has advanced to find identical vertex */		/* corner_vert_source is at position 0, while m_loop_target has advanced to find identical vertex
		*/
/* Go around the loop and check that all vertices match in same order */		/* Go around the loop and check that all vertices match in same order */
/* Skipping source loops when consecutive source vertices are mapped to same target vertex */		/* Skipping source loops when consecutive source vertices are mapped to same target vertex */

i_loop_target_start = i_loop_target;		i_loop_target_start = i_loop_target;
i_loop_target_offset = 0;		i_loop_target_offset = 0;
first_vert_source = vert_source;		first_vert_source = vert_source;

compare_completed = false;		compare_completed = false;
same_loops = false;		same_loops = false;

while (!compare_completed) {		while (!compare_completed) {

vert_target = mloop_target->v;		vert_target = *corner_vert_target;

/* First advance i_loop_source, until it points to different vertex, after mapping applied */		/* First advance i_loop_source, until it points to different vertex, after mapping applied */
do {		do {
i_loop_source++;		i_loop_source++;

if (i_loop_source == mpoly_source->totloop) {		if (i_loop_source == mpoly_source->totloop) {
/* End of loops for source, must match end of loop for target. */		/* End of loops for source, must match end of loop for target. */
if (i_loop_target_offset == mpoly_target->totloop - 1) {		if (i_loop_target_offset == mpoly_target->totloop - 1) {
compare_completed = true;		compare_completed = true;
same_loops = true;		same_loops = true;
break; /* Polys are identical */		break; /* Polys are identical */
}		}

compare_completed = true;		compare_completed = true;
same_loops = false;		same_loops = false;
break; /* Polys are different */		break; /* Polys are different */
}		}

mloop_source++;		corner_vert_source++;
vert_source = mloop_source->v;		vert_source = *corner_vert_source;

if (vtargetmap[vert_source] != -1) {		if (vtargetmap[vert_source] != -1) {
vert_source = vtargetmap[vert_source];		vert_source = vtargetmap[vert_source];
}		}
else {		else {
/* All source loop vertices should be mapped */		/* All source loop vertices should be mapped */
BLI_assert(false);		BLI_assert(false);
}		}

} while (vert_source == vert_target);		} while (vert_source == vert_target);

if (compare_completed) {		if (compare_completed) {
break;		break;
}		}

/* Now advance i_loop_target as well */		/* Now advance i_loop_target as well */
i_loop_target_offset++;		i_loop_target_offset++;

if (i_loop_target_offset == mpoly_target->totloop) {		if (i_loop_target_offset == mpoly_target->totloop) {
/* End of loops for target only, that means no match */		/* End of loops for target only, that means no match */
/* except if all remaining source vertices are mapped to first target */		/* except if all remaining source vertices are mapped to first target */
for (; i_loop_source < mpoly_source->totloop; i_loop_source++, mloop_source++) {		for (; i_loop_source < mpoly_source->totloop; i_loop_source++, corner_vert_source++) {
vert_source = vtargetmap[mloop_source->v];		vert_source = vtargetmap[*corner_vert_source];
if (vert_source != first_vert_source) {		if (vert_source != first_vert_source) {
compare_completed = true;		compare_completed = true;
same_loops = false;		same_loops = false;
break;		break;
}		}
}		}
if (!compare_completed) {		if (!compare_completed) {
same_loops = true;		same_loops = true;
}		}
break;		break;
}		}

/* Adjust i_loop_target for cycling around and for direct/reverse order		/* Adjust i_loop_target for cycling around and for direct/reverse order
* defined by delta = +1 or -1 */		* defined by delta = +1 or -1 */
i_loop_target_adjusted = (i_loop_target_start + direct_reverse * i_loop_target_offset) %		i_loop_target_adjusted = (i_loop_target_start + direct_reverse * i_loop_target_offset) %
mpoly_target->totloop;		mpoly_target->totloop;
if (i_loop_target_adjusted < 0) {		if (i_loop_target_adjusted < 0) {
i_loop_target_adjusted += mpoly_target->totloop;		i_loop_target_adjusted += mpoly_target->totloop;
}		}
mloop_target = mloop_array + mpoly_target->loopstart + i_loop_target_adjusted;		corner_vert_target = corner_verts + mpoly_target->loopstart + i_loop_target_adjusted;
vert_target = mloop_target->v;		vert_target = *corner_vert_target;

if (vert_target != vert_source) {		if (vert_target != vert_source) {
same_loops = false; /* Polys are different */		same_loops = false; /* Polys are different */
break;		break;
}		}
}		}
return same_loops;		return same_loops;
}		}
Show All 37 Lines	Mesh BKE_mesh_merge_verts(Mesh mesh,
Mesh *result = NULL;		Mesh *result = NULL;

const int totvert = mesh->totvert;		const int totvert = mesh->totvert;
const int totedge = mesh->totedge;		const int totedge = mesh->totedge;
const int totloop = mesh->totloop;		const int totloop = mesh->totloop;
const int totpoly = mesh->totpoly;		const int totpoly = mesh->totpoly;
const MEdge *src_edges = BKE_mesh_edges(mesh);		const MEdge *src_edges = BKE_mesh_edges(mesh);
const MPoly *src_polys = BKE_mesh_polys(mesh);		const MPoly *src_polys = BKE_mesh_polys(mesh);
const MLoop *src_loops = BKE_mesh_loops(mesh);		const int *src_corner_verts = BKE_mesh_corner_verts(mesh);
		const int *src_corner_edges = BKE_mesh_corner_edges(mesh);

const int totvert_final = totvert - tot_vtargetmap;		const int totvert_final = totvert - tot_vtargetmap;

int oldv = MEM_malloc_arrayN(totvert_final, sizeof(oldv), __func__);		int oldv = MEM_malloc_arrayN(totvert_final, sizeof(oldv), __func__);
int newv = MEM_malloc_arrayN(totvert, sizeof(newv), __func__);		int newv = MEM_malloc_arrayN(totvert, sizeof(newv), __func__);
STACK_DECLARE(oldv);		STACK_DECLARE(oldv);

/* NOTE: create (totedge + totloop) elements because partially invalid polys due to merge may		/* NOTE: create (totedge + totloop) elements because partially invalid polys due to merge may
* require generating new edges, and while in 99% cases we'll still end with less final edges		* require generating new edges, and while in 99% cases we'll still end with less final edges
* than totedge, cases can be forged that would end requiring more. */		* than totedge, cases can be forged that would end requiring more. */
const MEdge *med;		const MEdge *med;
MEdge medge = MEM_malloc_arrayN((totedge + totloop), sizeof(medge), __func__);		MEdge medge = MEM_malloc_arrayN((totedge + totloop), sizeof(medge), __func__);
int olde = MEM_malloc_arrayN((totedge + totloop), sizeof(olde), __func__);		int olde = MEM_malloc_arrayN((totedge + totloop), sizeof(olde), __func__);
int newe = MEM_malloc_arrayN((totedge + totloop), sizeof(newe), __func__);		int newe = MEM_malloc_arrayN((totedge + totloop), sizeof(newe), __func__);
STACK_DECLARE(medge);		STACK_DECLARE(medge);
STACK_DECLARE(olde);		STACK_DECLARE(olde);

const MLoop *ml;		int *corner_verts = MEM_malloc_arrayN(totloop, sizeof(int), __func__);
MLoop mloop = MEM_malloc_arrayN(totloop, sizeof(mloop), __func__);		int *corner_edges = MEM_malloc_arrayN(totloop, sizeof(int), __func__);
int oldl = MEM_malloc_arrayN(totloop, sizeof(oldl), __func__);		int oldl = MEM_malloc_arrayN(totloop, sizeof(oldl), __func__);
#ifdef USE_LOOPS		#ifdef USE_LOOPS
int newl = MEM_malloc_arrayN(totloop, sizeof(newl), __func__);		int newl = MEM_malloc_arrayN(totloop, sizeof(newl), __func__);
#endif		#endif
STACK_DECLARE(mloop);		STACK_DECLARE(corner_verts);
		STACK_DECLARE(corner_edges);
STACK_DECLARE(oldl);		STACK_DECLARE(oldl);

const MPoly *mp;		const MPoly *mp;
MPoly mpoly = MEM_malloc_arrayN(totpoly, sizeof(medge), __func__);		MPoly mpoly = MEM_malloc_arrayN(totpoly, sizeof(medge), __func__);
int oldp = MEM_malloc_arrayN(totpoly, sizeof(oldp), __func__);		int oldp = MEM_malloc_arrayN(totpoly, sizeof(oldp), __func__);
STACK_DECLARE(mpoly);		STACK_DECLARE(mpoly);
STACK_DECLARE(oldp);		STACK_DECLARE(oldp);

EdgeHash *ehash = BLI_edgehash_new_ex(__func__, totedge);		EdgeHash *ehash = BLI_edgehash_new_ex(__func__, totedge);

int i, j, c;		int i, j, c;

PolyKey *poly_keys;		PolyKey *poly_keys;
GSet *poly_gset = NULL;		GSet *poly_gset = NULL;
MeshElemMap *poly_map = NULL;		MeshElemMap *poly_map = NULL;
int *poly_map_mem = NULL;		int *poly_map_mem = NULL;

STACK_INIT(oldv, totvert_final);		STACK_INIT(oldv, totvert_final);
STACK_INIT(olde, totedge);		STACK_INIT(olde, totedge);
STACK_INIT(oldl, totloop);		STACK_INIT(oldl, totloop);
STACK_INIT(oldp, totpoly);		STACK_INIT(oldp, totpoly);

STACK_INIT(medge, totedge);		STACK_INIT(medge, totedge);
STACK_INIT(mloop, totloop);		STACK_INIT(corner_verts, totloop);
		STACK_INIT(corner_edges, totloop);
STACK_INIT(mpoly, totpoly);		STACK_INIT(mpoly, totpoly);

/* fill newv with destination vertex indices */		/* fill newv with destination vertex indices */
c = 0;		c = 0;
for (i = 0; i < totvert; i++) {		for (i = 0; i < totvert; i++) {
if (vtargetmap[i] == -1) {		if (vtargetmap[i] == -1) {
STACK_PUSH(oldv, i);		STACK_PUSH(oldv, i);
newv[i] = c++;		newv[i] = c++;
▲ Show 20 Lines • Show All 52 Lines • ▼ Show 20 Lines	if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_EQUAL) {
/* Duplicates allowed because our compare function is not pure equality */		/* Duplicates allowed because our compare function is not pure equality */
BLI_gset_flag_set(poly_gset, GHASH_FLAG_ALLOW_DUPES);		BLI_gset_flag_set(poly_gset, GHASH_FLAG_ALLOW_DUPES);

mp = src_polys;		mp = src_polys;
mpgh = poly_keys;		mpgh = poly_keys;
for (i = 0; i < totpoly; i++, mp++, mpgh++) {		for (i = 0; i < totpoly; i++, mp++, mpgh++) {
mpgh->poly_index = i;		mpgh->poly_index = i;
mpgh->totloops = mp->totloop;		mpgh->totloops = mp->totloop;
ml = src_loops + mp->loopstart;
mpgh->hash_sum = mpgh->hash_xor = 0;		mpgh->hash_sum = mpgh->hash_xor = 0;
for (j = 0; j < mp->totloop; j++, ml++) {		for (j = 0; j < mp->totloop; j++) {
mpgh->hash_sum += ml->v;		const int vert_i = src_corner_verts[mp->loopstart + j];
mpgh->hash_xor ^= ml->v;		mpgh->hash_sum += vert_i;
		mpgh->hash_xor ^= vert_i;
}		}
BLI_gset_insert(poly_gset, mpgh);		BLI_gset_insert(poly_gset, mpgh);
}		}

/* Can we optimize by reusing an old `pmap`? How do we know an old `pmap` is stale? */		/* Can we optimize by reusing an old `pmap`? How do we know an old `pmap` is stale? */
/* When called by `MOD_array.c` the `cddm` has just been created, so it has no valid `pmap`. */		/* When called by `MOD_array.c` the `cddm` has just been created, so it has no valid `pmap`. */
BKE_mesh_vert_poly_map_create(		BKE_mesh_vert_poly_map_create(
&poly_map, &poly_map_mem, src_polys, src_loops, totvert, totpoly, totloop);		&poly_map, &poly_map_mem, src_polys, src_corner_verts, totvert, totpoly, totloop);
} /* done preparing for fast poly compare */		} /* done preparing for fast poly compare */

BLI_bitmap *vert_tag = BLI_BITMAP_NEW(mesh->totvert, __func__);		BLI_bitmap *vert_tag = BLI_BITMAP_NEW(mesh->totvert, __func__);

mp = src_polys;		mp = src_polys;
for (i = 0; i < totpoly; i++, mp++) {		for (i = 0; i < totpoly; i++, mp++) {
MPoly *mp_new;		MPoly *mp_new;

ml = src_loops + mp->loopstart;

/* check faces with all vertices merged */		/* check faces with all vertices merged */
bool all_verts_merged = true;		bool all_verts_merged = true;

for (j = 0; j < mp->totloop; j++, ml++) {		for (j = 0; j < mp->totloop; j++) {
if (vtargetmap[ml->v] == -1) {		const int vert_i = src_corner_verts[mp->loopstart + j];
		if (vtargetmap[vert_i] == -1) {
all_verts_merged = false;		all_verts_merged = false;
/* This will be used to check for poly using several time the same vert. */		/* This will be used to check for poly using several time the same vert. */
BLI_BITMAP_DISABLE(vert_tag, ml->v);		BLI_BITMAP_DISABLE(vert_tag, vert_i);
}		}
else {		else {
/* This will be used to check for poly using several time the same vert. */		/* This will be used to check for poly using several time the same vert. */
BLI_BITMAP_DISABLE(vert_tag, vtargetmap[ml->v]);		BLI_BITMAP_DISABLE(vert_tag, vtargetmap[vert_i]);
}		}
}		}

if (UNLIKELY(all_verts_merged)) {		if (UNLIKELY(all_verts_merged)) {
if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_MAPPED) {		if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_MAPPED) {
/* In this mode, all vertices merged is enough to dump face */		/* In this mode, all vertices merged is enough to dump face */
continue;		continue;
}		}
if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_EQUAL) {		if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_EQUAL) {
/* Additional condition for face dump: target vertices must make up an identical face.		/* Additional condition for face dump: target vertices must make up an identical face.
* The test has 2 steps:		* The test has 2 steps:
* 1) first step is fast `ghash` lookup, but not fail-proof.		* 1) first step is fast `ghash` lookup, but not fail-proof.
* 2) second step is thorough but more costly poly compare. */		* 2) second step is thorough but more costly poly compare. */
int i_poly, v_target;		int i_poly, v_target;
bool found = false;		bool found = false;
PolyKey pkey;		PolyKey pkey;

/* Use poly_gset for fast (although not 100% certain) identification of same poly */		/* Use poly_gset for fast (although not 100% certain) identification of same poly */
/* First, make up a poly_summary structure */		/* First, make up a poly_summary structure */
ml = src_loops + mp->loopstart;
pkey.hash_sum = pkey.hash_xor = 0;		pkey.hash_sum = pkey.hash_xor = 0;
pkey.totloops = 0;		pkey.totloops = 0;
for (j = 0; j < mp->totloop; j++, ml++) {		for (j = 0; j < mp->totloop; j++) {
v_target = vtargetmap[ml->v]; /* Cannot be -1, they are all mapped */		const int vert_i = src_corner_verts[mp->loopstart + j];
		v_target = vtargetmap[vert_i]; /* Cannot be -1, they are all mapped */
pkey.hash_sum += v_target;		pkey.hash_sum += v_target;
pkey.hash_xor ^= v_target;		pkey.hash_xor ^= v_target;
pkey.totloops++;		pkey.totloops++;
}		}
if (BLI_gset_haskey(poly_gset, &pkey)) {		if (BLI_gset_haskey(poly_gset, &pkey)) {

/* There might be a poly that matches this one.		/* There might be a poly that matches this one.
* We could just leave it there and say there is, and do a "continue".		* We could just leave it there and say there is, and do a "continue".
* ... but we are checking whether there is an exact poly match.		* ... but we are checking whether there is an exact poly match.
* It's not so costly in terms of CPU since it's very rare, just a lot of complex code.		* It's not so costly in terms of CPU since it's very rare, just a lot of complex code.
*/		*/

/* Consider current loop again */		/* Consider current loop again */
ml = src_loops + mp->loopstart;
/* Consider the target of the loop's first vert */		/* Consider the target of the loop's first vert */
v_target = vtargetmap[ml->v];		v_target = vtargetmap[src_corner_verts[mp->loopstart]];
/* Now see if v_target belongs to a poly that shares all vertices with source poly,		/* Now see if v_target belongs to a poly that shares all vertices with source poly,
* in same order, or reverse order */		* in same order, or reverse order */

for (i_poly = 0; i_poly < poly_map[v_target].count; i_poly++) {		for (i_poly = 0; i_poly < poly_map[v_target].count; i_poly++) {
const MPoly target_poly = src_polys + (poly_map[v_target].indices + i_poly);		const MPoly target_poly = src_polys + (poly_map[v_target].indices + i_poly);

if (cddm_poly_compare(src_loops, mp, target_poly, vtargetmap, +1) \|\|		if (cddm_poly_compare(corner_verts, mp, target_poly, vtargetmap, +1) \|\|
cddm_poly_compare(src_loops, mp, target_poly, vtargetmap, -1)) {		cddm_poly_compare(corner_verts, mp, target_poly, vtargetmap, -1)) {
found = true;		found = true;
break;		break;
}		}
}		}
if (found) {		if (found) {
/* Current poly's vertices are mapped to a poly that is strictly identical */		/* Current poly's vertices are mapped to a poly that is strictly identical */
/* Current poly is dumped */		/* Current poly is dumped */
continue;		continue;
}		}
}		}
}		}
}		}

/* Here either the poly's vertices were not all merged		/* Here either the poly's vertices were not all merged
* or they were all merged, but targets do not make up an identical poly,		* or they were all merged, but targets do not make up an identical poly,
* the poly is retained.		* the poly is retained.
*/		*/
ml = src_loops + mp->loopstart;

c = 0;		c = 0;
MLoop *last_valid_ml = NULL;		int *last_valid_corner_vert = NULL;
MLoop *first_valid_ml = NULL;		int *last_valid_corner_edge = NULL;
		int *first_valid_corner_vert = NULL;
		int *first_valid_corner_edge = NULL;
bool need_edge_from_last_valid_ml = false;		bool need_edge_from_last_valid_ml = false;
bool need_edge_to_first_valid_ml = false;		bool need_edge_to_first_valid_ml = false;
int created_edges = 0;		int created_edges = 0;
for (j = 0; j < mp->totloop; j++, ml++) {		for (j = 0; j < mp->totloop; j++) {
const uint mlv = (vtargetmap[ml->v] != -1) ? vtargetmap[ml->v] : ml->v;		const int orig_vert_i = src_corner_verts[mp->loopstart + j];
		const int orig_edge_i = src_corner_edges[mp->loopstart + j];
		const uint mlv = (vtargetmap[orig_vert_i] != -1) ? vtargetmap[orig_vert_i] : orig_vert_i;
#ifndef NDEBUG		#ifndef NDEBUG
{		{
const MLoop *next_ml = src_loops + mp->loopstart + ((j + 1) % mp->totloop);		const int next_corner_vert = src_corner_verts[mp->loopstart + ((j + 1) % mp->totloop)];
uint next_mlv = (vtargetmap[next_ml->v] != -1) ? vtargetmap[next_ml->v] : next_ml->v;		uint next_mlv = (vtargetmap[next_corner_vert] != -1) ? vtargetmap[next_corner_vert] :
med = src_edges + ml->e;		next_corner_vert;
		med = src_edges + orig_edge_i;
uint v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;		uint v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;
uint v2 = (vtargetmap[med->v2] != -1) ? vtargetmap[med->v2] : med->v2;		uint v2 = (vtargetmap[med->v2] != -1) ? vtargetmap[med->v2] : med->v2;
BLI_assert((mlv == v1 && next_mlv == v2) \|\| (mlv == v2 && next_mlv == v1));		BLI_assert((mlv == v1 && next_mlv == v2) \|\| (mlv == v2 && next_mlv == v1));
}		}
#endif		#endif
/* A loop is only valid if its matching edge is,		/* A loop is only valid if its matching edge is,
* and it's not reusing a vertex already used by this poly. */		* and it's not reusing a vertex already used by this poly. */
if (LIKELY((newe[ml->e] != -1) && !BLI_BITMAP_TEST(vert_tag, mlv))) {		if (LIKELY((newe[orig_edge_i] != -1) && !BLI_BITMAP_TEST(vert_tag, mlv))) {
BLI_BITMAP_ENABLE(vert_tag, mlv);		BLI_BITMAP_ENABLE(vert_tag, mlv);

if (UNLIKELY(last_valid_ml != NULL && need_edge_from_last_valid_ml)) {		if (UNLIKELY(last_valid_corner_vert != NULL && need_edge_from_last_valid_ml)) {
/* We need to create a new edge between last valid loop and this one! */		/* We need to create a new edge between last valid loop and this one! */
void **val_p;		void **val_p;

uint v1 = (vtargetmap[last_valid_ml->v] != -1) ? vtargetmap[last_valid_ml->v] :		uint v1 = (vtargetmap[*last_valid_corner_vert] != -1) ?
last_valid_ml->v;		vtargetmap[*last_valid_corner_vert] :
		*last_valid_corner_vert;
uint v2 = mlv;		uint v2 = mlv;
BLI_assert(v1 != v2);		BLI_assert(v1 != v2);
if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {		if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {
last_valid_ml->e = POINTER_AS_INT(*val_p);		last_valid_corner_edge = POINTER_AS_INT(val_p);
}		}
else {		else {
const int new_eidx = STACK_SIZE(medge);		const int new_eidx = STACK_SIZE(medge);
STACK_PUSH(olde, olde[last_valid_ml->e]);		STACK_PUSH(olde, olde[*last_valid_corner_edge]);
STACK_PUSH(medge, src_edges[last_valid_ml->e]);		STACK_PUSH(medge, src_edges[*last_valid_corner_edge]);
medge[new_eidx].v1 = last_valid_ml->v;		medge[new_eidx].v1 = *last_valid_corner_vert;
medge[new_eidx].v2 = ml->v;		medge[new_eidx].v2 = orig_vert_i;
/* DO NOT change newe mapping,		/* DO NOT change newe mapping,
* could break actual values due to some deleted original edges. */		* could break actual values due to some deleted original edges. */
*val_p = POINTER_FROM_INT(new_eidx);		*val_p = POINTER_FROM_INT(new_eidx);
created_edges++;		created_edges++;

last_valid_ml->e = new_eidx;		*last_valid_corner_edge = new_eidx;
}		}
need_edge_from_last_valid_ml = false;		need_edge_from_last_valid_ml = false;
}		}

#ifdef USE_LOOPS		#ifdef USE_LOOPS
newl[j + mp->loopstart] = STACK_SIZE(mloop);		newl[j + mp->loopstart] = STACK_SIZE(corner_verts);
#endif		#endif
STACK_PUSH(oldl, j + mp->loopstart);		STACK_PUSH(oldl, j + mp->loopstart);
last_valid_ml = STACK_PUSH_RET_PTR(mloop);		last_valid_corner_vert = STACK_PUSH_RET_PTR(corner_verts);
last_valid_ml = ml;		last_valid_corner_edge = STACK_PUSH_RET_PTR(corner_edges);
if (first_valid_ml == NULL) {		*last_valid_corner_vert = orig_vert_i;
first_valid_ml = last_valid_ml;		*last_valid_corner_edge = orig_edge_i;
		if (first_valid_corner_vert == NULL) {
		first_valid_corner_vert = last_valid_corner_vert;
		}
		if (first_valid_corner_edge == NULL) {
		first_valid_corner_edge = last_valid_corner_edge;
}		}
c++;		c++;

/* We absolutely HAVE to handle edge index remapping here, otherwise potential newly		/* We absolutely HAVE to handle edge index remapping here, otherwise potential newly
* created edges in that part of code make remapping later totally unreliable. */		* created edges in that part of code make remapping later totally unreliable. */
BLI_assert(newe[ml->e] != -1);		BLI_assert(newe[orig_edge_i] != -1);
last_valid_ml->e = newe[ml->e];		*last_valid_corner_edge = newe[orig_edge_i];
}		}
else {		else {
if (last_valid_ml != NULL) {		if (last_valid_corner_vert != NULL) {
need_edge_from_last_valid_ml = true;		need_edge_from_last_valid_ml = true;
}		}
else {		else {
need_edge_to_first_valid_ml = true;		need_edge_to_first_valid_ml = true;
}		}
}		}
}		}
if (UNLIKELY(last_valid_ml != NULL && !ELEM(first_valid_ml, NULL, last_valid_ml) &&		if (UNLIKELY(last_valid_corner_vert != NULL &&
		!ELEM(first_valid_corner_vert, NULL, last_valid_corner_vert) &&
(need_edge_to_first_valid_ml \|\| need_edge_from_last_valid_ml))) {		(need_edge_to_first_valid_ml \|\| need_edge_from_last_valid_ml))) {
/* We need to create a new edge between last valid loop and first valid one! */		/* We need to create a new edge between last valid loop and first valid one! */
void **val_p;		void **val_p;

uint v1 = (vtargetmap[last_valid_ml->v] != -1) ? vtargetmap[last_valid_ml->v] :		uint v1 = (vtargetmap[last_valid_corner_vert] != -1) ? vtargetmap[last_valid_corner_vert] :
last_valid_ml->v;		*last_valid_corner_vert;
uint v2 = (vtargetmap[first_valid_ml->v] != -1) ? vtargetmap[first_valid_ml->v] :		uint v2 = (vtargetmap[*first_valid_corner_vert] != -1) ?
first_valid_ml->v;		vtargetmap[*first_valid_corner_vert] :
		*first_valid_corner_vert;
BLI_assert(v1 != v2);		BLI_assert(v1 != v2);
if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {		if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {
last_valid_ml->e = POINTER_AS_INT(*val_p);		last_valid_corner_edge = POINTER_AS_INT(val_p);
}		}
else {		else {
const int new_eidx = STACK_SIZE(medge);		const int new_eidx = STACK_SIZE(medge);
STACK_PUSH(olde, olde[last_valid_ml->e]);		STACK_PUSH(olde, olde[*last_valid_corner_edge]);
STACK_PUSH(medge, src_edges[last_valid_ml->e]);		STACK_PUSH(medge, src_edges[*last_valid_corner_edge]);
medge[new_eidx].v1 = last_valid_ml->v;		medge[new_eidx].v1 = *last_valid_corner_vert;
medge[new_eidx].v2 = first_valid_ml->v;		medge[new_eidx].v2 = *first_valid_corner_vert;
/* DO NOT change newe mapping,		/* DO NOT change newe mapping,
* could break actual values due to some deleted original edges. */		* could break actual values due to some deleted original edges. */
*val_p = POINTER_FROM_INT(new_eidx);		*val_p = POINTER_FROM_INT(new_eidx);
created_edges++;		created_edges++;

last_valid_ml->e = new_eidx;		*last_valid_corner_edge = new_eidx;
}		}
need_edge_to_first_valid_ml = need_edge_from_last_valid_ml = false;		need_edge_to_first_valid_ml = need_edge_from_last_valid_ml = false;
}		}

if (UNLIKELY(c == 0)) {		if (UNLIKELY(c == 0)) {
BLI_assert(created_edges == 0);		BLI_assert(created_edges == 0);
continue;		continue;
}		}
if (UNLIKELY(c < 3)) {		if (UNLIKELY(c < 3)) {
STACK_DISCARD(oldl, c);		STACK_DISCARD(oldl, c);
STACK_DISCARD(mloop, c);		STACK_DISCARD(corner_verts, c);
		STACK_DISCARD(corner_edges, c);
if (created_edges > 0) {		if (created_edges > 0) {
for (j = STACK_SIZE(medge) - created_edges; j < STACK_SIZE(medge); j++) {		for (j = STACK_SIZE(medge) - created_edges; j < STACK_SIZE(medge); j++) {
BLI_edgehash_remove(ehash, medge[j].v1, medge[j].v2, NULL);		BLI_edgehash_remove(ehash, medge[j].v1, medge[j].v2, NULL);
}		}
STACK_DISCARD(olde, created_edges);		STACK_DISCARD(olde, created_edges);
STACK_DISCARD(medge, created_edges);		STACK_DISCARD(medge, created_edges);
}		}
continue;		continue;
}		}

mp_new = STACK_PUSH_RET_PTR(mpoly);		mp_new = STACK_PUSH_RET_PTR(mpoly);
mp_new = mp;		mp_new = mp;
mp_new->totloop = c;		mp_new->totloop = c;
BLI_assert(mp_new->totloop >= 3);		BLI_assert(mp_new->totloop >= 3);
mp_new->loopstart = STACK_SIZE(mloop) - c;		mp_new->loopstart = STACK_SIZE(corner_verts) - c;

STACK_PUSH(oldp, i);		STACK_PUSH(oldp, i);
} /* End of the loop that tests polys. */		} /* End of the loop that tests polys. */

if (poly_gset) {		if (poly_gset) {
// printf("hash quality %.6f\n", BLI_gset_calc_quality(poly_gset));		// printf("hash quality %.6f\n", BLI_gset_calc_quality(poly_gset));

BLI_gset_free(poly_gset, NULL);		BLI_gset_free(poly_gset, NULL);
MEM_freeN(poly_keys);		MEM_freeN(poly_keys);
}		}

/* Create new cddm. */		/* Create new cddm. */
result = BKE_mesh_new_nomain_from_template(		result = BKE_mesh_new_nomain_from_template(
mesh, totvert_final, STACK_SIZE(medge), 0, STACK_SIZE(mloop), STACK_SIZE(mpoly));		mesh, totvert_final, STACK_SIZE(medge), 0, STACK_SIZE(corner_verts), STACK_SIZE(mpoly));

/* Update edge indices and copy customdata. */		/* Update edge indices and copy customdata. */
MEdge *new_med = medge;		MEdge *new_med = medge;
for (i = 0; i < result->totedge; i++, new_med++) {		for (i = 0; i < result->totedge; i++, new_med++) {
BLI_assert(newv[new_med->v1] != -1);		BLI_assert(newv[new_med->v1] != -1);
new_med->v1 = newv[new_med->v1];		new_med->v1 = newv[new_med->v1];
BLI_assert(newv[new_med->v2] != -1);		BLI_assert(newv[new_med->v2] != -1);
new_med->v2 = newv[new_med->v2];		new_med->v2 = newv[new_med->v2];

/* Can happen in case vtargetmap contains some double chains, we do not support that. */		/* Can happen in case vtargetmap contains some double chains, we do not support that. */
BLI_assert(new_med->v1 != new_med->v2);		BLI_assert(new_med->v1 != new_med->v2);

CustomData_copy_data(&mesh->edata, &result->edata, olde[i], i, 1);		CustomData_copy_data(&mesh->edata, &result->edata, olde[i], i, 1);
}		}

/* Update loop indices and copy customdata. */		/* Update loop indices and copy customdata. */
MLoop *new_ml = mloop;		for (i = 0; i < result->totloop; i++) {
for (i = 0; i < result->totloop; i++, new_ml++) {
/* Edge remapping has already be done in main loop handling part above. */		/* Edge remapping has already be done in main loop handling part above. */
BLI_assert(newv[new_ml->v] != -1);		BLI_assert(newv[corner_verts[i]] != -1);
new_ml->v = newv[new_ml->v];		corner_verts[i] = newv[corner_verts[i]];

CustomData_copy_data(&mesh->ldata, &result->ldata, oldl[i], i, 1);		CustomData_copy_data(&mesh->ldata, &result->ldata, oldl[i], i, 1);
}		}

/* Copy vertex customdata. */		/* Copy vertex customdata. */
for (i = 0; i < result->totvert; i++) {		for (i = 0; i < result->totvert; i++) {
CustomData_copy_data(&mesh->vdata, &result->vdata, oldv[i], i, 1);		CustomData_copy_data(&mesh->vdata, &result->vdata, oldv[i], i, 1);
}		}

/* Copy poly customdata. */		/* Copy poly customdata. */
mp = mpoly;		mp = mpoly;
for (i = 0; i < result->totpoly; i++, mp++) {		for (i = 0; i < result->totpoly; i++, mp++) {
CustomData_copy_data(&mesh->pdata, &result->pdata, oldp[i], i, 1);		CustomData_copy_data(&mesh->pdata, &result->pdata, oldp[i], i, 1);
}		}

/* Copy over data. #CustomData_add_layer can do this, need to look it up. */		/* Copy over data. #CustomData_add_layer can do this, need to look it up. */
if (STACK_SIZE(medge)) {		if (STACK_SIZE(medge)) {
memcpy(BKE_mesh_edges_for_write(result), medge, sizeof(MEdge) * STACK_SIZE(medge));		memcpy(BKE_mesh_edges_for_write(result), medge, sizeof(MEdge) * STACK_SIZE(medge));
}		}
if (STACK_SIZE(mloop)) {		if (STACK_SIZE(corner_verts)) {
memcpy(BKE_mesh_loops_for_write(result), mloop, sizeof(MLoop) * STACK_SIZE(mloop));		memcpy(BKE_mesh_corner_verts_for_write(result),
		corner_verts,
		sizeof(int) * STACK_SIZE(corner_verts));
		}
		if (STACK_SIZE(corner_edges)) {
		memcpy(BKE_mesh_corner_edges_for_write(result),
		corner_edges,
		sizeof(int) * STACK_SIZE(corner_edges));
}		}
if (STACK_SIZE(mpoly)) {		if (STACK_SIZE(mpoly)) {
memcpy(BKE_mesh_polys_for_write(result), mpoly, sizeof(MPoly) * STACK_SIZE(mpoly));		memcpy(BKE_mesh_polys_for_write(result), mpoly, sizeof(MPoly) * STACK_SIZE(mpoly));
}		}

MEM_freeN(medge);		MEM_freeN(medge);
MEM_freeN(mloop);		MEM_freeN(corner_verts);
		MEM_freeN(corner_edges);
MEM_freeN(mpoly);		MEM_freeN(mpoly);

MEM_freeN(newv);		MEM_freeN(newv);
MEM_freeN(newe);		MEM_freeN(newe);
#ifdef USE_LOOPS		#ifdef USE_LOOPS
MEM_freeN(newl);		MEM_freeN(newl);
#endif		#endif

Show All 20 Lines