Merging r58475 through r58700 from trunk into soc-2013-depsgraph_mt
[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_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         /* Only intended to be called for 2-valence vertices */
494         BLI_assert(bmesh_disk_count(v_kill) <= 2);
495
496
497         /* first modify the face loop data */
498
499         if (e_kill->l) {
500                 BMLoop *l_iter;
501                 const float w[2] = {1.0f - fac, fac};
502
503                 l_iter = e_kill->l;
504                 do {
505                         if (l_iter->v == tv && l_iter->next->v == v_kill) {
506                                 void *src[2];
507                                 BMLoop *tvloop = l_iter;
508                                 BMLoop *kvloop = l_iter->next;
509
510                                 src[0] = kvloop->head.data;
511                                 src[1] = tvloop->head.data;
512                                 CustomData_bmesh_interp(&bm->ldata, src, w, NULL, 2, kvloop->head.data);
513                         }
514                 } while ((l_iter = l_iter->radial_next) != e_kill->l);
515         }
516
517         /* now interpolate the vertex data */
518         BM_data_interp_from_verts(bm, v_kill, tv, v_kill, fac);
519
520         e2 = bmesh_disk_edge_next(e_kill, v_kill);
521         tv2 = BM_edge_other_vert(e2, v_kill);
522
523         if (join_faces) {
524                 BMIter fiter;
525                 BMFace **faces = NULL;
526                 BMFace *f;
527                 BLI_array_staticdeclare(faces, BM_DEFAULT_ITER_STACK_SIZE);
528
529                 BM_ITER_ELEM (f, &fiter, v_kill, BM_FACES_OF_VERT) {
530                         BLI_array_append(faces, f);
531                 }
532
533                 if (BLI_array_count(faces) >= 2) {
534                         BMFace *f2 = BM_faces_join(bm, faces, BLI_array_count(faces), true);
535                         if (f2) {
536                                 BMLoop *l_new = NULL;
537                                 if (BM_face_split(bm, f2, tv, tv2, &l_new, NULL, false)) {
538                                         e_new = l_new->e;
539                                 }
540                         }
541                 }
542
543                 BLI_assert(BLI_array_count(faces) < 8);
544
545                 BLI_array_free(faces);
546         }
547         else {
548                 /* single face or no faces */
549                 /* same as BM_vert_collapse_edge() however we already
550                  * have vars to perform this operation so don't call. */
551                 e_new = bmesh_jekv(bm, e_kill, v_kill, true);
552                 /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */
553
554                 if (e_new && kill_degenerate_faces) {
555                         BMFace **bad_faces = NULL;
556                         BLI_array_staticdeclare(bad_faces, BM_DEFAULT_ITER_STACK_SIZE);
557
558                         BMIter fiter;
559                         BMFace *f;
560                         BMVert *verts[2] = {e_new->v1, e_new->v2};
561                         int i;
562
563                         for (i = 0; i < 2; i++) {
564                                 /* cant kill data we loop on, build a list and remove those */
565                                 BLI_array_empty(bad_faces);
566                                 BM_ITER_ELEM (f, &fiter, verts[i], BM_FACES_OF_VERT) {
567                                         if (UNLIKELY(f->len < 3)) {
568                                                 BLI_array_append(bad_faces, f);
569                                         }
570                                 }
571                                 while ((f = BLI_array_pop(bad_faces))) {
572                                         BM_face_kill(bm, f);
573                                 }
574                         }
575                         BLI_array_free(bad_faces);
576                 }
577         }
578
579         return e_new;
580 }
581
582
583 /**
584  * \brief Vert Collapse Faces
585  *
586  * Collapses a vertex onto another vertex it shares an edge with.
587  *
588  * \return The New Edge
589  */
590 BMEdge *BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill,
591                               const bool kill_degenerate_faces)
592 {
593         /* nice example implementation but we want loops to have their customdata
594          * accounted for */
595 #if 0
596         BMEdge *e_new = NULL;
597
598         /* Collapse between 2 edges */
599
600         /* in this case we want to keep all faces and not join them,
601          * rather just get rid of the vertex - see bug [#28645] */
602         BMVert *tv  = bmesh_edge_other_vert_get(e_kill, v_kill);
603         if (tv) {
604                 BMEdge *e2 = bmesh_disk_edge_next(e_kill, v_kill);
605                 if (e2) {
606                         BMVert *tv2 = BM_edge_other_vert(e2, v_kill);
607                         if (tv2) {
608                                 /* only action, other calls here only get the edge to return */
609                                 e_new = bmesh_jekv(bm, e_kill, v_kill);
610
611                                 /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */
612                         }
613                 }
614         }
615
616         return e_new;
617 #else
618         /* with these args faces are never joined, same as above
619          * but account for loop customdata */
620         return BM_vert_collapse_faces(bm, e_kill, v_kill, 1.0f, false, kill_degenerate_faces);
621 #endif
622 }
623
624 #undef DO_V_INTERP
625
626 /**
627  * \brief Edge Split
628  *
629  * Splits an edge. \a v should be one of the vertices in \a e and defines
630  * the "from" end of the splitting operation: the new vertex will be
631  * \a percent of the way from \a v to the other end.
632  * The newly created edge is attached to \a v and is returned in \a r_e.
633  * The original edge \a e will be the other half of the split.
634  *
635  * \return The new vert
636  */
637 BMVert *BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float percent)
638 {
639         BMVert *v_new, *v2;
640         BMFace **oldfaces = NULL;
641         BMEdge *e_dummy;
642         BLI_array_staticdeclare(oldfaces, 32);
643         const bool do_mdisp = (e->l && CustomData_has_layer(&bm->ldata, CD_MDISPS));
644
645         /* we need this for handling multi-res */
646         if (!r_e) {
647                 r_e = &e_dummy;
648         }
649
650         /* do we have a multi-res layer? */
651         if (do_mdisp) {
652                 BMLoop *l;
653                 int i;
654                 
655                 l = e->l;
656                 do {
657                         BLI_array_append(oldfaces, l->f);
658                         l = l->radial_next;
659                 } while (l != e->l);
660                 
661                 /* flag existing faces so we can differentiate oldfaces from new faces */
662                 for (i = 0; i < BLI_array_count(oldfaces); i++) {
663                         BM_ELEM_API_FLAG_ENABLE(oldfaces[i], _FLAG_OVERLAP);
664                         oldfaces[i] = BM_face_copy(bm, bm, oldfaces[i], true, true);
665                         BM_ELEM_API_FLAG_DISABLE(oldfaces[i], _FLAG_OVERLAP);
666                 }
667         }
668
669         v2 = bmesh_edge_other_vert_get(e, v);
670         v_new = bmesh_semv(bm, v, e, r_e);
671
672         BLI_assert(v_new != NULL);
673
674         sub_v3_v3v3(v_new->co, v2->co, v->co);
675         madd_v3_v3v3fl(v_new->co, v->co, v_new->co, percent);
676
677         if (r_e) {
678                 (*r_e)->head.hflag = e->head.hflag;
679                 BM_elem_attrs_copy(bm, bm, e, *r_e);
680         }
681
682         /* v->v_new->v2 */
683         BM_data_interp_face_vert_edge(bm, v2, v, v_new, e, percent);
684         BM_data_interp_from_verts(bm, v, v2, v_new, percent);
685
686         if (do_mdisp) {
687                 int i, j;
688
689                 /* interpolate new/changed loop data from copied old faces */
690                 for (j = 0; j < 2; j++) {
691                         for (i = 0; i < BLI_array_count(oldfaces); i++) {
692                                 BMEdge *e1 = j ? *r_e : e;
693                                 BMLoop *l, *l2;
694                                 
695                                 l = e1->l;
696
697                                 if (UNLIKELY(!l)) {
698                                         BMESH_ASSERT(0);
699                                         break;
700                                 }
701                                 
702                                 do {
703                                         /* check this is an old face */
704                                         if (BM_ELEM_API_FLAG_TEST(l->f, _FLAG_OVERLAP)) {
705                                                 BMLoop *l2_first;
706
707                                                 l2 = l2_first = BM_FACE_FIRST_LOOP(l->f);
708                                                 do {
709                                                         BM_loop_interp_multires(bm, l2, oldfaces[i]);
710                                                 } while ((l2 = l2->next) != l2_first);
711                                         }
712                                         l = l->radial_next;
713                                 } while (l != e1->l);
714                         }
715                 }
716                 
717                 /* destroy the old faces */
718                 for (i = 0; i < BLI_array_count(oldfaces); i++) {
719                         BM_face_verts_kill(bm, oldfaces[i]);
720                 }
721                 
722                 /* fix boundaries a bit, doesn't work too well quite yet */
723 #if 0
724                 for (j = 0; j < 2; j++) {
725                         BMEdge *e1 = j ? *r_e : e;
726                         BMLoop *l, *l2;
727                         
728                         l = e1->l;
729                         if (UNLIKELY(!l)) {
730                                 BMESH_ASSERT(0);
731                                 break;
732                         }
733                         
734                         do {
735                                 BM_face_multires_bounds_smooth(bm, l->f);
736                                 l = l->radial_next;
737                         } while (l != e1->l);
738                 }
739 #endif
740                 
741                 BLI_array_free(oldfaces);
742         }
743
744         return v_new;
745 }
746
747 /**
748  * \brief Split an edge multiple times evenly
749  *
750  * \param r_varr  Optional array, verts in between (v1 -> v2)
751  */
752 BMVert  *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts, BMVert **r_varr)
753 {
754         int i;
755         float percent;
756         BMVert *v_new = NULL;
757         
758         for (i = 0; i < numcuts; i++) {
759                 percent = 1.0f / (float)(numcuts + 1 - i);
760                 v_new = BM_edge_split(bm, e, e->v2, NULL, percent);
761                 if (r_varr) {
762                         /* fill in reverse order (v1 -> v2) */
763                         r_varr[numcuts - i - 1] = v_new;
764                 }
765         }
766         return v_new;
767 }
768
769 #if 0
770 /**
771  * Checks if a face is valid in the data structure
772  */
773 bool BM_face_validate(BMFace *face, FILE *err)
774 {
775         BMIter iter;
776         BLI_array_declare(verts);
777         BMVert **verts = NULL;
778         BMLoop *l;
779         int i, j;
780         bool ret = true;
781         
782         if (face->len == 2) {
783                 fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
784                 fflush(err);
785         }
786
787         BLI_array_grow_items(verts, face->len);
788         BM_ITER_ELEM_INDEX (l, &iter, face, BM_LOOPS_OF_FACE, i) {
789                 verts[i] = l->v;
790                 if (l->e->v1 == l->e->v2) {
791                         fprintf(err, "Found bmesh edge with identical verts!\n");
792                         fprintf(err, "  edge ptr: %p, vert: %p\n",  l->e, l->e->v1);
793                         fflush(err);
794                         ret = false;
795                 }
796         }
797
798         for (i = 0; i < face->len; i++) {
799                 for (j = 0; j < face->len; j++) {
800                         if (j == i) {
801                                 continue;
802                         }
803
804                         if (verts[i] == verts[j]) {
805                                 fprintf(err, "Found duplicate verts in bmesh face!\n");
806                                 fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
807                                 fflush(err);
808                                 ret = false;
809                         }
810                 }
811         }
812         
813         BLI_array_free(verts);
814         return ret;
815 }
816 #endif
817
818 /**
819  * Calculate the 2 loops which _would_ make up the newly rotated Edge
820  * but don't actually change anything.
821  *
822  * Use this to further inspect if the loops to be connected have issues:
823  *
824  * Examples:
825  * - the newly formed edge already exists
826  * - the new face would be degenerate (zero area / concave /  bow-tie)
827  * - may want to measure if the new edge gives improved results topology.
828  *   over the old one, as with beauty fill.
829  *
830  * \note #BM_edge_rotate_check must have already run.
831  */
832 void BM_edge_calc_rotate(BMEdge *e, const bool ccw,
833                          BMLoop **r_l1, BMLoop **r_l2)
834 {
835         BMVert *v1, *v2;
836         BMFace *fa, *fb;
837
838         /* this should have already run */
839         BLI_assert(BM_edge_rotate_check(e) == true);
840
841         /* we know this will work */
842         BM_edge_face_pair(e, &fa, &fb);
843
844         /* so we can use ccw variable correctly,
845          * otherwise we could use the edges verts direct */
846         BM_edge_ordered_verts(e, &v1, &v2);
847
848         /* we could swap the verts _or_ the faces, swapping faces
849          * gives more predictable results since that way the next vert
850          * just stitches from face fa / fb */
851         if (ccw) {
852                 SWAP(BMFace *, fa, fb);
853         }
854
855         *r_l1 = BM_face_other_vert_loop(fb, v2, v1);
856         *r_l2 = BM_face_other_vert_loop(fa, v1, v2);
857 }
858
859 /**
860  * \brief Check if Rotate Edge is OK
861  *
862  * Quick check to see if we could rotate the edge,
863  * use this to avoid calling exceptions on common cases.
864  */
865 bool BM_edge_rotate_check(BMEdge *e)
866 {
867         BMFace *fa, *fb;
868         if (BM_edge_face_pair(e, &fa, &fb)) {
869                 BMLoop *la, *lb;
870
871                 la = BM_face_other_vert_loop(fa, e->v2, e->v1);
872                 lb = BM_face_other_vert_loop(fb, e->v2, e->v1);
873
874                 /* check that the next vert in both faces isn't the same
875                  * (ie - the next edge doesn't share the same faces).
876                  * since we can't rotate usefully in this case. */
877                 if (la->v == lb->v) {
878                         return false;
879                 }
880
881                 /* mirror of the check above but in the opposite direction */
882                 la = BM_face_other_vert_loop(fa, e->v1, e->v2);
883                 lb = BM_face_other_vert_loop(fb, e->v1, e->v2);
884
885                 if (la->v == lb->v) {
886                         return false;
887                 }
888
889                 return true;
890         }
891         else {
892                 return false;
893         }
894 }
895
896 /**
897  * \brief Check if Edge Rotate Gives Degenerate Faces
898  *
899  * Check 2 cases
900  * 1) does the newly forms edge form a flipped face (compare with previous cross product)
901  * 2) does the newly formed edge cause a zero area corner (or close enough to be almost zero)
902  *
903  * \param e The edge to test rotation.
904  * \param l1,l2 are the loops of the proposed verts to rotate too and should
905  * be the result of calling #BM_edge_calc_rotate
906  */
907 bool BM_edge_rotate_check_degenerate(BMEdge *e, BMLoop *l1, BMLoop *l2)
908 {
909         /* note: for these vars 'old' just means initial edge state. */
910
911         float ed_dir_old[3]; /* edge vector */
912         float ed_dir_new[3]; /* edge vector */
913         float ed_dir_new_flip[3]; /* edge vector */
914
915         float ed_dir_v1_old[3];
916         float ed_dir_v2_old[3];
917
918         float ed_dir_v1_new[3];
919         float ed_dir_v2_new[3];
920
921         float cross_old[3];
922         float cross_new[3];
923
924         /* original verts - these will be in the edge 'e' */
925         BMVert *v1_old, *v2_old;
926
927         /* verts from the loops passed */
928
929         BMVert *v1, *v2;
930         /* these are the opposite verts - the verts that _would_ be used if 'ccw' was inverted*/
931         BMVert *v1_alt, *v2_alt;
932
933         /* this should have already run */
934         BLI_assert(BM_edge_rotate_check(e) == true);
935
936         BM_edge_ordered_verts(e, &v1_old, &v2_old);
937
938         v1 = l1->v;
939         v2 = l2->v;
940
941         /* get the next vert along */
942         v1_alt = BM_face_other_vert_loop(l1->f, v1_old, v1)->v;
943         v2_alt = BM_face_other_vert_loop(l2->f, v2_old, v2)->v;
944
945         /* normalize all so comparisons are scale independent */
946
947         BLI_assert(BM_edge_exists(v1_old, v1));
948         BLI_assert(BM_edge_exists(v1, v1_alt));
949
950         BLI_assert(BM_edge_exists(v2_old, v2));
951         BLI_assert(BM_edge_exists(v2, v2_alt));
952
953         /* old and new edge vecs */
954         sub_v3_v3v3(ed_dir_old, v1_old->co, v2_old->co);
955         sub_v3_v3v3(ed_dir_new, v1->co, v2->co);
956         normalize_v3(ed_dir_old);
957         normalize_v3(ed_dir_new);
958
959         /* old edge corner vecs */
960         sub_v3_v3v3(ed_dir_v1_old, v1_old->co, v1->co);
961         sub_v3_v3v3(ed_dir_v2_old, v2_old->co, v2->co);
962         normalize_v3(ed_dir_v1_old);
963         normalize_v3(ed_dir_v2_old);
964
965         /* old edge corner vecs */
966         sub_v3_v3v3(ed_dir_v1_new, v1->co, v1_alt->co);
967         sub_v3_v3v3(ed_dir_v2_new, v2->co, v2_alt->co);
968         normalize_v3(ed_dir_v1_new);
969         normalize_v3(ed_dir_v2_new);
970
971         /* compare */
972         cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v1_old);
973         cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v1_new);
974         if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
975                 return false;
976         }
977         cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v2_old);
978         cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v2_new);
979         if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
980                 return false;
981         }
982
983         negate_v3_v3(ed_dir_new_flip, ed_dir_new);
984
985         /* result is zero area corner */
986         if ((dot_v3v3(ed_dir_new,      ed_dir_v1_new) > 0.999f) ||
987             (dot_v3v3(ed_dir_new_flip, ed_dir_v2_new) > 0.999f))
988         {
989                 return false;
990         }
991
992         return true;
993 }
994
995 bool BM_edge_rotate_check_beauty(BMEdge *e,
996                                  BMLoop *l1, BMLoop *l2)
997 {
998         /* Stupid check for now:
999          * Could compare angles of surrounding edges
1000          * before & after, but this is OK.*/
1001         return (len_squared_v3v3(e->v1->co, e->v2->co) >
1002                 len_squared_v3v3(l1->v->co, l2->v->co));
1003 }
1004
1005 /**
1006  * \brief Rotate Edge
1007  *
1008  * Spins an edge topologically,
1009  * either counter-clockwise or clockwise depending on \a ccw.
1010  *
1011  * \return The spun edge, NULL on error
1012  * (e.g., if the edge isn't surrounded by exactly two faces).
1013  *
1014  * \note This works by dissolving the edge then re-creating it,
1015  * so the returned edge won't have the same pointer address as the original one.
1016  *
1017  * \see header definition for \a check_flag enum.
1018  */
1019 BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const bool ccw, const short check_flag)
1020 {
1021         BMVert *v1, *v2;
1022         BMLoop *l1, *l2;
1023         BMFace *f;
1024         BMEdge *e_new = NULL;
1025         char f_hflag_prev_1;
1026         char f_hflag_prev_2;
1027
1028         if (!BM_edge_rotate_check(e)) {
1029                 return NULL;
1030         }
1031
1032         BM_edge_calc_rotate(e, ccw, &l1, &l2);
1033
1034         /* the loops will be freed so assign verts */
1035         v1 = l1->v;
1036         v2 = l2->v;
1037
1038         /* --------------------------------------- */
1039         /* Checking Code - make sure we can rotate */
1040
1041         if (check_flag & BM_EDGEROT_CHECK_BEAUTY) {
1042                 if (!BM_edge_rotate_check_beauty(e, l1, l2)) {
1043                         return NULL;
1044                 }
1045         }
1046
1047         /* check before applying */
1048         if (check_flag & BM_EDGEROT_CHECK_EXISTS) {
1049                 if (BM_edge_exists(v1, v2)) {
1050                         return NULL;
1051                 }
1052         }
1053
1054         /* slowest, check last */
1055         if (check_flag & BM_EDGEROT_CHECK_DEGENERATE) {
1056                 if (!BM_edge_rotate_check_degenerate(e, l1, l2)) {
1057                         return NULL;
1058                 }
1059         }
1060         /* Done Checking */
1061         /* ------------- */
1062
1063
1064
1065         /* --------------- */
1066         /* Rotate The Edge */
1067
1068         /* first create the new edge, this is so we can copy the customdata from the old one
1069          * if splice if disabled, always add in a new edge even if theres one there. */
1070         e_new = BM_edge_create(bm, v1, v2, e, (check_flag & BM_EDGEROT_CHECK_SPLICE) != 0);
1071
1072         f_hflag_prev_1 = l1->f->head.hflag;
1073         f_hflag_prev_2 = l2->f->head.hflag;
1074
1075         /* don't delete the edge, manually remove the edge after so we can copy its attributes */
1076         f = BM_faces_join_pair(bm, l1->f, l2->f, NULL, true);
1077
1078         if (f == NULL) {
1079                 return NULL;
1080         }
1081
1082         /* note, this assumes joining the faces _didnt_ also remove the verts.
1083          * the #BM_edge_rotate_check will ensure this, but its possibly corrupt state or future edits
1084          * break this */
1085         if (!BM_face_split(bm, f, v1, v2, NULL, NULL, true)) {
1086                 return NULL;
1087         }
1088         else {
1089                 /* we should really be able to know the faces some other way,
1090                  * rather then fetching them back from the edge, but this is predictable
1091                  * where using the return values from face split isn't. - campbell */
1092                 BMFace *fa, *fb;
1093                 if (BM_edge_face_pair(e_new, &fa, &fb)) {
1094                         fa->head.hflag = f_hflag_prev_1;
1095                         fb->head.hflag = f_hflag_prev_2;
1096                 }
1097         }
1098
1099         return e_new;
1100 }
1101
1102 /**
1103  * \brief Rip a single face from a vertex fan
1104  */
1105 BMVert *BM_face_vert_separate(BMesh *bm, BMFace *sf, BMVert *sv)
1106 {
1107         return bmesh_urmv(bm, sf, sv);
1108 }
1109
1110 /**
1111  * \brief Rip a single face from a vertex fan
1112  *
1113  * \note same as #BM_face_vert_separate but faster (avoids a loop lookup)
1114  */
1115 BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *sl)
1116 {
1117         return bmesh_urmv_loop(bm, sl);
1118 }