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