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