indentation cleanup
[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 #include "MEM_guardedalloc.h"
24
25
26 #include "bmesh.h"
27
28 #include "BLI_math.h"
29 #include "BLI_array.h"
30
31 #define VERT_INPUT      1
32 #define EDGE_OUT        1
33 #define FACE_NEW        2
34 #define EDGE_MARK       4
35 #define EDGE_DONE       8
36
37 void connectverts_exec(BMesh *bm, BMOperator *op)
38 {
39         BMIter iter, liter;
40         BMFace *f, *nf;
41         BMLoop **loops = NULL, *lastl = NULL;
42         BLI_array_declare(loops);
43         BMLoop *l, *nl;
44         BMVert **verts = NULL;
45         BLI_array_declare(verts);
46         int i;
47         
48         BMO_slot_buffer_flag(bm, op, "verts", VERT_INPUT, BM_VERT);
49
50         for (f = BM_iter_new(&iter, bm, BM_FACES_OF_MESH, NULL); f; f = BM_iter_step(&iter)) {
51                 BLI_array_empty(loops);
52                 BLI_array_empty(verts);
53                 
54                 if (BMO_elem_flag_test(bm, f, FACE_NEW)) continue;
55
56                 l = BM_iter_new(&liter, bm, BM_LOOPS_OF_FACE, f);
57                 lastl = NULL;
58                 for ( ; l; l = BM_iter_step(&liter)) {
59                         if (BMO_elem_flag_test(bm, l->v, VERT_INPUT)) {
60                                 if (!lastl) {
61                                         lastl = l;
62                                         continue;
63                                 }
64
65                                 if (lastl != l->prev && lastl != l->next) {
66                                         BLI_array_growone(loops);
67                                         loops[BLI_array_count(loops) - 1] = lastl;
68
69                                         BLI_array_growone(loops);
70                                         loops[BLI_array_count(loops) - 1] = l;
71
72                                 }
73                                 lastl = l;
74                         }
75                 }
76
77                 if (BLI_array_count(loops) == 0) continue;
78                 
79                 if (BLI_array_count(loops) > 2) {
80                         BLI_array_growone(loops);
81                         loops[BLI_array_count(loops) - 1] = loops[BLI_array_count(loops) - 2];
82
83                         BLI_array_growone(loops);
84                         loops[BLI_array_count(loops) - 1] = loops[0];
85                 }
86
87                 BM_face_legal_splits(bm, f, (BMLoop *(*)[2])loops, BLI_array_count(loops) / 2);
88                 
89                 for (i = 0; i < BLI_array_count(loops) / 2; i++) {
90                         if (loops[i * 2] == NULL) continue;
91
92                         BLI_array_growone(verts);
93                         verts[BLI_array_count(verts) - 1] = loops[i * 2]->v;
94
95                         BLI_array_growone(verts);
96                         verts[BLI_array_count(verts) - 1] = loops[i * 2 + 1]->v;
97                 }
98
99                 for (i = 0; i < BLI_array_count(verts) / 2; i++) {
100                         nf = BM_face_split(bm, f, verts[i * 2], verts[i * 2 + 1], &nl, NULL);
101                         f = nf;
102                         
103                         if (!nl || !nf) {
104                                 BMO_error_raise(bm, op, BMERR_CONNECTVERT_FAILED, NULL);
105                                 BLI_array_free(loops);
106                                 return;
107                         }
108                         BMO_elem_flag_set(bm, nf, FACE_NEW);
109                         BMO_elem_flag_set(bm, nl->e, EDGE_OUT);
110                 }
111         }
112
113         BMO_slot_from_flag(bm, op, "edgeout", EDGE_OUT, BM_EDGE);
114
115         BLI_array_free(loops);
116         BLI_array_free(verts);
117 }
118
119 static BMVert *get_outer_vert(BMesh *bm, BMEdge *e)
120 {
121         BMIter iter;
122         BMEdge *e2;
123         int i;
124
125         i = 0;
126         BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, e->v1) {
127                 if (BMO_elem_flag_test(bm, e2, EDGE_MARK)) {
128                         i++;
129                 }
130         }
131
132         return (i == 2) ? e->v2 : e->v1;
133 }
134
135 /* Clamp x to the interval {0..len-1}, with wrap-around */
136 static int clamp_index(const int x, const int len)
137 {
138         return (x < 0) ? (len - (-x % len)) : (x % len);
139 }
140
141 /* There probably is a better way to swap BLI_arrays, or if there
142  * isn't there should be... */
143 #define ARRAY_SWAP(elemtype, arr1, arr2)                                      \
144         {                                                                         \
145                 int i;                                                                \
146                 elemtype *arr_tmp = NULL;                                             \
147                 BLI_array_declare(arr_tmp);                                           \
148                 for (i = 0; i < BLI_array_count(arr1); i++) {                         \
149                         BLI_array_append(arr_tmp, arr1[i]);                               \
150                 }                                                                     \
151                 BLI_array_empty(arr1);                                                \
152                 for (i = 0; i < BLI_array_count(arr2); i++) {                         \
153                         BLI_array_append(arr1, arr2[i]);                                  \
154                 }                                                                     \
155                 BLI_array_empty(arr2);                                                \
156                 for (i = 0; i < BLI_array_count(arr_tmp); i++) {                      \
157                         BLI_array_append(arr2, arr_tmp[i]);                               \
158                 }                                                                     \
159                 BLI_array_free(arr_tmp);                                              \
160         }
161
162 void bmesh_bridge_loops_exec(BMesh *bm, BMOperator *op)
163 {
164         BMEdge **ee1 = NULL, **ee2 = NULL;
165         BMVert **vv1 = NULL, **vv2 = NULL;
166         BLI_array_declare(ee1);
167         BLI_array_declare(ee2);
168         BLI_array_declare(vv1);
169         BLI_array_declare(vv2);
170         BMOIter siter;
171         BMIter iter;
172         BMEdge *e, *nexte;
173         int c = 0, cl1 = 0, cl2 = 0;
174
175         BMO_slot_buffer_flag(bm, op, "edges", EDGE_MARK, BM_EDGE);
176
177         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
178                 if (!BMO_elem_flag_test(bm, e, EDGE_DONE)) {
179                         BMVert *v, *ov;
180                         /* BMEdge *e2, *e3, *oe = e; */ /* UNUSED */
181                         BMEdge *e2, *e3;
182                         
183                         if (c > 2) {
184                                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, "Select only two edge loops");
185                                 goto cleanup;
186                         }
187                         
188                         e2 = e;
189                         v = e->v1;
190                         do {
191                                 v = BM_edge_other_vert(e2, v);
192                                 nexte = NULL;
193                                 BM_ITER(e3, &iter, bm, BM_EDGES_OF_VERT, v) {
194                                         if (e3 != e2 && BMO_elem_flag_test(bm, e3, EDGE_MARK)) {
195                                                 if (nexte == NULL) {
196                                                         nexte = e3;
197                                                 }
198                                                 else {
199                                                         /* edges do not form a loop: there is a disk
200                                                          * with more than two marked edges. */
201                                                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
202                                                                         "Selection must only contain edges from two edge loops");
203                                                         goto cleanup;
204                                                 }
205                                         }
206                                 }
207                                 
208                                 if (nexte)
209                                         e2 = nexte;
210                         } while (nexte && e2 != e);
211                         
212                         if (!e2)
213                                 e2 = e;
214
215                         e = e2;
216                         ov = v;
217                         do {
218                                 if (c == 0) {
219                                         BLI_array_append(ee1, e2);
220                                         BLI_array_append(vv1, v);
221                                 }
222                                 else {
223                                         BLI_array_append(ee2, e2);
224                                         BLI_array_append(vv2, v);
225                                 }
226                                 
227                                 BMO_elem_flag_set(bm, e2, EDGE_DONE);
228                                 
229                                 v = BM_edge_other_vert(e2, v);
230                                 BM_ITER(e3, &iter, bm, BM_EDGES_OF_VERT, v) {
231                                         if (e3 != e2 && BMO_elem_flag_test(bm, e3, EDGE_MARK) && !BMO_elem_flag_test(bm, e3, EDGE_DONE)) {
232                                                 break;
233                                         }
234                                 }
235                                 if (e3)
236                                         e2 = e3;
237                         } while (e3 && e2 != e);
238                         
239                         if (v && !e3) {
240                                 if (c == 0) {
241                                         if (BLI_array_count(vv1) && v == vv1[BLI_array_count(vv1) - 1]) {
242                                                 printf("%s: internal state waning *TODO DESCRIPTION!*\n", __func__);
243                                         }
244                                         BLI_array_append(vv1, v);
245                                 }
246                                 else {
247                                         BLI_array_append(vv2, v);
248                                 }
249                         }
250                         
251                         /* test for connected loops, and set cl1 or cl2 if so */
252                         if (v == ov) {
253                                 if (c == 0) {
254                                         cl1 = 1;
255                                 }
256                                 else {
257                                         cl2 = 1;
258                                 }
259                         }
260                         
261                         c++;
262                 }
263         }
264
265         if (ee1 && ee2) {
266                 int i, j;
267                 BMVert *v1, *v2, *v3, *v4;
268                 int starti = 0, dir1 = 1, wdir = 0, lenv1, lenv2;
269
270                 /* Simplify code below by avoiding the (!cl1 && cl2) case */
271                 if (!cl1 && cl2) {
272                         SWAP(int, cl1, cl2);
273                         ARRAY_SWAP(BMVert *, vv1, vv2);
274                         ARRAY_SWAP(BMEdge *, ee1, ee2);
275                 }
276
277                 lenv1 = lenv2 = BLI_array_count(vv1);
278
279                 /* Below code assumes vv1/vv2 each have at least two verts. should always be
280                  * a safe assumption, since ee1/ee2 are non-empty and an edge has two verts. */
281                 BLI_assert((lenv1 > 1) && (lenv2 > 1));
282
283                 /* BMESH_TODO: Would be nice to handle cases where the edge loops
284                  * have different edge counts by generating triangles & quads for
285                  * the bridge instead of quads only. */
286                 if (BLI_array_count(ee1) != BLI_array_count(ee2)) {
287                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
288                                         "Selected loops must have equal edge counts");
289                         goto cleanup;
290                 }
291
292                 j = 0;
293                 if (vv1[0] == vv1[lenv1 - 1]) {
294                         lenv1--;
295                 }
296                 if (vv2[0] == vv2[lenv2 - 1]) {
297                         lenv2--;
298                 }
299
300                 /* Find starting point and winding direction for two unclosed loops */
301                 if (!cl1 && !cl2) {
302                         /* First point of loop 1 */
303                         v1 = get_outer_vert(bm, ee1[0]);
304                         /* Last point of loop 1 */
305                         v2 = get_outer_vert(bm, ee1[clamp_index(-1, BLI_array_count(ee1))]);
306                         /* First point of loop 2 */
307                         v3 = get_outer_vert(bm, ee2[0]);
308                         /* Last point of loop 2 */
309                         v4 = get_outer_vert(bm, ee2[clamp_index(-1, BLI_array_count(ee2))]);
310
311                         /* If v1 is a better match for v4 than v3, AND v2 is a better match
312                          * for v3 than v4, the loops are in opposite directions, so reverse
313                          * the order of reads from vv1. We can avoid sqrt for comparison */
314                         if (len_squared_v3v3(v1->co, v3->co) > len_squared_v3v3(v1->co, v4->co) &&
315                             len_squared_v3v3(v2->co, v4->co) > len_squared_v3v3(v2->co, v3->co))
316                         {
317                                 dir1 = -1;
318                                 starti = clamp_index(-1, lenv1);
319                         }
320                 }
321
322                 /* Find the shortest distance from a vert in vv1 to vv2[0]. Use that
323                  * vertex in vv1 as a starting point in the first loop, while starting
324                  * from vv2[0] in the second loop. This is a simplistic attempt to get
325                  * a better edge-to-edge match between the two loops. */
326                 if (cl1) {
327                         int previ, nexti;
328                         float min = 1e32;
329
330                         /* BMESH_TODO: Would be nice to do a more thorough analysis of all
331                          * the vertices in both loops to find a more accurate match for the
332                          * starting point and winding direction of the bridge generation. */
333                         
334                         for (i = 0; i < BLI_array_count(vv1); i++) {
335                                 if (len_v3v3(vv1[i]->co, vv2[0]->co) < min) {
336                                         min = len_v3v3(vv1[i]->co, vv2[0]->co);
337                                         starti = i;
338                                 }
339                         }
340
341                         /* Reverse iteration order for the first loop if the distance of
342                          * the (starti - 1) vert from vv1 is a better match for vv2[1] than
343                          * the (starti + 1) vert.
344                          *
345                          * This is not always going to be right, but it will work better in
346                          * the average case.
347                          */
348                         previ = clamp_index(starti - 1, lenv1);
349                         nexti = clamp_index(starti + 1, lenv1);
350
351                         /* avoid sqrt for comparison */
352                         if (len_squared_v3v3(vv1[nexti]->co, vv2[1]->co) > len_squared_v3v3(vv1[previ]->co, vv2[1]->co)) {
353                                 /* reverse direction for reading vv1 (1 is forward, -1 is backward) */
354                                 dir1 = -1;
355                         }
356                 }
357
358                 /* Vert rough attempt to determine proper winding for the bridge quads:
359                  * just uses the first loop it finds for any of the edges of ee2 or ee1 */
360                 if (wdir == 0) {
361                         for (i = 0; i < BLI_array_count(ee2); i++) {
362                                 if (ee2[i]->l) {
363                                         wdir = (ee2[i]->l->v == vv2[i]) ? (-1) : (1);
364                                         break;
365                                 }
366                         }
367                 }
368                 if (wdir == 0) {
369                         for (i = 0; i < BLI_array_count(ee1); i++) {
370                                 j = clamp_index((i * dir1) + starti, BLI_array_count(ee1));
371                                 if (ee1[j]->l && ee2[j]->l) {
372                                         wdir = (ee2[j]->l->v == vv2[j]) ? (1) : (-1);
373                                         break;
374                                 }
375                         }
376                 }
377                 
378                 /* Generate the bridge quads */
379                 for (i = 0; i < BLI_array_count(ee1) && i < BLI_array_count(ee2); i++) {
380                         BMFace *f;
381                         int i1, i1next, i2, i2next;
382
383                         i1 = clamp_index(i * dir1 + starti, lenv1);
384                         i1next = clamp_index((i + 1) * dir1 + starti, lenv1);
385                         i2 = i;
386                         i2next = clamp_index(i + 1, lenv2);
387
388                         if (vv1[i1] ==  vv1[i1next]) {
389                                 continue;
390                         }
391
392                         if (wdir < 0) {
393                                 SWAP(int, i1, i1next);
394                                 SWAP(int, i2, i2next);
395                         }
396
397                         f = BM_face_create_quad_tri(bm,
398                                                     vv1[i1],
399                                                     vv2[i2],
400                                                     vv2[i2next],
401                                                     vv1[i1next],
402                                                     NULL, TRUE);
403                         if (!f || f->len != 4) {
404                                 fprintf(stderr, "%s: in bridge! (bmesh internal error)\n", __func__);
405                         }
406                 }
407         }
408
409 cleanup:
410         BLI_array_free(ee1);
411         BLI_array_free(ee2);
412         BLI_array_free(vv1);
413         BLI_array_free(vv2);
414 }