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