After figuring out the shape for the pillows - I had to figure out how to cut the foam in an easy way - and then convince the people working at the foam shop to cut it for me. Luckily, having figured out the order in advance, this worked out quite well.

The pictures show a reconstruction of the cutting process.