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