On second thought, an octree only works if the color to look up is in the palette.

So using a table-based approach to find the nearest color now, using only the upper 6 bits to stop the table from getting too large. It still takes noticeable time to build it. :/
But as a result, the video actually looks okay now...

svn-id: r35298

9 files changed, 171 insertions, 183 deletions

diff --git a/engines/gob/coktelvideo.cpp b/engines/gob/coktelvideo.cpp
index aa265432a7..555ce1612c 100644
--- a/engines/gob/coktelvideo.cpp
+++ b/engines/gob/coktelvideo.cpp
@@ -72,7 +72,6 @@ bool Imd::load(Common::SeekableReadStream &stream) {
 
 	// Palette
 	_stream->read((byte *) _palette, 768);
-	notifyChangedPalette();
 
 	// Standard coordinates
 	if (_version >= 3) {
@@ -198,11 +197,6 @@ void Imd::setFrameRate(int16 frameRate) {
 	_frameLength = 1000 / _frameRate;
 }
 
-void Imd::setPalette(const byte *palette) {
-	memcpy(_palette, palette, 768);
-	notifyChangedPalette();
-}
-
 void Imd::setXY(int16 x, int16 y) {
 	// Adjusting the standard coordinates
 	if (_stdX != -1) {
@@ -588,8 +582,6 @@ CoktelVideo::State Imd::processFrame(uint16 frame) {
 			state.flags |= kStatePalette;
 
 			_stream->read(_palette, 768);
-			notifyChangedPalette();
-
 			cmd = _stream->readUint16LE();
 		}
 
@@ -681,7 +673,6 @@ uint32 Imd::renderFrame(int16 left, int16 top, int16 right, int16 bottom) {
 		int index = *dataPtr++;
 		// 16 entries with each 3 bytes (RGB)
 		memcpy(_palette + index * 3, dataPtr, MIN((255 - index) * 3, 48));
-		notifyChangedPalette();
 
 		retVal = kStatePalette;
 		dataPtr += 48;
@@ -879,7 +870,7 @@ const uint16 Vmd::_tableDPCM[128] = {
 	0x0F00, 0x1000, 0x1400, 0x1800, 0x1C00, 0x2000, 0x3000, 0x4000
 };
 
-Vmd::Vmd() {
+Vmd::Vmd(PaletteLUT *palLUT) : _palLUT(palLUT) {
 	clear(false);
 }
 
@@ -924,7 +915,8 @@ bool Vmd::load(Common::SeekableReadStream &stream) {
 	if ((_width != 0) && (_height != 0)) {
 		_hasVideo = true;
 		_features |= kFeaturesVideo;
-		_codecIndeo3 = new Indeo3(_width, _height);
+		if (_features & kFeaturesFullColor)
+			_codecIndeo3 = new Indeo3(_width, _height, _palLUT);
 	} else
 		_hasVideo = false;
 
@@ -955,7 +947,6 @@ bool Vmd::load(Common::SeekableReadStream &stream) {
 	// 0x1A (26)
 
 	_stream->read((byte *) _palette, 768);
-	notifyChangedPalette();
 
 	// 0x31A (794)
 
@@ -1255,8 +1246,6 @@ CoktelVideo::State Vmd::processFrame(uint16 frame) {
 				uint8 count = _stream->readByte();
 
 				_stream->read(_palette + index * 3, (count + 1) * 3);
-				notifyChangedPalette();
-
 				_stream->skip((255 - count) * 3);
 
 				state.flags |= kStatePalette;
@@ -1628,9 +1617,4 @@ Common::MemoryReadStream *Vmd::getExtraData(const char *fileName) {
 	return stream;
 }
 
-void Vmd::notifyChangedPalette() {
-	if (_codecIndeo3)
-		_codecIndeo3->setPalette(_palette);
-}
-
 } // End of namespace Gob
diff --git a/engines/gob/coktelvideo.h b/engines/gob/coktelvideo.h
index c167db68cd..51e61a2979 100644
--- a/engines/gob/coktelvideo.h
+++ b/engines/gob/coktelvideo.h
@@ -33,6 +33,7 @@
 
 namespace Gob {
 
+class PaletteLUT;
 class Indeo3;
 
 /** Common interface for handling Coktel Vision videos and derivated formats. */
@@ -137,8 +138,6 @@ public:
 	/** Set the frame rate. */
 	virtual void setFrameRate(int16 frameRate) = 0;
 
-	virtual void setPalette(const byte *palette) = 0;
-
 	/** Set the coordinations where to draw the video. */
 	virtual void setXY(int16 x, int16 y) = 0;
 	/** Use a specific memory block as video memory. */
@@ -185,9 +184,6 @@ public:
 	virtual void copyCurrentFrame(byte *dest,
 			uint16 left, uint16 top, uint16 width, uint16 height,
 			uint16 x, uint16 y, uint16 pitch, int16 transp = -1) = 0;
-
-protected:
-	virtual void notifyChangedPalette() {}
 };
 
 /** Coktel Vision's IMD files.
@@ -221,8 +217,6 @@ public:
 
 	void setFrameRate(int16 frameRate);
 
-	void setPalette(const byte *palette);
-
 	bool load(Common::SeekableReadStream &stream);
 	void unload();
 
@@ -310,7 +304,7 @@ protected:
 
 class Vmd : public Imd {
 public:
-	Vmd();
+	Vmd(PaletteLUT *palLUT = 0);
 	~Vmd();
 
 	bool getAnchor(int16 frame, uint16 partType,
@@ -373,6 +367,7 @@ protected:
 	byte _soundBytesPerSample;
 	byte _soundStereo; // (0: mono, 1: old-style stereo, 2: new-style stereo)
 
+	PaletteLUT *_palLUT;
 	Indeo3 *_codecIndeo3;
 
 	void clear(bool del = true);
@@ -388,8 +383,6 @@ protected:
 	void filledSoundSlice(uint32 size);
 	void filledSoundSlices(uint32 size, uint32 mask);
 	void deDPCM(byte *soundBuf, byte *dataBuf, int16 &init, uint32 n);
-
-	void notifyChangedPalette();
 };
 
 } // End of namespace Gob
diff --git a/engines/gob/indeo3.cpp b/engines/gob/indeo3.cpp
index 2e01d03da5..3b8c94b5b4 100644
--- a/engines/gob/indeo3.cpp
+++ b/engines/gob/indeo3.cpp
@@ -40,90 +40,127 @@
 
 namespace Gob {
 
-const int Ordered8x8::map[8][8] = {
-	{0, 15, 3, 18, 1, 15, 4, 19},
-	{10, 5, 13, 8, 11, 6, 14, 9},
-	{2, 17, 1, 16, 3, 18, 2, 17},
-	{12, 7, 11, 6, 13, 8, 12, 7},
-	{0, 15, 4, 19, 0, 15, 4, 19},
-	{10, 5, 14, 9, 10, 5, 14, 9},
-	{3, 18, 2, 16, 3, 17, 1, 16},
-	{13, 8, 11, 7, 12, 7, 11, 6}
-};
-
-PalOctree::PalOctree(const byte *palette, byte depth) : _depth(depth) {
+#define SQR(x) ((x) * (x))
+PaletteLUT::PaletteLUT(byte depth, PaletteFormat format) {
 	assert((depth > 1) && (depth < 9));
 
-	build(palette);
+	_depth1 = depth;
+	_depth2 = 2 * _depth1;
+	_shift = 8 - _depth1;
+
+	_dim1 = (1 << _depth1);
+	_dim2 = _dim1 * _dim1;
+	_dim3 = _dim1 * _dim1 * _dim1;
+
+	_format = format;
+
+	_got = _dim1;
+	_lut = new byte[_dim3];
+	_gots = new byte[_dim1];
+
+	memset(_lutPal, 0, 768);
+	memset(_realPal, 0, 768);
+	memset(_gots, 1, _dim1);
+}
+
+void PaletteLUT::setPalette(const byte *palette, PaletteFormat format, byte depth) {
+	assert((depth > 1) && (depth < 9));
+
+	warning("Building new palette LUT");
+
+	int shift = 8 - depth;
+
+	if ((_format == kPaletteRGB) && (format == kPaletteYUV)) {
+		byte *newPal = _realPal;
+		const byte *oldPal = palette;
+		for (int i = 0; i < 256; i++, newPal += 3, oldPal += 3)
+			YUV2RGB(oldPal[0] << shift, oldPal[1] << shift, oldPal[2] << shift,
+					newPal[0], newPal[1], newPal[2]);
+	} else if ((_format == kPaletteYUV) && (format == kPaletteRGB)) {
+		byte *newPal = _realPal;
+		const byte *oldPal = palette;
+		for (int i = 0; i < 256; i++, newPal += 3, oldPal += 3)
+			RGB2YUV(oldPal[0] << shift, oldPal[1] << shift, oldPal[2] << shift,
+					newPal[0], newPal[1], newPal[2]);
+	} else
+		memcpy(_realPal, palette, 768);
+
+	byte *newPal = _lutPal, *oldPal = _realPal;
+	for (int i = 0; i < 768; i++)
+		*newPal++ = (*oldPal++) >> _shift;
+
+	_got = 0;
+	memset(_gots, 0, _dim1);
 }
 
-PalOctree::~PalOctree() {
-	delete _root;
+PaletteLUT::~PaletteLUT() {
+	delete[] _lut;
+	delete[] _gots;
 }
 
-void PalOctree::build(const byte *palette) {
-	_root = new Node(0, 0, 0, 0);
+void PaletteLUT::buildNext() {
+	if (_got >= _dim1)
+		return;
+
+	build(_got++);
+}
 
-	for (int i = 0; i < 256; i++, palette += 3) {
-		byte c1, c2, c3;
-		byte oC1, oC2, oC3;
+void PaletteLUT::build(int d1) {
+	byte *lut = _lut + d1 * _dim2;
 
-		oC1 = c1 = palette[0];
-		oC2 = c2 = palette[1];
-		oC3 = c3 = palette[2];
+	warning("LUT %d/%d", d1, _dim1 - 1);
 
-		Node *node = _root;
-		for (int j = 0; j < _depth; j++) {
-			// Generating an index out of the upper-most bits
-			int n = 4 * (c1 >> 7) + 2 * (c2 >> 7) + (c3 >> 7);
+	for (int j = 0; j < _dim1; j++) {
+		for (int k = 0; k < _dim1; k++) {
+			const byte *p = _lutPal;
+			uint32 d = 0xFFFFFFFF;
+			byte n = 0;
 
-			if (!node->children[n]) {
-				// Found a free place
-				node->children[n] = new Node(i, oC1, oC2, oC3);
-				break;
+			for (int c = 0; c < 256; c++, p += 3) {
+				uint32 di = SQR(d1 - p[0]) + SQR(j - p[1]) + SQR(k - p[2]);
+				if (di < d) {
+					d = di;
+					n = c;
+					if (d == 0)
+						break;
+				}
 			}
 
-			node = node->children[n];
-			c1 <<= 1;
-			c2 <<= 1;
-			c3 <<= 1;
+			*lut++ = n;
 		}
 	}
-}
 
-byte PalOctree::findNearest(byte c1, byte c2, byte c3) const {
-	byte n1, n2, n3;
+	_gots[d1] = 1;
+}
 
-	return findNearest(c1, c2, c3, n1, n2, n3);
+inline int PaletteLUT::getIndex(byte c1, byte c2, byte c3) const {
+	return ((c1 >> _shift) << _depth2) | ((c2 >> _shift) << _depth1) | (c3 >> _shift);
 }
 
-byte PalOctree::findNearest(byte c1, byte c2, byte c3, byte &nc1, byte &nc2, byte &nc3) const {
-	Node *node = _root;
+byte PaletteLUT::findNearest(byte c1, byte c2, byte c3) {
+	return _lut[getIndex(c1, c2, c3)];
+}
 
-	int n = 4 * (c1 >> 7) + 2 * (c2 >> 7) + (c3 >> 7);
-	while (node->children[n]) {
-		node = node->children[n];
+byte PaletteLUT::findNearest(byte c1, byte c2, byte c3, byte &nC1, byte &nC2, byte &nC3) {
+	if (!_gots[c1 >> _shift])
+		build(c1 >> _shift);
 
-		c1 <<= 1;
-		c2 <<= 1;
-		c3 <<= 1;
+	int palIndex = _lut[getIndex(c1, c2, c3)];
+	int i = palIndex * 3;
 
-		n = 4 * (c1 >> 7) + 2 * (c2 >> 7) + (c3 >> 7);
-	}
+	nC1 = _realPal[i + 0];
+	nC2 = _realPal[i + 1];
+	nC3 = _realPal[i + 2];
 
-	nc1 = node->comp[0];
-	nc2 = node->comp[1];
-	nc3 = node->comp[2];
-	return node->index;
+	return palIndex;
 }
 
-SierraLite::SierraLite(int16 width, int16 height) {
+SierraLite::SierraLite(int16 width, int16 height, PaletteLUT *palLUT) {
 	assert((width > 0) && (height > 0));
 
 	_width = width;
 	_height = height;
-
-	_palTree = 0;
+	_palLUT = palLUT;
 
 	_errorBuf = new int32[3 * (2 * (_width + 2*1))];
 	memset(_errorBuf, 0, (3 * (2 * (_width + 2*1))) * sizeof(int32));
@@ -137,10 +174,6 @@ SierraLite::~SierraLite() {
 	delete[] _errorBuf;
 }
 
-void SierraLite::setPalTree(const PalOctree *palTree) {
-	_palTree = palTree;
-}
-
 void SierraLite::newFrame() {
 	_curLine = 0;
 	memset(_errors[0], 0, 3 * _width * sizeof(int32));
@@ -155,7 +188,7 @@ void SierraLite::nextLine() {
 }
 
 byte SierraLite::dither(byte c1, byte c2, byte c3, uint32 x) {
-	assert(_palTree);
+	assert(_palLUT);
 
 	int32 eC1, eC2, eC3;
 
@@ -168,8 +201,9 @@ byte SierraLite::dither(byte c1, byte c2, byte c3, uint32 x) {
 
 	// Find color
 	byte newC1, newC2, newC3;
-	byte newPixel = _palTree->findNearest(c1, c2, c3, newC1, newC2, newC3);
+	byte newPixel = _palLUT->findNearest(c1, c2, c3, newC1, newC2, newC3);
 
+	// Calculate new error
 	eC1 = c1 - newC1;
 	eC2 = c2 - newC2;
 	eC3 = c3 - newC3;
@@ -209,13 +243,12 @@ inline void SierraLite::addErrors(uint32 x, int32 eC1, int32 eC2, int32 eC3) {
 	errNext[x2 + 2] += eC3;
 }
 
-Indeo3::Indeo3(int16 width, int16 height) {
+Indeo3::Indeo3(int16 width, int16 height, PaletteLUT *palLUT) {
 	assert((width > 0) && (height > 0));
 
 	_width = width;
 	_height = height;
-
-	_palTree = 0;
+	_palLUT = palLUT;
 
 	_ditherSL = 0;
 	setDither(kDitherSierraLite);
@@ -228,22 +261,9 @@ Indeo3::~Indeo3() {
 	delete[] _iv_frame[0].the_buf;
 	delete[] _ModPred;
 	delete[] _corrector_type;
-	delete _palTree;
 	delete _ditherSL;
 }
 
-inline void Indeo3::YUV2RGB(byte y, byte u, byte v, byte &r, byte &g, byte &b) {
-	r = CLIP<int>(y + ((1357 * (v - 128)) >> 10), 0, 255);
-	g = CLIP<int>(y - (( 691 * (v - 128)) >> 10) - ((333 * (u - 128)) >> 10), 0, 255);
-	b = CLIP<int>(y + ((1715 * (u - 128)) >> 10), 0, 255);
-}
-
-inline void Indeo3::RGB2YUV(byte r, byte g, byte b, byte &y, byte &u, byte &v) {
-	y = CLIP<int>( ((r * 306) >> 10) + ((g * 601) >> 10) + ((b * 117) >> 10)      , 0, 255);
-	u = CLIP<int>(-((r * 172) >> 10) - ((g * 340) >> 10) + ((b * 512) >> 10) + 128, 0, 255);
-	v = CLIP<int>( ((r * 512) >> 10) - ((g * 429) >> 10) - ((b *  83) >> 10) + 128, 0, 255);
-}
-
 bool Indeo3::isIndeo3(byte *data, uint32 dataLen) {
 	// No data, no Indeo 3
 	if (!data)
@@ -270,22 +290,6 @@ bool Indeo3::isIndeo3(byte *data, uint32 dataLen) {
 	return true;
 }
 
-void Indeo3::setPalette(const byte *palette) {
-	delete _palTree;
-
-	byte paletteYUV[768];
-
-	const byte *rgb = palette;
-	byte *yuv = paletteYUV;
-	for (int i = 0; i < 256; i++, rgb += 3, yuv += 3)
-		RGB2YUV(rgb[0] << 2, rgb[1] << 2, rgb[2] << 2, yuv[0], yuv[1], yuv[2]);
-
-	_palTree = new PalOctree(paletteYUV, 6);
-
-	if (_ditherSL)
-		_ditherSL->setPalTree(_palTree);
-}
-
 void Indeo3::setDither(DitherAlgorithm dither) {
 	delete _ditherSL;
 	_ditherSL = 0;
@@ -294,8 +298,7 @@ void Indeo3::setDither(DitherAlgorithm dither) {
 
 	switch(dither) {
 	case kDitherSierraLite:
-		_ditherSL = new SierraLite(_width, _height);
-		_ditherSL->setPalTree(_palTree);
+		_ditherSL = new SierraLite(_width, _height, _palLUT);
 		break;
 
 	default:
@@ -389,7 +392,7 @@ bool Indeo3::decompressFrame(byte *inData, uint32 dataLen,
 		return false;
 
 	assert(outData);
-	assert(_palTree);
+	assert(_palLUT);
 
 	uint32 frameDataLen = READ_LE_UINT32(inData + 12);
 
@@ -507,7 +510,7 @@ void Indeo3::blitLine(BlitState &s) {
 		byte dataV = lineV[s.curX >> 2];
 
 		for (int n = 0; n < s.scaleWYOut; n++)
-			*s.bufOut++ = _palTree->findNearest(dataY, dataU, dataV);
+			*s.bufOut++ = _palLUT->findNearest(dataY, dataU, dataV);
 	}
 
 	byte *lineDest = s.bufOut - s.lineWidthOut;
diff --git a/engines/gob/indeo3.h b/engines/gob/indeo3.h
index 9c666138b9..7a557f2a76 100644
--- a/engines/gob/indeo3.h
+++ b/engines/gob/indeo3.h
@@ -35,47 +35,59 @@
 
 namespace Gob {
 
-// A simple octree for quickly finding the best matching palette entry
-class PalOctree {
+class PaletteLUT {
 public:
-	PalOctree(const byte *palette, byte depth);
-	~PalOctree();
+	enum PaletteFormat {
+		kPaletteRGB,
+		kPaletteYUV
+	};
+
+	inline static void YUV2RGB(byte y, byte u, byte v, byte &r, byte &g, byte &b) {
+		r = CLIP<int>(y + ((1357 * (v - 128)) >> 10), 0, 255);
+		g = CLIP<int>(y - (( 691 * (v - 128)) >> 10) - ((333 * (u - 128)) >> 10), 0, 255);
+		b = CLIP<int>(y + ((1715 * (u - 128)) >> 10), 0, 255);
+	}
+	inline static void RGB2YUV(byte r, byte g, byte b, byte &y, byte &u, byte &v) {
+		y = CLIP<int>( ((r * 306) >> 10) + ((g * 601) >> 10) + ((b * 117) >> 10)      , 0, 255);
+		u = CLIP<int>(-((r * 172) >> 10) - ((g * 340) >> 10) + ((b * 512) >> 10) + 128, 0, 255);
+		v = CLIP<int>( ((r * 512) >> 10) - ((g * 429) >> 10) - ((b *  83) >> 10) + 128, 0, 255);
+	}
+
+	PaletteLUT(byte depth, PaletteFormat format);
+	~PaletteLUT();
 
-	byte findNearest(byte c1, byte c2, byte c3) const;
-	byte findNearest(byte c1, byte c2, byte c3, byte &nc1, byte &nc2, byte &nc3) const;
+	void setPalette(const byte *palette, PaletteFormat format, byte depth);
+
+	void buildNext();
+
+	byte findNearest(byte c1, byte c2, byte c3);
+	byte findNearest(byte c1, byte c2, byte c3, byte &nC1, byte &nC2, byte &nC3);
 
 private:
-	struct Node {
-		byte index;
-		byte comp[3];
-		struct Node *children[8];
-
-		Node(byte i, byte c1, byte c2, byte c3) : index(i) {
-			memset(children, 0, 8 * sizeof(struct Node *));
-			comp[0] = c1;
-			comp[1] = c2;
-			comp[2] = c3;
-		}
-		~Node() {
-			for (int i = 0; i < 8; i++)
-				delete children[i];
-		}
-	};
+	byte _depth1, _depth2;
+	byte _shift;
+
+	int _dim1, _dim2, _dim3;
 
-	Node *_root;
-	byte _depth;
+	PaletteFormat _format;
+	byte _lutPal[768];
+	byte _realPal[768];
 
-	void build(const byte *palette);
+	int _got;
+	byte *_gots;
+	byte *_lut;
+
+	void build(int d1);
+	inline int getIndex(byte c1, byte c2, byte c3) const;
+	inline void plotEntry(int x, int y, int z, byte e, byte *filled, int &free);
 };
 
 // The Sierra-2-4A ("Filter Light") dithering algorithm
 class SierraLite {
 public:
-	SierraLite(int16 width, int16 height);
+	SierraLite(int16 width, int16 height, PaletteLUT *palLUT);
 	~SierraLite();
 
-	void setPalTree(const PalOctree *palTree);
-
 	void newFrame();
 	void nextLine();
 	byte dither(byte c1, byte c2, byte c3, uint32 x);
@@ -83,7 +95,7 @@ public:
 protected:
 	int16 _width, _height;
 
-	const PalOctree *_palTree;
+	PaletteLUT *_palLUT;
 
 	int32 *_errorBuf;
 	int32 *_errors[2];
@@ -93,34 +105,18 @@ protected:
 	inline void addErrors(uint32 x, int32 eC1, int32 eC2, int32 eC3);
 };
 
-// Ordered ditherer with a 8x8 mask
-class Ordered8x8 {
-public:
-	inline static byte dither(byte c1, byte c2, byte c3, const PalOctree *palTree, uint32 x, uint32 y) {
-		c1 = CLIP<int>(c1 + map[x % 8][y % 8], 0, 255);
-		c2 = CLIP<int>(c2 + map[x % 8][y % 8], 0, 255);
-		c3 = CLIP<int>(c3 + map[x % 8][y % 8], 0, 255);
-		return palTree->findNearest(c1, c2, c3);
-	}
-
-private:
-	static const int map[8][8];
-};
-
 class Indeo3 {
 public:
 	enum DitherAlgorithm {
 		kDitherNone = 0,
-		kDitherSierraLite,
-		kDitherOrdered8x8
+		kDitherSierraLite
 	};
 
-	Indeo3(int16 width, int16 height);
+	Indeo3(int16 width, int16 height, PaletteLUT *palLUT);
 	~Indeo3();
 
 	static bool isIndeo3(byte *data, uint32 dataLen);
 
-	void setPalette(const byte *palette);
 	void setDither(DitherAlgorithm dither);
 
 	bool decompressFrame(byte *inData, uint32 dataLen,
@@ -152,7 +148,7 @@ private:
 	byte *_ModPred;
 	uint16 *_corrector_type;
 
-	PalOctree *_palTree;
+	PaletteLUT *_palLUT;
 
 	DitherAlgorithm _dither;
 	SierraLite *_ditherSL;
@@ -180,9 +176,6 @@ private:
 
 	void blitLine(BlitState &s);
 	void blitLineDither(BlitState &s);
-
-	inline void YUV2RGB(byte y, byte u, byte v, byte &r, byte &g, byte &b);
-	inline void RGB2YUV(byte r, byte g, byte b, byte &y, byte &u, byte &v);
 };
 
 } // End of namespace Gob
diff --git a/engines/gob/inter.h b/engines/gob/inter.h
index 3ea8688bc3..bdab8b84f9 100644
--- a/engines/gob/inter.h
+++ b/engines/gob/inter.h
@@ -624,6 +624,7 @@ protected:
 
 	bool o6_loadCursor(OpFuncParams &params);
 	bool o6_evaluateStore(OpFuncParams &params);
+	bool o6_palLoad(OpFuncParams &params);
 };
 
 } // End of namespace Gob
diff --git a/engines/gob/inter_v6.cpp b/engines/gob/inter_v6.cpp
index 05782e8f4f..d5ef5704d0 100644
--- a/engines/gob/inter_v6.cpp
+++ b/engines/gob/inter_v6.cpp
@@ -32,6 +32,7 @@
 #include "gob/game.h"
 #include "gob/parse.h"
 #include "gob/draw.h"
+#include "gob/indeo3.h"
 
 namespace Gob {
 
@@ -394,7 +395,7 @@ void Inter_v6::setupOpcodes() {
 		{NULL, ""},
 		OPCODE(o2_printText),
 		OPCODE(o1_loadTot),
-		OPCODE(o1_palLoad),
+		OPCODE(o6_palLoad),
 		/* 14 */
 		OPCODE(o1_keyFunc),
 		OPCODE(o1_capturePush),
@@ -582,6 +583,8 @@ void Inter_v6::executeDrawOpcode(byte i) {
 }
 
 bool Inter_v6::executeFuncOpcode(byte i, byte j, OpFuncParams &params) {
+	_vm->_video->_palLUT->buildNext();
+
 	debugC(1, kDebugFuncOp, "opcodeFunc %d.%d [0x%X.0x%X] (%s) - %s, %d, %d",
 			i, j, i, j, getOpcodeFuncDesc(i, j), _vm->_game->_curTotFile,
 			(uint) (_vm->_global->_inter_execPtr - _vm->_game->_totFileData),
@@ -793,4 +796,11 @@ bool Inter_v6::o6_evaluateStore(OpFuncParams &params) {
 	return false;
 }
 
+bool Inter_v6::o6_palLoad(OpFuncParams &params) {
+	o1_palLoad(params);
+	_vm->_video->_palLUT->setPalette((const byte *) _vm->_global->_pPaletteDesc->vgaPal,
+			PaletteLUT::kPaletteRGB, 6);
+	return false;
+}
+
 } // End of namespace Gob
diff --git a/engines/gob/video.cpp b/engines/gob/video.cpp
index 6dd159ddca..4298be6872 100644
--- a/engines/gob/video.cpp
+++ b/engines/gob/video.cpp
@@ -32,6 +32,7 @@
 #include "gob/util.h"
 #include "gob/dataio.h"
 #include "gob/draw.h"
+#include "gob/indeo3.h"
 
 #include "gob/driver_vga.h"
 
@@ -105,6 +106,8 @@ Video::Video(GobEngine *vm) : _vm(vm) {
 	_lastSparse = 0xFFFFFFFF;
 
 	_dirtyAll = false;
+
+	_palLUT = new PaletteLUT(6, PaletteLUT::kPaletteYUV);
 }
 
 char Video::initDriver(int16 vidMode) {
diff --git a/engines/gob/video.h b/engines/gob/video.h
index f539fa76e0..79a1029202 100644
--- a/engines/gob/video.h
+++ b/engines/gob/video.h
@@ -33,6 +33,8 @@
 
 namespace Gob {
 
+class PaletteLUT;
+
 // Some Surfaces are simultaneous in Draw::spritesArray and discrete
 // variables, so it's a references counting class that cleans
 // up its own mess
@@ -116,6 +118,8 @@ public:
 	int16 _screenDeltaX;
 	int16 _screenDeltaY;
 
+	PaletteLUT *_palLUT;
+
 	void freeDriver();
 	void initPrimary(int16 mode);
 	SurfaceDesc *initSurfDesc(int16 vidMode, int16 width,
diff --git a/engines/gob/videoplayer.cpp b/engines/gob/videoplayer.cpp
index d5dfb9847d..e719374b5c 100644
--- a/engines/gob/videoplayer.cpp
+++ b/engines/gob/videoplayer.cpp
@@ -62,7 +62,7 @@ bool VideoPlayer::Video::open(const char *fileName, Type which) {
 	if (which == kVideoTypeIMD) {
 		_video = new Imd();
 	} else if (which == kVideoTypeVMD) {
-		_video = new Vmd();
+		_video = new Vmd(_vm->_video->_palLUT);
 	} else {
 		warning("Couldn't open video \"%s\": Invalid video Type", fileName);
 		close();
@@ -301,9 +301,6 @@ void VideoPlayer::primaryPlay(int16 startFrame, int16 lastFrame, int16 breakKey,
 	if (fade)
 		_vm->_palAnim->fade(0, -2, 0);
 
-	if (video.getFeatures() & CoktelVideo::kFeaturesFullColor)
-		video.setPalette((byte *) _vm->_global->_pPaletteDesc->vgaPal);
-
 	while (startFrame <= lastFrame) {
 		if (doPlay(startFrame, breakKey, palCmd, palStart, palEnd, palFrame, endFrame))
 			break;