diff options
Diffstat (limited to 'source/blender/blenkernel/intern/BME_eulers.c')
-rw-r--r-- | source/blender/blenkernel/intern/BME_eulers.c | 973 |
1 files changed, 0 insertions, 973 deletions
diff --git a/source/blender/blenkernel/intern/BME_eulers.c b/source/blender/blenkernel/intern/BME_eulers.c deleted file mode 100644 index 25970dd8d91..00000000000 --- a/source/blender/blenkernel/intern/BME_eulers.c +++ /dev/null @@ -1,973 +0,0 @@ -/* - * 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 ***** - */ - -/** \file blender/blenkernel/intern/BME_eulers.c - * \ingroup bke - */ - - -#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_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 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, **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 */ - -/** - * 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, 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_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; - - - /*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; -} - - -/** - * 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; 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; -} - - -/** - * 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; - 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_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, 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; -} |