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