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