Blender V5.3
grease_pencil_fills.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2026 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include "BLI_map.hh"
10#include "BLI_vector.hh"
11#include "BLI_virtual_array.hh"
12
13#include "BKE_curves.hh"
14#include "BKE_curves_utils.hh"
16
18
19std::optional<FillCache> fill_cache_from_fill_ids(const VArray<int> &fill_ids)
20{
21 if (!fill_ids || fill_ids.is_empty()) {
22 return std::nullopt;
23 }
24
25 /* The size of each fill. */
26 Vector<int> fill_sizes;
27 /* Contains the curve indices for each fill. */
28 Vector<Vector<int>> curve_indices_by_fill;
29 /* Maps the fill id to the index in the #curve_indices_by_fill vector. */
30 Map<int, int> fill_indexing;
31
32 for (const int curve : fill_ids.index_range()) {
33 const int fill_id = fill_ids[curve];
34
35 /* Unfilled curves are skipped. */
36 if (fill_id == 0) {
37 continue;
38 }
39
40 /* Try adding new fill id to the map or update existing fill id info. */
41 fill_indexing.add_or_modify(
42 fill_id,
43 [&](int *value) {
44 *value = fill_sizes.size();
45 fill_sizes.append(1);
46 curve_indices_by_fill.append(Vector<int>({curve}));
47 },
48 [&](const int *value) {
49 const int fill_index = *value;
50 fill_sizes[fill_index]++;
51 curve_indices_by_fill[fill_index].append(curve);
52 });
53 }
54
55 if (fill_sizes.is_empty()) {
56 return std::nullopt;
57 }
58
59 fill_sizes.append(0);
61
62 Vector<int> fill_map(fill_offsets.total_size());
63 threading::parallel_for(fill_offsets.index_range(), 4096, [&](const IndexRange range) {
64 for (const int fill_i : range) {
65 const IndexRange fill_range = fill_offsets[fill_i];
66 const Span<int> curve_indices = curve_indices_by_fill[fill_i].as_span();
67 fill_map.as_mutable_span().slice(fill_range).copy_from(curve_indices);
68 }
69 });
70
71 FillCache fill_cache;
72 fill_cache.fill_map = std::move(fill_map);
73 fill_cache.fill_offsets = std::move(fill_sizes);
74
75 return fill_cache;
76}
77
78ShapeData shapes_from_fill_ids(const VArray<int> &fill_ids, const int num_curves)
79{
80 if (!fill_ids || fill_ids.is_empty()) {
81 Vector<int> shape_map(num_curves);
82 Vector<int> shape_offset(num_curves + 1);
83
86
87 ShapeData shape_data;
88 shape_data.shape_map = std::move(shape_map);
89 shape_data.shape_offsets = std::move(shape_offset);
90
91 return shape_data;
92 }
93
94 BLI_assert(fill_ids.size() == num_curves);
95
96 /* The size of each shape. This includes zero fill id shapes (which always have a size of 1). */
97 Vector<int> shape_sizes;
98 /* Maps the non-zero fill id to the index of the shape. */
99 Map<int, int> fill_id_to_shape;
100 /* The fill id of each fill. The fill id zero can appear more than once, others may appear
101 * at most once. */
102 Vector<int> all_fill_ids;
103 /* The index of the curve if the shape is a zero fill. Otherwise -1. */
104 Vector<int> all_zero_fill_curve_indices;
105
106 /* Contains the curve indices for each non-zero fill. */
107 Vector<Vector<int>> curve_indices_by_non_zero_fill;
108 /* Maps the fill id to the index in the #curve_indices_by_non_zero_fill vector. */
109 Map<int, int> non_zero_fill_indexing;
110
111 for (const int curve : IndexRange(num_curves)) {
112 const int fill_id = fill_ids[curve];
113 if (fill_id == 0) {
114 shape_sizes.append(1);
115 all_fill_ids.append(0);
116 all_zero_fill_curve_indices.append(curve);
117 }
118 /* Try adding non zero fill id to the map. */
119 else if (fill_id_to_shape.add(fill_id, shape_sizes.size())) {
120 shape_sizes.append(1);
121 all_fill_ids.append(fill_id);
122 /* Not a zero fill. */
123 all_zero_fill_curve_indices.append(-1);
124 }
125 else {
126 shape_sizes[fill_id_to_shape.lookup(fill_id)]++;
127 }
128
129 /* Keep track of curve indices for non-zero fills. */
130 if (fill_id != 0) {
131 if (non_zero_fill_indexing.add(fill_id, curve_indices_by_non_zero_fill.size())) {
132 curve_indices_by_non_zero_fill.append(Vector<int>({curve}));
133 }
134 else {
135 curve_indices_by_non_zero_fill[non_zero_fill_indexing.lookup(fill_id)].append(curve);
136 }
137 }
138 }
139
140 shape_sizes.append(0);
142
143 Vector<int> shape_map(num_curves);
144 MutableSpan<int> shape_map_span = shape_map.as_mutable_span();
145 threading::parallel_for(shape_offsets.index_range(), 4096, [&](const IndexRange range) {
146 for (const int shape_i : range) {
147 const IndexRange shape_range = shape_offsets[shape_i];
148 const bool is_zero_fill = all_fill_ids[shape_i] == 0;
149 if (is_zero_fill) {
150 const int curve_i = all_zero_fill_curve_indices[shape_i];
151 BLI_assert(shape_range.size() == 1);
152 shape_map_span[shape_range.first()] = curve_i;
153 }
154 else {
155 const int fill_id = all_fill_ids[shape_i];
156 const Span<int> curve_indices =
157 curve_indices_by_non_zero_fill[non_zero_fill_indexing.lookup(fill_id)].as_span();
158 shape_map_span.slice(shape_range).copy_from(curve_indices);
159 }
160 }
161 });
162
163 ShapeData shape_data;
164 shape_data.shape_map = std::move(shape_map);
165 shape_data.shape_offsets = std::move(shape_sizes);
166
167 return shape_data;
168}
169
170static int get_next_available_fill_id_from_max(const int max_fill_id)
171{
172 /* Make sure the fill ID is greater than zero. This avoids the issue of hitting an invalid fill
173 * ID of zero when creating multiple IDs at once. */
174 return max_fill_id <= 0 ? 1 : max_fill_id + 1;
175}
176
178{
179 if (std::optional<int64_t> max_i = array_utils::max_element_index(fill_ids)) {
180 return get_next_available_fill_id_from_max(fill_ids[*max_i]);
181 }
182 return 1;
183}
185{
186 if (std::optional<int64_t> max_i = array_utils::max_element_index(fill_ids)) {
187 return get_next_available_fill_id_from_max(fill_ids[*max_i]);
188 }
189 return 1;
190}
191
193{
194 const int next_fill_id = get_next_available_fill_id(fill_ids);
195 array_utils::fill_index_range(r_new_fill_ids, next_fill_id);
196}
198 const IndexMask &curve_mask,
199 MutableSpan<int> r_new_fill_ids)
200{
201 const int next_fill_id = get_next_available_fill_id(fill_ids);
202 curve_mask.foreach_index(
203 [&](const int index, const int pos) { r_new_fill_ids[index] = next_fill_id + pos; },
205}
206
208 const CurvesGeometry &curves,
209 const AttrDomain domain,
210 IndexMaskMemory &memory)
211{
212 const AttributeAccessor attributes = curves.attributes();
213 const OffsetIndices points_by_curve = curves.points_by_curve();
214 const VArray<int> fill_ids = *attributes.lookup<int>("fill_id", AttrDomain::Curve);
215
216 /* If the attribute does not exist then each curves is its own fill. */
217 if (!fill_ids) {
218 if (domain == AttrDomain::Curve) {
219 return selected_mask;
220 }
221 BLI_assert(domain == AttrDomain::Point);
222
223 const IndexMask selected_curves = curves::point_to_curve_selection(
224 points_by_curve, selected_mask, memory);
225 return curves::curve_to_point_selection(points_by_curve, selected_curves, memory);
226 }
227
228 VectorSet<int> selected_fill_ids;
229 Array<bool> src_selected_curves(curves.curves_num());
230
231 if (domain == AttrDomain::Point) {
232 const IndexMask selected_curves = curves::point_to_curve_selection(
233 points_by_curve, selected_mask, memory);
234
235 selected_curves.foreach_index([&](const int64_t curve_i) {
236 const int fill_id = fill_ids[curve_i];
237 if (fill_id != 0) {
238 selected_fill_ids.add(fill_id);
239 }
240 });
241 selected_curves.to_bools(src_selected_curves);
242 }
243 else {
244 selected_mask.foreach_index([&](const int64_t curve_i) {
245 const int fill_id = fill_ids[curve_i];
246 if (fill_id != 0) {
247 selected_fill_ids.add(fill_id);
248 }
249 });
250 selected_mask.to_bools(src_selected_curves);
251 }
252
253 const IndexMask selected_curves = IndexMask::from_predicate(
254 curves.curves_range(), memory, [&](const int64_t curve_i) {
255 const int fill_id = fill_ids[curve_i];
256 if (fill_id == 0) {
257 return src_selected_curves[curve_i];
258 }
259 return selected_fill_ids.contains(fill_id);
260 });
261
262 if (domain == AttrDomain::Curve) {
263 return selected_curves;
264 }
265 BLI_assert(domain == AttrDomain::Point);
266
267 return curves::curve_to_point_selection(curves.points_by_curve(), selected_curves, memory);
268}
269
271 const GroupedSpan<int> shapes,
272 IndexMaskMemory &memory)
273{
274 const int curves_num = shapes.data.size();
275
276 /* If every shape is just one curve then the sames and curves are the same. */
277 if (shapes.size() == curves_num) {
278 return curve_mask;
279 }
280
281 Array<int> curve_to_shape_map(curves_num);
282 threading::parallel_for(shapes.index_range(), 4096, [&](const IndexRange range) {
283 for (const int shape_i : range) {
284 const Span<int> shape = shapes[shape_i];
285 for (const int curve_i : shape) {
286 curve_to_shape_map[curve_i] = shape_i;
287 }
288 }
289 });
290
291 VectorSet<int> selected_shapes;
292 curve_mask.foreach_index([&](const int curve_i) {
293 const int shape_i = curve_to_shape_map[curve_i];
294 selected_shapes.add(shape_i);
295 });
296
297 return IndexMask::from_indices(selected_shapes.as_span(), memory);
298}
299
300void separate_fill_ids(CurvesGeometry &curves, const IndexMask &strokes_to_keep)
301{
302 IndexMaskMemory memory;
303 const IndexMask strokes_to_change = strokes_to_keep.complement(curves.curves_range(), memory);
304
305 if (strokes_to_change.is_empty() || strokes_to_keep.is_empty()) {
306 return;
307 }
308
309 MutableAttributeAccessor attributes = curves.attributes_for_write();
310 SpanAttributeWriter<int> fill_ids = attributes.lookup_for_write_span<int>("fill_id");
311
312 if (!fill_ids) {
313 return;
314 }
315
316 int max_id = 0;
317 strokes_to_keep.foreach_index(
318 [&](const int curve_i) { max_id = math::max(max_id, fill_ids.span[curve_i]); });
319
320 if (max_id == 0) {
321 fill_ids.finish();
322 return;
323 }
324
325 VectorSet<int> fill_indexing;
326 strokes_to_change.foreach_index(
327 [&](const int curve_i) { fill_indexing.add(fill_ids.span[curve_i]); });
328
329 strokes_to_change.foreach_index(
330 [&](const int curve_i) {
331 if (fill_ids.span[curve_i] == 0) {
332 return;
333 }
334 fill_ids.span[curve_i] = fill_indexing.index_of(fill_ids.span[curve_i]) + max_id + 1;
335 },
337
338 fill_ids.finish();
339}
340
341} // namespace blender::bke::greasepencil
Low-level operations for curves.
Low-level operations for curves.
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
static IndexMask from_indices(Span< T > indices, LinearAllocator<> &memory)
bool add(const Key &key, const Value &value)
Definition BLI_map.hh:295
const Value & lookup(const Key &key) const
Definition BLI_map.hh:545
auto add_or_modify(const Key &key, const CreateValueF &create_value, const ModifyValueF &modify_value) -> decltype(create_value(nullptr))
Definition BLI_map.hh:481
IndexRange index_range() const
bool add(const Key &key)
int64_t index_of(const Key &key) const
bool contains(const Key &key) const
Span< Key > as_span() const
int64_t size() const
void append(const T &value)
bool is_empty() const
MutableSpan< T > as_mutable_span()
GAttributeReader lookup(const StringRef name) const
GSpanAttributeWriter lookup_for_write_span(StringRef name)
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
IndexMask complement(const IndexMask &universe, LinearAllocator<> &memory) const
void to_bools(MutableSpan< bool > r_bools) const
std::optional< int64_t > max_element_index(const Span< T > &span, const int64_t grain_size=8192)
void fill_index_range(MutableSpan< T > span, const T start=0)
IndexMask point_to_curve_selection(OffsetIndices< int > points_by_curve, const IndexMask &point_mask, LinearAllocator<> &memory)
IndexMask curve_to_point_selection(OffsetIndices< int > points_by_curve, const IndexMask &curve_selection, LinearAllocator<> &memory)
IndexMask selected_mask_to_fills(const IndexMask &selected_mask, const CurvesGeometry &curves, AttrDomain selection_domain, IndexMaskMemory &memory)
std::optional< FillCache > fill_cache_from_fill_ids(const VArray< int > &fill_ids)
int get_next_available_fill_id(Span< int > fill_ids)
static int get_next_available_fill_id_from_max(const int max_fill_id)
IndexMask curves_mask_to_shapes(const IndexMask &curve_mask, const GroupedSpan< int > shapes, IndexMaskMemory &memory)
void gather_next_available_fill_ids(const VArray< int > &fill_ids, MutableSpan< int > r_new_fill_ids)
void separate_fill_ids(CurvesGeometry &curves, const IndexMask &strokes_to_keep)
ShapeData shapes_from_fill_ids(const VArray< int > &fill_ids, int curves_num)
constexpr ParallelGrainSize grain_size(int grain_size)
T max(const T &a, const T &b)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
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
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90