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