Condense damage list by merging overlapping dirty rectangles

thanks, Craxic, for suggesting the idea for this optimization in #192 !

1 files changed, 36 insertions, 1 deletions

diff --git a/morphic.js b/morphic.js
index 2aaba02..ca84210 100644
--- a/morphic.js
+++ b/morphic.js
@@ -1035,7 +1035,7 @@
 /*global window, HTMLCanvasElement, getMinimumFontHeight, FileReader, Audio,
 FileList, getBlurredShadowSupport*/
 
-var morphicVersion = '2013-September-20';
+var morphicVersion = '2013-October-14';
 var modules = {}; // keep track of additional loaded modules
 var useBlurredShadows = getBlurredShadowSupport(); // check for Chrome-bug
 
@@ -1913,6 +1913,12 @@ Rectangle.prototype.merge = function (aRect) {
     return result;
 };
 
+Rectangle.prototype.mergeWith = function (aRect) {
+    // mutates myself
+    this.origin = this.origin.min(aRect.origin);
+    this.corner = this.corner.max(aRect.corner);
+};
+
 Rectangle.prototype.round = function () {
     return this.origin.round().corner(this.corner.round());
 };
@@ -9950,6 +9956,7 @@ WorldMorph.prototype.fullDrawOn = function (aCanvas, aRect) {
 
 WorldMorph.prototype.updateBroken = function () {
     var myself = this;
+    this.condenseDamages();
     this.broken.forEach(function (rect) {
         if (rect.extent().gt(new Point(0, 0))) {
             myself.fullDrawOn(myself.worldCanvas, rect);
@@ -9958,6 +9965,34 @@ WorldMorph.prototype.updateBroken = function () {
     this.broken = [];
 };
 
+WorldMorph.prototype.condenseDamages = function () {
+    // collapse overlapping damaged rectangles into their unions,
+    // thereby reducing the array of brokens to a manageable size
+
+    function condense(src) {
+        var trgt = [], hit;
+        src.forEach(function (rect) {
+            hit = detect(
+                trgt,
+                function (each) {return each.intersects(rect); }
+            );
+            if (hit) {
+                hit.mergeWith(rect);
+            } else {
+                trgt.push(rect);
+            }
+        });
+        return trgt;
+    }
+
+    var again = true, size = this.broken.length;
+    while (again) {
+        this.broken = condense(this.broken);
+        again = (this.broken.length < size);
+        size = this.broken.length;
+    }
+};
+
 WorldMorph.prototype.doOneCycle = function () {
     this.stepFrame();
     this.updateBroken();