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