ddc744550b2e06f1a9da4208fdc20e93b60603d2
[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(GHash *hull_triangles, BLI_mempool *pool,
123                                                           BMVert *v1, BMVert *v2, BMVert *v3)
124 {
125         HullTriangle *t;
126
127         t = BLI_mempool_calloc(pool);
128         t->v[0] = v1;
129         t->v[1] = v2;
130         t->v[2] = v3;
131
132         BLI_ghash_insert(hull_triangles, t, NULL);
133         normal_tri_v3(t->no, v1->co, v2->co, v3->co);
134 }
135
136 static int hull_point_tri_side(const HullTriangle *t, const float co[3])
137 {
138         float p[3], d;
139         sub_v3_v3v3(p, co, t->v[0]->co);
140         d = dot_v3v3(t->no, p);
141         if (d < 0) return -1;
142         else if (d > 0) return 1;
143         else return 0;
144 }
145
146 /* Get all hull triangles that vertex 'v' is outside of */
147 static GHash *hull_triangles_v_outside(GHash *hull_triangles, const BMVert *v)
148 {
149         GHash *outside;
150         GHashIterator iter;
151
152         outside = BLI_ghash_new(BLI_ghashutil_ptrhash,
153                                                         BLI_ghashutil_ptrcmp,
154                                                         "outside");
155
156         GHASH_ITER (iter, hull_triangles) {
157                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
158                 
159                 if (hull_point_tri_side(t, v->co) >= 0)
160                         BLI_ghash_insert(outside, t, NULL);
161         }
162
163         return outside;
164 }
165
166 /* Similar to above, but just get true/false rather than triangles */
167 static int hull_test_v_outside(GHash *hull_triangles, const BMVert *v)
168 {
169         GHashIterator iter;
170
171         GHASH_ITER (iter, hull_triangles) {
172                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
173                 
174                 if (hull_point_tri_side(t, v->co) >= 0)
175                         return TRUE;
176         }
177
178         return FALSE;
179 }
180
181
182 /* For vertex 'v', find which triangles must be deleted to extend the
183    hull; find the boundary edges of that hole so that it can be filled
184    with connections to the new vertex, and update the hull_triangles
185    to delete the marked triangles */
186 static void add_point(GHash *hull_triangles, BLI_mempool *hull_pool,
187                                           BLI_mempool *edge_pool, GHash *outside, BMVert *v)
188 {
189         ListBase edges = {NULL, NULL};
190         HullBoundaryEdge *e, *next;
191         GHashIterator iter;
192
193         GHASH_ITER (iter, outside) {
194                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
195                 expand_boundary_edges(&edges, edge_pool, t);
196                 
197                 /* Delete the triangle */
198                 BLI_ghash_remove(hull_triangles, t, NULL, NULL);
199                 BLI_mempool_free(hull_pool, t);
200         }
201
202         /* Fill hole boundary with triangles to new point */
203         for (e = edges.first; e; e = next) {
204                 next = e->next;
205                 hull_add_triangle(hull_triangles, hull_pool, e->v[0], e->v[1], v);
206                 BLI_mempool_free(edge_pool, e);
207         }
208 }
209
210 static BMFace *hull_find_example_face(BMesh *bm, BMEdge *e)
211 {
212         BMIter iter;
213         BMFace *f;
214
215         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
216                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT) ||
217                         !BMO_elem_flag_test(bm, f, HULL_FLAG_OUTPUT_GEOM))
218                         return f;
219         }
220
221         return NULL;
222 }
223
224 static void hull_output_triangles(BMesh *bm, GHash *hull_triangles)
225 {
226         GHashIterator iter;
227         
228         GHASH_ITER (iter, hull_triangles) {
229                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
230
231                 if (!t->skip) {
232                         BMEdge *edges[3] = {
233                                 BM_edge_create(bm, t->v[0], t->v[1], NULL, TRUE),
234                                 BM_edge_create(bm, t->v[1], t->v[2], NULL, TRUE),
235                                 BM_edge_create(bm, t->v[2], t->v[0], NULL, TRUE)
236                         };
237                         BMFace *f, *example = NULL;
238                         int i;
239
240                         /* Look for an adjacent face that existed before the hull */
241                         for (i = 0; i < 3; i++) {
242                                 if (!example)
243                                         example = hull_find_example_face(bm, edges[i]);
244                         }
245
246                         f = BM_face_create_quad_tri_v(bm, t->v, 3, example, FALSE);
247                         BM_face_copy_shared(bm, f);
248
249                         /* Mark face/verts/edges for 'geomout' slot and select */
250                         BMO_elem_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
251                         BM_face_select_set(bm, f, TRUE);
252                         for (i = 0; i < 3; i++) {
253                                 BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_OUTPUT_GEOM);
254                                 BMO_elem_flag_enable(bm, edges[i], HULL_FLAG_OUTPUT_GEOM);
255                         }
256                 }
257         }
258 }
259
260
261
262 /***************************** Final Edges ****************************/
263
264 typedef struct {
265         GHash *edges;
266         BLI_mempool *base_pool, *link_pool;
267 } HullFinalEdges;
268
269 static LinkData *final_edges_find_link(ListBase *adj, BMVert *v)
270 {
271         LinkData *link;
272
273         for (link = adj->first; link; link = link->next) {
274                 if (link->data == v)
275                         return link;
276         }
277
278         return NULL;
279 }
280
281 static int hull_final_edges_lookup(HullFinalEdges *final_edges,
282                                                                    BMVert *v1, BMVert *v2)
283 {
284         ListBase *adj;
285
286         /* Use lower vertex pointer for hash key */
287         if (v1 > v2)
288                 SWAP(BMVert*, v1, v2);
289
290         adj = BLI_ghash_lookup(final_edges->edges, v1);
291         if (!adj)
292                 return FALSE;
293
294         return !!final_edges_find_link(adj, v2);
295 }
296
297 /* Used for checking whether a pre-existing edge lies on the hull */
298 static HullFinalEdges *hull_final_edges(GHash *hull_triangles)
299 {
300         HullFinalEdges *final_edges;
301         GHashIterator iter;
302         
303         final_edges = MEM_callocN(sizeof(HullFinalEdges), "HullFinalEdges");
304         final_edges->edges = BLI_ghash_new(BLI_ghashutil_ptrhash,
305                                                                            BLI_ghashutil_ptrcmp,
306                                                                            "final edges ghash");
307         final_edges->base_pool = BLI_mempool_create(sizeof(ListBase), 128, 128, 0);
308         final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 128, 128, 0);
309
310         GHASH_ITER (iter, hull_triangles) {
311                 LinkData *link;
312                 int i;
313                 
314                 for (i = 0; i < 3; i++) {
315                         HullTriangle *t = BLI_ghashIterator_getKey(&iter);
316                         BMVert *v1 = t->v[i];
317                         BMVert *v2 = t->v[(i + 1) % 3];
318                         ListBase *adj;
319
320                         /* Use lower vertex pointer for hash key */
321                         if (v1 > v2)
322                                 SWAP(BMVert*, v1, v2);
323
324                         adj = BLI_ghash_lookup(final_edges->edges, v1);
325                         if (!adj) {
326                                 adj = BLI_mempool_calloc(final_edges->base_pool);
327                                 BLI_ghash_insert(final_edges->edges, v1, adj);
328                         }
329
330                         if (!final_edges_find_link(adj, v2)) {
331                                 link = BLI_mempool_calloc(final_edges->link_pool);
332                                 link->data = v2;
333                                 BLI_addtail(adj, link);
334                         }
335                 }
336         }
337
338         return final_edges;
339 }
340
341 static void hull_final_edges_free(HullFinalEdges *final_edges)
342 {
343         BLI_ghash_free(final_edges->edges, NULL, NULL);
344         BLI_mempool_destroy(final_edges->base_pool);
345         BLI_mempool_destroy(final_edges->link_pool);
346         MEM_freeN(final_edges);
347 }
348
349
350
351 /************************* Initial Tetrahedron ************************/
352
353 static void hull_add_tetrahedron(GHash *hull_triangles, BLI_mempool *pool,
354                                                                  BMVert *tetra[4])
355 {
356         float center[3];
357         int i, indices[4][3] = {
358                 {0, 1, 2},
359                 {0, 2, 3},
360                 {1, 0, 3},
361                 {2, 1, 3}};
362
363         /* Calculate center */
364         zero_v3(center);
365         for (i = 0; i < 4; i++)
366                 add_v3_v3(center, tetra[i]->co);
367         mul_v3_fl(center, 0.25f);
368
369         for (i = 0; i < 4; i++) {
370                 BMVert *v1 = tetra[indices[i][0]];
371                 BMVert *v2 = tetra[indices[i][1]];
372                 BMVert *v3 = tetra[indices[i][2]];
373                 float no[3], d[3];
374
375                 normal_tri_v3(no, v1->co, v2->co, v3->co);
376                 sub_v3_v3v3(d, center, v1->co);
377                 if (dot_v3v3(no, d) > 0)
378                         SWAP(BMVert*, v1, v3);
379
380                 hull_add_triangle(hull_triangles, pool, v1, v2, v3);
381         }
382 }
383
384 /* For each axis, get the minimum and maximum input vertices */
385 static void hull_get_min_max(BMesh *bm, BMOperator *op,
386                                                          BMVert *min[3], BMVert *max[3])
387 {
388         BMOIter oiter;
389         BMVert *v;
390
391         min[0] = min[1] = min[2] = NULL;
392         max[0] = max[1] = max[2] = NULL;
393
394         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
395                 int i;
396                 
397                 for (i = 0; i < 3; i++) {
398                         if (!min[i] || v->co[i] < min[i]->co[i])
399                                 min[i] = v;
400                         if (!max[i] || v->co[i] > max[i]->co[i])
401                                 max[i] = v;
402                 }
403         }
404 }
405
406 /* Returns true if input is coplanar */
407 static int hull_find_large_tetrahedron(BMesh *bm, BMOperator *op,
408                                                                            BMVert *tetra[4])
409 {
410         BMVert *min[3], *max[3], *v;
411         BMOIter oiter;
412         float widest_axis_len, largest_dist, plane_normal[3];
413         int i, j, widest_axis;
414         
415         hull_get_min_max(bm, op, min, max);
416
417         /* Check for flat axis */
418         for (i = 0; i < 3; i++) {
419                 if (min[i] == max[i]) {
420                         return TRUE;
421                 }
422         }
423
424         /* Find widest axis */
425         widest_axis_len = 0;
426         for (i = 0; i < 3; i++) {
427                 float len = (max[i]->co[i] - min[i]->co[i]);
428                 if (len >= widest_axis_len) {
429                         widest_axis_len = len;
430                         widest_axis = i;
431                 }
432         }
433
434         /* Use widest axis for first two points */
435         tetra[0] = min[widest_axis];
436         tetra[1] = max[widest_axis];
437         BMO_elem_flag_enable(bm, tetra[0], HULL_FLAG_TETRA_VERT);
438         BMO_elem_flag_enable(bm, tetra[1], HULL_FLAG_TETRA_VERT);
439
440         /* Choose third vertex farthest from existing line segment */
441         largest_dist = 0;
442         for (i = 0; i < 3; i++) {
443                 BMVert *v;
444                 float dist;
445
446                 if (i == widest_axis)
447                         continue;
448
449                 v = min[i];
450                 for (j = 0; j < 2; j++) {
451                         dist = dist_to_line_segment_v3(v->co, tetra[0]->co, tetra[1]->co);
452                         if (dist > largest_dist) {
453                                 largest_dist = dist;
454                                 tetra[2] = v;
455                         }
456
457                         v = max[i];
458                 }
459         }
460
461         BMO_elem_flag_enable(bm, tetra[2], HULL_FLAG_TETRA_VERT);
462         /* Check for colinear vertices */
463         if (largest_dist < 0.0001)
464                 return TRUE;
465
466         /* Choose fourth point farthest from existing plane */
467         largest_dist = 0;
468         normal_tri_v3(plane_normal, tetra[0]->co, tetra[1]->co, tetra[2]->co);
469         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
470                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
471                         float dist = dist_to_plane_v3(v->co, tetra[0]->co, plane_normal);
472                         if (dist > largest_dist) {
473                                 largest_dist = dist;
474                                 tetra[3] = v;
475                         }
476                 }
477         }
478
479         BMO_elem_flag_enable(bm, tetra[3], HULL_FLAG_TETRA_VERT);
480         if (largest_dist < 0.0001)
481                 return TRUE;
482
483         return FALSE;
484 }
485
486
487
488 /**************************** Final Output ****************************/
489
490 static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
491                                                                         HullFinalEdges *final_edges)
492 {
493         GHashIterator hull_iter;
494
495         GHASH_ITER (hull_iter, hull_triangles) {
496                 HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter);
497                 BMIter bm_iter1, bm_iter2;
498                 BMFace *f;
499                 int f_on_hull;
500
501                 BM_ITER_ELEM (f, &bm_iter1, t->v[0], BM_FACES_OF_VERT) {
502                         BMEdge *e;
503
504                         /* Check that all the face's edges are on the hull,
505                            otherwise can't reuse it */
506                         f_on_hull = TRUE;
507                         BM_ITER_ELEM (e, &bm_iter2, f, BM_EDGES_OF_FACE) {
508                                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2)) {
509                                         f_on_hull = FALSE;
510                                         break;
511                                 }
512                         }
513                         
514                         /* Note: can't change ghash while iterating, so mark
515                            with 'skip' flag rather than deleting triangles */
516                         if (BM_vert_in_face(f, t->v[1]) &&
517                                 BM_vert_in_face(f, t->v[2]) && f_on_hull) {
518                                 t->skip = TRUE;
519                                 BMO_elem_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
520                                 BMO_elem_flag_enable(bm, f, HULL_FLAG_HOLE);
521                         }
522                 }
523         }
524 }
525
526 static void hull_mark_interior_elements(BMesh *bm, BMOperator *op,
527                                                                                 GHash *hull_triangles,
528                                                                                 HullFinalEdges *final_edges)
529 {
530         BMVert *v;
531         BMEdge *e;
532         BMFace *f;
533         BMOIter oiter;
534
535         /* Check all input vertices again to see if they are actually part
536            of the hull */
537         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
538                 if (!hull_test_v_outside(hull_triangles, v)) {
539                         /* Mark for 'interior_verts' slot */
540                         BMO_elem_flag_enable(bm, v, HULL_FLAG_INTERIOR_ELE);
541                 }
542         }
543
544         /* Check for interior edges too */
545         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
546                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2))
547                         BMO_elem_flag_enable(bm, e, HULL_FLAG_INTERIOR_ELE);
548         }
549
550         /* Mark all input faces as interior, some may be unmarked in
551            hull_remove_overlapping() */
552         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
553                 BMO_elem_flag_enable(bm, f, HULL_FLAG_INTERIOR_ELE);
554         }
555 }
556
557 static void hull_tag_unused(BMesh *bm, BMOperator *op)
558 {
559         BMIter iter;
560         BMOIter oiter;
561         BMVert *v;
562         BMEdge *e;
563         BMFace *f;
564
565         /* Mark vertices, edges, and faces that are already marked
566            interior (i.e. were already part of the input, but not part of
567            the hull), but that aren't also used by elements outside the
568            input set */
569         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
570                 if (BMO_elem_flag_test(bm, v, HULL_FLAG_INTERIOR_ELE)) {
571                         int del = TRUE;
572                 
573                         BM_ITER_ELEM(e, &iter, v, BM_EDGES_OF_VERT) {
574                                 if (!BMO_elem_flag_test(bm, e, HULL_FLAG_INPUT)) {
575                                         del = FALSE;
576                                         break;
577                                 }
578                         }
579
580                         BM_ITER_ELEM(f, &iter, v, BM_FACES_OF_VERT) {
581                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
582                                         del = FALSE;
583                                         break;
584                                 }
585                         }
586
587                         if (del)
588                                 BMO_elem_flag_enable(bm, v, HULL_FLAG_DEL);
589                 }
590         }
591
592         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
593                 if (BMO_elem_flag_test(bm, e, HULL_FLAG_INTERIOR_ELE)) {
594                         int del = TRUE;
595
596                         BM_ITER_ELEM(f, &iter, e, BM_FACES_OF_EDGE) {
597                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
598                                         del = FALSE;
599                                         break;
600                                 }
601                         }
602
603                         if (del)
604                                 BMO_elem_flag_enable(bm, e, HULL_FLAG_DEL);
605                 }
606         }
607
608         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
609                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INTERIOR_ELE))
610                         BMO_elem_flag_enable(bm, f, HULL_FLAG_DEL);
611         }
612 }
613
614 void hull_tag_holes(BMesh *bm, BMOperator *op)
615 {
616         BMIter iter;
617         BMOIter oiter;
618         BMFace *f;
619         BMEdge *e;
620
621         /* Unmark any hole faces if they are isolated or part of a
622            border */
623         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
624                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
625                         BM_ITER_ELEM(e, &iter, f, BM_EDGES_OF_FACE) {
626                                 if (BM_edge_face_count(e) == 1) {
627                                         BMO_elem_flag_disable(bm, f, HULL_FLAG_HOLE);
628                                         break;
629                                 }
630                         }
631                 }
632         }
633
634         /* Mark edges too if all adjacent faces are holes */
635         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
636                 int hole = TRUE;
637                 
638                 BM_ITER_ELEM(f, &iter, e, BM_FACES_OF_EDGE) {
639                         if (!BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
640                                 hole = FALSE;
641                                 break;
642                         }
643                 }
644
645                 if (hole)
646                         BMO_elem_flag_enable(bm, e, HULL_FLAG_HOLE);
647         }
648 }
649
650 void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
651 {
652         HullFinalEdges *final_edges;
653         BLI_mempool *hull_pool, *edge_pool;
654         BMVert *v, *tetra[4];
655         BMElemF *ele;
656         BMOIter oiter;
657         GHash *hull_triangles;
658
659         /* Verify that at least four verts in the input */
660         if (BMO_slot_get(op, "input")->len < 4) {
661                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
662                                                 "Requires at least four vertices");
663                 return;
664         }
665
666         /* Initialize the convex hull by building a tetrahedron. A
667            degenerate tetrahedron can cause problems, so report error and
668            fail if the result is coplanar */
669         if (hull_find_large_tetrahedron(bm, op, tetra)) {
670                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
671                                                 "Input vertices are coplanar");
672                 return;
673         }
674
675         /* Tag input elements */
676         BMO_ITER (ele, &oiter, bm, op, "input", BM_ALL)
677                 BMO_elem_flag_enable(bm, ele, HULL_FLAG_INPUT);
678
679         edge_pool = BLI_mempool_create(sizeof(HullBoundaryEdge), 128, 128, 0);
680         hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0);
681         hull_triangles = BLI_ghash_new(BLI_ghashutil_ptrhash,
682                                                                    BLI_ghashutil_ptrcmp,
683                                                                    "hull_triangles");
684
685         /* Add tetrahedron triangles */
686         hull_add_tetrahedron(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(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, hull_triangles, 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 }