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