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