legolization

Turn a colored voxel model into a physically buildable LEGO model in LDraw format, with step-by-step build instructions and a bill of materials.

This is the classic "LEGO construction problem" from the research literature (see references/): voxelize → hollow → place bricks → check structural stability → repair → export. The stability check is a full Rigid-Block-Equilibrium (RBE) model (StableLego formulation, cross-validated against its released test fixtures): per-brick force and torque balance with knob-friction capacities, solved as a provably exact linear program on an open solver stack — no Gurobi required.

What it does

• Input: a MagicaVoxel .vox file or a numpy .npy array (LDraw colour codes or RGB(A) voxels — colours are quantized to the nearest solid LDraw colour, with optional Floyd-Steinberg dithering for gradients).
• Placement: covers every voxel with bricks and plates at true heights (plate = 8 LDU, brick = 24 LDU) using one of seven strategies; tiles and slopes are opt-in finishing passes (--tiles, --slopes). Slope fitting places all three catalogued slopes (45° 2x1/2x2, 33° 3x1): --slopes (= --slopes preserve) swaps bricks whose cells exactly match a slope's own profile inside the shape — no material added or removed — while --slopes smooth is the legacy pass that fills staircase steps with slopes outside the shape:
  • greedy (default): largest-first bottom-up fill with Kollsker's remainder-lookahead h(r) and distance-decayed stretcher-bond scoring, then delete-and-rebuild reinforcement around the weakest bricks.
  • luo: Luo et al. (2015) maximal random merge with split-and-remerge refinement, accepted by Luo's maximin friction capacity C_M; supports soft colour constraints (--colour soft).
  • bond: Kollsker & Malaguti's constructive brick-bonding heuristic — remainder lookahead + staggering reward + per-layer repair.
  • fast: Bao et al.'s greedy per-layer merge with a dominant big-brick weight, perpendicularity term, and connectivity retries.
  • smga: Lee et al.'s split-and-merge genetic algorithm per layer (--ga-generations, --time-budget).
  • beauty: Min et al.'s objective-driven tiling with symmetry/balance, stability-priority, and big-brick terms (--beauty-preset {balanced,stability,aesthetics,efficiency}).
  • kollsker: Kollsker & Malaguti's exact set-partitioning MILP, solved per 4-connected component of each layer — stage 1 minimizes the part count, stage 2 maximizes stagger quality at that optimum; falls back to bond per component on timeout.
• Physics: every layout is scored by the RBE — gravity, support, press, drag/pull friction (capacity T = 0.98 N per contact point), knob presses, and torque-capable side presses at shared-face extremes (side-supported structures shed load like Luo's bridges). Equilibrium residuals sit in the objective, so even collapsing structures solve and failures localize to specific bricks.
• Repair: unstable layouts go through an ALNS destroy-and-repair pass (Kollsker's artificial-link QP pinpoints the deficit; the freed region is refilled by the merge engine or an exact-cover MILP) before any material is added back by the stability-aware hollow-restore loop.
• Auto-hollow: interiors are hollowed to a shell (~1 brick thick, tunable with --shell-plates); interior cells are colour-free so merges never fragment on invisible boundaries.
• Instructions: smart step sequencing (default) chunks each layer into ~7-brick spatially coherent steps, keeps mirror-symmetric halves together, prefers spatially adjacent steps (Ma et al.'s continuity heuristic), guarantees every prefix is stable and vertically insertable (or warns), and adds 0 ROTSTEP view hints. When the greedy pass hits an unstable stretch it re-plans the remainder by assembly-by-disassembly along a maximal-stability path (Tian et al. / Luo); an opt-in beam search (InstructionsConfig(search="beam")) explores whole build orders. --bom out.json writes a bill of materials with per-step callouts.
• SNOT cladding: --snot clads tall flat wall faces with sideways 1x1 tiles (3070b) hung on side-stud brackets (87087) — real receiving geometry, priced by the same RBE physics through genuine lateral stud contacts. Only free-standing 1x1 wall columns are converted (carving a bracket out of a wall-spanning brick would destroy its bonding), and the pass reverts wholesale if it would flip the stability verdict.
• Subassemblies: --subassemblies detects stretches that float in every build order (mushroom caps, arches), lifts them out as separately built units — each constructed stably on the table, then attached as one piece — and emits them as .mpd submodel FILE sections. Booklets get per-unit sections and attach callouts; the .ldr fallback flattens attach steps back to world-frame bricks.
• Booklets: --instructions out.html (or .pdf) writes a paginated instruction booklet — cover page with model stats, parts list, and one rendered image per step with new bricks highlighted and per-step part callouts. Step images render through LeoCAD (preferred; batched per-step export) or LDView, auto-detected from $LEGOLIZATION_RENDERER, PATH, then /Applications; the parts library is found via $LDRAWDIR or common install paths. Without a renderer the booklet is still written with placeholder boxes (LEGOLIZATION_RENDERER=none disables rendering explicitly, e.g. in CI).
• Output: a valid .ldr or .mpd written through pyldraw3. Open it in LDView or BrickLink Studio.
• LDraw input: an existing .ldr/.mpd model can be the input too — placement is skipped and the model's own bricks are analyzed and sequenced into instructions (legolization model.ldr -o out.ldr --instructions booklet.pdf). Import is strict: every part must be in the catalog, axis-aligned, on the stud/plate grid, and in the solid palette; all problems are reported together. MPD submodels are flattened through their world transforms.

Setup

uv sync
uv run ldraw download --yes   # once: fetch the LDraw parts library
uv run ldraw generate --yes   # once: generate ldraw.library.* part/colour modules

Usage

uv run legolization data/examples/heart.vox -o heart.ldr
uv run legolization model.npy --strategy beauty --beauty-preset aesthetics
uv run legolization model.vox --strategy bond --bom parts.json
uv run legolization model.vox --instructions booklet.pdf   # rendered booklet
uv run legolization model.npy --strategy luo --solid --seed 7
uv run legolization model.vox --slopes --tiles      # surface finishing passes
uv run legolization model.vox --slopes smooth       # legacy add-outside slopes
uv run legolization model.vox --snot                # sideways wall cladding
uv run legolization model.vox -o out.mpd --subassemblies  # separately built units
uv run legolization model.vox --aspect-correct      # keep cubic voxel aspect
uv run legolization model.vox --milp                # cross-check the exact LP
uv run legolization model.npy --strategy all --jobs 4 --report report.json
uv run legolization model.obj --up y --target-studs 24   # mesh input (M6)
uv run legolization model.ldr -o out.ldr --instructions b.pdf  # LDraw input
uv run legolization analyze model.ldr                    # physics report + repair

Analyze an existing LDraw model

analyze is the non-generative feasibility workflow. It auto-grounds the lowest occupied layer, checks stud connectivity and grounding, solves both the StableLego-parity 5-DOF and stricter yaw-torque 6-DOF profiles, computes strict maximin friction capacity, and checks explicit STEP prefixes. If the finished model fails, a killable worker searches deterministic re-tiling, enclosed-fill, and exterior-support tiers for one candidate that passes every same check.

uv run legolization analyze model.ldr
uv run legolization analyze assembly.mpd --preserve-origin --no-repair
uv run legolization analyze model.ldr \
  --report evidence.json --output repaired.ldr --time-budget 120 --seed 7
uv run legolization analyze model.ldr --catalog local-parts.json --catalog lab.json

The defaults are model.analysis.json and, only when a validated repair is found, model.repaired.ldr. The input path is always rejected as an artifact path. Exit code 0 means the original model is feasible, 2 means the original is infeasible (even when a repair was found), and 1 means invalid input, solver failure, or an indeterminate result. Source STEP warnings are informational and do not change the finished-model exit code. Once the finished-model verdict is determined, repair-search failures, timeouts, and repair-write failures are recorded in the report (status "partial") and likewise leave the exit code unchanged.

Analysis reports use schema 2. The ldraw block records pyldraw's prepared catalog state, tolerant-load diagnostics, exact transformed bounds, official BOM, occurrence provenance, and renderer-neutral instruction sections. Exact stud contacts and AABB gaps are included through 1,000 occurrences and marked as skipped above that safety limit. The analyze command prepares the configured catalog automatically; if the library is missing, run ldraw download --yes.

LDraw import — for both the generation and analyze workflows — snaps Studio-style export noise: positions within 0.2 LDU of the stud/plate grid and rotations within about half a degree of a yaw multiple are accepted; meaningful offsets such as a half plate are still rejected.

Catalog extensions declare "schema": 1 and a parts list. Rectangular bricks, plates, and tiles use explicit size, height_plates, and measured mass_g. A custom non-rectangular part must instead declare its complete occupied_cells, filled_cells, top_connectors, bottom_connectors, orientations, origin_offset, height_plates, and measured mass_g. Extensions cannot override keys or introduce an ambiguous LDraw decode.

Mesh inputs (.obj/.stl/.ply) are voxelized directly at plate resolution (always aspect-correct): --target-studs N sets the footprint width (or --pitch for explicit model-units-per-stud), --up y handles the common Y-up convention, --mesh-colour CODE picks the uniform colour, and --no-fill keeps shell meshes hollow. Disconnected mesh components are preserved by default; --largest-component-only discards every smaller voxel island and always reports how many voxels were removed. --mesh-colour-mode sampled colours each voxel from the mesh's texture/vertex colours (nearest-vertex, quantized to the LDraw palette), falling back to --mesh-colour with a note when the mesh carries no colour data — note a loose .obj without its .mtl/texture (e.g. the corpus spot.obj) has none, so it stays uniform.

--strategy all runs every registered strategy on the same input (in parallel worker processes; --jobs 1 forces sequential) and keeps the best model. Selection is lexicographic, following the reference papers: candidates are first gated on buildability (stable, one connected component, nothing floating), and the survivors are ranked by the weighted objective, with ties broken by maximin friction capacity, then brick count. --report writes a JSON comparison of every strategy, --keep-candidates DIR also writes each strategy's model, and --timeout SECONDS sets a soft deadline for the overall parallel sweep while also becoming the cooperative time budget for strategies that support one. Workers already running at the deadline cannot be terminated and may continue after the sweep returns.

The CLI races a few seeds by default (--restarts, default 3: placement and physics run per seed in parallel, then the best layout is re-run once with full instruction sequencing — --restarts 1 restores single-seed runs) and reports brick count, mass, step count, and the physics verdict:

restart race: seeds 0..2 -> seed 2
wrote heart.ldr
  bricks: 12   mass: 17.9 g   steps: 8   slopes: 0   tiles: 0
  stability: STABLE (worst score 0.001, min capacity 0.979 N)

Exit code 0 means the model is stable, one stud-connected component, and ground-connected. Exit 2 means it is not buildable as-is (try another --strategy, --solid, or a different --seed) — note that an input made of several disconnected voxel islands is reported as multiple components even when every island stands on the ground.

Python API:

from pathlib import Path
from legolization import (
    AnalysisConfig,
    PipelineConfig,
    VoxelGrid,
    analyze_ldraw,
    run,
    run_file,
)

result = run_file(Path("model.vox"), Path("model.ldr"), PipelineConfig(seed=1))
print(result.buildable, result.step_count, result.stability.max_score)

analysis = analyze_ldraw(
    Path("existing.mpd"),
    AnalysisConfig(repair_time_budget_s=120, seed=7),
)
print(analysis.report.verdict, analysis.report.to_json())

How the stability model works

Each mated stud contributes 3 or 4 contact points (per StableLego's measured geometry) carrying a shared normal force and a friction (drag/pull) force, so Newton's third law holds by construction; each knob adds four horizontal knob-press forces, and laterally touching bricks exchange two side presses at the shared face's vertical extremes so lateral load transfer carries torque. Per brick, five equilibrium residuals (3 forces, 2 torques about the mass centroid) are minimized rather than constrained. A brick scores 1 when it cannot reach equilibrium or its friction demand exceeds T; otherwise drag_max / T — so the score doubles as a stress heatmap. The default solver is a hand-assembled LP on scipy/HiGHS, and the relaxation is provably exact (each contact's press and pull columns are exact negatives, so no optimum ever uses both); --milp re-verifies with explicit big-M complementarity via cvxpy. The whole stack reproduces all nine verdicts of the StableLego release's test fixtures (vendored under tests/data/stablelego/).

Benchmark

uv run python scripts/benchmark.py compares all six strategies across the example models (brick count, stability margin, seam/perpendicularity/symmetry metrics, runtime). Highlights at seed 0: bond and beauty cover the arch in 13 bricks where largest-first greedy needs 32, and beauty --beauty-preset aesthetics produces perfectly mirror-symmetric layers on symmetric models. For picking one model right now rather than tabulating, --strategy all is the CLI counterpart (see Usage).

Development

uv run pytest          # fast inner loop; slow integrations skip by default
uv run pytest --run-slow  # full suite, including benchmark/sweep/renderer tests
uv run ruff format --check . && uv run ruff check .
uv run ty check src tests
uv run pyrefly check src tests

License

GPL-3.0-or-later (inherited from pyldraw3).