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