diff options
| -rw-r--r-- | source/blender/blenkernel/BKE_spline.hh | 12 | ||||
| -rw-r--r-- | source/blender/blenkernel/intern/spline_bezier.cc | 40 | ||||
| -rw-r--r-- | source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc | 76 |
3 files changed, 84 insertions, 44 deletions
diff --git a/source/blender/blenkernel/BKE_spline.hh b/source/blender/blenkernel/BKE_spline.hh index 1aac2e311e3..f85e62768f7 100644 --- a/source/blender/blenkernel/BKE_spline.hh +++ b/source/blender/blenkernel/BKE_spline.hh @@ -337,6 +337,18 @@ class BezierSpline final : public Spline { blender::MutableSpan<blender::float3> positions) const; bool segment_is_vector(const int start_index) const; + /** See comment and diagram for #calculate_segment_insertion. */ + struct InsertResult { + blender::float3 handle_prev; + blender::float3 left_handle; + blender::float3 position; + blender::float3 right_handle; + blender::float3 handle_next; + }; + InsertResult calculate_segment_insertion(const int index, + const int next_index, + const float parameter); + private: void correct_end_tangents() const final; void copy_settings(Spline &dst) const final; diff --git a/source/blender/blenkernel/intern/spline_bezier.cc b/source/blender/blenkernel/intern/spline_bezier.cc index 02d26ac715b..b6764f65631 100644 --- a/source/blender/blenkernel/intern/spline_bezier.cc +++ b/source/blender/blenkernel/intern/spline_bezier.cc @@ -333,6 +333,46 @@ void BezierSpline::correct_end_tangents() const } } +/** + * De Casteljau Bezier subdivision. + * \param index: The index of the segment's start control point. + * \param next_index: The index of the control point at the end of the segment. Could be 0, + * if the spline is cyclic. + * \param parameter: The factor along the segment, between 0 and 1. Note that this is used + * directly by the calculation, it doesn't correspond to a portion of the evaluated length. + * + * <pre> + * handle_prev handle_next + * x----------------x + * / \ + * / x---O---x \ + * / result \ + * / \ + * O O + * point_prev point_next + * </pre> + */ +BezierSpline::InsertResult BezierSpline::calculate_segment_insertion(const int index, + const int next_index, + const float parameter) +{ + BLI_assert(parameter <= 1.0f && parameter >= 0.0f); + BLI_assert(next_index == 0 || next_index == index + 1); + const float3 &point_prev = positions_[index]; + const float3 &handle_prev = handle_positions_right_[index]; + const float3 &handle_next = handle_positions_left_[next_index]; + const float3 &point_next = positions_[next_index]; + const float3 center_point = float3::interpolate(handle_prev, handle_next, parameter); + + BezierSpline::InsertResult result; + result.handle_prev = float3::interpolate(point_prev, handle_prev, parameter); + result.handle_next = float3::interpolate(handle_next, point_next, parameter); + result.left_handle = float3::interpolate(result.handle_prev, center_point, parameter); + result.right_handle = float3::interpolate(center_point, result.handle_next, parameter); + result.position = float3::interpolate(result.left_handle, result.right_handle, parameter); + return result; +} + static void bezier_forward_difference_3d(const float3 &point_0, const float3 &point_1, const float3 &point_2, diff --git a/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc b/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc index 3de2604cd0a..7908c26e2dc 100644 --- a/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc +++ b/source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc @@ -116,38 +116,6 @@ static void subdivide_attribute(Span<T> src, } /** - * De Casteljau Bezier subdivision. - * - * <pre> - * handle_prev handle_next - * O----------------O - * / \ - * / x---O---x \ - * / new_* \ - * / \ - * O O - * point_prev point_next - * </pre> - */ -static void calculate_new_bezier_point(const float3 &point_prev, - float3 &handle_prev, - float3 &new_left_handle, - float3 &new_position, - float3 &new_right_handle, - float3 &handle_next, - const float3 &point_next, - const float parameter) -{ - const float3 center_point = float3::interpolate(handle_prev, handle_next, parameter); - - handle_prev = float3::interpolate(point_prev, handle_prev, parameter); - handle_next = float3::interpolate(handle_next, point_next, parameter); - new_left_handle = float3::interpolate(handle_prev, center_point, parameter); - new_right_handle = float3::interpolate(center_point, handle_next, parameter); - new_position = float3::interpolate(new_left_handle, new_right_handle, parameter); -} - -/** * In order to generate a Bezier spline with the same shape as the input spline, apply the * De Casteljau algorithm iteratively for the provided number of cuts, constantly updating the * previous result point's right handle and the left handle at the end of the segment. @@ -171,6 +139,10 @@ static void subdivide_bezier_segment(const BezierSpline &src, { const bool is_last_cyclic_segment = index == (src.size() - 1); const int next_index = is_last_cyclic_segment ? 0 : index + 1; + + /* The first point in the segment is always copied. */ + dst_positions[offset] = src_positions[index]; + if (src.segment_is_vector(index)) { if (is_last_cyclic_segment) { dst_type_left.first() = BezierSpline::HandleType::Vector; @@ -178,7 +150,6 @@ static void subdivide_bezier_segment(const BezierSpline &src, dst_type_left.slice(offset + 1, result_size).fill(BezierSpline::HandleType::Vector); dst_type_right.slice(offset, result_size).fill(BezierSpline::HandleType::Vector); - dst_positions[offset] = src_positions[index]; const float factor_delta = 1.0f / result_size; for (const int cut : IndexRange(result_size)) { const float factor = cut * factor_delta; @@ -194,21 +165,38 @@ static void subdivide_bezier_segment(const BezierSpline &src, dst_type_right.slice(offset, result_size).fill(BezierSpline::HandleType::Free); const int i_segment_last = is_last_cyclic_segment ? 0 : offset + result_size; - dst_positions[offset] = src_positions[index]; - dst_handles_right[offset] = src_handles_right[index]; - dst_handles_left[i_segment_last] = src_handles_left[next_index]; + + /* Create a Bezier segment to update iteratively for every subdivision + * and references to the meaningful values for ease of use. */ + BezierSpline temp; + temp.resize(2); + float3 &segment_start = temp.positions().first(); + float3 &segment_end = temp.positions().last(); + float3 &handle_prev = temp.handle_positions_right().first(); + float3 &handle_next = temp.handle_positions_left().last(); + segment_start = src_positions[index]; + segment_end = src_positions[next_index]; + handle_prev = src_handles_right[index]; + handle_next = src_handles_left[next_index]; for (const int cut : IndexRange(result_size - 1)) { const float parameter = 1.0f / (result_size - cut); - calculate_new_bezier_point(dst_positions[offset + cut], - dst_handles_right[offset + cut], - dst_handles_left[offset + cut + 1], - dst_positions[offset + cut + 1], - dst_handles_right[offset + cut + 1], - dst_handles_left[i_segment_last], - src_positions[next_index], - parameter); + const BezierSpline::InsertResult insert = temp.calculate_segment_insertion(0, 1, parameter); + + /* Copy relevant temporary data to the result. */ + dst_handles_right[offset + cut] = insert.handle_prev; + dst_handles_left[offset + cut + 1] = insert.left_handle; + dst_positions[offset + cut + 1] = insert.position; + + /* Update the segment to prepare it for the next subdivision. */ + segment_start = insert.position; + handle_prev = insert.right_handle; + handle_next = insert.handle_next; } + + /* Copy the handles for the last segment from the temporary spline. */ + dst_handles_right[offset + result_size - 1] = handle_prev; + dst_handles_left[i_segment_last] = handle_next; } } |