Blender V5.3
node_geo_curve_fill.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
5#include "BLI_array.hh"
6#include "BLI_array_utils.hh"
7#include "BLI_delaunay_2d.hh"
9
10#include "BKE_curves.hh"
11#include "BKE_grease_pencil.hh"
12#include "BKE_instances.hh"
13#include "BKE_mesh.hh"
14
15#include "BLI_task.hh"
16
19
20#include "node_geometry_util.hh"
21
23
25
26static const EnumPropertyItem mode_items[] = {
27 {GEO_NODE_CURVE_FILL_MODE_TRIANGULATED, "TRIANGLES", 0, N_("Triangles"), ""},
28 {GEO_NODE_CURVE_FILL_MODE_NGONS, "NGONS", 0, N_("N-gons"), ""},
29 {0, nullptr, 0, nullptr, nullptr},
30};
31
32/* See #CDT_output_type in BLI_delaunay_2d.hh for winding rule details. */
35 "EVEN_ODD",
36 0,
37 N_("Even-Odd"),
38 N_("Alternate inside/outside based on crossing count")},
40 "NON_ZERO",
41 0,
42 N_("Non-Zero"),
43 N_("Overlapping curves with the same winding direction are filled as a union")},
44 {0, nullptr, 0, nullptr, nullptr},
45};
46
48{
49 b.add_input<decl::Geometry>("Curve"_ustr)
51 .description(
52 "Curves to fill. All curves are treated as cyclic and projected to the XY plane");
53 b.add_input<decl::Int>("Group ID"_ustr)
54 .evaluated_geometry_field()
55 .hide_value()
56 .description(
57 "An index used to group curves together. Filling is done separately for each group");
58 b.add_input<decl::Menu>("Mode"_ustr)
59 .static_items(mode_items)
61 .optional_label();
62 b.add_input<decl::Menu>("Fill Rule"_ustr)
63 .static_items(fill_rule_items)
65 .optional_label()
66 .description("Rule used to determine which regions are inside or outside");
67 b.add_output<decl::Geometry>("Mesh"_ustr).propagate_all_geometry();
68}
69
70static void node_init(bNodeTree * /*tree*/, bNode *node)
71{
72 /* Still used for forward compatibility. */
73 node->storage = MEM_new<NodeGeometryCurveFill>(__func__);
74}
75
77 MutableSpan<int> face_vert_indices)
78{
79 threading::parallel_for(offsets.index_range(), 1024, [&](const IndexRange range) {
80 for (const int i : range) {
81 array_utils::fill_index_range<int>(face_vert_indices.slice(offsets[i]), offsets[i].start());
82 }
83 });
84}
85
87 const CDT_output_type output_type)
88{
89 const OffsetIndices points_by_curve = curves.evaluated_points_by_curve();
90 const Span<float3> positions = curves.evaluated_positions();
91
92 Array<double2> positions_2d(positions.size());
93 threading::parallel_for(positions.index_range(), 2048, [&](const IndexRange range) {
94 for (const int i : range) {
95 positions_2d[i] = double2(positions[i].x, positions[i].y);
96 }
97 });
98
99 Array<int> face_vert_indices(positions.size());
100 fill_curve_vert_indices(points_by_curve, face_vert_indices);
101
103 input.vert = positions_2d;
104 input.face_offsets = points_by_curve;
105 input.face_vert_indices = face_vert_indices;
107 return delaunay_2d_calc(input, output_type);
108}
109
111 const CDT_output_type output_type,
112 const IndexMask &mask)
113{
114 const OffsetIndices points_by_curve = curves.evaluated_points_by_curve();
115 const Span<float3> positions = curves.evaluated_positions();
116
117 Array<int> offsets_data(mask.size() + 1);
118 const OffsetIndices points_by_curve_masked = offset_indices::gather_selected_offsets(
119 points_by_curve, mask, offsets_data);
120
121 Array<double2> positions_2d(points_by_curve_masked.total_size());
122 mask.foreach_index(
123 [&](const int src_curve, const int dst_curve) {
124 const IndexRange src_points = points_by_curve[src_curve];
125 const IndexRange dst_points = points_by_curve_masked[dst_curve];
126 for (const int i : src_points.index_range()) {
127 const int src = src_points[i];
128 const int dst = dst_points[i];
129 positions_2d[dst] = double2(positions[src].x, positions[src].y);
130 }
131 },
133
134 Array<int> face_vert_indices(positions_2d.size());
135 fill_curve_vert_indices(points_by_curve_masked, face_vert_indices);
136
138 input.vert = positions_2d;
139 input.face_offsets = points_by_curve_masked;
140 input.face_vert_indices = face_vert_indices;
142
143 return delaunay_2d_calc(input, output_type);
144}
145
148 const CDT_output_type output_type,
149 const Field<int> &group_index_field)
150{
151 const bke::GeometryFieldContext field_context{curves, AttrDomain::Curve};
152 fn::FieldEvaluator data_evaluator{field_context, curves.curves_num()};
153 data_evaluator.add(group_index_field);
154 data_evaluator.evaluate();
155 const VArray<int> curve_group_ids = data_evaluator.get_evaluated<int>(0);
156
157 if (curve_group_ids.is_single()) {
158 return {do_cdt(curves, output_type)};
159 }
160
161 IndexMaskMemory mask_memory;
162 const Vector<IndexMask> group_masks = IndexMask::from_group_ids(curve_group_ids, mask_memory);
163 const int groups_num = group_masks.size();
164
165 Array<meshintersect::CDT_result<double>> cdt_results(groups_num);
166
167 /* The grain size should be larger as each group gets smaller. */
168 const int domain_size = curve_group_ids.size();
169 const int avg_group_size = domain_size / groups_num;
170 const int grain_size = std::max(8192 / avg_group_size, 1);
171 threading::parallel_for(IndexRange(groups_num), grain_size, [&](const IndexRange range) {
172 for (const int group_index : range) {
173 const IndexMask &mask = group_masks[group_index];
174 cdt_results[group_index] = do_cdt_with_mask(curves, output_type, mask);
175 }
176 });
177
178 return cdt_results;
179}
180
181/* Converts multiple CDT results into a single Mesh. */
183{
184 /* Converting a single CDT result to a Mesh would be simple because the indices could be re-used.
185 * However, in the general case here we need to combine several CDT results into a single Mesh,
186 * which requires us to map the original indices to a new set of indices.
187 * In order to allow for parallelization when appropriate, this implementation starts by
188 * determining (for each domain) what range of indices in the final mesh data will be used for
189 * each CDT result. The index ranges are represented as offsets, which are referred to as "group
190 * offsets" to distinguish them from the other types of offsets we need to work with here.
191 * Since it's likely that most invocations will only have a single CDT result, it's important
192 * that case is made as optimal as feasible. */
193
194 Array<int> vert_groups_data(results.size() + 1);
195 Array<int> edge_groups_data(results.size() + 1);
196 Array<int> face_groups_data(results.size() + 1);
197 Array<int> loop_groups_data(results.size() + 1);
198 threading::parallel_for(results.index_range(), 1024, [&](const IndexRange results_range) {
199 for (const int i_result : results_range) {
200 const meshintersect::CDT_result<double> &result = results[i_result];
201 vert_groups_data[i_result] = result.vert.size();
202 edge_groups_data[i_result] = result.edge.size();
203 face_groups_data[i_result] = result.face.size();
204 int loop_len = 0;
205 for (const Vector<int> &face : result.face) {
206 loop_len += face.size();
207 }
208 loop_groups_data[i_result] = loop_len;
209 }
210 });
211
212 const OffsetIndices vert_groups = offset_indices::accumulate_counts_to_offsets(vert_groups_data);
213 const OffsetIndices edge_groups = offset_indices::accumulate_counts_to_offsets(edge_groups_data);
214 const OffsetIndices face_groups = offset_indices::accumulate_counts_to_offsets(face_groups_data);
215 const OffsetIndices loop_groups = offset_indices::accumulate_counts_to_offsets(loop_groups_data);
216
217 Mesh *mesh = BKE_mesh_new_nomain(vert_groups.total_size(),
218 edge_groups.total_size(),
219 face_groups.total_size(),
220 loop_groups.total_size());
221
222 MutableSpan<float3> all_positions = mesh->vert_positions_for_write();
223 MutableSpan<int2> all_edges = mesh->edges_for_write();
224 MutableSpan<int> all_face_offsets = mesh->face_offsets_for_write();
225 MutableSpan<int> all_corner_verts = mesh->corner_verts_for_write();
226
227 threading::parallel_for(results.index_range(), 1024, [&](const IndexRange results_range) {
228 for (const int i_result : results_range) {
229 const meshintersect::CDT_result<double> &result = results[i_result];
230 const IndexRange verts_range = vert_groups[i_result];
231 const IndexRange edges_range = edge_groups[i_result];
232 const IndexRange faces_range = face_groups[i_result];
233 const IndexRange loops_range = loop_groups[i_result];
234
235 MutableSpan<float3> positions = all_positions.slice(verts_range);
236 for (const int i : result.vert.index_range()) {
237 positions[i] = float3(float(result.vert[i].x), float(result.vert[i].y), 0.0f);
238 }
239
240 MutableSpan<int2> edges = all_edges.slice(edges_range);
241 for (const int i : result.edge.index_range()) {
242 edges[i] = result.edge[i] + int(verts_range.start());
243 }
244
245 MutableSpan<int> face_offsets = all_face_offsets.slice(faces_range);
246 MutableSpan<int> corner_verts = all_corner_verts.slice(loops_range);
247 int i_face_corner = 0;
248 for (const int i_face : result.face.index_range()) {
249 face_offsets[i_face] = i_face_corner + loops_range.start();
250 for (const int i_corner : result.face[i_face].index_range()) {
251 corner_verts[i_face_corner] = result.face[i_face][i_corner] + verts_range.start();
252 i_face_corner++;
253 }
254 }
255 }
256 });
257
258 /* The delaunay triangulation doesn't seem to return all of the necessary all_edges, even in
259 * triangulation mode. */
260 bke::mesh_calc_edges(*mesh, true, false);
261 bke::mesh_smooth_set(*mesh, false);
262
263 mesh->tag_overlapping_none();
264
265 return mesh;
266}
267
268static void curve_fill_calculate(GeometrySet &geometry_set,
269 const GeometryNodeCurveFillMode mode,
270 const GeometryNodeCurveFillRule fill_rule,
271 const Field<int> &group_index)
272{
273 /* Determine CDT output type based on mode and fill rule. */
274 CDT_output_type output_type;
275 if (mode == GEO_NODE_CURVE_FILL_MODE_NGONS) {
277 switch (fill_rule) {
280 break;
281 }
283 /* Default, already set. */
284 break;
285 }
286 }
287 }
288 else {
289 /* Triangulated mode. */
290 output_type = CDT_INSIDE_WITH_HOLES;
291 switch (fill_rule) {
293 output_type = CDT_INSIDE_WITH_HOLES_NONZERO;
294 break;
295 }
297 /* Default, already set. */
298 break;
299 }
300 }
301 }
302 if (geometry_set.has_curves()) {
303 const Curves &curves_id = *geometry_set.get_curves();
304 const bke::CurvesGeometry &curves = curves_id.geometry.wrap();
305 if (curves.curves_num() > 0) {
307 curves, output_type, group_index);
308 Mesh *mesh = cdts_to_mesh(results);
309 geometry_set.replace_mesh(mesh);
310 }
311 geometry_set.replace_curves(nullptr);
312 }
313
314 if (geometry_set.has_grease_pencil()) {
315 using namespace blender::bke::greasepencil;
316 const GreasePencil &grease_pencil = *geometry_set.get_grease_pencil();
317 Vector<Mesh *> mesh_by_layer(grease_pencil.layers().size(), nullptr);
318 for (const int layer_index : grease_pencil.layers().index_range()) {
319 const Drawing *drawing = grease_pencil.get_eval_drawing(grease_pencil.layer(layer_index));
320 if (drawing == nullptr) {
321 continue;
322 }
323 const bke::CurvesGeometry &src_curves = drawing->strokes();
324 if (src_curves.is_empty()) {
325 continue;
326 }
328 src_curves, output_type, group_index);
329 mesh_by_layer[layer_index] = cdts_to_mesh(results);
330 }
331 if (!mesh_by_layer.is_empty()) {
332 auto instances = std::make_unique<bke::Instances>(mesh_by_layer.size());
333 MutableSpan<int> handles = instances->reference_handles_for_write();
334 instances->transforms_for_write().fill(float4x4::identity());
335 for (const int i : mesh_by_layer.index_range()) {
336 Mesh *mesh = mesh_by_layer[i];
337 if (!mesh) {
338 /* Add an empty reference so the number of layers and instances match.
339 * This makes it easy to reconstruct the layers afterwards and keep their attributes.
340 * Although in this particular case we don't propagate the attributes. */
341 handles[i] = instances->add_reference(bke::InstanceReference());
342 continue;
343 }
345 handles[i] = instances->add_reference(bke::InstanceReference{temp_set});
346 }
347 auto &dst_component = geometry_set.get_component_for_write<InstancesComponent>();
349 {GeometrySet::from_instances(dst_component.release()),
350 GeometrySet::from_instances(std::move(instances))},
351 {});
352 dst_component.replace(new_instances.get_component_for_write<InstancesComponent>().release());
353 }
354 geometry_set.replace_grease_pencil(nullptr);
355 }
356}
357
359{
360 GeometrySet geometry_set = params.extract_input<GeometrySet>("Curve"_ustr);
361 Field<int> group_index = params.extract_input<Field<int>>("Group ID"_ustr);
363 "Mode"_ustr);
364 const auto fill_rule = params.extract_input<GeometryNodeCurveFillRule>("Fill Rule"_ustr);
365
367 curve_fill_calculate(geometry, mode, fill_rule, group_index);
368 });
369
370 params.set_output("Mesh"_ustr, std::move(geometry_set));
371}
372
373static void node_register()
374{
375 static bke::bNodeType ntype;
376 geo_node_type_base(&ntype, "GeometryNodeFillCurve"_ustr, GEO_NODE_FILL_CURVE);
377 ntype.ui_name = "Fill Curve";
378 ntype.ui_description =
379 "Generate a mesh on the XY plane with faces on the inside of input curves";
380 ntype.enum_name_legacy = "FILL_CURVE";
382 ntype.initfunc = node_init;
384 ntype, "NodeGeometryCurveFill", node_free_standard_storage, node_copy_standard_storage);
385 ntype.declare = node_declare;
388}
389NOD_REGISTER_NODE(node_register)
390
391} // namespace blender::nodes::node_geo_curve_fill_cc
Low-level operations for curves.
Low-level operations for grease pencil.
#define NODE_STORAGE_FUNCS(StorageT)
Definition BKE_node.hh:1353
#define NODE_CLASS_GEOMETRY
Definition BKE_node.hh:492
#define GEO_NODE_FILL_CURVE
#define NOD_REGISTER_NODE(REGISTER_FUNC)
int64_t size() const
Definition BLI_array.hh:267
static Vector< IndexMask, 4 > from_group_ids(const VArray< int > &group_ids, LinearAllocator<> &memory)
constexpr IndexRange index_range() const
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
int64_t size() const
bool is_empty() const
IndexRange index_range() const
const bke::CurvesGeometry & strokes() const
int add(GField field, GVArray *varray_ptr)
const GVArray & get_evaluated(const int field_index) const
T extract_input(const UString identifier)
void set_output(const UString identifier, T &&value)
void node_register_type(bNodeType &ntype)
Definition node.cc:2920
void mesh_smooth_set(Mesh &mesh, bool use_smooth, bool keep_sharp_edges=false)
void mesh_calc_edges(Mesh &mesh, bool keep_existing_edges, bool select_new_edges)
void node_type_storage(bNodeType &ntype, std::optional< StringRefNull > storagename, void(*freefunc)(bNode *node), void(*copyfunc)(bNodeTree *dest_ntree, bNode *dest_node, const bNode *src_node))
Definition node.cc:6166
constexpr ParallelGrainSize grain_size(int grain_size)
bke::GeometrySet join_geometries(Span< bke::GeometrySet > geometries, const bke::AttributeFilter &attribute_filter, const std::optional< Span< bke::GeometryComponent::Type > > &component_types_to_join=std::nullopt, bool allow_merging_instance_references=true)
void foreach_real_geometry(bke::GeometrySet &geometry, FunctionRef< void(bke::GeometrySet &geometry_set)> fn)
static void node_init(bNodeTree *, bNode *node)
static void fill_curve_vert_indices(const OffsetIndices< int > offsets, MutableSpan< int > face_vert_indices)
static void node_geo_exec(GeoNodeExecParams params)
static void node_declare(NodeDeclarationBuilder &b)
static const EnumPropertyItem mode_items[]
static Array< meshintersect::CDT_result< double > > do_group_aware_cdt(const bke::CurvesGeometry &curves, const CDT_output_type output_type, const Field< int > &group_index_field)
static meshintersect::CDT_result< double > do_cdt_with_mask(const bke::CurvesGeometry &curves, const CDT_output_type output_type, const IndexMask &mask)
static void curve_fill_calculate(GeometrySet &geometry_set, const GeometryNodeCurveFillMode mode, const GeometryNodeCurveFillRule fill_rule, const Field< int > &group_index)
static Mesh * cdts_to_mesh(const Span< meshintersect::CDT_result< double > > results)
static const EnumPropertyItem fill_rule_items[]
static meshintersect::CDT_result< double > do_cdt(const bke::CurvesGeometry &curves, const CDT_output_type output_type)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
OffsetIndices< int > gather_selected_offsets(OffsetIndices< int > src_offsets, const IndexMask &selection, int start_offset, MutableSpan< int > dst_offsets)
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
@ GEO_NODE_CURVE_FILL_RULE_EVEN_ODD
@ GEO_NODE_CURVE_FILL_RULE_NON_ZERO
@ CDT_INSIDE_WITH_HOLES
@ CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES_NONZERO
@ CDT_INSIDE_WITH_HOLES_NONZERO
@ CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES
VecBase< double, 2 > double2
@ GEO_NODE_CURVE_FILL_MODE_TRIANGULATED
@ GEO_NODE_CURVE_FILL_MODE_NGONS
Mesh * BKE_mesh_new_nomain(int verts_num, int edges_num, int faces_num, int corners_num)
void node_copy_standard_storage(bNodeTree *, bNode *dest_node, const bNode *src_node)
Definition node_util.cc:57
void node_free_standard_storage(bNode *node)
Definition node_util.cc:45
void geo_node_type_base(bke::bNodeType *ntype, UString idname, const std::optional< int16_t > legacy_type)
GeometryComponent & get_component_for_write(GeometryComponent::Type component_type)
const GreasePencil * get_grease_pencil() const
const Curves * get_curves() const
void replace_curves(Curves *curves, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
void replace_mesh(Mesh *mesh, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
void replace_grease_pencil(GreasePencil *grease_pencil, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
Defines a node type.
Definition BKE_node.hh:265
std::string ui_description
Definition BKE_node.hh:271
NodeGeometryExecFunction geometry_node_execute
Definition BKE_node.hh:385
void(*) initfunc(bNodeTree *ntree, bNode *node)
Definition BKE_node.hh:320
const char * enum_name_legacy
Definition BKE_node.hh:274
NodeDeclareFunction declare
Definition BKE_node.hh:393
static GeometrySet from_mesh(Mesh *mesh, GeometryOwnershipType ownership=GeometryOwnershipType::Owned)
static GeometrySet from_instances(std::unique_ptr< Instances > instances)
#define N_(msgid)