Blender V5.3
mesh_remap.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 <algorithm>
12
13#include "CLG_log.h"
14
15#include "MEM_guardedalloc.h"
16
17#include "BLI_array.hh"
18#include "BLI_astar.hh"
19#include "BLI_bit_vector.hh"
20#include "BLI_index_mask.hh"
21#include "BLI_math_geom_c.hh"
22#include "BLI_math_matrix_c.hh"
23#include "BLI_math_solvers.hh"
25#include "BLI_math_vector.hh"
26#include "BLI_math_vector_c.hh"
27#include "BLI_memarena.hh"
28#include "BLI_polyfill_2d.hh"
29#include "BLI_rand_c.hh"
30#include "BLI_utildefines.hh"
31
32#include "DNA_modifier_enums.h"
33
34#include "BKE_attribute.hh"
35#include "BKE_bvh.hh"
36#include "BKE_bvhutils.hh"
37#include "BKE_customdata.hh"
38#include "BKE_mesh.hh"
39#include "BKE_mesh_mapping.hh"
40#include "BKE_mesh_remap.hh" /* own include */
41
42#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
43
44namespace blender {
45
46static CLG_LogRef LOG = {"geom.mesh"};
47
48/* -------------------------------------------------------------------- */
51
53 const float3 &co,
54 const float max_dist,
55 int *r_index,
56 float *r_hit_dist)
57{
58 const std::optional<bke::bvh::ClosestPointResult> nearest = tree.closest_point(co, max_dist);
59 if (!nearest) {
60 return false;
61 }
62 *r_index = int(nearest->index);
63 *r_hit_dist = math::distance(co, nearest->position);
64 return true;
65}
66
68 BVHTreeNearest *nearest,
69 const float co[3],
70 const float max_dist_sq,
71 float *r_hit_dist)
72{
73 /* Use local proximity heuristics (to reduce the nearest search). */
74 if (nearest->index != -1) {
75 nearest->dist_sq = len_squared_v3v3(co, nearest->co);
76 if (nearest->dist_sq > max_dist_sq) {
77 /* The previous valid index is too far away and not valid for this check. */
78 nearest->dist_sq = max_dist_sq;
79 nearest->index = -1;
80 }
81 }
82 else {
83 nearest->dist_sq = max_dist_sq;
84 }
85 /* Compute and store result. If invalid (-1 index), keep FLT_MAX dist. */
86 BLI_bvhtree_find_nearest(treedata->tree, co, nearest, treedata->nearest_callback, treedata);
87
88 if ((nearest->index != -1) && (nearest->dist_sq <= max_dist_sq)) {
89 *r_hit_dist = sqrtf(nearest->dist_sq);
90 return true;
91 }
92
93 return false;
94}
95
97 BVHTreeRayHit *rayhit,
98 const float co[3],
99 const float no[3],
100 const float radius,
101 const float max_dist,
102 float *r_hit_dist)
103{
104 BVHTreeRayHit rayhit_tmp;
105 float inv_no[3];
106
107 rayhit->index = -1;
108 rayhit->dist = max_dist;
110 treedata->tree, co, no, radius, rayhit, treedata->raycast_callback, treedata);
111
112 /* Also cast in the other direction! */
113 rayhit_tmp = *rayhit;
114 negate_v3_v3(inv_no, no);
116 treedata->tree, co, inv_no, radius, &rayhit_tmp, treedata->raycast_callback, treedata);
117 if (rayhit_tmp.dist < rayhit->dist) {
118 *rayhit = rayhit_tmp;
119 }
120
121 if ((rayhit->index != -1) && (rayhit->dist <= max_dist)) {
122 *r_hit_dist = rayhit->dist;
123 return true;
124 }
125
126 return false;
127}
128
130
131/* -------------------------------------------------------------------- */
136
138 const Span<float3> vert_positions_dst,
139 const Mesh *me_src)
140{
141 float hit_dist;
142
143 float result = 0.0f;
144 int i;
145
146 const bke::bvh::Tree &tree = me_src->bvh_verts();
147
148 for (i = 0; i < vert_positions_dst.size(); i++) {
149 float3 tmp_co = vert_positions_dst[i];
150
151 /* Convert the vertex to tree coordinates, if needed. */
152 if (space_transform) {
153 BLI_space_transform_apply(space_transform, tmp_co);
154 }
155
156 int index;
157 if (mesh_remap_bvh_query_nearest(tree, tmp_co, FLT_MAX, &index, &hit_dist)) {
158 result += 1.0f / (hit_dist + 1.0f);
159 }
160 else {
161 /* No source for this dest vertex! */
162 result += 1e-18f;
163 }
164 }
165
166 result = (float(vert_positions_dst.size()) / result) - 1.0f;
167
168#if 0
169 printf("%s: Computed difference between meshes (the lower the better): %f\n", __func__, result);
170#endif
171
172 return result;
173}
174
175/* This helper computes the eigen values & vectors for
176 * covariance matrix of all given vertices coordinates.
177 *
178 * Those vectors define the 'average ellipsoid' of the mesh (i.e. the 'best fitting' ellipsoid
179 * containing 50% of the vertices).
180 *
181 * Note that it will not perform fantastic in case two or more eigen values are equal
182 * (e.g. a cylinder or parallelepiped with a square section give two identical eigenvalues,
183 * a sphere or tetrahedron give three identical ones, etc.), since you cannot really define all
184 * axes in those cases. We default to dummy generated orthogonal vectors in this case,
185 * instead of using eigen vectors.
186 */
187static void mesh_calc_eigen_matrix(const Span<float3> positions, float r_mat[4][4])
188{
189 float center[3], covmat[3][3];
190 float eigen_val[3], eigen_vec[3][3];
191
192 bool eigen_success;
193 int i;
194
195 unit_m4(r_mat);
196
197 /* NOTE: here we apply sample correction to covariance matrix, since we consider the vertices
198 * as a sample of the whole 'surface' population of our mesh. */
199 BLI_covariance_m3_v3n(reinterpret_cast<const float (*)[3]>(positions.data()),
200 int(positions.size()),
201 true,
202 covmat,
203 center);
204
205 eigen_success = BLI_eigen_solve_selfadjoint_m3(
206 const_cast<const float (*)[3]>(covmat), eigen_val, eigen_vec);
207 BLI_assert(eigen_success);
208 UNUSED_VARS_NDEBUG(eigen_success);
209
210 /* Special handling of cases where some eigen values are (nearly) identical. */
211 if (compare_ff_relative(eigen_val[0], eigen_val[1], FLT_EPSILON, 64)) {
212 if (compare_ff_relative(eigen_val[0], eigen_val[2], FLT_EPSILON, 64)) {
213 /* No preferred direction, that set of vertices has a spherical average,
214 * so we simply returned scaled/translated identity matrix (with no rotation). */
215 unit_m3(eigen_vec);
216 }
217 else {
218 /* Ellipsoid defined by eigen values/vectors has a spherical section,
219 * we can only define one axis from eigen_vec[2] (two others computed eigen vecs
220 * are not so nice for us here, they tend to 'randomly' rotate around valid one).
221 * Note that eigen vectors as returned by BLI_eigen_solve_selfadjoint_m3() are normalized. */
222 ortho_basis_v3v3_v3(eigen_vec[0], eigen_vec[1], eigen_vec[2]);
223 }
224 }
225 else if (compare_ff_relative(eigen_val[0], eigen_val[2], FLT_EPSILON, 64)) {
226 /* Same as above, but with eigen_vec[1] as valid axis. */
227 ortho_basis_v3v3_v3(eigen_vec[2], eigen_vec[0], eigen_vec[1]);
228 }
229 else if (compare_ff_relative(eigen_val[1], eigen_val[2], FLT_EPSILON, 64)) {
230 /* Same as above, but with eigen_vec[0] as valid axis. */
231 ortho_basis_v3v3_v3(eigen_vec[1], eigen_vec[2], eigen_vec[0]);
232 }
233
234 for (i = 0; i < 3; i++) {
235 float evi = eigen_val[i];
236
237 /* Protect against 1D/2D degenerated cases! */
238 /* NOTE: not sure why we need square root of eigen values here
239 * (which are equivalent to singular values, as far as I have understood),
240 * but it seems to heavily reduce (if not completely nullify)
241 * the error due to non-uniform scalings... */
242 evi = (evi < 1e-6f && evi > -1e-6f) ? ((evi < 0.0f) ? -1e-3f : 1e-3f) : sqrtf_signed(evi);
243 mul_v3_fl(eigen_vec[i], evi);
244 }
245
246 copy_m4_m3(r_mat, eigen_vec);
247 copy_v3_v3(r_mat[3], center);
248}
249
251 const Mesh *me_src,
252 SpaceTransform *r_space_transform)
253{
254 /* Note that those are done so that we successively get actual mirror matrix
255 * (by multiplication of columns). */
256 const float mirrors[][3] = {
257 {-1.0f, 1.0f, 1.0f}, /* -> -1, 1, 1 */
258 {1.0f, -1.0f, 1.0f}, /* -> -1, -1, 1 */
259 {1.0f, 1.0f, -1.0f}, /* -> -1, -1, -1 */
260 {1.0f, -1.0f, 1.0f}, /* -> -1, 1, -1 */
261 {-1.0f, 1.0f, 1.0f}, /* -> 1, 1, -1 */
262 {1.0f, -1.0f, 1.0f}, /* -> 1, -1, -1 */
263 {1.0f, 1.0f, -1.0f}, /* -> 1, -1, 1 */
264 {0.0f, 0.0f, 0.0f},
265 };
266 const float (*mirr)[3];
267
268 float mat_src[4][4], mat_dst[4][4], best_mat_dst[4][4];
269 float best_match = FLT_MAX, match;
270
271 const Span<float3> positions_src = me_src->vert_positions();
272 mesh_calc_eigen_matrix(positions_src, mat_src);
273 mesh_calc_eigen_matrix(vert_positions_dst, mat_dst);
274
275 BLI_space_transform_global_from_matrices(r_space_transform, mat_dst, mat_src);
276 match = BKE_mesh_remap_calc_difference_from_mesh(r_space_transform, vert_positions_dst, me_src);
277 best_match = match;
278 copy_m4_m4(best_mat_dst, mat_dst);
279
280 /* And now, we have to check the other sixth possible mirrored versions... */
281 for (mirr = mirrors; (*mirr)[0]; mirr++) {
282 mul_v3_fl(mat_dst[0], (*mirr)[0]);
283 mul_v3_fl(mat_dst[1], (*mirr)[1]);
284 mul_v3_fl(mat_dst[2], (*mirr)[2]);
285
286 BLI_space_transform_global_from_matrices(r_space_transform, mat_dst, mat_src);
288 r_space_transform, vert_positions_dst, me_src);
289 if (match < best_match) {
290 best_match = match;
291 copy_m4_m4(best_mat_dst, mat_dst);
292 }
293 }
294
295 BLI_space_transform_global_from_matrices(r_space_transform, best_mat_dst, mat_src);
296}
297
299
300/* -------------------------------------------------------------------- */
303
304void BKE_mesh_remap_init(MeshPairRemap *map, const int items_num)
305{
307
309
310 map->items = static_cast<MeshPairRemapItem *>(
311 BLI_memarena_alloc(mem, sizeof(*map->items) * size_t(items_num)));
312 map->items_num = items_num;
313
314 map->mem = mem;
315}
316
318{
319 if (map->mem) {
321 }
322
323 map->items_num = 0;
324 map->items = nullptr;
325 map->mem = nullptr;
326}
327
329 const int index,
330 const float /*hit_dist*/,
331 const int island,
332 const int sources_num,
333 const int *indices_src,
334 const float *weights_src)
335{
336 MeshPairRemapItem *mapit = &map->items[index];
337 MemArena *mem = map->mem;
338
339 if (sources_num) {
340 mapit->sources_num = sources_num;
341 mapit->indices_src = static_cast<int *>(
342 BLI_memarena_alloc(mem, sizeof(*mapit->indices_src) * size_t(sources_num)));
343 memcpy(mapit->indices_src, indices_src, sizeof(*mapit->indices_src) * size_t(sources_num));
344 mapit->weights_src = static_cast<float *>(
345 BLI_memarena_alloc(mem, sizeof(*mapit->weights_src) * size_t(sources_num)));
346 memcpy(mapit->weights_src, weights_src, sizeof(*mapit->weights_src) * size_t(sources_num));
347 }
348 else {
349 mapit->sources_num = 0;
350 mapit->indices_src = nullptr;
351 mapit->weights_src = nullptr;
352 }
353 // mapit->hit_dist = hit_dist;
354 mapit->island = island;
355}
356
358{
359 mesh_remap_item_define(map, index, FLT_MAX, 0, 0, nullptr, nullptr);
360}
361
363 const Span<int> corner_verts,
364 const Span<float3> positions_src,
365 const float point[3],
366 size_t *buff_size,
367 float (**vcos)[3],
368 const bool use_loops,
369 int **indices,
370 float **weights,
371 const bool do_weights,
372 int *r_closest_index)
373{
374 float (*vco)[3];
375 float ref_dist_sq = FLT_MAX;
376 int *index;
377 const int sources_num = int(face.size());
378 int i;
379
380 if (size_t(sources_num) > *buff_size) {
381 *buff_size = size_t(sources_num);
382 *vcos = static_cast<float (*)[3]>(
383 MEM_realloc_uninitialized(*vcos, sizeof(**vcos) * *buff_size));
384 *indices = static_cast<int *>(
385 MEM_realloc_uninitialized(*indices, sizeof(**indices) * *buff_size));
386 if (do_weights) {
387 *weights = static_cast<float *>(
388 MEM_realloc_uninitialized(*weights, sizeof(**weights) * *buff_size));
389 }
390 }
391
392 for (i = 0, vco = *vcos, index = *indices; i < sources_num; i++, vco++, index++) {
393 const int vert = corner_verts[face[i]];
394 *index = use_loops ? int(face[i]) : vert;
395 copy_v3_v3(*vco, positions_src[vert]);
396 if (r_closest_index) {
397 /* Find closest vert/loop in this case. */
398 const float dist_sq = len_squared_v3v3(point, *vco);
399 if (dist_sq < ref_dist_sq) {
400 ref_dist_sq = dist_sq;
401 *r_closest_index = *index;
402 }
403 }
404 }
405
406 if (do_weights) {
407 interp_weights_poly_v3(*weights, *vcos, sources_num, point);
408 }
409
410 return sources_num;
411}
412
416 float factor;
420 float hit_dist;
422 float hit_point[3];
423};
424
440
442#define MREMAP_RAYCAST_APPROXIMATE_NR 3
444#define MREMAP_RAYCAST_APPROXIMATE_FAC 5.0f
445
446/* min 16 rays/face, max 400. */
447#define MREMAP_RAYCAST_TRI_SAMPLES_MIN 4
448#define MREMAP_RAYCAST_TRI_SAMPLES_MAX 20
449
450/* Will be enough in 99% of cases. */
451#define MREMAP_DEFAULT_BUFSIZE 32
452
454 const SpaceTransform *space_transform,
455 const float max_dist,
456 const float ray_radius,
457 const Span<float3> vert_positions_dst,
458 const Mesh *me_src,
459 Mesh *me_dst,
460 MeshPairRemap *r_map)
461{
462 const float full_weight = 1.0f;
463 const float max_dist_sq = max_dist * max_dist;
464 int i;
465
467
468 BKE_mesh_remap_init(r_map, int(vert_positions_dst.size()));
469
470 if (mode == MREMAP_MODE_TOPOLOGY) {
471 BLI_assert(vert_positions_dst.size() == me_src->verts_num);
472 for (i = 0; i < vert_positions_dst.size(); i++) {
473 mesh_remap_item_define(r_map, i, FLT_MAX, 0, 1, &i, &full_weight);
474 }
475 }
476 else {
477 bke::BVHTreeFromMesh treedata{};
478 BVHTreeNearest nearest = {0};
479 BVHTreeRayHit rayhit = {0};
480 float hit_dist;
481 float tmp_co[3], tmp_no[3];
482
483 if (mode == MREMAP_MODE_VERT_NEAREST) {
484 const bke::bvh::Tree &tree = me_src->bvh_verts();
485
486 for (i = 0; i < vert_positions_dst.size(); i++) {
487 float3 co = vert_positions_dst[i];
488
489 /* Convert the vertex to tree coordinates, if needed. */
490 if (space_transform) {
491 BLI_space_transform_apply(space_transform, co);
492 }
493
494 int index;
495 if (mesh_remap_bvh_query_nearest(tree, co, max_dist, &index, &hit_dist)) {
496 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &index, &full_weight);
497 }
498 else {
499 /* No source for this dest vertex! */
501 }
502 }
503 }
505 const Span<int2> edges_src = me_src->edges();
506 const Span<float3> positions_src = me_src->vert_positions();
507
508 const bke::bvh::Tree &tree = me_src->bvh_edges();
509
510 for (i = 0; i < vert_positions_dst.size(); i++) {
511 float3 co = vert_positions_dst[i];
512
513 /* Convert the vertex to tree coordinates, if needed. */
514 if (space_transform) {
515 BLI_space_transform_apply(space_transform, co);
516 }
517
518 int edge_index;
519 if (mesh_remap_bvh_query_nearest(tree, co, max_dist, &edge_index, &hit_dist)) {
520 const int2 &edge = edges_src[edge_index];
521 const float *v1cos = positions_src[edge[0]];
522 const float *v2cos = positions_src[edge[1]];
523
524 if (mode == MREMAP_MODE_VERT_EDGE_NEAREST) {
525 const float dist_v1 = len_squared_v3v3(co, v1cos);
526 const float dist_v2 = len_squared_v3v3(co, v2cos);
527 const int index = (dist_v1 > dist_v2) ? edge[1] : edge[0];
528 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &index, &full_weight);
529 }
530 else if (mode == MREMAP_MODE_VERT_EDGEINTERP_NEAREST) {
531 int indices[2];
532 float weights[2];
533
534 indices[0] = edge[0];
535 indices[1] = edge[1];
536
537 /* Weight is inverse of point factor here... */
538 weights[0] = line_point_factor_v3(co, v2cos, v1cos);
539 CLAMP(weights[0], 0.0f, 1.0f);
540 weights[1] = 1.0f - weights[0];
541
542 mesh_remap_item_define(r_map, i, hit_dist, 0, 2, indices, weights);
543 }
544 }
545 else {
546 /* No source for this dest vertex! */
548 }
549 }
550 }
551 else if (ELEM(mode,
555 {
556 const OffsetIndices faces_src = me_src->faces();
557 const Span<int> corner_verts_src = me_src->corner_verts();
558 const Span<float3> positions_src = me_src->vert_positions();
559 const Span<float3> vert_normals_dst = me_dst->vert_normals();
560 const Span<int> tri_faces = me_src->corner_tri_faces();
561
562 size_t tmp_buff_size = MREMAP_DEFAULT_BUFSIZE;
563 float (*vcos)[3] = MEM_new_array_uninitialized<float[3]>(tmp_buff_size, __func__);
564 int *indices = MEM_new_array_uninitialized<int>(tmp_buff_size, __func__);
565 float *weights = MEM_new_array_uninitialized<float>(tmp_buff_size, __func__);
566
567 treedata = me_src->bvh_corner_tris();
568
570 for (i = 0; i < vert_positions_dst.size(); i++) {
571 copy_v3_v3(tmp_co, vert_positions_dst[i]);
572 copy_v3_v3(tmp_no, vert_normals_dst[i]);
573
574 /* Convert the vertex to tree coordinates, if needed. */
575 if (space_transform) {
576 BLI_space_transform_apply(space_transform, tmp_co);
577 BLI_space_transform_apply_normal(space_transform, tmp_no);
578 }
579
581 &treedata, &rayhit, tmp_co, tmp_no, ray_radius, max_dist, &hit_dist))
582 {
583 const int face_index = tri_faces[rayhit.index];
584 const int sources_num = mesh_remap_interp_face_data_get(faces_src[face_index],
585 corner_verts_src,
586 positions_src,
587 rayhit.co,
588 &tmp_buff_size,
589 &vcos,
590 false,
591 &indices,
592 &weights,
593 true,
594 nullptr);
595
596 mesh_remap_item_define(r_map, i, hit_dist, 0, sources_num, indices, weights);
597 }
598 else {
599 /* No source for this dest vertex! */
601 }
602 }
603 }
604 else {
605 nearest.index = -1;
606
607 for (i = 0; i < vert_positions_dst.size(); i++) {
608 copy_v3_v3(tmp_co, vert_positions_dst[i]);
609
610 /* Convert the vertex to tree coordinates, if needed. */
611 if (space_transform) {
612 BLI_space_transform_apply(space_transform, tmp_co);
613 }
614
616 &treedata, &nearest, tmp_co, max_dist_sq, &hit_dist))
617 {
618 const int face_index = tri_faces[nearest.index];
619
620 if (mode == MREMAP_MODE_VERT_FACE_NEAREST) {
621 int index;
622 mesh_remap_interp_face_data_get(faces_src[face_index],
623 corner_verts_src,
624 positions_src,
625 nearest.co,
626 &tmp_buff_size,
627 &vcos,
628 false,
629 &indices,
630 &weights,
631 false,
632 &index);
633
634 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &index, &full_weight);
635 }
636 else if (mode == MREMAP_MODE_VERT_POLYINTERP_NEAREST) {
637 const int sources_num = mesh_remap_interp_face_data_get(faces_src[face_index],
638 corner_verts_src,
639 positions_src,
640 nearest.co,
641 &tmp_buff_size,
642 &vcos,
643 false,
644 &indices,
645 &weights,
646 true,
647 nullptr);
648
649 mesh_remap_item_define(r_map, i, hit_dist, 0, sources_num, indices, weights);
650 }
651 }
652 else {
653 /* No source for this dest vertex! */
655 }
656 }
657 }
658
659 MEM_delete(vcos);
660 MEM_delete(indices);
661 MEM_delete(weights);
662 }
663 else {
664 CLOG_WARN(&LOG, "Unsupported mesh-to-mesh vertex mapping mode (%d)!", mode);
665 memset(r_map->items, 0, sizeof(*r_map->items) * size_t(vert_positions_dst.size()));
666 }
667 }
668}
669
671 const SpaceTransform *space_transform,
672 const float max_dist,
673 const float ray_radius,
674 const Span<float3> vert_positions_dst,
675 const Span<int2> edges_dst,
676 const Mesh *me_src,
677 Mesh *me_dst,
678 MeshPairRemap *r_map)
679{
680 const float full_weight = 1.0f;
681 const float max_dist_sq = max_dist * max_dist;
682 int i;
683
685
686 BKE_mesh_remap_init(r_map, int(edges_dst.size()));
687
688 if (mode == MREMAP_MODE_TOPOLOGY) {
689 BLI_assert(edges_dst.size() == me_src->edges_num);
690 for (i = 0; i < edges_dst.size(); i++) {
691 mesh_remap_item_define(r_map, i, FLT_MAX, 0, 1, &i, &full_weight);
692 }
693 }
694 else {
695 bke::BVHTreeFromMesh treedata{};
696 BVHTreeNearest nearest = {0};
697 BVHTreeRayHit rayhit = {0};
698 float hit_dist;
699 float tmp_co[3], tmp_no[3];
700
701 if (mode == MREMAP_MODE_EDGE_VERT_NEAREST) {
702 const int num_verts_src = me_src->verts_num;
703 const Span<int2> edges_src = me_src->edges();
704 const Span<float3> positions_src = me_src->vert_positions();
705
706 struct HitData {
707 float hit_dist;
708 int index;
709 };
710 HitData *v_dst_to_src_map = MEM_new_array_uninitialized<HitData>(
711 size_t(vert_positions_dst.size()), __func__);
712
713 for (i = 0; i < vert_positions_dst.size(); i++) {
714 v_dst_to_src_map[i].hit_dist = -1.0f;
715 }
716
717 Array<int> vert_to_edge_src_offsets;
718 Array<int> vert_to_edge_src_indices;
719 const GroupedSpan<int> vert_to_edge_src_map = bke::mesh::build_vert_to_edge_map(
720 edges_src, num_verts_src, vert_to_edge_src_offsets, vert_to_edge_src_indices);
721
722 const bke::bvh::Tree &tree = me_src->bvh_verts();
723
724 for (i = 0; i < edges_dst.size(); i++) {
725 const int2 &e_dst = edges_dst[i];
726 float best_totdist = FLT_MAX;
727 int best_eidx_src = -1;
728 int j = 2;
729
730 while (j--) {
731 const int vidx_dst = j ? e_dst[0] : e_dst[1];
732
733 /* Compute closest verts only once! */
734 if (v_dst_to_src_map[vidx_dst].hit_dist == -1.0f) {
735 float3 co = vert_positions_dst[vidx_dst];
736
737 /* Convert the vertex to tree coordinates, if needed. */
738 if (space_transform) {
739 BLI_space_transform_apply(space_transform, co);
740 }
741
742 int index;
743 if (mesh_remap_bvh_query_nearest(tree, co, max_dist, &index, &hit_dist)) {
744 v_dst_to_src_map[vidx_dst].hit_dist = hit_dist;
745 v_dst_to_src_map[vidx_dst].index = index;
746 }
747 else {
748 /* No source for this dest vert! */
749 v_dst_to_src_map[vidx_dst].hit_dist = FLT_MAX;
750 }
751 }
752 }
753
754 /* Now, check all source edges of closest sources vertices,
755 * and select the one giving the smallest total verts-to-verts distance. */
756 for (j = 2; j--;) {
757 const int vidx_dst = j ? e_dst[0] : e_dst[1];
758 const float first_dist = v_dst_to_src_map[vidx_dst].hit_dist;
759 const int vidx_src = v_dst_to_src_map[vidx_dst].index;
760 const int *eidx_src;
761 int k;
762
763 if (vidx_src < 0) {
764 continue;
765 }
766
767 eidx_src = vert_to_edge_src_map[vidx_src].data();
768 k = int(vert_to_edge_src_map[vidx_src].size());
769
770 for (; k--; eidx_src++) {
771 const int2 &edge_src = edges_src[*eidx_src];
772 const float *other_co_src =
773 positions_src[bke::mesh::edge_other_vert(edge_src, vidx_src)];
774 const float *other_co_dst =
775 vert_positions_dst[bke::mesh::edge_other_vert(e_dst, int(vidx_dst))];
776 const float totdist = first_dist + len_v3v3(other_co_src, other_co_dst);
777
778 if (totdist < best_totdist) {
779 best_totdist = totdist;
780 best_eidx_src = *eidx_src;
781 }
782 }
783 }
784
785 if (best_eidx_src >= 0) {
786 const float *co1_src = positions_src[edges_src[best_eidx_src][0]];
787 const float *co2_src = positions_src[edges_src[best_eidx_src][1]];
788 const float *co1_dst = vert_positions_dst[e_dst[0]];
789 const float *co2_dst = vert_positions_dst[e_dst[1]];
790 float co_src[3], co_dst[3];
791
792 /* TODO: would need an isect_seg_seg_v3(), actually! */
793 const int isect_type = isect_line_line_v3(
794 co1_src, co2_src, co1_dst, co2_dst, co_src, co_dst);
795 if (isect_type != 0) {
796 const float fac_src = line_point_factor_v3(co_src, co1_src, co2_src);
797 const float fac_dst = line_point_factor_v3(co_dst, co1_dst, co2_dst);
798 if (fac_src < 0.0f) {
799 copy_v3_v3(co_src, co1_src);
800 }
801 else if (fac_src > 1.0f) {
802 copy_v3_v3(co_src, co2_src);
803 }
804 if (fac_dst < 0.0f) {
805 copy_v3_v3(co_dst, co1_dst);
806 }
807 else if (fac_dst > 1.0f) {
808 copy_v3_v3(co_dst, co2_dst);
809 }
810 }
811 hit_dist = len_v3v3(co_dst, co_src);
812 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &best_eidx_src, &full_weight);
813 }
814 else {
815 /* No source for this dest edge! */
817 }
818 }
819
820 MEM_delete(v_dst_to_src_map);
821 }
822 else if (mode == MREMAP_MODE_EDGE_NEAREST) {
823 const bke::bvh::Tree &tree = me_src->bvh_edges();
824
825 for (i = 0; i < edges_dst.size(); i++) {
826 float3 co = math::midpoint(vert_positions_dst[edges_dst[i][0]],
827 vert_positions_dst[edges_dst[i][1]]);
828
829 /* Convert the vertex to tree coordinates, if needed. */
830 if (space_transform) {
831 BLI_space_transform_apply(space_transform, co);
832 }
833
834 int index;
835 if (mesh_remap_bvh_query_nearest(tree, co, max_dist, &index, &hit_dist)) {
836 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &index, &full_weight);
837 }
838 else {
839 /* No source for this dest edge! */
841 }
842 }
843 }
844 else if (mode == MREMAP_MODE_EDGE_POLY_NEAREST) {
845 const Span<int2> edges_src = me_src->edges();
846 const OffsetIndices faces_src = me_src->faces();
847 const Span<int> corner_edges_src = me_src->corner_edges();
848 const Span<float3> positions_src = me_src->vert_positions();
849 const Span<int> tri_faces = me_src->corner_tri_faces();
850
851 treedata = me_src->bvh_corner_tris();
852
853 for (i = 0; i < edges_dst.size(); i++) {
854 interp_v3_v3v3(tmp_co,
855 vert_positions_dst[edges_dst[i][0]],
856 vert_positions_dst[edges_dst[i][1]],
857 0.5f);
858
859 /* Convert the vertex to tree coordinates, if needed. */
860 if (space_transform) {
861 BLI_space_transform_apply(space_transform, tmp_co);
862 }
863
864 if (mesh_remap_bvhtree_query_nearest(&treedata, &nearest, tmp_co, max_dist_sq, &hit_dist))
865 {
866 const int face_index = tri_faces[nearest.index];
867 const IndexRange face_src = faces_src[face_index];
868 const int *corner_edge_src = &corner_edges_src[face_src.start()];
869 int nloops = int(face_src.size());
870 float best_dist_sq = FLT_MAX;
871 int best_eidx_src = -1;
872
873 for (; nloops--; corner_edge_src++) {
874 const int2 &edge_src = edges_src[*corner_edge_src];
875 const float *co1_src = positions_src[edge_src[0]];
876 const float *co2_src = positions_src[edge_src[1]];
877 float co_src[3];
878 float dist_sq;
879
880 interp_v3_v3v3(co_src, co1_src, co2_src, 0.5f);
881 dist_sq = len_squared_v3v3(tmp_co, co_src);
882 if (dist_sq < best_dist_sq) {
883 best_dist_sq = dist_sq;
884 best_eidx_src = *corner_edge_src;
885 }
886 }
887 if (best_eidx_src >= 0) {
888 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &best_eidx_src, &full_weight);
889 }
890 }
891 else {
892 /* No source for this dest edge! */
894 }
895 }
896 }
897 else if (mode == MREMAP_MODE_EDGE_EDGEINTERP_VNORPROJ) {
898 const int num_rays_min = 5, num_rays_max = 100;
899 const int numedges_src = me_src->edges_num;
900
901 /* Subtleness - this one we can allocate only max number of cast rays per edges! */
902 int *indices = MEM_new_array_uninitialized<int>(size_t(min_ii(numedges_src, num_rays_max)),
903 __func__);
904 /* Here it's simpler to just allocate for all edges :/ */
905 float *weights = MEM_new_array_uninitialized<float>(size_t(numedges_src), __func__);
906
907 /* This mode casts rays against the edges, which #Mesh::bvh_edges() doesn't yet support. */
908 treedata = me_src->bvh_edges_legacy();
909
910 const Span<float3> vert_normals_dst = me_dst->vert_normals();
911
912 for (i = 0; i < edges_dst.size(); i++) {
913 /* For each dst edge, we sample some rays from it (interpolated from its vertices)
914 * and use their hits to interpolate from source edges. */
915 const int2 &edge = edges_dst[i];
916 float v1_co[3], v2_co[3];
917 float v1_no[3], v2_no[3];
918
919 int grid_size;
920 float edge_dst_len;
921 float grid_step;
922
923 float totweights = 0.0f;
924 float hit_dist_accum = 0.0f;
925 int sources_num = 0;
926 int j;
927
928 copy_v3_v3(v1_co, vert_positions_dst[edge[0]]);
929 copy_v3_v3(v2_co, vert_positions_dst[edge[1]]);
930
931 copy_v3_v3(v1_no, vert_normals_dst[edge[0]]);
932 copy_v3_v3(v2_no, vert_normals_dst[edge[1]]);
933
934 /* We do our transform here, allows to interpolate from normals already in src space. */
935 if (space_transform) {
936 BLI_space_transform_apply(space_transform, v1_co);
937 BLI_space_transform_apply(space_transform, v2_co);
938 BLI_space_transform_apply_normal(space_transform, v1_no);
939 BLI_space_transform_apply_normal(space_transform, v2_no);
940 }
941
942 std::fill_n(weights, int(numedges_src), 0.0f);
943
944 /* We adjust our ray-casting grid to ray_radius (the smaller, the more rays are cast),
945 * with lower/upper bounds. */
946 edge_dst_len = len_v3v3(v1_co, v2_co);
947
948 grid_size = int((edge_dst_len / ray_radius) + 0.5f);
949 CLAMP(grid_size, num_rays_min, num_rays_max); /* min 5 rays/edge, max 100. */
950
951 /* Not actual distance here, rather an interp fac... */
952 grid_step = 1.0f / float(grid_size);
953
954 /* And now we can cast all our rays, and see what we get! */
955 for (j = 0; j < grid_size; j++) {
956 const float fac = grid_step * float(j);
957
958 int n = (ray_radius > 0.0f) ? MREMAP_RAYCAST_APPROXIMATE_NR : 1;
959 float w = 1.0f;
960
961 interp_v3_v3v3(tmp_co, v1_co, v2_co, fac);
962 interp_v3_v3v3_slerp_safe(tmp_no, v1_no, v2_no, fac);
963
964 while (n--) {
966 &treedata, &rayhit, tmp_co, tmp_no, ray_radius / w, max_dist, &hit_dist))
967 {
968 weights[rayhit.index] += w;
969 totweights += w;
970 hit_dist_accum += hit_dist;
971 break;
972 }
973 /* Next iteration will get bigger radius but smaller weight! */
975 }
976 }
977 /* A sampling is valid (as in, its result can be considered as valid sources)
978 * only if at least half of the rays found a source! */
979 if (totweights > (float(grid_size) / 2.0f)) {
980 for (j = 0; j < int(numedges_src); j++) {
981 if (!weights[j]) {
982 continue;
983 }
984 /* NOTE: sources_num is always <= j! */
985 weights[sources_num] = weights[j] / totweights;
986 indices[sources_num] = j;
987 sources_num++;
988 }
990 r_map, i, hit_dist_accum / totweights, 0, sources_num, indices, weights);
991 }
992 else {
993 /* No source for this dest edge! */
995 }
996 }
997
998 MEM_delete(indices);
999 MEM_delete(weights);
1000 }
1001 else {
1002 CLOG_WARN(&LOG, "Unsupported mesh-to-mesh edge mapping mode (%d)!", mode);
1003 memset(r_map->items, 0, sizeof(*r_map->items) * size_t(edges_dst.size()));
1004 }
1005 }
1006}
1007
1008#define POLY_UNSET 0
1009#define POLY_CENTER_INIT 1
1010#define POLY_COMPLETE 2
1011
1013 const int island_index,
1014 BLI_AStarGraph *as_graph,
1015 const Span<float3> positions,
1016 const OffsetIndices<int> faces,
1017 const Span<int> corner_verts,
1018 const int edge_idx,
1019 BLI_bitmap *done_edges,
1020 const GroupedSpan<int> edge_to_face_map,
1021 const bool is_edge_innercut,
1022 const int *face_island_index_map,
1023 float (*face_centers)[3],
1024 uchar *face_status)
1025{
1026 Array<int, 16> face_island_indices(edge_to_face_map[edge_idx].size());
1027 int i, j;
1028
1029 for (i = 0; i < edge_to_face_map[edge_idx].size(); i++) {
1030 const int pidx = edge_to_face_map[edge_idx][i];
1031 const IndexRange face = faces[pidx];
1032 const int pidx_isld = islands ? face_island_index_map[pidx] : pidx;
1033 void *custom_data = is_edge_innercut ? POINTER_FROM_INT(edge_idx) : POINTER_FROM_INT(-1);
1034
1035 if (islands && (islands->items_to_islands[face.start()] != island_index)) [[unlikely]] {
1036 /* face not in current island, happens with border edges... */
1037 face_island_indices[i] = -1;
1038 continue;
1039 }
1040
1041 if (face_status[pidx_isld] == POLY_COMPLETE) {
1042 face_island_indices[i] = pidx_isld;
1043 continue;
1044 }
1045
1046 if (face_status[pidx_isld] == POLY_UNSET) {
1047 copy_v3_v3(face_centers[pidx_isld],
1048 bke::mesh::face_center_calc(positions, corner_verts.slice(face)));
1049 BLI_astar_node_init(as_graph, pidx_isld, face_centers[pidx_isld]);
1050 face_status[pidx_isld] = POLY_CENTER_INIT;
1051 }
1052
1053 for (j = i; j--;) {
1054 float dist_cost;
1055 const int pidx_isld_other = face_island_indices[j];
1056
1057 if (pidx_isld_other == -1 || face_status[pidx_isld_other] == POLY_COMPLETE) {
1058 /* If the other face is complete, that link has already been added! */
1059 continue;
1060 }
1061 dist_cost = len_v3v3(face_centers[pidx_isld_other], face_centers[pidx_isld]);
1062 BLI_astar_node_link_add(as_graph, pidx_isld_other, pidx_isld, dist_cost, custom_data);
1063 }
1064
1065 face_island_indices[i] = pidx_isld;
1066 }
1067
1068 BLI_BITMAP_ENABLE(done_edges, edge_idx);
1069}
1070
1072 const int island_index,
1073 const Span<float3> positions,
1074 const GroupedSpan<int> edge_to_face_map,
1075 const int numedges,
1076 const OffsetIndices<int> faces,
1077 const Span<int> corner_verts,
1078 const Span<int> corner_edges,
1079 BLI_AStarGraph *r_as_graph)
1080{
1081 MeshElemMap *island_face_map = islands ? islands->islands[island_index] : nullptr;
1082 MeshElemMap *island_einnercut_map = islands ? islands->innercuts[island_index] : nullptr;
1083
1084 int *face_island_index_map = nullptr;
1085 BLI_bitmap *done_edges = BLI_BITMAP_NEW(numedges, __func__);
1086
1087 const int node_num = islands ? island_face_map->count : int(faces.size());
1088 uchar *face_status = MEM_new_array_zeroed<uchar>(size_t(node_num), __func__);
1089 float (*face_centers)[3];
1090
1091 int pidx_isld;
1092 int i;
1093
1094 BLI_astar_graph_init(r_as_graph, node_num, nullptr);
1095 /* face_centers is owned by graph memarena. */
1096 face_centers = static_cast<float (*)[3]>(
1097 BLI_memarena_calloc(r_as_graph->mem, sizeof(*face_centers) * size_t(node_num)));
1098
1099 if (islands) {
1100 /* face_island_index_map is owned by graph memarena. */
1101 face_island_index_map = static_cast<int *>(BLI_memarena_calloc(
1102 r_as_graph->mem, sizeof(*face_island_index_map) * size_t(faces.size())));
1103 for (i = island_face_map->count; i--;) {
1104 face_island_index_map[island_face_map->indices[i]] = i;
1105 }
1106
1107 r_as_graph->custom_data = face_island_index_map;
1108
1109 for (i = island_einnercut_map->count; i--;) {
1111 island_index,
1112 r_as_graph,
1113 positions,
1114 faces,
1115 corner_verts,
1116 island_einnercut_map->indices[i],
1117 done_edges,
1118 edge_to_face_map,
1119 true,
1120 face_island_index_map,
1121 face_centers,
1122 face_status);
1123 }
1124 }
1125
1126 for (pidx_isld = node_num; pidx_isld--;) {
1127 const int pidx = islands ? island_face_map->indices[pidx_isld] : pidx_isld;
1128
1129 if (face_status[pidx_isld] == POLY_COMPLETE) {
1130 continue;
1131 }
1132
1133 for (const int edge : corner_edges.slice(faces[pidx])) {
1134 if (BLI_BITMAP_TEST(done_edges, edge)) {
1135 continue;
1136 }
1137
1139 island_index,
1140 r_as_graph,
1141 positions,
1142 faces,
1143 corner_verts,
1144 edge,
1145 done_edges,
1146 edge_to_face_map,
1147 false,
1148 face_island_index_map,
1149 face_centers,
1150 face_status);
1151 }
1152 face_status[pidx_isld] = POLY_COMPLETE;
1153 }
1154
1155 MEM_delete(done_edges);
1156 MEM_delete(face_status);
1157}
1158
1159#undef POLY_UNSET
1160#undef POLY_CENTER_INIT
1161#undef POLY_COMPLETE
1162
1163/* Our 'f_cost' callback func, to find shortest face-path between two remapped-loops.
1164 * Note we do not want to make innercuts 'walls' here,
1165 * just detect when the shortest path goes by those. */
1167 BLI_AStarSolution *as_solution,
1168 BLI_AStarGNLink *link,
1169 const int node_idx_curr,
1170 const int node_idx_next,
1171 const int node_idx_dst)
1172{
1173 float *co_next, *co_dest;
1174
1175 if (link && (POINTER_AS_INT(link->custom_data) != -1)) {
1176 /* An innercut edge... We tag our solution as potentially crossing innercuts.
1177 * Note it might not be the case in the end (AStar will explore around optimal path), but helps
1178 * trimming off some processing later... */
1179 if (!POINTER_AS_INT(as_solution->custom_data)) {
1180 as_solution->custom_data = POINTER_FROM_INT(true);
1181 }
1182 }
1183
1184 /* Our heuristic part of current f_cost is distance from next node to destination one.
1185 * It is guaranteed to be less than (or equal to)
1186 * actual shortest face-path between next node and destination one. */
1187 co_next = static_cast<float *>(as_graph->nodes[node_idx_next].custom_data);
1188 co_dest = static_cast<float *>(as_graph->nodes[node_idx_dst].custom_data);
1189 return (link ? (as_solution->g_costs[node_idx_curr] + link->cost) : 0.0f) +
1190 len_v3v3(co_next, co_dest);
1191}
1192
1193#define ASTAR_STEPS_MAX 64
1194
1196 const SpaceTransform *space_transform,
1197 const float max_dist,
1198 const float ray_radius,
1199 const Mesh *mesh_dst,
1200 const Span<float3> vert_positions_dst,
1201 const Span<int> corner_verts_dst,
1202 const OffsetIndices<int> faces_dst,
1203 const Mesh *me_src,
1204 MeshRemapIslandsCalc gen_islands_src,
1205 const float islands_precision_src,
1206 MeshPairRemap *r_map)
1207{
1208 const float full_weight = 1.0f;
1209 const float max_dist_sq = max_dist * max_dist;
1210
1212 BLI_assert((islands_precision_src >= 0.0f) && (islands_precision_src <= 1.0f));
1213
1214 BKE_mesh_remap_init(r_map, int(corner_verts_dst.size()));
1215
1216 if (mode == MREMAP_MODE_TOPOLOGY) {
1217 /* In topology mapping, we assume meshes are identical, islands included! */
1218 BLI_assert(corner_verts_dst.size() == me_src->corners_num);
1219 for (int i = 0; i < corner_verts_dst.size(); i++) {
1220 mesh_remap_item_define(r_map, i, FLT_MAX, 0, 1, &i, &full_weight);
1221 }
1222 }
1223 else {
1226 Array<bke::bvh::Tree> island_vert_trees;
1228 BVHTreeNearest nearest = {0};
1229 BVHTreeRayHit rayhit = {0};
1230 int num_trees = 0;
1231 float hit_dist;
1232 float tmp_co[3], tmp_no[3];
1233
1234 const bool use_from_vert = (mode & MREMAP_USE_VERT);
1235
1236 MeshIslandStore island_store = {0};
1237 bool use_islands = false;
1238
1239 BLI_AStarGraph *as_graphdata = nullptr;
1240 BLI_AStarSolution as_solution = {0};
1241 const int isld_steps_src = (islands_precision_src ?
1242 max_ii(int(ASTAR_STEPS_MAX * islands_precision_src + 0.499f),
1243 1) :
1244 0);
1245
1246 Span<float3> face_normals_src;
1247 Span<float3> loop_normals_src;
1248
1249 Span<float3> face_normals_dst;
1250 Span<float3> loop_normals_dst;
1251
1252 Array<float3> face_cents_src;
1253
1254 GroupedSpan<int> vert_to_corner_map_src;
1255 GroupedSpan<int> vert_to_face_map_src;
1256
1257 Array<int> edge_to_face_src_offsets;
1258 Array<int> edge_to_face_src_indices;
1259 GroupedSpan<int> edge_to_face_map_src;
1260
1261 MeshElemMap *face_to_corner_tri_map_src = nullptr;
1262 int *face_to_corner_tri_map_src_buff = nullptr;
1263
1264 /* Unlike above, those are one-to-one mappings, simpler! */
1265 Span<int> loop_to_face_map_src;
1266
1267 const Span<float3> positions_src = me_src->vert_positions();
1268 const int num_verts_src = me_src->verts_num;
1269 const Span<int2> edges_src = me_src->edges();
1270 const OffsetIndices faces_src = me_src->faces();
1271 const Span<int> corner_verts_src = me_src->corner_verts();
1272 const Span<int> corner_edges_src = me_src->corner_edges();
1273 Span<int3> corner_tris_src;
1274 Span<int> tri_faces_src;
1275
1276 size_t buff_size_interp = MREMAP_DEFAULT_BUFSIZE;
1277 float (*vcos_interp)[3] = nullptr;
1278 int *indices_interp = nullptr;
1279 float *weights_interp = nullptr;
1280
1281 int tindex, pidx_dst, lidx_dst, plidx_dst, pidx_src, lidx_src, plidx_src;
1282
1283 IslandResult **islands_res;
1284 size_t islands_res_buff_size = MREMAP_DEFAULT_BUFSIZE;
1285
1286 if (!use_from_vert) {
1287 vcos_interp = MEM_new_array_uninitialized<float[3]>(buff_size_interp, __func__);
1288 indices_interp = MEM_new_array_uninitialized<int>(buff_size_interp, __func__);
1289 weights_interp = MEM_new_array_uninitialized<float>(buff_size_interp, __func__);
1290 }
1291
1292 {
1293 const bool need_lnors_src = (mode & MREMAP_USE_LOOP) && (mode & MREMAP_USE_NORMAL);
1294 const bool need_lnors_dst = need_lnors_src || (mode & MREMAP_USE_NORPROJ);
1295 const bool need_pnors_src = need_lnors_src ||
1296 ((mode & MREMAP_USE_POLY) && (mode & MREMAP_USE_NORMAL));
1297 const bool need_pnors_dst = need_lnors_dst || need_pnors_src;
1298
1299 if (need_pnors_dst) {
1300 face_normals_dst = mesh_dst->face_normals();
1301 }
1302 if (need_lnors_dst) {
1303 loop_normals_dst = mesh_dst->corner_normals();
1304 }
1305 if (need_pnors_src) {
1306 face_normals_src = me_src->face_normals();
1307 }
1308 if (need_lnors_src) {
1309 loop_normals_src = me_src->corner_normals();
1310 }
1311 }
1312
1313 if (use_from_vert) {
1314 vert_to_corner_map_src = me_src->vert_to_corner_map();
1315 if (mode & MREMAP_USE_POLY) {
1316 vert_to_face_map_src = me_src->vert_to_face_map();
1317 }
1318 }
1319
1320 /* Needed for islands (or plain mesh) to AStar graph conversion. */
1321 edge_to_face_map_src = bke::mesh::build_edge_to_face_map(faces_src,
1322 corner_edges_src,
1323 int(edges_src.size()),
1324 edge_to_face_src_offsets,
1325 edge_to_face_src_indices);
1326
1327 if (use_from_vert) {
1328 loop_to_face_map_src = me_src->corner_to_face_map();
1329 face_cents_src.reinitialize(faces_src.size());
1330 for (const int64_t i : faces_src.index_range()) {
1331 face_cents_src[i] = bke::mesh::face_center_calc(positions_src,
1332 corner_verts_src.slice(faces_src[i]));
1333 }
1334 }
1335
1336 /* Island makes things slightly more complex here.
1337 * Basically, we:
1338 * * Make one treedata for each island's elements.
1339 * * Check all loops of a same dest face against all treedata.
1340 * * Choose the island's elements giving the best results.
1341 */
1342
1343 /* First, generate the islands, if possible. */
1344 if (gen_islands_src) {
1345 const bke::AttributeAccessor attributes = me_src->attributes();
1346 const VArraySpan uv_seams = *attributes.lookup<bool>("uv_seam", bke::AttrDomain::Edge);
1347 use_islands = gen_islands_src(positions_src,
1348 edges_src,
1349 uv_seams,
1350 faces_src,
1351 corner_verts_src,
1352 corner_edges_src,
1353 &island_store);
1354
1355 num_trees = use_islands ? island_store.islands_num : 1;
1356 treedata.reinitialize(num_trees);
1357 if (isld_steps_src) {
1358 as_graphdata = MEM_new_array_zeroed<BLI_AStarGraph>(size_t(num_trees), __func__);
1359 }
1360
1361 if (use_islands) {
1362 /* We expect our islands to contain face indices, with edge indices of 'inner cuts',
1363 * and a mapping loops -> islands indices.
1364 * This implies all loops of a same face are in the same island. */
1365 BLI_assert((island_store.item_type == MISLAND_TYPE_LOOP) &&
1366 (island_store.island_type == MISLAND_TYPE_POLY) &&
1367 (island_store.innercut_type == MISLAND_TYPE_EDGE));
1368 }
1369 }
1370 else {
1371 num_trees = 1;
1372 treedata.reinitialize(1);
1373 if (isld_steps_src) {
1374 as_graphdata = MEM_new_zeroed<BLI_AStarGraph>(__func__);
1375 }
1376 }
1377
1378 /* Build our AStar graphs. */
1379 if (isld_steps_src) {
1380 for (tindex = 0; tindex < num_trees; tindex++) {
1381 mesh_island_to_astar_graph(use_islands ? &island_store : nullptr,
1382 tindex,
1383 positions_src,
1384 edge_to_face_map_src,
1385 int(edges_src.size()),
1386 faces_src,
1387 corner_verts_src,
1388 corner_edges_src,
1389 &as_graphdata[tindex]);
1390 }
1391 }
1392
1393 /* Build our BVHtrees, either from verts or tessfaces. */
1394 if (use_from_vert) {
1395 vert_trees.reinitialize(num_trees);
1396 if (use_islands) {
1397 island_vert_trees.reinitialize(num_trees);
1398 BitVector<> verts_active(num_verts_src);
1399
1400 for (tindex = 0; tindex < num_trees; tindex++) {
1401 MeshElemMap *isld = island_store.islands[tindex];
1402 verts_active.fill(false);
1403 for (int i = 0; i < isld->count; i++) {
1404 for (const int vidx_src : corner_verts_src.slice(faces_src[isld->indices[i]])) {
1405 if (!verts_active[vidx_src]) {
1406 verts_active[vidx_src].set();
1407 }
1408 }
1409 }
1410 IndexMaskMemory memory;
1411 island_vert_trees[tindex] = bke::bvh::Tree::from_points(
1412 positions_src, IndexMask::from_bits(verts_active, memory));
1413 vert_trees[tindex] = &island_vert_trees[tindex];
1414 }
1415 }
1416 else {
1417 BLI_assert(num_trees == 1);
1418 vert_trees[0] = &me_src->bvh_verts();
1419 }
1420 }
1421 else { /* We use faces. */
1422 if (use_islands) {
1423 corner_tris_src = me_src->corner_tris();
1424 tri_faces_src = me_src->corner_tri_faces();
1425 BitVector<> faces_active(corner_tris_src.size());
1426
1427 for (tindex = 0; tindex < num_trees; tindex++) {
1428 faces_active.fill(false);
1429 for (const int64_t i : faces_src.index_range()) {
1430 const IndexRange face = faces_src[i];
1431 if (island_store.items_to_islands[face.start()] == tindex) {
1432 faces_active[i].set();
1433 }
1434 }
1435 IndexMaskMemory memory;
1436 treedata[tindex] = bke::bvhtree_from_mesh_corner_tris_ex(
1437 positions_src,
1438 faces_src,
1439 corner_verts_src,
1440 corner_tris_src,
1441 IndexMask::from_bits(faces_active, memory));
1442 }
1443 }
1444 else {
1445 BLI_assert(num_trees == 1);
1446 treedata[0] = me_src->bvh_corner_tris();
1447 }
1448 }
1449
1450 /* And check each dest face! */
1451 islands_res = MEM_new_array_uninitialized<IslandResult *>(size_t(num_trees), __func__);
1452 for (tindex = 0; tindex < num_trees; tindex++) {
1453 islands_res[tindex] = MEM_new_array_uninitialized<IslandResult>(islands_res_buff_size,
1454 __func__);
1455 }
1456 const Span<int> tri_faces = me_src->corner_tri_faces();
1457
1458 for (pidx_dst = 0; pidx_dst < faces_dst.size(); pidx_dst++) {
1459 const IndexRange face_dst = faces_dst[pidx_dst];
1460 float pnor_dst[3];
1461
1462 /* Only in use_from_vert case, we may need faces' centers as fallback
1463 * in case we cannot decide which corner to use from normals only. */
1464 float3 pcent_dst;
1465 bool pcent_dst_valid = false;
1466
1468 copy_v3_v3(pnor_dst, face_normals_dst[pidx_dst]);
1469 if (space_transform) {
1470 BLI_space_transform_apply_normal(space_transform, pnor_dst);
1471 }
1472 }
1473
1474 if (size_t(face_dst.size()) > islands_res_buff_size) {
1475 islands_res_buff_size = size_t(face_dst.size()) + MREMAP_DEFAULT_BUFSIZE;
1476 for (tindex = 0; tindex < num_trees; tindex++) {
1477 islands_res[tindex] = static_cast<IslandResult *>(MEM_realloc_uninitialized(
1478 islands_res[tindex], sizeof(**islands_res) * islands_res_buff_size));
1479 }
1480 }
1481
1482 for (tindex = 0; tindex < num_trees; tindex++) {
1483 bke::BVHTreeFromMesh *tdata = &treedata[tindex];
1484
1485 for (plidx_dst = 0; plidx_dst < face_dst.size(); plidx_dst++) {
1486 const int vert_dst = corner_verts_dst[face_dst.start() + plidx_dst];
1487 if (use_from_vert) {
1488 Span<int> vert_to_refelem_map_src;
1489
1490 float3 co = vert_positions_dst[vert_dst];
1491
1492 /* Convert the vertex to tree coordinates, if needed. */
1493 if (space_transform) {
1494 BLI_space_transform_apply(space_transform, co);
1495 }
1496
1497 int nearest_vert_src;
1499 *vert_trees[tindex], co, max_dist, &nearest_vert_src, &hit_dist))
1500 {
1501 float (*nor_dst)[3];
1502 Span<float3> nors_src;
1503 float best_nor_dot = -2.0f;
1504 float best_sqdist_fallback = FLT_MAX;
1505 int best_index_src = -1;
1506
1508 copy_v3_v3(tmp_no, loop_normals_dst[plidx_dst + face_dst.start()]);
1509 if (space_transform) {
1510 BLI_space_transform_apply_normal(space_transform, tmp_no);
1511 }
1512 nor_dst = &tmp_no;
1513 nors_src = loop_normals_src;
1514 vert_to_refelem_map_src = vert_to_corner_map_src[nearest_vert_src];
1515 }
1516 else { /* `mode == MREMAP_MODE_LOOP_NEAREST_POLYNOR` */
1517 nor_dst = &pnor_dst;
1518 nors_src = face_normals_src;
1519 vert_to_refelem_map_src = vert_to_face_map_src[nearest_vert_src];
1520 }
1521
1522 for (const int index_src : vert_to_refelem_map_src) {
1523 BLI_assert(index_src != -1);
1524 const float dot = dot_v3v3(nors_src[index_src], *nor_dst);
1525
1526 pidx_src = ((mode == MREMAP_MODE_LOOP_NEAREST_LOOPNOR) ?
1527 loop_to_face_map_src[index_src] :
1528 index_src);
1529 /* WARNING! This is not the *real* lidx_src in case of POLYNOR, we only use it
1530 * to check we stay on current island (all loops from a given face are
1531 * on same island!). */
1532 lidx_src = ((mode == MREMAP_MODE_LOOP_NEAREST_LOOPNOR) ?
1533 index_src :
1534 int(faces_src[pidx_src].start()));
1535
1536 /* A same vert may be at the boundary of several islands! Hence, we have to ensure
1537 * face/loop we are currently considering *belongs* to current island! */
1538 if (use_islands && island_store.items_to_islands[lidx_src] != tindex) {
1539 continue;
1540 }
1541
1542 if (dot > best_nor_dot - 1e-6f) {
1543 /* We need something as fallback decision in case dest normal matches several
1544 * source normals (see #44522), using distance between faces' centers here. */
1545 float *pcent_src;
1546 float sqdist;
1547
1548 if (!pcent_dst_valid) {
1549 pcent_dst = bke::mesh::face_center_calc(vert_positions_dst,
1550 corner_verts_dst.slice(face_dst));
1551 pcent_dst_valid = true;
1552 }
1553 pcent_src = face_cents_src[pidx_src];
1554 sqdist = len_squared_v3v3(pcent_dst, pcent_src);
1555
1556 if ((dot > best_nor_dot + 1e-6f) || (sqdist < best_sqdist_fallback)) {
1557 best_nor_dot = dot;
1558 best_sqdist_fallback = sqdist;
1559 best_index_src = index_src;
1560 }
1561 }
1562 }
1563 if (best_index_src == -1) {
1564 /* We found no item to map back from closest vertex... */
1565 best_nor_dot = -1.0f;
1566 hit_dist = FLT_MAX;
1567 }
1568 else if (mode == MREMAP_MODE_LOOP_NEAREST_POLYNOR) {
1569 /* Our best_index_src is a face one for now!
1570 * Have to find its loop matching our closest vertex. */
1571 const IndexRange face_src = faces_src[best_index_src];
1572 for (plidx_src = 0; plidx_src < face_src.size(); plidx_src++) {
1573 const int vert_src = corner_verts_src[face_src.start() + plidx_src];
1574 if (vert_src == nearest_vert_src) {
1575 best_index_src = plidx_src + int(face_src.start());
1576 break;
1577 }
1578 }
1579 }
1580 best_nor_dot = (best_nor_dot + 1.0f) * 0.5f;
1581 islands_res[tindex][plidx_dst].factor = hit_dist ? (best_nor_dot / hit_dist) : 1e18f;
1582 islands_res[tindex][plidx_dst].hit_dist = hit_dist;
1583 islands_res[tindex][plidx_dst].index_src = best_index_src;
1584 }
1585 else {
1586 /* No source for this dest loop! */
1587 islands_res[tindex][plidx_dst].factor = 0.0f;
1588 islands_res[tindex][plidx_dst].hit_dist = FLT_MAX;
1589 islands_res[tindex][plidx_dst].index_src = -1;
1590 }
1591 }
1592 else if (mode & MREMAP_USE_NORPROJ) {
1593 int n = (ray_radius > 0.0f) ? MREMAP_RAYCAST_APPROXIMATE_NR : 1;
1594 float w = 1.0f;
1595
1596 copy_v3_v3(tmp_co, vert_positions_dst[vert_dst]);
1597 copy_v3_v3(tmp_no, loop_normals_dst[plidx_dst + face_dst.start()]);
1598
1599 /* We do our transform here, since we may do several raycast/nearest queries. */
1600 if (space_transform) {
1601 BLI_space_transform_apply(space_transform, tmp_co);
1602 BLI_space_transform_apply_normal(space_transform, tmp_no);
1603 }
1604
1605 while (n--) {
1607 tdata, &rayhit, tmp_co, tmp_no, ray_radius / w, max_dist, &hit_dist))
1608 {
1609 islands_res[tindex][plidx_dst].factor = (hit_dist ? (1.0f / hit_dist) : 1e18f) * w;
1610 islands_res[tindex][plidx_dst].hit_dist = hit_dist;
1611 islands_res[tindex][plidx_dst].index_src = tri_faces[rayhit.index];
1612 copy_v3_v3(islands_res[tindex][plidx_dst].hit_point, rayhit.co);
1613 break;
1614 }
1615 /* Next iteration will get bigger radius but smaller weight! */
1617 }
1618 if (n == -1) {
1619 /* Fall back to 'nearest' hit here, loops usually comes in 'face group', not good to
1620 * have only part of one dest face's loops to map to source.
1621 * Note that since we give this a null weight, if whole weight for a given face
1622 * is null, it means none of its loop mapped to this source island,
1623 * hence we can skip it later.
1624 */
1625 copy_v3_v3(tmp_co, vert_positions_dst[vert_dst]);
1626 nearest.index = -1;
1627
1628 /* Convert the vertex to tree coordinates, if needed. */
1629 if (space_transform) {
1630 BLI_space_transform_apply(space_transform, tmp_co);
1631 }
1632
1633 /* In any case, this fallback nearest hit should have no weight at all
1634 * in 'best island' decision! */
1635 islands_res[tindex][plidx_dst].factor = 0.0f;
1636
1638 tdata, &nearest, tmp_co, max_dist_sq, &hit_dist))
1639 {
1640 islands_res[tindex][plidx_dst].hit_dist = hit_dist;
1641 islands_res[tindex][plidx_dst].index_src = tri_faces[nearest.index];
1642 copy_v3_v3(islands_res[tindex][plidx_dst].hit_point, nearest.co);
1643 }
1644 else {
1645 /* No source for this dest loop! */
1646 islands_res[tindex][plidx_dst].hit_dist = FLT_MAX;
1647 islands_res[tindex][plidx_dst].index_src = -1;
1648 }
1649 }
1650 }
1651 else { /* Nearest face either to use all its loops/verts or just closest one. */
1652 copy_v3_v3(tmp_co, vert_positions_dst[vert_dst]);
1653 nearest.index = -1;
1654
1655 /* Convert the vertex to tree coordinates, if needed. */
1656 if (space_transform) {
1657 BLI_space_transform_apply(space_transform, tmp_co);
1658 }
1659
1660 if (mesh_remap_bvhtree_query_nearest(tdata, &nearest, tmp_co, max_dist_sq, &hit_dist))
1661 {
1662 islands_res[tindex][plidx_dst].factor = hit_dist ? (1.0f / hit_dist) : 1e18f;
1663 islands_res[tindex][plidx_dst].hit_dist = hit_dist;
1664 islands_res[tindex][plidx_dst].index_src = tri_faces[nearest.index];
1665 copy_v3_v3(islands_res[tindex][plidx_dst].hit_point, nearest.co);
1666 }
1667 else {
1668 /* No source for this dest loop! */
1669 islands_res[tindex][plidx_dst].factor = 0.0f;
1670 islands_res[tindex][plidx_dst].hit_dist = FLT_MAX;
1671 islands_res[tindex][plidx_dst].index_src = -1;
1672 }
1673 }
1674 }
1675 }
1676
1677 /* And now, find best island to use! */
1678 /* We have to first select the 'best source island' for given dst face and its loops.
1679 * Then, we have to check that face does not 'spread' across some island's limits
1680 * (like inner seams for UVs, etc.).
1681 * Note we only still partially support that kind of situation here, i.e.
1682 * Faces spreading over actual cracks
1683 * (like a narrow space without faces on src, splitting a 'tube-like' geometry).
1684 * That kind of situation should be relatively rare, though.
1685 */
1686 /* XXX This block in itself is big and complex enough to be a separate function but...
1687 * it uses a bunch of locale vars.
1688 * Not worth sending all that through parameters (for now at least). */
1689 {
1690 BLI_AStarGraph *as_graph = nullptr;
1691 int *face_island_index_map = nullptr;
1692 int pidx_src_prev = -1;
1693
1694 MeshElemMap *best_island = nullptr;
1695 float best_island_fac = 0.0f;
1696 int best_island_index = -1;
1697
1698 for (tindex = 0; tindex < num_trees; tindex++) {
1699 float island_fac = 0.0f;
1700
1701 for (plidx_dst = 0; plidx_dst < face_dst.size(); plidx_dst++) {
1702 island_fac += islands_res[tindex][plidx_dst].factor;
1703 }
1704 island_fac /= float(face_dst.size());
1705
1706 if (island_fac > best_island_fac) {
1707 best_island_fac = island_fac;
1708 best_island_index = tindex;
1709 }
1710 }
1711
1712 if (best_island_index != -1 && isld_steps_src) {
1713 best_island = use_islands ? island_store.islands[best_island_index] : nullptr;
1714 as_graph = &as_graphdata[best_island_index];
1715 face_island_index_map = static_cast<int *>(as_graph->custom_data);
1716 BLI_astar_solution_init(as_graph, &as_solution, nullptr);
1717 }
1718
1719 for (plidx_dst = 0; plidx_dst < face_dst.size(); plidx_dst++) {
1720 IslandResult *isld_res;
1721 lidx_dst = plidx_dst + int(face_dst.start());
1722
1723 if (best_island_index == -1) {
1724 /* No source for any loops of our dest face in any source islands. */
1725 BKE_mesh_remap_item_define_invalid(r_map, lidx_dst);
1726 continue;
1727 }
1728
1729 as_solution.custom_data = POINTER_FROM_INT(false);
1730
1731 isld_res = &islands_res[best_island_index][plidx_dst];
1732 if (use_from_vert) {
1733 /* Indices stored in islands_res are those of loops, one per dest loop. */
1734 lidx_src = isld_res->index_src;
1735 if (lidx_src >= 0) {
1736 pidx_src = loop_to_face_map_src[lidx_src];
1737 /* If prev and curr face are the same, no need to do anything more!!! */
1738 if (!ELEM(pidx_src_prev, -1, pidx_src) && isld_steps_src) {
1739 int pidx_isld_src, pidx_isld_src_prev;
1740 if (face_island_index_map) {
1741 pidx_isld_src = face_island_index_map[pidx_src];
1742 pidx_isld_src_prev = face_island_index_map[pidx_src_prev];
1743 }
1744 else {
1745 pidx_isld_src = pidx_src;
1746 pidx_isld_src_prev = pidx_src_prev;
1747 }
1748
1749 BLI_astar_graph_solve(as_graph,
1750 pidx_isld_src_prev,
1751 pidx_isld_src,
1753 &as_solution,
1754 isld_steps_src);
1755 if (POINTER_AS_INT(as_solution.custom_data) && (as_solution.steps > 0)) {
1756 /* Find first 'cutting edge' on path, and bring back lidx_src on face just
1757 * before that edge.
1758 * Note we could try to be much smarter, g.g. Storing a whole face's indices,
1759 * and making decision (on which side of cutting edge(s!) to be) on the end,
1760 * but this is one more level of complexity, better to first see if
1761 * simple solution works!
1762 */
1763 int last_valid_pidx_isld_src = -1;
1764 /* Note we go backward here, from dest to src face. */
1765 for (int i = as_solution.steps - 1; i--;) {
1766 BLI_AStarGNLink *as_link = as_solution.prev_links[pidx_isld_src];
1767 const int eidx = POINTER_AS_INT(as_link->custom_data);
1768 pidx_isld_src = as_solution.prev_nodes[pidx_isld_src];
1769 BLI_assert(pidx_isld_src != -1);
1770 if (eidx != -1) {
1771 /* we are 'crossing' a cutting edge. */
1772 last_valid_pidx_isld_src = pidx_isld_src;
1773 }
1774 }
1775 if (last_valid_pidx_isld_src != -1) {
1776 /* Find a new valid loop in that new face (nearest one for now).
1777 * Note we could be much more subtle here, again that's for later... */
1778 float best_dist_sq = FLT_MAX;
1779
1780 copy_v3_v3(tmp_co, vert_positions_dst[corner_verts_dst[lidx_dst]]);
1781
1782 /* We do our transform here,
1783 * since we may do several raycast/nearest queries. */
1784 if (space_transform) {
1785 BLI_space_transform_apply(space_transform, tmp_co);
1786 }
1787
1788 pidx_src = (use_islands ? best_island->indices[last_valid_pidx_isld_src] :
1789 last_valid_pidx_isld_src);
1790 const IndexRange face_src = faces_src[pidx_src];
1791 for (const int64_t corner : face_src) {
1792 const int vert_src = corner_verts_src[corner];
1793 const float dist_sq = len_squared_v3v3(positions_src[vert_src], tmp_co);
1794 if (dist_sq < best_dist_sq) {
1795 best_dist_sq = dist_sq;
1796 lidx_src = int(corner);
1797 }
1798 }
1799 }
1800 }
1801 }
1803 lidx_dst,
1804 isld_res->hit_dist,
1805 best_island_index,
1806 1,
1807 &lidx_src,
1808 &full_weight);
1809 pidx_src_prev = pidx_src;
1810 }
1811 else {
1812 /* No source for this loop in this island. */
1813 /* TODO: would probably be better to get a source
1814 * at all cost in best island anyway? */
1816 r_map, lidx_dst, FLT_MAX, best_island_index, 0, nullptr, nullptr);
1817 }
1818 }
1819 else {
1820 /* Else, we use source face, indices stored in islands_res are those of faces. */
1821 pidx_src = isld_res->index_src;
1822 if (pidx_src >= 0) {
1823 float *hit_co = isld_res->hit_point;
1824 int best_loop_index_src;
1825
1826 const IndexRange face_src = faces_src[pidx_src];
1827 /* If prev and curr face are the same, no need to do anything more!!! */
1828 if (!ELEM(pidx_src_prev, -1, pidx_src) && isld_steps_src) {
1829 int pidx_isld_src, pidx_isld_src_prev;
1830 if (face_island_index_map) {
1831 pidx_isld_src = face_island_index_map[pidx_src];
1832 pidx_isld_src_prev = face_island_index_map[pidx_src_prev];
1833 }
1834 else {
1835 pidx_isld_src = pidx_src;
1836 pidx_isld_src_prev = pidx_src_prev;
1837 }
1838
1839 BLI_astar_graph_solve(as_graph,
1840 pidx_isld_src_prev,
1841 pidx_isld_src,
1843 &as_solution,
1844 isld_steps_src);
1845 if (POINTER_AS_INT(as_solution.custom_data) && (as_solution.steps > 0)) {
1846 /* Find first 'cutting edge' on path, and bring back lidx_src on face just
1847 * before that edge.
1848 * Note we could try to be much smarter: e.g. Storing a whole face's indices,
1849 * and making decision (one which side of cutting edge(s)!) to be on the end,
1850 * but this is one more level of complexity, better to first see if
1851 * simple solution works!
1852 */
1853 int last_valid_pidx_isld_src = -1;
1854 /* Note we go backward here, from dest to src face. */
1855 for (int i = as_solution.steps - 1; i--;) {
1856 BLI_AStarGNLink *as_link = as_solution.prev_links[pidx_isld_src];
1857 int eidx = POINTER_AS_INT(as_link->custom_data);
1858
1859 pidx_isld_src = as_solution.prev_nodes[pidx_isld_src];
1860 BLI_assert(pidx_isld_src != -1);
1861 if (eidx != -1) {
1862 /* we are 'crossing' a cutting edge. */
1863 last_valid_pidx_isld_src = pidx_isld_src;
1864 }
1865 }
1866 if (last_valid_pidx_isld_src != -1) {
1867 /* Find a new valid loop in that new face (nearest point on face for now).
1868 * Note we could be much more subtle here, again that's for later... */
1869 float best_dist_sq = FLT_MAX;
1870 int j;
1871
1872 const int vert_dst = corner_verts_dst[lidx_dst];
1873 copy_v3_v3(tmp_co, vert_positions_dst[vert_dst]);
1874
1875 /* We do our transform here,
1876 * since we may do several raycast/nearest queries. */
1877 if (space_transform) {
1878 BLI_space_transform_apply(space_transform, tmp_co);
1879 }
1880
1881 pidx_src = (use_islands ? best_island->indices[last_valid_pidx_isld_src] :
1882 last_valid_pidx_isld_src);
1883
1884 /* Create that one on demand. */
1885 if (face_to_corner_tri_map_src == nullptr) {
1886 BKE_mesh_origindex_map_create_corner_tri(&face_to_corner_tri_map_src,
1887 &face_to_corner_tri_map_src_buff,
1888 faces_src,
1889 tri_faces_src.data(),
1890 int(tri_faces_src.size()));
1891 }
1892
1893 for (j = face_to_corner_tri_map_src[pidx_src].count; j--;) {
1894 float h[3];
1895 const int3 &tri =
1896 corner_tris_src[face_to_corner_tri_map_src[pidx_src].indices[j]];
1897 float dist_sq;
1898
1900 tmp_co,
1901 positions_src[corner_verts_src[tri[0]]],
1902 positions_src[corner_verts_src[tri[1]]],
1903 positions_src[corner_verts_src[tri[2]]]);
1904 dist_sq = len_squared_v3v3(tmp_co, h);
1905 if (dist_sq < best_dist_sq) {
1906 copy_v3_v3(hit_co, h);
1907 best_dist_sq = dist_sq;
1908 }
1909 }
1910 }
1911 }
1912 }
1913
1914 if (mode == MREMAP_MODE_LOOP_POLY_NEAREST) {
1916 corner_verts_src,
1917 positions_src,
1918 hit_co,
1919 &buff_size_interp,
1920 &vcos_interp,
1921 true,
1922 &indices_interp,
1923 &weights_interp,
1924 false,
1925 &best_loop_index_src);
1926
1928 lidx_dst,
1929 isld_res->hit_dist,
1930 best_island_index,
1931 1,
1932 &best_loop_index_src,
1933 &full_weight);
1934 }
1935 else {
1936 const int sources_num = mesh_remap_interp_face_data_get(face_src,
1937 corner_verts_src,
1938 positions_src,
1939 hit_co,
1940 &buff_size_interp,
1941 &vcos_interp,
1942 true,
1943 &indices_interp,
1944 &weights_interp,
1945 true,
1946 nullptr);
1947
1949 lidx_dst,
1950 isld_res->hit_dist,
1951 best_island_index,
1952 sources_num,
1953 indices_interp,
1954 weights_interp);
1955 }
1956
1957 pidx_src_prev = pidx_src;
1958 }
1959 else {
1960 /* No source for this loop in this island. */
1961 /* TODO: would probably be better to get a source
1962 * at all cost in best island anyway? */
1964 r_map, lidx_dst, FLT_MAX, best_island_index, 0, nullptr, nullptr);
1965 }
1966 }
1967 }
1968
1969 BLI_astar_solution_clear(&as_solution);
1970 }
1971 }
1972
1973 for (tindex = 0; tindex < num_trees; tindex++) {
1974 MEM_delete(islands_res[tindex]);
1975 if (isld_steps_src) {
1976 BLI_astar_graph_free(&as_graphdata[tindex]);
1977 }
1978 }
1979 MEM_delete(islands_res);
1980 BKE_mesh_loop_islands_free(&island_store);
1981 if (isld_steps_src) {
1982 MEM_delete(as_graphdata);
1983 BLI_astar_solution_free(&as_solution);
1984 }
1985
1986 if (face_to_corner_tri_map_src) {
1987 MEM_delete(face_to_corner_tri_map_src);
1988 }
1989 if (face_to_corner_tri_map_src_buff) {
1990 MEM_delete(face_to_corner_tri_map_src_buff);
1991 }
1992 if (vcos_interp) {
1993 MEM_delete(vcos_interp);
1994 }
1995 if (indices_interp) {
1996 MEM_delete(indices_interp);
1997 }
1998 if (weights_interp) {
1999 MEM_delete(weights_interp);
2000 }
2001 }
2002}
2003
2005 const SpaceTransform *space_transform,
2006 const float max_dist,
2007 const float ray_radius,
2008 const Mesh *mesh_dst,
2009 const Span<float3> vert_positions_dst,
2010 const Span<int> corner_verts_dst,
2011 const OffsetIndices<int> faces_dst,
2012 const Mesh *me_src,
2013 MeshPairRemap *r_map)
2014{
2015 const float full_weight = 1.0f;
2016 const float max_dist_sq = max_dist * max_dist;
2017 Span<float3> face_normals_dst;
2018 float3 tmp_co, tmp_no;
2019
2021
2022 if (mode & (MREMAP_USE_NORMAL | MREMAP_USE_NORPROJ)) {
2023 face_normals_dst = mesh_dst->face_normals();
2024 }
2025
2026 BKE_mesh_remap_init(r_map, int(faces_dst.size()));
2027
2028 if (mode == MREMAP_MODE_TOPOLOGY) {
2029 BLI_assert(faces_dst.size() == me_src->faces_num);
2030 for (const int64_t i : faces_dst.index_range()) {
2031 const int index = int(i);
2032 mesh_remap_item_define(r_map, int(i), FLT_MAX, 0, 1, &index, &full_weight);
2033 }
2034 }
2035 else {
2036 BVHTreeNearest nearest = {0};
2037 BVHTreeRayHit rayhit = {0};
2038 float hit_dist;
2039 const Span<int> tri_faces = me_src->corner_tri_faces();
2040
2041 bke::BVHTreeFromMesh treedata = me_src->bvh_corner_tris();
2042
2043 if (mode == MREMAP_MODE_POLY_NEAREST) {
2044 nearest.index = -1;
2045
2046 for (const int64_t i : faces_dst.index_range()) {
2047 const IndexRange face = faces_dst[i];
2048 tmp_co = bke::mesh::face_center_calc(vert_positions_dst, corner_verts_dst.slice(face));
2049
2050 /* Convert the vertex to tree coordinates, if needed. */
2051 if (space_transform) {
2052 BLI_space_transform_apply(space_transform, tmp_co);
2053 }
2054
2055 if (mesh_remap_bvhtree_query_nearest(&treedata, &nearest, tmp_co, max_dist_sq, &hit_dist))
2056 {
2057 const int face_index = tri_faces[nearest.index];
2058 mesh_remap_item_define(r_map, int(i), hit_dist, 0, 1, &face_index, &full_weight);
2059 }
2060 else {
2061 /* No source for this dest face! */
2063 }
2064 }
2065 }
2066 else if (mode == MREMAP_MODE_POLY_NOR) {
2067 for (const int64_t i : faces_dst.index_range()) {
2068 const IndexRange face = faces_dst[i];
2069
2070 tmp_co = bke::mesh::face_center_calc(vert_positions_dst, corner_verts_dst.slice(face));
2071 copy_v3_v3(tmp_no, face_normals_dst[i]);
2072
2073 /* Convert the vertex to tree coordinates, if needed. */
2074 if (space_transform) {
2075 BLI_space_transform_apply(space_transform, tmp_co);
2076 BLI_space_transform_apply_normal(space_transform, tmp_no);
2077 }
2078
2080 &treedata, &rayhit, tmp_co, tmp_no, ray_radius, max_dist, &hit_dist))
2081 {
2082 const int face_index = tri_faces[rayhit.index];
2083 mesh_remap_item_define(r_map, int(i), hit_dist, 0, 1, &face_index, &full_weight);
2084 }
2085 else {
2086 /* No source for this dest face! */
2088 }
2089 }
2090 }
2091 else if (mode == MREMAP_MODE_POLY_POLYINTERP_PNORPROJ) {
2092 /* We cast our rays randomly, with a pseudo-even distribution
2093 * (since we spread across tessellated triangles,
2094 * with additional weighting based on each triangle's relative area). */
2095 RNG *rng = BLI_rng_new(0);
2096
2097 const size_t numfaces_src = size_t(me_src->faces_num);
2098
2099 /* Here it's simpler to just allocate for all faces :/ */
2100 int *indices = MEM_new_array_uninitialized<int>(numfaces_src, __func__);
2101 float *weights = MEM_new_array_uninitialized<float>(numfaces_src, __func__);
2102
2103 size_t tmp_face_size = MREMAP_DEFAULT_BUFSIZE;
2104 float (*face_vcos_2d)[2] = MEM_new_array_uninitialized<float[2]>(tmp_face_size, __func__);
2105 /* Tessellated 2D face, always (num_loops - 2) triangles. */
2106 int (*tri_vidx_2d)[3] = MEM_new_array_uninitialized<int[3]>(tmp_face_size - 2, __func__);
2107
2108 for (const int64_t i : faces_dst.index_range()) {
2109 /* For each dst face, we sample some rays from it (2D grid in pnor space)
2110 * and use their hits to interpolate from source faces. */
2111 /* NOTE: dst face is early-converted into src space! */
2112 const IndexRange face = faces_dst[i];
2113
2114 int tot_rays, done_rays = 0;
2115 float face_area_2d_inv, done_area = 0.0f;
2116
2117 float3 pcent_dst;
2118 float to_pnor_2d_mat[3][3], from_pnor_2d_mat[3][3];
2119 float faces_dst_2d_min[2], faces_dst_2d_max[2], faces_dst_2d_z;
2120 float faces_dst_2d_size[2];
2121
2122 float totweights = 0.0f;
2123 float hit_dist_accum = 0.0f;
2124 int sources_num = 0;
2125 const int tris_num = int(face.size()) - 2;
2126 int j;
2127
2128 pcent_dst = bke::mesh::face_center_calc(vert_positions_dst, corner_verts_dst.slice(face));
2129
2130 copy_v3_v3(tmp_no, face_normals_dst[i]);
2131
2132 /* We do our transform here, else it'd be redone by raycast helper for each ray, ugh! */
2133 if (space_transform) {
2134 BLI_space_transform_apply(space_transform, pcent_dst);
2135 BLI_space_transform_apply_normal(space_transform, tmp_no);
2136 }
2137
2138 std::fill_n(weights, int(numfaces_src), 0.0f);
2139
2140 if (size_t(face.size()) > tmp_face_size) [[unlikely]] {
2141 tmp_face_size = size_t(face.size());
2142 face_vcos_2d = static_cast<float (*)[2]>(
2143 MEM_realloc_uninitialized(face_vcos_2d, sizeof(*face_vcos_2d) * tmp_face_size));
2144 tri_vidx_2d = static_cast<int (*)[3]>(
2145 MEM_realloc_uninitialized(tri_vidx_2d, sizeof(*tri_vidx_2d) * (tmp_face_size - 2)));
2146 }
2147
2148 axis_dominant_v3_to_m3(to_pnor_2d_mat, tmp_no);
2149 invert_m3_m3(from_pnor_2d_mat, to_pnor_2d_mat);
2150
2151 mul_m3_v3(to_pnor_2d_mat, pcent_dst);
2152 faces_dst_2d_z = pcent_dst[2];
2153
2154 /* Get (2D) bounding square of our face. */
2155 INIT_MINMAX2(faces_dst_2d_min, faces_dst_2d_max);
2156
2157 for (j = 0; j < face.size(); j++) {
2158 const int vert = corner_verts_dst[face[j]];
2159 copy_v3_v3(tmp_co, vert_positions_dst[vert]);
2160 if (space_transform) {
2161 BLI_space_transform_apply(space_transform, tmp_co);
2162 }
2163 mul_v2_m3v3(face_vcos_2d[j], to_pnor_2d_mat, tmp_co);
2164 minmax_v2v2_v2(faces_dst_2d_min, faces_dst_2d_max, face_vcos_2d[j]);
2165 }
2166
2167 /* We adjust our ray-casting grid to ray_radius (the smaller, the more rays are cast),
2168 * with lower/upper bounds. */
2169 sub_v2_v2v2(faces_dst_2d_size, faces_dst_2d_max, faces_dst_2d_min);
2170
2171 if (ray_radius) {
2172 tot_rays = int((max_ff(faces_dst_2d_size[0], faces_dst_2d_size[1]) / ray_radius) + 0.5f);
2174 }
2175 else {
2176 /* If no radius (pure rays), give max number of rays! */
2178 }
2179 tot_rays *= tot_rays;
2180
2181 face_area_2d_inv = area_poly_v2(face_vcos_2d, uint(face.size()));
2182 /* In case we have a null-area degenerated face... */
2183 face_area_2d_inv = 1.0f / max_ff(face_area_2d_inv, 1e-9f);
2184
2185 /* Tessellate our face. */
2186 if (face.size() == 3) {
2187 tri_vidx_2d[0][0] = 0;
2188 tri_vidx_2d[0][1] = 1;
2189 tri_vidx_2d[0][2] = 2;
2190 }
2191 if (face.size() == 4) {
2192 tri_vidx_2d[0][0] = 0;
2193 tri_vidx_2d[0][1] = 1;
2194 tri_vidx_2d[0][2] = 2;
2195 tri_vidx_2d[1][0] = 0;
2196 tri_vidx_2d[1][1] = 2;
2197 tri_vidx_2d[1][2] = 3;
2198 }
2199 else {
2201 face_vcos_2d, uint(face.size()), -1, reinterpret_cast<uint(*)[3]>(tri_vidx_2d));
2202 }
2203
2204 for (j = 0; j < tris_num; j++) {
2205 float *v1 = face_vcos_2d[tri_vidx_2d[j][0]];
2206 float *v2 = face_vcos_2d[tri_vidx_2d[j][1]];
2207 float *v3 = face_vcos_2d[tri_vidx_2d[j][2]];
2208 int rays_num;
2209
2210 /* All this allows us to get 'absolute' number of rays for each tri,
2211 * avoiding accumulating errors over iterations, and helping better even distribution. */
2212 done_area += area_tri_v2(v1, v2, v3);
2213 rays_num = max_ii(int(float(tot_rays) * done_area * face_area_2d_inv + 0.5f) - done_rays,
2214 0);
2215 done_rays += rays_num;
2216
2217 while (rays_num--) {
2218 int n = (ray_radius > 0.0f) ? MREMAP_RAYCAST_APPROXIMATE_NR : 1;
2219 float w = 1.0f;
2220
2221 BLI_rng_get_tri_sample_float_v2(rng, v1, v2, v3, tmp_co);
2222
2223 tmp_co[2] = faces_dst_2d_z;
2224 mul_m3_v3(from_pnor_2d_mat, tmp_co);
2225
2226 /* At this point, tmp_co is a point on our face surface, in mesh_src space! */
2227 while (n--) {
2229 &treedata, &rayhit, tmp_co, tmp_no, ray_radius / w, max_dist, &hit_dist))
2230 {
2231 const int face_index = tri_faces[rayhit.index];
2232 weights[face_index] += w;
2233 totweights += w;
2234 hit_dist_accum += hit_dist;
2235 break;
2236 }
2237 /* Next iteration will get bigger radius but smaller weight! */
2239 }
2240 }
2241 }
2242
2243 if (totweights > 0.0f) {
2244 for (j = 0; j < int(numfaces_src); j++) {
2245 if (!weights[j]) {
2246 continue;
2247 }
2248 /* NOTE: sources_num is always <= j! */
2249 weights[sources_num] = weights[j] / totweights;
2250 indices[sources_num] = j;
2251 sources_num++;
2252 }
2254 r_map, int(i), hit_dist_accum / totweights, 0, sources_num, indices, weights);
2255 }
2256 else {
2257 /* No source for this dest face! */
2259 }
2260 }
2261
2262 MEM_delete(tri_vidx_2d);
2263 MEM_delete(face_vcos_2d);
2264 MEM_delete(indices);
2265 MEM_delete(weights);
2266 BLI_rng_free(rng);
2267 }
2268 else {
2269 CLOG_WARN(&LOG, "Unsupported mesh-to-mesh face mapping mode (%d)!", mode);
2270 memset(r_map->items, 0, sizeof(*r_map->items) * size_t(faces_dst.size()));
2271 }
2272 }
2273}
2274
2275#undef MREMAP_RAYCAST_APPROXIMATE_NR
2276#undef MREMAP_RAYCAST_APPROXIMATE_FAC
2277#undef MREMAP_RAYCAST_TRI_SAMPLES_MIN
2278#undef MREMAP_RAYCAST_TRI_SAMPLES_MAX
2279#undef MREMAP_DEFAULT_BUFSIZE
2280
2282
2283} // namespace blender
CustomData interface, see also DNA_customdata_types.h.
An implementation of the A* (AStar) algorithm to solve shortest path problem.
#define BLI_BITMAP_NEW(_num, _alloc_string)
Definition BLI_bitmap.hh:39
#define BLI_BITMAP_TEST(_bitmap, _index)
Definition BLI_bitmap.hh:63
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition BLI_bitmap.hh:80
#define BLI_MEMARENA_STD_BUFSIZE
Random number functions.
#define CLOG_WARN(clg_ref,...)
Definition CLG_log.h:189
Read Blender memory allocation and freeing.
#define CLAMP(a, b, c)
#define INIT_MINMAX2(min, max)
#define POINTER_FROM_INT(i)
#define UNUSED_VARS_NDEBUG(...)
#define POINTER_AS_INT(i)
#define ELEM(...)
#define MEM_realloc_uninitialized(vmemh, len)
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
static IndexMask from_bits(BitSpan bits, LinearAllocator<> &memory)
constexpr int64_t size() const
constexpr int64_t start() const
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
void fill(const bool value)
GAttributeReader lookup(const StringRef name) const
std::optional< ClosestPointResult > closest_point(const float3 &point, float radius=std::numeric_limits< float >::max()) const
Definition bvh.cc:709
static Tree from_points(Span< float3 > positions, const IndexMask &mask)
Definition bvh.cc:391
#define FLT_MAX
#define FLT_EPSILON
float dot(VecOp< float, D >, VecOp< float, D >) RET
#define POLY_UNSET
#define MREMAP_RAYCAST_TRI_SAMPLES_MIN
#define MREMAP_RAYCAST_TRI_SAMPLES_MAX
#define MREMAP_RAYCAST_APPROXIMATE_NR
#define MREMAP_RAYCAST_APPROXIMATE_FAC
#define POLY_COMPLETE
#define MREMAP_DEFAULT_BUFSIZE
#define ASTAR_STEPS_MAX
#define POLY_CENTER_INIT
int edge_other_vert(const int2 edge, const int vert)
Definition BKE_mesh.hh:370
GroupedSpan< int > build_edge_to_face_map(OffsetIndices< int > faces, Span< int > corner_edges, int edges_num, Array< int > &r_offsets, Array< int > &r_indices)
float3 face_center_calc(Span< float3 > vert_positions, Span< int > face_verts)
GroupedSpan< int > build_vert_to_edge_map(Span< int2 > edges, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
BVHTreeFromMesh bvhtree_from_mesh_corner_tris_ex(Span< float3 > vert_positions, OffsetIndices< int > faces, Span< int > corner_verts, Span< int3 > corner_tris, const IndexMask &faces_mask, bool map_global_indices=true)
Definition bvhutils.cc:562
T distance(const T &a, const T &b)
T midpoint(const T &a, const T &b)
BMesh Iterators.
static bool mesh_remap_bvhtree_query_raycast(bke::BVHTreeFromMesh *treedata, BVHTreeRayHit *rayhit, const float co[3], const float no[3], const float radius, const float max_dist, float *r_hit_dist)
Definition mesh_remap.cc:96
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void negate_v3_v3(float r[3], const float a[3])
void mul_m3_v3(const float M[3][3], float r[3])
void BKE_mesh_remap_free(MeshPairRemap *map)
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
__int64 int64_t
Definition BKE_text.h:90
void BLI_astar_node_init(BLI_AStarGraph *as_graph, int node_index, void *custom_data)
Definition astar.cc:40
MINLINE int compare_ff_relative(float a, float b, float max_diff, int max_ulps)
void BKE_mesh_remap_calc_edges_from_mesh(int mode, const SpaceTransform *space_transform, float max_dist, float ray_radius, Span< float3 > vert_positions_dst, Span< int2 > edges_dst, const Mesh *me_src, Mesh *me_dst, MeshPairRemap *r_map)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
@ MREMAP_MODE_VERT_EDGEINTERP_NEAREST
@ MREMAP_MODE_LOOP_NEAREST_LOOPNOR
@ MREMAP_MODE_VERT_POLYINTERP_VNORPROJ
@ MREMAP_MODE_EDGE_VERT_NEAREST
@ MREMAP_MODE_EDGE_EDGEINTERP_VNORPROJ
@ MREMAP_MODE_VERT_FACE_NEAREST
@ MREMAP_MODE_POLY_POLYINTERP_PNORPROJ
@ MREMAP_MODE_LOOP_NEAREST_POLYNOR
@ MREMAP_MODE_VERT_EDGE_NEAREST
@ MREMAP_MODE_VERT_POLYINTERP_NEAREST
@ MREMAP_MODE_LOOP_POLY_NEAREST
@ MREMAP_MODE_EDGE_POLY_NEAREST
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
int BLI_bvhtree_find_nearest(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
void BKE_mesh_remap_find_best_match_from_mesh(Span< float3 > vert_positions_dst, const Mesh *me_src, SpaceTransform *r_space_transform)
void copy_m4_m3(float m1[4][4], const float m2[3][3])
void BLI_covariance_m3_v3n(const float(*cos_v3)[3], int cos_v3_num, bool use_sample_correction, float r_covmat[3][3], float r_center[3])
Compute the covariance matrix of given set of 3D coordinates.
bool invert_m3_m3(float inverse[3][3], const float mat[3][3])
void BLI_polyfill_calc(const float(*coords)[2], unsigned int coords_num, int coords_sign, unsigned int(*r_tris)[3])
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
static int mesh_remap_interp_face_data_get(const IndexRange face, const Span< int > corner_verts, const Span< float3 > positions_src, const float point[3], size_t *buff_size, float(**vcos)[3], const bool use_loops, int **indices, float **weights, const bool do_weights, int *r_closest_index)
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
static void mesh_calc_eigen_matrix(const Span< float3 > positions, float r_mat[4][4])
MINLINE int max_ii(int a, int b)
int BLI_bvhtree_ray_cast(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
static bool mesh_remap_bvhtree_query_nearest(bke::BVHTreeFromMesh *treedata, BVHTreeNearest *nearest, const float co[3], const float max_dist_sq, float *r_hit_dist)
Definition mesh_remap.cc:67
struct RNG * BLI_rng_new(unsigned int seed)
Definition rand.cc:41
void BLI_rng_get_tri_sample_float_v2(struct RNG *rng, const float v1[2], const float v2[2], const float v3[2], float r_pt[2]) ATTR_NONNULL()
Definition rand.cc:95
MINLINE float sqrtf_signed(float f)
MINLINE void mul_v3_fl(float r[3], float f)
void BKE_mesh_remap_init(MeshPairRemap *map, int items_num)
static bool mesh_remap_bvh_query_nearest(const bke::bvh::Tree &tree, const float3 &co, const float max_dist, int *r_index, float *r_hit_dist)
Definition mesh_remap.cc:52
float area_poly_v2(const float verts[][2], unsigned int nr)
Definition math_geom.cc:186
static void mesh_remap_item_define(MeshPairRemap *map, const int index, const float, const int island, const int sources_num, const int *indices_src, const float *weights_src)
VecBase< int32_t, 2 > int2
VecBase< int32_t, 3 > int3
bool BLI_astar_graph_solve(BLI_AStarGraph *as_graph, int node_index_src, int node_index_dst, astar_f_cost f_cost_cb, BLI_AStarSolution *r_solution, int max_steps)
Definition astar.cc:144
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
unsigned char uchar
Definition BKE_text.h:58
MINLINE float area_tri_v2(const float v1[2], const float v2[2], const float v3[2])
void BLI_astar_node_link_add(BLI_AStarGraph *as_graph, int node1_index, int node2_index, float cost, void *custom_data)
Definition astar.cc:45
void minmax_v2v2_v2(float min[2], float max[2], const float vec[2])
void BLI_space_transform_global_from_matrices(struct SpaceTransform *data, const float local[4][4], const float target[4][4])
void BKE_mesh_origindex_map_create_corner_tri(MeshElemMap **r_map, int **r_mem, OffsetIndices< int > faces, const int *corner_tri_faces, int corner_tris_num)
void BLI_astar_solution_free(BLI_AStarSolution *as_solution)
Definition astar.cc:112
void unit_m4(float m[4][4])
void BKE_mesh_remap_calc_loops_from_mesh(int mode, const SpaceTransform *space_transform, float max_dist, float ray_radius, const Mesh *mesh_dst, Span< float3 > vert_positions_dst, Span< int > corner_verts_dst, const OffsetIndices< int > faces_dst, const Mesh *me_src, MeshRemapIslandsCalc gen_islands_src, float islands_precision_src, MeshPairRemap *r_map)
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
void BLI_rng_free(struct RNG *rng) ATTR_NONNULL(1)
Definition rand.cc:55
void interp_weights_poly_v3(float w[], float v[][3], int n, const float co[3])
bool BLI_eigen_solve_selfadjoint_m3(const float m3[3][3], float r_eigen_values[3], float r_eigen_vectors[3][3])
Compute the eigen values and/or vectors of given 3D symmetric (aka adjoint) matrix.
void BKE_mesh_remap_calc_faces_from_mesh(int mode, const SpaceTransform *space_transform, float max_dist, float ray_radius, const Mesh *mesh_dst, Span< float3 > vert_positions_dst, Span< int > corner_verts, const OffsetIndices< int > faces_dst, const Mesh *me_src, MeshPairRemap *r_map)
float BKE_mesh_remap_calc_difference_from_mesh(const SpaceTransform *space_transform, Span< float3 > vert_positions_dst, const Mesh *me_src)
void interp_v3_v3v3_slerp_safe(float target[3], const float a[3], const float b[3], float t)
static void mesh_island_to_astar_graph(MeshIslandStore *islands, const int island_index, const Span< float3 > positions, const GroupedSpan< int > edge_to_face_map, const int numedges, const OffsetIndices< int > faces, const Span< int > corner_verts, const Span< int > corner_edges, BLI_AStarGraph *r_as_graph)
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
static void mesh_island_to_astar_graph_edge_process(MeshIslandStore *islands, const int island_index, BLI_AStarGraph *as_graph, const Span< float3 > positions, const OffsetIndices< int > faces, const Span< int > corner_verts, const int edge_idx, BLI_bitmap *done_edges, const GroupedSpan< int > edge_to_face_map, const bool is_edge_innercut, const int *face_island_index_map, float(*face_centers)[3], uchar *face_status)
unsigned int BLI_bitmap
Definition BLI_bitmap.hh:15
void unit_m3(float m[3][3])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
MINLINE float max_ff(float a, float b)
void BKE_mesh_loop_islands_free(MeshIslandStore *island_store)
void BLI_astar_solution_init(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, void *custom_data)
Definition astar.cc:71
void closest_on_tri_to_point_v3(float r[3], const float p[3], const float v1[3], const float v2[3], const float v3[3])
bool(*)(Span< float3 > vert_positions, Span< int2 > edges, Span< bool > uv_seams, OffsetIndices< int > faces, Span< int > corner_verts, Span< int > corner_edges, MeshIslandStore *r_island_store) MeshRemapIslandsCalc
void BLI_astar_graph_init(BLI_AStarGraph *as_graph, int node_num, void *custom_data)
Definition astar.cc:120
static CLG_LogRef LOG
Definition logging.cpp:12
void BLI_space_transform_apply(const struct SpaceTransform *data, float co[3])
void copy_m4_m4(float m1[4][4], const float m2[4][4])
VecBase< float, 3 > float3
void ortho_basis_v3v3_v3(float r_n1[3], float r_n2[3], const float n[3])
void BKE_mesh_remap_item_define_invalid(MeshPairRemap *map, int index)
void BLI_space_transform_apply_normal(const struct SpaceTransform *data, float no[3])
void BKE_mesh_remap_calc_verts_from_mesh(int mode, const SpaceTransform *space_transform, float max_dist, float ray_radius, Span< float3 > vert_positions_dst, const Mesh *me_src, Mesh *me_dst, MeshPairRemap *r_map)
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static float mesh_remap_calc_loops_astar_f_cost(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, BLI_AStarGNLink *link, const int node_idx_curr, const int node_idx_next, const int node_idx_dst)
MINLINE int min_ii(int a, int b)
void BLI_astar_solution_clear(BLI_AStarSolution *as_solution)
Definition astar.cc:95
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
void * BLI_memarena_calloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
int isect_line_line_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float r_i1[3], float r_i2[3])
void * MEM_new_array_zeroed(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void BLI_astar_graph_free(BLI_AStarGraph *as_graph)
Definition astar.cc:136
#define sqrtf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
BLI_AStarGNode * nodes
Definition BLI_astar.hh:57
struct MemArena * mem
Definition BLI_astar.hh:61
BLI_AStarGNLink ** prev_links
Definition BLI_astar.hh:43
MeshPairRemapItem * items
BVHTree_NearestPointCallback nearest_callback
BVHTree_RayCastCallback raycast_callback