Optimizing cut lists with bin-packing

I am building subwoofer CAD and design software, and I needed a cut list optimizer for it. After tuning the enclosure and setting its parameters, the designer produces the panels needed to build it. Those panels then go to a tool that works out how to cut them from the stock material available.

I couldn't find a library that did what I needed. I wanted something fast that I could use through WebAssembly, with enough control over the stock and cutting constraints to produce useful results. I built bin-packing in Rust for that part of the project, then expanded it to handle other dimensions as well.

The bin-packing problem

This is a version of the bin-packing problem. Given a set of items and containers with fixed capacities, how can you fit all the items while using as few containers as possible? For my cut list, the items are rectangular panels and the containers are sheets of material.

Total area gives you a starting point, but geometry decides whether the parts fit. Two 600 by 600 mm panels have less combined area than a 1000 by 1000 mm sheet. Even with no kerf, they cannot sit side by side or one above the other on that sheet. There is enough area, but neither dimension can accommodate both panels.

Placement order and rotation add more choices. A panel can leave a long, narrow offcut in one position and a larger usable space in another. As the number of parts grows, checking every possible arrangement becomes expensive. This is why a cut list optimizer needs a strategy for finding and comparing promising layouts.

Turning panel dimensions into a cut list

Knowing the dimensions of the panels is only part of the problem. You also need to know which sheets are available, how many of each you have, and how much material the blade removes between parts. That last measurement is the kerf. A layout that ignores it can show parts fitting where there is not enough material to make the cuts.

The 2D solver accepts rectangular parts with dimensions and quantities, plus the sheet stock to place them on. Each sheet type can have its own size, cost and inventory limit. A rotation flag on each part controls whether the solver can turn it to get a better fit.

The cutting method matters too. Setting guillotine_required restricts automatic selection to layouts built with straight cuts across the current piece of stock. This is useful for saw-based work, where an efficient arrangement also needs to be practical to cut.

Running the optimizer through WASM

Rust gives me one core implementation that I can use natively or compile to WebAssembly. In the subwoofer workflow, the design software sends its panels to the tool using the WASM build to generate the cut list. The optimization can run in the browser without sending the layout to a server.

The WASM package has a smaller 2D entry point for applications that only need sheet layouts. Install it with:

pnpm add @0xdoublesharp/bin-packing-wasm

This example uses version 0.5.0 and the browser ES module entry point. Initialize the module once before solving. All dimensions below are in millimeters, including the 3 mm kerf:

import init, { solve2d } from '@0xdoublesharp/bin-packing-wasm/two-d/web';

await init();

const solution = solve2d(
  {
    sheets: [
      { name: 'plywood', width: 2440, height: 1220, kerf: 3, quantity: 1 },
    ],
    demands: [
      { name: 'large-panel', width: 600, height: 400, quantity: 2, can_rotate: true },
      { name: 'small-panel', width: 400, height: 300, quantity: 4, can_rotate: true },
    ],
  },
  { algorithm: 'auto', guillotine_required: true, seed: 42 },
);

console.log(solution.sheet_count); // 1
console.log(solution.unplaced);    // []

These sample parts fit on one sheet with nothing left unplaced. The layouts array contains each part's position, dimensions and rotation, which a calling application can use to draw the result. Check unplaced before treating a result as a complete cut list.

Use consistent integer units throughout a problem. If finer precision is needed, scale every dimension and the kerf together. For larger jobs, the WASM call can run in a Web Worker so the interface can respond while the solver works.

Choosing how to search

A quick layout is useful while changing a design. When it is time to buy material or start cutting, spending more time comparing candidates can be worthwhile.

The library includes MaxRects, Skyline, Guillotine and other packing strategies. Automatic mode compares several strategies and returns the best candidate it finds. Individual algorithms can be selected directly, and a seed makes randomized searches repeatable. Heuristic packing finds useful layouts, but does not establish that every result is a globally optimal arrangement.

That control was part of what I wanted from a library. The application can choose how much searching to do for its current task while using the same stock and part definitions.

Beyond subwoofer panels

The original need was sheet material for an enclosure, but the underlying problem applies to other projects. The 1D solver assigns required lengths to linear stock such as bars or pipe, with kerf and trim included. The 3D solver places boxes into bins and supports limits on how each item can rotate.

The core is available as a Rust crate, with separate Node.js and WebAssembly packages for JavaScript and TypeScript applications. The WASM build targets wasm32-unknown-unknown and ships entry points for bundlers, browser ES modules and Node.js. It can run in browsers, Node.js, Deno, Bun and Cloudflare Workers. Keeping the optimizer separate from the subwoofer designer lets other applications use it with their own parts, materials and displays.

The library page has more examples. See the README for the current algorithms, options and cut-planning APIs.