Blender V5.3
simplify_curves.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2024 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "BLI_array_utils.hh"
10#include "BLI_stack.hh"
11
12#include "BKE_curves_utils.hh"
13
15
16namespace blender::geometry {
17
30template<typename T>
32 const Span<T> attribute_data,
33 const int64_t first_index,
34 const int64_t last_index,
35 const int64_t index)
36{
37 const float3 ray_dir = positions[last_index] - positions[first_index];
38 float lambda = 0.0f;
39 if (!math::is_zero(ray_dir)) {
40 lambda = math::dot(ray_dir, positions[index] - positions[first_index]) /
41 math::dot(ray_dir, ray_dir);
42 }
43 const T &from = attribute_data[first_index];
44 const T &to = attribute_data[last_index];
45 const T &value = attribute_data[index];
46 const T &interpolated = math::interpolate(from, to, lambda);
47 return math::distance(value, interpolated);
48}
49
53template<typename T>
54static void ramer_douglas_peucker(const IndexRange range,
55 const Span<float3> positions,
56 const float epsilon,
57 const Span<T> attribute_data,
58 MutableSpan<bool> points_to_delete)
59{
60 /* Mark all points to be kept. */
61 points_to_delete.slice(range).fill(false);
62
64 stack.push(range);
65 while (!stack.is_empty()) {
66 const IndexRange sub_range = stack.pop();
67 /* Skip ranges with less than 3 points. All points are kept. */
68 if (sub_range.size() < 3) {
69 continue;
70 }
71 const IndexRange inside_range = sub_range.drop_front(1).drop_back(1);
72 /* Compute the maximum distance and the corresponding index. */
73 float max_dist = -1.0f;
74 int max_index = -1;
75 for (const int64_t index : inside_range) {
76 const float dist = perpendicular_distance(
77 positions, attribute_data, sub_range.first(), sub_range.last(), index);
78 if (dist > max_dist) {
79 max_dist = dist;
80 max_index = index - sub_range.first();
81 }
82 }
83
84 if (max_dist > epsilon) {
85 /* Found point outside the epsilon-sized strip. The point at `max_index` will be kept, repeat
86 * the search on the left & right side. */
87 stack.push(sub_range.slice(0, max_index + 1));
88 stack.push(sub_range.slice(max_index, sub_range.size() - max_index));
89 }
90 else {
91 /* Points in `sub_range` are inside the epsilon-sized strip. Mark them to be deleted. */
92 points_to_delete.slice(inside_range).fill(true);
93 }
94 }
95}
96
97template<typename T>
98static void curve_simplify(const Span<float3> positions,
99 const bool cyclic,
100 const float epsilon,
101 const Span<T> attribute_data,
102 MutableSpan<bool> points_to_delete)
103{
104 const Vector<IndexRange> selection_ranges = array_utils::find_all_ranges(
105 points_to_delete.as_span(), true);
107 selection_ranges.index_range(), 512, [&](const IndexRange range_of_ranges) {
108 for (const IndexRange range : selection_ranges.as_span().slice(range_of_ranges)) {
109 ramer_douglas_peucker(range, positions, epsilon, attribute_data, points_to_delete);
110 }
111 });
112
113 /* For cyclic curves, handle the last segment separately. */
114 const int points_num = positions.size();
115 if (cyclic && points_num > 2) {
116 const float dist = perpendicular_distance(
117 positions, attribute_data, points_num - 2, 0, points_num - 1);
118 if (dist <= epsilon) {
119 points_to_delete[points_num - 1] = true;
120 }
121 }
122}
123
124void curve_simplify(const Span<float3> positions,
125 const bool cyclic,
126 const float epsilon,
127 const GSpan attribute_data,
128 MutableSpan<bool> points_to_delete)
129
130{
131 attribute_data.type().to_static_type<float, float2, float3>([&]<typename T>() {
132 curve_simplify(positions, cyclic, epsilon, attribute_data.typed<T>(), points_to_delete);
133 });
134}
135
137 const IndexMask &curves_selection,
138 const OffsetIndices<int> points_by_curve,
139 const VArray<bool> &cyclic,
140 const float epsilon,
141 const GSpan attribute_data,
142 IndexMaskMemory &memory)
143{
144 Array<bool> points_to_delete(positions.size(), false);
145 if (epsilon <= 0.0f) {
146 return IndexMask::from_bools(points_to_delete, memory);
147 }
149 points_by_curve, curves_selection, true, points_to_delete.as_mutable_span());
150 curves_selection.foreach_index(
151 [&](const int64_t curve_i) {
152 const IndexRange points = points_by_curve[curve_i];
153 attribute_data.type().to_static_type<float, float2, float3>([&]<typename T>() {
154 curve_simplify(positions.slice(points),
155 cyclic[curve_i],
156 epsilon,
157 attribute_data.typed<T>().slice(points),
158 points_to_delete.as_mutable_span().slice(points));
159 });
160 },
162 return IndexMask::from_bools(points_to_delete, memory);
163}
164
165} // namespace blender::geometry
Low-level operations for curves.
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
void to_static_type(Fn &&fn) const
Span< T > typed() const
const CPPType & type() const
static IndexMask from_bools(Span< bool > bools, LinearAllocator<> &memory)
constexpr int64_t first() const
constexpr IndexRange drop_back(int64_t n) const
constexpr int64_t last(const int64_t n=0) const
constexpr int64_t size() const
constexpr IndexRange slice(int64_t start, int64_t size) const
constexpr IndexRange drop_front(int64_t n) const
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr Span< T > as_span() const
Definition BLI_span.hh:667
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
bool is_empty() const
Definition BLI_stack.hh:310
void push(const T &value)
Definition BLI_stack.hh:215
IndexRange index_range() const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
#define T
Vector< IndexRange > find_all_ranges(const Span< T > span, const T &value)
void fill_points(OffsetIndices< int > points_by_curve, const IndexMask &curve_selection, GPointer value, GMutableSpan dst)
constexpr ParallelGrainSize grain_size(int grain_size)
float perpendicular_distance(const Span< float3 > positions, const Span< T > attribute_data, const int64_t first_index, const int64_t last_index, const int64_t index)
static void ramer_douglas_peucker(const IndexRange range, const Span< float3 > positions, const float epsilon, const Span< T > attribute_data, MutableSpan< bool > points_to_delete)
IndexMask simplify_curve_attribute(const Span< float3 > positions, const IndexMask &curves_selection, const OffsetIndices< int > points_by_curve, const VArray< bool > &cyclic, float epsilon, GSpan attribute_data, IndexMaskMemory &memory)
void curve_simplify(const Span< float3 > positions, const bool cyclic, const float epsilon, const GSpan attribute_data, MutableSpan< bool > points_to_delete)
T distance(const T &a, const T &b)
T dot(const QuaternionBase< T > &a, const QuaternionBase< T > &b)
bool is_zero(const T &a)
T interpolate(const T &a, const T &b, const FactorT &t)
void parallel_for(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
__int64 int64_t
Definition BKE_text.h:90
VecBase< float, 2 > float2
VecBase< float, 3 > float3
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float