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