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