Publications / 2018 / Sequencing in Transformation of Rasterized 3D Models

Sequencing in Transformation of Rasterized 3D Models

Wei Pan

Singapore University of Technology and Design

In one sentenceThis thesis turns reshaping a structure of voxels, LEGO bricks or chained cubes into a sequence of moves a machine can follow, keeping the total work low while respecting how parts can be picked, placed and folded.

The problem

A rasterized 3D structure is built from discrete, equal-sized parts, the way a picture is built from pixels: voxels in a computer, and cubes, bricks or food cans in the physical world. Such parts are easy to process as data, easy to reuse and suited to mass production. The thesis asks how to change one such structure into another. It frames this as a transformation from a source structure to a destination structure, and looks for an efficient sequence of operations that a machine can follow, with efficiency measured by an application-dependent cost function. Building a structure from a material palette is a special case, in which the source is the palette.

The difficulty is that the problem is discrete. Even deciding which part goes where is a combinatorial problem: for n parts there are n! possible assignments. The lowest-cost assignment is not necessarily executable either. A suction gripper can only pick parts on the top surface, a LEGO brick cannot be picked while other bricks cover or surround it, and a brick cannot be placed where it would hang in the air. Sequencing therefore has to trade the total amount of work against physical feasibility, and for bricks also against how many of the source parts are reused.

Four stages left to right: mesh models of a spiral staircase and a mountain; the same two models made of grey voxels; the two voxel models overlaid, part of them in green; and two intermediate states, with red highlights, followed by the final mountain shape. — The task for voxel structures: (a) input meshes of the source (a spiral staircase) and the destination (a mountain), (b) the rasterized models, (c) alignment, and (d) a motion sequence that turns the source into the destination. Fig. 3.1 of the thesis.

How it works

The thesis studies three cases that, in its words, represent the majority of sequencing problems for transforming and shaping rasterized structures: pick-and-place of homogeneous voxels (Chapter 3), pick-and-place of heterogeneous LEGO bricks (Chapter 4), and folding of voxel chains (Chapter 5). The explainer follows the thesis’s worked voxel example step by step, then places the other two cases alongside it.

Align and classify. Both mesh models are rasterized into voxels. Assuming they are already aligned vertically and only translation is allowed, an exhaustive search in the horizontal plane finds the alignment with the largest overlap. Voxels present only in the source are movers (M), voxels present only in the destination are voids (V), and overlapped voxels stay where they are. If the numbers of M and V differ, the extra voxels go to, or come from, a linear stack.
Price every move. The cost function models a three-axis Cartesian machine that moves sideways only at a clearance plane z_max: the cost c_ij of moving mover i into void j is c_ij = |x_j − x_i| + |y_j − y_i| + 2z_max − z_i − z_j. Pairing every M with a V at minimum total cost is an assignment problem, which the Hungarian method solves in O(n³) time instead of comparing n! options.
Respect top access. With a vacuum suction gripper, only voxels on the top surface can be picked or placed. Pairing all M and V at once (the global optimisation strategy, GOS) gives a lower bound on the cost, but the pairs may deadlock. The local optimisation strategy (LOS) builds the cost matrix only from the M and V that are currently accessible, applies the Hungarian method, and moves those pairs.
Update and repeat. After each round the top surfaces change, a new cost matrix is built, and the process repeats until every M has been placed. In the worked example LOS reaches a total cost of 27, the same as the GOS lower bound. Two simpler baselines are also compared: a greedy strategy (GSS) that moves only the single cheapest accessible pair at each step, and a random one (RSS).
Extend to bricks and chains. Bricks (LEGO). Voxels are merged into bricks layer by layer. The rigid approach (RT) generates both brick layouts before transformation, and the flexible approach (FT) generates the target layout on the fly, preferring brick types that are movable on the source. Each approach is combined with three strategies for routing bricks through a buffer and a stock (see the figure below), giving six algorithms, RT1–RT3 and FT1–FT3, named after the approach and the strategy number.
The algorithms are scored by cost (the number of pick-and-place actions), reuse rate (the share of source bricks that end up in the target) and an overall performance that grows with reuse and falls with cost.
Chains. A shape is turned into a 1D string by finding a Hamiltonian path through its voxels. The path is made possible either by pruning and appending voxels or by dividing each voxel into 4 (2D) or 8 (3D) sub-voxels. The fold is then planned from the difference between the start and target joint angles.

Two grid diagrams side by side. In (a), two pink cells labelled 1, 5′ and 8, 6′ sit on top of grey cells, and two green cells labelled 4 and 5 lie on the ground to the right; red bars mark the top surfaces. In (b), the green cells are gone and two pink cells labelled 4, 7′ and 5, 8′ sit on top of the stack. — The two LOS stages of the worked example: (a) movers 1 and 8 are placed into voids 5′ and 6′; (b) movers 4 and 5 are placed into voids 7′ and 8′. Red bars mark the top surfaces. Fig. 3.6 of the thesis.

Three rows, each showing a LEGO source model on the left and a different LEGO target model on the right. Row 1 routes bricks from the source through a cyan buffer box, with a grey stock box also feeding the target. Row 2 adds a direct arrow from source to target above the buffer. Row 3 has only the direct arrow and the stock. — The three brick strategies. Strategy 1 disassembles the source completely into a buffer, then builds the target from the buffer and a stock. Strategy 2 moves bricks directly from source to target, and disassembles into the buffer only when no suitable brick is available. Strategy 3 builds the target from the source and the stock, with no buffer. Fig. 4.6 of the thesis.

The letters A and O, each rasterized into a grid of 28 square pixels, then each traced by a single red path that visits every pixel once; a curved arrow labelled Folding points from the A path to the O path. — Folding: the letters A and O are rasterized into 28 pixels each, a Hamiltonian path (HP) turns each shape into a string, and the A string is folded into the O string. Fig. 5.1 of the thesis.

Results

The voxel strategies were tested on eight models (wall, pyramid, starfish, cube, igloo, castle, stairs and the Eiger mountain), each rasterized to between 2,250 and 2,550 voxels and transformed into every other. GOS always gives the lowest cost but does not by itself define a feasible sequence, and it is the slowest, because it runs the Hungarian method once on a very large cost matrix. LOS is second in cost, GSS slightly worse, and RSS clearly worse but fastest. The work is set by the number of M-V pairs, not by model size: wall → pyramid needs 1,643 pairs, while the more similar pyramid → igloo needs only 325. Across rasterization resolutions, the total cost grows about linearly with the number of pairs, and so does the time of LOS, even though the Hungarian method itself is O(n³). LOS stands out for the balance it strikes between cost and computation time. Its stated limitation is the top-access constraint, which rules out overhanging structures. Bricks that lock together, like LEGO, can form overhangs, which motivates the LEGO chapter.

Left: grouped bar chart of total cost in thousands for GOS, LOS, GSS and RSS at 139, 246, 364, 793, 1624 and 2016 M-V pairs; costs rise steeply with the number of pairs and RSS is highest. Right: computation time in seconds against M-V pairs; the GOS curve shoots off the top of the chart before 500 pairs, while LOS, GSS and RSS stay below about 22 s up to 2,000 pairs. — Total cost (a) and computation time (b) of the four strategies for the starfish → castle transformation at different rasterization resolutions; more M-V pairs means a higher resolution. Fig. 3.9 of the thesis.

For LEGO, eight triangle-mesh models were converted to brick models. In the average over all pairwise transformations, cost rises linearly with model size, and Strategies 1, 2 and 3 cost successively less. Strategies 1 and 2 reach very similar reuse rates, so the thesis concludes that disassembling the whole source up front is not worthwhile. FT reuses more bricks than RT, but its bricks tend to be smaller than the best fit, which gives weaker structures with internal sliding planes and more bricks in the target. FT3 reaches a reuse rate comparable to the best RT algorithms, and in the transformations from one model to the other seven it matches the reuse of FT1 and FT2 at a much lower cost. With colour information (114 colours, and exterior bricks must match in colour as well as shape), reuse falls but does not drop to zero, because interior bricks may take any colour. The thesis notes that the overall-performance metric is empirical, and that the relative ranking may change in scenarios that define cost differently.

Three line charts side by side, each against model size from about 500 to 4,500 voxels, with lines for FT1, FT2, FT3, RT1, RT2 and RT3: (a) cost in pick-and-place actions rising linearly, (b) reuse rate in percent, with RT3 far below the others around 35 to 48 percent, and (c) overall performance, with FT3 clearly highest. — Average performance of the six brick algorithms over transformations among eight models, at seven model sizes: (a) cost, (b) reuse rate and (c) overall performance. The three panels, stacked vertically in the thesis, are placed side by side here. Fig. 4.9 of the thesis.

Two directions are left as future work: adding force analysis such as finite element analysis, so that intermediate structures as well as the final one are stable, and transforming at the level of modules (groups of parts moved as a whole) rather than single parts, which the thesis expects to improve both reuse rate and cost.

Cite

@phdthesis{pan2018sequencing,
  title={Sequencing in Transformation of Rasterized 3D Models},
  author={Pan, Wei},
  year={2018},
  school={Singapore University of Technology and Design}
}

Type

Thesis

Topic

Computational Design

Venue

Singapore University of Technology and Design

Year

2018