Differential D15346 Diff 53840 source/blender/geometry/intern/fillet_curves.cc

Changeset View

Standalone View

source/blender/geometry/intern/fillet_curves.cc

This file was added.

				/* SPDX-License-Identifier: GPL-2.0-or-later */

				#include "BKE_attribute_math.hh"
				#include "BKE_curves.hh"
				#include "BKE_curves_utils.hh"
				#include "BKE_geometry_set.hh"

				#include "BLI_devirtualize_parameters.hh"
				#include "BLI_math_geom.h"
				#include "BLI_math_rotation.hh"
				#include "BLI_task.hh"

				#include "GEO_fillet_curves.hh"

				namespace blender::geometry {

				/**
				* Return a range used to retrieve values from an array of values stored per point, but with an
				* extra element at the end of each curve. This is useful for offsets within curves, where it is
				* convenient to store the first 0 and have the last offset be the total result curve size.
				*/
				static IndexRange curve_dst_offsets(const IndexRange points, const int curve_index)
				{
				return {curve_index + points.start(), points.size() + 1};
				}

				template<typename T>
				static void threaded_slice_fill(const Span<T> src, const Span<int> offsets, MutableSpan<T> dst)
				{
				threading::parallel_for(src.index_range(), 512, [&](IndexRange range) {
				for (const int i : range) {
				dst.slice(bke::offsets_to_range(offsets, i)).fill(src[i]);
				}
				});
				}

				template<typename T>
				static void duplicate_fillet_point_data(const bke::CurvesGeometry &src_curves,
				const bke::CurvesGeometry &dst_curves,
				const IndexMask curve_selection,
				const Span<int> point_offsets,
				const Span<T> src,
				MutableSpan<T> dst)
				{
				threading::parallel_for(curve_selection.index_range(), 512, [&](IndexRange range) {
				for (const int curve_i : curve_selection.slice(range)) {
				const IndexRange src_points = src_curves.points_for_curve(curve_i);
				const IndexRange dst_points = dst_curves.points_for_curve(curve_i);
				const Span<int> offsets = point_offsets.slice(curve_dst_offsets(src_points, curve_i));
				threaded_slice_fill(src.slice(src_points), offsets, dst.slice(dst_points));
				}
				});
				}

				static void duplicate_fillet_point_data(const bke::CurvesGeometry &src_curves,
				const bke::CurvesGeometry &dst_curves,
				const IndexMask selection,
				const Span<int> point_offsets,
				const GSpan src,
				GMutableSpan dst)
				{
				attribute_math::convert_to_static_type(dst.type(), [&](auto dummy) {
				using T = decltype(dummy);
				duplicate_fillet_point_data(
				src_curves, dst_curves, selection, point_offsets, src.typed<T>(), dst.typed<T>());
				});
				}

				static void calculate_result_offsets(const bke::CurvesGeometry &src_curves,
				const IndexMask selection,
				const Span<IndexRange> unselected_ranges,
				const VArray<float> &radii,
				const VArray<int> &counts,
				const Span<bool> cyclic,
				MutableSpan<int> dst_curve_offsets,
				MutableSpan<int> dst_point_offsets)
				{
				/* Fill the offsets array with the curve point counts, then accumulate them to form offsets. */
				bke::curves::fill_curve_counts(src_curves, unselected_ranges, dst_curve_offsets);
				JacquesLuckeUnsubmitted Not Done Inline Actions typo (`offsets`) JacquesLucke: typo (`offsets`)
				threading::parallel_for(selection.index_range(), 512, [&](IndexRange range) {
				for (const int curve_i : selection.slice(range)) {
				const IndexRange src_points = src_curves.points_for_curve(curve_i);
				const IndexRange offsets_range = curve_dst_offsets(src_points, curve_i);

				MutableSpan<int> point_offsets = dst_point_offsets.slice(offsets_range);
				MutableSpan<int> point_counts = point_offsets.drop_back(1);

				counts.materialize_compressed(src_points, point_counts);
				for (int &count : point_counts) {
				/* Make sure the number of cuts is greater than zero and add one for the existing point. */
				JacquesLuckeUnsubmitted Done Inline Actions Avoid using the `count` variable name twice. JacquesLucke: Avoid using the `count` variable name twice.
				count = std::max(count, 0) + 1;
				}
				if (!cyclic[curve_i]) {
				/* Endpoints on non-cyclic curves cannot be filleted. */
				point_counts.first() = 1;
				point_counts.last() = 1;
				}
				/* Implicitly "deselect" points with zero radius. */
				devirtualize_varray(radii, [&](const auto radii) {
				for (const int i : IndexRange(src_points.size())) {
				if (radii[i] == 0.0f) {
				point_counts[i] = 1;
				}
				}
				});

				bke::curves::accumulate_counts_to_offsets(point_offsets);

				dst_curve_offsets[curve_i] = point_offsets.last();
				}
				});
				bke::curves::accumulate_counts_to_offsets(dst_curve_offsets);
				}

				static void calculate_directions(const Span<float3> positions, MutableSpan<float3> directions)
				{
				for (const int i : positions.index_range().drop_back(1)) {
				directions[i] = math::normalize(positions[i + 1] - positions[i]);
				}
				directions.last() = math::normalize(positions.first() - positions.last());
				}

				static void calculate_angles(const Span<float3> directions, MutableSpan<float> angles)
				{
				angles.first() = M_PI - angle_v3v3(-directions.last(), directions.first());
				for (const int i : directions.index_range().drop_front(1)) {
				angles[i] = M_PI - angle_v3v3(-directions[i - 1], directions[i]);
				}
				}

				/**
				* Find the portion of the previous and next segments used by the current and next point fillets.
				* If more than the total length of the segment would be used, scale the current point's radius
				* just enough to make the two points meet in the middle.
				*/
				static float limit_radius(const float3 &position_prev,
				const float3 &position,
				const float3 &position_next,
				const float angle_prev,
				const float angle,
				const float angle_next,
				const float radius_prev,
				const float radius,
				const float radius_next)
				{
				const float displacement = radius * std::tan(angle / 2.0f);

				const float displacement_prev = radius_prev * std::tan(angle_prev / 2.0f);
				const float segment_length_prev = math::distance(position, position_prev);
				const float total_displacement_prev = displacement_prev + displacement;
				const float factor_prev = std::clamp(segment_length_prev / total_displacement_prev, 0.0f, 1.0f);

				const float displacement_next = radius_next * std::tan(angle_next / 2.0f);
				const float segment_length_next = math::distance(position, position_next);
				const float total_displacement_next = displacement_next + displacement;
				const float factor_next = std::clamp(segment_length_next / total_displacement_next, 0.0f, 1.0f);

				return radius * std::min(factor_prev, factor_next);
				}

				static void limit_radii(const Span<float3> positions,
				const Span<float> angles,
				const Span<float> radii,
				const bool cyclic,
				MutableSpan<float> radii_clamped)
				{
				if (cyclic) {
				/* First point. */
				radii_clamped.first() = limit_radius(positions.last(),
				positions.first(),
				positions[1],
				angles.last(),
				angles.first(),
				angles[1],
				radii.last(),
				radii.first(),
				radii[1]);
				/* All middle points. */
				for (const int i : positions.index_range().drop_back(1).drop_front(1)) {
				const int i_prev = i - 1;
				const int i_next = i + 1;
				radii_clamped[i] = limit_radius(positions[i_prev],
				positions[i],
				positions[i_next],
				angles[i_prev],
				angles[i],
				angles[i_next],
				radii[i_prev],
				radii[i],
				radii[i_next]);
				}
				/* Last point. */
				radii_clamped.last() = limit_radius(positions.last(1),
				positions.last(),
				positions.first(),
				angles.last(1),
				angles.last(),
				angles.first(),
				radii.last(1),
				radii.last(),
				radii.first());
				}
				else {
				const int i_last = positions.index_range().last();
				/* First point. */
				radii_clamped.first() = 0.0f;
				/* All middle points. */
				for (const int i : positions.index_range().drop_back(1).drop_front(1)) {
				const int i_prev = i - 1;
				const int i_next = i + 1;
				/* Use a zero radius for the first and last points, because they don't have fillets.
				* This logic could potentially be unrolled, but it doesn't seem worth it. */
				const float radius_prev = i_prev == 0 ? 0.0f : radii[i_prev];
				const float radius_next = i_next == i_last ? 0.0f : radii[i_next];
				radii_clamped[i] = limit_radius(positions[i_prev],
				positions[i],
				positions[i_next],
				angles[i_prev],
				angles[i],
				angles[i_next],
				radius_prev,
				radii[i],
				radius_next);
				}
				/* Last point. */
				radii_clamped.last() = 0.0f;
				}
				}

				static void calculate_fillet_positions(const Span<float3> src_positions,
				const Span<float> angles,
				const Span<float> radii,
				const Span<float3> directions,
				const Span<int> dst_offsets,
				MutableSpan<float3> dst)
				{
				const int i_src_last = src_positions.index_range().last();
				threading::parallel_for(src_positions.index_range(), 512, [&](IndexRange range) {
				for (const int i_src : range) {
				const IndexRange arc = bke::offsets_to_range(dst_offsets, i_src);
				const float3 &src = src_positions[i_src];
				if (arc.size() == 1) {
				dst[arc.first()] = src;
				continue;
				}

				const int i_src_prev = i_src == 0 ? i_src_last : i_src - 1;
				const float angle = angles[i_src];
				const float radius = radii[i_src];
				const float displacement = radius * std::tan(angle / 2.0f);
				const float3 prev_dir = -directions[i_src_prev];
				const float3 &next_dir = directions[i_src];
				const float3 arc_start = src + prev_dir * displacement;
				const float3 arc_end = src + next_dir * displacement;

				dst[arc.first()] = arc_start;
				dst[arc.last()] = arc_end;

				const IndexRange middle = arc.drop_front(1).drop_back(1);
				if (middle.is_empty()) {
				continue;
				}

				const float3 axis = -math::normalize(math::cross(prev_dir, next_dir));
				const float3 center_direction = math::normalize(math::midpoint(next_dir, prev_dir));
				const float distance_to_center = std::sqrt(pow2f(radius) + pow2f(displacement));
				const float3 center = src + center_direction * distance_to_center;

				/* Rotate each middle fillet point around the center. */
				const float segment_angle = angle / (middle.size() + 1);
				for (const int i : IndexRange(middle.size())) {
				const int point_i = middle[i];
				dst[point_i] = math::rotate_around_axis(arc_start, center, axis, segment_angle * (i + 1));
				}
				}
				});
				}

				/**
				* Set handles for the "Bezier" mode where we rely on setting the inner handles to approximate a
				* circular arc. The outer (previous and next) handles outside the result fillet segment are set
				* to vector handles.
				*/
				static void calculate_bezier_handles_bezier_mode(const Span<float3> src_handles_l,
				const Span<float3> src_handles_r,
				const Span<int8_t> src_types_l,
				const Span<int8_t> src_types_r,
				const Span<float> angles,
				const Span<float> radii,
				const Span<float3> directions,
				const Span<int> dst_offsets,
				const Span<float3> dst_positions,
				MutableSpan<float3> dst_handles_l,
				MutableSpan<float3> dst_handles_r,
				MutableSpan<int8_t> dst_types_l,
				MutableSpan<int8_t> dst_types_r)
				{
				const int i_src_last = src_handles_l.index_range().last();
				const int i_dst_last = dst_positions.index_range().last();
				threading::parallel_for(src_handles_l.index_range(), 512, [&](IndexRange range) {
				for (const int i_src : range) {
				const IndexRange arc = bke::offsets_to_range(dst_offsets, i_src);
				if (arc.size() == 1) {
				dst_handles_l[arc.first()] = src_handles_l[i_src];
				dst_handles_r[arc.first()] = src_handles_r[i_src];
				dst_types_l[arc.first()] = src_types_l[i_src];
				dst_types_r[arc.first()] = src_types_r[i_src];
				continue;
				}
				BLI_assert(arc.size() == 2);
				const int i_dst_a = arc.first();
				const int i_dst_b = arc.last();

				const int i_src_prev = i_src == 0 ? i_src_last : i_src - 1;
				const float angle = angles[i_src];
				const float radius = radii[i_src];
				const float3 prev_dir = -directions[i_src_prev];
				const float3 &next_dir = directions[i_src];

				const float3 &arc_start = dst_positions[arc.first()];
				const float3 &arc_end = dst_positions[arc.last()];

				/* Calculate the point's handles on the outside of the fillet segment,
				* connecting to the next or previous result points. */
				const int i_dst_prev = i_dst_a == 0 ? i_dst_last : i_dst_a - 1;
				const int i_dst_next = i_dst_b == i_dst_last ? 0 : i_dst_b + 1;
				dst_handles_l[i_dst_a] = bke::curves::bezier::calculate_vector_handle(
				dst_positions[i_dst_a], dst_positions[i_dst_prev]);
				dst_handles_r[i_dst_b] = bke::curves::bezier::calculate_vector_handle(
				dst_positions[i_dst_b], dst_positions[i_dst_next]);
				dst_types_l[i_dst_a] = BEZIER_HANDLE_VECTOR;
				dst_types_r[i_dst_b] = BEZIER_HANDLE_VECTOR;

				/* The inner handles are aligned with the aligned with the outer vector
				* handles, but have a specific length to best approximate a circle. */
				const float handle_length = (4.0f / 3.0f) * radius * std::tan(angle / 4.0f);
				dst_handles_r[i_dst_a] = arc_start - prev_dir * handle_length;
				dst_handles_l[i_dst_b] = arc_end - next_dir * handle_length;
				dst_types_r[i_dst_a] = BEZIER_HANDLE_ALIGN;
				dst_types_l[i_dst_b] = BEZIER_HANDLE_ALIGN;
				}
				});
				}

				/**
				* In the poly fillet mode, all the inner handles are set to vector handles, along with the "outer"
				* (previous and next) handles at each fillet.
				*/
				static void calculate_bezier_handles_poly_mode(const Span<float3> src_handles_l,
				const Span<float3> src_handles_r,
				const Span<int8_t> src_types_l,
				const Span<int8_t> src_types_r,
				const Span<int> dst_offsets,
				const Span<float3> dst_positions,
				MutableSpan<float3> dst_handles_l,
				MutableSpan<float3> dst_handles_r,
				MutableSpan<int8_t> dst_types_l,
				MutableSpan<int8_t> dst_types_r)
				{
				const int i_dst_last = dst_positions.index_range().last();
				threading::parallel_for(src_handles_l.index_range(), 512, [&](IndexRange range) {
				for (const int i_src : range) {
				const IndexRange arc = bke::offsets_to_range(dst_offsets, i_src);
				if (arc.size() == 1) {
				dst_handles_l[arc.first()] = src_handles_l[i_src];
				dst_handles_r[arc.first()] = src_handles_r[i_src];
				dst_types_l[arc.first()] = src_types_l[i_src];
				dst_types_r[arc.first()] = src_types_r[i_src];
				continue;
				}

				/* The fillet's next and previous handles are vector handles, as are the inner handles. */
				dst_types_l.slice(arc).fill(BEZIER_HANDLE_VECTOR);
				dst_types_r.slice(arc).fill(BEZIER_HANDLE_VECTOR);

				/* Calculate the point's handles on the outside of the fillet segment. This point
				* won't be selected for a fillet if it is the first or last in a non-cyclic curve. */

				const int i_dst_prev = arc.first() == 0 ? i_dst_last : arc.one_before_start();
				const int i_dst_next = arc.last() == i_dst_last ? 0 : arc.one_after_last();
				dst_handles_l[arc.first()] = bke::curves::bezier::calculate_vector_handle(
				dst_positions[arc.first()], dst_positions[i_dst_prev]);
				dst_handles_r[arc.last()] = bke::curves::bezier::calculate_vector_handle(
				dst_positions[arc.last()], dst_positions[i_dst_next]);

				/* Set the values for the inner handles. */
				const IndexRange middle = arc.drop_front(1).drop_back(1);
				for (const int i : middle) {
				dst_handles_r[i] = bke::curves::bezier::calculate_vector_handle(dst_positions[i],
				dst_positions[i - 1]);
				dst_handles_l[i] = bke::curves::bezier::calculate_vector_handle(dst_positions[i],
				dst_positions[i + 1]);
				}
				}
				});
				}

				static bke::CurvesGeometry fillet_curves(const bke::CurvesGeometry &src_curves,
				const IndexMask curve_selection,
				const VArray<float> &radius_input,
				const VArray<int> &counts,
				const bool limit_radius,
				const bool use_bezier_mode)
				{
				const Vector<IndexRange> unselected_ranges = curve_selection.extract_ranges_invert(
				src_curves.curves_range());

				const Span<float3> positions = src_curves.positions();
				const VArraySpan<bool> cyclic{src_curves.cyclic()};
				const bke::AttributeAccessor src_attributes = src_curves.attributes();

				bke::CurvesGeometry dst_curves = bke::curves::copy_only_curve_domain(src_curves);
				/* Stores the offset of every result point for every original point.
				* The extra length is used in order to store an extra zero for every curve. */
				Array<int> dst_point_offsets(src_curves.points_num() + src_curves.curves_num());
				calculate_result_offsets(src_curves,
				curve_selection,
				unselected_ranges,
				radius_input,
				counts,
				cyclic,
				dst_curves.offsets_for_write(),
				dst_point_offsets);
				const Span<int> point_offsets = dst_point_offsets.as_span();

				dst_curves.resize(dst_curves.offsets().last(), dst_curves.curves_num());
				bke::MutableAttributeAccessor dst_attributes = dst_curves.attributes_for_write();
				MutableSpan<float3> dst_positions = dst_curves.positions_for_write();

				VArraySpan<int8_t> src_types_l;
				VArraySpan<int8_t> src_types_r;
				Span<float3> src_handles_l;
				Span<float3> src_handles_r;
				MutableSpan<int8_t> dst_types_l;
				MutableSpan<int8_t> dst_types_r;
				MutableSpan<float3> dst_handles_l;
				MutableSpan<float3> dst_handles_r;
				if (src_curves.has_curve_with_type(CURVE_TYPE_BEZIER)) {
				src_types_l = src_curves.handle_types_left();
				src_types_r = src_curves.handle_types_right();
				src_handles_l = src_curves.handle_positions_left();
				src_handles_r = src_curves.handle_positions_right();

				dst_types_l = dst_curves.handle_types_left_for_write();
				dst_types_r = dst_curves.handle_types_right_for_write();
				dst_handles_l = dst_curves.handle_positions_left_for_write();
				dst_handles_r = dst_curves.handle_positions_right_for_write();
				}

				threading::parallel_for(curve_selection.index_range(), 512, [&](IndexRange range) {
				Array<float3> directions;
				Array<float> angles;
				Array<float> radii;
				Array<float> input_radii_buffer;

				for (const int curve_i : curve_selection.slice(range)) {
				const IndexRange src_points = src_curves.points_for_curve(curve_i);
				const Span<int> offsets = point_offsets.slice(curve_dst_offsets(src_points, curve_i));
				const IndexRange dst_points = dst_curves.points_for_curve(curve_i);
				const Span<float3> src_positions = positions.slice(src_points);

				directions.reinitialize(src_points.size());
				calculate_directions(src_positions, directions);

				angles.reinitialize(src_points.size());
				calculate_angles(directions, angles);

				radii.reinitialize(src_points.size());
				if (limit_radius) {
				input_radii_buffer.reinitialize(src_points.size());
				radius_input.materialize_compressed(src_points, input_radii_buffer);
				limit_radii(src_positions, angles, input_radii_buffer, cyclic[curve_i], radii);
				}
				else {
				radius_input.materialize_compressed(src_points, radii);
				}

				calculate_fillet_positions(positions.slice(src_points),
				angles,
				radii,
				directions,
				offsets,
				dst_positions.slice(dst_points));

				if (src_curves.has_curve_with_type(CURVE_TYPE_BEZIER)) {
				if (use_bezier_mode) {
				calculate_bezier_handles_bezier_mode(src_handles_l.slice(src_points),
				src_handles_r.slice(src_points),
				src_types_l.slice(src_points),
				src_types_r.slice(src_points),
				angles,
				radii,
				directions,
				offsets,
				dst_positions.slice(dst_points),
				dst_handles_l.slice(dst_points),
				dst_handles_r.slice(dst_points),
				dst_types_l.slice(dst_points),
				dst_types_r.slice(dst_points));
				}
				else {
				calculate_bezier_handles_poly_mode(src_handles_l.slice(src_points),
				src_handles_r.slice(src_points),
				src_types_l.slice(src_points),
				src_types_r.slice(src_points),
				offsets,
				dst_positions.slice(dst_points),
				dst_handles_l.slice(dst_points),
				dst_handles_r.slice(dst_points),
				JacquesLuckeUnsubmitted Done Inline Actions Redundant check of `use_bezier_mode`. JacquesLucke: Redundant check of `use_bezier_mode`.
				HooglyBooglyAuthorUnsubmitted Done Inline Actions Good catch. I ended up deduplicating the Bezier and Poly loops, this area is simpler now. HooglyBoogly: Good catch. I ended up deduplicating the Bezier and Poly loops, this area is simpler now.
				dst_types_l.slice(dst_points),
				dst_types_r.slice(dst_points));
				}
				}
				}
				});

				for (auto &attribute : bke::retrieve_attributes_for_transfer(
				src_attributes,
				dst_attributes,
				ATTR_DOMAIN_MASK_POINT,
				{"position", "handle_type_left", "handle_type_right", "handle_right", "handle_left"})) {
				duplicate_fillet_point_data(
				src_curves, dst_curves, curve_selection, point_offsets, attribute.src, attribute.dst.span);
				attribute.dst.finish();
				}

				if (!unselected_ranges.is_empty()) {
				for (auto &attribute : bke::retrieve_attributes_for_transfer(
				src_attributes, dst_attributes, ATTR_DOMAIN_MASK_POINT)) {
				bke::curves::copy_point_data(
				src_curves, dst_curves, unselected_ranges, attribute.src, attribute.dst.span);
				attribute.dst.finish();
				}
				}

				return dst_curves;
				}

				bke::CurvesGeometry fillet_curves_poly(const bke::CurvesGeometry &src_curves,
				const IndexMask curve_selection,
				const VArray<float> &radius,
				const VArray<int> &count,
				const bool limit_radius)
				{
				return fillet_curves(src_curves, curve_selection, radius, count, limit_radius, false);
				}

				bke::CurvesGeometry fillet_curves_bezier(const bke::CurvesGeometry &src_curves,
				const IndexMask curve_selection,
				const VArray<float> &radius,
				const bool limit_radius)
				{
				return fillet_curves(src_curves,
				curve_selection,
				radius,
				VArray<int>::ForSingle(1, src_curves.points_num()),
				limit_radius,
				true);
				}

				} // namespace blender::geometry