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