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