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 bke
19 *
20 * Functions for mapping data between meshes.
21 */
22
23 #include <limits.h>
24
25 #include "CLG_log.h"
26
27 #include "MEM_guardedalloc.h"
28
29 #include "DNA_mesh_types.h"
30 #include "DNA_meshdata_types.h"
31
32 #include "BLI_alloca.h"
33 #include "BLI_astar.h"
34 #include "BLI_bitmap.h"
35 #include "BLI_math.h"
36 #include "BLI_memarena.h"
37 #include "BLI_polyfill_2d.h"
38 #include "BLI_rand.h"
39 #include "BLI_utildefines.h"
40
41 #include "BKE_bvhutils.h"
42 #include "BKE_customdata.h"
43 #include "BKE_mesh.h"
44 #include "BKE_mesh_mapping.h"
45 #include "BKE_mesh_remap.h" /* own include */
46 #include "BKE_mesh_runtime.h"
47
48 #include "BLI_strict_flags.h"
49
50 static CLG_LogRef LOG = {"bke.mesh"};
51
52 /* -------------------------------------------------------------------- */
53 /** \name Some generic helpers.
54 * \{ */
55
mesh_remap_bvhtree_query_nearest(BVHTreeFromMesh * treedata,BVHTreeNearest * nearest,const float co[3],const float max_dist_sq,float * r_hit_dist)56 static bool mesh_remap_bvhtree_query_nearest(BVHTreeFromMesh *treedata,
57 BVHTreeNearest *nearest,
58 const float co[3],
59 const float max_dist_sq,
60 float *r_hit_dist)
61 {
62 /* Use local proximity heuristics (to reduce the nearest search). */
63 if (nearest->index != -1) {
64 nearest->dist_sq = len_squared_v3v3(co, nearest->co);
65 if (nearest->dist_sq > max_dist_sq) {
66 /* The previous valid index is too far away and not valid for this check. */
67 nearest->dist_sq = max_dist_sq;
68 nearest->index = -1;
69 }
70 }
71 else {
72 nearest->dist_sq = max_dist_sq;
73 }
74 /* Compute and store result. If invalid (-1 index), keep FLT_MAX dist. */
75 BLI_bvhtree_find_nearest(treedata->tree, co, nearest, treedata->nearest_callback, treedata);
76
77 if ((nearest->index != -1) && (nearest->dist_sq <= max_dist_sq)) {
78 *r_hit_dist = sqrtf(nearest->dist_sq);
79 return true;
80 }
81
82 return false;
83 }
84
mesh_remap_bvhtree_query_raycast(BVHTreeFromMesh * treedata,BVHTreeRayHit * rayhit,const float co[3],const float no[3],const float radius,const float max_dist,float * r_hit_dist)85 static bool mesh_remap_bvhtree_query_raycast(BVHTreeFromMesh *treedata,
86 BVHTreeRayHit *rayhit,
87 const float co[3],
88 const float no[3],
89 const float radius,
90 const float max_dist,
91 float *r_hit_dist)
92 {
93 BVHTreeRayHit rayhit_tmp;
94 float inv_no[3];
95
96 rayhit->index = -1;
97 rayhit->dist = max_dist;
98 BLI_bvhtree_ray_cast(
99 treedata->tree, co, no, radius, rayhit, treedata->raycast_callback, treedata);
100
101 /* Also cast in the other direction! */
102 rayhit_tmp = *rayhit;
103 negate_v3_v3(inv_no, no);
104 BLI_bvhtree_ray_cast(
105 treedata->tree, co, inv_no, radius, &rayhit_tmp, treedata->raycast_callback, treedata);
106 if (rayhit_tmp.dist < rayhit->dist) {
107 *rayhit = rayhit_tmp;
108 }
109
110 if ((rayhit->index != -1) && (rayhit->dist <= max_dist)) {
111 *r_hit_dist = rayhit->dist;
112 return true;
113 }
114
115 return false;
116 }
117
118 /** \} */
119
120 /**
121 * \name Auto-match.
122 *
123 * Find transform of a mesh to get best match with another.
124 * \{ */
125
126 /**
127 * Compute a value of the difference between both given meshes.
128 * The smaller the result, the better the match.
129 *
130 * We return the inverse of the average of the inversed
131 * shortest distance from each dst vertex to src ones.
132 * In other words, beyond a certain (relatively small) distance, all differences have more or less
133 * the same weight in final result, which allows to reduce influence of a few high differences,
134 * in favor of a global good matching.
135 */
BKE_mesh_remap_calc_difference_from_mesh(const SpaceTransform * space_transform,const MVert * verts_dst,const int numverts_dst,Mesh * me_src)136 float BKE_mesh_remap_calc_difference_from_mesh(const SpaceTransform *space_transform,
137 const MVert *verts_dst,
138 const int numverts_dst,
139 Mesh *me_src)
140 {
141 BVHTreeFromMesh treedata = {NULL};
142 BVHTreeNearest nearest = {0};
143 float hit_dist;
144
145 float result = 0.0f;
146 int i;
147
148 BKE_bvhtree_from_mesh_get(&treedata, me_src, BVHTREE_FROM_VERTS, 2);
149 nearest.index = -1;
150
151 for (i = 0; i < numverts_dst; i++) {
152 float tmp_co[3];
153
154 copy_v3_v3(tmp_co, verts_dst[i].co);
155
156 /* Convert the vertex to tree coordinates, if needed. */
157 if (space_transform) {
158 BLI_space_transform_apply(space_transform, tmp_co);
159 }
160
161 if (mesh_remap_bvhtree_query_nearest(&treedata, &nearest, tmp_co, FLT_MAX, &hit_dist)) {
162 result += 1.0f / (hit_dist + 1.0f);
163 }
164 else {
165 /* No source for this dest vertex! */
166 result += 1e-18f;
167 }
168 }
169
170 result = ((float)numverts_dst / result) - 1.0f;
171
172 #if 0
173 printf("%s: Computed difference between meshes (the lower the better): %f\n", __func__, result);
174 #endif
175
176 return result;
177 }
178
179 /* This helper computes the eigen values & vectors for
180 * covariance matrix of all given vertices coordinates.
181 *
182 * Those vectors define the 'average ellipsoid' of the mesh (i.e. the 'best fitting' ellipsoid
183 * containing 50% of the vertices).
184 *
185 * Note that it will not perform fantastic in case two or more eigen values are equal
186 * (e.g. a cylinder or parallelepiped with a square section give two identical eigenvalues,
187 * a sphere or tetrahedron give three identical ones, etc.), since you cannot really define all
188 * axes in those cases. We default to dummy generated orthogonal vectors in this case,
189 * instead of using eigen vectors.
190 */
mesh_calc_eigen_matrix(const MVert * verts,const float (* vcos)[3],const int numverts,float r_mat[4][4])191 static void mesh_calc_eigen_matrix(const MVert *verts,
192 const float (*vcos)[3],
193 const int numverts,
194 float r_mat[4][4])
195 {
196 float center[3], covmat[3][3];
197 float eigen_val[3], eigen_vec[3][3];
198 float(*cos)[3] = NULL;
199
200 bool eigen_success;
201 int i;
202
203 if (verts) {
204 const MVert *mv;
205 float(*co)[3];
206
207 cos = MEM_mallocN(sizeof(*cos) * (size_t)numverts, __func__);
208 for (i = 0, co = cos, mv = verts; i < numverts; i++, co++, mv++) {
209 copy_v3_v3(*co, mv->co);
210 }
211 /* TODO(sergey): For until we officially drop all compilers which
212 * doesn't handle casting correct we use workaround to avoid explicit
213 * cast here.
214 */
215 vcos = (void *)cos;
216 }
217 unit_m4(r_mat);
218
219 /* Note: here we apply sample correction to covariance matrix, since we consider the vertices
220 * as a sample of the whole 'surface' population of our mesh. */
221 BLI_covariance_m3_v3n(vcos, numverts, true, covmat, center);
222
223 if (cos) {
224 MEM_freeN(cos);
225 }
226
227 eigen_success = BLI_eigen_solve_selfadjoint_m3((const float(*)[3])covmat, eigen_val, eigen_vec);
228 BLI_assert(eigen_success);
229 UNUSED_VARS_NDEBUG(eigen_success);
230
231 /* Special handling of cases where some eigen values are (nearly) identical. */
232 if (compare_ff_relative(eigen_val[0], eigen_val[1], FLT_EPSILON, 64)) {
233 if (compare_ff_relative(eigen_val[0], eigen_val[2], FLT_EPSILON, 64)) {
234 /* No preferred direction, that set of vertices has a spherical average,
235 * so we simply returned scaled/translated identity matrix (with no rotation). */
236 unit_m3(eigen_vec);
237 }
238 else {
239 /* Ellipsoid defined by eigen values/vectors has a spherical section,
240 * we can only define one axis from eigen_vec[2] (two others computed eigen vecs
241 * are not so nice for us here, they tend to 'randomly' rotate around valid one).
242 * Note that eigen vectors as returned by BLI_eigen_solve_selfadjoint_m3() are normalized. */
243 ortho_basis_v3v3_v3(eigen_vec[0], eigen_vec[1], eigen_vec[2]);
244 }
245 }
246 else if (compare_ff_relative(eigen_val[0], eigen_val[2], FLT_EPSILON, 64)) {
247 /* Same as above, but with eigen_vec[1] as valid axis. */
248 ortho_basis_v3v3_v3(eigen_vec[2], eigen_vec[0], eigen_vec[1]);
249 }
250 else if (compare_ff_relative(eigen_val[1], eigen_val[2], FLT_EPSILON, 64)) {
251 /* Same as above, but with eigen_vec[0] as valid axis. */
252 ortho_basis_v3v3_v3(eigen_vec[1], eigen_vec[2], eigen_vec[0]);
253 }
254
255 for (i = 0; i < 3; i++) {
256 float evi = eigen_val[i];
257
258 /* Protect against 1D/2D degenerated cases! */
259 /* Note: not sure why we need square root of eigen values here
260 * (which are equivalent to singular values, as far as I have understood),
261 * but it seems to heavily reduce (if not completely nullify)
262 * the error due to non-uniform scalings... */
263 evi = (evi < 1e-6f && evi > -1e-6f) ? ((evi < 0.0f) ? -1e-3f : 1e-3f) : sqrtf_signed(evi);
264 mul_v3_fl(eigen_vec[i], evi);
265 }
266
267 copy_m4_m3(r_mat, eigen_vec);
268 copy_v3_v3(r_mat[3], center);
269 }
270
271 /**
272 * Set r_space_transform so that best bbox of dst matches best bbox of src.
273 */
BKE_mesh_remap_find_best_match_from_mesh(const MVert * verts_dst,const int numverts_dst,Mesh * me_src,SpaceTransform * r_space_transform)274 void BKE_mesh_remap_find_best_match_from_mesh(const MVert *verts_dst,
275 const int numverts_dst,
276 Mesh *me_src,
277 SpaceTransform *r_space_transform)
278 {
279 /* Note that those are done so that we successively get actual mirror matrix
280 * (by multiplication of columns). */
281 const float mirrors[][3] = {
282 {-1.0f, 1.0f, 1.0f}, /* -> -1, 1, 1 */
283 {1.0f, -1.0f, 1.0f}, /* -> -1, -1, 1 */
284 {1.0f, 1.0f, -1.0f}, /* -> -1, -1, -1 */
285 {1.0f, -1.0f, 1.0f}, /* -> -1, 1, -1 */
286 {-1.0f, 1.0f, 1.0f}, /* -> 1, 1, -1 */
287 {1.0f, -1.0f, 1.0f}, /* -> 1, -1, -1 */
288 {1.0f, 1.0f, -1.0f}, /* -> 1, -1, 1 */
289 {0.0f, 0.0f, 0.0f},
290 };
291 const float(*mirr)[3];
292
293 float mat_src[4][4], mat_dst[4][4], best_mat_dst[4][4];
294 float best_match = FLT_MAX, match;
295
296 const int numverts_src = me_src->totvert;
297 float(*vcos_src)[3] = BKE_mesh_vert_coords_alloc(me_src, NULL);
298
299 mesh_calc_eigen_matrix(NULL, (const float(*)[3])vcos_src, numverts_src, mat_src);
300 mesh_calc_eigen_matrix(verts_dst, NULL, numverts_dst, mat_dst);
301
302 BLI_space_transform_global_from_matrices(r_space_transform, mat_dst, mat_src);
303 match = BKE_mesh_remap_calc_difference_from_mesh(
304 r_space_transform, verts_dst, numverts_dst, me_src);
305 best_match = match;
306 copy_m4_m4(best_mat_dst, mat_dst);
307
308 /* And now, we have to check the other sixth possible mirrored versions... */
309 for (mirr = mirrors; (*mirr)[0]; mirr++) {
310 mul_v3_fl(mat_dst[0], (*mirr)[0]);
311 mul_v3_fl(mat_dst[1], (*mirr)[1]);
312 mul_v3_fl(mat_dst[2], (*mirr)[2]);
313
314 BLI_space_transform_global_from_matrices(r_space_transform, mat_dst, mat_src);
315 match = BKE_mesh_remap_calc_difference_from_mesh(
316 r_space_transform, verts_dst, numverts_dst, me_src);
317 if (match < best_match) {
318 best_match = match;
319 copy_m4_m4(best_mat_dst, mat_dst);
320 }
321 }
322
323 BLI_space_transform_global_from_matrices(r_space_transform, best_mat_dst, mat_src);
324
325 MEM_freeN(vcos_src);
326 }
327
328 /** \} */
329
330 /** \name Mesh to mesh mapping
331 * \{ */
332
BKE_mesh_remap_calc_source_cddata_masks_from_map_modes(const int UNUSED (vert_mode),const int UNUSED (edge_mode),const int loop_mode,const int UNUSED (poly_mode),CustomData_MeshMasks * r_cddata_mask)333 void BKE_mesh_remap_calc_source_cddata_masks_from_map_modes(const int UNUSED(vert_mode),
334 const int UNUSED(edge_mode),
335 const int loop_mode,
336 const int UNUSED(poly_mode),
337 CustomData_MeshMasks *r_cddata_mask)
338 {
339 /* vert, edge and poly mapping modes never need extra cddata from source object. */
340 const bool need_lnors_src = (loop_mode & MREMAP_USE_LOOP) && (loop_mode & MREMAP_USE_NORMAL);
341 const bool need_pnors_src = need_lnors_src ||
342 ((loop_mode & MREMAP_USE_POLY) && (loop_mode & MREMAP_USE_NORMAL));
343
344 if (need_lnors_src) {
345 r_cddata_mask->lmask |= CD_MASK_NORMAL;
346 }
347 if (need_pnors_src) {
348 r_cddata_mask->pmask |= CD_MASK_NORMAL;
349 }
350 }
351
BKE_mesh_remap_init(MeshPairRemap * map,const int items_num)352 void BKE_mesh_remap_init(MeshPairRemap *map, const int items_num)
353 {
354 MemArena *mem = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
355
356 BKE_mesh_remap_free(map);
357
358 map->items = BLI_memarena_alloc(mem, sizeof(*map->items) * (size_t)items_num);
359 map->items_num = items_num;
360
361 map->mem = mem;
362 }
363
BKE_mesh_remap_free(MeshPairRemap * map)364 void BKE_mesh_remap_free(MeshPairRemap *map)
365 {
366 if (map->mem) {
367 BLI_memarena_free((MemArena *)map->mem);
368 }
369
370 map->items_num = 0;
371 map->items = NULL;
372 map->mem = NULL;
373 }
374
mesh_remap_item_define(MeshPairRemap * map,const int index,const float UNUSED (hit_dist),const int island,const int sources_num,const int * indices_src,const float * weights_src)375 static void mesh_remap_item_define(MeshPairRemap *map,
376 const int index,
377 const float UNUSED(hit_dist),
378 const int island,
379 const int sources_num,
380 const int *indices_src,
381 const float *weights_src)
382 {
383 MeshPairRemapItem *mapit = &map->items[index];
384 MemArena *mem = map->mem;
385
386 if (sources_num) {
387 mapit->sources_num = sources_num;
388 mapit->indices_src = BLI_memarena_alloc(mem,
389 sizeof(*mapit->indices_src) * (size_t)sources_num);
390 memcpy(mapit->indices_src, indices_src, sizeof(*mapit->indices_src) * (size_t)sources_num);
391 mapit->weights_src = BLI_memarena_alloc(mem,
392 sizeof(*mapit->weights_src) * (size_t)sources_num);
393 memcpy(mapit->weights_src, weights_src, sizeof(*mapit->weights_src) * (size_t)sources_num);
394 }
395 else {
396 mapit->sources_num = 0;
397 mapit->indices_src = NULL;
398 mapit->weights_src = NULL;
399 }
400 /* UNUSED */
401 // mapit->hit_dist = hit_dist;
402 mapit->island = island;
403 }
404
BKE_mesh_remap_item_define_invalid(MeshPairRemap * map,const int index)405 void BKE_mesh_remap_item_define_invalid(MeshPairRemap *map, const int index)
406 {
407 mesh_remap_item_define(map, index, FLT_MAX, 0, 0, NULL, NULL);
408 }
409
mesh_remap_interp_poly_data_get(const MPoly * mp,MLoop * mloops,const float (* vcos_src)[3],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)410 static int mesh_remap_interp_poly_data_get(const MPoly *mp,
411 MLoop *mloops,
412 const float (*vcos_src)[3],
413 const float point[3],
414 size_t *buff_size,
415 float (**vcos)[3],
416 const bool use_loops,
417 int **indices,
418 float **weights,
419 const bool do_weights,
420 int *r_closest_index)
421 {
422 MLoop *ml;
423 float(*vco)[3];
424 float ref_dist_sq = FLT_MAX;
425 int *index;
426 const int sources_num = mp->totloop;
427 int i;
428
429 if ((size_t)sources_num > *buff_size) {
430 *buff_size = (size_t)sources_num;
431 *vcos = MEM_reallocN(*vcos, sizeof(**vcos) * *buff_size);
432 *indices = MEM_reallocN(*indices, sizeof(**indices) * *buff_size);
433 if (do_weights) {
434 *weights = MEM_reallocN(*weights, sizeof(**weights) * *buff_size);
435 }
436 }
437
438 for (i = 0, ml = &mloops[mp->loopstart], vco = *vcos, index = *indices; i < sources_num;
439 i++, ml++, vco++, index++) {
440 *index = use_loops ? (int)mp->loopstart + i : (int)ml->v;
441 copy_v3_v3(*vco, vcos_src[ml->v]);
442 if (r_closest_index) {
443 /* Find closest vert/loop in this case. */
444 const float dist_sq = len_squared_v3v3(point, *vco);
445 if (dist_sq < ref_dist_sq) {
446 ref_dist_sq = dist_sq;
447 *r_closest_index = *index;
448 }
449 }
450 }
451
452 if (do_weights) {
453 interp_weights_poly_v3(*weights, *vcos, sources_num, point);
454 }
455
456 return sources_num;
457 }
458
459 /** Little helper when dealing with source islands */
460 typedef struct IslandResult {
461 /** A factor, based on which best island for a given set of elements will be selected. */
462 float factor;
463 /** Index of the source. */
464 int index_src;
465 /** The actual hit distance. */
466 float hit_dist;
467 /** The hit point, if relevant. */
468 float hit_point[3];
469 } IslandResult;
470
471 /**
472 * \note About all bvh/raycasting stuff below:
473 *
474 * * We must use our ray radius as BVH epsilon too, else rays not hitting anything but
475 * 'passing near' an item would be missed (since BVH handling would not detect them,
476 * 'refining' callbacks won't be executed, even though they would return a valid hit).
477 * * However, in 'islands' case where each hit gets a weight, 'precise' hits should have a better
478 * weight than 'approximate' hits.
479 * To address that, we simplify things with:
480 * * A first raycast with default, given rayradius;
481 * * If first one fails, we do more raycasting with bigger radius, but if hit is found
482 * it will get smaller weight.
483 *
484 * This only concerns loops, currently (because of islands), and 'sampled' edges/polys norproj.
485 */
486
487 /* At most n raycasts per 'real' ray. */
488 #define MREMAP_RAYCAST_APPROXIMATE_NR 3
489 /* Each approximated raycasts will have n times bigger radius than previous one. */
490 #define MREMAP_RAYCAST_APPROXIMATE_FAC 5.0f
491
492 /* min 16 rays/face, max 400. */
493 #define MREMAP_RAYCAST_TRI_SAMPLES_MIN 4
494 #define MREMAP_RAYCAST_TRI_SAMPLES_MAX 20
495
496 /* Will be enough in 99% of cases. */
497 #define MREMAP_DEFAULT_BUFSIZE 32
498
BKE_mesh_remap_calc_verts_from_mesh(const int mode,const SpaceTransform * space_transform,const float max_dist,const float ray_radius,const MVert * verts_dst,const int numverts_dst,const bool UNUSED (dirty_nors_dst),Mesh * me_src,MeshPairRemap * r_map)499 void BKE_mesh_remap_calc_verts_from_mesh(const int mode,
500 const SpaceTransform *space_transform,
501 const float max_dist,
502 const float ray_radius,
503 const MVert *verts_dst,
504 const int numverts_dst,
505 const bool UNUSED(dirty_nors_dst),
506 Mesh *me_src,
507 MeshPairRemap *r_map)
508 {
509 const float full_weight = 1.0f;
510 const float max_dist_sq = max_dist * max_dist;
511 int i;
512
513 BLI_assert(mode & MREMAP_MODE_VERT);
514
515 BKE_mesh_remap_init(r_map, numverts_dst);
516
517 if (mode == MREMAP_MODE_TOPOLOGY) {
518 BLI_assert(numverts_dst == me_src->totvert);
519 for (i = 0; i < numverts_dst; i++) {
520 mesh_remap_item_define(r_map, i, FLT_MAX, 0, 1, &i, &full_weight);
521 }
522 }
523 else {
524 BVHTreeFromMesh treedata = {NULL};
525 BVHTreeNearest nearest = {0};
526 BVHTreeRayHit rayhit = {0};
527 float hit_dist;
528 float tmp_co[3], tmp_no[3];
529
530 if (mode == MREMAP_MODE_VERT_NEAREST) {
531 BKE_bvhtree_from_mesh_get(&treedata, me_src, BVHTREE_FROM_VERTS, 2);
532 nearest.index = -1;
533
534 for (i = 0; i < numverts_dst; i++) {
535 copy_v3_v3(tmp_co, verts_dst[i].co);
536
537 /* Convert the vertex to tree coordinates, if needed. */
538 if (space_transform) {
539 BLI_space_transform_apply(space_transform, tmp_co);
540 }
541
542 if (mesh_remap_bvhtree_query_nearest(
543 &treedata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
544 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &nearest.index, &full_weight);
545 }
546 else {
547 /* No source for this dest vertex! */
548 BKE_mesh_remap_item_define_invalid(r_map, i);
549 }
550 }
551 }
552 else if (ELEM(mode, MREMAP_MODE_VERT_EDGE_NEAREST, MREMAP_MODE_VERT_EDGEINTERP_NEAREST)) {
553 MEdge *edges_src = me_src->medge;
554 float(*vcos_src)[3] = BKE_mesh_vert_coords_alloc(me_src, NULL);
555
556 BKE_bvhtree_from_mesh_get(&treedata, me_src, BVHTREE_FROM_EDGES, 2);
557 nearest.index = -1;
558
559 for (i = 0; i < numverts_dst; i++) {
560 copy_v3_v3(tmp_co, verts_dst[i].co);
561
562 /* Convert the vertex to tree coordinates, if needed. */
563 if (space_transform) {
564 BLI_space_transform_apply(space_transform, tmp_co);
565 }
566
567 if (mesh_remap_bvhtree_query_nearest(
568 &treedata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
569 MEdge *me = &edges_src[nearest.index];
570 const float *v1cos = vcos_src[me->v1];
571 const float *v2cos = vcos_src[me->v2];
572
573 if (mode == MREMAP_MODE_VERT_EDGE_NEAREST) {
574 const float dist_v1 = len_squared_v3v3(tmp_co, v1cos);
575 const float dist_v2 = len_squared_v3v3(tmp_co, v2cos);
576 const int index = (int)((dist_v1 > dist_v2) ? me->v2 : me->v1);
577 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &index, &full_weight);
578 }
579 else if (mode == MREMAP_MODE_VERT_EDGEINTERP_NEAREST) {
580 int indices[2];
581 float weights[2];
582
583 indices[0] = (int)me->v1;
584 indices[1] = (int)me->v2;
585
586 /* Weight is inverse of point factor here... */
587 weights[0] = line_point_factor_v3(tmp_co, v2cos, v1cos);
588 CLAMP(weights[0], 0.0f, 1.0f);
589 weights[1] = 1.0f - weights[0];
590
591 mesh_remap_item_define(r_map, i, hit_dist, 0, 2, indices, weights);
592 }
593 }
594 else {
595 /* No source for this dest vertex! */
596 BKE_mesh_remap_item_define_invalid(r_map, i);
597 }
598 }
599
600 MEM_freeN(vcos_src);
601 }
602 else if (ELEM(mode,
603 MREMAP_MODE_VERT_POLY_NEAREST,
604 MREMAP_MODE_VERT_POLYINTERP_NEAREST,
605 MREMAP_MODE_VERT_POLYINTERP_VNORPROJ)) {
606 MPoly *polys_src = me_src->mpoly;
607 MLoop *loops_src = me_src->mloop;
608 float(*vcos_src)[3] = BKE_mesh_vert_coords_alloc(me_src, NULL);
609
610 size_t tmp_buff_size = MREMAP_DEFAULT_BUFSIZE;
611 float(*vcos)[3] = MEM_mallocN(sizeof(*vcos) * tmp_buff_size, __func__);
612 int *indices = MEM_mallocN(sizeof(*indices) * tmp_buff_size, __func__);
613 float *weights = MEM_mallocN(sizeof(*weights) * tmp_buff_size, __func__);
614
615 BKE_bvhtree_from_mesh_get(&treedata, me_src, BVHTREE_FROM_LOOPTRI, 2);
616
617 if (mode == MREMAP_MODE_VERT_POLYINTERP_VNORPROJ) {
618 for (i = 0; i < numverts_dst; i++) {
619 copy_v3_v3(tmp_co, verts_dst[i].co);
620 normal_short_to_float_v3(tmp_no, verts_dst[i].no);
621
622 /* Convert the vertex to tree coordinates, if needed. */
623 if (space_transform) {
624 BLI_space_transform_apply(space_transform, tmp_co);
625 BLI_space_transform_apply_normal(space_transform, tmp_no);
626 }
627
628 if (mesh_remap_bvhtree_query_raycast(
629 &treedata, &rayhit, tmp_co, tmp_no, ray_radius, max_dist, &hit_dist)) {
630 const MLoopTri *lt = &treedata.looptri[rayhit.index];
631 MPoly *mp_src = &polys_src[lt->poly];
632 const int sources_num = mesh_remap_interp_poly_data_get(mp_src,
633 loops_src,
634 (const float(*)[3])vcos_src,
635 rayhit.co,
636 &tmp_buff_size,
637 &vcos,
638 false,
639 &indices,
640 &weights,
641 true,
642 NULL);
643
644 mesh_remap_item_define(r_map, i, hit_dist, 0, sources_num, indices, weights);
645 }
646 else {
647 /* No source for this dest vertex! */
648 BKE_mesh_remap_item_define_invalid(r_map, i);
649 }
650 }
651 }
652 else {
653 nearest.index = -1;
654
655 for (i = 0; i < numverts_dst; i++) {
656 copy_v3_v3(tmp_co, verts_dst[i].co);
657
658 /* Convert the vertex to tree coordinates, if needed. */
659 if (space_transform) {
660 BLI_space_transform_apply(space_transform, tmp_co);
661 }
662
663 if (mesh_remap_bvhtree_query_nearest(
664 &treedata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
665 const MLoopTri *lt = &treedata.looptri[nearest.index];
666 MPoly *mp = &polys_src[lt->poly];
667
668 if (mode == MREMAP_MODE_VERT_POLY_NEAREST) {
669 int index;
670 mesh_remap_interp_poly_data_get(mp,
671 loops_src,
672 (const float(*)[3])vcos_src,
673 nearest.co,
674 &tmp_buff_size,
675 &vcos,
676 false,
677 &indices,
678 &weights,
679 false,
680 &index);
681
682 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &index, &full_weight);
683 }
684 else if (mode == MREMAP_MODE_VERT_POLYINTERP_NEAREST) {
685 const int sources_num = mesh_remap_interp_poly_data_get(mp,
686 loops_src,
687 (const float(*)[3])vcos_src,
688 nearest.co,
689 &tmp_buff_size,
690 &vcos,
691 false,
692 &indices,
693 &weights,
694 true,
695 NULL);
696
697 mesh_remap_item_define(r_map, i, hit_dist, 0, sources_num, indices, weights);
698 }
699 }
700 else {
701 /* No source for this dest vertex! */
702 BKE_mesh_remap_item_define_invalid(r_map, i);
703 }
704 }
705 }
706
707 MEM_freeN(vcos_src);
708 MEM_freeN(vcos);
709 MEM_freeN(indices);
710 MEM_freeN(weights);
711 }
712 else {
713 CLOG_WARN(&LOG, "Unsupported mesh-to-mesh vertex mapping mode (%d)!", mode);
714 memset(r_map->items, 0, sizeof(*r_map->items) * (size_t)numverts_dst);
715 }
716
717 free_bvhtree_from_mesh(&treedata);
718 }
719 }
720
BKE_mesh_remap_calc_edges_from_mesh(const int mode,const SpaceTransform * space_transform,const float max_dist,const float ray_radius,const MVert * verts_dst,const int numverts_dst,const MEdge * edges_dst,const int numedges_dst,const bool UNUSED (dirty_nors_dst),Mesh * me_src,MeshPairRemap * r_map)721 void BKE_mesh_remap_calc_edges_from_mesh(const int mode,
722 const SpaceTransform *space_transform,
723 const float max_dist,
724 const float ray_radius,
725 const MVert *verts_dst,
726 const int numverts_dst,
727 const MEdge *edges_dst,
728 const int numedges_dst,
729 const bool UNUSED(dirty_nors_dst),
730 Mesh *me_src,
731 MeshPairRemap *r_map)
732 {
733 const float full_weight = 1.0f;
734 const float max_dist_sq = max_dist * max_dist;
735 int i;
736
737 BLI_assert(mode & MREMAP_MODE_EDGE);
738
739 BKE_mesh_remap_init(r_map, numedges_dst);
740
741 if (mode == MREMAP_MODE_TOPOLOGY) {
742 BLI_assert(numedges_dst == me_src->totedge);
743 for (i = 0; i < numedges_dst; i++) {
744 mesh_remap_item_define(r_map, i, FLT_MAX, 0, 1, &i, &full_weight);
745 }
746 }
747 else {
748 BVHTreeFromMesh treedata = {NULL};
749 BVHTreeNearest nearest = {0};
750 BVHTreeRayHit rayhit = {0};
751 float hit_dist;
752 float tmp_co[3], tmp_no[3];
753
754 if (mode == MREMAP_MODE_EDGE_VERT_NEAREST) {
755 const int num_verts_src = me_src->totvert;
756 const int num_edges_src = me_src->totedge;
757 MEdge *edges_src = me_src->medge;
758 float(*vcos_src)[3] = BKE_mesh_vert_coords_alloc(me_src, NULL);
759
760 MeshElemMap *vert_to_edge_src_map;
761 int *vert_to_edge_src_map_mem;
762
763 struct {
764 float hit_dist;
765 int index;
766 } *v_dst_to_src_map = MEM_mallocN(sizeof(*v_dst_to_src_map) * (size_t)numverts_dst,
767 __func__);
768
769 for (i = 0; i < numverts_dst; i++) {
770 v_dst_to_src_map[i].hit_dist = -1.0f;
771 }
772
773 BKE_mesh_vert_edge_map_create(&vert_to_edge_src_map,
774 &vert_to_edge_src_map_mem,
775 edges_src,
776 num_verts_src,
777 num_edges_src);
778
779 BKE_bvhtree_from_mesh_get(&treedata, me_src, BVHTREE_FROM_VERTS, 2);
780 nearest.index = -1;
781
782 for (i = 0; i < numedges_dst; i++) {
783 const MEdge *e_dst = &edges_dst[i];
784 float best_totdist = FLT_MAX;
785 int best_eidx_src = -1;
786 int j = 2;
787
788 while (j--) {
789 const unsigned int vidx_dst = j ? e_dst->v1 : e_dst->v2;
790
791 /* Compute closest verts only once! */
792 if (v_dst_to_src_map[vidx_dst].hit_dist == -1.0f) {
793 copy_v3_v3(tmp_co, verts_dst[vidx_dst].co);
794
795 /* Convert the vertex to tree coordinates, if needed. */
796 if (space_transform) {
797 BLI_space_transform_apply(space_transform, tmp_co);
798 }
799
800 if (mesh_remap_bvhtree_query_nearest(
801 &treedata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
802 v_dst_to_src_map[vidx_dst].hit_dist = hit_dist;
803 v_dst_to_src_map[vidx_dst].index = nearest.index;
804 }
805 else {
806 /* No source for this dest vert! */
807 v_dst_to_src_map[vidx_dst].hit_dist = FLT_MAX;
808 }
809 }
810 }
811
812 /* Now, check all source edges of closest sources vertices,
813 * and select the one giving the smallest total verts-to-verts distance. */
814 for (j = 2; j--;) {
815 const unsigned int vidx_dst = j ? e_dst->v1 : e_dst->v2;
816 const float first_dist = v_dst_to_src_map[vidx_dst].hit_dist;
817 const int vidx_src = v_dst_to_src_map[vidx_dst].index;
818 int *eidx_src, k;
819
820 if (vidx_src < 0) {
821 continue;
822 }
823
824 eidx_src = vert_to_edge_src_map[vidx_src].indices;
825 k = vert_to_edge_src_map[vidx_src].count;
826
827 for (; k--; eidx_src++) {
828 MEdge *e_src = &edges_src[*eidx_src];
829 const float *other_co_src = vcos_src[BKE_mesh_edge_other_vert(e_src, vidx_src)];
830 const float *other_co_dst =
831 verts_dst[BKE_mesh_edge_other_vert(e_dst, (int)vidx_dst)].co;
832 const float totdist = first_dist + len_v3v3(other_co_src, other_co_dst);
833
834 if (totdist < best_totdist) {
835 best_totdist = totdist;
836 best_eidx_src = *eidx_src;
837 }
838 }
839 }
840
841 if (best_eidx_src >= 0) {
842 const float *co1_src = vcos_src[edges_src[best_eidx_src].v1];
843 const float *co2_src = vcos_src[edges_src[best_eidx_src].v2];
844 const float *co1_dst = verts_dst[e_dst->v1].co;
845 const float *co2_dst = verts_dst[e_dst->v2].co;
846 float co_src[3], co_dst[3];
847
848 /* TODO: would need an isect_seg_seg_v3(), actually! */
849 const int isect_type = isect_line_line_v3(
850 co1_src, co2_src, co1_dst, co2_dst, co_src, co_dst);
851 if (isect_type != 0) {
852 const float fac_src = line_point_factor_v3(co_src, co1_src, co2_src);
853 const float fac_dst = line_point_factor_v3(co_dst, co1_dst, co2_dst);
854 if (fac_src < 0.0f) {
855 copy_v3_v3(co_src, co1_src);
856 }
857 else if (fac_src > 1.0f) {
858 copy_v3_v3(co_src, co2_src);
859 }
860 if (fac_dst < 0.0f) {
861 copy_v3_v3(co_dst, co1_dst);
862 }
863 else if (fac_dst > 1.0f) {
864 copy_v3_v3(co_dst, co2_dst);
865 }
866 }
867 hit_dist = len_v3v3(co_dst, co_src);
868 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &best_eidx_src, &full_weight);
869 }
870 else {
871 /* No source for this dest edge! */
872 BKE_mesh_remap_item_define_invalid(r_map, i);
873 }
874 }
875
876 MEM_freeN(vcos_src);
877 MEM_freeN(v_dst_to_src_map);
878 MEM_freeN(vert_to_edge_src_map);
879 MEM_freeN(vert_to_edge_src_map_mem);
880 }
881 else if (mode == MREMAP_MODE_EDGE_NEAREST) {
882 BKE_bvhtree_from_mesh_get(&treedata, me_src, BVHTREE_FROM_EDGES, 2);
883 nearest.index = -1;
884
885 for (i = 0; i < numedges_dst; i++) {
886 interp_v3_v3v3(tmp_co, verts_dst[edges_dst[i].v1].co, verts_dst[edges_dst[i].v2].co, 0.5f);
887
888 /* Convert the vertex to tree coordinates, if needed. */
889 if (space_transform) {
890 BLI_space_transform_apply(space_transform, tmp_co);
891 }
892
893 if (mesh_remap_bvhtree_query_nearest(
894 &treedata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
895 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &nearest.index, &full_weight);
896 }
897 else {
898 /* No source for this dest edge! */
899 BKE_mesh_remap_item_define_invalid(r_map, i);
900 }
901 }
902 }
903 else if (mode == MREMAP_MODE_EDGE_POLY_NEAREST) {
904 MEdge *edges_src = me_src->medge;
905 MPoly *polys_src = me_src->mpoly;
906 MLoop *loops_src = me_src->mloop;
907 float(*vcos_src)[3] = BKE_mesh_vert_coords_alloc(me_src, NULL);
908
909 BKE_bvhtree_from_mesh_get(&treedata, me_src, BVHTREE_FROM_LOOPTRI, 2);
910
911 for (i = 0; i < numedges_dst; i++) {
912 interp_v3_v3v3(tmp_co, verts_dst[edges_dst[i].v1].co, verts_dst[edges_dst[i].v2].co, 0.5f);
913
914 /* Convert the vertex to tree coordinates, if needed. */
915 if (space_transform) {
916 BLI_space_transform_apply(space_transform, tmp_co);
917 }
918
919 if (mesh_remap_bvhtree_query_nearest(
920 &treedata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
921 const MLoopTri *lt = &treedata.looptri[nearest.index];
922 MPoly *mp_src = &polys_src[lt->poly];
923 MLoop *ml_src = &loops_src[mp_src->loopstart];
924 int nloops = mp_src->totloop;
925 float best_dist_sq = FLT_MAX;
926 int best_eidx_src = -1;
927
928 for (; nloops--; ml_src++) {
929 MEdge *med_src = &edges_src[ml_src->e];
930 float *co1_src = vcos_src[med_src->v1];
931 float *co2_src = vcos_src[med_src->v2];
932 float co_src[3];
933 float dist_sq;
934
935 interp_v3_v3v3(co_src, co1_src, co2_src, 0.5f);
936 dist_sq = len_squared_v3v3(tmp_co, co_src);
937 if (dist_sq < best_dist_sq) {
938 best_dist_sq = dist_sq;
939 best_eidx_src = (int)ml_src->e;
940 }
941 }
942 if (best_eidx_src >= 0) {
943 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &best_eidx_src, &full_weight);
944 }
945 }
946 else {
947 /* No source for this dest edge! */
948 BKE_mesh_remap_item_define_invalid(r_map, i);
949 }
950 }
951
952 MEM_freeN(vcos_src);
953 }
954 else if (mode == MREMAP_MODE_EDGE_EDGEINTERP_VNORPROJ) {
955 const int num_rays_min = 5, num_rays_max = 100;
956 const int numedges_src = me_src->totedge;
957
958 /* Subtleness - this one we can allocate only max number of cast rays per edges! */
959 int *indices = MEM_mallocN(sizeof(*indices) * (size_t)min_ii(numedges_src, num_rays_max),
960 __func__);
961 /* Here it's simpler to just allocate for all edges :/ */
962 float *weights = MEM_mallocN(sizeof(*weights) * (size_t)numedges_src, __func__);
963
964 BKE_bvhtree_from_mesh_get(&treedata, me_src, BVHTREE_FROM_EDGES, 2);
965
966 for (i = 0; i < numedges_dst; i++) {
967 /* For each dst edge, we sample some rays from it (interpolated from its vertices)
968 * and use their hits to interpolate from source edges. */
969 const MEdge *me = &edges_dst[i];
970 float v1_co[3], v2_co[3];
971 float v1_no[3], v2_no[3];
972
973 int grid_size;
974 float edge_dst_len;
975 float grid_step;
976
977 float totweights = 0.0f;
978 float hit_dist_accum = 0.0f;
979 int sources_num = 0;
980 int j;
981
982 copy_v3_v3(v1_co, verts_dst[me->v1].co);
983 copy_v3_v3(v2_co, verts_dst[me->v2].co);
984
985 normal_short_to_float_v3(v1_no, verts_dst[me->v1].no);
986 normal_short_to_float_v3(v2_no, verts_dst[me->v2].no);
987
988 /* We do our transform here, allows to interpolate from normals already in src space. */
989 if (space_transform) {
990 BLI_space_transform_apply(space_transform, v1_co);
991 BLI_space_transform_apply(space_transform, v2_co);
992 BLI_space_transform_apply_normal(space_transform, v1_no);
993 BLI_space_transform_apply_normal(space_transform, v2_no);
994 }
995
996 copy_vn_fl(weights, (int)numedges_src, 0.0f);
997
998 /* We adjust our ray-casting grid to ray_radius (the smaller, the more rays are cast),
999 * with lower/upper bounds. */
1000 edge_dst_len = len_v3v3(v1_co, v2_co);
1001
1002 grid_size = (int)((edge_dst_len / ray_radius) + 0.5f);
1003 CLAMP(grid_size, num_rays_min, num_rays_max); /* min 5 rays/edge, max 100. */
1004
1005 grid_step = 1.0f /
1006 (float)grid_size; /* Not actual distance here, rather an interp fac... */
1007
1008 /* And now we can cast all our rays, and see what we get! */
1009 for (j = 0; j < grid_size; j++) {
1010 const float fac = grid_step * (float)j;
1011
1012 int n = (ray_radius > 0.0f) ? MREMAP_RAYCAST_APPROXIMATE_NR : 1;
1013 float w = 1.0f;
1014
1015 interp_v3_v3v3(tmp_co, v1_co, v2_co, fac);
1016 interp_v3_v3v3_slerp_safe(tmp_no, v1_no, v2_no, fac);
1017
1018 while (n--) {
1019 if (mesh_remap_bvhtree_query_raycast(
1020 &treedata, &rayhit, tmp_co, tmp_no, ray_radius / w, max_dist, &hit_dist)) {
1021 weights[rayhit.index] += w;
1022 totweights += w;
1023 hit_dist_accum += hit_dist;
1024 break;
1025 }
1026 /* Next iteration will get bigger radius but smaller weight! */
1027 w /= MREMAP_RAYCAST_APPROXIMATE_FAC;
1028 }
1029 }
1030 /* A sampling is valid (as in, its result can be considered as valid sources)
1031 * only if at least half of the rays found a source! */
1032 if (totweights > ((float)grid_size / 2.0f)) {
1033 for (j = 0; j < (int)numedges_src; j++) {
1034 if (!weights[j]) {
1035 continue;
1036 }
1037 /* Note: sources_num is always <= j! */
1038 weights[sources_num] = weights[j] / totweights;
1039 indices[sources_num] = j;
1040 sources_num++;
1041 }
1042 mesh_remap_item_define(
1043 r_map, i, hit_dist_accum / totweights, 0, sources_num, indices, weights);
1044 }
1045 else {
1046 /* No source for this dest edge! */
1047 BKE_mesh_remap_item_define_invalid(r_map, i);
1048 }
1049 }
1050
1051 MEM_freeN(indices);
1052 MEM_freeN(weights);
1053 }
1054 else {
1055 CLOG_WARN(&LOG, "Unsupported mesh-to-mesh edge mapping mode (%d)!", mode);
1056 memset(r_map->items, 0, sizeof(*r_map->items) * (size_t)numedges_dst);
1057 }
1058
1059 free_bvhtree_from_mesh(&treedata);
1060 }
1061 }
1062
1063 #define POLY_UNSET 0
1064 #define POLY_CENTER_INIT 1
1065 #define POLY_COMPLETE 2
1066
mesh_island_to_astar_graph_edge_process(MeshIslandStore * islands,const int island_index,BLI_AStarGraph * as_graph,MVert * verts,MPoly * polys,MLoop * loops,const int edge_idx,BLI_bitmap * done_edges,MeshElemMap * edge_to_poly_map,const bool is_edge_innercut,const int * poly_island_index_map,float (* poly_centers)[3],unsigned char * poly_status)1067 static void mesh_island_to_astar_graph_edge_process(MeshIslandStore *islands,
1068 const int island_index,
1069 BLI_AStarGraph *as_graph,
1070 MVert *verts,
1071 MPoly *polys,
1072 MLoop *loops,
1073 const int edge_idx,
1074 BLI_bitmap *done_edges,
1075 MeshElemMap *edge_to_poly_map,
1076 const bool is_edge_innercut,
1077 const int *poly_island_index_map,
1078 float (*poly_centers)[3],
1079 unsigned char *poly_status)
1080 {
1081 int *poly_island_indices = BLI_array_alloca(poly_island_indices,
1082 (size_t)edge_to_poly_map[edge_idx].count);
1083 int i, j;
1084
1085 for (i = 0; i < edge_to_poly_map[edge_idx].count; i++) {
1086 const int pidx = edge_to_poly_map[edge_idx].indices[i];
1087 MPoly *mp = &polys[pidx];
1088 const int pidx_isld = islands ? poly_island_index_map[pidx] : pidx;
1089 void *custom_data = is_edge_innercut ? POINTER_FROM_INT(edge_idx) : POINTER_FROM_INT(-1);
1090
1091 if (UNLIKELY(islands && (islands->items_to_islands[mp->loopstart] != island_index))) {
1092 /* poly not in current island, happens with border edges... */
1093 poly_island_indices[i] = -1;
1094 continue;
1095 }
1096
1097 if (poly_status[pidx_isld] == POLY_COMPLETE) {
1098 poly_island_indices[i] = pidx_isld;
1099 continue;
1100 }
1101
1102 if (poly_status[pidx_isld] == POLY_UNSET) {
1103 BKE_mesh_calc_poly_center(mp, &loops[mp->loopstart], verts, poly_centers[pidx_isld]);
1104 BLI_astar_node_init(as_graph, pidx_isld, poly_centers[pidx_isld]);
1105 poly_status[pidx_isld] = POLY_CENTER_INIT;
1106 }
1107
1108 for (j = i; j--;) {
1109 float dist_cost;
1110 const int pidx_isld_other = poly_island_indices[j];
1111
1112 if (pidx_isld_other == -1 || poly_status[pidx_isld_other] == POLY_COMPLETE) {
1113 /* If the other poly is complete, that link has already been added! */
1114 continue;
1115 }
1116 dist_cost = len_v3v3(poly_centers[pidx_isld_other], poly_centers[pidx_isld]);
1117 BLI_astar_node_link_add(as_graph, pidx_isld_other, pidx_isld, dist_cost, custom_data);
1118 }
1119
1120 poly_island_indices[i] = pidx_isld;
1121 }
1122
1123 BLI_BITMAP_ENABLE(done_edges, edge_idx);
1124 }
1125
mesh_island_to_astar_graph(MeshIslandStore * islands,const int island_index,MVert * verts,MeshElemMap * edge_to_poly_map,const int numedges,MLoop * loops,MPoly * polys,const int numpolys,BLI_AStarGraph * r_as_graph)1126 static void mesh_island_to_astar_graph(MeshIslandStore *islands,
1127 const int island_index,
1128 MVert *verts,
1129 MeshElemMap *edge_to_poly_map,
1130 const int numedges,
1131 MLoop *loops,
1132 MPoly *polys,
1133 const int numpolys,
1134 BLI_AStarGraph *r_as_graph)
1135 {
1136 MeshElemMap *island_poly_map = islands ? islands->islands[island_index] : NULL;
1137 MeshElemMap *island_einnercut_map = islands ? islands->innercuts[island_index] : NULL;
1138
1139 int *poly_island_index_map = NULL;
1140 BLI_bitmap *done_edges = BLI_BITMAP_NEW(numedges, __func__);
1141
1142 const int node_num = islands ? island_poly_map->count : numpolys;
1143 unsigned char *poly_status = MEM_callocN(sizeof(*poly_status) * (size_t)node_num, __func__);
1144 float(*poly_centers)[3];
1145
1146 int pidx_isld;
1147 int i;
1148
1149 BLI_astar_graph_init(r_as_graph, node_num, NULL);
1150 /* poly_centers is owned by graph memarena. */
1151 poly_centers = BLI_memarena_calloc(r_as_graph->mem, sizeof(*poly_centers) * (size_t)node_num);
1152
1153 if (islands) {
1154 /* poly_island_index_map is owned by graph memarena. */
1155 poly_island_index_map = BLI_memarena_calloc(r_as_graph->mem,
1156 sizeof(*poly_island_index_map) * (size_t)numpolys);
1157 for (i = island_poly_map->count; i--;) {
1158 poly_island_index_map[island_poly_map->indices[i]] = i;
1159 }
1160
1161 r_as_graph->custom_data = poly_island_index_map;
1162
1163 for (i = island_einnercut_map->count; i--;) {
1164 mesh_island_to_astar_graph_edge_process(islands,
1165 island_index,
1166 r_as_graph,
1167 verts,
1168 polys,
1169 loops,
1170 island_einnercut_map->indices[i],
1171 done_edges,
1172 edge_to_poly_map,
1173 true,
1174 poly_island_index_map,
1175 poly_centers,
1176 poly_status);
1177 }
1178 }
1179
1180 for (pidx_isld = node_num; pidx_isld--;) {
1181 const int pidx = islands ? island_poly_map->indices[pidx_isld] : pidx_isld;
1182 MPoly *mp = &polys[pidx];
1183 int pl_idx, l_idx;
1184
1185 if (poly_status[pidx_isld] == POLY_COMPLETE) {
1186 continue;
1187 }
1188
1189 for (pl_idx = 0, l_idx = mp->loopstart; pl_idx < mp->totloop; pl_idx++, l_idx++) {
1190 MLoop *ml = &loops[l_idx];
1191
1192 if (BLI_BITMAP_TEST(done_edges, ml->e)) {
1193 continue;
1194 }
1195
1196 mesh_island_to_astar_graph_edge_process(islands,
1197 island_index,
1198 r_as_graph,
1199 verts,
1200 polys,
1201 loops,
1202 (int)ml->e,
1203 done_edges,
1204 edge_to_poly_map,
1205 false,
1206 poly_island_index_map,
1207 poly_centers,
1208 poly_status);
1209 }
1210 poly_status[pidx_isld] = POLY_COMPLETE;
1211 }
1212
1213 MEM_freeN(done_edges);
1214 MEM_freeN(poly_status);
1215 }
1216
1217 #undef POLY_UNSET
1218 #undef POLY_CENTER_INIT
1219 #undef POLY_COMPLETE
1220
1221 /* Our 'f_cost' callback func, to find shortest poly-path between two remapped-loops.
1222 * Note we do not want to make innercuts 'walls' here,
1223 * just detect when the shortest path goes by those. */
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)1224 static float mesh_remap_calc_loops_astar_f_cost(BLI_AStarGraph *as_graph,
1225 BLI_AStarSolution *as_solution,
1226 BLI_AStarGNLink *link,
1227 const int node_idx_curr,
1228 const int node_idx_next,
1229 const int node_idx_dst)
1230 {
1231 float *co_next, *co_dest;
1232
1233 if (link && (POINTER_AS_INT(link->custom_data) != -1)) {
1234 /* An innercut edge... We tag our solution as potentially crossing innercuts.
1235 * Note it might not be the case in the end (AStar will explore around optimal path), but helps
1236 * trimming off some processing later... */
1237 if (!POINTER_AS_INT(as_solution->custom_data)) {
1238 as_solution->custom_data = POINTER_FROM_INT(true);
1239 }
1240 }
1241
1242 /* Our heuristic part of current f_cost is distance from next node to destination one.
1243 * It is guaranteed to be less than (or equal to)
1244 * actual shortest poly-path between next node and destination one. */
1245 co_next = (float *)as_graph->nodes[node_idx_next].custom_data;
1246 co_dest = (float *)as_graph->nodes[node_idx_dst].custom_data;
1247 return (link ? (as_solution->g_costs[node_idx_curr] + link->cost) : 0.0f) +
1248 len_v3v3(co_next, co_dest);
1249 }
1250
1251 #define ASTAR_STEPS_MAX 64
1252
BKE_mesh_remap_calc_loops_from_mesh(const int mode,const SpaceTransform * space_transform,const float max_dist,const float ray_radius,MVert * verts_dst,const int numverts_dst,MEdge * edges_dst,const int numedges_dst,MLoop * loops_dst,const int numloops_dst,MPoly * polys_dst,const int numpolys_dst,CustomData * ldata_dst,CustomData * pdata_dst,const bool use_split_nors_dst,const float split_angle_dst,const bool dirty_nors_dst,Mesh * me_src,MeshRemapIslandsCalc gen_islands_src,const float islands_precision_src,MeshPairRemap * r_map)1253 void BKE_mesh_remap_calc_loops_from_mesh(const int mode,
1254 const SpaceTransform *space_transform,
1255 const float max_dist,
1256 const float ray_radius,
1257 MVert *verts_dst,
1258 const int numverts_dst,
1259 MEdge *edges_dst,
1260 const int numedges_dst,
1261 MLoop *loops_dst,
1262 const int numloops_dst,
1263 MPoly *polys_dst,
1264 const int numpolys_dst,
1265 CustomData *ldata_dst,
1266 CustomData *pdata_dst,
1267 const bool use_split_nors_dst,
1268 const float split_angle_dst,
1269 const bool dirty_nors_dst,
1270 Mesh *me_src,
1271 MeshRemapIslandsCalc gen_islands_src,
1272 const float islands_precision_src,
1273 MeshPairRemap *r_map)
1274 {
1275 const float full_weight = 1.0f;
1276 const float max_dist_sq = max_dist * max_dist;
1277
1278 int i;
1279
1280 BLI_assert(mode & MREMAP_MODE_LOOP);
1281 BLI_assert((islands_precision_src >= 0.0f) && (islands_precision_src <= 1.0f));
1282
1283 BKE_mesh_remap_init(r_map, numloops_dst);
1284
1285 if (mode == MREMAP_MODE_TOPOLOGY) {
1286 /* In topology mapping, we assume meshes are identical, islands included! */
1287 BLI_assert(numloops_dst == me_src->totloop);
1288 for (i = 0; i < numloops_dst; i++) {
1289 mesh_remap_item_define(r_map, i, FLT_MAX, 0, 1, &i, &full_weight);
1290 }
1291 }
1292 else {
1293 BVHTreeFromMesh *treedata = NULL;
1294 BVHTreeNearest nearest = {0};
1295 BVHTreeRayHit rayhit = {0};
1296 int num_trees = 0;
1297 float hit_dist;
1298 float tmp_co[3], tmp_no[3];
1299
1300 const bool use_from_vert = (mode & MREMAP_USE_VERT);
1301
1302 MeshIslandStore island_store = {0};
1303 bool use_islands = false;
1304
1305 BLI_AStarGraph *as_graphdata = NULL;
1306 BLI_AStarSolution as_solution = {0};
1307 const int isld_steps_src = (islands_precision_src ?
1308 max_ii((int)(ASTAR_STEPS_MAX * islands_precision_src + 0.499f),
1309 1) :
1310 0);
1311
1312 float(*poly_nors_src)[3] = NULL;
1313 float(*loop_nors_src)[3] = NULL;
1314 float(*poly_nors_dst)[3] = NULL;
1315 float(*loop_nors_dst)[3] = NULL;
1316
1317 float(*poly_cents_src)[3] = NULL;
1318
1319 MeshElemMap *vert_to_loop_map_src = NULL;
1320 int *vert_to_loop_map_src_buff = NULL;
1321 MeshElemMap *vert_to_poly_map_src = NULL;
1322 int *vert_to_poly_map_src_buff = NULL;
1323 MeshElemMap *edge_to_poly_map_src = NULL;
1324 int *edge_to_poly_map_src_buff = NULL;
1325 MeshElemMap *poly_to_looptri_map_src = NULL;
1326 int *poly_to_looptri_map_src_buff = NULL;
1327
1328 /* Unlike above, those are one-to-one mappings, simpler! */
1329 int *loop_to_poly_map_src = NULL;
1330
1331 MVert *verts_src = me_src->mvert;
1332 const int num_verts_src = me_src->totvert;
1333 float(*vcos_src)[3] = NULL;
1334 MEdge *edges_src = me_src->medge;
1335 const int num_edges_src = me_src->totedge;
1336 MLoop *loops_src = me_src->mloop;
1337 const int num_loops_src = me_src->totloop;
1338 MPoly *polys_src = me_src->mpoly;
1339 const int num_polys_src = me_src->totpoly;
1340 const MLoopTri *looptri_src = NULL;
1341 int num_looptri_src = 0;
1342
1343 size_t buff_size_interp = MREMAP_DEFAULT_BUFSIZE;
1344 float(*vcos_interp)[3] = NULL;
1345 int *indices_interp = NULL;
1346 float *weights_interp = NULL;
1347
1348 MLoop *ml_src, *ml_dst;
1349 MPoly *mp_src, *mp_dst;
1350 int tindex, pidx_dst, lidx_dst, plidx_dst, pidx_src, lidx_src, plidx_src;
1351
1352 IslandResult **islands_res;
1353 size_t islands_res_buff_size = MREMAP_DEFAULT_BUFSIZE;
1354
1355 if (!use_from_vert) {
1356 vcos_src = BKE_mesh_vert_coords_alloc(me_src, NULL);
1357
1358 vcos_interp = MEM_mallocN(sizeof(*vcos_interp) * buff_size_interp, __func__);
1359 indices_interp = MEM_mallocN(sizeof(*indices_interp) * buff_size_interp, __func__);
1360 weights_interp = MEM_mallocN(sizeof(*weights_interp) * buff_size_interp, __func__);
1361 }
1362
1363 {
1364 const bool need_lnors_src = (mode & MREMAP_USE_LOOP) && (mode & MREMAP_USE_NORMAL);
1365 const bool need_lnors_dst = need_lnors_src || (mode & MREMAP_USE_NORPROJ);
1366 const bool need_pnors_src = need_lnors_src ||
1367 ((mode & MREMAP_USE_POLY) && (mode & MREMAP_USE_NORMAL));
1368 const bool need_pnors_dst = need_lnors_dst || need_pnors_src;
1369
1370 if (need_pnors_dst) {
1371 /* Cache poly nors into a temp CDLayer. */
1372 poly_nors_dst = CustomData_get_layer(pdata_dst, CD_NORMAL);
1373 const bool do_poly_nors_dst = (poly_nors_dst == NULL);
1374 if (!poly_nors_dst) {
1375 poly_nors_dst = CustomData_add_layer(
1376 pdata_dst, CD_NORMAL, CD_CALLOC, NULL, numpolys_dst);
1377 CustomData_set_layer_flag(pdata_dst, CD_NORMAL, CD_FLAG_TEMPORARY);
1378 }
1379 if (dirty_nors_dst || do_poly_nors_dst) {
1380 BKE_mesh_calc_normals_poly(verts_dst,
1381 NULL,
1382 numverts_dst,
1383 loops_dst,
1384 polys_dst,
1385 numloops_dst,
1386 numpolys_dst,
1387 poly_nors_dst,
1388 true);
1389 }
1390 }
1391 if (need_lnors_dst) {
1392 short(*custom_nors_dst)[2] = CustomData_get_layer(ldata_dst, CD_CUSTOMLOOPNORMAL);
1393
1394 /* Cache poly nors into a temp CDLayer. */
1395 loop_nors_dst = CustomData_get_layer(ldata_dst, CD_NORMAL);
1396 const bool do_loop_nors_dst = (loop_nors_dst == NULL);
1397 if (!loop_nors_dst) {
1398 loop_nors_dst = CustomData_add_layer(
1399 ldata_dst, CD_NORMAL, CD_CALLOC, NULL, numloops_dst);
1400 CustomData_set_layer_flag(ldata_dst, CD_NORMAL, CD_FLAG_TEMPORARY);
1401 }
1402 if (dirty_nors_dst || do_loop_nors_dst) {
1403 BKE_mesh_normals_loop_split(verts_dst,
1404 numverts_dst,
1405 edges_dst,
1406 numedges_dst,
1407 loops_dst,
1408 loop_nors_dst,
1409 numloops_dst,
1410 polys_dst,
1411 (const float(*)[3])poly_nors_dst,
1412 numpolys_dst,
1413 use_split_nors_dst,
1414 split_angle_dst,
1415 NULL,
1416 custom_nors_dst,
1417 NULL);
1418 }
1419 }
1420 if (need_pnors_src || need_lnors_src) {
1421 if (need_pnors_src) {
1422 poly_nors_src = CustomData_get_layer(&me_src->pdata, CD_NORMAL);
1423 BLI_assert(poly_nors_src != NULL);
1424 }
1425 if (need_lnors_src) {
1426 loop_nors_src = CustomData_get_layer(&me_src->ldata, CD_NORMAL);
1427 BLI_assert(loop_nors_src != NULL);
1428 }
1429 }
1430 }
1431
1432 if (use_from_vert) {
1433 BKE_mesh_vert_loop_map_create(&vert_to_loop_map_src,
1434 &vert_to_loop_map_src_buff,
1435 polys_src,
1436 loops_src,
1437 num_verts_src,
1438 num_polys_src,
1439 num_loops_src);
1440 if (mode & MREMAP_USE_POLY) {
1441 BKE_mesh_vert_poly_map_create(&vert_to_poly_map_src,
1442 &vert_to_poly_map_src_buff,
1443 polys_src,
1444 loops_src,
1445 num_verts_src,
1446 num_polys_src,
1447 num_loops_src);
1448 }
1449 }
1450
1451 /* Needed for islands (or plain mesh) to AStar graph conversion. */
1452 BKE_mesh_edge_poly_map_create(&edge_to_poly_map_src,
1453 &edge_to_poly_map_src_buff,
1454 edges_src,
1455 num_edges_src,
1456 polys_src,
1457 num_polys_src,
1458 loops_src,
1459 num_loops_src);
1460 if (use_from_vert) {
1461 loop_to_poly_map_src = MEM_mallocN(sizeof(*loop_to_poly_map_src) * (size_t)num_loops_src,
1462 __func__);
1463 poly_cents_src = MEM_mallocN(sizeof(*poly_cents_src) * (size_t)num_polys_src, __func__);
1464 for (pidx_src = 0, mp_src = polys_src; pidx_src < num_polys_src; pidx_src++, mp_src++) {
1465 ml_src = &loops_src[mp_src->loopstart];
1466 for (plidx_src = 0, lidx_src = mp_src->loopstart; plidx_src < mp_src->totloop;
1467 plidx_src++, lidx_src++) {
1468 loop_to_poly_map_src[lidx_src] = pidx_src;
1469 }
1470 BKE_mesh_calc_poly_center(mp_src, ml_src, verts_src, poly_cents_src[pidx_src]);
1471 }
1472 }
1473
1474 /* Island makes things slightly more complex here.
1475 * Basically, we:
1476 * * Make one treedata for each island's elements.
1477 * * Check all loops of a same dest poly against all treedata.
1478 * * Choose the island's elements giving the best results.
1479 */
1480
1481 /* First, generate the islands, if possible. */
1482 if (gen_islands_src) {
1483 use_islands = gen_islands_src(verts_src,
1484 num_verts_src,
1485 edges_src,
1486 num_edges_src,
1487 polys_src,
1488 num_polys_src,
1489 loops_src,
1490 num_loops_src,
1491 &island_store);
1492
1493 num_trees = use_islands ? island_store.islands_num : 1;
1494 treedata = MEM_callocN(sizeof(*treedata) * (size_t)num_trees, __func__);
1495 if (isld_steps_src) {
1496 as_graphdata = MEM_callocN(sizeof(*as_graphdata) * (size_t)num_trees, __func__);
1497 }
1498
1499 if (use_islands) {
1500 /* We expect our islands to contain poly indices, with edge indices of 'inner cuts',
1501 * and a mapping loops -> islands indices.
1502 * This implies all loops of a same poly are in the same island. */
1503 BLI_assert((island_store.item_type == MISLAND_TYPE_LOOP) &&
1504 (island_store.island_type == MISLAND_TYPE_POLY) &&
1505 (island_store.innercut_type == MISLAND_TYPE_EDGE));
1506 }
1507 }
1508 else {
1509 num_trees = 1;
1510 treedata = MEM_callocN(sizeof(*treedata), __func__);
1511 if (isld_steps_src) {
1512 as_graphdata = MEM_callocN(sizeof(*as_graphdata), __func__);
1513 }
1514 }
1515
1516 /* Build our AStar graphs. */
1517 if (isld_steps_src) {
1518 for (tindex = 0; tindex < num_trees; tindex++) {
1519 mesh_island_to_astar_graph(use_islands ? &island_store : NULL,
1520 tindex,
1521 verts_src,
1522 edge_to_poly_map_src,
1523 num_edges_src,
1524 loops_src,
1525 polys_src,
1526 num_polys_src,
1527 &as_graphdata[tindex]);
1528 }
1529 }
1530
1531 /* Build our BVHtrees, either from verts or tessfaces. */
1532 if (use_from_vert) {
1533 if (use_islands) {
1534 BLI_bitmap *verts_active = BLI_BITMAP_NEW((size_t)num_verts_src, __func__);
1535
1536 for (tindex = 0; tindex < num_trees; tindex++) {
1537 MeshElemMap *isld = island_store.islands[tindex];
1538 int num_verts_active = 0;
1539 BLI_bitmap_set_all(verts_active, false, (size_t)num_verts_src);
1540 for (i = 0; i < isld->count; i++) {
1541 mp_src = &polys_src[isld->indices[i]];
1542 for (lidx_src = mp_src->loopstart; lidx_src < mp_src->loopstart + mp_src->totloop;
1543 lidx_src++) {
1544 const unsigned int vidx_src = loops_src[lidx_src].v;
1545 if (!BLI_BITMAP_TEST(verts_active, vidx_src)) {
1546 BLI_BITMAP_ENABLE(verts_active, loops_src[lidx_src].v);
1547 num_verts_active++;
1548 }
1549 }
1550 }
1551 bvhtree_from_mesh_verts_ex(&treedata[tindex],
1552 verts_src,
1553 num_verts_src,
1554 false,
1555 verts_active,
1556 num_verts_active,
1557 0.0,
1558 2,
1559 6,
1560 0,
1561 NULL,
1562 NULL);
1563 }
1564
1565 MEM_freeN(verts_active);
1566 }
1567 else {
1568 BLI_assert(num_trees == 1);
1569 BKE_bvhtree_from_mesh_get(&treedata[0], me_src, BVHTREE_FROM_VERTS, 2);
1570 }
1571 }
1572 else { /* We use polygons. */
1573 if (use_islands) {
1574 /* bvhtree here uses looptri faces... */
1575 BLI_bitmap *looptri_active;
1576
1577 looptri_src = BKE_mesh_runtime_looptri_ensure(me_src);
1578 num_looptri_src = me_src->runtime.looptris.len;
1579 looptri_active = BLI_BITMAP_NEW((size_t)num_looptri_src, __func__);
1580
1581 for (tindex = 0; tindex < num_trees; tindex++) {
1582 int num_looptri_active = 0;
1583 BLI_bitmap_set_all(looptri_active, false, (size_t)num_looptri_src);
1584 for (i = 0; i < num_looptri_src; i++) {
1585 mp_src = &polys_src[looptri_src[i].poly];
1586 if (island_store.items_to_islands[mp_src->loopstart] == tindex) {
1587 BLI_BITMAP_ENABLE(looptri_active, i);
1588 num_looptri_active++;
1589 }
1590 }
1591 bvhtree_from_mesh_looptri_ex(&treedata[tindex],
1592 verts_src,
1593 false,
1594 loops_src,
1595 false,
1596 looptri_src,
1597 num_looptri_src,
1598 false,
1599 looptri_active,
1600 num_looptri_active,
1601 0.0,
1602 2,
1603 6,
1604 0,
1605 NULL,
1606 NULL);
1607 }
1608
1609 MEM_freeN(looptri_active);
1610 }
1611 else {
1612 BLI_assert(num_trees == 1);
1613 BKE_bvhtree_from_mesh_get(&treedata[0], me_src, BVHTREE_FROM_LOOPTRI, 2);
1614 }
1615 }
1616
1617 /* And check each dest poly! */
1618 islands_res = MEM_mallocN(sizeof(*islands_res) * (size_t)num_trees, __func__);
1619 for (tindex = 0; tindex < num_trees; tindex++) {
1620 islands_res[tindex] = MEM_mallocN(sizeof(**islands_res) * islands_res_buff_size, __func__);
1621 }
1622
1623 for (pidx_dst = 0, mp_dst = polys_dst; pidx_dst < numpolys_dst; pidx_dst++, mp_dst++) {
1624 float pnor_dst[3];
1625
1626 /* Only in use_from_vert case, we may need polys' centers as fallback
1627 * in case we cannot decide which corner to use from normals only. */
1628 float pcent_dst[3];
1629 bool pcent_dst_valid = false;
1630
1631 if (mode == MREMAP_MODE_LOOP_NEAREST_POLYNOR) {
1632 copy_v3_v3(pnor_dst, poly_nors_dst[pidx_dst]);
1633 if (space_transform) {
1634 BLI_space_transform_apply_normal(space_transform, pnor_dst);
1635 }
1636 }
1637
1638 if ((size_t)mp_dst->totloop > islands_res_buff_size) {
1639 islands_res_buff_size = (size_t)mp_dst->totloop + MREMAP_DEFAULT_BUFSIZE;
1640 for (tindex = 0; tindex < num_trees; tindex++) {
1641 islands_res[tindex] = MEM_reallocN(islands_res[tindex],
1642 sizeof(**islands_res) * islands_res_buff_size);
1643 }
1644 }
1645
1646 for (tindex = 0; tindex < num_trees; tindex++) {
1647 BVHTreeFromMesh *tdata = &treedata[tindex];
1648
1649 ml_dst = &loops_dst[mp_dst->loopstart];
1650 for (plidx_dst = 0; plidx_dst < mp_dst->totloop; plidx_dst++, ml_dst++) {
1651 if (use_from_vert) {
1652 MeshElemMap *vert_to_refelem_map_src = NULL;
1653
1654 copy_v3_v3(tmp_co, verts_dst[ml_dst->v].co);
1655 nearest.index = -1;
1656
1657 /* Convert the vertex to tree coordinates, if needed. */
1658 if (space_transform) {
1659 BLI_space_transform_apply(space_transform, tmp_co);
1660 }
1661
1662 if (mesh_remap_bvhtree_query_nearest(
1663 tdata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
1664 float(*nor_dst)[3];
1665 float(*nors_src)[3];
1666 float best_nor_dot = -2.0f;
1667 float best_sqdist_fallback = FLT_MAX;
1668 int best_index_src = -1;
1669
1670 if (mode == MREMAP_MODE_LOOP_NEAREST_LOOPNOR) {
1671 copy_v3_v3(tmp_no, loop_nors_dst[plidx_dst + mp_dst->loopstart]);
1672 if (space_transform) {
1673 BLI_space_transform_apply_normal(space_transform, tmp_no);
1674 }
1675 nor_dst = &tmp_no;
1676 nors_src = loop_nors_src;
1677 vert_to_refelem_map_src = vert_to_loop_map_src;
1678 }
1679 else { /* if (mode == MREMAP_MODE_LOOP_NEAREST_POLYNOR) { */
1680 nor_dst = &pnor_dst;
1681 nors_src = poly_nors_src;
1682 vert_to_refelem_map_src = vert_to_poly_map_src;
1683 }
1684
1685 for (i = vert_to_refelem_map_src[nearest.index].count; i--;) {
1686 const int index_src = vert_to_refelem_map_src[nearest.index].indices[i];
1687 BLI_assert(index_src != -1);
1688 const float dot = dot_v3v3(nors_src[index_src], *nor_dst);
1689
1690 pidx_src = ((mode == MREMAP_MODE_LOOP_NEAREST_LOOPNOR) ?
1691 loop_to_poly_map_src[index_src] :
1692 index_src);
1693 /* WARNING! This is not the *real* lidx_src in case of POLYNOR, we only use it
1694 * to check we stay on current island (all loops from a given poly are
1695 * on same island!). */
1696 lidx_src = ((mode == MREMAP_MODE_LOOP_NEAREST_LOOPNOR) ?
1697 index_src :
1698 polys_src[pidx_src].loopstart);
1699
1700 /* A same vert may be at the boundary of several islands! Hence, we have to ensure
1701 * poly/loop we are currently considering *belongs* to current island! */
1702 if (use_islands && island_store.items_to_islands[lidx_src] != tindex) {
1703 continue;
1704 }
1705
1706 if (dot > best_nor_dot - 1e-6f) {
1707 /* We need something as fallback decision in case dest normal matches several
1708 * source normals (see T44522), using distance between polys' centers here. */
1709 float *pcent_src;
1710 float sqdist;
1711
1712 mp_src = &polys_src[pidx_src];
1713 ml_src = &loops_src[mp_src->loopstart];
1714
1715 if (!pcent_dst_valid) {
1716 BKE_mesh_calc_poly_center(
1717 mp_dst, &loops_dst[mp_dst->loopstart], verts_dst, pcent_dst);
1718 pcent_dst_valid = true;
1719 }
1720 pcent_src = poly_cents_src[pidx_src];
1721 sqdist = len_squared_v3v3(pcent_dst, pcent_src);
1722
1723 if ((dot > best_nor_dot + 1e-6f) || (sqdist < best_sqdist_fallback)) {
1724 best_nor_dot = dot;
1725 best_sqdist_fallback = sqdist;
1726 best_index_src = index_src;
1727 }
1728 }
1729 }
1730 if (best_index_src == -1) {
1731 /* We found no item to map back from closest vertex... */
1732 best_nor_dot = -1.0f;
1733 hit_dist = FLT_MAX;
1734 }
1735 else if (mode == MREMAP_MODE_LOOP_NEAREST_POLYNOR) {
1736 /* Our best_index_src is a poly one for now!
1737 * Have to find its loop matching our closest vertex. */
1738 mp_src = &polys_src[best_index_src];
1739 ml_src = &loops_src[mp_src->loopstart];
1740 for (plidx_src = 0; plidx_src < mp_src->totloop; plidx_src++, ml_src++) {
1741 if ((int)ml_src->v == nearest.index) {
1742 best_index_src = plidx_src + mp_src->loopstart;
1743 break;
1744 }
1745 }
1746 }
1747 best_nor_dot = (best_nor_dot + 1.0f) * 0.5f;
1748 islands_res[tindex][plidx_dst].factor = hit_dist ? (best_nor_dot / hit_dist) : 1e18f;
1749 islands_res[tindex][plidx_dst].hit_dist = hit_dist;
1750 islands_res[tindex][plidx_dst].index_src = best_index_src;
1751 }
1752 else {
1753 /* No source for this dest loop! */
1754 islands_res[tindex][plidx_dst].factor = 0.0f;
1755 islands_res[tindex][plidx_dst].hit_dist = FLT_MAX;
1756 islands_res[tindex][plidx_dst].index_src = -1;
1757 }
1758 }
1759 else if (mode & MREMAP_USE_NORPROJ) {
1760 int n = (ray_radius > 0.0f) ? MREMAP_RAYCAST_APPROXIMATE_NR : 1;
1761 float w = 1.0f;
1762
1763 copy_v3_v3(tmp_co, verts_dst[ml_dst->v].co);
1764 copy_v3_v3(tmp_no, loop_nors_dst[plidx_dst + mp_dst->loopstart]);
1765
1766 /* We do our transform here, since we may do several raycast/nearest queries. */
1767 if (space_transform) {
1768 BLI_space_transform_apply(space_transform, tmp_co);
1769 BLI_space_transform_apply_normal(space_transform, tmp_no);
1770 }
1771
1772 while (n--) {
1773 if (mesh_remap_bvhtree_query_raycast(
1774 tdata, &rayhit, tmp_co, tmp_no, ray_radius / w, max_dist, &hit_dist)) {
1775 islands_res[tindex][plidx_dst].factor = (hit_dist ? (1.0f / hit_dist) : 1e18f) * w;
1776 islands_res[tindex][plidx_dst].hit_dist = hit_dist;
1777 islands_res[tindex][plidx_dst].index_src = (int)tdata->looptri[rayhit.index].poly;
1778 copy_v3_v3(islands_res[tindex][plidx_dst].hit_point, rayhit.co);
1779 break;
1780 }
1781 /* Next iteration will get bigger radius but smaller weight! */
1782 w /= MREMAP_RAYCAST_APPROXIMATE_FAC;
1783 }
1784 if (n == -1) {
1785 /* Fallback to 'nearest' hit here, loops usually comes in 'face group', not good to
1786 * have only part of one dest face's loops to map to source.
1787 * Note that since we give this a null weight, if whole weight for a given face
1788 * is null, it means none of its loop mapped to this source island,
1789 * hence we can skip it later.
1790 */
1791 copy_v3_v3(tmp_co, verts_dst[ml_dst->v].co);
1792 nearest.index = -1;
1793
1794 /* Convert the vertex to tree coordinates, if needed. */
1795 if (space_transform) {
1796 BLI_space_transform_apply(space_transform, tmp_co);
1797 }
1798
1799 /* In any case, this fallback nearest hit should have no weight at all
1800 * in 'best island' decision! */
1801 islands_res[tindex][plidx_dst].factor = 0.0f;
1802
1803 if (mesh_remap_bvhtree_query_nearest(
1804 tdata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
1805 islands_res[tindex][plidx_dst].hit_dist = hit_dist;
1806 islands_res[tindex][plidx_dst].index_src = (int)tdata->looptri[nearest.index].poly;
1807 copy_v3_v3(islands_res[tindex][plidx_dst].hit_point, nearest.co);
1808 }
1809 else {
1810 /* No source for this dest loop! */
1811 islands_res[tindex][plidx_dst].hit_dist = FLT_MAX;
1812 islands_res[tindex][plidx_dst].index_src = -1;
1813 }
1814 }
1815 }
1816 else { /* Nearest poly either to use all its loops/verts or just closest one. */
1817 copy_v3_v3(tmp_co, verts_dst[ml_dst->v].co);
1818 nearest.index = -1;
1819
1820 /* Convert the vertex to tree coordinates, if needed. */
1821 if (space_transform) {
1822 BLI_space_transform_apply(space_transform, tmp_co);
1823 }
1824
1825 if (mesh_remap_bvhtree_query_nearest(
1826 tdata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
1827 islands_res[tindex][plidx_dst].factor = hit_dist ? (1.0f / hit_dist) : 1e18f;
1828 islands_res[tindex][plidx_dst].hit_dist = hit_dist;
1829 islands_res[tindex][plidx_dst].index_src = (int)tdata->looptri[nearest.index].poly;
1830 copy_v3_v3(islands_res[tindex][plidx_dst].hit_point, nearest.co);
1831 }
1832 else {
1833 /* No source for this dest loop! */
1834 islands_res[tindex][plidx_dst].factor = 0.0f;
1835 islands_res[tindex][plidx_dst].hit_dist = FLT_MAX;
1836 islands_res[tindex][plidx_dst].index_src = -1;
1837 }
1838 }
1839 }
1840 }
1841
1842 /* And now, find best island to use! */
1843 /* We have to first select the 'best source island' for given dst poly and its loops.
1844 * Then, we have to check that poly does not 'spread' across some island's limits
1845 * (like inner seams for UVs, etc.).
1846 * Note we only still partially support that kind of situation here, i.e.
1847 * Polys spreading over actual cracks
1848 * (like a narrow space without faces on src, splitting a 'tube-like' geometry).
1849 * That kind of situation should be relatively rare, though.
1850 */
1851 /* XXX This block in itself is big and complex enough to be a separate function but...
1852 * it uses a bunch of locale vars.
1853 * Not worth sending all that through parameters (for now at least). */
1854 {
1855 BLI_AStarGraph *as_graph = NULL;
1856 int *poly_island_index_map = NULL;
1857 int pidx_src_prev = -1;
1858
1859 MeshElemMap *best_island = NULL;
1860 float best_island_fac = 0.0f;
1861 int best_island_index = -1;
1862
1863 for (tindex = 0; tindex < num_trees; tindex++) {
1864 float island_fac = 0.0f;
1865
1866 for (plidx_dst = 0; plidx_dst < mp_dst->totloop; plidx_dst++) {
1867 island_fac += islands_res[tindex][plidx_dst].factor;
1868 }
1869 island_fac /= (float)mp_dst->totloop;
1870
1871 if (island_fac > best_island_fac) {
1872 best_island_fac = island_fac;
1873 best_island_index = tindex;
1874 }
1875 }
1876
1877 if (best_island_index != -1 && isld_steps_src) {
1878 best_island = use_islands ? island_store.islands[best_island_index] : NULL;
1879 as_graph = &as_graphdata[best_island_index];
1880 poly_island_index_map = (int *)as_graph->custom_data;
1881 BLI_astar_solution_init(as_graph, &as_solution, NULL);
1882 }
1883
1884 for (plidx_dst = 0; plidx_dst < mp_dst->totloop; plidx_dst++) {
1885 IslandResult *isld_res;
1886 lidx_dst = plidx_dst + mp_dst->loopstart;
1887
1888 if (best_island_index == -1) {
1889 /* No source for any loops of our dest poly in any source islands. */
1890 BKE_mesh_remap_item_define_invalid(r_map, lidx_dst);
1891 continue;
1892 }
1893
1894 as_solution.custom_data = POINTER_FROM_INT(false);
1895
1896 isld_res = &islands_res[best_island_index][plidx_dst];
1897 if (use_from_vert) {
1898 /* Indices stored in islands_res are those of loops, one per dest loop. */
1899 lidx_src = isld_res->index_src;
1900 if (lidx_src >= 0) {
1901 pidx_src = loop_to_poly_map_src[lidx_src];
1902 /* If prev and curr poly are the same, no need to do anything more!!! */
1903 if (!ELEM(pidx_src_prev, -1, pidx_src) && isld_steps_src) {
1904 int pidx_isld_src, pidx_isld_src_prev;
1905 if (poly_island_index_map) {
1906 pidx_isld_src = poly_island_index_map[pidx_src];
1907 pidx_isld_src_prev = poly_island_index_map[pidx_src_prev];
1908 }
1909 else {
1910 pidx_isld_src = pidx_src;
1911 pidx_isld_src_prev = pidx_src_prev;
1912 }
1913
1914 BLI_astar_graph_solve(as_graph,
1915 pidx_isld_src_prev,
1916 pidx_isld_src,
1917 mesh_remap_calc_loops_astar_f_cost,
1918 &as_solution,
1919 isld_steps_src);
1920 if (POINTER_AS_INT(as_solution.custom_data) && (as_solution.steps > 0)) {
1921 /* Find first 'cutting edge' on path, and bring back lidx_src on poly just
1922 * before that edge.
1923 * Note we could try to be much smarter, g.g. Storing a whole poly's indices,
1924 * and making decision (on which side of cutting edge(s!) to be) on the end,
1925 * but this is one more level of complexity, better to first see if
1926 * simple solution works!
1927 */
1928 int last_valid_pidx_isld_src = -1;
1929 /* Note we go backward here, from dest to src poly. */
1930 for (i = as_solution.steps - 1; i--;) {
1931 BLI_AStarGNLink *as_link = as_solution.prev_links[pidx_isld_src];
1932 const int eidx = POINTER_AS_INT(as_link->custom_data);
1933 pidx_isld_src = as_solution.prev_nodes[pidx_isld_src];
1934 BLI_assert(pidx_isld_src != -1);
1935 if (eidx != -1) {
1936 /* we are 'crossing' a cutting edge. */
1937 last_valid_pidx_isld_src = pidx_isld_src;
1938 }
1939 }
1940 if (last_valid_pidx_isld_src != -1) {
1941 /* Find a new valid loop in that new poly (nearest one for now).
1942 * Note we could be much more subtle here, again that's for later... */
1943 int j;
1944 float best_dist_sq = FLT_MAX;
1945
1946 ml_dst = &loops_dst[lidx_dst];
1947 copy_v3_v3(tmp_co, verts_dst[ml_dst->v].co);
1948
1949 /* We do our transform here,
1950 * since we may do several raycast/nearest queries. */
1951 if (space_transform) {
1952 BLI_space_transform_apply(space_transform, tmp_co);
1953 }
1954
1955 pidx_src = (use_islands ? best_island->indices[last_valid_pidx_isld_src] :
1956 last_valid_pidx_isld_src);
1957 mp_src = &polys_src[pidx_src];
1958 ml_src = &loops_src[mp_src->loopstart];
1959 for (j = 0; j < mp_src->totloop; j++, ml_src++) {
1960 const float dist_sq = len_squared_v3v3(verts_src[ml_src->v].co, tmp_co);
1961 if (dist_sq < best_dist_sq) {
1962 best_dist_sq = dist_sq;
1963 lidx_src = mp_src->loopstart + j;
1964 }
1965 }
1966 }
1967 }
1968 }
1969 mesh_remap_item_define(r_map,
1970 lidx_dst,
1971 isld_res->hit_dist,
1972 best_island_index,
1973 1,
1974 &lidx_src,
1975 &full_weight);
1976 pidx_src_prev = pidx_src;
1977 }
1978 else {
1979 /* No source for this loop in this island. */
1980 /* TODO: would probably be better to get a source
1981 * at all cost in best island anyway? */
1982 mesh_remap_item_define(r_map, lidx_dst, FLT_MAX, best_island_index, 0, NULL, NULL);
1983 }
1984 }
1985 else {
1986 /* Else, we use source poly, indices stored in islands_res are those of polygons. */
1987 pidx_src = isld_res->index_src;
1988 if (pidx_src >= 0) {
1989 float *hit_co = isld_res->hit_point;
1990 int best_loop_index_src;
1991
1992 mp_src = &polys_src[pidx_src];
1993 /* If prev and curr poly are the same, no need to do anything more!!! */
1994 if (!ELEM(pidx_src_prev, -1, pidx_src) && isld_steps_src) {
1995 int pidx_isld_src, pidx_isld_src_prev;
1996 if (poly_island_index_map) {
1997 pidx_isld_src = poly_island_index_map[pidx_src];
1998 pidx_isld_src_prev = poly_island_index_map[pidx_src_prev];
1999 }
2000 else {
2001 pidx_isld_src = pidx_src;
2002 pidx_isld_src_prev = pidx_src_prev;
2003 }
2004
2005 BLI_astar_graph_solve(as_graph,
2006 pidx_isld_src_prev,
2007 pidx_isld_src,
2008 mesh_remap_calc_loops_astar_f_cost,
2009 &as_solution,
2010 isld_steps_src);
2011 if (POINTER_AS_INT(as_solution.custom_data) && (as_solution.steps > 0)) {
2012 /* Find first 'cutting edge' on path, and bring back lidx_src on poly just
2013 * before that edge.
2014 * Note we could try to be much smarter: e.g. Storing a whole poly's indices,
2015 * and making decision (one which side of cutting edge(s)!) to be on the end,
2016 * but this is one more level of complexity, better to first see if
2017 * simple solution works!
2018 */
2019 int last_valid_pidx_isld_src = -1;
2020 /* Note we go backward here, from dest to src poly. */
2021 for (i = as_solution.steps - 1; i--;) {
2022 BLI_AStarGNLink *as_link = as_solution.prev_links[pidx_isld_src];
2023 int eidx = POINTER_AS_INT(as_link->custom_data);
2024
2025 pidx_isld_src = as_solution.prev_nodes[pidx_isld_src];
2026 BLI_assert(pidx_isld_src != -1);
2027 if (eidx != -1) {
2028 /* we are 'crossing' a cutting edge. */
2029 last_valid_pidx_isld_src = pidx_isld_src;
2030 }
2031 }
2032 if (last_valid_pidx_isld_src != -1) {
2033 /* Find a new valid loop in that new poly (nearest point on poly for now).
2034 * Note we could be much more subtle here, again that's for later... */
2035 float best_dist_sq = FLT_MAX;
2036 int j;
2037
2038 ml_dst = &loops_dst[lidx_dst];
2039 copy_v3_v3(tmp_co, verts_dst[ml_dst->v].co);
2040
2041 /* We do our transform here,
2042 * since we may do several raycast/nearest queries. */
2043 if (space_transform) {
2044 BLI_space_transform_apply(space_transform, tmp_co);
2045 }
2046
2047 pidx_src = (use_islands ? best_island->indices[last_valid_pidx_isld_src] :
2048 last_valid_pidx_isld_src);
2049 mp_src = &polys_src[pidx_src];
2050
2051 /* Create that one on demand. */
2052 if (poly_to_looptri_map_src == NULL) {
2053 BKE_mesh_origindex_map_create_looptri(&poly_to_looptri_map_src,
2054 &poly_to_looptri_map_src_buff,
2055 polys_src,
2056 num_polys_src,
2057 looptri_src,
2058 num_looptri_src);
2059 }
2060
2061 for (j = poly_to_looptri_map_src[pidx_src].count; j--;) {
2062 float h[3];
2063 const MLoopTri *lt =
2064 &looptri_src[poly_to_looptri_map_src[pidx_src].indices[j]];
2065 float dist_sq;
2066
2067 closest_on_tri_to_point_v3(h,
2068 tmp_co,
2069 vcos_src[loops_src[lt->tri[0]].v],
2070 vcos_src[loops_src[lt->tri[1]].v],
2071 vcos_src[loops_src[lt->tri[2]].v]);
2072 dist_sq = len_squared_v3v3(tmp_co, h);
2073 if (dist_sq < best_dist_sq) {
2074 copy_v3_v3(hit_co, h);
2075 best_dist_sq = dist_sq;
2076 }
2077 }
2078 }
2079 }
2080 }
2081
2082 if (mode == MREMAP_MODE_LOOP_POLY_NEAREST) {
2083 mesh_remap_interp_poly_data_get(mp_src,
2084 loops_src,
2085 (const float(*)[3])vcos_src,
2086 hit_co,
2087 &buff_size_interp,
2088 &vcos_interp,
2089 true,
2090 &indices_interp,
2091 &weights_interp,
2092 false,
2093 &best_loop_index_src);
2094
2095 mesh_remap_item_define(r_map,
2096 lidx_dst,
2097 isld_res->hit_dist,
2098 best_island_index,
2099 1,
2100 &best_loop_index_src,
2101 &full_weight);
2102 }
2103 else {
2104 const int sources_num = mesh_remap_interp_poly_data_get(
2105 mp_src,
2106 loops_src,
2107 (const float(*)[3])vcos_src,
2108 hit_co,
2109 &buff_size_interp,
2110 &vcos_interp,
2111 true,
2112 &indices_interp,
2113 &weights_interp,
2114 true,
2115 NULL);
2116
2117 mesh_remap_item_define(r_map,
2118 lidx_dst,
2119 isld_res->hit_dist,
2120 best_island_index,
2121 sources_num,
2122 indices_interp,
2123 weights_interp);
2124 }
2125
2126 pidx_src_prev = pidx_src;
2127 }
2128 else {
2129 /* No source for this loop in this island. */
2130 /* TODO: would probably be better to get a source
2131 * at all cost in best island anyway? */
2132 mesh_remap_item_define(r_map, lidx_dst, FLT_MAX, best_island_index, 0, NULL, NULL);
2133 }
2134 }
2135 }
2136
2137 BLI_astar_solution_clear(&as_solution);
2138 }
2139 }
2140
2141 for (tindex = 0; tindex < num_trees; tindex++) {
2142 MEM_freeN(islands_res[tindex]);
2143 free_bvhtree_from_mesh(&treedata[tindex]);
2144 if (isld_steps_src) {
2145 BLI_astar_graph_free(&as_graphdata[tindex]);
2146 }
2147 }
2148 MEM_freeN(islands_res);
2149 BKE_mesh_loop_islands_free(&island_store);
2150 MEM_freeN(treedata);
2151 if (isld_steps_src) {
2152 MEM_freeN(as_graphdata);
2153 BLI_astar_solution_free(&as_solution);
2154 }
2155
2156 if (vcos_src) {
2157 MEM_freeN(vcos_src);
2158 }
2159 if (vert_to_loop_map_src) {
2160 MEM_freeN(vert_to_loop_map_src);
2161 }
2162 if (vert_to_loop_map_src_buff) {
2163 MEM_freeN(vert_to_loop_map_src_buff);
2164 }
2165 if (vert_to_poly_map_src) {
2166 MEM_freeN(vert_to_poly_map_src);
2167 }
2168 if (vert_to_poly_map_src_buff) {
2169 MEM_freeN(vert_to_poly_map_src_buff);
2170 }
2171 if (edge_to_poly_map_src) {
2172 MEM_freeN(edge_to_poly_map_src);
2173 }
2174 if (edge_to_poly_map_src_buff) {
2175 MEM_freeN(edge_to_poly_map_src_buff);
2176 }
2177 if (poly_to_looptri_map_src) {
2178 MEM_freeN(poly_to_looptri_map_src);
2179 }
2180 if (poly_to_looptri_map_src_buff) {
2181 MEM_freeN(poly_to_looptri_map_src_buff);
2182 }
2183 if (loop_to_poly_map_src) {
2184 MEM_freeN(loop_to_poly_map_src);
2185 }
2186 if (poly_cents_src) {
2187 MEM_freeN(poly_cents_src);
2188 }
2189 if (vcos_interp) {
2190 MEM_freeN(vcos_interp);
2191 }
2192 if (indices_interp) {
2193 MEM_freeN(indices_interp);
2194 }
2195 if (weights_interp) {
2196 MEM_freeN(weights_interp);
2197 }
2198 }
2199 }
2200
BKE_mesh_remap_calc_polys_from_mesh(const int mode,const SpaceTransform * space_transform,const float max_dist,const float ray_radius,MVert * verts_dst,const int numverts_dst,MLoop * loops_dst,const int numloops_dst,MPoly * polys_dst,const int numpolys_dst,CustomData * pdata_dst,const bool dirty_nors_dst,Mesh * me_src,MeshPairRemap * r_map)2201 void BKE_mesh_remap_calc_polys_from_mesh(const int mode,
2202 const SpaceTransform *space_transform,
2203 const float max_dist,
2204 const float ray_radius,
2205 MVert *verts_dst,
2206 const int numverts_dst,
2207 MLoop *loops_dst,
2208 const int numloops_dst,
2209 MPoly *polys_dst,
2210 const int numpolys_dst,
2211 CustomData *pdata_dst,
2212 const bool dirty_nors_dst,
2213 Mesh *me_src,
2214 MeshPairRemap *r_map)
2215 {
2216 const float full_weight = 1.0f;
2217 const float max_dist_sq = max_dist * max_dist;
2218 float(*poly_nors_dst)[3] = NULL;
2219 float tmp_co[3], tmp_no[3];
2220 int i;
2221
2222 BLI_assert(mode & MREMAP_MODE_POLY);
2223
2224 if (mode & (MREMAP_USE_NORMAL | MREMAP_USE_NORPROJ)) {
2225 /* Cache poly nors into a temp CDLayer. */
2226 poly_nors_dst = CustomData_get_layer(pdata_dst, CD_NORMAL);
2227 if (!poly_nors_dst) {
2228 poly_nors_dst = CustomData_add_layer(pdata_dst, CD_NORMAL, CD_CALLOC, NULL, numpolys_dst);
2229 CustomData_set_layer_flag(pdata_dst, CD_NORMAL, CD_FLAG_TEMPORARY);
2230 }
2231 if (dirty_nors_dst) {
2232 BKE_mesh_calc_normals_poly(verts_dst,
2233 NULL,
2234 numverts_dst,
2235 loops_dst,
2236 polys_dst,
2237 numloops_dst,
2238 numpolys_dst,
2239 poly_nors_dst,
2240 true);
2241 }
2242 }
2243
2244 BKE_mesh_remap_init(r_map, numpolys_dst);
2245
2246 if (mode == MREMAP_MODE_TOPOLOGY) {
2247 BLI_assert(numpolys_dst == me_src->totpoly);
2248 for (i = 0; i < numpolys_dst; i++) {
2249 mesh_remap_item_define(r_map, i, FLT_MAX, 0, 1, &i, &full_weight);
2250 }
2251 }
2252 else {
2253 BVHTreeFromMesh treedata = {NULL};
2254 BVHTreeNearest nearest = {0};
2255 BVHTreeRayHit rayhit = {0};
2256 float hit_dist;
2257
2258 BKE_bvhtree_from_mesh_get(&treedata, me_src, BVHTREE_FROM_LOOPTRI, 2);
2259
2260 if (mode == MREMAP_MODE_POLY_NEAREST) {
2261 nearest.index = -1;
2262
2263 for (i = 0; i < numpolys_dst; i++) {
2264 MPoly *mp = &polys_dst[i];
2265
2266 BKE_mesh_calc_poly_center(mp, &loops_dst[mp->loopstart], verts_dst, tmp_co);
2267
2268 /* Convert the vertex to tree coordinates, if needed. */
2269 if (space_transform) {
2270 BLI_space_transform_apply(space_transform, tmp_co);
2271 }
2272
2273 if (mesh_remap_bvhtree_query_nearest(
2274 &treedata, &nearest, tmp_co, max_dist_sq, &hit_dist)) {
2275 const MLoopTri *lt = &treedata.looptri[nearest.index];
2276 const int poly_index = (int)lt->poly;
2277 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &poly_index, &full_weight);
2278 }
2279 else {
2280 /* No source for this dest poly! */
2281 BKE_mesh_remap_item_define_invalid(r_map, i);
2282 }
2283 }
2284 }
2285 else if (mode == MREMAP_MODE_POLY_NOR) {
2286 BLI_assert(poly_nors_dst);
2287
2288 for (i = 0; i < numpolys_dst; i++) {
2289 MPoly *mp = &polys_dst[i];
2290
2291 BKE_mesh_calc_poly_center(mp, &loops_dst[mp->loopstart], verts_dst, tmp_co);
2292 copy_v3_v3(tmp_no, poly_nors_dst[i]);
2293
2294 /* Convert the vertex to tree coordinates, if needed. */
2295 if (space_transform) {
2296 BLI_space_transform_apply(space_transform, tmp_co);
2297 BLI_space_transform_apply_normal(space_transform, tmp_no);
2298 }
2299
2300 if (mesh_remap_bvhtree_query_raycast(
2301 &treedata, &rayhit, tmp_co, tmp_no, ray_radius, max_dist, &hit_dist)) {
2302 const MLoopTri *lt = &treedata.looptri[rayhit.index];
2303 const int poly_index = (int)lt->poly;
2304
2305 mesh_remap_item_define(r_map, i, hit_dist, 0, 1, &poly_index, &full_weight);
2306 }
2307 else {
2308 /* No source for this dest poly! */
2309 BKE_mesh_remap_item_define_invalid(r_map, i);
2310 }
2311 }
2312 }
2313 else if (mode == MREMAP_MODE_POLY_POLYINTERP_PNORPROJ) {
2314 /* We cast our rays randomly, with a pseudo-even distribution
2315 * (since we spread across tessellated tris,
2316 * with additional weighting based on each tri's relative area).
2317 */
2318 RNG *rng = BLI_rng_new(0);
2319
2320 const size_t numpolys_src = (size_t)me_src->totpoly;
2321
2322 /* Here it's simpler to just allocate for all polys :/ */
2323 int *indices = MEM_mallocN(sizeof(*indices) * numpolys_src, __func__);
2324 float *weights = MEM_mallocN(sizeof(*weights) * numpolys_src, __func__);
2325
2326 size_t tmp_poly_size = MREMAP_DEFAULT_BUFSIZE;
2327 float(*poly_vcos_2d)[2] = MEM_mallocN(sizeof(*poly_vcos_2d) * tmp_poly_size, __func__);
2328 /* Tessellated 2D poly, always (num_loops - 2) triangles. */
2329 int(*tri_vidx_2d)[3] = MEM_mallocN(sizeof(*tri_vidx_2d) * (tmp_poly_size - 2), __func__);
2330
2331 for (i = 0; i < numpolys_dst; i++) {
2332 /* For each dst poly, we sample some rays from it (2D grid in pnor space)
2333 * and use their hits to interpolate from source polys. */
2334 /* Note: dst poly is early-converted into src space! */
2335 MPoly *mp = &polys_dst[i];
2336
2337 int tot_rays, done_rays = 0;
2338 float poly_area_2d_inv, done_area = 0.0f;
2339
2340 float pcent_dst[3];
2341 float to_pnor_2d_mat[3][3], from_pnor_2d_mat[3][3];
2342 float poly_dst_2d_min[2], poly_dst_2d_max[2], poly_dst_2d_z;
2343 float poly_dst_2d_size[2];
2344
2345 float totweights = 0.0f;
2346 float hit_dist_accum = 0.0f;
2347 int sources_num = 0;
2348 const int tris_num = mp->totloop - 2;
2349 int j;
2350
2351 BKE_mesh_calc_poly_center(mp, &loops_dst[mp->loopstart], verts_dst, pcent_dst);
2352 copy_v3_v3(tmp_no, poly_nors_dst[i]);
2353
2354 /* We do our transform here, else it'd be redone by raycast helper for each ray, ugh! */
2355 if (space_transform) {
2356 BLI_space_transform_apply(space_transform, pcent_dst);
2357 BLI_space_transform_apply_normal(space_transform, tmp_no);
2358 }
2359
2360 copy_vn_fl(weights, (int)numpolys_src, 0.0f);
2361
2362 if (UNLIKELY((size_t)mp->totloop > tmp_poly_size)) {
2363 tmp_poly_size = (size_t)mp->totloop;
2364 poly_vcos_2d = MEM_reallocN(poly_vcos_2d, sizeof(*poly_vcos_2d) * tmp_poly_size);
2365 tri_vidx_2d = MEM_reallocN(tri_vidx_2d, sizeof(*tri_vidx_2d) * (tmp_poly_size - 2));
2366 }
2367
2368 axis_dominant_v3_to_m3(to_pnor_2d_mat, tmp_no);
2369 invert_m3_m3(from_pnor_2d_mat, to_pnor_2d_mat);
2370
2371 mul_m3_v3(to_pnor_2d_mat, pcent_dst);
2372 poly_dst_2d_z = pcent_dst[2];
2373
2374 /* Get (2D) bounding square of our poly. */
2375 INIT_MINMAX2(poly_dst_2d_min, poly_dst_2d_max);
2376
2377 for (j = 0; j < mp->totloop; j++) {
2378 MLoop *ml = &loops_dst[j + mp->loopstart];
2379 copy_v3_v3(tmp_co, verts_dst[ml->v].co);
2380 if (space_transform) {
2381 BLI_space_transform_apply(space_transform, tmp_co);
2382 }
2383 mul_v2_m3v3(poly_vcos_2d[j], to_pnor_2d_mat, tmp_co);
2384 minmax_v2v2_v2(poly_dst_2d_min, poly_dst_2d_max, poly_vcos_2d[j]);
2385 }
2386
2387 /* We adjust our ray-casting grid to ray_radius (the smaller, the more rays are cast),
2388 * with lower/upper bounds. */
2389 sub_v2_v2v2(poly_dst_2d_size, poly_dst_2d_max, poly_dst_2d_min);
2390
2391 if (ray_radius) {
2392 tot_rays = (int)((max_ff(poly_dst_2d_size[0], poly_dst_2d_size[1]) / ray_radius) + 0.5f);
2393 CLAMP(tot_rays, MREMAP_RAYCAST_TRI_SAMPLES_MIN, MREMAP_RAYCAST_TRI_SAMPLES_MAX);
2394 }
2395 else {
2396 /* If no radius (pure rays), give max number of rays! */
2397 tot_rays = MREMAP_RAYCAST_TRI_SAMPLES_MIN;
2398 }
2399 tot_rays *= tot_rays;
2400
2401 poly_area_2d_inv = area_poly_v2((const float(*)[2])poly_vcos_2d,
2402 (unsigned int)mp->totloop);
2403 /* In case we have a null-area degenerated poly... */
2404 poly_area_2d_inv = 1.0f / max_ff(poly_area_2d_inv, 1e-9f);
2405
2406 /* Tessellate our poly. */
2407 if (mp->totloop == 3) {
2408 tri_vidx_2d[0][0] = 0;
2409 tri_vidx_2d[0][1] = 1;
2410 tri_vidx_2d[0][2] = 2;
2411 }
2412 if (mp->totloop == 4) {
2413 tri_vidx_2d[0][0] = 0;
2414 tri_vidx_2d[0][1] = 1;
2415 tri_vidx_2d[0][2] = 2;
2416 tri_vidx_2d[1][0] = 0;
2417 tri_vidx_2d[1][1] = 2;
2418 tri_vidx_2d[1][2] = 3;
2419 }
2420 else {
2421 BLI_polyfill_calc(
2422 poly_vcos_2d, (unsigned int)mp->totloop, -1, (unsigned int(*)[3])tri_vidx_2d);
2423 }
2424
2425 for (j = 0; j < tris_num; j++) {
2426 float *v1 = poly_vcos_2d[tri_vidx_2d[j][0]];
2427 float *v2 = poly_vcos_2d[tri_vidx_2d[j][1]];
2428 float *v3 = poly_vcos_2d[tri_vidx_2d[j][2]];
2429 int rays_num;
2430
2431 /* All this allows us to get 'absolute' number of rays for each tri,
2432 * avoiding accumulating errors over iterations, and helping better even distribution. */
2433 done_area += area_tri_v2(v1, v2, v3);
2434 rays_num = max_ii(
2435 (int)((float)tot_rays * done_area * poly_area_2d_inv + 0.5f) - done_rays, 0);
2436 done_rays += rays_num;
2437
2438 while (rays_num--) {
2439 int n = (ray_radius > 0.0f) ? MREMAP_RAYCAST_APPROXIMATE_NR : 1;
2440 float w = 1.0f;
2441
2442 BLI_rng_get_tri_sample_float_v2(rng, v1, v2, v3, tmp_co);
2443
2444 tmp_co[2] = poly_dst_2d_z;
2445 mul_m3_v3(from_pnor_2d_mat, tmp_co);
2446
2447 /* At this point, tmp_co is a point on our poly surface, in mesh_src space! */
2448 while (n--) {
2449 if (mesh_remap_bvhtree_query_raycast(
2450 &treedata, &rayhit, tmp_co, tmp_no, ray_radius / w, max_dist, &hit_dist)) {
2451 const MLoopTri *lt = &treedata.looptri[rayhit.index];
2452
2453 weights[lt->poly] += w;
2454 totweights += w;
2455 hit_dist_accum += hit_dist;
2456 break;
2457 }
2458 /* Next iteration will get bigger radius but smaller weight! */
2459 w /= MREMAP_RAYCAST_APPROXIMATE_FAC;
2460 }
2461 }
2462 }
2463
2464 if (totweights > 0.0f) {
2465 for (j = 0; j < (int)numpolys_src; j++) {
2466 if (!weights[j]) {
2467 continue;
2468 }
2469 /* Note: sources_num is always <= j! */
2470 weights[sources_num] = weights[j] / totweights;
2471 indices[sources_num] = j;
2472 sources_num++;
2473 }
2474 mesh_remap_item_define(
2475 r_map, i, hit_dist_accum / totweights, 0, sources_num, indices, weights);
2476 }
2477 else {
2478 /* No source for this dest poly! */
2479 BKE_mesh_remap_item_define_invalid(r_map, i);
2480 }
2481 }
2482
2483 MEM_freeN(tri_vidx_2d);
2484 MEM_freeN(poly_vcos_2d);
2485 MEM_freeN(indices);
2486 MEM_freeN(weights);
2487 BLI_rng_free(rng);
2488 }
2489 else {
2490 CLOG_WARN(&LOG, "Unsupported mesh-to-mesh poly mapping mode (%d)!", mode);
2491 memset(r_map->items, 0, sizeof(*r_map->items) * (size_t)numpolys_dst);
2492 }
2493
2494 free_bvhtree_from_mesh(&treedata);
2495 }
2496 }
2497
2498 #undef MREMAP_RAYCAST_APPROXIMATE_NR
2499 #undef MREMAP_RAYCAST_APPROXIMATE_FAC
2500 #undef MREMAP_RAYCAST_TRI_SAMPLES_MIN
2501 #undef MREMAP_RAYCAST_TRI_SAMPLES_MAX
2502 #undef MREMAP_DEFAULT_BUFSIZE
2503
2504 /** \} */
2505