2f742d8e985820394023ff560a0db183e0b238cb
[blender.git] / source / blender / src / editmesh_lib.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): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  */
32
33 /*
34
35 editmesh_lib: generic (no UI, no menus) operations/evaluators for editmesh data
36
37 */
38
39 #include <stdlib.h>
40 #include <string.h>
41 #include <math.h>
42
43 #ifdef HAVE_CONFIG_H
44 #include <config.h>
45 #endif
46
47 #include "MEM_guardedalloc.h"
48
49
50 #include "DNA_mesh_types.h"
51 #include "DNA_meshdata_types.h"
52 #include "DNA_modifier_types.h"
53 #include "DNA_object_types.h"
54 #include "DNA_scene_types.h"
55
56 #include "BLI_blenlib.h"
57 #include "BLI_arithb.h"
58 #include "BLI_editVert.h"
59
60 #include "BKE_global.h"
61 #include "BKE_mesh.h"
62 #include "BKE_utildefines.h"
63
64 #include "BIF_editmesh.h"
65
66 #ifdef WITH_VERSE
67 #include "BIF_verse.h"
68 #endif
69
70 #include "BSE_edit.h"
71
72 #include "editmesh.h"
73
74 /* ********* Selection History ************ */
75 static int EM_check_selection(void *data)
76 {
77         EditSelection *ese;
78         
79         for(ese = G.editMesh->selected.first; ese; ese = ese->next){
80                 if(ese->data == data) return 1;
81                 }
82         
83         return 0;
84 }
85
86 void EM_remove_selection(void *data, int type)
87 {
88         EditSelection *ese;
89         for(ese=G.editMesh->selected.first; ese; ese = ese->next){
90                 if(ese->data == data){
91                         BLI_freelinkN(&(G.editMesh->selected),ese);
92                         break;
93                 }
94         }
95 }
96
97 void EM_store_selection(void *data, int type)
98 {
99         EditSelection *ese;
100         if(!EM_check_selection(data)){
101                 ese = (EditSelection*) MEM_callocN( sizeof(EditSelection), "Edit Selection");
102                 ese->type = type;
103                 ese->data = data;
104                 BLI_addtail(&(G.editMesh->selected),ese);
105         }
106 }
107
108 void EM_validate_selections(void)
109 {
110         EditSelection *ese, *nextese;
111         EditMesh *em = G.editMesh;
112         ese = em->selected.first;
113         while(ese){
114                 nextese = ese->next;
115                 if(ese->type == EDITVERT && !(((EditVert*)ese->data)->f & SELECT)) BLI_freelinkN(&(em->selected), ese);
116                 else if(ese->type == EDITEDGE && !(((EditEdge*)ese->data)->f & SELECT)) BLI_freelinkN(&(em->selected), ese);
117                 else if(ese->type == EDITFACE && !(((EditFace*)ese->data)->f & SELECT)) BLI_freelinkN(&(em->selected), ese);
118                 ese = nextese;
119         }
120 }
121
122 static void EM_strip_selections(void)
123 {
124         EditSelection *ese, *nextese;
125         if(!(G.scene->selectmode & SCE_SELECT_VERTEX)){
126                 ese = G.editMesh->selected.first;
127                 while(ese){
128                         nextese = ese->next; 
129                         if(ese->type == EDITVERT) BLI_freelinkN(&(G.editMesh->selected),ese);
130                         ese = nextese;
131                 }
132         }
133         if(!(G.scene->selectmode & SCE_SELECT_EDGE)){
134                 ese=G.editMesh->selected.first;
135                 while(ese){
136                         nextese = ese->next;
137                         if(ese->type == EDITEDGE) BLI_freelinkN(&(G.editMesh->selected), ese);
138                         ese = nextese;
139                 }
140         }
141         if(!(G.scene->selectmode & SCE_SELECT_FACE)){
142                 ese=G.editMesh->selected.first;
143                 while(ese){
144                         nextese = ese->next;
145                         if(ese->type == EDITFACE) BLI_freelinkN(&(G.editMesh->selected), ese);
146                         ese = nextese;
147                 }
148         }
149 }
150
151 /* generic way to get data from an EditSelection type 
152 These functions were written to be used by the Modifier widget when in Rotate about active mode,
153 but can be used anywhere.
154 EM_editselection_center
155 EM_editselection_normal
156 EM_editselection_plane
157 */
158 void EM_editselection_center(float *center, EditSelection *ese)
159 {
160         if (ese->type==EDITVERT) {
161                 EditVert *eve= ese->data;
162                 VecCopyf(center, eve->co);
163         } else if (ese->type==EDITEDGE) {
164                 EditEdge *eed= ese->data;
165                 VecAddf(center, eed->v1->co, eed->v2->co);
166                 VecMulf(center, 0.5);
167         } else if (ese->type==EDITFACE) {
168                 EditFace *efa= ese->data;
169                 VecCopyf(center, efa->cent);
170         }
171 }
172
173 void EM_editselection_normal(float *normal, EditSelection *ese)
174 {
175         if (ese->type==EDITVERT) {
176                 EditVert *eve= ese->data;
177                 VecCopyf(normal, eve->no);
178         } else if (ese->type==EDITEDGE) {
179                 EditEdge *eed= ese->data;
180                 float plane[3]; /* need a plane to correct the normal */
181                 float vec[3]; /* temp vec storage */
182                 
183                 VecAddf(normal, eed->v1->no, eed->v2->no);
184                 VecSubf(plane, eed->v2->co, eed->v1->co);
185                 
186                 /* the 2 vertex normals will be close but not at rightangles to the edge
187                 for rotate about edge we want them to be at right angles, so we need to
188                 do some extra colculation to correct the vert normals,
189                 we need the plane for this */
190                 Crossf(vec, normal, plane);
191                 Crossf(normal, plane, vec); 
192                 Normalise(normal);
193                 
194         } else if (ese->type==EDITFACE) {
195                 EditFace *efa= ese->data;
196                 VecCopyf(normal, efa->n);
197         }
198 }
199
200 /* Calculate a plane that is rightangles to the edge/vert/faces normal
201 also make the plane run allong an axis that is related to the geometry,
202 because this is used for the manipulators Y axis.*/
203 void EM_editselection_plane(float *plane, EditSelection *ese)
204 {
205         if (ese->type==EDITVERT) {
206                 EditVert *eve= ese->data;
207                 float vec[3]={0,0,0};
208                 
209                 if (ese->prev) { /*use previously selected data to make a usefull vertex plane */
210                         EM_editselection_center(vec, ese->prev);
211                         VecSubf(plane, vec, eve->co);
212                 } else {
213                         /* make a fake  plane thats at rightangles to the normal
214                         we cant make a crossvec from a vec thats the same as the vec
215                         unlikely but possible, so make sure if the normal is (0,0,1)
216                         that vec isnt the same or in the same direction even.*/
217                         if (eve->no[0]<0.5)                     vec[0]=1;
218                         else if (eve->no[1]<0.5)        vec[1]=1;
219                         else                                            vec[2]=1;
220                         Crossf(plane, eve->no, vec);
221                 }
222         } else if (ese->type==EDITEDGE) {
223                 EditEdge *eed= ese->data;
224
225                 /*the plane is simple, it runs allong the edge
226                 however selecting different edges can swap the direction of the y axis.
227                 this makes it less likely for the y axis of the manipulator
228                 (running along the edge).. to flip less often.
229                 at least its more pradictable */
230                 if (eed->v2->co[1] > eed->v1->co[1]) /*check which to do first */
231                         VecSubf(plane, eed->v2->co, eed->v1->co);
232                 else
233                         VecSubf(plane, eed->v1->co, eed->v2->co);
234                 
235         } else if (ese->type==EDITFACE) {
236                 EditFace *efa= ese->data;
237                 float vec[3];
238                 if (efa->v4) { /*if its a quad- set the plane along the 2 longest edges.*/
239                         float vecA[3], vecB[3];
240                         VecSubf(vecA, efa->v4->co, efa->v3->co);
241                         VecSubf(vecB, efa->v1->co, efa->v2->co);
242                         VecAddf(plane, vecA, vecB);
243                         
244                         VecSubf(vecA, efa->v1->co, efa->v4->co);
245                         VecSubf(vecB, efa->v2->co, efa->v3->co);
246                         VecAddf(vec, vecA, vecB);                                               
247                         /*use the biggest edge length*/
248                         if (plane[0]*plane[0]+plane[1]*plane[1]+plane[2]*plane[2] < vec[0]*vec[0]+vec[1]*vec[1]+vec[2]*vec[2])
249                                 VecCopyf(plane, vec);
250                 } else {
251                         /*start with v1-2 */
252                         VecSubf(plane, efa->v1->co, efa->v2->co);
253                         
254                         /*test the edge between v2-3, use if longer */
255                         VecSubf(vec, efa->v2->co, efa->v3->co);
256                         if (plane[0]*plane[0]+plane[1]*plane[1]+plane[2]*plane[2] < vec[0]*vec[0]+vec[1]*vec[1]+vec[2]*vec[2])
257                                 VecCopyf(plane, vec);
258                         
259                         /*test the edge between v1-3, use if longer */
260                         VecSubf(vec, efa->v3->co, efa->v1->co);
261                         if (plane[0]*plane[0]+plane[1]*plane[1]+plane[2]*plane[2] < vec[0]*vec[0]+vec[1]*vec[1]+vec[2]*vec[2])
262                                 VecCopyf(plane, vec);
263                 }
264         }
265         Normalise(plane);
266 }
267
268
269
270 void EM_select_face(EditFace *efa, int sel)
271 {
272         if(sel) {
273                 efa->f |= SELECT;
274                 efa->e1->f |= SELECT;
275                 efa->e2->f |= SELECT;
276                 efa->e3->f |= SELECT;
277                 if(efa->e4) efa->e4->f |= SELECT;
278                 efa->v1->f |= SELECT;
279                 efa->v2->f |= SELECT;
280                 efa->v3->f |= SELECT;
281                 if(efa->v4) efa->v4->f |= SELECT;
282         }
283         else {
284                 efa->f &= ~SELECT;
285                 efa->e1->f &= ~SELECT;
286                 efa->e2->f &= ~SELECT;
287                 efa->e3->f &= ~SELECT;
288                 if(efa->e4) efa->e4->f &= ~SELECT;
289                 efa->v1->f &= ~SELECT;
290                 efa->v2->f &= ~SELECT;
291                 efa->v3->f &= ~SELECT;
292                 if(efa->v4) efa->v4->f &= ~SELECT;
293         }
294 }
295
296 void EM_select_edge(EditEdge *eed, int sel)
297 {
298         if(sel) {
299                 eed->f |= SELECT;
300                 eed->v1->f |= SELECT;
301                 eed->v2->f |= SELECT;
302         }
303         else {
304                 eed->f &= ~SELECT;
305                 eed->v1->f &= ~SELECT;
306                 eed->v2->f &= ~SELECT;
307         }
308 }
309
310 void EM_select_face_fgon(EditFace *efa, int val)
311 {
312         EditMesh *em = G.editMesh;
313         short index=0;
314         
315         if(efa->fgonf==0) EM_select_face(efa, val);
316         else {
317                 if(efa->e1->fgoni) index= efa->e1->fgoni;
318                 if(efa->e2->fgoni) index= efa->e2->fgoni;
319                 if(efa->e3->fgoni) index= efa->e3->fgoni;
320                 if(efa->v4 && efa->e4->fgoni) index= efa->e4->fgoni;
321                 
322                 if(index==0) printf("wrong fgon select\n");
323                 
324                 // select all ngon faces with index
325                 for(efa= em->faces.first; efa; efa= efa->next) {
326                         if(efa->fgonf) {
327                                 if(efa->e1->fgoni==index || efa->e2->fgoni==index || 
328                                    efa->e3->fgoni==index || (efa->e4 && efa->e4->fgoni==index) ) {
329                                         EM_select_face(efa, val);
330                                 }
331                         }
332                 }
333         }
334 }
335
336
337 /* only vertices */
338 int faceselectedOR(EditFace *efa, int flag)
339 {
340         if ((efa->v1->f | efa->v2->f | efa->v3->f | (efa->v4?efa->v4->f:0))&flag) {
341                 return 1;
342         } else {
343                 return 0;
344         }
345 }
346
347 // replace with (efa->f & SELECT)
348 int faceselectedAND(EditFace *efa, int flag)
349 {
350         if ((efa->v1->f & efa->v2->f & efa->v3->f & (efa->v4?efa->v4->f:flag))&flag) {
351                 return 1;
352         } else {
353                 return 0;
354         }
355 }
356
357 int EM_nfaces_selected(void)
358 {
359         EditMesh *em = G.editMesh;
360         EditFace *efa;
361         int count= 0;
362
363         for (efa= em->faces.first; efa; efa= efa->next)
364                 if (efa->f & SELECT)
365                         count++;
366
367         return count;
368 }
369
370 #if 0
371 static int EM_nedges(void)
372 {
373         EditMesh *em = G.editMesh;
374         EditEdge *eed;
375         int count= 0;
376
377         for (eed= em->edges.first; eed; eed= eed->next) count++;
378         return count;
379 }
380 #endif
381
382 int EM_nvertices_selected(void)
383 {
384         EditMesh *em = G.editMesh;
385         EditVert *eve;
386         int count= 0;
387
388         for (eve= em->verts.first; eve; eve= eve->next)
389                 if (eve->f & SELECT)
390                         count++;
391
392         return count;
393 }
394
395 void EM_clear_flag_all(int flag)
396 {
397         EditMesh *em = G.editMesh;
398         EditVert *eve;
399         EditEdge *eed;
400         EditFace *efa;
401         
402         for (eve= em->verts.first; eve; eve= eve->next) eve->f &= ~flag;
403         for (eed= em->edges.first; eed; eed= eed->next) eed->f &= ~flag;
404         for (efa= em->faces.first; efa; efa= efa->next) efa->f &= ~flag;
405         
406         if(flag & SELECT) BLI_freelistN(&(G.editMesh->selected));
407 }
408
409 void EM_set_flag_all(int flag)
410 {
411         EditMesh *em = G.editMesh;
412         EditVert *eve;
413         EditEdge *eed;
414         EditFace *efa;
415         
416         for (eve= em->verts.first; eve; eve= eve->next) if(eve->h==0) eve->f |= flag;
417         for (eed= em->edges.first; eed; eed= eed->next) if(eed->h==0) eed->f |= flag;
418         for (efa= em->faces.first; efa; efa= efa->next) if(efa->h==0) efa->f |= flag;
419         
420 }
421
422 /* flush for changes in vertices only */
423 void EM_deselect_flush(void)
424 {
425         EditMesh *em = G.editMesh;
426         EditEdge *eed;
427         EditFace *efa;
428         
429         for(eed= em->edges.first; eed; eed= eed->next) {
430                 if(eed->v1->f & eed->v2->f & SELECT);
431                 else eed->f &= ~SELECT;
432         }
433         for(efa= em->faces.first; efa; efa= efa->next) {
434                 if(efa->v4) {
435                         if(efa->v1->f & efa->v2->f & efa->v3->f & efa->v4->f & SELECT );
436                         else efa->f &= ~SELECT;
437                 }
438                 else {
439                         if(efa->v1->f & efa->v2->f & efa->v3->f & SELECT );
440                         else efa->f &= ~SELECT;
441                 }
442         }
443 }
444
445
446 /* flush selection to edges & faces */
447
448 /*  this only based on coherent selected vertices, for example when adding new
449     objects. call clear_flag_all() before you select vertices to be sure it ends OK!
450         
451 */
452
453 void EM_select_flush(void)
454 {
455         EditMesh *em = G.editMesh;
456         EditEdge *eed;
457         EditFace *efa;
458         
459         for(eed= em->edges.first; eed; eed= eed->next) {
460                 if(eed->v1->f & eed->v2->f & SELECT) eed->f |= SELECT;
461         }
462         for(efa= em->faces.first; efa; efa= efa->next) {
463                 if(efa->v4) {
464                         if(efa->v1->f & efa->v2->f & efa->v3->f & efa->v4->f & SELECT ) efa->f |= SELECT;
465                 }
466                 else {
467                         if(efa->v1->f & efa->v2->f & efa->v3->f & SELECT ) efa->f |= SELECT;
468                 }
469         }
470 }
471
472 /* when vertices or edges can be selected, also make fgon consistant */
473 static void check_fgons_selection()
474 {
475         EditMesh *em = G.editMesh;
476         EditFace *efa, *efan;
477         EditEdge *eed;
478         ListBase *lbar;
479         int sel, desel, index, totfgon= 0;
480         
481         /* count amount of fgons */
482         for(eed= em->edges.first; eed; eed= eed->next) 
483                 if(eed->fgoni>totfgon) totfgon= eed->fgoni;
484         
485         if(totfgon==0) return;
486         
487         lbar= MEM_callocN((totfgon+1)*sizeof(ListBase), "listbase array");
488         
489         /* put all fgons in lbar */
490         for(efa= em->faces.first; efa; efa= efan) {
491                 efan= efa->next;
492                 index= efa->e1->fgoni;
493                 if(index==0) index= efa->e2->fgoni;
494                 if(index==0) index= efa->e3->fgoni;
495                 if(index==0 && efa->e4) index= efa->e4->fgoni;
496                 if(index) {
497                         BLI_remlink(&em->faces, efa);
498                         BLI_addtail(&lbar[index], efa);
499                 }
500         }
501         
502         /* now check the fgons */
503         for(index=1; index<=totfgon; index++) {
504                 /* we count on vertices/faces/edges being set OK, so we only have to set ngon itself */
505                 sel= desel= 0;
506                 for(efa= lbar[index].first; efa; efa= efa->next) {
507                         if(efa->e1->fgoni==0) {
508                                 if(efa->e1->f & SELECT) sel++;
509                                 else desel++;
510                         }
511                         if(efa->e2->fgoni==0) {
512                                 if(efa->e2->f & SELECT) sel++;
513                                 else desel++;
514                         }
515                         if(efa->e3->fgoni==0) {
516                                 if(efa->e3->f & SELECT) sel++;
517                                 else desel++;
518                         }
519                         if(efa->e4 && efa->e4->fgoni==0) {
520                                 if(efa->e4->f & SELECT) sel++;
521                                 else desel++;
522                         }
523                         
524                         if(sel && desel) break;
525                 }
526
527                 if(sel && desel) sel= 0;
528                 else if(sel) sel= 1;
529                 else sel= 0;
530                 
531                 /* select/deselect and put back */
532                 for(efa= lbar[index].first; efa; efa= efa->next) {
533                         if(sel) efa->f |= SELECT;
534                         else efa->f &= ~SELECT;
535                 }
536                 addlisttolist(&em->faces, &lbar[index]);
537         }
538         
539         MEM_freeN(lbar);
540 }
541
542
543 /* flush to edges & faces */
544
545 /* based on select mode it selects edges/faces 
546    assumed is that verts/edges/faces were properly selected themselves
547    with the calls above
548 */
549
550 void EM_selectmode_flush(void)
551 {
552         EditMesh *em = G.editMesh;
553         EditEdge *eed;
554         EditFace *efa;
555         
556         // flush to edges & faces
557         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
558                 for(eed= em->edges.first; eed; eed= eed->next) {
559                         if(eed->v1->f & eed->v2->f & SELECT) eed->f |= SELECT;
560                         else eed->f &= ~SELECT;
561                 }
562                 for(efa= em->faces.first; efa; efa= efa->next) {
563                         if(efa->v4) {
564                                 if(efa->v1->f & efa->v2->f & efa->v3->f & efa->v4->f & SELECT) efa->f |= SELECT;
565                                 else efa->f &= ~SELECT;
566                         }
567                         else {
568                                 if(efa->v1->f & efa->v2->f & efa->v3->f & SELECT) efa->f |= SELECT;
569                                 else efa->f &= ~SELECT;
570                         }
571                 }
572         }
573         // flush to faces
574         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
575                 for(efa= em->faces.first; efa; efa= efa->next) {
576                         if(efa->e4) {
577                                 if(efa->e1->f & efa->e2->f & efa->e3->f & efa->e4->f & SELECT) efa->f |= SELECT;
578                                 else efa->f &= ~SELECT;
579                         }
580                         else {
581                                 if(efa->e1->f & efa->e2->f & efa->e3->f & SELECT) efa->f |= SELECT;
582                                 else efa->f &= ~SELECT;
583                         }
584                 }
585         }       
586         // make sure selected faces have selected edges too, for extrude (hack?)
587         else if(G.scene->selectmode & SCE_SELECT_FACE) {
588                 for(efa= em->faces.first; efa; efa= efa->next) {
589                         if(efa->f & SELECT) EM_select_face(efa, 1);
590                 }
591         }
592         check_fgons_selection();
593
594 }
595
596 void EM_convertsel(short oldmode, short selectmode)
597 {
598         EditMesh *em = G.editMesh;
599         EditVert *eve;
600         EditEdge *eed;
601         EditFace *efa;
602         /*clear flags*/
603         for(eve= em->verts.first; eve; eve= eve->next) eve->f1 = 0;
604         for(eed= em->edges.first; eed; eed= eed->next) eed->f1 = 0;
605         for(efa= em->faces.first; efa; efa= efa->next) efa->f1 = 0;
606         
607         /*have to find out what the selectionmode was previously*/
608         if(oldmode == SCE_SELECT_VERTEX) {
609                 if(selectmode == SCE_SELECT_EDGE){
610                         /*select all edges associated with every selected vertex*/
611                         for(eed= em->edges.first; eed; eed= eed->next){
612                                 if(eed->v1->f&SELECT) eed->f1 = 1;
613                                 else if(eed->v2->f&SELECT) eed->f1 = 1;
614                         }
615                         
616                         for(eed= em->edges.first; eed; eed= eed->next){
617                                 if(eed->f1 == 1) EM_select_edge(eed,1); 
618                         }
619                 }               
620                 else if(selectmode == SCE_SELECT_FACE){
621                         /*select all faces associated with every selected vertex*/
622                         for(efa= em->faces.first; efa; efa= efa->next){
623                                 if(efa->v1->f&SELECT) efa->f1 = 1;
624                                 else if(efa->v2->f&SELECT) efa->f1 = 1;
625                                 else if(efa->v3->f&SELECT) efa->f1 = 1;
626                                 else{ 
627                                         if(efa->v4){
628                                                 if(efa->v4->f&SELECT) efa->f1 =1;
629                                         }
630                                 }
631                         }
632                         for(efa= em->faces.first; efa; efa= efa->next){
633                                 if(efa->f1 == 1) EM_select_face(efa,1);
634                         }
635                 }
636         }
637         
638         if(oldmode == SCE_SELECT_EDGE){
639                 if(selectmode == SCE_SELECT_FACE){
640                         for(efa= em->faces.first; efa; efa= efa->next){
641                                 if(efa->e1->f&SELECT) efa->f1 = 1;
642                                 else if(efa->e2->f&SELECT) efa->f1 = 1;
643                                 else if(efa->e3->f&SELECT) efa->f1 = 1;
644                                 else if(efa->e4){
645                                         if(efa->e4->f&SELECT) efa->f1 = 1;
646                                 }
647                         }
648                         for(efa= em->faces.first; efa; efa= efa->next){
649                                 if(efa->f1 == 1) EM_select_face(efa,1);
650                         }
651                 }
652         }
653         
654         check_fgons_selection();
655 }
656
657 /* when switching select mode, makes sure selection is consistant for editing */
658 /* also for paranoia checks to make sure edge or face mode works */
659 void EM_selectmode_set(void)
660 {
661         EditMesh *em = G.editMesh;
662         EditVert *eve;
663         EditEdge *eed;
664         EditFace *efa;
665         
666         EM_strip_selections(); /*strip EditSelections from em->selected that are not relevant to new mode*/
667         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
668                 /* vertices -> edges -> faces */
669                 for (eed= em->edges.first; eed; eed= eed->next) eed->f &= ~SELECT;
670                 for (efa= em->faces.first; efa; efa= efa->next) efa->f &= ~SELECT;
671                 
672                 EM_select_flush();
673         }
674         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
675                 /* deselect vertices, and select again based on edge select */
676                 for(eve= em->verts.first; eve; eve= eve->next) eve->f &= ~SELECT;
677                 for(eed= em->edges.first; eed; eed= eed->next) 
678                         if(eed->f & SELECT) EM_select_edge(eed, 1);
679                 /* selects faces based on edge status */
680                 EM_selectmode_flush();
681         }
682         else if(G.scene->selectmode & SCE_SELECT_FACE) {
683                 /* deselect eges, and select again based on face select */
684                 for(eed= em->edges.first; eed; eed= eed->next) EM_select_edge(eed, 0);
685                 
686                 for(efa= em->faces.first; efa; efa= efa->next) 
687                         if(efa->f & SELECT) EM_select_face(efa, 1);
688         }
689 }
690
691 /* paranoia check, actually only for entering editmode. rule:
692 - vertex hidden, always means edge is hidden too
693 - edge hidden, always means face is hidden too
694 - face hidden, dont change anything
695 */
696 void EM_hide_reset(void)
697 {
698         EditMesh *em = G.editMesh;
699         EditEdge *eed;
700         EditFace *efa;
701         
702         for(eed= em->edges.first; eed; eed= eed->next) 
703                 if(eed->v1->h || eed->v2->h) eed->h |= 1;
704                 
705         for(efa= em->faces.first; efa; efa= efa->next) 
706                 if((efa->e1->h & 1) || (efa->e2->h & 1) || (efa->e3->h & 1) || (efa->e4 && (efa->e4->h & 1)))
707                         efa->h= 1;
708                 
709 }
710
711
712 /* ********  EXTRUDE ********* */
713
714 static void add_normal_aligned(float *nor, float *add)
715 {
716         if( INPR(nor, add) < 0.0 ) 
717                 VecSubf(nor, nor, add);
718         else
719                 VecAddf(nor, nor, add);
720 }
721
722 static void set_edge_directions_f2(int val)
723 {
724         EditMesh *em= G.editMesh;
725         EditFace *efa;
726         int do_all= 1;
727         
728         /* edge directions are used for extrude, to detect direction of edges that make new faces */
729         /* we have set 'f2' flags in edges that need to get a direction set (e.g. get new face) */
730         /* the val argument differs... so we need it as arg */
731         
732         for(efa= em->faces.first; efa; efa= efa->next) {
733                 if(efa->f & SELECT) {
734                         do_all= 0;
735                         if(efa->e1->f2<val) {
736                                 if(efa->e1->v1 == efa->v1) efa->e1->dir= 0;
737                                 else efa->e1->dir= 1;
738                         }
739                         if(efa->e2->f2<val) {
740                                 if(efa->e2->v1 == efa->v2) efa->e2->dir= 0;
741                                 else efa->e2->dir= 1;
742                         }
743                         if(efa->e3->f2<val) {
744                                 if(efa->e3->v1 == efa->v3) efa->e3->dir= 0;
745                                 else efa->e3->dir= 1;
746                         }
747                         if(efa->e4 && efa->e4->f2<val) {
748                                 if(efa->e4->v1 == efa->v4) efa->e4->dir= 0;
749                                 else efa->e4->dir= 1;
750                         }
751                 }
752         }       
753         /* ok, no faces done... then we at least set it for exterior edges */
754         if(do_all) {
755                 for(efa= em->faces.first; efa; efa= efa->next) {
756                         if(efa->e1->v1 == efa->v1) efa->e1->dir= 0;
757                         else efa->e1->dir= 1;
758                         if(efa->e2->v1 == efa->v2) efa->e2->dir= 0;
759                         else efa->e2->dir= 1;
760                         if(efa->e3->v1 == efa->v3) efa->e3->dir= 0;
761                         else efa->e3->dir= 1;
762                         if(efa->e4) {
763                                 if(efa->e4->v1 == efa->v4) efa->e4->dir= 0;
764                                 else efa->e4->dir= 1;
765                         }
766                 }       
767         }
768 }
769
770 /* individual face extrude */
771 /* will use vertex normals for extrusion directions, so *nor is unaffected */
772 short extrudeflag_face_indiv(short flag, float *nor)
773 {
774         EditMesh *em = G.editMesh;
775         EditVert *eve, *v1, *v2, *v3, *v4;
776         EditEdge *eed;
777         EditFace *efa, *nextfa;
778         
779         if(G.obedit==0 || get_mesh(G.obedit)==0) return 0;
780         
781         /* selected edges with 1 or more selected face become faces */
782         /* selected faces each makes new faces */
783         /* always remove old faces, keeps volumes manifold */
784         /* select the new extrusion, deselect old */
785         
786         /* step 1; init, count faces in edges */
787         recalc_editnormals();
788         
789         for(eve= em->verts.first; eve; eve= eve->next) eve->f1= 0;      // new select flag
790
791         for(eed= em->edges.first; eed; eed= eed->next) {
792                 eed->f2= 0; // amount of unselected faces
793         }
794         for(efa= em->faces.first; efa; efa= efa->next) {
795                 if(efa->f & SELECT);
796                 else {
797                         efa->e1->f2++;
798                         efa->e2->f2++;
799                         efa->e3->f2++;
800                         if(efa->e4) efa->e4->f2++;
801                 }
802         }
803
804         /* step 2: make new faces from faces */
805         for(efa= em->faces.last; efa; efa= efa->prev) {
806                 if(efa->f & SELECT) {
807                         v1= addvertlist(efa->v1->co);
808                         if(efa->v1->totweight){
809                                 v1->dw = MEM_dupallocN(efa->v1->dw);
810                                 v1->totweight = efa->v1->totweight;
811                         }
812                         
813                         v2= addvertlist(efa->v2->co);
814                         if(efa->v2->totweight){
815                                 v2->dw = MEM_dupallocN(efa->v2->dw);
816                                 v2->totweight = efa->v2->totweight;
817                         }
818                 
819                         v3= addvertlist(efa->v3->co);
820                         if(efa->v3->totweight){
821                                 v3->dw = MEM_dupallocN(efa->v3->dw);
822                                 v3->totweight = efa->v3->totweight;
823                         }
824                         
825                         v1->f1= v2->f1= v3->f1= 1;
826                         VECCOPY(v1->no, efa->n);
827                         VECCOPY(v2->no, efa->n);
828                         VECCOPY(v3->no, efa->n);
829                         if(efa->v4) {
830                                 v4= addvertlist(efa->v4->co); 
831                                 if(efa->v4->totweight){
832                                         v4->dw = MEM_dupallocN(efa->v4->dw);
833                                         v4->totweight = efa->v4->totweight;
834                                 }
835                                 v4->f1= 1;
836                                 VECCOPY(v4->no, efa->n);
837                         }
838                         else v4= NULL;
839                         
840                         /* side faces, clockwise */
841                         addfacelist(efa->v2, v2, v1, efa->v1, efa, NULL);
842                         addfacelist(efa->v3, v3, v2, efa->v2, efa, NULL);
843                         if(efa->v4) {
844                                 addfacelist(efa->v4, v4, v3, efa->v3, efa, NULL);
845                                 addfacelist(efa->v1, v1, v4, efa->v4, efa, NULL);
846                         }
847                         else {
848                                 addfacelist(efa->v1, v1, v3, efa->v3, efa, NULL);
849                         }
850                         /* top face */
851                         addfacelist(v1, v2, v3, v4, efa, NULL);
852                 }
853         }
854         
855         /* step 3: remove old faces */
856         efa= em->faces.first;
857         while(efa) {
858                 nextfa= efa->next;
859                 if(efa->f & SELECT) {
860                         BLI_remlink(&em->faces, efa);
861                         free_editface(efa);
862                 }
863                 efa= nextfa;
864         }
865
866         /* step 4: redo selection */
867         EM_clear_flag_all(SELECT);
868         
869         for(eve= em->verts.first; eve; eve= eve->next) {
870                 if(eve->f1)  eve->f |= SELECT;
871         }
872         
873         EM_select_flush();
874         
875         return 'n';
876 }
877
878
879 /* extrudes individual edges */
880 /* nor is filled with constraint vector */
881 short extrudeflag_edges_indiv(short flag, float *nor) 
882 {
883         EditMesh *em = G.editMesh;
884         EditVert *eve;
885         EditEdge *eed;
886         EditFace *efa;
887         
888         for(eve= em->verts.first; eve; eve= eve->next) eve->tmp.v = NULL;
889         for(eed= em->edges.first; eed; eed= eed->next) {
890                 eed->tmp.f = NULL;
891                 eed->f2= ((eed->f & flag)!=0);
892         }
893         
894         set_edge_directions_f2(2);
895
896         /* sample for next loop */
897         for(efa= em->faces.first; efa; efa= efa->next) {
898                 efa->e1->tmp.f = efa;
899                 efa->e2->tmp.f = efa;
900                 efa->e3->tmp.f = efa;
901                 if(efa->e4) efa->e4->tmp.f = efa;
902         }
903         /* make the faces */
904         for(eed= em->edges.first; eed; eed= eed->next) {
905                 if(eed->f & flag) {
906                         if(eed->v1->tmp.v == NULL){
907                                 eed->v1->tmp.v = addvertlist(eed->v1->co);
908                                 if(eed->v1->totweight){
909                                         eed->v1->tmp.v->dw = MEM_dupallocN(eed->v1->dw);
910                                         eed->v1->tmp.v->totweight = eed->v1->totweight;
911                                 }
912                         }
913                         if(eed->v2->tmp.v == NULL){ 
914                                 eed->v2->tmp.v = addvertlist(eed->v2->co);
915                                 if(eed->v2->totweight){
916                                         eed->v2->tmp.v->dw = MEM_dupallocN(eed->v2->dw);
917                                         eed->v2->tmp.v->totweight = eed->v2->totweight;
918                                 }
919                         }
920                         if(eed->dir==1) 
921                                 addfacelist(eed->v1, eed->v2, 
922                                                         eed->v2->tmp.v, eed->v1->tmp.v, 
923                                                         eed->tmp.f, NULL);
924                         else 
925                                 addfacelist(eed->v2, eed->v1, 
926                                                         eed->v1->tmp.v, eed->v2->tmp.v, 
927                                                         eed->tmp.f, NULL);
928
929                         /* for transform */
930                         if(eed->tmp.f) {
931                                 efa = eed->tmp.f;
932                                 if (efa->f & SELECT) add_normal_aligned(nor, efa->n);
933                         }
934                 }
935         }
936         Normalise(nor);
937         
938         /* set correct selection */
939         EM_clear_flag_all(SELECT);
940         for(eve= em->verts.last; eve; eve= eve->prev) {
941                 if(eve->tmp.v) {
942                         eve->tmp.v->f |= flag;
943                 }
944         }
945
946         for(eed= em->edges.first; eed; eed= eed->next) {
947                 if(eed->v1->f & eed->v2->f & flag) eed->f |= flag;
948         }
949         
950         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // g is grab
951         return 'n';  // n is for normal constraint
952 }
953
954 /* extrudes individual vertices */
955 short extrudeflag_verts_indiv(short flag, float *nor) 
956 {
957         EditMesh *em = G.editMesh;
958         EditVert *eve;
959         
960         /* make the edges */
961         for(eve= em->verts.first; eve; eve= eve->next) {
962                 if(eve->f & flag) {
963                         eve->tmp.v = addvertlist(eve->co);
964                         if(eve->totweight){
965                                 eve->tmp.v->dw = MEM_dupallocN(eve->dw);
966                                 eve->tmp.v->totweight = eve->totweight;
967                         }
968                         addedgelist(eve, eve->tmp.v, NULL);
969                 }
970                 else eve->tmp.v = NULL;
971         }
972         
973         /* set correct selection */
974         EM_clear_flag_all(SELECT);
975
976         for(eve= em->verts.last; eve; eve= eve->prev) 
977                 if (eve->tmp.v) 
978                         eve->tmp.v->f |= flag;
979
980         return 'g';     // g is grab
981 }
982
983
984 /* this is actually a recode of extrudeflag(), using proper edge/face select */
985 /* hurms, doesnt use 'flag' yet, but its not called by primitive making stuff anyway */
986 static short extrudeflag_edge(short flag, float *nor)
987 {
988         /* all select edges/faces: extrude */
989         /* old select is cleared, in new ones it is set */
990         EditMesh *em = G.editMesh;
991         EditVert *eve, *nextve;
992         EditEdge *eed, *nexted;
993         EditFace *efa, *nextfa;
994         short del_old= 0;
995         ModifierData *md;
996         
997         if(G.obedit==0 || get_mesh(G.obedit)==0) return 0;
998
999         md = G.obedit->modifiers.first;
1000         
1001         /* selected edges with 0 or 1 selected face become faces */
1002         /* selected faces generate new faces */
1003
1004         /* if *one* selected face has edge with unselected face; remove old selected faces */
1005         
1006         /* if selected edge is not used anymore; remove */
1007         /* if selected vertex is not used anymore: remove */
1008         
1009         /* select the new extrusion, deselect old */
1010         
1011         
1012         /* step 1; init, count faces in edges */
1013         recalc_editnormals();
1014         
1015         for(eve= em->verts.first; eve; eve= eve->next) {
1016                 eve->tmp.v = NULL;
1017                 eve->f1= 0;
1018         }
1019
1020         for(eed= em->edges.first; eed; eed= eed->next) {
1021                 eed->f1= 0; // amount of unselected faces
1022                 eed->f2= 0; // amount of selected faces
1023                 if(eed->f & SELECT) {
1024                         eed->v1->f1= 1; // we call this 'selected vertex' now
1025                         eed->v2->f1= 1;
1026                 }
1027                 eed->tmp.f = NULL;              // here we tuck face pointer, as sample
1028         }
1029         for(efa= em->faces.first; efa; efa= efa->next) {
1030                 if(efa->f & SELECT) {
1031                         efa->e1->f2++;
1032                         efa->e2->f2++;
1033                         efa->e3->f2++;
1034                         if(efa->e4) efa->e4->f2++;
1035                         
1036                         // sample for next loop
1037                         efa->e1->tmp.f = efa;
1038                         efa->e2->tmp.f = efa;
1039                         efa->e3->tmp.f = efa;
1040                         if(efa->e4) efa->e4->tmp.f = efa;
1041                 }
1042                 else {
1043                         efa->e1->f1++;
1044                         efa->e2->f1++;
1045                         efa->e3->f1++;
1046                         if(efa->e4) efa->e4->f1++;
1047                 }
1048         }
1049         
1050         /* If a mirror modifier with clipping is on, we need to adjust some 
1051          * of the cases above to handle edges on the line of symmetry.
1052          */
1053         for (; md; md=md->next) {
1054                 if (md->type==eModifierType_Mirror) {
1055                         MirrorModifierData *mmd = (MirrorModifierData*) md;     
1056                 
1057                         if(mmd->flag & MOD_MIR_CLIPPING) {
1058                                 for (eed= em->edges.first; eed; eed= eed->next) {
1059                                         if(eed->f2 == 1) {
1060
1061                                                 switch(mmd->axis){
1062                                                         case 0:
1063                                                                 if ( (fabs(eed->v1->co[0]) < mmd->tolerance) &&
1064                                                                          (fabs(eed->v2->co[0]) < mmd->tolerance) )
1065                                                                         ++eed->f2;
1066                                                                 break;
1067                                                         case 1:
1068                                                                 if ( (fabs(eed->v1->co[1]) < mmd->tolerance) &&
1069                                                                          (fabs(eed->v2->co[1]) < mmd->tolerance) )
1070                                                                         ++eed->f2;
1071                                                                 break;
1072                                                         case 2:
1073                                                                 if ( (fabs(eed->v1->co[2]) < mmd->tolerance) &&
1074                                                                          (fabs(eed->v2->co[2]) < mmd->tolerance) )
1075                                                                         ++eed->f2;
1076                                                                 break;
1077                                                 }
1078                                         }
1079                                 }
1080                         }
1081                 }
1082         }
1083
1084         set_edge_directions_f2(2);
1085         
1086         /* step 1.5: if *one* selected face has edge with unselected face; remove old selected faces */
1087         for(efa= em->faces.last; efa; efa= efa->prev) {
1088                 if(efa->f & SELECT) {
1089                         if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1 || (efa->e4 && efa->e4->f1)) {
1090                                 del_old= 1;
1091                                 break;
1092                         }
1093                 }
1094         }
1095                                 
1096         /* step 2: make new faces from edges */
1097         for(eed= em->edges.last; eed; eed= eed->prev) {
1098                 if(eed->f & SELECT) {
1099                         if(eed->f2<2) {
1100                                 if(eed->v1->tmp.v == NULL){
1101                                         eed->v1->tmp.v = addvertlist(eed->v1->co);
1102                                         if(eed->v1->totweight){
1103                                                 eed->v1->tmp.v->dw = MEM_dupallocN(eed->v1->dw);
1104                                                 eed->v1->tmp.v->totweight = eed->v1->totweight;
1105                                         }
1106                                 }
1107                                 if(eed->v2->tmp.v == NULL){
1108                                         eed->v2->tmp.v = addvertlist(eed->v2->co);
1109                                         if(eed->v2->totweight){
1110                                                 eed->v2->tmp.v->dw = MEM_dupallocN(eed->v2->dw);
1111                                                 eed->v2->tmp.v->totweight = eed->v2->totweight;
1112                                         }
1113                                 }       
1114                                 /* if del_old, the preferred normal direction is exact 
1115                                  * opposite as for keep old faces
1116                                  */
1117                                 if(eed->dir!=del_old) 
1118                                         addfacelist(eed->v1, eed->v2, 
1119                                                                 eed->v2->tmp.v, eed->v1->tmp.v, 
1120                                                                 eed->tmp.f, NULL);
1121                                 else 
1122                                         addfacelist(eed->v2, eed->v1, 
1123                                                                 eed->v1->tmp.v, eed->v2->tmp.v,
1124                                                                 eed->tmp.f, NULL);
1125                         }
1126                 }
1127         }
1128         
1129         /* step 3: make new faces from faces */
1130         for(efa= em->faces.last; efa; efa= efa->prev) {
1131                 if(efa->f & SELECT) {
1132                         if (efa->v1->tmp.v == NULL){ 
1133                                 efa->v1->tmp.v = addvertlist(efa->v1->co);
1134                                 if(efa->v1->totweight){
1135                                         efa->v1->tmp.v->dw = MEM_dupallocN(efa->v1->dw);
1136                                         efa->v1->tmp.v->totweight = efa->v1->totweight;
1137                                 }
1138                         }
1139                         if (efa->v2->tmp.v ==NULL){
1140                                 efa->v2->tmp.v = addvertlist(efa->v2->co);
1141                                 if(efa->v2->totweight){
1142                                         efa->v2->tmp.v->dw = MEM_dupallocN(efa->v2->dw);
1143                                         efa->v2->tmp.v->totweight = efa->v2->totweight;
1144                                 }
1145                         }
1146                         if (efa->v3->tmp.v ==NULL){ 
1147                                 efa->v3->tmp.v = addvertlist(efa->v3->co);
1148                                 if(efa->v3->totweight){
1149                                         efa->v3->tmp.v->dw = MEM_dupallocN(efa->v3->dw);
1150                                         efa->v3->tmp.v->totweight = efa->v3->totweight;
1151                                 }
1152                         }
1153                         if (efa->v4 && (efa->v4->tmp.v == NULL)){ 
1154                                 efa->v4->tmp.v = addvertlist(efa->v4->co);
1155                                 if(efa->v4->totweight){
1156                                         efa->v4->tmp.v->dw = MEM_dupallocN(efa->v4->dw);
1157                                         efa->v4->tmp.v->totweight = efa->v4->totweight;
1158                                 }
1159                         }
1160                         
1161                         if(del_old==0) {        // keep old faces means flipping normal
1162                                 if(efa->v4)
1163                                         addfacelist(efa->v4->tmp.v, efa->v3->tmp.v, 
1164                                                                 efa->v2->tmp.v, efa->v1->tmp.v, efa, efa);
1165                                 else
1166                                         addfacelist(efa->v3->tmp.v, efa->v2->tmp.v, 
1167                                                                 efa->v1->tmp.v, NULL, efa, efa);
1168                         }
1169                         else {
1170                                 if(efa->v4)
1171                                         addfacelist(efa->v1->tmp.v, efa->v2->tmp.v, 
1172                                                                 efa->v3->tmp.v, efa->v4->tmp.v, efa, efa);
1173                                 else
1174                                         addfacelist(efa->v1->tmp.v, efa->v2->tmp.v, 
1175                                                                 efa->v3->tmp.v, NULL, efa, efa);
1176                         }
1177         
1178                         /* for transform */
1179                         add_normal_aligned(nor, efa->n);
1180                 }
1181         }
1182         
1183         if(del_old) {
1184                 /* step 4: remove old faces, if del_old */
1185                 efa= em->faces.first;
1186                 while(efa) {
1187                         nextfa= efa->next;
1188                         if(efa->f & SELECT) {
1189                                 BLI_remlink(&em->faces, efa);
1190                                 free_editface(efa);
1191                         }
1192                         efa= nextfa;
1193                 }
1194         
1195                 /* step 5: remove selected unused edges */
1196                 /* start tagging again */
1197                 for(eed= em->edges.first; eed; eed= eed->next) eed->f1=0;
1198                 for(efa= em->faces.first; efa; efa= efa->next) {
1199                         efa->e1->f1= 1;
1200                         efa->e2->f1= 1;
1201                         efa->e3->f1= 1;
1202                         if(efa->e4) efa->e4->f1= 1;
1203                 }
1204                 /* remove */
1205                 eed= em->edges.first; 
1206                 while(eed) {
1207                         nexted= eed->next;
1208                         if(eed->f & SELECT) {
1209                                 if(eed->f1==0) {
1210                                         remedge(eed);
1211                                         free_editedge(eed);
1212                                 }
1213                         }
1214                         eed= nexted;
1215                 }
1216         
1217                 /* step 6: remove selected unused vertices */
1218                 for(eed= em->edges.first; eed; eed= eed->next) 
1219                         eed->v1->f1= eed->v2->f1= 0;
1220                 
1221                 eve= em->verts.first;
1222                 while(eve) {
1223                         nextve= eve->next;
1224                         if(eve->f1) {
1225                                 // hack... but we need it for step 7, redoing selection
1226                                 if(eve->tmp.v) eve->tmp.v->tmp.v= eve->tmp.v;
1227                                 
1228                                 BLI_remlink(&em->verts, eve);
1229                                 free_editvert(eve);
1230                         }
1231                         eve= nextve;
1232                 }
1233         }
1234         
1235         Normalise(nor); // translation normal grab
1236         
1237         /* step 7: redo selection */
1238         EM_clear_flag_all(SELECT);
1239
1240         for(eve= em->verts.first; eve; eve= eve->next) {
1241                 if(eve->tmp.v) {
1242                         eve->tmp.v->f |= SELECT;
1243                 }
1244         }
1245
1246         EM_select_flush();
1247
1248         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // grab
1249         return 'n'; // normal constraint 
1250 }
1251
1252 short extrudeflag_vert(short flag, float *nor)
1253 {
1254         /* all verts/edges/faces with (f & 'flag'): extrude */
1255         /* from old verts, 'flag' is cleared, in new ones it is set */
1256         EditMesh *em = G.editMesh;
1257         EditVert *eve, *v1, *v2, *v3, *v4, *nextve;
1258         EditEdge *eed, *e1, *e2, *e3, *e4, *nexted;
1259         EditFace *efa, *efa2, *nextvl;
1260         short sel=0, del_old= 0, is_face_sel=0;
1261         ModifierData *md;
1262
1263         if(G.obedit==0 || get_mesh(G.obedit)==0) return 0;
1264
1265         md = G.obedit->modifiers.first;
1266
1267         /* clear vert flag f1, we use this to detect a loose selected vertice */
1268         eve= em->verts.first;
1269         while(eve) {
1270                 if(eve->f & flag) eve->f1= 1;
1271                 else eve->f1= 0;
1272                 eve= eve->next;
1273         }
1274         /* clear edges counter flag, if selected we set it at 1 */
1275         eed= em->edges.first;
1276         while(eed) {
1277                 if( (eed->v1->f & flag) && (eed->v2->f & flag) ) {
1278                         eed->f2= 1;
1279                         eed->v1->f1= 0;
1280                         eed->v2->f1= 0;
1281                 }
1282                 else eed->f2= 0;
1283                 
1284                 eed->f1= 1;             /* this indicates it is an 'old' edge (in this routine we make new ones) */
1285                 eed->tmp.f = NULL;      /* used as sample */
1286                 
1287                 eed= eed->next;
1288         }
1289
1290         /* we set a flag in all selected faces, and increase the associated edge counters */
1291
1292         efa= em->faces.first;
1293         while(efa) {
1294                 efa->f1= 0;
1295
1296                 if(faceselectedAND(efa, flag)) {
1297                         e1= efa->e1;
1298                         e2= efa->e2;
1299                         e3= efa->e3;
1300                         e4= efa->e4;
1301
1302                         if(e1->f2 < 3) e1->f2++;
1303                         if(e2->f2 < 3) e2->f2++;
1304                         if(e3->f2 < 3) e3->f2++;
1305                         if(e4 && e4->f2 < 3) e4->f2++;
1306                         
1307                         efa->f1= 1;
1308                         is_face_sel= 1; // for del_old
1309                 }
1310                 else if(faceselectedOR(efa, flag)) {
1311                         e1= efa->e1;
1312                         e2= efa->e2;
1313                         e3= efa->e3;
1314                         e4= efa->e4;
1315                         
1316                         if( (e1->v1->f & flag) && (e1->v2->f & flag) ) e1->f1= 2;
1317                         if( (e2->v1->f & flag) && (e2->v2->f & flag) ) e2->f1= 2;
1318                         if( (e3->v1->f & flag) && (e3->v2->f & flag) ) e3->f1= 2;
1319                         if( e4 && (e4->v1->f & flag) && (e4->v2->f & flag) ) e4->f1= 2;
1320                 }
1321                 
1322                 // sample for next loop
1323                 efa->e1->tmp.f = efa;
1324                 efa->e2->tmp.f = efa;
1325                 efa->e3->tmp.f = efa;
1326                 if(efa->e4) efa->e4->tmp.f = efa;
1327
1328                 efa= efa->next;
1329         }
1330
1331         set_edge_directions_f2(3);
1332
1333         /* the current state now is:
1334                 eve->f1==1: loose selected vertex 
1335
1336                 eed->f2==0 : edge is not selected, no extrude
1337                 eed->f2==1 : edge selected, is not part of a face, extrude
1338                 eed->f2==2 : edge selected, is part of 1 face, extrude
1339                 eed->f2==3 : edge selected, is part of more faces, no extrude
1340                 
1341                 eed->f1==0: new edge
1342                 eed->f1==1: edge selected, is part of selected face, when eed->f==3: remove
1343                 eed->f1==2: edge selected, part of a partially selected face
1344                                         
1345                 efa->f1==1 : duplicate this face
1346         */
1347
1348         /* If a mirror modifier with clipping is on, we need to adjust some 
1349          * of the cases above to handle edges on the line of symmetry.
1350          */
1351         for (; md; md=md->next) {
1352                 if (md->type==eModifierType_Mirror) {
1353                         MirrorModifierData *mmd = (MirrorModifierData*) md;     
1354                 
1355                         if(mmd->flag & MOD_MIR_CLIPPING) {
1356                                 for (eed= em->edges.first; eed; eed= eed->next) {
1357                                         if(eed->f2 == 2) {
1358
1359                                                 switch(mmd->axis){
1360                                                         case 0:
1361                                                                 if ( (fabs(eed->v1->co[0]) < mmd->tolerance) &&
1362                                                                          (fabs(eed->v2->co[0]) < mmd->tolerance) )
1363                                                                         ++eed->f2;
1364                                                                 break;
1365                                                         case 1:
1366                                                                 if ( (fabs(eed->v1->co[1]) < mmd->tolerance) &&
1367                                                                          (fabs(eed->v2->co[1]) < mmd->tolerance) )
1368                                                                         ++eed->f2;
1369                                                                 break;
1370                                                         case 2:
1371                                                                 if ( (fabs(eed->v1->co[2]) < mmd->tolerance) &&
1372                                                                          (fabs(eed->v2->co[2]) < mmd->tolerance) )
1373                                                                         ++eed->f2;
1374                                                                 break;
1375                                                 }
1376                                         }
1377                                 }
1378                         }
1379                 }
1380         }
1381
1382         /* copy all selected vertices, */
1383         /* write pointer to new vert in old struct at eve->tmp.v */
1384         eve= em->verts.last;
1385         while(eve) {
1386                 eve->f &= ~128;  /* clear, for later test for loose verts */
1387                 if(eve->f & flag) {
1388                         sel= 1;
1389                         v1= addvertlist(0);
1390                         
1391                         VECCOPY(v1->co, eve->co);
1392                         v1->f= eve->f;
1393                         eve->f-= flag;
1394                         eve->tmp.v = v1;
1395                 }
1396                 else eve->tmp.v = 0;
1397                 eve= eve->prev;
1398         }
1399
1400         if(sel==0) return 0;
1401
1402         /* all edges with eed->f2==1 or eed->f2==2 become faces */
1403         
1404         /* if del_old==1 then extrude is in partial geometry, to keep it manifold.
1405                                          verts with f1==0 and (eve->f & 128)==0) are removed
1406                          edges with eed->f2>2 are removed
1407                                          faces with efa->f1 are removed
1408            if del_old==0 the extrude creates a volume.
1409         */
1410         
1411          /* find if we delete old faces */
1412         if(is_face_sel) {
1413                 for(eed= em->edges.first; eed; eed= eed->next) {
1414                         if( (eed->f2==1 || eed->f2==2) ) {
1415                                 if(eed->f1==2) {
1416                                         del_old= 1;
1417                                         break;
1418                                 }
1419                         }
1420                 }
1421         }
1422         
1423         eed= em->edges.last;
1424         while(eed) {
1425                 nexted= eed->prev;
1426                 if( eed->f2<3) {
1427                         eed->v1->f |= 128;  /* = no loose vert! */
1428                         eed->v2->f |= 128;
1429                 }
1430                 if( (eed->f2==1 || eed->f2==2) ) {
1431         
1432                         /* if del_old, the preferred normal direction is exact opposite as for keep old faces */
1433                         if(eed->dir != del_old) 
1434                                 efa2 = addfacelist(eed->v1, eed->v2, 
1435                                                                   eed->v2->tmp.v, eed->v1->tmp.v, 
1436                                                                   NULL, NULL);
1437                         else 
1438                                 efa2 = addfacelist(eed->v2, eed->v1, 
1439                                                                    eed->v1->tmp.v, eed->v2->tmp.v, 
1440                                                                    NULL, NULL);
1441                         
1442                         if(eed->tmp.f) {
1443                                 efa = eed->tmp.f;
1444                                 efa2->mat_nr= efa->mat_nr;
1445                                 efa2->tf= efa->tf;
1446                                 efa2->flag= efa->flag;
1447                         }
1448                         
1449                         /* Needs smarter adaption of existing creases.
1450                          * If addedgelist is used, make sure seams are set to 0 on these
1451                          * new edges, since we do not want to add any seams on extrusion.
1452                          */
1453                         efa2->e1->crease= eed->crease;
1454                         efa2->e2->crease= eed->crease;
1455                         efa2->e3->crease= eed->crease;
1456                         if(efa2->e4) efa2->e4->crease= eed->crease;
1457                 }
1458
1459                 eed= nexted;
1460         }
1461         if(del_old) {
1462                 eed= em->edges.first;
1463                 while(eed) {
1464                         nexted= eed->next;
1465                         if(eed->f2==3 && eed->f1==1) {
1466                                 remedge(eed);
1467                                 free_editedge(eed);
1468                         }
1469                         eed= nexted;
1470                 }
1471         }
1472         /* duplicate faces, if necessary remove old ones  */
1473         efa= em->faces.first;
1474         while(efa) {
1475                 nextvl= efa->next;
1476                 if(efa->f1 & 1) {
1477                 
1478                         v1 = efa->v1->tmp.v;
1479                         v2 = efa->v2->tmp.v;
1480                         v3 = efa->v3->tmp.v;
1481                         if(efa->v4) 
1482                                 v4 = efa->v4->tmp.v; 
1483                         else
1484                                 v4= 0;
1485
1486                         /* hmm .. not sure about edges here */
1487                         if(del_old==0)  // if we keep old, we flip normal
1488                                 efa2= addfacelist(v3, v2, v1, v4, efa, efa); 
1489                         else
1490                                 efa2= addfacelist(v1, v2, v3, v4, efa, efa);
1491                         
1492                         /* for transform */
1493                         add_normal_aligned(nor, efa->n);
1494
1495                         if(del_old) {
1496                                 BLI_remlink(&em->faces, efa);
1497                                 free_editface(efa);
1498                         }
1499                 }
1500                 efa= nextvl;
1501         }
1502         
1503         Normalise(nor); // for grab
1504         
1505         /* for all vertices with eve->tmp.v!=0 
1506                 if eve->f1==1: make edge
1507                 if flag!=128 : if del_old==1: remove
1508         */
1509         eve= em->verts.last;
1510         while(eve) {
1511                 nextve= eve->prev;
1512                 if(eve->tmp.v) {
1513                         if(eve->f1==1) addedgelist(eve, eve->tmp.v, NULL);
1514                         else if( (eve->f & 128)==0) {
1515                                 if(del_old) {
1516                                         BLI_remlink(&em->verts,eve);
1517                                         free_editvert(eve);
1518                                         eve= NULL;
1519                                 }
1520                         }
1521                 }
1522                 if(eve) {
1523                         eve->f &= ~128;
1524                 }
1525                 eve= nextve;
1526         }
1527         // since its vertex select mode now, it also deselects higher order
1528         EM_selectmode_flush();
1529
1530         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // g is grab, for correct undo print
1531         return 'n';
1532 }
1533
1534 /* generic extrude */
1535 short extrudeflag(short flag, float *nor)
1536 {
1537         if(G.scene->selectmode & SCE_SELECT_VERTEX)
1538                 return extrudeflag_vert(flag, nor);
1539         else 
1540                 return extrudeflag_edge(flag, nor);
1541                 
1542 }
1543
1544 void rotateflag(short flag, float *cent, float rotmat[][3])
1545 {
1546         /* all verts with (flag & 'flag') rotate */
1547         EditMesh *em = G.editMesh;
1548         EditVert *eve;
1549
1550         eve= em->verts.first;
1551         while(eve) {
1552                 if(eve->f & flag) {
1553                         eve->co[0]-=cent[0];
1554                         eve->co[1]-=cent[1];
1555                         eve->co[2]-=cent[2];
1556                         Mat3MulVecfl(rotmat,eve->co);
1557                         eve->co[0]+=cent[0];
1558                         eve->co[1]+=cent[1];
1559                         eve->co[2]+=cent[2];
1560                 }
1561                 eve= eve->next;
1562         }
1563 }
1564
1565 void translateflag(short flag, float *vec)
1566 {
1567         /* all verts with (flag & 'flag') translate */
1568         EditMesh *em = G.editMesh;
1569         EditVert *eve;
1570
1571         eve= em->verts.first;
1572         while(eve) {
1573                 if(eve->f & flag) {
1574                         eve->co[0]+=vec[0];
1575                         eve->co[1]+=vec[1];
1576                         eve->co[2]+=vec[2];
1577                 }
1578                 eve= eve->next;
1579         }
1580 }
1581
1582 /* helper call for below */
1583 static EditVert *adduplicate_vertex(EditVert *eve, int flag)
1584 {
1585         EditVert *v1= addvertlist(eve->co);
1586         
1587         v1->f= eve->f;
1588         eve->f-= flag;
1589         eve->f|= 128;
1590         
1591         eve->tmp.v = v1;
1592         
1593         /* FIXME: Copy deformation weight ? */
1594         v1->totweight = eve->totweight;
1595         if (eve->totweight){
1596                 v1->dw = MEM_mallocN (eve->totweight * sizeof(MDeformWeight), "deformWeight");
1597                 memcpy (v1->dw, eve->dw, eve->totweight * sizeof(MDeformWeight));
1598         }
1599         else
1600                 v1->dw=NULL;
1601         
1602         return v1;
1603 }
1604
1605 /* old selection has flag 128 set, and flag 'flag' cleared
1606 new selection has flag 'flag' set */
1607 void adduplicateflag(int flag)
1608 {
1609         EditMesh *em = G.editMesh;
1610         EditVert *eve, *v1, *v2, *v3, *v4;
1611         EditEdge *eed, *newed;
1612         EditFace *efa, *newfa;
1613
1614         EM_clear_flag_all(128);
1615         EM_selectmode_set();    // paranoia check, selection now is consistant
1616
1617         /* vertices first */
1618         for(eve= em->verts.last; eve; eve= eve->prev) {
1619
1620                 if(eve->f & flag)
1621                         adduplicate_vertex(eve, flag);
1622                 else 
1623                         eve->tmp.v = NULL;
1624         }
1625         
1626         /* copy edges, note that vertex selection can be independent of edge */
1627         for(eed= em->edges.last; eed; eed= eed->prev) {
1628                 if( eed->f & flag ) {
1629                         v1 = eed->v1->tmp.v;
1630                         if(v1==NULL) v1= adduplicate_vertex(eed->v1, flag);
1631                         v2 = eed->v2->tmp.v;
1632                         if(v2==NULL) v2= adduplicate_vertex(eed->v2, flag);
1633                         
1634                         newed= addedgelist(v1, v2, eed);
1635                         
1636                         newed->f= eed->f;
1637                         eed->f -= flag;
1638                         eed->f |= 128;
1639                 }
1640         }
1641
1642         /* then duplicate faces, again create new vertices if needed */
1643         for(efa= em->faces.last; efa; efa= efa->prev) {
1644                 if(efa->f & flag) {
1645                         v1 = efa->v1->tmp.v;
1646                         if(v1==NULL) v1= adduplicate_vertex(efa->v1, flag);
1647                         v2 = efa->v2->tmp.v;
1648                         if(v2==NULL) v2= adduplicate_vertex(efa->v2, flag);
1649                         v3 = efa->v3->tmp.v;
1650                         if(v3==NULL) v3= adduplicate_vertex(efa->v3, flag);
1651                         if(efa->v4) {
1652                                 v4 = efa->v4->tmp.v; 
1653                                 if(v4==NULL) v4= adduplicate_vertex(efa->v4, flag);
1654                         }
1655                         else v4= NULL;
1656                         
1657                         newfa= addfacelist(v1, v2, v3, v4, efa, efa); 
1658                         
1659                         newfa->f= efa->f;
1660                         efa->f -= flag;
1661                         efa->f |= 128;
1662                 }
1663         }
1664         
1665         EM_fgon_flags();        // redo flags and indices for fgons
1666 }
1667
1668 void delfaceflag(int flag)
1669 {
1670         EditMesh *em = G.editMesh;
1671         /* delete all faces with 'flag', including loose edges and loose vertices */
1672         /* this is maybe a bit weird, but this function is used for 'split' and 'separate' */
1673         /* in remaining vertices/edges 'flag' is cleared */
1674         EditVert *eve,*nextve;
1675         EditEdge *eed, *nexted;
1676         EditFace *efa,*nextvl;
1677
1678         /* to detect loose edges, we put f2 flag on 1 */
1679         for(eed= em->edges.first; eed; eed= eed->next) {
1680                 if(eed->f & flag) eed->f2= 1;
1681                 else eed->f2= 0;
1682         }
1683         
1684         /* delete faces */
1685         efa= em->faces.first;
1686         while(efa) {
1687                 nextvl= efa->next;
1688                 if(efa->f & flag) {
1689                         
1690                         efa->e1->f2= 1;
1691                         efa->e2->f2= 1;
1692                         efa->e3->f2= 1;
1693                         if(efa->e4) {
1694                                 efa->e4->f2= 1;
1695                         }
1696                                                                 
1697                         BLI_remlink(&em->faces, efa);
1698                         free_editface(efa);
1699                 }
1700                 efa= nextvl;
1701         }
1702         
1703         /* all remaining faces: make sure we keep the edges */
1704         for(efa= em->faces.first; efa; efa= efa->next) {
1705                 efa->e1->f2= 0;
1706                 efa->e2->f2= 0;
1707                 efa->e3->f2= 0;
1708                 if(efa->e4) {
1709                         efa->e4->f2= 0;
1710                 }
1711         }
1712         
1713         /* remove tagged edges, and clear remaining ones */
1714         eed= em->edges.first;
1715         while(eed) {
1716                 nexted= eed->next;
1717                 
1718                 if(eed->f2==1) {
1719                         remedge(eed);
1720                         free_editedge(eed);
1721                 }
1722                 else {
1723                         eed->f &= ~flag;
1724                         eed->v1->f &= ~flag;
1725                         eed->v2->f &= ~flag;
1726                 }
1727                 eed= nexted;
1728         }
1729         
1730         /* vertices with 'flag' now are the loose ones, and will be removed */
1731         eve= em->verts.first;
1732         while(eve) {
1733                 nextve= eve->next;
1734                 if(eve->f & flag) {
1735                         BLI_remlink(&em->verts, eve);
1736                         free_editvert(eve);
1737                 }
1738                 eve= nextve;
1739         }
1740
1741 }
1742
1743 /* ********************* */
1744 #if 0
1745 static int check_vnormal_flip(float *n, float *vnorm) 
1746 {
1747         float inp;
1748
1749         inp= n[0]*vnorm[0]+n[1]*vnorm[1]+n[2]*vnorm[2];
1750
1751         /* angles 90 degrees: dont flip */
1752         if(inp> -0.000001) return 0;
1753
1754         return 1;
1755 }
1756 #endif
1757
1758 void flipface(EditFace *efa)
1759 {
1760         if(efa->v4) {
1761                 SWAP(EditVert *, efa->v2, efa->v4);
1762                 SWAP(EditEdge *, efa->e1, efa->e4);
1763                 SWAP(EditEdge *, efa->e2, efa->e3);
1764                 SWAP(unsigned int, efa->tf.col[1], efa->tf.col[3]);
1765                 SWAP(float, efa->tf.uv[1][0], efa->tf.uv[3][0]);
1766                 SWAP(float, efa->tf.uv[1][1], efa->tf.uv[3][1]);
1767         }
1768         else {
1769                 SWAP(EditVert *, efa->v2, efa->v3);
1770                 SWAP(EditEdge *, efa->e1, efa->e3);
1771                 SWAP(unsigned int, efa->tf.col[1], efa->tf.col[2]);
1772                 efa->e2->dir= 1-efa->e2->dir;
1773                 SWAP(float, efa->tf.uv[1][0], efa->tf.uv[2][0]);
1774                 SWAP(float, efa->tf.uv[1][1], efa->tf.uv[2][1]);
1775         }
1776         if(efa->v4) CalcNormFloat4(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co, efa->n);
1777         else CalcNormFloat(efa->v1->co, efa->v2->co, efa->v3->co, efa->n);
1778 }
1779
1780
1781 void flip_editnormals(void)
1782 {
1783         EditMesh *em = G.editMesh;
1784         EditFace *efa;
1785         
1786         efa= em->faces.first;
1787         while(efa) {
1788                 if( efa->f & SELECT ){
1789                         flipface(efa);
1790                 }
1791                 efa= efa->next;
1792         }
1793 #ifdef WITH_VERSE
1794         if(G.editMesh->vnode)
1795                 sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
1796 #endif
1797 }
1798
1799 /* does face centers too */
1800 void recalc_editnormals(void)
1801 {
1802         EditMesh *em = G.editMesh;
1803         EditFace *efa;
1804         EditVert *eve;
1805
1806         for(eve= em->verts.first; eve; eve=eve->next) {
1807                 eve->no[0] = eve->no[1] = eve->no[2] = 0.0;
1808         }
1809
1810         for(efa= em->faces.first; efa; efa=efa->next) {
1811                 if(efa->v4) {
1812                         CalcNormFloat4(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co, efa->n);
1813                         CalcCent4f(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
1814                         VecAddf(efa->v4->no, efa->v4->no, efa->n);
1815                 }
1816                 else {
1817                         CalcNormFloat(efa->v1->co, efa->v2->co, efa->v3->co, efa->n);
1818                         CalcCent3f(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co);
1819                 }
1820                 VecAddf(efa->v1->no, efa->v1->no, efa->n);
1821                 VecAddf(efa->v2->no, efa->v2->no, efa->n);
1822                 VecAddf(efa->v3->no, efa->v3->no, efa->n);
1823         }
1824
1825         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
1826         for(eve= em->verts.first; eve; eve=eve->next) {
1827                 if (Normalise(eve->no)==0.0) {
1828                         VECCOPY(eve->no, eve->co);
1829                         Normalise(eve->no);
1830                 }
1831         }
1832 }
1833
1834 int compareface(EditFace *vl1, EditFace *vl2)
1835 {
1836         EditVert *v1, *v2, *v3, *v4;
1837         
1838         if(vl1->v4 && vl2->v4) {
1839                 v1= vl2->v1;
1840                 v2= vl2->v2;
1841                 v3= vl2->v3;
1842                 v4= vl2->v4;
1843                 
1844                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1 || vl1->v4==v1) {
1845                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2 || vl1->v4==v2) {
1846                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3 || vl1->v4==v3) {
1847                                         if(vl1->v1==v4 || vl1->v2==v4 || vl1->v3==v4 || vl1->v4==v4) {
1848                                                 return 1;
1849                                         }
1850                                 }
1851                         }
1852                 }
1853         }
1854         else if(vl1->v4==0 && vl2->v4==0) {
1855                 v1= vl2->v1;
1856                 v2= vl2->v2;
1857                 v3= vl2->v3;
1858                 
1859                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1) {
1860                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2) {
1861                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3) {
1862                                         return 1;
1863                                 }
1864                         }
1865                 }
1866         }
1867         
1868         return 0;
1869 }
1870
1871 /* checks for existance, not tria overlapping inside quad */
1872 EditFace *exist_face(EditVert *v1, EditVert *v2, EditVert *v3, EditVert *v4)
1873 {
1874         EditMesh *em = G.editMesh;
1875         EditFace *efa, efatest;
1876         
1877         efatest.v1= v1;
1878         efatest.v2= v2;
1879         efatest.v3= v3;
1880         efatest.v4= v4;
1881         
1882         efa= em->faces.first;
1883         while(efa) {
1884                 if(compareface(&efatest, efa)) return efa;
1885                 efa= efa->next;
1886         }
1887         return NULL;
1888 }
1889
1890 /* evaluate if entire quad is a proper convex quad */
1891 int convex(float *v1, float *v2, float *v3, float *v4)
1892 {
1893         float nor[3], nor1[3], nor2[3], vec[4][2];
1894         
1895         /* define projection, do both trias apart, quad is undefined! */
1896         CalcNormFloat(v1, v2, v3, nor1);
1897         CalcNormFloat(v1, v3, v4, nor2);
1898         nor[0]= ABS(nor1[0]) + ABS(nor2[0]);
1899         nor[1]= ABS(nor1[1]) + ABS(nor2[1]);
1900         nor[2]= ABS(nor1[2]) + ABS(nor2[2]);
1901
1902         if(nor[2] >= nor[0] && nor[2] >= nor[1]) {
1903                 vec[0][0]= v1[0]; vec[0][1]= v1[1];
1904                 vec[1][0]= v2[0]; vec[1][1]= v2[1];
1905                 vec[2][0]= v3[0]; vec[2][1]= v3[1];
1906                 vec[3][0]= v4[0]; vec[3][1]= v4[1];
1907         }
1908         else if(nor[1] >= nor[0] && nor[1]>= nor[2]) {
1909                 vec[0][0]= v1[0]; vec[0][1]= v1[2];
1910                 vec[1][0]= v2[0]; vec[1][1]= v2[2];
1911                 vec[2][0]= v3[0]; vec[2][1]= v3[2];
1912                 vec[3][0]= v4[0]; vec[3][1]= v4[2];
1913         }
1914         else {
1915                 vec[0][0]= v1[1]; vec[0][1]= v1[2];
1916                 vec[1][0]= v2[1]; vec[1][1]= v2[2];
1917                 vec[2][0]= v3[1]; vec[2][1]= v3[2];
1918                 vec[3][0]= v4[1]; vec[3][1]= v4[2];
1919         }
1920         
1921         /* linetests, the 2 diagonals have to instersect to be convex */
1922         if( IsectLL2Df(vec[0], vec[2], vec[1], vec[3]) > 0 ) return 1;
1923         return 0;
1924 }
1925
1926
1927 /* ********************* Fake Polgon support (FGon) ***************** */
1928
1929
1930 /* results in:
1931    - faces having ->fgonf flag set (also for draw)
1932    - edges having ->fgoni index set (for select)
1933 */
1934
1935 float EM_face_area(EditFace *efa)
1936 {
1937         if(efa->v4) return AreaQ3Dfl(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
1938         else return AreaT3Dfl(efa->v1->co, efa->v2->co, efa->v3->co);
1939 }
1940
1941 float EM_face_perimeter(EditFace *efa)
1942 {       
1943         if(efa->v4) return
1944                 VecLenf(efa->v1->co, efa->v2->co)+
1945                 VecLenf(efa->v2->co, efa->v3->co)+
1946                 VecLenf(efa->v3->co, efa->v4->co)+
1947                 VecLenf(efa->v4->co, efa->v1->co);
1948         
1949         else return
1950                 VecLenf(efa->v1->co, efa->v2->co)+
1951                 VecLenf(efa->v2->co, efa->v3->co)+
1952                 VecLenf(efa->v3->co, efa->v1->co);
1953 }
1954
1955 void EM_fgon_flags(void)
1956 {
1957         EditMesh *em = G.editMesh;
1958         EditFace *efa, *efan, *efamax;
1959         EditEdge *eed;
1960         ListBase listb={NULL, NULL};
1961         float size, maxsize;
1962         short done, curindex= 1;
1963         
1964         // for each face with fgon edge AND not fgon flag set
1965         for(eed= em->edges.first; eed; eed= eed->next) eed->fgoni= 0;  // index
1966         for(efa= em->faces.first; efa; efa= efa->next) efa->fgonf= 0;  // flag
1967         
1968         // for speed & simplicity, put fgon face candidates in new listbase
1969         efa= em->faces.first;
1970         while(efa) {
1971                 efan= efa->next;
1972                 if( (efa->e1->h & EM_FGON) || (efa->e2->h & EM_FGON) || 
1973                         (efa->e3->h & EM_FGON) || (efa->e4 && (efa->e4->h & EM_FGON)) ) {
1974                         BLI_remlink(&em->faces, efa);
1975                         BLI_addtail(&listb, efa);
1976                 }
1977                 efa= efan;
1978         }
1979         
1980         // find an undone face with fgon edge
1981         for(efa= listb.first; efa; efa= efa->next) {
1982                 if(efa->fgonf==0) {
1983                         
1984                         // init this face
1985                         efa->fgonf= EM_FGON;
1986                         if(efa->e1->h & EM_FGON) efa->e1->fgoni= curindex;
1987                         if(efa->e2->h & EM_FGON) efa->e2->fgoni= curindex;
1988                         if(efa->e3->h & EM_FGON) efa->e3->fgoni= curindex;
1989                         if(efa->e4 && (efa->e4->h & EM_FGON)) efa->e4->fgoni= curindex;
1990                         
1991                         // we search for largest face, to give facedot drawing rights
1992                         maxsize= EM_face_area(efa);
1993                         efamax= efa;
1994                         
1995                         // now flush curendex over edges and set faceflags
1996                         done= 1;
1997                         while(done==1) {
1998                                 done= 0;
1999                                 
2000                                 for(efan= listb.first; efan; efan= efan->next) {
2001                                         if(efan->fgonf==0) {
2002                                                 // if one if its edges has index set, do other too
2003                                                 if( (efan->e1->fgoni==curindex) || (efan->e2->fgoni==curindex) ||
2004                                                         (efan->e3->fgoni==curindex) || (efan->e4 && (efan->e4->fgoni==curindex)) ) {
2005                                                         
2006                                                         efan->fgonf= EM_FGON;
2007                                                         if(efan->e1->h & EM_FGON) efan->e1->fgoni= curindex;
2008                                                         if(efan->e2->h & EM_FGON) efan->e2->fgoni= curindex;
2009                                                         if(efan->e3->h & EM_FGON) efan->e3->fgoni= curindex;
2010                                                         if(efan->e4 && (efan->e4->h & EM_FGON)) efan->e4->fgoni= curindex;
2011                                                         
2012                                                         size= EM_face_area(efan);
2013                                                         if(size>maxsize) {
2014                                                                 efamax= efan;
2015                                                                 maxsize= size;
2016                                                         }
2017                                                         done= 1;
2018                                                 }
2019                                         }
2020                                 }
2021                         }
2022                         
2023                         efamax->fgonf |= EM_FGON_DRAW;
2024                         curindex++;
2025
2026                 }
2027         }
2028
2029         // put fgon face candidates back in listbase
2030         efa= listb.first;
2031         while(efa) {
2032                 efan= efa->next;
2033                 BLI_remlink(&listb, efa);
2034                 BLI_addtail(&em->faces, efa);
2035                 efa= efan;
2036         }
2037         
2038         // remove fgon flags when edge not in fgon (anymore)
2039         for(eed= em->edges.first; eed; eed= eed->next) {
2040                 if(eed->fgoni==0) eed->h &= ~EM_FGON;
2041         }
2042         
2043 }