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