Monday, 5 August 2013

Mental Block: A Summary

Mental Block is an interactive work of art that I (George van den Driessche) designed and built for Nowhere 2013. Its seven pieces can be assembled into a 1.2m cube, or into a multitude of other shapes. There are ten large square images hidden in the work; each can be revealed by building a cube in a different way. The seven pieces are also a good size for sitting on!





The full photo album from the event is here.

Timeline

The project was carried out in my spare time. Overall, it involved about six months of programming, planning and modelling, followed by three months of construction.

  • October: Discovered the Soma cube. Wrote a computer program to enumerate its solutions.

  • November: Improved program performance and rewrote it in other languages to see how it came out.
  • January: Added code to export a 3D animation of the solutions to Blender. Uploaded a simple animation to YouTube.

  • February: Used a constraint solver to discover that a single Soma cube can contain ten whole square faces (though obviously they can't all be displayed at once).
  • March: Realised I could build a giant Soma cube and paint it. Submitted an application for an art grant for Nowhere.
  • April: Learned that my art grant application was successful. Acquired plywood, and built a small test cube to learn how to build the full thing.
  • May: Experimented with feet and corners for the cube. Cut all the large parts of plywood. Made some more models in Blender and uploaded a Sketchfab model of one of them.


  • June: Built all of the pieces of the giant cube. Undercoated them all, and designed a way to project images vertically from a laptop, for painting the sides.
  • July: Finished painting and varnishing the cube. Took it to Nowhere and finally assembled it. Brought it back from Nowhere.



Materials

  • 21msq 9mm spruce plywood
  • 32m 34mm frame timber
  • 2000 1.25" countersunk woodscrews
  • 500 rubber flight case feet
  • 500 1.25" round-headed screws
  • 2.5l white undercoat
  • 2.5l floor varnish
  • Various acrylic paints

Things that worked well


  • Modelling the more complicated pieces in Blender gave me confidence that I could build the structure correctly.
  • I structured the work so that if I ran out of time, I'd still have something I could present.
  • The pieces were as weatherproof as they needed to be.
  • The pieces have not suffered too much damage, even though I decided not to add corner protectors.
  • Using a spreadsheet to manage my cut lists meant I used the frame timber with over 98% efficiency.
  • I kept good financial records.

Things that didn't work so well


  • I didn't have time to fit EL wire edges to the pieces.
  • The tarpaulin that was supposed to protect the work from storms was instead ripped up by the storms.
  • The lights I'd ordered didn't arrive on time, so I had to pick up some more expensive equivalents at short notice.
  • I made one mistake in the painting of the sides.

Things learned (and relearned)


  • Timber merchants don't know how much their timber weighs, because their customers almost never care.
  • How to use a mitre saw, a skill saw, and a jigsaw.
  • What IP65 means.
  • How to wire Ceeform plugs.
  • Having a system is much more important than having the best system.
  • Power tools are amazing.
  • People like to build tall things, and will go to great lengths to build the tallest things they can.
  • Friends will happily lend a hand when the need arises.


Saturday, 27 July 2013

Done and Heavily Dusted

It worked! The moment of truth was when we put all the painted and varnished pieces together, and put all the feet on. They stacked just fine.



It was possible to build a complete face of the cube before we'd finished putting all the pieces together, so of course the first thing to do was to show that it was safe to stand on the result.



Over the course of the week, people did use the cube in all the ways I had hoped they would. They solved the cube to reveal the different designs (the smiley face being very popular). They used the pieces as seats. And they built unlikely edifices that I had never imagined.





The woodwork lasted the whole week with only small amounts of damage, despite my decision not to bother protecting the corners. And the paint and varnish also survived well. The tarpaulin that was supposed to protect the work from weather was torn apart on Wednesday night in the first thunderstorm, but that just showed that the tarpaulin wasn't necessary.

I found I'd only made one mistake, which was annoying but not enormously important: I had painted one side of one of the seven pieces upside down. The side formed part of the Nowhere logo, which meant that it wasn't possible to make a cube with that logo on the side. (It was still possible to complete the logo, but the pieces didn't then form a cube.) The other nine faces worked perfectly.
More photos are in a Google+ photo album and a Facebook photo album – whichever you prefer.

I can just about remember the beginning of this year, when this project was nothing more than a vague intention. It would never have become a reality without the help of a great many people in various ways. So, here are the people who made it happen:

Construction crew: "Freddie" (Mike), Bianca
Power tools training: "Freddie" (Mike)
Painting and varnishing: Lexy, Charlotte, Tom and Kate, Vic
Transport: my parents
Moral support: the Nowhere art crew (especially Camille); other nobodies (including Lexy, Bill, Rich, Joyce, Bambi, Hilda, Pauly, Nancy); my family; my Google ex-team (John, Natalie, Kyle)
Maths: the members of the Google math mailing list
Emergency tools: Pauly
Emergency beer: Asierr
Funding: everyone who bought a Nowhere ticket

You're all amazing. Thank you!

Tuesday, 25 June 2013

Build Complete; Painting ...

 Last week, as expected, I finished building the last of the pieces of the giant Soma cube. (I'd predicted a Thursday finish, but it turned out to be Friday. Not too bad, though.)
Piece Y was fun to build because, in spite of being made of square shapes, it has rotational symmetry of order three around a diagonal axis. For the same reason, it has a good strong corner shape from which to reckon right-angles. I took a little longer over it than I had planned because I wanted to do it justice, and it did come out very nice and square.
So this is what all the sides of all the pieces look like. There are ... quite a lot of them!

On Sunday I bought a handful of paints to experiment with colours and textures. I confirmed that undercoat/primer is definitely going to be worthwhile, as is a quick sanding once that's applied.

Yesterday I sorted the convex sides into the ten cube faces to which they belong, ready for painting. I also bought enough undercoat for the entire job. Mike very kindly did the first layer of undercoat, and took only 90 minutes, which was encouraging.

The last thing I did on Monday was to cobble together a crude frame for holding a projector vertically at ceiling height. The shelves have holes in them, that were originally going to accommodate rods supporting the lowest shelves. Those rods turned out not to be necessary, but the holes have found a new purpose: the frame is held on by just two dowel pins that fit into those holes.

With the projector pointing downwards from a height of over 2.5 metres, I can lay out each cube face on the floor and project its design onto it, which should make it easy to produce large-scale imagery. The frame took under an hour to build, and should save many times that. 
Today all the convex faces got a gentle sanding and then their second undercoat. Here they are, drying. I realised that if I put a screw part-way into a carefully chosen screw-hole on each face then that could be used to prop the faces a good distance apart.

Also I finished rigging the projector with power and signal. Amazingly, from ceiling height it produces an image on the floor that's 1.22m tall – exactly the size it needs to be. So that's one advantage of living in a place with high ceilings.

Monday, 17 June 2013

Still Building

A week after my last post, I've finished four out of seven pieces of giant Soma cube, and am half-way through the fifth. The first four were all comparatively simple: because they are essentially flat shapes, I could attach most of the frame to the two large sides, then join it all together with simple rectangles. The fifth (piece P) is more complicated. There's no obvious order in which to put it together, and it needs screws at some less accessible angles.
 To cap it all, this piece is more likely than others to suffer odd tension forces, so I decided to put a long coach bolt through the central joint. Working out how to dril the hole for that accurately enough was a novel task.
Once I'd finished assembling piece P, I put cube X on it to get an idea of how the pieces will look when fitted together. I'm happy with the result. As you can see, the pieces are built slightly smaller than the ideal mathematical cubes that they represent, leaving a gap that is just large enough for the feet that will eventually be on every side.

After I've finished gluing piece P together, the next piece will be Q which is the mirror image of P. And then after that, only Y will be left. I've been timing my work with a stopwatch app, and I reckon there are about 20 hours of construction work left. So the basic construction should be complete by Thursday.








Sunday, 9 June 2013

Under Construction

Piece R in progress
I've started building proper cube pieces. It's taking a lot of measuring, double-checking, and Pythagoras' theorem to make sure the pieces don't end up too warped. I suppose the process would be less laborious if I had been able to cut the faces and frames to higher precision.

Roughly speaking, the steps to build each piece are:
  • Collect all the parts required.
  • For each length of frame:
    • Clamp it onto the side to which it will be glued.
    • Drill pilot holes for all the screws it will need.
    • Secure it temporarily with just two screws.
  • Fit the faces together, and add more pilot holes and again secure with two more screws on each edge. This is the step where the alignment of the holes can be fine tuned, to help keep the faces flat.
  • Number the faces on the inside, and also mark which other faces they are adjacent to, for easy reassembly on site.
  • Drill pilot holes for all the feet.
  • Remove the second set of temporary screws.
  • For each side:
    • Label the corners with letters on the inside, and label the ends of the frame with the same corner letters.
    • Remove the first set of temporary screws, to release all the lengths of frame.
    • Countersink all the pilot holes.
    • For each length of frame:
      • Glue it onto the side, and secure it permanently with all the screws it will need.
Preliminary construction of piece S
I weighed piece S after assembling it. It is 16.7kg, which is about what I was expecting. One person can lift it, but it would definitely be more fun for two people.

Gluing the frame onto one side
Meanwhile, I did a bit more work on the maths. I found that, by adding variables that model how much of each solution face appears on the outside of each solution, I can use the same integer constraint solver as before to discover a set of ten solution faces where solving for one face doesn't nearly reconstruct any of the other faces. This required 360,000 constraints and I wasn't sure the solver would be able to deal with that. But it turned up an answer in only 30 seconds ... in spite of being single-threaded.

Back in the physical world, I still need to work out how to varnish and paint the thing. The wood is very absorbent, so it could probably use a coat of varnish before painting with acrylic or similar.

If you've got any recommendations, let me know.

Ready for decoration







Tuesday, 14 May 2013

I need your help

Okay, lovely people, it's time to think about painting, and I need your input.

As you perhaps know, I'm building a giant Soma cube to take to Nowhere in July. There are 240 different ways to put its seven pieces together to form a cube.

And I've discovered (by using mathematics!) that though a cube, of course, has six faces, it is possible to choose one complete square face from each of ten different solutions of the cube such that none of the ten chosen square faces share any of the faces of the pieces that compose them.

In other words, if you gave me ten different square pictures, I could carefully paint the pieces of the cube so that, if you solved the cube one way, you'd get one of the pictures, and if you solved it another way, you'd get a different picture, and so on. The cube would secretly have ten faces!

So I want you to help me choose ten different square pictures, so I can decorate the cube like that. Here's the spec:

Themes

One face will be reserved for a Nowhere logo. The other nine designs are to reflect different aspects of life that conflict with each other or compete for attention ... something like:

  1. Family
  2. Friends
  3. Work
  4. Rest
  5. Travel
  6. Home
  7. Your topic here!
  8. Your topic here!
  9. Your topic here!

Style

Each design should be bold and simple. That way, it will be easy to see even in dusty conditions. Also it will mean even a software engineer can understand it. Think icons, traffic signs, special symbols in typefaces (♥¸ ☺, &, ☢, ♜, ⚥) and so on.

 The finished cube will be 1.2 metres on a side, but there will be some narrow gaps between the pieces. Each face is made of nine smaller square faces. Ideally, each design should cover all nine of the smaller squares that compose it.

What you should do next

  • Open the face template that shows, in proportion, how one square face will be made up. Print out a few copies and put them on your desk or wherever. See what you can fill them with. Maybe doodle on them when you're on the phone or bored. Photograph or scan the results, and share them with the +Soma Cube, or send them to nowherecube@gmail.com.
  • Think about the things in your life that you wish would add up, but which don't. Do you love the sunshine, but know that only one rainy city will ever be truly home to you? Do you love burning things, but worry about your carbon footprint? Share your thoughts with the +Soma Cube or send them to nowherecube@gmail.com.
What's in it for you, beyond fame and glory? Something, I promise ... but I'm not saying what yet.


Monday, 13 May 2013

Making Faces

I spent most of the May Day bank holiday cutting cube piece faces. I've now finished all the large pieces, which also means I've finished all the difficult concave cuts.


I learned a couple of industrial economics facts from this.

The first is that, even on small-scale production of things such as the nine identical L-shaped faces I needed to make, it pays to specialise. That is to say, it's faster to do the first cut of all nine, then the second cut of all nine, and so on, than it is to do all the cuts of the first face, then all the cuts of the second face, and so on. That's because setting everything up for each kind of cut takes time, and doing different cuts one after another also makes me likely to forget where in the room I left the various tools.

The second thing I noticed is that, because working more efficiently allows me to do the same amount of work in a shorter time, it also means I'm doing more physical activity per unit time. So one symptom of increased productivity is more sweat. (In my normal line of work, the extra 'sweat' from increased efficiency is experienced by a data centre, so I don't notice it so much.)

I wasn't entirely sure that I'd get the cuts for the more complicated pieces right, so I made models of them in Blender. (I tried Sketchup first and found it fiddly and surprisingly buggy. Blender has been harder to figure out but I found it very slick once I discovered how to use snap-to-face.)

Here's one of my models on Sketchfab. Unfortunately that site doesn't do animation yet so you can't see how all the pieces are going to go together or what the inside looks like.

Now there are lots of boring square and squarish pieces left — 37 of them, to be precise. I can make it interesting by working out how to cut more than one of them at once without sacrificing precision.

Aside from that, I need to acquire and start cutting the wood for the frame. 34x34mm timber is readily available and will certainly be solid enough, but is a bit heavier than I'd like. I suspect I could get away with something slenderer than that, but I can't find anyone selling smaller square cross sections.

Thursday, 2 May 2013

Further Feet


Following on from my last foot-finding foray, I've done some more experiments. It's possible to cut a tennis ball in half in a zigzag sort of way, so that the halves each fit neatly on a cube corner. There are four downsides of using tennis balls, though:

  • They're really difficult to cut in half;
  • The hair falls off them (especially along the cut) and gets everywhere;
  • They have a second-hand value, so they're cheap rather than free;
  • They're quite bulky.
So I'm not convinced that tennis balls are a good solution.

I also tried cutting bicycle tyre into pieces that fit better on a corner. The previous design for this used three separate strips for each corner; unless constructed very cleverly, it's likely to open up along the diagonal and not protect the corner as well as it could. This new design uses only one piece but stays over the corner better.

The prototype is similar in shape to the sort of sticking plaster that is designed to go on an elbow – for similar reasons. The only downside of it is that it doesn't have the same rotational symmetry that the earlier tyre-based design had. However, I think a final design could be more equilateral in shape.

It would be useful to work out a way to use a template to cut the pieces of tyre accurately and quickly. I doubt that jig saws work on rubber.

Monday, 29 April 2013

Cube X Grows Feet

Machine feet
I've been wondering for a long time how to make the corners of the cube pieces of the giant Soma cube for Nowhere. There needs to be some separation between the faces, so that they don't scrape against each other. There also needs to be some sort of protection of the corners themselves.

I have already built a small test cube for working out things like this, so I have been experimenting on that.

I found a company that sells machine feet and ball corners. The feet work well and even look okay, but at £5 for 12 I'd be looking at £200 worth of feet! Even buying in bulk from China, it looks like £100. Meanwhile, the ball corners looked surprisingly ugly, were slightly too small, and weren't really round enough to stop one cube piece damaging another.

Prototype tyre-based corner
My plan B was to cut up some used car tyres and nail them onto the corners. Yesterday I went looking for tyres. Tyre shops aren't open on Sundays, but I found a stack of moribund tyres outside one and that was enough to realise that they'd be far too big and heavy for this purpose. Then it dawned on me that I should have been thinking about bicycle tyres all along. And, what's more, Get a Grip Bicycle Workshop is open on Sundays. So I walked over there, picked up a bunch of old tyres and spent the afternoon cutting them up. The result is promising.


I can get about 40 strips out of each tyre. I'll need about 500 strips in total. But I've made a jig to help cut the strips, so it should only take 2-3 hours to cut all of them. It'd be even faster if I had some sort of shears or guillotine suitable for cutting rubber.

The strips of each corner can be glued together with rubber cement. Once fabricated, the completed corners can be left unattached where necessary, to permit disassembly and final assembly on site.

Monday, 22 April 2013

The Birth of Cube X

It's been a while (over seven weeks, in fact) since I noted that I'd proposed to build and paint a giant Soma cube for Nowhere. And the reason is: I got a grant for it! So I've been working on realising this thing.

Each piece of the full-size cube is made of three or four small cubes. The pieces need to be affordable, light enough to lift, and yet strong enough for excited people to climb on. They should also be relatively environmentally friendly, and suitable for flat packing for ease of transport. I started researching plywood.

It wasn't easy to find out which wood to use for the faces. Timber merchants sell almost exclusively to builders, who just want cheap wood at known sizes with known structural properties. So, I learned, they generally don't know how much a sheet of any given material weighs, and look at you funny down the phone line when you ask. Three different suppliers gave me three different figures for the density of the same product.

I wanted to build a prototype to see whether my choice of materials would work, before throwing time and money at building the full project. (I had meant to make two prototypes, in fact: one for each of two possible choices of wood for the faces, to see which worked better. That plan was abandoned when I learned that no timber merchant actually stocked the plywood that I suspected would be the better choice – given the lead time they quoted, I'd only be able to make a single order.) Since I'd named the pieces of the Soma cube after letters of the alphabet, the prototype would be called Cube X.

120kg of plywood, in thirds of sheets. Joy
The wood for all the faces arrived one Wednesday, at the same time as a severe migraine. Luckily I'd had the timber merchant cut the sheets into thirds to make them less cumbersome. I lugged 120kg of plywood into the building without being sick, but left it at the foot of the stairwell till I felt better. Later, Mike helped carry it all upstairs.

Each third of a sheet is enough to make six small cube faces, so the prototype would only need one of those thirds. For the frame, I picked up some off-cuts from a Brixton-based burner who answered my ad.

How to McGyver a skill saw onto a vacuum cleaner
On Saturday, I set about cutting. But first I needed something to connect the skill saw exhaust to the vacuum cleaner. Mike suggested fashioning an adapter out of an empty tonic water bottle. I didn't think it would work but, in the absence of better suggestions, gave it a go. Once we'd filed down the thread on the top, it worked amazingly well.

One prototype's worth of wood
Setting up the workbench and some templates for efficient output was interesting and time-consuming. But it won't need to be worked out again. By mid-afternoon, I'd cut all the parts I needed (and learned a lot about how to control the tools along the way).

Next, I made a template to help get screw-holes in the right places quickly and accurately. This is important because the full project needs almost 2000 screws! But other than that, I tried to cut as many corners as possible – I don't want to over-engineer the thing because time is precious, so I wanted to see how little I could get away with.

I had already guessed that it would be sensible to label the insides of all the faces to show how they go together. Doing this means the faces only need to fit together in one way (i.e. they don't need to be interchangeable) which in turn allows me to be a lot less precise about the location of screw holes.

Another thing I learned is that it'll be good to have a scheme for discreetly labeling the outsides of the pieces' faces, to indicate the order in which they should be removed when dismantling them. Arabic numerals are probably best (Roman numerals are useless – they look like accidental marks, and even if circled they look confusingly like 1 and 11). So that means I should use a different sequence to name the faces on the inside.

It probably took me 45 minutes to assemble the complete thing.

So, without further ado, here's Cube X in all its glory. It's 400mm on a side, weighs about 7kg, of which half is the faces and half is the frame. (I'll need the production frame to be a bit lighter.) It has 96 screws in it. It doesn't mind if I jump up and down on it.
Cube X
Next, I need to get hold of more wood for the frame – about 30x30mm should be right. I'll need about 100m of it! Also, I have some Cunning Plans for making bumpers to prevent the pieces from damaging each other. And meanwhile I can carry on producing the faces of all the pieces.

Friday, 1 March 2013

Now We Play the (Somewhat Nervous) Waiting Game!

Eek! I've just finished submitting an art grant application for Nowhere this year! If it's successful, I'll be building the cube In Real Life on a large scale (1.5m on a side, I hope) and taking it to Spain.

Larry Page likes to use the phrase "uncomfortably excited" to describe his feelings about projects that are so ambitious that it's not obvious whether they're achievable. I'm reasonably sure this project is achievable, but I'm still feeling that way ...

Saturday, 16 February 2013

Counting to Ten

Earlier I worked out how to fit ten square faces into a single Soma cube. I've now also finished the logic for working out how to assemble and dismantle a particular solution of the cube. It turned out not to be too complicated. And the code for incorporating that into the resulting animation wasn't too tricky either. So, as promised, here's the video:


That is all.

Friday, 15 February 2013

A Ten-Faced Cube

It's been a busy couple of weeks. Among other things, I investigated how many distinct solution faces can be encoded in a single Soma cube. The answer turns out to be ten – the theoretical maximum – which is a surprising result and perhaps even a new one. A little help from Google's math mailing list helped me find that very quickly.

I also:
  • stripped out the custom Recipe representation in favour of a more general one built on Data.Vect;
  • built most of a representation of 128-bit words;
  • finished code for correct assignment of UV coordinates to shape faces, and added those UV coordinates to Haskell export and Python import;
  • split the cube face materials into their own Blender library and added scripts to automate their generation.
Excluding comments, the source code current stands at 747 lines of Haskell and 235 lines of Python.

Next, I want to beautify the animation a bit, and then I'll produce another video. In the mean time, here's a big chunk of new code, which computes the tenfold encoding and the corresponding UV coordinates.

> module Stats where

> import Control.Monad
> import Data.Bits
> import Data.Function
> import Data.List
> import Data.Map ((!))
> import qualified Data.Map as Map
> import Data.Maybe
> import Data.Monoid
> import Data.Ord
> import Data.Vect hiding (transpose)
> import Data.Word

> import Cube hiding (main)
> import Mesh hiding (testMeshes)
> import Misc
> import Word128

This counts how many squares cover the surface of a shape in the Soma cube.

A less brute-force way to arrive at the same numbers would be to see that:
  • each shape can be built up by starting with a single cube, and sticking successive cubes on by a single face;
  • the initial cube has six faces;
  • each subsequent cube adds four more faces (it brings six faces into play, but one of its own and one of the existing ones are stuck together and hidden). So, the six four-cube shapes must all have 6 + 3 × 4 = 18 faces, and the one three-cube shape must have 6 + 2 × 4 = 14 faces.
> countFaces = length . allFaces . defaultForm

That makes 122 faces in total. (In any solution, only 6 × 9 = 54 faces can go on the outside, so the other 68 must be inside the cube, in 34 pairs of adjacent faces.)

> totalFaces = sum [countFaces shape | shape <- enumFrom L]

The following defines an offset into a bitfield at which to find the bits for each face. Since there are 122 of them, they pack neatly into 128 bits.

> shapeBitOffset = Map.fromList $ foldl reserveBits [] (enumFrom L)
>  where
>   reserveBits [] shape = [(shape, 0)]
>   reserveBits os@((shape', o):_) shape = (shape, o + countFaces shape'):os

Given a predicate that selects faces of shapes, the corresponding subset of faces can be represented as 128 bits.

> markingsAsBits :: [(Shape, [Bool])] -> Word128
> markingsAsBits markings = foldl setBit (fromInteger 0) bitsToSet
>  where
>   bitsForShape (shape, marking) = [shapeBitOffset!shape + i |
>                                    (i, marked) <- zip [0..] marking,
>                                    marked]
>   bitsToSet = concatMap bitsForShape markings

> mapFaces :: (a -> b) -> [(Shape, [a])] -> [(Shape, [b])]
> mapFaces f = map (\(shape, faces) -> (shape, map f faces))

> markFaces :: (a -> Bool) -> [(Shape, [a])] -> Word128
> markFaces f = markingsAsBits . mapFaces f

'paintings' takes a solution and lists, for each shape, how the shape's faces would be coloured by that solution.

> paintings :: Solution -> [(Shape, [FacePaint])]
> paintings solution = [(shape, map snd faces) |
>                       (shape, (_, faces)) <- allMeshes solution]

Now there's enough information to work out how many of the shapes' faces are ever on the outside of the cube:

> totalEverExternalFaces = popCount everExternalBits
>  where
>   everExternalBits = foldr1 (.|.) [markFaces (isJust . cubeFace) $
>                                    paintings s | s <- solutions' RotationOnly]

This reveals that 90 of the 122 faces are ever on the outside. Since each face of a solution requires 9 faces of a shape, that means there is a theoretical limit of 90/9 = 10 disjoint solution faces that can simultaneously be assigned to the faces of the pieces.

Obviously, six disjoint solution faces can be simultaneously assigned to the faces of the pieces, just by choosing all the solution faces from the same solution. But that's not very interesting. The interesting problem is to have as many solution faces represented as possible, but where each one comes from a different solution.

In other words, the aim is to find as large a set of solutions as possible, such that there is some choice of one face from each solution having the property that the chosen faces all occupy disjoint sets of piece faces.

This function takes an assignment of cube faces to shape faces, and splits it into a separate list describing, for each cube face, which shape faces it comprises.

> explodePainting :: [(Shape, [FacePaint])] -> [(CubeFace, [(Shape, [Bool])])]
> explodePainting p = [(cf, filterPaint cf p) |
>                      cf <- [CubeFace sign axis |
>                             sign <- [Negative, Positive],
>                             axis <- enumFrom X]]
>  where
>   filterPaint cf shapePaints = [(shape, [match cf fp | fp <- facePaints]) |
>                                 (shape, facePaints) <- shapePaints]
>   match cf (FacePaint cf') = (Just cf == cf')

Applying that splitting function to the face assignments of each solution in turn results in the following function. It produces a list of 6 × 480 = 2880 elements.

> faceInfos :: [((Solution, Int), CubeFace, Word128, [(Shape, [Bool])])]
> faceInfos = [((solution, n), cf, markingsAsBits fs, fs) |
>               (solution, n) <- zip (solutions' RotationOnly) [0..],
>               (cf, fs) <- explodePainting (paintings solution)]
> solutionIndex ((_, n), _, _, _) = n
> bitRep        (_,      _, w, _) = w

Of course, there's some chance that a cube face from one solution will cover exactly the same shape faces as a cube face from another solution (albeit probably with different orientations). Ideally, a set of cube faces would not contain any cube face that is also formed by a different solution.

> distinctFaceInfos = nubBy ((==) `on` bitRep) faceInfos

This reveals that there are only 1176 distinct cube faces. And even fewer will appear on only one solution. That's unsurprising in fact, because while symmetries of individual shapes are discounted, it's often the case that a solution will contain a subunit comprising two or more shapes, where the subunit has a symmetry. In such a solution, the subunit can be removed, transformed by its symmetry, and recombined, to give a new solution; any cube faces not affected by this will then be shared between the two solutions.

> groupedFaces = groupSortBy bitRep faceInfos
> faceFreq = histogram groupSizes
>  where
>   groupSizes = map length groupedFaces

The above function produces this histogram: [(1,619),(2,258),(3,104),(4,72),(5,39),(6,19),(7,22),(8,6),(9,6),(10,7), (11,2),(12,1),(13,4),(14,2),(15,1),(16,2),(18,2),(20,2),(25,1),(28,2), (30,2),(38,1),(46,1),(48,1)]

That is to say, there are 619 cube faces that can only be made by a single solution; there are 258 cube faces that can each only be made by two solutions, and so on ... up to one cube face that appears in 48 different solutions and another that appears in 46.

Here are the solution faces that appear only in a single solution:

> interestingFaceInfos = concat [g | g <- groupedFaces, length g == 1]

These can then be grouped by which solution they appear in:

> interestingSolutionFaces = sortBy (flip $ comparing length) $
>                            groupSortBy solutionIndex interestingFaceInfos

> interestingSolutionFreq = histogram $ map length interestingSolutionFaces

The above function produces this histogram: [(1,226),(2,131),(3,35),(4,4),(5,2)]

So, 226 solutions have one unique face each. But two solutions have five unique faces each!

Although the cube faces between them cover 90 different shape faces, there is some redundant information being encoded, because a shape has several coplanar faces, and when a cube face is assigned to a shape face, it must be assigned to all coplanar faces on the same shape. For example, when a cube face contains one of the L-shaped sides of shape L, it must contain all four of the shape faces comprised by that L-shaped side.

Eliminating this redundant information could be done earlier (at the face painting stage) by comparing faces' geometry, but here will do just as well and keeps things simple, by avoiding the need for a representation of a mapping from cell face to shape face.

By removing this redundancy, the cube-face-to-shape-face mapping can be reduced to just 42 bits per cube face, which is good because it will fit in a native 64-bit word now.

> bitGroups = sortBy (comparing head) $
>             dupBits $ map bitRep interestingFaceInfos

> compressRep :: Word128 -> Word64
> compressRep w = foldl (mapBit w) 0 bitMap
>  where
>   mapBit :: (Bits a, Bits b) => a -> b -> (Int, Int) -> b
>   mapBit w w' (outBit, inBit) = if (testBit w inBit)
>                                 then setBit w' outBit
>                                 else w'
>   bitMap = zip [0..] (map head bitGroups)

> uncompressRep :: Word64 -> Word128
> uncompressRep w' = foldl (unmapBit w') 0 bitUnmap
>  where
>   unmapBit :: (Bits a, Bits b) => a -> b -> (Int, [Int]) -> b
>   unmapBit w' w (inBit, outBits) = if (testBit w' inBit)
>                                    then foldl setBit w outBits
>                                    else w
>   bitUnmap = zip [0..] bitGroups

The following working form now contains, for each interesting solution face, a deduplicated representation of the shape faces that it uses, and also an Integer describing which of the other 618 interesting solution faces cannot appear in conjunction with it.

> compressedFaceInfos = [(n, s, cf, compressRep b, p) |
>                        (n, ((s, _), cf, b, p)) <- zip [0..]
>                                                       interestingFaceInfos]

Each cube face needs 9 cell faces.

> targetComboSize = totalEverExternalFaces `div` 9

The above working provides the basis for a naive depth-first search for solutions.

> search partialSolution n
>        usedFaceBits
>        bestN
>        infos =
>     if n > bestN
>     then let (restSolutions, restBestN) = rest n infos
>          in (partialSolution : restSolutions, max n restBestN)
>     else rest bestN infos
>  where
>   rest bestN' [] = ([], bestN')
>   rest bestN' (info@(_,_,_,faceBits,_):infos) =
>     if (usedFaceBits .&. faceBits == 0)
>     then let (withThisInfo, bestN'W) = search (info:partialSolution) (n+1)
>                                               (usedFaceBits .|. faceBits)
>                                               bestN'
>                                               infos
>              (withoutThisInfo, bestN'') = search partialSolution n
>                                                  usedFaceBits
>                                                  bestN'W
>                                                  infos
>          in (withThisInfo ++ withoutThisInfo, bestN'')
>     else search partialSolution n
>                 usedFaceBits
>                 bestN'
>                 infos

> run' minLength = search [] 0 0 (minLength-1)
> run = run' targetComboSize compressedFaceInfos

> chosenCombo' = head $ fst run

Of course, this simple approach runs straight into the combinatrial explosion of having to choose ten elements from a set of 619; considering each possibility at a time is going to take longer than a lifetime. Luckily, there are other ways to attack the problem and once there's a solution it can be plugged in quickly.

The following was found very quickly (that's to say, in less than a second) with a linear constraint solver. Thanks to Google's math mailing list for that suggestion.

> chosenCombo = map (compressedFaceInfos!!)
>                   [68, 139, 152, 208, 234, 336, 363, 386, 487, 513]

The naive search may not be efficient enough for finding a solution, but it's suitable for checkin a solution. This confirms that the selection made by the linear constraint solver does have the properties required.

> chosenComboIsValid = (not . null . fst) $ run' targetComboSize chosenCombo

Having found a set of ten solution faces that completely cover the shape faces, it's time to condense those faces into one data set that describes, for each shape face, which solution face it belongs in and where in the solution face it appears. That will be enough to asssign a texture to the shape face, and also texture coordinates.

> type ShapeFaceData = Maybe (Int, Recipe)

This elaborate list comprehension fits together all the exploded face information from earlier, into a single structure that collects the facts for each face of each shape.

> implodePainting :: [(Int, Solution, [(Shape, [Bool])])]
>                 -> [(Shape, [ShapeFaceData])]
> implodePainting explodedMarkings = [
>     (shape, superpose paintGroups) |
>     (shape, paintGroups) <- [head $ groupKey grp |
>                              grp <- groupSortBy fst .
>                              concat $ explodedShapeFaceDatas]]
>  where
>   superpose :: [[ShapeFaceData]] -> [ShapeFaceData]
>   superpose = map msum . transpose
>   explodedShapeFaceDatas :: [[(Shape, [ShapeFaceData])]]
>   explodedShapeFaceDatas = [attachMaterials (i, solution, shapeFacePaints) |
>                            (i, solution, shapeFacePaints) <- explodedMarkings]

The painting condensation logic relies on this helper function, whose purpose is to multiply solution face information out onto each face that appears on the solution face.

> attachMaterials :: (Int, Solution, [(Shape, [Bool])]) ->
>                                    [(Shape, [ShapeFaceData])]
> attachMaterials (cubeFaceNumber, solution, shapeFacePaints) = [
>  (shape, [if paint then Just (cubeFaceNumber, recipe) else Nothing |
>           paint <- facePaints]) |
>  (shape, recipe, facePaints) <- merge solution shapeFacePaints]
>   where merge (Solution s) (facePaints) = [
>          (checkEqual "Yikes!" shape shape', recipe, paints) |
>          ((shape, recipe, _), (shape', paints) )<- zip s facePaints]

> checkEqual msg s1 s2 = if s1 == s2 then s1 else error msg

The solution information can now be split into two results.

The first result is an association of solution to cube face, which allows for successive face solution animations to point the same way, even though different chosen solution faces have different orientations.

The second result describes, for each face of each shape, which solution it belongs to (if any) and the position of the shape in that solution (if any), which is necessary for assigning UV coordinates.

> implodeCombo combo = (solutionToCubeFace, implodePainting nsps)
>  where (solutionToCubeFace, nsps) = unzip [((s, cf), (n, s, p)) |
>                                            (n, (_, s, cf, _, p)) <-
>                                            zip [0..] combo]

A couple of small helper functions ease export to a Python-readable form.

> pyVec2 (Vec2 x y) = (x, y)
> pyMaterial Nothing       = "Face" ++ "X"
> pyMaterial (Just (n, _)) = "Face" ++ show n

> painter faceMaterials shape = fromJust . flip lookup faceInfo
>  where 
>   faceInfo = [(face, (pyMaterial mat, uvs mat (faceVerts sign axis face))) |
>               ((sign, axis, face), mat) <-
>               zip (allFaces $ defaultForm shape)
>                   faceMaterials]

Always-internal shape faces don't add up to nice shapes, so they can each display a full texture.

>   uvs Nothing _ = [(0,0),(0,1),(1,1),(1,0)]

For sometimes-external shape faces, the UV coordinates are chosen by transforming the face's vertices into their position in the solution to which the shape face belongs, then seeing whether the vertices appear on the corresponding cube face. At this point there's no information about which cube face it's meant to be, so that is reconstructed from the vertices' normal. (It ought to be possible to keep the cube face information up to this point, then use 'toXaxis' to avoid the normal calculation. But that's for another time.)

>   uvs (Just (_, recipe)) verts = [pyVec2 $ extractUvs vert' &* (1/3) |
>                                   vert' <- verts']
>     where
>       verts' = map (vApplyRecipe recipe) verts  -- into solution space
>       extractUvs = (apply . extractor) verts'
>   apply :: (Vec3 -> Float, Vec3 -> Float) -> Vec3 -> Vec2
>   apply (exU, exV) vec = Vec2 (exU vec) (exV vec)

It's perhaps possible to simplify this mapping, but how is not obvious.

>   extractor [a,b,c,_] =  ex $ pyVert uvNormal
>    where uvNormal = (b &- a) &^ (c &- b)
>          ex (1, 0, 0) = (p _2, p _3)
>          ex (0, 1, 0) = (n _1, p _3)
>          ex (0, 0, 1) = (p _2, n _1)
>          -- For negative normals, just flip the V coordinate
>          ex (a, b, c) = let (eu, ev) = ex (-a, -b, -c) in (p eu, n ev)
>          n = ((3-) .)
>          p = id

> testMeshes = do
>   let (solutionToCubeFace, shapeFaces) = implodeCombo chosenCombo
>   writeMeshes [(shape, mesh (painter faceInfos shape) shape) |
>                (shape, faceInfos) <- shapeFaces]
>   writeSolutions [Solution [(shape, recipe .*. toXaxis sign axis, bitmap) |
>                             (shape, recipe, bitmap) <- s] |
>                   (Solution s, CubeFace sign axis) <- solutionToCubeFace]
>   importIntoBlender

> main = testMeshes

Thursday, 31 January 2013

The Moment You Didn't Know You Were Waiting For

Following on from the export side of the Soma Cube work, here's the import side, in Python, to be run as a Blender script. This is more of an exercise in finding one's way around Blender's object model than anything else, so there's not much point in a deep commentary on it. Each shape of the cube is loaded into a separate Mesh object, and each solution of the cube becomes a set of keyframes for those objects.

import math
import bpy
import io

file = io.open

# RGB components are in the range [0,1].
#
# NMesh.materials is a list of Material objects. NMesh.faces[i].mat is the
# index into the mesh's material list of the material to use for the i'th
# face.

# When assigning to a face's vertex index list, a final zero is ignored.
# So, when creating a square face, rotate its vertex list if necessary
# to make sure vertex zero can be specified.
def RawVertices(verts):
  if len(verts) == 4 and verts[-1] == 0:
    return [0] + verts[:-1]
  else:
    return verts

def ReadShapes():
  meshes = eval(file('shapes.txt').read())

  materials = {}
  for (_, (_, faces)) in meshes:
    for i, (_, mat_name) in enumerate(faces):
      if mat_name not in materials:
        n = len(materials)
        material = bpy.data.materials.new(mat_name)
        material.diffuse_color = [(n & (1<<j)) and 1.0 or 0.3 for j in range(3)]
        materials[mat_name] = material

  for i, (name, (verts, faces)) in enumerate(meshes):
    poly = bpy.data.meshes.new(name)

    poly.vertices.add(len(verts))
    for j, v in enumerate(verts):
      poly.vertices[j].co = v

    mesh_materials = []
    for (_, mat_name) in faces:
      if mat_name not in mesh_materials:
        mesh_materials.append(mat_name)
    for mat_name in mesh_materials:
      poly.materials.append(bpy.data.materials[mat_name])

    poly.faces.add(len(faces))
    for j, (verts, mat_name) in enumerate(faces):
      f = poly.faces[j]
      f.vertices_raw = RawVertices(verts)
      f.material_index = mesh_materials.index(mat_name)

    poly.update()
    obj = bpy.data.objects.new(name, poly)
    bpy.context.scene.objects.link(obj)

def ReadSolutions():
  solutions = eval(file('pysolutions.txt').read())
  frames_per_solution = 10

  for i, solution in enumerate(solutions + solutions[:1]):
    for name, (euler, location) in solution:
      props = {'rotation_euler': euler, 'location': location }

      obj = bpy.data.objects[name]

      anim_data = obj.animation_data or obj.animation_data_create()
      action = anim_data.action
      if action is None:
        action = bpy.data.actions.new('%s_Action' % name)
        for prop in 'location', 'rotation_euler':
          for index in range(3):
            action.fcurves.new(prop, index)
        anim_data.action = action

      for curve in action.fcurves:
        value = props[curve.data_path][curve.array_index]
        curve.keyframe_points.insert(i * frames_per_solution, value)

  bpy.context.scene.frame_end = i * frames_per_solution

if __name__ == '__main__':
  ReadShapes()
  ReadSolutions()


... And if you've read this far, here's a little reward - a crude Blender render of the resulting animation. Nothing fancy yet, but it represents progress.