Fix precision issue for bmo_hull.interior_geom output slot.
[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_new(BLI_ghashutil_ptrhash,
158                                 BLI_ghashutil_ptrcmp,
159                                 "outside");
160
161         GHASH_ITER (iter, hull_triangles) {
162                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
163                 
164                 if (hull_point_tri_side(t, v->co) >= 0)
165                         BLI_ghash_insert(outside, t, NULL);
166         }
167
168         return outside;
169 }
170
171 /* For vertex 'v', find which triangles must be deleted to extend the
172  * hull; find the boundary edges of that hole so that it can be filled
173  * with connections to the new vertex, and update the hull_triangles
174  * to delete the marked triangles */
175 static void add_point(BMesh *bm, GHash *hull_triangles, BLI_mempool *hull_pool,
176                       BLI_mempool *edge_pool, GHash *outside, BMVert *v)
177 {
178         ListBase edges = {NULL, NULL};
179         HullBoundaryEdge *e, *next;
180         GHashIterator iter;
181
182         GHASH_ITER (iter, outside) {
183                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
184                 int i;
185                 
186                 expand_boundary_edges(&edges, edge_pool, t);
187
188                 /* Mark triangle's vertices as interior */
189                 for (i = 0; i < 3; i++)
190                         BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
191                 
192                 /* Delete the triangle */
193                 BLI_ghash_remove(hull_triangles, t, NULL, NULL);
194                 BLI_mempool_free(hull_pool, t);
195         }
196
197         /* Fill hole boundary with triangles to new point */
198         for (e = edges.first; e; e = next) {
199                 next = e->next;
200                 hull_add_triangle(bm, hull_triangles, hull_pool, e->v[0], e->v[1], v);
201                 BLI_mempool_free(edge_pool, e);
202         }
203 }
204
205 static BMFace *hull_find_example_face(BMesh *bm, BMEdge *e)
206 {
207         BMIter iter;
208         BMFace *f;
209
210         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
211                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT) ||
212                     !BMO_elem_flag_test(bm, f, HULL_FLAG_OUTPUT_GEOM))
213                 {
214                         return f;
215                 }
216         }
217
218         return NULL;
219 }
220
221 static void hull_output_triangles(BMesh *bm, GHash *hull_triangles)
222 {
223         GHashIterator iter;
224         
225         GHASH_ITER (iter, hull_triangles) {
226                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
227
228                 if (!t->skip) {
229                         BMEdge *edges[3] = {
230                                 BM_edge_create(bm, t->v[0], t->v[1], NULL, TRUE),
231                                 BM_edge_create(bm, t->v[1], t->v[2], NULL, TRUE),
232                                 BM_edge_create(bm, t->v[2], t->v[0], NULL, TRUE)
233                         };
234                         BMFace *f, *example = NULL;
235                         int i;
236
237                         /* Look for an adjacent face that existed before the hull */
238                         for (i = 0; i < 3; i++) {
239                                 if (!example)
240                                         example = hull_find_example_face(bm, edges[i]);
241                         }
242
243                         f = BM_face_create_quad_tri_v(bm, t->v, 3, example, FALSE);
244                         BM_face_copy_shared(bm, f);
245
246                         /* Mark face/verts/edges for 'geomout' slot and select */
247                         BMO_elem_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
248                         BM_face_select_set(bm, f, TRUE);
249                         for (i = 0; i < 3; i++) {
250                                 BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_OUTPUT_GEOM);
251                                 BMO_elem_flag_enable(bm, edges[i], HULL_FLAG_OUTPUT_GEOM);
252                         }
253                 }
254         }
255 }
256
257
258
259 /***************************** Final Edges ****************************/
260
261 typedef struct {
262         GHash *edges;
263         BLI_mempool *base_pool, *link_pool;
264 } HullFinalEdges;
265
266 static LinkData *final_edges_find_link(ListBase *adj, BMVert *v)
267 {
268         LinkData *link;
269
270         for (link = adj->first; link; link = link->next) {
271                 if (link->data == v)
272                         return link;
273         }
274
275         return NULL;
276 }
277
278 static int hull_final_edges_lookup(HullFinalEdges *final_edges,
279                                    BMVert *v1, BMVert *v2)
280 {
281         ListBase *adj;
282
283         /* Use lower vertex pointer for hash key */
284         if (v1 > v2)
285                 SWAP(BMVert *, v1, v2);
286
287         adj = BLI_ghash_lookup(final_edges->edges, v1);
288         if (!adj)
289                 return FALSE;
290
291         return !!final_edges_find_link(adj, v2);
292 }
293
294 /* Used for checking whether a pre-existing edge lies on the hull */
295 static HullFinalEdges *hull_final_edges(GHash *hull_triangles)
296 {
297         HullFinalEdges *final_edges;
298         GHashIterator iter;
299         
300         final_edges = MEM_callocN(sizeof(HullFinalEdges), "HullFinalEdges");
301         final_edges->edges = BLI_ghash_new(BLI_ghashutil_ptrhash,
302                                            BLI_ghashutil_ptrcmp,
303                                            "final edges ghash");
304         final_edges->base_pool = BLI_mempool_create(sizeof(ListBase), 128, 128, 0);
305         final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 128, 128, 0);
306
307         GHASH_ITER (iter, hull_triangles) {
308                 LinkData *link;
309                 int i;
310                 
311                 for (i = 0; i < 3; i++) {
312                         HullTriangle *t = BLI_ghashIterator_getKey(&iter);
313                         BMVert *v1 = t->v[i];
314                         BMVert *v2 = t->v[(i + 1) % 3];
315                         ListBase *adj;
316
317                         /* Use lower vertex pointer for hash key */
318                         if (v1 > v2)
319                                 SWAP(BMVert *, v1, v2);
320
321                         adj = BLI_ghash_lookup(final_edges->edges, v1);
322                         if (!adj) {
323                                 adj = BLI_mempool_calloc(final_edges->base_pool);
324                                 BLI_ghash_insert(final_edges->edges, v1, adj);
325                         }
326
327                         if (!final_edges_find_link(adj, v2)) {
328                                 link = BLI_mempool_calloc(final_edges->link_pool);
329                                 link->data = v2;
330                                 BLI_addtail(adj, link);
331                         }
332                 }
333         }
334
335         return final_edges;
336 }
337
338 static void hull_final_edges_free(HullFinalEdges *final_edges)
339 {
340         BLI_ghash_free(final_edges->edges, NULL, NULL);
341         BLI_mempool_destroy(final_edges->base_pool);
342         BLI_mempool_destroy(final_edges->link_pool);
343         MEM_freeN(final_edges);
344 }
345
346
347
348 /************************* Initial Tetrahedron ************************/
349
350 static void hull_add_tetrahedron(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
351                                  BMVert *tetra[4])
352 {
353         float center[3];
354         int i, indices[4][3] = {
355                 {0, 1, 2},
356                 {0, 2, 3},
357                 {1, 0, 3},
358                 {2, 1, 3}};
359
360         /* Calculate center */
361         zero_v3(center);
362         for (i = 0; i < 4; i++)
363                 add_v3_v3(center, tetra[i]->co);
364         mul_v3_fl(center, 0.25f);
365
366         for (i = 0; i < 4; i++) {
367                 BMVert *v1 = tetra[indices[i][0]];
368                 BMVert *v2 = tetra[indices[i][1]];
369                 BMVert *v3 = tetra[indices[i][2]];
370                 float no[3], d[3];
371
372                 normal_tri_v3(no, v1->co, v2->co, v3->co);
373                 sub_v3_v3v3(d, center, v1->co);
374                 if (dot_v3v3(no, d) > 0)
375                         SWAP(BMVert *, v1, v3);
376
377                 hull_add_triangle(bm, hull_triangles, pool, v1, v2, v3);
378         }
379 }
380
381 /* For each axis, get the minimum and maximum input vertices */
382 static void hull_get_min_max(BMesh *bm, BMOperator *op,
383                              BMVert *min[3], BMVert *max[3])
384 {
385         BMOIter oiter;
386         BMVert *v;
387
388         min[0] = min[1] = min[2] = NULL;
389         max[0] = max[1] = max[2] = NULL;
390
391         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
392                 int i;
393                 
394                 for (i = 0; i < 3; i++) {
395                         if (!min[i] || v->co[i] < min[i]->co[i])
396                                 min[i] = v;
397                         if (!max[i] || v->co[i] > max[i]->co[i])
398                                 max[i] = v;
399                 }
400         }
401 }
402
403 /* Returns true if input is coplanar */
404 static int hull_find_large_tetrahedron(BMesh *bm, BMOperator *op,
405                                        BMVert *tetra[4])
406 {
407         BMVert *min[3], *max[3], *v;
408         BMOIter oiter;
409         float widest_axis_len, largest_dist, plane_normal[3];
410         int i, j, widest_axis;
411         
412         tetra[0] = tetra[1] = tetra[2] = tetra[3] = NULL;
413         hull_get_min_max(bm, op, min, max);
414
415         /* Check for flat axis */
416         for (i = 0; i < 3; i++) {
417                 if (min[i] == max[i]) {
418                         return TRUE;
419                 }
420         }
421
422         /* Find widest axis */
423         widest_axis_len = 0.0f;
424         widest_axis = 0; /* set here in the unlikey case this isn't set below */
425         for (i = 0; i < 3; i++) {
426                 float len = (max[i]->co[i] - min[i]->co[i]);
427                 if (len >= widest_axis_len) {
428                         widest_axis_len = len;
429                         widest_axis = i;
430                 }
431         }
432
433         /* Use widest axis for first two points */
434         tetra[0] = min[widest_axis];
435         tetra[1] = max[widest_axis];
436         BMO_elem_flag_enable(bm, tetra[0], HULL_FLAG_TETRA_VERT);
437         BMO_elem_flag_enable(bm, tetra[1], HULL_FLAG_TETRA_VERT);
438
439         /* Choose third vertex farthest from existing line segment */
440         largest_dist = 0;
441         for (i = 0; i < 3; i++) {
442                 BMVert *v;
443                 float dist;
444
445                 if (i == widest_axis)
446                         continue;
447
448                 v = min[i];
449                 for (j = 0; j < 2; j++) {
450                         dist = dist_to_line_segment_v3(v->co, tetra[0]->co, tetra[1]->co);
451                         if (dist > largest_dist) {
452                                 largest_dist = dist;
453                                 tetra[2] = v;
454                         }
455
456                         v = max[i];
457                 }
458         }
459
460         if (tetra[2]) {
461                 BMO_elem_flag_enable(bm, tetra[2], HULL_FLAG_TETRA_VERT);
462         }
463         else {
464                 return TRUE;
465         }
466
467         /* Check for colinear vertices */
468         if (largest_dist < 0.0001f)
469                 return TRUE;
470
471         /* Choose fourth point farthest from existing plane */
472         largest_dist = 0;
473         normal_tri_v3(plane_normal, tetra[0]->co, tetra[1]->co, tetra[2]->co);
474         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
475                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
476                         float dist = fabsf(dist_to_plane_v3(v->co, tetra[0]->co, plane_normal));
477                         if (dist > largest_dist) {
478                                 largest_dist = dist;
479                                 tetra[3] = v;
480                         }
481                 }
482         }
483
484         if (tetra[3]) {
485                 BMO_elem_flag_enable(bm, tetra[3], HULL_FLAG_TETRA_VERT);
486         }
487         else {
488                 return TRUE;
489         }
490
491         if (largest_dist < 0.0001f)
492                 return TRUE;
493
494         return FALSE;
495 }
496
497
498
499 /**************************** Final Output ****************************/
500
501 static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
502                                     HullFinalEdges *final_edges)
503 {
504         GHashIterator hull_iter;
505
506         GHASH_ITER (hull_iter, hull_triangles) {
507                 HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter);
508                 BMIter bm_iter1, bm_iter2;
509                 BMFace *f;
510                 int f_on_hull;
511
512                 BM_ITER_ELEM (f, &bm_iter1, t->v[0], BM_FACES_OF_VERT) {
513                         BMEdge *e;
514
515                         /* Check that all the face's edges are on the hull,
516                            otherwise can't reuse it */
517                         f_on_hull = TRUE;
518                         BM_ITER_ELEM (e, &bm_iter2, f, BM_EDGES_OF_FACE) {
519                                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2)) {
520                                         f_on_hull = FALSE;
521                                         break;
522                                 }
523                         }
524                         
525                         /* Note: can't change ghash while iterating, so mark
526                            with 'skip' flag rather than deleting triangles */
527                         if (BM_vert_in_face(f, t->v[1]) &&
528                             BM_vert_in_face(f, t->v[2]) && f_on_hull) {
529                                 t->skip = TRUE;
530                                 BMO_elem_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
531                                 BMO_elem_flag_enable(bm, f, HULL_FLAG_HOLE);
532                         }
533                 }
534         }
535 }
536
537 static void hull_mark_interior_elements(BMesh *bm, BMOperator *op,
538                                         HullFinalEdges *final_edges)
539 {
540         BMEdge *e;
541         BMFace *f;
542         BMOIter oiter;
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                 /* Mark all vertices as interior to begin with */
680                 if (ele->head.htype == BM_VERT)
681                         BMO_elem_flag_enable(bm, ele, HULL_FLAG_INTERIOR_ELE);
682         }
683
684         edge_pool = BLI_mempool_create(sizeof(HullBoundaryEdge), 128, 128, 0);
685         hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0);
686         hull_triangles = BLI_ghash_new(BLI_ghashutil_ptrhash,
687                                        BLI_ghashutil_ptrcmp,
688                                        "hull_triangles");
689
690         /* Add tetrahedron triangles */
691         hull_add_tetrahedron(bm, hull_triangles, hull_pool, tetra);
692
693         /* Expand hull to cover new vertices outside the existing hull */
694         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
695                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
696                         GHash *outside = hull_triangles_v_outside(hull_triangles, v);
697                         if (BLI_ghash_size(outside)) {
698                                 /* Expand hull and delete interior triangles */
699                                 add_point(bm, hull_triangles, hull_pool, edge_pool, outside, v);
700                         }
701                         BLI_ghash_free(outside, NULL, NULL);
702                 }
703         }
704
705         BLI_mempool_destroy(edge_pool);
706         final_edges = hull_final_edges(hull_triangles);
707         
708         hull_mark_interior_elements(bm, op, final_edges);
709
710         /* Remove hull triangles covered by an existing face */
711         if (BMO_slot_bool_get(op, "use_existing_faces")) {
712                 hull_remove_overlapping(bm, hull_triangles, final_edges);
713
714                 hull_tag_holes(bm, op);
715         }
716
717         /* Done with edges */
718         hull_final_edges_free(final_edges);
719
720         /* Convert hull triangles to BMesh faces */
721         hull_output_triangles(bm, hull_triangles);
722         BLI_mempool_destroy(hull_pool);
723
724         BLI_ghash_free(hull_triangles, NULL, NULL);
725
726         hull_tag_unused(bm, op);
727
728         /* Output slot of input elements that ended up inside the hull
729          * rather than part of it */
730         BMO_slot_buffer_from_enabled_flag(bm, op, "interior_geom", BM_ALL,
731                                           HULL_FLAG_INTERIOR_ELE);
732
733         /* Output slot of input elements that ended up inside the hull and
734          * are are unused by other geometry. */
735         BMO_slot_buffer_from_enabled_flag(bm, op, "unused_geom", BM_ALL,
736                                           HULL_FLAG_DEL);
737
738         /* Output slot of faces and edges that were in the input and on
739          * the hull (useful for cases like bridging where you want to
740          * delete some input geometry) */
741         BMO_slot_buffer_from_enabled_flag(bm, op, "holes_geom", BM_ALL,
742                                           HULL_FLAG_HOLE);
743
744         /* Output slot of all hull vertices, faces, and edges */
745         BMO_slot_buffer_from_enabled_flag(bm, op, "geomout", BM_ALL,
746                                           HULL_FLAG_OUTPUT_GEOM);
747 }