CIRCLE PACKING

Circle packings are nice. They are geometrically quite fascinating and visually appealing. But besides, they also have some interesting applications in computational and differential geometry, especially since Thurston linked them to conformal mappings. Using Houdini, we are well equipped with different operators in Sops and Dops which enables us to generate some kind of pseudo-circle packings pretty much out of the box. We could use the ScatterSop and a point cloud lookup in a SopSolver, we could use Grains, or maybe Bullet together with constraints, we could use microsolvers or any other method one can think of but generally the result won’t be a perfect circle packing. Most of the time this is not much of a problem as long as we just need something that looks like a circle packing but doesn´t has to be one. But if we need a real circle packing in which every circle is tangent to its surrounding neighbors, we´ll have to set up things a bit differently. Exactly this was the situation I was in some time ago. So I finally had a reason to implement a circle packing algorithm. The implementation I did, is basically an iterative relaxation method based on a paper by Collins and Stephensons. It’s fast and fairly easy to implement.

C. R. Collins, K. Stephenson: A circle packing algorithm

Circle packings based on the famous “butterfly.pic” images shipped with Houdini.

The algorithm described by Collins and Stephenson is about precise circle packings in the plane but with some workarounds it also does a good job on a surface. Even though a real circle packing does not exist on an arbitrary surface, it’s possible to achieve a fairly good approximation.

For much more about circle packings, check out Ken Stepenson’s page.