Grid math

Introduction

This page contains some mathematical expressions I worked out while figuring out how to render grids.

By a grid, I just mean a bunch horizontal and vertical lines, each laid out in patterns a bit like you'd find on a ruler. On a ruler, the smallest marks are generally millimeters (10-3 meters). The next smallest marks are centimeters (10-2 meters), and so on. You can think of these as a bunch of lines spaced out one millimeter apart, but with a certain pattern giving their size or opacity in our case. I will define this pattern below.

Unlike on a ruler, the grid should get infinitely finer as you zoom. I'll focus on the horizontal line pattern and ignore the vertical lines, since their equations are similar. We don't want to draw infinitely many levels, so we'll draw only the "$N$ highest visible levels", which will be defined more precisely below.

On a ruler, the higher the power of 10 that a line's index is divisible by, the bigger the line is. There is nothing special about 10, of course, and so we will use $b$ to denote the base of the grid. It turns out to be convenient to express the camera zoom as a power of $b$: $z = b^m$. ($m$ is for magnification, if you will.) The camera's position is denoted by $x$.

We assume that the width of the screen is 1 in camera-space. The goal is to draw the grid efficiently at any camera zoom and for any camera position, without precision issues.

The grid pattern

The pattern on a regular ruler is: $$ p(i) = \max_{0 \leq k < N} \left\{ k : b^k \vert i \right\} $$ where $i$ is the "index" of the line. Clearly $p(0) = N-1$, and $i=b^{N-1}$ must be the next index such that $p(i) = N-1$. This pattern is, in fact, periodic with period $b^{N-1}$, since if $qb^k = i$ for some integer $q$, then $b^k(q + b^{N-1-k}) = i + b^{N-1}$ which proves that $p(i) <= p(i+b^{N-1})$, and similarly if $q b^{k} = i + b^{N-1}$ then $b^{k}(q - b^{N-1-k}) = i$ which means that $p(i) >= p(i+b^{N-1})$. We conclude $p(i) = p(i + b^{N-1})$, so that $p$ is periodic with period $b^{N-1}$. This pattern is used to give alpha values determining how transparent the line should be, for example $\alpha(i) = (p(i)+1)/N$.

Grid spacing

Thenote the distance between grid-lines at level $i$ of the grid by $$ d(i) = \frac{ b^i }{w} $$ where $w > 0$ is just the width of the screen in pixels, so that $d(0) = 1/w$ is the width of a pixel.

Which levels are visible?

Which levels of the grid should we bother concidering when we render? We define the highest visible level, $i_H$, as the smallest integer such that $$ d(i_H) >= \frac{1}{z} $$ Since d is continuous and increases monotonically, this can be done by first solving $$ d(x) = \frac{1}{z} $$ for $x$ and then taking the ceiling on the result: $$ \frac{ b^x }{w} = b^{-m} $$ $$ -\ln(w) + x \ln(b) = -m \ln(b) $$ $$ x = \frac{\ln(w)}{\ln(b)} -m $$ and so $$ i_H = \left\lceil {\frac{\ln(w)}{\ln(b)} - m} \right\rceil $$ The lowest visible level is therefore $$ i_L = i_H - N + 1 $$

Spacing between lines in camera coordinates

The spacing, $s$, between lines in camera space is $$ s = z d(i_L) = \frac{ b^{ m + \left\lceil {\frac{\ln(w)}{\ln(b)} - m} \right\rceil - N + 1 } }{w} = b^{ m - \frac{\ln(w)}{\ln(b)} + \left\lceil {\frac{\ln(w)}{\ln(b)} - m} \right\rceil - N + 1 } $$ Using $\left\lceil x \right\rceil = -\left\lfloor -x \right\rfloor$ as well as $x - \lfloor x \rfloor = \left\{x\right\}$ (known as "the fractional part of $x$"), this becomes $$ s = b^{ \left\{ m - \frac{\ln(w)}{\ln(b)} \right\} - N + 1 } $$

Number of lines visible

The number of visible lines, $n$, is simply $$ n = \left\lfloor { \frac{1}{s} } \right\rfloor + 1 = \left\lfloor b^{ N-1 - \left\{ m - \frac{\ln(w)}{\ln(b)} \right\} } \right\rfloor + 1$$

Grid pattern length

As we figured out above, the grid pattern at a given zoom level repeats with period $b^{N-1}$. Using the camera-space spacing of the lowest level of the grid, we can find out the camera-space distance, $L$ at which the grid repeats $$ L = s b^{N-1} = b^{ \left\{ m - \frac{\ln(w)}{\ln(b)} \right\} } $$

Index of the leftmost visible gridline

In order to color a grid-line, we need to know it's pattern index, modulo the pattern length of $b^{N-1}$. This number can be expressed as the smallest integer $k$ such that $k \frac{s}{z} \geq x - \frac{1}{2z}$. To find this, we solve the following equation for $\kappa$: $$ \kappa = \frac{xz}{s} - \frac{1}{2s} $$ The actual index, $k$ would be obtained if we were to take the ceiling of this number.

Note, however, that the first term can be enormous, while the second term will typically be less than, say, 50, in our use-case of interest (recall that $s$ is the distance between the grid lines on screen). We are therefore now in danger of running into precision problems. Since the pattern repeats with a period of $b^{N-1}$, we'll do equally well with the potentially much smaller number $\kappa \mod b^{N-1}$. (Recall that $N$ is the number of visible levels, typically something like 4 or 5.)

An example: suppose that the screen width is something like $2^{10}=1024$ pixels wide, and that $s=2^{-6}=1/64$ We plan to perform the ceiling function on the resulting number, which is a discontinuous function and thus quite sensitive to imprecision. We need a precision of $2^{-10+6} = 2^{-4}$ to avoid having the ceiling function wrap in visibly wrong places. A single precision floating point number has 23 bits of precision, so we require $m + \log_2(x) + 4 <= 23$ or $m + \log_2(x) \leq 19$. For instance, if the camera is a modest distance like $2^9$ away from the origin, it can at most zoom in by 10 levels, which means that we get into precision problems when we have zoomed in enough to look at a closeup of an individual pixel. (Note that I'm ignoring a couple of things that I don't know about here, like what kind of precision losses are implied in taking the powers, etc...)

Let's take a closer look at $\kappa$ by substituting in $z=b^m$ and $x=\text{sgn}(x) b^{\log_b(|x|)}$ and $s = b^{\left\{ m - \frac{\ln(w)}{\ln(b)} \right\} - N + 1}$, and then looking at it's remainder modulo $b^{N-1}$: $$ \left\lceil \kappa \right\rceil \mod b^{N-1} = \left\lceil \text{sgn}(x)b^{ \log_b(x) + m - N + 1 + \left\{ m - \frac{\ln(w)}{\ln(b)} \right\} } - \frac{1}{2} b^{\left\{ m - \frac{\ln(w)}{\ln(b)} \right\} - N + 1} \right\rceil \mod b^{N-1} = \left\lceil \text{sgn}(x)b^{ \log_b(x) + m + \left\{ m - \frac{\ln(w)}{\ln(b)} \right\} \mod {N-1} } - \frac{1}{2} b^{\left\{ m - \frac{\ln(w)}{\ln(b)} \right\}} \right\rceil \mod b^{N-1} $$ So now we're looking at a term of order $b^{N-1}$ versus one of order $b^0$, in the "worst case" scenario. This should be much more manageable, precision-wise. (I'm again perhaps ignoring a few potential sources of precision loss.) More importantly though: the precision constraint now only applies to $N$ and $b$, so $x$ and $m$ can be whatever and we won't run into precision problems! To summarize, here's the important information about $k$: $$ k \mod {b^{N-1}} = \left\lceil \text{sgn}(x)b^{ \log_b(x) + m + \left\{ m - \frac{\ln(w)}{\ln(b)} \right\} \mod {N-1} } - \frac{1}{2} b^{\left\{ m - \frac{\ln(w)}{\ln(b)} \right\}} \right\rceil \mod b^{N-1} $$ This is the index we'll use to see where in the (wrapping) pattern the line falls. It can also be used to calculate the x-coordinate of the leftmsot grid-line, in camera coordinates. We do that in the next section.

Camera coordinate of leftmost gridline

The x-coordinate, in world space, of the lefmost gridline is $ ks/z $, where k is the index mentioned in the previous section. In camera-space, this works out to $$ x_L = z\left( \frac{ks}{z} - x\right) = ks - zx $$ We are again in danger of running into precision issues, since we are subtracting two potentially enormous numbers that are close to each other (since they are both camera coordinates of visible lines). However, we know that the answer should repeat with a period of $L = sb^{N-1} = b^{ \left\{ m - \log_b(w) \right\} }$, since the grid is periodic with period $L$ in camera space, so we calculate: $$ x_L \mod L = ks - zx = (k \mod b^{N-1})s - b^{m + \log_b(x)} \mod b^{ \left\{ m - \log_b(w) \right\} } $$