Difference between revisions of "TSP art"
(TSP art page -- initial upload) |
|||
| Line 1: | Line 1: | ||
Likenesses of images can be made by processes of halftoning, dithering, or stippling as well as other techniques as shown in the four images below. (Left to right: original color image, grayscale dithered image, halftoned image, and a stippled image) | Likenesses of images can be made by processes of halftoning, dithering, or stippling as well as other techniques as shown in the four images below. (Left to right: original color image, grayscale dithered image, halftoned image, and a stippled image) | ||
| − | [[http:/mtbaldy.us/~dnewman/tspart/mona-quartet.jpg]] | + | [[http://mtbaldy.us/~dnewman/tspart/mona-quartet.jpg]] |
However, to produce an image on the Eggbot, we want a process that not only generates a pleasing likeness of the image, but is also recognizes the Eggbot's mechanical nature. Pen plotters such as the Eggbot excel at drawing long, continuous paths but are mediocre at drawing thousands of small, shaded fills (halftones, dithers). Pen plotters are somewhat better suited to drawing thousands of small circles or points (stipples). With stippling, an image's grayscale tonal quality is reproduced by drawing more stipples in darker regions of the image and fewer in lighter regions. That is, the density of stipples in a given region of the canvas increases with increasing darkness in the same region of the original image. Unfortunately, even stippling can be challenging to the pen tip of a pen plotter. And, the many pen-up and pen-down operations are slow relative to drawing connected segments of lines. | However, to produce an image on the Eggbot, we want a process that not only generates a pleasing likeness of the image, but is also recognizes the Eggbot's mechanical nature. Pen plotters such as the Eggbot excel at drawing long, continuous paths but are mediocre at drawing thousands of small, shaded fills (halftones, dithers). Pen plotters are somewhat better suited to drawing thousands of small circles or points (stipples). With stippling, an image's grayscale tonal quality is reproduced by drawing more stipples in darker regions of the image and fewer in lighter regions. That is, the density of stipples in a given region of the canvas increases with increasing darkness in the same region of the original image. Unfortunately, even stippling can be challenging to the pen tip of a pen plotter. And, the many pen-up and pen-down operations are slow relative to drawing connected segments of lines. | ||
Revision as of 15:35, 26 September 2010
Likenesses of images can be made by processes of halftoning, dithering, or stippling as well as other techniques as shown in the four images below. (Left to right: original color image, grayscale dithered image, halftoned image, and a stippled image)
[[1]]
However, to produce an image on the Eggbot, we want a process that not only generates a pleasing likeness of the image, but is also recognizes the Eggbot's mechanical nature. Pen plotters such as the Eggbot excel at drawing long, continuous paths but are mediocre at drawing thousands of small, shaded fills (halftones, dithers). Pen plotters are somewhat better suited to drawing thousands of small circles or points (stipples). With stippling, an image's grayscale tonal quality is reproduced by drawing more stipples in darker regions of the image and fewer in lighter regions. That is, the density of stipples in a given region of the canvas increases with increasing darkness in the same region of the original image. Unfortunately, even stippling can be challenging to the pen tip of a pen plotter. And, the many pen-up and pen-down operations are slow relative to drawing connected segments of lines.
Sounds like we want a means of reproducing an image by drawing continuous paths, and preferrably as few distinct paths as possible....
Welcome to "TSP art" in which an image's tonal quality is reproduced with a *single*, continuous path. This single path meanders over the entire canvas. Like stippling, segments of this path appear more frequently in regions of the canvas which correspond to darker regions in the original image. And, fewer segments of the path in lighter regions. A method of determining how to draw this single, continuous path can be achieved by treating the question as a Travelling Salesman Problem (TSP). By first producing a stippled representation of the image, we pose the question of the Travelling Salesman: what is the shortest possible path that visits each and every stipple exactly once and then returns me to my starting point? Determining the correct answer is actually very hard (NP-hard). But, even fast approximate answers work well with the Eggbot.
![[1]](http://mtbaldy.us/~dnewman/tspart/mona-quartet.jpg){kind=link}