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