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