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.

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

I'm going to try to post more frequently. Apologies, my posting has been scarce by any means.

This post is for beginner programmers who want to get into object-oriented programming. Let's talk about design patterns. As you may know object oriented programming is all about objects, creating definitions of them and planning interactions between them.

Now design patterns are about common situations encountered in programming. Implementing them and using them is a common practice for programmers and is the day to day challenge of the object-oriented programmer. Of course, there's always millions of ways to hack around problems and get around things, but hacking code, producing spaghetti code, always creates problems when further changes are later required. Structuring good code while it can take more time initially to plan and carefully understand always shortens the amount of time required to later make changes. Good implementation of design patterns always directly solve problems.

It is possible to use design patterns wrong and to over-program. Remember while programming you should account for changes you will later make, but you don't have to program rules for every situation, only the ones you will encounter. It would be useless to write algorithms for situations that will never occur, all situations should obviously be understood and predetermined as use cases in advance.

The Observer Pattern
So let's talk about a common design pattern that people use frequently, the observer pattern.
Like I said earlier the observer pattern is all about interaction between your code. In the observer design pattern you have several objects which require action when a particular piece of data changes value.

That is you have an object that is observable and an object that is your observer. The object that is the center of attention is the observable, this object has data which you are interested in. When this data changes it sends an update call to all of its observers, who then execute the required actions based on this value change in the interested data.

Code for a simple Observable:

class Observable {
private var _list      :Array;
 private var _data      :String;

 public function Observable() {
    _list=[];
 }

     public function register($o:Observer):Void {
            _list.push($o);
     }

     public function set data($s:String):Void {
            _data = $s;
           _update();
     }

     public _update():Void {
            var n:int=_list.length;
           for(var i:int=0; i
     }
}

Code for a simple Observer:

public class Observer {
     public function Observer() { }

     public function update($data:Object):Void {
            /* do something exciting! */
     }
}

Now to set these classes up and use them:

// let's instantiate them
var parent:Observable = new Observable();
var child1:Observer = new Observable();
var child2:Observer = new Observable();

// let's set it up
parent.register(child1);
parent.register(child2);

// now let's get the parent to
parent.data = "new data woohoo!";

Once the parent changes its data all of its children should then change their data.

This is very useful if you want to create a class to manage your in a class dedicated to being your data model, such as when you use the Model-View-Controller design pattern.

Next time let's talk about the event delegation design pattern.