← Back to branch summary

~ubuntu-branches/ubuntu/trusty/blender/trusty

« back to all changes in this revision

Viewing changes to source/blender/blenkernel/intern/pbvh_bmesh.c

  • Committer: Package Import Robot
  • Author(s): Jeremy Bicha
  • Date: 2013-03-06 12:08:47 UTC
  • mfrom: (1.5.1) (14.1.8 experimental)
  • Revision ID: package-import@ubuntu.com-20130306120847-frjfaryb2zrotwcg
Tags: 2.66a-1ubuntu1
https://launchpad.net/bugs/1076930
https://launchpad.net/bugs/1089256
https://launchpad.net/bugs/1052743
https://launchpad.net/bugs/999024
* Resynchronize with Debian (LP: #1076930, #1089256, #1052743, #999024,
  #1122888, #1147084)
* debian/control:
  - Lower build-depends on libavcodec-dev since we're not
    doing the libav9 transition in Ubuntu yet

Show diffs side-by-side

added added

removed removed

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