«
»

Extracting, Analyzing and Optimizing a Vector Shape from a BitmapData Shape

This post has been a long time coming, as I've re-written the code more times than I care to recall. There are just too many ways to skin this damn cat! What I'm sharing now is not a final solution by any means. I just need to stop obsessing for a moment, move on and actually use the code for the cool things I've been planning to do with it! Then obsess further at a more suitable time :D

Also, retrospectively, this post is gonna take some courage and dedication to get through without falling asleep. The code was thrilling to conceive, but less so to write about. Apologies.

Anyway, the challenge is : Given extracted "shape outline points" from a BitmapData shape, I want to optimize these points into the minimum amount which correctly define that shapes perimeter.

Rather than going over the ifs, buts, successes and failiures, here's how the process currently works:

1) Remove redundant points from the "shape outline points"

Since the shape is extracted from a bitmap, the "outline" is composed of rows and columns. Any row or column longer than 2 contains "redudant" points (or pixels), between the start and the end of the line. These are easily removed by looping through the points, keeping track of the current row or column direction.

In the case of the F, the process is done, however, much more work is required for those pesky diagonals and curves...

2) Create "Line" Objects which connect the "non redundant" points

The optimization routines use net.sakri.flash.vector.VectorLine, which has the following properties:

  • start_point:Point
  • end_point:Point
  • type:uint VERTICAL, HORIZONTAL or DIAGONAL
  • direction:Point UP, DOWN, LEFT or RIGHT. Only relevant to VERTICAL and HORIZONTAL lines

The code loops through the "non redundant points", creating Lines. At this point, only VERTICAL and HORIZONTAL lines are present (again, due to the "rows and columns" nature of bitmaps). The loop sets each "line direction", based on the lines start and end positions. See the little red arrows below:

3) Use the directions of the "Line" Objects to discover "break points" or "turning points"

Essentially the goal is to isolate Lines, Diagonals and Curves. I have tried approaches ad infinitum, and so far the following delivers the most Bang For my Buck:

  • Loop through the lines, minding a "vertical anchor line" and a "horizontal anchor line".
  • Whenever the direction of lines changes from the current anchors, this can be seen as a "break" or a "turning point".
  • Store these "break points" in a list.
  • Use the "break point" as the current anchor, and continue looping.

The image below is a "single clockwise pass", the "turning points" are represented as blue pixels accentuated by totally awesome green circles.

Following the lines starting from the top left corner, you should "discover" the same "break points".

The first "horizontal direction change" takes place at the bottom right corner of the M. Up until this point all the horizontal lines go "RIGHT".

The first "vertical direction change" occurs at the bottom of the first "V" shape between the M's legs. Up until this point, all the verticals point DOWN, and after the turn point UP.

This first "pass" uncovers 10 break points, which could be used to analyze the "sub components" (deal with diagonals and curves). However, it's painfully clear that more break points are needed. In the "M", there are 13 which define the shape. So, a "second" pass sounds like a good idea, this time counterclockwise (or in reverse order). This results in different "break points" than the clockwise pass, (again just follow the lines with your eyes...).

Below is a "single counter-clockwise pass", the "turning points" are again visualized as blue pixels surrounded by gratuitous neon green pixels:

Putting these two together, running clockwise and counter-clockwise gives us:

Now we've got 16 break points for "M"! This is good enough, the main lines and diagonals are isolated. There was much rejoicement!

Here's the same for a character with some curves:

Nifty as this might sound, the approach isn't without it's shortcomings. "Staircases" and "Curve Staircases" are a thorn in my side. In such cases, there are "clear" changes in visual direction, yet, neither the HORIZONTAL nor the VERTICAL direction changes in a "staircase". Experience the phenomena in characters including T,F,4,S,a, etc. etc. Witness the F below:

At this point, we say "F it", and move on.

4) Use the "break points" to cut the shape up into segments, and analyze

Loop again. This time looking at the sets of VectorLines separated by "break points":

  • Any set of 1 must be a Vertical or a Horizontal line.
  • Detect Diagonals
  • Handle Curves and "complex shapes"

Here's my "CPU Cheap" approach to detecting a Diagonal in a set:

PLAIN TEXT
Actionscript:
  1. protected var _diagonal_buffer:Number=.15;
  2.         protected function isDiagonal(lines_vect:Vector.<VectorLine>,index1:uint,index2:uint):Boolean{
  3.             var first:Point=VectorLine(lines_vect[index1]).start_point;
  4.             var middle:Point=getMiddlePointInVLineSegment(lines_vect,index1,index2);
  5.             var last:Point=VectorLine(lines_vect[index2]).start_point;
  6.             var diff:Number=Point.distance(first,last)-Point.distance(first,middle)-Point.distance(middle,last);
  7.             return Math.abs(diff)<_diagonal_buffer;
  8.         }

The code grabs the "middle point" within a set of Lines. Then it compares the distance from the "sets start point to finish point", with the added distance of "start TO midpoint+midpoint TO endpoint". If the difference is less than "_diagonal_buffer", it's a diagonal. Accept it.

The remaining shapes fall under the categories of "Curves" and "Complex Shapes". Both can actually be treated the same : Based on a parametrized "Curve Accuracy", the remaining shapes can just be divided into "sub segments".

Let's say a Curve has 200 pixels, which might translate to 50 "Lines" once "redundant points" are removed. If "Curve Accuracy" is set to 15, it's relatively easy to loop through the 50 lines, and isolate them into "Sub Lines" grouped by this "Curve Accuracy". Maybe an easier way to picture this is just to chop up a curve by choosing every X points along it's path. If that makes no sense, just check out the code.

There's a few more optimizations, but I can't be arsed to go into it right now. This post is long enough as it is.


Click here for the demo (Comic Sans pictured below):

Download the Source (Requires FlexBuilder, with sdk 3.2+)

Congrats, give yourself a hearty pat on the back for making it all the way through! You have our Gratitude! I personally guarantee future posts with better entertainment value using this code base and it's oncoming descendants :D

Tags: , , , , , , , , ,

This entry was posted on Tuesday, April 28th, 2009 at 9:09 pm and is filed under AS3, experiment, Flash, flex. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to “Extracting, Analyzing and Optimizing a Vector Shape from a BitmapData Shape”

  1. Campbell Says:
    April 29th, 2009 at 3:49 am

    Might pay to also check out http://www.libspark.org/wiki/nitoyon/PotrAs

    Samples http://www.libspark.org/svn/as3/PotrAs/samples/potras/demo20070929/bin/

  2. sakri Says:
    April 29th, 2009 at 5:30 am

    Thanks Campbell! Nicely spotted :)

    I’ll try to make a comparison between these two, I had a brief look at the potr source code, it’s fascinating to see someone elses approach to this problem!

  3. Alpha Says:
    February 9th, 2011 at 8:27 pm

    Question:
    The getVectorShapeLinesWithBoundary() call doesn’t seem to need a boundary higher than 1, is the default of 5 and the used value of 4 just a guess for safety or am I missing something?

    Idea:
    Looks like you could avoid the CCW sweep by making the previous point checked a breakpoint each time you find a breakpoint.

Leave a Reply