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