Merging r58475 through r58700 from trunk into soc-2013-depsgraph_mt
[blender.git] / source / blender / bmesh / operators / bmo_subdivide_edgering.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_subdivide_edgering.c
24  *  \ingroup bmesh
25  *
26  * This operator is a special edge-ring subdivision tool
27  * which gives special options for interpolation.
28  *
29  * \note Tagging and flags
30  * Tagging here is quite prone to errors if not done carefully.
31  *
32  * - With the exception of EDGE_RIM & EDGE_RIM,
33  *   all flags need to be cleared on function exit.
34  * - verts use BM_ELEM_TAG, these need to be cleared before functions exit.
35  *
36  * \note Order of execution with 2+ rings is undefined,
37  * so tage care
38  */
39
40 #include "MEM_guardedalloc.h"
41
42 #include "BLI_utildefines.h"
43 #include "BLI_alloca.h"
44 #include "BLI_math.h"
45 #include "BLI_listbase.h"
46
47 #include "BKE_curve.h"
48
49 #include "bmesh.h"
50 #include "tools/bmesh_edgesplit.h"
51
52 #include "intern/bmesh_operators_private.h" /* own include */
53
54 #define VERT_SHARED             (1 << 0)
55
56 #define EDGE_RING               (1 << 0)
57 #define EDGE_RIM                (1 << 1)
58 #define EDGE_IN_STACK   (1 << 2)
59
60 #define FACE_OUT                (1 << 0)
61 #define FACE_SHARED             (1 << 1)
62 #define FACE_IN_STACK   (1 << 2)
63
64
65 /* -------------------------------------------------------------------- */
66 /* Specialized Utility Funcs */
67
68 #ifndef NDEBUG
69 static unsigned int bm_verts_tag_count(BMesh *bm)
70 {
71         int count = 0;
72         BMIter iter;
73         BMVert *v;
74         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
75                 if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
76                         count++;
77                 }
78         }
79         return count;
80 }
81 #endif
82
83 static float bezier_handle_calc_length_v3(const float co_a[3], const float no_a[3],
84                                           const float co_b[3], const float no_b[3])
85 {
86         const float dot = dot_v3v3(no_a, no_b);
87         /* gives closest approx at a circle with 2 parallel handles */
88         float fac = 1.333333f;
89         float len;
90         if (dot < 0.0f) {
91                 /* scale down to 0.666 if we point directly at each other rough but ok */
92                 /* TODO, current blend from dot may not be optimal but its also a detail */
93                 const float t = 1.0f + dot;
94                 fac = (fac * t) + (0.75f * (1.0f - t));
95         }
96
97 #if 0
98         len = len_v3v3(co_a, co_b);
99 #else
100         /* 2d length projected on plane of normals */
101         {
102                 float co_a_ofs[3];
103                 cross_v3_v3v3(co_a_ofs, no_a, no_b);
104                 if (len_squared_v3(co_a_ofs) > FLT_EPSILON) {
105                         add_v3_v3(co_a_ofs, co_a);
106                         closest_to_line_v3(co_a_ofs, co_b, co_a, co_a_ofs);
107                 }
108                 else {
109                         copy_v3_v3(co_a_ofs, co_a);
110                 }
111                 len = len_v3v3(co_a_ofs, co_b);
112         }
113 #endif
114
115         return (len * 0.5f) * fac;
116 }
117
118 static void bm_edgeloop_vert_tag(struct BMEdgeLoopStore *el_store, const bool tag)
119 {
120         LinkData *node = BM_edgeloop_verts_get(el_store)->first;
121         do {
122                 BM_elem_flag_set((BMVert *)node->data, BM_ELEM_TAG, tag);
123         } while ((node = node->next));
124 }
125
126 static void bmo_edgeloop_vert_tag(BMesh *bm, struct BMEdgeLoopStore *el_store, const short oflag, const bool tag)
127 {
128         LinkData *node = BM_edgeloop_verts_get(el_store)->first;
129         do {
130                 BMO_elem_flag_set(bm, (BMVert *)node->data, oflag, tag);
131         } while ((node = node->next));
132 }
133
134 static bool bmo_face_is_vert_tag_all(BMesh *bm, BMFace *f, short oflag)
135 {
136         BMLoop *l_iter, *l_first;
137         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
138         do {
139                 if (!BMO_elem_flag_test(bm, l_iter->v, oflag)) {
140                         return false;
141                 }
142         } while ((l_iter = l_iter->next) != l_first);
143         return true;
144 }
145
146 static bool bm_vert_is_tag_edge_connect(BMesh *bm, BMVert *v)
147 {
148         BMIter eiter;
149         BMEdge *e;
150
151         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
152                 if (BMO_elem_flag_test(bm, e, EDGE_RING)) {
153                         BMVert *v_other = BM_edge_other_vert(e, v);
154                         if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
155                                 return true;
156                         }
157                 }
158         }
159         return false;
160 }
161
162 /* for now we need full overlap,
163  * supporting partial overlap could be done but gets complicated
164  * when trimming endpoints is not enough to ensure consistency.
165  */
166 static bool bm_edgeloop_check_overlap_all(
167         BMesh *bm,
168         struct BMEdgeLoopStore *el_store_a,
169         struct BMEdgeLoopStore *el_store_b)
170 {
171         bool has_overlap = true;
172         LinkData *node;
173
174         ListBase *lb_a = BM_edgeloop_verts_get(el_store_a);
175         ListBase *lb_b = BM_edgeloop_verts_get(el_store_b);
176
177         bm_edgeloop_vert_tag(el_store_a, false);
178         bm_edgeloop_vert_tag(el_store_b, true);
179
180         for (node = lb_a->first; node; node = node->next) {
181                 if (bm_vert_is_tag_edge_connect(bm, node->data) == false) {
182                         has_overlap = false;
183                         goto finally;
184                 }
185         }
186
187         bm_edgeloop_vert_tag(el_store_a, true);
188         bm_edgeloop_vert_tag(el_store_b, false);
189
190         for (node = lb_b->first; node; node = node->next) {
191                 if (bm_vert_is_tag_edge_connect(bm, node->data) == false) {
192                         has_overlap = false;
193                         goto finally;
194                 }
195         }
196
197 finally:
198         bm_edgeloop_vert_tag(el_store_a, false);
199         bm_edgeloop_vert_tag(el_store_b, false);
200         return has_overlap;
201
202 }
203
204 /* -------------------------------------------------------------------- */
205 /* Edge Loop Pairs */
206 /* key (ordered loop pointers) */
207 static GHash *bm_edgering_pair_calc(BMesh *bm, ListBase *eloops_rim)
208 {
209         /**
210          * Method for for finding pairs:
211          *
212          * - first create (vert -> eloop) mapping.
213          * - loop over all eloops.
214          *   - take first vertex of the eloop (any vertex will do)
215          *     - loop over all edges of the vertex.
216          *       - use the edge-verts and (vert -> eloop) map
217          *         to create a pair of eloop pointers, add these to a hash.
218          *
219          * \note, each loop pair will be found twice.
220          * could sort and optimize this but not really so important.
221          */
222
223         GHash *eloop_pair_gh = BLI_ghash_pair_new(__func__);
224         GHash *vert_eloop_gh = BLI_ghash_ptr_new(__func__);
225
226         struct BMEdgeLoopStore *el_store;
227
228         /* create vert -> eloop map */
229         for (el_store = eloops_rim->first; el_store; el_store = BM_EDGELOOP_NEXT(el_store)) {
230                 LinkData *node = BM_edgeloop_verts_get(el_store)->first;
231                 do {
232                         BLI_ghash_insert(vert_eloop_gh, node->data, el_store);
233                 } while ((node = node->next));
234         }
235
236
237         /* collect eloop pairs */
238         for (el_store = eloops_rim->first; el_store; el_store = BM_EDGELOOP_NEXT(el_store)) {
239                 BMIter eiter;
240                 BMEdge *e;
241
242                 BMVert *v = ((LinkData *)BM_edgeloop_verts_get(el_store)->first)->data;
243
244                 BM_ITER_ELEM (e, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
245                         if (BMO_elem_flag_test(bm, e, EDGE_RING)) {
246                                 struct BMEdgeLoopStore *el_store_other;
247                                 BMVert *v_other = BM_edge_other_vert(e, v);
248                                 GHashPair pair_test;
249
250                                 el_store_other = BLI_ghash_lookup(vert_eloop_gh, v_other);
251
252                                 /* in rare cases we cant find a match */
253                                 if (el_store_other) {
254                                         pair_test.first = el_store;
255                                         pair_test.second = el_store_other;
256
257                                         if (pair_test.first > pair_test.second)
258                                                 SWAP(const void *, pair_test.first, pair_test.second);
259
260                                         if (!BLI_ghash_haskey(eloop_pair_gh, &pair_test)) {
261                                                 GHashPair *pair = BLI_ghashutil_pairalloc(pair_test.first, pair_test.second);
262                                                 BLI_ghash_insert(eloop_pair_gh, pair, NULL);
263                                         }
264
265                                 }
266                         }
267                 }
268         }
269
270         BLI_ghash_free(vert_eloop_gh, NULL, NULL);
271
272         if (BLI_ghash_size(eloop_pair_gh) == 0) {
273                 BLI_ghash_free(eloop_pair_gh, NULL, NULL);
274                 eloop_pair_gh = NULL;
275         }
276
277         return eloop_pair_gh;
278 }
279
280
281 /* -------------------------------------------------------------------- */
282 /* Subdivide an edge 'n' times and return an open edgeloop */
283
284 static void bm_edge_subdiv_as_loop(BMesh *bm, ListBase *eloops, BMEdge *e, BMVert *v_a, const int cuts)
285 {
286         struct BMEdgeLoopStore *eloop;
287         BMVert **v_arr = BLI_array_alloca(v_arr, cuts + 2);
288         BMVert *v_b;
289         BLI_assert(BM_vert_in_edge(e, v_a));
290
291         v_b = BM_edge_other_vert(e, v_a);
292
293         BM_edge_split_n(bm, e, cuts, &v_arr[1]);
294         if (v_a == e->v1) {
295                 v_arr[0]        = v_a;
296                 v_arr[cuts + 1] = v_b;
297         }
298         else {
299                 v_arr[0]        = v_b;
300                 v_arr[cuts + 1] = v_a;
301         }
302
303         eloop = BM_edgeloop_from_verts(v_arr, cuts + 2, false);
304
305         if (v_a == e->v1) {
306                 BM_edgeloop_flip(bm, eloop);
307         }
308
309         BLI_addtail(eloops, eloop);
310 }
311
312
313 /* -------------------------------------------------------------------- */
314 /* LoopPair Cache (struct and util funcs) */
315
316
317 /**
318  * Use for finding spline handle direction from surrounding faces.
319  *
320  * Resulting normal will _always_ point towards 'FACE_SHARED'
321  *
322  * This function must be called after all loops have been created,
323  * but before any mesh modifications.
324  *
325  * \return true on success
326  */
327 static void bm_vert_calc_surface_tangent(BMesh *bm, BMVert *v, float r_no[3])
328 {
329         BMIter eiter;
330         BMEdge *e;
331
332         /* get outer normal, fallback to inner (if this vertex is on a boundary) */
333         bool found_outer = false, found_inner = false, found_outer_tag = false;
334
335         float no_outer[3] = {0.0f}, no_inner[3] = {0.0f};
336
337         /* first find rim edges, typically we will only add 2 normals */
338         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
339                 if (UNLIKELY(BM_edge_is_wire(e))) {
340                         /* pass - this may confuse things */
341                 }
342                 else if (BMO_elem_flag_test(bm, e, EDGE_RIM)) {
343                         BMIter liter;
344                         BMLoop *l;
345                         BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
346                                 /* use unmarked (surrounding) faces to create surface tangent */
347                                 float no[3];
348                                 // BM_face_normal_update(l->f);
349                                 BM_edge_calc_face_tangent(e, l, no);
350                                 if (BMO_elem_flag_test(bm, l->f, FACE_SHARED)) {
351                                         add_v3_v3(no_inner, no);
352                                         found_inner = true;
353                                 }
354                                 else {
355                                         add_v3_v3(no_outer, no);
356                                         found_outer = true;
357
358                                         /* other side is used too, blend midway */
359                                         if (BMO_elem_flag_test(bm, l->f, FACE_OUT)) {
360                                                 found_outer_tag = true;
361                                         }
362                                 }
363                         }
364                 }
365         }
366
367         /* detect if this vertex is in-between 2 loops (when blending multiple),
368          * if so - take both inner and outer into account */
369
370         if (found_inner && found_outer_tag) {
371                 /* blend between the 2 */
372                 negate_v3(no_outer);
373                 normalize_v3(no_outer);
374                 normalize_v3(no_inner);
375                 add_v3_v3v3(r_no, no_outer, no_inner);
376                 normalize_v3(r_no);
377         }
378         else if (found_outer) {
379                 negate_v3(no_outer);
380                 normalize_v3_v3(r_no, no_outer);
381         }
382         else {
383                 /* we always have inner geometry */
384                 BLI_assert(found_inner == true);
385                 normalize_v3_v3(r_no, no_inner);
386         }
387 }
388
389 /**
390  * Tag faces connected to an edge loop as FACE_SHARED
391  * if all vertices are VERT_SHARED.
392  */
393 static void bm_faces_share_tag_flush(BMesh *bm, BMEdge **e_arr, const unsigned int e_arr_len)
394 {
395         unsigned int i;
396
397         for (i = 0; i < e_arr_len; i++) {
398                 BMEdge *e = e_arr[i];
399                 BMLoop *l_iter, *l_first;
400
401                 l_iter = l_first = e->l;
402                 do {
403                         if (!BMO_elem_flag_test(bm, l_iter->f, FACE_SHARED)) {
404                                 if (bmo_face_is_vert_tag_all(bm, l_iter->f, VERT_SHARED)) {
405                                         BMO_elem_flag_enable(bm, l_iter->f, FACE_SHARED);
406                                 }
407                         }
408                 } while ((l_iter = l_iter->radial_next) != l_first);
409         }
410 }
411
412 /**
413  * Un-Tag faces connected to an edge loop, clearing FACE_SHARED
414  */
415 static void bm_faces_share_tag_clear(BMesh *bm, BMEdge **e_arr_iter, const unsigned int e_arr_len_iter)
416 {
417         unsigned int i;
418
419         for (i = 0; i < e_arr_len_iter; i++) {
420                 BMEdge *e = e_arr_iter[i];
421                 BMLoop *l_iter, *l_first;
422
423                 l_iter = l_first = e->l;
424                 do {
425                         BMO_elem_flag_disable(bm, l_iter->f, FACE_SHARED);
426                 } while ((l_iter = l_iter->radial_next) != l_first);
427         }
428 }
429
430 /**
431  * Store data for each loop pair,
432  * needed so we don't get feedback loop reading/writing the mesh data.
433  *
434  * currently only used to store vert-spline-handles,
435  * but may be extended for other uses.
436  */
437 typedef struct LoopPairStore {
438         /* handle array for splines */
439         float (*nors_a)[3];
440         float (*nors_b)[3];
441
442         /* since we don't have reliable index values into the array,
443          * store a map (BMVert -> index) */
444         GHash *nors_gh_a;
445         GHash *nors_gh_b;
446 } LoopPairStore;
447
448 static LoopPairStore *bm_edgering_pair_store_create(
449         BMesh *bm,
450         struct BMEdgeLoopStore *el_store_a,
451         struct BMEdgeLoopStore *el_store_b,
452         const int interp_mode)
453 {
454         LoopPairStore *lpair = MEM_mallocN(sizeof(*lpair), __func__);
455
456         if (interp_mode == SUBD_RING_INTERP_SURF) {
457                 const unsigned int len_a = BM_edgeloop_length_get(el_store_a);
458                 const unsigned int len_b = BM_edgeloop_length_get(el_store_b);
459                 const unsigned int e_arr_a_len = len_a - (BM_edgeloop_is_closed(el_store_a) ? 0 : 1);
460                 const unsigned int e_arr_b_len = len_b - (BM_edgeloop_is_closed(el_store_b) ? 0 : 1);
461                 BMEdge **e_arr_a = BLI_array_alloca(e_arr_a, e_arr_a_len);
462                 BMEdge **e_arr_b = BLI_array_alloca(e_arr_b, e_arr_b_len);
463                 unsigned int i;
464
465                 struct BMEdgeLoopStore *el_store_pair[2] = {el_store_a, el_store_b};
466                 unsigned int side_index;
467                 float (*nors_pair[2])[3];
468                 GHash *nors_gh_pair[2];
469
470                 BM_edgeloop_edges_get(el_store_a, e_arr_a);
471                 BM_edgeloop_edges_get(el_store_b, e_arr_b);
472
473                 lpair->nors_a = MEM_mallocN(sizeof(*lpair->nors_a) * len_a, __func__);
474                 lpair->nors_b = MEM_mallocN(sizeof(*lpair->nors_b) * len_b, __func__);
475
476                 nors_pair[0] = lpair->nors_a;
477                 nors_pair[1] = lpair->nors_b;
478
479                 lpair->nors_gh_a = BLI_ghash_ptr_new(__func__);
480                 lpair->nors_gh_b = BLI_ghash_ptr_new(__func__);
481
482                 nors_gh_pair[0] = lpair->nors_gh_a;
483                 nors_gh_pair[1] = lpair->nors_gh_b;
484
485                 /* now calculate nor */
486
487                 /* all other verts must _not_ be tagged */
488                 bmo_edgeloop_vert_tag(bm, el_store_a, VERT_SHARED, true);
489                 bmo_edgeloop_vert_tag(bm, el_store_b, VERT_SHARED, true);
490
491                 /* tag all faces that are in-between both loops */
492                 bm_faces_share_tag_flush(bm, e_arr_a, e_arr_a_len);
493                 bm_faces_share_tag_flush(bm, e_arr_b, e_arr_b_len);
494
495                 /* now we have all data we need, calculate vertex spline nor! */
496                 for (side_index = 0; side_index < 2; side_index++) {
497                         /* iter vars */
498                         struct BMEdgeLoopStore *el_store = el_store_pair[side_index];
499                         ListBase *lb = BM_edgeloop_verts_get(el_store);
500                         GHash *nors_gh_iter = nors_gh_pair[side_index];
501                         float (*nor)[3] = nors_pair[side_index];
502
503                         LinkData *v_iter;
504
505                         for (v_iter = lb->first, i = 0; v_iter; v_iter = v_iter->next, i++) {
506                                 BMVert *v = v_iter->data;
507                                 bm_vert_calc_surface_tangent(bm, v, nor[i]);
508                                 BLI_ghash_insert(nors_gh_iter, v, SET_UINT_IN_POINTER(i));
509                         }
510                 }
511
512                 /* cleanup verts share */
513                 bmo_edgeloop_vert_tag(bm, el_store_a, VERT_SHARED, false);
514                 bmo_edgeloop_vert_tag(bm, el_store_b, VERT_SHARED, false);
515
516                 /* cleanup faces share */
517                 bm_faces_share_tag_clear(bm, e_arr_a, e_arr_a_len);
518                 bm_faces_share_tag_clear(bm, e_arr_b, e_arr_b_len);
519         }
520         return lpair;
521 }
522
523 static void bm_edgering_pair_store_free(
524         LoopPairStore *lpair,
525         const int interp_mode)
526 {
527         if (interp_mode == SUBD_RING_INTERP_SURF) {
528                 MEM_freeN(lpair->nors_a);
529                 MEM_freeN(lpair->nors_b);
530
531                 BLI_ghash_free(lpair->nors_gh_a, NULL, NULL);
532                 BLI_ghash_free(lpair->nors_gh_b, NULL, NULL);
533         }
534         MEM_freeN(lpair);
535 }
536
537
538 /* -------------------------------------------------------------------- */
539 /* Interpolation Function */
540
541 static void bm_edgering_pair_interpolate(BMesh *bm, LoopPairStore *lpair,
542                                          struct BMEdgeLoopStore *el_store_a,
543                                          struct BMEdgeLoopStore *el_store_b,
544                                          ListBase *eloops_ring,
545                                          const int interp_mode, const int cuts, const float smooth,
546                                          const float *falloff_cache)
547 {
548         const int resolu = cuts + 2;
549         const int dims = 3;
550         bool is_a_no_valid, is_b_no_valid;
551         int i;
552
553         float el_store_a_co[3], el_store_b_co[3];
554         float el_store_a_no[3], el_store_b_no[3];
555
556         struct BMEdgeLoopStore *el_store_ring;
557
558         float (*coord_array_main)[3] = NULL;
559
560         BM_edgeloop_calc_center(bm, el_store_a);
561         BM_edgeloop_calc_center(bm, el_store_b);
562
563         is_a_no_valid = BM_edgeloop_calc_normal(bm, el_store_a);
564         is_b_no_valid = BM_edgeloop_calc_normal(bm, el_store_b);
565
566         copy_v3_v3(el_store_a_co, BM_edgeloop_center_get(el_store_a));
567         copy_v3_v3(el_store_b_co, BM_edgeloop_center_get(el_store_b));
568
569         /* correct normals need to be flipped to face each other
570          * we know both normals point in the same direction so one will need flipping */
571         {
572                 float el_dir[3];
573                 float no[3];
574                 sub_v3_v3v3(el_dir, el_store_a_co, el_store_b_co);
575                 normalize_v3_v3(no, el_dir);
576
577                 if (is_a_no_valid == false) {
578                         is_a_no_valid = BM_edgeloop_calc_normal_aligned(bm, el_store_a, no);
579                 }
580                 if (is_b_no_valid == false) {
581                         is_b_no_valid = BM_edgeloop_calc_normal_aligned(bm, el_store_b, no);
582                 }
583                 (void)is_a_no_valid, (void)is_b_no_valid;
584
585                 copy_v3_v3(el_store_a_no, BM_edgeloop_normal_get(el_store_a));
586                 copy_v3_v3(el_store_b_no, BM_edgeloop_normal_get(el_store_b));
587
588                 if (dot_v3v3(el_store_a_no, el_dir) > 0.0f) {
589                         negate_v3(el_store_a_no);
590                 }
591                 if (dot_v3v3(el_store_b_no, el_dir) < 0.0f) {
592                         negate_v3(el_store_b_no);
593                 }
594
595         }
596         /* now normals are correct, don't touch! */
597
598
599         /* calculate the center spline, multiple  */
600         if ((interp_mode == SUBD_RING_INTERP_PATH) || falloff_cache) {
601                 float handle_a[3], handle_b[3];
602                 float handle_len;
603
604                 handle_len = bezier_handle_calc_length_v3(el_store_a_co, el_store_a_no,
605                                                           el_store_b_co, el_store_b_no) * smooth;
606
607                 mul_v3_v3fl(handle_a, el_store_a_no, handle_len);
608                 mul_v3_v3fl(handle_b, el_store_b_no, handle_len);
609
610                 add_v3_v3(handle_a, el_store_a_co);
611                 add_v3_v3(handle_b, el_store_b_co);
612
613                 coord_array_main = MEM_mallocN(dims * (resolu) * sizeof(float), __func__);
614
615                 for (i = 0; i < dims; i++) {
616                         BKE_curve_forward_diff_bezier(el_store_a_co[i], handle_a[i], handle_b[i], el_store_b_co[i],
617                                                       ((float *)coord_array_main) + i, resolu - 1, sizeof(float) * dims);
618                 }
619         }
620
621         switch (interp_mode) {
622                 case SUBD_RING_INTERP_LINEAR:
623                 {
624                         if (falloff_cache) {
625                                 float (*coord_array)[3] = MEM_mallocN(dims * (resolu) * sizeof(float), __func__);
626                                 for (i = 0; i < resolu; i++) {
627                                         interp_v3_v3v3(coord_array[i], el_store_a_co, el_store_b_co, (float)i / (float)(resolu - 1));
628                                 }
629
630                                 for (el_store_ring = eloops_ring->first;
631                                      el_store_ring;
632                                      el_store_ring = BM_EDGELOOP_NEXT(el_store_ring))
633                                 {
634                                         ListBase *lb_ring = BM_edgeloop_verts_get(el_store_ring);
635                                         LinkData *v_iter;
636
637                                         for (v_iter = lb_ring->first, i = 0; v_iter; v_iter = v_iter->next, i++) {
638                                                 if (i > 0 && i < resolu - 1) {
639                                                         /* shape */
640                                                         if (falloff_cache) {
641                                                                 interp_v3_v3v3(((BMVert *)v_iter->data)->co,
642                                                                                coord_array[i], ((BMVert *)v_iter->data)->co, falloff_cache[i]);
643                                                         }
644                                                 }
645                                         }
646                                 }
647
648                                 MEM_freeN(coord_array);
649
650                         }
651
652                         break;
653                 }
654                 case SUBD_RING_INTERP_PATH:
655                 {
656                         float (*direction_array)[3] = MEM_mallocN(dims * (resolu) * sizeof(float), __func__);
657                         float (*quat_array)[4] = MEM_mallocN(resolu * sizeof(*quat_array), __func__);
658                         float (*tri_array)[3][3] = MEM_mallocN(resolu * sizeof(*tri_array), __func__);
659                         float (*tri_sta)[3], (*tri_end)[3], (*tri_tmp)[3];
660
661                         /* very similar to make_bevel_list_3D_minimum_twist */
662
663                         /* calculate normals */
664                         copy_v3_v3(direction_array[0],            el_store_a_no);
665                         negate_v3_v3(direction_array[resolu - 1], el_store_b_no);
666                         for (i = 1; i < resolu - 1; i++) {
667                                 bisect_v3_v3v3v3(direction_array[i],
668                                                  coord_array_main[i - 1], coord_array_main[i], coord_array_main[i + 1]);
669                         }
670
671                         vec_to_quat(quat_array[0], direction_array[0], 5, 1);
672                         normalize_qt(quat_array[0]);
673
674                         for (i = 1; i < resolu; i++) {
675                                 float angle = angle_normalized_v3v3(direction_array[i - 1], direction_array[i]);
676                                 // BLI_assert(angle < DEG2RADF(90.0f));
677                                 if (angle > 0.0f) { /* otherwise we can keep as is */
678                                         float cross_tmp[3];
679                                         float q[4];
680                                         cross_v3_v3v3(cross_tmp, direction_array[i - 1], direction_array[i]);
681                                         axis_angle_to_quat(q, cross_tmp, angle);
682                                         mul_qt_qtqt(quat_array[i], q, quat_array[i - 1]);
683                                         normalize_qt(quat_array[i]);
684                                 }
685                                 else {
686                                         copy_qt_qt(quat_array[i], quat_array[i - 1]);
687                                 }
688                         }
689
690                         /* init base tri */
691                         for (i = 0; i < resolu; i++) {
692                                 int j;
693
694                                 const float shape_size = falloff_cache ? falloff_cache[i] : 1.0f;
695
696                                 tri_tmp = tri_array[i];
697
698                                 /* create the triangle and transform */
699                                 for (j = 0; j < 3; j++) {
700                                         zero_v3(tri_tmp[j]);
701                                         if      (j == 1) tri_tmp[j][0] = shape_size;
702                                         else if (j == 2) tri_tmp[j][1] = shape_size;
703                                         mul_qt_v3(quat_array[i], tri_tmp[j]);
704                                         add_v3_v3(tri_tmp[j], coord_array_main[i]);
705                                 }
706                         }
707
708                         tri_sta = tri_array[0];
709                         tri_end = tri_array[resolu - 1];
710
711                         for (el_store_ring = eloops_ring->first;
712                              el_store_ring;
713                              el_store_ring = BM_EDGELOOP_NEXT(el_store_ring))
714                         {
715                                 ListBase *lb_ring = BM_edgeloop_verts_get(el_store_ring);
716                                 LinkData *v_iter;
717
718                                 BMVert *v_a = ((LinkData *)lb_ring->first)->data;
719                                 BMVert *v_b = ((LinkData *)lb_ring->last)->data;
720
721                                 /* skip first and last */
722                                 for (v_iter = ((LinkData *)lb_ring->first)->next, i = 1;
723                                      v_iter != lb_ring->last;
724                                      v_iter = v_iter->next, i++)
725                                 {
726                                         float co_a[3], co_b[3];
727
728                                         tri_tmp = tri_array[i];
729
730                                         barycentric_transform(co_a, v_a->co, UNPACK3(tri_tmp), UNPACK3(tri_sta));
731                                         barycentric_transform(co_b, v_b->co, UNPACK3(tri_tmp), UNPACK3(tri_end));
732
733                                         interp_v3_v3v3(((BMVert *)v_iter->data)->co, co_a, co_b, (float)i / (float)(resolu - 1));
734                                 }
735                         }
736
737                         MEM_freeN(direction_array);
738                         MEM_freeN(quat_array);
739                         MEM_freeN(tri_array);
740                         break;
741                 }
742                 case SUBD_RING_INTERP_SURF:
743                 {
744                         float (*coord_array)[3] = MEM_mallocN(dims * (resolu) * sizeof(float), __func__);
745
746                         /* calculate a bezier handle per edge ring */
747                         for (el_store_ring = eloops_ring->first;
748                              el_store_ring;
749                              el_store_ring = BM_EDGELOOP_NEXT(el_store_ring))
750                         {
751                                 ListBase *lb_ring = BM_edgeloop_verts_get(el_store_ring);
752                                 LinkData *v_iter;
753
754                                 BMVert *v_a = ((LinkData *)lb_ring->first)->data;
755                                 BMVert *v_b = ((LinkData *)lb_ring->last)->data;
756
757                                 float co_a[3], no_a[3], handle_a[3], co_b[3], no_b[3], handle_b[3];
758                                 float handle_len;
759
760                                 copy_v3_v3(co_a, v_a->co);
761                                 copy_v3_v3(co_b, v_b->co);
762
763                                 /* don't calculate normals here else we get into feedback loop
764                                  * when subdividing 2+ connected edge rings */
765 #if 0
766                                 bm_vert_calc_surface_tangent(bm, v_a, no_a);
767                                 bm_vert_calc_surface_tangent(bm, v_b, no_b);
768 #else
769                                 {
770                                         const unsigned int index_a = GET_UINT_FROM_POINTER(BLI_ghash_lookup(lpair->nors_gh_a, v_a));
771                                         const unsigned int index_b = GET_UINT_FROM_POINTER(BLI_ghash_lookup(lpair->nors_gh_b, v_b));
772
773                                         BLI_assert(BLI_ghash_haskey(lpair->nors_gh_a, v_a));
774                                         BLI_assert(BLI_ghash_haskey(lpair->nors_gh_b, v_b));
775
776                                         copy_v3_v3(no_a, lpair->nors_a[index_a]);
777                                         copy_v3_v3(no_b, lpair->nors_b[index_b]);
778                                 }
779 #endif
780                                 handle_len = bezier_handle_calc_length_v3(co_a, no_a, co_b, no_b) * smooth;
781
782                                 mul_v3_v3fl(handle_a, no_a, handle_len);
783                                 mul_v3_v3fl(handle_b, no_b, handle_len);
784
785                                 add_v3_v3(handle_a, co_a);
786                                 add_v3_v3(handle_b, co_b);
787
788                                 for (i = 0; i < dims; i++) {
789                                         BKE_curve_forward_diff_bezier(co_a[i], handle_a[i], handle_b[i], co_b[i],
790                                                                       ((float *)coord_array) + i, resolu - 1, sizeof(float) * dims);
791                                 }
792
793                                 /* skip first and last */
794                                 for (v_iter = ((LinkData *)lb_ring->first)->next, i = 1;
795                                      v_iter != lb_ring->last;
796                                      v_iter = v_iter->next, i++)
797                                 {
798                                         if (i > 0 && i < resolu - 1) {
799                                                 copy_v3_v3(((BMVert *)v_iter->data)->co, coord_array[i]);
800
801                                                 /* shape */
802                                                 if (falloff_cache) {
803                                                         interp_v3_v3v3(((BMVert *)v_iter->data)->co,
804                                                                        coord_array_main[i], ((BMVert *)v_iter->data)->co, falloff_cache[i]);
805                                                 }
806                                         }
807                                 }
808                         }
809
810                         MEM_freeN(coord_array);
811
812                         break;
813                 }
814         }
815
816         if (coord_array_main) {
817                 MEM_freeN(coord_array_main);
818         }
819 }
820
821 /**
822  * Cuts up an ngon into many slices.
823  */
824 static void bm_face_slice(BMesh *bm, BMLoop *l, const int cuts)
825 {
826         /* TODO, interpolate edge data */
827         BMLoop *l_new = l;
828         int i;
829
830         for (i = 0; i < cuts; i++) {
831                 /* no chance of double */
832                 BM_face_split(bm, l_new->f, l_new->prev->v, l_new->next->next->v, &l_new, NULL, false);
833                 if (l_new->f->len < l_new->radial_next->f->len) {
834                         l_new = l_new->radial_next;
835                 }
836                 BMO_elem_flag_enable(bm, l_new->f, FACE_OUT);
837                 BMO_elem_flag_enable(bm, l_new->radial_next->f, FACE_OUT);
838         }
839 }
840
841 static bool bm_edgering_pair_order_is_flipped(BMesh *UNUSED(bm),
842                                               struct BMEdgeLoopStore *el_store_a,
843                                               struct BMEdgeLoopStore *el_store_b )
844 {
845         ListBase *lb_a = BM_edgeloop_verts_get(el_store_a);
846         ListBase *lb_b = BM_edgeloop_verts_get(el_store_b);
847
848         LinkData *v_iter_a_first = lb_a->first;
849         LinkData *v_iter_b_first = lb_b->first;
850
851         LinkData *v_iter_a_step = v_iter_a_first;
852         LinkData *v_iter_b_step = v_iter_b_first;
853
854         /* we _must_ have same starting edge shared */
855         BLI_assert(BM_edge_exists(v_iter_a_first->data, v_iter_b_first->data));
856
857         /* step around any fan-faces on both sides */
858         do {
859                 v_iter_a_step = v_iter_a_step->next;
860         } while (v_iter_a_step &&
861                  ((BM_edge_exists(v_iter_a_step->data, v_iter_b_first->data)) ||
862                   (BM_edge_exists(v_iter_a_step->data, v_iter_b_first->next->data))));
863         do {
864                 v_iter_b_step = v_iter_b_step->next;
865         } while (v_iter_b_step &&
866                  ((BM_edge_exists(v_iter_b_step->data, v_iter_a_first->data)) ||
867                   (BM_edge_exists(v_iter_b_step->data, v_iter_a_first->next->data))));
868
869         v_iter_a_step = v_iter_a_step ? v_iter_a_step->prev : lb_a->last;
870         v_iter_b_step = v_iter_b_step ? v_iter_b_step->prev : lb_b->last;
871
872         return !(BM_edge_exists(v_iter_a_step->data, v_iter_b_step->data) ||
873                  BM_edge_exists(v_iter_a_first->next->data, v_iter_b_step->data) ||
874                  BM_edge_exists(v_iter_b_first->next->data, v_iter_a_step->data));
875 }
876
877 /**
878  * Takes 2 edge loops that share edges,
879  * sort their verts and rotates the list so the lined up.
880  */
881 static void bm_edgering_pair_order(BMesh *bm,
882                                    struct BMEdgeLoopStore *el_store_a,
883                                    struct BMEdgeLoopStore *el_store_b)
884 {
885         ListBase *lb_a = BM_edgeloop_verts_get(el_store_a);
886         ListBase *lb_b = BM_edgeloop_verts_get(el_store_b);
887
888         LinkData *node;
889
890         bm_edgeloop_vert_tag(el_store_a, false);
891         bm_edgeloop_vert_tag(el_store_b, true);
892
893         /* before going much further, get ourselves in order
894          * - align loops (not strictly necessary but handy)
895          * - ensure winding is set for both loops */
896         if (BM_edgeloop_is_closed(el_store_a) && BM_edgeloop_is_closed(el_store_b)) {
897                 BMIter eiter;
898                 BMEdge *e;
899                 BMVert *v_other;
900
901                 node = lb_a->first;
902
903                 BM_ITER_ELEM (e, &eiter, (BMVert *)node->data, BM_EDGES_OF_VERT) {
904                         if (BMO_elem_flag_test(bm, e, EDGE_RING)) {
905                                 v_other = BM_edge_other_vert(e, (BMVert *)node->data);
906                                 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
907                                         break;
908                                 }
909                                 else {
910                                         v_other = NULL;
911                                 }
912                         }
913                 }
914                 BLI_assert(v_other != NULL);
915
916                 for (node = lb_b->first; node; node = node->next) {
917                         if (node->data == v_other) {
918                                 break;
919                         }
920                 }
921                 BLI_assert(node != NULL);
922
923                 BLI_rotatelist(lb_b, node);
924
925                 /* now check we are winding the same way */
926                 if (bm_edgering_pair_order_is_flipped(bm, el_store_a, el_store_b)) {
927                         BM_edgeloop_flip(bm, el_store_b);
928                         /* re-ensure the first node */
929                         BLI_rotatelist(lb_b, node);
930                 }
931
932                 /* sanity checks that we are aligned & winding now */
933                 BLI_assert(bm_edgering_pair_order_is_flipped(bm, el_store_a, el_store_b) == false);
934         }
935         else {
936                 /* if we dont share and edge - flip */
937                 BMEdge *e = BM_edge_exists(((LinkData *)lb_a->first)->data,
938                                            ((LinkData *)lb_b->first)->data);
939                 if (e == NULL || !BMO_elem_flag_test(bm, e, EDGE_RING)) {
940                         BM_edgeloop_flip(bm, el_store_b);
941                 }
942         }
943
944         /* for cases with multiple loops */
945         bm_edgeloop_vert_tag(el_store_b, false);
946 }
947
948
949 /**
950  * Take 2 edge loops, do a subdivision on connecting edges.
951  *
952  * \note loops are _not_ aligned.
953  */
954 static void bm_edgering_pair_subdiv(BMesh *bm,
955                                     struct BMEdgeLoopStore *el_store_a,
956                                     struct BMEdgeLoopStore *el_store_b,
957                                     ListBase *eloops_ring,
958                                     const int cuts)
959 {
960         ListBase *lb_a = BM_edgeloop_verts_get(el_store_a);
961         // ListBase *lb_b = BM_edgeloop_verts_get(el_store_b);
962         const int stack_max = max_ii(BM_edgeloop_length_get(el_store_a),
963                                      BM_edgeloop_length_get(el_store_b)) * 2;
964         BMEdge **edges_ring_arr = BLI_array_alloca(edges_ring_arr, stack_max);
965         BMFace **faces_ring_arr = BLI_array_alloca(faces_ring_arr, stack_max);
966         STACK_DECLARE(edges_ring_arr);
967         STACK_DECLARE(faces_ring_arr);
968         struct BMEdgeLoopStore *el_store_ring;
969         LinkData *node;
970         BMEdge *e;
971         BMFace *f;
972
973         STACK_INIT(edges_ring_arr);
974         STACK_INIT(faces_ring_arr);
975
976         bm_edgeloop_vert_tag(el_store_a, false);
977         bm_edgeloop_vert_tag(el_store_b, true);
978
979         for (node = lb_a->first; node; node = node->next) {
980                 BMIter eiter;
981
982                 BM_ITER_ELEM (e, &eiter, (BMVert *)node->data, BM_EDGES_OF_VERT) {
983                         if (!BMO_elem_flag_test(bm, e, EDGE_IN_STACK)) {
984                                 BMVert *v_other = BM_edge_other_vert(e, (BMVert *)node->data);
985                                 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
986                                         BMIter fiter;
987
988                                         BMO_elem_flag_enable(bm, e, EDGE_IN_STACK);
989                                         STACK_PUSH(edges_ring_arr, e);
990
991                                         /* add faces to the stack */
992                                         BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
993                                                 if (BMO_elem_flag_test(bm, f, FACE_OUT)) {
994                                                         if (!BMO_elem_flag_test(bm, f, FACE_IN_STACK)) {
995                                                                 BMO_elem_flag_enable(bm, f, FACE_IN_STACK);
996                                                                 STACK_PUSH(faces_ring_arr, f);
997                                                         }
998                                                 }
999                                         }
1000                                 }
1001                         }
1002                 }
1003         }
1004
1005         while ((e = STACK_POP(edges_ring_arr))) {
1006                 /* found opposite edge */
1007                 BMVert *v_other;
1008
1009                 BMO_elem_flag_disable(bm, e, EDGE_IN_STACK);
1010
1011                 /* unrelated to subdiv, but if we _don't_ clear flag, multiple rings fail */
1012                 BMO_elem_flag_disable(bm, e, EDGE_RING);
1013
1014                 v_other = BM_elem_flag_test(e->v1, BM_ELEM_TAG) ? e->v1 : e->v2;
1015                 bm_edge_subdiv_as_loop(bm, eloops_ring, e, v_other, cuts);
1016         }
1017
1018         while ((f = STACK_POP(faces_ring_arr))) {
1019                 BMLoop *l_iter, *l_first;
1020
1021                 BMO_elem_flag_disable(bm, f, FACE_IN_STACK);
1022
1023                 /* Check each edge of the face */
1024                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1025                 do {
1026                         if (BMO_elem_flag_test(bm, l_iter->e, EDGE_RIM)) {
1027                                 bm_face_slice(bm, l_iter, cuts);
1028                                 break;
1029                         }
1030                 } while ((l_iter = l_iter->next) != l_first);
1031         }
1032
1033
1034         /* clear tags so subdiv verts don't get tagged too  */
1035         for (el_store_ring = eloops_ring->first;
1036              el_store_ring;
1037              el_store_ring = BM_EDGELOOP_NEXT(el_store_ring))
1038         {
1039                 bm_edgeloop_vert_tag(el_store_ring, false);
1040         }
1041
1042         /* cleanup after */
1043         bm_edgeloop_vert_tag(el_store_b, false);
1044 }
1045
1046 static void bm_edgering_pair_ringsubd(BMesh *bm, LoopPairStore *lpair,
1047                                       struct BMEdgeLoopStore *el_store_a,
1048                                       struct BMEdgeLoopStore *el_store_b,
1049                                       const int interp_mode, const int cuts, const float smooth,
1050                                       const float *falloff_cache)
1051 {
1052         ListBase eloops_ring = {NULL};
1053         bm_edgering_pair_order(bm, el_store_a, el_store_b);
1054         bm_edgering_pair_subdiv(bm, el_store_a, el_store_b, &eloops_ring, cuts);
1055         bm_edgering_pair_interpolate(bm, lpair, el_store_a, el_store_b, &eloops_ring,
1056                                      interp_mode, cuts, smooth, falloff_cache);
1057         BM_mesh_edgeloops_free(&eloops_ring);
1058 }
1059
1060 static bool bm_edge_rim_test_cb(BMEdge *e, void *bm_v)
1061 {
1062         BMesh *bm = bm_v;
1063         return BMO_elem_flag_test_bool(bm, e, EDGE_RIM);
1064 }
1065
1066
1067 /* keep this operator fast, its used in a modifier */
1068 void bmo_subdivide_edgering_exec(BMesh *bm, BMOperator *op)
1069 {
1070         ListBase eloops_rim = {NULL};
1071         BMOIter siter;
1072         BMEdge *e;
1073         int count;
1074         bool change = false;
1075
1076         const int cuts = BMO_slot_int_get(op->slots_in, "cuts");
1077         const int interp_mode = BMO_slot_int_get(op->slots_in, "interp_mode");
1078         const float smooth = BMO_slot_float_get(op->slots_in, "smooth");
1079         const int resolu = cuts + 2;
1080
1081         /* optional 'shape' */
1082         const int profile_shape = BMO_slot_int_get(op->slots_in, "profile_shape");
1083         const float profile_shape_factor = BMO_slot_float_get(op->slots_in, "profile_shape_factor");
1084         float *falloff_cache = (profile_shape_factor != 0.0f) ? BLI_array_alloca(falloff_cache, cuts + 2) : NULL;
1085
1086         BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_RING);
1087
1088         BM_mesh_elem_hflag_disable_all(bm, BM_VERT, BM_ELEM_TAG, false);
1089
1090         /* -------------------------------------------------------------------- */
1091         /* flag outer edges (loops defined as edges on the bounds of the edge ring) */
1092
1093         BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
1094                 BMIter fiter;
1095                 BMFace *f;
1096
1097                 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
1098                         if (!BMO_elem_flag_test(bm, f, FACE_OUT)) {
1099                                 BMIter liter;
1100                                 BMLoop *l;
1101                                 bool ok = false;
1102
1103                                 /* check at least 2 edges in the face are rings */
1104                                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
1105                                         if (BMO_elem_flag_test(bm, l->e, EDGE_RING) && e != l->e) {
1106                                                 ok = true;
1107                                                 break;
1108                                         }
1109                                 }
1110
1111                                 if (ok) {
1112                                         BMO_elem_flag_enable(bm, f, FACE_OUT);
1113
1114                                         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
1115                                                 if (!BMO_elem_flag_test(bm, l->e, EDGE_RING)) {
1116                                                         BMO_elem_flag_enable(bm, l->e, EDGE_RIM);
1117                                                 }
1118                                         }
1119                                 }
1120                         }
1121                 }
1122         }
1123
1124
1125         /* -------------------------------------------------------------------- */
1126         /* Cache falloff for each step (symmetrical) */
1127
1128         if (falloff_cache) {
1129                 int i;
1130                 for (i = 0; i < resolu; i++) {
1131                         float shape_size = 1.0f;
1132                         float fac = (float)i / (float)(resolu - 1);
1133                         fac = fabsf(1.0f - 2.0f * fabsf(0.5f - fac));
1134                         fac = bmesh_subd_falloff_calc(profile_shape, fac);
1135                         shape_size += fac * profile_shape_factor;
1136
1137                         falloff_cache[i] = shape_size;
1138                 }
1139         }
1140
1141
1142         /* -------------------------------------------------------------------- */
1143         /* Execute subdivision on all ring pairs */
1144
1145         count = BM_mesh_edgeloops_find(bm, &eloops_rim, bm_edge_rim_test_cb, (void *)bm);
1146
1147         if (count < 2) {
1148                 BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
1149                                 "No edge rings found");
1150                 goto cleanup;
1151         }
1152         else if (count == 2) {
1153                 /* this case could be removed,
1154                  * but simple to avoid 'bm_edgering_pair_calc' in this case since theres only one. */
1155                 struct BMEdgeLoopStore *el_store_a = eloops_rim.first;
1156                 struct BMEdgeLoopStore *el_store_b = eloops_rim.last;
1157                 LoopPairStore *lpair;
1158
1159                 if (bm_edgeloop_check_overlap_all(bm, el_store_a, el_store_b)) {
1160                         lpair = bm_edgering_pair_store_create(bm, el_store_a, el_store_b, interp_mode);
1161                 }
1162                 else {
1163                         lpair = NULL;
1164                 }
1165
1166                 if (lpair) {
1167                         bm_edgering_pair_ringsubd(bm, lpair, el_store_a, el_store_b,
1168                                                   interp_mode, cuts, smooth, falloff_cache);
1169                         bm_edgering_pair_store_free(lpair, interp_mode);
1170                         change = true;
1171                 }
1172                 else {
1173                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
1174                                         "Edge-ring pair isn't connected");
1175                         goto cleanup;
1176                 }
1177         }
1178         else {
1179                 GHashIterator gh_iter;
1180                 int i;
1181
1182                 GHash *eloop_pairs_gh = bm_edgering_pair_calc(bm, &eloops_rim);
1183                 LoopPairStore **lpair_arr;
1184
1185                 if (eloop_pairs_gh == NULL) {
1186                         BMO_error_raise(bm, op, BMERR_INVALID_SELECTION,
1187                                         "Edge-rings are not connected");
1188                         goto cleanup;
1189                 }
1190
1191                 lpair_arr = BLI_array_alloca(lpair_arr, BLI_ghash_size(eloop_pairs_gh));
1192
1193                 /* first cache pairs */
1194                 GHASH_ITER_INDEX (gh_iter, eloop_pairs_gh, i) {
1195                         GHashPair *eloop_pair = BLI_ghashIterator_getKey(&gh_iter);
1196                         struct BMEdgeLoopStore *el_store_a = (void *)eloop_pair->first;
1197                         struct BMEdgeLoopStore *el_store_b = (void *)eloop_pair->second;
1198                         LoopPairStore *lpair;
1199
1200                         if (bm_edgeloop_check_overlap_all(bm, el_store_a, el_store_b)) {
1201                                 lpair = bm_edgering_pair_store_create(bm, el_store_a, el_store_b, interp_mode);
1202                         }
1203                         else {
1204                                 lpair = NULL;
1205                         }
1206                         lpair_arr[i] = lpair;
1207
1208                         BLI_assert(bm_verts_tag_count(bm) == 0);
1209                 }
1210
1211                 GHASH_ITER_INDEX (gh_iter, eloop_pairs_gh, i) {
1212                         GHashPair *eloop_pair = BLI_ghashIterator_getKey(&gh_iter);
1213                         struct BMEdgeLoopStore *el_store_a = (void *)eloop_pair->first;
1214                         struct BMEdgeLoopStore *el_store_b = (void *)eloop_pair->second;
1215                         LoopPairStore *lpair = lpair_arr[i];
1216
1217                         if (lpair) {
1218                                 bm_edgering_pair_ringsubd(bm, lpair, el_store_a, el_store_b,
1219                                                           interp_mode, cuts, smooth, falloff_cache);
1220                                 bm_edgering_pair_store_free(lpair, interp_mode);
1221                                 change = true;
1222                         }
1223
1224                         BLI_assert(bm_verts_tag_count(bm) == 0);
1225                 }
1226                 BLI_ghash_free(eloop_pairs_gh, MEM_freeN, NULL);
1227         }
1228
1229 cleanup:
1230         BM_mesh_edgeloops_free(&eloops_rim);
1231
1232         /* flag output */
1233         if (change) {
1234                 BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT);
1235         }
1236 }