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