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