ad8788b1bbbae07245b536982497f96fd240af89
[blender.git] / source / blender / src / editmesh_lib.c
1 /**
2  * $Id: 
3  *
4  * ***** BEGIN GPL/BL DUAL 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. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2004 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  */
32
33 /*
34
35 editmesh_lib: generic (no UI, no menus) operations/evaluators for editmesh data
36
37 */
38
39 #include <stdlib.h>
40 #include <string.h>
41 #include <math.h>
42
43 #ifdef HAVE_CONFIG_H
44 #include <config.h>
45 #endif
46
47 #include "MEM_guardedalloc.h"
48
49
50 #include "DNA_mesh_types.h"
51 #include "DNA_meshdata_types.h"
52 #include "DNA_object_types.h"
53 #include "DNA_scene_types.h"
54
55 #include "BLI_blenlib.h"
56 #include "BLI_arithb.h"
57 #include "BLI_editVert.h"
58
59 #include "BKE_global.h"
60 #include "BKE_mesh.h"
61 #include "BKE_utildefines.h"
62
63 #include "BIF_editmesh.h"
64
65 #include "BSE_edit.h"
66
67 #include "editmesh.h"
68
69 /* ********* Selection ************ */
70 static int EM_check_selection(void *data)
71 {
72         EditSelection *ese;
73         
74         for(ese = G.editMesh->selected.first; ese; ese = ese->next){
75                 if(ese->data == data) return 1;
76                 }
77         
78         return 0;
79 }
80
81 void EM_remove_selection(void *data, int type)
82 {
83         EditSelection *ese;
84         for(ese=G.editMesh->selected.first; ese; ese = ese->next){
85                 if(ese->data == data){
86                         BLI_freelinkN(&(G.editMesh->selected),ese);
87                         break;
88                 }
89         }
90 }
91
92 void EM_store_selection(void *data, int type)
93 {
94         EditSelection *ese;
95         if(!EM_check_selection(data)){
96                 ese = (EditSelection*) MEM_callocN( sizeof(EditSelection), "Edit Selection");
97                 ese->type = type;
98                 ese->data = data;
99                 BLI_addtail(&(G.editMesh->selected),ese);
100         }
101 }
102
103 static void EM_strip_selections(void)
104 {
105         EditSelection *ese, *nextese;
106         if(!(G.scene->selectmode & SCE_SELECT_VERTEX)){
107                 ese = G.editMesh->selected.first;
108                 while(ese){
109                         nextese = ese->next; 
110                         if(ese->type == EDITVERT) BLI_freelinkN(&(G.editMesh->selected),ese);
111                         ese = nextese;
112                 }
113         }
114         if(!(G.scene->selectmode & SCE_SELECT_EDGE)){
115                 ese=G.editMesh->selected.first;
116                 while(ese){
117                         nextese = ese->next;
118                         if(ese->type == EDITEDGE) BLI_freelinkN(&(G.editMesh->selected), ese);
119                         ese = nextese;
120                 }
121         }
122         if(!(G.scene->selectmode & SCE_SELECT_FACE)){
123                 ese=G.editMesh->selected.first;
124                 while(ese){
125                         nextese = ese->next;
126                         if(ese->type == EDITFACE) BLI_freelinkN(&(G.editMesh->selected), ese);
127                         ese = nextese;
128                 }
129         }
130 }
131
132 /* generic way to get data from an EditSelection type 
133 These functions were written to be used by the Modifier widget when in Rotate about active mode,
134 but can be used anywhere.
135 EM_editselection_center
136 EM_editselection_normal
137 EM_editselection_plane
138 */
139 void EM_editselection_center(float *center, EditSelection *ese)
140 {
141         if (ese->type==EDITVERT) {
142                 EditVert *eve= ese->data;
143                 VecCopyf(center, eve->co);
144         } else if (ese->type==EDITEDGE) {
145                 EditEdge *eed= ese->data;
146                 VecAddf(center, eed->v1->co, eed->v2->co);
147                 VecMulf(center, 0.5);
148         } else if (ese->type==EDITFACE) {
149                 EditFace *efa= ese->data;
150                 VecCopyf(center, efa->cent);
151         }
152 }
153
154 void EM_editselection_normal(float *normal, EditSelection *ese)
155 {
156         if (ese->type==EDITVERT) {
157                 EditVert *eve= ese->data;
158                 VecCopyf(normal, eve->no);
159         } else if (ese->type==EDITEDGE) {
160                 EditEdge *eed= ese->data;
161                 float plane[3]; /* need a plane to correct the normal */
162                 float vec[3]; /* temp vec storage */
163                 
164                 VecAddf(normal, eed->v1->no, eed->v2->no);
165                 VecSubf(plane, eed->v2->co, eed->v1->co);
166                 
167                 /* the 2 vertex normals will be close but not at rightangles to the edge
168                 for rotate about edge we want them to be at right angles, so we need to
169                 do some extra colculation to correct the vert normals,
170                 we need the plane for this */
171                 Crossf(vec, normal, plane);
172                 Crossf(normal, plane, vec); 
173                 Normalise(normal);
174                 
175         } else if (ese->type==EDITFACE) {
176                 EditFace *efa= ese->data;
177                 VecCopyf(normal, efa->n);
178         }
179 }
180
181 /* Calculate a plane that is rightangles to the edge/vert/faces normal
182 also make the plane run allong an axis that is related to the geometry,
183 because this is used for the manipulators Y axis.*/
184 void EM_editselection_plane(float *plane, EditSelection *ese)
185 {
186         if (ese->type==EDITVERT) {
187                 EditVert *eve= ese->data;
188                 float vec[3]={0,0,0};
189                 
190                 if (ese->prev) { /*use previously selected data to make a usefull vertex plane */
191                         EM_editselection_center(vec, ese->prev);
192                         VecSubf(plane, eve->co, vec);
193                 } else {
194                         /* make a fake  plane thats at rightangles to the normal
195                         we cant make a crossvec from a vec thats the same as the vec
196                         unlikely but possible, so make sure if the normal is (0,0,1)
197                         that vec isnt the same or in the same direction even.*/
198                         if (eve->no[0]<0.5)                     vec[0]=1;
199                         else if (eve->no[1]<0.5)        vec[1]=1;
200                         else                                            vec[2]=1;
201                         Crossf(plane, eve->no, vec);
202                 }
203         } else if (ese->type==EDITEDGE) {
204                 EditEdge *eed= ese->data;
205
206                 /*the plane is simple, it runs allong the edge
207                 however selecting different edges can swap the direction of the y axis.
208                 this makes it less likely for the y axis of the manipulator
209                 (running along the edge).. to flip less often.
210                 at least its more pradictable */
211                 if (eed->v2->co[1] > eed->v1->co[1]) /*check which to do first */
212                         VecSubf(plane, eed->v2->co, eed->v1->co);
213                 else
214                         VecSubf(plane, eed->v1->co, eed->v2->co);
215                 
216         } else if (ese->type==EDITFACE) {
217                 EditFace *efa= ese->data;
218                 float vec[3];
219                 if (efa->v4) { /*if its a quad- set the plane along the 2 longest edges.*/
220                         float vecA[3], vecB[3];
221                         VecSubf(vecA, efa->v4->co, efa->v3->co);
222                         VecSubf(vecB, efa->v1->co, efa->v2->co);
223                         VecAddf(plane, vecA, vecB);
224                         
225                         VecSubf(vecA, efa->v1->co, efa->v4->co);
226                         VecSubf(vecB, efa->v2->co, efa->v3->co);
227                         VecAddf(vec, vecA, vecB);                                               
228                         /*use the biggest edge length*/
229                         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])
230                                 VecCopyf(plane, vec);
231                 } else {
232                         /*start with v1-2 */
233                         VecSubf(plane, efa->v1->co, efa->v2->co);
234                         
235                         /*test the edge between v2-3, use if longer */
236                         VecSubf(vec, efa->v2->co, efa->v3->co);
237                         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])
238                                 VecCopyf(plane, vec);
239                         
240                         /*test the edge between v1-3, use if longer */
241                         VecSubf(vec, efa->v3->co, efa->v1->co);
242                         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])
243                                 VecCopyf(plane, vec);
244                 }
245         }
246         Normalise(plane);
247 }
248
249
250
251 void EM_select_face(EditFace *efa, int sel)
252 {
253         if(sel) {
254                 efa->f |= SELECT;
255                 efa->e1->f |= SELECT;
256                 efa->e2->f |= SELECT;
257                 efa->e3->f |= SELECT;
258                 if(efa->e4) efa->e4->f |= SELECT;
259                 efa->v1->f |= SELECT;
260                 efa->v2->f |= SELECT;
261                 efa->v3->f |= SELECT;
262                 if(efa->v4) efa->v4->f |= SELECT;
263         }
264         else {
265                 efa->f &= ~SELECT;
266                 efa->e1->f &= ~SELECT;
267                 efa->e2->f &= ~SELECT;
268                 efa->e3->f &= ~SELECT;
269                 if(efa->e4) efa->e4->f &= ~SELECT;
270                 efa->v1->f &= ~SELECT;
271                 efa->v2->f &= ~SELECT;
272                 efa->v3->f &= ~SELECT;
273                 if(efa->v4) efa->v4->f &= ~SELECT;
274         }
275 }
276
277 void EM_select_edge(EditEdge *eed, int sel)
278 {
279         if(sel) {
280                 eed->f |= SELECT;
281                 eed->v1->f |= SELECT;
282                 eed->v2->f |= SELECT;
283         }
284         else {
285                 eed->f &= ~SELECT;
286                 eed->v1->f &= ~SELECT;
287                 eed->v2->f &= ~SELECT;
288         }
289 }
290
291 void EM_select_face_fgon(EditFace *efa, int val)
292 {
293         EditMesh *em = G.editMesh;
294         short index=0;
295         
296         if(efa->fgonf==0) EM_select_face(efa, val);
297         else {
298                 if(efa->e1->fgoni) index= efa->e1->fgoni;
299                 if(efa->e2->fgoni) index= efa->e2->fgoni;
300                 if(efa->e3->fgoni) index= efa->e3->fgoni;
301                 if(efa->v4 && efa->e4->fgoni) index= efa->e4->fgoni;
302                 
303                 if(index==0) printf("wrong fgon select\n");
304                 
305                 // select all ngon faces with index
306                 for(efa= em->faces.first; efa; efa= efa->next) {
307                         if(efa->fgonf) {
308                                 if(efa->e1->fgoni==index || efa->e2->fgoni==index || 
309                                    efa->e3->fgoni==index || (efa->e4 && efa->e4->fgoni==index) ) {
310                                         EM_select_face(efa, val);
311                                 }
312                         }
313                 }
314         }
315 }
316
317
318 /* only vertices */
319 int faceselectedOR(EditFace *efa, int flag)
320 {
321         if ((efa->v1->f | efa->v2->f | efa->v3->f | (efa->v4?efa->v4->f:0))&flag) {
322                 return 1;
323         } else {
324                 return 0;
325         }
326 }
327
328 // replace with (efa->f & SELECT)
329 int faceselectedAND(EditFace *efa, int flag)
330 {
331         if ((efa->v1->f & efa->v2->f & efa->v3->f & (efa->v4?efa->v4->f:flag))&flag) {
332                 return 1;
333         } else {
334                 return 0;
335         }
336 }
337
338 int EM_nfaces_selected(void)
339 {
340         EditMesh *em = G.editMesh;
341         EditFace *efa;
342         int count= 0;
343
344         for (efa= em->faces.first; efa; efa= efa->next)
345                 if (efa->f & SELECT)
346                         count++;
347
348         return count;
349 }
350
351 #if 0
352 static int EM_nedges(void)
353 {
354         EditMesh *em = G.editMesh;
355         EditEdge *eed;
356         int count= 0;
357
358         for (eed= em->edges.first; eed; eed= eed->next) count++;
359         return count;
360 }
361 #endif
362
363 int EM_nvertices_selected(void)
364 {
365         EditMesh *em = G.editMesh;
366         EditVert *eve;
367         int count= 0;
368
369         for (eve= em->verts.first; eve; eve= eve->next)
370                 if (eve->f & SELECT)
371                         count++;
372
373         return count;
374 }
375
376 void EM_clear_flag_all(int flag)
377 {
378         EditMesh *em = G.editMesh;
379         EditVert *eve;
380         EditEdge *eed;
381         EditFace *efa;
382         
383         for (eve= em->verts.first; eve; eve= eve->next) eve->f &= ~flag;
384         for (eed= em->edges.first; eed; eed= eed->next) eed->f &= ~flag;
385         for (efa= em->faces.first; efa; efa= efa->next) efa->f &= ~flag;
386         
387         if(flag & SELECT) BLI_freelistN(&(G.editMesh->selected));
388 }
389
390 void EM_set_flag_all(int flag)
391 {
392         EditMesh *em = G.editMesh;
393         EditVert *eve;
394         EditEdge *eed;
395         EditFace *efa;
396         
397         for (eve= em->verts.first; eve; eve= eve->next) if(eve->h==0) eve->f |= flag;
398         for (eed= em->edges.first; eed; eed= eed->next) if(eed->h==0) eed->f |= flag;
399         for (efa= em->faces.first; efa; efa= efa->next) if(efa->h==0) efa->f |= flag;
400         
401 }
402
403 /* flush for changes in vertices only */
404 void EM_deselect_flush(void)
405 {
406         EditMesh *em = G.editMesh;
407         EditEdge *eed;
408         EditFace *efa;
409         
410         for(eed= em->edges.first; eed; eed= eed->next) {
411                 if(eed->v1->f & eed->v2->f & SELECT);
412                 else eed->f &= ~SELECT;
413         }
414         for(efa= em->faces.first; efa; efa= efa->next) {
415                 if(efa->v4) {
416                         if(efa->v1->f & efa->v2->f & efa->v3->f & efa->v4->f & SELECT );
417                         else efa->f &= ~SELECT;
418                 }
419                 else {
420                         if(efa->v1->f & efa->v2->f & efa->v3->f & SELECT );
421                         else efa->f &= ~SELECT;
422                 }
423         }
424 }
425
426
427 /* flush selection to edges & faces */
428
429 /*  this only based on coherent selected vertices, for example when adding new
430     objects. call clear_flag_all() before you select vertices to be sure it ends OK!
431         
432 */
433
434 void EM_select_flush(void)
435 {
436         EditMesh *em = G.editMesh;
437         EditEdge *eed;
438         EditFace *efa;
439         
440         for(eed= em->edges.first; eed; eed= eed->next) {
441                 if(eed->v1->f & eed->v2->f & SELECT) eed->f |= SELECT;
442         }
443         for(efa= em->faces.first; efa; efa= efa->next) {
444                 if(efa->v4) {
445                         if(efa->v1->f & efa->v2->f & efa->v3->f & efa->v4->f & SELECT ) efa->f |= SELECT;
446                 }
447                 else {
448                         if(efa->v1->f & efa->v2->f & efa->v3->f & SELECT ) efa->f |= SELECT;
449                 }
450         }
451 }
452
453 /* when vertices or edges can be selected, also make fgon consistant */
454 static void check_fgons_selection()
455 {
456         EditMesh *em = G.editMesh;
457         EditFace *efa, *efan;
458         EditEdge *eed;
459         ListBase *lbar;
460         int sel, desel, index, totfgon= 0;
461         
462         /* count amount of fgons */
463         for(eed= em->edges.first; eed; eed= eed->next) 
464                 if(eed->fgoni>totfgon) totfgon= eed->fgoni;
465         
466         if(totfgon==0) return;
467         
468         lbar= MEM_callocN((totfgon+1)*sizeof(ListBase), "listbase array");
469         
470         /* put all fgons in lbar */
471         for(efa= em->faces.first; efa; efa= efan) {
472                 efan= efa->next;
473                 index= efa->e1->fgoni;
474                 if(index==0) index= efa->e2->fgoni;
475                 if(index==0) index= efa->e3->fgoni;
476                 if(index==0 && efa->e4) index= efa->e4->fgoni;
477                 if(index) {
478                         BLI_remlink(&em->faces, efa);
479                         BLI_addtail(&lbar[index], efa);
480                 }
481         }
482         
483         /* now check the fgons */
484         for(index=1; index<=totfgon; index++) {
485                 /* we count on vertices/faces/edges being set OK, so we only have to set ngon itself */
486                 sel= desel= 0;
487                 for(efa= lbar[index].first; efa; efa= efa->next) {
488                         if(efa->e1->fgoni==0) {
489                                 if(efa->e1->f & SELECT) sel++;
490                                 else desel++;
491                         }
492                         if(efa->e2->fgoni==0) {
493                                 if(efa->e2->f & SELECT) sel++;
494                                 else desel++;
495                         }
496                         if(efa->e3->fgoni==0) {
497                                 if(efa->e3->f & SELECT) sel++;
498                                 else desel++;
499                         }
500                         if(efa->e4 && efa->e4->fgoni==0) {
501                                 if(efa->e4->f & SELECT) sel++;
502                                 else desel++;
503                         }
504                         
505                         if(sel && desel) break;
506                 }
507
508                 if(sel && desel) sel= 0;
509                 else if(sel) sel= 1;
510                 else sel= 0;
511                 
512                 /* select/deselect and put back */
513                 for(efa= lbar[index].first; efa; efa= efa->next) {
514                         if(sel) efa->f |= SELECT;
515                         else efa->f &= ~SELECT;
516                 }
517                 addlisttolist(&em->faces, &lbar[index]);
518         }
519         
520         MEM_freeN(lbar);
521 }
522
523
524 /* flush to edges & faces */
525
526 /* based on select mode it selects edges/faces 
527    assumed is that verts/edges/faces were properly selected themselves
528    with the calls above
529 */
530
531 void EM_selectmode_flush(void)
532 {
533         EditMesh *em = G.editMesh;
534         EditEdge *eed;
535         EditFace *efa;
536         
537         // flush to edges & faces
538         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
539                 for(eed= em->edges.first; eed; eed= eed->next) {
540                         if(eed->v1->f & eed->v2->f & SELECT) eed->f |= SELECT;
541                         else 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                                 else efa->f &= ~SELECT;
547                         }
548                         else {
549                                 if(efa->v1->f & efa->v2->f & efa->v3->f & SELECT) efa->f |= SELECT;
550                                 else efa->f &= ~SELECT;
551                         }
552                 }
553         }
554         // flush to faces
555         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
556                 for(efa= em->faces.first; efa; efa= efa->next) {
557                         if(efa->e4) {
558                                 if(efa->e1->f & efa->e2->f & efa->e3->f & efa->e4->f & SELECT) efa->f |= SELECT;
559                                 else efa->f &= ~SELECT;
560                         }
561                         else {
562                                 if(efa->e1->f & efa->e2->f & efa->e3->f & SELECT) efa->f |= SELECT;
563                                 else efa->f &= ~SELECT;
564                         }
565                 }
566         }       
567         // make sure selected faces have selected edges too, for extrude (hack?)
568         else if(G.scene->selectmode & SCE_SELECT_FACE) {
569                 for(efa= em->faces.first; efa; efa= efa->next) {
570                         if(efa->f & SELECT) EM_select_face(efa, 1);
571                 }
572         }
573         check_fgons_selection();
574
575 }
576
577 void EM_convertsel(short oldmode, short selectmode)
578 {
579         EditMesh *em = G.editMesh;
580         EditVert *eve;
581         EditEdge *eed;
582         EditFace *efa;
583         /*clear flags*/
584         for(eve= em->verts.first; eve; eve= eve->next) eve->f1 = 0;
585         for(eed= em->edges.first; eed; eed= eed->next) eed->f1 = 0;
586         for(efa= em->faces.first; efa; efa= efa->next) efa->f1 = 0;
587         
588         /*have to find out what the selectionmode was previously*/
589         if(oldmode == SCE_SELECT_VERTEX) {
590                 if(selectmode == SCE_SELECT_EDGE){
591                         /*select all edges associated with every selected vertex*/
592                         for(eed= em->edges.first; eed; eed= eed->next){
593                                 if(eed->v1->f&SELECT) eed->f1 = 1;
594                                 else if(eed->v2->f&SELECT) eed->f1 = 1;
595                         }
596                         
597                         for(eed= em->edges.first; eed; eed= eed->next){
598                                 if(eed->f1 == 1) EM_select_edge(eed,1); 
599                         }
600                 }               
601                 else if(selectmode == SCE_SELECT_FACE){
602                         /*select all faces associated with every selected vertex*/
603                         for(efa= em->faces.first; efa; efa= efa->next){
604                                 if(efa->v1->f&SELECT) efa->f1 = 1;
605                                 else if(efa->v2->f&SELECT) efa->f1 = 1;
606                                 else if(efa->v3->f&SELECT) efa->f1 = 1;
607                                 else{ 
608                                         if(efa->v4){
609                                                 if(efa->v4->f&SELECT) efa->f1 =1;
610                                         }
611                                 }
612                         }
613                         for(efa= em->faces.first; efa; efa= efa->next){
614                                 if(efa->f1 == 1) EM_select_face(efa,1);
615                         }
616                 }
617         }
618         
619         if(oldmode == SCE_SELECT_EDGE){
620                 if(selectmode == SCE_SELECT_FACE){
621                         for(efa= em->faces.first; efa; efa= efa->next){
622                                 if(efa->e1->f&SELECT) efa->f1 = 1;
623                                 else if(efa->e2->f&SELECT) efa->f1 = 1;
624                                 else if(efa->e3->f&SELECT) efa->f1 = 1;
625                                 else if(efa->e4){
626                                         if(efa->e4->f&SELECT) efa->f1 = 1;
627                                 }
628                         }
629                         for(efa= em->faces.first; efa; efa= efa->next){
630                                 if(efa->f1 == 1) EM_select_face(efa,1);
631                         }
632                 }
633         }
634         
635         check_fgons_selection();
636 }
637
638 /* when switching select mode, makes sure selection is consistant for editing */
639 /* also for paranoia checks to make sure edge or face mode works */
640 void EM_selectmode_set(void)
641 {
642         EditMesh *em = G.editMesh;
643         EditVert *eve;
644         EditEdge *eed;
645         EditFace *efa;
646         
647         EM_strip_selections(); /*strip EditSelections from em->selected that are not relevant to new mode*/
648         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
649                 /* vertices -> edges -> faces */
650                 for (eed= em->edges.first; eed; eed= eed->next) eed->f &= ~SELECT;
651                 for (efa= em->faces.first; efa; efa= efa->next) efa->f &= ~SELECT;
652                 
653                 EM_select_flush();
654         }
655         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
656                 /* deselect vertices, and select again based on edge select */
657                 for(eve= em->verts.first; eve; eve= eve->next) eve->f &= ~SELECT;
658                 for(eed= em->edges.first; eed; eed= eed->next) 
659                         if(eed->f & SELECT) EM_select_edge(eed, 1);
660                 /* selects faces based on edge status */
661                 EM_selectmode_flush();
662         }
663         else if(G.scene->selectmode & SCE_SELECT_FACE) {
664                 /* deselect eges, and select again based on face select */
665                 for(eed= em->edges.first; eed; eed= eed->next) EM_select_edge(eed, 0);
666                 
667                 for(efa= em->faces.first; efa; efa= efa->next) 
668                         if(efa->f & SELECT) EM_select_face(efa, 1);
669         }
670 }
671
672 /* paranoia check, actually only for entering editmode. rule:
673 - vertex hidden, always means edge is hidden too
674 - edge hidden, always means face is hidden too
675 - face hidden, dont change anything
676 */
677 void EM_hide_reset(void)
678 {
679         EditMesh *em = G.editMesh;
680         EditEdge *eed;
681         EditFace *efa;
682         
683         for(eed= em->edges.first; eed; eed= eed->next) 
684                 if(eed->v1->h || eed->v2->h) eed->h |= 1;
685                 
686         for(efa= em->faces.first; efa; efa= efa->next) 
687                 if((efa->e1->h & 1) || (efa->e2->h & 1) || (efa->e3->h & 1) || (efa->e4 && (efa->e4->h & 1)))
688                         efa->h= 1;
689                 
690 }
691
692
693 /* ********  EXTRUDE ********* */
694
695 static void add_normal_aligned(float *nor, float *add)
696 {
697         if( INPR(nor, add) < 0.0 ) 
698                 VecSubf(nor, nor, add);
699         else
700                 VecAddf(nor, nor, add);
701 }
702
703 static void set_edge_directions_f2(int val)
704 {
705         EditMesh *em= G.editMesh;
706         EditFace *efa;
707         int do_all= 1;
708         
709         /* edge directions are used for extrude, to detect direction of edges that make new faces */
710         /* we have set 'f2' flags in edges that need to get a direction set (e.g. get new face) */
711         /* the val argument differs... so we need it as arg */
712         
713         for(efa= em->faces.first; efa; efa= efa->next) {
714                 if(efa->f & SELECT) {
715                         do_all= 0;
716                         if(efa->e1->f2<val) {
717                                 if(efa->e1->v1 == efa->v1) efa->e1->dir= 0;
718                                 else efa->e1->dir= 1;
719                         }
720                         if(efa->e2->f2<val) {
721                                 if(efa->e2->v1 == efa->v2) efa->e2->dir= 0;
722                                 else efa->e2->dir= 1;
723                         }
724                         if(efa->e3->f2<val) {
725                                 if(efa->e3->v1 == efa->v3) efa->e3->dir= 0;
726                                 else efa->e3->dir= 1;
727                         }
728                         if(efa->e4 && efa->e4->f2<val) {
729                                 if(efa->e4->v1 == efa->v4) efa->e4->dir= 0;
730                                 else efa->e4->dir= 1;
731                         }
732                 }
733         }       
734         /* ok, no faces done... then we at least set it for exterior edges */
735         if(do_all) {
736                 for(efa= em->faces.first; efa; efa= efa->next) {
737                         if(efa->e1->v1 == efa->v1) efa->e1->dir= 0;
738                         else efa->e1->dir= 1;
739                         if(efa->e2->v1 == efa->v2) efa->e2->dir= 0;
740                         else efa->e2->dir= 1;
741                         if(efa->e3->v1 == efa->v3) efa->e3->dir= 0;
742                         else efa->e3->dir= 1;
743                         if(efa->e4) {
744                                 if(efa->e4->v1 == efa->v4) efa->e4->dir= 0;
745                                 else efa->e4->dir= 1;
746                         }
747                 }       
748         }
749 }
750
751 /* individual face extrude */
752 /* will use vertex normals for extrusion directions, so *nor is unaffected */
753 short extrudeflag_face_indiv(short flag, float *nor)
754 {
755         EditMesh *em = G.editMesh;
756         EditVert *eve, *v1, *v2, *v3, *v4;
757         EditEdge *eed;
758         EditFace *efa, *nextfa;
759         
760         if(G.obedit==0 || get_mesh(G.obedit)==0) return 0;
761         
762         /* selected edges with 1 or more selected face become faces */
763         /* selected faces each makes new faces */
764         /* always remove old faces, keeps volumes manifold */
765         /* select the new extrusion, deselect old */
766         
767         /* step 1; init, count faces in edges */
768         recalc_editnormals();
769         
770         for(eve= em->verts.first; eve; eve= eve->next) eve->f1= 0;      // new select flag
771
772         for(eed= em->edges.first; eed; eed= eed->next) {
773                 eed->f2= 0; // amount of unselected faces
774         }
775         for(efa= em->faces.first; efa; efa= efa->next) {
776                 if(efa->f & SELECT);
777                 else {
778                         efa->e1->f2++;
779                         efa->e2->f2++;
780                         efa->e3->f2++;
781                         if(efa->e4) efa->e4->f2++;
782                 }
783         }
784
785         /* step 2: make new faces from faces */
786         for(efa= em->faces.last; efa; efa= efa->prev) {
787                 if(efa->f & SELECT) {
788                         v1= addvertlist(efa->v1->co);
789                         v2= addvertlist(efa->v2->co);
790                         v3= addvertlist(efa->v3->co);
791                         v1->f1= v2->f1= v3->f1= 1;
792                         VECCOPY(v1->no, efa->n);
793                         VECCOPY(v2->no, efa->n);
794                         VECCOPY(v3->no, efa->n);
795                         if(efa->v4) {
796                                 v4= addvertlist(efa->v4->co); 
797                                 v4->f1= 1;
798                                 VECCOPY(v4->no, efa->n);
799                         }
800                         else v4= NULL;
801                         
802                         /* side faces, clockwise */
803                         addfacelist(efa->v2, v2, v1, efa->v1, efa, NULL);
804                         addfacelist(efa->v3, v3, v2, efa->v2, efa, NULL);
805                         if(efa->v4) {
806                                 addfacelist(efa->v4, v4, v3, efa->v3, efa, NULL);
807                                 addfacelist(efa->v1, v1, v4, efa->v4, efa, NULL);
808                         }
809                         else {
810                                 addfacelist(efa->v1, v1, v3, efa->v3, efa, NULL);
811                         }
812                         /* top face */
813                         addfacelist(v1, v2, v3, v4, efa, NULL);
814                 }
815         }
816         
817         /* step 3: remove old faces */
818         efa= em->faces.first;
819         while(efa) {
820                 nextfa= efa->next;
821                 if(efa->f & SELECT) {
822                         BLI_remlink(&em->faces, efa);
823                         free_editface(efa);
824                 }
825                 efa= nextfa;
826         }
827
828         /* step 4: redo selection */
829         EM_clear_flag_all(SELECT);
830         
831         for(eve= em->verts.first; eve; eve= eve->next) {
832                 if(eve->f1)  eve->f |= SELECT;
833         }
834         
835         EM_select_flush();
836         
837         return 'n';
838 }
839
840
841 /* extrudes individual edges */
842 /* nor is filled with constraint vector */
843 short extrudeflag_edges_indiv(short flag, float *nor) 
844 {
845         EditMesh *em = G.editMesh;
846         EditVert *eve;
847         EditEdge *eed;
848         EditFace *efa;
849         
850         for(eve= em->verts.first; eve; eve= eve->next) eve->tmp.v = NULL;
851         for(eed= em->edges.first; eed; eed= eed->next) {
852                 eed->tmp.f = NULL;
853                 eed->f2= ((eed->f & flag)!=0);
854         }
855         
856         set_edge_directions_f2(2);
857
858         /* sample for next loop */
859         for(efa= em->faces.first; efa; efa= efa->next) {
860                 efa->e1->tmp.f = efa;
861                 efa->e2->tmp.f = efa;
862                 efa->e3->tmp.f = efa;
863                 if(efa->e4) efa->e4->tmp.f = efa;
864         }
865         /* make the faces */
866         for(eed= em->edges.first; eed; eed= eed->next) {
867                 if(eed->f & flag) {
868                         if(eed->v1->tmp.v == NULL) 
869                                 eed->v1->tmp.v = addvertlist(eed->v1->co);
870                         if(eed->v2->tmp.v == NULL) 
871                                 eed->v2->tmp.v = addvertlist(eed->v2->co);
872                         
873                         if(eed->dir==1) 
874                                 addfacelist(eed->v1, eed->v2, 
875                                                         eed->v2->tmp.v, eed->v1->tmp.v, 
876                                                         eed->tmp.f, NULL);
877                         else 
878                                 addfacelist(eed->v2, eed->v1, 
879                                                         eed->v1->tmp.v, eed->v2->tmp.v, 
880                                                         eed->tmp.f, NULL);
881
882                         /* for transform */
883                         if(eed->tmp.f) {
884                                 efa = eed->tmp.f;
885                                 if (efa->f & SELECT) add_normal_aligned(nor, efa->n);
886                         }
887                 }
888         }
889         Normalise(nor);
890         
891         /* set correct selection */
892         EM_clear_flag_all(SELECT);
893         for(eve= em->verts.last; eve; eve= eve->prev) {
894                 if(eve->tmp.v) {
895                         eve->tmp.v->f |= flag;
896                 }
897         }
898
899         for(eed= em->edges.first; eed; eed= eed->next) {
900                 if(eed->v1->f & eed->v2->f & flag) eed->f |= flag;
901         }
902         
903         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // g is grab
904         return 'n';  // n is for normal constraint
905 }
906
907 /* extrudes individual vertices */
908 short extrudeflag_verts_indiv(short flag, float *nor) 
909 {
910         EditMesh *em = G.editMesh;
911         EditVert *eve;
912         
913         /* make the edges */
914         for(eve= em->verts.first; eve; eve= eve->next) {
915                 if(eve->f & flag) {
916                         eve->tmp.v = addvertlist(eve->co);
917                         addedgelist(eve, eve->tmp.v, NULL);
918                 }
919                 else eve->tmp.v = NULL;
920         }
921         
922         /* set correct selection */
923         EM_clear_flag_all(SELECT);
924
925         for(eve= em->verts.last; eve; eve= eve->prev) 
926                 if (eve->tmp.v) 
927                         eve->tmp.v->f |= flag;
928
929         return 'g';     // g is grab
930 }
931
932
933 /* this is actually a recode of extrudeflag(), using proper edge/face select */
934 /* hurms, doesnt use 'flag' yet, but its not called by primitive making stuff anyway */
935 static short extrudeflag_edge(short flag, float *nor)
936 {
937         /* all select edges/faces: extrude */
938         /* old select is cleared, in new ones it is set */
939         EditMesh *em = G.editMesh;
940         EditVert *eve, *nextve;
941         EditEdge *eed, *nexted;
942         EditFace *efa, *nextfa;
943         short del_old= 0;
944         
945         if(G.obedit==0 || get_mesh(G.obedit)==0) return 0;
946         
947         /* selected edges with 0 or 1 selected face become faces */
948         /* selected faces generate new faces */
949
950         /* if *one* selected face has edge with unselected face; remove old selected faces */
951         
952         /* if selected edge is not used anymore; remove */
953         /* if selected vertex is not used anymore: remove */
954         
955         /* select the new extrusion, deselect old */
956         
957         
958         /* step 1; init, count faces in edges */
959         recalc_editnormals();
960         
961         for(eve= em->verts.first; eve; eve= eve->next) {
962                 eve->tmp.v = NULL;
963                 eve->f1= 0;
964         }
965
966         for(eed= em->edges.first; eed; eed= eed->next) {
967                 eed->f1= 0; // amount of unselected faces
968                 eed->f2= 0; // amount of selected faces
969                 if(eed->f & SELECT) {
970                         eed->v1->f1= 1; // we call this 'selected vertex' now
971                         eed->v2->f1= 1;
972                 }
973                 eed->tmp.f = NULL;              // here we tuck face pointer, as sample
974         }
975         for(efa= em->faces.first; efa; efa= efa->next) {
976                 if(efa->f & SELECT) {
977                         efa->e1->f2++;
978                         efa->e2->f2++;
979                         efa->e3->f2++;
980                         if(efa->e4) efa->e4->f2++;
981                         
982                         // sample for next loop
983                         efa->e1->tmp.f = efa;
984                         efa->e2->tmp.f = efa;
985                         efa->e3->tmp.f = efa;
986                         if(efa->e4) efa->e4->tmp.f = efa;
987                 }
988                 else {
989                         efa->e1->f1++;
990                         efa->e2->f1++;
991                         efa->e3->f1++;
992                         if(efa->e4) efa->e4->f1++;
993                 }
994         }
995         
996         set_edge_directions_f2(2);
997         
998         /* step 1.5: if *one* selected face has edge with unselected face; remove old selected faces */
999         for(efa= em->faces.last; efa; efa= efa->prev) {
1000                 if(efa->f & SELECT) {
1001                         if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1 || (efa->e4 && efa->e4->f1)) {
1002                                 del_old= 1;
1003                                 break;
1004                         }
1005                 }
1006         }
1007                                 
1008         /* step 2: make new faces from edges */
1009         for(eed= em->edges.last; eed; eed= eed->prev) {
1010                 if(eed->f & SELECT) {
1011                         if(eed->f2<2) {
1012                                 if(eed->v1->tmp.v == NULL)
1013                                         eed->v1->tmp.v = addvertlist(eed->v1->co);
1014                                 if(eed->v2->tmp.v == NULL)
1015                                         eed->v2->tmp.v = addvertlist(eed->v2->co);
1016                                 
1017                                 /* if del_old, the preferred normal direction is exact 
1018                                  * opposite as for keep old faces
1019                                  */
1020                                 if(eed->dir!=del_old) 
1021                                         addfacelist(eed->v1, eed->v2, 
1022                                                                 eed->v2->tmp.v, eed->v1->tmp.v, 
1023                                                                 eed->tmp.f, NULL);
1024                                 else 
1025                                         addfacelist(eed->v2, eed->v1, 
1026                                                                 eed->v1->tmp.v, eed->v2->tmp.v,
1027                                                                 eed->tmp.f, NULL);
1028                         }
1029                 }
1030         }
1031         
1032         /* step 3: make new faces from faces */
1033         for(efa= em->faces.last; efa; efa= efa->prev) {
1034                 if(efa->f & SELECT) {
1035                         if (efa->v1->tmp.v == NULL) 
1036                                 efa->v1->tmp.v = addvertlist(efa->v1->co);
1037                         if (efa->v2->tmp.v ==NULL)
1038                                 efa->v2->tmp.v = addvertlist(efa->v2->co);
1039                         if (efa->v3->tmp.v ==NULL) 
1040                                 efa->v3->tmp.v = addvertlist(efa->v3->co);
1041                         if (efa->v4 && (efa->v4->tmp.v == NULL)) 
1042                                 efa->v4->tmp.v = addvertlist(efa->v4->co);
1043                         
1044                         if(del_old==0) {        // keep old faces means flipping normal
1045                                 if(efa->v4)
1046                                         addfacelist(efa->v4->tmp.v, efa->v3->tmp.v, 
1047                                                                 efa->v2->tmp.v, efa->v1->tmp.v, efa, efa);
1048                                 else
1049                                         addfacelist(efa->v3->tmp.v, efa->v2->tmp.v, 
1050                                                                 efa->v1->tmp.v, NULL, efa, efa);
1051                         }
1052                         else {
1053                                 if(efa->v4)
1054                                         addfacelist(efa->v1->tmp.v, efa->v2->tmp.v, 
1055                                                                 efa->v3->tmp.v, efa->v4->tmp.v, efa, efa);
1056                                 else
1057                                         addfacelist(efa->v1->tmp.v, efa->v2->tmp.v, 
1058                                                                 efa->v3->tmp.v, NULL, efa, efa);
1059                         }
1060         
1061                         /* for transform */
1062                         add_normal_aligned(nor, efa->n);
1063                 }
1064         }
1065         
1066         if(del_old) {
1067                 /* step 4: remove old faces, if del_old */
1068                 efa= em->faces.first;
1069                 while(efa) {
1070                         nextfa= efa->next;
1071                         if(efa->f & SELECT) {
1072                                 BLI_remlink(&em->faces, efa);
1073                                 free_editface(efa);
1074                         }
1075                         efa= nextfa;
1076                 }
1077         
1078                 /* step 5: remove selected unused edges */
1079                 /* start tagging again */
1080                 for(eed= em->edges.first; eed; eed= eed->next) eed->f1=0;
1081                 for(efa= em->faces.first; efa; efa= efa->next) {
1082                         efa->e1->f1= 1;
1083                         efa->e2->f1= 1;
1084                         efa->e3->f1= 1;
1085                         if(efa->e4) efa->e4->f1= 1;
1086                 }
1087                 /* remove */
1088                 eed= em->edges.first; 
1089                 while(eed) {
1090                         nexted= eed->next;
1091                         if(eed->f & SELECT) {
1092                                 if(eed->f1==0) {
1093                                         remedge(eed);
1094                                         free_editedge(eed);
1095                                 }
1096                         }
1097                         eed= nexted;
1098                 }
1099         
1100                 /* step 6: remove selected unused vertices */
1101                 for(eed= em->edges.first; eed; eed= eed->next) 
1102                         eed->v1->f1= eed->v2->f1= 0;
1103                 
1104                 eve= em->verts.first;
1105                 while(eve) {
1106                         nextve= eve->next;
1107                         if(eve->f1) {
1108                                 // hack... but we need it for step 7, redoing selection
1109                                 if(eve->tmp.v) eve->tmp.v->tmp.v= eve->tmp.v;
1110                                 
1111                                 BLI_remlink(&em->verts, eve);
1112                                 free_editvert(eve);
1113                         }
1114                         eve= nextve;
1115                 }
1116         }
1117         
1118         Normalise(nor); // translation normal grab
1119         
1120         /* step 7: redo selection */
1121         EM_clear_flag_all(SELECT);
1122
1123         for(eve= em->verts.first; eve; eve= eve->next) {
1124                 if(eve->tmp.v) {
1125                         eve->tmp.v->f |= SELECT;
1126                 }
1127         }
1128
1129         EM_select_flush();
1130
1131         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // grab
1132         return 'n'; // normal constraint 
1133 }
1134
1135 short extrudeflag_vert(short flag, float *nor)
1136 {
1137         /* all verts/edges/faces with (f & 'flag'): extrude */
1138         /* from old verts, 'flag' is cleared, in new ones it is set */
1139         EditMesh *em = G.editMesh;
1140         EditVert *eve, *v1, *v2, *v3, *v4, *nextve;
1141         EditEdge *eed, *e1, *e2, *e3, *e4, *nexted;
1142         EditFace *efa, *efa2, *nextvl;
1143         short sel=0, del_old= 0, is_face_sel=0;
1144
1145         if(G.obedit==0 || get_mesh(G.obedit)==0) return 0;
1146
1147         /* clear vert flag f1, we use this to detect a loose selected vertice */
1148         eve= em->verts.first;
1149         while(eve) {
1150                 if(eve->f & flag) eve->f1= 1;
1151                 else eve->f1= 0;
1152                 eve= eve->next;
1153         }
1154         /* clear edges counter flag, if selected we set it at 1 */
1155         eed= em->edges.first;
1156         while(eed) {
1157                 if( (eed->v1->f & flag) && (eed->v2->f & flag) ) {
1158                         eed->f2= 1;
1159                         eed->v1->f1= 0;
1160                         eed->v2->f1= 0;
1161                 }
1162                 else eed->f2= 0;
1163                 
1164                 eed->f1= 1;             /* this indicates it is an 'old' edge (in this routine we make new ones) */
1165                 eed->tmp.f = NULL;      /* used as sample */
1166                 
1167                 eed= eed->next;
1168         }
1169
1170         /* we set a flag in all selected faces, and increase the associated edge counters */
1171
1172         efa= em->faces.first;
1173         while(efa) {
1174                 efa->f1= 0;
1175
1176                 if(faceselectedAND(efa, flag)) {
1177                         e1= efa->e1;
1178                         e2= efa->e2;
1179                         e3= efa->e3;
1180                         e4= efa->e4;
1181
1182                         if(e1->f2 < 3) e1->f2++;
1183                         if(e2->f2 < 3) e2->f2++;
1184                         if(e3->f2 < 3) e3->f2++;
1185                         if(e4 && e4->f2 < 3) e4->f2++;
1186                         
1187                         efa->f1= 1;
1188                         is_face_sel= 1; // for del_old
1189                 }
1190                 else if(faceselectedOR(efa, flag)) {
1191                         e1= efa->e1;
1192                         e2= efa->e2;
1193                         e3= efa->e3;
1194                         e4= efa->e4;
1195                         
1196                         if( (e1->v1->f & flag) && (e1->v2->f & flag) ) e1->f1= 2;
1197                         if( (e2->v1->f & flag) && (e2->v2->f & flag) ) e2->f1= 2;
1198                         if( (e3->v1->f & flag) && (e3->v2->f & flag) ) e3->f1= 2;
1199                         if( e4 && (e4->v1->f & flag) && (e4->v2->f & flag) ) e4->f1= 2;
1200                 }
1201                 
1202                 // sample for next loop
1203                 efa->e1->tmp.f = efa;
1204                 efa->e2->tmp.f = efa;
1205                 efa->e3->tmp.f = efa;
1206                 if(efa->e4) efa->e4->tmp.f = efa;
1207
1208                 efa= efa->next;
1209         }
1210
1211         set_edge_directions_f2(3);
1212
1213         /* the current state now is:
1214                 eve->f1==1: loose selected vertex 
1215
1216                 eed->f2==0 : edge is not selected, no extrude
1217                 eed->f2==1 : edge selected, is not part of a face, extrude
1218                 eed->f2==2 : edge selected, is part of 1 face, extrude
1219                 eed->f2==3 : edge selected, is part of more faces, no extrude
1220                 
1221                 eed->f1==0: new edge
1222                 eed->f1==1: edge selected, is part of selected face, when eed->f==3: remove
1223                 eed->f1==2: edge selected, part of a partially selected face
1224                                         
1225                 efa->f1==1 : duplicate this face
1226         */
1227
1228         /* copy all selected vertices, */
1229         /* write pointer to new vert in old struct at eve->tmp.v */
1230         eve= em->verts.last;
1231         while(eve) {
1232                 eve->f &= ~128;  /* clear, for later test for loose verts */
1233                 if(eve->f & flag) {
1234                         sel= 1;
1235                         v1= addvertlist(0);
1236                         
1237                         VECCOPY(v1->co, eve->co);
1238                         v1->f= eve->f;
1239                         eve->f-= flag;
1240                         eve->tmp.v = v1;
1241                 }
1242                 else eve->tmp.v = 0;
1243                 eve= eve->prev;
1244         }
1245
1246         if(sel==0) return 0;
1247
1248         /* all edges with eed->f2==1 or eed->f2==2 become faces */
1249         
1250         /* if del_old==1 then extrude is in partial geometry, to keep it manifold.
1251                                          verts with f1==0 and (eve->f & 128)==0) are removed
1252                          edges with eed->f2>2 are removed
1253                                          faces with efa->f1 are removed
1254            if del_old==0 the extrude creates a volume.
1255         */
1256         
1257          /* find if we delete old faces */
1258         if(is_face_sel) {
1259                 for(eed= em->edges.first; eed; eed= eed->next) {
1260                         if( (eed->f2==1 || eed->f2==2) ) {
1261                                 if(eed->f1==2) {
1262                                         del_old= 1;
1263                                         break;
1264                                 }
1265                         }
1266                 }
1267         }
1268         
1269         eed= em->edges.last;
1270         while(eed) {
1271                 nexted= eed->prev;
1272                 if( eed->f2<3) {
1273                         eed->v1->f |= 128;  /* = no loose vert! */
1274                         eed->v2->f |= 128;
1275                 }
1276                 if( (eed->f2==1 || eed->f2==2) ) {
1277         
1278                         /* if del_old, the preferred normal direction is exact opposite as for keep old faces */
1279                         if(eed->dir != del_old) 
1280                                 efa2 = addfacelist(eed->v1, eed->v2, 
1281                                                                   eed->v2->tmp.v, eed->v1->tmp.v, 
1282                                                                   NULL, NULL);
1283                         else 
1284                                 efa2 = addfacelist(eed->v2, eed->v1, 
1285                                                                    eed->v1->tmp.v, eed->v2->tmp.v, 
1286                                                                    NULL, NULL);
1287                         
1288                         if(eed->tmp.f) {
1289                                 efa = eed->tmp.f;
1290                                 efa2->mat_nr= efa->mat_nr;
1291                                 efa2->tf= efa->tf;
1292                                 efa2->flag= efa->flag;
1293                         }
1294                         
1295                         /* Needs smarter adaption of existing creases.
1296                          * If addedgelist is used, make sure seams are set to 0 on these
1297                          * new edges, since we do not want to add any seams on extrusion.
1298                          */
1299                         efa2->e1->crease= eed->crease;
1300                         efa2->e2->crease= eed->crease;
1301                         efa2->e3->crease= eed->crease;
1302                         if(efa2->e4) efa2->e4->crease= eed->crease;
1303                 }
1304
1305                 eed= nexted;
1306         }
1307         if(del_old) {
1308                 eed= em->edges.first;
1309                 while(eed) {
1310                         nexted= eed->next;
1311                         if(eed->f2==3 && eed->f1==1) {
1312                                 remedge(eed);
1313                                 free_editedge(eed);
1314                         }
1315                         eed= nexted;
1316                 }
1317         }
1318         /* duplicate faces, if necessary remove old ones  */
1319         efa= em->faces.first;
1320         while(efa) {
1321                 nextvl= efa->next;
1322                 if(efa->f1 & 1) {
1323                 
1324                         v1 = efa->v1->tmp.v;
1325                         v2 = efa->v2->tmp.v;
1326                         v3 = efa->v3->tmp.v;
1327                         if(efa->v4) 
1328                                 v4 = efa->v4->tmp.v; 
1329                         else
1330                                 v4= 0;
1331
1332                         /* hmm .. not sure about edges here */
1333                         if(del_old==0)  // if we keep old, we flip normal
1334                                 efa2= addfacelist(v3, v2, v1, v4, efa, efa); 
1335                         else
1336                                 efa2= addfacelist(v1, v2, v3, v4, efa, efa);
1337                         
1338                         /* for transform */
1339                         add_normal_aligned(nor, efa->n);
1340
1341                         if(del_old) {
1342                                 BLI_remlink(&em->faces, efa);
1343                                 free_editface(efa);
1344                         }
1345                 }
1346                 efa= nextvl;
1347         }
1348         
1349         Normalise(nor); // for grab
1350         
1351         /* for all vertices with eve->tmp.v!=0 
1352                 if eve->f1==1: make edge
1353                 if flag!=128 : if del_old==1: remove
1354         */
1355         eve= em->verts.last;
1356         while(eve) {
1357                 nextve= eve->prev;
1358                 if(eve->tmp.v) {
1359                         if(eve->f1==1) addedgelist(eve, eve->tmp.v, NULL);
1360                         else if( (eve->f & 128)==0) {
1361                                 if(del_old) {
1362                                         BLI_remlink(&em->verts,eve);
1363                                         free_editvert(eve);
1364                                         eve= NULL;
1365                                 }
1366                         }
1367                 }
1368                 if(eve) {
1369                         eve->f &= ~128;
1370                 }
1371                 eve= nextve;
1372         }
1373         // since its vertex select mode now, it also deselects higher order
1374         EM_selectmode_flush();
1375
1376         if(nor[0]==0.0 && nor[1]==0.0 && nor[2]==0.0) return 'g'; // g is grab, for correct undo print
1377         return 'n';
1378 }
1379
1380 /* generic extrude */
1381 short extrudeflag(short flag, float *nor)
1382 {
1383         if(G.scene->selectmode & SCE_SELECT_VERTEX)
1384                 return extrudeflag_vert(flag, nor);
1385         else 
1386                 return extrudeflag_edge(flag, nor);
1387                 
1388 }
1389
1390 void rotateflag(short flag, float *cent, float rotmat[][3])
1391 {
1392         /* all verts with (flag & 'flag') rotate */
1393         EditMesh *em = G.editMesh;
1394         EditVert *eve;
1395
1396         eve= em->verts.first;
1397         while(eve) {
1398                 if(eve->f & flag) {
1399                         eve->co[0]-=cent[0];
1400                         eve->co[1]-=cent[1];
1401                         eve->co[2]-=cent[2];
1402                         Mat3MulVecfl(rotmat,eve->co);
1403                         eve->co[0]+=cent[0];
1404                         eve->co[1]+=cent[1];
1405                         eve->co[2]+=cent[2];
1406                 }
1407                 eve= eve->next;
1408         }
1409 }
1410
1411 void translateflag(short flag, float *vec)
1412 {
1413         /* all verts with (flag & 'flag') translate */
1414         EditMesh *em = G.editMesh;
1415         EditVert *eve;
1416
1417         eve= em->verts.first;
1418         while(eve) {
1419                 if(eve->f & flag) {
1420                         eve->co[0]+=vec[0];
1421                         eve->co[1]+=vec[1];
1422                         eve->co[2]+=vec[2];
1423                 }
1424                 eve= eve->next;
1425         }
1426 }
1427
1428 /* helper call for below */
1429 static EditVert *adduplicate_vertex(EditVert *eve, int flag)
1430 {
1431         EditVert *v1= addvertlist(eve->co);
1432         
1433         v1->f= eve->f;
1434         eve->f-= flag;
1435         eve->f|= 128;
1436         
1437         eve->tmp.v = v1;
1438         
1439         /* FIXME: Copy deformation weight ? */
1440         v1->totweight = eve->totweight;
1441         if (eve->totweight){
1442                 v1->dw = MEM_mallocN (eve->totweight * sizeof(MDeformWeight), "deformWeight");
1443                 memcpy (v1->dw, eve->dw, eve->totweight * sizeof(MDeformWeight));
1444         }
1445         else
1446                 v1->dw=NULL;
1447         
1448         return v1;
1449 }
1450
1451 /* old selection has flag 128 set, and flag 'flag' cleared
1452 new selection has flag 'flag' set */
1453 void adduplicateflag(int flag)
1454 {
1455         EditMesh *em = G.editMesh;
1456         EditVert *eve, *v1, *v2, *v3, *v4;
1457         EditEdge *eed, *newed;
1458         EditFace *efa, *newfa;
1459
1460         EM_clear_flag_all(128);
1461         EM_selectmode_set();    // paranoia check, selection now is consistant
1462
1463         /* vertices first */
1464         for(eve= em->verts.last; eve; eve= eve->prev) {
1465
1466                 if(eve->f & flag)
1467                         adduplicate_vertex(eve, flag);
1468                 else 
1469                         eve->tmp.v = NULL;
1470         }
1471         
1472         /* copy edges, note that vertex selection can be independent of edge */
1473         for(eed= em->edges.last; eed; eed= eed->prev) {
1474                 if( eed->f & flag ) {
1475                         v1 = eed->v1->tmp.v;
1476                         if(v1==NULL) v1= adduplicate_vertex(eed->v1, flag);
1477                         v2 = eed->v2->tmp.v;
1478                         if(v2==NULL) v2= adduplicate_vertex(eed->v2, flag);
1479                         
1480                         newed= addedgelist(v1, v2, eed);
1481                         
1482                         newed->f= eed->f;
1483                         eed->f -= flag;
1484                         eed->f |= 128;
1485                 }
1486         }
1487
1488         /* then duplicate faces, again create new vertices if needed */
1489         for(efa= em->faces.last; efa; efa= efa->prev) {
1490                 if(efa->f & flag) {
1491                         v1 = efa->v1->tmp.v;
1492                         if(v1==NULL) v1= adduplicate_vertex(efa->v1, flag);
1493                         v2 = efa->v2->tmp.v;
1494                         if(v2==NULL) v2= adduplicate_vertex(efa->v2, flag);
1495                         v3 = efa->v3->tmp.v;
1496                         if(v3==NULL) v3= adduplicate_vertex(efa->v3, flag);
1497                         if(efa->v4) {
1498                                 v4 = efa->v4->tmp.v; 
1499                                 if(v4==NULL) v4= adduplicate_vertex(efa->v4, flag);
1500                         }
1501                         else v4= NULL;
1502                         
1503                         newfa= addfacelist(v1, v2, v3, v4, efa, efa); 
1504                         
1505                         newfa->f= efa->f;
1506                         efa->f -= flag;
1507                         efa->f |= 128;
1508                 }
1509         }
1510         
1511         EM_fgon_flags();        // redo flags and indices for fgons
1512 }
1513
1514 void delfaceflag(int flag)
1515 {
1516         EditMesh *em = G.editMesh;
1517         /* delete all faces with 'flag', including loose edges and loose vertices */
1518         /* this is maybe a bit weird, but this function is used for 'split' and 'separate' */
1519         /* in remaining vertices/edges 'flag' is cleared */
1520         EditVert *eve,*nextve;
1521         EditEdge *eed, *nexted;
1522         EditFace *efa,*nextvl;
1523
1524         /* to detect loose edges, we put f2 flag on 1 */
1525         for(eed= em->edges.first; eed; eed= eed->next) {
1526                 if(eed->f & flag) eed->f2= 1;
1527                 else eed->f2= 0;
1528         }
1529         
1530         /* delete faces */
1531         efa= em->faces.first;
1532         while(efa) {
1533                 nextvl= efa->next;
1534                 if(efa->f & flag) {
1535                         
1536                         efa->e1->f2= 1;
1537                         efa->e2->f2= 1;
1538                         efa->e3->f2= 1;
1539                         if(efa->e4) {
1540                                 efa->e4->f2= 1;
1541                         }
1542                                                                 
1543                         BLI_remlink(&em->faces, efa);
1544                         free_editface(efa);
1545                 }
1546                 efa= nextvl;
1547         }
1548         
1549         /* all remaining faces: make sure we keep the edges */
1550         for(efa= em->faces.first; efa; efa= efa->next) {
1551                 efa->e1->f2= 0;
1552                 efa->e2->f2= 0;
1553                 efa->e3->f2= 0;
1554                 if(efa->e4) {
1555                         efa->e4->f2= 0;
1556                 }
1557         }
1558         
1559         /* remove tagged edges, and clear remaining ones */
1560         eed= em->edges.first;
1561         while(eed) {
1562                 nexted= eed->next;
1563                 
1564                 if(eed->f2==1) {
1565                         remedge(eed);
1566                         free_editedge(eed);
1567                 }
1568                 else {
1569                         eed->f &= ~flag;
1570                         eed->v1->f &= ~flag;
1571                         eed->v2->f &= ~flag;
1572                 }
1573                 eed= nexted;
1574         }
1575         
1576         /* vertices with 'flag' now are the loose ones, and will be removed */
1577         eve= em->verts.first;
1578         while(eve) {
1579                 nextve= eve->next;
1580                 if(eve->f & flag) {
1581                         BLI_remlink(&em->verts, eve);
1582                         free_editvert(eve);
1583                 }
1584                 eve= nextve;
1585         }
1586
1587 }
1588
1589 /* ********************* */
1590 #if 0
1591 static int check_vnormal_flip(float *n, float *vnorm) 
1592 {
1593         float inp;
1594
1595         inp= n[0]*vnorm[0]+n[1]*vnorm[1]+n[2]*vnorm[2];
1596
1597         /* angles 90 degrees: dont flip */
1598         if(inp> -0.000001) return 0;
1599
1600         return 1;
1601 }
1602 #endif
1603
1604 void flipface(EditFace *efa)
1605 {
1606         if(efa->v4) {
1607                 SWAP(EditVert *, efa->v2, efa->v4);
1608                 SWAP(EditEdge *, efa->e1, efa->e4);
1609                 SWAP(EditEdge *, efa->e2, efa->e3);
1610                 SWAP(unsigned int, efa->tf.col[1], efa->tf.col[3]);
1611                 SWAP(float, efa->tf.uv[1][0], efa->tf.uv[3][0]);
1612                 SWAP(float, efa->tf.uv[1][1], efa->tf.uv[3][1]);
1613         }
1614         else {
1615                 SWAP(EditVert *, efa->v2, efa->v3);
1616                 SWAP(EditEdge *, efa->e1, efa->e3);
1617                 SWAP(unsigned int, efa->tf.col[1], efa->tf.col[2]);
1618                 efa->e2->dir= 1-efa->e2->dir;
1619                 SWAP(float, efa->tf.uv[1][0], efa->tf.uv[2][0]);
1620                 SWAP(float, efa->tf.uv[1][1], efa->tf.uv[2][1]);
1621         }
1622         if(efa->v4) CalcNormFloat4(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co, efa->n);
1623         else CalcNormFloat(efa->v1->co, efa->v2->co, efa->v3->co, efa->n);
1624 }
1625
1626
1627 void flip_editnormals(void)
1628 {
1629         EditMesh *em = G.editMesh;
1630         EditFace *efa;
1631         
1632         efa= em->faces.first;
1633         while(efa) {
1634                 if( efa->f & SELECT ){
1635                         flipface(efa);
1636                 }
1637                 efa= efa->next;
1638         }
1639 }
1640
1641 /* does face centers too */
1642 void recalc_editnormals(void)
1643 {
1644         EditMesh *em = G.editMesh;
1645         EditFace *efa;
1646         EditVert *eve;
1647
1648         for(eve= em->verts.first; eve; eve=eve->next) {
1649                 eve->no[0] = eve->no[1] = eve->no[2] = 0.0;
1650         }
1651
1652         for(efa= em->faces.first; efa; efa=efa->next) {
1653                 if(efa->v4) {
1654                         CalcNormFloat4(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co, efa->n);
1655                         CalcCent4f(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
1656                         VecAddf(efa->v4->no, efa->v4->no, efa->n);
1657                 }
1658                 else {
1659                         CalcNormFloat(efa->v1->co, efa->v2->co, efa->v3->co, efa->n);
1660                         CalcCent3f(efa->cent, efa->v1->co, efa->v2->co, efa->v3->co);
1661                 }
1662                 VecAddf(efa->v1->no, efa->v1->no, efa->n);
1663                 VecAddf(efa->v2->no, efa->v2->no, efa->n);
1664                 VecAddf(efa->v3->no, efa->v3->no, efa->n);
1665         }
1666
1667         /* following Mesh convention; we use vertex coordinate itself for normal in this case */
1668         for(eve= em->verts.first; eve; eve=eve->next) {
1669                 if (Normalise(eve->no)==0.0) {
1670                         VECCOPY(eve->no, eve->co);
1671                         Normalise(eve->no);
1672                 }
1673         }
1674 }
1675
1676 int compareface(EditFace *vl1, EditFace *vl2)
1677 {
1678         EditVert *v1, *v2, *v3, *v4;
1679         
1680         if(vl1->v4 && vl2->v4) {
1681                 v1= vl2->v1;
1682                 v2= vl2->v2;
1683                 v3= vl2->v3;
1684                 v4= vl2->v4;
1685                 
1686                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1 || vl1->v4==v1) {
1687                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2 || vl1->v4==v2) {
1688                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3 || vl1->v4==v3) {
1689                                         if(vl1->v1==v4 || vl1->v2==v4 || vl1->v3==v4 || vl1->v4==v4) {
1690                                                 return 1;
1691                                         }
1692                                 }
1693                         }
1694                 }
1695         }
1696         else if(vl1->v4==0 && vl2->v4==0) {
1697                 v1= vl2->v1;
1698                 v2= vl2->v2;
1699                 v3= vl2->v3;
1700                 
1701                 if(vl1->v1==v1 || vl1->v2==v1 || vl1->v3==v1) {
1702                         if(vl1->v1==v2 || vl1->v2==v2 || vl1->v3==v2) {
1703                                 if(vl1->v1==v3 || vl1->v2==v3 || vl1->v3==v3) {
1704                                         return 1;
1705                                 }
1706                         }
1707                 }
1708         }
1709         
1710         return 0;
1711 }
1712
1713 /* checks for existance, not tria overlapping inside quad */
1714 EditFace *exist_face(EditVert *v1, EditVert *v2, EditVert *v3, EditVert *v4)
1715 {
1716         EditMesh *em = G.editMesh;
1717         EditFace *efa, efatest;
1718         
1719         efatest.v1= v1;
1720         efatest.v2= v2;
1721         efatest.v3= v3;
1722         efatest.v4= v4;
1723         
1724         efa= em->faces.first;
1725         while(efa) {
1726                 if(compareface(&efatest, efa)) return efa;
1727                 efa= efa->next;
1728         }
1729         return NULL;
1730 }
1731
1732 /* evaluate if entire quad is a proper convex quad */
1733 int convex(float *v1, float *v2, float *v3, float *v4)
1734 {
1735         float nor[3], nor1[3], nor2[3], vec[4][2];
1736         
1737         /* define projection, do both trias apart, quad is undefined! */
1738         CalcNormFloat(v1, v2, v3, nor1);
1739         CalcNormFloat(v1, v3, v4, nor2);
1740         nor[0]= ABS(nor1[0]) + ABS(nor2[0]);
1741         nor[1]= ABS(nor1[1]) + ABS(nor2[1]);
1742         nor[2]= ABS(nor1[2]) + ABS(nor2[2]);
1743
1744         if(nor[2] >= nor[0] && nor[2] >= nor[1]) {
1745                 vec[0][0]= v1[0]; vec[0][1]= v1[1];
1746                 vec[1][0]= v2[0]; vec[1][1]= v2[1];
1747                 vec[2][0]= v3[0]; vec[2][1]= v3[1];
1748                 vec[3][0]= v4[0]; vec[3][1]= v4[1];
1749         }
1750         else if(nor[1] >= nor[0] && nor[1]>= nor[2]) {
1751                 vec[0][0]= v1[0]; vec[0][1]= v1[2];
1752                 vec[1][0]= v2[0]; vec[1][1]= v2[2];
1753                 vec[2][0]= v3[0]; vec[2][1]= v3[2];
1754                 vec[3][0]= v4[0]; vec[3][1]= v4[2];
1755         }
1756         else {
1757                 vec[0][0]= v1[1]; vec[0][1]= v1[2];
1758                 vec[1][0]= v2[1]; vec[1][1]= v2[2];
1759                 vec[2][0]= v3[1]; vec[2][1]= v3[2];
1760                 vec[3][0]= v4[1]; vec[3][1]= v4[2];
1761         }
1762         
1763         /* linetests, the 2 diagonals have to instersect to be convex */
1764         if( IsectLL2Df(vec[0], vec[2], vec[1], vec[3]) > 0 ) return 1;
1765         return 0;
1766 }
1767
1768
1769 /* ********************* Fake Polgon support (FGon) ***************** */
1770
1771
1772 /* results in:
1773    - faces having ->fgonf flag set (also for draw)
1774    - edges having ->fgoni index set (for select)
1775 */
1776
1777 float EM_face_area(EditFace *efa)
1778 {
1779         if(efa->v4) return AreaQ3Dfl(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co);
1780         else return AreaT3Dfl(efa->v1->co, efa->v2->co, efa->v3->co);
1781 }
1782
1783 float EM_face_perimeter(EditFace *efa)
1784 {       
1785         if(efa->v4) return
1786                 VecLenf(efa->v1->co, efa->v2->co)+
1787                 VecLenf(efa->v2->co, efa->v3->co)+
1788                 VecLenf(efa->v3->co, efa->v4->co)+
1789                 VecLenf(efa->v4->co, efa->v1->co);
1790         
1791         else return
1792                 VecLenf(efa->v1->co, efa->v2->co)+
1793                 VecLenf(efa->v2->co, efa->v3->co)+
1794                 VecLenf(efa->v3->co, efa->v1->co);
1795 }
1796
1797 void EM_fgon_flags(void)
1798 {
1799         EditMesh *em = G.editMesh;
1800         EditFace *efa, *efan, *efamax;
1801         EditEdge *eed;
1802         ListBase listb={NULL, NULL};
1803         float size, maxsize;
1804         short done, curindex= 1;
1805         
1806         // for each face with fgon edge AND not fgon flag set
1807         for(eed= em->edges.first; eed; eed= eed->next) eed->fgoni= 0;  // index
1808         for(efa= em->faces.first; efa; efa= efa->next) efa->fgonf= 0;  // flag
1809         
1810         // for speed & simplicity, put fgon face candidates in new listbase
1811         efa= em->faces.first;
1812         while(efa) {
1813                 efan= efa->next;
1814                 if( (efa->e1->h & EM_FGON) || (efa->e2->h & EM_FGON) || 
1815                         (efa->e3->h & EM_FGON) || (efa->e4 && (efa->e4->h & EM_FGON)) ) {
1816                         BLI_remlink(&em->faces, efa);
1817                         BLI_addtail(&listb, efa);
1818                 }
1819                 efa= efan;
1820         }
1821         
1822         // find an undone face with fgon edge
1823         for(efa= listb.first; efa; efa= efa->next) {
1824                 if(efa->fgonf==0) {
1825                         
1826                         // init this face
1827                         efa->fgonf= EM_FGON;
1828                         if(efa->e1->h & EM_FGON) efa->e1->fgoni= curindex;
1829                         if(efa->e2->h & EM_FGON) efa->e2->fgoni= curindex;
1830                         if(efa->e3->h & EM_FGON) efa->e3->fgoni= curindex;
1831                         if(efa->e4 && (efa->e4->h & EM_FGON)) efa->e4->fgoni= curindex;
1832                         
1833                         // we search for largest face, to give facedot drawing rights
1834                         maxsize= EM_face_area(efa);
1835                         efamax= efa;
1836                         
1837                         // now flush curendex over edges and set faceflags
1838                         done= 1;
1839                         while(done==1) {
1840                                 done= 0;
1841                                 
1842                                 for(efan= listb.first; efan; efan= efan->next) {
1843                                         if(efan->fgonf==0) {
1844                                                 // if one if its edges has index set, do other too
1845                                                 if( (efan->e1->fgoni==curindex) || (efan->e2->fgoni==curindex) ||
1846                                                         (efan->e3->fgoni==curindex) || (efan->e4 && (efan->e4->fgoni==curindex)) ) {
1847                                                         
1848                                                         efan->fgonf= EM_FGON;
1849                                                         if(efan->e1->h & EM_FGON) efan->e1->fgoni= curindex;
1850                                                         if(efan->e2->h & EM_FGON) efan->e2->fgoni= curindex;
1851                                                         if(efan->e3->h & EM_FGON) efan->e3->fgoni= curindex;
1852                                                         if(efan->e4 && (efan->e4->h & EM_FGON)) efan->e4->fgoni= curindex;
1853                                                         
1854                                                         size= EM_face_area(efan);
1855                                                         if(size>maxsize) {
1856                                                                 efamax= efan;
1857                                                                 maxsize= size;
1858                                                         }
1859                                                         done= 1;
1860                                                 }
1861                                         }
1862                                 }
1863                         }
1864                         
1865                         efamax->fgonf |= EM_FGON_DRAW;
1866                         curindex++;
1867
1868                 }
1869         }
1870
1871         // put fgon face candidates back in listbase
1872         efa= listb.first;
1873         while(efa) {
1874                 efan= efa->next;
1875                 BLI_remlink(&listb, efa);
1876                 BLI_addtail(&em->faces, efa);
1877                 efa= efan;
1878         }
1879         
1880         // remove fgon flags when edge not in fgon (anymore)
1881         for(eed= em->edges.first; eed; eed= eed->next) {
1882                 if(eed->fgoni==0) eed->h &= ~EM_FGON;
1883         }
1884         
1885 }