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