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