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