diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2021-10-11 02:54:02 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2021-10-11 02:54:02 +0300 |
commit | 1bfa9539d3b50da2530c6273d2f692fb57f9c267 (patch) | |
tree | a199f7cbb813d2410d8c6e55cb153e6ab3cf9386 /source/blender/blenlib/intern/mesh_intersect.cc | |
parent | 79425ed3267663ee482ee3ffcc542d86888103af (diff) |
Fix T91889 Exact boolean sometimes drops triangles.
The problem is that the fast triangulator (based on polyfill)
sometimes makes degenerate triangles. Commit 8115f0c5bd91f had
a check for degenerate triangles but it wasn't thorough enough.
This commit uses a more thorough (and pessimistic) test for
degenerate triangles, using the exact triangulator in those cases.
Diffstat (limited to 'source/blender/blenlib/intern/mesh_intersect.cc')
-rw-r--r-- | source/blender/blenlib/intern/mesh_intersect.cc | 20 |
1 files changed, 18 insertions, 2 deletions
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc index 526871c7b1f..8276890eec1 100644 --- a/source/blender/blenlib/intern/mesh_intersect.cc +++ b/source/blender/blenlib/intern/mesh_intersect.cc @@ -2225,8 +2225,7 @@ static bool face_is_degenerate(const Face *f) return false; } -/** Fast check for degenerate tris. Only tests for when verts are identical, - * not cases where there are zero-length edges. */ +/** Fast check for degenerate tris. It is OK if it returns true for nearly degenerate triangles. */ static bool any_degenerate_tris_fast(const Array<Face *> triangulation) { for (const Face *f : triangulation) { @@ -2236,6 +2235,23 @@ static bool any_degenerate_tris_fast(const Array<Face *> triangulation) if (v0 == v1 || v0 == v2 || v1 == v2) { return true; } + double3 da = v2->co - v0->co; + double3 db = v2->co - v1->co; + double da_length_squared = da.length_squared(); + double db_length_squared = db.length_squared(); + if (da_length_squared == 0.0 || db_length_squared == 0.0) { + return true; + } + /* |da x db| = |da| |db| sin t, where t is angle between them. + * The triangle is almost degenerate if sin t is almost 0. + * sin^2 t = |da x db|^2 / (|da|^2 |db|^2) + */ + double3 dab = double3::cross_high_precision(da, db); + double dab_length_squared = dab.length_squared(); + double sin_squared_t = dab_length_squared / (da_length_squared * db_length_squared); + if (sin_squared_t < 1e-8) { + return true; + } } return false; } |