Blender V5.3
bmesh_bisect_plane.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
17
18#include <algorithm>
19
20#include "MEM_guardedalloc.h"
21
22#include "BLI_array.hh"
23#include "BLI_linklist_stack.hh"
24#include "BLI_math_geom_c.hh"
25
26#include "BLI_math_vector_c.hh"
27#include "BLI_set.hh"
28#include "BLI_utildefines.hh"
30
31#include "bmesh.hh"
32#include "bmesh_bisect_plane.hh" /* Own include. */
33
34#include "BLI_strict_flags.hh" /* IWYU pragma: keep. Keep last. */
35
36namespace blender {
37
38/* -------------------------------------------------------------------- */
41
42static short plane_point_test_v3(const float plane[4],
43 const float co[3],
44 const float eps,
45 float *r_depth)
46{
47 const float f = plane_point_side_v3(plane, co);
48 *r_depth = f;
49
50 if (f <= -eps) {
51 return -1;
52 }
53 if (f >= eps) {
54 return 1;
55 }
56 return 0;
57}
58
60
61/* -------------------------------------------------------------------- */
68
69#define BM_VERT_DIR(v) ((short *)(&(v)->head.index))[0] /* Direction -1/0/1 */
70#define BM_VERT_SKIP(v) ((short *)(&(v)->head.index))[1] /* Skip Vert 0/1 */
71#define BM_VERT_DIST(v) ((v)->no[0]) /* Distance from the plane. */
72#define BM_VERT_SORTVAL(v) ((v)->no[1]) /* Temp value for sorting. */
73#define BM_VERT_LOOPINDEX(v) /* The verts index within a face (temp var) */ \
74 (*((uint *)(&(v)->no[2])))
75
77
78/* -------------------------------------------------------------------- */
84
98
100{
101 const uint delta = uint(abs(int(BM_VERT_LOOPINDEX(v_a)) - int(BM_VERT_LOOPINDEX(v_b))));
102 return ELEM(delta, 1, uint(f_len_orig - 1));
103}
104
115{
116 return (BM_elem_flag_test(e, BM_ELEM_TAG) != 0);
117}
118
129{
130 return (BM_elem_flag_test(f, BM_ELEM_TAG) == 0);
131}
132
134
135/* -------------------------------------------------------------------- */
138
140 BMesh *bm, BMFace *f, const float plane[4], const short oflag_center, const short oflag_new)
141{
142 /* Unlikely more than 2 verts are needed. */
143 const uint f_len_orig = uint(f->len);
144 Array<BMVert *, BM_DEFAULT_NGON_STACK_SIZE> vert_split_arr_buf(f_len_orig);
145 BMVert **vert_split_arr = vert_split_arr_buf.data();
146 STACK_DECLARE(vert_split_arr);
147 BMLoop *l_iter, *l_first;
148 bool use_dirs[3] = {false, false, false};
149 bool is_inside = false;
150 /* True when the face contains one or more edges with both it's vertices on the plane.
151 * When set, centered loops are walked over to check if they need to be skipped. */
152 bool face_has_center_edge = false;
153
154 STACK_INIT(vert_split_arr, f_len_orig);
155
156 l_first = BM_FACE_FIRST_LOOP(f);
157
158 /* Add plane-aligned verts to the stack and check we have verts from both sides in this face
159 * (that the face doesn't only have boundary verts on the plane for eg). */
160 l_iter = l_first;
161 do {
162 if (vert_is_center_test(l_iter->v)) {
163 BLI_assert(BM_VERT_DIR(l_iter->v) == 0);
164
165 /* If both are -1 or 1, or both are zero: don't flip 'inside' var while walking. */
166 BM_VERT_SKIP(l_iter->v) = ((BM_VERT_DIR(l_iter->prev->v) ^ BM_VERT_DIR(l_iter->next->v)) ==
167 0);
168
169 STACK_PUSH(vert_split_arr, l_iter->v);
170
171 if (face_has_center_edge == false) {
172 if (vert_is_center_test(l_iter->prev->v)) {
173 face_has_center_edge = true;
174 }
175 }
176 }
177 use_dirs[BM_VERT_DIR(l_iter->v) + 1] = true;
178 } while ((l_iter = l_iter->next) != l_first);
179
180 if ((STACK_SIZE(vert_split_arr) > 1) && (use_dirs[0] && use_dirs[2])) {
181 if (STACK_SIZE(vert_split_arr) == 2) [[likely]] {
182 BMLoop *l_new;
183 BMLoop *l_a, *l_b;
184
185 l_a = BM_face_vert_share_loop(f, vert_split_arr[0]);
186 l_b = BM_face_vert_share_loop(f, vert_split_arr[1]);
187
188 /* Common case, just cut the face once. */
189 BM_face_split(bm, f, l_a, l_b, &l_new, nullptr, true);
190 if (l_new) {
191 if (oflag_center | oflag_new) {
192 BMO_edge_flag_enable(bm, l_new->e, oflag_center | oflag_new);
193 }
194 if (oflag_new) {
195 BMO_face_flag_enable(bm, l_new->f, oflag_new);
196 }
197 }
198 }
199 else {
200 /* Less common case, _complicated_ we need to calculate how to do multiple cuts. */
201
202 uint i = 0;
203
204 /* ---- */
205 /* Check contiguous spans of centered vertices (skipping when necessary). */
206 if (face_has_center_edge) {
207
208 /* Loop indices need to be set for adjacency checks. */
209 l_iter = l_first;
210 do {
211 BM_VERT_LOOPINDEX(l_iter->v) = i++;
212 } while ((l_iter = l_iter->next) != l_first);
213
214 /* Start out on a non-centered vertex so a span of centered vertices can be looped over
215 * without having to scan backwards as well as forwards. */
216 BMLoop *l_first_non_center = l_first;
217 while (vert_is_center_test(l_first_non_center->v)) {
218 l_first_non_center = l_first_non_center->next;
219 }
220
221 l_iter = l_first_non_center;
222 do {
223 if (BM_VERT_SKIP(l_iter->v)) {
224 continue;
225 }
226 /* No need to check the previous as the iteration starts on a non-centered vertex. */
227 if (!(vert_is_center_test(l_iter->v) && vert_is_center_test(l_iter->next->v))) {
228 continue;
229 }
230
231 /* Walk over the next loops as long as they are centered. */
232 BMLoop *l_prev = l_iter->prev;
233 BMLoop *l_next = l_iter->next->next;
234 /* No need to scan the previous vertices,
235 * these will have been dealt with in previous steps. */
237 while (vert_is_center_test(l_next->v)) {
238 l_next = l_next->next;
239 }
240
241 /* Skip all vertices when the edges connected to the beginning/end
242 * of the range are on a different side of the bisecting plane. */
243 if (!(BM_VERT_DIR(l_prev->v) ^ BM_VERT_DIR(l_next->v))) {
245 l_iter = l_prev->next;
246 while (l_iter != l_next) {
248 BM_VERT_SKIP(l_iter->v) = true;
249 l_iter = l_iter->next;
250 }
251 }
252 /* Step over the span already handled, even if skip wasn't set. */
253 l_iter = l_next->prev;
254 } while ((l_iter = l_iter->next) != l_first_non_center);
255 }
256
257 Array<BMFace *, BM_DEFAULT_NGON_STACK_SIZE> face_split_arr_buf(STACK_SIZE(vert_split_arr));
258 BMFace **face_split_arr = face_split_arr_buf.data();
259 STACK_DECLARE(face_split_arr);
260
261 float sort_dir[3];
262
263 /* ---- */
264 /* Calculate the direction to sort verts in the face intersecting the plane */
265
266 /* The exact direction isn't important, vertices just need to be sorted across the face.
267 * (`sort_dir` could be flipped either way). */
269 cross_v3_v3v3(sort_dir, f->no, plane);
270 if (normalize_v3(sort_dir) == 0.0f) [[unlikely]] {
271 /* find any 2 verts and get their direction */
272 for (i = 0; i < STACK_SIZE(vert_split_arr); i++) {
273 if (!equals_v3v3(vert_split_arr[0]->co, vert_split_arr[i]->co)) {
274 sub_v3_v3v3(sort_dir, vert_split_arr[0]->co, vert_split_arr[i]->co);
275 normalize_v3(sort_dir);
276 }
277 }
278 if (i == STACK_SIZE(vert_split_arr)) [[unlikely]] {
279 /* Ok, we can't do anything useful here,
280 * face has no area or so, bail out, this is highly unlikely but not impossible. */
281 goto finally;
282 }
283 }
284
285 /* ---- */
286 /* Sort the verts across the face from one side to another. */
287 for (i = 0; i < STACK_SIZE(vert_split_arr); i++) {
288 BMVert *v = vert_split_arr[i];
289 BM_VERT_SORTVAL(v) = dot_v3v3(sort_dir, v->co);
290 }
291
292 std::sort(
293 vert_split_arr,
294 vert_split_arr + STACK_SIZE(vert_split_arr),
295 [](BMVert *v_a, BMVert *v_b) { return BM_VERT_SORTVAL(v_a) < BM_VERT_SORTVAL(v_b); });
296
297 /* ---- */
298 /* Split the face across sorted splits. */
299
300 /* NOTE: we don't know which face gets which splits,
301 * so at the moment we have to search all faces for the vert pair,
302 * while not all that nice, typically there are < 5 resulting faces,
303 * so its not _that_ bad. */
304
305 STACK_INIT(face_split_arr, STACK_SIZE(vert_split_arr));
306 STACK_PUSH(face_split_arr, f);
307
308 for (i = 0; i < STACK_SIZE(vert_split_arr) - 1; i++) {
309 BMVert *v_a = vert_split_arr[i];
310 BMVert *v_b = vert_split_arr[i + 1];
311
312 if (face_has_center_edge) {
313 if (vert_pair_adjacent_in_orig_face(v_a, v_b, f_len_orig)) {
314 continue;
315 }
316 }
317
318 if (!BM_VERT_SKIP(v_a)) {
319 is_inside = !is_inside;
320 }
321
322 if (is_inside) {
323 BMLoop *l_a, *l_b;
324 bool found = false;
325 uint j;
326
327 for (j = 0; j < STACK_SIZE(face_split_arr); j++) {
328 /* It would be nice to avoid loop lookup here,
329 * but we need to know which face the verts are in. */
330 if ((l_a = BM_face_vert_share_loop(face_split_arr[j], v_a)) &&
331 (l_b = BM_face_vert_share_loop(face_split_arr[j], v_b)))
332 {
333 found = true;
334 break;
335 }
336 }
337
338 /* Ideally won't happen, but it can for self-intersecting faces. */
339 // BLI_assert(found == true);
340
341 /* In fact this simple test is good enough, test if the loops are adjacent. */
342 if (found && !BM_loop_is_adjacent(l_a, l_b)) {
343 BMLoop *l_new;
344 BMFace *f_tmp;
345 f_tmp = BM_face_split(bm, face_split_arr[j], l_a, l_b, &l_new, nullptr, true);
346
347 if (l_new) {
348 if (oflag_center | oflag_new) {
349 BMO_edge_flag_enable(bm, l_new->e, oflag_center | oflag_new);
350 }
351 if (oflag_new) {
352 BMO_face_flag_enable(bm, l_new->f, oflag_new);
353 }
354 }
355
356 if (f_tmp) {
357 if (f_tmp != face_split_arr[j]) {
358 STACK_PUSH(face_split_arr, f_tmp);
359 BLI_assert(STACK_SIZE(face_split_arr) <= STACK_SIZE(vert_split_arr));
360 }
361 }
362 }
363 }
364 else {
365 // printf("no intersect\n");
366 }
367 }
368 }
369 }
370
371finally:
372 (void)vert_split_arr;
373}
374
376
377/* -------------------------------------------------------------------- */
380
382 const float plane[4],
383 const bool use_snap_center,
384 const bool use_tag,
385 const short oflag_center,
386 const short oflag_new,
387 const float eps)
388{
389 uint einput_len;
390 uint i;
391 BMEdge **edges_arr = MEM_new_array_uninitialized<BMEdge *>(size_t(bm->totedge), __func__);
392
393 BLI_LINKSTACK_DECLARE(face_stack, BMFace *);
394
395 BMVert *v;
396 BMFace *f;
397
398 BMIter iter;
399
400 /* Needed when `use_snap_center` moves vertices. */
401 Set<BMFace *> faces_deferred_normal_update;
402
403 if (use_tag) {
404 /* Build tagged edge array. */
405 BMEdge *e;
406 einput_len = 0;
407
408 /* Keep vertex tags set by the caller (needed for loose vertices),
409 * edge tags are flushed to their vertices below. */
411 if (edge_is_cut_test(e)) {
412 edges_arr[einput_len++] = e;
413
414 /* Flush edge tags to verts. */
417 }
418 }
419
420 /* Face tags are set by caller. */
421 }
422 else {
423 BMEdge *e;
424 einput_len = uint(bm->totedge);
427 edges_arr[i] = e;
428 }
429
430 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
432 }
433 }
434
435 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
436
437 if (use_tag && !BM_elem_flag_test(v, BM_ELEM_TAG)) {
439
440 /* These should never be accessed. */
441 BM_VERT_DIR(v) = 0;
442 BM_VERT_DIST(v) = 0.0f;
443
444 continue;
445 }
446
449
450 if (BM_VERT_DIR(v) == 0) {
451 if (oflag_center) {
452 BMO_vert_flag_enable(bm, v, oflag_center);
453 }
454 if (use_snap_center) {
455 float co_center[3];
456 closest_to_plane_v3(co_center, plane, v->co);
457 if (!equals_v3v3(co_center, v->co)) {
458 copy_v3_v3(v->co, co_center);
459 BMIter itersub;
460 BM_ITER_ELEM (f, &itersub, v, BM_FACES_OF_VERT) {
461 faces_deferred_normal_update.add(f);
462 }
463 }
464 }
465 }
466 }
467
468 for (BMFace *f_iter : faces_deferred_normal_update) {
469 BM_face_normal_update(f_iter);
470 }
471
472 /* Store a stack of faces to be evaluated for splitting. */
473 BLI_LINKSTACK_INIT(face_stack);
474
475 for (i = 0; i < einput_len; i++) {
476 /* We could check `edge_is_cut_test(e)` but there is no point. */
477 BMEdge *e = edges_arr[i];
478 const int side[2] = {BM_VERT_DIR(e->v1), BM_VERT_DIR(e->v2)};
479 const float dist[2] = {BM_VERT_DIST(e->v1), BM_VERT_DIST(e->v2)};
480
481 if (side[0] && side[1] && (side[0] != side[1])) {
482 const float e_fac = dist[0] / (dist[0] - dist[1]);
483 BMVert *v_new;
484
485 if (e->l) {
486 BMLoop *l_iter, *l_first;
487 l_iter = l_first = e->l;
488 do {
489 if (!face_in_stack_test(l_iter->f)) {
490 face_in_stack_enable(l_iter->f);
491 BLI_LINKSTACK_PUSH(face_stack, l_iter->f);
492 }
493 } while ((l_iter = l_iter->radial_next) != l_first);
494 }
495
496 {
497 BMEdge *e_new;
498 v_new = BM_edge_split(bm, e, e->v1, &e_new, e_fac);
499 if (oflag_new) {
500 BMO_edge_flag_enable(bm, e_new, oflag_new);
501 }
502 }
503
505 if (oflag_new | oflag_center) {
506 BMO_vert_flag_enable(bm, v_new, oflag_new | oflag_center);
507 }
508
509 BM_VERT_DIR(v_new) = 0;
510 BM_VERT_DIST(v_new) = 0.0f;
511 }
512 else if (side[0] == 0 || side[1] == 0) {
513 /* Check if either edge verts are aligned,
514 * if so - tag and push all faces that use it into the stack. */
515 uint j;
516 BM_ITER_ELEM_INDEX (v, &iter, e, BM_VERTS_OF_EDGE, j) {
517 if (side[j] == 0) {
518 if (vert_is_center_test(v) == 0) {
519 BMIter itersub;
520 BMLoop *l_iter;
521
523
524 BM_ITER_ELEM (l_iter, &itersub, v, BM_LOOPS_OF_VERT) {
525 if (!face_in_stack_test(l_iter->f)) {
526 face_in_stack_enable(l_iter->f);
527 BLI_LINKSTACK_PUSH(face_stack, l_iter->f);
528 }
529 }
530 }
531 }
532 }
533
534 /* If both verts are on the center - tag it. */
535 if (oflag_center) {
536 if (side[0] == 0 && side[1] == 0) {
537 BMO_edge_flag_enable(bm, e, oflag_center);
538 }
539 }
540 }
541 }
542
543 MEM_delete(edges_arr);
544
545 while ((f = BLI_LINKSTACK_POP(face_stack))) {
546 bm_face_bisect_verts(bm, f, plane, oflag_center, oflag_new);
547 }
548
549 /* Caused by access macros: #BM_VERT_DIR, #BM_VERT_SKIP. */
551
552 /* Now we have all faces to split in the stack. */
553 BLI_LINKSTACK_FREE(face_stack);
554}
555
557
558} // namespace blender
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
Read Blender memory allocation and freeing.
#define BLI_INLINE
#define ELEM(...)
#define BM_VERT_SKIP(v)
#define BM_VERT_DIR(v)
#define BM_VERT_LOOPINDEX(v)
#define BM_VERT_DIST(v)
#define BM_VERT_SORTVAL(v)
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#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)
#define BM_ITER_ELEM_INDEX(ele, iter, data, itype, indexvar)
#define BMO_edge_flag_enable(bm, e, oflag)
#define BMO_vert_flag_enable(bm, e, oflag)
#define BMO_face_flag_enable(bm, e, oflag)
const T * data() const
Definition BLI_array.hh:323
bool add(const Key &key)
Definition BLI_set.hh:248
#define abs
BMesh Iterators.
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
void closest_to_plane_v3(float r_close[3], const float plane[4], const float pt[3])
Definition math_geom.cc:451
BLI_INLINE void face_in_stack_disable(BMFace *f)
BLI_INLINE bool BM_loop_is_adjacent(const BMLoop *l_a, const BMLoop *l_b) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
MINLINE void copy_v3_v3(float r[3], const float a[3])
unsigned int uint
Definition BKE_text.h:55
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
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)
BLI_INLINE void edge_is_cut_enable(BMEdge *e)
BLI_INLINE bool vert_is_center_test(BMVert *v)
ATTR_WARN_UNUSED_RESULT const BMVert * 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 vert_is_center_enable(BMVert *v)
MINLINE bool equals_v3v3(const float v1[3], const float v2[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void BM_face_normal_update(BMFace *f)
BLI_INLINE bool vert_pair_adjacent_in_orig_face(BMVert *v_a, BMVert *v_b, const uint f_len_orig)
BLI_INLINE void vert_is_center_disable(BMVert *v)
BLI_INLINE bool edge_is_cut_test(BMEdge *e)
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
MINLINE float plane_point_side_v3(const float plane[4], const float co[3])
BLI_INLINE void edge_is_cut_disable(BMEdge *e)
static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], const short oflag_center, const short oflag_new)
MINLINE float normalize_v3(float n[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
BMVert * BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float fac)
Edge Split.
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.
BLI_INLINE void face_in_stack_enable(BMFace *f)
BMLoop * BM_face_vert_share_loop(BMFace *f, BMVert *v)
Return the Loop Shared by Face and Vertex.
bool BM_face_is_normal_valid(const BMFace *f)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
const btScalar eps
Definition poly34.cpp:11
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f