Blender V5.3
curve_constraints.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "BLI_math_matrix.hh"
10#include "BLI_task.hh"
11
12#include "DNA_mesh_types.h"
13
15
16#include "BKE_bvh.hh"
17
24
26
28 const Span<float3> positions,
29 const IndexMask &curve_selection,
30 MutableSpan<float> r_segment_lengths)
31{
32 BLI_assert(r_segment_lengths.size() == points_by_curve.total_size());
33
34 curve_selection.foreach_segment(
35 [&](const IndexMaskSegment segment) {
36 for (const int curve_i : segment) {
37 const IndexRange points = points_by_curve[curve_i].drop_back(1);
38 for (const int point_i : points) {
39 const float3 &p1 = positions[point_i];
40 const float3 &p2 = positions[point_i + 1];
41 const float length = math::distance(p1, p2);
42 r_segment_lengths[point_i] = length;
43 }
44 }
45 },
47}
48
50 const IndexMask &curve_selection,
51 const Span<float> segment_lenghts,
52 MutableSpan<float3> positions)
53{
54 BLI_assert(segment_lenghts.size() == points_by_curve.total_size());
55
56 curve_selection.foreach_segment(
57 [&](const IndexMaskSegment segment) {
58 for (const int curve_i : segment) {
59 const IndexRange points = points_by_curve[curve_i].drop_back(1);
60 for (const int point_i : points) {
61 const float3 &p1 = positions[point_i];
62 float3 &p2 = positions[point_i + 1];
63 const float3 direction = math::normalize(p2 - p1);
64 const float goal_length = segment_lenghts[point_i];
65 p2 = p1 + direction * goal_length;
66 }
67 }
68 },
70}
71
73 const IndexMask &curve_selection,
74 const Span<float> segment_lengths_cu,
75 const Span<float3> start_positions_cu,
76 const Mesh &surface,
77 const bke::CurvesSurfaceTransforms &transforms,
78 MutableSpan<float3> positions_cu,
79 const float surface_collision_distance)
80{
81 solve_length_constraints(points_by_curve, curve_selection, segment_lengths_cu, positions_cu);
82
83 const bke::bvh::Tree &surface_bvh = surface.bvh_tris();
84
85 const int max_collisions = 5;
86
87 curve_selection.foreach_segment(
88 [&](const IndexMaskSegment segment) {
89 for (const int curve_i : segment) {
90 const IndexRange points = points_by_curve[curve_i];
91
92 /* Sometimes not all collisions can be handled. This happens relatively rarely, but if it
93 * happens it's better to just not to move the curve instead of going into the surface.
94 */
95 bool revert_curve = false;
96 for (const int point_i : points.drop_front(1)) {
97 const float goal_segment_length_cu = segment_lengths_cu[point_i - 1];
98 const float3 &prev_pos_cu = positions_cu[point_i - 1];
99 const float3 &start_pos_cu = start_positions_cu[point_i];
100
101 int used_iterations = 0;
102 for ([[maybe_unused]] const int iteration : IndexRange(max_collisions)) {
103 used_iterations++;
104 const float3 &old_pos_cu = positions_cu[point_i];
105 if (start_pos_cu == old_pos_cu) {
106 /* The point did not move, done. */
107 break;
108 }
109
110 /* Check if the point moved through a surface. */
111 const float3 start_pos_su = math::transform_point(transforms.curves_to_surface,
112 start_pos_cu);
113 const float3 old_pos_su = math::transform_point(transforms.curves_to_surface,
114 old_pos_cu);
115 const float3 pos_diff_su = old_pos_su - start_pos_su;
116 float max_ray_length_su;
117 const float3 ray_direction_su = math::normalize_and_get_length(pos_diff_su,
118 max_ray_length_su);
119
120 const bke::bvh::Ray ray(
121 start_pos_su, ray_direction_su, max_ray_length_su + surface_collision_distance);
122
123 const std::optional<bke::bvh::RayHit> hit = surface_bvh.ray_intersect(ray);
124 if (!hit) {
125 break;
126 }
127 const float3 hit_pos_su = ray.origin + ray.direction * hit->distance;
128 const float3 hit_normal_su = math::normalize(hit->normal);
129 if (math::dot(hit_normal_su, ray_direction_su) > 0.0f) {
130 /* Moving from the inside to the outside is ok. */
131 break;
132 }
133
134 /* The point was moved through a surface. Now put it back on the correct side of the
135 * surface and slide it on the surface to keep the length the same. */
136
137 const float3 hit_pos_cu = math::transform_point(transforms.surface_to_curves,
138 hit_pos_su);
139 const float3 hit_normal_cu = math::normalize(
140 math::transform_direction(transforms.surface_to_curves_normal, hit_normal_su));
141
142 /* Slide on a plane that is slightly above the surface. */
143 const float3 plane_pos_cu = hit_pos_cu + hit_normal_cu * surface_collision_distance;
144 const float3 plane_normal_cu = hit_normal_cu;
145
146 /* Decompose the current segment into the part normal and tangent to the collision
147 * surface. */
148 const float3 collided_segment_cu = plane_pos_cu - prev_pos_cu;
149 const float3 slide_normal_cu = plane_normal_cu *
150 math::dot(collided_segment_cu, plane_normal_cu);
151 const float3 slide_direction_cu = collided_segment_cu - slide_normal_cu;
152
153 float slide_direction_length_cu;
154 const float3 normalized_slide_direction_cu = math::normalize_and_get_length(
155 slide_direction_cu, slide_direction_length_cu);
156 const float slide_normal_length_sq_cu = math::length_squared(slide_normal_cu);
157
158 if (pow2f(goal_segment_length_cu) > slide_normal_length_sq_cu) {
159 /* Use Pythagorean theorem to determine how far to slide. */
160 const float slide_distance_cu = std::sqrt(pow2f(goal_segment_length_cu) -
161 slide_normal_length_sq_cu) -
162 slide_direction_length_cu;
163 positions_cu[point_i] = plane_pos_cu +
164 normalized_slide_direction_cu * slide_distance_cu;
165 }
166 else {
167 /* Minimum distance is larger than allowed segment length.
168 * The unilateral collision constraint is satisfied by just clamping segment
169 * length. */
170 positions_cu[point_i] = prev_pos_cu + math::normalize(old_pos_su - prev_pos_cu) *
171 goal_segment_length_cu;
172 }
173 }
174 if (used_iterations == max_collisions) {
175 revert_curve = true;
176 break;
177 }
178 }
179 if (revert_curve) {
180 positions_cu.slice(points).copy_from(start_positions_cu.slice(points));
181 }
182 }
183 },
185}
186
187} // namespace blender::geometry::curve_constraints
constexpr IndexRange()=default
constexpr IndexRange drop_front(int64_t n) const
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
constexpr Span slice(int64_t start, int64_t size) const
Definition BLI_span.hh:141
constexpr int64_t size() const
Definition BLI_span.hh:256
std::optional< RayHit > ray_intersect(const Ray &ray) const
Definition bvh.cc:439
void foreach_segment(Fn &&fn, Mode mode=exec_mode::serial) const
float length(VecOp< float, D >) RET
constexpr ParallelGrainSize grain_size(int grain_size)
void solve_length_and_collision_constraints(OffsetIndices< int > points_by_curve, const IndexMask &curve_selection, Span< float > segment_lengths, Span< float3 > start_positions, const Mesh &surface, const bke::CurvesSurfaceTransforms &transforms, MutableSpan< float3 > positions, const float surface_collision_distance)
void solve_length_constraints(OffsetIndices< int > points_by_curve, const IndexMask &curve_selection, Span< float > segment_lenghts, MutableSpan< float3 > positions)
void compute_segment_lengths(OffsetIndices< int > points_by_curve, Span< float3 > positions, const IndexMask &curve_selection, MutableSpan< float > r_segment_lengths)
T length_squared(const VecBase< T, Size > &a)
T distance(const T &a, const T &b)
QuaternionBase< T > normalize_and_get_length(const QuaternionBase< T > &q, T &out_length)
T dot(const QuaternionBase< T > &a, const QuaternionBase< T > &b)
MatBase< T, NumCol, NumRow > normalize(const MatBase< T, NumCol, NumRow > &a)
VecBase< T, 3 > transform_direction(const MatBase< T, 3, 3 > &mat, const VecBase< T, 3 > &direction)
VecBase< T, 3 > transform_point(const CartesianBasis &basis, const VecBase< T, 3 > &v)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float pow2f(float x)
VecBase< float, 3 > float3