← Back to branch summary

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

« back to all changes in this revision

Viewing changes to source/blender/bmesh/operators/bmo_hull.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/bmesh/operators/bmo_hull.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
 * Contributor(s): Nicholas Bishop
 
19
 *
 
20
 * ***** END GPL LICENSE BLOCK *****
 
21
 */
 
22
 
 
23
/** \file blender/bmesh/operators/bmo_hull.c
 
24
 *  \ingroup bmesh
 
25
 */
 
26
 
 
27
#ifdef WITH_BULLET
 
28
 
 
29
#include "MEM_guardedalloc.h"
 
30
 
 
31
#include "BLI_array.h"
 
32
#include "BLI_ghash.h"
 
33
#include "BLI_listbase.h"
 
34
#include "BLI_math.h"
 
35
#include "BLI_utildefines.h"
 
36
 
 
37
#include "Bullet-C-Api.h"
 
38
 
 
39
/* XXX: using 128 for totelem and pchunk of mempool, no idea what good
 
40
 * values would be though */
 
41
#include "BLI_mempool.h"
 
42
 
 
43
#include "bmesh.h"
 
44
 
 
45
#include "intern/bmesh_operators_private.h"  /* own include */
 
46
 
 
47
/* Internal operator flags */
 
48
typedef enum {
 
49
        HULL_FLAG_INPUT =           (1 << 0),
 
50
        
 
51
        HULL_FLAG_INTERIOR_ELE =    (1 << 1),
 
52
        HULL_FLAG_OUTPUT_GEOM =     (1 << 2),
 
53
        
 
54
        HULL_FLAG_DEL =             (1 << 3),
 
55
        HULL_FLAG_HOLE =            (1 << 4)
 
56
} HullFlags;
 
57
 
 
58
/* Store hull triangles separate from BMesh faces until the end; this
 
59
 * way we don't have to worry about cleaning up extraneous edges or
 
60
 * incorrectly deleting existing geometry. */
 
61
typedef struct HullTriangle {
 
62
        BMVert *v[3];
 
63
        float no[3];
 
64
        int skip;
 
65
} HullTriangle;
 
66
 
 
67
 
 
68
 
 
69
/*************************** Hull Triangles ***************************/
 
70
 
 
71
static void hull_add_triangle(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
 
72
                              BMVert *v1, BMVert *v2, BMVert *v3)
 
73
{
 
74
        HullTriangle *t;
 
75
        int i;
 
76
 
 
77
        t = BLI_mempool_calloc(pool);
 
78
        t->v[0] = v1;
 
79
        t->v[1] = v2;
 
80
        t->v[2] = v3;
 
81
 
 
82
        /* Mark triangles vertices as not interior */
 
83
        for (i = 0; i < 3; i++)
 
84
                BMO_elem_flag_disable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
 
85
 
 
86
        BLI_ghash_insert(hull_triangles, t, NULL);
 
87
        normal_tri_v3(t->no, v1->co, v2->co, v3->co);
 
88
}
 
89
 
 
90
static BMFace *hull_find_example_face(BMesh *bm, BMEdge *e)
 
91
{
 
92
        BMIter iter;
 
93
        BMFace *f;
 
94
 
 
95
        BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
 
96
                if (BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT) ||
 
97
                    !BMO_elem_flag_test(bm, f, HULL_FLAG_OUTPUT_GEOM))
 
98
                {
 
99
                        return f;
 
100
                }
 
101
        }
 
102
 
 
103
        return NULL;
 
104
}
 
105
 
 
106
static void hull_output_triangles(BMesh *bm, GHash *hull_triangles)
 
107
{
 
108
        GHashIterator iter;
 
109
        
 
110
        GHASH_ITER (iter, hull_triangles) {
 
111
                HullTriangle *t = BLI_ghashIterator_getKey(&iter);
 
112
                int i;
 
113
 
 
114
                if (!t->skip) {
 
115
                        BMEdge *edges[3] = {
 
116
                                BM_edge_create(bm, t->v[0], t->v[1], NULL, BM_CREATE_NO_DOUBLE),
 
117
                                BM_edge_create(bm, t->v[1], t->v[2], NULL, BM_CREATE_NO_DOUBLE),
 
118
                                BM_edge_create(bm, t->v[2], t->v[0], NULL, BM_CREATE_NO_DOUBLE)
 
119
                        };
 
120
                        BMFace *f, *example = NULL;
 
121
 
 
122
                        if (BM_face_exists(t->v, 3, &f)) {
 
123
                                /* If the operator is run with "use_existing_faces"
 
124
                                 * disabled, but an output face in the hull is the
 
125
                                 * same as a face in the existing mesh, it should not
 
126
                                 * be marked as unused or interior. */
 
127
                                BMO_elem_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
 
128
                                BMO_elem_flag_disable(bm, f, HULL_FLAG_HOLE);
 
129
                                BMO_elem_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
 
130
                        }
 
131
                        else {
 
132
                                /* Look for an adjacent face that existed before the hull */
 
133
                                for (i = 0; i < 3; i++) {
 
134
                                        if (!example)
 
135
                                                example = hull_find_example_face(bm, edges[i]);
 
136
                                }
 
137
 
 
138
                                /* Create new hull face */
 
139
                                f = BM_face_create_quad_tri_v(bm, t->v, 3, example, true);
 
140
                                BM_face_copy_shared(bm, f);
 
141
                        }
 
142
                        /* Mark face for 'geom.out' slot and select */
 
143
                        BMO_elem_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
 
144
                        BM_face_select_set(bm, f, true);
 
145
 
 
146
                        /* Mark edges for 'geom.out' slot */
 
147
                        for (i = 0; i < 3; i++) {
 
148
                                BMO_elem_flag_enable(bm, edges[i], HULL_FLAG_OUTPUT_GEOM);
 
149
                        }
 
150
                }
 
151
                else {
 
152
                        /* Mark input edges for 'geom.out' slot */
 
153
                        for (i = 0; i < 3; i++) {
 
154
                                const int next = (i == 2 ? 0 : i + 1);
 
155
                                BMEdge *e = BM_edge_exists(t->v[i], t->v[next]);
 
156
                                if (e &&
 
157
                                        BMO_elem_flag_test(bm, e, HULL_FLAG_INPUT) &&
 
158
                                        !BMO_elem_flag_test(bm, e, HULL_FLAG_HOLE)) {
 
159
                                        BMO_elem_flag_enable(bm, e, HULL_FLAG_OUTPUT_GEOM);
 
160
                                }
 
161
                        }
 
162
                }
 
163
 
 
164
                /* Mark verts for 'geom.out' slot */
 
165
                for (i = 0; i < 3; i++) {
 
166
                        BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_OUTPUT_GEOM);
 
167
                }
 
168
        }
 
169
}
 
170
 
 
171
 
 
172
 
 
173
/***************************** Final Edges ****************************/
 
174
 
 
175
typedef struct {
 
176
        GHash *edges;
 
177
        BLI_mempool *base_pool, *link_pool;
 
178
} HullFinalEdges;
 
179
 
 
180
static LinkData *final_edges_find_link(ListBase *adj, BMVert *v)
 
181
{
 
182
        LinkData *link;
 
183
 
 
184
        for (link = adj->first; link; link = link->next) {
 
185
                if (link->data == v)
 
186
                        return link;
 
187
        }
 
188
 
 
189
        return NULL;
 
190
}
 
191
 
 
192
static int hull_final_edges_lookup(HullFinalEdges *final_edges,
 
193
                                   BMVert *v1, BMVert *v2)
 
194
{
 
195
        ListBase *adj;
 
196
 
 
197
        /* Use lower vertex pointer for hash key */
 
198
        if (v1 > v2)
 
199
                SWAP(BMVert *, v1, v2);
 
200
 
 
201
        adj = BLI_ghash_lookup(final_edges->edges, v1);
 
202
        if (!adj)
 
203
                return false;
 
204
 
 
205
        return !!final_edges_find_link(adj, v2);
 
206
}
 
207
 
 
208
/* Used for checking whether a pre-existing edge lies on the hull */
 
209
static HullFinalEdges *hull_final_edges(GHash *hull_triangles)
 
210
{
 
211
        HullFinalEdges *final_edges;
 
212
        GHashIterator iter;
 
213
        
 
214
        final_edges = MEM_callocN(sizeof(HullFinalEdges), "HullFinalEdges");
 
215
        final_edges->edges = BLI_ghash_ptr_new("final edges ghash");
 
216
        final_edges->base_pool = BLI_mempool_create(sizeof(ListBase), 128, 128, 0);
 
217
        final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 128, 128, 0);
 
218
 
 
219
        GHASH_ITER (iter, hull_triangles) {
 
220
                LinkData *link;
 
221
                int i;
 
222
                
 
223
                for (i = 0; i < 3; i++) {
 
224
                        HullTriangle *t = BLI_ghashIterator_getKey(&iter);
 
225
                        BMVert *v1 = t->v[i];
 
226
                        BMVert *v2 = t->v[(i + 1) % 3];
 
227
                        ListBase *adj;
 
228
 
 
229
                        /* Use lower vertex pointer for hash key */
 
230
                        if (v1 > v2)
 
231
                                SWAP(BMVert *, v1, v2);
 
232
 
 
233
                        adj = BLI_ghash_lookup(final_edges->edges, v1);
 
234
                        if (!adj) {
 
235
                                adj = BLI_mempool_calloc(final_edges->base_pool);
 
236
                                BLI_ghash_insert(final_edges->edges, v1, adj);
 
237
                        }
 
238
 
 
239
                        if (!final_edges_find_link(adj, v2)) {
 
240
                                link = BLI_mempool_calloc(final_edges->link_pool);
 
241
                                link->data = v2;
 
242
                                BLI_addtail(adj, link);
 
243
                        }
 
244
                }
 
245
        }
 
246
 
 
247
        return final_edges;
 
248
}
 
249
 
 
250
static void hull_final_edges_free(HullFinalEdges *final_edges)
 
251
{
 
252
        BLI_ghash_free(final_edges->edges, NULL, NULL);
 
253
        BLI_mempool_destroy(final_edges->base_pool);
 
254
        BLI_mempool_destroy(final_edges->link_pool);
 
255
        MEM_freeN(final_edges);
 
256
}
 
257
 
 
258
 
 
259
 
 
260
/**************************** Final Output ****************************/
 
261
 
 
262
static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
 
263
                                    HullFinalEdges *final_edges)
 
264
{
 
265
        GHashIterator hull_iter;
 
266
 
 
267
        GHASH_ITER (hull_iter, hull_triangles) {
 
268
                HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter);
 
269
                BMIter bm_iter1, bm_iter2;
 
270
                BMFace *f;
 
271
                bool f_on_hull;
 
272
 
 
273
                BM_ITER_ELEM (f, &bm_iter1, t->v[0], BM_FACES_OF_VERT) {
 
274
                        BMEdge *e;
 
275
 
 
276
                        /* Check that all the face's edges are on the hull,
 
277
                         * otherwise can't reuse it */
 
278
                        f_on_hull = true;
 
279
                        BM_ITER_ELEM (e, &bm_iter2, f, BM_EDGES_OF_FACE) {
 
280
                                if (!hull_final_edges_lookup(final_edges, e->v1, e->v2)) {
 
281
                                        f_on_hull = false;
 
282
                                        break;
 
283
                                }
 
284
                        }
 
285
                        
 
286
                        /* Note: can't change ghash while iterating, so mark
 
287
                         * with 'skip' flag rather than deleting triangles */
 
288
                        if (BM_vert_in_face(f, t->v[1]) &&
 
289
                            BM_vert_in_face(f, t->v[2]) && f_on_hull)
 
290
                        {
 
291
                                t->skip = true;
 
292
                                BMO_elem_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
 
293
                                BMO_elem_flag_enable(bm, f, HULL_FLAG_HOLE);
 
294
                        }
 
295
                }
 
296
        }
 
297
}
 
298
 
 
299
static void hull_mark_interior_elements(BMesh *bm, BMOperator *op,
 
300
                                        HullFinalEdges *final_edges)
 
301
{
 
302
        BMEdge *e;
 
303
        BMFace *f;
 
304
        BMOIter oiter;
 
305
 
 
306
        /* Check for interior edges too */
 
307
        BMO_ITER (e, &oiter, op->slots_in, "input", BM_EDGE) {
 
308
                if (!hull_final_edges_lookup(final_edges, e->v1, e->v2))
 
309
                        BMO_elem_flag_enable(bm, e, HULL_FLAG_INTERIOR_ELE);
 
310
        }
 
311
 
 
312
        /* Mark all input faces as interior, some may be unmarked in
 
313
         * hull_remove_overlapping() */
 
314
        BMO_ITER (f, &oiter, op->slots_in, "input", BM_FACE) {
 
315
                BMO_elem_flag_enable(bm, f, HULL_FLAG_INTERIOR_ELE);
 
316
        }
 
317
}
 
318
 
 
319
static void hull_tag_unused(BMesh *bm, BMOperator *op)
 
320
{
 
321
        BMIter iter;
 
322
        BMOIter oiter;
 
323
        BMVert *v;
 
324
        BMEdge *e;
 
325
        BMFace *f;
 
326
 
 
327
        /* Mark vertices, edges, and faces that are already marked
 
328
         * interior (i.e. were already part of the input, but not part of
 
329
         * the hull), but that aren't also used by elements outside the
 
330
         * input set */
 
331
        BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
 
332
                if (BMO_elem_flag_test(bm, v, HULL_FLAG_INTERIOR_ELE)) {
 
333
                        bool del = true;
 
334
                
 
335
                        BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
 
336
                                if (!BMO_elem_flag_test(bm, e, HULL_FLAG_INPUT)) {
 
337
                                        del = false;
 
338
                                        break;
 
339
                                }
 
340
                        }
 
341
 
 
342
                        BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
 
343
                                if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
 
344
                                        del = false;
 
345
                                        break;
 
346
                                }
 
347
                        }
 
348
 
 
349
                        if (del)
 
350
                                BMO_elem_flag_enable(bm, v, HULL_FLAG_DEL);
 
351
                }
 
352
        }
 
353
 
 
354
        BMO_ITER (e, &oiter, op->slots_in, "input", BM_EDGE) {
 
355
                if (BMO_elem_flag_test(bm, e, HULL_FLAG_INTERIOR_ELE)) {
 
356
                        bool del = true;
 
357
 
 
358
                        BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
 
359
                                if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
 
360
                                        del = false;
 
361
                                        break;
 
362
                                }
 
363
                        }
 
364
 
 
365
                        if (del)
 
366
                                BMO_elem_flag_enable(bm, e, HULL_FLAG_DEL);
 
367
                }
 
368
        }
 
369
 
 
370
        BMO_ITER (f, &oiter, op->slots_in, "input", BM_FACE) {
 
371
                if (BMO_elem_flag_test(bm, f, HULL_FLAG_INTERIOR_ELE))
 
372
                        BMO_elem_flag_enable(bm, f, HULL_FLAG_DEL);
 
373
        }
 
374
}
 
375
 
 
376
static void hull_tag_holes(BMesh *bm, BMOperator *op)
 
377
{
 
378
        BMIter iter;
 
379
        BMOIter oiter;
 
380
        BMFace *f;
 
381
        BMEdge *e;
 
382
 
 
383
        /* Unmark any hole faces if they are isolated or part of a
 
384
         * border */
 
385
        BMO_ITER (f, &oiter, op->slots_in, "input", BM_FACE) {
 
386
                if (BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
 
387
                        BM_ITER_ELEM (e, &iter, f, BM_EDGES_OF_FACE) {
 
388
                                if (BM_edge_is_boundary(e)) {
 
389
                                        BMO_elem_flag_disable(bm, f, HULL_FLAG_HOLE);
 
390
                                        break;
 
391
                                }
 
392
                        }
 
393
                }
 
394
        }
 
395
 
 
396
        /* Mark edges too if all adjacent faces are holes and the edge is
 
397
         * not already isolated */
 
398
        BMO_ITER (e, &oiter, op->slots_in, "input", BM_EDGE) {
 
399
                bool hole = true;
 
400
                bool any_faces = false;
 
401
                
 
402
                BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
 
403
                        any_faces = true;
 
404
                        if (!BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
 
405
                                hole = false;
 
406
                                break;
 
407
                        }
 
408
                }
 
409
 
 
410
                if (hole && any_faces)
 
411
                        BMO_elem_flag_enable(bm, e, HULL_FLAG_HOLE);
 
412
        }
 
413
}
 
414
 
 
415
static int hull_input_vert_count(BMOperator *op)
 
416
{
 
417
        BMOIter oiter;
 
418
        BMVert *v;
 
419
        int count = 0;
 
420
 
 
421
        BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
 
422
                count++;
 
423
        }
 
424
 
 
425
        return count;
 
426
}
 
427
 
 
428
static BMVert **hull_input_verts_copy(BMOperator *op,
 
429
                                      const int num_input_verts)
 
430
{
 
431
        BMOIter oiter;
 
432
        BMVert *v;
 
433
        BMVert **input_verts = MEM_callocN(sizeof(*input_verts) *
 
434
                                           num_input_verts, AT);
 
435
        int i = 0;
 
436
 
 
437
        BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
 
438
                input_verts[i++] = v;
 
439
        }
 
440
 
 
441
        return input_verts;
 
442
}
 
443
 
 
444
static float (*hull_verts_for_bullet(BMVert **input_verts,
 
445
                                     const int num_input_verts))[3]
 
446
{
 
447
        float (*coords)[3] = MEM_callocN(sizeof(*coords) * num_input_verts, AT);
 
448
        int i;
 
449
 
 
450
        for (i = 0; i < num_input_verts; i++) {
 
451
                copy_v3_v3(coords[i], input_verts[i]->co);
 
452
        }
 
453
 
 
454
        return coords;
 
455
}
 
456
 
 
457
static BMVert **hull_verts_from_bullet(plConvexHull hull,
 
458
                                       BMVert **input_verts,
 
459
                                       const int num_input_verts)
 
460
{
 
461
        const int num_verts = plConvexHullNumVertices(hull);
 
462
        BMVert **hull_verts = MEM_mallocN(sizeof(*hull_verts) *
 
463
                                          num_verts, AT);
 
464
        int i;
 
465
 
 
466
        for (i = 0; i < num_verts; i++) {
 
467
                float co[3];
 
468
                int original_index;
 
469
                plConvexHullGetVertex(hull, i, co, &original_index);
 
470
 
 
471
                if (original_index >= 0 && original_index < num_input_verts) {
 
472
                        hull_verts[i] = input_verts[original_index];
 
473
                }
 
474
                else
 
475
                        BLI_assert(!"Unexpected new vertex in hull output");
 
476
        }
 
477
 
 
478
        return hull_verts;
 
479
}
 
480
 
 
481
static void hull_from_bullet(BMesh *bm, BMOperator *op,
 
482
                             GHash *hull_triangles,
 
483
                             BLI_mempool *pool)
 
484
{
 
485
        int *fvi = NULL;
 
486
        BLI_array_declare(fvi);
 
487
 
 
488
        BMVert **input_verts;
 
489
        float (*coords)[3];
 
490
        BMVert **hull_verts;
 
491
 
 
492
        plConvexHull hull;
 
493
        int i, count = 0;
 
494
 
 
495
        const int num_input_verts = hull_input_vert_count(op);
 
496
 
 
497
        input_verts = hull_input_verts_copy(op, num_input_verts);
 
498
        coords = hull_verts_for_bullet(input_verts, num_input_verts);
 
499
 
 
500
        hull = plConvexHullCompute(coords, num_input_verts);
 
501
        hull_verts = hull_verts_from_bullet(hull, input_verts, num_input_verts);
 
502
        
 
503
        count = plConvexHullNumFaces(hull);
 
504
        for (i = 0; i < count; i++) {
 
505
                const int len = plConvexHullGetFaceSize(hull, i);
 
506
 
 
507
                if (len > 2) {
 
508
                        BMVert *fv[3];
 
509
                        int j;
 
510
 
 
511
                        /* Get face vertex indices */
 
512
                        BLI_array_empty(fvi);
 
513
                        BLI_array_grow_items(fvi, len);
 
514
                        plConvexHullGetFaceVertices(hull, i, fvi);
 
515
 
 
516
                        /* Note: here we throw away any NGons from Bullet and turn
 
517
                         * them into triangle fans. Would be nice to use these
 
518
                         * directly, but will have to wait until HullTriangle goes
 
519
                         * away (TODO) */
 
520
                        fv[0] = hull_verts[fvi[0]];
 
521
                        for (j = 2; j < len; j++) {
 
522
                                fv[1] = hull_verts[fvi[j - 1]];
 
523
                                fv[2] = hull_verts[fvi[j]];
 
524
 
 
525
                                hull_add_triangle(bm, hull_triangles, pool,
 
526
                                                  fv[0], fv[1], fv[2]);
 
527
                        }
 
528
                }
 
529
        }
 
530
 
 
531
        BLI_array_free(fvi);
 
532
        MEM_freeN(hull_verts);
 
533
        MEM_freeN(coords);
 
534
        MEM_freeN(input_verts);
 
535
}
 
536
 
 
537
/* Check that there are at least three vertices in the input */
 
538
static int hull_num_input_verts_is_ok(BMOperator *op)
 
539
{
 
540
        BMOIter oiter;
 
541
        BMVert *v;
 
542
        int partial_num_verts = 0;
 
543
 
 
544
        BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
 
545
                partial_num_verts++;
 
546
                if (partial_num_verts >= 3)
 
547
                        break;
 
548
        }
 
549
 
 
550
        return (partial_num_verts >= 3);
 
551
}
 
552
 
 
553
void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
 
554
{
 
555
        HullFinalEdges *final_edges;
 
556
        BLI_mempool *hull_pool;
 
557
        BMElemF *ele;
 
558
        BMOIter oiter;
 
559
        GHash *hull_triangles;
 
560
 
 
561
        /* Verify that at least three verts in the input */
 
562
        if (!hull_num_input_verts_is_ok(op)) {
 
563
                BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
 
564
                                "Requires at least three vertices");
 
565
                return;
 
566
        }
 
567
 
 
568
        /* Tag input elements */
 
569
        BMO_ITER (ele, &oiter, op->slots_in, "input", BM_ALL) {
 
570
                BMO_elem_flag_enable(bm, ele, HULL_FLAG_INPUT);
 
571
                
 
572
                /* Mark all vertices as interior to begin with */
 
573
                if (ele->head.htype == BM_VERT)
 
574
                        BMO_elem_flag_enable(bm, ele, HULL_FLAG_INTERIOR_ELE);
 
575
        }
 
576
 
 
577
        hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0);
 
578
        hull_triangles = BLI_ghash_ptr_new("hull_triangles");
 
579
 
 
580
        hull_from_bullet(bm, op, hull_triangles, hull_pool);
 
581
 
 
582
        final_edges = hull_final_edges(hull_triangles);
 
583
        
 
584
        hull_mark_interior_elements(bm, op, final_edges);
 
585
 
 
586
        /* Remove hull triangles covered by an existing face */
 
587
        if (BMO_slot_bool_get(op->slots_in, "use_existing_faces")) {
 
588
                hull_remove_overlapping(bm, hull_triangles, final_edges);
 
589
 
 
590
                hull_tag_holes(bm, op);
 
591
        }
 
592
 
 
593
        /* Done with edges */
 
594
        hull_final_edges_free(final_edges);
 
595
 
 
596
        /* Convert hull triangles to BMesh faces */
 
597
        hull_output_triangles(bm, hull_triangles);
 
598
        BLI_mempool_destroy(hull_pool);
 
599
 
 
600
        BLI_ghash_free(hull_triangles, NULL, NULL);
 
601
 
 
602
        hull_tag_unused(bm, op);
 
603
 
 
604
        /* Output slot of input elements that ended up inside the hull
 
605
         * rather than part of it */
 
606
        BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_interior.out",
 
607
                                          BM_ALL_NOLOOP, HULL_FLAG_INTERIOR_ELE);
 
608
 
 
609
        /* Output slot of input elements that ended up inside the hull and
 
610
         * are are unused by other geometry. */
 
611
        BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_unused.out",
 
612
                                          BM_ALL_NOLOOP, HULL_FLAG_DEL);
 
613
 
 
614
        /* Output slot of faces and edges that were in the input and on
 
615
         * the hull (useful for cases like bridging where you want to
 
616
         * delete some input geometry) */
 
617
        BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_holes.out",
 
618
                                          BM_ALL_NOLOOP, HULL_FLAG_HOLE);
 
619
 
 
620
        /* Output slot of all hull vertices, faces, and edges */
 
621
        BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom.out",
 
622
                                          BM_ALL_NOLOOP, HULL_FLAG_OUTPUT_GEOM);
 
623
}
 
624
 
 
625
#endif  /* WITH_BULLET */