Recursive Subdivision

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
Posted on 27 May 2010
16 Comments
1 Trackbacks

Meta

Recursive Polygon Subdivision was posted on May 27th 2010 in the category Lab / Actionscript 3.0, Code, Design, Flash, Generative, Lab, Open Source and tagged; , , , , , .

You can Leave a comment.


Warning: file_get_contents(http://search.twitter.com/search.atom?q=from:soulwire&rpp=1) [function.file-get-contents]: failed to open stream: HTTP request failed! HTTP/1.0 410 Gone in /home/soulwire/webapps/soulwire_blog/wp-content/themes/soulwire/functions.php on line 203

Discussion

12 Responses to Recursive Polygon Subdivision

Leave a Reply

Pingbacks / Trackbacks

  1. 3 years ago rdg::preset - In Polygongewittern » 0003_0004

    [...] This Procedural Plagiarism was inspired by Soulwire’s “Recursive Subdivision“. [...]

  1. Lawrie 4 years ago

    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!

    Reply to this comment

    1. Soulwire 4 years ago

      Thanks Lawrie! Yes, I find I always prefer starting with a pen and paper, glad you do too. Who needs iPads :)

  2. Jon B 4 years ago

    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

    Reply to this comment

    1. Soulwire 4 years ago

      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

    2. Jon B 4 years ago

      That Mario Klingemann set is amazing – such a simple idea that produces something so captivating – I feel inspired!

  3. Mathieu Gosselin 4 years ago

    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

    Reply to this comment

    1. Soulwire 4 years ago

      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.

  4. simon 4 years ago

    this should be fun to play with….thanks

    Reply to this comment

  5. J 4 years ago
  6. Chris 4 years ago

    Lovely blog, lovely images…
    Have you considered adding some live ActionScript class diagrams to your code? Please check my address and think about.

    Reply to this comment

  7. Prakash 3 years ago

    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.

    Reply to this comment