Mempool: delay allocating an initial chunk, its not always used
[blender.git] / source / blender / bmesh / intern / bmesh_edgeloop.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  * The Original Code is Copyright (C) 2013 by Campbell Barton.
19  * All rights reserved.
20  *
21  * ***** END GPL LICENSE BLOCK *****
22  */
23
24 /** \file blender/bmesh/intern/bmesh_edgeloop.c
25  *  \ingroup bmesh
26  *
27  * Generic utility functions for getting edge loops from a mesh.
28  */
29
30 #include "MEM_guardedalloc.h"
31
32 #include "BLI_math_vector.h"
33 #include "BLI_listbase.h"
34 #include "BLI_mempool.h"
35
36 #include "bmesh.h"
37
38 #include "bmesh_edgeloop.h"  /* own include */
39
40 typedef struct BMEdgeLoopStore {
41         struct BMEdgeLoopStore *next, *prev;
42         ListBase verts;
43         int flag;
44         int len;
45         /* optional values  to calc */
46         float co[3], no[3];
47 } BMEdgeLoopStore;
48
49 #define BM_EDGELOOP_IS_CLOSED (1 << 0)
50 #define EDGELOOP_EPS 0.00001f
51
52 /* -------------------------------------------------------------------- */
53 /* BM_mesh_edgeloops_find & Util Functions  */
54
55 static int bm_vert_other_tag(BMVert *v, BMVert *v_prev,
56                              BMEdge **r_e)
57 {
58         BMIter iter;
59         BMEdge *e, *e_next = NULL;
60         unsigned int count = 0;
61
62         BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
63                 if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) {
64                         BMVert *v_other = BM_edge_other_vert(e, v);
65                         if (v_other != v_prev) {
66                                 e_next = e;
67                                 count++;
68                         }
69                 }
70         }
71
72         *r_e = e_next;
73         return count;
74 }
75
76 /**
77  * \return success
78  */
79 static bool bm_loop_build(BMEdgeLoopStore *el_store, BMVert *v_prev, BMVert *v, int dir)
80 {
81         void (*add_fn)(ListBase *, void *) = dir == 1 ? BLI_addhead : BLI_addtail;
82         BMEdge *e_next;
83         BMVert *v_next;
84         BMVert *v_first = v;
85
86         BLI_assert(ABS(dir) == 1);
87
88         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
89                 return true;
90         }
91
92         while (v) {
93                 LinkData *node = MEM_callocN(sizeof(*node), __func__);
94                 int count;
95                 node->data = v;
96                 add_fn(&el_store->verts, node);
97                 el_store->len++;
98                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
99
100                 count = bm_vert_other_tag(v, v_prev, &e_next);
101                 if (count == 1) {
102                         v_next = BM_edge_other_vert(e_next, v);
103                         BM_elem_flag_disable(e_next, BM_ELEM_INTERNAL_TAG);
104                         if (UNLIKELY(v_next == v_first)) {
105                                 el_store->flag |= BM_EDGELOOP_IS_CLOSED;
106                                 v_next = NULL;
107                         }
108                 }
109                 else if (count == 0) {
110                         /* pass */
111                         v_next = NULL;
112                 }
113                 else {
114                         v_next = NULL;
115                         return false;
116                 }
117
118                 v_prev = v;
119                 v = v_next;
120         }
121
122         return true;
123 }
124
125 /**
126  * \return listbase of listbases, each linking to a vertex.
127  */
128 int BM_mesh_edgeloops_find(BMesh *bm, ListBase *r_eloops,
129                            bool (*test_fn)(BMEdge *, void *user_data), void *user_data)
130 {
131         BMIter iter;
132         BMEdge *e;
133         BMVert *v;
134         int count = 0;
135
136         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
137                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
138         }
139
140         /* first flush edges to tags, and tag verts */
141         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
142                 if (test_fn(e, user_data)) {
143                         BM_elem_flag_enable(e,     BM_ELEM_INTERNAL_TAG);
144                         BM_elem_flag_enable(e->v1, BM_ELEM_INTERNAL_TAG);
145                         BM_elem_flag_enable(e->v2, BM_ELEM_INTERNAL_TAG);
146                 }
147                 else {
148                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
149                 }
150         }
151
152         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
153                 if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) {
154                         BMEdgeLoopStore *el_store = MEM_callocN(sizeof(BMEdgeLoopStore), __func__);
155
156                         /* add both directions */
157                         if (bm_loop_build(el_store, e->v1, e->v2,  1) &&
158                             bm_loop_build(el_store, e->v2, e->v1, -1) &&
159                             el_store->len > 1)
160                         {
161                                 BLI_addtail(r_eloops, el_store);
162                                 BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
163                                 count++;
164                         }
165                         else {
166                                 BM_edgeloop_free(el_store);
167                         }
168                 }
169         }
170         return count;
171 }
172
173
174 /* -------------------------------------------------------------------- */
175 /* BM_mesh_edgeloops_find_path & Util Functions  */
176
177 /**
178  * Find s single, open edge loop - given 2 vertices.
179  * Add to
180  */
181 struct VertStep {
182         struct VertStep *next, *prev;
183         BMVert *v;
184 };
185
186 static void vs_add(BLI_mempool *vs_pool, ListBase *lb,
187                    BMVert *v, BMEdge *e_prev, const int iter_tot)
188 {
189         struct VertStep *vs_new = BLI_mempool_alloc(vs_pool);
190         vs_new->v = v;
191
192         BM_elem_index_set(v, iter_tot);
193
194         /* This edge stores a direct path back to the original vertex so we can
195          * backtrack without having to store an array of previous verts. */
196
197         /* WARNING - setting the edge is not common practice
198          * but currently harmless, take care. */
199         BLI_assert(BM_vert_in_edge(e_prev, v));
200         v->e = e_prev;
201
202         BLI_addtail(lb, vs_new);
203 }
204
205 static bool bm_loop_path_build_step(BLI_mempool *vs_pool, ListBase *lb, const int dir, BMVert *v_match[2])
206 {
207         ListBase lb_tmp = {NULL, NULL};
208         struct VertStep *vs, *vs_next;
209         BLI_assert(ABS(dir) == 1);
210
211         for (vs = lb->first; vs; vs = vs_next) {
212                 BMIter iter;
213                 BMEdge *e;
214                 /* these values will be the same every iteration */
215                 const int vs_iter_tot  = BM_elem_index_get(vs->v);
216                 const int vs_iter_next = vs_iter_tot + dir;
217
218                 vs_next = vs->next;
219
220                 BM_ITER_ELEM (e, &iter, vs->v, BM_EDGES_OF_VERT) {
221                         if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) {
222                                 BMVert *v_next = BM_edge_other_vert(e, vs->v);
223                                 const int v_next_index = BM_elem_index_get(v_next);
224                                 /* not essential to clear flag but prevents more checking next time round */
225                                 BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
226                                 if (v_next_index == 0) {
227                                         vs_add(vs_pool, &lb_tmp, v_next, e, vs_iter_next);
228                                 }
229                                 else if ((dir < 0) == (v_next_index < 0)) {
230                                         /* on the same side - do nothing */
231                                 }
232                                 else {
233                                         /* we have met out match! (vertices from different sides meet) */
234                                         if (dir == 1) {
235                                                 v_match[0] = vs->v;
236                                                 v_match[1] = v_next;
237                                         }
238                                         else {
239                                                 v_match[0] = v_next;
240                                                 v_match[1] = vs->v;
241                                         }
242                                         /* normally we would manage memory of remaining items in (lb, lb_tmp),
243                                          * but search is done, vs_pool will get destroyed immediately */
244                                         return true;
245                                 }
246                         }
247                 }
248
249                 BLI_mempool_free(vs_pool, vs);
250         }
251
252         /* lb is now full of free'd items, overwrite */
253         *lb = lb_tmp;
254
255         return (BLI_listbase_is_empty(lb) == false);
256 }
257
258 bool BM_mesh_edgeloops_find_path(BMesh *bm, ListBase *r_eloops,
259                                  bool (*test_fn)(BMEdge *, void *user_data), void *user_data,
260                                  BMVert *v_src, BMVert *v_dst)
261 {
262         BMIter iter;
263         BMEdge *e;
264
265         BLI_assert(v_src != v_dst);
266
267         {
268                 BMVert *v;
269                 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
270                         BM_elem_index_set(v, 0);
271                 }
272         }
273         bm->elem_index_dirty |= BM_VERT;
274
275         /* first flush edges to tags, and tag verts */
276         if (test_fn) {
277                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
278                         if (test_fn(e, user_data)) {
279                                 BM_elem_flag_enable(e,     BM_ELEM_INTERNAL_TAG);
280                                 BM_elem_flag_enable(e->v1, BM_ELEM_INTERNAL_TAG);
281                                 BM_elem_flag_enable(e->v2, BM_ELEM_INTERNAL_TAG);
282                         }
283                         else {
284                                 BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
285                         }
286                 }
287         }
288         else {
289                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
290                         BM_elem_flag_enable(e,     BM_ELEM_INTERNAL_TAG);
291                         BM_elem_flag_enable(e->v1, BM_ELEM_INTERNAL_TAG);
292                         BM_elem_flag_enable(e->v2, BM_ELEM_INTERNAL_TAG);
293                 }
294         }
295
296         /* prime the lists and begin search */
297         {
298                 BMVert *v_match[2] = {NULL, NULL};
299                 ListBase lb_src = {NULL, NULL};
300                 ListBase lb_dst = {NULL, NULL};
301                 BLI_mempool *vs_pool = BLI_mempool_create(sizeof(struct VertStep), 0, 512, BLI_MEMPOOL_NOP);
302
303                 /* edge args are dummy */
304                 vs_add(vs_pool, &lb_src, v_src, v_src->e,  1);
305                 vs_add(vs_pool, &lb_dst, v_dst, v_dst->e, -1);
306
307                 do {
308                         if ((bm_loop_path_build_step(vs_pool, &lb_src, 1, v_match) == false) || v_match[0]) {
309                                 break;
310                         }
311                         if ((bm_loop_path_build_step(vs_pool, &lb_dst, -1, v_match) == false) || v_match[0]) {
312                                 break;
313                         }
314                 } while (true);
315
316                 BLI_mempool_destroy(vs_pool);
317
318                 if (v_match[0]) {
319                         BMEdgeLoopStore *el_store = MEM_callocN(sizeof(BMEdgeLoopStore), __func__);
320                         BMVert *v;
321
322                         /* build loop from edge pointers */
323                         v = v_match[0];
324                         while (true) {
325                                 LinkData *node = MEM_callocN(sizeof(*node), __func__);
326                                 node->data = v;
327                                 BLI_addhead(&el_store->verts, node);
328                                 el_store->len++;
329                                 if (v == v_src) {
330                                         break;
331                                 }
332                                 v = BM_edge_other_vert(v->e, v);
333                         }
334
335                         v = v_match[1];
336                         while (true) {
337                                 LinkData *node = MEM_callocN(sizeof(*node), __func__);
338                                 node->data = v;
339                                 BLI_addtail(&el_store->verts, node);
340                                 el_store->len++;
341                                 if (v == v_dst) {
342                                         break;
343                                 }
344                                 v = BM_edge_other_vert(v->e, v);
345                         }
346
347
348                         BLI_addtail(r_eloops, el_store);
349
350                         return true;
351                 }
352         }
353
354         return false;
355 }
356
357
358 /* -------------------------------------------------------------------- */
359 /* BM_mesh_edgeloops_xxx utility function */
360
361 void BM_mesh_edgeloops_free(ListBase *eloops)
362 {
363         BMEdgeLoopStore *el_store;
364         while ((el_store = BLI_pophead(eloops))) {
365                 BM_edgeloop_free(el_store);
366         }
367 }
368
369 void BM_mesh_edgeloops_calc_center(BMesh *bm, ListBase *eloops)
370 {
371         BMEdgeLoopStore *el_store;
372         for (el_store = eloops->first; el_store; el_store = el_store->next) {
373                 BM_edgeloop_calc_center(bm, el_store);
374         }
375 }
376
377 void BM_mesh_edgeloops_calc_normal(BMesh *bm, ListBase *eloops)
378 {
379         BMEdgeLoopStore *el_store;
380         for (el_store = eloops->first; el_store; el_store = el_store->next) {
381                 BM_edgeloop_calc_normal(bm, el_store);
382         }
383 }
384
385 void BM_mesh_edgeloops_calc_normal_aligned(BMesh *bm, ListBase *eloops, const float no_align[3])
386 {
387         BMEdgeLoopStore *el_store;
388         for (el_store = eloops->first; el_store; el_store = el_store->next) {
389                 BM_edgeloop_calc_normal_aligned(bm, el_store, no_align);
390         }
391 }
392
393 void BM_mesh_edgeloops_calc_order(BMesh *UNUSED(bm), ListBase *eloops, const bool use_normals)
394 {
395         ListBase eloops_ordered = {NULL};
396         BMEdgeLoopStore *el_store;
397         float cent[3];
398         int tot = 0;
399         zero_v3(cent);
400         /* assumes we calculated centers already */
401         for (el_store = eloops->first; el_store; el_store = el_store->next, tot++) {
402                 add_v3_v3(cent, el_store->co);
403         }
404         mul_v3_fl(cent, 1.0f / (float)tot);
405
406         /* find far outest loop */
407         {
408                 BMEdgeLoopStore *el_store_best = NULL;
409                 float len_best_sq = -1.0f;
410                 for (el_store = eloops->first; el_store; el_store = el_store->next) {
411                         const float len_sq = len_squared_v3v3(cent, el_store->co);
412                         if (len_sq > len_best_sq) {
413                                 len_best_sq = len_sq;
414                                 el_store_best = el_store;
415                         }
416                 }
417
418                 BLI_remlink(eloops, el_store_best);
419                 BLI_addtail(&eloops_ordered, el_store_best);
420         }
421
422         /* not so efficient re-ordering */
423         while (eloops->first) {
424                 BMEdgeLoopStore *el_store_best = NULL;
425                 const float *co = ((BMEdgeLoopStore *)eloops_ordered.last)->co;
426                 const float *no = ((BMEdgeLoopStore *)eloops_ordered.last)->no;
427                 float len_best_sq = FLT_MAX;
428
429                 if (use_normals)
430                         BLI_ASSERT_UNIT_V3(no);
431
432                 for (el_store = eloops->first; el_store; el_store = el_store->next) {
433                         float len_sq;
434                         if (use_normals) {
435                                 /* scale the length by how close the loops are to pointing at eachother */
436                                 float dir[3];
437                                 sub_v3_v3v3(dir, co, el_store->co);
438                                 len_sq = normalize_v3(dir);
439                                 len_sq = len_sq * ((1.0f - fabsf(dot_v3v3(dir, no))) +
440                                                    (1.0f - fabsf(dot_v3v3(dir, el_store->no))));
441                         }
442                         else {
443                                 len_sq = len_squared_v3v3(co, el_store->co);
444                         }
445
446                         if (len_sq < len_best_sq) {
447                                 len_best_sq = len_sq;
448                                 el_store_best = el_store;
449                         }
450                 }
451
452                 BLI_remlink(eloops, el_store_best);
453                 BLI_addtail(&eloops_ordered, el_store_best);
454         }
455
456         *eloops = eloops_ordered;
457 }
458
459 /* -------------------------------------------------------------------- */
460 /* BM_edgeloop_*** functions */
461
462 /* return new edgeloops */
463 BMEdgeLoopStore *BM_edgeloop_copy(BMEdgeLoopStore *el_store)
464 {
465         BMEdgeLoopStore *el_store_copy = MEM_mallocN(sizeof(*el_store), __func__);
466         *el_store_copy = *el_store;
467         BLI_duplicatelist(&el_store_copy->verts, &el_store->verts);
468         return el_store_copy;
469 }
470
471 BMEdgeLoopStore *BM_edgeloop_from_verts(BMVert **v_arr, const int v_arr_tot, bool is_closed)
472 {
473         BMEdgeLoopStore *el_store = MEM_callocN(sizeof(*el_store), __func__);
474         int i;
475         for (i = 0; i < v_arr_tot; i++) {
476                 LinkData *node = MEM_callocN(sizeof(*node), __func__);
477                 node->data = v_arr[i];
478                 BLI_addtail(&el_store->verts, node);
479         }
480         el_store->len = v_arr_tot;
481         if (is_closed) {
482                 el_store->flag |= BM_EDGELOOP_IS_CLOSED;
483         }
484         return el_store;
485 }
486
487 void BM_edgeloop_free(BMEdgeLoopStore *el_store)
488 {
489         BLI_freelistN(&el_store->verts);
490         MEM_freeN(el_store);
491 }
492
493 bool BM_edgeloop_is_closed(BMEdgeLoopStore *el_store)
494 {
495         return (el_store->flag & BM_EDGELOOP_IS_CLOSED) != 0;
496 }
497
498 ListBase *BM_edgeloop_verts_get(BMEdgeLoopStore *el_store)
499 {
500         return &el_store->verts;
501 }
502
503 int BM_edgeloop_length_get(BMEdgeLoopStore *el_store)
504 {
505         return el_store->len;
506 }
507
508 const float *BM_edgeloop_normal_get(struct BMEdgeLoopStore *el_store)
509 {
510         return el_store->no;
511 }
512
513 const float *BM_edgeloop_center_get(struct BMEdgeLoopStore *el_store)
514 {
515         return el_store->co;
516 }
517
518 #define NODE_AS_V(n)  ((BMVert *)((LinkData *)n)->data)
519 #define NODE_AS_CO(n) ((BMVert *)((LinkData *)n)->data)->co
520
521 /**
522  * edges are assigned to one vert -> the next.
523  */
524 void BM_edgeloop_edges_get(struct BMEdgeLoopStore *el_store, BMEdge **e_arr)
525 {
526         LinkData *node;
527         int i = 0;
528         for (node = el_store->verts.first; node && node->next; node = node->next) {
529                 e_arr[i++] = BM_edge_exists(NODE_AS_V(node), NODE_AS_V(node->next));
530                 BLI_assert(e_arr[i - 1] != NULL);
531         }
532
533         if (el_store->flag & BM_EDGELOOP_IS_CLOSED) {
534                 e_arr[i] = BM_edge_exists(NODE_AS_V(el_store->verts.first), NODE_AS_V(el_store->verts.last));
535                 BLI_assert(e_arr[i] != NULL);
536         }
537         BLI_assert(el_store->len == i + 1);
538 }
539
540 void BM_edgeloop_calc_center(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
541 {
542         LinkData *node_curr = el_store->verts.last;
543         LinkData *node_prev = ((LinkData *)el_store->verts.last)->prev;
544         LinkData *node_first = el_store->verts.first;
545         LinkData *node_next = node_first;
546
547         float const *v_prev = NODE_AS_CO(node_prev);
548         float const *v_curr = NODE_AS_CO(node_curr);
549         float const *v_next = NODE_AS_CO(node_next);
550
551         float totw = 0.0f;
552         float w_prev;
553
554         zero_v3(el_store->co);
555
556         w_prev = len_v3v3(v_prev, v_curr);
557         do {
558                 const float w_curr = len_v3v3(v_curr, v_next);
559                 const float w = (w_curr + w_prev);
560                 madd_v3_v3fl(el_store->co, v_curr, w);
561                 totw += w;
562                 w_prev = w_curr;
563
564
565                 node_prev = node_curr;
566                 node_curr = node_next;
567                 node_next = node_next->next;
568
569                 if (node_next == NULL) {
570                         break;
571                 }
572                 v_prev = v_curr;
573                 v_curr = v_next;
574                 v_next = NODE_AS_CO(node_next);
575         } while (1);
576
577         if (totw != 0.0f)
578                 mul_v3_fl(el_store->co, 1.0f / (float) totw);
579
580 }
581
582 bool BM_edgeloop_calc_normal(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
583 {
584         LinkData *node_curr = el_store->verts.first;
585         float const *v_prev = NODE_AS_CO(el_store->verts.last);
586         float const *v_curr = NODE_AS_CO(node_curr);
587
588         zero_v3(el_store->no);
589
590         /* Newell's Method */
591         do {
592                 add_newell_cross_v3_v3v3(el_store->no, v_prev, v_curr);
593
594                 if ((node_curr = node_curr->next)) {
595                         v_prev = v_curr;
596                         v_curr = NODE_AS_CO(node_curr);
597                 }
598                 else {
599                         break;
600                 }
601         } while (true);
602
603         if (UNLIKELY(normalize_v3(el_store->no) < EDGELOOP_EPS)) {
604                 el_store->no[2] = 1.0f; /* other axis set to 0.0 */
605                 return false;
606
607         }
608         else {
609                 return true;
610         }
611 }
612
613 /**
614  * For open loops that are straight lines,
615  * calculating the normal as if it were a polygon is meaningless.
616  *
617  * Instead use an alignment vector and calculate the normal based on that.
618  */
619 bool BM_edgeloop_calc_normal_aligned(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store, const float no_align[3])
620 {
621         LinkData *node_curr = el_store->verts.first;
622         float const *v_prev = NODE_AS_CO(el_store->verts.last);
623         float const *v_curr = NODE_AS_CO(node_curr);
624
625         zero_v3(el_store->no);
626
627         /* Own Method */
628         do {
629                 float cross[3], no[3], dir[3];
630                 sub_v3_v3v3(dir, v_curr, v_prev);
631                 cross_v3_v3v3(cross, no_align, dir);
632                 cross_v3_v3v3(no, dir, cross);
633                 add_v3_v3(el_store->no, no);
634
635                 if ((node_curr = node_curr->next)) {
636                         v_prev = v_curr;
637                         v_curr = NODE_AS_CO(node_curr);
638                 }
639                 else {
640                         break;
641                 }
642         } while (true);
643
644         if (UNLIKELY(normalize_v3(el_store->no) < EDGELOOP_EPS)) {
645                 el_store->no[2] = 1.0f; /* other axis set to 0.0 */
646                 return false;
647         }
648         else {
649                 return true;
650         }
651 }
652
653
654
655 void BM_edgeloop_flip(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
656 {
657         negate_v3(el_store->no);
658         BLI_reverselist(&el_store->verts);
659 }
660
661 void BM_edgeloop_expand(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store, int el_store_len)
662 {
663         /* first double until we are more then half as big */
664         while ((el_store->len * 2) < el_store_len) {
665                 LinkData *node_curr = el_store->verts.first;
666                 while (node_curr) {
667                         LinkData *node_curr_copy = MEM_dupallocN(node_curr);
668                         BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
669                         el_store->len++;
670                         node_curr = node_curr_copy->next;
671                 }
672         }
673
674         if (el_store->len < el_store_len) {
675                 const int step = max_ii(1, el_store->len / (el_store->len % el_store_len));
676                 LinkData *node_first = el_store->verts.first;
677                 LinkData *node_curr = node_first;
678
679                 do {
680                         LinkData *node_curr_init = node_curr;
681                         LinkData *node_curr_copy;
682                         int i = 0;
683                         LISTBASE_CIRCULAR_FORWARD_BEGIN (&el_store->verts, node_curr, node_curr_init) {
684                                 if (i++ < step) {
685                                         break;
686                                 }
687                         }
688                         LISTBASE_CIRCULAR_FORWARD_END (&el_store->verts, node_curr, node_curr_init);
689
690                         node_curr_copy = MEM_dupallocN(node_curr);
691                         BLI_insertlinkafter(&el_store->verts, node_curr, node_curr_copy);
692                         el_store->len++;
693                         node_curr = node_curr_copy->next;
694                 } while (el_store->len < el_store_len);
695         }
696
697         BLI_assert(el_store->len == el_store_len);
698 }
699
700 bool BM_edgeloop_overlap_check(struct BMEdgeLoopStore *el_store_a, struct BMEdgeLoopStore *el_store_b)
701 {
702         LinkData *node;
703
704         /* init */
705         for (node = el_store_a->verts.first; node; node = node->next) {
706                 BM_elem_flag_disable((BMVert *)node->data, BM_ELEM_INTERNAL_TAG);
707         }
708         for (node = el_store_b->verts.first; node; node = node->next) {
709                 BM_elem_flag_enable((BMVert *)node->data, BM_ELEM_INTERNAL_TAG);
710         }
711
712         /* check 'a' */
713         for (node = el_store_a->verts.first; node; node = node->next) {
714                 if (BM_elem_flag_test((BMVert *)node->data, BM_ELEM_INTERNAL_TAG)) {
715                         return true;
716                 }
717         }
718         return false;
719 }