Balance — Project Cube

Balance: harder than it looks

TL;DR. Programming "does this 3-D structure stand?" turned out to be the longest detour of the project. Each simple rule I tried failed on a slightly weirder configuration. In the end, I stuck to a linear program to solve it to some extend at least.

The main thing I wanted was to establish a rule of balance. Something that can be checked by the computer. Preferably simple, under which every case of balance will fall. This page contains some examples and how the algorithm changed throughout the project.

An L on a hollow cube

Center of mass (COM) at

(11/6, 11/6, 3/2)

, inside the 1×1 support polygon (which spans

x, y \in [1, 2]

The L spans three unit cells with centers at $(1.5, 1.5, 1.5)$ , $(2.5, 1.5, 1.5)$ , and $(1.5, 2.5, 1.5)$ . With equal mass per cell, the COM is the mean of the centers:

COM = \frac{1}{3} [(1.5, 1.5, 1.5) + (2.5, 1.5, 1.5) + (1.5, 2.5, 1.5)] = (11/6, 11/6, 3/2) .

The rule: each block's center of mass (COM) has to be over the cells supporting it.

"Right, it seems we are done, a COM can be easily calculated for each block, and the cells supporting it are the ones directly beneath, right? Right?!?"

Dropping a 1×1×3 on top

Now we add a long bar to the structure. Our rule says that this will balance, since the long bar's center of mass is above the cell directly beneath it. And for the L piece it was just as before, so that center of mass will also be above the cell supporting it. Yet, this tower will not stand at all. Therefore, our rule was wrong.

Changing the rule, we must account for not only the blocks, but each block resting on top of that as well. The L is now carrying the long bar on top, and the combined center of mass of those two falls past the blocks supporting it.

The rule: for each block, the COM of that block plus every block resting on it has to be over the cells supporting it.

"This is it, COM can be easily calculated still, every block on top will just be directly on top (works transitively) and the cells supporting it haven't changed. This rule works, right?!?"

Bridges

The long bar's middle cell hangs over nothing.

Apply the updated rule: Nothing rests on top of the long bar. So we calculate the COM of the long bar. It is right above the empty middle cell. So it doesn't have any supporting blocks directly beneath it, yet the tower clearly stands.

Now the rule must undergo another change. The issue this time is with the supporting blocks. And we will change this to a rule that the COM should lie above the convex hull of the cells directly beneath it. However, if we do this, we would still have a problem. One that might not be that obvious. What if this structure is on top of something? Again, the long bar will distribute its weight equally over its supports. Currently, the algorithm wouldn't account for that. And then it would have "the block plus every block resting on it" wrong.

Thus, our rule is changing again. Before we formulate how the rule would need to change, let's think of other cases that might be special or broken before we continue. Otherwise, we might have to start all over again.

The rule: for each block, the COM of that block plus every block resting on it has to be over the convex hull of the cells supporting it. Plus somehow account for bridges and weight splitting.

"So we already have a rule that's not properly defined, if this is it, we can probably make it working. This IS it, right?!?"

An L wrapping a column

The L's COM is at $x_{COM} = 1/2$ , $y_{COM} = 7/6$ . Since the COM is outside its support, will this block fall? Well, imagine that the blocks were made of rubber. The center of mass of the whole structure says it will stand. And yet the LP actually has it slide off. There is friction, especially when the pieces are made of rubber. So then it would be pretty logical that this tower would stand. Do we somehow need to account for friction? In the end, I chose not to do this because it would just create a lot more difficulty.

"The rule remains unchanged, but now also has to account for torque, and we also said that we won't implement friction. Does this have to become a full-blown physics simulator?"

Does weight matter?

What about weight? Can we find positions with different stabilities depending on the weight of the blocks? The actual blocks weigh roughly 15 g (full) and 5 g (hollow). A 3:1 ratio. See below. There are two situations with the same blocks but with different stability depending on the weight ratio.

3:1 (the game). The hollow piece counterweights the L. Stable.

15:1 (hollow nearly weightless). Same blocks, same positions. Counterweight gone. Tips.

"Thus a COM of a block plus every block resting on it has to be over the convex hull supporting it + account for bridges and weight dividing + torque + the actual weights of pieces matter, that would be a lot of rules, we need something stronger to fix this!"

The actual stability check

This is the algorithm that I went for in the end. For every block, two things must balance — force and torque. If there exist forces such that all are counteracted (Newton's third law) and there is no net torque in the whole structure, then there is a stable solution. This can be solved using a linear program.

Torque can be calculated from the forces acting on an object and its center of mass. Thus, we need to solve for all the forces. Every face of every block is split up into four corners, each with a possible force perpendicular to the surface.

Instance 1: one block, one contact

Left: the force of gravity of the long bar can be counteracted with forces at the four corners of the smaller block. Right: the long bar overhangs the face of the small block. Any force on the small block would induce a torque on the long bar. Therefore this is unstable.

Instance 2: two contacts

Same algorithm. The LP automatically splits the load wherever a non-negative split satisfies all the equations — no special "bridge rule" needed.

Bridge, side view. Two separate 1×1 contacts, COM over the gap. Each of the four corners can push independently; one balanced solution puts

\frac{m g}{4}

at every corner. Force balance:

4 \cdot \frac{m g}{4} = m g

✓. Torque balance: the four equal pushes are symmetric around the COM, so their torques cancel ✓.

The algorithm, written out

Each face of every block is split into 1×1 parts. This ensures that a block like the long bar can be used in the same way and have the same counteracting forces. Since we check for torque, this ensures that the long bar is actually connected because it has a single center of mass. Also, to slightly simplify the algorithm and lower the running time, I only added vertical forces here. Yes, you could also do side forces, but side forces need to be counteracted, and there is no wall and no friction to do this. If one were to extend this algorithm with friction, side forces should also be implemented.

Notation, before the LP equations:

$C$ — the set of all contact faces in the tower (block-on-block, and block-on-ground). $C (b)$ — the subset that touches block $b$ .
$F_{c, k} \geq 0$ — the upward push at corner $k \in {1, 2, 3, 4}$ of contact $c$ . Four non-negative variables per face.
$(x_{c, k}, y_{c, k})$ — the horizontal position of that corner.
$σ_{b, c}$ — sign convention: $+ 1$ if block $b$ sits above contact $c$ (contact pushes $b$ up), $- 1$ if $b$ sits below (reaction presses $b$ down).
$m_{b}, g, (x_{b}^{COM}, y_{b}^{COM})$ — block $b$ 's mass, gravity, and the horizontal coordinates of its centre of mass.

force balance: torque about y : torque about x : c \in C (b) \sum σ_{b, c} k = 1 \sum 4 F_{c, k} = m_{b} g c \in C (b) \sum σ_{b, c} k = 1 \sum 4 F_{c, k} x_{c, k} = m_{b} g x_{b}^{COM} c \in C (b) \sum σ_{b, c} k = 1 \sum 4 F_{c, k} y_{c, k} = m_{b} g y_{b}^{COM}

No objective: it's a pure feasibility LP. Some $F \geq 0$ satisfies every equation ⇒ stable; no such $F$ exists ⇒ tips.

Strict vs marginal balance.

What about a 1×1×2 block balancing on a single block? In a perfect world, this would balance because the center of mass is directly above the edge of the face below. However, in the real world, this will likely not be possible. The pieces are not perfectly manufactured, and somehow I just don't like that solution — barely balancing, or somehow cheating and shifting the block a little more than it has to. Thus I made two categories of balancing: one called strict and one called marginal.

To determine between strict and marginal stability, one can run the linear program with each face's corner positions shrunk inward by a small δ. Towers that survive are strictly stable. Ones that don't are marginally stable.

Left: δ = 0. This is the case as before. If the force at the right corner is exactly the gravity from the center of mass, this will balance. Right: if we trimmed the face a little, then the center of mass now lies outside the contact face. So there are no possible forces that would counteract the weight.