2D Hilbert curves in O(1)

...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 […]

3D Hilbert curves in even fewer instructions

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: […]

3D Hilbert curves in O(log(n)) optimized

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). […]

Proof of concept: 3D Hilbert curves in O(log(n))

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 […]

LUT-based 3D Hilbert curves

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 […]

Sponza in a Millisecond

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 […]

Hilbert curves in O(log(n)) time

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 […]

The Near Plane Is A Lie

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 […]

Dithering in Gamma vs. Linear Space

Here is some public domain image, originally created by Ricardo Cancho Niemietz. Conversion to R4G4B4A4, without application of dithering, yields a rather unsightly result. Note the significant color banding on the gradients, which results in the Mach band optical illusion. There is some heavy color banding of the parrot's plumage as well. Dithering improves the […]

Fast and Accurate Color Depth Conversion

When converting between low-bit color color formats (R4G4B4A4, R5G6B6, R8G8B8A8, and so on), the conversion routines used often don't map to the nearest color channel values in the target bit depth. For example, when converting 8bit to 4bit colors, this is typically done by simply the discarding the lower 4 bits of each channel. This […]