First let us get the terminology straightened out:
- Mormon bubbling
- The idea came from here (semi-nsfw), and basically entails covering parts of an image to force the viewers brain to fill in the blanks
- EEDT
- Exact Euclidean Distance Transform
As an avid GIMP’er (that’s open source for Photoshop, for those who are wondering) and redditor, I inevitably ended up trying my hands at Mormon bubbling. While it wasn’t difficult as such, it sure was laborious. It got me thinking – would it be possible to do this algorithmically? The answer it turns out, is yes and no.
My early sketch of how it could be done included calculating a distance map from the parts of the image you didn’t want shown. I knew this task to be non-trivial, but I also knew that other people had done it before me – though as I was to find out, not in Javascript.
I settled on an implementation from Animal, more specifically the algorithm called meijster2000. Before I started porting this to Javascript, I noted all the problems I thought I would encounter, such that I would hopefully have an easier time spotting them:
- Array indexes
- Pointers
- unsigned variables
but as I started the port, it became clear that there was another problem: passing around huge amounts of data. In C that’s just a pointer, but in Javascript that would quickly end up hurting the performance. Instead, I opted to deviate slightly from the C version, and make it Object Oriented, which would let me attach the relevant functions to the image object, and keep the data in one place. After some hours work, I had an algorithm that ran in as far as it didn’t have any syntactical or runtime errors. It just didn’t exactly do what it should either. On the way to figure out why, I ran into amongst other things a Firefox bug that reduced my performance by about 1000%, and not reading the specs carefully enough on typed arrays also lead me to one of the most elusive bugs I’ve had to deal with in Javascript.
Working with typed arrays
For those of you who do not know how Array.slice() works, here is an excerpt from MDC:
Returns a one-level deep copy of a portion of an array.
Not having carefully read the rest of the document (for neither Array or typed arrays) this is all I knew – that and experience from using it over the years. This oversight led me to believe that both of these examples would return true:
var foo = Array(0,1,2,3,4); var bar = foo.slice(0,5); foo[0]=42; bar[0]==0 var foo = Float64Array(0,1,2,3,4); var bar = foo.slice(0,5); foo[0]=42; bar[0]==0
However as it turns out, in the latter example bar[0]==42, and that took me hours to spot.
I will note that typed arrays do make a significant difference in speed, so as long as you know what you are doing, use them whenever you can!
A missing difference
It also turned out that I had completely missed one important difference between unsigned u and var u namely that the Javascript variable is not constrained to being an integer (remember I already took care of the unsignedness because I had that on my list) – luckily I didn’t have any other plans for he weekend, which left me plenty of time to debug.
Other biproducts
To create the UI needed for the project, I also created a drop in canvas editor with unlimited undo, and a small lib to make receiving files via drag and drop easier. Both of these could use more features, and I plan on working more on them and describing them in separate posts at a later time. For now, along with my image library, they can be scrounged from the source code of my bubbler.
In addition to my own creations, I also included the work of several others, including Farbtastic (a color picker by Steven Wittens) and StackBlur (a blur algorithm for canvas by Mario Klingemann, slightly modified for my needs).
The bubbling algorithm
The idea is fairly simple. Ask the user to mark out which parts of the image he doesn’t want shown, place a bubble as far away as possible from all markings, include the bubble as a marking, repeat. I’ve set a limit of 30 bubbles, and it stops placing bubbles if the radius of the biggest possible bubble is less than 2.
This is a very naive algorithm, that doesn’t take into account that there might be places you really want shown and others you don’t really care about. The biggest possible bubble wins. I might extend the algorithm to let users place a few bubbles themselves before filling in the rest, or possibly even letting the user place all the bubbles by hand, restricted in size by the distance map.
Demo
Here is a live demo of the project, instructions can be found in the bottom left corner. While it should work in most recent browsers, the best experience can be found in Firefox 4b6, as later nightlies suffer from aforementioned bug making them fairly slow, and chrome is quite a bit slower when it comes to canvas manipulations and slightly slower calculating the distance maps. It does not appear to work in Safari, but I am not sure why.