In Flash we can HARNESS THE POWER OF BITMAPDATA (as it might be put in a conference session blurb) to grow Voronoi regions under differing conditions, without doing any algebra. Click on the image to launch the Voronoi Generator.
One way of getting Voronoi diagrams is by growing crystals. If you start a number of crystals, all growing at the same rate, and all starting at the same time, you get a number of growing circles. As these circles meet, straight line boundaries appear between them. Eventually, the entire plane will be filled up. Each crystal will exactly fill up the Voronoi region of its point of origin.
This is a little too simple. In reality, crystals start growing at different times. Even if they still grow at the same rate, if they start at different times, they will no longer meet in straight lines. Instead, they will meet in hyperbolic segments. The diagram you get is called the “additively weighted Voronoi diagram”. It’s defined just like the usual Voronoi diagram, but each site has a weight, and you measure distance to a site, you add its weight to the usual Euclidean distance.
Now suppose instead that all the crystals start at the same time, but grow at different rates. Now you get what’s called the “multiplicatively weighted Voronoi diagram”. Once again, each site is given a weight, but when you measure the distance to a site, you multiply by its weight. Now the boundaries between different regions are segments of circles.
This model still has some problems. For example, in a multiplicatively weighted Voronoi diagram, it’s possible for a region to be disconnected [ see picture above -- AS ]. Obviously, this can’t happen with real crystals. So there’s yat another version which treats existing crystals as obstacles, and lets fast-growing crystals grow around the slower ones. Now the boundaries between neighboring regions are sort of tear-shaped. This variation is called the “multiplicatively weighted crystal growth Voronoi diagram.”
There are several other variations. You can change the metric from the normal Euclidean distance to L1, or Lp, or Linfinity, or even stranger distance functions. You can weight the sites additively and mulitplicatively. You can change the sites from points to line segments or circles or polygons. You can generalize to higher dimensions. You can associate points with the farthest site, instead of their nearest site. And so on.
Different applications of Voronoi diagrams require different variations. For example, motion planning algorithms for circular robots often use the Voronoi diagram of the obstacles. If there is a path from one location to another, then there must be a path that follows the edges of the Voronoi diagram, since those edges are by definition as far from the obstacles as possible.
The “L1 metric” is called the Manhattan metric or city-block distance. “Manhattan metric” is a misnomer, though, because in Manhattan the east-west blocks are much longer than the north-south blocks.
The crystal-growth model is equivalent to the “evil forest ranger model,” in which instead of watching for forest fires, the rangers set fire to their lookouts, sometimes at different times, and the fires may spread at different rates. Voronoi diagrams indeed find application in crystallography and in forest-fire modelling.
Sakri was working on this, and I ported a class from Java which I believe he adapted into his final implementation. It’s a basic tool for morphing, 3D surface reconstruction, and vectorization.
I’ve cleaned up my version of it and I offer it here. The important function signature looks like this:
public static function perimeter(data:BitmapData, x:int, y:int):Vector.<Point>
It returns a list of pixels representing the boundary between opaque and transparent pixels, starting from a single boundary point that you provide.
You can get a boundary point using Sakri’s and Mario’s EdgeFinder class.
Jim Armstrong, the Flash community’s primary math whiz, has encouraged me in the past, and today he did so publicly. I’m very grateful for this recommendation.
Here’s the crass part: I’m available for contract or permanent work, locally or remotely. I live in New York City. CV, references, and samples of my work are available. Please hit the Contact link to get in touch.
I’ve rendered some images using the Voronoi Toy from my last post.
I’ve used my logo 結 (as in 結點 “node”) as the input image, run Sakri Rosenstrom’s image segmentation algorithm on it, dropped 10,000 random points into the segments, and drawn the minimum spanning tree of each set of points, thus creating a sort of space-filling tree.
The idea for this kind of fill comes from Mario Klingemann’s presentation at FITC.
relax, v.
10. Chiefly Physics. To return towards a state of equilibrium. (OED)
Here’s the planar analog of my earlier post Distributing Points on the Sphere. This time I’ve ported Steve Fortune’s C implementation of his sweepline algorithm for Voronoi diagrams, and applied Lloyd’s algorithm to change the input values (the point locations) iteratively so the output function (the stress or energy) approaches a minimum. Lloyd’s algorithm works by repeatedly computing the Voronoi diagram and moving each point to the centroid of its region. Soon the points converge to an even distribution. You can see this in action by starting the app by clicking on the image, and then pressing the “r” key.
The displacement map in Flash provides only one byte of precision for each of x and y, which means it can map a pixel value from one of at most 128 discrete locations on one side, and only 127 on the other. So when you map pixels over larger distances (which you can do using the scaleX and scaleY parameters of the DisplacementMapFilter constructor), you lose precision.
Image quality can be improved by using as much as possible of the 0×00～0xFF range of each of the map image components. I won’t go into detail on the procedure, but these are the main points:
1. Multiply the map’s X component by N with 0×80 as a center
2. Divide the map’s scaleX by N
If N is so large that the range 0×00～0xFF is exceeded, adjust it appropriately.
So it has been standard practice to set the scaleX and scaleY parameters heuristically to minimize image degradation.
Well in Flash 10 that is all moot, thanks to PixelBender!
Click here to open BenderDemo in a new window (requires Flash Player 10 of course).
The program uses a slightly modified version of Ryan Taylor’s Pixel Bender DisplacementMapFilter. I’ve also written an ActionScript wrapper class, DisplacementMapShader, for it. Both images are generated using the DisplacementMapShader, the left one with a BitmapData displacement map just as in the DisplacementMapFilter, and the right one using a ByteArray of floats as the displacement map.
There are some interesting API differences between the shader and the built-in DisplacementMapFilter. Let’s compare the constructor calls:
_displacementMapFilter = new DisplacementMapFilter(_map as BitmapData, null,
BitmapDataChannel.BLUE, BitmapDataChannel.GREEN,
_outputSize, _outputSize,
DisplacementMapFilterMode.COLOR, 0xc0c0c0);
_displacementMapShader = new DisplacementMapShader(_map, new Point(_outputSize/2, _outputSize/2),
BitmapDataChannel.BLUE, BitmapDataChannel.GREEN,
2, 2);
First we note the mapPoint parameter, which is defined as “A value that contains the offset of the upper-left corner of the target display object from the upper-left corner of the map image.” We pass null to the DisplacementMapFilter to signify that we want the map to be aligned with the input image. But for the DisplacementMapShader we pass new Point(_outputSize/2, _outputSize/2). Recall that a Shader has no concept of the image size or location; it operates over a potentially infinite coordinate system. I believe that this parameter indicates where the origin of the coordinate system is to be located.
Then we have the scaleX and scaleY parameters, “The multiplier to use to scale the x displacement result from the map calculation” and “The multiplier to use to scale the y displacement result from the map calculation.” What this means is that the range of the displacement channel data (0 to 255 for the DisplacementMapFilter; 0 to 1 for the DisplacementMapShader), which specifies the range from max negative displacement to max positive displacement, is mapped to the interval we pass in this parameter. For the DisplacementMapFilter we pass _outputSize, indicating a range of the image size, i.e. half that many pixels in the positive direction and half that many pixels in the negative direction. For the Shader, we pass the value 2, indicating that we want a max negative displacement of 1 and a max positive displacement of 1. We’re saying that we want the displacement map to cover a width of two units; this combined with the mapPoint indicates that the map covers a square of width 2 centered at the origin.
He supports an expansion of stem-cell research. He’s made nuclear nonproliferation a priority. He favors combating global warming with a “cap and trade” system. He supported a bill to expand the government’s eavesdropping authority and to protect telephone companies that cooperated with the program from being sued. He embraces the idea of continuing Bush’s faith-based initiative. He said he was picked last on a sports team as a boy. He said it taught him to work hard and persevere. His favorite childhood Halloween costume was a pirate.
Click on the image to open AstroMorpher in a new window (requires Flash Player 10).
AS3 provides a built-in data structure that you can use for dynamic programming to supplement your application’s functionality. This structure is the prototype chain.
What’s the prototype chain?
To answer that, let’s start by forgetting about user-defined Classes for the moment, and looking at some older mechanisms that have been common to ActionScript and JavaScript since AS1.
Functions and the new operator
Whenever a Function is created, the Function constructor also creates a new generic Object. The Function gets a property named “prototype” that refers to this new Object. This generic object is a default that you can change by setting the Function’s prototype to a different object, as we shall see.
Now when you the programmer want to create a new custom object, you can do it by invoking a function preceded by the new operator:
var myObject:Object = new SomeFunction();
When used with the new operator, a function is known as a constructor function (not to be confused with a constructor method!), or just a constructor. The new operator modifies the way the function works in three ways:
1. Ordinarily, the keyword this, when used inside a function, is bound to the global object. When a function is invoked with new, a new Object is created, and this refers to that Object. (This is like using the Function.apply() method.)
2. The new Object gets a property named __proto__ that refers to the constructor’s prototype. The Object’s __proto__ is a basis for inheritance — a way to customize the new Object — as described in the next section.
3. If the function returns a non-object value, then when invoked with new, this (the new object) is returned instead. If the function returns an object, that object becomes the value of the new expression, and this is discarded.
You can see that use of the new operator causes the function to behave quite differently. So although there is no formal difference between a constructor function and any other function, the code you put in them will be quite different. Constructor functions are conventionally named with an upper-case first letter as a reminder of the distinction.
Prototype Inheritance
When the runtime encounters a reference to a property of an object, as in myObject.var or myObject.func(), it naturally looks for the property in the object itself. But if it doesn’t find it there, it looks in the object’s __proto__ (the prototype object). Note that the prototype is an object like any other, and when it was created it got a __proto__ reference to a prototype, too. Thus we have a prototype chain. The chain has an end, though, because eventually we reach an Object that was created with new Object(); or with an Object literal in curly braces, and the next object in the chain is the unique and final Object.prototype. The runtime will search the chain until it finds the desired property or until it reaches Object.prototype.
The constructor’s prototype appears as the first element in the new Object’s prototype chain. Thus, although no new Class is created, and the new object’s type is simply Object, this particular prototype has a tangible effect on the object’s behavior that is shared with all other objects that have the same prototype chain. The prototype constitutes the Object’s pseudoclass. (The pseudoclass is often called “class” for simplicity when speaking of AS1 or JavaScript). The instanceof operator works by traversing the prototype chain.
If properties of the prototype are modified, the object naturally inherits the new values. If the object is directly assigned a property of a given name, that property will mask (or “shadow”) a property with the same name on the prototype.
If the constructor function is assigned a different prototype, then objects subsequently created with new SomeFunction() will inherit from the new prototype, but old objects continue to inherit from the original prototype. Normally, if a pseudoclass is to inherit from another, the programmer will explicitly set the constructor’s prototype before creating any objects from it:
function Shape() { this.handle = "shape"; } // leave default prototype; shape objects will inherit from an Object
function Circle(r) { this.radius = r; }
Circle.prototype = new Shape(); // circle objects will inherit from a shape object
var circle = new Circle(); // circle will have the "handle" property
Note that the constructor function itself, being an object of class Function, inherits properties not from its prototype, but rather from its own __proto__, which is a reference to Function.prototype.
The programmer can also replace an object’s __proto__, changing its pseudoclass at will. This may seem a bit out there, but it was actually the way to set the document type in AS1 and AS2.
All of the above applies equally to JavaScript and to all versions of ActionScript. But ActionScript 3 imposes certain restrictions:
1. Neither package-level functions nor class methods may be used as constructor functions. So a constructor function must be defined outside a package statement, within a method, or in a frame script.
2. The __proto__ property of an object is not accessible to the programmer.
3. In strict mode, passing any parameters to a constructor function that is declared outside a package statement is a compile-time error, even if the function is declared to accept parameters. (This is not the case when the function is defined within the method where it is invoked, or when the function is invoked through a reference defined within the method where it is invoked.) This appears to be a mistake on the part of the compiler.
Bringing it Up to Date
First let’s note that the above stuff is dynamic in that it can all be changed at runtime. Good times. Of course it comes with a price: slower performance, and everything is public and untyped.
Now let’s bring back Classes, and see how they behave compared to these ancestral features of the language.
In AS2, classes were grafted onto the underlying prototype-based language. Class syntax was just that: syntax allowing programmers to ignore the implementation and submit to certain restrictions at compile time. But prototype-based inheritance was all there really was in the VM, and its full power (and dangers) were still available at run time. AS3 is different. It has true classes and class-based inheritance.
When a Class is created, it gets a prototype object just as a Function does. The instances created by new ClassName() inherit from the class prototype, and you can add, delete, or change properties of the class prototype, and those properties are all public and untyped, too. The difference is that you cannot replace a Class’s prototype; the prototype chain (or tree, really) is isomorphic to the class hierarchy and is immutable.
Another difference, of course, is that you normally define fixed instance properties (variables and methods) when you write a Class. The fixed properties are placed in the class’s traits object, and the runtime checks the traits object for a property before searching the prototype chain; that is, class inheritance takes precedence over prototype inheritance. Fixed properties are typed, need not be public, and are found more quickly. As implied by the name, fixed properties cannot be deleted.
(You might think that the runtime has to search up the class hierarchy to find fixed properties that are inherited from a superclass. But in fact in AS3 these are copied down into the current class’s traits object, so they are found even more quickly.)
A Class’s constructor method is much like a constructor function. But you don’t get the chance to return anything from a constructor method, so new ClassName() will always return the new object. In fact you can’t even get a reference to the constructor method as a Function object, so you have no opportunity to try to invoke it without the new operator. This suggests that in AS3 the constructor method is still in a sense the same thing as the class.
I’m not going to get into the fascinating topic of closures right now, except to note that every function in AS and JS is a closure, so named because the scope of an inner function in these languages encloses the parameters and variables of the functions they are defined within.
Closures are first-class citizens of ActionScript. Every method in your class is a closure. That’s how it knows the instance variables of the class. Essentially every class is a big closure. You can write a function with closures inside that would be very much a class for all practical purposes.
– the RIA Book, p. 88
That last sentence describes what Douglas Crockford does in JavaScript: The Good Parts — what classical programmers may call simulating classes, and what Crockford calls better than classes.
Should you use dynamic features in your programming?
Sure, occasionally. Obviously, if you want to, you can create objects with a constructor function, then replace the constructor’s prototype, and create more objects with it.
If you think up a good use case for doing that, please let me know.
In fact, you should probably not use constructor functions at all. Crockford advises against them — and this in a language without user-defined classes! The lack of privacy is just one of the reasons he cites.
But you should definitely consider placing properties on class prototypes where appropriate.
UPDATE 22 Sept 2008: I now believe that the STRATEGY pattern is a better solution for this use case (see the comments on this post), but I’m leaving this example up as a demonstration of the technique for those who are interested.
Consider a game character who has a number of private methods; he wants to execute the appropriate method when he arrives at various targets, depending on the type of the target. He may have one method that he must execute whenever he arrives at any Flower, whether it be a Daisy or a Pansy or whatever derived class instance. If I set
Flower.prototype.myTask = flowerTask;
then on arrival, my character can call
target["myTask"]();
and the flowerTask is the one that will be executed if the target is any Flower derivative.
Here’s a little example; I’ve set properties on Target1.prototype and on Target2.prototype but not on Target3.prototype. Target2A is derived from Target2. Click on the targets:
An archive of the FlexBuilder project with sources and fuller explanation is here.
I like to think of prototype properties as a kind of enhanced reverse Dictionary; if you think of the property name as the data structure, and the object instances as keys — as though you were saying “myTask”[target] in the last example — then, when a certain value is set on a class’s prototype, you retrieve that value through any index that’s an instanceOf that class.
RSS
