c20c3e50e677c81eb7354a60e77d2e1f446ba192
[blender.git] / source / blender / editors / mesh / editmesh_select.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2004 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/mesh/editmesh_select.c
29  *  \ingroup edmesh
30  */
31
32 #include "MEM_guardedalloc.h"
33
34 #include "BLI_blenlib.h"
35 #include "BLI_math.h"
36 #include "BLI_rand.h"
37 #include "BLI_array.h"
38 #include "BLI_smallhash.h"
39 #include "BLI_heap.h"
40
41 #include "BKE_context.h"
42 #include "BKE_displist.h"
43 #include "BKE_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_MESH (v1, &iter, em->bm, BM_VERTS_OF_MESH) {
79                 if (!BM_elem_flag_test(v1, BM_ELEM_SELECT) || BM_elem_flag_test(v1, BM_ELEM_HIDDEN)) {
80                         BM_elem_flag_disable(v1, BM_ELEM_TAG);
81                 }
82                 else {
83                         BM_elem_flag_enable(v1, BM_ELEM_TAG);
84                 }
85         }
86
87         EDBM_verts_mirror_cache_begin(em, TRUE);
88
89         if (!extend)
90                 EDBM_flag_disable_all(em, BM_ELEM_SELECT);
91
92         BM_ITER_MESH (v1, &iter, em->bm, BM_VERTS_OF_MESH) {
93                 if (!BM_elem_flag_test(v1, BM_ELEM_TAG) || BM_elem_flag_test(v1, BM_ELEM_HIDDEN))
94                         continue;
95
96                 v2 = EDBM_verts_mirror_get(em, v1);
97                 if (v2 && !BM_elem_flag_test(v2, BM_ELEM_HIDDEN)) {
98                         BM_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_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
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_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
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_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
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_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
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_MESH (eve, &iter, em->bm, BM_VERTS_OF_MESH) {
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_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
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_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
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_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1706                 if (BM_elem_flag_test(efa, BM_ELEM_HIDDEN))
1707                         continue;
1708
1709
1710                 ok = TRUE;
1711                 BM_ITER_ELEM (eed, &eiter, efa, BM_EDGES_OF_FACE) {
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_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
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_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
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_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
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_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
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_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
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_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
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_MESH (ele, &iter, bm, itertype) {
2048                 if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
2049                         /* BMESH_TODO, don't use 'BM_ELEM_SELECT' here, its a HFLAG only! */
2050                         BMO_elem_flag_enable(bm, (BMElemF *)ele, BM_ELEM_SELECT);
2051                 }
2052         }
2053
2054         /* Walk over selected elements starting at active */
2055         BMW_init(&walker, bm, walktype,
2056                  mask_vert, mask_edge, mask_face,
2057                  BMW_FLAG_NOP, /* don't use BMW_FLAG_TEST_HIDDEN here since we want to desel all */
2058                  BMW_NIL_LAY);
2059
2060         BLI_assert(walker.order == BMW_BREADTH_FIRST);
2061         for (ele = BMW_begin(&walker, h_act); ele != NULL; ele = BMW_step(&walker)) {
2062                 /* Deselect elements that aren't at "nth" depth from active */
2063                 if ((offset + BMW_current_depth(&walker)) % nth) {
2064                         BM_elem_select_set(bm, ele, FALSE);
2065                 }
2066         }
2067         BMW_end(&walker);
2068
2069         BMO_pop(bm);
2070
2071         /* Flush selection up */
2072         EDBM_selectmode_flush_ex(em, flushtype);
2073 }
2074
2075 static void deselect_nth_active(BMEditMesh *em, BMVert **r_eve, BMEdge **r_eed, BMFace **r_efa)
2076 {
2077         BMVert *v;
2078         BMEdge *e;
2079         BMFace *f;
2080         BMIter iter;
2081         BMEditSelection *ese;
2082
2083         *r_eve = NULL;
2084         *r_eed = NULL;
2085         *r_efa = NULL;
2086
2087         EDBM_selectmode_flush(em);
2088         ese = (BMEditSelection *)em->bm->selected.last;
2089
2090         if (ese) {
2091                 switch (ese->htype) {
2092                         case BM_VERT:
2093                                 *r_eve = (BMVert *)ese->ele;
2094                                 return;
2095                         case BM_EDGE:
2096                                 *r_eed = (BMEdge *)ese->ele;
2097                                 return;
2098                         case BM_FACE:
2099                                 *r_efa = (BMFace *)ese->ele;
2100                                 return;
2101                 }
2102         }
2103
2104         if (em->selectmode & SCE_SELECT_VERTEX) {
2105                 BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
2106                         if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
2107                                 *r_eve = v;
2108                                 return;
2109                         }
2110                 }
2111         }
2112         else if (em->selectmode & SCE_SELECT_EDGE) {
2113                 BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2114                         if (BM_elem_flag_test(e, BM_ELEM_SELECT)) {
2115                                 *r_eed = e;
2116                                 return;
2117                         }
2118                 }
2119         }
2120         else if (em->selectmode & SCE_SELECT_FACE) {
2121                 f = BM_active_face_get(em->bm, TRUE);
2122                 if (f) {
2123                         *r_efa = f;
2124                         return;
2125                 }
2126         }
2127 }
2128
2129 static int edbm_deselect_nth(BMEditMesh *em, int nth, int offset)
2130 {
2131         BMVert *v;
2132         BMEdge *e;
2133         BMFace *f;
2134
2135         deselect_nth_active(em, &v, &e, &f);
2136
2137         if (v) {
2138                 walker_deselect_nth(em, nth, offset, &v->head);
2139                 return 1;
2140         }
2141         else if (e) {
2142                 walker_deselect_nth(em, nth, offset, &e->head);
2143                 return 1;
2144         }
2145         else if (f) {
2146                 walker_deselect_nth(em, nth, offset, &f->head);
2147                 return 1;
2148         }
2149
2150         return 0;
2151 }
2152
2153 static int edbm_select_nth_exec(bContext *C, wmOperator *op)
2154 {
2155         Object *obedit = CTX_data_edit_object(C);
2156         BMEditMesh *em = BMEdit_FromObject(obedit);
2157         int nth = RNA_int_get(op->ptr, "nth");
2158         int offset = RNA_int_get(op->ptr, "offset");
2159
2160         offset = MIN2(nth, offset);
2161
2162         if (edbm_deselect_nth(em, nth, offset) == 0) {
2163                 BKE_report(op->reports, RPT_ERROR, "Mesh has no active vert/edge/face");
2164                 return OPERATOR_CANCELLED;
2165         }
2166
2167         EDBM_update_generic(C, em, FALSE);
2168
2169         return OPERATOR_FINISHED;
2170 }
2171
2172
2173 void MESH_OT_select_nth(wmOperatorType *ot)
2174 {
2175         /* identifiers */
2176         ot->name = "Select Nth";
2177         ot->idname = "MESH_OT_select_nth";
2178         ot->description = "Select every Nth element starting from a selected vertex, edge or face";
2179
2180         /* api callbacks */
2181         ot->exec = edbm_select_nth_exec;
2182         ot->poll = ED_operator_editmesh;
2183
2184         /* flags */
2185         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2186
2187         RNA_def_int(ot->srna, "nth", 2, 2, 100, "Nth Selection", "", 1, INT_MAX);
2188         RNA_def_int(ot->srna, "offset", 0, 0, 100, "Offset", "", 0, INT_MAX);
2189 }
2190
2191 void em_setup_viewcontext(bContext *C, ViewContext *vc)
2192 {
2193         view3d_set_viewcontext(C, vc);
2194         
2195         if (vc->obedit) {
2196                 Mesh *me = vc->obedit->data;
2197                 vc->em = me->edit_btmesh;
2198         }
2199 }
2200
2201 /* poll call for mesh operators requiring a view3d context */
2202 int EM_view3d_poll(bContext *C)
2203 {
2204         if (ED_operator_editmesh(C) && ED_operator_view3d_active(C))
2205                 return 1;
2206
2207         return 0;
2208 }
2209
2210
2211 static int edbm_select_sharp_edges_exec(bContext *C, wmOperator *op)
2212 {
2213         /* Find edges that have exactly two neighboring faces,
2214          * check the angle between those faces, and if angle is
2215          * small enough, select the edge
2216          */
2217         Object *obedit = CTX_data_edit_object(C);
2218         BMEditMesh *em = BMEdit_FromObject(obedit);
2219         BMIter iter;
2220         BMEdge *e;
2221         BMLoop *l1, *l2;
2222         float sharp = RNA_float_get(op->ptr, "sharpness"), angle;
2223
2224         sharp = DEG2RADF(sharp);
2225
2226         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2227                 if (BM_elem_flag_test(e, BM_ELEM_HIDDEN) || !e->l)
2228                         continue;
2229
2230                 l1 = e->l;
2231                 l2 = l1->radial_next;
2232
2233                 if (l1 == l2)
2234                         continue;
2235
2236                 /* edge has exactly two neighboring faces, check angle */
2237                 angle = angle_normalized_v3v3(l1->f->no, l2->f->no);
2238
2239                 if (fabsf(angle) > sharp) {
2240                         BM_elem_select_set(em->bm, e, TRUE);
2241                 }
2242
2243         }
2244
2245         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2246
2247         return OPERATOR_FINISHED;
2248 }
2249
2250 void MESH_OT_edges_select_sharp(wmOperatorType *ot)
2251 {
2252         /* identifiers */
2253         ot->name = "Select Sharp Edges";
2254         ot->description = "Marked selected edges as sharp";
2255         ot->idname = "MESH_OT_edges_select_sharp";
2256         
2257         /* api callbacks */
2258         ot->exec = edbm_select_sharp_edges_exec;
2259         ot->poll = ED_operator_editmesh;
2260         
2261         /* flags */
2262         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2263         
2264         /* props */
2265         RNA_def_float(ot->srna, "sharpness", 1.0f, 0.01f, FLT_MAX, "sharpness", "", 1.0f, 180.0f);
2266 }
2267
2268 static int edbm_select_linked_flat_faces_exec(bContext *C, wmOperator *op)
2269 {
2270         Object *obedit = CTX_data_edit_object(C);
2271         BMEditMesh *em = BMEdit_FromObject(obedit);
2272         BMIter iter, liter, liter2;
2273         BMFace *f, **stack = NULL;
2274         BLI_array_declare(stack);
2275         BMLoop *l, *l2;
2276         float sharp = RNA_float_get(op->ptr, "sharpness");
2277         int i;
2278
2279         sharp = (sharp * M_PI) / 180.0;
2280
2281         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2282                 BM_elem_flag_disable(f, BM_ELEM_TAG);
2283         }
2284
2285         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2286                 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))
2287                         continue;
2288
2289                 BLI_array_empty(stack);
2290                 i = 1;
2291
2292                 BLI_array_growone(stack);
2293                 stack[i - 1] = f;
2294
2295                 while (i) {
2296                         f = stack[i - 1];
2297                         i--;
2298
2299                         BM_elem_select_set(em->bm, f, TRUE);
2300
2301                         BM_elem_flag_enable(f, BM_ELEM_TAG);
2302
2303                         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
2304                                 BM_ITER_ELEM (l2, &liter2, l, BM_LOOPS_OF_LOOP) {
2305                                         float angle;
2306
2307                                         if (BM_elem_flag_test(l2->f, BM_ELEM_TAG) || BM_elem_flag_test(l2->f, BM_ELEM_HIDDEN))
2308                                                 continue;
2309
2310                                         /* edge has exactly two neighboring faces, check angle */
2311                                         angle = angle_normalized_v3v3(f->no, l2->f->no);
2312
2313                                         /* invalidate: edge too sharp */
2314                                         if (angle < sharp) {
2315                                                 BLI_array_growone(stack);
2316                                                 stack[i] = l2->f;
2317                                                 i++;
2318                                         }
2319                                 }
2320                         }
2321                 }
2322         }
2323
2324         BLI_array_free(stack);
2325
2326         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2327
2328         return OPERATOR_FINISHED;
2329 }
2330
2331 void MESH_OT_faces_select_linked_flat(wmOperatorType *ot)
2332 {
2333         /* identifiers */
2334         ot->name = "Select Linked Flat Faces";
2335         ot->description = "Select linked faces by angle";
2336         ot->idname = "MESH_OT_faces_select_linked_flat";
2337         
2338         /* api callbacks */
2339         ot->exec = edbm_select_linked_flat_faces_exec;
2340         ot->poll = ED_operator_editmesh;
2341         
2342         /* flags */
2343         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2344         
2345         /* props */
2346         RNA_def_float(ot->srna, "sharpness", 1.0f, 0.01f, FLT_MAX, "sharpness", "", 1.0f, 180.0f);
2347 }
2348
2349 static int edbm_select_non_manifold_exec(bContext *C, wmOperator *op)
2350 {
2351         Object *obedit = CTX_data_edit_object(C);
2352         BMEditMesh *em = BMEdit_FromObject(obedit);
2353         BMVert *v;
2354         BMEdge *e;
2355         BMIter iter;
2356
2357         /* Selects isolated verts, and edges that do not have 2 neighboring
2358          * faces
2359          */
2360         
2361         if (em->selectmode == SCE_SELECT_FACE) {
2362                 BKE_report(op->reports, RPT_ERROR, "Doesn't work in face selection mode");
2363                 return OPERATOR_CANCELLED;
2364         }
2365         
2366         BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
2367                 if (!BM_elem_flag_test(v, BM_ELEM_HIDDEN) && !BM_vert_is_manifold(v)) {
2368                         BM_elem_select_set(em->bm, v, TRUE);
2369                 }
2370         }
2371         
2372         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2373                 if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN) && !BM_edge_is_manifold(e)) {
2374                         BM_elem_select_set(em->bm, e, TRUE);
2375                 }
2376         }
2377
2378         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2379
2380         return OPERATOR_FINISHED;
2381 }
2382
2383 void MESH_OT_select_non_manifold(wmOperatorType *ot)
2384 {
2385         /* identifiers */
2386         ot->name = "Select Non Manifold";
2387         ot->description = "Select all non-manifold vertices or edges";
2388         ot->idname = "MESH_OT_select_non_manifold";
2389         
2390         /* api callbacks */
2391         ot->exec = edbm_select_non_manifold_exec;
2392         ot->poll = ED_operator_editmesh;
2393         
2394         /* flags */
2395         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2396 }
2397
2398 static int edbm_select_random_exec(bContext *C, wmOperator *op)
2399 {
2400         Object *obedit = CTX_data_edit_object(C);
2401         BMEditMesh *em = BMEdit_FromObject(obedit);
2402         BMVert *eve;
2403         BMEdge *eed;
2404         BMFace *efa;
2405         BMIter iter;
2406         float randfac =  RNA_float_get(op->ptr, "percent") / 100.0f;
2407
2408         BLI_srand(BLI_rand()); /* random seed */
2409         
2410         if (!RNA_boolean_get(op->ptr, "extend"))
2411                 EDBM_flag_disable_all(em, BM_ELEM_SELECT);
2412
2413         if (em->selectmode & SCE_SELECT_VERTEX) {
2414                 BM_ITER_MESH (eve, &iter, em->bm, BM_VERTS_OF_MESH) {
2415                         if (!BM_elem_flag_test(eve, BM_ELEM_HIDDEN) && BLI_frand() < randfac) {
2416                                 BM_elem_select_set(em->bm, eve, TRUE);
2417                         }
2418                 }
2419                 EDBM_selectmode_flush(em);
2420         }
2421         else if (em->selectmode & SCE_SELECT_EDGE) {
2422                 BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
2423                         if (!BM_elem_flag_test(eed, BM_ELEM_HIDDEN) && BLI_frand() < randfac) {
2424                                 BM_elem_select_set(em->bm, eed, TRUE);
2425                         }
2426                 }
2427                 EDBM_selectmode_flush(em);
2428         }
2429         else {
2430                 BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
2431                         if (!BM_elem_flag_test(efa, BM_ELEM_HIDDEN) && BLI_frand() < randfac) {
2432                                 BM_elem_select_set(em->bm, efa, TRUE);
2433                         }
2434                 }
2435                 EDBM_selectmode_flush(em);
2436         }
2437         
2438         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2439         
2440         return OPERATOR_FINISHED;
2441 }
2442
2443 void MESH_OT_select_random(wmOperatorType *ot)
2444 {
2445         /* identifiers */
2446         ot->name = "Select Random";
2447         ot->description = "Randomly select vertices";
2448         ot->idname = "MESH_OT_select_random";
2449
2450         /* api callbacks */
2451         ot->exec = edbm_select_random_exec;
2452         ot->poll = ED_operator_editmesh;
2453
2454         /* flags */
2455         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2456         
2457         /* props */
2458         RNA_def_float_percentage(ot->srna, "percent", 50.f, 0.0f, 100.0f,
2459                                  "Percent", "Percentage of elements to select randomly", 0.f, 100.0f);
2460         RNA_def_boolean(ot->srna, "extend", 0,
2461                         "Extend Selection", "Extend selection instead of deselecting everything first");
2462 }
2463
2464 static int edbm_select_next_loop_exec(bContext *C, wmOperator *UNUSED(op))
2465 {
2466         Object *obedit = CTX_data_edit_object(C);
2467         BMEditMesh *em = BMEdit_FromObject(obedit);
2468         BMFace *f;
2469         BMVert *v;
2470         BMIter iter;
2471         
2472         BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
2473                 BM_elem_flag_disable(v, BM_ELEM_TAG);
2474         }
2475         
2476         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2477                 BMLoop *l;
2478                 BMIter liter;
2479                 
2480                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
2481                         if (BM_elem_flag_test(l->v, BM_ELEM_SELECT)) {
2482                                 BM_elem_flag_enable(l->next->v, BM_ELEM_TAG);
2483                                 BM_elem_select_set(em->bm, l->v, FALSE);
2484                         }
2485                 }
2486         }
2487
2488         BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
2489                 if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
2490                         BM_elem_select_set(em->bm, v, TRUE);
2491                 }
2492         }
2493
2494         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit);
2495         return OPERATOR_FINISHED;
2496 }
2497
2498 void MESH_OT_select_next_loop(wmOperatorType *ot)
2499 {
2500         /* identifiers */
2501         ot->name = "Select Next Loop";
2502         ot->idname = "MESH_OT_select_next_loop";
2503         ot->description = "Select next edge loop adjacent to a selected loop";
2504
2505         /* api callbacks */
2506         ot->exec = edbm_select_next_loop_exec;
2507         ot->poll = ED_operator_editmesh;
2508         
2509         /* flags */
2510         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2511 }
2512
2513
2514 static int edbm_region_to_loop_exec(bContext *C, wmOperator *UNUSED(op))
2515 {
2516         Object *obedit = CTX_data_edit_object(C);
2517         BMEditMesh *em = BMEdit_FromObject(obedit);
2518         BMFace *f;
2519         BMEdge *e;
2520         BMIter iter;
2521
2522         BM_mesh_elem_hflag_disable_all(em->bm, BM_EDGE, BM_ELEM_TAG, FALSE);
2523
2524         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2525                 BMLoop *l1, *l2;
2526                 BMIter liter1, liter2;
2527                 
2528                 BM_ITER_ELEM (l1, &liter1, f, BM_LOOPS_OF_FACE) {
2529                         int tot = 0, totsel = 0;
2530                         
2531                         BM_ITER_ELEM (l2, &liter2, l1->e, BM_LOOPS_OF_EDGE) {
2532                                 tot++;
2533                                 totsel += BM_elem_flag_test(l2->f, BM_ELEM_SELECT) != 0;
2534                         }
2535                         
2536                         if ((tot != totsel && totsel > 0) || (totsel == 1 && tot == 1))
2537                                 BM_elem_flag_enable(l1->e, BM_ELEM_TAG);
2538                 }
2539         }
2540
2541         EDBM_flag_disable_all(em, BM_ELEM_SELECT);
2542         
2543         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2544                 if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
2545                         BM_edge_select_set(em->bm, e, TRUE);
2546                 }
2547         }
2548
2549         /* If in face-only select mode, switch to edge select mode so that
2550          * an edge-only selection is not inconsistent state */
2551         if (em->selectmode == SCE_SELECT_FACE) {
2552                 em->selectmode = SCE_SELECT_EDGE;
2553                 EDBM_selectmode_set(em);
2554                 EDBM_selectmode_to_scene(C);
2555         }
2556
2557         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2558
2559         return OPERATOR_FINISHED;
2560 }
2561
2562 void MESH_OT_region_to_loop(wmOperatorType *ot)
2563 {
2564         /* identifiers */
2565         ot->name = "Select Boundary Loop";
2566         ot->idname = "MESH_OT_region_to_loop";
2567         ot->description = "Select boundary edges around the selected faces";
2568
2569         /* api callbacks */
2570         ot->exec = edbm_region_to_loop_exec;
2571         ot->poll = ED_operator_editmesh;
2572
2573         /* flags */
2574         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2575 }
2576
2577 static int loop_find_region(BMLoop *l, int flag,
2578                             SmallHash *fhash, BMFace ***region_out)
2579 {
2580         BLI_array_declare(region);
2581         BLI_array_declare(stack);
2582         BMFace **region = NULL;
2583         BMFace **stack = NULL;
2584         BMFace *f;
2585         
2586         BLI_array_append(stack, l->f);
2587         BLI_smallhash_insert(fhash, (uintptr_t)l->f, NULL);
2588         
2589         while (BLI_array_count(stack) > 0) {
2590                 BMIter liter1, liter2;
2591                 BMLoop *l1, *l2;
2592                 
2593                 f = BLI_array_pop(stack);
2594                 BLI_array_append(region, f);
2595                 
2596                 BM_ITER_ELEM (l1, &liter1, f, BM_LOOPS_OF_FACE) {
2597                         if (BM_elem_flag_test(l1->e, flag))
2598                                 continue;
2599                         
2600                         BM_ITER_ELEM (l2, &liter2, l1->e, BM_LOOPS_OF_EDGE) {
2601                                 if (BLI_smallhash_haskey(fhash, (uintptr_t)l2->f))
2602                                         continue;
2603                                 
2604                                 BLI_array_append(stack, l2->f);
2605                                 BLI_smallhash_insert(fhash, (uintptr_t)l2->f, NULL);
2606                         }
2607                 }
2608         }
2609         
2610         BLI_array_free(stack);
2611         
2612         *region_out = region;
2613         return BLI_array_count(region);
2614 }
2615
2616 static int verg_radial(const void *va, const void *vb)
2617 {
2618         BMEdge *e1 = *((void **)va);
2619         BMEdge *e2 = *((void **)vb);
2620         int a, b;
2621         
2622         a = BM_edge_face_count(e1);
2623         b = BM_edge_face_count(e2);
2624         
2625         if (a > b)  return -1;
2626         if (a == b) return  0;
2627         if (a < b)  return  1;
2628         
2629         return -1;
2630 }
2631
2632 static int loop_find_regions(BMEditMesh *em, int selbigger)
2633 {
2634         SmallHash visithash;
2635         BMIter iter;
2636         BMEdge *e, **edges = NULL;
2637         BLI_array_declare(edges);
2638         BMFace *f;
2639         int count = 0, i;
2640         
2641         BLI_smallhash_init(&visithash);
2642         
2643         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2644                 BM_elem_flag_disable(f, BM_ELEM_TAG);
2645         }
2646
2647         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2648                 if (BM_elem_flag_test(e, BM_ELEM_SELECT)) {
2649                         BLI_array_append(edges, e);
2650                         BM_elem_flag_enable(e, BM_ELEM_TAG);
2651                 }
2652                 else {
2653                         BM_elem_flag_disable(e, BM_ELEM_TAG);
2654                 }
2655         }
2656         
2657         /* sort edges by radial cycle length */
2658         qsort(edges,  BLI_array_count(edges), sizeof(void *), verg_radial);
2659         
2660         for (i = 0; i < BLI_array_count(edges); i++) {
2661                 BMIter liter;
2662                 BMLoop *l;
2663                 BMFace **region = NULL, **region_out;
2664                 int c, tot = 0;
2665                 
2666                 e = edges[i];
2667                 
2668                 if (!BM_elem_flag_test(e, BM_ELEM_TAG))
2669                         continue;
2670                 
2671                 BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
2672                         if (BLI_smallhash_haskey(&visithash, (uintptr_t)l->f))
2673                                 continue;
2674                                                 
2675                         c = loop_find_region(l, BM_ELEM_SELECT, &visithash, &region_out);
2676
2677                         if (!region || (selbigger ? c >= tot : c < tot)) {
2678                                 /* this region is the best seen so far */
2679                                 tot = c;
2680                                 if (region) {
2681                                         /* free the previous best */
2682                                         MEM_freeN(region);
2683                                 }
2684                                 /* track the current region as the new best */
2685                                 region = region_out;
2686                         }
2687                         else {
2688                                 /* this region is not as good as best so far, just free it */
2689                                 MEM_freeN(region_out);
2690                         }
2691                 }
2692                 
2693                 if (region) {
2694                         int j;
2695                         
2696                         for (j = 0; j < tot; j++) {
2697                                 BM_elem_flag_enable(region[j], BM_ELEM_TAG);
2698                                 BM_ITER_ELEM (l, &liter, region[j], BM_LOOPS_OF_FACE) {
2699                                         BM_elem_flag_disable(l->e, BM_ELEM_TAG);
2700                                 }
2701                         }
2702                         
2703                         count += tot;
2704                         
2705                         MEM_freeN(region);
2706                 }
2707         }
2708         
2709         BLI_array_free(edges);
2710         BLI_smallhash_release(&visithash);
2711         
2712         return count;
2713 }
2714
2715 static int edbm_loop_to_region_exec(bContext *C, wmOperator *op)
2716 {
2717         Object *obedit = CTX_data_edit_object(C);
2718         BMEditMesh *em = BMEdit_FromObject(obedit);
2719         BMIter iter;
2720         BMFace *f;
2721         int selbigger = RNA_boolean_get(op->ptr, "select_bigger");
2722         int a, b;
2723
2724         /* find the set of regions with smallest number of total faces */
2725         a = loop_find_regions(em, selbigger);
2726         b = loop_find_regions(em, !selbigger);
2727         
2728         if ((a <= b) ^ selbigger) {
2729                 loop_find_regions(em, selbigger);
2730         }
2731         
2732         EDBM_flag_disable_all(em, BM_ELEM_SELECT);
2733         
2734         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2735                 if (BM_elem_flag_test(f, BM_ELEM_TAG) && !BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
2736                         BM_face_select_set(em->bm, f, TRUE);
2737                 }
2738         }
2739         
2740         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2741         return OPERATOR_FINISHED;
2742 }
2743
2744 void MESH_OT_loop_to_region(wmOperatorType *ot)
2745 {
2746         /* identifiers */
2747         ot->name = "Select Loop Inner-Region";
2748         ot->idname = "MESH_OT_loop_to_region";
2749         ot->description = "Select region of faces inside of a selected loop of edges";
2750
2751         /* api callbacks */
2752         ot->exec = edbm_loop_to_region_exec;
2753         ot->poll = ED_operator_editmesh;
2754
2755         /* flags */
2756         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2757         
2758         RNA_def_boolean(ot->srna, "select_bigger", 0, "Select Bigger", "Select bigger regions instead of smaller ones");
2759 }