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