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