Archive for the ‘experiment’ Category

Simple Shape Extruder using FP10 Drawing API

Tuesday, March 10th, 2009

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:

Actionscript:
  1. protected function testExtrude():void{
  2.     var points:Vector.<Point>=createCircularPath(new Point(300,300),200,250,50);
  3.     var negative_shape_points:Vector.<Point>=createCircularPath(new Point(300,300),90,190,40);
  4.     var points2:Vector.<Point>=createCircularPath(new Point(550,550),80,20,20);
  5.     var points3:Vector.<Point>=createCircularPath(new Point(300,650),80,20,20);
  6.     var points4:Vector.<Point>=createCircularPath(new Point(650,300),80,20,20);
  7.     _extruded=SimpleShapeExtruderDrawAPI.createExtrudedShapeFromPoints(100,
  8.                                                                 Vector.<Vector.<Point>>([points,points2,points3,points4]),
  9.                                                                 Vector.<Vector.<Point>>([negative_shape_points]),
  10.                                                                 Math.random()*0xFFFFFF,0xFF000000+Math.random()*0xFFFFFF
  11.                                                                 );
  12.     _extruded.adjustCenter(300,300);
  13.     _extruded.x=300;
  14.     _extruded.y=300;
  15.     addChild(_extruded);
  16.     addEventListener(Event.ENTER_FRAME,rotateExtruded);
  17. }

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)

Extracting positive and negative shapes from a BitmapData

Tuesday, March 3rd, 2009

The first step in generating the "vector text effects" which I blogged about in my previous post is to grab a BitmapData of a character, then seperate the "characters components" into individual BitmapData instances.

So let's take a capital B :

The B only contains one "positive shape", that is, the "filled in" part. The B contains 3 "negative shapes" or the transparent bits. In this case we've got the surrounding area and the two "holes".

If we take a percent symbol "%"

We've got 3 positive shapes and 3 negative ones.

So how does one go about extracting these? I'm sure there are several approaches, I tried a few, this was the speediest of the ones I came up with.

Step 1 : Convert the captured BitmapData into one containing just two colors, a solid and a transparent. *Note:* this has the side effect that the extracted shapes have "pixelated" , "jagged" or "aliased" edges. For my purposes this is sufficient, a different approach would be needed to keep anti-aliasing.

Actionscript:
  1. public static function toMonoChrome(source:BitmapData,mono_color:uint=0xFF000000):BitmapData{
  2.     var bmd:BitmapData=source.clone();
  3.     bmd.threshold(bmd,bmd.rect,new Point(),">",0x00000000,mono_color);
  4.     return bmd;
  5. }

Step 2 : Create an "inverse" of the "monochrome" image:

Actionscript:
  1. //create the monochrome for extracting "positive shapes"
  2. var positive_two_color:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0x00);
  3. positive_two_color.draw(source_bmd);
  4. positive_two_color=BitmapDataUtil.toMonoChrome(positive_two_color,0xFFFF0000);
  5.  
  6. //create the monochrome for extracting "negative shapes"
  7. var temp:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0xFF0000FF);
  8. temp.draw(positive_two_color);
  9. var negative_two_color:BitmapData=new BitmapData(source_bmd.width,source_bmd.height,true,0xFFFF0000);
  10. negative_two_color.copyChannel(temp,positive_two_color.rect,new Point(), BitmapDataChannel.BLUE, BitmapDataChannel.ALPHA);

Again, I'm sure there are other ways to skin this cat. I created a BLUE "temp" BitmapData, then drew the "positive shape" on it. I then copy the BLUE Channel into the ALPHA channel of a RED BitmapData, which creates an image with inverted RED and ALPHA from the "positive shape".

Step 3 : Extract the "component" BitmapDatas from the positive and negative BitmapDatas. This requires a few steps:

Create a loop which:

  1. finds the first non transparent pixel more info
  2. Does a FloodFill with Blue on that pixel
  3. Create a new BitmapData, and copy the BLUE Channel into it, add this to the "found" items
  4. Remove the Blue from the original by using a transparent FloodFill

Do this for both the "positive" and inverse "negative" BitmapDatas and store the discovered "component shapes" in a vector or an array.

Here's my code for doing so:

Actionscript:
  1. protected static function extractShapesFromMonochrome(bmd:BitmapData):Vector.<BitmapData>{
  2.     var scan_y:uint=0;
  3.     var non_trans:Point;
  4.     var found:Vector.<BitmapData>=new Vector.<BitmapData>();
  5.     var copy_bmd:BitmapData;
  6.     while(scan_y<bmd.height){
  7.         non_trans=BitmapDataUtil.getFirstNonTransparentPixel(bmd,scan_y);
  8.         if(non_trans==null)return found;
  9.         bmd.floodFill(non_trans.x,non_trans.y,0xFF0000FF);//fill with blue
  10.         copy_bmd=new BitmapData(bmd.width,bmd.height,true,0xFFFF0000);
  11.         copy_bmd.copyChannel(bmd,bmd.rect,new Point(),BitmapDataChannel.BLUE , BitmapDataChannel.ALPHA);
  12.         bmd.floodFill(non_trans.x,non_trans.y,0x00000000);//fill with blue
  13.         found.push(copy_bmd);
  14.         scan_y=non_trans.y;
  15.     }
  16.     return found;
  17. }

That pretty much does it. The next step is to analyze the discovered shapes and generate vector points to work with... but that's another blog post.

Get first non transparent pixel in a bitmap Part III

Wednesday, February 18th, 2009

I know, I know... such a riveting topic, just can't get enough! :D

So I felt quite embarrassed when Mario commented on my previous entry, stating that in fact I had misunderstood his method. Either just me being an idiot, or me being an idiot after a few drinks at the Max party.

He then proceeded to blog about the real deal. Indeed this requires less code, looks cleaner and more 1337 in every way! I then included the new method into my test run.

Here is Marios code:

Actionscript:
  1. public static function getFirstNonTransparentPixel( bmd:BitmapData ):Point{
  2.     var r1:Rectangle = bmd.getColorBoundsRect( 0xff000000, 0, false );
  3.     if ( r1.width> 0 ){
  4.         var temp:BitmapData = new BitmapData( r1.width, 1, true, 0 );
  5.         temp.copyPixels( bmd, r1, new Point());
  6.         var r2:Rectangle = temp.getColorBoundsRect( 0xff000000, 0, false );
  7.         return r1.topLeft.add( r2.topLeft );
  8.     }
  9.     return null;
  10. }

Here (once again) be the results:

Test with image w:100,h:100
testFirstBitmapLooping() first:(x=30, y=30)
testFirstBitmapLooping() test took : 3 milliseconds
testFirstBitmapFloodFill() first:(x=30, y=30)
testFirstBitmapFloodFill() test took : 4 milliseconds
testFirstBitmapHitTest() first:(x=30, y=30)
testFirstBitmapHitTest() test took : 1 milliseconds
testFirstBitmapMario() first:(x=30, y=30)
testFirstBitmapMario() test took : 1 milliseconds

Test with image w:500,h:500
testFirstBitmapLooping() first:(x=150, y=150)
testFirstBitmapLooping() test took : 30 milliseconds
testFirstBitmapFloodFill() first:(x=150, y=150)
testFirstBitmapFloodFill() test took : 17 milliseconds
testFirstBitmapHitTest() first:(x=150, y=150)
testFirstBitmapHitTest() test took : 1 milliseconds
testFirstBitmapMario() first:(x=150, y=150)
testFirstBitmapMario() test took : 3 milliseconds

Test with image w:1000,h:1000
testFirstBitmapLooping() first:(x=300, y=300)
testFirstBitmapLooping() test took : 62 milliseconds
testFirstBitmapFloodFill() first:(x=300, y=300)
testFirstBitmapFloodFill() test took : 41 milliseconds
testFirstBitmapHitTest() first:(x=300, y=300)
testFirstBitmapHitTest() test took : 7 milliseconds
testFirstBitmapMario() first:(x=300, y=300)
testFirstBitmapMario() test took : 10 milliseconds

Test with image w:2000,h:2000
testFirstBitmapLooping() first:(x=600, y=600)
testFirstBitmapLooping() test took : 306 milliseconds
testFirstBitmapFloodFill() first:(x=600, y=600)
testFirstBitmapFloodFill() test took : 96 milliseconds
testFirstBitmapHitTest() first:(x=600, y=600)
testFirstBitmapHitTest() test took : 32 milliseconds
testFirstBitmapMario() first:(x=600, y=600)
testFirstBitmapMario() test took : 55 milliseconds

...so it turns out this wasn't an entirely futile exercise after all! I felt like a schmuck having misunderstood Mario, but I'm quite chuffed that the HitTest method is faster (even if by a practically irrelevant amount).

To be sure, I ran the two competitors 20 times on a bitmap of 2000 by 2000 and took the averages:

Mario Average: :36.7
HitTest Average: :21.2

In any case, I got to better terms with some of the BitmapData methods, which is something we all should aspire to anyway :) Thanks again Mario!

********** FINAL UPDATE (hopefully)************

Mario had a go at the HitTest version, and modified it slightly for even better performance:

Actionscript:
  1. public static function getFirstNonTransparentPixel( bmd:BitmapData ):Point{
  2.     var hit_rect:Rectangle=new Rectangle(0,0,bmd.width,1);
  3.     var p:Point = new Point();
  4.     for( hit_rect.y = 0; hit_rect.y <bmd.height; hit_rect.y++ ){
  5.         if( bmd.hitTest( p, 0x01, hit_rect) ){
  6.         var hit_bmd:BitmapData=new BitmapData( bmd.width, 1, true, 0 );
  7.         hit_bmd.copyPixels( bmd, hit_rect, p );
  8.         return hit_rect.topLeft.add( hit_bmd.getColorBoundsRect(0xFF000000, 0, false).topLeft );
  9.         }
  10.     }
  11.     return null;
  12. }

Mind you, I am testing this in debug player... I should use a release version with the release player, but for the sake of consistency with my previous posts I'll stick to my old "test suite".

Results:

HitTest Averages: :16
Mario Averages: :35.285714285714285
Hybrid Averages: :14.142857142857142

Now, finally, back to the code where I actually use this algo ;)

Get first non transparent pixel in a bitmap update

Tuesday, February 10th, 2009

On the way home I realized I had made a mistake in my previous blog post. In my hitTest() version, for some reason I had used a Rectangle which was the full size of the target bitmap. Like the FloodFill version, this "hit test" rectangle only needs to be one pixel in height. This means a lot less checking.

Behold the updated version:

Actionscript:
  1. public static function getFirstNonTransparentPixelHitTest(bmd:flash.display.BitmapData,test_fill_color:uint=0xFFFFFF00):Point{
  2.     var hit_rect:Rectangle=new Rectangle(0,0,bmd.width,1);
  3.     for(var i:uint=0;i<bmd.height;i++){
  4.         if(bmd.hitTest(new Point(),0x01,hit_rect)){
  5.             var hit_bmd:BitmapData=new BitmapData(bmd.width,1,true,0);
  6.             var m:Matrix=new Matrix(1,0,0,1,0,-i);
  7.             hit_bmd.draw(bmd,m);
  8.             hit_bmd.floodFill(0,0,test_fill_color);//use yellow, assume that the image tested is monochrome... (black and transparent)
  9.             var bounds:Rectangle=hit_bmd.getColorBoundsRect(0xFFFFFFFF,test_fill_color);
  10.             return new Point(bounds.width,i);
  11.         }
  12.         hit_rect.y++;
  13.     }
  14.     return null;
  15. }

Now behold the new results:

Test with image w:100,h:100
testFirstBitmapHitTest() first:(x=30, y=30)
testFirstBitmapHitTest() test took : 2 milliseconds
testFirstBitmapLooping() first:(x=30, y=30)
testFirstBitmapLooping() test took : 1 milliseconds
testFirstBitmapFloodFill() first:(x=30, y=30)
testFirstBitmapFloodFill() test took : 3 milliseconds

Test with image w:500,h:500
testFirstBitmapHitTest() first:(x=150, y=150)
testFirstBitmapHitTest() test took : 8 milliseconds
testFirstBitmapLooping() first:(x=150, y=150)
testFirstBitmapLooping() test took : 32 milliseconds
testFirstBitmapFloodFill() first:(x=150, y=150)
testFirstBitmapFloodFill() test took : 20 milliseconds

Test with image w:1000,h:1000
testFirstBitmapHitTest() first:(x=300, y=300)
testFirstBitmapHitTest() test took : 13 milliseconds
testFirstBitmapLooping() first:(x=300, y=300)
testFirstBitmapLooping() test took : 117 milliseconds
testFirstBitmapFloodFill() first:(x=300, y=300)
testFirstBitmapFloodFill() test took : 42 milliseconds

Test with image w:2000,h:2000
testFirstBitmapHitTest() first:(x=600, y=600)
testFirstBitmapHitTest() test took : 23 milliseconds
testFirstBitmapLooping() first:(x=600, y=600)
testFirstBitmapLooping() test took : 282 milliseconds
testFirstBitmapFloodFill() first:(x=600, y=600)
testFirstBitmapFloodFill() test took : 102 milliseconds

So the hitTest approach wins after all :)

***EDIT :

AND CLICK HERE TO READ UPDATE!

***

Get first non transparent pixel in a bitmap, 3 approaches and benchmarks

Tuesday, February 10th, 2009

I was (once again) very inspired by Mario Klingemanns presentation at the Max in Milan. He showed an example of finding the "perimeter of non transparent pixels" in a bitmap. Not long ago I did the same thing while trying to generate 3d text . He briefly mentioned "you just find the first non transparent pixel, then..." which left me wondering.

I had taken the "brute force approach" of just looping through the pixels, doing a if(bmd.getPixel32(ix,iy)>0x00000000) approach, which (unsurprisingly) isn't very fast. So, at the afterparty, I decided to harass Herr Klingemann. He gladly explained that you 'just create a one pixel high BitmapData, the width of your source BitmapData, iterate from top to bottom draw()ing this "scan line", using floodFill() and getColorBoundsRect() each time to compare if the bounds rect was the width of the source bitmap'.

This sounded incredibly slow. In preparation for my FITC presentation, i'm now returning to the 3d text code, and I just had to test this out. I had this "Brilliant" idea to use BitmapData.hitTest() instead... surely this was faster?! I would create a Rectangle, position it above the source BitmapData, then iterate all the way down, merrily hitTesting() all the way.

Here are my findFirstTransparentPixel() mutations:

Actionscript:
  1. public static function getFirstNonTransparentPixelLooping(bmd:flash.display.BitmapData):Point{
  2.     var ix:uint,iy:uint,bmd_height:uint=bmd.height,bmd_width:uint=bmd.width;
  3.     for (iy=0;iy<bmd_height;iy++){
  4.         for(ix=0;ix<bmd_width;ix++){
  5.             if(bmd.getPixel32(ix,iy)>0x00000000){
  6.                 return new Point(ix,iy);
  7.             }
  8.         }
  9.     }
  10.     return null;
  11. }
  12.  
  13. public static function getFirstNonTransparentPixelFloodFill(bmd:flash.display.BitmapData,test_fill_color:uint=0xFFFFFF00):Point{
  14.     //var hit_bmd:BitmapData=new BitmapData(bmd.width,1,true,0);
  15.     var hit_bmd:BitmapData;
  16.     var m:Matrix=new Matrix();
  17.     for(var i:int=0;i<bmd.height;i++){
  18.         m.ty=-i;
  19.         hit_bmd=new BitmapData(bmd.width,1,true,0);
  20.         hit_bmd.draw(bmd,m);
  21.         hit_bmd.floodFill(0,0,test_fill_color);//use yellow, assume that the image tested is monochrome... (black and transparent)
  22.         var bounds:Rectangle=hit_bmd.getColorBoundsRect(0xFFFFFFFF,test_fill_color);
  23.         if(bounds.width!=bmd.width){
  24.             return new Point(i,bounds.width);
  25.         }
  26.         //hit_bmd.floodFill(0,0,0);
  27.         hit_bmd.dispose();
  28.     }
  29.     return null;
  30. }
  31.  
  32. public static function getFirstNonTransparentPixelHitTest(bmd:flash.display.BitmapData,test_fill_color:uint=0xFFFFFF00):Point{
  33.     var hit_rect:Rectangle=new Rectangle(0,-bmd.height+1,bmd.width,bmd.height);   
  34.     for(var i:uint=1;i<bmd.height;i++){
  35.         if(bmd.hitTest(new Point(),0x01,hit_rect)){
  36.             var hit_bmd:BitmapData=new BitmapData(bmd.width,1,true,0);
  37.             var m:Matrix=new Matrix(1,0,0,1,0,-(i-1));
  38.             hit_bmd.draw(bmd,m);
  39.             hit_bmd.floodFill(0,0,test_fill_color);
  40.             var bounds:Rectangle=hit_bmd.getColorBoundsRect(0xFFFFFFFF,test_fill_color);
  41.             return new Point(bounds.width,i-1);
  42.         }
  43.         hit_rect.y++;
  44.     }
  45.     return null;
  46. }

Here's my test code:

Actionscript:
  1. protected function createTestBitmap(w:uint,h:uint):BitmapData{
  2.     var b:BitmapData=new BitmapData(w,h,true,0x00000000);
  3.     b.fillRect(new Rectangle(Math.round(w*.30),Math.round(h*.30),Math.round(w*.40),Math.round(w*.40)),0xFFFF0000);
  4.     return b;
  5. }
  6.  
  7. protected function testFirstBitmapFloodFill(w:uint,h:uint):void{
  8.     var start:uint=flash.utils.getTimer();
  9.     var b:BitmapData=createTestBitmap(w,h);
  10.     trace("testFirstBitmapFloodFill() first:"+BitmapDataUtil.getFirstNonTransparentPixelFloodFill(b));
  11.     trace("testFirstBitmapFloodFill() test took : "+(flash.utils.getTimer()-start)+" milliseconds");   
  12.     b.dispose();
  13.     b=null;
  14. }
  15.  
  16. protected function testFirstBitmapHitTest(w:uint,h:uint):void{
  17.     var start:uint=flash.utils.getTimer();
  18.     var b:BitmapData=createTestBitmap(w,h);
  19.     trace("testFirstBitmapHitTest() first:"+BitmapDataUtil.getFirstNonTransparentPixelHitTest(b));
  20.     trace("testFirstBitmapHitTest() test took : "+(flash.utils.getTimer()-start)+" milliseconds");
  21.     b.dispose();
  22.     b=null;
  23. }
  24.  
  25. protected function testFirstBitmapLooping(w:uint,h:uint):void{
  26.     var start:uint=flash.utils.getTimer();   
  27.     var b:BitmapData=createTestBitmap(w,h);
  28.     trace("testFirstBitmapLooping() first:"+BitmapDataUtil.getFirstNonTransparentPixelLooping(b));
  29.     trace("testFirstBitmapLooping() test took : "+(flash.utils.getTimer()-start)+" milliseconds")
  30.     b.dispose();
  31.     b=null;
  32. }

I tested all three functions with images ranging from 100x100 to 2000x2000 pixels:

Here be the results:

Test with image w:100,h:100
testFirstBitmapHitTest() first:(x=30, y=30)
testFirstBitmapHitTest() test took : 2 milliseconds
testFirstBitmapLooping() first:(x=30, y=30)
testFirstBitmapLooping() test took : 7 milliseconds
testFirstBitmapFloodFill() first:(x=30, y=30)
testFirstBitmapFloodFill() test took : 8 milliseconds

Test with image w:500,h:500
testFirstBitmapHitTest() first:(x=150, y=150)
testFirstBitmapHitTest() test took : 29 milliseconds
testFirstBitmapLooping() first:(x=150, y=150)
testFirstBitmapLooping() test took : 34 milliseconds
testFirstBitmapFloodFill() first:(x=150, y=150)
testFirstBitmapFloodFill() test took : 20 milliseconds

Test with image w:1000,h:1000
testFirstBitmapHitTest() first:(x=300, y=300)
testFirstBitmapHitTest() test took : 147 milliseconds
testFirstBitmapLooping() first:(x=300, y=300)
testFirstBitmapLooping() test took : 111 milliseconds
testFirstBitmapFloodFill() first:(x=300, y=300)
testFirstBitmapFloodFill() test took : 41 milliseconds

Test with image w:2000,h:2000
testFirstBitmapHitTest() first:(x=600, y=600)
testFirstBitmapHitTest() test took : 644 milliseconds
testFirstBitmapLooping() first:(x=600, y=600)
testFirstBitmapLooping() test took : 210 milliseconds
testFirstBitmapFloodFill() first:(x=600, y=600)
testFirstBitmapFloodFill() test took : 75 milliseconds

Started out good for me! With a small image my hitTest approach was over 3 times faster! Then, the bigger the sample image got, the more my method started sucking, and Mario started Rocking. Eventually the "looping" method became faster than the hitTest() :D

So, Conclusion : For small images, the amount of difference is so little it really doesn't matter, with bigger images go FloodFill... Hats off Quasimondo :)

If you have ideas for faster approaches, or improvements to the above three, don't hesitate to comment!

***EDIT :
CLICK HERE TO READ UPDATE

AND CLICK HERE TO READ UPDATE 2

***