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