From e03ab146ae673ec296e97f3c146c048417833521 Mon Sep 17 00:00:00 2001 From: Geoffrey Bantle Date: Sat, 23 Feb 2008 22:11:16 +0000 Subject: -> Bevel tools and Bmesh kernel The following is a commit of Levi Schooley's bevel code and the bmesh library it depends on. The current editmode bevel has been replaced with a new per edge bevel function. Vertex beveling is also availible. To set weights for the modifier to use, use the ctrl-shift-e shortcut on either edges or vertices. Recursive beveling is turned of for the time being. --- source/blender/blenkernel/intern/BME_eulers.c | 1007 +++++++++++++++++++++++++ 1 file changed, 1007 insertions(+) create mode 100644 source/blender/blenkernel/intern/BME_eulers.c (limited to 'source/blender/blenkernel/intern/BME_eulers.c') diff --git a/source/blender/blenkernel/intern/BME_eulers.c b/source/blender/blenkernel/intern/BME_eulers.c new file mode 100644 index 00000000000..34187e71beb --- /dev/null +++ b/source/blender/blenkernel/intern/BME_eulers.c @@ -0,0 +1,1007 @@ +/** + * BME_eulers.c jan 2007 + * + * BMesh Euler construction API. + * + * $Id: BME_eulers.c,v 1.00 2007/01/17 17:42:01 Briggs Exp $ + * + * ***** BEGIN GPL/BL DUAL 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. The Blender + * Foundation also sells licenses for use in proprietary software under + * the Blender License. See http://www.blender.org/BL/ for information + * 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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/BL DUAL LICENSE BLOCK ***** + */ + +#include "MEM_guardedalloc.h" + +#include "DNA_listBase.h" +#include "DNA_meshdata_types.h" +#include "DNA_mesh_types.h" + +#include "BKE_utildefines.h" +#include "BKE_bmesh.h" + +#include "BLI_blenlib.h" +#include "bmesh_private.h" +#include "BLI_ghash.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_MV + * + * MAKE VERT EULER: + * + * Makes a single loose vertex. + * + * Returns - + * A BME_Vert pointer. + */ + +BME_Vert *BME_MV(BME_Mesh *bm, float *vec){ + BME_Vert *v = BME_addvertlist(bm, NULL); + VECCOPY(v->co,vec); + return v; +} + +/** + * BME_ME + * + * MAKE EDGE EULER: + * + * Makes a single wire edge between two vertices. + * If the caller does not want there to be duplicate + * edges between the vertices, it is up to them to check + * for this condition beforehand. + * + * Returns - + * A BME_Edge pointer. + */ + +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 BME_exit("ME returned 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; +} + + + +/** + * BME_MF + * + * MAKE FACE EULER: + * Takes a list of edge pointers which form a closed loop and makes a face + * from them. The first edge in elist is considered to be the start of the + * polygon, and v1 and v2 are its vertices and determine the winding of the face + * Other than the first edge, no other assumptions are made about the order of edges + * in the elist array. To verify that it is a single closed loop and derive the correct + * order a simple series of verifications is done and all elements are visited. + * + * Returns - + * A BME_Poly pointer + */ + +#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, *nextv,**vlist; + int i, j, done, cont, edok,vlen; + + if(len < 2) return BME_exit("MF returned NULL"); + + /*make sure that v1 and v2 are in elist[0]*/ + if(BME_verts_in_edge(v1,v2,elist[0]) == 0) return BME_exit("MF returned NULL"); + + /*clear euler flags*/ + for(i=0;ieflag1=elist[i]->eflag2 = 0; + for(i=0;ieflag1 |= 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; iv1, MF_CANDIDATE, 0); + if(edok != 2) return BME_exit("MF returned NULL"); + edok = BME_disk_count_edgeflag(elist[i]->v2, MF_CANDIDATE, 0); + if(edok != 2) return BME_exit("MF returned NULL"); + } + + /*set start edge, start vert and target vert for our loop traversal*/ + curedge = elist[0]; + tv = v1; + curvert = v2; + + /*insert tv into vlist since its the first vertex in face*/ + i=0; + vlist=MEM_callocN(sizeof(BME_Vert*)*len,"BME_MF vlist array"); + 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; ieflag1 & 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;iloopbase)) f->loopbase = l; + BME_cycle_append(f->loopbase, l); + } + + /*take care of edge pointers and radial cycle*/ + for(i=0, l = f->loopbase; inext){ + e = NULL; + if(l == f->loopbase) e = elist[0]; /*first edge*/ + + else{/*search elist for others*/ + for(j=1; jv, 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; inext){ + /*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(); + } + } + + MEM_freeN(vlist); + return f; +} + +/* KILL Eulers */ + +/** + * BME_KV + * + * KILL VERT EULER: + * + * Kills a single loose vertex. + * + * Returns - + * 1 for success, 0 for failure. + */ + +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; +} + +/** + * BME_KE + * + * KILL EDGE EULER: + * + * Kills a wire edge. + * + * Returns - + * 1 for success, 0 for failure. + */ + +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; +} + +/** + * BME_KF + * + * KILL FACE EULER: + * + * The logical inverse of BME_MF. + * Kills a face and removes each of its loops from the radial that it belongs to. + * + * Returns - + * 1 for success, 0 for failure. +*/ + +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_SEMV + * + * SPLIT EDGE MAKE VERT: + * Takes a given edge and splits it into two, creating a new vert. + * + * + * Before: OV---------TV + * After: OV----NV---TV + * + * Returns - + * BME_Vert pointer. + * +*/ + +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, radlen, edok, valance1=0, valance2=0; + + if(BME_vert_in_edge(e,tv) == 0) return BME_exit("SEMV returned 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_SFME + * + * SPLIT FACE MAKE EDGE: + * + * Takes as input two vertices in a single face. An edge is created which divides the original face + * into two distinct regions. One of the regions is assigned to the original face and it is closed off. + * The second region has a new face assigned to it. + * + * Examples: + * + * Before: After: + * ---------- ---------- + * | | | | + * | | | f1 | + * v1 f1 v2 v1======v2 + * | | | f2 | + * | | | | + * ---------- ---------- + * + * Note that the input vertices can be part of the same edge. This will result in a two edged face. + * This is desirable for advanced construction tools and particularly essential for edge bevel. Because + * of this it is up to the caller to decide what to do with the extra edge. + * + * Returns - + * A BME_Poly pointer + */ +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; + + if(f->holes.first) return BME_exit("SFME returned NULL"); //not good, fix me + + /*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 BME_exit("SFME returned 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,NULL); + f2loop = BME_create_loop(bm,v1,e,f2,NULL); + + 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; +} + + +/** + * BME_JEKV + * + * JOIN EDGE KILL VERT: + * Takes a an edge and pointer to one of its vertices and collapses + * the edge on that vertex. + * + * Before: OE KE + * ------- ------- + * | || | + * OV KV TV + * + * + * After: OE + * --------------- + * | | + * OV TV + * + * + * Restrictions: + * KV is a vertex that must have a valance of exactly two. Furthermore + * both edges in KV's disk cycle (OE and KE) must be unique (no double + * edges). + * + * It should also be noted that this euler has the possibility of creating + * faces with just 2 edges. It is up to the caller to decide what to do with + * these faces. + * + * Returns - + * 1 for success, 0 for failure. + */ +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; inext->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)); + i=0; + while(iradial.next->data; + BME_free_loop(bm, killoop); + killoop = nextl; + 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; if->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; +} + + +/** + * BME_loop_reverse + * + * FLIP FACE EULER + * + * Changes the winding order of a face from CW to CCW or vice versa. + * This euler is a bit peculiar in compairson to others as it is its + * own inverse. + * + * TODO: reinsert validation code. + * + * Returns - + * 1 for success, 0 for failure. + */ + +int BME_loop_reverse(BME_Mesh *bm, BME_Poly *f){ + BME_Loop *l = f->loopbase, *curloop, *oldprev, *oldnext; + BME_Edge **elist; + int i, j, edok, len = 0; + + len = BME_cycle_length(l); + elist = MEM_callocN(sizeof(BME_Edge *)*len, "BME Loop Reverse edge array"); + + for(i=0, curloop = l; i< len; i++, curloop=curloop->next){ + BME_radial_remove_loop(curloop, curloop->e); + curloop->e->eflag1 = 0; + elist[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 = elist[1]; + l->next->e = elist[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, elist[j]); + if(edok){ + curloop->e = elist[j]; + break; + } + } + } + } + /*rebuild radial*/ + for(i=0, curloop = l; i < len; i++, curloop = curloop->next){ + BME_radial_append(curloop->e, curloop); + //radok = BME_cycle_validate(curloop->e->tmp.l, &(curloop->radial)); + //if(!radok || curloop->e->loop == NULL) BME_error(); + } + MEM_freeN(elist); + return 1; +} + +/** + * BME_JFKE + * + * JOIN FACE KILL EDGE: + * + * Takes two faces joined by a single 2-manifold edge and fuses them togather. + * The edge shared by the faces must not be connected to any other edges which have + * Both faces in its radial cycle + * + * Examples: + * + * A B + * ---------- ---------- + * | | | | + * | f1 | | f1 | + * v1========v2 = Ok! v1==V2==v3 == Wrong! + * | f2 | | f2 | + * | | | | + * ---------- ---------- + * + * In the example A, faces f1 and f2 are joined by a single edge, and the euler can safely be used. + * In example B however, f1 and f2 are joined by multiple edges and will produce an error. The caller + * in this case should call BME_JEKV on the extra edges before attempting to fuse f1 and f2. + * + * Also note that the order of arguments decides whether or not certain per-face attributes are present + * in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited + * from f1, not f2. + * + * Returns - + * A BME_Poly pointer +*/ + +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, valance1,valance2,edok; + + if(f1->holes.first || f2->holes.first) return BME_exit("JFKE returned NULL"); //dont operate on faces with holes. Not best solution but tolerable. + if(f1 == f2) return BME_exit("JFKE returned 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 BME_exit("JFKE returned NULL"); + + /*validate that edge is 2-manifold edge*/ + radlen = BME_cycle_length(&(f1loop->radial)); + if(radlen != 2) return BME_exit("JFKE returned NULL"); + + /*validate direction of f2's loop cycle is compatible.*/ + if(f1loop->v == f2loop->v) return BME_exit("JFKE returned 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 BME_exit("JFKE returned NULL"); + if(BME_radial_find_face(f1loop->prev->e,f2)) return BME_exit("JFKE returned NULL"); + if(BME_radial_find_face(f2loop->next->e,f1)) return BME_exit("JFKE returned NULL"); + if(BME_radial_find_face(f2loop->prev->e,f1)) return BME_exit("JFKE returned 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; +} + +/** + * BME_MEKL + * + * MAKE EDGE KILL LOOP: + * + * Bridges a perphiary loop of a face with an internal loop + * + * Examples: + * + * ---------------- ---------------- + * | f1 | | f1 | + * | ----- | | ----- | + * | | | | | | | | + * X X | | X-----X | | + * | | | | | | | | + * | ----- | | ----- | + * | | | | + * ---------------- ---------------- + * + * + * Returns - + * A BME_Poly pointer + */ + +/** + * BME_KEML + * + * KILL EDGE MAKE LOOP: + * + * Kills an edge and splits the loose loops off into an internal loop + * + * Examples: + * + * ---------------- ---------------- + * | f1 | | f1 | + * | ----- | | ----- | + * | | | | | | | | + * X ----X | | X X | | + * | | | | | | | | + * | ----- | | ----- | + * | | | | + * ---------------- ---------------- + * + * The tool author should take care to realize that although a face may have + * a hole in its topology, that hole may be filled with one or many other faces. + * Regardless, this does not imply a parent child relationship. + * + * + * Returns - + * A BME_Poly pointer + */ + -- cgit v1.2.3