blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 746 Projects 19 Wiki Activity

Bezier Spline: Add a more generalized insertion utility 

This logic is from the curve sundivide node, used to add points with
proper handles in between two existing points. However, the same logic
is used for trimming of Bezier splines, and possibly interactive point
insertion in the future, so it's helpful as a general utility.

The logic is converted to depend on a bezier spline instead of being
static. A temporary segment spline can be used for the latter use case.
This commit is contained in:
Hans Goudey 2021-07-14 15:13:17 -04:00
parent 2829caa9f8
commit 093074aefe
3 changed files with 84 additions and 44 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

12
source/blender/blenkernel/BKE_spline.hh
View File

@ -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;

40
source/blender/blenkernel/intern/spline_bezier.cc
View File

@ -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,

76
source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc
View File

@ -115,38 +115,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
@ -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;
}
}