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