Generating Collages with PAD

“Pyramid of Arclength Descriptor for Generating Collage of Shapes,” by Kin Chung Kwan, Lok Tsun Sinn, Chu Han, Tien-Tsin Wong, and Chi-Wing Fu, is a research paper on filling a specified shape with a collage of images.

The results are quite nice:

The technique supports a number of additional settings and constraints. They can even loop infinitely:

While the authors concentrate on the use in collage and design (and this will undoubtedly be a highly-useful design tool that someone will rip off for a music video or ad in the next year or two) I can’t help think of the wider applications.

As I’ve said before, any procedural generation technique can be attached to many other techniques. What if you built a map generator out of this? It wouldn’t need to be constrained to rectangular shapes; you could use any curving shape.

Or, more mundanely, laying out a texture sheet or a UV atlas. While there’s been quite a lot of work in this area, existing algorithms have their own drawbacks. Broader still, packing problems are very common in many industries. How many shapes can you cut out of one board? How do you load the most items on a pallet?

While this algorithm doesn’t guarantee the maximum efficiency, it does work with arbitrary irregular shapes, and it uses a search space rather than a time-intensive process like physical simulation.

http://www.cse.cuhk.edu.hk/~ttwong/papers/pad/pad_lowres.pdf