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