Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/geometry
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/geometry')
-rw-r--r--source/blender/geometry/CMakeLists.txt42
-rw-r--r--source/blender/geometry/GEO_mesh_to_curve.hh35
-rw-r--r--source/blender/geometry/intern/mesh_to_curve_convert.cc283
3 files changed, 360 insertions, 0 deletions
diff --git a/source/blender/geometry/CMakeLists.txt b/source/blender/geometry/CMakeLists.txt
new file mode 100644
index 00000000000..4e7e0b1ea58
--- /dev/null
+++ b/source/blender/geometry/CMakeLists.txt
@@ -0,0 +1,42 @@
+# ***** BEGIN GPL LICENSE BLOCK *****
+#
+# 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.
+#
+# The Original Code is Copyright (C) 2006, Blender Foundation
+# All rights reserved.
+
+set(INC
+ .
+ ../blenkernel
+ ../blenlib
+ ../blentranslation
+ ../functions
+ ../makesdna
+ ../makesrna
+ ../../../intern/guardedalloc
+ ${CMAKE_BINARY_DIR}/source/blender/makesdna/intern
+)
+
+set(SRC
+ intern/mesh_to_curve_convert.cc
+ GEO_mesh_to_curve.hh
+)
+
+set(LIB
+ bf_blenkernel
+ bf_blenlib
+)
+
+blender_add_lib(bf_geometry "${SRC}" "${INC}" "${INC_SYS}" "${LIB}")
diff --git a/source/blender/geometry/GEO_mesh_to_curve.hh b/source/blender/geometry/GEO_mesh_to_curve.hh
new file mode 100644
index 00000000000..66459ab79a9
--- /dev/null
+++ b/source/blender/geometry/GEO_mesh_to_curve.hh
@@ -0,0 +1,35 @@
+/*
+ * 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_index_mask.hh"
+
+#include "BKE_spline.hh"
+
+#pragma once
+
+struct Mesh;
+class MeshComponent;
+
+/** \file
+ * \ingroup geo
+ */
+
+namespace blender::geometry {
+
+std::unique_ptr<CurveEval> mesh_to_curve_convert(const MeshComponent &mesh_component,
+ const IndexMask selection);
+
+} // namespace blender::geometry
diff --git a/source/blender/geometry/intern/mesh_to_curve_convert.cc b/source/blender/geometry/intern/mesh_to_curve_convert.cc
new file mode 100644
index 00000000000..64b9fa5c01d
--- /dev/null
+++ b/source/blender/geometry/intern/mesh_to_curve_convert.cc
@@ -0,0 +1,283 @@
+/*
+ * 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<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<bke::AttributeIDRef> source_attribute_ids = mesh_component.attribute_ids();
+
+ /* Copy builtin control point attributes. */
+ if (source_attribute_ids.contains("tilt")) {
+ const fn::GVArray_Typed<float> tilt_attribute = mesh_component.attribute_get_for_read<float>(
+ "tilt", ATTR_DOMAIN_POINT, 0.0f);
+ threading::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_ids.remove_contained("tilt");
+ }
+ if (source_attribute_ids.contains("radius")) {
+ const fn::GVArray_Typed<float> radius_attribute = mesh_component.attribute_get_for_read<float>(
+ "radius", ATTR_DOMAIN_POINT, 1.0f);
+ threading::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_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;
+ }
+
+ /* Don't copy anonymous attributes with no references anymore. */
+ if (attribute_id.is_anonymous()) {
+ const AnonymousAttributeID &anonymous_id = attribute_id.anonymous_id();
+ if (!BKE_anonymous_attribute_id_has_strong_references(&anonymous_id)) {
+ continue;
+ }
+ }
+
+ const fn::GVArrayPtr 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<fn::GMutableSpan> 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<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 edges_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(const Mesh &mesh, const IndexMask selection)
+{
+ Vector<std::pair<int, int>> 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<CurveEval> mesh_to_curve_convert(const MeshComponent &mesh_component,
+ const IndexMask selection)
+{
+ const Mesh &mesh = *mesh_component.get_for_read();
+ Vector<std::pair<int, int>> 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
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-08 19:03:23 +0300