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