style cleanup: block comments
[blender.git] / 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 #include "MEM_guardedalloc.h"
28
29 #include "BLI_ghash.h"
30 #include "BLI_listbase.h"
31 #include "BLI_math.h"
32 #include "BLI_utildefines.h"
33
34 /* XXX: using 128 for totelem and pchunk of mempool, no idea what good
35  * values would be though */
36 #include "BLI_mempool.h"
37
38 #include "bmesh.h"
39
40 /* Internal operator flags */
41 typedef enum {
42         HULL_FLAG_INPUT =           (1 << 0),
43         HULL_FLAG_TETRA_VERT =      (1 << 1),
44         
45         HULL_FLAG_INTERIOR_ELE =    (1 << 2),
46         HULL_FLAG_OUTPUT_GEOM =     (1 << 3),
47         
48         HULL_FLAG_DEL =             (1 << 4),
49         HULL_FLAG_HOLE =            (1 << 5)
50 } HullFlags;
51
52 /* Store hull triangles seperate from BMesh faces until the end; this
53  * way we don't have to worry about cleaning up extraneous edges or
54  * incorrectly deleting existing geometry. */
55 typedef struct HullTriangle {
56         BMVert *v[3];
57         float no[3];
58         int skip;
59 } HullTriangle;
60
61 /* These edges define the hole created in the hull by deleting faces
62  * that can "see" a new vertex (the boundary edges then form the edge
63  * of a new triangle fan that has the new vertex as its center) */
64 typedef struct HullBoundaryEdge {
65         struct HullBoundaryEdge *next, *prev;
66         BMVert *v[2];
67 } HullBoundaryEdge;
68
69
70
71 /*************************** Boundary Edges ***************************/
72
73 static int edge_match(BMVert *e1_0, BMVert *e1_1, BMVert *e2[2])
74 {
75         return (e1_0 == e2[0] && e1_1 == e2[1]) ||
76                (e1_0 == e2[1] && e1_1 == e2[0]);
77 }
78
79 /* Returns true if the edge (e1, e2) is already in edges; that edge is
80  * deleted here as well. if not found just returns 0 */
81 static int check_for_dup(ListBase *edges, BLI_mempool *pool,
82                          BMVert *e1, BMVert *e2)
83 {
84         HullBoundaryEdge *e, *next;
85
86         for (e = edges->first; e; e = next) {
87                 next = e->next;
88
89                 if (edge_match(e1, e2, e->v)) {
90                         /* remove the interior edge */
91                         BLI_remlink(edges, e);
92                         BLI_mempool_free(pool, e);
93                         return 1;
94                 }
95         }
96
97         return 0;
98 }
99
100 static void expand_boundary_edges(ListBase *edges, BLI_mempool *edge_pool,
101                                   const HullTriangle *t)
102 {
103         HullBoundaryEdge *new;
104         int i;
105
106         /* Insert each triangle edge into the boundary list; if any of
107          * its edges are already in there, remove the edge entirely */
108         for (i = 0; i < 3; i++) {
109                 if (!check_for_dup(edges, edge_pool, t->v[i], t->v[(i + 1) % 3])) {
110                         new = BLI_mempool_calloc(edge_pool);
111                         new->v[0] = t->v[i];
112                         new->v[1] = t->v[(i + 1) % 3];
113                         BLI_addtail(edges, new);
114                 }
115         }
116 }
117
118
119
120 /*************************** Hull Triangles ***************************/
121
122 static void hull_add_triangle(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
123                               BMVert *v1, BMVert *v2, BMVert *v3)
124 {
125         HullTriangle *t;
126         int i;
127
128         t = BLI_mempool_calloc(pool);
129         t->v[0] = v1;
130         t->v[1] = v2;
131         t->v[2] = v3;
132
133         /* Mark triangles vertices as not interior */
134         for (i = 0; i < 3; i++)
135                 BMO_elem_flag_disable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
136
137         BLI_ghash_insert(hull_triangles, t, NULL);
138         normal_tri_v3(t->no, v1->co, v2->co, v3->co);
139 }
140
141 static int hull_point_tri_side(const HullTriangle *t, const float co[3])
142 {
143         float p[3], d;
144         sub_v3_v3v3(p, co, t->v[0]->co);
145         d = dot_v3v3(t->no, p);
146         if (d < 0) return -1;
147         else if (d > 0) return 1;
148         else return 0;
149 }
150
151 /* Get all hull triangles that vertex 'v' is outside of */
152 static GHash *hull_triangles_v_outside(GHash *hull_triangles, const BMVert *v)
153 {
154         GHash *outside;
155         GHashIterator iter;
156
157         outside = BLI_ghash_ptr_new("outside");
158
159         GHASH_ITER (iter, hull_triangles) {
160                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
161                 
162                 if (hull_point_tri_side(t, v->co) > 0)
163                         BLI_ghash_insert(outside, t, NULL);
164         }
165
166         return outside;
167 }
168
169 /* For vertex 'v', find which triangles must be deleted to extend the
170  * hull; find the boundary edges of that hole so that it can be filled
171  * with connections to the new vertex, and update the hull_triangles
172  * to delete the marked triangles */
173 static void add_point(BMesh *bm, GHash *hull_triangles, BLI_mempool *hull_pool,
174                       BLI_mempool *edge_pool, GHash *outside, BMVert *v)
175 {
176         ListBase edges = {NULL, NULL};
177         HullBoundaryEdge *e, *next;
178         GHashIterator iter;
179
180         GHASH_ITER (iter, outside) {
181                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
182                 int i;
183                 
184                 expand_boundary_edges(&edges, edge_pool, t);
185
186                 /* Mark triangle's vertices as interior */
187                 for (i = 0; i < 3; i++)
188                         BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
189                 
190                 /* Delete the triangle */
191                 BLI_ghash_remove(hull_triangles, t, NULL, NULL);
192                 BLI_mempool_free(hull_pool, t);
193         }
194
195         /* Fill hole boundary with triangles to new point */
196         for (e = edges.first; e; e = next) {
197                 next = e->next;
198                 hull_add_triangle(bm, hull_triangles, hull_pool, e->v[0], e->v[1], v);
199                 BLI_mempool_free(edge_pool, e);
200         }
201 }
202
203 static BMFace *hull_find_example_face(BMesh *bm, BMEdge *e)
204 {
205         BMIter iter;
206         BMFace *f;
207
208         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
209                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT) ||
210                     !BMO_elem_flag_test(bm, f, HULL_FLAG_OUTPUT_GEOM))
211                 {
212                         return f;
213                 }
214         }
215
216         return NULL;
217 }
218
219 static void hull_output_triangles(BMesh *bm, GHash *hull_triangles)
220 {
221         GHashIterator iter;
222         
223         GHASH_ITER (iter, hull_triangles) {
224                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
225
226                 if (!t->skip) {
227                         BMEdge *edges[3] = {
228                                 BM_edge_create(bm, t->v[0], t->v[1], NULL, TRUE),
229                                 BM_edge_create(bm, t->v[1], t->v[2], NULL, TRUE),
230                                 BM_edge_create(bm, t->v[2], t->v[0], NULL, TRUE)
231                         };
232                         BMFace *f, *example = NULL;
233                         int i;
234
235                         /* Look for an adjacent face that existed before the hull */
236                         for (i = 0; i < 3; i++) {
237                                 if (!example)
238                                         example = hull_find_example_face(bm, edges[i]);
239                         }
240
241                         f = BM_face_create_quad_tri_v(bm, t->v, 3, example, FALSE);
242                         BM_face_copy_shared(bm, f);
243
244                         /* Mark face/verts/edges for 'geomout' slot and select */
245                         BMO_elem_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
246                         BM_face_select_set(bm, f, TRUE);
247                         for (i = 0; i < 3; i++) {
248                                 BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_OUTPUT_GEOM);
249                                 BMO_elem_flag_enable(bm, edges[i], HULL_FLAG_OUTPUT_GEOM);
250                         }
251                 }
252         }
253 }
254
255
256
257 /***************************** Final Edges ****************************/
258
259 typedef struct {
260         GHash *edges;
261         BLI_mempool *base_pool, *link_pool;
262 } HullFinalEdges;
263
264 static LinkData *final_edges_find_link(ListBase *adj, BMVert *v)
265 {
266         LinkData *link;
267
268         for (link = adj->first; link; link = link->next) {
269                 if (link->data == v)
270                         return link;
271         }
272
273         return NULL;
274 }
275
276 static int hull_final_edges_lookup(HullFinalEdges *final_edges,
277                                    BMVert *v1, BMVert *v2)
278 {
279         ListBase *adj;
280
281         /* Use lower vertex pointer for hash key */
282         if (v1 > v2)
283                 SWAP(BMVert *, v1, v2);
284
285         adj = BLI_ghash_lookup(final_edges->edges, v1);
286         if (!adj)
287                 return FALSE;
288
289         return !!final_edges_find_link(adj, v2);
290 }
291
292 /* Used for checking whether a pre-existing edge lies on the hull */
293 static HullFinalEdges *hull_final_edges(GHash *hull_triangles)
294 {
295         HullFinalEdges *final_edges;
296         GHashIterator iter;
297         
298         final_edges = MEM_callocN(sizeof(HullFinalEdges), "HullFinalEdges");
299         final_edges->edges = BLI_ghash_ptr_new("final edges ghash");
300         final_edges->base_pool = BLI_mempool_create(sizeof(ListBase), 128, 128, 0);
301         final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 128, 128, 0);
302
303         GHASH_ITER (iter, hull_triangles) {
304                 LinkData *link;
305                 int i;
306                 
307                 for (i = 0; i < 3; i++) {
308                         HullTriangle *t = BLI_ghashIterator_getKey(&iter);
309                         BMVert *v1 = t->v[i];
310                         BMVert *v2 = t->v[(i + 1) % 3];
311                         ListBase *adj;
312
313                         /* Use lower vertex pointer for hash key */
314                         if (v1 > v2)
315                                 SWAP(BMVert *, v1, v2);
316
317                         adj = BLI_ghash_lookup(final_edges->edges, v1);
318                         if (!adj) {
319                                 adj = BLI_mempool_calloc(final_edges->base_pool);
320                                 BLI_ghash_insert(final_edges->edges, v1, adj);
321                         }
322
323                         if (!final_edges_find_link(adj, v2)) {
324                                 link = BLI_mempool_calloc(final_edges->link_pool);
325                                 link->data = v2;
326                                 BLI_addtail(adj, link);
327                         }
328                 }
329         }
330
331         return final_edges;
332 }
333
334 static void hull_final_edges_free(HullFinalEdges *final_edges)
335 {
336         BLI_ghash_free(final_edges->edges, NULL, NULL);
337         BLI_mempool_destroy(final_edges->base_pool);
338         BLI_mempool_destroy(final_edges->link_pool);
339         MEM_freeN(final_edges);
340 }
341
342
343
344 /************************* Initial Tetrahedron ************************/
345
346 static void hull_add_tetrahedron(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
347                                  BMVert *tetra[4])
348 {
349         float center[3];
350         int i, indices[4][3] = {
351                 {0, 1, 2},
352                 {0, 2, 3},
353                 {1, 0, 3},
354                 {2, 1, 3}};
355
356         /* Calculate center */
357         zero_v3(center);
358         for (i = 0; i < 4; i++)
359                 add_v3_v3(center, tetra[i]->co);
360         mul_v3_fl(center, 0.25f);
361
362         for (i = 0; i < 4; i++) {
363                 BMVert *v1 = tetra[indices[i][0]];
364                 BMVert *v2 = tetra[indices[i][1]];
365                 BMVert *v3 = tetra[indices[i][2]];
366                 float no[3], d[3];
367
368                 normal_tri_v3(no, v1->co, v2->co, v3->co);
369                 sub_v3_v3v3(d, center, v1->co);
370                 if (dot_v3v3(no, d) > 0)
371                         SWAP(BMVert *, v1, v3);
372
373                 hull_add_triangle(bm, hull_triangles, pool, v1, v2, v3);
374         }
375 }
376
377 /* For each axis, get the minimum and maximum input vertices */
378 static void hull_get_min_max(BMesh *bm, BMOperator *op,
379                              BMVert *min[3], BMVert *max[3])
380 {
381         BMOIter oiter;
382         BMVert *v;
383
384         min[0] = min[1] = min[2] = NULL;
385         max[0] = max[1] = max[2] = NULL;
386
387         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
388                 int i;
389                 
390                 for (i = 0; i < 3; i++) {
391                         if (!min[i] || v->co[i] < min[i]->co[i])
392                                 min[i] = v;
393                         if (!max[i] || v->co[i] > max[i]->co[i])
394                                 max[i] = v;
395                 }
396         }
397 }
398
399 /* Returns true if input is coplanar */
400 static int hull_find_large_tetrahedron(BMesh *bm, BMOperator *op,
401                                        BMVert *tetra[4])
402 {
403         BMVert *min[3], *max[3], *v;
404         BMOIter oiter;
405         float widest_axis_len, largest_dist, plane_normal[3];
406         int i, j, widest_axis;
407         
408         tetra[0] = tetra[1] = tetra[2] = tetra[3] = NULL;
409         hull_get_min_max(bm, op, min, max);
410
411         /* Check for flat axis */
412         for (i = 0; i < 3; i++) {
413                 if (min[i] == max[i]) {
414                         return TRUE;
415                 }
416         }
417
418         /* Find widest axis */
419         widest_axis_len = 0.0f;
420         widest_axis = 0; /* set here in the unlikey case this isn't set below */
421         for (i = 0; i < 3; i++) {
422                 float len = (max[i]->co[i] - min[i]->co[i]);
423                 if (len >= widest_axis_len) {
424                         widest_axis_len = len;
425                         widest_axis = i;
426                 }
427         }
428
429         /* Use widest axis for first two points */
430         tetra[0] = min[widest_axis];
431         tetra[1] = max[widest_axis];
432         BMO_elem_flag_enable(bm, tetra[0], HULL_FLAG_TETRA_VERT);
433         BMO_elem_flag_enable(bm, tetra[1], HULL_FLAG_TETRA_VERT);
434
435         /* Choose third vertex farthest from existing line segment */
436         largest_dist = 0;
437         for (i = 0; i < 3; i++) {
438                 BMVert *v;
439                 float dist;
440
441                 if (i == widest_axis)
442                         continue;
443
444                 v = min[i];
445                 for (j = 0; j < 2; j++) {
446                         dist = dist_to_line_segment_v3(v->co, tetra[0]->co, tetra[1]->co);
447                         if (dist > largest_dist) {
448                                 largest_dist = dist;
449                                 tetra[2] = v;
450                         }
451
452                         v = max[i];
453                 }
454         }
455
456         if (tetra[2]) {
457                 BMO_elem_flag_enable(bm, tetra[2], HULL_FLAG_TETRA_VERT);
458         }
459         else {
460                 return TRUE;
461         }
462
463         /* Check for colinear vertices */
464         if (largest_dist < 0.0001f)
465                 return TRUE;
466
467         /* Choose fourth point farthest from existing plane */
468         largest_dist = 0;
469         normal_tri_v3(plane_normal, tetra[0]->co, tetra[1]->co, tetra[2]->co);
470         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
471                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
472                         float dist = fabsf(dist_to_plane_v3(v->co, tetra[0]->co, plane_normal));
473                         if (dist > largest_dist) {
474                                 largest_dist = dist;
475                                 tetra[3] = v;
476                         }
477                 }
478         }
479
480         if (tetra[3]) {
481                 BMO_elem_flag_enable(bm, tetra[3], HULL_FLAG_TETRA_VERT);
482         }
483         else {
484                 return TRUE;
485         }
486
487         if (largest_dist < 0.0001f)
488                 return TRUE;
489
490         return FALSE;
491 }
492
493
494
495 /**************************** Final Output ****************************/
496
497 static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
498                                     HullFinalEdges *final_edges)
499 {
500         GHashIterator hull_iter;
501
502         GHASH_ITER (hull_iter, hull_triangles) {
503                 HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter);
504                 BMIter bm_iter1, bm_iter2;
505                 BMFace *f;
506                 int f_on_hull;
507
508                 BM_ITER_ELEM (f, &bm_iter1, t->v[0], BM_FACES_OF_VERT) {
509                         BMEdge *e;
510
511                         /* Check that all the face's edges are on the hull,
512                          * otherwise can't reuse it */
513                         f_on_hull = TRUE;
514                         BM_ITER_ELEM (e, &bm_iter2, f, BM_EDGES_OF_FACE) {
515                                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2)) {
516                                         f_on_hull = FALSE;
517                                         break;
518                                 }
519                         }
520                         
521                         /* Note: can't change ghash while iterating, so mark
522                          * with 'skip' flag rather than deleting triangles */
523                         if (BM_vert_in_face(f, t->v[1]) &&
524                             BM_vert_in_face(f, t->v[2]) && f_on_hull)
525                         {
526                                 t->skip = TRUE;
527                                 BMO_elem_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
528                                 BMO_elem_flag_enable(bm, f, HULL_FLAG_HOLE);
529                         }
530                 }
531         }
532 }
533
534 static void hull_mark_interior_elements(BMesh *bm, BMOperator *op,
535                                         HullFinalEdges *final_edges)
536 {
537         BMEdge *e;
538         BMFace *f;
539         BMOIter oiter;
540
541         /* Check for interior edges too */
542         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
543                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2))
544                         BMO_elem_flag_enable(bm, e, HULL_FLAG_INTERIOR_ELE);
545         }
546
547         /* Mark all input faces as interior, some may be unmarked in
548          * hull_remove_overlapping() */
549         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
550                 BMO_elem_flag_enable(bm, f, HULL_FLAG_INTERIOR_ELE);
551         }
552 }
553
554 static void hull_tag_unused(BMesh *bm, BMOperator *op)
555 {
556         BMIter iter;
557         BMOIter oiter;
558         BMVert *v;
559         BMEdge *e;
560         BMFace *f;
561
562         /* Mark vertices, edges, and faces that are already marked
563          * interior (i.e. were already part of the input, but not part of
564          * the hull), but that aren't also used by elements outside the
565          * input set */
566         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
567                 if (BMO_elem_flag_test(bm, v, HULL_FLAG_INTERIOR_ELE)) {
568                         int del = TRUE;
569                 
570                         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
571                                 if (!BMO_elem_flag_test(bm, e, HULL_FLAG_INPUT)) {
572                                         del = FALSE;
573                                         break;
574                                 }
575                         }
576
577                         BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
578                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
579                                         del = FALSE;
580                                         break;
581                                 }
582                         }
583
584                         if (del)
585                                 BMO_elem_flag_enable(bm, v, HULL_FLAG_DEL);
586                 }
587         }
588
589         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
590                 if (BMO_elem_flag_test(bm, e, HULL_FLAG_INTERIOR_ELE)) {
591                         int del = TRUE;
592
593                         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
594                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
595                                         del = FALSE;
596                                         break;
597                                 }
598                         }
599
600                         if (del)
601                                 BMO_elem_flag_enable(bm, e, HULL_FLAG_DEL);
602                 }
603         }
604
605         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
606                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INTERIOR_ELE))
607                         BMO_elem_flag_enable(bm, f, HULL_FLAG_DEL);
608         }
609 }
610
611 void hull_tag_holes(BMesh *bm, BMOperator *op)
612 {
613         BMIter iter;
614         BMOIter oiter;
615         BMFace *f;
616         BMEdge *e;
617
618         /* Unmark any hole faces if they are isolated or part of a
619          * border */
620         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
621                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
622                         BM_ITER_ELEM (e, &iter, f, BM_EDGES_OF_FACE) {
623                                 if (BM_edge_face_count(e) == 1) {
624                                         BMO_elem_flag_disable(bm, f, HULL_FLAG_HOLE);
625                                         break;
626                                 }
627                         }
628                 }
629         }
630
631         /* Mark edges too if all adjacent faces are holes */
632         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
633                 int hole = TRUE;
634                 
635                 BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
636                         if (!BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
637                                 hole = FALSE;
638                                 break;
639                         }
640                 }
641
642                 if (hole)
643                         BMO_elem_flag_enable(bm, e, HULL_FLAG_HOLE);
644         }
645 }
646
647 void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
648 {
649         HullFinalEdges *final_edges;
650         BLI_mempool *hull_pool, *edge_pool;
651         BMVert *v, *tetra[4];
652         BMElemF *ele;
653         BMOIter oiter;
654         GHash *hull_triangles;
655
656         /* Verify that at least four verts in the input */
657         if (BMO_slot_get(op, "input")->len < 4) {
658                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
659                                 "Requires at least four vertices");
660                 return;
661         }
662
663         /* Initialize the convex hull by building a tetrahedron. A
664          * degenerate tetrahedron can cause problems, so report error and
665          * fail if the result is coplanar */
666         if (hull_find_large_tetrahedron(bm, op, tetra)) {
667                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
668                                 "Input vertices are coplanar");
669                 return;
670         }
671
672         /* Tag input elements */
673         BMO_ITER (ele, &oiter, bm, op, "input", BM_ALL) {
674                 BMO_elem_flag_enable(bm, ele, HULL_FLAG_INPUT);
675                 
676                 /* Mark all vertices as interior to begin with */
677                 if (ele->head.htype == BM_VERT)
678                         BMO_elem_flag_enable(bm, ele, HULL_FLAG_INTERIOR_ELE);
679         }
680
681         edge_pool = BLI_mempool_create(sizeof(HullBoundaryEdge), 128, 128, 0);
682         hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0);
683         hull_triangles = BLI_ghash_ptr_new("hull_triangles");
684
685         /* Add tetrahedron triangles */
686         hull_add_tetrahedron(bm, hull_triangles, hull_pool, tetra);
687
688         /* Expand hull to cover new vertices outside the existing hull */
689         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
690                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
691                         GHash *outside = hull_triangles_v_outside(hull_triangles, v);
692                         if (BLI_ghash_size(outside)) {
693                                 /* Expand hull and delete interior triangles */
694                                 add_point(bm, hull_triangles, hull_pool, edge_pool, outside, v);
695                         }
696                         BLI_ghash_free(outside, NULL, NULL);
697                 }
698         }
699
700         BLI_mempool_destroy(edge_pool);
701         final_edges = hull_final_edges(hull_triangles);
702         
703         hull_mark_interior_elements(bm, op, final_edges);
704
705         /* Remove hull triangles covered by an existing face */
706         if (BMO_slot_bool_get(op, "use_existing_faces")) {
707                 hull_remove_overlapping(bm, hull_triangles, final_edges);
708
709                 hull_tag_holes(bm, op);
710         }
711
712         /* Done with edges */
713         hull_final_edges_free(final_edges);
714
715         /* Convert hull triangles to BMesh faces */
716         hull_output_triangles(bm, hull_triangles);
717         BLI_mempool_destroy(hull_pool);
718
719         BLI_ghash_free(hull_triangles, NULL, NULL);
720
721         hull_tag_unused(bm, op);
722
723         /* Output slot of input elements that ended up inside the hull
724          * rather than part of it */
725         BMO_slot_buffer_from_enabled_flag(bm, op, "interior_geom", BM_ALL,
726                                           HULL_FLAG_INTERIOR_ELE);
727
728         /* Output slot of input elements that ended up inside the hull and
729          * are are unused by other geometry. */
730         BMO_slot_buffer_from_enabled_flag(bm, op, "unused_geom", BM_ALL,
731                                           HULL_FLAG_DEL);
732
733         /* Output slot of faces and edges that were in the input and on
734          * the hull (useful for cases like bridging where you want to
735          * delete some input geometry) */
736         BMO_slot_buffer_from_enabled_flag(bm, op, "holes_geom", BM_ALL,
737                                           HULL_FLAG_HOLE);
738
739         /* Output slot of all hull vertices, faces, and edges */
740         BMO_slot_buffer_from_enabled_flag(bm, op, "geomout", BM_ALL,
741                                           HULL_FLAG_OUTPUT_GEOM);
742 }