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