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