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