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