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