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