svn merge ^/trunk/blender -r42197:42221
[blender.git] / source / blender / editors / mesh / bmesh_select.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
17  *
18  * The Original Code is Copyright (C) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /*
29
30 BMEditMesh_mods.c, UI level access, no geometry changes 
31
32 */
33
34 #include <stdlib.h>
35 #include <string.h>
36 #include <math.h>
37
38 #include "MEM_guardedalloc.h"
39
40 #include "DNA_mesh_types.h"
41 #include "DNA_material_types.h"
42 #include "DNA_meshdata_types.h"
43 #include "DNA_modifier_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_texture_types.h"
46 #include "DNA_scene_types.h"
47 #include "DNA_screen_types.h"
48 #include "DNA_space_types.h"
49 #include "DNA_view3d_types.h"
50
51 #include "BLI_utildefines.h"
52 #include "BLI_blenlib.h"
53 #include "BLI_math.h"
54 #include "BLI_rand.h"
55 #include "BLI_array.h"
56 #include "BLI_smallhash.h"
57 #include "BLI_heap.h"
58
59 #include "BKE_context.h"
60 #include "BKE_displist.h"
61 #include "BKE_depsgraph.h"
62 #include "BKE_DerivedMesh.h"
63 #include "BKE_customdata.h"
64 #include "BKE_global.h"
65 #include "BKE_mesh.h"
66 #include "BKE_material.h"
67 #include "BKE_texture.h"
68 #include "BKE_report.h"
69 #include "BKE_tessmesh.h"
70 #include "BKE_paint.h"
71
72 #include "IMB_imbuf_types.h"
73 #include "IMB_imbuf.h"
74
75 #include "RE_render_ext.h"  /* externtex */
76
77 #include "WM_api.h"
78 #include "WM_types.h"
79
80 #include "RNA_access.h"
81 #include "RNA_define.h"
82
83 #include "ED_mesh.h"
84 #include "ED_screen.h"
85 #include "ED_view3d.h"
86 #include "bmesh.h"
87
88 #include "BIF_gl.h"
89 #include "BIF_glutil.h"
90
91 #include "UI_resources.h"
92
93 #include "mesh_intern.h"
94
95 #include "BLO_sys_types.h" // for intptr_t support
96
97 /* ****************************** MIRROR **************** */
98
99 static void EDBM_select_mirrored(Object *obedit, BMEditMesh *em)
100 {
101         if(em->selectmode & SCE_SELECT_VERTEX) {
102                 BMVert *eve, *v1;
103                 BMIter iter;
104                 int i;
105
106                 i= 0;
107                 BM_ITER(eve, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
108                         if (BM_TestHFlag(eve, BM_SELECT) && !BM_TestHFlag(eve, BM_HIDDEN)) {
109                                 v1= editbmesh_get_x_mirror_vert(obedit, em, eve, eve->co, i);
110                                 if(v1) {
111                                         BM_Select(em->bm, eve, 0);
112                                         BM_Select(em->bm, v1, 1);
113                                 }
114                         }
115                         i++;
116                 }
117         }
118 }
119
120 void EDBM_automerge(Scene *scene, Object *obedit, int update)
121 {
122         BMEditMesh *em;
123         
124         if ((scene->toolsettings->automerge) &&
125             (obedit && obedit->type==OB_MESH))
126         {
127                 em = ((Mesh*)obedit->data)->edit_btmesh;
128                 if (!em)
129                         return;
130
131                 BMO_CallOpf(em->bm, "automerge verts=%hv dist=%f", BM_SELECT, scene->toolsettings->doublimit);
132                 if (update) {
133                         DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
134                 }
135         }
136 }
137
138 /* ****************************** SELECTION ROUTINES **************** */
139
140 unsigned int bm_solidoffs=0, bm_wireoffs=0, bm_vertoffs=0;      /* set in drawobject.c ... for colorindices */
141
142 /* facilities for border select and circle select */
143 static char *selbuf= NULL;
144
145 /* opengl doesn't support concave... */
146 static void draw_triangulated(int mcords[][2], short tot)
147 {
148         ListBase lb={NULL, NULL};
149         DispList *dl;
150         float *fp;
151         int a;
152         
153         /* make displist */
154         dl= MEM_callocN(sizeof(DispList), "poly disp");
155         dl->type= DL_POLY;
156         dl->parts= 1;
157         dl->nr= tot;
158         dl->verts= fp=  MEM_callocN(tot*3*sizeof(float), "poly verts");
159         BLI_addtail(&lb, dl);
160         
161         for(a=0; a<tot; a++, fp+=3) {
162                 fp[0]= (float)mcords[a][0];
163                 fp[1]= (float)mcords[a][1];
164         }
165         
166         /* do the fill */
167         filldisplist(&lb, &lb, 0);
168
169         /* do the draw */
170         dl= lb.first;   /* filldisplist adds in head of list */
171         if(dl->type==DL_INDEX3) {
172                 int *index;
173                 
174                 a= dl->parts;
175                 fp= dl->verts;
176                 index= dl->index;
177                 glBegin(GL_TRIANGLES);
178                 while(a--) {
179                         glVertex3fv(fp+3*index[0]);
180                         glVertex3fv(fp+3*index[1]);
181                         glVertex3fv(fp+3*index[2]);
182                         index+= 3;
183                 }
184                 glEnd();
185         }
186         
187         freedisplist(&lb);
188 }
189
190
191 /* reads rect, and builds selection array for quick lookup */
192 /* returns if all is OK */
193 int EDBM_init_backbuf_border(ViewContext *vc, short xmin, short ymin, short xmax, short ymax)
194 {
195         struct ImBuf *buf;
196         unsigned int *dr;
197         int a;
198         
199         if(vc->obedit==NULL || vc->v3d->drawtype<OB_SOLID || (vc->v3d->flag & V3D_ZBUF_SELECT)==0) return 0;
200         
201         buf= view3d_read_backbuf(vc, xmin, ymin, xmax, ymax);
202         if(buf==NULL) return 0;
203         if(bm_vertoffs==0) return 0;
204
205         dr = buf->rect;
206         
207         /* build selection lookup */
208         selbuf= MEM_callocN(bm_vertoffs+1, "selbuf");
209         
210         a= (xmax-xmin+1)*(ymax-ymin+1);
211         while(a--) {
212                 if(*dr>0 && *dr<=bm_vertoffs) 
213                         selbuf[*dr]= 1;
214                 dr++;
215         }
216         IMB_freeImBuf(buf);
217         return 1;
218 }
219
220 int EDBM_check_backbuf(unsigned int index)
221 {
222         if(selbuf==NULL) return 1;
223         if(index>0 && index<=bm_vertoffs)
224                 return selbuf[index];
225         return 0;
226 }
227
228 void EDBM_free_backbuf(void)
229 {
230         if(selbuf) MEM_freeN(selbuf);
231         selbuf= NULL;
232 }
233
234 /* mcords is a polygon mask
235    - grab backbuffer,
236    - draw with black in backbuffer, 
237    - grab again and compare
238    returns 'OK' 
239 */
240 int EDBM_mask_init_backbuf_border(ViewContext *vc, int mcords[][2], short tot, short xmin, short ymin, short xmax, short ymax)
241 {
242         unsigned int *dr, *drm;
243         struct ImBuf *buf, *bufmask;
244         int a;
245         
246         /* method in use for face selecting too */
247         if(vc->obedit==NULL) {
248                 if(paint_facesel_test(vc->obact));
249                 else if(paint_vertsel_test(vc->obact));
250                 else return 0;
251         }
252         else if(vc->v3d->drawtype<OB_SOLID || (vc->v3d->flag & V3D_ZBUF_SELECT)==0) return 0;
253
254         buf= view3d_read_backbuf(vc, xmin, ymin, xmax, ymax);
255         if(buf==NULL) return 0;
256         if(bm_vertoffs==0) return 0;
257
258         dr = buf->rect;
259
260         /* draw the mask */
261         glDisable(GL_DEPTH_TEST);
262         
263         glColor3ub(0, 0, 0);
264         
265         /* yah, opengl doesn't do concave... tsk! */
266         ED_region_pixelspace(vc->ar);
267         draw_triangulated(mcords, tot); 
268         
269         glBegin(GL_LINE_LOOP);  /* for zero sized masks, lines */
270         for(a=0; a<tot; a++) glVertex2iv(mcords[a]);
271         glEnd();
272         
273         glFinish();     /* to be sure readpixels sees mask */
274         
275         /* grab mask */
276         bufmask= view3d_read_backbuf(vc, xmin, ymin, xmax, ymax);
277         drm = bufmask->rect;
278         if(bufmask==NULL) return 0; /* only when mem alloc fails, go crash somewhere else! */
279         
280         /* build selection lookup */
281         selbuf= MEM_callocN(bm_vertoffs+1, "selbuf");
282         
283         a= (xmax-xmin+1)*(ymax-ymin+1);
284         while(a--) {
285                 if(*dr>0 && *dr<=bm_vertoffs && *drm==0) selbuf[*dr]= 1;
286                 dr++; drm++;
287         }
288         IMB_freeImBuf(buf);
289         IMB_freeImBuf(bufmask);
290         return 1;
291         
292 }
293
294 /* circle shaped sample area */
295 int EDBM_init_backbuf_circle(ViewContext *vc, short xs, short ys, short rads)
296 {
297         struct ImBuf *buf;
298         unsigned int *dr;
299         short xmin, ymin, xmax, ymax, xc, yc;
300         int radsq;
301         
302         /* method in use for face selecting too */
303         if(vc->obedit==NULL) {
304                 if(paint_facesel_test(vc->obact));
305                 else if(paint_vertsel_test(vc->obact));
306                 else return 0;
307         }
308         else if(vc->v3d->drawtype<OB_SOLID || (vc->v3d->flag & V3D_ZBUF_SELECT)==0) return 0;
309         
310         xmin= xs-rads; xmax= xs+rads;
311         ymin= ys-rads; ymax= ys+rads;
312         buf= view3d_read_backbuf(vc, xmin, ymin, xmax, ymax);
313         if(bm_vertoffs==0) return 0;
314         if(buf==NULL) return 0;
315
316         dr = buf->rect;
317         
318         /* build selection lookup */
319         selbuf= MEM_callocN(bm_vertoffs+1, "selbuf");
320         radsq= rads*rads;
321         for(yc= -rads; yc<=rads; yc++) {
322                 for(xc= -rads; xc<=rads; xc++, dr++) {
323                         if(xc*xc + yc*yc < radsq) {
324                                 if(*dr>0 && *dr<=bm_vertoffs) selbuf[*dr]= 1;
325                         }
326                 }
327         }
328
329         IMB_freeImBuf(buf);
330         return 1;
331         
332 }
333
334 static void findnearestvert__doClosest(void *userData, BMVert *eve, int x, int y, int index)
335 {
336         struct { short mval[2], pass, select, strict; int dist, lastIndex, closestIndex; BMVert *closest; } *data = userData;
337
338         if (data->pass==0) {
339                 if (index<=data->lastIndex)
340                         return;
341         } else {
342                 if (index>data->lastIndex)
343                         return;
344         }
345
346         if (data->dist>3) {
347                 int temp = abs(data->mval[0] - x) + abs(data->mval[1]- y);
348                 if (BM_TestHFlag(eve, BM_SELECT) == data->select) {
349                         if (data->strict == 1)
350                                 return;
351                         else
352                                 temp += 5;
353                 }
354
355                 if (temp<data->dist) {
356                         data->dist = temp;
357                         data->closest = eve;
358                         data->closestIndex = index;
359                 }
360         }
361 }
362
363
364
365
366 static unsigned int findnearestvert__backbufIndextest(void *handle, unsigned int index)
367 {
368         BMEditMesh *em= (BMEditMesh *)handle;
369         BMVert *eve = BM_Vert_AtIndex(em->bm, index-1);
370
371         if(eve && BM_TestHFlag(eve, BM_SELECT)) return 0;
372         return 1; 
373 }
374 /**
375  * findnearestvert
376  * 
377  * dist (in/out): minimal distance to the nearest and at the end, actual distance
378  * sel: selection bias
379  *              if SELECT, selected vertice are given a 5 pixel bias to make them farter than unselect verts
380  *              if 0, unselected vertice are given the bias
381  * strict: if 1, the vertice corresponding to the sel parameter are ignored and not just biased 
382  */
383 BMVert *EDBM_findnearestvert(ViewContext *vc, int *dist, short sel, short strict)
384 {
385         if(vc->v3d->drawtype>OB_WIRE && (vc->v3d->flag & V3D_ZBUF_SELECT)){
386                 int distance;
387                 unsigned int index;
388                 BMVert *eve;
389                 
390                 if(strict) index = view3d_sample_backbuf_rect(vc, vc->mval, 50, bm_wireoffs, 0xFFFFFF, &distance, strict, vc->em, findnearestvert__backbufIndextest); 
391                 else index = view3d_sample_backbuf_rect(vc, vc->mval, 50, bm_wireoffs, 0xFFFFFF, &distance, 0, NULL, NULL); 
392                 
393                 eve = BM_Vert_AtIndex(vc->em->bm, index-1);
394                 
395                 if(eve && distance < *dist) {
396                         *dist = distance;
397                         return eve;
398                 } else {
399                         return NULL;
400                 }
401                         
402         }
403         else {
404                 struct { short mval[2], pass, select, strict; int dist, lastIndex, closestIndex; BMVert *closest; } data;
405                 static int lastSelectedIndex=0;
406                 static BMVert *lastSelected=NULL;
407                 
408                 if (lastSelected && BM_Vert_AtIndex(vc->em->bm, lastSelectedIndex) != lastSelected) {
409                         lastSelectedIndex = 0;
410                         lastSelected = NULL;
411                 }
412
413                 data.lastIndex = lastSelectedIndex;
414                 data.mval[0] = vc->mval[0];
415                 data.mval[1] = vc->mval[1];
416                 data.select = sel;
417                 data.dist = *dist;
418                 data.strict = strict;
419                 data.closest = NULL;
420                 data.closestIndex = 0;
421
422                 data.pass = 0;
423
424                 ED_view3d_init_mats_rv3d(vc->obedit, vc->rv3d);
425
426                 mesh_foreachScreenVert(vc, findnearestvert__doClosest, &data, V3D_CLIP_TEST_RV3D_CLIPPING);
427
428                 if (data.dist>3) {
429                         data.pass = 1;
430                         mesh_foreachScreenVert(vc, findnearestvert__doClosest, &data, V3D_CLIP_TEST_RV3D_CLIPPING);
431                 }
432
433                 *dist = data.dist;
434                 lastSelected = data.closest;
435                 lastSelectedIndex = data.closestIndex;
436
437                 return data.closest;
438         }
439 }
440
441 /* returns labda for closest distance v1 to line-piece v2-v3 */
442 float labda_PdistVL2Dfl(const float v1[3], const float v2[3], const float v3[3])
443 {
444         float rc[2], len;
445         
446         rc[0]= v3[0]-v2[0];
447         rc[1]= v3[1]-v2[1];
448         len= rc[0]*rc[0]+ rc[1]*rc[1];
449         if(len==0.0f)
450                 return 0.0f;
451         
452         return ( rc[0]*(v1[0]-v2[0]) + rc[1]*(v1[1]-v2[1]) )/len;
453 }
454
455 /* note; uses v3d, so needs active 3d window */
456 static void findnearestedge__doClosest(void *userData, BMEdge *eed, int x0, int y0, int x1, int y1, int UNUSED(index))
457 {
458         struct { ViewContext vc; float mval[2]; int dist; BMEdge *closest; } *data = userData;
459         float v1[2], v2[2];
460         int distance;
461                 
462         v1[0] = x0;
463         v1[1] = y0;
464         v2[0] = x1;
465         v2[1] = y1;
466                 
467         distance= dist_to_line_segment_v2(data->mval, v1, v2);
468                 
469         if(BM_TestHFlag(eed, BM_SELECT)) distance+=5;
470         if(distance < data->dist) {
471                 if(data->vc.rv3d->rflag & RV3D_CLIPPING) {
472                         float labda= labda_PdistVL2Dfl(data->mval, v1, v2);
473                         float vec[3];
474
475                         vec[0]= eed->v1->co[0] + labda*(eed->v2->co[0] - eed->v1->co[0]);
476                         vec[1]= eed->v1->co[1] + labda*(eed->v2->co[1] - eed->v1->co[1]);
477                         vec[2]= eed->v1->co[2] + labda*(eed->v2->co[2] - eed->v1->co[2]);
478                         mul_m4_v3(data->vc.obedit->obmat, vec);
479
480                         if(ED_view3d_test_clipping(data->vc.rv3d, vec, 1)==0) {
481                                 data->dist = distance;
482                                 data->closest = eed;
483                         }
484                 }
485                 else {
486                         data->dist = distance;
487                         data->closest = eed;
488                 }
489         }
490 }
491 BMEdge *EDBM_findnearestedge(ViewContext *vc, int *dist)
492 {
493
494         if(vc->v3d->drawtype>OB_WIRE && (vc->v3d->flag & V3D_ZBUF_SELECT)) {
495                 int distance;
496                 unsigned int index;
497                 BMEdge *eed;
498                 
499                 view3d_validate_backbuf(vc);
500                 
501                 index = view3d_sample_backbuf_rect(vc, vc->mval, 50, bm_solidoffs, bm_wireoffs, &distance,0, NULL, NULL);
502                 eed = BM_Edge_AtIndex(vc->em->bm, index-1);
503                 
504                 if (eed && distance<*dist) {
505                         *dist = distance;
506                         return eed;
507                 } else {
508                         return NULL;
509                 }
510         }
511         else {
512                 struct { ViewContext vc; float mval[2]; int dist; BMEdge *closest; } data;
513
514                 data.vc= *vc;
515                 data.mval[0] = vc->mval[0];
516                 data.mval[1] = vc->mval[1];
517                 data.dist = *dist;
518                 data.closest = NULL;
519                 ED_view3d_init_mats_rv3d(vc->obedit, vc->rv3d);
520
521                 mesh_foreachScreenEdge(vc, findnearestedge__doClosest, &data, 2);
522
523                 *dist = data.dist;
524                 return data.closest;
525         }
526 }
527
528 static void findnearestface__getDistance(void *userData, BMFace *efa, int x, int y, int UNUSED(index))
529 {
530         struct { short mval[2]; int dist; BMFace *toFace; } *data = userData;
531
532         if (efa==data->toFace) {
533                 int temp = abs(data->mval[0]-x) + abs(data->mval[1]-y);
534
535                 if (temp<data->dist)
536                         data->dist = temp;
537         }
538 }
539 static void findnearestface__doClosest(void *userData, BMFace *efa, int x, int y, int index)
540 {
541         struct { short mval[2], pass; int dist, lastIndex, closestIndex; BMFace *closest; } *data = userData;
542
543         if (data->pass==0) {
544                 if (index<=data->lastIndex)
545                         return;
546         } else {
547                 if (index>data->lastIndex)
548                         return;
549         }
550
551         if (data->dist>3) {
552                 int temp = abs(data->mval[0]-x) + abs(data->mval[1]-y);
553
554                 if (temp<data->dist) {
555                         data->dist = temp;
556                         data->closest = efa;
557                         data->closestIndex = index;
558                 }
559         }
560 }
561
562 BMFace *EDBM_findnearestface(ViewContext *vc, int *dist)
563 {
564
565         if(vc->v3d->drawtype>OB_WIRE && (vc->v3d->flag & V3D_ZBUF_SELECT)) {
566                 unsigned int index;
567                 BMFace *efa;
568
569                 view3d_validate_backbuf(vc);
570
571                 index = view3d_sample_backbuf(vc, vc->mval[0], vc->mval[1]);
572                 efa = BM_Face_AtIndex(vc->em->bm, index-1);
573                 
574                 if (efa) {
575                         struct { short mval[2]; int dist; BMFace *toFace; } data;
576
577                         data.mval[0] = vc->mval[0];
578                         data.mval[1] = vc->mval[1];
579                         data.dist = 0x7FFF;             /* largest short */
580                         data.toFace = efa;
581
582                         mesh_foreachScreenFace(vc, findnearestface__getDistance, &data);
583
584                         if(vc->em->selectmode == SCE_SELECT_FACE || data.dist<*dist) {  /* only faces, no dist check */
585                                 *dist= data.dist;
586                                 return efa;
587                         }
588                 }
589                 
590                 return NULL;
591         }
592         else {
593                 struct { short mval[2], pass; int dist, lastIndex, closestIndex; BMFace *closest; } data;
594                 static int lastSelectedIndex=0;
595                 static BMFace *lastSelected=NULL;
596
597                 if (lastSelected && BM_Face_AtIndex(vc->em->bm, lastSelectedIndex) != lastSelected) {
598                         lastSelectedIndex = 0;
599                         lastSelected = NULL;
600                 }
601
602                 data.lastIndex = lastSelectedIndex;
603                 data.mval[0] = vc->mval[0];
604                 data.mval[1] = vc->mval[1];
605                 data.dist = *dist;
606                 data.closest = NULL;
607                 data.closestIndex = 0;
608                 ED_view3d_init_mats_rv3d(vc->obedit, vc->rv3d);
609
610                 data.pass = 0;
611                 mesh_foreachScreenFace(vc, findnearestface__doClosest, &data);
612
613                 if (data.dist>3) {
614                         data.pass = 1;
615                         ED_view3d_init_mats_rv3d(vc->obedit, vc->rv3d);
616                         mesh_foreachScreenFace(vc, findnearestface__doClosest, &data);
617                 }
618
619                 *dist = data.dist;
620                 lastSelected = data.closest;
621                 lastSelectedIndex = data.closestIndex;
622
623                 return data.closest;
624         }
625 }
626
627 /* best distance based on screen coords. 
628    use em->selectmode to define how to use 
629    selected vertices and edges get disadvantage
630    return 1 if found one
631 */
632 static int unified_findnearest(ViewContext *vc, BMVert **eve, BMEdge **eed, BMFace **efa) 
633 {
634         BMEditMesh *em= vc->em;
635         int dist= 75;
636         
637         *eve= NULL;
638         *eed= NULL;
639         *efa= NULL;
640         
641         /* no afterqueue (yet), so we check it now, otherwise the em_xxxofs indices are bad */
642         view3d_validate_backbuf(vc);
643         
644         if(em->selectmode & SCE_SELECT_VERTEX)
645                 *eve= EDBM_findnearestvert(vc, &dist, BM_SELECT, 0);
646         if(em->selectmode & SCE_SELECT_FACE)
647                 *efa= EDBM_findnearestface(vc, &dist);
648
649         dist-= 20;      /* since edges select lines, we give dots advantage of 20 pix */
650         if(em->selectmode & SCE_SELECT_EDGE)
651                 *eed= EDBM_findnearestedge(vc, &dist);
652
653         /* return only one of 3 pointers, for frontbuffer redraws */
654         if(*eed) {
655                 *efa= NULL; *eve= NULL;
656         }
657         else if(*efa) {
658                 *eve= NULL;
659         }
660         
661         return (*eve || *eed || *efa);
662 }
663
664 /* ****************  SIMILAR "group" SELECTS. FACE, EDGE AND VERTEX ************** */
665
666 static EnumPropertyItem prop_similar_types[] = {
667         {SIMVERT_NORMAL, "NORMAL", 0, "Normal", ""},
668         {SIMVERT_FACE, "FACE", 0, "Amount of Adjacent Faces", ""},
669         {SIMVERT_VGROUP, "VGROUP", 0, "Vertex Groups", ""},
670
671         {SIMEDGE_LENGTH, "LENGTH", 0, "Length", ""},
672         {SIMEDGE_DIR, "DIR", 0, "Direction", ""},
673         {SIMEDGE_FACE, "FACE", 0, "Amount of Faces Around an Edge", ""},
674         {SIMEDGE_FACE_ANGLE, "FACE_ANGLE", 0, "Face Angles", ""},
675         {SIMEDGE_CREASE, "CREASE", 0, "Crease", ""},
676         {SIMEDGE_SEAM, "SEAM", 0, "Seam", ""},
677         {SIMEDGE_SHARP, "SHARP", 0, "Sharpness", ""},
678
679         {SIMFACE_MATERIAL, "MATERIAL", 0, "Material", ""},
680         {SIMFACE_IMAGE, "IMAGE", 0, "Image", ""},
681         {SIMFACE_AREA, "AREA", 0, "Area", ""},
682         {SIMFACE_PERIMETER, "PERIMETER", 0, "Perimeter", ""},
683         {SIMFACE_NORMAL, "NORMAL", 0, "Normal", ""},
684         {SIMFACE_COPLANAR, "COPLANAR", 0, "Co-planar", ""},
685
686         {0, NULL, 0, NULL, NULL}
687 };
688
689 /* selects new faces/edges/verts based on the existing selection */
690
691 static int similar_face_select_exec(bContext *C, wmOperator *op)
692 {
693         Object *ob = CTX_data_edit_object(C);
694         BMEditMesh *em = ((Mesh*)ob->data)->edit_btmesh;
695         BMOperator bmop;
696
697         /* get the type from RNA */
698         int type = RNA_enum_get(op->ptr, "type");
699
700         float thresh = CTX_data_tool_settings(C)->select_thresh;
701
702         /* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */
703         EDBM_InitOpf(em, &bmop, op, "similarfaces faces=%hf type=%d thresh=%f", BM_SELECT, type, thresh);
704
705         /* execute the operator */
706         BMO_Exec_Op(em->bm, &bmop);
707
708         /* clear the existing selection */
709         EDBM_clear_flag_all(em, BM_SELECT);
710
711         /* select the output */
712         BMO_HeaderFlag_Buffer(em->bm, &bmop, "faceout", BM_SELECT, BM_ALL);
713
714         /* finish the operator */
715         if( !EDBM_FinishOp(em, &bmop, op, 1) )
716                 return OPERATOR_CANCELLED;
717
718         /* dependencies graph and notification stuff */
719         DAG_id_tag_update(ob->data, OB_RECALC_DATA);
720         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, ob->data);
721
722         /* we succeeded */
723         return OPERATOR_FINISHED;
724 }       
725
726 /* ***************************************************** */
727
728 /* EDGE GROUP */
729
730 /* wrap the above function but do selection flushing edge to face */
731 static int similar_edge_select_exec(bContext *C, wmOperator *op)
732 {
733         Object *ob = CTX_data_edit_object(C);
734         BMEditMesh *em = ((Mesh*)ob->data)->edit_btmesh;
735         BMOperator bmop;
736
737         /* get the type from RNA */
738         int type = RNA_enum_get(op->ptr, "type");
739
740         float thresh = CTX_data_tool_settings(C)->select_thresh;
741
742         /* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */
743         EDBM_InitOpf(em, &bmop, op, "similaredges edges=%he type=%d thresh=%f", BM_SELECT, type, thresh);
744
745         /* execute the operator */
746         BMO_Exec_Op(em->bm, &bmop);
747
748         /* clear the existing selection */
749         EDBM_clear_flag_all(em, BM_SELECT);
750
751         /* select the output */
752         BMO_HeaderFlag_Buffer(em->bm, &bmop, "edgeout", BM_SELECT, BM_ALL);
753         EDBM_selectmode_flush(em);
754
755         /* finish the operator */
756         if( !EDBM_FinishOp(em, &bmop, op, 1) )
757                 return OPERATOR_CANCELLED;
758
759         /* dependencies graph and notification stuff */
760         DAG_id_tag_update(ob->data, OB_RECALC_DATA);
761         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, ob->data);
762
763         /* we succeeded */
764         return OPERATOR_FINISHED;
765 }
766
767 /* ********************************* */
768
769 /*
770 VERT GROUP
771  mode 1: same normal
772  mode 2: same number of face users
773  mode 3: same vertex groups
774 */
775
776
777 static int similar_vert_select_exec(bContext *C, wmOperator *op)
778 {
779         Object *ob = CTX_data_edit_object(C);
780         BMEditMesh *em = ((Mesh*)ob->data)->edit_btmesh;
781         BMOperator bmop;
782         /* get the type from RNA */
783         int type = RNA_enum_get(op->ptr, "type");
784         float thresh = CTX_data_tool_settings(C)->select_thresh;
785
786         /* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */
787         EDBM_InitOpf(em, &bmop, op, "similarverts verts=%hv type=%d thresh=%f", BM_SELECT, type, thresh);
788
789         /* execute the operator */
790         BMO_Exec_Op(em->bm, &bmop);
791
792         /* clear the existing selection */
793         EDBM_clear_flag_all(em, BM_SELECT);
794
795         /* select the output */
796         BMO_HeaderFlag_Buffer(em->bm, &bmop, "vertout", BM_SELECT, BM_ALL);
797
798         /* finish the operator */
799         if( !EDBM_FinishOp(em, &bmop, op, 1) )
800                 return OPERATOR_CANCELLED;
801
802         EDBM_selectmode_flush(em);
803
804         /* dependencies graph and notification stuff */
805         DAG_id_tag_update(ob->data, OB_RECALC_DATA);
806         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, ob->data);
807
808         /* we succeeded */
809         return OPERATOR_FINISHED;
810 }
811
812 static int select_similar_exec(bContext *C, wmOperator *op)
813 {
814         int type= RNA_enum_get(op->ptr, "type");
815
816         if(type < 100)
817                 return similar_vert_select_exec(C, op);
818         else if(type < 200)
819                 return similar_edge_select_exec(C, op);
820         else
821                 return similar_face_select_exec(C, op);
822 }
823
824 static EnumPropertyItem *select_similar_type_itemf(bContext *C, PointerRNA *UNUSED(ptr), PropertyRNA *UNUSED(prop), int *free)
825 {
826         Object *obedit = CTX_data_edit_object(C);
827
828         if(obedit && obedit->type == OB_MESH) {
829                 EnumPropertyItem *item= NULL;
830                 int a, totitem= 0;
831                 BMEditMesh *em= ((Mesh*)obedit->data)->edit_btmesh; 
832
833                 if(em->selectmode & SCE_SELECT_VERTEX) {
834                         for (a=SIMVERT_NORMAL; a<SIMEDGE_LENGTH; a++) {
835                                 RNA_enum_items_add_value(&item, &totitem, prop_similar_types, a);
836                         }
837                 } else if(em->selectmode & SCE_SELECT_EDGE) {
838                         for (a=SIMEDGE_LENGTH; a<SIMFACE_MATERIAL; a++) {
839                                 RNA_enum_items_add_value(&item, &totitem, prop_similar_types, a);
840                         }
841                 } else if(em->selectmode & SCE_SELECT_FACE) {
842                         for (a=SIMFACE_MATERIAL; a<=SIMFACE_COPLANAR; a++) {
843                                 RNA_enum_items_add_value(&item, &totitem, prop_similar_types, a);
844                         }
845                 }
846                 RNA_enum_item_end(&item, &totitem);
847
848                 *free= 1;
849
850                 return item;
851         }
852         
853         return NULL;
854 }
855
856 void MESH_OT_select_similar(wmOperatorType *ot)
857 {
858         PropertyRNA *prop;
859
860         /* identifiers */
861         ot->name= "Select Similar";
862         ot->idname= "MESH_OT_select_similar";
863         
864         /* api callbacks */
865         ot->invoke= WM_menu_invoke;
866         ot->exec= select_similar_exec;
867         ot->poll= ED_operator_editmesh;
868         ot->description= "Select similar vertices, edges or faces by property types";
869         
870         /* flags */
871         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
872         
873         /* properties */
874         prop= ot->prop= RNA_def_enum(ot->srna, "type", prop_similar_types, SIMVERT_NORMAL, "Type", "");
875         RNA_def_enum_funcs(prop, select_similar_type_itemf);
876 }
877
878 /* ***************************************************** */
879
880 /* ****************  LOOP SELECTS *************** */
881
882 static void walker_select(BMEditMesh *em, int walkercode, void *start, int select)
883 {
884         BMesh *bm = em->bm;
885         BMHeader *h;
886         BMWalker walker;
887
888         BMW_Init(&walker, bm, walkercode, 0,0,0,0, BMW_NIL_LAY);
889         h = BMW_Begin(&walker, start);
890         for (; h; h=BMW_Step(&walker)) {
891                 if (!select)
892                         BM_remove_selection(bm, h);
893                 BM_Select(bm, h, select);
894         }
895         BMW_End(&walker);
896 }
897
898 static int loop_multiselect(bContext *C, wmOperator *op)
899 {
900         Object *obedit= CTX_data_edit_object(C);
901         BMEditMesh *em = ((Mesh*)obedit->data)->edit_btmesh;
902         BMEdge *eed;
903         BMEdge **edarray;
904         int edindex;
905         int looptype= RNA_boolean_get(op->ptr, "ring");
906         
907         BMIter iter;
908         int totedgesel = 0;
909
910         for(eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
911             eed; eed = BMIter_Step(&iter)){
912
913                 if(BM_TestHFlag(eed, BM_SELECT)){
914                         totedgesel++;
915                 }
916         }
917
918         
919         edarray = MEM_mallocN(sizeof(BMEdge*)*totedgesel,"edge array");
920         edindex = 0;
921         
922         for(eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
923             eed; eed = BMIter_Step(&iter)){
924
925                 if(BM_TestHFlag(eed, BM_SELECT)){
926                         edarray[edindex] = eed;
927                         edindex++;
928                 }
929         }
930         
931         if(looptype){
932                 for(edindex = 0; edindex < totedgesel; edindex +=1){
933                         eed = edarray[edindex];
934                         walker_select(em, BMW_EDGERING, eed, 1);
935                 }
936                 EDBM_selectmode_flush(em);
937         }
938         else{
939                 for(edindex = 0; edindex < totedgesel; edindex +=1){
940                         eed = edarray[edindex];
941                         walker_select(em, BMW_LOOP, eed, 1);
942                 }
943                 EDBM_selectmode_flush(em);
944         }
945         MEM_freeN(edarray);
946 //      if (EM_texFaceCheck())
947         
948         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
949
950         return OPERATOR_FINISHED;       
951 }
952
953 void MESH_OT_loop_multi_select(wmOperatorType *ot)
954 {
955         /* identifiers */
956         ot->name= "Multi Select Loops";
957         ot->idname= "MESH_OT_loop_multi_select";
958         
959         /* api callbacks */
960         ot->exec= loop_multiselect;
961         ot->poll= ED_operator_editmesh;
962         ot->description= "Select a loop of connected edges by connection type";
963         
964         /* flags */
965         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
966         
967         /* properties */
968         RNA_def_boolean(ot->srna, "ring", 0, "Ring", "");
969 }
970
971                 
972 /* ***************** MAIN MOUSE SELECTION ************** */
973
974
975 /* ***************** loop select (non modal) ************** */
976
977 static void mouse_mesh_loop(bContext *C, int mval[2], short extend, short ring)
978 {
979         ViewContext vc;
980         BMEditMesh *em;
981         BMEdge *eed;
982         int select= 1;
983         int dist = 50;
984         
985         em_setup_viewcontext(C, &vc);
986         vc.mval[0]= mval[0];
987         vc.mval[1]= mval[1];
988         em= vc.em;
989         
990         /* no afterqueue (yet), so we check it now, otherwise the bm_xxxofs indices are bad */
991         view3d_validate_backbuf(&vc);
992
993         eed = EDBM_findnearestedge(&vc, &dist);
994         if (eed) {
995                 if(extend==0) EDBM_clear_flag_all(em, BM_SELECT);
996         
997                 if (BM_TestHFlag(eed, BM_SELECT)==0) {
998                         select=1;
999                 }
1000                 else if (extend) {
1001                         select=0;
1002                 }
1003
1004                 if(em->selectmode & SCE_SELECT_FACE) {
1005                         walker_select(em, BMW_FACELOOP, eed, select);
1006                 }
1007                 else if(em->selectmode & SCE_SELECT_EDGE) {
1008                         if(ring)
1009                                 walker_select(em, BMW_EDGERING, eed, select);
1010                         else
1011                                 walker_select(em, BMW_LOOP, eed, select);
1012                 }
1013                 else if(em->selectmode & SCE_SELECT_VERTEX) {
1014                         if(ring)
1015                                 walker_select(em, BMW_EDGERING, eed, select);
1016
1017                         else
1018                                 walker_select(em, BMW_LOOP, eed, select);
1019                 }
1020
1021                 EDBM_selectmode_flush(em);
1022 //                      if (EM_texFaceCheck())
1023                 
1024                 /* sets as active, useful for other tools */
1025                 if (select) {
1026                         if (em->selectmode & SCE_SELECT_VERTEX) {
1027                                 /* TODO: would be nice if the edge vertex chosen here
1028                                    was the one closer to the selection pointer, instead
1029                                    of arbitrarily selecting the first one */
1030                                 EDBM_store_selection(em, eed->v1);
1031                         }
1032                         else if(em->selectmode & SCE_SELECT_EDGE) {
1033                                 EDBM_store_selection(em, eed);
1034                         }
1035                         /* TODO: would be nice if the nearest face that
1036                            belongs to the selected edge could be set to
1037                            active here in face select mode */
1038                 }
1039
1040                 WM_event_add_notifier(C, NC_GEOM|ND_SELECT, vc.obedit);
1041         }
1042 }
1043
1044 static int mesh_select_loop_invoke(bContext *C, wmOperator *op, wmEvent *event)
1045 {
1046         
1047         view3d_operator_needs_opengl(C);
1048         
1049         mouse_mesh_loop(C, event->mval, RNA_boolean_get(op->ptr, "extend"),
1050                                         RNA_boolean_get(op->ptr, "ring"));
1051         
1052         /* cannot do tweaks for as long this keymap is after transform map */
1053         return OPERATOR_FINISHED;
1054 }
1055
1056 void MESH_OT_loop_select(wmOperatorType *ot)
1057 {
1058         /* identifiers */
1059         ot->name= "Loop Select";
1060         ot->idname= "MESH_OT_loop_select";
1061         ot->description= "Select a loop";
1062         
1063         /* api callbacks */
1064         ot->invoke= mesh_select_loop_invoke;
1065         ot->poll= ED_operator_editmesh_region_view3d;
1066         ot->description= "Select a loop of connected edges";
1067         
1068         /* flags */
1069         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1070         
1071         /* properties */
1072         RNA_def_boolean(ot->srna, "extend", 0, "Extend Select", "Extend the selection");
1073         RNA_def_boolean(ot->srna, "ring", 0, "Select Ring", "Select ring");
1074 }
1075
1076 void MESH_OT_edgering_select (wmOperatorType *ot)
1077 {
1078         /* description */
1079         ot->name= "Edge Ring Select";
1080         ot->idname= "MESH_OT_edgering_select";
1081         ot->description= "Select an edge ring";
1082         
1083         /* callbacks */
1084         ot->invoke= mesh_select_loop_invoke;
1085         ot->poll= ED_operator_editmesh_region_view3d;
1086         
1087         /* flags */
1088         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1089
1090         RNA_def_boolean(ot->srna, "extend", 0, "Extend", "Extend the selection");
1091         RNA_def_boolean(ot->srna, "ring", 1, "Select Ring", "Select ring");
1092 }
1093
1094 /* ******************* edgetag_shortest_path and helpers ****************** */
1095
1096 static float edgetag_cut_cost(BMEditMesh *UNUSED(em), BMEdge *e1, BMEdge *e2, BMVert* v)
1097 {
1098         BMVert *v1 = (e1->v1 == v) ? e1->v2 : e1->v1;
1099         BMVert *v2 = (e2->v1 == v) ? e2->v2 : e2->v1;
1100         float cost, d1[3], d2[3];
1101
1102         /*The cost is based on the simple sum of the length of the two edgees...*/
1103         sub_v3_v3v3(d1, v->co, v1->co);
1104         sub_v3_v3v3(d2, v2->co, v->co);
1105         cost = len_v3(d1);
1106         cost += len_v3(d2);
1107
1108         /*...but is biased to give higher values to sharp turns, so that it will take
1109           paths with fewer "turns" when selecting between equal-weighted paths between
1110           the two edges*/
1111         cost = cost + 0.5f*cost*(2.0f - sqrt(fabs(dot_v3v3(d1, d2))));
1112
1113         return cost;
1114 }
1115
1116 static void edgetag_add_adjacent(BMEditMesh *em, SmallHash *visithash, Heap *heap, int mednum, int vertnum, 
1117                                                                  int *nedges, int *edges, int *prevedge, float *cost)
1118 {
1119         BMEdge *e1 = EDBM_get_edge_for_index(em, mednum);
1120         BMVert *v = EDBM_get_vert_for_index(em, vertnum);
1121         int startadj, endadj = nedges[vertnum+1];
1122
1123         for (startadj = nedges[vertnum]; startadj < endadj; startadj++) {
1124                 int adjnum = edges[startadj];
1125                 BMEdge *e2 = EDBM_get_edge_for_index(em, adjnum);
1126                 float newcost;
1127                 float cutcost;
1128
1129                 if (BLI_smallhash_haskey(visithash, (uintptr_t)e2))
1130                         continue;
1131
1132                 cutcost = edgetag_cut_cost(em, e1, e2, v);
1133                 newcost = cost[mednum] + cutcost;
1134
1135                 if (cost[adjnum] > newcost) {
1136                         cost[adjnum] = newcost;
1137                         prevedge[adjnum] = mednum;
1138                         BLI_heap_insert(heap, newcost, SET_INT_IN_POINTER(adjnum));
1139                 }
1140         }
1141 }
1142
1143 static void edgetag_context_set(BMEditMesh *em, Scene *scene, BMEdge *e, int val)
1144 {
1145         
1146         switch (scene->toolsettings->edge_mode) {
1147         case EDGE_MODE_SELECT:
1148                 BM_Select(em->bm, e, val);
1149                 break;
1150         case EDGE_MODE_TAG_SEAM:
1151                 if (val)                {BM_SetHFlag(e, BM_SEAM);}
1152                 else                    {BM_ClearHFlag(e, BM_SEAM);}
1153                 break;
1154         case EDGE_MODE_TAG_SHARP:
1155                 if (val)                {BM_SetHFlag(e, BM_SEAM);}
1156                 else                    {BM_ClearHFlag(e, BM_SEAM);}
1157                 break;                          
1158         case EDGE_MODE_TAG_CREASE:
1159          {
1160                 float *crease = CustomData_bmesh_get(&em->bm->edata, e->head.data, CD_CREASE);
1161                 
1162                 if (val)                {*crease = 1.0f;}
1163                 else                    {*crease = 0.0f;}
1164                 break;
1165          }
1166         case EDGE_MODE_TAG_BEVEL:
1167          {
1168                 float *bweight = CustomData_bmesh_get(&em->bm->edata, e->head.data, CD_BWEIGHT);
1169
1170                 if (val)                {*bweight = 1.0f;}
1171                 else                    {*bweight = 0.0f;}
1172                 break;
1173          }
1174         }
1175 }
1176
1177 static float bm_cdata_get_single_float(BMesh *UNUSED(bm), CustomData *cdata, void *element, int type)
1178 {
1179         BMHeader *ele = element;
1180         float *f;
1181         
1182         if (!CustomData_has_layer(cdata, type))
1183                 return 0.0f;
1184         
1185         f = CustomData_bmesh_get(cdata, ele->data, type);
1186         
1187         return *f;
1188 }
1189
1190 static int edgetag_context_check(Scene *scene, BMEditMesh *em, BMEdge *e)
1191 {
1192         switch (scene->toolsettings->edge_mode) {
1193         case EDGE_MODE_SELECT:
1194                 return BM_TestHFlag(e, BM_SELECT) ? 1 : 0;
1195         case EDGE_MODE_TAG_SEAM:
1196                 return BM_TestHFlag(e, BM_SEAM);
1197         case EDGE_MODE_TAG_SHARP:
1198                 return BM_TestHFlag(e, BM_SHARP);
1199         case EDGE_MODE_TAG_CREASE:      
1200                 return bm_cdata_get_single_float(em->bm, &em->bm->edata, e, CD_CREASE) ? 1 : 0;
1201         case EDGE_MODE_TAG_BEVEL:
1202                 return bm_cdata_get_single_float(em->bm, &em->bm->edata, e, CD_BWEIGHT) ? 1 : 0;
1203         }
1204         return 0;
1205 }
1206
1207 static int edgetag_shortest_path(Scene *scene, BMEditMesh *em, BMEdge *source, BMEdge *target)
1208 {
1209         BMEdge *e;
1210         BMIter iter;
1211         Heap *heap;
1212         SmallHash visithash;
1213         float *cost;
1214         int i, totvert=0, totedge=0, *nedges, *edges, *prevedge, mednum = -1, nedgeswap = 0;
1215         int targetnum;
1216
1217         BLI_smallhash_init(&visithash);
1218
1219         /* note, would pass BM_EDGE except we are looping over all edges anyway */
1220         BM_ElemIndex_Ensure(em->bm, BM_VERT /* | BM_EDGE */ );
1221
1222         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
1223                 e->head.flags[0].f = 0;
1224                 if (BM_TestHFlag(e, BM_HIDDEN)) {
1225                         BLI_smallhash_insert(&visithash, (uintptr_t)e, NULL);
1226                 }
1227
1228                 BM_SetIndex(e, totedge); /* set_inline */
1229                 totedge++;
1230         }
1231         em->bm->elem_index_dirty &= ~BM_EDGE;
1232
1233         /* alloc */
1234         nedges = MEM_callocN(sizeof(*nedges)*totvert+1, "SeamPathNEdges");
1235         edges = MEM_mallocN(sizeof(*edges)*totedge*2, "SeamPathEdges");
1236         prevedge = MEM_mallocN(sizeof(*prevedge)*totedge, "SeamPathPrevious");
1237         cost = MEM_mallocN(sizeof(*cost)*totedge, "SeamPathCost");
1238
1239         /* count edges, compute adjacent edges offsets and fill adjacent */
1240         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
1241                 nedges[BM_GetIndex(e->v1)+1]++;
1242                 nedges[BM_GetIndex(e->v2)+1]++;
1243         }
1244
1245         for (i = 1; i < totvert; i++) {
1246                 int newswap = nedges[i+1];
1247                 nedges[i+1] = nedgeswap + nedges[i];
1248                 nedgeswap = newswap;
1249         }
1250         nedges[0] = nedges[1] = 0;
1251
1252         i = 0;
1253         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
1254                 edges[nedges[BM_GetIndex(e->v1)+1]++] = i;
1255                 edges[nedges[BM_GetIndex(e->v2)+1]++] = i;
1256
1257                 cost[i] = 1e20f;
1258                 prevedge[i] = -1;
1259                 i++;
1260         }
1261
1262         /*
1263          * Arrays are now filled as follows:
1264          *
1265          *      nedges[n] = sum of the # of edges incident to all vertices numbered 0 thru n-1
1266          *      edges[edges[n]..edges[n-1]] = the indices of of the edges incident to vertex n
1267          *
1268          * As the search continues, prevedge[n] will be the previous edge on the shortest
1269          * path found so far to edge n. The visitedhash will of course contain entries
1270          * for edges that have been visited, cost[n] will contain the length of the shortest
1271          * path to edge n found so far, Finally, heap is a priority heap which is built on the
1272          * the same data as the cost arry, but inverted: it is a worklist of edges prioritized
1273          * by the shortest path found so far to the edge.
1274         */
1275
1276 #if 0 /* UNUSED */ /* this block does nothing, not sure why its here? - campbell */
1277         for (i = 0; i < totvert; i++) {
1278                 int start = nedges[i], end = nedges[i+1], cur;
1279                 for (cur = start; cur < end; cur++) {
1280                         BMEdge* e = EDBM_get_edge_for_index(em, edges[cur]);
1281                 }
1282         }
1283 #endif
1284
1285         /* regular dijkstra shortest path, but over edges instead of vertices */
1286         heap = BLI_heap_new();
1287         BLI_heap_insert(heap, 0.0f, SET_INT_IN_POINTER(BM_GetIndex(source)));
1288         cost[BM_GetIndex(source)] = 0.0f;
1289         EDBM_init_index_arrays(em, 1, 1, 0);
1290         targetnum = BM_GetIndex(target);
1291
1292         while (!BLI_heap_empty(heap)) {
1293                 mednum = GET_INT_FROM_POINTER(BLI_heap_popmin(heap));
1294                 e = EDBM_get_edge_for_index(em, mednum);
1295
1296                 if (mednum == targetnum)
1297                         break;
1298
1299                 if (BLI_smallhash_haskey(&visithash, (uintptr_t)e))
1300                         continue;
1301
1302                 BLI_smallhash_insert(&visithash, (uintptr_t)e, NULL);
1303
1304                 edgetag_add_adjacent(em, &visithash, heap, mednum, BM_GetIndex(e->v1), nedges, edges, prevedge, cost);
1305                 edgetag_add_adjacent(em, &visithash, heap, mednum, BM_GetIndex(e->v2), nedges, edges, prevedge, cost);
1306         }
1307         
1308         if (mednum == targetnum) {
1309                 short allseams = 1;
1310
1311                 /*Check whether the path is already completely tagged.
1312                   if it is, the tags will be cleared instead of set.*/
1313                 mednum = targetnum;
1314                 do {
1315                         e = EDBM_get_edge_for_index(em, mednum);
1316                         if (!edgetag_context_check(scene, em, e)) {
1317                                 allseams = 0;
1318                                 break;
1319                         }
1320                         mednum = prevedge[mednum];
1321                 } while (mednum != BM_GetIndex(source));
1322
1323                 /*Follow path back and source and add or remove tags*/
1324                 mednum = targetnum;
1325                 do {
1326                         e = EDBM_get_edge_for_index(em, mednum);
1327                         if (allseams)
1328                                 edgetag_context_set(em, scene, e, 0);
1329                         else
1330                                 edgetag_context_set(em, scene, e, 1);
1331                         mednum = prevedge[mednum];
1332                 } while (mednum != -1);
1333         }
1334
1335         EDBM_free_index_arrays(em);
1336         MEM_freeN(nedges);
1337         MEM_freeN(edges);
1338         MEM_freeN(prevedge);
1339         MEM_freeN(cost);
1340         BLI_heap_free(heap, NULL);
1341         BLI_smallhash_release(&visithash);
1342
1343         return 1;
1344 }
1345
1346 /* ******************* mesh shortest path select, uses prev-selected edge ****************** */
1347
1348 /* since you want to create paths with multiple selects, it doesn't have extend option */
1349 static void mouse_mesh_shortest_path(bContext *C, int mval[2])
1350 {
1351         Object *ob = CTX_data_edit_object(C);
1352         ViewContext vc;
1353         BMEditMesh *em;
1354         BMEdge *e;
1355         int dist= 50;
1356         
1357         em_setup_viewcontext(C, &vc);
1358         vc.mval[0]= mval[0];
1359         vc.mval[1]= mval[1];
1360         em= vc.em;
1361         
1362         e= EDBM_findnearestedge(&vc, &dist);
1363         if(e) {
1364                 Mesh *me= vc.obedit->data;
1365                 int path = 0;
1366                 
1367                 if (em->bm->selected.last) {
1368                         BMEditSelection *ese= em->bm->selected.last;
1369                         
1370                         if(ese && ese->htype == BM_EDGE) {
1371                                 BMEdge *e_act;
1372                                 e_act = (BMEdge *)ese->data;
1373                                 if (e_act != e) {
1374                                         if (edgetag_shortest_path(vc.scene, em, e_act, e)) {
1375                                                 EDBM_remove_selection(em, e_act);
1376                                                 path = 1;
1377                                         }
1378                                 }
1379                         }
1380                 }
1381                 if (path==0) {
1382                         int act = (edgetag_context_check(vc.scene, em, e)==0);
1383                         edgetag_context_set(em, vc.scene, e, act); /* switch the edge option */
1384                 }
1385                 
1386                 EDBM_selectmode_flush(em);
1387
1388                 /* even if this is selected it may not be in the selection list */
1389                 if(edgetag_context_check(vc.scene, em, e)==0)
1390                         EDBM_remove_selection(em, e);
1391                 else
1392                         EDBM_store_selection(em, e);
1393         
1394                 /* force drawmode for mesh */
1395                 switch (CTX_data_tool_settings(C)->edge_mode) {
1396                         
1397                         case EDGE_MODE_TAG_SEAM:
1398                                 me->drawflag |= ME_DRAWSEAMS;
1399                                 break;
1400                         case EDGE_MODE_TAG_SHARP:
1401                                 me->drawflag |= ME_DRAWSHARP;
1402                                 break;
1403                         case EDGE_MODE_TAG_CREASE:      
1404                                 me->drawflag |= ME_DRAWCREASES;
1405                                 break;
1406                         case EDGE_MODE_TAG_BEVEL:
1407                                 me->drawflag |= ME_DRAWBWEIGHTS;
1408                                 break;
1409                 }
1410                 
1411                 DAG_id_tag_update(ob->data, OB_RECALC_DATA);
1412                 WM_event_add_notifier(C, NC_GEOM|ND_SELECT, ob->data);
1413         }
1414 }
1415
1416
1417 static int mesh_shortest_path_select_invoke(bContext *C, wmOperator *UNUSED(op), wmEvent *event)
1418 {
1419         
1420         view3d_operator_needs_opengl(C);
1421
1422         mouse_mesh_shortest_path(C, event->mval);
1423         
1424         return OPERATOR_FINISHED;
1425 }
1426         
1427 void MESH_OT_select_shortest_path(wmOperatorType *ot)
1428 {
1429         /* identifiers */
1430         ot->name= "Shortest Path Select";
1431         ot->idname= "MESH_OT_select_shortest_path";
1432         
1433         /* api callbacks */
1434         ot->invoke= mesh_shortest_path_select_invoke;
1435         ot->poll= ED_operator_editmesh;
1436         ot->description= "Select shortest path between two selections";
1437         
1438         /* flags */
1439         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1440         
1441         /* properties */
1442         RNA_def_boolean(ot->srna, "extend", 0, "Extend Select", "");
1443 }
1444
1445 /* ************************************************** */
1446 /* here actual select happens */
1447 /* gets called via generic mouse select operator */
1448 int mouse_mesh(bContext *C, const int mval[2], short extend)
1449 {
1450         ViewContext vc;
1451         BMVert *eve = NULL;
1452         BMEdge *eed = NULL;
1453         BMFace *efa = NULL;
1454         
1455         /* setup view context for argument to callbacks */
1456         em_setup_viewcontext(C, &vc);
1457         vc.mval[0]= mval[0];
1458         vc.mval[1]= mval[1];
1459         
1460         if(unified_findnearest(&vc, &eve, &eed, &efa)) {
1461                 
1462                 if(extend==0) EDBM_clear_flag_all(vc.em, BM_SELECT);
1463                 
1464                 if(efa) {
1465                         /* set the last selected face */
1466                         BM_set_actFace(vc.em->bm, efa);
1467                         
1468                         if(!BM_TestHFlag(efa, BM_SELECT)) {
1469                                 EDBM_store_selection(vc.em, efa);
1470                                 BM_Select(vc.em->bm, efa, 1);
1471                         }
1472                         else if(extend) {
1473                                 EDBM_remove_selection(vc.em, efa);
1474                                 BM_Select(vc.em->bm, efa, 0);
1475                         }
1476                 }
1477                 else if(eed) {
1478                         if(!BM_TestHFlag(eed, BM_SELECT)) {
1479                                 EDBM_store_selection(vc.em, eed);
1480                                 BM_Select(vc.em->bm, eed, 1);
1481                         }
1482                         else if(extend) {
1483                                 EDBM_remove_selection(vc.em, eed);
1484                                 BM_Select(vc.em->bm, eed, 0);
1485                         }
1486                 }
1487                 else if(eve) {
1488                         if(!BM_TestHFlag(eve, BM_SELECT)) {
1489                                 EDBM_store_selection(vc.em, eve);
1490                                 BM_Select(vc.em->bm, eve, 1);
1491                         }
1492                         else if(extend){ 
1493                                 EDBM_remove_selection(vc.em, eve);
1494                                 BM_Select(vc.em->bm, eve, 0);
1495                         }
1496                 }
1497                 
1498                 EDBM_selectmode_flush(vc.em);
1499                   
1500 //              if (EM_texFaceCheck()) {
1501
1502                 if (efa && efa->mat_nr != vc.obedit->actcol-1) {
1503                         vc.obedit->actcol= efa->mat_nr+1;
1504                         vc.em->mat_nr= efa->mat_nr;
1505 //                      BIF_preview_changed(ID_MA);
1506                 }
1507
1508                 WM_event_add_notifier(C, NC_GEOM|ND_SELECT, vc.obedit);
1509                 return 1;
1510         }
1511
1512         return 0;
1513 }
1514
1515 static void EDBM_strip_selections(BMEditMesh *em)
1516 {
1517         BMEditSelection *ese, *nextese;
1518
1519         if(!(em->selectmode & SCE_SELECT_VERTEX)){
1520                 ese = em->bm->selected.first;
1521                 while(ese){
1522                         nextese = ese->next; 
1523                         if(ese->htype == BM_VERT) BLI_freelinkN(&(em->bm->selected),ese);
1524                         ese = nextese;
1525                 }
1526         }
1527         if(!(em->selectmode & SCE_SELECT_EDGE)){
1528                 ese=em->bm->selected.first;
1529                 while(ese){
1530                         nextese = ese->next;
1531                         if(ese->htype == BM_EDGE) BLI_freelinkN(&(em->bm->selected), ese);
1532                         ese = nextese;
1533                 }
1534         }
1535         if(!(em->selectmode & SCE_SELECT_FACE)){
1536                 ese=em->bm->selected.first;
1537                 while(ese){
1538                         nextese = ese->next;
1539                         if(ese->htype == BM_FACE) BLI_freelinkN(&(em->bm->selected), ese);
1540                         ese = nextese;
1541                 }
1542         }
1543 }
1544
1545 /* when switching select mode, makes sure selection is consistant for editing */
1546 /* also for paranoia checks to make sure edge or face mode works */
1547 void EDBM_selectmode_set(BMEditMesh *em)
1548 {
1549         BMVert *eve;
1550         BMEdge *eed;
1551         BMFace *efa;
1552         BMIter iter;
1553         
1554         em->bm->selectmode = em->selectmode;
1555
1556         EDBM_strip_selections(em); /*strip BMEditSelections from em->selected that are not relevant to new mode*/
1557         
1558         if(em->selectmode & SCE_SELECT_VERTEX) {
1559                 /*BMIter iter;
1560                 
1561                 eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1562                 for ( ; eed; eed=BMIter_Step(&iter)) BM_Select(em->bm, eed, 0);
1563                 
1564                 efa = BMIter_New(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1565                 for ( ; efa; efa=BMIter_Step(&iter)) BM_Select(em->bm, efa, 0);*/
1566
1567                 EDBM_selectmode_flush(em);
1568         }
1569         else if(em->selectmode & SCE_SELECT_EDGE) {
1570                 /* deselect vertices, and select again based on edge select */
1571                 eve = BMIter_New(&iter, em->bm, BM_VERTS_OF_MESH, NULL);
1572                 for ( ; eve; eve=BMIter_Step(&iter)) BM_Select(em->bm, eve, 0);
1573                 
1574                 eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1575                 for ( ; eed; eed=BMIter_Step(&iter)) {
1576                         if (BM_TestHFlag(eed, BM_SELECT))
1577                                 BM_Select(em->bm, eed, 1);
1578                 }
1579                 
1580                 /* selects faces based on edge status */
1581                 EDBM_selectmode_flush(em);
1582         }
1583         else if(em->selectmode & SCE_SELECT_FACE) {
1584                 /* deselect eges, and select again based on face select */
1585                 eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1586                 for ( ; eed; eed=BMIter_Step(&iter)) BM_Select(em->bm, eed, 0);
1587                 
1588                 efa = BMIter_New(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1589                 for ( ; efa; efa=BMIter_Step(&iter)) {
1590                         if (BM_TestHFlag(efa, BM_SELECT))
1591                                 BM_Select(em->bm, efa, 1);
1592                 }
1593         }
1594 }
1595
1596 void EDBM_convertsel(BMEditMesh *em, short oldmode, short selectmode)
1597 {
1598         BMEdge *eed;
1599         BMFace *efa;
1600         BMIter iter;
1601
1602         /*have to find out what the selectionmode was previously*/
1603         if(oldmode == SCE_SELECT_VERTEX) {
1604                 if(selectmode == SCE_SELECT_EDGE) {
1605                         /*select all edges associated with every selected vertex*/
1606                         eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1607                         for ( ; eed; eed=BMIter_Step(&iter)) {
1608                                 if(BM_TestHFlag(eed->v1, BM_SELECT)) BM_Select(em->bm, eed, 1);
1609                                 else if(BM_TestHFlag(eed->v2, BM_SELECT)) BM_Select(em->bm, eed, 1);
1610                         }
1611                 }               
1612                 else if(selectmode == SCE_SELECT_FACE) {
1613                         BMIter liter;
1614                         BMLoop *l;
1615
1616                         /*select all faces associated with every selected vertex*/
1617                         efa = BMIter_New(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1618                         for ( ; efa; efa=BMIter_Step(&iter)) {
1619                                 l = BMIter_New(&liter, em->bm, BM_LOOPS_OF_FACE, efa);
1620                                 for (; l; l=BMIter_Step(&liter)) {
1621                                         if (BM_TestHFlag(l->v, BM_SELECT)) {
1622                                                 BM_Select(em->bm, efa, 1);
1623                                                 break;
1624                                         }
1625                                 }
1626                         }
1627                 }
1628         }
1629         
1630         if(oldmode == SCE_SELECT_EDGE){
1631                 if(selectmode == SCE_SELECT_FACE) {
1632                         BMIter liter;
1633                         BMLoop *l;
1634
1635                         /*select all faces associated with every selected vertex*/
1636                         efa = BMIter_New(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1637                         for ( ; efa; efa=BMIter_Step(&iter)) {
1638                                 l = BMIter_New(&liter, em->bm, BM_LOOPS_OF_FACE, efa);
1639                                 for (; l; l=BMIter_Step(&liter)) {
1640                                         if (BM_TestHFlag(l->v, BM_SELECT)) {
1641                                                 BM_Select(em->bm, efa, 1);
1642                                                 break;
1643                                         }
1644                                 }
1645                         }
1646                 }
1647         }
1648 }
1649
1650
1651 void EDBM_deselect_by_material(struct BMEditMesh *em, const short index, const short select)
1652 {
1653         BMIter iter;
1654         BMFace *efa;
1655
1656         BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
1657                 if (BM_TestHFlag(efa, BM_HIDDEN))
1658                         continue;
1659                 if(efa->mat_nr == index) {
1660                         BM_Select(em->bm, efa, select);
1661                 }
1662         }
1663 }
1664
1665
1666 void EDBM_select_swap(BMEditMesh *em) /* exported for UV */
1667 {
1668         BMIter iter;
1669         BMVert *eve;
1670         BMEdge *eed;
1671         BMFace *efa;
1672         
1673         if(em->bm->selectmode & SCE_SELECT_VERTEX) {
1674                 BM_ITER(eve, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
1675                         if (BM_TestHFlag(eve, BM_HIDDEN))
1676                                 continue;
1677                         BM_Select(em->bm, eve, !BM_TestHFlag(eve, BM_SELECT));
1678                 }
1679         }
1680         else if(em->selectmode & SCE_SELECT_EDGE) {
1681                 BM_ITER(eed, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
1682                         if (BM_TestHFlag(eed, BM_HIDDEN))
1683                                 continue;
1684                         BM_Select(em->bm, eed, !BM_TestHFlag(eed, BM_SELECT));
1685                 }
1686         }
1687         else {
1688                 BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
1689                         if (BM_TestHFlag(efa, BM_HIDDEN))
1690                                 continue;
1691                         BM_Select(em->bm, efa, !BM_TestHFlag(efa, BM_SELECT));
1692                 }
1693
1694         }
1695 //      if (EM_texFaceCheck())
1696 }
1697
1698 static int select_inverse_mesh_exec(bContext *C, wmOperator *UNUSED(op))
1699 {
1700         Object *obedit= CTX_data_edit_object(C);
1701         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
1702         
1703         EDBM_select_swap(em);
1704         
1705         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1706
1707         return OPERATOR_FINISHED;       
1708 }
1709
1710 void MESH_OT_select_inverse(wmOperatorType *ot)
1711 {
1712         /* identifiers */
1713         ot->name= "Select Inverse";
1714         ot->idname= "MESH_OT_select_inverse";
1715         ot->description= "Select inverse of (un)selected vertices, edges or faces";
1716         
1717         /* api callbacks */
1718         ot->exec= select_inverse_mesh_exec;
1719         ot->poll= ED_operator_editmesh;
1720         
1721         /* flags */
1722         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1723 }
1724
1725
1726 static int select_linked_pick_invoke(bContext *C, wmOperator *op, wmEvent *event)
1727 {
1728         Object *obedit= CTX_data_edit_object(C);
1729         ViewContext vc;
1730         BMesh *bm;
1731         BMWalker walker;
1732         BMEditMesh *em;
1733         BMVert *eve;
1734         BMEdge *e, *eed;
1735         BMFace *efa;
1736         int sel= !RNA_boolean_get(op->ptr, "deselect");
1737         
1738         /* unified_finednearest needs ogl */
1739         view3d_operator_needs_opengl(C);
1740         
1741         /* setup view context for argument to callbacks */
1742         em_setup_viewcontext(C, &vc);
1743         em = vc.em;
1744
1745         if(em->bm->totedge==0)
1746                 return OPERATOR_CANCELLED;
1747         
1748         bm= em->bm;
1749
1750         vc.mval[0]= event->mval[0];
1751         vc.mval[1]= event->mval[1];
1752         
1753         /* return warning! */
1754
1755         /*if(limit) {
1756                 int retval= select_linked_limited_invoke(&vc, 0, sel);
1757                 WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1758                 return retval;
1759         }*/
1760         
1761         if( unified_findnearest(&vc, &eve, &eed, &efa)==0 ) {
1762                 WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1763         
1764                 return OPERATOR_CANCELLED;
1765         }
1766         
1767         if (em->selectmode == SCE_SELECT_FACE) {
1768                 BMIter iter;
1769
1770                 if (efa == NULL)
1771                         return OPERATOR_CANCELLED;
1772
1773                 BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
1774                         if (!BM_TestHFlag(e, BM_SEAM)) BMO_SetFlag(bm, e, BM_SELECT);
1775                         else                           BMO_ClearFlag(bm, e, BM_SELECT); /* is this needed ? */
1776                 }
1777
1778                 /* walk */
1779                 BMW_Init(&walker, bm, BMW_ISLAND,  0,BM_SELECT,0,0,  BMW_NIL_LAY);
1780                 e = BMW_Begin(&walker, efa);
1781                 for (; efa; efa=BMW_Step(&walker)) {
1782                         BM_Select(bm, efa, sel);
1783                 }
1784                 BMW_End(&walker);
1785         }
1786         else {
1787                 if (efa) {
1788                         eed = bm_firstfaceloop(efa)->e;
1789                 } else if (!eed) {
1790                         if (!eve || !eve->e)
1791                                 return OPERATOR_CANCELLED;
1792
1793                         eed = eve->e;
1794                 }
1795
1796                 BMW_Init(&walker, bm, BMW_SHELL, 0,0,0,0, BMW_NIL_LAY);
1797                 e = BMW_Begin(&walker, eed->v1);
1798                 for (; e; e=BMW_Step(&walker)) {
1799                                 BM_Select(bm, e->v1, sel);
1800                                 BM_Select(bm, e->v2, sel);
1801                 }
1802                 BMW_End(&walker);
1803                 EDBM_select_flush(em, SCE_SELECT_VERTEX);
1804         }
1805
1806         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1807         return OPERATOR_FINISHED;       
1808 }
1809
1810 void MESH_OT_select_linked_pick(wmOperatorType *ot)
1811 {
1812         /* identifiers */
1813         ot->name= "Select Linked";
1814         ot->idname= "MESH_OT_select_linked_pick";
1815         
1816         /* api callbacks */
1817         ot->invoke= select_linked_pick_invoke;
1818         ot->poll= ED_operator_editmesh;
1819         ot->description= "select/deselect all vertices linked to the edge under the mouse cursor";
1820         
1821         /* flags */
1822         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1823         
1824         RNA_def_boolean(ot->srna, "deselect", 0, "Deselect", "");
1825         RNA_def_boolean(ot->srna, "limit", 0, "Limit by Seams", "");
1826 }
1827
1828
1829 static int select_linked_exec(bContext *C, wmOperator *UNUSED(op))
1830 {
1831         Object *obedit= CTX_data_edit_object(C);
1832         BMEditMesh *em= ((Mesh*)obedit->data)->edit_btmesh;
1833         BMesh *bm= em->bm;
1834         BMIter iter;
1835         BMVert *v;
1836         BMEdge *e;
1837         BMWalker walker;
1838
1839         if (em->selectmode == SCE_SELECT_FACE) {
1840                 BMFace *efa;
1841
1842                 BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
1843                         if (BM_TestHFlag(efa, BM_SELECT) && !BM_TestHFlag(efa, BM_HIDDEN)) {
1844                                 BM_SetHFlag(efa, BM_TMP_TAG);
1845                         }
1846                         else {
1847                                 BM_ClearHFlag(efa, BM_TMP_TAG);
1848                         }
1849                 }
1850
1851                 BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
1852                         if (!BM_TestHFlag(e, BM_SEAM)) BMO_SetFlag(bm, e, BM_SELECT);
1853                         else                           BMO_ClearFlag(bm, e, BM_SELECT); /* is this needed ? */
1854                 }
1855
1856                 BMW_Init(&walker, bm, BMW_ISLAND,  0,BM_SELECT,0,0,  BMW_NIL_LAY);
1857                 BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
1858                         if (BM_TestHFlag(efa, BM_TMP_TAG)) {
1859                                 e = BMW_Begin(&walker, efa);
1860                                 for (; efa; efa=BMW_Step(&walker)) {
1861                                         BM_Select(bm, efa, TRUE);
1862                                 }
1863                         }
1864                 }
1865                 BMW_End(&walker);
1866         }
1867         else  {
1868                 BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
1869                         if (BM_TestHFlag(v, BM_SELECT) && !BM_TestHFlag(v, BM_HIDDEN)) {
1870                                 BM_SetHFlag(v, BM_TMP_TAG);
1871                         }
1872                         else {
1873                                 BM_ClearHFlag(v, BM_TMP_TAG);
1874                         }
1875                 }
1876
1877                 BMW_Init(&walker, em->bm, BMW_SHELL, 0,0,0,0, BMW_NIL_LAY);
1878                 BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
1879                         if (BM_TestHFlag(v, BM_TMP_TAG)) {
1880                                 e = BMW_Begin(&walker, v);
1881                                 for (; e; e=BMW_Step(&walker)) {
1882                                         BM_Select(em->bm, e->v1, 1);
1883                                         BM_Select(em->bm, e->v2, 1);
1884                                 }
1885                         }
1886                 }
1887                 BMW_End(&walker);
1888         }
1889         EDBM_select_flush(em, SCE_SELECT_VERTEX);
1890
1891         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1892
1893         return OPERATOR_FINISHED;       
1894 }
1895
1896 void MESH_OT_select_linked(wmOperatorType *ot)
1897 {
1898         /* identifiers */
1899         ot->name= "Select Linked All";
1900         ot->idname= "MESH_OT_select_linked";
1901         
1902         /* api callbacks */
1903         ot->exec= select_linked_exec;
1904         ot->poll= ED_operator_editmesh;
1905         ot->description= "Select all vertices linked to the active mesh";
1906         
1907         /* flags */
1908         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1909         
1910         RNA_def_boolean(ot->srna, "limit", 0, "Limit by Seams", "");
1911 }
1912
1913 /* ******************** **************** */
1914
1915 static int select_more(bContext *C, wmOperator *op)
1916 {
1917         Object *obedit= CTX_data_edit_object(C);
1918         BMEditMesh *em= (((Mesh *)obedit->data))->edit_btmesh;
1919         BMOperator bmop;
1920         int usefaces = em->selectmode > SCE_SELECT_EDGE;
1921
1922         EDBM_InitOpf(em, &bmop, op, "regionextend geom=%hvef constrict=%d usefaces=%d", 
1923                      BM_SELECT, 0, usefaces);
1924
1925         BMO_Exec_Op(em->bm, &bmop);
1926         BMO_HeaderFlag_Buffer(em->bm, &bmop, "geomout", BM_SELECT, BM_ALL);
1927
1928         EDBM_selectmode_flush(em);
1929
1930         if (!EDBM_FinishOp(em, &bmop, op, 1))
1931                 return OPERATOR_CANCELLED;
1932
1933         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1934         return OPERATOR_FINISHED;
1935 }
1936
1937 void MESH_OT_select_more(wmOperatorType *ot)
1938 {
1939         /* identifiers */
1940         ot->name= "Select More";
1941         ot->idname= "MESH_OT_select_more";
1942         ot->description= "Select more vertices, edges or faces connected to initial selection";
1943
1944         /* api callbacks */
1945         ot->exec= select_more;
1946         ot->poll= ED_operator_editmesh;
1947         
1948         /* flags */
1949         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1950 }
1951
1952 static int select_less(bContext *C, wmOperator *op)
1953 {
1954         Object *obedit= CTX_data_edit_object(C);
1955         BMEditMesh *em= (((Mesh *)obedit->data))->edit_btmesh;
1956         BMOperator bmop;
1957         int usefaces = em->selectmode > SCE_SELECT_EDGE;
1958
1959         EDBM_InitOpf(em, &bmop, op, "regionextend geom=%hvef constrict=%d usefaces=%d", 
1960                      BM_SELECT, 1, usefaces);
1961
1962         BMO_Exec_Op(em->bm, &bmop);
1963         BMO_UnHeaderFlag_Buffer(em->bm, &bmop, "geomout", BM_SELECT, BM_ALL);
1964
1965         EDBM_selectmode_flush(em);
1966
1967         if (!EDBM_FinishOp(em, &bmop, op, 1))
1968                 return OPERATOR_CANCELLED;
1969
1970         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1971         return OPERATOR_FINISHED;
1972 }
1973
1974 void MESH_OT_select_less(wmOperatorType *ot)
1975 {
1976         /* identifiers */
1977         ot->name= "Select Less";
1978         ot->idname= "MESH_OT_select_less";
1979         ot->description= "Deselect vertices, edges or faces at the boundary of each selection region";
1980
1981         /* api callbacks */
1982         ot->exec= select_less;
1983         ot->poll= ED_operator_editmesh;
1984         
1985         /* flags */
1986         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1987 }
1988
1989 /* Walk all reachable elements of the same type as h_act in breadth-first
1990    order, starting from h_act. Deselects elements if the depth when they
1991    are reached is not a multiple of "nth". */
1992 static void walker_deselect_nth(BMEditMesh *em, int nth, int offset, BMHeader *h_act)
1993 {
1994         BMHeader *h;
1995         BMesh *bm = em->bm;
1996         BMWalker walker;
1997         BMIter iter;
1998         int walktype = 0, itertype = 0, flushtype = 0;
1999         short mask_vert=0, mask_edge=0, mask_loop=0, mask_face=0;
2000
2001         /* No active element from which to start - nothing to do */
2002         if(h_act==NULL) {
2003                 return;
2004         }
2005
2006         /* Determine which type of iter, walker, and select flush to use
2007            based on type of the elements being deselected */
2008         switch (h_act->htype) {
2009         case BM_VERT:
2010                 itertype = BM_VERTS_OF_MESH;
2011                 walktype = BMW_CONNECTED_VERTEX;
2012                 flushtype = SCE_SELECT_VERTEX;
2013                 mask_vert = BM_SELECT;
2014                 break;
2015         case BM_EDGE:
2016                 itertype = BM_EDGES_OF_MESH;
2017                 walktype = BMW_SHELL;
2018                 flushtype = SCE_SELECT_EDGE;
2019                 mask_edge = BM_SELECT;
2020                 break;
2021         case BM_FACE:
2022                 itertype = BM_FACES_OF_MESH;
2023                 walktype = BMW_ISLAND;
2024                 flushtype = SCE_SELECT_FACE;
2025                 mask_face = BM_SELECT;
2026                 break;
2027         }
2028
2029         /* Walker restrictions uses BMO flags, not header flags,
2030            so transfer BM_SELECT from HFlags onto a BMO flag layer. */
2031         BMO_push(bm, NULL);
2032         BM_ITER(h, &iter, bm, itertype, NULL) {
2033                 if (BM_TestHFlag(h, BM_SELECT)) {
2034                         BMO_SetFlag(bm, h, BM_SELECT);
2035                 }
2036         }
2037
2038         /* Walk over selected elements starting at active */
2039         BMW_Init(&walker, bm, walktype,  mask_vert,mask_edge,mask_loop,mask_face,  BMW_NIL_LAY);
2040         BLI_assert(walker.order == BMW_BREADTH_FIRST);
2041         for (h = BMW_Begin(&walker, h_act); h != NULL; h = BMW_Step(&walker)) {
2042                 /* Deselect elements that aren't at "nth" depth from active */
2043                 if ((offset + BMW_CurrentDepth(&walker)) % nth) {
2044                         BM_Select(bm, h, 0);
2045                 }
2046         }
2047         BMW_End(&walker);
2048
2049         BMO_pop(bm);
2050
2051         /* Flush selection up */
2052         EDBM_select_flush(em, flushtype);
2053 }
2054
2055 static void deselect_nth_active(BMEditMesh *em, BMVert **v_p, BMEdge **e_p, BMFace **f_p)
2056 {
2057         BMVert *v;
2058         BMEdge *e;
2059         BMFace *f;
2060         BMIter iter;
2061         BMEditSelection *ese;
2062
2063         *v_p= NULL;
2064         *e_p= NULL;
2065         *f_p= NULL;
2066
2067         EDBM_selectmode_flush(em);
2068         ese= (BMEditSelection*)em->bm->selected.last;
2069
2070         if(ese) {
2071                 switch(ese->htype) {
2072                 case BM_VERT:
2073                         *v_p= (BMVert *)ese->data;
2074                         return;
2075                 case BM_EDGE:
2076                         *e_p= (BMEdge *)ese->data;
2077                         return;
2078                 case BM_FACE:
2079                         *f_p= (BMFace *)ese->data;
2080                         return;
2081                 }
2082         }
2083
2084         if(em->selectmode & SCE_SELECT_VERTEX) {
2085                 BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2086                         if (BM_TestHFlag(v, BM_SELECT)) {
2087                                 *v_p = v;
2088                                 return;
2089                         }
2090                 }
2091         }
2092         else if(em->selectmode & SCE_SELECT_EDGE) {
2093                 BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2094                         if (BM_TestHFlag(e, BM_SELECT)) {
2095                                 *e_p = e;
2096                                 return;
2097                         }
2098                 }
2099         }
2100         else if(em->selectmode & SCE_SELECT_FACE) {
2101                 f= BM_get_actFace(em->bm, 1);
2102                 if(f) {
2103                         *f_p= f;
2104                         return;
2105                 }
2106         }
2107 }
2108
2109 static int EM_deselect_nth(BMEditMesh *em, int nth, int offset)
2110 {
2111         BMVert *v;
2112         BMEdge *e;
2113         BMFace *f;
2114
2115         deselect_nth_active(em, &v, &e, &f);
2116
2117         if (v) {
2118                 walker_deselect_nth(em, nth, offset, &v->head);
2119                 return 1;
2120         }
2121         else if(e) {
2122                 walker_deselect_nth(em, nth, offset, &e->head);
2123                 return 1;
2124         }
2125         else if(f) {
2126                 walker_deselect_nth(em, nth, offset, &f->head);
2127                 return 1;
2128         }
2129
2130         return 0;
2131 }
2132
2133 static int mesh_select_nth_exec(bContext *C, wmOperator *op)
2134 {
2135         Object *obedit= CTX_data_edit_object(C);
2136         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2137         int nth= RNA_int_get(op->ptr, "nth");
2138         int offset= RNA_int_get(op->ptr, "offset");
2139
2140         offset = MIN2(nth, offset);
2141
2142         if(EM_deselect_nth(em, nth, offset) == 0) {
2143                 BKE_report(op->reports, RPT_ERROR, "Mesh has no active vert/edge/face");
2144                 return OPERATOR_CANCELLED;
2145         }
2146
2147         DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
2148         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
2149
2150         return OPERATOR_FINISHED;
2151 }
2152
2153
2154 void MESH_OT_select_nth(wmOperatorType *ot)
2155 {
2156         /* identifiers */
2157         ot->name= "Select Nth";
2158         ot->description= "";
2159         ot->idname= "MESH_OT_select_nth";
2160
2161         /* api callbacks */
2162         ot->exec= mesh_select_nth_exec;
2163         ot->poll= ED_operator_editmesh;
2164
2165         /* flags */
2166         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2167
2168         RNA_def_int(ot->srna, "nth", 2, 2, 100, "Nth Selection", "", 1, INT_MAX);
2169         RNA_def_int(ot->srna, "offset", 0, 0, 100, "Offset", "", 0, INT_MAX);
2170 }
2171
2172 void em_setup_viewcontext(bContext *C, ViewContext *vc)
2173 {
2174         view3d_set_viewcontext(C, vc);
2175         
2176         if(vc->obedit) {
2177                 Mesh *me= vc->obedit->data;
2178                 vc->em= me->edit_btmesh;
2179         }
2180 }
2181
2182 /* poll call for mesh operators requiring a view3d context */
2183 int EM_view3d_poll(bContext *C)
2184 {
2185         if(ED_operator_editmesh(C) && ED_operator_view3d_active(C))
2186                 return 1;
2187         return 0;
2188 }
2189
2190
2191 static int select_sharp_edges_exec(bContext *C, wmOperator *op)
2192 {
2193         /* Find edges that have exactly two neighboring faces,
2194         * check the angle between those faces, and if angle is
2195         * small enough, select the edge
2196         */
2197         Object *obedit= CTX_data_edit_object(C);
2198         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2199         BMIter iter;
2200         BMEdge *e;
2201         BMLoop *l1, *l2;
2202         float sharp = RNA_float_get(op->ptr, "sharpness"), angle;
2203
2204         sharp = DEG2RADF(sharp);
2205
2206         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2207                 if (BM_TestHFlag(e, BM_HIDDEN) || !e->l)
2208                         continue;
2209
2210                 l1 = e->l;
2211                 l2 = l1->radial_next;
2212
2213                 if (l1 == l2)
2214                         continue;
2215
2216                 /* edge has exactly two neighboring faces, check angle */
2217                 angle = saacos(l1->f->no[0]*l2->f->no[0]+l1->f->no[1]*l2->f->no[1]+l1->f->no[2]*l2->f->no[2]);
2218
2219                 if (fabsf(angle) < sharp) {
2220                         BM_Select(em->bm, e, 1);
2221                 }
2222
2223         }
2224
2225         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2226
2227         return OPERATOR_FINISHED;
2228 }
2229
2230 void MESH_OT_edges_select_sharp(wmOperatorType *ot)
2231 {
2232         /* identifiers */
2233         ot->name= "Select Sharp Edges";
2234         ot->description= "Marked selected edges as sharp";
2235         ot->idname= "MESH_OT_edges_select_sharp";
2236         
2237         /* api callbacks */
2238         ot->exec= select_sharp_edges_exec;
2239         ot->poll= ED_operator_editmesh;
2240         
2241         /* flags */
2242         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2243         
2244         /* props */
2245         RNA_def_float(ot->srna, "sharpness", 1.0f, 0.01f, FLT_MAX, "sharpness", "", 1.0f, 180.0f);
2246 }
2247
2248 static int select_linked_flat_faces_exec(bContext *C, wmOperator *op)
2249 {
2250         Object *obedit= CTX_data_edit_object(C);
2251         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2252         BMIter iter, liter, liter2;
2253         BMFace *f, **stack = NULL;
2254         BLI_array_declare(stack);
2255         BMLoop *l, *l2;
2256         float sharp = RNA_float_get(op->ptr, "sharpness");
2257         int i;
2258
2259         sharp = (sharp * M_PI) / 180.0;
2260
2261         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2262                 BM_ClearHFlag(f, BM_TMP_TAG);
2263         }
2264
2265         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2266                 if (BM_TestHFlag(f, BM_HIDDEN) || !BM_TestHFlag(f, BM_SELECT) || BM_TestHFlag(f, BM_TMP_TAG))
2267                         continue;
2268
2269                 BLI_array_empty(stack);
2270                 i = 1;
2271
2272                 BLI_array_growone(stack);
2273                 stack[i-1] = f;
2274
2275                 while (i) {
2276                         f = stack[i-1];
2277                         i--;
2278
2279                         BM_Select(em->bm, f, 1);
2280
2281                         BM_SetHFlag(f, BM_TMP_TAG);
2282
2283                         BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, f) {
2284                                 BM_ITER(l2, &liter2, em->bm, BM_LOOPS_OF_LOOP, l) {
2285                                         float angle;
2286
2287                                         if (BM_TestHFlag(l2->f, BM_TMP_TAG) || BM_TestHFlag(l2->f, BM_HIDDEN))
2288                                                 continue;
2289
2290                                         /* edge has exactly two neighboring faces, check angle */
2291                                         angle = saacos(f->no[0]*l2->f->no[0]+f->no[1]*l2->f->no[1]+f->no[2]*l2->f->no[2]);
2292
2293                                         /* invalidate: edge too sharp */
2294                                         if (fabs(angle) < sharp) {
2295                                                 BLI_array_growone(stack);
2296                                                 stack[i] = l2->f;
2297                                                 i++;
2298                                         }
2299                                 }
2300                         }
2301                 }
2302         }
2303
2304         BLI_array_free(stack);
2305
2306         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2307
2308         return OPERATOR_FINISHED;
2309 }
2310
2311 void MESH_OT_faces_select_linked_flat(wmOperatorType *ot)
2312 {
2313         /* identifiers */
2314         ot->name= "Select Linked Flat Faces";
2315         ot->description= "Select linked faces by angle";
2316         ot->idname= "MESH_OT_faces_select_linked_flat";
2317         
2318         /* api callbacks */
2319         ot->exec= select_linked_flat_faces_exec;
2320         ot->poll= ED_operator_editmesh;
2321         
2322         /* flags */
2323         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2324         
2325         /* props */
2326         RNA_def_float(ot->srna, "sharpness", 1.0f, 0.01f, FLT_MAX, "sharpness", "", 1.0f, 180.0f);
2327 }
2328
2329 static int select_non_manifold_exec(bContext *C, wmOperator *op)
2330 {
2331         Object *obedit= CTX_data_edit_object(C);
2332         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2333         BMVert *v;
2334         BMEdge *e;
2335         BMIter iter;
2336
2337         /* Selects isolated verts, and edges that do not have 2 neighboring
2338          * faces
2339          */
2340         
2341         if(em->selectmode==SCE_SELECT_FACE) {
2342                 BKE_report(op->reports, RPT_ERROR, "Doesn't work in face selection mode");
2343                 return OPERATOR_CANCELLED;
2344         }
2345         
2346         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2347                 if (!BM_TestHFlag(em->bm, BM_HIDDEN) && BM_Nonmanifold_Vert(em->bm, v))
2348                         BM_Select(em->bm, v, 1);
2349         }
2350         
2351         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2352                 if (!BM_TestHFlag(em->bm, BM_HIDDEN) && BM_Edge_FaceCount(e) != 2)
2353                         BM_Select(em->bm, e, 1);
2354         }
2355
2356         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2357
2358         return OPERATOR_FINISHED;       
2359 }
2360
2361 void MESH_OT_select_non_manifold(wmOperatorType *ot)
2362 {
2363         /* identifiers */
2364         ot->name= "Select Non Manifold";
2365         ot->description= "Select all non-manifold vertices or edges";
2366         ot->idname= "MESH_OT_select_non_manifold";
2367         
2368         /* api callbacks */
2369         ot->exec= select_non_manifold_exec;
2370         ot->poll= ED_operator_editmesh;
2371         
2372         /* flags */
2373         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2374 }
2375
2376 static int mesh_select_random_exec(bContext *C, wmOperator *op)
2377 {
2378         Object *obedit= CTX_data_edit_object(C);
2379         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2380         BMVert *eve;
2381         BMEdge *eed;
2382         BMFace *efa;
2383         BMIter iter;
2384         float randfac =  RNA_float_get(op->ptr, "percent")/100.0f;
2385
2386         BLI_srand( BLI_rand() ); /* random seed */
2387         
2388         if(!RNA_boolean_get(op->ptr, "extend"))
2389                 EDBM_clear_flag_all(em, BM_SELECT);
2390
2391         if(em->selectmode & SCE_SELECT_VERTEX) {
2392                 BM_ITER(eve, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2393                         if (!BM_TestHFlag(eve, BM_HIDDEN) && BLI_frand() < randfac)
2394                                 BM_Select(em->bm, eve, 1);
2395                 }
2396                 EDBM_selectmode_flush(em);
2397         }
2398         else if(em->selectmode & SCE_SELECT_EDGE) {
2399                 BM_ITER(eed, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2400                         if (!BM_TestHFlag(eed, BM_HIDDEN) && BLI_frand() < randfac)
2401                                 BM_Select(em->bm, eed, 1);
2402                 }
2403                 EDBM_selectmode_flush(em);
2404         }
2405         else {
2406                 BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2407                         if (!BM_TestHFlag(efa, BM_HIDDEN) && BLI_frand() < randfac)
2408                                 BM_Select(em->bm, efa, 1);
2409                 }
2410                 EDBM_selectmode_flush(em);
2411         }
2412         
2413         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2414         
2415         return OPERATOR_FINISHED;       
2416 }
2417
2418 void MESH_OT_select_random(wmOperatorType *ot)
2419 {
2420         /* identifiers */
2421         ot->name= "Select Random";
2422         ot->description= "Randomly select vertices";
2423         ot->idname= "MESH_OT_select_random";
2424
2425         /* api callbacks */
2426         ot->exec= mesh_select_random_exec;
2427         ot->poll= ED_operator_editmesh;
2428
2429         /* flags */
2430         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2431         
2432         /* props */
2433         RNA_def_float_percentage(ot->srna, "percent", 50.f, 0.0f, 100.0f, "Percent", "Percentage of elements to select randomly", 0.f, 100.0f);
2434         RNA_def_boolean(ot->srna, "extend", 0, "Extend Selection", "Extend selection instead of deselecting everything first");
2435 }
2436
2437 static int select_next_loop(bContext *C, wmOperator *UNUSED(op))
2438 {
2439         Object *obedit= CTX_data_edit_object(C);
2440         BMEditMesh *em= (((Mesh *)obedit->data))->edit_btmesh;
2441         BMFace *f;
2442         BMVert *v;
2443         BMIter iter;
2444         
2445         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2446                 BM_ClearHFlag(v, BM_TMP_TAG);
2447         }
2448         
2449         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2450                 BMLoop *l;
2451                 BMIter liter;
2452                 
2453                 BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, f) {
2454                         if (BM_TestHFlag(l->v, BM_SELECT) && !BM_TestHFlag(l->v, BM_HIDDEN)) {
2455                                 BM_SetHFlag(l->next->v, BM_TMP_TAG);
2456                                 BM_Select(em->bm, l->v, 0);
2457                         }
2458                 }
2459         }
2460
2461         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2462                 if (BM_TestHFlag(v, BM_TMP_TAG)) {
2463                         BM_Select(em->bm, v, 1);
2464                 }
2465         }
2466
2467         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
2468         return OPERATOR_FINISHED;
2469 }
2470
2471 void MESH_OT_select_next_loop(wmOperatorType *ot)
2472 {
2473         /* identifiers */
2474         ot->name= "Select Next Loop";
2475         ot->idname= "MESH_OT_select_next_loop";
2476         ot->description= "";
2477
2478         /* api callbacks */
2479         ot->exec= select_next_loop;
2480         ot->poll= ED_operator_editmesh;
2481         
2482         /* flags */
2483         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2484 }
2485
2486
2487 static int region_to_loop(bContext *C, wmOperator *UNUSED(op))
2488 {
2489         Object *obedit = CTX_data_edit_object(C);
2490         BMEditMesh *em = ((Mesh*)obedit->data)->edit_btmesh;
2491         BMFace *f;
2492         BMEdge *e;
2493         BMIter iter;
2494         ViewContext vc;
2495         
2496         em_setup_viewcontext(C, &vc);
2497         
2498         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2499                 BM_ClearHFlag(e, BM_TMP_TAG);
2500         }
2501
2502         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2503                 BMLoop *l1, *l2;
2504                 BMIter liter1, liter2;
2505                 
2506                 BM_ITER(l1, &liter1, em->bm, BM_LOOPS_OF_FACE, f) {
2507                         int tot=0, totsel=0;
2508                         
2509                         BM_ITER(l2, &liter2, em->bm, BM_LOOPS_OF_EDGE, l1->e) {
2510                                 tot++;
2511                                 totsel += BM_TestHFlag(l2->f, BM_SELECT) != 0;
2512                         }
2513                         
2514                         if ((tot != totsel && totsel > 0) || (totsel == 1 && tot == 1))
2515                                 BM_SetHFlag(l1->e, BM_TMP_TAG);
2516                 }
2517         }
2518
2519         EDBM_clear_flag_all(em, BM_SELECT);
2520         
2521         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2522                 if (BM_TestHFlag(e, BM_TMP_TAG) && !BM_TestHFlag(e, BM_HIDDEN))
2523                         BM_Select_Edge(em->bm, e, 1);
2524         }
2525
2526         /* If in face-only select mode, switch to edge select mode so that
2527            an edge-only selection is not inconsistent state */
2528         if (em->selectmode == SCE_SELECT_FACE) {
2529                 em->selectmode = SCE_SELECT_EDGE;
2530                 EDBM_selectmode_set(em);
2531                 EDBM_selectmode_to_scene(C);
2532         }
2533
2534         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2535
2536         return OPERATOR_FINISHED;
2537 }
2538
2539 void MESH_OT_region_to_loop(wmOperatorType *ot)
2540 {
2541         /* identifiers */
2542         ot->name= "Select Boundary Loop";
2543         ot->idname= "MESH_OT_region_to_loop";
2544
2545         /* api callbacks */
2546         ot->exec= region_to_loop;
2547         ot->poll= ED_operator_editmesh;
2548
2549         /* flags */
2550         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2551 }
2552
2553 static int loop_find_region(BMEditMesh *em, BMLoop *l, int flag, 
2554         SmallHash *fhash, BMFace ***region_out)
2555 {
2556         BLI_array_declare(region);
2557         BLI_array_declare(stack);
2558         BMFace **region = NULL, *f;
2559         BMFace **stack = NULL;
2560         
2561         BLI_array_append(stack, l->f);
2562         BLI_smallhash_insert(fhash, (uintptr_t)l->f, NULL);
2563         
2564         while (BLI_array_count(stack) > 0) {
2565                 BMIter liter1, liter2;
2566                 BMLoop *l1, *l2;
2567                 
2568                 f = BLI_array_pop(stack);
2569                 BLI_array_append(region, f);
2570                 
2571                 BM_ITER(l1, &liter1, em->bm, BM_LOOPS_OF_FACE, f) {
2572                         if (BM_TestHFlag(l1->e, flag))
2573                                 continue;
2574                         
2575                         BM_ITER(l2, &liter2, em->bm, BM_LOOPS_OF_EDGE, l1->e) {
2576                                 if (BLI_smallhash_haskey(fhash, (uintptr_t)l2->f))
2577                                         continue;
2578                                 
2579                                 BLI_array_append(stack, l2->f);
2580                                 BLI_smallhash_insert(fhash, (uintptr_t)l2->f, NULL);
2581                         }
2582                 }
2583         }
2584         
2585         BLI_array_free(stack);
2586         
2587         *region_out = region;
2588         return BLI_array_count(region);
2589 }
2590
2591 static int verg_radial(const void *va, const void *vb)
2592 {
2593         BMEdge *e1 = *((void**)va);
2594         BMEdge *e2 = *((void**)vb);
2595         int a, b;
2596         
2597         a = BM_Edge_FaceCount(e1);
2598         b = BM_Edge_FaceCount(e2);
2599         
2600         if (a > b) return -1;
2601         if (a == b) return 0;
2602         if (a < b) return 1;
2603         
2604         return -1;
2605 }
2606
2607 static int loop_find_regions(BMEditMesh *em, int selbigger)
2608 {
2609         SmallHash visithash;
2610         BMIter iter;
2611         BMEdge *e, **edges=NULL;
2612         BLI_array_declare(edges);
2613         BMFace *f;
2614         int count = 0, i;
2615         
2616         BLI_smallhash_init(&visithash);
2617         
2618         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2619                 BM_ClearHFlag(f, BM_TMP_TAG);
2620         }
2621
2622         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2623                 if (BM_TestHFlag(e, BM_SELECT)) {
2624                         BLI_array_append(edges, e);
2625                         BM_SetHFlag(e, BM_TMP_TAG);
2626                 } else {
2627                         BM_ClearHFlag(e, BM_TMP_TAG);
2628                 }
2629         }
2630         
2631         /*sort edges by radial cycle length*/
2632         qsort(edges,  BLI_array_count(edges), sizeof(void*), verg_radial);
2633         
2634         for (i=0; i<BLI_array_count(edges); i++) {
2635                 BMIter liter;
2636                 BMLoop *l;
2637                 BMFace **region=NULL, **r;
2638                 int c, tot=0;
2639                 
2640                 e = edges[i];
2641                 
2642                 if (!BM_TestHFlag(e, BM_TMP_TAG))
2643                         continue;
2644                 
2645                 BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_EDGE, e) {
2646                         if (BLI_smallhash_haskey(&visithash, (uintptr_t)l->f))
2647                                 continue;
2648                                                 
2649                         c = loop_find_region(em, l, BM_SELECT, &visithash, &r);
2650
2651                         if (!region || (selbigger ? c >= tot : c < tot)) {
2652                                 /* this region is the best seen so far */
2653                                 tot = c;
2654                                 if (region) {
2655                                         /* free the previous best */
2656                                         MEM_freeN(region);
2657                                 }
2658                                 /* track the current region as the new best */
2659                                 region = r;
2660                         }
2661                         else {
2662                                 /* this region is not as good as best so far, just free it */
2663                                 MEM_freeN(r);
2664                         }
2665                 }
2666                 
2667                 if (region) {
2668                         int j;
2669                         
2670                         for (j=0; j<tot; j++) {
2671                                 BM_SetHFlag(region[j], BM_TMP_TAG);
2672                                 BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, region[j]) {
2673                                         BM_ClearHFlag(l->e, BM_TMP_TAG);
2674                                 }
2675                         }
2676                         
2677                         count += tot;
2678                         
2679                         MEM_freeN(region);
2680                 }
2681         }
2682         
2683         BLI_array_free(edges);
2684         BLI_smallhash_release(&visithash);
2685         
2686         return count;
2687 }
2688
2689 static int loop_to_region(bContext *C, wmOperator *op)
2690 {
2691         Object *obedit = CTX_data_edit_object(C);
2692         BMEditMesh *em = ((Mesh*)obedit->data)->edit_btmesh;
2693         BMIter iter;
2694         BMFace *f;
2695         int selbigger = RNA_boolean_get(op->ptr, "select_bigger");
2696         int a, b;
2697
2698         /*find the set of regions with smallest number of total faces*/
2699         a = loop_find_regions(em, selbigger);
2700         b = loop_find_regions(em, !selbigger);
2701         
2702         if ((a <= b) ^ selbigger) {
2703                 loop_find_regions(em, selbigger);
2704         }
2705         
2706         EDBM_clear_flag_all(em, BM_SELECT);
2707         
2708         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2709                 if (BM_TestHFlag(f, BM_TMP_TAG) && !BM_TestHFlag(f, BM_HIDDEN)) {
2710                         BM_Select_Face(em->bm, f, 1);
2711                 }
2712         }
2713         
2714         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2715         return OPERATOR_FINISHED;
2716 }
2717
2718 void MESH_OT_loop_to_region(wmOperatorType *ot)
2719 {
2720         /* identifiers */
2721         ot->name= "Select Loop Inner-Region";
2722         ot->idname= "MESH_OT_loop_to_region";
2723
2724         /* api callbacks */
2725         ot->exec= loop_to_region;
2726         ot->poll= ED_operator_editmesh;
2727
2728         /* flags */
2729         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2730         
2731         RNA_def_boolean(ot->srna, "select_bigger", 0, "Select Bigger", "Select bigger regions instead of smaller ones");
2732 }