4173f368557c01f63174323260797963ee6db3a0
[blender.git] / source / blender / bmesh / intern / bmesh_eulers.c
1 /**
2  * bmesh_eulers.c    jan 2007
3  *
4  *      BM Euler construction API.
5  *
6  * $Id: bmesh_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_customdata.h"
42 #include "BKE_utildefines.h"
43
44 #include "bmesh.h"
45 #include "bmesh_private.h"
46
47 #include "BLI_blenlib.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 BM 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 bmesh_loop_reverse, which is its own inverse).
71                 
72         bmesh_MF/KF: Make Face and Kill Face
73         bmesh_ME/KE: Make Edge and Kill Edge
74         bmesh_MV/KV: Make Vert and Kill Vert
75         bmesh_SEMV/JEKV: Split Edge, Make Vert and Join Edge, Kill Vert
76         bmesh_SFME/JFKE: Split Face, Make Edge and Join Face, Kill Edge
77         bmesh_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         -Make seperate 'debug levels' of validation
88         -Add in the UnglueFaceRegionMakeVert and GlueFaceRegionKillVert eulers.
89
90         NOTE:
91         -The functions in this file are notoriously difficult to debug and even understand sometimes.
92          better code comments would be nice....
93
94 */
95
96
97 /*MAKE Eulers*/
98
99 /**
100  *                      bmesh_MV
101  *
102  *      MAKE VERT EULER:
103  *      
104  *      Makes a single loose vertex.
105  *
106  *      Returns -
107  *      A BMVert pointer.
108  */
109
110 BMVert *bmesh_mv(BMesh *bm, float *vec){
111         BMVert *v = bmesh_addvertlist(bm, NULL);        
112         VECCOPY(v->co,vec);
113         return v;
114 }
115
116 /**
117  *                      bmesh_ME
118  *
119  *      MAKE EDGE EULER:
120  *      
121  *      Makes a single wire edge between two vertices.
122  *      If the caller does not want there to be duplicate
123  *      edges between the vertices, it is up to them to check 
124  *      for this condition beforehand.
125  *
126  *      Returns -
127  *      A BMEdge pointer.
128  */
129
130 BMEdge *bmesh_me(BMesh *bm, BMVert *v1, BMVert *v2){
131         BMEdge *e=NULL;
132         BMNode *d1=NULL, *d2=NULL;
133         int valance1=0, valance2=0, edok;
134         
135         /*edge must be between two distinct vertices...*/
136         if(v1 == v2) return NULL;
137         
138         #ifndef bmesh_FASTEULER
139         /*count valance of v1*/
140         if(v1->edge){ 
141                 d1 = bmesh_disk_getpointer(v1->edge,v1);
142                 if(d1) valance1 = bmesh_cycle_length(d1);
143                 else bmesh_error();
144         }
145         if(v2->edge){
146                 d2 = bmesh_disk_getpointer(v2->edge,v2);
147                 if(d2) valance2 = bmesh_cycle_length(d2);
148                 else bmesh_error();
149         }
150         #endif
151         
152         /*go ahead and add*/
153         e = bmesh_addedgelist(bm, v1, v2, NULL);
154         bmesh_disk_append_edge(e, e->v1);
155         bmesh_disk_append_edge(e, e->v2);
156         
157         #ifndef bmesh_FASTEULER
158         /*verify disk cycle lengths*/
159         d1 = bmesh_disk_getpointer(e, e->v1);
160         edok = bmesh_cycle_validate(valance1+1, d1);
161         if(!edok) bmesh_error();
162         d2 = bmesh_disk_getpointer(e, e->v2);
163         edok = bmesh_cycle_validate(valance2+1, d2);
164         if(!edok) bmesh_error();
165         
166         /*verify that edge actually made it into the cycle*/
167         edok = bmesh_disk_hasedge(v1, e);
168         if(!edok) bmesh_error();
169         edok = bmesh_disk_hasedge(v2, e);
170         if(!edok) bmesh_error();
171         #endif
172         return e;
173 }
174
175
176
177 /**
178  *                      bmesh_MF
179  *
180  *      MAKE FACE EULER:
181  *      Takes a list of edge pointers which form a closed loop and makes a face 
182  *  from them. The first edge in elist is considered to be the start of the 
183  *      polygon, and v1 and v2 are its vertices and determine the winding of the face 
184  *  Other than the first edge, no other assumptions are made about the order of edges
185  *  in the elist array. To verify that it is a single closed loop and derive the correct 
186  *  order a simple series of verifications is done and all elements are visited.
187  *              
188  *  Returns -
189  *      A BMFace pointer
190  */
191
192 #define MF_CANDIDATE    1
193 #define MF_VISITED              2
194 #define MF_TAKEN                4 
195
196 BMFace *bmesh_mf(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **elist, int len)
197 {
198         BMFace *f = NULL;
199         BMEdge *curedge;
200         BMVert *curvert, *tv, **vlist;
201         int i, j, done, cont, edok;
202         
203         if(len < 2) goto error;
204         
205         /*make sure that v1 and v2 are in elist[0]*/
206         if(bmesh_verts_in_edge(v1,v2,elist[0]) == 0) 
207                 goto error;
208         
209         /*clear euler flags*/
210         for(i=0;i<len;i++) elist[i]->head.eflag1=elist[i]->head.eflag2 = 0;
211         for(i=0;i<len;i++){
212                 elist[i]->head.eflag1 |= MF_CANDIDATE;
213                 
214                 /*if elist[i] has a loop, count its radial length*/
215                 if(elist[i]->loop) elist[i]->head.eflag2 = bmesh_cycle_length(&(elist[i]->loop->radial));
216                 else elist[i]->head.eflag2 = 0;
217         }
218         
219         /*      For each vertex in each edge, it must have exactly two MF_CANDIDATE edges attached to it
220                 Note that this does not gauruntee that face is a single closed loop. At best it gauruntees
221                 that elist contains a finite number of seperate closed loops.
222         */
223         for(i=0; i<len; i++){
224                 edok = bmesh_disk_count_edgeflag(elist[i]->v1, MF_CANDIDATE, 0);
225                 if(edok != 2) goto error;
226                 edok = bmesh_disk_count_edgeflag(elist[i]->v2, MF_CANDIDATE, 0);
227                 if(edok != 2) goto error;
228         }
229         
230         /*set start edge, start vert and target vert for our loop traversal*/
231         curedge = elist[0];
232         tv = v1;
233         curvert = v2;
234         
235         if(bm->vtarlen < len){
236                 if (bm->vtar) MEM_freeN(bm->vtar);
237                 bm->vtar = MEM_callocN(sizeof(BMVert *)* len, "BM Vert pointer array");
238                 bm->vtarlen = len;
239         }
240         /*insert tv into vlist since its the first vertex in face*/
241         i=0;
242         vlist=bm->vtar;
243         vlist[i] = tv;
244
245         /*      Basic procedure: Starting with curv we find the edge in it's disk cycle which hasn't 
246                 been visited yet. When we do, we put curv in a linked list and find the next MF_CANDIDATE
247                 edge, loop until we find TV. We know TV is reachable because of test we did earlier.
248         */
249         done=0;
250         while(!done){
251                 /*add curvert to vlist*/
252                 /*insert some error cheking here for overflows*/
253                 i++;
254                 vlist[i] = curvert;
255                 
256                 /*mark curedge as visited*/
257                 curedge->head.eflag1 |= MF_VISITED;
258                 
259                 /*find next edge and vert*/
260                 curedge = bmesh_disk_next_edgeflag(curedge, curvert, MF_CANDIDATE, 0);
261                 curvert = bmesh_edge_getothervert(curedge, curvert);
262                 if(curvert == tv){
263                         curedge->head.eflag1 |= MF_VISITED;
264                         done=1;
265                 }
266         }
267
268         /*      Verify that all edges have been visited It's possible that we did reach tv 
269                 from sv, but that several unconnected loops were passed in via elist.
270         */
271         cont=1;
272         for(i=0; i<len; i++){
273                 if((elist[i]->head.eflag1 & MF_VISITED) == 0) cont = 0;
274         }
275         
276         /*if we get this far, its ok to allocate the face and add the loops*/
277         if(cont){
278                 BMLoop *l;
279                 BMEdge *e;
280                 f = bmesh_addpolylist(bm, NULL);
281                 f->len = len;
282                 for(i=0;i<len;i++){
283                         curvert = vlist[i];
284                         l = bmesh_create_loop(bm,curvert,NULL,f,NULL);
285                         if(!(f->loopbase)) f->loopbase = l;
286                         bmesh_cycle_append(f->loopbase, l);
287                 }
288                 
289                 /*take care of edge pointers and radial cycle*/
290                 for(i=0, l = f->loopbase; i<len; i++, l=((BMLoop*)(l->head.next))){
291                         e = NULL;
292                         if(l == f->loopbase) e = elist[0]; /*first edge*/
293                         
294                         else{/*search elist for others*/
295                                 for(j=1; j<len; j++){
296                                         edok = bmesh_verts_in_edge(l->v, ((BMLoop*)(l->head.next))->v, elist[j]);
297                                         if(edok){ 
298                                                 e = elist[j];
299                                                 break;
300                                         }
301                                 }
302                         }
303                         l->e = e; /*set pointer*/
304                         bmesh_radial_append(e, l); /*append into radial*/
305                 }
306
307                 f->len = len;
308                 
309                 /*Validation Loop cycle*/
310                 edok = bmesh_cycle_validate(len, f->loopbase);
311                 if(!edok) bmesh_error();
312                 for(i=0, l = f->loopbase; i<len; i++, l=((BMLoop*)(l->head.next))){
313                         /*validate loop vert pointers*/
314                         edok = bmesh_verts_in_edge(l->v, ((BMLoop*)(l->head.next))->v, l->e);
315                         if(!edok) bmesh_error();
316                         /*validate the radial cycle of each edge*/
317                         edok = bmesh_cycle_length(&(l->radial));
318                         if(edok != (l->e->head.eflag2 + 1)) bmesh_error();
319                 }
320         }
321
322         for(i=0;i<len;i++) elist[i]->head.eflag1=elist[i]->head.eflag2 = 0;
323         return f;
324 error:
325         for(i=0;i<len;i++) elist[i]->head.eflag1=elist[i]->head.eflag2 = 0;
326         return NULL;
327
328 }
329
330 /* KILL Eulers */
331
332 /**
333  *                      bmesh_KV
334  *
335  *      KILL VERT EULER:
336  *      
337  *      Kills a single loose vertex.
338  *
339  *      Returns -
340  *      1 for success, 0 for failure.
341  */
342
343 int bmesh_kv(BMesh *bm, BMVert *v){
344         if(v->edge == NULL){ 
345                 if (BM_TestHFlag(v, BM_SELECT)) bm->totvertsel--;
346
347                 BLI_remlink(&(bm->verts), &(v->head));
348                 bmesh_free_vert(bm,v);
349                 return 1;
350         }
351         return 0;
352 }
353
354 /**
355  *                      bmesh_KE
356  *
357  *      KILL EDGE EULER:
358  *      
359  *      Kills a wire edge.
360  *
361  *      Returns -
362  *      1 for success, 0 for failure.
363  */
364
365 int bmesh_ke(BMesh *bm, BMEdge *e){
366         int edok;
367         
368         /*Make sure that no faces!*/
369         if(e->loop == NULL){
370                 bmesh_disk_remove_edge(e, e->v1);
371                 bmesh_disk_remove_edge(e, e->v2);
372                 
373                 /*verify that edge out of disk*/
374                 edok = bmesh_disk_hasedge(e->v1, e);
375                 if(edok) bmesh_error();
376                 edok = bmesh_disk_hasedge(e->v2, e);
377                 if(edok) bmesh_error();
378                 
379                 /*remove and deallocate*/
380                 if (BM_TestHFlag(e, BM_SELECT)) bm->totedgesel--;
381                 BLI_remlink(&(bm->edges), &(e->head));
382                 bmesh_free_edge(bm, e);
383                 return 1;
384         }
385         return 0;
386 }
387
388 /**
389  *                      bmesh_KF
390  *
391  *      KILL FACE EULER:
392  *      
393  *      The logical inverse of bmesh_MF.
394  *      Kills a face and removes each of its loops from the radial that it belongs to.
395  *
396  *  Returns -
397  *      1 for success, 0 for failure.
398 */
399
400 int bmesh_kf(BMesh *bm, BMFace *bply){
401         BMLoop *newbase,*oldbase, *curloop;
402         int i,len=0;
403         
404         /*add validation to make sure that radial cycle is cleaned up ok*/
405         /*deal with radial cycle first*/
406         len = bmesh_cycle_length(bply->loopbase);
407         for(i=0, curloop=bply->loopbase; i < len; i++, curloop = ((BMLoop*)(curloop->head.next))) 
408                 bmesh_radial_remove_loop(curloop, curloop->e);
409         
410         /*now deallocate the editloops*/
411         for(i=0; i < len; i++){
412                 newbase = ((BMLoop*)(bply->loopbase->head.next));
413                 oldbase = bply->loopbase;
414                 bmesh_cycle_remove(oldbase, oldbase);
415                 bmesh_free_loop(bm, oldbase);
416                 bply->loopbase = newbase;
417         }
418         
419         if (BM_TestHFlag(bply, BM_SELECT)) bm->totfacesel--;
420         BLI_remlink(&(bm->polys), &(bply->head));
421         bmesh_free_poly(bm, bply);
422         return 1;
423 }
424
425 /*SPLIT Eulers*/
426
427 /**
428  *                      bmesh_SEMV
429  *
430  *      SPLIT EDGE MAKE VERT:
431  *      Takes a given edge and splits it into two, creating a new vert.
432  *
433  *
434  *              Before: OV---------TV   
435  *              After:  OV----NV---TV
436  *
437  *  Returns -
438  *      BMVert pointer.
439  *
440 */
441
442 BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **re){
443         BMVert *nv, *ov;
444         BMNode *diskbase;
445         BMEdge *ne;
446         int i, edok, valance1=0, valance2=0;
447         
448         if(bmesh_vert_in_edge(e,tv) == 0) return NULL;
449         ov = bmesh_edge_getothervert(e,tv);
450         //v2 = tv;
451
452         /*count valance of v1*/
453         diskbase = bmesh_disk_getpointer(e, ov);
454         valance1 = bmesh_cycle_length(diskbase);
455         /*count valance of v2*/
456         diskbase = bmesh_disk_getpointer(e, tv);
457         valance2 = bmesh_cycle_length(diskbase);
458         
459         nv = bmesh_addvertlist(bm, tv);
460         ne = bmesh_addedgelist(bm, nv, tv, e);
461         
462         //e->v2 = nv;
463         /*remove e from v2's disk cycle*/
464         bmesh_disk_remove_edge(e, tv);
465         /*swap out tv for nv in e*/
466         bmesh_edge_swapverts(e, tv, nv);
467         /*add e to nv's disk cycle*/
468         bmesh_disk_append_edge(e, nv);
469         /*add ne to nv's disk cycle*/
470         bmesh_disk_append_edge(ne, nv);
471         /*add ne to tv's disk cycle*/
472         bmesh_disk_append_edge(ne, tv);
473         /*verify disk cycles*/
474         diskbase = bmesh_disk_getpointer(ov->edge,ov);
475         edok = bmesh_cycle_validate(valance1, diskbase);
476         if(!edok) bmesh_error();
477         diskbase = bmesh_disk_getpointer(tv->edge,tv);
478         edok = bmesh_cycle_validate(valance2, diskbase);
479         if(!edok) bmesh_error();
480         diskbase = bmesh_disk_getpointer(nv->edge,nv);
481         edok = bmesh_cycle_validate(2, diskbase);
482         if(!edok) bmesh_error();
483         
484         /*Split the radial cycle if present*/
485         if(e->loop){
486                 BMLoop *nl,*l;
487                 BMNode *radEBase=NULL, *radNEBase=NULL;
488                 int radlen = bmesh_cycle_length(&(e->loop->radial));
489                 /*Take the next loop. Remove it from radial. Split it. Append to appropriate radials.*/
490                 while(e->loop){
491                         l=e->loop;
492                         l->f->len++;
493                         bmesh_radial_remove_loop(l,e);
494                         
495                         nl = bmesh_create_loop(bm,NULL,NULL,l->f,l);
496                         nl->head.prev = (BMHeader*)l;
497                         nl->head.next = (BMHeader*)(l->head.next);
498                         nl->head.prev->next = (BMHeader*)nl;
499                         nl->head.next->prev = (BMHeader*)nl;
500                         nl->v = nv;
501                         
502                         /*assign the correct edge to the correct loop*/
503                         if(bmesh_verts_in_edge(nl->v, ((BMLoop*)(nl->head.next))->v, e)){
504                                 nl->e = e;
505                                 l->e = ne;
506                                 
507                                 /*append l into ne's rad cycle*/
508                                 if(!radNEBase){
509                                         radNEBase = &(l->radial);
510                                         radNEBase->next = NULL;
511                                         radNEBase->prev = NULL;
512                                 }
513                                 
514                                 if(!radEBase){
515                                         radEBase = &(nl->radial);
516                                         radEBase->next = NULL;
517                                         radEBase->prev = NULL;
518                                 }
519                                 
520                                 bmesh_cycle_append(radEBase,&(nl->radial));
521                                 bmesh_cycle_append(radNEBase,&(l->radial));
522                                         
523                         }
524                         else if(bmesh_verts_in_edge(nl->v,((BMLoop*)(nl->head.next))->v,ne)){
525                                 nl->e = ne;
526                                 l->e = e;
527                                 
528                                 if(!radNEBase){
529                                         radNEBase = &(nl->radial);
530                                         radNEBase->next = NULL;
531                                         radNEBase->prev = NULL;
532                                 }
533                                 if(!radEBase){
534                                         radEBase = &(l->radial);
535                                         radEBase->next = NULL;
536                                         radEBase->prev = NULL;
537                                 }
538                                 bmesh_cycle_append(radEBase,&(l->radial));
539                                 bmesh_cycle_append(radNEBase,&(nl->radial));
540                         }
541                                         
542                 }
543                 
544                 e->loop = radEBase->data;
545                 ne->loop = radNEBase->data;
546                 
547                 /*verify length of radial cycle*/
548                 edok = bmesh_cycle_validate(radlen,&(e->loop->radial));
549                 if(!edok) bmesh_error();
550                 edok = bmesh_cycle_validate(radlen,&(ne->loop->radial));
551                 if(!edok) bmesh_error();
552                 
553                 /*verify loop->v and loop->next->v pointers for e*/
554                 for(i=0,l=e->loop; i < radlen; i++, l = l->radial.next->data){
555                         if(!(l->e == e)) bmesh_error();
556                         if(!(l->radial.data == l)) bmesh_error();
557                         if( ((BMLoop*)(l->head.prev))->e != ne && ((BMLoop*)(l->head.next))->e != ne) bmesh_error();
558                         edok = bmesh_verts_in_edge(l->v, ((BMLoop*)(l->head.next))->v, e);
559                         if(!edok) bmesh_error();
560                         if(l->v == ((BMLoop*)(l->head.next))->v) bmesh_error();
561                         if(l->e == ((BMLoop*)(l->head.next))->e) bmesh_error();
562                         /*verify loop cycle for kloop->f*/
563                         edok = bmesh_cycle_validate(l->f->len, l->f->loopbase);
564                         if(!edok) bmesh_error();
565                 }
566                 /*verify loop->v and loop->next->v pointers for ne*/
567                 for(i=0,l=ne->loop; i < radlen; i++, l = l->radial.next->data){
568                         if(!(l->e == ne)) bmesh_error();
569                         if(!(l->radial.data == l)) bmesh_error();
570                         if( ((BMLoop*)(l->head.prev))->e != e && ((BMLoop*)(l->head.next))->e != e) bmesh_error();
571                         edok = bmesh_verts_in_edge(l->v, ((BMLoop*)(l->head.next))->v, ne);
572                         if(!edok) bmesh_error();
573                         if(l->v == ((BMLoop*)(l->head.next))->v) bmesh_error();
574                         if(l->e == ((BMLoop*)(l->head.next))->e) bmesh_error();
575                         /*verify loop cycle for kloop->f. Redundant*/
576                         edok = bmesh_cycle_validate(l->f->len, l->f->loopbase);
577                         if(!edok) bmesh_error();
578                 }
579         }
580         
581         if(re) *re = ne;
582         return nv;
583 }
584
585 /**
586  *                      bmesh_SFME
587  *
588  *      SPLIT FACE MAKE EDGE:
589  *
590  *      Takes as input two vertices in a single face. An edge is created which divides the original face
591  *      into two distinct regions. One of the regions is assigned to the original face and it is closed off.
592  *      The second region has a new face assigned to it.
593  *
594  *      Examples:
595  *      
596  *     Before:               After:
597  *       ----------           ----------
598  *       |                |           |        | 
599  *       |        |           |   f1   |
600  *      v1   f1   v2          v1======v2
601  *       |        |           |   f2   |
602  *       |        |           |        |
603  *       ----------           ---------- 
604  *
605  *      Note that the input vertices can be part of the same edge. This will result in a two edged face.
606  *  This is desirable for advanced construction tools and particularly essential for edge bevel. Because
607  *  of this it is up to the caller to decide what to do with the extra edge.
608  *
609  *  Note that the tesselator abuses eflag2 while using this euler! (don't ever ever do this....)
610  *
611  *      Returns -
612  *  A BMFace pointer
613  */
614 BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, BMLoop **rl){
615
616         BMFace *f2;
617         BMLoop *v1loop = NULL, *v2loop = NULL, *curloop, *f1loop=NULL, *f2loop=NULL;
618         BMEdge *e;
619         int i, len, f1len, f2len;
620         
621         
622         /*verify that v1 and v2 are in face.*/
623         len = bmesh_cycle_length(f->loopbase);
624         for(i = 0, curloop = f->loopbase; i < len; i++, curloop = ((BMLoop*)(curloop->head.next)) ){
625                 if(curloop->v == v1) v1loop = curloop;
626                 else if(curloop->v == v2) v2loop = curloop;
627         }
628         
629         if(!v1loop || !v2loop) return NULL;
630         
631         /*allocate new edge between v1 and v2*/
632         e = bmesh_addedgelist(bm, v1, v2,NULL);
633         bmesh_disk_append_edge(e, v1);
634         bmesh_disk_append_edge(e, v2);
635         
636         f2 = bmesh_addpolylist(bm,f);
637         f1loop = bmesh_create_loop(bm,v2,e,f,v2loop);
638         f2loop = bmesh_create_loop(bm,v1,e,f2,v1loop);
639         
640         f1loop->head.prev = v2loop->head.prev;
641         f2loop->head.prev = v1loop->head.prev;
642         v2loop->head.prev->next = (BMHeader*)f1loop;
643         v1loop->head.prev->next = (BMHeader*)f2loop;
644         
645         f1loop->head.next = (BMHeader*)v1loop;
646         f2loop->head.next = (BMHeader*)v2loop;
647         v1loop->head.prev = (BMHeader*)f1loop;
648         v2loop->head.prev = (BMHeader*)f2loop;
649         
650         f2->loopbase = f2loop;
651         f->loopbase = f1loop;
652         
653         /*validate both loops*/
654         /*I dont know how many loops are supposed to be in each face at this point! FIXME!*/
655         
656         /*go through all of f2's loops and make sure they point to it properly.*/
657         f2len = bmesh_cycle_length(f2->loopbase);
658         for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = ((BMLoop*)(curloop->head.next)) ) curloop->f = f2;
659         
660         /*link up the new loops into the new edges radial*/
661         bmesh_radial_append(e, f1loop);
662         bmesh_radial_append(e, f2loop);
663         
664         
665         f2->len = f2len;
666         
667         f1len = bmesh_cycle_length(f->loopbase);
668         f->len = f1len;
669         
670         if(rl) *rl = f2loop;
671         return f2;
672 }
673
674
675 /**
676  *                      bmesh_JEKV
677  *
678  *      JOIN EDGE KILL VERT:
679  *      Takes a an edge and pointer to one of its vertices and collapses
680  *      the edge on that vertex.
681  *      
682  *      Before:    OE      KE
683  *               ------- -------
684  *               |     ||      |
685  *              OV     KV      TV
686  *
687  *
688  *   After:             OE      
689  *               ---------------
690  *               |             |
691  *              OV             TV
692  *
693  *
694  *      Restrictions:
695  *      KV is a vertex that must have a valance of exactly two. Furthermore
696  *  both edges in KV's disk cycle (OE and KE) must be unique (no double
697  *  edges).
698  *
699  *      It should also be noted that this euler has the possibility of creating
700  *      faces with just 2 edges. It is up to the caller to decide what to do with
701  *  these faces.
702  *
703  *  Returns -
704  *      1 for success, 0 for failure.
705  */
706 int bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv)
707 {
708         BMEdge *oe;
709         BMVert *ov, *tv;
710         BMNode *diskbase;
711         BMLoop *killoop,*nextl;
712         int len,radlen=0, halt = 0, i, valance1, valance2,edok;
713         
714         if(bmesh_vert_in_edge(ke,kv) == 0) return 0;
715         diskbase = bmesh_disk_getpointer(kv->edge, kv);
716         len = bmesh_cycle_length(diskbase);
717         
718         if(len == 2){
719                 oe = bmesh_disk_nextedge(ke, kv);
720                 tv = bmesh_edge_getothervert(ke, kv);
721                 ov = bmesh_edge_getothervert(oe, kv);           
722                 halt = bmesh_verts_in_edge(kv, tv, oe); //check for double edges
723                 
724                 if(halt) return 0;
725                 else{
726                         
727                         /*For verification later, count valance of ov and tv*/
728                         diskbase = bmesh_disk_getpointer(ov->edge, ov);
729                         valance1 = bmesh_cycle_length(diskbase);
730                         diskbase = bmesh_disk_getpointer(tv->edge, tv);
731                         valance2 = bmesh_cycle_length(diskbase);
732                         
733                         /*remove oe from kv's disk cycle*/
734                         bmesh_disk_remove_edge(oe,kv);
735                         /*relink oe->kv to be oe->tv*/
736                         bmesh_edge_swapverts(oe, kv, tv);
737                         /*append oe to tv's disk cycle*/
738                         bmesh_disk_append_edge(oe, tv);
739                         /*remove ke from tv's disk cycle*/
740                         bmesh_disk_remove_edge(ke, tv);
741                 
742                         
743
744                         /*deal with radial cycle of ke*/
745                         if(ke->loop){
746                                 /*first step, fix the neighboring loops of all loops in ke's radial cycle*/
747                                 radlen = bmesh_cycle_length(&(ke->loop->radial));
748                                 for(i=0,killoop = ke->loop; i<radlen; i++, killoop = bmesh_radial_nextloop(killoop)){
749                                         /*relink loops and fix vertex pointer*/
750                                         killoop->head.next->prev = killoop->head.prev;
751                                         killoop->head.prev->next = killoop->head.next;
752                                         if( ((BMLoop*)(killoop->head.next))->v == kv) ((BMLoop*)(killoop->head.next))->v = tv;
753                                         
754                                         /*fix len attribute of face*/
755                                         killoop->f->len--;
756                                         if(killoop->f->loopbase == killoop) killoop->f->loopbase = ((BMLoop*)(killoop->head.next));
757                                 }
758                                 /*second step, remove all the hanging loops attached to ke*/
759                                 killoop = ke->loop;
760                                 radlen = bmesh_cycle_length(&(ke->loop->radial));
761                                 /*make sure we have enough room in bm->lpar*/
762                                 if(bm->lparlen < radlen){
763                                         MEM_freeN(bm->lpar);
764                                         bm->lpar = MEM_callocN(sizeof(BMLoop *)* radlen, "BM Loop pointer array");
765                                         bm->lparlen = bm->lparlen * radlen;
766                                 }
767                                 /*this should be wrapped into a bme_free_radial function to be used by bmesh_KF as well...*/
768                                 i=0;
769                                 while(i<radlen){
770                                         bm->lpar[i] = killoop;
771                                         killoop = killoop->radial.next->data;
772                                         i++;
773                                 }
774                                 i=0;
775                                 while(i<radlen){
776                                         bmesh_free_loop(bm,bm->lpar[i]);
777                                         i++;
778                                 }
779                                 /*Validate radial cycle of oe*/
780                                 edok = bmesh_cycle_validate(radlen,&(oe->loop->radial));
781                                 
782                         }
783                         
784
785                         /*Validate disk cycles*/
786                         diskbase = bmesh_disk_getpointer(ov->edge,ov);
787                         edok = bmesh_cycle_validate(valance1, diskbase);
788                         if(!edok) bmesh_error();
789                         diskbase = bmesh_disk_getpointer(tv->edge,tv);
790                         edok = bmesh_cycle_validate(valance2, diskbase);
791                         if(!edok) bmesh_error();
792                         
793                         /*Validate loop cycle of all faces attached to oe*/
794                         for(i=0,nextl = oe->loop; i<radlen; i++, nextl = bmesh_radial_nextloop(nextl)){
795                                 edok = bmesh_cycle_validate(nextl->f->len,nextl->f->loopbase);
796                                 if(!edok) bmesh_error();
797                         }
798                         /*deallocate edge*/
799                         BLI_remlink(&(bm->edges), &(ke->head));
800                         bmesh_free_edge(bm, ke);
801                         /*deallocate vertex*/
802                         BLI_remlink(&(bm->verts), &(kv->head));
803                         bmesh_free_vert(bm, kv);        
804                         return 1;
805                 }
806         }
807         return 0;
808 }
809
810
811 /**
812  *                      bmesh_loop_reverse
813  *
814  *      FLIP FACE EULER
815  *
816  *      Changes the winding order of a face from CW to CCW or vice versa.
817  *      This euler is a bit peculiar in compairson to others as it is its
818  *      own inverse.
819  *
820  *      TODO: reinsert validation code.
821  *
822  *  Returns -
823  *      1 for success, 0 for failure.
824  */
825
826 int bmesh_loop_reverse(BMesh *bm, BMFace *f){
827         BMLoop *l = f->loopbase, *curloop, *oldprev, *oldnext;
828         int i, j, edok, len = 0;
829
830         len = bmesh_cycle_length(l);
831         if(bm->edarlen < len){
832                 MEM_freeN(bm->edar);
833                 bm->edar = MEM_callocN(sizeof(BMEdge *)* len, "BM Edge pointer array");
834                 bm->edarlen = len;
835         }
836         
837         for(i=0, curloop = l; i< len; i++, curloop= ((BMLoop*)(curloop->head.next)) ){
838                 curloop->e->head.eflag1 = 0;
839                 curloop->e->head.eflag2 = bmesh_cycle_length(&curloop->radial);
840                 bmesh_radial_remove_loop(curloop, curloop->e);
841                 /*in case of border edges we HAVE to zero out curloop->radial Next/Prev*/
842                 curloop->radial.next = curloop->radial.prev = NULL;
843                 bm->edar[i] = curloop->e;
844         }
845         
846         /*actually reverse the loop. This belongs in bmesh_cycle_reverse!*/
847         for(i=0, curloop = l; i < len; i++){
848                 oldnext = ((BMLoop*)(curloop->head.next));
849                 oldprev = ((BMLoop*)(curloop->head.prev));
850                 curloop->head.next = (BMHeader*)oldprev;
851                 curloop->head.prev = (BMHeader*)oldnext;
852                 curloop = oldnext;
853         }
854
855         if(len == 2){ //two edged face
856                 //do some verification here!
857                 l->e = bm->edar[1];
858                 ((BMLoop*)(l->head.next))->e = bm->edar[0];
859         }
860         else{
861                 for(i=0, curloop = l; i < len; i++, curloop = ((BMLoop*)(curloop->head.next)) ){
862                         edok = 0;
863                         for(j=0; j < len; j++){
864                                 edok = bmesh_verts_in_edge(curloop->v, ((BMLoop*)(curloop->head.next))->v, bm->edar[j]);
865                                 if(edok){
866                                         curloop->e = bm->edar[j];
867                                         break;
868                                 }
869                         }
870                 }
871         }
872         /*rebuild radial*/
873         for(i=0, curloop = l; i < len; i++, curloop = ((BMLoop*)(curloop->head.next)) ) bmesh_radial_append(curloop->e, curloop);
874         
875         /*validate radial*/
876         for(i=0, curloop = l; i < len; i++, curloop = ((BMLoop*)(curloop->head.next)) ){
877                 edok = bmesh_cycle_validate(curloop->e->head.eflag2, &(curloop->radial));
878                 if(!edok){
879                         bmesh_error();
880                 }
881         }
882         return 1;
883 }
884
885 /**
886  *                      bmesh_JFKE
887  *
888  *      JOIN FACE KILL EDGE:
889  *      
890  *      Takes two faces joined by a single 2-manifold edge and fuses them togather.
891  *      The edge shared by the faces must not be connected to any other edges which have
892  *      Both faces in its radial cycle
893  *
894  *      Examples:
895  *      
896  *        A                   B
897  *       ----------           ----------
898  *       |                |           |        | 
899  *       |   f1   |           |   f1   |
900  *      v1========v2 = Ok!    v1==V2==v3 == Wrong!
901  *       |   f2   |           |   f2   |
902  *       |        |           |        |
903  *       ----------           ---------- 
904  *
905  *      In the example A, faces f1 and f2 are joined by a single edge, and the euler can safely be used.
906  *      In example B however, f1 and f2 are joined by multiple edges and will produce an error. The caller
907  *      in this case should call bmesh_JEKV on the extra edges before attempting to fuse f1 and f2.
908  *
909  *      Also note that the order of arguments decides whether or not certain per-face attributes are present
910  *      in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited
911  *      from f1, not f2.
912  *
913  *  Returns -
914  *      A BMFace pointer
915 */
916
917 //disregarding f1loop and f2loop, if a vertex appears in a joined face more than once, we cancel
918
919 BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e)
920 {
921         
922         BMLoop *curloop, *f1loop=NULL, *f2loop=NULL;
923         int loopok = 0, newlen = 0,i, f1len=0, f2len=0, radlen=0, edok, shared;
924         
925         if(f1 == f2) return NULL; //can't join a face to itself
926         /*verify that e is in both f1 and f2*/
927         f1len = bmesh_cycle_length(f1->loopbase);
928         f2len = bmesh_cycle_length(f2->loopbase);
929         for(i=0, curloop = f1->loopbase; i < f1len; i++, curloop = ((BMLoop*)(curloop->head.next)) ){
930                 if(curloop->e == e){ 
931                         f1loop = curloop;
932                         break;
933                 }
934         }
935         for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = ((BMLoop*)(curloop->head.next)) ){
936                 if(curloop->e==e){
937                         f2loop = curloop;
938                         break;
939                 }
940         }
941         if(!(f1loop && f2loop)) return NULL;
942         
943         /*validate that edge is 2-manifold edge*/
944         radlen = bmesh_cycle_length(&(f1loop->radial));
945         if(radlen != 2) return NULL;
946
947         /*validate direction of f2's loop cycle is compatible.*/
948         if(f1loop->v == f2loop->v) return NULL;
949         
950         /*
951                 validate that for each face, each vertex has another edge in its disk cycle that is 
952                 not e, and not shared.
953         */
954         if(bmesh_radial_find_face( ((BMLoop*)(f1loop->head.next))->e,f2)) return NULL;
955         if(bmesh_radial_find_face( ((BMLoop*)(f1loop->head.prev))->e,f2)) return NULL;
956         if(bmesh_radial_find_face( ((BMLoop*)(f2loop->head.next))->e,f1)) return NULL;
957         if(bmesh_radial_find_face( ((BMLoop*)(f2loop->head.prev))->e,f1)) return NULL;
958         
959         /*validate only one shared edge*/
960         shared = BM_Face_Sharededges(f1,f2);
961         if(shared > 1) return NULL;
962
963         /*validate no internal joins*/
964         for(i=0, curloop = f1->loopbase; i < f1len; i++, curloop = ((BMLoop*)(curloop->head.next)) ) curloop->v->head.eflag1 = 0;
965         for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = ((BMLoop*)(curloop->head.next)) ) curloop->v->head.eflag1 = 0;
966
967         for(i=0, curloop = f1->loopbase; i < f1len; i++, curloop = ((BMLoop*)(curloop->head.next)) ){
968                 if(curloop != f1loop)
969                         curloop->v->head.eflag1++;
970         }
971         for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = ((BMLoop*)(curloop->head.next)) ){
972                 if(curloop != f2loop)
973                         curloop->v->head.eflag1++;
974         }
975
976         for(i=0, curloop = f1->loopbase; i < f1len; i++, curloop = ((BMLoop*)(curloop->head.next)) ){
977                 if(curloop->v->head.eflag1 > 1)
978                         return NULL;
979         }
980         
981         for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = ((BMLoop*)(curloop->head.next)) ){
982                 if(curloop->v->head.eflag1 > 1)
983                         return NULL;
984         }
985
986         /*join the two loops*/
987         f1loop->head.prev->next = f2loop->head.next;
988         f2loop->head.next->prev = f1loop->head.prev;
989         
990         f1loop->head.next->prev = f2loop->head.prev;
991         f2loop->head.prev->next = f1loop->head.next;
992         
993         /*if f1loop was baseloop, give f1loop->next the base.*/
994         if(f1->loopbase == f1loop) f1->loopbase = ((BMLoop*)(f1loop->head.next));
995         
996         /*validate the new loop*/
997         loopok = bmesh_cycle_validate((f1len+f2len)-2, f1->loopbase);
998         if(!loopok) bmesh_error();
999         
1000         /*make sure each loop points to the proper face*/
1001         newlen = bmesh_cycle_length(f1->loopbase);
1002         for(i = 0, curloop = f1->loopbase; i < newlen; i++, curloop = ((BMLoop*)(curloop->head.next)) ) curloop->f = f1;
1003         
1004         f1->len = newlen;
1005         
1006         edok = bmesh_cycle_validate(f1->len, f1->loopbase);
1007         if(!edok) bmesh_error();
1008         
1009         /*remove edge from the disk cycle of its two vertices.*/
1010         bmesh_disk_remove_edge(f1loop->e, f1loop->e->v1);
1011         bmesh_disk_remove_edge(f1loop->e, f1loop->e->v2);
1012         
1013         /*deallocate edge and its two loops as well as f2*/
1014         BLI_remlink(&(bm->edges), &(f1loop->e->head));
1015         BLI_remlink(&(bm->polys), &(f2->head));
1016         bmesh_free_edge(bm, f1loop->e);
1017         bmesh_free_loop(bm, f1loop);
1018         bmesh_free_loop(bm, f2loop);
1019         bmesh_free_poly(bm, f2);        
1020         return f1;
1021 }
1022
1023 /**
1024 *    bmesh_URMV
1025 *
1026 *    UNGLUE REGION MAKE VERT:
1027 *
1028 *    Takes a locally manifold disk of face corners and 'unglues' it
1029 *    creating a new vertex
1030 *
1031 **/
1032
1033 #define URMV_VISIT    1
1034 #define URMV_VISIT2   2
1035
1036 BMVert *bmesh_urmv(BMesh *bm, BMFace *sf, BMVert *sv)
1037 {
1038     BMVert *nv = NULL;
1039     BMLoop *l = NULL, *sl = NULL;
1040     BMEdge *curedge = NULL;
1041     int numloops = 0, numedges = 0, i, maxedges, maxloops;
1042
1043
1044     /*Todo: Validation*/
1045     /*validate radial cycle of all collected loops*/
1046     /*validate the disk cycle of sv, and nv*/
1047     /*validate the face length of all faces? overkill?*/
1048     /*validate the l->e pointers of all affected faces, ie: l->v and l->next->v should be equivalent to l->e*/
1049    
1050     /*verify that sv has edges*/
1051     if(sv->edge == NULL)
1052         return NULL;
1053    
1054     /*first verify no wire edges on sv*/
1055     curedge = sv->edge;
1056     do{
1057         if(curedge->loop == NULL)
1058             return NULL;
1059         curedge = bmesh_disk_nextedge(curedge, sv);
1060     }while(curedge != sv->edge);
1061    
1062     /*next verify that sv is in sf*/
1063     l = sf->loopbase;
1064     do{
1065         if(l->v == sv){
1066             sl = l;
1067             break;
1068         }
1069         l = (BMLoop*)(l->head.next);
1070     }while(l != sf->loopbase);
1071    
1072     if(sl == NULL)
1073         return NULL;
1074    
1075     /*clear euler flags*/
1076     sv->head.eflag1 = 0;
1077    
1078     curedge = sv->edge;
1079     do{
1080         curedge->head.eflag1 = 0;
1081         l = curedge->loop;
1082         do{
1083             l->head.eflag1 = 0;
1084             l->f->head.eflag1 = 0;
1085             l = bmesh_radial_nextloop(l);
1086         }while(l != curedge->loop);
1087         curedge = bmesh_disk_nextedge(curedge, sv);
1088     }while(curedge != sv->edge);
1089    
1090     /*search through face disk and flag elements as we go.*/
1091     /*Note, test this to make sure that it works correct on
1092     non-manifold faces!
1093     */
1094     l = sl;
1095     l->e->head.eflag1 |= URMV_VISIT;
1096     l->f->head.eflag1 |= URMV_VISIT;
1097     do{
1098         if(l->v == sv)
1099             l = bmesh_radial_nextloop((BMLoop*)(l->head.prev));
1100         else
1101             l = bmesh_radial_nextloop((BMLoop*)(l->head.next));
1102         l->e->head.eflag1 |= URMV_VISIT;
1103         l->f->head.eflag1 |= URMV_VISIT;
1104     }while(l != sl && (bmesh_cycle_length(&(l->radial)) > 1) );
1105    
1106     /*Verify that all visited edges are at least 1 or 2 manifold*/
1107     curedge = sv->edge;
1108     do{
1109         if(curedge->head.eflag1 && (bmesh_cycle_length(&(curedge->loop->radial)) > 2) )
1110             return NULL;
1111         curedge = bmesh_disk_nextedge(curedge, sv);
1112     }while(curedge != sv->edge);
1113
1114         /*allocate temp storage - we overallocate here instead of trying to be clever*/
1115         maxedges = 0;
1116         maxloops = 0;
1117         curedge = sv->edge;
1118         do{
1119                 if(curedge->loop){
1120                         l = curedge->loop;
1121                         do{
1122                                 maxloops += l->f->len;
1123                                 l = bmesh_radial_nextloop(l);
1124                         }while(l != curedge->loop);
1125                 }
1126                 maxedges+= 1;
1127                 curedge = bmesh_disk_nextedge(curedge,sv);
1128         }while(curedge != sv->edge);
1129
1130         if(bm->edarlen < maxedges){
1131                 MEM_freeN(bm->edar);
1132                 bm->edar = MEM_callocN(sizeof(BMEdge *) * maxedges, "BM Edge pointer array");
1133                 bm->edarlen = maxedges;
1134         }
1135         if(bm->lparlen < maxloops){
1136                 MEM_freeN(bm->lpar);
1137                 bm->lpar = MEM_callocN(sizeof(BMLoop *) * maxloops, "BM Loop pointer array");
1138                 bm->lparlen = maxloops;
1139         }
1140
1141     /*first get loops by looping around edges and loops around that edges faces*/
1142     curedge = sv->edge;
1143     do{
1144         if(curedge->loop){
1145             l = curedge->loop;
1146             do{
1147                 if( (l->head.eflag1 & URMV_VISIT) && (!(l->head.eflag1 & URMV_VISIT2)) ){
1148                     bm->lpar[numloops] = l;
1149                     l->head.eflag1 |= URMV_VISIT2;
1150                     numloops++;
1151                 }
1152                 l = bmesh_radial_nextloop(l);
1153             }while(l != curedge->loop);
1154         }
1155         curedge = bmesh_disk_nextedge(curedge, sv);
1156     }while(curedge != sv->edge);
1157
1158     /*now collect edges by looping around edges and looking at visited flags*/
1159     curedge = sv->edge;
1160     do{
1161         if(curedge->head.eflag1 & URMV_VISIT){
1162             bm->edar[numedges] = curedge;
1163             numedges++;
1164         }
1165         curedge = bmesh_disk_nextedge(curedge, sv);
1166     }while(curedge != sv->edge);
1167    
1168     /*make new vertex*/
1169     nv = bmesh_addvertlist(bm, sv);
1170    
1171     /*go through and relink edges*/
1172     for(i = 0;  i <  numedges; i++){
1173         curedge = bm->edar[i];
1174         /*remove curedge from sv*/
1175         bmesh_disk_remove_edge(curedge, sv);
1176         /*swap out sv for nv in curedge*/
1177         bmesh_edge_swapverts(curedge, sv, nv);
1178         /*add curedge to nv's disk cycle*/
1179         bmesh_disk_append_edge(curedge, nv);
1180     }
1181    
1182     /*go through and relink loops*/
1183     for(i = 0; i < numloops; i ++){
1184         l = bm->lpar[i];
1185         if(l->v == sv)
1186             l->v = nv;
1187         }
1188         return nv;
1189 }