sakri rosenstrom blog

Here’s a demo I made for my presentation at multi-mania. I played around with verlet integration before and have long wanted to try this technique on text. Once I got the vectorization going, it was just a matter of connecting all the points to “Verlet Sticks”.

This turned out to be a little tougher than expected. The tricky thing about Verlet Sticks, is that if you connect the same Verlet Point to multiple Verlet Points, the calculations go berzerk, and your shape quickly vanishes from the canvas into the ether. So the challenge was to find a way to connect all the points of a vector shape, with a minimum number of “individual connections”, yet in a way that maintains the integrity of the shape. Keyboard cat played me off multiple times in my attempts .

Finally, the solution I landed on, was to create a grid out of all the points. The idea is to create a boundary rectangle, which maintains it’s shape via “cross sticks”:

Then, create a grid using all the points of your vector shape(s), in such a way that each point connects to a subdivision of the outlines of that “boundary Rectangle”:

In the image above you can see the “boundary rectangle” surrounding the vector shape. Then, each point is connected with a vertical and horizontal line. These verticals and horizontals are then connected to a “subdivided” boundary rectangle.

In the demo you can turn “render sticks” on and off to visualize the trick.

Strengths:

• Can handle pretty much any set of shapes and subshapes

Weaknesses:

• Due to the “Boundary Rectangle” the shapes “bouncing” is limited, a “T” for instance can’t lie diagonally, it always ends up on one of the four sides of the rectangle.
• The vertical and horizontal lines shouldn’t have more than two subdivisions. To fix this, the code first checks for all points along the same x and y, then shifts any instances above 2 by .5 pixels each. It’s practically invisible, but it’s there.
• Doesn’t support transparency, I guess this could be done with a blendmode or so…
• More complex shapes can still spazz out and disappear

Click to try out the demo here . Ignore the collision physics, it’s CRAP! The effect works best with “pixel fonts”. The controls are :

• RENDER : renders the input text with the selected font
• UPDATE : update one frame of animation (when stopped)
• PLAY : updates the animation on an enter frame
• BOUNCE : when the characters are just skidding the floor, spice things up by clicking this button

The code is DIRTY, but does the trick. I’ve uploaded the source for the brave (or desperate ). It’s the same project that I’ve been using for my last 5 or so blog posts, so there’s a lot of redundant code in there. Download it here.

ext steps:

• compose a clean “all purpose” class for generating such a grid
• Render shapes with curves, using the drawing api
• Use nicopteres vectorization code to do this with photos…
• Improve the curves and optimization, again I think I can use some code from nicopetre

I just wanted to put this out there because, well, it’s kind of nifty… More to come, enjoy!

.

Last week a kind individual called "Rothrock" commented on an older blog entry of mine Extract shape outline points from BitmapData and pointed me to the Marching Squares Algorithm.

(Image ruthlessly stolen from wikipedia without remorse)

This does more or less what my "outline point extraction" algorithm was doing, except, with a grid of 4 pixels instead of 9. I nearly choked at the thought of how wasteful my previous approach was. So, I promptly implemented the algorithm in as3, and tested out the speed difference.

Indeed, Marching Squares pwns and humiliates my older implementation, it's 2-3 times faster. This due to the fact that the source bitmap data does not need to be doubled in size, and naturally less pixels require inspection.

However, there are two gaping problems with this 4 pixel grid approach.

1) 'Single pixel vertical and horizontal lines' result in duplicate points

Although the 4grid handles such "single pixel lines" like a champion, it "scans" those points twice (see the line at the bottom of the wikipedia image above). If the goal is to (let's say) extrude this shape, problems just might ensue. So my implementation allows for a parameter which returns only unique points.

2) There is a special case which causes an eternal march. Poor squares.

If you consider the grid variations on that wikipedia page image, the squares march right into our lonely pixel, and keep doing circles Ad infinitum.

The best solution I could come up with, and please don't hesitate to share a better one, was to set a MAX_POINTS value. If the number of discovered points exceeds this, then the algorithm stops, and hands the task over to... wait for it... my old approach I refactored this into a class called MarchingSquares9Grid.as . This one has no duplicate pixels by the way, thanks to the double sizing of the source bitmap.

Click the images below to see the algos in action:

On my machine the MarchingSquares runs around 50 fps, but dips whenever the above mentioned exception occurs. The point is that you'll always get the pixel outline, in most cases very fast, in fringe cases a bit slower.

I wrote a MarchingSquares class, which can be used as follows:

If speed isn't an issue, use :

Just two considerations:

• I couldn't be arsed to make the MarchingSquares9Grid run counter clockwise, so there's a method that reverses your Vector if that tickles your perversions.
• Both of these will require at least a one pixel padding of transparent pixels in your source bitmap. This can be introduced with some bitmapdata magic.

download MarchingSquares.as and MarchingSquares9Grid.as here

Thanks again Rothrock!

Putting together a number of previous blog posts, here's the current state of my 3d text. In terms of speed and quality, it's a big improvement on the examples I was showing at FITC in Amsterdam, old example here.

So, the process is (links to blog posts with explanations and source code):

• Create text, grab a bitmap data snapshot of it.
• Extract Positive and Negative shapes from the BitmapData.
• Extract the Shape Outline Points from the Positive and Negative Shapes.
• Analyze and Optimize the Shape Outline Points into a Vector Shape.
• Extrude the Points using the FP10 Drawing API.

Here's some screen shots, click images for the demo :

The colors are random, use the widgets to choose a font, the text size and depth of the extrude.

On my machine the framerate is pretty steady in the 20's even with longer strings. The text box on the right displays the duration of the entire process described above.

Check out the demo

Download the source (I know, the project has the same name as the last 3, because it is, I've just added a bunch more code to it). Parts of it I'm quite happy with, others less so, but you know, there's always room for improvement

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

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:

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

One slightly frustrating (but totally logical) feature of using editmode in TLF is that inserted InlineGraphicElements lose their "interactivity". Instead, they are treated the same as text characters, that is, the user can select them as if they were selecting text:

There was a comment In my previous entry about the possibility of mouse interaction with inserted graphics.

I have a way to do this, a bit hackish, but it does the job. Every added graphic needs to be stored in an array. When a user clicks, the code loops through all the graphics and checks if one of them happens to be under the mouse. This is achieved using the trusty old localToGlobal() method:

This is very useful if you want to edit the graphic somehow, for instance, in the RTE that I'm currently working on I use this for "table support". In the TextFlow, my tables are represented as bitmaps, when clicked, the actual DataGrid is opened and ready to edit. When finished, a new BitmapData is grabbed and the InlineGraphic in the TextFlow is updated.

I have found one "bug" (or a feature?!), if an image is taller than (somewhere around 1000 pixels), the image is no longer properly "wrapped", and actually starts to cover some text.

It's also possible to listen to MouseMove, and set some rollover/out states to the graphics. You can see a demo here and download the source mxml file here.