Blender  V3.3
mesh_calc_edges.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
7 #include "DNA_mesh_types.h"
8 #include "DNA_meshdata_types.h"
9 #include "DNA_object_types.h"
10 
11 #include "BLI_map.hh"
12 #include "BLI_task.hh"
13 #include "BLI_threads.h"
14 #include "BLI_timeit.hh"
15 
16 #include "BKE_customdata.h"
17 #include "BKE_mesh.h"
18 
20 
22 struct OrderedEdge {
23  int v_low, v_high;
24 
25  OrderedEdge(const int v1, const int v2)
26  {
27  if (v1 < v2) {
28  v_low = v1;
29  v_high = v2;
30  }
31  else {
32  v_low = v2;
33  v_high = v1;
34  }
35  }
36 
37  OrderedEdge(const uint v1, const uint v2)
38  : OrderedEdge(static_cast<int>(v1), static_cast<int>(v2))
39  {
40  }
41 
42  uint64_t hash() const
43  {
44  return (this->v_low << 8) ^ this->v_high;
45  }
46 
49  uint64_t hash2() const
50  {
51  return this->v_low;
52  }
53 
54  friend bool operator==(const OrderedEdge &e1, const OrderedEdge &e2)
55  {
56  BLI_assert(e1.v_low < e1.v_high);
57  BLI_assert(e2.v_low < e2.v_high);
58  return e1.v_low == e2.v_low && e1.v_high == e2.v_high;
59  }
60 };
61 
62 /* The map first contains an edge pointer and later an index. */
65  int index;
66 };
68 
69 static void reserve_hash_maps(const Mesh *mesh,
70  const bool keep_existing_edges,
71  MutableSpan<EdgeMap> edge_maps)
72 {
73  const int totedge_guess = std::max(keep_existing_edges ? mesh->totedge : 0, mesh->totpoly * 2);
75  edge_maps, [&](EdgeMap &edge_map) { edge_map.reserve(totedge_guess / edge_maps.size()); });
76 }
77 
79  MutableSpan<EdgeMap> edge_maps,
80  uint32_t parallel_mask)
81 {
82  /* Assume existing edges are valid. */
83  threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) {
84  const int task_index = &edge_map - edge_maps.data();
85  for (const MEdge &edge : Span(mesh->medge, mesh->totedge)) {
86  OrderedEdge ordered_edge{edge.v1, edge.v2};
87  /* Only add the edge when it belongs into this map. */
88  if (task_index == (parallel_mask & ordered_edge.hash2())) {
89  edge_map.add_new(ordered_edge, {&edge});
90  }
91  }
92  });
93 }
94 
96  MutableSpan<EdgeMap> edge_maps,
97  uint32_t parallel_mask)
98 {
99  const Span<MLoop> loops{mesh->mloop, mesh->totloop};
100  threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) {
101  const int task_index = &edge_map - edge_maps.data();
102  for (const MPoly &poly : Span(mesh->mpoly, mesh->totpoly)) {
103  Span<MLoop> poly_loops = loops.slice(poly.loopstart, poly.totloop);
104  const MLoop *prev_loop = &poly_loops.last();
105  for (const MLoop &next_loop : poly_loops) {
106  /* Can only be the same when the mesh data is invalid. */
107  if (prev_loop->v != next_loop.v) {
108  OrderedEdge ordered_edge{prev_loop->v, next_loop.v};
109  /* Only add the edge when it belongs into this map. */
110  if (task_index == (parallel_mask & ordered_edge.hash2())) {
111  edge_map.lookup_or_add(ordered_edge, {nullptr});
112  }
113  }
114  prev_loop = &next_loop;
115  }
116  }
117  });
118 }
119 
121  MutableSpan<MEdge> new_edges,
122  short new_edge_flag)
123 {
124  /* All edges are distributed in the hash tables now. They have to be serialized into a single
125  * array below. To be able to parallelize this, we have to compute edge index offsets for each
126  * map. */
127  Array<int> edge_index_offsets(edge_maps.size());
128  edge_index_offsets[0] = 0;
129  for (const int i : IndexRange(edge_maps.size() - 1)) {
130  edge_index_offsets[i + 1] = edge_index_offsets[i] + edge_maps[i].size();
131  }
132 
133  threading::parallel_for_each(edge_maps, [&](EdgeMap &edge_map) {
134  const int task_index = &edge_map - edge_maps.data();
135 
136  int new_edge_index = edge_index_offsets[task_index];
137  for (EdgeMap::MutableItem item : edge_map.items()) {
138  MEdge &new_edge = new_edges[new_edge_index];
139  const MEdge *orig_edge = item.value.original_edge;
140  if (orig_edge != nullptr) {
141  /* Copy values from original edge. */
142  new_edge = *orig_edge;
143  }
144  else {
145  /* Initialize new edge. */
146  new_edge.v1 = item.key.v_low;
147  new_edge.v2 = item.key.v_high;
148  new_edge.flag = new_edge_flag;
149  }
150  item.value.index = new_edge_index;
151  new_edge_index++;
152  }
153  });
154 }
155 
157  Span<EdgeMap> edge_maps,
158  uint32_t parallel_mask)
159 {
160  const MutableSpan<MLoop> loops{mesh->mloop, mesh->totloop};
162  for (const int poly_index : range) {
163  MPoly &poly = mesh->mpoly[poly_index];
164  MutableSpan<MLoop> poly_loops = loops.slice(poly.loopstart, poly.totloop);
165 
166  MLoop *prev_loop = &poly_loops.last();
167  for (MLoop &next_loop : poly_loops) {
168  int edge_index;
169  if (prev_loop->v != next_loop.v) {
170  OrderedEdge ordered_edge{prev_loop->v, next_loop.v};
171  /* Double lookup: First find the map that contains the edge, then lookup the edge. */
172  const EdgeMap &edge_map = edge_maps[parallel_mask & ordered_edge.hash2()];
173  edge_index = edge_map.lookup(ordered_edge).index;
174  }
175  else {
176  /* This is an invalid edge; normally this does not happen in Blender,
177  * but it can be part of an imported mesh with invalid geometry. See
178  * T76514. */
179  edge_index = 0;
180  }
181  prev_loop->e = edge_index;
182  prev_loop = &next_loop;
183  }
184  }
185  });
186 }
187 
189 {
190  /* Don't use parallelization when the mesh is small. */
191  if (mesh->totpoly < 1000) {
192  return 1;
193  }
194  /* Use at most 8 separate hash tables. Using more threads has diminishing returns. These threads
195  * can better do something more useful instead. */
196  const int system_thread_count = BLI_system_thread_count();
197  return power_of_2_min_i(std::min(8, system_thread_count));
198 }
199 
201 {
202  threading::parallel_for_each(edge_maps, [](EdgeMap &edge_map) { edge_map.clear(); });
203 }
204 
205 } // namespace blender::bke::calc_edges
206 
207 void BKE_mesh_calc_edges(Mesh *mesh, bool keep_existing_edges, const bool select_new_edges)
208 {
209  using namespace blender;
210  using namespace blender::bke;
211  using namespace blender::bke::calc_edges;
212 
213  /* Parallelization is achieved by having multiple hash tables for different subsets of edges.
214  * Each edge is assigned to one of the hash maps based on the lower bits of a hash value. */
215  const int parallel_maps = get_parallel_maps_count(mesh);
216  BLI_assert(is_power_of_2_i(parallel_maps));
217  const uint32_t parallel_mask = static_cast<uint32_t>(parallel_maps) - 1;
218  Array<EdgeMap> edge_maps(parallel_maps);
219  reserve_hash_maps(mesh, keep_existing_edges, edge_maps);
220 
221  /* Add all edges. */
222  if (keep_existing_edges) {
223  calc_edges::add_existing_edges_to_hash_maps(mesh, edge_maps, parallel_mask);
224  }
225  calc_edges::add_polygon_edges_to_hash_maps(mesh, edge_maps, parallel_mask);
226 
227  /* Compute total number of edges. */
228  int new_totedge = 0;
229  for (EdgeMap &edge_map : edge_maps) {
230  new_totedge += edge_map.size();
231  }
232 
233  /* Create new edges. */
234  MutableSpan<MEdge> new_edges{
235  static_cast<MEdge *>(MEM_calloc_arrayN(new_totedge, sizeof(MEdge), __func__)), new_totedge};
236  const short new_edge_flag = (ME_EDGEDRAW | ME_EDGERENDER) | (select_new_edges ? SELECT : 0);
237  calc_edges::serialize_and_initialize_deduplicated_edges(edge_maps, new_edges, new_edge_flag);
238  calc_edges::update_edge_indices_in_poly_loops(mesh, edge_maps, parallel_mask);
239 
240  /* Free old CustomData and assign new one. */
243  CustomData_add_layer(&mesh->edata, CD_MEDGE, CD_ASSIGN, new_edges.data(), new_totedge);
244  mesh->totedge = new_totedge;
245  mesh->medge = new_edges.data();
246 
247  /* Explicitly clear edge maps, because that way it can be parallelized. */
248  clear_hash_tables(edge_maps);
249 }
CustomData interface, see also DNA_customdata_types.h.
void CustomData_free(struct CustomData *data, int totelem)
Definition: customdata.cc:2373
@ CD_ASSIGN
void * CustomData_add_layer(struct CustomData *data, int type, eCDAllocType alloctype, void *layer, int totelem)
Definition: customdata.cc:2776
void CustomData_reset(struct CustomData *data)
Definition: customdata.cc:2367
#define BLI_assert(a)
Definition: BLI_assert.h:46
MINLINE int power_of_2_min_i(int n)
MINLINE int is_power_of_2_i(int n)
unsigned int uint
Definition: BLI_sys_types.h:67
int BLI_system_thread_count(void)
Definition: threads.cc:281
@ CD_MEDGE
@ ME_EDGEDRAW
@ ME_EDGERENDER
Object is a sort of wrapper for general info.
_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
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void clear()
Definition: BLI_map.hh:963
ItemIterator items() const
Definition: BLI_map.hh:859
void reserve(int64_t n)
Definition: BLI_map.hh:953
constexpr int64_t size() const
Definition: BLI_span.hh:511
constexpr T * data() const
Definition: BLI_span.hh:548
#define SELECT
void *(* MEM_calloc_arrayN)(size_t len, size_t size, const char *str)
Definition: mallocn.c:32
void BKE_mesh_calc_edges(Mesh *mesh, bool keep_existing_edges, const bool select_new_edges)
static int get_parallel_maps_count(const Mesh *mesh)
static void add_polygon_edges_to_hash_maps(Mesh *mesh, MutableSpan< EdgeMap > edge_maps, uint32_t parallel_mask)
static void update_edge_indices_in_poly_loops(Mesh *mesh, Span< EdgeMap > edge_maps, uint32_t parallel_mask)
static void serialize_and_initialize_deduplicated_edges(MutableSpan< EdgeMap > edge_maps, MutableSpan< MEdge > new_edges, short new_edge_flag)
static void reserve_hash_maps(const Mesh *mesh, const bool keep_existing_edges, MutableSpan< EdgeMap > edge_maps)
static void clear_hash_tables(MutableSpan< EdgeMap > edge_maps)
static void add_existing_edges_to_hash_maps(Mesh *mesh, MutableSpan< EdgeMap > edge_maps, uint32_t parallel_mask)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
void parallel_for_each(Range &range, const Function &function)
Definition: BLI_task.hh:39
#define min(a, b)
Definition: sort.c:35
unsigned int uint32_t
Definition: stdint.h:80
unsigned __int64 uint64_t
Definition: stdint.h:90
struct MEdge * medge
int totedge
struct MLoop * mloop
int totpoly
CustomData edata
int totloop
struct MPoly * mpoly
OrderedEdge(const uint v1, const uint v2)
OrderedEdge(const int v1, const int v2)
friend bool operator==(const OrderedEdge &e1, const OrderedEdge &e2)
float max