code cleanup: quiet clang warnings, these would likely never but wont hurt to quiet...
[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.0f;
428         widest_axis = 0; /* set here in the unlikey case this isn't set below */
429         for (i = 0; i < 3; i++) {
430                 float len = (max[i]->co[i] - min[i]->co[i]);
431                 if (len >= widest_axis_len) {
432                         widest_axis_len = len;
433                         widest_axis = i;
434                 }
435         }
436
437         /* Use widest axis for first two points */
438         tetra[0] = min[widest_axis];
439         tetra[1] = max[widest_axis];
440         BMO_elem_flag_enable(bm, tetra[0], HULL_FLAG_TETRA_VERT);
441         BMO_elem_flag_enable(bm, tetra[1], HULL_FLAG_TETRA_VERT);
442
443         /* Choose third vertex farthest from existing line segment */
444         largest_dist = 0;
445         tetra[2] = NULL;
446         for (i = 0; i < 3; i++) {
447                 BMVert *v;
448                 float dist;
449
450                 if (i == widest_axis)
451                         continue;
452
453                 v = min[i];
454                 for (j = 0; j < 2; j++) {
455                         dist = dist_to_line_segment_v3(v->co, tetra[0]->co, tetra[1]->co);
456                         if (dist > largest_dist) {
457                                 largest_dist = dist;
458                                 tetra[2] = v;
459                         }
460
461                         v = max[i];
462                 }
463         }
464
465         if (tetra[2]) {
466                 BMO_elem_flag_enable(bm, tetra[2], HULL_FLAG_TETRA_VERT);
467         }
468         else {
469                 return TRUE;
470         }
471
472         /* Check for colinear vertices */
473         if (largest_dist < 0.0001)
474                 return TRUE;
475
476         /* Choose fourth point farthest from existing plane */
477         largest_dist = 0;
478         normal_tri_v3(plane_normal, tetra[0]->co, tetra[1]->co, tetra[2]->co);
479         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
480                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
481                         float dist = dist_to_plane_v3(v->co, tetra[0]->co, plane_normal);
482                         if (dist > largest_dist) {
483                                 largest_dist = dist;
484                                 tetra[3] = v;
485                         }
486                 }
487         }
488
489         if (tetra[3]) {
490                 BMO_elem_flag_enable(bm, tetra[3], HULL_FLAG_TETRA_VERT);
491         }
492         else {
493                 return TRUE;
494         }
495
496         if (largest_dist < 0.0001)
497                 return TRUE;
498
499         return FALSE;
500 }
501
502
503
504 /**************************** Final Output ****************************/
505
506 static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
507                                     HullFinalEdges *final_edges)
508 {
509         GHashIterator hull_iter;
510
511         GHASH_ITER (hull_iter, hull_triangles) {
512                 HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter);
513                 BMIter bm_iter1, bm_iter2;
514                 BMFace *f;
515                 int f_on_hull;
516
517                 BM_ITER_ELEM (f, &bm_iter1, t->v[0], BM_FACES_OF_VERT) {
518                         BMEdge *e;
519
520                         /* Check that all the face's edges are on the hull,
521                            otherwise can't reuse it */
522                         f_on_hull = TRUE;
523                         BM_ITER_ELEM (e, &bm_iter2, f, BM_EDGES_OF_FACE) {
524                                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2)) {
525                                         f_on_hull = FALSE;
526                                         break;
527                                 }
528                         }
529                         
530                         /* Note: can't change ghash while iterating, so mark
531                            with 'skip' flag rather than deleting triangles */
532                         if (BM_vert_in_face(f, t->v[1]) &&
533                             BM_vert_in_face(f, t->v[2]) && f_on_hull) {
534                                 t->skip = TRUE;
535                                 BMO_elem_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
536                                 BMO_elem_flag_enable(bm, f, HULL_FLAG_HOLE);
537                         }
538                 }
539         }
540 }
541
542 static void hull_mark_interior_elements(BMesh *bm, BMOperator *op,
543                                         GHash *hull_triangles,
544                                         HullFinalEdges *final_edges)
545 {
546         BMVert *v;
547         BMEdge *e;
548         BMFace *f;
549         BMOIter oiter;
550
551         /* Check all input vertices again to see if they are actually part
552            of the hull */
553         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
554                 if (!hull_test_v_outside(hull_triangles, v)) {
555                         /* Mark for 'interior_verts' slot */
556                         BMO_elem_flag_enable(bm, v, HULL_FLAG_INTERIOR_ELE);
557                 }
558         }
559
560         /* Check for interior edges too */
561         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
562                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2))
563                         BMO_elem_flag_enable(bm, e, HULL_FLAG_INTERIOR_ELE);
564         }
565
566         /* Mark all input faces as interior, some may be unmarked in
567            hull_remove_overlapping() */
568         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
569                 BMO_elem_flag_enable(bm, f, HULL_FLAG_INTERIOR_ELE);
570         }
571 }
572
573 static void hull_tag_unused(BMesh *bm, BMOperator *op)
574 {
575         BMIter iter;
576         BMOIter oiter;
577         BMVert *v;
578         BMEdge *e;
579         BMFace *f;
580
581         /* Mark vertices, edges, and faces that are already marked
582            interior (i.e. were already part of the input, but not part of
583            the hull), but that aren't also used by elements outside the
584            input set */
585         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
586                 if (BMO_elem_flag_test(bm, v, HULL_FLAG_INTERIOR_ELE)) {
587                         int del = TRUE;
588                 
589                         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
590                                 if (!BMO_elem_flag_test(bm, e, HULL_FLAG_INPUT)) {
591                                         del = FALSE;
592                                         break;
593                                 }
594                         }
595
596                         BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
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, v, HULL_FLAG_DEL);
605                 }
606         }
607
608         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
609                 if (BMO_elem_flag_test(bm, e, HULL_FLAG_INTERIOR_ELE)) {
610                         int del = TRUE;
611
612                         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
613                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
614                                         del = FALSE;
615                                         break;
616                                 }
617                         }
618
619                         if (del)
620                                 BMO_elem_flag_enable(bm, e, HULL_FLAG_DEL);
621                 }
622         }
623
624         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
625                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INTERIOR_ELE))
626                         BMO_elem_flag_enable(bm, f, HULL_FLAG_DEL);
627         }
628 }
629
630 void hull_tag_holes(BMesh *bm, BMOperator *op)
631 {
632         BMIter iter;
633         BMOIter oiter;
634         BMFace *f;
635         BMEdge *e;
636
637         /* Unmark any hole faces if they are isolated or part of a
638          * border */
639         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
640                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
641                         BM_ITER_ELEM (e, &iter, f, BM_EDGES_OF_FACE) {
642                                 if (BM_edge_face_count(e) == 1) {
643                                         BMO_elem_flag_disable(bm, f, HULL_FLAG_HOLE);
644                                         break;
645                                 }
646                         }
647                 }
648         }
649
650         /* Mark edges too if all adjacent faces are holes */
651         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
652                 int hole = TRUE;
653                 
654                 BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
655                         if (!BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
656                                 hole = FALSE;
657                                 break;
658                         }
659                 }
660
661                 if (hole)
662                         BMO_elem_flag_enable(bm, e, HULL_FLAG_HOLE);
663         }
664 }
665
666 void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
667 {
668         HullFinalEdges *final_edges;
669         BLI_mempool *hull_pool, *edge_pool;
670         BMVert *v, *tetra[4];
671         BMElemF *ele;
672         BMOIter oiter;
673         GHash *hull_triangles;
674
675         /* Verify that at least four verts in the input */
676         if (BMO_slot_get(op, "input")->len < 4) {
677                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
678                                 "Requires at least four vertices");
679                 return;
680         }
681
682         /* Initialize the convex hull by building a tetrahedron. A
683          * degenerate tetrahedron can cause problems, so report error and
684          * fail if the result is coplanar */
685         if (hull_find_large_tetrahedron(bm, op, tetra)) {
686                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
687                                 "Input vertices are coplanar");
688                 return;
689         }
690
691         /* Tag input elements */
692         BMO_ITER (ele, &oiter, bm, op, "input", BM_ALL)
693                 BMO_elem_flag_enable(bm, ele, HULL_FLAG_INPUT);
694
695         edge_pool = BLI_mempool_create(sizeof(HullBoundaryEdge), 128, 128, 0);
696         hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0);
697         hull_triangles = BLI_ghash_new(BLI_ghashutil_ptrhash,
698                                        BLI_ghashutil_ptrcmp,
699                                        "hull_triangles");
700
701         /* Add tetrahedron triangles */
702         hull_add_tetrahedron(hull_triangles, hull_pool, tetra);
703
704         /* Expand hull to cover new vertices outside the existing hull */
705         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
706                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
707                         GHash *outside = hull_triangles_v_outside(hull_triangles, v);
708                         if (BLI_ghash_size(outside)) {
709                                 /* Expand hull and delete interior triangles */
710                                 add_point(hull_triangles, hull_pool, edge_pool, outside, v);
711                         }
712                         BLI_ghash_free(outside, NULL, NULL);
713                 }
714         }
715
716         BLI_mempool_destroy(edge_pool);
717         final_edges = hull_final_edges(hull_triangles);
718         
719         hull_mark_interior_elements(bm, op, hull_triangles, final_edges);
720
721         /* Remove hull triangles covered by an existing face */
722         if (BMO_slot_bool_get(op, "use_existing_faces")) {
723                 hull_remove_overlapping(bm, hull_triangles, final_edges);
724
725                 hull_tag_holes(bm, op);
726         }
727
728         /* Done with edges */
729         hull_final_edges_free(final_edges);
730
731         /* Convert hull triangles to BMesh faces */
732         hull_output_triangles(bm, hull_triangles);
733         BLI_mempool_destroy(hull_pool);
734
735         BLI_ghash_free(hull_triangles, NULL, NULL);
736
737         hull_tag_unused(bm, op);
738
739         /* Output slot of input elements that ended up inside the hull
740          * rather than part of it */
741         BMO_slot_buffer_from_enabled_flag(bm, op, "interior_geom", BM_ALL,
742                                           HULL_FLAG_INTERIOR_ELE);
743
744         /* Output slot of input elements that ended up inside the hull and
745          * are are unused by other geometry. */
746         BMO_slot_buffer_from_enabled_flag(bm, op, "unused_geom", BM_ALL,
747                                           HULL_FLAG_DEL);
748
749         /* Output slot of faces and edges that were in the input and on
750          * the hull (useful for cases like bridging where you want to
751          * delete some input geometry) */
752         BMO_slot_buffer_from_enabled_flag(bm, op, "holes_geom", BM_ALL,
753                                           HULL_FLAG_HOLE);
754
755         /* Output slot of all hull vertices, faces, and edges */
756         BMO_slot_buffer_from_enabled_flag(bm, op, "geomout", BM_ALL,
757                                           HULL_FLAG_OUTPUT_GEOM);
758 }