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