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