craftyjs/Crafty — pull request #427 by statico (2013-03-05 06:00:10+00:00)
Title: Improved dirty rectangles algorithm

Attached is an improved algorithm for Crafty's dirty rectangle merging which is faster and more correct. It only ever manifests in Crafty applications which use sprites with greater-than-1-bit alpha channel. It was originally written by Mark Logan (@mlogan).

Demo using master: http://statico.github.com/crafty-dirty-rectangles/master.html

Demo using code from this PR: http://statico.github.com/crafty-dirty-rectangles/modified.html

(View developer console to see the benchmarks.)

## The Problem

Here's a screenshot of an example application using the latest version of Crafty. Red arrows point to the artifacts:
![Screen Shot 2013-03-04 at 6 17 52 PM](https://f.cloud.github.com/assets/137158/220053/8b6026a0-8557-11e2-833b-fdc346ea8ee2.png)

## Benchmarks

Five averages of 100 calls each using the algorithm from master, in seconds:

merge: 0.040643565508878175
merge: 0.04171287193709966
merge: 0.03759406384836772
merge: 0.040346535273117594
merge: 0.036881185980458364

And the same using the new algorithm:

merge: 0.0217425726852057
merge: 0.02055445750529813
merge: 0.02647524913957361
merge: 0.02366336844031616
merge: 0.021237621803094846