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