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