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