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