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