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