sakri rosenstrom blog

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

On my quest to generate 3D text from non-embedded fonts, after extracting positive and negative shapes from characters, the next step is to analyze and extract the points which define the pixel boundary surrounding the extracted shapes.

There is a "brute" way to do this, simply by looping through every pixel in a BitmapData, and checking weather any surrounding pixels are transparent. This works, but the discovered pixels are not in a meaningful order.

The goal is to create an algorithm which circumnavigates the extremities of shapes, storing the traversed points in sequence, eventually doing this:

My original approach was to grab the first transparent pixel, then loop around its 8 surrounding pixels, run through some rules, then determine the next pixel to move to, until the "3x3 grid" would arrive at its starting point. The "3x3" grid would move along the shape clockwise.

As a side note, it was a relief to see Marios presentation in Milan, where he had pretty much the same approach, except his was moving counter clockwise. One very important "innovation" that I learned from Mario was to double the size of the analyzed bitmap. This prevents "single pixel" lines, which, if you think about it, are very tricky for the "3x3 grid" to analyze.

My implementation was sluggish, and had a few bugs... So I came up with another approach. I guessed that the rules of moving clockwise never change, so I figured a lookup table approach might just work. The idea is to represent the "3x3 grid" surrounding a pixel as a String using zeros for transparent pixels, ones for non-transparent ones. The lookup table would then map the "next position" to the various "3x3 grids". Here's a short snippet of my lookup table:

It's still not the Usain Bolt of algorithms, but a big improvement on my previous attempt. So where did this magical lookup table come from? If you look at the animated gif above, it's actually a screenshot of a "outline pixels generator" tool which I wrote just for this purpose. This allowed me to move along the edge of a shape, as the eye would follow it, and store the "moves" as "rules". You can find the entire lookup table in the zip below.

To test and demo the algorithm, I wrote a quick flex app, click to try it out:

Choose any font, pick a character, then extract the outlines. There is one thorny topic of annoyance. Flash player adds a weird anti-alias to all text above a certain font size. Small non-embedded text appears as one would expect, but in bigger sizes (which is needed for better curve information), there is a "quasi-anti-alias". In the above image,

• The left-most image is a non-embedded text field, with the "anti-alias".
• The second image is a "mono-chrome" representation of it.
• The third is the generated outline (of the mono-chrome)
• The last one is the original (first image), with the generated outline superimposed.

The outline is not "ideal", all pixels with an alpha greater than 0 are represented as black, making the image "blockier" than necessary. In the "superimposed" image, particularly with curves, there is a clear difference between the original character and the curve. meh. There is a way to get the "aliased" text with embedded fonts, more here. But since I'm interested in non-embedded fonts...

The second "demo" within is an animated "blob", which extracts the outline on every frame. I made this mostly just to "test" the algorithm... So far it's not throwing any errors for me. The frame rate is dependent on the number of "separate shapes and negative shapes". If you have a slow machine I don't recommend this one

The next step is to analyze these outline paths and optimize them into "vector information", which I'll blog about shortly.

Click here to try out the demo, then click
here to download the zipped flex source folder. The relevant code is in plain as3 classes, in case flex isn't your thing.

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.

My SoTexty 3d Text Effect demo uses a Class I wrote a which takes a polygon in the form of a Vector of Points, and extrudes it into a 3dMesh of sorts.

Click the image for a demo:

The colors are random, as is the outline of the shapes... Refresh if the result doesn't please your aesthetics

Here's the snippet that uses the class:

Instead of Triangulating the shape, I used a "shortcut" which I learned a while back from Den Ivanov. The Mesh contains a "front" and a "back" which are a triangle pair, who use the "original" shape as their material:

The large red square with the diagonal represents the "front", the "back" is identical. A curiosity about this screenshot is that the "filled triangles" are z-sorted correctly, however, there are some issues with the outlines. Meh.

The code accepts a Vector of Positive and Negative "shapes", which are rendered into a BitmapData and used as a "Material" by the 3DMesh. Here is a screenshot of what the "rendered" material looks like:

The filled box on the right is the "material" used by the extruded sides.

Notice the white space surrounding the shape. An annoying issue I ran into was that the "front" and the "back" had unwanted artifacts when using a "1 to 1" ratio "material". The UV mapping would go from 0 to 50% horizontally, and 0 to 100% vertically. For some reason, the edges (when rotated) would render an arbitrary "line" on any of the four sides.

The solution was to add white space, and grab the material using "less precise" percentages, which unfortunately results in some "spaces" on the edges of the "shape" material and the extruded side triangles. Another Meh.

It's not perfect, but I figured the code might be fun to play with...

Download the flex project here

(requires Flex SDK 3.2 or higher)

I participated in the original one back at the were-here forums, and couldn't resist giving it a shot this time around as well If you don't know, this is what I'm talking about.

In the spirit of my upcoming FITC Talk, I naturally went for a text effect! Click the image to see it in action :

I started with a good 50 lines of code... I'm just getting my head around the tricks involved with using Graphics.drawTriangles(). Took a bit of effort to a) get it to work, b) get it down to 25 lines. Basically the code:

• Creates a textfield
• Grabs a bitmapData of it, this is the "material"
• Creates a cylinder with a loop (vertices, triangles and uv data)
• In an enterframe it:
• Rotates a matrix in y and z
• Transforms that rotation to the "mesh" and it to the perspective projection
• Draws the triangles using the material as a bitmap fill

At the end, I got the line count down to the point where I could even add some glow and z rotation oh: The screenshot looks a bit "pixely", and it is, because the font is not embedded.

The 25lines website proclaims : "You probably don't want to share your code prematurely, but that's up to you", well.... Last time I was probably 60th out of 61 entries so I doubt this is gonna kill my chances I'll never match up to the math gurus out there, but hey, mine has a joke in it!

The code:

The source in an easier "cut and paste" format : circular_logic.txt

Again, the html page with the compiled swf in it : 25Lines.html

anyway, fingers crossed! Looking forwards to seeing the other entries