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