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