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