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