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