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