Blender V5.3
bmesh_intersect_edges.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2019 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10
11#include "MEM_guardedalloc.h"
12
13#include "BLI_math_geom_c.hh"
14#include "BLI_math_vector_c.hh"
15#include "BLI_sort.hh"
16#include "BLI_stack_c.hh"
17#include "BLI_vector.hh"
18
19#include "BKE_bvhutils.hh"
20
21#include "atomic_ops.h"
22
23#include "bmesh.hh"
24
25#include "bmesh_intersect_edges.hh" /* own include */
26
27namespace blender {
28
29// #define INTERSECT_EDGES_DEBUG
30
31#define KDOP_TREE_TYPE 4
32#define KDOP_AXIS_LEN 14
33#define BLI_STACK_PAIR_LEN (2 * KDOP_TREE_TYPE)
34
35/* -------------------------------------------------------------------- */
40
41/* Callbacks for `BM_vert_pair_shared_face_cb` */
42
54
56 BMLoop *l_a,
57 BMLoop *l_b,
58 void *userdata)
59{
60 EDBMSplitBestFaceData *data = static_cast<EDBMSplitBestFaceData *>(userdata);
61 float no[3];
62 copy_v3_v3(no, f->no);
63
64 float min = dot_v3v3(l_a->v->co, no);
65 float max = dot_v3v3(l_b->v->co, no);
66 if (min > max) {
67 std::swap(min, max);
68 }
69
70 BMEdge **e_iter = &data->edgenet[0];
71 BMEdge *e_next = data->edgenet[1];
72 BMVert *v_test = ELEM((*e_iter)->v1, e_next->v1, e_next->v2) ? (*e_iter)->v2 : (*e_iter)->v1;
73
74 int verts_len = data->edgenet_len - 1;
75 for (int i = verts_len; i--; e_iter++) {
76 v_test = BM_edge_other_vert(*e_iter, v_test);
77 BLI_assert(v_test != nullptr);
78 if (!BM_face_point_inside_test(f, v_test->co)) {
79 return false;
80 }
81 float dot = dot_v3v3(v_test->co, no);
82 min = std::min(dot, min);
83 max = std::max(dot, max);
84 }
85
86 const float test_edgenet_range_on_face_normal = max - min;
87 if (test_edgenet_range_on_face_normal < data->best_edgenet_range_on_face_normal) {
88 data->best_edgenet_range_on_face_normal = test_edgenet_range_on_face_normal;
89 data->r_best_face = f;
90 }
91
92 return false;
93}
94
95/* find the best splittable face between the two vertices. */
97 BMLoop *l_a,
98 BMLoop *l_b,
99 void *userdata)
100{
101 float (*data)[3] = static_cast<float (*)[3]>(userdata);
102 float *v_a_co = data[0];
103 float *v_a_b_dir = data[1];
104 const float range_min = -FLT_EPSILON;
105 const float range_max = 1.0f + FLT_EPSILON;
106
107 float co[3];
108 float dir[3];
109 float lambda_b;
110
111 copy_v3_v3(co, l_a->prev->v->co);
112 sub_v3_v3v3(dir, l_a->next->v->co, co);
113 if (isect_ray_ray_v3(v_a_co, v_a_b_dir, co, dir, nullptr, &lambda_b)) {
114 if (IN_RANGE(lambda_b, range_min, range_max)) {
115 return true;
116 }
117 copy_v3_v3(co, l_b->prev->v->co);
118 sub_v3_v3v3(dir, l_b->next->v->co, co);
119 if (isect_ray_ray_v3(v_a_co, v_a_b_dir, co, dir, nullptr, &lambda_b)) {
120 return IN_RANGE(lambda_b, range_min, range_max);
121 }
122 }
123 return false;
124}
125
127 BMVert *v_a, BMVert *v_b, BMEdge **edgenet, const int edgenet_len, const float epsilon)
128{
129 BMFace *best_face = nullptr;
130
131 BLI_assert(v_a != v_b);
132
133 BMLoop *dummy;
134 if (edgenet_len == 1) {
135 float data[2][3];
136 copy_v3_v3(data[0], v_b->co);
137 sub_v3_v3v3(data[1], v_a->co, data[0]);
138 best_face = BM_vert_pair_shared_face_cb(
139 v_a, v_b, false, bm_vert_pair_share_splittable_face_cb, &data, &dummy, &dummy);
140 BLI_assert(!best_face || BM_edge_in_face(edgenet[0], best_face) == false);
141 }
142 else {
144 data.edgenet = edgenet;
145 data.edgenet_len = edgenet_len;
146 data.best_edgenet_range_on_face_normal = FLT_MAX;
147 data.r_best_face = nullptr;
148
150 v_a, v_b, true, bm_vert_pair_share_best_splittable_face_cb, &data, &dummy, &dummy);
151
152 if (data.r_best_face) {
153 /* Check if the edgenet's range is smaller than the face's range. */
154 float no[3], min = FLT_MAX, max = -FLT_MAX;
155 copy_v3_v3(no, data.r_best_face->no);
156 BMVert *v_test;
157 BMIter f_iter;
158 BM_ITER_ELEM (v_test, &f_iter, data.r_best_face, BM_VERTS_OF_FACE) {
159 float dot = dot_v3v3(v_test->co, no);
160 min = std::min(dot, min);
161 max = std::max(dot, max);
162 }
163 float face_range_on_normal = max - min + 2 * epsilon;
164 if (face_range_on_normal < data.best_edgenet_range_on_face_normal) {
165 data.r_best_face = nullptr;
166 }
167 }
168 best_face = data.r_best_face;
169 }
170
171 return best_face;
172}
173
175
176/* -------------------------------------------------------------------- */
181
183 union {
184 BMElem *elem;
185 BMVert *vert;
186 struct {
187 BMEdge *edge;
188 float lambda;
189 };
190 };
191};
192
193/* -------------------------------------------------------------------- */
194/* Overlap Callbacks */
195
203
204/* Utils */
205
207{
208 r_pair_elem->vert = v;
209}
210
212 float lambda,
213 int *r_data_cut_edges_len,
214 EDBMSplitElem *r_pair_elem)
215{
216 r_pair_elem->edge = e;
217 r_pair_elem->lambda = lambda;
218
219 /* Even though we have multiple atomic operations, this is fine here, since
220 * there is no dependency on order.
221 * The `e->head.index` check + atomic increment will ever be true once, as
222 * expected. We don't care which instance of the code actually ends up
223 * incrementing `r_data_cut_edge_len`, so there is no race condition here. */
224 if (atomic_fetch_and_add_int32(&e->head.index, 1) == 0) {
225 atomic_fetch_and_add_int32(r_data_cut_edges_len, 1);
226 }
227}
228
229/* Util for Vert x Edge and Edge x Edge callbacks */
231 BMEdge *e,
232 const float co[3],
233 const float dir[3],
234 float lambda,
235 float data_dist_sq,
236 int *data_cut_edges_len,
237 EDBMSplitElem r_pair[2])
238{
239 BMVert *e_v;
240 float dist_sq_vert_factor;
241
242 if (!IN_RANGE_INCL(lambda, 0.0f, 1.0f)) {
243 /* Vert x Vert is already handled elsewhere. */
244 return false;
245 }
246
247 if (lambda < 0.5f) {
248 e_v = e->v1;
249 dist_sq_vert_factor = lambda;
250 }
251 else {
252 e_v = e->v2;
253 dist_sq_vert_factor = 1.0f - lambda;
254 }
255
256 if (v != e_v) {
257 float dist_sq_vert = square_f(dist_sq_vert_factor) * len_squared_v3(dir);
258 if (dist_sq_vert < data_dist_sq) {
259 /* Vert x Vert is already handled elsewhere. */
260 return false;
261 }
262
263 float closest[3];
264 madd_v3_v3v3fl(closest, co, dir, lambda);
265
266 float dist_sq = len_squared_v3v3(v->co, closest);
267 if (dist_sq < data_dist_sq) {
268 bm_edge_pair_elem_setup(e, lambda, data_cut_edges_len, &r_pair[0]);
269 bm_vert_pair_elem_setup_ex(v, &r_pair[1]);
270 return true;
271 }
272 }
273
274 return false;
275}
276
277/* Vertex x Vertex Callback */
278
279static bool bm_vertxvert_isect_cb(void *userdata, int index_a, int index_b, int thread)
280{
281 EDBMSplitData *data = static_cast<EDBMSplitData *>(userdata);
282 BMVert *v_a = BM_vert_at_index(data->bm, index_a);
283 BMVert *v_b = BM_vert_at_index(data->bm, index_b);
284
285 EDBMSplitElem *pair = static_cast<EDBMSplitElem *>(BLI_stack_push_r(data->pair_stack[thread]));
286
287 bm_vert_pair_elem_setup_ex(v_a, &pair[0]);
288 bm_vert_pair_elem_setup_ex(v_b, &pair[1]);
289
290 return true;
291}
292
293static bool bm_vertxvert_self_isect_cb(void *userdata, int index_a, int index_b, int thread)
294{
295 if (index_a < index_b) {
296 return bm_vertxvert_isect_cb(userdata, index_a, index_b, thread);
297 }
298 return false;
299}
300
301/* Vertex x Edge and Edge x Vertex Callbacks */
302
303static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int thread)
304{
305 EDBMSplitData *data = static_cast<EDBMSplitData *>(userdata);
306 BMEdge *e = BM_edge_at_index(data->bm, index_a);
307 BMVert *v = BM_vert_at_index(data->bm, index_b);
308
309 float co[3], dir[3], lambda;
310 copy_v3_v3(co, e->v1->co);
311 sub_v3_v3v3(dir, e->v2->co, co);
312 lambda = ray_point_factor_v3_ex(v->co, co, dir, 0.0f, -1.0f);
313
314 EDBMSplitElem pair_tmp[2];
316 v, e, co, dir, lambda, data->dist_sq, &data->cut_edges_len, pair_tmp))
317 {
318 EDBMSplitElem *pair = static_cast<EDBMSplitElem *>(BLI_stack_push_r(data->pair_stack[thread]));
319 pair[0] = pair_tmp[0];
320 pair[1] = pair_tmp[1];
321 }
322
323 /* Always return false with edges. */
324 return false;
325}
326
327/* Edge x Edge Callbacks */
328
330 BMEdge *e_a,
331 BMEdge *e_b,
332 const float co_a[3],
333 const float dir_a[3],
334 const float co_b[3],
335 const float dir_b[3],
336 float lambda_a,
337 float lambda_b,
338 EDBMSplitElem r_pair[2])
339{
340 float dist_sq_va_factor, dist_sq_vb_factor;
341 BMVert *e_a_v, *e_b_v;
342 if (lambda_a < 0.5f) {
343 e_a_v = e_a->v1;
344 dist_sq_va_factor = lambda_a;
345 }
346 else {
347 e_a_v = e_a->v2;
348 dist_sq_va_factor = 1.0f - lambda_a;
349 }
350
351 if (lambda_b < 0.5f) {
352 e_b_v = e_b->v1;
353 dist_sq_vb_factor = lambda_b;
354 }
355 else {
356 e_b_v = e_b->v2;
357 dist_sq_vb_factor = 1.0f - lambda_b;
358 }
359
360 if (e_a_v != e_b_v) {
361 if (!IN_RANGE_INCL(lambda_a, 0.0f, 1.0f) || !IN_RANGE_INCL(lambda_b, 0.0f, 1.0f)) {
362 /* Vert x Edge is already handled elsewhere. */
363 return false;
364 }
365
366 float dist_sq_va = square_f(dist_sq_va_factor) * len_squared_v3(dir_a);
367 float dist_sq_vb = square_f(dist_sq_vb_factor) * len_squared_v3(dir_b);
368
369 if (dist_sq_va < data->dist_sq || dist_sq_vb < data->dist_sq) {
370 /* Vert x Edge is already handled elsewhere. */
371 return false;
372 }
373
374 float near_a[3], near_b[3];
375 madd_v3_v3v3fl(near_a, co_a, dir_a, lambda_a);
376 madd_v3_v3v3fl(near_b, co_b, dir_b, lambda_b);
377
378 float dist_sq = len_squared_v3v3(near_a, near_b);
379 if (dist_sq < data->dist_sq) {
380 bm_edge_pair_elem_setup(e_a, lambda_a, &data->cut_edges_len, &r_pair[0]);
381 bm_edge_pair_elem_setup(e_b, lambda_b, &data->cut_edges_len, &r_pair[1]);
382 return true;
383 }
384 }
385 return false;
386}
387
388static bool bm_edgexedge_isect_cb(void *userdata, int index_a, int index_b, int thread)
389{
390 EDBMSplitData *data = static_cast<EDBMSplitData *>(userdata);
391 BMEdge *e_a = BM_edge_at_index(data->bm, index_a);
392 BMEdge *e_b = BM_edge_at_index(data->bm, index_b);
393
394 if (BM_edge_share_vert_check(e_a, e_b)) {
395 /* The other vertices may intersect but Vert x Edge is already handled elsewhere. */
396 return false;
397 }
398
399 float co_a[3], dir_a[3], co_b[3], dir_b[3];
400 copy_v3_v3(co_a, e_a->v1->co);
401 sub_v3_v3v3(dir_a, e_a->v2->co, co_a);
402
403 copy_v3_v3(co_b, e_b->v1->co);
404 sub_v3_v3v3(dir_b, e_b->v2->co, co_b);
405
406 float lambda_a, lambda_b;
407 /* Using with dist^4 as `epsilon` is not the best solution, but it fits in most cases. */
408 if (isect_ray_ray_epsilon_v3(co_a, dir_a, co_b, dir_b, data->dist_sq_sq, &lambda_a, &lambda_b)) {
409 EDBMSplitElem pair_tmp[2];
411 data, e_a, e_b, co_a, dir_a, co_b, dir_b, lambda_a, lambda_b, pair_tmp))
412 {
413 EDBMSplitElem *pair = static_cast<EDBMSplitElem *>(
414 BLI_stack_push_r(data->pair_stack[thread]));
415 pair[0] = pair_tmp[0];
416 pair[1] = pair_tmp[1];
417 }
418 }
419
420 /* Edge x Edge returns always false. */
421 return false;
422}
423
424static bool bm_edgexedge_self_isect_cb(void *userdata, int index_a, int index_b, int thread)
425{
426 if (index_a < index_b) {
427 return bm_edgexedge_isect_cb(userdata, index_a, index_b, thread);
428 }
429 return false;
430}
431
432/* -------------------------------------------------------------------- */
433/* BVHTree Overlap Function */
434
435static void bm_elemxelem_bvhtree_overlap(const BVHTree *tree1,
436 const BVHTree *tree2,
439 BLI_Stack **pair_stack)
440{
441 int parallel_tasks_num = BLI_bvhtree_overlap_thread_num(tree1);
442 for (int i = 0; i < parallel_tasks_num; i++) {
443 if (pair_stack[i] == nullptr) {
444 pair_stack[i] = BLI_stack_new(sizeof(const EDBMSplitElem[2]), __func__);
445 }
446 }
447 data->pair_stack = pair_stack;
448 BLI_bvhtree_overlap_ex(tree1, tree2, nullptr, callback, data, 1, BVH_OVERLAP_USE_THREADING);
449}
450
451/* -------------------------------------------------------------------- */
452/* Callbacks for `BLI_qsort_r` */
453
454static int sort_cmp_by_lambda_cb(const void *index1_v, const void *index2_v, void *keys_v)
455{
456 const EDBMSplitElem *pair_flat = static_cast<const EDBMSplitElem *>(keys_v);
457 const int index1 = *static_cast<int *>(const_cast<void *>(index1_v));
458 const int index2 = *static_cast<int *>(const_cast<void *>(index2_v));
459
460 if (pair_flat[index1].lambda > pair_flat[index2].lambda) {
461 return 1;
462 }
463 return -1;
464}
465
466/* -------------------------------------------------------------------- */
467/* Main API */
468
469#define INTERSECT_EDGES
470
472 BMesh *bm, const char hflag, const float dist, const bool split_faces, GHash *r_targetmap)
473{
474 bool ok = false;
475
476 BMIter iter;
477 BMVert *v;
478 BMEdge *e;
479 int i;
480
481 /* Store all intersections in this array. */
482 EDBMSplitElem(*pair_iter)[2], (*pair_array)[2] = nullptr;
483 int pair_len = 0;
484
485 BLI_Stack *pair_stack[BLI_STACK_PAIR_LEN] = {nullptr};
486 BLI_Stack **pair_stack_vertxvert = pair_stack;
487 BLI_Stack **pair_stack_edgexelem = &pair_stack[KDOP_TREE_TYPE];
488
489 const float dist_sq = square_f(dist);
490 const float dist_half = dist / 2;
491
493 data.bm = bm;
494 data.pair_stack = pair_stack;
495 data.cut_edges_len = 0;
496 data.dist_sq = dist_sq;
497 data.dist_sq_sq = square_f(dist_sq);
498
500
501 /* tag and count the verts to be tested. */
502 int verts_act_len = 0, verts_remain_len = 0;
503 BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
504 if (BM_elem_flag_test(v, hflag)) {
506 verts_act_len++;
507 }
508 else {
511 verts_remain_len++;
512 }
513 }
514
515 /* The index will indicate which cut in pair_array this vertex belongs to. */
516 BM_elem_index_set(v, -1);
517 }
519
520 /* Start the creation of BVHTrees. */
521 BVHTree *tree_verts_act = nullptr, *tree_verts_remain = nullptr;
522 if (verts_act_len) {
523 tree_verts_act = BLI_bvhtree_new(verts_act_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN);
524 }
525 if (verts_remain_len) {
526 tree_verts_remain = BLI_bvhtree_new(
527 verts_remain_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN);
528 }
529
530 if (tree_verts_act || tree_verts_remain) {
533 if (tree_verts_act) {
534 BLI_bvhtree_insert(tree_verts_act, i, v->co, 1);
535 }
536 }
537 else if (tree_verts_remain && !BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
538 BLI_bvhtree_insert(tree_verts_remain, i, v->co, 1);
539 }
540 }
541
542 if (tree_verts_act) {
543 BLI_bvhtree_balance(tree_verts_act);
544 /* First pair search. */
546 tree_verts_act, tree_verts_act, bm_vertxvert_self_isect_cb, &data, pair_stack_vertxvert);
547 }
548
549 if (tree_verts_remain) {
550 BLI_bvhtree_balance(tree_verts_remain);
551 }
552
553 if (tree_verts_act && tree_verts_remain) {
555 tree_verts_remain, tree_verts_act, bm_vertxvert_isect_cb, &data, pair_stack_vertxvert);
556 }
557 }
558
559 for (i = KDOP_TREE_TYPE; i--;) {
560 if (pair_stack_vertxvert[i]) {
561 pair_len += BLI_stack_count(pair_stack_vertxvert[i]);
562 }
563 }
564
565#ifdef INTERSECT_EDGES
566 uint vertxvert_pair_len = pair_len;
567
568# define EDGE_ACT_TO_TEST 1
569# define EDGE_REMAIN_TO_TEST 2
570 /* Tag and count the edges. */
571 int edges_act_len = 0, edges_remain_len = 0;
572 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
573 if (BM_elem_flag_test(e, BM_ELEM_HIDDEN) || (len_squared_v3v3(e->v1->co, e->v2->co) < dist_sq))
574 {
575 /* Don't test hidden edges or smaller than the minimum distance.
576 * These have already been handled in the vertices overlap. */
578 if (split_faces) {
579 /* Tag to be ignored. */
581 }
582 continue;
583 }
584
587 edges_act_len++;
588 }
589 else {
591 edges_remain_len++;
592 if (split_faces) {
593 /* Tag to be ignored. */
595 }
596 }
597 }
598
599 BVHTree *tree_edges_act = nullptr, *tree_edges_remain = nullptr;
600 if (edges_act_len) {
601 tree_edges_act = BLI_bvhtree_new(edges_act_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN);
602 }
603
604 if (edges_remain_len && (tree_edges_act || tree_verts_act)) {
605 tree_edges_remain = BLI_bvhtree_new(
606 edges_remain_len, dist_half, KDOP_TREE_TYPE, KDOP_AXIS_LEN);
607 }
608
609 if (tree_edges_act || tree_edges_remain) {
611 int edge_test = BM_elem_index_get(e);
612 float co[2][3];
613 if (edge_test == EDGE_ACT_TO_TEST) {
614 BLI_assert(tree_edges_act);
615 e->head.index = 0;
616 copy_v3_v3(co[0], e->v1->co);
617 copy_v3_v3(co[1], e->v2->co);
618 BLI_bvhtree_insert(tree_edges_act, i, co[0], 2);
619 }
620 else if (edge_test == EDGE_REMAIN_TO_TEST) {
621 BLI_assert(tree_edges_remain);
622 e->head.index = 0;
623 copy_v3_v3(co[0], e->v1->co);
624 copy_v3_v3(co[1], e->v2->co);
625 BLI_bvhtree_insert(tree_edges_remain, i, co[0], 2);
626 }
627# ifdef INTERSECT_EDGES_DEBUG
628 else {
629 e->head.index = 0;
630 }
631# endif
632 /* Tag used when converting pairs to vert x vert. */
634 }
635# undef EDGE_ACT_TO_TEST
636# undef EDGE_REMAIN_TO_TEST
637
638 /* Use `e->head.index` to count intersections. */
640
641 if (tree_edges_act) {
642 BLI_bvhtree_balance(tree_edges_act);
643 }
644
645 if (tree_edges_remain) {
646 BLI_bvhtree_balance(tree_edges_remain);
647 }
648
649 int edgexedge_pair_len = 0;
650 if (tree_edges_act) {
651 /* Edge x Edge */
653 tree_edges_act, tree_edges_act, bm_edgexedge_self_isect_cb, &data, pair_stack_edgexelem);
654
655 if (tree_edges_remain) {
657 tree_edges_remain, tree_edges_act, bm_edgexedge_isect_cb, &data, pair_stack_edgexelem);
658 }
659
660 for (i = KDOP_TREE_TYPE; i--;) {
661 if (pair_stack_edgexelem[i]) {
662 edgexedge_pair_len += BLI_stack_count(pair_stack_edgexelem[i]);
663 }
664 }
665
666 if (tree_verts_act) {
667 /* Edge v Vert */
669 tree_edges_act, tree_verts_act, bm_edgexvert_isect_cb, &data, pair_stack_edgexelem);
670 }
671
672 if (tree_verts_remain) {
673 /* Edge v Vert */
675 tree_edges_act, tree_verts_remain, bm_edgexvert_isect_cb, &data, pair_stack_edgexelem);
676 }
677
678 BLI_bvhtree_free(tree_edges_act);
679 }
680
681 if (tree_verts_act && tree_edges_remain) {
682 /* Edge v Vert */
684 tree_edges_remain, tree_verts_act, bm_edgexvert_isect_cb, &data, pair_stack_edgexelem);
685 }
686
687 BLI_bvhtree_free(tree_edges_remain);
688
689 int edgexelem_pair_len = 0;
690 for (i = KDOP_TREE_TYPE; i--;) {
691 if (pair_stack_edgexelem[i]) {
692 edgexelem_pair_len += BLI_stack_count(pair_stack_edgexelem[i]);
693 }
694 }
695
696 pair_len += edgexelem_pair_len;
697 int edgexvert_pair_len = edgexelem_pair_len - edgexedge_pair_len;
698
699 if (edgexelem_pair_len) {
700 pair_array = MEM_new_array_uninitialized<EDBMSplitElem[2]>(pair_len, __func__);
701
702 pair_iter = pair_array;
703 for (i = 0; i < BLI_STACK_PAIR_LEN; i++) {
704 if (pair_stack[i]) {
705 uint count = uint(BLI_stack_count(pair_stack[i]));
706 BLI_stack_pop_n_reverse(pair_stack[i], pair_iter, count);
707 pair_iter += count;
708 }
709 }
710
711 /* Map intersections per edge. */
712 union EdgeIntersectionsMap {
713 struct {
714 int cuts_len;
715 int cuts_index[];
716 };
717 int as_int[0];
718 } *e_map_iter, *e_map;
719
720# ifdef INTERSECT_EDGES_DEBUG
721 int cut_edges_len = 0;
722 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
723 if (e->head.index != 0) {
724 cut_edges_len++;
725 }
726 }
727 BLI_assert(cut_edges_len == data.cut_edges_len);
728# endif
729
730 size_t e_map_size = (data.cut_edges_len * sizeof(*e_map)) +
731 ((size_t(2) * edgexedge_pair_len + edgexvert_pair_len) *
732 sizeof(*(e_map->cuts_index)));
733
734 e_map = static_cast<EdgeIntersectionsMap *>(MEM_new_uninitialized(e_map_size, __func__));
735 int map_len = 0;
736
737 /* Convert every pair to Vert x Vert. */
738
739 /* The list of pairs starts with [vert x vert] followed by [edge x edge]
740 * and finally [edge x vert].
741 * Ignore the [vert x vert] pairs */
742 EDBMSplitElem *pair_flat, *pair_flat_iter;
743 pair_flat = reinterpret_cast<EDBMSplitElem *>(&pair_array[vertxvert_pair_len]);
744 pair_flat_iter = &pair_flat[0];
745 uint pair_flat_len = 2 * edgexelem_pair_len;
746 for (i = 0; i < pair_flat_len; i++, pair_flat_iter++) {
747 if (pair_flat_iter->elem->head.htype != BM_EDGE) {
748 continue;
749 }
750
751 e = pair_flat_iter->edge;
754 int e_cuts_len = e->head.index;
755
756 e_map_iter = reinterpret_cast<EdgeIntersectionsMap *>(&e_map->as_int[map_len]);
757 e_map_iter->cuts_len = e_cuts_len;
758 e_map_iter->cuts_index[0] = i;
759
760 /* Use `e->head.index` to indicate which slot to fill with the `cut` index. */
761 e->head.index = map_len + 1;
762 map_len += 1 + e_cuts_len;
763 }
764 else {
765 e_map->as_int[++e->head.index] = i;
766 }
767 }
768
769 /* Split Edges A to set all Vert x Edge. */
770 for (i = 0; i < map_len;
771 e_map_iter = reinterpret_cast<EdgeIntersectionsMap *>(&e_map->as_int[i]),
772 i += 1 + e_map_iter->cuts_len)
773 {
774
775 /* sort by lambda. */
776 BLI_qsort_r(e_map_iter->cuts_index,
777 e_map_iter->cuts_len,
778 sizeof(*(e_map->cuts_index)),
780 pair_flat);
781
782 float lambda, lambda_prev = 0.0f;
783 for (int j = 0; j < e_map_iter->cuts_len; j++) {
784 uint index = e_map_iter->cuts_index[j];
785
786 EDBMSplitElem *pair_elem = &pair_flat[index];
787 lambda = (pair_elem->lambda - lambda_prev) / (1.0f - lambda_prev);
788 lambda_prev = pair_elem->lambda;
789 e = pair_elem->edge;
790 if (split_faces) {
791 /* Tagged edges are ignored when split faces.
792 * Un-tag these. */
794 }
795
796 BMVert *v_new = BM_edge_split(bm, e, e->v1, nullptr, lambda);
797 pair_elem->vert = v_new;
798 }
799
800 /* As this function uses face-normals to check if a point is "within" a face,
801 * (asserting on stale face normals), recalculated modified faces.
802 * Note that vertex normals are *not* recalculated as it's not needed. */
803 if (BMLoop *l_iter = e->l) {
804 do {
805 BM_face_normal_update(l_iter->f);
806 } while ((l_iter = l_iter->radial_next) != e->l);
807 }
808 }
809
810 MEM_delete(e_map);
811 }
812 }
813#endif
814
815 BLI_bvhtree_free(tree_verts_act);
816 BLI_bvhtree_free(tree_verts_remain);
817
818 if (r_targetmap) {
819 if (pair_len && pair_array == nullptr) {
820 pair_array = MEM_new_array_uninitialized<EDBMSplitElem[2]>(pair_len, __func__);
821 pair_iter = pair_array;
822 for (i = 0; i < BLI_STACK_PAIR_LEN; i++) {
823 if (pair_stack[i]) {
824 uint count = uint(BLI_stack_count(pair_stack[i]));
825 BLI_stack_pop_n_reverse(pair_stack[i], pair_iter, count);
826 pair_iter += count;
827 }
828 }
829 }
830
831 if (pair_array) {
832 BMVert *v_key, *v_val;
833 pair_iter = &pair_array[0];
834 for (i = 0; i < pair_len; i++, pair_iter++) {
835 BLI_assert((*pair_iter)[0].elem->head.htype == BM_VERT);
836 BLI_assert((*pair_iter)[1].elem->head.htype == BM_VERT);
837 BLI_assert((*pair_iter)[0].elem != (*pair_iter)[1].elem);
838 v_key = (*pair_iter)[0].vert;
839 v_val = (*pair_iter)[1].vert;
840 BLI_ghash_insert(r_targetmap, v_key, v_val);
841 }
842
851 pair_iter = &pair_array[0];
852 for (i = 0; i < pair_len; i++, pair_iter++) {
853 v_key = (*pair_iter)[0].vert;
854 v_val = (*pair_iter)[1].vert;
855 BMVert *v_target;
856 while ((v_target = static_cast<BMVert *>(BLI_ghash_lookup(r_targetmap, v_val)))) {
857 v_val = v_target;
858 }
859 if (v_val != (*pair_iter)[1].vert) {
860 BMVert **v_val_p = reinterpret_cast<BMVert **>(BLI_ghash_lookup_p(r_targetmap, v_key));
861 *v_val_p = (*pair_iter)[1].vert = v_val;
862 }
863 if (split_faces) {
864 /* The vertex index indicates its position in the pair_array flat. */
865 BM_elem_index_set(v_key, i * 2);
866 BM_elem_index_set(v_val, i * 2 + 1);
867 }
868 }
869
870 if (split_faces) {
871 BMEdge **edgenet = nullptr;
872 int edgenet_alloc_len = 0;
873
874 EDBMSplitElem *pair_flat = reinterpret_cast<EDBMSplitElem *>(&pair_array[0]);
875 BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
877 /* Edge out of context or already tested. */
878 continue;
879 }
880
881 BMVert *va, *vb, *va_dest = nullptr;
882 va = e->v1;
883 vb = e->v2;
884
885 int v_cut = BM_elem_index_get(va);
886 int v_cut_other = BM_elem_index_get(vb);
887 if (v_cut == -1 && v_cut_other == -1) {
889 /* Edge out of context. */
891 }
892 continue;
893 }
894
895 /* Tag to avoid testing again. */
897
898 if (v_cut == -1) {
899 std::swap(va, vb);
900 v_cut = v_cut_other;
901 v_cut_other = -1;
902 }
903
904 /* `v_cut` indicates the other vertex within the `pair_array`. */
905 v_cut += v_cut % 2 ? -1 : 1;
906 va_dest = pair_flat[v_cut].vert;
907
908 if (BM_vert_pair_share_face_check(va, va_dest)) {
909 /* Vert par acts on the same face.
910 * Although there are cases like this where the face can be split,
911 * for efficiency it is better to ignore then. */
912 continue;
913 }
914
915 BMFace *best_face = nullptr;
916 BMVert *v_other_dest, *v_other = vb;
917 BMEdge *e_net = e;
918 int edgenet_len = 0;
919 while (true) {
920 if (v_cut_other != -1) {
921 v_cut_other += v_cut_other % 2 ? -1 : 1;
922 v_other_dest = pair_flat[v_cut_other].vert;
923
924 if (BM_vert_pair_share_face_check(v_other, v_other_dest)) {
925 /* Vert par acts on the same face.
926 * Although there are cases like this where the face can be split,
927 * for efficiency and to avoid complications, it is better to ignore these cases.
928 */
929 break;
930 }
931 }
932 else {
933 v_other_dest = v_other;
934 }
935
936 if (va_dest == v_other_dest) {
937 /* Edge/Edge-net to vertex - we can't split the face. */
938 break;
939 }
940 if (edgenet_len == 0 && BM_edge_exists(va_dest, v_other_dest)) {
941 /* Edge to edge - no need to detect face. */
942 break;
943 }
944
945 if (edgenet_alloc_len == edgenet_len) {
946 edgenet_alloc_len = (edgenet_alloc_len + 1) * 2;
947 edgenet = static_cast<BMEdge **>(
948 MEM_realloc_uninitialized(edgenet, (edgenet_alloc_len) * sizeof(*edgenet)));
949 }
950 edgenet[edgenet_len++] = e_net;
951
952 best_face = bm_vert_pair_best_face_get(
953 va_dest, v_other_dest, edgenet, edgenet_len, dist);
954
955 if (best_face) {
956 if ((va_dest != va) && !BM_edge_exists(va_dest, va)) {
964 e_net = edgenet[0];
965 if (edgenet_len > 1) {
966 vb = BM_edge_other_vert(e_net, va);
967 }
968 else {
969 vb = v_other_dest;
970 }
971 edgenet[0] = BM_edge_create(bm, va_dest, vb, e_net, BM_CREATE_NOP);
972 }
973 if ((edgenet_len > 1) && (v_other_dest != v_other) &&
974 !BM_edge_exists(v_other_dest, v_other))
975 {
983 e_net = edgenet[edgenet_len - 1];
984 edgenet[edgenet_len - 1] = BM_edge_create(
985 bm, v_other_dest, BM_edge_other_vert(e_net, v_other), e_net, BM_CREATE_NOP);
986 }
987 break;
988 }
989
990 BMEdge *e_test = e_net, *e_next = nullptr;
991 while ((e_test = BM_DISK_EDGE_NEXT(e_test, v_other)) != (e_net)) {
992 if (!BM_edge_is_wire(e_test)) {
993 if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) {
994 continue;
995 }
996 if (!BM_elem_flag_test(e_test->v1, BM_ELEM_TAG) &&
998 {
999 continue;
1000 }
1001 /* Avoids endless loop. */
1003 }
1004 else if (!BM_edge_is_wire(e_net)) {
1005 continue;
1006 }
1007 e_next = e_test;
1008 break;
1009 }
1010
1011 if (e_next == nullptr) {
1012 break;
1013 }
1014
1015 e_net = e_next;
1016 v_other = BM_edge_other_vert(e_net, v_other);
1017 if (v_other == va) {
1018 /* Endless loop. */
1019 break;
1020 }
1021 v_cut_other = BM_elem_index_get(v_other);
1022 }
1023
1024 if (best_face) {
1025 Vector<BMFace *> face_arr;
1026 BM_face_split_edgenet(bm, best_face, edgenet, edgenet_len, &face_arr);
1027 /* Update the new faces normal.
1028 * Normal is necessary to obtain the best face for edgenet */
1029 for (BMFace *face : face_arr) {
1031 }
1032 }
1033 }
1034
1035 if (edgenet) {
1036 MEM_delete(edgenet);
1037 }
1038 }
1039 ok = true;
1040 }
1041 }
1042
1043 for (i = BLI_STACK_PAIR_LEN; i--;) {
1044 if (pair_stack[i]) {
1045 BLI_stack_free(pair_stack[i]);
1046 }
1047 }
1048 if (pair_array) {
1049 MEM_delete(pair_array);
1050 }
1051
1052 return ok;
1053}
1054
1056
1057} // namespace blender
Read Blender memory allocation and freeing.
Provides wrapper around system-specific atomic primitives, and some extensions (faked-atomic operatio...
ATOMIC_INLINE int32_t atomic_fetch_and_add_int32(int32_t *p, int32_t x)
#define IN_RANGE(a, b, c)
#define ELEM(...)
#define IN_RANGE_INCL(a, b, c)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define KDOP_TREE_TYPE
#define KDOP_AXIS_LEN
#define EDGE_REMAIN_TO_TEST
#define BLI_STACK_PAIR_LEN
#define EDGE_ACT_TO_TEST
#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 MEM_realloc_uninitialized(vmemh, len)
btScalar max
bool closest(btVector3 &v)
#define FLT_MAX
#define FLT_EPSILON
float dot(VecOp< float, D >, VecOp< float, D >) RET
ccl_device_inline int as_int(const uint i)
Definition math_base.h:240
BMesh Iterators.
MINLINE void madd_v3_v3v3fl(float r[3], const float a[3], const float b[3], float f)
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
BVHTreeOverlap * BLI_bvhtree_overlap_ex(const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, uint max_interactions, int flag)
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BMFace * BM_vert_pair_shared_face_cb(BMVert *v_a, BMVert *v_b, const bool allow_adjacent, bool(*callback)(BMFace *, BMLoop *, BMLoop *, void *userdata), void *user_data, BMLoop **r_l_a, BMLoop **r_l_b)
bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
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
void BLI_stack_free(BLI_Stack *stack) ATTR_NONNULL()
Definition stack.cc:99
BLI_INLINE BMEdge * BM_edge_at_index(BMesh *bm, const int index)
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:735
void BLI_bvhtree_free(BVHTree *tree)
void BLI_bvhtree_balance(BVHTree *tree)
ATTR_WARN_UNUSED_RESULT const BMVert * v
static BMFace * bm_vert_pair_best_face_get(BMVert *v_a, BMVert *v_b, BMEdge **edgenet, const int edgenet_len, const float epsilon)
static bool bm_vert_pair_share_best_splittable_face_cb(BMFace *f, BMLoop *l_a, BMLoop *l_b, void *userdata)
void * BLI_stack_push_r(BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:106
float ray_point_factor_v3_ex(const float p[3], const float ray_origin[3], const float ray_direction[3], float epsilon, float fallback)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BLI_ghash_insert(GHash *gh, void *key, void *val)
Definition BLI_ghash.cc:711
bool isect_ray_ray_epsilon_v3(const float ray_origin_a[3], const float ray_direction_a[3], const float ray_origin_b[3], const float ray_direction_b[3], float epsilon, float *r_lambda_a, float *r_lambda_b)
bool BM_face_point_inside_test(const BMFace *f, const float co[3])
void ** BLI_ghash_lookup_p(GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
Definition BLI_ghash.cc:749
@ BM_CREATE_NOP
Definition bmesh_core.hh:34
void BM_face_normal_update(BMFace *f)
size_t BLI_stack_count(const BLI_Stack *stack) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:231
BMesh const char void * data
static bool bm_edgexedge_isect_impl(EDBMSplitData *data, BMEdge *e_a, BMEdge *e_b, const float co_a[3], const float dir_a[3], const float co_b[3], const float dir_b[3], float lambda_a, float lambda_b, EDBMSplitElem r_pair[2])
ATTR_WARN_UNUSED_RESULT const BMLoop * l_b
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
bool BM_vert_pair_share_face_check(BMVert *v_a, BMVert *v_b)
static void bm_edge_pair_elem_setup(BMEdge *e, float lambda, int *r_data_cut_edges_len, EDBMSplitElem *r_pair_elem)
static int sort_cmp_by_lambda_cb(const void *index1_v, const void *index2_v, void *keys_v)
@ BVH_OVERLAP_USE_THREADING
BLI_INLINE BMVert * BM_vert_at_index(BMesh *bm, const int index)
bool isect_ray_ray_v3(const float ray_origin_a[3], const float ray_direction_a[3], const float ray_origin_b[3], const float ray_direction_b[3], float *r_lambda_a, float *r_lambda_b)
int BLI_bvhtree_overlap_thread_num(const BVHTree *tree)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
bool(*)(void *userdata, int index_a, int index_b, int thread) BVHTree_OverlapCallback
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.
void BLI_stack_pop_n_reverse(BLI_Stack *stack, void *dst, unsigned int n) ATTR_NONNULL()
Definition stack.cc:160
static bool bm_vert_pair_share_splittable_face_cb(BMFace *, BMLoop *l_a, BMLoop *l_b, void *userdata)
void BLI_qsort_r(void *a, size_t n, size_t es, BLI_sort_cmp_t cmp, void *thunk)
Definition sort.cc:79
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
MINLINE float square_f(float a)
bool BM_face_split_edgenet(BMesh *bm, BMFace *f, BMEdge **edge_net, const int edge_net_len, Vector< BMFace * > *r_face_arr)
bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, const bool split_faces, GHash *r_targetmap)
static bool bm_edgexedge_self_isect_cb(void *userdata, int index_a, int index_b, int thread)
static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int thread)
static bool bm_edgexvert_isect_impl(BMVert *v, BMEdge *e, const float co[3], const float dir[3], float lambda, float data_dist_sq, int *data_cut_edges_len, EDBMSplitElem r_pair[2])
static bool bm_edgexedge_isect_cb(void *userdata, int index_a, int index_b, int thread)
bool BM_edge_share_vert_check(BMEdge *e1, BMEdge *e2)
static void bm_elemxelem_bvhtree_overlap(const BVHTree *tree1, const BVHTree *tree2, BVHTree_OverlapCallback callback, EDBMSplitData *data, BLI_Stack **pair_stack)
static bool bm_vertxvert_isect_cb(void *userdata, int index_a, int index_b, int thread)
BLI_Stack * BLI_stack_new(size_t elem_size, const char *description) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
Definition stack.cc:85
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static void bm_vert_pair_elem_setup_ex(BMVert *v, EDBMSplitElem *r_pair_elem)
BMEdge * BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *e_example, const eBMCreateFlag create_flag)
Main function for creating a new edge.
static bool bm_vertxvert_self_isect_cb(void *userdata, int index_a, int index_b, int thread)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
#define min(a, b)
Definition sort.cc:38
struct BMLoop * next
struct BMLoop * prev
struct BMVert * v