the opposite order, starting with the least significant bits of d, and building up x and y starting with the least significant bits. Both functions use the rotation function to rotate and flip the (x,y) coordinate system appropriately. The two mapping algorithms work in similar ways. The entire square is viewed as composed of 4 regions, arranged 2 by 2. Each region is composed of 4 smaller regions, and so on, for a number of levels. At level s, each region is s by s cells. There is a single FOR loop that iterates through levels. On each iteration, an amount is added to d or to x and y, determined by which of the 4 regions it is in at the current level. The current region out of the 4 is (rx,ry), where rx and ry are each 0 or 1. So it consumes 2 input bits, (either 2 from d or 1 each from x and y), and generates two output bits. It also calls the rotation function so that (x,y) will be appropriate for the next level, on the next iteration. For xy2d, it starts at the top level of the entire square, and works its way down to the lowest level of individual cells. For d2xy, it starts at the bottom with cells, and works up to include the entire square. It is possible to implement Hilbert curves efficiently even when the data space does not form a square. Moreover, there are several possible generalizations of Hilbert curves to higher dimensions. Representation as Lindenmayer system The Hilbert Curve can be expressed by a rewrite system (L-system). Alphabet : A, B Constants : F + − Axiom : A Production rules: A → +BF−AFA−FB+ B → −AF+BFB+FA− Here, "F" means "draw forward", "+" means "turn left 90°", "-" means "turn right 90°" (see turtle graphics), and "A" and "B" are ignored during drawing. Other implementations Graphics Gems II discusses Hilbert curve coherency, and provides implementation. The Hilbert Curve is commonly used among rendering images or videos. Common programs such as Blender and Cinema 4D use the Hilbert Curve to trace the objects, and render the scene. See also Hilbert curve scheduling Hilbert R-tree Locality of reference Locality-sensitive hashing Moore curve Murray polygon Sierpiński curve List of fractals by Hausdorff dimension Notes Further reading External links Dynamic Hilbert curve with JSXGraph Three.js WebGL 3D Hilbert curve demo XKCD