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