diff options
author | Brecht Van Lommel <brechtvanlommel@gmail.com> | 2020-12-31 09:49:19 +0300 |
---|---|---|
committer | Brecht Van Lommel <brecht@blender.org> | 2021-01-13 20:24:33 +0300 |
commit | 21b9231d7f5a248027c32dcc7daab3318390c20f (patch) | |
tree | d839a6a1f178c8f1506bce881f94be7575d12607 /source/blender/blenlib/intern/math_geom.c | |
parent | 00b2c7c5ccc38fd80b3264b248157683b366491f (diff) |
Transform: geodesic distances for proportional edit connected mode
Use approximate geodesic distance computatiom that crosses through triangles
rather than only along edges. Using only edges would give artifacts already
on a simple grid.
Fixes T78752, T35590, T43393, T53602
Differential Revision: https://developer.blender.org/D10068
Diffstat (limited to 'source/blender/blenlib/intern/math_geom.c')
-rw-r--r-- | source/blender/blenlib/intern/math_geom.c | 53 |
1 files changed, 53 insertions, 0 deletions
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c index 3cc4d03d547..563457603bd 100644 --- a/source/blender/blenlib/intern/math_geom.c +++ b/source/blender/blenlib/intern/math_geom.c @@ -6246,3 +6246,56 @@ float cubic_tangent_factor_circle_v3(const float tan_l[3], const float tan_r[3]) const float angle_cos = cosf(angle); return ((1.0f - angle_cos) / (angle_sin * 2.0f)) / angle_sin; } + +/** + * Utility for computing approximate geodesic distances on triangle meshes. + * + * Given triangle with vertex coordinates v0, v1, v2, and known geodesic distances + * dist1 and dist2 at v1 and v2, estimate a geodesic distance at vertex v0. + * + * From "Dart Throwing on Surfaces", EGSR 2009. Section 7, Geodesic Dart Throwing. + */ +float geodesic_distance_propagate_across_triangle( + const float v0[3], const float v1[3], const float v2[3], const float dist1, const float dist2) +{ + /* Vectors along triangle edges. */ + float v10[3], v12[3]; + sub_v3_v3v3(v10, v0, v1); + sub_v3_v3v3(v12, v2, v1); + + if (dist1 != 0.0f && dist2 != 0.0f) { + /* Local coordinate system in the triangle plane. */ + float u[3], v[3], n[3]; + const float d12 = normalize_v3_v3(u, v12); + + if (d12 * d12 > 0.0f) { + cross_v3_v3v3(n, v12, v10); + normalize_v3(n); + cross_v3_v3v3(v, n, u); + + /* v0 in local coordinates */ + const float v0_[2] = {dot_v3v3(v10, u), fabsf(dot_v3v3(v10, v))}; + + /* Compute virtual source point in local coordinates, that we estimate the geodesic + * distance is being computed from. See figure 9 in the paper for the derivation. */ + const float a = 0.5f * (1.0f + (dist1 * dist1 - dist2 * dist2) / (d12 * d12)); + const float hh = dist1 * dist1 - a * a * d12 * d12; + + if (hh > 0.0f) { + const float h = sqrtf(hh); + const float S_[2] = {a * d12, -h}; + + /* Only valid if the line between the source point and v0 crosses + * the edge between v1 and v2. */ + const float x_intercept = S_[0] + h * (v0_[0] - S_[0]) / (v0_[1] + h); + if (x_intercept >= 0.0f && x_intercept <= d12) { + return len_v2v2(S_, v0_); + } + } + } + } + + /* Fall back to Dijsktra approximaton in trivial case, or if no valid source + * point found that connects to v0 across the triangle. */ + return min_ff(dist1 + len_v3(v10), dist2 + len_v3v3(v0, v2)); +} |