Blender  V3.3
pbvh_bmesh.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include "MEM_guardedalloc.h"
8 
9 #include "BLI_buffer.h"
10 #include "BLI_ghash.h"
11 #include "BLI_heap_simple.h"
12 #include "BLI_math.h"
13 #include "BLI_memarena.h"
14 #include "BLI_utildefines.h"
15 
16 #include "BKE_DerivedMesh.h"
17 #include "BKE_ccg.h"
18 #include "BKE_pbvh.h"
19 
20 #include "GPU_buffers.h"
21 
22 #include "bmesh.h"
23 #include "pbvh_intern.h"
24 
25 /* Avoid skinny faces */
26 #define USE_EDGEQUEUE_EVEN_SUBDIV
27 #ifdef USE_EDGEQUEUE_EVEN_SUBDIV
28 # include "BKE_global.h"
29 #endif
30 
31 /* Support for only operating on front-faces */
32 #define USE_EDGEQUEUE_FRONTFACE
33 
34 /* don't add edges into the queue multiple times */
35 #define USE_EDGEQUEUE_TAG
40 #if defined(USE_EDGEQUEUE_TAG) && 0
41 # if !defined(NDEBUG)
42 # define USE_EDGEQUEUE_TAG_VERIFY
43 # endif
44 #endif
45 
46 // #define USE_VERIFY
47 
48 #ifdef USE_VERIFY
49 static void pbvh_bmesh_verify(PBVH *pbvh);
50 #endif
51 
52 /* -------------------------------------------------------------------- */
65 #define BM_LOOPS_OF_VERT_ITER_BEGIN(l_iter_radial_, v_) \
66  { \
67  struct { \
68  BMVert *v; \
69  BMEdge *e_iter, *e_first; \
70  BMLoop *l_iter_radial; \
71  } _iter; \
72  _iter.v = v_; \
73  if (_iter.v->e) { \
74  _iter.e_iter = _iter.e_first = _iter.v->e; \
75  do { \
76  if (_iter.e_iter->l) { \
77  _iter.l_iter_radial = _iter.e_iter->l; \
78  do { \
79  if (_iter.l_iter_radial->v == _iter.v) { \
80  l_iter_radial_ = _iter.l_iter_radial;
81 
82 #define BM_LOOPS_OF_VERT_ITER_END \
83  } \
84  } \
85  while ((_iter.l_iter_radial = _iter.l_iter_radial->radial_next) != _iter.e_iter->l) \
86  ; \
87  } \
88  } \
89  while ((_iter.e_iter = BM_DISK_EDGE_NEXT(_iter.e_iter, _iter.v)) != _iter.e_first) \
90  ; \
91  } \
92  } \
93  ((void)0)
94 
95 #define BM_FACES_OF_VERT_ITER_BEGIN(f_iter_, v_) \
96  { \
97  BMLoop *l_iter_radial_; \
98  BM_LOOPS_OF_VERT_ITER_BEGIN (l_iter_radial_, v_) { \
99  f_iter_ = l_iter_radial_->f;
100 
101 #define BM_FACES_OF_VERT_ITER_END \
102  } \
103  BM_LOOPS_OF_VERT_ITER_END; \
104  } \
105  ((void)0)
106 
107 static void bm_edges_from_tri(BMesh *bm, BMVert *v_tri[3], BMEdge *e_tri[3])
108 {
109  e_tri[0] = BM_edge_create(bm, v_tri[0], v_tri[1], NULL, BM_CREATE_NO_DOUBLE);
110  e_tri[1] = BM_edge_create(bm, v_tri[1], v_tri[2], NULL, BM_CREATE_NO_DOUBLE);
111  e_tri[2] = BM_edge_create(bm, v_tri[2], v_tri[0], NULL, BM_CREATE_NO_DOUBLE);
112 }
113 
115 {
117 
118  BLI_assert(f->len == 3);
119 
120  r_index[0] = BM_elem_index_get(l->v);
121  l = l->next;
122  r_index[1] = BM_elem_index_get(l->v);
123  l = l->next;
124  r_index[2] = BM_elem_index_get(l->v);
125 }
126 
144 static BMFace *bm_face_exists_tri_from_loop_vert(BMLoop *l_radial_first, BMVert *v_opposite)
145 {
146  BLI_assert(
147  !ELEM(v_opposite, l_radial_first->v, l_radial_first->next->v, l_radial_first->prev->v));
148  if (l_radial_first->radial_next != l_radial_first) {
149  BMLoop *l_radial_iter = l_radial_first->radial_next;
150  do {
151  BLI_assert(l_radial_iter->f->len == 3);
152  if (l_radial_iter->prev->v == v_opposite) {
153  return l_radial_iter->f;
154  }
155  } while ((l_radial_iter = l_radial_iter->radial_next) != l_radial_first);
156  }
157  return NULL;
158 }
159 
164 static BMVert *bm_vert_hash_lookup_chain(GHash *deleted_verts, BMVert *v)
165 {
166  while (true) {
167  BMVert **v_next_p = (BMVert **)BLI_ghash_lookup_p(deleted_verts, v);
168  if (v_next_p == NULL) {
169  /* Not remapped. */
170  return v;
171  }
172  if (*v_next_p == NULL) {
173  /* removed and not remapped */
174  return NULL;
175  }
176 
177  /* remapped */
178  v = *v_next_p;
179  }
180 }
181 
184 /****************************** Building ******************************/
185 
186 /* Update node data after splitting */
187 static void pbvh_bmesh_node_finalize(PBVH *pbvh,
188  const int node_index,
189  const int cd_vert_node_offset,
190  const int cd_face_node_offset)
191 {
192  GSetIterator gs_iter;
193  PBVHNode *n = &pbvh->nodes[node_index];
194  bool has_visible = false;
195 
196  /* Create vert hash sets */
197  n->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts");
198  n->bm_other_verts = BLI_gset_ptr_new("bm_other_verts");
199 
200  BB_reset(&n->vb);
201 
202  GSET_ITER (gs_iter, n->bm_faces) {
203  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
204 
205  /* Update ownership of faces */
206  BM_ELEM_CD_SET_INT(f, cd_face_node_offset, node_index);
207 
208  /* Update vertices */
209  BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
210  BMLoop *l_iter = l_first;
211 
212  do {
213  BMVert *v = l_iter->v;
214  if (!BLI_gset_haskey(n->bm_unique_verts, v)) {
215  if (BM_ELEM_CD_GET_INT(v, cd_vert_node_offset) != DYNTOPO_NODE_NONE) {
217  }
218  else {
220  BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, node_index);
221  }
222  }
223  /* Update node bounding box */
224  BB_expand(&n->vb, v->co);
225  } while ((l_iter = l_iter->next) != l_first);
226 
228  has_visible = true;
229  }
230  }
231 
232  BLI_assert(n->vb.bmin[0] <= n->vb.bmax[0] && n->vb.bmin[1] <= n->vb.bmax[1] &&
233  n->vb.bmin[2] <= n->vb.bmax[2]);
234 
235  n->orig_vb = n->vb;
236 
237  /* Build GPU buffers for new node and update vertex normals */
239 
240  BKE_pbvh_node_fully_hidden_set(n, !has_visible);
241  n->flag |= PBVH_UpdateNormals;
242 }
243 
244 /* Recursively split the node if it exceeds the leaf_limit */
245 static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_index)
246 {
247  const int cd_vert_node_offset = pbvh->cd_vert_node_offset;
248  const int cd_face_node_offset = pbvh->cd_face_node_offset;
249  PBVHNode *n = &pbvh->nodes[node_index];
250 
251  if (BLI_gset_len(n->bm_faces) <= pbvh->leaf_limit) {
252  /* Node limit not exceeded */
253  pbvh_bmesh_node_finalize(pbvh, node_index, cd_vert_node_offset, cd_face_node_offset);
254  return;
255  }
256 
257  /* Calculate bounding box around primitive centroids */
258  BB cb;
259  BB_reset(&cb);
260  GSetIterator gs_iter;
261  GSET_ITER (gs_iter, n->bm_faces) {
262  const BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
263  const BBC *bbc = &bbc_array[BM_elem_index_get(f)];
264 
265  BB_expand(&cb, bbc->bcentroid);
266  }
267 
268  /* Find widest axis and its midpoint */
269  const int axis = BB_widest_axis(&cb);
270  const float mid = (cb.bmax[axis] + cb.bmin[axis]) * 0.5f;
271 
272  /* Add two new child nodes */
273  const int children = pbvh->totnode;
274  n->children_offset = children;
275  pbvh_grow_nodes(pbvh, pbvh->totnode + 2);
276 
277  /* Array reallocated, update current node pointer */
278  n = &pbvh->nodes[node_index];
279 
280  /* Initialize children */
281  PBVHNode *c1 = &pbvh->nodes[children], *c2 = &pbvh->nodes[children + 1];
282  c1->flag |= PBVH_Leaf;
283  c2->flag |= PBVH_Leaf;
284  c1->bm_faces = BLI_gset_ptr_new_ex("bm_faces", BLI_gset_len(n->bm_faces) / 2);
285  c2->bm_faces = BLI_gset_ptr_new_ex("bm_faces", BLI_gset_len(n->bm_faces) / 2);
286 
287  /* Partition the parent node's faces between the two children */
288  GSET_ITER (gs_iter, n->bm_faces) {
289  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
290  const BBC *bbc = &bbc_array[BM_elem_index_get(f)];
291 
292  if (bbc->bcentroid[axis] < mid) {
293  BLI_gset_insert(c1->bm_faces, f);
294  }
295  else {
296  BLI_gset_insert(c2->bm_faces, f);
297  }
298  }
299 
300  /* Enforce at least one primitive in each node */
301  GSet *empty = NULL, *other;
302  if (BLI_gset_len(c1->bm_faces) == 0) {
303  empty = c1->bm_faces;
304  other = c2->bm_faces;
305  }
306  else if (BLI_gset_len(c2->bm_faces) == 0) {
307  empty = c2->bm_faces;
308  other = c1->bm_faces;
309  }
310  if (empty) {
311  GSET_ITER (gs_iter, other) {
312  void *key = BLI_gsetIterator_getKey(&gs_iter);
313  BLI_gset_insert(empty, key);
314  BLI_gset_remove(other, key, NULL);
315  break;
316  }
317  }
318 
319  /* Clear this node */
320 
321  /* Mark this node's unique verts as unclaimed */
322  if (n->bm_unique_verts) {
323  GSET_ITER (gs_iter, n->bm_unique_verts) {
324  BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
325  BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, DYNTOPO_NODE_NONE);
326  }
328  }
329 
330  /* Unclaim faces */
331  GSET_ITER (gs_iter, n->bm_faces) {
332  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
333  BM_ELEM_CD_SET_INT(f, cd_face_node_offset, DYNTOPO_NODE_NONE);
334  }
336 
337  if (n->bm_other_verts) {
339  }
340 
341  if (n->layer_disp) {
342  MEM_freeN(n->layer_disp);
343  }
344 
345  n->bm_faces = NULL;
346  n->bm_unique_verts = NULL;
347  n->bm_other_verts = NULL;
348  n->layer_disp = NULL;
349 
350  if (n->draw_buffers) {
351  pbvh_free_draw_buffers(pbvh, n);
352  }
353  n->flag &= ~PBVH_Leaf;
354 
355  /* Recurse */
356  pbvh_bmesh_node_split(pbvh, bbc_array, children);
357  pbvh_bmesh_node_split(pbvh, bbc_array, children + 1);
358 
359  /* Array maybe reallocated, update current node pointer */
360  n = &pbvh->nodes[node_index];
361 
362  /* Update bounding box */
363  BB_reset(&n->vb);
364  BB_expand_with_bb(&n->vb, &pbvh->nodes[n->children_offset].vb);
365  BB_expand_with_bb(&n->vb, &pbvh->nodes[n->children_offset + 1].vb);
366  n->orig_vb = n->vb;
367 }
368 
369 /* Recursively split the node if it exceeds the leaf_limit */
370 static bool pbvh_bmesh_node_limit_ensure(PBVH *pbvh, int node_index)
371 {
372  GSet *bm_faces = pbvh->nodes[node_index].bm_faces;
373  const int bm_faces_size = BLI_gset_len(bm_faces);
374  if (bm_faces_size <= pbvh->leaf_limit) {
375  /* Node limit not exceeded */
376  return false;
377  }
378 
379  /* Trigger draw manager cache invalidation. */
380  pbvh->draw_cache_invalid = true;
381 
382  /* For each BMFace, store the AABB and AABB centroid */
383  BBC *bbc_array = MEM_mallocN(sizeof(BBC) * bm_faces_size, "BBC");
384 
385  GSetIterator gs_iter;
386  int i;
387  GSET_ITER_INDEX (gs_iter, bm_faces, i) {
388  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
389  BBC *bbc = &bbc_array[i];
390 
391  BB_reset((BB *)bbc);
392  BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
393  BMLoop *l_iter = l_first;
394  do {
395  BB_expand((BB *)bbc, l_iter->v->co);
396  } while ((l_iter = l_iter->next) != l_first);
397  BBC_update_centroid(bbc);
398 
399  /* so we can do direct lookups on 'bbc_array' */
400  BM_elem_index_set(f, i); /* set_dirty! */
401  }
402  /* Likely this is already dirty. */
403  pbvh->bm->elem_index_dirty |= BM_FACE;
404 
405  pbvh_bmesh_node_split(pbvh, bbc_array, node_index);
406 
407  MEM_freeN(bbc_array);
408 
409  return true;
410 }
411 
412 /**********************************************************************/
413 
414 #if 0
415 static int pbvh_bmesh_node_offset_from_elem(PBVH *pbvh, BMElem *ele)
416 {
417  switch (ele->head.htype) {
418  case BM_VERT:
419  return pbvh->cd_vert_node_offset;
420  default:
421  BLI_assert(ele->head.htype == BM_FACE);
422  return pbvh->cd_face_node_offset;
423  }
424 }
425 
426 static int pbvh_bmesh_node_index_from_elem(PBVH *pbvh, void *key)
427 {
428  const int cd_node_offset = pbvh_bmesh_node_offset_from_elem(pbvh, key);
429  const int node_index = BM_ELEM_CD_GET_INT((BMElem *)key, cd_node_offset);
430 
431  BLI_assert(node_index != DYNTOPO_NODE_NONE);
432  BLI_assert(node_index < pbvh->totnode);
433  (void)pbvh;
434 
435  return node_index;
436 }
437 
438 static PBVHNode *pbvh_bmesh_node_from_elem(PBVH *pbvh, void *key)
439 {
440  return &pbvh->nodes[pbvh_bmesh_node_index_from_elem(pbvh, key)];
441 }
442 
443 /* typecheck */
444 # define pbvh_bmesh_node_index_from_elem(pbvh, key) \
445  (CHECK_TYPE_ANY(key, BMFace *, BMVert *), pbvh_bmesh_node_index_from_elem(pbvh, key))
446 # define pbvh_bmesh_node_from_elem(pbvh, key) \
447  (CHECK_TYPE_ANY(key, BMFace *, BMVert *), pbvh_bmesh_node_from_elem(pbvh, key))
448 #endif
449 
451 {
452  const int node_index = BM_ELEM_CD_GET_INT((const BMElem *)key, pbvh->cd_vert_node_offset);
453  BLI_assert(node_index != DYNTOPO_NODE_NONE);
454  BLI_assert(node_index < pbvh->totnode);
455  return node_index;
456 }
457 
459 {
460  const int node_index = BM_ELEM_CD_GET_INT((const BMElem *)key, pbvh->cd_face_node_offset);
461  BLI_assert(node_index != DYNTOPO_NODE_NONE);
462  BLI_assert(node_index < pbvh->totnode);
463  return node_index;
464 }
465 
467 {
468  return &pbvh->nodes[pbvh_bmesh_node_index_from_vert(pbvh, key)];
469 }
470 
472 {
473  return &pbvh->nodes[pbvh_bmesh_node_index_from_face(pbvh, key)];
474 }
475 
477  int node_index,
478  const float co[3],
479  const float no[3],
480  const int cd_vert_mask_offset)
481 {
482  PBVHNode *node = &pbvh->nodes[node_index];
483 
484  BLI_assert((pbvh->totnode == 1 || node_index) && node_index <= pbvh->totnode);
485 
486  /* avoid initializing customdata because its quite involved */
489 
490  /* This value is logged below */
491  copy_v3_v3(v->no, no);
492 
493  BLI_gset_insert(node->bm_unique_verts, v);
494  BM_ELEM_CD_SET_INT(v, pbvh->cd_vert_node_offset, node_index);
495 
497 
498  /* Log the new vertex */
499  BM_log_vert_added(pbvh->bm_log, v, cd_vert_mask_offset);
500 
501  return v;
502 }
503 
508  PBVH *pbvh, int node_index, BMVert *v_tri[3], BMEdge *e_tri[3], const BMFace *f_example)
509 {
510  PBVHNode *node = &pbvh->nodes[node_index];
511 
512  /* ensure we never add existing face */
513  BLI_assert(!BM_face_exists(v_tri, 3));
514 
515  BMFace *f = BM_face_create(pbvh->bm, v_tri, e_tri, 3, f_example, BM_CREATE_NOP);
516  f->head.hflag = f_example->head.hflag;
517 
518  BLI_gset_insert(node->bm_faces, f);
519  BM_ELEM_CD_SET_INT(f, pbvh->cd_face_node_offset, node_index);
520 
521  /* mark node for update */
523  node->flag &= ~PBVH_FullyHidden;
524 
525  /* Log the new face */
526  BM_log_face_added(pbvh->bm_log, f);
527 
528  return f;
529 }
530 
531 /* Return the number of faces in 'node' that use vertex 'v' */
532 #if 0
533 static int pbvh_bmesh_node_vert_use_count(PBVH *pbvh, PBVHNode *node, BMVert *v)
534 {
535  BMFace *f;
536  int count = 0;
537 
539  PBVHNode *f_node = pbvh_bmesh_node_from_face(pbvh, f);
540  if (f_node == node) {
541  count++;
542  }
543  }
545 
546  return count;
547 }
548 #endif
549 
550 #define pbvh_bmesh_node_vert_use_count_is_equal(pbvh, node, v, n) \
551  (pbvh_bmesh_node_vert_use_count_at_most(pbvh, node, v, (n) + 1) == n)
552 
554  PBVHNode *node,
555  BMVert *v,
556  const int count_max)
557 {
558  int count = 0;
559  BMFace *f;
560 
562  PBVHNode *f_node = pbvh_bmesh_node_from_face(pbvh, f);
563  if (f_node == node) {
564  count++;
565  if (count == count_max) {
566  return count;
567  }
568  }
569  }
571 
572  return count;
573 }
574 
575 /* Return a node that uses vertex 'v' other than its current owner */
577 {
578  PBVHNode *current_node = pbvh_bmesh_node_from_vert(pbvh, v);
579  BMFace *f;
580 
582  PBVHNode *f_node = pbvh_bmesh_node_from_face(pbvh, f);
583 
584  if (f_node != current_node) {
585  return f_node;
586  }
587  }
589 
590  return NULL;
591 }
592 
593 static void pbvh_bmesh_vert_ownership_transfer(PBVH *pbvh, PBVHNode *new_owner, BMVert *v)
594 {
595  PBVHNode *current_owner = pbvh_bmesh_node_from_vert(pbvh, v);
596  /* mark node for update */
597  current_owner->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
598 
599  BLI_assert(current_owner != new_owner);
600 
601  /* Remove current ownership */
602  BLI_gset_remove(current_owner->bm_unique_verts, v, NULL);
603 
604  /* Set new ownership */
605  BM_ELEM_CD_SET_INT(v, pbvh->cd_vert_node_offset, new_owner - pbvh->nodes);
606  BLI_gset_insert(new_owner->bm_unique_verts, v);
607  BLI_gset_remove(new_owner->bm_other_verts, v, NULL);
609 
610  /* mark node for update */
611  new_owner->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
612 }
613 
614 static void pbvh_bmesh_vert_remove(PBVH *pbvh, BMVert *v)
615 {
616  /* never match for first time */
617  int f_node_index_prev = DYNTOPO_NODE_NONE;
618 
619  PBVHNode *v_node = pbvh_bmesh_node_from_vert(pbvh, v);
622 
623  /* Have to check each neighboring face's node */
624  BMFace *f;
626  const int f_node_index = pbvh_bmesh_node_index_from_face(pbvh, f);
627 
628  /* faces often share the same node,
629  * quick check to avoid redundant #BLI_gset_remove calls */
630  if (f_node_index_prev != f_node_index) {
631  f_node_index_prev = f_node_index;
632 
633  PBVHNode *f_node = &pbvh->nodes[f_node_index];
635 
636  /* Remove current ownership */
638 
641  }
642  }
644 }
645 
646 static void pbvh_bmesh_face_remove(PBVH *pbvh, BMFace *f)
647 {
648  PBVHNode *f_node = pbvh_bmesh_node_from_face(pbvh, f);
649 
650  /* Check if any of this face's vertices need to be removed
651  * from the node */
652  BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
653  BMLoop *l_iter = l_first;
654  do {
655  BMVert *v = l_iter->v;
656  if (pbvh_bmesh_node_vert_use_count_is_equal(pbvh, f_node, v, 1)) {
657  if (BLI_gset_haskey(f_node->bm_unique_verts, v)) {
658  /* Find a different node that uses 'v' */
659  PBVHNode *new_node;
660 
661  new_node = pbvh_bmesh_vert_other_node_find(pbvh, v);
662  BLI_assert(new_node || BM_vert_face_count_is_equal(v, 1));
663 
664  if (new_node) {
665  pbvh_bmesh_vert_ownership_transfer(pbvh, new_node, v);
666  }
667  }
668  else {
669  /* Remove from other verts */
671  }
672  }
673  } while ((l_iter = l_iter->next) != l_first);
674 
675  /* Remove face from node and top level */
676  BLI_gset_remove(f_node->bm_faces, f, NULL);
678 
679  /* Log removed face */
680  BM_log_face_removed(pbvh->bm_log, f);
681 
682  /* mark node for update */
684 }
685 
687 {
688  /* fast-path for most common case where an edge has 2 faces,
689  * no need to iterate twice.
690  * This assumes that the buffer */
691  BMLoop **data = buf->data;
692  BLI_assert(buf->alloc_count >= 2);
693  if (LIKELY(BM_edge_loop_pair(e, &data[0], &data[1]))) {
694  buf->count = 2;
695  }
696  else {
699  }
700 }
701 
703 {
704  if (node->bm_orco) {
705  MEM_freeN(node->bm_orco);
706  }
707  if (node->bm_ortri) {
708  MEM_freeN(node->bm_ortri);
709  }
710  node->bm_orco = NULL;
711  node->bm_ortri = NULL;
712  node->bm_tot_ortri = 0;
713 }
714 
715 /****************************** EdgeQueue *****************************/
716 
717 struct EdgeQueue;
718 
719 typedef struct EdgeQueue {
721  const float *center;
722  float center_proj[3]; /* for when we use projected coords. */
725 #ifdef USE_EDGEQUEUE_EVEN_SUBDIV
726  float limit_len;
727 #endif
728 
729  bool (*edge_queue_tri_in_range)(const struct EdgeQueue *q, BMFace *f);
730 
731  const float *view_normal;
732 #ifdef USE_EDGEQUEUE_FRONTFACE
733  unsigned int use_view_normal : 1;
734 #endif
736 
737 typedef struct {
745 
746 /* only tag'd edges are in the queue */
747 #ifdef USE_EDGEQUEUE_TAG
748 # define EDGE_QUEUE_TEST(e) (BM_elem_flag_test((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG))
749 # define EDGE_QUEUE_ENABLE(e) \
750  BM_elem_flag_enable((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG)
751 # define EDGE_QUEUE_DISABLE(e) \
752  BM_elem_flag_disable((CHECK_TYPE_INLINE(e, BMEdge *), e), BM_ELEM_TAG)
753 #endif
754 
755 #ifdef USE_EDGEQUEUE_TAG_VERIFY
756 /* simply check no edges are tagged
757  * (it's a requirement that edges enter and leave a clean tag state) */
758 static void pbvh_bmesh_edge_tag_verify(PBVH *pbvh)
759 {
760  for (int n = 0; n < pbvh->totnode; n++) {
761  PBVHNode *node = &pbvh->nodes[n];
762  if (node->bm_faces) {
763  GSetIterator gs_iter;
764  GSET_ITER (gs_iter, node->bm_faces) {
765  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
766  BMEdge *e_tri[3];
767  BMLoop *l_iter;
768 
769  BLI_assert(f->len == 3);
770  l_iter = BM_FACE_FIRST_LOOP(f);
771  e_tri[0] = l_iter->e;
772  l_iter = l_iter->next;
773  e_tri[1] = l_iter->e;
774  l_iter = l_iter->next;
775  e_tri[2] = l_iter->e;
776 
777  BLI_assert((EDGE_QUEUE_TEST(e_tri[0]) == false) && (EDGE_QUEUE_TEST(e_tri[1]) == false) &&
778  (EDGE_QUEUE_TEST(e_tri[2]) == false));
779  }
780  }
781  }
782 }
783 #endif
784 
785 static bool edge_queue_tri_in_sphere(const EdgeQueue *q, BMFace *f)
786 {
787  BMVert *v_tri[3];
788  float c[3];
789 
790  /* Get closest point in triangle to sphere center */
791  BM_face_as_array_vert_tri(f, v_tri);
792 
793  closest_on_tri_to_point_v3(c, q->center, v_tri[0]->co, v_tri[1]->co, v_tri[2]->co);
794 
795  /* Check if triangle intersects the sphere */
796  return len_squared_v3v3(q->center, c) <= q->radius_squared;
797 }
798 
799 static bool edge_queue_tri_in_circle(const EdgeQueue *q, BMFace *f)
800 {
801  BMVert *v_tri[3];
802  float c[3];
803  float tri_proj[3][3];
804 
805  /* Get closest point in triangle to sphere center */
806  BM_face_as_array_vert_tri(f, v_tri);
807 
808  project_plane_normalized_v3_v3v3(tri_proj[0], v_tri[0]->co, q->view_normal);
809  project_plane_normalized_v3_v3v3(tri_proj[1], v_tri[1]->co, q->view_normal);
810  project_plane_normalized_v3_v3v3(tri_proj[2], v_tri[2]->co, q->view_normal);
811 
812  closest_on_tri_to_point_v3(c, q->center_proj, tri_proj[0], tri_proj[1], tri_proj[2]);
813 
814  /* Check if triangle intersects the sphere */
815  return len_squared_v3v3(q->center_proj, c) <= q->radius_squared;
816 }
817 
818 /* Return true if the vertex mask is less than 1.0, false otherwise */
819 static bool check_mask(EdgeQueueContext *eq_ctx, BMVert *v)
820 {
821  return BM_ELEM_CD_GET_FLOAT(v, eq_ctx->cd_vert_mask_offset) < 1.0f;
822 }
823 
824 static void edge_queue_insert(EdgeQueueContext *eq_ctx, BMEdge *e, float priority)
825 {
826  /* Don't let topology update affect fully masked vertices. This used to
827  * have a 50% mask cutoff, with the reasoning that you can't do a 50%
828  * topology update. But this gives an ugly border in the mesh. The mask
829  * should already make the brush move the vertices only 50%, which means
830  * that topology updates will also happen less frequent, that should be
831  * enough. */
832  if (((eq_ctx->cd_vert_mask_offset == -1) ||
833  (check_mask(eq_ctx, e->v1) || check_mask(eq_ctx, e->v2))) &&
836  BMVert **pair = BLI_mempool_alloc(eq_ctx->pool);
837  pair[0] = e->v1;
838  pair[1] = e->v2;
839  BLI_heapsimple_insert(eq_ctx->q->heap, priority, pair);
840 #ifdef USE_EDGEQUEUE_TAG
841  BLI_assert(EDGE_QUEUE_TEST(e) == false);
843 #endif
844  }
845 }
846 
848 {
849 #ifdef USE_EDGEQUEUE_TAG
850  if (EDGE_QUEUE_TEST(e) == false)
851 #endif
852  {
853  const float len_sq = BM_edge_calc_length_squared(e);
854  if (len_sq > eq_ctx->q->limit_len_squared) {
855  edge_queue_insert(eq_ctx, e, -len_sq);
856  }
857  }
858 }
859 
860 #ifdef USE_EDGEQUEUE_EVEN_SUBDIV
862  EdgeQueueContext *eq_ctx, BMLoop *l_edge, BMLoop *l_end, const float len_sq, float limit_len)
863 {
864  BLI_assert(len_sq > square_f(limit_len));
865 
866 # ifdef USE_EDGEQUEUE_FRONTFACE
867  if (eq_ctx->q->use_view_normal) {
868  if (dot_v3v3(l_edge->f->no, eq_ctx->q->view_normal) < 0.0f) {
869  return;
870  }
871  }
872 # endif
873 
874 # ifdef USE_EDGEQUEUE_TAG
875  if (EDGE_QUEUE_TEST(l_edge->e) == false)
876 # endif
877  {
878  edge_queue_insert(eq_ctx, l_edge->e, -len_sq);
879  }
880 
881  /* temp support previous behavior! */
882  if (UNLIKELY(G.debug_value == 1234)) {
883  return;
884  }
885 
886  if ((l_edge->radial_next != l_edge)) {
887  /* How much longer we need to be to consider for subdividing
888  * (avoids subdividing faces which are only *slightly* skinny) */
889 # define EVEN_EDGELEN_THRESHOLD 1.2f
890  /* How much the limit increases per recursion
891  * (avoids performing subdivisions too far away). */
892 # define EVEN_GENERATION_SCALE 1.6f
893 
894  const float len_sq_cmp = len_sq * EVEN_EDGELEN_THRESHOLD;
895 
896  limit_len *= EVEN_GENERATION_SCALE;
897  const float limit_len_sq = square_f(limit_len);
898 
899  BMLoop *l_iter = l_edge;
900  do {
901  BMLoop *l_adjacent[2] = {l_iter->next, l_iter->prev};
902  for (int i = 0; i < ARRAY_SIZE(l_adjacent); i++) {
903  float len_sq_other = BM_edge_calc_length_squared(l_adjacent[i]->e);
904  if (len_sq_other > max_ff(len_sq_cmp, limit_len_sq)) {
905  // edge_queue_insert(eq_ctx, l_adjacent[i]->e, -len_sq_other);
907  eq_ctx, l_adjacent[i]->radial_next, l_adjacent[i], len_sq_other, limit_len);
908  }
909  }
910  } while ((l_iter = l_iter->radial_next) != l_end);
911 
912 # undef EVEN_EDGELEN_THRESHOLD
913 # undef EVEN_GENERATION_SCALE
914  }
915 }
916 #endif /* USE_EDGEQUEUE_EVEN_SUBDIV */
917 
919 {
920 #ifdef USE_EDGEQUEUE_TAG
921  if (EDGE_QUEUE_TEST(e) == false)
922 #endif
923  {
924  const float len_sq = BM_edge_calc_length_squared(e);
925  if (len_sq < eq_ctx->q->limit_len_squared) {
926  edge_queue_insert(eq_ctx, e, len_sq);
927  }
928  }
929 }
930 
932 {
933 #ifdef USE_EDGEQUEUE_FRONTFACE
934  if (eq_ctx->q->use_view_normal) {
935  if (dot_v3v3(f->no, eq_ctx->q->view_normal) < 0.0f) {
936  return;
937  }
938  }
939 #endif
940 
941  if (eq_ctx->q->edge_queue_tri_in_range(eq_ctx->q, f)) {
942  /* Check each edge of the face */
943  BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
944  BMLoop *l_iter = l_first;
945  do {
946 #ifdef USE_EDGEQUEUE_EVEN_SUBDIV
947  const float len_sq = BM_edge_calc_length_squared(l_iter->e);
948  if (len_sq > eq_ctx->q->limit_len_squared) {
950  eq_ctx, l_iter->radial_next, l_iter, len_sq, eq_ctx->q->limit_len);
951  }
952 #else
953  long_edge_queue_edge_add(eq_ctx, l_iter->e);
954 #endif
955  } while ((l_iter = l_iter->next) != l_first);
956  }
957 }
958 
960 {
961 #ifdef USE_EDGEQUEUE_FRONTFACE
962  if (eq_ctx->q->use_view_normal) {
963  if (dot_v3v3(f->no, eq_ctx->q->view_normal) < 0.0f) {
964  return;
965  }
966  }
967 #endif
968 
969  if (eq_ctx->q->edge_queue_tri_in_range(eq_ctx->q, f)) {
970  BMLoop *l_iter;
971  BMLoop *l_first;
972 
973  /* Check each edge of the face */
974  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
975  do {
976  short_edge_queue_edge_add(eq_ctx, l_iter->e);
977  } while ((l_iter = l_iter->next) != l_first);
978  }
979 }
980 
981 /* Create a priority queue containing vertex pairs connected by a long
982  * edge as defined by PBVH.bm_max_edge_len.
983  *
984  * Only nodes marked for topology update are checked, and in those
985  * nodes only edges used by a face intersecting the (center, radius)
986  * sphere are checked.
987  *
988  * The highest priority (lowest number) is given to the longest edge.
989  */
991  PBVH *pbvh,
992  const float center[3],
993  const float view_normal[3],
994  float radius,
995  const bool use_frontface,
996  const bool use_projected)
997 {
998  eq_ctx->q->heap = BLI_heapsimple_new();
999  eq_ctx->q->center = center;
1000  eq_ctx->q->radius_squared = radius * radius;
1001  eq_ctx->q->limit_len_squared = pbvh->bm_max_edge_len * pbvh->bm_max_edge_len;
1002 #ifdef USE_EDGEQUEUE_EVEN_SUBDIV
1003  eq_ctx->q->limit_len = pbvh->bm_max_edge_len;
1004 #endif
1005 
1006  eq_ctx->q->view_normal = view_normal;
1007 
1008 #ifdef USE_EDGEQUEUE_FRONTFACE
1009  eq_ctx->q->use_view_normal = use_frontface;
1010 #else
1011  UNUSED_VARS(use_frontface);
1012 #endif
1013 
1014  if (use_projected) {
1016  project_plane_normalized_v3_v3v3(eq_ctx->q->center_proj, center, view_normal);
1017  }
1018  else {
1020  }
1021 
1022 #ifdef USE_EDGEQUEUE_TAG_VERIFY
1023  pbvh_bmesh_edge_tag_verify(pbvh);
1024 #endif
1025 
1026  for (int n = 0; n < pbvh->totnode; n++) {
1027  PBVHNode *node = &pbvh->nodes[n];
1028 
1029  /* Check leaf nodes marked for topology update */
1030  if ((node->flag & PBVH_Leaf) && (node->flag & PBVH_UpdateTopology) &&
1031  !(node->flag & PBVH_FullyHidden)) {
1032  GSetIterator gs_iter;
1033 
1034  /* Check each face */
1035  GSET_ITER (gs_iter, node->bm_faces) {
1036  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
1037 
1038  long_edge_queue_face_add(eq_ctx, f);
1039  }
1040  }
1041  }
1042 }
1043 
1044 /* Create a priority queue containing vertex pairs connected by a
1045  * short edge as defined by PBVH.bm_min_edge_len.
1046  *
1047  * Only nodes marked for topology update are checked, and in those
1048  * nodes only edges used by a face intersecting the (center, radius)
1049  * sphere are checked.
1050  *
1051  * The highest priority (lowest number) is given to the shortest edge.
1052  */
1054  PBVH *pbvh,
1055  const float center[3],
1056  const float view_normal[3],
1057  float radius,
1058  const bool use_frontface,
1059  const bool use_projected)
1060 {
1061  eq_ctx->q->heap = BLI_heapsimple_new();
1062  eq_ctx->q->center = center;
1063  eq_ctx->q->radius_squared = radius * radius;
1064  eq_ctx->q->limit_len_squared = pbvh->bm_min_edge_len * pbvh->bm_min_edge_len;
1065 #ifdef USE_EDGEQUEUE_EVEN_SUBDIV
1066  eq_ctx->q->limit_len = pbvh->bm_min_edge_len;
1067 #endif
1068 
1069  eq_ctx->q->view_normal = view_normal;
1070 
1071 #ifdef USE_EDGEQUEUE_FRONTFACE
1072  eq_ctx->q->use_view_normal = use_frontface;
1073 #else
1074  UNUSED_VARS(use_frontface);
1075 #endif
1076 
1077  if (use_projected) {
1079  project_plane_normalized_v3_v3v3(eq_ctx->q->center_proj, center, view_normal);
1080  }
1081  else {
1083  }
1084 
1085  for (int n = 0; n < pbvh->totnode; n++) {
1086  PBVHNode *node = &pbvh->nodes[n];
1087 
1088  /* Check leaf nodes marked for topology update */
1089  if ((node->flag & PBVH_Leaf) && (node->flag & PBVH_UpdateTopology) &&
1090  !(node->flag & PBVH_FullyHidden)) {
1091  GSetIterator gs_iter;
1092 
1093  /* Check each face */
1094  GSET_ITER (gs_iter, node->bm_faces) {
1095  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
1096 
1097  short_edge_queue_face_add(eq_ctx, f);
1098  }
1099  }
1100  }
1101 }
1102 
1103 /*************************** Topology update **************************/
1104 
1106  PBVH *pbvh,
1107  BMEdge *e,
1108  BLI_Buffer *edge_loops)
1109 {
1110  float co_mid[3], no_mid[3];
1111 
1112  /* Get all faces adjacent to the edge */
1113  pbvh_bmesh_edge_loops(edge_loops, e);
1114 
1115  /* Create a new vertex in current node at the edge's midpoint */
1116  mid_v3_v3v3(co_mid, e->v1->co, e->v2->co);
1117  mid_v3_v3v3(no_mid, e->v1->no, e->v2->no);
1118  normalize_v3(no_mid);
1119 
1120  int node_index = BM_ELEM_CD_GET_INT(e->v1, eq_ctx->cd_vert_node_offset);
1121  BMVert *v_new = pbvh_bmesh_vert_create(
1122  pbvh, node_index, co_mid, no_mid, eq_ctx->cd_vert_mask_offset);
1123 
1124  /* update paint mask */
1125  if (eq_ctx->cd_vert_mask_offset != -1) {
1126  float mask_v1 = BM_ELEM_CD_GET_FLOAT(e->v1, eq_ctx->cd_vert_mask_offset);
1127  float mask_v2 = BM_ELEM_CD_GET_FLOAT(e->v2, eq_ctx->cd_vert_mask_offset);
1128  float mask_v_new = 0.5f * (mask_v1 + mask_v2);
1129 
1130  BM_ELEM_CD_SET_FLOAT(v_new, eq_ctx->cd_vert_mask_offset, mask_v_new);
1131  }
1132 
1133  /* For each face, add two new triangles and delete the original */
1134  for (int i = 0; i < edge_loops->count; i++) {
1135  BMLoop *l_adj = BLI_buffer_at(edge_loops, BMLoop *, i);
1136  BMFace *f_adj = l_adj->f;
1137  BMFace *f_new;
1138  BMVert *v_opp, *v1, *v2;
1139  BMVert *v_tri[3];
1140  BMEdge *e_tri[3];
1141 
1142  BLI_assert(f_adj->len == 3);
1143  int ni = BM_ELEM_CD_GET_INT(f_adj, eq_ctx->cd_face_node_offset);
1144 
1145  /* Find the vertex not in the edge */
1146  v_opp = l_adj->prev->v;
1147 
1148  /* Get e->v1 and e->v2 in the order they appear in the
1149  * existing face so that the new faces' winding orders
1150  * match */
1151  v1 = l_adj->v;
1152  v2 = l_adj->next->v;
1153 
1154  if (ni != node_index && i == 0) {
1155  pbvh_bmesh_vert_ownership_transfer(pbvh, &pbvh->nodes[ni], v_new);
1156  }
1157 
1184  /* Create two new faces */
1185  v_tri[0] = v1;
1186  v_tri[1] = v_new;
1187  v_tri[2] = v_opp;
1188  bm_edges_from_tri(pbvh->bm, v_tri, e_tri);
1189  f_new = pbvh_bmesh_face_create(pbvh, ni, v_tri, e_tri, f_adj);
1190  long_edge_queue_face_add(eq_ctx, f_new);
1191 
1192  v_tri[0] = v_new;
1193  v_tri[1] = v2;
1194  /* v_tri[2] = v_opp; */ /* unchanged */
1195  e_tri[0] = BM_edge_create(pbvh->bm, v_tri[0], v_tri[1], NULL, BM_CREATE_NO_DOUBLE);
1196  e_tri[2] = e_tri[1]; /* switched */
1197  e_tri[1] = BM_edge_create(pbvh->bm, v_tri[1], v_tri[2], NULL, BM_CREATE_NO_DOUBLE);
1198  f_new = pbvh_bmesh_face_create(pbvh, ni, v_tri, e_tri, f_adj);
1199  long_edge_queue_face_add(eq_ctx, f_new);
1200 
1201  /* Delete original */
1202  pbvh_bmesh_face_remove(pbvh, f_adj);
1203  BM_face_kill(pbvh->bm, f_adj);
1204 
1205  /* Ensure new vertex is in the node */
1206  if (!BLI_gset_haskey(pbvh->nodes[ni].bm_unique_verts, v_new)) {
1207  BLI_gset_add(pbvh->nodes[ni].bm_other_verts, v_new);
1208  }
1209 
1210  if (BM_vert_edge_count_is_over(v_opp, 8)) {
1211  BMIter bm_iter;
1212  BMEdge *e2;
1213 
1214  BM_ITER_ELEM (e2, &bm_iter, v_opp, BM_EDGES_OF_VERT) {
1215  long_edge_queue_edge_add(eq_ctx, e2);
1216  }
1217  }
1218  }
1219 
1220  BM_edge_kill(pbvh->bm, e);
1221 }
1222 
1224  PBVH *pbvh,
1225  BLI_Buffer *edge_loops)
1226 {
1227  bool any_subdivided = false;
1228 
1229  while (!BLI_heapsimple_is_empty(eq_ctx->q->heap)) {
1230  BMVert **pair = BLI_heapsimple_pop_min(eq_ctx->q->heap);
1231  BMVert *v1 = pair[0], *v2 = pair[1];
1232  BMEdge *e;
1233 
1234  BLI_mempool_free(eq_ctx->pool, pair);
1235  pair = NULL;
1236 
1237  /* Check that the edge still exists */
1238  if (!(e = BM_edge_exists(v1, v2))) {
1239  continue;
1240  }
1241 #ifdef USE_EDGEQUEUE_TAG
1243 #endif
1244 
1245  /* At the moment edges never get shorter (subdivision will make new edges)
1246  * unlike collapse where edges can become longer. */
1247 #if 0
1248  if (len_squared_v3v3(v1->co, v2->co) <= eq_ctx->q->limit_len_squared) {
1249  continue;
1250  }
1251 #else
1252  BLI_assert(len_squared_v3v3(v1->co, v2->co) > eq_ctx->q->limit_len_squared);
1253 #endif
1254 
1255  /* Check that the edge's vertices are still in the PBVH. It's
1256  * possible that an edge collapse has deleted adjacent faces
1257  * and the node has been split, thus leaving wire edges and
1258  * associated vertices. */
1259  if ((BM_ELEM_CD_GET_INT(e->v1, eq_ctx->cd_vert_node_offset) == DYNTOPO_NODE_NONE) ||
1261  continue;
1262  }
1263 
1264  any_subdivided = true;
1265 
1266  pbvh_bmesh_split_edge(eq_ctx, pbvh, e, edge_loops);
1267  }
1268 
1269 #ifdef USE_EDGEQUEUE_TAG_VERIFY
1270  pbvh_bmesh_edge_tag_verify(pbvh);
1271 #endif
1272 
1273  return any_subdivided;
1274 }
1275 
1276 static void pbvh_bmesh_collapse_edge(PBVH *pbvh,
1277  BMEdge *e,
1278  BMVert *v1,
1279  BMVert *v2,
1280  GHash *deleted_verts,
1281  BLI_Buffer *deleted_faces,
1282  EdgeQueueContext *eq_ctx)
1283 {
1284  BMVert *v_del, *v_conn;
1285 
1286  /* one of the two vertices may be masked, select the correct one for deletion */
1289  v_del = v1;
1290  v_conn = v2;
1291  }
1292  else {
1293  v_del = v2;
1294  v_conn = v1;
1295  }
1296 
1297  /* Remove the merge vertex from the PBVH */
1298  pbvh_bmesh_vert_remove(pbvh, v_del);
1299 
1300  /* Remove all faces adjacent to the edge */
1301  BMLoop *l_adj;
1302  while ((l_adj = e->l)) {
1303  BMFace *f_adj = l_adj->f;
1304 
1305  pbvh_bmesh_face_remove(pbvh, f_adj);
1306  BM_face_kill(pbvh->bm, f_adj);
1307  }
1308 
1309  /* Kill the edge */
1311  BM_edge_kill(pbvh->bm, e);
1312 
1313  /* For all remaining faces of v_del, create a new face that is the
1314  * same except it uses v_conn instead of v_del */
1315  /* NOTE: this could be done with BM_vert_splice(), but that
1316  * requires handling other issues like duplicate edges, so doesn't
1317  * really buy anything. */
1318  BLI_buffer_clear(deleted_faces);
1319 
1320  BMLoop *l;
1321 
1322  BM_LOOPS_OF_VERT_ITER_BEGIN (l, v_del) {
1323  BMFace *existing_face;
1324 
1325  /* Get vertices, replace use of v_del with v_conn */
1326  // BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f, (void **)v_tri, 3);
1327  BMFace *f = l->f;
1328 #if 0
1329  BMVert *v_tri[3];
1330  BM_face_as_array_vert_tri(f, v_tri);
1331  for (int i = 0; i < 3; i++) {
1332  if (v_tri[i] == v_del) {
1333  v_tri[i] = v_conn;
1334  }
1335  }
1336 #endif
1337 
1338  /* Check if a face using these vertices already exists. If so,
1339  * skip adding this face and mark the existing one for
1340  * deletion as well. Prevents extraneous "flaps" from being
1341  * created. */
1342 #if 0
1343  if (UNLIKELY(existing_face = BM_face_exists(v_tri, 3)))
1344 #else
1345  if (UNLIKELY(existing_face = bm_face_exists_tri_from_loop_vert(l->next, v_conn)))
1346 #endif
1347  {
1348  BLI_buffer_append(deleted_faces, BMFace *, existing_face);
1349  }
1350  else
1351  {
1352  BMVert *v_tri[3] = {v_conn, l->next->v, l->prev->v};
1353 
1354  BLI_assert(!BM_face_exists(v_tri, 3));
1355  BMEdge *e_tri[3];
1356  PBVHNode *n = pbvh_bmesh_node_from_face(pbvh, f);
1357  int ni = n - pbvh->nodes;
1358  bm_edges_from_tri(pbvh->bm, v_tri, e_tri);
1359  pbvh_bmesh_face_create(pbvh, ni, v_tri, e_tri, f);
1360 
1361  /* Ensure that v_conn is in the new face's node */
1362  if (!BLI_gset_haskey(n->bm_unique_verts, v_conn)) {
1363  BLI_gset_add(n->bm_other_verts, v_conn);
1364  }
1365  }
1366 
1367  BLI_buffer_append(deleted_faces, BMFace *, f);
1368  }
1370 
1371  /* Delete the tagged faces */
1372  for (int i = 0; i < deleted_faces->count; i++) {
1373  BMFace *f_del = BLI_buffer_at(deleted_faces, BMFace *, i);
1374 
1375  /* Get vertices and edges of face */
1376  BLI_assert(f_del->len == 3);
1377  BMLoop *l_iter = BM_FACE_FIRST_LOOP(f_del);
1378  BMVert *v_tri[3];
1379  BMEdge *e_tri[3];
1380  v_tri[0] = l_iter->v;
1381  e_tri[0] = l_iter->e;
1382  l_iter = l_iter->next;
1383  v_tri[1] = l_iter->v;
1384  e_tri[1] = l_iter->e;
1385  l_iter = l_iter->next;
1386  v_tri[2] = l_iter->v;
1387  e_tri[2] = l_iter->e;
1388 
1389  /* Remove the face */
1390  pbvh_bmesh_face_remove(pbvh, f_del);
1391  BM_face_kill(pbvh->bm, f_del);
1392 
1393  /* Check if any of the face's edges are now unused by any
1394  * face, if so delete them */
1395  for (int j = 0; j < 3; j++) {
1396  if (BM_edge_is_wire(e_tri[j])) {
1397  BM_edge_kill(pbvh->bm, e_tri[j]);
1398  }
1399  }
1400 
1401  /* Check if any of the face's vertices are now unused, if so
1402  * remove them from the PBVH */
1403  for (int j = 0; j < 3; j++) {
1404  if ((v_tri[j] != v_del) && (v_tri[j]->e == NULL)) {
1405  pbvh_bmesh_vert_remove(pbvh, v_tri[j]);
1406 
1407  BM_log_vert_removed(pbvh->bm_log, v_tri[j], eq_ctx->cd_vert_mask_offset);
1408 
1409  if (v_tri[j] == v_conn) {
1410  v_conn = NULL;
1411  }
1412  BLI_ghash_insert(deleted_verts, v_tri[j], NULL);
1413  BM_vert_kill(pbvh->bm, v_tri[j]);
1414  }
1415  }
1416  }
1417 
1418  /* Move v_conn to the midpoint of v_conn and v_del (if v_conn still exists, it
1419  * may have been deleted above) */
1420  if (v_conn != NULL) {
1421  BM_log_vert_before_modified(pbvh->bm_log, v_conn, eq_ctx->cd_vert_mask_offset);
1422  mid_v3_v3v3(v_conn->co, v_conn->co, v_del->co);
1423  add_v3_v3(v_conn->no, v_del->no);
1424  normalize_v3(v_conn->no);
1425 
1426  /* update boundboxes attached to the connected vertex
1427  * note that we can often get-away without this but causes T48779 */
1428  BM_LOOPS_OF_VERT_ITER_BEGIN (l, v_conn) {
1429  PBVHNode *f_node = pbvh_bmesh_node_from_face(pbvh, l->f);
1431  }
1433  }
1434 
1435  /* Delete v_del */
1436  BLI_assert(!BM_vert_face_check(v_del));
1437  BM_log_vert_removed(pbvh->bm_log, v_del, eq_ctx->cd_vert_mask_offset);
1438  /* v_conn == NULL is OK */
1439  BLI_ghash_insert(deleted_verts, v_del, v_conn);
1440  BM_vert_kill(pbvh->bm, v_del);
1441 }
1442 
1444  PBVH *pbvh,
1445  BLI_Buffer *deleted_faces)
1446 {
1447  const float min_len_squared = pbvh->bm_min_edge_len * pbvh->bm_min_edge_len;
1448  bool any_collapsed = false;
1449  /* deleted verts point to vertices they were merged into, or NULL when removed. */
1450  GHash *deleted_verts = BLI_ghash_ptr_new("deleted_verts");
1451 
1452  while (!BLI_heapsimple_is_empty(eq_ctx->q->heap)) {
1453  BMVert **pair = BLI_heapsimple_pop_min(eq_ctx->q->heap);
1454  BMVert *v1 = pair[0], *v2 = pair[1];
1455  BLI_mempool_free(eq_ctx->pool, pair);
1456  pair = NULL;
1457 
1458  /* Check the verts still exist */
1459  if (!(v1 = bm_vert_hash_lookup_chain(deleted_verts, v1)) ||
1460  !(v2 = bm_vert_hash_lookup_chain(deleted_verts, v2)) || (v1 == v2)) {
1461  continue;
1462  }
1463 
1464  /* Check that the edge still exists */
1465  BMEdge *e;
1466  if (!(e = BM_edge_exists(v1, v2))) {
1467  continue;
1468  }
1469 #ifdef USE_EDGEQUEUE_TAG
1471 #endif
1472 
1473  if (len_squared_v3v3(v1->co, v2->co) >= min_len_squared) {
1474  continue;
1475  }
1476 
1477  /* Check that the edge's vertices are still in the PBVH. It's
1478  * possible that an edge collapse has deleted adjacent faces
1479  * and the node has been split, thus leaving wire edges and
1480  * associated vertices. */
1481  if ((BM_ELEM_CD_GET_INT(e->v1, eq_ctx->cd_vert_node_offset) == DYNTOPO_NODE_NONE) ||
1483  continue;
1484  }
1485 
1486  any_collapsed = true;
1487 
1488  pbvh_bmesh_collapse_edge(pbvh, e, v1, v2, deleted_verts, deleted_faces, eq_ctx);
1489  }
1490 
1491  BLI_ghash_free(deleted_verts, NULL, NULL);
1492 
1493  return any_collapsed;
1494 }
1495 
1496 /************************* Called from pbvh.c *************************/
1497 
1499  const float ray_start[3],
1500  const float ray_normal[3],
1501  struct IsectRayPrecalc *isect_precalc,
1502  float *depth,
1503  bool use_original,
1504  int *r_active_vertex_index,
1505  float *r_face_normal)
1506 {
1507  bool hit = false;
1508  float nearest_vertex_co[3] = {0.0f};
1509 
1510  if (use_original && node->bm_tot_ortri) {
1511  for (int i = 0; i < node->bm_tot_ortri; i++) {
1512  const int *t = node->bm_ortri[i];
1513  hit |= ray_face_intersection_tri(ray_start,
1514  isect_precalc,
1515  node->bm_orco[t[0]],
1516  node->bm_orco[t[1]],
1517  node->bm_orco[t[2]],
1518  depth);
1519  }
1520  }
1521  else {
1522  GSetIterator gs_iter;
1523 
1524  GSET_ITER (gs_iter, node->bm_faces) {
1525  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
1526 
1527  BLI_assert(f->len == 3);
1528  if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
1529  BMVert *v_tri[3];
1530 
1531  BM_face_as_array_vert_tri(f, v_tri);
1532 
1534  ray_start, isect_precalc, v_tri[0]->co, v_tri[1]->co, v_tri[2]->co, depth)) {
1535  hit = true;
1536 
1537  if (r_face_normal) {
1538  normal_tri_v3(r_face_normal, v_tri[0]->co, v_tri[1]->co, v_tri[2]->co);
1539  }
1540 
1541  if (r_active_vertex_index) {
1542  float location[3] = {0.0f};
1543  madd_v3_v3v3fl(location, ray_start, ray_normal, *depth);
1544  for (int j = 0; j < 3; j++) {
1545  if (len_squared_v3v3(location, v_tri[j]->co) <
1546  len_squared_v3v3(location, nearest_vertex_co)) {
1547  copy_v3_v3(nearest_vertex_co, v_tri[j]->co);
1548  *r_active_vertex_index = BM_elem_index_get(v_tri[j]);
1549  }
1550  }
1551  }
1552  }
1553  }
1554  }
1555  }
1556 
1557  return hit;
1558 }
1559 
1561  const float ray_start[3],
1562  struct IsectRayPrecalc *isect_precalc,
1563  float *depth,
1564  float *r_edge_length)
1565 {
1566  if (node->flag & PBVH_FullyHidden) {
1567  return 0;
1568  }
1569 
1570  GSetIterator gs_iter;
1571  bool hit = false;
1572  BMFace *f_hit = NULL;
1573 
1574  GSET_ITER (gs_iter, node->bm_faces) {
1575  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
1576 
1577  BLI_assert(f->len == 3);
1578  if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
1579  BMVert *v_tri[3];
1580  bool hit_local;
1581  BM_face_as_array_vert_tri(f, v_tri);
1582  hit_local = ray_face_intersection_tri(
1583  ray_start, isect_precalc, v_tri[0]->co, v_tri[1]->co, v_tri[2]->co, depth);
1584 
1585  if (hit_local) {
1586  f_hit = f;
1587  hit = true;
1588  }
1589  }
1590  }
1591 
1592  if (hit) {
1593  BMVert *v_tri[3];
1594  BM_face_as_array_vert_tri(f_hit, v_tri);
1595  float len1 = len_squared_v3v3(v_tri[0]->co, v_tri[1]->co);
1596  float len2 = len_squared_v3v3(v_tri[1]->co, v_tri[2]->co);
1597  float len3 = len_squared_v3v3(v_tri[2]->co, v_tri[0]->co);
1598 
1599  /* detail returned will be set to the maximum allowed size, so take max here */
1600  *r_edge_length = sqrtf(max_fff(len1, len2, len3));
1601  }
1602 
1603  return hit;
1604 }
1605 
1607  const float ray_start[3],
1608  const float ray_normal[3],
1609  float *depth,
1610  float *dist_sq,
1611  bool use_original)
1612 {
1613  bool hit = false;
1614 
1615  if (use_original && node->bm_tot_ortri) {
1616  for (int i = 0; i < node->bm_tot_ortri; i++) {
1617  const int *t = node->bm_ortri[i];
1618  hit |= ray_face_nearest_tri(ray_start,
1619  ray_normal,
1620  node->bm_orco[t[0]],
1621  node->bm_orco[t[1]],
1622  node->bm_orco[t[2]],
1623  depth,
1624  dist_sq);
1625  }
1626  }
1627  else {
1628  GSetIterator gs_iter;
1629 
1630  GSET_ITER (gs_iter, node->bm_faces) {
1631  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
1632 
1633  BLI_assert(f->len == 3);
1634  if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
1635  BMVert *v_tri[3];
1636 
1637  BM_face_as_array_vert_tri(f, v_tri);
1638  hit |= ray_face_nearest_tri(
1639  ray_start, ray_normal, v_tri[0]->co, v_tri[1]->co, v_tri[2]->co, depth, dist_sq);
1640  }
1641  }
1642  }
1643 
1644  return hit;
1645 }
1646 
1647 void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode)
1648 {
1649  for (int n = 0; n < totnode; n++) {
1650  PBVHNode *node = nodes[n];
1651 
1652  if (node->flag & PBVH_UpdateNormals) {
1653  GSetIterator gs_iter;
1654 
1655  GSET_ITER (gs_iter, node->bm_faces) {
1657  }
1658  GSET_ITER (gs_iter, node->bm_unique_verts) {
1660  }
1661  /* This should be unneeded normally */
1662  GSET_ITER (gs_iter, node->bm_other_verts) {
1664  }
1665  node->flag &= ~PBVH_UpdateNormals;
1666  }
1667  }
1668 }
1669 
1671  int totface; /* number of faces */
1672  int start; /* start of faces in array */
1675 };
1676 
1683  PBVH *pbvh, BMFace **nodeinfo, BBC *bbc_array, struct FastNodeBuildInfo *node, MemArena *arena)
1684 {
1685  struct FastNodeBuildInfo *child1, *child2;
1686 
1687  if (node->totface <= pbvh->leaf_limit) {
1688  return;
1689  }
1690 
1691  /* Calculate bounding box around primitive centroids */
1692  BB cb;
1693  BB_reset(&cb);
1694  for (int i = 0; i < node->totface; i++) {
1695  BMFace *f = nodeinfo[i + node->start];
1696  BBC *bbc = &bbc_array[BM_elem_index_get(f)];
1697 
1698  BB_expand(&cb, bbc->bcentroid);
1699  }
1700 
1701  /* initialize the children */
1702 
1703  /* Find widest axis and its midpoint */
1704  const int axis = BB_widest_axis(&cb);
1705  const float mid = (cb.bmax[axis] + cb.bmin[axis]) * 0.5f;
1706 
1707  int num_child1 = 0, num_child2 = 0;
1708 
1709  /* split vertices along the middle line */
1710  const int end = node->start + node->totface;
1711  for (int i = node->start; i < end - num_child2; i++) {
1712  BMFace *f = nodeinfo[i];
1713  BBC *bbc = &bbc_array[BM_elem_index_get(f)];
1714 
1715  if (bbc->bcentroid[axis] > mid) {
1716  int i_iter = end - num_child2 - 1;
1717  int candidate = -1;
1718  /* found a face that should be part of another node, look for a face to substitute with */
1719 
1720  for (; i_iter > i; i_iter--) {
1721  BMFace *f_iter = nodeinfo[i_iter];
1722  const BBC *bbc_iter = &bbc_array[BM_elem_index_get(f_iter)];
1723  if (bbc_iter->bcentroid[axis] <= mid) {
1724  candidate = i_iter;
1725  break;
1726  }
1727 
1728  num_child2++;
1729  }
1730 
1731  if (candidate != -1) {
1732  BMFace *tmp = nodeinfo[i];
1733  nodeinfo[i] = nodeinfo[candidate];
1734  nodeinfo[candidate] = tmp;
1735  /* increase both counts */
1736  num_child1++;
1737  num_child2++;
1738  }
1739  else {
1740  /* not finding candidate means second half of array part is full of
1741  * second node parts, just increase the number of child nodes for it */
1742  num_child2++;
1743  }
1744  }
1745  else {
1746  num_child1++;
1747  }
1748  }
1749 
1750  /* ensure at least one child in each node */
1751  if (num_child2 == 0) {
1752  num_child2++;
1753  num_child1--;
1754  }
1755  else if (num_child1 == 0) {
1756  num_child1++;
1757  num_child2--;
1758  }
1759 
1760  /* at this point, faces should have been split along the array range sequentially,
1761  * each sequential part belonging to one node only */
1762  BLI_assert((num_child1 + num_child2) == node->totface);
1763 
1764  node->child1 = child1 = BLI_memarena_alloc(arena, sizeof(struct FastNodeBuildInfo));
1765  node->child2 = child2 = BLI_memarena_alloc(arena, sizeof(struct FastNodeBuildInfo));
1766 
1767  child1->totface = num_child1;
1768  child1->start = node->start;
1769  child2->totface = num_child2;
1770  child2->start = node->start + num_child1;
1772 
1773  pbvh_bmesh_node_limit_ensure_fast(pbvh, nodeinfo, bbc_array, child1, arena);
1774  pbvh_bmesh_node_limit_ensure_fast(pbvh, nodeinfo, bbc_array, child2, arena);
1775 }
1776 
1778  PBVH *pbvh, BMFace **nodeinfo, BBC *bbc_array, struct FastNodeBuildInfo *node, int node_index)
1779 {
1780  PBVHNode *n = pbvh->nodes + node_index;
1781  /* two cases, node does not have children or does have children */
1782  if (node->child1) {
1783  int children_offset = pbvh->totnode;
1784 
1785  n->children_offset = children_offset;
1786  pbvh_grow_nodes(pbvh, pbvh->totnode + 2);
1788  pbvh, nodeinfo, bbc_array, node->child1, children_offset);
1790  pbvh, nodeinfo, bbc_array, node->child2, children_offset + 1);
1791 
1792  n = &pbvh->nodes[node_index];
1793 
1794  /* Update bounding box */
1795  BB_reset(&n->vb);
1796  BB_expand_with_bb(&n->vb, &pbvh->nodes[n->children_offset].vb);
1797  BB_expand_with_bb(&n->vb, &pbvh->nodes[n->children_offset + 1].vb);
1798  n->orig_vb = n->vb;
1799  }
1800  else {
1801  /* node does not have children so it's a leaf node, populate with faces and tag accordingly
1802  * this is an expensive part but it's not so easily thread-able due to vertex node indices */
1803  const int cd_vert_node_offset = pbvh->cd_vert_node_offset;
1804  const int cd_face_node_offset = pbvh->cd_face_node_offset;
1805 
1806  bool has_visible = false;
1807 
1808  n->flag = PBVH_Leaf;
1809  n->bm_faces = BLI_gset_ptr_new_ex("bm_faces", node->totface);
1810 
1811  /* Create vert hash sets */
1812  n->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts");
1813  n->bm_other_verts = BLI_gset_ptr_new("bm_other_verts");
1814 
1815  BB_reset(&n->vb);
1816 
1817  const int end = node->start + node->totface;
1818 
1819  for (int i = node->start; i < end; i++) {
1820  BMFace *f = nodeinfo[i];
1821  BBC *bbc = &bbc_array[BM_elem_index_get(f)];
1822 
1823  /* Update ownership of faces */
1824  BLI_gset_insert(n->bm_faces, f);
1825  BM_ELEM_CD_SET_INT(f, cd_face_node_offset, node_index);
1826 
1827  /* Update vertices */
1828  BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
1829  BMLoop *l_iter = l_first;
1830  do {
1831  BMVert *v = l_iter->v;
1832  if (!BLI_gset_haskey(n->bm_unique_verts, v)) {
1833  if (BM_ELEM_CD_GET_INT(v, cd_vert_node_offset) != DYNTOPO_NODE_NONE) {
1835  }
1836  else {
1838  BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, node_index);
1839  }
1840  }
1841  /* Update node bounding box */
1842  } while ((l_iter = l_iter->next) != l_first);
1843 
1844  if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
1845  has_visible = true;
1846  }
1847 
1848  BB_expand_with_bb(&n->vb, (BB *)bbc);
1849  }
1850 
1851  BLI_assert(n->vb.bmin[0] <= n->vb.bmax[0] && n->vb.bmin[1] <= n->vb.bmax[1] &&
1852  n->vb.bmin[2] <= n->vb.bmax[2]);
1853 
1854  n->orig_vb = n->vb;
1855 
1856  /* Build GPU buffers for new node and update vertex normals */
1858 
1859  BKE_pbvh_node_fully_hidden_set(n, !has_visible);
1860  n->flag |= PBVH_UpdateNormals;
1861  }
1862 }
1863 
1864 /***************************** Public API *****************************/
1865 
1867  BMesh *bm,
1868  bool smooth_shading,
1869  BMLog *log,
1870  const int cd_vert_node_offset,
1871  const int cd_face_node_offset)
1872 {
1873  pbvh->cd_vert_node_offset = cd_vert_node_offset;
1874  pbvh->cd_face_node_offset = cd_face_node_offset;
1875  pbvh->bm = bm;
1876 
1877  BKE_pbvh_bmesh_detail_size_set(pbvh, 0.75);
1878 
1879  pbvh->type = PBVH_BMESH;
1880  pbvh->bm_log = log;
1881 
1882  /* TODO: choose leaf limit better */
1883  pbvh->leaf_limit = 100;
1884 
1885  if (smooth_shading) {
1887  }
1888 
1889  /* bounding box array of all faces, no need to recalculate every time */
1890  BBC *bbc_array = MEM_mallocN(sizeof(BBC) * bm->totface, "BBC");
1891  BMFace **nodeinfo = MEM_mallocN(sizeof(*nodeinfo) * bm->totface, "nodeinfo");
1892  MemArena *arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, "fast PBVH node storage");
1893 
1894  BMIter iter;
1895  BMFace *f;
1896  int i;
1897  BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
1898  BBC *bbc = &bbc_array[i];
1899  BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
1900  BMLoop *l_iter = l_first;
1901 
1902  BB_reset((BB *)bbc);
1903  do {
1904  BB_expand((BB *)bbc, l_iter->v->co);
1905  } while ((l_iter = l_iter->next) != l_first);
1906  BBC_update_centroid(bbc);
1907 
1908  /* so we can do direct lookups on 'bbc_array' */
1909  BM_elem_index_set(f, i); /* set_dirty! */
1910  nodeinfo[i] = f;
1911  BM_ELEM_CD_SET_INT(f, cd_face_node_offset, DYNTOPO_NODE_NONE);
1912  }
1913  /* Likely this is already dirty. */
1915 
1916  BMVert *v;
1917  BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1918  BM_ELEM_CD_SET_INT(v, cd_vert_node_offset, DYNTOPO_NODE_NONE);
1919  }
1920 
1921  /* setup root node */
1922  struct FastNodeBuildInfo rootnode = {0};
1923  rootnode.totface = bm->totface;
1924 
1925  /* start recursion, assign faces to nodes accordingly */
1926  pbvh_bmesh_node_limit_ensure_fast(pbvh, nodeinfo, bbc_array, &rootnode, arena);
1927 
1928  /* We now have all faces assigned to a node,
1929  * next we need to assign those to the gsets of the nodes. */
1930 
1931  /* Start with all faces in the root node */
1932  pbvh->nodes = MEM_callocN(sizeof(PBVHNode), "PBVHNode");
1933  pbvh->totnode = 1;
1934 
1935  /* take root node and visit and populate children recursively */
1936  pbvh_bmesh_create_nodes_fast_recursive(pbvh, nodeinfo, bbc_array, &rootnode, 0);
1937 
1938  BLI_memarena_free(arena);
1939  MEM_freeN(bbc_array);
1940  MEM_freeN(nodeinfo);
1941 }
1942 
1945  const float center[3],
1946  const float view_normal[3],
1947  float radius,
1948  const bool use_frontface,
1949  const bool use_projected)
1950 {
1951  /* 2 is enough for edge faces - manifold edge */
1952  BLI_buffer_declare_static(BMLoop *, edge_loops, BLI_BUFFER_NOP, 2);
1953  BLI_buffer_declare_static(BMFace *, deleted_faces, BLI_BUFFER_NOP, 32);
1954  const int cd_vert_mask_offset = CustomData_get_offset(&pbvh->bm->vdata, CD_PAINT_MASK);
1955  const int cd_vert_node_offset = pbvh->cd_vert_node_offset;
1956  const int cd_face_node_offset = pbvh->cd_face_node_offset;
1957 
1958  bool modified = false;
1959 
1960  if (view_normal) {
1961  BLI_assert(len_squared_v3(view_normal) != 0.0f);
1962  }
1963 
1964  if (mode & PBVH_Collapse) {
1965  EdgeQueue q;
1966  BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *) * 2, 0, 128, BLI_MEMPOOL_NOP);
1967  EdgeQueueContext eq_ctx = {
1968  &q,
1969  queue_pool,
1970  pbvh->bm,
1971  cd_vert_mask_offset,
1972  cd_vert_node_offset,
1973  cd_face_node_offset,
1974  };
1975 
1977  &eq_ctx, pbvh, center, view_normal, radius, use_frontface, use_projected);
1978  modified |= pbvh_bmesh_collapse_short_edges(&eq_ctx, pbvh, &deleted_faces);
1980  BLI_mempool_destroy(queue_pool);
1981  }
1982 
1983  if (mode & PBVH_Subdivide) {
1984  EdgeQueue q;
1985  BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *) * 2, 0, 128, BLI_MEMPOOL_NOP);
1986  EdgeQueueContext eq_ctx = {
1987  &q,
1988  queue_pool,
1989  pbvh->bm,
1990  cd_vert_mask_offset,
1991  cd_vert_node_offset,
1992  cd_face_node_offset,
1993  };
1994 
1996  &eq_ctx, pbvh, center, view_normal, radius, use_frontface, use_projected);
1997  modified |= pbvh_bmesh_subdivide_long_edges(&eq_ctx, pbvh, &edge_loops);
1999  BLI_mempool_destroy(queue_pool);
2000  }
2001 
2002  /* Unmark nodes */
2003  for (int n = 0; n < pbvh->totnode; n++) {
2004  PBVHNode *node = &pbvh->nodes[n];
2005 
2006  if (node->flag & PBVH_Leaf && node->flag & PBVH_UpdateTopology) {
2007  node->flag &= ~PBVH_UpdateTopology;
2008  }
2009  }
2010  BLI_buffer_free(&edge_loops);
2011  BLI_buffer_free(&deleted_faces);
2012 
2013 #ifdef USE_VERIFY
2014  pbvh_bmesh_verify(pbvh);
2015 #endif
2016 
2017  return modified;
2018 }
2019 
2021 {
2022  /* Skip if original coords/triangles are already saved */
2023  if (node->bm_orco) {
2024  return;
2025  }
2026 
2027  const int totvert = BLI_gset_len(node->bm_unique_verts) + BLI_gset_len(node->bm_other_verts);
2028 
2029  const int tottri = BLI_gset_len(node->bm_faces);
2030 
2031  node->bm_orco = MEM_mallocN(sizeof(*node->bm_orco) * totvert, __func__);
2032  node->bm_ortri = MEM_mallocN(sizeof(*node->bm_ortri) * tottri, __func__);
2033 
2034  /* Copy out the vertices and assign a temporary index */
2035  int i = 0;
2036  GSetIterator gs_iter;
2037  GSET_ITER (gs_iter, node->bm_unique_verts) {
2038  BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
2039  copy_v3_v3(node->bm_orco[i], v->co);
2040  BM_elem_index_set(v, i); /* set_dirty! */
2041  i++;
2042  }
2043  GSET_ITER (gs_iter, node->bm_other_verts) {
2044  BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
2045  copy_v3_v3(node->bm_orco[i], v->co);
2046  BM_elem_index_set(v, i); /* set_dirty! */
2047  i++;
2048  }
2049  /* Likely this is already dirty. */
2051 
2052  /* Copy the triangles */
2053  i = 0;
2054  GSET_ITER (gs_iter, node->bm_faces) {
2055  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
2056 
2058  continue;
2059  }
2060 
2061 #if 0
2062  BMIter bm_iter;
2063  BMVert *v;
2064  int j = 0;
2065  BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) {
2066  node->bm_ortri[i][j] = BM_elem_index_get(v);
2067  j++;
2068  }
2069 #else
2070  bm_face_as_array_index_tri(f, node->bm_ortri[i]);
2071 #endif
2072  i++;
2073  }
2074  node->bm_tot_ortri = i;
2075 }
2076 
2078 {
2079  for (int i = 0; i < pbvh->totnode; i++) {
2080  PBVHNode *n = &pbvh->nodes[i];
2081  if (n->flag & PBVH_Leaf) {
2082  /* Free orco/ortri data */
2084 
2085  /* Recursively split nodes that have gotten too many
2086  * elements */
2088  }
2089  }
2090 }
2091 
2092 void BKE_pbvh_bmesh_detail_size_set(PBVH *pbvh, float detail_size)
2093 {
2094  pbvh->bm_max_edge_len = detail_size;
2095  pbvh->bm_min_edge_len = pbvh->bm_max_edge_len * 0.4f;
2096 }
2097 
2099 {
2100  node->flag |= PBVH_UpdateTopology;
2101 }
2102 
2104 {
2105  return node->bm_unique_verts;
2106 }
2107 
2109 {
2110  return node->bm_other_verts;
2111 }
2112 
2114 {
2115  return node->bm_faces;
2116 }
2117 
2118 /****************************** Debugging *****************************/
2119 
2120 #if 0
2121 
2122 static void pbvh_bmesh_print(PBVH *pbvh)
2123 {
2124  fprintf(stderr, "\npbvh=%p\n", pbvh);
2125  fprintf(stderr, "bm_face_to_node:\n");
2126 
2127  BMIter iter;
2128  BMFace *f;
2129  BM_ITER_MESH (f, &iter, pbvh->bm, BM_FACES_OF_MESH) {
2130  fprintf(stderr, " %d -> %d\n", BM_elem_index_get(f), pbvh_bmesh_node_index_from_face(pbvh, f));
2131  }
2132 
2133  fprintf(stderr, "bm_vert_to_node:\n");
2134  BMVert *v;
2135  BM_ITER_MESH (v, &iter, pbvh->bm, BM_FACES_OF_MESH) {
2136  fprintf(stderr, " %d -> %d\n", BM_elem_index_get(v), pbvh_bmesh_node_index_from_vert(pbvh, v));
2137  }
2138 
2139  for (int n = 0; n < pbvh->totnode; n++) {
2140  PBVHNode *node = &pbvh->nodes[n];
2141  if (!(node->flag & PBVH_Leaf)) {
2142  continue;
2143  }
2144 
2145  GSetIterator gs_iter;
2146  fprintf(stderr, "node %d\n faces:\n", n);
2147  GSET_ITER (gs_iter, node->bm_faces)
2148  fprintf(stderr, " %d\n", BM_elem_index_get((BMFace *)BLI_gsetIterator_getKey(&gs_iter)));
2149  fprintf(stderr, " unique verts:\n");
2150  GSET_ITER (gs_iter, node->bm_unique_verts)
2151  fprintf(stderr, " %d\n", BM_elem_index_get((BMVert *)BLI_gsetIterator_getKey(&gs_iter)));
2152  fprintf(stderr, " other verts:\n");
2153  GSET_ITER (gs_iter, node->bm_other_verts)
2154  fprintf(stderr, " %d\n", BM_elem_index_get((BMVert *)BLI_gsetIterator_getKey(&gs_iter)));
2155  }
2156 }
2157 
2158 static void print_flag_factors(int flag)
2159 {
2160  printf("flag=0x%x:\n", flag);
2161  for (int i = 0; i < 32; i++) {
2162  if (flag & (1 << i)) {
2163  printf(" %d (1 << %d)\n", 1 << i, i);
2164  }
2165  }
2166 }
2167 #endif
2168 
2169 #ifdef USE_VERIFY
2170 
2171 static void pbvh_bmesh_verify(PBVH *pbvh)
2172 {
2173  /* build list of faces & verts to lookup */
2174  GSet *faces_all = BLI_gset_ptr_new_ex(__func__, pbvh->bm->totface);
2175  BMIter iter;
2176 
2177  {
2178  BMFace *f;
2179  BM_ITER_MESH (f, &iter, pbvh->bm, BM_FACES_OF_MESH) {
2181  BLI_gset_insert(faces_all, f);
2182  }
2183  }
2184 
2185  GSet *verts_all = BLI_gset_ptr_new_ex(__func__, pbvh->bm->totvert);
2186  {
2187  BMVert *v;
2188  BM_ITER_MESH (v, &iter, pbvh->bm, BM_VERTS_OF_MESH) {
2190  BLI_gset_insert(verts_all, v);
2191  }
2192  }
2193  }
2194 
2195  /* Check vert/face counts */
2196  {
2197  int totface = 0, totvert = 0;
2198  for (int i = 0; i < pbvh->totnode; i++) {
2199  PBVHNode *n = &pbvh->nodes[i];
2200  totface += n->bm_faces ? BLI_gset_len(n->bm_faces) : 0;
2201  totvert += n->bm_unique_verts ? BLI_gset_len(n->bm_unique_verts) : 0;
2202  }
2203 
2204  BLI_assert(totface == BLI_gset_len(faces_all));
2205  BLI_assert(totvert == BLI_gset_len(verts_all));
2206  }
2207 
2208  {
2209  BMFace *f;
2210  BM_ITER_MESH (f, &iter, pbvh->bm, BM_FACES_OF_MESH) {
2211  BMIter bm_iter;
2212  BMVert *v;
2213  PBVHNode *n = pbvh_bmesh_node_lookup(pbvh, f);
2214 
2215  /* Check that the face's node is a leaf */
2216  BLI_assert(n->flag & PBVH_Leaf);
2217 
2218  /* Check that the face's node knows it owns the face */
2220 
2221  /* Check the face's vertices... */
2222  BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) {
2223  PBVHNode *nv;
2224 
2225  /* Check that the vertex is in the node */
2227 
2228  /* Check that the vertex has a node owner */
2229  nv = pbvh_bmesh_node_lookup(pbvh, v);
2230 
2231  /* Check that the vertex's node knows it owns the vert */
2233 
2234  /* Check that the vertex isn't duplicated as an 'other' vert */
2236  }
2237  }
2238  }
2239 
2240  /* Check verts */
2241  {
2242  BMVert *v;
2243  BM_ITER_MESH (v, &iter, pbvh->bm, BM_VERTS_OF_MESH) {
2244  /* vertex isn't tracked */
2246  continue;
2247  }
2248 
2249  PBVHNode *n = pbvh_bmesh_node_lookup(pbvh, v);
2250 
2251  /* Check that the vert's node is a leaf */
2252  BLI_assert(n->flag & PBVH_Leaf);
2253 
2254  /* Check that the vert's node knows it owns the vert */
2256 
2257  /* Check that the vertex isn't duplicated as an 'other' vert */
2259 
2260  /* Check that the vert's node also contains one of the vert's
2261  * adjacent faces */
2262  bool found = false;
2263  BMIter bm_iter;
2264  BMFace *f = NULL;
2265  BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
2266  if (pbvh_bmesh_node_lookup(pbvh, f) == n) {
2267  found = true;
2268  break;
2269  }
2270  }
2271  BLI_assert(found || f == NULL);
2272 
2273 # if 1
2274  /* total freak stuff, check if node exists somewhere else */
2275  /* Slow */
2276  for (int i = 0; i < pbvh->totnode; i++) {
2277  PBVHNode *n_other = &pbvh->nodes[i];
2278  if ((n != n_other) && (n_other->bm_unique_verts)) {
2280  }
2281  }
2282 # endif
2283  }
2284  }
2285 
2286 # if 0
2287  /* check that every vert belongs somewhere */
2288  /* Slow */
2289  BM_ITER_MESH (vi, &iter, pbvh->bm, BM_VERTS_OF_MESH) {
2290  bool has_unique = false;
2291  for (int i = 0; i < pbvh->totnode; i++) {
2292  PBVHNode *n = &pbvh->nodes[i];
2293  if ((n->bm_unique_verts != NULL) && BLI_gset_haskey(n->bm_unique_verts, vi)) {
2294  has_unique = true;
2295  }
2296  }
2297  BLI_assert(has_unique);
2298  vert_count++;
2299  }
2300 
2301  /* If totvert differs from number of verts inside the hash. hash-totvert is checked above. */
2302  BLI_assert(vert_count == pbvh->bm->totvert);
2303 # endif
2304 
2305  /* Check that node elements are recorded in the top level */
2306  for (int i = 0; i < pbvh->totnode; i++) {
2307  PBVHNode *n = &pbvh->nodes[i];
2308  if (n->flag & PBVH_Leaf) {
2309  GSetIterator gs_iter;
2310 
2311  GSET_ITER (gs_iter, n->bm_faces) {
2312  BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
2313  PBVHNode *n_other = pbvh_bmesh_node_lookup(pbvh, f);
2314  BLI_assert(n == n_other);
2315  BLI_assert(BLI_gset_haskey(faces_all, f));
2316  }
2317 
2318  GSET_ITER (gs_iter, n->bm_unique_verts) {
2319  BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
2320  PBVHNode *n_other = pbvh_bmesh_node_lookup(pbvh, v);
2322  BLI_assert(n == n_other);
2323  BLI_assert(BLI_gset_haskey(verts_all, v));
2324  }
2325 
2326  GSET_ITER (gs_iter, n->bm_other_verts) {
2327  BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
2328  /* this happens sometimes and seems harmless */
2329  // BLI_assert(!BM_vert_face_check(v));
2330  BLI_assert(BLI_gset_haskey(verts_all, v));
2331  }
2332  }
2333  }
2334 
2335  BLI_gset_free(faces_all, NULL);
2336  BLI_gset_free(verts_all, NULL);
2337 }
2338 
2339 #endif
void CustomData_bmesh_set_default(struct CustomData *data, void **block)
Definition: customdata.cc:3756
int CustomData_get_offset(const struct CustomData *data, int type)
A BVH for high poly meshes.
void BKE_pbvh_node_mark_rebuild_draw(PBVHNode *node)
Definition: pbvh.c:1901
PBVHTopologyUpdateMode
Definition: BKE_pbvh.h:278
@ PBVH_Collapse
Definition: BKE_pbvh.h:280
@ PBVH_Subdivide
Definition: BKE_pbvh.h:279
@ PBVH_BMESH
Definition: BKE_pbvh.h:236
void BKE_pbvh_node_fully_hidden_set(PBVHNode *node, int fully_hidden)
Definition: pbvh.c:1916
@ PBVH_UpdateDrawBuffers
Definition: BKE_pbvh.h:69
@ PBVH_UpdateNormals
Definition: BKE_pbvh.h:66
@ PBVH_UpdateTopology
Definition: BKE_pbvh.h:79
@ PBVH_FullyHidden
Definition: BKE_pbvh.h:75
@ PBVH_UpdateBB
Definition: BKE_pbvh.h:67
@ PBVH_Leaf
Definition: BKE_pbvh.h:64
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_buffer_append(buffer_, type_, val_)
Definition: BLI_buffer.h:50
void BLI_buffer_reinit(BLI_Buffer *buffer, size_t new_count)
Definition: buffer.c:75
@ BLI_BUFFER_NOP
Definition: BLI_buffer.h:21
#define BLI_buffer_at(buffer_, type_, index_)
Definition: BLI_buffer.h:36
#define BLI_buffer_declare_static(type_, name_, flag_, static_count_)
Definition: BLI_buffer.h:25
#define BLI_buffer_clear(buffer_)
Definition: BLI_buffer.h:54
#define BLI_buffer_free(name_)
Definition: BLI_buffer.h:94
#define BLI_INLINE
#define GSET_ITER_INDEX(gs_iter_, gset_, i_)
Definition: BLI_ghash.h:475
struct GSet GSet
Definition: BLI_ghash.h:340
bool BLI_gset_haskey(const GSet *gs, const void *key) ATTR_WARN_UNUSED_RESULT
Definition: BLI_ghash.c:1007
GSet * BLI_gset_ptr_new(const char *info)
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
GSet * BLI_gset_ptr_new_ex(const char *info, unsigned int nentries_reserve) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
#define GSET_ITER(gs_iter_, gset_)
Definition: BLI_ghash.h:471
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
BLI_INLINE void * BLI_gsetIterator_getKey(GSetIterator *gsi)
Definition: BLI_ghash.h:458
bool BLI_gset_add(GSet *gs, void *key)
Definition: BLI_ghash.c:969
bool BLI_gset_remove(GSet *gs, const void *key, GSetKeyFreeFP keyfreefp)
Definition: BLI_ghash.c:1002
A min-heap / priority queue ADT.
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
HeapSimple * BLI_heapsimple_new(void) ATTR_WARN_UNUSED_RESULT
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
MINLINE float max_fff(float a, float b, float c)
MINLINE float max_ff(float a, float b)
MINLINE float square_f(float a)
void closest_on_tri_to_point_v3(float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:980
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
Definition: math_geom.c:33
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
MINLINE float normalize_v3(float r[3])
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void copy_v3_v3(float r[3], const float a[3])
void project_plane_normalized_v3_v3v3(float out[3], const float p[3], const float v_plane[3])
Definition: math_vector.c:652
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void mid_v3_v3v3(float r[3], const float a[3], const float b[3])
Definition: math_vector.c:237
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
MINLINE void add_v3_v3(float r[3], const float a[3])
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
Definition: BLI_memarena.c:94
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
Definition: BLI_memarena.c:64
#define BLI_MEMARENA_STD_BUFSIZE
Definition: BLI_memarena.h:20
void * BLI_memarena_alloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
Definition: BLI_memarena.c:116
@ 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
#define ARRAY_SIZE(arr)
#define UNUSED_VARS(...)
#define UNLIKELY(x)
#define ELEM(...)
#define LIKELY(x)
@ CD_PAINT_MASK
#define DYNTOPO_NODE_NONE
NSNotificationCenter * center
_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 GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble u2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLdouble GLdouble v2 _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLdouble GLdouble nz _GL_VOID_RET _GL_VOID GLfloat GLfloat nz _GL_VOID_RET _GL_VOID GLint GLint nz _GL_VOID_RET _GL_VOID GLshort GLshort nz _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const GLfloat *values _GL_VOID_RET _GL_VOID GLsizei const GLushort *values _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID const GLuint const GLclampf *priorities _GL_VOID_RET _GL_VOID GLdouble y _GL_VOID_RET _GL_VOID GLfloat y _GL_VOID_RET _GL_VOID GLint y _GL_VOID_RET _GL_VOID GLshort y _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLfloat GLfloat z _GL_VOID_RET _GL_VOID GLint GLint z _GL_VOID_RET _GL_VOID GLshort GLshort z _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble w _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat w _GL_VOID_RET _GL_VOID GLint GLint GLint w _GL_VOID_RET _GL_VOID GLshort GLshort GLshort w _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble y2 _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat y2 _GL_VOID_RET _GL_VOID GLint GLint GLint y2 _GL_VOID_RET _GL_VOID GLshort GLshort GLshort y2 _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLdouble GLdouble z _GL_VOID_RET _GL_VOID GLuint *buffer _GL_VOID_RET _GL_VOID GLdouble t _GL_VOID_RET _GL_VOID GLfloat t _GL_VOID_RET _GL_VOID GLint t _GL_VOID_RET _GL_VOID GLshort t _GL_VOID_RET _GL_VOID GLdouble t
_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 BM_ELEM_CD_SET_FLOAT(ele, offset, f)
Definition: bmesh_class.h:545
#define BM_ELEM_CD_GET_FLOAT(ele, offset)
Definition: bmesh_class.h:553
#define BM_ELEM_CD_GET_INT(ele, offset)
Definition: bmesh_class.h:518
#define BM_ELEM_CD_SET_INT(ele, offset, f)
Definition: bmesh_class.h:510
#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_ELEM_HIDDEN
Definition: bmesh_class.h:472
BMVert * BM_vert_create(BMesh *bm, const float co[3], const BMVert *v_example, const eBMCreateFlag create_flag)
Main function for creating a new vertex.
Definition: bmesh_core.c:41
void BM_vert_kill(BMesh *bm, BMVert *v)
Definition: bmesh_core.c:939
void BM_face_kill(BMesh *bm, BMFace *f)
Definition: bmesh_core.c:828
void BM_edge_kill(BMesh *bm, BMEdge *e)
Definition: bmesh_core.c:927
BMFace * BM_face_create(BMesh *bm, BMVert **verts, BMEdge **edges, const int len, const BMFace *f_example, const eBMCreateFlag create_flag)
Definition: bmesh_core.c:395
BMEdge * BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *e_example, const eBMCreateFlag create_flag)
Main function for creating a new edge.
Definition: bmesh_core.c:123
@ BM_CREATE_NOP
Definition: bmesh_core.h:12
@ BM_CREATE_SKIP_CD
Definition: bmesh_core.h:20
@ BM_CREATE_NO_DOUBLE
Definition: bmesh_core.h:14
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_elem_index_set(ele, index)
Definition: bmesh_inline.h:111
#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
int BM_iter_as_array(BMesh *bm, const char itype, void *data, void **array, const int len)
Iterator as Array.
#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_VERTS_OF_MESH
@ BM_VERTS_OF_FACE
@ BM_FACES_OF_MESH
@ BM_LOOPS_OF_EDGE
@ BM_EDGES_OF_VERT
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_log_face_added(BMLog *log, BMFace *f)
Definition: bmesh_log.c:807
void BM_log_face_removed(BMLog *log, BMFace *f)
Definition: bmesh_log.c:849
void BM_log_vert_added(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
Definition: bmesh_log.c:786
void BM_log_vert_removed(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
Definition: bmesh_log.c:821
void BM_log_vert_before_modified(BMLog *log, BMVert *v, const int cd_vert_mask_offset)
Definition: bmesh_log.c:768
void BM_vert_normal_update(BMVert *v)
void BM_face_normal_update(BMFace *f)
void BM_face_as_array_vert_tri(BMFace *f, BMVert *r_verts[3])
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
Definition: bmesh_query.c:1553
bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
Definition: bmesh_query.c:553
float BM_edge_calc_length_squared(const BMEdge *e)
Definition: bmesh_query.c:533
int BM_edge_face_count(const BMEdge *e)
Definition: bmesh_query.c:629
BMFace * BM_face_exists(BMVert **varr, int len)
Definition: bmesh_query.c:1612
bool BM_vert_face_check(const BMVert *v)
Definition: bmesh_query.c:674
#define BM_vert_face_count_is_equal(v, n)
Definition: bmesh_query.h:255
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
#define BM_vert_edge_count_is_over(v, n)
Definition: bmesh_query.h:240
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
OperationNode * node
SyclQueue void void size_t num_bytes void
static float verts[][3]
int count
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
ccl_device_inline float3 log(float3 v)
Definition: math_float3.h:397
#define G(x, y, z)
#define sqrtf(x)
Definition: metal/compat.h:243
static unsigned c
Definition: RandGen.cpp:83
bool ray_face_nearest_tri(const float ray_start[3], const float ray_normal[3], const float t0[3], const float t1[3], const float t2[3], float *depth, float *dist_sq)
Definition: pbvh.c:2274
void BB_expand_with_bb(BB *bb, BB *bb2)
Definition: pbvh.c:77
int BB_widest_axis(const BB *bb)
Definition: pbvh.c:85
void pbvh_grow_nodes(PBVH *pbvh, int totnode)
Definition: pbvh.c:224
bool ray_face_intersection_tri(const float ray_start[3], struct IsectRayPrecalc *isect_precalc, const float t0[3], const float t1[3], const float t2[3], float *depth)
Definition: pbvh.c:2205
void pbvh_free_draw_buffers(PBVH *pbvh, PBVHNode *node)
Definition: pbvh.c:1389
void BBC_update_centroid(BBC *bbc)
Definition: pbvh.c:108
void BB_reset(BB *bb)
Definition: pbvh.c:63
void BB_expand(BB *bb, const float co[3])
Definition: pbvh.c:69
BLI_INLINE int pbvh_bmesh_node_index_from_vert(PBVH *pbvh, const BMVert *key)
Definition: pbvh_bmesh.c:450
BLI_INLINE int pbvh_bmesh_node_index_from_face(PBVH *pbvh, const BMFace *key)
Definition: pbvh_bmesh.c:458
#define BM_LOOPS_OF_VERT_ITER_END
Definition: pbvh_bmesh.c:82
#define BM_FACES_OF_VERT_ITER_BEGIN(f_iter_, v_)
Definition: pbvh_bmesh.c:95
void BKE_pbvh_bmesh_node_save_orig(BMesh *bm, PBVHNode *node)
Definition: pbvh_bmesh.c:2020
static void long_edge_queue_edge_add_recursive(EdgeQueueContext *eq_ctx, BMLoop *l_edge, BMLoop *l_end, const float len_sq, float limit_len)
Definition: pbvh_bmesh.c:861
static bool pbvh_bmesh_node_limit_ensure(PBVH *pbvh, int node_index)
Definition: pbvh_bmesh.c:370
static void edge_queue_insert(EdgeQueueContext *eq_ctx, BMEdge *e, float priority)
Definition: pbvh_bmesh.c:824
static void pbvh_bmesh_collapse_edge(PBVH *pbvh, BMEdge *e, BMVert *v1, BMVert *v2, GHash *deleted_verts, BLI_Buffer *deleted_faces, EdgeQueueContext *eq_ctx)
Definition: pbvh_bmesh.c:1276
#define BM_LOOPS_OF_VERT_ITER_BEGIN(l_iter_radial_, v_)
Definition: pbvh_bmesh.c:65
static BMFace * bm_face_exists_tri_from_loop_vert(BMLoop *l_radial_first, BMVert *v_opposite)
Definition: pbvh_bmesh.c:144
bool pbvh_bmesh_node_nearest_to_ray(PBVHNode *node, const float ray_start[3], const float ray_normal[3], float *depth, float *dist_sq, bool use_original)
Definition: pbvh_bmesh.c:1606
static void pbvh_bmesh_node_split(PBVH *pbvh, const BBC *bbc_array, int node_index)
Definition: pbvh_bmesh.c:245
GSet * BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node)
Definition: pbvh_bmesh.c:2103
static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx, PBVH *pbvh, BMEdge *e, BLI_Buffer *edge_loops)
Definition: pbvh_bmesh.c:1105
GSet * BKE_pbvh_bmesh_node_other_verts(PBVHNode *node)
Definition: pbvh_bmesh.c:2108
BLI_INLINE PBVHNode * pbvh_bmesh_node_from_face(PBVH *pbvh, const BMFace *key)
Definition: pbvh_bmesh.c:471
static void long_edge_queue_face_add(EdgeQueueContext *eq_ctx, BMFace *f)
Definition: pbvh_bmesh.c:931
static void pbvh_bmesh_node_limit_ensure_fast(PBVH *pbvh, BMFace **nodeinfo, BBC *bbc_array, struct FastNodeBuildInfo *node, MemArena *arena)
Definition: pbvh_bmesh.c:1682
static bool pbvh_bmesh_collapse_short_edges(EdgeQueueContext *eq_ctx, PBVH *pbvh, BLI_Buffer *deleted_faces)
Definition: pbvh_bmesh.c:1443
bool pbvh_bmesh_node_raycast(PBVHNode *node, const float ray_start[3], const float ray_normal[3], struct IsectRayPrecalc *isect_precalc, float *depth, bool use_original, int *r_active_vertex_index, float *r_face_normal)
Definition: pbvh_bmesh.c:1498
static void long_edge_queue_edge_add(EdgeQueueContext *eq_ctx, BMEdge *e)
Definition: pbvh_bmesh.c:847
static void pbvh_bmesh_edge_loops(BLI_Buffer *buf, BMEdge *e)
Definition: pbvh_bmesh.c:686
static void pbvh_bmesh_node_drop_orig(PBVHNode *node)
Definition: pbvh_bmesh.c:702
bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh, PBVHTopologyUpdateMode mode, const float center[3], const float view_normal[3], float radius, const bool use_frontface, const bool use_projected)
Definition: pbvh_bmesh.c:1943
#define EVEN_GENERATION_SCALE
static void long_edge_queue_create(EdgeQueueContext *eq_ctx, PBVH *pbvh, const float center[3], const float view_normal[3], float radius, const bool use_frontface, const bool use_projected)
Definition: pbvh_bmesh.c:990
static BMVert * bm_vert_hash_lookup_chain(GHash *deleted_verts, BMVert *v)
Definition: pbvh_bmesh.c:164
#define EVEN_EDGELEN_THRESHOLD
static void short_edge_queue_face_add(EdgeQueueContext *eq_ctx, BMFace *f)
Definition: pbvh_bmesh.c:959
BLI_INLINE PBVHNode * pbvh_bmesh_node_from_vert(PBVH *pbvh, const BMVert *key)
Definition: pbvh_bmesh.c:466
static void pbvh_bmesh_vert_ownership_transfer(PBVH *pbvh, PBVHNode *new_owner, BMVert *v)
Definition: pbvh_bmesh.c:593
void BKE_pbvh_build_bmesh(PBVH *pbvh, BMesh *bm, bool smooth_shading, BMLog *log, const int cd_vert_node_offset, const int cd_face_node_offset)
Definition: pbvh_bmesh.c:1866
static bool edge_queue_tri_in_sphere(const EdgeQueue *q, BMFace *f)
Definition: pbvh_bmesh.c:785
static BMFace * pbvh_bmesh_face_create(PBVH *pbvh, int node_index, BMVert *v_tri[3], BMEdge *e_tri[3], const BMFace *f_example)
Definition: pbvh_bmesh.c:507
static void pbvh_bmesh_face_remove(PBVH *pbvh, BMFace *f)
Definition: pbvh_bmesh.c:646
static void short_edge_queue_create(EdgeQueueContext *eq_ctx, PBVH *pbvh, const float center[3], const float view_normal[3], float radius, const bool use_frontface, const bool use_projected)
Definition: pbvh_bmesh.c:1053
static void pbvh_bmesh_create_nodes_fast_recursive(PBVH *pbvh, BMFace **nodeinfo, BBC *bbc_array, struct FastNodeBuildInfo *node, int node_index)
Definition: pbvh_bmesh.c:1777
static bool check_mask(EdgeQueueContext *eq_ctx, BMVert *v)
Definition: pbvh_bmesh.c:819
bool BKE_pbvh_bmesh_node_raycast_detail(PBVHNode *node, const float ray_start[3], struct IsectRayPrecalc *isect_precalc, float *depth, float *r_edge_length)
Definition: pbvh_bmesh.c:1560
struct EdgeQueue EdgeQueue
#define pbvh_bmesh_node_vert_use_count_is_equal(pbvh, node, v, n)
Definition: pbvh_bmesh.c:550
#define BM_FACES_OF_VERT_ITER_END
Definition: pbvh_bmesh.c:101
struct GSet * BKE_pbvh_bmesh_node_faces(PBVHNode *node)
Definition: pbvh_bmesh.c:2113
static bool edge_queue_tri_in_circle(const EdgeQueue *q, BMFace *f)
Definition: pbvh_bmesh.c:799
static void pbvh_bmesh_vert_remove(PBVH *pbvh, BMVert *v)
Definition: pbvh_bmesh.c:614
static void bm_edges_from_tri(BMesh *bm, BMVert *v_tri[3], BMEdge *e_tri[3])
Definition: pbvh_bmesh.c:107
#define EDGE_QUEUE_DISABLE(e)
Definition: pbvh_bmesh.c:751
#define EDGE_QUEUE_ENABLE(e)
Definition: pbvh_bmesh.c:749
void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode)
Definition: pbvh_bmesh.c:1647
void BKE_pbvh_bmesh_after_stroke(PBVH *pbvh)
Definition: pbvh_bmesh.c:2077
static PBVHNode * pbvh_bmesh_vert_other_node_find(PBVH *pbvh, BMVert *v)
Definition: pbvh_bmesh.c:576
static void pbvh_bmesh_node_finalize(PBVH *pbvh, const int node_index, const int cd_vert_node_offset, const int cd_face_node_offset)
Definition: pbvh_bmesh.c:187
#define EDGE_QUEUE_TEST(e)
Definition: pbvh_bmesh.c:748
static int pbvh_bmesh_node_vert_use_count_at_most(PBVH *pbvh, PBVHNode *node, BMVert *v, const int count_max)
Definition: pbvh_bmesh.c:553
static void short_edge_queue_edge_add(EdgeQueueContext *eq_ctx, BMEdge *e)
Definition: pbvh_bmesh.c:918
void BKE_pbvh_bmesh_detail_size_set(PBVH *pbvh, float detail_size)
Definition: pbvh_bmesh.c:2092
void BKE_pbvh_node_mark_topology_update(PBVHNode *node)
Definition: pbvh_bmesh.c:2098
static BMVert * pbvh_bmesh_vert_create(PBVH *pbvh, int node_index, const float co[3], const float no[3], const int cd_vert_mask_offset)
Definition: pbvh_bmesh.c:476
BLI_INLINE void bm_face_as_array_index_tri(BMFace *f, int r_index[3])
Definition: pbvh_bmesh.c:114
static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx, PBVH *pbvh, BLI_Buffer *edge_loops)
Definition: pbvh_bmesh.c:1223
@ PBVH_DYNTOPO_SMOOTH_SHADING
Definition: pbvh_intern.h:128
float bcentroid[3]
Definition: pbvh_intern.h:27
Definition: pbvh_intern.h:21
float bmax[3]
Definition: pbvh_intern.h:22
float bmin[3]
Definition: pbvh_intern.h:22
void * data
Definition: BLI_buffer.h:14
size_t alloc_count
Definition: BLI_buffer.h:16
size_t count
Definition: BLI_buffer.h:16
BMHeader head
Definition: bmesh_class.h:243
int len
Definition: bmesh_class.h:267
BMHeader head
Definition: bmesh_class.h:255
float no[3]
Definition: bmesh_class.h:271
char htype
Definition: bmesh_class.h:64
char hflag
Definition: bmesh_class.h:66
void * data
Definition: bmesh_class.h:51
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
float co[3]
Definition: bmesh_class.h:87
float no[3]
Definition: bmesh_class.h:88
BMHeader head
Definition: bmesh_class.h:85
int totvert
Definition: bmesh_class.h:297
char elem_index_dirty
Definition: bmesh_class.h:305
CustomData vdata
Definition: bmesh_class.h:337
int totface
Definition: bmesh_class.h:297
BLI_mempool * pool
Definition: pbvh_bmesh.c:739
EdgeQueue * q
Definition: pbvh_bmesh.c:738
unsigned int use_view_normal
Definition: pbvh_bmesh.c:733
bool(* edge_queue_tri_in_range)(const struct EdgeQueue *q, BMFace *f)
Definition: pbvh_bmesh.c:729
const float * view_normal
Definition: pbvh_bmesh.c:731
const float * center
Definition: pbvh_bmesh.c:721
float radius_squared
Definition: pbvh_bmesh.c:723
float limit_len
Definition: pbvh_bmesh.c:726
float center_proj[3]
Definition: pbvh_bmesh.c:722
float limit_len_squared
Definition: pbvh_bmesh.c:724
HeapSimple * heap
Definition: pbvh_bmesh.c:720
struct FastNodeBuildInfo * child2
Definition: pbvh_bmesh.c:1674
struct FastNodeBuildInfo * child1
Definition: pbvh_bmesh.c:1673
GSet * bm_faces
Definition: pbvh_intern.h:116
struct GPU_PBVH_Buffers * draw_buffers
Definition: pbvh_intern.h:36
GSet * bm_unique_verts
Definition: pbvh_intern.h:117
BB orig_vb
Definition: pbvh_intern.h:40
float * layer_disp
Definition: pbvh_intern.h:105
int children_offset
Definition: pbvh_intern.h:44
PBVHNodeFlags flag
Definition: pbvh_intern.h:99
GSet * bm_other_verts
Definition: pbvh_intern.h:118
PBVHType type
Definition: pbvh_intern.h:133
int cd_face_node_offset
Definition: pbvh_intern.h:190
struct BMLog * bm_log
Definition: pbvh_intern.h:195
float bm_min_edge_len
Definition: pbvh_intern.h:188
int leaf_limit
Definition: pbvh_intern.h:144
bool draw_cache_invalid
Definition: pbvh_intern.h:206
PBVHFlags flags
Definition: pbvh_intern.h:134
float bm_max_edge_len
Definition: pbvh_intern.h:187
BMesh * bm
Definition: pbvh_intern.h:186
int totnode
Definition: pbvh_intern.h:137
int cd_vert_node_offset
Definition: pbvh_intern.h:189
PBVHNode * nodes
Definition: pbvh_intern.h:136