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