[Bf-blender-cvs] [1bfa9539d3b] master: Fix T91889 Exact boolean sometimes drops triangles.
Howard Trickey
noreply at git.blender.org
Mon Oct 11 01:59:35 CEST 2021
Commit: 1bfa9539d3b50da2530c6273d2f692fb57f9c267
Author: Howard Trickey
Date: Sun Oct 10 19:54:02 2021 -0400
Branches: master
https://developer.blender.org/rB1bfa9539d3b50da2530c6273d2f692fb57f9c267
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.
===================================================================
M source/blender/blenlib/intern/mesh_intersect.cc
===================================================================
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;
}
More information about the Bf-blender-cvs
mailing list