09ccbfec1b10325d60abb01bb294ed57a1783a7c
[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                 {
219                         return f;
220                 }
221         }
222
223         return NULL;
224 }
225
226 static void hull_output_triangles(BMesh *bm, GHash *hull_triangles)
227 {
228         GHashIterator iter;
229         
230         GHASH_ITER (iter, hull_triangles) {
231                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
232
233                 if (!t->skip) {
234                         BMEdge *edges[3] = {
235                                 BM_edge_create(bm, t->v[0], t->v[1], NULL, TRUE),
236                                 BM_edge_create(bm, t->v[1], t->v[2], NULL, TRUE),
237                                 BM_edge_create(bm, t->v[2], t->v[0], NULL, TRUE)
238                         };
239                         BMFace *f, *example = NULL;
240                         int i;
241
242                         /* Look for an adjacent face that existed before the hull */
243                         for (i = 0; i < 3; i++) {
244                                 if (!example)
245                                         example = hull_find_example_face(bm, edges[i]);
246                         }
247
248                         f = BM_face_create_quad_tri_v(bm, t->v, 3, example, FALSE);
249                         BM_face_copy_shared(bm, f);
250
251                         /* Mark face/verts/edges for 'geomout' slot and select */
252                         BMO_elem_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
253                         BM_face_select_set(bm, f, TRUE);
254                         for (i = 0; i < 3; i++) {
255                                 BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_OUTPUT_GEOM);
256                                 BMO_elem_flag_enable(bm, edges[i], HULL_FLAG_OUTPUT_GEOM);
257                         }
258                 }
259         }
260 }
261
262
263
264 /***************************** Final Edges ****************************/
265
266 typedef struct {
267         GHash *edges;
268         BLI_mempool *base_pool, *link_pool;
269 } HullFinalEdges;
270
271 static LinkData *final_edges_find_link(ListBase *adj, BMVert *v)
272 {
273         LinkData *link;
274
275         for (link = adj->first; link; link = link->next) {
276                 if (link->data == v)
277                         return link;
278         }
279
280         return NULL;
281 }
282
283 static int hull_final_edges_lookup(HullFinalEdges *final_edges,
284                                    BMVert *v1, BMVert *v2)
285 {
286         ListBase *adj;
287
288         /* Use lower vertex pointer for hash key */
289         if (v1 > v2)
290                 SWAP(BMVert *, v1, v2);
291
292         adj = BLI_ghash_lookup(final_edges->edges, v1);
293         if (!adj)
294                 return FALSE;
295
296         return !!final_edges_find_link(adj, v2);
297 }
298
299 /* Used for checking whether a pre-existing edge lies on the hull */
300 static HullFinalEdges *hull_final_edges(GHash *hull_triangles)
301 {
302         HullFinalEdges *final_edges;
303         GHashIterator iter;
304         
305         final_edges = MEM_callocN(sizeof(HullFinalEdges), "HullFinalEdges");
306         final_edges->edges = BLI_ghash_new(BLI_ghashutil_ptrhash,
307                                            BLI_ghashutil_ptrcmp,
308                                            "final edges ghash");
309         final_edges->base_pool = BLI_mempool_create(sizeof(ListBase), 128, 128, 0);
310         final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 128, 128, 0);
311
312         GHASH_ITER (iter, hull_triangles) {
313                 LinkData *link;
314                 int i;
315                 
316                 for (i = 0; i < 3; i++) {
317                         HullTriangle *t = BLI_ghashIterator_getKey(&iter);
318                         BMVert *v1 = t->v[i];
319                         BMVert *v2 = t->v[(i + 1) % 3];
320                         ListBase *adj;
321
322                         /* Use lower vertex pointer for hash key */
323                         if (v1 > v2)
324                                 SWAP(BMVert *, v1, v2);
325
326                         adj = BLI_ghash_lookup(final_edges->edges, v1);
327                         if (!adj) {
328                                 adj = BLI_mempool_calloc(final_edges->base_pool);
329                                 BLI_ghash_insert(final_edges->edges, v1, adj);
330                         }
331
332                         if (!final_edges_find_link(adj, v2)) {
333                                 link = BLI_mempool_calloc(final_edges->link_pool);
334                                 link->data = v2;
335                                 BLI_addtail(adj, link);
336                         }
337                 }
338         }
339
340         return final_edges;
341 }
342
343 static void hull_final_edges_free(HullFinalEdges *final_edges)
344 {
345         BLI_ghash_free(final_edges->edges, NULL, NULL);
346         BLI_mempool_destroy(final_edges->base_pool);
347         BLI_mempool_destroy(final_edges->link_pool);
348         MEM_freeN(final_edges);
349 }
350
351
352
353 /************************* Initial Tetrahedron ************************/
354
355 static void hull_add_tetrahedron(GHash *hull_triangles, BLI_mempool *pool,
356                                  BMVert *tetra[4])
357 {
358         float center[3];
359         int i, indices[4][3] = {
360                 {0, 1, 2},
361                 {0, 2, 3},
362                 {1, 0, 3},
363                 {2, 1, 3}};
364
365         /* Calculate center */
366         zero_v3(center);
367         for (i = 0; i < 4; i++)
368                 add_v3_v3(center, tetra[i]->co);
369         mul_v3_fl(center, 0.25f);
370
371         for (i = 0; i < 4; i++) {
372                 BMVert *v1 = tetra[indices[i][0]];
373                 BMVert *v2 = tetra[indices[i][1]];
374                 BMVert *v3 = tetra[indices[i][2]];
375                 float no[3], d[3];
376
377                 normal_tri_v3(no, v1->co, v2->co, v3->co);
378                 sub_v3_v3v3(d, center, v1->co);
379                 if (dot_v3v3(no, d) > 0)
380                         SWAP(BMVert *, v1, v3);
381
382                 hull_add_triangle(hull_triangles, pool, v1, v2, v3);
383         }
384 }
385
386 /* For each axis, get the minimum and maximum input vertices */
387 static void hull_get_min_max(BMesh *bm, BMOperator *op,
388                              BMVert *min[3], BMVert *max[3])
389 {
390         BMOIter oiter;
391         BMVert *v;
392
393         min[0] = min[1] = min[2] = NULL;
394         max[0] = max[1] = max[2] = NULL;
395
396         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
397                 int i;
398                 
399                 for (i = 0; i < 3; i++) {
400                         if (!min[i] || v->co[i] < min[i]->co[i])
401                                 min[i] = v;
402                         if (!max[i] || v->co[i] > max[i]->co[i])
403                                 max[i] = v;
404                 }
405         }
406 }
407
408 /* Returns true if input is coplanar */
409 static int hull_find_large_tetrahedron(BMesh *bm, BMOperator *op,
410                                        BMVert *tetra[4])
411 {
412         BMVert *min[3], *max[3], *v;
413         BMOIter oiter;
414         float widest_axis_len, largest_dist, plane_normal[3];
415         int i, j, widest_axis;
416         
417         hull_get_min_max(bm, op, min, max);
418
419         /* Check for flat axis */
420         for (i = 0; i < 3; i++) {
421                 if (min[i] == max[i]) {
422                         return TRUE;
423                 }
424         }
425
426         /* Find widest axis */
427         widest_axis_len = 0;
428         for (i = 0; i < 3; i++) {
429                 float len = (max[i]->co[i] - min[i]->co[i]);
430                 if (len >= widest_axis_len) {
431                         widest_axis_len = len;
432                         widest_axis = i;
433                 }
434         }
435
436         /* Use widest axis for first two points */
437         tetra[0] = min[widest_axis];
438         tetra[1] = max[widest_axis];
439         BMO_elem_flag_enable(bm, tetra[0], HULL_FLAG_TETRA_VERT);
440         BMO_elem_flag_enable(bm, tetra[1], HULL_FLAG_TETRA_VERT);
441
442         /* Choose third vertex farthest from existing line segment */
443         largest_dist = 0;
444         for (i = 0; i < 3; i++) {
445                 BMVert *v;
446                 float dist;
447
448                 if (i == widest_axis)
449                         continue;
450
451                 v = min[i];
452                 for (j = 0; j < 2; j++) {
453                         dist = dist_to_line_segment_v3(v->co, tetra[0]->co, tetra[1]->co);
454                         if (dist > largest_dist) {
455                                 largest_dist = dist;
456                                 tetra[2] = v;
457                         }
458
459                         v = max[i];
460                 }
461         }
462
463         BMO_elem_flag_enable(bm, tetra[2], HULL_FLAG_TETRA_VERT);
464         /* Check for colinear vertices */
465         if (largest_dist < 0.0001)
466                 return TRUE;
467
468         /* Choose fourth point farthest from existing plane */
469         largest_dist = 0;
470         normal_tri_v3(plane_normal, tetra[0]->co, tetra[1]->co, tetra[2]->co);
471         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
472                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
473                         float dist = dist_to_plane_v3(v->co, tetra[0]->co, plane_normal);
474                         if (dist > largest_dist) {
475                                 largest_dist = dist;
476                                 tetra[3] = v;
477                         }
478                 }
479         }
480
481         BMO_elem_flag_enable(bm, tetra[3], HULL_FLAG_TETRA_VERT);
482         if (largest_dist < 0.0001)
483                 return TRUE;
484
485         return FALSE;
486 }
487
488
489
490 /**************************** Final Output ****************************/
491
492 static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
493                                     HullFinalEdges *final_edges)
494 {
495         GHashIterator hull_iter;
496
497         GHASH_ITER (hull_iter, hull_triangles) {
498                 HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter);
499                 BMIter bm_iter1, bm_iter2;
500                 BMFace *f;
501                 int f_on_hull;
502
503                 BM_ITER_ELEM (f, &bm_iter1, t->v[0], BM_FACES_OF_VERT) {
504                         BMEdge *e;
505
506                         /* Check that all the face's edges are on the hull,
507                            otherwise can't reuse it */
508                         f_on_hull = TRUE;
509                         BM_ITER_ELEM (e, &bm_iter2, f, BM_EDGES_OF_FACE) {
510                                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2)) {
511                                         f_on_hull = FALSE;
512                                         break;
513                                 }
514                         }
515                         
516                         /* Note: can't change ghash while iterating, so mark
517                            with 'skip' flag rather than deleting triangles */
518                         if (BM_vert_in_face(f, t->v[1]) &&
519                             BM_vert_in_face(f, t->v[2]) && f_on_hull) {
520                                 t->skip = TRUE;
521                                 BMO_elem_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
522                                 BMO_elem_flag_enable(bm, f, HULL_FLAG_HOLE);
523                         }
524                 }
525         }
526 }
527
528 static void hull_mark_interior_elements(BMesh *bm, BMOperator *op,
529                                         GHash *hull_triangles,
530                                         HullFinalEdges *final_edges)
531 {
532         BMVert *v;
533         BMEdge *e;
534         BMFace *f;
535         BMOIter oiter;
536
537         /* Check all input vertices again to see if they are actually part
538            of the hull */
539         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
540                 if (!hull_test_v_outside(hull_triangles, v)) {
541                         /* Mark for 'interior_verts' slot */
542                         BMO_elem_flag_enable(bm, v, HULL_FLAG_INTERIOR_ELE);
543                 }
544         }
545
546         /* Check for interior edges too */
547         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
548                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2))
549                         BMO_elem_flag_enable(bm, e, HULL_FLAG_INTERIOR_ELE);
550         }
551
552         /* Mark all input faces as interior, some may be unmarked in
553            hull_remove_overlapping() */
554         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
555                 BMO_elem_flag_enable(bm, f, HULL_FLAG_INTERIOR_ELE);
556         }
557 }
558
559 static void hull_tag_unused(BMesh *bm, BMOperator *op)
560 {
561         BMIter iter;
562         BMOIter oiter;
563         BMVert *v;
564         BMEdge *e;
565         BMFace *f;
566
567         /* Mark vertices, edges, and faces that are already marked
568            interior (i.e. were already part of the input, but not part of
569            the hull), but that aren't also used by elements outside the
570            input set */
571         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
572                 if (BMO_elem_flag_test(bm, v, HULL_FLAG_INTERIOR_ELE)) {
573                         int del = TRUE;
574                 
575                         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
576                                 if (!BMO_elem_flag_test(bm, e, HULL_FLAG_INPUT)) {
577                                         del = FALSE;
578                                         break;
579                                 }
580                         }
581
582                         BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
583                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
584                                         del = FALSE;
585                                         break;
586                                 }
587                         }
588
589                         if (del)
590                                 BMO_elem_flag_enable(bm, v, HULL_FLAG_DEL);
591                 }
592         }
593
594         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
595                 if (BMO_elem_flag_test(bm, e, HULL_FLAG_INTERIOR_ELE)) {
596                         int del = TRUE;
597
598                         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
599                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
600                                         del = FALSE;
601                                         break;
602                                 }
603                         }
604
605                         if (del)
606                                 BMO_elem_flag_enable(bm, e, HULL_FLAG_DEL);
607                 }
608         }
609
610         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
611                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INTERIOR_ELE))
612                         BMO_elem_flag_enable(bm, f, HULL_FLAG_DEL);
613         }
614 }
615
616 void hull_tag_holes(BMesh *bm, BMOperator *op)
617 {
618         BMIter iter;
619         BMOIter oiter;
620         BMFace *f;
621         BMEdge *e;
622
623         /* Unmark any hole faces if they are isolated or part of a
624          * border */
625         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
626                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
627                         BM_ITER_ELEM (e, &iter, f, BM_EDGES_OF_FACE) {
628                                 if (BM_edge_face_count(e) == 1) {
629                                         BMO_elem_flag_disable(bm, f, HULL_FLAG_HOLE);
630                                         break;
631                                 }
632                         }
633                 }
634         }
635
636         /* Mark edges too if all adjacent faces are holes */
637         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
638                 int hole = TRUE;
639                 
640                 BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
641                         if (!BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
642                                 hole = FALSE;
643                                 break;
644                         }
645                 }
646
647                 if (hole)
648                         BMO_elem_flag_enable(bm, e, HULL_FLAG_HOLE);
649         }
650 }
651
652 void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
653 {
654         HullFinalEdges *final_edges;
655         BLI_mempool *hull_pool, *edge_pool;
656         BMVert *v, *tetra[4];
657         BMElemF *ele;
658         BMOIter oiter;
659         GHash *hull_triangles;
660
661         /* Verify that at least four verts in the input */
662         if (BMO_slot_get(op, "input")->len < 4) {
663                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
664                                 "Requires at least four vertices");
665                 return;
666         }
667
668         /* Initialize the convex hull by building a tetrahedron. A
669          * degenerate tetrahedron can cause problems, so report error and
670          * fail if the result is coplanar */
671         if (hull_find_large_tetrahedron(bm, op, tetra)) {
672                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
673                                 "Input vertices are coplanar");
674                 return;
675         }
676
677         /* Tag input elements */
678         BMO_ITER (ele, &oiter, bm, op, "input", BM_ALL)
679                 BMO_elem_flag_enable(bm, ele, HULL_FLAG_INPUT);
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_new(BLI_ghashutil_ptrhash,
684                                        BLI_ghashutil_ptrcmp,
685                                        "hull_triangles");
686
687         /* Add tetrahedron triangles */
688         hull_add_tetrahedron(hull_triangles, hull_pool, tetra);
689
690         /* Expand hull to cover new vertices outside the existing hull */
691         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
692                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
693                         GHash *outside = hull_triangles_v_outside(hull_triangles, v);
694                         if (BLI_ghash_size(outside)) {
695                                 /* Expand hull and delete interior triangles */
696                                 add_point(hull_triangles, hull_pool, edge_pool, outside, v);
697                         }
698                         BLI_ghash_free(outside, NULL, NULL);
699                 }
700         }
701
702         BLI_mempool_destroy(edge_pool);
703         final_edges = hull_final_edges(hull_triangles);
704         
705         hull_mark_interior_elements(bm, op, hull_triangles, final_edges);
706
707         /* Remove hull triangles covered by an existing face */
708         if (BMO_slot_bool_get(op, "use_existing_faces")) {
709                 hull_remove_overlapping(bm, hull_triangles, final_edges);
710
711                 hull_tag_holes(bm, op);
712         }
713
714         /* Done with edges */
715         hull_final_edges_free(final_edges);
716
717         /* Convert hull triangles to BMesh faces */
718         hull_output_triangles(bm, hull_triangles);
719         BLI_mempool_destroy(hull_pool);
720
721         BLI_ghash_free(hull_triangles, NULL, NULL);
722
723         hull_tag_unused(bm, op);
724
725         /* Output slot of input elements that ended up inside the hull
726          * rather than part of it */
727         BMO_slot_buffer_from_enabled_flag(bm, op, "interior_geom", BM_ALL,
728                                           HULL_FLAG_INTERIOR_ELE);
729
730         /* Output slot of input elements that ended up inside the hull and
731          * are are unused by other geometry. */
732         BMO_slot_buffer_from_enabled_flag(bm, op, "unused_geom", BM_ALL,
733                                           HULL_FLAG_DEL);
734
735         /* Output slot of faces and edges that were in the input and on
736          * the hull (useful for cases like bridging where you want to
737          * delete some input geometry) */
738         BMO_slot_buffer_from_enabled_flag(bm, op, "holes_geom", BM_ALL,
739                                           HULL_FLAG_HOLE);
740
741         /* Output slot of all hull vertices, faces, and edges */
742         BMO_slot_buffer_from_enabled_flag(bm, op, "geomout", BM_ALL,
743                                           HULL_FLAG_OUTPUT_GEOM);
744 }