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