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