Colour Is Not What Colouring Is All About

December 18th, 2020

My prototype graphics generator has been merrily running on the test server for the past weeks, creating not only the cutest and silliest NPCs I have ever seen but also no end of harsh testing situations for the client-server communications part to expose various potential troubles. As a result, I enjoy the balanced situation where I can either take a break from communications to advance the graphics or take a break from graphics to advance the communications! This is - as you guessed already - the part where I kick the graphics out in the field again.

The aim this time is to find a working way to generate all those heightmaps that an infinite world requires. As a prerequisite and logical move at the moment anyway, the first step was to start building up a production as opposed to prototype graphics generator - while awk and the rest are excellent for prototyping, they are not really up to production standards. So I took first a few days to implement this time in Ada a png writer to start with and then the image generators that I had explored earlier with the awk and C code. While the naive view on this is that "she duplicated the effort having to reimplement now the same thing", the reality is of course quite the opposite of naivety: having previously explored so much with the quick-prototyping in awk, I knew now both the problems and the approach well enough to design a much more useful structure to start building on. And while it might still happen that bits and pieces will change and have to be refactored and rewritten (as it always happens when truly exploring the unknown), the checks and precision required by Ada actually help with this: it's way, way easier even to refactor bits and parts when everything is well defined and otherwise never failing silently.

In addition to the above, there was further speed gained also through the fact that Ada comes with very good support for all operations with complex numbers and in general with real numbers - the requirement to actually specify the desired precision is already just great. Moreover, the generics mechanism turns out to be a very convenient way to write packages that can be used as building blocks, to be combined as desired, even programmatically - this is by far the most effective way I found to deal with the sea of parameters that fractal texture generation throws at me otherwise. Anyways, in short, as a result on the code side of those past few days of re-focusing on graphics, I have now a set of generic packages and the tiny bit of glue required to mix them up for various exploration. To start with and for the most basics of checking that everything is working, here's the familiar shape of the Mandelbrot fractal, in plain gray and all done in Ada, png-writing included1:

The next break I took was the one in which I read the part that I had previously avoided - colouring approaches. This turned out to be in the end quite a useful thing - I finally found a published text2 looking at the Mathematics rather than the pretty-pictures-and-futzing-with-parameters-otherwise of this colouring of fractals business, so it took me one day with pen in hand to go through it all but at least I have something to show for the time thus spent! The "smooth" part in there was especially interesting to me, since my terrain-generation goal rather requires some smooth transition between shades of gray - at least if one aims for some reasonable transition from holes in the ground to mountains and everything in between. At any rate, having read that, I realised that the "colouring" name is even misleading - it's not as much about colours, as it is about choosing the information to represent and the way to pack its representation into a single value, preferably through a function that is continuous and has a continuous derivative as well, over the whole domain of interest. Once all that is done, the actual colouring is a separate step really - one can map the values obtained to any colour palette and therefore paint it all as desired. As usual though, it's trickier to choose correctly *what* to show and *how* to show it than to pick a bunch of pretty rather than ugly colours! Still, there are known functions for the picking of the pretty, too, and I even implemented a generic palette too, but that will have to wait its turn in the writing queue since this is getting already both long and convoluted so better to not add colours to the mix as well just now.

Given the happy realisation above that colouring is pointedely not about colours at all, I went ahead and implemented one of the fundamental approaches. The core of it is that the information picked for display is an average of the values obtained at each point rather than the counting of the number of iterations themselves3. This average is smoothed mainly by means of spline interpolation so that effectively there are several moving averages calculated and then combined to produce a final value.

The most interesting part of the above method is that it opens up perhaps a whole areas to explore, since it is but one specific case - the underlying idea seems to me to aim to look at each iteration essentially through a statistical lens instead of focusing so narrowly on only one overall measure at the end of the iteration. I don't yet know whether the average is indeed the best statistic that can be found for this purpose but since it seems at least slightly more interesting than the plain (or even smoothed) iteration count, I went ahead and gave it a spin. Note also that the actual result further depends on other parameters, such as the maximum number of iterations (to some extent) or the exact interpolation and smoothing techniques applied - for one clue in the images, the pin-point effects are basically discontinuities. It's also probably not at all surprising that an essentially statistical approach works better - or at least provides more detail - with more rather than with less data. More data in this case means a larger bailout value as well as a higher number of maximum iterations allowed. To illustrate all this, here's the very same basic Mandelbrot fractal coloured still in grayscale4 but showing the smoothed iteration count in the first image and the smoothed average curvature for 20, 50 and 100 iterations respectively in the following 3 images:



Armed as above with two working smooth colouring schemes and the generic building block of complex functions, the next logical step is to explore a bit functions other than the good old Mandelbrot. But since I'm running out of writing time right now, I'll leave the write-up of that exploration for the next article - this one is running long enough as it is and I didn't even get to mixing in any pseudo-randomness at all to spice things up!


  1. Surprisingly or perhaps not all that surprisingly, it's really this png-writing part that was a chore to implement. Supposedly png is actually one of the clearer standards out there and moreover, I implemented the bare minimum here but nevertheless, there's no joy I can find in the job of getting all headers just right and in the correct place and then chunking everything as expected and still having to hunt some tiny detail that just throws everything off at times. Anyways, at least once done it stays done and I guess it will even seem a breeze about the 10th time I implement it or something. 

  2. Harkonen, J., On Smooth Fractal Colouring Techniques, MSc Thesis, Department of Mathematics, Abo Akademi University, Turku, 2007 

  3. For a quick reminder here: the fractals are obtained through the iteration of complex polynomials; each point of the image is mapped to a complex number that is then used typically as the free term (ie coefficient of z^0) of a chosen complex polynomial; the polynomial is then iterated starting with (0,0) until either a maximum number of iterations or a bailout value are reached; when the bailout value is reached, the point is considered to have escaped the attractor of the function, basically converging towards infinity rather than remaining trapped in a radius of bailout size around the origin; the simplest representations pick then at each point the number of iterations performed and then map this to some colour scheme (sometimes pre-processing it first to ensure continuity). The averaging method aims instead to use more of the available information: it calculates the average of some characteristic (such as magnitude or argument) of all the intermediate values obtained when iterating at each point. 

  4. Well, the grayscale is the result of applying a function too but I'll skip those details for now.