Preserving rate of change while changing dimensionality

October 15, 2011

Idea

This topic originally became of interest to me when designing the website's background color, which I decided should be dynamically based on unix epoch time (seconds since 1971). This would allow the color to change evenly across the entire website without any other fancy workarounds.

The above problem, rephrased in mathematical terms, would be a mapping of an integer (one dimensional vector) with infinite domain (time value will increase every second, effectively no upper bound) to a 3d vector (color with R, G, B components) in a finite space (each of the R, G, B values can only be 0-255). This is in fact an easy task, since the latter is a finite space. The total number of available colors is 256*256*256 = 16,777,216. All we have to do for the mapping is take the modulus of the current time, base 16777216, stored in a 32-bit integer, and assign the least-significant 8 bits to R, next significant 8 bits to G, and next significant 8 bits to B.

This is a viable approach, but aesthetically it is not the best choice. Why? Notice that blue is represented by the most significant 8 bits. That means it will take 256*256 = 65536 time units for blue to change by one unit, while red changes every 1 time unit. In other words, the user will see a very large amount of red-color change, but very little in blue-color change. There will be entire long periods in which blue remains visually constant, while red and to a lesser extent green are changing all the time. Another big problem is that with this approach the color value drops to zero immediately after reaching its maximum value (1677215 mod 1677216 = all colors 255, 1677216 mod 1677216 = all colors 0) for every color, meaning there will be plenty of large and very visible changes in color. This was something I wanted to avoid, so that the website contents could be read without even noticing the background color changing. For instance, before blue changes by 1 unit the user will have seen 255 sudden changes in red and 1 sudden change in green. Not good.

Out of this, arises the question of how to make the mapping so it is smooth (let's say, no single color changes by more than 1 unit for every change of 1 in time units) and has an even spread of color changes? This is easily done by limiting the mapping range, so instead of mapping a time to any possible color, the time can only be mapped to color combinations that have a sum of 255 units, and at least one unit equal to 0. For instance, (0,0,255) or (100,155,0) are valid while (1,50,0) or (1,134,20) are not. Then, the result of (floor(time/255) mod 3) determines which 2 of the three colors are chosen (0=R,G; 1=G,B; 2=B,R). Next, the time is taken mod 255, where 0 means (the first color in the pair is 255 while second is 0) and 254 means (the first color in the pair is 1 while second is 254). This approach transfers the sum of 255, smoothly and evenly, between any two of the three colors. This is actually the approach I ended up using in the website background code (with color range modified for better visual appearance).

However, the significant limitation of this approach is that it is not a true three-dimensional mapping. It is in fact a two-dimensional mapping, with the two dimensions being varied over time. Even in the two dimensions, it is not a full mapping, since it only covers combinations of two colors of sum 255, not every possible two-color combination. From the original question, I hoped to formulate a mapping to cover the full range of colors, that is a full three-dimensional mapping, with smooth changes and even spread of changes. Is this even possible?

Problem

Create a mapping from an infinite 1-dimensional vector [a] to a finite 3-dimensional space [x y z] (say M(a)=[x y z]) where the maximum values of x, y, and z are equal and (a, x, y, z are integers). The mapping must satisfy the following:

  1. da is equal to one of (dx dy dz) while the other 2 are zero (smooth color change - exactly one variable changes by one unit for a change of 1 in the time unit)
  2. the mapping sequence created by contiguous values of a between astart=b+cn and aend=b+(c+1)n for a constant value of b and any value of c (b and c are integers), where n is the number of all unique values of [x y z], contains no repeat values of [x y z] (that is, every possible value of [x y z] is visited exactly once before the cycle repeats)  
  3. all valid combinations of [x y z] are covered by the mapping  for contiguous values of a between (inclusive) astart and aend from condition 2
  4. the average rates of change for x y and z are all equal (even spread of color change) for the mapping of contiguous values of a between astart and aend from condition 2

Solution

To me this looked pretty formidable, so I decided to start with a reduced set of specifications, changing the mapping to a 1-dimensional one (and with a much smaller range than 255).

1 Dimension

This is quite easy, but not as easy as taking the modulus because that would not satisfy the first condition. Modulus base n gives values from 0 to n, each value increasing and then dropping to zero. If we graph y=x mod 5, the graph will look like: | / / / / This could be made smooth by changing the second half of each line to a downward slope, so the graph would have range of only 0 to .5n but would be smooth. To accomplish that, we need to use the abs function, which returns the absolute value of an input. Then the transformation is given by y=abs(.5n-(x mod n)). For n=6 and x=[0 to 10] this would give  y=abs(3-(x mod 6))  
x=[0 1 2 3 4 5 6 7 8 9 10]
y=[3 2 1 0 1 2 3 2 1 0 1]
This clearly satisfies the condition for smoothness, since the maximum (in fact, only) change between any two contiguous entries is 1.

So that was easy enough. Let's move on to two dimensions.

2 Dimensions

To keep this reasonable, assume minimum value is [x y] = [0 0] and maximum is [3 3] as above. First, ignore the fourth condition and find all possible combinations that satisfy the first. Starting with [0 0] the next color after a change can be either [1 0] or [0 1] since 0 is the lower bound. When this analysis is extended, a layout like the one below emerges:

[0 0] - [1 0] - [2 0] - [3 0]
[0 1] - [1 1] - [2 1] - [3 1]
[0 2] - [1 2] - [2 2] - [3 2]
[0 3] - [1 3] - [2 3] - [3 3]

Where the allowed moves are one row up/down or one column left/right. If the goal is to cover all combinations in the graph (condition 3) moving only by one row or column at a time, it is certainly possible to do. However, taking condition 2 into effect the problem becomes slightly more involved. Now it is a  Hamiltonian path problem. I could not find a theorem to prove definitively that a graph like this has a Hamiltonian path (most likely it doesn't yet exist? There are lots of reports of using computational algorithms to solve similar problems). However, by visual observation it is evident that a Hamiltonian path exists from [0 0] to [3 0] and from [0 0] to [0 3]. Thus, if another row and vector are added to increase the maximum bound to [4 4] the Hamiltonian path can easily be extended to either [0 4] or [4 0] respectively. Thus by induction, all graphs of this nature (of a square shape, that is maximum value of x is same as maximum value of y) have a Hamiltonian path and condition 2 is satisfied. (Note that a Hamiltonian cycle from [0 0] to [3 3] does not exist, but it is adequate that one exists from [0 0] to [0 3] since the next cycle can be from [0 3] to [3 3] and so on).

Now we move on to condition 4. Note that x changes as we move across columns, and y changes as we move down/up rows. Condition 4 in other words states that the number of row moves must equal the number of column moves in a single cycle. One cycle found previously was from [0 0] to [0 3]. One way to do this is go across the row [0 0] to [3 0], then down to [3 1] and back left to [0 1], down to [0 2] and over to [3 2], finally down to [3 3] and left to [0 3]. As a result, there are 3 row changes, [3 0] to [3 1], [0 1] to [0 2], and [3 2] to [3 3]. However, there are 12 column changes as you can see. The sum is 15, so clearly there is no way to divide it evenly between x and y. The closest theoretical combination is (7 8), and as evident by observation this is indeed possible. The cycle traverses the vertices in this order: [0 0] [1 0] [1 1] [0 1] [0 2] [1 2] [2 2] [2 1] [2 0] [3 0] [3 1] [3 2] [3 3] [2 3] [1 3] [0 3].

However, for even values of maximum [x y], a perfectly split rate of change is possible. This is evident since the Hamiltonian cycle must have n-1 edges. For max [x y] = [3 3] as in above graph n=4*4=16 and n-1=15. For max [x y] = [4 4], n=5*5=25 and n-1=24=12*2. Continuing the above pattern, it is possible to create a cycle that has 12 changes in row and 12 changes in column, as the reader may see by observation. This is another case of induction that proves that for all values of max [x y] such that x=y, either an almost-even or perfectly even split of changes in x and in y can be attained in two dimensions. This completes our analysis of the two-dimensional case, with the verdict that a mapping satisfying all of the conditions is attainable.

3 Dimensions

Now we apply a similar analysis to a three-dimensional space [x y z]. Again ignoring condition 3, we find that there is no easy way to draw the three-dimensional graph that results. Using a computer for assistance, the following 3d graph for combinations of [x y z] from [0 0 0] to [3 3 3] is obtained:

It is in fact multiple cubes put face-to-face to form a large cube (not sure if there is a name for this pattern). Clearly a Hamiltonian path can be constructed between some points in this graph, extending the analysis above. However, checking that condition 4 is satisfied becomes too difficult to solve by simple observation. First, we check if the length of a potential Hamiltonian path can be divided by three (that is, if condition 4 may theoretically be satisfied, without knowing definitively whether it is satisfied). The Hamiltonian path length is always n-1, where n is the number of vertices. for max [x y z]=[1 1 1], the number of vertices is 2*2*2=8 and path length is 7, clearly not divisible by 3. Continuing to [2 2 2], 3^3=27 and 26 is not divisible by 3..
4^3-1=63 is divisible by 3
5^3-1=124 is not divisible by 3
6^3-1=215 is not divisible by 3
7^3-1=342 is divisible by 3

Continuing the pattern, it is evident that for n=1 mod 3 a Hamiltonian path MAY exist. Since n=1 is not relevant, the smallest pattern that can be analyzed for a Hamiltonian cycle satisfying condition 3 is 4x4x4 units, or max [x y z] = [3 3 3]. Conveniently, 255 mod 3 = 0 and 256 mod 3 = 1, so it IS POSSIBLE for a mapping that satisfies the four above conditions exists in three dimensions for the RGB color scheme!

However, I currently do not have the time/resources to analyze the above cases for the existence of a valid Hamiltonian path. This was why I used the inferior two-color scheme listed above for the actual website background. If I have time to definitively analyze this I will update the page (and who knows, maybe the background script).