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