#packing problem

Space-filling tangent field

Sometimes, someone comes up with a technique that seems so obvious in retrospect that you wonder why you haven’t seen it before.

It’s not new (this ACM 2008 paper describes the technique) but if I’ve seen it before I didn’t remember it. Or maybe I just connected to the context in the right way this time.

So, what the heck is a tangent field and how can you use it to generate a city? A vector field is a field of vectors--that is, for each point in the space there is an arrow pointing in a direction, which can be shorter or longer. This should be fairly easy to understand if you’re already familiar with vectors: it’s just a bunch of vectors that each have a position in space. They can be useful for a lot of things, such as wind simulation, pathfinding, and crowd simulation.

A tangent field is a vector field on a surface, where the vectors are in tangent space--for a flat plane they’re lying flat on the ground. The city generator Stijn Raaijmakers made works by taking the weighted average angle (with the weight as 1/(r*r) where r is the distance to each tangent attractor) and generating a building there either along the tangent angle or perpendicular to it. This creates a densely packed space to sample from to give a degree of order to the placed buildings.

Packing problems come up quite a bit in procedural generation, especially where you’re trying to fill a space with content and don’t want any unsightly gaps. (There’s non-spatial applications of packing problems too, but we’ll leave that for another day.) Stijn’s generator reminded me that there’s a lot of useful research to draw on out there.

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.

Until my plane takes off. So much to do, so little sleep. My packing problem is almost been resolved. I get to the point where I think I'll be okay, then I look around at all the little things that I know I won't be able to cramm in there. The problem is my two coat. I am thinking one will go in my carry-on, along with my down comforter. Heh ^-^