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