Blender V5.3
shrinkwrap.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10#include <cfloat>
11#include <cmath>
12#include <cstdio>
13#include <cstring>
14#include <ctime>
15#include <memory.h>
16
18#include "DNA_mesh_types.h"
19#include "DNA_modifier_types.h"
20#include "DNA_object_types.h"
21
22#include "BLI_math_geom_c.hh"
23#include "BLI_math_matrix_c.hh"
24#include "BLI_math_solvers.hh"
25#include "BLI_math_vector.hh"
26#include "BLI_math_vector_c.hh"
27#include "BLI_utildefines.hh"
28
29#include "BKE_attribute.hh"
30#include "BKE_modifier.hh"
31#include "BKE_shrinkwrap.hh"
32#include "BKE_subdiv.hh"
33
34#include "BKE_deform.hh"
35#include "BKE_editmesh.hh"
36#include "BKE_mesh.hh" /* for OMP limits. */
37#include "BKE_mesh_wrapper.hh"
38#include "BKE_subdiv_deform.hh"
39
41
42#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
43
44namespace blender {
45
46/* for timing... */
47#if 0
49#else
50# define TIMEIT_BENCH(expr, id) (expr)
51#endif
52
53/* Util macros */
54#define OUT_OF_MEMORY() ((void)printf("Shrinkwrap: Out of memory\n"))
55
57 ShrinkwrapModifierData *smd; /* shrinkwrap modifier data */
58
59 Object *ob; /* object we are applying shrinkwrap to */
60
61 float (*vert_positions)[3]; /* Array of verts being projected. */
63 /* Vertices being shrink-wrapped. */
66
67 const MDeformVert *dvert; /* Pointer to mdeform array */
68 int vgroup; /* Vertex group num */
69 bool invert_vgroup; /* invert vertex group influence */
70
71 Mesh *target; /* mesh we are shrinking to */
72 SpaceTransform local2target; /* transform to move between local and target space */
73 ShrinkwrapTreeData *tree; /* mesh BVH tree data */
74
76
77 float keepDist; /* Distance to keep above target surface (units are in local space) */
78};
79
80bool BKE_shrinkwrap_needs_normals(int shrinkType, int shrinkMode)
81{
82 return (shrinkType == MOD_SHRINKWRAP_TARGET_PROJECT) ||
83 (shrinkType != MOD_SHRINKWRAP_NEAREST_VERTEX &&
84 shrinkMode == MOD_SHRINKWRAP_ABOVE_SURFACE);
85}
86
88 ShrinkwrapTreeData *data, Mesh *mesh, int shrinkType, int shrinkMode, bool force_normals)
89{
90 using namespace blender::bke;
91 *data = {};
92
93 if (mesh == nullptr) {
94 return false;
95 }
96
97 /* We could create a BVH tree from the edit mesh,
98 * however accessing normals from the face/loop normals gets more involved.
99 * Convert mesh data since this isn't typically used in edit-mode. */
101
102 if (mesh->verts_num <= 0) {
103 return false;
104 }
105
106 data->mesh = mesh;
107 data->edges = mesh->edges();
108 data->faces = mesh->faces();
109 data->corner_edges = mesh->corner_edges();
110 data->vert_normals = mesh->vert_normals();
111 const AttributeAccessor attributes = mesh->attributes();
112 data->sharp_faces = *attributes.lookup<bool>("sharp_face", AttrDomain::Face);
113
114 if (shrinkType == MOD_SHRINKWRAP_NEAREST_VERTEX) {
115 data->vert_tree = &mesh->bvh_verts();
116 return true;
117 }
118
119 if (mesh->faces_num <= 0) {
120 return false;
121 }
122
123 data->treeData = mesh->bvh_corner_tris();
124 data->bvh = data->treeData.tree;
125
126 if (data->bvh == nullptr) {
127 return false;
128 }
129
130 if (force_normals || BKE_shrinkwrap_needs_normals(shrinkType, shrinkMode)) {
131 data->face_normals = mesh->face_normals();
132 if (mesh->normals_domain() == bke::MeshNormalDomain::Corner) {
133 data->corner_normals = mesh->corner_normals();
134 }
135 }
136
137 if (shrinkType == MOD_SHRINKWRAP_TARGET_PROJECT) {
139 }
140
141 return true;
142}
143
145
146namespace bke::shrinkwrap {
147
148/* Accumulate edge for average boundary edge direction. */
150 MutableSpan<int8_t> status,
151 int index,
152 const float edge_dir[3],
153 signed char side)
154{
155 BLI_assert(index >= 0);
156 float *direction = vdata[index].direction;
157
158 /* Invert the direction vector if either:
159 * - This is the second edge and both edges have the vertex as start or end.
160 * - For third and above, if it points in the wrong direction.
161 */
162 if (status[index] >= 0 ? status[index] == side : dot_v3v3(direction, edge_dir) < 0) {
163 sub_v3_v3(direction, edge_dir);
164 }
165 else {
166 add_v3_v3(direction, edge_dir);
167 }
168
169 status[index] = (status[index] == 0) ? side : -1;
170}
171
173{
174 const Span<float3> positions = mesh.vert_positions();
175 const Span<int2> edges = mesh.edges();
176 const Span<int> corner_verts = mesh.corner_verts();
177 const Span<int> corner_edges = mesh.corner_edges();
178
179 /* Count faces per edge (up to 2). */
180 Array<int8_t> edge_mode(edges.size(), 0);
181
182 for (const int edge : corner_edges) {
183 if (edge_mode[edge] < 2) {
184 edge_mode[edge]++;
185 }
186 }
187
188 /* Build the boundary edge bitmask. */
189 BitVector<> edge_is_boundary(mesh.edges_num, false);
190
191 int num_boundary_edges = 0;
192 for (const int64_t i : edges.index_range()) {
193 if (edge_mode[i] == 1) {
194 edge_is_boundary[i].set();
195 num_boundary_edges++;
196 }
197 }
198
199 /* If no boundary, return nullptr. */
200 if (num_boundary_edges == 0) {
201 return {};
202 }
203
204 /* Allocate the data object. */
206
207 /* Build the boundary corner_tris bit-mask. */
208 const Span<int3> corner_tris = mesh.corner_tris();
209
210 BitVector<> tri_has_boundary(corner_tris.size(), false);
211
212 for (const int64_t i : corner_tris.index_range()) {
214 edges, corner_verts, corner_edges, corner_tris[i]);
215
216 for (int j = 0; j < 3; j++) {
217 if (real_edges[j] >= 0 && edge_is_boundary[real_edges[j]]) {
218 tri_has_boundary[i].set();
219 break;
220 }
221 }
222 }
223
224 /* Find boundary vertices and build a mapping table for compact storage of data. */
225 Array<int> vert_boundary_id(mesh.verts_num, 0);
226
227 for (const int64_t i : edges.index_range()) {
228 if (edge_is_boundary[i]) {
229 const int2 &edge = edges[i];
230 vert_boundary_id[edge[0]] = 1;
231 vert_boundary_id[edge[1]] = 1;
232 }
233 }
234
235 int boundary_verts_num = 0;
236 for (const int64_t i : positions.index_range()) {
237 vert_boundary_id[i] = (vert_boundary_id[i] != 0) ? boundary_verts_num++ : -1;
238 }
239
240 /* Compute average directions. */
241 Array<ShrinkwrapBoundaryVertData> boundary_verts(boundary_verts_num);
242
243 Array<int8_t> vert_status(boundary_verts_num);
244 for (const int64_t i : edges.index_range()) {
245 if (edge_is_boundary[i]) {
246 const int2 &edge = edges[i];
247
248 float dir[3];
249 sub_v3_v3v3(dir, positions[edge[1]], positions[edge[0]]);
250 normalize_v3(dir);
251
252 merge_vert_dir(boundary_verts.data(), vert_status, vert_boundary_id[edge[0]], dir, 1);
253 merge_vert_dir(boundary_verts.data(), vert_status, vert_boundary_id[edge[1]], dir, 2);
254 }
255 }
256
257 /* Finalize average direction and compute normal. */
258 const Span<float3> vert_normals = mesh.vert_normals();
259 for (const int64_t i : positions.index_range()) {
260 int bidx = vert_boundary_id[i];
261
262 if (bidx >= 0) {
263 ShrinkwrapBoundaryVertData *vdata = &boundary_verts[bidx];
264 float tmp[3];
265
266 normalize_v3(vdata->direction);
267
268 cross_v3_v3v3(tmp, vert_normals[i], vdata->direction);
269 cross_v3_v3v3(vdata->normal_plane, tmp, vert_normals[i]);
271 }
272 }
273
274 data.edge_is_boundary = std::move(edge_is_boundary);
275 data.tri_has_boundary = std::move(tri_has_boundary);
276 data.vert_boundary_id = std::move(vert_boundary_id);
277 data.boundary_verts = std::move(boundary_verts);
278
279 return data;
280}
281
283{
284 mesh.runtime->shrinkwrap_boundary_cache.ensure(
286 return mesh.runtime->shrinkwrap_boundary_cache.data();
287}
288
289} // namespace bke::shrinkwrap
290
298 const bke::bvh::Tree &tree,
299 const int i)
300{
301 float *co = calc->vertexCos[i];
302 float3 tmp_co;
304 calc->dvert, i, calc->vgroup, calc->invert_vgroup);
305
306 if (weight == 0.0f) {
307 return;
308 }
309
310 /* Convert the vertex to tree coordinates */
311 if (calc->vert_positions) {
312 tmp_co = calc->vert_positions[i];
313 }
314 else {
315 tmp_co = float3(co);
316 }
318
319 const std::optional<bke::bvh::ClosestPointResult> nearest = tree.closest_point(tmp_co);
320
321 /* Found the nearest vertex */
322 if (nearest) {
323 /* Adjusting the vertex weight,
324 * so that after interpolating it keeps a certain distance from the nearest position */
325 const float dist_sq = math::distance_squared(tmp_co, nearest->position);
326 if (dist_sq > FLT_EPSILON) {
327 const float dist = sqrtf(dist_sq);
328 weight *= (dist - calc->keepDist) / dist;
329 }
330
331 /* Convert the coordinates back to mesh coordinates */
332 tmp_co = nearest->position;
334
335 interp_v3_v3v3(co, co, tmp_co, weight); /* linear interpolation */
336 }
337}
338
340{
341 const bke::bvh::Tree &tree = *calc->tree->vert_tree;
342 threading::parallel_for(IndexRange(calc->numVerts), 512, [&](const IndexRange range) {
343 for (const int64_t i : range) {
344 shrinkwrap_calc_nearest_vertex_cb_ex(calc, tree, int(i));
345 }
346 });
347}
348
350 const float vert[3],
351 const float dir[3],
352 const SpaceTransform *transf,
353 ShrinkwrapTreeData *tree,
354 BVHTreeRayHit *hit)
355{
356 /* don't use this because this dist value could be incompatible
357 * this value used by the callback for comparing previous/new dist values.
358 * also, at the moment there is no need to have a corrected 'dist' value */
359 // #define USE_DIST_CORRECT
360
361 float tmp_co[3], tmp_no[3];
362 const float *co, *no;
363 BVHTreeRayHit hit_tmp;
364
365 /* Copy from hit (we need to convert hit rays from one space coordinates to the other) */
366 memcpy(&hit_tmp, hit, sizeof(hit_tmp));
367
368 /* Apply space transform (TODO readjust dist) */
369 if (transf) {
370 copy_v3_v3(tmp_co, vert);
371 BLI_space_transform_apply(transf, tmp_co);
372 co = tmp_co;
373
374 copy_v3_v3(tmp_no, dir);
375 BLI_space_transform_apply_normal(transf, tmp_no);
376 no = tmp_no;
377
378#ifdef USE_DIST_CORRECT
379 hit_tmp.dist *= mat4_to_scale(((SpaceTransform *)transf)->local2target);
380#endif
381 }
382 else {
383 co = vert;
384 no = dir;
385 }
386
387 hit_tmp.index = -1;
388
390 tree->bvh, co, no, 0.0f, &hit_tmp, tree->treeData.raycast_callback, &tree->treeData);
391
392 if (hit_tmp.index != -1) {
393 /* invert the normal first so face culling works on rotated objects */
394 if (transf) {
395 BLI_space_transform_invert_normal(transf, hit_tmp.no);
396 }
397
399 /* Apply back-face. */
400 const float dot = dot_v3v3(dir, hit_tmp.no);
401 if (((options & MOD_SHRINKWRAP_CULL_TARGET_FRONTFACE) && dot <= 0.0f) ||
403 {
404 return false; /* Ignore hit */
405 }
406 }
407
408 if (transf) {
409 /* Inverting space transform (TODO: make coherent with the initial dist readjust). */
410 BLI_space_transform_invert(transf, hit_tmp.co);
411#ifdef USE_DIST_CORRECT
412 hit_tmp.dist = len_v3v3(vert, hit_tmp.co);
413#endif
414 }
415
416 BLI_assert(hit_tmp.dist <= hit->dist);
417
418 memcpy(hit, &hit_tmp, sizeof(hit_tmp));
419 return true;
420 }
421 return false;
422}
423
425 ShrinkwrapTreeData *aux_tree,
426 const float *proj_axis,
427 SpaceTransform *local2aux,
428 const int i,
429 BVHTreeRayHit *hit)
430{
431 ShrinkwrapTreeData *tree = calc->tree;
432
433 const float proj_limit_squared = calc->smd->projLimit * calc->smd->projLimit;
434 float *co = calc->vertexCos[i];
435 const float *tmp_co, *tmp_no;
437 calc->dvert, i, calc->vgroup, calc->invert_vgroup);
438
439 if (weight == 0.0f) {
440 return;
441 }
442
443 if (calc->vert_positions != nullptr && calc->smd->projAxis == MOD_SHRINKWRAP_PROJECT_OVER_NORMAL)
444 {
445 /* calc->vert_positions contains verts from evaluated mesh. */
446 /* These coordinates are deformed by vertexCos only for normal projection
447 * (to get correct normals) for other cases calc->verts contains undeformed coordinates and
448 * vertexCos should be used */
449 tmp_co = calc->vert_positions[i];
450 tmp_no = calc->vert_normals[i];
451 }
452 else {
453 tmp_co = co;
454 tmp_no = proj_axis;
455 }
456
457 hit->index = -1;
458
459 /* TODO: we should use FLT_MAX here, but sweep-sphere code isn't prepared for that. */
461
462 bool is_aux = false;
463
464 /* Project over positive direction of axis. */
466 if (aux_tree) {
467 if (BKE_shrinkwrap_project_normal(0, tmp_co, tmp_no, local2aux, aux_tree, hit)) {
468 is_aux = true;
469 }
470 }
471
473 calc->smd->shrinkOpts, tmp_co, tmp_no, &calc->local2target, tree, hit))
474 {
475 is_aux = false;
476 }
477 }
478
479 /* Project over negative direction of axis */
481 float inv_no[3];
482 negate_v3_v3(inv_no, tmp_no);
483
484 char options = calc->smd->shrinkOpts;
485
488 {
490 }
491
492 if (aux_tree) {
493 if (BKE_shrinkwrap_project_normal(0, tmp_co, inv_no, local2aux, aux_tree, hit)) {
494 is_aux = true;
495 }
496 }
497
498 if (BKE_shrinkwrap_project_normal(options, tmp_co, inv_no, &calc->local2target, tree, hit)) {
499 is_aux = false;
500 }
501 }
502
503 /* don't set the initial dist (which is more efficient),
504 * because its calculated in the targets space, we want the dist in our own space */
505 if (proj_limit_squared != 0.0f) {
506 if (hit->index != -1 && len_squared_v3v3(hit->co, co) > proj_limit_squared) {
507 hit->index = -1;
508 }
509 }
510
511 if (hit->index != -1) {
512 if (is_aux) {
514 local2aux,
515 calc->smd->shrinkMode,
516 hit->index,
517 hit->co,
518 hit->no,
519 calc->keepDist,
520 tmp_co,
521 hit->co);
522 }
523 else {
525 &calc->local2target,
526 calc->smd->shrinkMode,
527 hit->index,
528 hit->co,
529 hit->no,
530 calc->keepDist,
531 tmp_co,
532 hit->co);
533 }
534
535 interp_v3_v3v3(co, co, hit->co, weight);
536 }
537}
538
540{
541 /* Options about projection direction */
542 float proj_axis[3] = {0.0f, 0.0f, 0.0f};
543
544 /* Ray-cast and tree stuff. */
545
546 /* auxiliary target */
547 Mesh *auxMesh = nullptr;
548 ShrinkwrapTreeData *aux_tree = nullptr;
549 ShrinkwrapTreeData aux_tree_stack;
550 SpaceTransform local2aux;
551
552 /* If the user doesn't allows to project in any direction of projection axis
553 * then there's nothing todo. */
554 if ((calc->smd->shrinkOpts &
556 {
557 return;
558 }
559
560 /* Prepare data to retrieve the direction in which we should project each vertex */
562 if (calc->vert_positions == nullptr) {
563 return;
564 }
565 }
566 else {
567 /* The code supports any axis that is a combination of X,Y,Z
568 * although currently UI only allows to set the 3 different axis */
570 proj_axis[0] = 1.0f;
571 }
573 proj_axis[1] = 1.0f;
574 }
576 proj_axis[2] = 1.0f;
577 }
578
579 normalize_v3(proj_axis);
580
581 /* Invalid projection direction */
582 if (len_squared_v3(proj_axis) < FLT_EPSILON) {
583 return;
584 }
585 }
586
587 if (calc->aux_target) {
589 if (!auxMesh) {
590 return;
591 }
592 BLI_SPACE_TRANSFORM_SETUP(&local2aux, calc->ob, calc->aux_target);
593 }
594
596 &aux_tree_stack, auxMesh, calc->smd->shrinkType, calc->smd->shrinkMode, false))
597 {
598 aux_tree = &aux_tree_stack;
599 }
600
601 /* After successfully build the trees, start projection vertices. */
602 threading::parallel_for(IndexRange(calc->numVerts), 512, [&](const IndexRange range) {
608 BVHTreeRayHit hit{};
609 for (const int64_t i : range) {
610 shrinkwrap_calc_normal_projection_cb_ex(calc, aux_tree, proj_axis, &local2aux, int(i), &hit);
611 }
612 });
613
614 /* free data structures */
615 if (aux_tree) {
616 BKE_shrinkwrap_free_tree(aux_tree);
617 }
618}
619
620/*
621 * Shrinkwrap Target Surface Project mode
622 *
623 * It uses Newton's method to find a surface location with its
624 * smooth normal pointing at the original point.
625 *
626 * The equation system on barycentric weights and normal multiplier:
627 *
628 * (w0*V0 + w1*V1 + w2*V2) + l * (w0*N0 + w1*N1 + w2*N2) - CO = 0
629 * w0 + w1 + w2 = 1
630 *
631 * The actual solution vector is [ w0, w1, l ], with w2 eliminated.
632 */
633
634// #define TRACE_TARGET_PROJECT
635
637 const float **vtri_co;
638 const float (*vtri_no)[3];
639 const float *point_co;
640
643
644 /* Current interpolated position and normal. */
645 float co_interp[3], no_interp[3];
646};
647
648/* Computes the deviation of the equation system from goal. */
649static void target_project_tri_deviation(void *userdata, const float x[3], float r_delta[3])
650{
651 TargetProjectTriData *data = static_cast<TargetProjectTriData *>(userdata);
652
653 const float w[3] = {x[0], x[1], 1.0f - x[0] - x[1]};
654 interp_v3_v3v3v3(data->co_interp, data->vtri_co[0], data->vtri_co[1], data->vtri_co[2], w);
655 interp_v3_v3v3v3(data->no_interp, data->vtri_no[0], data->vtri_no[1], data->vtri_no[2], w);
656
657 madd_v3_v3v3fl(r_delta, data->co_interp, data->no_interp, x[2]);
658 sub_v3_v3(r_delta, data->point_co);
659}
660
661/* Computes the Jacobian matrix of the equation system. */
662static void target_project_tri_jacobian(void *userdata, const float x[3], float r_jacobian[3][3])
663{
664 TargetProjectTriData *data = static_cast<TargetProjectTriData *>(userdata);
665
666 madd_v3_v3v3fl(r_jacobian[0], data->c0_minus_c2, data->n0_minus_n2, x[2]);
667 madd_v3_v3v3fl(r_jacobian[1], data->c1_minus_c2, data->n1_minus_n2, x[2]);
668
669 copy_v3_v3(r_jacobian[2], data->vtri_no[2]);
670 madd_v3_v3fl(r_jacobian[2], data->n0_minus_n2, x[0]);
671 madd_v3_v3fl(r_jacobian[2], data->n1_minus_n2, x[1]);
672}
673
674/* Clamp barycentric weights to the triangle. */
675static void target_project_tri_clamp(float x[3])
676{
677 x[0] = std::max(x[0], 0.0f);
678 x[1] = std::max(x[1], 0.0f);
679 if (x[0] + x[1] > 1.0f) {
680 x[0] = x[0] / (x[0] + x[1]);
681 x[1] = 1.0f - x[0];
682 }
683}
684
685/* Correct the Newton's method step to keep the coordinates within the triangle. */
686static bool target_project_tri_correct(void * /*userdata*/,
687 const float x[3],
688 float step[3],
689 float x_next[3])
690{
691 /* Insignificant correction threshold */
692 const float epsilon = 1e-5f;
693 /* Dot product threshold for checking if step is 'clearly' pointing outside. */
694 const float dir_epsilon = 0.5f;
695 bool fixed = false, locked = false;
696
697 /* The barycentric coordinate domain is a triangle bounded by
698 * the X and Y axes, plus the x+y=1 diagonal. First, clamp the
699 * movement against the diagonal. Note that step is subtracted. */
700 float sum = x[0] + x[1];
701 float sstep = -(step[0] + step[1]);
702
703 if (sum + sstep > 1.0f) {
704 float ldist = 1.0f - sum;
705
706 /* If already at the boundary, slide along it. */
707 if (ldist < epsilon * float(M_SQRT2)) {
708 float step_len = len_v2(step);
709
710 /* Abort if the solution is clearly outside the domain. */
711 if (step_len > epsilon && sstep > step_len * dir_epsilon * float(M_SQRT2)) {
712 return false;
713 }
714
715 /* Project the new position onto the diagonal. */
716 add_v2_fl(step, (sum + sstep - 1.0f) * 0.5f);
717 fixed = locked = true;
718 }
719 else {
720 /* Scale a significant step down to arrive at the boundary. */
721 mul_v3_fl(step, ldist / sstep);
722 fixed = true;
723 }
724 }
725
726 /* Weight 0 and 1 boundary checks - along axis. */
727 for (int i = 0; i < 2; i++) {
728 if (step[i] > x[i]) {
729 /* If already at the boundary, slide along it. */
730 if (x[i] < epsilon) {
731 float step_len = len_v2(step);
732
733 /* Abort if the solution is clearly outside the domain. */
734 if (step_len > epsilon && (locked || step[i] > step_len * dir_epsilon)) {
735 return false;
736 }
737
738 /* Reset precision errors to stay at the boundary. */
739 step[i] = x[i];
740 fixed = true;
741 }
742 else {
743 /* Scale a significant step down to arrive at the boundary. */
744 mul_v3_fl(step, x[i] / step[i]);
745 fixed = true;
746 }
747 }
748 }
749
750 /* Recompute and clamp the new coordinates after step correction. */
751 if (fixed) {
752 sub_v3_v3v3(x_next, x, step);
754 }
755
756 return true;
757}
758
759static bool target_project_solve_point_tri(const float *vtri_co[3],
760 const float vtri_no[3][3],
761 const float point_co[3],
762 const float hit_co[3],
763 float hit_dist_sq,
764 float r_hit_co[3],
765 float r_hit_no[3])
766{
767 float x[3], tmp[3];
768 float dist = sqrtf(hit_dist_sq);
769 float magnitude_estimate = dist + len_manhattan_v3(vtri_co[0]) + len_manhattan_v3(vtri_co[1]) +
770 len_manhattan_v3(vtri_co[2]);
771 float epsilon = magnitude_estimate * 1.0e-6f;
772
773 /* Initial solution vector: barycentric weights plus distance along normal. */
774 interp_weights_tri_v3(x, UNPACK3(vtri_co), hit_co);
775
776 interp_v3_v3v3v3(r_hit_no, UNPACK3(vtri_no), x);
777 sub_v3_v3v3(tmp, point_co, hit_co);
778
779 x[2] = (dot_v3v3(tmp, r_hit_no) < 0) ? -dist : dist;
780
781 /* Solve the equations iteratively. */
782 TargetProjectTriData tri_data{};
783 tri_data.vtri_co = vtri_co;
784 tri_data.vtri_no = vtri_no;
785 tri_data.point_co = point_co;
786
787 sub_v3_v3v3(tri_data.n0_minus_n2, vtri_no[0], vtri_no[2]);
788 sub_v3_v3v3(tri_data.n1_minus_n2, vtri_no[1], vtri_no[2]);
789 sub_v3_v3v3(tri_data.c0_minus_c2, vtri_co[0], vtri_co[2]);
790 sub_v3_v3v3(tri_data.c1_minus_c2, vtri_co[1], vtri_co[2]);
791
793
794#ifdef TRACE_TARGET_PROJECT
795 const bool trace = true;
796#else
797 const bool trace = false;
798#endif
799
803 &tri_data,
804 epsilon,
805 20,
806 trace,
807 x,
808 x);
809
810 if (ok) {
811 copy_v3_v3(r_hit_co, tri_data.co_interp);
812 copy_v3_v3(r_hit_no, tri_data.no_interp);
813
814 return true;
815 }
816
817 return false;
818}
819
820static bool update_hit(BVHTreeNearest *nearest,
821 int index,
822 const float co[3],
823 const float hit_co[3],
824 const float hit_no[3])
825{
826 float dist_sq = len_squared_v3v3(hit_co, co);
827
828 if (dist_sq < nearest->dist_sq) {
829#ifdef TRACE_TARGET_PROJECT
830 printf(
831 "#=#=#> %d (%.3f,%.3f,%.3f) %g < %g\n", index, UNPACK3(hit_co), dist_sq, nearest->dist_sq);
832#endif
833 nearest->index = index;
834 nearest->dist_sq = dist_sq;
835 copy_v3_v3(nearest->co, hit_co);
836 normalize_v3_v3(nearest->no, hit_no);
837 return true;
838 }
839
840 return false;
841}
842
843/* Target projection on a non-manifold boundary edge -
844 * treats it like an infinitely thin cylinder. */
846 int index,
847 const float co[3],
848 BVHTreeNearest *nearest,
849 int eidx)
850{
851 const bke::BVHTreeFromMesh *data = &tree->treeData;
852 const int2 &edge = tree->edges[eidx];
853 const float *vedge_co[2] = {data->vert_positions[edge[0]], data->vert_positions[edge[1]]};
854
855#ifdef TRACE_TARGET_PROJECT
856 printf("EDGE %d (%.3f,%.3f,%.3f) (%.3f,%.3f,%.3f)\n",
857 eidx,
858 UNPACK3(vedge_co[0]),
859 UNPACK3(vedge_co[1]));
860#endif
861
862 /* Retrieve boundary vertex IDs */
863 const int *vert_boundary_id = tree->boundary->vert_boundary_id.data();
864 const int bid1 = vert_boundary_id[edge[0]], bid2 = vert_boundary_id[edge[1]];
865
866 if (bid1 < 0 || bid2 < 0) {
867 return;
868 }
869
870 /* Retrieve boundary vertex normals and align them to direction. */
871 const ShrinkwrapBoundaryVertData *boundary_verts = tree->boundary->boundary_verts.data();
872 float vedge_dir[2][3], dir[3];
873
874 copy_v3_v3(vedge_dir[0], boundary_verts[bid1].normal_plane);
875 copy_v3_v3(vedge_dir[1], boundary_verts[bid2].normal_plane);
876
877 sub_v3_v3v3(dir, vedge_co[1], vedge_co[0]);
878
879 if (dot_v3v3(boundary_verts[bid1].direction, dir) < 0) {
880 negate_v3(vedge_dir[0]);
881 }
882 if (dot_v3v3(boundary_verts[bid2].direction, dir) < 0) {
883 negate_v3(vedge_dir[1]);
884 }
885
886 /* Solve a quadratic equation: `lerp(d0,d1,x) * (co - lerp(v0,v1,x)) = 0`. */
887 const float d0v0 = dot_v3v3(vedge_dir[0], vedge_co[0]),
888 d0v1 = dot_v3v3(vedge_dir[0], vedge_co[1]);
889 const float d1v0 = dot_v3v3(vedge_dir[1], vedge_co[0]),
890 d1v1 = dot_v3v3(vedge_dir[1], vedge_co[1]);
891 const float d0co = dot_v3v3(vedge_dir[0], co);
892
893 /* Checked for non-zero prevent divide by zero when calculating `x`. */
894 const float a = d0v1 - d0v0 + d1v0 - d1v1;
895 if (a != 0.0f) {
896 const float b = 2 * d0v0 - d0v1 - d0co - d1v0 + dot_v3v3(vedge_dir[1], co);
897 const float c = d0co - d0v0;
898 const float det = b * b - 4 * a * c;
899
900 if (det >= 0) {
901 const float epsilon = 1e-6f;
902 const float sdet = sqrtf(det);
903 float hit_co[3], hit_no[3];
904
905 for (int i = (det > 0 ? 2 : 0); i >= 0; i -= 2) {
906 float x = (-b + float(i - 1) * sdet) / (2.0f * a);
907
908 if (x >= -epsilon && x <= 1.0f + epsilon) {
909 CLAMP(x, 0.0f, 1.0f);
910
911 float vedge_no[2][3];
912 copy_v3_v3(vedge_no[0], tree->vert_normals[edge[0]]);
913 copy_v3_v3(vedge_no[1], tree->vert_normals[edge[1]]);
914
915 interp_v3_v3v3(hit_co, vedge_co[0], vedge_co[1], x);
916 interp_v3_v3v3(hit_no, vedge_no[0], vedge_no[1], x);
917
918 update_hit(nearest, index, co, hit_co, hit_no);
919 }
920 }
921 }
922 }
923}
924
925/* Target normal projection BVH callback - based on mesh_corner_tri_nearest_point. */
926static void mesh_corner_tris_target_project(void *userdata,
927 int index,
928 const float co[3],
929 BVHTreeNearest *nearest)
930{
931 const ShrinkwrapTreeData *tree = static_cast<ShrinkwrapTreeData *>(userdata);
932 const bke::BVHTreeFromMesh *data = &tree->treeData;
933 const int3 &tri = data->corner_tris[index];
934 const int tri_verts[3] = {
935 data->corner_verts[tri[0]],
936 data->corner_verts[tri[1]],
937 data->corner_verts[tri[2]],
938 };
939 const float *vtri_co[3] = {
940 data->vert_positions[tri_verts[0]],
941 data->vert_positions[tri_verts[1]],
942 data->vert_positions[tri_verts[2]],
943 };
944 float raw_hit_co[3], hit_co[3], hit_no[3], dist_sq, vtri_no[3][3];
945
946 /* First find the closest point and bail out if it's worse than the current solution. */
947 closest_on_tri_to_point_v3(raw_hit_co, co, UNPACK3(vtri_co));
948 dist_sq = len_squared_v3v3(co, raw_hit_co);
949
950#ifdef TRACE_TARGET_PROJECT
951 printf("TRIANGLE %d (%.3f,%.3f,%.3f) (%.3f,%.3f,%.3f) (%.3f,%.3f,%.3f) %g %g\n",
952 index,
953 UNPACK3(vtri_co[0]),
954 UNPACK3(vtri_co[1]),
955 UNPACK3(vtri_co[2]),
956 dist_sq,
957 nearest->dist_sq);
958#endif
959
960 if (dist_sq >= nearest->dist_sq) {
961 return;
962 }
963
964 /* Decode normals */
965 copy_v3_v3(vtri_no[0], tree->vert_normals[tri_verts[0]]);
966 copy_v3_v3(vtri_no[1], tree->vert_normals[tri_verts[1]]);
967 copy_v3_v3(vtri_no[2], tree->vert_normals[tri_verts[2]]);
968
969 /* Solve the equations for the triangle */
970 if (target_project_solve_point_tri(vtri_co, vtri_no, co, raw_hit_co, dist_sq, hit_co, hit_no)) {
971 update_hit(nearest, index, co, hit_co, hit_no);
972 }
973 /* Boundary edges */
974 else if (tree->boundary && tree->boundary->has_boundary() &&
976 {
977 const BitSpan is_boundary = tree->boundary->edge_is_boundary;
979 tree->edges, data->corner_verts, tree->corner_edges, tri);
980
981 for (int i = 0; i < 3; i++) {
982 if (edges[i] >= 0 && is_boundary[edges[i]]) {
983 target_project_edge(tree, index, co, nearest, edges[i]);
984 }
985 }
986 }
987}
988
990 BVHTreeNearest *nearest,
991 float co[3],
992 int type)
993{
994 bke::BVHTreeFromMesh *treeData = &tree->treeData;
995
996 if (type == MOD_SHRINKWRAP_NEAREST_VERTEX) {
997 const std::optional<bke::bvh::ClosestPointResult> result = tree->vert_tree->closest_point(
998 co, sqrtf(nearest->dist_sq));
999 if (result) {
1000 nearest->index = int(result->index);
1001 nearest->dist_sq = math::distance_squared(float3(co), result->position);
1002 copy_v3_v3(nearest->co, result->position);
1003 }
1004 return;
1005 }
1006
1007 if (type == MOD_SHRINKWRAP_TARGET_PROJECT) {
1008#ifdef TRACE_TARGET_PROJECT
1009 printf("\n====== TARGET PROJECT START ======\n");
1010#endif
1011
1014
1015#ifdef TRACE_TARGET_PROJECT
1016 printf("====== TARGET PROJECT END: %d %g ======\n\n", nearest->index, nearest->dist_sq);
1017#endif
1018
1019 if (nearest->index < 0) {
1020 /* fall back to simple nearest */
1021 BLI_bvhtree_find_nearest(tree->bvh, co, nearest, treeData->nearest_callback, treeData);
1022 }
1023 }
1024 else {
1025 BLI_bvhtree_find_nearest(tree->bvh, co, nearest, treeData->nearest_callback, treeData);
1026 }
1027}
1028
1036 const int i,
1037 BVHTreeNearest *nearest)
1038{
1039 float *co = calc->vertexCos[i];
1040 float tmp_co[3];
1042 calc->dvert, i, calc->vgroup, calc->invert_vgroup);
1043
1044 if (weight == 0.0f) {
1045 return;
1046 }
1047
1048 /* Convert the vertex to tree coordinates */
1049 if (calc->vert_positions) {
1050 copy_v3_v3(tmp_co, calc->vert_positions[i]);
1051 }
1052 else {
1053 copy_v3_v3(tmp_co, co);
1054 }
1056
1057 /* Use local proximity heuristics (to reduce the nearest search)
1058 *
1059 * If we already had an hit before.. we assume this vertex is going to have a close hit to that
1060 * other vertex so we can initiate the "nearest.dist" with the expected value to that last hit.
1061 * This will lead in pruning of the search tree. */
1062 if (nearest->index != -1) {
1064 /* Heuristic doesn't work because of additional restrictions. */
1065 nearest->index = -1;
1066 nearest->dist_sq = FLT_MAX;
1067 }
1068 else {
1069 nearest->dist_sq = len_squared_v3v3(tmp_co, nearest->co);
1070 }
1071 }
1072 else {
1073 nearest->dist_sq = FLT_MAX;
1074 }
1075
1076 BKE_shrinkwrap_find_nearest_surface(calc->tree, nearest, tmp_co, calc->smd->shrinkType);
1077
1078 /* Found the nearest vertex */
1079 if (nearest->index != -1) {
1081 nullptr,
1082 calc->smd->shrinkMode,
1083 nearest->index,
1084 nearest->co,
1085 nearest->no,
1086 calc->keepDist,
1087 tmp_co,
1088 tmp_co);
1089
1090 /* Convert the coordinates back to mesh coordinates */
1092 interp_v3_v3v3(co, co, tmp_co, weight); /* linear interpolation */
1093 }
1094}
1095
1098 int corner_tri_idx,
1099 const float hit_co[3],
1100 const float hit_no[3],
1101 float r_no[3])
1102{
1103 const bke::BVHTreeFromMesh *treeData = &tree->treeData;
1104 const int3 &tri = treeData->corner_tris[corner_tri_idx];
1105 const int face_i = tree->mesh->corner_tri_faces()[corner_tri_idx];
1106
1107 /* Interpolate smooth normals if enabled. */
1108 if (tree->sharp_faces.is_empty() || tree->sharp_faces[face_i]) {
1109 const int vert_indices[3] = {treeData->corner_verts[tri[0]],
1110 treeData->corner_verts[tri[1]],
1111 treeData->corner_verts[tri[2]]};
1112 float w[3], no[3][3], tmp_co[3];
1113
1114 /* Custom normals. */
1115 if (!tree->corner_normals.is_empty()) {
1116 copy_v3_v3(no[0], tree->corner_normals[tri[0]]);
1117 copy_v3_v3(no[1], tree->corner_normals[tri[1]]);
1118 copy_v3_v3(no[2], tree->corner_normals[tri[2]]);
1119 }
1120 /* Ordinary vertex normals. */
1121 else {
1122 copy_v3_v3(no[0], tree->vert_normals[vert_indices[0]]);
1123 copy_v3_v3(no[1], tree->vert_normals[vert_indices[1]]);
1124 copy_v3_v3(no[2], tree->vert_normals[vert_indices[2]]);
1125 }
1126
1127 /* Barycentric weights from hit point. */
1128 copy_v3_v3(tmp_co, hit_co);
1129
1130 if (transform) {
1132 }
1133
1135 treeData->vert_positions[vert_indices[0]],
1136 treeData->vert_positions[vert_indices[1]],
1137 treeData->vert_positions[vert_indices[2]],
1138 tmp_co);
1139
1140 /* Interpolate using weights. */
1141 interp_v3_v3v3v3(r_no, no[0], no[1], no[2], w);
1142
1143 if (transform) {
1145 }
1146 else {
1147 normalize_v3(r_no);
1148 }
1149 }
1150 /* Use the face normal if flat. */
1151 else if (!tree->face_normals.is_empty()) {
1152 copy_v3_v3(r_no, tree->face_normals[face_i]);
1153 if (transform) {
1155 }
1156 }
1157 /* Finally fall back to the corner_tris normal. */
1158 else {
1159 copy_v3_v3(r_no, hit_no);
1160 }
1161}
1162
1163/* Helper for MOD_SHRINKWRAP_INSIDE, MOD_SHRINKWRAP_OUTSIDE and MOD_SHRINKWRAP_OUTSIDE_SURFACE. */
1164static void shrinkwrap_snap_with_side(float r_point_co[3],
1165 const float point_co[3],
1166 const float hit_co[3],
1167 const float hit_no[3],
1168 float goal_dist,
1169 float forcesign,
1170 bool forcesnap)
1171{
1172 float delta[3];
1173 sub_v3_v3v3(delta, point_co, hit_co);
1174
1175 float dist = len_v3(delta);
1176
1177 /* If exactly on the surface, push out along normal */
1178 if (dist < FLT_EPSILON) {
1179 if (forcesnap || goal_dist > 0) {
1180 madd_v3_v3v3fl(r_point_co, hit_co, hit_no, goal_dist * forcesign);
1181 }
1182 else {
1183 copy_v3_v3(r_point_co, hit_co);
1184 }
1185 }
1186 /* Move to the correct side if needed */
1187 else {
1188 float dsign = signf(dot_v3v3(delta, hit_no));
1189
1190 if (forcesign == 0.0f) {
1191 forcesign = dsign;
1192 }
1193
1194 /* If on the wrong side or too close, move to correct */
1195 if (forcesnap || dsign * dist * forcesign < goal_dist) {
1196 mul_v3_fl(delta, dsign / dist);
1197
1198 /* At very small distance, blend in the hit normal to stabilize math. */
1199 float dist_epsilon = (fabsf(goal_dist) + len_manhattan_v3(hit_co)) * 1e-4f;
1200
1201 if (dist < dist_epsilon) {
1202#ifdef TRACE_TARGET_PROJECT
1203 printf("zero_factor %g = %g / %g\n", dist / dist_epsilon, dist, dist_epsilon);
1204#endif
1205
1206 interp_v3_v3v3(delta, hit_no, delta, dist / dist_epsilon);
1207 }
1208
1209 madd_v3_v3v3fl(r_point_co, hit_co, delta, goal_dist * forcesign);
1210 }
1211 else {
1212 copy_v3_v3(r_point_co, point_co);
1213 }
1214 }
1215}
1216
1219 int mode,
1220 int hit_idx,
1221 const float hit_co[3],
1222 const float hit_no[3],
1223 float goal_dist,
1224 const float point_co[3],
1225 float r_point_co[3])
1226{
1227 float tmp[3];
1228
1229 switch (mode) {
1230 /* Offsets along the line between point_co and hit_co. */
1232 if (goal_dist != 0) {
1233 shrinkwrap_snap_with_side(r_point_co, point_co, hit_co, hit_no, goal_dist, 0, true);
1234 }
1235 else {
1236 copy_v3_v3(r_point_co, hit_co);
1237 }
1238 break;
1239
1241 shrinkwrap_snap_with_side(r_point_co, point_co, hit_co, hit_no, goal_dist, -1, false);
1242 break;
1243
1245 shrinkwrap_snap_with_side(r_point_co, point_co, hit_co, hit_no, goal_dist, +1, false);
1246 break;
1247
1249 if (goal_dist != 0) {
1250 shrinkwrap_snap_with_side(r_point_co, point_co, hit_co, hit_no, goal_dist, +1, true);
1251 }
1252 else {
1253 copy_v3_v3(r_point_co, hit_co);
1254 }
1255 break;
1256
1257 /* Offsets along the normal */
1259 if (goal_dist != 0) {
1260 BKE_shrinkwrap_compute_smooth_normal(tree, transform, hit_idx, hit_co, hit_no, tmp);
1261 madd_v3_v3v3fl(r_point_co, hit_co, tmp, goal_dist);
1262 }
1263 else {
1264 copy_v3_v3(r_point_co, hit_co);
1265 }
1266 break;
1267
1268 default:
1269 printf("Unknown Shrinkwrap surface snap mode: %d\n", mode);
1270 copy_v3_v3(r_point_co, hit_co);
1271 }
1272}
1273
1275{
1276 /* Find the nearest vertex */
1277 threading::parallel_for(IndexRange(calc->numVerts), 512, [&](const IndexRange range) {
1278 BVHTreeNearest nearest{};
1279 nearest.index = -1;
1280 nearest.dist_sq = FLT_MAX;
1281 for (const int64_t i : range) {
1282 shrinkwrap_calc_nearest_surface_point_cb_ex(calc, int(i), &nearest);
1283 }
1284 });
1285}
1286
1288{
1289 using namespace blender::bke;
1290
1291 Array<float3> positions = mesh->vert_positions();
1292
1293 subdiv::Settings settings{};
1294 settings.is_simple = false;
1295 settings.is_adaptive = false;
1296 settings.level = subdivision_level;
1297 settings.use_creases = true;
1298
1299 /* Default subdivision surface modifier settings:
1300 * - UV Smooth:Keep Corners.
1301 * - BoundarySmooth: All. */
1303 settings.fvar_linear_interpolation =
1305
1306 subdiv::Subdiv *subdiv = subdiv::update_from_mesh(nullptr, &settings, mesh);
1307 if (subdiv) {
1310 }
1311
1312 return positions;
1313}
1314
1316 const ModifierEvalContext *ctx,
1317 Scene * /*scene*/,
1318 Object *ob,
1319 Mesh *mesh,
1320 const MDeformVert *dvert,
1321 const int defgrp_index,
1322 float (*vertexCos)[3],
1323 int numVerts)
1324{
1326 Array<float3> subdivided_positions;
1327
1328 /* remove loop dependencies on derived meshes (TODO should this be done elsewhere?) */
1329 if (smd->target == ob) {
1330 smd->target = nullptr;
1331 }
1332 if (smd->auxTarget == ob) {
1333 smd->auxTarget = nullptr;
1334 }
1335
1336 /* Configure Shrinkwrap calc data */
1337 calc.smd = smd;
1338 calc.ob = ob;
1339 calc.numVerts = numVerts;
1340 calc.vertexCos = vertexCos;
1341 calc.dvert = dvert;
1342 calc.vgroup = defgrp_index;
1344
1345 if (smd->target != nullptr) {
1346 Object *ob_target = DEG_get_evaluated(ctx->depsgraph, smd->target);
1348
1349 /* TODO: there might be several "bugs" with non-uniform scales matrices
1350 * because it will no longer be nearest surface, not sphere projection
1351 * because space has been deformed */
1352 BLI_SPACE_TRANSFORM_SETUP(&calc.local2target, ob, ob_target);
1353
1354 /* TODO: smd->keepDist is in global units.. must change to local */
1355 calc.keepDist = smd->keepDist;
1356 }
1358
1359 if (mesh != nullptr && smd->shrinkType == MOD_SHRINKWRAP_PROJECT) {
1360 /* Setup arrays to get vertex positions, normals and deform weights */
1361 calc.vert_positions = reinterpret_cast<float (*)[3]>(mesh->vert_positions_for_write().data());
1362 calc.vert_normals = mesh->vert_normals();
1363
1364 /* Using vertices positions/normals as if a subsurface was applied */
1365 if (smd->subsurfLevels) {
1366 subdivided_positions = shrinkwrap_calc_subdivided_positions(mesh, smd->subsurfLevels);
1367 calc.vert_positions = reinterpret_cast<float (*)[3]>(subdivided_positions.data());
1368 }
1369 }
1370
1371 /* Projecting target defined - lets work! */
1372 ShrinkwrapTreeData tree;
1373
1374 if (BKE_shrinkwrap_init_tree(&tree, calc.target, smd->shrinkType, smd->shrinkMode, false)) {
1375 calc.tree = &tree;
1376
1377 switch (smd->shrinkType) {
1381 break;
1382
1384 TIMEIT_BENCH(shrinkwrap_calc_normal_projection(&calc), deform_project);
1385 break;
1386
1388 TIMEIT_BENCH(shrinkwrap_calc_nearest_vertex(&calc), deform_vertex);
1389 break;
1390 }
1391
1393 }
1394}
1395
1397 Object &object,
1398 ShrinkwrapTreeData &tree,
1399 const Span<MDeformVert> dvert,
1400 const int defgrp_index,
1401 const MutableSpan<float3> positions)
1402{
1403 using namespace blender::bke;
1404
1406 /* Convert params struct to use the same struct and function used with meshes. */
1408 smd.target = params.target;
1409 smd.auxTarget = params.aux_target;
1410 smd.keepDist = params.keep_distance;
1411 smd.shrinkType = params.shrink_type;
1412 smd.shrinkOpts = params.shrink_options;
1413 smd.shrinkMode = params.shrink_mode;
1414 smd.projLimit = params.projection_limit;
1415 smd.projAxis = params.projection_axis;
1416
1417 /* Configure Shrinkwrap calc data. */
1418 calc.smd = &smd;
1419 calc.ob = &object;
1420 calc.numVerts = int(positions.size());
1421 calc.vertexCos = reinterpret_cast<float (*)[3]>(positions.data());
1422 calc.dvert = dvert.is_empty() ? nullptr : dvert.data();
1423 calc.vgroup = defgrp_index;
1425
1426 BLI_SPACE_TRANSFORM_SETUP(&calc.local2target, &object, params.target);
1427 calc.keepDist = params.keep_distance;
1428 calc.tree = &tree;
1429
1430 switch (params.shrink_type) {
1431 case MOD_SHRINKWRAP_NEAREST_SURFACE:
1432 case MOD_SHRINKWRAP_TARGET_PROJECT:
1433 TIMEIT_BENCH(shrinkwrap_calc_nearest_surface_point(&calc), gpdeform_surface);
1434 break;
1435
1436 case MOD_SHRINKWRAP_PROJECT:
1437 TIMEIT_BENCH(shrinkwrap_calc_normal_projection(&calc), gpdeform_project);
1438 break;
1439
1440 case MOD_SHRINKWRAP_NEAREST_VERTEX:
1441 TIMEIT_BENCH(shrinkwrap_calc_nearest_vertex(&calc), gpdeform_vertex);
1442 break;
1443 }
1444}
1445
1447 Scene *scene,
1448 Object *ob_source,
1449 Object *ob_target)
1450{
1451 ShrinkwrapModifierData ssmd = {{nullptr}};
1452 ModifierEvalContext ctx = {depsgraph, ob_source, ModifierApplyFlag(0)};
1453
1454 ssmd.target = ob_target;
1457 ssmd.keepDist = 0.0f;
1458
1459 Mesh *src_me = id_cast<Mesh *>(ob_source->data);
1460
1462 &ssmd,
1463 &ctx,
1464 scene,
1465 ob_source,
1466 src_me,
1467 nullptr,
1468 -1,
1469 reinterpret_cast<float (*)[3]>(src_me->vert_positions_for_write().data()),
1470 src_me->verts_num);
1471 src_me->tag_positions_changed();
1472}
1473
1474void BKE_shrinkwrap_remesh_target_project(Mesh *src_me, Mesh *target_me, Object *ob_target)
1475{
1476 ShrinkwrapModifierData ssmd = {{nullptr}};
1477
1478 ssmd.target = ob_target;
1482 ssmd.keepDist = 0.0f;
1483
1484 /* Tolerance value to prevent artifacts on sharp edges of a mesh.
1485 * This constant and based on experimenting with different values. */
1486 const float projLimitTolerance = 5.0f;
1487 ssmd.projLimit = target_me->remesh_voxel_size * projLimitTolerance;
1488
1490
1491 calc.smd = &ssmd;
1492 calc.numVerts = src_me->verts_num;
1493 calc.vertexCos = reinterpret_cast<float (*)[3]>(src_me->vert_positions_for_write().data());
1494 calc.vert_normals = src_me->vert_normals();
1495 calc.vgroup = -1;
1496 calc.target = target_me;
1497 calc.keepDist = ssmd.keepDist;
1498 calc.vert_positions = reinterpret_cast<float (*)[3]>(src_me->vert_positions_for_write().data());
1499 BLI_SPACE_TRANSFORM_SETUP(&calc.local2target, ob_target, ob_target);
1500
1501 ShrinkwrapTreeData tree;
1502 if (BKE_shrinkwrap_init_tree(&tree, calc.target, ssmd.shrinkType, ssmd.shrinkMode, false)) {
1503 calc.tree = &tree;
1504 TIMEIT_BENCH(shrinkwrap_calc_normal_projection(&calc), deform_project);
1506 }
1507
1508 src_me->tag_positions_changed();
1509}
1510
1511} // namespace blender
support for deformation groups and hooks.
#define NULL_ShrinkwrapCalcData
#define BVH_RAYCAST_DIST_MAX
#define M_SQRT2
#define BLI_SPACE_TRANSFORM_SETUP(data, local, target)
Utility defines for timing/benchmarks.
#define MOD_SHRINKWRAP_CULL_TARGET_MASK
Object is a sort of wrapper for general info.
#define CLAMP(a, b, c)
#define UNPACK3(a)
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
Definition btQuadWord.h:119
const T * data() const
Definition BLI_array.hh:323
constexpr IndexRange()=default
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr T * data() const
Definition BLI_span.hh:545
Array< ShrinkwrapBoundaryVertData > boundary_verts
constexpr const T * data() const
Definition BLI_span.hh:219
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
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
constexpr bool is_empty() const
CCL_NAMESPACE_BEGIN struct Options options
#define FLT_MAX
#define FLT_EPSILON
float dot(VecOp< float, D >, VecOp< float, D >) RET
VecBase< float, D > step(VecOp< float, D >, VecOp< float, D >) RET
int3 corner_tri_get_real_edges(Span< int2 > edges, Span< int > corner_verts, Span< int > corner_edges, const int3 &corner_tri)
static void merge_vert_dir(ShrinkwrapBoundaryVertData *vdata, MutableSpan< int8_t > status, int index, const float edge_dir[3], signed char side)
const ShrinkwrapBoundaryData & boundary_cache_ensure(const Mesh &mesh)
static ShrinkwrapBoundaryData shrinkwrap_build_boundary_data(const Mesh &mesh)
void free(Subdiv *subdiv)
Definition subdiv.cc:192
@ SUBDIV_FVAR_LINEAR_INTERPOLATION_CORNERS_AND_JUNCTIONS
Definition BKE_subdiv.hh:43
void deform_coarse_vertices(Subdiv *subdiv, const Mesh *coarse_mesh, MutableSpan< float3 > vert_positions)
Subdiv * update_from_mesh(Subdiv *subdiv, const Settings *settings, const Mesh *mesh)
Definition subdiv.cc:181
T distance_squared(const VecBase< T, Size > &a, const VecBase< T, Size > &b)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
BMesh Iterators.
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
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])
static void target_project_edge(const ShrinkwrapTreeData *tree, int index, const float co[3], BVHTreeNearest *nearest, int eidx)
void shrinkwrapParams_deform(const ShrinkwrapParams &params, Object &object, ShrinkwrapTreeData &tree, Span< MDeformVert > dvert, int defgrp_index, MutableSpan< float3 > positions)
__int64 int64_t
Definition BKE_text.h:90
@ BVH_NEAREST_OPTIMAL_ORDER
static void mesh_corner_tris_target_project(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
bool BKE_shrinkwrap_needs_normals(int shrinkType, int shrinkMode)
Definition shrinkwrap.cc:80
static bool target_project_solve_point_tri(const float *vtri_co[3], const float vtri_no[3][3], const float point_co[3], const float hit_co[3], float hit_dist_sq, float r_hit_co[3], float r_hit_no[3])
static void shrinkwrap_calc_nearest_surface_point_cb_ex(ShrinkwrapCalcData *calc, const int i, BVHTreeNearest *nearest)
MINLINE void copy_v3_v3(float r[3], const float a[3])
static bool target_project_tri_correct(void *, const float x[3], float step[3], float x_next[3])
int BLI_bvhtree_find_nearest(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata)
static void shrinkwrap_calc_nearest_surface_point(ShrinkwrapCalcData *calc)
bool BKE_shrinkwrap_project_normal(char options, const float vert[3], const float dir[3], const SpaceTransform *transf, ShrinkwrapTreeData *tree, BVHTreeRayHit *hit)
float mat4_to_scale(const float mat[4][4])
MINLINE float len_manhattan_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
void BKE_shrinkwrap_free_tree(ShrinkwrapTreeData *data)
void BLI_space_transform_invert(const struct SpaceTransform *data, float co[3])
void BKE_mesh_wrapper_ensure_mdata(Mesh *mesh)
static void shrinkwrap_calc_nearest_vertex(ShrinkwrapCalcData *calc)
void BKE_shrinkwrap_mesh_nearest_surface_deform(Depsgraph *depsgraph, Scene *scene, Object *ob_source, Object *ob_target)
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)
void BKE_shrinkwrap_remesh_target_project(Mesh *src_me, Mesh *target_me, Object *ob_target)
void BKE_shrinkwrap_find_nearest_surface(ShrinkwrapTreeData *tree, BVHTreeNearest *nearest, float co[3], int type)
MINLINE void mul_v3_fl(float r[3], float f)
MINLINE void sub_v3_v3(float r[3], const float a[3])
Mesh * BKE_modifier_get_evaluated_mesh_from_evaluated_object(Object *ob_eval)
MINLINE void madd_v3_v3fl(float r[3], const float a[3], float f)
int BLI_bvhtree_find_nearest_ex(const BVHTree *tree, const float co[3], BVHTreeNearest *nearest, BVHTree_NearestPointCallback callback, void *userdata, int flag)
VecBase< int32_t, 2 > int2
VecBase< int32_t, 3 > int3
void BKE_shrinkwrap_compute_smooth_normal(const ShrinkwrapTreeData *tree, const SpaceTransform *transform, int tri_idx, const float hit_co[3], const float hit_no[3], float r_no[3])
static void target_project_tri_jacobian(void *userdata, const float x[3], float r_jacobian[3][3])
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
@ MOD_SHRINKWRAP_ABOVE_SURFACE
@ MOD_SHRINKWRAP_OUTSIDE_SURFACE
@ MOD_SHRINKWRAP_ON_SURFACE
BMesh const char void * data
T * DEG_get_evaluated(const Depsgraph *depsgraph, T *id)
MINLINE float signf(float f)
static void target_project_tri_clamp(float x[3])
void interp_weights_tri_v3(float w[3], const float v1[3], const float v2[3], const float v3[3], const float co[3])
MINLINE void negate_v3(float r[3])
float BKE_defvert_array_find_weight_safe(const MDeformVert *dvert, int index, int defgroup, bool invert)
Definition deform.cc:785
switch(BMIterType(itype))
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
MINLINE float len_v3(const float a[3]) ATTR_WARN_UNUSED_RESULT
static void shrinkwrap_calc_normal_projection_cb_ex(ShrinkwrapCalcData *calc, ShrinkwrapTreeData *aux_tree, const float *proj_axis, SpaceTransform *local2aux, const int i, BVHTreeRayHit *hit)
bool BLI_newton3d_solve(Newton3D_DeltaFunc func_delta, Newton3D_JacobianFunc func_jacobian, Newton3D_CorrectionFunc func_correction, void *userdata, float epsilon, int max_iterations, bool trace, const float x_init[3], float result[3])
Solve a generic f(x) = 0 equation using Newton's method.
static bool update_hit(BVHTreeNearest *nearest, int index, const float co[3], const float hit_co[3], const float hit_no[3])
@ MOD_SHRINKWRAP_NEAREST_VERTEX
@ MOD_SHRINKWRAP_NEAREST_SURFACE
@ MOD_SHRINKWRAP_TARGET_PROJECT
void BKE_shrinkwrap_snap_point_to_surface(const ShrinkwrapTreeData *tree, const SpaceTransform *transform, int mode, int hit_idx, const float hit_co[3], const float hit_no[3], float goal_dist, const float point_co[3], float r_point_co[3])
@ MOD_SHRINKWRAP_PROJECT_OVER_Y_AXIS
@ MOD_SHRINKWRAP_PROJECT_OVER_X_AXIS
@ MOD_SHRINKWRAP_PROJECT_OVER_NORMAL
@ MOD_SHRINKWRAP_PROJECT_OVER_Z_AXIS
MINLINE float normalize_v3_v3(float r[3], const float a[3])
MINLINE float normalize_v3(float n[3])
MINLINE void add_v3_v3(float r[3], const float a[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
static void shrinkwrap_snap_with_side(float r_point_co[3], const float point_co[3], const float hit_co[3], const float hit_no[3], float goal_dist, float forcesign, bool forcesnap)
static void target_project_tri_deviation(void *userdata, const float x[3], float r_delta[3])
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])
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
void shrinkwrapModifier_deform(ShrinkwrapModifierData *smd, const ModifierEvalContext *ctx, Scene *scene, Object *ob, Mesh *mesh, const MDeformVert *dvert, int defgrp_index, float(*vertexCos)[3], int numVerts)
static Array< float3 > shrinkwrap_calc_subdivided_positions(Mesh *mesh, const int subdivision_level)
@ MOD_SHRINKWRAP_INVERT_VGROUP
@ MOD_SHRINKWRAP_PROJECT_ALLOW_POS_DIR
@ MOD_SHRINKWRAP_CULL_TARGET_BACKFACE
@ MOD_SHRINKWRAP_PROJECT_ALLOW_NEG_DIR
@ MOD_SHRINKWRAP_CULL_TARGET_FRONTFACE
@ MOD_SHRINKWRAP_INVERT_CULL_TARGET
void BLI_space_transform_apply(const struct SpaceTransform *data, float co[3])
MINLINE float len_v2(const float v[2]) ATTR_WARN_UNUSED_RESULT
VecBase< float, 3 > float3
void interp_v3_v3v3v3(float p[3], const float v1[3], const float v2[3], const float v3[3], const float w[3])
void BLI_space_transform_apply_normal(const struct SpaceTransform *data, float no[3])
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void add_v2_fl(float r[2], float f)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static void shrinkwrap_calc_nearest_vertex_cb_ex(ShrinkwrapCalcData *calc, const bke::bvh::Tree &tree, const int i)
void BLI_space_transform_invert_normal(const struct SpaceTransform *data, float no[3])
bool BKE_shrinkwrap_init_tree(ShrinkwrapTreeData *data, Mesh *mesh, int shrinkType, int shrinkMode, bool force_normals)
Definition shrinkwrap.cc:87
static void shrinkwrap_calc_normal_projection(ShrinkwrapCalcData *calc)
#define fabsf
#define sqrtf
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define TIMEIT_BENCH(expr, id)
Definition shrinkwrap.cc:50
Span< float3 > vert_normals
Definition shrinkwrap.cc:62
const MDeformVert * dvert
Definition shrinkwrap.cc:67
ShrinkwrapTreeData * tree
Definition shrinkwrap.cc:73
ShrinkwrapModifierData * smd
Definition shrinkwrap.cc:57
SpaceTransform local2target
Definition shrinkwrap.cc:72
bke::BVHTreeFromMesh treeData
VArraySpan< bool > sharp_faces
const ShrinkwrapBoundaryData * boundary
const bke::bvh::Tree * vert_tree
BVHTree_NearestPointCallback nearest_callback
BVHTree_RayCastCallback raycast_callback
VtxBoundaryInterpolation vtx_boundary_interpolation
Definition BKE_subdiv.hh:83
FVarLinearInterpolation fvar_linear_interpolation
Definition BKE_subdiv.hh:84