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