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