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