3 ms·

One neat trick I’ve learned is that you can use the points on a Fibonacci sphere to optimally compress unit vectors, for things like normal textures. For exampl

One neat trick I’ve learned is that you can use the points on a Fibonacci sphere to optimally compress unit vectors, for things like normal textures. For example, if you have an array of 1024 points representing a Fibonacci sphere, you can compress unit vectors into lg(1024)=10 bits with a nearest neighbor search and decompress with an O(1) table lookup. In fact, the general strategy works for higher dimensions as well. Spread some points on the hypersurface of a unit 3-sphere with some kind of energy minimalization simulation, and the resulting array of 4D unit vectors can can be used to compress quaternions!

zarang 5y ago
this is a really cool idea! Do you have any links to posts/videos that further describe, analyse, etc this trick?
bruce343434 5y ago
What you're saying sounds promising but I have no idea how to implement it - any articles about it that contain algorithms?
- deleted 5y ago
  [deleted]
- 10000truths 5y ago
  Here's some Python pseudocode to get you started: import math def fibonacci_sphere_point(idx, num_points): i = idx + 0.5 phi = math.acos(1 - 2 * i / num_points) golden_ratio = (1 + 5 ** 0.5) / 2 theta = 2 * math.pi * i / golden_ratio sin_phi = math.sin(phi) cos_phi = math.cos(phi) sin_theta = math.sin(theta) cos_theta = math.cos(theta) return ( cos_theta * sin_phi, sin_theta * sin_phi, cos_phi, ) table = [fibonacci_sphere_point(i, 1024) for i in range(1024)] def sqr_dist(a, b): return (a[0]-b[0])**2 + (a[1]-b[1])**2 + (a[2]-b[2])**2 def decode(value): return table[value] def encode(point): closest_idx = 0 closest_dist2 = sqr_dist(point, table[closest_idx]) for i in range(1, len(table)): curr_dist2 = sqr_dist(point, table[i]) if closest_dist2 > curr_dist2: closest_dist2 = curr_dist2 closest_idx = i return closest_idx
  - bruce343434 5y ago
    Ah, I see now. Encoding still seems expensive though. O(n)
alanbernstein 5y ago
I would expect the energy minimization approach to perform better than anything else, for vectors distributed uniformly on the surface of the N-sphere. Why go with the Fibonacci sphere instead?
- 10000truths 5y ago
  The Fibonacci sphere arrangement has the advantage that the point coordinates can be computed from a function, so you don't even need a lookup table to decode: def fibonacci_sphere_point(idx, num_points): i = idx + 0.5 phi = math.acos(1 - 2 * i / num_points) golden_ratio = (1 + 5 ** 0.5) / 2 theta = 2 * math.pi * i / golden_ratio sin_phi = math.sin(phi) cos_phi = math.cos(phi) sin_theta = math.sin(theta) cos_theta = math.cos(theta) return ( cos_theta * sin_phi, sin_theta * sin_phi, cos_phi, ) If you're willing to forgo using a spatial acceleration structure and instead do an O(n) scan for encoding, then you can get O(1) space complexity.
  - alanbernstein 5y ago
    Ahh, I get it, neat.
- extremelearning 5y ago
  One reason/situation where the Fibonacci method is preferred is because it is a direct construction method, which can be coded in a few lines, rather than an indirect iterative method. The second is that because an energy minmization method is minimizing the sum of forces, it more closely minimizes average distance between points, rather than absolute minimum distance which is what packing distance focuses on. As I describe in the article, different methods produce similar but slightly different solutions. An optimal solution for one objective function, may not be the optimal for a different objective function. I then give details about how the solution that optimizes volume of the convex hull is different to the solution that optimizes for packing distance, etc.
  - phkahler 5y ago
phkahler 5y ago
I used a similar method of quantizing normal vectors, but I settled for 240 of them, so one byte per normal. It was based on IIRC using a dodecahedron, split faces into triangles, then split those each into 4. Then use the face normals. I dont recall it being as complicated as it sounds, but it does work rather nicely. I could precompute view dependent shading for each normal once per frame and then use the normal index as a color index instead. CPU implementation.

zarang 5y ago

this is a really cool idea! Do you have any links to posts/videos that further describe, analyse, etc this trick?

bruce343434 5y ago

What you're saying sounds promising but I have no idea how to implement it - any articles about it that contain algorithms?

deleted 5y ago
[deleted]
10000truths 5y ago
Here's some Python pseudocode to get you started: import math def fibonacci_sphere_point(idx, num_points): i = idx + 0.5 phi = math.acos(1 - 2 * i / num_points) golden_ratio = (1 + 5 ** 0.5) / 2 theta = 2 * math.pi * i / golden_ratio sin_phi = math.sin(phi) cos_phi = math.cos(phi) sin_theta = math.sin(theta) cos_theta = math.cos(theta) return ( cos_theta * sin_phi, sin_theta * sin_phi, cos_phi, ) table = [fibonacci_sphere_point(i, 1024) for i in range(1024)] def sqr_dist(a, b): return (a[0]-b[0])**2 + (a[1]-b[1])**2 + (a[2]-b[2])**2 def decode(value): return table[value] def encode(point): closest_idx = 0 closest_dist2 = sqr_dist(point, table[closest_idx]) for i in range(1, len(table)): curr_dist2 = sqr_dist(point, table[i]) if closest_dist2 > curr_dist2: closest_dist2 = curr_dist2 closest_idx = i return closest_idx
- bruce343434 5y ago
  Ah, I see now. Encoding still seems expensive though. O(n)

alanbernstein 5y ago

I would expect the energy minimization approach to perform better than anything else, for vectors distributed uniformly on the surface of the N-sphere. Why go with the Fibonacci sphere instead?

10000truths 5y ago
The Fibonacci sphere arrangement has the advantage that the point coordinates can be computed from a function, so you don't even need a lookup table to decode: def fibonacci_sphere_point(idx, num_points): i = idx + 0.5 phi = math.acos(1 - 2 * i / num_points) golden_ratio = (1 + 5 ** 0.5) / 2 theta = 2 * math.pi * i / golden_ratio sin_phi = math.sin(phi) cos_phi = math.cos(phi) sin_theta = math.sin(theta) cos_theta = math.cos(theta) return ( cos_theta * sin_phi, sin_theta * sin_phi, cos_phi, ) If you're willing to forgo using a spatial acceleration structure and instead do an O(n) scan for encoding, then you can get O(1) space complexity.
- alanbernstein 5y ago
  Ahh, I get it, neat.
extremelearning 5y ago
One reason/situation where the Fibonacci method is preferred is because it is a direct construction method, which can be coded in a few lines, rather than an indirect iterative method. The second is that because an energy minmization method is minimizing the sum of forces, it more closely minimizes average distance between points, rather than absolute minimum distance which is what packing distance focuses on. As I describe in the article, different methods produce similar but slightly different solutions. An optimal solution for one objective function, may not be the optimal for a different objective function. I then give details about how the solution that optimizes volume of the convex hull is different to the solution that optimizes for packing distance, etc.
- phkahler 5y ago

phkahler 5y ago

I used a similar method of quantizing normal vectors, but I settled for 240 of them, so one byte per normal. It was based on IIRC using a dodecahedron, split faces into triangles, then split those each into 4. Then use the face normals. I dont recall it being as complicated as it sounds, but it does work rather nicely. I could precompute view dependent shading for each normal once per frame and then use the normal index as a color index instead. CPU implementation.