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