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