skip assigning vars for inline bmesh flag funcs, just cast.
[blender.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
243         /* find the ultimate left, front, upper face (not manhattan dist!!) */
244         /* also evaluate both triangle cases in quad, since these can be non-flat */
245
246         /* put normal to the outside, and set the first direction flags in edges */
247
248         /* then check the object, and set directions / direction-flags: but only for edges with 1 or 2 faces */
249         /* this is in fact the 'select connected' */
250         
251         /* in case (selected) faces were not done: start over with 'find the ultimate ...' */
252
253 /*note: this function uses recursion, which is a little unusual for a bmop
254         function, but acceptable I think.*/
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 (cent[0]*startf->no[0] + cent[1]*startf->no[1] + cent[2]*startf->no[2] < 0.0) {
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                 co[0] /= (float)j;
392                 co[1] /= (float)j;
393                 co[2] /= (float)j;
394
395                 co[0] = v->co[0]*0.5 + co[0]*0.5;
396                 co[1] = v->co[1]*0.5 + co[1]*0.5;
397                 co[2] = v->co[2]*0.5 + co[2]*0.5;
398                 
399                 if (clipx && fabs(v->co[0]) < clipdist)
400                         co[0] = 0.0f;
401                 if (clipy && fabs(v->co[1]) < clipdist)
402                         co[1] = 0.0f;
403                 if (clipz && fabs(v->co[2]) < clipdist)
404                         co[2] = 0.0f;
405
406                 i++;
407         }
408
409         i = 0;
410         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
411                 copy_v3_v3(v->co, cos[i]);
412                 i++;
413         }
414
415         BLI_array_free(cos);
416 }
417
418 /*
419 ** compute the centroid of an ngon
420 **
421 ** NOTE: This should probably go to bmesh_polygon.c and replace the function that compute its center
422 ** basing on bounding box
423 */
424 static void ngon_center(float *v, BMesh *bm, BMFace *f)
425 {
426         BMIter  liter;
427         BMLoop  *l;
428         v[0] = v[1] = v[2] = 0;
429
430         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
431                 add_v3_v3v3(v, v, l->v->co);
432         }
433
434         if( f->len )
435         {
436                 v[0] /= f->len;
437                 v[1] /= f->len;
438                 v[2] /= f->len;
439         }
440 }
441
442 /*
443 ** compute the perimeter of an ngon
444 **
445 ** NOTE: This should probably go to bmesh_polygon.c
446 */
447 static float ngon_perimeter(BMesh *bm, BMFace *f)
448 {
449         BMIter  liter;
450         BMLoop  *l;
451         int             num_verts = 0;
452         float   v[3], sv[3];
453         float   perimeter = 0.0f;
454
455         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
456                 if( num_verts == 0 ) {
457                         sv[0] = v[0] = l->v->co[0];
458                         sv[1] = v[1] = l->v->co[1];
459                         sv[2] = v[2] = l->v->co[2];
460                         num_verts++;
461                 } else {
462                         perimeter += len_v3v3(v, l->v->co);
463                         v[0] = l->v->co[0];
464                         v[1] = l->v->co[1];
465                         v[2] = l->v->co[2];
466                         num_verts++;
467                 }
468         }
469
470         perimeter += len_v3v3(v, sv);
471
472         return perimeter;
473 }
474
475 /*
476 ** compute the fake surface of an ngon
477 ** This is done by decomposing the ngon into triangles who share the centroid of the ngon
478 ** while this method is far from being exact, it should garantee an invariance.
479 **
480 ** NOTE: This should probably go to bmesh_polygon.c
481 */
482 static float ngon_fake_area(BMesh *bm, BMFace *f)
483 {
484         BMIter  liter;
485         BMLoop  *l;
486         int             num_verts = 0;
487         float   v[3], sv[3], c[3];
488         float   area = 0.0f;
489
490         ngon_center(c, bm, f);
491
492         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
493                 if( num_verts == 0 ) {
494                         sv[0] = v[0] = l->v->co[0];
495                         sv[1] = v[1] = l->v->co[1];
496                         sv[2] = v[2] = l->v->co[2];
497                         num_verts++;
498                 } else {
499                         area += area_tri_v3(v, c, l->v->co);
500                         v[0] = l->v->co[0];
501                         v[1] = l->v->co[1];
502                         v[2] = l->v->co[2];
503                         num_verts++;
504                 }
505         }
506
507         area += area_tri_v3(v, c, sv);
508
509         return area;
510 }
511
512 /*
513 ** extra face data (computed data)
514 */
515 typedef struct tmp_face_ext {
516         BMFace          *f;                     /* the face */
517         float   c[3];                   /* center */
518         union {
519                 float   area;           /* area */
520                 float   perim;          /* perimeter */
521                 float   d;                      /* 4th component of plane (the first three being the normal) */
522                 struct Image    *t;     /* image pointer */
523         };
524 } tmp_face_ext;
525
526 /*
527 ** Select similar faces, the choices are in the enum in source/blender/bmesh/bmesh_operators.h
528 ** We select either similar faces based on material, image, area, perimeter, normal, or the coplanar faces
529 */
530 void bmesh_similarfaces_exec(BMesh *bm, BMOperator *op)
531 {
532         BMIter fm_iter;
533         BMFace *fs, *fm;
534         BMOIter fs_iter;
535         int num_sels = 0, num_total = 0, i = 0, idx = 0;
536         float angle = 0.0f;
537         tmp_face_ext *f_ext = NULL;
538         int *indices = NULL;
539         float t_no[3];  /* temporary normal */
540         int type = BMO_Get_Int(op, "type");
541         float thresh = BMO_Get_Float(op, "thresh");
542
543         num_total = BM_Count_Element(bm, BM_FACE);
544
545         /*
546         ** The first thing to do is to iterate through all the the selected items and mark them since
547         ** they will be in the selection anyway.
548         ** This will increase performance, (especially when the number of originaly selected faces is high)
549         ** so the overall complexity will be less than $O(mn)$ where is the total number of selected faces,
550         ** and n is the total number of faces
551         */
552         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
553                 if (!BMO_TestFlag(bm, fs, FACE_MARK)) { /* is this really needed ? */
554                         BMO_SetFlag(bm, fs, FACE_MARK);
555                         num_sels++;
556                 }
557         }
558
559         /* allocate memory for the selected faces indices and for all temporary faces */
560         indices = (int*)MEM_callocN(sizeof(int) * num_sels, "face indices util.c");
561         f_ext = (tmp_face_ext*)MEM_callocN(sizeof(tmp_face_ext) * num_total, "f_ext util.c");
562
563         /* loop through all the faces and fill the faces/indices structure */
564         BM_ITER(fm, &fm_iter, bm, BM_FACES_OF_MESH, NULL) {
565                 f_ext[i].f = fm;
566                 if (BMO_TestFlag(bm, fm, FACE_MARK)) {
567                         indices[idx] = i;
568                         idx++;
569                 }
570                 i++;
571         }
572
573         /*
574         ** Save us some computation burden: In case of perimeter/area/coplanar selection we compute
575         ** only once.
576         */
577         if( type == SIMFACE_PERIMETER || type == SIMFACE_AREA || type == SIMFACE_COPLANAR || type == SIMFACE_IMAGE ) {
578                 for( i = 0; i < num_total; i++ ) {
579                         switch( type ) {
580                         case SIMFACE_PERIMETER:
581                                 /* set the perimeter */
582                                 f_ext[i].perim = ngon_perimeter(bm, f_ext[i].f);
583                                 break;
584
585                         case SIMFACE_COPLANAR:
586                                 /* compute the center of the polygon */
587                                 ngon_center(f_ext[i].c, bm, f_ext[i].f);
588
589                                 /* normalize the polygon normal */
590                                 copy_v3_v3(t_no, f_ext[i].f->no);
591                                 normalize_v3(t_no);
592
593                                 /* compute the plane distance */
594                                 f_ext[i].d = dot_v3v3(t_no, f_ext[i].c);
595                                 break;
596
597                         case SIMFACE_AREA:
598                                 f_ext[i].area = ngon_fake_area(bm, f_ext[i].f);
599                                 break;
600
601                         case SIMFACE_IMAGE:
602                                 f_ext[i].t = NULL;
603                                 if( CustomData_has_layer(&(bm->pdata), CD_MTEXPOLY) ) {
604                                         MTexPoly *mtpoly = CustomData_bmesh_get(&bm->pdata, f_ext[i].f->head.data, CD_MTEXPOLY);
605                                         f_ext[i].t = mtpoly->tpage;
606                                 }
607                                 break;
608                         }
609                 }
610         }
611
612         /* now select the rest (if any) */
613         for( i = 0; i < num_total; i++ ) {
614                 fm = f_ext[i].f;
615                 if( !BMO_TestFlag(bm, fm, FACE_MARK)  && !BM_TestHFlag(fm, BM_HIDDEN) ) {
616                         int cont = 1;
617                         for( idx = 0; idx < num_sels && cont == 1; idx++ ) {
618                                 fs = f_ext[indices[idx]].f;
619                                 switch( type ) {
620                                 case SIMFACE_MATERIAL:
621                                         if( fm->mat_nr == fs->mat_nr ) {
622                                                 BMO_SetFlag(bm, fm, FACE_MARK);
623                                                 cont = 0;
624                                         }
625                                         break;
626
627                                 case SIMFACE_IMAGE:
628                                         if( f_ext[i].t == f_ext[indices[idx]].t ) {
629                                                 BMO_SetFlag(bm, fm, FACE_MARK);
630                                                 cont = 0;
631                                         }
632                                         break;
633
634                                 case SIMFACE_NORMAL:
635                                         angle = RAD2DEG(angle_v2v2(fs->no, fm->no));    /* if the angle between the normals -> 0 */
636                                         if( angle / 180.0 <= thresh ) {
637                                                 BMO_SetFlag(bm, fm, FACE_MARK);
638                                                 cont = 0;
639                                         }
640                                         break;
641
642                                 case SIMFACE_COPLANAR:
643                                         angle = RAD2DEG(angle_v2v2(fs->no, fm->no)); /* angle -> 0 */
644                                         if( angle / 180.0 <= thresh ) { /* and dot product difference -> 0 */
645                                                 if( fabs(f_ext[i].d - f_ext[indices[idx]].d) <= thresh ) {
646                                                         BMO_SetFlag(bm, fm, FACE_MARK);
647                                                         cont = 0;
648                                                 }
649                                         }
650                                         break;
651
652                                 case SIMFACE_AREA:
653                                         if( fabs(f_ext[i].area - f_ext[indices[idx]].area) <= thresh ) {
654                                                 BMO_SetFlag(bm, fm, FACE_MARK);
655                                                 cont = 0;
656                                         }
657                                         break;
658
659                                 case SIMFACE_PERIMETER:
660                                         if( fabs(f_ext[i].perim - f_ext[indices[idx]].perim) <= thresh ) {
661                                                 BMO_SetFlag(bm, fm, FACE_MARK);
662                                                 cont = 0;
663                                         }
664                                         break;
665                                 }
666                         }
667                 }
668         }
669
670         MEM_freeN(f_ext);
671         MEM_freeN(indices);
672
673         /* transfer all marked faces to the output slot */
674         BMO_Flag_To_Slot(bm, op, "faceout", FACE_MARK, BM_FACE);
675 }
676
677 /******************************************************************************
678 ** Similar Edges
679 ******************************************************************************/
680 #define EDGE_MARK       1
681
682 /*
683 ** compute the angle of an edge (i.e. the angle between two faces)
684 */
685 static float edge_angle(BMesh *bm, BMEdge *e)
686 {
687         BMIter  fiter;
688         BMFace  *f;
689         int             num_faces = 0;
690         float   n1[3], n2[3];
691         float   angle = 0.0f;
692
693         BM_ITER(f, &fiter, bm, BM_FACES_OF_EDGE, e) {
694                 if( num_faces == 0 ) {
695                         n1[0] = f->no[0];
696                         n1[1] = f->no[1];
697                         n1[2] = f->no[2];
698                         num_faces++;
699                 } else {
700                         n2[0] = f->no[0];
701                         n2[1] = f->no[1];
702                         n2[2] = f->no[2];
703                         num_faces++;
704                 }
705         }
706
707         angle = angle_v2v2(n1, n2);
708
709         return angle;
710 }
711 /*
712 ** extra edge information
713 */
714 typedef struct tmp_edge_ext {
715         BMEdge          *e;
716         union {
717                 float           dir[3];
718                 float           angle;                  /* angle between the faces*/
719         };
720
721         union {
722                 float           length;                 /* edge length */
723                 int                     faces;                  /* faces count */
724         };
725 } tmp_edge_ext;
726
727 /*
728 ** select similar edges: the choices are in the enum in source/blender/bmesh/bmesh_operators.h
729 ** choices are length, direction, face, ...
730 */
731 void bmesh_similaredges_exec(BMesh *bm, BMOperator *op)
732 {
733         BMOIter es_iter;        /* selected edges iterator */
734         BMIter  e_iter;         /* mesh edges iterator */
735         BMEdge  *es;            /* selected edge */
736         BMEdge  *e;             /* mesh edge */
737         int idx = 0, i = 0 /* , f = 0 */;
738         int *indices = NULL;
739         tmp_edge_ext *e_ext = NULL;
740         // float *angles = NULL;
741         float angle;
742
743         int num_sels = 0, num_total = 0;
744         int type = BMO_Get_Int(op, "type");
745         float thresh = BMO_Get_Float(op, "thresh");
746
747         num_total = BM_Count_Element(bm, BM_EDGE);
748
749         /* iterate through all selected edges and mark them */
750         BMO_ITER(es, &es_iter, bm, op, "edges", BM_EDGE) {
751                         BMO_SetFlag(bm, es, EDGE_MARK);
752                         num_sels++;
753         }
754
755         /* allocate memory for the selected edges indices and for all temporary edges */
756         indices = (int*)MEM_callocN(sizeof(int) * num_sels, "indices util.c");
757         e_ext = (tmp_edge_ext*)MEM_callocN(sizeof(tmp_edge_ext) * num_total, "e_ext util.c");
758
759         /* loop through all the edges and fill the edges/indices structure */
760         BM_ITER(e, &e_iter, bm, BM_EDGES_OF_MESH, NULL) {
761                 e_ext[i].e = e;
762                 if (BMO_TestFlag(bm, e, EDGE_MARK)) {
763                         indices[idx] = i;
764                         idx++;
765                 }
766                 i++;
767         }
768
769         /* save us some computation time by doing heavy computation once */
770         if( type == SIMEDGE_LENGTH || type == SIMEDGE_FACE || type == SIMEDGE_DIR ||
771                 type == SIMEDGE_FACE_ANGLE ) {
772                 for( i = 0; i < num_total; i++ ) {
773                         switch( type ) {
774                         case SIMEDGE_LENGTH:    /* compute the length of the edge */
775                                 e_ext[i].length = len_v3v3(e_ext[i].e->v1->co, e_ext[i].e->v2->co);
776                                 break;
777
778                         case SIMEDGE_DIR:               /* compute the direction */
779                                 sub_v3_v3v3(e_ext[i].dir, e_ext[i].e->v1->co, e_ext[i].e->v2->co);
780                                 break;
781
782                         case SIMEDGE_FACE:              /* count the faces around the edge */
783                                 e_ext[i].faces  = BM_Edge_FaceCount(e_ext[i].e);
784                                 break;
785
786                         case SIMEDGE_FACE_ANGLE:
787                                 e_ext[i].faces  = BM_Edge_FaceCount(e_ext[i].e);
788                                 if( e_ext[i].faces == 2 )
789                                         e_ext[i].angle = edge_angle(bm, e_ext[i].e);
790                                 break;
791                         }
792                 }
793         }
794
795         /* select the edges if any */
796         for( i = 0; i < num_total; i++ ) {
797                 e = e_ext[i].e;
798                 if( !BMO_TestFlag(bm, e, EDGE_MARK) && !BM_TestHFlag(e, BM_HIDDEN) ) {
799                         int cont = 1;
800                         for( idx = 0; idx < num_sels && cont == 1; idx++ ) {
801                                 es = e_ext[indices[idx]].e;
802                                 switch( type ) {
803                                 case SIMEDGE_LENGTH:
804                                         if( fabs(e_ext[i].length - e_ext[indices[idx]].length) <= thresh ) {
805                                                 BMO_SetFlag(bm, e, EDGE_MARK);
806                                                 cont = 0;
807                                         }
808                                         break;
809
810                                 case SIMEDGE_DIR:
811                                         /* compute the angle between the two edges */
812                                         angle = RAD2DEG(angle_v2v2(e_ext[i].dir, e_ext[indices[idx]].dir));
813
814                                         if( angle > 90.0 ) /* use the smallest angle between the edges */
815                                                 angle = fabs(angle - 180.0f);
816
817                                         if( angle / 90.0 <= thresh ) {
818                                                 BMO_SetFlag(bm, e, EDGE_MARK);
819                                                 cont = 0;
820                                         }
821                                         break;
822
823                                 case SIMEDGE_FACE:
824                                         if( e_ext[i].faces == e_ext[indices[idx]].faces ) {
825                                                 BMO_SetFlag(bm, e, EDGE_MARK);
826                                                 cont = 0;
827                                         }
828                                         break;
829
830                                 case SIMEDGE_FACE_ANGLE:
831                                         if( e_ext[i].faces == 2 ) {
832                                                 if( e_ext[indices[idx]].faces == 2 ) {
833                                                         if( fabs(e_ext[i].angle - e_ext[indices[idx]].angle) <= thresh ) {
834                                                                 BMO_SetFlag(bm, e, EDGE_MARK);
835                                                                 cont = 0;
836                                                         }
837                                                 }
838                                         } else cont = 0;
839                                         break;
840
841                                 case SIMEDGE_CREASE:
842                                         if (CustomData_has_layer(&bm->edata, CD_CREASE)) {
843                                                 float *c1, *c2;
844
845                                                 c1 = CustomData_bmesh_get(&bm->edata, e->head.data, CD_CREASE);
846                                                 c2 = CustomData_bmesh_get(&bm->edata, es->head.data, CD_CREASE);
847
848                                                 if( c1&&c2 && fabs(*c1 - *c2) <= thresh ) {
849                                                         BMO_SetFlag(bm, e, EDGE_MARK);
850                                                         cont = 0;
851                                                 }
852                                         }
853                                         break;
854
855                                 case SIMEDGE_SEAM:
856                                         if( BM_TestHFlag(e, BM_SEAM) == BM_TestHFlag(es, BM_SEAM) ) {
857                                                 BMO_SetFlag(bm, e, EDGE_MARK);
858                                                 cont = 0;
859                                         }
860                                         break;
861
862                                 case SIMEDGE_SHARP:
863                                         if( BM_TestHFlag(e, BM_SHARP) == BM_TestHFlag(es, BM_SHARP) ) {
864                                                 BMO_SetFlag(bm, e, EDGE_MARK);
865                                                 cont = 0;
866                                         }
867                                         break;
868                                 }
869                         }
870                 }
871         }
872
873         MEM_freeN(e_ext);
874         MEM_freeN(indices);
875
876         /* transfer all marked edges to the output slot */
877         BMO_Flag_To_Slot(bm, op, "edgeout", EDGE_MARK, BM_EDGE);
878 }
879
880 /******************************************************************************
881 ** Similar Vertices
882 ******************************************************************************/
883 #define VERT_MARK       1
884
885 typedef struct tmp_vert_ext {
886         BMVert *v;
887         union {
888                 int num_faces; /* adjacent faces */
889                 MDeformVert *dvert; /* deform vertex */
890         };
891 } tmp_vert_ext;
892
893 /*
894 ** select similar vertices: the choices are in the enum in source/blender/bmesh/bmesh_operators.h
895 ** choices are normal, face, vertex group...
896 */
897 void bmesh_similarverts_exec(BMesh *bm, BMOperator *op)
898 {
899         BMOIter vs_iter;        /* selected verts iterator */
900         BMIter v_iter;          /* mesh verts iterator */
901         BMVert *vs;             /* selected vertex */
902         BMVert *v;                      /* mesh vertex */
903         tmp_vert_ext *v_ext = NULL;
904         int *indices = NULL;
905         int num_total = 0, num_sels = 0, i = 0, idx = 0;
906         int type = BMO_Get_Int(op, "type");
907         float thresh = BMO_Get_Float(op, "thresh");
908
909         num_total = BM_Count_Element(bm, BM_VERT);
910
911         /* iterate through all selected edges and mark them */
912         BMO_ITER(vs, &vs_iter, bm, op, "verts", BM_VERT) {
913                 BMO_SetFlag(bm, vs, VERT_MARK);
914                 num_sels++;
915         }
916
917         /* allocate memory for the selected vertices indices and for all temporary vertices */
918         indices = (int*)MEM_mallocN(sizeof(int) * num_sels, "vertex indices");
919         v_ext = (tmp_vert_ext*)MEM_mallocN(sizeof(tmp_vert_ext) * num_total, "vertex extra");
920
921         /* loop through all the vertices and fill the vertices/indices structure */
922         BM_ITER(v, &v_iter, bm, BM_VERTS_OF_MESH, NULL) {
923                 v_ext[i].v = v;
924                 if (BMO_TestFlag(bm, v, VERT_MARK)) {
925                         indices[idx] = i;
926                         idx++;
927                 }
928
929                 switch( type ) {
930                 case SIMVERT_FACE:
931                         /* calling BM_Vert_FaceCount every time is time consumming, so call it only once per vertex */
932                         v_ext[i].num_faces      = BM_Vert_FaceCount(v);
933                         break;
934
935                 case SIMVERT_VGROUP:
936                         if( CustomData_has_layer(&(bm->vdata),CD_MDEFORMVERT) ) {
937                                 v_ext[i].dvert = CustomData_bmesh_get(&bm->vdata, v_ext[i].v->head.data, CD_MDEFORMVERT);
938                         } else v_ext[i].dvert = NULL;
939                         break;
940                 }
941
942                 i++;
943         }
944
945         /* select the vertices if any */
946         for( i = 0; i < num_total; i++ ) {
947                 v = v_ext[i].v;
948                 if( !BMO_TestFlag(bm, v, VERT_MARK) && !BM_TestHFlag(v, BM_HIDDEN) ) {
949                         int cont = 1;
950                         for( idx = 0; idx < num_sels && cont == 1; idx++ ) {
951                                 vs = v_ext[indices[idx]].v;
952                                 switch( type ) {
953                                 case SIMVERT_NORMAL:
954                                         /* compare the angle between the normals */
955                                         if( RAD2DEG(angle_v2v2(v->no, vs->no) / 180.0 <= thresh )) {
956                                                 BMO_SetFlag(bm, v, VERT_MARK);
957                                                 cont = 0;
958
959                                         }
960                                         break;
961                                 case SIMVERT_FACE:
962                                         /* number of adjacent faces */
963                                         if( v_ext[i].num_faces == v_ext[indices[idx]].num_faces ) {
964                                                 BMO_SetFlag(bm, v, VERT_MARK);
965                                                 cont = 0;
966                                         }
967                                         break;
968
969                                 case SIMVERT_VGROUP:
970                                         if( v_ext[i].dvert != NULL && v_ext[indices[idx]].dvert != NULL ) {
971                                                 int v1, v2;
972                                                 for( v1 = 0; v1 < v_ext[i].dvert->totweight && cont == 1; v1++ ) {
973                                                         for( v2 = 0; v2 < v_ext[indices[idx]].dvert->totweight; v2++ ) {
974                                                                 if( v_ext[i].dvert->dw[v1].def_nr == v_ext[indices[idx]].dvert->dw[v2].def_nr ) {
975                                                                         BMO_SetFlag(bm, v, VERT_MARK);
976                                                                         cont = 0;
977                                                                         break;
978                                                                 }
979                                                         }
980                                                 }
981                                         }
982                                         break;
983                                 }
984                         }
985                 }
986         }
987
988         MEM_freeN(indices);
989         MEM_freeN(v_ext);
990
991         BMO_Flag_To_Slot(bm, op, "vertout", VERT_MARK, BM_VERT);
992 }
993
994 /******************************************************************************
995 ** Cycle UVs for a face
996 ******************************************************************************/
997
998 void bmesh_rotateuvs_exec(BMesh *bm, BMOperator *op)
999 {
1000         BMOIter fs_iter;        /* selected faces iterator */
1001         BMFace *fs;     /* current face */
1002         BMIter l_iter;  /* iteration loop */
1003         // int n;
1004
1005         int dir = BMO_Get_Int(op, "dir");
1006
1007         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
1008                 if( CustomData_has_layer(&(bm->ldata), CD_MLOOPUV) ) {
1009                         if( dir == DIRECTION_CW ) { /* same loops direction */
1010                                 BMLoop *lf;     /* current face loops */
1011                                 MLoopUV *f_luv; /* first face loop uv */
1012                                 float p_uv[2];  /* previous uvs */
1013                                 float t_uv[2];  /* tmp uvs */
1014
1015                                 int n = 0;
1016                                 BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1017                                         /* current loop uv is the previous loop uv */
1018                                         MLoopUV *luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPUV);
1019                                         if( n == 0 ) {
1020                                                 f_luv = luv;
1021                                                 p_uv[0] = luv->uv[0];
1022                                                 p_uv[1] = luv->uv[1];
1023                                         } else {
1024                                                 t_uv[0] = luv->uv[0];
1025                                                 t_uv[1] = luv->uv[1];
1026                                                 luv->uv[0] = p_uv[0];
1027                                                 luv->uv[1] = p_uv[1];
1028                                                 p_uv[0] = t_uv[0];
1029                                                 p_uv[1] = t_uv[1];
1030                                         }
1031                                         n++;
1032                                 }
1033
1034                                 f_luv->uv[0] = p_uv[0];
1035                                 f_luv->uv[1] = p_uv[1];
1036                         } else if( dir == DIRECTION_CCW ) { /* counter loop direction */
1037                                 BMLoop *lf;     /* current face loops */
1038                                 MLoopUV *p_luv; /*previous loop uv */
1039                                 MLoopUV *luv;
1040                                 float t_uv[2];  /* current uvs */
1041
1042                                 int n = 0;
1043                                 BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1044                                         /* previous loop uv is the current loop uv */
1045                                         luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPUV);
1046                                         if( n == 0 ) {
1047                                                 p_luv = luv;
1048                                                 t_uv[0] = luv->uv[0];
1049                                                 t_uv[1] = luv->uv[1];
1050                                         } else {
1051                                                 p_luv->uv[0] = luv->uv[0];
1052                                                 p_luv->uv[1] = luv->uv[1];
1053                                                 p_luv = luv;
1054                                         }
1055                                         n++;
1056                                 }
1057
1058                                 luv->uv[0] = t_uv[0];
1059                                 luv->uv[1] = t_uv[1];
1060                         }
1061                 }
1062         }
1063
1064 }
1065
1066 /******************************************************************************
1067 ** Reverse UVs for a face
1068 ******************************************************************************/
1069
1070 void bmesh_reverseuvs_exec(BMesh *bm, BMOperator *op)
1071 {
1072         BMOIter fs_iter;        /* selected faces iterator */
1073         BMFace *fs;             /* current face */
1074         BMIter l_iter;          /* iteration loop */
1075         BLI_array_declare(uvs);
1076         float (*uvs)[2] = NULL;
1077
1078         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
1079                 if( CustomData_has_layer(&(bm->ldata), CD_MLOOPUV) ) {
1080                         BMLoop *lf;     /* current face loops */
1081                         int i = 0;
1082
1083                         BLI_array_empty(uvs);
1084                         BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1085                                 MLoopUV *luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPUV);
1086
1087                                 /* current loop uv is the previous loop uv */
1088                                 BLI_array_growone(uvs);
1089                                 uvs[i][0] = luv->uv[0];
1090                                 uvs[i][1] = luv->uv[1];
1091                                 i++;
1092                         }
1093
1094                         /* now that we have the uvs in the array, reverse! */
1095                         i = 0;
1096                         BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1097                                 /* current loop uv is the previous loop uv */
1098                                 MLoopUV *luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPUV);
1099                                 luv->uv[0] = uvs[(fs->len - i - 1)][0];
1100                                 luv->uv[1] = uvs[(fs->len - i - 1)][1];
1101                                 i++;
1102                         }
1103                 }
1104         }
1105
1106         BLI_array_free(uvs);
1107 }
1108
1109 /******************************************************************************
1110 ** Cycle colors for a face
1111 ******************************************************************************/
1112
1113 void bmesh_rotatecolors_exec(BMesh *bm, BMOperator *op)
1114 {
1115         BMOIter fs_iter;        /* selected faces iterator */
1116         BMFace *fs;     /* current face */
1117         BMIter l_iter;  /* iteration loop */
1118         // int n;
1119
1120         int dir = BMO_Get_Int(op, "dir");
1121
1122         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
1123                 if( CustomData_has_layer(&(bm->ldata), CD_MLOOPCOL) ) {
1124                         if( dir == DIRECTION_CW ) { /* same loops direction */
1125                                 BMLoop *lf;     /* current face loops */
1126                                 MLoopCol *f_lcol; /* first face loop color */
1127                                 MLoopCol p_col; /* previous color */
1128                                 MLoopCol t_col; /* tmp color */
1129
1130                                 int n = 0;
1131                                 BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1132                                         /* current loop color is the previous loop color */
1133                                         MLoopCol *luv = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPCOL);
1134                                         if( n == 0 ) {
1135                                                 f_lcol = luv;
1136                                                 p_col = *luv;
1137                                         } else {
1138                                                 t_col = *luv;
1139                                                 *luv = p_col;
1140                                                 p_col = t_col;
1141                                         }
1142                                         n++;
1143                                 }
1144
1145                                 *f_lcol = p_col;
1146                         } else if( dir == DIRECTION_CCW ) { /* counter loop direction */
1147                                 BMLoop *lf;     /* current face loops */
1148                                 MLoopCol *p_lcol; /*previous loop color */
1149                                 MLoopCol *lcol;
1150                                 MLoopCol t_col; /* current color */
1151
1152                                 int n = 0;
1153                                 BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1154                                         /* previous loop color is the current loop color */
1155                                         lcol = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPCOL);
1156                                         if( n == 0 ) {
1157                                                 p_lcol = lcol;
1158                                                 t_col = *lcol;
1159                                         } else {
1160                                                 *p_lcol = *lcol;
1161                                                 p_lcol = lcol;
1162                                         }
1163                                         n++;
1164                                 }
1165
1166                                 *lcol = t_col;
1167                         }
1168                 }
1169         }
1170 }
1171
1172 /******************************************************************************
1173 ** Reverse colors for a face
1174 ******************************************************************************/
1175
1176 void bmesh_reversecolors_exec(BMesh *bm, BMOperator *op)
1177 {
1178         BMOIter fs_iter;        /* selected faces iterator */
1179         BMFace *fs;             /* current face */
1180         BMIter l_iter;          /* iteration loop */
1181         BLI_array_declare(cols);
1182         MLoopCol *cols = NULL;
1183
1184         BMO_ITER(fs, &fs_iter, bm, op, "faces", BM_FACE) {
1185                 if( CustomData_has_layer(&(bm->ldata), CD_MLOOPCOL) ) {
1186                         BMLoop *lf;     /* current face loops */
1187                         int i = 0;
1188
1189                         BLI_array_empty(cols);
1190                         BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1191                                 MLoopCol *lcol = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPCOL);
1192
1193                                 /* current loop uv is the previous loop color */
1194                                 BLI_array_growone(cols);
1195                                 cols[i] = *lcol;
1196                                 i++;
1197                         }
1198
1199                         /* now that we have the uvs in the array, reverse! */
1200                         i = 0;
1201                         BM_ITER(lf, &l_iter, bm, BM_LOOPS_OF_FACE, fs) {
1202                                 /* current loop uv is the previous loop color */
1203                                 MLoopCol *lcol = CustomData_bmesh_get(&bm->ldata, lf->head.data, CD_MLOOPCOL);
1204                                 *lcol = cols[(fs->len - i - 1)];
1205                                 i++;
1206                         }
1207                 }
1208         }
1209
1210         BLI_array_free(cols);
1211 }
1212
1213
1214 /******************************************************************************
1215 ** shortest vertex path select
1216 ******************************************************************************/
1217
1218 typedef struct element_node {
1219         BMVert *v;      /* vertex */
1220         BMVert *parent; /* node parent id */
1221         float weight;   /* node weight */
1222         HeapNode *hn;   /* heap node */
1223 } element_node;
1224
1225 void bmesh_vertexshortestpath_exec(BMesh *bm, BMOperator *op)
1226 {
1227         BMOIter vs_iter /* , vs2_iter */;       /* selected verts iterator */
1228         BMIter v_iter;          /* mesh verts iterator */
1229         BMVert *vs, *sv, *ev;   /* starting vertex, ending vertex */
1230         BMVert *v;              /* mesh vertex */
1231         Heap *h = NULL;
1232
1233         element_node *vert_list = NULL;
1234
1235         int num_total = 0 /*, num_sels = 0 */, i = 0;
1236         int type = BMO_Get_Int(op, "type");
1237
1238         BMO_ITER(vs, &vs_iter, bm, op, "startv", BM_VERT)
1239                         sv = vs;
1240         BMO_ITER(vs, &vs_iter, bm, op, "endv", BM_VERT)
1241                         ev = vs;
1242
1243         num_total = BM_Count_Element(bm, BM_VERT);
1244
1245         /* allocate memory for the nodes */
1246         vert_list = (element_node*)MEM_mallocN(sizeof(element_node) * num_total, "vertex nodes");
1247
1248         /* iterate through all the mesh vertices */
1249         /* loop through all the vertices and fill the vertices/indices structure */
1250         i = 0;
1251         BM_ITER(v, &v_iter, bm, BM_VERTS_OF_MESH, NULL) {
1252                 vert_list[i].v = v;
1253                 vert_list[i].parent = NULL;
1254                 vert_list[i].weight = FLT_MAX;
1255                 BM_SetIndex(v, i);
1256                 i++;
1257         }
1258
1259         /*
1260         ** we now have everything we need, start Dijkstra path finding algorithm
1261         */
1262
1263         /* set the distance/weight of the start vertex to 0 */
1264         vert_list[BM_GetIndex(sv)].weight = 0.0f;
1265
1266         h = BLI_heap_new();
1267
1268         for( i = 0; i < num_total; i++ )
1269                 vert_list[i].hn = BLI_heap_insert(h, vert_list[i].weight, vert_list[i].v);
1270
1271         while( !BLI_heap_empty(h) ) {
1272                 BMEdge *e;
1273                 BMIter e_i;
1274                 float v_weight;
1275
1276                 /* take the vertex with the lowest weight out of the heap */
1277                 BMVert *v = (BMVert*)BLI_heap_popmin(h);
1278
1279                 if( vert_list[BM_GetIndex(v)].weight == FLT_MAX ) /* this means that there is no path */
1280                         break;
1281
1282                 v_weight = vert_list[BM_GetIndex(v)].weight;
1283
1284                 BM_ITER(e, &e_i, bm, BM_EDGES_OF_VERT, v) {
1285                         BMVert *u;
1286                         float e_weight = v_weight;
1287
1288                         if( type == VPATH_SELECT_EDGE_LENGTH )
1289                                 e_weight += len_v3v3(e->v1->co, e->v2->co);
1290                         else e_weight += 1.0f;
1291
1292                         u = ( e->v1 == v ) ? e->v2 : e->v1;
1293
1294                         if( e_weight < vert_list[BM_GetIndex(u)].weight ) { /* is this path shorter ? */
1295                                 /* add it if so */
1296                                 vert_list[BM_GetIndex(u)].parent = v;
1297                                 vert_list[BM_GetIndex(u)].weight = e_weight;
1298
1299                                 /* we should do a heap update node function!!! :-/ */
1300                                 BLI_heap_remove(h, vert_list[BM_GetIndex(u)].hn);
1301                                 BLI_heap_insert(h, e_weight, u);
1302                         }
1303                 }
1304         }
1305
1306         /* now we trace the path (if it exists) */
1307         v = ev;
1308
1309         while( vert_list[BM_GetIndex(v)].parent != NULL ) {
1310                 BMO_SetFlag(bm, v, VERT_MARK);
1311                 v = vert_list[BM_GetIndex(v)].parent;
1312         }
1313
1314         BLI_heap_free(h, NULL);
1315         MEM_freeN(vert_list);
1316
1317         BMO_Flag_To_Slot(bm, op, "vertout", VERT_MARK, BM_VERT);
1318 }