Merged changes in the trunk up to revision 52815.
[blender.git] / source / blender / bmesh / operators / bmo_connect.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): Joseph Eagar.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_connect.c
24  *  \ingroup bmesh
25  */
26
27 #include "MEM_guardedalloc.h"
28
29 #include "BLI_math.h"
30 #include "BLI_array.h"
31 #include "BLI_utildefines.h"
32
33 #include "bmesh.h"
34
35 #include "intern/bmesh_operators_private.h" /* own include */
36
37 #define VERT_INPUT      1
38 #define EDGE_OUT        1
39 #define FACE_NEW        2
40 #define EDGE_MARK       4
41 #define EDGE_DONE       8
42 #define FACE_OUT        16
43
44 void bmo_connect_verts_exec(BMesh *bm, BMOperator *op)
45 {
46         BMIter iter, liter;
47         BMFace *f, *nf;
48         BMLoop *(*loops_split)[2] = NULL;
49         BLI_array_declare(loops_split);
50         BMLoop *l, *nl, *lastl = NULL;
51         BMVert *(*verts_pair)[2] = NULL;
52         BLI_array_declare(verts_pair);
53         int i;
54         
55         BMO_slot_buffer_flag_enable(bm, op->slots_in, "verts", BM_VERT, VERT_INPUT);
56
57         /* BMESH_TODO, loop over vert faces:
58          * faster then looping over all faces, then searching each for flagged verts*/
59         for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) {
60                 BLI_array_empty(loops_split);
61                 BLI_array_empty(verts_pair);
62                 
63                 if (BMO_elem_flag_test(bm, f, FACE_NEW)) {
64                         continue;
65                 }
66
67                 l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
68                 lastl = NULL;
69                 for ( ; l; l = BM_iter_step(&liter)) {
70                         if (BMO_elem_flag_test(bm, l->v, VERT_INPUT)) {
71                                 if (!lastl) {
72                                         lastl = l;
73                                         continue;
74                                 }
75
76                                 if (lastl != l->prev && lastl != l->next) {
77                                         BLI_array_grow_one(loops_split);
78                                         loops_split[BLI_array_count(loops_split) - 1][0] = lastl;
79                                         loops_split[BLI_array_count(loops_split) - 1][1] = l;
80
81                                 }
82                                 lastl = l;
83                         }
84                 }
85
86                 if (BLI_array_count(loops_split) == 0) {
87                         continue;
88                 }
89                 
90                 if (BLI_array_count(loops_split) > 1) {
91                         BLI_array_grow_one(loops_split);
92                         loops_split[BLI_array_count(loops_split) - 1][0] = loops_split[BLI_array_count(loops_split) - 2][1];
93                         loops_split[BLI_array_count(loops_split) - 1][1] = loops_split[0][0];
94                 }
95
96                 BM_face_legal_splits(bm, f, loops_split, BLI_array_count(loops_split));
97                 
98                 for (i = 0; i < BLI_array_count(loops_split); i++) {
99                         if (loops_split[i][0] == NULL) {
100                                 continue;
101                         }
102
103                         BLI_array_grow_one(verts_pair);
104                         verts_pair[BLI_array_count(verts_pair) - 1][0] = loops_split[i][0]->v;
105                         verts_pair[BLI_array_count(verts_pair) - 1][1] = loops_split[i][1]->v;
106                 }
107
108                 for (i = 0; i < BLI_array_count(verts_pair); i++) {
109                         nf = BM_face_split(bm, f, verts_pair[i][0], verts_pair[i][1], &nl, NULL, FALSE);
110                         f = nf;
111                         
112                         if (!nl || !nf) {
113                                 BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL);
114                                 BLI_array_free(loops_split);
115                                 return;
116                         }
117                         BMO_elem_flag_enable(bm, nf, FACE_NEW);
118                         BMO_elem_flag_enable(bm, nl->e, EDGE_OUT);
119                 }
120         }
121
122         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT);
123
124         BLI_array_free(loops_split);
125         BLI_array_free(verts_pair);
126 }
127
128 static BMVert *get_outer_vert(BMesh *bm, BMEdge *e)
129 {
130         BMIter iter;
131         BMEdge *e2;
132         int i;
133
134         i = 0;
135         BM_ITER_ELEM (e2, &iter, e->v1, BM_EDGES_OF_VERT) {
136                 if (BMO_elem_flag_test(bm, e2, EDGE_MARK)) {
137                         i++;
138                 }
139         }
140
141         return (i == 2) ? e->v2 : e->v1;
142 }
143
144 /* Clamp x to the interval {0..len-1}, with wrap-around */
145 static int clamp_index(const int x, const int len)
146 {
147         if (x >= 0) {
148                 return x % len;
149         }
150         else {
151                 int r = len - (-x % len);
152                 if (r == len)
153                         return len - 1;
154                 else
155                         return r;
156         }
157 }
158
159 /* There probably is a better way to swap BLI_arrays, or if there
160  * isn't there should be... */
161 #define ARRAY_SWAP(elemtype, arr1, arr2)                                      \
162         {                                                                         \
163                 int i;                                                                \
164                 elemtype *arr_tmp = NULL;                                             \
165                 BLI_array_declare(arr_tmp);                                           \
166                 for (i = 0; i < BLI_array_count(arr1); i++) {                         \
167                         BLI_array_append(arr_tmp, arr1[i]);                               \
168                 }                                                                     \
169                 BLI_array_empty(arr1);                                                \
170                 for (i = 0; i < BLI_array_count(arr2); i++) {                         \
171                         BLI_array_append(arr1, arr2[i]);                                  \
172                 }                                                                     \
173                 BLI_array_empty(arr2);                                                \
174                 for (i = 0; i < BLI_array_count(arr_tmp); i++) {                      \
175                         BLI_array_append(arr2, arr_tmp[i]);                               \
176                 }                                                                     \
177                 BLI_array_free(arr_tmp);                                              \
178         } (void)0
179
180 /* get the 2 loops matching 2 verts.
181  * first attempt to get the face corners that use the edge defined by v1 & v2,
182  * if that fails just get any loop thats on the vert (the first one) */
183 static void bm_vert_loop_pair(BMesh *bm, BMVert *v1, BMVert *v2, BMLoop **l1, BMLoop **l2)
184 {
185         BMIter liter;
186         BMLoop *l;
187
188         if ((v1->e && v1->e->l) &&
189             (v2->e && v2->e->l))
190         {
191                 BM_ITER_ELEM (l, &liter, v1, BM_LOOPS_OF_VERT) {
192                         if (l->prev->v == v2) {
193                                 *l1 = l;
194                                 *l2 = l->prev;
195                                 return;
196                         }
197                         else if (l->next->v == v2) {
198                                 *l1 = l;
199                                 *l2 = l->next;
200                                 return;
201                         }
202                 }
203         }
204
205         /* fallback to _any_ loop */
206         *l1 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v1, 0);
207         *l2 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v2, 0);
208 }
209
210 void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op)
211 {
212         BMEdge **ee1 = NULL, **ee2 = NULL;
213         BMVert **vv1 = NULL, **vv2 = NULL;
214         BLI_array_declare(ee1);
215         BLI_array_declare(ee2);
216         BLI_array_declare(vv1);
217         BLI_array_declare(vv2);
218         BMOIter siter;
219         BMIter iter;
220         BMEdge *e, *nexte;
221         int c = 0, cl1 = 0, cl2 = 0;
222
223         /* merge-bridge support */
224         const int   use_merge    = BMO_slot_bool_get(op->slots_in,  "use_merge");
225         const float merge_factor = BMO_slot_float_get(op->slots_in, "merge_factor");
226
227         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
228
229         BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
230                 if (!BMO_elem_flag_test(bm, e, EDGE_DONE)) {
231                         BMVert *v, *ov;
232                         /* BMEdge *e2, *e3, *oe = e; */ /* UNUSED */
233                         BMEdge *e2, *e3;
234                         
235                         if (c > 2) {
236                                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, "Select only two edge loops");
237                                 goto cleanup;
238                         }
239                         
240                         e2 = e;
241                         v = e->v1;
242                         do {
243                                 v = BM_edge_other_vert(e2, v);
244                                 nexte = NULL;
245                                 BM_ITER_ELEM (e3, &iter, v, BM_EDGES_OF_VERT) {
246                                         if (e3 != e2 && BMO_elem_flag_test(bm, e3, EDGE_MARK)) {
247                                                 if (nexte == NULL) {
248                                                         nexte = e3;
249                                                 }
250                                                 else {
251                                                         /* edges do not form a loop: there is a disk
252                                                          * with more than two marked edges. */
253                                                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
254                                                                         "Selection must only contain edges from two edge loops");
255                                                         goto cleanup;
256                                                 }
257                                         }
258                                 }
259                                 
260                                 if (nexte)
261                                         e2 = nexte;
262                         } while (nexte && e2 != e);
263                         
264                         if (!e2)
265                                 e2 = e;
266
267                         e = e2;
268                         ov = v;
269                         do {
270                                 if (c == 0) {
271                                         BLI_array_append(ee1, e2);
272                                         BLI_array_append(vv1, v);
273                                 }
274                                 else {
275                                         BLI_array_append(ee2, e2);
276                                         BLI_array_append(vv2, v);
277                                 }
278                                 
279                                 BMO_elem_flag_enable(bm, e2, EDGE_DONE);
280                                 
281                                 v = BM_edge_other_vert(e2, v);
282                                 BM_ITER_ELEM (e3, &iter, v, BM_EDGES_OF_VERT) {
283                                         if (e3 != e2 && BMO_elem_flag_test(bm, e3, EDGE_MARK) && !BMO_elem_flag_test(bm, e3, EDGE_DONE)) {
284                                                 break;
285                                         }
286                                 }
287                                 if (e3)
288                                         e2 = e3;
289                         } while (e3 && e2 != e);
290                         
291                         if (v && !e3) {
292                                 if (c == 0) {
293                                         if (BLI_array_count(vv1) && v == vv1[BLI_array_count(vv1) - 1]) {
294                                                 printf("%s: internal state waning *TODO DESCRIPTION!*\n", __func__);
295                                         }
296                                         BLI_array_append(vv1, v);
297                                 }
298                                 else {
299                                         BLI_array_append(vv2, v);
300                                 }
301                         }
302                         
303                         /* test for connected loops, and set cl1 or cl2 if so */
304                         if (v == ov) {
305                                 if (c == 0) {
306                                         cl1 = 1;
307                                 }
308                                 else {
309                                         cl2 = 1;
310                                 }
311                         }
312                         
313                         c++;
314                 }
315         }
316
317         if (ee1 && ee2) {
318                 int i, j;
319                 BMVert *v1, *v2, *v3, *v4;
320                 int starti = 0, dir1 = 1, wdir = 0, lenv1, lenv2;
321
322                 /* Simplify code below by avoiding the (!cl1 && cl2) case */
323                 if (!cl1 && cl2) {
324                         SWAP(int, cl1, cl2);
325                         ARRAY_SWAP(BMVert *, vv1, vv2);
326                         ARRAY_SWAP(BMEdge *, ee1, ee2);
327                 }
328
329                 lenv1 = lenv2 = BLI_array_count(vv1);
330
331                 /* Below code assumes vv1/vv2 each have at least two verts. should always be
332                  * a safe assumption, since ee1/ee2 are non-empty and an edge has two verts. */
333                 BLI_assert((lenv1 > 1) && (lenv2 > 1));
334
335                 /* BMESH_TODO: Would be nice to handle cases where the edge loops
336                  * have different edge counts by generating triangles & quads for
337                  * the bridge instead of quads only. */
338                 if (BLI_array_count(ee1) != BLI_array_count(ee2)) {
339                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
340                                         "Selected loops must have equal edge counts");
341                         goto cleanup;
342                 }
343
344                 if (vv1[0] == vv1[lenv1 - 1]) {
345                         lenv1--;
346                 }
347                 if (vv2[0] == vv2[lenv2 - 1]) {
348                         lenv2--;
349                 }
350
351                 /* Find starting point and winding direction for two unclosed loops */
352                 if (!cl1 && !cl2) {
353                         /* First point of loop 1 */
354                         v1 = get_outer_vert(bm, ee1[0]);
355                         /* Last point of loop 1 */
356                         v2 = get_outer_vert(bm, ee1[clamp_index(-1, BLI_array_count(ee1))]);
357                         /* First point of loop 2 */
358                         v3 = get_outer_vert(bm, ee2[0]);
359                         /* Last point of loop 2 */
360                         v4 = get_outer_vert(bm, ee2[clamp_index(-1, BLI_array_count(ee2))]);
361
362                         /* If v1 is a better match for v4 than v3, AND v2 is a better match
363                          * for v3 than v4, the loops are in opposite directions, so reverse
364                          * the order of reads from vv1. We can avoid sqrt for comparison */
365                         if (len_squared_v3v3(v1->co, v3->co) > len_squared_v3v3(v1->co, v4->co) &&
366                             len_squared_v3v3(v2->co, v4->co) > len_squared_v3v3(v2->co, v3->co))
367                         {
368                                 dir1 = -1;
369                                 starti = clamp_index(-1, lenv1);
370                         }
371                 }
372
373                 /* Find the smallest sum of distances from verts in vv1 to verts in vv2,
374                  * finding a starting point in the first loop, to start with vv2[0] in the
375                  * second loop. This is a simplistic attempt to get a better edge-to-edge
376                  * match between two loops. */
377                 if (cl1) {
378                         float min = 1e32;
379
380                         for (i = 0; i < lenv1; i++) {
381                                 float len;
382
383                                 /* compute summed length between vertices in forward direction */
384                                 len = 0.0f;
385                                 for (j = 0; (j < lenv2) && (len < min); j++) {
386                                         len += len_v3v3(vv1[clamp_index(i + j, lenv1)]->co, vv2[j]->co);
387                                 }
388
389                                 if (len < min) {
390                                         min = len;
391                                         starti = i;
392                                         dir1 = 1;
393                                 }
394
395                                 /* compute summed length between vertices in backward direction */
396                                 len = 0.0f;
397                                 for (j = 0; (j < lenv2) && (len < min); j++) {
398                                         len += len_v3v3(vv1[clamp_index(i - j, lenv1)]->co, vv2[j]->co);
399                                 }
400
401                                 if (len < min) {
402                                         min = len;
403                                         starti = i;
404                                         dir1 = -1;
405                                 }
406                         }
407                 }
408
409                 /* Vert rough attempt to determine proper winding for the bridge quads:
410                  * just uses the first loop it finds for any of the edges of ee2 or ee1 */
411                 if (wdir == 0) {
412                         for (i = 0; i < BLI_array_count(ee2); i++) {
413                                 if (ee2[i]->l) {
414                                         wdir = (ee2[i]->l->v == vv2[i]) ? (-1) : (1);
415                                         break;
416                                 }
417                         }
418                 }
419                 if (wdir == 0) {
420                         for (i = 0; i < BLI_array_count(ee1); i++) {
421                                 j = clamp_index((i * dir1) + starti, BLI_array_count(ee1));
422                                 if (ee1[j]->l && ee2[j]->l) {
423                                         wdir = (ee2[j]->l->v == vv2[j]) ? (1) : (-1);
424                                         break;
425                                 }
426                         }
427                 }
428                 
429                 /* merge loops of bridge faces */
430                 if (use_merge) {
431                         const int vert_len = min_ii(BLI_array_count(vv1), BLI_array_count(vv2)) - ((cl1 || cl2) ? 1 : 0);
432                         const int edge_len = min_ii(BLI_array_count(ee1), BLI_array_count(ee2));
433
434                         if (merge_factor <= 0.0f) {
435                                 /* 2 --> 1 */
436                                 for (i = 0; i < vert_len; i++) {
437                                         BM_vert_splice(bm, vv2[i], vv1[i]);
438                                 }
439                                 for (i = 0; i < edge_len; i++) {
440                                         BM_edge_splice(bm, ee2[i], ee1[i]);
441                                 }
442                         }
443                         else if (merge_factor >= 1.0f) {
444                                 /* 1 --> 2 */
445                                 for (i = 0; i < vert_len; i++) {
446                                         BM_vert_splice(bm, vv1[i], vv2[i]);
447                                 }
448                                 for (i = 0; i < edge_len; i++) {
449                                         BM_edge_splice(bm, ee1[i], ee2[i]);
450                                 }
451                         }
452                         else {
453                                 /* mid factor, be tricky */
454                                 /* 1 --> 2 */
455                                 for (i = 0; i < vert_len; i++) {
456                                         BM_data_interp_from_verts(bm, vv1[i], vv2[i], vv2[i], merge_factor);
457                                         interp_v3_v3v3(vv2[i]->co, vv1[i]->co, vv2[i]->co, merge_factor);
458                                         BM_elem_flag_merge(vv1[i], vv2[i]);
459                                         BM_vert_splice(bm, vv1[i], vv2[i]);
460                                 }
461                                 for (i = 0; i < edge_len; i++) {
462                                         BM_data_interp_from_edges(bm, ee1[i], ee2[i], ee2[i], merge_factor);
463                                         BM_elem_flag_merge(ee1[i], ee2[i]);
464                                         BM_edge_splice(bm, ee1[i], ee2[i]);
465                                 }
466                         }
467                 }
468                 else {
469                         /* Generate the bridge quads */
470                         for (i = 0; i < BLI_array_count(ee1) && i < BLI_array_count(ee2); i++) {
471                                 BMFace *f;
472
473                                 BMLoop *l_1 = NULL;
474                                 BMLoop *l_2 = NULL;
475                                 BMLoop *l_1_next = NULL;
476                                 BMLoop *l_2_next = NULL;
477                                 BMLoop *l_iter;
478                                 BMFace *f_example;
479
480                                 int i1, i1next, i2, i2next;
481
482                                 i1 = clamp_index(i * dir1 + starti, lenv1);
483                                 i1next = clamp_index((i + 1) * dir1 + starti, lenv1);
484                                 i2 = i;
485                                 i2next = clamp_index(i + 1, lenv2);
486
487                                 if (vv1[i1] == vv1[i1next]) {
488                                         continue;
489                                 }
490
491                                 if (wdir < 0) {
492                                         SWAP(int, i1, i1next);
493                                         SWAP(int, i2, i2next);
494                                 }
495
496                                 /* get loop data - before making the face */
497                                 bm_vert_loop_pair(bm, vv1[i1], vv2[i2], &l_1, &l_2);
498                                 bm_vert_loop_pair(bm, vv1[i1next], vv2[i2next], &l_1_next, &l_2_next);
499                                 /* copy if loop data if its is missing on one ring */
500                                 if (l_1 && l_1_next == NULL) l_1_next = l_1;
501                                 if (l_1_next && l_1 == NULL) l_1 = l_1_next;
502                                 if (l_2 && l_2_next == NULL) l_2_next = l_2;
503                                 if (l_2_next && l_2 == NULL) l_2 = l_2_next;
504                                 f_example = l_1 ? l_1->f : (l_2 ? l_2->f : NULL);
505
506                                 f = BM_face_create_quad_tri(bm,
507                                                             vv1[i1],
508                                                             vv2[i2],
509                                                             vv2[i2next],
510                                                             vv1[i1next],
511                                                             f_example, TRUE);
512                                 if (UNLIKELY((f == NULL) || (f->len != 4))) {
513                                         fprintf(stderr, "%s: in bridge! (bmesh internal error)\n", __func__);
514                                 }
515                                 else {
516                                         BMO_elem_flag_enable(bm, f, FACE_OUT);
517
518                                         l_iter = BM_FACE_FIRST_LOOP(f);
519
520                                         if (l_1)      BM_elem_attrs_copy(bm, bm, l_1,      l_iter); l_iter = l_iter->next;
521                                         if (l_2)      BM_elem_attrs_copy(bm, bm, l_2,      l_iter); l_iter = l_iter->next;
522                                         if (l_2_next) BM_elem_attrs_copy(bm, bm, l_2_next, l_iter); l_iter = l_iter->next;
523                                         if (l_1_next) BM_elem_attrs_copy(bm, bm, l_1_next, l_iter);
524                                 }
525                         }
526                 }
527         }
528
529         BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
530
531 cleanup:
532         BLI_array_free(ee1);
533         BLI_array_free(ee2);
534         BLI_array_free(vv1);
535         BLI_array_free(vv2);
536 }