diff --git a/common/rfb/CopyRectDecoder.cxx b/common/rfb/CopyRectDecoder.cxx
index 32ed1b3..23949a8 100644
--- a/common/rfb/CopyRectDecoder.cxx
+++ b/common/rfb/CopyRectDecoder.cxx
@@ -18,6 +18,7 @@
 #include <rdr/MemInStream.h>
 #include <rdr/OutStream.h>
 #include <rfb/PixelBuffer.h>
+#include <rfb/Region.h>
 #include <rfb/CopyRectDecoder.h>
 
 using namespace rfb;
@@ -36,6 +37,23 @@
   os->copyBytes(is, 4);
 }
 
+
+void CopyRectDecoder::getAffectedRegion(const Rect& rect,
+                                        const void* buffer,
+                                        size_t buflen,
+                                        const ConnParams& cp,
+                                        Region* region)
+{
+  rdr::MemInStream is(buffer, buflen);
+  int srcX = is.readU16();
+  int srcY = is.readU16();
+
+  Decoder::getAffectedRegion(rect, buffer, buflen, cp, region);
+
+  region->assign_union(Region(rect.translate(Point(srcX-rect.tl.x,
+                                                   srcY-rect.tl.y))));
+}
+
 void CopyRectDecoder::decodeRect(const Rect& r, const void* buffer,
                                  size_t buflen, const ConnParams& cp,
                                  ModifiablePixelBuffer* pb)
diff --git a/common/rfb/CopyRectDecoder.h b/common/rfb/CopyRectDecoder.h
index 998a509..1d2ce53 100644
--- a/common/rfb/CopyRectDecoder.h
+++ b/common/rfb/CopyRectDecoder.h
@@ -28,6 +28,9 @@
     virtual ~CopyRectDecoder();
     virtual void readRect(const Rect& r, rdr::InStream* is,
                           const ConnParams& cp, rdr::OutStream* os);
+    virtual void getAffectedRegion(const Rect& rect, const void* buffer,
+                                   size_t buflen, const ConnParams& cp,
+                                   Region* region);
     virtual void decodeRect(const Rect& r, const void* buffer,
                             size_t buflen, const ConnParams& cp,
                             ModifiablePixelBuffer* pb);
diff --git a/common/rfb/DecodeManager.cxx b/common/rfb/DecodeManager.cxx
index a444eb7..ddebf0a 100644
--- a/common/rfb/DecodeManager.cxx
+++ b/common/rfb/DecodeManager.cxx
@@ -22,6 +22,7 @@
 #include <rfb/CConnection.h>
 #include <rfb/DecodeManager.h>
 #include <rfb/Decoder.h>
+#include <rfb/Region.h>
 
 #include <rfb/LogWriter.h>
 
@@ -129,6 +130,10 @@
   entry->pb = pb;
   entry->bufferStream = bufferStream;
 
+  decoder->getAffectedRegion(r, bufferStream->data(),
+                             bufferStream->length(), conn->cp,
+                             &entry->affectedRegion);
+
   queueMutex->lock();
 
   // The workers add buffers to the end so it's safe to assume
@@ -233,6 +238,7 @@
 DecodeManager::QueueEntry* DecodeManager::DecodeThread::findEntry()
 {
   std::list<DecodeManager::QueueEntry*>::iterator iter;
+  Region lockedRegion;
 
   if (manager->workQueue.empty())
     return NULL;
@@ -243,13 +249,24 @@
   for (iter = manager->workQueue.begin();
        iter != manager->workQueue.end();
        ++iter) {
+    DecodeManager::QueueEntry* entry;
+
+    entry = *iter;
+
     // Another thread working on this?
-    if ((*iter)->active)
-      continue;
+    if (entry->active)
+      goto next;
+
+    // Check overlap with earlier rectangles
+    if (!lockedRegion.intersect(entry->affectedRegion).is_empty())
+      goto next;
 
     // FIXME: check dependencies between rects
 
-    return *iter;
+    return entry;
+
+next:
+    lockedRegion.assign_union(entry->affectedRegion);
   }
 
   return NULL;
diff --git a/common/rfb/DecodeManager.h b/common/rfb/DecodeManager.h
index 1a974ea..dec7a6c 100644
--- a/common/rfb/DecodeManager.h
+++ b/common/rfb/DecodeManager.h
@@ -23,6 +23,7 @@
 
 #include <os/Thread.h>
 
+#include <rfb/Region.h>
 #include <rfb/encodings.h>
 
 namespace os {
@@ -60,6 +61,7 @@
       const ConnParams* cp;
       ModifiablePixelBuffer* pb;
       rdr::MemOutStream* bufferStream;
+      Region affectedRegion;
     };
 
     std::list<rdr::MemOutStream*> freeBuffers;
diff --git a/common/rfb/Decoder.cxx b/common/rfb/Decoder.cxx
index f9bbffc..df785eb 100644
--- a/common/rfb/Decoder.cxx
+++ b/common/rfb/Decoder.cxx
@@ -18,6 +18,7 @@
  */
 #include <stdio.h>
 #include <rfb/encodings.h>
+#include <rfb/Region.h>
 #include <rfb/Decoder.h>
 #include <rfb/RawDecoder.h>
 #include <rfb/CopyRectDecoder.h>
@@ -36,6 +37,13 @@
 {
 }
 
+void Decoder::getAffectedRegion(const Rect& rect, const void* buffer,
+                                size_t buflen, const ConnParams& cp,
+                                Region* region)
+{
+  region->reset(rect);
+}
+
 bool Decoder::supported(int encoding)
 {
   switch (encoding) {
diff --git a/common/rfb/Decoder.h b/common/rfb/Decoder.h
index 95c1466..f631a55 100644
--- a/common/rfb/Decoder.h
+++ b/common/rfb/Decoder.h
@@ -53,6 +53,13 @@
     // A lock will be held whilst these are called so it is safe to
     // read and update internal state as necessary.
 
+    // getAffectedRegion() returns the parts of the frame buffer will
+    // be either read from or written do when decoding this rect. The
+    // default implementation simply returns the given rectangle.
+    virtual void getAffectedRegion(const Rect& rect, const void* buffer,
+                                   size_t buflen, const ConnParams& cp,
+                                   Region* region);
+
     // decodeRect() decodes the given rectangle with data from the
     // given buffer, onto the ModifiablePixelBuffer. The PixelFormat of
     // the PixelBuffer might not match the ConnParams and it is up to