Piecewise-Manhattan Sparse Grids for Large-Scale Constrained Assembly

Learned solvers for spatial assembly can now check whether a new part collides with anything already built almost for free. They do it by sliding a fixed, part-shaped filter over a 3D occupancy grid on the GPU. The catch is that this only works when every part sits on one axis-aligned grid. A diagonal wing, a slanted roof or a building with two street orientations forces either staircase approximations, which waste the part budget, or a fall back to slow geometric tests. We propose to represent a structure as a few overlapping sparse grids, each rotated to one locally dominant orientation. Within each grid, collision checks stay exact and convolutional. Only the thin seams where grids meet need explicit geometry. A global network decides which region belongs to which grid, and local placement policies then fill the regions in parallel. Put in two sentences: most "non-Manhattan" structures are really several Manhattan structures glued together, so give each piece its own grid and keep the fast convolutional feasibility check. Splitting the problem by orientation also yields the divide-and-conquer decomposition that lets a neural solver scale past step-by-step placement.

This matters because the two literatures that touch the problem have moved in opposite directions. Assembly solvers kept the grid and its hardware-friendly checks but stayed rectilinear. Architectural generators dropped the grid to escape the "Manhattan world" assumption, the prior that all surfaces align with three perpendicular axes, and in doing so lost cheap feasibility checking and quadratic-free scaling.

Core Claim

Fast convolutional feasibility checking does not require a globally Manhattan world, only a piecewise one. Concretely, we pair a learned partition of occupied space into K oriented frames, with K typically between 2 and 6, with one sparse occupancy tensor per frame. A sparse tensor stores only occupied voxels as coordinate and feature lists, so memory scales with occupied space rather than the bounding box. On these tensors, BrECS-style filter checks are exact. Cross-frame conflicts are confined to seam voxels whose count grows with region boundary area rather than volume. The claim is that this matches or exceeds an axis-aligned solver on Manhattan shapes. It should beat it on shapes with off-axis structure, both in reconstruction fidelity at a fixed part budget and in feasibility. And it should do so with wall-clock cost that grows close to linearly in occupied voxels, because regions are filled in parallel rather than one part at a time.

Prior Work and Where This Sits

The method is supplied mainly by Budget-Aware Sequential Brick Assembly with Efficient Constraint Satisfaction (BrECS). BrECS casts LEGO assembly as budgeted combinatorial optimization. A U-shaped sparse 3D network scores next-brick placements, and a fixed all-ones brick-shaped filter checks overlap in 0.0021s on a $64^3$ grid against 4.7s for iterative tests. BrECS is also the closest existing work and the paper we must clearly differ from. It uses one axis-aligned lattice, places bricks one at a time, and offers no mechanism for slanted geometry. We keep its filter check but apply it per rotated frame. We also replace its global sequential loop with partition-then-parallel-fill.

The decomposition idea comes from GLOP. GLOP has a non-autoregressive global network predict a partition heatmap, and small autoregressive policies then solve the sub-problems, which lets it reach 100,000-node routing at a 5.1% gap. GLOP partitions abstract points with no physical extent. Our partition is over occupied voxels, and it is driven by geometric orientation as well as locality, so each sub-problem is guaranteed to be Manhattan within its own frame.

The motivation for avoiding long sequential decoding comes from FrontierCO. FrontierCO documents early errors compounding over long horizons and a leading neural routing solver's gap growing from 0.72% to 77% on hard real-world sets. That paper is a warning, not a tool: it tells us to report out-of-distribution scale results honestly rather than only in-distribution ones.

The piecewise-orientation prior is motivated by reconstruction work that already relaxes the Manhattan world. AtlasGS uses an Atlanta-world prior, which keeps the vertical axis but allows several horizontal directions, to regularize surface reconstruction. HouseDiffusion snaps floorplan corners to integer coordinates to get shared walls and right angles while keeping continuous freedom for non-Manhattan plans. Both treat orientation structure as a prior on a single output. We instead use it to choose the coordinate systems in which a combinatorial solver runs. HouseDiffusion's single snapping lattice is the special case K = 1.

Conv-MPN constrains the design in a useful way. It shows that spatial feature volumes help reasoning about non-Manhattan building graphs, reaching 54.2 region F1 on SpaceNet. It also shows that dense per-element volumes are the memory bottleneck, which is why every tensor here is sparse.

The backbone and the pruning tools are borrowed. The partition network reuses the sparse residual U-Net of PointContrast. The learned occupancy pruning of GSDN, which processes a 78-million-point building in 5 GB, is reused to keep candidate placement sites sparse. Neither paper solves an assembly or allocation problem.

Research Program

The representation is a target shape voxelized at resolution $h$. Each occupied voxel receives a frame label $k \in \{1,\dots,K\}$. Frame $k$ carries a rotation $R_k$, either a yaw about the vertical axis in the Atlanta setting or a full rotation for objects. Each frame keeps its own sparse occupancy tensor on the lattice $R_k \mathbb{Z}^3 h$, so parts placed in frame $k$ are axis-aligned in that frame and the all-ones filter check is exact there. A seam is the set of voxels within one part-length of a frame boundary. A candidate placement whose footprint touches the seam is additionally tested against parts in neighboring frames using exact oriented-box intersection. These are the only geometric tests in the system.

Because the problem changes once parts can be rotated, we generalize from LEGO stud connections to face-contact connectivity. Studs do not mate across rotated frames, so a stud rule would forbid connecting frames at all. This generalization is a real modeling choice, and we report results under both rules where the stud rule applies.

The solver has two stages, mirroring GLOP. The global stage is a non-autoregressive sparse U-Net that predicts, for every occupied voxel, a frame label and a region identity in one pass. It is trained against orientation clusters of surface normals together with a balanced-region loss. The local stage runs a BrECS-style placement policy independently and in parallel within each region and frame, under a per-region budget allocated by the global stage. The policy uses the per-frame filter check, the seam test and a large-parts-first ordering. A final repair pass fixes seam conflicts that parallel fills create, and we measure how often this repair is needed. Region sizes are capped so that each local solve stays inside the size range the local policy was trained on. This is the mechanism by which we hope to sidestep the synthetic-to-scale collapse FrontierCO reports.

The analysis has three parts. We count seam voxels as a fraction of occupied voxels as resolution grows. We relate the gain over axis-aligned BrECS to the fraction of surface area that is off-axis in the target. And we measure how solution quality degrades as K is forced lower or higher than the partition network would choose.

Baselines

The naive reference point is BrECS itself run unchanged with axis-aligned bricks, at the same voxel resolution and brick budget, using the authors' training protocol. It is the honest "do nothing about orientation" answer: it approximates diagonals with staircases. On ModelNet40 airplanes BrECS reports a completion IoU of 0.599 and a 100% validity ratio (BrECS). We first reproduce these numbers. Beating this baseline means higher IoU at an equal brick budget while keeping 100% validity. Because airplanes have large off-axis wing surfaces, they are where the gain should be largest.

The strongest competitor is a single fine sparse grid whose filters are rasterized rotated part shapes, one filter per allowed orientation. This is the most obvious way to extend BrECS. We give it the same orientation set the partition network discovers, the same sparse backbone, and a matched hyperparameter search with equal GPU-hours. Its resolution is swept until it either matches our seam-free exactness or runs out of memory. Beating it means equal or better IoU together with fewer false feasibility verdicts, measured by auditing every accepted placement against exact geometry, at equal or lower memory and wall-clock.

A classical reference completes the set. Bayesian optimization is included as in BrECS, which reports roughly a third of BrECS's airplane IoU. We also run an exact integer program on small instances (at most a few hundred candidate placements) to give a true optimum and measure the absolute gap.

Two ablations isolate the key ingredients and run inside our system. Multiple frames with a single global sequential policy tests whether parallel regional filling, rather than orientation, carries the speedup. A single frame with the GLOP-style partition and parallel fill tests whether orientation, rather than decomposition, carries the fidelity gain. All methods share the voxelization, budgets, hardware and seeds, with at least three seeds reported.

Why not just…?

Why not just rasterize rotated parts as convolution filters on one fine grid? This is the real threat, and it could plausibly match us. A rotated part rasterized at resolution $h$ is wrong by up to one voxel along its boundary. That error produces spurious overlaps that reject valid placements and missed slivers that accept invalid ones. Both are worst exactly where parts must share faces. Shrinking $h$ fixes this but raises the number of occupied voxels as surface area over $h^2$, with a matching rise in hash lookups. The direct comparison in the baselines settles the question: we audit feasibility errors and plot memory as a function of $h$. If the rotated-filter method reaches equal exactness and IoU at comparable cost, the multi-frame representation is not justified. In that case we would report the result and recast the contribution as the parallel partition solver alone.

Why not just generate geometry as vectors with a diffusion model or transformer, like HouseDiffusion or TLC-Plan? These models handle non-Manhattan plans, but in 2D, with attention cost quadratic in the number of corners. They were evaluated on residential plans of roughly 5–10 rooms (HouseDiffusion, TLC-Plan), and they have no hard feasibility check during generation. BrECS reports that generative baselines without such checks produced invalid structures 90% of the time. On the extruded-footprint task below we will nonetheless run HouseDiffusion's 2D output, extruded and then checked, as a reference. This tests whether its implicit constraint satisfaction holds once validity is measured exactly.

Why not just use dense 3D convolutions, or a classical solver? A dense grid wastes memory on empty space and must crop large structures. We will report the resolution at which a dense variant of our partition network runs out of memory, rather than assert it. Classical solvers give guarantees but scale poorly: GLOP reports 13 hours for LKH-3 on 10,000-node routing against 32 seconds for itself. Our small-instance integer program measures how far our solutions sit from optimal where exact solving is still possible, so the speed claim is never made without a quality cost attached.

Proposed Experiments

The primary benchmark is BrECS's ModelNet40 brick assembly, covering airplanes, chairs and tables. We run it at the original $64^3$ resolution and at $128^3$ and $256^3$ with proportionally larger budgets, up to thousands of parts. Metrics are completion IoU, validity ratio, audited feasibility errors, wall-clock, peak GPU memory and the fraction of placements that needed seam repair. Scale generalization is tested by training local policies only at $64^3$ and evaluating at higher resolutions, in the spirit of FrontierCO's out-of-distribution reporting.

The second benchmark tests the Manhattan question directly. We extrude footprints from HouseDiffusion's Non-Manhattan RPLAN split, and as a contrast its standard Manhattan RPLAN plans, into 3D massing models. Each is then assembled from blocks under a budget. No reported result found on Lacuna for brick or block assembly on extruded RPLAN footprints, so all numbers there will be new. They will be anchored by running every baseline ourselves.

Three checks decide the question. First, on purely Manhattan shapes the partition network should choose K = 1 and match BrECS, since there is nothing to gain. A gain there would signal a confound such as extra capacity. Second, across shapes, the IoU gain over axis-aligned BrECS should rise with the off-axis surface fraction. Third, the seam-voxel fraction should fall as resolution grows, and end-to-end time should grow close to linearly in occupied voxels while the sequential ablation grows with part count. If the gain does not track off-axis fraction, or the rotated-filter baseline matches us on both exactness and cost, the piecewise-Manhattan hypothesis is wrong for this problem.