Blender  V3.3
mesh_merge.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later
2  * Copyright 2001-2002 NaN Holding BV. All rights reserved. */
3 
7 #include <string.h> /* for memcpy */
8 
9 #include "MEM_guardedalloc.h"
10 
11 #include "DNA_mesh_types.h"
12 #include "DNA_meshdata_types.h"
13 
14 #include "BLI_bitmap.h"
15 #include "BLI_edgehash.h"
16 #include "BLI_ghash.h"
17 #include "BLI_utildefines.h"
18 #include "BLI_utildefines_stack.h"
19 
20 #include "BKE_customdata.h"
21 #include "BKE_lib_id.h"
22 #include "BKE_mesh.h"
23 #include "BKE_mesh_mapping.h"
24 
35 static int cddm_poly_compare(MLoop *mloop_array,
36  MPoly *mpoly_source,
37  MPoly *mpoly_target,
38  const int *vtargetmap,
39  const int direct_reverse)
40 {
41  int vert_source, first_vert_source, vert_target;
42  int i_loop_source;
43  int i_loop_target, i_loop_target_start, i_loop_target_offset, i_loop_target_adjusted;
44  bool compare_completed = false;
45  bool same_loops = false;
46 
47  MLoop *mloop_source, *mloop_target;
48 
49  BLI_assert(ELEM(direct_reverse, 1, -1));
50 
51  i_loop_source = 0;
52  mloop_source = mloop_array + mpoly_source->loopstart;
53  vert_source = mloop_source->v;
54 
55  if (vtargetmap[vert_source] != -1) {
56  vert_source = vtargetmap[vert_source];
57  }
58  else {
59  /* All source loop vertices should be mapped */
60  BLI_assert(false);
61  }
62 
63  /* Find same vertex within mpoly_target's loops */
64  mloop_target = mloop_array + mpoly_target->loopstart;
65  for (i_loop_target = 0; i_loop_target < mpoly_target->totloop; i_loop_target++, mloop_target++) {
66  if (mloop_target->v == vert_source) {
67  break;
68  }
69  }
70 
71  /* If same vertex not found, then polys cannot be equal */
72  if (i_loop_target >= mpoly_target->totloop) {
73  return false;
74  }
75 
76  /* Now mloop_source and m_loop_target have one identical vertex */
77  /* mloop_source is at position 0, while m_loop_target has advanced to find identical vertex */
78  /* Go around the loop and check that all vertices match in same order */
79  /* Skipping source loops when consecutive source vertices are mapped to same target vertex */
80 
81  i_loop_target_start = i_loop_target;
82  i_loop_target_offset = 0;
83  first_vert_source = vert_source;
84 
85  compare_completed = false;
86  same_loops = false;
87 
88  while (!compare_completed) {
89 
90  vert_target = mloop_target->v;
91 
92  /* First advance i_loop_source, until it points to different vertex, after mapping applied */
93  do {
94  i_loop_source++;
95 
96  if (i_loop_source == mpoly_source->totloop) {
97  /* End of loops for source, must match end of loop for target. */
98  if (i_loop_target_offset == mpoly_target->totloop - 1) {
99  compare_completed = true;
100  same_loops = true;
101  break; /* Polys are identical */
102  }
103 
104  compare_completed = true;
105  same_loops = false;
106  break; /* Polys are different */
107  }
108 
109  mloop_source++;
110  vert_source = mloop_source->v;
111 
112  if (vtargetmap[vert_source] != -1) {
113  vert_source = vtargetmap[vert_source];
114  }
115  else {
116  /* All source loop vertices should be mapped */
117  BLI_assert(false);
118  }
119 
120  } while (vert_source == vert_target);
121 
122  if (compare_completed) {
123  break;
124  }
125 
126  /* Now advance i_loop_target as well */
127  i_loop_target_offset++;
128 
129  if (i_loop_target_offset == mpoly_target->totloop) {
130  /* End of loops for target only, that means no match */
131  /* except if all remaining source vertices are mapped to first target */
132  for (; i_loop_source < mpoly_source->totloop; i_loop_source++, mloop_source++) {
133  vert_source = vtargetmap[mloop_source->v];
134  if (vert_source != first_vert_source) {
135  compare_completed = true;
136  same_loops = false;
137  break;
138  }
139  }
140  if (!compare_completed) {
141  same_loops = true;
142  }
143  break;
144  }
145 
146  /* Adjust i_loop_target for cycling around and for direct/reverse order
147  * defined by delta = +1 or -1 */
148  i_loop_target_adjusted = (i_loop_target_start + direct_reverse * i_loop_target_offset) %
149  mpoly_target->totloop;
150  if (i_loop_target_adjusted < 0) {
151  i_loop_target_adjusted += mpoly_target->totloop;
152  }
153  mloop_target = mloop_array + mpoly_target->loopstart + i_loop_target_adjusted;
154  vert_target = mloop_target->v;
155 
156  if (vert_target != vert_source) {
157  same_loops = false; /* Polys are different */
158  break;
159  }
160  }
161  return same_loops;
162 }
163 
164 /* Utility stuff for using GHash with polys, used by vertex merging. */
165 
166 typedef struct PolyKey {
167  int poly_index; /* index of the MPoly within the derived mesh */
168  int totloops; /* number of loops in the poly */
169  uint hash_sum; /* Sum of all vertices indices */
170  uint hash_xor; /* Xor of all vertices indices */
172 
173 static uint poly_gset_hash_fn(const void *key)
174 {
175  const PolyKey *pk = key;
176  return pk->hash_sum;
177 }
178 
179 static bool poly_gset_compare_fn(const void *k1, const void *k2)
180 {
181  const PolyKey *pk1 = k1;
182  const PolyKey *pk2 = k2;
183  if ((pk1->hash_sum == pk2->hash_sum) && (pk1->hash_xor == pk2->hash_xor) &&
184  (pk1->totloops == pk2->totloops)) {
185  /* Equality - note that this does not mean equality of polys */
186  return false;
187  }
188 
189  return true;
190 }
191 
193  const int *vtargetmap,
194  const int tot_vtargetmap,
195  const int merge_mode)
196 {
197  /* This was commented out back in 2013, see commit f45d8827bafe6b9eaf9de42f4054e9d84a21955d. */
198  // #define USE_LOOPS
199 
200  Mesh *result = NULL;
201 
202  const int totvert = mesh->totvert;
203  const int totedge = mesh->totedge;
204  const int totloop = mesh->totloop;
205  const int totpoly = mesh->totpoly;
206 
207  const int totvert_final = totvert - tot_vtargetmap;
208 
209  MVert *mv, *mvert = MEM_malloc_arrayN(totvert_final, sizeof(*mvert), __func__);
210  int *oldv = MEM_malloc_arrayN(totvert_final, sizeof(*oldv), __func__);
211  int *newv = MEM_malloc_arrayN(totvert, sizeof(*newv), __func__);
212  STACK_DECLARE(mvert);
213  STACK_DECLARE(oldv);
214 
215  /* NOTE: create (totedge + totloop) elements because partially invalid polys due to merge may
216  * require generating new edges, and while in 99% cases we'll still end with less final edges
217  * than totedge, cases can be forged that would end requiring more. */
218  MEdge *med, *medge = MEM_malloc_arrayN((totedge + totloop), sizeof(*medge), __func__);
219  int *olde = MEM_malloc_arrayN((totedge + totloop), sizeof(*olde), __func__);
220  int *newe = MEM_malloc_arrayN((totedge + totloop), sizeof(*newe), __func__);
221  STACK_DECLARE(medge);
222  STACK_DECLARE(olde);
223 
224  MLoop *ml, *mloop = MEM_malloc_arrayN(totloop, sizeof(*mloop), __func__);
225  int *oldl = MEM_malloc_arrayN(totloop, sizeof(*oldl), __func__);
226 #ifdef USE_LOOPS
227  int *newl = MEM_malloc_arrayN(totloop, sizeof(*newl), __func__);
228 #endif
229  STACK_DECLARE(mloop);
230  STACK_DECLARE(oldl);
231 
232  MPoly *mp, *mpoly = MEM_malloc_arrayN(totpoly, sizeof(*medge), __func__);
233  int *oldp = MEM_malloc_arrayN(totpoly, sizeof(*oldp), __func__);
234  STACK_DECLARE(mpoly);
235  STACK_DECLARE(oldp);
236 
237  EdgeHash *ehash = BLI_edgehash_new_ex(__func__, totedge);
238 
239  int i, j, c;
240 
241  PolyKey *poly_keys;
242  GSet *poly_gset = NULL;
243  MeshElemMap *poly_map = NULL;
244  int *poly_map_mem = NULL;
245 
246  STACK_INIT(oldv, totvert_final);
247  STACK_INIT(olde, totedge);
248  STACK_INIT(oldl, totloop);
249  STACK_INIT(oldp, totpoly);
250 
251  STACK_INIT(mvert, totvert_final);
252  STACK_INIT(medge, totedge);
253  STACK_INIT(mloop, totloop);
254  STACK_INIT(mpoly, totpoly);
255 
256  /* fill newv with destination vertex indices */
257  mv = mesh->mvert;
258  c = 0;
259  for (i = 0; i < totvert; i++, mv++) {
260  if (vtargetmap[i] == -1) {
261  STACK_PUSH(oldv, i);
262  STACK_PUSH(mvert, *mv);
263  newv[i] = c++;
264  }
265  else {
266  /* dummy value */
267  newv[i] = 0;
268  }
269  }
270 
271  /* now link target vertices to destination indices */
272  for (i = 0; i < totvert; i++) {
273  if (vtargetmap[i] != -1) {
274  newv[i] = newv[vtargetmap[i]];
275  }
276  }
277 
278  /* Don't remap vertices in cddm->mloop, because we need to know the original
279  * indices in order to skip faces with all vertices merged.
280  * The "update loop indices..." section further down remaps vertices in mloop.
281  */
282 
283  /* now go through and fix edges and faces */
284  med = mesh->medge;
285  c = 0;
286  for (i = 0; i < totedge; i++, med++) {
287  const uint v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;
288  const uint v2 = (vtargetmap[med->v2] != -1) ? vtargetmap[med->v2] : med->v2;
289  if (LIKELY(v1 != v2)) {
290  void **val_p;
291 
292  if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {
293  newe[i] = POINTER_AS_INT(*val_p);
294  }
295  else {
296  STACK_PUSH(olde, i);
297  STACK_PUSH(medge, *med);
298  newe[i] = c;
299  *val_p = POINTER_FROM_INT(c);
300  c++;
301  }
302  }
303  else {
304  newe[i] = -1;
305  }
306  }
307 
308  if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_EQUAL) {
309  /* In this mode, we need to determine, whenever a poly' vertices are all mapped */
310  /* if the targets already make up a poly, in which case the new poly is dropped */
311  /* This poly equality check is rather complex.
312  * We use a BLI_ghash to speed it up with a first level check */
313  PolyKey *mpgh;
314  poly_keys = MEM_malloc_arrayN(totpoly, sizeof(PolyKey), __func__);
315  poly_gset = BLI_gset_new_ex(poly_gset_hash_fn, poly_gset_compare_fn, __func__, totpoly);
316  /* Duplicates allowed because our compare function is not pure equality */
318 
319  mp = mesh->mpoly;
320  mpgh = poly_keys;
321  for (i = 0; i < totpoly; i++, mp++, mpgh++) {
322  mpgh->poly_index = i;
323  mpgh->totloops = mp->totloop;
324  ml = mesh->mloop + mp->loopstart;
325  mpgh->hash_sum = mpgh->hash_xor = 0;
326  for (j = 0; j < mp->totloop; j++, ml++) {
327  mpgh->hash_sum += ml->v;
328  mpgh->hash_xor ^= ml->v;
329  }
330  BLI_gset_insert(poly_gset, mpgh);
331  }
332 
333  /* Can we optimize by reusing an old `pmap`? How do we know an old `pmap` is stale? */
334  /* When called by `MOD_array.c` the `cddm` has just been created, so it has no valid `pmap`. */
336  &poly_map, &poly_map_mem, mesh->mpoly, mesh->mloop, totvert, totpoly, totloop);
337  } /* done preparing for fast poly compare */
338 
339  BLI_bitmap *vert_tag = BLI_BITMAP_NEW(mesh->totvert, __func__);
340 
341  mp = mesh->mpoly;
342  mv = mesh->mvert;
343  for (i = 0; i < totpoly; i++, mp++) {
344  MPoly *mp_new;
345 
346  ml = mesh->mloop + mp->loopstart;
347 
348  /* check faces with all vertices merged */
349  bool all_vertices_merged = true;
350 
351  for (j = 0; j < mp->totloop; j++, ml++) {
352  if (vtargetmap[ml->v] == -1) {
353  all_vertices_merged = false;
354  /* This will be used to check for poly using several time the same vert. */
355  BLI_BITMAP_DISABLE(vert_tag, ml->v);
356  }
357  else {
358  /* This will be used to check for poly using several time the same vert. */
359  BLI_BITMAP_DISABLE(vert_tag, vtargetmap[ml->v]);
360  }
361  }
362 
363  if (UNLIKELY(all_vertices_merged)) {
364  if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_MAPPED) {
365  /* In this mode, all vertices merged is enough to dump face */
366  continue;
367  }
368  if (merge_mode == MESH_MERGE_VERTS_DUMP_IF_EQUAL) {
369  /* Additional condition for face dump: target vertices must make up an identical face.
370  * The test has 2 steps:
371  * 1) first step is fast `ghash` lookup, but not fail-proof.
372  * 2) second step is thorough but more costly poly compare. */
373  int i_poly, v_target;
374  bool found = false;
375  PolyKey pkey;
376 
377  /* Use poly_gset for fast (although not 100% certain) identification of same poly */
378  /* First, make up a poly_summary structure */
379  ml = mesh->mloop + mp->loopstart;
380  pkey.hash_sum = pkey.hash_xor = 0;
381  pkey.totloops = 0;
382  for (j = 0; j < mp->totloop; j++, ml++) {
383  v_target = vtargetmap[ml->v]; /* Cannot be -1, they are all mapped */
384  pkey.hash_sum += v_target;
385  pkey.hash_xor ^= v_target;
386  pkey.totloops++;
387  }
388  if (BLI_gset_haskey(poly_gset, &pkey)) {
389 
390  /* There might be a poly that matches this one.
391  * We could just leave it there and say there is, and do a "continue".
392  * ... but we are checking whether there is an exact poly match.
393  * It's not so costly in terms of CPU since it's very rare, just a lot of complex code.
394  */
395 
396  /* Consider current loop again */
397  ml = mesh->mloop + mp->loopstart;
398  /* Consider the target of the loop's first vert */
399  v_target = vtargetmap[ml->v];
400  /* Now see if v_target belongs to a poly that shares all vertices with source poly,
401  * in same order, or reverse order */
402 
403  for (i_poly = 0; i_poly < poly_map[v_target].count; i_poly++) {
404  MPoly *target_poly = mesh->mpoly + *(poly_map[v_target].indices + i_poly);
405 
406  if (cddm_poly_compare(mesh->mloop, mp, target_poly, vtargetmap, +1) ||
407  cddm_poly_compare(mesh->mloop, mp, target_poly, vtargetmap, -1)) {
408  found = true;
409  break;
410  }
411  }
412  if (found) {
413  /* Current poly's vertices are mapped to a poly that is strictly identical */
414  /* Current poly is dumped */
415  continue;
416  }
417  }
418  }
419  }
420 
421  /* Here either the poly's vertices were not all merged
422  * or they were all merged, but targets do not make up an identical poly,
423  * the poly is retained.
424  */
425  ml = mesh->mloop + mp->loopstart;
426 
427  c = 0;
428  MLoop *last_valid_ml = NULL;
429  MLoop *first_valid_ml = NULL;
430  bool need_edge_from_last_valid_ml = false;
431  bool need_edge_to_first_valid_ml = false;
432  int created_edges = 0;
433  for (j = 0; j < mp->totloop; j++, ml++) {
434  const uint mlv = (vtargetmap[ml->v] != -1) ? vtargetmap[ml->v] : ml->v;
435 #ifndef NDEBUG
436  {
437  MLoop *next_ml = mesh->mloop + mp->loopstart + ((j + 1) % mp->totloop);
438  uint next_mlv = (vtargetmap[next_ml->v] != -1) ? vtargetmap[next_ml->v] : next_ml->v;
439  med = mesh->medge + ml->e;
440  uint v1 = (vtargetmap[med->v1] != -1) ? vtargetmap[med->v1] : med->v1;
441  uint v2 = (vtargetmap[med->v2] != -1) ? vtargetmap[med->v2] : med->v2;
442  BLI_assert((mlv == v1 && next_mlv == v2) || (mlv == v2 && next_mlv == v1));
443  }
444 #endif
445  /* A loop is only valid if its matching edge is,
446  * and it's not reusing a vertex already used by this poly. */
447  if (LIKELY((newe[ml->e] != -1) && !BLI_BITMAP_TEST(vert_tag, mlv))) {
448  BLI_BITMAP_ENABLE(vert_tag, mlv);
449 
450  if (UNLIKELY(last_valid_ml != NULL && need_edge_from_last_valid_ml)) {
451  /* We need to create a new edge between last valid loop and this one! */
452  void **val_p;
453 
454  uint v1 = (vtargetmap[last_valid_ml->v] != -1) ? vtargetmap[last_valid_ml->v] :
455  last_valid_ml->v;
456  uint v2 = mlv;
457  BLI_assert(v1 != v2);
458  if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {
459  last_valid_ml->e = POINTER_AS_INT(*val_p);
460  }
461  else {
462  const int new_eidx = STACK_SIZE(medge);
463  STACK_PUSH(olde, olde[last_valid_ml->e]);
464  STACK_PUSH(medge, mesh->medge[last_valid_ml->e]);
465  medge[new_eidx].v1 = last_valid_ml->v;
466  medge[new_eidx].v2 = ml->v;
467  /* DO NOT change newe mapping,
468  * could break actual values due to some deleted original edges. */
469  *val_p = POINTER_FROM_INT(new_eidx);
470  created_edges++;
471 
472  last_valid_ml->e = new_eidx;
473  }
474  need_edge_from_last_valid_ml = false;
475  }
476 
477 #ifdef USE_LOOPS
478  newl[j + mp->loopstart] = STACK_SIZE(mloop);
479 #endif
480  STACK_PUSH(oldl, j + mp->loopstart);
481  last_valid_ml = STACK_PUSH_RET_PTR(mloop);
482  *last_valid_ml = *ml;
483  if (first_valid_ml == NULL) {
484  first_valid_ml = last_valid_ml;
485  }
486  c++;
487 
488  /* We absolutely HAVE to handle edge index remapping here, otherwise potential newly
489  * created edges in that part of code make remapping later totally unreliable. */
490  BLI_assert(newe[ml->e] != -1);
491  last_valid_ml->e = newe[ml->e];
492  }
493  else {
494  if (last_valid_ml != NULL) {
495  need_edge_from_last_valid_ml = true;
496  }
497  else {
498  need_edge_to_first_valid_ml = true;
499  }
500  }
501  }
502  if (UNLIKELY(last_valid_ml != NULL && !ELEM(first_valid_ml, NULL, last_valid_ml) &&
503  (need_edge_to_first_valid_ml || need_edge_from_last_valid_ml))) {
504  /* We need to create a new edge between last valid loop and first valid one! */
505  void **val_p;
506 
507  uint v1 = (vtargetmap[last_valid_ml->v] != -1) ? vtargetmap[last_valid_ml->v] :
508  last_valid_ml->v;
509  uint v2 = (vtargetmap[first_valid_ml->v] != -1) ? vtargetmap[first_valid_ml->v] :
510  first_valid_ml->v;
511  BLI_assert(v1 != v2);
512  if (BLI_edgehash_ensure_p(ehash, v1, v2, &val_p)) {
513  last_valid_ml->e = POINTER_AS_INT(*val_p);
514  }
515  else {
516  const int new_eidx = STACK_SIZE(medge);
517  STACK_PUSH(olde, olde[last_valid_ml->e]);
518  STACK_PUSH(medge, mesh->medge[last_valid_ml->e]);
519  medge[new_eidx].v1 = last_valid_ml->v;
520  medge[new_eidx].v2 = first_valid_ml->v;
521  /* DO NOT change newe mapping,
522  * could break actual values due to some deleted original edges. */
523  *val_p = POINTER_FROM_INT(new_eidx);
524  created_edges++;
525 
526  last_valid_ml->e = new_eidx;
527  }
528  need_edge_to_first_valid_ml = need_edge_from_last_valid_ml = false;
529  }
530 
531  if (UNLIKELY(c == 0)) {
532  BLI_assert(created_edges == 0);
533  continue;
534  }
535  if (UNLIKELY(c < 3)) {
536  STACK_DISCARD(oldl, c);
537  STACK_DISCARD(mloop, c);
538  if (created_edges > 0) {
539  for (j = STACK_SIZE(medge) - created_edges; j < STACK_SIZE(medge); j++) {
540  BLI_edgehash_remove(ehash, medge[j].v1, medge[j].v2, NULL);
541  }
542  STACK_DISCARD(olde, created_edges);
543  STACK_DISCARD(medge, created_edges);
544  }
545  continue;
546  }
547 
548  mp_new = STACK_PUSH_RET_PTR(mpoly);
549  *mp_new = *mp;
550  mp_new->totloop = c;
551  BLI_assert(mp_new->totloop >= 3);
552  mp_new->loopstart = STACK_SIZE(mloop) - c;
553 
554  STACK_PUSH(oldp, i);
555  } /* End of the loop that tests polys. */
556 
557  if (poly_gset) {
558  // printf("hash quality %.6f\n", BLI_gset_calc_quality(poly_gset));
559 
560  BLI_gset_free(poly_gset, NULL);
561  MEM_freeN(poly_keys);
562  }
563 
564  /* Create new cddm. */
566  mesh, STACK_SIZE(mvert), STACK_SIZE(medge), 0, STACK_SIZE(mloop), STACK_SIZE(mpoly));
567 
568  /* Update edge indices and copy customdata. */
569  med = medge;
570  for (i = 0; i < result->totedge; i++, med++) {
571  BLI_assert(newv[med->v1] != -1);
572  med->v1 = newv[med->v1];
573  BLI_assert(newv[med->v2] != -1);
574  med->v2 = newv[med->v2];
575 
576  /* Can happen in case vtargetmap contains some double chains, we do not support that. */
577  BLI_assert(med->v1 != med->v2);
578 
579  CustomData_copy_data(&mesh->edata, &result->edata, olde[i], i, 1);
580  }
581 
582  /* Update loop indices and copy customdata. */
583  ml = mloop;
584  for (i = 0; i < result->totloop; i++, ml++) {
585  /* Edge remapping has already be done in main loop handling part above. */
586  BLI_assert(newv[ml->v] != -1);
587  ml->v = newv[ml->v];
588 
589  CustomData_copy_data(&mesh->ldata, &result->ldata, oldl[i], i, 1);
590  }
591 
592  /* Copy vertex customdata. */
593  mv = mvert;
594  for (i = 0; i < result->totvert; i++, mv++) {
595  CustomData_copy_data(&mesh->vdata, &result->vdata, oldv[i], i, 1);
596  }
597 
598  /* Copy poly customdata. */
599  mp = mpoly;
600  for (i = 0; i < result->totpoly; i++, mp++) {
601  CustomData_copy_data(&mesh->pdata, &result->pdata, oldp[i], i, 1);
602  }
603 
604  /* Copy over data. #CustomData_add_layer can do this, need to look it up. */
605  if (STACK_SIZE(mvert)) {
606  memcpy(result->mvert, mvert, sizeof(MVert) * STACK_SIZE(mvert));
607  }
608  if (STACK_SIZE(medge)) {
609  memcpy(result->medge, medge, sizeof(MEdge) * STACK_SIZE(medge));
610  }
611  if (STACK_SIZE(mloop)) {
612  memcpy(result->mloop, mloop, sizeof(MLoop) * STACK_SIZE(mloop));
613  }
614  if (STACK_SIZE(mpoly)) {
615  memcpy(result->mpoly, mpoly, sizeof(MPoly) * STACK_SIZE(mpoly));
616  }
617 
618  MEM_freeN(mvert);
619  MEM_freeN(medge);
620  MEM_freeN(mloop);
621  MEM_freeN(mpoly);
622 
623  MEM_freeN(newv);
624  MEM_freeN(newe);
625 #ifdef USE_LOOPS
626  MEM_freeN(newl);
627 #endif
628 
629  MEM_freeN(oldv);
630  MEM_freeN(olde);
631  MEM_freeN(oldl);
632  MEM_freeN(oldp);
633 
634  MEM_freeN(vert_tag);
635 
636  BLI_edgehash_free(ehash, NULL);
637 
638  if (poly_map != NULL) {
639  MEM_freeN(poly_map);
640  }
641  if (poly_map_mem != NULL) {
642  MEM_freeN(poly_map_mem);
643  }
644 
646 
647  return result;
648 }
CustomData interface, see also DNA_customdata_types.h.
void CustomData_copy_data(const struct CustomData *source, struct CustomData *dest, int source_index, int dest_index, int count)
void BKE_id_free(struct Main *bmain, void *idv)
@ MESH_MERGE_VERTS_DUMP_IF_EQUAL
Definition: BKE_mesh.h:819
@ MESH_MERGE_VERTS_DUMP_IF_MAPPED
Definition: BKE_mesh.h:818
struct Mesh * BKE_mesh_new_nomain_from_template(const struct Mesh *me_src, int verts_len, int edges_len, int tessface_len, int loops_len, int polys_len)
void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem, const struct MPoly *mpoly, const struct MLoop *mloop, int totvert, int totpoly, int totloop)
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_BITMAP_NEW(_num, _alloc_string)
Definition: BLI_bitmap.h:40
#define BLI_BITMAP_TEST(_bitmap, _index)
Definition: BLI_bitmap.h:64
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition: BLI_bitmap.h:81
#define BLI_BITMAP_DISABLE(_bitmap, _index)
Definition: BLI_bitmap.h:88
unsigned int BLI_bitmap
Definition: BLI_bitmap.h:16
void BLI_edgehash_free(EdgeHash *eh, EdgeHashFreeFP free_value)
Definition: edgehash.c:230
bool BLI_edgehash_ensure_p(EdgeHash *eh, unsigned int v0, unsigned int v1, void ***r_val) ATTR_WARN_UNUSED_RESULT
Definition: edgehash.c:307
bool BLI_edgehash_remove(EdgeHash *eh, unsigned int v0, unsigned int v1, EdgeHashFreeFP free_value)
Definition: edgehash.c:328
EdgeHash * BLI_edgehash_new_ex(const char *info, unsigned int nentries_reserve)
Definition: edgehash.c:212
struct GSet GSet
Definition: BLI_ghash.h:340
@ GHASH_FLAG_ALLOW_DUPES
Definition: BLI_ghash.h:55
void BLI_gset_flag_set(GSet *gs, unsigned int flag)
Definition: BLI_ghash.c:1042
bool BLI_gset_haskey(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:1007
GSet * BLI_gset_new_ex(GSetHashFP hashfp, GSetCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:939
void BLI_gset_insert(GSet *gs, void *key)
Definition: BLI_ghash.c:962
void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
Definition: BLI_ghash.c:1037
unsigned int uint
Definition: BLI_sys_types.h:67
#define POINTER_FROM_INT(i)
#define POINTER_AS_INT(i)
#define UNLIKELY(x)
#define ELEM(...)
#define LIKELY(x)
#define STACK_DISCARD(stack, n)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_PUSH_RET_PTR(stack)
#define STACK_INIT(stack, stack_num)
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Read Guarded memory(de)allocation.
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void *(* MEM_malloc_arrayN)(size_t len, size_t size, const char *str)
Definition: mallocn.c:34
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
Mesh * BKE_mesh_merge_verts(Mesh *mesh, const int *vtargetmap, const int tot_vtargetmap, const int merge_mode)
Definition: mesh_merge.c:192
struct PolyKey PolyKey
static bool poly_gset_compare_fn(const void *k1, const void *k2)
Definition: mesh_merge.c:179
static uint poly_gset_hash_fn(const void *key)
Definition: mesh_merge.c:173
static int cddm_poly_compare(MLoop *mloop_array, MPoly *mpoly_source, MPoly *mpoly_target, const int *vtargetmap, const int direct_reverse)
Definition: mesh_merge.c:35
static unsigned c
Definition: RandGen.cpp:83
unsigned int v1
unsigned int v2
unsigned int e
unsigned int v
struct MEdge * medge
CustomData vdata
struct MVert * mvert
int totedge
int totvert
struct MLoop * mloop
CustomData pdata
int totpoly
CustomData edata
int totloop
struct MPoly * mpoly
CustomData ldata
int poly_index
Definition: mesh_merge.c:167
uint hash_sum
Definition: mesh_merge.c:169
int totloops
Definition: mesh_merge.c:168
uint hash_xor
Definition: mesh_merge.c:170