clar fon @clarfonthey@toot.cat

decided that, because I know and trust the folks who run toot.cat, I'm going to try and start moving my alt account here too. however, before I make an actual alt account, I decided to move some of the light-hearted stuff that I used to post there into an unlocked account, @ltht.

most of the stuff there will be out-of-context quotes from stuff I've been watching or reading, and it will be boostable for folks who are as amused as I usually am.

honestly at this rate I've done enough research that I could probably write a literal academic paper on this algorithm

maybe I will, hmm.

1. I could technically just approximate most colour spaces as an octahedron, but that wouldn't be entirely accurate and ICC profiles give more data points to define the full shape.
2. I'm going to have to implement a 3D convex hull algorithm, aren't I.
3. oh, and to efficiently create a 2D slice, I'm going to have to find an algorithm to efficiently find the bipartite subgraph that represents the edges I need to slice in order to create my polygon.
4. oh no.
5. and I probably should write the code to get the ICC data too…

remembering that time last year when people called the cops on a suspicious-looking statue of Frederick Douglass

as a user, I want to construct objects, set them, get them, mix them all around town, and then yeet them into the sun. I call it my CSGMY system pronounced shzzhhhgimme

why is like 90% of tech debt just poorly designed crud apis

so, this is the final pain in the ass.

we have a point for our colour and a convex polygon for our space of valid colours. we need to find a new point that represents our desired hue, and then once we get that we can take our resulting XYZ value and convert it into sRGB and call it a day.

first, we will define "nudging" as mixing the colour with an equivalent shade of grey. we just figure out the intersection of our black-white line with the desired luminance. okay, done.

as a side note, to make our 2D colour generation also visualisable, we do another conversion from XYZ to xyY, where we essentially just divide by the sum of X, Y, and Z. this is what all the fancy computer colour diagrams online use. since we're essentially just doing an affine transform, this will keep our shape convex.

to check if our point is in the polygon, we sort our vertices carefully and use the right-hand rule. essentially, we keep our points ordered "counter-clockwise" according to a positive cross-product, and then make triangles out of each edge's points followed by the point we're checking. if any of these triangles is listed in clockwise order, rather than counter-clockwise, it means that our point is outside the polygon.

if we do find out that our colour is outside the polygon, we need to actually nudge it into shape. the way I do this is by finding the intersection of the shape and the line between our "grey" shade and the colour. really, this is just checking the intersection with all the edges until one of them actually intersects. technically, this won't be the closest point inside sRGB, but it will be the closest with the same hue; not only is preserving the luminance important, but also making the colour look visually similar; we could convert "impossibly bright blue" into "bright green" with the same luminance or "washed-out blue"; while the green might be closer to the original impossible colour mathematically, it won't feel as close to us humans.

and, yeah. we just convert everything back and that's it.

in order to detect whether a colour is in the space, we have no choice but to implement 3D collision detection. except, we can kind-of cheat. since we're always working with the same luminance, we really just need to do 2D collision. except... now, we're working with a 2D slice of a 3D object. yikes!

since parallelepipeds are basically just stretched cubes, it's more helpful to just imagine that we have a cube, for simplicity. the maths works out the same either way.

first, completely disregard black and white as the bad and ugly cases. at luminance 0 and luminance 1, we always just want black or white, and shouldn't even bother doing any weird shape maths. the shapes at those levels are just points, which we don't want to deal with.

any other slice is a convex polygon with anywhere between 3 and 6 edges. in the cube case, slicing off one corner gives you a triangle, and cutting off four corners gives you a hexagon. since the cube is symmetrical, cutting off 5-7 corners is the same as cutting off 1-4; just grab the other half you cut.

take your time and grab out the nearest and closet approximation to a cube you have and agonise over trying to visualise. it's okay to give up before you continue reading.

the key insight from this exercise is that however you cut, the points on the boundary will always be along some edge of the cube. the reason why we can have between 3 and 6 points on our cube is that we have 12 edges to cut, and we need at least 3 to cut a shape; if we cut more than 6, the symmetry argument means we really just had less than 6.

so, how do we tell what edges we cut? well, we can look at all the points on the cube (in this case they're at the eight primary colours black, red, green, blue, cyan, magenta, yellow, and white) and then figure out which side of the cut they're on. the edges that are cut will be the ones where the vertices are on opposite sides of the cut; in my case, I just go through every pair of colours across the cut and check if they have an edge between them.

technically you don't even need to verify that the pair of colours lies on an edge, since we have an extra bit of info to help us: the resulting shape is convex. so, if one of the points isn't in the convex hull of what we've got, we know that there's no edge. convex hull algorithms are a pain, so, I chose to just check if there's an edge.

the way I do the edge checking is basically by giving each vertex a 12-bit number where each bit corresponds to an edge, AND the two vertices' numbers, and check if it's nonzero. but, implementation details, you could do it however you want, babey.

so, to recap: we slice our parallelepiped (think of it like a cube) at a given luminance and then get some shape. ignoring the luminance of our colour, we now have a point for the colour we want, and a shape telling us what colours we can have. the next step is to check that our colour is in the shape, and to nudge it in if it's not.

this is actually pretty easy

pretty much all colour spaces (including sRGB) are defined with three primary colours, to match the three types of cone cells in our eyes. one of the more useful colour spaces we can use is CIE XYZ, where the X and Z represent the "hue" of the colour and the Y represents the brightness, or luminance. the luminance we use to compute the contrast ratio is actually this Y value, which represents the stimulation of the rod cells (not cones) in our eyes, which detect brightness. essentially, this means that even if someone has no working cone cells (and hence no colour vision), this is how bright various colours will appear to them.

sRGB is defined as a simple linear transformation from XYZ, so we can just mess around with matrices to convert back and forth. if we convert to XYZ, we can then set the Y to whatever we want and get a colour with the desired brightness.

the issue, of course, is that we can get "impossible" colours which make absolutely no sense. and while this impossibility will always be relative to what level of colour vision a person has, in our case, we just care about whether a colour is in sRGB or not.

because the transformation between sRGB and XYZ is linear, we can model it as a parallelepiped (fun word) and then just compare the colour with our parallelepiped and see where it should actually go.

and, this leads to the next part...

so, starting with the simple stuff: the equation for the contrast ratio is (x + 0.05) / (y + 0.05), where x and y are the luminance of the two colours. we always put the larger luminance on the top to make sure we get a positive number. the range of possible values we can get for this are 1 to 21; the first case is for two colours that have the same luminance, and the second is between black and white, which simplifies to 1.05/0.05 = 21.

to figure out the colour with a 7:1 ratio, we just need to set the ratio to 7 and solve, but there's a caveat: we don't know whether the colour should go on the top, or the bottom.

this is where we get clever and notice something. there is a luminance that's exactly between white and black, that is, such that 1.05 / (x + 0.05) = (x + 0.05) / 0.05. this is around 18% luminance, so we just check whether a colour's luminance is above or below this to determine which version of the equation to use.

that's the easy part, which lets us figure out the luminance of the colour we want.

(oh, and to clarify the "sad zone" I mentioned earlier: we might get a luminance lower than zero or higher than one, which is fine; we just have to cap the number we get into this range)

here are the sRGB colours with (approximately) 7:1 contrast with:

000000 -> 959595
FFFFFF -> 585858
FF0000 -> 000000 (*)
00FF00 -> 005000
0000FF -> E6E6FF
FFFF00 -> 575700
FF00FF -> 000000 (*)
00FFFF -> 005353

(*) these colours lie in the "sad zone" where a 7:1 ratio is literally impossible. neither pure black nor pure white satisfies this ratio, so, we just pick the one further from the colour we've got. the worst case is actually greys around 757575, which can achieve at maximum a 4.5:1 ratio.

in the broadest terms, the code computes the luminance of the colour (which is used to compute the contrast ratio) and then figures out the luminance of the desired contrasting colour. using a clever change of coordinates, we can just "set" the luminance to this new value, but the caveat is that this colour might not actually exist in sRGB, which is the set of colours computers can display.

there's actually an example of this in the colours I gave: since blue is the darkest primary colour our eyes perceive, pure blue actually contrasts better with white than black. however, since it's pure blue, it's already the brightest blue we can possibly have in sRGB; it's literally impossible to have the same blue, only brighter. to compromise, we have to mix the blue with equal parts red and green in order to get a brighter colour.

before I convert back to sRGB, I have to check if the resulting colour actually fits. if it doesn't, I have to nudge it closer to the equivalent shade of grey until it fits.

in a reply I'll go into a bit more detail about why this is challenging, which I've gone over a bit in past posts, but I just want to summarise.

like I literally told them, hi it's been literally The Year of shit happening that really sucks and is totally beyond most people's control, the last thing you can do is make it look like you're intentionally not doing something about the situation and that it could just be really minor but you don't wanna give any fucks about it