code cleanup: typos
[blender-staging.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_smallhash.h"
36
37 #include "BKE_customdata.h"
38
39 #include "bmesh.h"
40 #include "intern/bmesh_private.h"
41
42 /**
43  * \brief Dissolve Vert
44  *
45  * Turns the face region surrounding a manifold vertex into a single polygon.
46  *
47  * \par Example:
48  * <pre>
49  *              +---------+             +---------+
50  *              |  \   /  |             |         |
51  *     Before:  |    v    |      After: |         |
52  *              |  /   \  |             |         |
53  *              +---------+             +---------+
54  * </pre>
55  *
56  * This function can also collapse edges too
57  * in cases when it cant merge into faces.
58  *
59  * \par Example:
60  * <pre>
61  *     Before:  +----v----+      After: +---------+
62  * </pre>
63  *
64  * \note dissolves vert, in more situations then BM_disk_dissolve
65  * (e.g. if the vert is part of a wire edge, etc).
66  */
67 bool BM_vert_dissolve(BMesh *bm, BMVert *v)
68 {
69         const int len = BM_vert_edge_count(v);
70         
71         if (len == 1) {
72                 BM_vert_kill(bm, v); /* will kill edges too */
73                 return true;
74         }
75         else if (!BM_vert_is_manifold(v)) {
76                 if (!v->e) {
77                         BM_vert_kill(bm, v);
78                         return true;
79                 }
80                 else if (!v->e->l) {
81                         if (len == 2) {
82                                 return (BM_vert_collapse_edge(bm, v->e, v, true) != NULL);
83                         }
84                         else {
85                                 /* used to kill the vertex here, but it may be connected to faces.
86                                  * so better do nothing */
87                                 return false;
88                         }
89                 }
90                 else {
91                         return false;
92                 }
93         }
94         else if (len == 2 && BM_vert_face_count(v) == 1) {
95                 /* boundary vertex on a face */
96                 return (BM_vert_collapse_edge(bm, v->e, v, true) != NULL);
97         }
98         else {
99                 return BM_disk_dissolve(bm, v);
100         }
101 }
102
103 /**
104  * dissolves all faces around a vert, and removes it.
105  */
106 bool BM_disk_dissolve(BMesh *bm, BMVert *v)
107 {
108         BMFace *f, *f2;
109         BMEdge *e, *keepedge = NULL, *baseedge = NULL;
110         int len = 0;
111
112         if (!BM_vert_is_manifold(v)) {
113                 return false;
114         }
115         
116         if (v->e) {
117                 /* v->e we keep, what else */
118                 e = v->e;
119                 do {
120                         e = bmesh_disk_edge_next(e, v);
121                         if (!(BM_edge_share_face_check(e, v->e))) {
122                                 keepedge = e;
123                                 baseedge = v->e;
124                                 break;
125                         }
126                         len++;
127                 } while (e != v->e);
128         }
129         
130         /* this code for handling 2 and 3-valence verts
131          * may be totally bad */
132         if (keepedge == NULL && len == 3) {
133 #if 0
134                 /* handle specific case for three-valence.  solve it by
135                  * increasing valence to four.  this may be hackish. .  */
136                 BMLoop *loop = e->l;
137                 if (loop->v == v) loop = loop->next;
138                 if (!BM_face_split(bm, loop->f, v, loop->v, NULL, NULL, false))
139                         return false;
140
141                 if (!BM_disk_dissolve(bm, v)) {
142                         return false;
143                 }
144 #else
145                 if (UNLIKELY(!BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e, true))) {
146                         return false;
147                 }
148                 else if (UNLIKELY(!BM_vert_collapse_faces(bm, v->e, v, 1.0, false, true))) {
149                         return false;
150                 }
151 #endif
152                 return true;
153         }
154         else if (keepedge == NULL && len == 2) {
155                 /* collapse the vertex */
156                 e = BM_vert_collapse_faces(bm, v->e, v, 1.0, true, true);
157
158                 if (!e) {
159                         return false;
160                 }
161
162                 /* handle two-valence */
163                 f = e->l->f;
164                 f2 = e->l->radial_next->f;
165
166                 if (f != f2 && !BM_faces_join_pair(bm, f, f2, e, true)) {
167                         return false;
168                 }
169
170                 return true;
171         }
172
173         if (keepedge) {
174                 bool done = false;
175
176                 while (!done) {
177                         done = true;
178                         e = v->e;
179                         do {
180                                 f = NULL;
181                                 len = bmesh_radial_length(e->l);
182                                 if (len == 2 && (e != baseedge) && (e != keepedge)) {
183                                         f = BM_faces_join_pair(bm, e->l->f, e->l->radial_next->f, e, true);
184                                         /* return if couldn't join faces in manifold
185                                          * conditions */
186                                         /* !disabled for testing why bad things happen */
187                                         if (!f) {
188                                                 return false;
189                                         }
190                                 }
191
192                                 if (f) {
193                                         done = false;
194                                         break;
195                                 }
196                                 e = bmesh_disk_edge_next(e, v);
197                         } while (e != v->e);
198                 }
199
200                 /* collapse the vertex */
201                 /* note, the baseedge can be a boundary of manifold, use this as join_faces arg */
202                 e = BM_vert_collapse_faces(bm, baseedge, v, 1.0, !BM_edge_is_boundary(baseedge), true);
203
204                 if (!e) {
205                         return false;
206                 }
207                 
208                 /* get remaining two faces */
209                 f = e->l->f;
210                 f2 = e->l->radial_next->f;
211
212                 if (f != f2) {
213                         /* join two remaining faces */
214                         if (!BM_faces_join_pair(bm, f, f2, e, true)) {
215                                 return false;
216                         }
217                 }
218         }
219
220         return true;
221 }
222
223 /**
224  * \brief Faces Join Pair
225  *
226  * Joins two adjacent faces together.
227  *
228  * Because this method calls to #BM_faces_join to do its work, if a pair
229  * of faces share multiple edges, the pair of faces will be joined at
230  * every edge (not just edge \a e). This part of the functionality might need
231  * to be reconsidered.
232  *
233  * If the windings do not match the winding of the new face will follow
234  * \a f1's winding (i.e. \a f2 will be reversed before the join).
235  *
236  * \return pointer to the combined face
237  */
238 BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e, const bool do_del)
239 {
240         BMLoop *l1, *l2;
241         BMEdge *jed = NULL;
242         BMFace *faces[2] = {f1, f2};
243         
244         jed = e;
245         if (!jed) {
246                 BMLoop *l_first;
247                 /* search for an edge that has both these faces in its radial cycle */
248                 l1 = l_first = BM_FACE_FIRST_LOOP(f1);
249                 do {
250                         if (l1->radial_next->f == f2) {
251                                 jed = l1->e;
252                                 break;
253                         }
254                 } while ((l1 = l1->next) != l_first);
255         }
256
257         if (UNLIKELY(!jed)) {
258                 BMESH_ASSERT(0);
259                 return NULL;
260         }
261         
262         l1 = jed->l;
263         
264         if (UNLIKELY(!l1)) {
265                 BMESH_ASSERT(0);
266                 return NULL;
267         }
268         
269         l2 = l1->radial_next;
270         if (l1->v == l2->v) {
271                 bmesh_loop_reverse(bm, f2);
272         }
273
274         f1 = BM_faces_join(bm, faces, 2, do_del);
275         
276         return f1;
277 }
278
279 /**
280  * \brief Connect Verts, Split Face
281  *
282  * connects two verts together, automatically (if very naively) finding the
283  * face they both share (if there is one) and splitting it.  Use this at your
284  * own risk, as it doesn't handle the many complex cases it should (like zero-area faces,
285  * multiple faces, etc).
286  *
287  * this is really only meant for cases where you don't know before hand the face
288  * the two verts belong to for splitting (e.g. the subdivision operator).
289  *
290  * \return The newly created edge.
291  */
292 BMEdge *BM_verts_connect(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **r_f)
293 {
294         BMIter fiter;
295         BMIter viter;
296         BMVert *v_iter;
297         BMFace *f_iter;
298
299         /* be warned: this can do weird things in some ngon situation, see BM_face_legal_splits */
300         BM_ITER_ELEM (f_iter, &fiter, v1, BM_FACES_OF_VERT) {
301                 BM_ITER_ELEM (v_iter, &viter, f_iter, BM_FACES_OF_VERT) {
302                         if (v_iter == v2) {
303                                 BMLoop *l_new;
304
305                                 f_iter = BM_face_split(bm, f_iter, v1, v2, &l_new, NULL, false);
306
307                                 if (r_f) {
308                                         *r_f = f_iter;
309                                 }
310                                 return l_new->e;
311                         }
312                 }
313         }
314
315         if (r_f) {
316                 *r_f = NULL;
317         }
318         return NULL;
319 }
320
321 /**
322  * \brief Face Split
323  *
324  * Split a face along two vertices. returns the newly made face, and sets
325  * the \a r_l member to a loop in the newly created edge.
326  *
327  * \param bm The bmesh
328  * \param f the original face
329  * \param v1, v2 vertices which define the split edge, must be different
330  * \param r_l pointer which will receive the BMLoop for the split edge in the new face
331  * \param example Edge used for attributes of splitting edge, if non-NULL
332  * \param nodouble Use an existing edge if found
333  *
334  * \return Pointer to the newly created face representing one side of the split
335  * if the split is successful (and the original original face will be the
336  * other side). NULL if the split fails.
337  */
338 BMFace *BM_face_split(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **r_l,
339                       BMEdge *example, const bool no_double)
340 {
341         const bool has_mdisp = CustomData_has_layer(&bm->ldata, CD_MDISPS);
342         BMFace *f_new, *f_tmp;
343
344         BLI_assert(v1 != v2);
345
346         /* do we have a multires layer? */
347         if (has_mdisp) {
348                 f_tmp = BM_face_copy(bm, bm, f, false, false);
349         }
350         
351 #ifdef USE_BMESH_HOLES
352         f_new = bmesh_sfme(bm, f, v1, v2, r_l, NULL, example, no_double);
353 #else
354         f_new = bmesh_sfme(bm, f, v1, v2, r_l, example, no_double);
355 #endif
356         
357         if (f_new) {
358                 BM_elem_attrs_copy(bm, bm, f, f_new);
359                 copy_v3_v3(f_new->no, f->no);
360
361                 /* handle multires update */
362                 if (has_mdisp && (f_new != f)) {
363                         BMLoop *l_iter;
364                         BMLoop *l_first;
365
366                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
367                         do {
368                                 BM_loop_interp_multires(bm, l_iter, f_tmp);
369                         } while ((l_iter = l_iter->next) != l_first);
370
371                         l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
372                         do {
373                                 BM_loop_interp_multires(bm, l_iter, f_tmp);
374                         } while ((l_iter = l_iter->next) != l_first);
375
376                         BM_face_kill(bm, f_tmp);
377
378 #if 0
379                         /* BM_face_multires_bounds_smooth doesn't flip displacement correct */
380                         BM_face_multires_bounds_smooth(bm, f);
381                         BM_face_multires_bounds_smooth(bm, f_new);
382 #endif
383                 }
384         }
385
386         return f_new;
387 }
388
389 /**
390  * \brief Face Split with intermediate points
391  *
392  * Like BM_face_split, but with an edge split by \a n intermediate points with given coordinates.
393  *
394  * \param bm The bmesh
395  * \param f the original face
396  * \param v1, v2 vertices which define the split edge, must be different
397  * \param cos Array of coordinates for intermediate points
398  * \param n Length of \a cos (must be > 0)
399  * \param r_l pointer which will receive the BMLoop for the first split edge (from \a v1) in the new face
400  * \param example Edge used for attributes of splitting edge, if non-NULL
401  *
402  * \return Pointer to the newly created face representing one side of the split
403  * if the split is successful (and the original original face will be the
404  * other side). NULL if the split fails.
405  */
406 BMFace *BM_face_split_n(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, float cos[][3], int n,
407                         BMLoop **r_l, BMEdge *example)
408 {
409         BMFace *f_new, *f_tmp;
410         BMLoop *l_dummy;
411         BMEdge *e, *e_new;
412         BMVert *v_new;
413         int i, j;
414
415         BLI_assert(v1 != v2);
416
417         f_tmp = BM_face_copy(bm, bm, f, true, true);
418
419         if (!r_l)
420                 r_l = &l_dummy;
421         
422 #ifdef USE_BMESH_HOLES
423         f_new = bmesh_sfme(bm, f, v1, v2, r_l, NULL, example, false);
424 #else
425         f_new = bmesh_sfme(bm, f, v1, v2, r_l, example, false);
426 #endif
427         /* bmesh_sfme returns in r_l a Loop for f_new going from v1 to v2.
428          * The radial_next is for f and goes from v2 to v1  */
429
430         if (f_new) {
431                 BM_elem_attrs_copy(bm, bm, f, f_new);
432                 copy_v3_v3(f_new->no, f->no);
433
434                 e = (*r_l)->e;
435                 for (i = 0; i < n; i++) {
436                         v_new = bmesh_semv(bm, v2, e, &e_new);
437                         BLI_assert(v_new != NULL);
438                         /* bmesh_semv returns in e_new the edge going from v_new to tv */
439                         copy_v3_v3(v_new->co, cos[i]);
440
441                         /* interpolate the loop data for the loops with (v == v_new), using orig face */
442                         for (j = 0; j < 2; j++) {
443                                 BMEdge *e_iter = (j == 0) ? e : e_new;
444                                 BMLoop *l_iter = e_iter->l;
445                                 do {
446                                         if (l_iter->v == v_new) {
447                                                 /* this interpolates both loop and vertex data */
448                                                 BM_loop_interp_from_face(bm, l_iter, f_tmp, true, true);
449                                         }
450                                 } while ((l_iter = l_iter->radial_next) != e_iter->l);
451                         }
452                         e = e_new;
453                 }
454         }
455
456         BM_face_verts_kill(bm, f_tmp);
457
458         return f_new;
459 }
460
461 /**
462  * \brief Vert Collapse Faces
463  *
464  * Collapses vertex \a v_kill that has only two manifold edges
465  * onto a vertex it shares an edge with.
466  * \a fac defines the amount of interpolation for Custom Data.
467  *
468  * \note that this is not a general edge collapse function.
469  *
470  * \note this function is very close to #BM_vert_collapse_edge,
471  * both collapse a vertex and return a new edge.
472  * Except this takes a factor and merges custom data.
473  *
474  * \param bm The bmesh
475  * \param e_kill The edge to collapse
476  * \param v_kill The vertex  to collapse into the edge
477  * \param fac The factor along the edge
478  * \param join_faces When true the faces around the vertex will be joined
479  * otherwise collapse the vertex by merging the 2 edges this vert touches into one.
480  * \param kill_degenerate_faces Removes faces with less than 3 verts after collapsing.
481  *
482  * \returns The New Edge
483  */
484 BMEdge *BM_vert_collapse_faces(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, float fac,
485                                const bool join_faces, const bool kill_degenerate_faces)
486 {
487         BMEdge *e_new = NULL;
488         BMVert *tv = bmesh_edge_other_vert_get(e_kill, v_kill);
489
490         BMEdge *e2;
491         BMVert *tv2;
492
493         BMIter iter;
494         BMLoop *l_iter = NULL, *kvloop = NULL, *tvloop = NULL;
495
496         void *src[2];
497         float w[2];
498
499         /* Only intended to be called for 2-valence vertices */
500         BLI_assert(bmesh_disk_count(v_kill) <= 2);
501
502
503         /* first modify the face loop data  */
504         w[0] = 1.0f - fac;
505         w[1] = fac;
506
507         if (e_kill->l) {
508                 l_iter = e_kill->l;
509                 do {
510                         if (l_iter->v == tv && l_iter->next->v == v_kill) {
511                                 tvloop = l_iter;
512                                 kvloop = l_iter->next;
513
514                                 src[0] = kvloop->head.data;
515                                 src[1] = tvloop->head.data;
516                                 CustomData_bmesh_interp(&bm->ldata, src, w, NULL, 2, kvloop->head.data);
517                         }
518                 } while ((l_iter = l_iter->radial_next) != e_kill->l);
519         }
520
521         /* now interpolate the vertex data */
522         BM_data_interp_from_verts(bm, v_kill, tv, v_kill, fac);
523
524         e2 = bmesh_disk_edge_next(e_kill, v_kill);
525         tv2 = BM_edge_other_vert(e2, v_kill);
526
527         if (join_faces) {
528                 BMFace **faces = NULL;
529                 BMFace *f;
530                 BLI_array_staticdeclare(faces, 8);
531
532                 BM_ITER_ELEM (f, &iter, v_kill, BM_FACES_OF_VERT) {
533                         BLI_array_append(faces, f);
534                 }
535
536                 if (BLI_array_count(faces) >= 2) {
537                         BMFace *f2 = BM_faces_join(bm, faces, BLI_array_count(faces), true);
538                         if (f2) {
539                                 BMLoop *l_new = NULL;
540                                 if (BM_face_split(bm, f2, tv, tv2, &l_new, NULL, false)) {
541                                         e_new = l_new->e;
542                                 }
543                         }
544                 }
545
546                 BLI_array_free(faces);
547         }
548         else {
549                 /* single face or no faces */
550                 /* same as BM_vert_collapse_edge() however we already
551                  * have vars to perform this operation so don't call. */
552                 e_new = bmesh_jekv(bm, e_kill, v_kill, true);
553                 /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */
554
555                 if (e_new && kill_degenerate_faces) {
556                         BLI_array_declare(bad_faces);
557                         BMFace **bad_faces = NULL;
558
559                         BMIter fiter;
560                         BMFace *f;
561                         BMVert *verts[2] = {e_new->v1, e_new->v2};
562                         int i;
563
564                         for (i = 0; i < 2; i++) {
565                                 /* cant kill data we loop on, build a list and remove those */
566                                 BLI_array_empty(bad_faces);
567                                 BM_ITER_ELEM (f, &fiter, verts[i], BM_FACES_OF_VERT) {
568                                         if (UNLIKELY(f->len < 3)) {
569                                                 BLI_array_append(bad_faces, f);
570                                         }
571                                 }
572                                 while ((f = BLI_array_pop(bad_faces))) {
573                                         BM_face_kill(bm, f);
574                                 }
575                         }
576                         BLI_array_free(bad_faces);
577                 }
578         }
579
580         return e_new;
581 }
582
583
584 /**
585  * \brief Vert Collapse Faces
586  *
587  * Collapses a vertex onto another vertex it shares an edge with.
588  *
589  * \return The New Edge
590  */
591 BMEdge *BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill,
592                               const bool kill_degenerate_faces)
593 {
594         /* nice example implementation but we want loops to have their customdata
595          * accounted for */
596 #if 0
597         BMEdge *e_new = NULL;
598
599         /* Collapse between 2 edges */
600
601         /* in this case we want to keep all faces and not join them,
602          * rather just get rid of the vertex - see bug [#28645] */
603         BMVert *tv  = bmesh_edge_other_vert_get(e_kill, v_kill);
604         if (tv) {
605                 BMEdge *e2 = bmesh_disk_edge_next(e_kill, v_kill);
606                 if (e2) {
607                         BMVert *tv2 = BM_edge_other_vert(e2, v_kill);
608                         if (tv2) {
609                                 /* only action, other calls here only get the edge to return */
610                                 e_new = bmesh_jekv(bm, e_kill, v_kill);
611
612                                 /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */
613                         }
614                 }
615         }
616
617         return e_new;
618 #else
619         /* with these args faces are never joined, same as above
620          * but account for loop customdata */
621         return BM_vert_collapse_faces(bm, e_kill, v_kill, 1.0f, false, kill_degenerate_faces);
622 #endif
623 }
624
625 #undef DO_V_INTERP
626
627 /**
628  * \brief Edge Split
629  *
630  * Splits an edge. \a v should be one of the vertices in \a e and defines
631  * the "from" end of the splitting operation: the new vertex will be
632  * \a percent of the way from \a v to the other end.
633  * The newly created edge is attached to \a v and is returned in \a r_e.
634  * The original edge \a e will be the other half of the split.
635  *
636  * \return The new vert
637  */
638 BMVert *BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float percent)
639 {
640         BMVert *v_new, *v2;
641         BMFace **oldfaces = NULL;
642         BMEdge *e_dummy;
643         BLI_array_staticdeclare(oldfaces, 32);
644         const bool do_mdisp = (e->l && CustomData_has_layer(&bm->ldata, CD_MDISPS));
645
646         /* we need this for handling multi-res */
647         if (!r_e) {
648                 r_e = &e_dummy;
649         }
650
651         /* do we have a multi-res layer? */
652         if (do_mdisp) {
653                 BMLoop *l;
654                 int i;
655                 
656                 l = e->l;
657                 do {
658                         BLI_array_append(oldfaces, l->f);
659                         l = l->radial_next;
660                 } while (l != e->l);
661                 
662                 /* flag existing faces so we can differentiate oldfaces from new faces */
663                 for (i = 0; i < BLI_array_count(oldfaces); i++) {
664                         BM_ELEM_API_FLAG_ENABLE(oldfaces[i], _FLAG_OVERLAP);
665                         oldfaces[i] = BM_face_copy(bm, bm, oldfaces[i], true, true);
666                         BM_ELEM_API_FLAG_DISABLE(oldfaces[i], _FLAG_OVERLAP);
667                 }
668         }
669
670         v2 = bmesh_edge_other_vert_get(e, v);
671         v_new = bmesh_semv(bm, v, e, r_e);
672
673         BLI_assert(v_new != NULL);
674
675         sub_v3_v3v3(v_new->co, v2->co, v->co);
676         madd_v3_v3v3fl(v_new->co, v->co, v_new->co, percent);
677
678         if (r_e) {
679                 (*r_e)->head.hflag = e->head.hflag;
680                 BM_elem_attrs_copy(bm, bm, e, *r_e);
681         }
682
683         /* v->v_new->v2 */
684         BM_data_interp_face_vert_edge(bm, v2, v, v_new, e, percent);
685         BM_data_interp_from_verts(bm, v, v2, v_new, percent);
686
687         if (do_mdisp) {
688                 int i, j;
689
690                 /* interpolate new/changed loop data from copied old faces */
691                 for (j = 0; j < 2; j++) {
692                         for (i = 0; i < BLI_array_count(oldfaces); i++) {
693                                 BMEdge *e1 = j ? *r_e : e;
694                                 BMLoop *l, *l2;
695                                 
696                                 l = e1->l;
697
698                                 if (UNLIKELY(!l)) {
699                                         BMESH_ASSERT(0);
700                                         break;
701                                 }
702                                 
703                                 do {
704                                         /* check this is an old face */
705                                         if (BM_ELEM_API_FLAG_TEST(l->f, _FLAG_OVERLAP)) {
706                                                 BMLoop *l2_first;
707
708                                                 l2 = l2_first = BM_FACE_FIRST_LOOP(l->f);
709                                                 do {
710                                                         BM_loop_interp_multires(bm, l2, oldfaces[i]);
711                                                 } while ((l2 = l2->next) != l2_first);
712                                         }
713                                         l = l->radial_next;
714                                 } while (l != e1->l);
715                         }
716                 }
717                 
718                 /* destroy the old faces */
719                 for (i = 0; i < BLI_array_count(oldfaces); i++) {
720                         BM_face_verts_kill(bm, oldfaces[i]);
721                 }
722                 
723                 /* fix boundaries a bit, doesn't work too well quite yet */
724 #if 0
725                 for (j = 0; j < 2; j++) {
726                         BMEdge *e1 = j ? *r_e : e;
727                         BMLoop *l, *l2;
728                         
729                         l = e1->l;
730                         if (UNLIKELY(!l)) {
731                                 BMESH_ASSERT(0);
732                                 break;
733                         }
734                         
735                         do {
736                                 BM_face_multires_bounds_smooth(bm, l->f);
737                                 l = l->radial_next;
738                         } while (l != e1->l);
739                 }
740 #endif
741                 
742                 BLI_array_free(oldfaces);
743         }
744
745         return v_new;
746 }
747
748 /**
749  * \brief Split an edge multiple times evenly
750  *
751  * \param r_varr  Optional array, verts in between (v1 -> v2)
752  */
753 BMVert  *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts, BMVert **r_varr)
754 {
755         int i;
756         float percent;
757         BMVert *v_new = NULL;
758         
759         for (i = 0; i < numcuts; i++) {
760                 percent = 1.0f / (float)(numcuts + 1 - i);
761                 v_new = BM_edge_split(bm, e, e->v2, NULL, percent);
762                 if (r_varr) {
763                         /* fill in reverse order (v1 -> v2) */
764                         r_varr[numcuts - i - 1] = v_new;
765                 }
766         }
767         return v_new;
768 }
769
770 #if 0
771 /**
772  * Checks if a face is valid in the data structure
773  */
774 bool BM_face_validate(BMFace *face, FILE *err)
775 {
776         BMIter iter;
777         BLI_array_declare(verts);
778         BMVert **verts = NULL;
779         BMLoop *l;
780         int i, j;
781         bool ret = true;
782         
783         if (face->len == 2) {
784                 fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
785                 fflush(err);
786         }
787
788         BLI_array_grow_items(verts, face->len);
789         BM_ITER_ELEM_INDEX (l, &iter, face, BM_LOOPS_OF_FACE, i) {
790                 verts[i] = l->v;
791                 if (l->e->v1 == l->e->v2) {
792                         fprintf(err, "Found bmesh edge with identical verts!\n");
793                         fprintf(err, "  edge ptr: %p, vert: %p\n",  l->e, l->e->v1);
794                         fflush(err);
795                         ret = false;
796                 }
797         }
798
799         for (i = 0; i < face->len; i++) {
800                 for (j = 0; j < face->len; j++) {
801                         if (j == i) {
802                                 continue;
803                         }
804
805                         if (verts[i] == verts[j]) {
806                                 fprintf(err, "Found duplicate verts in bmesh face!\n");
807                                 fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
808                                 fflush(err);
809                                 ret = false;
810                         }
811                 }
812         }
813         
814         BLI_array_free(verts);
815         return ret;
816 }
817 #endif
818
819 /**
820  * Calculate the 2 loops which _would_ make up the newly rotated Edge
821  * but don't actually change anything.
822  *
823  * Use this to further inspect if the loops to be connected have issues:
824  *
825  * Examples:
826  * - the newly formed edge already exists
827  * - the new face would be degenerate (zero area / concave /  bow-tie)
828  * - may want to measure if the new edge gives improved results topology.
829  *   over the old one, as with beauty fill.
830  *
831  * \note #BM_edge_rotate_check must have already run.
832  */
833 void BM_edge_calc_rotate(BMEdge *e, const bool ccw,
834                          BMLoop **r_l1, BMLoop **r_l2)
835 {
836         BMVert *v1, *v2;
837         BMFace *fa, *fb;
838
839         /* this should have already run */
840         BLI_assert(BM_edge_rotate_check(e) == true);
841
842         /* we know this will work */
843         BM_edge_face_pair(e, &fa, &fb);
844
845         /* so we can use ccw variable correctly,
846          * otherwise we could use the edges verts direct */
847         BM_edge_ordered_verts(e, &v1, &v2);
848
849         /* we could swap the verts _or_ the faces, swapping faces
850          * gives more predictable results since that way the next vert
851          * just stitches from face fa / fb */
852         if (ccw) {
853                 SWAP(BMFace *, fa, fb);
854         }
855
856         *r_l1 = BM_face_other_vert_loop(fb, v2, v1);
857         *r_l2 = BM_face_other_vert_loop(fa, v1, v2);
858 }
859
860 /**
861  * \brief Check if Rotate Edge is OK
862  *
863  * Quick check to see if we could rotate the edge,
864  * use this to avoid calling exceptions on common cases.
865  */
866 bool BM_edge_rotate_check(BMEdge *e)
867 {
868         BMFace *fa, *fb;
869         if (BM_edge_face_pair(e, &fa, &fb)) {
870                 BMLoop *la, *lb;
871
872                 la = BM_face_other_vert_loop(fa, e->v2, e->v1);
873                 lb = BM_face_other_vert_loop(fb, e->v2, e->v1);
874
875                 /* check that the next vert in both faces isn't the same
876                  * (ie - the next edge doesn't share the same faces).
877                  * since we can't rotate usefully in this case. */
878                 if (la->v == lb->v) {
879                         return false;
880                 }
881
882                 /* mirror of the check above but in the opposite direction */
883                 la = BM_face_other_vert_loop(fa, e->v1, e->v2);
884                 lb = BM_face_other_vert_loop(fb, e->v1, e->v2);
885
886                 if (la->v == lb->v) {
887                         return false;
888                 }
889
890                 return true;
891         }
892         else {
893                 return false;
894         }
895 }
896
897 /**
898  * \brief Check if Edge Rotate Gives Degenerate Faces
899  *
900  * Check 2 cases
901  * 1) does the newly forms edge form a flipped face (compare with previous cross product)
902  * 2) does the newly formed edge cause a zero area corner (or close enough to be almost zero)
903  *
904  * \param e The edge to test rotation.
905  * \param l1,l2 are the loops of the proposed verts to rotate too and should
906  * be the result of calling #BM_edge_calc_rotate
907  */
908 bool BM_edge_rotate_check_degenerate(BMEdge *e, BMLoop *l1, BMLoop *l2)
909 {
910         /* note: for these vars 'old' just means initial edge state. */
911
912         float ed_dir_old[3]; /* edge vector */
913         float ed_dir_new[3]; /* edge vector */
914         float ed_dir_new_flip[3]; /* edge vector */
915
916         float ed_dir_v1_old[3];
917         float ed_dir_v2_old[3];
918
919         float ed_dir_v1_new[3];
920         float ed_dir_v2_new[3];
921
922         float cross_old[3];
923         float cross_new[3];
924
925         /* original verts - these will be in the edge 'e' */
926         BMVert *v1_old, *v2_old;
927
928         /* verts from the loops passed */
929
930         BMVert *v1, *v2;
931         /* these are the opposite verts - the verts that _would_ be used if 'ccw' was inverted*/
932         BMVert *v1_alt, *v2_alt;
933
934         /* this should have already run */
935         BLI_assert(BM_edge_rotate_check(e) == true);
936
937         BM_edge_ordered_verts(e, &v1_old, &v2_old);
938
939         v1 = l1->v;
940         v2 = l2->v;
941
942         /* get the next vert along */
943         v1_alt = BM_face_other_vert_loop(l1->f, v1_old, v1)->v;
944         v2_alt = BM_face_other_vert_loop(l2->f, v2_old, v2)->v;
945
946         /* normalize all so comparisons are scale independent */
947
948         BLI_assert(BM_edge_exists(v1_old, v1));
949         BLI_assert(BM_edge_exists(v1, v1_alt));
950
951         BLI_assert(BM_edge_exists(v2_old, v2));
952         BLI_assert(BM_edge_exists(v2, v2_alt));
953
954         /* old and new edge vecs */
955         sub_v3_v3v3(ed_dir_old, v1_old->co, v2_old->co);
956         sub_v3_v3v3(ed_dir_new, v1->co, v2->co);
957         normalize_v3(ed_dir_old);
958         normalize_v3(ed_dir_new);
959
960         /* old edge corner vecs */
961         sub_v3_v3v3(ed_dir_v1_old, v1_old->co, v1->co);
962         sub_v3_v3v3(ed_dir_v2_old, v2_old->co, v2->co);
963         normalize_v3(ed_dir_v1_old);
964         normalize_v3(ed_dir_v2_old);
965
966         /* old edge corner vecs */
967         sub_v3_v3v3(ed_dir_v1_new, v1->co, v1_alt->co);
968         sub_v3_v3v3(ed_dir_v2_new, v2->co, v2_alt->co);
969         normalize_v3(ed_dir_v1_new);
970         normalize_v3(ed_dir_v2_new);
971
972         /* compare */
973         cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v1_old);
974         cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v1_new);
975         if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
976                 return false;
977         }
978         cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v2_old);
979         cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v2_new);
980         if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
981                 return false;
982         }
983
984         negate_v3_v3(ed_dir_new_flip, ed_dir_new);
985
986         /* result is zero area corner */
987         if ((dot_v3v3(ed_dir_new,      ed_dir_v1_new) > 0.999f) ||
988             (dot_v3v3(ed_dir_new_flip, ed_dir_v2_new) > 0.999f))
989         {
990                 return false;
991         }
992
993         return true;
994 }
995
996 bool BM_edge_rotate_check_beauty(BMEdge *e,
997                                  BMLoop *l1, BMLoop *l2)
998 {
999         /* Stupid check for now:
1000          * Could compare angles of surrounding edges
1001          * before & after, but this is OK.*/
1002         return (len_squared_v3v3(e->v1->co, e->v2->co) >
1003                 len_squared_v3v3(l1->v->co, l2->v->co));
1004 }
1005
1006 /**
1007  * \brief Rotate Edge
1008  *
1009  * Spins an edge topologically,
1010  * either counter-clockwise or clockwise depending on \a ccw.
1011  *
1012  * \return The spun edge, NULL on error
1013  * (e.g., if the edge isn't surrounded by exactly two faces).
1014  *
1015  * \note This works by dissolving the edge then re-creating it,
1016  * so the returned edge won't have the same pointer address as the original one.
1017  *
1018  * \see header definition for \a check_flag enum.
1019  */
1020 BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_flag)
1021 {
1022         BMVert *v1, *v2;
1023         BMLoop *l1, *l2;
1024         BMFace *f;
1025         BMEdge *e_new = NULL;
1026         char f_hflag_prev_1;
1027         char f_hflag_prev_2;
1028
1029         if (!BM_edge_rotate_check(e)) {
1030                 return NULL;
1031         }
1032
1033         BM_edge_calc_rotate(e, ccw, &l1, &l2);
1034
1035         /* the loops will be freed so assign verts */
1036         v1 = l1->v;
1037         v2 = l2->v;
1038
1039         /* --------------------------------------- */
1040         /* Checking Code - make sure we can rotate */
1041
1042         if (check_flag & BM_EDGEROT_CHECK_BEAUTY) {
1043                 if (!BM_edge_rotate_check_beauty(e, l1, l2)) {
1044                         return NULL;
1045                 }
1046         }
1047
1048         /* check before applying */
1049         if (check_flag & BM_EDGEROT_CHECK_EXISTS) {
1050                 if (BM_edge_exists(v1, v2)) {
1051                         return NULL;
1052                 }
1053         }
1054
1055         /* slowest, check last */
1056         if (check_flag & BM_EDGEROT_CHECK_DEGENERATE) {
1057                 if (!BM_edge_rotate_check_degenerate(e, l1, l2)) {
1058                         return NULL;
1059                 }
1060         }
1061         /* Done Checking */
1062         /* ------------- */
1063
1064
1065
1066         /* --------------- */
1067         /* Rotate The Edge */
1068
1069         /* first create the new edge, this is so we can copy the customdata from the old one
1070          * if splice if disabled, always add in a new edge even if theres one there. */
1071         e_new = BM_edge_create(bm, v1, v2, e, (check_flag & BM_EDGEROT_CHECK_SPLICE) != 0);
1072
1073         f_hflag_prev_1 = l1->f->head.hflag;
1074         f_hflag_prev_2 = l2->f->head.hflag;
1075
1076         /* don't delete the edge, manually remove the edge after so we can copy its attributes */
1077         f = BM_faces_join_pair(bm, l1->f, l2->f, NULL, true);
1078
1079         if (f == NULL) {
1080                 return NULL;
1081         }
1082
1083         /* note, this assumes joining the faces _didnt_ also remove the verts.
1084          * the #BM_edge_rotate_check will ensure this, but its possibly corrupt state or future edits
1085          * break this */
1086         if (!BM_face_split(bm, f, v1, v2, NULL, NULL, true)) {
1087                 return NULL;
1088         }
1089         else {
1090                 /* we should really be able to know the faces some other way,
1091                  * rather then fetching them back from the edge, but this is predictable
1092                  * where using the return values from face split isn't. - campbell */
1093                 BMFace *fa, *fb;
1094                 if (BM_edge_face_pair(e_new, &fa, &fb)) {
1095                         fa->head.hflag = f_hflag_prev_1;
1096                         fb->head.hflag = f_hflag_prev_2;
1097                 }
1098         }
1099
1100         return e_new;
1101 }
1102
1103 /**
1104  * \brief Rip a single face from a vertex fan
1105  */
1106 BMVert *BM_face_vert_separate(BMesh *bm, BMFace *sf, BMVert *sv)
1107 {
1108         return bmesh_urmv(bm, sf, sv);
1109 }
1110
1111 /**
1112  * \brief Rip a single face from a vertex fan
1113  *
1114  * \note same as #BM_face_vert_separate but faster (avoids a loop lookup)
1115  */
1116 BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *sl)
1117 {
1118         return bmesh_urmv_loop(bm, sl);
1119 }