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