decrease size for convex hull epsilon when checking which side of a face the vertex...
[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 #define HULL_EPSILON_FLT 0.0001f
41 /* values above 0.0001 cause errors, see below for details, don't increase
42  * without checking against bug [#32027] */
43 #define HULL_EPSILON_DOT_FLT 0.00000001f
44
45 /* Internal operator flags */
46 typedef enum {
47         HULL_FLAG_INPUT =           (1 << 0),
48         HULL_FLAG_TETRA_VERT =      (1 << 1),
49         
50         HULL_FLAG_INTERIOR_ELE =    (1 << 2),
51         HULL_FLAG_OUTPUT_GEOM =     (1 << 3),
52         
53         HULL_FLAG_DEL =             (1 << 4),
54         HULL_FLAG_HOLE =            (1 << 5)
55 } HullFlags;
56
57 /* Store hull triangles seperate from BMesh faces until the end; this
58  * way we don't have to worry about cleaning up extraneous edges or
59  * incorrectly deleting existing geometry. */
60 typedef struct HullTriangle {
61         BMVert *v[3];
62         float no[3];
63         int skip;
64 } HullTriangle;
65
66 /* These edges define the hole created in the hull by deleting faces
67  * that can "see" a new vertex (the boundary edges then form the edge
68  * of a new triangle fan that has the new vertex as its center) */
69 typedef struct HullBoundaryEdge {
70         struct HullBoundaryEdge *next, *prev;
71         BMVert *v[2];
72 } HullBoundaryEdge;
73
74
75
76 /*************************** Boundary Edges ***************************/
77
78 static int edge_match(BMVert *e1_v1, BMVert *e1_v2, BMVert *e2[2])
79 {
80         return (e1_v1 == e2[0] && e1_v2 == e2[1]) ||
81                (e1_v1 == e2[1] && e1_v2 == e2[0]);
82 }
83
84 /* Returns true if the edge (e1, e2) is already in edges; that edge is
85  * deleted here as well. if not found just returns 0 */
86 static int check_for_dup(ListBase *edges, BLI_mempool *pool,
87                          BMVert *v1, BMVert *v2)
88 {
89         HullBoundaryEdge *e, *e_next;
90
91         for (e = edges->first; e; e = e_next) {
92                 e_next = e->next;
93
94                 if (edge_match(v1, v2, e->v)) {
95                         /* remove the interior edge */
96                         BLI_remlink(edges, e);
97                         BLI_mempool_free(pool, e);
98                         return 1;
99                 }
100         }
101
102         return 0;
103 }
104
105 static void expand_boundary_edges(ListBase *edges, BLI_mempool *edge_pool,
106                                   const HullTriangle *t)
107 {
108         HullBoundaryEdge *e_new;
109         int i;
110
111         /* Insert each triangle edge into the boundary list; if any of
112          * its edges are already in there, remove the edge entirely */
113         for (i = 0; i < 3; i++) {
114                 if (!check_for_dup(edges, edge_pool, t->v[i], t->v[(i + 1) % 3])) {
115                         e_new = BLI_mempool_calloc(edge_pool);
116                         e_new->v[0] = t->v[i];
117                         e_new->v[1] = t->v[(i + 1) % 3];
118                         BLI_addtail(edges, e_new);
119                 }
120         }
121 }
122
123
124
125 /*************************** Hull Triangles ***************************/
126
127 static void hull_add_triangle(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
128                               BMVert *v1, BMVert *v2, BMVert *v3)
129 {
130         HullTriangle *t;
131         int i;
132
133         t = BLI_mempool_calloc(pool);
134         t->v[0] = v1;
135         t->v[1] = v2;
136         t->v[2] = v3;
137
138         /* Mark triangles vertices as not interior */
139         for (i = 0; i < 3; i++)
140                 BMO_elem_flag_disable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
141
142         BLI_ghash_insert(hull_triangles, t, NULL);
143         normal_tri_v3(t->no, v1->co, v2->co, v3->co);
144 }
145
146 static int hull_point_tri_side(const HullTriangle *t, const float co[3])
147 {
148         /* Added epsilon to fix bug [#31941], improves output when some
149          * vertices are nearly coplanar. Might need further tweaking for
150          * other cases though.
151          * ...
152          * Update: epsilon of 0.0001 causes [#32027], use HULL_EPSILON_DOT_FLT
153          * and give it a much smaller value
154          * */
155         float p[3], d;
156         sub_v3_v3v3(p, co, t->v[0]->co);
157         d = dot_v3v3(t->no, p);
158         if      (d < -HULL_EPSILON_DOT_FLT) return -1;
159         else if (d >  HULL_EPSILON_DOT_FLT) return  1;
160         else return 0;
161 }
162
163 /* Get all hull triangles that vertex 'v' is outside of */
164 static GHash *hull_triangles_v_outside(GHash *hull_triangles, const BMVert *v)
165 {
166         GHash *outside;
167         GHashIterator iter;
168
169         outside = BLI_ghash_ptr_new("outside");
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                         BLI_ghash_insert(outside, t, NULL);
176         }
177
178         return outside;
179 }
180
181 /* For vertex 'v', find which triangles must be deleted to extend the
182  * hull; find the boundary edges of that hole so that it can be filled
183  * with connections to the new vertex, and update the hull_triangles
184  * to delete the marked triangles */
185 static void add_point(BMesh *bm, GHash *hull_triangles, BLI_mempool *hull_pool,
186                       BLI_mempool *edge_pool, GHash *outside, BMVert *v)
187 {
188         ListBase edges = {NULL, NULL};
189         HullBoundaryEdge *e, *e_next;
190         GHashIterator iter;
191
192         GHASH_ITER (iter, outside) {
193                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
194                 int i;
195                 
196                 expand_boundary_edges(&edges, edge_pool, t);
197
198                 /* Mark triangle's vertices as interior */
199                 for (i = 0; i < 3; i++)
200                         BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
201                 
202                 /* Delete the triangle */
203                 BLI_ghash_remove(hull_triangles, t, NULL, NULL);
204                 BLI_mempool_free(hull_pool, t);
205         }
206
207         /* Fill hole boundary with triangles to new point */
208         for (e = edges.first; e; e = e_next) {
209                 e_next = e->next;
210                 hull_add_triangle(bm, hull_triangles, hull_pool, e->v[0], e->v[1], v);
211                 BLI_mempool_free(edge_pool, e);
212         }
213 }
214
215 static BMFace *hull_find_example_face(BMesh *bm, BMEdge *e)
216 {
217         BMIter iter;
218         BMFace *f;
219
220         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
221                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT) ||
222                     !BMO_elem_flag_test(bm, f, HULL_FLAG_OUTPUT_GEOM))
223                 {
224                         return f;
225                 }
226         }
227
228         return NULL;
229 }
230
231 static void hull_output_triangles(BMesh *bm, GHash *hull_triangles)
232 {
233         GHashIterator iter;
234         
235         GHASH_ITER (iter, hull_triangles) {
236                 HullTriangle *t = BLI_ghashIterator_getKey(&iter);
237
238                 if (!t->skip) {
239                         BMEdge *edges[3] = {
240                                 BM_edge_create(bm, t->v[0], t->v[1], NULL, TRUE),
241                                 BM_edge_create(bm, t->v[1], t->v[2], NULL, TRUE),
242                                 BM_edge_create(bm, t->v[2], t->v[0], NULL, TRUE)
243                         };
244                         BMFace *f, *example = NULL;
245                         int i;
246
247                         /* Look for an adjacent face that existed before the hull */
248                         for (i = 0; i < 3; i++) {
249                                 if (!example)
250                                         example = hull_find_example_face(bm, edges[i]);
251                         }
252
253                         f = BM_face_create_quad_tri_v(bm, t->v, 3, example, FALSE);
254                         BM_face_copy_shared(bm, f);
255
256                         /* Mark face/verts/edges for 'geomout' slot and select */
257                         BMO_elem_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
258                         BM_face_select_set(bm, f, TRUE);
259                         for (i = 0; i < 3; i++) {
260                                 BMO_elem_flag_enable(bm, t->v[i], HULL_FLAG_OUTPUT_GEOM);
261                                 BMO_elem_flag_enable(bm, edges[i], HULL_FLAG_OUTPUT_GEOM);
262                         }
263                 }
264         }
265 }
266
267
268
269 /***************************** Final Edges ****************************/
270
271 typedef struct {
272         GHash *edges;
273         BLI_mempool *base_pool, *link_pool;
274 } HullFinalEdges;
275
276 static LinkData *final_edges_find_link(ListBase *adj, BMVert *v)
277 {
278         LinkData *link;
279
280         for (link = adj->first; link; link = link->next) {
281                 if (link->data == v)
282                         return link;
283         }
284
285         return NULL;
286 }
287
288 static int hull_final_edges_lookup(HullFinalEdges *final_edges,
289                                    BMVert *v1, BMVert *v2)
290 {
291         ListBase *adj;
292
293         /* Use lower vertex pointer for hash key */
294         if (v1 > v2)
295                 SWAP(BMVert *, v1, v2);
296
297         adj = BLI_ghash_lookup(final_edges->edges, v1);
298         if (!adj)
299                 return FALSE;
300
301         return !!final_edges_find_link(adj, v2);
302 }
303
304 /* Used for checking whether a pre-existing edge lies on the hull */
305 static HullFinalEdges *hull_final_edges(GHash *hull_triangles)
306 {
307         HullFinalEdges *final_edges;
308         GHashIterator iter;
309         
310         final_edges = MEM_callocN(sizeof(HullFinalEdges), "HullFinalEdges");
311         final_edges->edges = BLI_ghash_ptr_new("final edges ghash");
312         final_edges->base_pool = BLI_mempool_create(sizeof(ListBase), 128, 128, 0);
313         final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 128, 128, 0);
314
315         GHASH_ITER (iter, hull_triangles) {
316                 LinkData *link;
317                 int i;
318                 
319                 for (i = 0; i < 3; i++) {
320                         HullTriangle *t = BLI_ghashIterator_getKey(&iter);
321                         BMVert *v1 = t->v[i];
322                         BMVert *v2 = t->v[(i + 1) % 3];
323                         ListBase *adj;
324
325                         /* Use lower vertex pointer for hash key */
326                         if (v1 > v2)
327                                 SWAP(BMVert *, v1, v2);
328
329                         adj = BLI_ghash_lookup(final_edges->edges, v1);
330                         if (!adj) {
331                                 adj = BLI_mempool_calloc(final_edges->base_pool);
332                                 BLI_ghash_insert(final_edges->edges, v1, adj);
333                         }
334
335                         if (!final_edges_find_link(adj, v2)) {
336                                 link = BLI_mempool_calloc(final_edges->link_pool);
337                                 link->data = v2;
338                                 BLI_addtail(adj, link);
339                         }
340                 }
341         }
342
343         return final_edges;
344 }
345
346 static void hull_final_edges_free(HullFinalEdges *final_edges)
347 {
348         BLI_ghash_free(final_edges->edges, NULL, NULL);
349         BLI_mempool_destroy(final_edges->base_pool);
350         BLI_mempool_destroy(final_edges->link_pool);
351         MEM_freeN(final_edges);
352 }
353
354
355
356 /************************* Initial Tetrahedron ************************/
357
358 static void hull_add_tetrahedron(BMesh *bm, GHash *hull_triangles, BLI_mempool *pool,
359                                  BMVert *tetra[4])
360 {
361         float center[3];
362         int i, indices[4][3] = {
363                 {0, 1, 2},
364                 {0, 2, 3},
365                 {1, 0, 3},
366                 {2, 1, 3}
367         };
368
369         /* Calculate center */
370         zero_v3(center);
371         for (i = 0; i < 4; i++)
372                 add_v3_v3(center, tetra[i]->co);
373         mul_v3_fl(center, 0.25f);
374
375         for (i = 0; i < 4; i++) {
376                 BMVert *v1 = tetra[indices[i][0]];
377                 BMVert *v2 = tetra[indices[i][1]];
378                 BMVert *v3 = tetra[indices[i][2]];
379                 float no[3], d[3];
380
381                 normal_tri_v3(no, v1->co, v2->co, v3->co);
382                 sub_v3_v3v3(d, center, v1->co);
383                 if (dot_v3v3(no, d) > 0)
384                         SWAP(BMVert *, v1, v3);
385
386                 hull_add_triangle(bm, hull_triangles, pool, v1, v2, v3);
387         }
388 }
389
390 /* For each axis, get the minimum and maximum input vertices */
391 static void hull_get_min_max(BMesh *bm, BMOperator *op,
392                              BMVert *min[3], BMVert *max[3])
393 {
394         BMOIter oiter;
395         BMVert *v;
396
397         min[0] = min[1] = min[2] = NULL;
398         max[0] = max[1] = max[2] = NULL;
399
400         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
401                 int i;
402                 
403                 for (i = 0; i < 3; i++) {
404                         if (!min[i] || v->co[i] < min[i]->co[i])
405                                 min[i] = v;
406                         if (!max[i] || v->co[i] > max[i]->co[i])
407                                 max[i] = v;
408                 }
409         }
410 }
411
412 /* Returns true if input is coplanar */
413 static int hull_find_large_tetrahedron(BMesh *bm, BMOperator *op,
414                                        BMVert *tetra[4])
415 {
416         BMVert *min[3], *max[3], *v;
417         BMOIter oiter;
418         float widest_axis_len, largest_dist, plane_normal[3];
419         int i, j, widest_axis;
420         
421         tetra[0] = tetra[1] = tetra[2] = tetra[3] = NULL;
422         hull_get_min_max(bm, op, min, max);
423
424         /* Check for flat axis */
425         for (i = 0; i < 3; i++) {
426                 if (min[i] == max[i]) {
427                         return TRUE;
428                 }
429         }
430
431         /* Find widest axis */
432         widest_axis_len = 0.0f;
433         widest_axis = 0; /* set here in the unlikey case this isn't set below */
434         for (i = 0; i < 3; i++) {
435                 float len = (max[i]->co[i] - min[i]->co[i]);
436                 if (len >= widest_axis_len) {
437                         widest_axis_len = len;
438                         widest_axis = i;
439                 }
440         }
441
442         /* Use widest axis for first two points */
443         tetra[0] = min[widest_axis];
444         tetra[1] = max[widest_axis];
445         BMO_elem_flag_enable(bm, tetra[0], HULL_FLAG_TETRA_VERT);
446         BMO_elem_flag_enable(bm, tetra[1], HULL_FLAG_TETRA_VERT);
447
448         /* Choose third vertex farthest from existing line segment */
449         largest_dist = 0;
450         for (i = 0; i < 3; i++) {
451                 BMVert *v;
452                 float dist;
453
454                 if (i == widest_axis)
455                         continue;
456
457                 v = min[i];
458                 for (j = 0; j < 2; j++) {
459                         dist = dist_to_line_segment_v3(v->co, tetra[0]->co, tetra[1]->co);
460                         if (dist > largest_dist) {
461                                 largest_dist = dist;
462                                 tetra[2] = v;
463                         }
464
465                         v = max[i];
466                 }
467         }
468
469         if (tetra[2]) {
470                 BMO_elem_flag_enable(bm, tetra[2], HULL_FLAG_TETRA_VERT);
471         }
472         else {
473                 return TRUE;
474         }
475
476         /* Check for colinear vertices */
477         if (largest_dist < HULL_EPSILON_FLT)
478                 return TRUE;
479
480         /* Choose fourth point farthest from existing plane */
481         largest_dist = 0;
482         normal_tri_v3(plane_normal, tetra[0]->co, tetra[1]->co, tetra[2]->co);
483         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
484                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
485                         float dist = fabsf(dist_to_plane_v3(v->co, tetra[0]->co, plane_normal));
486                         if (dist > largest_dist) {
487                                 largest_dist = dist;
488                                 tetra[3] = v;
489                         }
490                 }
491         }
492
493         if (tetra[3]) {
494                 BMO_elem_flag_enable(bm, tetra[3], HULL_FLAG_TETRA_VERT);
495         }
496         else {
497                 return TRUE;
498         }
499
500         if (largest_dist < HULL_EPSILON_FLT)
501                 return TRUE;
502
503         return FALSE;
504 }
505
506
507
508 /**************************** Final Output ****************************/
509
510 static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
511                                     HullFinalEdges *final_edges)
512 {
513         GHashIterator hull_iter;
514
515         GHASH_ITER (hull_iter, hull_triangles) {
516                 HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter);
517                 BMIter bm_iter1, bm_iter2;
518                 BMFace *f;
519                 int f_on_hull;
520
521                 BM_ITER_ELEM (f, &bm_iter1, t->v[0], BM_FACES_OF_VERT) {
522                         BMEdge *e;
523
524                         /* Check that all the face's edges are on the hull,
525                          * otherwise can't reuse it */
526                         f_on_hull = TRUE;
527                         BM_ITER_ELEM (e, &bm_iter2, f, BM_EDGES_OF_FACE) {
528                                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2)) {
529                                         f_on_hull = FALSE;
530                                         break;
531                                 }
532                         }
533                         
534                         /* Note: can't change ghash while iterating, so mark
535                          * with 'skip' flag rather than deleting triangles */
536                         if (BM_vert_in_face(f, t->v[1]) &&
537                             BM_vert_in_face(f, t->v[2]) && f_on_hull)
538                         {
539                                 t->skip = TRUE;
540                                 BMO_elem_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
541                                 BMO_elem_flag_enable(bm, f, HULL_FLAG_HOLE);
542                         }
543                 }
544         }
545 }
546
547 static void hull_mark_interior_elements(BMesh *bm, BMOperator *op,
548                                         HullFinalEdges *final_edges)
549 {
550         BMEdge *e;
551         BMFace *f;
552         BMOIter oiter;
553
554         /* Check for interior edges too */
555         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
556                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2))
557                         BMO_elem_flag_enable(bm, e, HULL_FLAG_INTERIOR_ELE);
558         }
559
560         /* Mark all input faces as interior, some may be unmarked in
561          * hull_remove_overlapping() */
562         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
563                 BMO_elem_flag_enable(bm, f, HULL_FLAG_INTERIOR_ELE);
564         }
565 }
566
567 static void hull_tag_unused(BMesh *bm, BMOperator *op)
568 {
569         BMIter iter;
570         BMOIter oiter;
571         BMVert *v;
572         BMEdge *e;
573         BMFace *f;
574
575         /* Mark vertices, edges, and faces that are already marked
576          * interior (i.e. were already part of the input, but not part of
577          * the hull), but that aren't also used by elements outside the
578          * input set */
579         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
580                 if (BMO_elem_flag_test(bm, v, HULL_FLAG_INTERIOR_ELE)) {
581                         int del = TRUE;
582                 
583                         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
584                                 if (!BMO_elem_flag_test(bm, e, HULL_FLAG_INPUT)) {
585                                         del = FALSE;
586                                         break;
587                                 }
588                         }
589
590                         BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
591                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
592                                         del = FALSE;
593                                         break;
594                                 }
595                         }
596
597                         if (del)
598                                 BMO_elem_flag_enable(bm, v, HULL_FLAG_DEL);
599                 }
600         }
601
602         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
603                 if (BMO_elem_flag_test(bm, e, HULL_FLAG_INTERIOR_ELE)) {
604                         int del = TRUE;
605
606                         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
607                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
608                                         del = FALSE;
609                                         break;
610                                 }
611                         }
612
613                         if (del)
614                                 BMO_elem_flag_enable(bm, e, HULL_FLAG_DEL);
615                 }
616         }
617
618         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
619                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INTERIOR_ELE))
620                         BMO_elem_flag_enable(bm, f, HULL_FLAG_DEL);
621         }
622 }
623
624 void hull_tag_holes(BMesh *bm, BMOperator *op)
625 {
626         BMIter iter;
627         BMOIter oiter;
628         BMFace *f;
629         BMEdge *e;
630
631         /* Unmark any hole faces if they are isolated or part of a
632          * border */
633         BMO_ITER (f, &oiter, bm, op, "input", BM_FACE) {
634                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
635                         BM_ITER_ELEM (e, &iter, f, BM_EDGES_OF_FACE) {
636                                 if (BM_edge_face_count(e) == 1) {
637                                         BMO_elem_flag_disable(bm, f, HULL_FLAG_HOLE);
638                                         break;
639                                 }
640                         }
641                 }
642         }
643
644         /* Mark edges too if all adjacent faces are holes */
645         BMO_ITER (e, &oiter, bm, op, "input", BM_EDGE) {
646                 int hole = TRUE;
647                 
648                 BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
649                         if (!BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
650                                 hole = FALSE;
651                                 break;
652                         }
653                 }
654
655                 if (hole)
656                         BMO_elem_flag_enable(bm, e, HULL_FLAG_HOLE);
657         }
658 }
659
660 void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
661 {
662         HullFinalEdges *final_edges;
663         BLI_mempool *hull_pool, *edge_pool;
664         BMVert *v, *tetra[4];
665         BMElemF *ele;
666         BMOIter oiter;
667         GHash *hull_triangles;
668
669         /* Verify that at least four verts in the input */
670         if (BMO_slot_get(op, "input")->len < 4) {
671                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
672                                 "Requires at least four vertices");
673                 return;
674         }
675
676         /* Initialize the convex hull by building a tetrahedron. A
677          * degenerate tetrahedron can cause problems, so report error and
678          * fail if the result is coplanar */
679         if (hull_find_large_tetrahedron(bm, op, tetra)) {
680                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
681                                 "Input vertices are coplanar");
682                 return;
683         }
684
685         /* Tag input elements */
686         BMO_ITER (ele, &oiter, bm, op, "input", BM_ALL) {
687                 BMO_elem_flag_enable(bm, ele, HULL_FLAG_INPUT);
688                 
689                 /* Mark all vertices as interior to begin with */
690                 if (ele->head.htype == BM_VERT)
691                         BMO_elem_flag_enable(bm, ele, HULL_FLAG_INTERIOR_ELE);
692         }
693
694         edge_pool = BLI_mempool_create(sizeof(HullBoundaryEdge), 128, 128, 0);
695         hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0);
696         hull_triangles = BLI_ghash_ptr_new("hull_triangles");
697
698         /* Add tetrahedron triangles */
699         hull_add_tetrahedron(bm, hull_triangles, hull_pool, tetra);
700
701         /* Expand hull to cover new vertices outside the existing hull */
702         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
703                 if (!BMO_elem_flag_test(bm, v, HULL_FLAG_TETRA_VERT)) {
704                         GHash *outside = hull_triangles_v_outside(hull_triangles, v);
705                         if (BLI_ghash_size(outside)) {
706                                 /* Expand hull and delete interior triangles */
707                                 add_point(bm, hull_triangles, hull_pool, edge_pool, outside, v);
708                         }
709                         BLI_ghash_free(outside, NULL, NULL);
710                 }
711         }
712
713         BLI_mempool_destroy(edge_pool);
714         final_edges = hull_final_edges(hull_triangles);
715         
716         hull_mark_interior_elements(bm, op, final_edges);
717
718         /* Remove hull triangles covered by an existing face */
719         if (BMO_slot_bool_get(op, "use_existing_faces")) {
720                 hull_remove_overlapping(bm, hull_triangles, final_edges);
721
722                 hull_tag_holes(bm, op);
723         }
724
725         /* Done with edges */
726         hull_final_edges_free(final_edges);
727
728         /* Convert hull triangles to BMesh faces */
729         hull_output_triangles(bm, hull_triangles);
730         BLI_mempool_destroy(hull_pool);
731
732         BLI_ghash_free(hull_triangles, NULL, NULL);
733
734         hull_tag_unused(bm, op);
735
736         /* Output slot of input elements that ended up inside the hull
737          * rather than part of it */
738         BMO_slot_buffer_from_enabled_flag(bm, op, "interior_geom", BM_ALL,
739                                           HULL_FLAG_INTERIOR_ELE);
740
741         /* Output slot of input elements that ended up inside the hull and
742          * are are unused by other geometry. */
743         BMO_slot_buffer_from_enabled_flag(bm, op, "unused_geom", BM_ALL,
744                                           HULL_FLAG_DEL);
745
746         /* Output slot of faces and edges that were in the input and on
747          * the hull (useful for cases like bridging where you want to
748          * delete some input geometry) */
749         BMO_slot_buffer_from_enabled_flag(bm, op, "holes_geom", BM_ALL,
750                                           HULL_FLAG_HOLE);
751
752         /* Output slot of all hull vertices, faces, and edges */
753         BMO_slot_buffer_from_enabled_flag(bm, op, "geomout", BM_ALL,
754                                           HULL_FLAG_OUTPUT_GEOM);
755 }