Transformation of LEGO Models

The problem

Container stacking raises a practical question: how can containers be moved efficiently from one stack to another? This paper studies a remotely related question with LEGO: build a new LEGO model using bricks taken from an existing one. Many algorithms turn a 3D shape into a LEGO model, but constructing a LEGO model from the bricks of another model had not been explored in open literature. The task has two goals that pull against each other. Every pick-and-place (PnP) of a brick costs one move, and as many bricks of the source model as possible should end up in the target.

Physical constraints make the order of moves matter. A brick fully or partly under other bricks cannot be picked, and a brick cannot be placed where it would hang in the air. The authors also treat a top-surface brick that is completely surrounded by other bricks as not movable, because freeing it would take extra moves.

How it works

The source model is taken apart from the top down and the target is built from the bottom up, layer by layer. Two basic approaches, rigid transformation (RT) and flexible transformation (FT), decide how the target’s bricks are chosen, and three strategies decide where each brick comes from: straight from the source, from a buffer of bricks already removed, or from a stock with an unlimited supply. Combining them gives six algorithms, RT1–RT3 and FT1–FT3, which use seven brick shapes.

1. Moves and constraints. Each PnP of one brick (source to buffer, source to target, buffer to target or stock to target) counts as a cost of 1. Only movable bricks, those with nothing on top and not fully surrounded, can be picked.
2. Rigid or flexible target. In rigid transformation (RT), the target LEGO model is generated before the transformation, with large bricks used first on each layer. In flexible transformation (FT), the target is built from an interim voxelized model on the fly: a scoring rule weights each brick type by how many movable bricks of that type the source currently offers, so source bricks are used first.
3. Strategy 1. The source is disassembled completely into the buffer, and the target is built from the buffer, with the stock filling in bricks the buffer lacks.
4. Strategy 2. Movable source bricks go straight to the target. If none matches, the buffer is searched; if it has none either, one more layer of the source is disassembled into the buffer to uncover new bricks. The stock is used only when the source is gone.
5. Strategy 3. No buffer. A matching movable source brick goes straight to the target; otherwise the stock supplies one.

The algorithms are compared with three metrics: the cost C, the number of PnP needed to build the target; the reuse rate R = N_r/N_s, the share of the source’s N_s bricks that end up in the target; and an overall performance P = V·R/C, where V is the number of voxels in the target model.

Results

The algorithms were tested on eight triangle mesh models converted to LEGO. In the first test, model A was transformed into each of the other seven models at about 2500 voxels per model. In the second, all eight models were transformed into each other at seven model sizes. Cost grows linearly with model size, and cost drops from Strategy 1 to 2 to 3 at every model size. An FT algorithm costs more than its RT counterpart because FT builds a target with more bricks. FT3 reaches a reuse rate comparable to the best RT algorithms. RT3’s reuse rate is much lower than RT1’s and RT2’s: when the target bricks are fixed in advance and there is no buffer, matching source bricks are hard to find, and on average more than half of the target bricks come from the stock. Reuse rate is not very sensitive to model size above 1700 voxels per model; smaller models reduce it.

The third test added colour: exterior bricks must match the surface colour, while interior bricks may take any colour. For the ball-to-house transformation, RT1 and RT2 reuse 61.9 % and 59.9 % of the bricks, and RT3 only 9.2 % (Fig. 9). The authors note the trade-offs: FT’s higher reuse comes with more and smaller bricks, giving weaker structures with internal sliding planes; the overall performance metric is empirical, and other scenarios may weigh cost differently. The study moves one brick at a time; reusing groups of bricks as modules is left to future work, and the results may not be directly applicable to a specific industrial application such as cargo container stacking.