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