Animating the Canvas part 6: Linking Dirty Rectangles

While the code we have created so far is usable, the big problem with it is that there is a lot of redrawing as dirty rectangles may overlap each other. If you are dealing with only a small number of objects then this may not be a big deal. Still, my original plan was to subdivide dirty rectangles to eliminate overlap. As I started preparing to write the code to deal with this it became clear that arrays were not the ideal mechanism for dealing with this problem. Instead, I needed a linked list. My JavaScript reference has no mention of any type of linked list class in the standard library so I am going to create my own simple doubly linked list class. This is dirty-rectangle specific class right now though I see no reason why this couldn't be modified and extended to create a general purpose class if such a thing was desired.

Linked lists are a useful concept. They simply are a list of objects with each object in the list pointing to the next object in the list. The advantage this offers is that there is no size limits, it is easy to transverse from start to end, and objects can be easily inserted in the middle of the list. Removing an item from the list isn't difficult but does require knowledge of the previous item. Arrays contain splice and slice functions to do this, but these are problematic and probably extremely inefficient. I say probably because it would depend on how the arrays were implemented.

A linked list would probably suffice for my needs, but as one of the key things I need to do is remove objects from the middle of the list, a doubly linked list would be much more convenient. This is the same as a linked list but instead of just pointing to the next object in the list, they also point to the previous object. This means that no knowledge of other items in the list are needed to remove an item.

The creation of an element in the linked list is simple enough. It is, after all, just references to three objects. In the case of our dirty rectangle class, this is the rectangle that is dirty, the previous node and the next node. The nodes are set to null initially with null being used to determine the beginning and end of the list.

BGLayers.DirtyRect = function(rect)
{
    this.rect = new BGLayers.Rectangle(rect);
    this.prev = null;
    this.nxt = null;
}

Having a node is fine but by itself it is not that useful. To be useful, the node has to be added to a list. Adding to a list only requires a node to the list in which the item is being added to. A node can only belong to one list at a time so it will remove itself from any existing list. The node from the list that this node is being added to will be considered the previous element in the list. As the previous item in the list may already have a next item, the first step then is to take the previous node next element and make it the added nodes next element. The node being added to the list then becomes the next node for the previous node. Likewise, the previous node is the added nodes previous entry. At this point everything is correct with this node, but the next node is not pointing to the added node so if the next node is not null, its previous entry will have to be changed to the added node.

BGLayers.DirtyRect.prototype.addSelf = function(parent)
{
    if ( (this.prev != null) || (this.nxt != null) )
        this.removeSelf();
    this.prev = parent;
    this.nxt = parent.nxt;
    if (this.nxt != null)
        this.nxt.prev = this;
    parent.nxt = this;
}

Removing a node is actually very easy. If the previous node is not null, it's next node becomes the removed nodes next entry. Likewise, if the next node is not null then it's previous entry becomes the removed nodes previous entry. Finally, the previous and next entries for the removed node are set to null so that it is clear that this node is not part of a list.

BGLayers.DirtyRect.prototype.removeSelf = function()
{
    if (this.prev != null) {
        this.prev.nxt = this.nxt;
    }
    if (this.nxt != null)
        this.nxt.prev = this.prev;
    this.prev = null;
    this.nxt = null;   
}

Some implementations of linked lists will have a separate class for manipulating nodes which also controls the root node. If you were going to expand on my linked list code this would be a good idea. For BGLayers, I am simply creating a root node which is not an active part of the list. This is not the best solution but it is very easy to do and doesn't require more classes be written. I might do this for a future version of this library as I am starting to think it is the proper thing to do.

Traversing the list is very simple. My implementation of renderDirty is a good demonstration of doing this. It simply grabs the first real node from the root node and then uses a while loop to continue through the list while the next element is not null. If the list is empty, the root nodes next will be null causing the while loop to exit  immediately. Of course, the loop processes the dirty rectangles by calling render, and then removes the node from the list so the list will be empty at the end of this function.

BGLayers.Layer.prototype.renderDirty = function(ctx)
{
    var nextDirty = this.dirtyList.nxt;
    while (nextDirty != null) {
        var bounds = nextDirty.rect;
        this.render(ctx, bounds);
        var curDirty = nextDirty;
        nextDirty = curDirty.nxt;
        curDirty.removeSelf();
    }
}

Now that we have the dirty rectangle doubly linked list class functioning, next time we will get to the fun part of splitting rectangles.