source/blender/blenkernel/intern/BME_eulers.c

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