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