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