diff options
author | Campbell Barton <campbell@blender.org> | 2022-07-27 12:48:17 +0300 |
---|---|---|
committer | Campbell Barton <campbell@blender.org> | 2022-07-28 02:34:46 +0300 |
commit | 397731d4df44197cf9cf359d9da38156ad86904e (patch) | |
tree | 8d987715ed414dbfa2c4c8b1b6880328380647ee /source/blender | |
parent | 38af5b0501005d8ee84a59f027417bf6a31fcc5e (diff) |
BLI_math: improve symmetrical values from sin_cos_from_fraction
When plotting equally distant points around a circle support an extra
axis of symmetry so twice as many exact values are repeated than
originally added in [0], see code-comments for a detailed explanation.
Tests to ensure accuracy and exact symmetry have been added too.
Follow up on fix for T87779.
[0]: 087f27a52f7857887e90754d87a7a73715ebc3fb
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/BLI_math_rotation.h | 9 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_rotation.c | 106 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_math_rotation_test.cc | 103 |
3 files changed, 187 insertions, 31 deletions
diff --git a/source/blender/blenlib/BLI_math_rotation.h b/source/blender/blenlib/BLI_math_rotation.h index fef51fa780e..3987c9daf0a 100644 --- a/source/blender/blenlib/BLI_math_rotation.h +++ b/source/blender/blenlib/BLI_math_rotation.h @@ -177,10 +177,9 @@ void mat3_to_quat_is_ok(float q[4], const float mat[3][3]); /* Other. */ /** - * Utility function that performs `sinf` & `cosf` where the quadrants of the circle - * will have exactly matching values when their sign is flipped. - * This works as long as the denominator can be divided by 2 or 4, - * otherwise `sinf` & `cosf` are used without any additional logic. + * Utility that performs `sinf` & `cosf` intended for plotting a 2D circle, + * where the values of the coordinates with are exactly symmetrical although this + * favors even numbers as odd numbers can only be symmetrical on a single axis. * * Besides adjustments to precision, this function is the equivalent of: * \code {.c} @@ -194,7 +193,7 @@ void mat3_to_quat_is_ok(float q[4], const float mat[3][3]); * \param r_sin: The resulting sine. * \param r_cos: The resulting cosine. */ -void sin_cos_from_fraction(const int numerator, const int denominator, float *r_sin, float *r_cos); +void sin_cos_from_fraction(int numerator, int denominator, float *r_sin, float *r_cos); void print_qt(const char *str, const float q[4]); diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c index f0bfc7c21e1..03275ce19b4 100644 --- a/source/blender/blenlib/intern/math_rotation.c +++ b/source/blender/blenlib/intern/math_rotation.c @@ -915,53 +915,107 @@ float tri_to_quat(float q[4], const float a[3], const float b[3], const float c[ return len; } -void sin_cos_from_fraction(const int numerator, const int denominator, float *r_sin, float *r_cos) -{ +void sin_cos_from_fraction(int numerator, const int denominator, float *r_sin, float *r_cos) +{ + /* By default, creating an circle from an integer: calling #sinf & #cosf on the fraction doesn't + * create symmetrical values (because of float imprecision). + * Resolve this when the rotation is calculated from a fraction by mapping the `numerator` + * to lower values so X/Y values for points around a circle are exactly symmetrical, see T87779. + * + * - Numbers divisible by 4 are mapped to the lower 8th (8 axis symmetry). + * - Even numbers are mapped to the lower quarter (4 axis symmetry). + * - Odd numbers are mapped to the lower half (1 axis symmetry). + * + * Once the values are calculated, the are mapped back to their position in the circle + * using negation & swapping values. */ + BLI_assert((numerator <= denominator) && (denominator > 0)); + enum { NEGATE_SIN_BIT = 0, NEGATE_COS_BIT = 1, SWAP_SIN_COS_BIT = 2 }; + enum { + NEGATE_SIN = (1 << NEGATE_SIN_BIT), + NEGATE_COS = (1 << NEGATE_COS_BIT), + SWAP_SIN_COS = (1 << SWAP_SIN_COS_BIT), + } xform = 0; if ((denominator & 3) == 0) { + /* The denominator divides by 4, determine the quadrant then further refine the upper 8th. */ const int denominator_4 = denominator / 4; - if (numerator <= denominator_4) { + if (numerator < denominator_4) { /* Fall through. */ } else { - if (numerator <= denominator_4 * 2) { - const float phi = (float)(2.0 * M_PI) * - ((float)(numerator - denominator_4) / (float)denominator); - *r_sin = cosf(phi); - *r_cos = -sinf(phi); + if (numerator < denominator_4 * 2) { + numerator -= denominator_4; + xform = NEGATE_SIN | SWAP_SIN_COS; + } + else if (numerator == denominator_4 * 2) { + numerator = 0; + xform = NEGATE_COS; + } + else if (numerator < denominator_4 * 3) { + numerator -= denominator_4 * 2; + xform = NEGATE_SIN | NEGATE_COS; } - else if (numerator <= denominator_4 * 3) { - const float phi = (float)(2.0 * M_PI) * - ((float)(numerator - (denominator_4 * 2)) / (float)denominator); - *r_sin = -sinf(phi); - *r_cos = -cosf(phi); + else if (numerator == denominator_4 * 3) { + numerator = 0; + xform = NEGATE_COS | SWAP_SIN_COS; } else { - const float phi = (float)(2.0 * M_PI) * - ((float)(numerator - (denominator_4 * 3)) / (float)denominator); - *r_cos = sinf(phi); - *r_sin = -cosf(phi); + numerator -= denominator_4 * 3; + xform = NEGATE_COS | SWAP_SIN_COS; } - return; + } + /* Further increase accuracy by using the range of the upper 8th. */ + const int numerator_test = denominator_4 - numerator; + if (numerator_test < numerator) { + numerator = numerator_test; + xform ^= SWAP_SIN_COS; + /* Swap #NEGATE_SIN, #NEGATE_COS flags. */ + xform = (xform & (uint)(~(NEGATE_SIN | NEGATE_COS))) | + (((xform & NEGATE_SIN) >> NEGATE_SIN_BIT) << NEGATE_COS_BIT) | + (((xform & NEGATE_COS) >> NEGATE_COS_BIT) << NEGATE_SIN_BIT); } } else if ((denominator & 1) == 0) { + /* The denominator divides by 2, determine the quadrant then further refine the upper 4th. */ const int denominator_2 = denominator / 2; - if (numerator <= denominator_2) { + if (numerator < denominator_2) { /* Fall through. */ } + else if (numerator == denominator_2) { + numerator = 0; + xform = NEGATE_COS; + } else { - const float phi = (float)(2.0 * M_PI) * - ((float)(numerator - denominator_2) / (float)denominator); - *r_sin = -sinf(phi); - *r_cos = -cosf(phi); - return; + numerator -= denominator_2; + xform = NEGATE_SIN | NEGATE_COS; + } + /* Further increase accuracy by using the range of the upper 4th. */ + const int numerator_test = denominator_2 - numerator; + if (numerator_test < numerator) { + numerator = numerator_test; + xform ^= NEGATE_COS; + } + } + else { + /* The denominator is an odd number, only refine the upper half. */ + const int numerator_test = denominator - numerator; + if (numerator_test < numerator) { + numerator = numerator_test; + xform ^= NEGATE_SIN; } } const float phi = (float)(2.0 * M_PI) * ((float)numerator / (float)denominator); - *r_sin = sinf(phi); - *r_cos = cosf(phi); + const float sin_phi = sinf(phi) * ((xform & NEGATE_SIN) ? -1.0f : 1.0f); + const float cos_phi = cosf(phi) * ((xform & NEGATE_COS) ? -1.0f : 1.0f); + if ((xform & SWAP_SIN_COS) == 0) { + *r_sin = sin_phi; + *r_cos = cos_phi; + } + else { + *r_sin = cos_phi; + *r_cos = sin_phi; + } } void print_qt(const char *str, const float q[4]) diff --git a/source/blender/blenlib/tests/BLI_math_rotation_test.cc b/source/blender/blenlib/tests/BLI_math_rotation_test.cc index a283118bea2..460cfd2d36c 100644 --- a/source/blender/blenlib/tests/BLI_math_rotation_test.cc +++ b/source/blender/blenlib/tests/BLI_math_rotation_test.cc @@ -7,6 +7,8 @@ #include "BLI_math_rotation.hh" #include "BLI_math_vector.hh" +#include "BLI_vector.hh" + #include <cmath> /* Test that quaternion converts to itself via matrix. */ @@ -150,6 +152,107 @@ TEST(math_rotation, quat_split_swing_and_twist_negative) EXPECT_V4_NEAR(twist, expected_twist, FLT_EPSILON); } +/* -------------------------------------------------------------------- */ +/** \name Test `sin_cos_from_fraction` Accuracy & Exact Symmetry + * \{ */ + +static void test_sin_cos_from_fraction_accuracy(const int range, const float expected_eps) +{ + for (int i = 0; i < range; i++) { + float sin_cos_fl[2]; + sin_cos_from_fraction(i, range, &sin_cos_fl[0], &sin_cos_fl[1]); + const float phi = (float)(2.0 * M_PI) * ((float)i / (float)range); + const float sin_cos_test_fl[2] = {sinf(phi), cosf(phi)}; + EXPECT_V2_NEAR(sin_cos_fl, sin_cos_test_fl, expected_eps); + } +} + +/** Ensure the result of #sin_cos_from_fraction match #sinf & #cosf. */ +TEST(math_rotation, sin_cos_from_fraction_accuracy) +{ + for (int range = 1; range <= 64; range++) { + test_sin_cos_from_fraction_accuracy(range, 1e-6f); + } +} + +/** Ensure values are exactly symmetrical where possible. */ +static void test_sin_cos_from_fraction_symmetry(const int range) +{ + /* The expected number of unique numbers depends on the range being a multiple of 4/2/1. */ + const enum { + MULTIPLE_OF_1 = 1, + MULTIPLE_OF_2 = 2, + MULTIPLE_OF_4 = 3, + } multiple_of = (range & 1) ? MULTIPLE_OF_1 : ((range & 3) ? MULTIPLE_OF_2 : MULTIPLE_OF_4); + + blender::Vector<blender::float2> coords; + coords.reserve(range); + for (int i = 0; i < range; i++) { + float sin_cos_fl[2]; + sin_cos_from_fraction(i, range, &sin_cos_fl[0], &sin_cos_fl[1]); + switch (multiple_of) { + case MULTIPLE_OF_1: { + sin_cos_fl[0] = fabsf(sin_cos_fl[0]); + break; + } + case MULTIPLE_OF_2: { + sin_cos_fl[0] = fabsf(sin_cos_fl[0]); + sin_cos_fl[1] = fabsf(sin_cos_fl[1]); + break; + } + case MULTIPLE_OF_4: { + sin_cos_fl[0] = fabsf(sin_cos_fl[0]); + sin_cos_fl[1] = fabsf(sin_cos_fl[1]); + if (sin_cos_fl[0] > sin_cos_fl[1]) { + SWAP(float, sin_cos_fl[0], sin_cos_fl[1]); + } + break; + } + } + coords.append_unchecked(sin_cos_fl); + } + /* Sort, then count unique items. */ + std::sort(coords.begin(), coords.end(), [](const blender::float2 &a, const blender::float2 &b) { + float delta = b[0] - a[0]; + if (delta == 0.0f) { + delta = b[1] - a[1]; + } + return delta > 0.0f; + }); + int unique_coords_count = 1; + if (range > 1) { + int i_prev = 0; + for (int i = 1; i < range; i_prev = i++) { + if (coords[i_prev] != coords[i]) { + unique_coords_count += 1; + } + } + } + switch (multiple_of) { + case MULTIPLE_OF_1: { + EXPECT_EQ(unique_coords_count, (range / 2) + 1); + break; + } + case MULTIPLE_OF_2: { + EXPECT_EQ(unique_coords_count, (range / 4) + 1); + break; + } + case MULTIPLE_OF_4: { + EXPECT_EQ(unique_coords_count, (range / 8) + 1); + break; + } + } +} + +TEST(math_rotation, sin_cos_from_fraction_symmetry) +{ + for (int range = 1; range <= 64; range++) { + test_sin_cos_from_fraction_symmetry(range); + } +} + +/** \} */ + namespace blender::math::tests { TEST(math_rotation, RotateDirectionAroundAxis) |