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