diff options
author | Hans Goudey <h.goudey@me.com> | 2021-05-28 17:42:22 +0300 |
---|---|---|
committer | Hans Goudey <h.goudey@me.com> | 2021-05-28 17:42:22 +0300 |
commit | 11e32332ddfdcacb7f992d9fb25025b53c5037c1 (patch) | |
tree | be40b4197b601884e24b986432ec31a66f9708dc /source/blender | |
parent | 418888f1c9a3c3ca8facc04d271d48ad37e5f5b2 (diff) |
Geometry Nodes: Add Mesh to Curve Node
This node creates poly curve splines from mesh edges. A selection
attribute input allows only using some of the edges from the mesh.
The node builds cyclic splines from branchless groups of edges where
possible, but when there is a three-way intersection, the spline stops.
The node also transfers all attributes from the mesh to the resulting
control points. In the future we could add a way to limit that to a
subset of the attributes to improve performance.
The algorithm is from Animation Nodes, written by @OmarSquircleArt.
I added the ability to use a selection, attribute transferring, and
used different variable names, etc, but other than that the algorithm
is the same.
Differential Revision: https://developer.blender.org/D11265
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenkernel/BKE_node.h | 1 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/node.cc | 1 | ||||
-rw-r--r-- | source/blender/nodes/CMakeLists.txt | 1 | ||||
-rw-r--r-- | source/blender/nodes/NOD_geometry.h | 1 | ||||
-rw-r--r-- | source/blender/nodes/NOD_static_types.h | 1 | ||||
-rw-r--r-- | source/blender/nodes/geometry/nodes/node_geo_mesh_to_curve.cc | 318 |
6 files changed, 323 insertions, 0 deletions
diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h index 448f4ae48ad..b3247a751bf 100644 --- a/source/blender/blenkernel/BKE_node.h +++ b/source/blender/blenkernel/BKE_node.h @@ -1426,6 +1426,7 @@ int ntreeTexExecTree(struct bNodeTree *ntree, #define GEO_NODE_MATERIAL_ASSIGN 1049 #define GEO_NODE_INPUT_MATERIAL 1050 #define GEO_NODE_MATERIAL_REPLACE 1051 +#define GEO_NODE_MESH_TO_CURVE 1052 /** \} */ diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc index 3377f5c69dc..d0864e85373 100644 --- a/source/blender/blenkernel/intern/node.cc +++ b/source/blender/blenkernel/intern/node.cc @@ -5066,6 +5066,7 @@ static void registerGeometryNodes() register_node_type_geo_mesh_primitive_ico_sphere(); register_node_type_geo_mesh_primitive_line(); register_node_type_geo_mesh_primitive_uv_sphere(); + register_node_type_geo_mesh_to_curve(); register_node_type_geo_object_info(); register_node_type_geo_point_distribute(); register_node_type_geo_point_instance(); diff --git a/source/blender/nodes/CMakeLists.txt b/source/blender/nodes/CMakeLists.txt index 9d21ff19f46..24085b31fc3 100644 --- a/source/blender/nodes/CMakeLists.txt +++ b/source/blender/nodes/CMakeLists.txt @@ -178,6 +178,7 @@ set(SRC geometry/nodes/node_geo_mesh_primitive_ico_sphere.cc geometry/nodes/node_geo_mesh_primitive_line.cc geometry/nodes/node_geo_mesh_primitive_uv_sphere.cc + geometry/nodes/node_geo_mesh_to_curve.cc geometry/nodes/node_geo_object_info.cc geometry/nodes/node_geo_point_distribute.cc geometry/nodes/node_geo_point_instance.cc diff --git a/source/blender/nodes/NOD_geometry.h b/source/blender/nodes/NOD_geometry.h index d2a702c30a6..eadfed26be1 100644 --- a/source/blender/nodes/NOD_geometry.h +++ b/source/blender/nodes/NOD_geometry.h @@ -66,6 +66,7 @@ void register_node_type_geo_mesh_primitive_grid(void); void register_node_type_geo_mesh_primitive_ico_sphere(void); void register_node_type_geo_mesh_primitive_line(void); void register_node_type_geo_mesh_primitive_uv_sphere(void); +void register_node_type_geo_mesh_to_curve(void); void register_node_type_geo_object_info(void); void register_node_type_geo_point_distribute(void); void register_node_type_geo_point_instance(void); diff --git a/source/blender/nodes/NOD_static_types.h b/source/blender/nodes/NOD_static_types.h index ce1813fdac3..ef5f25e7b57 100644 --- a/source/blender/nodes/NOD_static_types.h +++ b/source/blender/nodes/NOD_static_types.h @@ -305,6 +305,7 @@ DefNode(GeometryNode, GEO_NODE_MESH_PRIMITIVE_GRID, 0, "MESH_PRIMITIVE_GRID", Me DefNode(GeometryNode, GEO_NODE_MESH_PRIMITIVE_ICO_SPHERE, 0, "MESH_PRIMITIVE_ICO_SPHERE", MeshIcoSphere, "Ico Sphere", "") DefNode(GeometryNode, GEO_NODE_MESH_PRIMITIVE_LINE, def_geo_mesh_line, "MESH_PRIMITIVE_LINE", MeshLine, "Line", "") DefNode(GeometryNode, GEO_NODE_MESH_PRIMITIVE_UV_SPHERE, 0, "MESH_PRIMITIVE_UV_SPHERE", MeshUVSphere, "UV Sphere", "") +DefNode(GeometryNode, GEO_NODE_MESH_TO_CURVE, 0, "MESH_TO_CURVE", MeshToCurve, "Mesh to Curve", "") DefNode(GeometryNode, GEO_NODE_OBJECT_INFO, def_geo_object_info, "OBJECT_INFO", ObjectInfo, "Object Info", "") DefNode(GeometryNode, GEO_NODE_POINT_DISTRIBUTE, def_geo_point_distribute, "POINT_DISTRIBUTE", PointDistribute, "Point Distribute", "") DefNode(GeometryNode, GEO_NODE_POINT_INSTANCE, def_geo_point_instance, "POINT_INSTANCE", PointInstance, "Point Instance", "") diff --git a/source/blender/nodes/geometry/nodes/node_geo_mesh_to_curve.cc b/source/blender/nodes/geometry/nodes/node_geo_mesh_to_curve.cc new file mode 100644 index 00000000000..b852f929b5f --- /dev/null +++ b/source/blender/nodes/geometry/nodes/node_geo_mesh_to_curve.cc @@ -0,0 +1,318 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#include "BLI_array.hh" +#include "BLI_task.hh" + +#include "DNA_mesh_types.h" +#include "DNA_meshdata_types.h" + +#include "BKE_attribute_math.hh" +#include "BKE_spline.hh" + +#include "node_geometry_util.hh" + +using blender::Array; + +static bNodeSocketTemplate geo_node_mesh_to_curve_in[] = { + {SOCK_GEOMETRY, N_("Mesh")}, + {SOCK_STRING, N_("Selection")}, + {-1, ""}, +}; + +static bNodeSocketTemplate geo_node_mesh_to_curve_out[] = { + {SOCK_GEOMETRY, N_("Curve")}, + {-1, ""}, +}; + +namespace blender::nodes { + +template<typename T> +static void copy_attribute_to_points(const VArray<T> &source_data, + Span<int> map, + MutableSpan<T> dest_data) +{ + for (const int point_index : map.index_range()) { + const int vert_index = map[point_index]; + dest_data[point_index] = source_data[vert_index]; + } +} + +static void copy_attributes_to_points(CurveEval &curve, + const MeshComponent &mesh_component, + Span<Vector<int>> point_to_vert_maps) +{ + MutableSpan<SplinePtr> splines = curve.splines(); + Set<std::string> source_attribute_names = mesh_component.attribute_names(); + + /* Copy builtin control point attributes. */ + if (source_attribute_names.contains_as("tilt")) { + const GVArray_Typed<float> tilt_attribute = mesh_component.attribute_get_for_read<float>( + "tilt", ATTR_DOMAIN_POINT, 0.0f); + parallel_for(splines.index_range(), 256, [&](IndexRange range) { + for (const int i : range) { + copy_attribute_to_points<float>( + *tilt_attribute, point_to_vert_maps[i], splines[i]->tilts()); + } + }); + source_attribute_names.remove_contained_as("tilt"); + } + if (source_attribute_names.contains_as("radius")) { + const GVArray_Typed<float> radius_attribute = mesh_component.attribute_get_for_read<float>( + "radius", ATTR_DOMAIN_POINT, 1.0f); + parallel_for(splines.index_range(), 256, [&](IndexRange range) { + for (const int i : range) { + copy_attribute_to_points<float>( + *radius_attribute, point_to_vert_maps[i], splines[i]->radii()); + } + }); + source_attribute_names.remove_contained_as("radius"); + } + + /* Don't copy other builtin control point attributes. */ + source_attribute_names.remove_as("position"); + + /* Copy dynamic control point attributes. */ + for (const StringRef name : source_attribute_names) { + const GVArrayPtr mesh_attribute = mesh_component.attribute_try_get_for_read(name, + ATTR_DOMAIN_POINT); + /* Some attributes might not exist if they were builtin attribute on domains that don't + * have any elements, i.e. a face attribute on the output of the line primitive node. */ + if (!mesh_attribute) { + continue; + } + + const CustomDataType data_type = bke::cpp_type_to_custom_data_type(mesh_attribute->type()); + + parallel_for(splines.index_range(), 128, [&](IndexRange range) { + for (const int i : range) { + /* Create attribute on the spline points. */ + splines[i]->attributes.create(name, data_type); + std::optional<GMutableSpan> spline_attribute = splines[i]->attributes.get_for_write(name); + BLI_assert(spline_attribute); + + /* Copy attribute based on the map for this spline. */ + attribute_math::convert_to_static_type(mesh_attribute->type(), [&](auto dummy) { + using T = decltype(dummy); + copy_attribute_to_points<T>( + mesh_attribute->typed<T>(), point_to_vert_maps[i], spline_attribute->typed<T>()); + }); + } + }); + } + + curve.assert_valid_point_attributes(); +} + +struct CurveFromEdgesOutput { + std::unique_ptr<CurveEval> curve; + Vector<Vector<int>> point_to_vert_maps; +}; + +static CurveFromEdgesOutput mesh_to_curve(Span<MVert> verts, Span<std::pair<int, int>> edges) +{ + std::unique_ptr<CurveEval> curve = std::make_unique<CurveEval>(); + Vector<Vector<int>> point_to_vert_maps; + + /* Compute the number of edges connecting to each vertex. */ + Array<int> neighbor_count(verts.size(), 0); + for (const std::pair<int, int> &edge : edges) { + neighbor_count[edge.first]++; + neighbor_count[edge.second]++; + } + + /* Compute an offset into the array of neighbor edges based on the counts. */ + Array<int> neighbor_offsets(verts.size()); + int start = 0; + for (const int i : verts.index_range()) { + neighbor_offsets[i] = start; + start += neighbor_count[i]; + } + + /* Use as an index into the "neighbor group" for each vertex. */ + Array<int> used_slots(verts.size(), 0); + /* Calculate the indices of each vertex's neighboring edges. */ + Array<int> neighbors(edges.size() * 2); + for (const int i : edges.index_range()) { + const int v1 = edges[i].first; + const int v2 = edges[i].second; + neighbors[neighbor_offsets[v1] + used_slots[v1]] = v2; + neighbors[neighbor_offsets[v2] + used_slots[v2]] = v1; + used_slots[v1]++; + used_slots[v2]++; + } + + /* Now use the neighbor group offsets calculated above as a count used edges at each vertex. */ + Array<int> unused_edges = std::move(used_slots); + + for (const int start_vert : verts.index_range()) { + /* The vertex will be part of a cyclic spline. */ + if (neighbor_count[start_vert] == 2) { + continue; + } + + /* The vertex has no connected edges, or they were already used. */ + if (unused_edges[start_vert] == 0) { + continue; + } + + for (const int i : IndexRange(neighbor_count[start_vert])) { + int current_vert = start_vert; + int next_vert = neighbors[neighbor_offsets[current_vert] + i]; + + if (unused_edges[next_vert] == 0) { + continue; + } + + std::unique_ptr<PolySpline> spline = std::make_unique<PolySpline>(); + Vector<int> point_to_vert_map; + + spline->add_point(verts[current_vert].co, 1.0f, 0.0f); + point_to_vert_map.append(current_vert); + + /* Follow connected edges until we read a vertex with more than two connected edges. */ + while (true) { + int last_vert = current_vert; + current_vert = next_vert; + + spline->add_point(verts[current_vert].co, 1.0f, 0.0f); + point_to_vert_map.append(current_vert); + unused_edges[current_vert]--; + unused_edges[last_vert]--; + + if (neighbor_count[current_vert] != 2) { + break; + } + + const int offset = neighbor_offsets[current_vert]; + const int next_a = neighbors[offset]; + const int next_b = neighbors[offset + 1]; + next_vert = (last_vert == next_a) ? next_b : next_a; + } + + spline->attributes.reallocate(spline->size()); + curve->add_spline(std::move(spline)); + point_to_vert_maps.append(std::move(point_to_vert_map)); + } + } + + /* All remaining edges are part of cyclic splines (we skipped vertices with two edges before). */ + for (const int start_vert : verts.index_range()) { + if (unused_edges[start_vert] != 2) { + continue; + } + + int current_vert = start_vert; + int next_vert = neighbors[neighbor_offsets[current_vert]]; + + std::unique_ptr<PolySpline> spline = std::make_unique<PolySpline>(); + Vector<int> point_to_vert_map; + spline->set_cyclic(true); + + spline->add_point(verts[current_vert].co, 1.0f, 0.0f); + point_to_vert_map.append(current_vert); + + /* Follow connected edges until we loop back to the start vertex. */ + while (next_vert != start_vert) { + const int last_vert = current_vert; + current_vert = next_vert; + + spline->add_point(verts[current_vert].co, 1.0f, 0.0f); + point_to_vert_map.append(current_vert); + unused_edges[current_vert]--; + unused_edges[last_vert]--; + + const int offset = neighbor_offsets[current_vert]; + const int next_a = neighbors[offset]; + const int next_b = neighbors[offset + 1]; + next_vert = (last_vert == next_a) ? next_b : next_a; + } + + spline->attributes.reallocate(spline->size()); + curve->add_spline(std::move(spline)); + point_to_vert_maps.append(std::move(point_to_vert_map)); + } + + curve->attributes.reallocate(curve->splines().size()); + return {std::move(curve), std::move(point_to_vert_maps)}; +} + +/** + * Get a separate array of the indices for edges in a selection (a boolean attribute). + * This helps to make the above algorithm simpler by removing the need to check for selection + * in many places. + */ +static Vector<std::pair<int, int>> get_selected_edges(GeoNodeExecParams params, + const MeshComponent &component) +{ + const Mesh &mesh = *component.get_for_read(); + const std::string selection_name = params.extract_input<std::string>("Selection"); + if (!selection_name.empty() && !component.attribute_exists(selection_name)) { + params.error_message_add(NodeWarningType::Error, + TIP_("No attribute with name \"") + selection_name + "\""); + } + GVArray_Typed<bool> selection = component.attribute_get_for_read<bool>( + selection_name, ATTR_DOMAIN_EDGE, true); + + Vector<std::pair<int, int>> selected_edges; + for (const int i : IndexRange(mesh.totedge)) { + if (selection[i]) { + selected_edges.append({mesh.medge[i].v1, mesh.medge[i].v2}); + } + } + + return selected_edges; +} + +static void geo_node_mesh_to_curve_exec(GeoNodeExecParams params) +{ + GeometrySet geometry_set = params.extract_input<GeometrySet>("Mesh"); + + geometry_set = bke::geometry_set_realize_instances(geometry_set); + + if (!geometry_set.has_mesh()) { + params.set_output("Curve", GeometrySet()); + return; + } + + const MeshComponent &component = *geometry_set.get_component_for_read<MeshComponent>(); + const Mesh &mesh = *component.get_for_read(); + Span<MVert> verts = Span{mesh.mvert, mesh.totvert}; + Span<MEdge> edges = Span{mesh.medge, mesh.totedge}; + if (edges.size() == 0) { + params.set_output("Curve", GeometrySet()); + return; + } + + Vector<std::pair<int, int>> selected_edges = get_selected_edges(params, component); + + CurveFromEdgesOutput output = mesh_to_curve(verts, selected_edges); + copy_attributes_to_points(*output.curve, component, output.point_to_vert_maps); + + params.set_output("Curve", GeometrySet::create_with_curve(output.curve.release())); +} + +} // namespace blender::nodes + +void register_node_type_geo_mesh_to_curve() +{ + static bNodeType ntype; + + geo_node_type_base(&ntype, GEO_NODE_MESH_TO_CURVE, "Mesh to Curve", NODE_CLASS_GEOMETRY, 0); + node_type_socket_templates(&ntype, geo_node_mesh_to_curve_in, geo_node_mesh_to_curve_out); + ntype.geometry_node_execute = blender::nodes::geo_node_mesh_to_curve_exec; + nodeRegisterType(&ntype); +} |