bc670c47940886f4b5e1185f440f5e3f263abf57
[blender.git] / source / blender / editors / mesh / editmesh_lib.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version.
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2004 by Blender Foundation
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 /*
31
32 editmesh_lib: generic (no UI, no menus) operations/evaluators for editmesh data
33
34 */
35
36 #include <stdlib.h>
37 #include <string.h>
38 #include <math.h>
39
40 #include "MEM_guardedalloc.h"
41
42 #include "DNA_meshdata_types.h"
43 #include "DNA_modifier_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_scene_types.h"
46
47 #include "BLI_blenlib.h"
48 #include "BLI_math.h"
49 #include "BLI_editVert.h"
50 #include "BLI_edgehash.h"
51 #include "BLI_utildefines.h"
52
53 #include "BKE_customdata.h"
54 #include "BKE_context.h"
55 #include "BKE_global.h"
56 #include "BKE_mesh.h"
57
58
59 #include "ED_mesh.h"
60 #include "ED_screen.h"
61 #include "ED_view3d.h"
62 #include "ED_transform.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 UNUSED(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 predictable */
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                 BLI_movelisttolist(&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, const char *name)
973 {
974         CustomData olddata;
975
976         olddata= *data;
977         olddata.layers= (olddata.layers)? MEM_dupallocN(olddata.layers): NULL;
978         CustomData_add_layer_named(data, type, CD_CALLOC, NULL, 0, name);
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_v3(nor, add);
1002         else
1003                 add_v3_v3(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 UNUSED(flag), float *UNUSED(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 *UNUSED(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 UNUSED(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_m4_v3(mtx, co1);
1322                                                         mul_m4_v3(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(efa->v4)
1396                                 efan = addfacelist(em, efa->v1->tmp.v, efa->v2->tmp.v,
1397                                                         efa->v3->tmp.v, efa->v4->tmp.v, efa, efa);
1398                         else
1399                                 efan = addfacelist(em, efa->v1->tmp.v, efa->v2->tmp.v,
1400                                                         efa->v3->tmp.v, NULL, efa, efa);
1401
1402                         /* keep old faces means flipping normal, reverse vertex order gives bad UV's & VCols etc - [#25260] */
1403                         if(del_old==0) {
1404                                 flipface(em, efan);
1405                         }
1406
1407                         if (em->act_face == efa) {
1408                                 em->act_face = efan; 
1409                         }
1410
1411                         /* for transform */
1412                         add_normal_aligned(nor, efa->n);
1413                 }
1414         }
1415         
1416         if(del_old) {
1417                 
1418                 /* step 4: remove old faces, if del_old */
1419                 efa= em->faces.first;
1420                 while(efa) {
1421                         nextfa= efa->next;
1422                         if(efa->f & SELECT) {
1423                                 BLI_remlink(&em->faces, efa);
1424                                 free_editface(em, efa);
1425                         }
1426                         efa= nextfa;
1427                 }
1428                 
1429                 
1430                 /* step 5: remove selected unused edges */
1431                 /* start tagging again */
1432                 for(eed= em->edges.first; eed; eed= eed->next) eed->f1=0;
1433                 for(efa= em->faces.first; efa; efa= efa->next) {
1434                         efa->e1->f1= 1;
1435                         efa->e2->f1= 1;
1436                         efa->e3->f1= 1;
1437                         if(efa->e4) efa->e4->f1= 1;
1438                 }
1439                 /* remove */
1440                 eed= em->edges.first; 
1441                 while(eed) {
1442                         nexted= eed->next;
1443                         if(eed->f & SELECT) {
1444                                 if(eed->f1==0) {
1445                                         remedge(em, eed);
1446                                         free_editedge(em, eed);
1447                                 }
1448                         }
1449                         eed= nexted;
1450                 }
1451         
1452                 /* step 6: remove selected unused vertices */
1453                 for(eed= em->edges.first; eed; eed= eed->next) 
1454                         eed->v1->f1= eed->v2->f1= 0;
1455                 
1456                 eve= em->verts.first;
1457                 while(eve) {
1458                         nextve= eve->next;
1459                         if(eve->f1) {
1460                                 // hack... but we need it for step 7, redoing selection
1461                                 if(eve->tmp.v) eve->tmp.v->tmp.v= eve->tmp.v;
1462                                 
1463                                 BLI_remlink(&em->verts, eve);
1464                                 free_editvert(em, eve);
1465                         }
1466                         eve= nextve;
1467                 }
1468         }
1469         
1470         normalize_v3(nor);      // translation normal grab
1471         
1472         /* step 7: redo selection */
1473         EM_clear_flag_all(em, SELECT);
1474
1475         for(eve= em->verts.first; eve; eve= eve->next) {
1476                 if(eve->tmp.v) {
1477                         eve->tmp.v->f |= SELECT;
1478                 }
1479         }
1480
1481         EM_select_flush(em);
1482
1483         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // grab
1484         return 'n'; // normal constraint 
1485 }
1486
1487 short extrudeflag_vert(Object *obedit, EditMesh *em, short flag, float *nor, int all)
1488 {
1489         /* all verts/edges/faces with (f & 'flag'): extrude */
1490         /* from old verts, 'flag' is cleared, in new ones it is set */
1491         EditVert *eve, *v1, *v2, *v3, *v4, *nextve;
1492         EditEdge *eed, *e1, *e2, *e3, *e4, *nexted;
1493         EditFace *efa, *efa2, *nextvl;
1494         short sel=0, del_old= 0, is_face_sel=0;
1495         ModifierData *md;
1496
1497         if(em==NULL) return 0;
1498
1499         md = obedit->modifiers.first;
1500
1501         /* clear vert flag f1, we use this to detect a loose selected vertice */
1502         eve= em->verts.first;
1503         while(eve) {
1504                 if(eve->f & flag) eve->f1= 1;
1505                 else eve->f1= 0;
1506                 eve= eve->next;
1507         }
1508         /* clear edges counter flag, if selected we set it at 1 */
1509         eed= em->edges.first;
1510         while(eed) {
1511                 if( (eed->v1->f & flag) && (eed->v2->f & flag) ) {
1512                         eed->f2= 1;
1513                         eed->v1->f1= 0;
1514                         eed->v2->f1= 0;
1515                 }
1516                 else eed->f2= 0;
1517                 
1518                 eed->f1= 1;             /* this indicates it is an 'old' edge (in this routine we make new ones) */
1519                 eed->tmp.f = NULL;      /* used as sample */
1520                 
1521                 eed= eed->next;
1522         }
1523
1524         /* we set a flag in all selected faces, and increase the associated edge counters */
1525
1526         efa= em->faces.first;
1527         while(efa) {
1528                 efa->f1= 0;
1529
1530                 if(faceselectedAND(efa, flag)) {
1531                         e1= efa->e1;
1532                         e2= efa->e2;
1533                         e3= efa->e3;
1534                         e4= efa->e4;
1535
1536                         if(e1->f2 < 3) e1->f2++;
1537                         if(e2->f2 < 3) e2->f2++;
1538                         if(e3->f2 < 3) e3->f2++;
1539                         if(e4 && e4->f2 < 3) e4->f2++;
1540                         
1541                         efa->f1= 1;
1542                         is_face_sel= 1; // for del_old
1543                 }
1544                 else if(faceselectedOR(efa, flag)) {
1545                         e1= efa->e1;
1546                         e2= efa->e2;
1547                         e3= efa->e3;
1548                         e4= efa->e4;
1549                         
1550                         if( (e1->v1->f & flag) && (e1->v2->f & flag) ) e1->f1= 2;
1551                         if( (e2->v1->f & flag) && (e2->v2->f & flag) ) e2->f1= 2;
1552                         if( (e3->v1->f & flag) && (e3->v2->f & flag) ) e3->f1= 2;
1553                         if( e4 && (e4->v1->f & flag) && (e4->v2->f & flag) ) e4->f1= 2;
1554                 }
1555                 
1556                 // sample for next loop
1557                 efa->e1->tmp.f = efa;
1558                 efa->e2->tmp.f = efa;
1559                 efa->e3->tmp.f = efa;
1560                 if(efa->e4) efa->e4->tmp.f = efa;
1561
1562                 efa= efa->next;
1563         }
1564
1565         set_edge_directions_f2(em, 3);
1566
1567         /* the current state now is:
1568                 eve->f1==1: loose selected vertex 
1569
1570                 eed->f2==0 : edge is not selected, no extrude
1571                 eed->f2==1 : edge selected, is not part of a face, extrude
1572                 eed->f2==2 : edge selected, is part of 1 face, extrude
1573                 eed->f2==3 : edge selected, is part of more faces, no extrude
1574                 
1575                 eed->f1==0: new edge
1576                 eed->f1==1: edge selected, is part of selected face, when eed->f==3: remove
1577                 eed->f1==2: edge selected, part of a partially selected face
1578                                         
1579                 efa->f1==1 : duplicate this face
1580         */
1581
1582         /* If a mirror modifier with clipping is on, we need to adjust some 
1583          * of the cases above to handle edges on the line of symmetry.
1584          */
1585         for (; md; md=md->next) {
1586                 if (md->type==eModifierType_Mirror) {
1587                         MirrorModifierData *mmd = (MirrorModifierData*) md;     
1588                 
1589                         if(mmd->flag & MOD_MIR_CLIPPING) {
1590                                 float mtx[4][4];
1591                                 if (mmd->mirror_ob) {
1592                                         float imtx[4][4];
1593                                         invert_m4_m4(imtx, mmd->mirror_ob->obmat);
1594                                         mul_m4_m4m4(mtx, obedit->obmat, imtx);
1595                                 }
1596
1597                                 for (eed= em->edges.first; eed; eed= eed->next) {
1598                                         if(eed->f2 == 2) {
1599                                                 float co1[3], co2[3];
1600
1601                                                 copy_v3_v3(co1, eed->v1->co);
1602                                                 copy_v3_v3(co2, eed->v2->co);
1603
1604                                                 if (mmd->mirror_ob) {
1605                                                         mul_m4_v3(mtx, co1);
1606                                                         mul_m4_v3(mtx, co2);
1607                                                 }
1608
1609                                                 if (mmd->flag & MOD_MIR_AXIS_X)
1610                                                         if ( (fabs(co1[0]) < mmd->tolerance) &&
1611                                                                  (fabs(co2[0]) < mmd->tolerance) )
1612                                                                 ++eed->f2;
1613
1614                                                 if (mmd->flag & MOD_MIR_AXIS_Y)
1615                                                         if ( (fabs(co1[1]) < mmd->tolerance) &&
1616                                                                  (fabs(co2[1]) < mmd->tolerance) )
1617                                                                 ++eed->f2;
1618                                                 if (mmd->flag & MOD_MIR_AXIS_Z)
1619                                                         if ( (fabs(co1[2]) < mmd->tolerance) &&
1620                                                                  (fabs(co2[2]) < mmd->tolerance) )
1621                                                                 ++eed->f2;
1622                                         }
1623                                 }
1624                         }
1625                 }
1626         }
1627
1628         /* copy all selected vertices, */
1629         /* write pointer to new vert in old struct at eve->tmp.v */
1630         eve= em->verts.last;
1631         while(eve) {
1632                 eve->f &= ~128;  /* clear, for later test for loose verts */
1633                 if(eve->f & flag) {
1634                         sel= 1;
1635                         v1= addvertlist(em, 0, NULL);
1636                         
1637                         VECCOPY(v1->co, eve->co);
1638                         VECCOPY(v1->no, eve->no);
1639                         v1->f= eve->f;
1640                         eve->f &= ~flag;
1641                         eve->tmp.v = v1;
1642                 }
1643                 else eve->tmp.v = NULL;
1644                 eve= eve->prev;
1645         }
1646
1647         if(sel==0) return 0;
1648
1649         /* all edges with eed->f2==1 or eed->f2==2 become faces */
1650         
1651         /* if del_old==1 then extrude is in partial geometry, to keep it manifold.
1652                                          verts with f1==0 and (eve->f & 128)==0) are removed
1653                                          edges with eed->f2>2 are removed
1654                                          faces with efa->f1 are removed
1655            if del_old==0 the extrude creates a volume.
1656         */
1657         
1658          /* find if we delete old faces */
1659         if(is_face_sel && all==0) {
1660                 for(eed= em->edges.first; eed; eed= eed->next) {
1661                         if( (eed->f2==1 || eed->f2==2) ) {
1662                                 if(eed->f1==2) {
1663                                         del_old= 1;
1664                                         break;
1665                                 }
1666                         }
1667                 }
1668         }
1669         
1670         eed= em->edges.last;
1671         while(eed) {
1672                 nexted= eed->prev;
1673                 if( eed->f2<3) {
1674                         eed->v1->f |= 128;  /* = no loose vert! */
1675                         eed->v2->f |= 128;
1676                 }
1677                 if( (eed->f2==1 || eed->f2==2) ) {
1678         
1679                         /* if del_old, the preferred normal direction is exact opposite as for keep old faces */
1680                         if(eed->dir != del_old) 
1681                                 efa2 = addfacelist(em, eed->v1, eed->v2, 
1682                                                                   eed->v2->tmp.v, eed->v1->tmp.v, 
1683                                                                   eed->tmp.f, NULL);
1684                         else 
1685                                 efa2 = addfacelist(em, eed->v2, eed->v1, 
1686                                                                    eed->v1->tmp.v, eed->v2->tmp.v, 
1687                                                                    eed->tmp.f, NULL);
1688                         
1689                         /* Needs smarter adaption of existing creases.
1690                          * If addedgelist is used, make sure seams are set to 0 on these
1691                          * new edges, since we do not want to add any seams on extrusion.
1692                          */
1693                         efa2->e1->crease= eed->crease;
1694                         efa2->e2->crease= eed->crease;
1695                         efa2->e3->crease= eed->crease;
1696                         if(efa2->e4) efa2->e4->crease= eed->crease;
1697                 }
1698
1699                 eed= nexted;
1700         }
1701         
1702         /* duplicate faces, if necessary remove old ones  */
1703         efa= em->faces.first;
1704         while(efa) {
1705                 nextvl= efa->next;
1706                 if(efa->f1 & 1) {
1707                 
1708                         v1 = efa->v1->tmp.v;
1709                         v2 = efa->v2->tmp.v;
1710                         v3 = efa->v3->tmp.v;
1711                         if(efa->v4) 
1712                                 v4 = efa->v4->tmp.v; 
1713                         else
1714                                 v4= NULL;
1715
1716                         /* hmm .. not sure about edges here */
1717                         if(del_old==0)  // if we keep old, we flip normal
1718                                 efa2= addfacelist(em, v3, v2, v1, v4, efa, efa); 
1719                         else
1720                                 efa2= addfacelist(em, v1, v2, v3, v4, efa, efa);
1721                         
1722                         /* for transform */
1723                         add_normal_aligned(nor, efa->n);
1724
1725                         if(del_old) {
1726                                 BLI_remlink(&em->faces, efa);
1727                                 free_editface(em, efa);
1728                         }
1729                 }
1730                 efa= nextvl;
1731         }
1732         /* delete edges after copying edges above! */
1733         if(del_old) {
1734                 eed= em->edges.first;
1735                 while(eed) {
1736                         nexted= eed->next;
1737                         if(eed->f2==3 && eed->f1==1) {
1738                                 remedge(em, eed);
1739                                 free_editedge(em, eed);
1740                         }
1741                         eed= nexted;
1742                 }
1743         }
1744         
1745         normalize_v3(nor);      // for grab
1746         
1747         /* for all vertices with eve->tmp.v!=0 
1748                 if eve->f1==1: make edge
1749                 if flag!=128 : if del_old==1: remove
1750         */
1751         eve= em->verts.last;
1752         while(eve) {
1753                 nextve= eve->prev;
1754                 if(eve->tmp.v) {
1755                         if(eve->f1==1) addedgelist(em, eve, eve->tmp.v, NULL);
1756                         else if( (eve->f & 128)==0) {
1757                                 if(del_old) {
1758                                         BLI_remlink(&em->verts,eve);
1759                                         free_editvert(em, eve);
1760                                         eve= NULL;
1761                                 }
1762                         }
1763                 }
1764                 if(eve) {
1765                         eve->f &= ~128;
1766                 }
1767                 eve= nextve;
1768         }
1769         // since its vertex select mode now, it also deselects higher order
1770         EM_selectmode_flush(em);
1771
1772         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // g is grab, for correct undo print
1773         return 'n';
1774 }
1775
1776 /* generic extrude */
1777 short extrudeflag(Object *obedit, EditMesh *em, short flag, float *nor, int all)
1778 {
1779         if(em->selectmode & SCE_SELECT_VERTEX)
1780                 return extrudeflag_vert(obedit, em, flag, nor, all);
1781         else 
1782                 return extrudeflag_edge(obedit, em, flag, nor, all);
1783                 
1784 }
1785
1786 void rotateflag(EditMesh *em, short flag, float *cent, float rotmat[][3])
1787 {
1788         /* all verts with (flag & 'flag') rotate */
1789         EditVert *eve;
1790
1791         eve= em->verts.first;
1792         while(eve) {
1793                 if(eve->f & flag) {
1794                         eve->co[0]-=cent[0];
1795                         eve->co[1]-=cent[1];
1796                         eve->co[2]-=cent[2];
1797                         mul_m3_v3(rotmat,eve->co);
1798                         eve->co[0]+=cent[0];
1799                         eve->co[1]+=cent[1];
1800                         eve->co[2]+=cent[2];
1801                 }
1802                 eve= eve->next;
1803         }
1804 }
1805
1806 void translateflag(EditMesh *em, short flag, float *vec)
1807 {
1808         /* all verts with (flag & 'flag') translate */
1809         EditVert *eve;
1810
1811         eve= em->verts.first;
1812         while(eve) {
1813                 if(eve->f & flag) {
1814                         eve->co[0]+=vec[0];
1815                         eve->co[1]+=vec[1];
1816                         eve->co[2]+=vec[2];
1817                 }
1818                 eve= eve->next;
1819         }
1820 }
1821
1822 /* helper call for below */
1823 static EditVert *adduplicate_vertex(EditMesh *em, EditVert *eve, int flag)
1824 {
1825         /* FIXME: copy deformation weight from eve ok here? */
1826         EditVert *v1= addvertlist(em, eve->co, eve);
1827         
1828         v1->f= eve->f;
1829         eve->f &= ~flag;
1830         eve->f|= 128;
1831         
1832         eve->tmp.v = v1;
1833         
1834         return v1;
1835 }
1836
1837 /* old selection has flag 128 set, and flag 'flag' cleared
1838 new selection has flag 'flag' set */
1839 void adduplicateflag(EditMesh *em, int flag)
1840 {
1841         EditVert *eve, *v1, *v2, *v3, *v4;
1842         EditEdge *eed, *newed;
1843         EditFace *efa, *newfa, *act_efa = EM_get_actFace(em, 0);
1844
1845         EM_clear_flag_all(em, 128);
1846         EM_selectmode_set(em);  // paranoia check, selection now is consistent
1847
1848         /* vertices first */
1849         for(eve= em->verts.last; eve; eve= eve->prev) {
1850
1851                 if(eve->f & flag)
1852                         adduplicate_vertex(em, eve, flag);
1853                 else 
1854                         eve->tmp.v = NULL;
1855         }
1856         
1857         /* copy edges, note that vertex selection can be independent of edge */
1858         for(eed= em->edges.last; eed; eed= eed->prev) {
1859                 if( eed->f & flag ) {
1860                         v1 = eed->v1->tmp.v;
1861                         if(v1==NULL) v1= adduplicate_vertex(em, eed->v1, flag);
1862                         v2 = eed->v2->tmp.v;
1863                         if(v2==NULL) v2= adduplicate_vertex(em, eed->v2, flag);
1864                         
1865                         newed= addedgelist(em, v1, v2, eed);
1866                         
1867                         newed->f= eed->f;
1868                         eed->f &= ~flag;
1869                         eed->f |= 128;
1870                 }
1871         }
1872
1873         /* then duplicate faces, again create new vertices if needed */
1874         for(efa= em->faces.last; efa; efa= efa->prev) {
1875                 if(efa->f & flag) {
1876                         v1 = efa->v1->tmp.v;
1877                         if(v1==NULL) v1= adduplicate_vertex(em, efa->v1, flag);
1878                         v2 = efa->v2->tmp.v;
1879                         if(v2==NULL) v2= adduplicate_vertex(em, efa->v2, flag);
1880                         v3 = efa->v3->tmp.v;
1881                         if(v3==NULL) v3= adduplicate_vertex(em, efa->v3, flag);
1882                         if(efa->v4) {
1883                                 v4 = efa->v4->tmp.v; 
1884                                 if(v4==NULL) v4= adduplicate_vertex(em, efa->v4, flag);
1885                         }
1886                         else v4= NULL;
1887                         
1888                         newfa= addfacelist(em, v1, v2, v3, v4, efa, efa); 
1889                         
1890                         if (efa==act_efa) {
1891                                 EM_set_actFace(em, newfa);
1892                         }
1893                         
1894                         newfa->f= efa->f;
1895                         efa->f &= ~flag;
1896                         efa->f |= 128;
1897                 }
1898         }
1899         
1900         EM_fgon_flags(em);      // redo flags and indices for fgons
1901 }
1902
1903 void delfaceflag(EditMesh *em, int flag)
1904 {
1905         /* delete all faces with 'flag', including loose edges and loose vertices */
1906         /* this is maybe a bit weird, but this function is used for 'split' and 'separate' */
1907         /* in remaining vertices/edges 'flag' is cleared */
1908         EditVert *eve,*nextve;
1909         EditEdge *eed, *nexted;
1910         EditFace *efa,*nextvl;
1911
1912         /* to detect loose edges, we put f2 flag on 1 */
1913         for(eed= em->edges.first; eed; eed= eed->next) {
1914                 if(eed->f & flag) eed->f2= 1;
1915                 else eed->f2= 0;
1916         }
1917         
1918         /* delete faces */
1919         efa= em->faces.first;
1920         while(efa) {
1921                 nextvl= efa->next;
1922                 if(efa->f & flag) {
1923                         
1924                         efa->e1->f2= 1;
1925                         efa->e2->f2= 1;
1926                         efa->e3->f2= 1;
1927                         if(efa->e4) {
1928                                 efa->e4->f2= 1;
1929                         }
1930                                                                 
1931                         BLI_remlink(&em->faces, efa);
1932                         free_editface(em, efa);
1933                 }
1934                 efa= nextvl;
1935         }
1936         
1937         /* all remaining faces: make sure we keep the edges */
1938         for(efa= em->faces.first; efa; efa= efa->next) {
1939                 efa->e1->f2= 0;
1940                 efa->e2->f2= 0;
1941                 efa->e3->f2= 0;
1942                 if(efa->e4) {
1943                         efa->e4->f2= 0;
1944                 }
1945         }
1946         
1947         /* remove tagged edges, and clear remaining ones */
1948         eed= em->edges.first;
1949         while(eed) {
1950                 nexted= eed->next;
1951                 
1952                 if(eed->f2==1) {
1953                         remedge(em, eed);
1954                         free_editedge(em, eed);
1955                 }
1956                 else {
1957                         eed->f &= ~flag;
1958                         eed->v1->f &= ~flag;
1959                         eed->v2->f &= ~flag;
1960                 }
1961                 eed= nexted;
1962         }
1963         
1964         /* vertices with 'flag' now are the loose ones, and will be removed */
1965         eve= em->verts.first;
1966         while(eve) {
1967                 nextve= eve->next;
1968                 if(eve->f & flag) {
1969                         BLI_remlink(&em->verts, eve);
1970                         free_editvert(em, eve);
1971                 }
1972                 eve= nextve;
1973         }
1974
1975 }
1976
1977 /* ********************* */
1978 #if 0
1979 static int check_vnormal_flip(float *n, float *vnorm) 
1980 {
1981         float inp;
1982
1983         inp= n[0]*vnorm[0]+n[1]*vnorm[1]+n[2]*vnorm[2];
1984
1985         /* angles 90 degrees: dont flip */
1986         if(inp> -0.000001) return 0;
1987
1988         return 1;
1989 }
1990 #endif
1991
1992
1993
1994 /* does face centers too */
1995 void recalc_editnormals(EditMesh *em)
1996 {
1997         EditFace *efa;
1998         EditVert *eve;
1999
2000         for(eve= em->verts.first; eve; eve=eve->next) {
2001                 eve->no[0] = eve->no[1] = eve->no[2] = 0.0;
2002         }
2003
2004         for(efa= em->faces.first; efa; efa=efa->next) {
2005                 if(efa->v4) {
2006                         normal_quad_v3( efa->n,efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
2007                         cent_quad_v3(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
2008                         add_v3_v3(efa->v4->no, efa->n);
2009                 }
2010                 else {
2011                         normal_tri_v3( efa->n,efa->v1->co, efa->v2->co, efa->v3->co);
2012                         cent_tri_v3(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co);
2013                 }
2014                 add_v3_v3(efa->v1->no, efa->n);
2015                 add_v3_v3(efa->v2->no, efa->n);
2016                 add_v3_v3(efa->v3->no, efa->n);
2017         }
2018
2019         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
2020         for(eve= em->verts.first; eve; eve=eve->next) {
2021                 if (normalize_v3(eve->no)==0.0) {
2022                         VECCOPY(eve->no, eve->co);
2023                         normalize_v3(eve->no);
2024                 }
2025         }
2026 }
2027
2028 int compareface(EditFace *vl1, EditFace *vl2)
2029 {
2030         EditVert *v1, *v2, *v3, *v4;
2031         
2032         if(vl1->v4 && vl2->v4) {
2033                 v1= vl2->v1;
2034                 v2= vl2->v2;
2035                 v3= vl2->v3;
2036                 v4= vl2->v4;
2037                 
2038                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1 || vl1->v4==v1) {
2039                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2 || vl1->v4==v2) {
2040                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3 || vl1->v4==v3) {
2041                                         if(vl1->v1==v4 || vl1->v2==v4 || vl1->v3==v4 || vl1->v4==v4) {
2042                                                 return 1;
2043                                         }
2044                                 }
2045                         }
2046                 }
2047         }
2048         else if(vl1->v4==0 && vl2->v4==0) {
2049                 v1= vl2->v1;
2050                 v2= vl2->v2;
2051                 v3= vl2->v3;
2052                 
2053                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1) {
2054                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2) {
2055                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3) {
2056                                         return 1;
2057                                 }
2058                         }
2059                 }
2060         }
2061         
2062         return 0;
2063 }
2064
2065 /* checks for existence, not tria overlapping inside quad */
2066 EditFace *exist_face(EditMesh *em, EditVert *v1, EditVert *v2, EditVert *v3, EditVert *v4)
2067 {
2068         EditFace *efa, efatest;
2069         
2070         efatest.v1= v1;
2071         efatest.v2= v2;
2072         efatest.v3= v3;
2073         efatest.v4= v4;
2074         
2075         efa= em->faces.first;
2076         while(efa) {
2077                 if(compareface(&efatest, efa)) return efa;
2078                 efa= efa->next;
2079         }
2080         return NULL;
2081 }
2082
2083 /* evaluate if entire quad is a proper convex quad */
2084 int convex(float *v1, float *v2, float *v3, float *v4)
2085 {
2086         float nor[3], nor1[3], nor2[3], vec[4][2];
2087         
2088         /* define projection, do both trias apart, quad is undefined! */
2089         normal_tri_v3( nor1,v1, v2, v3);
2090         normal_tri_v3( nor2,v1, v3, v4);
2091         nor[0]= ABS(nor1[0]) + ABS(nor2[0]);
2092         nor[1]= ABS(nor1[1]) + ABS(nor2[1]);
2093         nor[2]= ABS(nor1[2]) + ABS(nor2[2]);
2094
2095         if(nor[2] >= nor[0] && nor[2] >= nor[1]) {
2096                 vec[0][0]= v1[0]; vec[0][1]= v1[1];
2097                 vec[1][0]= v2[0]; vec[1][1]= v2[1];
2098                 vec[2][0]= v3[0]; vec[2][1]= v3[1];
2099                 vec[3][0]= v4[0]; vec[3][1]= v4[1];
2100         }
2101         else if(nor[1] >= nor[0] && nor[1]>= nor[2]) {
2102                 vec[0][0]= v1[0]; vec[0][1]= v1[2];
2103                 vec[1][0]= v2[0]; vec[1][1]= v2[2];
2104                 vec[2][0]= v3[0]; vec[2][1]= v3[2];
2105                 vec[3][0]= v4[0]; vec[3][1]= v4[2];
2106         }
2107         else {
2108                 vec[0][0]= v1[1]; vec[0][1]= v1[2];
2109                 vec[1][0]= v2[1]; vec[1][1]= v2[2];
2110                 vec[2][0]= v3[1]; vec[2][1]= v3[2];
2111                 vec[3][0]= v4[1]; vec[3][1]= v4[2];
2112         }
2113         
2114         /* linetests, the 2 diagonals have to instersect to be convex */
2115         if( isect_line_line_v2(vec[0], vec[2], vec[1], vec[3]) > 0 ) return 1;
2116         return 0;
2117 }
2118
2119
2120 /* ********************* Fake Polgon support (FGon) ***************** */
2121
2122
2123 /* results in:
2124    - faces having ->fgonf flag set (also for draw)
2125    - edges having ->fgoni index set (for select)
2126 */
2127
2128 float EM_face_area(EditFace *efa)
2129 {
2130         if(efa->v4) return area_quad_v3(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
2131         else return area_tri_v3(efa->v1->co, efa->v2->co, efa->v3->co);
2132 }
2133
2134 float EM_face_perimeter(EditFace *efa)
2135 {       
2136         if(efa->v4) return
2137                 len_v3v3(efa->v1->co, efa->v2->co)+
2138                 len_v3v3(efa->v2->co, efa->v3->co)+
2139                 len_v3v3(efa->v3->co, efa->v4->co)+
2140                 len_v3v3(efa->v4->co, efa->v1->co);
2141         
2142         else return
2143                 len_v3v3(efa->v1->co, efa->v2->co)+
2144                 len_v3v3(efa->v2->co, efa->v3->co)+
2145                 len_v3v3(efa->v3->co, efa->v1->co);
2146 }
2147
2148 void EM_fgon_flags(EditMesh *em)
2149 {
2150         EditFace *efa, *efan, *efamax;
2151         EditEdge *eed;
2152         ListBase listb={NULL, NULL};
2153         float size, maxsize;
2154         short done, curindex= 1;
2155         
2156         // for each face with fgon edge AND not fgon flag set
2157         for(eed= em->edges.first; eed; eed= eed->next) eed->fgoni= 0;  // index
2158         for(efa= em->faces.first; efa; efa= efa->next) efa->fgonf= 0;  // flag
2159         
2160         // for speed & simplicity, put fgon face candidates in new listbase
2161         efa= em->faces.first;
2162         while(efa) {
2163                 efan= efa->next;
2164                 if( (efa->e1->h & EM_FGON) || (efa->e2->h & EM_FGON) || 
2165                         (efa->e3->h & EM_FGON) || (efa->e4 && (efa->e4->h & EM_FGON)) ) {
2166                         BLI_remlink(&em->faces, efa);
2167                         BLI_addtail(&listb, efa);
2168                 }
2169                 efa= efan;
2170         }
2171         
2172         // find an undone face with fgon edge
2173         for(efa= listb.first; efa; efa= efa->next) {
2174                 if(efa->fgonf==0) {
2175                         
2176                         // init this face
2177                         efa->fgonf= EM_FGON;
2178                         if(efa->e1->h & EM_FGON) efa->e1->fgoni= curindex;
2179                         if(efa->e2->h & EM_FGON) efa->e2->fgoni= curindex;
2180                         if(efa->e3->h & EM_FGON) efa->e3->fgoni= curindex;
2181                         if(efa->e4 && (efa->e4->h & EM_FGON)) efa->e4->fgoni= curindex;
2182                         
2183                         // we search for largest face, to give facedot drawing rights
2184                         maxsize= EM_face_area(efa);
2185                         efamax= efa;
2186                         
2187                         // now flush curendex over edges and set faceflags
2188                         done= 1;
2189                         while(done==1) {
2190                                 done= 0;
2191                                 
2192                                 for(efan= listb.first; efan; efan= efan->next) {
2193                                         if(efan->fgonf==0) {
2194                                                 // if one if its edges has index set, do other too
2195                                                 if( (efan->e1->fgoni==curindex) || (efan->e2->fgoni==curindex) ||
2196                                                         (efan->e3->fgoni==curindex) || (efan->e4 && (efan->e4->fgoni==curindex)) ) {
2197                                                         
2198                                                         efan->fgonf= EM_FGON;
2199                                                         if(efan->e1->h & EM_FGON) efan->e1->fgoni= curindex;
2200                                                         if(efan->e2->h & EM_FGON) efan->e2->fgoni= curindex;
2201                                                         if(efan->e3->h & EM_FGON) efan->e3->fgoni= curindex;
2202                                                         if(efan->e4 && (efan->e4->h & EM_FGON)) efan->e4->fgoni= curindex;
2203                                                         
2204                                                         size= EM_face_area(efan);
2205                                                         if(size>maxsize) {
2206                                                                 efamax= efan;
2207                                                                 maxsize= size;
2208                                                         }
2209                                                         done= 1;
2210                                                 }
2211                                         }
2212                                 }
2213                         }
2214                         
2215                         efamax->fgonf |= EM_FGON_DRAW;
2216                         curindex++;
2217
2218                 }
2219         }
2220
2221         // put fgon face candidates back in listbase
2222         efa= listb.first;
2223         while(efa) {
2224                 efan= efa->next;
2225                 BLI_remlink(&listb, efa);
2226                 BLI_addtail(&em->faces, efa);
2227                 efa= efan;
2228         }
2229         
2230         // remove fgon flags when edge not in fgon (anymore)
2231         for(eed= em->edges.first; eed; eed= eed->next) {
2232                 if(eed->fgoni==0) eed->h &= ~EM_FGON;
2233         }
2234         
2235 }
2236
2237 /* editmesh vertmap, copied from intern.mesh.c
2238  * if do_face_idx_array is 0 it means we need to run it as well as freeing
2239  * */
2240
2241 UvVertMap *EM_make_uv_vert_map(EditMesh *em, int selected, int do_face_idx_array, float *limit)
2242 {
2243         EditVert *ev;
2244         EditFace *efa;
2245         int totverts;
2246         
2247         /* vars from original func */
2248         UvVertMap *vmap;
2249         UvMapVert *buf;
2250         MTFace *tf;
2251         unsigned int a;
2252         int     i, totuv, nverts;
2253         
2254         if (do_face_idx_array)
2255                 EM_init_index_arrays(em, 0, 0, 1);
2256         
2257         /* we need the vert */
2258         for (ev= em->verts.first, totverts=0; ev; ev= ev->next, totverts++) {
2259                 ev->tmp.l = totverts;
2260         }
2261         
2262         totuv = 0;
2263
2264         /* generate UvMapVert array */
2265         for (efa= em->faces.first; efa; efa= efa->next)
2266                 if(!selected || ((!efa->h) && (efa->f & SELECT)))
2267                         totuv += (efa->v4)? 4: 3;
2268                 
2269         if(totuv==0) {
2270                 if (do_face_idx_array)
2271                         EM_free_index_arrays();
2272                 return NULL;
2273         }
2274         vmap= (UvVertMap*)MEM_callocN(sizeof(*vmap), "UvVertMap");
2275         if (!vmap) {
2276                 if (do_face_idx_array)
2277                         EM_free_index_arrays();
2278                 return NULL;
2279         }
2280
2281         vmap->vert= (UvMapVert**)MEM_callocN(sizeof(*vmap->vert)*totverts, "UvMapVert*");
2282         buf= vmap->buf= (UvMapVert*)MEM_callocN(sizeof(*vmap->buf)*totuv, "UvMapVert");
2283
2284         if (!vmap->vert || !vmap->buf) {
2285                 free_uv_vert_map(vmap);
2286                 if (do_face_idx_array)
2287                         EM_free_index_arrays();
2288                 return NULL;
2289         }
2290
2291         for (a=0, efa= em->faces.first; efa; a++, efa= efa->next) {
2292                 if(!selected || ((!efa->h) && (efa->f & SELECT))) {
2293                         nverts= (efa->v4)? 4: 3;
2294                         
2295                         for(i=0; i<nverts; i++) {
2296                                 buf->tfindex= i;
2297                                 buf->f= a;
2298                                 buf->separate = 0;
2299                                 
2300                                 buf->next= vmap->vert[(*(&efa->v1 + i))->tmp.l];
2301                                 vmap->vert[(*(&efa->v1 + i))->tmp.l]= buf;
2302                                 
2303                                 buf++;
2304                         }
2305                 }
2306         }
2307         
2308         /* sort individual uvs for each vert */
2309         for(a=0, ev=em->verts.first; ev; a++, ev= ev->next) {
2310                 UvMapVert *newvlist= NULL, *vlist=vmap->vert[a];
2311                 UvMapVert *iterv, *v, *lastv, *next;
2312                 float *uv, *uv2, uvdiff[2];
2313
2314                 while(vlist) {
2315                         v= vlist;
2316                         vlist= vlist->next;
2317                         v->next= newvlist;
2318                         newvlist= v;
2319
2320                         efa = EM_get_face_for_index(v->f);
2321                         tf = CustomData_em_get(&em->fdata, efa->data, CD_MTFACE);
2322                         uv = tf->uv[v->tfindex]; 
2323                         
2324                         lastv= NULL;
2325                         iterv= vlist;
2326
2327                         while(iterv) {
2328                                 next= iterv->next;
2329                                 efa = EM_get_face_for_index(iterv->f);
2330                                 tf = CustomData_em_get(&em->fdata, efa->data, CD_MTFACE);
2331                                 uv2 = tf->uv[iterv->tfindex];
2332                                 
2333                                 sub_v2_v2v2(uvdiff, uv2, uv);
2334
2335                                 if(fabs(uv[0]-uv2[0]) < limit[0] && fabs(uv[1]-uv2[1]) < limit[1]) {
2336                                         if(lastv) lastv->next= next;
2337                                         else vlist= next;
2338                                         iterv->next= newvlist;
2339                                         newvlist= iterv;
2340                                 }
2341                                 else
2342                                         lastv=iterv;
2343
2344                                 iterv= next;
2345                         }
2346
2347                         newvlist->separate = 1;
2348                 }
2349
2350                 vmap->vert[a]= newvlist;
2351         }
2352         
2353         if (do_face_idx_array)
2354                 EM_free_index_arrays();
2355         
2356         return vmap;
2357 }
2358
2359 UvMapVert *EM_get_uv_map_vert(UvVertMap *vmap, unsigned int v)
2360 {
2361         return vmap->vert[v];
2362 }
2363
2364 void EM_free_uv_vert_map(UvVertMap *vmap)
2365 {
2366         if (vmap) {
2367                 if (vmap->vert) MEM_freeN(vmap->vert);
2368                 if (vmap->buf) MEM_freeN(vmap->buf);
2369                 MEM_freeN(vmap);
2370         }
2371 }
2372
2373 /* poll call for mesh operators requiring a view3d context */
2374 int EM_view3d_poll(bContext *C)
2375 {
2376         if(ED_operator_editmesh(C) && ED_operator_view3d_active(C))
2377                 return 1;
2378         return 0;
2379 }
2380
2381 /* higher quality normals */
2382
2383 /* NormalCalc */
2384 /* NormalCalc modifier: calculates higher quality normals
2385 */
2386
2387 /* each edge uses this to  */
2388 typedef struct EdgeFaceRef {
2389         int f1; /* init as -1 */
2390         int f2;
2391 } EdgeFaceRef;
2392
2393 void EM_make_hq_normals(EditMesh *em)
2394 {
2395         EditFace *efa;
2396         EditVert *eve;
2397         int i;
2398
2399         EdgeHash *edge_hash = BLI_edgehash_new();
2400         EdgeHashIterator *edge_iter;
2401         int edge_ref_count = 0;
2402         int ed_v1, ed_v2; /* use when getting the key */
2403         EdgeFaceRef *edge_ref_array = MEM_callocN(em->totedge * sizeof(EdgeFaceRef), "Edge Connectivity");
2404         EdgeFaceRef *edge_ref;
2405         float edge_normal[3];
2406
2407         EM_init_index_arrays(em, 1, 1, 1);
2408
2409         for(eve= em->verts.first, i=0; eve; eve= eve->next, i++) {
2410                 zero_v3(eve->no);
2411                 eve->tmp.l= i;
2412         }
2413
2414         /* This function adds an edge hash if its not there, and adds the face index */
2415 #define NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(EDV1, EDV2); \
2416                         edge_ref = (EdgeFaceRef *)BLI_edgehash_lookup(edge_hash, EDV1, EDV2); \
2417                         if (!edge_ref) { \
2418                                 edge_ref = &edge_ref_array[edge_ref_count]; edge_ref_count++; \
2419                                 edge_ref->f1=i; \
2420                                 edge_ref->f2=-1; \
2421                                 BLI_edgehash_insert(edge_hash, EDV1, EDV2, edge_ref); \
2422                         } else { \
2423                                 edge_ref->f2=i; \
2424                         }
2425
2426
2427         efa= em->faces.first;
2428         for(i = 0; i < em->totface; i++, efa= efa->next) {
2429                 if(efa->v4) {
2430                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v1->tmp.l, efa->v2->tmp.l);
2431                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v2->tmp.l, efa->v3->tmp.l);
2432                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v3->tmp.l, efa->v4->tmp.l);
2433                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v4->tmp.l, efa->v1->tmp.l);
2434                 } else {
2435                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v1->tmp.l, efa->v2->tmp.l);
2436                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v2->tmp.l, efa->v3->tmp.l);
2437                         NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE(efa->v3->tmp.l, efa->v1->tmp.l);
2438                 }
2439         }
2440
2441 #undef NOCALC_EDGEWEIGHT_ADD_EDGEREF_FACE
2442
2443
2444         for(edge_iter = BLI_edgehashIterator_new(edge_hash); !BLI_edgehashIterator_isDone(edge_iter); BLI_edgehashIterator_step(edge_iter)) {
2445                 /* Get the edge vert indices, and edge value (the face indices that use it)*/
2446                 BLI_edgehashIterator_getKey(edge_iter, (int*)&ed_v1, (int*)&ed_v2);
2447                 edge_ref = BLI_edgehashIterator_getValue(edge_iter);
2448
2449                 if (edge_ref->f2 != -1) {
2450                         EditFace *ef1= EM_get_face_for_index(edge_ref->f1), *ef2= EM_get_face_for_index(edge_ref->f2);
2451                         float angle= angle_normalized_v3v3(ef1->n, ef2->n);
2452                         if(angle > 0.0f) {
2453                                 /* We have 2 faces using this edge, calculate the edges normal
2454                                  * using the angle between the 2 faces as a weighting */
2455                                 add_v3_v3v3(edge_normal, ef1->n, ef2->n);
2456                                 normalize_v3(edge_normal);
2457                                 mul_v3_fl(edge_normal, angle);
2458                         }
2459                         else {
2460                                 /* cant do anything useful here!
2461                                    Set the face index for a vert incase it gets a zero normal */
2462                                 EM_get_vert_for_index(ed_v1)->tmp.l=
2463                                 EM_get_vert_for_index(ed_v2)->tmp.l= -(edge_ref->f1 + 1);
2464                                 continue;
2465                         }
2466                 } else {
2467                         /* only one face attached to that edge */
2468                         /* an edge without another attached- the weight on this is
2469                          * undefined, M_PI/2 is 90d in radians and that seems good enough */
2470                         VECCOPY(edge_normal, EM_get_face_for_index(edge_ref->f1)->n)
2471                         mul_v3_fl(edge_normal, M_PI/2);
2472                 }
2473                 add_v3_v3(EM_get_vert_for_index(ed_v1)->no, edge_normal );
2474                 add_v3_v3(EM_get_vert_for_index(ed_v2)->no, edge_normal );
2475
2476
2477         }
2478         BLI_edgehashIterator_free(edge_iter);
2479         BLI_edgehash_free(edge_hash, NULL);
2480         MEM_freeN(edge_ref_array);
2481
2482         /* normalize vertex normals and assign */
2483         for(eve= em->verts.first; eve; eve= eve->next) {
2484                 if(normalize_v3(eve->no) == 0.0f && eve->tmp.l < 0) {
2485                         /* exceptional case, totally flat */
2486                         efa= EM_get_face_for_index(-(eve->tmp.l) - 1);
2487                         VECCOPY(eve->no, efa->n);
2488                 }       
2489         }
2490
2491         EM_free_index_arrays();
2492 }
2493
2494 void EM_solidify(EditMesh *em, float dist)
2495 {
2496         EditFace *efa;
2497         EditVert *eve;
2498         float *vert_angles= MEM_callocN(sizeof(float) * em->totvert * 2, "EM_solidify"); /* 2 in 1 */
2499         float *vert_accum= vert_angles + em->totvert;
2500         float face_angles[4];
2501         int i, j;
2502
2503         for(eve= em->verts.first, i=0; eve; eve= eve->next, i++) {
2504                 eve->tmp.l= i;
2505         }
2506
2507         efa= em->faces.first;
2508         for(i = 0; i < em->totface; i++, efa= efa->next) {
2509
2510                 if(!(efa->f & SELECT))
2511                         continue;
2512
2513                 if(efa->v4) {
2514                         angle_quad_v3(face_angles, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
2515                         j= 3;
2516                 }
2517                 else {
2518                         angle_tri_v3(face_angles, efa->v1->co, efa->v2->co, efa->v3->co);
2519                         j= 2;
2520                 }
2521
2522                 for(; j>=0; j--) {
2523                         eve= *(&efa->v1 + j);
2524                         vert_accum[eve->tmp.l] += face_angles[j];
2525                         vert_angles[eve->tmp.l]+= shell_angle_to_dist(angle_normalized_v3v3(eve->no, efa->n)) * face_angles[j];
2526                 }
2527         }
2528
2529         for(eve= em->verts.first, i=0; eve; eve= eve->next, i++) {
2530                 if(vert_accum[i]) { /* zero if unselected */
2531                         madd_v3_v3fl(eve->co, eve->no, dist * vert_angles[i] / vert_accum[i]);
2532                 }
2533         }
2534
2535         MEM_freeN(vert_angles);
2536 }
2537
2538 /* not that optimal!, should be nicer with bmesh */
2539 static void tag_face_edges(EditFace *efa)
2540 {
2541         if(efa->v4)
2542                 efa->e1->tmp.l= efa->e2->tmp.l= efa->e3->tmp.l= efa->e4->tmp.l= 1;
2543         else
2544                 efa->e1->tmp.l= efa->e2->tmp.l= efa->e3->tmp.l= 1;
2545 }
2546 static int tag_face_edges_test(EditFace *efa)
2547 {
2548         if(efa->v4)
2549                 return (efa->e1->tmp.l || efa->e2->tmp.l || efa->e3->tmp.l || efa->e4->tmp.l) ? 1:0;
2550         else
2551                 return (efa->e1->tmp.l || efa->e2->tmp.l || efa->e3->tmp.l) ? 1:0;
2552 }
2553
2554 static void em_deselect_nth_face(EditMesh *em, int nth, EditFace *efa_act)
2555 {
2556         EditFace *efa;
2557         EditEdge *eed;
2558         int ok= 1;
2559
2560         if(efa_act==NULL) {
2561                 return;
2562         }
2563
2564         /* to detect loose edges, we put f2 flag on 1 */
2565         for(eed= em->edges.first; eed; eed= eed->next) {
2566                 eed->tmp.l= 0;
2567         }
2568
2569         for (efa= em->faces.first; efa; efa= efa->next) {
2570                 efa->tmp.l = 0;
2571         }
2572
2573         efa_act->tmp.l = 1;
2574
2575         while(ok) {
2576                 ok = 0;
2577
2578                 for (efa= em->faces.first; efa; efa= efa->next) {
2579                         if(efa->f & SELECT) {
2580                                 if(efa->tmp.l==1) { /* initialize */
2581                                         tag_face_edges(efa);
2582                                 }
2583         
2584                                 if(efa->tmp.l) {
2585                                         efa->tmp.l++;
2586                                 }
2587                         }
2588                 }
2589
2590                 for (efa= em->faces.first; efa; efa= efa->next) {
2591                         if(efa->f & SELECT) {
2592                                 if(efa->tmp.l==0 && tag_face_edges_test(efa)) {
2593                                         efa->tmp.l= 1;
2594                                         ok = 1; /* keep looping */
2595                                 }
2596                         }
2597                 }
2598         }
2599
2600         for (efa= em->faces.first; efa; efa= efa->next) {
2601                 if(efa->tmp.l > 0 && efa->tmp.l % nth) {
2602                         EM_select_face(efa, 0);
2603                 }
2604         }
2605         for (efa= em->faces.first; efa; efa= efa->next) {
2606                 if(efa->f & SELECT) {
2607                         EM_select_face(efa, 1);
2608                 }
2609         }
2610
2611         EM_nvertices_selected(em);
2612         EM_nedges_selected(em);
2613         EM_nfaces_selected(em);
2614 }
2615
2616 /* not that optimal!, should be nicer with bmesh */
2617 static void tag_edge_verts(EditEdge *eed)
2618 {
2619         eed->v1->tmp.l= eed->v2->tmp.l= 1;
2620 }
2621 static int tag_edge_verts_test(EditEdge *eed)
2622 {
2623         return (eed->v1->tmp.l || eed->v2->tmp.l) ? 1:0;
2624 }
2625
2626 static void em_deselect_nth_edge(EditMesh *em, int nth, EditEdge *eed_act)
2627 {
2628         EditEdge *eed;
2629         EditVert *eve;
2630         int ok= 1;
2631
2632         if(eed_act==NULL) {
2633                 return;
2634         }
2635
2636         for(eve= em->verts.first; eve; eve= eve->next) {
2637                 eve->tmp.l= 0;
2638         }
2639
2640         for (eed= em->edges.first; eed; eed= eed->next) {
2641                 eed->tmp.l = 0;
2642         }
2643
2644         eed_act->tmp.l = 1;
2645
2646         while(ok) {
2647                 ok = 0;
2648
2649                 for (eed= em->edges.first; eed; eed= eed->next) {
2650                         if(eed->f & SELECT) {
2651                                 if(eed->tmp.l==1) { /* initialize */
2652                                         tag_edge_verts(eed);
2653                                 }
2654         
2655                                 if(eed->tmp.l) {
2656                                         eed->tmp.l++;
2657                                 }
2658                         }
2659                 }
2660
2661                 for (eed= em->edges.first; eed; eed= eed->next) {
2662                         if(eed->f & SELECT) {
2663                                 if(eed->tmp.l==0 && tag_edge_verts_test(eed)) {
2664                                         eed->tmp.l= 1;
2665                                         ok = 1; /* keep looping */
2666                                 }
2667                         }
2668                 }
2669         }
2670
2671         for (eed= em->edges.first; eed; eed= eed->next) {
2672                 if(eed->tmp.l > 0 && eed->tmp.l % nth) {
2673                         EM_select_edge(eed, 0);
2674                 }
2675         }
2676         for (eed= em->edges.first; eed; eed= eed->next) {
2677                 if(eed->f & SELECT) {
2678                         EM_select_edge(eed, 1);
2679                 }
2680         }
2681
2682         {
2683                 /* grr, should be a function */
2684                 EditFace *efa;
2685                 for (efa= em->faces.first; efa; efa= efa->next) {
2686                         if(efa->v4) {
2687                                 if(efa->e1->f & efa->e2->f & efa->e3->f & efa->e4->f & SELECT );
2688                                 else efa->f &= ~SELECT;
2689                         }
2690                         else {
2691                                 if(efa->e1->f & efa->e2->f & efa->e3->f & SELECT );
2692                                 else efa->f &= ~SELECT;
2693                         }
2694                 }
2695         }
2696
2697         EM_nvertices_selected(em);
2698         EM_nedges_selected(em);
2699         EM_nfaces_selected(em);
2700 }
2701
2702 static void em_deselect_nth_vert(EditMesh *em, int nth, EditVert *eve_act)
2703 {
2704         EditVert *eve;
2705         EditEdge *eed;
2706         int ok= 1;
2707
2708         if(eve_act==NULL) {
2709                 return;
2710         }
2711
2712         for (eve= em->verts.first; eve; eve= eve->next) {
2713                 eve->tmp.l = 0;
2714         }
2715
2716         eve_act->tmp.l = 1;
2717
2718         while(ok) {
2719                 ok = 0;
2720
2721                 for (eve= em->verts.first; eve; eve= eve->next) {
2722                         if(eve->f & SELECT) {
2723                                 if(eve->tmp.l)
2724                                         eve->tmp.l++;
2725                         }
2726                 }
2727
2728                 for (eed= em->edges.first; eed; eed= eed->next) {
2729                         if(eed->f & SELECT) {
2730                                 if(eed->v1->tmp.l==2 && eed->v2->tmp.l==0) { /* initialize */
2731                                         eed->v2->tmp.l= 1;
2732                                         ok = 1; /* keep looping */
2733                                 }
2734                                 else if(eed->v2->tmp.l==2 && eed->v1->tmp.l==0) { /* initialize */
2735                                         eed->v1->tmp.l= 1;
2736                                         ok = 1; /* keep looping */
2737                                 }
2738                         }
2739                 }
2740         }
2741
2742         for (eve= em->verts.first; eve; eve= eve->next) {
2743                 if(eve->tmp.l > 0 && eve->tmp.l % nth) {
2744                         eve->f &= ~SELECT;
2745                 }
2746         }
2747
2748         EM_deselect_flush(em);
2749
2750         EM_nvertices_selected(em);
2751         // EM_nedges_selected(em); // flush does these
2752         // EM_nfaces_selected(em); // flush does these
2753 }
2754
2755 static void deselect_nth_active(EditMesh *em, EditVert **eve_p, EditEdge **eed_p, EditFace **efa_p)
2756 {
2757         EditSelection *ese;
2758
2759         *eve_p= NULL;
2760         *eed_p= NULL;
2761         *efa_p= NULL;
2762
2763         ese= (EditSelection*)em->selected.last;
2764
2765         if(ese) {
2766                 switch(ese->type) {
2767                 case EDITVERT:
2768                         *eve_p= (EditVert *)ese->data;
2769                         return;
2770                 case EDITEDGE:
2771                         *eed_p= (EditEdge *)ese->data;
2772                         return;
2773                 case EDITFACE:
2774                         *efa_p= (EditFace *)ese->data;
2775                         return;
2776                 }
2777         }
2778
2779         if(em->selectmode & SCE_SELECT_VERTEX) {
2780                 EditVert *eve;
2781                 for (eve= em->verts.first; eve; eve= eve->next) {
2782                         if(eve->f & SELECT) {
2783                                 *eve_p= eve;
2784                                 return;
2785                         }
2786                 }
2787         }
2788
2789         if(em->selectmode & SCE_SELECT_EDGE) {
2790                 EditEdge *eed;
2791                 for (eed= em->edges.first; eed; eed= eed->next) {
2792                         if(eed->f & SELECT) {
2793                                 *eed_p= eed;
2794                                 return;
2795                         }
2796                 }
2797         }
2798
2799         if(em->selectmode & SCE_SELECT_FACE) {
2800                 EditFace *efa= EM_get_actFace(em, 1);
2801                 if(efa) {
2802                         *efa_p= efa;
2803                         return;
2804                 }
2805         }
2806 }
2807
2808 int EM_deselect_nth(EditMesh *em, int nth)
2809 {
2810         EditVert *eve;
2811         EditEdge *eed;
2812         EditFace *efa;
2813
2814         deselect_nth_active(em, &eve, &eed, &efa);
2815
2816         if(eve)
2817                 em_deselect_nth_vert(em, nth, eve);
2818         else if (eed)
2819                 em_deselect_nth_edge(em, nth, eed);
2820         else if (efa)
2821                 em_deselect_nth_face(em, nth, efa);
2822         else
2823                 return 0;
2824         
2825         return 1;
2826 }
2827
2828 void EM_project_snap_verts(bContext *C, ARegion *ar, Object *obedit, EditMesh *em)
2829 {
2830         EditVert *eve;
2831         for(eve= em->verts.first;eve; eve=eve->next) {
2832                 if(eve->f & SELECT) {
2833                         float mval[2], vec[3], no_dummy[3];
2834                         int dist_dummy;
2835                         mul_v3_m4v3(vec, obedit->obmat, eve->co);
2836                         project_float_noclip(ar, vec, mval);
2837                         if(snapObjectsContext(C, mval, &dist_dummy, vec, no_dummy, SNAP_NOT_OBEDIT)) {
2838                                 mul_v3_m4v3(eve->co, obedit->imat, vec);
2839                         }
2840                 }
2841         }
2842 }