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