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