Blender  V3.3
bmesh_bisect_plane.c
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
16 #include <limits.h>
17 
18 #include "MEM_guardedalloc.h"
19 
20 #include "BLI_alloca.h"
21 #include "BLI_linklist.h"
22 #include "BLI_linklist_stack.h"
23 #include "BLI_math.h"
24 #include "BLI_utildefines.h"
25 #include "BLI_utildefines_stack.h"
26 
27 #include "bmesh.h"
28 #include "bmesh_bisect_plane.h" /* Own include. */
29 
30 #include "BLI_strict_flags.h" /* Keep last. */
31 
32 /* -------------------------------------------------------------------- */
36 static short plane_point_test_v3(const float plane[4],
37  const float co[3],
38  const float eps,
39  float *r_depth)
40 {
41  const float f = plane_point_side_v3(plane, co);
42  *r_depth = f;
43 
44  if (f <= -eps) {
45  return -1;
46  }
47  if (f >= eps) {
48  return 1;
49  }
50  return 0;
51 }
52 
55 /* -------------------------------------------------------------------- */
63 #define BM_VERT_DIR(v) ((short *)(&(v)->head.index))[0] /* Direction -1/0/1 */
64 #define BM_VERT_SKIP(v) ((short *)(&(v)->head.index))[1] /* Skip Vert 0/1 */
65 #define BM_VERT_DIST(v) ((v)->no[0]) /* Distance from the plane. */
66 #define BM_VERT_SORTVAL(v) ((v)->no[1]) /* Temp value for sorting. */
67 #define BM_VERT_LOOPINDEX(v) /* The verts index within a face (temp var) */ \
68  (*((uint *)(&(v)->no[2])))
69 
72 /* -------------------------------------------------------------------- */
81 {
83 }
85 {
87 }
89 {
90  return (BM_elem_flag_test(v, BM_ELEM_TAG) != 0);
91 }
92 
93 BLI_INLINE bool vert_pair_adjacent_in_orig_face(BMVert *v_a, BMVert *v_b, const uint f_len_orig)
94 {
95  const uint delta = (uint)abs((int)BM_VERT_LOOPINDEX(v_a) - (int)BM_VERT_LOOPINDEX(v_b));
96  return ELEM(delta, 1, (uint)(f_len_orig - 1));
97 }
98 
101 {
103 }
105 {
107 }
109 {
110  return (BM_elem_flag_test(e, BM_ELEM_TAG) != 0);
111 }
112 
115 {
117 }
119 {
121 }
123 {
124  return (BM_elem_flag_test(f, BM_ELEM_TAG) == 0);
125 }
126 
129 /* -------------------------------------------------------------------- */
133 static int bm_vert_sortval_cb(const void *v_a_v, const void *v_b_v)
134 {
135  const float val_a = BM_VERT_SORTVAL(*((BMVert **)v_a_v));
136  const float val_b = BM_VERT_SORTVAL(*((BMVert **)v_b_v));
137 
138  if (val_a > val_b) {
139  return 1;
140  }
141  if (val_a < val_b) {
142  return -1;
143  }
144  return 0;
145 }
146 
148  BMesh *bm, BMFace *f, const float plane[4], const short oflag_center, const short oflag_new)
149 {
150  /* Unlikely more than 2 verts are needed. */
151  const uint f_len_orig = (uint)f->len;
152  BMVert **vert_split_arr = BLI_array_alloca(vert_split_arr, f_len_orig);
153  STACK_DECLARE(vert_split_arr);
154  BMLoop *l_iter, *l_first;
155  bool use_dirs[3] = {false, false, false};
156  bool is_inside = false;
157  /* True when the face contains one or more edges with both it's vertices on the plane.
158  * When set, centered loops are walked over to check if they need to be skipped. */
159  bool face_has_center_edge = false;
160 
161  STACK_INIT(vert_split_arr, f_len_orig);
162 
163  l_first = BM_FACE_FIRST_LOOP(f);
164 
165  /* Add plane-aligned verts to the stack and check we have verts from both sides in this face
166  * (that the face doesn't only have boundary verts on the plane for eg). */
167  l_iter = l_first;
168  do {
169  if (vert_is_center_test(l_iter->v)) {
170  BLI_assert(BM_VERT_DIR(l_iter->v) == 0);
171 
172  /* If both are -1 or 1, or both are zero: don't flip 'inside' var while walking. */
173  BM_VERT_SKIP(l_iter->v) = (((BM_VERT_DIR(l_iter->prev->v) ^ BM_VERT_DIR(l_iter->next->v))) ==
174  0);
175 
176  STACK_PUSH(vert_split_arr, l_iter->v);
177 
178  if (face_has_center_edge == false) {
179  if (vert_is_center_test(l_iter->prev->v)) {
180  face_has_center_edge = true;
181  }
182  }
183  }
184  use_dirs[BM_VERT_DIR(l_iter->v) + 1] = true;
185  } while ((l_iter = l_iter->next) != l_first);
186 
187  if ((STACK_SIZE(vert_split_arr) > 1) && (use_dirs[0] && use_dirs[2])) {
188  if (LIKELY(STACK_SIZE(vert_split_arr) == 2)) {
189  BMLoop *l_new;
190  BMLoop *l_a, *l_b;
191 
192  l_a = BM_face_vert_share_loop(f, vert_split_arr[0]);
193  l_b = BM_face_vert_share_loop(f, vert_split_arr[1]);
194 
195  /* Common case, just cut the face once. */
196  BM_face_split(bm, f, l_a, l_b, &l_new, NULL, true);
197  if (l_new) {
198  if (oflag_center | oflag_new) {
199  BMO_edge_flag_enable(bm, l_new->e, oflag_center | oflag_new);
200  }
201  if (oflag_new) {
202  BMO_face_flag_enable(bm, l_new->f, oflag_new);
203  }
204  }
205  }
206  else {
207  /* Less common case, _complicated_ we need to calculate how to do multiple cuts. */
208 
209  uint i = 0;
210 
211  /* ---- */
212  /* Check contiguous spans of centered vertices (skipping when necessary). */
213  if (face_has_center_edge) {
214 
215  /* Loop indices need to be set for adjacency checks. */
216  l_iter = l_first;
217  do {
218  BM_VERT_LOOPINDEX(l_iter->v) = i++;
219  } while ((l_iter = l_iter->next) != l_first);
220 
221  /* Start out on a non-centered vertex so a span of centered vertices can be looped over
222  * without having to scan backwards as well as forwards. */
223  BMLoop *l_first_non_center = l_first;
224  while (vert_is_center_test(l_first_non_center->v)) {
225  l_first_non_center = l_first_non_center->next;
226  }
227 
228  l_iter = l_first_non_center;
229  do {
230  if (BM_VERT_SKIP(l_iter->v)) {
231  continue;
232  }
233  /* No need to check the previous as the iteration starts on a non-centered vertex. */
234  if (!(vert_is_center_test(l_iter->v) && vert_is_center_test(l_iter->next->v))) {
235  continue;
236  }
237 
238  /* Walk over the next loops as long as they are centered. */
239  BMLoop *l_prev = l_iter->prev;
240  BMLoop *l_next = l_iter->next->next;
241  /* No need to scan the previous vertices,
242  * these will have been dealt with in previous steps. */
243  BLI_assert(!vert_is_center_test(l_prev->v));
244  while (vert_is_center_test(l_next->v)) {
245  l_next = l_next->next;
246  }
247 
248  /* Skip all vertices when the edges connected to the beginning/end
249  * of the range are on a different side of the bisecting plane. */
250  if (!(BM_VERT_DIR(l_prev->v) ^ BM_VERT_DIR(l_next->v))) {
251  BLI_assert(!vert_is_center_test(l_prev->v));
252  l_iter = l_prev->next;
253  while (l_iter != l_next) {
254  BLI_assert(vert_is_center_test(l_iter->v));
255  BM_VERT_SKIP(l_iter->v) = true;
256  l_iter = l_iter->next;
257  }
258  }
259  /* Step over the span already handled, even if skip wasn't set. */
260  l_iter = l_next->prev;
261  } while ((l_iter = l_iter->next) != l_first_non_center);
262  }
263 
264  float(*face_verts_proj_2d)[2] = BLI_array_alloca(face_verts_proj_2d, f_len_orig);
265  float axis_mat[3][3];
266 
267  BMFace **face_split_arr = BLI_array_alloca(face_split_arr, STACK_SIZE(vert_split_arr));
268  STACK_DECLARE(face_split_arr);
269 
270  float sort_dir[3];
271 
272  /* ---- */
273  /* Calculate the direction to sort verts in the face intersecting the plane */
274 
275  /* The exact direction isn't important, vertices just need to be sorted across the face.
276  * (`sort_dir` could be flipped either way). */
277  cross_v3_v3v3(sort_dir, f->no, plane);
278  if (UNLIKELY(normalize_v3(sort_dir) == 0.0f)) {
279  /* find any 2 verts and get their direction */
280  for (i = 0; i < STACK_SIZE(vert_split_arr); i++) {
281  if (!equals_v3v3(vert_split_arr[0]->co, vert_split_arr[i]->co)) {
282  sub_v3_v3v3(sort_dir, vert_split_arr[0]->co, vert_split_arr[i]->co);
283  normalize_v3(sort_dir);
284  }
285  }
286  if (UNLIKELY(i == STACK_SIZE(vert_split_arr))) {
287  /* Ok, we can't do anything useful here,
288  * face has no area or so, bail out, this is highly unlikely but not impossible. */
289  goto finally;
290  }
291  }
292 
293  /* ---- */
294  /* Calculate 2d coords to use for intersection checks */
295 
296  /* Get the faces 2d coords. */
298  axis_dominant_v3_to_m3(axis_mat, f->no);
299 
300  l_iter = l_first;
301  i = 0;
302  do {
303  mul_v2_m3v3(face_verts_proj_2d[i], axis_mat, l_iter->v->co);
304  i++;
305  } while ((l_iter = l_iter->next) != l_first);
306 
307  /* ---- */
308  /* Sort the verts across the face from one side to another. */
309  for (i = 0; i < STACK_SIZE(vert_split_arr); i++) {
310  BMVert *v = vert_split_arr[i];
311  BM_VERT_SORTVAL(v) = dot_v3v3(sort_dir, v->co);
312  }
313 
314  qsort(
315  vert_split_arr, STACK_SIZE(vert_split_arr), sizeof(*vert_split_arr), bm_vert_sortval_cb);
316 
317  /* ---- */
318  /* Split the face across sorted splits. */
319 
320  /* NOTE: we don't know which face gets which splits,
321  * so at the moment we have to search all faces for the vert pair,
322  * while not all that nice, typically there are < 5 resulting faces,
323  * so its not _that_ bad. */
324 
325  STACK_INIT(face_split_arr, STACK_SIZE(vert_split_arr));
326  STACK_PUSH(face_split_arr, f);
327 
328  for (i = 0; i < STACK_SIZE(vert_split_arr) - 1; i++) {
329  BMVert *v_a = vert_split_arr[i];
330  BMVert *v_b = vert_split_arr[i + 1];
331 
332  if (face_has_center_edge) {
333  if (vert_pair_adjacent_in_orig_face(v_a, v_b, f_len_orig)) {
334  continue;
335  }
336  }
337 
338  if (!BM_VERT_SKIP(v_a)) {
339  is_inside = !is_inside;
340  }
341 
342  if (is_inside) {
343  BMLoop *l_a, *l_b;
344  bool found = false;
345  uint j;
346 
347  for (j = 0; j < STACK_SIZE(face_split_arr); j++) {
348  /* It would be nice to avoid loop lookup here,
349  * but we need to know which face the verts are in. */
350  if ((l_a = BM_face_vert_share_loop(face_split_arr[j], v_a)) &&
351  (l_b = BM_face_vert_share_loop(face_split_arr[j], v_b))) {
352  found = true;
353  break;
354  }
355  }
356 
357  /* Ideally won't happen, but it can for self-intersecting faces. */
358  // BLI_assert(found == true);
359 
360  /* In fact this simple test is good enough, test if the loops are adjacent. */
361  if (found && !BM_loop_is_adjacent(l_a, l_b)) {
362  BMLoop *l_new;
363  BMFace *f_tmp;
364  f_tmp = BM_face_split(bm, face_split_arr[j], l_a, l_b, &l_new, NULL, true);
365 
366  if (l_new) {
367  if (oflag_center | oflag_new) {
368  BMO_edge_flag_enable(bm, l_new->e, oflag_center | oflag_new);
369  }
370  if (oflag_new) {
371  BMO_face_flag_enable(bm, l_new->f, oflag_new);
372  }
373  }
374 
375  if (f_tmp) {
376  if (f_tmp != face_split_arr[j]) {
377  STACK_PUSH(face_split_arr, f_tmp);
378  BLI_assert(STACK_SIZE(face_split_arr) <= STACK_SIZE(vert_split_arr));
379  }
380  }
381  }
382  }
383  else {
384  // printf("no intersect\n");
385  }
386  }
387  }
388  }
389 
390 finally:
391  (void)vert_split_arr;
392 }
393 
396 /* -------------------------------------------------------------------- */
401  const float plane[4],
402  const bool use_snap_center,
403  const bool use_tag,
404  const short oflag_center,
405  const short oflag_new,
406  const float eps)
407 {
408  uint einput_len;
409  uint i;
410  BMEdge **edges_arr = MEM_mallocN(sizeof(*edges_arr) * (size_t)bm->totedge, __func__);
411 
412  BLI_LINKSTACK_DECLARE(face_stack, BMFace *);
413 
414  BMVert *v;
415  BMFace *f;
416 
417  BMIter iter;
418 
419  if (use_tag) {
420  /* Build tagged edge array. */
421  BMEdge *e;
422  einput_len = 0;
423 
424  /* Flush edge tags to verts. */
426 
427  /* Keep face tags as is. */
428  BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
429  if (edge_is_cut_test(e)) {
430  edges_arr[einput_len++] = e;
431 
432  /* Flush edge tags to verts. */
435  }
436  }
437 
438  /* Face tags are set by caller. */
439  }
440  else {
441  BMEdge *e;
442  einput_len = (uint)bm->totedge;
443  BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
445  edges_arr[i] = e;
446  }
447 
448  BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
450  }
451  }
452 
453  BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
454 
455  if (use_tag && !BM_elem_flag_test(v, BM_ELEM_TAG)) {
457 
458  /* These should never be accessed. */
459  BM_VERT_DIR(v) = 0;
460  BM_VERT_DIST(v) = 0.0f;
461 
462  continue;
463  }
464 
467 
468  if (BM_VERT_DIR(v) == 0) {
469  if (oflag_center) {
470  BMO_vert_flag_enable(bm, v, oflag_center);
471  }
472  if (use_snap_center) {
473  closest_to_plane_v3(v->co, plane, v->co);
474  }
475  }
476  }
477 
478  /* Store a stack of faces to be evaluated for splitting. */
479  BLI_LINKSTACK_INIT(face_stack);
480 
481  for (i = 0; i < einput_len; i++) {
482  /* We could check `edge_is_cut_test(e)` but there is no point. */
483  BMEdge *e = edges_arr[i];
484  const int side[2] = {BM_VERT_DIR(e->v1), BM_VERT_DIR(e->v2)};
485  const float dist[2] = {BM_VERT_DIST(e->v1), BM_VERT_DIST(e->v2)};
486 
487  if (side[0] && side[1] && (side[0] != side[1])) {
488  const float e_fac = dist[0] / (dist[0] - dist[1]);
489  BMVert *v_new;
490 
491  if (e->l) {
492  BMLoop *l_iter, *l_first;
493  l_iter = l_first = e->l;
494  do {
495  if (!face_in_stack_test(l_iter->f)) {
496  face_in_stack_enable(l_iter->f);
497  BLI_LINKSTACK_PUSH(face_stack, l_iter->f);
498  }
499  } while ((l_iter = l_iter->radial_next) != l_first);
500  }
501 
502  {
503  BMEdge *e_new;
504  v_new = BM_edge_split(bm, e, e->v1, &e_new, e_fac);
505  if (oflag_new) {
506  BMO_edge_flag_enable(bm, e_new, oflag_new);
507  }
508  }
509 
510  vert_is_center_enable(v_new);
511  if (oflag_new | oflag_center) {
512  BMO_vert_flag_enable(bm, v_new, oflag_new | oflag_center);
513  }
514 
515  BM_VERT_DIR(v_new) = 0;
516  BM_VERT_DIST(v_new) = 0.0f;
517  }
518  else if (side[0] == 0 || side[1] == 0) {
519  /* Check if either edge verts are aligned,
520  * if so - tag and push all faces that use it into the stack. */
521  uint j;
522  BM_ITER_ELEM_INDEX (v, &iter, e, BM_VERTS_OF_EDGE, j) {
523  if (side[j] == 0) {
524  if (vert_is_center_test(v) == 0) {
525  BMIter itersub;
526  BMLoop *l_iter;
527 
529 
530  BM_ITER_ELEM (l_iter, &itersub, v, BM_LOOPS_OF_VERT) {
531  if (!face_in_stack_test(l_iter->f)) {
532  face_in_stack_enable(l_iter->f);
533  BLI_LINKSTACK_PUSH(face_stack, l_iter->f);
534  }
535  }
536  }
537  }
538  }
539 
540  /* If both verts are on the center - tag it. */
541  if (oflag_center) {
542  if (side[0] == 0 && side[1] == 0) {
543  BMO_edge_flag_enable(bm, e, oflag_center);
544  }
545  }
546  }
547  }
548 
549  MEM_freeN(edges_arr);
550 
551  while ((f = BLI_LINKSTACK_POP(face_stack))) {
552  bm_face_bisect_verts(bm, f, plane, oflag_center, oflag_new);
553  }
554 
555  /* Caused by access macros: #BM_VERT_DIR, #BM_VERT_SKIP. */
557 
558  /* Now we have all faces to split in the stack. */
559  BLI_LINKSTACK_FREE(face_stack);
560 }
561 
typedef float(TangentPoint)[2]
#define BLI_array_alloca(arr, realsize)
Definition: BLI_alloca.h:22
#define BLI_assert(a)
Definition: BLI_assert.h:46
#define BLI_INLINE
MINLINE float plane_point_side_v3(const float plane[4], const float co[3])
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
Definition: math_geom.c:3527
void closest_to_plane_v3(float r_close[3], const float plane[4], const float pt[3])
Definition: math_geom.c:401
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
Definition: math_matrix.c:917
MINLINE float normalize_v3(float r[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
MINLINE bool equals_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
Strict compiler flags for areas of code we want to ensure don't do conversions without us knowing abo...
unsigned int uint
Definition: BLI_sys_types.h:67
#define UNLIKELY(x)
#define ELEM(...)
#define LIKELY(x)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
Read Guarded memory(de)allocation.
BLI_INLINE void vert_is_center_enable(BMVert *v)
static int bm_vert_sortval_cb(const void *v_a_v, const void *v_b_v)
void BM_mesh_bisect_plane(BMesh *bm, const float plane[4], const bool use_snap_center, const bool use_tag, const short oflag_center, const short oflag_new, const float eps)
BLI_INLINE void face_in_stack_enable(BMFace *f)
static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], const short oflag_center, const short oflag_new)
#define BM_VERT_SKIP(v)
BLI_INLINE void vert_is_center_disable(BMVert *v)
BLI_INLINE bool edge_is_cut_test(BMEdge *e)
BLI_INLINE bool vert_is_center_test(BMVert *v)
BLI_INLINE void edge_is_cut_disable(BMEdge *e)
#define BM_VERT_DIR(v)
#define BM_VERT_LOOPINDEX(v)
#define BM_VERT_DIST(v)
static short plane_point_test_v3(const float plane[4], const float co[3], const float eps, float *r_depth)
BLI_INLINE bool face_in_stack_test(BMFace *f)
#define BM_VERT_SORTVAL(v)
BLI_INLINE void edge_is_cut_enable(BMEdge *e)
BLI_INLINE bool vert_pair_adjacent_in_orig_face(BMVert *v_a, BMVert *v_b, const uint f_len_orig)
BLI_INLINE void face_in_stack_disable(BMFace *f)
#define BM_FACE_FIRST_LOOP(p)
Definition: bmesh_class.h:622
@ BM_VERT
Definition: bmesh_class.h:383
@ BM_ELEM_TAG
Definition: bmesh_class.h:484
#define BM_elem_flag_disable(ele, hflag)
Definition: bmesh_inline.h:15
#define BM_elem_flag_test(ele, hflag)
Definition: bmesh_inline.h:12
#define BM_elem_flag_enable(ele, hflag)
Definition: bmesh_inline.h:14
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BM_ITER_MESH(ele, iter, bm, itype)
#define BM_ITER_MESH_INDEX(ele, iter, bm, itype, indexvar)
@ BM_EDGES_OF_MESH
@ BM_VERTS_OF_MESH
@ BM_VERTS_OF_EDGE
@ BM_FACES_OF_MESH
@ BM_LOOPS_OF_VERT
#define BM_ITER_ELEM_INDEX(ele, iter, data, itype, indexvar)
ATTR_WARN_UNUSED_RESULT BMesh * bm
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
BMVert * BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float fac)
Edge Split.
Definition: bmesh_mods.c:448
BMFace * BM_face_split(BMesh *bm, BMFace *f, BMLoop *l_a, BMLoop *l_b, BMLoop **r_l, BMEdge *example, const bool no_double)
Face Split.
Definition: bmesh_mods.c:179
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_vert_flag_enable(bm, e, oflag)
#define BMO_face_flag_enable(bm, e, oflag)
bool BM_face_is_normal_valid(const BMFace *f)
Definition: bmesh_query.c:2033
BMLoop * BM_face_vert_share_loop(BMFace *f, BMVert *v)
Return the Loop Shared by Face and Vertex.
Definition: bmesh_query.c:1100
BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
ATTR_WARN_UNUSED_RESULT const BMVert * v
SyclQueue void void size_t num_bytes void
static bool is_inside(int x, int y, int cols, int rows)
Definition: filesel.c:706
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33
T abs(const T &a)
const btScalar eps
Definition: poly34.cpp:11
int len
Definition: bmesh_class.h:267
float no[3]
Definition: bmesh_class.h:271
struct BMVert * v
Definition: bmesh_class.h:153
struct BMEdge * e
Definition: bmesh_class.h:164
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
float co[3]
Definition: bmesh_class.h:87
char elem_index_dirty
Definition: bmesh_class.h:305
int totedge
Definition: bmesh_class.h:297