Given the (x, y) coordinates of a point on the order n Hilbert curve, how can one find the coordinates of the next point? One way is to convert (x, y) to s, add 1 to s, and then convert the new value of s back to (x, y), using algorithms given above.

A slightly (but not dramatically) better way is based on the fact that as one moves along the Hilbert curve, at each step either x or y, but not both, is either incremented or decremented (by 1). The algorithm to be described scans the coordinate numbers from left to right to determine the type of U-curve that the rightmost two bits are on. Then, based on the U-curve and the value of the rightmost two bits, it increments or decrements either x or y.

That's basically it, but there is a complication when the path is at the end of a U-curve (which happens once every four steps). At this point, the direction to take is determined by the previous bits of x and y and by the higher order U-curve with which these bits are associated. If that point is also at the end of its U-curve, then the previous bits and the U-curve there determine the direction to take, and so on.

Table 14-7 describes this algorithm. In this table, the A, B, C, and D denote the U-curves as shown in Table 14-1 on page 246. To use the table, first pad x and y with leading zeros so they are n bits long, where n is the order of the Hilbert curve. Start in state A and scan the bits of x and y from left to right. The first row of Table 14-7 means that if the current state is A and the currently scanned bits are (0, 0), then set a variable to indicate to increment y, and enter state B. The other rows are interpreted similarly, with a suffix minus sign indicating to decrement the associated coordinate. A dash in the third column means do not alter the variable that keeps track of the coordinate changes.

After scanning the last (rightmost) bits of x and y, increment or decrement the appropriate coordinate as indicated by the final value of the variable.

A C program implementing these steps is shown in Figure 14-11. Variable `dx` is initialized in such a way that if
invoked many times, the algorithm cycles around, generating the same Hilbert
curve over and over again. (However, the step that connects one cycle to the
next is not a unit step.)

void hil_inc_xy(unsigned *xp, unsigned *yp, int n) {

牋 int i;

牋爑nsigned x, y, state, dx, dy, row, dochange;

牋 x = *xp;

牋爕 = *yp;

牋爏tate = 0;牋牋牋牋牋牋牋牋牋 // Initialize.

牋燿x = -((1 << n) - 1);牋牋牋?// Init. -(2**n - 1).

牋燿y = 0;

牋 for (i = n-1; i >= 0; i--) {牋牋牋牋 // Do n times.

牋牋牋row = 4*state | 2*((x >> i) & 1) | (y >> i) & 1;

牋牋牋dochange = (0xBDDB >> row) & 1;

牋牋牋if (dochange) {

牋牋牋牋 dx = ((0x16451659 >> 2*row) & 3) - 1;

牋牋牋牋燿y = ((0x51166516 >> 2*row) & 3) - 1;

牋牋牋}

牋牋牋state = (0x8FE65831 >> 2*row) & 3;

牋爙

牋?xp = *xp + dx;

牋?yp = *yp + dy;

}

Table 14-7 can readily be implemented in logic, as shown in Figure 14-12. In this figure, the variables have the following meanings:

x |
Bit i of input x. |

y |
Bit i of input y. |

X, Y: |
x |

I: |
If 1, increment; if 0, decrement (by 1). |

W: |
If 1, increment or decrement x; if 0, increment or decrement y. |

S: |
If 1, swap x |

C: |
If 1, complement x |

S and C together identify the
"state" of Table 14-7, with (C, S) = (0, 0), (0,
1), (1, 0), and (1, 1) denoting states A, B, C, and D, respectively. The output
signals are I_{0} and W_{0}, which tell, respectively, whether to
increment or decrement, and which variable to change. (In addition to the logic
shown, an incrementer/decrementer circuit is required, with MUX's to route
either x or y
to the incrementer/ decrementer, and a circuit to route the altered value back
to the register that holds x or y. Alternatively, two incrementer/decrementer
circuits could be used.)