[Bf-blender-cvs] [9435ee8c651] master: Curves: Port subdivide node to the new data-block
Hans Goudey
noreply at git.blender.org
Tue Jul 5 23:18:02 CEST 2022
Commit: 9435ee8c65193e3d4af8f1ac5b07b7884cf62bd5
Author: Hans Goudey
Date: Tue Jul 5 16:08:37 2022 -0500
Branches: master
https://developer.blender.org/rB9435ee8c65193e3d4af8f1ac5b07b7884cf62bd5
Curves: Port subdivide node to the new data-block
This commit moves the subdivide curve node implementation to the
geometry module, changes it to work on the new curves data-block,
and adds support for Catmull Rom curves. Internally I also added
support for a curve domain selection. That isn't used, but it's
nice to have the option anyway.
Users should notice better performance as well, since we can avoid
many small allocations, and there is no conversion to and from the
old curve type.
The code uses a similar structure to the resample node (60a6fbf5b599)
and the set type node (9e393fc2f125). The resample curves node can be
restructured to be more similar to this soon though.
Differential Revision: https://developer.blender.org/D15334
===================================================================
M source/blender/blenkernel/BKE_curves.hh
M source/blender/blenkernel/intern/curve_bezier.cc
M source/blender/blenkernel/intern/curve_catmull_rom.cc
M source/blender/blenlib/BLI_index_range.hh
M source/blender/geometry/CMakeLists.txt
A source/blender/geometry/GEO_subdivide_curves.hh
A source/blender/geometry/intern/subdivide_curves.cc
M source/blender/nodes/geometry/nodes/node_geo_curve_subdivide.cc
===================================================================
diff --git a/source/blender/blenkernel/BKE_curves.hh b/source/blender/blenkernel/BKE_curves.hh
index 767936e2a26..3e00dc78b74 100644
--- a/source/blender/blenkernel/BKE_curves.hh
+++ b/source/blender/blenkernel/BKE_curves.hh
@@ -483,6 +483,8 @@ namespace bezier {
* Return true if the handles that make up a segment both have a vector type. Vector segments for
* Bezier curves have special behavior because they aren't divided into many evaluated points.
*/
+bool segment_is_vector(const HandleType left, const HandleType right);
+bool segment_is_vector(const int8_t left, const int8_t right);
bool segment_is_vector(Span<int8_t> handle_types_left,
Span<int8_t> handle_types_right,
int segment_index);
@@ -515,6 +517,35 @@ void calculate_evaluated_offsets(Span<int8_t> handle_types_left,
int resolution,
MutableSpan<int> evaluated_offsets);
+/** See #insert. */
+struct Insertion {
+ float3 handle_prev;
+ float3 left_handle;
+ float3 position;
+ float3 right_handle;
+ float3 handle_next;
+};
+
+/**
+ * Compute the Bezier segment insertion for the given parameter on the segment, returning
+ * the position and handles of the new point and the updated existing handle positions.
+ * <pre>
+ * handle_prev handle_next
+ * x-----------------x
+ * / \
+ * / x---O---x \
+ * / result \
+ * / \
+ * O O
+ * point_prev point_next
+ * </pre>
+ */
+Insertion insert(const float3 &point_prev,
+ const float3 &handle_prev,
+ const float3 &handle_next,
+ const float3 &point_next,
+ float parameter);
+
/**
* Calculate the automatically defined positions for a vector handle (#BEZIER_HANDLE_VECTOR). While
* this can be calculated automatically with #calculate_auto_handles, when more context is
@@ -607,6 +638,15 @@ int calculate_evaluated_num(int points_num, bool cyclic, int resolution);
*/
void interpolate_to_evaluated(GSpan src, bool cyclic, int resolution, GMutableSpan dst);
+/**
+ * Evaluate the Catmull Rom curve. The size of each segment and its offset in the #dst span
+ * is encoded in #evaluated_offsets, with the same method as #CurvesGeometry::offsets().
+ */
+void interpolate_to_evaluated(const GSpan src,
+ const bool cyclic,
+ const Span<int> evaluated_offsets,
+ GMutableSpan dst);
+
} // namespace catmull_rom
/** \} */
@@ -827,6 +867,16 @@ inline bool point_is_sharp(const Span<int8_t> handle_types_left,
ELEM(handle_types_right[index], BEZIER_HANDLE_VECTOR, BEZIER_HANDLE_FREE);
}
+inline bool segment_is_vector(const HandleType left, const HandleType right)
+{
+ return left == BEZIER_HANDLE_VECTOR && right == BEZIER_HANDLE_VECTOR;
+}
+
+inline bool segment_is_vector(const int8_t left, const int8_t right)
+{
+ return segment_is_vector(HandleType(left), HandleType(right));
+}
+
inline float3 calculate_vector_handle(const float3 &point, const float3 &next_point)
{
return math::interpolate(point, next_point, 1.0f / 3.0f);
diff --git a/source/blender/blenkernel/intern/curve_bezier.cc b/source/blender/blenkernel/intern/curve_bezier.cc
index 1d6ee4938b5..59b09384698 100644
--- a/source/blender/blenkernel/intern/curve_bezier.cc
+++ b/source/blender/blenkernel/intern/curve_bezier.cc
@@ -16,15 +16,14 @@ bool segment_is_vector(const Span<int8_t> handle_types_left,
const int segment_index)
{
BLI_assert(handle_types_left.index_range().drop_back(1).contains(segment_index));
- return handle_types_right[segment_index] == BEZIER_HANDLE_VECTOR &&
- handle_types_left[segment_index + 1] == BEZIER_HANDLE_VECTOR;
+ return segment_is_vector(handle_types_right[segment_index],
+ handle_types_left[segment_index + 1]);
}
bool last_cyclic_segment_is_vector(const Span<int8_t> handle_types_left,
const Span<int8_t> handle_types_right)
{
- return handle_types_right.last() == BEZIER_HANDLE_VECTOR &&
- handle_types_left.first() == BEZIER_HANDLE_VECTOR;
+ return segment_is_vector(handle_types_right.last(), handle_types_left.first());
}
void calculate_evaluated_offsets(const Span<int8_t> handle_types_left,
@@ -59,6 +58,26 @@ void calculate_evaluated_offsets(const Span<int8_t> handle_types_left,
evaluated_offsets.last() = offset;
}
+Insertion insert(const float3 &point_prev,
+ const float3 &handle_prev,
+ const float3 &handle_next,
+ const float3 &point_next,
+ float parameter)
+{
+ /* De Casteljau Bezier subdivision. */
+ BLI_assert(parameter <= 1.0f && parameter >= 0.0f);
+
+ const float3 center_point = math::interpolate(handle_prev, handle_next, parameter);
+
+ Insertion result;
+ result.handle_prev = math::interpolate(point_prev, handle_prev, parameter);
+ result.handle_next = math::interpolate(handle_next, point_next, parameter);
+ result.left_handle = math::interpolate(result.handle_prev, center_point, parameter);
+ result.right_handle = math::interpolate(center_point, result.handle_next, parameter);
+ result.position = math::interpolate(result.left_handle, result.right_handle, parameter);
+ return result;
+}
+
static float3 calculate_aligned_handle(const float3 &position,
const float3 &other_handle,
const float3 &aligned_handle)
diff --git a/source/blender/blenkernel/intern/curve_catmull_rom.cc b/source/blender/blenkernel/intern/curve_catmull_rom.cc
index 1875c7b366a..952d59edcf9 100644
--- a/source/blender/blenkernel/intern/curve_catmull_rom.cc
+++ b/source/blender/blenkernel/intern/curve_catmull_rom.cc
@@ -39,15 +39,18 @@ static void evaluate_segment(const T &a, const T &b, const T &c, const T &d, Mut
}
}
-template<typename T>
+/**
+ * \param range_fn: Returns an index range describing where in the #dst span each segment should be
+ * evaluated to, and how many points to add to it. This is used to avoid the need to allocate an
+ * actual offsets array in typical evaluation use cases where the resolution is per-curve.
+ */
+template<typename T, typename RangeForSegmentFn>
static void interpolate_to_evaluated(const Span<T> src,
const bool cyclic,
- const int resolution,
+ const RangeForSegmentFn &range_fn,
MutableSpan<T> dst)
{
- BLI_assert(dst.size() == calculate_evaluated_num(src.size(), cyclic, resolution));
-
/* - First deal with one and two point curves need special attention.
* - Then evaluate the first and last segment(s) whose control points need to wrap around
* to the other side of the source array.
@@ -57,11 +60,14 @@ static void interpolate_to_evaluated(const Span<T> src,
dst.first() = src.first();
return;
}
+
+ const IndexRange first = range_fn(0);
+
if (src.size() == 2) {
- evaluate_segment(src.first(), src.first(), src.last(), src.last(), dst.take_front(resolution));
+ evaluate_segment(src.first(), src.first(), src.last(), src.last(), dst.slice(first));
if (cyclic) {
- evaluate_segment(
- src.last(), src.last(), src.first(), src.first(), dst.take_back(resolution));
+ const IndexRange last = range_fn(1);
+ evaluate_segment(src.last(), src.last(), src.first(), src.first(), dst.slice(last));
}
else {
dst.last() = src.last();
@@ -69,39 +75,65 @@ static void interpolate_to_evaluated(const Span<T> src,
return;
}
+ const IndexRange second_to_last = range_fn(src.index_range().last(1));
+ const IndexRange last = range_fn(src.index_range().last());
if (cyclic) {
- /* The first segment. */
- evaluate_segment(src.last(), src[0], src[1], src[2], dst.take_front(resolution));
- /* The second-to-last segment. */
- evaluate_segment(src.last(2),
- src.last(1),
- src.last(),
- src.first(),
- dst.take_back(resolution * 2).drop_back(resolution));
- /* The last segment. */
- evaluate_segment(src.last(1), src.last(), src[0], src[1], dst.take_back(resolution));
+ evaluate_segment(src.last(), src[0], src[1], src[2], dst.slice(first));
+ evaluate_segment(src.last(2), src.last(1), src.last(), src.first(), dst.slice(second_to_last));
+ evaluate_segment(src.last(1), src.last(), src[0], src[1], dst.slice(last));
}
else {
- /* The first segment. */
- evaluate_segment(src[0], src[0], src[1], src[2], dst.take_front(resolution));
- /* The last segment. */
- evaluate_segment(
- src.last(2), src.last(1), src.last(), src.last(), dst.drop_back(1).take_back(resolution));
- /* The final point of the last segment. */
+ evaluate_segment(src[0], src[0], src[1], src[2], dst.slice(first));
+ evaluate_segment(src.last(2), src.last(1), src.last(), src.last(), dst.slice(second_to_last));
+ /* For non-cyclic curves, the last segment should always just have a single point. We could
+ * assert that the size of the provided range is 1 here, but that would require specializing
+ * the #range_fn implementation for the last point, which may have a performance cost. */
dst.last() = src.last();
}
/* Evaluate every segment that isn't the first or last. */
- const int grain_size = std::max(512 / resolution, 1);
const IndexRange inner_range = src.index_range().drop_back(2).drop_front(1);
- threading::parallel_for(inner_range, grain_size, [&](IndexRange range) {
+ threading::parallel_for(inner_range, 512, [&](IndexRange range) {
for (const int i : range) {
- const IndexRange segment_range(resolution * i, resolution);
- evaluate_segment(src[i - 1], src[i], src[i + 1], src[i + 2], dst.slice(segment_range));
+ const Inde
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list