Parallelized String Art

Author

Catherine Yu (tianhony) Nanxi Li (nanxil1)

Proposal & Reports

Proposal Checkpoint Report Final Report Slides Presentation Recording

Summary

String art is an image solely composed of strings between pins around a circular canvas. We implemented a parallelized string art solver in C++ and CUDA that computes the string art best resembling the input image. We developed our algorithm from scratch based on the sequential greedy approach proposed in paper by Brisak et al. We modified the proposed algorithm while implementing our sequential version of the solver, so that algorithm would have more parallelism to exploit while outputting more accurate string art image. We then developed our parallel version of the solver, which produces the same output as the sequential solver in a considerably shorter runtime. We were able to achieve an over 221x speedup on a 512*512 image with 128 pins.

See Final Report for more information.

Background

First of all, what is string art? String art is a technique for the creation of visual artwork where images emerge from a set of strings that are spanned between pins. It is traditionally done with strings wounding around a grid of nails hammered into a velvet-covered wooden board. Here is a video explaining how it is done.

The above two images are taken from work by Birsak et al. and Petros Vrellis Petros.

We are going to use the algorithm presented by Birsak et al in his research paper. This algorithm will not produce a solution using a single continuous thread, but many discrete edges.

References

Michael Birsak et al. “String art: towards computational fabrication of string images”. In:ComputerGraphics Forum. Vol. 37. 2. Wiley Online Library. 2018, pp. 263–274 link

Exception1984. Exception1984/StringArt. link.

Jblezoray. jblezoray/stringart. link

petros vrellis petros. A new way to knit (2016). link