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