style cleanup
[blender.git] / source / blender / bmesh / operators / bmo_fill_grid.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): Campbell Barton.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_fill_grid.c
24  *  \ingroup bmesh
25  *
26  * Fill 2 isolated, open edge loops with a grid of quads.
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_listbase.h"
32 #include "BLI_math.h"
33
34 #include "BKE_customdata.h"
35
36 #include "bmesh.h"
37
38 #include "intern/bmesh_operators_private.h" /* own include */
39
40 #include "BLI_strict_flags.h"
41
42 #define EDGE_MARK       4
43 #define FACE_OUT        16
44
45 #define BARYCENTRIC_INTERP
46
47 #ifdef BARYCENTRIC_INTERP
48 /**
49  * 2 edge vectors to normal.
50  */
51 static void quad_edges_to_normal(
52         float no[3],
53         const float co_a1[3], const float co_a2[3],
54         const float co_b1[3], const float co_b2[3])
55 {
56         float diff_a[3];
57         float diff_b[3];
58
59         sub_v3_v3v3(diff_a, co_a2, co_a1);
60         sub_v3_v3v3(diff_b, co_b2, co_b1);
61         normalize_v3(diff_a);
62         normalize_v3(diff_b);
63         add_v3_v3v3(no, diff_a, diff_b);
64         normalize_v3(no);
65 }
66
67 static void quad_verts_to_barycentric_tri(
68         float tri[3][3],
69         const float co_a[3],
70         const float co_b[3],
71
72         const float co_a_next[3],
73         const float co_b_next[3],
74
75         const float co_a_prev[3],
76         const float co_b_prev[3],
77         const bool is_flip
78         )
79 {
80         float no[3];
81
82         copy_v3_v3(tri[0], co_a);
83         copy_v3_v3(tri[1], co_b);
84
85         quad_edges_to_normal(no,
86                              co_a, co_a_next,
87                              co_b, co_b_next);
88
89         if (co_a_prev) {
90                 float no_t[3];
91                 quad_edges_to_normal(no_t,
92                                      co_a_prev, co_a,
93                                      co_b_prev, co_b);
94                 add_v3_v3(no, no_t);
95                 normalize_v3(no);
96         }
97
98         if (is_flip) negate_v3(no);
99         mul_v3_fl(no, len_v3v3(tri[0], tri[1]));
100
101         mid_v3_v3v3(tri[2], tri[0], tri[1]);
102         add_v3_v3(tri[2], no);
103 }
104
105 #endif
106
107
108 /* -------------------------------------------------------------------- */
109 /* Handle Loop Pairs */
110
111 /** \name Loop Pairs
112  * \{ */
113
114 /**
115  * Assign a loop pair from 2 verts (which _must_ share an edge)
116  */
117 static void bm_loop_pair_from_verts(BMVert *v_a, BMVert *v_b,
118                                     BMLoop *l_pair[2])
119 {
120         BMEdge *e = BM_edge_exists(v_a, v_b);
121         if (e->l) {
122                 if (e->l->v == v_a) {
123                         l_pair[0] = e->l;
124                         l_pair[1] = e->l->next;
125                 }
126                 else {
127                         l_pair[0] = e->l->next;
128                         l_pair[1] = e->l;
129                 }
130         }
131         else {
132                 l_pair[0] = NULL;
133                 l_pair[1] = NULL;
134         }
135 }
136
137 /**
138  * Copy loop pair from one side to the other if either is missing,
139  * this simplifies interpolation code so we only need to check if x/y are missing,
140  * rather then checking each loop.
141  */
142 static void bm_loop_pair_test_copy(BMLoop *l_pair_a[2], BMLoop *l_pair_b[2])
143 {
144         /* if the first one is set, we know the second is too */
145         if (l_pair_a[0] && l_pair_b[0] == NULL) {
146                 l_pair_b[0] = l_pair_a[1];
147                 l_pair_b[1] = l_pair_a[0];
148         }
149         else if (l_pair_b[0] && l_pair_a[0] == NULL) {
150                 l_pair_a[0] = l_pair_b[1];
151                 l_pair_a[1] = l_pair_b[0];
152         }
153 }
154
155 /**
156  * Interpolate from boundary loops.
157  *
158  * \note These weights will be calculated multiple times per vertex.
159  */
160 static void bm_loop_interp_from_grid_boundary_4(BMesh *bm, BMLoop *l, BMLoop *l_bound[4], const float w[4])
161 {
162         void *l_cdata[4] = {
163             l_bound[0]->head.data,
164             l_bound[1]->head.data,
165             l_bound[2]->head.data,
166             l_bound[3]->head.data};
167
168         CustomData_bmesh_interp(&bm->ldata, l_cdata, w, NULL, 4, l->head.data);
169 }
170
171 static void bm_loop_interp_from_grid_boundary_2(BMesh *bm, BMLoop *l, BMLoop *l_bound[2], const float t)
172 {
173
174         void *l_cdata[2] = {
175             l_bound[0]->head.data,
176             l_bound[1]->head.data};
177
178         const float w[2] = {1.0f - t, t};
179
180         CustomData_bmesh_interp(&bm->ldata, l_cdata, w, NULL, 2, l->head.data);
181 }
182
183 /** \} */
184
185
186 /**
187  * Avoids calling #barycentric_weights_v2_quad often by caching weights into an array.
188  */
189 static void barycentric_weights_v2_grid_cache(const unsigned int xtot, const unsigned int ytot,
190                                               float (*weight_table)[4])
191 {
192         float x_step = 1.0f / (float)(xtot - 1);
193         float y_step = 1.0f / (float)(ytot - 1);
194         unsigned int i = 0;
195         float xy_fl[2];
196
197         unsigned int x, y;
198         for (y = 0; y < ytot; y++) {
199                 xy_fl[1] = y_step * (float)y;
200                 for (x = 0; x < xtot; x++) {
201                         xy_fl[0] = x_step * (float)x;
202                         {
203                                 const float cos[4][2] = {
204                                     {xy_fl[0], 0.0f},
205                                     {0.0f, xy_fl[1]},
206                                     {xy_fl[0], 1.0f},
207                                     {1.0f, xy_fl[1]}};
208                                 barycentric_weights_v2_quad(UNPACK4(cos), xy_fl, weight_table[i++]);
209                         }
210                 }
211         }
212 }
213
214
215 /**
216  * This may be useful outside the bmesh operator.
217  *
218  * \param v_grid  2d array of verts, all boundary verts must be set, we fill in the middle.
219  */
220 static void bm_grid_fill_array(BMesh *bm, BMVert **v_grid, const unsigned int xtot, unsigned const int ytot,
221                                const short mat_nr, const bool use_smooth,
222                                const bool use_flip, const bool use_interp_simple)
223 {
224         const bool use_vert_interp = CustomData_has_interp(&bm->vdata);
225         const bool use_loop_interp = CustomData_has_interp(&bm->ldata);
226         unsigned int x, y;
227
228         /* for use_loop_interp */
229         BMLoop *((*larr_x_a)[2]), *((*larr_x_b)[2]), *((*larr_y_a)[2]), *((*larr_y_b)[2]);
230
231         float (*weight_table)[4];
232
233 #define XY(_x, _y)  ((_x) + ((_y) * (xtot)))
234
235 #ifdef BARYCENTRIC_INTERP
236         float tri_a[3][3];
237         float tri_b[3][3];
238         float tri_t[3][3];  /* temp */
239
240         quad_verts_to_barycentric_tri(
241                 tri_a,
242                 v_grid[XY(0,        0)]->co,
243                 v_grid[XY(xtot - 1, 0)]->co,
244                 v_grid[XY(0,        1)]->co,
245                 v_grid[XY(xtot - 1, 1)]->co,
246                 NULL, NULL,
247                 false);
248
249         quad_verts_to_barycentric_tri(
250                 tri_b,
251                 v_grid[XY(0,        (ytot - 1))]->co,
252                 v_grid[XY(xtot - 1, (ytot - 1))]->co,
253                 v_grid[XY(0,        (ytot - 2))]->co,
254                 v_grid[XY(xtot - 1, (ytot - 2))]->co,
255                 NULL, NULL,
256                 true);
257 #endif
258
259         if (use_interp_simple || use_vert_interp || use_loop_interp) {
260                 weight_table = MEM_mallocN(sizeof(*weight_table) * (size_t)(xtot * ytot), __func__);
261                 barycentric_weights_v2_grid_cache(xtot, ytot, weight_table);
262         }
263         else {
264                 weight_table = NULL;
265         }
266
267
268         /* Store loops */
269         if (use_loop_interp) {
270                 /* x2 because each edge connects 2 loops */
271                 larr_x_a = MEM_mallocN(sizeof(*larr_x_a) * (xtot - 1), __func__);
272                 larr_x_b = MEM_mallocN(sizeof(*larr_x_b) * (xtot - 1), __func__);
273
274                 larr_y_a = MEM_mallocN(sizeof(*larr_y_a) * (ytot - 1), __func__);
275                 larr_y_b = MEM_mallocN(sizeof(*larr_y_b) * (ytot - 1), __func__);
276
277                 /* fill in the loops */
278                 for (x = 0; x < xtot - 1; x++) {
279                         bm_loop_pair_from_verts(v_grid[XY(x,        0)], v_grid[XY(x + 1,        0)], larr_x_a[x]);
280                         bm_loop_pair_from_verts(v_grid[XY(x, ytot - 1)], v_grid[XY(x + 1, ytot - 1)], larr_x_b[x]);
281                         bm_loop_pair_test_copy(larr_x_a[x], larr_x_b[x]);
282                 }
283
284                 for (y = 0; y < ytot - 1; y++) {
285                         bm_loop_pair_from_verts(v_grid[XY(0,        y)], v_grid[XY(0,        y + 1)], larr_y_a[y]);
286                         bm_loop_pair_from_verts(v_grid[XY(xtot - 1, y)], v_grid[XY(xtot - 1, y + 1)], larr_y_b[y]);
287                         bm_loop_pair_test_copy(larr_y_a[y], larr_y_b[y]);
288                 }
289         }
290
291
292         /* Build Verts */
293         for (y = 1; y < ytot - 1; y++) {
294 #ifdef BARYCENTRIC_INTERP
295                 quad_verts_to_barycentric_tri(
296                         tri_t,
297                         v_grid[XY(0,        y + 0)]->co,
298                         v_grid[XY(xtot - 1, y + 0)]->co,
299                         v_grid[XY(0,        y + 1)]->co,
300                         v_grid[XY(xtot - 1, y + 1)]->co,
301                         v_grid[XY(0,        y - 1)]->co,
302                         v_grid[XY(xtot - 1, y - 1)]->co,
303                         false);
304 #endif
305                 for (x = 1; x < xtot - 1; x++) {
306                         float co[3];
307                         BMVert *v;
308                         /* we may want to allow sparse filled arrays, but for now, ensure its empty */
309                         BLI_assert(v_grid[(y * xtot) + x] == NULL);
310
311                         /* place the vertex */
312 #ifdef BARYCENTRIC_INTERP
313                         if (use_interp_simple == false) {
314                                 float co_a[3], co_b[3];
315
316                                 barycentric_transform(
317                                             co_a,
318                                             v_grid[x]->co,
319                                             tri_t[0], tri_t[1], tri_t[2],
320                                             tri_a[0], tri_a[1], tri_a[2]);
321                                 barycentric_transform(
322                                             co_b,
323                                             v_grid[(xtot * ytot) + (x - xtot)]->co,
324                                             tri_t[0], tri_t[1], tri_t[2],
325                                             tri_b[0], tri_b[1], tri_b[2]);
326
327                                 interp_v3_v3v3(co, co_a, co_b, (float)y / ((float)ytot - 1));
328                         }
329                         else
330 #endif
331                         {
332                                 const float *w = weight_table[XY(x, y)];
333
334                                 zero_v3(co);
335                                 madd_v3_v3fl(co, v_grid[XY(x,        0)]->co, w[0]);
336                                 madd_v3_v3fl(co, v_grid[XY(0,        y)]->co, w[1]);
337                                 madd_v3_v3fl(co, v_grid[XY(x, ytot - 1)]->co, w[2]);
338                                 madd_v3_v3fl(co, v_grid[XY(xtot - 1, y)]->co, w[3]);
339                         }
340
341                         v = BM_vert_create(bm, co, NULL, BM_CREATE_NOP);
342                         v_grid[(y * xtot) + x] = v;
343
344                         /* interpolate only along one axis, this could be changed
345                          * but from user pov gives predictable results since these are selected loop */
346                         if (use_vert_interp) {
347                                 const float *w = weight_table[XY(x, y)];
348
349                                 void *v_cdata[4] = {
350                                     v_grid[XY(x,        0)]->head.data,
351                                     v_grid[XY(0,        y)]->head.data,
352                                     v_grid[XY(x, ytot - 1)]->head.data,
353                                     v_grid[XY(xtot - 1, y)]->head.data,
354                                 };
355
356                                 CustomData_bmesh_interp(&bm->vdata, v_cdata, w, NULL, 4, v->head.data);
357                         }
358
359                 }
360         }
361
362         /* Build Faces */
363         for (x = 0; x < xtot - 1; x++) {
364                 for (y = 0; y < ytot - 1; y++) {
365                         BMFace *f;
366
367                         if (use_flip) {
368                                 f = BM_face_create_quad_tri(
369                                         bm,
370                                         v_grid[XY(x,     y + 0)],  /* BL */
371                                         v_grid[XY(x,     y + 1)],  /* TL */
372                                         v_grid[XY(x + 1, y + 1)],  /* TR */
373                                         v_grid[XY(x + 1, y + 0)],  /* BR */
374                                         NULL,
375                                         BM_CREATE_NOP);
376                         }
377                         else {
378                                 f = BM_face_create_quad_tri(
379                                         bm,
380                                         v_grid[XY(x + 1, y + 0)],  /* BR */
381                                         v_grid[XY(x + 1, y + 1)],  /* TR */
382                                         v_grid[XY(x,     y + 1)],  /* TL */
383                                         v_grid[XY(x,     y + 0)],  /* BL */
384                                         NULL,
385                                         BM_CREATE_NOP);
386                         }
387
388
389                         if (use_loop_interp && (larr_x_a[x][0] || larr_y_a[y][0])) {
390                                 /* bottom/left/top/right */
391                                 BMLoop *l_quad[4];
392                                 BMLoop *l_bound[4];
393                                 BMLoop *l_tmp;
394                                 unsigned int x_side, y_side, i;
395                                 char interp_from;
396
397
398                                 if (larr_x_a[x][0] && larr_y_a[y][0]) {
399                                         interp_from = 'B';  /* B == both */
400                                         l_tmp = larr_x_a[x][0];
401                                 }
402                                 else if (larr_x_a[x][0]) {
403                                         interp_from = 'X';
404                                         l_tmp = larr_x_a[x][0];
405                                 }
406                                 else {
407                                         interp_from = 'Y';
408                                         l_tmp = larr_y_a[y][0];
409                                 }
410
411                                 BM_elem_attrs_copy(bm, bm, l_tmp->f, f);
412
413
414                                 BM_face_as_array_loop_quad(f, l_quad);
415
416                                 l_tmp = BM_FACE_FIRST_LOOP(f);
417
418                                 if (use_flip) {
419                                         l_quad[0] = l_tmp; l_tmp = l_tmp->next;
420                                         l_quad[1] = l_tmp; l_tmp = l_tmp->next;
421                                         l_quad[3] = l_tmp; l_tmp = l_tmp->next;
422                                         l_quad[2] = l_tmp;
423                                 }
424                                 else {
425                                         l_quad[2] = l_tmp; l_tmp = l_tmp->next;
426                                         l_quad[3] = l_tmp; l_tmp = l_tmp->next;
427                                         l_quad[1] = l_tmp; l_tmp = l_tmp->next;
428                                         l_quad[0] = l_tmp;
429                                 }
430
431                                 i = 0;
432
433                                 for (x_side = 0; x_side < 2; x_side++) {
434                                         for (y_side = 0; y_side < 2; y_side++) {
435                                                 if (interp_from == 'B') {
436                                                         const float *w = weight_table[XY(x + x_side, y + y_side)];
437                                                         l_bound[0] = larr_x_a[x][x_side];  /* B */
438                                                         l_bound[1] = larr_y_a[y][y_side];  /* L */
439                                                         l_bound[2] = larr_x_b[x][x_side];  /* T */
440                                                         l_bound[3] = larr_y_b[y][y_side];  /* R */
441
442                                                         bm_loop_interp_from_grid_boundary_4(bm, l_quad[i++], l_bound, w);
443                                                 }
444                                                 else if (interp_from == 'X') {
445                                                         const float t = (float)(y + y_side) / (float)(ytot - 1);
446                                                         l_bound[0] = larr_x_a[x][x_side];  /* B */
447                                                         l_bound[1] = larr_x_b[x][x_side];  /* T */
448
449                                                         bm_loop_interp_from_grid_boundary_2(bm, l_quad[i++], l_bound, t);
450                                                 }
451                                                 else if (interp_from == 'Y') {
452                                                         const float t = (float)(x + x_side) / (float)(xtot - 1);
453                                                         l_bound[0] = larr_y_a[y][y_side];  /* L */
454                                                         l_bound[1] = larr_y_b[y][y_side];  /* R */
455
456                                                         bm_loop_interp_from_grid_boundary_2(bm, l_quad[i++], l_bound, t);
457                                                 }
458                                                 else {
459                                                         BLI_assert(0);
460                                                 }
461                                         }
462                                 }
463                         }
464                         /* end interp */
465
466
467                         BMO_elem_flag_enable(bm, f, FACE_OUT);
468                         f->mat_nr = mat_nr;
469                         if (use_smooth) {
470                                 BM_elem_flag_enable(f, BM_ELEM_SMOOTH);
471                         }
472                 }
473         }
474
475         if (use_loop_interp) {
476                 MEM_freeN(larr_x_a);
477                 MEM_freeN(larr_y_a);
478                 MEM_freeN(larr_x_b);
479                 MEM_freeN(larr_y_b);
480         }
481
482         if (weight_table) {
483                 MEM_freeN(weight_table);
484         }
485
486 #undef XY
487 }
488
489 static void bm_grid_fill(BMesh *bm,
490                          struct BMEdgeLoopStore *estore_a,      struct BMEdgeLoopStore *estore_b,
491                          struct BMEdgeLoopStore *estore_rail_a, struct BMEdgeLoopStore *estore_rail_b,
492                          const short mat_nr, const bool use_smooth, const bool use_interp_simple)
493 {
494 #define USE_FLIP_DETECT
495
496         const unsigned int xtot = (unsigned int)BM_edgeloop_length_get(estore_a);
497         const unsigned int ytot = (unsigned int)BM_edgeloop_length_get(estore_rail_a);
498         //BMVert *v;
499         unsigned int i;
500 #ifdef DEBUG
501         unsigned int x, y;
502 #endif
503         LinkData *el;
504         bool use_flip = false;
505
506         ListBase *lb_a = BM_edgeloop_verts_get(estore_a);
507         ListBase *lb_b = BM_edgeloop_verts_get(estore_b);
508
509         ListBase *lb_rail_a = BM_edgeloop_verts_get(estore_rail_a);
510         ListBase *lb_rail_b = BM_edgeloop_verts_get(estore_rail_b);
511
512         BMVert **v_grid = MEM_callocN(sizeof(BMVert *) * (size_t)(xtot * ytot), __func__);
513         /**
514          * <pre>
515          *           estore_b
516          *          +------------------+
517          *       ^  |                  |
518          *   end |  |                  |
519          *       |  |                  |
520          *       |  |estore_rail_a     |estore_rail_b
521          *       |  |                  |
522          * start |  |                  |
523          *          |estore_a          |
524          *          +------------------+
525          *                --->
526          *             start -> end
527          * </pre>
528          */
529
530         BLI_assert(((LinkData *)lb_a->first)->data == ((LinkData *)lb_rail_a->first)->data);  /* BL */
531         BLI_assert(((LinkData *)lb_b->first)->data == ((LinkData *)lb_rail_a->last)->data);   /* TL */
532         BLI_assert(((LinkData *)lb_b->last)->data  == ((LinkData *)lb_rail_b->last)->data);   /* TR */
533         BLI_assert(((LinkData *)lb_a->last)->data  == ((LinkData *)lb_rail_b->first)->data);  /* BR */
534
535         for (el = lb_a->first,      i = 0; el; el = el->next, i++) { v_grid[i]                          = el->data; }
536         for (el = lb_b->first,      i = 0; el; el = el->next, i++) { v_grid[(ytot * xtot) + (i - xtot)] = el->data; }
537         for (el = lb_rail_a->first, i = 0; el; el = el->next, i++) { v_grid[xtot * i]                   = el->data; }
538         for (el = lb_rail_b->first, i = 0; el; el = el->next, i++) { v_grid[(xtot * i) + (xtot - 1)]    = el->data; }
539 #ifdef DEBUG
540         for (x = 1; x < xtot - 1; x++) { for (y = 1; y < ytot - 1; y++) { BLI_assert(v_grid[(y * xtot) + x] == NULL); }}
541 #endif
542
543 #ifdef USE_FLIP_DETECT
544         {
545                 ListBase *lb_iter[4] = {lb_a, lb_b, lb_rail_a, lb_rail_b};
546                 const int lb_iter_dir[4] = {-1, 1, 1, -1};
547                 int winding_votes = 0;
548
549                 for (i = 0; i < 4; i++) {
550                         LinkData *el_next;
551                         for (el = lb_iter[i]->first; el && (el_next = el->next); el = el->next) {
552                                 BMEdge *e = BM_edge_exists(el->data, el_next->data);
553                                 if (BM_edge_is_boundary(e)) {
554                                         winding_votes += (e->l->v == el->data) ? lb_iter_dir[i] : -lb_iter_dir[i];
555                                 }
556                         }
557                 }
558                 use_flip = (winding_votes < 0);
559         }
560 #endif
561
562
563         bm_grid_fill_array(bm, v_grid, xtot, ytot, mat_nr, use_smooth, use_flip, use_interp_simple);
564         MEM_freeN(v_grid);
565
566 #undef USE_FLIP_DETECT
567 }
568
569 static bool bm_edge_test_cb(BMEdge *e, void *bm_v)
570 {
571         return BMO_elem_flag_test_bool((BMesh *)bm_v, e, EDGE_MARK);
572 }
573
574 static bool bm_edge_test_rail_cb(BMEdge *e, void *UNUSED(bm_v))
575 {
576         /* normally operators dont check for hidden state
577          * but alternative would be to pass slot of rail edges */
578         if (BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
579                 return false;
580         }
581         return BM_edge_is_wire(e) || BM_edge_is_boundary(e);
582 }
583
584 void bmo_grid_fill_exec(BMesh *bm, BMOperator *op)
585 {
586         ListBase eloops = {NULL, NULL};
587         ListBase eloops_rail = {NULL, NULL};
588         struct BMEdgeLoopStore *estore_a, *estore_b;
589         struct BMEdgeLoopStore *estore_rail_a, *estore_rail_b;
590         BMVert *v_a_first, *v_a_last;
591         BMVert *v_b_first, *v_b_last;
592         const short mat_nr = (short)BMO_slot_int_get(op->slots_in,  "mat_nr");
593         const bool use_smooth = BMO_slot_bool_get(op->slots_in, "use_smooth");
594         const bool use_interp_simple = BMO_slot_bool_get(op->slots_in, "use_interp_simple");
595
596         int count;
597         bool change = false;
598         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
599
600         count = BM_mesh_edgeloops_find(bm, &eloops, bm_edge_test_cb, (void *)bm);
601
602         if (count != 2) {
603                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
604                                 "Select two edge loops");
605                 goto cleanup;
606         }
607
608         estore_a = eloops.first;
609         estore_b = eloops.last;
610
611         v_a_first = ((LinkData *)BM_edgeloop_verts_get(estore_a)->first)->data;
612         v_a_last  = ((LinkData *)BM_edgeloop_verts_get(estore_a)->last)->data;
613         v_b_first = ((LinkData *)BM_edgeloop_verts_get(estore_b)->first)->data;
614         v_b_last  = ((LinkData *)BM_edgeloop_verts_get(estore_b)->last)->data;
615
616         if (BM_edgeloop_length_get(estore_a) != BM_edgeloop_length_get(estore_b)) {
617                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
618                                 "Edge loop vertex count mismatch");
619                 goto cleanup;
620         }
621
622         if (BM_edgeloop_is_closed(estore_a) || BM_edgeloop_is_closed(estore_b)) {
623                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
624                                 "Closed loops unsupported");
625                 goto cleanup;
626         }
627
628         /* ok. all error checking done, now we can find the rail edges */
629
630         if (BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, bm, v_a_first, v_b_first) == false) {
631                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
632                                 "Loops are not connected by wire/boundary edges");
633                 goto cleanup;
634         }
635
636         BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, (void *)bm, v_a_first, v_b_last);
637
638         /* Check flipping by comparing path length */
639         estore_rail_a = eloops_rail.first;
640         estore_rail_b = eloops_rail.last;
641
642         BLI_assert(BM_edgeloop_length_get(estore_rail_a) != BM_edgeloop_length_get(estore_rail_b));
643
644         if (BM_edgeloop_length_get(estore_rail_a) < BM_edgeloop_length_get(estore_rail_b)) {
645                 BLI_remlink(&eloops_rail, estore_rail_b);
646                 BM_edgeloop_free(estore_rail_b);
647                 estore_rail_b = NULL;
648
649                 BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, (void *)bm,
650                                             v_a_last,
651                                             v_b_last);
652                 estore_rail_b = eloops_rail.last;
653         }
654         else {  /* a > b */
655                 BLI_remlink(&eloops_rail, estore_rail_a);
656                 BM_edgeloop_free(estore_rail_a);
657                 estore_rail_a = estore_rail_b;
658
659                 /* reverse so these so both are sorted the same way */
660                 BM_edgeloop_flip(bm, estore_b);
661                 SWAP(BMVert *, v_b_first, v_b_last);
662
663                 BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, (void *)bm,
664                                             v_a_last,
665                                             v_b_last);
666                 estore_rail_b = eloops_rail.last;
667         }
668
669         BLI_assert(estore_a != estore_b);
670         BLI_assert(v_a_last != v_b_last);
671
672         if (BM_edgeloop_length_get(estore_rail_a) != BM_edgeloop_length_get(estore_rail_b)) {
673                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
674                                 "Connecting edges vertex mismatch");
675                 goto cleanup;
676         }
677
678         if (BM_edgeloop_overlap_check(estore_rail_a, estore_rail_b)) {
679                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
680                                 "Connecting edge loops overlap");
681                 goto cleanup;
682         }
683
684         /* finally we have all edge loops needed */
685         bm_grid_fill(bm, estore_a, estore_b, estore_rail_a, estore_rail_b,
686                      mat_nr, use_smooth, use_interp_simple);
687
688         change = true;
689
690
691 cleanup:
692         BM_mesh_edgeloops_free(&eloops);
693         BM_mesh_edgeloops_free(&eloops_rail);
694
695         if (change) {
696                 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
697         }
698 }