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