Emulating 3D Bitmap Transformations (part 2)

(correction)
Okay, so the first time I posted this I was definitely not thinking straight at all. Here's a correction.

So let's take a look at the math involved:

In a scale, pixels (x',y') are given by the following:
x' = x * x_scale_factor
y' = y * y_scale_factor

In a skew, pixels (x",y") are given by the following:
x" = y * x_skew_factor
y" = x * y_skew_factor

If you remember our image is partly scaled and partly skewed. Remember that the images are divided along the line f(x)=x meaning along this line pixels of the skewed picture approach the scaled picture.

So let's pull out that high school math and we'll find that means that:

x * x_scale_factor = y * x_skew_factor
y * y_scale_factor = x * y_skew_factor

By substituting in the line y=x this tells us along the line y=x pixels converge when x_scale_factor = x_skew_factor and y_scale_factor = y_skew_factor.

Emulating 3D Bitmap Transformations

I've been looking into 3D through Flash and there's a lot of 3D projects going on in the community, but Flash is currently not natively 3D. Though the new upcoming version of Flash seems very promising.
Before I explain anything credit for this post goes to my friend Steve at BSS who originally showed me this.

So my goal was to figure out how Papervision initially worked. My first assumption is that people were using the flash.geom.Matrix class to perform perspective transformations on BitmapData, but this is not the case. The Matrix class in Flash is only able to create affine transformations.

First let's take a look at affine transformations:
Affine transformations are transformations where:

• Collinearity between points, i.e., three points which lie on a line continue to be collinear after the transformation
• Ratios of distances along a line, i.e., for distinct colinear points p₁,p₂,p₃, | | p₂ − p₁ | | / | | p₃ − p₂ | | is preserved

This allows us to achieve only an isometric projection. What we are looking for is to be able to create depth using a perspective projection. With perspective we need to create a vanishing point which means lines which means parallel lines can converge. So this is a dilemma.

What We Can Do
What we can do is approximate 3D transformations by approximating a perspective transformation. We'll approximate by slicing our 2D image into smaller pieces and performing transformations on those individual pieces. As a side effect the image may be distorted, but we'll be able to control the distortion if we cut the image into smaller pieces.

Let's experiment through visually. Start with a grid image and slice it into two triangles:

Now let's take a look at two particular affine transformations.


Notice that the pixels near the line P1P4 do not move very much. These are a characteristic natures of these two particular transformations, scale and skew.

So if we take the top portion of the skewed image and the bottom portion of the scale image, it's possible to arrange the image so we're able to move only P4.


Therefore, since our pixels near our slice are able to match up, performing transformations on the individual pieces to allow our lines to converge and we are able to approximate perspective transformations with a certain degree of distortion. For each of the other points we'll simply use the same affine transformations. In my explanation I've only detailed one corner P4.

Controlling Distortion
To reduce the amount of distortion we'll simply create more subdivisions, or tessellations, for some given picture. As the pieces become smaller and smaller the distances between where pixels are and should be become closer and closer.

Here is an example with draggable corners and smoothing:

Verification Mathematically:
For those that are interested, we can prove this mathematically because of the way image data is manipulated mathematically by these affine transformations. I'll talk about this next time for the real nerds.

Download the source

Advanced OOP: Semaphore Follow Up

Here's an example of a test of AS3 Semaphore code.

http://www.henrytseng.com/storage/blog/semaphore.zip

You can download and use it according to the GNU General Public License as published by
the Free Software Foundation. Enjoy.

Advanced OOP: Understanding Semaphores

One very useful programming algorithm that is very useful in Flash comes from concurrent programming, and is called mutual exclusion. If you've taken classes in operating systems these concepts may be familiar to you.

About Mutual Exclusion
Mutual Exclusion is all about common resources and making sure blocks of code that share these resources aren't halted when requests are made. For example, if we have 2 programs and 2 resources, both of which are required for a specific operation, both programs must take turns using the resources.

Say program 1 acquires resource 1 the same moment that program 2 acquires resource 2. Since neither program can complete their operation without the other resource; we have what we call a dead lock. This stops the program from running or creates undesired effects. Without a specific implementation to prevent this situation from occurring we have a race condition where program 1 and 2 are competing to finish their blocks of code.

What is a Semaphore
A semaphore is a classic example of an algorithm used to solve this particular situation.

Here's code for a semaphore:

class Semaphore extends EventHandler {
// events
public static var ADDED                : String = 'added';            // resource was added

// used as events and states
public static var LOCKED                : String = 'locked';        // anything locked
public static var UNLOCKED            : String = 'unlocked';        // everything unlocked

private var _lockHash                    : Object;
private var _state                        : String;            // defaults to unlocked
private var _numLocked                    : Number;
private var _numTotal                    : Number;

public function Semaphore($state:String) {
  _state=($state) ? $state : UNLOCKED;
  _lockHash={};
  _numLocked=0;
  _numTotal=0;
}

public function lock($name:String):Void {
  // change count
  if(_lockHash[$name]==undefined) _numTotal++;
  if(_lockHash[$name]!=LOCKED) _numLocked++;

  // lock item
  _lockHash[$name] = LOCKED;

  // something locked
  if(_state == UNLOCKED) {
      _state=LOCKED;
      dispatchEvent({
          type:         LOCKED,
          target:        this
      });
  }
}

public function unlock($name:String):Void {
  // change count
  if(_lockHash[$name]==undefined) _numTotal++;
  if(_lockHash[$name]==LOCKED) _numLocked--;

  // unlock item
  _lockHash[$name] = UNLOCKED;

  // everything unlocked
  if(_numLocked==0 && _state==LOCKED) {
      _state=UNLOCKED;
      dispatchEvent({
          type:        UNLOCKED,
          target:        this
      });
  }
}

public function get numLocked():Number { return _numLocked; }

public function get numTotal():Number { return _numTotal; }

public function get state():String { return _state; }

public function remove():Void {
  removeAllEventListeners();
  _lockHash=null;
}
}

In this class definition we store locks in a hash called _lockHash. We'll store things when a lock or an unlock is invoked. We'll also store the number or locks and total locks. This way we won't have to count all of the locks each time we change their values.

By default the Semaphore starts in an UNLOCKED state. If anyone requests a lock when the semaphore is in a UNLOCKED state we'll dispatch a LOCK event to tell everyone and we'll change the state to LOCKED. When the last lock is released we'll dispatch an UNLOCK event and set the state of the semaphore to UNLOCKED.

And there we have it. I'll show some more examples when I get a chance. There's some interesting applications that simplify a lot of programmatic situations.

Beginner OOP: Observer and Event Delegation Patterns (Part 2)

Now remember last time we talked about the observer design pattern. The observer pattern is very useful because it centralizes information and allows coordination of the interactions between objects.

But there's more. Let's see what's behind door number 2.

The event delegation design pattern is a similar programming strategy. The difference is that this pattern allows multiple types of events. For example, if we write a program which is able to draw a piano keyboard, we might create a class to represent a single key on the keyboard. This single key object might listen to a data model. Now when our keyboard data model tells us that C# is pressed we're not interested in updating the visuals for every key on our keyboard we're only interested in one key. With the event delegation pattern we're able to dispatch a single specific event that will allow only the objects subscribed to this event to be triggered.

Let's talk about terminology. Delegates are objects interested in events. Delegates listen to a specific event fired from a dispatcher. Let's take a look at some simple code to create an event dispatcher. Our event types are actually represented using strings.

To draw an analogy between the observer pattern and the event delegation pattern: Dispatchers are like observables, delegates are like observers, and events are like updates.

class EventHandler {
private var _hash:Object;

public function EventHandler() {  }    

private function _getListenerIndex($queue:Array, $obj:Object, $listener:String):Number {
  for(var i:Number=$queue.length-1; i>=0 &&$queue; i--) {
  if($queue[i].l == $listener && $queue[i].o == $obj) return i;
}
   return -1;    // didn't find anything
}

public function addEventListener($type:String, $obj:Object, $listener:String, $useCapture:Boolean, $priority:Number, $useWeakReference:Boolean):Void {
  if(_hash===undefined)              _hash={};          
if(_hash[$type]===undefined) _hash[$type]=[];
  var i:Number=_getListenerIndex(_hash[$type], $obj, $listener);  
if(i==-1) {
  _hash[$type].push({o:$obj, l:$listener});
}
}

public function dispatchEvent($event:Object):Boolean {
  if(!hasEventListener($event.type)) return false;  
var queue:Array=_hash[$event.type];  
for(var i:Number=queue.length-1; i>=0 &&queue; i--) {      
  var obj:Object = queue[i].o;      
  var fxn:String = queue[i].l;      
  obj[fxn]($event);
}  
return true;
}

public function hasEventListener($type:String):Boolean {  
if(_hash[$type]!=null && _hash[$type].length>0) return true;  
return false;
}

public function removeEventListener($type:String, $obj:Object, $listener:String, $useCapture:Boolean):Void {
if($type!=undefined && $listener==undefined) {      
  delete(_hash[$type]);             return;
}  
var i:Number = _getListenerIndex(_hash[$type], $obj, $listener)         if(i!=-1)
_hash[$type].splice(i,1);
}    

public function removeAllEventListeners():Void { 
delete(_hash);     }
}

In the above code, we have an object, our hash, which acts as an index for our different event types. Each event type then has a list of delegates. These delegates have methods which will run in their respective scopes.

The addEventListener function will first locates the event list, then if the delegate is not already on the list, it pushes the delegate to the list. When the event occurs our dispatchEvent function locate the event list and call each delegate on the list notifying them that the event has occurred. We also include a removeEventListener function to remove delegates from events.

And there we have it.

After Thought
Now, you might ask why would anyone want to write a whole new event delegation class. Aren't there classes written in Flash which accomplish this? Partly, Flash MX and other provided classes do not run code in their intended functional scopes. This creates a large problem since event delegation is typically deployed inter-object. Classes written to satisfy this need are mostly external classes outside of Flash. Grant Skinner has written a great event class called GDispatcher.

ActionScript 3.0 now uses a similar event model which allows functions to run in their proper scope. In addition, most classes in AS3 now inherit from the EventDispatcher class.