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