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