source/blender/bmesh/intern/bmesh_newcore.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_newcore.c
  24  *  \ingroup bmesh
  25  *
  26  */
  27
  28 #include "MEM_guardedalloc.h"
  29
  30 #include "BLI_math_vector.h"
  31
  32 #include "BKE_DerivedMesh.h"
  33
  34 #include "BLI_listbase.h"
  35 #include "BLI_array.h"
  36
  37 #include "bmesh.h"
  38 #include "bmesh_private.h"
  39
  40 /* use so valgrinds memcheck alerts us when undefined index is used.
  41  * TESTING ONLY! */
  42 // #define USE_DEBUG_INDEX_MEMCHECK
  43
  44 #ifdef USE_DEBUG_INDEX_MEMCHECK
  45 #define DEBUG_MEMCHECK_INDEX_INVALIDATE(ele)               \
  46         {                                                      \
  47                 int undef_idx;                                     \
  48                 BM_elem_index_set(ele, undef_idx); /* set_ok_invalid */  \
  49         }                                                      \
  50
  51 #endif
  52
  53 BMVert *BM_vert_create(BMesh *bm, const float co[3], const struct BMVert *example)
  54 {
  55         BMVert *v = BLI_mempool_calloc(bm->vpool);
  56
  57 #ifdef USE_DEBUG_INDEX_MEMCHECK
  58         DEBUG_MEMCHECK_INDEX_INVALIDATE(v)
  59 #else
  60         BM_elem_index_set(v, -1); /* set_ok_invalid */
  61 #endif
  62
  63         bm->elem_index_dirty |= BM_VERT; /* may add to middle of the pool */
  64
  65         bm->totvert++;
  66
  67         v->head.htype = BM_VERT;
  68
  69         /* 'v->no' is handled by BM_elem_attrs_copy */
  70         if (co) copy_v3_v3(v->co, co);
  71
  72         /* allocate flag */
  73         v->oflags = BLI_mempool_calloc(bm->toolflagpool);
  74
  75         CustomData_bmesh_set_default(&bm->vdata, &v->head.data);
  76
  77         if (example) {
  78                 BM_elem_attrs_copy(bm, bm, (BMVert *)example, v);
  79         }
  80
  81         BM_CHECK_ELEMENT(bm, v);
  82
  83         return (BMVert *) v;
  84 }
  85
  86 /**
  87  *                      BMESH EDGE EXIST
  88  *
  89  *  Finds out if two vertices already have an edge
  90  *  connecting them. Note that multiple edges may
  91  *  exist between any two vertices, and therefore
  92  *  This function only returns the first one found.
  93  *
  94  *  Returns -
  95  *      BMEdge pointer
  96  */
  97 BMEdge *BM_edge_exists(BMVert *v1, BMVert *v2)
  98 {
  99         BMIter iter;
 100         BMEdge *e;
 101
 102         BM_ITER(e, &iter, NULL, BM_EDGES_OF_VERT, v1) {
 103                 if (e->v1 == v2 || e->v2 == v2)
 104                         return e;
 105         }
 106
 107         return NULL;
 108 }
 109
 110 BMEdge *BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *example, int nodouble)
 111 {
 112         BMEdge *e;
 113
 114         if (nodouble && (e = BM_edge_exists(v1, v2)))
 115                 return (BMEdge *)e;
 116
 117         e = BLI_mempool_calloc(bm->epool);
 118
 119 #ifdef USE_DEBUG_INDEX_MEMCHECK
 120         DEBUG_MEMCHECK_INDEX_INVALIDATE(e)
 121 #else
 122         BM_elem_index_set(e, -1); /* set_ok_invalid */
 123 #endif
 124
 125         bm->elem_index_dirty |= BM_EDGE; /* may add to middle of the pool */
 126
 127         bm->totedge++;
 128
 129         e->head.htype = BM_EDGE;
 130
 131         /* allocate flag */
 132         e->oflags = BLI_mempool_calloc(bm->toolflagpool);
 133
 134         e->v1 = (BMVert *) v1;
 135         e->v2 = (BMVert *) v2;
 136
 137         BM_elem_flag_enable(e, BM_ELEM_SMOOTH);
 138
 139         CustomData_bmesh_set_default(&bm->edata, &e->head.data);
 140
 141         bmesh_disk_append_edge(e, e->v1);
 142         bmesh_disk_append_edge(e, e->v2);
 143
 144         if (example)
 145                 BM_elem_attrs_copy(bm, bm, (BMEdge *)example, (BMEdge *)e);
 146
 147         BM_CHECK_ELEMENT(bm, e);
 148
 149         return (BMEdge *) e;
 150 }
 151
 152 static BMLoop *bmesh_create_loop(BMesh *bm, BMVert *v, BMEdge *e, BMFace *f, const BMLoop *example)
 153 {
 154         BMLoop *l = NULL;
 155
 156         l = BLI_mempool_calloc(bm->lpool);
 157         l->next = l->prev = NULL;
 158         l->v = v;
 159         l->e = e;
 160         l->f = f;
 161         l->radial_next = l->radial_prev = NULL;
 162         l->head.data = NULL;
 163         l->head.htype = BM_LOOP;
 164
 165         bm->totloop++;
 166
 167         if (example)
 168                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->head.data, &l->head.data);
 169         else
 170                 CustomData_bmesh_set_default(&bm->ldata, &l->head.data);
 171
 172         return l;
 173 }
 174
 175 static BMLoop *bm_face_boundry_add(BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte)
 176 {
 177 #ifdef USE_BMESH_HOLES
 178         BMLoopList *lst = BLI_mempool_calloc(bm->looplistpool);
 179 #endif
 180         BMLoop *l = bmesh_create_loop(bm, startv, starte, f, NULL);
 181
 182         bmesh_radial_append(starte, l);
 183
 184 #ifdef USE_BMESH_HOLES
 185         lst->first = lst->last = l;
 186         BLI_addtail(&f->loops, lst);
 187 #else
 188         f->l_first = l;
 189 #endif
 190
 191         l->f = f;
 192
 193         return l;
 194 }
 195
 196 BMFace *BM_face_copy(BMesh *bm, BMFace *f, const short copyverts, const short copyedges)
 197 {
 198         BMEdge **edges = NULL;
 199         BMVert **verts = NULL;
 200         BLI_array_staticdeclare(edges, BM_NGON_STACK_SIZE);
 201         BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE);
 202         BMLoop *l_iter;
 203         BMLoop *l_first;
 204         BMLoop *l2;
 205         BMFace *f2;
 206         int i;
 207
 208         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 209         do {
 210                 if (copyverts) {
 211                         BMVert *v = BM_vert_create(bm, l_iter->v->co, l_iter->v);
 212                         BLI_array_append(verts, v);
 213                 }
 214                 else {
 215                         BLI_array_append(verts, l_iter->v);
 216                 }
 217         } while ((l_iter = l_iter->next) != l_first);
 218
 219         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 220         i = 0;
 221         do {
 222                 if (copyedges) {
 223                         BMEdge *e;
 224                         BMVert *v1, *v2;
 225
 226                         if (l_iter->e->v1 == verts[i]) {
 227                                 v1 = verts[i];
 228                                 v2 = verts[(i + 1) % f->len];
 229                         }
 230                         else {
 231                                 v2 = verts[i];
 232                                 v1 = verts[(i + 1) % f->len];
 233                         }
 234
 235                         e = BM_edge_create(bm,  v1, v2, l_iter->e, FALSE);
 236                         BLI_array_append(edges, e);
 237                 }
 238                 else {
 239                         BLI_array_append(edges, l_iter->e);
 240                 }
 241
 242                 i++;
 243         } while ((l_iter = l_iter->next) != l_first);
 244
 245         f2 = BM_face_create(bm, verts, edges, f->len, FALSE);
 246
 247         BM_elem_attrs_copy(bm, bm, f, f2);
 248
 249         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 250         l2 = BM_FACE_FIRST_LOOP(f2);
 251         do {
 252                 BM_elem_attrs_copy(bm, bm, l_iter, l2);
 253                 l2 = l2->next;
 254         } while ((l_iter = l_iter->next) != l_first);
 255
 256         return f2;
 257 }
 258
 259 BMFace *BM_face_create(BMesh *bm, BMVert **verts, BMEdge **edges, const int len, int nodouble)
 260 {
 261         BMFace *f = NULL;
 262         BMLoop *l, *startl, *lastl;
 263         int i, overlap;
 264
 265         if (len == 0) {
 266                 /* just return NULL for no */
 267                 return NULL;
 268         }
 269
 270         if (nodouble) {
 271                 /* Check if face already exists */
 272                 overlap = BM_face_exists(bm, verts, len, &f);
 273                 if (overlap) {
 274                         return f;
 275                 }
 276                 else {
 277                         BLI_assert(f == NULL);
 278                 }
 279         }
 280
 281         f = BLI_mempool_calloc(bm->fpool);
 282
 283 #ifdef USE_DEBUG_INDEX_MEMCHECK
 284         DEBUG_MEMCHECK_INDEX_INVALIDATE(f)
 285 #else
 286         BM_elem_index_set(f, -1); /* set_ok_invalid */
 287 #endif
 288
 289         bm->elem_index_dirty |= BM_FACE; /* may add to middle of the pool */
 290
 291         bm->totface++;
 292
 293         f->head.htype = BM_FACE;
 294
 295         startl = lastl = bm_face_boundry_add(bm, (BMFace *)f, verts[0], edges[0]);
 296
 297         startl->v = (BMVert *)verts[0];
 298         startl->e = (BMEdge *)edges[0];
 299         for (i = 1; i < len; i++) {
 300                 l = bmesh_create_loop(bm, verts[i], edges[i], (BMFace *)f, edges[i]->l);
 301
 302                 l->f = (BMFace *) f;
 303                 bmesh_radial_append(edges[i], l);
 304
 305                 l->prev = lastl;
 306                 lastl->next = l;
 307                 lastl = l;
 308         }
 309
 310         /* allocate flag */
 311         f->oflags = BLI_mempool_calloc(bm->toolflagpool);
 312
 313         CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
 314
 315         startl->prev = lastl;
 316         lastl->next = startl;
 317
 318         f->len = len;
 319
 320 #ifdef USE_BMESH_HOLES
 321         f->totbounds = 0;
 322 #endif
 323
 324         BM_CHECK_ELEMENT(bm, f);
 325
 326         return (BMFace *) f;
 327 }
 328
 329 int bmesh_check_element(BMesh *UNUSED(bm), void *element, const char htype)
 330 {
 331         BMHeader *head = element;
 332         int err = 0;
 333
 334         if (!element)
 335                 return 1;
 336
 337         if (head->htype != htype)
 338                 return 2;
 339
 340         switch (htype) {
 341                 case BM_VERT: {
 342                         BMVert *v = element;
 343                         if (v->e && v->e->head.htype != BM_EDGE) {
 344                                 err |= 4;
 345                         }
 346                         break;
 347                 }
 348                 case BM_EDGE: {
 349                         BMEdge *e = element;
 350                         if (e->l && e->l->head.htype != BM_LOOP)
 351                                 err |= 8;
 352                         if (e->l && e->l->f->head.htype != BM_FACE)
 353                                 err |= 16;
 354                         if (e->v1_disk_link.prev == NULL ||
 355                             e->v2_disk_link.prev == NULL ||
 356                             e->v1_disk_link.next == NULL ||
 357                             e->v2_disk_link.next == NULL)
 358                         {
 359                                 err |= 32;
 360                         }
 361                         if (e->l && (e->l->radial_next == NULL || e->l->radial_prev == NULL))
 362                                 err |= 64;
 363                         if (e->l && e->l->f->len <= 0)
 364                                 err |= 128;
 365                         break;
 366                 }
 367                 case BM_LOOP: {
 368                         BMLoop *l = element, *l2;
 369                         int i;
 370
 371                         if (l->f->head.htype != BM_FACE)
 372                                 err |= 256;
 373                         if (l->e->head.htype != BM_EDGE)
 374                                 err |= 512;
 375                         if (l->v->head.htype !=  BM_VERT)
 376                                 err |= 1024;
 377                         if (!BM_vert_in_edge(l->e, l->v)) {
 378                                 fprintf(stderr, "%s: fatal bmesh error (vert not in edge)! (bmesh internal error)\n", __func__);
 379                                 err |= 2048;
 380                         }
 381
 382                         if (l->radial_next == NULL || l->radial_prev == NULL)
 383                                 err |= (1 << 12);
 384                         if (l->f->len <= 0)
 385                                 err |= (1 << 13);
 386
 387                         /* validate boundary loop--invalid for hole loops, of course,
 388                  * but we won't be allowing those for a while ye */
 389                         l2 = l;
 390                         i = 0;
 391                         do {
 392                                 if (i >= BM_NGON_MAX) {
 393                                         break;
 394                                 }
 395
 396                                 i++;
 397                         } while ((l2 = l2->next) != l);
 398
 399                         if (i != l->f->len || l2 != l)
 400                                 err |= (1 << 14);
 401
 402                         if (!bmesh_radial_validate(bmesh_radial_length(l), l))
 403                                 err |= (1 << 15);
 404
 405                         break;
 406                 }
 407                 case BM_FACE: {
 408                         BMFace *f = element;
 409                         BMLoop *l_iter;
 410                         BMLoop *l_first;
 411                         int len = 0;
 412
 413 #ifdef USE_BMESH_HOLES
 414                         if (!f->loops.first)
 415 #else
 416                         if (!f->l_first)
 417 #endif
 418                         {
 419                                 err |= (1 << 16);
 420                         }
 421                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 422                         do {
 423                                 if (l_iter->f != f) {
 424                                         fprintf(stderr, "%s: loop inside one face points to another! (bmesh internal error)\n", __func__);
 425                                         err |= (1 << 17);
 426                                 }
 427
 428                                 if (!l_iter->e)
 429                                         err |= (1 << 18);
 430                                 if (!l_iter->v)
 431                                         err |= (1 << 19);
 432                                 if (!BM_vert_in_edge(l_iter->e, l_iter->v) || !BM_vert_in_edge(l_iter->e, l_iter->next->v)) {
 433                                         err |= (1 << 20);
 434                                 }
 435
 436                                 if (!bmesh_radial_validate(bmesh_radial_length(l_iter), l_iter))
 437                                         err |= (1 << 21);
 438
 439                                 if (!bmesh_disk_count(l_iter->v) || !bmesh_disk_count(l_iter->next->v))
 440                                         err |= (1 << 22);
 441
 442                                 len++;
 443                         } while ((l_iter = l_iter->next) != l_first);
 444
 445                         if (len != f->len)
 446                                 err |= (1 << 23);
 447                 }
 448         }
 449
 450         if (err) {
 451                 bmesh_error();
 452         }
 453
 454         return err;
 455 }
 456
 457 /* low level function, only free's,
 458  * does not change adjust surrounding geometry */
 459 static void bmesh_kill_only_vert(BMesh *bm, BMVert *v)
 460 {
 461         bm->totvert--;
 462         bm->elem_index_dirty |= BM_VERT;
 463
 464         BM_select_history_remove(bm, v);
 465         if (v->head.data)
 466                 CustomData_bmesh_free_block(&bm->vdata, &v->head.data);
 467
 468         BLI_mempool_free(bm->toolflagpool, v->oflags);
 469         BLI_mempool_free(bm->vpool, v);
 470 }
 471
 472 static void bmesh_kill_only_edge(BMesh *bm, BMEdge *e)
 473 {
 474         bm->totedge--;
 475         bm->elem_index_dirty |= BM_EDGE;
 476
 477         BM_select_history_remove(bm, e);
 478
 479         if (e->head.data)
 480                 CustomData_bmesh_free_block(&bm->edata, &e->head.data);
 481
 482         BLI_mempool_free(bm->toolflagpool, e->oflags);
 483         BLI_mempool_free(bm->epool, e);
 484 }
 485
 486 static void bmesh_kill_only_face(BMesh *bm, BMFace *f)
 487 {
 488         if (bm->act_face == f)
 489                 bm->act_face = NULL;
 490
 491         bm->totface--;
 492         bm->elem_index_dirty |= BM_FACE;
 493
 494         BM_select_history_remove(bm, f);
 495
 496         if (f->head.data)
 497                 CustomData_bmesh_free_block(&bm->pdata, &f->head.data);
 498
 499         BLI_mempool_free(bm->toolflagpool, f->oflags);
 500         BLI_mempool_free(bm->fpool, f);
 501 }
 502
 503 static void bmesh_kill_only_loop(BMesh *bm, BMLoop *l)
 504 {
 505         bm->totloop--;
 506         if (l->head.data)
 507                 CustomData_bmesh_free_block(&bm->ldata, &l->head.data);
 508
 509         BLI_mempool_free(bm->lpool, l);
 510 }
 511
 512 void BM_face_edges_kill(BMesh *bm, BMFace *f)
 513 {
 514         BMEdge **edges = NULL;
 515         BLI_array_staticdeclare(edges, BM_NGON_STACK_SIZE);
 516         BMLoop *l_iter;
 517         BMLoop *l_first;
 518         int i;
 519
 520         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 521         do {
 522                 BLI_array_append(edges, l_iter->e);
 523         } while ((l_iter = l_iter->next) != l_first);
 524
 525         for (i = 0; i < BLI_array_count(edges); i++) {
 526                 BM_edge_kill(bm, edges[i]);
 527         }
 528
 529         BLI_array_free(edges);
 530 }
 531
 532 void BM_face_verts_kill(BMesh *bm, BMFace *f)
 533 {
 534         BMVert **verts = NULL;
 535         BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE);
 536         BMLoop *l_iter;
 537         BMLoop *l_first;
 538         int i;
 539
 540         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 541         do {
 542                 BLI_array_append(verts, l_iter->v);
 543         } while ((l_iter = l_iter->next) != l_first);
 544
 545         for (i = 0; i < BLI_array_count(verts); i++) {
 546                 BM_vert_kill(bm, verts[i]);
 547         }
 548
 549         BLI_array_free(verts);
 550 }
 551
 552 void BM_face_kill(BMesh *bm, BMFace *f)
 553 {
 554 #ifdef USE_BMESH_HOLES
 555         BMLoopList *ls, *ls_next;
 556 #endif
 557
 558         BM_CHECK_ELEMENT(bm, f);
 559
 560 #ifdef USE_BMESH_HOLES
 561         for (ls = f->loops.first; ls; ls = ls_next)
 562 #else
 563         if (f->l_first)
 564 #endif
 565         {
 566                 BMLoop *l_iter, *l_next, *l_first;
 567
 568 #ifdef USE_BMESH_HOLES
 569                 ls_next = ls->next;
 570                 l_iter = l_first = ls->first;
 571 #else
 572                 l_iter = l_first = f->l_first;
 573 #endif
 574
 575                 do {
 576                         l_next = l_iter->next;
 577
 578                         bmesh_radial_remove_loop(l_iter, l_iter->e);
 579                         bmesh_kill_only_loop(bm, l_iter);
 580
 581                 } while ((l_iter = l_next) != l_first);
 582
 583 #ifdef USE_BMESH_HOLES
 584                 BLI_mempool_free(bm->looplistpool, ls);
 585 #endif
 586         }
 587
 588         bmesh_kill_only_face(bm, f);
 589 }
 590
 591 void BM_edge_kill(BMesh *bm, BMEdge *e)
 592 {
 593
 594         bmesh_disk_remove_edge(e, e->v1);
 595         bmesh_disk_remove_edge(e, e->v2);
 596
 597         if (e->l) {
 598                 BMLoop *l = e->l, *lnext, *startl = e->l;
 599
 600                 do {
 601                         lnext = l->radial_next;
 602                         if (lnext->f == l->f) {
 603                                 BM_face_kill(bm, l->f);
 604                                 break;
 605                         }
 606
 607                         BM_face_kill(bm, l->f);
 608
 609                         if (l == lnext)
 610                                 break;
 611                         l = lnext;
 612                 } while (l != startl);
 613         }
 614
 615         bmesh_kill_only_edge(bm, e);
 616 }
 617
 618 void BM_vert_kill(BMesh *bm, BMVert *v)
 619 {
 620         if (v->e) {
 621                 BMEdge *e, *nexte;
 622
 623                 e = v->e;
 624                 while (v->e) {
 625                         nexte = bmesh_disk_nextedge(e, v);
 626                         BM_edge_kill(bm, e);
 627                         e = nexte;
 628                 }
 629         }
 630
 631         bmesh_kill_only_vert(bm, v);
 632 }
 633
 634 /********** private disk and radial cycle functions ********** */
 635
 636 /**
 637  *                      bmesh_loop_reverse
 638  *
 639  *      FLIP FACE EULER
 640  *
 641  *      Changes the winding order of a face from CW to CCW or vice versa.
 642  *      This euler is a bit peculiar in compairson to others as it is its
 643  *      own inverse.
 644  *
 645  *      BMESH_TODO: reinsert validation code.
 646  *
 647  *  Returns -
 648  *      1 for success, 0 for failure.
 649  */
 650
 651 static int bmesh_loop_length(BMLoop *l)
 652 {
 653         BMLoop *l_first = l;
 654         int i = 0;
 655
 656         do {
 657                 i++;
 658         } while ((l = l->next) != l_first);
 659
 660         return i;
 661 }
 662
 663 static int bmesh_loop_reverse_loop(BMesh *bm, BMFace *f
 664 #ifdef USE_BMESH_HOLES
 665                                    , BMLoopList *lst
 666 #endif
 667                                    )
 668 {
 669
 670 #ifdef USE_BMESH_HOLES
 671         BMLoop *l_first = lst->first;
 672 #else
 673         BMLoop *l_first = f->l_first;
 674 #endif
 675
 676         BMLoop *l_iter, *oldprev, *oldnext;
 677         BMEdge **edar = NULL;
 678         MDisps *md;
 679         BLI_array_staticdeclare(edar, BM_NGON_STACK_SIZE);
 680         int i, j, edok, len = 0, do_disps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
 681
 682         len = bmesh_loop_length(l_first);
 683
 684         for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next) {
 685                 BMEdge *curedge = l_iter->e;
 686                 bmesh_radial_remove_loop(l_iter, curedge);
 687                 BLI_array_append(edar, curedge);
 688         }
 689
 690         /* actually reverse the loop */
 691         for (i = 0, l_iter = l_first; i < len; i++) {
 692                 oldnext = l_iter->next;
 693                 oldprev = l_iter->prev;
 694                 l_iter->next = oldprev;
 695                 l_iter->prev = oldnext;
 696                 l_iter = oldnext;
 697
 698                 if (do_disps) {
 699                         float (*co)[3];
 700                         int x, y, sides;
 701
 702                         md = CustomData_bmesh_get(&bm->ldata, l_iter->head.data, CD_MDISPS);
 703                         if (!md->totdisp || !md->disps)
 704                                 continue;
 705
 706                         sides = (int)sqrt(md->totdisp);
 707                         co = md->disps;
 708
 709                         for (x = 0; x < sides; x++) {
 710                                 for (y = 0; y < x; y++) {
 711                                         swap_v3_v3(co[y * sides + x], co[sides * x + y]);
 712                                 }
 713                         }
 714                 }
 715         }
 716
 717         if (len == 2) { /* two edged face */
 718                 /* do some verification here! */
 719                 l_first->e = edar[1];
 720                 l_first->next->e = edar[0];
 721         }
 722         else {
 723                 for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next) {
 724                         edok = 0;
 725                         for (j = 0; j < len; j++) {
 726                                 edok = bmesh_verts_in_edge(l_iter->v, l_iter->next->v, edar[j]);
 727                                 if (edok) {
 728                                         l_iter->e = edar[j];
 729                                         break;
 730                                 }
 731                         }
 732                 }
 733         }
 734         /* rebuild radia */
 735         for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next)
 736                 bmesh_radial_append(l_iter->e, l_iter);
 737
 738         /* validate radia */
 739         for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next) {
 740                 BM_CHECK_ELEMENT(bm, l_iter);
 741                 BM_CHECK_ELEMENT(bm, l_iter->e);
 742                 BM_CHECK_ELEMENT(bm, l_iter->v);
 743                 BM_CHECK_ELEMENT(bm, l_iter->f);
 744         }
 745
 746         BLI_array_free(edar);
 747
 748         BM_CHECK_ELEMENT(bm, f);
 749
 750         return 1;
 751 }
 752
 753 int bmesh_loop_reverse(BMesh *bm, BMFace *f)
 754 {
 755 #ifdef USE_BMESH_HOLES
 756         return bmesh_loop_reverse_loop(bm, f, f->loops.first);
 757 #else
 758         return bmesh_loop_reverse_loop(bm, f);
 759 #endif
 760 }
 761
 762 static void bmesh_systag_elements(BMesh *UNUSED(bm), void *veles, int tot, int flag)
 763 {
 764         BMHeader **eles = veles;
 765         int i;
 766
 767         for (i = 0; i < tot; i++) {
 768                 BM_ELEM_API_FLAG_ENABLE((BMElemF *)eles[i], flag);
 769         }
 770 }
 771
 772 static void bmesh_clear_systag_elements(BMesh *UNUSED(bm), void *veles, int tot, int flag)
 773 {
 774         BMHeader **eles = veles;
 775         int i;
 776
 777         for (i = 0; i < tot; i++) {
 778                 BM_ELEM_API_FLAG_DISABLE((BMElemF *)eles[i], flag);
 779         }
 780 }
 781
 782 #define FACE_MARK       (1 << 10)
 783
 784 static int count_flagged_radial(BMesh *bm, BMLoop *l, int flag)
 785 {
 786         BMLoop *l2 = l;
 787         int i = 0, c = 0;
 788
 789         do {
 790                 if (!l2) {
 791                         bmesh_error();
 792                         goto error;
 793                 }
 794
 795                 i += BM_ELEM_API_FLAG_TEST(l2->f, flag) ? 1 : 0;
 796                 l2 = bmesh_radial_nextloop(l2);
 797                 if (c >= BM_LOOP_RADIAL_MAX) {
 798                         bmesh_error();
 799                         goto error;
 800                 }
 801                 c++;
 802         } while (l2 != l);
 803
 804         return i;
 805
 806 error:
 807         BMO_error_raise(bm, bm->currentop, BMERR_MESH_ERROR, NULL);
 808         return 0;
 809 }
 810
 811 static int UNUSED_FUNCTION(count_flagged_disk)(BMVert *v, int flag)
 812 {
 813         BMEdge *e = v->e;
 814         int i = 0;
 815
 816         if (!e)
 817                 return 0;
 818
 819         do {
 820                 i += BM_ELEM_API_FLAG_TEST(e, flag) ? 1 : 0;
 821                 e = bmesh_disk_nextedge(e, v);
 822         } while (e != v->e);
 823
 824         return i;
 825 }
 826
 827 static int disk_is_flagged(BMVert *v, int flag)
 828 {
 829         BMEdge *e = v->e;
 830
 831         if (!e)
 832                 return FALSE;
 833
 834         do {
 835                 BMLoop *l = e->l;
 836
 837                 if (!l) {
 838                         return FALSE;
 839                 }
 840
 841                 if (bmesh_radial_length(l) == 1)
 842                         return FALSE;
 843
 844                 do {
 845                         if (!BM_ELEM_API_FLAG_TEST(l->f, flag))
 846                                 return FALSE;
 847
 848                         l = l->radial_next;
 849                 } while (l != e->l);
 850
 851                 e = bmesh_disk_nextedge(e, v);
 852         } while (e != v->e);
 853
 854         return TRUE;
 855 }
 856
 857 /* Midlevel Topology Manipulation Functions */
 858
 859 /*
 860  * BM_faces_join
 861  *
 862  * Joins a collected group of faces into one. Only restriction on
 863  * the input data is that the faces must be connected to each other.
 864  *
 865  * If a pair of faces share multiple edges, the pair of
 866  * faces will be joined at every edge.
 867  *
 868  * Returns a pointer to the combined face.
 869  */
 870 BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface)
 871 {
 872         BMFace *f, *newf;
 873 #ifdef USE_BMESH_HOLES
 874         BMLoopList *lst;
 875         ListBase holes = {NULL, NULL};
 876 #endif
 877         BMLoop *l_iter;
 878         BMLoop *l_first;
 879         BMEdge **edges = NULL;
 880         BMEdge **deledges = NULL;
 881         BMVert **delverts = NULL;
 882         BLI_array_staticdeclare(edges,    BM_NGON_STACK_SIZE);
 883         BLI_array_staticdeclare(deledges, BM_NGON_STACK_SIZE);
 884         BLI_array_staticdeclare(delverts, BM_NGON_STACK_SIZE);
 885         BMVert *v1 = NULL, *v2 = NULL;
 886         const char *err = NULL;
 887         int i, tote = 0;
 888
 889         if (!totface) {
 890                 bmesh_error();
 891                 return NULL;
 892         }
 893
 894         if (totface == 1)
 895                 return faces[0];
 896
 897         bmesh_systag_elements(bm, faces, totface, _FLAG_JF);
 898
 899         for (i = 0; i < totface; i++) {
 900                 f = faces[i];
 901                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 902                 do {
 903                         int rlen = count_flagged_radial(bm, l_iter, _FLAG_JF);
 904
 905                         if (rlen > 2) {
 906                                 err = "Input faces do not form a contiguous manifold region";
 907                                 goto error;
 908                         }
 909                         else if (rlen == 1) {
 910                                 BLI_array_append(edges, l_iter->e);
 911
 912                                 if (!v1) {
 913                                         v1 = l_iter->v;
 914                                         v2 = BM_edge_other_vert(l_iter->e, l_iter->v);
 915                                 }
 916                                 tote++;
 917                         }
 918                         else if (rlen == 2) {
 919                                 int d1, d2;
 920
 921                                 d1 = disk_is_flagged(l_iter->e->v1, _FLAG_JF);
 922                                 d2 = disk_is_flagged(l_iter->e->v2, _FLAG_JF);
 923
 924                                 if (!d1 && !d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e, _FLAG_JF)) {
 925                                         /* don't remove an edge it makes up the side of another face
 926                                          * else this will remove the face as well - campbell */
 927                                         if (BM_edge_face_count(l_iter->e) <= 2) {
 928                                                 BLI_array_append(deledges, l_iter->e);
 929                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e, _FLAG_JF);
 930                                         }
 931                                 }
 932                                 else {
 933                                         if (d1 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v1, _FLAG_JF)) {
 934                                                 BLI_array_append(delverts, l_iter->e->v1);
 935                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e->v1, _FLAG_JF);
 936                                         }
 937
 938                                         if (d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v2, _FLAG_JF)) {
 939                                                 BLI_array_append(delverts, l_iter->e->v2);
 940                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e->v2, _FLAG_JF);
 941                                         }
 942                                 }
 943                         }
 944                 } while ((l_iter = l_iter->next) != l_first);
 945
 946 #ifdef USE_BMESH_HOLES
 947                 for (lst = f->loops.first; lst; lst = lst->next) {
 948                         if (lst == f->loops.first) continue;
 949
 950                         BLI_remlink(&f->loops, lst);
 951                         BLI_addtail(&holes, lst);
 952                 }
 953 #endif
 954
 955         }
 956
 957         /* create region fac */
 958         newf = BM_face_create_ngon(bm, v1, v2, edges, tote, FALSE);
 959         if (!newf || BMO_error_occurred(bm)) {
 960                 if (!BMO_error_occurred(bm))
 961                         err = "Invalid boundary region to join faces";
 962                 goto error;
 963         }
 964
 965         /* copy over loop data */
 966         l_iter = l_first = BM_FACE_FIRST_LOOP(newf);
 967         do {
 968                 BMLoop *l2 = l_iter->radial_next;
 969
 970                 do {
 971                         if (BM_ELEM_API_FLAG_TEST(l2->f, _FLAG_JF))
 972                                 break;
 973                         l2 = l2->radial_next;
 974                 } while (l2 != l_iter);
 975
 976                 if (l2 != l_iter) {
 977                         /* I think this is correct */
 978                         if (l2->v != l_iter->v) {
 979                                 l2 = l2->next;
 980                         }
 981
 982                         BM_elem_attrs_copy(bm, bm, l2, l_iter);
 983                 }
 984         } while ((l_iter = l_iter->next) != l_first);
 985
 986         BM_elem_attrs_copy(bm, bm, faces[0], newf);
 987
 988 #ifdef USE_BMESH_HOLES
 989         /* add hole */
 990         BLI_movelisttolist(&newf->loops, &holes);
 991 #endif
 992
 993         /* update loop face pointer */
 994 #ifdef USE_BMESH_HOLES
 995         for (lst = newf->loops.first; lst; lst = lst->next)
 996 #endif
 997         {
 998 #ifdef USE_BMESH_HOLES
 999                 l_iter = l_first = lst->first;
1000 #else
1001                 l_iter = l_first = BM_FACE_FIRST_LOOP(newf);
1002 #endif
1003                 do {
1004                         l_iter->f = newf;
1005                 } while ((l_iter = l_iter->next) != l_first);
1006         }
1007
1008         bmesh_clear_systag_elements(bm, faces, totface, _FLAG_JF);
1009         BM_ELEM_API_FLAG_DISABLE(newf, _FLAG_JF);
1010
1011         /* handle multires data */
1012         if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
1013                 l_iter = l_first = BM_FACE_FIRST_LOOP(newf);
1014                 do {
1015                         for (i = 0; i < totface; i++) {
1016                                 BM_loop_interp_multires(bm, l_iter, faces[i]);
1017                         }
1018                 } while ((l_iter = l_iter->next) != l_first);
1019         }
1020
1021         /* delete old geometr */
1022         for (i = 0; i < BLI_array_count(deledges); i++) {
1023                 BM_edge_kill(bm, deledges[i]);
1024         }
1025
1026         for (i = 0; i < BLI_array_count(delverts); i++) {
1027                 BM_vert_kill(bm, delverts[i]);
1028         }
1029
1030         BLI_array_free(edges);
1031         BLI_array_free(deledges);
1032         BLI_array_free(delverts);
1033
1034         BM_CHECK_ELEMENT(bm, newf);
1035         return newf;
1036 error:
1037         bmesh_clear_systag_elements(bm, faces, totface, _FLAG_JF);
1038         BLI_array_free(edges);
1039         BLI_array_free(deledges);
1040         BLI_array_free(delverts);
1041
1042         if (err) {
1043                 BMO_error_raise(bm, bm->currentop, BMERR_DISSOLVEFACES_FAILED, err);
1044         }
1045         return NULL;
1046 }
1047
1048 static BMFace *bmesh_addpolylist(BMesh *bm, BMFace *UNUSED(example))
1049 {
1050         BMFace *f;
1051 #ifdef USE_BMESH_HOLES
1052         BMLoopList *lst;
1053 #endif
1054
1055         f = BLI_mempool_calloc(bm->fpool);
1056 #ifdef USE_BMESH_HOLES
1057         lst = BLI_mempool_calloc(bm->looplistpool);
1058 #endif
1059
1060         f->head.htype = BM_FACE;
1061 #ifdef USE_BMESH_HOLES
1062         BLI_addtail(&f->loops, lst);
1063 #endif
1064
1065 #ifdef USE_DEBUG_INDEX_MEMCHECK
1066         DEBUG_MEMCHECK_INDEX_INVALIDATE(f)
1067 #else
1068         BM_elem_index_set(f, -1); /* set_ok_invalid */
1069 #endif
1070
1071         bm->elem_index_dirty |= BM_FACE; /* may add to middle of the pool */
1072
1073         bm->totface++;
1074
1075         /* allocate flag */
1076         f->oflags = BLI_mempool_calloc(bm->toolflagpool);
1077
1078         CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
1079
1080         f->len = 0;
1081
1082 #ifdef USE_BMESH_HOLES
1083         f->totbounds = 1;
1084 #endif
1085
1086         return (BMFace *) f;
1087 }
1088
1089 /**
1090  *                      bmesh_SFME
1091  *
1092  *      SPLIT FACE MAKE EDGE:
1093  *
1094  *      Takes as input two vertices in a single face. An edge is created which divides the original face
1095  *      into two distinct regions. One of the regions is assigned to the original face and it is closed off.
1096  *      The second region has a new face assigned to it.
1097  *
1098  *      Examples:
1099  *
1100  *     Before:               After:
1101  *       ----------           ----------
1102  *       |        |           |        |
1103  *       |        |           |   f1   |
1104  *      v1   f1   v2          v1======v2
1105  *       |        |           |   f2   |
1106  *       |        |           |        |
1107  *       ----------           ----------
1108  *
1109  *      Note that the input vertices can be part of the same edge. This will
1110  *  result in a two edged face. This is desirable for advanced construction
1111  *  tools and particularly essential for edge bevel. Because of this it is
1112  *  up to the caller to decide what to do with the extra edge.
1113  *
1114  *  If holes is NULL, then both faces will lose
1115  *  all holes from the original face.  Also, you cannot split between
1116  *  a hole vert and a boundary vert; that case is handled by higher-
1117  *  level wrapping functions (when holes are fully implemented, anyway).
1118  *
1119  *  Note that holes represents which holes goes to the new face, and of
1120  *  course this requires removing them from the exitsing face first, since
1121  *  you cannot have linked list links inside multiple lists.
1122  *
1123  *      Returns -
1124  *  A BMFace pointer
1125  */
1126 BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2,
1127                    BMLoop **rl,
1128 #ifdef USE_BMESH_HOLES
1129                    ListBase *holes,
1130 #endif
1131                    BMEdge *example
1132                    )
1133 {
1134 #ifdef USE_BMESH_HOLES
1135         BMLoopList *lst, *lst2;
1136 #endif
1137
1138         BMFace *f2;
1139         BMLoop *l_iter, *l_first;
1140         BMLoop *v1loop = NULL, *v2loop = NULL, *f1loop = NULL, *f2loop = NULL;
1141         BMEdge *e;
1142         int i, len, f1len, f2len;
1143
1144         /* verify that v1 and v2 are in face */
1145         len = f->len;
1146         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < len; i++, l_iter = l_iter->next) {
1147                 if (l_iter->v == v1) v1loop = l_iter;
1148                 else if (l_iter->v == v2) v2loop = l_iter;
1149         }
1150
1151         if (!v1loop || !v2loop) {
1152                 return NULL;
1153         }
1154
1155         /* allocate new edge between v1 and v2 */
1156         e = BM_edge_create(bm, v1, v2, example, FALSE);
1157
1158         f2 = bmesh_addpolylist(bm, f);
1159         f1loop = bmesh_create_loop(bm, v2, e, f, v2loop);
1160         f2loop = bmesh_create_loop(bm, v1, e, f2, v1loop);
1161
1162         f1loop->prev = v2loop->prev;
1163         f2loop->prev = v1loop->prev;
1164         v2loop->prev->next = f1loop;
1165         v1loop->prev->next = f2loop;
1166
1167         f1loop->next = v1loop;
1168         f2loop->next = v2loop;
1169         v1loop->prev = f1loop;
1170         v2loop->prev = f2loop;
1171
1172 #ifdef USE_BMESH_HOLES
1173         lst = f->loops.first;
1174         lst2 = f2->loops.first;
1175
1176         lst2->first = lst2->last = f2loop;
1177         lst->first = lst->last = f1loop;
1178 #else
1179         f2->l_first = f2loop;
1180         f->l_first = f1loop;
1181 #endif
1182
1183         /* validate both loop */
1184         /* I dont know how many loops are supposed to be in each face at this point! FIXME */
1185
1186         /* go through all of f2's loops and make sure they point to it properly */
1187         l_iter = l_first = BM_FACE_FIRST_LOOP(f2);
1188         f2len = 0;
1189         do {
1190                 l_iter->f = f2;
1191                 f2len++;
1192         } while ((l_iter = l_iter->next) != l_first);
1193
1194         /* link up the new loops into the new edges radia */
1195         bmesh_radial_append(e, f1loop);
1196         bmesh_radial_append(e, f2loop);
1197
1198         f2->len = f2len;
1199
1200         f1len = 0;
1201         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1202         do {
1203                 f1len++;
1204         } while ((l_iter = l_iter->next) != l_first);
1205
1206         f->len = f1len;
1207
1208         if (rl) *rl = f2loop;
1209
1210 #ifdef USE_BMESH_HOLES
1211         if (holes) {
1212                 BLI_movelisttolist(&f2->loops, holes);
1213         }
1214         else {
1215                 /* this code is not significant until holes actually work */
1216                 //printf("warning: call to split face euler without holes argument; holes will be tossed.\n");
1217                 for (lst = f->loops.last; lst != f->loops.first; lst = lst2) {
1218                         lst2 = lst->prev;
1219                         BLI_mempool_free(bm->looplistpool, lst);
1220                 }
1221         }
1222 #endif
1223
1224         BM_CHECK_ELEMENT(bm, e);
1225         BM_CHECK_ELEMENT(bm, f);
1226         BM_CHECK_ELEMENT(bm, f2);
1227
1228         return f2;
1229 }
1230
1231 /**
1232  *                      bmesh_SEMV
1233  *
1234  *      SPLIT EDGE MAKE VERT:
1235  *      Takes a given edge and splits it into two, creating a new vert.
1236  *
1237  *
1238  *              Before: OV---------TV
1239  *              After:  OV----NV---TV
1240  *
1241  *  Returns -
1242  *      BMVert pointer.
1243  *
1244  */
1245
1246 BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **re)
1247 {
1248         BMLoop *nextl;
1249         BMEdge *ne;
1250         BMVert *nv, *ov;
1251         int i, edok, valence1 = 0, valence2 = 0;
1252
1253         if (bmesh_vert_in_edge(e, tv) == 0) {
1254                 return NULL;
1255         }
1256         ov = bmesh_edge_getothervert(e, tv);
1257
1258         /* count valence of v1 */
1259         valence1 = bmesh_disk_count(ov);
1260
1261         /* count valence of v2 */
1262         valence2 = bmesh_disk_count(tv);
1263
1264         nv = BM_vert_create(bm, tv->co, tv);
1265         ne = BM_edge_create(bm, nv, tv, e, FALSE);
1266
1267         bmesh_disk_remove_edge(ne, tv);
1268         bmesh_disk_remove_edge(ne, nv);
1269
1270         /* remove e from v2's disk cycle */
1271         bmesh_disk_remove_edge(e, tv);
1272
1273         /* swap out tv for nv in e */
1274         bmesh_edge_swapverts(e, tv, nv);
1275
1276         /* add e to nv's disk cycl */
1277         bmesh_disk_append_edge(e, nv);
1278
1279         /* add ne to nv's disk cycl */
1280         bmesh_disk_append_edge(ne, nv);
1281
1282         /* add ne to tv's disk cycl */
1283         bmesh_disk_append_edge(ne, tv);
1284
1285         /* verify disk cycle */
1286         edok = bmesh_disk_validate(valence1, ov->e, ov);
1287         if (!edok) bmesh_error();
1288         edok = bmesh_disk_validate(valence2, tv->e, tv);
1289         if (!edok) bmesh_error();
1290         edok = bmesh_disk_validate(2, nv->e, nv);
1291         if (!edok) bmesh_error();
1292
1293         /* Split the radial cycle if presen */
1294         nextl = e->l;
1295         e->l = NULL;
1296         if (nextl) {
1297                 BMLoop *nl, *l;
1298                 int radlen = bmesh_radial_length(nextl);
1299                 int first1 = 0, first2 = 0;
1300
1301                 /* Take the next loop. Remove it from radial. Split it. Append to appropriate radials */
1302                 while (nextl) {
1303                         l = nextl;
1304                         l->f->len++;
1305                         nextl = nextl != nextl->radial_next ? nextl->radial_next : NULL;
1306                         bmesh_radial_remove_loop(l, NULL);
1307
1308                         nl = bmesh_create_loop(bm, NULL, NULL, l->f, l);
1309                         nl->prev = l;
1310                         nl->next = (l->next);
1311                         nl->prev->next = nl;
1312                         nl->next->prev = nl;
1313                         nl->v = nv;
1314
1315                         /* assign the correct edge to the correct loo */
1316                         if (bmesh_verts_in_edge(nl->v, nl->next->v, e)) {
1317                                 nl->e = e;
1318                                 l->e = ne;
1319
1320                                 /* append l into ne's rad cycl */
1321                                 if (!first1) {
1322                                         first1 = 1;
1323                                         l->radial_next = l->radial_prev = NULL;
1324                                 }
1325
1326                                 if (!first2) {
1327                                         first2 = 1;
1328                                         l->radial_next = l->radial_prev = NULL;
1329                                 }
1330
1331                                 bmesh_radial_append(nl->e, nl);
1332                                 bmesh_radial_append(l->e, l);
1333                         }
1334                         else if (bmesh_verts_in_edge(nl->v, nl->next->v, ne)) {
1335                                 nl->e = ne;
1336                                 l->e = e;
1337
1338                                 /* append l into ne's rad cycl */
1339                                 if (!first1) {
1340                                         first1 = 1;
1341                                         l->radial_next = l->radial_prev = NULL;
1342                                 }
1343
1344                                 if (!first2) {
1345                                         first2 = 1;
1346                                         l->radial_next = l->radial_prev = NULL;
1347                                 }
1348
1349                                 bmesh_radial_append(nl->e, nl);
1350                                 bmesh_radial_append(l->e, l);
1351                         }
1352
1353                 }
1354
1355                 /* verify length of radial cycl */
1356                 edok = bmesh_radial_validate(radlen, e->l);
1357                 if (!edok) bmesh_error();
1358                 edok = bmesh_radial_validate(radlen, ne->l);
1359                 if (!edok) bmesh_error();
1360
1361                 /* verify loop->v and loop->next->v pointers for  */
1362                 for (i = 0, l = e->l; i < radlen; i++, l = l->radial_next) {
1363                         if (!(l->e == e)) bmesh_error();
1364                         //if (!(l->radial_next == l)) bmesh_error();
1365                         if (l->prev->e != ne && l->next->e != ne) {
1366                                 bmesh_error();
1367                         }
1368                         edok = bmesh_verts_in_edge(l->v, l->next->v, e);
1369                         if (!edok)               bmesh_error();
1370                         if (l->v == l->next->v)  bmesh_error();
1371                         if (l->e == l->next->e)  bmesh_error();
1372
1373                         /* verify loop cycle for kloop-> */
1374                         BM_CHECK_ELEMENT(bm, l);
1375                         BM_CHECK_ELEMENT(bm, l->v);
1376                         BM_CHECK_ELEMENT(bm, l->e);
1377                         BM_CHECK_ELEMENT(bm, l->f);
1378                 }
1379                 /* verify loop->v and loop->next->v pointers for n */
1380                 for (i = 0, l = ne->l; i < radlen; i++, l = l->radial_next) {
1381                         if (!(l->e == ne)) bmesh_error();
1382                         //if (!(l->radial_next == l)) bmesh_error();
1383                         if (l->prev->e != e && l->next->e != e) bmesh_error();
1384                         edok = bmesh_verts_in_edge(l->v, l->next->v, ne);
1385                         if (!edok)                bmesh_error();
1386                         if (l->v == l->next->v)  bmesh_error();
1387                         if (l->e == l->next->e)  bmesh_error();
1388
1389                         BM_CHECK_ELEMENT(bm, l);
1390                         BM_CHECK_ELEMENT(bm, l->v);
1391                         BM_CHECK_ELEMENT(bm, l->e);
1392                         BM_CHECK_ELEMENT(bm, l->f);
1393                 }
1394         }
1395
1396         BM_CHECK_ELEMENT(bm, ne);
1397         BM_CHECK_ELEMENT(bm, nv);
1398         BM_CHECK_ELEMENT(bm, ov);
1399         BM_CHECK_ELEMENT(bm, e);
1400         BM_CHECK_ELEMENT(bm, tv);
1401
1402         if (re) *re = ne;
1403         return nv;
1404 }
1405
1406 /**
1407  *                      bmesh_JEKV
1408  *
1409  *      JOIN EDGE KILL VERT:
1410  *      Takes a an edge and pointer to one of its vertices and collapses
1411  *      the edge on that vertex.
1412  *
1413  *      Before:    OE      KE
1414  *               ------- -------
1415  *               |     ||      |
1416  *              OV     KV      TV
1417  *
1418  *
1419  *   After:             OE
1420  *               ---------------
1421  *               |             |
1422  *              OV             TV
1423  *
1424  *
1425  *      Restrictions:
1426  *      KV is a vertex that must have a valance of exactly two. Furthermore
1427  *  both edges in KV's disk cycle (OE and KE) must be unique (no double
1428  *  edges).
1429  *
1430  *      It should also be noted that this euler has the possibility of creating
1431  *      faces with just 2 edges. It is up to the caller to decide what to do with
1432  *  these faces.
1433  *
1434  *  Returns -
1435  *      1 for success, 0 for failure.
1436  */
1437 int bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv)
1438 {
1439         BMEdge *oe;
1440         BMVert *ov, *tv;
1441         BMLoop *killoop, *l;
1442         int len, radlen = 0, halt = 0, i, valence1, valence2, edok;
1443
1444         if (bmesh_vert_in_edge(ke, kv) == 0) {
1445                 return FALSE;
1446         }
1447
1448         len = bmesh_disk_count(kv);
1449
1450         if (len == 2) {
1451                 oe = bmesh_disk_nextedge(ke, kv);
1452                 tv = bmesh_edge_getothervert(ke, kv);
1453                 ov = bmesh_edge_getothervert(oe, kv);
1454                 halt = bmesh_verts_in_edge(kv, tv, oe); /* check for double edge */
1455
1456                 if (halt) {
1457                         return FALSE;
1458                 }
1459                 else {
1460                         /* For verification later, count valence of ov and t */
1461                         valence1 = bmesh_disk_count(ov);
1462                         valence2 = bmesh_disk_count(tv);
1463
1464                         /* remove oe from kv's disk cycl */
1465                         bmesh_disk_remove_edge(oe, kv);
1466                         /* relink oe->kv to be oe->t */
1467                         bmesh_edge_swapverts(oe, kv, tv);
1468                         /* append oe to tv's disk cycl */
1469                         bmesh_disk_append_edge(oe, tv);
1470                         /* remove ke from tv's disk cycl */
1471                         bmesh_disk_remove_edge(ke, tv);
1472
1473                         /* deal with radial cycle of k */
1474                         radlen = bmesh_radial_length(ke->l);
1475                         if (ke->l) {
1476                                 /* first step, fix the neighboring loops of all loops in ke's radial cycl */
1477                                 for (i = 0, killoop = ke->l; i < radlen; i++, killoop = bmesh_radial_nextloop(killoop)) {
1478                                         /* relink loops and fix vertex pointer */
1479                                         if (killoop->next->v == kv) {
1480                                                 killoop->next->v = tv;
1481                                         }
1482
1483                                         killoop->next->prev = killoop->prev;
1484                                         killoop->prev->next = killoop->next;
1485                                         if (BM_FACE_FIRST_LOOP(killoop->f) == killoop) {
1486                                                 BM_FACE_FIRST_LOOP(killoop->f) = killoop->next;
1487                                         }
1488                                         killoop->next = NULL;
1489                                         killoop->prev = NULL;
1490
1491                                         /* fix len attribute of fac */
1492                                         killoop->f->len--;
1493                                 }
1494                                 /* second step, remove all the hanging loops attached to k */
1495                                 radlen = bmesh_radial_length(ke->l);
1496
1497                                 if (LIKELY(radlen)) {
1498                                         BMLoop **loops = NULL;
1499                                         BLI_array_fixedstack_declare(loops, BM_NGON_STACK_SIZE, radlen, __func__);
1500
1501                                         killoop = ke->l;
1502
1503                                         /* this should be wrapped into a bme_free_radial function to be used by bmesh_KF as well.. */
1504                                         for (i = 0; i < radlen; i++) {
1505                                                 loops[i] = killoop;
1506                                                 killoop = bmesh_radial_nextloop(killoop);
1507                                         }
1508                                         for (i = 0; i < radlen; i++) {
1509                                                 bm->totloop--;
1510                                                 BLI_mempool_free(bm->lpool, loops[i]);
1511                                         }
1512                                         BLI_array_fixedstack_free(loops);
1513                                 }
1514
1515                                 /* Validate radial cycle of o */
1516                                 edok = bmesh_radial_validate(radlen, oe->l);
1517                                 if (!edok) {
1518                                         bmesh_error();
1519                                 }
1520                         }
1521
1522                         /* deallocate edg */
1523                         bmesh_kill_only_edge(bm, ke);
1524
1525                         /* deallocate verte */
1526                         bmesh_kill_only_vert(bm, kv);
1527
1528                         /* Validate disk cycle lengths of ov, tv are unchange */
1529                         edok = bmesh_disk_validate(valence1, ov->e, ov);
1530                         if (!edok) bmesh_error();
1531                         edok = bmesh_disk_validate(valence2, tv->e, tv);
1532                         if (!edok) bmesh_error();
1533
1534                         /* Validate loop cycle of all faces attached to o */
1535                         for (i = 0, l = oe->l; i < radlen; i++, l = bmesh_radial_nextloop(l)) {
1536                                 if (l->e != oe) bmesh_error();
1537                                 edok = bmesh_verts_in_edge(l->v, l->next->v, oe);
1538                                 if (!edok) bmesh_error();
1539                                 edok = bmesh_loop_validate(l->f);
1540                                 if (!edok) bmesh_error();
1541
1542                                 BM_CHECK_ELEMENT(bm, l);
1543                                 BM_CHECK_ELEMENT(bm, l->v);
1544                                 BM_CHECK_ELEMENT(bm, l->e);
1545                                 BM_CHECK_ELEMENT(bm, l->f);
1546                         }
1547
1548                         BM_CHECK_ELEMENT(bm, ov);
1549                         BM_CHECK_ELEMENT(bm, tv);
1550                         BM_CHECK_ELEMENT(bm, oe);
1551
1552                         return TRUE;
1553                 }
1554         }
1555         return FALSE;
1556 }
1557
1558 /**
1559  *                      bmesh_JFKE
1560  *
1561  *      JOIN FACE KILL EDGE:
1562  *
1563  *      Takes two faces joined by a single 2-manifold edge and fuses them togather.
1564  *      The edge shared by the faces must not be connected to any other edges which have
1565  *      Both faces in its radial cycle
1566  *
1567  *      Examples:
1568  *
1569  *        A                   B
1570  *       ----------           ----------
1571  *       |        |           |        |
1572  *       |   f1   |           |   f1   |
1573  *      v1========v2 = Ok!    v1==V2==v3 == Wrong!
1574  *       |   f2   |           |   f2   |
1575  *       |        |           |        |
1576  *       ----------           ----------
1577  *
1578  *      In the example A, faces f1 and f2 are joined by a single edge, and the euler can safely be used.
1579  *      In example B however, f1 and f2 are joined by multiple edges and will produce an error. The caller
1580  *      in this case should call bmesh_JEKV on the extra edges before attempting to fuse f1 and f2.
1581  *
1582  *      Also note that the order of arguments decides whether or not certain per-face attributes are present
1583  *      in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited
1584  *      from f1, not f2.
1585  *
1586  *  Returns -
1587  *      A BMFace pointer
1588  */
1589 BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e)
1590 {
1591         BMLoop *l_iter, *f1loop = NULL, *f2loop = NULL;
1592         int newlen = 0, i, f1len = 0, f2len = 0, radlen = 0, edok, shared;
1593         BMIter iter;
1594
1595         /* can't join a face to itsel */
1596         if (f1 == f2) {
1597                 return NULL;
1598         }
1599
1600         /* verify that e is in both f1 and f2 */
1601         f1len = f1->len;
1602         f2len = f2->len;
1603         BM_ITER(l_iter, &iter, bm, BM_LOOPS_OF_FACE, f1) {
1604                 if (l_iter->e == e) {
1605                         f1loop = l_iter;
1606                         break;
1607                 }
1608         }
1609         BM_ITER(l_iter, &iter, bm, BM_LOOPS_OF_FACE, f2) {
1610                 if (l_iter->e == e) {
1611                         f2loop = l_iter;
1612                         break;
1613                 }
1614         }
1615         if (!(f1loop && f2loop)) {
1616                 return NULL;
1617         }
1618
1619         /* validate that edge is 2-manifold edg */
1620         radlen = bmesh_radial_length(f1loop);
1621         if (radlen != 2) {
1622                 return NULL;
1623         }
1624
1625         /* validate direction of f2's loop cycle is compatible */
1626         if (f1loop->v == f2loop->v) {
1627                 return NULL;
1628         }
1629
1630         /* validate that for each face, each vertex has another edge in its disk cycle that is
1631          * not e, and not shared. */
1632         if ( bmesh_radial_find_face(f1loop->next->e, f2) ||
1633              bmesh_radial_find_face(f1loop->prev->e, f2) ||
1634              bmesh_radial_find_face(f2loop->next->e, f1) ||
1635              bmesh_radial_find_face(f2loop->prev->e, f1) )
1636         {
1637                 return NULL;
1638         }
1639
1640         /* validate only one shared edg */
1641         shared = BM_face_share_edges(f1, f2);
1642         if (shared > 1) {
1643                 return NULL;
1644         }
1645
1646         /* validate no internal join */
1647         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
1648                 BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG);
1649         }
1650         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
1651                 BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG);
1652         }
1653
1654         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
1655                 if (l_iter != f1loop) {
1656                         BM_elem_flag_enable(l_iter->v, BM_ELEM_TAG);
1657                 }
1658         }
1659         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
1660                 if (l_iter != f2loop) {
1661                         /* as soon as a duplicate is found, bail out */
1662                         if (BM_elem_flag_test(l_iter->v, BM_ELEM_TAG)) {
1663                                 return NULL;
1664                         }
1665                 }
1666         }
1667
1668         /* join the two loop */
1669         f1loop->prev->next = f2loop->next;
1670         f2loop->next->prev = f1loop->prev;
1671
1672         f1loop->next->prev = f2loop->prev;
1673         f2loop->prev->next = f1loop->next;
1674
1675         /* if f1loop was baseloop, make f1loop->next the base. */
1676         if (BM_FACE_FIRST_LOOP(f1) == f1loop)
1677                 BM_FACE_FIRST_LOOP(f1) = f1loop->next;
1678
1679         /* increase length of f1 */
1680         f1->len += (f2->len - 2);
1681
1682         /* make sure each loop points to the proper fac */
1683         newlen = f1->len;
1684         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < newlen; i++, l_iter = l_iter->next)
1685                 l_iter->f = f1;
1686
1687         /* remove edge from the disk cycle of its two vertices */
1688         bmesh_disk_remove_edge(f1loop->e, f1loop->e->v1);
1689         bmesh_disk_remove_edge(f1loop->e, f1loop->e->v2);
1690
1691         /* deallocate edge and its two loops as well as f2 */
1692         BLI_mempool_free(bm->toolflagpool, f1loop->e->oflags);
1693         BLI_mempool_free(bm->epool, f1loop->e);
1694         bm->totedge--;
1695         BLI_mempool_free(bm->lpool, f1loop);
1696         bm->totloop--;
1697         BLI_mempool_free(bm->lpool, f2loop);
1698         bm->totloop--;
1699         BLI_mempool_free(bm->toolflagpool, f2->oflags);
1700         BLI_mempool_free(bm->fpool, f2);
1701         bm->totface--;
1702         /* account for both above */
1703         bm->elem_index_dirty |= BM_EDGE | BM_FACE;
1704
1705         BM_CHECK_ELEMENT(bm, f1);
1706
1707         /* validate the new loop cycle */
1708         edok = bmesh_loop_validate(f1);
1709         if (!edok) bmesh_error();
1710
1711         return f1;
1712 }
1713
1714 /*
1715  * BMESH SPLICE VERT
1716  *
1717  * merges two verts into one (v into vtarget).
1718  */
1719 static int bmesh_splicevert(BMesh *bm, BMVert *v, BMVert *vtarget)
1720 {
1721         BMEdge *e;
1722         BMLoop *l;
1723         BMIter liter;
1724
1725         /* verts already spliced */
1726         if (v == vtarget) {
1727                 return FALSE;
1728         }
1729
1730         /* retarget all the loops of v to vtarget */
1731         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
1732                 l->v = vtarget;
1733         }
1734
1735         /* move all the edges from v's disk to vtarget's disk */
1736         e = v->e;
1737         while (e != NULL) {
1738                 bmesh_disk_remove_edge(e, v);
1739                 bmesh_edge_swapverts(e, v, vtarget);
1740                 bmesh_disk_append_edge(e, vtarget);
1741                 e = v->e;
1742         }
1743
1744         BM_CHECK_ELEMENT(bm, v);
1745         BM_CHECK_ELEMENT(bm, vtarget);
1746
1747         /* v is unused now, and can be killed */
1748         BM_vert_kill(bm, v);
1749
1750         return TRUE;
1751 }
1752
1753 /* BMESH CUT VERT
1754  *
1755  * cut all disjoint fans that meet at a vertex, making a unique
1756  * vertex for each region. returns an array of all resulting
1757  * vertices.
1758  */
1759 static int bmesh_cutvert(BMesh *bm, BMVert *v, BMVert ***vout, int *len)
1760 {
1761         BMEdge **stack = NULL;
1762         BLI_array_declare(stack);
1763         BMVert **verts = NULL;
1764         GHash *visithash;
1765         BMIter eiter, liter;
1766         BMLoop *l;
1767         BMEdge *e;
1768         int i, maxindex;
1769         BMLoop *nl;
1770
1771         visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "bmesh_cutvert visithash");
1772
1773         maxindex = 0;
1774         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
1775                 if (BLI_ghash_haskey(visithash, e)) {
1776                         continue;
1777                 }
1778
1779                 /* Prime the stack with this unvisited edge */
1780                 BLI_array_append(stack, e);
1781
1782                 /* Considering only edges and faces incident on vertex v, walk
1783                  * the edges & faces and assign an index to each connected set */
1784                 while ((e = BLI_array_pop(stack))) {
1785                         BLI_ghash_insert(visithash, e, SET_INT_IN_POINTER(maxindex));
1786
1787                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
1788                                 nl = (l->v == v) ? l->prev : l->next;
1789                                 if (!BLI_ghash_haskey(visithash, nl->e)) {
1790                                         BLI_array_append(stack, nl->e);
1791                                 }
1792                         }
1793                 }
1794
1795                 maxindex++;
1796         }
1797
1798         /* Make enough verts to split v for each group */
1799         verts = MEM_callocN(sizeof(BMVert *) * maxindex, "bmesh_cutvert");
1800         verts[0] = v;
1801         for (i = 1; i < maxindex; i++) {
1802                 verts[i] = BM_vert_create(bm, v->co, v);
1803         }
1804
1805         /* Replace v with the new verts in each group */
1806         BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
1807                 i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, l->e));
1808                 if (i == 0) {
1809                         continue;
1810                 }
1811
1812                 /* Loops here should alway refer to an edge that has v as an
1813                  * endpoint. For each appearance of this vert in a face, there
1814                  * will actually be two iterations: one for the loop heading
1815                  * towards vertex v, and another for the loop heading out from
1816                  * vertex v. Only need to swap the vertex on one of those times,
1817                  * on the outgoing loop. */
1818                 if (l->v == v) {
1819                         l->v = verts[i];
1820                 }
1821         }
1822
1823         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
1824                 i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, e));
1825                 if (i == 0) {
1826                         continue;
1827                 }
1828
1829                 BLI_assert(e->v1 == v || e->v2 == v);
1830                 bmesh_disk_remove_edge(e, v);
1831                 bmesh_edge_swapverts(e, v, verts[i]);
1832                 bmesh_disk_append_edge(e, verts[i]);
1833         }
1834
1835         BLI_ghash_free(visithash, NULL, NULL);
1836         BLI_array_free(stack);
1837
1838         for (i = 0; i < maxindex; i++) {
1839                 BM_CHECK_ELEMENT(bm, verts[i]);
1840         }
1841
1842         if (len != NULL) {
1843                 *len = maxindex;
1844         }
1845
1846         if (vout != NULL) {
1847                 *vout = verts;
1848         }
1849         else {
1850                 MEM_freeN(verts);
1851         }
1852
1853         return TRUE;
1854 }
1855
1856 /* BMESH SPLICE EDGE
1857  *
1858  * splice two unique edges which share the same two vertices into one edge.
1859  *
1860  * edges must already have the same vertices
1861  */
1862 static int UNUSED_FUNCTION(bmesh_spliceedge)(BMesh *bm, BMEdge *e, BMEdge *etarget)
1863 {
1864         BMLoop *l;
1865
1866         if (!BM_vert_in_edge(e, etarget->v1) || !BM_vert_in_edge(e, etarget->v2)) {
1867                 /* not the same vertices can't splice */
1868                 return FALSE;
1869         }
1870
1871         while (e->l) {
1872                 l = e->l;
1873                 BLI_assert(BM_vert_in_edge(etarget, l->v));
1874                 BLI_assert(BM_vert_in_edge(etarget, l->next->v));
1875                 bmesh_radial_remove_loop(l, e);
1876                 bmesh_radial_append(etarget, l);
1877         }
1878
1879         BLI_assert(bmesh_radial_length(e->l) == 0);
1880
1881         BM_CHECK_ELEMENT(bm, e);
1882         BM_CHECK_ELEMENT(bm, etarget);
1883
1884         BM_edge_kill(bm, e);
1885
1886         return TRUE;
1887 }
1888
1889 /*
1890  * BMESH CUT EDGE
1891  *
1892  * Cuts a single edge into two edge: the original edge and
1893  * a new edge that has only "cutl" in its radial.
1894  *
1895  * Does nothing if cutl is already the only loop in the
1896  * edge radial.
1897  */
1898 static int bmesh_cutedge(BMesh *bm, BMEdge *e, BMLoop *cutl)
1899 {
1900         BMEdge *ne;
1901         int radlen;
1902
1903         BLI_assert(cutl->e == e);
1904         BLI_assert(e->l);
1905
1906         radlen = bmesh_radial_length(e->l);
1907         if (radlen < 2) {
1908                 /* no cut required */
1909                 return TRUE;
1910         }
1911
1912         if (cutl == e->l) {
1913                 e->l = cutl->radial_next;
1914         }
1915
1916         ne = BM_edge_create(bm, e->v1, e->v2, e, FALSE);
1917         bmesh_radial_remove_loop(cutl, e);
1918         bmesh_radial_append(ne, cutl);
1919         cutl->e = ne;
1920
1921         BLI_assert(bmesh_radial_length(e->l) == radlen - 1);
1922         BLI_assert(bmesh_radial_length(ne->l) == 1);
1923
1924         BM_CHECK_ELEMENT(bm, ne);
1925         BM_CHECK_ELEMENT(bm, e);
1926
1927         return TRUE;
1928 }
1929
1930 /*
1931  * BMESH UNGLUE REGION MAKE VERT
1932  *
1933  * Disconnects a face from its vertex fan at loop sl.
1934  */
1935 static BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *sl)
1936 {
1937         BMVert **vtar;
1938         int len, i;
1939         BMVert *nv = NULL;
1940         BMVert *sv = sl->v;
1941
1942         /* peel the face from the edge radials on both sides of the
1943          * loop vert, disconnecting the face from its fan */
1944         bmesh_cutedge(bm, sl->e, sl);
1945         bmesh_cutedge(bm, sl->prev->e, sl->prev);
1946
1947         if (bmesh_disk_count(sv) == 2) {
1948                 /* If there are still only two edges out of sv, then
1949                  * this whole URMV was just a no-op, so exit now. */
1950                 return sv;
1951         }
1952
1953         /* Update the disk start, so that v->e points to an edge
1954          * not touching the split loop. This is so that bmesh_cutvert
1955          * will leave the original sv on some *other* fan (not the
1956          * one-face fan that holds the unglue face). */
1957         while (sv->e == sl->e || sv->e == sl->prev->e) {
1958                 sv->e = bmesh_disk_nextedge(sv->e, sv);
1959         }
1960
1961         /* Split all fans connected to the vert, duplicating it for
1962          * each fans. */
1963         bmesh_cutvert(bm, sv, &vtar, &len);
1964
1965         /* There should have been at least two fans cut apart here,
1966          * otherwise the early exit would have kicked in. */
1967         BLI_assert(len >= 2);
1968
1969         nv = sl->v;
1970
1971         /* Desired result here is that a new vert should always be
1972          * created for the unglue face. This is so we can glue any
1973          * extras back into the original vert. */
1974         BLI_assert(nv != sv);
1975         BLI_assert(sv == vtar[0]);
1976
1977         /* If there are more than two verts as a result, glue together
1978          * all the verts except the one this URMV intended to create */
1979         if (len > 2) {
1980                 for (i = 0; i < len; i++) {
1981                         if (vtar[i] == nv) {
1982                                 break;
1983                         }
1984                 }
1985
1986                 if (i != len) {
1987                         /* Swap the single vert that was needed for the
1988                          * unglue into the last array slot */
1989                         SWAP(BMVert *, vtar[i], vtar[len - 1]);
1990
1991                         /* And then glue the rest back together */
1992                         for (i = 1; i < len - 1; i++) {
1993                                 bmesh_splicevert(bm, vtar[i], vtar[0]);
1994                         }
1995                 }
1996         }
1997
1998         MEM_freeN(vtar);
1999
2000         return nv;
2001 }
2002
2003 /*
2004  * BMESH UNGLUE REGION MAKE VERT
2005  *
2006  * Disconnects sf from the vertex fan at sv
2007  */
2008 BMVert *bmesh_urmv(BMesh *bm, BMFace *sf, BMVert *sv)
2009 {
2010         BMLoop *l_first;
2011         BMLoop *l_iter;
2012
2013         l_iter = l_first = BM_FACE_FIRST_LOOP(sf);
2014         do {
2015                 if (l_iter->v == sv) {
2016                         break;
2017                 }
2018         } while ((l_iter = l_iter->next) != l_first);
2019
2020         if (l_iter->v != sv) {
2021                 /* sv is not part of sf */
2022                 return NULL;
2023         }
2024
2025         return bmesh_urmv_loop(bm, l_iter);
2026 }