HashTable: An Algorithm for Material Reuse

March 29 2010

There is a great deal of waste in fabrication shops. According to our observation, 1/2 - 2/3 of the material surface area is left out in most CNC cuts. Due to their irregular shape, scrap material usually fails to fulfill another cutting request and are therefore discarded.

In MadFab – an MIT student furniture design competition – we proposed a program that recognizes usable regions from the photos of scrap material and algorithmically search for an optimized layout to cut out a given design. Unlike ordinary digital fabrication systems, this process contains feedback loop from the physical object to the CAD environment to the physical object. By doing this, the material cost and waste of digital fabrication may be greatly reduced.

To implement the process, the user should photograph scrap sheets on a distinct background:

Step 1 - Photograph Material

Then, through an interface implemented in Java, the user may pick a size and shape for the desired table/bench. The program will vectorize the photos and recognize reusable regions.

Step 2 - Import Into Program

It will then search within these regions proper placement for the parts of the table. If a part is too large to fit in, it will be subdivided in a way that can be reassembled. Finally, the program will output the results to files that can be directly sent to the CNC cutting technology of choice (laser, router, water jet).

Step 3 - Output CAD File

Step 4 - Lasercut

After cutting the scrap material, the final pieces can be assembled following an instruction generated by the program.

Step 5 - Assemble Step 6 - Finished Model

At this stage, the algorithm has been fully implemented. In the mock-up program the shape of table is chosen among six Cyclotomic Rhomb 7-Fold Tiling shapes which can be subdivided into their scaled selves.

Program Screenshot

Placing the parts is recognized as a 2-D packing problem with irregular shapes. In our current implementation pieces are placed in the order of area. The quality of a placement is measured by the distance between the vertices of the piece to the vertices of the scrap sheet. A hill-climbing algorithm is used in the searching.

The project was final-listed in the competition.

Collaborated with Ari Kardasis.

lasercut recycling Processing