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