Merged changes in the trunk up to revision 52191.
[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, TRUE),
117                                 BM_edge_create(bm, t->v[1], t->v[2], NULL, TRUE),
118                                 BM_edge_create(bm, t->v[2], t->v[0], NULL, TRUE)
119                         };
120                         BMFace *f, *example = NULL;
121
122                         if (BM_face_exists(bm, 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 'geomout' 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 'geomout' 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 'geomout' 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                                         BMO_elem_flag_enable(bm, e, HULL_FLAG_OUTPUT_GEOM);
160                                 }
161                         }
162                 }
163
164                 /* Mark verts for 'geomout' 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(GHash *hull_triangles)
210 {
211         HullFinalEdges *final_edges;
212         GHashIterator 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, 0);
217         final_edges->link_pool = BLI_mempool_create(sizeof(LinkData), 128, 128, 0);
218
219         GHASH_ITER (iter, hull_triangles) {
220                 LinkData *link;
221                 int i;
222                 
223                 for (i = 0; i < 3; i++) {
224                         HullTriangle *t = BLI_ghashIterator_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, GHash *hull_triangles,
263                                     HullFinalEdges *final_edges)
264 {
265         GHashIterator hull_iter;
266
267         GHASH_ITER (hull_iter, hull_triangles) {
268                 HullTriangle *t = BLI_ghashIterator_getKey(&hull_iter);
269                 BMIter bm_iter1, bm_iter2;
270                 BMFace *f;
271                 int 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, bm, op, "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, bm, op, "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, bm, op, "input", BM_VERT) {
332                 if (BMO_elem_flag_test(bm, v, HULL_FLAG_INTERIOR_ELE)) {
333                         int 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, bm, op, "input", BM_EDGE) {
355                 if (BMO_elem_flag_test(bm, e, HULL_FLAG_INTERIOR_ELE)) {
356                         int 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, bm, op, "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, bm, op, "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, bm, op, "input", BM_EDGE) {
399                 int hole = TRUE;
400                 int 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(BMesh *bm, BMOperator *op)
416 {
417         BMOIter oiter;
418         BMVert *v;
419         int count = 0;
420
421         BMO_ITER (v, &oiter, bm, op, "input", BM_VERT) {
422                 count++;
423         }
424
425         return count;
426 }
427
428 static BMVert **hull_input_verts_copy(BMesh *bm, 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, bm, op, "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, AT);
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                              GHash *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(bm, op);
496
497         input_verts = hull_input_verts_copy(bm, 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 int hull_num_input_verts_is_ok(BMesh *bm, BMOperator *op)
539 {
540         BMOIter oiter;
541         BMVert *v;
542         int partial_num_verts = 0;
543
544         BMO_ITER (v, &oiter, bm, op, "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         GHash *hull_triangles;
560
561         /* Verify that at least three verts in the input */
562         if (!hull_num_input_verts_is_ok(bm, 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, bm, op, "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, 0);
578         hull_triangles = BLI_ghash_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, "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_ghash_free(hull_triangles, NULL, 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, "interior_geom", BM_ALL,
607                                           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, "unused_geom", BM_ALL,
612                                           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, "holes_geom", BM_ALL,
618                                           HULL_FLAG_HOLE);
619
620         /* Output slot of all hull vertices, faces, and edges */
621         BMO_slot_buffer_from_enabled_flag(bm, op, "geomout", BM_ALL,
622                                           HULL_FLAG_OUTPUT_GEOM);
623 }
624
625 #endif  /* WITH_BULLET */