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