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