Cleaned up some warnings.
[blender.git] / source / blender / src / editmesh_mods.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_mods.c, UI level access, no geometry changes 
36
37 */
38
39 #include <stdlib.h>
40 #include <string.h>
41 #include <math.h>
42
43 #include "MEM_guardedalloc.h"
44
45 #include "MTC_matrixops.h"
46
47 #include "DNA_mesh_types.h"
48 #include "DNA_material_types.h"
49 #include "DNA_meshdata_types.h"
50 #include "DNA_modifier_types.h"
51 #include "DNA_object_types.h"
52 #include "DNA_texture_types.h"
53 #include "DNA_scene_types.h"
54 #include "DNA_screen_types.h"
55 #include "DNA_view3d_types.h"
56
57 #include "BLI_blenlib.h"
58 #include "BLI_arithb.h"
59 #include "BLI_editVert.h"
60 #include "BLI_rand.h"
61
62 #include "BKE_displist.h"
63 #include "BKE_depsgraph.h"
64 #include "BKE_DerivedMesh.h"
65 #include "BKE_customdata.h"
66 #include "BKE_global.h"
67 #include "BKE_mesh.h"
68 #include "BKE_material.h"
69 #include "BKE_texture.h"
70 #include "BKE_utildefines.h"
71
72 #ifdef WITH_VERSE
73 #include "BKE_verse.h"
74 #endif
75
76 #include "BIF_editmesh.h"
77 #include "BIF_resources.h"
78 #include "BIF_gl.h"
79 #include "BIF_glutil.h"
80 #include "BIF_graphics.h"
81 #include "BIF_interface.h"
82 #include "BIF_meshtools.h"
83 #include "BIF_mywindow.h"
84 #include "BIF_resources.h"
85 #include "BIF_screen.h"
86 #include "BIF_space.h"
87 #include "BIF_toolbox.h"
88
89 #ifdef WITH_VERSE
90 #include "BIF_verse.h"
91 #endif
92
93 #include "BDR_drawobject.h"
94 #include "BDR_editobject.h"
95
96 #include "BSE_drawview.h"
97 #include "BSE_edit.h"
98 #include "BSE_view.h"
99
100 #include "IMB_imbuf_types.h"
101 #include "IMB_imbuf.h"
102
103 #include "RE_render_ext.h"  /* externtex */
104
105 #include "multires.h"
106 #include "mydevice.h"
107 #include "blendef.h"
108
109 #include "editmesh.h"
110
111
112 /* ****************************** MIRROR **************** */
113
114 void EM_select_mirrored(void)
115 {
116         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
117                 EditMesh *em = G.editMesh;
118                 EditVert *eve, *v1;
119                 
120                 for(eve= em->verts.first; eve; eve= eve->next) {
121                         if(eve->f & SELECT) {
122                                 v1= editmesh_get_x_mirror_vert(G.obedit, eve->co);
123                                 if(v1) {
124                                         eve->f &= ~SELECT;
125                                         v1->f |= SELECT;
126                                 }
127                         }
128                 }
129         }
130 }
131
132 /* ****************************** SELECTION ROUTINES **************** */
133
134 unsigned int em_solidoffs=0, em_wireoffs=0, em_vertoffs=0;      /* set in drawobject.c ... for colorindices */
135
136 /* facilities for border select and circle select */
137 static char *selbuf= NULL;
138
139 /* opengl doesn't support concave... */
140 static void draw_triangulated(short mcords[][2], short tot)
141 {
142         ListBase lb={NULL, NULL};
143         DispList *dl;
144         float *fp;
145         int a;
146         
147         /* make displist */
148         dl= MEM_callocN(sizeof(DispList), "poly disp");
149         dl->type= DL_POLY;
150         dl->parts= 1;
151         dl->nr= tot;
152         dl->verts= fp=  MEM_callocN(tot*3*sizeof(float), "poly verts");
153         BLI_addtail(&lb, dl);
154         
155         for(a=0; a<tot; a++, fp+=3) {
156                 fp[0]= (float)mcords[a][0];
157                 fp[1]= (float)mcords[a][1];
158         }
159         
160         /* do the fill */
161         filldisplist(&lb, &lb);
162
163         /* do the draw */
164         dl= lb.first;   /* filldisplist adds in head of list */
165         if(dl->type==DL_INDEX3) {
166                 int *index;
167                 
168                 a= dl->parts;
169                 fp= dl->verts;
170                 index= dl->index;
171                 glBegin(GL_TRIANGLES);
172                 while(a--) {
173                         glVertex3fv(fp+3*index[0]);
174                         glVertex3fv(fp+3*index[1]);
175                         glVertex3fv(fp+3*index[2]);
176                         index+= 3;
177                 }
178                 glEnd();
179         }
180         
181         freedisplist(&lb);
182 }
183
184
185 /* reads rect, and builds selection array for quick lookup */
186 /* returns if all is OK */
187 int EM_init_backbuf_border(short xmin, short ymin, short xmax, short ymax)
188 {
189         struct ImBuf *buf;
190         unsigned int *dr;
191         int a;
192         
193         if(G.obedit==NULL || G.vd->drawtype<OB_SOLID || (G.vd->flag & V3D_ZBUF_SELECT)==0) return 0;
194         if(em_vertoffs==0) return 0;
195         
196         buf= read_backbuf(xmin, ymin, xmax, ymax);
197         if(buf==NULL) return 0;
198
199         dr = buf->rect;
200         
201         /* build selection lookup */
202         selbuf= MEM_callocN(em_vertoffs+1, "selbuf");
203         
204         a= (xmax-xmin+1)*(ymax-ymin+1);
205         while(a--) {
206                 if(*dr>0 && *dr<=em_vertoffs) 
207                         selbuf[*dr]= 1;
208                 dr++;
209         }
210         IMB_freeImBuf(buf);
211         return 1;
212 }
213
214 int EM_check_backbuf(unsigned int index)
215 {
216         if(selbuf==NULL) return 1;
217         if(index>0 && index<=em_vertoffs)
218                 return selbuf[index];
219         return 0;
220 }
221
222 void EM_free_backbuf(void)
223 {
224         if(selbuf) MEM_freeN(selbuf);
225         selbuf= NULL;
226 }
227
228 /* mcords is a polygon mask
229    - grab backbuffer,
230    - draw with black in backbuffer, 
231    - grab again and compare
232    returns 'OK' 
233 */
234 int EM_mask_init_backbuf_border(short mcords[][2], short tot, short xmin, short ymin, short xmax, short ymax)
235 {
236         unsigned int *dr, *drm;
237         struct ImBuf *buf, *bufmask;
238         int a;
239         
240         /* method in use for face selecting too */
241         if(G.obedit==NULL) {
242                 if(G.f & G_FACESELECT);
243                 else return 0;
244         }
245         else if(G.vd->drawtype<OB_SOLID || (G.vd->flag & V3D_ZBUF_SELECT)==0) return 0;
246
247         if(em_vertoffs==0) return 0;
248         
249         buf= read_backbuf(xmin, ymin, xmax, ymax);
250         if(buf==NULL) return 0;
251
252         dr = buf->rect;
253
254         /* draw the mask */
255 #ifdef __APPLE__
256         glDrawBuffer(GL_AUX0);
257 #endif
258         glDisable(GL_DEPTH_TEST);
259         
260         persp(PERSP_WIN);
261         glColor3ub(0, 0, 0);
262         
263         /* yah, opengl doesn't do concave... tsk! */
264         draw_triangulated(mcords, tot); 
265         
266         glBegin(GL_LINE_LOOP);  /* for zero sized masks, lines */
267         for(a=0; a<tot; a++) glVertex2s(mcords[a][0], mcords[a][1]);
268         glEnd();
269         
270         persp(PERSP_VIEW);
271         glFinish();     /* to be sure readpixels sees mask */
272         
273         glDrawBuffer(GL_BACK);
274         
275         /* grab mask */
276         bufmask= read_backbuf(xmin, ymin, xmax, ymax);
277         drm = bufmask->rect;
278         if(bufmask==NULL) return 0; /* only when mem alloc fails, go crash somewhere else! */
279         
280         /* build selection lookup */
281         selbuf= MEM_callocN(em_vertoffs+1, "selbuf");
282         
283         a= (xmax-xmin+1)*(ymax-ymin+1);
284         while(a--) {
285                 if(*dr>0 && *dr<=em_vertoffs && *drm==0) selbuf[*dr]= 1;
286                 dr++; drm++;
287         }
288         IMB_freeImBuf(buf);
289         IMB_freeImBuf(bufmask);
290         return 1;
291         
292 }
293
294 /* circle shaped sample area */
295 int EM_init_backbuf_circle(short xs, short ys, short rads)
296 {
297         struct ImBuf *buf;
298         unsigned int *dr;
299         short xmin, ymin, xmax, ymax, xc, yc;
300         int radsq;
301         
302         /* method in use for face selecting too */
303         if(G.obedit==NULL) {
304                 if(G.f & G_FACESELECT);
305                 else return 0;
306         }
307         else if(G.vd->drawtype<OB_SOLID || (G.vd->flag & V3D_ZBUF_SELECT)==0) return 0;
308         if(em_vertoffs==0) return 0;
309         
310         xmin= xs-rads; xmax= xs+rads;
311         ymin= ys-rads; ymax= ys+rads;
312         buf= read_backbuf(xmin, ymin, xmax, ymax);
313         if(buf==NULL) return 0;
314
315         dr = buf->rect;
316         
317         /* build selection lookup */
318         selbuf= MEM_callocN(em_vertoffs+1, "selbuf");
319         radsq= rads*rads;
320         for(yc= -rads; yc<=rads; yc++) {
321                 for(xc= -rads; xc<=rads; xc++, dr++) {
322                         if(xc*xc + yc*yc < radsq) {
323                                 if(*dr>0 && *dr<=em_vertoffs) selbuf[*dr]= 1;
324                         }
325                 }
326         }
327
328         IMB_freeImBuf(buf);
329         return 1;
330         
331 }
332
333 static void findnearestvert__doClosest(void *userData, EditVert *eve, int x, int y, int index)
334 {
335         struct { short mval[2], pass, select, strict; int dist, lastIndex, closestIndex; EditVert *closest; } *data = userData;
336
337         if (data->pass==0) {
338                 if (index<=data->lastIndex)
339                         return;
340         } else {
341                 if (index>data->lastIndex)
342                         return;
343         }
344
345         if (data->dist>3) {
346                 int temp = abs(data->mval[0] - x) + abs(data->mval[1]- y);
347                 if ((eve->f&1) == data->select) {
348                         if (data->strict == 1)
349                                 return;
350                         else
351                                 temp += 5;
352                 }
353
354                 if (temp<data->dist) {
355                         data->dist = temp;
356                         data->closest = eve;
357                         data->closestIndex = index;
358                 }
359         }
360 }
361
362
363
364
365 static unsigned int findnearestvert__backbufIndextest(unsigned int index){
366                 EditVert *eve = BLI_findlink(&G.editMesh->verts, index-1);
367                 if(eve && (eve->f & SELECT)) return 0;
368                 return 1; 
369 }
370 /**
371  * findnearestvert
372  * 
373  * dist (in/out): minimal distance to the nearest and at the end, actual distance
374  * sel: selection bias
375  *              if SELECT, selected vertice are given a 5 pixel bias to make them farter than unselect verts
376  *              if 0, unselected vertice are given the bias
377  * strict: if 1, the vertice corresponding to the sel parameter are ignored and not just biased 
378  */
379 EditVert *findnearestvert(int *dist, short sel, short strict)
380 {
381         short mval[2];
382
383         getmouseco_areawin(mval);
384         if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)){
385                 int distance;
386                 unsigned int index;
387                 EditVert *eve;
388                 
389                 if(strict) index = sample_backbuf_rect(mval, 50, em_wireoffs, 0xFFFFFF, &distance, strict, findnearestvert__backbufIndextest); 
390                 else index = sample_backbuf_rect(mval, 50, em_wireoffs, 0xFFFFFF, &distance, 0, NULL); 
391                 
392                 eve = BLI_findlink(&G.editMesh->verts, index-1);
393                 
394                 if(eve && distance < *dist) {
395                         *dist = distance;
396                         return eve;
397                 } else {
398                         return NULL;
399                 }
400                         
401         }
402         else {
403                 struct { short mval[2], pass, select, strict; int dist, lastIndex, closestIndex; EditVert *closest; } data;
404                 static int lastSelectedIndex=0;
405                 static EditVert *lastSelected=NULL;
406
407                 if (lastSelected && BLI_findlink(&G.editMesh->verts, lastSelectedIndex)!=lastSelected) {
408                         lastSelectedIndex = 0;
409                         lastSelected = NULL;
410                 }
411
412                 data.lastIndex = lastSelectedIndex;
413                 data.mval[0] = mval[0];
414                 data.mval[1] = mval[1];
415                 data.select = sel;
416                 data.dist = *dist;
417                 data.strict = strict;
418                 data.closest = NULL;
419                 data.closestIndex = 0;
420
421                 data.pass = 0;
422                 mesh_foreachScreenVert(findnearestvert__doClosest, &data, 1);
423
424                 if (data.dist>3) {
425                         data.pass = 1;
426                         mesh_foreachScreenVert(findnearestvert__doClosest, &data, 1);
427                 }
428
429                 *dist = data.dist;
430                 lastSelected = data.closest;
431                 lastSelectedIndex = data.closestIndex;
432
433                 return data.closest;
434         }
435 }
436
437 /* returns labda for closest distance v1 to line-piece v2-v3 */
438 static float labda_PdistVL2Dfl( float *v1, float *v2, float *v3) 
439 {
440         float rc[2], len;
441         
442         rc[0]= v3[0]-v2[0];
443         rc[1]= v3[1]-v2[1];
444         len= rc[0]*rc[0]+ rc[1]*rc[1];
445         if(len==0.0f)
446                 return 0.0f;
447         
448         return ( rc[0]*(v1[0]-v2[0]) + rc[1]*(v1[1]-v2[1]) )/len;
449 }
450
451 /* note; uses G.vd, so needs active 3d window */
452 static void findnearestedge__doClosest(void *userData, EditEdge *eed, int x0, int y0, int x1, int y1, int index)
453 {
454         struct { float mval[2]; int dist; EditEdge *closest; } *data = userData;
455         float v1[2], v2[2];
456         int distance;
457                 
458         v1[0] = x0;
459         v1[1] = y0;
460         v2[0] = x1;
461         v2[1] = y1;
462                 
463         distance= PdistVL2Dfl(data->mval, v1, v2);
464                 
465         if(eed->f & SELECT) distance+=5;
466         if(distance < data->dist) {
467                 if(G.vd->flag & V3D_CLIPPING) {
468                         float labda= labda_PdistVL2Dfl(data->mval, v1, v2);
469                         float vec[3];
470
471                         vec[0]= eed->v1->co[0] + labda*(eed->v2->co[0] - eed->v1->co[0]);
472                         vec[1]= eed->v1->co[1] + labda*(eed->v2->co[1] - eed->v1->co[1]);
473                         vec[2]= eed->v1->co[2] + labda*(eed->v2->co[2] - eed->v1->co[2]);
474                         Mat4MulVecfl(G.obedit->obmat, vec);
475
476                         if(view3d_test_clipping(G.vd, vec)==0) {
477                                 data->dist = distance;
478                                 data->closest = eed;
479                         }
480                 }
481                 else {
482                         data->dist = distance;
483                         data->closest = eed;
484                 }
485         }
486 }
487 EditEdge *findnearestedge(int *dist)
488 {
489         short mval[2];
490                 
491         getmouseco_areawin(mval);
492
493         if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
494                 int distance;
495                 unsigned int index = sample_backbuf_rect(mval, 50, em_solidoffs, em_wireoffs, &distance,0, NULL);
496                 EditEdge *eed = BLI_findlink(&G.editMesh->edges, index-1);
497
498                 if (eed && distance<*dist) {
499                         *dist = distance;
500                         return eed;
501                 } else {
502                         return NULL;
503                 }
504         }
505         else {
506                 struct { float mval[2]; int dist; EditEdge *closest; } data;
507
508                 data.mval[0] = mval[0];
509                 data.mval[1] = mval[1];
510                 data.dist = *dist;
511                 data.closest = NULL;
512
513                 mesh_foreachScreenEdge(findnearestedge__doClosest, &data, 2);
514
515                 *dist = data.dist;
516                 return data.closest;
517         }
518 }
519
520 static void findnearestface__getDistance(void *userData, EditFace *efa, int x, int y, int index)
521 {
522         struct { short mval[2]; int dist; EditFace *toFace; } *data = userData;
523
524         if (efa==data->toFace) {
525                 int temp = abs(data->mval[0]-x) + abs(data->mval[1]-y);
526
527                 if (temp<data->dist)
528                         data->dist = temp;
529         }
530 }
531 static void findnearestface__doClosest(void *userData, EditFace *efa, int x, int y, int index)
532 {
533         struct { short mval[2], pass; int dist, lastIndex, closestIndex; EditFace *closest; } *data = userData;
534
535         if (data->pass==0) {
536                 if (index<=data->lastIndex)
537                         return;
538         } else {
539                 if (index>data->lastIndex)
540                         return;
541         }
542
543         if (data->dist>3) {
544                 int temp = abs(data->mval[0]-x) + abs(data->mval[1]-y);
545
546                 if (temp<data->dist) {
547                         data->dist = temp;
548                         data->closest = efa;
549                         data->closestIndex = index;
550                 }
551         }
552 }
553 static EditFace *findnearestface(int *dist)
554 {
555         short mval[2];
556
557         getmouseco_areawin(mval);
558
559         if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
560                 unsigned int index = sample_backbuf(mval[0], mval[1]);
561                 EditFace *efa = BLI_findlink(&G.editMesh->faces, index-1);
562
563                 if (efa) {
564                         struct { short mval[2]; int dist; EditFace *toFace; } data;
565
566                         data.mval[0] = mval[0];
567                         data.mval[1] = mval[1];
568                         data.dist = 0x7FFF;             /* largest short */
569                         data.toFace = efa;
570
571                         mesh_foreachScreenFace(findnearestface__getDistance, &data);
572
573                         if(G.scene->selectmode == SCE_SELECT_FACE || data.dist<*dist) { /* only faces, no dist check */
574                                 *dist= data.dist;
575                                 return efa;
576                         }
577                 }
578                 
579                 return NULL;
580         }
581         else {
582                 struct { short mval[2], pass; int dist, lastIndex, closestIndex; EditFace *closest; } data;
583                 static int lastSelectedIndex=0;
584                 static EditFace *lastSelected=NULL;
585
586                 if (lastSelected && BLI_findlink(&G.editMesh->faces, lastSelectedIndex)!=lastSelected) {
587                         lastSelectedIndex = 0;
588                         lastSelected = NULL;
589                 }
590
591                 data.lastIndex = lastSelectedIndex;
592                 data.mval[0] = mval[0];
593                 data.mval[1] = mval[1];
594                 data.dist = *dist;
595                 data.closest = NULL;
596                 data.closestIndex = 0;
597
598                 data.pass = 0;
599                 mesh_foreachScreenFace(findnearestface__doClosest, &data);
600
601                 if (data.dist>3) {
602                         data.pass = 1;
603                         mesh_foreachScreenFace(findnearestface__doClosest, &data);
604                 }
605
606                 *dist = data.dist;
607                 lastSelected = data.closest;
608                 lastSelectedIndex = data.closestIndex;
609
610                 return data.closest;
611         }
612 }
613
614 /* for interactivity, frontbuffer draw in current window */
615 static void draw_dm_mapped_vert__mapFunc(void *theVert, int index, float *co, float *no_f, short *no_s)
616 {
617         if (EM_get_vert_for_index(index)==theVert) {
618                 bglVertex3fv(co);
619         }
620 }
621 static void draw_dm_mapped_vert(DerivedMesh *dm, EditVert *eve)
622 {
623         EM_init_index_arrays(1, 0, 0);
624         bglBegin(GL_POINTS);
625         dm->foreachMappedVert(dm, draw_dm_mapped_vert__mapFunc, eve);
626         bglEnd();
627         EM_free_index_arrays();
628 }
629
630 static int draw_dm_mapped_edge__setDrawOptions(void *theEdge, int index)
631 {
632         return EM_get_edge_for_index(index)==theEdge;
633 }
634 static void draw_dm_mapped_edge(DerivedMesh *dm, EditEdge *eed)
635 {
636         EM_init_index_arrays(0, 1, 0);
637         dm->drawMappedEdges(dm, draw_dm_mapped_edge__setDrawOptions, eed);
638         EM_free_index_arrays();
639 }
640
641 static void draw_dm_mapped_face_center__mapFunc(void *theFace, int index, float *cent, float *no)
642 {
643         if (EM_get_face_for_index(index)==theFace) {
644                 bglVertex3fv(cent);
645         }
646 }
647 static void draw_dm_mapped_face_center(DerivedMesh *dm, EditFace *efa)
648 {
649         EM_init_index_arrays(0, 0, 1);
650         bglBegin(GL_POINTS);
651         dm->foreachMappedFaceCenter(dm, draw_dm_mapped_face_center__mapFunc, efa);
652         bglEnd();
653         EM_free_index_arrays();
654 }
655
656 static void unified_select_draw(EditVert *eve, EditEdge *eed, EditFace *efa)
657 {
658         DerivedMesh *dm = editmesh_get_derived_cage(CD_MASK_BAREMESH);
659
660         glDrawBuffer(GL_FRONT);
661
662         persp(PERSP_VIEW);
663         
664         if(G.vd->flag & V3D_CLIPPING)
665                 view3d_set_clipping(G.vd);
666         
667         glPushMatrix();
668         mymultmatrix(G.obedit->obmat);
669         
670         /* face selected */
671         if(efa) {
672                 if(G.scene->selectmode & SCE_SELECT_VERTEX) {
673                         glPointSize(BIF_GetThemeValuef(TH_VERTEX_SIZE));
674                         
675                         if(efa->f & SELECT) BIF_ThemeColor(TH_VERTEX_SELECT);
676                         else BIF_ThemeColor(TH_VERTEX);
677                         
678                         bglBegin(GL_POINTS);
679                         bglVertex3fv(efa->v1->co);
680                         bglVertex3fv(efa->v2->co);
681                         bglVertex3fv(efa->v3->co);
682                         if(efa->v4) bglVertex3fv(efa->v4->co);
683                         bglEnd();
684                 }
685
686                 if(G.scene->selectmode & (SCE_SELECT_EDGE|SCE_SELECT_FACE)) {
687                         if(efa->fgonf==0) {
688                                 BIF_ThemeColor((efa->f & SELECT)?TH_EDGE_SELECT:TH_WIRE);
689         
690                                 draw_dm_mapped_edge(dm, efa->e1);
691                                 draw_dm_mapped_edge(dm, efa->e2);
692                                 draw_dm_mapped_edge(dm, efa->e3);
693                                 if (efa->e4) {
694                                         draw_dm_mapped_edge(dm, efa->e4);
695                                 }
696                         }
697                 }
698                 
699                 if(G.scene->selectmode & SCE_SELECT_FACE) {
700                         if(efa->fgonf==0) {
701                                 glPointSize(BIF_GetThemeValuef(TH_FACEDOT_SIZE));
702                                 BIF_ThemeColor((efa->f & SELECT)?TH_FACE_DOT:TH_WIRE);
703
704                                 draw_dm_mapped_face_center(dm, efa);
705                         }
706                 }
707         }
708         /* edge selected */
709         if(eed) {
710                 if(G.scene->selectmode & (SCE_SELECT_EDGE|SCE_SELECT_FACE)) {
711                         BIF_ThemeColor((eed->f & SELECT)?TH_EDGE_SELECT:TH_WIRE);
712
713                         draw_dm_mapped_edge(dm, eed);
714                 }
715                 if(G.scene->selectmode & SCE_SELECT_VERTEX) {
716                         glPointSize(BIF_GetThemeValuef(TH_VERTEX_SIZE));
717                         
718                         BIF_ThemeColor((eed->f & SELECT)?TH_VERTEX_SELECT:TH_VERTEX);
719                         
720                         draw_dm_mapped_vert(dm, eed->v1);
721                         draw_dm_mapped_vert(dm, eed->v2);
722                 }
723         }
724         if(eve) {
725                 if(G.scene->selectmode & SCE_SELECT_VERTEX) {
726                         glPointSize(BIF_GetThemeValuef(TH_VERTEX_SIZE));
727                         
728                         BIF_ThemeColor((eve->f & SELECT)?TH_VERTEX_SELECT:TH_VERTEX);
729                         
730                         draw_dm_mapped_vert(dm, eve);
731                 }
732         }
733
734         glPointSize(1.0);
735         glPopMatrix();
736
737         bglFlush();
738         glDrawBuffer(GL_BACK);
739
740         if(G.vd->flag & V3D_CLIPPING)
741                 view3d_clr_clipping();
742         
743         /* signal that frontbuf differs from back */
744         curarea->win_swap= WIN_FRONT_OK;
745
746         dm->release(dm);
747 }
748
749
750 /* best distance based on screen coords. 
751    use g.scene->selectmode to define how to use 
752    selected vertices and edges get disadvantage
753    return 1 if found one
754 */
755 static int unified_findnearest(EditVert **eve, EditEdge **eed, EditFace **efa) 
756 {
757         int dist= 75;
758         
759         *eve= NULL;
760         *eed= NULL;
761         *efa= NULL;
762         
763         if(G.scene->selectmode & SCE_SELECT_VERTEX)
764                 *eve= findnearestvert(&dist, SELECT, 0);
765         if(G.scene->selectmode & SCE_SELECT_FACE)
766                 *efa= findnearestface(&dist);
767
768         dist-= 20;      /* since edges select lines, we give dots advantage of 20 pix */
769         if(G.scene->selectmode & SCE_SELECT_EDGE)
770                 *eed= findnearestedge(&dist);
771
772         /* return only one of 3 pointers, for frontbuffer redraws */
773         if(*eed) {
774                 *efa= NULL; *eve= NULL;
775         }
776         else if(*efa) {
777                 *eve= NULL;
778         }
779         
780         return (*eve || *eed || *efa);
781 }
782
783 /* this as a way to compare the ares, perim  of 2 faces thay will scale to different sizes
784  *0.5 so smaller faces arnt ALWAYS selected with a thresh of 1.0 */
785 #define SCALE_CMP(a,b) ((a+a*thresh >= b) && (a-(a*thresh*0.5) <= b))
786
787 /* ****************  GROUP SELECTS ************** */
788 /* selects new faces/edges/verts based on the
789  existing selection
790
791 FACES GROUP
792  mode 1: same material
793  mode 2: same image
794  mode 3: same area
795  mode 4: same perimeter
796  mode 5: same normal
797  mode 6: same co-planer
798 */
799 int facegroup_select(short mode)
800 {
801         EditMesh *em = G.editMesh;
802         EditFace *efa, *base_efa=NULL;
803         unsigned int selcount=0; /*count how many new faces we select*/
804         
805         /*deselcount, count how many deselected faces are left, so we can bail out early
806         also means that if there are no deselected faces, we can avoid a lot of looping */
807         unsigned int deselcount=0; 
808         
809         short ok=0;
810         float thresh=G.scene->toolsettings->select_thresh;
811         
812         for(efa= em->faces.first; efa; efa= efa->next) {
813                 if (!efa->h) {
814                         if (efa->f & SELECT) {
815                                 efa->f1=1;
816                                 ok=1;
817                         } else {
818                                 efa->f1=0;
819                                 deselcount++; /* a deselected face we may select later */
820                         }
821                 }
822         }
823         
824         if (!ok || !deselcount) /* no data selected OR no more data to select */
825                 return 0;
826         
827         /*if mode is 3 then record face areas, 4 record perimeter */
828         if (mode==3) {
829                 for(efa= em->faces.first; efa; efa= efa->next) {
830                         efa->tmp.fp= EM_face_area(efa);
831                 }
832         } else if (mode==4) {
833                 for(efa= em->faces.first; efa; efa= efa->next) {
834                         efa->tmp.fp= EM_face_perimeter(efa);
835                 }
836         }
837         
838         for(base_efa= em->faces.first; base_efa; base_efa= base_efa->next) {
839                 if (base_efa->f1) { /* This was one of the faces originaly selected */
840                         if (mode==1) { /* same material */
841                                 for(efa= em->faces.first; efa; efa= efa->next) {
842                                         if (
843                                                 !(efa->f & SELECT) &&
844                                                 !efa->h &&
845                                                 base_efa->mat_nr == efa->mat_nr
846                                         ) {
847                                                 EM_select_face(efa, 1);
848                                                 selcount++;
849                                                 deselcount--;
850                                                 if (!deselcount) /*have we selected all posible faces?, if so return*/
851                                                         return selcount;
852                                         }
853                                 }
854                         } else if (mode==2) { /* same image */
855                                 MTFace *tf, *base_tf;
856
857                                 base_tf = (MTFace*)CustomData_em_get(&em->fdata, base_efa->data,
858                                                                      CD_MTFACE);
859
860                                 if(!base_tf)
861                                         return selcount;
862
863                                 for(efa= em->faces.first; efa; efa= efa->next) {
864                                         if (!(efa->f & SELECT) && !efa->h) {
865                                                 tf = (MTFace*)CustomData_em_get(&em->fdata, efa->data,
866                                                                                 CD_MTFACE);
867
868                                                 if(base_tf->tpage == tf->tpage) {
869                                                         EM_select_face(efa, 1);
870                                                         selcount++;
871                                                         deselcount--;
872                                                         if (!deselcount) /*have we selected all posible faces?, if so return*/
873                                                                 return selcount;
874                                                 }
875                                         }
876                                 }
877                         } else if (mode==3 || mode==4) { /* same area OR same perimeter, both use the same temp var */
878                                 for(efa= em->faces.first; efa; efa= efa->next) {
879                                         if (
880                                                 (!(efa->f & SELECT) && !efa->h) &&
881                                                 SCALE_CMP(base_efa->tmp.fp, efa->tmp.fp)
882                                         ) {
883                                                 EM_select_face(efa, 1);
884                                                 selcount++;
885                                                 deselcount--;
886                                                 if (!deselcount) /*have we selected all posible faces?, if so return*/
887                                                         return selcount;
888                                         }
889                                 }
890                         } else if (mode==5) { /* same normal */
891                                 float angle;
892                                 for(efa= em->faces.first; efa; efa= efa->next) {
893                                         if (!(efa->f & SELECT) && !efa->h) {
894                                                 angle= VecAngle2(base_efa->n, efa->n);
895                                                 if (angle/180.0<=thresh) {
896                                                         EM_select_face(efa, 1);
897                                                         selcount++;
898                                                         deselcount--;
899                                                         if (!deselcount) /*have we selected all posible faces?, if so return*/
900                                                                 return selcount;
901                                                 }
902                                         }
903                                 }
904                         } else if (mode==6) { /* same planer */
905                                 float angle, base_dot, dot;
906                                 base_dot= Inpf(base_efa->cent, base_efa->n);
907                                 for(efa= em->faces.first; efa; efa= efa->next) {
908                                         if (!(efa->f & SELECT) && !efa->h) {
909                                                 angle= VecAngle2(base_efa->n, efa->n);
910                                                 if (angle/180.0<=thresh) {
911                                                         dot=Inpf(efa->cent, base_efa->n);
912                                                         if (fabs(base_dot-dot) <= thresh) {
913                                                                 EM_select_face(efa, 1);
914                                                                 selcount++;
915                                                                 deselcount--;
916                                                                 if (!deselcount) /*have we selected all posible faces?, if so return*/
917                                                                         return selcount;
918                                                         }
919                                                 }
920                                         }
921                                 }
922                         }
923                 }
924         } /* end base_efa loop */
925         return selcount;
926 }
927
928
929 /*
930 EDGE GROUP
931  mode 1: same length
932  mode 2: same direction
933  mode 3: same number of face users
934  mode 4: similar face angles.
935  mode 5: similar crease
936 */
937
938 /* this function is only used by edgegroup_select's edge angle */
939
940
941
942 int edgegroup_select(short mode)
943 {
944         EditMesh *em = G.editMesh;
945         EditEdge *eed, *base_eed=NULL;
946         unsigned int selcount=0; /* count how many new edges we select*/
947         
948         /*count how many visible selected edges there are,
949         so we can return when there are none left */
950         unsigned int deselcount=0;
951         
952         short ok=0;
953         float thresh=G.scene->toolsettings->select_thresh;
954         
955         for(eed= em->edges.first; eed; eed= eed->next) {
956                 if (!eed->h) {
957                         if (eed->f & SELECT) {
958                                 eed->f1=1;
959                                 ok=1;
960                         } else {
961                                 eed->f1=0;
962                                 deselcount++;
963                         }
964                         /* set all eed->tmp.l to 0 we use it later.
965                         for counting face users*/
966                         eed->tmp.l=0;
967                         eed->f2=0; /* only for mode 4, edge animations */
968                 }
969         }
970         
971         if (!ok || !deselcount) /* no data selected OR no more data to select*/
972                 return 0;
973         
974         if (mode==1) { /*store length*/
975                 for(eed= em->edges.first; eed; eed= eed->next) {
976                         if (!eed->h) /* dont calc data for hidden edges*/
977                                 eed->tmp.fp= VecLenf(eed->v1->co, eed->v2->co);
978                 }
979         } else if (mode==3) { /*store face users*/
980                 EditFace *efa;
981                 /* cound how many faces each edge uses use tmp->l */
982                 for(efa= em->faces.first; efa; efa= efa->next) {
983                         efa->e1->tmp.l++;
984                         efa->e2->tmp.l++;
985                         efa->e3->tmp.l++;
986                         if (efa->e4) efa->e4->tmp.l++;
987                 }
988         } else if (mode==4) { /*store edge angles */
989                 EditFace *efa;
990                 int j;
991                 /* cound how many faces each edge uses use tmp.l */
992                 for(efa= em->faces.first; efa; efa= efa->next) {
993                         /* here we use the edges temp data to assign a face
994                         if a face has alredy been assigned (eed->f2==1)
995                         we calculate the angle between the current face and
996                         the edges previously found face.
997                         store the angle in eed->tmp.fp (loosing the face eed->tmp.f)
998                         but tagging eed->f2==2, so we know not to look at it again.
999                         This only works for edges that connect to 2 faces. but its good enough
1000                         */
1001                         
1002                         /* se we can loop through face edges*/
1003                         j=0;
1004                         eed= efa->e1;
1005                         while (j<4) {
1006                                 if (j==1) eed= efa->e2;
1007                                 else if (j==2) eed= efa->e3;
1008                                 else if (j==3) {
1009                                         eed= efa->e4;
1010                                         if (!eed)
1011                                                 break;
1012                                 } /* done looping */
1013                                 
1014                                 if (!eed->h) { /* dont calc data for hidden edges*/
1015                                         if (eed->f2==2)
1016                                                 break;
1017                                         else if (eed->f2==0) /* first access, assign the face */
1018                                                 eed->tmp.f= efa;
1019                                         else if (eed->f2==1) /* second, we assign the angle*/
1020                                                 eed->tmp.fp= VecAngle2(eed->tmp.f->n, efa->n)/180;
1021                                         eed->f2++; /* f2==0 no face assigned. f2==1 one face found. f2==2 angle calculated.*/
1022                                 }
1023                                 j++;
1024                         }
1025                 }
1026         }
1027         
1028         for(base_eed= em->edges.first; base_eed; base_eed= base_eed->next) {
1029                 if (base_eed->f1) {
1030                         if (mode==1) { /* same length */
1031                                 for(eed= em->edges.first; eed; eed= eed->next) {
1032                                         if (
1033                                                 !(eed->f & SELECT) &&
1034                                                 !eed->h &&
1035                                                 SCALE_CMP(base_eed->tmp.fp, eed->tmp.fp)
1036                                         ) {
1037                                                 EM_select_edge(eed, 1);
1038                                                 selcount++;
1039                                                 deselcount--;
1040                                                 if (!deselcount) /*have we selected all posible faces?, if so return*/
1041                                                         return selcount;
1042                                         }
1043                                 }
1044                         } else if (mode==2) { /* same direction */
1045                                 float base_dir[3], dir[3], angle;
1046                                 VecSubf(base_dir, base_eed->v1->co, base_eed->v2->co);
1047                                 for(eed= em->edges.first; eed; eed= eed->next) {
1048                                         if (!(eed->f & SELECT) && !eed->h) {
1049                                                 VecSubf(dir, eed->v1->co, eed->v2->co);
1050                                                 angle= VecAngle2(base_dir, dir);
1051                                                 
1052                                                 if (angle>90) /* use the smallest angle between the edges */
1053                                                         angle= fabs(angle-180.0f);
1054                                                 
1055                                                 if (angle/90.0<=thresh) {
1056                                                         EM_select_edge(eed, 1);
1057                                                         selcount++;
1058                                                         deselcount--;
1059                                                         if (!deselcount) /*have we selected all posible faces?, if so return*/
1060                                                                 return selcount;
1061                                                 }
1062                                         }
1063                                 }
1064                         } else if (mode==3) { /* face users */                          
1065                                 for(eed= em->edges.first; eed; eed= eed->next) {
1066                                         if (
1067                                                 !(eed->f & SELECT) &&
1068                                                 !eed->h &&
1069                                                 base_eed->tmp.l==eed->tmp.l
1070                                         ) {
1071                                                 EM_select_edge(eed, 1);
1072                                                 selcount++;
1073                                                 deselcount--;
1074                                                 if (!deselcount) /*have we selected all posible faces?, if so return*/
1075                                                         return selcount;
1076                                         }
1077                                 }
1078                         } else if (mode==4 && base_eed->f2==2) { /* edge angles, f2==2 means the edge has an angle. */                          
1079                                 for(eed= em->edges.first; eed; eed= eed->next) {
1080                                         if (
1081                                                 !(eed->f & SELECT) &&
1082                                                 !eed->h &&
1083                                                 eed->f2==2 &&
1084                                                 (fabs(base_eed->tmp.fp-eed->tmp.fp)<=thresh)
1085                                         ) {
1086                                                 EM_select_edge(eed, 1);
1087                                                 selcount++;
1088                                                 deselcount--;
1089                                                 if (!deselcount) /*have we selected all posible faces?, if so return*/
1090                                                         return selcount;
1091                                         }
1092                                 }
1093                         } else if (mode==5) { /* edge crease */
1094                                 for(eed= em->edges.first; eed; eed= eed->next) {
1095                                         if (
1096                                                 !(eed->f & SELECT) &&
1097                                                 !eed->h &&
1098                                                 (fabs(base_eed->crease-eed->crease) <= thresh)
1099                                         ) {
1100                                                 EM_select_edge(eed, 1);
1101                                                 selcount++;
1102                                                 deselcount--;
1103                                                 if (!deselcount) /*have we selected all posible faces?, if so return*/
1104                                                         return selcount;
1105                                         }
1106                                 }
1107                         }
1108                 }
1109         } 
1110         return selcount;
1111 }
1112
1113
1114 /*
1115 VERT GROUP
1116  mode 1: same normal
1117  mode 2: same number of face users
1118  mode 3: same vertex groups
1119 */
1120 int vertgroup_select(short mode)
1121 {
1122         EditMesh *em = G.editMesh;
1123         EditVert *eve, *base_eve=NULL;
1124         
1125         unsigned int selcount=0; /* count how many new edges we select*/
1126         
1127         /*count how many visible selected edges there are,
1128         so we can return when there are none left */
1129         unsigned int deselcount=0;
1130         
1131         short ok=0;
1132         float thresh=G.scene->toolsettings->select_thresh;
1133         
1134         for(eve= em->verts.first; eve; eve= eve->next) {
1135                 if (!eve->h) {
1136                         if (eve->f & SELECT) {
1137                                 eve->f1=1;
1138                                 ok=1;
1139                         } else {
1140                                 eve->f1=0;
1141                                 deselcount++;
1142                         }
1143                         /* set all eve->tmp.l to 0 we use them later.*/
1144                         eve->tmp.l=0;
1145                 }
1146                 
1147         }
1148         
1149         if (!ok || !deselcount) /* no data selected OR no more data to select*/
1150                 return 0;
1151         
1152         
1153         if (mode==2) { /* store face users */
1154                 EditFace *efa;
1155                 
1156                 /* count how many faces each edge uses use tmp->l */
1157                 for(efa= em->faces.first; efa; efa= efa->next) {
1158                         efa->v1->tmp.l++;
1159                         efa->v2->tmp.l++;
1160                         efa->v3->tmp.l++;
1161                         if (efa->v4) efa->v4->tmp.l++;
1162                 }
1163         }
1164         
1165         
1166         for(base_eve= em->verts.first; base_eve; base_eve= base_eve->next) {
1167                 if (base_eve->f1) {
1168                                 
1169                         if (mode==1) { /* same normal */
1170                                 float angle;
1171                                 for(eve= em->verts.first; eve; eve= eve->next) {
1172                                         if (!(eve->f & SELECT) && !eve->h) {
1173                                                 angle= VecAngle2(base_eve->no, eve->no);
1174                                                 if (angle/180.0<=thresh) {
1175                                                         eve->f |= SELECT;
1176                                                         selcount++;
1177                                                         deselcount--;
1178                                                         if (!deselcount) /*have we selected all posible faces?, if so return*/
1179                                                                 return selcount;
1180                                                 }
1181                                         }
1182                                 }
1183                         } else if (mode==2) { /* face users */
1184                                 for(eve= em->verts.first; eve; eve= eve->next) {
1185                                         if (
1186                                                 !(eve->f & SELECT) &&
1187                                                 !eve->h &&
1188                                                 base_eve->tmp.l==eve->tmp.l
1189                                         ) {
1190                                                 eve->f |= SELECT;
1191                                                 selcount++;
1192                                                 deselcount--;
1193                                                 if (!deselcount) /*have we selected all posible faces?, if so return*/
1194                                                         return selcount;
1195                                         }
1196                                 }
1197                         } else if (mode==3) { /* vertex groups */
1198                                 MDeformVert *dvert, *base_dvert;
1199                                 short i, j; /* weight index */
1200
1201                                 base_dvert= CustomData_em_get(&em->vdata, base_eve->data,
1202                                         CD_MDEFORMVERT);
1203
1204                                 if (!base_dvert || base_dvert->totweight == 0)
1205                                         return selcount;
1206                                 
1207                                 for(eve= em->verts.first; eve; eve= eve->next) {
1208                                         dvert= CustomData_em_get(&em->vdata, eve->data,
1209                                                 CD_MDEFORMVERT);
1210
1211                                         if (dvert && !(eve->f & SELECT) && !eve->h && dvert->totweight) {
1212                                                 /* do the extra check for selection in the following if, so were not
1213                                                 checking verts that may be alredy selected */
1214                                                 for (i=0; base_dvert->totweight >i && !(eve->f & SELECT); i++) { 
1215                                                         for (j=0; dvert->totweight >j; j++) {
1216                                                                 if (base_dvert->dw[i].def_nr==dvert->dw[j].def_nr) {
1217                                                                         eve->f |= SELECT;
1218                                                                         selcount++;
1219                                                                         deselcount--;
1220                                                                         if (!deselcount) /*have we selected all posible faces?, if so return*/
1221                                                                                 return selcount;
1222                                                                         break;
1223                                                                 }
1224                                                         }
1225                                                 }
1226                                         }
1227                                 }
1228                         }
1229                 }
1230         } /* end basevert loop */
1231         return selcount;
1232 }
1233
1234 /* EditMode menu triggered from space.c by pressing Shift+G
1235 handles face/edge vert context and
1236 facegroup_select/edgegroup_select/vertgroup_select do all the work
1237 */
1238
1239 void select_mesh_group_menu()
1240 {
1241         short ret;
1242         int selcount, first_item=1;
1243         char str[512] = "Select Grouped%t"; /* total max length is 404 at the moment */
1244
1245         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
1246                 first_item=0;
1247                 strcat(str, "|Verts...%x-1|    Similar Normal %x1|    Same Face Users %x2|    Shared Vertex Groups%x3");
1248         }
1249
1250         if(G.scene->selectmode & SCE_SELECT_EDGE) {
1251                 if (!first_item)        strcat(str, "|%l");
1252                 else                            first_item=1;
1253                 
1254                 strcat(str, "|Edges...%x-1|    Similar Length %x10|    Similar Direction %x20|    Same Face Users%x30|    Similar Face Angle%x40|    Similar Crease%x50");
1255         }
1256         
1257         if(G.scene->selectmode & SCE_SELECT_FACE) {
1258                 if (!first_item)        strcat(str, "|%l");
1259                 strcat(str, "|Faces...%x-1|    Same Material %x100|    Same Image %x200|    Similar Area %x300|    Similar Perimeter %x400|    Similar Normal %x500|    Similar Co-Planer %x600");
1260         
1261         }
1262         
1263         ret= pupmenu(str);
1264         if (ret<1) return;
1265         
1266         if (ret<10) {
1267                 selcount= vertgroup_select(ret);
1268                 if (selcount) { /* update if data was selected */
1269                         EM_select_flush(); /* so that selected verts, go onto select faces */
1270                         G.totvertsel += selcount;
1271                         allqueue(REDRAWVIEW3D, 0);
1272                         BIF_undo_push("Select Grouped Verts");
1273                 }
1274                 return;
1275         }
1276         
1277         if (ret<100) {
1278                 selcount= edgegroup_select(ret/10);
1279                 
1280                 if (selcount) { /* update if data was selected */
1281                         /*EM_select_flush();*/ /* dont use because it can end up selecting more edges and is not usefull*/
1282                         G.totedgesel+=selcount;
1283                         allqueue(REDRAWVIEW3D, 0);
1284                         BIF_undo_push("Select Grouped Edges");
1285                 }
1286                 return;
1287         }
1288         
1289         if (ret<1000) {
1290                 selcount= facegroup_select(ret/100);
1291                 if (selcount) { /* update if data was selected */
1292                         G.totfacesel+=selcount;
1293                         allqueue(REDRAWVIEW3D, 0);
1294                         BIF_undo_push("Select Grouped Faces");
1295                 }
1296                 return;
1297         }
1298 }
1299
1300
1301 /* ****************  LOOP SELECTS *************** */
1302
1303 /* selects quads in loop direction of indicated edge */
1304 /* only flush over edges with valence <= 2 */
1305 void faceloop_select(EditEdge *startedge, int select)
1306 {
1307         EditMesh *em = G.editMesh;
1308         EditEdge *eed;
1309         EditFace *efa;
1310         int looking= 1;
1311         
1312         /* in eed->f1 we put the valence (amount of faces in edge) */
1313         /* in eed->f2 we put tagged flag as correct loop */
1314         /* in efa->f1 we put tagged flag as correct to select */
1315
1316         for(eed= em->edges.first; eed; eed= eed->next) {
1317                 eed->f1= 0;
1318                 eed->f2= 0;
1319         }
1320         for(efa= em->faces.first; efa; efa= efa->next) {
1321                 efa->f1= 0;
1322                 if(efa->h==0) {
1323                         efa->e1->f1++;
1324                         efa->e2->f1++;
1325                         efa->e3->f1++;
1326                         if(efa->e4) efa->e4->f1++;
1327                 }
1328         }
1329         
1330         /* tag startedge OK*/
1331         startedge->f2= 1;
1332         
1333         while(looking) {
1334                 looking= 0;
1335                 
1336                 for(efa= em->faces.first; efa; efa= efa->next) {
1337                         if(efa->e4 && efa->f1==0) {     /* not done quad */
1338                                 if(efa->e1->f1<=2 && efa->e2->f1<=2 && efa->e3->f1<=2 && efa->e4->f1<=2) { /* valence ok */
1339
1340                                         /* if edge tagged, select opposing edge and mark face ok */
1341                                         if(efa->e1->f2) {
1342                                                 efa->e3->f2= 1;
1343                                                 efa->f1= 1;
1344                                                 looking= 1;
1345                                         }
1346                                         else if(efa->e2->f2) {
1347                                                 efa->e4->f2= 1;
1348                                                 efa->f1= 1;
1349                                                 looking= 1;
1350                                         }
1351                                         if(efa->e3->f2) {
1352                                                 efa->e1->f2= 1;
1353                                                 efa->f1= 1;
1354                                                 looking= 1;
1355                                         }
1356                                         if(efa->e4->f2) {
1357                                                 efa->e2->f2= 1;
1358                                                 efa->f1= 1;
1359                                                 looking= 1;
1360                                         }
1361                                 }
1362                         }
1363                 }
1364         }
1365         
1366         /* (de)select the faces */
1367         if(select!=2) {
1368                 for(efa= em->faces.first; efa; efa= efa->next) {
1369                         if(efa->f1) EM_select_face(efa, select);
1370                 }
1371         }
1372 }
1373
1374
1375 /* helper for edgeloop_select, checks for eed->f2 tag in faces */
1376 static int edge_not_in_tagged_face(EditEdge *eed)
1377 {
1378         EditMesh *em = G.editMesh;
1379         EditFace *efa;
1380         
1381         for(efa= em->faces.first; efa; efa= efa->next) {
1382                 if(efa->h==0) {
1383                         if(efa->e1==eed || efa->e2==eed || efa->e3==eed || efa->e4==eed) {      /* edge is in face */
1384                                 if(efa->e1->f2 || efa->e2->f2 || efa->e3->f2 || (efa->e4 && efa->e4->f2)) {     /* face is tagged */
1385                                         return 0;
1386                                 }
1387                         }
1388                 }
1389         }
1390         return 1;
1391 }
1392
1393 /* selects or deselects edges that:
1394 - if edges has 2 faces:
1395         - has vertices with valence of 4
1396         - not shares face with previous edge
1397 - if edge has 1 face:
1398         - has vertices with valence 4
1399         - not shares face with previous edge
1400         - but also only 1 face
1401 - if edge no face:
1402         - has vertices with valence 2
1403 */
1404 static void edgeloop_select(EditEdge *starteed, int select)
1405 {
1406         EditMesh *em = G.editMesh;
1407         EditVert *eve;
1408         EditEdge *eed;
1409         EditFace *efa;
1410         int looking= 1;
1411         
1412         /* in f1 we put the valence (amount of edges in a vertex, or faces in edge) */
1413         /* in eed->f2 and efa->f1 we put tagged flag as correct loop */
1414         for(eve= em->verts.first; eve; eve= eve->next) {
1415                 eve->f1= 0;
1416                 eve->f2= 0;
1417         }
1418         for(eed= em->edges.first; eed; eed= eed->next) {
1419                 eed->f1= 0;
1420                 eed->f2= 0;
1421                 if((eed->h & 1)==0) {   /* fgon edges add to valence too */
1422                         eed->v1->f1++; eed->v2->f1++;
1423                 }
1424         }
1425         for(efa= em->faces.first; efa; efa= efa->next) {
1426                 efa->f1= 0;
1427                 if(efa->h==0) {
1428                         efa->e1->f1++;
1429                         efa->e2->f1++;
1430                         efa->e3->f1++;
1431                         if(efa->e4) efa->e4->f1++;
1432                 }
1433         }
1434         
1435         /* looped edges & vertices get tagged f2 */
1436         starteed->f2= 1;
1437         if(starteed->v1->f1<5) starteed->v1->f2= 1;
1438         if(starteed->v2->f1<5) starteed->v2->f2= 1;
1439         /* sorry, first edge isnt even ok */
1440         if(starteed->v1->f2==0 && starteed->v2->f2==0) looking= 0;
1441         
1442         while(looking) {
1443                 looking= 0;
1444                 
1445                 /* find correct valence edges which are not tagged yet, but connect to tagged one */
1446                 for(eed= em->edges.first; eed; eed= eed->next) {
1447                         if(eed->h==0 && eed->f2==0) { /* edge not hidden, not tagged */
1448                                 if( (eed->v1->f1<5 && eed->v1->f2) || (eed->v2->f1<5 && eed->v2->f2)) { /* valence of vertex OK, and is tagged */
1449                                         /* new edge is not allowed to be in face with tagged edge */
1450                                         if(edge_not_in_tagged_face(eed)) {
1451                                                 if(eed->f1==starteed->f1) {     /* same amount of faces */
1452                                                         looking= 1;
1453                                                         eed->f2= 1;
1454                                                         if(eed->v2->f1<5) eed->v2->f2= 1;
1455                                                         if(eed->v1->f1<5) eed->v1->f2= 1;
1456                                                 }
1457                                         }
1458                                 }
1459                         }
1460                 }
1461         }
1462         /* and we do the select */
1463         for(eed= em->edges.first; eed; eed= eed->next) {
1464                 if(eed->f2) EM_select_edge(eed, select);
1465         }
1466 }
1467
1468 /* 
1469    Almostly exactly the same code as faceloop select
1470 */
1471 static void edgering_select(EditEdge *startedge, int select){
1472         EditMesh *em = G.editMesh;
1473         EditEdge *eed;
1474         EditFace *efa;
1475         int looking= 1;
1476         
1477         /* in eed->f1 we put the valence (amount of faces in edge) */
1478         /* in eed->f2 we put tagged flag as correct loop */
1479         /* in efa->f1 we put tagged flag as correct to select */
1480
1481         for(eed= em->edges.first; eed; eed= eed->next) {
1482                 eed->f1= 0;
1483                 eed->f2= 0;
1484         }
1485         for(efa= em->faces.first; efa; efa= efa->next) {
1486                 efa->f1= 0;
1487                 if(efa->h==0) {
1488                         efa->e1->f1++;
1489                         efa->e2->f1++;
1490                         efa->e3->f1++;
1491                         if(efa->e4) efa->e4->f1++;
1492                 }
1493         }
1494         
1495         /* tag startedge OK */
1496         startedge->f2= 1;
1497         
1498         while(looking) {
1499                 looking= 0;
1500                 
1501                 for(efa= em->faces.first; efa; efa= efa->next) {
1502                         if(efa->e4 && efa->f1==0 && !efa->h) {  /* not done quad */
1503                                 if(efa->e1->f1<=2 && efa->e2->f1<=2 && efa->e3->f1<=2 && efa->e4->f1<=2) { /* valence ok */
1504
1505                                         /* if edge tagged, select opposing edge and mark face ok */
1506                                         if(efa->e1->f2) {
1507                                                 efa->e3->f2= 1;
1508                                                 efa->f1= 1;
1509                                                 looking= 1;
1510                                         }
1511                                         else if(efa->e2->f2) {
1512                                                 efa->e4->f2= 1;
1513                                                 efa->f1= 1;
1514                                                 looking= 1;
1515                                         }
1516                                         if(efa->e3->f2) {
1517                                                 efa->e1->f2= 1;
1518                                                 efa->f1= 1;
1519                                                 looking= 1;
1520                                         }
1521                                         if(efa->e4->f2) {
1522                                                 efa->e2->f2= 1;
1523                                                 efa->f1= 1;
1524                                                 looking= 1;
1525                                         }
1526                                 }
1527                         }
1528                 }
1529         }
1530         
1531         /* (de)select the edges */
1532         for(eed= em->edges.first; eed; eed= eed->next) {
1533                 if(eed->f2) EM_select_edge(eed, select);
1534         }
1535 }
1536
1537 void loop_multiselect(int looptype)
1538 {
1539         EditEdge *eed;
1540         EditEdge **edarray;
1541         int edindex, edfirstcount;
1542         
1543         /*edarray = MEM_mallocN(sizeof(*edarray)*G.totedgesel,"edge array");*/
1544         edarray = MEM_mallocN(sizeof(EditEdge*)*G.totedgesel,"edge array");
1545         edindex = 0;
1546         edfirstcount = G.totedgesel;
1547         
1548         for(eed=G.editMesh->edges.first; eed; eed=eed->next){
1549                 if(eed->f&SELECT){
1550                         edarray[edindex] = eed;
1551                         edindex += 1;
1552                 }
1553         }
1554         
1555         if(looptype){
1556                 for(edindex = 0; edindex < edfirstcount; edindex +=1){
1557                         eed = edarray[edindex];
1558                         edgering_select(eed,SELECT);
1559                 }
1560                 countall();
1561                 EM_selectmode_flush();
1562                 BIF_undo_push("Edge Ring Multi-Select");
1563         }
1564         else{
1565                 for(edindex = 0; edindex < edfirstcount; edindex +=1){
1566                         eed = edarray[edindex];
1567                         edgeloop_select(eed,SELECT);
1568                 }
1569                 countall();
1570                 EM_selectmode_flush();
1571                 BIF_undo_push("Edge Loop Multi-Select");
1572         }
1573         MEM_freeN(edarray);
1574         allqueue(REDRAWVIEW3D,0);
1575 }
1576                 
1577 /* ***************** MAIN MOUSE SELECTION ************** */
1578
1579 /* just to have the functions nice together */
1580 static void mouse_mesh_loop(void)
1581 {
1582         EditEdge *eed;
1583         int select= 1;
1584         int dist= 50;
1585         
1586         eed= findnearestedge(&dist);
1587         if(eed) {
1588                 
1589                 if((G.qual & LR_SHIFTKEY)==0) EM_clear_flag_all(SELECT);
1590                 
1591                 if((eed->f & SELECT)==0) select=1;
1592                 else if(G.qual & LR_SHIFTKEY) select=0;
1593
1594                 if(G.scene->selectmode & SCE_SELECT_FACE) {
1595                         faceloop_select(eed, select);
1596                 }
1597                 else if(G.scene->selectmode & SCE_SELECT_EDGE) {
1598             if(G.qual == (LR_CTRLKEY | LR_ALTKEY) || G.qual == (LR_CTRLKEY | LR_ALTKEY |LR_SHIFTKEY))
1599                         edgering_select(eed, select);
1600             else if(G.qual & LR_ALTKEY)
1601                         edgeloop_select(eed, select);
1602                 }
1603         else if(G.scene->selectmode & SCE_SELECT_VERTEX) {
1604             if(G.qual == (LR_CTRLKEY | LR_ALTKEY) || G.qual == (LR_CTRLKEY | LR_ALTKEY |LR_SHIFTKEY))
1605                         edgering_select(eed, select);
1606             else if(G.qual & LR_ALTKEY)
1607                         edgeloop_select(eed, select);
1608                 }
1609
1610                 /* frontbuffer draw of last selected only */
1611                 unified_select_draw(NULL, eed, NULL);
1612                 
1613                 EM_selectmode_flush();
1614                 countall();
1615                 
1616                 allqueue(REDRAWVIEW3D, 0);
1617         }
1618 }
1619
1620
1621 /* here actual select happens */
1622 void mouse_mesh(void)
1623 {
1624         EditVert *eve;
1625         EditEdge *eed;
1626         EditFace *efa;
1627         
1628         if(G.qual & LR_ALTKEY) mouse_mesh_loop();
1629         else if(unified_findnearest(&eve, &eed, &efa)) {
1630                 
1631                 if((G.qual & LR_SHIFTKEY)==0) EM_clear_flag_all(SELECT);
1632                 
1633                 if(efa) {
1634                         
1635                         if( (efa->f & SELECT)==0 ) {
1636                                 EM_store_selection(efa, EDITFACE);
1637                                 EM_select_face_fgon(efa, 1);
1638                         }
1639                         else if(G.qual & LR_SHIFTKEY) {
1640                                 EM_remove_selection(efa, EDITFACE);
1641                                 EM_select_face_fgon(efa, 0);
1642                         }
1643                 }
1644                 else if(eed) {
1645                         if((eed->f & SELECT)==0) {
1646                                 EM_store_selection(eed, EDITEDGE);
1647                                 EM_select_edge(eed, 1);
1648                         }
1649                         else if(G.qual & LR_SHIFTKEY) {
1650                                 EM_remove_selection(eed, EDITEDGE);
1651                                 EM_select_edge(eed, 0);
1652                         }
1653                 }
1654                 else if(eve) {
1655                         if((eve->f & SELECT)==0) {
1656                                 eve->f |= SELECT;
1657                                 EM_store_selection(eve, EDITVERT);
1658                         }
1659                         else if(G.qual & LR_SHIFTKEY){ 
1660                                 EM_remove_selection(eve, EDITVERT);
1661                                 eve->f &= ~SELECT;
1662                         }
1663                 }
1664                 
1665                 /* frontbuffer draw of last selected only */
1666                 unified_select_draw(eve, eed, efa);
1667         
1668                 EM_selectmode_flush();
1669                 countall();
1670
1671                 allqueue(REDRAWVIEW3D, 0);
1672         }
1673
1674         rightmouse_transform();
1675 }
1676
1677
1678 static void selectconnectedAll(void)
1679 {
1680         EditMesh *em = G.editMesh;
1681         EditVert *v1,*v2;
1682         EditEdge *eed;
1683         short done=1, toggle=0;
1684
1685         if(em->edges.first==0) return;
1686         
1687         while(done==1) {
1688                 done= 0;
1689                 
1690                 toggle++;
1691                 if(toggle & 1) eed= em->edges.first;
1692                 else eed= em->edges.last;
1693                 
1694                 while(eed) {
1695                         v1= eed->v1;
1696                         v2= eed->v2;
1697                         if(eed->h==0) {
1698                                 if(v1->f & SELECT) {
1699                                         if( (v2->f & SELECT)==0 ) {
1700                                                 v2->f |= SELECT;
1701                                                 done= 1;
1702                                         }
1703                                 }
1704                                 else if(v2->f & SELECT) {
1705                                         if( (v1->f & SELECT)==0 ) {
1706                                                 v1->f |= SELECT;
1707                                                 done= 1;
1708                                         }
1709                                 }
1710                         }
1711                         if(toggle & 1) eed= eed->next;
1712                         else eed= eed->prev;
1713                 }
1714         }
1715
1716         /* now use vertex select flag to select rest */
1717         EM_select_flush();
1718         
1719         countall();
1720
1721         allqueue(REDRAWVIEW3D, 0);
1722         BIF_undo_push("Select Connected (All)");
1723 }
1724
1725 void selectconnected_mesh(int qual)
1726 {
1727         EditMesh *em = G.editMesh;
1728         EditVert *eve, *v1, *v2;
1729         EditEdge *eed;
1730         EditFace *efa;
1731         short done=1, sel, toggle=0;
1732
1733         if(em->edges.first==0) return;
1734
1735         if(qual & LR_CTRLKEY) {
1736                 selectconnectedAll();
1737                 return;
1738         }
1739
1740         
1741         if( unified_findnearest(&eve, &eed, &efa)==0 ) {
1742                 error("Nothing indicated ");
1743                 return;
1744         }
1745         
1746         sel= 1;
1747         if(qual & LR_SHIFTKEY) sel=0;
1748
1749         /* clear test flags */
1750         for(v1= em->verts.first; v1; v1= v1->next) v1->f1= 0;
1751         
1752         /* start vertex/face/edge */
1753         if(eve) eve->f1= 1;
1754         else if(eed) eed->v1->f1= eed->v2->f1= 1;
1755         else efa->v1->f1= efa->v2->f1= efa->v3->f1= 1;
1756         
1757         /* set flag f1 if affected */
1758         while(done==1) {
1759                 done= 0;
1760                 toggle++;
1761                 
1762                 if(toggle & 1) eed= em->edges.first;
1763                 else eed= em->edges.last;
1764                 
1765                 while(eed) {
1766                         v1= eed->v1;
1767                         v2= eed->v2;
1768                         
1769                         if(eed->h==0) {
1770                                 if(v1->f1 && v2->f1==0) {
1771                                         v2->f1= 1;
1772                                         done= 1;
1773                                 }
1774                                 else if(v1->f1==0 && v2->f1) {
1775                                         v1->f1= 1;
1776                                         done= 1;
1777                                 }
1778                         }
1779                         
1780                         if(toggle & 1) eed= eed->next;
1781                         else eed= eed->prev;
1782                 }
1783         }
1784         
1785         /* now use vertex f1 flag to select/deselect */
1786         for(eed= em->edges.first; eed; eed= eed->next) {
1787                 if(eed->v1->f1 && eed->v2->f1) 
1788                         EM_select_edge(eed, sel);
1789         }
1790         for(efa= em->faces.first; efa; efa= efa->next) {
1791                 if(efa->v1->f1 && efa->v2->f1 && efa->v3->f1 && (efa->v4==NULL || efa->v4->f1)) 
1792                         EM_select_face(efa, sel);
1793         }
1794         /* no flush needed, connected geometry is done */
1795         
1796         countall();
1797         
1798         allqueue(REDRAWVIEW3D, 0);
1799         BIF_undo_push("Select Linked");
1800         
1801 }
1802
1803 /* swap is 0 or 1, if 1 it hides not selected */
1804 void hide_mesh(int swap)
1805 {
1806         EditMesh *em = G.editMesh;
1807         EditVert *eve;
1808         EditEdge *eed;
1809         EditFace *efa;
1810         int a;
1811         
1812         if(G.obedit==0) return;
1813
1814         /* hide happens on least dominant select mode, and flushes up, not down! (helps preventing errors in subsurf) */
1815         /*  - vertex hidden, always means edge is hidden too
1816                 - edge hidden, always means face is hidden too
1817                 - face hidden, only set face hide
1818                 - then only flush back down what's absolute hidden
1819         */
1820         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
1821                 for(eve= em->verts.first; eve; eve= eve->next) {
1822                         if((eve->f & SELECT)!=swap) {
1823                                 eve->f &= ~SELECT;
1824                                 eve->h= 1;
1825                         }
1826                 }
1827         
1828                 for(eed= em->edges.first; eed; eed= eed->next) {
1829                         if(eed->v1->h || eed->v2->h) {
1830                                 eed->h |= 1;
1831                                 eed->f &= ~SELECT;
1832                         }
1833                 }
1834         
1835                 for(efa= em->faces.first; efa; efa= efa->next) {
1836                         if(efa->e1->h & 1 || efa->e2->h & 1 || efa->e3->h & 1 || (efa->e4 && efa->e4->h & 1)) {
1837                                 efa->h= 1;
1838                                 efa->f &= ~SELECT;
1839                         }
1840                 }
1841         }
1842         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
1843
1844                 for(eed= em->edges.first; eed; eed= eed->next) {
1845                         if((eed->f & SELECT)!=swap) {
1846                                 eed->h |= 1;
1847                                 EM_select_edge(eed, 0);
1848                         }
1849                 }
1850
1851                 for(efa= em->faces.first; efa; efa= efa->next) {
1852                         if(efa->e1->h & 1 || efa->e2->h & 1 || efa->e3->h & 1 || (efa->e4 && efa->e4->h & 1)) {
1853                                 efa->h= 1;
1854                                 efa->f &= ~SELECT;
1855                         }
1856                 }
1857         }
1858         else {
1859
1860                 for(efa= em->faces.first; efa; efa= efa->next) {
1861                         if((efa->f & SELECT)!=swap) {
1862                                 efa->h= 1;
1863                                 EM_select_face(efa, 0);
1864                         }
1865                 }
1866         }
1867         
1868         /* flush down, only whats 100% hidden */
1869         for(eve= em->verts.first; eve; eve= eve->next) eve->f1= 0;
1870         for(eed= em->edges.first; eed; eed= eed->next) eed->f1= 0;
1871         
1872         if(G.scene->selectmode & SCE_SELECT_FACE) {
1873                 for(efa= em->faces.first; efa; efa= efa->next) {
1874                         if(efa->h) a= 1; else a= 2;
1875                         efa->e1->f1 |= a;
1876                         efa->e2->f1 |= a;
1877                         efa->e3->f1 |= a;
1878                         if(efa->e4) efa->e4->f1 |= a;
1879                 }
1880         }
1881         
1882         if(G.scene->selectmode >= SCE_SELECT_EDGE) {
1883                 for(eed= em->edges.first; eed; eed= eed->next) {
1884                         if(eed->f1==1) eed->h |= 1;
1885                         if(eed->h & 1) a= 1; else a= 2;
1886                         eed->v1->f1 |= a;
1887                         eed->v2->f1 |= a;
1888                 }
1889         }
1890
1891         if(G.scene->selectmode >= SCE_SELECT_VERTEX) {
1892                 for(eve= em->verts.first; eve; eve= eve->next) {
1893                         if(eve->f1==1) eve->h= 1;
1894                 }
1895         }
1896         
1897         G.totedgesel= G.totfacesel= G.totvertsel= 0;
1898         allqueue(REDRAWVIEW3D, 0);
1899         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);     
1900         BIF_undo_push("Hide");
1901 }
1902
1903
1904 void reveal_mesh(void)
1905 {
1906         EditMesh *em = G.editMesh;
1907         EditVert *eve;
1908         EditEdge *eed;
1909         EditFace *efa;
1910         
1911         if(G.obedit==0) return;
1912
1913         for(eve= em->verts.first; eve; eve= eve->next) {
1914                 if(eve->h) {
1915                         eve->h= 0;
1916                         eve->f |= SELECT;
1917                 }
1918         }
1919         for(eed= em->edges.first; eed; eed= eed->next) {
1920                 if(eed->h & 1) {
1921                         eed->h &= ~1;
1922                         if(G.scene->selectmode & SCE_SELECT_VERTEX); 
1923                         else EM_select_edge(eed, 1);
1924                 }
1925         }
1926         for(efa= em->faces.first; efa; efa= efa->next) {
1927                 if(efa->h) {
1928                         efa->h= 0;
1929                         if(G.scene->selectmode & (SCE_SELECT_EDGE|SCE_SELECT_VERTEX)); 
1930                         else EM_select_face(efa, 1);
1931                 }
1932         }
1933
1934         EM_fgon_flags();        /* redo flags and indices for fgons */
1935         EM_selectmode_flush();
1936         countall();
1937
1938         allqueue(REDRAWVIEW3D, 0);
1939         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);     
1940         BIF_undo_push("Reveal");
1941 }
1942
1943 void select_faces_by_numverts(int numverts)
1944 {
1945         EditMesh *em = G.editMesh;
1946         EditFace *efa;
1947
1948         /* Selects trias/qiads or isolated verts, and edges that do not have 2 neighboring
1949          * faces
1950          */
1951
1952         /* for loose vertices/edges, we first select all, loop below will deselect */
1953         if(numverts==5)
1954                 EM_set_flag_all(SELECT);
1955         else if(G.scene->selectmode!=SCE_SELECT_FACE) {
1956                 error("Only works in face selection mode");
1957                 return;
1958         }
1959         
1960         for(efa= em->faces.first; efa; efa= efa->next) {
1961                 if (efa->e4) {
1962                         EM_select_face(efa, (numverts==4) );
1963                 }
1964                 else {
1965                         EM_select_face(efa, (numverts==3) );
1966                 }
1967         }
1968
1969         countall();
1970         addqueue(curarea->win,  REDRAW, 0);
1971
1972         if (numverts==3)
1973                 BIF_undo_push("Select Triangles");
1974         else if (numverts==4)
1975                 BIF_undo_push("Select Quads");
1976         else
1977                 BIF_undo_push("Select non-Triangles/Quads");
1978 }
1979
1980 void select_sharp_edges(void)
1981 {
1982         /* Find edges that have exactly two neighboring faces,
1983          * check the angle between those faces, and if angle is
1984          * small enough, select the edge
1985          */
1986         EditMesh *em = G.editMesh;
1987         EditEdge *eed;
1988         EditFace *efa;
1989         EditFace **efa1;
1990         EditFace **efa2;
1991         long edgecount = 0, i;
1992         static short sharpness = 135;
1993         float fsharpness;
1994
1995         if(G.scene->selectmode==SCE_SELECT_FACE) {
1996                 error("Doesn't work in face selection mode");
1997                 return;
1998         }
1999
2000         if(button(&sharpness,0, 180,"Max Angle:")==0) return;
2001         /* if faces are at angle 'sharpness', then the face normals
2002          * are at angle 180.0 - 'sharpness' (convert to radians too)
2003          */
2004         fsharpness = ((180.0 - sharpness) * M_PI) / 180.0;
2005
2006         i=0;
2007         /* count edges, use tmp.l  */
2008         eed= em->edges.first;
2009         while(eed) {
2010                 edgecount++;
2011                 eed->tmp.l = i;
2012                 eed= eed->next;
2013                 ++i;
2014         }
2015
2016         /* for each edge, we want a pointer to two adjacent faces */
2017         efa1 = MEM_callocN(edgecount*sizeof(EditFace *), 
2018                                            "pairs of edit face pointers");
2019         efa2 = MEM_callocN(edgecount*sizeof(EditFace *), 
2020                                            "pairs of edit face pointers");
2021
2022 #define face_table_edge(eed) { \
2023                 i = eed->tmp.l; \
2024                 if (i != -1) { \
2025                         if (efa1[i]) { \
2026                                 if (efa2[i]) { \
2027                                         /* invalidate, edge has more than two neighbors */ \
2028                                         eed->tmp.l = -1; \
2029                                 } \
2030                                 else { \
2031                                         efa2[i] = efa; \
2032                                 } \
2033                         } \
2034                         else { \
2035                                 efa1[i] = efa; \
2036                         } \
2037                 } \
2038         }
2039
2040         /* find the adjacent faces of each edge, we want only two */
2041         efa= em->faces.first;
2042         while(efa) {
2043                 face_table_edge(efa->e1);
2044                 face_table_edge(efa->e2);
2045                 face_table_edge(efa->e3);
2046                 if (efa->e4) {
2047                         face_table_edge(efa->e4);
2048                 }
2049                 efa= efa->next;
2050         }
2051
2052 #undef face_table_edge
2053
2054         eed = em->edges.first;
2055         while(eed) {
2056                 i = eed->tmp.l;
2057                 if (i != -1) { 
2058                         /* edge has two or less neighboring faces */
2059                         if ( (efa1[i]) && (efa2[i]) ) { 
2060                                 /* edge has exactly two neighboring faces, check angle */
2061                                 float angle;
2062                                 angle = saacos(efa1[i]->n[0]*efa2[i]->n[0] +
2063                                                            efa1[i]->n[1]*efa2[i]->n[1] +
2064                                                            efa1[i]->n[2]*efa2[i]->n[2]);
2065                                 if (fabs(angle) >= fsharpness)
2066                                         EM_select_edge(eed, 1);
2067                         }
2068                 }
2069
2070                 eed= eed->next;
2071         }
2072
2073         MEM_freeN(efa1);
2074         MEM_freeN(efa2);
2075
2076         countall();
2077         addqueue(curarea->win,  REDRAW, 0);
2078         BIF_undo_push("Select Sharp Edges");
2079 }
2080
2081 void select_linked_flat_faces(void)
2082 {
2083         /* Find faces that are linked to selected faces that are 
2084          * relatively flat (angle between faces is higher than
2085          * specified angle)
2086          */
2087         EditMesh *em = G.editMesh;
2088         EditEdge *eed;
2089         EditFace *efa;
2090         EditFace **efa1;
2091         EditFace **efa2;
2092         long edgecount = 0, i, faceselcount=0, faceselcountold=0;
2093         static short sharpness = 135;
2094         float fsharpness;
2095
2096         if(G.scene->selectmode!=SCE_SELECT_FACE) {
2097                 error("Only works in face selection mode");
2098                 return;
2099         }
2100
2101         if(button(&sharpness,0, 180,"Min Angle:")==0) return;
2102         /* if faces are at angle 'sharpness', then the face normals
2103          * are at angle 180.0 - 'sharpness' (convert to radians too)
2104          */
2105         fsharpness = ((180.0 - sharpness) * M_PI) / 180.0;
2106
2107         i=0;
2108         /* count edges, use tmp.l */
2109         eed= em->edges.first;
2110         while(eed) {
2111                 edgecount++;
2112                 eed->tmp.l = i;
2113                 eed= eed->next;
2114                 ++i;
2115         }
2116
2117         /* for each edge, we want a pointer to two adjacent faces */
2118         efa1 = MEM_callocN(edgecount*sizeof(EditFace *), 
2119                                            "pairs of edit face pointers");
2120         efa2 = MEM_callocN(edgecount*sizeof(EditFace *), 
2121                                            "pairs of edit face pointers");
2122
2123 #define face_table_edge(eed) { \
2124                 i = eed->tmp.l; \
2125                 if (i != -1) { \
2126                         if (efa1[i]) { \
2127                                 if (efa2[i]) { \
2128                                         /* invalidate, edge has more than two neighbors */ \
2129                                         eed->tmp.l = -1; \
2130                                 } \
2131                                 else { \
2132                                         efa2[i] = efa; \
2133                                 } \
2134                         } \
2135                         else { \
2136                                 efa1[i] = efa; \
2137                         } \
2138                 } \
2139         }
2140
2141         /* find the adjacent faces of each edge, we want only two */
2142         efa= em->faces.first;
2143         while(efa) {
2144                 face_table_edge(efa->e1);
2145                 face_table_edge(efa->e2);
2146                 face_table_edge(efa->e3);
2147                 if (efa->e4) {
2148                         face_table_edge(efa->e4);
2149                 }
2150
2151                 /* while were at it, count the selected faces */
2152                 if (efa->f & SELECT) ++faceselcount;
2153
2154                 efa= efa->next;
2155         }
2156
2157 #undef face_table_edge
2158
2159         eed= em->edges.first;
2160         while(eed) {
2161                 i = eed->tmp.l;
2162                 if (i != -1) { 
2163                         /* edge has two or less neighboring faces */
2164                         if ( (efa1[i]) && (efa2[i]) ) { 
2165                                 /* edge has exactly two neighboring faces, check angle */
2166                                 float angle;
2167                                 angle = saacos(efa1[i]->n[0]*efa2[i]->n[0] +
2168                                                            efa1[i]->n[1]*efa2[i]->n[1] +
2169                                                            efa1[i]->n[2]*efa2[i]->n[2]);
2170                                 /* invalidate: edge too sharp */
2171                                 if (fabs(angle) >= fsharpness)
2172                                         eed->tmp.l = -1;
2173                         }
2174                         else {
2175                                 /* invalidate: less than two neighbors */
2176                                 eed->tmp.l = -1;
2177                         }
2178                 }
2179
2180                 eed= eed->next;
2181         }
2182
2183 #define select_flat_neighbor(eed) { \
2184                                 i = eed->tmp.l; \
2185                                 if (i!=-1) { \
2186                                         if (! (efa1[i]->f & SELECT) ) { \
2187                                                 EM_select_face(efa1[i], 1); \
2188                                                 ++faceselcount; \
2189                                         } \
2190                                         if (! (efa2[i]->f & SELECT) ) { \
2191                                                 EM_select_face(efa2[i], 1); \
2192                                                 ++faceselcount; \
2193                                         } \
2194                                 } \
2195         }
2196
2197         while (faceselcount != faceselcountold) {
2198                 faceselcountold = faceselcount;
2199
2200                 efa= em->faces.first;
2201                 while(efa) {
2202                         if (efa->f & SELECT) {
2203                                 select_flat_neighbor(efa->e1);
2204                                 select_flat_neighbor(efa->e2);
2205                                 select_flat_neighbor(efa->e3);
2206                                 if (efa->e4) {
2207                                         select_flat_neighbor(efa->e4);
2208                                 }
2209                         }
2210                         efa= efa->next;
2211                 }
2212         }
2213
2214 #undef select_flat_neighbor
2215
2216         MEM_freeN(efa1);
2217         MEM_freeN(efa2);
2218
2219         countall();
2220         addqueue(curarea->win,  REDRAW, 0);
2221         BIF_undo_push("Select Linked Flat Faces");
2222 }
2223
2224 void select_non_manifold(void)
2225 {
2226         EditMesh *em = G.editMesh;
2227         EditVert *eve;
2228         EditEdge *eed;
2229         EditFace *efa;
2230
2231         /* Selects isolated verts, and edges that do not have 2 neighboring
2232          * faces
2233          */
2234         
2235         if(G.scene->selectmode==SCE_SELECT_FACE) {
2236                 error("Doesn't work in face selection mode");
2237                 return;
2238         }
2239
2240         eve= em->verts.first;
2241         while(eve) {
2242                 /* this will count how many edges are connected
2243                  * to this vert */
2244                 eve->f1= 0;
2245                 eve= eve->next;
2246         }
2247
2248         eed= em->edges.first;
2249         while(eed) {
2250                 /* this will count how many faces are connected to
2251                  * this edge */
2252                 eed->f1= 0;
2253                 /* increase edge count for verts */
2254                 ++eed->v1->f1;
2255                 ++eed->v2->f1;
2256                 eed= eed->next;
2257         }
2258
2259         efa= em->faces.first;
2260         while(efa) {
2261                 /* increase face count for edges */
2262                 ++efa->e1->f1;
2263                 ++efa->e2->f1;
2264                 ++efa->e3->f1;
2265                 if (efa->e4)
2266                         ++efa->e4->f1;                  
2267                 efa= efa->next;
2268         }
2269
2270         /* select verts that are attached to an edge that does not
2271          * have 2 neighboring faces */
2272         eed= em->edges.first;
2273         while(eed) {
2274                 if (eed->h==0 && eed->f1 != 2) {
2275                         EM_select_edge(eed, 1);
2276                 }
2277                 eed= eed->next;
2278         }
2279
2280         /* select isolated verts */
2281         eve= em->verts.first;
2282         while(eve) {
2283                 if (eve->f1 == 0) {
2284                         if (!eve->h) eve->f |= SELECT;
2285                 }
2286                 eve= eve->next;
2287         }
2288
2289         countall();
2290         addqueue(curarea->win,  REDRAW, 0);
2291         BIF_undo_push("Select Non Manifold");
2292 }
2293
2294 void selectswap_mesh(void) /* UI level */
2295 {
2296         EditMesh *em = G.editMesh;
2297         EditVert *eve;
2298         EditEdge *eed;
2299         EditFace *efa;
2300         
2301         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
2302
2303                 for(eve= em->verts.first; eve; eve= eve->next) {
2304                         if(eve->h==0) {
2305                                 if(eve->f & SELECT) eve->f &= ~SELECT;
2306                                 else eve->f|= SELECT;
2307                         }
2308                 }
2309         }
2310         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
2311                 for(eed= em->edges.first; eed; eed= eed->next) {
2312                         if(eed->h==0) {
2313                                 EM_select_edge(eed, !(eed->f & SELECT));
2314                         }
2315                 }
2316         }
2317         else {
2318                 for(efa= em->faces.first; efa; efa= efa->next) {
2319                         if(efa->h==0) {
2320                                 EM_select_face(efa, !(efa->f & SELECT));
2321                         }
2322                 }
2323         }
2324
2325         EM_selectmode_flush();
2326         
2327         countall();
2328         allqueue(REDRAWVIEW3D, 0);
2329
2330         BIF_undo_push("Select Swap");
2331         
2332 }
2333
2334 void deselectall_mesh(void)      /* this toggles!!!, UI level */
2335 {
2336         
2337         if(G.obedit->lay & G.vd->lay) {
2338
2339                 if( EM_nvertices_selected() ) {
2340                         EM_clear_flag_all(SELECT);
2341                         BIF_undo_push("Deselect All");
2342                 }
2343                 else  {
2344                         EM_set_flag_all(SELECT);
2345                         BIF_undo_push("Select All");
2346                 }
2347                 
2348                 countall();
2349                 allqueue(REDRAWVIEW3D, 0);
2350         }
2351 }
2352
2353 void select_more(void)
2354 {
2355         EditMesh *em = G.editMesh;
2356         EditVert *eve;
2357         EditEdge *eed;
2358         EditFace *efa;
2359         
2360         for(eve= em->verts.first; eve; eve= eve->next) {
2361                 if(eve->f & SELECT) eve->f1= 1;
2362                 else eve->f1 = 0;
2363         }
2364         
2365         /* set f1 flags in vertices to select 'more' */
2366         for(eed= em->edges.first; eed; eed= eed->next) {
2367                 if(eed->h==0) {
2368                         if (eed->v1->f & SELECT)
2369                                 eed->v2->f1 = 1;
2370                         if (eed->v2->f & SELECT)
2371                                 eed->v1->f1 = 1;
2372                 }
2373         }
2374
2375         /* new selected edges, but not in facemode */
2376         if(G.scene->selectmode <= SCE_SELECT_EDGE) {
2377                 
2378                 for(eed= em->edges.first; eed; eed= eed->next) {
2379                         if(eed->h==0) {
2380                                 if(eed->v1->f1 && eed->v2->f1) EM_select_edge(eed, 1);
2381                         }
2382                 }
2383         }
2384         /* new selected faces */
2385         for(efa= em->faces.first; efa; efa= efa->next) {
2386                 if(efa->h==0) {
2387                         if(efa->v1->f1 && efa->v2->f1 && efa->v3->f1 && (efa->v4==NULL || efa->v4->f1)) 
2388                                 EM_select_face(efa, 1);
2389                 }
2390         }
2391
2392         countall();
2393         addqueue(curarea->win,  REDRAW, 0);
2394         BIF_undo_push("Select More");
2395 }
2396
2397 void select_less(void)
2398 {
2399         EditMesh *em = G.editMesh;
2400         EditEdge *eed;
2401         EditFace *efa;
2402
2403         if(G.scene->selectmode <= SCE_SELECT_EDGE) {
2404                 /* eed->f1 == 1:  edge with a selected and deselected vert */ 
2405
2406                 for(eed= em->edges.first; eed; eed= eed->next) {
2407                         eed->f1= 0;
2408                         if(eed->h==0) {
2409                                 
2410                                 if ( !(eed->v1->f & SELECT) && (eed->v2->f & SELECT) ) 
2411                                         eed->f1= 1;
2412                                 if ( (eed->v1->f & SELECT) && !(eed->v2->f & SELECT) ) 
2413                                         eed->f1= 1;
2414                         }
2415                 }
2416                 
2417                 /* deselect edges with flag set */
2418                 for(eed= em->edges.first; eed; eed= eed->next) {
2419                         if (eed->h==0 && eed->f1 == 1) {
2420                                 EM_select_edge(eed, 0);
2421                         }
2422                 }
2423                 EM_deselect_flush();
2424                 
2425         }
2426         else {
2427                 /* deselect faces with 1 or more deselect edges */
2428                 /* eed->f1 == mixed selection edge */
2429                 for(eed= em->edges.first; eed; eed= eed->next) eed->f1= 0;
2430
2431                 for(efa= em->faces.first; efa; efa= efa->next) {
2432                         if(efa->h==0) {
2433                                 if(efa->f & SELECT) {
2434                                         efa->e1->f1 |= 1;
2435                                         efa->e2->f1 |= 1;
2436                                         efa->e3->f1 |= 1;
2437                                         if(efa->e4) efa->e4->f1 |= 1;
2438                                 }
2439                                 else {
2440                                         efa->e1->f1 |= 2;
2441                                         efa->e2->f1 |= 2;
2442                                         efa->e3->f1 |= 2;
2443                                         if(efa->e4) efa->e4->f1 |= 2;
2444                                 }
2445                         }
2446                 }
2447                 for(efa= em->faces.first; efa; efa= efa->next) {
2448                         if(efa->h==0) {
2449                                 if(efa->e1->f1==3 || efa->e2->f1==3 || efa->e3->f1==3 || (efa->e4 && efa->e4->f1==3)) { 
2450                                         EM_select_face(efa, 0);
2451                                 }
2452                         }
2453                 }
2454                 EM_selectmode_flush();
2455                 
2456         }
2457         
2458         countall();
2459         BIF_undo_push("Select Less");
2460         allqueue(REDRAWVIEW3D, 0);
2461 }
2462
2463
2464 void selectrandom_mesh(void) /* randomly selects a user-set % of vertices/edges/faces */
2465 {
2466         EditMesh *em = G.editMesh;
2467         EditVert *eve;
2468         EditEdge *eed;
2469         EditFace *efa;
2470         static short randfac = 50;
2471
2472         if(G.obedit==NULL || (G.obedit->lay & G.vd->lay)==0) return;
2473
2474         /* Get the percentage of vertices to randomly select as 'randfac' */
2475         if(button(&randfac,0, 100,"Percentage:")==0) return;
2476
2477         BLI_srand( BLI_rand() ); /* random seed */
2478         
2479         if(G.scene->selectmode & SCE_SELECT_VERTEX) {
2480                 for(eve= em->verts.first; eve; eve= eve->next) {
2481                         if(eve->h==0) {
2482                                 if ( (BLI_frand() * 100) < randfac) 
2483                                         eve->f |= SELECT;
2484                         }
2485                 }
2486                 EM_selectmode_flush();
2487                 countall();
2488                 BIF_undo_push("Select Random: Vertices");
2489         }
2490         else if(G.scene->selectmode & SCE_SELECT_EDGE) {
2491                 for(eed= em->edges.first; eed; eed= eed->next) {
2492                         if(eed->h==0) {
2493                                 if ( (BLI_frand() * 100) < randfac) 
2494                                         EM_select_edge(eed, 1);
2495                         }
2496                 }
2497                 EM_selectmode_flush();
2498                 countall();
2499                 BIF_undo_push("Select Random:Edges");
2500         }
2501         else {
2502                 for(efa= em->faces.first; efa; efa= efa->next) {
2503                         if(efa->h==0) {
2504                                 if ( (BLI_frand() * 100) < randfac) 
2505                                         EM_select_face(efa, 1);
2506                         }
2507                 }
2508                 
2509                 EM_selectmode_flush();
2510                 countall();
2511                 BIF_undo_push("Select Random:Faces");
2512         }
2513         allqueue(REDRAWVIEW3D, 0);
2514 }
2515
2516 void editmesh_select_by_material(int index) 
2517 {
2518         EditMesh *em = G.editMesh;
2519         EditFace *efa;
2520         
2521         for (efa=em->faces.first; efa; efa= efa->next) {
2522                 if (efa->mat_nr==index) {
2523                         EM_select_face(efa, 1);
2524                 }
2525         }
2526
2527         EM_selectmode_flush();
2528 }
2529
2530 void editmesh_deselect_by_material(int index) 
2531 {
2532         EditMesh *em = G.editMesh;
2533         EditFace *efa;
2534         
2535         for (efa=em->faces.first; efa; efa= efa->next) {
2536                 if (efa->mat_nr==index) {
2537                         EM_select_face(efa, 0);
2538                 }
2539         }
2540
2541         EM_selectmode_flush();
2542 }
2543
2544 void EM_selectmode_menu(void)
2545 {
2546         int val;
2547         
2548         if(G.scene->selectmode & SCE_SELECT_VERTEX) pupmenu_set_active(1);
2549         else if(G.scene->selectmode & SCE_SELECT_EDGE) pupmenu_set_active(2);
2550         else pupmenu_set_active(3);
2551         
2552         val= pupmenu("Select Mode%t|Vertices|Edges|Faces");
2553         
2554         
2555         if(val>0) {
2556                 if(val==1){ 
2557                         G.scene->selectmode= SCE_SELECT_VERTEX;
2558                         EM_selectmode_set();
2559                         countall(); 
2560                         BIF_undo_push("Selectmode Set: Vertex");
2561                         }
2562                 else if(val==2){
2563                         if((G.qual==LR_CTRLKEY)) EM_convertsel(G.scene->selectmode, SCE_SELECT_EDGE);
2564                         G.scene->selectmode= SCE_SELECT_EDGE;
2565                         EM_selectmode_set();
2566                         countall();
2567                         BIF_undo_push("Selectmode Set: Edge");
2568                 }
2569                 
2570                 else{
2571                         if((G.qual==LR_CTRLKEY)) EM_convertsel(G.scene->selectmode, SCE_SELECT_FACE);
2572                         G.scene->selectmode= SCE_SELECT_FACE;
2573                         EM_selectmode_set();
2574                         countall();
2575                         BIF_undo_push("Selectmode Set: Vertex");
2576                 }
2577                 
2578                 allqueue(REDRAWVIEW3D, 1);
2579         }
2580 }
2581
2582 /* ************************* SEAMS AND EDGES **************** */
2583
2584 void editmesh_mark_seam(int clear)
2585 {
2586         EditMesh *em= G.editMesh;
2587         EditEdge *eed;
2588         
2589         if(multires_level1_test()) return;
2590
2591         /* auto-enable seams drawing */
2592         if(clear==0) {
2593                 if(!(G.f & G_DRAWSEAMS)) {
2594                         G.f |= G_DRAWSEAMS;
2595                         allqueue(REDRAWBUTSEDIT, 0);
2596                 }
2597         }
2598
2599         if(clear) {
2600                 eed= em->edges.first;
2601                 while(eed) {
2602                         if((eed->h==0) && (eed->f & SELECT)) {
2603                                 eed->seam = 0;
2604                         }
2605                         eed= eed->next;
2606                 }
2607                 BIF_undo_push("Mark Seam");
2608         }
2609         else {
2610                 eed= em->edges.first;
2611                 while(eed) {
2612                         if((eed->h==0) && (eed->f & SELECT)) {
2613                                 eed->seam = 1;
2614                         }
2615                         eed= eed->next;
2616                 }
2617                 BIF_undo_push("Clear Seam");
2618         }
2619
2620         allqueue(REDRAWVIEW3D, 0);
2621 }
2622
2623 void editmesh_mark_sharp(int set)
2624 {
2625         EditMesh *em= G.editMesh;
2626         EditEdge *eed;
2627
2628 #if 0
2629         /* auto-enable sharp edge drawing */
2630         if(set) {
2631                 if(!(G.f & G_DRAWSEAMS)) {
2632                         G.f |= G_DRAWSEAMS;
2633                         allqueue(REDRAWBUTSEDIT, 0);
2634                 }
2635         }
2636 #endif
2637
2638         if(set) {
2639                 eed= em->edges.first;
2640                 while(eed) {
2641                         if(!eed->h && (eed->f & SELECT)) eed->sharp = 1;
2642                         eed = eed->next;
2643                 }
2644         } else {
2645                 eed= em->edges.first;
2646                 while(eed) {
2647                         if(!eed->h && (eed->f & SELECT)) eed->sharp = 0;
2648                         eed = eed->next;
2649                 }
2650         }
2651
2652         allqueue(REDRAWVIEW3D, 0);
2653 }
2654
2655 void BME_Menu() {
2656         short ret;
2657         ret= pupmenu("BME modeller%t|Select Edges of Vert%x1");
2658         
2659         switch(ret)
2660         {
2661                 case 1:
2662                 //BME_edges_of_vert();
2663                 break;
2664         }
2665 }
2666
2667 void Edge_Menu() {
2668         short ret;
2669
2670         ret= pupmenu("Edge Specials%t|Mark Seam %x1|Clear Seam %x2|Rotate Edge CW%x3|Rotate Edge CCW%x4|Loopcut%x6|Edge Slide%x5|Edge Loop Select%x7|Edge Ring Select%x8|Loop to Region%x9|Region to Loop%x10|Mark Sharp%x11|Clear Sharp%x12");
2671
2672         switch(ret)
2673         {
2674         case 1:
2675                 editmesh_mark_seam(0);
2676                 break;
2677         case 2:
2678                 editmesh_mark_seam(1);
2679                 break;
2680         case 3:
2681                 edge_rotate_selected(2);
2682                 break;
2683         case 4:
2684                 edge_rotate_selected(1);
2685                 break;
2686         case 5:
2687                 EdgeSlide(0,0.0);
2688                 BIF_undo_push("EdgeSlide");
2689                 break;
2690         case 6:
2691                 CutEdgeloop(1);
2692                 BIF_undo_push("Loopcut New");
2693                 break;
2694         case 7:
2695                 loop_multiselect(0);
2696                 break;
2697         case 8:
2698                 loop_multiselect(1);
2699                 break;
2700         case 9:
2701                 loop_to_region();
2702                 break;
2703         case 10:
2704                 region_to_loop();
2705                 break;
2706         case 11:
2707                 editmesh_mark_sharp(1);
2708                 BIF_undo_push("Mark Sharp");
2709                 DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2710                 break;
2711         case 12: 
2712                 editmesh_mark_sharp(0);
2713                 BIF_undo_push("Clear Sharp");
2714                 DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2715                 break;
2716         }
2717 }
2718
2719
2720 /* **************** NORMALS ************** */
2721
2722 void righthandfaces(int select) /* makes faces righthand turning */
2723 {
2724         EditMesh *em = G.editMesh;
2725         EditEdge *eed, *ed1, *ed2, *ed3, *ed4;
2726         EditFace *efa, *startvl;
2727         float maxx, nor[3], cent[3];
2728         int totsel, found, foundone, direct, turn, tria_nr;
2729
2730    /* based at a select-connected to witness loose objects */
2731
2732         /* count per edge the amount of faces */
2733
2734         /* find the ultimate left, front, upper face (not manhattan dist!!) */
2735         /* also evaluate both triangle cases in quad, since these can be non-flat */
2736
2737         /* put normal to the outside, and set the first direction flags in edges */
2738
2739         /* then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces */
2740         /* this is in fact the 'select connected' */
2741         
2742         /* in case (selected) faces were not done: start over with 'find the ultimate ...' */
2743
2744         waitcursor(1);
2745         
2746         eed= em->edges.first;
2747         while(eed) {
2748                 eed->f2= 0;             /* edge direction */
2749                 eed->f1= 0;             /* counter */
2750                 eed= eed->next;
2751         }
2752
2753         /* count faces and edges */
2754         totsel= 0;
2755         efa= em->faces.first;
2756         while(efa) {
2757                 if(select==0 || (efa->f & SELECT) ) {
2758                         efa->f1= 1;
2759                         totsel++;
2760                         efa->e1->f1++;
2761                         efa->e2->f1++;
2762                         efa->e3->f1++;
2763                         if(efa->v4) efa->e4->f1++;
2764                 }
2765                 else efa->f1= 0;
2766
2767                 efa= efa->next;
2768         }
2769
2770         while(totsel>0) {
2771                 /* from the outside to the inside */
2772
2773                 efa= em->faces.first;
2774                 startvl= NULL;
2775                 maxx= -1.0e10;
2776                 tria_nr= 0;
2777
2778                 while(efa) {
2779                         if(efa->f1) {
2780                                 CalcCent3f(cent, efa->v1->co, efa->v2->co, efa->v3->co);
2781                                 cent[0]= cent[0]*cent[0] + cent[1]*cent[1] + cent[2]*cent[2];
2782                                 
2783                                 if(cent[0]>maxx) {
2784                                         maxx= cent[0];
2785                                         startvl= efa;
2786                                         tria_nr= 0;
2787                                 }
2788                                 if(efa->v4) {
2789                                         CalcCent3f(cent, efa->v1->co, efa->v3->co, efa->v4->co);
2790                                         cent[0]= cent[0]*cent[0] + cent[1]*cent[1] + cent[2]*cent[2];
2791                                         
2792                                         if(cent[0]>maxx) {
2793                                                 maxx= cent[0];
2794                                                 startvl= efa;
2795                                                 tria_nr= 1;
2796                                         }
2797                                 }
2798                         }
2799                         efa= efa->next;
2800                 }
2801
2802                 if (startvl==NULL)
2803                         startvl= em->faces.first;
2804                 
2805                 /* set first face correct: calc normal */
2806                 
2807                 if(tria_nr==1) {
2808                         CalcNormFloat(startvl->v1->co, startvl->v3->co, startvl->v4->co, nor);
2809                         CalcCent3f(cent, startvl->v1->co, startvl->v3->co, startvl->v4->co);
2810                 } else {
2811                         CalcNormFloat(startvl->v1->co, startvl->v2->co, startvl->v3->co, nor);
2812                         CalcCent3f(cent, startvl->v1->co, startvl->v2->co, startvl->v3->co);
2813                 }
2814                 /* first normal is oriented this way or the other */
2815                 if(select) {
2816                         if(select==2) {
2817                                 if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] > 0.0) flipface(startvl);
2818                         }
2819                         else {
2820                                 if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] < 0.0) flipface(startvl);
2821                         }
2822                 }
2823                 else if(cent[0]*nor[0]+cent[1]*nor[1]+cent[2]*nor[2] < 0.0) flipface(startvl);
2824
2825
2826                 eed= startvl->e1;
2827                 if(eed->v1==startvl->v1) eed->f2= 1; 
2828                 else eed->f2= 2;
2829                 
2830                 eed= startvl->e2;
2831                 if(eed->v1==startvl->v2) eed->f2= 1; 
2832                 else eed->f2= 2;
2833                 
2834                 eed= startvl->e3;
2835                 if(eed->v1==startvl->v3) eed->f2= 1; 
2836                 else eed->f2= 2;
2837                 
2838                 eed= startvl->e4;
2839                 if(eed) {
2840                         if(eed->v1==startvl->v4) eed->f2= 1; 
2841                         else eed->f2= 2;
2842                 }
2843                 
2844                 startvl->f1= 0;
2845                 totsel--;
2846
2847                 /* test normals */
2848                 found= 1;
2849                 direct= 1;
2850                 while(found) {
2851                         found= 0;
2852                         if(direct) efa= em->faces.first;
2853                         else efa= em->faces.last;
2854                         while(efa) {
2855                                 if(efa->f1) {
2856                                         turn= 0;
2857                                         foundone= 0;
2858
2859                                         ed1= efa->e1;
2860                                         ed2= efa->e2;
2861                                         ed3= efa->e3;
2862                                         ed4= efa->e4;
2863
2864                                         if(ed1->f2) {
2865                                                 if(ed1->v1==efa->v1 && ed1->f2==1) turn= 1;
2866                                                 if(ed1->v2==efa->v1 && ed1->f2==2) turn= 1;
2867                                                 foundone= 1;
2868                                         }
2869                                         else if(ed2->f2) {
2870                                                 if(ed2->v1==efa->v2 && ed2->f2==1) turn= 1;
2871                                                 if(ed2->v2==efa->v2 && ed2->f2==2) turn= 1;
2872                                                 foundone= 1;
2873                                         }
2874                                         else if(ed3->f2) {
2875                                                 if(ed3->v1==efa->v3 && ed3->f2==1) turn= 1;
2876                                                 if(ed3->v2==efa->v3 && ed3->f2==2) turn= 1;
2877                                                 foundone= 1;
2878                                         }
2879                                         else if(ed4 && ed4->f2) {
2880                                                 if(ed4->v1==efa->v4 && ed4->f2==1) turn= 1;
2881                                                 if(ed4->v2==efa->v4 && ed4->f2==2) turn= 1;
2882                                                 foundone= 1;
2883                                         }
2884
2885                                         if(foundone) {
2886                                                 found= 1;
2887                                                 totsel--;
2888                                                 efa->f1= 0;
2889
2890                                                 if(turn) {
2891                                                         if(ed1->v1==efa->v1) ed1->f2= 2; 
2892                                                         else ed1->f2= 1;
2893                                                         if(ed2->v1==efa->v2) ed2->f2= 2; 
2894                                                         else ed2->f2= 1;
2895                                                         if(ed3->v1==efa->v3) ed3->f2= 2; 
2896                                                         else ed3->f2= 1;
2897                                                         if(ed4) {
2898                                                                 if(ed4->v1==efa->v4) ed4->f2= 2; 
2899                                                                 else ed4->f2= 1;
2900                                                         }
2901
2902                                                         flipface(efa);
2903
2904                                                 }
2905                                                 else {
2906                                                         if(ed1->v1== efa->v1) ed1->f2= 1; 
2907                                                         else ed1->f2= 2;
2908                                                         if(ed2->v1==efa->v2) ed2->f2= 1; 
2909                                                         else ed2->f2= 2;
2910                                                         if(ed3->v1==efa->v3) ed3->f2= 1; 
2911                                                         else ed3->f2= 2;
2912                                                         if(ed4) {
2913                                                                 if(ed4->v1==efa->v4) ed4->f2= 1; 
2914                                                                 else ed4->f2= 2;
2915                                                         }
2916                                                 }
2917                                         }
2918                                 }
2919                                 if(direct) efa= efa->next;
2920                                 else efa= efa->prev;
2921                         }
2922                         direct= 1-direct;
2923                 }
2924         }
2925
2926         recalc_editnormals();
2927         
2928         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
2929
2930 #ifdef WITH_VERSE
2931         if(G.editMesh->vnode)
2932                 sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
2933 #endif
2934         
2935         waitcursor(0);
2936 }
2937
2938
2939 /* ********** ALIGN WITH VIEW **************** */
2940
2941
2942 static void editmesh_calc_selvert_center(float cent_r[3])
2943 {
2944         EditMesh *em = G.editMesh;
2945         EditVert *eve;
2946         int nsel= 0;
2947
2948         cent_r[0]= cent_r[1]= cent_r[0]= 0.0;
2949
2950         for (eve= em->verts.first; eve; eve= eve->next) {
2951                 if (eve->f & SELECT) {
2952                         cent_r[0]+= eve->co[0];
2953                         cent_r[1]+= eve->co[1];
2954                         cent_r[2]+= eve->co[2];
2955                         nsel++;
2956                 }
2957         }
2958
2959         if (nsel) {
2960                 cent_r[0]/= nsel;
2961                 cent_r[1]/= nsel;
2962                 cent_r[2]/= nsel;
2963         }
2964 }
2965
2966 static int tface_is_selected(MTFace *tf)
2967 {
2968         return (!(tf->flag & TF_HIDE) && (tf->flag & TF_SELECT));
2969 }
2970
2971         /* XXX, code for both these functions should be abstract,
2972          * then unified, then written for other things (like objects,
2973          * which would use same as vertices method), then added
2974          * to interface! Hoera! - zr
2975          */
2976 void faceselect_align_view_to_selected(View3D *v3d, Mesh *me, int axis)
2977 {
2978         float norm[3];
2979         int i, totselected = 0;
2980
2981         norm[0]= norm[1]= norm[2]= 0.0;
2982         for (i=0; i<me->totface; i++) {
2983                 MFace *mf= ((MFace*) me->mface) + i;
2984                 MTFace *tf= ((MTFace*) me->mtface) + i;
2985
2986                 if (tface_is_selected(tf)) {
2987                         float *v1, *v2, *v3, fno[3];
2988
2989                         v1= me->mvert[mf->v1].co;
2990                         v2= me->mvert[mf->v2].co;
2991                         v3= me->mvert[mf->v3].co;
2992                         if (mf->v4) {
2993                                 float *v4= me->mvert[mf->v4].co;
2994                                 CalcNormFloat4(v1, v2, v3, v4, fno);
2995                         } else {
2996                                 CalcNormFloat(v1, v2, v3, fno);
2997                         }
2998
2999                         norm[0]+= fno[0];
3000                         norm[1]+= fno[1];
3001                         norm[2]+= fno[2];
3002
3003                         totselected++;
3004                 }
3005         }
3006
3007         if (totselected == 0)
3008                 error("No faces selected.");
3009         else
3010                 view3d_align_axis_to_vector(v3d, axis, norm);
3011 }
3012
3013 void editmesh_align_view_to_selected(View3D *v3d, int axis)
3014 {
3015         EditMesh *em = G.editMesh;
3016         int nselverts= EM_nvertices_selected();
3017         float norm[3]={0.0, 0.0, 0.0}; /* used for storing the mesh normal */
3018         
3019         if (nselverts==0) {
3020                 error("No faces or vertices selected.");
3021         } else if (EM_nfaces_selected()) {
3022                 EditFace *efa;
3023                 for (efa= em->faces.first; efa; efa= efa->next) {
3024                         if (faceselectedAND(efa, SELECT)) {
3025                                 float fno[3];
3026                                 if (efa->v4) CalcNormFloat4(efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co, fno);
3027                                 else CalcNormFloat(efa->v1->co, efa->v2->co, efa->v3->co, fno);
3028                                                 /* XXX, fixme, should be flipped intp a 
3029                                                  * consistent direction. -zr
3030                                                  */
3031                                 norm[0]+= fno[0];
3032                                 norm[1]+= fno[1];
3033                                 norm[2]+= fno[2];
3034                         }
3035                 }
3036
3037                 Mat4Mul3Vecfl(G.obedit->obmat, norm);
3038                 view3d_align_axis_to_vector(v3d, axis, norm);
3039         } else if (nselverts>2) {
3040                 float cent[3];
3041                 EditVert *eve, *leve= NULL;
3042
3043                 editmesh_calc_selvert_center(cent);
3044                 for (eve= em->verts.first; eve; eve= eve->next) {
3045                         if (eve->f & SELECT) {
3046                                 if (leve) {
3047                                         float tno[3];
3048                                         CalcNormFloat(cent, leve->co, eve->co, tno);
3049                                         
3050                                                 /* XXX, fixme, should be flipped intp a 
3051                                                  * consistent direction. -zr
3052                                                  */
3053                                         norm[0]+= tno[0];
3054                                         norm[1]+= tno[1];
3055                                         norm[2]+= tno[2];
3056                                 }
3057                                 leve= eve;
3058                         }
3059                 }
3060
3061                 Mat4Mul3Vecfl(G.obedit->obmat, norm);
3062                 view3d_align_axis_to_vector(v3d, axis, norm);
3063         } else if (nselverts==2) { /* Align view to edge (or 2 verts) */ 
3064                 EditVert *eve, *leve= NULL;
3065
3066                 for (eve= em->verts.first; eve; eve= eve->next) {
3067                         if (eve->f & SELECT) {
3068                                 if (leve) {
3069                                         norm[0]= leve->co[0] - eve->co[0];
3070                                         norm[1]= leve->co[1] - eve->co[1];
3071                                         norm[2]= leve->co[2] - eve->co[2];
3072                                         break; /* we know there are only 2 verts so no need to keep looking */
3073                                 }
3074                                 leve= eve;
3075                         }
3076                 }