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