Blender  V3.3
bmesh_region_match.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
20 #include <string.h>
21 
22 #include "BLI_alloca.h"
23 #include "BLI_ghash.h"
24 #include "BLI_linklist.h"
25 #include "BLI_linklist_stack.h"
26 #include "BLI_listbase.h"
27 #include "BLI_mempool.h"
28 #include "MEM_guardedalloc.h"
29 
30 #include "bmesh.h"
31 
32 #include "tools/bmesh_region_match.h" /* own include */
33 
34 /* avoid re-creating ghash and pools for each search */
35 #define USE_WALKER_REUSE
36 
37 /* do a first-pass id of all vertices,
38  * this avoids expensive checks on every item later on
39  * (works fine without, just slower) */
40 #define USE_PIVOT_FASTMATCH
41 
42 /* otherwise use active element as pivot, for quick tests only */
43 #define USE_PIVOT_SEARCH
44 
45 // #define DEBUG_TIME
46 // #define DEBUG_PRINT
47 
48 #ifdef DEBUG_TIME
49 # include "PIL_time.h"
50 # include "PIL_time_utildefines.h"
51 #endif
52 
53 #include "BLI_strict_flags.h"
54 
55 /* -------------------------------------------------------------------- */
59 #define PRIME_VERT_INIT 100003
60 
62 
63 typedef struct UUIDWalk {
64 
65  /* List of faces we can step onto (UUIDFaceStep's) */
67 
68  /* Face & Vert UUID's */
71 
72  /* memory pool for LinkNode's */
74 
75  /* memory pool for LinkBase's */
77 
78  /* memory pool for UUIDFaceStep's */
81 
82  /* Optionally use face-tag to isolate search */
84 
85  /* Increment for each pass added */
87 
88  /* runtime vars, avoid re-creating each pass */
89  struct {
90  GHash *verts_uuid; /* BMVert -> UUID */
91  GSet *faces_step; /* BMFace */
92 
93  GHash *faces_from_uuid; /* UUID -> UUIDFaceStepItem */
94 
97  } cache;
98 
100 
101 /* stores a set of potential faces to step onto */
102 typedef struct UUIDFaceStep {
103  struct UUIDFaceStep *next, *prev;
104 
105  /* unsorted 'BMFace' */
107 
108  /* faces sorted into 'UUIDFaceStepItem' */
111 
112 /* store face-lists with same uuid */
113 typedef struct UUIDFaceStepItem {
116 
120 
122 {
123  if (uuidwalk->use_face_isolate) {
125  }
126  return true;
127 }
128 
130 {
131  void **ret;
132  ret = BLI_ghash_lookup_p(uuidwalk->verts_uuid, v);
133  if (ret) {
134  *r_uuid = (UUID_Int)(*ret);
135  return true;
136  }
137  return false;
138 }
139 
141 {
142  void **ret;
143  ret = BLI_ghash_lookup_p(uuidwalk->faces_uuid, f);
144  if (ret) {
145  *r_uuid = (UUID_Int)(*ret);
146  return true;
147  }
148  return false;
149 }
150 
151 static uint ghashutil_bmelem_indexhash(const void *key)
152 {
153  const BMElem *ele = key;
154  return (uint)BM_elem_index_get(ele);
155 }
156 
157 static bool ghashutil_bmelem_indexcmp(const void *a, const void *b)
158 {
160  return (a != b);
161 }
162 
163 static GHash *ghash_bmelem_new_ex(const char *info, const uint nentries_reserve)
164 {
165  return BLI_ghash_new_ex(
166  ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve);
167 }
168 
169 static GSet *gset_bmelem_new_ex(const char *info, const uint nentries_reserve)
170 {
171  return BLI_gset_new_ex(
172  ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve);
173 }
174 
175 static GHash *ghash_bmelem_new(const char *info)
176 {
177  return ghash_bmelem_new_ex(info, 0);
178 }
179 
180 static GSet *gset_bmelem_new(const char *info)
181 {
182  return gset_bmelem_new_ex(info, 0);
183 }
184 
185 static void bm_uuidwalk_init(UUIDWalk *uuidwalk,
186  const uint faces_src_region_len,
187  const uint verts_src_region_len)
188 {
189  BLI_listbase_clear(&uuidwalk->faces_step);
190 
191  uuidwalk->verts_uuid = ghash_bmelem_new_ex(__func__, verts_src_region_len);
192  uuidwalk->faces_uuid = ghash_bmelem_new_ex(__func__, faces_src_region_len);
193 
194  uuidwalk->cache.verts_uuid = ghash_bmelem_new(__func__);
195  uuidwalk->cache.faces_step = gset_bmelem_new(__func__);
196 
197  /* works because 'int' ghash works for intptr_t too */
198  uuidwalk->cache.faces_from_uuid = BLI_ghash_int_new(__func__);
199 
200  uuidwalk->cache.rehash_store = NULL;
201  uuidwalk->cache.rehash_store_len = 0;
202 
203  uuidwalk->use_face_isolate = false;
204 
205  /* smaller pool's for faster clearing */
206  uuidwalk->link_pool = BLI_mempool_create(sizeof(LinkNode), 64, 64, BLI_MEMPOOL_NOP);
207  uuidwalk->step_pool = BLI_mempool_create(sizeof(UUIDFaceStep), 64, 64, BLI_MEMPOOL_NOP);
209  sizeof(UUIDFaceStepItem), 64, 64, BLI_MEMPOOL_NOP);
210 
211  uuidwalk->pass = 1;
212 }
213 
214 static void bm_uuidwalk_clear(UUIDWalk *uuidwalk)
215 {
216  BLI_listbase_clear(&uuidwalk->faces_step);
217 
218  BLI_ghash_clear(uuidwalk->verts_uuid, NULL, NULL);
219  BLI_ghash_clear(uuidwalk->faces_uuid, NULL, NULL);
220 
222  BLI_gset_clear(uuidwalk->cache.faces_step, NULL);
224 
225  /* keep rehash_store as-is, for reuse */
226 
227  uuidwalk->use_face_isolate = false;
228 
229  BLI_mempool_clear(uuidwalk->link_pool);
230  BLI_mempool_clear(uuidwalk->step_pool);
232 
233  uuidwalk->pass = 1;
234 }
235 
236 static void bm_uuidwalk_free(UUIDWalk *uuidwalk)
237 {
244  BLI_ghash_free(uuidwalk->verts_uuid, NULL, NULL);
245  BLI_ghash_free(uuidwalk->faces_uuid, NULL, NULL);
246 
247  /* cache */
248  BLI_ghash_free(uuidwalk->cache.verts_uuid, NULL, NULL);
249  BLI_gset_free(uuidwalk->cache.faces_step, NULL);
251  MEM_SAFE_FREE(uuidwalk->cache.rehash_store);
252 
253  BLI_mempool_destroy(uuidwalk->link_pool);
254  BLI_mempool_destroy(uuidwalk->step_pool);
256 }
257 
259 {
260 #define PRIME_VERT_SMALL 7
261 #define PRIME_VERT_MID 43
262 #define PRIME_VERT_LARGE 1031
263 
264 #define PRIME_FACE_SMALL 13
265 #define PRIME_FACE_MID 53
266 
267  UUID_Int uuid;
268 
269  uuid = uuidwalk->pass * PRIME_VERT_LARGE;
270 
271  /* vert -> other */
272  {
273  uint tot = 0;
274  BMIter eiter;
275  BMEdge *e;
276  BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
277  BMVert *v_other = BM_edge_other_vert(e, v);
278  UUID_Int uuid_other;
279  if (bm_uuidwalk_vert_lookup(uuidwalk, v_other, &uuid_other)) {
280  uuid ^= (uuid_other * PRIME_VERT_SMALL);
281  tot += 1;
282  }
283  }
284  uuid ^= (tot * PRIME_VERT_MID);
285  }
286 
287  /* faces */
288  {
289  uint tot = 0;
290  BMIter iter;
291  BMFace *f;
292 
293  BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
294  UUID_Int uuid_other;
295  if (bm_uuidwalk_face_lookup(uuidwalk, f, &uuid_other)) {
296  uuid ^= (uuid_other * PRIME_FACE_SMALL);
297  tot += 1;
298  }
299  }
300  uuid ^= (tot * PRIME_FACE_MID);
301  }
302 
303  return uuid;
304 
305 #undef PRIME_VERT_SMALL
306 #undef PRIME_VERT_MID
307 #undef PRIME_VERT_LARGE
308 
309 #undef PRIME_FACE_SMALL
310 #undef PRIME_FACE_MID
311 }
312 
314 {
315 #define PRIME_VERT_SMALL 11
316 
317 #define PRIME_FACE_SMALL 17
318 #define PRIME_FACE_LARGE 1013
319 
320  UUID_Int uuid;
321 
322  uuid = uuidwalk->pass * (uint)f->len * PRIME_FACE_LARGE;
323 
324  /* face-verts */
325  {
326  BMLoop *l_iter, *l_first;
327 
328  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
329  do {
330  UUID_Int uuid_other;
331  if (bm_uuidwalk_vert_lookup(uuidwalk, l_iter->v, &uuid_other)) {
332  uuid ^= (uuid_other * PRIME_VERT_SMALL);
333  }
334  } while ((l_iter = l_iter->next) != l_first);
335  }
336 
337  /* face-faces (connected by edge) */
338  {
339  BMLoop *l_iter, *l_first;
340 
341  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
342  do {
343  if (l_iter->radial_next != l_iter) {
344  BMLoop *l_iter_radial = l_iter->radial_next;
345  do {
346  UUID_Int uuid_other;
347  if (bm_uuidwalk_face_lookup(uuidwalk, l_iter_radial->f, &uuid_other)) {
348  uuid ^= (uuid_other * PRIME_FACE_SMALL);
349  }
350  } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter);
351  }
352  } while ((l_iter = l_iter->next) != l_first);
353  }
354 
355  return uuid;
356 
357 #undef PRIME_VERT_SMALL
358 
359 #undef PRIME_FACE_SMALL
360 #undef PRIME_FACE_LARGE
361 }
362 
363 static void bm_uuidwalk_rehash_reserve(UUIDWalk *uuidwalk, uint rehash_store_len_new)
364 {
365  if (UNLIKELY(rehash_store_len_new > uuidwalk->cache.rehash_store_len)) {
366  /* avoid re-allocs */
367  rehash_store_len_new *= 2;
368  uuidwalk->cache.rehash_store = MEM_reallocN(uuidwalk->cache.rehash_store,
369  rehash_store_len_new *
370  sizeof(*uuidwalk->cache.rehash_store));
371  uuidwalk->cache.rehash_store_len = rehash_store_len_new;
372  }
373 }
374 
378 static void bm_uuidwalk_rehash(UUIDWalk *uuidwalk)
379 {
380  GHashIterator gh_iter;
381  UUID_Int *uuid_store;
382  uint i;
383 
384  uint rehash_store_len_new = MAX2(BLI_ghash_len(uuidwalk->verts_uuid),
385  BLI_ghash_len(uuidwalk->faces_uuid));
386 
387  bm_uuidwalk_rehash_reserve(uuidwalk, rehash_store_len_new);
388  uuid_store = uuidwalk->cache.rehash_store;
389 
390  /* verts */
391  i = 0;
392  GHASH_ITER (gh_iter, uuidwalk->verts_uuid) {
393  BMVert *v = BLI_ghashIterator_getKey(&gh_iter);
394  uuid_store[i++] = bm_uuidwalk_calc_vert_uuid(uuidwalk, v);
395  }
396  i = 0;
397  GHASH_ITER (gh_iter, uuidwalk->verts_uuid) {
398  void **uuid_p = BLI_ghashIterator_getValue_p(&gh_iter);
399  *((UUID_Int *)uuid_p) = uuid_store[i++];
400  }
401 
402  /* faces */
403  i = 0;
404  GHASH_ITER (gh_iter, uuidwalk->faces_uuid) {
405  BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
406  uuid_store[i++] = bm_uuidwalk_calc_face_uuid(uuidwalk, f);
407  }
408  i = 0;
409  GHASH_ITER (gh_iter, uuidwalk->faces_uuid) {
410  void **uuid_p = BLI_ghashIterator_getValue_p(&gh_iter);
411  *((UUID_Int *)uuid_p) = uuid_store[i++];
412  }
413 }
414 
416  LinkNode *faces,
417  const uint faces_len,
418  const bool is_init)
419 {
420  UUID_Int *uuid_store;
421  LinkNode *f_link;
422  uint i;
423 
424  bm_uuidwalk_rehash_reserve(uuidwalk, faces_len);
425  uuid_store = uuidwalk->cache.rehash_store;
426 
427  i = 0;
428  for (f_link = faces; f_link; f_link = f_link->next) {
429  BMFace *f = f_link->link;
430  uuid_store[i++] = bm_uuidwalk_calc_face_uuid(uuidwalk, f);
431  }
432 
433  i = 0;
434  if (is_init) {
435  for (f_link = faces; f_link; f_link = f_link->next) {
436  BMFace *f = f_link->link;
437  BLI_ghash_insert(uuidwalk->faces_uuid, f, (void *)uuid_store[i++]);
438  }
439  }
440  else {
441  for (f_link = faces; f_link; f_link = f_link->next) {
442  BMFace *f = f_link->link;
443  void **uuid_p = BLI_ghash_lookup_p(uuidwalk->faces_uuid, f);
444  *((UUID_Int *)uuid_p) = uuid_store[i++];
445  }
446  }
447 }
448 
449 static bool bm_vert_is_uuid_connect(UUIDWalk *uuidwalk, BMVert *v)
450 {
451  BMIter eiter;
452  BMEdge *e;
453 
454  BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
455  BMVert *v_other = BM_edge_other_vert(e, v);
456  if (BLI_ghash_haskey(uuidwalk->verts_uuid, v_other)) {
457  return true;
458  }
459  }
460  return false;
461 }
462 
463 static void bm_uuidwalk_pass_add(UUIDWalk *uuidwalk,
464  LinkNode *faces_pass,
465  const uint faces_pass_len)
466 {
467  GHashIterator gh_iter;
468  GHash *verts_uuid_pass;
469  GSet *faces_step_next;
470  LinkNode *f_link;
471 
472  UUIDFaceStep *fstep;
473 
474  BLI_assert(faces_pass_len == (uint)BLI_linklist_count(faces_pass));
475 
476  /* rehash faces now all their verts have been added */
477  bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, true);
478 
479  /* create verts_new */
480  verts_uuid_pass = uuidwalk->cache.verts_uuid;
481  faces_step_next = uuidwalk->cache.faces_step;
482 
483  BLI_assert(BLI_ghash_len(verts_uuid_pass) == 0);
484  BLI_assert(BLI_gset_len(faces_step_next) == 0);
485 
486  /* Add the face_step data from connected faces, creating new passes */
487  fstep = BLI_mempool_alloc(uuidwalk->step_pool);
488  BLI_addhead(&uuidwalk->faces_step, fstep);
489  fstep->faces = NULL;
490  BLI_listbase_clear(&fstep->items);
491 
492  for (f_link = faces_pass; f_link; f_link = f_link->next) {
493  BMFace *f = f_link->link;
494  BMLoop *l_iter, *l_first;
495 
496  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
497  do {
498  /* fill verts_new */
499  void **val_p;
500  if (!BLI_ghash_haskey(uuidwalk->verts_uuid, l_iter->v) &&
501  !BLI_ghash_ensure_p(verts_uuid_pass, l_iter->v, &val_p) &&
502  (bm_vert_is_uuid_connect(uuidwalk, l_iter->v) == true)) {
503  const UUID_Int uuid = bm_uuidwalk_calc_vert_uuid(uuidwalk, l_iter->v);
504  *val_p = (void *)uuid;
505  }
506 
507  /* fill faces_step_next */
508  if (l_iter->radial_next != l_iter) {
509  BMLoop *l_iter_radial = l_iter->radial_next;
510  do {
511  if (!BLI_ghash_haskey(uuidwalk->faces_uuid, l_iter_radial->f) &&
512  !BLI_gset_haskey(faces_step_next, l_iter_radial->f) &&
513  (bm_uuidwalk_face_test(uuidwalk, l_iter_radial->f))) {
514  BLI_gset_insert(faces_step_next, l_iter_radial->f);
515 
516  /* add to fstep */
517  BLI_linklist_prepend_pool(&fstep->faces, l_iter_radial->f, uuidwalk->link_pool);
518  }
519  } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter);
520  }
521  } while ((l_iter = l_iter->next) != l_first);
522  }
523 
524  /* faces_uuid.update(verts_new) */
525  GHASH_ITER (gh_iter, verts_uuid_pass) {
526  BMVert *v = BLI_ghashIterator_getKey(&gh_iter);
527  void *uuid_p = BLI_ghashIterator_getValue(&gh_iter);
528  BLI_ghash_insert(uuidwalk->verts_uuid, v, uuid_p);
529  }
530 
531  /* rehash faces now all their verts have been added */
532  bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, false);
533 
534  uuidwalk->pass += 1;
535 
537  BLI_gset_clear(uuidwalk->cache.faces_step, NULL);
538 }
539 
540 static int bm_face_len_cmp(const void *v1, const void *v2)
541 {
542  const BMFace *f1 = *((BMFace **)v1);
543  const BMFace *f2 = *((BMFace **)v2);
544 
545  if (f1->len > f2->len) {
546  return 1;
547  }
548  if (f1->len < f2->len) {
549  return -1;
550  }
551  return 0;
552 }
553 
555 {
556  BMLoop *l_iter = e->l;
557  uint f_arr_len = (uint)BM_edge_face_count(e);
558  BMFace **f_arr = BLI_array_alloca(f_arr, f_arr_len);
559  uint fstep_num = 0, i = 0;
560 
561  do {
562  BMFace *f = l_iter->f;
563  if (bm_uuidwalk_face_test(uuidwalk, f)) {
564  f_arr[i++] = f;
565  }
566  } while ((l_iter = l_iter->radial_next) != e->l);
567  BLI_assert(i <= f_arr_len);
568  f_arr_len = i;
569 
570  qsort(f_arr, f_arr_len, sizeof(*f_arr), bm_face_len_cmp);
571 
572  /* start us off! */
573  {
574  const UUID_Int uuid = PRIME_VERT_INIT;
575  BLI_ghash_insert(uuidwalk->verts_uuid, e->v1, (void *)uuid);
576  BLI_ghash_insert(uuidwalk->verts_uuid, e->v2, (void *)uuid);
577  }
578 
579  /* turning an array into LinkNode's seems odd,
580  * but this is just for initialization,
581  * elsewhere using LinkNode's makes more sense */
582  for (i = 0; i < f_arr_len;) {
583  LinkNode *faces_pass = NULL;
584  const uint i_init = i;
585  const int f_len = f_arr[i]->len;
586 
587  do {
588  BLI_linklist_prepend_pool(&faces_pass, f_arr[i++], uuidwalk->link_pool);
589  } while (i < f_arr_len && (f_len == f_arr[i]->len));
590 
591  bm_uuidwalk_pass_add(uuidwalk, faces_pass, i - i_init);
592  BLI_linklist_free_pool(faces_pass, NULL, uuidwalk->link_pool);
593  fstep_num += 1;
594  }
595 
596  return fstep_num;
597 }
598 
599 #undef PRIME_VERT_INIT
600 
603 /* -------------------------------------------------------------------- */
607 static int facestep_sort(const void *a, const void *b)
608 {
609  const UUIDFaceStepItem *fstep_a = a;
610  const UUIDFaceStepItem *fstep_b = b;
611  return (fstep_a->uuid > fstep_b->uuid) ? 1 : 0;
612 }
613 
618 static bool bm_uuidwalk_facestep_begin(UUIDWalk *uuidwalk, UUIDFaceStep *fstep)
619 {
620  LinkNode *f_link, *f_link_next, **f_link_prev_p;
621  bool ok = false;
622 
625 
626  f_link_prev_p = &fstep->faces;
627  for (f_link = fstep->faces; f_link; f_link = f_link_next) {
628  BMFace *f = f_link->link;
629  f_link_next = f_link->next;
630 
631  /* possible another pass added this face already, free in that case */
632  if (!BLI_ghash_haskey(uuidwalk->faces_uuid, f)) {
633  const UUID_Int uuid = bm_uuidwalk_calc_face_uuid(uuidwalk, f);
634  UUIDFaceStepItem *fstep_item;
635  void **val_p;
636 
637  ok = true;
638 
639  if (BLI_ghash_ensure_p(uuidwalk->cache.faces_from_uuid, (void *)uuid, &val_p)) {
640  fstep_item = *val_p;
641  }
642  else {
643  fstep_item = *val_p = BLI_mempool_alloc(uuidwalk->step_pool_items);
644 
645  /* add to start, so its handled on the next round of passes */
646  BLI_addhead(&fstep->items, fstep_item);
647  fstep_item->uuid = uuid;
648  fstep_item->list = NULL;
649  fstep_item->list_len = 0;
650  }
651 
652  BLI_linklist_prepend_pool(&fstep_item->list, f, uuidwalk->link_pool);
653  fstep_item->list_len += 1;
654 
655  f_link_prev_p = &f_link->next;
656  }
657  else {
658  *f_link_prev_p = f_link->next;
659  BLI_mempool_free(uuidwalk->link_pool, f_link);
660  }
661  }
662 
664 
666 
667  return ok;
668 }
669 
673 static void bm_uuidwalk_facestep_end(UUIDWalk *uuidwalk, UUIDFaceStep *fstep)
674 {
675  UUIDFaceStepItem *fstep_item;
676 
677  while ((fstep_item = BLI_pophead(&fstep->items))) {
678  BLI_mempool_free(uuidwalk->step_pool_items, fstep_item);
679  }
680 }
681 
682 static void bm_uuidwalk_facestep_free(UUIDWalk *uuidwalk, UUIDFaceStep *fstep)
683 {
684  LinkNode *f_link, *f_link_next;
685 
687 
688  for (f_link = fstep->faces; f_link; f_link = f_link_next) {
689  f_link_next = f_link->next;
690  BLI_mempool_free(uuidwalk->link_pool, f_link);
691  }
692 
693  BLI_remlink(&uuidwalk->faces_step, fstep);
694  BLI_mempool_free(uuidwalk->step_pool, fstep);
695 }
696 
699 /* -------------------------------------------------------------------- */
700 /* Main Loop to match up regions */
701 
707 #ifdef USE_WALKER_REUSE
708  UUIDWalk *w_src,
709  UUIDWalk *w_dst,
710 #endif
711  BMEdge *e_src,
712  BMEdge *e_dst,
713  const uint faces_src_region_len,
714  const uint verts_src_region_len,
715  uint *r_faces_result_len)
716 {
717 #ifndef USE_WALKER_REUSE
718  UUIDWalk w_src_, w_dst_;
719  UUIDWalk *w_src = &w_src_, *w_dst = &w_dst_;
720 #endif
721  BMFace **faces_result = NULL;
722  bool found = false;
723 
724  BLI_assert(e_src != e_dst);
725 
726 #ifndef USE_WALKER_REUSE
727  bm_uuidwalk_init(w_src, faces_src_region_len, verts_src_region_len);
728  bm_uuidwalk_init(w_dst, faces_src_region_len, verts_src_region_len);
729 #endif
730 
731  w_src->use_face_isolate = true;
732 
733  /* setup the initial state */
734  if (UNLIKELY(bm_uuidwalk_init_from_edge(w_src, e_src) !=
735  bm_uuidwalk_init_from_edge(w_dst, e_dst))) {
736  /* should never happen, if verts passed are compatible, but to be safe... */
737  goto finally;
738  }
739 
740  bm_uuidwalk_rehash_reserve(w_src, MAX2(faces_src_region_len, verts_src_region_len));
741  bm_uuidwalk_rehash_reserve(w_dst, MAX2(faces_src_region_len, verts_src_region_len));
742 
743  while (true) {
744  bool ok = false;
745 
746  UUIDFaceStep *fstep_src = w_src->faces_step.first;
747  UUIDFaceStep *fstep_dst = w_dst->faces_step.first;
748 
749  BLI_assert(BLI_listbase_count(&w_src->faces_step) == BLI_listbase_count(&w_dst->faces_step));
750 
751  while (fstep_src) {
752 
753  /* even if the destination has faces,
754  * it's not important, since the source doesn't, free and move-on. */
755  if (fstep_src->faces == NULL) {
756  UUIDFaceStep *fstep_src_next = fstep_src->next;
757  UUIDFaceStep *fstep_dst_next = fstep_dst->next;
758  bm_uuidwalk_facestep_free(w_src, fstep_src);
759  bm_uuidwalk_facestep_free(w_dst, fstep_dst);
760  fstep_src = fstep_src_next;
761  fstep_dst = fstep_dst_next;
762  continue;
763  }
764 
765  if (bm_uuidwalk_facestep_begin(w_src, fstep_src) &&
766  bm_uuidwalk_facestep_begin(w_dst, fstep_dst)) {
767  /* Step over face-lists with matching UUID's
768  * both lists are sorted, so no need for lookups.
769  * The data is created on 'begin' and cleared on 'end' */
770  UUIDFaceStepItem *fstep_item_src;
771  UUIDFaceStepItem *fstep_item_dst;
772  for (fstep_item_src = fstep_src->items.first, fstep_item_dst = fstep_dst->items.first;
773  fstep_item_src && fstep_item_dst;
774  fstep_item_src = fstep_item_src->next, fstep_item_dst = fstep_item_dst->next) {
775  while ((fstep_item_dst != NULL) && (fstep_item_dst->uuid < fstep_item_src->uuid)) {
776  fstep_item_dst = fstep_item_dst->next;
777  }
778 
779  if ((fstep_item_dst == NULL) || (fstep_item_src->uuid != fstep_item_dst->uuid) ||
780  (fstep_item_src->list_len > fstep_item_dst->list_len)) {
781  /* if the target walker has less than the source
782  * then the islands don't match, bail early */
783  ok = false;
784  break;
785  }
786 
787  if (fstep_item_src->list_len == fstep_item_dst->list_len) {
788  /* found a match */
789  bm_uuidwalk_pass_add(w_src, fstep_item_src->list, fstep_item_src->list_len);
790  bm_uuidwalk_pass_add(w_dst, fstep_item_dst->list, fstep_item_dst->list_len);
791 
792  BLI_linklist_free_pool(fstep_item_src->list, NULL, w_src->link_pool);
793  BLI_linklist_free_pool(fstep_item_dst->list, NULL, w_dst->link_pool);
794 
795  fstep_item_src->list = NULL;
796  fstep_item_src->list_len = 0;
797 
798  fstep_item_dst->list = NULL;
799  fstep_item_dst->list_len = 0;
800 
801  ok = true;
802  }
803  }
804  }
805 
806  bm_uuidwalk_facestep_end(w_src, fstep_src);
807  bm_uuidwalk_facestep_end(w_dst, fstep_dst);
808 
809  /* lock-step */
810  fstep_src = fstep_src->next;
811  fstep_dst = fstep_dst->next;
812  }
813 
814  if (!ok) {
815  break;
816  }
817 
818  found = (BLI_ghash_len(w_dst->faces_uuid) == faces_src_region_len);
819  if (found) {
820  break;
821  }
822 
823  /* Expensive! but some cases fails without.
824  * (also faster in other cases since it can rule-out invalid regions) */
825  bm_uuidwalk_rehash(w_src);
826  bm_uuidwalk_rehash(w_dst);
827  }
828 
829  if (found) {
830  GHashIterator gh_iter;
831  const uint faces_result_len = BLI_ghash_len(w_dst->faces_uuid);
832  uint i;
833 
834  faces_result = MEM_mallocN(sizeof(*faces_result) * (faces_result_len + 1), __func__);
835  GHASH_ITER_INDEX (gh_iter, w_dst->faces_uuid, i) {
836  BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
837  faces_result[i] = f;
838  }
839  faces_result[faces_result_len] = NULL;
840  *r_faces_result_len = faces_result_len;
841  }
842  else {
843  *r_faces_result_len = 0;
844  }
845 
846 finally:
847 
848 #ifdef USE_WALKER_REUSE
849  bm_uuidwalk_clear(w_src);
850  bm_uuidwalk_clear(w_dst);
851 #else
852  bm_uuidwalk_free(w_src);
853  bm_uuidwalk_free(w_dst);
854 #endif
855 
856  return faces_result;
857 }
858 
863  const uint faces_len,
864  uint *r_verts_len,
865  bool visit_faces)
866 {
867  uint verts_len = 0;
868  uint i;
869  for (i = 0; i < faces_len; i++) {
870  BMFace *f = faces[i];
871  BMLoop *l_iter, *l_first;
872  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
873  do {
874  if (r_verts_len) {
875  if (!BM_elem_flag_test(l_iter->v, BM_ELEM_TAG)) {
876  verts_len += 1;
877  }
878  }
879 
882  } while ((l_iter = l_iter->next) != l_first);
883 
884  if (visit_faces) {
886  }
887  }
888 
889  if (r_verts_len) {
890  *r_verts_len = verts_len;
891  }
892 }
893 
894 #ifdef USE_PIVOT_SEARCH
895 
896 /* -------------------------------------------------------------------- */
900 /* signed user id */
902 
904 {
905  return (a < 0) ? -a : a;
906 }
907 
909 {
910  if (e->l->radial_next != e->l) {
911  BMLoop *l_iter = e->l;
912  do {
913  if (!BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
914  return true;
915  }
916  } while ((l_iter = l_iter->radial_next) != e->l);
917  return false;
918  }
919  /* boundary */
920  return true;
921 }
922 
924  BMEdge *e_test,
925  BMEdge **r_e_pivot_best,
926  SUID_Int e_pivot_best_id[2])
927 {
928  SUID_Int e_pivot_test_id[2];
929 
930  e_pivot_test_id[0] = (SUID_Int)BLI_ghash_lookup(gh, e_test->v1);
931  e_pivot_test_id[1] = (SUID_Int)BLI_ghash_lookup(gh, e_test->v2);
932  if (e_pivot_test_id[0] > e_pivot_test_id[1]) {
933  SWAP(SUID_Int, e_pivot_test_id[0], e_pivot_test_id[1]);
934  }
935 
936  if ((*r_e_pivot_best == NULL) ||
937  ((e_pivot_best_id[0] != e_pivot_test_id[0]) ? (e_pivot_best_id[0] < e_pivot_test_id[0]) :
938  (e_pivot_best_id[1] < e_pivot_test_id[1]))) {
939  e_pivot_best_id[0] = e_pivot_test_id[0];
940  e_pivot_best_id[1] = e_pivot_test_id[1];
941 
942  /* both verts are from the same pass, record this! */
943  *r_e_pivot_best = e_test;
944  }
945 }
946 
947 /* quick id from a boundary vertex */
949 {
950 # define PRIME_VERT_SMALL_A 7
951 # define PRIME_VERT_SMALL_B 13
952 # define PRIME_VERT_MID_A 103
953 # define PRIME_VERT_MID_B 131
954 
955  int tot = 0;
956  BMIter iter;
957  BMLoop *l;
959 
960  BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
961  const bool is_boundary_vert = (bm_edge_is_region_boundary(l->e) ||
963  id ^= l->f->len * (is_boundary_vert ? PRIME_VERT_SMALL_A : PRIME_VERT_SMALL_B);
964  tot += 1;
965  }
966 
967  id ^= (tot * PRIME_VERT_MID_B);
968 
969  return id ? abs_intptr(id) : 1;
970 
971 # undef PRIME_VERT_SMALL_A
972 # undef PRIME_VERT_SMALL_B
973 # undef PRIME_VERT_MID_A
974 # undef PRIME_VERT_MID_B
975 }
976 
981 {
982  BMIter eiter;
983  BMEdge *e;
984  SUID_Int tot = 0;
985  SUID_Int v_sum_face_len = 0;
986  SUID_Int v_sum_id = 0;
987  SUID_Int id;
988  SUID_Int id_min = INTPTR_MIN + 1;
989 
990 # define PRIME_VERT_MID_A 23
991 # define PRIME_VERT_MID_B 31
992 
993  BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
995  BMVert *v_other = BM_edge_other_vert(e, v);
996  if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
997  /* non-zero values aren't allowed... so no need to check haskey */
998  SUID_Int v_other_id = (SUID_Int)BLI_ghash_lookup(gh, v_other);
999  if (v_other_id > 0) {
1000  v_sum_id += v_other_id;
1001  tot += 1;
1002 
1003  /* face-count */
1004  {
1005  BMLoop *l_iter = e->l;
1006  do {
1007  if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) {
1008  v_sum_face_len += l_iter->f->len;
1009  }
1010  } while ((l_iter = l_iter->radial_next) != e->l);
1011  }
1012  }
1013  }
1014  }
1015  }
1016 
1017  id = (tot * PRIME_VERT_MID_A);
1018  id ^= (v_sum_face_len * PRIME_VERT_MID_B);
1019  id ^= v_sum_id;
1020 
1021  /* disallow 0 & min (since it can't be flipped) */
1022  id = (UNLIKELY(id == 0) ? 1 : UNLIKELY(id < id_min) ? id_min : id);
1023 
1024  return abs_intptr(id);
1025 
1026 # undef PRIME_VERT_MID_A
1027 # undef PRIME_VERT_MID_B
1028 }
1029 
1038  uint faces_region_len,
1039  uint verts_region_len,
1040  uint *r_depth)
1041 {
1042  /* NOTE: keep deterministic where possible (geometry order independent)
1043  * this function assumed all visit faces & edges are tagged */
1044 
1045  BLI_LINKSTACK_DECLARE(vert_queue_prev, BMVert *);
1046  BLI_LINKSTACK_DECLARE(vert_queue_next, BMVert *);
1047 
1048  GHash *gh = BLI_ghash_ptr_new(__func__);
1049  uint i;
1050 
1051  BMEdge *e_pivot = NULL;
1052  /* pick any non-boundary edge (not ideal) */
1053  BMEdge *e_pivot_fallback = NULL;
1054 
1055  SUID_Int pass = 0;
1056 
1057  /* total verts in 'gs' we have visited - aka - not v_init_none */
1058  uint vert_queue_used = 0;
1059 
1060  BLI_LINKSTACK_INIT(vert_queue_prev);
1061  BLI_LINKSTACK_INIT(vert_queue_next);
1062 
1063  /* face-verts */
1064  for (i = 0; i < faces_region_len; i++) {
1065  BMFace *f = faces_region[i];
1066 
1067  BMLoop *l_iter, *l_first;
1068  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1069  do {
1070  BMEdge *e = l_iter->e;
1072  uint j;
1073  for (j = 0; j < 2; j++) {
1074  void **val_p;
1075  if (!BLI_ghash_ensure_p(gh, (&e->v1)[j], &val_p)) {
1076  SUID_Int v_id = bm_face_region_vert_boundary_id((&e->v1)[j]);
1077  *val_p = (void *)v_id;
1078  BLI_LINKSTACK_PUSH(vert_queue_prev, (&e->v1)[j]);
1079  vert_queue_used += 1;
1080  }
1081  }
1082  }
1083  else {
1084  /* Use in case (depth == 0), no interior verts. */
1085  e_pivot_fallback = e;
1086  }
1087  } while ((l_iter = l_iter->next) != l_first);
1088  }
1089 
1090  while (BLI_LINKSTACK_SIZE(vert_queue_prev)) {
1091  BMVert *v;
1092  while ((v = BLI_LINKSTACK_POP(vert_queue_prev))) {
1093  BMIter eiter;
1094  BMEdge *e;
1097  BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1099  BMVert *v_other = BM_edge_other_vert(e, v);
1100  if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1101  void **val_p;
1102  if (!BLI_ghash_ensure_p(gh, v_other, &val_p)) {
1103  /* add as negative, so we know not to read from them this pass */
1104  const SUID_Int v_id_other = -bm_face_region_vert_pass_id(gh, v_other);
1105  *val_p = (void *)v_id_other;
1106  BLI_LINKSTACK_PUSH(vert_queue_next, v_other);
1107  vert_queue_used += 1;
1108  }
1109  }
1110  }
1111  }
1112  }
1113 
1114  /* flip all the newly added hashes to positive */
1115  {
1116  LinkNode *v_link;
1117  for (v_link = vert_queue_next; v_link; v_link = v_link->next) {
1118  SUID_Int *v_id_p = (SUID_Int *)BLI_ghash_lookup_p(gh, v_link->link);
1119  *v_id_p = -(*v_id_p);
1120  BLI_assert(*v_id_p > 0);
1121  }
1122  }
1123 
1124  BLI_LINKSTACK_SWAP(vert_queue_prev, vert_queue_next);
1125  pass += 1;
1126 
1127  if (vert_queue_used == verts_region_len) {
1128  break;
1129  }
1130  }
1131 
1132  if (BLI_LINKSTACK_SIZE(vert_queue_prev) >= 2) {
1133  /* common case - we managed to find some interior verts */
1134  LinkNode *v_link;
1135  BMEdge *e_pivot_best = NULL;
1136  SUID_Int e_pivot_best_id[2] = {0, 0};
1137 
1138  /* temp untag, so we can quickly know what other verts are in this last pass */
1139  for (v_link = vert_queue_prev; v_link; v_link = v_link->next) {
1140  BMVert *v = v_link->link;
1142  }
1143 
1144  /* restore correct tagging */
1145  for (v_link = vert_queue_prev; v_link; v_link = v_link->next) {
1146  BMIter eiter;
1147  BMEdge *e_test;
1148 
1149  BMVert *v = v_link->link;
1151 
1152  BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) {
1153  if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) {
1154  BMVert *v_other = BM_edge_other_vert(e_test, v);
1155  if (BM_elem_flag_test(v_other, BM_ELEM_TAG) == false) {
1156  bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id);
1157  }
1158  }
1159  }
1160  }
1161 
1162  e_pivot = e_pivot_best;
1163  }
1164 
1165  if ((e_pivot == NULL) && BLI_LINKSTACK_SIZE(vert_queue_prev)) {
1166  /* find the best single edge */
1167  BMEdge *e_pivot_best = NULL;
1168  SUID_Int e_pivot_best_id[2] = {0, 0};
1169 
1170  LinkNode *v_link;
1171 
1172  /* reduce a pass since we're having to step into a previous passes vert,
1173  * and will be closer to the boundary */
1174  BLI_assert(pass != 0);
1175  pass -= 1;
1176 
1177  for (v_link = vert_queue_prev; v_link; v_link = v_link->next) {
1178  BMVert *v = v_link->link;
1179 
1180  BMIter eiter;
1181  BMEdge *e_test;
1182  BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) {
1183  if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) {
1184  BMVert *v_other = BM_edge_other_vert(e_test, v);
1185  if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1186  bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id);
1187  }
1188  }
1189  }
1190  }
1191 
1192  e_pivot = e_pivot_best;
1193  }
1194 
1195  BLI_LINKSTACK_FREE(vert_queue_prev);
1196  BLI_LINKSTACK_FREE(vert_queue_next);
1197 
1198  BLI_ghash_free(gh, NULL, NULL);
1199 
1200  if (e_pivot == NULL) {
1201 # ifdef DEBUG_PRINT
1202  printf("%s: using fallback edge!\n", __func__);
1203 # endif
1204  e_pivot = e_pivot_fallback;
1205  pass = 0;
1206  }
1207 
1208  *r_depth = (uint)pass;
1209 
1210  return e_pivot;
1211 }
1212 
1215 #endif /* USE_PIVOT_SEARCH */
1216 
1217 /* Quick UUID pass - identify candidates */
1218 
1219 #ifdef USE_PIVOT_FASTMATCH
1220 
1221 /* -------------------------------------------------------------------- */
1226 
1228 {
1229  BMIter eiter;
1230  BMEdge *e;
1231  UUIDFashMatch e_num = 0, f_num = 0, l_num = 0;
1232 
1233 # define PRIME_EDGE 7
1234 # define PRIME_FACE 31
1235 # define PRIME_LOOP 61
1236 
1237  BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
1238  if (!BM_edge_is_wire(e)) {
1239  BMLoop *l_iter = e->l;
1240  e_num += 1;
1241  do {
1242  f_num += 1;
1243  l_num += (uint)l_iter->f->len;
1244  } while ((l_iter = l_iter->radial_next) != e->l);
1245  }
1246  }
1247 
1248  return ((e_num * PRIME_EDGE) ^ (f_num * PRIME_FACE) * (l_num * PRIME_LOOP));
1249 
1250 # undef PRIME_EDGE
1251 # undef PRIME_FACE
1252 # undef PRIME_LOOP
1253 }
1254 
1256 {
1257  UUIDFashMatch *id_prev;
1258  UUIDFashMatch *id_curr;
1259  uint pass, i;
1260  BMVert *v;
1261  BMIter iter;
1262 
1263  id_prev = MEM_mallocN(sizeof(*id_prev) * (uint)bm->totvert, __func__);
1264  id_curr = MEM_mallocN(sizeof(*id_curr) * (uint)bm->totvert, __func__);
1265 
1266  BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
1267  id_prev[i] = bm_vert_fasthash_single(v);
1268  }
1269 
1270  for (pass = 0; pass < depth; pass++) {
1271  BMEdge *e;
1272 
1273  memcpy(id_curr, id_prev, sizeof(*id_prev) * (uint)bm->totvert);
1274 
1275  BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
1276  if (BM_edge_is_wire(e) == false) {
1277  const int i1 = BM_elem_index_get(e->v1);
1278  const int i2 = BM_elem_index_get(e->v2);
1279 
1280  id_curr[i1] += id_prev[i2];
1281  id_curr[i2] += id_prev[i1];
1282  }
1283  }
1284  }
1285  MEM_freeN(id_prev);
1286 
1287  return id_curr;
1288 }
1289 
1291  const BMEdge *e,
1292  UUIDFashMatch e_fm[2])
1293 {
1294  e_fm[0] = fm[BM_elem_index_get(e->v1)];
1295  e_fm[1] = fm[BM_elem_index_get(e->v2)];
1296 
1297  if (e_fm[0] > e_fm[1]) {
1298  SWAP(UUIDFashMatch, e_fm[0], e_fm[1]);
1299  }
1300 }
1301 
1302 static bool bm_vert_fasthash_edge_is_match(UUIDFashMatch *fm, const BMEdge *e_a, const BMEdge *e_b)
1303 {
1304  UUIDFashMatch e_a_fm[2];
1305  UUIDFashMatch e_b_fm[2];
1306 
1307  bm_vert_fasthash_edge_order(fm, e_a, e_a_fm);
1308  bm_vert_fasthash_edge_order(fm, e_b, e_b_fm);
1309 
1310  return ((e_a_fm[0] == e_b_fm[0]) && (e_a_fm[1] == e_b_fm[1]));
1311 }
1312 
1314 {
1315  MEM_freeN(fm);
1316 }
1317 
1320 #endif /* USE_PIVOT_FASTMATCH */
1321 
1323  BMFace **faces_region,
1324  uint faces_region_len,
1325  ListBase *r_face_regions)
1326 {
1327  BMEdge *e_src;
1328  BMEdge *e_dst;
1329  BMIter iter;
1330  uint verts_region_len = 0;
1331  uint faces_result_len = 0;
1332  /* number of steps from e_src to a boundary vert */
1333  uint depth;
1334 
1335 #ifdef USE_WALKER_REUSE
1336  UUIDWalk w_src, w_dst;
1337 #endif
1338 
1339 #ifdef USE_PIVOT_FASTMATCH
1340  UUIDFashMatch *fm;
1341 #endif
1342 
1343 #ifdef DEBUG_PRINT
1344  int search_num = 0;
1345 #endif
1346 
1347 #ifdef DEBUG_TIME
1348  TIMEIT_START(region_match);
1349 #endif
1350 
1351  /* initialize visited verts */
1353  bm_face_array_visit(faces_region, faces_region_len, &verts_region_len, true);
1354 
1355  /* needed for 'ghashutil_bmelem_indexhash' */
1357 
1358 #ifdef USE_PIVOT_SEARCH
1359  e_src = bm_face_region_pivot_edge_find(faces_region, faces_region_len, verts_region_len, &depth);
1360 
1361  /* see which edge is added */
1362 # if 0
1364  if (e_src) {
1365  BM_select_history_store(bm, e_src);
1366  }
1367 # endif
1368 
1369 #else
1370  /* quick test only! */
1371  e_src = BM_mesh_active_edge_get(bm);
1372 #endif
1373 
1374  if (e_src == NULL) {
1375 #ifdef DEBUG_PRINT
1376  printf("Couldn't find 'e_src'");
1377 #endif
1378  return 0;
1379  }
1380 
1381  BLI_listbase_clear(r_face_regions);
1382 
1383 #ifdef USE_PIVOT_FASTMATCH
1384  if (depth > 0) {
1385  fm = bm_vert_fasthash_create(bm, depth);
1386  }
1387  else {
1388  fm = NULL;
1389  }
1390 #endif
1391 
1392 #ifdef USE_WALKER_REUSE
1393  bm_uuidwalk_init(&w_src, faces_region_len, verts_region_len);
1394  bm_uuidwalk_init(&w_dst, faces_region_len, verts_region_len);
1395 #endif
1396 
1397  BM_ITER_MESH (e_dst, &iter, bm, BM_EDGES_OF_MESH) {
1398  BMFace **faces_result;
1399  uint faces_result_len_out;
1400 
1401  if (BM_elem_flag_test(e_dst, BM_ELEM_TAG) || BM_edge_is_wire(e_dst)) {
1402  continue;
1403  }
1404 
1405 #ifdef USE_PIVOT_FASTMATCH
1406  if (fm && !bm_vert_fasthash_edge_is_match(fm, e_src, e_dst)) {
1407  continue;
1408  }
1409 #endif
1410 
1411 #ifdef DEBUG_PRINT
1412  search_num += 1;
1413 #endif
1414 
1415  faces_result = bm_mesh_region_match_pair(
1416 #ifdef USE_WALKER_REUSE
1417  &w_src,
1418  &w_dst,
1419 #endif
1420  e_src,
1421  e_dst,
1422  faces_region_len,
1423  verts_region_len,
1424  &faces_result_len_out);
1425 
1426  /* tag verts as visited */
1427  if (faces_result) {
1428  LinkData *link;
1429 
1430  bm_face_array_visit(faces_result, faces_result_len_out, NULL, false);
1431 
1432  link = BLI_genericNodeN(faces_result);
1433  BLI_addtail(r_face_regions, link);
1434  faces_result_len += 1;
1435  }
1436  }
1437 
1438 #ifdef USE_WALKER_REUSE
1439  bm_uuidwalk_free(&w_src);
1440  bm_uuidwalk_free(&w_dst);
1441 #else
1443 #endif
1444 
1445 #ifdef USE_PIVOT_FASTMATCH
1446  if (fm) {
1448  }
1449 #endif
1450 
1451 #ifdef DEBUG_PRINT
1452  printf("%s: search: %d, found %d\n", __func__, search_num, faces_result_len);
1453 #endif
1454 
1455 #ifdef DEBUG_TIME
1456  TIMEIT_END(region_match);
1457 #endif
1458 
1459  return (int)faces_result_len;
1460 }
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
struct GSet GSet
Definition: BLI_ghash.h:340
BLI_INLINE void * BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.h:298
bool BLI_ghash_haskey(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:822
bool BLI_gset_haskey(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:1007
void BLI_ghash_clear(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition: BLI_ghash.c:858
BLI_INLINE void * BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.h:302
BLI_INLINE void ** BLI_ghashIterator_getValue_p(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.h:306
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
#define GHASH_ITER(gh_iter_, ghash_)
Definition: BLI_ghash.h:321
void BLI_gset_clear(GSet *gs, GSetKeyFreeFP keyfreefp)
Definition: BLI_ghash.c:1032
unsigned int BLI_gset_len(const GSet *gs) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:957
void BLI_gset_insert(GSet *gs, void *key)
Definition: BLI_ghash.c:962
GHash * BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:734
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:705
GHash * BLI_ghash_new_ex(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:681
void BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition: BLI_ghash.c:710
void ** BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:748
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
Definition: BLI_ghash.c:863
void BLI_gset_free(GSet *gs, GSetKeyFreeFP keyfreefp)
Definition: BLI_ghash.c:1037
GHash * BLI_ghash_ptr_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:755
#define GHASH_ITER_INDEX(gh_iter_, ghash_, i_)
Definition: BLI_ghash.h:325
BLI_INLINE bool BLI_listbase_is_empty(const struct ListBase *lb)
Definition: BLI_listbase.h:269
void * BLI_pophead(ListBase *listbase) ATTR_NONNULL(1)
Definition: listbase.c:221
void BLI_addhead(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:60
BLI_INLINE void BLI_listbase_clear(struct ListBase *lb)
Definition: BLI_listbase.h:273
struct LinkData * BLI_genericNodeN(void *data)
Definition: listbase.c:842
void void BLI_listbase_sort(struct ListBase *listbase, int(*cmp)(const void *, const void *)) ATTR_NONNULL(1
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:80
void BLI_remlink(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
Definition: listbase.c:100
int BLI_listbase_count(const struct ListBase *listbase) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
@ BLI_MEMPOOL_NOP
Definition: BLI_mempool.h:99
void BLI_mempool_free(BLI_mempool *pool, void *addr) ATTR_NONNULL(1
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
Definition: BLI_mempool.c:253
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
Definition: BLI_mempool.c:319
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
Definition: BLI_mempool.c:707
void BLI_mempool_clear(BLI_mempool *pool) ATTR_NONNULL(1)
Definition: BLI_mempool.c:702
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define SWAP(type, a, b)
#define MAX2(a, b)
#define UNLIKELY(x)
_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 i1
_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.
#define MEM_SAFE_FREE(v)
#define MEM_reallocN(vmemh, len)
Platform independent time functions.
Utility defines for timing/benchmarks.
#define TIMEIT_START(var)
#define TIMEIT_END(var)
#define BM_FACE_FIRST_LOOP(p)
Definition: bmesh_class.h:622
@ BM_FACE
Definition: bmesh_class.h:386
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_EDGE
Definition: bmesh_class.h:384
@ BM_ELEM_TAG
Definition: bmesh_class.h:484
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_elem_flag_disable(ele, hflag)
Definition: bmesh_inline.h:15
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
#define BM_elem_flag_test_bool(ele, hflag)
Definition: bmesh_inline.h:13
#define BM_elem_flag_enable(ele, hflag)
Definition: bmesh_inline.h:14
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
@ BM_FACES_OF_VERT
@ BM_EDGES_OF_MESH
@ BM_VERTS_OF_MESH
@ BM_LOOPS_OF_VERT
@ BM_EDGES_OF_VERT
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_select_history_clear(BMesh *bm)
BMEdge * BM_mesh_active_edge_get(BMesh *bm)
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
#define BM_select_history_store(bm, ele)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:446
int BM_edge_face_count(const BMEdge *e)
Definition: bmesh_query.c:629
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMVert * v2
ATTR_WARN_UNUSED_RESULT const BMLoop * l
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMVert * v
static void bm_uuidwalk_init(UUIDWalk *uuidwalk, const uint faces_src_region_len, const uint verts_src_region_len)
BLI_INLINE bool bm_uuidwalk_face_test(UUIDWalk *uuidwalk, BMFace *f)
#define PRIME_LOOP
BLI_INLINE bool bm_uuidwalk_vert_lookup(UUIDWalk *uuidwalk, BMVert *v, UUID_Int *r_uuid)
static void bm_face_region_pivot_edge_use_best(GHash *gh, BMEdge *e_test, BMEdge **r_e_pivot_best, SUID_Int e_pivot_best_id[2])
static UUID_Int bm_uuidwalk_calc_face_uuid(UUIDWalk *uuidwalk, BMFace *f)
#define PRIME_VERT_MID_B
struct UUIDFaceStepItem UUIDFaceStepItem
static void bm_uuidwalk_free(UUIDWalk *uuidwalk)
static int bm_face_len_cmp(const void *v1, const void *v2)
static void bm_uuidwalk_rehash_reserve(UUIDWalk *uuidwalk, uint rehash_store_len_new)
static bool ghashutil_bmelem_indexcmp(const void *a, const void *b)
struct UUIDWalk UUIDWalk
#define PRIME_FACE_MID
static bool bm_vert_is_uuid_connect(UUIDWalk *uuidwalk, BMVert *v)
intptr_t SUID_Int
static UUID_Int bm_uuidwalk_calc_vert_uuid(UUIDWalk *uuidwalk, BMVert *v)
static void bm_uuidwalk_pass_add(UUIDWalk *uuidwalk, LinkNode *faces_pass, const uint faces_pass_len)
#define USE_WALKER_REUSE
static UUIDFashMatch bm_vert_fasthash_single(BMVert *v)
static UUIDFashMatch * bm_vert_fasthash_create(BMesh *bm, const uint depth)
static bool bm_uuidwalk_facestep_begin(UUIDWalk *uuidwalk, UUIDFaceStep *fstep)
#define PRIME_VERT_MID
static BMFace ** bm_mesh_region_match_pair(UUIDWalk *w_src, UUIDWalk *w_dst, BMEdge *e_src, BMEdge *e_dst, const uint faces_src_region_len, const uint verts_src_region_len, uint *r_faces_result_len)
#define PRIME_FACE
BLI_INLINE intptr_t abs_intptr(intptr_t a)
#define PRIME_EDGE
BLI_INLINE bool bm_uuidwalk_face_lookup(UUIDWalk *uuidwalk, BMFace *f, UUID_Int *r_uuid)
#define PRIME_FACE_SMALL
uintptr_t UUIDFashMatch
static GSet * gset_bmelem_new_ex(const char *info, const uint nentries_reserve)
static void bm_vert_fasthash_destroy(UUIDFashMatch *fm)
static SUID_Int bm_face_region_vert_pass_id(GHash *gh, BMVert *v)
static uint bm_uuidwalk_init_from_edge(UUIDWalk *uuidwalk, BMEdge *e)
static int facestep_sort(const void *a, const void *b)
static void bm_uuidwalk_facestep_free(UUIDWalk *uuidwalk, UUIDFaceStep *fstep)
#define PRIME_VERT_LARGE
#define PRIME_VERT_SMALL
static uint ghashutil_bmelem_indexhash(const void *key)
static bool bm_vert_fasthash_edge_is_match(UUIDFashMatch *fm, const BMEdge *e_a, const BMEdge *e_b)
static BMEdge * bm_face_region_pivot_edge_find(BMFace **faces_region, uint faces_region_len, uint verts_region_len, uint *r_depth)
#define PRIME_VERT_MID_A
#define PRIME_VERT_INIT
static void bm_uuidwalk_rehash(UUIDWalk *uuidwalk)
static void bm_uuidwalk_facestep_end(UUIDWalk *uuidwalk, UUIDFaceStep *fstep)
#define PRIME_VERT_SMALL_A
static void bm_uuidwalk_clear(UUIDWalk *uuidwalk)
struct UUIDFaceStep UUIDFaceStep
static SUID_Int bm_face_region_vert_boundary_id(BMVert *v)
static bool bm_edge_is_region_boundary(BMEdge *e)
static GHash * ghash_bmelem_new(const char *info)
#define PRIME_FACE_LARGE
uintptr_t UUID_Int
static void bm_vert_fasthash_edge_order(const UUIDFashMatch *fm, const BMEdge *e, UUIDFashMatch e_fm[2])
#define PRIME_VERT_SMALL_B
int BM_mesh_region_match(BMesh *bm, BMFace **faces_region, uint faces_region_len, ListBase *r_face_regions)
static void bm_uuidwalk_rehash_facelinks(UUIDWalk *uuidwalk, LinkNode *faces, const uint faces_len, const bool is_init)
static GHash * ghash_bmelem_new_ex(const char *info, const uint nentries_reserve)
static void bm_face_array_visit(BMFace **faces, const uint faces_len, uint *r_verts_len, bool visit_faces)
static GSet * gset_bmelem_new(const char *info)
SyclQueue void void size_t num_bytes void
int len
Definition: draw_manager.c:108
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
static char faces[256]
static unsigned a[3]
Definition: RandGen.cpp:78
static const pxr::TfToken b("b", pxr::TfToken::Immortal)
return ret
#define INTPTR_MIN
Definition: stdint.h:179
_W64 unsigned int uintptr_t
Definition: stdint.h:119
_W64 int intptr_t
Definition: stdint.h:118
BMVert * v1
Definition: bmesh_class.h:122
BMVert * v2
Definition: bmesh_class.h:122
int len
Definition: bmesh_class.h:267
struct BMVert * v
Definition: bmesh_class.h:153
struct BMEdge * e
Definition: bmesh_class.h:164
struct BMLoop * radial_next
Definition: bmesh_class.h:204
struct BMLoop * prev
Definition: bmesh_class.h:233
struct BMFace * f
Definition: bmesh_class.h:171
struct BMLoop * next
Definition: bmesh_class.h:233
int totvert
Definition: bmesh_class.h:297
void * link
Definition: BLI_linklist.h:24
struct LinkNode * next
Definition: BLI_linklist.h:23
void * first
Definition: DNA_listBase.h:31
struct UUIDFaceStepItem * prev
struct UUIDFaceStepItem * next
struct UUIDFaceStep * prev
struct UUIDFaceStep * next
UUID_Int pass
uint rehash_store_len
GSet * faces_step
BLI_mempool * step_pool
BLI_mempool * lbase_pool
GHash * faces_from_uuid
bool use_face_isolate
GHash * verts_uuid
BLI_mempool * step_pool_items
UUID_Int * rehash_store
struct UUIDWalk::@176 cache
GHash * faces_uuid
BLI_mempool * link_pool
ListBase faces_step