source/blender/blenkernel/intern/BME_eulers.c

   1 /*
   2  * BME_eulers.c    jan 2007
   3  *
   4  *      BMesh Euler construction API.
   5  *
   6  *
   7  * ***** BEGIN GPL LICENSE BLOCK *****
   8  *
   9  * This program is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU General Public License
  11  * as published by the Free Software Foundation; either version 2
  12  * of the License, or (at your option) any later version.
  13  * about this.
  14  *
  15  * This program is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; if not, write to the Free Software Foundation,
  22  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  23  *
  24  * The Original Code is Copyright (C) 2004 Blender Foundation.
  25  * All rights reserved.
  26  *
  27  * The Original Code is: all of this file.
  28  *
  29  * Contributor(s): Geoffrey Bantle.
  30  *
  31  * ***** END GPL LICENSE BLOCK *****
  32  */
  33
  34 /** \file blender/blenkernel/intern/BME_eulers.c
  35  *  \ingroup bke
  36  */
  37
  38
  39 #include "MEM_guardedalloc.h"
  40 #include "BLI_listbase.h"
  41 #include "BLI_utildefines.h"
  42
  43 #include "bmesh_private.h"
  44
  45 /*********************************************************
  46  *                    "Euler API"                        *
  47  *                                                       *
  48  *                                                       *
  49  *       Primitive construction operators for mesh tools.    *
  50  *                                                       *
  51  **********************************************************/
  52
  53
  54 /*
  55         The functions in this file represent the 'primitive' or 'atomic' operators that
  56         mesh tools use to manipulate the topology of the structure.* The purpose of these
  57         functions is to provide a trusted set of operators to manipulate the mesh topology
  58         and which can also be combined together like building blocks to create more
  59         sophisticated tools. It needs to be stressed that NO manipulation of an existing
  60         mesh structure should be done outside of these functions.
  61
  62         In the BMesh system, each euler is named by an ancronym which describes what it actually does.
  63         Furthermore each Euler has a logical inverse. An important design criteria of all Eulers is that
  64         through a Euler's logical inverse you can 'undo' an operation. (Special note should
  65         be taken of BME_loop_reverse, which is its own inverse).
  66
  67         BME_MF/KF: Make Face and Kill Face
  68         BME_ME/KE: Make Edge and Kill Edge
  69         BME_MV/KV: Make Vert and Kill Vert
  70         BME_SEMV/JEKV: Split Edge, Make Vert and Join Edge, Kill Vert
  71         BME_SFME/JFKE: Split Face, Make Edge and Join Face, Kill Edge
  72         BME_loop_reverse: Reverse a Polygon's loop cycle. (used for flip normals for one)
  73
  74         Using a combination of these eleven eulers any non-manifold modelling operation can be achieved.
  75         Each Euler operator has a detailed explanation of what is does in the comments preceding its
  76         code.
  77
  78    *The term "Euler Operator" is actually a misnomer when referring to a non-manifold
  79         data structure. Its use is in keeping with the convention established by others.
  80
  81         TODO:
  82         -Finish inserting 'strict' validation in all Eulers
  83 */
  84
  85 void *BME_exit(char *s) {
  86         if (s) printf("%s\n",s);
  87         return NULL;
  88 }
  89
  90 #define RETCLEAR(bm) {bm->rval->v = bm->rval->e = bm->rval->f = bm->rva->l = NULL;}
  91 /*MAKE Eulers*/
  92
  93 /**
  94  *                      BME_MV
  95  *
  96  *      MAKE VERT EULER:
  97  *
  98  *      Makes a single loose vertex.
  99  *
 100  *      Returns -
 101  *      A BME_Vert pointer.
 102  */
 103
 104 BME_Vert *BME_MV(BME_Mesh *bm, float *vec){
 105         BME_Vert *v = BME_addvertlist(bm, NULL);
 106         VECCOPY(v->co,vec);
 107         return v;
 108 }
 109
 110 /**
 111  *                      BME_ME
 112  *
 113  *      MAKE EDGE EULER:
 114  *
 115  *      Makes a single wire edge between two vertices.
 116  *      If the caller does not want there to be duplicate
 117  *      edges between the vertices, it is up to them to check
 118  *      for this condition beforehand.
 119  *
 120  *      Returns -
 121  *      A BME_Edge pointer.
 122  */
 123
 124 BME_Edge *BME_ME(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2){
 125         BME_Edge *e=NULL;
 126         BME_CycleNode *d1=NULL, *d2=NULL;
 127         int valance1=0, valance2=0, edok;
 128
 129         /*edge must be between two distinct vertices...*/
 130         if(v1 == v2) return NULL;
 131
 132         #ifndef BME_FASTEULER
 133         /*count valance of v1*/
 134         if(v1->edge){
 135                 d1 = BME_disk_getpointer(v1->edge,v1);
 136                 if(d1) valance1 = BME_cycle_length(d1);
 137                 else BME_error();
 138         }
 139         if(v2->edge){
 140                 d2 = BME_disk_getpointer(v2->edge,v2);
 141                 if(d2) valance2 = BME_cycle_length(d2);
 142                 else BME_error();
 143         }
 144         #endif
 145
 146         /*go ahead and add*/
 147         e = BME_addedgelist(bm, v1, v2, NULL);
 148         BME_disk_append_edge(e, e->v1);
 149         BME_disk_append_edge(e, e->v2);
 150
 151         #ifndef BME_FASTEULER
 152         /*verify disk cycle lengths*/
 153         d1 = BME_disk_getpointer(e, e->v1);
 154         edok = BME_cycle_validate(valance1+1, d1);
 155         if(!edok) BME_error();
 156         d2 = BME_disk_getpointer(e, e->v2);
 157         edok = BME_cycle_validate(valance2+1, d2);
 158         if(!edok) BME_error();
 159
 160         /*verify that edge actually made it into the cycle*/
 161         edok = BME_disk_hasedge(v1, e);
 162         if(!edok) BME_error();
 163         edok = BME_disk_hasedge(v2, e);
 164         if(!edok) BME_error();
 165         #endif
 166         return e;
 167 }
 168
 169
 170
 171 /**
 172  *                      BME_MF
 173  *
 174  *      MAKE FACE EULER:
 175  *      Takes a list of edge pointers which form a closed loop and makes a face
 176  *  from them. The first edge in elist is considered to be the start of the
 177  *      polygon, and v1 and v2 are its vertices and determine the winding of the face
 178  *  Other than the first edge, no other assumptions are made about the order of edges
 179  *  in the elist array. To verify that it is a single closed loop and derive the correct
 180  *  order a simple series of verifications is done and all elements are visited.
 181  *
 182  *  Returns -
 183  *      A BME_Poly pointer
 184  */
 185
 186 #define MF_CANDIDATE    1
 187 #define MF_VISITED              2
 188 #define MF_TAKEN                4
 189
 190 BME_Poly *BME_MF(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge **elist, int len)
 191 {
 192         BME_Poly *f = NULL;
 193         BME_Edge *curedge;
 194         BME_Vert *curvert, *tv, **vlist;
 195         int i, j, done, cont, edok;
 196
 197         if(len < 2) return NULL;
 198
 199         /*make sure that v1 and v2 are in elist[0]*/
 200         if(BME_verts_in_edge(v1,v2,elist[0]) == 0) return NULL;
 201
 202         /*clear euler flags*/
 203         for(i=0;i<len;i++) elist[i]->eflag1=elist[i]->eflag2 = 0;
 204         for(i=0;i<len;i++){
 205                 elist[i]->eflag1 |= MF_CANDIDATE;
 206
 207                 /*if elist[i] has a loop, count its radial length*/
 208                 if(elist[i]->loop) elist[i]->eflag2 = BME_cycle_length(&(elist[i]->loop->radial));
 209                 else elist[i]->eflag2 = 0;
 210         }
 211
 212         /*      For each vertex in each edge, it must have exactly two MF_CANDIDATE edges attached to it
 213                 Note that this does not gauruntee that face is a single closed loop. At best it gauruntees
 214                 that elist contains a finite number of seperate closed loops.
 215         */
 216         for(i=0; i<len; i++){
 217                 edok = BME_disk_count_edgeflag(elist[i]->v1, MF_CANDIDATE, 0);
 218                 if(edok != 2) return NULL;
 219                 edok = BME_disk_count_edgeflag(elist[i]->v2, MF_CANDIDATE, 0);
 220                 if(edok != 2) return NULL;
 221         }
 222
 223         /*set start edge, start vert and target vert for our loop traversal*/
 224         curedge = elist[0];
 225         tv = v1;
 226         curvert = v2;
 227
 228         if(bm->vtarlen < len){
 229                 MEM_freeN(bm->vtar);
 230                 bm->vtar = MEM_callocN(sizeof(BME_Vert *)* len, "BMesh Vert pointer array");
 231                 bm->vtarlen = len;
 232         }
 233         /*insert tv into vlist since its the first vertex in face*/
 234         i=0;
 235         vlist=bm->vtar;
 236         vlist[i] = tv;
 237
 238         /*      Basic procedure: Starting with curv we find the edge in it's disk cycle which hasn't
 239                 been visited yet. When we do, we put curv in a linked list and find the next MF_CANDIDATE
 240                 edge, loop until we find TV. We know TV is reachable because of test we did earlier.
 241         */
 242         done=0;
 243         while(!done){
 244                 /*add curvert to vlist*/
 245                 /*insert some error cheking here for overflows*/
 246                 i++;
 247                 vlist[i] = curvert;
 248
 249                 /*mark curedge as visited*/
 250                 curedge->eflag1 |= MF_VISITED;
 251
 252                 /*find next edge and vert*/
 253                 curedge = BME_disk_next_edgeflag(curedge, curvert, MF_CANDIDATE, 0);
 254                 curvert = BME_edge_getothervert(curedge, curvert);
 255                 if(curvert == tv){
 256                         curedge->eflag1 |= MF_VISITED;
 257                         done=1;
 258                 }
 259         }
 260
 261         /*      Verify that all edges have been visited It's possible that we did reach tv
 262                 from sv, but that several unconnected loops were passed in via elist.
 263         */
 264         cont=1;
 265         for(i=0; i<len; i++){
 266                 if((elist[i]->eflag1 & MF_VISITED) == 0) cont = 0;
 267         }
 268
 269         /*if we get this far, its ok to allocate the face and add the loops*/
 270         if(cont){
 271                 BME_Loop *l;
 272                 BME_Edge *e;
 273                 f = BME_addpolylist(bm, NULL);
 274                 f->len = len;
 275                 for(i=0;i<len;i++){
 276                         curvert = vlist[i];
 277                         l = BME_create_loop(bm,curvert,NULL,f,NULL);
 278                         if(!(f->loopbase)) f->loopbase = l;
 279                         BME_cycle_append(f->loopbase, l);
 280                 }
 281
 282                 /*take care of edge pointers and radial cycle*/
 283                 for(i=0, l = f->loopbase; i<len; i++, l=l->next){
 284                         e = NULL;
 285                         if(l == f->loopbase) e = elist[0]; /*first edge*/
 286
 287                         else{/*search elist for others*/
 288                                 for(j=1; j<len; j++){
 289                                         edok = BME_verts_in_edge(l->v, l->next->v, elist[j]);
 290                                         if(edok){
 291                                                 e = elist[j];
 292                                                 break;
 293                                         }
 294                                 }
 295                         }
 296                         l->e = e; /*set pointer*/
 297                         BME_radial_append(e, l); /*append into radial*/
 298                 }
 299
 300                 f->len = len;
 301
 302                 /*Validation Loop cycle*/
 303                 edok = BME_cycle_validate(len, f->loopbase);
 304                 if(!edok) BME_error();
 305                 for(i=0, l = f->loopbase; i<len; i++, l=l->next){
 306                         /*validate loop vert pointers*/
 307                         edok = BME_verts_in_edge(l->v, l->next->v, l->e);
 308                         if(!edok) BME_error();
 309                         /*validate the radial cycle of each edge*/
 310                         edok = BME_cycle_length(&(l->radial));
 311                         if(edok != (l->e->eflag2 + 1)) BME_error();
 312                 }
 313         }
 314         return f;
 315 }
 316
 317 /* KILL Eulers */
 318
 319 /**
 320  *                      BME_KV
 321  *
 322  *      KILL VERT EULER:
 323  *
 324  *      Kills a single loose vertex.
 325  *
 326  *      Returns -
 327  *      1 for success, 0 for failure.
 328  */
 329
 330 int BME_KV(BME_Mesh *bm, BME_Vert *v){
 331         if(v->edge == NULL){
 332                 BLI_remlink(&(bm->verts), v);
 333                 BME_free_vert(bm,v);
 334                 return 1;
 335         }
 336         return 0;
 337 }
 338
 339 /**
 340  *                      BME_KE
 341  *
 342  *      KILL EDGE EULER:
 343  *
 344  *      Kills a wire edge.
 345  *
 346  *      Returns -
 347  *      1 for success, 0 for failure.
 348  */
 349
 350 int BME_KE(BME_Mesh *bm, BME_Edge *e){
 351         int edok;
 352
 353         /*Make sure that no faces!*/
 354         if(e->loop == NULL){
 355                 BME_disk_remove_edge(e, e->v1);
 356                 BME_disk_remove_edge(e, e->v2);
 357
 358                 /*verify that edge out of disk*/
 359                 edok = BME_disk_hasedge(e->v1, e);
 360                 if(edok) BME_error();
 361                 edok = BME_disk_hasedge(e->v2, e);
 362                 if(edok) BME_error();
 363
 364                 /*remove and deallocate*/
 365                 BLI_remlink(&(bm->edges), e);
 366                 BME_free_edge(bm, e);
 367                 return 1;
 368         }
 369         return 0;
 370 }
 371
 372 /**
 373  *                      BME_KF
 374  *
 375  *      KILL FACE EULER:
 376  *
 377  *      The logical inverse of BME_MF.
 378  *      Kills a face and removes each of its loops from the radial that it belongs to.
 379  *
 380  *  Returns -
 381  *      1 for success, 0 for failure.
 382 */
 383
 384 int BME_KF(BME_Mesh *bm, BME_Poly *bply){
 385         BME_Loop *newbase,*oldbase, *curloop;
 386         int i,len=0;
 387
 388         /*add validation to make sure that radial cycle is cleaned up ok*/
 389         /*deal with radial cycle first*/
 390         len = BME_cycle_length(bply->loopbase);
 391         for(i=0, curloop=bply->loopbase; i < len; i++, curloop = curloop->next)
 392                 BME_radial_remove_loop(curloop, curloop->e);
 393
 394         /*now deallocate the editloops*/
 395         for(i=0; i < len; i++){
 396                 newbase = bply->loopbase->next;
 397                 oldbase = bply->loopbase;
 398                 BME_cycle_remove(oldbase, oldbase);
 399                 BME_free_loop(bm, oldbase);
 400                 bply->loopbase = newbase;
 401         }
 402
 403         BLI_remlink(&(bm->polys), bply);
 404         BME_free_poly(bm, bply);
 405         return 1;
 406 }
 407
 408 /*SPLIT Eulers*/
 409
 410 /**
 411  *                      BME_SEMV
 412  *
 413  *      SPLIT EDGE MAKE VERT:
 414  *      Takes a given edge and splits it into two, creating a new vert.
 415  *
 416  *
 417  *              Before: OV---------TV
 418  *              After:  OV----NV---TV
 419  *
 420  *  Returns -
 421  *      BME_Vert pointer.
 422  *
 423 */
 424
 425 BME_Vert *BME_SEMV(BME_Mesh *bm, BME_Vert *tv, BME_Edge *e, BME_Edge **re){
 426         BME_Vert *nv, *ov;
 427         BME_CycleNode *diskbase;
 428         BME_Edge *ne;
 429         int i, edok, valance1=0, valance2=0;
 430
 431         if(BME_vert_in_edge(e,tv) == 0) return NULL;
 432         ov = BME_edge_getothervert(e,tv);
 433         //v2 = tv;
 434
 435         /*count valance of v1*/
 436         diskbase = BME_disk_getpointer(e, ov);
 437         valance1 = BME_cycle_length(diskbase);
 438         /*count valance of v2*/
 439         diskbase = BME_disk_getpointer(e, tv);
 440         valance2 = BME_cycle_length(diskbase);
 441
 442         nv = BME_addvertlist(bm, tv);
 443         ne = BME_addedgelist(bm, nv, tv, e);
 444
 445         //e->v2 = nv;
 446         /*remove e from v2's disk cycle*/
 447         BME_disk_remove_edge(e, tv);
 448         /*swap out tv for nv in e*/
 449         BME_edge_swapverts(e, tv, nv);
 450         /*add e to nv's disk cycle*/
 451         BME_disk_append_edge(e, nv);
 452         /*add ne to nv's disk cycle*/
 453         BME_disk_append_edge(ne, nv);
 454         /*add ne to tv's disk cycle*/
 455         BME_disk_append_edge(ne, tv);
 456         /*verify disk cycles*/
 457         diskbase = BME_disk_getpointer(ov->edge,ov);
 458         edok = BME_cycle_validate(valance1, diskbase);
 459         if(!edok) BME_error();
 460         diskbase = BME_disk_getpointer(tv->edge,tv);
 461         edok = BME_cycle_validate(valance2, diskbase);
 462         if(!edok) BME_error();
 463         diskbase = BME_disk_getpointer(nv->edge,nv);
 464         edok = BME_cycle_validate(2, diskbase);
 465         if(!edok) BME_error();
 466
 467         /*Split the radial cycle if present*/
 468         if(e->loop){
 469                 BME_Loop *nl,*l;
 470                 BME_CycleNode *radEBase=NULL, *radNEBase=NULL;
 471                 int radlen = BME_cycle_length(&(e->loop->radial));
 472                 /*Take the next loop. Remove it from radial. Split it. Append to appropriate radials.*/
 473                 while(e->loop){
 474                         l=e->loop;
 475                         l->f->len++;
 476                         BME_radial_remove_loop(l,e);
 477
 478                         nl = BME_create_loop(bm,NULL,NULL,l->f,l);
 479                         nl->prev = l;
 480                         nl->next = l->next;
 481                         nl->prev->next = nl;
 482                         nl->next->prev = nl;
 483                         nl->v = nv;
 484
 485                         /*assign the correct edge to the correct loop*/
 486                         if(BME_verts_in_edge(nl->v, nl->next->v, e)){
 487                                 nl->e = e;
 488                                 l->e = ne;
 489
 490                                 /*append l into ne's rad cycle*/
 491                                 if(!radNEBase){
 492                                         radNEBase = &(l->radial);
 493                                         radNEBase->next = NULL;
 494                                         radNEBase->prev = NULL;
 495                                 }
 496
 497                                 if(!radEBase){
 498                                         radEBase = &(nl->radial);
 499                                         radEBase->next = NULL;
 500                                         radEBase->prev = NULL;
 501                                 }
 502
 503                                 BME_cycle_append(radEBase,&(nl->radial));
 504                                 BME_cycle_append(radNEBase,&(l->radial));
 505
 506                         }
 507                         else if(BME_verts_in_edge(nl->v,nl->next->v,ne)){
 508                                 nl->e = ne;
 509                                 l->e = e;
 510
 511                                 if(!radNEBase){
 512                                         radNEBase = &(nl->radial);
 513                                         radNEBase->next = NULL;
 514                                         radNEBase->prev = NULL;
 515                                 }
 516                                 if(!radEBase){
 517                                         radEBase = &(l->radial);
 518                                         radEBase->next = NULL;
 519                                         radEBase->prev = NULL;
 520                                 }
 521                                 BME_cycle_append(radEBase,&(l->radial));
 522                                 BME_cycle_append(radNEBase,&(nl->radial));
 523                         }
 524
 525                 }
 526
 527                 e->loop = radEBase->data;
 528                 ne->loop = radNEBase->data;
 529
 530                 /*verify length of radial cycle*/
 531                 edok = BME_cycle_validate(radlen,&(e->loop->radial));
 532                 if(!edok) BME_error();
 533                 edok = BME_cycle_validate(radlen,&(ne->loop->radial));
 534                 if(!edok) BME_error();
 535
 536                 /*verify loop->v and loop->next->v pointers for e*/
 537                 for(i=0,l=e->loop; i < radlen; i++, l = l->radial.next->data){
 538                         if(!(l->e == e)) BME_error();
 539                         if(!(l->radial.data == l)) BME_error();
 540                         if(l->prev->e != ne && l->next->e != ne) BME_error();
 541                         edok = BME_verts_in_edge(l->v, l->next->v, e);
 542                         if(!edok) BME_error();
 543                         if(l->v == l->next->v) BME_error();
 544                         if(l->e == l->next->e) BME_error();
 545                         /*verify loop cycle for kloop->f*/
 546                         edok = BME_cycle_validate(l->f->len, l->f->loopbase);
 547                         if(!edok) BME_error();
 548                 }
 549                 /*verify loop->v and loop->next->v pointers for ne*/
 550                 for(i=0,l=ne->loop; i < radlen; i++, l = l->radial.next->data){
 551                         if(!(l->e == ne)) BME_error();
 552                         if(!(l->radial.data == l)) BME_error();
 553                         if(l->prev->e != e && l->next->e != e) BME_error();
 554                         edok = BME_verts_in_edge(l->v, l->next->v, ne);
 555                         if(!edok) BME_error();
 556                         if(l->v == l->next->v) BME_error();
 557                         if(l->e == l->next->e) BME_error();
 558                         /*verify loop cycle for kloop->f. Redundant*/
 559                         edok = BME_cycle_validate(l->f->len, l->f->loopbase);
 560                         if(!edok) BME_error();
 561                 }
 562         }
 563
 564         if(re) *re = ne;
 565         return nv;
 566 }
 567
 568 /**
 569  *                      BME_SFME
 570  *
 571  *      SPLIT FACE MAKE EDGE:
 572  *
 573  *      Takes as input two vertices in a single face. An edge is created which divides the original face
 574  *      into two distinct regions. One of the regions is assigned to the original face and it is closed off.
 575  *      The second region has a new face assigned to it.
 576  *
 577  *      Examples:
 578  *
 579  *     Before:               After:
 580  *       ----------           ----------
 581  *       |                |           |        |
 582  *       |        |           |   f1   |
 583  *      v1   f1   v2          v1======v2
 584  *       |        |           |   f2   |
 585  *       |        |           |        |
 586  *       ----------           ----------
 587  *
 588  *      Note that the input vertices can be part of the same edge. This will result in a two edged face.
 589  *  This is desirable for advanced construction tools and particularly essential for edge bevel. Because
 590  *  of this it is up to the caller to decide what to do with the extra edge.
 591  *
 592  *      Returns -
 593  *  A BME_Poly pointer
 594  */
 595 BME_Poly *BME_SFME(BME_Mesh *bm, BME_Poly *f, BME_Vert *v1, BME_Vert *v2, BME_Loop **rl){
 596
 597         BME_Poly *f2;
 598         BME_Loop *v1loop = NULL, *v2loop = NULL, *curloop, *f1loop=NULL, *f2loop=NULL;
 599         BME_Edge *e;
 600         int i, len, f1len, f2len;
 601
 602
 603         /*verify that v1 and v2 are in face.*/
 604         len = BME_cycle_length(f->loopbase);
 605         for(i = 0, curloop = f->loopbase; i < len; i++, curloop = curloop->next){
 606                 if(curloop->v == v1) v1loop = curloop;
 607                 else if(curloop->v == v2) v2loop = curloop;
 608         }
 609
 610         if(!v1loop || !v2loop) return NULL;
 611
 612         /*allocate new edge between v1 and v2*/
 613         e = BME_addedgelist(bm, v1, v2,NULL);
 614         BME_disk_append_edge(e, v1);
 615         BME_disk_append_edge(e, v2);
 616
 617         f2 = BME_addpolylist(bm,f);
 618         f1loop = BME_create_loop(bm,v2,e,f,v2loop);
 619         f2loop = BME_create_loop(bm,v1,e,f2,v1loop);
 620
 621         f1loop->prev = v2loop->prev;
 622         f2loop->prev = v1loop->prev;
 623         v2loop->prev->next = f1loop;
 624         v1loop->prev->next = f2loop;
 625
 626         f1loop->next = v1loop;
 627         f2loop->next = v2loop;
 628         v1loop->prev = f1loop;
 629         v2loop->prev = f2loop;
 630
 631         f2->loopbase = f2loop;
 632         f->loopbase = f1loop;
 633
 634         /*validate both loops*/
 635         /*I dont know how many loops are supposed to be in each face at this point! FIXME!*/
 636
 637         /*go through all of f2's loops and make sure they point to it properly.*/
 638         f2len = BME_cycle_length(f2->loopbase);
 639         for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = curloop->next) curloop->f = f2;
 640
 641         /*link up the new loops into the new edges radial*/
 642         BME_radial_append(e, f1loop);
 643         BME_radial_append(e, f2loop);
 644
 645
 646         f2->len = f2len;
 647
 648         f1len = BME_cycle_length(f->loopbase);
 649         f->len = f1len;
 650
 651         if(rl) *rl = f2loop;
 652         return f2;
 653 }
 654
 655
 656 /**
 657  *                      BME_JEKV
 658  *
 659  *      JOIN EDGE KILL VERT:
 660  *      Takes a an edge and pointer to one of its vertices and collapses
 661  *      the edge on that vertex.
 662  *
 663  *      Before:    OE      KE
 664  *               ------- -------
 665  *               |     ||      |
 666  *              OV     KV      TV
 667  *
 668  *
 669  *   After:             OE
 670  *               ---------------
 671  *               |             |
 672  *              OV             TV
 673  *
 674  *
 675  *      Restrictions:
 676  *      KV is a vertex that must have a valance of exactly two. Furthermore
 677  *  both edges in KV's disk cycle (OE and KE) must be unique (no double
 678  *  edges).
 679  *
 680  *      It should also be noted that this euler has the possibility of creating
 681  *      faces with just 2 edges. It is up to the caller to decide what to do with
 682  *  these faces.
 683  *
 684  *  Returns -
 685  *      1 for success, 0 for failure.
 686  */
 687 int BME_JEKV(BME_Mesh *bm, BME_Edge *ke, BME_Vert *kv)
 688 {
 689         BME_Edge *oe;
 690         BME_Vert *ov, *tv;
 691         BME_CycleNode *diskbase;
 692         BME_Loop *killoop,*nextl;
 693         int len,radlen=0, halt = 0, i, valance1, valance2,edok;
 694
 695         if(BME_vert_in_edge(ke,kv) == 0) return 0;
 696         diskbase = BME_disk_getpointer(kv->edge, kv);
 697         len = BME_cycle_length(diskbase);
 698
 699         if(len == 2){
 700                 oe = BME_disk_nextedge(ke, kv);
 701                 tv = BME_edge_getothervert(ke, kv);
 702                 ov = BME_edge_getothervert(oe, kv);
 703                 halt = BME_verts_in_edge(kv, tv, oe); //check for double edges
 704
 705                 if(halt) return 0;
 706                 else{
 707
 708                         /*For verification later, count valance of ov and tv*/
 709                         diskbase = BME_disk_getpointer(ov->edge, ov);
 710                         valance1 = BME_cycle_length(diskbase);
 711                         diskbase = BME_disk_getpointer(tv->edge, tv);
 712                         valance2 = BME_cycle_length(diskbase);
 713
 714                         /*remove oe from kv's disk cycle*/
 715                         BME_disk_remove_edge(oe,kv);
 716                         /*relink oe->kv to be oe->tv*/
 717                         BME_edge_swapverts(oe, kv, tv);
 718                         /*append oe to tv's disk cycle*/
 719                         BME_disk_append_edge(oe, tv);
 720                         /*remove ke from tv's disk cycle*/
 721                         BME_disk_remove_edge(ke, tv);
 722
 723
 724
 725                         /*deal with radial cycle of ke*/
 726                         if(ke->loop){
 727                                 /*first step, fix the neighboring loops of all loops in ke's radial cycle*/
 728                                 radlen = BME_cycle_length(&(ke->loop->radial));
 729                                 for(i=0,killoop = ke->loop; i<radlen; i++, killoop = BME_radial_nextloop(killoop)){
 730                                         /*relink loops and fix vertex pointer*/
 731                                         killoop->next->prev = killoop->prev;
 732                                         killoop->prev->next = killoop->next;
 733                                         if(killoop->next->v == kv) killoop->next->v = tv;
 734
 735                                         /*fix len attribute of face*/
 736                                         killoop->f->len--;
 737                                         if(killoop->f->loopbase == killoop) killoop->f->loopbase = killoop->next;
 738                                 }
 739                                 /*second step, remove all the hanging loops attached to ke*/
 740                                 killoop = ke->loop;
 741                                 radlen = BME_cycle_length(&(ke->loop->radial));
 742                                 /*make sure we have enough room in bm->lpar*/
 743                                 if(bm->lparlen < radlen){
 744                                         MEM_freeN(bm->lpar);
 745                                         bm->lpar = MEM_callocN(sizeof(BME_Loop *)* radlen, "BMesh Loop pointer array");
 746                                         bm->lparlen = bm->lparlen * radlen;
 747                                 }
 748                                 /*this should be wrapped into a bme_free_radial function to be used by BME_KF as well...*/
 749                                 i=0;
 750                                 while(i<radlen){
 751                                         bm->lpar[i] = killoop;
 752                                         killoop = killoop->radial.next->data;
 753                                         i++;
 754                                 }
 755                                 i=0;
 756                                 while(i<radlen){
 757                                         BME_free_loop(bm,bm->lpar[i]);
 758                                         i++;
 759                                 }
 760                                 /*Validate radial cycle of oe*/
 761                                 edok = BME_cycle_validate(radlen,&(oe->loop->radial));
 762
 763                         }
 764
 765
 766                         /*Validate disk cycles*/
 767                         diskbase = BME_disk_getpointer(ov->edge,ov);
 768                         edok = BME_cycle_validate(valance1, diskbase);
 769                         if(!edok) BME_error();
 770                         diskbase = BME_disk_getpointer(tv->edge,tv);
 771                         edok = BME_cycle_validate(valance2, diskbase);
 772                         if(!edok) BME_error();
 773
 774                         /*Validate loop cycle of all faces attached to oe*/
 775                         for(i=0,nextl = oe->loop; i<radlen; i++, nextl = BME_radial_nextloop(nextl)){
 776                                 edok = BME_cycle_validate(nextl->f->len,nextl->f->loopbase);
 777                                 if(!edok) BME_error();
 778                         }
 779                         /*deallocate edge*/
 780                         BLI_remlink(&(bm->edges), ke);
 781                         BME_free_edge(bm, ke);
 782                         /*deallocate vertex*/
 783                         BLI_remlink(&(bm->verts), kv);
 784                         BME_free_vert(bm, kv);
 785                         return 1;
 786                 }
 787         }
 788         return 0;
 789 }
 790
 791
 792 /**
 793  *                      BME_loop_reverse
 794  *
 795  *      FLIP FACE EULER
 796  *
 797  *      Changes the winding order of a face from CW to CCW or vice versa.
 798  *      This euler is a bit peculiar in compairson to others as it is its
 799  *      own inverse.
 800  *
 801  *      TODO: reinsert validation code.
 802  *
 803  *  Returns -
 804  *      1 for success, 0 for failure.
 805  */
 806
 807 int BME_loop_reverse(BME_Mesh *bm, BME_Poly *f){
 808         BME_Loop *l = f->loopbase, *curloop, *oldprev, *oldnext;
 809         int i, j, edok, len = 0;
 810
 811         len = BME_cycle_length(l);
 812         if(bm->edarlen < len){
 813                 MEM_freeN(bm->edar);
 814                 bm->edar = MEM_callocN(sizeof(BME_Edge *)* len, "BMesh Edge pointer array");
 815                 bm->edarlen = len;
 816         }
 817
 818         for(i=0, curloop = l; i< len; i++, curloop=curloop->next){
 819                 curloop->e->eflag1 = 0;
 820                 curloop->e->eflag2 = BME_cycle_length(&curloop->radial);
 821                 BME_radial_remove_loop(curloop, curloop->e);
 822                 /*in case of border edges we HAVE to zero out curloop->radial Next/Prev*/
 823                 curloop->radial.next = curloop->radial.prev = NULL;
 824                 bm->edar[i] = curloop->e;
 825         }
 826
 827         /*actually reverse the loop. This belongs in BME_cycle_reverse!*/
 828         for(i=0, curloop = l; i < len; i++){
 829                 oldnext = curloop->next;
 830                 oldprev = curloop->prev;
 831                 curloop->next = oldprev;
 832                 curloop->prev = oldnext;
 833                 curloop = oldnext;
 834         }
 835
 836         if(len == 2){ //two edged face
 837                 //do some verification here!
 838                 l->e = bm->edar[1];
 839                 l->next->e = bm->edar[0];
 840         }
 841         else{
 842                 for(i=0, curloop = l; i < len; i++, curloop = curloop->next){
 843                         edok = 0;
 844                         for(j=0; j < len; j++){
 845                                 edok = BME_verts_in_edge(curloop->v, curloop->next->v, bm->edar[j]);
 846                                 if(edok){
 847                                         curloop->e = bm->edar[j];
 848                                         break;
 849                                 }
 850                         }
 851                 }
 852         }
 853         /*rebuild radial*/
 854         for(i=0, curloop = l; i < len; i++, curloop = curloop->next) BME_radial_append(curloop->e, curloop);
 855
 856         /*validate radial*/
 857         for(i=0, curloop = l; i < len; i++, curloop = curloop->next){
 858                 edok = BME_cycle_validate(curloop->e->eflag2, &(curloop->radial));
 859                 if(!edok){
 860                         BME_error();
 861                 }
 862         }
 863         return 1;
 864 }
 865
 866 /**
 867  *                      BME_JFKE
 868  *
 869  *      JOIN FACE KILL EDGE:
 870  *
 871  *      Takes two faces joined by a single 2-manifold edge and fuses them togather.
 872  *      The edge shared by the faces must not be connected to any other edges which have
 873  *      Both faces in its radial cycle
 874  *
 875  *      Examples:
 876  *
 877  *        A                   B
 878  *       ----------           ----------
 879  *       |                |           |        |
 880  *       |   f1   |           |   f1   |
 881  *      v1========v2 = Ok!    v1==V2==v3 == Wrong!
 882  *       |   f2   |           |   f2   |
 883  *       |        |           |        |
 884  *       ----------           ----------
 885  *
 886  *      In the example A, faces f1 and f2 are joined by a single edge, and the euler can safely be used.
 887  *      In example B however, f1 and f2 are joined by multiple edges and will produce an error. The caller
 888  *      in this case should call BME_JEKV on the extra edges before attempting to fuse f1 and f2.
 889  *
 890  *      Also note that the order of arguments decides whether or not certain per-face attributes are present
 891  *      in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited
 892  *      from f1, not f2.
 893  *
 894  *  Returns -
 895  *      A BME_Poly pointer
 896 */
 897
 898 BME_Poly *BME_JFKE(BME_Mesh *bm, BME_Poly *f1, BME_Poly *f2, BME_Edge *e)
 899 {
 900
 901         BME_Loop *curloop, *f1loop=NULL, *f2loop=NULL;
 902         int loopok = 0, newlen = 0,i, f1len=0, f2len=0, radlen=0, edok;
 903
 904         if(f1 == f2) return NULL; //can't join a face to itself
 905         /*verify that e is in both f1 and f2*/
 906         f1len = BME_cycle_length(f1->loopbase);
 907         f2len = BME_cycle_length(f2->loopbase);
 908         for(i=0, curloop = f1->loopbase; i < f1len; i++, curloop = curloop->next){
 909                 if(curloop->e == e){
 910                         f1loop = curloop;
 911                         break;
 912                 }
 913         }
 914         for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = curloop->next){
 915                 if(curloop->e==e){
 916                         f2loop = curloop;
 917                         break;
 918                 }
 919         }
 920         if(!(f1loop && f2loop)) return NULL;
 921
 922         /*validate that edge is 2-manifold edge*/
 923         radlen = BME_cycle_length(&(f1loop->radial));
 924         if(radlen != 2) return NULL;
 925
 926         /*validate direction of f2's loop cycle is compatible.*/
 927         if(f1loop->v == f2loop->v) return NULL;
 928
 929         /*
 930                 Finally validate that for each face, each vertex has another edge in its disk cycle that is
 931                 not e, and not shared.
 932         */
 933         if(BME_radial_find_face(f1loop->next->e,f2)) return NULL;
 934         if(BME_radial_find_face(f1loop->prev->e,f2)) return NULL;
 935         if(BME_radial_find_face(f2loop->next->e,f1)) return NULL;
 936         if(BME_radial_find_face(f2loop->prev->e,f1)) return NULL;
 937
 938         /*join the two loops*/
 939         f1loop->prev->next = f2loop->next;
 940         f2loop->next->prev = f1loop->prev;
 941
 942         f1loop->next->prev = f2loop->prev;
 943         f2loop->prev->next = f1loop->next;
 944
 945         /*if f1loop was baseloop, give f1loop->next the base.*/
 946         if(f1->loopbase == f1loop) f1->loopbase = f1loop->next;
 947
 948         /*validate the new loop*/
 949         loopok = BME_cycle_validate((f1len+f2len)-2, f1->loopbase);
 950         if(!loopok) BME_error();
 951
 952         /*make sure each loop points to the proper face*/
 953         newlen = BME_cycle_length(f1->loopbase);
 954         for(i = 0, curloop = f1->loopbase; i < newlen; i++, curloop = curloop->next) curloop->f = f1;
 955
 956         f1->len = newlen;
 957
 958         edok = BME_cycle_validate(f1->len, f1->loopbase);
 959         if(!edok) BME_error();
 960
 961         /*remove edge from the disk cycle of its two vertices.*/
 962         BME_disk_remove_edge(f1loop->e, f1loop->e->v1);
 963         BME_disk_remove_edge(f1loop->e, f1loop->e->v2);
 964
 965         /*deallocate edge and its two loops as well as f2*/
 966         BLI_remlink(&(bm->edges), f1loop->e);
 967         BLI_remlink(&(bm->polys), f2);
 968         BME_free_edge(bm, f1loop->e);
 969         BME_free_loop(bm, f1loop);
 970         BME_free_loop(bm, f2loop);
 971         BME_free_poly(bm, f2);
 972         return f1;
 973 }