/* * 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_set.hh" #include "BLI_task.hh" #include "DNA_mesh_types.h" #include "DNA_meshdata_types.h" #include "BKE_attribute_access.hh" #include "BKE_attribute_math.hh" #include "BKE_geometry_set.hh" #include "BKE_spline.hh" #include "GEO_mesh_to_curve.hh" namespace blender::geometry { template static void copy_attribute_to_points(const VArray &source_data, Span map, MutableSpan 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> point_to_vert_maps) { MutableSpan splines = curve.splines(); Set source_attribute_ids = mesh_component.attribute_ids(); /* Copy builtin control point attributes. */ if (source_attribute_ids.contains("tilt")) { const VArray tilt_attribute = mesh_component.attribute_get_for_read( "tilt", ATTR_DOMAIN_POINT, 0.0f); threading::parallel_for(splines.index_range(), 256, [&](IndexRange range) { for (const int i : range) { copy_attribute_to_points( tilt_attribute, point_to_vert_maps[i], splines[i]->tilts()); } }); source_attribute_ids.remove_contained("tilt"); } if (source_attribute_ids.contains("radius")) { const VArray radius_attribute = mesh_component.attribute_get_for_read( "radius", ATTR_DOMAIN_POINT, 1.0f); threading::parallel_for(splines.index_range(), 256, [&](IndexRange range) { for (const int i : range) { copy_attribute_to_points( radius_attribute, point_to_vert_maps[i], splines[i]->radii()); } }); source_attribute_ids.remove_contained("radius"); } for (const bke::AttributeIDRef &attribute_id : source_attribute_ids) { /* Don't copy attributes that are built-in on meshes but not on curves. */ if (mesh_component.attribute_is_builtin(attribute_id)) { continue; } if (!attribute_id.should_be_kept()) { continue; } const fn::GVArray mesh_attribute = mesh_component.attribute_try_get_for_read( attribute_id, 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()); threading::parallel_for(splines.index_range(), 128, [&](IndexRange range) { for (const int i : range) { /* Create attribute on the spline points. */ splines[i]->attributes.create(attribute_id, data_type); std::optional spline_attribute = splines[i]->attributes.get_for_write( attribute_id); 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( mesh_attribute.typed(), point_to_vert_maps[i], spline_attribute->typed()); }); } }); } curve.assert_valid_point_attributes(); } struct CurveFromEdgesOutput { std::unique_ptr curve; Vector> point_to_vert_maps; }; static CurveFromEdgesOutput edges_to_curve(Span verts, Span> edges) { std::unique_ptr curve = std::make_unique(); Vector> point_to_vert_maps; /* Compute the number of edges connecting to each vertex. */ Array neighbor_count(verts.size(), 0); for (const std::pair &edge : edges) { neighbor_count[edge.first]++; neighbor_count[edge.second]++; } /* Compute an offset into the array of neighbor edges based on the counts. */ Array 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 used_slots(verts.size(), 0); /* Calculate the indices of each vertex's neighboring edges. */ Array 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 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 spline = std::make_unique(); Vector 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 spline = std::make_unique(); Vector 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> get_selected_edges(const Mesh &mesh, const IndexMask selection) { Vector> selected_edges; for (const int i : selection) { selected_edges.append({mesh.medge[i].v1, mesh.medge[i].v2}); } return selected_edges; } /** * Convert the mesh into one or many poly splines. Since splines cannot have branches, * intersections of more than three edges will become breaks in splines. Attributes that * are not built-in on meshes and not curves are transferred to the result curve. */ std::unique_ptr mesh_to_curve_convert(const MeshComponent &mesh_component, const IndexMask selection) { const Mesh &mesh = *mesh_component.get_for_read(); Vector> selected_edges = get_selected_edges(*mesh_component.get_for_read(), selection); CurveFromEdgesOutput output = edges_to_curve({mesh.mvert, mesh.totvert}, selected_edges); copy_attributes_to_points(*output.curve, mesh_component, output.point_to_vert_maps); return std::move(output.curve); } } // namespace blender::geometry