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