Blender  V3.3
mesh_to_curve_convert.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
3 #include "BLI_array.hh"
5 #include "BLI_set.hh"
6 #include "BLI_task.hh"
7 
8 #include "DNA_mesh_types.h"
9 #include "DNA_meshdata_types.h"
10 
11 #include "BKE_attribute.hh"
12 #include "BKE_attribute_math.hh"
13 #include "BKE_curves.hh"
14 #include "BKE_geometry_set.hh"
15 
16 #include "GEO_mesh_to_curve.hh"
17 
18 namespace blender::geometry {
19 
20 template<typename T>
22 {
23  devirtualize_varray(src, [&](const auto &src) {
24  threading::parallel_for(map.index_range(), 1024, [&](const IndexRange range) {
25  for (const int i : range) {
26  const int vert_index = map[i];
27  dst[i] = src[vert_index];
28  }
29  });
30  });
31 }
32 
34  const Span<int> vert_indices,
35  const Span<int> curve_offsets,
36  const IndexRange cyclic_curves)
37 {
38  bke::CurvesGeometry curves(vert_indices.size(), curve_offsets.size());
39  curves.offsets_for_write().drop_back(1).copy_from(curve_offsets);
40  curves.offsets_for_write().last() = vert_indices.size();
41  curves.fill_curve_types(CURVE_TYPE_POLY);
42 
43  curves.cyclic_for_write().fill(false);
44  curves.cyclic_for_write().slice(cyclic_curves).fill(true);
45 
47  bke::MutableAttributeAccessor curves_attributes = curves.attributes_for_write();
48 
49  Set<bke::AttributeIDRef> source_attribute_ids = mesh_attributes.all_ids();
50 
51  for (const bke::AttributeIDRef &attribute_id : source_attribute_ids) {
52  if (mesh_attributes.is_builtin(attribute_id) && !curves_attributes.is_builtin(attribute_id)) {
53  /* Don't copy attributes that are built-in on meshes but not on curves. */
54  continue;
55  }
56 
57  if (!attribute_id.should_be_kept()) {
58  continue;
59  }
60 
61  const GVArray mesh_attribute = mesh_attributes.lookup(attribute_id, ATTR_DOMAIN_POINT);
62  /* Some attributes might not exist if they were builtin attribute on domains that don't
63  * have any elements, i.e. a face attribute on the output of the line primitive node. */
64  if (!mesh_attribute) {
65  continue;
66  }
67 
68  /* Copy attribute based on the map for this curve. */
69  attribute_math::convert_to_static_type(mesh_attribute.type(), [&](auto dummy) {
70  using T = decltype(dummy);
71  bke::SpanAttributeWriter<T> attribute =
72  curves_attributes.lookup_or_add_for_write_only_span<T>(attribute_id, ATTR_DOMAIN_POINT);
73  copy_with_map<T>(mesh_attribute.typed<T>(), vert_indices, attribute.span);
74  attribute.finish();
75  });
76  }
77 
78  return curves;
79 }
80 
88 };
89 
91  Span<std::pair<int, int>> edges)
92 {
93  Vector<int> vert_indices;
94  vert_indices.reserve(edges.size());
95  Vector<int> curve_offsets;
96 
97  /* Compute the number of edges connecting to each vertex. */
98  Array<int> neighbor_count(verts.size(), 0);
99  for (const std::pair<int, int> &edge : edges) {
100  neighbor_count[edge.first]++;
101  neighbor_count[edge.second]++;
102  }
103 
104  /* Compute an offset into the array of neighbor edges based on the counts. */
105  Array<int> neighbor_offsets(verts.size());
106  int start = 0;
107  for (const int i : verts.index_range()) {
108  neighbor_offsets[i] = start;
109  start += neighbor_count[i];
110  }
111 
112  /* Use as an index into the "neighbor group" for each vertex. */
113  Array<int> used_slots(verts.size(), 0);
114  /* Calculate the indices of each vertex's neighboring edges. */
115  Array<int> neighbors(edges.size() * 2);
116  for (const int i : edges.index_range()) {
117  const int v1 = edges[i].first;
118  const int v2 = edges[i].second;
119  neighbors[neighbor_offsets[v1] + used_slots[v1]] = v2;
120  neighbors[neighbor_offsets[v2] + used_slots[v2]] = v1;
121  used_slots[v1]++;
122  used_slots[v2]++;
123  }
124 
125  /* Now use the neighbor group offsets calculated above as a count used edges at each vertex. */
126  Array<int> unused_edges = std::move(used_slots);
127 
128  for (const int start_vert : verts.index_range()) {
129  /* The vertex will be part of a cyclic curve. */
130  if (neighbor_count[start_vert] == 2) {
131  continue;
132  }
133 
134  /* The vertex has no connected edges, or they were already used. */
135  if (unused_edges[start_vert] == 0) {
136  continue;
137  }
138 
139  for (const int i : IndexRange(neighbor_count[start_vert])) {
140  int current_vert = start_vert;
141  int next_vert = neighbors[neighbor_offsets[current_vert] + i];
142 
143  if (unused_edges[next_vert] == 0) {
144  continue;
145  }
146 
147  /* Start a new curve in the output. */
148  curve_offsets.append(vert_indices.size());
149  vert_indices.append(current_vert);
150 
151  /* Follow connected edges until we read a vertex with more than two connected edges. */
152  while (true) {
153  int last_vert = current_vert;
154  current_vert = next_vert;
155 
156  vert_indices.append(current_vert);
157  unused_edges[current_vert]--;
158  unused_edges[last_vert]--;
159 
160  if (neighbor_count[current_vert] != 2) {
161  break;
162  }
163 
164  const int offset = neighbor_offsets[current_vert];
165  const int next_a = neighbors[offset];
166  const int next_b = neighbors[offset + 1];
167  next_vert = (last_vert == next_a) ? next_b : next_a;
168  }
169  }
170  }
171 
172  /* All curves added after this are cyclic. */
173  const int cyclic_start = curve_offsets.size();
174 
175  /* All remaining edges are part of cyclic curves (we skipped vertices with two edges before). */
176  for (const int start_vert : verts.index_range()) {
177  if (unused_edges[start_vert] != 2) {
178  continue;
179  }
180 
181  int current_vert = start_vert;
182  int next_vert = neighbors[neighbor_offsets[current_vert]];
183 
184  curve_offsets.append(vert_indices.size());
185  vert_indices.append(current_vert);
186 
187  /* Follow connected edges until we loop back to the start vertex. */
188  while (next_vert != start_vert) {
189  const int last_vert = current_vert;
190  current_vert = next_vert;
191 
192  vert_indices.append(current_vert);
193  unused_edges[current_vert]--;
194  unused_edges[last_vert]--;
195 
196  const int offset = neighbor_offsets[current_vert];
197  const int next_a = neighbors[offset];
198  const int next_b = neighbors[offset + 1];
199  next_vert = (last_vert == next_a) ? next_b : next_a;
200  }
201  }
202 
203  const IndexRange cyclic_curves = curve_offsets.index_range().drop_front(cyclic_start);
204 
205  return {std::move(vert_indices), std::move(curve_offsets), cyclic_curves};
206 }
207 
214 {
215  Vector<std::pair<int, int>> selected_edges;
216  for (const int i : selection) {
217  selected_edges.append({mesh.medge[i].v1, mesh.medge[i].v2});
218  }
219  return selected_edges;
220 }
221 
223 {
224  Vector<std::pair<int, int>> selected_edges = get_selected_edges(mesh, selection);
226  selected_edges);
227 
229  mesh, output.vert_indices, output.curve_offsets, output.cyclic_curves);
230 }
231 
232 } // namespace blender::geometry
@ ATTR_DOMAIN_POINT
Definition: BKE_attribute.h:27
Low-level operations for curves.
@ CURVE_TYPE_POLY
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint GLint i2 _GL_VOID_RET _GL_VOID GLint j _GL_VOID_RET _GL_VOID GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble GLdouble GLdouble zFar _GL_VOID_RET _GL_UINT GLdouble *equation _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLenum GLfloat *v _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLfloat *values _GL_VOID_RET _GL_VOID GLushort *values _GL_VOID_RET _GL_VOID GLenum GLfloat *params _GL_VOID_RET _GL_VOID GLenum GLdouble *params _GL_VOID_RET _GL_VOID GLenum GLint *params _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_VOID GLsizei const void *pointer _GL_VOID_RET _GL_BOOL GLfloat param _GL_VOID_RET _GL_VOID GLint param _GL_VOID_RET _GL_VOID GLenum GLfloat param _GL_VOID_RET _GL_VOID GLenum GLint param _GL_VOID_RET _GL_VOID GLushort pattern _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint const GLdouble *points _GL_VOID_RET _GL_VOID GLdouble GLdouble GLint GLint GLdouble v1
Group Output data from inside of a node group A color picker Mix two input colors RGB to Convert a color s luminance to a grayscale value Generate a normal vector and a dot product Bright Control the brightness and contrast of the input color Vector Map an input vectors to curves
ATTR_WARN_UNUSED_RESULT const BMVert * v2
const CPPType & type() const
constexpr IndexRange drop_front(int64_t n) const
constexpr int64_t size() const
Definition: BLI_span.hh:240
int64_t size() const
Definition: BLI_vector.hh:694
void append(const T &value)
Definition: BLI_vector.hh:433
IndexRange index_range() const
Definition: BLI_vector.hh:920
void reserve(const int64_t min_capacity)
Definition: BLI_vector.hh:340
bool is_builtin(const AttributeIDRef &attribute_id) const
Set< AttributeIDRef > all_ids() const
GAttributeReader lookup(const AttributeIDRef &attribute_id) const
SyclQueue void void * src
static float verts[][3]
ccl_global KernelShaderEvalInput ccl_global float * output
ccl_gpu_kernel_postfix ccl_global float int int int int float bool int offset
void convert_to_static_type(const CPPType &cpp_type, const Func &func)
AttributeAccessor mesh_attributes(const Mesh &mesh)
static Vector< std::pair< int, int > > get_selected_edges(const Mesh &mesh, const IndexMask selection)
bke::CurvesGeometry create_curve_from_vert_indices(const Mesh &mesh, Span< int > vert_indices, Span< int > curve_offsets, IndexRange cyclic_curves)
static CurveFromEdgesOutput edges_to_curve_point_indices(Span< MVert > verts, Span< std::pair< int, int >> edges)
bke::CurvesGeometry mesh_to_curve_convert(const Mesh &mesh, const IndexMask selection)
static void copy_with_map(const VArray< T > &src, Span< int > map, MutableSpan< T > dst)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
void devirtualize_varray(const VArray< T > &varray, const Func &func, bool enable=true)
SocketIndexByIdentifierMap * map
unsigned int v1
unsigned int v2
struct MEdge * medge
struct MVert * mvert
int totvert