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