Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / mesh_merge.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * Contributor(s): Blender Foundation
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/mesh_merge.c
27  *  \ingroup bke
28  */
29 #include <string.h> // for memcpy
30
31 #include "MEM_guardedalloc.h"
32
33 #include "DNA_mesh_types.h"
34 #include "DNA_meshdata_types.h"
35
36 #include "BLI_utildefines.h"
37 #include "BLI_utildefines_stack.h"
38 #include "BLI_edgehash.h"
39 #include "BLI_ghash.h"
40
41 #include "BKE_customdata.h"
42 #include "BKE_library.h"
43 #include "BKE_mesh.h"
44 #include "BKE_mesh_mapping.h"
45
46
47 /**
48  * Poly compare with vtargetmap
49  * Function used by #BKE_mesh_merge_verts.
50  * The function compares poly_source after applying vtargetmap, with poly_target.
51  * The two polys are identical if they share the same vertices in the same order, or in reverse order,
52  * but starting position loopstart may be different.
53  * The function is called with direct_reverse=1 for same order (i.e. same normal),
54  * and may be called again with direct_reverse=-1 for reverse order.
55  * \return 1 if polys are identical,  0 if polys are different.
56  */
57 static int cddm_poly_compare(
58         MLoop *mloop_array,
59         MPoly *mpoly_source, MPoly *mpoly_target,
60         const int *vtargetmap, const int direct_reverse)
61 {
62         int vert_source, first_vert_source, vert_target;
63         int i_loop_source;
64         int i_loop_target, i_loop_target_start, i_loop_target_offset, i_loop_target_adjusted;
65         bool compare_completed = false;
66         bool same_loops = false;
67
68         MLoop *mloop_source, *mloop_target;
69
70         BLI_assert(direct_reverse == 1 || direct_reverse == -1);
71
72         i_loop_source = 0;
73         mloop_source = mloop_array + mpoly_source->loopstart;
74         vert_source = mloop_source->v;
75
76         if (vtargetmap[vert_source] != -1) {
77                 vert_source = vtargetmap[vert_source];
78         }
79         else {
80                 /* All source loop vertices should be mapped */
81                 BLI_assert(false);
82         }
83
84         /* Find same vertex within mpoly_target's loops */
85         mloop_target = mloop_array + mpoly_target->loopstart;
86         for (i_loop_target = 0; i_loop_target < mpoly_target->totloop; i_loop_target++, mloop_target++) {
87                 if (mloop_target->v == vert_source) {
88                         break;
89                 }
90         }
91
92         /* If same vertex not found, then polys cannot be equal */
93         if (i_loop_target >= mpoly_target->totloop) {
94                 return false;
95         }
96
97         /* Now mloop_source and m_loop_target have one identical vertex */
98         /* mloop_source is at position 0, while m_loop_target has advanced to find identical vertex */
99         /* Go around the loop and check that all vertices match in same order */
100         /* Skipping source loops when consecutive source vertices are mapped to same target vertex */
101
102         i_loop_target_start = i_loop_target;
103         i_loop_target_offset = 0;
104         first_vert_source = vert_source;
105
106         compare_completed = false;
107         same_loops = false;
108
109         while (!compare_completed) {
110
111                 vert_target = mloop_target->v;
112
113                 /* First advance i_loop_source, until it points to different vertex, after mapping applied */
114                 do {
115                         i_loop_source++;
116
117                         if (i_loop_source == mpoly_source->totloop) {
118                                 /* End of loops for source, must match end of loop for target.  */
119                                 if (i_loop_target_offset == mpoly_target->totloop - 1) {
120                                         compare_completed = true;
121                                         same_loops = true;
122                                         break;  /* Polys are identical */
123                                 }
124                                 else {
125                                         compare_completed = true;
126                                         same_loops = false;
127                                         break;  /* Polys are different */
128                                 }
129                         }
130
131                         mloop_source++;
132                         vert_source = mloop_source->v;
133
134                         if (vtargetmap[vert_source] != -1) {
135                                 vert_source = vtargetmap[vert_source];
136                         }
137                         else {
138                                 /* All source loop vertices should be mapped */
139                                 BLI_assert(false);
140                         }
141
142                 } while (vert_source == vert_target);
143
144                 if (compare_completed) {
145                         break;
146                 }
147
148                 /* Now advance i_loop_target as well */
149                 i_loop_target_offset++;
150
151                 if (i_loop_target_offset == mpoly_target->totloop) {
152                         /* End of loops for target only, that means no match */
153                         /* except if all remaining source vertices are mapped to first target */
154                         for (; i_loop_source < mpoly_source->totloop; i_loop_source++, mloop_source++) {
155                                 vert_source = vtargetmap[mloop_source->v];
156                                 if (vert_source != first_vert_source) {
157                                         compare_completed = true;
158                                         same_loops = false;
159                                         break;
160                                 }
161                         }
162                         if (!compare_completed) {
163                                 same_loops = true;
164                         }
165                         break;
166                 }
167
168                 /* Adjust i_loop_target for cycling around and for direct/reverse order defined by delta = +1 or -1 */
169                 i_loop_target_adjusted = (i_loop_target_start + direct_reverse * i_loop_target_offset) % mpoly_target->totloop;
170                 if (i_loop_target_adjusted < 0) {
171                         i_loop_target_adjusted += mpoly_target->totloop;
172                 }
173                 mloop_target = mloop_array + mpoly_target->loopstart + i_loop_target_adjusted;
174                 vert_target = mloop_target->v;
175
176                 if (vert_target != vert_source) {
177                         same_loops = false;  /* Polys are different */
178                         break;
179                 }
180         }
181         return same_loops;
182 }
183
184
185 /* Utility stuff for using GHash with polys, used by vertex merging. */
186
187 typedef struct PolyKey {
188         int poly_index;   /* index of the MPoly within the derived mesh */
189         int totloops;     /* number of loops in the poly */
190         unsigned int hash_sum;  /* Sum of all vertices indices */
191         unsigned int hash_xor;  /* Xor of all vertices indices */
192 } PolyKey;
193
194
195 static unsigned int poly_gset_hash_fn(const void *key)
196 {
197         const PolyKey *pk = key;
198         return pk->hash_sum;
199 }
200
201 static bool poly_gset_compare_fn(const void *k1, const void *k2)
202 {
203         const PolyKey *pk1 = k1;
204         const PolyKey *pk2 = k2;
205         if ((pk1->hash_sum == pk2->hash_sum) &&
206             (pk1->hash_xor == pk2->hash_xor) &&
207             (pk1->totloops == pk2->totloops))
208         {
209                 /* Equality - note that this does not mean equality of polys */
210                 return false;
211         }
212         else {
213                 return true;
214         }
215 }
216
217 /**
218  * Merge Verts
219  *
220  * This frees the given mesh and returns a new mesh.
221  *
222  * \param vtargetmap  The table that maps vertices to target vertices.  a value of -1
223  * indicates a vertex is a target, and is to be kept.
224  * This array is aligned with 'mesh->totvert'
225  * \warning \a vtargetmap must **not** contain any chained mapping (v1 -> v2 -> v3 etc.), this is not supported
226  * and will likely generate corrupted geometry.
227  *
228  * \param tot_vtargetmap  The number of non '-1' values in vtargetmap. (not the size)
229  *
230  * \param merge_mode enum with two modes.
231  * - #MESH_MERGE_VERTS_DUMP_IF_MAPPED
232  * When called by the Mirror Modifier,
233  * In this mode it skips any faces that have all vertices merged (to avoid creating pairs
234  * of faces sharing the same set of vertices)
235  * - #MESH_MERGE_VERTS_DUMP_IF_EQUAL
236  * When called by the Array Modifier,
237  * In this mode, faces where all vertices are merged are double-checked,
238  * to see whether all target vertices actually make up a poly already.
239  * Indeed it could be that all of a poly's vertices are merged,
240  * but merged to vertices that do not make up a single poly,
241  * in which case the original poly should not be dumped.
242  * Actually this later behavior could apply to the Mirror Modifier as well, but the additional checks are
243  * costly and not necessary in the case of mirror, because each vertex is only merged to its own mirror.
244  *
245  * \note #BKE_mesh_recalc_tessellation has to run on the returned DM if you want to access tessfaces.
246  */
247 Mesh *BKE_mesh_merge_verts(Mesh *mesh, const int *vtargetmap, const int tot_vtargetmap, const int merge_mode)
248 {
249         /* This was commented out back in 2013, see commit f45d8827bafe6b9eaf9de42f4054e9d84a21955d. */
250 // #define USE_LOOPS
251
252         Mesh *result = NULL;
253
254         const int totvert = mesh->totvert;
255         const int totedge = mesh->totedge;
256         const int totloop = mesh->totloop;
257         const int totpoly = mesh->totpoly;
258
259         const int totvert_final = totvert - tot_vtargetmap;
260
261         MVert *mv, *mvert = MEM_malloc_arrayN(totvert_final, sizeof(*mvert), __func__);
262         int *oldv         = MEM_malloc_arrayN(totvert_final, sizeof(*oldv), __func__);
263         int *newv         = MEM_malloc_arrayN(totvert, sizeof(*newv), __func__);
264         STACK_DECLARE(mvert);
265         STACK_DECLARE(oldv);
266
267         /* Note: create (totedge + totloop) elements because partially invalid polys due to merge may require
268          * generating new edges, and while in 99% cases we'll still end with less final edges than totedge,
269          * cases can be forged that would end requiring more... */
270         MEdge *med, *medge = MEM_malloc_arrayN((totedge + totloop), sizeof(*medge), __func__);
271         int *olde          = MEM_malloc_arrayN((totedge + totloop), sizeof(*olde), __func__);
272         int *newe          = MEM_malloc_arrayN((totedge + totloop), sizeof(*newe), __func__);
273         STACK_DECLARE(medge);
274         STACK_DECLARE(olde);
275
276         MLoop *ml, *mloop = MEM_malloc_arrayN(totloop, sizeof(*mloop), __func__);
277         int *oldl         = MEM_malloc_arrayN(totloop, sizeof(*oldl), __func__);
278 #ifdef USE_LOOPS
279         int *newl          = MEM_malloc_arrayN(totloop, sizeof(*newl), __func__);
280 #endif
281         STACK_DECLARE(mloop);
282         STACK_DECLARE(oldl);
283
284         MPoly *mp, *mpoly = MEM_malloc_arrayN(totpoly, sizeof(*medge), __func__);
285         int *oldp         = MEM_malloc_arrayN(totpoly, sizeof(*oldp), __func__);
286         STACK_DECLARE(mpoly);
287         STACK_DECLARE(oldp);
288
289         EdgeHash *ehash = BLI_edgehash_new_ex(__func__, totedge);
290
291         int i, j, c;
292
293         PolyKey *poly_keys;
294         GSet *poly_gset = NULL;
295         MeshElemMap *poly_map = NULL;
296         int *poly_map_mem = NULL;
297
298         STACK_INIT(oldv, totvert_final);
299         STACK_INIT(olde, totedge);
300         STACK_INIT(oldl, totloop);
301         STACK_INIT(oldp, totpoly);
302
303         STACK_INIT(mvert, totvert_final);
304         STACK_INIT(medge, totedge);
305         STACK_INIT(mloop, totloop);
306         STACK_INIT(mpoly, totpoly);
307
308         /* fill newv with destination vertex indices */
309         mv = mesh->mvert;
310         c = 0;
311         for (i = 0; i < totvert; i++, mv++) {
312                 if (vtargetmap[i] == -1) {
313                         STACK_PUSH(oldv, i);
314                         STACK_PUSH(mvert, *mv);
315                         newv[i] = c++;
316                 }
317                 else {
318                         /* dummy value */
319                         newv[i] = 0;
320                 }
321         }
322
323         /* now link target vertices to destination indices */
324         for (i = 0; i < totvert; i++) {
325                 if (vtargetmap[i] != -1) {
326                         newv[i] = newv[vtargetmap[i]];
327                 }
328         }
329
330         /* Don't remap vertices in cddm->mloop, because we need to know the original
331          * indices in order to skip faces with all vertices merged.
332          * The "update loop indices..." section further down remaps vertices in mloop.
333          */
334
335         /* now go through and fix edges and faces */
336         med = mesh->medge;
337         c = 0;
338         for (i = 0; i < totedge; i++, med++) {
339                 const unsigned int v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;
340                 const unsigned int v2 = (vtargetmap[med->v2] != -1) ? vtargetmap[med->v2] : med->v2;
341                 if (LIKELY(v1 != v2)) {
342                         void **val_p;
343
344                         if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {
345                                 newe[i] = GET_INT_FROM_POINTER(*val_p);
346                         }
347                         else {
348                                 STACK_PUSH(olde, i);
349                                 STACK_PUSH(medge, *med);
350                                 newe[i] = c;
351                                 *val_p = SET_INT_IN_POINTER(c);
352                                 c++;
353                         }
354                 }
355                 else {
356                         newe[i] = -1;
357                 }
358         }
359
360         if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_EQUAL) {
361                 /* In this mode, we need to determine,  whenever a poly' vertices are all mapped */
362                 /* if the targets already make up a poly, in which case the new poly is dropped */
363                 /* This poly equality check is rather complex.   We use a BLI_ghash to speed it up with a first level check */
364                 PolyKey *mpgh;
365                 poly_keys = MEM_malloc_arrayN(totpoly, sizeof(PolyKey), __func__);
366                 poly_gset = BLI_gset_new_ex(poly_gset_hash_fn, poly_gset_compare_fn, __func__, totpoly);
367                 /* Duplicates allowed because our compare function is not pure equality */
368                 BLI_gset_flag_set(poly_gset, GHASH_FLAG_ALLOW_DUPES);
369
370                 mp = mesh->mpoly;
371                 mpgh = poly_keys;
372                 for (i = 0; i < totpoly; i++, mp++, mpgh++) {
373                         mpgh->poly_index = i;
374                         mpgh->totloops = mp->totloop;
375                         ml = mesh->mloop + mp->loopstart;
376                         mpgh->hash_sum = mpgh->hash_xor = 0;
377                         for (j = 0; j < mp->totloop; j++, ml++) {
378                                 mpgh->hash_sum += ml->v;
379                                 mpgh->hash_xor ^= ml->v;
380                         }
381                         BLI_gset_insert(poly_gset, mpgh);
382                 }
383
384                 /* Can we optimise by reusing an old pmap ?  How do we know an old pmap is stale ?  */
385                 /* When called by MOD_array.c, the cddm has just been created, so it has no valid pmap.   */
386                 BKE_mesh_vert_poly_map_create(&poly_map, &poly_map_mem,
387                                               mesh->mpoly, mesh->mloop,
388                                               totvert, totpoly, totloop);
389         }  /* done preparing for fast poly compare */
390
391
392         mp = mesh->mpoly;
393         mv = mesh->mvert;
394         for (i = 0; i < totpoly; i++, mp++) {
395                 MPoly *mp_new;
396
397                 ml = mesh->mloop + mp->loopstart;
398
399                 /* check faces with all vertices merged */
400                 bool all_vertices_merged = true;
401
402                 for (j = 0; j < mp->totloop; j++, ml++) {
403                         if (vtargetmap[ml->v] == -1) {
404                                 all_vertices_merged = false;
405                                 /* This will be used to check for poly using several time the same vert. */
406                                 mv[ml->v].flag &= ~ME_VERT_TMP_TAG;
407                         }
408                         else {
409                                 /* This will be used to check for poly using several time the same vert. */
410                                 mv[vtargetmap[ml->v]].flag &= ~ME_VERT_TMP_TAG;
411                         }
412                 }
413
414                 if (UNLIKELY(all_vertices_merged)) {
415                         if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_MAPPED) {
416                                 /* In this mode, all vertices merged is enough to dump face */
417                                 continue;
418                         }
419                         else if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_EQUAL) {
420                                 /* Additional condition for face dump:  target vertices must make up an identical face */
421                                 /* The test has 2 steps:  (1) first step is fast ghash lookup, but not failproof       */
422                                 /*                        (2) second step is thorough but more costly poly compare     */
423                                 int i_poly, v_target;
424                                 bool found = false;
425                                 PolyKey pkey;
426
427                                 /* Use poly_gset for fast (although not 100% certain) identification of same poly */
428                                 /* First, make up a poly_summary structure */
429                                 ml = mesh->mloop + mp->loopstart;
430                                 pkey.hash_sum = pkey.hash_xor = 0;
431                                 pkey.totloops = 0;
432                                 for (j = 0; j < mp->totloop; j++, ml++) {
433                                         v_target = vtargetmap[ml->v];   /* Cannot be -1, they are all mapped */
434                                         pkey.hash_sum += v_target;
435                                         pkey.hash_xor ^= v_target;
436                                         pkey.totloops++;
437                                 }
438                                 if (BLI_gset_haskey(poly_gset, &pkey)) {
439
440                                         /* There might be a poly that matches this one.
441                                          * We could just leave it there and say there is, and do a "continue".
442                                          * ... but we are checking whether there is an exact poly match.
443                                          * It's not so costly in terms of CPU since it's very rare, just a lot of complex code.
444                                          */
445
446                                         /* Consider current loop again */
447                                         ml = mesh->mloop + mp->loopstart;
448                                         /* Consider the target of the loop's first vert */
449                                         v_target = vtargetmap[ml->v];
450                                         /* Now see if v_target belongs to a poly that shares all vertices with source poly,
451                                          * in same order, or reverse order */
452
453                                         for (i_poly = 0; i_poly < poly_map[v_target].count; i_poly++) {
454                                                 MPoly *target_poly = mesh->mpoly + *(poly_map[v_target].indices + i_poly);
455
456                                                 if (cddm_poly_compare(mesh->mloop, mp, target_poly, vtargetmap, +1) ||
457                                                     cddm_poly_compare(mesh->mloop, mp, target_poly, vtargetmap, -1))
458                                                 {
459                                                         found = true;
460                                                         break;
461                                                 }
462                                         }
463                                         if (found) {
464                                                 /* Current poly's vertices are mapped to a poly that is strictly identical */
465                                                 /* Current poly is dumped */
466                                                 continue;
467                                         }
468                                 }
469                         }
470                 }
471
472
473                 /* Here either the poly's vertices were not all merged
474                  * or they were all merged, but targets do not make up an identical poly,
475                  * the poly is retained.
476                  */
477                 ml = mesh->mloop + mp->loopstart;
478
479                 c = 0;
480                 MLoop *last_valid_ml = NULL;
481                 MLoop *first_valid_ml = NULL;
482                 bool need_edge_from_last_valid_ml = false;
483                 bool need_edge_to_first_valid_ml = false;
484                 int created_edges = 0;
485                 for (j = 0; j < mp->totloop; j++, ml++) {
486                         const uint mlv = (vtargetmap[ml->v] != -1) ? vtargetmap[ml->v] : ml->v;
487 #ifndef NDEBUG
488                         {
489                                 MLoop *next_ml = mesh->mloop + mp->loopstart + ((j + 1) % mp->totloop);
490                                 uint next_mlv = (vtargetmap[next_ml->v] != -1) ? vtargetmap[next_ml->v] : next_ml->v;
491                                 med = mesh->medge + ml->e;
492                                 uint v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;
493                                 uint v2 = (vtargetmap[med->v2] != -1) ? vtargetmap[med->v2] : med->v2;
494                                 BLI_assert((mlv == v1 && next_mlv == v2) || (mlv == v2 && next_mlv == v1));
495                         }
496 #endif
497                         /* A loop is only valid if its matching edge is, and it's not reusing a vertex already used by this poly. */
498                         if (LIKELY((newe[ml->e] != -1) && ((mv[mlv].flag & ME_VERT_TMP_TAG) == 0))) {
499                                 mv[mlv].flag |= ME_VERT_TMP_TAG;
500
501                                 if (UNLIKELY(last_valid_ml != NULL && need_edge_from_last_valid_ml)) {
502                                         /* We need to create a new edge between last valid loop and this one! */
503                                         void **val_p;
504
505                                         uint v1 = (vtargetmap[last_valid_ml->v] != -1) ? vtargetmap[last_valid_ml->v] : last_valid_ml->v;
506                                         uint v2 = mlv;
507                                         BLI_assert(v1 != v2);
508                                         if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {
509                                                 last_valid_ml->e = GET_INT_FROM_POINTER(*val_p);
510                                         }
511                                         else {
512                                                 const int new_eidx = STACK_SIZE(medge);
513                                                 STACK_PUSH(olde, olde[last_valid_ml->e]);
514                                                 STACK_PUSH(medge, mesh->medge[last_valid_ml->e]);
515                                                 medge[new_eidx].v1 = last_valid_ml->v;
516                                                 medge[new_eidx].v2 = ml->v;
517                                                 /* DO NOT change newe mapping, could break actual values due to some deleted original edges. */
518                                                 *val_p = SET_INT_IN_POINTER(new_eidx);
519                                                 created_edges++;
520
521                                                 last_valid_ml->e = new_eidx;
522                                         }
523                                         need_edge_from_last_valid_ml = false;
524                                 }
525
526 #ifdef USE_LOOPS
527                                 newl[j + mp->loopstart] = STACK_SIZE(mloop);
528 #endif
529                                 STACK_PUSH(oldl, j + mp->loopstart);
530                                 last_valid_ml = STACK_PUSH_RET_PTR(mloop);
531                                 *last_valid_ml = *ml;
532                                 if (first_valid_ml == NULL) {
533                                         first_valid_ml = last_valid_ml;
534                                 }
535                                 c++;
536
537                                 /* We absolutely HAVE to handle edge index remapping here, otherwise potential newly created edges
538                                  * in that part of code make remapping later totally unreliable. */
539                                 BLI_assert(newe[ml->e] != -1);
540                                 last_valid_ml->e = newe[ml->e];
541                         }
542                         else {
543                                 if (last_valid_ml != NULL) {
544                                         need_edge_from_last_valid_ml = true;
545                                 }
546                                 else {
547                                         need_edge_to_first_valid_ml = true;
548                                 }
549                         }
550                 }
551                 if (UNLIKELY(last_valid_ml != NULL && !ELEM(first_valid_ml, NULL, last_valid_ml) &&
552                              (need_edge_to_first_valid_ml || need_edge_from_last_valid_ml)))
553                 {
554                         /* We need to create a new edge between last valid loop and first valid one! */
555                         void **val_p;
556
557                         uint v1 = (vtargetmap[last_valid_ml->v] != -1) ? vtargetmap[last_valid_ml->v] : last_valid_ml->v;
558                         uint v2 = (vtargetmap[first_valid_ml->v] != -1) ? vtargetmap[first_valid_ml->v] : first_valid_ml->v;
559                         BLI_assert(v1 != v2);
560                         if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {
561                                 last_valid_ml->e = GET_INT_FROM_POINTER(*val_p);
562                         }
563                         else {
564                                 const int new_eidx = STACK_SIZE(medge);
565                                 STACK_PUSH(olde, olde[last_valid_ml->e]);
566                                 STACK_PUSH(medge, mesh->medge[last_valid_ml->e]);
567                                 medge[new_eidx].v1 = last_valid_ml->v;
568                                 medge[new_eidx].v2 = first_valid_ml->v;
569                                 /* DO NOT change newe mapping, could break actual values due to some deleted original edges. */
570                                 *val_p = SET_INT_IN_POINTER(new_eidx);
571                                 created_edges++;
572
573                                 last_valid_ml->e = new_eidx;
574                         }
575                         need_edge_to_first_valid_ml = need_edge_from_last_valid_ml = false;
576                 }
577
578                 if (UNLIKELY(c == 0)) {
579                         BLI_assert(created_edges == 0);
580                         continue;
581                 }
582                 else if (UNLIKELY(c < 3)) {
583                         STACK_DISCARD(oldl, c);
584                         STACK_DISCARD(mloop, c);
585                         if (created_edges > 0) {
586                                 for (j = STACK_SIZE(medge) - created_edges; j < STACK_SIZE(medge); j++) {
587                                         BLI_edgehash_remove(ehash, medge[j].v1, medge[j].v2, NULL);
588                                 }
589                                 STACK_DISCARD(olde, created_edges);
590                                 STACK_DISCARD(medge, created_edges);
591                         }
592                         continue;
593                 }
594
595                 mp_new = STACK_PUSH_RET_PTR(mpoly);
596                 *mp_new = *mp;
597                 mp_new->totloop = c;
598                 BLI_assert(mp_new->totloop >= 3);
599                 mp_new->loopstart = STACK_SIZE(mloop) - c;
600
601                 STACK_PUSH(oldp, i);
602         }  /* end of the loop that tests polys   */
603
604
605         if (poly_gset) {
606                 // printf("hash quality %.6f\n", BLI_gset_calc_quality(poly_gset));
607
608                 BLI_gset_free(poly_gset, NULL);
609                 MEM_freeN(poly_keys);
610         }
611
612         /*create new cddm*/
613         result = BKE_mesh_new_nomain_from_template(
614                 mesh, STACK_SIZE(mvert), STACK_SIZE(medge), 0, STACK_SIZE(mloop), STACK_SIZE(mpoly));
615
616         /*update edge indices and copy customdata*/
617         med = medge;
618         for (i = 0; i < result->totedge; i++, med++) {
619                 BLI_assert(newv[med->v1] != -1);
620                 med->v1 = newv[med->v1];
621                 BLI_assert(newv[med->v2] != -1);
622                 med->v2 = newv[med->v2];
623
624                 /* Can happen in case vtargetmap contains some double chains, we do not support that. */
625                 BLI_assert(med->v1 != med->v2);
626
627                 CustomData_copy_data(&mesh->edata, &result->edata, olde[i], i, 1);
628         }
629
630         /*update loop indices and copy customdata*/
631         ml = mloop;
632         for (i = 0; i < result->totloop; i++, ml++) {
633                 /* Edge remapping has already be done in main loop handling part above. */
634                 BLI_assert(newv[ml->v] != -1);
635                 ml->v = newv[ml->v];
636
637                 CustomData_copy_data(&mesh->ldata, &result->ldata, oldl[i], i, 1);
638         }
639
640         /*copy vertex customdata*/
641         mv = mvert;
642         for (i = 0; i < result->totvert; i++, mv++) {
643                 CustomData_copy_data(&mesh->vdata, &result->vdata, oldv[i], i, 1);
644         }
645
646         /*copy poly customdata*/
647         mp = mpoly;
648         for (i = 0; i < result->totpoly; i++, mp++) {
649                 CustomData_copy_data(&mesh->pdata, &result->pdata, oldp[i], i, 1);
650         }
651
652         /*copy over data.  CustomData_add_layer can do this, need to look it up.*/
653         memcpy(result->mvert, mvert, sizeof(MVert) * STACK_SIZE(mvert));
654         memcpy(result->medge, medge, sizeof(MEdge) * STACK_SIZE(medge));
655         memcpy(result->mloop, mloop, sizeof(MLoop) * STACK_SIZE(mloop));
656         memcpy(result->mpoly, mpoly, sizeof(MPoly) * STACK_SIZE(mpoly));
657
658         MEM_freeN(mvert);
659         MEM_freeN(medge);
660         MEM_freeN(mloop);
661         MEM_freeN(mpoly);
662
663         MEM_freeN(newv);
664         MEM_freeN(newe);
665 #ifdef USE_LOOPS
666         MEM_freeN(newl);
667 #endif
668
669         MEM_freeN(oldv);
670         MEM_freeN(olde);
671         MEM_freeN(oldl);
672         MEM_freeN(oldp);
673
674         BLI_edgehash_free(ehash, NULL);
675
676         if (poly_map != NULL)
677                 MEM_freeN(poly_map);
678         if (poly_map_mem != NULL)
679                 MEM_freeN(poly_map_mem);
680
681         BKE_id_free(NULL, mesh);
682
683         return result;
684 }