In any dimension, the key for an efficient implementation of a coordinate <=> Hilbert curve index mapping is finding a sequence of machine instructions that computes the subcube transformation group of that curve. In particular, if the transformation group multiplication can be represented as a logic circuit, the coordinate <=> Hilbert mapping algorithm can be […]
I'm happy to announce that my software rasterizer side project has been picked up by a major commercial VR product a while ago. While I can't go into too much detail, adding in the rasterizer gave an average frame time saving of 1ms on the CPU and GPU each, which was critical to shipping the […]
...sort of. The core of computing 2D coordinates from a Hilbert index in logarithmic time is a XOR prefix sum. As it so happens, the upper bits of carry-less multiplication with -1 are equivalent to a XOR prefix sum. On an x86 machine with CLMUL and PEXT support, this yields the following "constant time" algorithm […]
So far, the LUT based algorithm is the fastest method in general for mapping between Morton and Hilbert orders in 3D. This method performs linearly in the input size, consuming 3 bits of input and producing 3 bits of output per iteration. Let's break it down into 5 logical steps: Extract 3 bits from input: […]
Finally I've managed to implement an optimized version of the 3D Hilbert Index -> XYZ transform in logarithmic time. The crucial element was finding an efficient bitwise representation of the alternating group A4. In the end I decided for a rather direct representation as a subgroup of S4, describing each permutation as a 4-tuple (a,b,c,d). […]
Back in my earlier post about 2D Hilbert curves in logarithmic time, I hinted that it would be possible but likely not efficient to extend the same approach to higher dimensions. Just as a proof of concept, I've done just that for the Hilbert Index -> XYZ mapping in 3D. Most of the actual code […]
As referenced in my earlier post about Hilbert curves, it's possible to map between -dimensional Euclidean coordinates and the offset along the Hilbert curve in time by direct application of the transformation group at each recursion level of the curve. The following applies this to the 3D case: The 3D Hilbert curve transforms under the […]
Today, after nearly three years of research and more than a dozen rewrites, I finally present a little side project of mine: https://github.com/rawrunprotected/rasterizer This is state-of-the-art software occlusion culling system; similar to Intel's Software Occlusion Culling, but better optimized. By default, the application loads and renders Crytek's Sponza mesh. Camera controls are simple WASD to […]
Jump to the code Today I present a novel technique for mapping a point in the -dimensional plane to its corresponding -bit offset on the th order Hilbert curve with a running time of on a processor with -bit words. While a large constant factor makes it infeasible in higher dimensions, it is significantly faster […]
In rasterization, the near plane is a weird beast. The reason for its existence is far from intuitive - after all, ray tracing does fine without it. Why does rasterization specifically have to deal with this, and the associated the trade-off between depth precision and clipping artifacts for geometry near the camera? One reason that […]