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