An interactive explanation of Spherical Fibonacci Grids and its properties.
The main problem in Physically-Based Ray Tracing (PBRT) is converging the value of the illumination integral that appears in the Light Transport Equation (LTE) (eq. \eqref{LTE}). Integral equations generally do not have an analytic solution, so numerical integration techniques are used. The most common approach is Monte Carlo integration (MC), which is based on randomization:
\[\begin{equation} \label{LTE} L_o(p, \omega_o) = L_e(p, \omega_o) + \int_{S^2} f(p, \omega_o, \omega_i)\, L_i(p, \omega_i)\, |\cos\theta_i|\, d\omega_i \end{equation}\]Further improvements focus on manipulating the random sampling to minimize convergence time — that is, distributing the samples so that we obtain the minimum error with the minimum number of samples. These methods fall under the category of Quasi-Monte Carlo integration (QMC).
In this context, we find utility in low-discrepancy distributions such as Fibonacci-based spherical distributions. The main strength of these point sets is an extremely uniform distribution which is near-optimal in terms of spherical cap discrepancy. There are two families of such point sets:
SFILs constrain point set sizes to be Fibonacci numbers. SFGs, on the other hand, allow generating point sets with an arbitrary number of points — which is strongly important in Physically-Based Rendering (PBR). For this reason, we focus on SFGs.
In mathematics, two quantities are in golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities:
\[\frac{a+b}{a} = \frac{a}{b} = \Phi \qquad \text{such that} \quad a > b > 0\]\(\Phi\) (also called the extreme and mean ratio, or divine proportion) satisfies the quadratic equation and is an irrational number. Some people call it the most irrational number, and this property makes it extremely useful when distributing samples without generating repetition patterns, therefore implying a low discrepancy.
\[\begin{equation} \label{golden ratio} \Phi = \frac{1 + \sqrt{5}}{2} = 1.618\ldots \end{equation}\]The following key identity is what makes it unique (the derivation can be found in the following subsection):
\[\begin{equation} \label{gr key identity} \frac{1}{\Phi} = \Phi - 1 \quad \Rightarrow \quad \frac{1}{\Phi} + 1 = \Phi \quad \Rightarrow \quad 1 + \Phi = \Phi^{2} \end{equation}\]This is mathematically exact and unique to the golden ratio because it satisfies the quadratic equation. We can also sustitute \(\Phi\) in eq. \eqref{gr key identity} to see it in a continued fraction expansion form. This shows that the golden ratio is the most irrational number, meaning that its rational approximation converges slower than for any other irrational number.
\[\Phi = 1 + \frac{1}{\Phi} = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{\ldots}}}\]In mathematics, the Fibonacci sequence is defined such that each element is the sum of the two preceding ones:
\[F_m = F_{m-1} + F_{m-2} \quad \text{for } m > 1, \qquad \text{where } F_0 = 0 \text{ and } F_1 = 1\]Fibonacci numbers appear unexpectedly often in mathematics, and are applied in multiple areas such as computer algorithms and biological settings (phyllotaxis, shell spirals, branching patterns).
Fibonacci numbers are also strongly related to the golden ratio. As the sequence progresses, the ratio of successive Fibonacci numbers approaches a specific irrational number, the golden ratio \(\Phi\):
\[\lim_{m \to \infty} \frac{F_{m+1}}{F_m} = \Phi \approx 1.618\ldots\]Due to this relation, Fibonacci-based distributions are frequently found in many applications requiring uniform, low-discrepancy coverage of a domain.
The Cartesian coordinates $(x_j,\, y_j)$ of the \(j\)-th point of a Planar Fibonacci Grid ($F_G$) with \(N\) samples are given by:
\[\begin{equation} \label{eq:pfg} \left. \begin{aligned} x_j &= \frac{j}{N} \\ y_j &= \operatorname{frac}\!\left(\frac{j}{\Phi}\right) \end{aligned} \right\} \quad 0 \le j \le N \end{equation}\]frac() frac(x) = x mod 1. Takes the fractional part of a number.
where $frac()$ denotes the fractional part, keeping values inside the unit square $[0,1)^2$.
This gives a distribution of samples in the unit square where each coordinate has a different delta (space between points): \(\frac{1}{N}\) in the x-coordinate, and \(\frac{1}{\Phi}\) in the y-coordinate.
Planar Fibonacci Grid — 30 points in [0,1)²
We can directly define the distribution on the unit sphere by using the Lambert cylindrical equal-area projection. The result gives the samples in terms of the elevation angle \(\theta\) and the azimuth angle \(\phi\). To maintain the uniformity of the samples along the vertical axis, the x-coordinate is mapped to \(z = \cos(\theta)\) instead of just \(\theta\). This projection gives us the following relation equations:
\[\begin{equation} \begin{aligned} x &= \frac{1 - \cos(\theta)}{2} \\ y &= \frac{\phi}{2\pi} \end{aligned} \end{equation}\]By substituting in the previous equation we obtain the polar coordinates of the \(j\)-th point of a Spherical Fibonacci Grid:
\[\begin{equation} \label{eq:sfg} \left. \begin{aligned} \theta_j &= \arccos\!\left(1 - \frac{2j}{N}\right) \\ \phi_j &= 2\pi j\,\Phi^{-1} \bmod 2\pi \end{aligned} \right\} \quad 0 \le j < N \end{equation}\]Also, SFGs are sometimes expressed with a shift in the z-axis. This shift symmetrizes the z-coordinate distribution so that the first and last points are at equal distances from their closest pole, which improves the spherical discrepancy of the point set.
This shift is half the distance between samples in the z-axis (half the delta). It can be computed either in the unit square or on the unit sphere:
The symmetrized formulas become:
\[\begin{equation} \label{eq:shift sfg} \left. \begin{aligned} \theta_j = \arccos\!\left(1 - \frac{2j+1}{N}\right) \\ \phi_j = 2\pi j\,\Phi^{-1} \bmod 2\pi \end{aligned} \right\} \quad 0 \le j < N \end{equation}\]To finish this section, the previous equations will be presented in terms of the unit hemishpere instead of the unit sphere. This is quite necessary, since many uses cases in PBR are computed on the hemisphere (only accounting for the reflection effect and omitting the transmittance).
[HEMISPHERE EQUATIONS …]
An alternative definition of a planar Fibonacci grid exists using a pair of consecutive basis vectors. In this case, the points are not restricted to the unit square but they exist in a planar Fibonacci lattice ($F_L$).
\[F_L = \{ p = z_0 b_k + z_1 b_{k+1} : (z_0, z_1) \in \mathbb{Z}^2 \}\]Swinbank and Purser
$N$ is the number of points on the grid and $F_{k_m}$ the largest Fibonacci number smaller or equal to $N$. The basis vectors satisfy a recurrence relationship similar to that of Fibonacci numbers.
\[b_{k+1} = b_k + b_{k-1}\]Using any pair of basis vectors ($b_k, b_{k+1}$) we can obtain a parallelogram area called unit cell. By definition the unit cell does not contain any point in its interior. We can compute the area of the parallelogram by doing the determinant of the matrix composed by the basis vectors of that parallelogram.
\[M = \begin{bmatrix} b_k & b_{k+1} \end{bmatrix} = \begin{bmatrix} \frac{F_k}{N} & \frac{F_{k+1}}{N} \\ \frac{(-1)^{k-1}}{\Phi^{k}} & \frac{(-1)^{k}}{\Phi^{k+1}} \end{bmatrix}\] \[\text{Area of Parallelogram} = det(M) = \Delta_M = \frac{F_k}{N} · \frac{(-1)^{k}}{\Phi^{k+1}} - \frac{F_{k+1}}{N} · \frac{(-1)^{k-1}}{\Phi^{k}} = \frac{1}{N}\]We prove that the area of the unit cell of a Fibonacci distribution for any N will be \(\frac{1}{N}\). This confirms us that it is a suitable lattice for QMC numerical integration.
…
Distributed under the terms of the CC BY-NC-ND 4.0 License.