IRC report:
[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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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_meshdata_types.h"
43 #include "DNA_modifier_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_scene_types.h"
46
47 #include "BLI_blenlib.h"
48 #include "BLI_math.h"
49 #include "BLI_editVert.h"
50 #include "BLI_edgehash.h"
51
52 #include "BKE_customdata.h"
53 #include "BKE_context.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_screen.h"
60 #include "ED_view3d.h"
61 #include "ED_transform.h"
62
63 #include "mesh_intern.h"
64
65 /* Helpers for EM_set_flag_all_selectmode */
66 #define SET_EVE_FLAG(eve, flag) \
67         if (eve->h==0) { \
68                 if (flag & SELECT && !(eve->f & SELECT)) { \
69                         ++selvert; \
70                 } \
71                 eve->f |= flag; \
72         }
73
74 #define SET_EED_FLAG(eed, flag) \
75         if (eed->h==0) { \
76                 if (flag & SELECT && !(eed->f & SELECT)) { \
77                         ++seledge; \
78                 } \
79                 eed->f |= flag; \
80                 SET_EVE_FLAG(eed->v1, flag); \
81                 SET_EVE_FLAG(eed->v2, flag); \
82         }
83
84
85 /* ****************** stats *************** */
86
87 int EM_nfaces_selected(EditMesh *em)
88 {
89         EditFace *efa;
90         int count= 0;
91         
92         for (efa= em->faces.first; efa; efa= efa->next)
93                 if (efa->f & SELECT)
94                         count++;
95         
96         em->totfacesel= count;
97         
98         return count;
99 }
100
101 int EM_nedges_selected(EditMesh *em)
102 {
103         EditEdge *eed;
104         int count= 0;
105         
106         for (eed= em->edges.first; eed; eed= eed->next) 
107                 if(eed->f & SELECT)
108                         count++;
109         
110         em->totedgesel= count;
111         
112         return count;
113 }
114
115 int EM_nvertices_selected(EditMesh *em)
116 {
117         EditVert *eve;
118         int count= 0;
119         
120         for (eve= em->verts.first; eve; eve= eve->next)
121                 if (eve->f & SELECT)
122                         count++;
123         
124         em->totvertsel= count;
125         
126         return count;
127 }
128
129 void EM_stats_update(EditMesh *em)
130 {
131         
132         em->totvert= BLI_countlist(&em->verts);
133         em->totedge= BLI_countlist(&em->edges);
134         em->totface= BLI_countlist(&em->faces);
135         
136         EM_nvertices_selected(em);
137         EM_nedges_selected(em);
138         EM_nfaces_selected(em);
139 }
140
141 /* ************************************** */
142
143 /* this replaces the active flag used in uv/face mode */
144 void EM_set_actFace(EditMesh *em, EditFace *efa)
145 {
146         em->act_face = efa;
147 }
148
149 EditFace *EM_get_actFace(EditMesh *em, int sloppy)
150 {
151         if (em->act_face) {
152                 return em->act_face;
153         } else if (sloppy) {
154                 EditFace *efa= NULL;
155                 EditSelection *ese;
156                 
157                 ese = em->selected.last;
158                 for (; ese; ese=ese->prev){
159                         if(ese->type == EDITFACE) {
160                                 efa = (EditFace *)ese->data;
161                                 
162                                 if (efa->h)     efa= NULL;
163                                 else            break;
164                         }
165                 }
166                 if (efa==NULL) {
167                         for (efa= em->faces.first; efa; efa= efa->next) {
168                                 if (efa->f & SELECT)
169                                         break;
170                         }
171                 }
172                 return efa; /* can still be null */
173         }
174         return NULL;
175 }
176
177 int EM_get_actSelection(EditMesh *em, EditSelection *ese)
178 {
179         EditSelection *ese_last = em->selected.last;
180         EditFace *efa = EM_get_actFace(em, 0);
181
182         ese->next = ese->prev = NULL;
183         
184         if (ese_last) {
185                 if (ese_last->type == EDITFACE) { /* if there is an active face, use it over the last selected face */
186                         if (efa) {
187                                 ese->data = (void *)efa;
188                         } else {
189                                 ese->data = ese_last->data;
190                         }
191                         ese->type = EDITFACE;
192                 } else {
193                         ese->data = ese_last->data;
194                         ese->type = ese_last->type;
195                 }
196         } else if (efa) { /* no */
197                 ese->data = (void *)efa;
198                 ese->type = EDITFACE;
199         } else {
200                 ese->data = NULL;
201                 return 0;
202         }
203         return 1;
204 }
205
206 /* ********* Selection History ************ */
207 static int EM_check_selection(EditMesh *em, void *data)
208 {
209         EditSelection *ese;
210         
211         for(ese = em->selected.first; ese; ese = ese->next){
212                 if(ese->data == data) return 1;
213         }
214         
215         return 0;
216 }
217
218 void EM_remove_selection(EditMesh *em, void *data, int UNUSED(type))
219 {
220         EditSelection *ese;
221         for(ese=em->selected.first; ese; ese = ese->next){
222                 if(ese->data == data){
223                         BLI_freelinkN(&(em->selected),ese);
224                         break;
225                 }
226         }
227 }
228
229 void EM_store_selection(EditMesh *em, void *data, int type)
230 {
231         EditSelection *ese;
232         if(!EM_check_selection(em, data)){
233                 ese = (EditSelection*) MEM_callocN( sizeof(EditSelection), "Edit Selection");
234                 ese->type = type;
235                 ese->data = data;
236                 BLI_addtail(&(em->selected),ese);
237         }
238 }
239
240 void EM_validate_selections(EditMesh *em)
241 {
242         EditSelection *ese, *nextese;
243
244         ese = em->selected.first;
245
246         while(ese){
247                 nextese = ese->next;
248                 if(ese->type == EDITVERT && !(((EditVert*)ese->data)->f & SELECT)) BLI_freelinkN(&(em->selected), ese);
249                 else if(ese->type == EDITEDGE && !(((EditEdge*)ese->data)->f & SELECT)) BLI_freelinkN(&(em->selected), ese);
250                 else if(ese->type == EDITFACE && !(((EditFace*)ese->data)->f & SELECT)) BLI_freelinkN(&(em->selected), ese);
251                 ese = nextese;
252         }
253 }
254
255 static void EM_strip_selections(EditMesh *em)
256 {
257         EditSelection *ese, *nextese;
258         if(!(em->selectmode & SCE_SELECT_VERTEX)){
259                 ese = em->selected.first;
260                 while(ese){
261                         nextese = ese->next; 
262                         if(ese->type == EDITVERT) BLI_freelinkN(&(em->selected),ese);
263                         ese = nextese;
264                 }
265         }
266         if(!(em->selectmode & SCE_SELECT_EDGE)){
267                 ese=em->selected.first;
268                 while(ese){
269                         nextese = ese->next;
270                         if(ese->type == EDITEDGE) BLI_freelinkN(&(em->selected), ese);
271                         ese = nextese;
272                 }
273         }
274         if(!(em->selectmode & SCE_SELECT_FACE)){
275                 ese=em->selected.first;
276                 while(ese){
277                         nextese = ese->next;
278                         if(ese->type == EDITFACE) BLI_freelinkN(&(em->selected), ese);
279                         ese = nextese;
280                 }
281         }
282 }
283
284 /* generic way to get data from an EditSelection type 
285 These functions were written to be used by the Modifier widget when in Rotate about active mode,
286 but can be used anywhere.
287 EM_editselection_center
288 EM_editselection_normal
289 EM_editselection_plane
290 */
291 void EM_editselection_center(float *center, EditSelection *ese)
292 {
293         if (ese->type==EDITVERT) {
294                 EditVert *eve= ese->data;
295                 copy_v3_v3(center, eve->co);
296         } else if (ese->type==EDITEDGE) {
297                 EditEdge *eed= ese->data;
298                 add_v3_v3v3(center, eed->v1->co, eed->v2->co);
299                 mul_v3_fl(center, 0.5);
300         } else if (ese->type==EDITFACE) {
301                 EditFace *efa= ese->data;
302                 copy_v3_v3(center, efa->cent);
303         }
304 }
305
306 void EM_editselection_normal(float *normal, EditSelection *ese)
307 {
308         if (ese->type==EDITVERT) {
309                 EditVert *eve= ese->data;
310                 copy_v3_v3(normal, eve->no);
311         } else if (ese->type==EDITEDGE) {
312                 EditEdge *eed= ese->data;
313                 float plane[3]; /* need a plane to correct the normal */
314                 float vec[3]; /* temp vec storage */
315                 
316                 add_v3_v3v3(normal, eed->v1->no, eed->v2->no);
317                 sub_v3_v3v3(plane, eed->v2->co, eed->v1->co);
318                 
319                 /* the 2 vertex normals will be close but not at rightangles to the edge
320                 for rotate about edge we want them to be at right angles, so we need to
321                 do some extra colculation to correct the vert normals,
322                 we need the plane for this */
323                 cross_v3_v3v3(vec, normal, plane);
324                 cross_v3_v3v3(normal, plane, vec); 
325                 normalize_v3(normal);
326                 
327         } else if (ese->type==EDITFACE) {
328                 EditFace *efa= ese->data;
329                 copy_v3_v3(normal, efa->n);
330         }
331 }
332
333 /* Calculate a plane that is rightangles to the edge/vert/faces normal
334 also make the plane run allong an axis that is related to the geometry,
335 because this is used for the manipulators Y axis.*/
336 void EM_editselection_plane(float *plane, EditSelection *ese)
337 {
338         if (ese->type==EDITVERT) {
339                 EditVert *eve= ese->data;
340                 float vec[3]={0,0,0};
341                 
342                 if (ese->prev) { /*use previously selected data to make a usefull vertex plane */
343                         EM_editselection_center(vec, ese->prev);
344                         sub_v3_v3v3(plane, vec, eve->co);
345                 } else {
346                         /* make a fake  plane thats at rightangles to the normal
347                         we cant make a crossvec from a vec thats the same as the vec
348                         unlikely but possible, so make sure if the normal is (0,0,1)
349                         that vec isnt the same or in the same direction even.*/
350                         if (eve->no[0]<0.5)                     vec[0]=1;
351                         else if (eve->no[1]<0.5)        vec[1]=1;
352                         else                                            vec[2]=1;
353                         cross_v3_v3v3(plane, eve->no, vec);
354                 }
355         } else if (ese->type==EDITEDGE) {
356                 EditEdge *eed= ese->data;
357
358                 /*the plane is simple, it runs allong the edge
359                 however selecting different edges can swap the direction of the y axis.
360                 this makes it less likely for the y axis of the manipulator
361                 (running along the edge).. to flip less often.
362                 at least its more pradictable */
363                 if (eed->v2->co[1] > eed->v1->co[1]) /*check which to do first */
364                         sub_v3_v3v3(plane, eed->v2->co, eed->v1->co);
365                 else
366                         sub_v3_v3v3(plane, eed->v1->co, eed->v2->co);
367                 
368         } else if (ese->type==EDITFACE) {
369                 EditFace *efa= ese->data;
370                 float vec[3];
371                 if (efa->v4) { /*if its a quad- set the plane along the 2 longest edges.*/
372                         float vecA[3], vecB[3];
373                         sub_v3_v3v3(vecA, efa->v4->co, efa->v3->co);
374                         sub_v3_v3v3(vecB, efa->v1->co, efa->v2->co);
375                         add_v3_v3v3(plane, vecA, vecB);
376                         
377                         sub_v3_v3v3(vecA, efa->v1->co, efa->v4->co);
378                         sub_v3_v3v3(vecB, efa->v2->co, efa->v3->co);
379                         add_v3_v3v3(vec, vecA, vecB);                                           
380                         /*use the biggest edge length*/
381                         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])
382                                 copy_v3_v3(plane, vec);
383                 } else {
384                         /*start with v1-2 */
385                         sub_v3_v3v3(plane, efa->v1->co, efa->v2->co);
386                         
387                         /*test the edge between v2-3, use if longer */
388                         sub_v3_v3v3(vec, efa->v2->co, efa->v3->co);
389                         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])
390                                 copy_v3_v3(plane, vec);
391                         
392                         /*test the edge between v1-3, use if longer */
393                         sub_v3_v3v3(vec, efa->v3->co, efa->v1->co);
394                         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])
395                                 copy_v3_v3(plane, vec);
396                 }
397         }
398         normalize_v3(plane);
399 }
400
401
402
403 void EM_select_face(EditFace *efa, int sel)
404 {
405         if(sel) {
406                 efa->f |= SELECT;
407                 efa->e1->f |= SELECT;
408                 efa->e2->f |= SELECT;
409                 efa->e3->f |= SELECT;
410                 if(efa->e4) efa->e4->f |= SELECT;
411                 efa->v1->f |= SELECT;
412                 efa->v2->f |= SELECT;
413                 efa->v3->f |= SELECT;
414                 if(efa->v4) efa->v4->f |= SELECT;
415         }
416         else {
417                 efa->f &= ~SELECT;
418                 efa->e1->f &= ~SELECT;
419                 efa->e2->f &= ~SELECT;
420                 efa->e3->f &= ~SELECT;
421                 if(efa->e4) efa->e4->f &= ~SELECT;
422                 efa->v1->f &= ~SELECT;
423                 efa->v2->f &= ~SELECT;
424                 efa->v3->f &= ~SELECT;
425                 if(efa->v4) efa->v4->f &= ~SELECT;
426         }
427 }
428
429 void EM_select_edge(EditEdge *eed, int sel)
430 {
431         if(sel) {
432                 eed->f |= SELECT;
433                 eed->v1->f |= SELECT;
434                 eed->v2->f |= SELECT;
435         }
436         else {
437                 eed->f &= ~SELECT;
438                 eed->v1->f &= ~SELECT;
439                 eed->v2->f &= ~SELECT;
440         }
441 }
442
443 void EM_select_face_fgon(EditMesh *em, EditFace *efa, int val)
444 {
445         short index=0;
446         
447         if(efa->fgonf==0) EM_select_face(efa, val);
448         else {
449                 if(efa->e1->fgoni) index= efa->e1->fgoni;
450                 if(efa->e2->fgoni) index= efa->e2->fgoni;
451                 if(efa->e3->fgoni) index= efa->e3->fgoni;
452                 if(efa->v4 && efa->e4->fgoni) index= efa->e4->fgoni;
453                 
454                 if((index==0) && (G.f & G_DEBUG))printf("wrong fgon select\n");
455                 
456                 // select all ngon faces with index
457                 for(efa= em->faces.first; efa; efa= efa->next) {
458                         if(efa->fgonf) {
459                                 if(efa->e1->fgoni==index || efa->e2->fgoni==index || 
460                                    efa->e3->fgoni==index || (efa->e4 && efa->e4->fgoni==index) ) {
461                                         EM_select_face(efa, val);
462                                 }
463                         }
464                 }
465         }
466 }
467
468
469 /* only vertices */
470 int faceselectedOR(EditFace *efa, int flag)
471 {
472         if ((efa->v1->f | efa->v2->f | efa->v3->f | (efa->v4?efa->v4->f:0))&flag) {
473                 return 1;
474         } else {
475                 return 0;
476         }
477 }
478
479 // replace with (efa->f & SELECT)
480 int faceselectedAND(EditFace *efa, int flag)
481 {
482         if ((efa->v1->f & efa->v2->f & efa->v3->f & (efa->v4?efa->v4->f:flag))&flag) {
483                 return 1;
484         } else {
485                 return 0;
486         }
487 }
488
489 void EM_clear_flag_all(EditMesh *em, int flag)
490 {
491         EditVert *eve;
492         EditEdge *eed;
493         EditFace *efa;
494         
495         for (eve= em->verts.first; eve; eve= eve->next) eve->f &= ~flag;
496         for (eed= em->edges.first; eed; eed= eed->next) eed->f &= ~flag;
497         for (efa= em->faces.first; efa; efa= efa->next) efa->f &= ~flag;
498         
499         if(flag & SELECT) {
500                 BLI_freelistN(&(em->selected));
501                 em->totvertsel= em->totedgesel= em->totfacesel= 0;
502         }
503 }
504
505 void EM_set_flag_all(EditMesh *em, int flag)
506 {
507         EditVert *eve;
508         EditEdge *eed;
509         EditFace *efa;
510         
511         for (eve= em->verts.first; eve; eve= eve->next) if(eve->h==0) eve->f |= flag;
512         for (eed= em->edges.first; eed; eed= eed->next) if(eed->h==0) eed->f |= flag;
513         for (efa= em->faces.first; efa; efa= efa->next) if(efa->h==0) efa->f |= flag;
514         
515         if(flag & SELECT) {
516                 em->totvertsel= em->totvert;
517                 em->totedgesel= em->totedge;
518                 em->totfacesel= em->totface;
519         }
520 }
521
522 void EM_set_flag_all_selectmode(EditMesh *em, int flag)
523 {
524          EditVert *eve;
525          EditEdge *eed;
526          EditFace *efa;
527
528         int selvert= 0, seledge= 0, selface= 0;
529
530         if (em->selectmode & SCE_SELECT_VERTEX) {
531                 /* If vertex select mode enabled all the data could be affected */
532                 for (eve= em->verts.first; eve; eve= eve->next) if(eve->h==0) eve->f |= flag;
533                 for (eed= em->edges.first; eed; eed= eed->next) if(eed->h==0) eed->f |= flag;
534                 for (efa= em->faces.first; efa; efa= efa->next) if(efa->h==0) efa->f |= flag;
535
536                 if (flag & SELECT) {
537                         selvert= em->totvert;
538                         seledge= em->totedge;
539                         selface= em->totface;
540                 }
541         } else if (em->selectmode & SCE_SELECT_EDGE) {
542                 /* If edge select mode is enabled we should affect on all edges, faces and */
543                 /* vertices, connected to them */
544
545                 for (eed= em->edges.first; eed; eed= eed->next) {
546                         SET_EED_FLAG(eed, flag)
547                 }
548
549                 for (efa= em->faces.first; efa; efa= efa->next) {
550                         if(efa->h==0) {
551                                 efa->f |= flag;
552
553                                 if (flag & SELECT) {
554                                         ++selface;
555                                 }
556                         }
557                 }
558         } else if (em->selectmode & SCE_SELECT_FACE) {
559                 /* No vertex and edge select mode, only face selection */
560                 /* In face select mode only edges and vertices belongs to faces should be affected */
561
562                 for (efa= em->faces.first; efa; efa= efa->next) {
563                         if(efa->h==0) {
564                                 efa->f |= flag;
565                                 SET_EED_FLAG(efa->e1, flag);
566                                 SET_EED_FLAG(efa->e2, flag);
567                                 SET_EED_FLAG(efa->e3, flag);
568
569                                 if (efa->e4) {
570                                         SET_EED_FLAG(efa->e4, flag);
571                                 }
572
573                                 if (flag & SELECT) {
574                                         ++selface;
575                                 }
576                         }
577                 }
578         }
579
580         if(flag & SELECT) {
581                 em->totvertsel= selvert;
582                 em->totedgesel= seledge;
583                 em->totfacesel= selface;
584          }
585  }
586 /* flush for changes in vertices only */
587 void EM_deselect_flush(EditMesh *em)
588 {
589         EditEdge *eed;
590         EditFace *efa;
591         
592         for(eed= em->edges.first; eed; eed= eed->next) {
593                 if(eed->v1->f & eed->v2->f & SELECT);
594                 else eed->f &= ~SELECT;
595         }
596         for(efa= em->faces.first; efa; efa= efa->next) {
597                 if(efa->v4) {
598                         if(efa->v1->f & efa->v2->f & efa->v3->f & efa->v4->f & SELECT );
599                         else efa->f &= ~SELECT;
600                 }
601                 else {
602                         if(efa->v1->f & efa->v2->f & efa->v3->f & SELECT );
603                         else efa->f &= ~SELECT;
604                 }
605         }
606         EM_nedges_selected(em);
607         EM_nfaces_selected(em);
608 }
609
610
611 /* flush selection to edges & faces */
612
613 /*  this only based on coherent selected vertices, for example when adding new
614         objects. call clear_flag_all() before you select vertices to be sure it ends OK!
615         
616 */
617
618 void EM_select_flush(EditMesh *em)
619 {
620         EditEdge *eed;
621         EditFace *efa;
622         
623         for(eed= em->edges.first; eed; eed= eed->next) {
624                 if(eed->v1->f & eed->v2->f & SELECT) eed->f |= SELECT;
625         }
626         for(efa= em->faces.first; efa; efa= efa->next) {
627                 if(efa->v4) {
628                         if(efa->v1->f & efa->v2->f & efa->v3->f & efa->v4->f & SELECT ) efa->f |= SELECT;
629                 }
630                 else {
631                         if(efa->v1->f & efa->v2->f & efa->v3->f & SELECT ) efa->f |= SELECT;
632                 }
633         }
634         EM_nedges_selected(em);
635         EM_nfaces_selected(em);
636 }
637
638 /* when vertices or edges can be selected, also make fgon consistent */
639 static void check_fgons_selection(EditMesh *em)
640 {
641         EditFace *efa, *efan;
642         EditEdge *eed;
643         ListBase *lbar;
644         int sel, desel, index, totfgon= 0;
645         
646         /* count amount of fgons */
647         for(eed= em->edges.first; eed; eed= eed->next) 
648                 if(eed->fgoni>totfgon) totfgon= eed->fgoni;
649         
650         if(totfgon==0) return;
651         
652         lbar= MEM_callocN((totfgon+1)*sizeof(ListBase), "listbase array");
653         
654         /* put all fgons in lbar */
655         for(efa= em->faces.first; efa; efa= efan) {
656                 efan= efa->next;
657                 index= efa->e1->fgoni;
658                 if(index==0) index= efa->e2->fgoni;
659                 if(index==0) index= efa->e3->fgoni;
660                 if(index==0 && efa->e4) index= efa->e4->fgoni;
661                 if(index) {
662                         BLI_remlink(&em->faces, efa);
663                         BLI_addtail(&lbar[index], efa);
664                 }
665         }
666         
667         /* now check the fgons */
668         for(index=1; index<=totfgon; index++) {
669                 /* we count on vertices/faces/edges being set OK, so we only have to set ngon itself */
670                 sel= desel= 0;
671                 for(efa= lbar[index].first; efa; efa= efa->next) {
672                         if(efa->e1->fgoni==0) {
673                                 if(efa->e1->f & SELECT) sel++;
674                                 else desel++;
675                         }
676                         if(efa->e2->fgoni==0) {
677                                 if(efa->e2->f & SELECT) sel++;
678                                 else desel++;
679                         }
680                         if(efa->e3->fgoni==0) {
681                                 if(efa->e3->f & SELECT) sel++;
682                                 else desel++;
683                         }
684                         if(efa->e4 && efa->e4->fgoni==0) {
685                                 if(efa->e4->f & SELECT) sel++;
686                                 else desel++;
687                         }
688                         
689                         if(sel && desel) break;
690                 }
691
692                 if(sel && desel) sel= 0;
693                 else if(sel) sel= 1;
694                 else sel= 0;
695                 
696                 /* select/deselect and put back */
697                 for(efa= lbar[index].first; efa; efa= efa->next) {
698                         if(sel) efa->f |= SELECT;
699                         else efa->f &= ~SELECT;
700                 }
701                 addlisttolist(&em->faces, &lbar[index]);
702         }
703         
704         MEM_freeN(lbar);
705 }
706
707
708 /* flush to edges & faces */
709
710 /* based on select mode it selects edges/faces 
711    assumed is that verts/edges/faces were properly selected themselves
712    with the calls above
713 */
714
715 void EM_selectmode_flush(EditMesh *em)
716 {
717         EditEdge *eed;
718         EditFace *efa;
719         
720         // flush to edges & faces
721         if(em->selectmode & SCE_SELECT_VERTEX) {
722                 for(eed= em->edges.first; eed; eed= eed->next) {
723                         if(eed->v1->f & eed->v2->f & SELECT) eed->f |= SELECT;
724                         else eed->f &= ~SELECT;
725                 }
726                 for(efa= em->faces.first; efa; efa= efa->next) {
727                         if(efa->v4) {
728                                 if(efa->v1->f & efa->v2->f & efa->v3->f & efa->v4->f & SELECT) efa->f |= SELECT;
729                                 else efa->f &= ~SELECT;
730                         }
731                         else {
732                                 if(efa->v1->f & efa->v2->f & efa->v3->f & SELECT) efa->f |= SELECT;
733                                 else efa->f &= ~SELECT;
734                         }
735                 }
736         }
737         // flush to faces
738         else if(em->selectmode & SCE_SELECT_EDGE) {
739                 for(efa= em->faces.first; efa; efa= efa->next) {
740                         if(efa->e4) {
741                                 if(efa->e1->f & efa->e2->f & efa->e3->f & efa->e4->f & SELECT) efa->f |= SELECT;
742                                 else efa->f &= ~SELECT;
743                         }
744                         else {
745                                 if(efa->e1->f & efa->e2->f & efa->e3->f & SELECT) efa->f |= SELECT;
746                                 else efa->f &= ~SELECT;
747                         }
748                 }
749         }       
750         // make sure selected faces have selected edges too, for extrude (hack?)
751         else if(em->selectmode & SCE_SELECT_FACE) {
752                 for(efa= em->faces.first; efa; efa= efa->next) {
753                         if(efa->f & SELECT) EM_select_face(efa, 1);
754                 }
755         }
756         
757         if(!(em->selectmode & SCE_SELECT_FACE))
758                 check_fgons_selection(em);
759
760         EM_nvertices_selected(em);
761         EM_nedges_selected(em);
762         EM_nfaces_selected(em);
763 }
764
765 void EM_convertsel(EditMesh *em, short oldmode, short selectmode)
766 {
767         EditVert *eve;
768         EditEdge *eed;
769         EditFace *efa;
770         /*clear flags*/
771         for(eve= em->verts.first; eve; eve= eve->next) eve->f1 = 0;
772         for(eed= em->edges.first; eed; eed= eed->next) eed->f1 = 0;
773         for(efa= em->faces.first; efa; efa= efa->next) efa->f1 = 0;
774         
775         /*have to find out what the selectionmode was previously*/
776         if(oldmode == SCE_SELECT_VERTEX) {
777                 if(selectmode == SCE_SELECT_EDGE){
778                         /*select all edges associated with every selected vertex*/
779                         for(eed= em->edges.first; eed; eed= eed->next){
780                                 if(eed->v1->f&SELECT) eed->f1 = 1;
781                                 else if(eed->v2->f&SELECT) eed->f1 = 1;
782                         }
783                         
784                         for(eed= em->edges.first; eed; eed= eed->next){
785                                 if(eed->f1 == 1) EM_select_edge(eed,1); 
786                         }
787                 }               
788                 else if(selectmode == SCE_SELECT_FACE){
789                         /*select all faces associated with every selected vertex*/
790                         for(efa= em->faces.first; efa; efa= efa->next){
791                                 if(efa->v1->f&SELECT) efa->f1 = 1;
792                                 else if(efa->v2->f&SELECT) efa->f1 = 1;
793                                 else if(efa->v3->f&SELECT) efa->f1 = 1;
794                                 else{ 
795                                         if(efa->v4){
796                                                 if(efa->v4->f&SELECT) efa->f1 =1;
797                                         }
798                                 }
799                         }
800                         for(efa= em->faces.first; efa; efa= efa->next){
801                                 if(efa->f1 == 1) EM_select_face(efa,1);
802                         }
803                 }
804         }
805         
806         if(oldmode == SCE_SELECT_EDGE){
807                 if(selectmode == SCE_SELECT_FACE){
808                         for(efa= em->faces.first; efa; efa= efa->next){
809                                 if(efa->e1->f&SELECT) efa->f1 = 1;
810                                 else if(efa->e2->f&SELECT) efa->f1 = 1;
811                                 else if(efa->e3->f&SELECT) efa->f1 = 1;
812                                 else if(efa->e4){
813                                         if(efa->e4->f&SELECT) efa->f1 = 1;
814                                 }
815                         }
816                         for(efa= em->faces.first; efa; efa= efa->next){
817                                 if(efa->f1 == 1) EM_select_face(efa,1);
818                         }
819                 }
820         }
821         
822         check_fgons_selection(em);
823
824         EM_nvertices_selected(em);
825         EM_nedges_selected(em);
826         EM_nfaces_selected(em);
827 }
828
829 void EM_selectmode_to_scene(struct Scene *scene, struct Object *obedit)
830 {
831         scene->toolsettings->selectmode= get_mesh(obedit)->edit_mesh->selectmode;
832 }
833
834 /* when switching select mode, makes sure selection is consistent for editing */
835 /* also for paranoia checks to make sure edge or face mode works */
836 void EM_selectmode_set(EditMesh *em)
837 {
838         EditVert *eve;
839         EditEdge *eed;
840         EditFace *efa;
841         
842         EM_strip_selections(em); /*strip EditSelections from em->selected that are not relevant to new mode*/
843         
844         if(em->selectmode & SCE_SELECT_VERTEX) {
845                 /* vertices -> edges -> faces */
846                 for (eed= em->edges.first; eed; eed= eed->next) eed->f &= ~SELECT;
847                 for (efa= em->faces.first; efa; efa= efa->next) efa->f &= ~SELECT;
848                 
849                 EM_select_flush(em);
850         }
851         else if(em->selectmode & SCE_SELECT_EDGE) {
852                 /* deselect vertices, and select again based on edge select */
853                 for(eve= em->verts.first; eve; eve= eve->next) eve->f &= ~SELECT;
854                 for(eed= em->edges.first; eed; eed= eed->next) 
855                         if(eed->f & SELECT) EM_select_edge(eed, 1);
856                 /* selects faces based on edge status */
857                 EM_selectmode_flush(em);
858         }
859         else if(em->selectmode & SCE_SELECT_FACE) {
860                 /* deselect eges, and select again based on face select */
861                 for(eed= em->edges.first; eed; eed= eed->next) EM_select_edge(eed, 0);
862                 
863                 for(efa= em->faces.first; efa; efa= efa->next) 
864                         if(efa->f & SELECT) EM_select_face(efa, 1);
865         }
866
867         EM_nvertices_selected(em);
868         EM_nedges_selected(em);
869         EM_nfaces_selected(em);
870 }
871
872 /* paranoia check, actually only for entering editmode. rule:
873 - vertex hidden, always means edge is hidden too
874 - edge hidden, always means face is hidden too
875 - face hidden, dont change anything
876 */
877 void EM_hide_reset(EditMesh *em)
878 {
879         EditEdge *eed;
880         EditFace *efa;
881         
882         for(eed= em->edges.first; eed; eed= eed->next) 
883                 if(eed->v1->h || eed->v2->h) eed->h |= 1;
884                 
885         for(efa= em->faces.first; efa; efa= efa->next) 
886                 if((efa->e1->h & 1) || (efa->e2->h & 1) || (efa->e3->h & 1) || (efa->e4 && (efa->e4->h & 1)))
887                         efa->h= 1;
888                 
889 }
890
891 void EM_data_interp_from_verts(EditMesh *em, EditVert *v1, EditVert *v2, EditVert *eve, float fac)
892 {
893         void *src[2];
894         float w[2];
895
896         if (v1->data && v2->data) {
897                 src[0]= v1->data;
898                 src[1]= v2->data;
899                 w[0] = 1.0f-fac;
900                 w[1] = fac;
901
902                 CustomData_em_interp(&em->vdata, src, w, NULL, 2, eve->data);
903         }
904 }
905
906 void EM_data_interp_from_faces(EditMesh *em, EditFace *efa1, EditFace *efa2, EditFace *efan, int i1, int i2, int i3, int i4)
907 {
908         float w[2][4][4];
909         void *src[2];
910         int count = (efa2)? 2: 1;
911
912         if (efa1->data) {
913                 /* set weights for copying from corners directly to other corners */
914                 memset(w, 0, sizeof(w));
915
916                 w[i1/4][0][i1%4]= 1.0f;
917                 w[i2/4][1][i2%4]= 1.0f;
918                 w[i3/4][2][i3%4]= 1.0f;
919                 if (i4 != -1)
920                         w[i4/4][3][i4%4]= 1.0f;
921
922                 src[0]= efa1->data;
923                 src[1]= (efa2)? efa2->data: NULL;
924
925                 CustomData_em_interp(&em->fdata, src, NULL, (float*)w, count, efan->data);
926         }
927 }
928
929 EditFace *EM_face_from_faces(EditMesh *em, EditFace *efa1, EditFace *efa2, int i1, int i2, int i3, int i4)
930 {
931         EditFace *efan;
932         EditVert **v[2];
933         
934         v[0]= &efa1->v1;
935         v[1]= (efa2)? &efa2->v1: NULL;
936
937         efan= addfacelist(em, v[i1/4][i1%4], v[i2/4][i2%4], v[i3/4][i3%4],
938                 (i4 == -1)? 0: v[i4/4][i4%4], efa1, NULL);
939
940         EM_data_interp_from_faces(em, efa1, efa2, efan, i1, i2, i3, i4);
941         
942         return efan;
943 }
944
945 static void update_data_blocks(EditMesh *em, CustomData *olddata, CustomData *data)
946 {
947         EditFace *efa;
948         EditVert *eve;
949         void *block;
950
951         if (data == &em->vdata) {
952                 for(eve= em->verts.first; eve; eve= eve->next) {
953                         block = NULL;
954                         CustomData_em_set_default(data, &block);
955                         CustomData_em_copy_data(olddata, data, eve->data, &block);
956                         CustomData_em_free_block(olddata, &eve->data);
957                         eve->data= block;
958                 }
959         }
960         else if (data == &em->fdata) {
961                 for(efa= em->faces.first; efa; efa= efa->next) {
962                         block = NULL;
963                         CustomData_em_set_default(data, &block);
964                         CustomData_em_copy_data(olddata, data, efa->data, &block);
965                         CustomData_em_free_block(olddata, &efa->data);
966                         efa->data= block;
967                 }
968         }
969 }
970
971 void EM_add_data_layer(EditMesh *em, CustomData *data, int type, const char *name)
972 {
973         CustomData olddata;
974
975         olddata= *data;
976         olddata.layers= (olddata.layers)? MEM_dupallocN(olddata.layers): NULL;
977         CustomData_add_layer_named(data, type, CD_CALLOC, NULL, 0, name);
978
979         update_data_blocks(em, &olddata, data);
980         if (olddata.layers) MEM_freeN(olddata.layers);
981 }
982
983 void EM_free_data_layer(EditMesh *em, CustomData *data, int type)
984 {
985         CustomData olddata;
986
987         olddata= *data;
988         olddata.layers= (olddata.layers)? MEM_dupallocN(olddata.layers): NULL;
989         CustomData_free_layer_active(data, type, 0);
990
991         update_data_blocks(em, &olddata, data);
992         if (olddata.layers) MEM_freeN(olddata.layers);
993 }
994
995 /* ********  EXTRUDE ********* */
996
997 static void add_normal_aligned(float *nor, float *add)
998 {
999         if( INPR(nor, add) < -0.9999f)
1000                 sub_v3_v3(nor, add);
1001         else
1002                 add_v3_v3(nor, add);
1003 }
1004
1005 static void set_edge_directions_f2(EditMesh *em, int val)
1006 {
1007         EditFace *efa;
1008         int do_all= 1;
1009         
1010         /* edge directions are used for extrude, to detect direction of edges that make new faces */
1011         /* we have set 'f2' flags in edges that need to get a direction set (e.g. get new face) */
1012         /* the val argument differs... so we need it as arg */
1013         
1014         for(efa= em->faces.first; efa; efa= efa->next) {
1015                 if(efa->f & SELECT) {
1016                         do_all= 0;
1017                         if(efa->e1->f2<val) {
1018                                 if(efa->e1->v1 == efa->v1) efa->e1->dir= 0;
1019                                 else efa->e1->dir= 1;
1020                         }
1021                         if(efa->e2->f2<val) {
1022                                 if(efa->e2->v1 == efa->v2) efa->e2->dir= 0;
1023                                 else efa->e2->dir= 1;
1024                         }
1025                         if(efa->e3->f2<val) {
1026                                 if(efa->e3->v1 == efa->v3) efa->e3->dir= 0;
1027                                 else efa->e3->dir= 1;
1028                         }
1029                         if(efa->e4 && efa->e4->f2<val) {
1030                                 if(efa->e4->v1 == efa->v4) efa->e4->dir= 0;
1031                                 else efa->e4->dir= 1;
1032                         }
1033                 }
1034         }       
1035         /* ok, no faces done... then we at least set it for exterior edges */
1036         if(do_all) {
1037                 for(efa= em->faces.first; efa; efa= efa->next) {
1038                         if(efa->e1->v1 == efa->v1) efa->e1->dir= 0;
1039                         else efa->e1->dir= 1;
1040                         if(efa->e2->v1 == efa->v2) efa->e2->dir= 0;
1041                         else efa->e2->dir= 1;
1042                         if(efa->e3->v1 == efa->v3) efa->e3->dir= 0;
1043                         else efa->e3->dir= 1;
1044                         if(efa->e4) {
1045                                 if(efa->e4->v1 == efa->v4) efa->e4->dir= 0;
1046                                 else efa->e4->dir= 1;
1047                         }
1048                 }       
1049         }
1050 }
1051
1052 /* individual face extrude */
1053 /* will use vertex normals for extrusion directions, so *nor is unaffected */
1054 short extrudeflag_face_indiv(EditMesh *em, short UNUSED(flag), float *UNUSED(nor))
1055 {
1056         EditVert *eve, *v1, *v2, *v3, *v4;
1057         EditEdge *eed;
1058         EditFace *efa, *nextfa;
1059         
1060         if(em==NULL) return 0;
1061         
1062         /* selected edges with 1 or more selected face become faces */
1063         /* selected faces each makes new faces */
1064         /* always remove old faces, keeps volumes manifold */
1065         /* select the new extrusion, deselect old */
1066         
1067         /* step 1; init, count faces in edges */
1068         recalc_editnormals(em);
1069         
1070         for(eve= em->verts.first; eve; eve= eve->next) eve->f1= 0;      // new select flag
1071
1072         for(eed= em->edges.first; eed; eed= eed->next) {
1073                 eed->f2= 0; // amount of unselected faces
1074         }
1075         for(efa= em->faces.first; efa; efa= efa->next) {
1076                 if(efa->f & SELECT);
1077                 else {
1078                         efa->e1->f2++;
1079                         efa->e2->f2++;
1080                         efa->e3->f2++;
1081                         if(efa->e4) efa->e4->f2++;
1082                 }
1083         }
1084
1085         /* step 2: make new faces from faces */
1086         for(efa= em->faces.last; efa; efa= efa->prev) {
1087                 if(efa->f & SELECT) {
1088                         v1= addvertlist(em, efa->v1->co, efa->v1);
1089                         v2= addvertlist(em, efa->v2->co, efa->v2);
1090                         v3= addvertlist(em, efa->v3->co, efa->v3);
1091                         
1092                         v1->f1= v2->f1= v3->f1= 1;
1093                         VECCOPY(v1->no, efa->n);
1094                         VECCOPY(v2->no, efa->n);
1095                         VECCOPY(v3->no, efa->n);
1096                         if(efa->v4) {
1097                                 v4= addvertlist(em, efa->v4->co, efa->v4); 
1098                                 v4->f1= 1;
1099                                 VECCOPY(v4->no, efa->n);
1100                         }
1101                         else v4= NULL;
1102                         
1103                         /* side faces, clockwise */
1104                         addfacelist(em, efa->v2, v2, v1, efa->v1, efa, NULL);
1105                         addfacelist(em, efa->v3, v3, v2, efa->v2, efa, NULL);
1106                         if(efa->v4) {
1107                                 addfacelist(em, efa->v4, v4, v3, efa->v3, efa, NULL);
1108                                 addfacelist(em, efa->v1, v1, v4, efa->v4, efa, NULL);
1109                         }
1110                         else {
1111                                 addfacelist(em, efa->v1, v1, v3, efa->v3, efa, NULL);
1112                         }
1113                         /* top face */
1114                         addfacelist(em, v1, v2, v3, v4, efa, NULL);
1115                 }
1116         }
1117         
1118         /* step 3: remove old faces */
1119         efa= em->faces.first;
1120         while(efa) {
1121                 nextfa= efa->next;
1122                 if(efa->f & SELECT) {
1123                         BLI_remlink(&em->faces, efa);
1124                         free_editface(em, efa);
1125                 }
1126                 efa= nextfa;
1127         }
1128
1129         /* step 4: redo selection */
1130         EM_clear_flag_all(em, SELECT);
1131         
1132         for(eve= em->verts.first; eve; eve= eve->next) {
1133                 if(eve->f1)  eve->f |= SELECT;
1134         }
1135         
1136         EM_select_flush(em);
1137         
1138         return 'n';
1139 }
1140
1141
1142 /* extrudes individual edges */
1143 /* nor is filled with constraint vector */
1144 short extrudeflag_edges_indiv(EditMesh *em, short flag, float *nor) 
1145 {
1146         EditVert *eve;
1147         EditEdge *eed;
1148         EditFace *efa;
1149         
1150         for(eve= em->verts.first; eve; eve= eve->next) eve->tmp.v = NULL;
1151         for(eed= em->edges.first; eed; eed= eed->next) {
1152                 eed->tmp.f = NULL;
1153                 eed->f2= ((eed->f & flag)!=0);
1154         }
1155         
1156         set_edge_directions_f2(em, 2);
1157
1158         /* sample for next loop */
1159         for(efa= em->faces.first; efa; efa= efa->next) {
1160                 efa->e1->tmp.f = efa;
1161                 efa->e2->tmp.f = efa;
1162                 efa->e3->tmp.f = efa;
1163                 if(efa->e4) efa->e4->tmp.f = efa;
1164         }
1165         /* make the faces */
1166         for(eed= em->edges.first; eed; eed= eed->next) {
1167                 if(eed->f & flag) {
1168                         if(eed->v1->tmp.v == NULL)
1169                                 eed->v1->tmp.v = addvertlist(em, eed->v1->co, eed->v1);
1170                         if(eed->v2->tmp.v == NULL)
1171                                 eed->v2->tmp.v = addvertlist(em, eed->v2->co, eed->v2);
1172
1173                         if(eed->dir==1) 
1174                                 addfacelist(em, eed->v1, eed->v2, 
1175                                                         eed->v2->tmp.v, eed->v1->tmp.v, 
1176                                                         eed->tmp.f, NULL);
1177                         else 
1178                                 addfacelist(em, eed->v2, eed->v1, 
1179                                                         eed->v1->tmp.v, eed->v2->tmp.v, 
1180                                                         eed->tmp.f, NULL);
1181
1182                         /* for transform */
1183                         if(eed->tmp.f) {
1184                                 efa = eed->tmp.f;
1185                                 if (efa->f & SELECT) add_normal_aligned(nor, efa->n);
1186                         }
1187                 }
1188         }
1189         normalize_v3(nor);
1190         
1191         /* set correct selection */
1192         EM_clear_flag_all(em, SELECT);
1193         for(eve= em->verts.last; eve; eve= eve->prev) {
1194                 if(eve->tmp.v) {
1195                         eve->tmp.v->f |= flag;
1196                 }
1197         }
1198
1199         for(eed= em->edges.first; eed; eed= eed->next) {
1200                 if(eed->v1->f & eed->v2->f & flag) eed->f |= flag;
1201         }
1202         
1203         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // g is grab
1204         return 'n';  // n is for normal constraint
1205 }
1206
1207 /* extrudes individual vertices */
1208 short extrudeflag_verts_indiv(EditMesh *em, short flag, float *UNUSED(nor)) 
1209 {
1210         EditVert *eve;
1211         
1212         /* make the edges */
1213         for(eve= em->verts.first; eve; eve= eve->next) {
1214                 if(eve->f & flag) {
1215                         eve->tmp.v = addvertlist(em, eve->co, eve);
1216                         addedgelist(em, eve, eve->tmp.v, NULL);
1217                 }
1218                 else eve->tmp.v = NULL;
1219         }
1220         
1221         /* set correct selection */
1222         EM_clear_flag_all(em, SELECT);
1223
1224         for(eve= em->verts.last; eve; eve= eve->prev) 
1225                 if (eve->tmp.v) 
1226                         eve->tmp.v->f |= flag;
1227
1228         return 'g';     // g is grab
1229 }
1230
1231
1232 /* this is actually a recode of extrudeflag(), using proper edge/face select */
1233 /* hurms, doesnt use 'flag' yet, but its not called by primitive making stuff anyway */
1234 static short extrudeflag_edge(Object *obedit, EditMesh *em, short UNUSED(flag), float *nor, int all)
1235 {
1236         /* all select edges/faces: extrude */
1237         /* old select is cleared, in new ones it is set */
1238         EditVert *eve, *nextve;
1239         EditEdge *eed, *nexted;
1240         EditFace *efa, *nextfa, *efan;
1241         short del_old= 0;
1242         ModifierData *md;
1243         
1244         if(em==NULL) return 0;
1245
1246         md = obedit->modifiers.first;
1247         
1248         /* selected edges with 0 or 1 selected face become faces */
1249         /* selected faces generate new faces */
1250
1251         /* if *one* selected face has edge with unselected face; remove old selected faces */
1252         
1253         /* if selected edge is not used anymore; remove */
1254         /* if selected vertex is not used anymore: remove */
1255         
1256         /* select the new extrusion, deselect old */
1257         
1258         
1259         /* step 1; init, count faces in edges */
1260         recalc_editnormals(em);
1261         
1262         for(eve= em->verts.first; eve; eve= eve->next) {
1263                 eve->tmp.v = NULL;
1264                 eve->f1= 0;
1265         }
1266
1267         for(eed= em->edges.first; eed; eed= eed->next) {
1268                 eed->f1= 0; // amount of unselected faces
1269                 eed->f2= 0; // amount of selected faces
1270                 if(eed->f & SELECT) {
1271                         eed->v1->f1= 1; // we call this 'selected vertex' now
1272                         eed->v2->f1= 1;
1273                 }
1274                 eed->tmp.f = NULL;              // here we tuck face pointer, as sample
1275         }
1276         for(efa= em->faces.first; efa; efa= efa->next) {
1277                 if(efa->f & SELECT) {
1278                         efa->e1->f2++;
1279                         efa->e2->f2++;
1280                         efa->e3->f2++;
1281                         if(efa->e4) efa->e4->f2++;
1282                         
1283                         // sample for next loop
1284                         efa->e1->tmp.f = efa;
1285                         efa->e2->tmp.f = efa;
1286                         efa->e3->tmp.f = efa;
1287                         if(efa->e4) efa->e4->tmp.f = efa;
1288                 }
1289                 else {
1290                         efa->e1->f1++;
1291                         efa->e2->f1++;
1292                         efa->e3->f1++;
1293                         if(efa->e4) efa->e4->f1++;
1294                 }
1295         }
1296         
1297         /* If a mirror modifier with clipping is on, we need to adjust some 
1298          * of the cases above to handle edges on the line of symmetry.
1299          */
1300         for (; md; md=md->next) {
1301                 if (md->type==eModifierType_Mirror) {
1302                         MirrorModifierData *mmd = (MirrorModifierData*) md;     
1303                 
1304                         if(mmd->flag & MOD_MIR_CLIPPING) {
1305                                 float mtx[4][4];
1306                                 if (mmd->mirror_ob) {
1307                                         float imtx[4][4];
1308                                         invert_m4_m4(imtx, mmd->mirror_ob->obmat);
1309                                         mul_m4_m4m4(mtx, obedit->obmat, imtx);
1310                                 }
1311
1312                                 for (eed= em->edges.first; eed; eed= eed->next) {
1313                                         if(eed->f2 == 1) {
1314                                                 float co1[3], co2[3];
1315
1316                                                 copy_v3_v3(co1, eed->v1->co);
1317                                                 copy_v3_v3(co2, eed->v2->co);
1318
1319                                                 if (mmd->mirror_ob) {
1320                                                         mul_m4_v3(mtx, co1);
1321                                                         mul_m4_v3(mtx, co2);
1322                                                 }
1323
1324                                                 if (mmd->flag & MOD_MIR_AXIS_X)
1325                                                         if ( (fabs(co1[0]) < mmd->tolerance) &&
1326                                                                  (fabs(co2[0]) < mmd->tolerance) )
1327                                                                 ++eed->f2;
1328
1329                                                 if (mmd->flag & MOD_MIR_AXIS_Y)
1330                                                         if ( (fabs(co1[1]) < mmd->tolerance) &&
1331                                                                  (fabs(co2[1]) < mmd->tolerance) )
1332                                                                 ++eed->f2;
1333
1334                                                 if (mmd->flag & MOD_MIR_AXIS_Z)
1335                                                         if ( (fabs(co1[2]) < mmd->tolerance) &&
1336                                                                  (fabs(co2[2]) < mmd->tolerance) )
1337                                                                 ++eed->f2;
1338                                         }
1339                                 }
1340                         }
1341                 }
1342         }
1343
1344         set_edge_directions_f2(em, 2);
1345         
1346         /* step 1.5: if *one* selected face has edge with unselected face; remove old selected faces */
1347         if(all == 0) {
1348                 for(efa= em->faces.last; efa; efa= efa->prev) {
1349                         if(efa->f & SELECT) {
1350                                 if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1 || (efa->e4 && efa->e4->f1)) {
1351                                         del_old= 1;
1352                                         break;
1353                                 }
1354                         }
1355                 }
1356         }
1357                                 
1358         /* step 2: make new faces from edges */
1359         for(eed= em->edges.last; eed; eed= eed->prev) {
1360                 if(eed->f & SELECT) {
1361                         if(eed->f2<2) {
1362                                 if(eed->v1->tmp.v == NULL)
1363                                         eed->v1->tmp.v = addvertlist(em, eed->v1->co, eed->v1);
1364                                 if(eed->v2->tmp.v == NULL)
1365                                         eed->v2->tmp.v = addvertlist(em, eed->v2->co, eed->v2);
1366
1367                                 /* if del_old, the preferred normal direction is exact 
1368                                  * opposite as for keep old faces
1369                                  */
1370                                 if(eed->dir!=del_old) 
1371                                         addfacelist(em, eed->v1, eed->v2, 
1372                                                                 eed->v2->tmp.v, eed->v1->tmp.v, 
1373                                                                 eed->tmp.f, NULL);
1374                                 else 
1375                                         addfacelist(em, eed->v2, eed->v1, 
1376                                                                 eed->v1->tmp.v, eed->v2->tmp.v,
1377                                                                 eed->tmp.f, NULL);
1378                         }
1379                 }
1380         }
1381         
1382         /* step 3: make new faces from faces */
1383         for(efa= em->faces.last; efa; efa= efa->prev) {
1384                 if(efa->f & SELECT) {
1385                         if (efa->v1->tmp.v == NULL)
1386                                 efa->v1->tmp.v = addvertlist(em, efa->v1->co, efa->v1);
1387                         if (efa->v2->tmp.v ==NULL)
1388                                 efa->v2->tmp.v = addvertlist(em, efa->v2->co, efa->v2);
1389                         if (efa->v3->tmp.v ==NULL)
1390                                 efa->v3->tmp.v = addvertlist(em, efa->v3->co, efa->v3);
1391                         if (efa->v4 && (efa->v4->tmp.v == NULL))
1392                                 efa->v4->tmp.v = addvertlist(em, efa->v4->co, efa->v4);
1393                         
1394                         if(del_old==0) {        // keep old faces means flipping normal
1395                                 if(efa->v4)
1396                                         efan = addfacelist(em, efa->v4->tmp.v, efa->v3->tmp.v, 
1397                                                                 efa->v2->tmp.v, efa->v1->tmp.v, efa, efa);
1398                                 else
1399                                         efan = addfacelist(em, efa->v3->tmp.v, efa->v2->tmp.v, 
1400                                                                 efa->v1->tmp.v, NULL, efa, efa);
1401                         }
1402                         else {
1403                                 if(efa->v4)
1404                                         efan = addfacelist(em, efa->v1->tmp.v, efa->v2->tmp.v, 
1405                                                                 efa->v3->tmp.v, efa->v4->tmp.v, efa, efa);
1406                                 else
1407                                         efan = addfacelist(em, efa->v1->tmp.v, efa->v2->tmp.v, 
1408                                                                 efa->v3->tmp.v, NULL, efa, efa);
1409                         }
1410                         
1411                         if (em->act_face == efa) {
1412                                 em->act_face = efan; 
1413                         }
1414                         
1415                         /* for transform */
1416                         add_normal_aligned(nor, efa->n);
1417                 }
1418         }
1419         
1420         if(del_old) {
1421                 
1422                 /* step 4: remove old faces, if del_old */
1423                 efa= em->faces.first;
1424                 while(efa) {
1425                         nextfa= efa->next;
1426                         if(efa->f & SELECT) {
1427                                 BLI_remlink(&em->faces, efa);
1428                                 free_editface(em, efa);
1429                         }
1430                         efa= nextfa;
1431                 }
1432                 
1433                 
1434                 /* step 5: remove selected unused edges */
1435                 /* start tagging again */
1436                 for(eed= em->edges.first; eed; eed= eed->next) eed->f1=0;
1437                 for(efa= em->faces.first; efa; efa= efa->next) {
1438                         efa->e1->f1= 1;
1439                         efa->e2->f1= 1;
1440                         efa->e3->f1= 1;
1441                         if(efa->e4) efa->e4->f1= 1;
1442                 }
1443                 /* remove */
1444                 eed= em->edges.first; 
1445                 while(eed) {
1446                         nexted= eed->next;
1447                         if(eed->f & SELECT) {
1448                                 if(eed->f1==0) {
1449                                         remedge(em, eed);
1450                                         free_editedge(em, eed);
1451                                 }
1452                         }
1453                         eed= nexted;
1454                 }
1455         
1456                 /* step 6: remove selected unused vertices */
1457                 for(eed= em->edges.first; eed; eed= eed->next) 
1458                         eed->v1->f1= eed->v2->f1= 0;
1459                 
1460                 eve= em->verts.first;
1461                 while(eve) {
1462                         nextve= eve->next;
1463                         if(eve->f1) {
1464                                 // hack... but we need it for step 7, redoing selection
1465                                 if(eve->tmp.v) eve->tmp.v->tmp.v= eve->tmp.v;
1466                                 
1467                                 BLI_remlink(&em->verts, eve);
1468                                 free_editvert(em, eve);
1469                         }
1470                         eve= nextve;
1471                 }
1472         }
1473         
1474         normalize_v3(nor);      // translation normal grab
1475         
1476         /* step 7: redo selection */
1477         EM_clear_flag_all(em, SELECT);
1478
1479         for(eve= em->verts.first; eve; eve= eve->next) {
1480                 if(eve->tmp.v) {
1481                         eve->tmp.v->f |= SELECT;
1482                 }
1483         }
1484
1485         EM_select_flush(em);
1486
1487         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // grab
1488         return 'n'; // normal constraint 
1489 }
1490
1491 short extrudeflag_vert(Object *obedit, EditMesh *em, short flag, float *nor, int all)
1492 {
1493         /* all verts/edges/faces with (f & 'flag'): extrude */
1494         /* from old verts, 'flag' is cleared, in new ones it is set */
1495         EditVert *eve, *v1, *v2, *v3, *v4, *nextve;
1496         EditEdge *eed, *e1, *e2, *e3, *e4, *nexted;
1497         EditFace *efa, *efa2, *nextvl;
1498         short sel=0, del_old= 0, is_face_sel=0;
1499         ModifierData *md;
1500
1501         if(em==NULL) return 0;
1502
1503         md = obedit->modifiers.first;
1504
1505         /* clear vert flag f1, we use this to detect a loose selected vertice */
1506         eve= em->verts.first;
1507         while(eve) {
1508                 if(eve->f & flag) eve->f1= 1;
1509                 else eve->f1= 0;
1510                 eve= eve->next;
1511         }
1512         /* clear edges counter flag, if selected we set it at 1 */
1513         eed= em->edges.first;
1514         while(eed) {
1515                 if( (eed->v1->f & flag) && (eed->v2->f & flag) ) {
1516                         eed->f2= 1;
1517                         eed->v1->f1= 0;
1518                         eed->v2->f1= 0;
1519                 }
1520                 else eed->f2= 0;
1521                 
1522                 eed->f1= 1;             /* this indicates it is an 'old' edge (in this routine we make new ones) */
1523                 eed->tmp.f = NULL;      /* used as sample */
1524                 
1525                 eed= eed->next;
1526         }
1527
1528         /* we set a flag in all selected faces, and increase the associated edge counters */
1529
1530         efa= em->faces.first;
1531         while(efa) {
1532                 efa->f1= 0;
1533
1534                 if(faceselectedAND(efa, flag)) {
1535                         e1= efa->e1;
1536                         e2= efa->e2;
1537                         e3= efa->e3;
1538                         e4= efa->e4;
1539
1540                         if(e1->f2 < 3) e1->f2++;
1541                         if(e2->f2 < 3) e2->f2++;
1542                         if(e3->f2 < 3) e3->f2++;
1543                         if(e4 && e4->f2 < 3) e4->f2++;
1544                         
1545                         efa->f1= 1;
1546                         is_face_sel= 1; // for del_old
1547                 }
1548                 else if(faceselectedOR(efa, flag)) {
1549                         e1= efa->e1;
1550                         e2= efa->e2;
1551                         e3= efa->e3;
1552                         e4= efa->e4;
1553                         
1554                         if( (e1->v1->f & flag) && (e1->v2->f & flag) ) e1->f1= 2;
1555                         if( (e2->v1->f & flag) && (e2->v2->f & flag) ) e2->f1= 2;
1556                         if( (e3->v1->f & flag) && (e3->v2->f & flag) ) e3->f1= 2;
1557                         if( e4 && (e4->v1->f & flag) && (e4->v2->f & flag) ) e4->f1= 2;
1558                 }
1559                 
1560                 // sample for next loop
1561                 efa->e1->tmp.f = efa;
1562                 efa->e2->tmp.f = efa;
1563                 efa->e3->tmp.f = efa;
1564                 if(efa->e4) efa->e4->tmp.f = efa;
1565
1566                 efa= efa->next;
1567         }
1568
1569         set_edge_directions_f2(em, 3);
1570
1571         /* the current state now is:
1572                 eve->f1==1: loose selected vertex 
1573
1574                 eed->f2==0 : edge is not selected, no extrude
1575                 eed->f2==1 : edge selected, is not part of a face, extrude
1576                 eed->f2==2 : edge selected, is part of 1 face, extrude
1577                 eed->f2==3 : edge selected, is part of more faces, no extrude
1578                 
1579                 eed->f1==0: new edge
1580                 eed->f1==1: edge selected, is part of selected face, when eed->f==3: remove
1581                 eed->f1==2: edge selected, part of a partially selected face
1582                                         
1583                 efa->f1==1 : duplicate this face
1584         */
1585
1586         /* If a mirror modifier with clipping is on, we need to adjust some 
1587          * of the cases above to handle edges on the line of symmetry.
1588          */
1589         for (; md; md=md->next) {
1590                 if (md->type==eModifierType_Mirror) {
1591                         MirrorModifierData *mmd = (MirrorModifierData*) md;     
1592                 
1593                         if(mmd->flag & MOD_MIR_CLIPPING) {
1594                                 float mtx[4][4];
1595                                 if (mmd->mirror_ob) {
1596                                         float imtx[4][4];
1597                                         invert_m4_m4(imtx, mmd->mirror_ob->obmat);
1598                                         mul_m4_m4m4(mtx, obedit->obmat, imtx);
1599                                 }
1600
1601                                 for (eed= em->edges.first; eed; eed= eed->next) {
1602                                         if(eed->f2 == 2) {
1603                                                 float co1[3], co2[3];
1604
1605                                                 copy_v3_v3(co1, eed->v1->co);
1606                                                 copy_v3_v3(co2, eed->v2->co);
1607
1608                                                 if (mmd->mirror_ob) {
1609                                                         mul_m4_v3(mtx, co1);
1610                                                         mul_m4_v3(mtx, co2);
1611                                                 }
1612
1613                                                 if (mmd->flag & MOD_MIR_AXIS_X)
1614                                                         if ( (fabs(co1[0]) < mmd->tolerance) &&
1615                                                                  (fabs(co2[0]) < mmd->tolerance) )
1616                                                                 ++eed->f2;
1617
1618                                                 if (mmd->flag & MOD_MIR_AXIS_Y)
1619                                                         if ( (fabs(co1[1]) < mmd->tolerance) &&
1620                                                                  (fabs(co2[1]) < mmd->tolerance) )
1621                                                                 ++eed->f2;
1622                                                 if (mmd->flag & MOD_MIR_AXIS_Z)
1623                                                         if ( (fabs(co1[2]) < mmd->tolerance) &&
1624                                                                  (fabs(co2[2]) < mmd->tolerance) )
1625                                                                 ++eed->f2;
1626                                         }
1627                                 }
1628                         }
1629                 }
1630         }
1631
1632         /* copy all selected vertices, */
1633         /* write pointer to new vert in old struct at eve->tmp.v */
1634         eve= em->verts.last;
1635         while(eve) {
1636                 eve->f &= ~128;  /* clear, for later test for loose verts */
1637                 if(eve->f & flag) {
1638                         sel= 1;
1639                         v1= addvertlist(em, 0, NULL);
1640                         
1641                         VECCOPY(v1->co, eve->co);
1642                         VECCOPY(v1->no, eve->no);
1643                         v1->f= eve->f;
1644                         eve->f-= flag;
1645                         eve->tmp.v = v1;
1646                 }
1647                 else eve->tmp.v = 0;
1648                 eve= eve->prev;
1649         }
1650
1651         if(sel==0) return 0;
1652
1653         /* all edges with eed->f2==1 or eed->f2==2 become faces */
1654         
1655         /* if del_old==1 then extrude is in partial geometry, to keep it manifold.
1656                                          verts with f1==0 and (eve->f & 128)==0) are removed
1657                                          edges with eed->f2>2 are removed
1658                                          faces with efa->f1 are removed
1659            if del_old==0 the extrude creates a volume.
1660         */
1661         
1662          /* find if we delete old faces */
1663         if(is_face_sel && all==0) {
1664                 for(eed= em->edges.first; eed; eed= eed->next) {
1665                         if( (eed->f2==1 || eed->f2==2) ) {
1666                                 if(eed->f1==2) {
1667                                         del_old= 1;
1668                                         break;
1669                                 }
1670                         }
1671                 }
1672         }
1673         
1674         eed= em->edges.last;
1675         while(eed) {
1676                 nexted= eed->prev;
1677                 if( eed->f2<3) {
1678                         eed->v1->f |= 128;  /* = no loose vert! */
1679                         eed->v2->f |= 128;
1680                 }
1681                 if( (eed->f2==1 || eed->f2==2) ) {
1682         
1683                         /* if del_old, the preferred normal direction is exact opposite as for keep old faces */
1684                         if(eed->dir != del_old) 
1685                                 efa2 = addfacelist(em, eed->v1, eed->v2, 
1686                                                                   eed->v2->tmp.v, eed->v1->tmp.v, 
1687                                                                   eed->tmp.f, NULL);
1688                         else 
1689                                 efa2 = addfacelist(em, eed->v2, eed->v1, 
1690                                                                    eed->v1->tmp.v, eed->v2->tmp.v, 
1691                                                                    eed->tmp.f, NULL);
1692                         
1693                         /* Needs smarter adaption of existing creases.
1694                          * If addedgelist is used, make sure seams are set to 0 on these
1695                          * new edges, since we do not want to add any seams on extrusion.
1696                          */
1697                         efa2->e1->crease= eed->crease;
1698                         efa2->e2->crease= eed->crease;
1699                         efa2->e3->crease= eed->crease;
1700                         if(efa2->e4) efa2->e4->crease= eed->crease;
1701                 }
1702
1703                 eed= nexted;
1704         }
1705         if(del_old) {
1706                 eed= em->edges.first;
1707                 while(eed) {
1708                         nexted= eed->next;
1709                         if(eed->f2==3 && eed->f1==1) {
1710                                 remedge(em, eed);
1711                                 free_editedge(em, eed);
1712                         }
1713                         eed= nexted;
1714                 }
1715         }
1716         /* duplicate faces, if necessary remove old ones  */
1717         efa= em->faces.first;
1718         while(efa) {
1719                 nextvl= efa->next;
1720                 if(efa->f1 & 1) {
1721                 
1722                         v1 = efa->v1->tmp.v;
1723                         v2 = efa->v2->tmp.v;
1724                         v3 = efa->v3->tmp.v;
1725                         if(efa->v4) 
1726                                 v4 = efa->v4->tmp.v; 
1727                         else
1728                                 v4= 0;
1729
1730                         /* hmm .. not sure about edges here */
1731                         if(del_old==0)  // if we keep old, we flip normal
1732                                 efa2= addfacelist(em, v3, v2, v1, v4, efa, efa); 
1733                         else
1734                                 efa2= addfacelist(em, v1, v2, v3, v4, efa, efa);
1735                         
1736                         /* for transform */
1737                         add_normal_aligned(nor, efa->n);
1738
1739                         if(del_old) {
1740                                 BLI_remlink(&em->faces, efa);
1741                                 free_editface(em, efa);
1742                         }
1743                 }
1744                 efa= nextvl;
1745         }
1746         
1747         normalize_v3(nor);      // for grab
1748         
1749         /* for all vertices with eve->tmp.v!=0 
1750                 if eve->f1==1: make edge
1751                 if flag!=128 : if del_old==1: remove
1752         */
1753         eve= em->verts.last;
1754         while(eve) {
1755                 nextve= eve->prev;
1756                 if(eve->tmp.v) {
1757                         if(eve->f1==1) addedgelist(em, eve, eve->tmp.v, NULL);
1758                         else if( (eve->f & 128)==0) {
1759                                 if(del_old) {
1760                                         BLI_remlink(&em->verts,eve);
1761                                         free_editvert(em, eve);
1762                                         eve= NULL;
1763                                 }
1764                         }
1765                 }
1766                 if(eve) {
1767                         eve->f &= ~128;
1768                 }
1769                 eve= nextve;
1770         }
1771         // since its vertex select mode now, it also deselects higher order
1772         EM_selectmode_flush(em);
1773
1774         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // g is grab, for correct undo print
1775         return 'n';
1776 }
1777
1778 /* generic extrude */
1779 short extrudeflag(Object *obedit, EditMesh *em, short flag, float *nor, int all)
1780 {
1781         if(em->selectmode & SCE_SELECT_VERTEX)
1782                 return extrudeflag_vert(obedit, em, flag, nor, all);
1783         else 
1784                 return extrudeflag_edge(obedit, em, flag, nor, all);
1785                 
1786 }
1787
1788 void rotateflag(EditMesh *em, short flag, float *cent, float rotmat[][3])
1789 {
1790         /* all verts with (flag & 'flag') rotate */
1791         EditVert *eve;
1792
1793         eve= em->verts.first;
1794         while(eve) {
1795                 if(eve->f & flag) {
1796                         eve->co[0]-=cent[0];
1797                         eve->co[1]-=cent[1];
1798                         eve->co[2]-=cent[2];
1799                         mul_m3_v3(rotmat,eve->co);
1800                         eve->co[0]+=cent[0];
1801                         eve->co[1]+=cent[1];
1802                         eve->co[2]+=cent[2];
1803                 }
1804                 eve= eve->next;
1805         }
1806 }
1807
1808 void translateflag(EditMesh *em, short flag, float *vec)
1809 {
1810         /* all verts with (flag & 'flag') translate */
1811         EditVert *eve;
1812
1813         eve= em->verts.first;
1814         while(eve) {
1815                 if(eve->f & flag) {
1816                         eve->co[0]+=vec[0];
1817                         eve->co[1]+=vec[1];
1818                         eve->co[2]+=vec[2];
1819                 }
1820                 eve= eve->next;
1821         }
1822 }
1823
1824 /* helper call for below */
1825 static EditVert *adduplicate_vertex(EditMesh *em, EditVert *eve, int flag)
1826 {
1827         /* FIXME: copy deformation weight from eve ok here? */
1828         EditVert *v1= addvertlist(em, eve->co, eve);
1829         
1830         v1->f= eve->f;
1831         eve->f-= flag;
1832         eve->f|= 128;
1833         
1834         eve->tmp.v = v1;
1835         
1836         return v1;
1837 }
1838
1839 /* old selection has flag 128 set, and flag 'flag' cleared
1840 new selection has flag 'flag' set */
1841 void adduplicateflag(EditMesh *em, int flag)
1842 {
1843         EditVert *eve, *v1, *v2, *v3, *v4;
1844         EditEdge *eed, *newed;
1845         EditFace *efa, *newfa, *act_efa = EM_get_actFace(em, 0);
1846
1847         EM_clear_flag_all(em, 128);
1848         EM_selectmode_set(em);  // paranoia check, selection now is consistent
1849
1850         /* vertices first */
1851         for(eve= em->verts.last; eve; eve= eve->prev) {
1852
1853                 if(eve->f & flag)
1854                         adduplicate_vertex(em, eve, flag);
1855                 else 
1856                         eve->tmp.v = NULL;
1857         }
1858         
1859         /* copy edges, note that vertex selection can be independent of edge */
1860         for(eed= em->edges.last; eed; eed= eed->prev) {
1861                 if( eed->f & flag ) {
1862                         v1 = eed->v1->tmp.v;
1863                         if(v1==NULL) v1= adduplicate_vertex(em, eed->v1, flag);
1864                         v2 = eed->v2->tmp.v;
1865                         if(v2==NULL) v2= adduplicate_vertex(em, eed->v2, flag);
1866                         
1867                         newed= addedgelist(em, v1, v2, eed);
1868                         
1869                         newed->f= eed->f;
1870                         eed->f -= flag;
1871                         eed->f |= 128;
1872                 }
1873         }
1874
1875         /* then duplicate faces, again create new vertices if needed */
1876         for(efa= em->faces.last; efa; efa= efa->prev) {
1877                 if(efa->f & flag) {
1878                         v1 = efa->v1->tmp.v;
1879                         if(v1==NULL) v1= adduplicate_vertex(em, efa->v1, flag);
1880                         v2 = efa->v2->tmp.v;
1881                         if(v2==NULL) v2= adduplicate_vertex(em, efa->v2, flag);
1882                         v3 = efa->v3->tmp.v;
1883                         if(v3==NULL) v3= adduplicate_vertex(em, efa->v3, flag);
1884                         if(efa->v4) {
1885                                 v4 = efa->v4->tmp.v; 
1886                                 if(v4==NULL) v4= adduplicate_vertex(em, efa->v4, flag);
1887                         }
1888                         else v4= NULL;
1889                         
1890                         newfa= addfacelist(em, v1, v2, v3, v4, efa, efa); 
1891                         
1892                         if (efa==act_efa) {
1893                                 EM_set_actFace(em, newfa);
1894                         }
1895                         
1896                         newfa->f= efa->f;
1897                         efa->f -= flag;
1898                         efa->f |= 128;
1899                 }
1900         }
1901         
1902         EM_fgon_flags(em);      // redo flags and indices for fgons
1903 }
1904
1905 void delfaceflag(EditMesh *em, int flag)
1906 {
1907         /* delete all faces with 'flag', including loose edges and loose vertices */
1908         /* this is maybe a bit weird, but this function is used for 'split' and 'separate' */
1909         /* in remaining vertices/edges 'flag' is cleared */
1910         EditVert *eve,*nextve;
1911         EditEdge *eed, *nexted;
1912         EditFace *efa,*nextvl;
1913
1914         /* to detect loose edges, we put f2 flag on 1 */
1915         for(eed= em->edges.first; eed; eed= eed->next) {
1916                 if(eed->f & flag) eed->f2= 1;
1917                 else eed->f2= 0;
1918         }
1919         
1920         /* delete faces */
1921         efa= em->faces.first;
1922         while(efa) {
1923                 nextvl= efa->next;
1924                 if(efa->f & flag) {
1925                         
1926                         efa->e1->f2= 1;
1927                         efa->e2->f2= 1;
1928                         efa->e3->f2= 1;
1929                         if(efa->e4) {
1930                                 efa->e4->f2= 1;
1931                         }
1932                                                                 
1933                         BLI_remlink(&em->faces, efa);
1934                         free_editface(em, efa);
1935                 }
1936                 efa= nextvl;
1937         }
1938         
1939         /* all remaining faces: make sure we keep the edges */
1940         for(efa= em->faces.first; efa; efa= efa->next) {
1941                 efa->e1->f2= 0;
1942                 efa->e2->f2= 0;
1943                 efa->e3->f2= 0;
1944                 if(efa->e4) {
1945                         efa->e4->f2= 0;
1946                 }
1947         }
1948         
1949         /* remove tagged edges, and clear remaining ones */
1950         eed= em->edges.first;
1951         while(eed) {
1952                 nexted= eed->next;
1953                 
1954                 if(eed->f2==1) {
1955                         remedge(em, eed);
1956                         free_editedge(em, eed);
1957                 }
1958                 else {
1959                         eed->f &= ~flag;
1960                         eed->v1->f &= ~flag;
1961                         eed->v2->f &= ~flag;
1962                 }
1963                 eed= nexted;
1964         }
1965         
1966         /* vertices with 'flag' now are the loose ones, and will be removed */
1967         eve= em->verts.first;
1968         while(eve) {
1969                 nextve= eve->next;
1970                 if(eve->f & flag) {
1971                         BLI_remlink(&em->verts, eve);
1972                         free_editvert(em, eve);
1973                 }
1974                 eve= nextve;
1975         }
1976
1977 }
1978
1979 /* ********************* */
1980 #if 0
1981 static int check_vnormal_flip(float *n, float *vnorm) 
1982 {
1983         float inp;
1984
1985         inp= n[0]*vnorm[0]+n[1]*vnorm[1]+n[2]*vnorm[2];
1986
1987         /* angles 90 degrees: dont flip */
1988         if(inp> -0.000001) return 0;
1989
1990         return 1;
1991 }
1992 #endif
1993
1994
1995
1996 /* does face centers too */
1997 void recalc_editnormals(EditMesh *em)
1998 {
1999         EditFace *efa;
2000         EditVert *eve;
2001
2002         for(eve= em->verts.first; eve; eve=eve->next) {
2003                 eve->no[0] = eve->no[1] = eve->no[2] = 0.0;
2004         }
2005
2006         for(efa= em->faces.first; efa; efa=efa->next) {
2007                 if(efa->v4) {
2008                         normal_quad_v3( efa->n,efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
2009                         cent_quad_v3(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
2010                         add_v3_v3(efa->v4->no, efa->n);
2011                 }
2012                 else {
2013                         normal_tri_v3( efa->n,efa->v1->co, efa->v2->co, efa->v3->co);
2014                         cent_tri_v3(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co);
2015                 }
2016                 add_v3_v3(efa->v1->no, efa->n);
2017                 add_v3_v3(efa->v2->no, efa->n);
2018                 add_v3_v3(efa->v3->no, efa->n);
2019         }
2020
2021         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
2022         for(eve= em->verts.first; eve; eve=eve->next) {
2023                 if (normalize_v3(eve->no)==0.0) {
2024                         VECCOPY(eve->no, eve->co);
2025                         normalize_v3(eve->no);
2026                 }
2027         }
2028 }
2029
2030 int compareface(EditFace *vl1, EditFace *vl2)
2031 {
2032         EditVert *v1, *v2, *v3, *v4;
2033         
2034         if(vl1->v4 && vl2->v4) {
2035                 v1= vl2->v1;
2036                 v2= vl2->v2;
2037                 v3= vl2->v3;
2038                 v4= vl2->v4;
2039                 
2040                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1 || vl1->v4==v1) {
2041                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2 || vl1->v4==v2) {
2042                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3 || vl1->v4==v3) {
2043                                         if(vl1->v1==v4 || vl1->v2==v4 || vl1->v3==v4 || vl1->v4==v4) {
2044                                                 return 1;
2045                                         }
2046                                 }
2047                         }
2048                 }
2049         }
2050         else if(vl1->v4==0 && vl2->v4==0) {
2051                 v1= vl2->v1;
2052                 v2= vl2->v2;
2053                 v3= vl2->v3;
2054                 
2055                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1) {
2056                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2) {
2057                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3) {
2058                                         return 1;
2059                                 }
2060                         }
2061                 }
2062         }
2063         
2064         return 0;
2065 }
2066
2067 /* checks for existence, not tria overlapping inside quad */
2068 EditFace *exist_face(EditMesh *em, EditVert *v1, EditVert *v2, EditVert *v3, EditVert *v4)
2069 {
2070         EditFace *efa, efatest;
2071         
2072         efatest.v1= v1;
2073         efatest.v2= v2;
2074         efatest.v3= v3;
2075         efatest.v4= v4;
2076         
2077         efa= em->faces.first;
2078         while(efa) {
2079                 if(compareface(&efatest, efa)) return efa;
2080                 efa= efa->next;
2081         }
2082         return NULL;
2083 }
2084
2085 /* evaluate if entire quad is a proper convex quad */
2086 int convex(float *v1, float *v2, float *v3, float *v4)
2087 {
2088         float nor[3], nor1[3], nor2[3], vec[4][2];
2089         
2090         /* define projection, do both trias apart, quad is undefined! */
2091         normal_tri_v3( nor1,v1, v2, v3);
2092         normal_tri_v3( nor2,v1, v3, v4);
2093         nor[0]= ABS(nor1[0]) + ABS(nor2[0]);
2094         nor[1]= ABS(nor1[1]) + ABS(nor2[1]);
2095         nor[2]= ABS(nor1[2]) + ABS(nor2[2]);
2096
2097         if(nor[2] >= nor[0] && nor[2] >= nor[1]) {
2098                 vec[0][0]= v1[0]; vec[0][1]= v1[1];
2099                 vec[1][0]= v2[0]; vec[1][1]= v2[1];
2100                 vec[2][0]= v3[0]; vec[2][1]= v3[1];
2101                 vec[3][0]= v4[0]; vec[3][1]= v4[1];
2102         }
2103         else if(nor[1] >= nor[0] && nor[1]>= nor[2]) {
2104                 vec[0][0]= v1[0]; vec[0][1]= v1[2];
2105                 vec[1][0]= v2[0]; vec[1][1]= v2[2];
2106                 vec[2][0]= v3[0]; vec[2][1]= v3[2];
2107                 vec[3][0]= v4[0]; vec[3][1]= v4[2];
2108         }
2109         else {
2110                 vec[0][0]= v1[1]; vec[0][1]= v1[2];
2111                 vec[1][0]= v2[1]; vec[1][1]= v2[2];
2112                 vec[2][0]= v3[1]; vec[2][1]= v3[2];
2113                 vec[3][0]= v4[1]; vec[3][1]= v4[2];
2114         }
2115         
2116         /* linetests, the 2 diagonals have to instersect to be convex */
2117         if( isect_line_line_v2(vec[0], vec[2], vec[1], vec[3]) > 0 ) return 1;
2118         return 0;
2119 }
2120
2121
2122 /* ********************* Fake Polgon support (FGon) ***************** */
2123
2124
2125 /* results in:
2126    - faces having ->fgonf flag set (also for draw)
2127    - edges having ->fgoni index set (for select)
2128 */
2129
2130 float EM_face_area(EditFace *efa)
2131 {
2132         if(efa->v4) return area_quad_v3(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
2133         else return area_tri_v3(efa->v1->co, efa->v2->co, efa->v3->co);
2134 }
2135
2136 float EM_face_perimeter(EditFace *efa)
2137 {       
2138         if(efa->v4) return
2139                 len_v3v3(efa->v1->co, efa->v2->co)+
2140                 len_v3v3(efa->v2->co, efa->v3->co)+
2141                 len_v3v3(efa->v3->co, efa->v4->co)+
2142                 len_v3v3(efa->v4->co, efa->v1->co);
2143         
2144         else return
2145                 len_v3v3(efa->v1->co, efa->v2->co)+
2146                 len_v3v3(efa->v2->co, efa->v3->co)+
2147                 len_v3v3(efa->v3->co, efa->v1->co);
2148 }
2149
2150 void EM_fgon_flags(EditMesh *em)
2151 {
2152         EditFace *efa, *efan, *efamax;
2153         EditEdge *eed;
2154         ListBase listb={NULL, NULL};
2155         float size, maxsize;
2156         short done, curindex= 1;
2157         
2158         // for each face with fgon edge AND not fgon flag set
2159         for(eed= em->edges.first; eed; eed= eed->next) eed->fgoni= 0;  // index
2160         for(efa= em->faces.first; efa; efa= efa->next) efa->fgonf= 0;  // flag
2161         
2162         // for speed & simplicity, put fgon face candidates in new listbase
2163         efa= em->faces.first;
2164         while(efa) {
2165                 efan= efa->next;
2166                 if( (efa->e1->h & EM_FGON) || (efa->e2->h & EM_FGON) || 
2167                         (efa->e3->h & EM_FGON) || (efa->e4 && (efa->e4->h & EM_FGON)) ) {
2168                         BLI_remlink(&em->faces, efa);
2169                         BLI_addtail(&listb, efa);
2170                 }
2171                 efa= efan;
2172         }
2173         
2174         // find an undone face with fgon edge
2175         for(efa= listb.first; efa; efa= efa->next) {
2176                 if(efa->fgonf==0) {
2177                         
2178                         // init this face
2179                         efa->fgonf= EM_FGON;
2180                         if(efa->e1->h & EM_FGON) efa->e1->fgoni= curindex;
2181                         if(efa->e2->h & EM_FGON) efa->e2->fgoni= curindex;
2182                         if(efa->e3->h & EM_FGON) efa->e3->fgoni= curindex;
2183                         if(efa->e4 && (efa->e4->h & EM_FGON)) efa->e4->fgoni= curindex;
2184                         
2185                         // we search for largest face, to give facedot drawing rights
2186                         maxsize= EM_face_area(efa);
2187                         efamax= efa;
2188                         
2189                         // now flush curendex over edges and set faceflags
2190                         done= 1;
2191                         while(done==1) {
2192                                 done= 0;
2193                                 
2194                                 for(efan= listb.first; efan; efan= efan->next) {
2195                                         if(efan->fgonf==0) {
2196                                                 // if one if its edges has index set, do other too
2197                                                 if( (efan->e1->fgoni==curindex) || (efan->e2->fgoni==curindex) ||
2198                                                         (efan->e3->fgoni==curindex) || (efan->e4 && (efan->e4->fgoni==curindex)) ) {
2199                                                         
2200                                                         efan->fgonf= EM_FGON;
2201                                                         if(efan->e1->h & EM_FGON) efan->e1->fgoni= curindex;
2202                                                         if(efan->e2->h & EM_FGON) efan->e2->fgoni= curindex;
2203                                                         if(efan->e3->h & EM_FGON) efan->e3->fgoni= curindex;
2204                                                         if(efan->e4 && (efan->e4->h & EM_FGON)) efan->e4->fgoni= curindex;
2205                                                         
2206                                                         size= EM_face_area(efan);
2207                                                         if(size>maxsize) {
2208                                                                 efamax= efan;
2209                                                                 maxsize= size;
2210                                                         }
2211                                                         done= 1;
2212                                                 }
2213                                         }
2214                                 }
2215                         }
2216                         
2217                         efamax->fgonf |= EM_FGON_DRAW;
2218                         curindex++;
2219
2220                 }
2221         }
2222
2223         // put fgon face candidates back in listbase
2224         efa= listb.first;
2225         while(efa) {
2226                 efan= efa->next;
2227                 BLI_remlink(&listb, efa);
2228                 BLI_addtail(&em->faces, efa);
2229                 efa= efan;
2230         }
2231         
2232         // remove fgon flags when edge not in fgon (anymore)
2233         for(eed= em->edges.first; eed; eed= eed->next) {
2234                 if(eed->fgoni==0) eed->h &= ~EM_FGON;
2235         }
2236         
2237 }
2238
2239 /* editmesh vertmap, copied from intern.mesh.c
2240  * if do_face_idx_array is 0 it means we need to run it as well as freeing
2241  * */
2242
2243 UvVertMap *EM_make_uv_vert_map(EditMesh *em, int selected, int do_face_idx_array, float *limit)
2244 {
2245         EditVert *ev;
2246         EditFace *efa;
2247         int totverts;
2248         
2249         /* vars from original func */
2250         UvVertMap *vmap;
2251         UvMapVert *buf;
2252         MTFace *tf;
2253         unsigned int a;
2254         int     i, totuv, nverts;
2255         
2256         if (do_face_idx_array)
2257                 EM_init_index_arrays(em, 0, 0, 1);
2258         
2259         /* we need the vert */
2260         for (ev= em->verts.first, totverts=0; ev; ev= ev->next, totverts++) {
2261                 ev->tmp.l = totverts;
2262         }
2263         
2264         totuv = 0;
2265
2266         /* generate UvMapVert array */
2267         for (efa= em->faces.first; efa; efa= efa->next)
2268                 if(!selected || ((!efa->h) && (efa->f & SELECT)))
2269                         totuv += (efa->v4)? 4: 3;
2270                 
2271         if(totuv==0) {
2272                 if (do_face_idx_array)
2273                         EM_free_index_arrays();
2274                 return NULL;
2275         }
2276         vmap= (UvVertMap*)MEM_callocN(sizeof(*vmap), "UvVertMap");
2277         if (!vmap) {
2278                 if (do_face_idx_array)
2279                         EM_free_index_arrays();
2280                 return NULL;
2281         }
2282
2283         vmap->vert= (UvMapVert**)MEM_callocN(sizeof(*vmap->vert)*totverts, "UvMapVert*");
2284         buf= vmap->buf= (UvMapVert*)MEM_callocN(sizeof(*vmap->buf)*totuv, "UvMapVert");
2285
2286         if (!vmap->vert || !vmap->buf) {
2287                 free_uv_vert_map(vmap);
2288                 if (do_face_idx_array)
2289                         EM_free_index_arrays();
2290                 return NULL;
2291         }
2292
2293         for (a=0, efa= em->faces.first; efa; a++, efa= efa->next) {
2294                 if(!selected || ((!efa->h) && (efa->f & SELECT))) {
2295                         nverts= (efa->v4)? 4: 3;
2296                         
2297                         for(i=0; i<nverts; i++) {
2298                                 buf->tfindex= i;
2299                                 buf->f= a;
2300                                 buf->separate = 0;
2301                                 
2302                                 buf->next= vmap->vert[(*(&efa->v1 + i))->tmp.l];
2303                                 vmap->vert[(*(&efa->v1 + i))->tmp.l]= buf;
2304                                 
2305                                 buf++;
2306                         }
2307                 }
2308         }
2309         
2310         /* sort individual uvs for each vert */
2311         for(a=0, ev=em->verts.first; ev; a++, ev= ev->next) {
2312                 UvMapVert *newvlist= NULL, *vlist=vmap->vert[a];
2313                 UvMapVert *iterv, *v, *lastv, *next;
2314                 float *uv, *uv2, uvdiff[2];
2315
2316                 while(vlist) {
2317                         v= vlist;
2318                         vlist= vlist->next;
2319                         v->next= newvlist;
2320                         newvlist= v;
2321
2322                         efa = EM_get_face_for_index(v->f);
2323                         tf = CustomData_em_get(&em->fdata, efa->data, CD_MTFACE);
2324                         uv = tf->uv[v->tfindex]; 
2325                         
2326                         lastv= NULL;
2327                         iterv= vlist;
2328
2329                         while(iterv) {
2330                                 next= iterv->next;
2331                                 efa = EM_get_face_for_index(iterv->f);
2332                                 tf = CustomData_em_get(&em->fdata, efa->data, CD_MTFACE);
2333                                 uv2 = tf->uv[iterv->tfindex];
2334                                 
2335                                 sub_v2_v2v2(uvdiff, uv2, uv);
2336
2337                                 if(fabs(uv[0]-uv2[0]) < limit[0] && fabs(uv[1]-uv2[1]) < limit[1]) {
2338                                         if(lastv) lastv->next= next;
2339                                         else vlist= next;
2340                                         iterv->next= newvlist;
2341                                         newvlist= iterv;
2342                                 }
2343                                 else
2344                                         lastv=iterv;
2345
2346                                 iterv= next;
2347                         }
2348
2349                         newvlist->separate = 1;
2350                 }
2351
2352                 vmap->vert[a]= newvlist;
2353         }
2354         
2355         if (do_face_idx_array)
2356                 EM_free_index_arrays();
2357         
2358         return vmap;
2359 }
2360
2361 UvMapVert *EM_get_uv_map_vert(UvVertMap *vmap, unsigned int v)
2362 {
2363         return vmap->vert[v];
2364 }
2365
2366 void EM_free_uv_vert_map(UvVertMap *vmap)
2367 {
2368         if (vmap) {
2369                 if (vmap->vert) MEM_freeN(vmap->vert);
2370                 if (vmap->buf) MEM_freeN(vmap->buf);
2371                 MEM_freeN(vmap);
2372         }
2373 }
2374
2375 /* poll call for mesh operators requiring a view3d context */
2376 int EM_view3d_poll(bContext *C)
2377 {
2378         if(ED_operator_editmesh(C) && ED_operator_view3d_active(C))
2379                 return 1;
2380         return 0;
2381 }
2382
2383 /* higher quality normals */
2384
2385 /* NormalCalc */
2386 /* NormalCalc modifier: calculates higher quality normals
2387 */
2388
2389 /* each edge uses this to  */
2390 typedef struct EdgeFaceRef {
2391         int f1; /* init as -1 */
2392         int f2;
2393 } EdgeFaceRef;
2394
2395 void EM_make_hq_normals(EditMesh *em)
2396 {
2397         EditFace *efa;
2398         EditVert *eve;
2399         int i;
2400
2401         EdgeHash *edge_hash = BLI_edgehash_new();
2402         EdgeHashIterator *edge_iter;
2403         int edge_ref_count = 0;
2404         int ed_v1, ed_v2; /* use when getting the key */
2405         EdgeFaceRef *edge_ref_array = MEM_callocN(em->totedge * sizeof(EdgeFaceRef), "Edge Connectivity");
2406         EdgeFaceRef *edge_ref;
2407         float edge_normal[3];
2408
2409         EM_init_index_arrays(em, 1, 1, 1);
2410
2411         for(eve= em->verts.first, i=0; eve; eve= eve->next, i++) {
2412                 zero_v3(eve->no);
2413                 eve->tmp.l= i;
2414         }
2415
2416         /* This function adds an edge hash if its not there, and adds the face index */
2417 #define NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(EDV1, EDV2); \
2418                         edge_ref = (EdgeFaceRef *)BLI_edgehash_lookup(edge_hash, EDV1, EDV2); \
2419                         if (!edge_ref) { \
2420                                 edge_ref = &edge_ref_array[edge_ref_count]; edge_ref_count++; \
2421                                 edge_ref->f1=i; \
2422                                 edge_ref->f2=-1; \
2423                                 BLI_edgehash_insert(edge_hash, EDV1, EDV2, edge_ref); \
2424                         } else { \
2425                                 edge_ref->f2=i; \
2426                         }
2427
2428
2429         efa= em->faces.first;
2430         for(i = 0; i < em->totface; i++, efa= efa->next) {
2431                 if(efa->v4) {
2432                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v1->tmp.l, efa->v2->tmp.l);
2433                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v2->tmp.l, efa->v3->tmp.l);
2434                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v3->tmp.l, efa->v4->tmp.l);
2435                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v4->tmp.l, efa->v1->tmp.l);
2436                 } else {
2437                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v1->tmp.l, efa->v2->tmp.l);
2438                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v2->tmp.l, efa->v3->tmp.l);
2439                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v3->tmp.l, efa->v1->tmp.l);
2440                 }
2441         }
2442
2443 #undef NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE
2444
2445
2446         for(edge_iter = BLI_edgehashIterator_new(edge_hash); !BLI_edgehashIterator_isDone(edge_iter); BLI_edgehashIterator_step(edge_iter)) {
2447                 /* Get the edge vert indicies, and edge value (the face indicies that use it)*/
2448                 BLI_edgehashIterator_getKey(edge_iter, (int*)&ed_v1, (int*)&ed_v2);
2449                 edge_ref = BLI_edgehashIterator_getValue(edge_iter);
2450
2451                 if (edge_ref->f2 != -1) {
2452                         EditFace *ef1= EM_get_face_for_index(edge_ref->f1), *ef2= EM_get_face_for_index(edge_ref->f2);
2453                         float angle= angle_normalized_v3v3(ef1->n, ef2->n);
2454                         if(angle > 0.0f) {
2455                                 /* We have 2 faces using this edge, calculate the edges normal
2456                                  * using the angle between the 2 faces as a weighting */
2457                                 add_v3_v3v3(edge_normal, ef1->n, ef2->n);
2458                                 normalize_v3(edge_normal);
2459                                 mul_v3_fl(edge_normal, angle);
2460                         }
2461                         else {
2462                                 /* cant do anything useful here!
2463                                    Set the face index for a vert incase it gets a zero normal */
2464                                 EM_get_vert_for_index(ed_v1)->tmp.l=
2465                                 EM_get_vert_for_index(ed_v2)->tmp.l= -(edge_ref->f1 + 1);
2466                                 continue;
2467                         }
2468                 } else {
2469                         /* only one face attached to that edge */
2470                         /* an edge without another attached- the weight on this is
2471                          * undefined, M_PI/2 is 90d in radians and that seems good enough */
2472                         VECCOPY(edge_normal, EM_get_face_for_index(edge_ref->f1)->n)
2473                         mul_v3_fl(edge_normal, M_PI/2);
2474                 }
2475                 add_v3_v3(EM_get_vert_for_index(ed_v1)->no, edge_normal );
2476                 add_v3_v3(EM_get_vert_for_index(ed_v2)->no, edge_normal );
2477
2478
2479         }
2480         BLI_edgehashIterator_free(edge_iter);
2481         BLI_edgehash_free(edge_hash, NULL);
2482         MEM_freeN(edge_ref_array);
2483
2484         /* normalize vertex normals and assign */
2485         for(eve= em->verts.first; eve; eve= eve->next) {
2486                 if(normalize_v3(eve->no) == 0.0f && eve->tmp.l < 0) {
2487                         /* exceptional case, totally flat */
2488                         efa= EM_get_face_for_index(-(eve->tmp.l) - 1);
2489                         VECCOPY(eve->no, efa->n);
2490                 }       
2491         }
2492
2493         EM_free_index_arrays();
2494 }
2495
2496 void EM_solidify(EditMesh *em, float dist)
2497 {
2498         EditFace *efa;
2499         EditVert *eve;
2500         float *vert_angles= MEM_callocN(sizeof(float) * em->totvert * 2, "EM_solidify"); /* 2 in 1 */
2501         float *vert_accum= vert_angles + em->totvert;
2502         float face_angles[4];
2503         int i, j;
2504
2505         for(eve= em->verts.first, i=0; eve; eve= eve->next, i++) {
2506                 eve->tmp.l= i;
2507         }
2508
2509         efa= em->faces.first;
2510         for(i = 0; i < em->totface; i++, efa= efa->next) {
2511
2512                 if(!(efa->f & SELECT))
2513                         continue;
2514
2515                 if(efa->v4) {
2516                         angle_quad_v3(face_angles, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
2517                         j= 3;
2518                 }
2519                 else {
2520                         angle_tri_v3(face_angles, efa->v1->co, efa->v2->co, efa->v3->co);
2521                         j= 2;
2522                 }
2523
2524                 for(; j>=0; j--) {
2525                         eve= *(&efa->v1 + j);
2526                         vert_accum[eve->tmp.l] += face_angles[j];
2527                         vert_angles[eve->tmp.l]+= shell_angle_to_dist(angle_normalized_v3v3(eve->no, efa->n)) * face_angles[j];
2528                 }
2529         }
2530
2531         for(eve= em->verts.first, i=0; eve; eve= eve->next, i++) {
2532                 if(vert_accum[i]) { /* zero if unselected */
2533                         madd_v3_v3fl(eve->co, eve->no, dist * vert_angles[i] / vert_accum[i]);
2534                 }
2535         }
2536
2537         MEM_freeN(vert_angles);
2538 }
2539
2540 /* not that optimal!, should be nicer with bmesh */
2541 static void tag_face_edges(EditFace *efa)
2542 {
2543         if(efa->v4)
2544                 efa->e1->tmp.l= efa->e2->tmp.l= efa->e3->tmp.l= efa->e4->tmp.l= 1;
2545         else
2546                 efa->e1->tmp.l= efa->e2->tmp.l= efa->e3->tmp.l= 1;
2547 }
2548 static int tag_face_edges_test(EditFace *efa)
2549 {
2550         if(efa->v4)
2551                 return (efa->e1->tmp.l || efa->e2->tmp.l || efa->e3->tmp.l || efa->e4->tmp.l) ? 1:0;
2552         else
2553                 return (efa->e1->tmp.l || efa->e2->tmp.l || efa->e3->tmp.l) ? 1:0;
2554 }
2555
2556 void em_deselect_nth_face(EditMesh *em, int nth, EditFace *efa_act)
2557 {
2558         EditFace *efa;
2559         EditEdge *eed;
2560         int ok= 1;
2561
2562         if(efa_act==NULL) {
2563                 return;
2564         }
2565
2566         /* to detect loose edges, we put f2 flag on 1 */
2567         for(eed= em->edges.first; eed; eed= eed->next) {
2568                 eed->tmp.l= 0;
2569         }
2570
2571         for (efa= em->faces.first; efa; efa= efa->next) {
2572                 efa->tmp.l = 0;
2573         }
2574
2575         efa_act->tmp.l = 1;
2576
2577         while(ok) {
2578                 ok = 0;
2579
2580                 for (efa= em->faces.first; efa; efa= efa->next) {
2581                         if(efa->f & SELECT) {
2582                                 if(efa->tmp.l==1) { /* initialize */
2583                                         tag_face_edges(efa);
2584                                 }
2585         
2586                                 if(efa->tmp.l) {
2587                                         efa->tmp.l++;
2588                                 }
2589                         }
2590                 }
2591
2592                 for (efa= em->faces.first; efa; efa= efa->next) {
2593                         if(efa->f & SELECT) {
2594                                 if(efa->tmp.l==0 && tag_face_edges_test(efa)) {
2595                                         efa->tmp.l= 1;
2596                                         ok = 1; /* keep looping */
2597                                 }
2598                         }
2599                 }
2600         }
2601
2602         for (efa= em->faces.first; efa; efa= efa->next) {
2603                 if(efa->tmp.l > 0 && efa->tmp.l % nth) {
2604                         EM_select_face(efa, 0);
2605                 }
2606         }
2607         for (efa= em->faces.first; efa; efa= efa->next) {
2608                 if(efa->f & SELECT) {
2609                         EM_select_face(efa, 1);
2610                 }
2611         }
2612
2613         EM_nvertices_selected(em);
2614         EM_nedges_selected(em);
2615         EM_nfaces_selected(em);
2616 }
2617
2618 /* not that optimal!, should be nicer with bmesh */
2619 static void tag_edge_verts(EditEdge *eed)
2620 {
2621         eed->v1->tmp.l= eed->v2->tmp.l= 1;
2622 }
2623 static int tag_edge_verts_test(EditEdge *eed)
2624 {
2625         return (eed->v1->tmp.l || eed->v2->tmp.l) ? 1:0;
2626 }
2627
2628 void em_deselect_nth_edge(EditMesh *em, int nth, EditEdge *eed_act)
2629 {
2630         EditEdge *eed;
2631         EditVert *eve;
2632         int ok= 1;
2633
2634         if(eed_act==NULL) {
2635                 return;
2636         }
2637
2638         for(eve= em->verts.first; eve; eve= eve->next) {
2639                 eve->tmp.l= 0;
2640         }
2641
2642         for (eed= em->edges.first; eed; eed= eed->next) {
2643                 eed->tmp.l = 0;
2644         }
2645
2646         eed_act->tmp.l = 1;
2647
2648         while(ok) {
2649                 ok = 0;
2650
2651                 for (eed= em->edges.first; eed; eed= eed->next) {
2652                         if(eed->f & SELECT) {
2653                                 if(eed->tmp.l==1) { /* initialize */
2654                                         tag_edge_verts(eed);
2655                                 }
2656         
2657                                 if(eed->tmp.l) {
2658                                         eed->tmp.l++;
2659                                 }
2660                         }
2661                 }
2662
2663                 for (eed= em->edges.first; eed; eed= eed->next) {
2664                         if(eed->f & SELECT) {
2665                                 if(eed->tmp.l==0 && tag_edge_verts_test(eed)) {
2666                                         eed->tmp.l= 1;
2667                                         ok = 1; /* keep looping */
2668                                 }
2669                         }
2670                 }
2671         }
2672
2673         for (eed= em->edges.first; eed; eed= eed->next) {
2674                 if(eed->tmp.l > 0 && eed->tmp.l % nth) {
2675                         EM_select_edge(eed, 0);
2676                 }
2677         }
2678         for (eed= em->edges.first; eed; eed= eed->next) {
2679                 if(eed->f & SELECT) {
2680                         EM_select_edge(eed, 1);
2681                 }
2682         }
2683
2684         {
2685                 /* grr, should be a function */
2686                 EditFace *efa;
2687                 for (efa= em->faces.first; efa; efa= efa->next) {
2688                         if(efa->v4) {
2689                                 if(efa->e1->f & efa->e2->f & efa->e3->f & efa->e4->f & SELECT );
2690                                 else efa->f &= ~SELECT;
2691                         }
2692                         else {
2693                                 if(efa->e1->f & efa->e2->f & efa->e3->f & SELECT );
2694                                 else efa->f &= ~SELECT;
2695                         }
2696                 }
2697         }
2698
2699         EM_nvertices_selected(em);
2700         EM_nedges_selected(em);
2701         EM_nfaces_selected(em);
2702 }
2703
2704 void em_deselect_nth_vert(EditMesh *em, int nth, EditVert *eve_act)
2705 {
2706         EditVert *eve;
2707         EditEdge *eed;
2708         int ok= 1;
2709
2710         if(eve_act==NULL) {
2711                 return;
2712         }
2713
2714         for (eve= em->verts.first; eve; eve= eve->next) {
2715                 eve->tmp.l = 0;
2716         }
2717
2718         eve_act->tmp.l = 1;
2719
2720         while(ok) {
2721                 ok = 0;
2722
2723                 for (eve= em->verts.first; eve; eve= eve->next) {
2724                         if(eve->f & SELECT) {
2725                                 if(eve->tmp.l)
2726                                         eve->tmp.l++;
2727                         }
2728                 }
2729
2730                 for (eed= em->edges.first; eed; eed= eed->next) {
2731                         if(eed->f & SELECT) {
2732                                 if(eed->v1->tmp.l==2 && eed->v2->tmp.l==0) { /* initialize */
2733                                         eed->v2->tmp.l= 1;
2734                                         ok = 1; /* keep looping */
2735                                 }
2736                                 else if(eed->v2->tmp.l==2 && eed->v1->tmp.l==0) { /* initialize */
2737                                         eed->v1->tmp.l= 1;
2738                                         ok = 1; /* keep looping */
2739                                 }
2740                         }
2741                 }
2742         }
2743
2744         for (eve= em->verts.first; eve; eve= eve->next) {
2745                 if(eve->tmp.l > 0 && eve->tmp.l % nth) {
2746                         eve->f &= ~SELECT;
2747                 }
2748         }
2749
2750         EM_deselect_flush(em);
2751
2752         EM_nvertices_selected(em);
2753         // EM_nedges_selected(em); // flush does these
2754         // EM_nfaces_selected(em); // flush does these
2755 }
2756
2757 static void deselect_nth_active(EditMesh *em, EditVert **eve_p, EditEdge **eed_p, EditFace **efa_p)
2758 {
2759         EditSelection *ese;
2760
2761         *eve_p= NULL;
2762         *eed_p= NULL;
2763         *efa_p= NULL;
2764
2765         ese= (EditSelection*)em->selected.last;
2766
2767         if(ese) {
2768                 switch(ese->type) {
2769                 case EDITVERT:
2770                         *eve_p= (EditVert *)ese->data;
2771                         return;
2772                 case EDITEDGE:
2773                         *eed_p= (EditEdge *)ese->data;
2774                         return;
2775                 case EDITFACE:
2776                         *efa_p= (EditFace *)ese->data;
2777                         return;
2778                 }
2779         }
2780
2781         if(em->selectmode & SCE_SELECT_VERTEX) {
2782                 EditVert *eve;
2783                 for (eve= em->verts.first; eve; eve= eve->next) {
2784                         if(eve->f & SELECT) {
2785                                 *eve_p= eve;
2786                                 return;
2787                         }
2788                 }
2789         }
2790
2791         if(em->selectmode & SCE_SELECT_EDGE) {
2792                 EditEdge *eed;
2793                 for (eed= em->edges.first; eed; eed= eed->next) {
2794                         if(eed->f & SELECT) {
2795                                 *eed_p= eed;
2796                                 return;
2797                         }
2798                 }
2799         }
2800
2801         if(em->selectmode & SCE_SELECT_FACE) {
2802                 EditFace *efa= EM_get_actFace(em, 1);
2803                 if(efa) {
2804                         *efa_p= efa;
2805                         return;
2806                 }
2807         }
2808 }
2809
2810 int EM_deselect_nth(EditMesh *em, int nth)
2811 {
2812         EditVert *eve;
2813         EditEdge *eed;
2814         EditFace *efa;
2815
2816         deselect_nth_active(em, &eve, &eed, &efa);
2817
2818         if(eve)
2819                 em_deselect_nth_vert(em, nth, eve);
2820         else if (eed)
2821                 em_deselect_nth_edge(em, nth, eed);
2822         else if (efa)
2823                 em_deselect_nth_face(em, nth, efa);
2824         else
2825                 return 0;
2826         
2827         return 1;
2828 }
2829
2830 void EM_project_snap_verts(bContext *C, ARegion *ar, Object *obedit, EditMesh *em)
2831 {
2832         EditVert *eve;
2833         for(eve= em->verts.first;eve; eve=eve->next) {
2834                 if(eve->f & SELECT) {
2835                         float mval[2], vec[3], no_dummy[3];
2836                         int dist_dummy;
2837                         mul_v3_m4v3(vec, obedit->obmat, eve->co);
2838                         project_float_noclip(ar, vec, mval);
2839                         if(snapObjectsContext(C, mval, &dist_dummy, vec, no_dummy, SNAP_NOT_OBEDIT)) {
2840                                 mul_v3_m4v3(eve->co, obedit->imat, vec);
2841                         }
2842                 }
2843         }
2844 }