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