fix [#26674] Inconsistency in snapping CursorToSelection between UV_Editor and 3d_View.
[blender.git] / source / blender / editors / mesh / editmesh_tools.c
1  /* $Id$
2  *
3  * ***** BEGIN GPL LICENSE BLOCK *****
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software Foundation,
17  * Inc., 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(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         RegionView3D *rv3d = ED_view3d_context_rv3d(C);
900
901         int steps = RNA_int_get(op->ptr,"steps");
902
903         float offs = RNA_float_get(op->ptr,"offset");
904
905         float dvec[3], tmat[3][3], bmat[3][3], nor[3]= {0.0, 0.0, 0.0};
906         short a;
907
908         /* dvec */
909         dvec[0]= rv3d->persinv[2][0];
910         dvec[1]= rv3d->persinv[2][1];
911         dvec[2]= rv3d->persinv[2][2];
912         normalize_v3(dvec);
913         dvec[0]*= offs;
914         dvec[1]*= offs;
915         dvec[2]*= offs;
916
917         /* base correction */
918         copy_m3_m4(bmat, obedit->obmat);
919         invert_m3_m3(tmat, bmat);
920         mul_m3_v3(tmat, dvec);
921
922         for(a=0; a<steps; a++) {
923                 extrudeflag(obedit, em, SELECT, nor, 0);
924                 translateflag(em, SELECT, dvec);
925         }
926
927         recalc_editnormals(em);
928
929         EM_fgon_flags(em);
930
931         DAG_id_tag_update(obedit->data, 0);
932         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
933
934         BKE_mesh_end_editmesh(obedit->data, em);
935         return OPERATOR_FINISHED;
936 }
937
938 void MESH_OT_extrude_repeat(wmOperatorType *ot)
939 {
940         /* identifiers */
941         ot->name= "Extrude Repeat Mesh";
942         ot->description= "Extrude selected vertices, edges or faces repeatedly";
943         ot->idname= "MESH_OT_extrude_repeat";
944
945         /* api callbacks */
946         ot->exec= extrude_repeat_mesh;
947         ot->poll= ED_operator_editmesh_region_view3d;
948
949         /* flags */
950         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
951
952         /* props */
953         RNA_def_float(ot->srna, "offset", 2.0f, 0.0f, 100.0f, "Offset", "", 0.0f, FLT_MAX);
954         RNA_def_int(ot->srna, "steps", 10, 0, 180, "Steps", "", 0, INT_MAX);
955 }
956
957 /* ************************** spin operator ******************** */
958
959
960 static int spin_mesh(bContext *C, wmOperator *op, float *dvec, int steps, float degr, int dupli )
961 {
962         Object *obedit= CTX_data_edit_object(C);
963         ToolSettings *ts= CTX_data_tool_settings(C);
964         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
965         EditVert *eve,*nextve;
966         float nor[3]= {0.0f, 0.0f, 0.0f};
967         float si, n[3], q[4], cmat[3][3], imat[3][3], tmat[3][3];
968         float cent[3], bmat[3][3];
969         float phi;
970         short a, ok= 1;
971
972         RNA_float_get_array(op->ptr, "center", cent);
973
974         /* imat and center and size */
975         copy_m3_m4(bmat, obedit->obmat);
976         invert_m3_m3(imat,bmat);
977
978         cent[0]-= obedit->obmat[3][0];
979         cent[1]-= obedit->obmat[3][1];
980         cent[2]-= obedit->obmat[3][2];
981         mul_m3_v3(imat, cent);
982
983         phi= degr*(float)M_PI/360.0f;
984         phi/= steps;
985         if(ts->editbutflag & B_CLOCKWISE) phi= -phi;
986
987         RNA_float_get_array(op->ptr, "axis", n);
988         normalize_v3(n);
989
990         q[0]= (float)cos(phi);
991         si= (float)sin(phi);
992         q[1]= n[0]*si;
993         q[2]= n[1]*si;
994         q[3]= n[2]*si;
995         quat_to_mat3( cmat,q);
996
997         mul_m3_m3m3(tmat,cmat,bmat);
998         mul_m3_m3m3(bmat,imat,tmat);
999
1000         if(dupli==0)
1001                 if(ts->editbutflag & B_KEEPORIG)
1002                         adduplicateflag(em, 1);
1003
1004         for(a=0; a<steps; a++) {
1005                 if(dupli==0) ok= extrudeflag(obedit, em, SELECT, nor, 0);
1006                 else adduplicateflag(em, SELECT);
1007
1008                 if(ok==0)
1009                         break;
1010
1011                 rotateflag(em, SELECT, cent, bmat);
1012                 if(dvec) {
1013                         mul_m3_v3(bmat,dvec);
1014                         translateflag(em, SELECT, dvec);
1015                 }
1016         }
1017
1018         if(ok==0) {
1019                 /* no vertices or only loose ones selected, remove duplicates */
1020                 eve= em->verts.first;
1021                 while(eve) {
1022                         nextve= eve->next;
1023                         if(eve->f & SELECT) {
1024                                 BLI_remlink(&em->verts,eve);
1025                                 free_editvert(em, eve);
1026                         }
1027                         eve= nextve;
1028                 }
1029         }
1030         else {
1031                 recalc_editnormals(em);
1032
1033                 EM_fgon_flags(em);
1034
1035                 DAG_id_tag_update(obedit->data, 0);
1036         }
1037
1038         BKE_mesh_end_editmesh(obedit->data, em);
1039         return ok;
1040 }
1041
1042 static int spin_mesh_exec(bContext *C, wmOperator *op)
1043 {
1044         Object *obedit= CTX_data_edit_object(C);
1045         int ok;
1046
1047         ok= spin_mesh(C, op, NULL, RNA_int_get(op->ptr,"steps"), RNA_float_get(op->ptr,"degrees"), RNA_boolean_get(op->ptr,"dupli"));
1048         if(ok==0) {
1049                 BKE_report(op->reports, RPT_WARNING, "No valid vertices are selected");
1050                 return OPERATOR_CANCELLED;
1051         }
1052
1053         DAG_id_tag_update(obedit->data, 0);
1054         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
1055
1056         return OPERATOR_FINISHED;
1057 }
1058
1059 /* get center and axis, in global coords */
1060 static int spin_mesh_invoke(bContext *C, wmOperator *op, wmEvent *UNUSED(event))
1061 {
1062         Scene *scene = CTX_data_scene(C);
1063         View3D *v3d = CTX_wm_view3d(C);
1064         RegionView3D *rv3d= ED_view3d_context_rv3d(C);
1065
1066         RNA_float_set_array(op->ptr, "center", give_cursor(scene, v3d));
1067         RNA_float_set_array(op->ptr, "axis", rv3d->viewinv[2]);
1068
1069         return spin_mesh_exec(C, op);
1070 }
1071
1072 void MESH_OT_spin(wmOperatorType *ot)
1073 {
1074         /* identifiers */
1075         ot->name= "Spin";
1076         ot->description= "Extrude selected vertices in a circle around the cursor in indicated viewport";
1077         ot->idname= "MESH_OT_spin";
1078
1079         /* api callbacks */
1080         ot->invoke= spin_mesh_invoke;
1081         ot->exec= spin_mesh_exec;
1082         ot->poll= EM_view3d_poll;
1083
1084         /* flags */
1085         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1086
1087         /* props */
1088         RNA_def_int(ot->srna, "steps", 9, 0, INT_MAX, "Steps", "Steps", 0, 128);
1089         RNA_def_boolean(ot->srna, "dupli", 0, "Dupli", "Make Duplicates");
1090         RNA_def_float(ot->srna, "degrees", 90.0f, -FLT_MAX, FLT_MAX, "Degrees", "Degrees", -360.0f, 360.0f);
1091
1092         RNA_def_float_vector_xyz(ot->srna, "center", 3, NULL, -FLT_MAX, FLT_MAX, "Center", "Center in global view space", -FLT_MAX, FLT_MAX);
1093         RNA_def_float_vector(ot->srna, "axis", 3, NULL, -1.0f, 1.0f, "Axis", "Axis in global view space", -FLT_MAX, FLT_MAX);
1094
1095 }
1096
1097 static int screw_mesh_exec(bContext *C, wmOperator *op)
1098 {
1099         Object *obedit= CTX_data_edit_object(C);
1100         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
1101         EditVert *eve,*v1=0,*v2=0;
1102         EditEdge *eed;
1103         float dvec[3], nor[3];
1104         int steps, turns;
1105
1106         turns= RNA_int_get(op->ptr, "turns");
1107         steps= RNA_int_get(op->ptr, "steps");
1108
1109         /* clear flags */
1110         for(eve= em->verts.first; eve; eve= eve->next)
1111                 eve->f1= 0;
1112
1113         /* edges set flags in verts */
1114         for(eed= em->edges.first; eed; eed= eed->next) {
1115                 if(eed->v1->f & SELECT) {
1116                         if(eed->v2->f & SELECT) {
1117                                 /* watch: f1 is a byte */
1118                                 if(eed->v1->f1<2) eed->v1->f1++;
1119                                 if(eed->v2->f1<2) eed->v2->f1++;
1120                         }
1121                 }
1122         }
1123         /* find two vertices with eve->f1==1, more or less is wrong */
1124         for(eve= em->verts.first; eve; eve= eve->next) {
1125                 if(eve->f1==1) {
1126                         if(v1==NULL) v1= eve;
1127                         else if(v2==NULL) v2= eve;
1128                         else {
1129                                 v1= NULL;
1130                                 break;
1131                         }
1132                 }
1133         }
1134         if(v1==NULL || v2==NULL) {
1135                 BKE_report(op->reports, RPT_WARNING, "You have to select a string of connected vertices too");
1136                 BKE_mesh_end_editmesh(obedit->data, em);
1137                 return OPERATOR_CANCELLED;
1138         }
1139
1140         /* calculate dvec */
1141         dvec[0]= ( v1->co[0]- v2->co[0] )/steps;
1142         dvec[1]= ( v1->co[1]- v2->co[1] )/steps;
1143         dvec[2]= ( v1->co[2]- v2->co[2] )/steps;
1144
1145         VECCOPY(nor, obedit->obmat[2]);
1146
1147         if(nor[0]*dvec[0]+nor[1]*dvec[1]+nor[2]*dvec[2]>0.0f) {
1148                 negate_v3(dvec);
1149         }
1150
1151         if(spin_mesh(C, op, dvec, turns*steps, 360.0f*turns, 0)) {
1152                 DAG_id_tag_update(obedit->data, 0);
1153                 WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
1154
1155                 BKE_mesh_end_editmesh(obedit->data, em);
1156                 return OPERATOR_FINISHED;
1157         }
1158         else {
1159                 BKE_report(op->reports, RPT_WARNING, "No valid vertices are selected");
1160                 BKE_mesh_end_editmesh(obedit->data, em);
1161                 return OPERATOR_CANCELLED;
1162         }
1163 }
1164
1165 /* get center and axis, in global coords */
1166 static int screw_mesh_invoke(bContext *C, wmOperator *op, wmEvent *UNUSED(event))
1167 {
1168         Scene *scene = CTX_data_scene(C);
1169         View3D *v3d = CTX_wm_view3d(C);
1170         RegionView3D *rv3d= ED_view3d_context_rv3d(C);
1171
1172         RNA_float_set_array(op->ptr, "center", give_cursor(scene, v3d));
1173         RNA_float_set_array(op->ptr, "axis", rv3d->viewinv[1]);
1174
1175         return screw_mesh_exec(C, op);
1176 }
1177
1178 void MESH_OT_screw(wmOperatorType *ot)
1179 {
1180         /* identifiers */
1181         ot->name= "Screw";
1182         ot->description= "Extrude selected vertices in screw-shaped rotation around the cursor in indicated viewport";
1183         ot->idname= "MESH_OT_screw";
1184
1185         /* api callbacks */
1186         ot->invoke= screw_mesh_invoke;
1187         ot->exec= screw_mesh_exec;
1188         ot->poll= EM_view3d_poll;
1189
1190         /* flags */
1191         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1192
1193         /*props */
1194         RNA_def_int(ot->srna, "steps", 9, 0, INT_MAX, "Steps", "Steps", 0, 256);
1195         RNA_def_int(ot->srna, "turns", 1, 0, INT_MAX, "Turns", "Turns", 0, 256);
1196
1197         RNA_def_float_vector_xyz(ot->srna, "center", 3, NULL, -FLT_MAX, FLT_MAX, "Center", "Center in global view space", -FLT_MAX, FLT_MAX);
1198         RNA_def_float_vector(ot->srna, "axis", 3, NULL, -1.0f, 1.0f, "Axis", "Axis in global view space", -FLT_MAX, FLT_MAX);
1199 }
1200
1201 static void erase_edges(EditMesh *em, ListBase *l)
1202 {
1203         EditEdge *ed, *nexted;
1204
1205         ed = (EditEdge *) l->first;
1206         while(ed) {
1207                 nexted= ed->next;
1208                 if( (ed->v1->f & SELECT) || (ed->v2->f & SELECT) ) {
1209                         remedge(em, ed);
1210                         free_editedge(em, ed);
1211                 }
1212                 ed= nexted;
1213         }
1214 }
1215
1216 static void erase_faces(EditMesh *em, ListBase *l)
1217 {
1218         EditFace *f, *nextf;
1219
1220         f = (EditFace *) l->first;
1221
1222         while(f) {
1223                 nextf= f->next;
1224                 if( faceselectedOR(f, SELECT) ) {
1225                         BLI_remlink(l, f);
1226                         free_editface(em, f);
1227                 }
1228                 f = nextf;
1229         }
1230 }
1231
1232 static void erase_vertices(EditMesh *em, ListBase *l)
1233 {
1234         EditVert *v, *nextv;
1235
1236         v = (EditVert *) l->first;
1237         while(v) {
1238                 nextv= v->next;
1239                 if(v->f & 1) {
1240                         BLI_remlink(l, v);
1241                         free_editvert(em, v);
1242                 }
1243                 v = nextv;
1244         }
1245 }
1246
1247 static void delete_mesh(EditMesh *em, wmOperator *op, int event)
1248 {
1249         EditFace *efa, *nextvl;
1250         EditVert *eve,*nextve;
1251         EditEdge *eed,*nexted;
1252         int count;
1253         /* const char *str="Erase"; */
1254
1255
1256         if(event<1) return;
1257
1258         if(event==10 ) {
1259                 /* str= "Erase Vertices"; */
1260                 erase_edges(em, &em->edges);
1261                 erase_faces(em, &em->faces);
1262                 erase_vertices(em, &em->verts);
1263         }
1264         else if(event==6) {
1265                 if(!EdgeLoopDelete(em, op))
1266                         return;
1267
1268                 /* str= "Erase Edge Loop"; */
1269         }
1270         else if(event==4) {
1271                 /* str= "Erase Edges & Faces"; */
1272                 efa= em->faces.first;
1273                 while(efa) {
1274                         nextvl= efa->next;
1275                         /* delete only faces with 1 or more edges selected */
1276                         count= 0;
1277                         if(efa->e1->f & SELECT) count++;
1278                         if(efa->e2->f & SELECT) count++;
1279                         if(efa->e3->f & SELECT) count++;
1280                         if(efa->e4 && (efa->e4->f & SELECT)) count++;
1281                         if(count) {
1282                                 BLI_remlink(&em->faces, efa);
1283                                 free_editface(em, efa);
1284                         }
1285                         efa= nextvl;
1286                 }
1287                 eed= em->edges.first;
1288                 while(eed) {
1289                         nexted= eed->next;
1290                         if(eed->f & SELECT) {
1291                                 remedge(em, eed);
1292                                 free_editedge(em, eed);
1293                         }
1294                         eed= nexted;
1295                 }
1296                 efa= em->faces.first;
1297                 while(efa) {
1298                         nextvl= efa->next;
1299                         event=0;
1300                         if( efa->v1->f & SELECT) event++;
1301                         if( efa->v2->f & SELECT) event++;
1302                         if( efa->v3->f & SELECT) event++;
1303                         if(efa->v4 && (efa->v4->f & SELECT)) event++;
1304
1305                         if(event>1) {
1306                                 BLI_remlink(&em->faces, efa);
1307                                 free_editface(em, efa);
1308                         }
1309                         efa= nextvl;
1310                 }
1311         }
1312         else if(event==1) {
1313                 /* str= "Erase Edges"; */
1314                 // faces first
1315                 efa= em->faces.first;
1316                 while(efa) {
1317                         nextvl= efa->next;
1318                         event=0;
1319                         if( efa->e1->f & SELECT) event++;
1320                         if( efa->e2->f & SELECT) event++;
1321                         if( efa->e3->f & SELECT) event++;
1322                         if(efa->e4 && (efa->e4->f & SELECT)) event++;
1323
1324                         if(event) {
1325                                 BLI_remlink(&em->faces, efa);
1326                                 free_editface(em, efa);
1327                         }
1328                         efa= nextvl;
1329                 }
1330                 eed= em->edges.first;
1331                 while(eed) {
1332                         nexted= eed->next;
1333                         if(eed->f & SELECT) {
1334                                 remedge(em, eed);
1335                                 free_editedge(em, eed);
1336                         }
1337                         eed= nexted;
1338                 }
1339                 /* to remove loose vertices: */
1340                 eed= em->edges.first;
1341                 while(eed) {
1342                         if( eed->v1->f & SELECT) eed->v1->f-=SELECT;
1343                         if( eed->v2->f & SELECT) eed->v2->f-=SELECT;
1344                         eed= eed->next;
1345                 }
1346                 eve= em->verts.first;
1347                 while(eve) {
1348                         nextve= eve->next;
1349                         if(eve->f & SELECT) {
1350                                 BLI_remlink(&em->verts,eve);
1351                                 free_editvert(em, eve);
1352                         }
1353                         eve= nextve;
1354                 }
1355
1356         }
1357         else if(event==2) {
1358                 /* str="Erase Faces"; */
1359                 delfaceflag(em, SELECT);
1360         }
1361         else if(event==3) {
1362                 /* str= "Erase All"; */
1363                 if(em->verts.first) free_vertlist(em, &em->verts);
1364                 if(em->edges.first) free_edgelist(em, &em->edges);
1365                 if(em->faces.first) free_facelist(em, &em->faces);
1366                 if(em->selected.first) BLI_freelistN(&(em->selected));
1367         }
1368         else if(event==5) {
1369                 /* str= "Erase Only Faces"; */
1370                 efa= em->faces.first;
1371                 while(efa) {
1372                         nextvl= efa->next;
1373                         if(efa->f & SELECT) {
1374                                 BLI_remlink(&em->faces, efa);
1375                                 free_editface(em, efa);
1376                         }
1377                         efa= nextvl;
1378                 }
1379         }
1380
1381         EM_fgon_flags(em);      // redo flags and indices for fgons
1382 }
1383
1384 /* Note, these values must match delete_mesh() event values */
1385 static EnumPropertyItem prop_mesh_delete_types[] = {
1386         {10,"VERT",             0, "Vertices", ""},
1387         {1, "EDGE",             0, "Edges", ""},
1388         {2, "FACE",             0, "Faces", ""},
1389         {3, "ALL",              0, "All", ""},
1390         {4, "EDGE_FACE",0, "Edges & Faces", ""},
1391         {5, "ONLY_FACE",0, "Only Faces", ""},
1392         {6, "EDGE_LOOP",0, "Edge Loop", ""},
1393         {0, NULL, 0, NULL, NULL}
1394 };
1395
1396 static int delete_mesh_exec(bContext *C, wmOperator *op)
1397 {
1398         Object *obedit= CTX_data_edit_object(C);
1399         EditMesh *em= BKE_mesh_get_editmesh((Mesh *)obedit->data);
1400         int type= RNA_enum_get(op->ptr, "type");
1401
1402         if(type==6)
1403                 return WM_operator_name_call(C, "MESH_OT_delete_edgeloop", WM_OP_EXEC_DEFAULT, NULL);
1404
1405         delete_mesh(em, op, type);
1406
1407         DAG_id_tag_update(obedit->data, 0);
1408         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
1409
1410         BKE_mesh_end_editmesh(obedit->data, em);
1411         return OPERATOR_FINISHED;
1412 }
1413
1414 void MESH_OT_delete(wmOperatorType *ot)
1415 {
1416         /* identifiers */
1417         ot->name= "Delete";
1418         ot->description= "Delete selected vertices, edges or faces";
1419         ot->idname= "MESH_OT_delete";
1420
1421         /* api callbacks */
1422         ot->invoke= WM_menu_invoke;
1423         ot->exec= delete_mesh_exec;
1424
1425         ot->poll= ED_operator_editmesh;
1426
1427         /* flags */
1428         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1429
1430         /*props */
1431         ot->prop= RNA_def_enum(ot->srna, "type", prop_mesh_delete_types, 10, "Type", "Method used for deleting mesh data");
1432 }
1433
1434
1435 /*GB*/
1436 /*-------------------------------------------------------------------------------*/
1437 /*--------------------------- Edge Based Subdivide ------------------------------*/
1438
1439 #define EDGENEW 2
1440 #define FACENEW 2
1441 #define EDGEINNER  4
1442 #define EDGEOLD  8
1443
1444 /*used by faceloop cut to select only edges valid for edge slide*/
1445 #define DOUBLEOPFILL 16
1446
1447 /* calculates offset for co, based on fractal, sphere or smooth settings  */
1448 static void alter_co(float *co, EditEdge *edge, float smooth, float fractal, int beauty, float perc)
1449 {
1450         float vec1[3], fac;
1451
1452         if(beauty & B_SMOOTH) {
1453                 /* we calculate an offset vector vec1[], to be added to *co */
1454                 float len, fac, nor[3], nor1[3], nor2[3];
1455
1456                 sub_v3_v3v3(nor, edge->v1->co, edge->v2->co);
1457                 len= 0.5f*normalize_v3(nor);
1458
1459                 VECCOPY(nor1, edge->v1->no);
1460                 VECCOPY(nor2, edge->v2->no);
1461
1462                 /* cosine angle */
1463                 fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
1464
1465                 vec1[0]= fac*nor1[0];
1466                 vec1[1]= fac*nor1[1];
1467                 vec1[2]= fac*nor1[2];
1468
1469                 /* cosine angle */
1470                 fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
1471
1472                 vec1[0]+= fac*nor2[0];
1473                 vec1[1]+= fac*nor2[1];
1474                 vec1[2]+= fac*nor2[2];
1475
1476                 /* falloff for multi subdivide */
1477                 smooth *= sqrtf(fabs(1.0f - 2.0f*fabsf(0.5f-perc)));
1478
1479                 vec1[0]*= smooth*len;
1480                 vec1[1]*= smooth*len;
1481                 vec1[2]*= smooth*len;
1482
1483                 co[0] += vec1[0];
1484                 co[1] += vec1[1];
1485                 co[2] += vec1[2];
1486         }
1487         else if(beauty & B_SPHERE) { /* subdivide sphere */
1488                 normalize_v3(co);
1489                 co[0]*= smooth;
1490                 co[1]*= smooth;
1491                 co[2]*= smooth;
1492         }
1493
1494         if(beauty & B_FRACTAL) {
1495                 fac= fractal*len_v3v3(edge->v1->co, edge->v2->co);
1496                 vec1[0]= fac*(float)(0.5-BLI_drand());
1497                 vec1[1]= fac*(float)(0.5-BLI_drand());
1498                 vec1[2]= fac*(float)(0.5-BLI_drand());
1499                 add_v3_v3(co, vec1);
1500         }
1501 }
1502
1503 /* assumes in the edge is the correct interpolated vertices already */
1504 /* percent defines the interpolation, smooth, fractal and beauty are for special options */
1505 /* results in new vertex with correct coordinate, vertex normal and weight group info */
1506 static EditVert *subdivide_edge_addvert(EditMesh *em, EditEdge *edge, float smooth, float fractal, int beauty, float percent)
1507 {
1508         EditVert *ev;
1509         float co[3];
1510
1511         co[0] = (edge->v2->co[0]-edge->v1->co[0])*percent + edge->v1->co[0];
1512         co[1] = (edge->v2->co[1]-edge->v1->co[1])*percent + edge->v1->co[1];
1513         co[2] = (edge->v2->co[2]-edge->v1->co[2])*percent + edge->v1->co[2];
1514
1515         /* offset for smooth or sphere or fractal */
1516         alter_co(co, edge, smooth, fractal, beauty, percent);
1517
1518         /* clip if needed by mirror modifier */
1519         if (edge->v1->f2) {
1520                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
1521                         co[0]= 0.0f;
1522                 }
1523                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
1524                         co[1]= 0.0f;
1525                 }
1526                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
1527                         co[2]= 0.0f;
1528                 }
1529         }
1530
1531         ev = addvertlist(em, co, NULL);
1532
1533         /* vert data (vgroups, ..) */
1534         EM_data_interp_from_verts(em, edge->v1, edge->v2, ev, percent);
1535
1536         /* normal */
1537         ev->no[0] = (edge->v2->no[0]-edge->v1->no[0])*percent + edge->v1->no[0];
1538         ev->no[1] = (edge->v2->no[1]-edge->v1->no[1])*percent + edge->v1->no[1];
1539         ev->no[2] = (edge->v2->no[2]-edge->v1->no[2])*percent + edge->v1->no[2];
1540         normalize_v3(ev->no);
1541
1542         return ev;
1543 }
1544
1545 static void flipvertarray(EditVert** arr, short size)
1546 {
1547         EditVert *hold;
1548         int i;
1549
1550         for(i=0; i<size/2; i++) {
1551                 hold = arr[i];
1552                 arr[i] = arr[size-i-1];
1553                 arr[size-i-1] = hold;
1554         }
1555 }
1556
1557 static void facecopy(EditMesh *em, EditFace *source, EditFace *target)
1558 {
1559         float *v1 = source->v1->co, *v2 = source->v2->co, *v3 = source->v3->co;
1560         float *v4 = source->v4? source->v4->co: NULL;
1561         float w[4][4];
1562
1563         CustomData_em_copy_data(&em->fdata, &em->fdata, source->data, &target->data);
1564
1565         target->mat_nr = source->mat_nr;
1566         target->flag   = source->flag;
1567         target->h          = source->h;
1568
1569         interp_weights_face_v3( w[0],v1, v2, v3, v4, target->v1->co);
1570         interp_weights_face_v3( w[1],v1, v2, v3, v4, target->v2->co);
1571         interp_weights_face_v3( w[2],v1, v2, v3, v4, target->v3->co);
1572         if (target->v4)
1573                 interp_weights_face_v3( w[3],v1, v2, v3, v4, target->v4->co);
1574
1575         CustomData_em_validate_data(&em->fdata, target->data, target->v4 ? 4 : 3);
1576         CustomData_em_interp(&em->fdata, &source->data, NULL, (float*)w, 1, target->data);
1577 }
1578
1579 static void fill_quad_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1580 {
1581         EditEdge *cedge=NULL;
1582         EditVert *v[4], **verts;
1583         EditFace *hold;
1584         short start=0, end, left, right, vertsize,i;
1585
1586         v[0] = efa->v1;
1587         v[1] = efa->v2;
1588         v[2] = efa->v3;
1589         v[3] = efa->v4;
1590
1591         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1592         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1593         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1594         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
1595
1596         // Point verts to the array of new verts for cedge
1597         verts = BLI_ghash_lookup(gh, cedge);
1598         //This is the index size of the verts array
1599         vertsize = numcuts+2;
1600
1601         // Is the original v1 the same as the first vert on the selected edge?
1602         // if not, the edge is running the opposite direction in this face so flip
1603         // the array to the correct direction
1604
1605         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1606         end     = (start+1)%4;
1607         left   = (start+2)%4;
1608         right  = (start+3)%4;
1609
1610         /*
1611         We should have something like this now
1612
1613                           end            start
1614                            3   2   1   0
1615                            |---*---*---|
1616                            |               |
1617                            |               |
1618                            |               |
1619                            -------------
1620                           left     right
1621
1622         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
1623         and 0,1,2... are the indexes of the new verts stored in verts
1624
1625         We will fill this case like this or this depending on even or odd cuts
1626
1627                            |---*---*---|                  |---*---|
1628                            |  /  \  |             |  / \  |
1629                            | /     \ |            | /   \ |
1630                            |/            \|               |/     \|
1631                            -------------                  ---------
1632         */
1633
1634         // Make center face
1635         if(vertsize % 2 == 0) {
1636                 hold = addfacelist(em, verts[(vertsize-1)/2],verts[((vertsize-1)/2)+1],v[left],v[right], NULL,NULL);
1637                 hold->e2->f2 |= EDGEINNER;
1638                 hold->e4->f2 |= EDGEINNER;
1639         }else{
1640                 hold = addfacelist(em, verts[(vertsize-1)/2],v[left],v[right],NULL, NULL,NULL);
1641                 hold->e1->f2 |= EDGEINNER;
1642                 hold->e3->f2 |= EDGEINNER;
1643         }
1644         facecopy(em, efa,hold);
1645
1646         // Make side faces
1647         for(i=0;i<(vertsize-1)/2;i++) {
1648                 hold = addfacelist(em, verts[i],verts[i+1],v[right],NULL,NULL,NULL);
1649                 facecopy(em, efa,hold);
1650                 if(i+1 != (vertsize-1)/2) {
1651                         if(seltype == SUBDIV_SELECT_INNER) {
1652                                 hold->e2->f2 |= EDGEINNER;
1653                         }
1654                 }
1655                 hold = addfacelist(em, verts[vertsize-2-i],verts[vertsize-1-i],v[left],NULL,NULL,NULL);
1656                 facecopy(em, efa,hold);
1657                 if(i+1 != (vertsize-1)/2) {
1658                         if(seltype == SUBDIV_SELECT_INNER) {
1659                                  hold->e3->f2 |= EDGEINNER;
1660                         }
1661                 }
1662         }
1663 }
1664
1665 static void fill_tri_single(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1666 {
1667         EditEdge *cedge=NULL;
1668         EditVert *v[3], **verts;
1669         EditFace *hold;
1670         short start=0, end, op, vertsize,i;
1671
1672         v[0] = efa->v1;
1673         v[1] = efa->v2;
1674         v[2] = efa->v3;
1675
1676         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1677         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
1678         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
1679
1680         // Point verts to the array of new verts for cedge
1681         verts = BLI_ghash_lookup(gh, cedge);
1682         //This is the index size of the verts array
1683         vertsize = numcuts+2;
1684
1685         // Is the original v1 the same as the first vert on the selected edge?
1686         // if not, the edge is running the opposite direction in this face so flip
1687         // the array to the correct direction
1688
1689         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1690            end  = (start+1)%3;
1691            op    = (start+2)%3;
1692
1693         /*
1694         We should have something like this now
1695
1696                           end            start
1697                            3   2   1   0
1698                            |---*---*---|
1699                            \               |
1700                                  \               |
1701                                    \       |
1702                                          \       |
1703                                            \   |
1704                                                  \ |
1705                                                    |op
1706
1707         where start,end,op are indexes of EditFace->v1, etc (stored in v)
1708         and 0,1,2... are the indexes of the new verts stored in verts
1709
1710         We will fill this case like this or this depending on even or odd cuts
1711
1712                            3   2   1   0
1713                            |---*---*---|
1714                            \    \  \   |
1715                                  \      \ \  |
1716                                    \   \ \ |
1717                                          \  \ \|
1718                                            \ \\|
1719                                                  \ |
1720                                                    |op
1721         */
1722
1723         // Make side faces
1724         for(i=0;i<(vertsize-1);i++) {
1725                 hold = addfacelist(em, verts[i],verts[i+1],v[op],NULL,NULL,NULL);
1726                 if(i+1 != vertsize-1) {
1727                         if(seltype == SUBDIV_SELECT_INNER) {
1728                                  hold->e2->f2 |= EDGEINNER;
1729                         }
1730                 }
1731                 facecopy(em, efa,hold);
1732         }
1733 }
1734
1735 static void fill_quad_double_op(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1736 {
1737         EditEdge *cedge[2]={NULL, NULL};
1738         EditVert *v[4], **verts[2];
1739         EditFace *hold;
1740         short start=0, /*end,*/ left, /* right,*/ vertsize,i;
1741
1742         v[0] = efa->v1;
1743         v[1] = efa->v2;
1744         v[2] = efa->v3;
1745         v[3] = efa->v4;
1746
1747         if(efa->e1->f & SELECT)   { cedge[0] = efa->e1;  cedge[1] = efa->e3; start = 0;}
1748         else if(efa->e2->f & SELECT)      { cedge[0] = efa->e2;  cedge[1] = efa->e4; start = 1;}
1749
1750         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1751         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1752         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1753         //This is the index size of the verts array
1754         vertsize = numcuts+2;
1755
1756         // Is the original v1 the same as the first vert on the selected edge?
1757         // if not, the edge is running the opposite direction in this face so flip
1758         // the array to the correct direction
1759
1760         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1761         /* end  = (start+1)%4; */ /* UNUSED */
1762         left   = (start+2)%4;
1763         /* right  = (start+3)%4; */ /* UNUSED */
1764         if(verts[1][0] != v[left]) {flipvertarray(verts[1],numcuts+2);}
1765         /*
1766         We should have something like this now
1767
1768                           end            start
1769                            3   2   1   0
1770                            |---*---*---|
1771                            |               |
1772                            |               |
1773                            |               |
1774                            |---*---*---|
1775                            0   1   2   3
1776                           left     right
1777
1778         We will fill this case like this or this depending on even or odd cuts
1779
1780                            |---*---*---|
1781                            |   |   |   |
1782                            |   |   |   |
1783                            |   |   |   |
1784                            |---*---*---|
1785         */
1786
1787         // Make side faces
1788         for(i=0;i<vertsize-1;i++) {
1789                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-2-i],verts[1][vertsize-1-i],NULL,NULL);
1790                 if(i < vertsize-2) {
1791                         hold->e2->f2 |= EDGEINNER;
1792                         hold->e2->f2 |= DOUBLEOPFILL;
1793                 }
1794                 facecopy(em, efa,hold);
1795         }
1796 }
1797
1798 static void fill_quad_double_adj_path(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1799 {
1800         EditEdge *cedge[2]={NULL, NULL};
1801         EditVert *v[4], **verts[2];
1802         EditFace *hold;
1803         short start=0, start2=0, vertsize,i;
1804         int ctrl= 0; // XXX
1805
1806         v[0] = efa->v1;
1807         v[1] = efa->v2;
1808         v[2] = efa->v3;
1809         v[3] = efa->v4;
1810
1811         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
1812         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
1813         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3;}
1814         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0;}
1815
1816         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1817         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1818         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1819         //This is the index size of the verts array
1820         vertsize = numcuts+2;
1821
1822         // Is the original v1 the same as the first vert on the selected edge?
1823         // if not, the edge is running the opposite direction in this face so flip
1824         // the array to the correct direction
1825
1826         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1827         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1828         /*
1829         We should have something like this now
1830
1831                            end           start
1832                                 3   2   1   0
1833                 start2 0|---*---*---|
1834                                 |                  |
1835                            1*              |
1836                                 |                  |
1837                            2*              |
1838                                 |                  |
1839                  end2  3|-----------|
1840
1841         We will fill this case like this or this depending on even or odd cuts
1842                            |---*---*---|
1843                            | /   /   / |
1844                            *   /   /   |
1845                            | /   /       |
1846                            *   /           |
1847                            | /           |
1848                            |-----------|
1849         */
1850
1851         // Make outside tris
1852         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
1853         /* when ctrl is depressed, only want verts on the cutline selected */
1854         if (ctrl)
1855                 hold->e3->f2 |= EDGEINNER;
1856         facecopy(em, efa,hold);
1857         hold = addfacelist(em, verts[0][0],verts[1][vertsize-1],v[(start2+2)%4],NULL,NULL,NULL);
1858         /* when ctrl is depressed, only want verts on the cutline selected */
1859         if (ctrl)
1860                 hold->e1->f2 |= EDGEINNER;
1861         facecopy(em, efa,hold);
1862         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
1863         //      hold->e1->h |= EM_FGON;
1864         //}
1865         // Make side faces
1866
1867         for(i=0;i<numcuts;i++) {
1868                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
1869                 hold->e2->f2 |= EDGEINNER;
1870                 facecopy(em, efa,hold);
1871         }
1872         //EM_fgon_flags(em);
1873
1874 }
1875
1876 static void fill_quad_double_adj_fan(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1877 {
1878         EditEdge *cedge[2]={NULL, NULL};
1879         EditVert *v[4], *op=NULL, **verts[2];
1880         EditFace *hold;
1881         short start=0, start2=0, vertsize,i;
1882
1883         v[0] = efa->v1;
1884         v[1] = efa->v2;
1885         v[2] = efa->v3;
1886         v[3] = efa->v4;
1887
1888         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1889         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1890         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1891         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1892
1893
1894         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1895         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1896         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1897         //This is the index size of the verts array
1898         vertsize = numcuts+2;
1899
1900         // Is the original v1 the same as the first vert on the selected edge?
1901         // if not, the edge is running the opposite direction in this face so flip
1902         // the array to the correct direction
1903
1904         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1905         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1906         /*
1907         We should have something like this now
1908
1909                            end           start
1910                                 3   2   1   0
1911                 start2 0|---*---*---|
1912                                 |                  |
1913                            1*              |
1914                                 |                  |
1915                            2*              |
1916                                 |                  |
1917                  end2  3|-----------|op
1918
1919         We will fill this case like this or this (warning horrible ascii art follows)
1920                            |---*---*---|
1921                            | \  \   \  |
1922                            *---\  \  \ |
1923                            |   \ \ \  \|
1924                            *---- \ \  \ |
1925                            |    ---  \\\|
1926                            |-----------|
1927         */
1928
1929         for(i=0;i<=numcuts;i++) {
1930                 hold = addfacelist(em, op,verts[1][numcuts-i],verts[1][numcuts-i+1],NULL,NULL,NULL);
1931                 hold->e1->f2 |= EDGEINNER;
1932                 facecopy(em, efa,hold);
1933
1934                 hold = addfacelist(em, op,verts[0][i],verts[0][i+1],NULL,NULL,NULL);
1935                 hold->e3->f2 |= EDGEINNER;
1936                 facecopy(em, efa,hold);
1937         }
1938 }
1939
1940 static void fill_quad_double_adj_inner(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
1941 {
1942         EditEdge *cedge[2]={NULL, NULL};
1943         EditVert *v[4], *op=NULL, **verts[2],**inner;
1944         EditFace *hold;
1945         short start=0, start2=0, vertsize,i;
1946         float co[3];
1947
1948         v[0] = efa->v1;
1949         v[1] = efa->v2;
1950         v[2] = efa->v3;
1951         v[3] = efa->v4;
1952
1953         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1954         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1955         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1956         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1957
1958
1959         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1960         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1961         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1962         //This is the index size of the verts array
1963         vertsize = numcuts+2;
1964
1965         // Is the original v1 the same as the first vert on the selected edge?
1966         // if not, the edge is running the opposite direction in this face so flip
1967         // the array to the correct direction
1968
1969         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1970         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
1971         /*
1972         We should have something like this now
1973
1974                            end           start
1975                                 3   2   1   0
1976                 start2 0|---*---*---|
1977                                 |                  |
1978                            1*              |
1979                                 |                  |
1980                            2*              |
1981                                 |                  |
1982                  end2  3|-----------|op
1983
1984         We will fill this case like this or this (warning horrible ascii art follows)
1985                            |---*-----*---|
1986                            | *     /     |
1987                            *   \ /       |
1988                            |    *        |
1989                            | /    \          |
1990                            *        \    |
1991                            |           \ |
1992                            |-------------|
1993         */
1994
1995         // Add Inner Vert(s)
1996         inner = MEM_mallocN(sizeof(EditVert*)*numcuts,"New inner verts");
1997
1998         for(i=0;i<numcuts;i++) {
1999                 co[0] = (verts[0][numcuts-i]->co[0] + verts[1][i+1]->co[0] ) / 2 ;
2000                 co[1] = (verts[0][numcuts-i]->co[1] + verts[1][i+1]->co[1] ) / 2 ;
2001                 co[2] = (verts[0][numcuts-i]->co[2] + verts[1][i+1]->co[2] ) / 2 ;
2002                 inner[i] = addvertlist(em, co, NULL);
2003                 inner[i]->f2 |= EDGEINNER;
2004
2005                 EM_data_interp_from_verts(em, verts[0][numcuts-i], verts[1][i+1], inner[i], 0.5f);
2006         }
2007
2008         // Add Corner Quad
2009         hold = addfacelist(em, verts[0][numcuts+1],verts[1][1],inner[0],verts[0][numcuts],NULL,NULL);
2010         hold->e2->f2 |= EDGEINNER;
2011         hold->e3->f2 |= EDGEINNER;
2012         facecopy(em, efa,hold);
2013         // Add Bottom Quads
2014         hold = addfacelist(em, verts[0][0],verts[0][1],inner[numcuts-1],op,NULL,NULL);
2015         hold->e2->f2 |= EDGEINNER;
2016         facecopy(em, efa,hold);
2017
2018         hold = addfacelist(em, op,inner[numcuts-1],verts[1][numcuts],verts[1][numcuts+1],NULL,NULL);
2019         hold->e2->f2 |= EDGEINNER;
2020         facecopy(em, efa,hold);
2021
2022         //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2023         //      hold->e1->h |= EM_FGON;
2024         //}
2025         // Add Fill Quads (if # cuts > 1)
2026
2027         for(i=0;i<numcuts-1;i++) {
2028                 hold = addfacelist(em, inner[i],verts[1][i+1],verts[1][i+2],inner[i+1],NULL,NULL);
2029                 hold->e1->f2 |= EDGEINNER;
2030                 hold->e3->f2 |= EDGEINNER;
2031                 facecopy(em, efa,hold);
2032
2033                 hold = addfacelist(em, inner[i],inner[i+1],verts[0][numcuts-1-i],verts[0][numcuts-i],NULL,NULL);
2034                 hold->e2->f2 |= EDGEINNER;
2035                 hold->e4->f2 |= EDGEINNER;
2036                 facecopy(em, efa,hold);
2037
2038                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2039                 //      hold->e1->h |= EM_FGON;
2040                 //}
2041         }
2042
2043         //EM_fgon_flags(em);
2044
2045         MEM_freeN(inner);
2046 }
2047
2048 static void fill_tri_double(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
2049 {
2050         EditEdge *cedge[2]={NULL, NULL};
2051         EditVert *v[3], **verts[2];
2052         EditFace *hold;
2053         short start=0, start2=0, vertsize,i;
2054
2055         v[0] = efa->v1;
2056         v[1] = efa->v2;
2057         v[2] = efa->v3;
2058
2059         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
2060         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
2061         if(efa->e3->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e1; start = 2; start2 = 0;}
2062
2063         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2064         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2065         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2066         //This is the index size of the verts array
2067         vertsize = numcuts+2;
2068
2069         // Is the original v1 the same as the first vert on the selected edge?
2070         // if not, the edge is running the opposite direction in this face so flip
2071         // the array to the correct direction
2072
2073         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2074         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
2075         /*
2076         We should have something like this now
2077
2078                            end           start
2079                                 3   2   1   0
2080                 start2 0|---*---*---|
2081                                 |                /
2082                            1*      /
2083                                 |        /
2084                            2*   /
2085                                 | /
2086                  end2  3|
2087
2088         We will fill this case like this or this depending on even or odd cuts
2089                            |---*---*---|
2090                            | /   /   /
2091                            *   /   /
2092                            | /   /
2093                            *   /
2094                            | /
2095                            |
2096         */
2097
2098         // Make outside tri
2099         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2100         hold->e3->f2 |= EDGEINNER;
2101         facecopy(em, efa,hold);
2102         // Make side faces
2103
2104         for(i=0;i<numcuts;i++) {
2105                 hold = addfacelist(em, verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);
2106                 hold->e2->f2 |= EDGEINNER;
2107                 facecopy(em, efa,hold);
2108         }
2109 }
2110
2111 static void fill_quad_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts)
2112 {
2113         EditEdge *cedge[3]={0};
2114         EditVert *v[4], **verts[3];
2115         EditFace *hold;
2116         short start=0, start2=0, start3=0, vertsize, i, repeats;
2117
2118         v[0] = efa->v1;
2119         v[1] = efa->v2;
2120         v[2] = efa->v3;
2121         v[3] = efa->v4;
2122
2123         if(!(efa->e1->f & SELECT)) {
2124                 cedge[0] = efa->e2;
2125                 cedge[1] = efa->e3;
2126                 cedge[2] = efa->e4;
2127                 start = 1;start2 = 2;start3 = 3;
2128         }
2129         if(!(efa->e2->f & SELECT)) {
2130                 cedge[0] = efa->e3;
2131                 cedge[1] = efa->e4;
2132                 cedge[2] = efa->e1;
2133                 start = 2;start2 = 3;start3 = 0;
2134         }
2135         if(!(efa->e3->f & SELECT)) {
2136                 cedge[0] = efa->e4;
2137                 cedge[1] = efa->e1;
2138                 cedge[2] = efa->e2;
2139                 start = 3;start2 = 0;start3 = 1;
2140         }
2141         if(!(efa->e4->f & SELECT)) {
2142                 cedge[0] = efa->e1;
2143                 cedge[1] = efa->e2;
2144                 cedge[2] = efa->e3;
2145                 start = 0;start2 = 1;start3 = 2;
2146         }
2147         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2148         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2149         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2150         verts[2] = BLI_ghash_lookup(gh, cedge[2]);
2151         //This is the index size of the verts array
2152         vertsize = numcuts+2;
2153
2154         // Is the original v1 the same as the first vert on the selected edge?
2155         // if not, the edge is running the opposite direction in this face so flip
2156         // the array to the correct direction
2157
2158         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2159         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}
2160         if(verts[2][0] != v[start3]) {flipvertarray(verts[2],numcuts+2);}
2161         /*
2162          We should have something like this now
2163
2164          start2
2165          3   2   1   0
2166          start3 0|---*---*---|3
2167          |                 |
2168          1*                *2
2169          |                 |
2170          2*                *1
2171          |                 |
2172          3|-----------|0 start
2173
2174          We will fill this case like this or this depending on even or odd cuts
2175          there are a couple of differences. For odd cuts, there is a tri in the
2176          middle as well as 1 quad at the bottom (not including the extra quads
2177          for odd cuts > 1
2178
2179          For even cuts, there is a quad in the middle and 2 quads on the bottom
2180
2181          they are numbered here for clarity
2182
2183          1 outer tris and bottom quads
2184          2 inner tri or quad
2185          3 repeating quads
2186
2187          |---*---*---*---|
2188          |1/   /  \   \ 1|
2189          |/ 3 / \  3 \|
2190          *  /   2   \   *
2191          | /              \  |
2192          |/                     \ |
2193          *---------------*
2194          |        3             |
2195          |                         |
2196          *---------------*
2197          |                         |
2198          |        1             |
2199          |                         |
2200          |---------------|
2201
2202          |---*---*---*---*---|
2203          | 1/   /        \   \ 1|
2204          | /   /           \   \ |
2205          |/ 3 /          \ 3 \|
2206          *   /             \   *
2207          |  /                    \  |
2208          | /       2       \ |
2209          |/                              \|
2210          *-------------------*
2211          |                                 |
2212          |               3               |
2213          |                                 |
2214          *-------------------*
2215          |                                 |
2216          |               1               |
2217          |                                 |
2218          *-------------------*
2219          |                                 |
2220          |              1                 |
2221          |                                 |
2222          |-------------------|
2223
2224          */
2225
2226         // Make outside tris
2227         hold = addfacelist(em, verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);
2228         hold->e3->f2 |= EDGEINNER;
2229         facecopy(em, efa,hold);
2230         hold = addfacelist(em, verts[1][vertsize-2],verts[1][vertsize-1],verts[2][1],NULL,NULL,NULL);
2231         hold->e3->f2 |= EDGEINNER;
2232         facecopy(em, efa,hold);
2233         // Make bottom quad
2234         hold = addfacelist(em, verts[0][0],verts[0][1],verts[2][vertsize-2],verts[2][vertsize-1],NULL,NULL);
2235         hold->e2->f2 |= EDGEINNER;
2236         facecopy(em, efa,hold);
2237         //If it is even cuts, add the 2nd lower quad
2238         if(numcuts % 2 == 0) {
2239                 hold = addfacelist(em, verts[0][1],verts[0][2],verts[2][vertsize-3],verts[2][vertsize-2],NULL,NULL);
2240                 hold->e2->f2 |= EDGEINNER;
2241                 facecopy(em, efa,hold);
2242                 // Also Make inner quad
2243                 hold = addfacelist(em, verts[1][numcuts/2],verts[1][(numcuts/2)+1],verts[2][numcuts/2],verts[0][(numcuts/2)+1],NULL,NULL);
2244                 hold->e3->f2 |= EDGEINNER;
2245                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2246                 //      hold->e3->h |= EM_FGON;
2247                 //}
2248                 facecopy(em, efa,hold);
2249                 repeats = (numcuts / 2) -1;
2250         } else {
2251                 // Make inner tri
2252                 hold = addfacelist(em, verts[1][(numcuts/2)+1],verts[2][(numcuts/2)+1],verts[0][(numcuts/2)+1],NULL,NULL,NULL);
2253                 hold->e2->f2 |= EDGEINNER;
2254                 //if(scene->toolsettings->editbutflag & B_AUTOFGON) {
2255                 //      hold->e2->h |= EM_FGON;
2256                 //}
2257                 facecopy(em, efa,hold);
2258                 repeats = ((numcuts+1) / 2)-1;
2259         }
2260
2261         // cuts for 1 and 2 do not have the repeating quads
2262         if(numcuts < 3) {repeats = 0;}
2263         for(i=0;i<repeats;i++) {
2264                 //Make side repeating Quads
2265                 hold = addfacelist(em, verts[1][i+1],verts[1][i+2],verts[0][vertsize-i-3],verts[0][vertsize-i-2],NULL,NULL);
2266                 hold->e2->f2 |= EDGEINNER;
2267                 facecopy(em, efa,hold);
2268                 hold = addfacelist(em, verts[1][vertsize-i-3],verts[1][vertsize-i-2],verts[2][i+1],verts[2][i+2],NULL,NULL);
2269                 hold->e4->f2 |= EDGEINNER;
2270                 facecopy(em, efa,hold);
2271         }
2272         // Do repeating bottom quads
2273         for(i=0;i<repeats;i++) {
2274                 if(numcuts % 2 == 1) {
2275                         hold = addfacelist(em, verts[0][1+i],verts[0][2+i],verts[2][vertsize-3-i],verts[2][vertsize-2-i],NULL,NULL);
2276                 } else {
2277                         hold = addfacelist(em, verts[0][2+i],verts[0][3+i],verts[2][vertsize-4-i],verts[2][vertsize-3-i],NULL,NULL);
2278                 }
2279                 hold->e2->f2 |= EDGEINNER;
2280                 facecopy(em, efa,hold);
2281         }
2282         //EM_fgon_flags(em);
2283 }
2284
2285 static void fill_quad_quadruple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2286 {
2287         EditVert **verts[4], ***innerverts;
2288         EditFace *hold;
2289         EditEdge temp;
2290         short vertsize, i, j;
2291
2292         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2293         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2294         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2295         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2296         verts[3] = BLI_ghash_lookup(gh, efa->e4);
2297
2298         //This is the index size of the verts array
2299         vertsize = numcuts+2;
2300
2301         // Is the original v1 the same as the first vert on the selected edge?
2302         // if not, the edge is running the opposite direction in this face so flip
2303         // the array to the correct direction
2304
2305         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2306         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2307         if(verts[2][0] == efa->v3) {flipvertarray(verts[2],numcuts+2);}
2308         if(verts[3][0] == efa->v4) {flipvertarray(verts[3],numcuts+2);}
2309         /*
2310         We should have something like this now
2311                                           1
2312
2313                                 3   2   1   0
2314                            0|---*---*---|0
2315                                 |           |
2316                            1*           *1
2317                          2  |           |   4
2318                            2*           *2
2319                                 |           |
2320                            3|---*---*---|3
2321                                 3   2   1   0
2322
2323                                           3
2324         // we will fill a 2 dim array of editvert*s to make filling easier
2325         //  the innervert order is shown
2326
2327                                 0   0---1---2---3
2328                                         |   |   |   |
2329                                 1   0---1---2---3
2330                                         |   |   |   |
2331                                 2   0---1---2---3
2332                                         |   |   |   |
2333                                 3   0---1---2---3
2334
2335          */
2336         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts outer array");
2337         for(i=0;i<numcuts+2;i++) {
2338                 innerverts[i] = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts inner array");
2339         }
2340
2341         // first row is e1 last row is e3
2342         for(i=0;i<numcuts+2;i++) {
2343                 innerverts[0][i]                  = verts[0][(numcuts+1)-i];
2344                 innerverts[numcuts+1][i]  = verts[2][(numcuts+1)-i];
2345         }
2346
2347         for(i=1;i<=numcuts;i++) {
2348                 /* we create a fake edge for the next loop */
2349                 temp.v2 = innerverts[i][0]                      = verts[1][i];
2350                 temp.v1 = innerverts[i][numcuts+1]  = verts[3][i];
2351
2352                 for(j=1;j<=numcuts;j++) {
2353                         float percent= (float)j/(float)(numcuts+1);
2354
2355                         innerverts[i][(numcuts+1)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, percent);
2356                 }
2357         }
2358         // Fill with faces
2359         for(i=0;i<numcuts+1;i++) {
2360                 for(j=0;j<numcuts+1;j++) {
2361                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],innerverts[i+1][j+1],NULL,NULL);
2362                         hold->e1->f2 = EDGENEW;
2363                         hold->e2->f2 = EDGENEW;
2364                         hold->e3->f2 = EDGENEW;
2365                         hold->e4->f2 = EDGENEW;
2366
2367                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2368                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2369                         if(i != numcuts) { hold->e3->f2 |= EDGEINNER; }
2370                         if(j != numcuts) { hold->e4->f2 |= EDGEINNER; }
2371
2372                         facecopy(em, efa,hold);
2373                 }
2374         }
2375         // Clean up our dynamic multi-dim array
2376         for(i=0;i<numcuts+2;i++) {
2377            MEM_freeN(innerverts[i]);
2378         }
2379         MEM_freeN(innerverts);
2380 }
2381
2382 static void fill_tri_triple(EditMesh *em, EditFace *efa, struct GHash *gh, int numcuts, float smooth, float fractal, int beauty)
2383 {
2384         EditVert **verts[3], ***innerverts;
2385         short vertsize, i, j;
2386         EditFace *hold;
2387         EditEdge temp;
2388
2389         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2390         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2391         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2392         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2393
2394         //This is the index size of the verts array
2395         vertsize = numcuts+2;
2396
2397         // Is the original v1 the same as the first vert on the selected edge?
2398         // if not, the edge is running the opposite direction in this face so flip
2399         // the array to the correct direction
2400
2401         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2402         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}
2403         if(verts[2][0] != efa->v3) {flipvertarray(verts[2],numcuts+2);}
2404         /*
2405         We should have something like this now
2406                                            3
2407
2408                                 3   2   1   0
2409                            0|---*---*---|3
2410                                 |                 /
2411                   1     1*              *2
2412                                 |         /
2413                            2*   *1         2
2414                                 |  /
2415                            3|/
2416                                  0
2417
2418         we will fill a 2 dim array of editvert*s to make filling easier
2419
2420                                                 3
2421
2422                          0  0---1---2---3---4
2423                                 | / | /  |/  | /
2424                          1  0---1----2---3
2425            1            | /  | / | /
2426                          2  0----1---2   2
2427                                 |  / |  /
2428                                 |/   |/
2429                          3  0---1
2430                                 |  /
2431                                 |/
2432                          4  0
2433
2434         */
2435
2436         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"tri-tri subdiv inner verts outer array");
2437         for(i=0;i<numcuts+2;i++) {
2438                   innerverts[i] = MEM_mallocN(sizeof(EditVert*)*((numcuts+2)-i),"tri-tri subdiv inner verts inner array");
2439         }
2440         //top row is e3 backwards
2441         for(i=0;i<numcuts+2;i++) {
2442                   innerverts[0][i]                = verts[2][(numcuts+1)-i];
2443         }
2444
2445         for(i=1;i<=numcuts+1;i++) {
2446                 //fake edge, first vert is from e1, last is from e2
2447                 temp.v1= innerverts[i][0]                         = verts[0][i];
2448                 temp.v2= innerverts[i][(numcuts+1)-i]  = verts[1][(numcuts+1)-i];
2449
2450                 for(j=1;j<(numcuts+1)-i;j++) {
2451                         float percent= (float)j/(float)((numcuts+1)-i);
2452
2453                         innerverts[i][((numcuts+1)-i)-j]= subdivide_edge_addvert(em, &temp, smooth, fractal, beauty, 1-percent);
2454                 }
2455         }
2456
2457         // Now fill the verts with happy little tris :)
2458         for(i=0;i<=numcuts+1;i++) {
2459                 for(j=0;j<(numcuts+1)-i;j++) {
2460                         //We always do the first tri
2461                         hold = addfacelist(em, innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],NULL,NULL,NULL);
2462                         hold->e1->f2 |= EDGENEW;
2463                         hold->e2->f2 |= EDGENEW;
2464                         hold->e3->f2 |= EDGENEW;
2465                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2466                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2467                         if(j+1 != (numcuts+1)-i) {hold->e3->f2 |= EDGEINNER;}
2468
2469                         facecopy(em, efa,hold);
2470                         //if there are more to come, we do the 2nd
2471                         if(j+1 <= numcuts-i) {
2472                                 hold = addfacelist(em, innerverts[i+1][j],innerverts[i+1][j+1],innerverts[i][j+1],NULL,NULL,NULL);
2473                                 facecopy(em, efa,hold);
2474                                 hold->e1->f2 |= EDGENEW;
2475                                 hold->e2->f2 |= EDGENEW;
2476                                 hold->e3->f2 |= EDGENEW;
2477                         }
2478                 }
2479         }
2480
2481         // Clean up our dynamic multi-dim array
2482         for(i=0;i<numcuts+2;i++) {
2483                 MEM_freeN(innerverts[i]);
2484         }
2485         MEM_freeN(innerverts);
2486 }
2487
2488 //Next two fill types are for knife exact only and are provided to allow for knifing through vertices
2489 //This means there is no multicut!
2490 static void fill_quad_doublevert(EditMesh *em, EditFace *efa, int v1, int v2)
2491 {
2492         EditFace *hold;
2493         /*
2494                 Depending on which two vertices have been knifed through (v1 and v2), we
2495                 triangulate like the patterns below.
2496                                 X-------|       |-------X
2497                                 | \     |       |     / |
2498                                 |   \   |       |   /   |
2499                                 |         \     |       | /         |
2500                                 --------X       X--------
2501         */
2502
2503         if(v1 == 1 && v2 == 3){
2504                 hold= addfacelist(em, efa->v1, efa->v2, efa->v3, 0, efa, NULL);
2505                 hold->e1->f2 |= EDGENEW;
2506                 hold->e2->f2 |= EDGENEW;
2507                 hold->e3->f2 |= EDGENEW;
2508                 hold->e3->f2 |= EDGEINNER;
2509                 facecopy(em, efa, hold);
2510
2511                 hold= addfacelist(em, efa->v1, efa->v3, efa->v4, 0, efa, NULL);
2512                 hold->e1->f2 |= EDGENEW;
2513                 hold->e2->f2 |= EDGENEW;
2514                 hold->e3->f2 |= EDGENEW;
2515                 hold->e1->f2 |= EDGEINNER;
2516                 facecopy(em, efa, hold);
2517         }
2518         else{
2519                 hold= addfacelist(em, efa->v1, efa->v2, efa->v4, 0, efa, NULL);
2520                 hold->e1->f2 |= EDGENEW;
2521                 hold->e2->f2 |= EDGENEW;
2522                 hold->e3->f2 |= EDGENEW;
2523                 hold->e2->f2 |= EDGEINNER;
2524                 facecopy(em, efa, hold);
2525
2526                 hold= addfacelist(em, efa->v2, efa->v3, efa->v4, 0, efa, NULL);
2527                 hold->e1->f2 |= EDGENEW;
2528                 hold->e2->f2 |= EDGENEW;
2529                 hold->e3->f2 |= EDGENEW;
2530                 hold->e3->f2 |= EDGEINNER;
2531                 facecopy(em, efa, hold);
2532         }
2533 }
2534
2535 static void fill_quad_singlevert(EditMesh *em, EditFace *efa, struct GHash *gh)
2536 {
2537         EditEdge *cedge=NULL;
2538         EditVert *v[4], **verts;
2539         EditFace *hold;
2540         short start=0, end, left, right, vertsize;
2541
2542         v[0] = efa->v1;
2543         v[1] = efa->v2;
2544         v[2] = efa->v3;
2545         v[3] = efa->v4;
2546
2547         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
2548         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}
2549         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}
2550         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}
2551
2552         // Point verts to the array of new verts for cedge
2553         verts = BLI_ghash_lookup(gh, cedge);
2554         //This is the index size of the verts array
2555         vertsize = 3;
2556
2557         // Is the original v1 the same as the first vert on the selected edge?
2558         // if not, the edge is running the opposite direction in this face so flip
2559         // the array to the correct direction
2560
2561         if(verts[0] != v[start]) {flipvertarray(verts,3);}
2562         end     = (start+1)%4;
2563         left   = (start+2)%4;
2564         right  = (start+3)%4;
2565
2566 /*
2567         We should have something like this now
2568
2569                           end            start
2570                            2     1     0
2571                            |-----*-----|
2572                            |               |
2573                            |               |
2574                            |               |
2575                            -------------
2576                           left     right
2577
2578         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
2579         and 0,1,2 are the indexes of the new verts stored in verts. We fill like
2580         this, depending on whether its vertex 'left' or vertex 'right' thats
2581         been knifed through...
2582
2583                                 |---*---|       |---*---|
2584                                 |  /    |       |    \  |
2585                                 | /             |       |         \ |
2586                                 |/              |       |          \|
2587                                 X--------       --------X
2588 */
2589
2590         if(v[left]->f1){
2591                 //triangle is composed of cutvert, end and left
2592                 hold = addfacelist(em, verts[1],v[end],v[left],NULL, NULL,NULL);
2593                 hold->e1->f2 |= EDGENEW;
2594                 hold->e2->f2 |= EDGENEW;
2595                 hold->e3->f2 |= EDGENEW;
2596                 hold->e3->f2 |= EDGEINNER;
2597                 facecopy(em, efa, hold);
2598
2599                 //quad is composed of cutvert, left, right and start
2600                 hold = addfacelist(em, verts[1],v[left],v[right],v[start], NULL, NULL);
2601                 hold->e1->f2 |= EDGENEW;
2602                 hold->e2->f2 |= EDGENEW;
2603                 hold->e3->f2 |= EDGENEW;
2604                 hold->e4->f2 |= EDGENEW;
2605                 hold->e1->f2 |= EDGEINNER;
2606                 facecopy(em, efa, hold);
2607         }
2608         else if(v[right]->f1){
2609                 //triangle is composed of cutvert, right and start
2610                 hold = addfacelist(em, verts[1],v[right],v[start], NULL, NULL, NULL);
2611                 hold->e1->f2 |= EDGENEW;
2612                 hold->e2->f2 |= EDGENEW;
2613                 hold->e3->f2 |= EDGENEW;
2614                 hold->e1->f2 |= EDGEINNER;
2615                 facecopy(em, efa, hold);
2616                 //quad is composed of cutvert, end, left, right
2617                 hold = addfacelist(em, verts[1],v[end], v[left], v[right], NULL, NULL);
2618                 hold->e1->f2 |= EDGENEW;
2619                 hold->e2->f2 |= EDGENEW;
2620                 hold->e3->f2 |= EDGENEW;
2621                 hold->e4->f2 |= EDGENEW;
2622                 hold->e4->f2 |= EDGEINNER;
2623                 facecopy(em, efa, hold);
2624         }
2625
2626 }
2627
2628 // This function takes an example edge, the current point to create and
2629 // the total # of points to create, then creates the point and return the
2630 // editvert pointer to it.
2631 static EditVert *subdivideedgenum(EditMesh *em, EditEdge *edge, int curpoint, int totpoint, float smooth, float fractal, int beauty)
2632 {
2633         EditVert *ev;
2634         float percent;
2635
2636         if (beauty & (B_PERCENTSUBD) && totpoint == 1)
2637                 //percent=(float)(edge->tmp.l)/32768.0f;
2638                 percent= edge->tmp.fp;
2639         else
2640                 percent= (float)curpoint/(float)(totpoint+1);
2641
2642         ev= subdivide_edge_addvert(em, edge, smooth, fractal, beauty, percent);
2643         ev->f = edge->v1->f;
2644
2645         return ev;
2646 }
2647
2648 void esubdivideflag(Object *obedit, EditMesh *em, int flag, float smooth, float fractal, int beauty, int numcuts, int corner_pattern, int seltype)
2649 {
2650         EditFace *ef;
2651         EditEdge *eed, *cedge, *sort[4];
2652         EditVert *eve, **templist;
2653         struct GHash *gh;
2654         float length[4], v1mat[3], v2mat[3], v3mat[3], v4mat[3];
2655         int i, j, edgecount, touchcount, facetype,hold;
2656         ModifierData *md= obedit->modifiers.first;
2657         int ctrl= 0; // XXX
2658
2659         //Set faces f1 to 0 cause we need it later
2660         for(ef=em->faces.first;ef;ef = ef->next) ef->f1 = 0;
2661         for(eve=em->verts.first; eve; eve=eve->next) {
2662                 if(!(beauty & B_KNIFE)) /* knife sets this flag for vertex cuts */
2663                         eve->f1 = 0;
2664                 eve->f2 = 0;
2665         }
2666
2667         for (; md; md=md->next) {
2668                 if (md->type==eModifierType_Mirror) {
2669                         MirrorModifierData *mmd = (MirrorModifierData*) md;
2670
2671                         if(mmd->flag & MOD_MIR_CLIPPING) {
2672                                 for (eve= em->verts.first; eve; eve= eve->next) {
2673                                         eve->f2= 0;
2674                                         switch(mmd->axis){
2675                                                 case 0:
2676                                                         if (fabsf(eve->co[0]) < mmd->tolerance)
2677                                                                 eve->f2 |= 1;
2678                                                         break;
2679                                                 case 1:
2680                                                         if (fabsf(eve->co[1]) < mmd->tolerance)
2681                                                                 eve->f2 |= 2;
2682                                                         break;
2683                                                 case 2:
2684                                                         if (fabsf(eve->co[2]) < mmd->tolerance)
2685                                                                 eve->f2 |= 4;
2686                                                         break;
2687                                         }
2688                                 }
2689                         }
2690                 }
2691         }
2692
2693         //Flush vertex flags upward to the edges
2694         for(eed = em->edges.first;eed;eed = eed->next) {
2695                 //if(eed->f & flag && eed->v1->f == eed->v2->f) {
2696                 //      eed->f |= eed->v1->f;
2697                 // }
2698                 eed->f2 = 0;
2699                 if(eed->f & flag) {
2700                         eed->f2 |= EDGEOLD;
2701                 }
2702         }
2703
2704         // We store an array of verts for each edge that is subdivided,
2705         // we put this array as a value in a ghash which is keyed by the EditEdge*
2706
2707         // Now for beauty subdivide deselect edges based on length
2708         if(beauty & B_BEAUTY) {
2709                 for(ef = em->faces.first;ef;ef = ef->next) {
2710                         if(!ef->v4) {
2711                                 continue;
2712                         }
2713                         if(ef->f & SELECT) {
2714                                 VECCOPY(v1mat, ef->v1->co);
2715                                 VECCOPY(v2mat, ef->v2->co);
2716                                 VECCOPY(v3mat, ef->v3->co);
2717                                 VECCOPY(v4mat, ef->v4->co);
2718                                 mul_mat3_m4_v3(obedit->obmat, v1mat);
2719                                 mul_mat3_m4_v3(obedit->obmat, v2mat);
2720                                 mul_mat3_m4_v3(obedit->obmat, v3mat);
2721                                 mul_mat3_m4_v3(obedit->obmat, v4mat);
2722
2723                                 length[0] = len_v3v3(v1mat, v2mat);
2724                                 length[1] = len_v3v3(v2mat, v3mat);
2725                                 length[2] = len_v3v3(v3mat, v4mat);
2726                                 length[3] = len_v3v3(v4mat, v1mat);
2727                                 sort[0] = ef->e1;
2728                                 sort[1] = ef->e2;
2729                                 sort[2] = ef->e3;
2730                                 sort[3] = ef->e4;
2731
2732
2733                                 // Beauty Short Edges
2734                                 if(beauty & B_BEAUTY_SHORT) {
2735                                         for(j=0;j<2;j++) {
2736                                                 hold = -1;
2737                                                 for(i=0;i<4;i++) {
2738                                                         if(length[i] < 0) {
2739                                                                 continue;
2740                                                         } else if(hold == -1) {
2741                                                                 hold = i;
2742                                                         } else {
2743                                                                 if(length[hold] < length[i]) {
2744                                                                         hold = i;
2745                                                                 }
2746                                                         }
2747                                                 }
2748                                                 if (hold > -1) {
2749                                                         sort[hold]->f &= ~SELECT;
2750                                                         sort[hold]->f2 |= EDGENEW;
2751                                                         length[hold] = -1;
2752                                                 }
2753                                         }
2754                                 }
2755
2756                                 // Beauty Long Edges
2757                                 else {
2758                                          for(j=0;j<2;j++) {
2759                                                 hold = -1;
2760                                                 for(i=0;i<4;i++) {
2761                                                         if(length[i] < 0) {
2762                                                                 continue;
2763                                                         } else if(hold == -1) {
2764                                                                 hold = i;
2765                                                         } else {
2766                                                                 if(length[hold] > length[i]) {
2767                                                                         hold = i;
2768                                                                 }
2769                                                         }
2770                                                 }
2771                                                 if (hold > -1) {
2772                                                         sort[hold]->f &= ~SELECT;
2773                                                         sort[hold]->f2 |= EDGENEW;
2774                                                         length[hold] = -1;
2775                                                 }
2776                                         }
2777                                 }
2778                         }
2779                 }
2780         }
2781
2782         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "subdivideedgenum gh");
2783
2784         // If we are knifing, We only need the selected edges that were cut, so deselect if it was not cut
2785         if(beauty & B_KNIFE) {
2786                 for(eed= em->edges.first;eed;eed=eed->next) {
2787                         if( eed->tmp.fp == 0 ) {
2788                                 EM_select_edge(eed,0);
2789                         }
2790                 }
2791         }
2792         // So for each edge, if it is selected, we allocate an array of size cuts+2
2793         // so we can have a place for the v1, the new verts and v2
2794         for(eed=em->edges.first;eed;eed = eed->next) {
2795                 if(eed->f & flag) {
2796                         templist = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"vertlist");
2797                         templist[0] = eed->v1;
2798                         for(i=0;i<numcuts;i++) {
2799                                 // This function creates the new vert and returns it back
2800                                 // to the array
2801                                 templist[i+1] = subdivideedgenum(em, eed, i+1, numcuts, smooth, fractal, beauty);
2802                                 //while we are here, we can copy edge info from the original edge
2803                                 cedge = addedgelist(em, templist[i],templist[i+1],eed);
2804                                 // Also set the edge f2 to EDGENEW so that we can use this info later
2805                                 cedge->f2 = EDGENEW;
2806                         }
2807                         templist[i+1] = eed->v2;
2808                         //Do the last edge too
2809                         cedge = addedgelist(em, templist[i],templist[i+1],eed);
2810                         cedge->f2 = EDGENEW;
2811                         // Now that the edge is subdivided, we can put its verts in the ghash
2812                         BLI_ghash_insert(gh, eed, templist);
2813                 }
2814         }
2815
2816 //      DAG_id_tag_update(obedit->data, 0);
2817         // Now for each face in the mesh we need to figure out How many edges were cut
2818         // and which filling method to use for that face
2819         for(ef = em->faces.first;ef;ef = ef->next) {
2820                 edgecount = 0;
2821                 facetype = 3;
2822                 if(ef->e1->f & flag) {edgecount++;}
2823                 if(ef->e2->f & flag) {edgecount++;}
2824                 if(ef->e3->f & flag) {edgecount++;}
2825                 if(ef->v4) {
2826                         facetype = 4;
2827                         if(ef->e4->f & flag) {edgecount++;}
2828                 }
2829                 if(facetype == 4) {
2830                         switch(edgecount) {
2831                                 case 0:
2832                                         if(beauty & B_KNIFE && numcuts == 1){
2833                                                 /*Test for when knifing through two opposite verts but no edges*/
2834                                                 touchcount = 0;
2835                                                 if(ef->v1->f1) touchcount++;
2836                                                 if(ef->v2->f1) touchcount++;
2837                                                 if(ef->v3->f1) touchcount++;
2838                                                 if(ef->v4->f1) touchcount++;
2839                                                 if(touchcount == 2){
2840                                                         if(ef->v1->f1 && ef->v3->f1){
2841                                                                 ef->f1 = SELECT;
2842                                                                 fill_quad_doublevert(em, ef, 1, 3);
2843                                                         }
2844                                                         else if(ef->v2->f1 && ef->v4->f1){
2845                                                                 ef->f1 = SELECT;
2846                                                                 fill_quad_doublevert(em, ef, 2, 4);
2847                                                         }
2848                                                 }
2849                                         }
2850                                         break;
2851
2852                                 case 1:
2853                                         if(beauty & B_KNIFE && numcuts == 1){
2854                                                 /*Test for when knifing through an edge and one vert*/
2855                                                 touchcount = 0;
2856                                                 if(ef->v1->f1) touchcount++;
2857                                                 if(ef->v2->f1) touchcount++;
2858                                                 if(ef->v3->f1) touchcount++;
2859                                                 if(ef->v4->f1) touchcount++;
2860
2861                                                 if(touchcount == 1){
2862                                                         if( (ef->e1->f & flag && ( !ef->e1->v1->f1 && !ef->e1->v2->f1 )) ||
2863                                                                 (ef->e2->f & flag && ( !ef->e2->v1->f1 && !ef->e2->v2->f1 )) ||
2864                                                                 (ef->e3->f & flag && ( !ef->e3->v1->f1 && !ef->e3->v2->f1 )) ||
2865                                                                 (ef->e4->f & flag && ( !ef->e4->v1->f1 && !ef->e4->v2->f1 )) ){
2866
2867                                                                 ef->f1 = SELECT;
2868                                                                 fill_quad_singlevert(em, ef, gh);
2869                                                         }
2870                                                         else{
2871                                                                 ef->f1 = SELECT;
2872                                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2873                                                         }
2874                                                 }
2875                                                 else{
2876                                                         ef->f1 = SELECT;
2877                                                         fill_quad_single(em, ef, gh, numcuts, seltype);
2878                                                 }
2879                                         }
2880                                         else{
2881                                                 ef->f1 = SELECT;
2882                                                 fill_quad_single(em, ef, gh, numcuts, seltype);
2883                                         }
2884                                         break;
2885                                 case 2: ef->f1 = SELECT;
2886                                         // if there are 2, we check if edge 1 and 3 are either both on or off that way
2887                                         // we can tell if the selected pair is Adjacent or Opposite of each other
2888                                         if((ef->e1->f & flag && ef->e3->f & flag) ||
2889                                            (ef->e2->f & flag && ef->e4->f & flag)) {
2890                                                 fill_quad_double_op(em, ef, gh, numcuts);
2891                                         }else{
2892                                                 switch(corner_pattern) {
2893                                                         case 0: fill_quad_double_adj_path(em, ef, gh, numcuts); break;
2894                                                         case 1: fill_quad_double_adj_inner(em, ef, gh, numcuts); break;
2895                                                         case 2: fill_quad_double_adj_fan(em, ef, gh, numcuts); break;
2896                                                 }
2897
2898                                         }
2899                                                 break;
2900                                 case 3: ef->f1 = SELECT;
2901                                         fill_quad_triple(em, ef, gh, numcuts);
2902                                         break;
2903                                 case 4: ef->f1 = SELECT;
2904                                         fill_quad_quadruple(em, ef, gh, numcuts, smooth, fractal, beauty);
2905                                         break;
2906                         }
2907                 } else {
2908                         switch(edgecount) {
2909                                 case 0: break;
2910                                 case 1: ef->f1 = SELECT;
2911                                         fill_tri_single(em, ef, gh, numcuts, seltype);
2912                                         break;
2913                                 case 2: ef->f1 = SELECT;
2914                                         fill_tri_double(em, ef, gh, numcuts);
2915                                         break;
2916                                 case 3: ef->f1 = SELECT;
2917                                         fill_tri_triple(em, ef, gh, numcuts, smooth, fractal, beauty);
2918                                         break;
2919                         }
2920                 }
2921         }
2922
2923         // Delete Old Edges and Faces
2924         for(eed = em->edges.first;eed;eed = eed->next) {
2925                 if(BLI_ghash_haskey(gh,eed)) {
2926                         eed->f1 = SELECT;
2927                 } else {
2928                         eed->f1 = 0;
2929                 }
2930         }
2931         free_tagged_edges_faces(em, em->edges.first, em->faces.first);
2932
2933         if(seltype == SUBDIV_SELECT_ORIG  && !ctrl) {
2934                 /* bugfix: vertex could get flagged as "not-selected"
2935                 // solution: clear flags before, not at the same time as setting SELECT flag -dg
2936                 */
2937                 for(eed = em->edges.first;eed;eed = eed->next) {
2938                         if(!(eed->f2 & EDGENEW || eed->f2 & EDGEOLD)) {
2939                                 eed->f &= !flag;
2940                                 EM_select_edge(eed,0);
2941                         }
2942                 }
2943                 for(eed = em->edges.first;eed;eed = eed->next) {
2944                         if(eed->f2 & EDGENEW || eed->f2 & EDGEOLD) {
2945                                 eed->f |= flag;
2946                                 EM_select_edge(eed,1);
2947                         }
2948                 }
2949         } else if ((seltype == SUBDIV_SELECT_INNER || seltype == SUBDIV_SELECT_INNER_SEL)|| ctrl) {
2950                 for(eed = em->edges.first;eed;eed = eed->next) {
2951                         if(eed->f2 & EDGEINNER) {
2952                                 eed->f |= flag;
2953                                 EM_select_edge(eed,1);
2954                                 if(eed->v1->f & EDGEINNER) eed->v1->f |= SELECT;
2955                                 if(eed->v2->f & EDGEINNER) eed->v2->f |= SELECT;
2956                         }else{
2957                                 eed->f &= !flag;
2958                                 EM_select_edge(eed,0);
2959                         }
2960                 }
2961         } else if(seltype == SUBDIV_SELECT_LOOPCUT){
2962                 for(eed = em->edges.first;eed;eed = eed->next) {
2963                         if(eed->f2 & DOUBLEOPFILL){
2964                                 eed->f |= flag;
2965                                 EM_select_edge(eed,1);
2966                         }else{
2967                                 eed->f &= !flag;
2968                                 EM_select_edge(eed,0);
2969                         }
2970                 }
2971         }
2972          if(em->selectmode & SCE_SELECT_VERTEX) {
2973                  for(eed = em->edges.first;eed;eed = eed->next) {
2974                         if(eed->f & SELECT) {
2975                                 eed->v1->f |= SELECT;
2976                                 eed->v2->f |= SELECT;
2977                         }
2978                 }
2979         }
2980
2981         //fix hide flags for edges. First pass, hide edges of hidden faces
2982         for(ef=em->faces.first; ef; ef=ef->next){
2983                 if(ef->h){
2984                         ef->e1->h |= 1;
2985                         ef->e2->h |= 1;
2986                         ef->e3->h |= 1;
2987                         if(ef->e4) ef->e4->h |= 1;
2988                 }
2989         }
2990         //second pass: unhide edges of visible faces adjacent to hidden faces
2991         for(ef=em->faces.first; ef; ef=ef->next){
2992                 if(ef->h == 0){
2993                         ef->e1->h &= ~1;
2994                         ef->e2->h &= ~1;
2995                         ef->e3->h &= ~1;
2996                         if(ef->e4) ef->e4->h &= ~1;
2997                 }
2998         }
2999
3000         //third pass: unhide edges that have both verts visible
3001         //(these were missed if all faces were hidden, bug #21976)
3002         for(eed=em->edges.first; eed; eed=eed->next){
3003                 if(eed->v1->h == 0 && eed->v2->h == 0)
3004                         eed->h &= ~1;
3005         }
3006
3007         // Free the ghash and call MEM_freeN on all the value entries to return
3008         // that memory
3009         BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);
3010
3011         EM_selectmode_flush(em);
3012         for(ef=em->faces.first;ef;ef = ef->next) {
3013                 if(ef->e4) {
3014                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) &&
3015                          (ef->e3->f & SELECT && ef->e4->f & SELECT) ) {
3016                                 ef->f |= SELECT;
3017                         }
3018                 } else {
3019                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) && ef->e3->f & SELECT) {
3020                                 ef->f |= SELECT;
3021                         }
3022                 }
3023         }
3024
3025         recalc_editnormals(em);
3026 }
3027
3028 static int count_selected_edges(EditEdge *ed)
3029 {
3030         int totedge = 0;