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