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