Fix #27224: Extrude Repeat Mesh doesn't have options
[blender-staging.git] / source / blender / editors / mesh / editmesh_tools.c
1  /* $Id$
2  *
3  * ***** BEGIN GPL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18  *
19  * The Original Code is Copyright (C) 2004 by Blender Foundation.
20  * All rights reserved.
21  *
22  * The Original Code is: all of this file.
23  *
24  * Contributor(s): Johnny Matthews, Geoffrey Bantle.
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 /** \file blender/editors/mesh/editmesh_tools.c
30  *  \ingroup edmesh
31  */
32
33
34 /*
35
36 editmesh_tool.c: UI called tools for editmesh, geometry changes here, otherwise in mods.c
37
38 */
39
40 #include <stdlib.h>
41 #include <string.h>
42 #include <math.h>
43 #include <float.h>
44
45 #include "BLO_sys_types.h" // for intptr_t support
46
47 #include "DNA_meshdata_types.h"
48 #include "DNA_modifier_types.h"
49 #include "DNA_object_types.h"
50 #include "DNA_scene_types.h"
51 #include "DNA_key_types.h"
52
53 #include "MEM_guardedalloc.h"
54
55 #include "RNA_define.h"
56 #include "RNA_access.h"
57
58 #include "BLI_blenlib.h"
59 #include "BLI_math.h"
60 #include "BLI_utildefines.h"
61 #include "BLI_editVert.h"
62 #include "BLI_rand.h"
63 #include "BLI_ghash.h"
64 #include "BLI_linklist.h"
65 #include "BLI_heap.h"
66 #include "BLI_scanfill.h"
67
68 #include "BKE_context.h"
69 #include "BKE_depsgraph.h"
70 #include "BKE_global.h"
71 #include "BKE_key.h"
72 #include "BKE_mesh.h"
73 #include "BKE_bmesh.h"
74 #include "BKE_report.h"
75
76
77 #include "WM_api.h"
78 #include "WM_types.h"
79
80 #include "ED_mesh.h"
81 #include "ED_screen.h"
82 #include "ED_transform.h"
83 #include "ED_view3d.h"
84 #include "ED_object.h"
85
86
87 #include "mesh_intern.h"
88
89 /* XXX */
90 static void waitcursor(int UNUSED(val)) {}
91 #define add_numbut(a, b, c, d, e, f, g) {}
92
93 /* XXX */
94
95 /* RNA corner cut enum property - used in multiple files for tools
96  * that need this property for esubdivideflag() */
97 EnumPropertyItem corner_type_items[] = {
98         {SUBDIV_CORNER_PATH,  "PATH", 0, "Path", ""},
99         {SUBDIV_CORNER_INNERVERT,  "INNER_VERTEX", 0, "Inner Vertex", ""},
100         {SUBDIV_CORNER_FAN,  "FAN",  0, "Fan", ""},
101         {0, NULL, 0, NULL, NULL}};
102
103
104 /* local prototypes ---------------*/
105 static void free_tagged_edges_faces(EditMesh *em, EditEdge *eed, EditFace *efa);
106 int EdgeLoopDelete(EditMesh *em, wmOperator *op);
107
108 /********* qsort routines *********/
109
110
111 typedef struct xvertsort {
112         float x;
113         EditVert *v1;
114 } xvertsort;
115
116 static int vergxco(const void *v1, const void *v2)
117 {
118         const xvertsort *x1=v1, *x2=v2;
119
120         if( x1->x > x2->x ) return 1;
121         else if( x1->x < x2->x) return -1;
122         return 0;
123 }
124
125 struct facesort {
126         uintptr_t x;
127         struct EditFace *efa;
128 };
129
130
131 static int vergface(const void *v1, const void *v2)
132 {
133         const struct facesort *x1=v1, *x2=v2;
134
135         if( x1->x > x2->x ) return 1;
136         else if( x1->x < x2->x) return -1;
137         return 0;
138 }
139
140
141 /* *********************************** */
142
143 static void convert_to_triface(EditMesh *em, int direction)
144 {
145         EditFace *efa, *efan, *next;
146         float fac;
147
148         efa= em->faces.last;
149         while(efa) {
150                 next= efa->prev;
151                 if(efa->v4) {
152                         if(efa->f & SELECT) {
153                                 /* choose shortest diagonal for split */
154                                 fac= len_v3v3(efa->v1->co, efa->v3->co) - len_v3v3(efa->v2->co, efa->v4->co);
155                                 /* this makes sure exact squares get split different in both cases */
156                                 if( (direction==0 && fac<FLT_EPSILON) || (direction && fac>0.0f) ) {
157                                         efan= EM_face_from_faces(em, efa, NULL, 0, 1, 2, -1);
158                                         if(efa->f & SELECT) EM_select_face(efan, 1);
159                                         efan= EM_face_from_faces(em, efa, NULL, 0, 2, 3, -1);
160                                         if(efa->f & SELECT) EM_select_face(efan, 1);
161                                 }
162                                 else {
163                                         efan= EM_face_from_faces(em, efa, NULL, 0, 1, 3, -1);
164                                         if(efa->f & SELECT) EM_select_face(efan, 1);
165                                         efan= EM_face_from_faces(em, efa, NULL, 1, 2, 3, -1);
166                                         if(efa->f & SELECT) EM_select_face(efan, 1);
167                                 }
168
169                                 BLI_remlink(&em->faces, efa);
170                                 free_editface(em, efa);
171                         }
172                 }
173                 efa= next;
174         }
175
176         EM_fgon_flags(em);      // redo flags and indices for fgons
177
178
179 }
180
181 int removedoublesflag(EditMesh *em, short flag, short automerge, float limit)           /* return amount */
182 {
183         /*
184                 flag -          Test with vert->flags
185                 automerge -     Alternative operation, merge unselected into selected.
186                                         Used for "Auto Weld" mode. warning.
187                 limit -         Quick manhattan distance between verts.
188         */
189
190         /* all verts with (flag & 'flag') are being evaluated */
191         EditVert *eve, *v1, *nextve;
192         EditEdge *eed, *e1, *nexted;
193         EditFace *efa, *nextvl;
194         xvertsort *sortblock, *sb, *sb1;
195         struct facesort *vlsortblock, *vsb, *vsb1;
196         int a, b, test, amount;
197
198
199         /* flag 128 is cleared, count */
200
201         /* Normal non weld operation */
202         eve= em->verts.first;
203         amount= 0;
204         while(eve) {
205                 eve->f &= ~128;
206                 if(eve->h==0 && (automerge || (eve->f & flag))) amount++;
207                 eve= eve->next;
208         }
209         if(amount==0) return 0;
210
211         /* allocate memory and qsort */
212         sb= sortblock= MEM_mallocN(sizeof(xvertsort)*amount,"sortremovedoub");
213         eve= em->verts.first;
214         while(eve) {
215                 if(eve->h==0 && (automerge || (eve->f & flag))) {
216                         sb->x= eve->co[0]+eve->co[1]+eve->co[2];
217                         sb->v1= eve;
218                         sb++;
219                 }
220                 eve= eve->next;
221         }
222         qsort(sortblock, amount, sizeof(xvertsort), vergxco);
223
224
225         /* test for doubles */
226         sb= sortblock;
227         if (automerge) {
228                 for(a=0; a<amount; a++, sb++) {
229                         eve= sb->v1;
230                         if( (eve->f & 128)==0 ) {
231                                 sb1= sb+1;
232                                 for(b=a+1; b<amount && (eve->f & 128)==0; b++, sb1++) {
233                                         if(sb1->x - sb->x > limit) break;
234
235                                         /* when automarge, only allow unselected->selected */
236                                         v1= sb1->v1;
237                                         if( (v1->f & 128)==0 ) {
238                                                 if ((eve->f & flag)==0 && (v1->f & flag)==1) {
239                                                         if(     (float)fabs(v1->co[0]-eve->co[0])<=limit &&
240                                                                 (float)fabs(v1->co[1]-eve->co[1])<=limit &&
241                                                                 (float)fabs(v1->co[2]-eve->co[2])<=limit)
242                                                         {       /* unique bit */
243                                                                 eve->f|= 128;
244                                                                 eve->tmp.v = v1;
245                                                         }
246                                                 } else if(      (eve->f & flag)==1 && (v1->f & flag)==0 ) {
247                                                         if(     (float)fabs(v1->co[0]-eve->co[0])<=limit &&
248                                                                 (float)fabs(v1->co[1]-eve->co[1])<=limit &&
249                                                                 (float)fabs(v1->co[2]-eve->co[2])<=limit)
250                                                         {       /* unique bit */
251                                                                 v1->f|= 128;
252                                                                 v1->tmp.v = eve;
253                                                         }
254                                                 }
255                                         }
256                                 }
257                         }
258                 }
259         } else {
260                 for(a=0; a<amount; a++, sb++) {
261                         eve= sb->v1;
262                         if( (eve->f & 128)==0 ) {
263                                 sb1= sb+1;
264                                 for(b=a+1; b<amount; b++, sb1++) {
265                                         /* first test: simpel dist */
266                                         if(sb1->x - sb->x > limit) break;
267                                         v1= sb1->v1;
268
269                                         /* second test: is vertex allowed */
270                                         if( (v1->f & 128)==0 ) {
271                                                 if(     (float)fabs(v1->co[0]-eve->co[0])<=limit &&
272                                                         (float)fabs(v1->co[1]-eve->co[1])<=limit &&
273                                                         (float)fabs(v1->co[2]-eve->co[2])<=limit)
274                                                 {
275                                                         v1->f|= 128;
276                                                         v1->tmp.v = eve;
277                                                 }
278                                         }
279                                 }
280                         }
281                 }
282         }
283         MEM_freeN(sortblock);
284
285         if (!automerge)
286                 for(eve = em->verts.first; eve; eve=eve->next)
287                         if((eve->f & flag) && (eve->f & 128))
288                                 EM_data_interp_from_verts(em, eve, eve->tmp.v, eve->tmp.v, 0.5f);
289
290         /* test edges and insert again */
291         eed= em->edges.first;
292         while(eed) {
293                 eed->f2= 0;
294                 eed= eed->next;
295         }
296         eed= em->edges.last;
297         while(eed) {
298                 nexted= eed->prev;
299
300                 if(eed->f2==0) {
301                         if( (eed->v1->f & 128) || (eed->v2->f & 128) ) {
302                                 remedge(em, eed);
303
304                                 if(eed->v1->f & 128) eed->v1 = eed->v1->tmp.v;
305                                 if(eed->v2->f & 128) eed->v2 = eed->v2->tmp.v;
306                                 e1= addedgelist(em, eed->v1, eed->v2, eed);
307
308                                 if(e1) {
309                                         e1->f2= 1;
310                                         if(eed->f & SELECT)
311                                                 e1->f |= SELECT;
312                                 }
313                                 if(e1!=eed) free_editedge(em, eed);
314                         }
315                 }
316                 eed= nexted;
317         }
318
319         /* first count amount of test faces */
320         efa= (struct EditFace *)em->faces.first;
321         amount= 0;
322         while(efa) {
323                 efa->f1= 0;
324                 if(efa->v1->f & 128) efa->f1= 1;
325                 else if(efa->v2->f & 128) efa->f1= 1;
326                 else if(efa->v3->f & 128) efa->f1= 1;
327                 else if(efa->v4 && (efa->v4->f & 128)) efa->f1= 1;
328
329                 if(efa->f1==1) amount++;
330                 efa= efa->next;
331         }
332
333         /* test faces for double vertices, and if needed remove them */
334         efa= (struct EditFace *)em->faces.first;
335         while(efa) {
336                 nextvl= efa->next;
337                 if(efa->f1==1) {
338
339                         if(efa->v1->f & 128) efa->v1= efa->v1->tmp.v;
340                         if(efa->v2->f & 128) efa->v2= efa->v2->tmp.v;
341                         if(efa->v3->f & 128) efa->v3= efa->v3->tmp.v;
342                         if(efa->v4 && (efa->v4->f & 128)) efa->v4= efa->v4->tmp.v;
343
344                         test= 0;
345                         if(efa->v1==efa->v2) test+=1;
346                         if(efa->v2==efa->v3) test+=2;
347                         if(efa->v3==efa->v1) test+=4;
348                         if(efa->v4==efa->v1) test+=8;
349                         if(efa->v3==efa->v4) test+=16;
350                         if(efa->v2==efa->v4) test+=32;
351
352                         if(test) {
353                                 if(efa->v4) {
354                                         if(test==1 || test==2) {
355                                                 efa->v2= efa->v3;
356                                                 efa->v3= efa->v4;
357                                                 efa->v4= 0;
358
359                                                 EM_data_interp_from_faces(em, efa, NULL, efa, 0, 2, 3, 3);
360
361                                                 test= 0;
362                                         }
363                                         else if(test==8 || test==16) {
364                                                 efa->v4= 0;
365                                                 test= 0;
366                                         }
367                                         else {
368                                                 BLI_remlink(&em->faces, efa);
369                                                 free_editface(em, efa);
370                                                 amount--;
371                                         }
372                                 }
373                                 else {
374                                         BLI_remlink(&em->faces, efa);
375                                         free_editface(em, efa);
376                                         amount--;
377                                 }
378                         }
379
380                         if(test==0) {
381                                 /* set edge pointers */
382                                 efa->e1= findedgelist(em, efa->v1, efa->v2);
383                                 efa->e2= findedgelist(em, efa->v2, efa->v3);
384                                 if(efa->v4==0) {
385                                         efa->e3= findedgelist(em, efa->v3, efa->v1);
386                                         efa->e4= 0;
387                                 }
388                                 else {
389                                         efa->e3= findedgelist(em, efa->v3, efa->v4);
390                                         efa->e4= findedgelist(em, efa->v4, efa->v1);
391                                 }
392                         }
393                 }
394                 efa= nextvl;
395         }
396
397         /* double faces: sort block */
398         /* count again, now all selected faces */
399         amount= 0;
400         efa= em->faces.first;
401         while(efa) {
402                 efa->f1= 0;
403                 if(faceselectedOR(efa, 1)) {
404                         efa->f1= 1;
405                         amount++;
406                 }
407                 efa= efa->next;
408         }
409
410         if(amount) {
411                 /* double faces: sort block */
412                 vsb= vlsortblock= MEM_mallocN(sizeof(struct facesort)*amount, "sortremovedoub");
413                 efa= em->faces.first;
414                 while(efa) {
415                         if(efa->f1 & 1) {
416                                 if(efa->v4) vsb->x= (uintptr_t) MIN4( (uintptr_t)efa->v1, (uintptr_t)efa->v2, (uintptr_t)efa->v3, (uintptr_t)efa->v4);
417                                 else vsb->x= (uintptr_t) MIN3( (uintptr_t)efa->v1, (uintptr_t)efa->v2, (uintptr_t)efa->v3);
418
419                                 vsb->efa= efa;
420                                 vsb++;
421                         }
422                         efa= efa->next;
423                 }
424
425                 qsort(vlsortblock, amount, sizeof(struct facesort), vergface);
426
427                 vsb= vlsortblock;
428                 for(a=0; a<amount; a++) {
429                         efa= vsb->efa;
430                         if( (efa->f1 & 128)==0 ) {
431                                 vsb1= vsb+1;
432
433                                 for(b=a+1; b<amount; b++) {
434
435                                         /* first test: same pointer? */
436                                         if(vsb->x != vsb1->x) break;
437
438                                         /* second test: is test permitted? */
439                                         efa= vsb1->efa;
440                                         if( (efa->f1 & 128)==0 ) {
441                                                 if( compareface(efa, vsb->efa)) efa->f1 |= 128;
442
443                                         }
444                                         vsb1++;
445                                 }
446                         }
447                         vsb++;
448                 }
449
450                 MEM_freeN(vlsortblock);
451
452                 /* remove double faces */
453                 efa= (struct EditFace *)em->faces.first;
454                 while(efa) {
455                         nextvl= efa->next;
456                         if(efa->f1 & 128) {
457                                 BLI_remlink(&em->faces, efa);
458                                 free_editface(em, efa);
459                         }
460                         efa= nextvl;
461                 }
462         }
463
464         /* remove double vertices */
465         a= 0;
466         eve= (struct EditVert *)em->verts.first;
467         while(eve) {
468                 nextve= eve->next;
469                 if(automerge || eve->f & flag) {
470                         if(eve->f & 128) {
471                                 a++;
472                                 BLI_remlink(&em->verts, eve);
473                                 free_editvert(em, eve);
474                         }
475                 }
476                 eve= nextve;
477         }
478
479         return a;       /* amount */
480 }
481
482 static int removedoublesflag_exec(bContext *C, wmOperator *op)
483 {
484         Object *obedit= CTX_data_edit_object(C);
485         EditMesh *em= BKE_mesh_get_editmesh(((Mesh *)obedit->data));
486
487         int count = removedoublesflag(em,1,0,RNA_float_get(op->ptr, "limit"));
488         
489         if(count) {
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), 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         EM_fgon_flags(em);      // redo flags and indices for fgons
1391 }
1392
1393 /* Note, these values must match delete_mesh() event values */
1394 static EnumPropertyItem prop_mesh_delete_types[] = {
1395         {10,"VERT",             0, "Vertices", ""},
1396         {1, "EDGE",             0, "Edges", ""},
1397         {2, "FACE",             0, "Faces", ""},
1398         {3, "ALL",              0, "All", ""},
1399         {4, "EDGE_FACE",0, "Edges & Faces", ""},
1400         {5, "ONLY_FACE",0, "Only Faces", ""},
1401         {6, "EDGE_LOOP",0, "Edge Loop", ""},
1402         {0, NULL, 0, NULL, NULL}
1403 };
1404
1405 static int delete_mesh_exec(bContext *C, wmOperator *op)
1406 {
1407         Object *obedit= CTX_data_edit_object(C);
1408         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
1409         int type= RNA_enum_get(op->ptr, "type");
1410
1411         if(type==6)
1412                 return WM_operator_name_call(C, "MESH_OT_delete_edgeloop", WM_OP_EXEC_DEFAULT, NULL);
1413
1414         delete_mesh(em, op, type);
1415
1416         DAG_id_tag_update(obedit->data, 0);
1417         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
1418
1419         BKE_mesh_end_editmesh(obedit->data, em);
1420         return OPERATOR_FINISHED;
1421 }
1422
1423 void MESH_OT_delete(wmOperatorType *ot)
1424 {
1425         /* identifiers */
1426         ot->name= "Delete";
1427         ot->description= "Delete selected vertices, edges or faces";
1428         ot->idname= "MESH_OT_delete";
1429
1430         /* api callbacks */
1431         ot->invoke= WM_menu_invoke;
1432         ot->exec= delete_mesh_exec;
1433
1434         ot->poll= ED_operator_editmesh;
1435
1436         /* flags */
1437         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1438
1439         /*props */
1440         ot->prop= RNA_def_enum(ot->srna, "type", prop_mesh_delete_types, 10, "Type", "Method used for deleting mesh data");
1441 }
1442
1443
1444 /*GB*/
1445 /*-------------------------------------------------------------------------------*/
1446 /*--------------------------- Edge Based Subdivide ------------------------------*/
1447
1448 #define EDGENEW 2
1449 #define FACENEW 2
1450 #define EDGEINNER  4
1451 #define EDGEOLD  8
1452
1453 /*used by faceloop cut to select only edges valid for edge slide*/
1454 #define DOUBLEOPFILL 16
1455
1456 /* calculates offset for co, based on fractal, sphere or smooth settings  */
1457 static void alter_co(float *co, EditEdge *edge, float smooth, float fractal, int beauty, float perc)
1458 {
1459         float vec1[3], fac;
1460
1461         if(beauty & B_SMOOTH) {
1462                 /* we calculate an offset vector vec1[], to be added to *co */
1463                 float len, fac, nor[3], nor1[3], nor2[3];
1464
1465                 sub_v3_v3v3(nor, edge->v1->co, edge->v2->co);
1466                 len= 0.5f*normalize_v3(nor);
1467
1468                 VECCOPY(nor1, edge->v1->no);
1469                 VECCOPY(nor2, edge->v2->no);
1470
1471                 /* cosine angle */
1472                 fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
1473
1474                 vec1[0]= fac*nor1[0];
1475                 vec1[1]= fac*nor1[1];
1476                 vec1[2]= fac*nor1[2];
1477
1478                 /* cosine angle */
1479                 fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
1480
1481                 vec1[0]+= fac*nor2[0];
1482                 vec1[1]+= fac*nor2[1];
1483                 vec1[2]+= fac*nor2[2];
1484
1485                 /* falloff for multi subdivide */
1486                 smooth *= sqrtf(fabs(1.0f - 2.0f*fabsf(0.5f-perc)));
1487
1488                 vec1[0]*= smooth*len;
1489                 vec1[1]*= smooth*len;
1490                 vec1[2]*= smooth*len;
1491
1492                 co[0] += vec1[0];
1493                 co[1] += vec1[1];
1494                 co[2] += vec1[2];
1495         }
1496         else if(beauty & B_SPHERE) { /* subdivide sphere */
1497                 normalize_v3(co);
1498                 co[0]*= smooth;
1499                 co[1]*= smooth;
1500                 co[2]*= smooth;
1501         }
1502
1503         if(beauty & B_FRACTAL) {
1504                 fac= fractal*len_v3v3(edge->v1->co, edge->v2->co);
1505                 vec1[0]= fac*(float)(0.5-BLI_drand());
1506                 vec1[1]= fac*(float)(0.5-BLI_drand());
1507                 vec1[2]= fac*(float)(0.5-BLI_drand());
1508                 add_v3_v3(co, vec1);
1509         }
1510 }
1511
1512 /* assumes in the edge is the correct interpolated vertices already */
1513 /* percent defines the interpolation, smooth, fractal and beauty are for special options */
1514 /* results in new vertex with correct coordinate, vertex normal and weight group info */
1515 static EditVert *subdivide_edge_addvert(EditMesh *em, EditEdge *edge, float smooth, float fractal, int beauty, float percent)
1516 {
1517         EditVert *ev;
1518         float co[3];
1519
1520         co[0] = (edge->v2->co[0]-edge->v1->co[0])*percent + edge->v1->co[0];
1521         co[1] = (edge->v2->co[1]-edge->v1->co[1])*percent + edge->v1->co[1];
1522         co[2] = (edge->v2->co[2]-edge->v1->co[2])*percent + edge->v1->co[2];
1523
1524         /* offset for smooth or sphere or fractal */
1525         alter_co(co, edge, smooth, fractal, beauty, percent);
1526
1527         /* clip if needed by mirror modifier */
1528         if (edge->v1->f2) {
1529                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
1530                         co[0]= 0.0f;
1531                 }
1532                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
1533                         co[1]= 0.0f;
1534                 }
1535                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
1536                         co[2]= 0.0f;
1537                 }
1538         }
1539
1540         ev = addvertlist(em, co, NULL);
1541
1542         /* vert data (vgroups, ..) */
1543         EM_data_interp_from_verts(em, edge->v1, edge->v2, ev, percent);
1544
1545         /* normal */
1546         ev->no[0] = (edge->v2->no[0]-edge->v1->no[0])*percent + edge->v1->no[0];
1547         ev->no[1] = (edge->v2->no[1]-edge->v1->no[1])*percent + edge->v1->no[1];
1548         ev->no[2] = (edge->v2->no[2]-edge->v1->no[2])*percent + edge->v1->no[2];
1549         normalize_v3(ev->no);
1550
1551         return ev;
1552 }
1553
1554 static void flipvertarray(EditVert** arr, short size)
1555 {
1556         EditVert *hold;
1557         int i;
1558
1559         for(i=0; i<size/2; i++) {
1560                 hold = arr[i];
1561                 arr[i] = arr[size-i-1];
1562                 arr[size-i-1] = hold;
1563         }
1564 }
1565
1566 static void facecopy(EditMesh *em, EditFace *source, EditFace *target)
1567 {
1568         float *v1 = source->v1->co, *v2 = source->v2->co, *v3 = source->v3->co;
1569         float *v4 = source->v4? source->v4->co: NULL;
1570         float w[4][4];
1571
1572         CustomData_em_copy_data(&em->fdata, &em->fdata, source->data, &target->data);
1573
1574         target->mat_nr = source->mat_nr;
1575         target->flag   = source->flag;
1576         target->h          = source->h;
1577
1578         interp_weights_face_v3( w[0],v1, v2, v3, v4, target->v1->co);
1579         interp_weights_face_v3( w[1],v1, v2, v3, v4, target->v2->co);
1580         interp_weights_face_v3( w[2],v1, v2, v3, v4, target->v3->co);
1581         if (target->v4)
1582                 interp_weights_face_v3( w[3],v1, v2, v3, v4, target->v4->co);
1583
1584         CustomData_em_validate_data(&em->fdata, target->data, target->v4 ? 4 : 3);
1585         CustomData_em_interp(&em->fdata, &source->data, NULL, (float*)w, 1, target->data);
1586 }
1587
1588 static void fill_quad_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1589 {
1590         EditEdge *cedge=NULL;
1591         EditVert *v[4], **verts;
1592         EditFace *hold;
1593         short start=0, end, left, right, vertsize,i;
1594
1595         v[0] = efa->v1;
1596         v[1] = efa->v2;
1597         v[2] = efa->v3;
1598         v[3] = efa->v4;
1599
1600         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1601         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1602         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1603         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
1604
1605         // Point verts to the array of new verts for cedge
1606         verts = BLI_ghash_lookup(gh, cedge);
1607         //This is the index size of the verts array
1608         vertsize = numcuts+2;
1609
1610         // Is the original v1 the same as the first vert on the selected edge?
1611         // if not, the edge is running the opposite direction in this face so flip
1612         // the array to the correct direction
1613
1614         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1615         end     = (start+1)%4;
1616         left   = (start+2)%4;
1617         right  = (start+3)%4;
1618
1619         /*
1620         We should have something like this now
1621
1622                           end            start
1623                            3   2   1   0
1624                            |---*---*---|
1625                            |               |
1626                            |               |
1627                            |               |
1628                            -------------
1629                           left     right
1630
1631         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
1632         and 0,1,2... are the indexes of the new verts stored in verts
1633
1634         We will fill this case like this or this depending on even or odd cuts
1635
1636                            |---*---*---|                  |---*---|
1637                            |  /  \  |             |  / \  |
1638                            | /     \ |            | /   \ |
1639                            |/            \|               |/     \|
1640                            -------------                  ---------
1641         */
1642
1643         // Make center face
1644         if(vertsize % 2 == 0) {
1645                 hold = addfacelist(em, verts[(vertsize-1)/2],verts[((vertsize-1)/2)+1],v[left],v[right], NULL,NULL);
1646                 hold->e2->f2 |= EDGEINNER;
1647                 hold->e4->f2 |= EDGEINNER;
1648         }else{
1649                 hold = addfacelist(em, verts[(vertsize-1)/2],v[left],v[right],NULL, NULL,NULL);
1650                 hold->e1->f2 |= EDGEINNER;
1651                 hold->e3->f2 |= EDGEINNER;
1652         }
1653         facecopy(em, efa,hold);
1654
1655         // Make side faces
1656         for(i=0;i<(vertsize-1)/2;i++) {
1657                 hold = addfacelist(em, verts[i],verts[i+1],v[right],NULL,NULL,NULL);
1658                 facecopy(em, efa,hold);
1659                 if(i+1 != (vertsize-1)/2) {
1660                         if(seltype == SUBDIV_SELECT_INNER) {
1661                                 hold->e2->f2 |= EDGEINNER;
1662                         }
1663                 }
1664                 hold = addfacelist(em, verts[vertsize-2-i],verts[vertsize-1-i],v[left],NULL,NULL,NULL);
1665                 facecopy(em, efa,hold);
1666                 if(i+1 != (vertsize-1)/2) {
1667                         if(seltype == SUBDIV_SELECT_INNER) {
1668                                  hold->e3->f2 |= EDGEINNER;
1669                         }
1670                 }
1671         }
1672 }
1673
1674 static void fill_tri_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1675 {
1676         EditEdge *cedge=NULL;
1677         EditVert *v[3], **verts;
1678         EditFace *hold;
1679         short start=0, end, op, vertsize,i;
1680
1681         v[0] = efa->v1;
1682         v[1] = efa->v2;
1683         v[2] = efa->v3;
1684
1685         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1686         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1687         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1688
1689         // Point verts to the array of new verts for cedge
1690         verts = BLI_ghash_lookup(gh, cedge);
1691         //This is the index size of the verts array
1692         vertsize = numcuts+2;
1693
1694         // Is the original v1 the same as the first vert on the selected edge?
1695         // if not, the edge is running the opposite direction in this face so flip
1696         // the array to the correct direction
1697
1698         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1699            end  = (start+1)%3;
1700            op    = (start+2)%3;
1701
1702         /*
1703         We should have something like this now
1704
1705                           end            start
1706                            3   2   1   0
1707                            |---*---*---|
1708                            \               |
1709                                  \               |
1710                                    \       |
1711                                          \       |
1712                                            \   |
1713                                                  \ |
1714                                                    |op
1715
1716         where start,end,op are indexes of EditFace->v1, etc (stored in v)
1717         and 0,1,2... are the indexes of the new verts stored in verts
1718
1719         We will fill this case like this or this depending on even or odd cuts
1720
1721                            3   2   1   0
1722                            |---*---*---|
1723                            \    \  \   |
1724                                  \      \ \  |
1725                                    \   \ \ |
1726                                          \  \ \|
1727                                            \ \\|
1728                                                  \ |
1729                                                    |op
1730         */
1731
1732         // Make side faces
1733         for(i=0;i<(vertsize-1);i++) {
1734                 hold = addfacelist(em, verts[i],verts[i+1],v[op],NULL,NULL,NULL);
1735                 if(i+1 != vertsize-1) {
1736                         if(seltype == SUBDIV_SELECT_INNER) {
1737                                  hold->e2->f2 |= EDGEINNER;
1738                         }
1739                 }
1740                 facecopy(em, efa,hold);
1741         }
1742 }
1743
1744 static void fill_quad_double_op(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1745 {
1746         EditEdge *cedge[2]={NULL, NULL};
1747         EditVert *v[4], **verts[2];
1748         EditFace *hold;
1749         short start=0, /*end,*/ left, /* right,*/ vertsize,i;
1750
1751         v[0] = efa->v1;
1752         v[1] = efa->v2;
1753         v[2] = efa->v3;
1754         v[3] = efa->v4;
1755
1756         if(efa->e1->f & SELECT)   { cedge[0] = efa->e1;  cedge[1] = efa->e3; start = 0;}
1757         else if(efa->e2->f & SELECT)      { cedge[0] = efa->e2;  cedge[1] = efa->e4; start = 1;}
1758
1759         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1760         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1761         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1762         //This is the index size of the verts array
1763         vertsize = numcuts+2;
1764
1765         // Is the original v1 the same as the first vert on the selected edge?
1766         // if not, the edge is running the opposite direction in this face so flip
1767         // the array to the correct direction
1768
1769         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1770         /* end  = (start+1)%4; */ /* UNUSED */
1771         left   = (start+2)%4;
1772         /* right  = (start+3)%4; */ /* UNUSED */
1773         if(verts[1][0] != v[left]) {flipvertarray(verts[1],numcuts+2);}
1774         /*
1775         We should have something like this now
1776
1777                           end            start
1778                            3   2   1   0
1779                            |---*---*---|
1780                            |               |
1781                            |               |
1782                            |               |
1783                            |---*---*---|
1784                            0   1   2   3
1785                           left     right
1786
1787         We will fill this case like this or this depending on even or odd cuts
1788
1789                            |---*---*---|
1790                            |   |   |   |
1791                            |   |   |   |
1792                            |   |   |   |
1793                            |---*---*---|
1794         */
1795
1796         // Make side faces
1797         for(i=0;i<vertsize-1;i++) {
1798                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-2-i],verts[1][vertsize-1-i],NULL,NULL);
1799                 if(i < vertsize-2) {
1800                         hold->e2->f2 |= EDGEINNER;
1801                         hold->e2->f2 |= DOUBLEOPFILL;
1802                 }
1803                 facecopy(em, efa,hold);
1804         }
1805 }
1806
1807 static void fill_quad_double_adj_path(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1808 {
1809         EditEdge *cedge[2]={NULL, NULL};
1810         EditVert *v[4], **verts[2];
1811         EditFace *hold;
1812         short start=0, start2=0, vertsize,i;
1813         int ctrl= 0; // XXX
1814
1815         v[0] = efa->v1;
1816         v[1] = efa->v2;
1817         v[2] = efa->v3;
1818         v[3] = efa->v4;
1819
1820         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
1821         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
1822         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3;}
1823         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0;}
1824
1825         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1826         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1827         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1828         //This is the index size of the verts array
1829         vertsize = numcuts+2;
1830
1831         // Is the original v1 the same as the first vert on the selected edge?
1832         // if not, the edge is running the opposite direction in this face so flip
1833         // the array to the correct direction
1834
1835         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1836         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1837         /*
1838         We should have something like this now
1839
1840                            end           start
1841                                 3   2   1   0
1842                 start2 0|---*---*---|
1843                                 |                  |
1844                            1*              |
1845                                 |                  |
1846                            2*              |
1847                                 |                  |
1848                  end2  3|-----------|
1849
1850         We will fill this case like this or this depending on even or odd cuts
1851                            |---*---*---|
1852                            | /   /   / |
1853                            *   /   /   |
1854                            | /   /       |
1855                            *   /           |
1856                            | /           |
1857                            |-----------|
1858         */
1859
1860         // Make outside tris
1861         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
1862         /* when ctrl is depressed, only want verts on the cutline selected */
1863         if (ctrl)
1864                 hold->e3->f2 |= EDGEINNER;
1865         facecopy(em, efa,hold);
1866         hold = addfacelist(em, verts[0][0],verts[1][vertsize-1],v[(start2+2)%4],NULL,NULL,NULL);
1867         /* when ctrl is depressed, only want verts on the cutline selected */
1868         if (ctrl)
1869                 hold->e1->f2 |= EDGEINNER;
1870         facecopy(em, efa,hold);
1871         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1872         //      hold->e1->h |= EM_FGON;
1873         //}
1874         // Make side faces
1875
1876         for(i=0;i<numcuts;i++) {
1877                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
1878                 hold->e2->f2 |= EDGEINNER;
1879                 facecopy(em, efa,hold);
1880         }
1881         //EM_fgon_flags(em);
1882
1883 }
1884
1885 static void fill_quad_double_adj_fan(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1886 {
1887         EditEdge *cedge[2]={NULL, NULL};
1888         EditVert *v[4], *op=NULL, **verts[2];
1889         EditFace *hold;
1890         short start=0, start2=0, vertsize,i;
1891
1892         v[0] = efa->v1;
1893         v[1] = efa->v2;
1894         v[2] = efa->v3;
1895         v[3] = efa->v4;
1896
1897         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1898         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1899         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1900         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1901
1902
1903         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1904         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1905         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1906         //This is the index size of the verts array
1907         vertsize = numcuts+2;
1908
1909         // Is the original v1 the same as the first vert on the selected edge?
1910         // if not, the edge is running the opposite direction in this face so flip
1911         // the array to the correct direction
1912
1913         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1914         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1915         /*
1916         We should have something like this now
1917
1918                            end           start
1919                                 3   2   1   0
1920                 start2 0|---*---*---|
1921                                 |                  |
1922                            1*              |
1923                                 |                  |
1924                            2*              |
1925                                 |                  |
1926                  end2  3|-----------|op
1927
1928         We will fill this case like this or this (warning horrible ascii art follows)
1929                            |---*---*---|
1930                            | \  \   \  |
1931                            *---\  \  \ |
1932                            |   \ \ \  \|
1933                            *---- \ \  \ |
1934                            |    ---  \\\|
1935                            |-----------|
1936         */
1937
1938         for(i=0;i<=numcuts;i++) {
1939                 hold = addfacelist(em, op,verts[1][numcuts-i],verts[1][numcuts-i+1],NULL,NULL,NULL);
1940                 hold->e1->f2 |= EDGEINNER;
1941                 facecopy(em, efa,hold);
1942
1943                 hold = addfacelist(em, op,verts[0][i],verts[0][i+1],NULL,NULL,NULL);
1944                 hold->e3->f2 |= EDGEINNER;
1945                 facecopy(em, efa,hold);
1946         }
1947 }
1948
1949 static void fill_quad_double_adj_inner(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1950 {
1951         EditEdge *cedge[2]={NULL, NULL};
1952         EditVert *v[4], *op=NULL, **verts[2],**inner;
1953         EditFace *hold;
1954         short start=0, start2=0, vertsize,i;
1955         float co[3];
1956
1957         v[0] = efa->v1;
1958         v[1] = efa->v2;
1959         v[2] = efa->v3;
1960         v[3] = efa->v4;
1961
1962         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1963         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1964         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1965         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1966
1967
1968         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1969         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1970         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1971         //This is the index size of the verts array
1972         vertsize = numcuts+2;
1973
1974         // Is the original v1 the same as the first vert on the selected edge?
1975         // if not, the edge is running the opposite direction in this face so flip
1976         // the array to the correct direction
1977
1978         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1979         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1980         /*
1981         We should have something like this now
1982
1983                            end           start
1984                                 3   2   1   0
1985                 start2 0|---*---*---|
1986                                 |                  |
1987                            1*              |
1988                                 |                  |
1989                            2*              |
1990                                 |                  |
1991                  end2  3|-----------|op
1992
1993         We will fill this case like this or this (warning horrible ascii art follows)
1994                            |---*-----*---|
1995                            | *     /     |
1996                            *   \ /       |
1997                            |    *        |
1998                            | /    \          |
1999                            *        \    |
2000                            |           \ |
2001                            |-------------|
2002         */
2003
2004         // Add Inner Vert(s)
2005         inner = MEM_mallocN(sizeof(EditVert*)*numcuts,"New inner verts");
2006
2007         for(i=0;i<numcuts;i++) {
2008                 co[0] = (verts[0][numcuts-i]->co[0] + verts[1][i+1]->co[0] ) / 2 ;
2009                 co[1] = (verts[0][numcuts-i]->co[1] + verts[1][i+1]->co[1] ) / 2 ;
2010                 co[2] = (verts[0][numcuts-i]->co[2] + verts[1][i+1]->co[2] ) / 2 ;
2011                 inner[i] = addvertlist(em, co, NULL);
2012                 inner[i]->f2 |= EDGEINNER;
2013
2014                 EM_data_interp_from_verts(em, verts[0][numcuts-i], verts[1][i+1], inner[i], 0.5f);
2015         }
2016
2017         // Add Corner Quad
2018         hold = addfacelist(em, verts[0][numcuts+1],verts[1][1],inner[0],verts[0][numcuts],NULL,NULL);
2019         hold->e2->f2 |= EDGEINNER;
2020         hold->e3->f2 |= EDGEINNER;
2021         facecopy(em, efa,hold);
2022         // Add Bottom Quads
2023         hold = addfacelist(em, verts[0][0],verts[0][1],inner[numcuts-1],op,NULL,NULL);
2024         hold->e2->f2 |= EDGEINNER;
2025         facecopy(em, efa,hold);
2026
2027         hold = addfacelist(em, op,inner[numcuts-1],verts[1][numcuts],verts[1][numcuts+1],NULL,NULL);
2028         hold->e2->f2 |= EDGEINNER;
2029         facecopy(em, efa,hold);
2030
2031         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2032         //      hold->e1->h |= EM_FGON;
2033         //}
2034         // Add Fill Quads (if # cuts > 1)
2035
2036         for(i=0;i<numcuts-1;i++) {
2037                 hold = addfacelist(em, inner[i],verts[1][i+1],verts[1][i+2],inner[i+1],NULL,NULL);
2038                 hold->e1->f2 |= EDGEINNER;
2039                 hold->e3->f2 |= EDGEINNER;
2040                 facecopy(em, efa,hold);
2041
2042                 hold = addfacelist(em, inner[i],inner[i+1],verts[0][numcuts-1-i],verts[0][numcuts-i],NULL,NULL);
2043                 hold->e2->f2 |= EDGEINNER;
2044                 hold->e4->f2 |= EDGEINNER;
2045                 facecopy(em, efa,hold);
2046
2047                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2048                 //      hold->e1->h |= EM_FGON;
2049                 //}
2050         }
2051
2052         //EM_fgon_flags(em);
2053
2054         MEM_freeN(inner);
2055 }
2056
2057 static void fill_tri_double(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
2058 {
2059         EditEdge *cedge[2]={NULL, NULL};
2060         EditVert *v[3], **verts[2];
2061         EditFace *hold;
2062         short start=0, start2=0, vertsize,i;
2063
2064         v[0] = efa->v1;
2065         v[1] = efa->v2;
2066         v[2] = efa->v3;
2067
2068         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
2069         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
2070         if(efa->e3->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e1; start = 2; start2 = 0;}
2071
2072         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2073         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2074         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2075         //This is the index size of the verts array
2076         vertsize = numcuts+2;
2077
2078         // Is the original v1 the same as the first vert on the selected edge?
2079         // if not, the edge is running the opposite direction in this face so flip
2080         // the array to the correct direction
2081
2082         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2083         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
2084         /*
2085         We should have something like this now
2086
2087                            end           start
2088                                 3   2   1   0
2089                 start2 0|---*---*---|
2090                                 |                /
2091                            1*      /
2092                                 |        /
2093                            2*   /
2094                                 | /
2095                  end2  3|
2096
2097         We will fill this case like this or this depending on even or odd cuts
2098                            |---*---*---|
2099                            | /   /   /
2100                            *   /   /
2101                            | /   /
2102                            *   /
2103                            | /
2104                            |
2105         */
2106
2107         // Make outside tri
2108         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2109         hold->e3->f2 |= EDGEINNER;
2110         facecopy(em, efa,hold);
2111         // Make side faces
2112
2113         for(i=0;i<numcuts;i++) {
2114                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
2115                 hold->e2->f2 |= EDGEINNER;
2116                 facecopy(em, efa,hold);
2117         }
2118 }
2119
2120 static void fill_quad_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
2121 {
2122         EditEdge *cedge[3]={0};
2123         EditVert *v[4], **verts[3];
2124         EditFace *hold;
2125         short start=0, start2=0, start3=0, vertsize, i, repeats;
2126
2127         v[0] = efa->v1;
2128         v[1] = efa->v2;
2129         v[2] = efa->v3;
2130         v[3] = efa->v4;
2131
2132         if(!(efa->e1->f & SELECT)) {
2133                 cedge[0] = efa->e2;
2134                 cedge[1] = efa->e3;
2135                 cedge[2] = efa->e4;
2136                 start = 1;start2 = 2;start3 = 3;
2137         }
2138         if(!(efa->e2->f & SELECT)) {
2139                 cedge[0] = efa->e3;
2140                 cedge[1] = efa->e4;
2141                 cedge[2] = efa->e1;
2142                 start = 2;start2 = 3;start3 = 0;
2143         }
2144         if(!(efa->e3->f & SELECT)) {
2145                 cedge[0] = efa->e4;
2146                 cedge[1] = efa->e1;
2147                 cedge[2] = efa->e2;
2148                 start = 3;start2 = 0;start3 = 1;
2149         }
2150         if(!(efa->e4->f & SELECT)) {
2151                 cedge[0] = efa->e1;
2152                 cedge[1] = efa->e2;
2153                 cedge[2] = efa->e3;
2154                 start = 0;start2 = 1;start3 = 2;
2155         }
2156         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2157         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2158         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2159         verts[2] = BLI_ghash_lookup(gh, cedge[2]);
2160         //This is the index size of the verts array
2161         vertsize = numcuts+2;
2162
2163         // Is the original v1 the same as the first vert on the selected edge?
2164         // if not, the edge is running the opposite direction in this face so flip
2165         // the array to the correct direction
2166
2167         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2168         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
2169         if(verts[2][0] != v[start3]) {flipvertarray(verts[2],numcuts+2);}
2170         /*
2171          We should have something like this now
2172
2173          start2
2174          3   2   1   0
2175          start3 0|---*---*---|3
2176          |                 |
2177          1*                *2
2178          |                 |
2179          2*                *1
2180          |                 |
2181          3|-----------|0 start
2182
2183          We will fill this case like this or this depending on even or odd cuts
2184          there are a couple of differences. For odd cuts, there is a tri in the
2185          middle as well as 1 quad at the bottom (not including the extra quads
2186          for odd cuts > 1
2187
2188          For even cuts, there is a quad in the middle and 2 quads on the bottom
2189
2190          they are numbered here for clarity
2191
2192          1 outer tris and bottom quads
2193          2 inner tri or quad
2194          3 repeating quads
2195
2196          |---*---*---*---|
2197          |1/   /  \   \ 1|
2198          |/ 3 / \  3 \|
2199          *  /   2   \   *
2200          | /              \  |
2201          |/                     \ |
2202          *---------------*
2203          |        3             |
2204          |                         |
2205          *---------------*
2206          |                         |
2207          |        1             |
2208          |                         |
2209          |---------------|
2210
2211          |---*---*---*---*---|
2212          | 1/   /        \   \ 1|
2213          | /   /           \   \ |
2214          |/ 3 /          \ 3 \|
2215          *   /             \   *
2216          |  /                    \  |
2217          | /       2       \ |
2218          |/                              \|
2219          *-------------------*
2220          |                                 |
2221          |               3               |
2222          |                                 |
2223          *-------------------*
2224          |                                 |
2225          |               1               |
2226          |                                 |
2227          *-------------------*
2228          |                                 |
2229          |              1                 |
2230          |                                 |
2231          |-------------------|
2232
2233          */
2234
2235         // Make outside tris
2236         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2237         hold->e3->f2 |= EDGEINNER;
2238         facecopy(em, efa,hold);
2239         hold = addfacelist(em, verts[1][vertsize-2],verts[1][vertsize-1],verts[2][1],NULL,NULL,NULL);
2240         hold->e3->f2 |= EDGEINNER;
2241         facecopy(em, efa,hold);
2242         // Make bottom quad
2243         hold = addfacelist(em, verts[0][0],verts[0][1],verts[2][vertsize-2],verts[2][vertsize-1],NULL,NULL);
2244         hold->e2->f2 |= EDGEINNER;
2245         facecopy(em, efa,hold);
2246         //If it is even cuts, add the 2nd lower quad
2247         if(numcuts % 2 == 0) {
2248                 hold = addfacelist(em, verts[0][1],verts[0][2],verts[2][vertsize-3],verts[2][vertsize-2],NULL,NULL);
2249                 hold->e2->f2 |= EDGEINNER;
2250                 facecopy(em, efa,hold);
2251                 // Also Make inner quad
2252                 hold = addfacelist(em, verts[1][numcuts/2],verts[1][(numcuts/2)+1],verts[2][numcuts/2],verts[0][(numcuts/2)+1],NULL,NULL);
2253                 hold->e3->f2 |= EDGEINNER;
2254                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2255                 //      hold->e3->h |= EM_FGON;
2256                 //}
2257                 facecopy(em, efa,hold);
2258                 repeats = (numcuts / 2) -1;
2259         } else {
2260                 // Make inner tri
2261                 hold = addfacelist(em, verts[1][(numcuts/2)+1],verts[2][(numcuts/2)+1],verts[0][(numcuts/2)+1],NULL,NULL,NULL);
2262                 hold->e2->f2 |= EDGEINNER;
2263                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2264                 //      hold->e2->h |= EM_FGON;
2265                 //}
2266                 facecopy(em, efa,hold);
2267                 repeats = ((numcuts+1) / 2)-1;
2268         }
2269
2270         // cuts for 1 and 2 do not have the repeating quads
2271         if(numcuts < 3) {repeats = 0;}
2272         for(i=0;i<repeats;i++) {
2273                 //Make side repeating Quads
2274                 hold = addfacelist(em, verts[1][i+1],verts[1][i+2],verts[0][vertsize-i-3],verts[0][vertsize-i-2],NULL,NULL);
2275                 hold->e2->f2 |= EDGEINNER;
2276                 facecopy(em, efa,hold);
2277                 hold = addfacelist(em, verts[1][vertsize-i-3],verts[1][vertsize-i-2],verts[2][i+1],verts[2][i+2],NULL,NULL);
2278                 hold->e4->f2 |= EDGEINNER;
2279                 facecopy(em, efa,hold);
2280         }
2281         // Do repeating bottom quads
2282         for(i=0;i<repeats;i++) {
2283                 if(numcuts % 2 == 1) {
2284                         hold = addfacelist(em, verts[0][1+i],verts[0][2+i],verts[2][vertsize-3-i],verts[2][vertsize-2-i],NULL,NULL);
2285                 } else {
2286                         hold = addfacelist(em, verts[0][2+i],verts[0][3+i],verts[2][vertsize-4-i],verts[2][vertsize-3-i],NULL,NULL);
2287                 }
2288                 hold->e2->f2 |= EDGEINNER;
2289                 facecopy(em, efa,hold);
2290         }
2291         //EM_fgon_flags(em);
2292 }
2293
2294 static void fill_quad_quadruple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2295 {
2296         EditVert **verts[4], ***innerverts;
2297         EditFace *hold;
2298         EditEdge temp;
2299         short vertsize, i, j;
2300
2301         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2302         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2303         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2304         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2305         verts[3] = BLI_ghash_lookup(gh, efa->e4);
2306
2307         //This is the index size of the verts array
2308         vertsize = numcuts+2;
2309
2310         // Is the original v1 the same as the first vert on the selected edge?
2311         // if not, the edge is running the opposite direction in this face so flip
2312         // the array to the correct direction
2313
2314         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2315         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2316         if(verts[2][0] == efa->v3) {flipvertarray(verts[2],numcuts+2);}
2317         if(verts[3][0] == efa->v4) {flipvertarray(verts[3],numcuts+2);}
2318         /*
2319         We should have something like this now
2320                                           1
2321
2322                                 3   2   1   0
2323                            0|---*---*---|0
2324                                 |           |
2325                            1*           *1
2326                          2  |           |   4
2327                            2*           *2
2328                                 |           |
2329                            3|---*---*---|3
2330                                 3   2   1   0
2331
2332                                           3
2333         // we will fill a 2 dim array of editvert*s to make filling easier
2334         //  the innervert order is shown
2335
2336                                 0   0---1---2---3
2337                                         |   |   |   |
2338                                 1   0---1---2---3
2339                                         |   |   |   |
2340                                 2   0---1---2---3
2341                                         |   |   |   |
2342                                 3   0---1---2---3
2343
2344          */
2345         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts outer array");
2346         for(i=0;i<numcuts+2;i++) {
2347                 innerverts[i] = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts inner array");
2348         }
2349
2350         // first row is e1 last row is e3
2351         for(i=0;i<numcuts+2;i++) {
2352                 innerverts[0][i]                  = verts[0][(numcuts+1)-i];
2353                 innerverts[numcuts+1][i]  = verts[2][(numcuts+1)-i];
2354         }
2355
2356         for(i=1;i<=numcuts;i++) {
2357                 /* we create a fake edge for the next loop */
2358                 temp.v2 = innerverts[i][0]                      = verts[1][i];
2359                 temp.v1 = innerverts[i][numcuts+1]  = verts[3][i];
2360
2361                 for(j=1;j<=numcuts;j++) {
2362                         float percent= (float)j/(float)(numcuts+1);
2363
2364                         innerverts[i][(numcuts+1)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, percent);
2365                 }
2366         }
2367         // Fill with faces
2368         for(i=0;i<numcuts+1;i++) {
2369                 for(j=0;j<numcuts+1;j++) {
2370                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],innerverts[i+1][j+1],NULL,NULL);
2371                         hold->e1->f2 = EDGENEW;
2372                         hold->e2->f2 = EDGENEW;
2373                         hold->e3->f2 = EDGENEW;
2374                         hold->e4->f2 = EDGENEW;
2375
2376                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2377                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2378                         if(i != numcuts) { hold->e3->f2 |= EDGEINNER; }
2379                         if(j != numcuts) { hold->e4->f2 |= EDGEINNER; }
2380
2381                         facecopy(em, efa,hold);
2382                 }
2383         }
2384         // Clean up our dynamic multi-dim array
2385         for(i=0;i<numcuts+2;i++) {
2386            MEM_freeN(innerverts[i]);
2387         }
2388         MEM_freeN(innerverts);
2389 }
2390
2391 static void fill_tri_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2392 {
2393         EditVert **verts[3], ***innerverts;
2394         short vertsize, i, j;
2395         EditFace *hold;
2396         EditEdge temp;
2397
2398         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2399         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2400         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2401         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2402
2403         //This is the index size of the verts array
2404         vertsize = numcuts+2;
2405
2406         // Is the original v1 the same as the first vert on the selected edge?
2407         // if not, the edge is running the opposite direction in this face so flip
2408         // the array to the correct direction
2409
2410         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2411         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2412         if(verts[2][0] != efa->v3) {flipvertarray(verts[2],numcuts+2);}
2413         /*
2414         We should have something like this now
2415                                            3
2416
2417                                 3   2   1   0
2418                            0|---*---*---|3
2419                                 |                 /
2420                   1     1*              *2
2421                                 |         /
2422                            2*   *1         2
2423                                 |  /
2424                            3|/
2425                                  0
2426
2427         we will fill a 2 dim array of editvert*s to make filling easier
2428
2429                                                 3
2430
2431                          0  0---1---2---3---4
2432                                 | / | /  |/  | /
2433                          1  0---1----2---3
2434            1            | /  | / | /
2435                          2  0----1---2   2
2436                                 |  / |  /
2437                                 |/   |/
2438                          3  0---1
2439                                 |  /
2440                                 |/
2441                          4  0
2442
2443         */
2444
2445         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"tri-tri subdiv inner verts outer array");
2446         for(i=0;i<numcuts+2;i++) {
2447                   innerverts[i] = MEM_mallocN(sizeof(EditVert*)*((numcuts+2)-i),"tri-tri subdiv inner verts inner array");
2448         }
2449         //top row is e3 backwards
2450         for(i=0;i<numcuts+2;i++) {
2451                   innerverts[0][i]                = verts[2][(numcuts+1)-i];
2452         }
2453
2454         for(i=1;i<=numcuts+1;i++) {
2455                 //fake edge, first vert is from e1, last is from e2
2456                 temp.v1= innerverts[i][0]                         = verts[0][i];
2457                 temp.v2= innerverts[i][(numcuts+1)-i]  = verts[1][(numcuts+1)-i];
2458
2459                 for(j=1;j<(numcuts+1)-i;j++) {
2460                         float percent= (float)j/(float)((numcuts+1)-i);
2461
2462                         innerverts[i][((numcuts+1)-i)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, 1-percent);
2463                 }
2464         }
2465
2466         // Now fill the verts with happy little tris :)
2467         for(i=0;i<=numcuts+1;i++) {
2468                 for(j=0;j<(numcuts+1)-i;j++) {
2469                         //We always do the first tri
2470                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],NULL,NULL,NULL);
2471                         hold->e1->f2 |= EDGENEW;
2472                         hold->e2->f2 |= EDGENEW;
2473                         hold->e3->f2 |= EDGENEW;
2474                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2475                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2476                         if(j+1 != (numcuts+1)-i) {hold->e3->f2 |= EDGEINNER;}
2477
2478                         facecopy(em, efa,hold);
2479                         //if there are more to come, we do the 2nd
2480                         if(j+1 <= numcuts-i) {
2481                                 hold = addfacelist(em, innerverts[i+1][j],innerverts[i+1][j+1],innerverts[i][j+1],NULL,NULL,NULL);
2482                                 facecopy(em, efa,hold);
2483                                 hold->e1->f2 |= EDGENEW;
2484                                 hold->e2->f2 |= EDGENEW;
2485                                 hold->e3->f2 |= EDGENEW;
2486                         }
2487                 }
2488         }
2489
2490         // Clean up our dynamic multi-dim array
2491         for(i=0;i<numcuts+2;i++) {
2492                 MEM_freeN(innerverts[i]);
2493         }
2494         MEM_freeN(innerverts);
2495 }
2496
2497 //Next two fill types are for knife exact only and are provided to allow for knifing through vertices
2498 //This means there is no multicut!
2499 static void fill_quad_doublevert(EditMesh *em, EditFace *efa, int v1, int v2)
2500 {
2501         EditFace *hold;
2502         /*
2503                 Depending on which two vertices have been knifed through (v1 and v2), we
2504                 triangulate like the patterns below.
2505                                 X-------|       |-------X
2506                                 | \     |       |     / |
2507                                 |   \   |       |   /   |
2508                                 |         \     |       | /         |
2509                                 --------X       X--------
2510         */
2511
2512         if(v1 == 1 && v2 == 3){
2513                 hold= addfacelist(em, efa->v1, efa->v2, efa->v3, 0, efa, NULL);
2514                 hold->e1->f2 |= EDGENEW;
2515                 hold->e2->f2 |= EDGENEW;
2516                 hold->e3->f2 |= EDGENEW;
2517                 hold->e3->f2 |= EDGEINNER;
2518                 facecopy(em, efa, hold);
2519
2520                 hold= addfacelist(em, efa->v1, efa->v3, efa->v4, 0, efa, NULL);
2521                 hold->e1->f2 |= EDGENEW;
2522                 hold->e2->f2 |= EDGENEW;
2523                 hold->e3->f2 |= EDGENEW;
2524                 hold->e1->f2 |= EDGEINNER;
2525                 facecopy(em, efa, hold);
2526         }
2527         else{
2528                 hold= addfacelist(em, efa->v1, efa->v2, efa->v4, 0, efa, NULL);
2529                 hold->e1->f2 |= EDGENEW;
2530                 hold->e2->f2 |= EDGENEW;
2531                 hold->e3->f2 |= EDGENEW;
2532                 hold->e2->f2 |= EDGEINNER;
2533                 facecopy(em, efa, hold);
2534
2535                 hold= addfacelist(em, efa->v2, efa->v3, efa->v4, 0, efa, NULL);
2536                 hold->e1->f2 |= EDGENEW;
2537                 hold->e2->f2 |= EDGENEW;
2538                 hold->e3->f2 |= EDGENEW;
2539                 hold->e3->f2 |= EDGEINNER;
2540                 facecopy(em, efa, hold);
2541         }
2542 }
2543
2544 static void fill_quad_singlevert(EditMesh *em, EditFace *efa, struct GHash *gh)
2545 {
2546         EditEdge *cedge=NULL;
2547         EditVert *v[4], **verts;
2548         EditFace *hold;
2549         short start=0, end, left, right, vertsize;
2550
2551         v[0] = efa->v1;
2552         v[1] = efa->v2;
2553         v[2] = efa->v3;
2554         v[3] = efa->v4;
2555
2556         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
2557         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
2558         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
2559         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
2560
2561         // Point verts to the array of new verts for cedge
2562         verts = BLI_ghash_lookup(gh, cedge);
2563         //This is the index size of the verts array
2564         vertsize = 3;
2565
2566         // Is the original v1 the same as the first vert on the selected edge?
2567         // if not, the edge is running the opposite direction in this face so flip
2568         // the array to the correct direction
2569
2570         if(verts[0] != v[start]) {flipvertarray(verts,3);}
2571         end     = (start+1)%4;
2572         left   = (start+2)%4;
2573         right  = (start+3)%4;
2574
2575 /*
2576         We should have something like this now
2577
2578                           end            start
2579                            2     1     0
2580                            |-----*-----|
2581                            |               |
2582                            |               |
2583                            |               |
2584                            -------------
2585                           left     right
2586
2587         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
2588         and 0,1,2 are the indexes of the new verts stored in verts. We fill like
2589         this, depending on whether its vertex 'left' or vertex 'right' thats
2590         been knifed through...
2591
2592                                 |---*---|       |---*---|
2593                                 |  /    |       |    \  |
2594                                 | /             |       |         \ |
2595                                 |/              |       |          \|
2596                                 X--------       --------X
2597 */
2598
2599         if(v[left]->f1){
2600                 //triangle is composed of cutvert, end and left
2601                 hold = addfacelist(em, verts[1],v[end],v[left],NULL, NULL,NULL);
2602                 hold->e1->f2 |= EDGENEW;
2603                 hold->e2->f2 |= EDGENEW;
2604                 hold->e3->f2 |= EDGENEW;
2605                 hold->e3->f2 |= EDGEINNER;
2606                 facecopy(em, efa, hold);
2607
2608                 //quad is composed of cutvert, left, right and start
2609                 hold = addfacelist(em, verts[1],v[left],v[right],v[start], NULL, NULL);
2610                 hold->e1->f2 |= EDGENEW;
2611                 hold->e2->f2 |= EDGENEW;
2612                 hold->e3->f2 |= EDGENEW;
2613                 hold->e4->f2 |= EDGENEW;
2614                 hold->e1->f2 |= EDGEINNER;
2615                 facecopy(em, efa, hold);
2616         }
2617         else if(v[right]->f1){
2618                 //triangle is composed of cutvert, right and start
2619                 hold = addfacelist(em, verts[1],v[right],v[start], NULL, NULL, NULL);
2620                 hold->e1->f2 |= EDGENEW;
2621                 hold->e2->f2 |= EDGENEW;
2622                 hold->e3->f2 |= EDGENEW;
2623                 hold->e1->f2 |= EDGEINNER;
2624                 facecopy(em, efa, hold);
2625                 //quad is composed of cutvert, end, left, right
2626                 hold = addfacelist(em, verts[1],v[end], v[left], v[right], NULL, NULL);
2627                 hold->e1->f2 |= EDGENEW;
2628                 hold->e2->f2 |= EDGENEW;
2629                 hold->e3->f2 |= EDGENEW;
2630                 hold->e4->f2 |= EDGENEW;
2631                 hold->e4->f2 |= EDGEINNER;
2632                 facecopy(em, efa, hold);
2633         }
2634
2635 }
2636
2637 // This function takes an example edge, the current point to create and
2638 // the total # of points to create, then creates the point and return the
2639 // editvert pointer to it.
2640 static EditVert *subdivideedgenum(EditMesh *em, EditEdge *edge, int curpoint, int totpoint, float smooth, float fractal, int beauty)
2641 {
2642         EditVert *ev;
2643         float percent;
2644
2645         if (beauty & (B_PERCENTSUBD) && totpoint == 1)
2646                 //percent=(float)(edge->tmp.l)/32768.0f;
2647                 percent= edge->tmp.fp;
2648         else
2649                 percent= (float)curpoint/(float)(totpoint+1);
2650
2651         ev= subdivide_edge_addvert(em, edge, smooth, fractal, beauty, percent);
2652         ev->f = edge->v1->f;
2653
2654         return ev;
2655 }
2656
2657 void esubdivideflag(Object *obedit, EditMesh *em, int flag, float smooth, float fractal, int beauty, int numcuts, int corner_pattern, int seltype)
2658 {
2659         EditFace *ef;
2660         EditEdge *eed, *cedge, *sort[4];
2661         EditVert *eve, **templist;
2662         struct GHash *gh;
2663         float length[4], v1mat[3], v2mat[3], v3mat[3], v4mat[3];
2664         int i, j, edgecount, touchcount, facetype,hold;
2665         ModifierData *md= obedit->modifiers.first;
2666         int ctrl= 0; // XXX
2667
2668         //Set faces f1 to 0 cause we need it later
2669         for(ef=em->faces.first;ef;ef = ef->next) ef->f1 = 0;
2670         for(eve=em->verts.first; eve; eve=eve->next) {
2671                 if(!(beauty & B_KNIFE)) /* knife sets this flag for vertex cuts */
2672                         eve->f1 = 0;
2673                 eve->f2 = 0;
2674         }
2675
2676         for (; md; md=md->next) {
2677                 if (md->type==eModifierType_Mirror) {
2678                         MirrorModifierData *mmd = (MirrorModifierData*) md;
2679
2680                         if(mmd->flag & MOD_MIR_CLIPPING) {
2681                                 for (eve= em->verts.first; eve; eve= eve->next) {
2682                                         eve->f2= 0;
2683                                         switch(mmd->axis){
2684                                                 case 0:
2685                                                         if (fabsf(eve->co[0]) < mmd->tolerance)
2686                                                                 eve->f2 |= 1;
2687                                                         break;
2688                                                 case 1:
2689                                                         if (fabsf(eve->co[1]) < mmd->tolerance)
2690                                                                 eve->f2 |= 2;
2691                                                         break;
2692                                                 case 2:
2693                                                         if (fabsf(eve->co[2]) < mmd->tolerance)
2694                                                                 eve->f2 |= 4;
2695                                                         break;
2696                                         }
2697                                 }
2698                         }
2699                 }
2700         }
2701
2702         //Flush vertex flags upward to the edges
2703         for(eed = em->edges.first;eed;eed = eed->next) {
2704                 //if(eed->f & flag && eed->v1->f == eed->v2->f) {
2705                 //      eed->f |= eed->v1->f;
2706                 // }
2707                 eed->f2 = 0;
2708                 if(eed->f & flag) {
2709                         eed->f2 |= EDGEOLD;
2710                 }
2711         }
2712
2713         // We store an array of verts for each edge that is subdivided,
2714         // we put this array as a value in a ghash which is keyed by the EditEdge*
2715
2716         // Now for beauty subdivide deselect edges based on length
2717         if(beauty & B_BEAUTY) {
2718                 for(ef = em->faces.first;ef;ef = ef->next) {
2719                         if(!ef->v4) {
2720                                 continue;
2721                         }
2722                         if(ef->f & SELECT) {
2723                                 VECCOPY(v1mat, ef->v1->co);
2724                                 VECCOPY(v2mat, ef->v2->co);
2725                                 VECCOPY(v3mat, ef->v3->co);
2726                                 VECCOPY(v4mat, ef->v4->co);
2727                                 mul_mat3_m4_v3(obedit->obmat, v1mat);
2728                                 mul_mat3_m4_v3(obedit->obmat, v2mat);
2729                                 mul_mat3_m4_v3(obedit->obmat, v3mat);
2730                                 mul_mat3_m4_v3(obedit->obmat, v4mat);
2731
2732                                 length[0] = len_v3v3(v1mat, v2mat);
2733                                 length[1] = len_v3v3(v2mat, v3mat);
2734                                 length[2] = len_v3v3(v3mat, v4mat);
2735                                 length[3] = len_v3v3(v4mat, v1mat);
2736                                 sort[0] = ef->e1;
2737                                 sort[1] = ef->e2;
2738                                 sort[2] = ef->e3;
2739                                 sort[3] = ef->e4;
2740
2741
2742                                 // Beauty Short Edges
2743                                 if(beauty & B_BEAUTY_SHORT) {
2744                                         for(j=0;j<2;j++) {
2745                                                 hold = -1;
2746                                                 for(i=0;i<4;i++) {
2747                                                         if(length[i] < 0) {
2748                                                                 continue;
2749                                                         } else if(hold == -1) {
2750                                                                 hold = i;
2751                                                         } else {
2752                                                                 if(length[hold] < length[i]) {
2753                                                                         hold = i;
2754                                                                 }
2755                                                         }
2756                                                 }
2757                                                 if (hold > -1) {
2758                                                         sort[hold]->f &= ~SELECT;
2759                                                         sort[hold]->f2 |= EDGENEW;
2760                                                         length[hold] = -1;
2761                                                 }
2762                                         }
2763                                 }
2764
2765                                 // Beauty Long Edges
2766                                 else {
2767                                         for(j=0;j<2;j++) {
2768                                                 hold = -1;
2769                                                 for(i=0;i<4;i++) {
2770                                                         if(length[i] < 0) {
2771                                                                 continue;
2772                                                         } else if(hold == -1) {
2773                                                                 hold = i;
2774                                                         } else {
2775                                                                 if(length[hold] > length[i]) {
2776                                                                         hold = i;
2777                                                                 }
2778                                                         }
2779                                                 }
2780                                                 if (hold > -1) {
2781                                                         sort[hold]->f &= ~SELECT;
2782                                                         sort[hold]->f2 |= EDGENEW;
2783                                                         length[hold] = -1;
2784                                                 }
2785                                         }
2786                                 }
2787                         }
2788                 }
2789         }
2790
2791         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "subdivideedgenum gh");
2792
2793         // If we are knifing, We only need the selected edges that were cut, so deselect if it was not cut
2794         if(beauty & B_KNIFE) {
2795                 for(eed= em->edges.first;eed;eed=eed->next) {
2796                         if( eed->tmp.fp == 0 ) {
2797                                 EM_select_edge(eed,0);
2798                         }
2799                 }
2800         }
2801         // So for each edge, if it is selected, we allocate an array of size cuts+2
2802         // so we can have a place for the v1, the new verts and v2
2803         for(eed=em->edges.first;eed;eed = eed->next) {
2804                 if(eed->f & flag) {
2805                         templist = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"vertlist");
2806                         templist[0] = eed->v1;
2807                         for(i=0;i<numcuts;i++) {
2808                                 // This function creates the new vert and returns it back
2809                                 // to the array
2810                                 templist[i+1] = subdivideedgenum(em, eed, i+1, numcuts, smooth, fractal, beauty);
2811                                 //while we are here, we can copy edge info from the original edge
2812                                 cedge = addedgelist(em, templist[i],templist[i+1],eed);
2813                                 // Also set the edge f2 to EDGENEW so that we can use this info later
2814                                 cedge->f2 = EDGENEW;
2815                         }
2816                         templist[i+1] = eed->v2;
2817                         //Do the last edge too
2818                         cedge = addedgelist(em, templist[i],templist[i+1],eed);
2819                         cedge->f2 = EDGENEW;
2820                         // Now that the edge is subdivided, we can put its verts in the ghash
2821                         BLI_ghash_insert(gh, eed, templist);
2822                 }
2823         }
2824
2825 //      DAG_id_tag_update(obedit->data, 0);
2826         // Now for each face in the mesh we need to figure out How many edges were cut
2827         // and which filling method to use for that face
2828         for(ef = em->faces.first;ef;ef = ef->next) {
2829                 edgecount = 0;
2830                 facetype = 3;
2831                 if(ef->e1->f & flag) {edgecount++;}
2832                 if(ef->e2->f & flag) {edgecount++;}
2833                 if(ef->e3->f & flag) {edgecount++;}
2834                 if(ef->v4) {
2835                         facetype = 4;
2836                         if(ef->e4->f & flag) {edgecount++;}
2837                 }
2838                 if(facetype == 4) {
2839                         switch(edgecount) {
2840                                 case 0:
2841                                         if(beauty & B_KNIFE && numcuts == 1){
2842                                                 /*Test for when knifing through two opposite verts but no edges*/
2843                                                 touchcount = 0;
2844                                                 if(ef->v1->f1) touchcount++;
2845                                                 if(ef->v2->f1) touchcount++;
2846                                                 if(ef->v3->f1) touchcount++;
2847                                                 if(ef->v4->f1) touchcount++;
2848                                                 if(touchcount == 2){
2849                                                         if(ef->v1->f1 && ef->v3->f1){
2850                                                                 ef->f1 = SELECT;
2851                                                                 fill_quad_doublevert(em, ef, 1, 3);
2852                                                         }
2853                                                         else if(ef->v2->f1 && ef->v4->f1){
2854                                                                 ef->f1 = SELECT;
2855                                                                 fill_quad_doublevert(em, ef, 2, 4);
2856                                                         }
2857                                                 }
2858                                         }
2859                                         break;
2860
2861                                 case 1:
2862                                         if(beauty & B_KNIFE && numcuts == 1){
2863                                                 /*Test for when knifing through an edge and one vert*/
2864                                                 touchcount = 0;
2865                                                 if(ef->v1->f1) touchcount++;
2866                                                 if(ef->v2->f1) touchcount++;
2867                                                 if(ef->v3->f1) touchcount++;
2868                                                 if(ef->v4->f1) touchcount++;
2869
2870                                                 if(touchcount == 1){
2871                                                         if( (ef->e1->f & flag && ( !ef->e1->v1->f1 && !ef->e1->v2->f1 )) ||
2872                                                                 (ef->e2->f & flag && ( !ef->e2->v1->f1 && !ef->e2->v2->f1 )) ||
2873                                                                 (ef->e3->f & flag && ( !ef->e3->v1->f1 && !ef->e3->v2->f1 )) ||
2874                                                                 (ef->e4->f & flag && ( !ef->e4->v1->f1 && !ef->e4->v2->f1 )) ){
2875
2876                                                                 ef->f1 = SELECT;
2877                                                                 fill_quad_singlevert(em, ef, gh);
2878                                                         }
2879                                                         else{
2880                                                                 ef->f1 = SELECT;
2881                                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2882                                                         }
2883                                                 }
2884                                                 else{
2885                                                         ef->f1 = SELECT;
2886                                                         fill_quad_single(em, ef, gh, numcuts, seltype);
2887                                                 }
2888                                         }
2889                                         else{
2890                                                 ef->f1 = SELECT;
2891                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2892                                         }
2893                                         break;
2894                                 case 2: ef->f1 = SELECT;
2895                                         // if there are 2, we check if edge 1 and 3 are either both on or off that way
2896                                         // we can tell if the selected pair is Adjacent or Opposite of each other
2897                                         if((ef->e1->f & flag && ef->e3->f & flag) ||
2898                                            (ef->e2->f & flag && ef->e4->f & flag)) {
2899                                                 fill_quad_double_op(em, ef, gh, numcuts);
2900                                         }else{
2901                                                 switch(corner_pattern) {
2902                                                         case 0: fill_quad_double_adj_path(em, ef, gh, numcuts); break;
2903                                                         case 1: fill_quad_double_adj_inner(em, ef, gh, numcuts); break;
2904                                                         case 2: fill_quad_double_adj_fan(em, ef, gh, numcuts); break;
2905                                                 }
2906
2907                                         }
2908                                                 break;
2909                                 case 3: ef->f1 = SELECT;
2910                                         fill_quad_triple(em, ef, gh, numcuts);
2911                                         break;
2912                                 case 4: ef->f1 = SELECT;
2913                                         fill_quad_quadruple(em, ef, gh, numcuts, smooth, fractal, beauty);
2914                                         break;
2915                         }
2916                 } else {
2917                         switch(edgecount) {
2918                                 case 0: break;
2919                                 case 1: ef->f1 = SELECT;
2920                                         fill_tri_single(em, ef, gh, numcuts, seltype);
2921                                         break;
2922                                 case 2: ef->f1 = SELECT;
2923                                         fill_tri_double(em, ef, gh, numcuts);
2924                                         break;
2925                                 case 3: ef->f1 = SELECT;
2926                                         fill_tri_triple(em, ef, gh, numcuts, smooth, fractal, beauty);
2927                                         break;
2928                         }
2929                 }
2930         }
2931
2932         // Delete Old Edges and Faces
2933         for(eed = em->edges.first;eed;eed = eed->next) {
2934                 if(BLI_ghash_haskey(gh,eed)) {
2935                         eed->f1 = SELECT;
2936                 } else {
2937                         eed->f1 = 0;
2938                 }
2939         }
2940         free_tagged_edges_faces(em, em->edges.first, em->faces.first);
2941
2942         if(seltype == SUBDIV_SELECT_ORIG  && !ctrl) {
2943                 /* bugfix: vertex could get flagged as "not-selected"
2944                 // solution: clear flags before, not at the same time as setting SELECT flag -dg
2945                 */
2946                 for(eed = em->edges.first;eed;eed = eed->next) {
2947                         if(!(eed->f2 & EDGENEW || eed->f2 & EDGEOLD)) {
2948                                 eed->f &= !flag;
2949                                 EM_select_edge(eed,0);
2950                         }
2951                 }
2952                 for(eed = em->edges.first;eed;eed = eed->next) {
2953                         if(eed->f2 & EDGENEW || eed->f2 & EDGEOLD) {
2954                                 eed->f |= flag;
2955                                 EM_select_edge(eed,1);
2956                         }
2957                 }
2958         } else if ((seltype == SUBDIV_SELECT_INNER || seltype == SUBDIV_SELECT_INNER_SEL)|| ctrl) {
2959                 for(eed = em->edges.first;eed;eed = eed->next) {
2960                         if(eed->f2 & EDGEINNER) {
2961                                 eed->f |= flag;
2962                                 EM_select_edge(eed,1);
2963                                 if(eed->v1->f & EDGEINNER) eed->v1->f |= SELECT;
2964                                 if(eed->v2->f & EDGEINNER)