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