c9e367d5f435552eea8d665d25bd13f4d1225ed1
[blender.git] / source / blender / bmesh / intern / bmesh_mods.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/intern/bmesh_mods.c
24  *  \ingroup bmesh
25  *
26  * This file contains functions for locally modifying
27  * the topology of existing mesh data. (split, join, flip etc).
28  */
29
30 #include "MEM_guardedalloc.h"
31
32
33 #include "BLI_math.h"
34 #include "BLI_array.h"
35 #include "BLI_alloca.h"
36 #include "BLI_stackdefines.h"
37 #include "BLI_linklist_stack.h"
38 #include "BLI_sort_utils.h"
39
40 #include "BKE_customdata.h"
41
42 #include "bmesh.h"
43 #include "intern/bmesh_private.h"
44
45 // #define DEBUG_PRINT
46
47
48 /**
49  * \brief Dissolve Vert
50  *
51  * Turns the face region surrounding a manifold vertex into a single polygon.
52  *
53  * \par Example:
54  * <pre>
55  *              +---------+             +---------+
56  *              |  \   /  |             |         |
57  *     Before:  |    v    |      After: |         |
58  *              |  /   \  |             |         |
59  *              +---------+             +---------+
60  * </pre>
61  *
62  * This function can also collapse edges too
63  * in cases when it cant merge into faces.
64  *
65  * \par Example:
66  * <pre>
67  *     Before:  +----v----+      After: +---------+
68  * </pre>
69  *
70  * \note dissolves vert, in more situations then BM_disk_dissolve
71  * (e.g. if the vert is part of a wire edge, etc).
72  */
73 bool BM_vert_dissolve(BMesh *bm, BMVert *v)
74 {
75         const int len = BM_vert_edge_count(v);
76         
77         if (len == 1) {
78                 BM_vert_kill(bm, v); /* will kill edges too */
79                 return true;
80         }
81         else if (!BM_vert_is_manifold(v)) {
82                 if (!v->e) {
83                         BM_vert_kill(bm, v);
84                         return true;
85                 }
86                 else if (!v->e->l) {
87                         if (len == 2) {
88                                 return (BM_vert_collapse_edge(bm, v->e, v, true, true) != NULL);
89                         }
90                         else {
91                                 /* used to kill the vertex here, but it may be connected to faces.
92                                  * so better do nothing */
93                                 return false;
94                         }
95                 }
96                 else {
97                         return false;
98                 }
99         }
100         else if (len == 2 && BM_vert_face_count(v) == 1) {
101                 /* boundary vertex on a face */
102                 return (BM_vert_collapse_edge(bm, v->e, v, true, true) != NULL);
103         }
104         else {
105                 return BM_disk_dissolve(bm, v);
106         }
107 }
108
109 /**
110  * dissolves all faces around a vert, and removes it.
111  */
112 bool BM_disk_dissolve(BMesh *bm, BMVert *v)
113 {
114         BMFace *f, *f2;
115         BMEdge *e, *keepedge = NULL, *baseedge = NULL;
116         int len = 0;
117
118         if (!BM_vert_is_manifold(v)) {
119                 return false;
120         }
121         
122         if (v->e) {
123                 /* v->e we keep, what else */
124                 e = v->e;
125                 do {
126                         e = bmesh_disk_edge_next(e, v);
127                         if (!(BM_edge_share_face_check(e, v->e))) {
128                                 keepedge = e;
129                                 baseedge = v->e;
130                                 break;
131                         }
132                         len++;
133                 } while (e != v->e);
134         }
135         
136         /* this code for handling 2 and 3-valence verts
137          * may be totally bad */
138         if (keepedge == NULL && len == 3) {
139 #if 0
140                 /* handle specific case for three-valence.  solve it by
141                  * increasing valence to four.  this may be hackish. .  */
142                 BMLoop *loop = e->l;
143                 if (loop->v == v) loop = loop->next;
144                 if (!BM_face_split(bm, loop->f, v, loop->v, NULL, NULL, false))
145                         return false;
146
147                 if (!BM_disk_dissolve(bm, v)) {
148                         return false;
149                 }
150 #else
151                 if (UNLIKELY(!BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e, true))) {
152                         return false;
153                 }
154                 else if (UNLIKELY(!BM_vert_collapse_faces(bm, v->e, v, 1.0, true, false, true))) {
155                         return false;
156                 }
157 #endif
158                 return true;
159         }
160         else if (keepedge == NULL && len == 2) {
161                 /* collapse the vertex */
162                 e = BM_vert_collapse_faces(bm, v->e, v, 1.0, true, true, true);
163
164                 if (!e) {
165                         return false;
166                 }
167
168                 /* handle two-valence */
169                 f = e->l->f;
170                 f2 = e->l->radial_next->f;
171
172                 if (f != f2 && !BM_faces_join_pair(bm, f, f2, e, true)) {
173                         return false;
174                 }
175
176                 return true;
177         }
178
179         if (keepedge) {
180                 bool done = false;
181
182                 while (!done) {
183                         done = true;
184                         e = v->e;
185                         do {
186                                 f = NULL;
187                                 if (BM_edge_is_manifold(e) && (e != baseedge) && (e != keepedge)) {
188                                         f = BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e, true);
189                                         /* return if couldn't join faces in manifold
190                                          * conditions */
191                                         /* !disabled for testing why bad things happen */
192                                         if (!f) {
193                                                 return false;
194                                         }
195                                 }
196
197                                 if (f) {
198                                         done = false;
199                                         break;
200                                 }
201                         } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
202                 }
203
204                 /* collapse the vertex */
205                 /* note, the baseedge can be a boundary of manifold, use this as join_faces arg */
206                 e = BM_vert_collapse_faces(bm, baseedge, v, 1.0, true, !BM_edge_is_boundary(baseedge), true);
207
208                 if (!e) {
209                         return false;
210                 }
211                 
212                 if (e->l) {
213                         /* get remaining two faces */
214                         f = e->l->f;
215                         f2 = e->l->radial_next->f;
216
217                         if (f != f2) {
218                                 /* join two remaining faces */
219                                 if (!BM_faces_join_pair(bm, f, f2, e, true)) {
220                                         return false;
221                                 }
222                         }
223                 }
224         }
225
226         return true;
227 }
228
229 /**
230  * \brief Faces Join Pair
231  *
232  * Joins two adjacent faces together.
233  *
234  * Because this method calls to #BM_faces_join to do its work, if a pair
235  * of faces share multiple edges, the pair of faces will be joined at
236  * every edge (not just edge \a e). This part of the functionality might need
237  * to be reconsidered.
238  *
239  * If the windings do not match the winding of the new face will follow
240  * \a f_a's winding (i.e. \a f_b will be reversed before the join).
241  *
242  * \return pointer to the combined face
243  */
244 BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f_a, BMFace *f_b, BMEdge *e, const bool do_del)
245 {
246         BMFace *faces[2] = {f_a, f_b};
247
248         BMLoop *l_a = BM_face_edge_share_loop(f_a, e);
249         BMLoop *l_b = BM_face_edge_share_loop(f_b, e);
250
251         BLI_assert(l_a && l_b);
252
253         if (l_a->v == l_b->v) {
254                 bmesh_loop_reverse(bm, f_b);
255         }
256         
257         return BM_faces_join(bm, faces, 2, do_del);
258 }
259
260 /**
261  * \brief Face Split
262  *
263  * Split a face along two vertices. returns the newly made face, and sets
264  * the \a r_l member to a loop in the newly created edge.
265  *
266  * \param bm The bmesh
267  * \param f the original face
268  * \param v1, v2 vertices which define the split edge, must be different
269  * \param r_l pointer which will receive the BMLoop for the split edge in the new face
270  * \param example Edge used for attributes of splitting edge, if non-NULL
271  * \param nodouble Use an existing edge if found
272  *
273  * \return Pointer to the newly created face representing one side of the split
274  * if the split is successful (and the original original face will be the
275  * other side). NULL if the split fails.
276  */
277 BMFace *BM_face_split(BMesh *bm, BMFace *f,
278                       BMLoop *l_a, BMLoop *l_b,
279                       BMLoop **r_l, BMEdge *example,
280                       const bool no_double)
281 {
282         const bool has_mdisp = CustomData_has_layer(&bm->ldata, CD_MDISPS);
283         BMFace *f_new, *f_tmp;
284
285         BLI_assert(l_a != l_b);
286         BLI_assert(f == l_a->f && f == l_b->f);
287         BLI_assert(!BM_loop_is_adjacent(l_a, l_b));
288
289         /* could be an assert */
290         if (UNLIKELY(BM_loop_is_adjacent(l_a, l_b)) ||
291             UNLIKELY((f != l_a->f || f != l_b->f)))
292         {
293                 if (r_l) {
294                         *r_l = NULL;
295                 }
296                 return NULL;
297         }
298
299         /* do we have a multires layer? */
300         if (has_mdisp) {
301                 f_tmp = BM_face_copy(bm, bm, f, false, false);
302         }
303         
304 #ifdef USE_BMESH_HOLES
305         f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, NULL, example, no_double);
306 #else
307         f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, example, no_double);
308 #endif
309         
310         if (f_new) {
311                 /* handle multires update */
312                 if (has_mdisp) {
313                         BMLoop *l_iter;
314                         BMLoop *l_first;
315
316                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
317                         do {
318                                 BM_loop_interp_multires(bm, l_iter, f_tmp);
319                         } while ((l_iter = l_iter->next) != l_first);
320
321                         l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
322                         do {
323                                 BM_loop_interp_multires(bm, l_iter, f_tmp);
324                         } while ((l_iter = l_iter->next) != l_first);
325
326 #if 0
327                         /* BM_face_multires_bounds_smooth doesn't flip displacement correct */
328                         BM_face_multires_bounds_smooth(bm, f);
329                         BM_face_multires_bounds_smooth(bm, f_new);
330 #endif
331                 }
332         }
333
334         if (has_mdisp) {
335                 BM_face_kill(bm, f_tmp);
336         }
337
338         return f_new;
339 }
340
341 /**
342  * \brief Face Split with intermediate points
343  *
344  * Like BM_face_split, but with an edge split by \a n intermediate points with given coordinates.
345  *
346  * \param bm The bmesh
347  * \param f the original face
348  * \param l_a, l_b vertices which define the split edge, must be different
349  * \param cos Array of coordinates for intermediate points
350  * \param n Length of \a cos (must be > 0)
351  * \param r_l pointer which will receive the BMLoop for the first split edge (from \a v1) in the new face
352  * \param example Edge used for attributes of splitting edge, if non-NULL
353  *
354  * \return Pointer to the newly created face representing one side of the split
355  * if the split is successful (and the original original face will be the
356  * other side). NULL if the split fails.
357  */
358 BMFace *BM_face_split_n(BMesh *bm, BMFace *f,
359                         BMLoop *l_a, BMLoop *l_b,
360                         float cos[][3], int n,
361                         BMLoop **r_l, BMEdge *example)
362 {
363         BMFace *f_new, *f_tmp;
364         BMLoop *l_dummy;
365         BMEdge *e, *e_new;
366         BMVert *v_new;
367         // BMVert *v_a = l_a->v; /* UNUSED */
368         BMVert *v_b = l_b->v;
369         int i, j;
370
371         BLI_assert(l_a != l_b);
372         BLI_assert(f == l_a->f && f == l_b->f);
373         BLI_assert(!((n == 0) && BM_loop_is_adjacent(l_a, l_b)));
374
375         /* could be an assert */
376         if (UNLIKELY((n == 0) && BM_loop_is_adjacent(l_a, l_b)) ||
377             UNLIKELY(l_a->f != l_b->f))
378         {
379                 if (r_l) {
380                         *r_l = NULL;
381                 }
382                 return NULL;
383         }
384
385         f_tmp = BM_face_copy(bm, bm, f, true, true);
386
387         if (!r_l)
388                 r_l = &l_dummy;
389         
390 #ifdef USE_BMESH_HOLES
391         f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, NULL, example, false);
392 #else
393         f_new = bmesh_sfme(bm, f, l_a, l_b, r_l, example, false);
394 #endif
395         /* bmesh_sfme returns in r_l a Loop for f_new going from v_a to v_b.
396          * The radial_next is for f and goes from v_b to v_a  */
397
398         if (f_new) {
399                 e = (*r_l)->e;
400                 for (i = 0; i < n; i++) {
401                         v_new = bmesh_semv(bm, v_b, e, &e_new);
402                         BLI_assert(v_new != NULL);
403                         /* bmesh_semv returns in e_new the edge going from v_new to tv */
404                         copy_v3_v3(v_new->co, cos[i]);
405
406                         /* interpolate the loop data for the loops with (v == v_new), using orig face */
407                         for (j = 0; j < 2; j++) {
408                                 BMEdge *e_iter = (j == 0) ? e : e_new;
409                                 BMLoop *l_iter = e_iter->l;
410                                 do {
411                                         if (l_iter->v == v_new) {
412                                                 /* this interpolates both loop and vertex data */
413                                                 BM_loop_interp_from_face(bm, l_iter, f_tmp, true, true);
414                                         }
415                                 } while ((l_iter = l_iter->radial_next) != e_iter->l);
416                         }
417                         e = e_new;
418                 }
419         }
420
421         BM_face_verts_kill(bm, f_tmp);
422
423         return f_new;
424 }
425
426
427 /* -------------------------------------------------------------------- */
428 /* Face Split Edge-Net */
429
430 /** \name BM_face_split_edgenet and helper functions.
431  *
432  * \note Don't use #BM_edge_is_wire or #BM_edge_is_boundary
433  * since we need to take flagged faces into account.
434  * Also take care accessing e->l directly.
435  *
436  * \{ */
437
438 /* Note: All these flags _must_ be cleared on exit */
439
440 /* face is apart of the edge-net (including the original face we're splitting) */
441 #define FACE_NET  _FLAG_WALK
442 /* edge is apart of the edge-net we're filling */
443 #define EDGE_NET   _FLAG_WALK
444 /* tag verts we've visit */
445 #define VERT_VISIT _FLAG_WALK
446
447 struct VertOrder {
448         float   angle;
449         BMVert *v;
450 };
451
452 static unsigned int bm_edge_flagged_radial_count(BMEdge *e)
453 {
454         unsigned int count = 0;
455         BMLoop *l;
456
457         if ((l = e->l)) {
458                 do {
459                         if (BM_ELEM_API_FLAG_TEST(l->f, FACE_NET)) {
460                                 count++;
461                         }
462                 } while ((l = l->radial_next) != e->l);
463         }
464         return count;
465 }
466
467 static BMLoop *bm_edge_flagged_radial_first(BMEdge *e)
468 {
469         BMLoop *l;
470
471         if ((l = e->l)) {
472                 do {
473                         if (BM_ELEM_API_FLAG_TEST(l->f, FACE_NET)) {
474                                 return l;
475                         }
476                 } while ((l = l->radial_next) != e->l);
477         }
478         return NULL;
479 }
480
481 static bool bm_face_split_edgenet_find_loop_pair(
482         BMVert *v_init, const float face_normal[3],
483         BMEdge *e_pair[2])
484 {
485         /* Always find one boundary edge (to determine winding)
486          * and one wire (if available), otherwise another boundary.
487          */
488         BMIter iter;
489         BMEdge *e;
490
491         /* detect winding */
492         BMLoop *l_walk;
493         bool swap;
494
495         BLI_SMALLSTACK_DECLARE(edges_boundary, BMEdge *);
496         BLI_SMALLSTACK_DECLARE(edges_wire,     BMEdge *);
497         int edges_boundary_len = 0;
498         int edges_wire_len = 0;
499
500         BM_ITER_ELEM (e, &iter, v_init, BM_EDGES_OF_VERT) {
501                 if (BM_ELEM_API_FLAG_TEST(e, EDGE_NET)) {
502                         const unsigned int count = bm_edge_flagged_radial_count(e);
503                         if (count == 1) {
504                                 BLI_SMALLSTACK_PUSH(edges_boundary, e);
505                                 edges_boundary_len++;
506                         }
507                         else if (count == 0) {
508                                 BLI_SMALLSTACK_PUSH(edges_wire, e);
509                                 edges_wire_len++;
510                         }
511                 }
512         }
513
514         /* first edge should always be boundary */
515         if (edges_boundary_len == 0) {
516                 return false;
517         }
518         e_pair[0] = BLI_SMALLSTACK_POP(edges_boundary);
519
520         /* attempt one boundary and one wire, or 2 boundary */
521         if (edges_wire_len == 0) {
522                 if (edges_boundary_len >= 2) {
523                         e_pair[1] = BLI_SMALLSTACK_POP(edges_boundary);
524                 }
525                 else {
526                         /* one boundary and no wire */
527                         return false;
528                 }
529         }
530         else {
531                 e_pair[1] = BLI_SMALLSTACK_POP(edges_wire);
532
533                 if (edges_wire_len > 1) {
534                         BMVert *v_prev = BM_edge_other_vert(e_pair[0], v_init);
535                         BMVert *v_next;
536                         float angle_best;
537
538                         v_next = BM_edge_other_vert(e_pair[1], v_init);
539                         angle_best = angle_on_axis_v3v3v3_v3(v_prev->co, v_init->co, v_next->co, face_normal);
540
541                         while ((e = BLI_SMALLSTACK_POP(edges_wire))) {
542                                 float angle_test;
543                                 v_next = BM_edge_other_vert(e, v_init);
544                                 angle_test = angle_on_axis_v3v3v3_v3(v_prev->co, v_init->co, v_next->co, face_normal);
545                                 if (angle_test < angle_best) {
546                                         angle_best = angle_test;
547                                         e_pair[1] = e;
548                                 }
549                         }
550                 }
551         }
552
553
554         /* flip based on winding */
555         l_walk = bm_edge_flagged_radial_first(e_pair[0]);
556         swap = false;
557         if (face_normal == l_walk->f->no) {
558                 swap = !swap;
559         }
560         if (l_walk->v != v_init) {
561                 swap = !swap;
562         }
563         if (swap) {
564                 SWAP(BMEdge *, e_pair[0], e_pair[1]);
565         }
566
567         return true;
568 }
569
570 static bool bm_face_split_edgenet_find_loop_walk(
571         BMVert *v_init, const float face_normal[3],
572         /* cache to avoid realloc every time */
573         struct VertOrder *edge_order, const unsigned int edge_order_len,
574         BMEdge *e_pair[2])
575 {
576         /* fast-path for the common case (avoid push-pop).
577          * Also avoids tagging as visited since we know we
578          * can't reach these verts some other way */
579 #define USE_FASTPATH_NOFORK
580
581         BMVert *v;
582         BMVert *v_dst;
583         bool found = false;
584
585         struct VertOrder *eo;
586         STACK_DECLARE(edge_order);
587
588         /* store visited verts so we can clear the visit flag after execution */
589         BLI_SMALLSTACK_DECLARE(vert_visit, BMVert *);
590
591         /* likely this will stay very small
592          * all verts pushed into this stack _must_ have their previous edges set! */
593         BLI_SMALLSTACK_DECLARE(vert_stack, BMVert *);
594         BLI_SMALLSTACK_DECLARE(vert_stack_next, BMVert *);
595
596         STACK_INIT(edge_order, edge_order_len);
597
598         /* start stepping */
599         v = BM_edge_other_vert(e_pair[0], v_init);
600         v->e = e_pair[0];
601         BLI_SMALLSTACK_PUSH(vert_stack, v);
602
603         v_dst = BM_edge_other_vert(e_pair[1], v_init);
604
605 #ifdef DEBUG_PRINT
606         printf("%s: vert (search) %d\n", __func__, BM_elem_index_get(v_init));
607 #endif
608
609         /* This loop will keep stepping over the best possible edge,
610          * in most cases it finds the direct route to close the face.
611          *
612          * In cases where paths can't be closed,
613          * alternatives are stored in the 'vert_stack'.
614          */
615         while ((v = BLI_SMALLSTACK_POP_EX(vert_stack, vert_stack_next))) {
616                 BMIter eiter;
617                 BMEdge *e_next;
618
619 #ifdef USE_FASTPATH_NOFORK
620 walk_nofork:
621 #else
622                 BLI_SMALLSTACK_PUSH(vert_visit, v);
623                 BM_ELEM_API_FLAG_ENABLE(v, VERT_VISIT);
624 #endif
625
626                 BLI_assert(STACK_SIZE(edge_order) == 0);
627
628                 /* check if we're done! */
629                 if (v == v_dst) {
630                         found = true;
631                         goto finally;
632                 }
633
634                 BM_ITER_ELEM (e_next, &eiter, v, BM_EDGES_OF_VERT) {
635                         if ((v->e != e_next) &&
636                             (BM_ELEM_API_FLAG_TEST(e_next, EDGE_NET)) &&
637                             (bm_edge_flagged_radial_count(e_next) < 2))
638                         {
639                                 BMVert *v_next;
640
641                                 v_next = BM_edge_other_vert(e_next, v);
642
643 #ifdef DEBUG_PRINT
644                                 /* indent and print */
645                                 {
646                                         BMVert *_v = v;
647                                         do {
648                                                 printf("  ");
649                                         } while ((_v = BM_edge_other_vert(_v->e, _v)) != v_init);
650                                         printf("vert %d -> %d (add=%d)\n",
651                                                BM_elem_index_get(v), BM_elem_index_get(v_next),
652                                                BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT) == 0);
653                                 }
654 #endif
655
656                                 if (!BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT)) {
657                                         eo = STACK_PUSH_RET_PTR(edge_order);
658                                         eo->v = v_next;
659
660                                         v_next->e = e_next;
661                                 }
662                         }
663                 }
664
665 #ifdef USE_FASTPATH_NOFORK
666                 if (STACK_SIZE(edge_order) == 1) {
667                         eo = STACK_POP_PTR(edge_order);
668                         v = eo->v;
669
670                         goto walk_nofork;
671                 }
672 #endif
673
674                 /* sort by angle if needed */
675                 if (STACK_SIZE(edge_order) > 1) {
676                         unsigned int j;
677                         BMVert *v_prev = BM_edge_other_vert(v->e, v);
678
679                         for (j = 0; j < STACK_SIZE(edge_order); j++) {
680                                 edge_order[j].angle = angle_signed_on_axis_v3v3v3_v3(v_prev->co, v->co, edge_order[j].v->co, face_normal);
681                         }
682                         qsort(edge_order, STACK_SIZE(edge_order), sizeof(struct VertOrder), BLI_sortutil_cmp_float_reverse);
683
684 #ifdef USE_FASTPATH_NOFORK
685                         /* only tag forks */
686                         BLI_SMALLSTACK_PUSH(vert_visit, v);
687                         BM_ELEM_API_FLAG_ENABLE(v, VERT_VISIT);
688 #endif
689                 }
690
691                 while ((eo = STACK_POP_PTR(edge_order))) {
692                         BLI_SMALLSTACK_PUSH(vert_stack_next, eo->v);
693                 }
694
695                 if (!BLI_SMALLSTACK_IS_EMPTY(vert_stack_next)) {
696                         BLI_SMALLSTACK_SWAP(vert_stack, vert_stack_next);
697                 }
698         }
699
700
701 finally:
702         /* clear flag for next execution */
703         while ((v = BLI_SMALLSTACK_POP(vert_visit))) {
704                 BM_ELEM_API_FLAG_DISABLE(v, VERT_VISIT);
705         }
706
707         return found;
708
709 #undef USE_FASTPATH_NOFORK
710 }
711
712 static bool bm_face_split_edgenet_find_loop(
713         BMVert *v_init, const float face_normal[3],
714         /* cache to avoid realloc every time */
715         struct VertOrder *edge_order, const unsigned int edge_order_len,
716         BMVert **r_face_verts, int *r_face_verts_len)
717 {
718         BMEdge *e_pair[2];
719         BMVert *v;
720
721         if (!bm_face_split_edgenet_find_loop_pair(v_init, face_normal, e_pair)) {
722                 return false;
723         }
724
725         BLI_assert((bm_edge_flagged_radial_count(e_pair[0]) == 1) ||
726                    (bm_edge_flagged_radial_count(e_pair[1]) == 1));
727
728         if (bm_face_split_edgenet_find_loop_walk(v_init, face_normal, edge_order, edge_order_len, e_pair)) {
729                 unsigned int i = 0;
730
731                 r_face_verts[i++] = v_init;
732                 v = BM_edge_other_vert(e_pair[1], v_init);
733                 do {
734                         r_face_verts[i++] = v;
735                 } while ((v = BM_edge_other_vert(v->e, v)) != v_init);
736                 *r_face_verts_len = i;
737                 return (i > 2) ? true : false;
738         }
739         else {
740                 return false;
741         }
742 }
743
744 /**
745  * Splits a face into many smaller faces defined by an edge-net.
746  * handle customdata and degenerate cases.
747  *
748  * - isolated holes or unsupported face configurations, will be ignored.
749  * - customdata calculations aren't efficient
750  *   (need to calculate weights for each vert).
751  */
752 bool BM_face_split_edgenet(
753         BMesh *bm,
754         BMFace *f, BMEdge **edge_net, const int edge_net_len,
755         BMFace ***r_face_arr, int *r_face_arr_len)
756 {
757         /* re-use for new face verts */
758         BMVert **face_verts;
759         int      face_verts_len;
760
761         BMFace **face_arr = NULL;
762         BLI_array_declare(face_arr);
763
764         BMVert **vert_queue;
765         STACK_DECLARE(vert_queue);
766         int i;
767
768         struct VertOrder *edge_order;
769         const unsigned int edge_order_len = edge_net_len + 2;
770
771         BMVert *v;
772
773         BMLoop *l_iter, *l_first;
774
775
776         if (!edge_net_len) {
777                 if (r_face_arr) {
778                         *r_face_arr = NULL;
779                         *r_face_arr_len = 0;
780                 }
781                 return false;
782         }
783
784         /* over-alloc (probably 2-4 is only used in most cases), for the biggest-fan */
785         edge_order = BLI_array_alloca(edge_order, edge_order_len);
786
787         /* use later */
788         face_verts = BLI_array_alloca(face_verts, edge_net_len + f->len);
789
790         vert_queue = BLI_array_alloca(vert_queue, edge_net_len + f->len);
791         STACK_INIT(vert_queue, f->len + edge_net_len);
792
793         BLI_assert(BM_ELEM_API_FLAG_TEST(f, FACE_NET) == 0);
794         BM_ELEM_API_FLAG_ENABLE(f, FACE_NET);
795
796 #ifdef DEBUG
797         for (i = 0; i < edge_net_len; i++) {
798                 BLI_assert(BM_ELEM_API_FLAG_TEST(edge_net[i], EDGE_NET) == 0);
799         }
800         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
801         do {
802                 BLI_assert(BM_ELEM_API_FLAG_TEST(l_iter->e, EDGE_NET) == 0);
803         } while ((l_iter = l_iter->next) != l_first);
804 #endif
805
806
807         for (i = 0; i < edge_net_len; i++) {
808                 BM_ELEM_API_FLAG_ENABLE(edge_net[i], EDGE_NET);
809         }
810         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
811         do {
812                 BM_ELEM_API_FLAG_ENABLE(l_iter->e, EDGE_NET);
813         } while ((l_iter = l_iter->next) != l_first);
814
815
816         /* any vert can be used to begin with */
817         STACK_PUSH(vert_queue, l_first->v);
818
819         while ((v = STACK_POP(vert_queue))) {
820                 if (bm_face_split_edgenet_find_loop(v, f->no, edge_order, edge_order_len, face_verts, &face_verts_len)) {
821                         BMFace *f_new = BM_face_create_verts(bm, face_verts, face_verts_len, f, 0, false);
822
823                         for (i = 0; i < edge_net_len; i++) {
824                                 BLI_assert(BM_ELEM_API_FLAG_TEST(edge_net[i], EDGE_NET));
825                         }
826
827                         if (f_new) {
828                                 bool l_prev_is_boundary;
829                                 BLI_array_append(face_arr, f_new);
830                                 copy_v3_v3(f_new->no, f->no);
831
832                                 BM_ELEM_API_FLAG_ENABLE(f_new, FACE_NET);
833
834                                 /* add new verts to keep finding loops for
835                                  * (verts betweem boundary and manifold edges) */
836                                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
837                                 l_prev_is_boundary = (bm_edge_flagged_radial_count(l_iter->prev->e) == 1);
838                                 do {
839                                         bool l_iter_is_boundary = (bm_edge_flagged_radial_count(l_iter->e) == 1);
840                                         if (l_prev_is_boundary != l_iter_is_boundary) {
841                                                 STACK_PUSH(vert_queue, l_iter->v);
842                                         }
843                                         l_prev_is_boundary = l_iter_is_boundary;
844                                 } while ((l_iter = l_iter->next) != l_first);
845                         }
846                 }
847         }
848
849
850         if (CustomData_has_math(&bm->ldata)) {
851                 /* reuse VERT_VISIT here to tag vert's already interpolated */
852                 BMIter iter;
853                 BMLoop *l_other;
854
855                 /* see: #BM_loop_interp_from_face for similar logic  */
856                 void **blocks   = BLI_array_alloca(blocks, f->len);
857                 float (*cos_2d)[2] = BLI_array_alloca(cos_2d, f->len);
858                 float *w        = BLI_array_alloca(w, f->len);
859                 float axis_mat[3][3];
860                 float co[2];
861
862                 /* interior loops */
863                 axis_dominant_v3_to_m3(axis_mat, f->no);
864
865
866                 /* first simply copy from existing face */
867                 i = 0;
868                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
869                 do {
870                         BM_ITER_ELEM (l_other, &iter, l_iter->v, BM_LOOPS_OF_VERT) {
871                                 if ((l_other->f != f) && BM_ELEM_API_FLAG_TEST(l_other->f, FACE_NET)) {
872                                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata,
873                                                                    l_iter->head.data, &l_other->head.data);
874                                 }
875                         }
876                         /* tag not to interpolate */
877                         BM_ELEM_API_FLAG_ENABLE(l_iter->v, VERT_VISIT);
878
879
880                         mul_v2_m3v3(cos_2d[i], axis_mat, l_iter->v->co);
881                         blocks[i] = l_iter->head.data;
882
883                 } while (i++, (l_iter = l_iter->next) != l_first);
884
885
886                 for (i = 0; i < edge_net_len; i++) {
887                         BM_ITER_ELEM (v, &iter, edge_net[i], BM_VERTS_OF_EDGE) {
888                                 if (!BM_ELEM_API_FLAG_TEST(v, VERT_VISIT)) {
889                                         BMIter liter;
890
891                                         BM_ELEM_API_FLAG_ENABLE(v, VERT_VISIT);
892
893                                         /* interpolate this loop, then copy to the rest */
894                                         l_first = NULL;
895
896                                         BM_ITER_ELEM (l_iter, &liter, v, BM_LOOPS_OF_VERT) {
897                                                 if (BM_ELEM_API_FLAG_TEST(l_iter->f, FACE_NET)) {
898                                                         if (l_first == NULL) {
899                                                                 mul_v2_m3v3(co, axis_mat, v->co);
900                                                                 interp_weights_poly_v2(w, cos_2d, f->len, co);
901                                                                 CustomData_bmesh_interp(&bm->ldata, blocks, w, NULL, f->len, l_iter->head.data);
902                                                                 l_first = l_iter;
903                                                         }
904                                                         else {
905                                                                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata,
906                                                                                            l_first->head.data, &l_iter->head.data);
907                                                         }
908                                                 }
909                                         }
910                                 }
911                         }
912                 }
913         }
914
915
916
917         /* cleanup */
918         for (i = 0; i < edge_net_len; i++) {
919                 BM_ELEM_API_FLAG_DISABLE(edge_net[i], EDGE_NET);
920                 /* from interp only */
921                 BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v1, VERT_VISIT);
922                 BM_ELEM_API_FLAG_DISABLE(edge_net[i]->v2, VERT_VISIT);
923         }
924         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
925         do {
926                 BM_ELEM_API_FLAG_DISABLE(l_iter->e, EDGE_NET);
927                 /* from interp only */
928                 BM_ELEM_API_FLAG_DISABLE(l_iter->v, VERT_VISIT);
929         } while ((l_iter = l_iter->next) != l_first);
930
931         if (BLI_array_count(face_arr)) {
932                 bmesh_face_swap_data(f, face_arr[0]);
933                 BM_face_kill(bm, face_arr[0]);
934                 face_arr[0] = f;
935         }
936         else {
937                 BM_ELEM_API_FLAG_DISABLE(f, FACE_NET);
938         }
939
940         for (i = 0; i < BLI_array_count(face_arr); i++) {
941                 BM_ELEM_API_FLAG_DISABLE(face_arr[i], FACE_NET);
942         }
943
944         if (r_face_arr) {
945                 *r_face_arr = face_arr;
946                 *r_face_arr_len = BLI_array_count(face_arr);
947         }
948         else {
949                 if (face_arr) {
950                         MEM_freeN(face_arr);
951                 }
952         }
953
954         return true;
955 }
956
957 #undef FACE_NET
958 #undef VERT_VISIT
959 #undef EDGE_NET
960
961 /** \} */
962
963
964 /**
965  * \brief Vert Collapse Faces
966  *
967  * Collapses vertex \a v_kill that has only two manifold edges
968  * onto a vertex it shares an edge with.
969  * \a fac defines the amount of interpolation for Custom Data.
970  *
971  * \note that this is not a general edge collapse function.
972  *
973  * \note this function is very close to #BM_vert_collapse_edge,
974  * both collapse a vertex and return a new edge.
975  * Except this takes a factor and merges custom data.
976  *
977  * \param bm The bmesh
978  * \param e_kill The edge to collapse
979  * \param v_kill The vertex  to collapse into the edge
980  * \param fac The factor along the edge
981  * \param join_faces When true the faces around the vertex will be joined
982  * otherwise collapse the vertex by merging the 2 edges this vert touches into one.
983  * \param kill_degenerate_faces Removes faces with less than 3 verts after collapsing.
984  *
985  * \returns The New Edge
986  */
987 BMEdge *BM_vert_collapse_faces(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, float fac,
988                                const bool do_del, const bool join_faces, const bool kill_degenerate_faces)
989 {
990         BMEdge *e_new = NULL;
991         BMVert *tv = BM_edge_other_vert(e_kill, v_kill);
992
993         BMEdge *e2;
994         BMVert *tv2;
995
996         /* Only intended to be called for 2-valence vertices */
997         BLI_assert(bmesh_disk_count(v_kill) <= 2);
998
999
1000         /* first modify the face loop data */
1001
1002         if (e_kill->l) {
1003                 BMLoop *l_iter;
1004                 const float w[2] = {1.0f - fac, fac};
1005
1006                 l_iter = e_kill->l;
1007                 do {
1008                         if (l_iter->v == tv && l_iter->next->v == v_kill) {
1009                                 void *src[2];
1010                                 BMLoop *tvloop = l_iter;
1011                                 BMLoop *kvloop = l_iter->next;
1012
1013                                 src[0] = kvloop->head.data;
1014                                 src[1] = tvloop->head.data;
1015                                 CustomData_bmesh_interp(&bm->ldata, src, w, NULL, 2, kvloop->head.data);
1016                         }
1017                 } while ((l_iter = l_iter->radial_next) != e_kill->l);
1018         }
1019
1020         /* now interpolate the vertex data */
1021         BM_data_interp_from_verts(bm, v_kill, tv, v_kill, fac);
1022
1023         e2 = bmesh_disk_edge_next(e_kill, v_kill);
1024         tv2 = BM_edge_other_vert(e2, v_kill);
1025
1026         if (join_faces) {
1027                 BMIter fiter;
1028                 BMFace **faces = NULL;
1029                 BMFace *f;
1030                 BLI_array_staticdeclare(faces, BM_DEFAULT_ITER_STACK_SIZE);
1031
1032                 BM_ITER_ELEM (f, &fiter, v_kill, BM_FACES_OF_VERT) {
1033                         BLI_array_append(faces, f);
1034                 }
1035
1036                 if (BLI_array_count(faces) >= 2) {
1037                         BMFace *f2 = BM_faces_join(bm, faces, BLI_array_count(faces), true);
1038                         if (f2) {
1039                                 BMLoop *l_a, *l_b;
1040
1041                                 if ((l_a = BM_face_vert_share_loop(f2, tv)) &&
1042                                     (l_b = BM_face_vert_share_loop(f2, tv2)))
1043                                 {
1044                                         BMLoop *l_new;
1045
1046                                         if (BM_face_split(bm, f2, l_a, l_b, &l_new, NULL, false)) {
1047                                                 e_new = l_new->e;
1048                                         }
1049                                 }
1050                         }
1051                 }
1052
1053                 BLI_assert(BLI_array_count(faces) < 8);
1054
1055                 BLI_array_free(faces);
1056         }
1057         else {
1058                 /* single face or no faces */
1059                 /* same as BM_vert_collapse_edge() however we already
1060                  * have vars to perform this operation so don't call. */
1061                 e_new = bmesh_jekv(bm, e_kill, v_kill, do_del, true);
1062                 /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */
1063
1064                 if (e_new && kill_degenerate_faces) {
1065                         BMFace **bad_faces = NULL;
1066                         BLI_array_staticdeclare(bad_faces, BM_DEFAULT_ITER_STACK_SIZE);
1067
1068                         BMIter fiter;
1069                         BMFace *f;
1070                         BMVert *verts[2] = {e_new->v1, e_new->v2};
1071                         int i;
1072
1073                         for (i = 0; i < 2; i++) {
1074                                 /* cant kill data we loop on, build a list and remove those */
1075                                 BLI_array_empty(bad_faces);
1076                                 BM_ITER_ELEM (f, &fiter, verts[i], BM_FACES_OF_VERT) {
1077                                         if (UNLIKELY(f->len < 3)) {
1078                                                 BLI_array_append(bad_faces, f);
1079                                         }
1080                                 }
1081                                 while ((f = BLI_array_pop(bad_faces))) {
1082                                         BM_face_kill(bm, f);
1083                                 }
1084                         }
1085                         BLI_array_free(bad_faces);
1086                 }
1087         }
1088
1089         return e_new;
1090 }
1091
1092
1093 /**
1094  * \brief Vert Collapse Faces
1095  *
1096  * Collapses a vertex onto another vertex it shares an edge with.
1097  *
1098  * \return The New Edge
1099  */
1100 BMEdge *BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill,
1101                               const bool do_del, const bool kill_degenerate_faces)
1102 {
1103         /* nice example implementation but we want loops to have their customdata
1104          * accounted for */
1105 #if 0
1106         BMEdge *e_new = NULL;
1107
1108         /* Collapse between 2 edges */
1109
1110         /* in this case we want to keep all faces and not join them,
1111          * rather just get rid of the vertex - see bug [#28645] */
1112         BMVert *tv  = BM_edge_other_vert(e_kill, v_kill);
1113         if (tv) {
1114                 BMEdge *e2 = bmesh_disk_edge_next(e_kill, v_kill);
1115                 if (e2) {
1116                         BMVert *tv2 = BM_edge_other_vert(e2, v_kill);
1117                         if (tv2) {
1118                                 /* only action, other calls here only get the edge to return */
1119                                 e_new = bmesh_jekv(bm, e_kill, v_kill, do_del);
1120                         }
1121                 }
1122         }
1123
1124         return e_new;
1125 #else
1126         /* with these args faces are never joined, same as above
1127          * but account for loop customdata */
1128         return BM_vert_collapse_faces(bm, e_kill, v_kill, 1.0f, do_del, false, kill_degenerate_faces);
1129 #endif
1130 }
1131
1132 #undef DO_V_INTERP
1133
1134 /**
1135  * \brief Edge Split
1136  *
1137  * Splits an edge. \a v should be one of the vertices in \a e and defines
1138  * the "from" end of the splitting operation: the new vertex will be
1139  * \a percent of the way from \a v to the other end.
1140  * The newly created edge is attached to \a v and is returned in \a r_e.
1141  * The original edge \a e will be the other half of the split.
1142  *
1143  * \return The new vert
1144  */
1145 BMVert *BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float percent)
1146 {
1147         BMVert *v_new, *v2;
1148         BMFace **oldfaces = NULL;
1149         BMEdge *e_dummy;
1150         BLI_array_staticdeclare(oldfaces, 32);
1151         const bool do_mdisp = (e->l && CustomData_has_layer(&bm->ldata, CD_MDISPS));
1152
1153         /* we need this for handling multi-res */
1154         if (!r_e) {
1155                 r_e = &e_dummy;
1156         }
1157
1158         /* do we have a multi-res layer? */
1159         if (do_mdisp) {
1160                 BMLoop *l;
1161                 int i;
1162                 
1163                 l = e->l;
1164                 do {
1165                         BLI_array_append(oldfaces, l->f);
1166                         l = l->radial_next;
1167                 } while (l != e->l);
1168                 
1169                 /* flag existing faces so we can differentiate oldfaces from new faces */
1170                 for (i = 0; i < BLI_array_count(oldfaces); i++) {
1171                         BM_ELEM_API_FLAG_ENABLE(oldfaces[i], _FLAG_OVERLAP);
1172                         oldfaces[i] = BM_face_copy(bm, bm, oldfaces[i], true, true);
1173                         BM_ELEM_API_FLAG_DISABLE(oldfaces[i], _FLAG_OVERLAP);
1174                 }
1175         }
1176
1177         v2 = BM_edge_other_vert(e, v);
1178         v_new = bmesh_semv(bm, v, e, r_e);
1179
1180         BLI_assert(v_new != NULL);
1181
1182         sub_v3_v3v3(v_new->co, v2->co, v->co);
1183         madd_v3_v3v3fl(v_new->co, v->co, v_new->co, percent);
1184
1185         if (r_e) {
1186                 (*r_e)->head.hflag = e->head.hflag;
1187                 BM_elem_attrs_copy(bm, bm, e, *r_e);
1188         }
1189
1190         /* v->v_new->v2 */
1191         BM_data_interp_face_vert_edge(bm, v2, v, v_new, e, percent);
1192         BM_data_interp_from_verts(bm, v, v2, v_new, percent);
1193
1194         if (do_mdisp) {
1195                 int i, j;
1196
1197                 /* interpolate new/changed loop data from copied old faces */
1198                 for (j = 0; j < 2; j++) {
1199                         for (i = 0; i < BLI_array_count(oldfaces); i++) {
1200                                 BMEdge *e1 = j ? *r_e : e;
1201                                 BMLoop *l, *l2;
1202                                 
1203                                 l = e1->l;
1204
1205                                 if (UNLIKELY(!l)) {
1206                                         BMESH_ASSERT(0);
1207                                         break;
1208                                 }
1209                                 
1210                                 do {
1211                                         /* check this is an old face */
1212                                         if (BM_ELEM_API_FLAG_TEST(l->f, _FLAG_OVERLAP)) {
1213                                                 BMLoop *l2_first;
1214
1215                                                 l2 = l2_first = BM_FACE_FIRST_LOOP(l->f);
1216                                                 do {
1217                                                         BM_loop_interp_multires(bm, l2, oldfaces[i]);
1218                                                 } while ((l2 = l2->next) != l2_first);
1219                                         }
1220                                         l = l->radial_next;
1221                                 } while (l != e1->l);
1222                         }
1223                 }
1224                 
1225                 /* destroy the old faces */
1226                 for (i = 0; i < BLI_array_count(oldfaces); i++) {
1227                         BM_face_verts_kill(bm, oldfaces[i]);
1228                 }
1229                 
1230                 /* fix boundaries a bit, doesn't work too well quite yet */
1231 #if 0
1232                 for (j = 0; j < 2; j++) {
1233                         BMEdge *e1 = j ? *r_e : e;
1234                         BMLoop *l, *l2;
1235                         
1236                         l = e1->l;
1237                         if (UNLIKELY(!l)) {
1238                                 BMESH_ASSERT(0);
1239                                 break;
1240                         }
1241                         
1242                         do {
1243                                 BM_face_multires_bounds_smooth(bm, l->f);
1244                                 l = l->radial_next;
1245                         } while (l != e1->l);
1246                 }
1247 #endif
1248                 
1249                 BLI_array_free(oldfaces);
1250         }
1251
1252         return v_new;
1253 }
1254
1255 /**
1256  * \brief Split an edge multiple times evenly
1257  *
1258  * \param r_varr  Optional array, verts in between (v1 -> v2)
1259  */
1260 BMVert  *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts, BMVert **r_varr)
1261 {
1262         int i;
1263         float percent;
1264         BMVert *v_new = NULL;
1265         
1266         for (i = 0; i < numcuts; i++) {
1267                 percent = 1.0f / (float)(numcuts + 1 - i);
1268                 v_new = BM_edge_split(bm, e, e->v2, NULL, percent);
1269                 if (r_varr) {
1270                         /* fill in reverse order (v1 -> v2) */
1271                         r_varr[numcuts - i - 1] = v_new;
1272                 }
1273         }
1274         return v_new;
1275 }
1276
1277 #if 0
1278 /**
1279  * Checks if a face is valid in the data structure
1280  */
1281 bool BM_face_validate(BMFace *face, FILE *err)
1282 {
1283         BMIter iter;
1284         BLI_array_declare(verts);
1285         BMVert **verts = NULL;
1286         BMLoop *l;
1287         int i, j;
1288         bool ret = true;
1289         
1290         if (face->len == 2) {
1291                 fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
1292                 fflush(err);
1293         }
1294
1295         BLI_array_grow_items(verts, face->len);
1296         BM_ITER_ELEM_INDEX (l, &iter, face, BM_LOOPS_OF_FACE, i) {
1297                 verts[i] = l->v;
1298                 if (l->e->v1 == l->e->v2) {
1299                         fprintf(err, "Found bmesh edge with identical verts!\n");
1300                         fprintf(err, "  edge ptr: %p, vert: %p\n",  l->e, l->e->v1);
1301                         fflush(err);
1302                         ret = false;
1303                 }
1304         }
1305
1306         for (i = 0; i < face->len; i++) {
1307                 for (j = 0; j < face->len; j++) {
1308                         if (j == i) {
1309                                 continue;
1310                         }
1311
1312                         if (verts[i] == verts[j]) {
1313                                 fprintf(err, "Found duplicate verts in bmesh face!\n");
1314                                 fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
1315                                 fflush(err);
1316                                 ret = false;
1317                         }
1318                 }
1319         }
1320         
1321         BLI_array_free(verts);
1322         return ret;
1323 }
1324 #endif
1325
1326 /**
1327  * Calculate the 2 loops which _would_ make up the newly rotated Edge
1328  * but don't actually change anything.
1329  *
1330  * Use this to further inspect if the loops to be connected have issues:
1331  *
1332  * Examples:
1333  * - the newly formed edge already exists
1334  * - the new face would be degenerate (zero area / concave /  bow-tie)
1335  * - may want to measure if the new edge gives improved results topology.
1336  *   over the old one, as with beauty fill.
1337  *
1338  * \note #BM_edge_rotate_check must have already run.
1339  */
1340 void BM_edge_calc_rotate(BMEdge *e, const bool ccw,
1341                          BMLoop **r_l1, BMLoop **r_l2)
1342 {
1343         BMVert *v1, *v2;
1344         BMFace *fa, *fb;
1345
1346         /* this should have already run */
1347         BLI_assert(BM_edge_rotate_check(e) == true);
1348
1349         /* we know this will work */
1350         BM_edge_face_pair(e, &fa, &fb);
1351
1352         /* so we can use ccw variable correctly,
1353          * otherwise we could use the edges verts direct */
1354         BM_edge_ordered_verts(e, &v1, &v2);
1355
1356         /* we could swap the verts _or_ the faces, swapping faces
1357          * gives more predictable results since that way the next vert
1358          * just stitches from face fa / fb */
1359         if (!ccw) {
1360                 SWAP(BMFace *, fa, fb);
1361         }
1362
1363         *r_l1 = BM_face_other_vert_loop(fb, v2, v1);
1364         *r_l2 = BM_face_other_vert_loop(fa, v1, v2);
1365 }
1366
1367 /**
1368  * \brief Check if Rotate Edge is OK
1369  *
1370  * Quick check to see if we could rotate the edge,
1371  * use this to avoid calling exceptions on common cases.
1372  */
1373 bool BM_edge_rotate_check(BMEdge *e)
1374 {
1375         BMFace *fa, *fb;
1376         if (BM_edge_face_pair(e, &fa, &fb)) {
1377                 BMLoop *la, *lb;
1378
1379                 la = BM_face_other_vert_loop(fa, e->v2, e->v1);
1380                 lb = BM_face_other_vert_loop(fb, e->v2, e->v1);
1381
1382                 /* check that the next vert in both faces isn't the same
1383                  * (ie - the next edge doesn't share the same faces).
1384                  * since we can't rotate usefully in this case. */
1385                 if (la->v == lb->v) {
1386                         return false;
1387                 }
1388
1389                 /* mirror of the check above but in the opposite direction */
1390                 la = BM_face_other_vert_loop(fa, e->v1, e->v2);
1391                 lb = BM_face_other_vert_loop(fb, e->v1, e->v2);
1392
1393                 if (la->v == lb->v) {
1394                         return false;
1395                 }
1396
1397                 return true;
1398         }
1399         else {
1400                 return false;
1401         }
1402 }
1403
1404 /**
1405  * \brief Check if Edge Rotate Gives Degenerate Faces
1406  *
1407  * Check 2 cases
1408  * 1) does the newly forms edge form a flipped face (compare with previous cross product)
1409  * 2) does the newly formed edge cause a zero area corner (or close enough to be almost zero)
1410  *
1411  * \param e The edge to test rotation.
1412  * \param l1,l2 are the loops of the proposed verts to rotate too and should
1413  * be the result of calling #BM_edge_calc_rotate
1414  */
1415 bool BM_edge_rotate_check_degenerate(BMEdge *e, BMLoop *l1, BMLoop *l2)
1416 {
1417         /* note: for these vars 'old' just means initial edge state. */
1418
1419         float ed_dir_old[3]; /* edge vector */
1420         float ed_dir_new[3]; /* edge vector */
1421         float ed_dir_new_flip[3]; /* edge vector */
1422
1423         float ed_dir_v1_old[3];
1424         float ed_dir_v2_old[3];
1425
1426         float ed_dir_v1_new[3];
1427         float ed_dir_v2_new[3];
1428
1429         float cross_old[3];
1430         float cross_new[3];
1431
1432         /* original verts - these will be in the edge 'e' */
1433         BMVert *v1_old, *v2_old;
1434
1435         /* verts from the loops passed */
1436
1437         BMVert *v1, *v2;
1438         /* these are the opposite verts - the verts that _would_ be used if 'ccw' was inverted*/
1439         BMVert *v1_alt, *v2_alt;
1440
1441         /* this should have already run */
1442         BLI_assert(BM_edge_rotate_check(e) == true);
1443
1444         BM_edge_ordered_verts(e, &v1_old, &v2_old);
1445
1446         v1 = l1->v;
1447         v2 = l2->v;
1448
1449         /* get the next vert along */
1450         v1_alt = BM_face_other_vert_loop(l1->f, v1_old, v1)->v;
1451         v2_alt = BM_face_other_vert_loop(l2->f, v2_old, v2)->v;
1452
1453         /* normalize all so comparisons are scale independent */
1454
1455         BLI_assert(BM_edge_exists(v1_old, v1));
1456         BLI_assert(BM_edge_exists(v1, v1_alt));
1457
1458         BLI_assert(BM_edge_exists(v2_old, v2));
1459         BLI_assert(BM_edge_exists(v2, v2_alt));
1460
1461         /* old and new edge vecs */
1462         sub_v3_v3v3(ed_dir_old, v1_old->co, v2_old->co);
1463         sub_v3_v3v3(ed_dir_new, v1->co, v2->co);
1464         normalize_v3(ed_dir_old);
1465         normalize_v3(ed_dir_new);
1466
1467         /* old edge corner vecs */
1468         sub_v3_v3v3(ed_dir_v1_old, v1_old->co, v1->co);
1469         sub_v3_v3v3(ed_dir_v2_old, v2_old->co, v2->co);
1470         normalize_v3(ed_dir_v1_old);
1471         normalize_v3(ed_dir_v2_old);
1472
1473         /* old edge corner vecs */
1474         sub_v3_v3v3(ed_dir_v1_new, v1->co, v1_alt->co);
1475         sub_v3_v3v3(ed_dir_v2_new, v2->co, v2_alt->co);
1476         normalize_v3(ed_dir_v1_new);
1477         normalize_v3(ed_dir_v2_new);
1478
1479         /* compare */
1480         cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v1_old);
1481         cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v1_new);
1482         if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
1483                 return false;
1484         }
1485         cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v2_old);
1486         cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v2_new);
1487         if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
1488                 return false;
1489         }
1490
1491         negate_v3_v3(ed_dir_new_flip, ed_dir_new);
1492
1493         /* result is zero area corner */
1494         if ((dot_v3v3(ed_dir_new,      ed_dir_v1_new) > 0.999f) ||
1495             (dot_v3v3(ed_dir_new_flip, ed_dir_v2_new) > 0.999f))
1496         {
1497                 return false;
1498         }
1499
1500         return true;
1501 }
1502
1503 bool BM_edge_rotate_check_beauty(BMEdge *e,
1504                                  BMLoop *l1, BMLoop *l2)
1505 {
1506         /* Stupid check for now:
1507          * Could compare angles of surrounding edges
1508          * before & after, but this is OK.*/
1509         return (len_squared_v3v3(e->v1->co, e->v2->co) >
1510                 len_squared_v3v3(l1->v->co, l2->v->co));
1511 }
1512
1513 /**
1514  * \brief Rotate Edge
1515  *
1516  * Spins an edge topologically,
1517  * either counter-clockwise or clockwise depending on \a ccw.
1518  *
1519  * \return The spun edge, NULL on error
1520  * (e.g., if the edge isn't surrounded by exactly two faces).
1521  *
1522  * \note This works by dissolving the edge then re-creating it,
1523  * so the returned edge won't have the same pointer address as the original one.
1524  *
1525  * \see header definition for \a check_flag enum.
1526  */
1527 BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_flag)
1528 {
1529         BMVert *v1, *v2;
1530         BMLoop *l1, *l2;
1531         BMFace *f;
1532         BMEdge *e_new = NULL;
1533         char f_hflag_prev_1;
1534         char f_hflag_prev_2;
1535
1536         if (!BM_edge_rotate_check(e)) {
1537                 return NULL;
1538         }
1539
1540         BM_edge_calc_rotate(e, ccw, &l1, &l2);
1541
1542         /* the loops will be freed so assign verts */
1543         v1 = l1->v;
1544         v2 = l2->v;
1545
1546         /* --------------------------------------- */
1547         /* Checking Code - make sure we can rotate */
1548
1549         if (check_flag & BM_EDGEROT_CHECK_BEAUTY) {
1550                 if (!BM_edge_rotate_check_beauty(e, l1, l2)) {
1551                         return NULL;
1552                 }
1553         }
1554
1555         /* check before applying */
1556         if (check_flag & BM_EDGEROT_CHECK_EXISTS) {
1557                 if (BM_edge_exists(v1, v2)) {
1558                         return NULL;
1559                 }
1560         }
1561
1562         /* slowest, check last */
1563         if (check_flag & BM_EDGEROT_CHECK_DEGENERATE) {
1564                 if (!BM_edge_rotate_check_degenerate(e, l1, l2)) {
1565                         return NULL;
1566                 }
1567         }
1568         /* Done Checking */
1569         /* ------------- */
1570
1571
1572
1573         /* --------------- */
1574         /* Rotate The Edge */
1575
1576         /* first create the new edge, this is so we can copy the customdata from the old one
1577          * if splice if disabled, always add in a new edge even if theres one there. */
1578         e_new = BM_edge_create(bm, v1, v2, e, (check_flag & BM_EDGEROT_CHECK_SPLICE) ? BM_CREATE_NO_DOUBLE : BM_CREATE_NOP);
1579
1580         f_hflag_prev_1 = l1->f->head.hflag;
1581         f_hflag_prev_2 = l2->f->head.hflag;
1582
1583         /* don't delete the edge, manually remove the edge after so we can copy its attributes */
1584         f = BM_faces_join_pair(bm, l1->f, l2->f, e, true);
1585
1586         if (f == NULL) {
1587                 return NULL;
1588         }
1589
1590         /* note, this assumes joining the faces _didnt_ also remove the verts.
1591          * the #BM_edge_rotate_check will ensure this, but its possibly corrupt state or future edits
1592          * break this */
1593         if ((l1 = BM_face_vert_share_loop(f, v1)) &&
1594             (l2 = BM_face_vert_share_loop(f, v2)) &&
1595             BM_face_split(bm, f, l1, l2, NULL, NULL, true))
1596         {
1597                 /* we should really be able to know the faces some other way,
1598                  * rather then fetching them back from the edge, but this is predictable
1599                  * where using the return values from face split isn't. - campbell */
1600                 BMFace *fa, *fb;
1601                 if (BM_edge_face_pair(e_new, &fa, &fb)) {
1602                         fa->head.hflag = f_hflag_prev_1;
1603                         fb->head.hflag = f_hflag_prev_2;
1604                 }
1605         }
1606         else {
1607                 return NULL;
1608         }
1609
1610         return e_new;
1611 }
1612
1613 /**
1614  * \brief Rip a single face from a vertex fan
1615  */
1616 BMVert *BM_face_vert_separate(BMesh *bm, BMFace *sf, BMVert *sv)
1617 {
1618         return bmesh_urmv(bm, sf, sv);
1619 }
1620
1621 /**
1622  * \brief Rip a single face from a vertex fan
1623  *
1624  * \note same as #BM_face_vert_separate but faster (avoids a loop lookup)
1625  */
1626 BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *sl)
1627 {
1628         return bmesh_urmv_loop(bm, sl);
1629 }