Blender  V3.3
bmesh_mesh_partial_update.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
36 #include "DNA_object_types.h"
37 
38 #include "MEM_guardedalloc.h"
39 
40 #include "BLI_alloca.h"
41 #include "BLI_bitmap.h"
42 #include "BLI_math_vector.h"
43 
44 #include "bmesh.h"
45 
52 #define GROW(len_alloc) ((len_alloc) + ((len_alloc) - ((len_alloc) / 2)))
53 #define GROW_ARRAY(mem, len_alloc) \
54  { \
55  mem = MEM_reallocN(mem, (sizeof(*mem)) * ((len_alloc) = GROW(len_alloc))); \
56  } \
57  ((void)0)
58 
59 #define GROW_ARRAY_AS_NEEDED(mem, len_alloc, index) \
60  if (UNLIKELY(len_alloc == index)) { \
61  GROW_ARRAY(mem, len_alloc); \
62  }
63 
65  BLI_bitmap *verts_tag,
66  BMVert *v)
67 {
68  const int i = BM_elem_index_get(v);
69  if (!BLI_BITMAP_TEST(verts_tag, i)) {
70  BLI_BITMAP_ENABLE(verts_tag, i);
71  GROW_ARRAY_AS_NEEDED(bmpinfo->verts, bmpinfo->verts_len_alloc, bmpinfo->verts_len);
72  bmpinfo->verts[bmpinfo->verts_len++] = v;
73  return true;
74  }
75  return false;
76 }
77 
79  BLI_bitmap *faces_tag,
80  BMFace *f)
81 {
82  const int i = BM_elem_index_get(f);
83  if (!BLI_BITMAP_TEST(faces_tag, i)) {
84  BLI_BITMAP_ENABLE(faces_tag, i);
85  GROW_ARRAY_AS_NEEDED(bmpinfo->faces, bmpinfo->faces_len_alloc, bmpinfo->faces_len);
86  bmpinfo->faces[bmpinfo->faces_len++] = f;
87  return true;
88  }
89  return false;
90 }
91 
94  const BLI_bitmap *verts_mask,
95  const int verts_mask_count)
96 {
97  /* The caller is doing something wrong if this isn't the case. */
98  BLI_assert(verts_mask_count <= bm->totvert);
99 
100  BMPartialUpdate *bmpinfo = MEM_callocN(sizeof(*bmpinfo), __func__);
101 
102  /* Reserve more edges than vertices since it's common for a grid topology
103  * to use around twice as many edges as vertices. */
104  const int default_verts_len_alloc = verts_mask_count;
105  const int default_faces_len_alloc = min_ii(bm->totface, verts_mask_count);
106 
107  /* Allocate tags instead of using #BM_ELEM_TAG because the caller may already be using tags.
108  * Further, walking over all geometry to clear the tags isn't so efficient. */
109  BLI_bitmap *verts_tag = NULL;
110  BLI_bitmap *faces_tag = NULL;
111 
112  /* Set vert inline. */
114 
115  if (params->do_normals || params->do_tessellate) {
116  /* - Extend to all vertices connected faces:
117  * In the case of tessellation this is enough.
118  *
119  * In the case of vertex normal calculation,
120  * All the relevant connectivity data can be accessed from the faces
121  * (there is no advantage in storing connected edges or vertices in this pass).
122  *
123  * NOTE: In the future it may be useful to differentiate between vertices
124  * that are directly marked (by the filter function when looping over all vertices).
125  * And vertices marked from indirect connections.
126  * This would require an extra tag array, so avoid this unless it's needed.
127  */
128 
129  /* Faces. */
130  if (bmpinfo->faces == NULL) {
131  bmpinfo->faces_len_alloc = default_faces_len_alloc;
132  bmpinfo->faces = MEM_mallocN((sizeof(BMFace *) * bmpinfo->faces_len_alloc), __func__);
133  faces_tag = BLI_BITMAP_NEW((size_t)bm->totface, __func__);
134  }
135 
136  BMVert *v;
137  BMIter iter;
138  int i;
139  BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
140  BM_elem_index_set(v, i); /* set_inline */
141  if (!BLI_BITMAP_TEST(verts_mask, i)) {
142  continue;
143  }
144  BMEdge *e_iter = v->e;
145  if (e_iter != NULL) {
146  /* Loop over edges. */
147  BMEdge *e_first = v->e;
148  do {
149  BMLoop *l_iter = e_iter->l;
150  if (e_iter->l != NULL) {
151  BMLoop *l_first = e_iter->l;
152  /* Loop over radial loops. */
153  do {
154  if (l_iter->v == v) {
155  partial_elem_face_ensure(bmpinfo, faces_tag, l_iter->f);
156  }
157  } while ((l_iter = l_iter->radial_next) != l_first);
158  }
159  } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first);
160  }
161  }
162  }
163 
164  if (params->do_normals) {
165  /* - Extend to all faces vertices:
166  * Any changes to the faces normal needs to update all surrounding vertices.
167  *
168  * - Extend to all these vertices connected edges:
169  * These and needed to access those vertices edge vectors in normal calculation logic.
170  */
171 
172  /* Vertices. */
173  if (bmpinfo->verts == NULL) {
174  bmpinfo->verts_len_alloc = default_verts_len_alloc;
175  bmpinfo->verts = MEM_mallocN((sizeof(BMVert *) * bmpinfo->verts_len_alloc), __func__);
176  verts_tag = BLI_BITMAP_NEW((size_t)bm->totvert, __func__);
177  }
178 
179  for (int i = 0; i < bmpinfo->faces_len; i++) {
180  BMFace *f = bmpinfo->faces[i];
181  BMLoop *l_iter, *l_first;
182  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
183  do {
184  partial_elem_vert_ensure(bmpinfo, verts_tag, l_iter->v);
185  } while ((l_iter = l_iter->next) != l_first);
186  }
187  }
188 
189  if (verts_tag) {
190  MEM_freeN(verts_tag);
191  }
192  if (faces_tag) {
193  MEM_freeN(faces_tag);
194  }
195 
196  bmpinfo->params = *params;
197 
198  return bmpinfo;
199 }
200 
202  BMesh *bm,
204  const BLI_bitmap *verts_mask,
205  const int verts_mask_count)
206 {
207  BMPartialUpdate *bmpinfo = MEM_callocN(sizeof(*bmpinfo), __func__);
208 
209  BLI_bitmap *verts_tag = NULL;
210  BLI_bitmap *faces_tag = NULL;
211 
212  /* It's not worth guessing a large number as isolated regions will allocate zero faces. */
213  const int default_faces_len_alloc = 1;
214 
215  int face_tag_loop_len = 0;
216 
217  if (params->do_normals || params->do_tessellate) {
218 
219  /* Faces. */
220  if (bmpinfo->faces == NULL) {
221  bmpinfo->faces_len_alloc = default_faces_len_alloc;
222  bmpinfo->faces = MEM_mallocN((sizeof(BMFace *) * bmpinfo->faces_len_alloc), __func__);
223  faces_tag = BLI_BITMAP_NEW((size_t)bm->totface, __func__);
224  }
225 
226  BMFace *f;
227  BMIter iter;
228  int i;
229  BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
230  enum { SIDE_A = (1 << 0), SIDE_B = (1 << 1) } side_flag = 0;
231  BM_elem_index_set(f, i); /* set_inline */
232  BMLoop *l_iter, *l_first;
233  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
234  do {
235  const int j = BM_elem_index_get(l_iter->v);
236  side_flag |= BLI_BITMAP_TEST(verts_mask, j) ? SIDE_A : SIDE_B;
237  if (UNLIKELY(side_flag == (SIDE_A | SIDE_B))) {
238  partial_elem_face_ensure(bmpinfo, faces_tag, f);
239  face_tag_loop_len += f->len;
240  break;
241  }
242  } while ((l_iter = l_iter->next) != l_first);
243  }
244  }
245 
246  if (params->do_normals) {
247  /* Extend to all faces vertices:
248  * Any changes to the faces normal needs to update all surrounding vertices. */
249 
250  /* Over allocate using the total number of face loops. */
251  const int default_verts_len_alloc = min_ii(bm->totvert, max_ii(1, face_tag_loop_len));
252 
253  /* Vertices. */
254  if (bmpinfo->verts == NULL) {
255  bmpinfo->verts_len_alloc = default_verts_len_alloc;
256  bmpinfo->verts = MEM_mallocN((sizeof(BMVert *) * bmpinfo->verts_len_alloc), __func__);
257  verts_tag = BLI_BITMAP_NEW((size_t)bm->totvert, __func__);
258  }
259 
260  for (int i = 0; i < bmpinfo->faces_len; i++) {
261  BMFace *f = bmpinfo->faces[i];
262  BMLoop *l_iter, *l_first;
263  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
264  do {
265  partial_elem_vert_ensure(bmpinfo, verts_tag, l_iter->v);
266  } while ((l_iter = l_iter->next) != l_first);
267  }
268 
269  /* Loose vertex support, these need special handling as loose normals depend on location. */
270  if (bmpinfo->verts_len < verts_mask_count) {
271  BMVert *v;
272  BMIter iter;
273  int i;
274  BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
275  if (BLI_BITMAP_TEST(verts_mask, i) && (BM_vert_find_first_loop(v) == NULL)) {
276  partial_elem_vert_ensure(bmpinfo, verts_tag, v);
277  }
278  }
279  }
280  }
281 
282  if (verts_tag) {
283  MEM_freeN(verts_tag);
284  }
285  if (faces_tag) {
286  MEM_freeN(faces_tag);
287  }
288 
289  bmpinfo->params = *params;
290 
291  return bmpinfo;
292 }
293 
295  BMesh *bm,
297  const int *verts_group,
298  const int verts_group_count)
299 {
300  /* Provide a quick way of visualizing which faces are being manipulated. */
301  // #define DEBUG_MATERIAL
302 
303  BMPartialUpdate *bmpinfo = MEM_callocN(sizeof(*bmpinfo), __func__);
304 
305  BLI_bitmap *verts_tag = NULL;
306  BLI_bitmap *faces_tag = NULL;
307 
308  /* It's not worth guessing a large number as isolated regions will allocate zero faces. */
309  const int default_faces_len_alloc = 1;
310 
311  int face_tag_loop_len = 0;
312 
313  if (params->do_normals || params->do_tessellate) {
314 
315  /* Faces. */
316  if (bmpinfo->faces == NULL) {
317  bmpinfo->faces_len_alloc = default_faces_len_alloc;
318  bmpinfo->faces = MEM_mallocN((sizeof(BMFace *) * bmpinfo->faces_len_alloc), __func__);
319  faces_tag = BLI_BITMAP_NEW((size_t)bm->totface, __func__);
320  }
321 
322  BMFace *f;
323  BMIter iter;
324  int i;
325  BM_ITER_MESH_INDEX (f, &iter, bm, BM_FACES_OF_MESH, i) {
326  BM_elem_index_set(f, i); /* set_inline */
327  BMLoop *l_iter, *l_first;
328  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
329  const int group_test = verts_group[BM_elem_index_get(l_iter->prev->v)];
330 #ifdef DEBUG_MATERIAL
331  f->mat_nr = 0;
332 #endif
333  do {
334  const int group_iter = verts_group[BM_elem_index_get(l_iter->v)];
335  if (UNLIKELY((group_iter != group_test) || (group_iter == -1))) {
336  partial_elem_face_ensure(bmpinfo, faces_tag, f);
337  face_tag_loop_len += f->len;
338 #ifdef DEBUG_MATERIAL
339  f->mat_nr = 1;
340 #endif
341  break;
342  }
343  } while ((l_iter = l_iter->next) != l_first);
344  }
345  }
346 
347  if (params->do_normals) {
348  /* Extend to all faces vertices:
349  * Any changes to the faces normal needs to update all surrounding vertices. */
350 
351  /* Over allocate using the total number of face loops. */
352  const int default_verts_len_alloc = min_ii(bm->totvert, max_ii(1, face_tag_loop_len));
353 
354  /* Vertices. */
355  if (bmpinfo->verts == NULL) {
356  bmpinfo->verts_len_alloc = default_verts_len_alloc;
357  bmpinfo->verts = MEM_mallocN((sizeof(BMVert *) * bmpinfo->verts_len_alloc), __func__);
358  verts_tag = BLI_BITMAP_NEW((size_t)bm->totvert, __func__);
359  }
360 
361  for (int i = 0; i < bmpinfo->faces_len; i++) {
362  BMFace *f = bmpinfo->faces[i];
363  BMLoop *l_iter, *l_first;
364  l_iter = l_first = BM_FACE_FIRST_LOOP(f);
365  do {
366  partial_elem_vert_ensure(bmpinfo, verts_tag, l_iter->v);
367  } while ((l_iter = l_iter->next) != l_first);
368  }
369 
370  /* Loose vertex support, these need special handling as loose normals depend on location. */
371  if (bmpinfo->verts_len < verts_group_count) {
372  BMVert *v;
373  BMIter iter;
374  int i;
375  BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
376  if ((verts_group[i] != 0) && (BM_vert_find_first_loop(v) == NULL)) {
377  partial_elem_vert_ensure(bmpinfo, verts_tag, v);
378  }
379  }
380  }
381  }
382 
383  if (verts_tag) {
384  MEM_freeN(verts_tag);
385  }
386  if (faces_tag) {
387  MEM_freeN(faces_tag);
388  }
389 
390  bmpinfo->params = *params;
391 
392  return bmpinfo;
393 }
394 
396 {
397  if (bmpinfo->verts) {
398  MEM_freeN(bmpinfo->verts);
399  }
400  if (bmpinfo->faces) {
401  MEM_freeN(bmpinfo->faces);
402  }
403  MEM_freeN(bmpinfo);
404 }
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_BITMAP_NEW(_num, _alloc_string)
Definition: BLI_bitmap.h:40
#define BLI_BITMAP_TEST(_bitmap, _index)
Definition: BLI_bitmap.h:64
#define BLI_BITMAP_ENABLE(_bitmap, _index)
Definition: BLI_bitmap.h:81
unsigned int BLI_bitmap
Definition: BLI_bitmap.h:16
#define BLI_INLINE
MINLINE int min_ii(int a, int b)
MINLINE int max_ii(int a, int b)
#define UNLIKELY(x)
Object is a sort of wrapper for general info.
Read Guarded memory(de)allocation.
#define BM_DISK_EDGE_NEXT(e, v)
Definition: bmesh_class.h:625
#define BM_FACE_FIRST_LOOP(p)
Definition: bmesh_class.h:622
@ BM_FACE
Definition: bmesh_class.h:386
#define BM_elem_index_get(ele)
Definition: bmesh_inline.h:110
#define BM_elem_index_set(ele, index)
Definition: bmesh_inline.h:111
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
@ BM_VERTS_OF_MESH
@ BM_FACES_OF_MESH
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
Definition: bmesh_mesh.cc:446
BLI_INLINE bool partial_elem_vert_ensure(BMPartialUpdate *bmpinfo, BLI_bitmap *verts_tag, BMVert *v)
BLI_INLINE bool partial_elem_face_ensure(BMPartialUpdate *bmpinfo, BLI_bitmap *faces_tag, BMFace *f)
#define GROW_ARRAY_AS_NEEDED(mem, len_alloc, index)
void BM_mesh_partial_destroy(BMPartialUpdate *bmpinfo)
BMPartialUpdate * BM_mesh_partial_create_from_verts_group_single(BMesh *bm, const BMPartialUpdate_Params *params, const BLI_bitmap *verts_mask, const int verts_mask_count)
BMPartialUpdate * BM_mesh_partial_create_from_verts_group_multi(BMesh *bm, const BMPartialUpdate_Params *params, const int *verts_group, const int verts_group_count)
BMPartialUpdate * BM_mesh_partial_create_from_verts(BMesh *bm, const BMPartialUpdate_Params *params, const BLI_bitmap *verts_mask, const int verts_mask_count)
BMLoop * BM_vert_find_first_loop(BMVert *v)
Definition: bmesh_query.c:297
ATTR_WARN_UNUSED_RESULT const BMVert * v
uiWidgetBaseParameters params[MAX_WIDGET_BASE_BATCH]
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_callocN)(size_t len, const char *str)
Definition: mallocn.c:31
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
struct BMLoop * l
Definition: bmesh_class.h:128
short mat_nr
Definition: bmesh_class.h:281
int len
Definition: bmesh_class.h:267
struct BMVert * v
Definition: bmesh_class.h:153
struct BMLoop * radial_next
Definition: bmesh_class.h:204
struct BMLoop * prev
Definition: bmesh_class.h:233
struct BMFace * f
Definition: bmesh_class.h:171
struct BMLoop * next
Definition: bmesh_class.h:233
BMPartialUpdate_Params params
struct BMEdge * e
Definition: bmesh_class.h:97
int totvert
Definition: bmesh_class.h:297
int totface
Definition: bmesh_class.h:297