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