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