50# define TIMEIT_BENCH(expr, id) (expr)
54#define OUT_OF_MEMORY() ((void)printf("Shrinkwrap: Out of memory\n"))
93 if (
mesh ==
nullptr) {
102 if (
mesh->verts_num <= 0) {
109 data->corner_edges =
mesh->corner_edges();
110 data->vert_normals =
mesh->vert_normals();
115 data->vert_tree = &
mesh->bvh_verts();
119 if (
mesh->faces_num <= 0) {
123 data->treeData =
mesh->bvh_corner_tris();
126 if (
data->bvh ==
nullptr) {
131 data->face_normals =
mesh->face_normals();
133 data->corner_normals =
mesh->corner_normals();
152 const float edge_dir[3],
169 status[
index] = (status[
index] == 0) ? side : -1;
182 for (
const int edge : corner_edges) {
183 if (edge_mode[edge] < 2) {
191 int num_boundary_edges = 0;
193 if (edge_mode[i] == 1) {
194 edge_is_boundary[i].set();
195 num_boundary_edges++;
200 if (num_boundary_edges == 0) {
214 edges, corner_verts, corner_edges, corner_tris[i]);
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();
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;
235 int boundary_verts_num = 0;
237 vert_boundary_id[i] = (vert_boundary_id[i] != 0) ? boundary_verts_num++ : -1;
245 if (edge_is_boundary[i]) {
246 const int2 &edge = edges[i];
249 sub_v3_v3v3(dir, positions[edge[1]], positions[edge[0]]);
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);
260 int bidx = vert_boundary_id[i];
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);
284 mesh.runtime->shrinkwrap_boundary_cache.ensure(
286 return mesh.runtime->shrinkwrap_boundary_cache.data();
306 if (weight == 0.0f) {
319 const std::optional<bke::bvh::ClosestPointResult> nearest = tree.
closest_point(tmp_co);
327 const float dist =
sqrtf(dist_sq);
328 weight *= (dist - calc->
keepDist) / dist;
332 tmp_co = nearest->position;
343 for (const int64_t i : range) {
344 shrinkwrap_calc_nearest_vertex_cb_ex(calc, tree, int(i));
361 float tmp_co[3], tmp_no[3];
362 const float *co, *no;
366 memcpy(&hit_tmp, hit,
sizeof(hit_tmp));
378#ifdef USE_DIST_CORRECT
392 if (hit_tmp.
index != -1) {
411#ifdef USE_DIST_CORRECT
418 memcpy(hit, &hit_tmp,
sizeof(hit_tmp));
426 const float *proj_axis,
435 const float *tmp_co, *tmp_no;
439 if (weight == 0.0f) {
505 if (proj_limit_squared != 0.0f) {
511 if (hit->
index != -1) {
542 float proj_axis[3] = {0.0f, 0.0f, 0.0f};
547 Mesh *auxMesh =
nullptr;
598 aux_tree = &aux_tree_stack;
609 for (
const int64_t i : range) {
653 const float w[3] = {
x[0],
x[1], 1.0f -
x[0] -
x[1]};
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]);
692 const float epsilon = 1e-5f;
694 const float dir_epsilon = 0.5f;
695 bool fixed =
false, locked =
false;
700 float sum =
x[0] +
x[1];
703 if (sum + sstep > 1.0f) {
704 float ldist = 1.0f - sum;
707 if (ldist < epsilon *
float(
M_SQRT2)) {
711 if (step_len > epsilon && sstep > step_len * dir_epsilon *
float(
M_SQRT2)) {
717 fixed = locked =
true;
727 for (
int i = 0; i < 2; i++) {
728 if (
step[i] >
x[i]) {
730 if (
x[i] < epsilon) {
734 if (step_len > epsilon && (locked ||
step[i] > step_len * dir_epsilon)) {
760 const float vtri_no[3][3],
761 const float point_co[3],
762 const float hit_co[3],
768 float dist =
sqrtf(hit_dist_sq);
771 float epsilon = magnitude_estimate * 1.0e-6f;
779 x[2] = (
dot_v3v3(tmp, r_hit_no) < 0) ? -dist : dist;
794#ifdef TRACE_TARGET_PROJECT
795 const bool trace =
true;
797 const bool trace =
false;
823 const float hit_co[3],
824 const float hit_no[3])
828 if (dist_sq < nearest->dist_sq) {
829#ifdef TRACE_TARGET_PROJECT
831 "#=#=#> %d (%.3f,%.3f,%.3f) %g < %g\n",
index,
UNPACK3(hit_co), dist_sq, nearest->
dist_sq);
853 const float *vedge_co[2] = {
data->vert_positions[edge[0]],
data->vert_positions[edge[1]]};
855#ifdef TRACE_TARGET_PROJECT
856 printf(
"EDGE %d (%.3f,%.3f,%.3f) (%.3f,%.3f,%.3f)\n",
864 const int bid1 = vert_boundary_id[edge[0]], bid2 = vert_boundary_id[edge[1]];
866 if (bid1 < 0 || bid2 < 0) {
872 float vedge_dir[2][3], dir[3];
874 copy_v3_v3(vedge_dir[0], boundary_verts[bid1].normal_plane);
875 copy_v3_v3(vedge_dir[1], boundary_verts[bid2].normal_plane);
879 if (
dot_v3v3(boundary_verts[bid1].direction, dir) < 0) {
882 if (
dot_v3v3(boundary_verts[bid2].direction, dir) < 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);
894 const float a = d0v1 - d0v0 + d1v0 - d1v1;
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;
901 const float epsilon = 1e-6f;
902 const float sdet =
sqrtf(det);
903 float hit_co[3], hit_no[3];
905 for (
int i = (det > 0 ? 2 : 0); i >= 0; i -= 2) {
906 float x = (-
b +
float(i - 1) * sdet) / (2.0f * a);
908 if (
x >= -epsilon &&
x <= 1.0f + epsilon) {
911 float vedge_no[2][3];
934 const int tri_verts[3] = {
935 data->corner_verts[tri[0]],
936 data->corner_verts[tri[1]],
937 data->corner_verts[tri[2]],
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]],
944 float raw_hit_co[3], hit_co[3], hit_no[3], dist_sq, vtri_no[3][3];
950#ifdef TRACE_TARGET_PROJECT
951 printf(
"TRIANGLE %d (%.3f,%.3f,%.3f) (%.3f,%.3f,%.3f) (%.3f,%.3f,%.3f) %g %g\n",
960 if (dist_sq >= nearest->
dist_sq) {
981 for (
int i = 0; i < 3; i++) {
982 if (edges[i] >= 0 && is_boundary[edges[i]]) {
1008#ifdef TRACE_TARGET_PROJECT
1009 printf(
"\n====== TARGET PROJECT START ======\n");
1015#ifdef TRACE_TARGET_PROJECT
1016 printf(
"====== TARGET PROJECT END: %d %g ======\n\n", nearest->
index, nearest->
dist_sq);
1019 if (nearest->
index < 0) {
1044 if (weight == 0.0f) {
1062 if (nearest->
index != -1) {
1065 nearest->
index = -1;
1079 if (nearest->
index != -1) {
1099 const float hit_co[3],
1100 const float hit_no[3],
1105 const int face_i = tree->
mesh->corner_tri_faces()[corner_tri_idx];
1109 const int vert_indices[3] = {treeData->
corner_verts[tri[0]],
1112 float w[3], no[3][3], tmp_co[3];
1165 const float point_co[3],
1166 const float hit_co[3],
1167 const float hit_no[3],
1175 float dist =
len_v3(delta);
1179 if (forcesnap || goal_dist > 0) {
1180 madd_v3_v3v3fl(r_point_co, hit_co, hit_no, goal_dist * forcesign);
1190 if (forcesign == 0.0f) {
1195 if (forcesnap || dsign * dist * forcesign < goal_dist) {
1201 if (dist < dist_epsilon) {
1202#ifdef TRACE_TARGET_PROJECT
1203 printf(
"zero_factor %g = %g / %g\n", dist / dist_epsilon, dist, dist_epsilon);
1209 madd_v3_v3v3fl(r_point_co, hit_co, delta, goal_dist * forcesign);
1221 const float hit_co[3],
1222 const float hit_no[3],
1224 const float point_co[3],
1225 float r_point_co[3])
1232 if (goal_dist != 0) {
1249 if (goal_dist != 0) {
1259 if (goal_dist != 0) {
1269 printf(
"Unknown Shrinkwrap surface snap mode: %d\n", mode);
1278 BVHTreeNearest nearest{};
1281 for (
const int64_t i : range) {
1296 settings.
level = subdivision_level;
1321 const int defgrp_index,
1322 float (*vertexCos)[3],
1342 calc.
vgroup = defgrp_index;
1345 if (smd->
target !=
nullptr) {
1366 subdivided_positions = shrinkwrap_calc_subdivided_positions(mesh, smd->subsurfLevels);
1367 calc.vert_positions = reinterpret_cast<float (*)[3]>(subdivided_positions.data());
1400 const int defgrp_index,
1421 calc.
vertexCos =
reinterpret_cast<float (*)[3]
>(positions.
data());
1423 calc.
vgroup = defgrp_index;
1431 case MOD_SHRINKWRAP_NEAREST_SURFACE:
1432 case MOD_SHRINKWRAP_TARGET_PROJECT:
1433 TIMEIT_BENCH(shrinkwrap_calc_nearest_surface_point(&calc), gpdeform_surface);
1436 case MOD_SHRINKWRAP_PROJECT:
1437 TIMEIT_BENCH(shrinkwrap_calc_normal_projection(&calc), gpdeform_project);
1440 case MOD_SHRINKWRAP_NEAREST_VERTEX:
1441 TIMEIT_BENCH(shrinkwrap_calc_nearest_vertex(&calc), gpdeform_vertex);
1459 Mesh *src_me = id_cast<Mesh *>(ob_source->
data);
1469 reinterpret_cast<float (*)[3]
>(src_me->vert_positions_for_write().data()),
1471 src_me->tag_positions_changed();
1486 const float projLimitTolerance = 5.0f;
1493 calc.
vertexCos =
reinterpret_cast<float (*)[3]
>(src_me->vert_positions_for_write().
data());
1498 calc.
vert_positions =
reinterpret_cast<float (*)[3]
>(src_me->vert_positions_for_write().
data());
1508 src_me->tag_positions_changed();
#define NULL_ShrinkwrapCalcData
#define BVH_RAYCAST_DIST_MAX
#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.
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
constexpr IndexRange()=default
constexpr int64_t size() const
constexpr T * data() const
Array< int > vert_boundary_id
Array< ShrinkwrapBoundaryVertData > boundary_verts
BitVector tri_has_boundary
BitVector edge_is_boundary
bool has_boundary() const
constexpr const T * data() const
constexpr int64_t size() const
constexpr IndexRange index_range() const
constexpr bool is_empty() const
GAttributeReader lookup(const StringRef name) const
std::optional< ClosestPointResult > closest_point(const float3 &point, float radius=std::numeric_limits< float >::max()) const
constexpr bool is_empty() const
CCL_NAMESPACE_BEGIN struct Options options
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)
@ SUBDIV_VTX_BOUNDARY_EDGE_ONLY
@ SUBDIV_FVAR_LINEAR_INTERPOLATION_CORNERS_AND_JUNCTIONS
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)
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))
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 ¶ms, Object &object, ShrinkwrapTreeData &tree, Span< MDeformVert > dvert, int defgrp_index, MutableSpan< float3 > positions)
@ 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)
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)
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)
static void shrinkwrap_calc_normal_projection(ShrinkwrapCalcData *calc)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define TIMEIT_BENCH(expr, id)
Span< float3 > vert_normals
const MDeformVert * dvert
ShrinkwrapTreeData * tree
ShrinkwrapModifierData * smd
SpaceTransform local2target
float(* vert_positions)[3]
struct Object * auxTarget
bool invert_vertex_weights
Span< float3 > face_normals
Span< float3 > vert_normals
bke::BVHTreeFromMesh treeData
VArraySpan< bool > sharp_faces
Span< float3 > corner_normals
const ShrinkwrapBoundaryData * boundary
const bke::bvh::Tree * vert_tree
const float(* vtri_no)[3]
BVHTree_NearestPointCallback nearest_callback
BVHTree_RayCastCallback raycast_callback
Span< float3 > vert_positions
VtxBoundaryInterpolation vtx_boundary_interpolation
FVarLinearInterpolation fvar_linear_interpolation