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