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