13 ms·
Fibonacci Sphere
- inasio 5y agoI ran into this problem working on differential equations that model pattern formation (reaction-diffusion equations, originally postulated by Turing in the 1950s). The equations are highly nonlinear, but some solutions can be found when solving the problem on a sphere. You get spot solutions that dynamically move essentially to the minimum energy configuration (Fekete points I believe are called). BTW, Neil Sloane, of OEIS fame, has a list of the best packings, up to n=100 I believe [0]. Things get interesting when you also allow the sphere to grow, the spots start to split (and sometimes annihilate), understanding how the spots move on the sphere is itself a very interesting problem. [0] http://neilsloane.com/packings/ http://neilsloane.com/packings/
- zarang 5y agoYes, He is legendary which is why i reference this page despite it being rarely updated.
- 10000truths 5y agoOne 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 agothis is a really cool idea! Do you have any links to posts/videos that further describe, analyse, etc this trick?
- bruce343434 5y agoWhat 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 agoHere'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 agoAh, I see now. Encoding still seems expensive though. O(n)
- alanbernstein 5y agoI 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 agoThe 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 agoAhh, I get it, neat.
- extremelearning 5y agoOne 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 agoI 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.
- extremelearning 5y agoAuthor here. Happy to try to answer any questions! ;)
- avmich 5y agoThis link - http://neilsloane.com/packings/index.html#I http://neilsloane.com/packings/index.html#I - has dead URLs. Like this - http://www.teleport.com/~tpgettys/dodeca.gif http://www.teleport.com/~tpgettys/dodeca.gif . I specifically wanted to check where the dodecahedron comes short. Good article, but it'll take some time to understand it. %1 is interesting, I used to use {..} for taking fractional part, %1 is intuitively easy, though not looking particularly good...
- zarang 5y agoyeah. I think his website is extremely old and hasn’t been updated in the last decade or so. Despite this I linked to it because he is a legend in this field and so i think this is still the definitive reference. As far as i understand, part of the story as to why dodecahedron and the cube fall short is due their non-triangular faces.
- fiddlerwoaroof 5y agoDid the article switch the dodecahedron and icosahedron? It specified that the icosahedron is optimal for 12 points and the dodecahedron for 20 which seems backwards to me.
- extremelearning 5y agoI believe it is right. However, I often get these two intuitively mixed up because: Icosahedron: 12 points, 20 faces (and 30 edges) Dodecahedron: 20 points, 12 faces (and 30 edges)
- fiddlerwoaroof 5y agoHmm, that explains it.
- Datagenerator 5y agoHas ε = 0.36 been named as constant or relations with other optimal packing algorithms? It's approximately 1/4 Phi?
- zarang 5y agoNot that I know of…
- deleted 5y ago[deleted]
- rustybolt 5y agoQuite cool how the author picks a topic, explains it well, and on top of that presents some novel results. He did this before with his article on minimum-discrepancy sequences, which is one of my favourite results in math.
- extremelearning 5y agothank you for these kind words. ;)
- jmiskovic 5y agoIn past weeks I've done some work on procedural meshes and filling out the space with various layout strategies. The posted article was a good introduction, and then I found this very approachable paper with great overview of different algorithms: "Point Picking and Distributing on the Disc and Sphere". https://apps.dtic.mil/dtic/tr/fulltext/u2/a626479.pdf https://apps.dtic.mil/dtic/tr/fulltext/u2/a626479.pdf