Friday, April 13, 2018

Giving the Kwak8 256 colours.

I am working on a 8-bit fantasy console called the Kwak-8. Inspired by the Pico-8 it provides a platform for people who want a more low-level coding experience

For the most part the Kwak-8 can be thought of as a 16 colour machine. The display generation modes and the blitter are both based around a fixed 16 colour palette. You can achieve more colours using the serial pixel writing port. Writing a byte to the port uses a colour from an 8 bit palette. This gives you more colours but at the cost of having to use the CPU to build up the image pixel by pixel. It is something to be used sparingly and/or cleverly.

Since the 8 bit palette will be not be changeable. I wanted to pick the best 256 colour palette I could find. As a general purpose palette it has to offer a bit of everything. I could find surprisingly few palettes in this category.

First up, let's look at the VGA palette.
The VGA pallete colours. Mouse-over the 3D view to see Lab space.

The reason we start here is pretty much to dismiss it out of hand. As general purpose palettes go it's laughably bad. From a technical standpoint it has given far too many entries to cover hues, and not enough for brightness and saturation. From a non-technical standpoint, just look at it! It's just hideous. The Base 16 colours, a greyscale then three slow trips around the colour wheel for Vivid, Murky and Murkier.

Let's not use the VGA palette.

Next up is the most obvious, naive thing to try. Make the largest colour cube you can fit into 256 entries. 6x6x6 comes to 216. So you can have a colour cube with six shades of red, green, and blue.

That's actually a pretty good range, for any arbitrary colour there will be something at least in the ballpark. This seems to be why there aren't many different 256 colour general purpose palettes. This is fairly good and consequently many general purpose palettes incorporate these 216 colours. Web Safe colours use exactly these values

Beyond this point, things got much harder to find. I encountered a nice and logical enhancement at https://www.compuphase.com/unifpal.htm. This suggests a palette with the Windows fixed system colours, a grayscale and a gamma adjusted colour cube with the corners trimmed off. You don't lose colours trimming the corners off the colour cube because those colours already exist within the fixed Windows entries.

The other interesting candidate was also a gamma adjusted colour cube, but one with a clever twist. The palette can be generated from the following javascript


 function gammaRamp(count,gamma=1.5) {
  result=[];
  for (let i=0; i<count; i++) {
   result.push(Math.round( Math.pow(1/(count-1)*i,1/gamma)*255));
  }
  return result;
 }

 function make8LevelCube(gamma=1.5) {
  let  levels = gammaRamp(8,gamma);
  let result = [];
  for (let i = 0; i<256;i++) {
   let gi = (i>>2) & 7;
   let bi = (i>>5) & 7;
   let ri = (i<<1) & 7 |  (gi&1) ^ (bi&1) ;
   result.push( [levels[ri],levels[gi],levels[bi]]);
  }
  return result;
 }

This makes a 8x8x8 colour cube where the least significant bit of the red intensity is the XOR of the least significant bits of the other two primaries. You get 8 primary intensity levels but at the cost of having to add just a hint of another primary colour to the mix.

It is certainly a very orderly looking palette. It's a bit hard to see that there are 8 levels of red in this arrangement, but each set of 4 reds is slightly offset from it's neigbours.

Just by looking at the palette tables, it is very hard to assess how well they represent the full range of colours. To act as a more useful guide I converted them into cylinders of hue, saturation and luminance. Each slice of the cylinder has the same saturation. I matched each point with the closest colour in the palette using both, RGB distance and the CIEDE2000 colour difference.

Saturation

If you drag the saturation slider up and down you can see the relative strength and weaknesses of the palettes. The 8x8x8 colour cube actually does a very good job in general, but when you get down to grays, the lack of a dedicated grayscale shows up. The colour shift of the bit twiddling limits the number of pure grays causing it to be worse than even the 6x6x6 colour cube. The weak point of the Gamma adjusted system palette is when things are slightly off gray, low saturation colours are much better represented by the 8x8x8 palette.

If you wanted to display colour video on a 256 colour display, the 8x8x8 would probably be a very good pick, Pure gray seldom occurs naturally and it has plenty of colours in the general neigbourhood of grey.

One thing I do notice about the palettes is they all seem to have colours that are nearly indistinguishable in some areas and yet neighbouring colours in other areas have quite dramatic changes. This is to be expected with colour cubes, human eyes do not see all hues equally. The MacAdam Ellipse demonstrates the problem nicely


One person's equal perception Ellipses (scaled 10 times larger than measured)

So our ideal palette probably has fewer greens and more purples, but it looks like it's going to be a bigger job than just shuffling around a few colours. So how does one generate an evenly spaced palette in the wibbly wobbly space of human perception?

I'm a fan of evolving solutions. Ever since I saw the original Evolving Mona Lisa post, I have been trying variations of this technique to problems. I did my own variant of the Image evolving where I evaluated it as a compression technique, with better results than I imagined. More recently I tried a version using a shader and an odd sort of distance field. It did pretty well.

It takes a long time, but as long as you have a way to measure the quality of a result you can make random changes and keep the changes that make things better. The theoretical ideal general purpose palette that we are after is one where any arbitrary colour we choose is represented by a colour in the palette which is as similar(to a person) as possible. The CIEDE2000 colour difference function provides a good basis for judging how good such a palette is.

I won't bore you with all of the details of the many things I tried. I shuffled colours around a lot and tried a huge variety of fitness functions. Ultimately a mix of fitness functions at different stages of evolution helped. I suspect I could keep on tweaking the code for years to get it better, but I had to stop somewhere.

Once I had a set of colours to work with, They were essentially randomly ordered. I wanted to put them into some form of useful order. Observing the earlier palettes, I noted it is actually quite hard to find the colour you are looking for when it is surrounded by colours that are significantly different. I developed a plan of attack. Assuming a prospective pixel artist was looking at a 16x16 table of colours, minimize the distance between neighbouring colours. Once again that sounds suspiciously like a fitness function, so evolution solves the problem without having to think too hard.

The actual fitness function I ended up using focused only on the palette entries 32...255. The first 32 colours are the Arne16 palette and a greyscale. I left it running for a fairly long time and the end result came out rather nice.

I think a prospective artist would be able to get a feel for the structure of the palette and know where to look for the colour they were wanting to use.

Now, let's take a look at the palettes and see how it compares with the others.

First up, greyscale;

VGA
ColourCube 8, redSwizzled
Websafe palette
Gamma adjusted System Palette
Evolved

It is no surprise that the palettes with dedicated grey ranges perform better here. On my display, the Evolved palette is more balanced with The Gamma Adjusted System biasing too strongly towards the lighter colours. I'm not sure how others will see it. This is about the only time the VGA palette is even remotely comparable.

Once we add a little bit of colour the story changes considerably.

VGA
ColourCube 8, redSwizzled
Websafe palette
Gamma adjusted System Palette
Evolved

At this level the Evolved palette seems to be the winner, The redSwizzled colour cube and the Gamma adjusted system palette don't do too badly though, At this point we'll drop the VGA palette, and the websafe palette so we just have the three to look at.

ColourCube 8, redSwizzled
Gamma adjusted System Palette
Evolved

At this level it becomes more subjective, I can't really call which is better. I can note differences The Evolved palette has fewer colours around the cyan to green and green to yellow parts of the wheel. On the other hand it has more oranges and browns in the yellow to red range.

The redSwizzled palette has a fairly detailed range from magenta to black and purple to black. The Evolved palette seems to better represent the darker colours compared to the other two.

ColourCube 8, redSwizzled
Gamma adjusted System Palette
Evolved

At full saturation The story is similar. The first two are better around the magenta area. The evolved is weaker on green hues but fades off to black a bit more smoothly.

Ultimately the evolved palette does more or less what I asked of it. It resulted in a palette with colours more evenly distributed. If I were to manually tweak the palette I might add another hue to the yellow/green area, but I'm not sure where I would take the colour from. There are certainly many other little improvements that could be made, but for now this will have to do me.

I am open to receiving suggestions and updates to this palette. I won't need to freeze the palette of the Kwak-8 system until someone actually releases a program that relies on it.

Next up for my Kwak-8 development is an in-browser assembler, so that people can dive in and make little bare-(emulated)-metal Kwak-8 programs without having to install a development environment. The Assembler already works, I just need to tidy up the environment a bit and add some examples. Stay tuned.



Finally, here's a view of all of the palettes so you can compare them at your leisure.

Saturation

1 comment:

  1. Worked briefly years ago on tiny palette which mapped into grayscale well for no-colour grey scale monitors when they had better dpi than colour did. It's surprisingly hard to chose good distinct colour whuvh remains distinctive in grey.

    Non linear eyeballs. Great stuff.

    ReplyDelete