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