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