Blender V5.3
bmesh_mesh_partial_update.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
37
38#include "MEM_guardedalloc.h"
39
40#include "BLI_bit_vector.hh"
41#include "BLI_math_base_c.hh"
42
43#include "bmesh.hh"
44
45namespace blender {
46
48 MutableBitSpan verts_tag,
49 BMVert *v)
50{
51 const int i = BM_elem_index_get(v);
52 if (!verts_tag[i]) {
53 verts_tag[i].set();
54 bmpinfo->verts.append(v);
55 return true;
56 }
57 return false;
58}
59
61 MutableBitSpan faces_tag,
62 BMFace *f)
63{
64 const int i = BM_elem_index_get(f);
65 if (!faces_tag[i]) {
66 faces_tag[i].set();
67 bmpinfo->faces.append(f);
68 return true;
69 }
70 return false;
71}
72
74 const BMPartialUpdate_Params &params,
75 const BitSpan verts_mask,
76 const int verts_mask_count)
77{
78 /* The caller is doing something wrong if this isn't the case. */
79 BLI_assert(verts_mask_count <= bm.totvert);
80
81 BMPartialUpdate *bmpinfo = MEM_new<BMPartialUpdate>(__func__);
82
83 /* Reserve more edges than vertices since it's common for a grid topology
84 * to use around twice as many edges as vertices. */
85 const int default_verts_len_alloc = verts_mask_count;
86 const int default_faces_len_alloc = min_ii(bm.totface, verts_mask_count);
87
88 /* Allocate tags instead of using #BM_ELEM_TAG because the caller may already be using tags.
89 * Further, walking over all geometry to clear the tags isn't so efficient. */
90 BitVector<> verts_tag;
91 BitVector<> faces_tag;
92
93 /* Set vert inline. */
95
96 if (params.do_normals || params.do_tessellate) {
97 /* - Extend to all vertices connected faces:
98 * In the case of tessellation this is enough.
99 *
100 * In the case of vertex normal calculation,
101 * All the relevant connectivity data can be accessed from the faces
102 * (there is no advantage in storing connected edges or vertices in this pass).
103 *
104 * NOTE: In the future it may be useful to differentiate between vertices
105 * that are directly marked (by the filter function when looping over all vertices).
106 * And vertices marked from indirect connections.
107 * This would require an extra tag array, so avoid this unless it's needed.
108 */
109
110 /* Faces. */
111 bmpinfo->faces.reserve(default_faces_len_alloc);
112 faces_tag.resize(bm.totface);
113
114 BMVert *v;
115 BMIter iter;
116 int i;
117 BM_ITER_MESH_INDEX (v, &iter, &bm, BM_VERTS_OF_MESH, i) {
118 BM_elem_index_set(v, i); /* set_inline */
119 if (!verts_mask[i]) {
120 continue;
121 }
122 BMEdge *e_iter = v->e;
123 if (e_iter != nullptr) {
124 /* Loop over edges. */
125 BMEdge *e_first = v->e;
126 do {
127 BMLoop *l_iter = e_iter->l;
128 if (e_iter->l != nullptr) {
129 BMLoop *l_first = e_iter->l;
130 /* Loop over radial loops. */
131 do {
132 if (l_iter->v == v) {
133 partial_elem_face_ensure(bmpinfo, faces_tag, l_iter->f);
134 }
135 } while ((l_iter = l_iter->radial_next) != l_first);
136 }
137 } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first);
138 }
139 }
140 }
141
142 if (params.do_normals) {
143 /* - Extend to all faces vertices:
144 * Any changes to the faces normal needs to update all surrounding vertices.
145 *
146 * - Extend to all these vertices connected edges:
147 * These and needed to access those vertices edge vectors in normal calculation logic.
148 */
149
150 /* Vertices. */
151 bmpinfo->verts.reserve(default_verts_len_alloc);
152 verts_tag.resize(bm.totvert);
153
154 for (const BMFace *f : bmpinfo->faces) {
155 BMLoop *l_iter, *l_first;
156 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
157 do {
158 partial_elem_vert_ensure(bmpinfo, verts_tag, l_iter->v);
159 } while ((l_iter = l_iter->next) != l_first);
160 }
161 }
162
163 bmpinfo->params = params;
164
165 return bmpinfo;
166}
167
169 BMesh &bm,
170 const BMPartialUpdate_Params &params,
171 const BitSpan verts_mask,
172 const int verts_mask_count)
173{
174 BMPartialUpdate *bmpinfo = MEM_new<BMPartialUpdate>(__func__);
175
176 BitVector<> verts_tag;
177 BitVector<> faces_tag;
178
179 int face_tag_loop_len = 0;
180
181 if (params.do_normals || params.do_tessellate) {
182 faces_tag.resize(bm.totface);
183
184 BMFace *f;
185 BMIter iter;
186 int i;
187 BM_ITER_MESH_INDEX (f, &iter, &bm, BM_FACES_OF_MESH, i) {
188 enum Side { SIDE_A = (1 << 0), SIDE_B = (1 << 1) } side_flag = Side(0);
189 BM_elem_index_set(f, i); /* set_inline */
190 BMLoop *l_iter, *l_first;
191 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
192 do {
193 const int j = BM_elem_index_get(l_iter->v);
194 side_flag = Side(side_flag | (verts_mask[j].test() ? SIDE_A : SIDE_B));
195 if (side_flag == (SIDE_A | SIDE_B)) [[unlikely]] {
196 partial_elem_face_ensure(bmpinfo, faces_tag, f);
197 face_tag_loop_len += f->len;
198 break;
199 }
200 } while ((l_iter = l_iter->next) != l_first);
201 }
202 }
203
204 if (params.do_normals) {
205 /* Extend to all faces vertices:
206 * Any changes to the faces normal needs to update all surrounding vertices. */
207
208 /* Over allocate using the total number of face loops. */
209 bmpinfo->verts.reserve(min_ii(bm.totvert, max_ii(1, face_tag_loop_len)));
210 verts_tag.resize(bm.totvert);
211
212 for (BMFace *f : bmpinfo->faces) {
213 BMLoop *l_iter, *l_first;
214 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
215 do {
216 partial_elem_vert_ensure(bmpinfo, verts_tag, l_iter->v);
217 } while ((l_iter = l_iter->next) != l_first);
218 }
219
220 /* Loose vertex support, these need special handling as loose normals depend on location. */
221 if (bmpinfo->verts.size() < verts_mask_count) {
222 BMVert *v;
223 BMIter iter;
224 int i;
225 BM_ITER_MESH_INDEX (v, &iter, &bm, BM_VERTS_OF_MESH, i) {
226 if (verts_mask[i] && (BM_vert_find_first_loop(v) == nullptr)) {
227 partial_elem_vert_ensure(bmpinfo, verts_tag, v);
228 }
229 }
230 }
231 }
232
233 bmpinfo->params = params;
234
235 return bmpinfo;
236}
237
239 BMesh &bm,
240 const BMPartialUpdate_Params &params,
241 const Span<int> verts_group,
242 const int verts_group_count)
243{
244 /* Provide a quick way of visualizing which faces are being manipulated. */
245 // #define DEBUG_MATERIAL
246
247 BMPartialUpdate *bmpinfo = MEM_new<BMPartialUpdate>(__func__);
248
249 BitVector<> verts_tag;
250 BitVector<> faces_tag;
251
252 int face_tag_loop_len = 0;
253
254 if (params.do_normals || params.do_tessellate) {
255 faces_tag.resize(bm.totface);
256
257 BMFace *f;
258 BMIter iter;
259 int i;
260 BM_ITER_MESH_INDEX (f, &iter, &bm, BM_FACES_OF_MESH, i) {
261 BM_elem_index_set(f, i); /* set_inline */
262 BMLoop *l_iter, *l_first;
263 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
264 const int group_test = verts_group[BM_elem_index_get(l_iter->prev->v)];
265#ifdef DEBUG_MATERIAL
266 f->mat_nr = 0;
267#endif
268 do {
269 const int group_iter = verts_group[BM_elem_index_get(l_iter->v)];
270 if ((group_iter != group_test) || (group_iter == -1)) [[unlikely]] {
271 partial_elem_face_ensure(bmpinfo, faces_tag, f);
272 face_tag_loop_len += f->len;
273#ifdef DEBUG_MATERIAL
274 f->mat_nr = 1;
275#endif
276 break;
277 }
278 } while ((l_iter = l_iter->next) != l_first);
279 }
280 }
281
282 if (params.do_normals) {
283 /* Extend to all faces vertices:
284 * Any changes to the faces normal needs to update all surrounding vertices. */
285
286 /* Over allocate using the total number of face loops. */
287 bmpinfo->verts.reserve(min_ii(bm.totvert, max_ii(1, face_tag_loop_len)));
288 verts_tag.resize(bm.totvert);
289
290 for (BMFace *f : bmpinfo->faces) {
291 BMLoop *l_iter, *l_first;
292 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
293 do {
294 partial_elem_vert_ensure(bmpinfo, verts_tag, l_iter->v);
295 } while ((l_iter = l_iter->next) != l_first);
296 }
297
298 /* Loose vertex support, these need special handling as loose normals depend on location. */
299 if (bmpinfo->verts.size() < verts_group_count) {
300 BMVert *v;
301 BMIter iter;
302 int i;
303 BM_ITER_MESH_INDEX (v, &iter, &bm, BM_VERTS_OF_MESH, i) {
304 if ((verts_group[i] != 0) && (BM_vert_find_first_loop(v) == nullptr)) {
305 partial_elem_vert_ensure(bmpinfo, verts_tag, v);
306 }
307 }
308 }
309 }
310
311 bmpinfo->params = params;
312
313 return bmpinfo;
314}
315
317{
318 MEM_delete(bmpinfo);
319}
320
321} // namespace blender
Read Blender memory allocation and freeing.
#define BLI_INLINE
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_index_get(ele)
#define BM_elem_index_set(ele, index)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
void resize(const int64_t new_size_in_bits, const bool value=false)
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
BMPartialUpdate * BM_mesh_partial_create_from_verts_group_multi(BMesh &bm, const BMPartialUpdate_Params &params, const Span< int > verts_group, const int verts_group_count)
MINLINE int max_ii(int a, int b)
ATTR_WARN_UNUSED_RESULT const BMVert * v
BMLoop * BM_vert_find_first_loop(BMVert *v)
BLI_INLINE bool partial_elem_face_ensure(BMPartialUpdate *bmpinfo, MutableBitSpan faces_tag, BMFace *f)
BLI_INLINE bool partial_elem_vert_ensure(BMPartialUpdate *bmpinfo, MutableBitSpan verts_tag, BMVert *v)
void BM_mesh_partial_destroy(BMPartialUpdate *bmpinfo)
BMPartialUpdate * BM_mesh_partial_create_from_verts(BMesh &bm, const BMPartialUpdate_Params &params, const BitSpan verts_mask, const int verts_mask_count)
BMPartialUpdate * BM_mesh_partial_create_from_verts_group_single(BMesh &bm, const BMPartialUpdate_Params &params, const BitSpan verts_mask, const int verts_mask_count)
MINLINE int min_ii(int a, int b)
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f