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