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