BLI_stackdefines
[blender.git] / source / blender / bmesh / intern / bmesh_queries.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_queries.c
24  *  \ingroup bmesh
25  *
26  * This file contains functions for answering common
27  * Topological and geometric queries about a mesh, such
28  * as, "What is the angle between these two faces?" or,
29  * "How many faces are incident upon this vertex?" Tool
30  * authors should use the functions in this file instead
31  * of inspecting the mesh structure directly.
32  */
33
34 #include "MEM_guardedalloc.h"
35
36 #include "BLI_math.h"
37 #include "BLI_alloca.h"
38 #include "BLI_linklist.h"
39 #include "BLI_stackdefines.h"
40
41 #include "bmesh.h"
42 #include "intern/bmesh_private.h"
43
44 /**
45  * \brief Other Loop in Face Sharing an Edge
46  *
47  * Finds the other loop that shares \a v with \a e loop in \a f.
48  * <pre>
49  *     +----------+
50  *     |          |
51  *     |    f     |
52  *     |          |
53  *     +----------+ <-- return the face loop of this vertex.
54  *     v --> e
55  *     ^     ^ <------- These vert args define direction
56  *                      in the face to check.
57  *                      The faces loop direction is ignored.
58  * </pre>
59  *
60  * \note caller must ensure \a e is used in \a f
61  */
62 BMLoop *BM_face_other_edge_loop(BMFace *f, BMEdge *e, BMVert *v)
63 {
64         BMLoop *l = BM_face_edge_share_loop(f, e);
65         BLI_assert(l != NULL);
66         return BM_loop_other_edge_loop(l, v);
67 }
68
69 /**
70  * See #BM_face_other_edge_loop This is the same functionality
71  * to be used when the edges loop is already known.
72  */
73 BMLoop *BM_loop_other_edge_loop(BMLoop *l, BMVert *v)
74 {
75         BLI_assert(BM_vert_in_edge(l->e, v));
76         return l->v == v ? l->prev : l->next;
77 }
78
79 /**
80  * \brief Other Loop in Face Sharing a Vertex
81  *
82  * Finds the other loop in a face.
83  *
84  * This function returns a loop in \a f that shares an edge with \a v
85  * The direction is defined by \a v_prev, where the return value is
86  * the loop of what would be 'v_next'
87  * <pre>
88  *     +----------+ <-- return the face loop of this vertex.
89  *     |          |
90  *     |    f     |
91  *     |          |
92  *     +----------+
93  *     v_prev --> v
94  *     ^^^^^^     ^ <-- These vert args define direction
95  *                      in the face to check.
96  *                      The faces loop direction is ignored.
97  * </pre>
98  *
99  * \note \a v_prev and \a v _implicitly_ define an edge.
100  */
101 BMLoop *BM_face_other_vert_loop(BMFace *f, BMVert *v_prev, BMVert *v)
102 {
103         BMIter liter;
104         BMLoop *l_iter;
105
106         BLI_assert(BM_edge_exists(v_prev, v) != NULL);
107
108         BM_ITER_ELEM (l_iter, &liter, v, BM_LOOPS_OF_VERT) {
109                 if (l_iter->f == f) {
110                         break;
111                 }
112         }
113
114         if (l_iter) {
115                 if (l_iter->prev->v == v_prev) {
116                         return l_iter->next;
117                 }
118                 else if (l_iter->next->v == v_prev) {
119                         return l_iter->prev;
120                 }
121                 else {
122                         /* invalid args */
123                         BLI_assert(0);
124                         return NULL;
125                 }
126         }
127         else {
128                 /* invalid args */
129                 BLI_assert(0);
130                 return NULL;
131         }
132 }
133
134 /**
135  * \brief Other Loop in Face Sharing a Vert
136  *
137  * Finds the other loop that shares \a v with \a e loop in \a f.
138  * <pre>
139  *     +----------+ <-- return the face loop of this vertex.
140  *     |          |
141  *     |          |
142  *     |          |
143  *     +----------+ <-- This vertex defines the direction.
144  *           l    v
145  *           ^ <------- This loop defines both the face to search
146  *                      and the edge, in combination with 'v'
147  *                      The faces loop direction is ignored.
148  * </pre>
149  */
150
151 BMLoop *BM_loop_other_vert_loop(BMLoop *l, BMVert *v)
152 {
153 #if 0 /* works but slow */
154         return BM_face_other_vert_loop(l->f, BM_edge_other_vert(l->e, v), v);
155 #else
156         BMEdge *e = l->e;
157         BMVert *v_prev = BM_edge_other_vert(e, v);
158         if (l->v == v) {
159                 if (l->prev->v == v_prev) {
160                         return l->next;
161                 }
162                 else {
163                         BLI_assert(l->next->v == v_prev);
164
165                         return l->prev;
166                 }
167         }
168         else {
169                 BLI_assert(l->v == v_prev);
170
171                 if (l->prev->v == v) {
172                         return l->prev->prev;
173                 }
174                 else {
175                         BLI_assert(l->next->v == v);
176                         return l->next->next;
177                 }
178         }
179
180
181
182 #endif
183 }
184
185 /**
186  * Given 2 verts, find the smallest face they share and give back both loops.
187  */
188 BMFace *BM_vert_pair_share_face_by_len(
189         BMVert *v_a, BMVert *v_b,
190         BMLoop **r_l_a, BMLoop **r_l_b,
191         const bool allow_adjacent)
192 {
193         BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
194         BMFace *f_cur = NULL;
195
196         if (v_a->e && v_b->e) {
197                 BMIter iter;
198                 BMLoop *l_a, *l_b;
199
200                 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
201                         if ((f_cur == NULL) || (l_a->f->len < f_cur->len)) {
202                                 l_b = BM_face_vert_share_loop(l_a->f, v_b);
203                                 if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
204                                         f_cur = l_a->f;
205                                         l_cur_a = l_a;
206                                         l_cur_b = l_b;
207                                 }
208                         }
209                 }
210         }
211
212         *r_l_a = l_cur_a;
213         *r_l_b = l_cur_b;
214
215         return f_cur;
216 }
217
218 static float bm_face_calc_split_dot(BMLoop *l_a, BMLoop *l_b)
219 {
220         float no[2][3];
221
222         if ((BM_face_calc_normal_subset(l_a, l_b, no[0]) != 0.0f) &&
223             (BM_face_calc_normal_subset(l_b, l_a, no[1]) != 0.0f))
224         {
225                 return dot_v3v3(no[0], no[1]);
226         }
227         else {
228                 return -1.0f;
229         }
230 }
231
232 /**
233  * Given 2 verts, find a face they share that has the lowest angle across these verts and give back both loops.
234  *
235  * This can be better then #BM_vert_pair_share_face_by_len because concave splits are ranked lowest.
236  */
237 BMFace *BM_vert_pair_share_face_by_angle(
238         BMVert *v_a, BMVert *v_b,
239         BMLoop **r_l_a, BMLoop **r_l_b,
240         const bool allow_adjacent)
241 {
242         BMLoop *l_cur_a = NULL, *l_cur_b = NULL;
243         BMFace *f_cur = NULL;
244
245         if (v_a->e && v_b->e) {
246                 BMIter iter;
247                 BMLoop *l_a, *l_b;
248                 float dot_best = -1.0f;
249
250                 BM_ITER_ELEM (l_a, &iter, v_a, BM_LOOPS_OF_VERT) {
251                         l_b = BM_face_vert_share_loop(l_a->f, v_b);
252                         if (l_b && (allow_adjacent || !BM_loop_is_adjacent(l_a, l_b))) {
253
254                                 if (f_cur == NULL) {
255                                         f_cur = l_a->f;
256                                         l_cur_a = l_a;
257                                         l_cur_b = l_b;
258                                 }
259                                 else {
260                                         /* avoid expensive calculations if we only ever find one face */
261                                         float dot;
262                                         if (dot_best == -1.0f) {
263                                                 dot_best = bm_face_calc_split_dot(l_cur_a, l_cur_b);
264                                         }
265
266                                         dot = bm_face_calc_split_dot(l_a, l_b);
267                                         if (dot > dot_best) {
268                                                 dot_best = dot;
269
270                                                 f_cur = l_a->f;
271                                                 l_cur_a = l_a;
272                                                 l_cur_b = l_b;
273                                         }
274                                 }
275                         }
276                 }
277         }
278
279         *r_l_a = l_cur_a;
280         *r_l_b = l_cur_b;
281
282         return f_cur;
283 }
284
285
286 /**
287  * Get the first loop of a vert. Uses the same initialization code for the first loop of the
288  * iterator API
289  */
290 BMLoop *BM_vert_find_first_loop(BMVert *v)
291 {
292         BMEdge *e;
293
294         if (!v || !v->e)
295                 return NULL;
296
297         e = bmesh_disk_faceedge_find_first(v->e, v);
298
299         if (!e)
300                 return NULL;
301
302         return bmesh_radial_faceloop_find_first(e->l, v);
303 }
304
305 /**
306  * Returns true if the vertex is used in a given face.
307  */
308 bool BM_vert_in_face(BMFace *f, BMVert *v)
309 {
310         BMLoop *l_iter, *l_first;
311
312 #ifdef USE_BMESH_HOLES
313         BMLoopList *lst;
314         for (lst = f->loops.first; lst; lst = lst->next)
315 #endif
316         {
317 #ifdef USE_BMESH_HOLES
318                 l_iter = l_first = lst->first;
319 #else
320                 l_iter = l_first = f->l_first;
321 #endif
322                 do {
323                         if (l_iter->v == v) {
324                                 return true;
325                         }
326                 } while ((l_iter = l_iter->next) != l_first);
327         }
328
329         return false;
330 }
331
332 /**
333  * Compares the number of vertices in an array
334  * that appear in a given face
335  */
336 int BM_verts_in_face_count(BMFace *f, BMVert **varr, int len)
337 {
338         BMLoop *l_iter, *l_first;
339
340 #ifdef USE_BMESH_HOLES
341         BMLoopList *lst;
342 #endif
343
344         int i, count = 0;
345         
346         for (i = 0; i < len; i++) {
347                 BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
348         }
349
350 #ifdef USE_BMESH_HOLES
351         for (lst = f->loops.first; lst; lst = lst->next)
352 #endif
353         {
354
355 #ifdef USE_BMESH_HOLES
356                 l_iter = l_first = lst->first;
357 #else
358                 l_iter = l_first = f->l_first;
359 #endif
360
361                 do {
362                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
363                                 count++;
364                         }
365
366                 } while ((l_iter = l_iter->next) != l_first);
367         }
368
369         for (i = 0; i < len; i++) {
370                 BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
371         }
372
373         return count;
374 }
375
376
377 /**
378  * Return true if all verts are in the face.
379  */
380 bool BM_verts_in_face(BMFace *f, BMVert **varr, int len)
381 {
382         BMLoop *l_iter, *l_first;
383
384 #ifdef USE_BMESH_HOLES
385         BMLoopList *lst;
386 #endif
387
388         int i;
389         bool ok = true;
390
391         /* simple check, we know can't succeed */
392         if (f->len < len) {
393                 return false;
394         }
395
396         for (i = 0; i < len; i++) {
397                 BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
398         }
399
400 #ifdef USE_BMESH_HOLES
401         for (lst = f->loops.first; lst; lst = lst->next)
402 #endif
403         {
404
405 #ifdef USE_BMESH_HOLES
406                 l_iter = l_first = lst->first;
407 #else
408                 l_iter = l_first = f->l_first;
409 #endif
410
411                 do {
412                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
413                                 /* pass */
414                         }
415                         else {
416                                 ok = false;
417                                 break;
418                         }
419
420                 } while ((l_iter = l_iter->next) != l_first);
421         }
422
423         for (i = 0; i < len; i++) {
424                 BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
425         }
426
427         return ok;
428 }
429
430 /**
431  * Returns whether or not a given edge is is part of a given face.
432  */
433 bool BM_edge_in_face(BMEdge *e, BMFace *f)
434 {
435         if (e->l) {
436                 BMLoop *l_iter, *l_first;
437
438                 l_iter = l_first = e->l;
439                 do {
440                         if (l_iter->f == f) {
441                                 return true;
442                         }
443                 } while ((l_iter = l_iter->radial_next) != l_first);
444         }
445
446         return false;
447 }
448
449 /**
450  * Given a edge and a loop (assumes the edge is manifold). returns
451  * the other faces loop, sharing the same vertex.
452  *
453  * <pre>
454  * +-------------------+
455  * |                   |
456  * |                   |
457  * |l_other <-- return |
458  * +-------------------+ <-- A manifold edge between 2 faces
459  * |l    e  <-- edge   |
460  * |^ <-------- loop   |
461  * |                   |
462  * +-------------------+
463  * </pre>
464  */
465 BMLoop *BM_edge_other_loop(BMEdge *e, BMLoop *l)
466 {
467         BMLoop *l_other;
468
469         // BLI_assert(BM_edge_is_manifold(e));  // TOO strict, just check if we have another radial face
470         BLI_assert(e->l && e->l->radial_next != e->l);
471         BLI_assert(BM_vert_in_edge(e, l->v));
472
473         l_other = (l->e == e) ? l : l->prev;
474         l_other = l_other->radial_next;
475         BLI_assert(l_other->e == e);
476
477         if (l_other->v == l->v) {
478                 /* pass */
479         }
480         else if (l_other->next->v == l->v) {
481                 l_other = l_other->next;
482         }
483         else {
484                 BLI_assert(0);
485         }
486
487         return l_other;
488 }
489
490 /**
491  * Utility function to step around a fan of loops,
492  * using an edge to mark the previous side.
493  *
494  * \note all edges must be manifold,
495  * once a non manifold edge is hit, return NULL.
496  *
497  * <pre>
498  *                ,.,-->|
499  *            _,-'      |
500  *          ,'          | (notice how 'e_step'
501  *         /            |  and 'l' define the
502  *        /             |  direction the arrow
503  *       |     return   |  points).
504  *       |     loop --> |
505  * ---------------------+---------------------
506  *         ^      l --> |
507  *         |            |
508  *  assign e_step       |
509  *                      |
510  *   begin e_step ----> |
511  *                      |
512  * </pre>
513  */
514
515 BMLoop *BM_vert_step_fan_loop(BMLoop *l, BMEdge **e_step)
516 {
517         BMEdge *e_prev = *e_step;
518         BMEdge *e_next;
519         if (l->e == e_prev) {
520                 e_next = l->prev->e;
521         }
522         else if (l->prev->e == e_prev) {
523                 e_next = l->e;
524         }
525         else {
526                 BLI_assert(0);
527                 return NULL;
528         }
529
530         if (BM_edge_is_manifold(e_next)) {
531                 return BM_edge_other_loop((*e_step = e_next), l);
532         }
533         else {
534                 return NULL;
535         }
536 }
537
538
539
540 /**
541  * The function takes a vertex at the center of a fan and returns the opposite edge in the fan.
542  * All edges in the fan must be manifold, otherwise return NULL.
543  *
544  * \note This could (probably) be done more efficiently.
545  */
546 BMEdge *BM_vert_other_disk_edge(BMVert *v, BMEdge *e_first)
547 {
548         BMLoop *l_a;
549         int tot = 0;
550         int i;
551
552         BLI_assert(BM_vert_in_edge(e_first, v));
553
554         l_a = e_first->l;
555         do {
556                 l_a = BM_loop_other_vert_loop(l_a, v);
557                 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
558                 if (BM_edge_is_manifold(l_a->e)) {
559                         l_a = l_a->radial_next;
560                 }
561                 else {
562                         return NULL;
563                 }
564
565                 tot++;
566         } while (l_a != e_first->l);
567
568         /* we know the total, now loop half way */
569         tot /= 2;
570         i = 0;
571
572         l_a = e_first->l;
573         do {
574                 if (i == tot) {
575                         l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
576                         return l_a->e;
577                 }
578
579                 l_a = BM_loop_other_vert_loop(l_a, v);
580                 l_a = BM_vert_in_edge(l_a->e, v) ? l_a : l_a->prev;
581                 if (BM_edge_is_manifold(l_a->e)) {
582                         l_a = l_a->radial_next;
583                 }
584                 /* this wont have changed from the previous loop */
585
586
587                 i++;
588         } while (l_a != e_first->l);
589
590         return NULL;
591 }
592
593 /**
594  * Returns edge length
595  */
596 float BM_edge_calc_length(BMEdge *e)
597 {
598         return len_v3v3(e->v1->co, e->v2->co);
599 }
600
601 /**
602  * Returns edge length squared (for comparisons)
603  */
604 float BM_edge_calc_length_squared(BMEdge *e)
605 {
606         return len_squared_v3v3(e->v1->co, e->v2->co);
607 }
608
609 /**
610  * Utility function, since enough times we have an edge
611  * and want to access 2 connected faces.
612  *
613  * \return true when only 2 faces are found.
614  */
615 bool BM_edge_face_pair(BMEdge *e, BMFace **r_fa, BMFace **r_fb)
616 {
617         BMLoop *la, *lb;
618
619         if ((la = e->l) &&
620             (lb = la->radial_next) &&
621             (la != lb) &&
622             (lb->radial_next == la))
623         {
624                 *r_fa = la->f;
625                 *r_fb = lb->f;
626                 return true;
627         }
628         else {
629                 *r_fa = NULL;
630                 *r_fb = NULL;
631                 return false;
632         }
633 }
634
635 /**
636  * Utility function, since enough times we have an edge
637  * and want to access 2 connected loops.
638  *
639  * \return true when only 2 faces are found.
640  */
641 bool BM_edge_loop_pair(BMEdge *e, BMLoop **r_la, BMLoop **r_lb)
642 {
643         BMLoop *la, *lb;
644
645         if ((la = e->l) &&
646             (lb = la->radial_next) &&
647             (la != lb) &&
648             (lb->radial_next == la))
649         {
650                 *r_la = la;
651                 *r_lb = lb;
652                 return true;
653         }
654         else {
655                 *r_la = NULL;
656                 *r_lb = NULL;
657                 return false;
658         }
659 }
660
661 /**
662  * Fast alternative to ``(BM_vert_edge_count(v) == 2)``
663  */
664 bool BM_vert_is_edge_pair(BMVert *v)
665 {
666         BMEdge *e = v->e;
667         if (e) {
668                 const BMDiskLink *dl = bmesh_disk_edge_link_from_vert(e, v);
669                 return (dl->next == dl->prev);
670         }
671         return false;
672 }
673
674 /**
675  *      Returns the number of edges around this vertex.
676  */
677 int BM_vert_edge_count(BMVert *v)
678 {
679         return bmesh_disk_count(v);
680 }
681
682 int BM_vert_edge_count_nonwire(BMVert *v)
683 {
684         int count = 0;
685         BMIter eiter;
686         BMEdge *edge;
687         BM_ITER_ELEM (edge, &eiter, v, BM_EDGES_OF_VERT) {
688                 if (edge->l) {
689                         count++;
690                 }
691         }
692         return count;
693 }
694 /**
695  *      Returns the number of faces around this edge
696  */
697 int BM_edge_face_count(BMEdge *e)
698 {
699         int count = 0;
700
701         if (e->l) {
702                 BMLoop *l_iter;
703                 BMLoop *l_first;
704
705                 l_iter = l_first = e->l;
706
707                 do {
708                         count++;
709                 } while ((l_iter = l_iter->radial_next) != l_first);
710         }
711
712         return count;
713 }
714
715 /**
716  * Returns the number of faces around this vert
717  * length matches #BM_LOOPS_OF_VERT iterator
718  */
719 int BM_vert_face_count(BMVert *v)
720 {
721         return bmesh_disk_facevert_count(v);
722 }
723
724 /**
725  * Tests whether or not the vertex is part of a wire edge.
726  * (ie: has no faces attached to it)
727  */
728 bool BM_vert_is_wire(const BMVert *v)
729 {
730         if (v->e) {
731                 BMEdge *e_first, *e_iter;
732
733                 e_first = e_iter = v->e;
734                 do {
735                         if (e_iter->l) {
736                                 return false;
737                         }
738                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
739
740                 return true;
741         }
742         else {
743                 return false;
744         }
745 }
746
747 /**
748  * A vertex is non-manifold if it meets the following conditions:
749  * 1: Loose - (has no edges/faces incident upon it).
750  * 2: Joins two distinct regions - (two pyramids joined at the tip).
751  * 3: Is part of a an edge with more than 2 faces.
752  * 4: Is part of a wire edge.
753  */
754 bool BM_vert_is_manifold(const BMVert *v)
755 {
756         BMEdge *e, *e_old;
757         BMLoop *l;
758         int len, count, flag;
759
760         if (v->e == NULL) {
761                 /* loose vert */
762                 return false;
763         }
764
765         /* count edges while looking for non-manifold edges */
766         len = 0;
767         e_old = e = v->e;
768         do {
769                 /* loose edge or edge shared by more than two faces,
770                  * edges with 1 face user are OK, otherwise we could
771                  * use BM_edge_is_manifold() here */
772                 if (e->l == NULL || bmesh_radial_length(e->l) > 2) {
773                         return false;
774                 }
775                 len++;
776         } while ((e = bmesh_disk_edge_next(e, v)) != e_old);
777
778         count = 1;
779         flag = 1;
780         e = NULL;
781         e_old = v->e;
782         l = e_old->l;
783         while (e != e_old) {
784                 l = (l->v == v) ? l->prev : l->next;
785                 e = l->e;
786                 count++; /* count the edges */
787
788                 if (flag && l->radial_next == l) {
789                         /* we've hit the edge of an open mesh, reset once */
790                         flag = 0;
791                         count = 1;
792                         e_old = e;
793                         e = NULL;
794                         l = e_old->l;
795                 }
796                 else if (l->radial_next == l) {
797                         /* break the loop */
798                         e = e_old;
799                 }
800                 else {
801                         l = l->radial_next;
802                 }
803         }
804
805         if (count < len) {
806                 /* vert shared by multiple regions */
807                 return false;
808         }
809
810         return true;
811 }
812
813 /**
814  * Check if the edge is convex or concave
815  * (depends on face winding)
816  */
817 bool BM_edge_is_convex(const BMEdge *e)
818 {
819         if (BM_edge_is_manifold(e)) {
820                 BMLoop *l1 = e->l;
821                 BMLoop *l2 = e->l->radial_next;
822                 if (!equals_v3v3(l1->f->no, l2->f->no)) {
823                         float cross[3];
824                         float l_dir[3];
825                         cross_v3_v3v3(cross, l1->f->no, l2->f->no);
826                         /* we assume contiguous normals, otherwise the result isn't meaningful */
827                         sub_v3_v3v3(l_dir, l1->next->v->co, l1->v->co);
828                         return (dot_v3v3(l_dir, cross) > 0.0f);
829                 }
830         }
831         return true;
832 }
833
834 bool BM_vert_is_boundary(const BMVert *v)
835 {
836         if (v->e) {
837                 BMEdge *e_first, *e_iter;
838
839                 e_first = e_iter = v->e;
840                 do {
841                         if (BM_edge_is_boundary(e_iter)) {
842                                 return true;
843                         }
844                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
845
846                 return false;
847         }
848         else {
849                 return false;
850         }
851 }
852
853 /**
854  * Returns the number of faces that are adjacent to both f1 and f2,
855  * \note Could be sped up a bit by not using iterators and by tagging
856  * faces on either side, then count the tags rather then searching.
857  */
858 int BM_face_share_face_count(BMFace *f1, BMFace *f2)
859 {
860         BMIter iter1, iter2;
861         BMEdge *e;
862         BMFace *f;
863         int count = 0;
864
865         BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
866                 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
867                         if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
868                                 count++;
869                 }
870         }
871
872         return count;
873 }
874
875 /**
876  * same as #BM_face_share_face_count but returns a bool
877  */
878 bool BM_face_share_face_check(BMFace *f1, BMFace *f2)
879 {
880         BMIter iter1, iter2;
881         BMEdge *e;
882         BMFace *f;
883
884         BM_ITER_ELEM (e, &iter1, f1, BM_EDGES_OF_FACE) {
885                 BM_ITER_ELEM (f, &iter2, e, BM_FACES_OF_EDGE) {
886                         if (f != f1 && f != f2 && BM_face_share_edge_check(f, f2))
887                                 return true;
888                 }
889         }
890
891         return false;
892 }
893
894 /**
895  *  Counts the number of edges two faces share (if any)
896  */
897 int BM_face_share_edge_count(BMFace *f_a, BMFace *f_b)
898 {
899         BMLoop *l_iter;
900         BMLoop *l_first;
901         int count = 0;
902         
903         l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
904         do {
905                 if (BM_edge_in_face(l_iter->e, f_b)) {
906                         count++;
907                 }
908         } while ((l_iter = l_iter->next) != l_first);
909
910         return count;
911 }
912
913 /**
914  *  Returns true if the faces share an edge
915  */
916 bool BM_face_share_edge_check(BMFace *f1, BMFace *f2)
917 {
918         BMLoop *l_iter;
919         BMLoop *l_first;
920
921         l_iter = l_first = BM_FACE_FIRST_LOOP(f1);
922         do {
923                 if (BM_edge_in_face(l_iter->e, f2)) {
924                         return true;
925                 }
926         } while ((l_iter = l_iter->next) != l_first);
927
928         return false;
929 }
930
931 /**
932  * Test if e1 shares any faces with e2
933  */
934 bool BM_edge_share_face_check(BMEdge *e1, BMEdge *e2)
935 {
936         BMLoop *l;
937         BMFace *f;
938
939         if (e1->l && e2->l) {
940                 l = e1->l;
941                 do {
942                         f = l->f;
943                         if (BM_edge_in_face(e2, f)) {
944                                 return true;
945                         }
946                         l = l->radial_next;
947                 } while (l != e1->l);
948         }
949         return false;
950 }
951
952 /**
953  *      Test if e1 shares any quad faces with e2
954  */
955 bool BM_edge_share_quad_check(BMEdge *e1, BMEdge *e2)
956 {
957         BMLoop *l;
958         BMFace *f;
959
960         if (e1->l && e2->l) {
961                 l = e1->l;
962                 do {
963                         f = l->f;
964                         if (f->len == 4) {
965                                 if (BM_edge_in_face(e2, f)) {
966                                         return true;
967                                 }
968                         }
969                         l = l->radial_next;
970                 } while (l != e1->l);
971         }
972         return false;
973 }
974
975 /**
976  *      Tests to see if e1 shares a vertex with e2
977  */
978 bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
979 {
980         return (e1->v1 == e2->v1 ||
981                 e1->v1 == e2->v2 ||
982                 e1->v2 == e2->v1 ||
983                 e1->v2 == e2->v2);
984 }
985
986 /**
987  *      Return the shared vertex between the two edges or NULL
988  */
989 BMVert *BM_edge_share_vert(BMEdge *e1, BMEdge *e2)
990 {
991         BLI_assert(e1 != e2);
992         if (BM_vert_in_edge(e2, e1->v1)) {
993                 return e1->v1;
994         }
995         else if (BM_vert_in_edge(e2, e1->v2)) {
996                 return e1->v2;
997         }
998         else {
999                 return NULL;
1000         }
1001 }
1002
1003 /**
1004  * \brief Return the Loop Shared by Edge and Vert
1005  *
1006  * Finds the loop used which uses \a  in face loop \a l
1007  *
1008  * \note this function takes a loop rather then an edge
1009  * so we can select the face that the loop should be from.
1010  */
1011 BMLoop *BM_edge_vert_share_loop(BMLoop *l, BMVert *v)
1012 {
1013         BLI_assert(BM_vert_in_edge(l->e, v));
1014         if (l->v == v) {
1015                 return l;
1016         }
1017         else {
1018                 return l->next;
1019         }
1020 }
1021
1022 /**
1023  * \brief Return the Loop Shared by Face and Vertex
1024  *
1025  * Finds the loop used which uses \a v in face loop \a l
1026  *
1027  * \note currently this just uses simple loop in future may be sped up
1028  * using radial vars
1029  */
1030 BMLoop *BM_face_vert_share_loop(BMFace *f, BMVert *v)
1031 {
1032         BMLoop *l_first;
1033         BMLoop *l_iter;
1034
1035         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1036         do {
1037                 if (l_iter->v == v) {
1038                         return l_iter;
1039                 }
1040         } while ((l_iter = l_iter->next) != l_first);
1041
1042         return NULL;
1043 }
1044
1045 /**
1046  * \brief Return the Loop Shared by Face and Edge
1047  *
1048  * Finds the loop used which uses \a e in face loop \a l
1049  *
1050  * \note currently this just uses simple loop in future may be sped up
1051  * using radial vars
1052  */
1053 BMLoop *BM_face_edge_share_loop(BMFace *f, BMEdge *e)
1054 {
1055         BMLoop *l_first;
1056         BMLoop *l_iter;
1057
1058         l_iter = l_first = e->l;
1059         do {
1060                 if (l_iter->f == f) {
1061                         return l_iter;
1062                 }
1063         } while ((l_iter = l_iter->radial_next) != l_first);
1064
1065         return NULL;
1066 }
1067
1068 /**
1069  * Returns the verts of an edge as used in a face
1070  * if used in a face at all, otherwise just assign as used in the edge.
1071  *
1072  * Useful to get a deterministic winding order when calling
1073  * BM_face_create_ngon() on an arbitrary array of verts,
1074  * though be sure to pick an edge which has a face.
1075  *
1076  * \note This is in fact quite a simple check, mainly include this function so the intent is more obvious.
1077  * We know these 2 verts will _always_ make up the loops edge
1078  */
1079 void BM_edge_ordered_verts_ex(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2,
1080                               const BMLoop *edge_loop)
1081 {
1082         BLI_assert(edge_loop->e == edge);
1083         (void)edge; /* quiet warning in release build */
1084         *r_v1 = edge_loop->v;
1085         *r_v2 = edge_loop->next->v;
1086 }
1087
1088 void BM_edge_ordered_verts(const BMEdge *edge, BMVert **r_v1, BMVert **r_v2)
1089 {
1090         BM_edge_ordered_verts_ex(edge, r_v1, r_v2, edge->l);
1091 }
1092
1093 /**
1094  * Check if the loop is convex or concave
1095  * (depends on face normal)
1096  */
1097 bool BM_loop_is_convex(const BMLoop *l)
1098 {
1099         float e_dir_prev[3];
1100         float e_dir_next[3];
1101         float l_no[3];
1102
1103         sub_v3_v3v3(e_dir_prev, l->prev->v->co, l->v->co);
1104         sub_v3_v3v3(e_dir_next, l->next->v->co, l->v->co);
1105         cross_v3_v3v3(l_no, e_dir_next, e_dir_prev);
1106         return dot_v3v3(l_no, l->f->no) > 0.0f;
1107 }
1108
1109 /**
1110  * Calculates the angle between the previous and next loops
1111  * (angle at this loops face corner).
1112  *
1113  * \return angle in radians
1114  */
1115 float BM_loop_calc_face_angle(BMLoop *l)
1116 {
1117         return angle_v3v3v3(l->prev->v->co,
1118                             l->v->co,
1119                             l->next->v->co);
1120 }
1121
1122 /**
1123  * \brief BM_loop_calc_face_normal
1124  *
1125  * Calculate the normal at this loop corner or fallback to the face normal on straight lines.
1126  *
1127  * \param l The loop to calculate the normal at
1128  * \param r_normal Resulting normal
1129  */
1130 void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3])
1131 {
1132         if (normal_tri_v3(r_normal,
1133                           l->prev->v->co,
1134                           l->v->co,
1135                           l->next->v->co) != 0.0f)
1136         {
1137                 /* pass */
1138         }
1139         else {
1140                 copy_v3_v3(r_normal, l->f->no);
1141         }
1142 }
1143
1144 /**
1145  * \brief BM_loop_calc_face_direction
1146  *
1147  * Calculate the direction a loop is pointing.
1148  *
1149  * \param l The loop to calculate the direction at
1150  * \param r_dir Resulting direction
1151  */
1152 void BM_loop_calc_face_direction(BMLoop *l, float r_dir[3])
1153 {
1154         float v_prev[3];
1155         float v_next[3];
1156
1157         sub_v3_v3v3(v_prev, l->v->co, l->prev->v->co);
1158         sub_v3_v3v3(v_next, l->next->v->co, l->v->co);
1159
1160         normalize_v3(v_prev);
1161         normalize_v3(v_next);
1162
1163         add_v3_v3v3(r_dir, v_prev, v_next);
1164         normalize_v3(r_dir);
1165 }
1166
1167 /**
1168  * \brief BM_loop_calc_face_tangent
1169  *
1170  * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1171  * This vector always points inward into the face.
1172  *
1173  * \param l The loop to calculate the tangent at
1174  * \param r_tangent Resulting tangent
1175  */
1176 void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3])
1177 {
1178         float v_prev[3];
1179         float v_next[3];
1180         float dir[3];
1181
1182         sub_v3_v3v3(v_prev, l->prev->v->co, l->v->co);
1183         sub_v3_v3v3(v_next, l->v->co, l->next->v->co);
1184
1185         normalize_v3(v_prev);
1186         normalize_v3(v_next);
1187         add_v3_v3v3(dir, v_prev, v_next);
1188
1189         if (compare_v3v3(v_prev, v_next, FLT_EPSILON * 10.0f) == false) {
1190                 float nor[3]; /* for this purpose doesn't need to be normalized */
1191                 cross_v3_v3v3(nor, v_prev, v_next);
1192                 /* concave face check */
1193                 if (UNLIKELY(dot_v3v3(nor, l->f->no) < 0.0f)) {
1194                         negate_v3(nor);
1195                 }
1196                 cross_v3_v3v3(r_tangent, dir, nor);
1197         }
1198         else {
1199                 /* prev/next are the same - compare with face normal since we don't have one */
1200                 cross_v3_v3v3(r_tangent, dir, l->f->no);
1201         }
1202
1203         normalize_v3(r_tangent);
1204 }
1205
1206 /**
1207  * \brief BMESH EDGE/FACE ANGLE
1208  *
1209  *  Calculates the angle between two faces.
1210  *  Assumes the face normals are correct.
1211  *
1212  * \return angle in radians
1213  */
1214 float BM_edge_calc_face_angle_ex(const BMEdge *e, const float fallback)
1215 {
1216         if (BM_edge_is_manifold(e)) {
1217                 const BMLoop *l1 = e->l;
1218                 const BMLoop *l2 = e->l->radial_next;
1219                 return angle_normalized_v3v3(l1->f->no, l2->f->no);
1220         }
1221         else {
1222                 return fallback;
1223         }
1224 }
1225 float BM_edge_calc_face_angle(const BMEdge *e)
1226 {
1227         return BM_edge_calc_face_angle_ex(e, DEG2RADF(90.0f));
1228 }
1229
1230 /**
1231  * \brief BMESH EDGE/FACE ANGLE
1232  *
1233  *  Calculates the angle between two faces.
1234  *  Assumes the face normals are correct.
1235  *
1236  * \return angle in radians
1237  */
1238 float BM_edge_calc_face_angle_signed_ex(const BMEdge *e, const float fallback)
1239 {
1240         if (BM_edge_is_manifold(e)) {
1241                 BMLoop *l1 = e->l;
1242                 BMLoop *l2 = e->l->radial_next;
1243                 const float angle = angle_normalized_v3v3(l1->f->no, l2->f->no);
1244                 return BM_edge_is_convex(e) ? angle : -angle;
1245         }
1246         else {
1247                 return fallback;
1248         }
1249 }
1250 float BM_edge_calc_face_angle_signed(const BMEdge *e)
1251 {
1252         return BM_edge_calc_face_angle_signed_ex(e, DEG2RADF(90.0f));
1253 }
1254
1255 /**
1256  * \brief BMESH EDGE/FACE TANGENT
1257  *
1258  * Calculate the tangent at this loop corner or fallback to the face normal on straight lines.
1259  * This vector always points inward into the face.
1260  *
1261  * \brief BM_edge_calc_face_tangent
1262  * \param e
1263  * \param e_loop The loop to calculate the tangent at,
1264  * used to get the face and winding direction.
1265  * \param r_tangent The loop corner tangent to set
1266  */
1267
1268 void BM_edge_calc_face_tangent(const BMEdge *e, const BMLoop *e_loop, float r_tangent[3])
1269 {
1270         float tvec[3];
1271         BMVert *v1, *v2;
1272         BM_edge_ordered_verts_ex(e, &v1, &v2, e_loop);
1273
1274         sub_v3_v3v3(tvec, v1->co, v2->co); /* use for temp storage */
1275         /* note, we could average the tangents of both loops,
1276          * for non flat ngons it will give a better direction */
1277         cross_v3_v3v3(r_tangent, tvec, e_loop->f->no);
1278         normalize_v3(r_tangent);
1279 }
1280
1281 /**
1282  * \brief BMESH VERT/EDGE ANGLE
1283  *
1284  * Calculates the angle a verts 2 edges.
1285  *
1286  * \returns the angle in radians
1287  */
1288 float BM_vert_calc_edge_angle(BMVert *v)
1289 {
1290         BMEdge *e1, *e2;
1291
1292         /* saves BM_vert_edge_count(v) and and edge iterator,
1293          * get the edges and count them both at once */
1294
1295         if ((e1 = v->e) &&
1296             (e2 =  bmesh_disk_edge_next(e1, v)) &&
1297             /* make sure we come full circle and only have 2 connected edges */
1298             (e1 == bmesh_disk_edge_next(e2, v)))
1299         {
1300                 BMVert *v1 = BM_edge_other_vert(e1, v);
1301                 BMVert *v2 = BM_edge_other_vert(e2, v);
1302
1303                 return (float)M_PI - angle_v3v3v3(v1->co, v->co, v2->co);
1304         }
1305         else {
1306                 return DEG2RADF(90.0f);
1307         }
1308 }
1309
1310 /**
1311  * \note this isn't optimal to run on an array of verts,
1312  * see 'solidify_add_thickness' for a function which runs on an array.
1313  */
1314 float BM_vert_calc_shell_factor(BMVert *v)
1315 {
1316         BMIter iter;
1317         BMLoop *l;
1318         float accum_shell = 0.0f;
1319         float accum_angle = 0.0f;
1320
1321         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
1322                 const float face_angle = BM_loop_calc_face_angle(l);
1323                 accum_shell += shell_v3v3_normalized_to_dist(v->no, l->f->no) * face_angle;
1324                 accum_angle += face_angle;
1325         }
1326
1327         if (accum_angle != 0.0f) {
1328                 return accum_shell / accum_angle;
1329         }
1330         else {
1331                 return 1.0f;
1332         }
1333 }
1334 /* alternate version of #BM_vert_calc_shell_factor which only
1335  * uses 'hflag' faces, but falls back to all if none found. */
1336 float BM_vert_calc_shell_factor_ex(BMVert *v, const char hflag)
1337 {
1338         BMIter iter;
1339         BMLoop *l;
1340         float accum_shell = 0.0f;
1341         float accum_angle = 0.0f;
1342         int tot_sel = 0, tot = 0;
1343
1344         BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) {
1345                 if (BM_elem_flag_test(l->f, hflag)) {  /* <-- main difference to BM_vert_calc_shell_factor! */
1346                         const float face_angle = BM_loop_calc_face_angle(l);
1347                         accum_shell += shell_v3v3_normalized_to_dist(v->no, l->f->no) * face_angle;
1348                         accum_angle += face_angle;
1349                         tot_sel++;
1350                 }
1351                 tot++;
1352         }
1353
1354         if (accum_angle != 0.0f) {
1355                 return accum_shell / accum_angle;
1356         }
1357         else {
1358                 /* other main difference from BM_vert_calc_shell_factor! */
1359                 if (tot != 0 && tot_sel == 0) {
1360                         /* none selected, so use all */
1361                         return BM_vert_calc_shell_factor(v);
1362                 }
1363                 else {
1364                         return 1.0f;
1365                 }
1366         }
1367 }
1368
1369 /**
1370  * \note quite an obscure function.
1371  * used in bmesh operators that have a relative scale options,
1372  */
1373 float BM_vert_calc_mean_tagged_edge_length(BMVert *v)
1374 {
1375         BMIter iter;
1376         BMEdge *e;
1377         int tot;
1378         float length = 0.0f;
1379
1380         BM_ITER_ELEM_INDEX (e, &iter, v, BM_EDGES_OF_VERT, tot) {
1381                 BMVert *v_other = BM_edge_other_vert(e, v);
1382                 if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) {
1383                         length += BM_edge_calc_length(e);
1384                 }
1385         }
1386
1387         if (tot) {
1388                 return length / (float)tot;
1389         }
1390         else {
1391                 return 0.0f;
1392         }
1393 }
1394
1395
1396 /**
1397  * Returns the loop of the shortest edge in f.
1398  */
1399 BMLoop *BM_face_find_shortest_loop(BMFace *f)
1400 {
1401         BMLoop *shortest_loop = NULL;
1402         float shortest_len = FLT_MAX;
1403
1404         BMLoop *l_iter;
1405         BMLoop *l_first;
1406
1407         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1408
1409         do {
1410                 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1411                 if (len_sq <= shortest_len) {
1412                         shortest_loop = l_iter;
1413                         shortest_len = len_sq;
1414                 }
1415         } while ((l_iter = l_iter->next) != l_first);
1416
1417         return shortest_loop;
1418 }
1419
1420 /**
1421  * Returns the loop of the longest edge in f.
1422  */
1423 BMLoop *BM_face_find_longest_loop(BMFace *f)
1424 {
1425         BMLoop *longest_loop = NULL;
1426         float len_max_sq = 0.0f;
1427
1428         BMLoop *l_iter;
1429         BMLoop *l_first;
1430
1431         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1432
1433         do {
1434                 const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co);
1435                 if (len_sq >= len_max_sq) {
1436                         longest_loop = l_iter;
1437                         len_max_sq = len_sq;
1438                 }
1439         } while ((l_iter = l_iter->next) != l_first);
1440
1441         return longest_loop;
1442 }
1443
1444 /**
1445  * Returns the edge existing between \a v_a and \a v_b, or NULL if there isn't one.
1446  *
1447  * \note multiple edges may exist between any two vertices, and therefore
1448  * this function only returns the first one found.
1449  */
1450 #if 0
1451 BMEdge *BM_edge_exists(BMVert *v_a, BMVert *v_b)
1452 {
1453         BMIter iter;
1454         BMEdge *e;
1455
1456
1457         BLI_assert(v_a != v_b);
1458         BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
1459
1460         BM_ITER_ELEM (e, &iter, v_a, BM_EDGES_OF_VERT) {
1461                 if (e->v1 == v_b || e->v2 == v_b)
1462                         return e;
1463         }
1464
1465         return NULL;
1466 }
1467 #else
1468 BMEdge *BM_edge_exists(BMVert *v_a, BMVert *v_b)
1469 {
1470         /* speedup by looping over both edges verts
1471          * where one vert may connect to many edges but not the other. */
1472
1473         BMEdge *e_a, *e_b;
1474
1475         BLI_assert(v_a != v_b);
1476         BLI_assert(v_a->head.htype == BM_VERT && v_b->head.htype == BM_VERT);
1477
1478         if ((e_a = v_a->e) && (e_b = v_b->e)) {
1479                 BMEdge *e_a_iter = e_a, *e_b_iter = e_b;
1480
1481                 do {
1482                         if (BM_vert_in_edge(e_a_iter, v_b)) {
1483                                 return e_a_iter;
1484                         }
1485                         if (BM_vert_in_edge(e_b_iter, v_a)) {
1486                                 return e_b_iter;
1487                         }
1488                 } while (((e_a_iter = bmesh_disk_edge_next(e_a_iter, v_a)) != e_a) &&
1489                          ((e_b_iter = bmesh_disk_edge_next(e_b_iter, v_b)) != e_b));
1490         }
1491
1492         return NULL;
1493 }
1494 #endif
1495
1496 /**
1497  * Returns an edge sharing the same vertices as this one.
1498  * This isn't an invalid state but tools should clean up these cases before
1499  * returning the mesh to the user.
1500  */
1501 BMEdge *BM_edge_find_double(BMEdge *e)
1502 {
1503         BMVert *v       = e->v1;
1504         BMVert *v_other = e->v2;
1505
1506         BMEdge *e_iter;
1507
1508         e_iter = e;
1509         while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e) {
1510                 if (UNLIKELY(BM_vert_in_edge(e_iter, v_other))) {
1511                         return e_iter;
1512                 }
1513         }
1514
1515         return NULL;
1516 }
1517
1518 /**
1519  * Given a set of vertices (varr), find out if
1520  * there is a face with exactly those vertices
1521  * (and only those vertices).
1522  *
1523  * \note there used to be a BM_face_exists_overlap function that checks for partial overlap.
1524  */
1525 bool BM_face_exists(BMVert **varr, int len, BMFace **r_existface)
1526 {
1527         BMVert *v_search = varr[0];  /* we can search any of the verts in the array */
1528         BMIter liter;
1529         BMLoop *l_search;
1530
1531
1532 #if 0
1533         BM_ITER_ELEM (f, &viter, v_search, BM_FACES_OF_VERT) {
1534                 if (f->len == len) {
1535                         if (BM_verts_in_face(f, varr, len)) {
1536                                 if (r_existface) {
1537                                         *r_existface = f;
1538                                 }
1539                                 return true;
1540                         }
1541                 }
1542         }
1543
1544         if (r_existface) {
1545                 *r_existface = NULL;
1546         }
1547         return false;
1548
1549 #else
1550
1551         /* faster to do the flagging once, and inline */
1552         bool is_init = false;
1553         bool is_found = false;
1554         int i;
1555
1556
1557         BM_ITER_ELEM (l_search, &liter, v_search, BM_LOOPS_OF_VERT) {
1558                 if (l_search->f->len == len) {
1559                         if (is_init == false) {
1560                                 is_init = true;
1561                                 for (i = 0; i < len; i++) {
1562                                         BLI_assert(!BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP));
1563                                         BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
1564                                 }
1565                         }
1566
1567                         is_found = true;
1568
1569                         {
1570                                 BMLoop *l_iter;
1571
1572                                 /* skip ourselves */
1573                                 l_iter  = l_search->next;
1574
1575                                 do {
1576                                         if (!BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP)) {
1577                                                 is_found = false;
1578                                                 break;
1579                                         }
1580                                 } while ((l_iter = l_iter->next) != l_search);
1581                         }
1582
1583                         if (is_found) {
1584                                 if (r_existface) {
1585                                         *r_existface = l_search->f;
1586                                 }
1587                                 break;
1588                         }
1589                 }
1590         }
1591
1592         if (is_found == false) {
1593                 if (r_existface) {
1594                         *r_existface = NULL;
1595                 }
1596         }
1597
1598         if (is_init == true) {
1599                 for (i = 0; i < len; i++) {
1600                         BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
1601                 }
1602         }
1603
1604         return is_found;
1605 #endif
1606 }
1607
1608
1609 /**
1610  * Given a set of vertices and edges (\a varr, \a earr), find out if
1611  * all those vertices are filled in by existing faces that _only_ use those vertices.
1612  *
1613  * This is for use in cases where creating a face is possible but would result in
1614  * many overlapping faces.
1615  *
1616  * An example of how this is used: when 2 tri's are selected that share an edge,
1617  * pressing Fkey would make a new overlapping quad (without a check like this)
1618  *
1619  * \a earr and \a varr can be in any order, however they _must_ form a closed loop.
1620  */
1621 bool BM_face_exists_multi(BMVert **varr, BMEdge **earr, int len)
1622 {
1623         BMFace *f;
1624         BMEdge *e;
1625         BMVert *v;
1626         bool ok;
1627         int tot_tag;
1628
1629         BMIter fiter;
1630         BMIter viter;
1631
1632         int i;
1633
1634         for (i = 0; i < len; i++) {
1635                 /* save some time by looping over edge faces rather then vert faces
1636                  * will still loop over some faces twice but not as many */
1637                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1638                         BM_elem_flag_disable(f, BM_ELEM_INTERNAL_TAG);
1639                         BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1640                                 BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
1641                         }
1642                 }
1643
1644                 /* clear all edge tags */
1645                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1646                         BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
1647                 }
1648         }
1649
1650         /* now tag all verts and edges in the boundary array as true so
1651          * we can know if a face-vert is from our array */
1652         for (i = 0; i < len; i++) {
1653                 BM_elem_flag_enable(varr[i], BM_ELEM_INTERNAL_TAG);
1654                 BM_elem_flag_enable(earr[i], BM_ELEM_INTERNAL_TAG);
1655         }
1656
1657
1658         /* so! boundary is tagged, everything else cleared */
1659
1660
1661         /* 1) tag all faces connected to edges - if all their verts are boundary */
1662         tot_tag = 0;
1663         for (i = 0; i < len; i++) {
1664                 BM_ITER_ELEM (f, &fiter, earr[i], BM_FACES_OF_EDGE) {
1665                         if (!BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1666                                 ok = true;
1667                                 BM_ITER_ELEM (v, &viter, f, BM_VERTS_OF_FACE) {
1668                                         if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
1669                                                 ok = false;
1670                                                 break;
1671                                         }
1672                                 }
1673
1674                                 if (ok) {
1675                                         /* we only use boundary verts */
1676                                         BM_elem_flag_enable(f, BM_ELEM_INTERNAL_TAG);
1677                                         tot_tag++;
1678                                 }
1679                         }
1680                         else {
1681                                 /* we already found! */
1682                         }
1683                 }
1684         }
1685
1686         if (tot_tag == 0) {
1687                 /* no faces use only boundary verts, quit early */
1688                 return false;
1689         }
1690
1691         /* 2) loop over non-boundary edges that use boundary verts,
1692          *    check each have 2 tagges faces connected (faces that only use 'varr' verts) */
1693         ok = true;
1694         for (i = 0; i < len; i++) {
1695                 BM_ITER_ELEM (e, &fiter, varr[i], BM_EDGES_OF_VERT) {
1696
1697                         if (/* non-boundary edge */
1698                             BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG) == false &&
1699                             /* ...using boundary verts */
1700                             BM_elem_flag_test(e->v1, BM_ELEM_INTERNAL_TAG) == true &&
1701                             BM_elem_flag_test(e->v2, BM_ELEM_INTERNAL_TAG) == true)
1702                         {
1703                                 int tot_face_tag = 0;
1704                                 BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
1705                                         if (BM_elem_flag_test(f, BM_ELEM_INTERNAL_TAG)) {
1706                                                 tot_face_tag++;
1707                                         }
1708                                 }
1709
1710                                 if (tot_face_tag != 2) {
1711                                         ok = false;
1712                                         break;
1713                                 }
1714
1715                         }
1716                 }
1717
1718                 if (ok == false) {
1719                         break;
1720                 }
1721         }
1722
1723         return ok;
1724 }
1725
1726 /* same as 'BM_face_exists_multi' but built vert array from edges */
1727 bool BM_face_exists_multi_edge(BMEdge **earr, int len)
1728 {
1729         BMVert **varr = BLI_array_alloca(varr, len);
1730
1731         bool ok;
1732         int i, i_next;
1733
1734         /* first check if verts have edges, if not we can bail out early */
1735         ok = true;
1736         for (i = len - 1, i_next = 0; i_next < len; (i = i_next++)) {
1737                 if (!(varr[i] = BM_edge_share_vert(earr[i], earr[i_next]))) {
1738                         ok = false;
1739                         break;
1740                 }
1741         }
1742
1743         if (ok == false) {
1744                 BMESH_ASSERT(0);
1745                 return false;
1746         }
1747
1748         ok = BM_face_exists_multi(varr, earr, len);
1749
1750         return ok;
1751 }
1752
1753
1754 /**
1755  * Given a set of vertices (varr), find out if
1756  * all those vertices overlap an existing face.
1757  *
1758  * \note The face may contain other verts \b not in \a varr.
1759  *
1760  * \note Its possible there are more then one overlapping faces,
1761  * in this case the first one found will be assigned to \a r_f_overlap.
1762  *
1763  * \param varr  Array of unordered verts.
1764  * \param len  \a varr array length.
1765  * \param r_f_overlap  The overlapping face to return.
1766  * \return Success
1767  */
1768
1769 bool BM_face_exists_overlap(BMVert **varr, const int len, BMFace **r_f_overlap)
1770 {
1771         BMIter viter;
1772         BMFace *f;
1773         int i;
1774         bool is_overlap = false;
1775         LinkNode *f_lnk = NULL;
1776
1777         if (r_f_overlap) {
1778                 *r_f_overlap = NULL;
1779         }
1780
1781 #ifdef DEBUG
1782         /* check flag isn't already set */
1783         for (i = 0; i < len; i++) {
1784                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1785                         BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
1786                 }
1787         }
1788 #endif
1789
1790         for (i = 0; i < len; i++) {
1791                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1792                         if (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0) {
1793                                 if (len <= BM_verts_in_face_count(f, varr, len)) {
1794                                         if (r_f_overlap)
1795                                                 *r_f_overlap = f;
1796
1797                                         is_overlap = true;
1798                                         break;
1799                                 }
1800
1801                                 BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
1802                                 BLI_linklist_prepend_alloca(&f_lnk, f);
1803                         }
1804                 }
1805         }
1806
1807         for (; f_lnk; f_lnk = f_lnk->next) {
1808                 BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
1809         }
1810
1811         return is_overlap;
1812 }
1813
1814 /**
1815  * Given a set of vertices (varr), find out if
1816  * there is a face that uses vertices only from this list
1817  * (that the face is a subset or made from the vertices given).
1818  *
1819  * \param varr  Array of unordered verts.
1820  * \param len  varr array length.
1821  */
1822 bool BM_face_exists_overlap_subset(BMVert **varr, const int len)
1823 {
1824         BMIter viter;
1825         BMFace *f;
1826         int i;
1827         bool is_init = false;
1828         bool is_overlap = false;
1829         LinkNode *f_lnk = NULL;
1830
1831 #ifdef DEBUG
1832         /* check flag isn't already set */
1833         for (i = 0; i < len; i++) {
1834                 BLI_assert(BM_ELEM_API_FLAG_TEST(varr[i], _FLAG_OVERLAP) == 0);
1835                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1836                         BLI_assert(BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0);
1837                 }
1838         }
1839 #endif
1840
1841         for (i = 0; i < len; i++) {
1842                 BM_ITER_ELEM (f, &viter, varr[i], BM_FACES_OF_VERT) {
1843                         if ((f->len <= len) && (BM_ELEM_API_FLAG_TEST(f, _FLAG_OVERLAP) == 0)) {
1844                                 /* check if all vers in this face are flagged*/
1845                                 BMLoop *l_iter, *l_first;
1846
1847                                 if (is_init == false) {
1848                                         is_init = true;
1849                                         for (i = 0; i < len; i++) {
1850                                                 BM_ELEM_API_FLAG_ENABLE(varr[i], _FLAG_OVERLAP);
1851                                         }
1852                                 }
1853
1854                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1855                                 is_overlap = true;
1856                                 do {
1857                                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_OVERLAP) == 0) {
1858                                                 is_overlap = false;
1859                                                 break;
1860                                         }
1861                                 } while ((l_iter = l_iter->next) != l_first);
1862
1863                                 if (is_overlap) {
1864                                         break;
1865                                 }
1866
1867                                 BM_ELEM_API_FLAG_ENABLE(f, _FLAG_OVERLAP);
1868                                 BLI_linklist_prepend_alloca(&f_lnk, f);
1869                         }
1870                 }
1871         }
1872
1873         if (is_init == true) {
1874                 for (i = 0; i < len; i++) {
1875                         BM_ELEM_API_FLAG_DISABLE(varr[i], _FLAG_OVERLAP);
1876                 }
1877         }
1878
1879         for (; f_lnk; f_lnk = f_lnk->next) {
1880                 BM_ELEM_API_FLAG_DISABLE((BMFace *)f_lnk->link, _FLAG_OVERLAP);
1881         }
1882
1883         return is_overlap;
1884 }
1885
1886 bool BM_vert_is_all_edge_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
1887 {
1888         if (v->e) {
1889                 BMEdge *e_other;
1890                 BMIter eiter;
1891
1892                 BM_ITER_ELEM (e_other, &eiter, (BMVert *)v, BM_EDGES_OF_VERT) {
1893                         if (!respect_hide || !BM_elem_flag_test(e_other, BM_ELEM_HIDDEN)) {
1894                                 if (!BM_elem_flag_test(e_other, hflag)) {
1895                                         return false;
1896                                 }
1897                         }
1898                 }
1899         }
1900
1901         return true;
1902 }
1903
1904 bool BM_vert_is_all_face_flag_test(const BMVert *v, const char hflag, const bool respect_hide)
1905 {
1906         if (v->e) {
1907                 BMEdge *f_other;
1908                 BMIter fiter;
1909
1910                 BM_ITER_ELEM (f_other, &fiter, (BMVert *)v, BM_FACES_OF_VERT) {
1911                         if (!respect_hide || !BM_elem_flag_test(f_other, BM_ELEM_HIDDEN)) {
1912                                 if (!BM_elem_flag_test(f_other, hflag)) {
1913                                         return false;
1914                                 }
1915                         }
1916                 }
1917         }
1918
1919         return true;
1920 }
1921
1922
1923 bool BM_edge_is_all_face_flag_test(const BMEdge *e, const char hflag, const bool respect_hide)
1924 {
1925         if (e->l) {
1926                 BMLoop *l_iter, *l_first;
1927
1928                 l_iter = l_first = e->l;
1929                 do {
1930                         if (!respect_hide || !BM_elem_flag_test(l_iter->f, BM_ELEM_HIDDEN)) {
1931                                 if (!BM_elem_flag_test(l_iter->f, hflag)) {
1932                                         return false;
1933                                 }
1934                         }
1935                 } while ((l_iter = l_iter->radial_next) != l_first);
1936         }
1937
1938         return true;
1939 }
1940
1941 /* convenience functions for checking flags */
1942 bool BM_edge_is_any_vert_flag_test(const BMEdge *e, const char hflag)
1943 {
1944         return (BM_elem_flag_test(e->v1, hflag) ||
1945                 BM_elem_flag_test(e->v2, hflag));
1946 }
1947
1948 bool BM_face_is_any_vert_flag_test(const BMFace *f, const char hflag)
1949 {
1950         BMLoop *l_iter;
1951         BMLoop *l_first;
1952
1953         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1954         do {
1955                 if (BM_elem_flag_test(l_iter->v, hflag)) {
1956                         return true;
1957                 }
1958         } while ((l_iter = l_iter->next) != l_first);
1959         return false;
1960 }
1961
1962 bool BM_face_is_any_edge_flag_test(const BMFace *f, const char hflag)
1963 {
1964         BMLoop *l_iter;
1965         BMLoop *l_first;
1966
1967         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1968         do {
1969                 if (BM_elem_flag_test(l_iter->e, hflag)) {
1970                         return true;
1971                 }
1972         } while ((l_iter = l_iter->next) != l_first);
1973         return false;
1974 }
1975
1976 /**
1977  * Use within assert's to check normals are valid.
1978  */
1979 bool BM_face_is_normal_valid(const BMFace *f)
1980 {
1981         const float eps = 0.0001f;
1982         float no[3];
1983
1984         BM_face_calc_normal(f, no);
1985         return len_squared_v3v3(no, f->no) < (eps * eps);
1986 }
1987
1988 static void bm_mesh_calc_volume_face(const BMFace *f, float *r_vol)
1989 {
1990         const int tottri = f->len - 2;
1991         BMLoop **loops = BLI_array_alloca(loops, f->len);
1992         unsigned int (*index)[3] = BLI_array_alloca(index, tottri);
1993         int j;
1994
1995         BM_face_calc_tessellation(f, loops, index);
1996
1997         for (j = 0; j < tottri; j++) {
1998                 const float *p1 = loops[index[j][0]]->v->co;
1999                 const float *p2 = loops[index[j][1]]->v->co;
2000                 const float *p3 = loops[index[j][2]]->v->co;
2001
2002                 /* co1.dot(co2.cross(co3)) / 6.0 */
2003                 float cross[3];
2004                 cross_v3_v3v3(cross, p2, p3);
2005                 *r_vol += (1.0f / 6.0f) * dot_v3v3(p1, cross);
2006         }
2007 }
2008 float BM_mesh_calc_volume(BMesh *bm, bool is_signed)
2009 {
2010         /* warning, calls own tessellation function, may be slow */
2011         float vol = 0.0f;
2012         BMFace *f;
2013         BMIter fiter;
2014
2015         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
2016                 bm_mesh_calc_volume_face(f, &vol);
2017         }
2018
2019         if (is_signed == false) {
2020                 vol = fabsf(vol);
2021         }
2022
2023         return vol;
2024 }
2025
2026 /* note, almost duplicate of BM_mesh_calc_edge_groups, keep in sync */
2027 /**
2028  * Calculate isolated groups of faces with optional filtering.
2029  *
2030  * \param bm  the BMesh.
2031  * \param r_groups_array  Array of ints to fill in, length of bm->totface
2032  *        (or when hflag_test is set, the number of flagged faces).
2033  * \param r_group_index  index, length pairs into \a r_groups_array, size of return value
2034  *        int pairs: (array_start, array_length).
2035  * \param filter_fn  Filter the edges or verts we step over (depends on \a htype_step)
2036  *        as to which types we deal with.
2037  * \param user_data  Optional user data for \a filter_fn, can be NULL.
2038  * \param hflag_test  Optional flag to test faces,
2039  *        use to exclude faces from the calculation, 0 for all faces.
2040  * \param htype_step  BM_VERT to walk over face-verts, BM_EDGE to walk over faces edges
2041  *        (having both set is supported too).
2042  * \return The number of groups found.
2043  */
2044 int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
2045                              BMElemFilterFunc filter_fn, void *user_data,
2046                              const char hflag_test, const char htype_step)
2047 {
2048 #ifdef DEBUG
2049         int group_index_len = 1;
2050 #else
2051         int group_index_len = 32;
2052 #endif
2053
2054         int (*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
2055
2056         int *group_array = r_groups_array;
2057         STACK_DECLARE(group_array);
2058
2059         int group_curr = 0;
2060
2061         unsigned int tot_faces = 0;
2062         unsigned int tot_touch = 0;
2063
2064         BMFace **stack;
2065         STACK_DECLARE(stack);
2066
2067         BMIter iter;
2068         BMFace *f;
2069         int i;
2070
2071         STACK_INIT(group_array, bm->totface);
2072
2073         BLI_assert(((htype_step & ~(BM_VERT | BM_EDGE)) == 0) && (htype_step != 0));
2074
2075         /* init the array */
2076         BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
2077                 if ((hflag_test == 0) || BM_elem_flag_test(f, hflag_test)) {
2078                         tot_faces++;
2079                         BM_elem_flag_disable(f, BM_ELEM_TAG);
2080                 }
2081                 else {
2082                         /* never walk over tagged */
2083                         BM_elem_flag_enable(f, BM_ELEM_TAG);
2084                 }
2085
2086                 BM_elem_index_set(f, i); /* set_inline */
2087         }
2088         bm->elem_index_dirty &= ~BM_FACE;
2089
2090         /* detect groups */
2091         stack = MEM_mallocN(sizeof(*stack) * tot_faces, __func__);
2092
2093         while (tot_touch != tot_faces) {
2094                 int *group_item;
2095                 bool ok = false;
2096
2097                 BLI_assert(tot_touch < tot_faces);
2098
2099                 STACK_INIT(stack, tot_faces);
2100
2101                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
2102                         if (BM_elem_flag_test(f, BM_ELEM_TAG) == false) {
2103                                 BM_elem_flag_enable(f, BM_ELEM_TAG);
2104                                 STACK_PUSH(stack, f);
2105                                 ok = true;
2106                                 break;
2107                         }
2108                 }
2109
2110                 BLI_assert(ok == true);
2111
2112                 /* manage arrays */
2113                 if (group_index_len == group_curr) {
2114                         group_index_len *= 2;
2115                         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
2116                 }
2117
2118                 group_item = group_index[group_curr];
2119                 group_item[0] = STACK_SIZE(group_array);
2120                 group_item[1] = 0;
2121
2122                 while ((f = STACK_POP(stack))) {
2123                         BMLoop *l_iter, *l_first;
2124
2125                         /* add face */
2126                         STACK_PUSH(group_array, BM_elem_index_get(f));
2127                         tot_touch++;
2128                         group_item[1]++;
2129                         /* done */
2130
2131                         if (htype_step & BM_EDGE) {
2132                                 /* search for other faces */
2133                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2134                                 do {
2135                                         BMLoop *l_radial_iter = l_iter->radial_next;
2136                                         if ((l_radial_iter != l_iter) &&
2137                                             ((filter_fn == NULL) || filter_fn((BMElem *)l_iter->e, user_data)))
2138                                         {
2139                                                 do {
2140                                                         BMFace *f_other = l_radial_iter->f;
2141                                                         if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2142                                                                 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
2143                                                                 STACK_PUSH(stack, f_other);
2144                                                         }
2145                                                 } while ((l_radial_iter = l_radial_iter->radial_next) != l_iter);
2146                                         }
2147                                 } while ((l_iter = l_iter->next) != l_first);
2148                         }
2149
2150                         if (htype_step & BM_VERT) {
2151                                 BMIter liter;
2152                                 /* search for other faces */
2153                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
2154                                 do {
2155                                         if ((filter_fn == NULL) || filter_fn((BMElem *)l_iter->v, user_data)) {
2156                                                 BMLoop *l_other;
2157                                                 BM_ITER_ELEM (l_other, &liter, l_iter, BM_LOOPS_OF_LOOP) {
2158                                                         BMFace *f_other = l_other->f;
2159                                                         if (BM_elem_flag_test(f_other, BM_ELEM_TAG) == false) {
2160                                                                 BM_elem_flag_enable(f_other, BM_ELEM_TAG);
2161                                                                 STACK_PUSH(stack, f_other);
2162                                                         }
2163                                                 }
2164                                         }
2165                                 } while ((l_iter = l_iter->next) != l_first);
2166                         }
2167                 }
2168
2169                 group_curr++;
2170         }
2171
2172         MEM_freeN(stack);
2173
2174         /* reduce alloc to required size */
2175         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
2176         *r_group_index = group_index;
2177
2178         return group_curr;
2179 }
2180
2181 /* note, almost duplicate of BM_mesh_calc_face_groups, keep in sync */
2182 /**
2183  * Calculate isolated groups of edges with optional filtering.
2184  *
2185  * \param bm  the BMesh.
2186  * \param r_groups_array  Array of ints to fill in, length of bm->totedge
2187  *        (or when hflag_test is set, the number of flagged edges).
2188  * \param r_group_index  index, length pairs into \a r_groups_array, size of return value
2189  *        int pairs: (array_start, array_length).
2190  * \param filter_fn  Filter the edges or verts we step over (depends on \a htype_step)
2191  *        as to which types we deal with.
2192  * \param user_data  Optional user data for \a filter_fn, can be NULL.
2193  * \param hflag_test  Optional flag to test edges,
2194  *        use to exclude edges from the calculation, 0 for all edges.
2195  * \return The number of groups found.
2196  *
2197  * \note Unlike #BM_mesh_calc_face_groups there is no 'htype_step' argument,
2198  *       since we always walk over verts.
2199  */
2200 int BM_mesh_calc_edge_groups(BMesh *bm, int *r_groups_array, int (**r_group_index)[2],
2201                              BMElemFilterFunc filter_fn, void *user_data,
2202                              const char hflag_test)
2203 {
2204 #ifdef DEBUG
2205         int group_index_len = 1;
2206 #else
2207         int group_index_len = 32;
2208 #endif
2209
2210         int (*group_index)[2] = MEM_mallocN(sizeof(*group_index) * group_index_len, __func__);
2211
2212         int *group_array = r_groups_array;
2213         STACK_DECLARE(group_array);
2214
2215         int group_curr = 0;
2216
2217         unsigned int tot_edges = 0;
2218         unsigned int tot_touch = 0;
2219
2220         BMEdge **stack;
2221         STACK_DECLARE(stack);
2222
2223         BMIter iter;
2224         BMEdge *e;
2225         int i;
2226
2227         STACK_INIT(group_array, bm->totface);
2228
2229         /* init the array */
2230         BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
2231                 if ((hflag_test == 0) || BM_elem_flag_test(e, hflag_test)) {
2232                         tot_edges++;
2233                         BM_elem_flag_disable(e, BM_ELEM_TAG);
2234                 }
2235                 else {
2236                         /* never walk over tagged */
2237                         BM_elem_flag_enable(e, BM_ELEM_TAG);
2238                 }
2239
2240                 BM_elem_index_set(e, i); /* set_inline */
2241         }
2242         bm->elem_index_dirty &= ~BM_EDGE;
2243
2244         /* detect groups */
2245         stack = MEM_mallocN(sizeof(*stack) * tot_edges, __func__);
2246
2247         while (tot_touch != tot_edges) {
2248                 int *group_item;
2249                 bool ok = false;
2250
2251                 BLI_assert(tot_touch < tot_edges);
2252
2253                 STACK_INIT(stack, tot_edges);
2254
2255                 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
2256                         if (BM_elem_flag_test(e, BM_ELEM_TAG) == false) {
2257                                 BM_elem_flag_enable(e, BM_ELEM_TAG);
2258                                 STACK_PUSH(stack, e);
2259                                 ok = true;
2260                                 break;
2261                         }
2262                 }
2263
2264                 BLI_assert(ok == true);
2265
2266                 /* manage arrays */
2267                 if (group_index_len == group_curr) {
2268                         group_index_len *= 2;
2269                         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_index_len);
2270                 }
2271
2272                 group_item = group_index[group_curr];
2273                 group_item[0] = STACK_SIZE(group_array);
2274                 group_item[1] = 0;
2275
2276                 while ((e = STACK_POP(stack))) {
2277                         BMIter viter;
2278                         BMIter eiter;
2279                         BMVert *v;
2280
2281                         /* add edge */
2282                         STACK_PUSH(group_array, BM_elem_index_get(e));
2283                         tot_touch++;
2284                         group_item[1]++;
2285                         /* done */
2286
2287                         /* search for other edges */
2288                         BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) {
2289                                 if ((filter_fn == NULL) || filter_fn((BMElem *)v, user_data)) {
2290                                         BMEdge *e_other;
2291                                         BM_ITER_ELEM (e_other, &eiter, v, BM_EDGES_OF_VERT) {
2292                                                 if (BM_elem_flag_test(e_other, BM_ELEM_TAG) == false) {
2293                                                         BM_elem_flag_enable(e_other, BM_ELEM_TAG);
2294                                                         STACK_PUSH(stack, e_other);
2295                                                 }
2296                                         }
2297                                 }
2298                         }
2299                 }
2300
2301                 group_curr++;
2302         }
2303
2304         MEM_freeN(stack);
2305
2306         /* reduce alloc to required size */
2307         group_index = MEM_reallocN(group_index, sizeof(*group_index) * group_curr);
2308         *r_group_index = group_index;
2309
2310         return group_curr;
2311 }
2312
2313 float bmesh_subd_falloff_calc(const int falloff, float val)
2314 {
2315         switch (falloff) {
2316                 case SUBD_FALLOFF_SMOOTH:
2317                         val = 3.0f * val * val - 2.0f * val * val * val;
2318                         break;
2319                 case SUBD_FALLOFF_SPHERE:
2320                         val = sqrtf(2.0f * val - val * val);
2321                         break;
2322                 case SUBD_FALLOFF_ROOT:
2323                         val = sqrtf(val);
2324                         break;
2325                 case SUBD_FALLOFF_SHARP:
2326                         val = val * val;
2327                         break;
2328                 case SUBD_FALLOFF_LIN:
2329                         break;
2330                 default:
2331                         BLI_assert(0);
2332                         break;
2333         }
2334
2335         return val;
2336 }