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