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