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