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