made a nice new softbody II panel on UI to keep things usable (logic wise)
[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, int 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= (float)(degr*M_PI/360.0);
814         phi/= steps;
815         if(G.scene->toolsettings->editbutflag & B_CLOCKWISE) phi= -phi;
816
817         if(dvec) {
818                 n[0]=n[1]= 0.0;
819                 n[2]= 1.0;
820         } else {
821                 n[0]= G.vd->viewinv[2][0];
822                 n[1]= G.vd->viewinv[2][1];
823                 n[2]= G.vd->viewinv[2][2];
824                 Normalise(n);
825         }
826
827         q[0]= (float)cos(phi);
828         si= (float)sin(phi);
829         q[1]= n[0]*si;
830         q[2]= n[1]*si;
831         q[3]= n[2]*si;
832         QuatToMat3(q, cmat);
833
834         Mat3MulMat3(tmat,cmat,bmat);
835         Mat3MulMat3(bmat,imat,tmat);
836
837         if(mode==0) if(G.scene->toolsettings->editbutflag & B_KEEPORIG) adduplicateflag(1);
838         ok= 1;
839
840         for(a=0;a<steps;a++) {
841                 if(mode==0) ok= extrudeflag(SELECT, nor);
842                 else adduplicateflag(SELECT);
843                 if(ok==0) {
844                         error("No valid vertices are selected");
845                         break;
846                 }
847                 rotateflag(SELECT, cent, bmat);
848                 if(dvec) {
849                         Mat3MulVecfl(bmat,dvec);
850                         translateflag(SELECT, dvec);
851                 }
852         }
853
854         if(ok==0) {
855                 /* no vertices or only loose ones selected, remove duplicates */
856                 eve= em->verts.first;
857                 while(eve) {
858                         nextve= eve->next;
859                         if(eve->f & SELECT) {
860                                 BLI_remlink(&em->verts,eve);
861                                 free_editvert(eve);
862                         }
863                         eve= nextve;
864                 }
865         }
866         recalc_editnormals();
867
868         EM_fgon_flags();
869         countall();
870         allqueue(REDRAWVIEW3D, 0);
871         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
872
873         
874         if(dvec==NULL) BIF_undo_push("Spin");
875 }
876
877 void screw_mesh(int steps, int turns)
878 {
879         EditMesh *em = G.editMesh;
880         EditVert *eve,*v1=0,*v2=0;
881         EditEdge *eed;
882         float dvec[3], nor[3];
883
884         TEST_EDITMESH
885
886         /* first condition: we need frontview! */
887         if(G.vd->view!=1) {
888                 error("Must be in Front View");
889                 return;
890         }
891         
892         /* clear flags */
893         eve= em->verts.first;
894         while(eve) {
895                 eve->f1= 0;
896                 eve= eve->next;
897         }
898         /* edges set flags in verts */
899         eed= em->edges.first;
900         while(eed) {
901                 if(eed->v1->f & SELECT) {
902                         if(eed->v2->f & SELECT) {
903                                 /* watch: f1 is a byte */
904                                 if(eed->v1->f1<2) eed->v1->f1++;
905                                 if(eed->v2->f1<2) eed->v2->f1++;
906                         }
907                 }
908                 eed= eed->next;
909         }
910         /* find two vertices with eve->f1==1, more or less is wrong */
911         eve= em->verts.first;
912         while(eve) {
913                 if(eve->f1==1) {
914                         if(v1==0) v1= eve;
915                         else if(v2==0) v2= eve;
916                         else {
917                                 v1=0;
918                                 break;
919                         }
920                 }
921                 eve= eve->next;
922         }
923         if(v1==0 || v2==0) {
924                 error("You have to select a string of connected vertices too");
925                 return;
926         }
927
928         /* calculate dvec */
929         dvec[0]= ( (v1->co[0]- v2->co[0]) )/(steps);
930         dvec[1]= ( (v1->co[1]- v2->co[1]) )/(steps);
931         dvec[2]= ( (v1->co[2]- v2->co[2]) )/(steps);
932
933         VECCOPY(nor, G.obedit->obmat[2]);
934
935         if(nor[0]*dvec[0]+nor[1]*dvec[1]+nor[2]*dvec[2]>0.000) {
936                 dvec[0]= -dvec[0];
937                 dvec[1]= -dvec[1];
938                 dvec[2]= -dvec[2];
939         }
940
941         spin_mesh(turns*steps, turns*360, 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 static int VecEqual(float *a, float *b)
1390 {
1391         if( a[0] == b[0] && 
1392            (a[1] == b[1] && 
1393                 a[2] == b[2])) {
1394                 return 1;
1395         }
1396         else {
1397                 return 0;
1398         }
1399 }
1400
1401 static void set_uv_vcol(EditFace *efa, float *co, float *uv, char *col)
1402
1403         EditVert *v1,*v2,*v3,*v4;
1404         float xn, yn, zn;
1405         float t00, t01, t10, t11;
1406         float detsh, u, v, l;
1407         int fac;
1408         short i, j;
1409         char *cp0, *cp1, *cp2;
1410         char *hold;
1411         
1412         //First Check for exact match between co and efa verts
1413         if(VecEqual(co,efa->v1->co)) {
1414                 uv[0] = efa->tf.uv[0][0];
1415                 uv[1] = efa->tf.uv[0][1];
1416                 
1417                 hold = (char*)&efa->tf.col[0];
1418                 col[0]= hold[0];
1419                 col[1]= hold[1];
1420                 col[2]= hold[2];
1421                 col[3]= hold[3];
1422                 return;   
1423         } else if(VecEqual(co,efa->v2->co)) {
1424                 uv[0] = efa->tf.uv[1][0];
1425                 uv[1] = efa->tf.uv[1][1];
1426                 
1427                 hold = (char*)&efa->tf.col[1];
1428                 col[0]= hold[0];
1429                 col[1]= hold[1];
1430                 col[2]= hold[2];
1431                 col[3]= hold[3]; 
1432                 return;    
1433         } else if(VecEqual(co,efa->v3->co)) {
1434                 uv[0] = efa->tf.uv[2][0];
1435                 uv[1] = efa->tf.uv[2][1];
1436                 
1437                 hold = (char*)&efa->tf.col[2];
1438                 col[0]= hold[0];
1439                 col[1]= hold[1];
1440                 col[2]= hold[2];
1441                 col[3]= hold[3];        
1442                 return;   
1443         } else if(efa->v4 && VecEqual(co,efa->v4->co)) {
1444                 uv[0] = efa->tf.uv[3][0];
1445                 uv[1] = efa->tf.uv[3][1];
1446                 
1447                 hold = (char*)&efa->tf.col[3];
1448                 col[0]= hold[0];
1449                 col[1]= hold[1];
1450                 col[2]= hold[2];
1451                 col[3]= hold[3];   
1452                 return;  
1453         }       
1454         
1455         /* define best projection of face XY, XZ or YZ */
1456         xn= fabs(efa->n[0]);
1457         yn= fabs(efa->n[1]);
1458         zn= fabs(efa->n[2]);
1459         if(zn>=xn && zn>=yn) {i= 0; j= 1;}
1460         else if(yn>=xn && yn>=zn) {i= 0; j= 2;}
1461         else {i= 1; j= 2;} 
1462         
1463         /* calculate u and v */
1464         v1= efa->v1;
1465         v2= efa->v2;
1466         v3= efa->v3;
1467                 
1468         t00= v3->co[i]-v1->co[i]; t01= v3->co[j]-v1->co[j];
1469         t10= v3->co[i]-v2->co[i]; t11= v3->co[j]-v2->co[j];
1470                 
1471         detsh= 1.0/(t00*t11-t10*t01);   /* potential danger */
1472         t00*= detsh; t01*=detsh;
1473         t10*=detsh; t11*=detsh;
1474                 
1475         u= (co[i]-v3->co[i])*t11-(co[j]-v3->co[j])*t10;
1476         v= (co[j]-v3->co[j])*t00-(co[i]-v3->co[i])*t01; 
1477         
1478         /* btw; u and v range from -1 to 0 */
1479                 
1480         /* interpolate */
1481         l= 1.0+u+v;
1482                 /* outside triangle? */
1483                 /* printf("l: %f u %f v %f\n",l,u,v); */
1484         
1485         if(efa->v4 && (v>0.001f)) {     /* only check for positive v is OK, that's the diagonal */
1486                 /* printf("outside\n"); */
1487                 /* do it all over, but now with vertex 2 replaced with 4 */
1488                 
1489                 /* calculate u and v */
1490                 v1= efa->v1;
1491                 v4= efa->v4;
1492                 v3= efa->v3;
1493                                 
1494                 t00= v3->co[i]-v1->co[i]; t01= v3->co[j]-v1->co[j];
1495                 t10= v3->co[i]-v4->co[i]; t11= v3->co[j]-v4->co[j];
1496                                 
1497                 detsh= 1.0/(t00*t11-t10*t01);   /* potential danger */
1498                 t00*= detsh; t01*=detsh;
1499                 t10*=detsh; t11*=detsh;
1500                                 
1501                 u= (co[i]-v3->co[i])*t11-(co[j]-v3->co[j])*t10;
1502                 v= (co[j]-v3->co[j])*t00-(co[i]-v3->co[i])*t01; 
1503                 
1504                 /* btw; u and v range from -1 to 0 */
1505                                 
1506                 /* interpolate */
1507                 l= 1.0+u+v;
1508                 uv[0] = (l*efa->tf.uv[2][0] - u*efa->tf.uv[0][0] - v*efa->tf.uv[3][0]);
1509                 uv[1] = (l*efa->tf.uv[2][1] - u*efa->tf.uv[0][1] - v*efa->tf.uv[3][1]);
1510
1511                 cp0= (char*)&(efa->tf.col[0]);
1512                 cp1= (char*)&(efa->tf.col[3]);
1513                 cp2= (char*)&(efa->tf.col[2]);
1514                 
1515                 for(i=0; i<4; i++) {
1516                         fac= (int)(l*cp2[i] - u*cp0[i] - v*cp1[i]);
1517                         col[i]= CLAMPIS(fac, 0, 255);
1518                 }                         
1519         } else {         
1520         //      printf("inside\n");      
1521                 //new = l*vertex3_val - u*vertex1_val - v*vertex2_val;
1522                 uv[0] = (l*efa->tf.uv[2][0] - u*efa->tf.uv[0][0] - v*efa->tf.uv[1][0]);
1523                 uv[1] = (l*efa->tf.uv[2][1] - u*efa->tf.uv[0][1] - v*efa->tf.uv[1][1]);
1524
1525                 cp0= (char*)&(efa->tf.col[0]);
1526                 cp1= (char*)&(efa->tf.col[1]);
1527                 cp2= (char*)&(efa->tf.col[2]);
1528                 
1529                 for(i=0; i<4; i++) {
1530                         fac= (int)(l*cp2[i] - u*cp0[i] - v*cp1[i]);
1531                         col[i]= CLAMPIS(fac, 0, 255);
1532                 }                                          
1533         }
1534
1535
1536 static void facecopy(EditFace *source,EditFace *target)
1537 {
1538
1539         set_uv_vcol(source,target->v1->co,target->tf.uv[0],(char*)&target->tf.col[0]);
1540         set_uv_vcol(source,target->v2->co,target->tf.uv[1],(char*)&target->tf.col[1]);
1541         set_uv_vcol(source,target->v3->co,target->tf.uv[2],(char*)&target->tf.col[2]);
1542         if(target->v4)
1543                 set_uv_vcol(source,target->v4->co,target->tf.uv[3],(char*)&target->tf.col[3]);
1544
1545         target->mat_nr   = source->mat_nr;
1546         target->tf.flag = source->tf.flag&~TF_ACTIVE;
1547         target->tf.transp  = source->tf.transp;
1548         target->tf.mode = source->tf.mode;
1549         target->tf.tile = source->tf.tile;
1550         target->tf.unwrap  = source->tf.unwrap;
1551         target->tf.tpage   = source->tf.tpage;
1552         target->flag       = source->flag;      
1553 }
1554
1555 static void fill_quad_single(EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1556 {
1557         EditEdge *cedge=NULL;
1558         EditVert *v[4], **verts;
1559         EditFace *hold;
1560         short start=0, end, left, right, vertsize,i;   
1561                                                         
1562         v[0] = efa->v1;
1563         v[1] = efa->v2;
1564         v[2] = efa->v3;
1565         v[3] = efa->v4;  
1566
1567         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1568         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}        
1569         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}        
1570         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}              
1571
1572         // Point verts to the array of new verts for cedge
1573         verts = BLI_ghash_lookup(gh, cedge);
1574         //This is the index size of the verts array
1575         vertsize = numcuts+2;
1576
1577         // Is the original v1 the same as the first vert on the selected edge?
1578         // if not, the edge is running the opposite direction in this face so flip
1579         // the array to the correct direction
1580
1581         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1582         end     = (start+1)%4;
1583         left   = (start+2)%4;
1584         right  = (start+3)%4; 
1585                    
1586         /*
1587         We should have something like this now
1588
1589                           end            start                           
1590                            3   2   1   0   
1591                            |---*---*---|
1592                            |               |
1593                            |               |       
1594                            |               |
1595                            -------------           
1596                           left     right
1597
1598         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
1599         and 0,1,2... are the indexes of the new verts stored in verts
1600
1601         We will fill this case like this or this depending on even or odd cuts
1602          
1603                            |---*---*---|                  |---*---|
1604                            |  /  \  |             |  / \  |
1605                            | /     \ |            | /   \ |      
1606                            |/            \|               |/     \|
1607                            -------------                  ---------  
1608         */
1609
1610         // Make center face
1611         if(vertsize % 2 == 0) {
1612                 hold = addfacelist(verts[(vertsize-1)/2],verts[((vertsize-1)/2)+1],v[left],v[right], NULL,NULL);
1613                 hold->e2->f2 |= EDGEINNER;
1614                 hold->e4->f2 |= EDGEINNER;
1615         }else{
1616                 hold = addfacelist(verts[(vertsize-1)/2],v[left],v[right],NULL, NULL,NULL);  
1617                 hold->e1->f2 |= EDGEINNER;
1618                 hold->e3->f2 |= EDGEINNER;                
1619         }
1620         facecopy(efa,hold);
1621
1622         // Make side faces
1623         for(i=0;i<(vertsize-1)/2;i++) {
1624                 hold = addfacelist(verts[i],verts[i+1],v[right],NULL,NULL,NULL);  
1625                 facecopy(efa,hold);
1626                 if(i+1 != (vertsize-1)/2) {
1627             if(seltype == SUBDIV_SELECT_INNER) {
1628                            hold->e2->f2 |= EDGEINNER;
1629             }
1630                 }
1631                 hold = addfacelist(verts[vertsize-2-i],verts[vertsize-1-i],v[left],NULL,NULL,NULL); 
1632                 facecopy(efa,hold);
1633                 if(i+1 != (vertsize-1)/2) {
1634             if(seltype == SUBDIV_SELECT_INNER) {
1635                                 hold->e3->f2 |= EDGEINNER;
1636             }
1637                 }
1638         }        
1639 }
1640
1641 static void fill_tri_single(EditFace *efa, struct GHash *gh, int numcuts, int seltype)
1642 {
1643         EditEdge *cedge=NULL;
1644         EditVert *v[3], **verts;
1645         EditFace *hold;
1646         short start=0, end, op, vertsize,i;   
1647                                                         
1648         v[0] = efa->v1;
1649         v[1] = efa->v2;
1650         v[2] = efa->v3; 
1651
1652         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
1653         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}        
1654         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}              
1655
1656         // Point verts to the array of new verts for cedge
1657         verts = BLI_ghash_lookup(gh, cedge);
1658         //This is the index size of the verts array
1659         vertsize = numcuts+2;
1660
1661         // Is the original v1 the same as the first vert on the selected edge?
1662         // if not, the edge is running the opposite direction in this face so flip
1663         // the array to the correct direction
1664
1665         if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
1666            end  = (start+1)%3;
1667            op    = (start+2)%3;
1668                    
1669         /*
1670         We should have something like this now
1671
1672                           end            start                           
1673                            3   2   1   0   
1674                            |---*---*---|
1675                            \               |
1676                                  \               |         
1677                                    \       |
1678                                          \       |
1679                                            \   |
1680                                                  \ |
1681                                                    |op
1682                                                    
1683         where start,end,op are indexes of EditFace->v1, etc (stored in v)
1684         and 0,1,2... are the indexes of the new verts stored in verts
1685
1686         We will fill this case like this or this depending on even or odd cuts
1687          
1688                            3   2   1   0   
1689                            |---*---*---|
1690                            \    \  \   |
1691                                  \      \ \  |     
1692                                    \   \ \ |
1693                                          \  \ \|
1694                                            \ \\|
1695                                                  \ |
1696                                                    |op
1697         */
1698
1699         // Make side faces
1700         for(i=0;i<(vertsize-1);i++) {
1701                 hold = addfacelist(verts[i],verts[i+1],v[op],NULL,NULL,NULL);  
1702                 if(i+1 != vertsize-1) {
1703             if(seltype == SUBDIV_SELECT_INNER) {
1704                                 hold->e2->f2 |= EDGEINNER;
1705             }
1706                 }
1707                 facecopy(efa,hold);
1708         }         
1709 }
1710
1711 static void fill_quad_double_op(EditFace *efa, struct GHash *gh, int numcuts)
1712 {
1713         EditEdge *cedge[2]={NULL, NULL};
1714         EditVert *v[4], **verts[2];
1715         EditFace *hold;
1716         short start=0, end, left, right, vertsize,i;
1717                                                         
1718         v[0] = efa->v1;
1719         v[1] = efa->v2;
1720         v[2] = efa->v3;
1721         v[3] = efa->v4;  
1722
1723         if(efa->e1->f & SELECT)   { cedge[0] = efa->e1;  cedge[1] = efa->e3; start = 0;}
1724         else if(efa->e2->f & SELECT)      { cedge[0] = efa->e2;  cedge[1] = efa->e4; start = 1;}
1725
1726         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1727         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1728         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1729         //This is the index size of the verts array
1730         vertsize = numcuts+2;
1731
1732         // Is the original v1 the same as the first vert on the selected edge?
1733         // if not, the edge is running the opposite direction in this face so flip
1734         // the array to the correct direction
1735
1736         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1737         end     = (start+1)%4;
1738         left   = (start+2)%4;
1739         right  = (start+3)%4; 
1740         if(verts[1][0] != v[left]) {flipvertarray(verts[1],numcuts+2);} 
1741         /*
1742         We should have something like this now
1743
1744                           end            start                           
1745                            3   2   1   0   
1746                            |---*---*---|
1747                            |               |
1748                            |               |       
1749                            |               |
1750                            |---*---*---|          
1751                            0   1   2   3
1752                           left     right
1753
1754         We will fill this case like this or this depending on even or odd cuts
1755          
1756                            |---*---*---|
1757                            |   |   |   |
1758                            |   |   |   |           
1759                            |   |   |   |
1760                            |---*---*---| 
1761         */
1762            
1763         // Make side faces
1764         for(i=0;i<vertsize-1;i++) {
1765                 hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-2-i],verts[1][vertsize-1-i],NULL,NULL);  
1766                 if(i < vertsize-2) {
1767                         hold->e2->f2 |= EDGEINNER;
1768                         hold->e2->f2 |= DOUBLEOPFILL;
1769                 }
1770                 facecopy(efa,hold);
1771         }         
1772 }
1773
1774 static void fill_quad_double_adj_path(EditFace *efa, struct GHash *gh, int numcuts)
1775 {
1776         EditEdge *cedge[2]={NULL, NULL};
1777         EditVert *v[4], **verts[2];
1778         EditFace *hold;
1779         short start=0, start2=0, vertsize,i;
1780                                                         
1781         v[0] = efa->v1;
1782         v[1] = efa->v2;
1783         v[2] = efa->v3;
1784         v[3] = efa->v4;  
1785
1786         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
1787         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
1788         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3;}
1789         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0;}
1790
1791         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1792         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1793         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1794         //This is the index size of the verts array
1795         vertsize = numcuts+2;
1796
1797         // Is the original v1 the same as the first vert on the selected edge?
1798         // if not, the edge is running the opposite direction in this face so flip
1799         // the array to the correct direction
1800
1801         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1802         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}       
1803         /*
1804         We should have something like this now
1805
1806                            end           start                           
1807                                 3   2   1   0   
1808                 start2 0|---*---*---|
1809                                 |                  |
1810                            1*              |
1811                                 |                  |
1812                            2*              |       
1813                                 |                  |
1814                  end2  3|-----------|   
1815
1816         We will fill this case like this or this depending on even or odd cuts
1817                            |---*---*---|
1818                            | /   /   / |
1819                            *   /   /   |
1820                            | /   /       |
1821                            *   /           |       
1822                            | /           |
1823                            |-----------|  
1824         */
1825
1826         // Make outside tris
1827         hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);  
1828         /* when ctrl is depressed, only want verts on the cutline selected */
1829         if (G.qual  != LR_CTRLKEY)
1830                 hold->e3->f2 |= EDGEINNER;
1831         facecopy(efa,hold);        
1832         hold = addfacelist(verts[0][0],verts[1][vertsize-1],v[(start2+2)%4],NULL,NULL,NULL);
1833         /* when ctrl is depressed, only want verts on the cutline selected */
1834         if (G.qual  != LR_CTRLKEY)
1835                 hold->e1->f2 |= EDGEINNER;  
1836         facecopy(efa,hold);                        
1837         //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
1838         //      hold->e1->h |= EM_FGON;
1839         //}     
1840         // Make side faces
1841
1842         for(i=0;i<numcuts;i++) {
1843                 hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);  
1844                 hold->e2->f2 |= EDGEINNER;
1845                 facecopy(efa,hold);
1846         }
1847         //EM_fgon_flags();
1848                   
1849 }
1850
1851 static void fill_quad_double_adj_fan(EditFace *efa, struct GHash *gh, int numcuts)
1852 {
1853         EditEdge *cedge[2]={NULL, NULL};
1854         EditVert *v[4], *op=NULL, **verts[2];
1855         EditFace *hold;
1856         short start=0, start2=0, vertsize,i;
1857                                                         
1858         v[0] = efa->v1;
1859         v[1] = efa->v2;
1860         v[2] = efa->v3;
1861         v[3] = efa->v4;  
1862
1863         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1864         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1865         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1866         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1867
1868         
1869         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1870         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1871         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1872         //This is the index size of the verts array
1873         vertsize = numcuts+2;
1874
1875         // Is the original v1 the same as the first vert on the selected edge?
1876         // if not, the edge is running the opposite direction in this face so flip
1877         // the array to the correct direction
1878
1879         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1880         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}       
1881         /*
1882         We should have something like this now
1883
1884                            end           start                           
1885                                 3   2   1   0   
1886                 start2 0|---*---*---|
1887                                 |                  |
1888                            1*              |
1889                                 |                  |
1890                            2*              |       
1891                                 |                  |
1892                  end2  3|-----------|op   
1893
1894         We will fill this case like this or this (warning horrible ascii art follows)
1895                            |---*---*---|
1896                            | \  \   \  |
1897                            *---\  \  \ |
1898                            |   \ \ \  \|
1899                            *---- \ \  \ |          
1900                            |    ---  \\\|
1901                            |-----------|  
1902         */
1903
1904         for(i=0;i<=numcuts;i++) {
1905                 hold = addfacelist(op,verts[1][numcuts-i],verts[1][numcuts-i+1],NULL,NULL,NULL);  
1906                 hold->e1->f2 |= EDGEINNER;
1907                 facecopy(efa,hold);
1908
1909                 hold = addfacelist(op,verts[0][i],verts[0][i+1],NULL,NULL,NULL);  
1910                 hold->e3->f2 |= EDGEINNER;
1911                 facecopy(efa,hold);
1912         }         
1913 }
1914
1915 static void fill_quad_double_adj_inner(EditFace *efa, struct GHash *gh, int numcuts)
1916 {
1917         EditEdge *cedge[2]={NULL, NULL};
1918         EditVert *v[4], *op=NULL, **verts[2],**inner;
1919         EditFace *hold;
1920         short start=0, start2=0, vertsize,i;
1921         float co[3];
1922                                                 
1923         v[0] = efa->v1;
1924         v[1] = efa->v2;
1925         v[2] = efa->v3;
1926         v[3] = efa->v4;  
1927
1928         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
1929         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
1930         if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
1931         if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
1932
1933         
1934         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
1935         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
1936         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
1937         //This is the index size of the verts array
1938         vertsize = numcuts+2;
1939
1940         // Is the original v1 the same as the first vert on the selected edge?
1941         // if not, the edge is running the opposite direction in this face so flip
1942         // the array to the correct direction
1943
1944         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
1945         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}       
1946         /*
1947         We should have something like this now
1948
1949                            end           start                           
1950                                 3   2   1   0   
1951                 start2 0|---*---*---|
1952                                 |                  |
1953                            1*              |
1954                                 |                  |
1955                            2*              |       
1956                                 |                  |
1957                  end2  3|-----------|op   
1958
1959         We will fill this case like this or this (warning horrible ascii art follows)
1960                            |---*-----*---|
1961                            | *     /     |
1962                            *   \ /       |
1963                            |    *        |
1964                            | /    \          |
1965                            *        \    |         
1966                            |           \ |
1967                            |-------------|  
1968         */
1969
1970         // Add Inner Vert(s)
1971         inner = MEM_mallocN(sizeof(EditVert*)*numcuts,"New inner verts");
1972         
1973         for(i=0;i<numcuts;i++) {
1974                         co[0] = (verts[0][numcuts-i]->co[0] + verts[1][i+1]->co[0] ) / 2 ;
1975                         co[1] = (verts[0][numcuts-i]->co[1] + verts[1][i+1]->co[1] ) / 2 ;
1976                         co[2] = (verts[0][numcuts-i]->co[2] + verts[1][i+1]->co[2] ) / 2 ;
1977                         inner[i] = addvertlist(co);
1978                         inner[i]->f2 |= EDGEINNER;
1979         }
1980         
1981         // Add Corner Quad
1982         hold = addfacelist(verts[0][numcuts+1],verts[1][1],inner[0],verts[0][numcuts],NULL,NULL);  
1983         hold->e2->f2 |= EDGEINNER;
1984         hold->e3->f2 |= EDGEINNER;
1985         facecopy(efa,hold);     
1986         // Add Bottom Quads
1987         hold = addfacelist(verts[0][0],verts[0][1],inner[numcuts-1],op,NULL,NULL);  
1988         hold->e2->f2 |= EDGEINNER;
1989         facecopy(efa,hold);     
1990
1991         hold = addfacelist(op,inner[numcuts-1],verts[1][numcuts],verts[1][numcuts+1],NULL,NULL);  
1992         hold->e2->f2 |= EDGEINNER;
1993         facecopy(efa,hold);             
1994         
1995         //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
1996         //      hold->e1->h |= EM_FGON;
1997         //}     
1998         // Add Fill Quads (if # cuts > 1)
1999
2000         for(i=0;i<numcuts-1;i++) {
2001                 hold = addfacelist(inner[i],verts[1][i+1],verts[1][i+2],inner[i+1],NULL,NULL);  
2002                 hold->e1->f2 |= EDGEINNER;
2003                 hold->e3->f2 |= EDGEINNER;
2004                 facecopy(efa,hold);
2005
2006                 hold = addfacelist(inner[i],inner[i+1],verts[0][numcuts-1-i],verts[0][numcuts-i],NULL,NULL);  
2007                 hold->e2->f2 |= EDGEINNER;
2008                 hold->e4->f2 |= EDGEINNER;
2009                 facecopy(efa,hold);     
2010                 
2011                 //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
2012                 //      hold->e1->h |= EM_FGON;
2013                 //}     
2014         }       
2015         
2016         //EM_fgon_flags();
2017         
2018         MEM_freeN(inner);  
2019 }
2020
2021 static void fill_tri_double(EditFace *efa, struct GHash *gh, int numcuts)
2022 {
2023         EditEdge *cedge[2]={NULL, NULL};
2024         EditVert *v[3], **verts[2];
2025         EditFace *hold;
2026         short start=0, start2=0, vertsize,i;
2027                                                         
2028         v[0] = efa->v1;
2029         v[1] = efa->v2;
2030         v[2] = efa->v3;
2031
2032         if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
2033         if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
2034         if(efa->e3->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e1; start = 2; start2 = 0;}
2035
2036         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2037         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2038         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2039         //This is the index size of the verts array
2040         vertsize = numcuts+2;
2041
2042         // Is the original v1 the same as the first vert on the selected edge?
2043         // if not, the edge is running the opposite direction in this face so flip
2044         // the array to the correct direction
2045
2046         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2047         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}       
2048         /*
2049         We should have something like this now
2050
2051                            end           start                           
2052                                 3   2   1   0   
2053                 start2 0|---*---*---|
2054                                 |                /       
2055                            1*      /            
2056                                 |        /               
2057                            2*   /                                
2058                                 | /                
2059                  end2  3|  
2060
2061         We will fill this case like this or this depending on even or odd cuts
2062                            |---*---*---|
2063                            | /   /   / 
2064                            *   /   /   
2065                            | /   /       
2066                            *   /                          
2067                            | /           
2068                            |
2069         */
2070
2071         // Make outside tri
2072         hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);  
2073         hold->e3->f2 |= EDGEINNER;
2074         facecopy(efa,hold);                       
2075         // Make side faces
2076
2077         for(i=0;i<numcuts;i++) {
2078                 hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);  
2079                 hold->e2->f2 |= EDGEINNER;
2080                 facecopy(efa,hold);
2081         }         
2082 }
2083
2084 static void fill_quad_triple(EditFace *efa, struct GHash *gh, int numcuts)
2085 {
2086         EditEdge *cedge[3];
2087         EditVert *v[4], **verts[3];
2088         EditFace *hold;
2089         short start=0, start2=0, start3=0, vertsize, i, repeats;
2090         
2091         v[0] = efa->v1;
2092         v[1] = efa->v2;
2093         v[2] = efa->v3;
2094         v[3] = efa->v4;  
2095            
2096         if(!(efa->e1->f & SELECT)) {
2097                 cedge[0] = efa->e2;  
2098                 cedge[1] = efa->e3; 
2099                 cedge[2] = efa->e4;
2100                 start = 1;start2 = 2;start3 = 3;   
2101         }
2102         if(!(efa->e2->f & SELECT)) {
2103                 cedge[0] = efa->e3;  
2104                 cedge[1] = efa->e4; 
2105                 cedge[2] = efa->e1;
2106                 start = 2;start2 = 3;start3 = 0;   
2107         }
2108         if(!(efa->e3->f & SELECT)) {
2109                 cedge[0] = efa->e4;  
2110                 cedge[1] = efa->e1; 
2111                 cedge[2] = efa->e2;
2112                 start = 3;start2 = 0;start3 = 1;   
2113         }
2114         if(!(efa->e4->f & SELECT)) {
2115                 cedge[0] = efa->e1;  
2116                 cedge[1] = efa->e2; 
2117                 cedge[2] = efa->e3;
2118                 start = 0;start2 = 1;start3 = 2;   
2119         }          
2120         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2121         verts[0] = BLI_ghash_lookup(gh, cedge[0]);
2122         verts[1] = BLI_ghash_lookup(gh, cedge[1]);
2123         verts[2] = BLI_ghash_lookup(gh, cedge[2]);
2124         //This is the index size of the verts array
2125         vertsize = numcuts+2;
2126         
2127         // Is the original v1 the same as the first vert on the selected edge?
2128         // if not, the edge is running the opposite direction in this face so flip
2129         // the array to the correct direction
2130         
2131         if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
2132         if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}  
2133         if(verts[2][0] != v[start3]) {flipvertarray(verts[2],numcuts+2);}   
2134         /*
2135          We should have something like this now
2136          
2137          start2                          
2138          3   2   1   0   
2139          start3 0|---*---*---|3 
2140          |                 |
2141          1*                *2
2142          |                 |
2143          2*                *1      
2144          |                 |
2145          3|-----------|0 start   
2146          
2147          We will fill this case like this or this depending on even or odd cuts  
2148          there are a couple of differences. For odd cuts, there is a tri in the
2149          middle as well as 1 quad at the bottom (not including the extra quads
2150          for odd cuts > 1                 
2151          
2152          For even cuts, there is a quad in the middle and 2 quads on the bottom
2153          
2154          they are numbered here for clarity
2155          
2156          1 outer tris and bottom quads
2157          2 inner tri or quad
2158          3 repeating quads
2159          
2160          |---*---*---*---|
2161          |1/   /  \   \ 1|
2162          |/ 3 / \  3 \|
2163          *  /   2   \   *
2164          | /              \  |
2165          |/                     \ | 
2166          *---------------*
2167          |        3             |
2168          |                         |  
2169          *---------------*
2170          |                         |
2171          |        1             |                                 
2172          |                         |
2173          |---------------|
2174          
2175          |---*---*---*---*---|
2176          | 1/   /        \   \ 1|   
2177          | /   /           \   \ |  
2178          |/ 3 /          \ 3 \|
2179          *   /             \   *
2180          |  /                    \  |   
2181          | /       2       \ |   
2182          |/                              \|
2183          *-------------------*
2184          |                                 |
2185          |               3               |
2186          |                                 | 
2187          *-------------------*
2188          |                                 |
2189          |               1               |
2190          |                                 | 
2191          *-------------------*
2192          |                                 |
2193          |              1                 |
2194          |                                 | 
2195          |-------------------|
2196          
2197          */
2198
2199         // Make outside tris
2200         hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);  
2201         hold->e3->f2 |= EDGEINNER;
2202         facecopy(efa,hold);       
2203         hold = addfacelist(verts[1][vertsize-2],verts[1][vertsize-1],verts[2][1],NULL,NULL,NULL);  
2204         hold->e3->f2 |= EDGEINNER;
2205         facecopy(efa,hold);                       
2206         // Make bottom quad
2207         hold = addfacelist(verts[0][0],verts[0][1],verts[2][vertsize-2],verts[2][vertsize-1],NULL,NULL);  
2208         hold->e2->f2 |= EDGEINNER;
2209         facecopy(efa,hold);              
2210         //If it is even cuts, add the 2nd lower quad
2211         if(numcuts % 2 == 0) {
2212                 hold = addfacelist(verts[0][1],verts[0][2],verts[2][vertsize-3],verts[2][vertsize-2],NULL,NULL);  
2213                 hold->e2->f2 |= EDGEINNER;
2214                 facecopy(efa,hold);              
2215                 // Also Make inner quad
2216                 hold = addfacelist(verts[1][numcuts/2],verts[1][(numcuts/2)+1],verts[2][numcuts/2],verts[0][(numcuts/2)+1],NULL,NULL);             
2217                 hold->e3->f2 |= EDGEINNER;
2218                 //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
2219                 //      hold->e3->h |= EM_FGON;
2220                 //}
2221                 facecopy(efa,hold);
2222                 repeats = (numcuts / 2) -1;
2223         } else {
2224                 // Make inner tri        
2225                 hold = addfacelist(verts[1][(numcuts/2)+1],verts[2][(numcuts/2)+1],verts[0][(numcuts/2)+1],NULL,NULL,NULL);                
2226                 hold->e2->f2 |= EDGEINNER;
2227                 //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
2228                 //      hold->e2->h |= EM_FGON;
2229                 //}
2230                 facecopy(efa,hold);   
2231                 repeats = ((numcuts+1) / 2)-1;
2232         }
2233         
2234         // cuts for 1 and 2 do not have the repeating quads
2235         if(numcuts < 3) {repeats = 0;}
2236         for(i=0;i<repeats;i++) {
2237                 //Make side repeating Quads
2238                 hold = addfacelist(verts[1][i+1],verts[1][i+2],verts[0][vertsize-i-3],verts[0][vertsize-i-2],NULL,NULL);  
2239                 hold->e2->f2 |= EDGEINNER;               
2240                 facecopy(efa,hold);                        
2241                 hold = addfacelist(verts[1][vertsize-i-3],verts[1][vertsize-i-2],verts[2][i+1],verts[2][i+2],NULL,NULL);                   
2242                 hold->e4->f2 |= EDGEINNER;
2243                 facecopy(efa,hold); 
2244         }
2245         // Do repeating bottom quads 
2246         for(i=0;i<repeats;i++) {
2247                 if(numcuts % 2 == 1) {   
2248                         hold = addfacelist(verts[0][1+i],verts[0][2+i],verts[2][vertsize-3-i],verts[2][vertsize-2-i],NULL,NULL);  
2249                 } else {
2250                         hold = addfacelist(verts[0][2+i],verts[0][3+i],verts[2][vertsize-4-i],verts[2][vertsize-3-i],NULL,NULL);                                  
2251                 }
2252                 hold->e2->f2 |= EDGEINNER;
2253                 facecopy(efa,hold);                             
2254         }       
2255         //EM_fgon_flags();
2256 }
2257
2258 static void fill_quad_quadruple(EditFace *efa, struct GHash *gh, int numcuts, float rad, int beauty)
2259 {
2260         EditVert **verts[4], ***innerverts;
2261         EditFace *hold; 
2262         EditEdge temp;
2263         short vertsize, i, j;
2264         
2265         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2266         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2267         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2268         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2269         verts[3] = BLI_ghash_lookup(gh, efa->e4);
2270
2271         //This is the index size of the verts array
2272         vertsize = numcuts+2;
2273
2274         // Is the original v1 the same as the first vert on the selected edge?
2275         // if not, the edge is running the opposite direction in this face so flip
2276         // the array to the correct direction
2277
2278         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2279         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}  
2280         if(verts[2][0] == efa->v3) {flipvertarray(verts[2],numcuts+2);}
2281         if(verts[3][0] == efa->v4) {flipvertarray(verts[3],numcuts+2);}  
2282         /*
2283         We should have something like this now
2284                                           1
2285                                                                                   
2286                                 3   2   1   0   
2287                            0|---*---*---|0 
2288                                 |           |
2289                            1*           *1
2290                      2  |           |   4
2291                            2*           *2         
2292                                 |           |
2293                            3|---*---*---|3      
2294                                 3   2   1   0
2295
2296                                           3
2297         // we will fill a 2 dim array of editvert*s to make filling easier
2298         //  the innervert order is shown
2299
2300                                 0   0---1---2---3 
2301                                         |   |   |   |
2302                                 1   0---1---2---3 
2303                                         |   |   |   |
2304                                 2   0---1---2---3               
2305                                         |   |   |   |
2306                                 3   0---1---2---3  
2307                   
2308          */
2309         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts outer array"); 
2310         for(i=0;i<numcuts+2;i++) {
2311                 innerverts[i] = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts inner array");
2312         }  
2313         
2314         // first row is e1 last row is e3
2315         for(i=0;i<numcuts+2;i++) {
2316                 innerverts[0][i]                  = verts[0][(numcuts+1)-i];
2317                 innerverts[numcuts+1][i]  = verts[2][(numcuts+1)-i];
2318         }
2319         
2320         for(i=1;i<=numcuts;i++) {
2321                 /* we create a fake edge for the next loop */
2322                 temp.v2 = innerverts[i][0]                      = verts[1][i];
2323                 temp.v1 = innerverts[i][numcuts+1]  = verts[3][i];
2324                 
2325                 for(j=1;j<=numcuts;j++) { 
2326                         float percent= (float)j/(float)(numcuts+1);
2327
2328                         innerverts[i][(numcuts+1)-j]= subdivide_edge_addvert(&temp, rad, beauty, percent);
2329                 }       
2330         }       
2331         // Fill with faces
2332         for(i=0;i<numcuts+1;i++) {
2333                 for(j=0;j<numcuts+1;j++) {
2334                         hold = addfacelist(innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],innerverts[i+1][j+1],NULL,NULL);       
2335                         hold->e1->f2 = EDGENEW;   
2336                         hold->e2->f2 = EDGENEW;  
2337                         hold->e3->f2 = EDGENEW;                 
2338                         hold->e4->f2 = EDGENEW;   
2339                         
2340                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2341                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2342                         if(i != numcuts) { hold->e3->f2 |= EDGEINNER; }
2343                         if(j != numcuts) { hold->e4->f2 |= EDGEINNER; }
2344                         
2345                         facecopy(efa,hold);             
2346                 }               
2347         }
2348         // Clean up our dynamic multi-dim array
2349         for(i=0;i<numcuts+2;i++) {
2350            MEM_freeN(innerverts[i]);   
2351         }       
2352         MEM_freeN(innerverts);
2353 }
2354
2355 static void fill_tri_triple(EditFace *efa, struct GHash *gh, int numcuts, float rad, int beauty)
2356 {
2357         EditVert **verts[3], ***innerverts;
2358         short vertsize, i, j;
2359         EditFace *hold;  
2360         EditEdge temp;
2361
2362         // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
2363         verts[0] = BLI_ghash_lookup(gh, efa->e1);
2364         verts[1] = BLI_ghash_lookup(gh, efa->e2);
2365         verts[2] = BLI_ghash_lookup(gh, efa->e3);
2366
2367         //This is the index size of the verts array
2368         vertsize = numcuts+2;
2369
2370         // Is the original v1 the same as the first vert on the selected edge?
2371         // if not, the edge is running the opposite direction in this face so flip
2372         // the array to the correct direction
2373
2374         if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
2375         if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}  
2376         if(verts[2][0] != efa->v3) {flipvertarray(verts[2],numcuts+2);}   
2377         /*
2378         We should have something like this now
2379                                            3
2380                                                                                   
2381                                 3   2   1   0   
2382                            0|---*---*---|3 
2383                                 |                 /     
2384                   1     1*              *2   
2385                                 |         /       
2386                            2*   *1         2             
2387                                 |  /               
2388                            3|/ 
2389                                  0
2390
2391         we will fill a 2 dim array of editvert*s to make filling easier
2392
2393                                                 3
2394
2395                          0  0---1---2---3---4
2396                                 | / | /  |/  | /        
2397                          1  0---1----2---3 
2398            1            | /  | / | /    
2399                          2  0----1---2   2
2400                                 |  / |  /          
2401                                 |/   |/   
2402                          3  0---1 
2403                                 |  /
2404                                 |/
2405                          4  0  
2406           
2407         */
2408         
2409         innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"tri-tri subdiv inner verts outer array"); 
2410         for(i=0;i<numcuts+2;i++) {
2411                   innerverts[i] = MEM_mallocN(sizeof(EditVert*)*((numcuts+2)-i),"tri-tri subdiv inner verts inner array");
2412         }
2413         //top row is e3 backwards
2414         for(i=0;i<numcuts+2;i++) {
2415                   innerverts[0][i]                = verts[2][(numcuts+1)-i];
2416         }   
2417                    
2418         for(i=1;i<=numcuts+1;i++) {
2419                 //fake edge, first vert is from e1, last is from e2
2420                 temp.v1= innerverts[i][0]                         = verts[0][i];
2421                 temp.v2= innerverts[i][(numcuts+1)-i]  = verts[1][(numcuts+1)-i];
2422                 
2423                 for(j=1;j<(numcuts+1)-i;j++) {
2424                         float percent= (float)j/(float)((numcuts+1)-i);
2425
2426                         innerverts[i][((numcuts+1)-i)-j]= subdivide_edge_addvert(&temp, rad, beauty, 1-percent);
2427                 }
2428         }
2429
2430         // Now fill the verts with happy little tris :)
2431         for(i=0;i<=numcuts+1;i++) {
2432                 for(j=0;j<(numcuts+1)-i;j++) {   
2433                         //We always do the first tri
2434                         hold = addfacelist(innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],NULL,NULL,NULL);      
2435                         hold->e1->f2 |= EDGENEW;          
2436                         hold->e2->f2 |= EDGENEW;  
2437                         hold->e3->f2 |= EDGENEW;  
2438                         if(i != 0) { hold->e1->f2 |= EDGEINNER; }
2439                         if(j != 0) { hold->e2->f2 |= EDGEINNER; }
2440                         if(j+1 != (numcuts+1)-i) {hold->e3->f2 |= EDGEINNER;}
2441                         
2442                         facecopy(efa,hold);             
2443                         //if there are more to come, we do the 2nd       
2444                         if(j+1 <= numcuts-i) {
2445                                 hold = addfacelist(innerverts[i+1][j],innerverts[i+1][j+1],innerverts[i][j+1],NULL,NULL,NULL);             
2446                                 facecopy(efa,hold); 
2447                                 hold->e1->f2 |= EDGENEW;          
2448                                 hold->e2->f2 |= EDGENEW;  
2449                                 hold->e3->f2 |= EDGENEW;        
2450                         }
2451                 } 
2452         }
2453
2454         // Clean up our dynamic multi-dim array
2455         for(i=0;i<numcuts+2;i++) {
2456                 MEM_freeN(innerverts[i]);   
2457         }       
2458         MEM_freeN(innerverts);
2459 }
2460
2461 //Next two fill types are for knife exact only and are provided to allow for knifing through vertices
2462 //This means there is no multicut!
2463 static void fill_quad_doublevert(EditFace *efa, int v1, int v2){
2464         EditFace *hold;
2465         /*
2466                 Depending on which two vertices have been knifed through (v1 and v2), we
2467                 triangulate like the patterns below.
2468                                 X-------|       |-------X
2469                                 | \     |       |     / |
2470                                 |   \   |       |   /   |
2471                                 |         \     |       | /         |
2472                                 --------X       X--------
2473         */
2474         
2475         if(v1 == 1 && v2 == 3){
2476                 hold= addfacelist(efa->v1, efa->v2, efa->v3, 0, efa, NULL);
2477                 hold->e1->f2 |= EDGENEW;
2478                 hold->e2->f2 |= EDGENEW;
2479                 hold->e3->f2 |= EDGENEW;
2480                 hold->e3->f2 |= EDGEINNER;
2481                 facecopy(efa, hold);
2482                 
2483                 hold= addfacelist(efa->v1, efa->v3, efa->v4, 0, efa, NULL);
2484                 hold->e1->f2 |= EDGENEW;
2485                 hold->e2->f2 |= EDGENEW;
2486                 hold->e3->f2 |= EDGENEW;
2487                 hold->e1->f2 |= EDGEINNER;
2488                 facecopy(efa, hold);
2489         }
2490         else{
2491                 hold= addfacelist(efa->v1, efa->v2, efa->v4, 0, efa, NULL);
2492                 hold->e1->f2 |= EDGENEW;
2493                 hold->e2->f2 |= EDGENEW;
2494                 hold->e3->f2 |= EDGENEW;
2495                 hold->e2->f2 |= EDGEINNER;
2496                 facecopy(efa, hold);
2497                 
2498                 hold= addfacelist(efa->v2, efa->v3, efa->v4, 0, efa, NULL);
2499                 hold->e1->f2 |= EDGENEW;
2500                 hold->e2->f2 |= EDGENEW;
2501                 hold->e3->f2 |= EDGENEW;
2502                 hold->e3->f2 |= EDGEINNER;
2503                 facecopy(efa, hold);
2504         }
2505 }
2506
2507 static void fill_quad_singlevert(EditFace *efa, struct GHash *gh)
2508 {
2509         EditEdge *cedge=NULL;
2510         EditVert *v[4], **verts;
2511         EditFace *hold;
2512         short start=0, end, left, right, vertsize;   
2513                                                         
2514         v[0] = efa->v1;
2515         v[1] = efa->v2;
2516         v[2] = efa->v3;
2517         v[3] = efa->v4;  
2518
2519         if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
2520         else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}        
2521         else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}        
2522         else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}              
2523
2524         // Point verts to the array of new verts for cedge
2525         verts = BLI_ghash_lookup(gh, cedge);
2526         //This is the index size of the verts array
2527         vertsize = 3;
2528
2529         // Is the original v1 the same as the first vert on the selected edge?
2530         // if not, the edge is running the opposite direction in this face so flip
2531         // the array to the correct direction
2532
2533         if(verts[0] != v[start]) {flipvertarray(verts,3);}
2534         end     = (start+1)%4;
2535         left   = (start+2)%4;
2536         right  = (start+3)%4; 
2537
2538 /*
2539         We should have something like this now
2540
2541                           end            start                           
2542                            2     1     0   
2543                            |-----*-----|
2544                            |               |
2545                            |               |       
2546                            |               |
2547                            -------------           
2548                           left     right
2549
2550         where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
2551         and 0,1,2 are the indexes of the new verts stored in verts. We fill like
2552         this, depending on whether its vertex 'left' or vertex 'right' thats
2553         been knifed through...
2554                                 
2555                                 |---*---|       |---*---|
2556                                 |  /    |       |    \  |
2557                                 | /             |       |         \ |
2558                                 |/              |       |          \|
2559                                 X--------       --------X
2560 */
2561
2562         if(v[left]->f1){
2563                 //triangle is composed of cutvert, end and left
2564                 hold = addfacelist(verts[1],v[end],v[left],NULL, NULL,NULL);
2565                 hold->e1->f2 |= EDGENEW;
2566                 hold->e2->f2 |= EDGENEW;
2567                 hold->e3->f2 |= EDGENEW;
2568                 hold->e3->f2 |= EDGEINNER;
2569                 facecopy(efa, hold);
2570                 
2571                 //quad is composed of cutvert, left, right and start
2572                 hold = addfacelist(verts[1],v[left],v[right],v[start], NULL, NULL);
2573                 hold->e1->f2 |= EDGENEW;
2574                 hold->e2->f2 |= EDGENEW;
2575                 hold->e3->f2 |= EDGENEW;
2576                 hold->e4->f2 |= EDGENEW;
2577                 hold->e1->f2 |= EDGEINNER;
2578                 facecopy(efa, hold);
2579         }
2580         else if(v[right]->f1){
2581                 //triangle is composed of cutvert, right and start
2582                 hold = addfacelist(verts[1],v[right],v[start], NULL, NULL, NULL);
2583                 hold->e1->f2 |= EDGENEW;
2584                 hold->e2->f2 |= EDGENEW;
2585                 hold->e3->f2 |= EDGENEW;
2586                 hold->e1->f2 |= EDGEINNER;
2587                 facecopy(efa, hold);
2588                 //quad is composed of cutvert, end, left, right
2589                 hold = addfacelist(verts[1],v[end], v[left], v[right], NULL, NULL);
2590                 hold->e1->f2 |= EDGENEW;
2591                 hold->e2->f2 |= EDGENEW;
2592                 hold->e3->f2 |= EDGENEW;
2593                 hold->e4->f2 |= EDGENEW;
2594                 hold->e4->f2 |= EDGEINNER;
2595                 facecopy(efa, hold);
2596         }
2597         
2598 }       
2599
2600 // This function takes an example edge, the current point to create and 
2601 // the total # of points to create, then creates the point and return the
2602 // editvert pointer to it.
2603 static EditVert *subdivideedgenum(EditEdge *edge, int curpoint, int totpoint, float rad, int beauty)
2604 {
2605         EditVert *ev;
2606         float percent;
2607          
2608         if (beauty & (B_PERCENTSUBD) && totpoint == 1)
2609                 //percent=(float)(edge->tmp.l)/32768.0f;
2610                 percent= edge->tmp.fp;
2611         else
2612                 percent= (float)curpoint/(float)(totpoint+1);
2613
2614         ev= subdivide_edge_addvert(edge, rad, beauty, percent);
2615         ev->f = edge->v1->f;
2616         
2617         return ev;
2618 }
2619
2620 void esubdivideflag(int flag, float rad, int beauty, int numcuts, int seltype)
2621 {
2622         EditMesh *em = G.editMesh;
2623         EditFace *ef;
2624         EditEdge *eed, *cedge, *sort[4];
2625         EditVert **templist;
2626         struct GHash *gh;
2627         float length[4], v1mat[3], v2mat[3], v3mat[3], v4mat[3];
2628         int i, j, edgecount, touchcount, facetype,hold;
2629         
2630         //Set faces f1 to 0 cause we need it later
2631         for(ef=em->faces.first;ef;ef = ef->next) {
2632                 ef->f1 = 0;
2633         }
2634         
2635         //Flush vertex flags upward to the edges
2636         for(eed = em->edges.first;eed;eed = eed->next) {
2637                 //if(eed->f & flag && eed->v1->f == eed->v2->f) {
2638                 //      eed->f |= eed->v1->f;   
2639                 // }
2640                 eed->f2 = 0;   
2641                 if(eed->f & flag) {
2642                         eed->f2 |= EDGEOLD;
2643                 }
2644         }   
2645                 
2646
2647         // We store an array of verts for each edge that is subdivided,
2648         // we put this array as a value in a ghash which is keyed by the EditEdge*
2649
2650         // Now for beauty subdivide deselect edges based on length
2651         if(beauty & B_BEAUTY) { 
2652                 for(ef = em->faces.first;ef;ef = ef->next) {
2653                         if(!ef->v4) {
2654                                 continue;
2655                         }
2656                         if(ef->f & SELECT) {
2657                                 VECCOPY(v1mat, ef->v1->co);
2658                                 VECCOPY(v2mat, ef->v2->co);
2659                                 VECCOPY(v3mat, ef->v3->co);
2660                                 VECCOPY(v4mat, ef->v4->co);                                             
2661                                 Mat4Mul3Vecfl(G.obedit->obmat, v1mat);
2662                                 Mat4Mul3Vecfl(G.obedit->obmat, v2mat);                                                                                  
2663                                 Mat4Mul3Vecfl(G.obedit->obmat, v3mat);
2664                                 Mat4Mul3Vecfl(G.obedit->obmat, v4mat);
2665                                 
2666                                 length[0] = VecLenf(v1mat, v2mat);
2667                                 length[1] = VecLenf(v2mat, v3mat);
2668                                 length[2] = VecLenf(v3mat, v4mat);
2669                                 length[3] = VecLenf(v4mat, v1mat);
2670                                 sort[0] = ef->e1;
2671                                 sort[1] = ef->e2;
2672                                 sort[2] = ef->e3;
2673                                 sort[3] = ef->e4;
2674                                                                                                   
2675                                                                                                 
2676                                 // Beauty Short Edges
2677                                 if(beauty & B_BEAUTY_SHORT) {
2678                                         for(j=0;j<2;j++) {
2679                                                 hold = -1;
2680                                                 for(i=0;i<4;i++) {
2681                                                         if(length[i] < 0) {
2682                                                                 continue;                                                       
2683                                                         } else if(hold == -1) {  
2684                                                                 hold = i; 
2685                                                         } else {
2686                                                                 if(length[hold] < length[i]) {
2687                                                                         hold = i;   
2688                                                                 }
2689                                                         }
2690                                                 }
2691                                                 sort[hold]->f &= ~SELECT;
2692                                                 sort[hold]->f2 |= EDGENEW;
2693                                                 length[hold] = -1;
2694                                         }                                                       
2695                                 } 
2696                                 
2697                                 // Beauty Long Edges
2698                                 else {
2699                                          for(j=0;j<2;j++) {
2700                                                 hold = -1;
2701                                                 for(i=0;i<4;i++) {
2702                                                         if(length[i] < 0) {
2703                                                                 continue;                                                       
2704                                                         } else if(hold == -1) {  
2705                                                                 hold = i; 
2706                                                         } else {
2707                                                                 if(length[hold] > length[i]) {
2708                                                                         hold = i;   
2709                                                                 }
2710                                                         }
2711                                                 }
2712                                                 sort[hold]->f &= ~SELECT;
2713                                                 sort[hold]->f2 |= EDGENEW;
2714                                                 length[hold] = -1;
2715                                         }                                                       
2716                                 }   
2717                         }
2718                 }       
2719         }
2720
2721         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp); 
2722
2723         // If we are knifing, We only need the selected edges that were cut, so deselect if it was not cut
2724         if(beauty & B_KNIFE) {  
2725                 for(eed= em->edges.first;eed;eed=eed->next) {   
2726                         if( eed->tmp.fp == 0 ) {
2727                                 EM_select_edge(eed,0);
2728                         }
2729                 }
2730         }  
2731         // So for each edge, if it is selected, we allocate an array of size cuts+2
2732         // so we can have a place for the v1, the new verts and v2  
2733         for(eed=em->edges.first;eed;eed = eed->next) {
2734                 if(eed->f & flag) {
2735                         templist = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"vertlist");
2736                         templist[0] = eed->v1;
2737                         for(i=0;i<numcuts;i++) {
2738                                 // This function creates the new vert and returns it back
2739                                 // to the array
2740                                 templist[i+1] = subdivideedgenum(eed, i+1, numcuts, rad, beauty);
2741                                 //while we are here, we can copy edge info from the original edge
2742                                 cedge = addedgelist(templist[i],templist[i+1],eed);
2743                                 // Also set the edge f2 to EDGENEW so that we can use this info later
2744                                 cedge->f2 = EDGENEW;
2745                         }
2746                         templist[i+1] = eed->v2;
2747                         //Do the last edge too
2748                         cedge = addedgelist(templist[i],templist[i+1],eed);
2749                         cedge->f2 = EDGENEW;
2750                         // Now that the edge is subdivided, we can put its verts in the ghash 
2751                         BLI_ghash_insert(gh, eed, templist);                       
2752                 }                                                                 
2753         }
2754
2755         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2756         // Now for each face in the mesh we need to figure out How many edges were cut
2757         // and which filling method to use for that face
2758         for(ef = em->faces.first;ef;ef = ef->next) {
2759                 edgecount = 0;
2760                 facetype = 3;
2761                 if(ef->e1->f & flag) {edgecount++;}
2762                 if(ef->e2->f & flag) {edgecount++;}
2763                 if(ef->e3->f & flag) {edgecount++;}
2764                 if(ef->v4) {
2765                         facetype = 4;
2766                         if(ef->e4->f & flag) {edgecount++;}
2767                 }  
2768                 if(facetype == 4) {
2769                         switch(edgecount) {
2770                                 case 0:
2771                                         if(beauty & B_KNIFE && numcuts == 1){
2772                                                 /*Test for when knifing through two opposite verts but no edges*/
2773                                                 touchcount = 0;
2774                                                 if(ef->v1->f1) touchcount++;
2775                                                 if(ef->v2->f1) touchcount++;
2776                                                 if(ef->v3->f1) touchcount++;
2777                                                 if(ef->v4->f1) touchcount++;
2778                                                 if(touchcount == 2){
2779                                                         if(ef->v1->f1 && ef->v3->f1){ 
2780                                                                 ef->f1 = SELECT;
2781                                                                 fill_quad_doublevert(ef, 1, 3); 
2782                                                         }
2783                                                         else if(ef->v2->f1 && ef->v4->f1){
2784                                                                 ef->f1 = SELECT;
2785                                                                 fill_quad_doublevert(ef, 2, 4);
2786                                                         }
2787                                                 }
2788                                         }
2789                                         break; 
2790                                 
2791                                 case 1: 
2792                                         if(beauty & B_KNIFE && numcuts == 1){
2793                                                 /*Test for when knifing through an edge and one vert*/
2794                                                 touchcount = 0;
2795                                                 if(ef->v1->f1) touchcount++;
2796                                                 if(ef->v2->f1) touchcount++;
2797                                                 if(ef->v3->f1) touchcount++;
2798                                                 if(ef->v4->f1) touchcount++;
2799                                                 
2800                                                 if(touchcount == 1){
2801                                                         if( (ef->e1->f & flag && ( !ef->e1->v1->f1 && !ef->e1->v2->f1 )) ||
2802                                                                 (ef->e2->f & flag && ( !ef->e2->v1->f1 && !ef->e2->v2->f1 )) ||
2803                                                                 (ef->e3->f & flag && ( !ef->e3->v1->f1 && !ef->e3->v2->f1 )) ||
2804                                                                 (ef->e4->f & flag && ( !ef->e4->v1->f1 && !ef->e4->v2->f1 )) ){
2805                                                                 
2806                                                                 ef->f1 = SELECT; 
2807                                                                 fill_quad_singlevert(ef, gh);
2808                                                         }
2809                                                         else{
2810                                                                 ef->f1 = SELECT;
2811                                                                 fill_quad_single(ef, gh, numcuts, seltype);
2812                                                         }
2813                                                 }
2814                                                 else{ 
2815                                                         ef->f1 = SELECT; 
2816                                                         fill_quad_single(ef, gh, numcuts, seltype);
2817                                                 }
2818                                         }
2819                                         else{ 
2820                                                 ef->f1 = SELECT;
2821                                                 fill_quad_single(ef, gh, numcuts, seltype);
2822                                         }
2823                                         break;   
2824                                 case 2: ef->f1 = SELECT;
2825                                         // if there are 2, we check if edge 1 and 3 are either both on or off that way
2826                                         // we can tell if the selected pair is Adjacent or Opposite of each other
2827                                         if((ef->e1->f & flag && ef->e3->f & flag) || 
2828                                            (ef->e2->f & flag && ef->e4->f & flag)) {
2829                                                 fill_quad_double_op(ef, gh, numcuts);                                                     
2830                                         }else{
2831                                                 switch(G.scene->toolsettings->cornertype) {
2832                                                         case 0: fill_quad_double_adj_path(ef, gh, numcuts); break;
2833                                                         case 1: fill_quad_double_adj_inner(ef, gh, numcuts); break;
2834                                                         case 2: fill_quad_double_adj_fan(ef, gh, numcuts); break;
2835                                                 }
2836                                                                                                   
2837                                         }
2838                                                 break;  
2839                                 case 3: ef->f1 = SELECT;
2840                                         fill_quad_triple(ef, gh, numcuts); 
2841                                         break;  
2842                                 case 4: ef->f1 = SELECT;
2843                                         fill_quad_quadruple(ef, gh, numcuts, rad, beauty); 
2844                                         break;  
2845                         }
2846                 } else {
2847                         switch(edgecount) {
2848                                 case 0: break;
2849                                 case 1: ef->f1 = SELECT;
2850                                         fill_tri_single(ef, gh, numcuts, seltype);
2851                                         break;   
2852                                 case 2: ef->f1 = SELECT;
2853                                         fill_tri_double(ef, gh, numcuts);
2854                                         break;  
2855                                 case 3: ef->f1 = SELECT;
2856                                         fill_tri_triple(ef, gh, numcuts, rad, beauty);
2857                                         break;  
2858                         }       
2859                 }       
2860         }
2861         
2862         // Delete Old Faces
2863         free_tagged_facelist(em->faces.first);   
2864         //Delete Old Edges
2865         for(eed = em->edges.first;eed;eed = eed->next) {
2866                 if(BLI_ghash_haskey(gh,eed)) {
2867                         eed->f1 = SELECT; 
2868                 } else {
2869                         eed->f1 = 0;   
2870                 }
2871         } 
2872         free_tagged_edgelist(em->edges.first); 
2873         
2874         if(seltype == SUBDIV_SELECT_ORIG  && G.qual  != LR_CTRLKEY) {
2875                 for(eed = em->edges.first;eed;eed = eed->next) {
2876                         if(eed->f2 & EDGENEW || eed->f2 & EDGEOLD) {
2877                                 eed->f |= flag;
2878                                 EM_select_edge(eed,1); 
2879                                 
2880                         }else{
2881                                 eed->f &= !flag;
2882                                 EM_select_edge(eed,0); 
2883                         }
2884                 }   
2885         } else if ((seltype == SUBDIV_SELECT_INNER || seltype == SUBDIV_SELECT_INNER_SEL)|| G.qual == LR_CTRLKEY) {
2886                 for(eed = em->edges.first;eed;eed = eed->next) {
2887                         if(eed->f2 & EDGEINNER) {
2888                                 eed->f |= flag;
2889                                 EM_select_edge(eed,1);   
2890                                 if(eed->v1->f & EDGEINNER) eed->v1->f |= SELECT;
2891                                 if(eed->v2->f & EDGEINNER) eed->v2->f |= SELECT;
2892                         }else{
2893                                 eed->f &= !flag;
2894                                 EM_select_edge(eed,0); 
2895                         }
2896                 }                 
2897         } else if(seltype == SUBDIV_SELECT_LOOPCUT){
2898                 for(eed = em->edges.first;eed;eed = eed->next) {
2899                         if(eed->f2 & DOUBLEOPFILL){
2900                                 eed->f |= flag;
2901                                 EM_select_edge(eed,1);
2902                         }else{
2903                                 eed->f &= !flag;
2904                                 EM_select_edge(eed,0);
2905                         }
2906                 }
2907         } 
2908          if(G.scene->selectmode & SCE_SELECT_VERTEX) {
2909                  for(eed = em->edges.first;eed;eed = eed->next) {
2910                         if(eed->f & SELECT) {
2911                                 eed->v1->f |= SELECT;
2912                                 eed->v2->f |= SELECT;
2913                         }
2914                 }       
2915         }
2916         // Free the ghash and call MEM_freeN on all the value entries to return 
2917         // that memory
2918         BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);   
2919         
2920         EM_selectmode_flush();
2921         for(ef=em->faces.first;ef;ef = ef->next) {
2922                 if(ef->e4) {
2923                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) &&
2924                          (ef->e3->f & SELECT && ef->e4->f & SELECT) ) {
2925                                 ef->f |= SELECT;                         
2926                         }                                  
2927                 } else {
2928                         if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) && ef->e3->f & SELECT) {
2929                                 ef->f |= SELECT;                         
2930                         }
2931                 }
2932         }
2933         
2934         recalc_editnormals();
2935         countall();
2936         allqueue(REDRAWVIEW3D, 0);
2937         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2938 }
2939
2940 static int count_selected_edges(EditEdge *ed)
2941 {
2942         int totedge = 0;
2943         while(ed) {
2944                 ed->tmp.p = 0;
2945                 if( ed->f & SELECT ) totedge++;
2946                 ed= ed->next;
2947         }
2948         return totedge;
2949 }
2950
2951 /* hurms, as if this makes code readable! It's pointerpointer hiding... (ton) */
2952 typedef EditFace *EVPtr;
2953 typedef EVPtr EVPTuple[2];
2954
2955 /** builds EVPTuple array efaa of face tuples (in fact pointers to EditFaces)
2956         sharing one edge.
2957         arguments: selected edge list, face list.
2958         Edges will also be tagged accordingly (see eed->f2)               */
2959
2960 static int collect_quadedges(EVPTuple *efaa, EditEdge *eed, EditFace *efa)
2961 {
2962         EditEdge *e1, *e2, *e3;
2963         EVPtr *evp;
2964         int i = 0;
2965
2966         /* run through edges, if selected, set pointer edge-> facearray */
2967         while(eed) {
2968                 eed->f2= 0;
2969                 eed->f1= 0;
2970                 if( eed->f & SELECT ) {
2971                         eed->tmp.p = (EditVert *) (&efaa[i]);
2972                         i++;
2973                 }
2974                 else eed->tmp.p = NULL;
2975                 
2976                 eed= eed->next;
2977         }
2978                 
2979         
2980         /* find edges pointing to 2 faces by procedure:
2981         
2982         - run through faces and their edges, increase
2983           face counter e->f1 for each face 
2984         */
2985
2986         while(efa) {
2987                 efa->f1= 0;
2988                 if(efa->v4==0) {  /* if triangle */
2989                         if(efa->f & SELECT) {
2990                                 
2991                                 e1= efa->e1;
2992                                 e2= efa->e2;
2993                                 e3= efa->e3;
2994                                 if(e1->f2<3 && e1->tmp.p) {
2995                                         if(e1->f2<2) {
2996                                                 evp= (EVPtr *) e1->tmp.p;
2997                                                 evp[(int)e1->f2] = efa;
2998                                         }