A recent entry on the (sadly now defunct) computer graphics message board OMPF.org directed my attention to what, in my opinion, qualifies as one of the nature’s most beautiful mathematical structures. I’m referring to the sunflower capitulum, an organic arrangement that ensures an optimal packing of seeds in a circular bed based on growth over time from a single point (a process known as phyllotaxis).

The capitulum of a sunflower. Image courtesy of Unitopia (Commons licenced).

The capitulum is distinctive because its growth program is based on the golden angle, a constant which has deep roots in both mathematics and the arts. New seeds are arranged about the central axis, each at a distance proportional to the square root of its rank and at deflection of ~137.5 degrees from each predecessor. As the pattern builds, the irrational nature of the seed angle prevents periodicities in the arrangement and eliminates gaps. What’s immediately eye-catching about the capitulum are the concentric spirals that radiate from its centre. Interestingly, these curves are not “by design” insofar as they are not an intended consequence of the growth program, but are highlighted by our brain’s natural predisposition to spot patterns.

A strategy for generating points that mimic capitula distributions was introduced by Helmut Vogel [1] who proposed that a spiral based on particle energies in a cyclotron could be used to seed points from the centre outward. His paper also established a mathematically rigorous framework for the existence of the spirals, predicting where each one begins and ends as a function of the Fibonacci sequence. I won’t go into Vogel’s work in detail here except to say that it’s a interesting read and neatly proves the case for the emergence of the golden ratio in the natural world.

The synthetic capitulum and its cyclotron growth spiral.

So how does this have a bearing on rendering? In the blog post linked from the OMPF thread, Mukund Sivaraman suggested that the sunflower capitulum would make an good sampling pattern for a thin-lens camera model. Sampling, or the selection of points over the domain of an integral, is a topic of key importance in computer rendering since the selection of an appropriate algorithm is key to optimal image quality. While the capitulum would certainly do a good job of sampling a thin lens, my thoughts were drawn more to its potential in hemispherical sampling. The rationale behind this is based on the relative difficulty in placing points over a unit hemisphere, and requires a quick delve into the background math to explain.

Complete sphere’s are known as locally-Euclidean 2-manifolds. This means that an object placed on the surface (like a person on the surface of a planet) has two degrees of freedom in which to move (or walk). On top of this, spheres exist in 3-dimensional Euclidean space so every 2-manifold coordinate has a 3D spatial counterpart. So far, so good.

In optics, hemispheres represent a integral domain over which light arrives at a given point on a surface. To work out how much light is reflected towards an observer, this integral must be solved numerically with the minimum of error. Consequently, it is advantageous to be able to place samples evenly over the entirety of the hemisphere. This gives us a problem of how to evenly sample a surface which is locally 2-dimensional but which appears rounded in 3-dimensional space.

We need an analogy. In the same way that a globe of the earth cannot be flattened out into a wall map without some degree of warping, so a 2D sheet cannot be wrapped around a hemisphere without encountering the same problem. Think of it as trying to wrap a football with a single sheet of plastic food wrap covered in small dots. No matter how you fold it, you’ll end up either with bits that overlap or regions that are stretched. This in turn disturbs the original spacing of the dots. In the end, you must accept that the sheet will get warped and carefully consider the initial positions of the dots be so that after you’ve wrapped the ball, they’ll appear to be evenly distributed.

See the problem?

Stratified sampling	Jittered sampling

Practically speaking, one of most basic schemes of sample placement is a simple stratification using polar coordinates as shown above. Although the samples are evenly-spaced in the polar coordinate system, the hemispherical “wrapping” function results in severe distortion around the axial origin. Jittering (shaking) the points removes this uniformity at the expense of introducing entropy. Visually, this makes the render more noisy (grainy).

Other, more sophisticated schemes perform better. HEALPix [2] is a recent development with produces a hierarchical, low-distortion distribution using a series of tiles which serve as the strata. I personally love this algorithm, particularly when combined with the polyomino sampling scheme of Ostromoukhov et al [3]. Unfortunately, methods based on tiling also tend to be comparatively complex, requiring separate parameter schemes for each tile.

Sticking to strictly 2D parameterisations, we encounter a further problem: most schemes are unable to generate arbitrary numbers of sample points while still ensuring a consistently even stratification. The polar scheme above, for example, can only yield sample sets whose size is divisible by 4. In the case of HEALPix, hierarchical subdivision means set sizes must follow the sequence 12, 48, 192, etc.

So what does all this have to do with the capitulum? Well first, being based on an optimally-packed, radial growth program in polar coordinates, it can be made to cover a hemisphere with no warping, requiring only slight modification to the original cyclotron spiral. Secondly, since points are seeded on the spiral’s curve, it represents a 1D parameterisation which places no restrictions on the size of its sample set.

Capitulum sampling

Sounds promising, but the question is: how does this translate to the final render? The table below shows a zoomed-in portion of a Cornell box rendered using random, jittered stratified and jittered capitulum schemes. 50 samples were taken per pixel. It should be noted that a certain amount of jittering (entropy) is necessary with any sample scheme in order to prevent aliasing. The underlying quality of the hemisphere mapping dictates how little jittering it’s possible to get away with. Click each image to see the full version.

Random sampling (worst case)	Stratified/quasi- random sampling	Capitulum sampling	Reference

Clearly, capitulum sampling performs at least as well and in many places better than jittered stratified or quasi-random sampling (not shown, but virtually identical). Compared to purely random sampling, it performs better still.

In summary, the capitulum sampling scheme presents a simple, fast and elegant way of equidistributing samples over the unit hemisphere. While using this approach is advantageous in numerous situations, it’s not a magic bullet. First and foremost, capitulum sampling is neither an unbiased nor a progressive sampling method. This is bad news for unbiased MCMC renderers like Maxwell or Fry Render. Secondly, it’s 1D parameterisation makes it useless for algorithms such as radiance caching which require a 2-manifold space over which to compute gradients.

Despite these drawbacks, it’s still pleasing to see how a pattern perfected by the natural evolution of plant growth has a positive impact when applied to a problem as artificial as global illumination.

References:
[1] A Better Way to Construct the Sunflower Head. Vogal, H. 1978.  http://www.sciencedirect.com/science/article/pii/0025556479900804
[2] HEALPix: A Framework for High-Resolution Discretization and Fast Analysis of Data Distributed on the Sphere. Górski, K.M. et al. 2005. http://iopscience.iop.org/0004-637X/622/2/759/
[3] Sampling with Polyminoes. Ostromoukhov et al. 2007. http://www.iro.umontreal.ca/~ostrom/SamplingWithPolyominoes/