1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version 2
5 * of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program; if not, write to the Free Software Foundation,
14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15 */
16
17 /** \file
18 * \ingroup bmesh
19 *
20 * Find a path between 2 elements in UV space.
21 */
22
23 #include "MEM_guardedalloc.h"
24
25 #include "BLI_heap_simple.h"
26 #include "BLI_linklist.h"
27 #include "BLI_math.h"
28
29 #include "DNA_meshdata_types.h"
30
31 #include "bmesh.h"
32 #include "bmesh_path_uv.h" /* own include */
33 #include "intern/bmesh_query.h"
34 #include "intern/bmesh_query_uv.h"
35
36 #define COST_INIT_MAX FLT_MAX
37
38 /* -------------------------------------------------------------------- */
39 /** \name Generic Helpers
40 * \{ */
41
42 /**
43 * Use skip options when we want to start measuring from a boundary.
44 *
45 * See #step_cost_3_v3_ex in bmesh_path.c which follows the same logic.
46 */
step_cost_3_v2_ex(const float v1[2],const float v2[2],const float v3[2],bool skip_12,bool skip_23)47 static float step_cost_3_v2_ex(
48 const float v1[2], const float v2[2], const float v3[2], bool skip_12, bool skip_23)
49 {
50 float d1[2], d2[2];
51
52 /* The cost is based on the simple sum of the length of the two edges. */
53 sub_v2_v2v2(d1, v2, v1);
54 sub_v2_v2v2(d2, v3, v2);
55 const float cost_12 = normalize_v2(d1);
56 const float cost_23 = normalize_v2(d2);
57 const float cost = ((skip_12 ? 0.0f : cost_12) + (skip_23 ? 0.0f : cost_23));
58
59 /* But is biased to give higher values to sharp turns, so that it will take paths with
60 * fewer "turns" when selecting between equal-weighted paths between the two edges. */
61 return cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v2v2(d1, d2)))));
62 }
63
UNUSED_FUNCTION(step_cost_3_v2)64 static float UNUSED_FUNCTION(step_cost_3_v2)(const float v1[2],
65 const float v2[2],
66 const float v3[2])
67 {
68 return step_cost_3_v2_ex(v1, v2, v3, false, false);
69 }
70
71 /** \} */
72
73 /* -------------------------------------------------------------------- */
74 /** \name BM_mesh_calc_path_uv_vert
75 * \{ */
76
looptag_add_adjacent_uv(HeapSimple * heap,BMLoop * l_a,BMLoop ** loops_prev,float * cost,const struct BMCalcPathUVParams * params)77 static void looptag_add_adjacent_uv(HeapSimple *heap,
78 BMLoop *l_a,
79 BMLoop **loops_prev,
80 float *cost,
81 const struct BMCalcPathUVParams *params)
82 {
83 BLI_assert(params->aspect_y != 0.0f);
84 const uint cd_loop_uv_offset = params->cd_loop_uv_offset;
85 const int l_a_index = BM_elem_index_get(l_a);
86 const MLoopUV *luv_a = BM_ELEM_CD_GET_VOID_P(l_a, cd_loop_uv_offset);
87 const float uv_a[2] = {luv_a->uv[0], luv_a->uv[1] / params->aspect_y};
88
89 {
90 BMIter liter;
91 BMLoop *l;
92 /* Loop over faces of face, but do so by first looping over loops. */
93 BM_ITER_ELEM (l, &liter, l_a->v, BM_LOOPS_OF_VERT) {
94 const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset);
95 if (equals_v2v2(luv_a->uv, luv->uv)) {
96 /* 'l_a' is already tagged, tag all adjacent. */
97 BM_elem_flag_enable(l, BM_ELEM_TAG);
98 BMLoop *l_b = l->next;
99 do {
100 if (!BM_elem_flag_test(l_b, BM_ELEM_TAG)) {
101 const MLoopUV *luv_b = BM_ELEM_CD_GET_VOID_P(l_b, cd_loop_uv_offset);
102 const float uv_b[2] = {luv_b->uv[0], luv_b->uv[1] / params->aspect_y};
103 /* We know 'l_b' is not visited, check it out! */
104 const int l_b_index = BM_elem_index_get(l_b);
105 const float cost_cut = params->use_topology_distance ? 1.0f : len_v2v2(uv_a, uv_b);
106 const float cost_new = cost[l_a_index] + cost_cut;
107
108 if (cost[l_b_index] > cost_new) {
109 cost[l_b_index] = cost_new;
110 loops_prev[l_b_index] = l_a;
111 BLI_heapsimple_insert(heap, cost_new, l_b);
112 }
113 }
114 /* This means we only step onto `l->prev` & `l->next`. */
115 if (params->use_step_face == false) {
116 if (l_b == l->next) {
117 l_b = l->prev->prev;
118 }
119 }
120 } while ((l_b = l_b->next) != l);
121 }
122 }
123 }
124 }
125
BM_mesh_calc_path_uv_vert(BMesh * bm,BMLoop * l_src,BMLoop * l_dst,const struct BMCalcPathUVParams * params,bool (* filter_fn)(BMLoop *,void *),void * user_data)126 struct LinkNode *BM_mesh_calc_path_uv_vert(BMesh *bm,
127 BMLoop *l_src,
128 BMLoop *l_dst,
129 const struct BMCalcPathUVParams *params,
130 bool (*filter_fn)(BMLoop *, void *),
131 void *user_data)
132 {
133 LinkNode *path = NULL;
134 /* BM_ELEM_TAG flag is used to store visited edges */
135 BMIter viter;
136 HeapSimple *heap;
137 float *cost;
138 BMLoop **loops_prev;
139 int i = 0, totloop;
140 BMFace *f;
141
142 /* Note, would pass BM_EDGE except we are looping over all faces anyway. */
143 // BM_mesh_elem_index_ensure(bm, BM_LOOP); // NOT NEEDED FOR FACETAG
144
145 BM_ITER_MESH (f, &viter, bm, BM_FACES_OF_MESH) {
146 BMLoop *l_first = BM_FACE_FIRST_LOOP(f);
147 BMLoop *l_iter = l_first;
148 do {
149 BM_elem_flag_set(l_iter, BM_ELEM_TAG, !filter_fn(l_iter, user_data));
150 BM_elem_index_set(l_iter, i); /* set_inline */
151 i += 1;
152 } while ((l_iter = l_iter->next) != l_first);
153 }
154 bm->elem_index_dirty &= ~BM_LOOP;
155
156 /* Allocate. */
157 totloop = bm->totloop;
158 loops_prev = MEM_callocN(sizeof(*loops_prev) * totloop, __func__);
159 cost = MEM_mallocN(sizeof(*cost) * totloop, __func__);
160
161 copy_vn_fl(cost, totloop, COST_INIT_MAX);
162
163 /* Regular dijkstra shortest path, but over UV loops instead of vertices. */
164 heap = BLI_heapsimple_new();
165 BLI_heapsimple_insert(heap, 0.0f, l_src);
166 cost[BM_elem_index_get(l_src)] = 0.0f;
167
168 BMLoop *l = NULL;
169 while (!BLI_heapsimple_is_empty(heap)) {
170 l = BLI_heapsimple_pop_min(heap);
171
172 if ((l->v == l_dst->v) && BM_loop_uv_share_vert_check(l, l_dst, params->cd_loop_uv_offset)) {
173 break;
174 }
175
176 if (!BM_elem_flag_test(l, BM_ELEM_TAG)) {
177 /* Adjacent loops are tagged while stepping to avoid 2x loops. */
178 BM_elem_flag_enable(l, BM_ELEM_TAG);
179 looptag_add_adjacent_uv(heap, l, loops_prev, cost, params);
180 }
181 }
182
183 if ((l->v == l_dst->v) && BM_loop_uv_share_vert_check(l, l_dst, params->cd_loop_uv_offset)) {
184 do {
185 BLI_linklist_prepend(&path, l);
186 } while ((l = loops_prev[BM_elem_index_get(l)]));
187 }
188
189 MEM_freeN(loops_prev);
190 MEM_freeN(cost);
191 BLI_heapsimple_free(heap, NULL);
192
193 return path;
194 }
195
196 /** \} */
197
198 /* -------------------------------------------------------------------- */
199 /** \name BM_mesh_calc_path_uv_edge
200 * \{ */
201 /* TODO(campbell): not very urgent, since the operator fakes this using vertex path. */
202
203 /** \} */
204
205 /* -------------------------------------------------------------------- */
206 /** \name BM_mesh_calc_path_uv_face
207 * \{ */
208
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)209 static float facetag_cut_cost_edge_uv(BMFace *f_a,
210 BMFace *f_b,
211 BMLoop *l_edge,
212 const void *const f_endpoints[2],
213 const float aspect_v2[2],
214 const int cd_loop_uv_offset)
215 {
216 float f_a_cent[2];
217 float f_b_cent[2];
218 float e_cent[2];
219
220 BM_face_uv_calc_center_median_weighted(f_a, aspect_v2, cd_loop_uv_offset, f_a_cent);
221 BM_face_uv_calc_center_median_weighted(f_b, aspect_v2, cd_loop_uv_offset, f_b_cent);
222
223 const float *co_v1 = ((const MLoopUV *)BM_ELEM_CD_GET_VOID_P(l_edge, cd_loop_uv_offset))->uv;
224 const float *co_v2 =
225 ((const MLoopUV *)BM_ELEM_CD_GET_VOID_P(l_edge->next, cd_loop_uv_offset))->uv;
226
227 #if 0
228 mid_v2_v2v2(e_cent, co_v1, co_v2);
229 #else
230 /* For triangle fans it gives better results to pick a point on the edge. */
231 {
232 float ix_e[2];
233 isect_line_line_v2_point(co_v1, co_v2, f_a_cent, f_b_cent, ix_e);
234 const float factor = line_point_factor_v2(ix_e, co_v1, co_v2);
235 if (factor < 0.0f) {
236 copy_v2_v2(e_cent, co_v1);
237 }
238 else if (factor > 1.0f) {
239 copy_v2_v2(e_cent, co_v2);
240 }
241 else {
242 copy_v2_v2(e_cent, ix_e);
243 }
244 }
245 #endif
246
247 /* Apply aspect before calculating cost. */
248 mul_v2_v2(f_a_cent, aspect_v2);
249 mul_v2_v2(f_b_cent, aspect_v2);
250 mul_v2_v2(e_cent, aspect_v2);
251
252 return step_cost_3_v2_ex(
253 f_a_cent, e_cent, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
254 }
255
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)256 static float facetag_cut_cost_vert_uv(BMFace *f_a,
257 BMFace *f_b,
258 BMLoop *l_vert,
259 const void *const f_endpoints[2],
260 const float aspect_v2[2],
261 const int cd_loop_uv_offset)
262 {
263 float f_a_cent[2];
264 float f_b_cent[2];
265 float v_cent[2];
266
267 BM_face_uv_calc_center_median_weighted(f_a, aspect_v2, cd_loop_uv_offset, f_a_cent);
268 BM_face_uv_calc_center_median_weighted(f_b, aspect_v2, cd_loop_uv_offset, f_b_cent);
269
270 copy_v2_v2(v_cent, ((const MLoopUV *)BM_ELEM_CD_GET_VOID_P(l_vert, cd_loop_uv_offset))->uv);
271
272 mul_v2_v2(f_a_cent, aspect_v2);
273 mul_v2_v2(f_b_cent, aspect_v2);
274 mul_v2_v2(v_cent, aspect_v2);
275
276 return step_cost_3_v2_ex(
277 f_a_cent, v_cent, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1]));
278 }
279
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 struct BMCalcPathUVParams * params)280 static void facetag_add_adjacent_uv(HeapSimple *heap,
281 BMFace *f_a,
282 BMFace **faces_prev,
283 float *cost,
284 const void *const f_endpoints[2],
285 const float aspect_v2[2],
286 const struct BMCalcPathUVParams *params)
287 {
288 const uint cd_loop_uv_offset = params->cd_loop_uv_offset;
289 const int f_a_index = BM_elem_index_get(f_a);
290
291 /* Loop over faces of face, but do so by first looping over loops. */
292 {
293 BMIter liter;
294 BMLoop *l_a;
295
296 BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
297 BMLoop *l_first, *l_iter;
298
299 /* Check there is an adjacent face to loop over. */
300 if (l_a != l_a->radial_next) {
301 l_iter = l_first = l_a->radial_next;
302 do {
303 BMFace *f_b = l_iter->f;
304 if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
305 if (BM_loop_uv_share_edge_check(l_a, l_iter, cd_loop_uv_offset)) {
306 /* We know 'f_b' is not visited, check it out! */
307 const int f_b_index = BM_elem_index_get(f_b);
308 const float cost_cut =
309 params->use_topology_distance ?
310 1.0f :
311 facetag_cut_cost_edge_uv(
312 f_a, f_b, l_iter, f_endpoints, aspect_v2, cd_loop_uv_offset);
313 const float cost_new = cost[f_a_index] + cost_cut;
314
315 if (cost[f_b_index] > cost_new) {
316 cost[f_b_index] = cost_new;
317 faces_prev[f_b_index] = f_a;
318 BLI_heapsimple_insert(heap, cost_new, f_b);
319 }
320 }
321 }
322 } while ((l_iter = l_iter->radial_next) != l_first);
323 }
324 }
325 }
326
327 if (params->use_step_face) {
328 BMIter liter;
329 BMLoop *l_a;
330
331 BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) {
332 BMIter litersub;
333 BMLoop *l_b;
334 BM_ITER_ELEM (l_b, &litersub, l_a->v, BM_LOOPS_OF_VERT) {
335 if ((l_a != l_b) && !BM_loop_share_edge_check(l_a, l_b)) {
336 BMFace *f_b = l_b->f;
337 if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) {
338 if (BM_loop_uv_share_vert_check(l_a, l_b, cd_loop_uv_offset)) {
339 /* We know 'f_b' is not visited, check it out! */
340 const int f_b_index = BM_elem_index_get(f_b);
341 const float cost_cut =
342 params->use_topology_distance ?
343 1.0f :
344 facetag_cut_cost_vert_uv(
345 f_a, f_b, l_a, f_endpoints, aspect_v2, cd_loop_uv_offset);
346 const float cost_new = cost[f_a_index] + cost_cut;
347
348 if (cost[f_b_index] > cost_new) {
349 cost[f_b_index] = cost_new;
350 faces_prev[f_b_index] = f_a;
351 BLI_heapsimple_insert(heap, cost_new, f_b);
352 }
353 }
354 }
355 }
356 }
357 }
358 }
359 }
360
BM_mesh_calc_path_uv_face(BMesh * bm,BMFace * f_src,BMFace * f_dst,const struct BMCalcPathUVParams * params,bool (* filter_fn)(BMFace *,void *),void * user_data)361 struct LinkNode *BM_mesh_calc_path_uv_face(BMesh *bm,
362 BMFace *f_src,
363 BMFace *f_dst,
364 const struct BMCalcPathUVParams *params,
365 bool (*filter_fn)(BMFace *, void *),
366 void *user_data)
367 {
368 const float aspect_v2[2] = {1.0f, 1.0f / params->aspect_y};
369 LinkNode *path = NULL;
370 /* BM_ELEM_TAG flag is used to store visited edges */
371 BMIter fiter;
372 HeapSimple *heap;
373 float *cost;
374 BMFace **faces_prev;
375 int i = 0, totface;
376
377 /* Start measuring face path at the face edges, ignoring their centers. */
378 const void *const f_endpoints[2] = {f_src, f_dst};
379
380 /* Note, would pass BM_EDGE except we are looping over all faces anyway. */
381 // BM_mesh_elem_index_ensure(bm, BM_LOOP); // NOT NEEDED FOR FACETAG
382
383 {
384 BMFace *f;
385 BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
386 BM_elem_flag_set(f, BM_ELEM_TAG, !filter_fn(f, user_data));
387 BM_elem_index_set(f, i); /* set_inline */
388 i += 1;
389 }
390 bm->elem_index_dirty &= ~BM_FACE;
391 }
392
393 /* Allocate. */
394 totface = bm->totface;
395 faces_prev = MEM_callocN(sizeof(*faces_prev) * totface, __func__);
396 cost = MEM_mallocN(sizeof(*cost) * totface, __func__);
397
398 copy_vn_fl(cost, totface, COST_INIT_MAX);
399
400 /* Regular dijkstra shortest path, but over UV faces instead of vertices. */
401 heap = BLI_heapsimple_new();
402 BLI_heapsimple_insert(heap, 0.0f, f_src);
403 cost[BM_elem_index_get(f_src)] = 0.0f;
404
405 BMFace *f = NULL;
406 while (!BLI_heapsimple_is_empty(heap)) {
407 f = BLI_heapsimple_pop_min(heap);
408
409 if (f == f_dst) {
410 break;
411 }
412
413 if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
414 /* Adjacent loops are tagged while stepping to avoid 2x loops. */
415 BM_elem_flag_enable(f, BM_ELEM_TAG);
416 facetag_add_adjacent_uv(heap, f, faces_prev, cost, f_endpoints, aspect_v2, params);
417 }
418 }
419
420 if (f == f_dst) {
421 do {
422 BLI_linklist_prepend(&path, f);
423 } while ((f = faces_prev[BM_elem_index_get(f)]));
424 }
425
426 MEM_freeN(faces_prev);
427 MEM_freeN(cost);
428 BLI_heapsimple_free(heap, NULL);
429
430 return path;
431 }
432
433 /** \} */
434