Welcome to mirror list, hosted at ThFree Co, Russian Federation.

git.blender.org/blender.git - Unnamed repository; edit this file 'description' to name the repository.
summaryrefslogtreecommitdiff
path: root/source/blender/bmesh
diff options
context:
space:
mode:
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r--source/blender/bmesh/intern/bmesh_polygon_edgenet.c128
-rw-r--r--source/blender/bmesh/tools/bmesh_decimate_collapse.c3
-rw-r--r--source/blender/bmesh/tools/bmesh_intersect.c80
3 files changed, 140 insertions, 71 deletions
diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
index c142dcae514..5ee0e904a33 100644
--- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
+++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
@@ -97,12 +97,22 @@ static BMLoop *bm_edge_flagged_radial_first(BMEdge *e)
return NULL;
}
+static void normalize_v2_m3_v3v3(float out[2], float axis_mat[3][3], const float v1[3], const float v2[3])
+{
+ float dir[3];
+ sub_v3_v3v3(dir, v1, v2);
+ mul_v2_m3v3(out, axis_mat, dir);
+ normalize_v2(out);
+}
+
+
/**
* \note Be sure to update #bm_face_split_edgenet_find_loop_pair_exists
* when making changed to edge picking logic.
*/
static bool bm_face_split_edgenet_find_loop_pair(
- BMVert *v_init, const float face_normal[3],
+ BMVert *v_init,
+ const float face_normal[3], float face_normal_matrix[3][3],
BMEdge *e_pair[2])
{
/* Always find one boundary edge (to determine winding)
@@ -142,10 +152,17 @@ static bool bm_face_split_edgenet_find_loop_pair(
}
e_pair[0] = BLI_SMALLSTACK_POP(edges_boundary);
+ /* use to hold boundary OR wire edges */
+ BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *);
+
/* attempt one boundary and one wire, or 2 boundary */
if (edges_wire_len == 0) {
- if (edges_boundary_len >= 2) {
+ if (edges_boundary_len > 1) {
e_pair[1] = BLI_SMALLSTACK_POP(edges_boundary);
+
+ if (edges_boundary_len > 2) {
+ BLI_SMALLSTACK_SWAP(edges_search, edges_wire);
+ }
}
else {
/* one boundary and no wire */
@@ -154,28 +171,37 @@ static bool bm_face_split_edgenet_find_loop_pair(
}
else {
e_pair[1] = BLI_SMALLSTACK_POP(edges_wire);
-
if (edges_wire_len > 1) {
- BMVert *v_prev = BM_edge_other_vert(e_pair[0], v_init);
- BMVert *v_next;
- float angle_best;
-
- v_next = BM_edge_other_vert(e_pair[1], v_init);
- angle_best = angle_on_axis_v3v3v3_v3(v_prev->co, v_init->co, v_next->co, face_normal);
-
- BMEdge *e;
- while ((e = BLI_SMALLSTACK_POP(edges_wire))) {
- float angle_test;
- v_next = BM_edge_other_vert(e, v_init);
- angle_test = angle_on_axis_v3v3v3_v3(v_prev->co, v_init->co, v_next->co, face_normal);
- if (angle_test < angle_best) {
- angle_best = angle_test;
- e_pair[1] = e;
- }
- }
+ BLI_SMALLSTACK_SWAP(edges_search, edges_wire);
}
}
+ /* if we swapped above, search this list for the best edge */
+ if (!BLI_SMALLSTACK_IS_EMPTY(edges_search)) {
+ /* find the best edge in 'edge_list' to use for 'e_pair[1]' */
+ const BMVert *v_prev = BM_edge_other_vert(e_pair[0], v_init);
+ const BMVert *v_next = BM_edge_other_vert(e_pair[1], v_init);
+
+ float dir_prev[2], dir_next[2];
+
+ normalize_v2_m3_v3v3(dir_prev, face_normal_matrix, v_prev->co, v_init->co);
+ normalize_v2_m3_v3v3(dir_next, face_normal_matrix, v_next->co, v_init->co);
+ float angle_best_cos = dot_v2v2(dir_next, dir_prev);
+
+ BMEdge *e;
+ while ((e = BLI_SMALLSTACK_POP(edges_search))) {
+ v_next = BM_edge_other_vert(e, v_init);
+ float dir_test[2];
+
+ normalize_v2_m3_v3v3(dir_test, face_normal_matrix, v_next->co, v_init->co);
+ const float angle_test_cos = dot_v2v2(dir_prev, dir_test);
+
+ if (angle_test_cos > angle_best_cos) {
+ angle_best_cos = angle_test_cos;
+ e_pair[1] = e;
+ }
+ }
+ }
/* flip based on winding */
l_walk = bm_edge_flagged_radial_first(e_pair[0]);
@@ -309,36 +335,40 @@ walk_nofork:
BMEdge *e_next, *e_first;
e_first = v->e;
e_next = BM_DISK_EDGE_NEXT(e_first, v); /* always skip this verts edge */
- do {
- BLI_assert(v->e != e_next);
- if ((BM_ELEM_API_FLAG_TEST(e_next, EDGE_NET)) &&
- (bm_edge_flagged_radial_count(e_next) < 2))
- {
- BMVert *v_next;
- v_next = BM_edge_other_vert(e_next, v);
+ /* in rare cases there may be edges with a single connecting vertex */
+ if (e_next != e_first) {
+ do {
+ if ((BM_ELEM_API_FLAG_TEST(e_next, EDGE_NET)) &&
+ (bm_edge_flagged_radial_count(e_next) < 2))
+ {
+ BMVert *v_next;
+
+ v_next = BM_edge_other_vert(e_next, v);
+ BLI_assert(v->e != e_next);
#ifdef DEBUG_PRINT
- /* indent and print */
- {
- BMVert *_v = v;
- do {
- printf(" ");
- } while ((_v = BM_edge_other_vert(_v->e, _v)) != v_init);
- printf("vert %d -> %d (add=%d)\n",
- BM_elem_index_get(v), BM_elem_index_get(v_next),
- BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT) == 0);
- }
+ /* indent and print */
+ {
+ BMVert *_v = v;
+ do {
+ printf(" ");
+ } while ((_v = BM_edge_other_vert(_v->e, _v)) != v_init);
+ printf("vert %d -> %d (add=%d)\n",
+ BM_elem_index_get(v), BM_elem_index_get(v_next),
+ BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT) == 0);
+ }
#endif
- if (!BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT)) {
- eo = STACK_PUSH_RET_PTR(edge_order);
- eo->v = v_next;
+ if (!BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT)) {
+ eo = STACK_PUSH_RET_PTR(edge_order);
+ eo->v = v_next;
- v_next->e = e_next;
+ v_next->e = e_next;
+ }
}
- }
- } while ((e_next = BM_DISK_EDGE_NEXT(e_next, v)) != e_first);
+ } while ((e_next = BM_DISK_EDGE_NEXT(e_next, v)) != e_first);
+ }
#ifdef USE_FASTPATH_NOFORK
if (STACK_SIZE(edge_order) == 1) {
@@ -388,7 +418,7 @@ finally:
}
static bool bm_face_split_edgenet_find_loop(
- BMVert *v_init, const float face_normal[3],
+ BMVert *v_init, const float face_normal[3], float face_normal_matrix[3][3],
/* cache to avoid realloc every time */
struct VertOrder *edge_order, const unsigned int edge_order_len,
BMVert **r_face_verts, int *r_face_verts_len)
@@ -396,7 +426,7 @@ static bool bm_face_split_edgenet_find_loop(
BMEdge *e_pair[2];
BMVert *v;
- if (!bm_face_split_edgenet_find_loop_pair(v_init, face_normal, e_pair)) {
+ if (!bm_face_split_edgenet_find_loop_pair(v_init, face_normal, face_normal_matrix, e_pair)) {
return false;
}
@@ -491,12 +521,18 @@ bool BM_face_split_edgenet(
BM_ELEM_API_FLAG_ENABLE(l_iter->e, EDGE_NET);
} while ((l_iter = l_iter->next) != l_first);
+ float face_normal_matrix[3][3];
+ axis_dominant_v3_to_m3(face_normal_matrix, f->no);
+
/* any vert can be used to begin with */
STACK_PUSH(vert_queue, l_first->v);
while ((v = STACK_POP(vert_queue))) {
- if (bm_face_split_edgenet_find_loop(v, f->no, edge_order, edge_order_len, face_verts, &face_verts_len)) {
+ if (bm_face_split_edgenet_find_loop(
+ v, f->no, face_normal_matrix,
+ edge_order, edge_order_len, face_verts, &face_verts_len))
+ {
BMFace *f_new;
f_new = BM_face_create_verts(bm, face_verts, face_verts_len, f, BM_CREATE_NOP, false);
diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c
index b4e8bb06afe..52a0df5b9d1 100644
--- a/source/blender/bmesh/tools/bmesh_decimate_collapse.c
+++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c
@@ -1292,7 +1292,8 @@ static bool bm_decim_edge_collapse(
* \param factor face count multiplier [0 - 1]
* \param vweights Optional array of vertex aligned weights [0 - 1],
* a vertex group is the usual source for this.
- * \param axis: Axis of symmetry, -1 to disable mirror decimate.
+ * \param symmetry_axis: Axis of symmetry, -1 to disable mirror decimate.
+ * \param symmetry_eps: Threshold when matching mirror verts.
*/
void BM_mesh_decimate_collapse(
BMesh *bm,
diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c
index 9d1f7fa45d2..bd6a68faabb 100644
--- a/source/blender/bmesh/tools/bmesh_intersect.c
+++ b/source/blender/bmesh/tools/bmesh_intersect.c
@@ -87,6 +87,18 @@
// #define USE_DUMP
+/* use only for small arrays */
+BLI_INLINE bool array_contains_pointer(const void **arr, unsigned int arr_len, const void *item)
+{
+ BLI_assert(arr_len < 3);
+ for (unsigned int i = 0; i < arr_len; i++) {
+ if (arr[i] == item) {
+ return true;
+ }
+ }
+ return false;
+}
+
static void tri_v3_scale(
float v1[3], float v2[3], float v3[3],
const float t)
@@ -535,6 +547,7 @@ static void bm_isect_tri_tri(
const float *f_b_cos[3] = {UNPACK3_EX(, fv_b, ->co)};
float f_a_nor[3];
float f_b_nor[3];
+ /* track vertices which have been added to 'iv_ls_a' & 'iv_ls_b' */
int a_mask = 0;
int b_mask = 0;
unsigned int i;
@@ -556,6 +569,24 @@ static void bm_isect_tri_tri(
STACK_INIT(iv_ls_a, ARRAY_SIZE(iv_ls_a));
STACK_INIT(iv_ls_b, ARRAY_SIZE(iv_ls_b));
+ /* don't test, but we must be sure not to add doubles (assert instead). */
+#ifndef NDEBUG
+# define STACK_PUSH_NOTEST(arr, ele) \
+ { \
+ BLI_assert(BLI_array_findindex(arr, STACK_SIZE(arr), &(ele)) == -1); \
+ STACK_PUSH(arr, ele); \
+ } ((void)0)
+#else
+# define STACK_PUSH_NOTEST STACK_PUSH
+#endif
+
+ /* warning, this seems like it might be inefficent,
+ * however there will be <3 items in this case. */
+# define STACK_PUSH_TEST(arr, ele, arr_offset) \
+ if (!array_contains_pointer((const void **)(&(arr)[arr_offset]), STACK_SIZE(arr) - (arr_offset), (void *)ele)) { \
+ STACK_PUSH(arr, ele); \
+ } ((void)0)
+
/* vert-vert
* --------- */
{
@@ -568,7 +599,7 @@ static void bm_isect_tri_tri(
for (i_b = 0; i_b < 3; i_b++) {
if (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
if (!((1 << i_a) & a_mask)) {
- STACK_PUSH(iv_ls_a, fv_a[i_a]);
+ STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]);
a_mask |= (1 << i_a);
#ifdef USE_DUMP
printf(" ('VERT-VERT-A') %d, %d),\n",
@@ -576,7 +607,7 @@ static void bm_isect_tri_tri(
#endif
}
if (!((1 << i_b) & b_mask)) {
- STACK_PUSH(iv_ls_b, fv_b[i_b]);
+ STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
b_mask |= (1 << i_b);
#ifdef USE_DUMP
printf(" ('VERT-VERT-B') %d, %d),\n",
@@ -606,8 +637,8 @@ static void bm_isect_tri_tri(
interp_v3_v3v3(ix, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co, fac);
if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
BMEdge *e;
- STACK_PUSH(iv_ls_b, fv_a[i_a]);
- // STACK_PUSH(iv_ls_a, fv_a[i_a]);
+ STACK_PUSH_NOTEST(iv_ls_b, fv_a[i_a]);
+ // STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]);
a_mask |= (1 << i_a);
e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]);
#ifdef USE_DUMP
@@ -644,8 +675,8 @@ static void bm_isect_tri_tri(
interp_v3_v3v3(ix, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co, fac);
if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
BMEdge *e;
- STACK_PUSH(iv_ls_a, fv_b[i_b]);
- // STACK_PUSH(iv_ls_b, fv_b[i_b]);
+ STACK_PUSH_NOTEST(iv_ls_a, fv_b[i_b]);
+ // STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
b_mask |= (1 << i_b);
e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]);
#ifdef USE_DUMP
@@ -685,11 +716,8 @@ static void bm_isect_tri_tri(
continue;
if (isect_point_tri_v3(fv_a[i_a]->co, UNPACK3(t_scale), ix)) {
if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
- BLI_assert(BLI_array_findindex(iv_ls_a, STACK_SIZE(iv_ls_a), fv_a[i_a]) == -1);
- BLI_assert(BLI_array_findindex(iv_ls_b, STACK_SIZE(iv_ls_b), fv_a[i_a]) == -1);
-
- STACK_PUSH(iv_ls_a, fv_a[i_a]);
- STACK_PUSH(iv_ls_b, fv_a[i_a]);
+ STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]);
+ STACK_PUSH_NOTEST(iv_ls_b, fv_a[i_a]);
a_mask |= (1 << i_a);
#ifdef USE_DUMP
printf(" 'VERT TRI-A',\n");
@@ -715,11 +743,8 @@ static void bm_isect_tri_tri(
if (isect_point_tri_v3(fv_b[i_b]->co, UNPACK3(t_scale), ix)) {
if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
- BLI_assert(BLI_array_findindex((void **)iv_ls_a, STACK_SIZE(iv_ls_a), fv_b[i_b]) == -1);
- BLI_assert(BLI_array_findindex((void **)iv_ls_b, STACK_SIZE(iv_ls_b), fv_b[i_b]) == -1);
-
- STACK_PUSH(iv_ls_a, fv_b[i_b]);
- STACK_PUSH(iv_ls_b, fv_b[i_b]);
+ STACK_PUSH_NOTEST(iv_ls_a, fv_b[i_b]);
+ STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
b_mask |= (1 << i_b);
#ifdef USE_DUMP
printf(" 'VERT TRI-B',\n");
@@ -744,6 +769,17 @@ static void bm_isect_tri_tri(
/* edge-tri & edge-edge
* -------------------- */
{
+ /**
+ * Note that its possible to add the same vertex multiple times
+ * with near degenerate faces (or a large epsilon).
+ *
+ * For this reason we have #STACK_PUSH_TEST macro which only adds vertices that aren't already added.
+ * Since we know none of the vertices from #bm_isect_edge_tri, the check can be offset.
+ */
+
+ const unsigned int iv_ls_a_offset = STACK_SIZE(iv_ls_a);
+ const unsigned int iv_ls_b_offset = STACK_SIZE(iv_ls_b);
+
unsigned int i_e0;
for (i_e0 = 0; i_e0 < 3; i_e0++) {
unsigned int i_e1 = (i_e0 + 1) % 3;
@@ -753,10 +789,8 @@ static void bm_isect_tri_tri(
continue;
iv = bm_isect_edge_tri(s, fv_a[i_e0], fv_a[i_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
if (iv) {
- BLI_assert(BLI_array_findindex((void **)iv_ls_a, STACK_SIZE(iv_ls_a), iv) == -1);
- BLI_assert(BLI_array_findindex((void **)iv_ls_b, STACK_SIZE(iv_ls_b), iv) == -1);
- STACK_PUSH(iv_ls_a, iv);
- STACK_PUSH(iv_ls_b, iv);
+ STACK_PUSH_TEST(iv_ls_a, iv, iv_ls_a_offset);
+ STACK_PUSH_TEST(iv_ls_b, iv, iv_ls_b_offset);
#ifdef USE_DUMP
printf(" ('EDGE-TRI-A', %d),\n", side);
#endif
@@ -771,10 +805,8 @@ static void bm_isect_tri_tri(
continue;
iv = bm_isect_edge_tri(s, fv_b[i_e0], fv_b[i_e1], fv_a, a_index, f_a_cos, f_a_nor, &side);
if (iv) {
- BLI_assert(BLI_array_findindex((void **)iv_ls_a, STACK_SIZE(iv_ls_a), iv) == -1);
- BLI_assert(BLI_array_findindex((void **)iv_ls_b, STACK_SIZE(iv_ls_b), iv) == -1);
- STACK_PUSH(iv_ls_a, iv);
- STACK_PUSH(iv_ls_b, iv);
+ STACK_PUSH_TEST(iv_ls_a, iv, iv_ls_a_offset);
+ STACK_PUSH_TEST(iv_ls_b, iv, iv_ls_b_offset);
#ifdef USE_DUMP
printf(" ('EDGE-TRI-B', %d),\n", side);
#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-08-12 10:57:37 +0300