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