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