Detecting edge pixels with Marching Squares Algorithm

Thursday, May 28th, 2009

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 :D 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:

PLAIN TEXT
Actionscript:
  1. MarchingSquares.getBlobOutlinePointsClockwise(bmd);
  2. //or
  3. MarchingSquares.getBlobOutlinePointsCounterClockwise(bmd);

If speed isn't an issue, use :

PLAIN TEXT
Actionscript:
  1. MarchingSquares9Grid.getBlobOutlinePoints(bmd);

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!

Posted in AS3, Flash, experiment, flex | 12 Comments »

Mouse interactions on Text Layout Framework InlineGraphicElements in EditMode

Thursday, March 26th, 2009

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:

PLAIN TEXT
Actionscript:
  1. protected function handleMouseDown(e:MouseEvent):void{
  2.     var hitrect:Rectangle;
  3.     var bm:Bitmap;
  4.     for(var i:uint=0;i<_images.length;i++){
  5.         bm=Bitmap(_images[i]);
  6.         var ltg:Point=bm.localToGlobal(new Point(0,0));
  7.         hitrect=new Rectangle(ltg.x,ltg.y,bm.width,bm.height);
  8.         if(hitrect.contains(mouseX,mouseY)){
  9.             mx.controls.Alert.show("so, I see you have clicked on an image eh?");
  10.             break;
  11.         }
  12.     }
  13. }

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.

Posted in AS3, Flash, flex, text layout framework | 8 Comments »