BMesh: make toolflags optional
[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  * Create a convex hull using bullet physics library.
27  */
28
29 #ifdef WITH_BULLET
30
31 #include "MEM_guardedalloc.h"
32
33 #include "BLI_array.h"
34 #include "BLI_listbase.h"
35 #include "BLI_math.h"
36
37 #include "Bullet-C-Api.h"
38
39 /* XXX: using 128 for totelem and pchunk of mempool, no idea what good
40  * values would be though */
41
42 #include "bmesh.h"
43
44 #include "intern/bmesh_operators_private.h"  /* own include */
45
46 /* Internal operator flags */
47 typedef enum {
48         HULL_FLAG_INPUT =           (1 << 0),
49         
50         HULL_FLAG_INTERIOR_ELE =    (1 << 1),
51         HULL_FLAG_OUTPUT_GEOM =     (1 << 2),
52         
53         HULL_FLAG_DEL =             (1 << 3),
54         HULL_FLAG_HOLE =            (1 << 4)
55 } HullFlags;
56
57 /* Store hull triangles separate 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
67
68 /*************************** Hull Triangles ***************************/
69
70 static void hull_add_triangle(
71         BMesh *bm, GSet *hull_triangles, BLI_mempool *pool,
72         BMVert *v1, BMVert *v2, BMVert *v3)
73 {
74         HullTriangle *t;
75         int i;
76
77         t = BLI_mempool_calloc(pool);
78         t->v[0] = v1;
79         t->v[1] = v2;
80         t->v[2] = v3;
81
82         /* Mark triangles vertices as not interior */
83         for (i = 0; i < 3; i++)
84                 BMO_vert_flag_disable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
85
86         BLI_gset_insert(hull_triangles, t);
87         normal_tri_v3(t->no, v1->co, v2->co, v3->co);
88 }
89
90 static BMFace *hull_find_example_face(BMesh *bm, BMEdge *e)
91 {
92         BMIter iter;
93         BMFace *f;
94
95         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
96                 if (BMO_face_flag_test(bm, f, HULL_FLAG_INPUT) ||
97                     BMO_face_flag_test(bm, f, HULL_FLAG_OUTPUT_GEOM) == false)
98                 {
99                         return f;
100                 }
101         }
102
103         return NULL;
104 }
105
106 static void hull_output_triangles(BMesh *bm, GSet *hull_triangles)
107 {
108         GSetIterator iter;
109         
110         GSET_ITER (iter, hull_triangles) {
111                 HullTriangle *t = BLI_gsetIterator_getKey(&iter);
112                 int i;
113
114                 if (!t->skip) {
115                         BMEdge *edges[3] = {
116                                 BM_edge_create(bm, t->v[0], t->v[1], NULL, BM_CREATE_NO_DOUBLE),
117                                 BM_edge_create(bm, t->v[1], t->v[2], NULL, BM_CREATE_NO_DOUBLE),
118                                 BM_edge_create(bm, t->v[2], t->v[0], NULL, BM_CREATE_NO_DOUBLE)
119                         };
120                         BMFace *f, *example = NULL;
121
122                         if (BM_face_exists(t->v, 3, &f)) {
123                                 /* If the operator is run with "use_existing_faces"
124                                  * disabled, but an output face in the hull is the
125                                  * same as a face in the existing mesh, it should not
126                                  * be marked as unused or interior. */
127                                 BMO_face_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
128                                 BMO_face_flag_disable(bm, f, HULL_FLAG_HOLE);
129                                 BMO_face_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
130                         }
131                         else {
132                                 /* Look for an adjacent face that existed before the hull */
133                                 for (i = 0; i < 3; i++) {
134                                         if (!example)
135                                                 example = hull_find_example_face(bm, edges[i]);
136                                 }
137
138                                 /* Create new hull face */
139                                 f = BM_face_create_verts(bm, t->v, 3, example, BM_CREATE_NO_DOUBLE, true);
140                                 BM_face_copy_shared(bm, f, NULL, NULL);
141                         }
142                         /* Mark face for 'geom.out' slot and select */
143                         BMO_face_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
144                         BM_face_select_set(bm, f, true);
145
146                         /* Mark edges for 'geom.out' slot */
147                         for (i = 0; i < 3; i++) {
148                                 BMO_edge_flag_enable(bm, edges[i], HULL_FLAG_OUTPUT_GEOM);
149                         }
150                 }
151                 else {
152                         /* Mark input edges for 'geom.out' slot */
153                         for (i = 0; i < 3; i++) {
154                                 const int next = (i == 2 ? 0 : i + 1);
155                                 BMEdge *e = BM_edge_exists(t->v[i], t->v[next]);
156                                 if (e &&
157                                     BMO_edge_flag_test(bm, e, HULL_FLAG_INPUT) &&
158                                     !BMO_edge_flag_test(bm, e, HULL_FLAG_HOLE))
159                                 {
160                                         BMO_edge_flag_enable(bm, e, HULL_FLAG_OUTPUT_GEOM);
161                                 }
162                         }
163                 }
164
165                 /* Mark verts for 'geom.out' slot */
166                 for (i = 0; i < 3; i++) {
167                         BMO_vert_flag_enable(bm, t->v[i], HULL_FLAG_OUTPUT_GEOM);
168                 }
169         }
170 }
171
172
173
174 /***************************** Final Edges ****************************/
175
176 typedef struct {
177         GHash *edges;
178         BLI_mempool *base_pool, *link_pool;
179 } HullFinalEdges;
180
181 static LinkData *final_edges_find_link(ListBase *adj, BMVert *v)
182 {
183         LinkData *link;
184
185         for (link = adj->first; link; link = link->next) {
186                 if (link->data == v)
187                         return link;
188         }
189
190         return NULL;
191 }
192
193 static int hull_final_edges_lookup(
194         HullFinalEdges *final_edges,
195         BMVert *v1, BMVert *v2)
196 {
197         ListBase *adj;
198
199         /* Use lower vertex pointer for hash key */
200         if (v1 > v2)
201                 SWAP(BMVert *, v1, v2);
202
203         adj = BLI_ghash_lookup(final_edges->edges, v1);
204         if (!adj)
205                 return false;
206
207         return !!final_edges_find_link(adj, v2);
208 }
209
210 /* Used for checking whether a pre-existing edge lies on the hull */
211 static HullFinalEdges *hull_final_edges(GSet *hull_triangles)
212 {
213         HullFinalEdges *final_edges;
214         GSetIterator iter;
215         
216         final_edges = MEM_callocN(sizeof(HullFinalEdges), "HullFinalEdges");
217         final_edges->edges = BLI_ghash_ptr_new("final edges ghash");
218         final_edges->base_pool = BLI_mempool_create(sizeof(ListBase), 0, 128, BLI_MEMPOOL_NOP);
219         final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 0, 128, BLI_MEMPOOL_NOP);
220
221         GSET_ITER (iter, hull_triangles) {
222                 HullTriangle *t = BLI_gsetIterator_getKey(&iter);
223                 LinkData *link;
224                 int i;
225
226                 for (i = 0; i < 3; i++) {
227                         BMVert *v1 = t->v[i];
228                         BMVert *v2 = t->v[(i + 1) % 3];
229                         ListBase *adj;
230
231                         /* Use lower vertex pointer for hash key */
232                         if (v1 > v2)
233                                 SWAP(BMVert *, v1, v2);
234
235                         adj = BLI_ghash_lookup(final_edges->edges, v1);
236                         if (!adj) {
237                                 adj = BLI_mempool_calloc(final_edges->base_pool);
238                                 BLI_ghash_insert(final_edges->edges, v1, adj);
239                         }
240
241                         if (!final_edges_find_link(adj, v2)) {
242                                 link = BLI_mempool_calloc(final_edges->link_pool);
243                                 link->data = v2;
244                                 BLI_addtail(adj, link);
245                         }
246                 }
247         }
248
249         return final_edges;
250 }
251
252 static void hull_final_edges_free(HullFinalEdges *final_edges)
253 {
254         BLI_ghash_free(final_edges->edges, NULL, NULL);
255         BLI_mempool_destroy(final_edges->base_pool);
256         BLI_mempool_destroy(final_edges->link_pool);
257         MEM_freeN(final_edges);
258 }
259
260
261
262 /**************************** Final Output ****************************/
263
264 static void hull_remove_overlapping(
265         BMesh *bm, GSet *hull_triangles,
266         HullFinalEdges *final_edges)
267 {
268         GSetIterator hull_iter;
269
270         GSET_ITER (hull_iter, hull_triangles) {
271                 HullTriangle *t = BLI_gsetIterator_getKey(&hull_iter);
272                 BMIter bm_iter1, bm_iter2;
273                 BMFace *f;
274                 bool f_on_hull;
275
276                 BM_ITER_ELEM (f, &bm_iter1, t->v[0], BM_FACES_OF_VERT) {
277                         BMEdge *e;
278
279                         /* Check that all the face's edges are on the hull,
280                          * otherwise can't reuse it */
281                         f_on_hull = true;
282                         BM_ITER_ELEM (e, &bm_iter2, f, BM_EDGES_OF_FACE) {
283                                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2)) {
284                                         f_on_hull = false;
285                                         break;
286                                 }
287                         }
288                         
289                         /* Note: can't change ghash while iterating, so mark
290                          * with 'skip' flag rather than deleting triangles */
291                         if (BM_vert_in_face(t->v[1], f) &&
292                             BM_vert_in_face(t->v[2], f) && f_on_hull)
293                         {
294                                 t->skip = true;
295                                 BMO_face_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
296                                 BMO_face_flag_enable(bm, f, HULL_FLAG_HOLE);
297                         }
298                 }
299         }
300 }
301
302 static void hull_mark_interior_elements(
303         BMesh *bm, BMOperator *op,
304         HullFinalEdges *final_edges)
305 {
306         BMEdge *e;
307         BMFace *f;
308         BMOIter oiter;
309
310         /* Check for interior edges too */
311         BMO_ITER (e, &oiter, op->slots_in, "input", BM_EDGE) {
312                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2))
313                         BMO_edge_flag_enable(bm, e, HULL_FLAG_INTERIOR_ELE);
314         }
315
316         /* Mark all input faces as interior, some may be unmarked in
317          * hull_remove_overlapping() */
318         BMO_ITER (f, &oiter, op->slots_in, "input", BM_FACE) {
319                 BMO_face_flag_enable(bm, f, HULL_FLAG_INTERIOR_ELE);
320         }
321 }
322
323 static void hull_tag_unused(BMesh *bm, BMOperator *op)
324 {
325         BMIter iter;
326         BMOIter oiter;
327         BMVert *v;
328         BMEdge *e;
329         BMFace *f;
330
331         /* Mark vertices, edges, and faces that are already marked
332          * interior (i.e. were already part of the input, but not part of
333          * the hull), but that aren't also used by elements outside the
334          * input set */
335         BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
336                 if (BMO_vert_flag_test(bm, v, HULL_FLAG_INTERIOR_ELE)) {
337                         bool del = true;
338                 
339                         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
340                                 if (!BMO_edge_flag_test(bm, e, HULL_FLAG_INPUT)) {
341                                         del = false;
342                                         break;
343                                 }
344                         }
345
346                         BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
347                                 if (!BMO_face_flag_test(bm, f, HULL_FLAG_INPUT)) {
348                                         del = false;
349                                         break;
350                                 }
351                         }
352
353                         if (del) {
354                                 BMO_vert_flag_enable(bm, v, HULL_FLAG_DEL);
355                         }
356                 }
357         }
358
359         BMO_ITER (e, &oiter, op->slots_in, "input", BM_EDGE) {
360                 if (BMO_edge_flag_test(bm, e, HULL_FLAG_INTERIOR_ELE)) {
361                         bool del = true;
362
363                         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
364                                 if (!BMO_face_flag_test(bm, f, HULL_FLAG_INPUT)) {
365                                         del = false;
366                                         break;
367                                 }
368                         }
369
370                         if (del) {
371                                 BMO_edge_flag_enable(bm, e, HULL_FLAG_DEL);
372                         }
373                 }
374         }
375
376         BMO_ITER (f, &oiter, op->slots_in, "input", BM_FACE) {
377                 if (BMO_face_flag_test(bm, f, HULL_FLAG_INTERIOR_ELE)) {
378                         BMO_face_flag_enable(bm, f, HULL_FLAG_DEL);
379                 }
380         }
381 }
382
383 static void hull_tag_holes(BMesh *bm, BMOperator *op)
384 {
385         BMIter iter;
386         BMOIter oiter;
387         BMFace *f;
388         BMEdge *e;
389
390         /* Unmark any hole faces if they are isolated or part of a
391          * border */
392         BMO_ITER (f, &oiter, op->slots_in, "input", BM_FACE) {
393                 if (BMO_face_flag_test(bm, f, HULL_FLAG_HOLE)) {
394                         BM_ITER_ELEM (e, &iter, f, BM_EDGES_OF_FACE) {
395                                 if (BM_edge_is_boundary(e)) {
396                                         BMO_face_flag_disable(bm, f, HULL_FLAG_HOLE);
397                                         break;
398                                 }
399                         }
400                 }
401         }
402
403         /* Mark edges too if all adjacent faces are holes and the edge is
404          * not already isolated */
405         BMO_ITER (e, &oiter, op->slots_in, "input", BM_EDGE) {
406                 bool hole = true;
407                 bool any_faces = false;
408                 
409                 BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
410                         any_faces = true;
411                         if (!BMO_face_flag_test(bm, f, HULL_FLAG_HOLE)) {
412                                 hole = false;
413                                 break;
414                         }
415                 }
416
417                 if (hole && any_faces)
418                         BMO_edge_flag_enable(bm, e, HULL_FLAG_HOLE);
419         }
420 }
421
422 static int hull_input_vert_count(BMOperator *op)
423 {
424         BMOIter oiter;
425         BMVert *v;
426         int count = 0;
427
428         BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
429                 count++;
430         }
431
432         return count;
433 }
434
435 static BMVert **hull_input_verts_copy(
436         BMOperator *op,
437         const int num_input_verts)
438 {
439         BMOIter oiter;
440         BMVert *v;
441         BMVert **input_verts = MEM_callocN(sizeof(*input_verts) *
442                                            num_input_verts, AT);
443         int i = 0;
444
445         BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
446                 input_verts[i++] = v;
447         }
448
449         return input_verts;
450 }
451
452 static float (*hull_verts_for_bullet(
453         BMVert **input_verts,
454         const int num_input_verts))[3]
455 {
456         float (*coords)[3] = MEM_callocN(sizeof(*coords) * num_input_verts, __func__);
457         int i;
458
459         for (i = 0; i < num_input_verts; i++) {
460                 copy_v3_v3(coords[i], input_verts[i]->co);
461         }
462
463         return coords;
464 }
465
466 static BMVert **hull_verts_from_bullet(
467         plConvexHull hull,
468         BMVert **input_verts,
469         const int num_input_verts)
470 {
471         const int num_verts = plConvexHullNumVertices(hull);
472         BMVert **hull_verts = MEM_mallocN(sizeof(*hull_verts) *
473                                           num_verts, AT);
474         int i;
475
476         for (i = 0; i < num_verts; i++) {
477                 float co[3];
478                 int original_index;
479                 plConvexHullGetVertex(hull, i, co, &original_index);
480
481                 if (original_index >= 0 && original_index < num_input_verts) {
482                         hull_verts[i] = input_verts[original_index];
483                 }
484                 else
485                         BLI_assert(!"Unexpected new vertex in hull output");
486         }
487
488         return hull_verts;
489 }
490
491 static void hull_from_bullet(
492         BMesh *bm, BMOperator *op,
493         GSet *hull_triangles,
494         BLI_mempool *pool)
495 {
496         int *fvi = NULL;
497         BLI_array_declare(fvi);
498
499         BMVert **input_verts;
500         float (*coords)[3];
501         BMVert **hull_verts;
502
503         plConvexHull hull;
504         int i, count = 0;
505
506         const int num_input_verts = hull_input_vert_count(op);
507
508         input_verts = hull_input_verts_copy(op, num_input_verts);
509         coords = hull_verts_for_bullet(input_verts, num_input_verts);
510
511         hull = plConvexHullCompute(coords, num_input_verts);
512         hull_verts = hull_verts_from_bullet(hull, input_verts, num_input_verts);
513         
514         count = plConvexHullNumFaces(hull);
515         for (i = 0; i < count; i++) {
516                 const int len = plConvexHullGetFaceSize(hull, i);
517
518                 if (len > 2) {
519                         BMVert *fv[3];
520                         int j;
521
522                         /* Get face vertex indices */
523                         BLI_array_empty(fvi);
524                         BLI_array_grow_items(fvi, len);
525                         plConvexHullGetFaceVertices(hull, i, fvi);
526
527                         /* Note: here we throw away any NGons from Bullet and turn
528                          * them into triangle fans. Would be nice to use these
529                          * directly, but will have to wait until HullTriangle goes
530                          * away (TODO) */
531                         fv[0] = hull_verts[fvi[0]];
532                         for (j = 2; j < len; j++) {
533                                 fv[1] = hull_verts[fvi[j - 1]];
534                                 fv[2] = hull_verts[fvi[j]];
535
536                                 hull_add_triangle(bm, hull_triangles, pool,
537                                                   fv[0], fv[1], fv[2]);
538                         }
539                 }
540         }
541
542         BLI_array_free(fvi);
543
544         plConvexHullDelete(hull);
545
546         MEM_freeN(hull_verts);
547         MEM_freeN(coords);
548         MEM_freeN(input_verts);
549 }
550
551 /* Check that there are at least three vertices in the input */
552 static bool hull_num_input_verts_is_ok(BMOperator *op)
553 {
554         BMOIter oiter;
555         BMVert *v;
556         int partial_num_verts = 0;
557
558         BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
559                 partial_num_verts++;
560                 if (partial_num_verts >= 3)
561                         break;
562         }
563
564         return (partial_num_verts >= 3);
565 }
566
567 void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
568 {
569         HullFinalEdges *final_edges;
570         BLI_mempool *hull_pool;
571         BMElemF *ele;
572         BMOIter oiter;
573         GSet *hull_triangles;
574
575         /* Verify that at least three verts in the input */
576         if (!hull_num_input_verts_is_ok(op)) {
577                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
578                                 "Requires at least three vertices");
579                 return;
580         }
581
582         /* Tag input elements */
583         BMO_ITER (ele, &oiter, op->slots_in, "input", BM_ALL) {
584
585                 /* Mark all vertices as interior to begin with */
586                 if (ele->head.htype == BM_VERT) {
587                         BMO_vert_flag_enable(bm, (BMVert *)ele, HULL_FLAG_INPUT | HULL_FLAG_INTERIOR_ELE);
588                 }
589                 else if (ele->head.htype == BM_EDGE) {
590                         BMO_edge_flag_enable(bm, (BMEdge *)ele, HULL_FLAG_INPUT);
591                 }
592                 else {
593                         BMO_face_flag_enable(bm, (BMFace *)ele, HULL_FLAG_INPUT);
594                 }
595         }
596
597         hull_pool = BLI_mempool_create(sizeof(HullTriangle), 0, 128, BLI_MEMPOOL_NOP);
598         hull_triangles = BLI_gset_ptr_new("hull_triangles");
599
600         hull_from_bullet(bm, op, hull_triangles, hull_pool);
601
602         final_edges = hull_final_edges(hull_triangles);
603         
604         hull_mark_interior_elements(bm, op, final_edges);
605
606         /* Remove hull triangles covered by an existing face */
607         if (BMO_slot_bool_get(op->slots_in, "use_existing_faces")) {
608                 hull_remove_overlapping(bm, hull_triangles, final_edges);
609
610                 hull_tag_holes(bm, op);
611         }
612
613         /* Done with edges */
614         hull_final_edges_free(final_edges);
615
616         /* Convert hull triangles to BMesh faces */
617         hull_output_triangles(bm, hull_triangles);
618         BLI_mempool_destroy(hull_pool);
619
620         BLI_gset_free(hull_triangles, NULL);
621
622         hull_tag_unused(bm, op);
623
624         /* Output slot of input elements that ended up inside the hull
625          * rather than part of it */
626         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_interior.out",
627                                           BM_ALL_NOLOOP, HULL_FLAG_INTERIOR_ELE);
628
629         /* Output slot of input elements that ended up inside the hull and
630          * are are unused by other geometry. */
631         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_unused.out",
632                                           BM_ALL_NOLOOP, HULL_FLAG_DEL);
633
634         /* Output slot of faces and edges that were in the input and on
635          * the hull (useful for cases like bridging where you want to
636          * delete some input geometry) */
637         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_holes.out",
638                                           BM_ALL_NOLOOP, HULL_FLAG_HOLE);
639
640         /* Output slot of all hull vertices, faces, and edges */
641         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom.out",
642                                           BM_ALL_NOLOOP, HULL_FLAG_OUTPUT_GEOM);
643 }
644
645 #endif  /* WITH_BULLET */