Style Cleanup: whitespace and some formatting.
[blender.git] / source / blender / bmesh / operators / utils.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * Contributor(s): Joseph Eagar.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 #include "MEM_guardedalloc.h"
24 #include "BKE_customdata.h"
25 #include "DNA_listBase.h"
26 #include "DNA_customdata_types.h"
27 #include "DNA_mesh_types.h"
28 #include "DNA_meshdata_types.h"
29 #include "DNA_object_types.h"
30 #include "DNA_scene_types.h"
31 #include <string.h>
32 #include "BKE_utildefines.h"
33 #include "BKE_mesh.h"
34 #include "BKE_global.h"
35 #include "BKE_DerivedMesh.h"
36 #include "BKE_cdderivedmesh.h"
37
38 #include "BLI_editVert.h"
39 #include "mesh_intern.h"
40 #include "ED_mesh.h"
41
42 #include "BLI_math.h"
43 #include "BLI_array.h"
44 #include "BLI_edgehash.h"
45
46 #include "BLI_heap.h"
47
48 #include "bmesh.h"
49
50 #include "bmesh_operators_private.h" /* own include */
51
52 /*
53  * UTILS.C
54  *
55  * utility bmesh operators, e.g. transform,
56  * translate, rotate, scale, etc.
57  *
58  */
59
60 void bmesh_makevert_exec(BMesh *bm, BMOperator *op)
61 {
62         float vec[3];
63
64         BMO_Get_Vec(op, "co", vec);
65
66         BMO_SetFlag(bm, BM_Make_Vert(bm, vec, NULL), 1);
67         BMO_Flag_To_Slot(bm, op, "newvertout", 1, BM_VERT);
68 }
69
70 void bmesh_transform_exec(BMesh *bm, BMOperator *op)
71 {
72         BMOIter iter;
73         BMVert *v;
74         float mat[4][4];
75
76         BMO_Get_Mat4(op, "mat", mat);
77
78         BMO_ITER(v, &iter, bm, op, "verts", BM_VERT) {
79                 mul_m4_v3(mat, v->co);
80         }
81 }
82
83 void bmesh_translate_exec(BMesh *bm, BMOperator *op)
84 {
85         float mat[4][4], vec[3];
86         
87         BMO_Get_Vec(op, "vec", vec);
88
89         unit_m4(mat);
90         copy_v3_v3(mat[3], vec);
91
92         BMO_CallOpf(bm, "transform mat=%m4 verts=%s", mat, op, "verts");
93 }
94
95 void bmesh_scale_exec(BMesh *bm, BMOperator *op)
96 {
97         float mat[3][3], vec[3];
98         
99         BMO_Get_Vec(op, "vec", vec);
100
101         unit_m3(mat);
102         mat[0][0] = vec[0];
103         mat[1][1] = vec[1];
104         mat[2][2] = vec[2];
105
106         BMO_CallOpf(bm, "transform mat=%m3 verts=%s", mat, op, "verts");
107 }
108
109 void bmesh_rotate_exec(BMesh *bm, BMOperator *op)
110 {
111         float vec[3];
112         
113         BMO_Get_Vec(op, "cent", vec);
114         
115         /* there has to be a proper matrix way to do this, but
116          * this is how editmesh did it and I'm too tired to think
117          * through the math right now. */
118         mul_v3_fl(vec, -1.0f);
119         BMO_CallOpf(bm, "translate verts=%s vec=%v", op, "verts", vec);
120
121         BMO_CallOpf(bm, "transform mat=%s verts=%s", op, "mat", op, "verts");
122
123         mul_v3_fl(vec, -1.0f);
124         BMO_CallOpf(bm, "translate verts=%s vec=%v", op, "verts", vec);
125 }
126
127 void bmesh_reversefaces_exec(BMesh *bm, BMOperator *op)
128 {
129         BMOIter siter;
130         BMFace *f;
131
132         BMO_ITER(f, &siter, bm, op, "faces", BM_FACE) {
133                 BM_flip_normal(bm, f);
134         }
135 }
136
137 void bmesh_edgerotate_exec(BMesh *bm, BMOperator *op)
138 {
139         BMOIter siter;
140         BMEdge *e, *e2;
141         int ccw = BMO_Get_Int(op, "ccw");
142
143         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
144                 if (!(e2 = BM_Rotate_Edge(bm, e, ccw))) {
145                         BMO_RaiseError(bm, op, BMERR_INVALID_SELECTION, "Could not rotate edge");
146                         return;
147                 }
148
149                 BMO_SetFlag(bm, e2, 1);
150         }
151
152         BMO_Flag_To_Slot(bm, op, "edgeout", 1, BM_EDGE);
153 }
154
155 #define SEL_FLAG        1
156 #define SEL_ORIG        2
157
158 static void bmesh_regionextend_extend(BMesh *bm, BMOperator *op, int usefaces)
159 {
160         BMVert *v;
161         BMEdge *e;
162         BMIter eiter;
163         BMOIter siter;
164
165         if (!usefaces) {
166                 BMO_ITER(v, &siter, bm, op, "geom", BM_VERT) {
167                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
168                                 if (!BMO_TestFlag(bm, e, SEL_ORIG))
169                                         break;
170                         }
171
172                         if (e) {
173                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
174                                         BMO_SetFlag(bm, e, SEL_FLAG);
175                                         BMO_SetFlag(bm, BM_OtherEdgeVert(e, v), SEL_FLAG);
176                                 }
177                         }
178                 }
179         }
180         else {
181                 BMIter liter, fiter;
182                 BMFace *f, *f2;
183                 BMLoop *l;
184
185                 BMO_ITER(f, &siter, bm, op, "geom", BM_FACE) {
186                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
187                                 BM_ITER(f2, &fiter, bm, BM_FACES_OF_EDGE, l->e) {
188                                         if (!BMO_TestFlag(bm, f2, SEL_ORIG))
189                                                 BMO_SetFlag(bm, f2, SEL_FLAG);
190                                 }
191                         }
192                 }
193         }
194 }
195
196 static void bmesh_regionextend_constrict(BMesh *bm, BMOperator *op, int usefaces)
197 {
198         BMVert *v;
199         BMEdge *e;
200         BMIter eiter;
201         BMOIter siter;
202
203         if (!usefaces) {
204                 BMO_ITER(v, &siter, bm, op, "geom", BM_VERT) {
205                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
206                                 if (!BMO_TestFlag(bm, e, SEL_ORIG))
207                                         break;
208                         }
209
210                         if (e) {
211                                 BMO_SetFlag(bm, v, SEL_FLAG);
212
213                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
214                                         BMO_SetFlag(bm, e, SEL_FLAG);
215                                 }
216                         }
217                 }
218         }
219         else {
220                 BMIter liter, fiter;
221                 BMFace *f, *f2;
222                 BMLoop *l;
223
224                 BMO_ITER(f, &siter, bm, op, "geom", BM_FACE) {
225                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
226                                 BM_ITER(f2, &fiter, bm, BM_FACES_OF_EDGE, l->e) {
227                                         if (!BMO_TestFlag(bm, f2, SEL_ORIG)) {
228                                                 BMO_SetFlag(bm, f, SEL_FLAG);
229                                                 break;
230                                         }
231                                 }
232                         }
233                 }
234         }
235 }
236
237 void bmesh_regionextend_exec(BMesh *bm, BMOperator *op)
238 {
239         int usefaces = BMO_Get_Int(op, "usefaces");
240         int constrict = BMO_Get_Int(op, "constrict");
241
242         BMO_Flag_Buffer(bm, op, "geom", SEL_ORIG, BM_ALL);
243
244         if (constrict)
245                 bmesh_regionextend_constrict(bm, op, usefaces);
246         else
247                 bmesh_regionextend_extend(bm, op, usefaces);
248
249         BMO_Flag_To_Slot(bm, op, "geomout", SEL_FLAG, BM_ALL);
250 }
251
252 /********* righthand faces implementation ****** */
253
254 #define FACE_VIS        1
255 #define FACE_FLAG       2
256 #define FACE_MARK       4
257 #define FACE_FLIP       8
258
259 /* NOTE: these are the original righthandfaces comment in editmesh_mods.c,
260  *       copied here for reference. */
261
262  /* based at a select-connected to witness loose objects */
263
264 /* count per edge the amount of faces
265  * find the ultimate left, front, upper face (not manhattan dist!!)
266  * also evaluate both triangle cases in quad, since these can be non-flat
267  *
268  * put normal to the outside, and set the first direction flags in edges
269  *
270  * then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces
271  * this is in fact the 'select connected'
272  *
273  * in case (selected) faces were not done: start over with 'find the ultimate ...' */
274
275 /* NOTE: this function uses recursion, which is a little unusual for a bmop
276  *       function, but acceptable I think. */
277
278 /* NOTE: BM_TMP_TAG is used on faces to tell if they are flipped. */
279
280 void bmesh_righthandfaces_exec(BMesh *bm, BMOperator *op)
281 {
282         BMIter liter, liter2;
283         BMOIter siter;
284         BMFace *f, *startf, **fstack = NULL;
285         BLI_array_declare(fstack);
286         BMLoop *l, *l2;
287         float maxx, cent[3];
288         int i, maxi, flagflip = BMO_Get_Int(op, "doflip");
289
290         startf = NULL;
291         maxx = -1.0e10;
292         
293         BMO_Flag_Buffer(bm, op, "faces", FACE_FLAG, BM_FACE);
294
295         /* find a starting face */
296         BMO_ITER(f, &siter, bm, op, "faces", BM_FACE) {
297
298                 /* clear dirty flag */
299                 BM_ClearHFlag(f, BM_TMP_TAG);
300
301                 if (BMO_TestFlag(bm, f, FACE_VIS))
302                         continue;
303
304                 if (!startf) startf = f;
305
306                 BM_Compute_Face_CenterBounds(bm, f, cent);
307
308                 cent[0] = cent[0]*cent[0] + cent[1]*cent[1] + cent[2]*cent[2];
309                 if (cent[0] > maxx) {
310                         maxx = cent[0];
311                         startf = f;
312                 }
313         }
314
315         if (!startf) return;
316
317         BM_Compute_Face_CenterBounds(bm, startf, cent);
318
319         /* make sure the starting face has the correct winding */
320         if (dot_v3v3(cent, startf->no) < 0.0f) {
321                 BM_flip_normal(bm, startf);
322                 BMO_ToggleFlag(bm, startf, FACE_FLIP);
323
324                 if (flagflip)
325                         BM_ToggleHFlag(startf, BM_TMP_TAG);
326         }
327         
328         /* now that we've found our starting face, make all connected faces
329          * have the same winding.  this is done recursively, using a manual
330          * stack (if we use simple function recursion, we'd end up overloading
331          * the stack on large meshes). */
332
333         BLI_array_growone(fstack);
334         fstack[0] = startf;
335         BMO_SetFlag(bm, startf, FACE_VIS);
336
337         i = 0;
338         maxi = 1;
339         while (i >= 0) {
340                 f = fstack[i];
341                 i--;
342
343                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
344                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_LOOP, l) {
345                                 if (!BMO_TestFlag(bm, l2->f, FACE_FLAG) || l2 == l)
346                                         continue;
347
348                                 if (!BMO_TestFlag(bm, l2->f, FACE_VIS)) {
349                                         BMO_SetFlag(bm, l2->f, FACE_VIS);
350                                         i++;
351                                         
352                                         if (l2->v == l->v) {
353                                                 BM_flip_normal(bm, l2->f);
354                                                 
355                                                 BMO_ToggleFlag(bm, l2->f, FACE_FLIP);
356                                                 if (flagflip)
357                                                         BM_ToggleHFlag(l2->f, BM_TMP_TAG);
358                                         }
359                                         else if (BM_TestHFlag(l2->f, BM_TMP_TAG) || BM_TestHFlag(l->f, BM_TMP_TAG)) {
360                                                 if (flagflip) {
361                                                         BM_ClearHFlag(l->f, BM_TMP_TAG);
362                                                         BM_ClearHFlag(l2->f, BM_TMP_TAG);
363                                                 }
364                                         }
365                                         
366                                         if (i == maxi) {
367                                                 BLI_array_growone(fstack);
368                                                 maxi++;
369                                         }
370
371                                         fstack[i] = l2->f;
372                                 }
373                         }
374                 }
375         }
376
377         BLI_array_free(fstack);
378
379         /* check if we have faces yet to do.  if so, recurse */
380         BMO_ITER(f, &siter, bm, op, "faces", BM_FACE) {
381                 if (!BMO_TestFlag(bm, f, FACE_VIS)) {
382                         bmesh_righthandfaces_exec(bm, op);
383                         break;
384                 }
385         }
386 }
387
388 void bmesh_vertexsmooth_exec(BMesh *bm, BMOperator *op)
389 {
390         BMOIter siter;
391         BMIter iter;
392         BMVert *v;
393         BMEdge *e;
394         BLI_array_declare(cos);
395         float (*cos)[3] = NULL;
396         float *co, *co2, clipdist = BMO_Get_Float(op, "clipdist");
397         int i, j, clipx, clipy, clipz;
398         
399         clipx = BMO_Get_Int(op, "mirror_clip_x");
400         clipy = BMO_Get_Int(op, "mirror_clip_y");
401         clipz = BMO_Get_Int(op, "mirror_clip_z");
402
403         i = 0;
404         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
405                 BLI_array_growone(cos);
406                 co = cos[i];
407                 
408                 j  = 0;
409                 BM_ITER(e, &iter, bm, BM_EDGES_OF_VERT, v) {
410                         co2 = BM_OtherEdgeVert(e, v)->co;
411                         add_v3_v3v3(co, co, co2);
412                         j += 1;
413                 }
414                 
415                 if (!j) {
416                         copy_v3_v3(co, v->co);
417                         i++;
418                         continue;
419                 }
420
421                 mul_v3_fl(co, 1.0f / (float)j);
422                 mid_v3_v3v3(co, co, v->co);
423
424                 if (clipx && fabsf(v->co[0]) < clipdist)
425                         co[0] = 0.0f;
426                 if (clipy && fabsf(v->co[1]) < clipdist)
427                         co[1] = 0.0f;
428                 if (clipz && fabsf(v->co[2]) < clipdist)
429                         co[2] = 0.0f;
430
431                 i++;
432         }
433
434         i = 0;
435         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
436                 copy_v3_v3(v->co, cos[i]);
437                 i++;
438         }
439
440         BLI_array_free(cos);
441 }
442
443 /*
444  * compute the perimeter of an ngon
445  *
446  * NOTE: This should probably go to bmesh_polygon.c
447  */
448 static float ngon_perimeter(BMesh *bm, BMFace *f)
449 {
450         BMIter  liter;
451         BMLoop  *l;
452         int             num_verts = 0;
453         float   v[3], sv[3];
454         float   perimeter = 0.0f;
455
456         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
457                 if (num_verts == 0) {
458                         copy_v3_v3(v, l->v->co);
459                         copy_v3_v3(sv, l->v->co);
460                 }
461                 else {
462                         perimeter += len_v3v3(v, l->v->co);
463                         copy_v3_v3(v, l->v->co);
464                 }
465                 num_verts++;
466         }
467
468         perimeter += len_v3v3(v, sv);
469
470         return perimeter;
471 }
472
473 /*
474  * compute the fake surface of an ngon
475  * This is done by decomposing the ngon into triangles who share the centroid of the ngon
476  * while this method is far from being exact, it should garantee an invariance.
477  *
478  * NOTE: This should probably go to bmesh_polygon.c
479  */
480 static float ngon_fake_area(BMesh *bm, BMFace *f)
481 {
482         BMIter  liter;
483         BMLoop  *l;
484         int             num_verts = 0;
485         float   v[3], sv[3], c[3];
486         float   area = 0.0f;
487
488         BM_Compute_Face_CenterMean(bm, f, c);
489
490         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
491                 if (num_verts == 0) {
492                         copy_v3_v3(v, l->v->co);
493                         copy_v3_v3(sv, l->v->co);
494                         num_verts++;
495                 }
496                 else {
497                         area += area_tri_v3(v, c, l->v->co);
498                         copy_v3_v3(v, l->v->co);
499                         num_verts++;
500                 }
501         }
502
503         area += area_tri_v3(v, c, sv);
504
505         return area;
506 }
507
508 /*
509  * extra face data (computed data)
510  */
511 typedef struct tmp_face_ext {
512         BMFace          *f;                     /* the face */
513         float   c[3];                   /* center */
514         union {
515                 float   area;           /* area */
516                 float   perim;          /* perimeter */
517                 float   d;                      /* 4th component of plane (the first three being the normal) */
518                 struct Image    *t;     /* image pointer */
519         };
520 } tmp_face_ext;
521
522 /*
523  * Select similar faces, the choices are in the enum in source/blender/bmesh/bmesh_operators.h
524  * We select either similar faces based on material, image, area, perimeter, normal, or the coplanar faces
525  */
526 void bmesh_similarfaces_exec(BMesh *bm, BMOperator *op)
527 {
528         BMIter fm_iter;
529         BMFace *fs, *fm;
530         BMOIter fs_iter;
531         int num_sels = 0, num_total = 0, i = 0, idx = 0;
532         float angle = 0.0f;
533         tmp_face_ext *f_ext = NULL;
534         int *indices = NULL;
535         float t_no[3];  /* temporary normal */
536         int type = BMO_Get_Int(op, "type");
537         float thresh = BMO_Get_Float(op, "thresh");
538
539         num_total = BM_Count_Element(bm, BM_FACE);
540
541         /*
542         ** The first thing to do is to iterate through all the the selected items and mark them since
543         ** they will be in the selection anyway.
544         ** This will increase performance, (especially when the number of originaly selected faces is high)
545         ** so the overall complexity will be less than $O(mn)$ where is the total number of selected faces,
546         ** and n is the total number of faces
547         */
548         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
549                 if (!BMO_TestFlag(bm, fs, FACE_MARK)) { /* is this really needed ? */
550                         BMO_SetFlag(bm, fs, FACE_MARK);
551                         num_sels++;
552                 }
553         }
554
555         /* allocate memory for the selected faces indices and for all temporary faces */
556         indices = (int *)MEM_callocN(sizeof(int) * num_sels, "face indices util.c");
557         f_ext = (tmp_face_ext *)MEM_callocN(sizeof(tmp_face_ext) * num_total, "f_ext util.c");
558
559         /* loop through all the faces and fill the faces/indices structure */
560         BM_ITER(fm, &fm_iter, bm, BM_FACES_OF_MESH, NULL) {
561                 f_ext[i].f = fm;
562                 if (BMO_TestFlag(bm, fm, FACE_MARK)) {
563                         indices[idx] = i;
564                         idx++;
565                 }
566                 i++;
567         }
568
569         /*
570         ** Save us some computation burden: In case of perimeter/area/coplanar selection we compute
571         ** only once.
572         */
573         if (type == SIMFACE_PERIMETER || type == SIMFACE_AREA || type == SIMFACE_COPLANAR || type == SIMFACE_IMAGE) {
574                 for (i = 0; i < num_total; i++) {
575                         switch (type) {
576                         case SIMFACE_PERIMETER:
577                                 /* set the perimeter */
578                                 f_ext[i].perim = ngon_perimeter(bm, f_ext[i].f);
579                                 break;
580
581                         case SIMFACE_COPLANAR:
582                                 /* compute the center of the polygon */
583                                 BM_Compute_Face_CenterMean(bm, f_ext[i].f, f_ext[i].c);
584
585                                 /* normalize the polygon normal */
586                                 copy_v3_v3(t_no, f_ext[i].f->no);
587                                 normalize_v3(t_no);
588
589                                 /* compute the plane distance */
590                                 f_ext[i].d = dot_v3v3(t_no, f_ext[i].c);
591                                 break;
592
593                         case SIMFACE_AREA:
594                                 f_ext[i].area = ngon_fake_area(bm, f_ext[i].f);
595                                 break;
596
597                         case SIMFACE_IMAGE:
598                                 f_ext[i].t = NULL;
599                                 if (CustomData_has_layer(&(bm->pdata), CD_MTEXPOLY)) {
600                                         MTexPoly *mtpoly = CustomData_bmesh_get(&bm->pdata, f_ext[i].f->head.data, CD_MTEXPOLY);
601                                         f_ext[i].t = mtpoly->tpage;
602                                 }
603                                 break;
604                         }
605                 }
606         }
607
608         /* now select the rest (if any) */
609         for (i = 0; i < num_total; i++) {
610                 fm = f_ext[i].f;
611                 if (!BMO_TestFlag(bm, fm, FACE_MARK)  && !BM_TestHFlag(fm, BM_HIDDEN)) {
612                         int cont = 1;
613                         for (idx = 0; idx < num_sels && cont == 1; idx++) {
614                                 fs = f_ext[indices[idx]].f;
615                                 switch (type) {
616                                 case SIMFACE_MATERIAL:
617                                         if (fm->mat_nr == fs->mat_nr) {
618                                                 BMO_SetFlag(bm, fm, FACE_MARK);
619                                                 cont = 0;
620                                         }
621                                         break;
622
623                                 case SIMFACE_IMAGE:
624                                         if (f_ext[i].t == f_ext[indices[idx]].t) {
625                                                 BMO_SetFlag(bm, fm, FACE_MARK);
626                                                 cont = 0;
627                                         }
628                                         break;
629
630                                 case SIMFACE_NORMAL:
631                                         angle = RAD2DEGF(angle_v3v3(fs->no, fm->no));   /* if the angle between the normals -> 0 */
632                                         if (angle / 180.0f <= thresh) {
633                                                 BMO_SetFlag(bm, fm, FACE_MARK);
634                                                 cont = 0;
635                                         }
636                                         break;
637
638                                 case SIMFACE_COPLANAR:
639                                         angle = RAD2DEGF(angle_v3v3(fs->no, fm->no)); /* angle -> 0 */
640                                         if (angle / 180.0f <= thresh) { /* and dot product difference -> 0 */
641                                                 if (fabsf(f_ext[i].d - f_ext[indices[idx]].d) <= thresh) {
642                                                         BMO_SetFlag(bm, fm, FACE_MARK);
643                                                         cont = 0;
644                                                 }
645                                         }
646                                         break;
647
648                                 case SIMFACE_AREA:
649                                         if (fabsf(f_ext[i].area - f_ext[indices[idx]].area) <= thresh) {
650                                                 BMO_SetFlag(bm, fm, FACE_MARK);
651                                                 cont = 0;
652                                         }
653                                         break;
654
655                                 case SIMFACE_PERIMETER:
656                                         if (fabsf(f_ext[i].perim - f_ext[indices[idx]].perim) <= thresh) {
657                                                 BMO_SetFlag(bm, fm, FACE_MARK);
658                                                 cont = 0;
659                                         }
660                                         break;
661                                 }
662                         }
663                 }
664         }
665
666         MEM_freeN(f_ext);
667         MEM_freeN(indices);
668
669         /* transfer all marked faces to the output slot */
670         BMO_Flag_To_Slot(bm, op, "faceout", FACE_MARK, BM_FACE);
671 }
672
673 /******************************************************************************
674 ** Similar Edges
675 **************************************************************************** */
676 #define EDGE_MARK       1
677
678 /*
679  * compute the angle of an edge (i.e. the angle between two faces)
680  */
681 static float edge_angle(BMesh *bm, BMEdge *e)
682 {
683         BMIter  fiter;
684         BMFace  *f, *f_prev = NULL;
685
686         /* first edge faces, dont account for 3+ */
687
688         BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, e) {
689                 if (f_prev == NULL) {
690                         f_prev = f;
691                 }
692                 else {
693                         return angle_v3v3(f_prev->no, f->no);
694                 }
695         }
696
697         return 0.0f;
698 }
699 /*
700  * extra edge information
701  */
702 typedef struct tmp_edge_ext {
703         BMEdge          *e;
704         union {
705                 float           dir[3];
706                 float           angle;                  /* angle between the face */
707         };
708
709         union {
710                 float           length;                 /* edge length */
711                 int                     faces;                  /* faces count */
712         };
713 } tmp_edge_ext;
714
715 /*
716  * select similar edges: the choices are in the enum in source/blender/bmesh/bmesh_operators.h
717  * choices are length, direction, face, ...
718  */
719 void bmesh_similaredges_exec(BMesh *bm, BMOperator *op)
720 {
721         BMOIter es_iter;        /* selected edges iterator */
722         BMIter  e_iter;         /* mesh edges iterator */
723         BMEdge  *es;            /* selected edge */
724         BMEdge  *e;             /* mesh edge */
725         int idx = 0, i = 0 /* , f = 0 */;
726         int *indices = NULL;
727         tmp_edge_ext *e_ext = NULL;
728         // float *angles = NULL;
729         float angle;
730
731         int num_sels = 0, num_total = 0;
732         int type = BMO_Get_Int(op, "type");
733         float thresh = BMO_Get_Float(op, "thresh");
734
735         num_total = BM_Count_Element(bm, BM_EDGE);
736
737         /* iterate through all selected edges and mark them */
738         BMO_ITER(es, &es_iter, bm, op, "edges", BM_EDGE) {
739                         BMO_SetFlag(bm, es, EDGE_MARK);
740                         num_sels++;
741         }
742
743         /* allocate memory for the selected edges indices and for all temporary edges */
744         indices = (int *)MEM_callocN(sizeof(int) * num_sels, "indices util.c");
745         e_ext = (tmp_edge_ext *)MEM_callocN(sizeof(tmp_edge_ext) * num_total, "e_ext util.c");
746
747         /* loop through all the edges and fill the edges/indices structure */
748         BM_ITER(e, &e_iter, bm, BM_EDGES_OF_MESH, NULL) {
749                 e_ext[i].e = e;
750                 if (BMO_TestFlag(bm, e, EDGE_MARK)) {
751                         indices[idx] = i;
752                         idx++;
753                 }
754                 i++;
755         }
756
757         /* save us some computation time by doing heavy computation once */
758         if (type == SIMEDGE_LENGTH || type == SIMEDGE_FACE || type == SIMEDGE_DIR || type == SIMEDGE_FACE_ANGLE) {
759                 for (i = 0; i < num_total; i++) {
760                         switch (type) {
761                         case SIMEDGE_LENGTH:    /* compute the length of the edge */
762                                 e_ext[i].length = len_v3v3(e_ext[i].e->v1->co, e_ext[i].e->v2->co);
763                                 break;
764
765                         case SIMEDGE_DIR:               /* compute the direction */
766                                 sub_v3_v3v3(e_ext[i].dir, e_ext[i].e->v1->co, e_ext[i].e->v2->co);
767                                 break;
768
769                         case SIMEDGE_FACE:              /* count the faces around the edge */
770                                 e_ext[i].faces  = BM_Edge_FaceCount(e_ext[i].e);
771                                 break;
772
773                         case SIMEDGE_FACE_ANGLE:
774                                 e_ext[i].faces  = BM_Edge_FaceCount(e_ext[i].e);
775                                 if (e_ext[i].faces == 2)
776                                         e_ext[i].angle = edge_angle(bm, e_ext[i].e);
777                                 break;
778                         }
779                 }
780         }
781
782         /* select the edges if any */
783         for (i = 0; i < num_total; i++) {
784                 e = e_ext[i].e;
785                 if (!BMO_TestFlag(bm, e, EDGE_MARK) && !BM_TestHFlag(e, BM_HIDDEN)) {
786                         int cont = 1;
787                         for (idx = 0; idx < num_sels && cont == 1; idx++) {
788                                 es = e_ext[indices[idx]].e;
789                                 switch (type) {
790                                 case SIMEDGE_LENGTH:
791                                         if (fabsf(e_ext[i].length - e_ext[indices[idx]].length) <= thresh) {
792                                                 BMO_SetFlag(bm, e, EDGE_MARK);
793                                                 cont = 0;
794                                         }
795                                         break;
796
797                                 case SIMEDGE_DIR:
798                                         /* compute the angle between the two edges */
799                                         angle = RAD2DEGF(angle_v3v3(e_ext[i].dir, e_ext[indices[idx]].dir));
800
801                                         if (angle > 90.0f) /* use the smallest angle between the edges */
802                                                 angle = fabsf(angle - 180.0f);
803
804                                         if (angle / 90.0f <= thresh) {
805                                                 BMO_SetFlag(bm, e, EDGE_MARK);
806                                                 cont = 0;
807                                         }
808                                         break;
809
810                                 case SIMEDGE_FACE:
811                                         if (e_ext[i].faces == e_ext[indices[idx]].faces) {
812                                                 BMO_SetFlag(bm, e, EDGE_MARK);
813                                                 cont = 0;
814                                         }
815                                         break;
816
817                                 case SIMEDGE_FACE_ANGLE:
818                                         if (e_ext[i].faces == 2) {
819                                                 if (e_ext[indices[idx]].faces == 2) {
820                                                         if (fabsf(e_ext[i].angle - e_ext[indices[idx]].angle) <= thresh) {
821                                                                 BMO_SetFlag(bm, e, EDGE_MARK);
822                                                                 cont = 0;
823                                                         }
824                                                 }
825                                         }
826                                         else {
827                                                 cont = 0;
828                                         }
829                                         break;
830
831                                 case SIMEDGE_CREASE:
832                                         if (CustomData_has_layer(&bm->edata, CD_CREASE)) {
833                                                 float *c1, *c2;
834
835                                                 c1 = CustomData_bmesh_get(&bm->edata, e->head.data, CD_CREASE);
836                                                 c2 = CustomData_bmesh_get(&bm->edata, es->head.data, CD_CREASE);
837
838                                                 if (c1 && c2 && fabsf(*c1 - *c2) <= thresh) {
839                                                         BMO_SetFlag(bm, e, EDGE_MARK);
840                                                         cont = 0;
841                                                 }
842                                         }
843                                         break;
844
845                                 case SIMEDGE_SEAM:
846                                         if (BM_TestHFlag(e, BM_SEAM) == BM_TestHFlag(es, BM_SEAM)) {
847                                                 BMO_SetFlag(bm, e, EDGE_MARK);
848                                                 cont = 0;
849                                         }
850                                         break;
851
852                                 case SIMEDGE_SHARP:
853                                         if (BM_TestHFlag(e, BM_SHARP) == BM_TestHFlag(es, BM_SHARP)) {
854                                                 BMO_SetFlag(bm, e, EDGE_MARK);
855                                                 cont = 0;
856                                         }
857                                         break;
858                                 }
859                         }
860                 }
861         }
862
863         MEM_freeN(e_ext);
864         MEM_freeN(indices);
865
866         /* transfer all marked edges to the output slot */
867         BMO_Flag_To_Slot(bm, op, "edgeout", EDGE_MARK, BM_EDGE);
868 }
869
870 /******************************************************************************
871 ** Similar Vertices
872 **************************************************************************** */
873 #define VERT_MARK       1
874
875 typedef struct tmp_vert_ext {
876         BMVert *v;
877         union {
878                 int num_faces; /* adjacent faces */
879                 MDeformVert *dvert; /* deform vertex */
880         };
881 } tmp_vert_ext;
882
883 /*
884  * select similar vertices: the choices are in the enum in source/blender/bmesh/bmesh_operators.h
885  * choices are normal, face, vertex group...
886  */
887 void bmesh_similarverts_exec(BMesh *bm, BMOperator *op)
888 {
889         BMOIter vs_iter;        /* selected verts iterator */
890         BMIter v_iter;          /* mesh verts iterator */
891         BMVert *vs;             /* selected vertex */
892         BMVert *v;                      /* mesh vertex */
893         tmp_vert_ext *v_ext = NULL;
894         int *indices = NULL;
895         int num_total = 0, num_sels = 0, i = 0, idx = 0;
896         int type = BMO_Get_Int(op, "type");
897         float thresh = BMO_Get_Float(op, "thresh");
898
899         num_total = BM_Count_Element(bm, BM_VERT);
900
901         /* iterate through all selected edges and mark them */
902         BMO_ITER(vs, &vs_iter, bm, op, "verts", BM_VERT) {
903                 BMO_SetFlag(bm, vs, VERT_MARK);
904                 num_sels++;
905         }
906
907         /* allocate memory for the selected vertices indices and for all temporary vertices */
908         indices = (int *)MEM_mallocN(sizeof(int) * num_sels, "vertex indices");
909         v_ext = (tmp_vert_ext *)MEM_mallocN(sizeof(tmp_vert_ext) * num_total, "vertex extra");
910
911         /* loop through all the vertices and fill the vertices/indices structure */
912         BM_ITER(v, &v_iter, bm, BM_VERTS_OF_MESH, NULL) {
913                 v_ext[i].v = v;
914                 if (BMO_TestFlag(bm, v, VERT_MARK)) {
915                         indices[idx] = i;
916                         idx++;
917                 }
918
919                 switch (type) {
920                 case SIMVERT_FACE:
921                         /* calling BM_Vert_FaceCount every time is time consumming, so call it only once per vertex */
922                         v_ext[i].num_faces      = BM_Vert_FaceCount(v);
923                         break;
924
925                 case SIMVERT_VGROUP:
926                         if (CustomData_has_layer(&(bm->vdata), CD_MDEFORMVERT)) {
927                                 v_ext[i].dvert = CustomData_bmesh_get(&bm->vdata, v_ext[i].v->head.data, CD_MDEFORMVERT);
928                         }
929                         else {
930                                 v_ext[i].dvert = NULL;
931                         }
932                         break;
933                 }
934
935                 i++;
936         }
937
938         /* select the vertices if any */
939         for (i = 0; i < num_total; i++) {
940                 v = v_ext[i].v;
941                 if (!BMO_TestFlag(bm, v, VERT_MARK) && !BM_TestHFlag(v, BM_HIDDEN)) {
942                         int cont = 1;
943                         for (idx = 0; idx < num_sels && cont == 1; idx++) {
944                                 vs = v_ext[indices[idx]].v;
945                                 switch (type) {
946                                 case SIMVERT_NORMAL:
947                                         /* compare the angle between the normals */
948                                         if (RAD2DEGF(angle_v3v3(v->no, vs->no)) / 180.0f <= thresh) {
949                                                 BMO_SetFlag(bm, v, VERT_MARK);
950                                                 cont = 0;
951                                         }
952                                         break;
953                                 case SIMVERT_FACE:
954                                         /* number of adjacent faces */
955                                         if (v_ext[i].num_faces == v_ext[indices[idx]].num_faces) {
956                                                 BMO_SetFlag(bm, v, VERT_MARK);
957                                                 cont = 0;
958                                         }
959                                         break;
960
961                                 case SIMVERT_VGROUP:
962                                         if (v_ext[i].dvert != NULL && v_ext[indices[idx]].dvert != NULL) {
963                                                 int v1, v2;
964                                                 for (v1 = 0; v1 < v_ext[i].dvert->totweight && cont == 1; v1++) {
965                                                         for (v2 = 0; v2 < v_ext[indices[idx]].dvert->totweight; v2++) {
966                                                                 if (v_ext[i].dvert->dw[v1].def_nr == v_ext[indices[idx]].dvert->dw[v2].def_nr) {
967                                                                         BMO_SetFlag(bm, v, VERT_MARK);
968                                                                         cont = 0;
969                                                                         break;
970                                                                 }
971                                                         }
972                                                 }
973                                         }
974                                         break;
975                                 }
976                         }
977                 }
978         }
979
980         MEM_freeN(indices);
981         MEM_freeN(v_ext);
982
983         BMO_Flag_To_Slot(bm, op, "vertout", VERT_MARK, BM_VERT);
984 }
985
986 /******************************************************************************
987 ** Cycle UVs for a face
988 **************************************************************************** */
989
990 void bmesh_rotateuvs_exec(BMesh *bm, BMOperator *op)
991 {
992         BMOIter fs_iter;        /* selected faces iterator */
993         BMFace *fs;     /* current face */
994         BMIter l_iter;  /* iteration loop */
995         // int n;
996
997         int dir = BMO_Get_Int(op, "dir");
998
999         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
1000                 if (CustomData_has_layer(&(bm->ldata), CD_MLOOPUV)) {
1001                         if (dir == DIRECTION_CW) { /* same loops direction */
1002                                 BMLoop *lf;     /* current face loops */
1003                                 MLoopUV *f_luv; /* first face loop uv */
1004                                 float p_uv[2];  /* previous uvs */
1005                                 float t_uv[2];  /* tmp uvs */
1006
1007                                 int n = 0;
1008                                 BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1009                                         /* current loop uv is the previous loop uv */
1010                                         MLoopUV *luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPUV);
1011                                         if (n == 0) {
1012                                                 f_luv = luv;
1013                                                 copy_v2_v2(p_uv, luv->uv);
1014                                         }
1015                                         else {
1016                                                 copy_v2_v2(t_uv, luv->uv);
1017                                                 copy_v2_v2(luv->uv, p_uv);
1018                                                 copy_v2_v2(p_uv, t_uv);
1019                                         }
1020                                         n++;
1021                                 }
1022
1023                                 copy_v2_v2(f_luv->uv, p_uv);
1024                         }
1025                         else if (dir == DIRECTION_CCW) { /* counter loop direction */
1026                                 BMLoop *lf;     /* current face loops */
1027                                 MLoopUV *p_luv; /* previous loop uv */
1028                                 MLoopUV *luv;
1029                                 float t_uv[2];  /* current uvs */
1030
1031                                 int n = 0;
1032                                 BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1033                                         /* previous loop uv is the current loop uv */
1034                                         luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPUV);
1035                                         if (n == 0) {
1036                                                 p_luv = luv;
1037                                                 copy_v2_v2(t_uv, luv->uv);
1038                                         }
1039                                         else {
1040                                                 copy_v2_v2(p_luv->uv, luv->uv);
1041                                                 p_luv = luv;
1042                                         }
1043                                         n++;
1044                                 }
1045
1046                                 copy_v2_v2(luv->uv, t_uv);
1047                         }
1048                 }
1049         }
1050
1051 }
1052
1053 /******************************************************************************
1054 ** Reverse UVs for a face
1055 **************************************************************************** */
1056
1057 void bmesh_reverseuvs_exec(BMesh *bm, BMOperator *op)
1058 {
1059         BMOIter fs_iter;        /* selected faces iterator */
1060         BMFace *fs;             /* current face */
1061         BMIter l_iter;          /* iteration loop */
1062         BLI_array_declare(uvs);
1063         float (*uvs)[2] = NULL;
1064
1065         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
1066                 if (CustomData_has_layer(&(bm->ldata), CD_MLOOPUV)) {
1067                         BMLoop *lf;     /* current face loops */
1068                         int i = 0;
1069
1070                         BLI_array_empty(uvs);
1071                         BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1072                                 MLoopUV *luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPUV);
1073
1074                                 /* current loop uv is the previous loop uv */
1075                                 BLI_array_growone(uvs);
1076                                 uvs[i][0] = luv->uv[0];
1077                                 uvs[i][1] = luv->uv[1];
1078                                 i++;
1079                         }
1080
1081                         /* now that we have the uvs in the array, reverse! */
1082                         i = 0;
1083                         BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1084                                 /* current loop uv is the previous loop uv */
1085                                 MLoopUV *luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPUV);
1086                                 luv->uv[0] = uvs[(fs->len - i - 1)][0];
1087                                 luv->uv[1] = uvs[(fs->len - i - 1)][1];
1088                                 i++;
1089                         }
1090                 }
1091         }
1092
1093         BLI_array_free(uvs);
1094 }
1095
1096 /******************************************************************************
1097 ** Cycle colors for a face
1098 **************************************************************************** */
1099
1100 void bmesh_rotatecolors_exec(BMesh *bm, BMOperator *op)
1101 {
1102         BMOIter fs_iter;        /* selected faces iterator */
1103         BMFace *fs;     /* current face */
1104         BMIter l_iter;  /* iteration loop */
1105         // int n;
1106
1107         int dir = BMO_Get_Int(op, "dir");
1108
1109         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
1110                 if (CustomData_has_layer(&(bm->ldata), CD_MLOOPCOL)) {
1111                         if (dir == DIRECTION_CW) { /* same loops direction */
1112                                 BMLoop *lf;     /* current face loops */
1113                                 MLoopCol *f_lcol; /* first face loop color */
1114                                 MLoopCol p_col; /* previous color */
1115                                 MLoopCol t_col; /* tmp color */
1116
1117                                 int n = 0;
1118                                 BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1119                                         /* current loop color is the previous loop color */
1120                                         MLoopCol *luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPCOL);
1121                                         if (n == 0) {
1122                                                 f_lcol = luv;
1123                                                 p_col = *luv;
1124                                         }
1125                                         else {
1126                                                 t_col = *luv;
1127                                                 *luv = p_col;
1128                                                 p_col = t_col;
1129                                         }
1130                                         n++;
1131                                 }
1132
1133                                 *f_lcol = p_col;
1134                         }
1135                         else if (dir == DIRECTION_CCW) { /* counter loop direction */
1136                                 BMLoop *lf;     /* current face loops */
1137                                 MLoopCol *p_lcol; /* previous loop color */
1138                                 MLoopCol *lcol;
1139                                 MLoopCol t_col; /* current color */
1140
1141                                 int n = 0;
1142                                 BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1143                                         /* previous loop color is the current loop color */
1144                                         lcol = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPCOL);
1145                                         if (n == 0) {
1146                                                 p_lcol = lcol;
1147                                                 t_col = *lcol;
1148                                         }
1149                                         else {
1150                                                 *p_lcol = *lcol;
1151                                                 p_lcol = lcol;
1152                                         }
1153                                         n++;
1154                                 }
1155
1156                                 *lcol = t_col;
1157                         }
1158                 }
1159         }
1160 }
1161
1162 /******************************************************************************
1163 ** Reverse colors for a face
1164 **************************************************************************** */
1165
1166 void bmesh_reversecolors_exec(BMesh *bm, BMOperator *op)
1167 {
1168         BMOIter fs_iter;        /* selected faces iterator */
1169         BMFace *fs;             /* current face */
1170         BMIter l_iter;          /* iteration loop */
1171         BLI_array_declare(cols);
1172         MLoopCol *cols = NULL;
1173
1174         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
1175                 if (CustomData_has_layer(&(bm->ldata), CD_MLOOPCOL)) {
1176                         BMLoop *lf;     /* current face loops */
1177                         int i = 0;
1178
1179                         BLI_array_empty(cols);
1180                         BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1181                                 MLoopCol *lcol = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPCOL);
1182
1183                                 /* current loop uv is the previous loop color */
1184                                 BLI_array_growone(cols);
1185                                 cols[i] = *lcol;
1186                                 i++;
1187                         }
1188
1189                         /* now that we have the uvs in the array, reverse! */
1190                         i = 0;
1191                         BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1192                                 /* current loop uv is the previous loop color */
1193                                 MLoopCol *lcol = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPCOL);
1194                                 *lcol = cols[(fs->len - i - 1)];
1195                                 i++;
1196                         }
1197                 }
1198         }
1199
1200         BLI_array_free(cols);
1201 }
1202
1203
1204 /******************************************************************************
1205 ** shortest vertex path select
1206 **************************************************************************** */
1207
1208 typedef struct element_node {
1209         BMVert *v;      /* vertex */
1210         BMVert *parent; /* node parent id */
1211         float weight;   /* node weight */
1212         HeapNode *hn;   /* heap node */
1213 } element_node;
1214
1215 void bmesh_vertexshortestpath_exec(BMesh *bm, BMOperator *op)
1216 {
1217         BMOIter vs_iter /* , vs2_iter */;       /* selected verts iterator */
1218         BMIter v_iter;          /* mesh verts iterator */
1219         BMVert *vs, *sv, *ev;   /* starting vertex, ending vertex */
1220         BMVert *v;              /* mesh vertex */
1221         Heap *h = NULL;
1222
1223         element_node *vert_list = NULL;
1224
1225         int num_total = 0 /*, num_sels = 0 */, i = 0;
1226         int type = BMO_Get_Int(op, "type");
1227
1228         BMO_ITER(vs, &vs_iter, bm, op, "startv", BM_VERT)
1229                         sv = vs;
1230         BMO_ITER(vs, &vs_iter, bm, op, "endv", BM_VERT)
1231                         ev = vs;
1232
1233         num_total = BM_Count_Element(bm, BM_VERT);
1234
1235         /* allocate memory for the nodes */
1236         vert_list = (element_node *)MEM_mallocN(sizeof(element_node) * num_total, "vertex nodes");
1237
1238         /* iterate through all the mesh vertices */
1239         /* loop through all the vertices and fill the vertices/indices structure */
1240         i = 0;
1241         BM_ITER(v, &v_iter, bm, BM_VERTS_OF_MESH, NULL) {
1242                 vert_list[i].v = v;
1243                 vert_list[i].parent = NULL;
1244                 vert_list[i].weight = FLT_MAX;
1245                 BM_SetIndex(v, i); /* set_inline */
1246                 i++;
1247         }
1248         bm->elem_index_dirty &= ~BM_VERT;
1249
1250         /*
1251         ** we now have everything we need, start Dijkstra path finding algorithm
1252         */
1253
1254         /* set the distance/weight of the start vertex to 0 */
1255         vert_list[BM_GetIndex(sv)].weight = 0.0f;
1256
1257         h = BLI_heap_new();
1258
1259         for (i = 0; i < num_total; i++) {
1260                 vert_list[i].hn = BLI_heap_insert(h, vert_list[i].weight, vert_list[i].v);
1261         }
1262
1263         while (!BLI_heap_empty(h)) {
1264                 BMEdge *e;
1265                 BMIter e_i;
1266                 float v_weight;
1267
1268                 /* take the vertex with the lowest weight out of the heap */
1269                 BMVert *v = (BMVert *)BLI_heap_popmin(h);
1270
1271                 if (vert_list[BM_GetIndex(v)].weight == FLT_MAX) /* this means that there is no path */
1272                         break;
1273
1274                 v_weight = vert_list[BM_GetIndex(v)].weight;
1275
1276                 BM_ITER(e, &e_i, bm, BM_EDGES_OF_VERT, v) {
1277                         BMVert *u;
1278                         float e_weight = v_weight;
1279
1280                         if (type == VPATH_SELECT_EDGE_LENGTH)
1281                                 e_weight += len_v3v3(e->v1->co, e->v2->co);
1282                         else e_weight += 1.0f;
1283
1284                         u = (e->v1 == v) ? e->v2 : e->v1;
1285
1286                         if (e_weight < vert_list[BM_GetIndex(u)].weight) { /* is this path shorter ? */
1287                                 /* add it if so */
1288                                 vert_list[BM_GetIndex(u)].parent = v;
1289                                 vert_list[BM_GetIndex(u)].weight = e_weight;
1290
1291                                 /* we should do a heap update node function!!! :-/ */
1292                                 BLI_heap_remove(h, vert_list[BM_GetIndex(u)].hn);
1293                                 BLI_heap_insert(h, e_weight, u);
1294                         }
1295                 }
1296         }
1297
1298         /* now we trace the path (if it exists) */
1299         v = ev;
1300
1301         while (vert_list[BM_GetIndex(v)].parent != NULL) {
1302                 BMO_SetFlag(bm, v, VERT_MARK);
1303                 v = vert_list[BM_GetIndex(v)].parent;
1304         }
1305
1306         BLI_heap_free(h, NULL);
1307         MEM_freeN(vert_list);
1308
1309         BMO_Flag_To_Slot(bm, op, "vertout", VERT_MARK, BM_VERT);
1310 }