Add rand integration

[Ogeon]

As discussed in #173, it would be helpful to have official support for generating random colors. Possibly also with min/max values for the components. The benefit of having it built into the library would be to make it easier to get uniformly distributed samples in each color space. Spaces like Hsv and Lch would sample within a cone and cylinder, for example.

Here's a preliminary check list for the parts of this feature:

• Implement Distribution<T> for Standard for each color space. Some will be more complicated than others, as their geometry are different. See the discussion below.
  • Hsl
  • Hsv
  • Hwb
  • Lab
  • Lch
  • Luma
  • Rgb
  • Yxy
  • Xyz
  • Alpha
• Implement SampleUniform for each color space. Will likely be able to share code with the Distribution implementations.
  • Hsl
  • Hsv
  • Hwb
  • Lab
  • Lch
  • Luma
  • Rgb
  • Yxy
  • Xyz
  • Alpha

Each part can be implemented separately, but probably best in top-to-bottom order.

Geometry:

• Hsv and Hwb - Cone. Seem to be the same space, but expressed differently.
• Hsl - Bicone. Should be possible to sample as a random selection between two cones.
• Lab, Rgb, Xyz and Yxy - Cubes and blocks. Each component can be sampled independently.
• Luma - A line. Just a single value.
• Alpha - Samples the contained color and the alpha channel independently.

Other preferences and requirements:

• This should be implemented behind an optional Cargo feature.
• It should preferably be implemented with #[no_std] support.

[okaneco]

Features

We need to figure out the bare minimum of rand features needed along with no_std compatibility. I assume at first the "rand" feature implementation should require "std"? Doing more reading I'm leaning towards keeping it std because the book lists issues with the portability of floats for distributions and the crate may not build on devices which don't support the features they need. I don't know the specifics though.
https://rust-random.github.io/book/portability.html

Here's the rand book
https://rust-random.github.io/book/crates.html
https://rust-random.github.io/book/features.html?highlight=no_std#no-std-mode

rand cargo.toml, edited to show what I believe are the relevant features. In my project I'm using default features off and only "std".

default = ["std", "std_rng"]

# Option (enabled by default): without "std" rand uses libcore; this option
# enables functionality expected to be available on a standard platform.
std = ["rand_core/std", "rand_chacha/std", "alloc", "getrandom", "libc"]

# Option: "alloc" enables support for Vec and Box when not using "std"
alloc = ["rand_core/alloc"]

# Option (enabled by default): enable StdRng
std_rng = ["rand_chacha", "rand_hc"]

Seeding, PRNGs, and CSPRNGs

https://rust-random.github.io/book/guide-rngs.html#basic-pseudo-random-number-generators-prngs
https://rust-random.github.io/book/guide-rngs.html#cryptographically-secure-pseudo-random-number-generators-csprngs

PRNGs are faster and take up less memory but I don't believe they can be seeded in rand. For that we'd have to use something like ChaCha8Rng in this example.

I think nonseedable and seedable rngs should both be available so users don't have to take a hit if they don't need it. I wouldn't grab seedable every time but I'd expect it to be there if I looked for it. Pcg64Mcg seems like a good choice for a nonseeded rng and ChaCha8Rng for seeded.

sample and gen_range

Under the hood, gen_range uses sample_single which prioritizes generating a number in a single use case. For generating multiple colors you'd want to use Uniform which does more work up front but makes sampling multiple numbers faster. Where the threshold is for which is faster I don't know. Uniform has new which is [low, high) with high excluded and new_inclusive with high included.
https://docs.rs/rand/0.7.3/rand/distributions/uniform/struct.Uniform.html

For generating multiple numbers, a distribution should be used. For one number, gen_range should be used. I also found out that gen_range is [low, high) so it makes sense to use for the case of hues which are [0, 2π | 360) or non-inclusive Uniform.

I was thinking that we should probably use an inclusive uniform distribution of [0.0, 1.0] for most cases and then multiply those color values with a scaling factor by whatever the scaling factor is. I think we can also generate [0, 255] for Rgb from a Uniform::new_inclusive distribution. There should be functions to generate both one color or multiple colors at once into a container. This avoids having to spin up multiple rngs if you know you want more than one.

I'm not sure of any other good containers for multiple colors or like in #156 where gradients rely on Vec, so the features can't be no_std with the current design unless the alloc crate is brought in.

Sampling cylinders/hues

I think this article on unit circle sampling outlines the approach we should take for hues/cylinders (ignoring the fact that gen_range is [0, 1)).

let hue = std::f32::consts::PI * 2.0 * rng.gen_range(0.0, 1.0);
let s = UPPER_BOUND * rng.gen_range(0.0, 1.0).sqrt();
let v = UPPER_BOUND * rng.gen_range(0.0, 1.0);

Whatever the radius factor is should have a square root applied to it in order to assure proper sampling of the unit circle. In this example it's HSV so the radius is Saturation.

Then things get weird with some of these color spaces like HSV and HSL. HSL especially because colors can only be fully saturated at 50 which makes it difficult to use in my experience. That aside, I think the best we can really do is equally sample a cylinder even though the color space is more like a cone or bicone for HSV and HSL, respectively, as shown in the right column of this image (and ignoring the strange RGB spheres).

https://commons.wikimedia.org/wiki/File:Color_solid_comparison_hsl_hsv_rgb_cone_sphere_cube_cylinder.png

Distributions and gen

https://rust-random.github.io/book/guide-dist.html

Most appear to be deprecated aside from those in the book. Thus, uniform [0, 1) and [0, 1]. There doesn't seem to be a normal distribution currently.
https://rust-random.github.io/rand/rand/distributions/index.html

Other use cases

The main cases I can think of are

1. random valid color from a space
2. random valid color between two colors
3. random valid color between self and min/max

Support for ranges could be cool. Something like

let color = Rgb::<u8>::new_random(60..=80, 110, 150..=170);

There have been times when I've wanted to generate colors with constant L* so that could use the second case. There should be some equal/relative equal to see if the colors are the same value so as to not generate a number for that range.

let c1 = Lab::new(50, 20, 0);
let random = c1.get_random_between(Lab::new(50, Lab::max_a(), Lab::min_b()));

In this example, we would only generate random values for a* between 20 and 127 and b* between 0 and -128.

[Ogeon]

Thanks for taking a closer look at it.

The portability seem to be a relatively small problem. Only rand_distr requires std, and it's the only part that seem to be affected by the float portability, but that one can probably just be ignored for now. We can start by just focusing on uniform distribution. And if we can implement the appropriate traits from rand, it may be possible to get away with not caring too much about alloc in the beginning. I would like to start out making it no_std, and see how far that lasts.

I think nonseedable and seedable rngs should both be available so users don't have to take a hit if they don't need it. I wouldn't grab seedable every time but I'd expect it to be there if I looked for it. Pcg64Mcg seems like a good choice for a nonseeded rng and ChaCha8Rng for seeded.

I think the overall direction should be to make things as generic as possible, regarding which RNG is used, just like rand itself does. There could, for example, be an RngExt trait in case we need to do anything special, but the more of the defaults we can use, the better. My impression is that the idea behind rand is that the user interacts with the RNG itself to generate the values and I would like us to continue down that path if possible.

For gen_range it seems like most colors will need their own UniformSamplers with the correct ranges and constraints coded into them. There may be some way to abstract away parts of them as some TristimulusSampler, AlphaSampler, and so on, but still. Constructing them out of multiple other samplers seem easy and cheap enough. I guess it would look something like

impl<T: SampleUniform, S> SampleUniform for Rgb<S, T> {
    type Sampler = RgbSampler<S, T>;
}

and RgbSampler would use one or more T::Samplers internally. I noticed implementing SampleUniform gives a free implementation of Distribution<T> for Uniform too, so that's cool. That makes sample and sample_iter available too, as long as Uniform is used.

Getting gen seem to only involve implementing Distribution<T> for Standard. That should be simple enough, I suppose. Not sure if the generic component type will cause any trouble, though.

I think you are spot on when it comes to how to generate the component values. Hues cannot be inclusive, I think, because that would double count 0 (a.k.a. 360 degrees). Cylinders and cubes/blocks are a solved problem. HSV and HSL may need to be sampled as cone and bicone to avoid having an overrepresentation of grays (they are of course ambiguous enough to have arguments for both). Generating a point inside a symmetric bicone would be the same as generating a point inside either the top or bottom cone. A quick search gave me this, but we will have to transform the limits we give to Uniform too.

HWB is weird, but I suspect it may just be a different representation of HSL. In that case one can piggyback on the other. That need to be looked into, though! I'm pretty sure Lch is just a plain cylinder within the Lab cube, so that one is fine. I think the rest that are tristimulus are cubes or blocks and Luma is a line.

There doesn't seem to be a normal distribution currently.

I think I managed to get "normal" and "standard" mixed up in my head. As I wrote above, let's not care about the more fancy distributions for now. I will edit the issue description.

Other use cases

I think those are some nice ideas. They are technically covered by gen_range, but that doesn't mean we can't add shortcuts.

I'll edit the issue description continuously to reflect what we have discussed.

[okaneco]

I misunderstood and was getting caught up in higher level details of using rand, not implementing it 😅. I read more about the traits from rand and understand that the user will be the one interacting with the RNG. I also came across that SO answer which should be helpful.

Thinking about HWB and playing with a color picker, I believe it can be represented the same as the HSV cone in the image above with the white and 100% saturation colors inverted. That is, the most saturated colors are located in the middle of the circle and the outside of the circle is white. Whiteness is the radius component and blackness the height component. Looking at the equations now that makes sense. In that case you might want more samples to be closer to the center of the circle.

H = H
W = (1 - S)V
B = 1 - V

It looks like start with UniformSampler, then SampleUniform, and then (optionally?) SampleBorrow.

The UnitCircle was the simplest example I could find. It doesn't seem that hard to make distributions. I imagine RGB would look something like this.

impl Distribution<Rgb<S, T>> for Uniform<Rgb<S, T>>
where
    S: RgbStandard,
    T: Component,
{
    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Rgb<S, T> {
        let uniform = Uniform::new_inclusive(0., 1.);
        Rgb {
            red: uniform.sample(rng),
            green: uniform.sample(rng),
            blue: uniform.sample(rng),
            standard: PhantomData,
        }
    }
}

It couldn't hurt to have a checklist of all the color types under the Distribution and SampleUniform checkpoints.

Another question I have is how do we test/verify this?

[Ogeon]

It seems like HWB is designed for color pickers, or at least the model doesn't necessarily care how the components are mixed. They can be normalized to still make sense. But I think it clicked for me now. HWB is HSV transformed into the cone shape. The multiplication with V for W is what turns it into a cone. That could mean that we can sample HWB as a cone where W is the inverse of the distance to the center and B is the distance from the base.

It looks like start with UniformSampler, then SampleUniform, and then (optionally?) SampleBorrow.

We will have to create our own samplers (implementing UniformSampler) for the color spaces and use them in the SampleUniform implementations. SampleBorrow is already blanket implemented as impl<Borrowed> SampleBorrow<Borrowed> for Borrowed where Borrowed: SampleUniform, so that one's on the house.

I imagine RGB would look something like this.

Pretty much, but I think rng.gen() will do the trick, despite not being inclusive for floats. I don't know if it's going to be noticeable. Or if the performance difference of having a range or not is noticeable.

It couldn't hurt to have a checklist of all the color types under the Distribution and SampleUniform checkpoints.

I'll add them. 🙂

Another question I have is how do we test/verify this?

Oh, good question. Faking an RNG to give predictable values? We can control the input, so that's an option. At least to verify that the output is correct for some input.

[peteroupc]

For your information, the paper on HWB is:

Smith, A.R. and Lyons, E.R., 1996. HWB—A more intuitive hue-based color model. Journal of Graphics Tools 1(1), pp. 3-17.

According to that paper, HWB is designed to be a more intuitive color model than HSV (which I believe was also invented by Smith), and is not a perception-based model.

[okaneco]

HSV

I was wondering how we could sample HSV as a cone since all the cylinder values are valid. HSV color pickers often offer the option of a hue triangle or cube, so in our case I believe we can sample a 1-1-√2 triangle (with rejection testing) for saturation and value. We'd scale the saturation in proportion to its distance between the height edge of the triangle (value) and the hypotenuse. The hue angle would be 2π * rng.gen().

        saturation (x)
       1 _________
        |       .
value   |     .
 (y)    | o .
        | .
       0          1

I think the saturation for the point o in the diagram would be x / (1 - (1 - V)). We'll need to handle V = 0 to avoid divide by 0. Saturation can be any value at that point since it always results in #000.

HSL

        saturation (x)
           1
            | .
            |   .
            | +   .
            |       .
lightness  0 _________
   (y)      |       .
            | -   .
            |   .
            | .
          -1          1

Extending this to the HSL bicone, I think sampling from -1 to 1 for the height makes sense with 0 to 1 for saturation. If in the negative half, saturation will be roughly the same calculation for scaling HSV. First Lightness might need to be scaled from [-1,0] to [0,1] for saturation calculation then from [-1, 1] to [0,1] for the actual Lightness. If in the positive portion, the equation becomes x / (1 - L) with only needing to scale for the final Lightness from [-1,1] to [0,1]. At Lightness = 50%, saturation does not need to be scaled. At L = 0 and L = 100, saturation can be any value since the resulting color will be black or white, respectively.

Testing/validation

I thought we could make example programs to output images then visually verify the samples looked uniform in a triangle, bicone radius slice/half-section, circle, and square.

[Ogeon]

@peteroupc Thanks! I hadn't seen there was a paper, but will look into it. It may have some useful info.

@okaneco Right, so what we really want to do is not to sample a cone within the HSV space, but warp the probability distribution to give more weight to the parts with higher value. Scaling the probability for some value V with V itself produces that cone shape. I'm basically repeating what you wrote, but I kind of need to formulate it in my own way to get it straight.

If we would sample a triangle, we would get the probability right, as I understand it, but since we have a 3D shape it becomes a cone. If it's not a cone, but a triangular prism, we will get a similar overrepresentation of white and light colors.

We could sample a cone with radius 1 and height 1, similar to your triangle. The SO link suggest calculating the radius (saturation) as r = (b / a) * h * sqrt(random()). a/b can be substituted with 1/1 = 1 in our case, so we are left with r = h * sqrt(random()). This produces a cone with the tip at (0, 0, 0) and the base at (x, y, 1) if z is the height axis. This means we can straight up substitute h with value and r with saturation. To normalize, we have to divide by value (h), which eliminates it from the equation (no divide by 0 🎉), leaving us with saturation = sqrt(random()). Cool!

The result, if I got it correctly, is

hue = 2 * pi * random()
saturation = sqrt(random())
value = random() ** (1/3)

Not too bad.

For HSL, my reasoning is that we have two cones. The probability to end up in either cone is equal, so it's basically if rand.gen() { /* sample upper cone */ } else { /* sample lower cone */ } with some nice transforms of the parameters. For one half lightness = h / 2 and for the other lightness = 1 - h / 2, I think. Hmm, lightness seem to be the only affected component, really, so that's what goes in the if branches, in that case.

[okaneco]

I had to write out the triangle examples to help conceptualize it but the cone math makes a lot more sense now. And yes, HSL seems to boil down to a bool and then the only difference is lightness in the branches. That's really clean and it didn't seem to be so simple yesterday.

And so HWB would look like this. The blackness remains because it stays a cone and we don't normalize to a cylinder.

hue = 2 * pi * random()
whiteness = blackness * sqrt(random())
blackness = random() ** (1/3)

In what manner should we go about PRs for this? Everything seems sorted out conceptually.

[Ogeon]

HWB is still strange to me. Part of me want to go via HSV for that one. They are the same thing, according to the HWB paper:

The RGB color space corresponds to a unit cube, the HSV space to a singly-ended hexagonal cone (a cone of hexagonal cross section), and the HSL to a doubly-ended hexagonal cone [Foley90]. The HWB model is just a recoordinatization of the HSV model, so the HWB color solid is also a singly-ended hexagonal cone, or hexcone.

Also HSV and HSL are apparently hexagonal. 😬

With a slight stretch of the imagination, the HWB color solid is spherical rather than cylindrical. The white point is the center of the “sphere” (hemisphere actually). H is one of the angles, B is the other, and W (actually the complement of W) measures distance along the spherical radius determined by the two “angles.” This hemisphere has a hexagonal cross section and straight sides, however.

😵

That paper has a lot of good info! Thanks again, @peteroupc.

I would suggest starting with one of the easier spaces (like RGB) and get the fundamentals in place, if you or anyone else want to get started with this. I'll keep track of progress with this issue.