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