here’s a nice twitter story…

sakri released a marching squares algorithm which is a fast and efficient way to outline rasterized shapes.

in the comments, Alan Shaw mentioned the Potrace library and its AS3 port : PotrAS which belongs to the (kick ass) Spark project.

then I left a comment saying that I thought it wouldn’t be a big deal to do the same and vectorize many shapes once we have the outline algorithm so I gave it a go.

all I did ( and which is far from perfect :/ ) is to perform a component labelling pass and vectorizing each found component.

In sakri’s article comment, I mentioned a line generalization method done by Andreas Weber and that can be found here

the shapes detected by the marching squares are exact but that may not be what we want, so I gave the choice of having this simplifying function to run after vectorizing a shape. The resulting path is much lighter yet somehow much more crispy.

so lastly, as I had already done a CubicPath method to smooth a set of points, I piled it up to the result and it looks good :)

now here’s an explaination of how things works :

and there’s a quick demo to play around:

check the smooth checkBox to get a lovely result :)

then a couple of outputs:

basic lossless vectorization

simplified shapes

smoothed simplified shapes
some more here

and finally the classes + fla (CS4 needed because of the use of Vector.<T>…)

this is a rather convincing test, I kept it quite simple: there’s a VectorShape dataHolder and the Vectorize class.
yet there are still thing to be improved and especially in the Vectorize.process() method:

• there are huge problems with color processing like disappearing or misinterpreted colors -> should fix that
• for the moment I’ve done a single method to process all the components -> should be split in a recursive /non blocking loop
• - I’m performing the simplification during extraction -> has to be done later maybe within the VectorShape class
• embed the smoothing method into the Vectorize class
• solving the Z-sorting/overlapping issue (tough) at least growing up region a bit not to leave blank spaces(tough)
• and of course optimization issues, I guess the per pixel approach is one of the slowest possible :)

limits:

• poor output with detailed pictures ( =photos )
• poor output with color pictures (too segmented)
• heavy process but might be improved

perspectives:

• 2D graphic outputs: sweeeeet curves from rastered images
• huuuge graphics with little data
• 2D physics : as we get the shapes overmore optimized, we could triangulate them to insert them into Box2D !
  well actually I ‘ve done it already and it is lots of fun to hand draw the shapes and include them to box 2D ^^
• 3D : sakri’s eagerly intending to extrude some shapes. noble goal, I think he’s close enough to say it’s done.
• from a purely formal perspective, ADs will surely find things do with it ^^

oh I almost forgot : there was of course an online vectorization tool : vectormagic (damn I hate softwares with the word ‘magic’ in the name)
or raven from the online graphic software suite aviary

and as Philippe Elsass would twit it: ‘the smooth vectors look rather professional – reminds me of (this good old)Streamline’
enjoy :)

edit: I’ve corrected some mistakes and uploaded the files should work better now

Tags: BitmapData, component, geometry, labelling, streamline, vector, vectorization