Fix T47998: Limited dissolve fails /w holes
Holes with flat surfaces could have their edges dissolved causing degenerate faces. Now check that collapsing a vertices isn't creating self-overlapping faces.
This commit is contained in:
parent
74b0591d42
commit
12b0c03e49
Notes:
blender-bot
2023-02-14 08:01:58 +01:00
Referenced by issue #47998, Decimate Modifier; Bad geometry when following subsurf with planar decimation on a mesh with holes
|
@ -37,6 +37,9 @@
|
|||
#include "bmesh.h"
|
||||
#include "bmesh_decimate.h" /* own include */
|
||||
|
||||
/* check that collapsing a vertex between 2 edges doesn't cause a degenerate face. */
|
||||
#define USE_DEGENERATE_CHECK
|
||||
|
||||
#define COST_INVALID FLT_MAX
|
||||
|
||||
|
||||
|
@ -137,6 +140,118 @@ fail:
|
|||
}
|
||||
|
||||
|
||||
#ifdef USE_DEGENERATE_CHECK
|
||||
|
||||
static void mul_v2_m3v3_center(float r[2], float m[3][3], const float a[3], const float center[3])
|
||||
{
|
||||
BLI_assert(r != a);
|
||||
BLI_assert(r != center);
|
||||
|
||||
float co[3];
|
||||
sub_v3_v3v3(co, a, center);
|
||||
|
||||
r[0] = m[0][0] * co[0] + m[1][0] * co[1] + m[2][0] * co[2];
|
||||
r[1] = m[0][1] * co[0] + m[1][1] * co[1] + m[2][1] * co[2];
|
||||
}
|
||||
|
||||
static bool bm_loop_collapse_is_degenerate(BMLoop *l_ear)
|
||||
{
|
||||
/* calculate relative to the centeral vertex for higher precision */
|
||||
const float *center = l_ear->v->co;
|
||||
|
||||
float tri_2d[3][2];
|
||||
float axis_mat[3][3];
|
||||
|
||||
axis_dominant_v3_to_m3(axis_mat, l_ear->f->no);
|
||||
|
||||
{
|
||||
mul_v2_m3v3_center(tri_2d[0], axis_mat, l_ear->prev->v->co, center);
|
||||
#if 0
|
||||
mul_v2_m3v3_center(tri_2d[1], axis_mat, l_ear->v->co, center);
|
||||
#else
|
||||
zero_v2(tri_2d[1]);
|
||||
#endif
|
||||
mul_v2_m3v3_center(tri_2d[2], axis_mat, l_ear->next->v->co, center);
|
||||
}
|
||||
|
||||
/* check we're not flipping face corners before or after the ear */
|
||||
{
|
||||
float adjacent_2d[2];
|
||||
|
||||
if (!BM_vert_is_edge_pair(l_ear->prev->v)) {
|
||||
mul_v2_m3v3_center(adjacent_2d, axis_mat, l_ear->prev->prev->v->co, center);
|
||||
if (signum_i(cross_tri_v2(adjacent_2d, tri_2d[0], tri_2d[1])) !=
|
||||
signum_i(cross_tri_v2(adjacent_2d, tri_2d[0], tri_2d[2])))
|
||||
{
|
||||
return true;
|
||||
}
|
||||
}
|
||||
|
||||
if (!BM_vert_is_edge_pair(l_ear->next->v)) {
|
||||
mul_v2_m3v3_center(adjacent_2d, axis_mat, l_ear->next->next->v->co, center);
|
||||
if (signum_i(cross_tri_v2(adjacent_2d, tri_2d[2], tri_2d[1])) !=
|
||||
signum_i(cross_tri_v2(adjacent_2d, tri_2d[2], tri_2d[0])))
|
||||
{
|
||||
return true;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
/* check no existing verts are inside the triangle */
|
||||
{
|
||||
/* triangle may be concave, if so - flip so we can use clockwise check */
|
||||
if (cross_tri_v2(UNPACK3(tri_2d)) < 0.0f) {
|
||||
swap_v2_v2(tri_2d[1], tri_2d[2]);
|
||||
}
|
||||
|
||||
/* skip l_ear and adjacent verts */
|
||||
BMLoop *l_iter, *l_first;
|
||||
|
||||
l_iter = l_ear->next->next;
|
||||
l_first = l_ear->prev;
|
||||
do {
|
||||
float co_2d[2];
|
||||
mul_v2_m3v3_center(co_2d, axis_mat, l_iter->v->co, center);
|
||||
if (isect_point_tri_v2_cw(co_2d, tri_2d[0], tri_2d[1], tri_2d[2])) {
|
||||
return true;
|
||||
}
|
||||
} while ((l_iter = l_iter->next) != l_first);
|
||||
}
|
||||
|
||||
return false;
|
||||
}
|
||||
|
||||
static bool bm_vert_collapse_is_degenerate(BMVert *v)
|
||||
{
|
||||
BMEdge *e_pair[2];
|
||||
BMVert *v_pair[2];
|
||||
|
||||
if (BM_vert_edge_pair(v, &e_pair[0], &e_pair[1])) {
|
||||
v_pair[0] = BM_edge_other_vert(e_pair[0], v);
|
||||
v_pair[1] = BM_edge_other_vert(e_pair[1], v);
|
||||
|
||||
if (fabsf(cos_v3v3v3(v_pair[0]->co, v->co, v_pair[1]->co)) < (1.0f - FLT_EPSILON)) {
|
||||
BMLoop *l_iter, *l_first;
|
||||
l_iter = l_first = e_pair[1]->l;
|
||||
do {
|
||||
if (l_iter->f->len > 3) {
|
||||
BMLoop *l_pivot = (l_iter->v == v ? l_iter : l_iter->next);
|
||||
BLI_assert(v == l_pivot->v);
|
||||
if (bm_loop_collapse_is_degenerate(l_pivot)) {
|
||||
return true;
|
||||
}
|
||||
}
|
||||
} while ((l_iter = l_iter->radial_next) != l_first);
|
||||
}
|
||||
return false;
|
||||
}
|
||||
else {
|
||||
return true;
|
||||
}
|
||||
}
|
||||
#endif /* USE_DEGENERATE_CHECK */
|
||||
|
||||
|
||||
void BM_mesh_decimate_dissolve_ex(
|
||||
BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries,
|
||||
BMO_Delimit delimit,
|
||||
|
@ -328,7 +443,14 @@ void BM_mesh_decimate_dissolve_ex(
|
|||
v = BLI_heap_node_ptr(vnode_top);
|
||||
i = BM_elem_index_get(v);
|
||||
|
||||
if (BM_vert_is_edge_pair(v)) {
|
||||
if (
|
||||
#ifdef USE_DEGENERATE_CHECK
|
||||
!bm_vert_collapse_is_degenerate(v)
|
||||
#else
|
||||
BM_vert_is_edge_pair(v)
|
||||
#endif
|
||||
)
|
||||
{
|
||||
e_new = BM_vert_collapse_edge(bm, v->e, v, true, true); /* join edges */
|
||||
|
||||
if (e_new) {
|
||||
|
@ -343,7 +465,6 @@ void BM_mesh_decimate_dissolve_ex(
|
|||
do {
|
||||
BM_face_normal_update(l_iter->f);
|
||||
} while ((l_iter = l_iter->radial_next) != l_first);
|
||||
|
||||
}
|
||||
|
||||
/* re-calculate costs */
|
||||
|
@ -355,6 +476,31 @@ void BM_mesh_decimate_dissolve_ex(
|
|||
vheap_table[j] = BLI_heap_insert(vheap, cost, v_iter);
|
||||
}
|
||||
}
|
||||
|
||||
#ifdef USE_DEGENERATE_CHECK
|
||||
/* dissolving a vertex may mean vertices we previously weren't able to dissolve
|
||||
* can bow be re-evaluated. */
|
||||
if (e_new->l) {
|
||||
BMLoop *l_first, *l_iter;
|
||||
l_iter = l_first = e_new->l;
|
||||
do {
|
||||
BMLoop *l_cycle_first, *l_cycle_iter;
|
||||
l_cycle_iter = l_cycle_first = l_iter;
|
||||
do {
|
||||
const int j = BM_elem_index_get(l_cycle_iter->v);
|
||||
if (j != -1 && vheap_table[j] &&
|
||||
(BLI_heap_node_value(vheap_table[j]) == COST_INVALID))
|
||||
{
|
||||
const float cost = bm_vert_edge_face_angle(l_cycle_iter->v);
|
||||
BLI_heap_remove(vheap, vheap_table[j]);
|
||||
vheap_table[j] = BLI_heap_insert(vheap, cost, l_cycle_iter->v);
|
||||
}
|
||||
} while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_first);
|
||||
|
||||
} while ((l_iter = l_iter->radial_next) != l_first);
|
||||
}
|
||||
#endif /* USE_DEGENERATE_CHECK */
|
||||
|
||||
}
|
||||
}
|
||||
|
||||
|
|
Loading…
Reference in New Issue