Sunday, October 10, 2010

Animating the Canvas part 7: Dirty Knives

I forgot to mention last week that the source code for parts 6 though 8 is located at It is time to start dealing with overlap. This will all be handled by the addDirty function which adds a dirty rectangle to the list of dirty rectangles. As before, this function adds dirty rectangles to the root layer. This time, however, an additional three steps have been added to this process.

The first step is simply to go through the existing list and make sure that the rectangle to be added isn't already in the list. By in the list, we are checking to see if there is a rectangle in the dirty rectangle list that covers the rectangle being added. If there is, our work is done and we can return from the function. This code is simply a traversal of the dirty rectangle list with a call to a rectangle function called containsRect.

ContainsRect is a simple function that simply checks to see if a passed rectangle is contained within the rectangle. This is simply done by seeing if the top left corner is in the bounds of the rectangle. If it is then a check is made to see if the bottom right corner is in the rectangle. If it is, then the rectangle is contained.

If the first step does not eliminate the dirty rectangle, then a second pass through the dirty rectangle list is made. This time, we are seeing if the new dirty rectangle covers some of the rectangles in the list. If it does, those rectangles can be removed from the list. This is why having the ability to remove nodes from the dirty rectangle list is important.

The third part is a really large chunk of code which is a bit too big to dump here so if my explanation is not good enough please review the code. This pass is where we make sure that the dirty rectangle doesn't overlap other rectangles in the list of dirty rectangles. If there is an overlap, the rectangle gets split. The check to find an overlap is simply a traversal of the dirty rectangle list with the traversal being stopped if an overlap is detected.

        var overlap = null;
        nextDirty = this.dirtyList.nxt;
        while (nextDirty != null) {
            var bounds = nextDirty.rect;
            if (dirty.rect.intersects(bounds)) {
                overlap = bounds;
                nextDirty = null;
            } else
                nextDirty = nextDirty.nxt;

If there is an overlap, the goal then becomes to divide the dirty rectangle. First, we see if there is overlap on the left side. If there is, we create a new rectangle that contains the left portion of the dirty rectangle up to the start of the overlap. This rectangle gets sent to the addDirty function so that it gets processed as there may be other overlaps that cause it to be split up further.

The dirty rectangle is then resized to have the dimensions without the sliced portion. At this point we check to see if there is a right overlap. If there is the rectangle is again sliced and addDirty is called for processing the right portion of the rectangle.

The same procedure is done for the top and bottom portions of the rectangle. However, with the bottom portion we do not need to adjust the size of the dirty rectangle because it will be contained by the overlap and can be discarded.

We now have the functioning dirty rectangle system I originally planned. Next week I will actually implement a custom image layer class. After that, I will either conclude this series and start work on a game or will optimise the code. I will decide next week.

No comments: