Blender V5.3
mesh_calc_edges.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
8
9#include "BLI_array_utils.hh"
11#include "BLI_math_base_c.hh"
12#include "BLI_ordered_edge.hh"
13#include "BLI_task.hh"
14#include "BLI_threads.hh"
15#include "BLI_vector_set.hh"
16
17#include "BKE_attribute.hh"
20#include "BKE_attribute_math.hh"
21#include "BKE_customdata.hh"
22#include "BKE_mesh.hh"
23
24namespace blender::bke {
25
26namespace calc_edges {
27
32static uint64_t edge_hash_2(const OrderedEdge &edge)
33{
34 return edge.v_low;
35}
36
38 16,
44
45static void reserve_hash_maps(const Mesh &mesh,
46 const bool keep_existing_edges,
47 MutableSpan<EdgeMap> edge_maps)
48{
49 const int totedge_guess = std::max(keep_existing_edges ? mesh.edges_num : 0, mesh.faces_num * 2);
51 edge_maps, [&](EdgeMap &edge_map) { edge_map.reserve(totedge_guess / edge_maps.size()); });
52}
53
55{
56 r_sizes.reinitialize(maps.size() + 1);
57 for (const int map_i : maps.index_range()) {
58 r_sizes[map_i] = maps[map_i].size();
59 }
61}
62
63static int edge_to_hash_map_i(const OrderedEdge edge, const uint32_t parallel_mask)
64{
65 return parallel_mask & edge_hash_2(edge);
66}
67
69 const uint32_t parallel_mask,
70 MutableSpan<EdgeMap> edge_maps)
71{
72 /* Assume existing edges are valid. */
73 const Span<int2> edges = mesh.edges();
74 threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) {
75 const int task_index = &edge_map - edge_maps.data();
76 for (const int2 edge : edges) {
77 const OrderedEdge ordered_edge(edge);
78 /* Only add the edge when it belongs into this map. */
79 if (task_index == edge_to_hash_map_i(ordered_edge, parallel_mask)) {
80 edge_map.add(ordered_edge);
81 }
82 }
83 });
84}
85
87 const uint32_t parallel_mask,
88 MutableSpan<EdgeMap> edge_maps)
89{
90 const OffsetIndices<int> faces = mesh.faces();
91 const Span<int> corner_verts = mesh.corner_verts();
92 threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) {
93 const int task_index = &edge_map - edge_maps.data();
94 for (const int face_i : faces.index_range()) {
95 const IndexRange face = faces[face_i];
96 for (const int corner : face) {
97 const int vert = corner_verts[corner];
98 const int vert_prev = corner_verts[bke::mesh::face_corner_prev(face, corner)];
99 const OrderedEdge ordered_edge(vert_prev, vert);
100 /* Only add the edge when it belongs into this map. */
101 if (task_index == edge_to_hash_map_i(ordered_edge, parallel_mask)) {
102 edge_map.add(ordered_edge);
103 }
104 }
105 }
106 });
107}
108
110 MutableSpan<EdgeMap> edge_maps,
111 const OffsetIndices<int> edge_offsets,
112 const OffsetIndices<int> prefix_skip_offsets,
113 MutableSpan<int2> new_edges)
114{
115 threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) {
116 const int task_index = &edge_map - edge_maps.data();
117 if (edge_offsets[task_index].is_empty()) {
118 return;
119 }
120
121 if (prefix_skip_offsets[task_index].size() == edge_offsets[task_index].size()) {
122 return;
123 }
124
125 const IndexRange all_map_edges = edge_offsets[task_index];
126 const IndexRange prefix_to_skip = prefix_skip_offsets[task_index];
127 const IndexRange map_edges = IndexRange::from_begin_size(
128 all_map_edges.start() - prefix_to_skip.start(),
129 all_map_edges.size() - prefix_to_skip.size());
130
131 MutableSpan<int2> result_edges = new_edges.slice(map_edges);
132 result_edges.copy_from(edge_map.as_span().drop_front(prefix_to_skip.size()).cast<int2>());
133 });
134}
135
137 const Span<int> corner_verts,
138 const Span<EdgeMap> edge_maps,
139 const uint32_t parallel_mask,
140 const OffsetIndices<int> edge_offsets,
141 MutableSpan<int> corner_edges)
142{
143 threading::parallel_for(faces.index_range(), 100, [&](IndexRange range) {
144 for (const int face_index : range) {
145 const IndexRange face = faces[face_index];
146 for (const int corner : face) {
147 const int vert = corner_verts[corner];
148 const int vert_prev = corner_verts[bke::mesh::face_corner_next(face, corner)];
149 const OrderedEdge ordered_edge(vert_prev, vert);
150 const int task_index = edge_to_hash_map_i(ordered_edge, parallel_mask);
151 const EdgeMap &edge_map = edge_maps[task_index];
152 const int edge_i = edge_map.index_of(ordered_edge);
153 const int edge_index = edge_offsets[task_index][edge_i];
154 corner_edges[corner] = edge_index;
155 }
156 }
157 });
158}
159
161{
162 /* Don't use parallelization when the mesh is small. */
163 if (mesh.faces_num < 1000) {
164 return 1;
165 }
166 /* Use at most 8 separate hash tables. Using more threads has diminishing returns. These threads
167 * are better off doing something more useful instead. */
168 const int system_thread_count = BLI_system_thread_count();
169 return power_of_2_min_i(std::min(8, system_thread_count));
170}
171
173{
174 threading::parallel_for_each(edge_maps, [](EdgeMap &edge_map) { edge_map.clear(); });
175}
176
178 const IndexMask &edges_to_check,
179 const Span<EdgeMap> edge_maps,
180 const uint32_t parallel_mask,
181 const OffsetIndices<int> edge_offsets,
182 IndexMaskMemory &memory)
183{
184 if (edges_to_check.is_empty()) {
185 return {};
186 }
187
188 constexpr int no_original_edge = std::numeric_limits<int>::max();
189 Array<int> map_edge_to_first_original(edge_offsets.total_size());
190 map_edge_to_first_original.as_mutable_span().fill(no_original_edge);
191
192 /* TODO: Lock-free parallel version? BLI' "atomic::min<T>(T&, T);" ? */
193 edges_to_check.foreach_index_optimized<int>([&](const int edge_i) {
194 const OrderedEdge edge = edges[edge_i];
195 const int map_i = calc_edges::edge_to_hash_map_i(edge, parallel_mask);
196 const int edge_index = edge_maps[map_i].index_of(edge);
197
198 int &original_edge = map_edge_to_first_original[edge_offsets[map_i][edge_index]];
199 original_edge = math::min(original_edge, edge_i);
200 });
201
202 /* Note: #map_edge_to_first_original might still contains #no_original_edge if edges was both non
203 * distinct and not full set. */
204
205 return IndexMask::from_predicate(edges_to_check, memory, [&](const int srd_edge_i) {
206 const OrderedEdge edge = edges[srd_edge_i];
207 const int map_i = calc_edges::edge_to_hash_map_i(edge, parallel_mask);
208 const int edge_index = edge_maps[map_i].index_of(edge);
209 return map_edge_to_first_original[edge_offsets[map_i][edge_index]] == srd_edge_i;
210 });
211}
212
213static void map_edge_to_span_index(const Span<int2> edges,
214 const Span<EdgeMap> edge_maps,
215 const uint32_t parallel_mask,
216 const OffsetIndices<int> edge_offsets,
217 MutableSpan<int> indices)
218{
219 threading::parallel_for_each(edge_maps.index_range(), [&](const int map_i) {
220 int edge_map_iter = 0;
221 for (const int edge_i : edges.index_range()) {
222 const int edge_map = calc_edges::edge_to_hash_map_i(edges[edge_i], parallel_mask);
223 if (map_i != edge_map) {
224 continue;
225 }
226 indices[edge_offsets[edge_map][edge_map_iter]] = edge_i;
227 edge_map_iter++;
228 }
229 });
230}
231
232} // namespace calc_edges
233
235 bool keep_existing_edges,
236 const bool select_new_edges,
237 const AttributeFilter &attribute_filter)
238{
239
240 if (mesh.edges_num == 0 && mesh.corners_num == 0) {
241 /* BLI_assert(mesh_is_valid(mesh)); */
242 return;
243 }
244
245 if (mesh.corners_num == 0 && !keep_existing_edges) {
246 CustomData_free(&mesh.edge_data);
247 mesh.edges_num = 0;
248 mesh.tag_loose_edges_none();
249 /* BLI_assert(mesh_is_valid(mesh)); */
250 return;
251 }
252
253 BLI_assert(std::all_of(mesh.edges().begin(), mesh.edges().end(), [&](const int2 edge) {
254 return edge.x != edge.y;
255 }));
256
257 /* Parallelization is achieved by having multiple hash tables for different subsets of edges.
258 * Each edge is assigned to one of the hash maps based on the lower bits of a hash value. */
259 const int parallel_maps = calc_edges::get_parallel_maps_count(mesh);
260 BLI_assert(is_power_of_2_i(parallel_maps));
261 const uint32_t parallel_mask = uint32_t(parallel_maps) - 1;
262 Array<calc_edges::EdgeMap> edge_maps(parallel_maps);
263 calc_edges::reserve_hash_maps(mesh, keep_existing_edges, edge_maps);
264
265 Array<int> original_edge_maps_prefix_size(edge_maps.size() + 1, 0);
266 if (keep_existing_edges) {
267 calc_edges::add_existing_edges_to_hash_maps(mesh, parallel_mask, edge_maps);
268 calc_edges::edge_map_offsets(edge_maps, original_edge_maps_prefix_size);
269 }
270 const OffsetIndices<int> original_edge_maps_prefix(original_edge_maps_prefix_size.as_span());
271 const int original_unique_edge_num = original_edge_maps_prefix.total_size();
272 const bool original_edges_are_distinct = original_unique_edge_num == mesh.edges_num;
273
274 if (mesh.corners_num == 0 && keep_existing_edges && original_edges_are_distinct) {
275 /* BLI_assert(mesh_is_valid(&mesh)); */
276 return;
277 }
278
279 calc_edges::add_face_edges_to_hash_maps(mesh, parallel_mask, edge_maps);
280 Array<int> edge_sizes;
281 const OffsetIndices<int> edge_offsets = calc_edges::edge_map_offsets(edge_maps, edge_sizes);
282 const bool no_new_edges = edge_offsets.total_size() == original_unique_edge_num;
283
284 MutableAttributeAccessor dst_attributes = mesh.attributes_for_write();
285 dst_attributes.add<int>(".corner_edge", AttrDomain::Corner, AttributeInitConstruct());
286 MutableSpan<int> corner_edges = mesh.corner_edges_for_write();
287#ifndef NDEBUG
288 corner_edges.fill(-1);
289#endif
290
291 const int result_edges_num = edge_offsets.total_size();
292
293 const OffsetIndices<int> faces = mesh.faces();
294 const Span<int2> original_edges = mesh.edges();
295 const Span<int> corner_verts = mesh.corner_verts();
296 if (keep_existing_edges && original_edges_are_distinct && no_new_edges) {
297 /* We need a way to say from caller side if we should generate corner edge attribute even in
298 * that case. TODO: make this optional. */
300 faces, corner_verts, edge_maps, parallel_mask, edge_offsets, corner_edges);
301
302 Array<int> edge_map_to_result_index(result_edges_num);
303#ifndef NDEBUG
304 edge_map_to_result_index.as_mutable_span().fill(-1);
305#endif
307 original_edges, edge_maps, parallel_mask, edge_offsets, edge_map_to_result_index);
308 array_utils::gather(edge_map_to_result_index.as_span(), corner_edges.as_span(), corner_edges);
309
310 BLI_assert(!corner_edges.contains(-1));
312 return;
313 }
314
315 IndexMaskMemory memory;
316 IndexRange back_range_of_new_edges;
317 IndexMask src_to_dst_mask;
318
319 auto *edge_verts_data = new ImplicitSharedValue<Array<int2>>(result_edges_num);
320 MutableSpan<int2> edge_verts = edge_verts_data->data;
321#ifndef NDEBUG
322 edge_verts.fill(int2(-1));
323#endif
324
325 if (keep_existing_edges) {
326 back_range_of_new_edges = IndexRange(result_edges_num).drop_front(original_unique_edge_num);
327
328 if (original_edges_are_distinct) {
329 src_to_dst_mask = IndexRange(original_unique_edge_num);
330 }
331 else {
332 src_to_dst_mask = calc_edges::mask_first_distinct_edges(original_edges,
333 original_edges.index_range(),
334 edge_maps,
335 parallel_mask,
336 edge_offsets,
337 memory);
338 }
339 BLI_assert(src_to_dst_mask.size() == original_unique_edge_num);
340
342 original_edges, src_to_dst_mask, edge_verts.take_front(original_unique_edge_num));
343
344 /* In order to reduce permutations of edge attributes we must provide result edge indices near
345 * to original. */
346 Array<int> edge_map_to_result_index(result_edges_num);
347#ifndef NDEBUG
348 edge_map_to_result_index.as_mutable_span().fill(-1);
349#endif
350
351 if (original_edges_are_distinct) {
352 /* TODO: Do we can group edges by .low vertex? Or by hash, but with Span<int> of edges by
353 * group?... */
354 calc_edges::map_edge_to_span_index(original_edges.take_front(mesh.edges_num),
355 edge_maps,
356 parallel_mask,
357 edge_offsets,
358 edge_map_to_result_index);
359 }
360 else {
361 src_to_dst_mask.foreach_index(
362 [&](const int src_index, const int dst_index) {
363 const OrderedEdge edge = original_edges[src_index];
364 const int map_i = calc_edges::edge_to_hash_map_i(edge, parallel_mask);
365 const int edge_index = edge_maps[map_i].index_of(edge);
366 edge_map_to_result_index[edge_offsets[map_i][edge_index]] = dst_index;
367 },
369 }
370
371 if (!no_new_edges) {
372 BLI_assert(edge_offsets.data().size() == original_edge_maps_prefix.data().size());
373
374 /* TODO: Check if all new edges are range. */
375 const int new_edges_start = original_unique_edge_num;
376 for (const int map_i : edge_maps.index_range()) {
377 const IndexRange map_edges = edge_offsets[map_i];
378 const IndexRange prefix_edges = original_edge_maps_prefix[map_i];
379 const IndexRange new_edges_in_map = map_edges.drop_front(prefix_edges.size());
380
381 const int new_edges_start_pos = map_edges.start() - prefix_edges.start();
382 const int map_new_edges_start = new_edges_start + new_edges_start_pos;
384 edge_map_to_result_index.as_mutable_span().slice(new_edges_in_map),
385 map_new_edges_start);
386 }
387 }
388
389 BLI_assert(!edge_map_to_result_index.as_span().contains(-1));
391 faces, corner_verts, edge_maps, parallel_mask, edge_offsets, corner_edges);
392 array_utils::gather(edge_map_to_result_index.as_span(), corner_edges.as_span(), corner_edges);
393
395 edge_maps,
396 edge_offsets,
397 original_edge_maps_prefix,
398 edge_verts.drop_front(original_unique_edge_num));
399 }
400 else {
401 if (mesh.edges_num != 0) {
402 const IndexMask original_corner_edges = IndexMask::from_predicate(
403 IndexRange(mesh.edges_num), memory, [&](const int edge_i) {
404 const OrderedEdge edge = original_edges[edge_i];
405 const int map_i = calc_edges::edge_to_hash_map_i(edge, parallel_mask);
406 return edge_maps[map_i].contains(edge);
407 });
409 original_edges, original_corner_edges, edge_maps, parallel_mask, edge_offsets, memory);
410
411 const int old_corner_edges_num = src_to_dst_mask.size();
412 back_range_of_new_edges = IndexRange(result_edges_num).drop_front(old_corner_edges_num);
413
414 Array<int> edge_map_to_result_index;
415 if (!src_to_dst_mask.is_empty()) {
416 /* TODO: Check if mask is range. */
417 edge_map_to_result_index.reinitialize(result_edges_num);
418 edge_map_to_result_index.as_mutable_span().fill(1);
419 src_to_dst_mask.foreach_index([&](const int original_edge_i) {
420 const OrderedEdge edge = original_edges[original_edge_i];
421 const int edge_map = calc_edges::edge_to_hash_map_i(edge, parallel_mask);
422 const int edge_index = edge_maps[edge_map].index_of(edge);
423 edge_map_to_result_index[edge_offsets[edge_map][edge_index]] = 0;
424 });
425
427 old_corner_edges_num);
428
429 src_to_dst_mask.foreach_index([&](const int original_edge_i, const int dst_edge_i) {
430 const OrderedEdge edge = original_edges[original_edge_i];
431 const int edge_map = calc_edges::edge_to_hash_map_i(edge, parallel_mask);
432 const int edge_index = edge_maps[edge_map].index_of(edge);
433 edge_map_to_result_index[edge_offsets[edge_map][edge_index]] = dst_edge_i;
434 });
435
437 original_edges, src_to_dst_mask, edge_verts.take_front(old_corner_edges_num));
438
439 threading::parallel_for_each(edge_maps, [&](calc_edges::EdgeMap &edge_map) {
440 const int task_index = &edge_map - edge_maps.data();
441 if (edge_offsets[task_index].is_empty()) {
442 return;
443 }
444
446 edge_map.as_span().cast<int2>(),
447 edge_map_to_result_index.as_span().slice(edge_offsets[task_index]),
448 edge_verts);
449 });
450
452 faces, corner_verts, edge_maps, parallel_mask, edge_offsets, corner_edges);
453
455 edge_map_to_result_index.as_span(), corner_edges.as_span(), corner_edges);
456 }
457 else {
459 faces, corner_verts, edge_maps, parallel_mask, edge_offsets, corner_edges);
461 edge_maps, edge_offsets, original_edge_maps_prefix, edge_verts);
462 }
463 }
464 else {
465 back_range_of_new_edges = IndexRange(result_edges_num);
466 BLI_assert(original_edge_maps_prefix.total_size() == 0);
468 faces, corner_verts, edge_maps, parallel_mask, edge_offsets, corner_edges);
470 edge_maps, edge_offsets, original_edge_maps_prefix, edge_verts);
471 }
472 }
473
474 BLI_assert(std::all_of(
475 edge_verts.begin(), edge_verts.end(), [&](const int2 edge) { return edge.x != edge.y; }));
476
477 BLI_assert(!corner_edges.contains(-1));
478 BLI_assert(!edge_verts.contains(int2(-1)));
479
480 BLI_assert(src_to_dst_mask.size() + back_range_of_new_edges.size() == result_edges_num);
481 BLI_assert(back_range_of_new_edges.one_after_last() == result_edges_num);
482
483 Vector<std::string> attributes_to_drop;
484 /* TODO: Need ::all_pass() on #attribute_filter to know if this loop can be skipped. */
485 mesh.attributes().foreach_attribute([&](const AttributeIter &attribute) {
486 if (attribute.data_type == AttrType::String) {
487 return;
488 }
489 if (attribute.domain != AttrDomain::Edge) {
490 return;
491 }
492 if (!attribute_filter.allow_skip(attribute.name)) {
493 return;
494 }
495 attributes_to_drop.append(attribute.name);
496 });
497
498 for (const StringRef attribute : attributes_to_drop) {
499 dst_attributes.remove(attribute);
500 }
501
502 mesh.attribute_storage.wrap().remove(".edge_verts");
503 for (bke::Attribute &attr : mesh.attribute_storage.wrap()) {
504 if (attr.domain() != bke::AttrDomain::Edge) {
505 continue;
506 }
507 switch (attr.storage_type()) {
509 break;
510 }
512 const CPPType &type = bke::attribute_type_to_cpp_type(attr.data_type());
513 const auto &src_data = std::get<bke::Attribute::ArrayData>(attr.data());
514 auto dst_data = bke::Attribute::ArrayData::from_uninitialized(type, result_edges_num);
515 const GSpan src(type, src_data.data, mesh.edges_num);
516 GMutableSpan dst(type, dst_data.data, result_edges_num);
517 array_utils::gather(src, src_to_dst_mask, dst.take_front(src_to_dst_mask.size()));
519 dst.slice(back_range_of_new_edges).data(),
520 dst.slice(back_range_of_new_edges).size());
521 attr.assign_data(std::move(dst_data));
522 break;
523 }
524 }
525 }
526
527 {
528 const int orig_index_layer = CustomData_get_layer_index(&mesh.edge_data, CD_ORIGINDEX);
529 if (orig_index_layer != -1) {
530 CustomDataLayer &layer = mesh.edge_data.layers[orig_index_layer];
531 const int *src_data = static_cast<const int *>(layer.data);
532
533 int *dst_data = MEM_new_array_uninitialized<int>(result_edges_num, __func__);
534 MutableSpan dst(dst_data, result_edges_num);
535 if (src_data != nullptr) {
536 const Span src(src_data, mesh.edges_num);
537 array_utils::gather(src, src_to_dst_mask, dst.take_front(src_to_dst_mask.size()));
538 }
539 dst.slice(back_range_of_new_edges).fill(-1);
540 layer.sharing_info->remove_user_and_delete_if_last();
541 layer.data = dst_data;
542 layer.sharing_info = implicit_sharing::info_for_mem_free(dst_data);
543 }
544 }
545
546 mesh.edges_num = result_edges_num;
547
548 dst_attributes.add<int2>(
549 ".edge_verts", AttrDomain::Edge, AttributeInitShared(edge_verts.data(), *edge_verts_data));
550 edge_verts_data->remove_user_and_delete_if_last();
551
552 if (select_new_edges) {
553 dst_attributes.remove(".select_edge");
554 if (ELEM(back_range_of_new_edges.size(), 0, mesh.edges_num)) {
555 const bool fill_value = back_range_of_new_edges.size() == mesh.edges_num;
556 dst_attributes.add<bool>(".select_edge", AttrDomain::Edge, AttributeInitValue(fill_value));
557 }
558 else {
559 SpanAttributeWriter<bool> select_edge = dst_attributes.lookup_or_add_for_write_span<bool>(
560 ".select_edge", AttrDomain::Edge);
561 select_edge.span.drop_back(back_range_of_new_edges.size()).fill(false);
562 select_edge.span.take_back(back_range_of_new_edges.size()).fill(true);
563 select_edge.finish();
564 }
565 }
566
567 if (!keep_existing_edges) {
568 /* All edges are rebuilt from the faces, so there are no loose edges. */
569 mesh.tag_loose_edges_none();
570 }
571
572 /* Explicitly clear edge maps, because that way it can be parallelized. */
574
575 /* BLI_assert(mesh_is_valid(mesh)); */
576}
577
578void mesh_calc_edges(Mesh &mesh, bool keep_existing_edges, const bool select_new_edges)
579{
580 mesh_calc_edges(mesh, keep_existing_edges, select_new_edges, AttributeFilter::default_filter());
581}
582
583} // namespace blender::bke
CustomData interface, see also DNA_customdata_types.h.
#define ELEM(...)
int64_t size() const
Definition BLI_array.hh:267
Span< T > as_span() const
Definition BLI_array.hh:254
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
const T * data() const
Definition BLI_array.hh:323
IndexRange index_range() const
Definition BLI_array.hh:371
void reinitialize(const int64_t new_size)
Definition BLI_array.hh:430
void fill_construct_n(const void *value, void *dst, int64_t n) const
const void * default_value() const
GMutableSpan take_front(const int64_t n) const
GMutableSpan slice(const int64_t start, int64_t size) const
static IndexMask from_predicate(const IndexMask &universe, LinearAllocator<> &memory, Fn &&predicate, exec_mode::Mode mode=exec_mode::parallel)
constexpr int64_t one_after_last() const
constexpr int64_t size() const
static constexpr IndexRange from_begin_size(const int64_t begin, const int64_t size)
constexpr int64_t start() const
constexpr IndexRange drop_front(int64_t n) const
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr T * data() const
Definition BLI_span.hh:545
constexpr void fill(const T &value) const
Definition BLI_span.hh:523
constexpr void copy_from(Span< T > values) const
Definition BLI_span.hh:745
constexpr MutableSpan take_front(const int64_t n) const
Definition BLI_span.hh:635
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr Span take_front(int64_t n) const
Definition BLI_span.hh:197
bool add(const Key &key)
void reserve(const int64_t n)
Span< Key > as_span() const
void append(const T &value)
bool add(const StringRef name, const AttrDomain domain, const AttrType data_type, const AttributeInit &initializer)
GSpanAttributeWriter lookup_or_add_for_write_span(StringRef name, AttrDomain domain, AttrType data_type, const AttributeInit &initializer=AttributeInitDefaultValue())
void foreach_index_optimized(Fn &&fn, Mode mode=exec_mode::serial) const
void foreach_index(Fn &&fn, Mode mode=exec_mode::serial) const
#define attribute(slot)
#define layer
void gather(const GVArray &src, const IndexMask &indices, GMutableSpan dst, exec_mode::Mode mode=exec_mode::parallel)
void scatter(const Span< T > src, const Span< IndexT > indices, MutableSpan< T > dst, const Mode mode={})
void fill_index_range(MutableSpan< T > span, const T start=0)
static void add_existing_edges_to_hash_maps(const Mesh &mesh, const uint32_t parallel_mask, MutableSpan< EdgeMap > edge_maps)
static uint64_t edge_hash_2(const OrderedEdge &edge)
static void update_edge_indices_in_face_loops(const OffsetIndices< int > faces, const Span< int > corner_verts, const Span< EdgeMap > edge_maps, const uint32_t parallel_mask, const OffsetIndices< int > edge_offsets, MutableSpan< int > corner_edges)
static int get_parallel_maps_count(const Mesh &mesh)
static int edge_to_hash_map_i(const OrderedEdge edge, const uint32_t parallel_mask)
static OffsetIndices< int > edge_map_offsets(const Span< EdgeMap > maps, Array< int > &r_sizes)
static void serialize_and_initialize_deduplicated_edges(MutableSpan< EdgeMap > edge_maps, const OffsetIndices< int > edge_offsets, const OffsetIndices< int > prefix_skip_offsets, MutableSpan< int2 > new_edges)
static void map_edge_to_span_index(const Span< int2 > edges, const Span< EdgeMap > edge_maps, const uint32_t parallel_mask, const OffsetIndices< int > edge_offsets, MutableSpan< int > indices)
static void clear_hash_tables(MutableSpan< EdgeMap > edge_maps)
static void reserve_hash_maps(const Mesh &mesh, const bool keep_existing_edges, MutableSpan< EdgeMap > edge_maps)
static void add_face_edges_to_hash_maps(const Mesh &mesh, const uint32_t parallel_mask, MutableSpan< EdgeMap > edge_maps)
static IndexMask mask_first_distinct_edges(const Span< int2 > edges, const IndexMask &edges_to_check, const Span< EdgeMap > edge_maps, const uint32_t parallel_mask, const OffsetIndices< int > edge_offsets, IndexMaskMemory &memory)
VectorSet< OrderedEdge, 16, DefaultProbingStrategy, DefaultHash< OrderedEdge >, DefaultEquality< OrderedEdge >, SimpleVectorSetSlot< OrderedEdge, int >, GuardedAllocator > EdgeMap
int face_corner_prev(const IndexRange face, const int corner)
Definition BKE_mesh.hh:306
bool mesh_is_valid(const Mesh &mesh, bool verbose=true)
void mesh_calc_edges(Mesh &mesh, bool keep_existing_edges, bool select_new_edges)
const CPPType & attribute_type_to_cpp_type(AttrType type)
constexpr ParallelGrainSize grain_size(int grain_size)
const ImplicitSharingInfo * info_for_mem_free(T *data)
T min(const T &a, const T &b)
OffsetIndices< int > accumulate_counts_to_offsets(MutableSpan< int > counts_to_offsets, int start_offset=0)
void parallel_for_each(Range &&range, const Function &function)
Definition BLI_task.hh:31
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
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
unsigned __int64 uint64_t
Definition BKE_text.h:91
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
MINLINE int power_of_2_min_i(int n)
int CustomData_get_layer_index(const CustomData *data, eCustomDataType type)
int BLI_system_thread_count()
Definition threads.cc:258
unsigned int uint32_t
Definition BKE_text.h:81
VecBase< int32_t, 2 > int2
void CustomData_free(CustomData *data)
PythonProbingStrategy<> DefaultProbingStrategy
MINLINE int is_power_of_2_i(int n)
static const AttributeFilter & default_filter()
bool allow_skip(const StringRef name) const
static ArrayData from_uninitialized(const CPPType &type, int64_t domain_size)