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