own cleanup commit in bmesh branch - removed last letters from ends of some comments.
[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 int 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 int 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                 int 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 short 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 *nl;
304
305                                 f_iter = BM_face_split(bm, f_iter, v1, v2, &nl, NULL, FALSE);
306
307                                 if (r_f) {
308                                         *r_f = f_iter;
309                                 }
310                                 return nl->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 short nodouble)
340 {
341         const int has_mdisp = CustomData_has_layer(&bm->ldata, CD_MDISPS);
342         BMFace *nf, *of;
343
344         BLI_assert(v1 != v2);
345
346         /* do we have a multires layer? */
347         if (has_mdisp) {
348                 of = BM_face_copy(bm, f, FALSE, FALSE);
349         }
350         
351 #ifdef USE_BMESH_HOLES
352         nf = bmesh_sfme(bm, f, v1, v2, r_l, NULL, example, nodouble);
353 #else
354         nf = bmesh_sfme(bm, f, v1, v2, r_l, example, nodouble);
355 #endif
356         
357         if (nf) {
358                 BM_elem_attrs_copy(bm, bm, f, nf);
359                 copy_v3_v3(nf->no, f->no);
360
361                 /* handle multires update */
362                 if (has_mdisp && (nf != 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, of);
369                         } while ((l_iter = l_iter->next) != l_first);
370
371                         l_iter = l_first = BM_FACE_FIRST_LOOP(nf);
372                         do {
373                                 BM_loop_interp_multires(bm, l_iter, of);
374                         } while ((l_iter = l_iter->next) != l_first);
375
376                         BM_face_kill(bm, of);
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, nf);
382 #endif
383                 }
384         }
385
386         return nf;
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 *nf, *of;
410         BMLoop *l_dummy;
411         BMEdge *e, *newe;
412         BMVert *newv;
413         int i, j;
414
415         BLI_assert(v1 != v2);
416
417         of = BM_face_copy(bm, f, TRUE, TRUE);
418
419         if (!r_l)
420                 r_l = &l_dummy;
421         
422 #ifdef USE_BMESH_HOLES
423         nf = bmesh_sfme(bm, f, v1, v2, r_l, NULL, example, FALSE);
424 #else
425         nf = bmesh_sfme(bm, f, v1, v2, r_l, example, FALSE);
426 #endif
427         /* bmesh_sfme returns in r_l a Loop for nf going from v1 to v2.
428          * The radial_next is for f and goes from v2 to v1  */
429
430         if (nf) {
431                 BM_elem_attrs_copy(bm, bm, f, nf);
432                 copy_v3_v3(nf->no, f->no);
433
434                 e = (*r_l)->e;
435                 for (i = 0; i < n; i++) {
436                         newv = bmesh_semv(bm, v2, e, &newe);
437                         BLI_assert(newv != NULL);
438                         /* bmesh_semv returns in newe the edge going from newv to tv */
439                         copy_v3_v3(newv->co, cos[i]);
440
441                         /* interpolate the loop data for the loops with (v == newv), using orig face */
442                         for (j = 0; j < 2; j++) {
443                                 BMEdge *e_iter = (j == 0) ? e : newe;
444                                 BMLoop *l_iter = e_iter->l;
445                                 do {
446                                         if (l_iter->v == newv) {
447                                                 /* this interpolates both loop and vertex data */
448                                                 BM_loop_interp_from_face(bm, l_iter, of, TRUE, TRUE);
449                                         }
450                                 } while ((l_iter = l_iter->radial_next) != e_iter->l);
451                         }
452                         e = newe;
453                 }
454         }
455
456         BM_face_verts_kill(bm, of);
457
458         return nf;
459 }
460
461 /**
462  * \brief Vert Collapse Faces
463  *
464  * Collapses vertex \a kv 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 ke The edge to collapse
476  * \param kv 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 *ke, BMVert *kv, float fac,
485                                const short join_faces, const short kill_degenerate_faces)
486 {
487         BMEdge *ne = NULL;
488         BMVert *tv = bmesh_edge_other_vert_get(ke, kv);
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(kv) <= 2);
501
502
503         /* first modify the face loop data  */
504         w[0] = 1.0f - fac;
505         w[1] = fac;
506
507         if (ke->l) {
508                 l_iter = ke->l;
509                 do {
510                         if (l_iter->v == tv && l_iter->next->v == kv) {
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) != ke->l);
519         }
520
521         /* now interpolate the vertex data */
522         BM_data_interp_from_verts(bm, kv, tv, kv, fac);
523
524         e2 = bmesh_disk_edge_next(ke, kv);
525         tv2 = BM_edge_other_vert(e2, kv);
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, kv, 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 *nl = NULL;
540                                 if (BM_face_split(bm, f2, tv, tv2, &nl, NULL, FALSE)) {
541                                         ne = nl->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                 ne = bmesh_jekv(bm, ke, kv, TRUE);
553                 /* ne = BM_edge_exists(tv, tv2); */ /* same as return above */
554
555                 if (ne && 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] = {ne->v1, ne->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 ne;
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 *ke, BMVert *kv,
592                               const short kill_degenerate_faces)
593 {
594         /* nice example implementation but we want loops to have their customdata
595          * accounted for */
596 #if 0
597         BMEdge *ne = 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(ke, kv);
604         if (tv) {
605                 BMEdge *e2 = bmesh_disk_edge_next(ke, kv);
606                 if (e2) {
607                         BMVert *tv2 = BM_edge_other_vert(e2, kv);
608                         if (tv2) {
609                                 /* only action, other calls here only get the edge to return */
610                                 ne = bmesh_jekv(bm, ke, kv);
611
612                                 /* ne = BM_edge_exists(tv, tv2); */ /* same as return above */
613                         }
614                 }
615         }
616
617         return ne;
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, ke, kv, 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 *nv, *v2;
641         BMFace **oldfaces = NULL;
642         BMEdge *e_dummy;
643         BLI_array_staticdeclare(oldfaces, 32);
644         SmallHash hash;
645         const int do_mdisp = (e->l && CustomData_has_layer(&bm->ldata, CD_MDISPS));
646
647         /* we need this for handling multi-res */
648         if (!r_e) {
649                 r_e = &e_dummy;
650         }
651
652         /* do we have a multi-res layer? */
653         if (do_mdisp) {
654                 BMLoop *l;
655                 int i;
656                 
657                 l = e->l;
658                 do {
659                         BLI_array_append(oldfaces, l->f);
660                         l = l->radial_next;
661                 } while (l != e->l);
662                 
663                 /* create a hash so we can differentiate oldfaces from new face */
664                 BLI_smallhash_init(&hash);
665                 
666                 for (i = 0; i < BLI_array_count(oldfaces); i++) {
667                         oldfaces[i] = BM_face_copy(bm, oldfaces[i], TRUE, TRUE);
668                         BLI_smallhash_insert(&hash, (intptr_t)oldfaces[i], NULL);
669                 }
670         }
671
672         v2 = bmesh_edge_other_vert_get(e, v);
673         nv = bmesh_semv(bm, v, e, r_e);
674
675         BLI_assert(nv != NULL);
676
677         sub_v3_v3v3(nv->co, v2->co, v->co);
678         madd_v3_v3v3fl(nv->co, v->co, nv->co, percent);
679
680         if (r_e) {
681                 (*r_e)->head.hflag = e->head.hflag;
682                 BM_elem_attrs_copy(bm, bm, e, *r_e);
683         }
684
685         /* v->nv->v2 */
686         BM_data_interp_face_vert_edge(bm, v2, v, nv, e, percent);
687         BM_data_interp_from_verts(bm, v, v2, nv, percent);
688
689         if (do_mdisp) {
690                 int i, j;
691
692                 /* interpolate new/changed loop data from copied old faces */
693                 for (j = 0; j < 2; j++) {
694                         for (i = 0; i < BLI_array_count(oldfaces); i++) {
695                                 BMEdge *e1 = j ? *r_e : e;
696                                 BMLoop *l, *l2;
697                                 
698                                 l = e1->l;
699
700                                 if (UNLIKELY(!l)) {
701                                         BMESH_ASSERT(0);
702                                         break;
703                                 }
704                                 
705                                 do {
706                                         if (!BLI_smallhash_haskey(&hash, (intptr_t)l->f)) {
707                                                 BMLoop *l2_first;
708
709                                                 l2 = l2_first = BM_FACE_FIRST_LOOP(l->f);
710                                                 do {
711                                                         BM_loop_interp_multires(bm, l2, oldfaces[i]);
712                                                 } while ((l2 = l2->next) != l2_first);
713                                         }
714                                         l = l->radial_next;
715                                 } while (l != e1->l);
716                         }
717                 }
718                 
719                 /* destroy the old faces */
720                 for (i = 0; i < BLI_array_count(oldfaces); i++) {
721                         BM_face_verts_kill(bm, oldfaces[i]);
722                 }
723                 
724                 /* fix boundaries a bit, doesn't work too well quite yet */
725 #if 0
726                 for (j = 0; j < 2; j++) {
727                         BMEdge *e1 = j ? *r_e : e;
728                         BMLoop *l, *l2;
729                         
730                         l = e1->l;
731                         if (UNLIKELY(!l)) {
732                                 BMESH_ASSERT(0);
733                                 break;
734                         }
735                         
736                         do {
737                                 BM_face_multires_bounds_smooth(bm, l->f);
738                                 l = l->radial_next;
739                         } while (l != e1->l);
740                 }
741 #endif
742                 
743                 BLI_array_free(oldfaces);
744                 BLI_smallhash_release(&hash);
745         }
746
747         return nv;
748 }
749
750 /**
751  * \brief Split an edge multiple times evenly
752  */
753 BMVert  *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts)
754 {
755         int i;
756         float percent;
757         BMVert *nv = NULL;
758         
759         for (i = 0; i < numcuts; i++) {
760                 percent = 1.0f / (float)(numcuts + 1 - i);
761                 nv = BM_edge_split(bm, e, e->v2, NULL, percent);
762         }
763         return nv;
764 }
765
766 /**
767  * Checks if a face is valid in the data structure
768  */
769 int BM_face_validate(BMFace *face, FILE *err)
770 {
771         BMIter iter;
772         BLI_array_declare(verts);
773         BMVert **verts = NULL;
774         BMLoop *l;
775         int ret = 1, i, j;
776         
777         if (face->len == 2) {
778                 fprintf(err, "warning: found two-edged face. face ptr: %p\n", face);
779                 fflush(err);
780         }
781
782         BLI_array_grow_items(verts, face->len);
783         BM_ITER_ELEM_INDEX (l, &iter, face, BM_LOOPS_OF_FACE, i) {
784                 verts[i] = l->v;
785                 if (l->e->v1 == l->e->v2) {
786                         fprintf(err, "Found bmesh edge with identical verts!\n");
787                         fprintf(err, "  edge ptr: %p, vert: %p\n",  l->e, l->e->v1);
788                         fflush(err);
789                         ret = 0;
790                 }
791         }
792
793         for (i = 0; i < face->len; i++) {
794                 for (j = 0; j < face->len; j++) {
795                         if (j == i) {
796                                 continue;
797                         }
798
799                         if (verts[i] == verts[j]) {
800                                 fprintf(err, "Found duplicate verts in bmesh face!\n");
801                                 fprintf(err, "  face ptr: %p, vert: %p\n", face, verts[i]);
802                                 fflush(err);
803                                 ret = 0;
804                         }
805                 }
806         }
807         
808         BLI_array_free(verts);
809         return ret;
810 }
811
812
813 /**
814  * Calculate the 2 loops which _would_ make up the newly rotated Edge
815  * but don't actually change anything.
816  *
817  * Use this to further inspect if the loops to be connected have issues:
818  *
819  * Examples:
820  * - the newly formed edge already exists
821  * - the new face would be degenerate (zero area / concave /  bow-tie)
822  * - may want to measure if the new edge gives improved results topology.
823  *   over the old one, as with beauty fill.
824  *
825  * \note #BM_edge_rotate_check must have already run.
826  */
827 void BM_edge_calc_rotate(BMEdge *e, int ccw,
828                          BMLoop **r_l1, BMLoop **r_l2)
829 {
830         BMVert *v1, *v2;
831         BMFace *fa, *fb;
832
833         /* this should have already run */
834         BLI_assert(BM_edge_rotate_check(e) == TRUE);
835
836         /* we know this will work */
837         BM_edge_face_pair(e, &fa, &fb);
838
839         /* so we can use ccw variable correctly,
840          * otherwise we could use the edges verts direct */
841         BM_edge_ordered_verts(e, &v1, &v2);
842
843         /* we could swap the verts _or_ the faces, swapping faces
844          * gives more predictable results since that way the next vert
845          * just stitches from face fa / fb */
846         if (ccw) {
847                 SWAP(BMFace *, fa, fb);
848         }
849
850         *r_l1 = BM_face_other_vert_loop(fb, v2, v1);
851         *r_l2 = BM_face_other_vert_loop(fa, v1, v2);
852 }
853
854 /**
855  * \brief Check if Rotate Edge is OK
856  *
857  * Quick check to see if we could rotate the edge,
858  * use this to avoid calling exceptions on common cases.
859  */
860 int BM_edge_rotate_check(BMEdge *e)
861 {
862         BMFace *fa, *fb;
863         if (BM_edge_face_pair(e, &fa, &fb)) {
864                 BMLoop *la, *lb;
865
866                 la = BM_face_other_vert_loop(fa, e->v2, e->v1);
867                 lb = BM_face_other_vert_loop(fb, e->v2, e->v1);
868
869                 /* check that the next vert in both faces isn't the same
870                  * (ie - the next edge doesn't share the same faces).
871                  * since we can't rotate usefully in this case. */
872                 if (la->v == lb->v) {
873                         return FALSE;
874                 }
875
876                 /* mirror of the check above but in the opposite direction */
877                 la = BM_face_other_vert_loop(fa, e->v1, e->v2);
878                 lb = BM_face_other_vert_loop(fb, e->v1, e->v2);
879
880                 if (la->v == lb->v) {
881                         return FALSE;
882                 }
883
884                 return TRUE;
885         }
886         else {
887                 return FALSE;
888         }
889 }
890
891 /**
892  * \brief Check if Edge Rotate Gives Degenerate Faces
893  *
894  * Check 2 cases
895  * 1) does the newly forms edge form a flipped face (compare with previous cross product)
896  * 2) does the newly formed edge cause a zero area corner (or close enough to be almost zero)
897  *
898  * \param e The edge to test rotation.
899  * \param l1,l2 are the loops of the proposed verts to rotate too and should
900  * be the result of calling #BM_edge_calc_rotate
901  */
902 int BM_edge_rotate_check_degenerate(BMEdge *e, BMLoop *l1, BMLoop *l2)
903 {
904         /* note: for these vars 'old' just means initial edge state. */
905
906         float ed_dir_old[3]; /* edge vector */
907         float ed_dir_new[3]; /* edge vector */
908         float ed_dir_new_flip[3]; /* edge vector */
909
910         float ed_dir_v1_old[3];
911         float ed_dir_v2_old[3];
912
913         float ed_dir_v1_new[3];
914         float ed_dir_v2_new[3];
915
916         float cross_old[3];
917         float cross_new[3];
918
919         /* original verts - these will be in the edge 'e' */
920         BMVert *v1_old, *v2_old;
921
922         /* verts from the loops passed */
923
924         BMVert *v1, *v2;
925         /* these are the opposite verts - the verts that _would_ be used if 'ccw' was inverted*/
926         BMVert *v1_alt, *v2_alt;
927
928         /* this should have already run */
929         BLI_assert(BM_edge_rotate_check(e) == TRUE);
930
931         BM_edge_ordered_verts(e, &v1_old, &v2_old);
932
933         v1 = l1->v;
934         v2 = l2->v;
935
936         /* get the next vert along */
937         v1_alt = BM_face_other_vert_loop(l1->f, v1_old, v1)->v;
938         v2_alt = BM_face_other_vert_loop(l2->f, v2_old, v2)->v;
939
940         /* normalize all so comparisons are scale independent */
941
942         BLI_assert(BM_edge_exists(v1_old, v1));
943         BLI_assert(BM_edge_exists(v1, v1_alt));
944
945         BLI_assert(BM_edge_exists(v2_old, v2));
946         BLI_assert(BM_edge_exists(v2, v2_alt));
947
948         /* old and new edge vecs */
949         sub_v3_v3v3(ed_dir_old, v1_old->co, v2_old->co);
950         sub_v3_v3v3(ed_dir_new, v1->co, v2->co);
951         normalize_v3(ed_dir_old);
952         normalize_v3(ed_dir_new);
953
954         /* old edge corner vecs */
955         sub_v3_v3v3(ed_dir_v1_old, v1_old->co, v1->co);
956         sub_v3_v3v3(ed_dir_v2_old, v2_old->co, v2->co);
957         normalize_v3(ed_dir_v1_old);
958         normalize_v3(ed_dir_v2_old);
959
960         /* old edge corner vecs */
961         sub_v3_v3v3(ed_dir_v1_new, v1->co, v1_alt->co);
962         sub_v3_v3v3(ed_dir_v2_new, v2->co, v2_alt->co);
963         normalize_v3(ed_dir_v1_new);
964         normalize_v3(ed_dir_v2_new);
965
966         /* compare */
967         cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v1_old);
968         cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v1_new);
969         if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
970                 return FALSE;
971         }
972         cross_v3_v3v3(cross_old, ed_dir_old, ed_dir_v2_old);
973         cross_v3_v3v3(cross_new, ed_dir_new, ed_dir_v2_new);
974         if (dot_v3v3(cross_old, cross_new) < 0.0f) { /* does this flip? */
975                 return FALSE;
976         }
977
978         negate_v3_v3(ed_dir_new_flip, ed_dir_new);
979
980         /* result is zero area corner */
981         if ((dot_v3v3(ed_dir_new,      ed_dir_v1_new) > 0.999f) ||
982             (dot_v3v3(ed_dir_new_flip, ed_dir_v2_new) > 0.999f))
983         {
984                 return FALSE;
985         }
986
987         return TRUE;
988 }
989
990 int BM_edge_rotate_check_beauty(BMEdge *e,
991                                 BMLoop *l1, BMLoop *l2)
992 {
993         /* Stupid check for now:
994          * Could compare angles of surrounding edges
995          * before & after, but this is OK.*/
996         return (len_squared_v3v3(e->v1->co, e->v2->co) >
997                 len_squared_v3v3(l1->v->co, l2->v->co));
998 }
999
1000 /**
1001  * \brief Rotate Edge
1002  *
1003  * Spins an edge topologically,
1004  * either counter-clockwise or clockwise depending on \a ccw.
1005  *
1006  * \return The spun edge, NULL on error
1007  * (e.g., if the edge isn't surrounded by exactly two faces).
1008  *
1009  * \note This works by dissolving the edge then re-creating it,
1010  * so the returned edge won't have the same pointer address as the original one.
1011  *
1012  * \see header definition for \a check_flag enum.
1013  */
1014 BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, const short ccw, const short check_flag)
1015 {
1016         BMVert *v1, *v2;
1017         BMLoop *l1, *l2;
1018         BMFace *f;
1019         BMEdge *e_new = NULL;
1020         char f_hflag_prev_1;
1021         char f_hflag_prev_2;
1022
1023         if (!BM_edge_rotate_check(e)) {
1024                 return NULL;
1025         }
1026
1027         BM_edge_calc_rotate(e, ccw, &l1, &l2);
1028
1029         /* the loops will be freed so assign verts */
1030         v1 = l1->v;
1031         v2 = l2->v;
1032
1033         /* --------------------------------------- */
1034         /* Checking Code - make sure we can rotate */
1035
1036         if (check_flag & BM_EDGEROT_CHECK_BEAUTY) {
1037                 if (!BM_edge_rotate_check_beauty(e, l1, l2)) {
1038                         return NULL;
1039                 }
1040         }
1041
1042         /* check before applying */
1043         if (check_flag & BM_EDGEROT_CHECK_EXISTS) {
1044                 if (BM_edge_exists(v1, v2)) {
1045                         return NULL;
1046                 }
1047         }
1048
1049         /* slowest, check last */
1050         if (check_flag & BM_EDGEROT_CHECK_DEGENERATE) {
1051                 if (!BM_edge_rotate_check_degenerate(e, l1, l2)) {
1052                         return NULL;
1053                 }
1054         }
1055         /* Done Checking */
1056         /* ------------- */
1057
1058
1059
1060         /* --------------- */
1061         /* Rotate The Edge */
1062
1063         /* first create the new edge, this is so we can copy the customdata from the old one
1064          * if splice if disabled, always add in a new edge even if theres one there. */
1065         e_new = BM_edge_create(bm, v1, v2, e, (check_flag & BM_EDGEROT_CHECK_SPLICE) != 0);
1066
1067         f_hflag_prev_1 = l1->f->head.hflag;
1068         f_hflag_prev_2 = l2->f->head.hflag;
1069
1070         /* don't delete the edge, manually remove the egde after so we can copy its attributes */
1071         f = BM_faces_join_pair(bm, l1->f, l2->f, NULL, TRUE);
1072
1073         if (f == NULL) {
1074                 return NULL;
1075         }
1076
1077         /* note, this assumes joining the faces _didnt_ also remove the verts.
1078          * the #BM_edge_rotate_check will ensure this, but its possibly corrupt state or future edits
1079          * break this */
1080         if (!BM_face_split(bm, f, v1, v2, NULL, NULL, TRUE)) {
1081                 return NULL;
1082         }
1083         else {
1084                 /* we should really be able to know the faces some other way,
1085                  * rather then fetching them back from the edge, but this is predictable
1086                  * where using the return values from face split isn't. - campbell */
1087                 BMFace *fa, *fb;
1088                 if (BM_edge_face_pair(e_new, &fa, &fb)) {
1089                         fa->head.hflag = f_hflag_prev_1;
1090                         fb->head.hflag = f_hflag_prev_2;
1091                 }
1092         }
1093
1094         return e_new;
1095 }
1096
1097 /**
1098  * \brief Rip a single face from a vertex fan
1099  */
1100 BMVert *BM_face_vert_separate(BMesh *bm, BMFace *sf, BMVert *sv)
1101 {
1102         return bmesh_urmv(bm, sf, sv);
1103 }
1104
1105 /**
1106  * \brief Rip a single face from a vertex fan
1107  *
1108  * \note same as #BM_face_vert_separate but faster (avoids a loop lookup)
1109  */
1110 BMVert *BM_face_loop_separate(BMesh *bm, BMLoop *sl)
1111 {
1112         return bmesh_urmv_loop(bm, sl);
1113 }