Blender V5.3
bmesh_path_uv.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include "MEM_guardedalloc.h"
12
13#include <algorithm>
14
15#include "BLI_heap_simple.hh"
16#include "BLI_linklist.hh"
17#include "BLI_math_geom_c.hh"
18#include "BLI_math_vector_c.hh"
19
20#include "bmesh.hh"
21#include "bmesh_path_uv.hh" /* own include */
22#include "intern/bmesh_query.hh"
24
25namespace blender {
26
27#define COST_INIT_MAX FLT_MAX
28
29/* -------------------------------------------------------------------- */
32
38static float step_cost_3_v2_ex(
39 const float v1[2], const float v2[2], const float v3[2], bool skip_12, bool skip_23)
40{
41 float d1[2], d2[2];
42
43 /* The cost is based on the simple sum of the length of the two edges. */
44 sub_v2_v2v2(d1, v2, v1);
45 sub_v2_v2v2(d2, v3, v2);
46 const float cost_12 = normalize_v2(d1);
47 const float cost_23 = normalize_v2(d2);
48 const float cost = ((skip_12 ? 0.0f : cost_12) + (skip_23 ? 0.0f : cost_23));
49
50 /* But is biased to give higher values to sharp turns, so that it will take paths with
51 * fewer "turns" when selecting between equal-weighted paths between the two edges. */
52 return cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v2v2(d1, d2)))));
53}
54
55static float step_cost_3_v2(const float v1[2], const float v2[2], const float v3[2])
56{
57 return step_cost_3_v2_ex(v1, v2, v3, false, false);
58}
59
61
62/* -------------------------------------------------------------------- */
65
67 BMLoop *l_a,
68 BMLoop **loops_prev,
69 float *cost,
70 const BMCalcPathUVParams *params)
71{
72 BLI_assert(params->aspect_y != 0.0f);
73 const int cd_loop_uv_offset = params->cd_loop_uv_offset;
74 const int l_a_index = BM_elem_index_get(l_a);
75 const float *luv_a = BM_ELEM_CD_GET_FLOAT_P(l_a, cd_loop_uv_offset);
76 const float uv_a[2] = {luv_a[0], luv_a[1] / params->aspect_y};
77
78 {
79 BMIter liter;
80 BMLoop *l;
81 /* Loop over faces of face, but do so by first looping over loops. */
82 BM_ITER_ELEM (l, &liter, l_a->v, BM_LOOPS_OF_VERT) {
83 const float *luv = BM_ELEM_CD_GET_FLOAT_P(l, cd_loop_uv_offset);
84 if (equals_v2v2(luv_a, luv)) {
85 /* 'l_a' is already tagged, tag all adjacent. */
87 BMLoop *l_b = l->next;
88 do {
90 const float *luv_b = BM_ELEM_CD_GET_FLOAT_P(l_b, cd_loop_uv_offset);
91 const float uv_b[2] = {luv_b[0], luv_b[1] / params->aspect_y};
92 /* We know 'l_b' is not visited, check it out! */
93 const int l_b_index = BM_elem_index_get(l_b);
94 const float cost_cut = params->use_topology_distance ? 1.0f : len_v2v2(uv_a, uv_b);
95 const float cost_new = cost[l_a_index] + cost_cut;
96
97 if (cost[l_b_index] > cost_new) {
98 cost[l_b_index] = cost_new;
99 loops_prev[l_b_index] = l_a;
100 BLI_heapsimple_insert(heap, cost_new, l_b);
101 }
102 }
103 /* This means we only step onto `l->prev` & `l->next`. */
104 if (params->use_step_face == false) {
105 if (l_b == l->next) {
106 l_b = l->prev->prev;
107 }
108 }
109 } while ((l_b = l_b->next) != l);
110 }
111 }
112 }
113}
114
116 BMLoop *l_src,
117 BMLoop *l_dst,
118 const BMCalcPathUVParams *params,
119 bool (*filter_fn)(BMLoop *, void *),
120 void *user_data)
121{
122 LinkNode *path = nullptr;
123 /* BM_ELEM_TAG flag is used to store visited edges */
124 BMIter viter;
125 HeapSimple *heap;
126 float *cost;
127 BMLoop **loops_prev;
128 int i = 0, totloop;
129 BMFace *f;
130
131 /* NOTE: would pass BM_EDGE except we are looping over all faces anyway. */
132 // BM_mesh_elem_index_ensure(bm, BM_LOOP); /* NOTE: not needed for facetag. */
133
134 BM_ITER_MESH (f, &viter, bm, BM_FACES_OF_MESH) {
135 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
136 BMLoop *l_iter = l_first;
137 do {
138 BM_elem_flag_set(l_iter, BM_ELEM_TAG, !filter_fn(l_iter, user_data));
139 BM_elem_index_set(l_iter, i); /* set_inline */
140 i += 1;
141 } while ((l_iter = l_iter->next) != l_first);
142 }
144
145 /* Allocate. */
146 totloop = bm->totloop;
147 loops_prev = MEM_new_array_zeroed<BMLoop *>(totloop, __func__);
148 cost = MEM_new_array_uninitialized<float>(totloop, __func__);
149
150 std::fill_n(cost, totloop, COST_INIT_MAX);
151
152 /* Regular dijkstra shortest path, but over UV loops instead of vertices. */
153 heap = BLI_heapsimple_new();
154 BLI_heapsimple_insert(heap, 0.0f, l_src);
155 cost[BM_elem_index_get(l_src)] = 0.0f;
156
157 BMLoop *l = nullptr;
158 while (!BLI_heapsimple_is_empty(heap)) {
159 l = static_cast<BMLoop *>(BLI_heapsimple_pop_min(heap));
160
161 if ((l->v == l_dst->v) && BM_loop_uv_share_vert_check(l, l_dst, params->cd_loop_uv_offset)) {
162 break;
163 }
164
166 /* Adjacent loops are tagged while stepping to avoid 2x loops. */
168 verttag_add_adjacent_uv(heap, l, loops_prev, cost, params);
169 }
170 }
171
172 if ((l->v == l_dst->v) && BM_loop_uv_share_vert_check(l, l_dst, params->cd_loop_uv_offset)) {
173 do {
174 BLI_linklist_prepend(&path, l);
175 } while ((l = loops_prev[BM_elem_index_get(l)]));
176 }
177
178 MEM_delete(loops_prev);
179 MEM_delete(cost);
180 BLI_heapsimple_free(heap, nullptr);
181
182 return path;
183}
184
186
187/* -------------------------------------------------------------------- */
190
192 BMLoop *l_e_a, BMLoop *l_e_b, BMLoop *l_v, const float aspect_y, const int cd_loop_uv_offset)
193{
194 BMLoop *l_v1 = (l_v->v == l_e_a->v) ? l_e_a->next : l_e_a;
195 BMLoop *l_v2 = (l_v->v == l_e_b->v) ? l_e_b->next : l_e_b;
196
197 float *luv_v1 = BM_ELEM_CD_GET_FLOAT_P(l_v1, cd_loop_uv_offset);
198 float *luv_v2 = BM_ELEM_CD_GET_FLOAT_P(l_v2, cd_loop_uv_offset);
199 float *luv_v = BM_ELEM_CD_GET_FLOAT_P(l_v, cd_loop_uv_offset);
200
201 float uv_v1[2] = {luv_v1[0], luv_v1[1] / aspect_y};
202 float uv_v2[2] = {luv_v2[0], luv_v2[1] / aspect_y};
203 float uv_v[2] = {luv_v[0], luv_v[1] / aspect_y};
204
205 return step_cost_3_v2(uv_v1, uv_v, uv_v2);
206}
207
209 BMLoop *l_e_a, BMLoop *l_e_b, BMFace *f, const float aspect_v2[2], const int cd_loop_uv_offset)
210{
211 float l_e_a_cent[2], l_e_b_cent[2], f_cent[2];
212 float *luv_e_a = BM_ELEM_CD_GET_FLOAT_P(l_e_a, cd_loop_uv_offset);
213 float *luv_e_b = BM_ELEM_CD_GET_FLOAT_P(l_e_b, cd_loop_uv_offset);
214
215 mid_v2_v2v2(l_e_a_cent, luv_e_a, luv_e_a);
216 mid_v2_v2v2(l_e_b_cent, luv_e_b, luv_e_b);
217
218 mul_v2_v2(l_e_a_cent, aspect_v2);
219 mul_v2_v2(l_e_b_cent, aspect_v2);
220
221 BM_face_uv_calc_center_median_weighted(f, aspect_v2, cd_loop_uv_offset, f_cent);
222
223 return step_cost_3_v2(l_e_a_cent, l_e_b_cent, f_cent);
224}
225
227 BMLoop *l_a,
228 BMLoop **loops_prev,
229 float *cost,
230 const BMCalcPathUVParams *params)
231{
232 BLI_assert(params->aspect_y != 0.0f);
233 const int cd_loop_uv_offset = params->cd_loop_uv_offset;
234 BMLoop *l_a_verts[2] = {l_a, l_a->next};
235 const int l_a_index = BM_elem_index_get(l_a);
236
237 if (params->use_step_face == false) {
238 for (int i = 0; i < ARRAY_SIZE(l_a_verts); i++) {
239
240 /* Skip current UV vert if it is part of the previous UV edge in the path. */
241 if (loops_prev[l_a_index]) {
242 BMLoop *l_prev = loops_prev[l_a_index];
243 if (l_a_verts[i]->v != l_prev->v) {
244 l_prev = (l_a_verts[i]->v == l_prev->next->v) ? l_prev->next : nullptr;
245 }
246 if (l_prev && BM_loop_uv_share_vert_check(l_a_verts[i], l_prev, cd_loop_uv_offset)) {
247 continue;
248 }
249 }
250
251 BMEdge *e_b;
252 BMIter eiter;
253 BM_ITER_ELEM (e_b, &eiter, l_a_verts[i]->v, BM_EDGES_OF_VERT) {
254 if (e_b->l == nullptr) {
255 continue;
256 }
257 BMLoop *l_first, *l_b;
258 l_first = l_b = e_b->l;
259 do {
261 BMLoop *l_b_vert = (l_a_verts[i]->v == l_b->v) ? l_b : l_b->next;
262 if (BM_loop_uv_share_vert_check(l_a_verts[i], l_b_vert, cd_loop_uv_offset)) {
263 /* We know 'l_b' is not visited, check it out! */
264 const int l_b_index = BM_elem_index_get(l_b);
265 const float cost_cut = params->use_topology_distance ?
266 1.0f :
268 l_b,
269 l_a_verts[i],
270 params->aspect_y,
271 cd_loop_uv_offset);
272 const float cost_new = cost[l_a_index] + cost_cut;
273
274 if (cost[l_b_index] > cost_new) {
275 cost[l_b_index] = cost_new;
276 loops_prev[l_b_index] = l_a;
277 BLI_heapsimple_insert(heap, cost_new, l_b);
278 }
279 }
280 }
281 } while ((l_b = l_b->radial_next) != l_first);
282 }
283 }
284 }
285 else {
286 const float aspect_v2[2] = {1.0f, 1.0f / params->aspect_y};
287 BMLoop *l_first, *l_iter;
288 l_iter = l_first = l_a;
289 do {
290 /* Ensures connected UVs and that they lie on the same island. */
291 if (!BM_loop_uv_share_edge_check(l_a, l_iter, cd_loop_uv_offset)) {
292 continue;
293 }
294
295 BMLoop *l_cycle_iter, *l_cycle_end;
296 l_cycle_iter = l_iter->next;
297 l_cycle_end = l_iter;
298 do {
299 BMLoop *l_b = l_cycle_iter;
301 /* We know 'l_b' is not visited, check it out! */
302 const int l_b_index = BM_elem_index_get(l_b);
303 const float cost_cut = params->use_topology_distance ?
304 1.0f :
306 l_b,
307 l_iter->f,
308 aspect_v2,
309 params->cd_loop_uv_offset);
310 const float cost_new = cost[l_a_index] + cost_cut;
311
312 if (cost[l_b_index] > cost_new) {
313 cost[l_b_index] = cost_new;
314 loops_prev[l_b_index] = l_a;
315 BLI_heapsimple_insert(heap, cost_new, l_b);
316 }
317 }
318 } while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_end);
319 } while ((l_iter = l_iter->radial_next) != l_first);
320 }
321}
322
324 BMLoop *l_src,
325 BMLoop *l_dst,
326 const BMCalcPathUVParams *params,
327 bool (*filter_fn)(BMLoop *, void *),
328 void *user_data)
329{
330 LinkNode *path = nullptr;
331
332 BMFace *f;
333 BMIter iter;
334 HeapSimple *heap;
335 float *cost;
336 BMLoop **loops_prev;
337 int i = 0, totloop;
338
339 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
340 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
341 BMLoop *l_iter = l_first;
342 do {
343 BM_elem_flag_set(l_iter, BM_ELEM_TAG, !filter_fn(l_iter, user_data));
344 BM_elem_index_set(l_iter, i);
345 i += 1;
346 } while ((l_iter = l_iter->next) != l_first);
347 }
349
350 totloop = bm->totloop;
351 loops_prev = MEM_new_array_zeroed<BMLoop *>(totloop, __func__);
352 cost = MEM_new_array_uninitialized<float>(totloop, __func__);
353
354 std::fill_n(cost, totloop, COST_INIT_MAX);
355
356 /* Regular dijkstra shortest path, but over UV loops/edges instead of vertices. */
357 heap = BLI_heapsimple_new();
358 BLI_heapsimple_insert(heap, 0.0f, l_src);
359 cost[BM_elem_index_get(l_src)] = 0.0f;
360
361 BMLoop *l = nullptr;
362 while (!BLI_heapsimple_is_empty(heap)) {
363 l = static_cast<BMLoop *>(BLI_heapsimple_pop_min(heap));
364
365 if ((l->e == l_dst->e) && BM_loop_uv_share_edge_check(l, l_dst, params->cd_loop_uv_offset)) {
366 break;
367 }
368
371 edgetag_add_adjacent_uv(heap, l, loops_prev, cost, params);
372 }
373 }
374
375 if ((l->e == l_dst->e) && BM_loop_uv_share_edge_check(l, l_dst, params->cd_loop_uv_offset)) {
376 do {
377 BLI_linklist_prepend(&path, l);
378 } while ((l = loops_prev[BM_elem_index_get(l)]));
379 }
380
381 MEM_delete(loops_prev);
382 MEM_delete(cost);
383 BLI_heapsimple_free(heap, nullptr);
384
385 return path;
386}
387
389
390/* -------------------------------------------------------------------- */
393
395 BMFace *f_b,
396 BMLoop *l_edge,
397 const void *const f_endpoints[2],
398 const float aspect_v2[2],
399 const int cd_loop_uv_offset)
400{
401 float f_a_cent[2];
402 float f_b_cent[2];
403 float e_cent[2];
404
405 BM_face_uv_calc_center_median_weighted(f_a, aspect_v2, cd_loop_uv_offset, f_a_cent);
406 BM_face_uv_calc_center_median_weighted(f_b, aspect_v2, cd_loop_uv_offset, f_b_cent);
407
408 const float *co_v1 = BM_ELEM_CD_GET_FLOAT_P(l_edge, cd_loop_uv_offset);
409 const float *co_v2 = BM_ELEM_CD_GET_FLOAT_P(l_edge->next, cd_loop_uv_offset);
410
411#if 0
412 mid_v2_v2v2(e_cent, co_v1, co_v2);
413#else
414 /* For triangle fans it gives better results to pick a point on the edge. */
415 {
416 float ix_e[2];
417 isect_line_line_v2_point(co_v1, co_v2, f_a_cent, f_b_cent, ix_e);
418 const float factor = line_point_factor_v2(ix_e, co_v1, co_v2);
419 if (factor < 0.0f) {
420 copy_v2_v2(e_cent, co_v1);
421 }
422 else if (factor > 1.0f) {
423 copy_v2_v2(e_cent, co_v2);
424 }
425 else {
426 copy_v2_v2(e_cent, ix_e);
427 }
428 }
429#endif
430
431 /* Apply aspect before calculating cost. */
432 mul_v2_v2(f_a_cent, aspect_v2);
433 mul_v2_v2(f_b_cent, aspect_v2);
434 mul_v2_v2(e_cent, aspect_v2);
435
436 return step_cost_3_v2_ex(
437 f_a_cent, e_cent, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
438}
439
441 BMFace *f_b,
442 BMLoop *l_vert,
443 const void *const f_endpoints[2],
444 const float aspect_v2[2],
445 const int cd_loop_uv_offset)
446{
447 float f_a_cent[2];
448 float f_b_cent[2];
449 float v_cent[2];
450
451 BM_face_uv_calc_center_median_weighted(f_a, aspect_v2, cd_loop_uv_offset, f_a_cent);
452 BM_face_uv_calc_center_median_weighted(f_b, aspect_v2, cd_loop_uv_offset, f_b_cent);
453
454 copy_v2_v2(v_cent, BM_ELEM_CD_GET_FLOAT_P(l_vert, cd_loop_uv_offset));
455
456 mul_v2_v2(f_a_cent, aspect_v2);
457 mul_v2_v2(f_b_cent, aspect_v2);
458 mul_v2_v2(v_cent, aspect_v2);
459
460 return step_cost_3_v2_ex(
461 f_a_cent, v_cent, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
462}
463
465 BMFace *f_a,
466 BMFace **faces_prev,
467 float *cost,
468 const void *const f_endpoints[2],
469 const float aspect_v2[2],
470 const BMCalcPathUVParams *params)
471{
472 const int cd_loop_uv_offset = params->cd_loop_uv_offset;
473 const int f_a_index = BM_elem_index_get(f_a);
474
475 /* Loop over faces of face, but do so by first looping over loops. */
476 {
477 BMIter liter;
478 BMLoop *l_a;
479
480 BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
481 BMLoop *l_first, *l_iter;
482
483 /* Check there is an adjacent face to loop over. */
484 if (l_a != l_a->radial_next) {
485 l_iter = l_first = l_a->radial_next;
486 do {
487 BMFace *f_b = l_iter->f;
488 if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
489 if (BM_loop_uv_share_edge_check(l_a, l_iter, cd_loop_uv_offset)) {
490 /* We know 'f_b' is not visited, check it out! */
491 const int f_b_index = BM_elem_index_get(f_b);
492 const float cost_cut =
493 params->use_topology_distance ?
494 1.0f :
496 f_a, f_b, l_iter, f_endpoints, aspect_v2, cd_loop_uv_offset);
497 const float cost_new = cost[f_a_index] + cost_cut;
498
499 if (cost[f_b_index] > cost_new) {
500 cost[f_b_index] = cost_new;
501 faces_prev[f_b_index] = f_a;
502 BLI_heapsimple_insert(heap, cost_new, f_b);
503 }
504 }
505 }
506 } while ((l_iter = l_iter->radial_next) != l_first);
507 }
508 }
509 }
510
511 if (params->use_step_face) {
512 BMIter liter;
513 BMLoop *l_a;
514
515 BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
516 BMIter litersub;
517 BMLoop *l_b;
518 BM_ITER_ELEM (l_b, &litersub, l_a->v, BM_LOOPS_OF_VERT) {
519 if ((l_a != l_b) && !BM_loop_share_edge_check(l_a, l_b)) {
520 BMFace *f_b = l_b->f;
521 if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
522 if (BM_loop_uv_share_vert_check(l_a, l_b, cd_loop_uv_offset)) {
523 /* We know 'f_b' is not visited, check it out! */
524 const int f_b_index = BM_elem_index_get(f_b);
525 const float cost_cut =
526 params->use_topology_distance ?
527 1.0f :
529 f_a, f_b, l_a, f_endpoints, aspect_v2, cd_loop_uv_offset);
530 const float cost_new = cost[f_a_index] + cost_cut;
531
532 if (cost[f_b_index] > cost_new) {
533 cost[f_b_index] = cost_new;
534 faces_prev[f_b_index] = f_a;
535 BLI_heapsimple_insert(heap, cost_new, f_b);
536 }
537 }
538 }
539 }
540 }
541 }
542 }
543}
544
546 BMFace *f_src,
547 BMFace *f_dst,
548 const BMCalcPathUVParams *params,
549 bool (*filter_fn)(BMFace *, void *),
550 void *user_data)
551{
552 const float aspect_v2[2] = {1.0f, 1.0f / params->aspect_y};
553 LinkNode *path = nullptr;
554 /* BM_ELEM_TAG flag is used to store visited edges */
555 BMIter fiter;
556 HeapSimple *heap;
557 float *cost;
558 BMFace **faces_prev;
559 int i = 0, totface;
560
561 /* Start measuring face path at the face edges, ignoring their centers. */
562 const void *const f_endpoints[2] = {f_src, f_dst};
563
564 /* NOTE: would pass BM_EDGE except we are looping over all faces anyway. */
565 // BM_mesh_elem_index_ensure(bm, BM_LOOP); /* NOTE: not needed for facetag. */
566
567 {
568 BMFace *f;
569 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
570 BM_elem_flag_set(f, BM_ELEM_TAG, !filter_fn(f, user_data));
571 BM_elem_index_set(f, i); /* set_inline */
572 i += 1;
573 }
575 }
576
577 /* Allocate. */
578 totface = bm->totface;
579 faces_prev = MEM_new_array_zeroed<BMFace *>(totface, __func__);
580 cost = MEM_new_array_uninitialized<float>(totface, __func__);
581
582 std::fill_n(cost, totface, COST_INIT_MAX);
583
584 /* Regular dijkstra shortest path, but over UV faces instead of vertices. */
585 heap = BLI_heapsimple_new();
586 BLI_heapsimple_insert(heap, 0.0f, f_src);
587 cost[BM_elem_index_get(f_src)] = 0.0f;
588
589 BMFace *f = nullptr;
590 while (!BLI_heapsimple_is_empty(heap)) {
591 f = static_cast<BMFace *>(BLI_heapsimple_pop_min(heap));
592
593 if (f == f_dst) {
594 break;
595 }
596
598 /* Adjacent loops are tagged while stepping to avoid 2x loops. */
600 facetag_add_adjacent_uv(heap, f, faces_prev, cost, f_endpoints, aspect_v2, params);
601 }
602 }
603
604 if (f == f_dst) {
605 do {
606 BLI_linklist_prepend(&path, f);
607 } while ((f = faces_prev[BM_elem_index_get(f)]));
608 }
609
610 MEM_delete(faces_prev);
611 MEM_delete(cost);
612 BLI_heapsimple_free(heap, nullptr);
613
614 return path;
615}
616
618
619} // namespace blender
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define BM_FACE_FIRST_LOOP(p)
#define BM_ELEM_CD_GET_FLOAT_P(ele, offset)
#define BM_elem_index_get(ele)
#define BM_elem_flag_set(ele, hflag, val)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define COST_INIT_MAX
Definition bmesh_path.cc:27
BMesh Iterators.
bool BM_loop_share_edge_check(BMLoop *l_a, BMLoop *l_b)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static void facetag_add_adjacent_uv(HeapSimple *heap, BMFace *f_a, BMFace **faces_prev, float *cost, const void *const f_endpoints[2], const float aspect_v2[2], const BMCalcPathUVParams *params)
static float facetag_cut_cost_edge_uv(BMFace *f_a, BMFace *f_b, BMLoop *l_edge, const void *const f_endpoints[2], const float aspect_v2[2], const int cd_loop_uv_offset)
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
ATTR_WARN_UNUSED_RESULT const BMLoop * l
MINLINE void copy_v2_v2(float r[2], const float a[2])
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
MINLINE float normalize_v2(float n[2])
ATTR_WARN_UNUSED_RESULT const BMVert * v
static float step_cost_3_v2_ex(const float v1[2], const float v2[2], const float v3[2], bool skip_12, bool skip_23)
bool BM_loop_uv_share_vert_check(const BMLoop *l_a, const BMLoop *l_b, const int cd_loop_uv_offset)
MINLINE void mul_v2_v2(float r[2], const float a[2])
void void BLI_linklist_prepend(LinkNode **listp, void *ptr) ATTR_NONNULL(1)
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
static float step_cost_3_v2(const float v1[2], const float v2[2], const float v3[2])
float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2])
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
static float facetag_cut_cost_vert_uv(BMFace *f_a, BMFace *f_b, BMLoop *l_vert, const void *const f_endpoints[2], const float aspect_v2[2], const int cd_loop_uv_offset)
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
static void edgetag_add_adjacent_uv(HeapSimple *heap, BMLoop *l_a, BMLoop **loops_prev, float *cost, const BMCalcPathUVParams *params)
static void verttag_add_adjacent_uv(HeapSimple *heap, BMLoop *l_a, BMLoop **loops_prev, float *cost, const BMCalcPathUVParams *params)
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
MINLINE float dot_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
MINLINE bool equals_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
HeapSimple * BLI_heapsimple_new() ATTR_WARN_UNUSED_RESULT
LinkNode * BM_mesh_calc_path_uv_face(BMesh *bm, BMFace *f_src, BMFace *f_dst, const BMCalcPathUVParams *params, bool(*filter_fn)(BMFace *, void *), void *user_data)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
LinkNode * BM_mesh_calc_path_uv_vert(BMesh *bm, BMLoop *l_src, BMLoop *l_dst, const BMCalcPathUVParams *params, bool(*filter_fn)(BMLoop *, void *), void *user_data)
MINLINE float len_v2v2(const float v1[2], const float v2[2]) ATTR_WARN_UNUSED_RESULT
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
void mid_v2_v2v2(float r[2], const float a[2], const float b[2])
void BM_face_uv_calc_center_median_weighted(const BMFace *f, const float aspect[2], const int cd_loop_uv_offset, float r_cent[2])
bool BM_loop_uv_share_edge_check(const BMLoop *l_a, const BMLoop *l_b, const int cd_loop_uv_offset)
static float edgetag_cut_cost_vert_uv(BMLoop *l_e_a, BMLoop *l_e_b, BMLoop *l_v, const float aspect_y, const int cd_loop_uv_offset)
int isect_line_line_v2_point(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float r_vi[2])
static float edgetag_cut_cost_face_uv(BMLoop *l_e_a, BMLoop *l_e_b, BMFace *f, const float aspect_v2[2], const int cd_loop_uv_offset)
LinkNode * BM_mesh_calc_path_uv_edge(BMesh *bm, BMLoop *l_src, BMLoop *l_dst, const BMCalcPathUVParams *params, bool(*filter_fn)(BMLoop *, void *), void *user_data)
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
#define fabsf
#define sqrtf
struct BMLoop * l
struct BMLoop * next
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMLoop * radial_next