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