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