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