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