### Friday, June 01, 2007

## How many ways can one flatten a cube by unfolding?

*I'm sorry to not be able to bring you a perfect result. Would you mind trying to rephrase your query?*

Well, no I don't think it could be much clearer without becoming much longer and likely more complex. But maybe I should explain why I'm asking, at least in this post if not to Hakia.

Imagine a cube made of lots of little identical cubes: 8, or 27, or some other integer raised to the power 3. For simplicity, let’s call those little cubes “cells” and save “cube” for the big composite one.

Imagine that these cells don’t really have sides, just edges (a lattice framework), so that if you are in one of these cells (floating, or clinging to the frame) you can move into the one below, the one above, or one of the four around the sides...unless, of course,

- you are at a boundary face of the cube so only five faces (those other than the one corresponding to the boundary face of the cube) lead to other cells;
- you are at an edge of the cube, with two adjacent faces of your cell at the boundary of the cube, so four faces lead to other cells;
- you are in a corner of the cube so that only three faces lead to other cells.

To help stay orientated, let's suppose the cells change color in a regular fashion: the higher the redder, greener from left to right, and bluer from back to front (or from "in" to "out"). Looking up, the cell above looks a little redder than the cell currently occupied. To represent the choice of options on a two-dimensional computer screen, how might one unfold, or cut and then unfold, the cube?

Over the past few months, I've found and used three tools for helping choose colors to use on a web page:

- Sortable Color Name Chart, which as its name indicates, provides a bunch of swatches or tiles of color samples which can be sorted according to various criteria (brightness, hue, etc.). Each tile has black text and white text. However, there are no indications of brightness or color contrast, nor possibility to try other text colors (or even colors other than the 200 or so that is shows).
- A second, and much more helpful tool, is Gez Lemon's Color Contrast Analyzer. Here, in an interactive page, one can enter color codes for foreground and background and the tool in the page produces a sample with evaluation of luminosity contrast and color contrast. I used this to help improve the contrast, and legibility, of this blog recently: the title banner is now much darker than the original orange, for instance. The site also provides examples, with their contrast evaluations, of a range of foregrounds for a range of backgrounds. Even better, he offers a Firefox extension to automatically audit and report on the contrasts of most elements of any page!
- Color Scheme Generator 2 proposes sets of colors that "go together" using some color-theoretic algorithms. It provides the user lots of possibilities to choose from: color or colors that provide the basis, and some aspects of contrast. It also provides a color-blindness simulation, so that one who is not color-challenged can get an idea what it would look like to others. Unfortunately, while it does provide this subjective aid, it does not indicate contrast indices nor guarantee that the schemes it produces will meet the Web Content Accessibility Guidelines.

While each serves a purpose, none really enables me to choose pairs of colors I like and which provide enough contrast, although the Color Contrast Analyzer comes pretty close. So, I'm tinkering with a tool that allows one to choose a background color (or perhaps a foreground color), then discover what colors provide sufficient contrast with it (the tool calculates the indices for a range of colors, and only displays samples with those that meet or exceed a threshold) to finally choose a combination one likes.

That is why I am wondering how to represent in 2-D the six adjacent cells one would see while traveling within the RGB cube in my tool's user interface; the color of the currently occupied cell should be represented as well. I have a working prototype, with a layout I find acceptable, but I started wondering about alternatives, and voilà! How many ways can one flatten a cube by unfolding?

Because the faces of a cell are flat, we could simply undo all the seams and show each one as an independent square, arranged in various ways. But this doesn't really help represent the 3-D experience, I don't think. I could be wrong, but I'll only consider cutting the cube into three pairs of sides, two half-cubes of three sides, or a single "bear-skin rug", and not other cuts into unequal numbers of sides. I'm sure I'm not the first to do this, it was probably done by the ancient Greeks, but I don't know where to look it up!

We could suppose that we can look toward two faces at a time by looking toward the seam that joins them. How many ways could we do that? There are twelve edges to a cube, each joining two faces. But how many ways could we take them apart, leaving pairs of adjacent sides joined? Eight:

- U[pward] can be paired with R[ight], L[eft], O[utward], or I[nward] (but not with D[ownward] because they don’t share an edge to begin). Removing U with its partner undo six seams, leaving six. The six undone are
- U’s three seams with the three of {R, L, O, I} left behind,
- its partner’s two with the two adjacent of the three left behind,
- its partner’s one with D.

- Once U is paired, three possibilities remain for D, but only two of them work: we only have six seams left (including D-and-partner) we must have three to join three pairs of faces, so we can only undo three, not four. Pairing D with the middle face of the three remaining would undo four, and leave the two “end” faces unjoined. Hence D must choose one of the two “end” faces.

- Starting with U again, it only has four corners, determining its four possible half-cubes.
- Once a corner with its three faces is removed, the other three meet at the diagonally opposite corner and leave no option.

If we have three faces that share a common corner, we can undo one of the three seams that joins them to flatten them to an “L”. It doesn’t matter which of the three we choose: since each face was joined to the other two, it will still be joined to at least one. So for each of these half-cubes, we have three possible “L”s, preserving two seams. The other half-cube will also preserve two seams. While one could impose a symmetry constraint, so that the choice of seam to undo in one half-cube "matches" the one undone in the other half-cube (its opposite, for instance), that isn’t truly necessary. In general, then, there are three options for each half-cube, nine for the two of them. Thus, we have 36 ways to flatten the cube into pairs of L’s.

And how many ways to skin a cube? I'm not sure yet. To hold the six faces together requires five seams, but not all combinations of five seams will work. For example, consider the set of the four seams which join the four sides plus one of the eight other seams: we'll have a tube with either the top or the bottom attached and the other not! And we have eight ways to do this, and as many for the two equivalent horizontal tubes, eliminating twenty-four cases of the 792 ways of taking five elements from a set of twelve.

An "easy" way is to leave the top and bottom each hinged to a side (not necessarily the same one for both), then undo one of the seams to unroll the tube of sides as a band. Four possibilities for the top-seam, four for the bottom-seam, and four for where to open the "tube": 64 possibilities at least. And the same should be true for each of the two horizontal tubes, I suppose.

For some, but not all of these flattened bands, it is possible to pivot a side sharing a corner with the top (or bottom) to share a seam with it instead of with the band of sides. For example,

T | |||

L | I | R | O |

B |

if "out" (the front face) were to stay attached to "top" rather than to the band, the "skin" becomes

T | O | ||

L | I | R | |

B |

or (same thing on the other end, instead)

T | |||

I | R | O | |

L | B |

or (doing both)

T | O | ||

I | R | ||

L | B |

I'll continue trying to figure this out (or find the answer in some old Greek sand), but not in this post: clearly there are way too many possibilities for any one of them to be "intuitive" or "natural" for my user interface, so I'll probably stick with what I have (which is much like a two-"L" solution with the two facing each other, as if on a circle, with the "current" cell color shown in the middle).

The first link Hakia provided was pretty interesting:

PolyMesh unwrapping and UV mapping While it is mainly about how to use a polymesh editor to unwrap general surfaces, it does unwrap a cube as a simple example. But it doesn't discuss how many ways there are to do so, it just shows one that works to produce a single flat piece. It also indicates

Mesh unfolding is carried out using the ABF++ (Angle Based Fitting) algorithm as published by SHEFFER, LEVY MOGILNITSKY aand BOGOMYAKOV.It seems a "polymesh" is what one obtains when one approximates a three-dimensional surface, which may have curvature, by plates (which are flat) joined by seams. The tool behind this article adds "texture" to such a surface; sort of like taking a bear-skin rug, wall-papering it, then re-shaping it into a stuffed bear. It does so only virtually, for 3-d graphic rendering and animation (I think, but I'm not really familiar with this tool).

Technorati Tags: geometry, combinatorics, color, graphics, Hakia

contrast

Powered by ScribeFire.

Stumble It!