This is a little algorithm I sketched in my moleskin on the train and for once had the free time to build. The idea is to split a convex polygon between two line segments, creating two new polygons. Each shape is pushed into a queue ready to be subdivided itself. Despite the simplicity of the algorithm, the results are quite nice and with certain configurations often far removed from what I would have expected – surprise is always good.
The Subdivide Algorithm
Here are the basic steps used to create the sketch above:
- Create the first polygon
- Pick two adjacent vertices at random
- Use linear interpolation to find a point between them (P1)
- You now have a point on one line segment connecting the two vertices
- Choose another line segment from the polygon
- Find a point along this line segment (P2)
- Build a new polygon by moving clockwise from P1 to P2
- Build a second polygon by moving clockwise from P2 back to P1
- Splice the original polygon from the list and insert the two new ones
- Choose a polygon from the list and (↑repeat)
Very simple, but you can start to have fun with each of these steps to produce different results. Here are some of the variations which can be created with the demo.
- Choose line segments to cut at random
- Always subdivide between the two longest line segments
- Always interpolate (choose points) half way along segments
- Choose points at random positions along line segments
- Only mark some polygons eligible for subdivision
- Vary the minimum area of divisible polygons
Source Code
The Polygon class is a DisplayObject (it extends Sprite) and implements it’s own draw method. I’ve had a lot of fun filling the shapes with textures, but kept it minimal for the example. One technique which I found worked well was to choose two vertices and compute the angle between them. From this I created a transformation matrix to use with Graphics.beginBitmapFill, giving the sketch a more 3 dimensional feel as if the collection of polygons was a 3D mesh with textures mapped to it. I’ll put these examples on Flickr soon.
If you’re interested in the source code, it’s available in my code repository or you can download the archive below (for the demo GUI, I am using minimal comps courtesy of Keith Peters and for image encoding, Ian McLean’s asynchronous JPEG encoder – thanks guys :).
Download: Recursive Subdivision
Cool!
I like the early stages in the demo – it almost looks like an ordinance survey map of a town changing from fields to cityscape.
I also like that I’m not the only person who sketches code ideas away from the computer in a moleskin!
Thanks Lawrie! Yes, I find I always prefer starting with a pen and paper, glad you do too. Who needs iPads :)
It reminded me of Jared Tarbell’s Substrate http://www.complexification.net/gallery/machines/substrate/
I’m sure you aware of his work, but if not then check it out – the source is all available, and the code is easily ported from Java to AS3
Yes I absolutely love that sketch and Jared’s work in general. I’ve also been pointed to Mario Klingemann Subdivision set on Flickr which is really nice: http://is.gd/cs4qq
That Mario Klingemann set is amazing – such a simple idea that produces something so captivating – I feel inspired!
Sweet!
I chose the manual approach to do this who is much more tiring for your fingers ;-)
Add a bit of colors, it will look awesome
http://peutichat.blogspot.com/2010/01/polygon-subdivision.html
Hi Mathieu. I couldn’t leave a comment on your blog so I’ll leave one here › Very nice work! I like how you’ve approached this and the results are very interesting. Mario would be proud of the Mona Lisa reference too I’m sure. Thanks for sharing.
this should be fun to play with….thanks
Nice!
Lovely blog, lovely images…
Have you considered adding some live ActionScript class diagrams to your code? Please check my address and think about.
It was reallly a nice blog with the effective & informative notes with beautiful image. I’m getting inspired with the image & with the informative algorithms in this excellent post. Thank you so much for sharing this post.