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