Fast, Constant Time Sphere Indexing, Part 2
To start, let's take the final solution from Part 1. The goal is to reduce this even further so that the technique can be used frequently in shaders.
Don Williamson, Consultant Game Technology Programmer/Director of Celtoys
To start, let's take the final solution from Part 1. The goal is to reduce this even further so that the technique can be used frequently in shaders.
The problem statement is: Assuming a triangle-subdivided sphere, map any 3D point on or above it to a triangle index in constant-time, without using recursion, table lookups or complicated branching logic. Even better; make it so simple you can use it in a pixel shader. This is useful for when your playing field is on/above a sphere and you have some lookup tables you want to reference based on player/camera position.
Around the age of 15 I started to code after a family friend gave me a BBC Microcomputer Model B that his local army barracks were throwing away. Though primitive, it was a wonderful machine that showed me where my future lay. I learned BBC BASIC and a smattering of 6502 Assembly to gain performance and then moved on to PC. I bought a second-hand 286 PC for something like £20 and migrated to QBasic and x86 Assembly using Gavin Estey's tutorials.
I've been considering removing comments from this blog for a while; mainly because the site doesn't trigger much discussion and I didn't like keeping the overhead of Disqus around. After looking into Disqus load-time behaviour I was pretty shocked what I was forcing on people loading the site (although you really should be using the likes of Privacy Badger and uBlock Origin).
Getting frustum points in world-space can be useful in a number of scenarios, such as debug visualisation or building a coarse volume around a partition in your frustum. Each method can be used depending what information you have available to you and what you want to avoid recalculating.
When you develop a solver for the Tammes problem you're usually concerned with distributing points evenly on the sphere, ensuring they are equidistant from each other. The radius of the circles you place at those points is generally not considered:
I posted an article a while back, entitled Very Fast, High-Precision SIMD/GPU Gradient Noise, where I outlined a technique for achieving double-resolution noise at speeds close to that when using float arithmetic. The key observation was that floor
could be used on cell boundaries to mask off the ranges that require double arithmetic, allowing the bulk of the work to use float arithmetic.
And we are back! It must be a year now since my old site donw.org went dark for many reasons, including being busy working on my own game. There's some big changes with this new setup: I own the domain donw.io this time round. I've gone through a bunch of domains -- donw.org, donw.co.uk, etc. -- that I used to pay somebody else to manage for me. That was obviously not the right way of going about this as I no longer own them.
This is a small test post exercising math notation with MathJax in Hugo.
A recently published article by Inigo Quilez on Voronoi Edges highlights the technique of shifting the co-ordinate frame of procedural algorithms to improve precision. This is a really important little trick that I felt was worth reviewing, as it provides huge benefits to world generation at a planetary scale.