blender
/
blender
136
406
Fork 588
Code Issues 6.2k Pull Requests 754 Projects 19 Wiki Activity

Cleanup: simplify sin_cos_from_fraction 

Multiply numerator and denominator by 8 to split circle into octants.
Use symmetry and negation to increase precision.
This commit is contained in:
Chris Blackbourn 2022-08-15 15:39:07 +12:00
parent 4a11c0aabb
commit 77c867a5ee
Notes: blender-bot 2024-04-26 15:51:50 +02:00 
Referenced by issue #121129, Regression: Crash on `bmesh.ops.create_uvsphere` if underspecified
1 changed files with 49 additions and 93 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

142
source/blender/blenlib/intern/math_rotation.c
View File

@ -915,107 +915,63 @@ 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(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)
{
/* By default, creating an circle from an integer: calling #sinf & #cosf on the fraction doesn't
* create symmetrical values (because of float imprecision).
/* By default, creating a circle from an integer: calling #sinf & #cosf on the fraction doesn't
* create symmetrical values (because floats can't represent Pi exactly).
* 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).
* Multiply both the `numerator` and `denominator` by eight to ensure we can divide the circle
* into 8 octants. For each octant, we then use symmetry and negation to bring the `numerator`
* closer to the origin where precision is highest.
*
* Once the values are calculated, the are mapped back to their position in the circle
* using negation & swapping values. */
* Cases 2, 4, 5 and 7, use the trigonometric identity sin(-x) == -sin(x).
* Cases 1, 2, 5 and 6, swap the pointers `r_sin` and `r_cos`.
*/
BLI_assert(0 <= numerator);
BLI_assert(numerator <= denominator);
BLI_assert(denominator > 0);
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) {
/* Fall through. */
}
else {
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) {
numerator = 0;
xform = NEGATE_COS | SWAP_SIN_COS;
}
else {
numerator -= denominator_4 * 3;
xform = NEGATE_COS | SWAP_SIN_COS;
}
}
/* 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) {
/* Fall through. */
}
else if (numerator == denominator_2) {
numerator = 0;
xform = NEGATE_COS;
}
else {
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;
}
numerator *= 8; /* Multiply numerator the same as denominator. */
const int octant = numerator / denominator; /* Determine the octant. */
denominator *= 8; /* Ensure denominator is a multiple of eight. */
float cos_sign = 1.0f; /* Either 1.0f or -1.0f. */
switch (octant) {
case 0:
/* Primary octant, nothing to do. */
break;
case 1:
case 2:
numerator = (denominator / 4) - numerator;
SWAP(float *, r_sin, r_cos);
break;
case 3:
case 4:
numerator = (denominator / 2) - numerator;
cos_sign = -1.0f;
break;
case 5:
case 6:
numerator = numerator - (denominator * 3 / 4);
SWAP(float *, r_sin, r_cos);
cos_sign = -1.0f;
break;
case 7:
numerator = numerator - denominator;
break;
default:
BLI_assert_unreachable();
}
const float phi = (float)(2.0 * M_PI) * ((float)numerator / (float)denominator);
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;
}
BLI_assert(-denominator / 4 <= numerator); /* Numerator may be negative. */
BLI_assert(numerator <= denominator / 4);
BLI_assert(cos_sign == -1.0f || cos_sign == 1.0f);
const float angle = (float)(2.0 * M_PI) * ((float)numerator / (float)denominator);
*r_sin = sinf(angle);
*r_cos = cosf(angle) * cos_sign;
}
void print_qt(const char *str, const float q[4])