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