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