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