Hand-sized drone uses camera and motion capture to paint stippled prints (with video)

Dot drawing time is minimized using a "traveling salesman" algorithm.

Hand-sized drone uses camera and motion capture to paint stippled prints
Hand-sized drone uses camera and motion capture to paint stippled prints
(Still from video: McGill University) Paul Kry and a few of his students at McGill University’s School of Computer Science (Montreal, QC, Canada) have teamed up to program a handheld drone to create drawings by dabbing a brush repeatedly on paper, an artistic technique known as stippling (see video).(Video: McGill University) Programming the aerial robots to apply each payload of ink accurately and efficiently requires complex algorithms, including motion capture to keep the drone aware of its position, and an algorithm that tries to approximately solve the "traveling salesman" problem to minimize the time it takes to make the drawing. (The traveling salesman problem has to do with finding the minimum path a salesman needs to travel to visit all locations in a random cloud of points representing customers; for large numbers of points, the globablly optimum solution becomes impossible to find even with great computing power.) The drones, which are small enough to fit in the palm of a hand, are outfitted with a miniature arm that holds a bit of ink-soaked sponge. As they hover near the surface to be painted, internal sensors and the motion-capture system help position them to dab the ink in just the right places. So far, the flying robots have rendered portraits of Alan Turing, Grace Kelly, and Che Guevara, among others. Each drawing is composed of a few hundred to a few thousand black dots of varying sizes. Eventually, larger drones could be deployed to paint murals on hard-to-reach outdoor surfaces, including curved or irregular facades, Kry says. Source: https://www.mcgill.ca/newsroom/channels/news/dot-drawing-drones-261928 REFERENCE:

1. Galea, Brendan et al., Eurographics Association May 2016 Expressive symposium; http://dx.doi.org/10.2312/exp.20161071

More in Software