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