5e2404c99193e3ff7e06246340d93147a72c9d0b
[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 #ifdef WITH_BULLET
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_array.h"
32 #include "BLI_ghash.h"
33 #include "BLI_listbase.h"
34 #include "BLI_math.h"
35 #include "BLI_utildefines.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 #include "BLI_mempool.h"
42
43 #include "bmesh.h"
44
45 #include "intern/bmesh_operators_private.h"  /* own include */
46
47 /* Internal operator flags */
48 typedef enum {
49         HULL_FLAG_INPUT =           (1 << 0),
50         
51         HULL_FLAG_INTERIOR_ELE =    (1 << 1),
52         HULL_FLAG_OUTPUT_GEOM =     (1 << 2),
53         
54         HULL_FLAG_DEL =             (1 << 3),
55         HULL_FLAG_HOLE =            (1 << 4)
56 } HullFlags;
57
58 /* Store hull triangles separate from BMesh faces until the end; this
59  * way we don't have to worry about cleaning up extraneous edges or
60  * incorrectly deleting existing geometry. */
61 typedef struct HullTriangle {
62         BMVert *v[3];
63         float no[3];
64         int skip;
65 } HullTriangle;
66
67
68
69 /*************************** Hull Triangles ***************************/
70
71 static void hull_add_triangle(BMesh *bm, GHash *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_elem_flag_disable(bm, t->v[i], HULL_FLAG_INTERIOR_ELE);
85
86         BLI_ghash_insert(hull_triangles, t, NULL);
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_elem_flag_test(bm, f, HULL_FLAG_INPUT) ||
97                     !BMO_elem_flag_test(bm, f, HULL_FLAG_OUTPUT_GEOM))
98                 {
99                         return f;
100                 }
101         }
102
103         return NULL;
104 }
105
106 static void hull_output_triangles(BMesh *bm, GHash *hull_triangles)
107 {
108         GHashIterator iter;
109         
110         GHASH_ITER (iter, hull_triangles) {
111                 HullTriangle *t = BLI_ghashIterator_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_elem_flag_enable(bm, f, HULL_FLAG_OUTPUT_GEOM);
128                                 BMO_elem_flag_disable(bm, f, HULL_FLAG_HOLE);
129                                 BMO_elem_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_quad_tri_v(bm, t->v, 3, example, true);
140                                 BM_face_copy_shared(bm, f);
141                         }
142                         /* Mark face for 'geom.out' slot and select */
143                         BMO_elem_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_elem_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_elem_flag_test(bm, e, HULL_FLAG_INPUT) &&
158                                     !BMO_elem_flag_test(bm, e, HULL_FLAG_HOLE))
159                                 {
160                                         BMO_elem_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_elem_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(HullFinalEdges *final_edges,
194                                    BMVert *v1, BMVert *v2)
195 {
196         ListBase *adj;
197
198         /* Use lower vertex pointer for hash key */
199         if (v1 > v2)
200                 SWAP(BMVert *, v1, v2);
201
202         adj = BLI_ghash_lookup(final_edges->edges, v1);
203         if (!adj)
204                 return false;
205
206         return !!final_edges_find_link(adj, v2);
207 }
208
209 /* Used for checking whether a pre-existing edge lies on the hull */
210 static HullFinalEdges *hull_final_edges(GHash *hull_triangles)
211 {
212         HullFinalEdges *final_edges;
213         GHashIterator iter;
214         
215         final_edges = MEM_callocN(sizeof(HullFinalEdges), "HullFinalEdges");
216         final_edges->edges = BLI_ghash_ptr_new("final edges ghash");
217         final_edges->base_pool = BLI_mempool_create(sizeof(ListBase), 128, 128, 0);
218         final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 128, 128, 0);
219
220         GHASH_ITER (iter, hull_triangles) {
221                 LinkData *link;
222                 int i;
223                 
224                 for (i = 0; i < 3; i++) {
225                         HullTriangle *t = BLI_ghashIterator_getKey(&iter);
226                         BMVert *v1 = t->v[i];
227                         BMVert *v2 = t->v[(i + 1) % 3];
228                         ListBase *adj;
229
230                         /* Use lower vertex pointer for hash key */
231                         if (v1 > v2)
232                                 SWAP(BMVert *, v1, v2);
233
234                         adj = BLI_ghash_lookup(final_edges->edges, v1);
235                         if (!adj) {
236                                 adj = BLI_mempool_calloc(final_edges->base_pool);
237                                 BLI_ghash_insert(final_edges->edges, v1, adj);
238                         }
239
240                         if (!final_edges_find_link(adj, v2)) {
241                                 link = BLI_mempool_calloc(final_edges->link_pool);
242                                 link->data = v2;
243                                 BLI_addtail(adj, link);
244                         }
245                 }
246         }
247
248         return final_edges;
249 }
250
251 static void hull_final_edges_free(HullFinalEdges *final_edges)
252 {
253         BLI_ghash_free(final_edges->edges, NULL, NULL);
254         BLI_mempool_destroy(final_edges->base_pool);
255         BLI_mempool_destroy(final_edges->link_pool);
256         MEM_freeN(final_edges);
257 }
258
259
260
261 /**************************** Final Output ****************************/
262
263 static void hull_remove_overlapping(BMesh *bm, GHash *hull_triangles,
264                                     HullFinalEdges *final_edges)
265 {
266         GHashIterator hull_iter;
267
268         GHASH_ITER (hull_iter, hull_triangles) {
269                 HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter);
270                 BMIter bm_iter1, bm_iter2;
271                 BMFace *f;
272                 bool f_on_hull;
273
274                 BM_ITER_ELEM (f, &bm_iter1, t->v[0], BM_FACES_OF_VERT) {
275                         BMEdge *e;
276
277                         /* Check that all the face's edges are on the hull,
278                          * otherwise can't reuse it */
279                         f_on_hull = true;
280                         BM_ITER_ELEM (e, &bm_iter2, f, BM_EDGES_OF_FACE) {
281                                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2)) {
282                                         f_on_hull = false;
283                                         break;
284                                 }
285                         }
286                         
287                         /* Note: can't change ghash while iterating, so mark
288                          * with 'skip' flag rather than deleting triangles */
289                         if (BM_vert_in_face(f, t->v[1]) &&
290                             BM_vert_in_face(f, t->v[2]) && f_on_hull)
291                         {
292                                 t->skip = true;
293                                 BMO_elem_flag_disable(bm, f, HULL_FLAG_INTERIOR_ELE);
294                                 BMO_elem_flag_enable(bm, f, HULL_FLAG_HOLE);
295                         }
296                 }
297         }
298 }
299
300 static void hull_mark_interior_elements(BMesh *bm, BMOperator *op,
301                                         HullFinalEdges *final_edges)
302 {
303         BMEdge *e;
304         BMFace *f;
305         BMOIter oiter;
306
307         /* Check for interior edges too */
308         BMO_ITER (e, &oiter, op->slots_in, "input", BM_EDGE) {
309                 if (!hull_final_edges_lookup(final_edges, e->v1, e->v2))
310                         BMO_elem_flag_enable(bm, e, HULL_FLAG_INTERIOR_ELE);
311         }
312
313         /* Mark all input faces as interior, some may be unmarked in
314          * hull_remove_overlapping() */
315         BMO_ITER (f, &oiter, op->slots_in, "input", BM_FACE) {
316                 BMO_elem_flag_enable(bm, f, HULL_FLAG_INTERIOR_ELE);
317         }
318 }
319
320 static void hull_tag_unused(BMesh *bm, BMOperator *op)
321 {
322         BMIter iter;
323         BMOIter oiter;
324         BMVert *v;
325         BMEdge *e;
326         BMFace *f;
327
328         /* Mark vertices, edges, and faces that are already marked
329          * interior (i.e. were already part of the input, but not part of
330          * the hull), but that aren't also used by elements outside the
331          * input set */
332         BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
333                 if (BMO_elem_flag_test(bm, v, HULL_FLAG_INTERIOR_ELE)) {
334                         bool del = true;
335                 
336                         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
337                                 if (!BMO_elem_flag_test(bm, e, HULL_FLAG_INPUT)) {
338                                         del = false;
339                                         break;
340                                 }
341                         }
342
343                         BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) {
344                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
345                                         del = false;
346                                         break;
347                                 }
348                         }
349
350                         if (del)
351                                 BMO_elem_flag_enable(bm, v, HULL_FLAG_DEL);
352                 }
353         }
354
355         BMO_ITER (e, &oiter, op->slots_in, "input", BM_EDGE) {
356                 if (BMO_elem_flag_test(bm, e, HULL_FLAG_INTERIOR_ELE)) {
357                         bool del = true;
358
359                         BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
360                                 if (!BMO_elem_flag_test(bm, f, HULL_FLAG_INPUT)) {
361                                         del = false;
362                                         break;
363                                 }
364                         }
365
366                         if (del)
367                                 BMO_elem_flag_enable(bm, e, HULL_FLAG_DEL);
368                 }
369         }
370
371         BMO_ITER (f, &oiter, op->slots_in, "input", BM_FACE) {
372                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_INTERIOR_ELE))
373                         BMO_elem_flag_enable(bm, f, HULL_FLAG_DEL);
374         }
375 }
376
377 static void hull_tag_holes(BMesh *bm, BMOperator *op)
378 {
379         BMIter iter;
380         BMOIter oiter;
381         BMFace *f;
382         BMEdge *e;
383
384         /* Unmark any hole faces if they are isolated or part of a
385          * border */
386         BMO_ITER (f, &oiter, op->slots_in, "input", BM_FACE) {
387                 if (BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
388                         BM_ITER_ELEM (e, &iter, f, BM_EDGES_OF_FACE) {
389                                 if (BM_edge_is_boundary(e)) {
390                                         BMO_elem_flag_disable(bm, f, HULL_FLAG_HOLE);
391                                         break;
392                                 }
393                         }
394                 }
395         }
396
397         /* Mark edges too if all adjacent faces are holes and the edge is
398          * not already isolated */
399         BMO_ITER (e, &oiter, op->slots_in, "input", BM_EDGE) {
400                 bool hole = true;
401                 bool any_faces = false;
402                 
403                 BM_ITER_ELEM (f, &iter, e, BM_FACES_OF_EDGE) {
404                         any_faces = true;
405                         if (!BMO_elem_flag_test(bm, f, HULL_FLAG_HOLE)) {
406                                 hole = false;
407                                 break;
408                         }
409                 }
410
411                 if (hole && any_faces)
412                         BMO_elem_flag_enable(bm, e, HULL_FLAG_HOLE);
413         }
414 }
415
416 static int hull_input_vert_count(BMOperator *op)
417 {
418         BMOIter oiter;
419         BMVert *v;
420         int count = 0;
421
422         BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
423                 count++;
424         }
425
426         return count;
427 }
428
429 static BMVert **hull_input_verts_copy(BMOperator *op,
430                                       const int num_input_verts)
431 {
432         BMOIter oiter;
433         BMVert *v;
434         BMVert **input_verts = MEM_callocN(sizeof(*input_verts) *
435                                            num_input_verts, AT);
436         int i = 0;
437
438         BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
439                 input_verts[i++] = v;
440         }
441
442         return input_verts;
443 }
444
445 static float (*hull_verts_for_bullet(BMVert **input_verts,
446                                      const int num_input_verts))[3]
447 {
448         float (*coords)[3] = MEM_callocN(sizeof(*coords) * num_input_verts, AT);
449         int i;
450
451         for (i = 0; i < num_input_verts; i++) {
452                 copy_v3_v3(coords[i], input_verts[i]->co);
453         }
454
455         return coords;
456 }
457
458 static BMVert **hull_verts_from_bullet(plConvexHull hull,
459                                        BMVert **input_verts,
460                                        const int num_input_verts)
461 {
462         const int num_verts = plConvexHullNumVertices(hull);
463         BMVert **hull_verts = MEM_mallocN(sizeof(*hull_verts) *
464                                           num_verts, AT);
465         int i;
466
467         for (i = 0; i < num_verts; i++) {
468                 float co[3];
469                 int original_index;
470                 plConvexHullGetVertex(hull, i, co, &original_index);
471
472                 if (original_index >= 0 && original_index < num_input_verts) {
473                         hull_verts[i] = input_verts[original_index];
474                 }
475                 else
476                         BLI_assert(!"Unexpected new vertex in hull output");
477         }
478
479         return hull_verts;
480 }
481
482 static void hull_from_bullet(BMesh *bm, BMOperator *op,
483                              GHash *hull_triangles,
484                              BLI_mempool *pool)
485 {
486         int *fvi = NULL;
487         BLI_array_declare(fvi);
488
489         BMVert **input_verts;
490         float (*coords)[3];
491         BMVert **hull_verts;
492
493         plConvexHull hull;
494         int i, count = 0;
495
496         const int num_input_verts = hull_input_vert_count(op);
497
498         input_verts = hull_input_verts_copy(op, num_input_verts);
499         coords = hull_verts_for_bullet(input_verts, num_input_verts);
500
501         hull = plConvexHullCompute(coords, num_input_verts);
502         hull_verts = hull_verts_from_bullet(hull, input_verts, num_input_verts);
503         
504         count = plConvexHullNumFaces(hull);
505         for (i = 0; i < count; i++) {
506                 const int len = plConvexHullGetFaceSize(hull, i);
507
508                 if (len > 2) {
509                         BMVert *fv[3];
510                         int j;
511
512                         /* Get face vertex indices */
513                         BLI_array_empty(fvi);
514                         BLI_array_grow_items(fvi, len);
515                         plConvexHullGetFaceVertices(hull, i, fvi);
516
517                         /* Note: here we throw away any NGons from Bullet and turn
518                          * them into triangle fans. Would be nice to use these
519                          * directly, but will have to wait until HullTriangle goes
520                          * away (TODO) */
521                         fv[0] = hull_verts[fvi[0]];
522                         for (j = 2; j < len; j++) {
523                                 fv[1] = hull_verts[fvi[j - 1]];
524                                 fv[2] = hull_verts[fvi[j]];
525
526                                 hull_add_triangle(bm, hull_triangles, pool,
527                                                   fv[0], fv[1], fv[2]);
528                         }
529                 }
530         }
531
532         BLI_array_free(fvi);
533         MEM_freeN(hull_verts);
534         MEM_freeN(coords);
535         MEM_freeN(input_verts);
536 }
537
538 /* Check that there are at least three vertices in the input */
539 static int hull_num_input_verts_is_ok(BMOperator *op)
540 {
541         BMOIter oiter;
542         BMVert *v;
543         int partial_num_verts = 0;
544
545         BMO_ITER (v, &oiter, op->slots_in, "input", BM_VERT) {
546                 partial_num_verts++;
547                 if (partial_num_verts >= 3)
548                         break;
549         }
550
551         return (partial_num_verts >= 3);
552 }
553
554 void bmo_convex_hull_exec(BMesh *bm, BMOperator *op)
555 {
556         HullFinalEdges *final_edges;
557         BLI_mempool *hull_pool;
558         BMElemF *ele;
559         BMOIter oiter;
560         GHash *hull_triangles;
561
562         /* Verify that at least three verts in the input */
563         if (!hull_num_input_verts_is_ok(op)) {
564                 BMO_error_raise(bm, op, BMERR_CONVEX_HULL_FAILED,
565                                 "Requires at least three vertices");
566                 return;
567         }
568
569         /* Tag input elements */
570         BMO_ITER (ele, &oiter, op->slots_in, "input", BM_ALL) {
571                 BMO_elem_flag_enable(bm, ele, HULL_FLAG_INPUT);
572                 
573                 /* Mark all vertices as interior to begin with */
574                 if (ele->head.htype == BM_VERT)
575                         BMO_elem_flag_enable(bm, ele, HULL_FLAG_INTERIOR_ELE);
576         }
577
578         hull_pool = BLI_mempool_create(sizeof(HullTriangle), 128, 128, 0);
579         hull_triangles = BLI_ghash_ptr_new("hull_triangles");
580
581         hull_from_bullet(bm, op, hull_triangles, hull_pool);
582
583         final_edges = hull_final_edges(hull_triangles);
584         
585         hull_mark_interior_elements(bm, op, final_edges);
586
587         /* Remove hull triangles covered by an existing face */
588         if (BMO_slot_bool_get(op->slots_in, "use_existing_faces")) {
589                 hull_remove_overlapping(bm, hull_triangles, final_edges);
590
591                 hull_tag_holes(bm, op);
592         }
593
594         /* Done with edges */
595         hull_final_edges_free(final_edges);
596
597         /* Convert hull triangles to BMesh faces */
598         hull_output_triangles(bm, hull_triangles);
599         BLI_mempool_destroy(hull_pool);
600
601         BLI_ghash_free(hull_triangles, NULL, NULL);
602
603         hull_tag_unused(bm, op);
604
605         /* Output slot of input elements that ended up inside the hull
606          * rather than part of it */
607         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_interior.out",
608                                           BM_ALL_NOLOOP, HULL_FLAG_INTERIOR_ELE);
609
610         /* Output slot of input elements that ended up inside the hull and
611          * are are unused by other geometry. */
612         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_unused.out",
613                                           BM_ALL_NOLOOP, HULL_FLAG_DEL);
614
615         /* Output slot of faces and edges that were in the input and on
616          * the hull (useful for cases like bridging where you want to
617          * delete some input geometry) */
618         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom_holes.out",
619                                           BM_ALL_NOLOOP, HULL_FLAG_HOLE);
620
621         /* Output slot of all hull vertices, faces, and edges */
622         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom.out",
623                                           BM_ALL_NOLOOP, HULL_FLAG_OUTPUT_GEOM);
624 }
625
626 #endif  /* WITH_BULLET */