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