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