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