Blender V5.3
bmesh_structure.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2007 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include "BLI_utildefines.hh"
12
13#include "bmesh.hh"
15
16namespace blender {
17
21
23{
24 if (e->v1 == v_src) {
25 e->v1 = v_dst;
26 e->v1_disk_link.next = e->v1_disk_link.prev = nullptr;
27 }
28 else if (e->v2 == v_src) {
29 e->v2 = v_dst;
30 e->v2_disk_link.next = e->v2_disk_link.prev = nullptr;
31 }
32 else {
33 BLI_assert(0);
34 }
35}
36
38{
39 /* swap out loops */
40 if (e->l) {
41 BMLoop *l_iter, *l_first;
42 l_iter = l_first = e->l;
43 do {
44 if (l_iter->v == v_src) {
45 l_iter->v = v_dst;
46 }
47 else if (l_iter->next->v == v_src) {
48 l_iter->next->v = v_dst;
49 }
50 else {
51 BLI_assert(l_iter->prev->v != v_src);
52 }
53 } while ((l_iter = l_iter->radial_next) != l_first);
54 }
55
56 /* swap out edges */
57 bmesh_disk_vert_replace(e, v_dst, v_src);
58}
59
61{
62 BLI_assert(e->v1 == v_src || e->v2 == v_src);
63 bmesh_disk_edge_remove(e, v_src); /* Remove `e` from `v_src` disk cycle. */
64 bmesh_disk_vert_swap(e, v_dst, v_src); /* Swap out `v_src` for `v_dst` in `e`. */
65 bmesh_disk_edge_append(e, v_dst); /* Add `e` to `v_dst` disk cycle. */
66 BLI_assert(e->v1 != e->v2);
67}
68
138
140{
141 if (!v->e) {
142 BMDiskLink *dl1 = bmesh_disk_edge_link_from_vert(e, v);
143
144 v->e = e;
145 dl1->next = dl1->prev = e;
146 }
147 else {
148 BMDiskLink *dl1, *dl2, *dl3;
149
150 dl1 = bmesh_disk_edge_link_from_vert(e, v);
151 dl2 = bmesh_disk_edge_link_from_vert(v->e, v);
152 dl3 = dl2->prev ? bmesh_disk_edge_link_from_vert(dl2->prev, v) : nullptr;
153
154 dl1->next = v->e;
155 dl1->prev = dl2->prev;
156
157 dl2->prev = e;
158 if (dl3) {
159 dl3->next = e;
160 }
161 }
162}
163
165{
166 BMDiskLink *dl1, *dl2;
167
168 dl1 = bmesh_disk_edge_link_from_vert(e, v);
169 if (dl1->prev) {
170 dl2 = bmesh_disk_edge_link_from_vert(dl1->prev, v);
171 dl2->next = dl1->next;
172 }
173
174 if (dl1->next) {
175 dl2 = bmesh_disk_edge_link_from_vert(dl1->next, v);
176 dl2->prev = dl1->prev;
177 }
178
179 if (v->e == e) {
180 v->e = (e != dl1->next) ? dl1->next : nullptr;
181 }
182
183 dl1->next = dl1->prev = nullptr;
184}
185
187{
188 if (v1->e) {
189 BMEdge *e_iter, *e_first;
190 e_first = e_iter = v1->e;
191
192 do {
193 if (BM_verts_in_edge(v1, v2, e_iter)) {
194 return e_iter;
195 }
196 } while ((e_iter = bmesh_disk_edge_next(e_iter, v1)) != e_first);
197 }
198
199 return nullptr;
200}
201
203{
204 int count = 0;
205 if (v->e) {
206 BMEdge *e_first, *e_iter;
207 e_iter = e_first = v->e;
208 do {
209 count++;
210 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
211 }
212 return count;
213}
214
215int bmesh_disk_count_at_most(const BMVert *v, const int count_max)
216{
217 int count = 0;
218 if (v->e) {
219 BMEdge *e_first, *e_iter;
220 e_iter = e_first = v->e;
221 do {
222 count++;
223 if (count == count_max) {
224 break;
225 }
226 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
227 }
228 return count;
229}
230
232{
233 BMEdge *e_iter;
234
235 if (!BM_vert_in_edge(e, v)) {
236 return false;
237 }
238 if (len == 0 || bmesh_disk_count_at_most(v, len + 1) != len) {
239 return false;
240 }
241
242 e_iter = e;
243 do {
244 if (len != 1 && bmesh_disk_edge_prev(e_iter, v) == e_iter) {
245 return false;
246 }
247 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e);
248
249 return true;
250}
251
253{
254 /* is there an edge on this vert at all */
255 int count = 0;
256 if (v->e) {
257 BMEdge *e_first, *e_iter;
258
259 /* first, loop around edge */
260 e_first = e_iter = v->e;
261 do {
262 if (e_iter->l) {
263 count += bmesh_radial_facevert_count(e_iter->l, v);
264 }
265 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
266 }
267 return count;
268}
269
270int bmesh_disk_facevert_count_at_most(const BMVert *v, const int count_max)
271{
272 /* is there an edge on this vert at all */
273 int count = 0;
274 if (v->e) {
275 BMEdge *e_first, *e_iter;
276
277 /* first, loop around edge */
278 e_first = e_iter = v->e;
279 do {
280 if (e_iter->l) {
281 count += bmesh_radial_facevert_count_at_most(e_iter->l, v, count_max - count);
282 if (count == count_max) {
283 break;
284 }
285 }
286 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
287 }
288 return count;
289}
290
292{
293 const BMEdge *e_iter = e;
294 do {
295 if (e_iter->l != nullptr) {
296 return const_cast<BMEdge *>((e_iter->l->v == v) ? e_iter : e_iter->l->next->e);
297 }
298 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e);
299 return nullptr;
300}
301
303{
304 const BMEdge *e_iter = e;
305 do {
306 if (e_iter->l != nullptr) {
307 return (e_iter->l->v == v) ? e_iter->l : e_iter->l->next;
308 }
309 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e);
310 return nullptr;
311}
312
314{
315 const BMEdge *e_iter = e;
316 do {
317 if (!BM_elem_flag_test(e_iter, BM_ELEM_HIDDEN)) {
318 if (e_iter->l != nullptr) {
319 BMLoop *l_iter, *l_first;
320 l_iter = l_first = e_iter->l;
321 do {
322 if (!BM_elem_flag_test(l_iter->f, BM_ELEM_HIDDEN)) {
323 return (l_iter->v == v) ? l_iter : l_iter->next;
324 }
325 } while ((l_iter = l_iter->radial_next) != l_first);
326 }
327 }
328 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e);
329 return nullptr;
330}
331
333{
334 BMEdge *e_find;
335 e_find = bmesh_disk_edge_next(e, v);
336 do {
337 if (e_find->l && bmesh_radial_facevert_check(e_find->l, v)) {
338 return e_find;
339 }
340 } while ((e_find = bmesh_disk_edge_next(e_find, v)) != e);
341 return const_cast<BMEdge *>(e);
342}
343
345{
346 BMLoop *l_iter = l;
347 int i = 0;
348
349 if (bmesh_radial_length(l) != radlen) {
350 return false;
351 }
352
353 do {
354 if (!l_iter) [[unlikely]] {
355 BMESH_ASSERT(0);
356 return false;
357 }
358
359 if (l_iter->e != l->e) {
360 return false;
361 }
362 if (!ELEM(l_iter->v, l->e->v1, l->e->v2)) {
363 return false;
364 }
365
366 if (i > BM_LOOP_RADIAL_MAX) [[unlikely]] {
367 BMESH_ASSERT(0);
368 return false;
369 }
370
371 i++;
372 } while ((l_iter = l_iter->radial_next) != l);
373
374 return true;
375}
376
378{
379 if (e->l == nullptr) {
380 e->l = l;
382 }
383 else {
384 l->radial_prev = e->l;
385 l->radial_next = e->l->radial_next;
386
387 e->l->radial_next->radial_prev = l;
388 e->l->radial_next = l;
389
390 e->l = l;
391 }
392
393 if (l->e && l->e != e) [[unlikely]] {
394 /* l is already in a radial cycle for a different edge */
395 BMESH_ASSERT(0);
396 }
397
398 l->e = e;
399}
400
402{
403 /* if e is non-nullptr, l must be in the radial cycle of e */
404 if (e != l->e) [[unlikely]] {
405 BMESH_ASSERT(0);
406 }
407
408 if (l->radial_next != l) {
409 if (l == e->l) {
410 e->l = l->radial_next;
411 }
412
415 }
416 else {
417 if (l == e->l) {
418 e->l = nullptr;
419 }
420 else {
421 BMESH_ASSERT(0);
422 }
423 }
424
425 /* l is no longer in a radial cycle; empty the links
426 * to the cycle and the link back to an edge */
427 l->radial_next = l->radial_prev = nullptr;
428 l->e = nullptr;
429}
430
432{
433 if (l->radial_next != l) {
436 }
437
438 /* l is no longer in a radial cycle; empty the links
439 * to the cycle and the link back to an edge */
440 l->radial_next = l->radial_prev = nullptr;
441 l->e = nullptr;
442}
443
445{
446 const BMLoop *l_iter;
447 l_iter = l;
448 do {
449 if (l_iter->v == v) {
450 return const_cast<BMLoop *>(l_iter);
451 }
452 } while ((l_iter = l_iter->radial_next) != l);
453 return nullptr;
454}
455
457{
458 BMLoop *l_iter;
459 l_iter = l->radial_next;
460 do {
461 if (l_iter->v == v) {
462 return l_iter;
463 }
464 } while ((l_iter = l_iter->radial_next) != l);
465 return const_cast<BMLoop *>(l);
466}
467
469{
470 const BMLoop *l_iter = l;
471 int i = 0;
472
473 if (!l) {
474 return 0;
475 }
476
477 do {
478 if (!l_iter) [[unlikely]] {
479 /* Radial cycle is broken (not a circular loop). */
480 BMESH_ASSERT(0);
481 return 0;
482 }
483
484 i++;
485 if (i >= BM_LOOP_RADIAL_MAX) [[unlikely]] {
486 BMESH_ASSERT(0);
487 return -1;
488 }
489 } while ((l_iter = l_iter->radial_next) != l);
490
491 return i;
492}
493
495{
496 const BMLoop *l_iter;
497 int count = 0;
498 l_iter = l;
499 do {
500 if (l_iter->v == v) {
501 count++;
502 }
503 } while ((l_iter = l_iter->radial_next) != l);
504
505 return count;
506}
507
508int bmesh_radial_facevert_count_at_most(const BMLoop *l, const BMVert *v, const int count_max)
509{
510 const BMLoop *l_iter;
511 int count = 0;
512 l_iter = l;
513 do {
514 if (l_iter->v == v) {
515 count++;
516 if (count == count_max) {
517 break;
518 }
519 }
520 } while ((l_iter = l_iter->radial_next) != l);
521
522 return count;
523}
524
526{
527 const BMLoop *l_iter;
528 l_iter = l;
529 do {
530 if (l_iter->v == v) {
531 return true;
532 }
533 } while ((l_iter = l_iter->radial_next) != l);
534
535 return false;
536}
537
539{
540 int i;
541 int len = f->len;
542 BMLoop *l_iter, *l_first;
543
544 l_first = BM_FACE_FIRST_LOOP(f);
545
546 if (l_first == nullptr) {
547 return false;
548 }
549
550 /* Validate that the face loop cycle is the length specified by f->len */
551 for (i = 1, l_iter = l_first->next; i < len; i++, l_iter = l_iter->next) {
552 if ((l_iter->f != f) || (l_iter == l_first)) {
553 return false;
554 }
555 }
556 if (l_iter != l_first) {
557 return false;
558 }
559
560 /* Validate the loop->prev links also form a cycle of length f->len */
561 for (i = 1, l_iter = l_first->prev; i < len; i++, l_iter = l_iter->prev) {
562 if (l_iter == l_first) {
563 return false;
564 }
565 }
566 if (l_iter != l_first) {
567 return false;
568 }
569
570 return true;
571}
572
573} // namespace blender
#define ELEM(...)
#define BM_LOOP_RADIAL_MAX
#define BM_FACE_FIRST_LOOP(p)
#define BMESH_ASSERT(a)
#define BM_elem_flag_test(ele, hflag)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
Definition math_dual.h:263
BMesh Iterators.
bool bmesh_radial_facevert_check(const BMLoop *l, const BMVert *v)
RADIAL CHECK FACE VERT.
void bmesh_disk_edge_remove(BMEdge *e, BMVert *v)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void bmesh_radial_loop_append(BMEdge *e, BMLoop *l)
bool bmesh_disk_validate(int len, BMEdge *e, BMVert *v)
ATTR_WARN_UNUSED_RESULT const BMLoop * l
bool bmesh_radial_validate(int radlen, BMLoop *l)
void bmesh_edge_vert_swap(BMEdge *e, BMVert *v_dst, BMVert *v_src)
int bmesh_disk_facevert_count(const BMVert *v)
DISK COUNT FACE VERT.
void bmesh_disk_vert_swap(BMEdge *e, BMVert *v_dst, BMVert *v_src)
bool bmesh_loop_validate(BMFace *f)
ATTR_WARN_UNUSED_RESULT const BMVert * v
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void bmesh_radial_loop_remove(BMEdge *e, BMLoop *l)
BMESH RADIAL REMOVE LOOP.
BMLoop * bmesh_disk_faceloop_find_first(const BMEdge *e, const BMVert *v)
int bmesh_radial_length(const BMLoop *l)
int bmesh_radial_facevert_count_at_most(const BMLoop *l, const BMVert *v, const int count_max)
int bmesh_disk_count_at_most(const BMVert *v, int count_max)
void bmesh_disk_vert_replace(BMEdge *e, BMVert *v_dst, BMVert *v_src)
BMEdge * bmesh_disk_faceedge_find_first(const BMEdge *e, const BMVert *v)
FIND FIRST FACE EDGE.
int bmesh_disk_count(const BMVert *v)
void bmesh_disk_edge_append(BMEdge *e, BMVert *v)
BLI_INLINE bool BM_verts_in_edge(const BMVert *v1, const BMVert *v2, const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BMEdge * bmesh_disk_faceedge_find_next(const BMEdge *e, const BMVert *v)
BMLoop * bmesh_radial_faceloop_find_first(const BMLoop *l, const BMVert *v)
BME RADIAL FIND FIRST FACE VERT.
BLI_INLINE BMEdge * bmesh_disk_edge_prev(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMVert * v2
BMLoop * bmesh_radial_faceloop_find_next(const BMLoop *l, const BMVert *v)
BLI_INLINE BMEdge * bmesh_disk_edge_next(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
int bmesh_disk_facevert_count_at_most(const BMVert *v, const int count_max)
BMEdge * bmesh_disk_edge_exists(const BMVert *v1, const BMVert *v2)
int bmesh_radial_facevert_count(const BMLoop *l, const BMVert *v)
RADIAL COUNT FACE VERT.
BMLoop * bmesh_disk_faceloop_find_first_visible(const BMEdge *e, const BMVert *v)
void bmesh_radial_loop_unlink(BMLoop *l)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
struct BMLoop * l
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
struct BMEdge * e
struct BMLoop * radial_next
struct BMLoop * radial_prev