BME_eulers.c

Go to the documentation of this file.

/*
 * BME_eulers.c    jan 2007
 *
 *  BMesh Euler construction API.
 *
 *
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * about this.  
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 *
 * The Original Code is Copyright (C) 2004 Blender Foundation.
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): Geoffrey Bantle.
 *
 * ***** END GPL LICENSE BLOCK *****
 */

#include "MEM_guardedalloc.h"
#include "BLI_listbase.h"
#include "BLI_utildefines.h"

#include "bmesh_private.h"

/*********************************************************
 *                    "Euler API"                        *
 *                                                       *
 *                                                       *
 *   Primitive construction operators for mesh tools.    *
 *                                                       *
 **********************************************************/


/*
    The functions in this file represent the 'primitive' or 'atomic' operators that
    mesh tools use to manipulate the topology of the structure.* The purpose of these
    functions is to provide a trusted set of operators to manipulate the mesh topology
    and which can also be combined together like building blocks to create more 
    sophisticated tools. It needs to be stressed that NO manipulation of an existing 
    mesh structure should be done outside of these functions.
    
    In the BMesh system, each euler is named by an ancronym which describes what it actually does.
    Furthermore each Euler has a logical inverse. An important design criteria of all Eulers is that
    through a Euler's logical inverse you can 'undo' an operation. (Special note should
    be taken of BME_loop_reverse, which is its own inverse).
        
    BME_MF/KF: Make Face and Kill Face
    BME_ME/KE: Make Edge and Kill Edge
    BME_MV/KV: Make Vert and Kill Vert
    BME_SEMV/JEKV: Split Edge, Make Vert and Join Edge, Kill Vert
    BME_SFME/JFKE: Split Face, Make Edge and Join Face, Kill Edge
    BME_loop_reverse: Reverse a Polygon's loop cycle. (used for flip normals for one)
    
    Using a combination of these eleven eulers any non-manifold modelling operation can be achieved.
    Each Euler operator has a detailed explanation of what is does in the comments preceding its 
    code. 

   *The term "Euler Operator" is actually a misnomer when referring to a non-manifold 
    data structure. Its use is in keeping with the convention established by others.

    TODO:
    -Finish inserting 'strict' validation in all Eulers
*/

void *BME_exit(char *s) {
    if (s) printf("%s\n",s);
    return NULL;
}

#define RETCLEAR(bm) {bm->rval->v = bm->rval->e = bm->rval->f = bm->rva->l = NULL;}
/*MAKE Eulers*/

BME_Vert *BME_MV(BME_Mesh *bm, float *vec){
    BME_Vert *v = BME_addvertlist(bm, NULL);    
    VECCOPY(v->co,vec);
    return v;
}

BME_Edge *BME_ME(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2){
    BME_Edge *e=NULL;
    BME_CycleNode *d1=NULL, *d2=NULL;
    int valance1=0, valance2=0, edok;
    
    /*edge must be between two distinct vertices...*/
    if(v1 == v2) return NULL;
    
    #ifndef BME_FASTEULER
    /*count valance of v1*/
    if(v1->edge){ 
        d1 = BME_disk_getpointer(v1->edge,v1);
        if(d1) valance1 = BME_cycle_length(d1);
        else BME_error();
    }
    if(v2->edge){
        d2 = BME_disk_getpointer(v2->edge,v2);
        if(d2) valance2 = BME_cycle_length(d2);
        else BME_error();
    }
    #endif
    
    /*go ahead and add*/
    e = BME_addedgelist(bm, v1, v2, NULL);
    BME_disk_append_edge(e, e->v1);
    BME_disk_append_edge(e, e->v2);
    
    #ifndef BME_FASTEULER
    /*verify disk cycle lengths*/
    d1 = BME_disk_getpointer(e, e->v1);
    edok = BME_cycle_validate(valance1+1, d1);
    if(!edok) BME_error();
    d2 = BME_disk_getpointer(e, e->v2);
    edok = BME_cycle_validate(valance2+1, d2);
    if(!edok) BME_error();
    
    /*verify that edge actually made it into the cycle*/
    edok = BME_disk_hasedge(v1, e);
    if(!edok) BME_error();
    edok = BME_disk_hasedge(v2, e);
    if(!edok) BME_error();
    #endif
    return e;
}



#define MF_CANDIDATE    1
#define MF_VISITED      2
#define MF_TAKEN        4 

BME_Poly *BME_MF(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge **elist, int len)
{
    BME_Poly *f = NULL;
    BME_Edge *curedge;
    BME_Vert *curvert, *tv, **vlist;
    int i, j, done, cont, edok;
    
    if(len < 2) return NULL;
    
    /*make sure that v1 and v2 are in elist[0]*/
    if(BME_verts_in_edge(v1,v2,elist[0]) == 0) return NULL;
    
    /*clear euler flags*/
    for(i=0;i<len;i++) elist[i]->eflag1=elist[i]->eflag2 = 0;
    for(i=0;i<len;i++){
        elist[i]->eflag1 |= MF_CANDIDATE;
        
        /*if elist[i] has a loop, count its radial length*/
        if(elist[i]->loop) elist[i]->eflag2 = BME_cycle_length(&(elist[i]->loop->radial));
        else elist[i]->eflag2 = 0;
    }
    
    /*  For each vertex in each edge, it must have exactly two MF_CANDIDATE edges attached to it
        Note that this does not gauruntee that face is a single closed loop. At best it gauruntees
        that elist contains a finite number of seperate closed loops.
    */
    for(i=0; i<len; i++){
        edok = BME_disk_count_edgeflag(elist[i]->v1, MF_CANDIDATE, 0);
        if(edok != 2) return NULL;
        edok = BME_disk_count_edgeflag(elist[i]->v2, MF_CANDIDATE, 0);
        if(edok != 2) return NULL;
    }
    
    /*set start edge, start vert and target vert for our loop traversal*/
    curedge = elist[0];
    tv = v1;
    curvert = v2;
    
    if(bm->vtarlen < len){
        MEM_freeN(bm->vtar);
        bm->vtar = MEM_callocN(sizeof(BME_Vert *)* len, "BMesh Vert pointer array");
        bm->vtarlen = len;
    }
    /*insert tv into vlist since its the first vertex in face*/
    i=0;
    vlist=bm->vtar;
    vlist[i] = tv;

    /*  Basic procedure: Starting with curv we find the edge in it's disk cycle which hasn't 
        been visited yet. When we do, we put curv in a linked list and find the next MF_CANDIDATE
        edge, loop until we find TV. We know TV is reachable because of test we did earlier.
    */
    done=0;
    while(!done){
        /*add curvert to vlist*/
        /*insert some error cheking here for overflows*/
        i++;
        vlist[i] = curvert;
        
        /*mark curedge as visited*/
        curedge->eflag1 |= MF_VISITED;
        
        /*find next edge and vert*/
        curedge = BME_disk_next_edgeflag(curedge, curvert, MF_CANDIDATE, 0);
        curvert = BME_edge_getothervert(curedge, curvert);
        if(curvert == tv){
            curedge->eflag1 |= MF_VISITED;
            done=1;
        }
    }

    /*  Verify that all edges have been visited It's possible that we did reach tv 
        from sv, but that several unconnected loops were passed in via elist.
    */
    cont=1;
    for(i=0; i<len; i++){
        if((elist[i]->eflag1 & MF_VISITED) == 0) cont = 0;
    }
    
    /*if we get this far, its ok to allocate the face and add the loops*/
    if(cont){
        BME_Loop *l;
        BME_Edge *e;
        f = BME_addpolylist(bm, NULL);
        f->len = len;
        for(i=0;i<len;i++){
            curvert = vlist[i];
            l = BME_create_loop(bm,curvert,NULL,f,NULL);
            if(!(f->loopbase)) f->loopbase = l;
            BME_cycle_append(f->loopbase, l);
        }
        
        /*take care of edge pointers and radial cycle*/
        for(i=0, l = f->loopbase; i<len; i++, l=l->next){
            e = NULL;
            if(l == f->loopbase) e = elist[0]; /*first edge*/
            
            else{/*search elist for others*/
                for(j=1; j<len; j++){
                    edok = BME_verts_in_edge(l->v, l->next->v, elist[j]);
                    if(edok){ 
                        e = elist[j];
                        break;
                    }
                }
            }
            l->e = e; /*set pointer*/
            BME_radial_append(e, l); /*append into radial*/
        }

        f->len = len;
        
        /*Validation Loop cycle*/
        edok = BME_cycle_validate(len, f->loopbase);
        if(!edok) BME_error();
        for(i=0, l = f->loopbase; i<len; i++, l=l->next){
            /*validate loop vert pointers*/
            edok = BME_verts_in_edge(l->v, l->next->v, l->e);
            if(!edok) BME_error();
            /*validate the radial cycle of each edge*/
            edok = BME_cycle_length(&(l->radial));
            if(edok != (l->e->eflag2 + 1)) BME_error();
        }
    }
    return f;
}

/* KILL Eulers */

int BME_KV(BME_Mesh *bm, BME_Vert *v){
    if(v->edge == NULL){ 
        BLI_remlink(&(bm->verts), v);
        BME_free_vert(bm,v);
        return 1;
    }
    return 0;
}

int BME_KE(BME_Mesh *bm, BME_Edge *e){
    int edok;
    
    /*Make sure that no faces!*/
    if(e->loop == NULL){
        BME_disk_remove_edge(e, e->v1);
        BME_disk_remove_edge(e, e->v2);
        
        /*verify that edge out of disk*/
        edok = BME_disk_hasedge(e->v1, e);
        if(edok) BME_error();
        edok = BME_disk_hasedge(e->v2, e);
        if(edok) BME_error();
        
        /*remove and deallocate*/
        BLI_remlink(&(bm->edges), e);
        BME_free_edge(bm, e);
        return 1;
    }
    return 0;
}

int BME_KF(BME_Mesh *bm, BME_Poly *bply){
    BME_Loop *newbase,*oldbase, *curloop;
    int i,len=0;
    
    /*add validation to make sure that radial cycle is cleaned up ok*/
    /*deal with radial cycle first*/
    len = BME_cycle_length(bply->loopbase);
    for(i=0, curloop=bply->loopbase; i < len; i++, curloop = curloop->next) 
        BME_radial_remove_loop(curloop, curloop->e);
    
    /*now deallocate the editloops*/
    for(i=0; i < len; i++){
        newbase = bply->loopbase->next;
        oldbase = bply->loopbase;
        BME_cycle_remove(oldbase, oldbase);
        BME_free_loop(bm, oldbase);
        bply->loopbase = newbase;
    }
    
    BLI_remlink(&(bm->polys), bply);
    BME_free_poly(bm, bply);
    return 1;
}

/*SPLIT Eulers*/

BME_Vert *BME_SEMV(BME_Mesh *bm, BME_Vert *tv, BME_Edge *e, BME_Edge **re){
    BME_Vert *nv, *ov;
    BME_CycleNode *diskbase;
    BME_Edge *ne;
    int i, edok, valance1=0, valance2=0;
    
    if(BME_vert_in_edge(e,tv) == 0) return NULL;
    ov = BME_edge_getothervert(e,tv);
    //v2 = tv;

    /*count valance of v1*/
    diskbase = BME_disk_getpointer(e, ov);
    valance1 = BME_cycle_length(diskbase);
    /*count valance of v2*/
    diskbase = BME_disk_getpointer(e, tv);
    valance2 = BME_cycle_length(diskbase);
    
    nv = BME_addvertlist(bm, tv);
    ne = BME_addedgelist(bm, nv, tv, e);
    
    //e->v2 = nv;
    /*remove e from v2's disk cycle*/
    BME_disk_remove_edge(e, tv);
    /*swap out tv for nv in e*/
    BME_edge_swapverts(e, tv, nv);
    /*add e to nv's disk cycle*/
    BME_disk_append_edge(e, nv);
    /*add ne to nv's disk cycle*/
    BME_disk_append_edge(ne, nv);
    /*add ne to tv's disk cycle*/
    BME_disk_append_edge(ne, tv);
    /*verify disk cycles*/
    diskbase = BME_disk_getpointer(ov->edge,ov);
    edok = BME_cycle_validate(valance1, diskbase);
    if(!edok) BME_error();
    diskbase = BME_disk_getpointer(tv->edge,tv);
    edok = BME_cycle_validate(valance2, diskbase);
    if(!edok) BME_error();
    diskbase = BME_disk_getpointer(nv->edge,nv);
    edok = BME_cycle_validate(2, diskbase);
    if(!edok) BME_error();
    
    /*Split the radial cycle if present*/
    if(e->loop){
        BME_Loop *nl,*l;
        BME_CycleNode *radEBase=NULL, *radNEBase=NULL;
        int radlen = BME_cycle_length(&(e->loop->radial));
        /*Take the next loop. Remove it from radial. Split it. Append to appropriate radials.*/
        while(e->loop){
            l=e->loop;
            l->f->len++;
            BME_radial_remove_loop(l,e);
            
            nl = BME_create_loop(bm,NULL,NULL,l->f,l);
            nl->prev = l;
            nl->next = l->next;
            nl->prev->next = nl;
            nl->next->prev = nl;
            nl->v = nv;
            
            /*assign the correct edge to the correct loop*/
            if(BME_verts_in_edge(nl->v, nl->next->v, e)){
                nl->e = e;
                l->e = ne;
                
                /*append l into ne's rad cycle*/
                if(!radNEBase){
                    radNEBase = &(l->radial);
                    radNEBase->next = NULL;
                    radNEBase->prev = NULL;
                }
                
                if(!radEBase){
                    radEBase = &(nl->radial);
                    radEBase->next = NULL;
                    radEBase->prev = NULL;
                }
                
                BME_cycle_append(radEBase,&(nl->radial));
                BME_cycle_append(radNEBase,&(l->radial));
                    
            }
            else if(BME_verts_in_edge(nl->v,nl->next->v,ne)){
                nl->e = ne;
                l->e = e;
                
                if(!radNEBase){
                    radNEBase = &(nl->radial);
                    radNEBase->next = NULL;
                    radNEBase->prev = NULL;
                }
                if(!radEBase){
                    radEBase = &(l->radial);
                    radEBase->next = NULL;
                    radEBase->prev = NULL;
                }
                BME_cycle_append(radEBase,&(l->radial));
                BME_cycle_append(radNEBase,&(nl->radial));
            }
                    
        }
        
        e->loop = radEBase->data;
        ne->loop = radNEBase->data;
        
        /*verify length of radial cycle*/
        edok = BME_cycle_validate(radlen,&(e->loop->radial));
        if(!edok) BME_error();
        edok = BME_cycle_validate(radlen,&(ne->loop->radial));
        if(!edok) BME_error();
        
        /*verify loop->v and loop->next->v pointers for e*/
        for(i=0,l=e->loop; i < radlen; i++, l = l->radial.next->data){
            if(!(l->e == e)) BME_error();
            if(!(l->radial.data == l)) BME_error();
            if(l->prev->e != ne && l->next->e != ne) BME_error();
            edok = BME_verts_in_edge(l->v, l->next->v, e);
            if(!edok) BME_error();
            if(l->v == l->next->v) BME_error();
            if(l->e == l->next->e) BME_error();
            /*verify loop cycle for kloop->f*/
            edok = BME_cycle_validate(l->f->len, l->f->loopbase);
            if(!edok) BME_error();
        }
        /*verify loop->v and loop->next->v pointers for ne*/
        for(i=0,l=ne->loop; i < radlen; i++, l = l->radial.next->data){
            if(!(l->e == ne)) BME_error();
            if(!(l->radial.data == l)) BME_error();
            if(l->prev->e != e && l->next->e != e) BME_error();
            edok = BME_verts_in_edge(l->v, l->next->v, ne);
            if(!edok) BME_error();
            if(l->v == l->next->v) BME_error();
            if(l->e == l->next->e) BME_error();
            /*verify loop cycle for kloop->f. Redundant*/
            edok = BME_cycle_validate(l->f->len, l->f->loopbase);
            if(!edok) BME_error();
        }
    }
    
    if(re) *re = ne;
    return nv;
}

BME_Poly *BME_SFME(BME_Mesh *bm, BME_Poly *f, BME_Vert *v1, BME_Vert *v2, BME_Loop **rl){

    BME_Poly *f2;
    BME_Loop *v1loop = NULL, *v2loop = NULL, *curloop, *f1loop=NULL, *f2loop=NULL;
    BME_Edge *e;
    int i, len, f1len, f2len;
    
    
    /*verify that v1 and v2 are in face.*/
    len = BME_cycle_length(f->loopbase);
    for(i = 0, curloop = f->loopbase; i < len; i++, curloop = curloop->next){
        if(curloop->v == v1) v1loop = curloop;
        else if(curloop->v == v2) v2loop = curloop;
    }
    
    if(!v1loop || !v2loop) return NULL;
    
    /*allocate new edge between v1 and v2*/
    e = BME_addedgelist(bm, v1, v2,NULL);
    BME_disk_append_edge(e, v1);
    BME_disk_append_edge(e, v2);
    
    f2 = BME_addpolylist(bm,f);
    f1loop = BME_create_loop(bm,v2,e,f,v2loop);
    f2loop = BME_create_loop(bm,v1,e,f2,v1loop);
    
    f1loop->prev = v2loop->prev;
    f2loop->prev = v1loop->prev;
    v2loop->prev->next = f1loop;
    v1loop->prev->next = f2loop;
    
    f1loop->next = v1loop;
    f2loop->next = v2loop;
    v1loop->prev = f1loop;
    v2loop->prev = f2loop;
    
    f2->loopbase = f2loop;
    f->loopbase = f1loop;
    
    /*validate both loops*/
    /*I dont know how many loops are supposed to be in each face at this point! FIXME!*/
    
    /*go through all of f2's loops and make sure they point to it properly.*/
    f2len = BME_cycle_length(f2->loopbase);
    for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = curloop->next) curloop->f = f2;
    
    /*link up the new loops into the new edges radial*/
    BME_radial_append(e, f1loop);
    BME_radial_append(e, f2loop);
    
    
    f2->len = f2len;
    
    f1len = BME_cycle_length(f->loopbase);
    f->len = f1len;
    
    if(rl) *rl = f2loop;
    return f2;
}


int BME_JEKV(BME_Mesh *bm, BME_Edge *ke, BME_Vert *kv)
{
    BME_Edge *oe;
    BME_Vert *ov, *tv;
    BME_CycleNode *diskbase;
    BME_Loop *killoop,*nextl;
    int len,radlen=0, halt = 0, i, valance1, valance2,edok;
    
    if(BME_vert_in_edge(ke,kv) == 0) return 0;
    diskbase = BME_disk_getpointer(kv->edge, kv);
    len = BME_cycle_length(diskbase);
    
    if(len == 2){
        oe = BME_disk_nextedge(ke, kv);
        tv = BME_edge_getothervert(ke, kv);
        ov = BME_edge_getothervert(oe, kv);     
        halt = BME_verts_in_edge(kv, tv, oe); //check for double edges
        
        if(halt) return 0;
        else{
            
            /*For verification later, count valance of ov and tv*/
            diskbase = BME_disk_getpointer(ov->edge, ov);
            valance1 = BME_cycle_length(diskbase);
            diskbase = BME_disk_getpointer(tv->edge, tv);
            valance2 = BME_cycle_length(diskbase);
            
            /*remove oe from kv's disk cycle*/
            BME_disk_remove_edge(oe,kv);
            /*relink oe->kv to be oe->tv*/
            BME_edge_swapverts(oe, kv, tv);
            /*append oe to tv's disk cycle*/
            BME_disk_append_edge(oe, tv);
            /*remove ke from tv's disk cycle*/
            BME_disk_remove_edge(ke, tv);
        
            

            /*deal with radial cycle of ke*/
            if(ke->loop){
                /*first step, fix the neighboring loops of all loops in ke's radial cycle*/
                radlen = BME_cycle_length(&(ke->loop->radial));
                for(i=0,killoop = ke->loop; i<radlen; i++, killoop = BME_radial_nextloop(killoop)){
                    /*relink loops and fix vertex pointer*/
                    killoop->next->prev = killoop->prev;
                    killoop->prev->next = killoop->next;
                    if(killoop->next->v == kv) killoop->next->v = tv;
                    
                    /*fix len attribute of face*/
                    killoop->f->len--;
                    if(killoop->f->loopbase == killoop) killoop->f->loopbase = killoop->next;
                }
                /*second step, remove all the hanging loops attached to ke*/
                killoop = ke->loop;
                radlen = BME_cycle_length(&(ke->loop->radial));
                /*make sure we have enough room in bm->lpar*/
                if(bm->lparlen < radlen){
                    MEM_freeN(bm->lpar);
                    bm->lpar = MEM_callocN(sizeof(BME_Loop *)* radlen, "BMesh Loop pointer array");
                    bm->lparlen = bm->lparlen * radlen;
                }
                /*this should be wrapped into a bme_free_radial function to be used by BME_KF as well...*/
                i=0;
                while(i<radlen){
                    bm->lpar[i] = killoop;
                    killoop = killoop->radial.next->data;
                    i++;
                }
                i=0;
                while(i<radlen){
                    BME_free_loop(bm,bm->lpar[i]);
                    i++;
                }
                /*Validate radial cycle of oe*/
                edok = BME_cycle_validate(radlen,&(oe->loop->radial));
                
            }
            

            /*Validate disk cycles*/
            diskbase = BME_disk_getpointer(ov->edge,ov);
            edok = BME_cycle_validate(valance1, diskbase);
            if(!edok) BME_error();
            diskbase = BME_disk_getpointer(tv->edge,tv);
            edok = BME_cycle_validate(valance2, diskbase);
            if(!edok) BME_error();
            
            /*Validate loop cycle of all faces attached to oe*/
            for(i=0,nextl = oe->loop; i<radlen; i++, nextl = BME_radial_nextloop(nextl)){
                edok = BME_cycle_validate(nextl->f->len,nextl->f->loopbase);
                if(!edok) BME_error();
            }
            /*deallocate edge*/
            BLI_remlink(&(bm->edges), ke);
            BME_free_edge(bm, ke);
            /*deallocate vertex*/
            BLI_remlink(&(bm->verts), kv);
            BME_free_vert(bm, kv);  
            return 1;
        }
    }
    return 0;
}


int BME_loop_reverse(BME_Mesh *bm, BME_Poly *f){
    BME_Loop *l = f->loopbase, *curloop, *oldprev, *oldnext;
    int i, j, edok, len = 0;

    len = BME_cycle_length(l);
    if(bm->edarlen < len){
        MEM_freeN(bm->edar);
        bm->edar = MEM_callocN(sizeof(BME_Edge *)* len, "BMesh Edge pointer array");
        bm->edarlen = len;
    }
    
    for(i=0, curloop = l; i< len; i++, curloop=curloop->next){
        curloop->e->eflag1 = 0;
        curloop->e->eflag2 = BME_cycle_length(&curloop->radial);
        BME_radial_remove_loop(curloop, curloop->e);
        /*in case of border edges we HAVE to zero out curloop->radial Next/Prev*/
        curloop->radial.next = curloop->radial.prev = NULL;
        bm->edar[i] = curloop->e;
    }
    
    /*actually reverse the loop. This belongs in BME_cycle_reverse!*/
    for(i=0, curloop = l; i < len; i++){
        oldnext = curloop->next;
        oldprev = curloop->prev;
        curloop->next = oldprev;
        curloop->prev = oldnext;
        curloop = oldnext;
    }

    if(len == 2){ //two edged face
        //do some verification here!
        l->e = bm->edar[1];
        l->next->e = bm->edar[0];
    }
    else{
        for(i=0, curloop = l; i < len; i++, curloop = curloop->next){
            edok = 0;
            for(j=0; j < len; j++){
                edok = BME_verts_in_edge(curloop->v, curloop->next->v, bm->edar[j]);
                if(edok){
                    curloop->e = bm->edar[j];
                    break;
                }
            }
        }
    }
    /*rebuild radial*/
    for(i=0, curloop = l; i < len; i++, curloop = curloop->next) BME_radial_append(curloop->e, curloop);
    
    /*validate radial*/
    for(i=0, curloop = l; i < len; i++, curloop = curloop->next){
        edok = BME_cycle_validate(curloop->e->eflag2, &(curloop->radial));
        if(!edok){
            BME_error();
        }
    }
    return 1;
}

BME_Poly *BME_JFKE(BME_Mesh *bm, BME_Poly *f1, BME_Poly *f2, BME_Edge *e)
{
    
    BME_Loop *curloop, *f1loop=NULL, *f2loop=NULL;
    int loopok = 0, newlen = 0,i, f1len=0, f2len=0, radlen=0, edok;
    
    if(f1 == f2) return NULL; //can't join a face to itself
    /*verify that e is in both f1 and f2*/
    f1len = BME_cycle_length(f1->loopbase);
    f2len = BME_cycle_length(f2->loopbase);
    for(i=0, curloop = f1->loopbase; i < f1len; i++, curloop = curloop->next){
        if(curloop->e == e){ 
            f1loop = curloop;
            break;
        }
    }
    for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = curloop->next){
        if(curloop->e==e){
            f2loop = curloop;
            break;
        }
    }
    if(!(f1loop && f2loop)) return NULL;
    
    /*validate that edge is 2-manifold edge*/
    radlen = BME_cycle_length(&(f1loop->radial));
    if(radlen != 2) return NULL;

    /*validate direction of f2's loop cycle is compatible.*/
    if(f1loop->v == f2loop->v) return NULL;
    
    /*
        Finally validate that for each face, each vertex has another edge in its disk cycle that is 
        not e, and not shared.
    */
    if(BME_radial_find_face(f1loop->next->e,f2)) return NULL;
    if(BME_radial_find_face(f1loop->prev->e,f2)) return NULL;
    if(BME_radial_find_face(f2loop->next->e,f1)) return NULL;
    if(BME_radial_find_face(f2loop->prev->e,f1)) return NULL;
    
    /*join the two loops*/
    f1loop->prev->next = f2loop->next;
    f2loop->next->prev = f1loop->prev;
    
    f1loop->next->prev = f2loop->prev;
    f2loop->prev->next = f1loop->next;
    
    /*if f1loop was baseloop, give f1loop->next the base.*/
    if(f1->loopbase == f1loop) f1->loopbase = f1loop->next;
    
    /*validate the new loop*/
    loopok = BME_cycle_validate((f1len+f2len)-2, f1->loopbase);
    if(!loopok) BME_error();
    
    /*make sure each loop points to the proper face*/
    newlen = BME_cycle_length(f1->loopbase);
    for(i = 0, curloop = f1->loopbase; i < newlen; i++, curloop = curloop->next) curloop->f = f1;
    
    f1->len = newlen;
    
    edok = BME_cycle_validate(f1->len, f1->loopbase);
    if(!edok) BME_error();
    
    /*remove edge from the disk cycle of its two vertices.*/
    BME_disk_remove_edge(f1loop->e, f1loop->e->v1);
    BME_disk_remove_edge(f1loop->e, f1loop->e->v2);
    
    /*deallocate edge and its two loops as well as f2*/
    BLI_remlink(&(bm->edges), f1loop->e);
    BLI_remlink(&(bm->polys), f2);
    BME_free_edge(bm, f1loop->e);
    BME_free_loop(bm, f1loop);
    BME_free_loop(bm, f2loop);
    BME_free_poly(bm, f2);  
    return f1;
}