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