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