Adapted LavosSpawn's idea for more efficient screen updating. It still

renders the entire screen every frame, but it tries to update (i.e. copy to
the backend) only the parts of the screen that actually changed. At least
approximately so.

svn-id: r12142

9 files changed, 118 insertions, 24 deletions

diff --git a/sword2/controls.cpp b/sword2/controls.cpp
index f06977b0dd..68ce63e2bd 100644
--- a/sword2/controls.cpp
+++ b/sword2/controls.cpp
@@ -283,7 +283,7 @@ int Dialog::run() {
 	while (!_finish) {
 		// So that the menu icons will reach their full size
 		_gui->_vm->_graphics->processMenu();
-		_gui->_vm->_graphics->updateDisplay();
+		_gui->_vm->_graphics->updateDisplay(false);
 
 		int16 newMouseX = _gui->_vm->_input->_mouseX;
 		int16 newMouseY = _gui->_vm->_input->_mouseY + 40;
diff --git a/sword2/driver/d_draw.cpp b/sword2/driver/d_draw.cpp
index 28e57a2709..91c2ba6888 100644
--- a/sword2/driver/d_draw.cpp
+++ b/sword2/driver/d_draw.cpp
@@ -32,12 +32,24 @@ Graphics::Graphics(Sword2Engine *vm, int16 width, int16 height)
 
 	int i, j;
 
+	_buffer = _dirtyGrid = NULL;
+
 	_buffer = (byte *) malloc(width * height);
 	if (!_buffer)
 		error("Could not initialise display");
 
 	_vm->_system->init_size(width, height);
 
+	_gridWide = width / CELLWIDE;
+	_gridDeep = height / CELLDEEP;
+
+	if ((width % CELLWIDE) || (height % CELLDEEP))
+		error("Bad cell size");
+
+	_dirtyGrid = (byte *) calloc(_gridWide, _gridDeep);
+	if (!_buffer)
+		error("Could not initialise dirty grid");
+
 	for (i = 0; i < ARRAYSIZE(_blockSurfaces); i++)
 		_blockSurfaces[i] = NULL;
 
@@ -51,6 +63,11 @@ Graphics::Graphics(Sword2Engine *vm, int16 width, int16 height)
 	}
 }
 
+Graphics::~Graphics() {
+	free(_buffer);
+	free(_dirtyGrid);
+}
+
 /**
  * @return the graphics detail setting
  */
@@ -199,6 +216,7 @@ int32 MoviePlayer::play(char *filename, MovieTextObject *text[], uint8 *musicOut
 			if (frameCounter == text[textCounter]->endFrame) {
 				closeTextObject(text[textCounter]);
 				_vm->_graphics->clearScene();
+				_vm->_graphics->setNeedFullRedraw();
 				textCounter++;
 			}
 
diff --git a/sword2/driver/d_draw.h b/sword2/driver/d_draw.h
index edcd220ac8..0d7b3fb310 100644
--- a/sword2/driver/d_draw.h
+++ b/sword2/driver/d_draw.h
@@ -41,6 +41,10 @@ namespace Sword2 {
 #define SCALE_MAXWIDTH		512
 #define SCALE_MAXHEIGHT		512
 
+// Dirty grid cell size
+#define CELLWIDE		10
+#define CELLDEEP		20
+
 #if !defined(__GNUC__)
 	#pragma START_PACK_STRUCTS
 #endif
@@ -85,6 +89,10 @@ private:
 	Sword2Engine *_vm;
 
 	byte *_buffer;
+	byte *_dirtyGrid;
+
+	uint16 _gridWide;
+	uint16 _gridDeep;
 
 	int32 _renderCaps;
 	int8 _renderLevel;
@@ -179,6 +187,7 @@ private:
 
 public:
 	Graphics(Sword2Engine *vm, int16 width, int16 height);
+	~Graphics();
 
 	// Game screen metrics
 	int16 _screenWide;
@@ -197,7 +206,7 @@ public:
 	int32 setMenuIcon(uint8 menu, uint8 pocket, uint8 *icon);
 	void closeMenuImmediately(void);
 
-	void updateDisplay(void);
+	void updateDisplay(bool redrawScene = true);
 	void setWindowName(const char *windowName);
 	void setNeedFullRedraw(void);
 
diff --git a/sword2/driver/palette.cpp b/sword2/driver/palette.cpp
index 3cfa4bc580..bdbfb4a3f8 100644
--- a/sword2/driver/palette.cpp
+++ b/sword2/driver/palette.cpp
@@ -113,10 +113,14 @@ uint8 Graphics::quickMatch(uint8 r, uint8 g, uint8 b) {
 void Graphics::setPalette(int16 startEntry, int16 noEntries, uint8 *colourTable, uint8 fadeNow) {
 	if (noEntries) {
 		memcpy(&_palCopy[startEntry][0], colourTable, noEntries * 4);
-		if (fadeNow == RDPAL_INSTANT)
+		if (fadeNow == RDPAL_INSTANT) {
 			_vm->_system->set_palette((const byte *) _palCopy, startEntry, noEntries);
-	} else
+			setNeedFullRedraw();
+		}
+	} else {
 		_vm->_system->set_palette((const byte *) _palCopy, 0, 256);
+		setNeedFullRedraw();
+	}
 }
 
 void Graphics::dimPalette(void) {
@@ -126,6 +130,7 @@ void Graphics::dimPalette(void) {
 		p[i] /= 2;
 
 	_vm->_system->set_palette(p, 0, 256);
+	setNeedFullRedraw();
 }
 
 /**
@@ -227,6 +232,7 @@ void Graphics::fadeServer(void) {
 	}
 
 	_vm->_system->set_palette(newPalette, 0, 256);
+	setNeedFullRedraw();
 }
 
 } // End of namespace Sword2
diff --git a/sword2/driver/rdwin.cpp b/sword2/driver/rdwin.cpp
index 142e7059c5..f0ac52d9b6 100644
--- a/sword2/driver/rdwin.cpp
+++ b/sword2/driver/rdwin.cpp
@@ -66,28 +66,78 @@ void Input::parseEvents(void) {
 	}
 }
 
-void Graphics::setNeedFullRedraw() {
+/**
+ * Tell updateDisplay() that the scene needs to be completely updated.
+ */
+
+void Graphics::setNeedFullRedraw(void) {
 	_needFullRedraw = true;
 }
 
 /**
- * This function should be called at a high rate (> 20 per second) to service
- * windows and the interface it provides.
+ * This function has two purposes: It redraws the scene, and it handles input
+ * events, palette fading, etc. It should be called at a high rate (> 20 per
+ * second), but the scene is usually only redrawn about 12 times per second,
+ * except when then screen is scrolling.
+ *
+ * @param redrawScene If true, redraw the scene.
  */
 
-void Graphics::updateDisplay(void) {
+void Graphics::updateDisplay(bool redrawScene) {
 	_vm->_input->parseEvents();
 	fadeServer();
 
-	// FIXME: We re-render the entire picture area of the screen for each
-	// frame, which is pretty horrible.
+	if (redrawScene) {
+		int i;
+
+		// Note that the entire scene is always rendered, which is less
+		// than optimal, but at least we can try to be intelligent
+		// about updating the screen afterwards.
+
+		if (_needFullRedraw) {
+			// Update the entire screen. This is necessary when
+			// scrolling, fading, etc.
+
+			_vm->_system->copy_rect(_buffer + MENUDEEP * _screenWide, _screenWide, 0, MENUDEEP, _screenWide, _screenDeep - 2 * MENUDEEP);
+			_needFullRedraw = false;
+		} else {
+			// Update only the dirty areas of the screen
+
+			int j, x, y;
+			int stripWide;
+
+			for (i = 0; i < _gridDeep; i++) {
+				stripWide = 0;
+
+				for (j = 0; j < _gridWide; j++) {
+					if (_dirtyGrid[i * _gridWide + j]) {
+						stripWide++;
+					} else if (stripWide) {
+						x = CELLWIDE * (j - stripWide);
+						y = CELLDEEP * i;
+						_vm->_system->copy_rect(_buffer + y * _screenWide + x, _screenWide, x, y, stripWide * CELLWIDE, CELLDEEP);
+						stripWide = 0;
+					}
+				}
+
+				if (stripWide) {
+					x = CELLWIDE * (j - stripWide);
+					y = CELLDEEP * i;
+					_vm->_system->copy_rect(_buffer + y * _screenWide + x, _screenWide, x, y, stripWide * CELLWIDE, CELLDEEP);
+					stripWide = 0;
+				}
+			}
+		}
+
+		// Age the dirty cells one generation. This way we keep track
+		// of both the cells that were updated this time, and the ones
+		// that were updated the last time.
 
-	if (_needFullRedraw) {
-		_vm->_system->copy_rect(_buffer + MENUDEEP * _screenWide, _screenWide, 0, MENUDEEP, _screenWide, _screenDeep - 2 * MENUDEEP);
-		_needFullRedraw = false;
+		for (i = 0; i < _gridWide * _gridDeep; i++)
+			_dirtyGrid[i] >>= 1;
 	}
 
-	// We still need to update because of fades, menu animations, etc.
+	// We always need to update because of fades, menu animations, etc.
 	_vm->_system->update_screen();
 }
 
diff --git a/sword2/driver/render.cpp b/sword2/driver/render.cpp
index ff75e4fa25..1846efa2a8 100644
--- a/sword2/driver/render.cpp
+++ b/sword2/driver/render.cpp
@@ -75,7 +75,7 @@ void Graphics::blitBlockSurface(BlockSurface *s, Common::Rect *r, Common::Rect *
 	}
 
 	// UploadRect(r);
-	setNeedFullRedraw();
+	// setNeedFullRedraw();
 }
 
 // I've made the scaling two separate functions because there were cases from
@@ -519,6 +519,7 @@ void Graphics::drawLine(int16 x0, int16 y0, int16 x1, int16 y1, uint8 colour) {
 void Graphics::setLocationMetrics(uint16 w, uint16 h) {
 	_locationWide = w;
 	_locationDeep = h;
+	setNeedFullRedraw();
 }
 
 /**
@@ -598,6 +599,9 @@ void Graphics::startRenderCycle(void) {
 		_renderTooSlow = false;
 	}
 
+	if (_scrollXOld != _scrollX || _scrollYOld != _scrollY)
+		setNeedFullRedraw();
+
 	_framesPerGameCycle = 0;
 }
 
@@ -656,6 +660,9 @@ bool Graphics::endRenderCycle(void) {
 		_scrollY = (int16) (_scrollYOld + ((_scrollYTarget - _scrollYOld) * (_startTime - _initialTime + _renderAverageTime)) / (_totalTime - _initialTime));
 	}
 
+	if (_scrollX != _scrollXOld || _scrollY != _scrollYOld)
+		setNeedFullRedraw();
+
 	return false;
 }
 
diff --git a/sword2/driver/sprite.cpp b/sword2/driver/sprite.cpp
index 2ec83b7808..ba030890f6 100644
--- a/sword2/driver/sprite.cpp
+++ b/sword2/driver/sprite.cpp
@@ -320,7 +320,6 @@ void Graphics::drawSurface(SpriteInfo *s, uint8 *surface, Common::Rect *clipRect
 	}
 
 	updateRect(&rd);
-	setNeedFullRedraw();
 }
 
 /**
@@ -613,9 +612,17 @@ int32 Graphics::drawSprite(SpriteInfo *s) {
 	if (freeSprite)
 		free(sprite);
 
-	// updateRect(&rd);
-	setNeedFullRedraw();
+	// Mark the approximate area of the sprite as "dirty", first generation
 
+	int16 gridX1 = rd.left / CELLWIDE;
+	int16 gridY1 = rd.top / CELLDEEP;
+	int16 gridX2 = (rd.right - 1) / CELLWIDE;
+	int16 gridY2 = (rd.bottom - 1) / CELLDEEP;
+
+	for (i = gridY1; i <= gridY2; i++)
+		for (j = gridX1; j <= gridX2; j++)
+			_dirtyGrid[i * _gridWide + j] = 2;
+	
 	return RD_OK;
 }
 
diff --git a/sword2/function.cpp b/sword2/function.cpp
index e9ca24ba4f..3dd6a4cb7c 100644
--- a/sword2/function.cpp
+++ b/sword2/function.cpp
@@ -623,7 +623,6 @@ int32 Logic::fnPlayCredits(int32 *params) {
 		bool foundStartLine = false;
 
 		_vm->_graphics->clearScene();
-		_vm->_graphics->setNeedFullRedraw();
 
 		for (i = startLine; i < lineCount; i++) {
 			// Free any sprites that have scrolled off the screen
diff --git a/sword2/sword2.cpp b/sword2/sword2.cpp
index 4c0340950c..c9d66990b3 100644
--- a/sword2/sword2.cpp
+++ b/sword2/sword2.cpp
@@ -327,8 +327,6 @@ void Sword2Engine::go() {
 		if (_debugger->isAttached())
 			_debugger->onFrame();
 
-		_graphics->updateDisplay();
-
 #ifdef _SWORD2_DEBUG
 // FIXME: If we want this, we should re-work it to use the backend's
 // screenshot functionality.
@@ -456,10 +454,10 @@ void Sword2Engine::startGame(void) {
 
 void Sword2Engine::sleepUntil(uint32 time) {
 	while (_system->get_msecs() < time) {
-		// Make sure menu animations and fades don't suffer
+		// Make sure menu animations and fades don't suffer, but don't
+		// redraw the entire scene.
 		_graphics->processMenu();
-		_graphics->updateDisplay();
-
+		_graphics->updateDisplay(false);
 		_system->delay_msecs(10);
 	}
 }