Merged changes in the trunk up to revision 47977.
[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_vert_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         BKE_displist_fill(&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         BKE_displist_free(&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         {SIMVERT_EDGE, "EDGE", 0, "Amount of connecting edges", ""},
680
681         {SIMEDGE_LENGTH, "LENGTH", 0, "Length", ""},
682         {SIMEDGE_DIR, "DIR", 0, "Direction", ""},
683         {SIMEDGE_FACE, "FACE", 0, "Amount of Faces Around an Edge", ""},
684         {SIMEDGE_FACE_ANGLE, "FACE_ANGLE", 0, "Face Angles", ""},
685         {SIMEDGE_CREASE, "CREASE", 0, "Crease", ""},
686         {SIMEDGE_BEVEL, "BEVEL", 0, "Bevel", ""},
687         {SIMEDGE_SEAM, "SEAM", 0, "Seam", ""},
688         {SIMEDGE_SHARP, "SHARP", 0, "Sharpness", ""},
689         {SIMEDGE_FREESTYLE, "FREESTYLE_EDGE", 0, "Freestyle Edge Marks", ""},
690
691         {SIMFACE_MATERIAL, "MATERIAL", 0, "Material", ""},
692         {SIMFACE_IMAGE, "IMAGE", 0, "Image", ""},
693         {SIMFACE_AREA, "AREA", 0, "Area", ""},
694         {SIMFACE_PERIMETER, "PERIMETER", 0, "Perimeter", ""},
695         {SIMFACE_NORMAL, "NORMAL", 0, "Normal", ""},
696         {SIMFACE_COPLANAR, "COPLANAR", 0, "Co-planar", ""},
697         {SIMFACE_FREESTYLE, "FREESTYLE_FACE", 0, "Freestyle Face Marks", ""},
698
699         {0, NULL, 0, NULL, NULL}
700 };
701
702 /* selects new faces/edges/verts based on the existing selection */
703
704 static int similar_face_select_exec(bContext *C, wmOperator *op)
705 {
706         Object *ob = CTX_data_edit_object(C);
707         BMEditMesh *em = BMEdit_FromObject(ob);
708         BMOperator bmop;
709
710         /* get the type from RNA */
711         int type = RNA_enum_get(op->ptr, "type");
712         float thresh = RNA_float_get(op->ptr, "threshold");
713
714         /* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */
715         EDBM_op_init(em, &bmop, op, "similarfaces faces=%hf type=%i thresh=%f", BM_ELEM_SELECT, type, thresh);
716
717         /* execute the operator */
718         BMO_op_exec(em->bm, &bmop);
719
720         /* clear the existing selection */
721         EDBM_flag_disable_all(em, BM_ELEM_SELECT);
722
723         /* select the output */
724         BMO_slot_buffer_hflag_enable(em->bm, &bmop, "faceout", BM_ALL, BM_ELEM_SELECT, TRUE);
725
726         /* finish the operator */
727         if (!EDBM_op_finish(em, &bmop, op, TRUE)) {
728                 return OPERATOR_CANCELLED;
729         }
730
731         EDBM_update_generic(C, em, FALSE);
732
733         /* we succeeded */
734         return OPERATOR_FINISHED;
735 }       
736
737 /* ***************************************************** */
738
739 /* EDGE GROUP */
740
741 /* wrap the above function but do selection flushing edge to face */
742 static int similar_edge_select_exec(bContext *C, wmOperator *op)
743 {
744         Object *ob = CTX_data_edit_object(C);
745         BMEditMesh *em = BMEdit_FromObject(ob);
746         BMOperator bmop;
747
748         /* get the type from RNA */
749         int type = RNA_enum_get(op->ptr, "type");
750         float thresh = RNA_float_get(op->ptr, "threshold");
751
752         /* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */
753         EDBM_op_init(em, &bmop, op, "similaredges edges=%he type=%i thresh=%f", BM_ELEM_SELECT, type, thresh);
754
755         /* execute the operator */
756         BMO_op_exec(em->bm, &bmop);
757
758         /* clear the existing selection */
759         EDBM_flag_disable_all(em, BM_ELEM_SELECT);
760
761         /* select the output */
762         BMO_slot_buffer_hflag_enable(em->bm, &bmop, "edgeout", BM_ALL, BM_ELEM_SELECT, TRUE);
763         EDBM_selectmode_flush(em);
764
765         /* finish the operator */
766         if (!EDBM_op_finish(em, &bmop, op, TRUE)) {
767                 return OPERATOR_CANCELLED;
768         }
769
770         EDBM_update_generic(C, em, FALSE);
771
772         /* we succeeded */
773         return OPERATOR_FINISHED;
774 }
775
776 /* ********************************* */
777
778 /*
779  * VERT GROUP
780  * mode 1: same normal
781  * mode 2: same number of face users
782  * mode 3: same vertex groups
783  */
784 static int similar_vert_select_exec(bContext *C, wmOperator *op)
785 {
786         Object *ob = CTX_data_edit_object(C);
787         BMEditMesh *em = BMEdit_FromObject(ob);
788         BMOperator bmop;
789         /* get the type from RNA */
790         int type = RNA_enum_get(op->ptr, "type");
791         float thresh = RNA_float_get(op->ptr, "threshold");
792
793         /* initialize the bmop using EDBM api, which does various ui error reporting and other stuff */
794         EDBM_op_init(em, &bmop, op, "similarverts verts=%hv type=%i thresh=%f", BM_ELEM_SELECT, type, thresh);
795
796         /* execute the operator */
797         BMO_op_exec(em->bm, &bmop);
798
799         /* clear the existing selection */
800         EDBM_flag_disable_all(em, BM_ELEM_SELECT);
801
802         /* select the output */
803         BMO_slot_buffer_hflag_enable(em->bm, &bmop, "vertout", BM_ALL, BM_ELEM_SELECT, TRUE);
804
805         /* finish the operator */
806         if (!EDBM_op_finish(em, &bmop, op, TRUE)) {
807                 return OPERATOR_CANCELLED;
808         }
809
810         EDBM_selectmode_flush(em);
811
812         EDBM_update_generic(C, em, FALSE);
813
814         /* we succeeded */
815         return OPERATOR_FINISHED;
816 }
817
818 static int edbm_select_similar_exec(bContext *C, wmOperator *op)
819 {
820         ToolSettings *ts = CTX_data_tool_settings(C);
821         PropertyRNA *prop = RNA_struct_find_property(op->ptr, "threshold");
822
823         int type = RNA_enum_get(op->ptr, "type");
824
825         if (!RNA_property_is_set(op->ptr, prop)) {
826                 RNA_property_float_set(op->ptr, prop, ts->select_thresh);
827         }
828         else {
829                 ts->select_thresh = RNA_property_float_get(op->ptr, prop);
830         }
831
832         if      (type < 100) return similar_vert_select_exec(C, op);
833         else if (type < 200) return similar_edge_select_exec(C, op);
834         else return similar_face_select_exec(C, op);
835 }
836
837 static EnumPropertyItem *select_similar_type_itemf(bContext *C, PointerRNA *UNUSED(ptr), PropertyRNA *UNUSED(prop),
838                                                    int *free)
839 {
840         Object *obedit;
841
842         if (!C) /* needed for docs and i18n tools */
843                 return prop_similar_types;
844
845         obedit = CTX_data_edit_object(C);
846
847         if (obedit && obedit->type == OB_MESH) {
848                 EnumPropertyItem *item = NULL;
849                 int a, totitem = 0;
850                 BMEditMesh *em = BMEdit_FromObject(obedit);
851
852                 if (em->selectmode & SCE_SELECT_VERTEX) {
853                         for (a = SIMVERT_NORMAL; a < SIMEDGE_LENGTH; a++) {
854                                 RNA_enum_items_add_value(&item, &totitem, prop_similar_types, a);
855                         }
856                 }
857                 else if (em->selectmode & SCE_SELECT_EDGE) {
858                         for (a = SIMEDGE_LENGTH; a < SIMFACE_MATERIAL; a++) {
859                                 RNA_enum_items_add_value(&item, &totitem, prop_similar_types, a);
860                         }
861                 }
862                 else if (em->selectmode & SCE_SELECT_FACE) {
863                         for (a = SIMFACE_MATERIAL; a <= SIMFACE_FREESTYLE; a++) {
864                                 RNA_enum_items_add_value(&item, &totitem, prop_similar_types, a);
865                         }
866                 }
867                 RNA_enum_item_end(&item, &totitem);
868
869                 *free = 1;
870
871                 return item;
872         }
873
874         return NULL;
875 }
876
877 void MESH_OT_select_similar(wmOperatorType *ot)
878 {
879         PropertyRNA *prop;
880
881         /* identifiers */
882         ot->name = "Select Similar";
883         ot->idname = "MESH_OT_select_similar";
884         ot->description = "Select similar vertices, edges or faces by property types";
885         
886         /* api callbacks */
887         ot->invoke = WM_menu_invoke;
888         ot->exec = edbm_select_similar_exec;
889         ot->poll = ED_operator_editmesh;
890         
891         /* flags */
892         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
893         
894         /* properties */
895         prop = ot->prop = RNA_def_enum(ot->srna, "type", prop_similar_types, SIMVERT_NORMAL, "Type", "");
896         RNA_def_enum_funcs(prop, select_similar_type_itemf);
897
898         RNA_def_float(ot->srna, "threshold", 0.0, 0.0, 1.0, "Threshold", "", 0.01, 1.0);
899 }
900
901 /* ***************************************************** */
902
903 /* ****************  LOOP SELECTS *************** */
904
905 static void walker_select(BMEditMesh *em, int walkercode, void *start, int select)
906 {
907         BMesh *bm = em->bm;
908         BMElem *ele;
909         BMWalker walker;
910
911         BMW_init(&walker, bm, walkercode,
912                  BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP,
913                  BMW_FLAG_TEST_HIDDEN,
914                  BMW_NIL_LAY);
915         ele = BMW_begin(&walker, start);
916         for (; ele; ele = BMW_step(&walker)) {
917                 if (!select) {
918                         BM_select_history_remove(bm, ele);
919                 }
920                 BM_elem_select_set(bm, ele, select);
921         }
922         BMW_end(&walker);
923 }
924
925 static int edbm_loop_multiselect_exec(bContext *C, wmOperator *op)
926 {
927         Object *obedit = CTX_data_edit_object(C);
928         BMEditMesh *em = BMEdit_FromObject(obedit);
929         BMEdge *eed;
930         BMEdge **edarray;
931         int edindex;
932         int looptype = RNA_boolean_get(op->ptr, "ring");
933         
934         BMIter iter;
935         int totedgesel = 0;
936
937         BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
938                 if (BM_elem_flag_test(eed, BM_ELEM_SELECT)) {
939                         totedgesel++;
940                 }
941         }
942         
943         edarray = MEM_mallocN(sizeof(BMEdge *) * totedgesel, "edge array");
944         edindex = 0;
945         
946         BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
947                 if (BM_elem_flag_test(eed, BM_ELEM_SELECT)) {
948                         edarray[edindex] = eed;
949                         edindex++;
950                 }
951         }
952         
953         if (looptype) {
954                 for (edindex = 0; edindex < totedgesel; edindex += 1) {
955                         eed = edarray[edindex];
956                         walker_select(em, BMW_EDGERING, eed, TRUE);
957                 }
958                 EDBM_selectmode_flush(em);
959         }
960         else {
961                 for (edindex = 0; edindex < totedgesel; edindex += 1) {
962                         eed = edarray[edindex];
963                         walker_select(em, BMW_LOOP, eed, TRUE);
964                 }
965                 EDBM_selectmode_flush(em);
966         }
967         MEM_freeN(edarray);
968 //      if (EM_texFaceCheck())
969         
970         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit);
971
972         return OPERATOR_FINISHED;
973 }
974
975 void MESH_OT_loop_multi_select(wmOperatorType *ot)
976 {
977         /* identifiers */
978         ot->name = "Multi Select Loops";
979         ot->idname = "MESH_OT_loop_multi_select";
980         ot->description = "Select a loop of connected edges by connection type";
981         
982         /* api callbacks */
983         ot->exec = edbm_loop_multiselect_exec;
984         ot->poll = ED_operator_editmesh;
985         
986         /* flags */
987         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
988         
989         /* properties */
990         RNA_def_boolean(ot->srna, "ring", 0, "Ring", "");
991 }
992
993                 
994 /* ***************** MAIN MOUSE SELECTION ************** */
995
996
997 /* ***************** loop select (non modal) ************** */
998
999 static void mouse_mesh_loop(bContext *C, int mval[2], short extend, short ring)
1000 {
1001         ViewContext vc;
1002         BMEditMesh *em;
1003         BMEdge *eed;
1004         int select = TRUE;
1005         int dist = 50;
1006         
1007         em_setup_viewcontext(C, &vc);
1008         vc.mval[0] = mval[0];
1009         vc.mval[1] = mval[1];
1010         em = vc.em;
1011         
1012         /* no afterqueue (yet), so we check it now, otherwise the bm_xxxofs indices are bad */
1013         view3d_validate_backbuf(&vc);
1014
1015         eed = EDBM_edge_find_nearest(&vc, &dist);
1016         if (eed) {
1017                 if (extend == 0) {
1018                         EDBM_flag_disable_all(em, BM_ELEM_SELECT);
1019                 }
1020         
1021                 if (BM_elem_flag_test(eed, BM_ELEM_SELECT) == 0) {
1022                         select = TRUE;
1023                 }
1024                 else if (extend) {
1025                         select = FALSE;
1026                 }
1027
1028                 if (em->selectmode & SCE_SELECT_FACE) {
1029                         walker_select(em, BMW_FACELOOP, eed, select);
1030                 }
1031                 else if (em->selectmode & SCE_SELECT_EDGE) {
1032                         if (ring)
1033                                 walker_select(em, BMW_EDGERING, eed, select);
1034                         else
1035                                 walker_select(em, BMW_LOOP, eed, select);
1036                 }
1037                 else if (em->selectmode & SCE_SELECT_VERTEX) {
1038                         if (ring)
1039                                 walker_select(em, BMW_EDGERING, eed, select);
1040
1041                         else
1042                                 walker_select(em, BMW_LOOP, eed, select);
1043                 }
1044
1045                 EDBM_selectmode_flush(em);
1046 //                      if (EM_texFaceCheck())
1047                 
1048                 /* sets as active, useful for other tools */
1049                 if (select) {
1050                         if (em->selectmode & SCE_SELECT_VERTEX) {
1051                                 /* TODO: would be nice if the edge vertex chosen here
1052                                  * was the one closer to the selection pointer, instead
1053                                  * of arbitrarily selecting the first one */
1054                                 BM_select_history_store(em->bm, eed->v1);
1055                         }
1056                         else if (em->selectmode & SCE_SELECT_EDGE) {
1057                                 BM_select_history_store(em->bm, eed);
1058                         }
1059                         /* TODO: would be nice if the nearest face that
1060                          * belongs to the selected edge could be set to
1061                          * active here in face select mode */
1062                 }
1063
1064                 WM_event_add_notifier(C, NC_GEOM | ND_SELECT, vc.obedit);
1065         }
1066 }
1067
1068 static int edbm_select_loop_invoke(bContext *C, wmOperator *op, wmEvent *event)
1069 {
1070         
1071         view3d_operator_needs_opengl(C);
1072         
1073         mouse_mesh_loop(C, event->mval, RNA_boolean_get(op->ptr, "extend"),
1074                         RNA_boolean_get(op->ptr, "ring"));
1075         
1076         /* cannot do tweaks for as long this keymap is after transform map */
1077         return OPERATOR_FINISHED;
1078 }
1079
1080 void MESH_OT_loop_select(wmOperatorType *ot)
1081 {
1082         /* identifiers */
1083         ot->name = "Loop Select";
1084         ot->idname = "MESH_OT_loop_select";
1085         ot->description = "Select a loop of connected edges";
1086         
1087         /* api callbacks */
1088         ot->invoke = edbm_select_loop_invoke;
1089         ot->poll = ED_operator_editmesh_region_view3d;
1090         
1091         /* flags */
1092         ot->flag = OPTYPE_UNDO;
1093         
1094         /* properties */
1095         RNA_def_boolean(ot->srna, "extend", 0, "Extend Select", "Extend the selection");
1096         RNA_def_boolean(ot->srna, "ring", 0, "Select Ring", "Select ring");
1097 }
1098
1099 void MESH_OT_edgering_select(wmOperatorType *ot)
1100 {
1101         /* description */
1102         ot->name = "Edge Ring Select";
1103         ot->idname = "MESH_OT_edgering_select";
1104         ot->description = "Select an edge ring";
1105         
1106         /* callbacks */
1107         ot->invoke = edbm_select_loop_invoke;
1108         ot->poll = ED_operator_editmesh_region_view3d;
1109         
1110         /* flags */
1111         ot->flag = OPTYPE_UNDO;
1112
1113         RNA_def_boolean(ot->srna, "extend", 0, "Extend", "Extend the selection");
1114         RNA_def_boolean(ot->srna, "ring", 1, "Select Ring", "Select ring");
1115 }
1116
1117 /* ******************* edgetag_shortest_path and helpers ****************** */
1118
1119 static float edgetag_cut_cost(BMEditMesh *UNUSED(em), BMEdge *e1, BMEdge *e2, BMVert *v)
1120 {
1121         BMVert *v1 = (e1->v1 == v) ? e1->v2 : e1->v1;
1122         BMVert *v2 = (e2->v1 == v) ? e2->v2 : e2->v1;
1123         float cost, d1[3], d2[3];
1124
1125         /* The cost is based on the simple sum of the length of the two edgees... */
1126         sub_v3_v3v3(d1, v->co, v1->co);
1127         sub_v3_v3v3(d2, v2->co, v->co);
1128         cost = len_v3(d1);
1129         cost += len_v3(d2);
1130
1131         /* but is biased to give higher values to sharp turns, so that it will take
1132          * paths with fewer "turns" when selecting between equal-weighted paths between
1133          * the two edges */
1134         cost = cost + 0.5f * cost * (2.0f - sqrtf(fabsf(dot_v3v3(d1, d2))));
1135
1136         return cost;
1137 }
1138
1139 static void edgetag_add_adjacent(BMEditMesh *em, SmallHash *visithash, Heap *heap, int mednum, int vertnum, 
1140                                  int *nedges, int *edges, int *prevedge, float *cost)
1141 {
1142         BMEdge *e1 = EDBM_edge_at_index(em, mednum);
1143         BMVert *v = EDBM_vert_at_index(em, vertnum);
1144         int startadj, endadj = nedges[vertnum + 1];
1145
1146         for (startadj = nedges[vertnum]; startadj < endadj; startadj++) {
1147                 int adjnum = edges[startadj];
1148                 BMEdge *e2 = EDBM_edge_at_index(em, adjnum);
1149                 float newcost;
1150                 float cutcost;
1151
1152                 if (BLI_smallhash_haskey(visithash, (uintptr_t)e2))
1153                         continue;
1154
1155                 cutcost = edgetag_cut_cost(em, e1, e2, v);
1156                 newcost = cost[mednum] + cutcost;
1157
1158                 if (cost[adjnum] > newcost) {
1159                         cost[adjnum] = newcost;
1160                         prevedge[adjnum] = mednum;
1161                         BLI_heap_insert(heap, newcost, SET_INT_IN_POINTER(adjnum));
1162                 }
1163         }
1164 }
1165
1166 static void edgetag_context_set(BMEditMesh *em, Scene *scene, BMEdge *e, int val)
1167 {
1168         
1169         switch (scene->toolsettings->edge_mode) {
1170                 case EDGE_MODE_SELECT:
1171                         BM_edge_select_set(em->bm, e, val);
1172                         break;
1173                 case EDGE_MODE_TAG_SEAM:
1174                         BM_elem_flag_set(e, BM_ELEM_SEAM, val);
1175                         break;
1176                 case EDGE_MODE_TAG_SHARP:
1177                         BM_elem_flag_set(e, BM_ELEM_SMOOTH, !val);
1178                         break;
1179                 case EDGE_MODE_TAG_FREESTYLE:
1180                         BM_elem_flag_set(e, BM_ELEM_FREESTYLE, val);
1181                         break;
1182                 case EDGE_MODE_TAG_CREASE:
1183                 {
1184                         float *crease = CustomData_bmesh_get(&em->bm->edata, e->head.data, CD_CREASE);
1185                         *crease = (val) ? 1.0f : 0.0f;
1186                         break;
1187                 }
1188                 case EDGE_MODE_TAG_BEVEL:
1189                 {
1190                         float *bweight = CustomData_bmesh_get(&em->bm->edata, e->head.data, CD_BWEIGHT);
1191                         *bweight = (val) ? 1.0f : 0.0f;
1192                         break;
1193                 }
1194         }
1195 }
1196
1197 static int edgetag_context_check(Scene *scene, BMEditMesh *em, BMEdge *e)
1198 {
1199         switch (scene->toolsettings->edge_mode) {
1200                 case EDGE_MODE_SELECT:
1201                         return BM_elem_flag_test(e, BM_ELEM_SELECT) ? 1 : 0;
1202                 case EDGE_MODE_TAG_SEAM:
1203                         return BM_elem_flag_test(e, BM_ELEM_SEAM);
1204                 case EDGE_MODE_TAG_SHARP:
1205                         return !BM_elem_flag_test(e, BM_ELEM_SMOOTH);
1206                 case EDGE_MODE_TAG_FREESTYLE:
1207                         return !BM_elem_flag_test(e, BM_ELEM_FREESTYLE);
1208                 case EDGE_MODE_TAG_CREASE:
1209                         return BM_elem_float_data_get(&em->bm->edata, e, CD_CREASE) ? 1 : 0;
1210                 case EDGE_MODE_TAG_BEVEL:
1211                         return BM_elem_float_data_get(&em->bm->edata, e, CD_BWEIGHT) ? 1 : 0;
1212         }
1213         return 0;
1214 }
1215
1216 static int edgetag_shortest_path(Scene *scene, BMEditMesh *em, BMEdge *source, BMEdge *target)
1217 {
1218         BMEdge *e;
1219         BMIter iter;
1220         Heap *heap;
1221         SmallHash visithash;
1222         float *cost;
1223         int i, totvert = 0, totedge = 0, *nedges, *edges, *prevedge, mednum = -1, nedgeswap = 0;
1224         int targetnum;
1225
1226         BLI_smallhash_init(&visithash);
1227
1228         /* note, would pass BM_EDGE except we are looping over all edges anyway */
1229         BM_mesh_elem_index_ensure(em->bm, BM_VERT /* | BM_EDGE */);
1230
1231         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
1232                 if (BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
1233                         BLI_smallhash_insert(&visithash, (uintptr_t)e, NULL);
1234                 }
1235
1236                 BM_elem_index_set(e, totedge); /* set_inline */
1237                 totedge++;
1238         }
1239         em->bm->elem_index_dirty &= ~BM_EDGE;
1240
1241         /* alloc */
1242         totvert = em->bm->totvert;
1243         nedges = MEM_callocN(sizeof(*nedges) * totvert + 1, "SeamPathNEdges");
1244         edges = MEM_mallocN(sizeof(*edges) * totedge * 2, "SeamPathEdges");
1245         prevedge = MEM_mallocN(sizeof(*prevedge) * totedge, "SeamPathPrevious");
1246         cost = MEM_mallocN(sizeof(*cost) * totedge, "SeamPathCost");
1247
1248         /* count edges, compute adjacent edges offsets and fill adjacent */
1249         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
1250                 nedges[BM_elem_index_get(e->v1) + 1]++;
1251                 nedges[BM_elem_index_get(e->v2) + 1]++;
1252         }
1253
1254         for (i = 1; i < totvert; i++) {
1255                 int newswap = nedges[i + 1];
1256                 nedges[i + 1] = nedgeswap + nedges[i];
1257                 nedgeswap = newswap;
1258         }
1259         nedges[0] = nedges[1] = 0;
1260
1261         i = 0;
1262         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
1263                 edges[nedges[BM_elem_index_get(e->v1) + 1]++] = i;
1264                 edges[nedges[BM_elem_index_get(e->v2) + 1]++] = i;
1265
1266                 cost[i] = 1e20f;
1267                 prevedge[i] = -1;
1268                 i++;
1269         }
1270
1271         /*
1272          * Arrays are now filled as follows:
1273          *
1274          *      nedges[n] = sum of the # of edges incident to all vertices numbered 0 through n - 1
1275          *      edges[edges[n]..edges[n - 1]] = the indices of of the edges incident to vertex n
1276          *
1277          * As the search continues, prevedge[n] will be the previous edge on the shortest
1278          * path found so far to edge n. The visitedhash will of course contain entries
1279          * for edges that have been visited, cost[n] will contain the length of the shortest
1280          * path to edge n found so far, Finally, heap is a priority heap which is built on the
1281          * the same data as the cost array, but inverted: it is a worklist of edges prioritized
1282          * by the shortest path found so far to the edge.
1283          */
1284
1285         /* regular dijkstra shortest path, but over edges instead of vertices */
1286         heap = BLI_heap_new();
1287         BLI_heap_insert(heap, 0.0f, SET_INT_IN_POINTER(BM_elem_index_get(source)));
1288         cost[BM_elem_index_get(source)] = 0.0f;
1289         EDBM_index_arrays_init(em, 1, 1, 0);
1290         targetnum = BM_elem_index_get(target);
1291
1292         while (!BLI_heap_empty(heap)) {
1293                 mednum = GET_INT_FROM_POINTER(BLI_heap_popmin(heap));
1294                 e = EDBM_edge_at_index(em, mednum);
1295
1296                 if (mednum == targetnum)
1297                         break;
1298
1299                 if (BLI_smallhash_haskey(&visithash, (uintptr_t)e))
1300                         continue;
1301
1302                 BLI_smallhash_insert(&visithash, (uintptr_t)e, NULL);
1303
1304                 edgetag_add_adjacent(em, &visithash, heap, mednum, BM_elem_index_get(e->v1), nedges, edges, prevedge, cost);
1305                 edgetag_add_adjacent(em, &visithash, heap, mednum, BM_elem_index_get(e->v2), nedges, edges, prevedge, cost);
1306         }
1307         
1308         if (mednum == targetnum) {
1309                 short allseams = 1;
1310
1311                 /* Check whether the path is already completely tagged.
1312                  * if it is, the tags will be cleared instead of set. */
1313                 mednum = targetnum;
1314                 do {
1315                         e = EDBM_edge_at_index(em, mednum);
1316                         if (!edgetag_context_check(scene, em, e)) {
1317                                 allseams = 0;
1318                                 break;
1319                         }
1320                         mednum = prevedge[mednum];
1321                 } while (mednum != BM_elem_index_get(source));
1322
1323                 /* Follow path back and source and add or remove tags */
1324                 mednum = targetnum;
1325                 do {
1326                         e = EDBM_edge_at_index(em, mednum);
1327                         if (allseams)
1328                                 edgetag_context_set(em, scene, e, 0);
1329                         else
1330                                 edgetag_context_set(em, scene, e, 1);
1331                         mednum = prevedge[mednum];
1332                 } while (mednum != -1);
1333         }
1334
1335         EDBM_index_arrays_free(em);
1336         MEM_freeN(nedges);
1337         MEM_freeN(edges);
1338         MEM_freeN(prevedge);
1339         MEM_freeN(cost);
1340         BLI_heap_free(heap, NULL);
1341         BLI_smallhash_release(&visithash);
1342
1343         return 1;
1344 }
1345
1346 /* ******************* mesh shortest path select, uses prev-selected edge ****************** */
1347
1348 /* since you want to create paths with multiple selects, it doesn't have extend option */
1349 static int mouse_mesh_shortest_path(bContext *C, int mval[2])
1350 {
1351         ViewContext vc;
1352         BMEditMesh *em;
1353         BMEdge *e;
1354         int dist = 50;
1355         
1356         em_setup_viewcontext(C, &vc);
1357         vc.mval[0] = mval[0];
1358         vc.mval[1] = mval[1];
1359         em = vc.em;
1360         
1361         e = EDBM_edge_find_nearest(&vc, &dist);
1362         if (e) {
1363                 Mesh *me = vc.obedit->data;
1364                 int path = 0;
1365                 
1366                 if (em->bm->selected.last) {
1367                         BMEditSelection *ese = em->bm->selected.last;
1368                         
1369                         if (ese && ese->htype == BM_EDGE) {
1370                                 BMEdge *e_act;
1371                                 e_act = (BMEdge *)ese->ele;
1372                                 if (e_act != e) {
1373                                         if (edgetag_shortest_path(vc.scene, em, e_act, e)) {
1374                                                 BM_select_history_remove(em->bm, e_act);
1375                                                 path = 1;
1376                                         }
1377                                 }
1378                         }
1379                 }
1380                 if (path == 0) {
1381                         int act = (edgetag_context_check(vc.scene, em, e) == 0);
1382                         edgetag_context_set(em, vc.scene, e, act); /* switch the edge option */
1383                 }
1384                 
1385                 EDBM_selectmode_flush(em);
1386
1387                 /* even if this is selected it may not be in the selection list */
1388                 if (edgetag_context_check(vc.scene, em, e) == 0)
1389                         BM_select_history_remove(em->bm, e);
1390                 else
1391                         BM_select_history_store(em->bm, e);
1392         
1393                 /* force drawmode for mesh */
1394                 switch (CTX_data_tool_settings(C)->edge_mode) {
1395                         
1396                         case EDGE_MODE_TAG_SEAM:
1397                                 me->drawflag |= ME_DRAWSEAMS;
1398                                 ED_uvedit_live_unwrap(vc.scene, vc.obedit);
1399                                 break;
1400                         case EDGE_MODE_TAG_SHARP:
1401                                 me->drawflag |= ME_DRAWSHARP;
1402                                 break;
1403                         case EDGE_MODE_TAG_CREASE:      
1404                                 me->drawflag |= ME_DRAWCREASES;
1405                                 break;
1406                         case EDGE_MODE_TAG_BEVEL:
1407                                 me->drawflag |= ME_DRAWBWEIGHTS;
1408                                 break;
1409                         case EDGE_MODE_TAG_FREESTYLE:
1410                                 me->drawflag |= ME_DRAW_FREESTYLE_EDGE;
1411                                 break;
1412                 }
1413                 
1414                 EDBM_update_generic(C, em, FALSE);
1415
1416                 return TRUE;
1417         }
1418         else {
1419                 return FALSE;
1420         }
1421 }
1422
1423
1424 static int edbm_shortest_path_select_invoke(bContext *C, wmOperator *UNUSED(op), wmEvent *event)
1425 {
1426         
1427         view3d_operator_needs_opengl(C);
1428
1429         if (mouse_mesh_shortest_path(C, event->mval)) {
1430                 return OPERATOR_FINISHED;
1431         }
1432         else {
1433                 return OPERATOR_PASS_THROUGH;
1434         }
1435 }
1436
1437 static int edbm_shortest_path_select_poll(bContext *C)
1438 {
1439         if (ED_operator_editmesh_region_view3d(C)) {
1440                 Object *obedit = CTX_data_edit_object(C);
1441                 BMEditMesh *em = BMEdit_FromObject(obedit);
1442                 return (em->selectmode & SCE_SELECT_EDGE) != 0;
1443         }
1444         return 0;
1445 }
1446
1447 void MESH_OT_select_shortest_path(wmOperatorType *ot)
1448 {
1449         /* identifiers */
1450         ot->name = "Shortest Path Select";
1451         ot->idname = "MESH_OT_select_shortest_path";
1452         ot->description = "Select shortest path between two selections";
1453         
1454         /* api callbacks */
1455         ot->invoke = edbm_shortest_path_select_invoke;
1456         ot->poll = edbm_shortest_path_select_poll;
1457         
1458         /* flags */
1459         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1460         
1461         /* properties */
1462         RNA_def_boolean(ot->srna, "extend", 0, "Extend Select", "");
1463 }
1464
1465 /* ************************************************** */
1466 /* here actual select happens */
1467 /* gets called via generic mouse select operator */
1468 int mouse_mesh(bContext *C, const int mval[2], short extend, short deselect, short toggle)
1469 {
1470         ViewContext vc;
1471         BMVert *eve = NULL;
1472         BMEdge *eed = NULL;
1473         BMFace *efa = NULL;
1474         
1475         /* setup view context for argument to callbacks */
1476         em_setup_viewcontext(C, &vc);
1477         vc.mval[0] = mval[0];
1478         vc.mval[1] = mval[1];
1479         
1480         if (unified_findnearest(&vc, &eve, &eed, &efa)) {
1481                 
1482                 // Deselect everything
1483                 if (extend == 0 && deselect == 0 && toggle == 0)
1484                         EDBM_flag_disable_all(vc.em, BM_ELEM_SELECT);
1485                 
1486                 if (efa) {
1487                         if (extend) {
1488                                 // set the last selected face
1489                                 BM_active_face_set(vc.em->bm, efa);
1490                                 
1491                                 // Work-around: deselect first, so we can guarantee it will
1492                                 // be active even if it was already selected
1493                                 BM_select_history_remove(vc.em->bm, efa);
1494                                 BM_face_select_set(vc.em->bm, efa, FALSE);
1495                                 BM_select_history_store(vc.em->bm, efa);
1496                                 BM_face_select_set(vc.em->bm, efa, TRUE);
1497                         }
1498                         else if (deselect) {
1499                                 BM_select_history_remove(vc.em->bm, efa);
1500                                 BM_face_select_set(vc.em->bm, efa, FALSE);
1501                         }
1502                         else {
1503                                 // set the last selected face
1504                                 BM_active_face_set(vc.em->bm, efa);
1505                         
1506                                 if (!BM_elem_flag_test(efa, BM_ELEM_SELECT)) {
1507                                         BM_select_history_store(vc.em->bm, efa);
1508                                         BM_face_select_set(vc.em->bm, efa, TRUE);
1509                                 }
1510                                 else if (toggle) {
1511                                         BM_select_history_remove(vc.em->bm, efa);
1512                                         BM_face_select_set(vc.em->bm, efa, FALSE);
1513                                 }
1514                         }
1515                 }
1516                 else if (eed) {
1517                         if (extend) {
1518                                 // Work-around: deselect first, so we can guarantee it will
1519                                 // be active even if it was already selected
1520                                 BM_select_history_remove(vc.em->bm, eed);
1521                                 BM_edge_select_set(vc.em->bm, eed, FALSE);
1522                                 BM_select_history_store(vc.em->bm, eed);
1523                                 BM_edge_select_set(vc.em->bm, eed, TRUE);
1524                         }
1525                         else if (deselect) {
1526                                 BM_select_history_remove(vc.em->bm, eed);
1527                                 BM_edge_select_set(vc.em->bm, eed, FALSE);
1528                         }
1529                         else {
1530                                 if (!BM_elem_flag_test(eed, BM_ELEM_SELECT)) {
1531                                         BM_select_history_store(vc.em->bm, eed);
1532                                         BM_edge_select_set(vc.em->bm, eed, TRUE);
1533                                 }
1534                                 else if (toggle) {
1535                                         BM_select_history_remove(vc.em->bm, eed);
1536                                         BM_edge_select_set(vc.em->bm, eed, FALSE);
1537                                 }
1538                         }
1539                 }
1540                 else if (eve) {
1541                         if (extend) {
1542                                 // Work-around: deselect first, so we can guarantee it will
1543                                 // be active even if it was already selected
1544                                 BM_select_history_remove(vc.em->bm, eve);
1545                                 BM_vert_select_set(vc.em->bm, eve, FALSE);
1546                                 BM_select_history_store(vc.em->bm, eve);
1547                                 BM_vert_select_set(vc.em->bm, eve, TRUE);
1548                         }
1549                         else if (deselect) {
1550                                 BM_select_history_remove(vc.em->bm, eve);
1551                                 BM_vert_select_set(vc.em->bm, eve, FALSE);
1552                         }
1553                         else {
1554                                 if (!BM_elem_flag_test(eve, BM_ELEM_SELECT)) {
1555                                         BM_select_history_store(vc.em->bm, eve);
1556                                         BM_vert_select_set(vc.em->bm, eve, TRUE);
1557                                 }
1558                                 else if (toggle) {
1559                                         BM_select_history_remove(vc.em->bm, eve);
1560                                         BM_vert_select_set(vc.em->bm, eve, FALSE);
1561                                 }
1562                         }
1563                 }
1564                 
1565                 EDBM_selectmode_flush(vc.em);
1566                   
1567                 /* change active material on object */
1568                 if (efa && efa->mat_nr != vc.obedit->actcol - 1) {
1569                         vc.obedit->actcol = efa->mat_nr + 1;
1570                         vc.em->mat_nr = efa->mat_nr;
1571
1572                         WM_event_add_notifier(C, NC_MATERIAL | ND_SHADING, NULL);
1573
1574                 }
1575
1576                 WM_event_add_notifier(C, NC_GEOM | ND_SELECT, vc.obedit);
1577                 return 1;
1578         }
1579
1580         return 0;
1581 }
1582
1583 static void edbm_strip_selections(BMEditMesh *em)
1584 {
1585         BMEditSelection *ese, *nextese;
1586
1587         if (!(em->selectmode & SCE_SELECT_VERTEX)) {
1588                 ese = em->bm->selected.first;
1589                 while (ese) {
1590                         nextese = ese->next;
1591                         if (ese->htype == BM_VERT) BLI_freelinkN(&(em->bm->selected), ese);
1592                         ese = nextese;
1593                 }
1594         }
1595         if (!(em->selectmode & SCE_SELECT_EDGE)) {
1596                 ese = em->bm->selected.first;
1597                 while (ese) {
1598                         nextese = ese->next;
1599                         if (ese->htype == BM_EDGE) BLI_freelinkN(&(em->bm->selected), ese);
1600                         ese = nextese;
1601                 }
1602         }
1603         if (!(em->selectmode & SCE_SELECT_FACE)) {
1604                 ese = em->bm->selected.first;
1605                 while (ese) {
1606                         nextese = ese->next;
1607                         if (ese->htype == BM_FACE) BLI_freelinkN(&(em->bm->selected), ese);
1608                         ese = nextese;
1609                 }
1610         }
1611 }
1612
1613 /* when switching select mode, makes sure selection is consistent for editing */
1614 /* also for paranoia checks to make sure edge or face mode works */
1615 void EDBM_selectmode_set(BMEditMesh *em)
1616 {
1617         BMVert *eve;
1618         BMEdge *eed;
1619         BMFace *efa;
1620         BMIter iter;
1621         
1622         em->bm->selectmode = em->selectmode;
1623
1624         edbm_strip_selections(em); /* strip BMEditSelections from em->selected that are not relevant to new mode */
1625         
1626         if (em->selectmode & SCE_SELECT_VERTEX) {
1627                 EDBM_select_flush(em);
1628         }
1629         else if (em->selectmode & SCE_SELECT_EDGE) {
1630                 /* deselect vertices, and select again based on edge select */
1631                 eve = BM_iter_new(&iter, em->bm, BM_VERTS_OF_MESH, NULL);
1632                 for (; eve; eve = BM_iter_step(&iter)) BM_vert_select_set(em->bm, eve, FALSE);
1633                 
1634                 eed = BM_iter_new(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1635                 for (; eed; eed = BM_iter_step(&iter)) {
1636                         if (BM_elem_flag_test(eed, BM_ELEM_SELECT)) {
1637                                 BM_edge_select_set(em->bm, eed, TRUE);
1638                         }
1639                 }
1640                 
1641                 /* selects faces based on edge status */
1642                 EDBM_selectmode_flush(em);
1643         }
1644         else if (em->selectmode & SCE_SELECT_FACE) {
1645                 /* deselect eges, and select again based on face select */
1646                 eed = BM_iter_new(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1647                 for (; eed; eed = BM_iter_step(&iter)) BM_edge_select_set(em->bm, eed, FALSE);
1648                 
1649                 efa = BM_iter_new(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1650                 for (; efa; efa = BM_iter_step(&iter)) {
1651                         if (BM_elem_flag_test(efa, BM_ELEM_SELECT)) {
1652                                 BM_face_select_set(em->bm, efa, TRUE);
1653                         }
1654                 }
1655         }
1656 }
1657
1658 void EDBM_selectmode_convert(BMEditMesh *em, short oldmode, short selectmode)
1659 {
1660         BMEdge *eed;
1661         BMFace *efa;
1662         BMIter iter;
1663
1664         /* have to find out what the selectionmode was previously */
1665         if (oldmode == SCE_SELECT_VERTEX) {
1666                 if (selectmode == SCE_SELECT_EDGE) {
1667                         /* select all edges associated with every selected vertex */
1668                         eed = BM_iter_new(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1669                         for (; eed; eed = BM_iter_step(&iter)) {
1670                                 if ((BM_elem_flag_test(eed->v1, BM_ELEM_SELECT) ||
1671                                      BM_elem_flag_test(eed->v2, BM_ELEM_SELECT)))
1672                                 {
1673                                         BM_edge_select_set(em->bm, eed, TRUE);
1674                                 }
1675                         }
1676                 }               
1677                 else if (selectmode == SCE_SELECT_FACE) {
1678                         BMIter liter;
1679                         BMLoop *l;
1680
1681                         /* select all faces associated with every selected vertex */
1682                         efa = BM_iter_new(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1683                         for (; efa; efa = BM_iter_step(&iter)) {
1684                                 l = BM_iter_new(&liter, em->bm, BM_LOOPS_OF_FACE, efa);
1685                                 for (; l; l = BM_iter_step(&liter)) {
1686                                         if (BM_elem_flag_test(l->v, BM_ELEM_SELECT)) {
1687                                                 BM_face_select_set(em->bm, efa, TRUE);
1688                                                 break;
1689                                         }
1690                                 }
1691                         }
1692                 }
1693         }
1694         
1695         if (oldmode == SCE_SELECT_EDGE) {
1696                 if (selectmode == SCE_SELECT_FACE) {
1697                         BMIter liter;
1698                         BMLoop *l;
1699
1700                         /* select all faces associated with every selected vertex */
1701                         efa = BM_iter_new(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1702                         for (; efa; efa = BM_iter_step(&iter)) {
1703                                 l = BM_iter_new(&liter, em->bm, BM_LOOPS_OF_FACE, efa);
1704                                 for (; l; l = BM_iter_step(&liter)) {
1705                                         if (BM_elem_flag_test(l->v, BM_ELEM_SELECT)) {
1706                                                 BM_face_select_set(em->bm, efa, TRUE);
1707                                                 break;
1708                                         }
1709                                 }
1710                         }
1711                 }
1712         }
1713 }
1714
1715
1716 void EDBM_deselect_by_material(BMEditMesh *em, const short index, const short select)
1717 {
1718         BMIter iter;
1719         BMFace *efa;
1720
1721         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1722                 if (BM_elem_flag_test(efa, BM_ELEM_HIDDEN))
1723                         continue;
1724                 if (efa->mat_nr == index) {
1725                         BM_face_select_set(em->bm, efa, select);
1726                 }
1727         }
1728 }
1729
1730 void EDBM_select_toggle_all(BMEditMesh *em) /* exported for UV */
1731 {
1732         if (em->bm->totvertsel || em->bm->totedgesel || em->bm->totfacesel)
1733                 EDBM_flag_disable_all(em, BM_ELEM_SELECT);
1734         else
1735                 EDBM_flag_enable_all(em, BM_ELEM_SELECT);
1736 }
1737
1738 void EDBM_select_swap(BMEditMesh *em) /* exported for UV */
1739 {
1740         BMIter iter;
1741         BMVert *eve;
1742         BMEdge *eed;
1743         BMFace *efa;
1744         
1745         if (em->bm->selectmode & SCE_SELECT_VERTEX) {
1746                 BM_ITER_MESH (eve, &iter, em->bm, BM_VERTS_OF_MESH) {
1747                         if (BM_elem_flag_test(eve, BM_ELEM_HIDDEN))
1748                                 continue;
1749                         BM_vert_select_set(em->bm, eve, !BM_elem_flag_test(eve, BM_ELEM_SELECT));
1750                 }
1751         }
1752         else if (em->selectmode & SCE_SELECT_EDGE) {
1753                 BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
1754                         if (BM_elem_flag_test(eed, BM_ELEM_HIDDEN))
1755                                 continue;
1756                         BM_edge_select_set(em->bm, eed, !BM_elem_flag_test(eed, BM_ELEM_SELECT));
1757                 }
1758         }
1759         else {
1760                 BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1761                         if (BM_elem_flag_test(efa, BM_ELEM_HIDDEN))
1762                                 continue;
1763                         BM_face_select_set(em->bm, efa, !BM_elem_flag_test(efa, BM_ELEM_SELECT));
1764                 }
1765
1766         }
1767 //      if (EM_texFaceCheck())
1768 }
1769
1770 int EDBM_select_interior_faces(BMEditMesh *em)
1771 {
1772         BMesh *bm = em->bm;
1773         BMIter iter;
1774         BMIter eiter;
1775         BMFace *efa;
1776         BMEdge *eed;
1777         int ok;
1778         int change = FALSE;
1779
1780         BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1781                 if (BM_elem_flag_test(efa, BM_ELEM_HIDDEN))
1782                         continue;
1783
1784
1785                 ok = TRUE;
1786                 BM_ITER_ELEM (eed, &eiter, efa, BM_EDGES_OF_FACE) {
1787                         if (BM_edge_face_count(eed) < 3) {
1788                                 ok = FALSE;
1789                                 break;
1790                         }
1791                 }
1792
1793                 if (ok) {
1794                         BM_face_select_set(bm, efa, TRUE);
1795                         change = TRUE;
1796                 }
1797         }
1798
1799         return change;
1800 }
1801
1802 static void linked_limit_default(bContext *C, wmOperator *op)
1803 {
1804         if (!RNA_struct_property_is_set(op->ptr, "limit")) {
1805                 Object *obedit = CTX_data_edit_object(C);
1806                 BMEditMesh *em = BMEdit_FromObject(obedit);
1807                 if (em->selectmode == SCE_SELECT_FACE)
1808                         RNA_boolean_set(op->ptr, "limit", TRUE);
1809                 else
1810                         RNA_boolean_set(op->ptr, "limit", FALSE);
1811         }
1812 }
1813
1814 static int edbm_select_linked_pick_invoke(bContext *C, wmOperator *op, wmEvent *event)
1815 {
1816         Object *obedit = CTX_data_edit_object(C);
1817         ViewContext vc;
1818         BMesh *bm;
1819         BMWalker walker;
1820         BMEditMesh *em;
1821         BMVert *eve;
1822         BMEdge *e, *eed;
1823         BMFace *efa;
1824         int sel = !RNA_boolean_get(op->ptr, "deselect");
1825
1826         int limit;
1827
1828         linked_limit_default(C, op);
1829
1830         limit = RNA_boolean_get(op->ptr, "limit");
1831
1832         /* unified_finednearest needs ogl */
1833         view3d_operator_needs_opengl(C);
1834         
1835         /* setup view context for argument to callbacks */
1836         em_setup_viewcontext(C, &vc);
1837         em = vc.em;
1838
1839         if (em->bm->totedge == 0)
1840                 return OPERATOR_CANCELLED;
1841         
1842         bm = em->bm;
1843
1844         vc.mval[0] = event->mval[0];
1845         vc.mval[1] = event->mval[1];
1846         
1847         /* return warning! */
1848         
1849         if (unified_findnearest(&vc, &eve, &eed, &efa) == 0) {
1850                 WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit);
1851         
1852                 return OPERATOR_CANCELLED;
1853         }
1854         
1855         if (em->selectmode == SCE_SELECT_FACE) {
1856                 BMIter iter;
1857
1858                 if (efa == NULL)
1859                         return OPERATOR_CANCELLED;
1860
1861                 if (limit) {
1862                         /* hflag no-seam --> bmo-tag */
1863                         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
1864                                 /* BMESH_TODO, don't use 'BM_ELEM_SELECT' here, its a HFLAG only! */
1865                                 BMO_elem_flag_set(bm, e, BM_ELEM_SELECT, !BM_elem_flag_test(e, BM_ELEM_SEAM));
1866                         }
1867                 }
1868
1869                 /* walk */
1870                 BMW_init(&walker, bm, BMW_ISLAND,
1871                          BMW_MASK_NOP, limit ? BM_ELEM_SELECT : BMW_MASK_NOP, BMW_MASK_NOP,
1872                          BMW_FLAG_TEST_HIDDEN,
1873                          BMW_NIL_LAY);
1874
1875                 e = BMW_begin(&walker, efa);
1876                 for (; efa; efa = BMW_step(&walker)) {
1877                         BM_face_select_set(bm, efa, sel);
1878                 }
1879                 BMW_end(&walker);
1880         }
1881         else {
1882                 if (efa) {
1883                         eed = BM_FACE_FIRST_LOOP(efa)->e;
1884                 }
1885                 else if (!eed) {
1886                         if (!eve || !eve->e)
1887                                 return OPERATOR_CANCELLED;
1888
1889                         eed = eve->e;
1890                 }
1891
1892                 BMW_init(&walker, bm, BMW_SHELL,
1893                          BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP,
1894                          BMW_FLAG_TEST_HIDDEN,
1895                          BMW_NIL_LAY);
1896
1897                 e = BMW_begin(&walker, eed->v1);
1898                 for (; e; e = BMW_step(&walker)) {
1899                         BM_edge_select_set(bm, e, sel);
1900                 }
1901                 BMW_end(&walker);
1902
1903                 EDBM_selectmode_flush(em);
1904         }
1905
1906         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit);
1907         return OPERATOR_FINISHED;
1908 }
1909
1910 void MESH_OT_select_linked_pick(wmOperatorType *ot)
1911 {
1912         /* identifiers */
1913         ot->name = "Select Linked";
1914         ot->idname = "MESH_OT_select_linked_pick";
1915         ot->description = "(De)select all vertices linked to the edge under the mouse cursor";
1916         
1917         /* api callbacks */
1918         ot->invoke = edbm_select_linked_pick_invoke;
1919         ot->poll = ED_operator_editmesh;
1920         
1921         /* flags */
1922         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1923         
1924         RNA_def_boolean(ot->srna, "deselect", 0, "Deselect", "");
1925         RNA_def_boolean(ot->srna, "limit", 0, "Limit by Seams", "");
1926 }
1927
1928
1929 static int edbm_select_linked_exec(bContext *C, wmOperator *op)
1930 {
1931         Object *obedit = CTX_data_edit_object(C);
1932         BMEditMesh *em = BMEdit_FromObject(obedit);
1933         BMesh *bm = em->bm;
1934         BMIter iter;
1935         BMVert *v;
1936         BMEdge *e;
1937         BMWalker walker;
1938
1939         int limit;
1940
1941         linked_limit_default(C, op);
1942
1943         limit = RNA_boolean_get(op->ptr, "limit");
1944
1945         if (em->selectmode == SCE_SELECT_FACE) {
1946                 BMFace *efa;
1947
1948                 BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1949                         BM_elem_flag_set(efa, BM_ELEM_TAG, (BM_elem_flag_test(efa, BM_ELEM_SELECT) &&
1950                                                             !BM_elem_flag_test(efa, BM_ELEM_HIDDEN)));
1951                 }
1952
1953                 if (limit) {
1954                         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
1955                                 /* BMESH_TODO, don't use 'BM_ELEM_SELECT' here, its a HFLAG only! */
1956                                 BMO_elem_flag_set(bm, e, BM_ELEM_SELECT, !BM_elem_flag_test(e, BM_ELEM_SEAM));
1957                         }
1958                 }
1959
1960                 BMW_init(&walker, bm, BMW_ISLAND,
1961                          BMW_MASK_NOP, limit ? BM_ELEM_SELECT : BMW_MASK_NOP, BMW_MASK_NOP,
1962                          BMW_FLAG_TEST_HIDDEN,
1963                          BMW_NIL_LAY);
1964
1965                 BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
1966                         if (BM_elem_flag_test(efa, BM_ELEM_TAG)) {
1967                                 e = BMW_begin(&walker, efa);
1968                                 for (; efa; efa = BMW_step(&walker)) {
1969                                         BM_face_select_set(bm, efa, TRUE);
1970                                 }
1971                         }
1972                 }
1973                 BMW_end(&walker);
1974         }
1975         else {
1976                 BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
1977                         if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
1978                                 BM_elem_flag_enable(v, BM_ELEM_TAG);
1979                         }
1980                         else {
1981                                 BM_elem_flag_disable(v, BM_ELEM_TAG);
1982                         }
1983                 }
1984
1985                 BMW_init(&walker, em->bm, BMW_SHELL,
1986                          BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP,
1987                          BMW_FLAG_TEST_HIDDEN,
1988                          BMW_NIL_LAY);
1989
1990                 BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
1991                         if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
1992                                 e = BMW_begin(&walker, v);
1993                                 for (; e; e = BMW_step(&walker)) {
1994                                         BM_vert_select_set(em->bm, e->v1, TRUE);
1995                                         BM_vert_select_set(em->bm, e->v2, TRUE);
1996                                 }
1997                         }
1998                 }
1999                 BMW_end(&walker);
2000         }
2001         EDBM_selectmode_flush_ex(em, SCE_SELECT_VERTEX);
2002
2003         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit);
2004
2005         return OPERATOR_FINISHED;
2006 }
2007
2008 void MESH_OT_select_linked(wmOperatorType *ot)
2009 {
2010         /* identifiers */
2011         ot->name = "Select Linked All";
2012         ot->idname = "MESH_OT_select_linked";
2013         ot->description = "Select all vertices linked to the active mesh";
2014         
2015         /* api callbacks */
2016         ot->exec = edbm_select_linked_exec;
2017         ot->poll = ED_operator_editmesh;
2018         
2019         /* flags */
2020         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2021         
2022         RNA_def_boolean(ot->srna, "limit", 0, "Limit by Seams", "");
2023 }
2024
2025 /* ******************** **************** */
2026
2027 static int edbm_select_more_exec(bContext *C, wmOperator *UNUSED(op))
2028 {
2029         Object *obedit = CTX_data_edit_object(C);
2030         BMEditMesh *em = BMEdit_FromObject(obedit);
2031
2032         EDBM_select_more(em);
2033
2034         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit);
2035         return OPERATOR_FINISHED;
2036 }
2037
2038 void MESH_OT_select_more(wmOperatorType *ot)
2039 {
2040         /* identifiers */
2041         ot->name = "Select More";
2042         ot->idname = "MESH_OT_select_more";
2043         ot->description = "Select more vertices, edges or faces connected to initial selection";
2044
2045         /* api callbacks */
2046         ot->exec = edbm_select_more_exec;
2047         ot->poll = ED_operator_editmesh;
2048         
2049         /* flags */
2050         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2051 }
2052
2053 static int edbm_select_less_exec(bContext *C, wmOperator *UNUSED(op))
2054 {
2055         Object *obedit = CTX_data_edit_object(C);
2056         BMEditMesh *em = BMEdit_FromObject(obedit);
2057
2058         EDBM_select_less(em);
2059
2060         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit);
2061         return OPERATOR_FINISHED;
2062 }
2063
2064 void MESH_OT_select_less(wmOperatorType *ot)
2065 {
2066         /* identifiers */
2067         ot->name = "Select Less";
2068         ot->idname = "MESH_OT_select_less";
2069         ot->description = "Deselect vertices, edges or faces at the boundary of each selection region";
2070
2071         /* api callbacks */
2072         ot->exec = edbm_select_less_exec;
2073         ot->poll = ED_operator_editmesh;
2074         
2075         /* flags */
2076         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2077 }
2078
2079 /* Walk all reachable elements of the same type as h_act in breadth-first
2080  * order, starting from h_act. Deselects elements if the depth when they
2081  * are reached is not a multiple of "nth". */
2082 static void walker_deselect_nth(BMEditMesh *em, int nth, int offset, BMHeader *h_act)
2083 {
2084         BMElem *ele;
2085         BMesh *bm = em->bm;
2086         BMWalker walker;
2087         BMIter iter;
2088         int walktype = 0, itertype = 0, flushtype = 0;
2089         short mask_vert = 0, mask_edge = 0, mask_face = 0;
2090
2091         /* No active element from which to start - nothing to do */
2092         if (h_act == NULL) {
2093                 return;
2094         }
2095
2096         /* Determine which type of iter, walker, and select flush to use
2097          * based on type of the elements being deselected */
2098         switch (h_act->htype) {
2099                 case BM_VERT:
2100                         itertype = BM_VERTS_OF_MESH;
2101                         walktype = BMW_CONNECTED_VERTEX;
2102                         flushtype = SCE_SELECT_VERTEX;
2103                         mask_vert = BM_ELEM_SELECT;
2104                         break;
2105                 case BM_EDGE:
2106                         itertype = BM_EDGES_OF_MESH;
2107                         walktype = BMW_SHELL;
2108                         flushtype = SCE_SELECT_EDGE;
2109                         mask_edge = BM_ELEM_SELECT;
2110                         break;
2111                 case BM_FACE:
2112                         itertype = BM_FACES_OF_MESH;
2113                         walktype = BMW_ISLAND;
2114                         flushtype = SCE_SELECT_FACE;
2115                         mask_face = BM_ELEM_SELECT;
2116                         break;
2117         }
2118
2119         /* Walker restrictions uses BMO flags, not header flags,
2120          * so transfer BM_ELEM_SELECT from HFlags onto a BMO flag layer. */
2121         BMO_push(bm, NULL);
2122         BM_ITER_MESH (ele, &iter, bm, itertype) {
2123                 if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
2124                         /* BMESH_TODO, don't use 'BM_ELEM_SELECT' here, its a HFLAG only! */
2125                         BMO_elem_flag_enable(bm, (BMElemF *)ele, BM_ELEM_SELECT);
2126                 }
2127         }
2128
2129         /* Walk over selected elements starting at active */
2130         BMW_init(&walker, bm, walktype,
2131                  mask_vert, mask_edge, mask_face,
2132                  BMW_FLAG_NOP, /* don't use BMW_FLAG_TEST_HIDDEN here since we want to desel all */
2133                  BMW_NIL_LAY);
2134
2135         BLI_assert(walker.order == BMW_BREADTH_FIRST);
2136         for (ele = BMW_begin(&walker, h_act); ele != NULL; ele = BMW_step(&walker)) {
2137                 /* Deselect elements that aren't at "nth" depth from active */
2138                 if ((offset + BMW_current_depth(&walker)) % nth) {
2139                         BM_elem_select_set(bm, ele, FALSE);
2140                 }
2141         }
2142         BMW_end(&walker);
2143
2144         BMO_pop(bm);
2145
2146         /* Flush selection up */
2147         EDBM_selectmode_flush_ex(em, flushtype);
2148 }
2149
2150 static void deselect_nth_active(BMEditMesh *em, BMVert **r_eve, BMEdge **r_eed, BMFace **r_efa)
2151 {
2152         BMVert *v;
2153         BMEdge *e;
2154         BMFace *f;
2155         BMIter iter;
2156         BMEditSelection *ese;
2157
2158         *r_eve = NULL;
2159         *r_eed = NULL;
2160         *r_efa = NULL;
2161
2162         EDBM_selectmode_flush(em);
2163         ese = (BMEditSelection *)em->bm->selected.last;
2164
2165         if (ese) {
2166                 switch (ese->htype) {
2167                         case BM_VERT:
2168                                 *r_eve = (BMVert *)ese->ele;
2169                                 return;
2170                         case BM_EDGE:
2171                                 *r_eed = (BMEdge *)ese->ele;
2172                                 return;
2173                         case BM_FACE:
2174                                 *r_efa = (BMFace *)ese->ele;
2175                                 return;
2176                 }
2177         }
2178
2179         if (em->selectmode & SCE_SELECT_VERTEX) {
2180                 BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
2181                         if (BM_elem_flag_test(v, BM_ELEM_SELECT)) {
2182                                 *r_eve = v;
2183                                 return;
2184                         }
2185                 }
2186         }
2187         else if (em->selectmode & SCE_SELECT_EDGE) {
2188                 BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2189                         if (BM_elem_flag_test(e, BM_ELEM_SELECT)) {
2190                                 *r_eed = e;
2191                                 return;
2192                         }
2193                 }
2194         }
2195         else if (em->selectmode & SCE_SELECT_FACE) {
2196                 f = BM_active_face_get(em->bm, TRUE);
2197                 if (f) {
2198                         *r_efa = f;
2199                         return;
2200                 }
2201         }
2202 }
2203
2204 static int edbm_deselect_nth(BMEditMesh *em, int nth, int offset)
2205 {
2206         BMVert *v;
2207         BMEdge *e;
2208         BMFace *f;
2209
2210         deselect_nth_active(em, &v, &e, &f);
2211
2212         if (v) {
2213                 walker_deselect_nth(em, nth, offset, &v->head);
2214                 return 1;
2215         }
2216         else if (e) {
2217                 walker_deselect_nth(em, nth, offset, &e->head);
2218                 return 1;
2219         }
2220         else if (f) {
2221                 walker_deselect_nth(em, nth, offset, &f->head);
2222                 return 1;
2223         }
2224
2225         return 0;
2226 }
2227
2228 static int edbm_select_nth_exec(bContext *C, wmOperator *op)
2229 {
2230         Object *obedit = CTX_data_edit_object(C);
2231         BMEditMesh *em = BMEdit_FromObject(obedit);
2232         int nth = RNA_int_get(op->ptr, "nth");
2233         int offset = RNA_int_get(op->ptr, "offset");
2234
2235         offset = MIN2(nth, offset);
2236
2237         if (edbm_deselect_nth(em, nth, offset) == 0) {
2238                 BKE_report(op->reports, RPT_ERROR, "Mesh has no active vert/edge/face");
2239                 return OPERATOR_CANCELLED;
2240         }
2241
2242         EDBM_update_generic(C, em, FALSE);
2243
2244         return OPERATOR_FINISHED;
2245 }
2246
2247
2248 void MESH_OT_select_nth(wmOperatorType *ot)
2249 {
2250         /* identifiers */
2251         ot->name = "Select Nth";
2252         ot->idname = "MESH_OT_select_nth";
2253         ot->description = "Select every Nth element starting from a selected vertex, edge or face";
2254
2255         /* api callbacks */
2256         ot->exec = edbm_select_nth_exec;
2257         ot->poll = ED_operator_editmesh;
2258
2259         /* flags */
2260         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2261
2262         RNA_def_int(ot->srna, "nth", 2, 2, 100, "Nth Selection", "", 1, INT_MAX);
2263         RNA_def_int(ot->srna, "offset", 0, 0, 100, "Offset", "", 0, INT_MAX);
2264 }
2265
2266 void em_setup_viewcontext(bContext *C, ViewContext *vc)
2267 {
2268         view3d_set_viewcontext(C, vc);
2269         
2270         if (vc->obedit) {
2271                 Mesh *me = vc->obedit->data;
2272                 vc->em = me->edit_btmesh;
2273         }
2274 }
2275
2276 /* poll call for mesh operators requiring a view3d context */
2277 int EM_view3d_poll(bContext *C)
2278 {
2279         if (ED_operator_editmesh(C) && ED_operator_view3d_active(C))
2280                 return 1;
2281
2282         return 0;
2283 }
2284
2285
2286 static int edbm_select_sharp_edges_exec(bContext *C, wmOperator *op)
2287 {
2288         /* Find edges that have exactly two neighboring faces,
2289          * check the angle between those faces, and if angle is
2290          * small enough, select the edge
2291          */
2292         Object *obedit = CTX_data_edit_object(C);
2293         BMEditMesh *em = BMEdit_FromObject(obedit);
2294         BMIter iter;
2295         BMEdge *e;
2296         BMLoop *l1, *l2;
2297         float sharp = RNA_float_get(op->ptr, "sharpness"), angle;
2298
2299         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2300                 if (BM_elem_flag_test(e, BM_ELEM_HIDDEN) || !e->l)
2301                         continue;
2302
2303                 l1 = e->l;
2304                 l2 = l1->radial_next;
2305
2306                 if (l1 == l2)
2307                         continue;
2308
2309                 /* edge has exactly two neighboring faces, check angle */
2310                 angle = angle_normalized_v3v3(l1->f->no, l2->f->no);
2311
2312                 if (fabsf(angle) > sharp) {
2313                         BM_edge_select_set(em->bm, e, TRUE);
2314                 }
2315
2316         }
2317
2318         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2319
2320         return OPERATOR_FINISHED;
2321 }
2322
2323 void MESH_OT_edges_select_sharp(wmOperatorType *ot)
2324 {
2325         PropertyRNA *prop;
2326
2327         /* identifiers */
2328         ot->name = "Select Sharp Edges";
2329         ot->description = "Select all sharp-enough edges";
2330         ot->idname = "MESH_OT_edges_select_sharp";
2331         
2332         /* api callbacks */
2333         ot->exec = edbm_select_sharp_edges_exec;
2334         ot->poll = ED_operator_editmesh;
2335         
2336         /* flags */
2337         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2338         
2339         /* props */
2340         prop = RNA_def_float_rotation(ot->srna, "sharpness", 0, NULL, DEG2RADF(0.01f), DEG2RADF(180.0f),
2341                                       "Sharpness", "", DEG2RADF(1.0f), DEG2RADF(180.0f));
2342         RNA_def_property_float_default(prop, DEG2RADF(1.0f));
2343 }
2344
2345 static int edbm_select_linked_flat_faces_exec(bContext *C, wmOperator *op)
2346 {
2347         Object *obedit = CTX_data_edit_object(C);
2348         BMEditMesh *em = BMEdit_FromObject(obedit);
2349         BMIter iter, liter, liter2;
2350         BMFace *f, **stack = NULL;
2351         BLI_array_declare(stack);
2352         BMLoop *l, *l2;
2353         float sharp = RNA_float_get(op->ptr, "sharpness");
2354         int i;
2355
2356         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2357                 BM_elem_flag_disable(f, BM_ELEM_TAG);
2358         }
2359
2360         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2361                 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))
2362                         continue;
2363
2364                 BLI_array_empty(stack);
2365                 i = 1;
2366
2367                 BLI_array_grow_one(stack);
2368                 stack[i - 1] = f;
2369
2370                 while (i) {
2371                         f = stack[i - 1];
2372                         i--;
2373
2374                         BM_face_select_set(em->bm, f, TRUE);
2375
2376                         BM_elem_flag_enable(f, BM_ELEM_TAG);
2377
2378                         BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
2379                                 BM_ITER_ELEM (l2, &liter2, l, BM_LOOPS_OF_LOOP) {
2380                                         float angle;
2381
2382                                         if (BM_elem_flag_test(l2->f, BM_ELEM_TAG) || BM_elem_flag_test(l2->f, BM_ELEM_HIDDEN))
2383                                                 continue;
2384
2385                                         /* edge has exactly two neighboring faces, check angle */
2386                                         angle = angle_normalized_v3v3(f->no, l2->f->no);
2387
2388                                         /* invalidate: edge too sharp */
2389                                         if (angle < sharp) {
2390                                                 BLI_array_grow_one(stack);
2391                                                 stack[i] = l2->f;
2392                                                 i++;
2393                                         }
2394                                 }
2395                         }
2396                 }
2397         }
2398
2399         BLI_array_free(stack);
2400
2401         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2402
2403         return OPERATOR_FINISHED;
2404 }
2405
2406 void MESH_OT_faces_select_linked_flat(wmOperatorType *ot)
2407 {
2408         PropertyRNA *prop;
2409
2410         /* identifiers */
2411         ot->name = "Select Linked Flat Faces";
2412         ot->description = "Select linked faces by angle";
2413         ot->idname = "MESH_OT_faces_select_linked_flat";
2414         
2415         /* api callbacks */
2416         ot->exec = edbm_select_linked_flat_faces_exec;
2417         ot->poll = ED_operator_editmesh;
2418         
2419         /* flags */
2420         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2421         
2422         /* props */
2423         prop = RNA_def_float_rotation(ot->srna, "sharpness", 0, NULL, DEG2RADF(0.01f), DEG2RADF(180.0f),
2424                                       "Sharpness", "", DEG2RADF(1.0f), DEG2RADF(180.0f));
2425         RNA_def_property_float_default(prop, DEG2RADF(1.0f));
2426 }
2427
2428 static int edbm_select_non_manifold_exec(bContext *C, wmOperator *op)
2429 {
2430         Object *obedit = CTX_data_edit_object(C);
2431         BMEditMesh *em = BMEdit_FromObject(obedit);
2432         BMVert *v;
2433         BMEdge *e;
2434         BMIter iter;
2435
2436         /* Selects isolated verts, and edges that do not have 2 neighboring
2437          * faces
2438          */
2439         
2440         if (em->selectmode == SCE_SELECT_FACE) {
2441                 BKE_report(op->reports, RPT_ERROR, "Doesn't work in face selection mode");
2442                 return OPERATOR_CANCELLED;
2443         }
2444         
2445         BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
2446                 if (!BM_elem_flag_test(v, BM_ELEM_HIDDEN) && !BM_vert_is_manifold(v)) {
2447                         BM_vert_select_set(em->bm, v, TRUE);
2448                 }
2449         }
2450         
2451         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2452                 if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN) && !BM_edge_is_manifold(e)) {
2453                         BM_edge_select_set(em->bm, e, TRUE);
2454                 }
2455         }
2456
2457         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2458
2459         return OPERATOR_FINISHED;
2460 }
2461
2462 void MESH_OT_select_non_manifold(wmOperatorType *ot)
2463 {
2464         /* identifiers */
2465         ot->name = "Select Non Manifold";
2466         ot->description = "Select all non-manifold vertices or edges";
2467         ot->idname = "MESH_OT_select_non_manifold";
2468         
2469         /* api callbacks */
2470         ot->exec = edbm_select_non_manifold_exec;
2471         ot->poll = ED_operator_editmesh;
2472         
2473         /* flags */
2474         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2475 }
2476
2477 static int edbm_select_random_exec(bContext *C, wmOperator *op)
2478 {
2479         Object *obedit = CTX_data_edit_object(C);
2480         BMEditMesh *em = BMEdit_FromObject(obedit);
2481         BMVert *eve;
2482         BMEdge *eed;
2483         BMFace *efa;
2484         BMIter iter;
2485         float randfac =  RNA_float_get(op->ptr, "percent") / 100.0f;
2486
2487         BLI_srand(BLI_rand()); /* random seed */
2488         
2489         if (!RNA_boolean_get(op->ptr, "extend"))
2490                 EDBM_flag_disable_all(em, BM_ELEM_SELECT);
2491
2492         if (em->selectmode & SCE_SELECT_VERTEX) {
2493                 BM_ITER_MESH (eve, &iter, em->bm, BM_VERTS_OF_MESH) {
2494                         if (!BM_elem_flag_test(eve, BM_ELEM_HIDDEN) && BLI_frand() < randfac) {
2495                                 BM_vert_select_set(em->bm, eve, TRUE);
2496                         }
2497                 }
2498                 EDBM_selectmode_flush(em);
2499         }
2500         else if (em->selectmode & SCE_SELECT_EDGE) {
2501                 BM_ITER_MESH (eed, &iter, em->bm, BM_EDGES_OF_MESH) {
2502                         if (!BM_elem_flag_test(eed, BM_ELEM_HIDDEN) && BLI_frand() < randfac) {
2503                                 BM_edge_select_set(em->bm, eed, TRUE);
2504                         }
2505                 }
2506                 EDBM_selectmode_flush(em);
2507         }
2508         else {
2509                 BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) {
2510                         if (!BM_elem_flag_test(efa, BM_ELEM_HIDDEN) && BLI_frand() < randfac) {
2511                                 BM_face_select_set(em->bm, efa, TRUE);
2512                         }
2513                 }
2514                 EDBM_selectmode_flush(em);
2515         }
2516         
2517         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2518         
2519         return OPERATOR_FINISHED;
2520 }
2521
2522 void MESH_OT_select_random(wmOperatorType *ot)
2523 {
2524         /* identifiers */
2525         ot->name = "Select Random";
2526         ot->description = "Randomly select vertices";
2527         ot->idname = "MESH_OT_select_random";
2528
2529         /* api callbacks */
2530         ot->exec = edbm_select_random_exec;
2531         ot->poll = ED_operator_editmesh;
2532
2533         /* flags */
2534         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2535         
2536         /* props */
2537         RNA_def_float_percentage(ot->srna, "percent", 50.f, 0.0f, 100.0f,
2538                                  "Percent", "Percentage of elements to select randomly", 0.f, 100.0f);
2539         RNA_def_boolean(ot->srna, "extend", 0,
2540                         "Extend Selection", "Extend selection instead of deselecting everything first");
2541 }
2542
2543 static int edbm_select_next_loop_exec(bContext *C, wmOperator *UNUSED(op))
2544 {
2545         Object *obedit = CTX_data_edit_object(C);
2546         BMEditMesh *em = BMEdit_FromObject(obedit);
2547         BMFace *f;
2548         BMVert *v;
2549         BMIter iter;
2550         
2551         BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
2552                 BM_elem_flag_disable(v, BM_ELEM_TAG);
2553         }
2554         
2555         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2556                 BMLoop *l;
2557                 BMIter liter;
2558                 
2559                 BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
2560                         if (BM_elem_flag_test(l->v, BM_ELEM_SELECT)) {
2561                                 BM_elem_flag_enable(l->next->v, BM_ELEM_TAG);
2562                                 BM_vert_select_set(em->bm, l->v, FALSE);
2563                         }
2564                 }
2565         }
2566
2567         BM_ITER_MESH (v, &iter, em->bm, BM_VERTS_OF_MESH) {
2568                 if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
2569                         BM_vert_select_set(em->bm, v, TRUE);
2570                 }
2571         }
2572
2573         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit);
2574         return OPERATOR_FINISHED;
2575 }
2576
2577 void MESH_OT_select_next_loop(wmOperatorType *ot)
2578 {
2579         /* identifiers */
2580         ot->name = "Select Next Loop";
2581         ot->idname = "MESH_OT_select_next_loop";
2582         ot->description = "Select next edge loop adjacent to a selected loop";
2583
2584         /* api callbacks */
2585         ot->exec = edbm_select_next_loop_exec;
2586         ot->poll = ED_operator_editmesh;
2587         
2588         /* flags */
2589         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2590 }
2591
2592
2593 static int edbm_region_to_loop_exec(bContext *C, wmOperator *UNUSED(op))
2594 {
2595         Object *obedit = CTX_data_edit_object(C);
2596         BMEditMesh *em = BMEdit_FromObject(obedit);
2597         BMFace *f;
2598         BMEdge *e;
2599         BMIter iter;
2600
2601         BM_mesh_elem_hflag_disable_all(em->bm, BM_EDGE, BM_ELEM_TAG, FALSE);
2602
2603         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2604                 BMLoop *l1, *l2;
2605                 BMIter liter1, liter2;
2606                 
2607                 BM_ITER_ELEM (l1, &liter1, f, BM_LOOPS_OF_FACE) {
2608                         int tot = 0, totsel = 0;
2609                         
2610                         BM_ITER_ELEM (l2, &liter2, l1->e, BM_LOOPS_OF_EDGE) {
2611                                 tot++;
2612                                 totsel += BM_elem_flag_test(l2->f, BM_ELEM_SELECT) != 0;
2613                         }
2614                         
2615                         if ((tot != totsel && totsel > 0) || (totsel == 1 && tot == 1))
2616                                 BM_elem_flag_enable(l1->e, BM_ELEM_TAG);
2617                 }
2618         }
2619
2620         EDBM_flag_disable_all(em, BM_ELEM_SELECT);
2621         
2622         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2623                 if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
2624                         BM_edge_select_set(em->bm, e, TRUE);
2625                 }
2626         }
2627
2628         /* If in face-only select mode, switch to edge select mode so that
2629          * an edge-only selection is not inconsistent state */
2630         if (em->selectmode == SCE_SELECT_FACE) {
2631                 em->selectmode = SCE_SELECT_EDGE;
2632                 EDBM_selectmode_set(em);
2633                 EDBM_selectmode_to_scene(C);
2634         }
2635
2636         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2637
2638         return OPERATOR_FINISHED;
2639 }
2640
2641 void MESH_OT_region_to_loop(wmOperatorType *ot)
2642 {
2643         /* identifiers */
2644         ot->name = "Select Boundary Loop";
2645         ot->idname = "MESH_OT_region_to_loop";
2646         ot->description = "Select boundary edges around the selected faces";
2647
2648         /* api callbacks */
2649         ot->exec = edbm_region_to_loop_exec;
2650         ot->poll = ED_operator_editmesh;
2651
2652         /* flags */
2653         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2654 }
2655
2656 static int loop_find_region(BMLoop *l, int flag,
2657                             SmallHash *fhash, BMFace ***region_out)
2658 {
2659         BLI_array_declare(region);
2660         BLI_array_declare(stack);
2661         BMFace **region = NULL;
2662         BMFace **stack = NULL;
2663         BMFace *f;
2664         
2665         BLI_array_append(stack, l->f);
2666         BLI_smallhash_insert(fhash, (uintptr_t)l->f, NULL);
2667         
2668         while (BLI_array_count(stack) > 0) {
2669                 BMIter liter1, liter2;
2670                 BMLoop *l1, *l2;
2671                 
2672                 f = BLI_array_pop(stack);
2673                 BLI_array_append(region, f);
2674                 
2675                 BM_ITER_ELEM (l1, &liter1, f, BM_LOOPS_OF_FACE) {
2676                         if (BM_elem_flag_test(l1->e, flag))
2677                                 continue;
2678                         
2679                         BM_ITER_ELEM (l2, &liter2, l1->e, BM_LOOPS_OF_EDGE) {
2680                                 if (BLI_smallhash_haskey(fhash, (uintptr_t)l2->f))
2681                                         continue;
2682                                 
2683                                 BLI_array_append(stack, l2->f);
2684                                 BLI_smallhash_insert(fhash, (uintptr_t)l2->f, NULL);
2685                         }
2686                 }
2687         }
2688         
2689         BLI_array_free(stack);
2690         
2691         *region_out = region;
2692         return BLI_array_count(region);
2693 }
2694
2695 static int verg_radial(const void *va, const void *vb)
2696 {
2697         BMEdge *e1 = *((void **)va);
2698         BMEdge *e2 = *((void **)vb);
2699         int a, b;
2700         
2701         a = BM_edge_face_count(e1);
2702         b = BM_edge_face_count(e2);
2703         
2704         if (a > b)  return -1;
2705         if (a == b) return  0;
2706         if (a < b)  return  1;
2707         
2708         return -1;
2709 }
2710
2711 static int loop_find_regions(BMEditMesh *em, int selbigger)
2712 {
2713         SmallHash visithash;
2714         BMIter iter;
2715         BMEdge *e, **edges = NULL;
2716         BLI_array_declare(edges);
2717         BMFace *f;
2718         int count = 0, i;
2719         
2720         BLI_smallhash_init(&visithash);
2721         
2722         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2723                 BM_elem_flag_disable(f, BM_ELEM_TAG);
2724         }
2725
2726         BM_ITER_MESH (e, &iter, em->bm, BM_EDGES_OF_MESH) {
2727                 if (BM_elem_flag_test(e, BM_ELEM_SELECT)) {
2728                         BLI_array_append(edges, e);
2729                         BM_elem_flag_enable(e, BM_ELEM_TAG);
2730                 }
2731                 else {
2732                         BM_elem_flag_disable(e, BM_ELEM_TAG);
2733                 }
2734         }
2735         
2736         /* sort edges by radial cycle length */
2737         qsort(edges,  BLI_array_count(edges), sizeof(void *), verg_radial);
2738         
2739         for (i = 0; i < BLI_array_count(edges); i++) {
2740                 BMIter liter;
2741                 BMLoop *l;
2742                 BMFace **region = NULL, **region_out;
2743                 int c, tot = 0;
2744                 
2745                 e = edges[i];
2746                 
2747                 if (!BM_elem_flag_test(e, BM_ELEM_TAG))
2748                         continue;
2749                 
2750                 BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) {
2751                         if (BLI_smallhash_haskey(&visithash, (uintptr_t)l->f))
2752                                 continue;
2753                                                 
2754                         c = loop_find_region(l, BM_ELEM_SELECT, &visithash, &region_out);
2755
2756                         if (!region || (selbigger ? c >= tot : c < tot)) {
2757                                 /* this region is the best seen so far */
2758                                 tot = c;
2759                                 if (region) {
2760                                         /* free the previous best */
2761                                         MEM_freeN(region);
2762                                 }
2763                                 /* track the current region as the new best */
2764                                 region = region_out;
2765                         }
2766                         else {
2767                                 /* this region is not as good as best so far, just free it */
2768                                 MEM_freeN(region_out);
2769                         }
2770                 }
2771                 
2772                 if (region) {
2773                         int j;
2774                         
2775                         for (j = 0; j < tot; j++) {
2776                                 BM_elem_flag_enable(region[j], BM_ELEM_TAG);
2777                                 BM_ITER_ELEM (l, &liter, region[j], BM_LOOPS_OF_FACE) {
2778                                         BM_elem_flag_disable(l->e, BM_ELEM_TAG);
2779                                 }
2780                         }
2781                         
2782                         count += tot;
2783                         
2784                         MEM_freeN(region);
2785                 }
2786         }
2787         
2788         BLI_array_free(edges);
2789         BLI_smallhash_release(&visithash);
2790         
2791         return count;
2792 }
2793
2794 static int edbm_loop_to_region_exec(bContext *C, wmOperator *op)
2795 {
2796         Object *obedit = CTX_data_edit_object(C);
2797         BMEditMesh *em = BMEdit_FromObject(obedit);
2798         BMIter iter;
2799         BMFace *f;
2800         int selbigger = RNA_boolean_get(op->ptr, "select_bigger");
2801         int a, b;
2802
2803         /* find the set of regions with smallest number of total faces */
2804         a = loop_find_regions(em, selbigger);
2805         b = loop_find_regions(em, !selbigger);
2806         
2807         if ((a <= b) ^ selbigger) {
2808                 loop_find_regions(em, selbigger);
2809         }
2810         
2811         EDBM_flag_disable_all(em, BM_ELEM_SELECT);
2812         
2813         BM_ITER_MESH (f, &iter, em->bm, BM_FACES_OF_MESH) {
2814                 if (BM_elem_flag_test(f, BM_ELEM_TAG) && !BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
2815                         BM_face_select_set(em->bm, f, TRUE);
2816                 }
2817         }
2818         
2819         WM_event_add_notifier(C, NC_GEOM | ND_SELECT, obedit->data);
2820         return OPERATOR_FINISHED;
2821 }
2822
2823 void MESH_OT_loop_to_region(wmOperatorType *ot)
2824 {
2825         /* identifiers */
2826         ot->name = "Select Loop Inner-Region";
2827         ot->idname = "MESH_OT_loop_to_region";
2828         ot->description = "Select region of faces inside of a selected loop of edges";
2829
2830         /* api callbacks */
2831         ot->exec = edbm_loop_to_region_exec;
2832         ot->poll = ED_operator_editmesh;
2833
2834         /* flags */
2835         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
2836         
2837         RNA_def_boolean(ot->srna, "select_bigger", 0, "Select Bigger", "Select bigger regions instead of smaller ones");
2838 }