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