svn merge ^/trunk/blender -r43976:43995
[blender-staging.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                 /*BMIter iter;
1571                 
1572                 eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1573                 for ( ; eed; eed=BMIter_Step(&iter)) BM_Select(em->bm, eed, FALSE);
1574                 
1575                 efa = BMIter_New(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1576                 for ( ; efa; efa=BMIter_Step(&iter)) BM_Select(em->bm, efa, FALSE);*/
1577
1578                 EDBM_selectmode_flush(em);
1579         }
1580         else if (em->selectmode & SCE_SELECT_EDGE) {
1581                 /* deselect vertices, and select again based on edge select */
1582                 eve = BMIter_New(&iter, em->bm, BM_VERTS_OF_MESH, NULL);
1583                 for ( ; eve; eve=BMIter_Step(&iter)) BM_Select(em->bm, eve, FALSE);
1584                 
1585                 eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1586                 for ( ; eed; eed=BMIter_Step(&iter)) {
1587                         if (BM_TestHFlag(eed, BM_SELECT)) {
1588                                 BM_Select(em->bm, eed, TRUE);
1589                         }
1590                 }
1591                 
1592                 /* selects faces based on edge status */
1593                 EDBM_selectmode_flush(em);
1594         }
1595         else if (em->selectmode & SCE_SELECT_FACE) {
1596                 /* deselect eges, and select again based on face select */
1597                 eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1598                 for ( ; eed; eed=BMIter_Step(&iter)) BM_Select(em->bm, eed, FALSE);
1599                 
1600                 efa = BMIter_New(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1601                 for ( ; efa; efa=BMIter_Step(&iter)) {
1602                         if (BM_TestHFlag(efa, BM_SELECT)) {
1603                                 BM_Select(em->bm, efa, TRUE);
1604                         }
1605                 }
1606         }
1607 }
1608
1609 void EDBM_convertsel(BMEditMesh *em, short oldmode, short selectmode)
1610 {
1611         BMEdge *eed;
1612         BMFace *efa;
1613         BMIter iter;
1614
1615         /*have to find out what the selectionmode was previously*/
1616         if (oldmode == SCE_SELECT_VERTEX) {
1617                 if (selectmode == SCE_SELECT_EDGE) {
1618                         /*select all edges associated with every selected vertex*/
1619                         eed = BMIter_New(&iter, em->bm, BM_EDGES_OF_MESH, NULL);
1620                         for ( ; eed; eed=BMIter_Step(&iter)) {
1621                                 if ( (BM_TestHFlag(eed->v1, BM_SELECT) ||
1622                                       BM_TestHFlag(eed->v2, BM_SELECT)))
1623                                 {
1624                                         BM_Select(em->bm, eed, TRUE);
1625                                 }
1626                         }
1627                 }               
1628                 else if (selectmode == SCE_SELECT_FACE) {
1629                         BMIter liter;
1630                         BMLoop *l;
1631
1632                         /*select all faces associated with every selected vertex*/
1633                         efa = BMIter_New(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1634                         for ( ; efa; efa=BMIter_Step(&iter)) {
1635                                 l = BMIter_New(&liter, em->bm, BM_LOOPS_OF_FACE, efa);
1636                                 for (; l; l=BMIter_Step(&liter)) {
1637                                         if (BM_TestHFlag(l->v, BM_SELECT)) {
1638                                                 BM_Select(em->bm, efa, TRUE);
1639                                                 break;
1640                                         }
1641                                 }
1642                         }
1643                 }
1644         }
1645         
1646         if (oldmode == SCE_SELECT_EDGE) {
1647                 if (selectmode == SCE_SELECT_FACE) {
1648                         BMIter liter;
1649                         BMLoop *l;
1650
1651                         /*select all faces associated with every selected vertex*/
1652                         efa = BMIter_New(&iter, em->bm, BM_FACES_OF_MESH, NULL);
1653                         for ( ; efa; efa=BMIter_Step(&iter)) {
1654                                 l = BMIter_New(&liter, em->bm, BM_LOOPS_OF_FACE, efa);
1655                                 for (; l; l=BMIter_Step(&liter)) {
1656                                         if (BM_TestHFlag(l->v, BM_SELECT)) {
1657                                                 BM_Select(em->bm, efa, TRUE);
1658                                                 break;
1659                                         }
1660                                 }
1661                         }
1662                 }
1663         }
1664 }
1665
1666
1667 void EDBM_deselect_by_material(struct BMEditMesh *em, const short index, const short select)
1668 {
1669         BMIter iter;
1670         BMFace *efa;
1671
1672         BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
1673                 if (BM_TestHFlag(efa, BM_HIDDEN))
1674                         continue;
1675                 if (efa->mat_nr == index) {
1676                         BM_Select(em->bm, efa, select);
1677                 }
1678         }
1679 }
1680
1681
1682 void EDBM_select_swap(BMEditMesh *em) /* exported for UV */
1683 {
1684         BMIter iter;
1685         BMVert *eve;
1686         BMEdge *eed;
1687         BMFace *efa;
1688         
1689         if (em->bm->selectmode & SCE_SELECT_VERTEX) {
1690                 BM_ITER(eve, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
1691                         if (BM_TestHFlag(eve, BM_HIDDEN))
1692                                 continue;
1693                         BM_Select(em->bm, eve, !BM_TestHFlag(eve, BM_SELECT));
1694                 }
1695         }
1696         else if (em->selectmode & SCE_SELECT_EDGE) {
1697                 BM_ITER(eed, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
1698                         if (BM_TestHFlag(eed, BM_HIDDEN))
1699                                 continue;
1700                         BM_Select(em->bm, eed, !BM_TestHFlag(eed, BM_SELECT));
1701                 }
1702         }
1703         else {
1704                 BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
1705                         if (BM_TestHFlag(efa, BM_HIDDEN))
1706                                 continue;
1707                         BM_Select(em->bm, efa, !BM_TestHFlag(efa, BM_SELECT));
1708                 }
1709
1710         }
1711 //      if (EM_texFaceCheck())
1712 }
1713
1714 static void linked_limit_default(bContext *C, wmOperator *op)
1715 {
1716         if(!RNA_struct_property_is_set(op->ptr, "limit")) {
1717                 Object *obedit= CTX_data_edit_object(C);
1718                 BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
1719                 if(em->selectmode == SCE_SELECT_FACE)
1720                         RNA_boolean_set(op->ptr, "limit", TRUE);
1721                 else
1722                         RNA_boolean_set(op->ptr, "limit", FALSE);
1723         }
1724 }
1725
1726 static int select_linked_pick_invoke(bContext *C, wmOperator *op, wmEvent *event)
1727 {
1728         Object *obedit= CTX_data_edit_object(C);
1729         ViewContext vc;
1730         BMesh *bm;
1731         BMWalker walker;
1732         BMEditMesh *em;
1733         BMVert *eve;
1734         BMEdge *e, *eed;
1735         BMFace *efa;
1736         int sel= !RNA_boolean_get(op->ptr, "deselect");
1737
1738         int limit;
1739
1740         linked_limit_default(C, op);
1741
1742         limit = RNA_boolean_get(op->ptr, "limit");
1743
1744         /* unified_finednearest needs ogl */
1745         view3d_operator_needs_opengl(C);
1746         
1747         /* setup view context for argument to callbacks */
1748         em_setup_viewcontext(C, &vc);
1749         em = vc.em;
1750
1751         if (em->bm->totedge==0)
1752                 return OPERATOR_CANCELLED;
1753         
1754         bm= em->bm;
1755
1756         vc.mval[0]= event->mval[0];
1757         vc.mval[1]= event->mval[1];
1758         
1759         /* return warning! */
1760         
1761         if ( unified_findnearest(&vc, &eve, &eed, &efa)==0 ) {
1762                 WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1763         
1764                 return OPERATOR_CANCELLED;
1765         }
1766         
1767         if (em->selectmode == SCE_SELECT_FACE) {
1768                 BMIter iter;
1769
1770                 if (efa == NULL)
1771                         return OPERATOR_CANCELLED;
1772
1773                 if (limit) {
1774                         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
1775                                 if (!BM_TestHFlag(e, BM_SEAM)) BMO_SetFlag(bm, e, BM_SELECT);
1776                                 else                           BMO_ClearFlag(bm, e, BM_SELECT); /* is this needed ? */
1777                         }
1778                 }
1779
1780                 /* walk */
1781                 BMW_Init(&walker, bm, BMW_ISLAND,
1782                          BMW_MASK_NOP, limit ? BM_SELECT : BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP,
1783                          BMW_NIL_LAY);
1784
1785                 e = BMW_Begin(&walker, efa);
1786                 for (; efa; efa=BMW_Step(&walker)) {
1787                         BM_Select(bm, efa, sel);
1788                 }
1789                 BMW_End(&walker);
1790         }
1791         else {
1792                 if (efa) {
1793                         eed = BM_FACE_FIRST_LOOP(efa)->e;
1794                 }
1795                 else if (!eed) {
1796                         if (!eve || !eve->e)
1797                                 return OPERATOR_CANCELLED;
1798
1799                         eed = eve->e;
1800                 }
1801
1802                 BMW_Init(&walker, bm, BMW_SHELL,
1803                          BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP,
1804                          BMW_NIL_LAY);
1805
1806                 e = BMW_Begin(&walker, eed->v1);
1807                 for (; e; e=BMW_Step(&walker)) {
1808                                 BM_Select(bm, e->v1, sel);
1809                                 BM_Select(bm, e->v2, sel);
1810                 }
1811                 BMW_End(&walker);
1812                 EDBM_select_flush(em, SCE_SELECT_VERTEX);
1813         }
1814
1815         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1816         return OPERATOR_FINISHED;       
1817 }
1818
1819 void MESH_OT_select_linked_pick(wmOperatorType *ot)
1820 {
1821         /* identifiers */
1822         ot->name= "Select Linked";
1823         ot->idname= "MESH_OT_select_linked_pick";
1824         
1825         /* api callbacks */
1826         ot->invoke= select_linked_pick_invoke;
1827         ot->poll= ED_operator_editmesh;
1828         ot->description= "select/deselect all vertices linked to the edge under the mouse cursor";
1829         
1830         /* flags */
1831         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1832         
1833         RNA_def_boolean(ot->srna, "deselect", 0, "Deselect", "");
1834         RNA_def_boolean(ot->srna, "limit", 0, "Limit by Seams", "");
1835 }
1836
1837
1838 static int select_linked_exec(bContext *C, wmOperator *op)
1839 {
1840         Object *obedit= CTX_data_edit_object(C);
1841         BMEditMesh *em= ((Mesh*)obedit->data)->edit_btmesh;
1842         BMesh *bm= em->bm;
1843         BMIter iter;
1844         BMVert *v;
1845         BMEdge *e;
1846         BMWalker walker;
1847
1848         int limit;
1849
1850         linked_limit_default(C, op);
1851
1852         limit = RNA_boolean_get(op->ptr, "limit");
1853
1854         if (em->selectmode == SCE_SELECT_FACE) {
1855                 BMFace *efa;
1856
1857                 BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
1858                         if (BM_TestHFlag(efa, BM_SELECT) && !BM_TestHFlag(efa, BM_HIDDEN)) {
1859                                 BM_SetHFlag(efa, BM_TMP_TAG);
1860                         }
1861                         else {
1862                                 BM_ClearHFlag(efa, BM_TMP_TAG);
1863                         }
1864                 }
1865
1866                 if (limit) {
1867                         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
1868                                 if (!BM_TestHFlag(e, BM_SEAM)) BMO_SetFlag(bm, e, BM_SELECT);
1869                                 else                           BMO_ClearFlag(bm, e, BM_SELECT); /* is this needed ? */
1870                         }
1871                 }
1872
1873                 BMW_Init(&walker, bm, BMW_ISLAND,
1874                          BMW_MASK_NOP, limit ? BM_SELECT : BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP,
1875                          BMW_NIL_LAY);
1876
1877                 BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
1878                         if (BM_TestHFlag(efa, BM_TMP_TAG)) {
1879                                 e = BMW_Begin(&walker, efa);
1880                                 for (; efa; efa=BMW_Step(&walker)) {
1881                                         BM_Select(bm, efa, TRUE);
1882                                 }
1883                         }
1884                 }
1885                 BMW_End(&walker);
1886         }
1887         else  {
1888                 BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
1889                         if (BM_TestHFlag(v, BM_SELECT) && !BM_TestHFlag(v, BM_HIDDEN)) {
1890                                 BM_SetHFlag(v, BM_TMP_TAG);
1891                         }
1892                         else {
1893                                 BM_ClearHFlag(v, BM_TMP_TAG);
1894                         }
1895                 }
1896
1897                 BMW_Init(&walker, em->bm, BMW_SHELL,
1898                          BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP, BMW_MASK_NOP,
1899                          BMW_NIL_LAY);
1900                 BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
1901                         if (BM_TestHFlag(v, BM_TMP_TAG)) {
1902                                 e = BMW_Begin(&walker, v);
1903                                 for (; e; e=BMW_Step(&walker)) {
1904                                         BM_Select(em->bm, e->v1, TRUE);
1905                                         BM_Select(em->bm, e->v2, TRUE);
1906                                 }
1907                         }
1908                 }
1909                 BMW_End(&walker);
1910         }
1911         EDBM_select_flush(em, SCE_SELECT_VERTEX);
1912
1913         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1914
1915         return OPERATOR_FINISHED;       
1916 }
1917
1918 void MESH_OT_select_linked(wmOperatorType *ot)
1919 {
1920         /* identifiers */
1921         ot->name= "Select Linked All";
1922         ot->idname= "MESH_OT_select_linked";
1923         
1924         /* api callbacks */
1925         ot->exec= select_linked_exec;
1926         ot->poll= ED_operator_editmesh;
1927         ot->description= "Select all vertices linked to the active mesh";
1928         
1929         /* flags */
1930         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1931         
1932         RNA_def_boolean(ot->srna, "limit", 0, "Limit by Seams", "");
1933 }
1934
1935 /* ******************** **************** */
1936
1937 static int select_more(bContext *C, wmOperator *UNUSED(op))
1938 {
1939         Object *obedit= CTX_data_edit_object(C);
1940         BMEditMesh *em= (((Mesh *)obedit->data))->edit_btmesh;
1941
1942         EDBM_select_more(em);
1943
1944         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1945         return OPERATOR_FINISHED;
1946 }
1947
1948 void MESH_OT_select_more(wmOperatorType *ot)
1949 {
1950         /* identifiers */
1951         ot->name= "Select More";
1952         ot->idname= "MESH_OT_select_more";
1953         ot->description= "Select more vertices, edges or faces connected to initial selection";
1954
1955         /* api callbacks */
1956         ot->exec= select_more;
1957         ot->poll= ED_operator_editmesh;
1958         
1959         /* flags */
1960         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1961 }
1962
1963 static int select_less(bContext *C, wmOperator *UNUSED(op))
1964 {
1965         Object *obedit= CTX_data_edit_object(C);
1966         BMEditMesh *em= (((Mesh *)obedit->data))->edit_btmesh;
1967
1968         EDBM_select_less(em);
1969
1970         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
1971         return OPERATOR_FINISHED;
1972 }
1973
1974 void MESH_OT_select_less(wmOperatorType *ot)
1975 {
1976         /* identifiers */
1977         ot->name= "Select Less";
1978         ot->idname= "MESH_OT_select_less";
1979         ot->description= "Deselect vertices, edges or faces at the boundary of each selection region";
1980
1981         /* api callbacks */
1982         ot->exec= select_less;
1983         ot->poll= ED_operator_editmesh;
1984         
1985         /* flags */
1986         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
1987 }
1988
1989 /* Walk all reachable elements of the same type as h_act in breadth-first
1990    order, starting from h_act. Deselects elements if the depth when they
1991    are reached is not a multiple of "nth". */
1992 static void walker_deselect_nth(BMEditMesh *em, int nth, int offset, BMHeader *h_act)
1993 {
1994         BMHeader *h;
1995         BMesh *bm = em->bm;
1996         BMWalker walker;
1997         BMIter iter;
1998         int walktype = 0, itertype = 0, flushtype = 0;
1999         short mask_vert=0, mask_edge=0, mask_loop=0, mask_face=0;
2000
2001         /* No active element from which to start - nothing to do */
2002         if (h_act==NULL) {
2003                 return;
2004         }
2005
2006         /* Determine which type of iter, walker, and select flush to use
2007            based on type of the elements being deselected */
2008         switch (h_act->htype) {
2009         case BM_VERT:
2010                 itertype = BM_VERTS_OF_MESH;
2011                 walktype = BMW_CONNECTED_VERTEX;
2012                 flushtype = SCE_SELECT_VERTEX;
2013                 mask_vert = BM_SELECT;
2014                 break;
2015         case BM_EDGE:
2016                 itertype = BM_EDGES_OF_MESH;
2017                 walktype = BMW_SHELL;
2018                 flushtype = SCE_SELECT_EDGE;
2019                 mask_edge = BM_SELECT;
2020                 break;
2021         case BM_FACE:
2022                 itertype = BM_FACES_OF_MESH;
2023                 walktype = BMW_ISLAND;
2024                 flushtype = SCE_SELECT_FACE;
2025                 mask_face = BM_SELECT;
2026                 break;
2027         }
2028
2029         /* Walker restrictions uses BMO flags, not header flags,
2030          * so transfer BM_SELECT from HFlags onto a BMO flag layer. */
2031         BMO_push(bm, NULL);
2032         BM_ITER(h, &iter, bm, itertype, NULL) {
2033                 if (BM_TestHFlag(h, BM_SELECT)) {
2034                         BMO_SetFlag(bm, h, BM_SELECT);
2035                 }
2036         }
2037
2038         /* Walk over selected elements starting at active */
2039         BMW_Init(&walker, bm, walktype,
2040                  mask_vert, mask_edge, mask_loop, mask_face,
2041                  BMW_NIL_LAY);
2042
2043         BLI_assert(walker.order == BMW_BREADTH_FIRST);
2044         for (h = BMW_Begin(&walker, h_act); h != NULL; h = BMW_Step(&walker)) {
2045                 /* Deselect elements that aren't at "nth" depth from active */
2046                 if ((offset + BMW_CurrentDepth(&walker)) % nth) {
2047                         BM_Select(bm, h, FALSE);
2048                 }
2049         }
2050         BMW_End(&walker);
2051
2052         BMO_pop(bm);
2053
2054         /* Flush selection up */
2055         EDBM_select_flush(em, flushtype);
2056 }
2057
2058 static void deselect_nth_active(BMEditMesh *em, BMVert **v_p, BMEdge **e_p, BMFace **f_p)
2059 {
2060         BMVert *v;
2061         BMEdge *e;
2062         BMFace *f;
2063         BMIter iter;
2064         BMEditSelection *ese;
2065
2066         *v_p= NULL;
2067         *e_p= NULL;
2068         *f_p= NULL;
2069
2070         EDBM_selectmode_flush(em);
2071         ese= (BMEditSelection*)em->bm->selected.last;
2072
2073         if (ese) {
2074                 switch(ese->htype) {
2075                 case BM_VERT:
2076                         *v_p= (BMVert *)ese->data;
2077                         return;
2078                 case BM_EDGE:
2079                         *e_p= (BMEdge *)ese->data;
2080                         return;
2081                 case BM_FACE:
2082                         *f_p= (BMFace *)ese->data;
2083                         return;
2084                 }
2085         }
2086
2087         if (em->selectmode & SCE_SELECT_VERTEX) {
2088                 BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2089                         if (BM_TestHFlag(v, BM_SELECT)) {
2090                                 *v_p = v;
2091                                 return;
2092                         }
2093                 }
2094         }
2095         else if (em->selectmode & SCE_SELECT_EDGE) {
2096                 BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2097                         if (BM_TestHFlag(e, BM_SELECT)) {
2098                                 *e_p = e;
2099                                 return;
2100                         }
2101                 }
2102         }
2103         else if (em->selectmode & SCE_SELECT_FACE) {
2104                 f= BM_get_actFace(em->bm, 1);
2105                 if (f) {
2106                         *f_p= f;
2107                         return;
2108                 }
2109         }
2110 }
2111
2112 static int EM_deselect_nth(BMEditMesh *em, int nth, int offset)
2113 {
2114         BMVert *v;
2115         BMEdge *e;
2116         BMFace *f;
2117
2118         deselect_nth_active(em, &v, &e, &f);
2119
2120         if (v) {
2121                 walker_deselect_nth(em, nth, offset, &v->head);
2122                 return 1;
2123         }
2124         else if (e) {
2125                 walker_deselect_nth(em, nth, offset, &e->head);
2126                 return 1;
2127         }
2128         else if (f) {
2129                 walker_deselect_nth(em, nth, offset, &f->head);
2130                 return 1;
2131         }
2132
2133         return 0;
2134 }
2135
2136 static int mesh_select_nth_exec(bContext *C, wmOperator *op)
2137 {
2138         Object *obedit= CTX_data_edit_object(C);
2139         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2140         int nth= RNA_int_get(op->ptr, "nth");
2141         int offset= RNA_int_get(op->ptr, "offset");
2142
2143         offset = MIN2(nth, offset);
2144
2145         if (EM_deselect_nth(em, nth, offset) == 0) {
2146                 BKE_report(op->reports, RPT_ERROR, "Mesh has no active vert/edge/face");
2147                 return OPERATOR_CANCELLED;
2148         }
2149
2150         DAG_id_tag_update(obedit->data, OB_RECALC_DATA);
2151         WM_event_add_notifier(C, NC_GEOM|ND_DATA, obedit->data);
2152
2153         return OPERATOR_FINISHED;
2154 }
2155
2156
2157 void MESH_OT_select_nth(wmOperatorType *ot)
2158 {
2159         /* identifiers */
2160         ot->name= "Select Nth";
2161         ot->description= "";
2162         ot->idname= "MESH_OT_select_nth";
2163
2164         /* api callbacks */
2165         ot->exec= mesh_select_nth_exec;
2166         ot->poll= ED_operator_editmesh;
2167
2168         /* flags */
2169         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2170
2171         RNA_def_int(ot->srna, "nth", 2, 2, 100, "Nth Selection", "", 1, INT_MAX);
2172         RNA_def_int(ot->srna, "offset", 0, 0, 100, "Offset", "", 0, INT_MAX);
2173 }
2174
2175 void em_setup_viewcontext(bContext *C, ViewContext *vc)
2176 {
2177         view3d_set_viewcontext(C, vc);
2178         
2179         if (vc->obedit) {
2180                 Mesh *me= vc->obedit->data;
2181                 vc->em= me->edit_btmesh;
2182         }
2183 }
2184
2185 /* poll call for mesh operators requiring a view3d context */
2186 int EM_view3d_poll(bContext *C)
2187 {
2188         if (ED_operator_editmesh(C) && ED_operator_view3d_active(C))
2189                 return 1;
2190         return 0;
2191 }
2192
2193
2194 static int select_sharp_edges_exec(bContext *C, wmOperator *op)
2195 {
2196         /* Find edges that have exactly two neighboring faces,
2197         * check the angle between those faces, and if angle is
2198         * small enough, select the edge
2199         */
2200         Object *obedit= CTX_data_edit_object(C);
2201         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2202         BMIter iter;
2203         BMEdge *e;
2204         BMLoop *l1, *l2;
2205         float sharp = RNA_float_get(op->ptr, "sharpness"), angle;
2206
2207         sharp = DEG2RADF(sharp);
2208
2209         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2210                 if (BM_TestHFlag(e, BM_HIDDEN) || !e->l)
2211                         continue;
2212
2213                 l1 = e->l;
2214                 l2 = l1->radial_next;
2215
2216                 if (l1 == l2)
2217                         continue;
2218
2219                 /* edge has exactly two neighboring faces, check angle */
2220                 angle = saacos(l1->f->no[0]*l2->f->no[0]+l1->f->no[1]*l2->f->no[1]+l1->f->no[2]*l2->f->no[2]);
2221
2222                 if (fabsf(angle) < sharp) {
2223                         BM_Select(em->bm, e, TRUE);
2224                 }
2225
2226         }
2227
2228         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2229
2230         return OPERATOR_FINISHED;
2231 }
2232
2233 void MESH_OT_edges_select_sharp(wmOperatorType *ot)
2234 {
2235         /* identifiers */
2236         ot->name= "Select Sharp Edges";
2237         ot->description= "Marked selected edges as sharp";
2238         ot->idname= "MESH_OT_edges_select_sharp";
2239         
2240         /* api callbacks */
2241         ot->exec= select_sharp_edges_exec;
2242         ot->poll= ED_operator_editmesh;
2243         
2244         /* flags */
2245         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2246         
2247         /* props */
2248         RNA_def_float(ot->srna, "sharpness", 1.0f, 0.01f, FLT_MAX, "sharpness", "", 1.0f, 180.0f);
2249 }
2250
2251 static int select_linked_flat_faces_exec(bContext *C, wmOperator *op)
2252 {
2253         Object *obedit= CTX_data_edit_object(C);
2254         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2255         BMIter iter, liter, liter2;
2256         BMFace *f, **stack = NULL;
2257         BLI_array_declare(stack);
2258         BMLoop *l, *l2;
2259         float sharp = RNA_float_get(op->ptr, "sharpness");
2260         int i;
2261
2262         sharp = (sharp * M_PI) / 180.0;
2263
2264         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2265                 BM_ClearHFlag(f, BM_TMP_TAG);
2266         }
2267
2268         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2269                 if (BM_TestHFlag(f, BM_HIDDEN) || !BM_TestHFlag(f, BM_SELECT) || BM_TestHFlag(f, BM_TMP_TAG))
2270                         continue;
2271
2272                 BLI_array_empty(stack);
2273                 i = 1;
2274
2275                 BLI_array_growone(stack);
2276                 stack[i-1] = f;
2277
2278                 while (i) {
2279                         f = stack[i-1];
2280                         i--;
2281
2282                         BM_Select(em->bm, f, TRUE);
2283
2284                         BM_SetHFlag(f, BM_TMP_TAG);
2285
2286                         BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, f) {
2287                                 BM_ITER(l2, &liter2, em->bm, BM_LOOPS_OF_LOOP, l) {
2288                                         float angle;
2289
2290                                         if (BM_TestHFlag(l2->f, BM_TMP_TAG) || BM_TestHFlag(l2->f, BM_HIDDEN))
2291                                                 continue;
2292
2293                                         /* edge has exactly two neighboring faces, check angle */
2294                                         angle = saacos(f->no[0]*l2->f->no[0]+f->no[1]*l2->f->no[1]+f->no[2]*l2->f->no[2]);
2295
2296                                         /* invalidate: edge too sharp */
2297                                         if (fabs(angle) < sharp) {
2298                                                 BLI_array_growone(stack);
2299                                                 stack[i] = l2->f;
2300                                                 i++;
2301                                         }
2302                                 }
2303                         }
2304                 }
2305         }
2306
2307         BLI_array_free(stack);
2308
2309         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2310
2311         return OPERATOR_FINISHED;
2312 }
2313
2314 void MESH_OT_faces_select_linked_flat(wmOperatorType *ot)
2315 {
2316         /* identifiers */
2317         ot->name= "Select Linked Flat Faces";
2318         ot->description= "Select linked faces by angle";
2319         ot->idname= "MESH_OT_faces_select_linked_flat";
2320         
2321         /* api callbacks */
2322         ot->exec= select_linked_flat_faces_exec;
2323         ot->poll= ED_operator_editmesh;
2324         
2325         /* flags */
2326         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2327         
2328         /* props */
2329         RNA_def_float(ot->srna, "sharpness", 1.0f, 0.01f, FLT_MAX, "sharpness", "", 1.0f, 180.0f);
2330 }
2331
2332 static int select_non_manifold_exec(bContext *C, wmOperator *op)
2333 {
2334         Object *obedit= CTX_data_edit_object(C);
2335         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2336         BMVert *v;
2337         BMEdge *e;
2338         BMIter iter;
2339
2340         /* Selects isolated verts, and edges that do not have 2 neighboring
2341          * faces
2342          */
2343         
2344         if (em->selectmode==SCE_SELECT_FACE) {
2345                 BKE_report(op->reports, RPT_ERROR, "Doesn't work in face selection mode");
2346                 return OPERATOR_CANCELLED;
2347         }
2348         
2349         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2350                 if (!BM_TestHFlag(em->bm, BM_HIDDEN) && BM_Nonmanifold_Vert(em->bm, v)) {
2351                         BM_Select(em->bm, v, TRUE);
2352                 }
2353         }
2354         
2355         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2356                 if (!BM_TestHFlag(em->bm, BM_HIDDEN) && BM_Edge_FaceCount(e) != 2) {
2357                         BM_Select(em->bm, e, TRUE);
2358                 }
2359         }
2360
2361         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2362
2363         return OPERATOR_FINISHED;       
2364 }
2365
2366 void MESH_OT_select_non_manifold(wmOperatorType *ot)
2367 {
2368         /* identifiers */
2369         ot->name= "Select Non Manifold";
2370         ot->description= "Select all non-manifold vertices or edges";
2371         ot->idname= "MESH_OT_select_non_manifold";
2372         
2373         /* api callbacks */
2374         ot->exec= select_non_manifold_exec;
2375         ot->poll= ED_operator_editmesh;
2376         
2377         /* flags */
2378         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2379 }
2380
2381 static int mesh_select_random_exec(bContext *C, wmOperator *op)
2382 {
2383         Object *obedit= CTX_data_edit_object(C);
2384         BMEditMesh *em= ((Mesh *)obedit->data)->edit_btmesh;
2385         BMVert *eve;
2386         BMEdge *eed;
2387         BMFace *efa;
2388         BMIter iter;
2389         float randfac =  RNA_float_get(op->ptr, "percent")/100.0f;
2390
2391         BLI_srand( BLI_rand() ); /* random seed */
2392         
2393         if (!RNA_boolean_get(op->ptr, "extend"))
2394                 EDBM_clear_flag_all(em, BM_SELECT);
2395
2396         if (em->selectmode & SCE_SELECT_VERTEX) {
2397                 BM_ITER(eve, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2398                         if (!BM_TestHFlag(eve, BM_HIDDEN) && BLI_frand() < randfac) {
2399                                 BM_Select(em->bm, eve, TRUE);
2400                         }
2401                 }
2402                 EDBM_selectmode_flush(em);
2403         }
2404         else if (em->selectmode & SCE_SELECT_EDGE) {
2405                 BM_ITER(eed, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2406                         if (!BM_TestHFlag(eed, BM_HIDDEN) && BLI_frand() < randfac) {
2407                                 BM_Select(em->bm, eed, TRUE);
2408                         }
2409                 }
2410                 EDBM_selectmode_flush(em);
2411         }
2412         else {
2413                 BM_ITER(efa, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2414                         if (!BM_TestHFlag(efa, BM_HIDDEN) && BLI_frand() < randfac) {
2415                                 BM_Select(em->bm, efa, TRUE);
2416                         }
2417                 }
2418                 EDBM_selectmode_flush(em);
2419         }
2420         
2421         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2422         
2423         return OPERATOR_FINISHED;       
2424 }
2425
2426 void MESH_OT_select_random(wmOperatorType *ot)
2427 {
2428         /* identifiers */
2429         ot->name= "Select Random";
2430         ot->description= "Randomly select vertices";
2431         ot->idname= "MESH_OT_select_random";
2432
2433         /* api callbacks */
2434         ot->exec= mesh_select_random_exec;
2435         ot->poll= ED_operator_editmesh;
2436
2437         /* flags */
2438         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2439         
2440         /* props */
2441         RNA_def_float_percentage(ot->srna, "percent", 50.f, 0.0f, 100.0f, "Percent", "Percentage of elements to select randomly", 0.f, 100.0f);
2442         RNA_def_boolean(ot->srna, "extend", 0, "Extend Selection", "Extend selection instead of deselecting everything first");
2443 }
2444
2445 static int select_next_loop(bContext *C, wmOperator *UNUSED(op))
2446 {
2447         Object *obedit= CTX_data_edit_object(C);
2448         BMEditMesh *em= (((Mesh *)obedit->data))->edit_btmesh;
2449         BMFace *f;
2450         BMVert *v;
2451         BMIter iter;
2452         
2453         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2454                 BM_ClearHFlag(v, BM_TMP_TAG);
2455         }
2456         
2457         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2458                 BMLoop *l;
2459                 BMIter liter;
2460                 
2461                 BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, f) {
2462                         if (BM_TestHFlag(l->v, BM_SELECT) && !BM_TestHFlag(l->v, BM_HIDDEN)) {
2463                                 BM_SetHFlag(l->next->v, BM_TMP_TAG);
2464                                 BM_Select(em->bm, l->v, FALSE);
2465                         }
2466                 }
2467         }
2468
2469         BM_ITER(v, &iter, em->bm, BM_VERTS_OF_MESH, NULL) {
2470                 if (BM_TestHFlag(v, BM_TMP_TAG)) {
2471                         BM_Select(em->bm, v, TRUE);
2472                 }
2473         }
2474
2475         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit);
2476         return OPERATOR_FINISHED;
2477 }
2478
2479 void MESH_OT_select_next_loop(wmOperatorType *ot)
2480 {
2481         /* identifiers */
2482         ot->name= "Select Next Loop";
2483         ot->idname= "MESH_OT_select_next_loop";
2484         ot->description= "";
2485
2486         /* api callbacks */
2487         ot->exec= select_next_loop;
2488         ot->poll= ED_operator_editmesh;
2489         
2490         /* flags */
2491         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2492 }
2493
2494
2495 static int region_to_loop(bContext *C, wmOperator *UNUSED(op))
2496 {
2497         Object *obedit = CTX_data_edit_object(C);
2498         BMEditMesh *em = ((Mesh*)obedit->data)->edit_btmesh;
2499         BMFace *f;
2500         BMEdge *e;
2501         BMIter iter;
2502         ViewContext vc;
2503         
2504         em_setup_viewcontext(C, &vc);
2505         
2506         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2507                 BM_ClearHFlag(e, BM_TMP_TAG);
2508         }
2509
2510         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2511                 BMLoop *l1, *l2;
2512                 BMIter liter1, liter2;
2513                 
2514                 BM_ITER(l1, &liter1, em->bm, BM_LOOPS_OF_FACE, f) {
2515                         int tot=0, totsel=0;
2516                         
2517                         BM_ITER(l2, &liter2, em->bm, BM_LOOPS_OF_EDGE, l1->e) {
2518                                 tot++;
2519                                 totsel += BM_TestHFlag(l2->f, BM_SELECT) != 0;
2520                         }
2521                         
2522                         if ((tot != totsel && totsel > 0) || (totsel == 1 && tot == 1))
2523                                 BM_SetHFlag(l1->e, BM_TMP_TAG);
2524                 }
2525         }
2526
2527         EDBM_clear_flag_all(em, BM_SELECT);
2528         
2529         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2530                 if (BM_TestHFlag(e, BM_TMP_TAG) && !BM_TestHFlag(e, BM_HIDDEN))
2531                         BM_Select_Edge(em->bm, e, TRUE);
2532         }
2533
2534         /* If in face-only select mode, switch to edge select mode so that
2535            an edge-only selection is not inconsistent state */
2536         if (em->selectmode == SCE_SELECT_FACE) {
2537                 em->selectmode = SCE_SELECT_EDGE;
2538                 EDBM_selectmode_set(em);
2539                 EDBM_selectmode_to_scene(C);
2540         }
2541
2542         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2543
2544         return OPERATOR_FINISHED;
2545 }
2546
2547 void MESH_OT_region_to_loop(wmOperatorType *ot)
2548 {
2549         /* identifiers */
2550         ot->name= "Select Boundary Loop";
2551         ot->idname= "MESH_OT_region_to_loop";
2552
2553         /* api callbacks */
2554         ot->exec= region_to_loop;
2555         ot->poll= ED_operator_editmesh;
2556
2557         /* flags */
2558         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2559 }
2560
2561 static int loop_find_region(BMEditMesh *em, BMLoop *l, int flag, 
2562         SmallHash *fhash, BMFace ***region_out)
2563 {
2564         BLI_array_declare(region);
2565         BLI_array_declare(stack);
2566         BMFace **region = NULL, *f;
2567         BMFace **stack = NULL;
2568         
2569         BLI_array_append(stack, l->f);
2570         BLI_smallhash_insert(fhash, (uintptr_t)l->f, NULL);
2571         
2572         while (BLI_array_count(stack) > 0) {
2573                 BMIter liter1, liter2;
2574                 BMLoop *l1, *l2;
2575                 
2576                 f = BLI_array_pop(stack);
2577                 BLI_array_append(region, f);
2578                 
2579                 BM_ITER(l1, &liter1, em->bm, BM_LOOPS_OF_FACE, f) {
2580                         if (BM_TestHFlag(l1->e, flag))
2581                                 continue;
2582                         
2583                         BM_ITER(l2, &liter2, em->bm, BM_LOOPS_OF_EDGE, l1->e) {
2584                                 if (BLI_smallhash_haskey(fhash, (uintptr_t)l2->f))
2585                                         continue;
2586                                 
2587                                 BLI_array_append(stack, l2->f);
2588                                 BLI_smallhash_insert(fhash, (uintptr_t)l2->f, NULL);
2589                         }
2590                 }
2591         }
2592         
2593         BLI_array_free(stack);
2594         
2595         *region_out = region;
2596         return BLI_array_count(region);
2597 }
2598
2599 static int verg_radial(const void *va, const void *vb)
2600 {
2601         BMEdge *e1 = *((void**)va);
2602         BMEdge *e2 = *((void**)vb);
2603         int a, b;
2604         
2605         a = BM_Edge_FaceCount(e1);
2606         b = BM_Edge_FaceCount(e2);
2607         
2608         if (a > b) return -1;
2609         if (a == b) return 0;
2610         if (a < b) return 1;
2611         
2612         return -1;
2613 }
2614
2615 static int loop_find_regions(BMEditMesh *em, int selbigger)
2616 {
2617         SmallHash visithash;
2618         BMIter iter;
2619         BMEdge *e, **edges=NULL;
2620         BLI_array_declare(edges);
2621         BMFace *f;
2622         int count = 0, i;
2623         
2624         BLI_smallhash_init(&visithash);
2625         
2626         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2627                 BM_ClearHFlag(f, BM_TMP_TAG);
2628         }
2629
2630         BM_ITER(e, &iter, em->bm, BM_EDGES_OF_MESH, NULL) {
2631                 if (BM_TestHFlag(e, BM_SELECT)) {
2632                         BLI_array_append(edges, e);
2633                         BM_SetHFlag(e, BM_TMP_TAG);
2634                 }
2635                 else {
2636                         BM_ClearHFlag(e, BM_TMP_TAG);
2637                 }
2638         }
2639         
2640         /*sort edges by radial cycle length*/
2641         qsort(edges,  BLI_array_count(edges), sizeof(void*), verg_radial);
2642         
2643         for (i=0; i<BLI_array_count(edges); i++) {
2644                 BMIter liter;
2645                 BMLoop *l;
2646                 BMFace **region=NULL, **r;
2647                 int c, tot=0;
2648                 
2649                 e = edges[i];
2650                 
2651                 if (!BM_TestHFlag(e, BM_TMP_TAG))
2652                         continue;
2653                 
2654                 BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_EDGE, e) {
2655                         if (BLI_smallhash_haskey(&visithash, (uintptr_t)l->f))
2656                                 continue;
2657                                                 
2658                         c = loop_find_region(em, l, BM_SELECT, &visithash, &r);
2659
2660                         if (!region || (selbigger ? c >= tot : c < tot)) {
2661                                 /* this region is the best seen so far */
2662                                 tot = c;
2663                                 if (region) {
2664                                         /* free the previous best */
2665                                         MEM_freeN(region);
2666                                 }
2667                                 /* track the current region as the new best */
2668                                 region = r;
2669                         }
2670                         else {
2671                                 /* this region is not as good as best so far, just free it */
2672                                 MEM_freeN(r);
2673                         }
2674                 }
2675                 
2676                 if (region) {
2677                         int j;
2678                         
2679                         for (j=0; j<tot; j++) {
2680                                 BM_SetHFlag(region[j], BM_TMP_TAG);
2681                                 BM_ITER(l, &liter, em->bm, BM_LOOPS_OF_FACE, region[j]) {
2682                                         BM_ClearHFlag(l->e, BM_TMP_TAG);
2683                                 }
2684                         }
2685                         
2686                         count += tot;
2687                         
2688                         MEM_freeN(region);
2689                 }
2690         }
2691         
2692         BLI_array_free(edges);
2693         BLI_smallhash_release(&visithash);
2694         
2695         return count;
2696 }
2697
2698 static int loop_to_region(bContext *C, wmOperator *op)
2699 {
2700         Object *obedit = CTX_data_edit_object(C);
2701         BMEditMesh *em = ((Mesh*)obedit->data)->edit_btmesh;
2702         BMIter iter;
2703         BMFace *f;
2704         int selbigger = RNA_boolean_get(op->ptr, "select_bigger");
2705         int a, b;
2706
2707         /*find the set of regions with smallest number of total faces*/
2708         a = loop_find_regions(em, selbigger);
2709         b = loop_find_regions(em, !selbigger);
2710         
2711         if ((a <= b) ^ selbigger) {
2712                 loop_find_regions(em, selbigger);
2713         }
2714         
2715         EDBM_clear_flag_all(em, BM_SELECT);
2716         
2717         BM_ITER(f, &iter, em->bm, BM_FACES_OF_MESH, NULL) {
2718                 if (BM_TestHFlag(f, BM_TMP_TAG) && !BM_TestHFlag(f, BM_HIDDEN)) {
2719                         BM_Select_Face(em->bm, f, TRUE);
2720                 }
2721         }
2722         
2723         WM_event_add_notifier(C, NC_GEOM|ND_SELECT, obedit->data);
2724         return OPERATOR_FINISHED;
2725 }
2726
2727 void MESH_OT_loop_to_region(wmOperatorType *ot)
2728 {
2729         /* identifiers */
2730         ot->name= "Select Loop Inner-Region";
2731         ot->idname= "MESH_OT_loop_to_region";
2732
2733         /* api callbacks */
2734         ot->exec= loop_to_region;
2735         ot->poll= ED_operator_editmesh;
2736
2737         /* flags */
2738         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
2739         
2740         RNA_def_boolean(ot->srna, "select_bigger", 0, "Select Bigger", "Select bigger regions instead of smaller ones");
2741 }