Two fixes;
[blender.git] / source / blender / src / editmesh_tools.c
1 /**
2  * $Id: 
3  *
4  * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2004 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  */
32
33 /*
34
35 editmesh_tool.c: UI called tools for editmesh, geometry changes here, otherwise in mods.c
36
37 */
38
39 #include <stdlib.h>
40 #include <string.h>
41 #include <math.h>
42
43 #ifdef HAVE_CONFIG_H
44 #include <config.h>
45 #endif
46
47 #ifdef WIN32
48 #include "BLI_winstuff.h"
49 #endif
50 #include "MEM_guardedalloc.h"
51
52
53 #include "DNA_mesh_types.h"
54 #include "DNA_material_types.h"
55 #include "DNA_meshdata_types.h"
56 #include "DNA_object_types.h"
57 #include "DNA_scene_types.h"
58 #include "DNA_screen_types.h"
59 #include "DNA_view3d_types.h"
60
61 #include "BLI_blenlib.h"
62 #include "BLI_arithb.h"
63 #include "BLI_editVert.h"
64 #include "BLI_rand.h"
65
66 #include "BKE_displist.h"
67 #include "BKE_global.h"
68 #include "BKE_library.h"
69 #include "BKE_mesh.h"
70 #include "BKE_object.h"
71 #include "BKE_utildefines.h"
72
73 #include "BIF_cursors.h"
74 #include "BIF_editmesh.h"
75 #include "BIF_gl.h"
76 #include "BIF_graphics.h"
77 #include "BIF_interface.h"
78 #include "BIF_mywindow.h"
79 #include "BIF_screen.h"
80 #include "BIF_space.h"
81 #include "BIF_resources.h"
82 #include "BIF_toolbox.h"
83
84 #include "BDR_drawobject.h"
85 #include "BDR_editobject.h"
86
87 #include "BSE_view.h"
88 #include "BSE_edit.h"
89
90 #include "mydevice.h"
91 #include "blendef.h"
92
93 #include "editmesh.h"
94
95
96 /********* qsort routines *********/
97
98
99 struct xvertsort {
100         float x;
101         EditVert *v1;
102 };
103
104 static int vergxco(const void *v1, const void *v2)
105 {
106         const struct xvertsort *x1=v1, *x2=v2;
107
108         if( x1->x > x2->x ) return 1;
109         else if( x1->x < x2->x) return -1;
110         return 0;
111 }
112
113 struct facesort {
114         long x;
115         struct EditFace *efa;
116 };
117
118
119 static int vergface(const void *v1, const void *v2)
120 {
121         const struct facesort *x1=v1, *x2=v2;
122         
123         if( x1->x > x2->x ) return 1;
124         else if( x1->x < x2->x) return -1;
125         return 0;
126 }
127
128
129 /* *********************************** */
130
131 void convert_to_triface(int all)
132 {
133         EditMesh *em = G.editMesh;
134         EditFace *efa, *efan, *next;
135         
136         efa= em->faces.last;
137         while(efa) {
138                 next= efa->prev;
139                 if(efa->v4) {
140                         if(all || (efa->f & SELECT) ) {
141                                 
142                                 efan= addfacelist(efa->v1, efa->v2, efa->v3, 0, efa, NULL);
143                                 if(efa->f & SELECT) EM_select_face(efan, 1);
144                                 efan= addfacelist(efa->v1, efa->v3, efa->v4, 0, efa, NULL);
145                                 if(efa->f & SELECT) EM_select_face(efan, 1);
146
147                                 efan->tf.uv[1][0]= efan->tf.uv[2][0];
148                                 efan->tf.uv[1][1]= efan->tf.uv[2][1];
149                                 efan->tf.uv[2][0]= efan->tf.uv[3][0];
150                                 efan->tf.uv[2][1]= efan->tf.uv[3][1];
151                                 
152                                 efan->tf.col[1]= efan->tf.col[2];
153                                 efan->tf.col[2]= efan->tf.col[3];
154                                 
155                                 BLI_remlink(&em->faces, efa);
156                                 free_editface(efa);
157                         }
158                 }
159                 efa= next;
160         }
161         
162         EM_fgon_flags();        // redo flags and indices for fgons
163         BIF_undo_push("Convert Quads to Triangles");
164         
165 }
166
167
168 short removedoublesflag(short flag, float limit)                /* return amount */
169 {
170         EditMesh *em = G.editMesh;
171         /* all verts with (flag & 'flag') are being evaluated */
172         EditVert *eve, *v1, *nextve;
173         EditEdge *eed, *e1, *nexted;
174         EditFace *efa, *nextvl;
175         struct xvertsort *sortblock, *sb, *sb1;
176         struct facesort *vlsortblock, *vsb, *vsb1;
177         float dist;
178         int a, b, test, amount;
179
180         /* flag 128 is cleared, count */
181         eve= em->verts.first;
182         amount= 0;
183         while(eve) {
184                 eve->f &= ~128;
185                 if(eve->f & flag) amount++;
186                 eve= eve->next;
187         }
188         if(amount==0) return 0;
189
190         /* allocate memory and qsort */
191         sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*amount,"sortremovedoub");
192         eve= em->verts.first;
193         while(eve) {
194                 if(eve->f & flag) {
195                         sb->x= eve->co[0]+eve->co[1]+eve->co[2];
196                         sb->v1= eve;
197                         sb++;
198                 }
199                 eve= eve->next;
200         }
201         qsort(sortblock, amount, sizeof(struct xvertsort), vergxco);
202
203         /* test for doubles */
204         sb= sortblock;
205         for(a=0; a<amount; a++) {
206                 eve= sb->v1;
207                 if( (eve->f & 128)==0 ) {
208                         sb1= sb+1;
209                         for(b=a+1; b<amount; b++) {
210                                 /* first test: simpel dist */
211                                 dist= sb1->x - sb->x;
212                                 if(dist > limit) break;
213                                 
214                                 /* second test: is vertex allowed */
215                                 v1= sb1->v1;
216                                 if( (v1->f & 128)==0 ) {
217                                         
218                                         dist= fabs(v1->co[0]-eve->co[0]);
219                                         if(dist<=limit) {
220                                                 dist= fabs(v1->co[1]-eve->co[1]);
221                                                 if(dist<=limit) {
222                                                         dist= fabs(v1->co[2]-eve->co[2]);
223                                                         if(dist<=limit) {
224                                                                 v1->f|= 128;
225                                                                 v1->vn= eve;
226                                                         }
227                                                 }
228                                         }
229                                 }
230                                 sb1++;
231                         }
232                 }
233                 sb++;
234         }
235         MEM_freeN(sortblock);
236
237         /* test edges and insert again */
238         eed= em->edges.first;
239         while(eed) {
240                 eed->f2= 0;
241                 eed= eed->next;
242         }
243         eed= em->edges.last;
244         while(eed) {
245                 nexted= eed->prev;
246
247                 if(eed->f2==0) {
248                         if( (eed->v1->f & 128) || (eed->v2->f & 128) ) {
249                                 remedge(eed);
250
251                                 if(eed->v1->f & 128) eed->v1= eed->v1->vn;
252                                 if(eed->v2->f & 128) eed->v2= eed->v2->vn;
253                                 e1= addedgelist(eed->v1, eed->v2, eed);
254                                 
255                                 if(e1) e1->f2= 1;
256                                 if(e1!=eed) free_editedge(eed);
257                         }
258                 }
259                 eed= nexted;
260         }
261
262         /* first count amount of test faces */
263         efa= (struct EditFace *)em->faces.first;
264         amount= 0;
265         while(efa) {
266                 efa->f1= 0;
267                 if(efa->v1->f & 128) efa->f1= 1;
268                 else if(efa->v2->f & 128) efa->f1= 1;
269                 else if(efa->v3->f & 128) efa->f1= 1;
270                 else if(efa->v4 && (efa->v4->f & 128)) efa->f1= 1;
271                 
272                 if(efa->f1==1) amount++;
273                 efa= efa->next;
274         }
275
276         /* test faces for double vertices, and if needed remove them */
277         efa= (struct EditFace *)em->faces.first;
278         while(efa) {
279                 nextvl= efa->next;
280                 if(efa->f1==1) {
281                         
282                         if(efa->v1->f & 128) efa->v1= efa->v1->vn;
283                         if(efa->v2->f & 128) efa->v2= efa->v2->vn;
284                         if(efa->v3->f & 128) efa->v3= efa->v3->vn;
285                         if(efa->v4 && (efa->v4->f & 128)) efa->v4= efa->v4->vn;
286                 
287                         test= 0;
288                         if(efa->v1==efa->v2) test+=1;
289                         if(efa->v2==efa->v3) test+=2;
290                         if(efa->v3==efa->v1) test+=4;
291                         if(efa->v4==efa->v1) test+=8;
292                         if(efa->v3==efa->v4) test+=16;
293                         if(efa->v2==efa->v4) test+=32;
294                         
295                         if(test) {
296                                 if(efa->v4) {
297                                         if(test==1 || test==2) {
298                                                 efa->v2= efa->v3;
299                                                 efa->v3= efa->v4;
300                                                 efa->v4= 0;
301                                                 test= 0;
302                                         }
303                                         else if(test==8 || test==16) {
304                                                 efa->v4= 0;
305                                                 test= 0;
306                                         }
307                                         else {
308                                                 BLI_remlink(&em->faces, efa);
309                                                 free_editface(efa);
310                                                 amount--;
311                                         }
312                                 }
313                                 else {
314                                         BLI_remlink(&em->faces, efa);
315                                         free_editface(efa);
316                                         amount--;
317                                 }
318                         }
319                         
320                         if(test==0) {
321                                 /* set edge pointers */
322                                 efa->e1= findedgelist(efa->v1, efa->v2);
323                                 efa->e2= findedgelist(efa->v2, efa->v3);
324                                 if(efa->v4==0) {
325                                         efa->e3= findedgelist(efa->v3, efa->v1);
326                                         efa->e4= 0;
327                                 }
328                                 else {
329                                         efa->e3= findedgelist(efa->v3, efa->v4);
330                                         efa->e4= findedgelist(efa->v4, efa->v1);
331                                 }
332                         }
333                 }
334                 efa= nextvl;
335         }
336
337         /* double faces: sort block */
338         /* count again, now all selected faces */
339         amount= 0;
340         efa= em->faces.first;
341         while(efa) {
342                 efa->f1= 0;
343                 if(faceselectedAND(efa, 1)) {
344                         efa->f1= 1;
345                         amount++;
346                 }
347                 efa= efa->next;
348         }
349
350         if(amount) {
351                 /* double faces: sort block */
352                 vsb= vlsortblock= MEM_mallocN(sizeof(struct facesort)*amount, "sortremovedoub");
353                 efa= em->faces.first;
354                 while(efa) {
355                         if(efa->f1 & 1) {
356                                 if(efa->v4) vsb->x= (long) MIN4( (long)efa->v1, (long)efa->v2, (long)efa->v3, (long)efa->v4);
357                                 else vsb->x= (long) MIN3( (long)efa->v1, (long)efa->v2, (long)efa->v3);
358
359                                 vsb->efa= efa;
360                                 vsb++;
361                         }
362                         efa= efa->next;
363                 }
364                 
365                 qsort(vlsortblock, amount, sizeof(struct facesort), vergface);
366                         
367                 vsb= vlsortblock;
368                 for(a=0; a<amount; a++) {
369                         efa= vsb->efa;
370                         if( (efa->f1 & 128)==0 ) {
371                                 vsb1= vsb+1;
372
373                                 for(b=a+1; b<amount; b++) {
374                                 
375                                         /* first test: same pointer? */
376                                         if(vsb->x != vsb1->x) break;
377                                         
378                                         /* second test: is test permitted? */
379                                         efa= vsb1->efa;
380                                         if( (efa->f1 & 128)==0 ) {
381                                                 if( compareface(efa, vsb->efa)) efa->f1 |= 128;
382                                                 
383                                         }
384                                         vsb1++;
385                                 }
386                         }
387                         vsb++;
388                 }
389                 
390                 MEM_freeN(vlsortblock);
391                 
392                 /* remove double faces */
393                 efa= (struct EditFace *)em->faces.first;
394                 while(efa) {
395                         nextvl= efa->next;
396                         if(efa->f1 & 128) {
397                                 BLI_remlink(&em->faces, efa);
398                                 free_editface(efa);
399                         }
400                         efa= nextvl;
401                 }
402         }
403         
404         /* remove double vertices */
405         a= 0;
406         eve= (struct EditVert *)em->verts.first;
407         while(eve) {
408                 nextve= eve->next;
409                 if(eve->f & flag) {
410                         if(eve->f & 128) {
411                                 a++;
412                                 BLI_remlink(&em->verts, eve);
413                                 free_editvert(eve);
414                         }
415                 }
416                 eve= nextve;
417         }
418
419         return a;       /* amount */
420 }
421
422 /* called from buttons */
423 void xsortvert_flag(int flag)
424 {
425         EditMesh *em = G.editMesh;
426         /* all verts with (flag & 'flag') are sorted */
427         EditVert *eve;
428         struct xvertsort *sortblock, *sb;
429         ListBase tbase;
430         int amount;
431         
432         /* count */
433         eve= em->verts.first;
434         amount= 0;
435         while(eve) {
436                 if(eve->f & flag) amount++;
437                 eve= eve->next;
438         }
439         if(amount==0) return;
440
441         /* allocate memory and sort */
442         sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*amount,"sortremovedoub");
443         eve= em->verts.first;
444         while(eve) {
445                 if(eve->f & flag) {
446                         sb->x= eve->xs;
447                         sb->v1= eve;
448                         sb++;
449                 }
450                 eve= eve->next;
451         }
452         qsort(sortblock, amount, sizeof(struct xvertsort), vergxco);
453         
454         /* make temporal listbase */
455         tbase.first= tbase.last= 0;
456         sb= sortblock;
457         while(amount--) {
458                 eve= sb->v1;
459                 BLI_remlink(&em->verts, eve);
460                 BLI_addtail(&tbase, eve);
461                 sb++;
462         }
463         
464         addlisttolist(&em->verts, &tbase);
465         
466         MEM_freeN(sortblock);
467         BIF_undo_push("Xsort");
468         
469 }
470
471 /* called from buttons */
472 void hashvert_flag(int flag)
473 {
474         /* switch vertex order using hash table */
475         EditMesh *em = G.editMesh;
476         EditVert *eve;
477         struct xvertsort *sortblock, *sb, onth, *newsort;
478         ListBase tbase;
479         int amount, a, b;
480         
481         /* count */
482         eve= em->verts.first;
483         amount= 0;
484         while(eve) {
485                 if(eve->f & flag) amount++;
486                 eve= eve->next;
487         }
488         if(amount==0) return;
489         
490         /* allocate memory */
491         sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*amount,"sortremovedoub");
492         eve= em->verts.first;
493         while(eve) {
494                 if(eve->f & flag) {
495                         sb->v1= eve;
496                         sb++;
497                 }
498                 eve= eve->next;
499         }
500
501         BLI_srand(1);
502         
503         sb= sortblock;
504         for(a=0; a<amount; a++, sb++) {
505                 b= amount*BLI_drand();
506                 if(b>=0 && b<amount) {
507                         newsort= sortblock+b;
508                         onth= *sb;
509                         *sb= *newsort;
510                         *newsort= onth;
511                 }
512         }
513
514         /* make temporal listbase */
515         tbase.first= tbase.last= 0;
516         sb= sortblock;
517         while(amount--) {
518                 eve= sb->v1;
519                 BLI_remlink(&em->verts, eve);
520                 BLI_addtail(&tbase, eve);
521                 sb++;
522         }
523         
524         addlisttolist(&em->verts, &tbase);
525         
526         MEM_freeN(sortblock);
527         BIF_undo_push("Hash");
528
529 }
530
531 void extrude_mesh(void)
532 {
533         short nr, xmode= 0;
534
535         TEST_EDITMESH
536         
537         if(G.scene->selectmode & SCE_SELECT_VERTEX)
538                 nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3|Only Vertices%x4");
539         else if(G.scene->selectmode & SCE_SELECT_EDGE)
540                 nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3");
541         else
542                 nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2");
543                 
544         if(nr<1) return;
545
546         if(nr==1)  xmode= extrudeflag(SELECT);
547         else if(nr==4) xmode= extrudeflag_verts_indiv(SELECT);
548         else if(nr==3) xmode= extrudeflag_edges_indiv(SELECT);
549         else xmode= extrudeflag_face_indiv(SELECT);
550         
551         if(xmode==0) {
552                 error("No valid selection");
553         }
554         else {
555                 EM_fgon_flags();
556                 countall(); 
557                 transform(xmode);
558         }
559
560 }
561
562 void split_mesh(void)
563 {
564
565         TEST_EDITMESH
566
567         if(okee(" Split ")==0) return;
568
569         waitcursor(1);
570
571         /* make duplicate first */
572         adduplicateflag(SELECT);
573         /* old faces have flag 128 set, delete them */
574         delfaceflag(128);
575
576         waitcursor(0);
577
578         countall();
579         allqueue(REDRAWVIEW3D, 0);
580         makeDispList(G.obedit);
581         BIF_undo_push("Hash");
582
583 }
584
585 void extrude_repeat_mesh(int steps, float offs)
586 {
587         float dvec[3], tmat[3][3], bmat[3][3];
588         short a,ok;
589
590         TEST_EDITMESH
591         waitcursor(1);
592         
593         /* dvec */
594         dvec[0]= G.vd->persinv[2][0];
595         dvec[1]= G.vd->persinv[2][1];
596         dvec[2]= G.vd->persinv[2][2];
597         Normalise(dvec);
598         dvec[0]*= offs;
599         dvec[1]*= offs;
600         dvec[2]*= offs;
601
602         /* base correction */
603         Mat3CpyMat4(bmat, G.obedit->obmat);
604         Mat3Inv(tmat, bmat);
605         Mat3MulVecfl(tmat, dvec);
606
607         for(a=0;a<steps;a++) {
608                 ok= extrudeflag(SELECT);
609                 if(ok==0) {
610                         error("No valid vertices are selected");
611                         break;
612                 }
613                 translateflag(SELECT, dvec);
614         }
615         
616         EM_fgon_flags();
617         countall();
618         allqueue(REDRAWVIEW3D, 0);
619         makeDispList(G.obedit);
620         waitcursor(0);
621         BIF_undo_push("Extrude Repeat");
622
623 }
624
625 void spin_mesh(int steps,int degr,float *dvec, int mode)
626 {
627         extern short editbutflag;
628         EditMesh *em = G.editMesh;
629         EditVert *eve,*nextve;
630         float *curs, si,n[3],q[4],cmat[3][3],imat[3][3], tmat[3][3];
631         float cent[3],bmat[3][3];
632         float phi;
633         short a,ok;
634
635         TEST_EDITMESH
636         
637         waitcursor(1);
638         
639         /* imat and centre and size */
640         Mat3CpyMat4(bmat, G.obedit->obmat);
641         Mat3Inv(imat,bmat);
642
643         curs= give_cursor();
644         VECCOPY(cent, curs);
645         cent[0]-= G.obedit->obmat[3][0];
646         cent[1]-= G.obedit->obmat[3][1];
647         cent[2]-= G.obedit->obmat[3][2];
648         Mat3MulVecfl(imat, cent);
649
650         phi= degr*M_PI/360.0;
651         phi/= steps;
652         if(editbutflag & B_CLOCKWISE) phi= -phi;
653
654         if(dvec) {
655                 n[0]=n[1]= 0.0;
656                 n[2]= 1.0;
657         } else {
658                 n[0]= G.vd->viewinv[2][0];
659                 n[1]= G.vd->viewinv[2][1];
660                 n[2]= G.vd->viewinv[2][2];
661                 Normalise(n);
662         }
663
664         q[0]= cos(phi);
665         si= sin(phi);
666         q[1]= n[0]*si;
667         q[2]= n[1]*si;
668         q[3]= n[2]*si;
669         QuatToMat3(q, cmat);
670
671         Mat3MulMat3(tmat,cmat,bmat);
672         Mat3MulMat3(bmat,imat,tmat);
673
674         if(mode==0) if(editbutflag & B_KEEPORIG) adduplicateflag(1);
675         ok= 1;
676
677         for(a=0;a<steps;a++) {
678                 if(mode==0) ok= extrudeflag(SELECT);
679                 else adduplicateflag(SELECT);
680                 if(ok==0) {
681                         error("No valid vertices are selected");
682                         break;
683                 }
684                 rotateflag(SELECT, cent, bmat);
685                 if(dvec) {
686                         Mat3MulVecfl(bmat,dvec);
687                         translateflag(SELECT, dvec);
688                 }
689         }
690
691         waitcursor(0);
692         if(ok==0) {
693                 /* no vertices or only loose ones selected, remove duplicates */
694                 eve= em->verts.first;
695                 while(eve) {
696                         nextve= eve->next;
697                         if(eve->f & SELECT) {
698                                 BLI_remlink(&em->verts,eve);
699                                 free_editvert(eve);
700                         }
701                         eve= nextve;
702                 }
703         }
704         
705         EM_fgon_flags();
706         countall();
707         recalc_editnormals();
708         allqueue(REDRAWVIEW3D, 0);
709         makeDispList(G.obedit);
710         
711         if(dvec==NULL) BIF_undo_push("Spin");
712 }
713
714 void screw_mesh(int steps,int turns)
715 {
716         EditMesh *em = G.editMesh;
717         EditVert *eve,*v1=0,*v2=0;
718         EditEdge *eed;
719         float dvec[3], nor[3];
720
721         TEST_EDITMESH
722
723         /* first condition: we need frontview! */
724         if(G.vd->view!=1) {
725                 error("Must be in Front View");
726                 return;
727         }
728         
729         /* clear flags */
730         eve= em->verts.first;
731         while(eve) {
732                 eve->f1= 0;
733                 eve= eve->next;
734         }
735         /* edges set flags in verts */
736         eed= em->edges.first;
737         while(eed) {
738                 if(eed->v1->f & SELECT) {
739                         if(eed->v2->f & SELECT) {
740                                 /* watch: f1 is a byte */
741                                 if(eed->v1->f1<2) eed->v1->f1++;
742                                 if(eed->v2->f1<2) eed->v2->f1++;
743                         }
744                 }
745                 eed= eed->next;
746         }
747         /* find two vertices with eve->f1==1, more or less is wrong */
748         eve= em->verts.first;
749         while(eve) {
750                 if(eve->f1==1) {
751                         if(v1==0) v1= eve;
752                         else if(v2==0) v2= eve;
753                         else {
754                                 v1=0;
755                                 break;
756                         }
757                 }
758                 eve= eve->next;
759         }
760         if(v1==0 || v2==0) {
761                 error("No curve is selected");
762                 return;
763         }
764
765         /* calculate dvec */
766         dvec[0]= ( (v1->co[0]- v2->co[0]) )/(steps);
767         dvec[1]= ( (v1->co[1]- v2->co[1]) )/(steps);
768         dvec[2]= ( (v1->co[2]- v2->co[2]) )/(steps);
769
770         VECCOPY(nor, G.obedit->obmat[2]);
771
772         if(nor[0]*dvec[0]+nor[1]*dvec[1]+nor[2]*dvec[2]>0.000) {
773                 dvec[0]= -dvec[0];
774                 dvec[1]= -dvec[1];
775                 dvec[2]= -dvec[2];
776         }
777
778         spin_mesh(turns*steps, turns*360, dvec, 0);
779
780         BIF_undo_push("Spin");
781 }
782
783
784 static void erase_edges(ListBase *l)
785 {
786         EditEdge *ed, *nexted;
787         
788         ed = (EditEdge *) l->first;
789         while(ed) {
790                 nexted= ed->next;
791                 if( (ed->v1->f & SELECT) || (ed->v2->f & SELECT) ) {
792                         remedge(ed);
793                         free_editedge(ed);
794                 }
795                 ed= nexted;
796         }
797 }
798
799 static void erase_faces(ListBase *l)
800 {
801         EditFace *f, *nextf;
802
803         f = (EditFace *) l->first;
804
805         while(f) {
806                 nextf= f->next;
807                 if( faceselectedOR(f, SELECT) ) {
808                         BLI_remlink(l, f);
809                         free_editface(f);
810                 }
811                 f = nextf;
812         }
813 }       
814
815 static void erase_vertices(ListBase *l)
816 {
817         EditVert *v, *nextv;
818
819         v = (EditVert *) l->first;
820         while(v) {
821                 nextv= v->next;
822                 if(v->f & 1) {
823                         BLI_remlink(l, v);
824                         free_editvert(v);
825                 }
826                 v = nextv;
827         }
828 }
829
830 void delete_mesh(void)
831 {
832         EditMesh *em = G.editMesh;
833         EditFace *efa, *nextvl;
834         EditVert *eve,*nextve;
835         EditEdge *eed,*nexted;
836         short event;
837         int count;
838         char *str="Erase";
839
840         TEST_EDITMESH
841         
842         event= pupmenu("Erase %t|Vertices%x10|Edges%x1|Faces%x2|All%x3|Edges & Faces%x4|Only Faces%x5");
843         if(event<1) return;
844
845         if(event==10 ) {
846                 str= "Erase Vertices";
847                 erase_edges(&em->edges);
848                 erase_faces(&em->faces);
849                 erase_vertices(&em->verts);
850         } 
851         else if(event==4) {
852                 str= "Erase Edges & Faces";
853                 efa= em->faces.first;
854                 while(efa) {
855                         nextvl= efa->next;
856                         /* delete only faces with 1 or more edges selected */
857                         count= 0;
858                         if(efa->e1->f & SELECT) count++;
859                         if(efa->e2->f & SELECT) count++;
860                         if(efa->e3->f & SELECT) count++;
861                         if(efa->e4 && (efa->e4->f & SELECT)) count++;
862                         if(count) {
863                                 BLI_remlink(&em->faces, efa);
864                                 free_editface(efa);
865                         }
866                         efa= nextvl;
867                 }
868                 eed= em->edges.first;
869                 while(eed) {
870                         nexted= eed->next;
871                         if(eed->f & SELECT) {
872                                 remedge(eed);
873                                 free_editedge(eed);
874                         }
875                         eed= nexted;
876                 }
877                 efa= em->faces.first;
878                 while(efa) {
879                         nextvl= efa->next;
880                         event=0;
881                         if( efa->v1->f & SELECT) event++;
882                         if( efa->v2->f & SELECT) event++;
883                         if( efa->v3->f & SELECT) event++;
884                         if(efa->v4 && (efa->v4->f & SELECT)) event++;
885                         
886                         if(event>1) {
887                                 BLI_remlink(&em->faces, efa);
888                                 free_editface(efa);
889                         }
890                         efa= nextvl;
891                 }
892         } 
893         else if(event==1) {
894                 str= "Erase Edges";
895                 // faces first
896                 efa= em->faces.first;
897                 while(efa) {
898                         nextvl= efa->next;
899                         event=0;
900                         if( efa->e1->f & SELECT) event++;
901                         if( efa->e2->f & SELECT) event++;
902                         if( efa->e3->f & SELECT) event++;
903                         if(efa->e4 && (efa->e4->f & SELECT)) event++;
904                         
905                         if(event) {
906                                 BLI_remlink(&em->faces, efa);
907                                 free_editface(efa);
908                         }
909                         efa= nextvl;
910                 }
911                 eed= em->edges.first;
912                 while(eed) {
913                         nexted= eed->next;
914                         if(eed->f & SELECT) {
915                                 remedge(eed);
916                                 free_editedge(eed);
917                         }
918                         eed= nexted;
919                 }
920                 /* to remove loose vertices: */
921                 eed= em->edges.first;
922                 while(eed) {
923                         if( eed->v1->f & SELECT) eed->v1->f-=SELECT;
924                         if( eed->v2->f & SELECT) eed->v2->f-=SELECT;
925                         eed= eed->next;
926                 }
927                 eve= em->verts.first;
928                 while(eve) {
929                         nextve= eve->next;
930                         if(eve->f & SELECT) {
931                                 BLI_remlink(&em->verts,eve);
932                                 free_editvert(eve);
933                         }
934                         eve= nextve;
935                 }
936
937         }
938         else if(event==2) {
939                 str="Erase Faces";
940                 delfaceflag(SELECT);
941         }
942         else if(event==3) {
943                 str= "Erase All";
944                 if(em->verts.first) free_vertlist(&em->verts);
945                 if(em->edges.first) free_edgelist(&em->edges);
946                 if(em->faces.first) free_facelist(&em->faces);
947         }
948         else if(event==5) {
949                 str= "Erase Only Faces";
950                 efa= em->faces.first;
951                 while(efa) {
952                         nextvl= efa->next;
953                         if(efa->f & SELECT) {
954                                 BLI_remlink(&em->faces, efa);
955                                 free_editface(efa);
956                         }
957                         efa= nextvl;
958                 }
959         }
960
961         EM_fgon_flags();        // redo flags and indices for fgons
962
963         countall();
964         allqueue(REDRAWVIEW3D, 0);
965         makeDispList(G.obedit);
966         BIF_undo_push(str);
967 }
968
969
970 /* Got this from scanfill.c. You will need to juggle around the
971  * callbacks for the scanfill.c code a bit for this to work. */
972 void fill_mesh(void)
973 {
974         EditMesh *em = G.editMesh;
975         EditVert *eve,*v1;
976         EditEdge *eed,*e1,*nexted;
977         EditFace *efa,*nextvl, *efan;
978         short ok;
979
980         if(G.obedit==0 || (G.obedit->type!=OB_MESH)) return;
981
982         waitcursor(1);
983
984         /* copy all selected vertices */
985         eve= em->verts.first;
986         while(eve) {
987                 if(eve->f & SELECT) {
988                         v1= BLI_addfillvert(eve->co);
989                         eve->vn= v1;
990                         v1->vn= eve;
991                         v1->h= 0;
992                 }
993                 eve= eve->next;
994         }
995         /* copy all selected edges */
996         eed= em->edges.first;
997         while(eed) {
998                 if( (eed->v1->f & SELECT) && (eed->v2->f & SELECT) ) {
999                         e1= BLI_addfilledge(eed->v1->vn, eed->v2->vn);
1000                         e1->v1->h++; 
1001                         e1->v2->h++;
1002                 }
1003                 eed= eed->next;
1004         }
1005         /* from all selected faces: remove vertices and edges to prevent doubles */
1006         /* all edges add values, faces subtract,
1007            then remove edges with vertices ->h<2 */
1008         efa= em->faces.first;
1009         ok= 0;
1010         while(efa) {
1011                 nextvl= efa->next;
1012                 if( faceselectedAND(efa, 1) ) {
1013                         efa->v1->vn->h--;
1014                         efa->v2->vn->h--;
1015                         efa->v3->vn->h--;
1016                         if(efa->v4) efa->v4->vn->h--;
1017                         ok= 1;
1018                         
1019                 }
1020                 efa= nextvl;
1021         }
1022         if(ok) {        /* there are faces selected */
1023                 eed= filledgebase.first;
1024                 while(eed) {
1025                         nexted= eed->next;
1026                         if(eed->v1->h<2 || eed->v2->h<2) {
1027                                 BLI_remlink(&filledgebase,eed);
1028                         }
1029                         eed= nexted;
1030                 }
1031         }
1032
1033         /* to make edgefill work */
1034         BLI_setScanFillObjectRef(G.obedit);
1035         BLI_setScanFillColourRef(&G.obedit->actcol);
1036
1037         ok= BLI_edgefill(0);
1038
1039         /* printf("time: %d\n",(clock()-tijd)/1000); */
1040
1041         if(ok) {
1042                 efa= fillfacebase.first;
1043                 while(efa) {
1044                         efan= addfacelist(efa->v3->vn, efa->v2->vn, efa->v1->vn, 0, efa, NULL); // normals default pointing up
1045                         EM_select_face(efan, 1);
1046                         efa= efa->next;
1047                 }
1048         }
1049         /* else printf("fill error\n"); */
1050
1051         BLI_end_edgefill();
1052
1053         waitcursor(0);
1054         EM_select_flush();
1055         countall();
1056         allqueue(REDRAWVIEW3D, 0);
1057         makeDispList(G.obedit);
1058         BIF_undo_push("Fill");
1059 }
1060
1061
1062
1063 /* ******************** SUBDIVIDE ********************************** */
1064
1065
1066 static unsigned int cpack_fact(unsigned int col1, unsigned int col2, float fact)
1067 {
1068         char *cp1, *cp2, *cp;
1069         unsigned int col=0;
1070         float fact1;
1071         
1072         fact1=1-fact; /*result is fact% col1 and (1-fact) % col2 */
1073                 
1074         cp1= (char *)&col1;
1075         cp2= (char *)&col2;
1076         cp=  (char *)&col;
1077         
1078         cp[0]= fact*cp1[0]+fact1*cp2[0];
1079         cp[1]= fact*cp1[1]+fact1*cp2[1];
1080         cp[2]= fact*cp1[2]+fact1*cp2[2];
1081         cp[3]= fact*cp1[3]+fact1*cp2[3];
1082         
1083         return col;
1084 }
1085
1086
1087 static void uv_half(float *uv, float *uv1, float *uv2)
1088 {
1089         uv[0]= (uv1[0]+uv2[0])/2.0;
1090         uv[1]= (uv1[1]+uv2[1])/2.0;
1091         
1092 }
1093
1094 static void uv_quart(float *uv, float *uv1)
1095 {
1096         uv[0]= (uv1[0]+uv1[2]+uv1[4]+uv1[6])/4.0;
1097         uv[1]= (uv1[1]+uv1[3]+uv1[5]+uv1[7])/4.0;
1098 }
1099
1100 static void face_pin_vertex(EditFace *efa, EditVert *vertex)
1101 {
1102         if(efa->v1 == vertex) efa->tf.unwrap |= TF_PIN1;
1103         else if(efa->v2 == vertex) efa->tf.unwrap |= TF_PIN2;
1104         else if(efa->v3 == vertex) efa->tf.unwrap |= TF_PIN3;
1105         else if(efa->v4 && vertex && efa->v4 == vertex) efa->tf.unwrap |= TF_PIN4;
1106 }
1107
1108 static void set_wuv(int tot, EditFace *efa, int v1, int v2, int v3, int v4, EditFace *efapin)
1109 {
1110         /* this weird function only to be used for subdivide, the 'w' in the name has no meaning! */
1111         float *uv, uvo[4][2];
1112         unsigned int *col, colo[4], col1, col2;
1113         int a, v;
1114
1115         /* recover pinning */
1116         if(efapin){
1117                 efa->tf.unwrap= 0;
1118                 if(efapin->tf.unwrap & TF_PIN1) face_pin_vertex(efa, efapin->v1);
1119                 if(efapin->tf.unwrap & TF_PIN2) face_pin_vertex(efa, efapin->v2);
1120                 if(efapin->tf.unwrap & TF_PIN3) face_pin_vertex(efa, efapin->v3);
1121                 if(efapin->tf.unwrap & TF_PIN4) face_pin_vertex(efa, efapin->v4);
1122         }
1123
1124                                                 /* Numbers corespond to verts (corner points),  */
1125                                                 /* edge->vn's (center edges), the Center        */
1126         memcpy(uvo, efa->tf.uv, sizeof(uvo));   /* And the quincunx points of a face            */
1127         uv= efa->tf.uv[0];                            /* as shown here:                                 */
1128                                                       /*           2         5          1   */
1129         memcpy(colo, efa->tf.col, sizeof(colo));      /*               10         13        */
1130         col= efa->tf.col;                             /*           6         9          8   */
1131                                                   /*               11         12        */
1132         if(tot==4) {                                  /*           3         7          4   */
1133                 for(a=0; a<4; a++, uv+=2, col++) {
1134                         if(a==0) v= v1;
1135                         else if(a==1) v= v2;
1136                         else if(a==2) v= v3;
1137                         else v= v4;
1138                         
1139                         if(a==3 && v4==0) break;
1140                         
1141                         if(v<=4) {
1142                                 uv[0]= uvo[v-1][0];
1143                                 uv[1]= uvo[v-1][1];
1144                                 *col= colo[v-1];
1145                         }
1146                         else if(v==8) {
1147                                 uv_half(uv, uvo[3], uvo[0]);
1148                                 *col= cpack_fact(colo[3], colo[0], 0.5);
1149                         }
1150                         else if(v==9) {
1151                                 uv_quart(uv, uvo[0]);
1152                                 col1= cpack_fact(colo[1], colo[0], 0.5);
1153                                 col2= cpack_fact(colo[2], colo[3], 0.5);
1154                                 *col= cpack_fact(col1, col2, 0.5);
1155                         }
1156                         /* Cases for adjacent edge square subdivide  Real voodoo */
1157                         /* 1/2 closest corner + 1/4 adjacent corners */
1158                         else if (v==10){ /* case test==3 in subdivideflag() */  
1159                                 uv[0]=(2*uvo[1][0]+uvo[0][0]+uvo[2][0])/4;
1160                                 uv[1]=(2*uvo[1][1]+uvo[0][1]+uvo[2][1])/4;
1161                                 col1= cpack_fact(colo[1], colo[0], 0.75);
1162                                 col2= cpack_fact(colo[2], colo[3], 0.75);
1163                                 *col= cpack_fact(col1, col2, 0.75);     
1164                         }
1165                         else if (v==11) { /* case of test==6 */
1166                                 uv[0]=(2*uvo[2][0]+uvo[1][0]+uvo[3][0])/4;
1167                                 uv[1]=(2*uvo[2][1]+uvo[1][1]+uvo[3][1])/4;
1168                                 col1= cpack_fact(colo[1], colo[0], 0.75);
1169                                 col2= cpack_fact(colo[2], colo[3], 0.75);
1170                                 *col= cpack_fact(col1, col2, 0.25);     
1171                         }
1172                         else if (v==12) { /* case of test==12 */
1173                                 uv[0]=(2*uvo[3][0]+uvo[2][0]+uvo[0][0])/4;
1174                                 uv[1]=(2*uvo[3][1]+uvo[2][1]+uvo[0][1])/4;
1175                                 col1= cpack_fact(colo[1], colo[0], 0.25);
1176                                 col2= cpack_fact(colo[2], colo[3], 0.25);
1177                                 *col= cpack_fact(col1, col2, 0.25);
1178                         }
1179                         else if (v==13) { /* case of test==9 */
1180                                 uv[0]=(2*uvo[0][0]+uvo[1][0]+uvo[3][0])/4;
1181                                 uv[1]=(2*uvo[0][1]+uvo[1][1]+uvo[3][1])/4;
1182                                 col1= cpack_fact(colo[1], colo[0], 0.25);
1183                                 col2= cpack_fact(colo[2], colo[3], 0.25);
1184                                 *col= cpack_fact(col1, col2, 0.75);
1185                         }
1186                         /* default for consecutive verts*/
1187                         else { 
1188                                 uv_half(uv, uvo[v-5], uvo[v-4]);
1189                                 *col= cpack_fact(colo[v-5], colo[v-4], 0.5);
1190                         }
1191                 }
1192         }
1193         else {
1194                 for(a=0; a<3; a++, uv+=2, col++) {
1195                         if(a==0) v= v1;
1196                         else if(a==1) v= v2;
1197                         else v= v3;
1198                 
1199                         if(v<=4) {
1200                                 uv[0]= uvo[v-1][0];
1201                                 uv[1]= uvo[v-1][1];
1202                                 *col= colo[v-1];
1203                         }
1204                         else if(v==7) {
1205                                 uv_half(uv, uvo[2], uvo[0]);
1206                                 *col= cpack_fact(colo[2], colo[0], 0.5);
1207                         }
1208                         else {
1209                                 uv_half(uv, uvo[v-5], uvo[v-4]);
1210                                 *col= cpack_fact(colo[v-5], colo[v-4], 0.5);
1211                         }
1212                 }
1213         }
1214 }
1215
1216 static EditVert *vert_from_number(EditFace *efa, int nr)
1217 {
1218         switch(nr) {
1219         case 0:
1220                 return 0;
1221         case 1:
1222                 return efa->v1;
1223         case 2:
1224                 return efa->v2;
1225         case 3:
1226                 return efa->v3;
1227         case 4:
1228                 return efa->v4;
1229         case 5:
1230                 return efa->e1->vn;
1231         case 6:
1232                 return efa->e2->vn;
1233         case 7:
1234                 return efa->e3->vn;
1235         case 8:
1236                 return efa->e4->vn;
1237         }
1238         
1239         return NULL;
1240 }
1241
1242 static void addface_subdiv(EditFace *efa, int val1, int val2, int val3, int val4, EditVert *eve, EditFace *efapin)
1243 {
1244         EditFace *w;
1245         EditVert *v1, *v2, *v3, *v4;
1246         
1247         if(val1>=9) v1= eve;
1248         else v1= vert_from_number(efa, val1);
1249         
1250         if(val2>=9) v2= eve;
1251         else v2= vert_from_number(efa, val2);
1252
1253         if(val3>=9) v3= eve;
1254         else v3= vert_from_number(efa, val3);
1255
1256         if(val4>=9) v4= eve;
1257         else v4= vert_from_number(efa, val4);
1258         
1259         w= addfacelist(v1, v2, v3, v4, efa, NULL);
1260         if(w) {
1261                 if(efa->v4) set_wuv(4, w, val1, val2, val3, val4, efapin);
1262                 else set_wuv(3, w, val1, val2, val3, val4, efapin);
1263         }
1264 }
1265
1266 static float smoothperc= 0.0;
1267
1268 static void smooth_subdiv_vec(float *v1, float *v2, float *n1, float *n2, float *vec)
1269 {
1270         float len, fac, nor[3], nor1[3], nor2[3];
1271         
1272         VecSubf(nor, v1, v2);
1273         len= 0.5*Normalise(nor);
1274
1275         VECCOPY(nor1, n1);
1276         VECCOPY(nor2, n2);
1277
1278         /* cosine angle */
1279         fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
1280         
1281         vec[0]= fac*nor1[0];
1282         vec[1]= fac*nor1[1];
1283         vec[2]= fac*nor1[2];
1284
1285         /* cosine angle */
1286         fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
1287         
1288         vec[0]+= fac*nor2[0];
1289         vec[1]+= fac*nor2[1];
1290         vec[2]+= fac*nor2[2];
1291
1292         vec[0]*= smoothperc*len;
1293         vec[1]*= smoothperc*len;
1294         vec[2]*= smoothperc*len;
1295 }
1296
1297 static void smooth_subdiv_quad(EditFace *efa, float *vec)
1298 {
1299         
1300         float nor1[3], nor2[3];
1301         float vec1[3], vec2[3];
1302         float cent[3];
1303         
1304         /* vlr->e1->vn is new vertex inbetween v1 / v2 */
1305         
1306         VecMidf(nor1, efa->v1->no, efa->v2->no);
1307         Normalise(nor1);
1308         VecMidf(nor2, efa->v3->no, efa->v4->no);
1309         Normalise(nor2);
1310
1311         smooth_subdiv_vec( efa->e1->vn->co, efa->e3->vn->co, nor1, nor2, vec1);
1312
1313         VecMidf(nor1, efa->v2->no, efa->v3->no);
1314         Normalise(nor1);
1315         VecMidf(nor2, efa->v4->no, efa->v1->no);
1316         Normalise(nor2);
1317
1318         smooth_subdiv_vec( efa->e2->vn->co, efa->e4->vn->co, nor1, nor2, vec2);
1319
1320         VecAddf(vec1, vec1, vec2);
1321
1322         CalcCent4f(cent, efa->v1->co,  efa->v2->co,  efa->v3->co,  efa->v4->co);
1323         VecAddf(vec, cent, vec1);
1324 }
1325
1326 void subdivideflag(int flag, float rad, int beauty)
1327 {
1328         EditMesh *em = G.editMesh;
1329         /* subdivide all with (vertflag & flag) */
1330         /* if rad>0.0 it's a 'sphere' subdivide */
1331         /* if rad<0.0 it's a fractal subdivide */
1332         extern float doublimit;
1333         EditVert *eve;
1334         EditEdge *eed, *e1, *e2, *e3, *e4, *nexted;
1335         EditFace *efa, efapin;
1336         float fac, vec[3], vec1[3], len1, len2, len3, percent;
1337         short test;
1338         
1339         if(beauty & B_SMOOTH) {
1340                 short perc= 100;
1341
1342                 if(button(&perc, 10, 500, "Percentage:")==0) return;
1343                 
1344                 smoothperc= 0.292*perc/100.0;
1345         }
1346
1347         /* edgeflags */
1348         if((beauty & B_KNIFE)==0) {             // knife option sets own flags
1349                 eed= em->edges.first;
1350                 while(eed) {    
1351                         if( (eed->v1->f & flag) && (eed->v2->f & flag) ) eed->f2= flag;
1352                         else eed->f2= 0;        
1353                         eed= eed->next;
1354                 }
1355         }
1356         
1357         /* if beauty: test for area and clear edge flags of 'ugly' edges */
1358         if(beauty & B_BEAUTY) {
1359                 efa= em->faces.first;
1360                 while(efa) {
1361                         if( faceselectedAND(efa, flag) ) {
1362                                 if(efa->v4) {
1363                                 
1364                                         /* area */
1365                                         len1= AreaQ3Dfl(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
1366                                         if(len1 <= doublimit) {
1367                                                 efa->e1->f2 = 0;
1368                                                 efa->e2->f2 = 0;
1369                                                 efa->e3->f2 = 0;
1370                                                 efa->e4->f2 = 0;
1371                                         }
1372                                         else {
1373                                                 len1= VecLenf(efa->v1->co, efa->v2->co) + VecLenf(efa->v3->co, efa->v4->co);
1374                                                 len2= VecLenf(efa->v2->co, efa->v3->co) + VecLenf(efa->v1->co, efa->v4->co);
1375                                                 
1376                                                 if(len1 < len2) {
1377                                                         efa->e1->f2 = 0;
1378                                                         efa->e3->f2 = 0;
1379                                                 }
1380                                                 else if(len1 > len2) {
1381                                                         efa->e2->f2 = 0;
1382                                                         efa->e4->f2 = 0;
1383                                                 }
1384                                         }
1385                                 }
1386                                 else {
1387                                         /* area */
1388                                         len1= AreaT3Dfl(efa->v1->co, efa->v2->co, efa->v3->co);
1389                                         if(len1 <= doublimit) {
1390                                                 efa->e1->f2 = 0;
1391                                                 efa->e2->f2 = 0;
1392                                                 efa->e3->f2 = 0;
1393                                         }
1394                                         else {
1395                                                 len1= VecLenf(efa->v1->co, efa->v2->co) ;
1396                                                 len2= VecLenf(efa->v2->co, efa->v3->co) ;
1397                                                 len3= VecLenf(efa->v3->co, efa->v1->co) ;
1398                                                 
1399                                                 if(len1<len2 && len1<len3) {
1400                                                         efa->e1->f2 = 0;
1401                                                 }
1402                                                 else if(len2<len3 && len2<len1) {
1403                                                         efa->e2->f2 = 0;
1404                                                 }
1405                                                 else if(len3<len2 && len3<len1) {
1406                                                         efa->e3->f2 = 0;
1407                                                 }
1408                                         }
1409                                 }
1410                         }
1411                         efa= efa->next;
1412                 }
1413         }
1414
1415         if(beauty & B_SMOOTH) {
1416                 
1417                 vertexnormals(0);               /* no1*/
1418                         
1419         }
1420         
1421         /* make new normal and put in edge, clear flag! needed for face creation part below */
1422         eed= em->edges.first;
1423         while(eed) {
1424                 if(eed->f2 & flag) {
1425                         /* for now */
1426                         eed->h &= ~EM_FGON;
1427                 
1428                         /* Subdivide percentage is stored in 1/32768ths in eed->f1 */
1429                         if (beauty & B_PERCENTSUBD) percent=(float)(eed->f1)/32768.0;
1430                         else percent=0.5;
1431                         
1432                         vec[0]= (1-percent)*eed->v1->co[0] + percent*eed->v2->co[0];
1433                         vec[1]= (1-percent)*eed->v1->co[1] + percent*eed->v2->co[1];
1434                         vec[2]= (1-percent)*eed->v1->co[2] + percent*eed->v2->co[2];
1435
1436                         if(rad > 0.0) {   /* subdivide sphere */
1437                                 Normalise(vec);
1438                                 vec[0]*= rad;
1439                                 vec[1]*= rad;
1440                                 vec[2]*= rad;
1441                         }
1442                         else if(rad< 0.0) {  /* fractal subdivide */
1443                                 fac= rad* VecLenf(eed->v1->co, eed->v2->co);
1444                                 vec1[0]= fac*(0.5-BLI_drand());
1445                                 vec1[1]= fac*(0.5-BLI_drand());
1446                                 vec1[2]= fac*(0.5-BLI_drand());
1447                                 VecAddf(vec, vec, vec1);
1448                         }
1449                         
1450                         if(beauty & B_SMOOTH) {
1451                                 smooth_subdiv_vec(eed->v1->co, eed->v2->co, eed->v1->no, eed->v2->no, vec1);
1452                                 VecAddf(vec, vec, vec1);
1453                         }
1454                         
1455                         eed->vn= addvertlist(vec);
1456                         eed->vn->f= eed->v1->f;
1457
1458                 }
1459                 else eed->vn= 0;
1460                 
1461                 eed->f2= 0; /* needed! */
1462                 
1463                 eed= eed->next;
1464         }
1465
1466         /* test all faces for subdivide edges, there are 8 or 16 cases (ugh)! */
1467
1468         efa= em->faces.last;
1469         while(efa) {
1470
1471                 efapin= *efa; /* make a copy of efa to recover uv pinning later */
1472
1473                 if( faceselectedOR(efa, flag) ) {
1474                         /* for now */
1475                         efa->fgonf= 0;
1476                         
1477                         e1= efa->e1;
1478                         e2= efa->e2;
1479                         e3= efa->e3;
1480                         e4= efa->e4;
1481
1482                         test= 0;
1483                         if(e1 && e1->vn) { 
1484                                 test+= 1;
1485                                 e1->f2= 1;
1486                                 /* add edges here, to copy correct edge data */
1487                                 eed= addedgelist(e1->v1, e1->vn, e1);
1488                                 eed= addedgelist(e1->vn, e1->v2, e1);
1489                         }
1490                         if(e2 && e2->vn) {
1491                                 test+= 2;
1492                                 e2->f2= 1;
1493                                 /* add edges here, to copy correct edge data */
1494                                 eed= addedgelist(e2->v1, e2->vn, e2);
1495                                 eed= addedgelist(e2->vn, e2->v2, e2);
1496                         }
1497                         if(e3 && e3->vn) {
1498                                 test+= 4;
1499                                 e3->f2= 1;
1500                                 /* add edges here, to copy correct edge data */
1501                                 eed= addedgelist(e3->v1, e3->vn, e3);
1502                                 eed= addedgelist(e3->vn, e3->v2, e3);
1503                         }
1504                         if(e4 && e4->vn) {
1505                                 test+= 8;
1506                                 e4->f2= 1;
1507                                 /* add edges here, to copy correct edge data */
1508                                 eed= addedgelist(e4->v1, e4->vn, e4);
1509                                 eed= addedgelist(e4->vn, e4->v2, e4);
1510                         }
1511                         if(test) {
1512                                 if(efa->v4==0) {  /* All the permutations of 3 edges*/
1513                                         if((test & 3)==3) addface_subdiv(efa, 2, 2+4, 1+4, 0, 0, &efapin);
1514                                         if((test & 6)==6) addface_subdiv(efa, 3, 3+4, 2+4, 0, 0, &efapin);
1515                                         if((test & 5)==5) addface_subdiv(efa, 1, 1+4, 3+4, 0, 0, &efapin);
1516
1517                                         if(test==7) {  /* four new faces, old face renews */
1518                                                 efa->v1= e1->vn;
1519                                                 efa->v2= e2->vn;
1520                                                 efa->v3= e3->vn;
1521                                                 set_wuv(3, efa, 1+4, 2+4, 3+4, 0, &efapin);
1522                                         }
1523                                         else if(test==3) {
1524                                                 addface_subdiv(efa, 1+4, 2+4, 3, 0, 0, &efapin);
1525                                                 efa->v2= e1->vn;
1526                                                 set_wuv(3, efa, 1, 1+4, 3, 0, &efapin);
1527                                         }
1528                                         else if(test==6) {
1529                                                 addface_subdiv(efa, 2+4, 3+4, 1, 0, 0, &efapin);
1530                                                 efa->v3= e2->vn;
1531                                                 set_wuv(3, efa, 1, 2, 2+4, 0, &efapin);
1532                                         }
1533                                         else if(test==5) {
1534                                                 addface_subdiv(efa, 3+4, 1+4, 2, 0, 0, &efapin);
1535                                                 efa->v1= e3->vn;
1536                                                 set_wuv(3, efa, 3+4, 2, 3, 0, &efapin);
1537                                         }
1538                                         else if(test==1) {
1539                                                 addface_subdiv(efa, 1+4, 2, 3, 0, 0, &efapin);
1540                                                 efa->v2= e1->vn;
1541                                                 set_wuv(3, efa, 1, 1+4, 3, 0, &efapin);
1542                                         }
1543                                         else if(test==2) {
1544                                                 addface_subdiv(efa, 2+4, 3, 1, 0, 0, &efapin);
1545                                                 efa->v3= e2->vn;
1546                                                 set_wuv(3, efa, 1, 2, 2+4, 0, &efapin);
1547                                         }
1548                                         else if(test==4) {
1549                                                 addface_subdiv(efa, 3+4, 1, 2, 0, 0, &efapin);
1550                                                 efa->v1= e3->vn;
1551                                                 set_wuv(3, efa, 3+4, 2, 3, 0, &efapin);
1552                                         }
1553                                         efa->e1= addedgelist(efa->v1, efa->v2, NULL);
1554                                         efa->e2= addedgelist(efa->v2, efa->v3, NULL);
1555                                         efa->e3= addedgelist(efa->v3, efa->v1, NULL);
1556
1557                                 }
1558                                 else {  /* All the permutations of 4 faces */
1559                                         if(test==15) {
1560                                                 /* add a new point in center */
1561                                                 CalcCent4f(vec, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
1562                                                 
1563                                                 if(beauty & B_SMOOTH) {
1564                                                         smooth_subdiv_quad(efa, vec);   /* adds */
1565                                                 }
1566                                                 eve= addvertlist(vec);
1567                                                 
1568                                                 eve->f |= flag;
1569
1570                                                 addface_subdiv(efa, 2, 2+4, 9, 1+4, eve, &efapin);
1571                                                 addface_subdiv(efa, 3, 3+4, 9, 2+4, eve, &efapin);
1572                                                 addface_subdiv(efa, 4, 4+4, 9, 3+4, eve, &efapin);
1573
1574                                                 efa->v2= e1->vn;
1575                                                 efa->v3= eve;
1576                                                 efa->v4= e4->vn;
1577                                                 set_wuv(4, efa, 1, 1+4, 9, 4+4, &efapin);
1578                                         }
1579                                         else {
1580                                                 if(((test & 3)==3)&&(test!=3)) addface_subdiv(efa, 1+4, 2, 2+4, 0, 0, &efapin);
1581                                                 if(((test & 6)==6)&&(test!=6)) addface_subdiv(efa, 2+4, 3, 3+4, 0, 0, &efapin);
1582                                                 if(((test & 12)==12)&&(test!=12)) addface_subdiv(efa, 3+4, 4, 4+4, 0, 0, &efapin);
1583                                                 if(((test & 9)==9)&&(test!=9)) addface_subdiv(efa, 4+4, 1, 1+4, 0, 0, &efapin);
1584
1585                                                 if(test==1) { /* Edge 1 has new vert */
1586                                                         addface_subdiv(efa, 1+4, 2, 3, 0, 0, &efapin);
1587                                                         addface_subdiv(efa, 1+4, 3, 4, 0, 0, &efapin);
1588                                                         efa->v2= e1->vn;
1589                                                         efa->v3= efa->v4;
1590                                                         efa->v4= 0;
1591                                                         set_wuv(4, efa, 1, 1+4, 4, 0, &efapin);
1592                                                 }
1593                                                 else if(test==2) { /* Edge 2 has new vert */
1594                                                         addface_subdiv(efa, 2+4, 3, 4, 0, 0, &efapin);
1595                                                         addface_subdiv(efa, 2+4, 4, 1, 0, 0, &efapin);
1596                                                         efa->v3= e2->vn;
1597                                                         efa->v4= 0;
1598                                                         set_wuv(4, efa, 1, 2, 2+4, 0, &efapin);
1599                                                 }
1600                                                 else if(test==4) { /* Edge 3 has new vert */
1601                                                         addface_subdiv(efa, 3+4, 4, 1, 0, 0, &efapin);
1602                                                         addface_subdiv(efa, 3+4, 1, 2, 0, 0, &efapin);
1603                                                         efa->v1= efa->v2;
1604                                                         efa->v2= efa->v3;
1605                                                         efa->v3= e3->vn;
1606                                                         efa->v4= 0;
1607                                                         set_wuv(4, efa, 2, 3, 3+4, 0, &efapin);
1608                                                 }
1609                                                 else if(test==8) { /* Edge 4 has new vert */
1610                                                         addface_subdiv(efa, 4+4, 1, 2, 0, 0, &efapin);
1611                                                         addface_subdiv(efa, 4+4, 2, 3, 0, 0, &efapin);
1612                                                         efa->v1= efa->v3;
1613                                                         efa->v2= efa->v4;
1614                                                         efa->v3= e4->vn;
1615                                                         efa->v4= 0;
1616                                                         set_wuv(4, efa, 3, 4, 4+4, 0, &efapin);
1617                                                 }
1618                                                 else if(test==3) { /*edge 1&2 */
1619                                                         /* make new vert in center of new edge */
1620                                                         vec[0]=(e1->vn->co[0]+e2->vn->co[0])/2;
1621                                                         vec[1]=(e1->vn->co[1]+e2->vn->co[1])/2;
1622                                                         vec[2]=(e1->vn->co[2]+e2->vn->co[2])/2;
1623                                                         eve= addvertlist(vec);
1624                                                         eve->f |= flag;
1625                                                         /* Add new faces */
1626                                                         addface_subdiv(efa, 4, 10, 2+4, 3, eve, &efapin);
1627                                                         addface_subdiv(efa, 4, 1, 1+4, 10, eve, &efapin);
1628                                                         /* orig face becomes small corner */
1629                                                         efa->v1=e1->vn;
1630                                                         //efa->v2=efa->v2;
1631                                                         efa->v3=e2->vn;
1632                                                         efa->v4=eve;
1633
1634                                                         set_wuv(4, efa, 1+4, 2, 2+4, 10, &efapin);
1635                                                 }
1636                                                 else if(test==6) { /* 2&3 */
1637                                                         /* make new vert in center of new edge */
1638                                                         vec[0]=(e2->vn->co[0]+e3->vn->co[0])/2;
1639                                                         vec[1]=(e2->vn->co[1]+e3->vn->co[1])/2;
1640                                                         vec[2]=(e2->vn->co[2]+e3->vn->co[2])/2;
1641                                                         eve= addvertlist(vec);
1642                                                         eve->f |= flag;
1643                                                         /*New faces*/
1644                                                         addface_subdiv(efa, 1, 11, 3+4, 4, eve, &efapin);
1645                                                         addface_subdiv(efa, 1, 2, 2+4, 11, eve, &efapin);
1646                                                         /* orig face becomes small corner */
1647                                                         efa->v1=e2->vn;
1648                                                         efa->v2=efa->v3;
1649                                                         efa->v3=e3->vn;
1650                                                         efa->v4=eve;
1651
1652                                                         set_wuv(4, efa, 2+4, 3, 3+4, 11, &efapin);
1653                                                 }
1654                                                 else if(test==12) { /* 3&4 */
1655                                                         /* make new vert in center of new edge */
1656                                                         vec[0]=(e3->vn->co[0]+e4->vn->co[0])/2;
1657                                                         vec[1]=(e3->vn->co[1]+e4->vn->co[1])/2;
1658                                                         vec[2]=(e3->vn->co[2]+e4->vn->co[2])/2;
1659                                                         eve= addvertlist(vec);
1660                                                         eve->f |= flag;
1661                                                         /*New Faces*/
1662                                                         addface_subdiv(efa, 2, 12, 4+4, 1, eve, &efapin);
1663                                                         addface_subdiv(efa, 2, 3, 3+4, 12, eve, &efapin);
1664                                                         /* orig face becomes small corner */
1665                                                         efa->v1=e3->vn;
1666                                                         efa->v2=efa->v4;
1667                                                         efa->v3=e4->vn;
1668                                                         efa->v4=eve;
1669
1670                                                         set_wuv(4, efa, 3+4, 4, 4+4, 12, &efapin);
1671                                                 }
1672                                                 else if(test==9) { /* 4&1 */
1673                                                         /* make new vert in center of new edge */
1674                                                         vec[0]=(e1->vn->co[0]+e4->vn->co[0])/2;
1675                                                         vec[1]=(e1->vn->co[1]+e4->vn->co[1])/2;
1676                                                         vec[2]=(e1->vn->co[2]+e4->vn->co[2])/2;
1677                                                         eve= addvertlist(vec);
1678                                                         eve->f |= flag;
1679                                                         /*New Faces*/
1680                                                         addface_subdiv(efa, 3, 13, 1+4, 2, eve, &efapin);
1681                                                         addface_subdiv(efa, 3, 4,  4+4,13, eve, &efapin);
1682                                                         /* orig face becomes small corner */
1683                                                         efa->v2=efa->v1;
1684                                                         efa->v1=e4->vn;
1685                                                         efa->v3=e1->vn;
1686                                                         efa->v4=eve;
1687
1688                                                         set_wuv(4, efa, 4+4, 1, 1+4, 13, &efapin);
1689                                                 }
1690                                                 else if(test==5) { /* 1&3 */
1691                                                         addface_subdiv(efa, 1+4, 2, 3, 3+4, 0, &efapin);
1692                                                         efa->v2= e1->vn;
1693                                                         efa->v3= e3->vn;
1694                                                         set_wuv(4, efa, 1, 1+4, 3+4, 4, &efapin);
1695                                                 }
1696                                                 else if(test==10) { /* 2&4 */
1697                                                         addface_subdiv(efa, 2+4, 3, 4, 4+4, 0, &efapin);
1698                                                         efa->v3= e2->vn;
1699                                                         efa->v4= e4->vn;
1700                                                         set_wuv(4, efa, 1, 2, 2+4, 4+4, &efapin);
1701                                                 }/* Unfortunately, there is no way to avoid tris on 1 or 3 edges*/
1702                                                 else if(test==7) { /*1,2&3 */
1703                                                         addface_subdiv(efa, 1+4, 2+4, 3+4, 0, 0, &efapin);
1704                                                         efa->v2= e1->vn;
1705                                                         efa->v3= e3->vn;
1706                                                         set_wuv(4, efa, 1, 1+4, 3+4, 4, &efapin);
1707                                                 }
1708                                                 
1709                                                 else if(test==14) { /* 2,3&4 */
1710                                                         addface_subdiv(efa, 2+4, 3+4, 4+4, 0, 0, &efapin);
1711                                                         efa->v3= e2->vn;
1712                                                         efa->v4= e4->vn;
1713                                                         set_wuv(4, efa, 1, 2, 2+4, 4+4, &efapin);
1714                                                 }
1715                                                 else if(test==13) {/* 1,3&4 */
1716                                                         addface_subdiv(efa, 3+4, 4+4, 1+4, 0, 0, &efapin);
1717                                                         efa->v4= e3->vn;
1718                                                         efa->v1= e1->vn;
1719                                                         set_wuv(4, efa, 1+4, 3, 3, 3+4, &efapin);
1720                                                 }
1721                                                 else if(test==11) { /* 1,2,&4 */
1722                                                         addface_subdiv(efa, 4+4, 1+4, 2+4, 0, 0, &efapin);
1723                                                         efa->v1= e4->vn;
1724                                                         efa->v2= e2->vn;
1725                                                         set_wuv(4, efa, 4+4, 2+4, 3, 4, &efapin);
1726                                                 }
1727                                         }
1728                                         efa->e1= addedgelist(efa->v1, efa->v2, NULL);
1729                                         efa->e2= addedgelist(efa->v2, efa->v3, NULL);
1730                                         if(efa->v4) efa->e3= addedgelist(efa->v3, efa->v4, NULL);
1731                                         else efa->e3= addedgelist(efa->v3, efa->v1, NULL);
1732                                         if(efa->v4) efa->e4= addedgelist(efa->v4, efa->v1, NULL);
1733                                         else efa->e4= NULL;
1734                                 }
1735                         }
1736                 }
1737                 efa= efa->prev;
1738         }
1739
1740         /* remove all old edges, if needed make new ones */
1741         eed= em->edges.first;
1742         while(eed) {
1743                 nexted= eed->next;
1744                 if( eed->vn ) {
1745                         eed->vn->f |= 16;                       
1746                         if(eed->f2==0) {  /* not used in face */                                
1747                                 addedgelist(eed->v1, eed->vn, eed);
1748                                 addedgelist(eed->vn, eed->v2, eed);
1749                         }                                               
1750                         remedge(eed);
1751                         free_editedge(eed);
1752                 }
1753                 eed= nexted;
1754         }
1755         
1756         /* since this is all on vertex level, flush vertex selection */
1757         EM_select_flush();
1758         recalc_editnormals();
1759         
1760         countall();
1761         allqueue(REDRAWVIEW3D, 0);
1762         makeDispList(G.obedit);
1763 }
1764
1765 static int count_selected_edges(EditEdge *ed)
1766 {
1767         int totedge = 0;
1768         while(ed) {
1769                 ed->vn= 0;
1770                 if( ed->f & SELECT ) totedge++;
1771                 ed= ed->next;
1772         }
1773         return totedge;
1774 }
1775
1776 /* hurms, as if this makes code readable! It's pointerpointer hiding... (ton) */
1777 typedef EditFace *EVPtr;
1778 typedef EVPtr EVPTuple[2];
1779
1780 /** builds EVPTuple array efaa of face tuples (in fact pointers to EditFaces)
1781     sharing one edge.
1782         arguments: selected edge list, face list.
1783         Edges will also be tagged accordingly (see eed->f2)          */
1784
1785 static int collect_quadedges(EVPTuple *efaa, EditEdge *eed, EditFace *efa)
1786 {
1787         int i = 0;
1788         EditEdge *e1, *e2, *e3;
1789         EVPtr *evp;
1790
1791         /* run through edges, if selected, set pointer edge-> facearray */
1792         while(eed) {
1793                 eed->f2= 0;
1794                 eed->f1= 0;
1795                 if( eed->f & SELECT ) {
1796                         eed->vn= (EditVert *) (&efaa[i]);
1797                         i++;
1798                 }
1799                 eed= eed->next;
1800         }
1801                 
1802         
1803         /* find edges pointing to 2 faces by procedure:
1804         
1805         - run through faces and their edges, increase
1806           face counter e->f1 for each face 
1807         */
1808
1809         while(efa) {
1810                 efa->f1= 0;
1811                 if(efa->v4==0) {  /* if triangle */
1812                         if(efa->f & SELECT) {
1813                                 
1814                                 e1= efa->e1;
1815                                 e2= efa->e2;
1816                                 e3= efa->e3;
1817                                 if(e1->f2<3) {
1818                                         if(e1->f2<2) {
1819                                                 evp= (EVPtr *) e1->vn;
1820                                                 evp[(int)e1->f2]= efa;
1821                                         }
1822                                         e1->f2+= 1;
1823                                 }
1824                                 if(e2->f2<3) {
1825                                         if(e2->f2<2) {
1826                                                 evp= (EVPtr *) e2->vn;
1827                                                 evp[(int)e2->f2]= efa;
1828                                         }
1829                                         e2->f2+= 1;
1830                                 }
1831                                 if(e3->f2<3) {
1832                                         if(e3->f2<2) {
1833                                                 evp= (EVPtr *) e3->vn;
1834                                                 evp[(int)e3->f2]= efa;
1835                                         }
1836                                         e3->f2+= 1;
1837                                 }
1838                         }
1839                 }
1840                 efa= efa->next;
1841         }
1842         return i;
1843 }
1844
1845
1846 /* returns vertices of two adjacent triangles forming a quad 
1847    - can be righthand or lefthand
1848
1849                         4-----3
1850                         |\    |
1851                         | \ 2 | <- efa1
1852                         |  \  | 
1853           efa-> | 1 \ | 
1854                         |    \| 
1855                         1-----2
1856
1857 */
1858 #define VTEST(face, num, other) \
1859         (face->v##num != other->v1 && face->v##num != other->v2 && face->v##num != other->v3) 
1860
1861 static void givequadverts(EditFace *efa, EditFace *efa1, EditVert **v1, EditVert **v2, EditVert **v3, EditVert **v4, float **uv, unsigned int *col)
1862 {
1863         if VTEST(efa, 1, efa1) {
1864         //if(efa->v1!=efa1->v1 && efa->v1!=efa1->v2 && efa->v1!=efa1->v3) {
1865                 *v1= efa->v1;
1866                 *v2= efa->v2;
1867                 uv[0] = efa->tf.uv[0];
1868                 uv[1] = efa->tf.uv[1];
1869                 col[0] = efa->tf.col[0];
1870                 col[1] = efa->tf.col[1];
1871         }
1872         else if VTEST(efa, 2, efa1) {
1873         //else if(efa->v2!=efa1->v1 && efa->v2!=efa1->v2 && efa->v2!=efa1->v3) {
1874                 *v1= efa->v2;
1875                 *v2= efa->v3;
1876                 uv[0] = efa->tf.uv[1];
1877                 uv[1] = efa->tf.uv[2];
1878                 col[0] = efa->tf.col[1];
1879                 col[1] = efa->tf.col[2];
1880         }
1881         else if VTEST(efa, 3, efa1) {
1882         // else if(efa->v3!=efa1->v1 && efa->v3!=efa1->v2 && efa->v3!=efa1->v3) {
1883                 *v1= efa->v3;
1884                 *v2= efa->v1;
1885                 uv[0] = efa->tf.uv[2];
1886                 uv[1] = efa->tf.uv[0];
1887                 col[0] = efa->tf.col[2];
1888                 col[1] = efa->tf.col[0];
1889         }
1890         
1891         if VTEST(efa1, 1, efa) {
1892         // if(efa1->v1!=efa->v1 && efa1->v1!=efa->v2 && efa1->v1!=efa->v3) {
1893                 *v3= efa1->v1;
1894                 uv[2] = efa1->tf.uv[0];
1895                 col[2] = efa1->tf.col[0];
1896
1897                 *v4= efa1->v2;
1898                 uv[3] = efa1->tf.uv[1];
1899                 col[3] = efa1->tf.col[1];
1900 /*
1901 if(efa1->v2== *v2) {
1902                         *v4= efa1->v3;
1903                         uv[3] = efa1->tf.uv[2];
1904                 } else {
1905                         *v4= efa1->v2;
1906                         uv[3] = efa1->tf.uv[1];
1907                 }       
1908                 */
1909         }
1910         else if VTEST(efa1, 2, efa) {
1911         // else if(efa1->v2!=efa->v1 && efa1->v2!=efa->v2 && efa1->v2!=efa->v3) {
1912                 *v3= efa1->v2;
1913                 uv[2] = efa1->tf.uv[1];
1914                 col[2] = efa1->tf.col[1];
1915
1916                 *v4= efa1->v3;
1917                 uv[3] = efa1->tf.uv[2];
1918                 col[3] = efa1->tf.col[2];
1919 /*
1920 if(efa1->v3== *v2) {
1921                         *v4= efa1->v1;
1922                         uv[3] = efa1->tf.uv[0];
1923                 } else {        
1924                         *v4= efa1->v3;
1925                         uv[3] = efa1->tf.uv[2];
1926                 }       
1927                 */
1928         }
1929         else if VTEST(efa1, 3, efa) {
1930         // else if(efa1->v3!=efa->v1 && efa1->v3!=efa->v2 && efa1->v3!=efa->v3) {
1931                 *v3= efa1->v3;
1932                 uv[2] = efa1->tf.uv[2];
1933                 col[2] = efa1->tf.col[2];
1934
1935                 *v4= efa1->v1;
1936                 uv[3] = efa1->tf.uv[0];
1937                 col[3] = efa1->tf.col[0];
1938 /*
1939 if(efa1->v1== *v2) {
1940                         *v4= efa1->v2;
1941                         uv[3] = efa1->tf.uv[3];
1942                 } else {        
1943                         *v4= efa1->v1;
1944                         uv[3] = efa1->tf.uv[0];
1945                 }       
1946                 */
1947         }
1948         else {
1949                 printf("error in givequadverts()\n");
1950                 return;
1951         }
1952         
1953 }
1954
1955 /* Helper functions for edge/quad edit features*/
1956
1957 static void untag_edges(EditFace *f)
1958 {
1959         f->e1->f2 = 0;
1960         f->e2->f2 = 0;
1961         if (f->e3) f->e3->f2 = 0;
1962         if (f->e4) f->e4->f2 = 0;
1963 }
1964
1965 /** remove and free list of tagged edges */
1966 static void free_tagged_edgelist(EditEdge *eed)
1967 {
1968         EditEdge *nexted;
1969
1970         while(eed) {
1971                 nexted= eed->next;
1972                 if(eed->f1) {
1973                         remedge(eed);
1974                         free_editedge(eed);
1975                 }
1976                 eed= nexted;
1977         }       
1978 }       
1979 /** remove and free list of tagged faces */
1980
1981 static void free_tagged_facelist(EditFace *efa)
1982 {       
1983         EditMesh *em = G.editMesh;
1984         EditFace *nextvl;
1985
1986         while(efa) {
1987                 nextvl= efa->next;
1988                 if(efa->f1) {
1989                         BLI_remlink(&em->faces, efa);
1990                         free_editface(efa);
1991                 }
1992                 efa= nextvl;
1993         }
1994 }       
1995
1996
1997 void beauty_fill(void)
1998 {
1999     EditMesh *em = G.editMesh;
2000     EditVert *v1, *v2, *v3, *v4;
2001     EditEdge *eed, *nexted;
2002     EditEdge dia1, dia2;
2003     EditFace *efa, *w;
2004     // void **efaar, **efaa;
2005     EVPTuple *efaar;
2006     EVPtr *efaa;
2007     float *uv[4];
2008     unsigned int col[4];
2009     float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2;
2010     int totedge, ok, notbeauty=8, onedone;
2011
2012         /* - all selected edges with two faces
2013                 * - find the faces: store them in edges (using datablock)
2014                 * - per edge: - test convex
2015                 *                          - test edge: flip?
2016                 *               - if true: remedge,  addedge, all edges at the edge get new face pointers
2017                 */
2018         
2019         EM_selectmode_flush();  // makes sure in selectmode 'face' the edges of selected faces are selected too 
2020
2021     totedge = count_selected_edges(em->edges.first);
2022     if(totedge==0) return;
2023
2024     if(okee("Beautify fill")==0) return;
2025     
2026     /* temp block with face pointers */
2027     efaar= (EVPTuple *) MEM_callocN(totedge * sizeof(EVPTuple), "beautyfill");
2028
2029     while (notbeauty) {
2030         notbeauty--;
2031
2032         ok = collect_quadedges(efaar, em->edges.first, em->faces.first);
2033
2034         /* there we go */
2035         onedone= 0;
2036
2037         eed= em->edges.first;
2038         while(eed) {
2039             nexted= eed->next;
2040
2041             if(eed->f2==2) {
2042
2043                 efaa = (EVPtr *) eed->vn;
2044
2045                 /* none of the faces should be treated before */
2046                 ok= 1;
2047                 efa= efaa[0];
2048                 if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
2049                 efa= efaa[1];
2050                 if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
2051
2052                 if(ok) {
2053                     /* test convex */
2054                     givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, uv, col);
2055                     if( convex(v1->co, v2->co, v3->co, v4->co) ) {
2056
2057                         /* test edges */
2058                         if( ((long)v1) > ((long)v3) ) {
2059                             dia1.v1= v3;
2060                             dia1.v2= v1;
2061                         }
2062                         else {
2063                             dia1.v1= v1;
2064                             dia1.v2= v3;
2065                         }
2066
2067                         if( ((long)v2) > ((long)v4) ) {
2068                             dia2.v1= v4;
2069                             dia2.v2= v2;
2070                         }
2071                         else {
2072                             dia2.v1= v2;
2073                             dia2.v2= v4;
2074                         }
2075
2076                         /* testing rule:
2077                          * the area divided by the total edge lengths
2078                          */
2079
2080                         len1= VecLenf(v1->co, v2->co);
2081                         len2= VecLenf(v2->co, v3->co);
2082                         len3= VecLenf(v3->co, v4->co);
2083                         len4= VecLenf(v4->co, v1->co);
2084                         len5= VecLenf(v1->co, v3->co);
2085                         len6= VecLenf(v2->co, v4->co);
2086
2087                         opp1= AreaT3Dfl(v1->co, v2->co, v3->co);
2088                         opp2= AreaT3Dfl(v1->co, v3->co, v4->co);
2089
2090                         fac1= opp1/(len1+len2+len5) + opp2/(len3+len4+len5);
2091
2092                         opp1= AreaT3Dfl(v2->co, v3->co, v4->co);
2093                         opp2= AreaT3Dfl(v2->co, v4->co, v1->co);
2094
2095                         fac2= opp1/(len2+len3+len6) + opp2/(len4+len1+len6);
2096
2097                         ok= 0;
2098                         if(fac1 > fac2) {
2099                             if(dia2.v1==eed->v1 && dia2.v2==eed->v2) {
2100                                 eed->f1= 1;
2101                                 efa= efaa[0];
2102                                 efa->f1= 1;
2103                                 efa= efaa[1];
2104                                 efa->f1= 1;
2105
2106                                 w= addfacelist(v1, v2, v3, 0, efa, NULL);
2107
2108                                                                 UVCOPY(w->tf.uv[0], uv[0]);
2109                                                                 UVCOPY(w->tf.uv[1], uv[1]);
2110                                                                 UVCOPY(w->tf.uv[2], uv[2]);
2111
2112                                 w->tf.col[0] = col[0]; w->tf.col[1] = col[1]; w->tf.col[2] = col[2];
2113                                 w= addfacelist(v1, v3, v4, 0, efa, NULL);
2114
2115                                                                 UVCOPY(w->tf.uv[0], uv[0]);
2116                                                                 UVCOPY(w->tf.uv[1], uv[2]);
2117                                                                 UVCOPY(w->tf.uv[2], uv[3]);
2118
2119                                 w->tf.col[0] = col[0]; w->tf.col[1] = col[2]; w->tf.col[2] = col[3];
2120
2121                                 onedone= 1;
2122                             }
2123                         }
2124                         else if(fac1 < fac2) {
2125                             if(dia1.v1==eed->v1 && dia1.v2==eed->v2) {
2126                                 eed->f1= 1;
2127                                 efa= efaa[0];
2128                                 efa->f1= 1;
2129                                 efa= efaa[1];
2130                                 efa->f1= 1;
2131
2132                                 w= addfacelist(v2, v3, v4, 0, efa, NULL);
2133
2134                                                                 UVCOPY(w->tf.uv[0], uv[1]);
2135                                                                 UVCOPY(w->tf.uv[1], uv[3]);
2136                                                                 UVCOPY(w->tf.uv[2], uv[4]);
2137
2138                                 w= addfacelist(v1, v2, v4, 0, efa, NULL);
2139
2140                                                                 UVCOPY(w->tf.uv[0], uv[0]);
2141                                                                 UVCOPY(w->tf.uv[1], uv[1]);
2142                                                                 UVCOPY(w->tf.uv[2], uv[3]);
2143
2144                                 onedone= 1;
2145                             }
2146                         }
2147                     }
2148                 }
2149
2150             }
2151             eed= nexted;
2152         }
2153
2154         free_tagged_edgelist(em->edges.first);
2155         free_tagged_facelist(em->faces.first);
2156
2157         if(onedone==0) break;
2158     }
2159
2160     MEM_freeN(efaar);
2161
2162         EM_select_flush();
2163         
2164     allqueue(REDRAWVIEW3D, 0);
2165     makeDispList(G.obedit);
2166         BIF_undo_push("Beauty Fill");
2167 }
2168
2169
2170 /* ******************** FLIP EDGE ************************************* */
2171
2172
2173 #define FACE_MARKCLEAR(f) (f->f1 = 1)
2174
2175 void join_triangles(void)
2176 {
2177         EditMesh *em = G.editMesh;
2178         EditVert *v1, *v2, *v3, *v4;
2179         EditFace *efa, *w;
2180         EVPTuple *efaar;
2181         EVPtr *efaa;
2182         EditEdge *eed, *nexted;
2183         int totedge, ok;
2184         float *uv[4];
2185         unsigned int col[4];
2186
2187         EM_selectmode_flush();  // makes sure in selectmode 'face' the edges of selected faces are selected too 
2188         
2189         totedge = count_selected_edges(em->edges.first);
2190         if(totedge==0) return;
2191
2192         efaar= (EVPTuple *) MEM_callocN(totedge * sizeof(EVPTuple), "jointris");
2193
2194         ok = collect_quadedges(efaar, em->edges.first, em->faces.first);
2195         if (G.f & G_DEBUG) {
2196                 printf("Edges selected: %d\n", ok);
2197         }       
2198
2199         eed= em->edges.first;
2200         while(eed) {
2201                 nexted= eed->next;
2202                 
2203                 if(eed->f2==2) {  /* points to 2 faces */
2204                         
2205                         efaa= (EVPtr *) eed->vn;
2206                         
2207                         /* don't do it if flagged */
2208
2209                         ok= 1;
2210                         efa= efaa[0];
2211                         if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
2212                         efa= efaa[1];
2213                         if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
2214                         
2215                         if(ok) {
2216                                 /* test convex */
2217                                 givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, uv, col);
2218
2219 /*
2220                 4-----3        4-----3
2221                 |\    |        |     |
2222                 | \ 1 |        |     |
2223                 |  \  |  ->    |     |  
2224                 | 0 \ |        |     | 
2225                 |    \|        |     |
2226                 1-----2        1-----2
2227 */
2228                                 /* make new faces */
2229                                 if( convex(v1->co, v2->co, v3->co, v4->co) ) {
2230                                         if(exist_face(v1, v2, v3, v4)==0) {
2231                                                 w = addfacelist(v1, v2, v3, v4, efaa[0], NULL); /* seam edge may get broken */
2232                                                 w->f= efaa[0]->f;       /* copy selection flag */
2233                                                 untag_edges(w);
2234
2235                                                 UVCOPY(w->tf.uv[0], uv[0]);
2236                                                 UVCOPY(w->tf.uv[1], uv[1]);
2237                                                 UVCOPY(w->tf.uv[2], uv[2]);
2238                                                 UVCOPY(w->tf.uv[3], uv[3]);
2239
2240                                                 memcpy(w->tf.col, col, sizeof(w->tf.col));
2241                                         }
2242                                         /* tag as to-be-removed */
2243                                         FACE_MARKCLEAR(efaa[0]);
2244                                         FACE_MARKCLEAR(efaa[1]);
2245                                         eed->f1 = 1; 
2246                                 } /* endif test convex */
2247                         }
2248                 }
2249                 eed= nexted;
2250         }
2251         free_tagged_edgelist(em->edges.first);
2252         free_tagged_facelist(em->faces.first);
2253
2254         MEM_freeN(efaar);
2255         
2256         allqueue(REDRAWVIEW3D, 0);
2257         makeDispList(G.obedit);
2258         BIF_undo_push("Convert Triangles to Quads");
2259 }
2260
2261 /* quick hack, basically a copy of beauty_fill */
2262 void edge_flip(void)
2263 {
2264         EditMesh *em = G.editMesh;
2265         EditVert *v1, *v2, *v3, *v4;
2266         EditEdge *eed, *nexted;
2267         EditFace *efa, *w;
2268         //void **efaar, **efaa;
2269         EVPTuple *efaar;
2270         EVPtr *efaa;
2271
2272         float *uv[4];
2273         unsigned int col[4];
2274
2275         int totedge, ok;
2276         
2277         /* - all selected edges with two faces
2278          * - find the faces: store them in edges (using datablock)
2279          * - per edge: - test convex
2280          *                         - test edge: flip?
2281                                                 - if true: remedge,  addedge, all edges at the edge get new face pointers
2282          */
2283
2284         EM_selectmode_flush();  // makes sure in selectmode 'face' the edges of selected faces are selected too 
2285
2286         totedge = count_selected_edges(em->edges.first);
2287         if(totedge==0) return;
2288
2289         /* temporary array for : edge -> face[1], face[2] */
2290         efaar= (EVPTuple *) MEM_callocN(totedge * sizeof(EVPTuple), "edgeflip");
2291
2292         ok = collect_quadedges(efaar, em->edges.first, em->faces.first);
2293         
2294         eed= em->edges.first;
2295         while(eed) {
2296                 nexted= eed->next;
2297                 
2298                 if(eed->f2==2) {  /* points to 2 faces */
2299                         
2300                         efaa= (EVPtr *) eed->vn;
2301                         
2302                         /* don't do it if flagged */
2303
2304                         ok= 1;
2305                         efa= efaa[0];
2306                         if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
2307                         efa= efaa[1];
2308                         if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
2309                         
2310                         if(ok) {
2311                                 /* test convex */
2312                                 givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, uv, col);
2313
2314 /*
2315                 4-----3        4-----3
2316                 |\    |        |    /|
2317                 | \ 1 |        | 1 / |
2318                 |  \  |  ->    |  /  |  
2319                 | 0 \ |        | / 0 | 
2320                 |    \|        |/    |
2321                 1-----2        1-----2
2322 */
2323                                 /* make new faces */
2324                                 if (v1 && v2 && v3){
2325                                         if( convex(v1->co, v2->co, v3->co, v4->co) ) {
2326                                                 if(exist_face(v1, v2, v3, v4)==0) {
2327                                                         w = addfacelist(v1, v2, v3, 0, efaa[1], NULL); /* outch this may break seams */ 
2328                                                         EM_select_face(w, 1);
2329                                                         untag_edges(w);
2330
2331                                                         UVCOPY(w->tf.uv[0], uv[0]);
2332                                                         UVCOPY(w->tf.uv[1], uv[1]);
2333                                                         UVCOPY(w->tf.uv[2], uv[2]);
2334
2335                                                         w->tf.col[0] = col[0]; w->tf.col[1] = col[1]; w->tf.col[2] = col[2]; 
2336                                                         
2337                                                         w = addfacelist(v1, v3, v4, 0, efaa[1], NULL); /* outch this may break seams */
2338                                                         EM_select_face(w, 1);
2339                                                         untag_edges(w);
2340
2341                                                         UVCOPY(w->tf.uv[0], uv[0]);
2342                                                         UVCOPY(w->tf.uv[1], uv[2]);
2343                                                         UVCOPY(w->tf.uv[2], uv[3]);
2344
2345                                                         w->tf.col[0] = col[0]; w->tf.col[1] = col[2]; w->tf.col[2] = col[3]; 
2346                                                         
2347                                                         /* erase old faces and edge */
2348                                                 }
2349                                                 /* tag as to-be-removed */
2350                                                 FACE_MARKCLEAR(efaa[1]);
2351                                                 FACE_MARKCLEAR(efaa[0]);
2352                                                 eed->f1 = 1; 
2353                                                 
2354                                         } /* endif test convex */
2355                                 }
2356                         }
2357                 }
2358                 eed= nexted;
2359         }
2360
2361         /* clear tagged edges and faces: */
2362         free_tagged_edgelist(em->edges.first);
2363         free_tagged_facelist(em->faces.first);
2364         
2365         MEM_freeN(efaar);
2366         
2367         allqueue(REDRAWVIEW3D, 0);
2368         makeDispList(G.obedit);
2369         BIF_undo_push("Flip Triangle Edges");
2370         
2371 }
2372
2373 static void edge_rotate(EditEdge *eed)
2374 {
2375         EditMesh *em = G.editMesh;
2376         EditFace *face[2], *efa, *newFace[2];
2377         EditVert *faces[2][4],*v1,*v2,*v3,*v4,*vtemp;
2378         short facecount=0, p1=0,p2=0,p3=0,p4=0,fac1=4,fac2=4,i,j;
2379
2380         /* check to make sure that the edge is only part of 2 faces */
2381         for(efa = em->faces.first;efa;efa = efa->next){
2382                 if((efa->e1 == eed || efa->e2 == eed) || (efa->e3 == eed || efa->e4 == eed)){
2383                         if(facecount == 2){
2384                                 scrarea_do_windraw(curarea);  /// what is this for? (ton)
2385                                 screen_swapbuffers();
2386                                 return;
2387                         }
2388                         if(facecount < 2)
2389                                 face[facecount] = efa;
2390                         facecount++;
2391                 }
2392         }
2393  
2394         
2395         if(facecount < 2){
2396                 return;
2397         }
2398         
2399
2400         /* how many edges does each face have */
2401         if(face[0]->e4 == NULL)
2402                 fac1=3;
2403         else
2404                 fac1=4;
2405         if(face[1]->e4 == NULL)
2406                 fac2=3;
2407         else
2408                 fac2=4;
2409         
2410                 
2411         /*store the face info in a handy array */                       
2412         faces[0][0] =  face[0]->v1;
2413         faces[0][1] =  face[0]->v2;
2414         faces[0][2] =  face[0]->v3;
2415         if(face[0]->e4 != NULL)
2416                 faces[0][3] =  face[0]->v4;
2417         else
2418                 faces[0][3] = NULL;
2419                         
2420         faces[1][0] =  face[1]->v1;
2421         faces[1][1] =  face[1]->v2;
2422         faces[1][2] =  face[1]->v3;
2423         if(face[1]->e4 != NULL)
2424                 faces[1][3] =  face[1]->v4;
2425         else
2426                 faces[1][3] = NULL;
2427         
2428
2429         /* we don't want to rotate edges between faces that share more than one edge */
2430         
2431         j=0;
2432         if(face[0]->e1 == face[1]->e1 ||
2433            face[0]->e1 == face[1]->e2 ||
2434            face[0]->e1 == face[1]->e3 ||
2435            ((face[1]->e4) && face[0]->e1 == face[1]->e4) )
2436            j++;
2437            
2438         if(face[0]->e2 == face[1]->e1 ||
2439            face[0]->e2 == face[1]->e2 ||
2440            face[0]->e2 == face[1]->e3 ||
2441            ((face[1]->e4) && face[0]->e2 == face[1]->e4) )
2442            j++;
2443            
2444         if(face[0]->e3 == face[1]->e1 ||
2445            face[0]->e3 == face[1]->e2 ||
2446            face[0]->e3 == face[1]->e3 ||
2447            ((face[1]->e4) && face[0]->e3 == face[1]->e4) )
2448            j++;    
2449
2450         if(face[0]->e4){
2451                 if(face[0]->e4 == face[1]->e1 ||
2452                    face[0]->e4 == face[1]->e2 ||
2453                    face[0]->e4 == face[1]->e3 ||
2454                    ((face[1]->e4) && face[0]->e4 == face[1]->e4) )
2455                            j++; 
2456          }                 
2457         if(j > 1){
2458                 return;
2459         }
2460         
2461         /* Coplaner Faces Only Please */
2462         if(Inpf(face[0]->n,face[1]->n) <= 0.000001){    
2463                 return;
2464         }
2465         
2466         /*get the edges verts */
2467         v1 = eed->v1;
2468         v2 = eed->v2;
2469         v3 = eed->v1;
2470         v4 = eed->v2;
2471
2472
2473         /*figure out where the edges verts lie one the 2 faces */
2474         for(i=0;i<4;i++){
2475                 if(v1 == faces[0][i])
2476                         p1 = i;
2477                 if(v2 == faces[0][i])
2478                         p2 = i;
2479                 if(v1 == faces[1][i])
2480                         p3 = i;
2481                 if(v2 == faces[1][i])
2482                         p4 = i;
2483         }
2484         
2485         /*make sure the verts are in the correct order */
2486         if((p1+1)%fac1 == p2){
2487                 vtemp = v2;
2488                 v2 = v1;
2489                 v1 = vtemp;
2490                 
2491                 i = p1;
2492                 p1 = p2;
2493                 p2 = i;
2494         }
2495         if((p3+1)%fac2 == p4){
2496                 vtemp = v4;
2497                 v4 = v3;
2498                 v3 = vtemp;
2499                 
2500                 i = p3;
2501                 p3 = p4;
2502                 p4 = i; 
2503         }       
2504
2505                                         
2506                                                         
2507         /* create the 2 new faces */                                                            
2508         if(fac1 == 3 && fac2 == 3){
2509                 newFace[0] = addfacelist(faces[0][(p1+1)%3],faces[0][(p1+2)%3],faces[1][(p3+1)%3],NULL,NULL,NULL);
2510                 newFace[1] = addfacelist(faces[1][(p3+1)%3],faces[1][(p3+2)%3],faces[0][(p1+1)%3],NULL,NULL,NULL);
2511         
2512                 newFace[0]->tf.col[0] = face[0]->tf.col[(p1+1)%3];
2513                 newFace[0]->tf.col[1] = face[0]->tf.col[(p1+2)%3];
2514                 newFace[0]->tf.col[2] = face[1]->tf.col[(p3+1)%3];
2515                 newFace[1]->tf.col[0] = face[1]->tf.col[(p3+1)%3];
2516                 newFace[1]->tf.col[1] = face[1]->tf.col[(p3+2)%3];
2517                 newFace[1]->tf.col[2] = face[0]->tf.col[(p1+1)%3];
2518         
2519                 UVCOPY(newFace[0]->tf.uv[0],face[0]->tf.uv[(p1+1)%3]);
2520                 UVCOPY(newFace[0]->tf.uv[1],face[0]->tf.uv[(p1+2)%3]);  
2521                 UVCOPY(newFace[0]->tf.uv[2],face[1]->tf.uv[(p3+1)%3]);
2522                 UVCOPY(newFace[1]->tf.uv[0],face[1]->tf.uv[(p3+1)%3]);
2523                 UVCOPY(newFace[1]->tf.uv[1],face[1]->tf.uv[(p3+2)%3]);
2524                 UVCOPY(newFace[1]->tf.uv[2],face[0]->tf.uv[(p1+1)%3]);
2525         }
2526         else if(fac1 == 4 && fac2 == 3){
2527                 newFace[0] = addfacelist(faces[0][(p1+1)%4],faces[0][(p1+2)%4],faces[0][(p1+3)%4],faces[1][(p3+1)%3],NULL,NULL);
2528                 newFace[1] = addfacelist(faces[1][(p3+1)%3],faces[1][(p3+2)%3],faces[0][(p1+1)%4],NULL,NULL,NULL);
2529
2530                 newFace[0]->tf.col[0] = face[0]->tf.col[(p1+1)%4];
2531                 newFace[0]->tf.col[1] = face[0]->tf.col[(p1+2)%4];
2532                 newFace[0]->tf.col[2] = face[0]->tf.col[(p1+3)%4];
2533                 newFace[0]->tf.col[3] = face[1]->tf.col[(p3+1)%3];
2534                 newFace[1]->tf.col[0] = face[1]->tf.col[(p3+1)%3];
2535                 newFace[1]->tf.col[1] = face[1]->tf.col[(p3+2)%3];
2536                 newFace[1]->tf.col[2] = face[0]->tf.col[(p1+1)%4];
2537
2538                 UVCOPY(newFace[0]->tf.uv[0],face[0]->tf.uv[(p1+1)%4]);
2539                 UVCOPY(newFace[0]->tf.uv[1],face[0]->tf.uv[(p1+2)%4]);  
2540                 UVCOPY(newFace[0]->tf.uv[2],face[0]->tf.uv[(p1+3)%4]);          
2541                 UVCOPY(newFace[0]->tf.uv[3],face[1]->tf.uv[(p3+1)%3]);
2542                 UVCOPY(newFace[1]->tf.uv[0],face[1]->tf.uv[(p3+1)%3]);
2543                 UVCOPY(newFace[1]->tf.uv[1],face[1]->tf.uv[(p3+2)%3]);
2544                 UVCOPY(newFace[1]->tf.uv[2],face[0]->tf.uv[(p1+1)%4]);  
2545         }
2546
2547         else if(fac1 == 3 && fac2 == 4){
2548                 newFace[0] = addfacelist(faces[0][(p1+1)%3],faces[0][(p1+2)%3],faces[1][(p3+1)%4],NULL,NULL,NULL);
2549                 newFace[1] = addfacelist(faces[1][(p3+1)%4],faces[1][(p3+2)%4],faces[1][(p3+3)%4],faces[0][(p1+1)%3],NULL,NULL);
2550
2551                 newFace[0]->tf.col[0] = face[0]->tf.col[(p1+1)%3];
2552                 newFace[0]->tf.col[1] = face[0]->tf.col[(p1+2)%3];
2553                 newFace[0]->tf.col[2] = face[1]->tf.col[(p3+1)%4];
2554                 newFace[1]->tf.col[0] = face[1]->tf.col[(p3+1)%4];
2555                 newFace[1]->tf.col[1] = face[1]->tf.col[(p3+2)%4];
2556                 newFace[1]->tf.col[2] = face[1]->tf.col[(p3+3)%4];              
2557                 newFace[1]->tf.col[3] = face[0]->tf.col[(p1+1)%3];
2558
2559                 UVCOPY(newFace[0]->tf.uv[0],face[0]->tf.uv[(p1+1)%3]);
2560                 UVCOPY(newFace[0]->tf.uv[1],face[0]->tf.uv[(p1+2)%3]);  
2561                 UVCOPY(newFace[0]->tf.uv[2],face[1]->tf.uv[(p3+1)%4]);
2562                 UVCOPY(newFace[1]->tf.uv[0],face[1]->tf.uv[(p3+1)%4]);
2563                 UVCOPY(newFace[1]->tf.uv[1],face[1]->tf.uv[(p3+2)%4]);
2564                 UVCOPY(newFace[1]->tf.uv[2],face[1]->tf.uv[(p3+3)%4]);
2565                 UVCOPY(newFace[1]->tf.uv[3],face[0]->tf.uv[(p1+1)%3]);
2566         
2567         }
2568         
2569         else if(fac1 == 4 && fac2 == 4){
2570                 newFace[0] = addfacelist(faces[0][(p1+1)%4],faces[0][(p1+2)%4],faces[0][(p1+3)%4],faces[1][(p3+1)%4],NULL,NULL);
2571                 newFace[1] = addfacelist(faces[1][(p3+1)%4],faces[1][(p3+2)%4],faces[1][(p3+3)%4],faces[0][(p1+1)%4],NULL,NULL);
2572
2573                 newFace[0]->tf.col[0] = face[0]->tf.col[(p1+1)%4];
2574                 newFace[0]->tf.col[1] = face[0]->tf.col[(p1+2)%4];
2575                 newFace[0]->tf.col[2] = face[0]->tf.col[(p1+3)%4];
2576                 newFace[0]->tf.col[3] = face[1]->tf.col[(p3+1)%4];
2577                 newFace[1]->tf.col[0] = face[1]->tf.col[(p3+1)%4];
2578                 newFace[1]->tf.col[1] = face[1]->tf.col[(p3+2)%4];
2579                 newFace[1]->tf.col[2] = face[1]->tf.col[(p3+3)%4];              
2580                 newFace[1]->tf.col[3] = face[0]->tf.col[(p1+1)%4];
2581                                                                 
2582                 UVCOPY(newFace[0]->tf.uv[0],face[0]->tf.uv[(p1+1)%4]);
2583                 UVCOPY(newFace[0]->tf.uv[1],face[0]->tf.uv[(p1+2)%4]);  
2584                 UVCOPY(newFace[0]->tf.uv[2],face[0]->tf.uv[(p1+3)%4]);          
2585                 UVCOPY(newFace[0]->tf.uv[3],face[1]->tf.uv[(p3+1)%4]);
2586                 UVCOPY(newFace[1]->tf.uv[0],face[1]->tf.uv[(p3+1)%4]);
2587                 UVCOPY(newFace[1]->tf.uv[1],face[1]->tf.uv[(p3+2)%4]);
2588                 UVCOPY(newFace[1]->tf.uv[2],face[1]->tf.uv[(p3+3)%4]);
2589                 UVCOPY(newFace[1]->tf.uv[3],face[0]->tf.uv[(p1+1)%4]);  
2590         }               
2591         else{
2592                 /*This should never happen*/
2593                 return;
2594         }
2595
2596         if(fac1 == 3)
2597                 newFace[0]->e3->f2 |= 2;
2598         else if(fac1 == 4)
2599                 newFace[0]->e4->f2 |= 2;
2600         
2601         /* added this for proper select flags, probably whats below is obsolete then */
2602         EM_select_face(newFace[0], 1);
2603         EM_select_face(newFace[1], 1);
2604
2605         /* mark the f1's of the verts for re-selection */
2606         faces[0][(p1+1)%fac1]->f1 |= 1;
2607         faces[1][(p3+1)%fac2]->f1 |= 1; 
2608         
2609         /* get rid of the old edge and faces*/
2610         remedge(eed);
2611         free_editedge(eed);     
2612         BLI_remlink(&em->faces, face[0]);
2613         free_editface(face[0]); 
2614         BLI_remlink(&em->faces, face[1]);
2615         free_editface(face[1]); 
2616         
2617         return;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         
2618 }                                               
2619
2620
2621 void edge_rotate_selected()
2622 {
2623         EditEdge *eed,*temp;
2624         EditVert *ev;
2625         short edgeCount = 0;
2626         
2627         /* Clear the f1 flag */
2628         for(ev = G.editMesh->verts.first;ev;ev = ev->next)
2629                 ev->f1 &= ~1;
2630
2631         /*clear new flag for new edges*/
2632         for(eed = G.editMesh->edges.first;eed;eed = eed->next){
2633                 eed->f2 &= ~2;
2634                 edgeCount++;    
2635         }
2636         eed = G.editMesh->edges.first;          
2637         while(eed){
2638                 if(edgeCount-- < 0){
2639                         /* To prevent an infinite loop */
2640                         break;  
2641                 }
2642                 if(eed->f2 & 2){
2643                         /* Do not rotate newly created edges */
2644                         eed = eed->next;
2645                         continue;
2646                 }
2647                 if(eed->f & SELECT){    // changed this... (ton)
2648                         temp = eed;
2649                         eed = eed->next;
2650                         edge_rotate(temp);      
2651                 } else
2652                         eed = eed->next;
2653
2654         }
2655                 
2656         /*clear new edge flags*/
2657         for(eed = G.editMesh->edges.first; eed; eed = eed->next)
2658                 eed->f2 &= ~2;
2659
2660         /* flush selected vertices (again) to edges/faces */
2661         EM_select_flush();
2662         
2663         allqueue(REDRAWVIEW3D, 0);
2664         
2665         BIF_undo_push("Rotate Edges");  
2666 }
2667
2668 /******************* BEVEL CODE STARTS HERE ********************/
2669
2670 void bevel_displace_vec(float *midvec, float *v1, float *v2, float *v3, float d, float no[3])
2671 {
2672         float a[3], c[3], n_a[3], n_c[3], mid[3], ac, ac2, fac;
2673
2674         VecSubf(a, v1, v2);
2675         VecSubf(c, v3, v2);
2676
2677         Crossf(n_a, a, no);
2678         Normalise(n_a);
2679         Crossf(n_c, no, c);
2680         Normalise(n_c);
2681
2682         Normalise(a);
2683         Normalise(c);
2684         ac = Inpf(a, c);
2685
2686         if (ac == 1 || ac == -1) {
2687                 midvec[0] = midvec[1] = midvec[2] = 0;
2688                 return;
2689         }
2690         ac2 = ac * ac;
2691         fac = sqrt((ac2 + 2*ac + 1)/(1 - ac2) + 1);
2692         VecAddf(mid, n_c, n_a);
2693         Normalise(mid);
2694         VecMulf(mid, d * fac);
2695         VecAddf(mid, mid, v2);
2696         VecCopyf(midvec, mid);
2697 }
2698
2699 /*      Finds the new point using the sinus law to extrapolate a triangle
2700         Lots of sqrts which would not be good for a real time algo
2701         Using the mid  point of the extrapolation of both sides 
2702         Useless for coplanar quads, but that doesn't happen too often */
2703 void fix_bevel_wrap(float *midvec, float *v1, float *v2, float *v3, float *v4, float d, float no[3]) 
2704 {
2705         float a[3], b[3], c[3], l_a, l_b, l_c, s_a, s_b, s_c, Pos1[3], Pos2[3], Dir[3];
2706
2707         VecSubf(a, v3, v2);
2708         l_a = Normalise(a);
2709         VecSubf(b, v4, v3);
2710         Normalise(b);
2711         VecSubf(c, v1, v2);
2712         Normalise(c);
2713
2714         s_b = Inpf(a, c);
2715         s_b = sqrt(1 - (s_b * s_b));
2716         s_a = Inpf(b, c);
2717         s_a = sqrt(1 - (s_a * s_a));
2718         VecMulf(a, -1);
2719         s_c = Inpf(a, b);
2720         s_c = sqrt(1 - (s_c * s_c));
2721
2722         l_b = s_b * l_a / s_a;
2723         l_c = s_c * l_a / s_a;
2724
2725         VecMulf(b, l_b);
2726         VecMulf(c, l_c);
2727
2728         VecAddf(Pos1, v2, c);
2729         VecAddf(Pos2, v3, b);
2730
2731         VecAddf(Dir, Pos1, Pos2);
2732         VecMulf(Dir, 0.5);
2733
2734         bevel_displace_vec(midvec, v3, Dir, v2, d, no);
2735
2736 }
2737
2738
2739 char detect_wrap(float *o_v1, float *o_v2, float *v1, float *v2, float *no) 
2740 {
2741         float o_a[3], a[3], o_c[3], c[3];
2742
2743         VecSubf(o_a, o_v1, o_v2);
2744         VecSubf(a, v1, v2);
2745
2746         Crossf(o_c, o_a, no);
2747         Crossf(c, a, no);
2748
2749         if (Inpf(c, o_c) <= 0)
2750                 return 1;
2751         else
2752                 return 0;
2753 }
2754
2755 // Detects and fix a quad wrapping after the resize
2756 // Arguments are the orginal verts followed by the final verts and then the bevel size and the normal
2757 void fix_bevel_quad_wrap(float *o_v1, float *o_v2, float *o_v3, float *o_v4, float *v1, float *v2, float *v3, float *v4, float d, float *no) 
2758 {
2759         float vec[3];
2760         char wrap[4];
2761         
2762         // Quads can wrap partially. Watch out
2763         wrap[0] = detect_wrap(o_v1, o_v2, v1, v2, no); // Edge 1-2
2764         wrap[1] = detect_wrap(o_v2, o_v3, v2, v3, no); // Edge 2-3
2765         wrap[2] = detect_wrap(o_v3, o_v4, v3, v4, no); // Edge 3-4
2766         wrap[3] = detect_wrap(o_v4, o_v1, v4, v1, no); // Edge 4-1
2767
2768         // Edge 1 inverted
2769         if (wrap[0] == 1 && wrap[1] == 0 && wrap[2] == 0 && wrap[3] == 0) {
2770                 fix_bevel_wrap(vec, o_v2, o_v3, o_v4, o_v1, d, no);
2771                 VECCOPY(v1, vec);
2772                 VECCOPY(v2, vec);
2773         }
2774         // Edge 2 inverted
2775         else if (wrap[0] == 0 && wrap[1] == 1 && wrap[2] == 0 && wrap[3] == 0) {
2776                 fix_bevel_wrap(vec, o_v3, o_v4, o_v1, o_v2, d, no);
2777                 VECCOPY(v2, vec);
2778                 VECCOPY(v3, vec);
2779         }
2780         // Edge 3 inverted
2781         else if (wrap[0] == 0 && wrap[1] == 0 && wrap[2] == 1 && wrap[3] == 0) {
2782                 fix_bevel_wrap(vec, o_v4, o_v1, o_v2, o_v3, d, no);
2783                 VECCOPY(v3, vec);
2784                 VECCOPY(v4, vec);
2785         }
2786         // Edge 4 inverted
2787         else if (wrap[0] == 0 && wrap[1] == 0 && wrap[2] == 0 && wrap[3] == 1) {
2788                 fix_bevel_wrap(vec, o_v1, o_v2, o_v3, o_v4, d, no);
2789                 VECCOPY(v4, vec);
2790                 VECCOPY(v1, vec);
2791         }
2792         // Edge 2 and 4 inverted
2793         else if (wrap[0] == 0 && wrap[1] == 1 && wrap[2] == 0 && wrap[3] == 1) {
2794                 VecAddf(vec, v2, v3);
2795                 VecMulf(vec, 0.5);
2796                 VECCOPY(v2, vec);
2797                 VECCOPY(v3, vec);
2798                 VecAddf(vec, v1, v4);
2799                 VecMulf(vec, 0.5);
2800                 VECCOPY(v1, vec);
2801                 VECCOPY(v4, vec);
2802         }
2803         // Edge 1 and 3 inverted
2804         else if (wrap[0] == 1 && wrap[1] == 0 && wrap[2] == 1 && wrap[3] == 0) {
2805                 VecAddf(vec, v1, v2);
2806                 VecMulf(vec, 0.5);
2807                 VECCOPY(v1, vec);
2808                 VECCOPY(v2, vec);
2809                 VecAddf(vec, v3, v4);
2810                 VecMulf(vec, 0.5);
2811                 VECCOPY(v3, vec);
2812                 VECCOPY(v4, vec);
2813         }
2814         // Totally inverted
2815         else if (wrap[0] == 1 && wrap[1] == 1 && wrap[2] == 1 && wrap[3] == 1) {
2816                 VecAddf(vec, v1, v2);
2817                 VecAddf(vec, vec, v3);
2818                 VecAddf(vec, vec, v4);
2819                 VecMulf(vec, 0.25);
2820                 VECCOPY(v1, vec);
2821                 VECCOPY(v2, vec);
2822                 VECCOPY(v3, vec);
2823                 VECCOPY(v4, vec);
2824         }
2825
2826 }
2827
2828 // Detects and fix a tri wrapping after the resize
2829 // Arguments are the orginal verts followed by the final verts and the normal
2830 // Triangles cannot wrap partially (not in this situation
2831 void fix_bevel_tri_wrap(float *o_v1, float *o_v2, float *o_v3, float *v1, float *v2, float *v3, float *no) 
2832 {
2833         if (detect_wrap(o_v1, o_v2, v1, v2, no)) {
2834                 float vec[3];
2835                 VecAddf(vec, o_v1, o_v2);
2836                 VecAddf(vec, vec, o_v3);
2837                 VecMulf(vec, 1.0/3.0);
2838                 VECCOPY(v1, vec);
2839                 VECCOPY(v2, vec);
2840                 VECCOPY(v3, vec);
2841         }
2842 }
2843
2844 void bevel_shrink_faces(float d, int flag)
2845 {
2846         EditMesh *em = G.editMesh;
2847         EditFace *efa;
2848         float vec[3], no[3], v1[3], v2[3], v3[3], v4[3];
2849
2850         /* move edges of all faces with efa->f1 & flag closer towards their centres */
2851         efa= em->faces.first;
2852         while (efa) {
2853                 if (efa->f1 & flag) {
2854                         VECCOPY(v1, efa->v1->co);
2855                         VECCOPY(v2, efa->v2->co);                       
2856                         VECCOPY(v3, efa->v3->co);       
2857                         VECCOPY(no, efa->n);
2858                         if (efa->v4 == NULL) {
2859                                 bevel_displace_vec(vec, v1, v2, v3, d, no);
2860                                 VECCOPY(efa->v2->co, vec);
2861                                 bevel_displace_vec(vec, v2, v3, v1, d, no);
2862                                 VECCOPY(efa->v3->co, vec);              
2863                                 bevel_displace_vec(vec, v3, v1, v2, d, no);
2864                                 VECCOPY(efa->v1->co, vec);
2865
2866                                 fix_bevel_tri_wrap(v1, v2, v3, efa->v1->co, efa->v2->co, efa->v3->co, no);
2867                         } else {
2868                                 VECCOPY(v4, efa->v4->co);
2869                                 bevel_displace_vec(vec, v1, v2, v3, d, no);
2870                                 VECCOPY(efa->v2->co, vec);
2871                                 bevel_displace_vec(vec, v2, v3, v4, d, no);
2872                                 VECCOPY(efa->v3->co, vec);              
2873                                 bevel_displace_vec(vec, v3, v4, v1, d, no);
2874                                 VECCOPY(efa->v4->co, vec);              
2875                                 bevel_displace_vec(vec, v4, v1, v2, d, no);
2876                                 VECCOPY(efa->v1->co, vec);
2877
2878                                 fix_bevel_quad_wrap(v1, v2, v3, v4, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co, d, no);
2879                         }
2880                 }
2881                 efa= efa->next;
2882         }       
2883 }
2884
2885 void bevel_shrink_draw(float d, int flag)
2886 {
2887         EditMesh *em = G.editMesh;
2888         EditFace *efa;
2889         float vec[3], no[3], v1[3], v2[3], v3[3], v4[3], fv1[3], fv2[3], fv3[3], fv4[3];
2890
2891         /* move edges of all faces with efa->f1 & flag closer towards their centres */
2892         efa= em->faces.first;
2893         while (efa) {
2894                 VECCOPY(v1, efa->v1->co);
2895                 VECCOPY(v2, efa->v2->co);                       
2896                 VECCOPY(v3, efa->v3->co);       
2897                 VECCOPY(no, efa->n);
2898                 if (efa->v4 == NULL) {
2899                         bevel_displace_vec(vec, v1, v2, v3, d, no);
2900                         VECCOPY(fv2, vec);
2901                         bevel_displace_vec(vec, v2, v3, v1, d, no);
2902                         VECCOPY(fv3, vec);              
2903                         bevel_displace_vec(vec, v3, v1, v2, d, no);
2904                         VECCOPY(fv1, vec);
2905
2906                         fix_bevel_tri_wrap(v1, v2, v3, fv1, fv2, fv3, no);
2907
2908                         glBegin(GL_LINES);
2909                         glVertex3fv(fv1);
2910                         glVertex3fv(fv2);
2911                         glEnd();                                                
2912                         glBegin(GL_LINES);
2913                         glVertex3fv(fv2);
2914                         glVertex3fv(fv3);
2915                         glEnd();                                                
2916                         glBegin(GL_LINES);
2917                         glVertex3fv(fv1);
2918                         glVertex3fv(fv3);
2919                         glEnd();                                                
2920                 } else {
2921                         VECCOPY(v4, efa->v4->co);
2922                         bevel_displace_vec(vec, v4, v1, v2, d, no);
2923                         VECCOPY(fv1, vec);
2924                         bevel_displace_vec(vec, v1, v2, v3, d, no);
2925                         VECCOPY(fv2, vec);
2926                         bevel_displace_vec(vec, v2, v3, v4, d, no);
2927                         VECCOPY(fv3, vec);              
2928                         bevel_displace_vec(vec, v3, v4, v1, d, no);
2929                         VECCOPY(fv4, vec);              
2930
2931                         fix_bevel_quad_wrap(v1, v2, v3, v4, fv1, fv2, fv3, fv4, d, no);
2932
2933                         glBegin(GL_LINES);
2934                         glVertex3fv(fv1);
2935                         glVertex3fv(fv2);
2936                         glEnd();                                                
2937                         glBegin(GL_LINES);
2938                         glVertex3fv(fv2);
2939                         glVertex3fv(fv3);
2940                         glEnd();                                                
2941                         glBegin(GL_LINES);
2942                         glVertex3fv(fv3);
2943                         glVertex3fv(fv4);
2944                         glEnd();                                                
2945                         glBegin(GL_LINES);
2946                         glVertex3fv(fv1);
2947                         glVertex3fv(fv4);
2948                         glEnd();                                                
2949                 }
2950                 efa= efa->next;
2951         }       
2952 }
2953
2954 void bevel_mesh(float bsize, int allfaces)
2955 {
2956         EditMesh *em = G.editMesh;
2957 //#define BEV_DEBUG
2958 /* Enables debug printfs and assigns material indices: */
2959 /* 2 = edge quad                                       */
2960 /* 3 = fill polygon (vertex clusters)                  */
2961
2962         EditFace *efa, *example; //, *nextvl;
2963         EditEdge *eed, *eed2;
2964         EditVert *neweve[1024], *eve, *eve2, *eve3, *v1, *v2, *v3, *v4; //, *eve4;
2965         //short found4,  search;
2966         //float f1, f2, f3, f4;
2967         float cent[3], min[3], max[3];
2968         int a, b, c;
2969         float limit= 0.001;
2970
2971         waitcursor(1);
2972
2973         removedoublesflag(1, limit);
2974
2975         /* tag all original faces */
2976         efa= em->faces.first;
2977         while (efa) {
2978                 efa->f1= 0;
2979                 if (faceselectedAND(efa, 1)||allfaces) {
2980                         efa->f1= 1;
2981                         efa->v1->f |= 128;
2982                         efa->v2->f |= 128;
2983