80d92f7c3a1bea7cead97e9d4a8592a02a94dabb
[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
33 #include "BKE_ccg.h"
34 #include "BKE_DerivedMesh.h"
35 #include "BKE_global.h"
36 #include "BKE_paint.h"
37 #include "BKE_pbvh.h"
38
39 #include "GPU_buffers.h"
40
41 #include "bmesh.h"
42 #include "pbvh_intern.h"
43
44 #include <assert.h>
45
46 /****************************** Building ******************************/
47
48 /* Update node data after splitting */
49 static void pbvh_bmesh_node_finalize(PBVH *bvh, int node_index)
50 {
51         GSetIterator gs_iter;
52         PBVHNode *n = &bvh->nodes[node_index];
53
54         /* Create vert hash sets */
55         n->bm_unique_verts = BLI_gset_ptr_new("bm_unique_verts");
56         n->bm_other_verts = BLI_gset_ptr_new("bm_other_verts");
57
58         BB_reset(&n->vb);
59
60         GSET_ITER (gs_iter, n->bm_faces) {
61                 BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
62                 BMLoop *l_iter;
63                 BMLoop *l_first;
64                 BMVert *v;
65                 void *node_val = SET_INT_IN_POINTER(node_index);
66
67                 /* Update ownership of faces */
68                 BLI_ghash_insert(bvh->bm_face_to_node, f, node_val);
69
70                 /* Update vertices */
71                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
72                 do {
73                         v = l_iter->v;
74                         if (!BLI_gset_haskey(n->bm_unique_verts, v)) {
75                                 if (BLI_ghash_haskey(bvh->bm_vert_to_node, v)) {
76                                         BLI_gset_reinsert(n->bm_other_verts, v, NULL);
77                                 }
78                                 else {
79                                         BLI_gset_insert(n->bm_unique_verts, v);
80                                         BLI_ghash_insert(bvh->bm_vert_to_node, v, node_val);
81                                 }
82                         }
83                         /* Update node bounding box */
84                         BB_expand(&n->vb, v->co);
85                 } while ((l_iter = l_iter->next) != l_first);
86         }
87
88         BLI_assert(n->vb.bmin[0] <= n->vb.bmax[0] &&
89                    n->vb.bmin[1] <= n->vb.bmax[1] &&
90                    n->vb.bmin[2] <= n->vb.bmax[2]);
91
92         n->orig_vb = n->vb;
93
94         /* Build GPU buffers for new node and update vertex normals */
95         BKE_pbvh_node_mark_rebuild_draw(n);
96         n->flag |= PBVH_UpdateNormals;
97 }
98
99 /* Recursively split the node if it exceeds the leaf_limit */
100 static void pbvh_bmesh_node_split(PBVH *bvh, GHash *prim_bbc, int node_index)
101 {
102         GSet *empty, *other;
103         GSetIterator gs_iter;
104         PBVHNode *n, *c1, *c2;
105         BB cb;
106         float mid;
107         int axis, children;
108
109         n = &bvh->nodes[node_index];
110
111         if (BLI_gset_size(n->bm_faces) <= bvh->leaf_limit) {
112                 /* Node limit not exceeded */
113                 pbvh_bmesh_node_finalize(bvh, node_index);
114                 return;
115         }
116
117         /* Calculate bounding box around primitive centroids */
118         BB_reset(&cb);
119         GSET_ITER (gs_iter, n->bm_faces) {
120                 const BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
121                 const BBC *bbc = BLI_ghash_lookup(prim_bbc, f);
122
123                 BB_expand(&cb, bbc->bcentroid);
124         }
125
126         /* Find widest axis and its midpoint */
127         axis = BB_widest_axis(&cb);
128         mid = (cb.bmax[axis] + cb.bmin[axis]) * 0.5f;
129
130         /* Add two new child nodes */
131         children = bvh->totnode;
132         n->children_offset = children;
133         pbvh_grow_nodes(bvh, bvh->totnode + 2);
134
135         /* Array reallocated, update current node pointer */
136         n = &bvh->nodes[node_index];
137
138         /* Initialize children */
139         c1 = &bvh->nodes[children];
140         c2 = &bvh->nodes[children + 1];
141         c1->flag |= PBVH_Leaf;
142         c2->flag |= PBVH_Leaf;
143         c1->bm_faces = BLI_gset_ptr_new_ex("bm_faces", BLI_gset_size(n->bm_faces) / 2);
144         c2->bm_faces = BLI_gset_ptr_new_ex("bm_faces", BLI_gset_size(n->bm_faces) / 2);
145
146         /* Partition the parent node's faces between the two children */
147         GSET_ITER (gs_iter, n->bm_faces) {
148                 BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
149                 const BBC *bbc = BLI_ghash_lookup(prim_bbc, f);
150
151                 if (bbc->bcentroid[axis] < mid)
152                         BLI_gset_insert(c1->bm_faces, f);
153                 else
154                         BLI_gset_insert(c2->bm_faces, f);
155         }
156
157         /* Enforce at least one primitive in each node */
158         empty = NULL;
159         if (BLI_gset_size(c1->bm_faces) == 0) {
160                 empty = c1->bm_faces;
161                 other = c2->bm_faces;
162         }
163         else if (BLI_gset_size(c2->bm_faces) == 0) {
164                 empty = c2->bm_faces;
165                 other = c1->bm_faces;
166         }
167         if (empty) {
168                 GSET_ITER (gs_iter, other) {
169                         void *key = BLI_gsetIterator_getKey(&gs_iter);
170                         BLI_gset_insert(empty, key);
171                         BLI_gset_remove(other, key, NULL);
172                         break;
173                 }
174         }
175         
176         /* Clear this node */
177
178         /* Mark this node's unique verts as unclaimed */
179         if (n->bm_unique_verts) {
180                 GSET_ITER (gs_iter, n->bm_unique_verts) {
181                         BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
182                         BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL);
183                 }
184                 BLI_gset_free(n->bm_unique_verts, NULL);
185         }
186
187         /* Unclaim faces */
188         GSET_ITER (gs_iter, n->bm_faces) {
189                 BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
190                 BLI_ghash_remove(bvh->bm_face_to_node, f, NULL, NULL);
191         }
192         BLI_gset_free(n->bm_faces, NULL);
193
194         if (n->bm_other_verts)
195                 BLI_gset_free(n->bm_other_verts, NULL);
196
197         if (n->layer_disp)
198                 MEM_freeN(n->layer_disp);
199         
200         n->bm_faces = NULL;
201         n->bm_unique_verts = NULL;
202         n->bm_other_verts = NULL;
203         n->layer_disp = NULL;
204         
205         if (n->draw_buffers) {
206                 GPU_free_pbvh_buffers(n->draw_buffers);
207                 n->draw_buffers = NULL;
208         }
209         n->flag &= ~PBVH_Leaf;
210         
211         /* Recurse */
212         c1 = c2 = NULL;
213         pbvh_bmesh_node_split(bvh, prim_bbc, children);
214         pbvh_bmesh_node_split(bvh, prim_bbc, children + 1);
215
216         /* Array maybe reallocated, update current node pointer */
217         n = &bvh->nodes[node_index];
218
219         /* Update bounding box */
220         BB_reset(&n->vb);
221         BB_expand_with_bb(&n->vb, &bvh->nodes[n->children_offset].vb);
222         BB_expand_with_bb(&n->vb, &bvh->nodes[n->children_offset + 1].vb);
223         n->orig_vb = n->vb;
224 }
225
226 /* Recursively split the node if it exceeds the leaf_limit */
227 static bool pbvh_bmesh_node_limit_ensure(PBVH *bvh, int node_index)
228 {
229         GHash *prim_bbc;
230         GSet *bm_faces;
231         int bm_faces_size;
232         GSetIterator gs_iter;
233         BBC *bbc_array;
234         unsigned int i;
235
236         bm_faces = bvh->nodes[node_index].bm_faces;
237         bm_faces_size = BLI_gset_size(bm_faces);
238         if (bm_faces_size <= bvh->leaf_limit) {
239                 /* Node limit not exceeded */
240                 return false;
241         }
242
243         /* For each BMFace, store the AABB and AABB centroid */
244         prim_bbc = BLI_ghash_ptr_new_ex("prim_bbc", bm_faces_size);
245         bbc_array = MEM_callocN(sizeof(BBC) * bm_faces_size, "BBC");
246
247         GSET_ITER_INDEX (gs_iter, bm_faces, i) {
248                 BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
249                 BBC *bbc = &bbc_array[i];
250                 BMLoop *l_iter;
251                 BMLoop *l_first;
252
253                 BB_reset((BB *)bbc);
254                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
255                 do {
256                         BB_expand((BB *)bbc, l_iter->v->co);
257                 } while ((l_iter = l_iter->next) != l_first);
258                 BBC_update_centroid(bbc);
259
260                 BLI_ghash_insert(prim_bbc, f, bbc);
261         }
262
263         pbvh_bmesh_node_split(bvh, prim_bbc, node_index);
264
265         BLI_ghash_free(prim_bbc, NULL, NULL);
266         MEM_freeN(bbc_array);
267
268         return true;
269 }
270
271 /**********************************************************************/
272
273 static PBVHNode *pbvh_bmesh_node_lookup(PBVH *bvh, GHash *map, void *key)
274 {
275         int node_index;
276
277         BLI_assert(BLI_ghash_haskey(map, key));
278
279         node_index = GET_INT_FROM_POINTER(BLI_ghash_lookup(map, key));
280         BLI_assert(node_index < bvh->totnode);
281
282         return &bvh->nodes[node_index];
283 }
284
285 static BMVert *pbvh_bmesh_vert_create(PBVH *bvh, int node_index,
286                                       const float co[3],
287                                       const BMVert *example,
288                                       const int cd_vert_mask_offset)
289 {
290         BMVert *v = BM_vert_create(bvh->bm, co, example, BM_CREATE_NOP);
291         void *val = SET_INT_IN_POINTER(node_index);
292         PBVHNode *node = &bvh->nodes[node_index];
293
294         BLI_assert((bvh->totnode == 1 || node_index) && node_index <= bvh->totnode);
295
296         BLI_gset_insert(node->bm_unique_verts, v);
297         BLI_ghash_insert(bvh->bm_vert_to_node, v, val);
298
299         node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
300
301         /* Log the new vertex */
302         BM_log_vert_added(bvh->bm_log, v, cd_vert_mask_offset);
303
304         return v;
305 }
306
307 static BMFace *pbvh_bmesh_face_create(PBVH *bvh, int node_index,
308                                       BMVert *v_tri[3], BMEdge *e_tri[3],
309                                       const BMFace *f_example)
310 {
311         BMFace *f;
312         void *val = SET_INT_IN_POINTER(node_index);
313         PBVHNode *node = &bvh->nodes[node_index];
314
315         /* ensure we never add existing face */
316         BLI_assert(BM_face_exists(v_tri, 3, NULL) == false);
317
318         f = BM_face_create(bvh->bm, v_tri, e_tri, 3, f_example, BM_CREATE_NOP);
319         f->head.hflag = f_example->head.hflag;
320
321         BLI_assert(!BLI_ghash_haskey(bvh->bm_face_to_node, f));
322
323         {
324                 BLI_gset_insert(node->bm_faces, f);
325                 BLI_ghash_insert(bvh->bm_face_to_node, f, val);
326
327                 /* mark node for update */
328                 node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateNormals;
329                 node->flag &= ~PBVH_FullyHidden;
330
331                 /* Log the new face */
332                 BM_log_face_added(bvh->bm_log, f);
333         }
334
335         return f;
336 }
337
338 /* Return the number of faces in 'node' that use vertex 'v' */
339 static int pbvh_bmesh_node_vert_use_count(PBVH *bvh, PBVHNode *node, BMVert *v)
340 {
341         BMIter bm_iter;
342         BMFace *f;
343         int count = 0;
344
345         BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
346                 PBVHNode *f_node;
347
348                 f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
349
350                 if (f_node == node)
351                         count++;
352         }
353
354         return count;
355 }
356
357 /* Return a node that uses vertex 'v' other than its current owner */
358 static PBVHNode *pbvh_bmesh_vert_other_node_find(PBVH *bvh, BMVert *v)
359 {
360         BMIter bm_iter;
361         BMFace *f;
362         PBVHNode *current_node;
363
364         current_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
365
366         BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
367                 PBVHNode *f_node;
368
369                 f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
370
371                 if (f_node != current_node)
372                         return f_node;
373         }
374
375         return NULL;
376 }
377
378 static void pbvh_bmesh_vert_ownership_transfer(PBVH *bvh, PBVHNode *new_owner,
379                                                BMVert *v)
380 {
381         PBVHNode *current_owner;
382
383         current_owner = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
384         /* mark node for update */
385         current_owner->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
386
387
388         BLI_assert(current_owner != new_owner);
389
390         /* Remove current ownership */
391         BLI_gset_remove(current_owner->bm_unique_verts, v, NULL);
392
393         /* Set new ownership */
394         BLI_ghash_reinsert(bvh->bm_vert_to_node, v,
395                            SET_INT_IN_POINTER(new_owner - bvh->nodes), NULL, NULL);
396         BLI_gset_insert(new_owner->bm_unique_verts, v);
397         BLI_gset_remove(new_owner->bm_other_verts, v, NULL);
398         BLI_assert(!BLI_gset_haskey(new_owner->bm_other_verts, v));
399
400         /* mark node for update */
401         new_owner->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
402 }
403
404 static void pbvh_bmesh_vert_remove(PBVH *bvh, BMVert *v)
405 {
406         PBVHNode *v_node;
407         BMIter bm_iter;
408         BMFace *f;
409
410         BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v));
411         v_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
412         BLI_gset_remove(v_node->bm_unique_verts, v, NULL);
413         BLI_ghash_remove(bvh->bm_vert_to_node, v, NULL, NULL);
414
415         /* Have to check each neighboring face's node */
416         BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
417                 PBVHNode *f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
418
419                 f_node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateBB;
420
421                 /* Remove current ownership */
422                 BLI_gset_remove(f_node->bm_other_verts, v, NULL);
423
424                 BLI_assert(!BLI_gset_haskey(f_node->bm_unique_verts, v));
425                 BLI_assert(!BLI_gset_haskey(f_node->bm_other_verts, v));
426         }
427 }
428
429 static void pbvh_bmesh_face_remove(PBVH *bvh, BMFace *f)
430 {
431         PBVHNode *f_node;
432         BMVert *v;
433
434         BMLoop *l_iter;
435         BMLoop *l_first;
436
437         f_node = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
438
439         /* Check if any of this face's vertices need to be removed
440          * from the node */
441         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
442         do {
443                 v = l_iter->v;
444                 if (pbvh_bmesh_node_vert_use_count(bvh, f_node, v) == 1) {
445                         if (BLI_gset_haskey(f_node->bm_unique_verts, v)) {
446                                 /* Find a different node that uses 'v' */
447                                 PBVHNode *new_node;
448
449                                 new_node = pbvh_bmesh_vert_other_node_find(bvh, v);
450                                 BLI_assert(new_node || BM_vert_face_count(v) == 1);
451
452                                 if (new_node) {
453                                         pbvh_bmesh_vert_ownership_transfer(bvh, new_node, v);
454                                 }
455                         }
456                         else {
457                                 /* Remove from other verts */
458                                 BLI_gset_remove(f_node->bm_other_verts, v, NULL);
459                         }
460                 }
461         } while ((l_iter = l_iter->next) != l_first);
462
463         /* Remove face from node and top level */
464         BLI_gset_remove(f_node->bm_faces, f, NULL);
465         BLI_ghash_remove(bvh->bm_face_to_node, f, NULL, NULL);
466
467         /* Log removed face */
468         BM_log_face_removed(bvh->bm_log, f);
469
470         /* mark node for update */
471         f_node->flag |= PBVH_UpdateDrawBuffers | PBVH_UpdateNormals;
472 }
473
474 static void pbvh_bmesh_edge_loops(BLI_Buffer *buf, BMEdge *e)
475 {
476         /* fast-path for most common case where an edge has 2 faces,
477          * no need to iterate twice.
478          * This assumes that the buffer */
479         BMLoop **data = buf->data;
480         BLI_assert(buf->alloc_count >= 2);
481         if (LIKELY(BM_edge_loop_pair(e, &data[0], &data[1]))) {
482                 buf->count = 2;
483         }
484         else {
485                 BLI_buffer_resize(buf, BM_edge_face_count(e));
486                 BM_iter_as_array(NULL, BM_LOOPS_OF_EDGE, e, buf->data, buf->count);
487         }
488 }
489
490 static void pbvh_bmesh_node_drop_orig(PBVHNode *node)
491 {
492         if (node->bm_orco)
493                 MEM_freeN(node->bm_orco);
494         if (node->bm_ortri)
495                 MEM_freeN(node->bm_ortri);
496         node->bm_orco = NULL;
497         node->bm_ortri = NULL;
498         node->bm_tot_ortri = 0;
499 }
500
501 /****************************** EdgeQueue *****************************/
502
503 typedef struct {
504         Heap *heap;
505         const float *center;
506         float radius_squared;
507         float limit_len_squared;
508 } EdgeQueue;
509
510 typedef struct {
511         EdgeQueue *q;
512         BLI_mempool *pool;
513         BMesh *bm;
514         int cd_vert_mask_offset;
515 } EdgeQueueContext;
516
517 static bool edge_queue_tri_in_sphere(const EdgeQueue *q, BMFace *f)
518 {
519         BMVert *v_tri[3];
520         float c[3];
521
522         /* Get closest point in triangle to sphere center */
523         // BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f, (void **)v_tri, 3);
524         BM_face_as_array_vert_tri(f, v_tri);
525
526         closest_on_tri_to_point_v3(c, q->center, v_tri[0]->co, v_tri[1]->co, v_tri[2]->co);
527
528         /* Check if triangle intersects the sphere */
529         return ((len_squared_v3v3(q->center, c) <= q->radius_squared));
530 }
531
532 /* Return true if the vertex mask is less than 1.0, false otherwise */
533 static bool check_mask(EdgeQueueContext *eq_ctx, BMVert *v)
534 {
535         return (BM_ELEM_CD_GET_FLOAT(v, eq_ctx->cd_vert_mask_offset) < 1.0f);
536 }
537
538 static void edge_queue_insert(EdgeQueueContext *eq_ctx, BMEdge *e,
539                               float priority)
540 {
541         BMVert **pair;
542
543         /* Don't let topology update affect fully masked vertices. This used to
544          * have a 50% mask cutoff, with the reasoning that you can't do a 50%
545          * topology update. But this gives an ugly border in the mesh. The mask
546          * should already make the brush move the vertices only 50%, which means
547          * that topology updates will also happen less frequent, that should be
548          * enough. */
549         if ((check_mask(eq_ctx, e->v1) || check_mask(eq_ctx, e->v2)) &&
550             !(BM_elem_flag_test_bool(e->v1, BM_ELEM_HIDDEN) ||
551               BM_elem_flag_test_bool(e->v2, BM_ELEM_HIDDEN)))
552         {
553                 pair = BLI_mempool_alloc(eq_ctx->pool);
554                 pair[0] = e->v1;
555                 pair[1] = e->v2;
556                 BLI_heap_insert(eq_ctx->q->heap, priority, pair);
557         }
558 }
559
560 static void long_edge_queue_edge_add(EdgeQueueContext *eq_ctx,
561                                      BMEdge *e)
562 {
563         const float len_sq = BM_edge_calc_length_squared(e);
564         if (len_sq > eq_ctx->q->limit_len_squared)
565                 edge_queue_insert(eq_ctx, e, -len_sq);
566 }
567
568 static void short_edge_queue_edge_add(EdgeQueueContext *eq_ctx,
569                                       BMEdge *e)
570 {
571         const float len_sq = BM_edge_calc_length_squared(e);
572         if (len_sq < eq_ctx->q->limit_len_squared)
573                 edge_queue_insert(eq_ctx, e, len_sq);
574 }
575
576 static void long_edge_queue_face_add(EdgeQueueContext *eq_ctx,
577                                      BMFace *f)
578 {
579         if (edge_queue_tri_in_sphere(eq_ctx->q, f)) {
580                 BMLoop *l_iter;
581                 BMLoop *l_first;
582
583                 /* Check each edge of the face */
584                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
585                 do {
586                         long_edge_queue_edge_add(eq_ctx, l_iter->e);
587                 } while ((l_iter = l_iter->next) != l_first);
588         }
589 }
590
591 static void short_edge_queue_face_add(EdgeQueueContext *eq_ctx,
592                                       BMFace *f)
593 {
594         if (edge_queue_tri_in_sphere(eq_ctx->q, f)) {
595                 BMLoop *l_iter;
596                 BMLoop *l_first;
597
598                 /* Check each edge of the face */
599                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
600                 do {
601                         short_edge_queue_edge_add(eq_ctx, l_iter->e);
602                 } while ((l_iter = l_iter->next) != l_first);
603         }
604 }
605
606 /* Create a priority queue containing vertex pairs connected by a long
607  * edge as defined by PBVH.bm_max_edge_len.
608  *
609  * Only nodes marked for topology update are checked, and in those
610  * nodes only edges used by a face intersecting the (center, radius)
611  * sphere are checked.
612  *
613  * The highest priority (lowest number) is given to the longest edge.
614  */
615 static void long_edge_queue_create(EdgeQueueContext *eq_ctx,
616                                    PBVH *bvh, const float center[3],
617                                    float radius)
618 {
619         int n;
620
621         eq_ctx->q->heap = BLI_heap_new();
622         eq_ctx->q->center = center;
623         eq_ctx->q->radius_squared = radius * radius;
624         eq_ctx->q->limit_len_squared = bvh->bm_max_edge_len * bvh->bm_max_edge_len;
625
626         for (n = 0; n < bvh->totnode; n++) {
627                 PBVHNode *node = &bvh->nodes[n];
628
629                 /* Check leaf nodes marked for topology update */
630                 if ((node->flag & PBVH_Leaf) &&
631                     (node->flag & PBVH_UpdateTopology) &&
632                     !(node->flag & PBVH_FullyHidden))
633                 {
634                         GSetIterator gs_iter;
635
636                         /* Check each face */
637                         GSET_ITER (gs_iter, node->bm_faces) {
638                                 BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
639
640                                 long_edge_queue_face_add(eq_ctx, f);
641                         }
642                 }
643         }
644 }
645
646 /* Create a priority queue containing vertex pairs connected by a
647  * short edge as defined by PBVH.bm_min_edge_len.
648  *
649  * Only nodes marked for topology update are checked, and in those
650  * nodes only edges used by a face intersecting the (center, radius)
651  * sphere are checked.
652  *
653  * The highest priority (lowest number) is given to the shortest edge.
654  */
655 static void short_edge_queue_create(EdgeQueueContext *eq_ctx,
656                                     PBVH *bvh, const float center[3],
657                                     float radius)
658 {
659         int n;
660
661         eq_ctx->q->heap = BLI_heap_new();
662         eq_ctx->q->center = center;
663         eq_ctx->q->radius_squared = radius * radius;
664         eq_ctx->q->limit_len_squared = bvh->bm_min_edge_len * bvh->bm_min_edge_len;
665
666         for (n = 0; n < bvh->totnode; n++) {
667                 PBVHNode *node = &bvh->nodes[n];
668
669                 /* Check leaf nodes marked for topology update */
670                 if ((node->flag & PBVH_Leaf) &&
671                     (node->flag & PBVH_UpdateTopology) &&
672                     !(node->flag & PBVH_FullyHidden))
673                 {
674                         GSetIterator gs_iter;
675
676                         /* Check each face */
677                         GSET_ITER (gs_iter, node->bm_faces) {
678                                 BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
679
680                                 short_edge_queue_face_add(eq_ctx, f);
681                         }
682                 }
683         }
684 }
685
686 /*************************** Topology update **************************/
687
688 static void bm_edges_from_tri(BMesh *bm, BMVert *v_tri[3], BMEdge *e_tri[3])
689 {
690         e_tri[0] = BM_edge_create(bm, v_tri[0], v_tri[1], NULL, BM_CREATE_NO_DOUBLE);
691         e_tri[1] = BM_edge_create(bm, v_tri[1], v_tri[2], NULL, BM_CREATE_NO_DOUBLE);
692         e_tri[2] = BM_edge_create(bm, v_tri[2], v_tri[0], NULL, BM_CREATE_NO_DOUBLE);
693 }
694
695 static void pbvh_bmesh_split_edge(EdgeQueueContext *eq_ctx, PBVH *bvh,
696                                   BMEdge *e, BLI_Buffer *edge_loops)
697 {
698         BMVert *v_new;
699         float mid[3];
700         int i, node_index;
701
702         /* Get all faces adjacent to the edge */
703         pbvh_bmesh_edge_loops(edge_loops, e);
704
705         /* Create a new vertex in current node at the edge's midpoint */
706         mid_v3_v3v3(mid, e->v1->co, e->v2->co);
707
708         node_index = GET_INT_FROM_POINTER(BLI_ghash_lookup(bvh->bm_vert_to_node,
709                                                            e->v1));
710         v_new = pbvh_bmesh_vert_create(bvh, node_index, mid, e->v1, eq_ctx->cd_vert_mask_offset);
711
712         /* update paint mask */
713         if (eq_ctx->cd_vert_mask_offset != -1) {
714                 float mask_v1 = BM_ELEM_CD_GET_FLOAT(e->v1, eq_ctx->cd_vert_mask_offset);
715                 float mask_v2 = BM_ELEM_CD_GET_FLOAT(e->v2, eq_ctx->cd_vert_mask_offset);
716                 float mask_v_new = 0.5f * (mask_v1 + mask_v2);
717
718                 BM_ELEM_CD_SET_FLOAT(v_new, eq_ctx->cd_vert_mask_offset, mask_v_new);
719         }
720
721         /* For each face, add two new triangles and delete the original */
722         for (i = 0; i < edge_loops->count; i++) {
723                 BMLoop *l_adj = BLI_buffer_at(edge_loops, BMLoop *, i);
724                 BMFace *f_adj = l_adj->f;
725                 BMFace *f_new;
726                 BMVert *v_opp, *v1, *v2;
727                 BMVert *v_tri[3];
728                 BMEdge *e_tri[3];
729                 void *nip;
730                 int ni;
731
732                 BLI_assert(f_adj->len == 3);
733                 nip = BLI_ghash_lookup(bvh->bm_face_to_node, f_adj);
734                 ni = GET_INT_FROM_POINTER(nip);
735
736                 /* Find the vertex not in the edge */
737                 v_opp = l_adj->prev->v;
738
739                 /* Get e->v1 and e->v2 in the order they appear in the
740                  * existing face so that the new faces' winding orders
741                  * match */
742                 v1 = l_adj->v;
743                 v2 = l_adj->next->v;
744
745                 if (ni != node_index && i == 0)
746                         pbvh_bmesh_vert_ownership_transfer(bvh, &bvh->nodes[ni], v_new);
747
748                 /* Create two new faces */
749                 v_tri[0] = v1;
750                 v_tri[1] = v_new;
751                 v_tri[2] = v_opp;
752                 bm_edges_from_tri(bvh->bm, v_tri, e_tri);
753                 f_new = pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f_adj);
754                 long_edge_queue_face_add(eq_ctx, f_new);
755
756                 v_tri[0] = v_new;
757                 v_tri[1] = v2;
758                 /* v_tri[2] = v_opp; */ /* unchanged */
759                 e_tri[0] = BM_edge_create(bvh->bm, v_tri[0], v_tri[1], NULL, BM_CREATE_NO_DOUBLE);
760                 e_tri[2] = e_tri[1];  /* switched */
761                 e_tri[1] = BM_edge_create(bvh->bm, v_tri[1], v_tri[2], NULL, BM_CREATE_NO_DOUBLE);
762                 f_new = pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f_adj);
763                 long_edge_queue_face_add(eq_ctx, f_new);
764
765                 /* Delete original */
766                 pbvh_bmesh_face_remove(bvh, f_adj);
767                 BM_face_kill(bvh->bm, f_adj);
768
769                 /* Ensure new vertex is in the node */
770                 if (!BLI_gset_haskey(bvh->nodes[ni].bm_unique_verts, v_new) &&
771                     !BLI_gset_haskey(bvh->nodes[ni].bm_other_verts, v_new))
772                 {
773                         BLI_gset_insert(bvh->nodes[ni].bm_other_verts, v_new);
774                 }
775
776                 if (BM_vert_edge_count(v_opp) >= 9) {
777                         BMIter bm_iter;
778                         BMEdge *e2;
779
780                         BM_ITER_ELEM (e2, &bm_iter, v_opp, BM_EDGES_OF_VERT) {
781                                 long_edge_queue_edge_add(eq_ctx, e2);
782                         }
783                 }
784         }
785
786         BM_edge_kill(bvh->bm, e);
787 }
788
789 static bool pbvh_bmesh_subdivide_long_edges(EdgeQueueContext *eq_ctx, PBVH *bvh,
790                                             BLI_Buffer *edge_loops)
791 {
792         bool any_subdivided = false;
793
794         while (!BLI_heap_is_empty(eq_ctx->q->heap)) {
795                 BMVert **pair = BLI_heap_popmin(eq_ctx->q->heap);
796                 BMVert *v1 = pair[0], *v2 = pair[1];
797                 BMEdge *e;
798
799                 BLI_mempool_free(eq_ctx->pool, pair);
800                 pair = NULL;
801
802                 if (len_squared_v3v3(v1->co, v2->co) <= eq_ctx->q->limit_len_squared)
803                         continue;
804
805                 /* Check that the edge still exists */
806                 if (!(e = BM_edge_exists(v1, v2))) {
807                         continue;
808                 }
809
810                 /* Check that the edge's vertices are still in the PBVH. It's
811                  * possible that an edge collapse has deleted adjacent faces
812                  * and the node has been split, thus leaving wire edges and
813                  * associated vertices. */
814                 if (!BLI_ghash_haskey(bvh->bm_vert_to_node, e->v1) ||
815                     !BLI_ghash_haskey(bvh->bm_vert_to_node, e->v2))
816                 {
817                         continue;
818                 }
819
820                 any_subdivided = true;
821
822                 pbvh_bmesh_split_edge(eq_ctx, bvh, e, edge_loops);
823         }
824
825         return any_subdivided;
826 }
827
828 static void pbvh_bmesh_collapse_edge(PBVH *bvh, BMEdge *e,
829                                      BMVert *v1, BMVert *v2,
830                                      GSet *deleted_verts,
831                                      BLI_Buffer *edge_loops,
832                                      BLI_Buffer *deleted_faces,
833                                      int cd_vert_mask_offset)
834 {
835         BMIter bm_iter;
836         BMFace *f;
837         BMVert *v_del, *v_conn;
838         int i;
839         float mask_v1 = BM_ELEM_CD_GET_FLOAT(v1, cd_vert_mask_offset);
840
841         /* one of the two vertices may be masked, select the correct one for deletion */
842         if (mask_v1 < 1.0f) {
843                 v_del = v1;
844                 v_conn = v2;
845         }
846         else {
847                 v_del = v2;
848                 v_conn = v1;
849         }
850
851         /* Get all faces adjacent to the edge */
852         pbvh_bmesh_edge_loops(edge_loops, e);
853
854         /* Remove the merge vertex from the PBVH */
855         pbvh_bmesh_vert_remove(bvh, v_del);
856
857         /* Remove all faces adjacent to the edge */
858         for (i = 0; i < edge_loops->count; i++) {
859                 BMLoop *l_adj = BLI_buffer_at(edge_loops, BMLoop *, i);
860                 BMFace *f_adj = l_adj->f;
861
862                 pbvh_bmesh_face_remove(bvh, f_adj);
863                 BM_face_kill(bvh->bm, f_adj);
864         }
865
866         /* Kill the edge */
867         BLI_assert(BM_edge_is_wire(e));
868         BM_edge_kill(bvh->bm, e);
869
870         /* For all remaining faces of v_del, create a new face that is the
871          * same except it uses v_conn instead of v_del */
872         /* Note: this could be done with BM_vert_splice(), but that
873          * requires handling other issues like duplicate edges, so doesn't
874          * really buy anything. */
875         deleted_faces->count = 0;
876         BM_ITER_ELEM (f, &bm_iter, v_del, BM_FACES_OF_VERT) {
877                 BMVert *v_tri[3];
878                 BMFace *existing_face;
879                 PBVHNode *n;
880                 int ni;
881
882                 /* Get vertices, replace use of v_del with v_conn */
883                 // BM_iter_as_array(NULL, BM_VERTS_OF_FACE, f, (void **)v_tri, 3);
884                 BM_face_as_array_vert_tri(f, v_tri);
885                 for (i = 0; i < 3; i++) {
886                         if (v_tri[i] == v_del) {
887                                 v_tri[i] = v_conn;
888                         }
889                 }
890
891                 /* Check if a face using these vertices already exists. If so,
892                  * skip adding this face and mark the existing one for
893                  * deletion as well. Prevents extraneous "flaps" from being
894                  * created. */
895                 if (BM_face_exists(v_tri, 3, &existing_face)) {
896                         BLI_assert(existing_face);
897                         BLI_buffer_append(deleted_faces, BMFace *, existing_face);
898                 }
899                 else {
900                         BMEdge *e_tri[3];
901                         n = pbvh_bmesh_node_lookup(bvh, bvh->bm_face_to_node, f);
902                         ni = n - bvh->nodes;
903                         bm_edges_from_tri(bvh->bm, v_tri, e_tri);
904                         pbvh_bmesh_face_create(bvh, ni, v_tri, e_tri, f);
905
906                         /* Ensure that v_conn is in the new face's node */
907                         if (!BLI_gset_haskey(n->bm_unique_verts, v_conn) &&
908                             !BLI_gset_haskey(n->bm_other_verts,  v_conn))
909                         {
910                                 BLI_gset_insert(n->bm_other_verts, v_conn);
911                         }
912                 }
913
914                 BLI_buffer_append(deleted_faces, BMFace *, f);
915         }
916
917         /* Delete the tagged faces */
918         for (i = 0; i < deleted_faces->count; i++) {
919                 BMFace *f_del = BLI_buffer_at(deleted_faces, BMFace *, i);
920                 BMLoop *l_iter;
921                 BMVert *v_tri[3];
922                 BMEdge *e_tri[3];
923                 int j;
924
925                 /* Get vertices and edges of face */
926                 BLI_assert(f_del->len == 3);
927                 l_iter = BM_FACE_FIRST_LOOP(f_del);
928                 v_tri[0] = l_iter->v; e_tri[0] = l_iter->e; l_iter = l_iter->next;
929                 v_tri[1] = l_iter->v; e_tri[1] = l_iter->e; l_iter = l_iter->next;
930                 v_tri[2] = l_iter->v; e_tri[2] = l_iter->e;
931
932                 /* Check if any of the face's vertices are now unused, if so
933                  * remove them from the PBVH */
934                 for (j = 0; j < 3; j++) {
935                         if (v_tri[j] != v_del && BM_vert_face_count(v_tri[j]) == 1) {
936                                 BLI_gset_insert(deleted_verts, v_tri[j]);
937                                 pbvh_bmesh_vert_remove(bvh, v_tri[j]);
938                         }
939                         else {
940                                 v_tri[j] = NULL;
941                         }
942                 }
943
944                 /* Remove the face */
945                 pbvh_bmesh_face_remove(bvh, f_del);
946                 BM_face_kill(bvh->bm, f_del);
947
948                 /* Check if any of the face's edges are now unused by any
949                  * face, if so delete them */
950                 for (j = 0; j < 3; j++) {
951                         if (BM_edge_is_wire(e_tri[j]))
952                                 BM_edge_kill(bvh->bm, e_tri[j]);
953                 }
954
955                 /* Delete unused vertices */
956                 for (j = 0; j < 3; j++) {
957                         if (v_tri[j]) {
958                                 BM_log_vert_removed(bvh->bm_log, v_tri[j], cd_vert_mask_offset);
959                                 BM_vert_kill(bvh->bm, v_tri[j]);
960                         }
961                 }
962         }
963
964         /* Move v_conn to the midpoint of v_conn and v_del (if v_conn still exists, it
965          * may have been deleted above) */
966         if (!BLI_gset_haskey(deleted_verts, v_conn)) {
967                 BM_log_vert_before_modified(bvh->bm_log, v_conn, cd_vert_mask_offset);
968                 mid_v3_v3v3(v_conn->co, v_conn->co, v_del->co);
969         }
970
971         /* Delete v_del */
972         BLI_assert(BM_vert_face_count(v_del) == 0);
973         BLI_gset_insert(deleted_verts, v_del);
974         BM_log_vert_removed(bvh->bm_log, v_del, cd_vert_mask_offset);
975         BM_vert_kill(bvh->bm, v_del);
976 }
977
978 static bool pbvh_bmesh_collapse_short_edges(EdgeQueueContext *eq_ctx,
979                                             PBVH *bvh,
980                                             BLI_Buffer *edge_loops,
981                                             BLI_Buffer *deleted_faces)
982 {
983         float min_len_squared = bvh->bm_min_edge_len * bvh->bm_min_edge_len;
984         GSet *deleted_verts;
985         bool any_collapsed = false;
986
987         deleted_verts = BLI_gset_ptr_new("deleted_verts");
988
989         while (!BLI_heap_is_empty(eq_ctx->q->heap)) {
990                 BMVert **pair = BLI_heap_popmin(eq_ctx->q->heap);
991                 BMVert *v1 = pair[0], *v2 = pair[1];
992                 BMEdge *e;
993
994                 BLI_mempool_free(eq_ctx->pool, pair);
995                 pair = NULL;
996
997                 /* Check the verts still exist */
998                 if (BLI_gset_haskey(deleted_verts, v1) ||
999                     BLI_gset_haskey(deleted_verts, v2))
1000                 {
1001                         continue;
1002                 }
1003
1004                 if (len_squared_v3v3(v1->co, v2->co) >= min_len_squared)
1005                         continue;
1006
1007                 /* Check that the edge still exists */
1008                 if (!(e = BM_edge_exists(v1, v2))) {
1009                         continue;
1010                 }
1011
1012                 /* Check that the edge's vertices are still in the PBVH. It's
1013                  * possible that an edge collapse has deleted adjacent faces
1014                  * and the node has been split, thus leaving wire edges and
1015                  * associated vertices. */
1016                 if (!BLI_ghash_haskey(bvh->bm_vert_to_node, e->v1) ||
1017                     !BLI_ghash_haskey(bvh->bm_vert_to_node, e->v2))
1018                 {
1019                         continue;
1020                 }
1021
1022                 any_collapsed = true;
1023
1024                 pbvh_bmesh_collapse_edge(bvh, e, v1, v2,
1025                                          deleted_verts, edge_loops,
1026                                          deleted_faces, eq_ctx->cd_vert_mask_offset);
1027         }
1028
1029         BLI_gset_free(deleted_verts, NULL);
1030
1031         return any_collapsed;
1032 }
1033
1034 /************************* Called from pbvh.c *************************/
1035
1036 bool pbvh_bmesh_node_raycast(PBVHNode *node, const float ray_start[3],
1037                             const float ray_normal[3], float *dist,
1038                             bool use_original)
1039 {
1040         bool hit = false;
1041
1042         if (use_original && node->bm_tot_ortri) {
1043                 int i;
1044                 for (i = 0; i < node->bm_tot_ortri; i++) {
1045                         const int *t = node->bm_ortri[i];
1046                         hit |= ray_face_intersection(ray_start, ray_normal,
1047                                                      node->bm_orco[t[0]],
1048                                                      node->bm_orco[t[1]],
1049                                                      node->bm_orco[t[2]],
1050                                                      NULL, dist);
1051                 }
1052         }
1053         else {
1054                 GSetIterator gs_iter;
1055
1056                 GSET_ITER (gs_iter, node->bm_faces) {
1057                         BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
1058
1059                         BLI_assert(f->len == 3);
1060                         if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
1061                                 BMVert *v_tri[3];
1062
1063                                 BM_face_as_array_vert_tri(f, v_tri);
1064                                 hit |= ray_face_intersection(ray_start, ray_normal,
1065                                                              v_tri[0]->co,
1066                                                              v_tri[1]->co,
1067                                                              v_tri[2]->co,
1068                                                              NULL, dist);
1069                         }
1070                 }
1071         }
1072
1073         return hit;
1074 }
1075
1076 bool BKE_pbvh_bmesh_node_raycast_detail(
1077         PBVHNode *node,
1078         const float ray_start[3], const float ray_normal[3],
1079         float *detail, float *dist)
1080 {
1081         GSetIterator gs_iter;
1082         bool hit = false;
1083         BMFace *f_hit = NULL;
1084
1085         if (node->flag & PBVH_FullyHidden)
1086                 return 0;
1087
1088         GSET_ITER (gs_iter, node->bm_faces) {
1089                 BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
1090
1091                 BLI_assert(f->len == 3);
1092                 if (!BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
1093                         BMVert *v_tri[3];
1094                         bool hit_local;
1095                         BM_face_as_array_vert_tri(f, v_tri);
1096                         hit_local = ray_face_intersection(
1097                                 ray_start, ray_normal,
1098                                 v_tri[0]->co,
1099                                 v_tri[1]->co,
1100                                 v_tri[2]->co,
1101                                 NULL, dist);
1102
1103                         if (hit_local) {
1104                                 f_hit = f;
1105                                 hit = true;
1106                         }
1107                 }
1108         }
1109
1110         if (hit) {
1111                 float len1, len2, len3;
1112                 BMVert *v_tri[3];
1113                 BM_face_as_array_vert_tri(f_hit, v_tri);
1114                 len1 = len_squared_v3v3(v_tri[0]->co, v_tri[1]->co);
1115                 len2 = len_squared_v3v3(v_tri[1]->co, v_tri[2]->co);
1116                 len3 = len_squared_v3v3(v_tri[2]->co, v_tri[0]->co);
1117
1118                 /* detail returned will be set to the maximum allowed size, so take max here */
1119                 *detail = sqrtf(max_fff(len1, len2, len3));
1120         }
1121
1122         return hit;
1123 }
1124
1125
1126 void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode)
1127 {
1128         int n;
1129
1130         for (n = 0; n < totnode; n++) {
1131                 PBVHNode *node = nodes[n];
1132
1133                 if (node->flag & PBVH_UpdateNormals) {
1134                         GSetIterator gs_iter;
1135
1136                         GSET_ITER (gs_iter, node->bm_faces) {
1137                                 BM_face_normal_update(BLI_gsetIterator_getKey(&gs_iter));
1138                         }
1139                         GSET_ITER (gs_iter, node->bm_unique_verts) {
1140                                 BM_vert_normal_update(BLI_gsetIterator_getKey(&gs_iter));
1141                         }
1142                         /* This should be unneeded normally */
1143                         GSET_ITER (gs_iter, node->bm_other_verts) {
1144                                 BM_vert_normal_update(BLI_gsetIterator_getKey(&gs_iter));
1145                         }
1146                         node->flag &= ~PBVH_UpdateNormals;
1147                 }
1148         }
1149 }
1150
1151 /***************************** Public API *****************************/
1152
1153 /* Build a PBVH from a BMesh */
1154 void BKE_pbvh_build_bmesh(PBVH *bvh, BMesh *bm, bool smooth_shading, BMLog *log)
1155 {
1156         BMIter iter;
1157         BMFace *f;
1158         PBVHNode *n;
1159         int node_index = 0;
1160
1161         bvh->bm = bm;
1162
1163         BKE_pbvh_bmesh_detail_size_set(bvh, 0.75);
1164
1165         bvh->type = PBVH_BMESH;
1166         bvh->bm_face_to_node = BLI_ghash_ptr_new("bm_face_to_node");
1167         bvh->bm_vert_to_node = BLI_ghash_ptr_new("bm_vert_to_node");
1168         bvh->bm_log = log;
1169
1170         /* TODO: choose leaf limit better */
1171         bvh->leaf_limit = 100;
1172
1173         if (smooth_shading)
1174                 bvh->flags |= PBVH_DYNTOPO_SMOOTH_SHADING;
1175
1176         /* Start with all faces in the root node */
1177         n = bvh->nodes = MEM_callocN(sizeof(PBVHNode), "PBVHNode");
1178         bvh->totnode = 1;
1179         n->flag = PBVH_Leaf;
1180         n->bm_faces = BLI_gset_ptr_new_ex("bm_faces", bvh->bm->totface);
1181         BM_ITER_MESH (f, &iter, bvh->bm, BM_FACES_OF_MESH) {
1182                 BLI_gset_insert(n->bm_faces, f);
1183         }
1184
1185         /* Recursively split the node until it is under the limit; if no
1186          * splitting occurs then finalize the existing leaf node */
1187         if (!pbvh_bmesh_node_limit_ensure(bvh, node_index))
1188                 pbvh_bmesh_node_finalize(bvh, 0);
1189 }
1190
1191 /* Collapse short edges, subdivide long edges */
1192 bool BKE_pbvh_bmesh_update_topology(PBVH *bvh, PBVHTopologyUpdateMode mode,
1193                                    const float center[3], float radius)
1194 {
1195         /* 2 is enough for edge faces - manifold edge */
1196         BLI_buffer_declare_static(BMFace *, edge_loops, BLI_BUFFER_NOP, 2);
1197         BLI_buffer_declare_static(BMFace *, deleted_faces, BLI_BUFFER_NOP, 32);
1198         const int cd_vert_mask_offset = CustomData_get_offset(&bvh->bm->vdata, CD_PAINT_MASK);
1199
1200         bool modified = false;
1201         int n;
1202
1203         if (mode & PBVH_Collapse) {
1204                 EdgeQueue q;
1205                 BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *[2]), 0, 128, BLI_MEMPOOL_NOP);
1206                 EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset};
1207
1208                 short_edge_queue_create(&eq_ctx, bvh, center, radius);
1209                 modified |= !BLI_heap_is_empty(q.heap);
1210                 pbvh_bmesh_collapse_short_edges(&eq_ctx, bvh, &edge_loops,
1211                                                 &deleted_faces);
1212                 BLI_heap_free(q.heap, NULL);
1213                 BLI_mempool_destroy(queue_pool);
1214         }
1215
1216         if (mode & PBVH_Subdivide) {
1217                 EdgeQueue q;
1218                 BLI_mempool *queue_pool = BLI_mempool_create(sizeof(BMVert *[2]), 0, 128, BLI_MEMPOOL_NOP);
1219                 EdgeQueueContext eq_ctx = {&q, queue_pool, bvh->bm, cd_vert_mask_offset};
1220
1221                 long_edge_queue_create(&eq_ctx, bvh, center, radius);
1222                 modified |= !BLI_heap_is_empty(q.heap);
1223                 pbvh_bmesh_subdivide_long_edges(&eq_ctx, bvh, &edge_loops);
1224                 BLI_heap_free(q.heap, NULL);
1225                 BLI_mempool_destroy(queue_pool);
1226         }
1227         
1228         /* Unmark nodes */
1229         for (n = 0; n < bvh->totnode; n++) {
1230                 PBVHNode *node = &bvh->nodes[n];
1231
1232                 if (node->flag & PBVH_Leaf &&
1233                     node->flag & PBVH_UpdateTopology)
1234                 {
1235                         node->flag &= ~PBVH_UpdateTopology;
1236                 }
1237         }
1238         BLI_buffer_free(&edge_loops);
1239         BLI_buffer_free(&deleted_faces);
1240
1241         return modified;
1242 }
1243
1244 BLI_INLINE void bm_face_as_array_index_tri(BMFace *f, int r_index[3])
1245 {
1246         BMLoop *l = BM_FACE_FIRST_LOOP(f);
1247
1248         BLI_assert(f->len == 3);
1249
1250         r_index[0] = BM_elem_index_get(l->v); l = l->next;
1251         r_index[1] = BM_elem_index_get(l->v); l = l->next;
1252         r_index[2] = BM_elem_index_get(l->v);
1253 }
1254
1255 /* In order to perform operations on the original node coordinates
1256  * (currently just raycast), store the node's triangles and vertices.
1257  *
1258  * Skips triangles that are hidden. */
1259 void BKE_pbvh_bmesh_node_save_orig(PBVHNode *node)
1260 {
1261         GSetIterator gs_iter;
1262         int i, totvert, tottri;
1263
1264         /* Skip if original coords/triangles are already saved */
1265         if (node->bm_orco)
1266                 return;
1267
1268         totvert = (BLI_gset_size(node->bm_unique_verts) +
1269                    BLI_gset_size(node->bm_other_verts));
1270
1271         tottri = BLI_gset_size(node->bm_faces);
1272
1273         node->bm_orco = MEM_mallocN(sizeof(*node->bm_orco) * totvert, __func__);
1274         node->bm_ortri = MEM_mallocN(sizeof(*node->bm_ortri) * tottri, __func__);
1275
1276         /* Copy out the vertices and assign a temporary index */
1277         i = 0;
1278         GSET_ITER (gs_iter, node->bm_unique_verts) {
1279                 BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
1280                 copy_v3_v3(node->bm_orco[i], v->co);
1281                 BM_elem_index_set(v, i); /* set_dirty! */
1282                 i++;
1283         }
1284         GSET_ITER (gs_iter, node->bm_other_verts) {
1285                 BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
1286                 copy_v3_v3(node->bm_orco[i], v->co);
1287                 BM_elem_index_set(v, i); /* set_dirty! */
1288                 i++;
1289         }
1290
1291         /* Copy the triangles */
1292         i = 0;
1293         GSET_ITER (gs_iter, node->bm_faces) {
1294                 BMFace *f = BLI_gsetIterator_getKey(&gs_iter);
1295
1296                 if (BM_elem_flag_test(f, BM_ELEM_HIDDEN))
1297                         continue;
1298
1299 #if 0
1300                 BMIter bm_iter;
1301                 BMVert *v;
1302                 int j = 0;
1303                 BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) {
1304                         node->bm_ortri[i][j] = BM_elem_index_get(v);
1305                         j++;
1306                 }
1307 #else
1308                 bm_face_as_array_index_tri(f, node->bm_ortri[i]);
1309 #endif
1310                 i++;
1311         }
1312         node->bm_tot_ortri = i;
1313 }
1314
1315 void BKE_pbvh_bmesh_after_stroke(PBVH *bvh)
1316 {
1317         int i;
1318         for (i = 0; i < bvh->totnode; i++) {
1319                 PBVHNode *n = &bvh->nodes[i];
1320                 if (n->flag & PBVH_Leaf) {
1321                         /* Free orco/ortri data */
1322                         pbvh_bmesh_node_drop_orig(n);
1323
1324                         /* Recursively split nodes that have gotten too many
1325                          * elements */
1326                         pbvh_bmesh_node_limit_ensure(bvh, i);
1327                 }
1328         }
1329 }
1330
1331 void BKE_pbvh_bmesh_detail_size_set(PBVH *bvh, float detail_size)
1332 {
1333         bvh->bm_max_edge_len = detail_size;
1334         bvh->bm_min_edge_len = bvh->bm_max_edge_len * 0.4f;
1335 }
1336
1337 void BKE_pbvh_node_mark_topology_update(PBVHNode *node)
1338 {
1339         node->flag |= PBVH_UpdateTopology;
1340 }
1341
1342 GSet *BKE_pbvh_bmesh_node_unique_verts(PBVHNode *node)
1343 {
1344         return node->bm_unique_verts;
1345 }
1346
1347 GSet *BKE_pbvh_bmesh_node_other_verts(PBVHNode *node)
1348 {
1349         return node->bm_other_verts;
1350 }
1351
1352 struct GSet *BKE_pbvh_bmesh_node_faces(PBVHNode *node)
1353 {
1354         return node->bm_faces;
1355 }
1356
1357 /****************************** Debugging *****************************/
1358
1359 #if 0
1360
1361 void bli_gset_duplicate_key_check(GSet *gs)
1362 {
1363         GSetIterator gs_iter1, gs_iter2;
1364
1365         GSET_ITER (gs_iter1, gs) {
1366                 void *key1 = BLI_gsetIterator_getKey(&gs_iter1);
1367                 int dup = -1;
1368
1369                 GSET_ITER (gs_iter2, gs) {
1370                         void *key2 = BLI_gsetIterator_getKey(&gs_iter2);
1371
1372                         if (key1 == key2) {
1373                                 dup++;
1374                                 if (dup > 0) {
1375                                         BLI_assert(!"duplicate in hash");
1376                                 }
1377                         }
1378                 }
1379         }
1380 }
1381
1382 void bmesh_print(BMesh *bm)
1383 {
1384         BMIter iter, siter;
1385         BMVert *v;
1386         BMEdge *e;
1387         BMFace *f;
1388         BMLoop *l;
1389
1390         fprintf(stderr, "\nbm=%p, totvert=%d, totedge=%d, "
1391                 "totloop=%d, totface=%d\n",
1392                 bm, bm->totvert, bm->totedge,
1393                 bm->totloop, bm->totface);
1394
1395         fprintf(stderr, "vertices:\n");
1396         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
1397                 fprintf(stderr, "  %d co=(%.3f %.3f %.3f) oflag=%x\n",
1398                         BM_elem_index_get(v), v->co[0], v->co[1], v->co[2],
1399                         v->oflags[bm->stackdepth - 1].f);
1400         }
1401
1402         fprintf(stderr, "edges:\n");
1403         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
1404                 fprintf(stderr, "  %d v1=%d, v2=%d, oflag=%x\n",
1405                         BM_elem_index_get(e),
1406                         BM_elem_index_get(e->v1),
1407                         BM_elem_index_get(e->v2),
1408                         e->oflags[bm->stackdepth - 1].f);
1409         }
1410
1411         fprintf(stderr, "faces:\n");
1412         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
1413                 fprintf(stderr, "  %d len=%d, oflag=%x\n",
1414                         BM_elem_index_get(f), f->len,
1415                         f->oflags[bm->stackdepth - 1].f);
1416
1417                 fprintf(stderr, "    v: ");
1418                 BM_ITER_ELEM(v, &siter, f, BM_VERTS_OF_FACE) {
1419                         fprintf(stderr, "%d ", BM_elem_index_get(v));
1420                 }
1421                 fprintf(stderr, "\n");
1422
1423                 fprintf(stderr, "    e: ");
1424                 BM_ITER_ELEM(e, &siter, f, BM_EDGES_OF_FACE) {
1425                         fprintf(stderr, "%d ", BM_elem_index_get(e));
1426                 }
1427                 fprintf(stderr, "\n");
1428
1429                 fprintf(stderr, "    l: ");
1430                 BM_ITER_ELEM(l, &siter, f, BM_LOOPS_OF_FACE) {
1431                         fprintf(stderr, "%d(v=%d, e=%d) ",
1432                                 BM_elem_index_get(l),
1433                                 BM_elem_index_get(l->v),
1434                                 BM_elem_index_get(l->e));
1435                 }
1436                 fprintf(stderr, "\n");
1437         }       
1438 }
1439
1440 void pbvh_bmesh_print(PBVH *bvh)
1441 {
1442         GHashIterator gh_iter;
1443         GSetIterator gs_iter;
1444         int n;
1445
1446         fprintf(stderr, "\npbvh=%p\n", bvh);
1447         fprintf(stderr, "bm_face_to_node:\n");
1448         GHASH_ITER (gh_iter, bvh->bm_face_to_node) {
1449                 fprintf(stderr, "  %d -> %d\n",
1450                         BM_elem_index_get((BMFace *)BLI_ghashIterator_getKey(&gh_iter)),
1451                         GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter)));
1452         }
1453
1454         fprintf(stderr, "bm_vert_to_node:\n");
1455         GHASH_ITER (gh_iter, bvh->bm_vert_to_node) {
1456                 fprintf(stderr, "  %d -> %d\n",
1457                         BM_elem_index_get((BMVert *)BLI_ghashIterator_getKey(&gh_iter)),
1458                         GET_INT_FROM_POINTER(BLI_ghashIterator_getValue(&gh_iter)));
1459         }
1460
1461         for (n = 0; n < bvh->totnode; n++) {
1462                 PBVHNode *node = &bvh->nodes[n];
1463                 if (!(node->flag & PBVH_Leaf))
1464                         continue;
1465
1466                 fprintf(stderr, "node %d\n  faces:\n", n);
1467                 GHASH_ITER (gh_iter, node->bm_faces)
1468                         fprintf(stderr, "    %d\n",
1469                                 BM_elem_index_get((BMFace *)BLI_ghashIterator_getKey(&gh_iter)));
1470                 fprintf(stderr, "  unique verts:\n");
1471                 GSET_ITER (gs_iter, node->bm_unique_verts)
1472                         fprintf(stderr, "    %d\n",
1473                                 BM_elem_index_get((BMVert *)BLI_gsetIterator_getKey(&gs_iter)));
1474                 fprintf(stderr, "  other verts:\n");
1475                 GSET_ITER (gs_iter, node->bm_other_verts)
1476                         fprintf(stderr, "    %d\n",
1477                                 BM_elem_index_get((BMVert *)BLI_gsetIterator_getKey(&gs_iter)));
1478         }
1479 }
1480
1481 void print_flag_factors(int flag)
1482 {
1483         int i;
1484         printf("flag=0x%x:\n", flag);
1485         for (i = 0; i < 32; i++) {
1486                 if (flag & (1 << i)) {
1487                         printf("  %d (1 << %d)\n", 1 << i, i);
1488                 }
1489         }
1490 }
1491
1492 void pbvh_bmesh_verify(PBVH *bvh)
1493 {
1494         GHashIterator gh_iter;
1495         GSetIterator gs_iter;
1496         int i, vert_count = 0;
1497         BMIter iter;
1498         BMVert *vi;
1499
1500         /* Check faces */
1501         BLI_assert(bvh->bm->totface == BLI_ghash_size(bvh->bm_face_to_node));
1502         GHASH_ITER (gh_iter, bvh->bm_face_to_node) {
1503                 BMIter bm_iter;
1504                 BMVert *v;
1505                 BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
1506                 void *nip = BLI_ghashIterator_getValue(&gh_iter);
1507                 int ni = GET_INT_FROM_POINTER(nip);
1508                 PBVHNode *n = &bvh->nodes[ni];
1509
1510                 /* Check that the face's node is a leaf */
1511                 BLI_assert(n->flag & PBVH_Leaf);
1512
1513                 /* Check that the face's node knows it owns the face */
1514                 BLI_assert(BLI_gset_haskey(n->bm_faces, f));
1515
1516                 /* Check the face's vertices... */
1517                 BM_ITER_ELEM (v, &bm_iter, f, BM_VERTS_OF_FACE) {
1518                         PBVHNode *nv;
1519
1520                         /* Check that the vertex is in the node */
1521                         BLI_assert(BLI_gset_haskey(n->bm_unique_verts, v) ^
1522                                    BLI_gset_haskey(n->bm_other_verts, v));
1523
1524                         /* Check that the vertex has a node owner */
1525                         nv = pbvh_bmesh_node_lookup(bvh, bvh->bm_vert_to_node, v);
1526
1527                         /* Check that the vertex's node knows it owns the vert */
1528                         BLI_assert(BLI_gset_haskey(nv->bm_unique_verts, v));
1529
1530                         /* Check that the vertex isn't duplicated as an 'other' vert */
1531                         BLI_assert(!BLI_gset_haskey(nv->bm_other_verts, v));
1532                 }
1533         }
1534
1535         /* Check verts */
1536         BLI_assert(bvh->bm->totvert == BLI_ghash_size(bvh->bm_vert_to_node));
1537         GHASH_ITER (gh_iter, bvh->bm_vert_to_node) {
1538                 BMIter bm_iter;
1539                 BMVert *v = BLI_ghashIterator_getKey(&gh_iter);
1540                 BMFace *f;
1541                 void *nip = BLI_ghashIterator_getValue(&gh_iter);
1542                 int ni = GET_INT_FROM_POINTER(nip);
1543                 PBVHNode *n = &bvh->nodes[ni];
1544                 bool found;
1545
1546                 /* Check that the vert's node is a leaf */
1547                 BLI_assert(n->flag & PBVH_Leaf);
1548
1549                 /* Check that the vert's node knows it owns the vert */
1550                 BLI_assert(BLI_gset_haskey(n->bm_unique_verts, v));
1551
1552                 /* Check that the vertex isn't duplicated as an 'other' vert */
1553                 BLI_assert(!BLI_gset_haskey(n->bm_other_verts, v));
1554
1555                 /* Check that the vert's node also contains one of the vert's
1556                  * adjacent faces */
1557                 BM_ITER_ELEM (f, &bm_iter, v, BM_FACES_OF_VERT) {
1558                         if (BLI_ghash_lookup(bvh->bm_face_to_node, f) == nip) {
1559                                 found = true;
1560                                 break;
1561                         }
1562                 }
1563                 BLI_assert(found);
1564
1565 #if 1
1566                 /* total freak stuff, check if node exists somewhere else */
1567                 /* Slow */
1568                 for (i = 0; i < bvh->totnode; i++) {
1569                         PBVHNode *n = &bvh->nodes[i];
1570                         if (i != ni && n->bm_unique_verts)
1571                                 BLI_assert(!BLI_gset_haskey(n->bm_unique_verts, v));
1572                 }
1573
1574 #endif
1575         }
1576
1577 #if 0
1578         /* check that every vert belongs somewhere */
1579         /* Slow */
1580         BM_ITER_MESH (vi, &iter, bvh->bm, BM_VERTS_OF_MESH) {
1581                 bool has_unique = false;
1582                 for (i = 0; i < bvh->totnode; i++) {
1583                         PBVHNode *n = &bvh->nodes[i];
1584                         if ((n->bm_unique_verts != NULL) && BLI_gset_haskey(n->bm_unique_verts, vi))
1585                                 has_unique = true;
1586                 }
1587                 BLI_assert(has_unique);
1588                 vert_count++;
1589         }
1590
1591         /* if totvert differs from number of verts inside the hash. hash-totvert is checked above  */
1592         BLI_assert(vert_count == bvh->bm->totvert);
1593 #endif
1594
1595         /* Check that node elements are recorded in the top level */
1596         for (i = 0; i < bvh->totnode; i++) {
1597                 PBVHNode *n = &bvh->nodes[i];
1598                 if (n->flag & PBVH_Leaf) {
1599                         /* Check for duplicate entries */
1600                         /* Slow */
1601 #if 0
1602                         bli_gset_duplicate_key_check(n->bm_faces);
1603                         bli_gset_duplicate_key_check(n->bm_unique_verts);
1604                         bli_gset_duplicate_key_check(n->bm_other_verts);
1605 #endif
1606
1607                         GHASH_ITER (gh_iter, n->bm_faces) {
1608                                 BMFace *f = BLI_ghashIterator_getKey(&gh_iter);
1609                                 void *nip = BLI_ghash_lookup(bvh->bm_face_to_node, f);
1610                                 BLI_assert(BLI_ghash_haskey(bvh->bm_face_to_node, f));
1611                                 BLI_assert(GET_INT_FROM_POINTER(nip) == (n - bvh->nodes));
1612                         }
1613
1614                         GSET_ITER (gs_iter, n->bm_unique_verts) {
1615                                 BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
1616                                 void *nip = BLI_ghash_lookup(bvh->bm_vert_to_node, v);
1617                                 BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v));
1618                                 BLI_assert(!BLI_gset_haskey(n->bm_other_verts, v));
1619                                 BLI_assert(GET_INT_FROM_POINTER(nip) == (n - bvh->nodes));
1620                         }
1621
1622                         GSET_ITER (gs_iter, n->bm_other_verts) {
1623                                 BMVert *v = BLI_gsetIterator_getKey(&gs_iter);
1624                                 BLI_assert(BLI_ghash_haskey(bvh->bm_vert_to_node, v));
1625                                 BLI_assert(BM_vert_face_count(v) > 0);
1626                         }
1627                 }
1628         }
1629 }
1630
1631 #endif