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