Rational rendering and floating bar
iquilezles.org
iquilezles.org
Quilez's concern with how the number fits into 32 or 64 bits may be necessary for performance, but using arbitrary precision numerators and denominators is the only way to achieve the robustness he was initially pursuing.
Both methods result in "holes" bellow zero (necessarily of course), but they do not fit inside each other. However within a limited set of operations, rational numbers (within a capable format, and with necessary operators) have some interesting properties over floating point math that makes them desirable, i.e not loosing precision (unless overflow due to encountering large primes), and they are less expensive (built on integer math).
What he did do, is make a rational number bit format (floating bar) which stores everything as fractions, it's quite elegant really and anyone familiar with IEEE754 will see the similarities.
Yes good point, I did wonder this... it's easy to look at the individual operations and think "that's cheap" but holistically, the GCD which I assume is expensive could make the overall performance benefits moot. It might be optimisable to not do it unnecessarily after _every_ operation though?
Perhaps then the only advantage in terms of hardware use is that it can be implemented on a CPU with only ints e.g small micro-controllers with no FPU or int divide. I think that by comparison implementing a soft FPU would be impractical, still niche I guess.
Is that because you can express a rotation (etc) as a matrix? If so, don't you need to be able to do the trigonometry exactly to create a correct rational matrix in the first place? What am i missing?
Or is it that you just don't need to do those sorts of operations at all inside the renderer?
As far as construction of rotation matrices goes, most of that will be baked before rendering a frame, so expensive trigonometric calculations and their conversion to rationals will occur ahead of time and therefore much less frequently than anything done per pixel, improving performance.
In computer graphics, because a great many calculations need to be done for each pixel to be displayed, use of expensive functions tends to be avoided. In the literature I recall reading a number of triangle-ray intersection algorithms where each breaks down precisely how many adds, multiplies, divisions, etc are performed because the goal is to minimize all these things. If you are intersecting 10 triangles per pixel at 2 million pixels per frame, a single multiply per intersection becomes 20 million multiplies per frame. By contrast, recalculating the camera matrix using expensive functions should only happen once per frame.
It is usually (but not always) possible to reframe problems in such a way that exponentials (including sine/cosine/tangent) and logarithms (including arcsine, arctangent, ..) are unnecessary.
Vector methods are much faster, have fewer weird edge cases, are less subject to rounding error, etc.
As an example: if you want to store a planar vector, use a pair of coordinates instead of an angle measure and magnitude. If you want to store an 2d orientation or rotation, still use a pair of (x, y) coordinates on the unit circle instead of angle measure (which is a logarithmic quantity). If you want to reduce your pair of coordinates to a single number, use the stereographic projection, which only requires division.
exp(ρ + θi) = (cosh ρ + sinh ρ)(cos θ + i sin θ)
The angle measure in the above is the θ part. The “linear space” expression of the orientation/rotation is a 2-dimensional quanitity cos θ + i sin θ.
Or if you start with the 2-coordinate version x + iy, where x^2 + y^2 = 1, you can find the angle measure by taking the natural logarithm, imag(log(x + yi)).
Rotations are naturally a multiplicative concept. If you have a rotation a + bi and a rotation c + di, then you can compose them like (a + bi)(c + di) = (ac - bd) + (ad + bc)i (you might recognize this as the the “angle sum” identities from high school trigonometry class).
The idea of the logarithm is that you can convert a multiplicative structure into an additive one. So if you have rotations Q and R, you could normally compose them like QR, but as an alternative you can use a log-space representation (angle measure): QR = exp(log(Q) + log(R)).
A rotation inherently comes with an orientation. The i (“imaginary unit”) is in my opinion properly thought of as a bivector, oriented like a plane. When we express something as a scalar-valued angle measure, we have stripped the orientation out.
I love the revelation that log/exp shifts between Cartesian and (log-)polar meanings of complex numbers. That's enormously satisfying for some reason.
I note that the pattern in multiplying rotations also comes up if you do it with matrices:
a -b c -d ac-bd -(ad+bc)
b a . d c = ad+bc ac-bd
The log space version is still useful though if you want to e.g. take the nth root of a spatial rotation.