Merging r45936 through r46042 from trunk into soc-2011-tomato
[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
43 void bmo_connectverts_exec(BMesh *bm, BMOperator *op)
44 {
45         BMIter iter, liter;
46         BMFace *f, *nf;
47         BMLoop **loops = NULL, *lastl = NULL;
48         BLI_array_declare(loops);
49         BMLoop *l, *nl;
50         BMVert **verts = NULL;
51         BLI_array_declare(verts);
52         int i;
53         
54         BMO_slot_buffer_flag_enable(bm, op, "verts", BM_VERT, VERT_INPUT);
55
56         for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) {
57                 BLI_array_empty(loops);
58                 BLI_array_empty(verts);
59                 
60                 if (BMO_elem_flag_test(bm, f, FACE_NEW)) {
61                         continue;
62                 }
63
64                 l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
65                 lastl = NULL;
66                 for ( ; l; l = BM_iter_step(&liter)) {
67                         if (BMO_elem_flag_test(bm, l->v, VERT_INPUT)) {
68                                 if (!lastl) {
69                                         lastl = l;
70                                         continue;
71                                 }
72
73                                 if (lastl != l->prev && lastl != l->next) {
74                                         BLI_array_grow_one(loops);
75                                         loops[BLI_array_count(loops) - 1] = lastl;
76
77                                         BLI_array_grow_one(loops);
78                                         loops[BLI_array_count(loops) - 1] = l;
79
80                                 }
81                                 lastl = l;
82                         }
83                 }
84
85                 if (BLI_array_count(loops) == 0) {
86                         continue;
87                 }
88                 
89                 if (BLI_array_count(loops) > 2) {
90                         BLI_array_grow_one(loops);
91                         loops[BLI_array_count(loops) - 1] = loops[BLI_array_count(loops) - 2];
92
93                         BLI_array_grow_one(loops);
94                         loops[BLI_array_count(loops) - 1] = loops[0];
95                 }
96
97                 BM_face_legal_splits(bm, f, (BMLoop *(*)[2])loops, BLI_array_count(loops) / 2);
98                 
99                 for (i = 0; i < BLI_array_count(loops) / 2; i++) {
100                         if (loops[i * 2] == NULL) {
101                                 continue;
102                         }
103
104                         BLI_array_grow_one(verts);
105                         verts[BLI_array_count(verts) - 1] = loops[i * 2]->v;
106
107                         BLI_array_grow_one(verts);
108                         verts[BLI_array_count(verts) - 1] = loops[i * 2 + 1]->v;
109                 }
110
111                 for (i = 0; i < BLI_array_count(verts) / 2; i++) {
112                         nf = BM_face_split(bm, f, verts[i * 2], verts[i * 2 + 1], &nl, NULL, FALSE);
113                         f = nf;
114                         
115                         if (!nl || !nf) {
116                                 BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL);
117                                 BLI_array_free(loops);
118                                 return;
119                         }
120                         BMO_elem_flag_enable(bm, nf, FACE_NEW);
121                         BMO_elem_flag_enable(bm, nl->e, EDGE_OUT);
122                 }
123         }
124
125         BMO_slot_buffer_from_enabled_flag(bm, op, "edgeout", BM_EDGE, EDGE_OUT);
126
127         BLI_array_free(loops);
128         BLI_array_free(verts);
129 }
130
131 static BMVert *get_outer_vert(BMesh *bm, BMEdge *e)
132 {
133         BMIter iter;
134         BMEdge *e2;
135         int i;
136
137         i = 0;
138         BM_ITER_ELEM (e2, &iter, e->v1, BM_EDGES_OF_VERT) {
139                 if (BMO_elem_flag_test(bm, e2, EDGE_MARK)) {
140                         i++;
141                 }
142         }
143
144         return (i == 2) ? e->v2 : e->v1;
145 }
146
147 /* Clamp x to the interval {0..len-1}, with wrap-around */
148 static int clamp_index(const int x, const int len)
149 {
150         if (x >= 0) {
151                 return x % len;
152         }
153         else {
154                 int r = len - (-x % len);
155                 if (r == len)
156                         return len - 1;
157                 else
158                         return r;
159         }
160 }
161
162 /* There probably is a better way to swap BLI_arrays, or if there
163  * isn't there should be... */
164 #define ARRAY_SWAP(elemtype, arr1, arr2)                                      \
165         {                                                                         \
166                 int i;                                                                \
167                 elemtype *arr_tmp = NULL;                                             \
168                 BLI_array_declare(arr_tmp);                                           \
169                 for (i = 0; i < BLI_array_count(arr1); i++) {                         \
170                         BLI_array_append(arr_tmp, arr1[i]);                               \
171                 }                                                                     \
172                 BLI_array_empty(arr1);                                                \
173                 for (i = 0; i < BLI_array_count(arr2); i++) {                         \
174                         BLI_array_append(arr1, arr2[i]);                                  \
175                 }                                                                     \
176                 BLI_array_empty(arr2);                                                \
177                 for (i = 0; i < BLI_array_count(arr_tmp); i++) {                      \
178                         BLI_array_append(arr2, arr_tmp[i]);                               \
179                 }                                                                     \
180                 BLI_array_free(arr_tmp);                                              \
181         }
182
183 /* get the 2 loops matching 2 verts.
184  * first attempt to get the face corners that use the edge defined by v1 & v2,
185  * if that fails just get any loop thats on the vert (the first one) */
186 static void bm_vert_loop_pair(BMesh *bm, BMVert *v1, BMVert *v2, BMLoop **l1, BMLoop **l2)
187 {
188         BMIter liter;
189         BMLoop *l;
190
191         if ((v1->e && v1->e->l) &&
192             (v2->e && v2->e->l))
193         {
194                 BM_ITER_ELEM (l, &liter, v1, BM_LOOPS_OF_VERT) {
195                         if (l->prev->v == v2) {
196                                 *l1 = l;
197                                 *l2 = l->prev;
198                                 return;
199                         }
200                         else if (l->next->v == v2) {
201                                 *l1 = l;
202                                 *l2 = l->next;
203                                 return;
204                         }
205                 }
206         }
207
208         /* fallback to _any_ loop */
209         *l1 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v1, 0);
210         *l2 = BM_iter_at_index(bm, BM_LOOPS_OF_VERT, v2, 0);
211 }
212
213 void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op)
214 {
215         BMEdge **ee1 = NULL, **ee2 = NULL;
216         BMVert **vv1 = NULL, **vv2 = NULL;
217         BLI_array_declare(ee1);
218         BLI_array_declare(ee2);
219         BLI_array_declare(vv1);
220         BLI_array_declare(vv2);
221         BMOIter siter;
222         BMIter iter;
223         BMEdge *e, *nexte;
224         int c = 0, cl1 = 0, cl2 = 0;
225
226         BMO_slot_buffer_flag_enable(bm, op, "edges", BM_EDGE, EDGE_MARK);
227
228         BMO_ITER (e, &siter, bm, op, "edges", BM_EDGE) {
229                 if (!BMO_elem_flag_test(bm, e, EDGE_DONE)) {
230                         BMVert *v, *ov;
231                         /* BMEdge *e2, *e3, *oe = e; */ /* UNUSED */
232                         BMEdge *e2, *e3;
233                         
234                         if (c > 2) {
235                                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, "Select only two edge loops");
236                                 goto cleanup;
237                         }
238                         
239                         e2 = e;
240                         v = e->v1;
241                         do {
242                                 v = BM_edge_other_vert(e2, v);
243                                 nexte = NULL;
244                                 BM_ITER_ELEM (e3, &iter, v, BM_EDGES_OF_VERT) {
245                                         if (e3 != e2 && BMO_elem_flag_test(bm, e3, EDGE_MARK)) {
246                                                 if (nexte == NULL) {
247                                                         nexte = e3;
248                                                 }
249                                                 else {
250                                                         /* edges do not form a loop: there is a disk
251                                                          * with more than two marked edges. */
252                                                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
253                                                                         "Selection must only contain edges from two edge loops");
254                                                         goto cleanup;
255                                                 }
256                                         }
257                                 }
258                                 
259                                 if (nexte)
260                                         e2 = nexte;
261                         } while (nexte && e2 != e);
262                         
263                         if (!e2)
264                                 e2 = e;
265
266                         e = e2;
267                         ov = v;
268                         do {
269                                 if (c == 0) {
270                                         BLI_array_append(ee1, e2);
271                                         BLI_array_append(vv1, v);
272                                 }
273                                 else {
274                                         BLI_array_append(ee2, e2);
275                                         BLI_array_append(vv2, v);
276                                 }
277                                 
278                                 BMO_elem_flag_enable(bm, e2, EDGE_DONE);
279                                 
280                                 v = BM_edge_other_vert(e2, v);
281                                 BM_ITER_ELEM (e3, &iter, v, BM_EDGES_OF_VERT) {
282                                         if (e3 != e2 && BMO_elem_flag_test(bm, e3, EDGE_MARK) && !BMO_elem_flag_test(bm, e3, EDGE_DONE)) {
283                                                 break;
284                                         }
285                                 }
286                                 if (e3)
287                                         e2 = e3;
288                         } while (e3 && e2 != e);
289                         
290                         if (v && !e3) {
291                                 if (c == 0) {
292                                         if (BLI_array_count(vv1) && v == vv1[BLI_array_count(vv1) - 1]) {
293                                                 printf("%s: internal state waning *TODO DESCRIPTION!*\n", __func__);
294                                         }
295                                         BLI_array_append(vv1, v);
296                                 }
297                                 else {
298                                         BLI_array_append(vv2, v);
299                                 }
300                         }
301                         
302                         /* test for connected loops, and set cl1 or cl2 if so */
303                         if (v == ov) {
304                                 if (c == 0) {
305                                         cl1 = 1;
306                                 }
307                                 else {
308                                         cl2 = 1;
309                                 }
310                         }
311                         
312                         c++;
313                 }
314         }
315
316         if (ee1 && ee2) {
317                 int i, j;
318                 BMVert *v1, *v2, *v3, *v4;
319                 int starti = 0, dir1 = 1, wdir = 0, lenv1, lenv2;
320
321                 /* Simplify code below by avoiding the (!cl1 && cl2) case */
322                 if (!cl1 && cl2) {
323                         SWAP(int, cl1, cl2);
324                         ARRAY_SWAP(BMVert *, vv1, vv2);
325                         ARRAY_SWAP(BMEdge *, ee1, ee2);
326                 }
327
328                 lenv1 = lenv2 = BLI_array_count(vv1);
329
330                 /* Below code assumes vv1/vv2 each have at least two verts. should always be
331                  * a safe assumption, since ee1/ee2 are non-empty and an edge has two verts. */
332                 BLI_assert((lenv1 > 1) && (lenv2 > 1));
333
334                 /* BMESH_TODO: Would be nice to handle cases where the edge loops
335                  * have different edge counts by generating triangles & quads for
336                  * the bridge instead of quads only. */
337                 if (BLI_array_count(ee1) != BLI_array_count(ee2)) {
338                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
339                                         "Selected loops must have equal edge counts");
340                         goto cleanup;
341                 }
342
343                 j = 0;
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 shortest distance from a vert in vv1 to vv2[0]. Use that
374                  * vertex in vv1 as a starting point in the first loop, while starting
375                  * from vv2[0] in the second loop. This is a simplistic attempt to get
376                  * a better edge-to-edge match between the two loops. */
377                 if (cl1) {
378                         int previ, nexti;
379                         float min = 1e32;
380
381                         /* BMESH_TODO: Would be nice to do a more thorough analysis of all
382                          * the vertices in both loops to find a more accurate match for the
383                          * starting point and winding direction of the bridge generation. */
384                         
385                         for (i = 0; i < BLI_array_count(vv1); i++) {
386                                 if (len_v3v3(vv1[i]->co, vv2[0]->co) < min) {
387                                         min = len_v3v3(vv1[i]->co, vv2[0]->co);
388                                         starti = i;
389                                 }
390                         }
391
392                         /* Reverse iteration order for the first loop if the distance of
393                          * the (starti - 1) vert from vv1 is a better match for vv2[1] than
394                          * the (starti + 1) vert.
395                          *
396                          * This is not always going to be right, but it will work better in
397                          * the average case.
398                          */
399                         previ = clamp_index(starti - 1, lenv1);
400                         nexti = clamp_index(starti + 1, lenv1);
401
402                         /* avoid sqrt for comparison */
403                         if (len_squared_v3v3(vv1[nexti]->co, vv2[1]->co) > len_squared_v3v3(vv1[previ]->co, vv2[1]->co)) {
404                                 /* reverse direction for reading vv1 (1 is forward, -1 is backward) */
405                                 dir1 = -1;
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                 /* Generate the bridge quads */
430                 for (i = 0; i < BLI_array_count(ee1) && i < BLI_array_count(ee2); i++) {
431                         BMFace *f;
432
433                         BMLoop *l_1 = NULL;
434                         BMLoop *l_2 = NULL;
435                         BMLoop *l_1_next = NULL;
436                         BMLoop *l_2_next = NULL;
437                         BMLoop *l_iter;
438                         BMFace *f_example;
439
440                         int i1, i1next, i2, i2next;
441
442                         i1 = clamp_index(i * dir1 + starti, lenv1);
443                         i1next = clamp_index((i + 1) * dir1 + starti, lenv1);
444                         i2 = i;
445                         i2next = clamp_index(i + 1, lenv2);
446
447                         if (vv1[i1] ==  vv1[i1next]) {
448                                 continue;
449                         }
450
451                         if (wdir < 0) {
452                                 SWAP(int, i1, i1next);
453                                 SWAP(int, i2, i2next);
454                         }
455
456                         /* get loop data - before making the face */
457                         bm_vert_loop_pair(bm, vv1[i1], vv2[i2], &l_1, &l_2);
458                         bm_vert_loop_pair(bm, vv1[i1next], vv2[i2next], &l_1_next, &l_2_next);
459                         /* copy if loop data if its is missing on one ring */
460                         if (l_1 && l_1_next == NULL) l_1_next = l_1;
461                         if (l_1_next && l_1 == NULL) l_1 = l_1_next;
462                         if (l_2 && l_2_next == NULL) l_2_next = l_2;
463                         if (l_2_next && l_2 == NULL) l_2 = l_2_next;
464                         f_example = l_1 ? l_1->f : (l_2 ? l_2->f : NULL);
465
466                         f = BM_face_create_quad_tri(bm,
467                                                     vv1[i1],
468                                                     vv2[i2],
469                                                     vv2[i2next],
470                                                     vv1[i1next],
471                                                     f_example, TRUE);
472                         if (!f || f->len != 4) {
473                                 fprintf(stderr, "%s: in bridge! (bmesh internal error)\n", __func__);
474                         }
475                         else {
476                                 l_iter = BM_FACE_FIRST_LOOP(f);
477
478                                 if (l_1)      BM_elem_attrs_copy(bm, bm, l_1,      l_iter); l_iter = l_iter->next;
479                                 if (l_2)      BM_elem_attrs_copy(bm, bm, l_2,      l_iter); l_iter = l_iter->next;
480                                 if (l_2_next) BM_elem_attrs_copy(bm, bm, l_2_next, l_iter); l_iter = l_iter->next;
481                                 if (l_1_next) BM_elem_attrs_copy(bm, bm, l_1_next, l_iter);
482                         }
483                 }
484         }
485
486 cleanup:
487         BLI_array_free(ee1);
488         BLI_array_free(ee2);
489         BLI_array_free(vv1);
490         BLI_array_free(vv2);
491 }