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