If an axis-aligned cube moves along one of those axes, the volume it carves out is a rectangular prism.
It's not hard to imagine what it looks like if it moves in a straight line in any direction, actually. Picture that cube moving slightly down or to the right at each time step.
A while back I was reading about a physics library and came across a comment about detecting collisions between two moving, rotating objects (probably cubes). If you have generous bounding volumes for the space each object will occupy over the time step being calculated, and those don't intersect, then you know that they couldn't have collided and you can avoid a relatively expensive calculation of where the collided and when.
One possible bounding area is a cylinder with rounded ends, the volume occupied by the sphere inscribing the cube during the time step. Whatever the cube's rotation during that period, it can't escape that shape, which should be easy to intersect with others of the same type.
But how tightly can you bound the space occupied by the cube as it travels? What is the exact shape of that space?
I found it hopeless to try to imagine, so I moved to two dimensions, considering a rotating and translating square. After thinking about it for some time (without paper), I thought I had figured out a way of generating bezier curves that would trace the trail that square would leave behind. I was only kind of right.
What I missed was that the two sides of the resulting shape would be asymmetrical. It seems obvious now, but I hadn't predicted the way that, at high speeds, the smooth connected arcs would turn into pointier and pointier protuberances on the side with the backward-moving corners.
The above image was generated by some Processing code that simply drew squares moving from left to right under the influence of a positive rotational force and a constant rightward velocity. Each row only differs in the frequency at which I sample the squares to be drawn (think strobe light). The last row has shading applied to visualize how much time the square spent at each location.
So that was fun.
As I was tweaking the code to get better compositions, I began to dig the way it looked: I really wanted it on my wall. Processing didn't seem to like increasing its window resolution to 7,200 by 3,655, running out of memory at launch. I couldn't just resize the image because I didn't want to compound the aliasing due to the way I was drawing squares with the aliasing of resizing the image. So I rewrote the renderer in Go and tossed a humongous GIF at DeviantArt for printing. It looks great.
The only hang-up I encountered while using Go's image package was that it doesn't have any functions for drawing primitives, even lines. Thankfully, I remembered a relatively efficient method from a computer graphics textbook:
// draw a line from (x1, y1) to (x2, y2) in the given image with the given color
func line(i *image.NRGBA, x1, y1, x2, y2 int, c image.NRGBAColor) {
dx := float(x2 - x1)
m := float(y2-y1) / dx // slope of the line
if m < 1 && m > -1 {
// line is not very steep, so walk along the x-axis
// swap if necessary so we can walk left to right
if x1 > x2 {
x1, y1, x2, y2 = x2, y2, x1, y1
}
for x := x1; x < x2; x++ {
if x < 0 || x >= i.Width() {
continue
}
// calculate y position at the given x coordinate
y := int(m*float(x-x1) + float(y1))
if y < 0 || y >= i.Height() {
continue
}
// draw
i.Pixel[y][x] = c
}
} else {
// a steep line, so walk along the y-axis
// swap if necessary so we can walk toward positive y
if y1 > y2 {
x1, y1, x2, y2 = x2, y2, x1, y1
}
for y := y1; y < y2; y++ {
if y < 0 || y >= i.Height() {
continue
}
// calculate x position at the given y coordinate
x := int(float(y-y1)/m) + x1
if x < 0 || x >= i.Width() {
continue
}
// draw
i.Pixel[y][x] = c
}
}
}
There's still plenty of room for improvement there, but it got the job done.