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