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