Initial commit of new keying nodes

First node is called Keying Screen (Add -> Matte -> Keying Screen) and it's
aimed to resolve issues with gradients on green screens by producing image
with gradient which is later used as an input for screen color in keying nodes.

This node gets motion tracks from given movie clip and trackign object and uses
them to define color and position of points of gradient: for position marker's
position on current frame is sued, for color average color of pattern area is
used.

Gradient is calculating in the following way:
- On first step voronoi diagram is creating for given tracks.
- On second step triangulation of this diagram happens by connecting sites
  to edges which defines area this site belongs to.
- On third step gradient filling of this triangles happens. One of triangle
  vertices is colored with average track color, two rest vertoces are colored
  with average color between two neighbor sites. Current pixel's color in
  triangle is calculating as linear combination of vertices colors and
  barycentric coordinates of this pixel.

This node is implemented for both tile and legacy compositor systems.

Second node is basically a combination of several existing nodes to make keying
more straighforward and reduce spagetti mess in the compositor, but it also
ships some fresh approaches calculating matte which seems to be working better
for not actually green screens.

This node supports:
- Chroma preblur
- Dispilling
- Clip white/black
- Dilate/Erode
- Matte post blur

This node doesn't support chroma pre-blur for legacy compositor (yet).

There're still lots of stuff to be improved here, but this nodes night already
be used i think.

Some details might be found on this wiki page:
http://wiki.blender.org/index.php/User:Nazg-gul/Keying

This patch also contains some currently unused code from color math module, but
it was used for tests and might be used for tests in the future. Think it's ok
to have it in branch at least.

12 files changed, 972 insertions, 0 deletions

diff --git a/source/blender/compositor/CMakeLists.txt b/source/blender/compositor/CMakeLists.txt
index 5e778d4d03b..d4e083f9ec1 100644
--- a/source/blender/compositor/CMakeLists.txt
+++ b/source/blender/compositor/CMakeLists.txt
@@ -331,6 +331,18 @@ set(SRC
 
 	operations/COM_DoubleEdgeMaskOperation.cpp
 	operations/COM_DoubleEdgeMaskOperation.h
+
+	nodes/COM_KeyingNode.cpp
+	nodes/COM_KeyingNode.h
+	nodes/COM_KeyingScreenNode.cpp
+	nodes/COM_KeyingScreenNode.h
+	operations/COM_KeyingOperation.cpp
+	operations/COM_KeyingOperation.h
+	operations/COM_KeyingScreenOperation.cpp
+	operations/COM_KeyingScreenOperation.h
+	operations/COM_KeyingDispillOperation.cpp
+	operations/COM_KeyingDispillOperation.h
+
 operations/COM_ColorSpillOperation.cpp
 operations/COM_ColorSpillOperation.h
 		operations/COM_RenderLayersBaseProg.cpp
diff --git a/source/blender/compositor/intern/COM_Converter.cpp b/source/blender/compositor/intern/COM_Converter.cpp
index dc6409e7b86..747d6495f5d 100644
--- a/source/blender/compositor/intern/COM_Converter.cpp
+++ b/source/blender/compositor/intern/COM_Converter.cpp
@@ -112,6 +112,8 @@
 #include "COM_DoubleEdgeMaskNode.h"
 #include "COM_CropNode.h"
 #include "COM_MaskNode.h"
+#include "COM_KeyingScreenNode.h"
+#include "COM_KeyingNode.h"
 
 Node *Converter::convert(bNode *bNode)
 {
@@ -350,6 +352,11 @@ case CMP_NODE_OUTPUT_FILE:
 		break;
 	case CMP_NODE_MASK:
 		node = new MaskNode(bNode);
+	case CMP_NODE_KEYINGSCREEN:
+		node = new KeyingScreenNode(bNode);
+		break;
+	case CMP_NODE_KEYING:
+		node = new KeyingNode(bNode);
 		break;
 	/* not inplemented yet */
 	default:
diff --git a/source/blender/compositor/nodes/COM_KeyingNode.cpp b/source/blender/compositor/nodes/COM_KeyingNode.cpp
new file mode 100644
index 00000000000..725060371a1
--- /dev/null
+++ b/source/blender/compositor/nodes/COM_KeyingNode.cpp
@@ -0,0 +1,211 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+#include "COM_KeyingNode.h"
+
+#include "COM_ExecutionSystem.h"
+
+#include "COM_KeyingOperation.h"
+#include "COM_KeyingDispillOperation.h"
+
+#include "COM_SeparateChannelOperation.h"
+#include "COM_CombineChannelsOperation.h"
+#include "COM_ConvertRGBToYCCOperation.h"
+#include "COM_ConvertYCCToRGBOperation.h"
+#include "COM_FastGaussianBlurOperation.h"
+#include "COM_SetValueOperation.h"
+
+#include "COM_DilateErodeOperation.h"
+
+#include "COM_SetAlphaOperation.h"
+
+KeyingNode::KeyingNode(bNode *editorNode): Node(editorNode)
+{
+}
+
+OutputSocket *KeyingNode::setupPreBlur(ExecutionSystem *graph, InputSocket *inputImage, int size, OutputSocket **originalImage)
+{
+	memset(&preBlurData, 0, sizeof(preBlurData));
+	preBlurData.sizex = size;
+	preBlurData.sizey = size;
+
+	ConvertRGBToYCCOperation *convertRGBToYCCOperation = new ConvertRGBToYCCOperation();
+	convertRGBToYCCOperation->setMode(0);  /* ITU 601 */
+
+	inputImage->relinkConnections(convertRGBToYCCOperation->getInputSocket(0), 0, graph);
+	graph->addOperation(convertRGBToYCCOperation);
+
+	CombineChannelsOperation *combineOperation = new CombineChannelsOperation();
+	graph->addOperation(combineOperation);
+
+	for (int channel = 0; channel < 4; channel++) {
+		SeparateChannelOperation *separateOperation = new SeparateChannelOperation();
+		separateOperation->setChannel(channel);
+		addLink(graph, convertRGBToYCCOperation->getOutputSocket(0), separateOperation->getInputSocket(0));
+		graph->addOperation(separateOperation);
+
+		if (channel == 0 || channel == 3) {
+			addLink(graph, separateOperation->getOutputSocket(0), combineOperation->getInputSocket(channel));
+		}
+		else {
+			SetValueOperation *setValueOperation = new SetValueOperation();
+			setValueOperation->setValue(1.0f);
+			graph->addOperation(setValueOperation);
+
+			FastGaussianBlurOperation *blurOperation = new FastGaussianBlurOperation();
+			blurOperation->setData(&preBlurData);
+
+			addLink(graph, separateOperation->getOutputSocket(0), blurOperation->getInputSocket(0));
+			addLink(graph, setValueOperation->getOutputSocket(0), blurOperation->getInputSocket(1));
+			addLink(graph, blurOperation->getOutputSocket(0), combineOperation->getInputSocket(channel));
+			graph->addOperation(blurOperation);
+		}
+	}
+
+	ConvertYCCToRGBOperation *convertYCCToRGBOperation = new ConvertYCCToRGBOperation();
+	convertYCCToRGBOperation->setMode(0);  /* ITU 601 */
+	addLink(graph, combineOperation->getOutputSocket(0), convertYCCToRGBOperation->getInputSocket(0));
+	graph->addOperation(convertYCCToRGBOperation);
+
+	*originalImage = convertRGBToYCCOperation->getInputSocket(0)->getConnection()->getFromSocket();
+
+	return convertYCCToRGBOperation->getOutputSocket(0);
+}
+
+OutputSocket *KeyingNode::setupPostBlur(ExecutionSystem *graph, OutputSocket *postBLurInput, int size)
+{
+	memset(&postBlurData, 0, sizeof(postBlurData));
+
+	postBlurData.sizex = size;
+	postBlurData.sizey = size;
+
+	SetValueOperation *setValueOperation = new SetValueOperation();
+
+	setValueOperation->setValue(1.0f);
+	graph->addOperation(setValueOperation);
+
+	FastGaussianBlurOperation *blurOperation = new FastGaussianBlurOperation();
+	blurOperation->setData(&postBlurData);
+
+	addLink(graph, postBLurInput, blurOperation->getInputSocket(0));
+	addLink(graph, setValueOperation->getOutputSocket(0), blurOperation->getInputSocket(1));
+
+	graph->addOperation(blurOperation);
+
+	return blurOperation->getOutputSocket();
+}
+
+OutputSocket *KeyingNode::setupDilateErode(ExecutionSystem *graph, OutputSocket *dilateErodeInput, int distance)
+{
+	DilateStepOperation *dilateErodeOperation;
+
+	if (distance > 0) {
+		dilateErodeOperation = new DilateStepOperation();
+		dilateErodeOperation->setIterations(distance);
+	}
+	else {
+		dilateErodeOperation = new ErodeStepOperation();
+		dilateErodeOperation->setIterations(-distance);
+	}
+
+	addLink(graph, dilateErodeInput, dilateErodeOperation->getInputSocket(0));
+
+	graph->addOperation(dilateErodeOperation);
+
+	return dilateErodeOperation->getOutputSocket(0);
+}
+
+OutputSocket *KeyingNode::setupDispill(ExecutionSystem *graph, OutputSocket *dispillInput, InputSocket *inputScreen, float factor)
+{
+	KeyingDispillOperation *dispillOperation = new KeyingDispillOperation();
+
+	dispillOperation->setDispillFactor(factor);
+
+	addLink(graph, dispillInput, dispillOperation->getInputSocket(0));
+	inputScreen->relinkConnections(dispillOperation->getInputSocket(1), 1, graph);
+
+	graph->addOperation(dispillOperation);
+
+	return dispillOperation->getOutputSocket(0);
+}
+
+void KeyingNode::convertToOperations(ExecutionSystem *graph, CompositorContext *context)
+{
+	InputSocket *inputImage = this->getInputSocket(0);
+	InputSocket *inputScreen = this->getInputSocket(1);
+	OutputSocket *outputImage = this->getOutputSocket(0);
+	OutputSocket *outputMatte = this->getOutputSocket(1);
+	OutputSocket *postprocessedMatte, *postprocessedImage, *originalImage;
+
+	bNode *editorNode = this->getbNode();
+	NodeKeyingData *keying_data = (NodeKeyingData *) editorNode->storage;
+
+	/* keying operation */
+	KeyingOperation *keyingOperation = new KeyingOperation();
+
+	keyingOperation->setClipBlack(keying_data->clip_black);
+	keyingOperation->setClipWhite(keying_data->clip_white);
+
+	inputScreen->relinkConnections(keyingOperation->getInputSocket(1), 1, graph);
+
+	if (keying_data->blur_pre) {
+		/* chroma preblur operation for input of keying operation  */
+		OutputSocket *preBluredImage = setupPreBlur(graph, inputImage, keying_data->blur_pre, &originalImage);
+		addLink(graph, preBluredImage, keyingOperation->getInputSocket(0));
+	}
+	else {
+		inputImage->relinkConnections(keyingOperation->getInputSocket(0), 0, graph);
+		originalImage = keyingOperation->getInputSocket(0)->getConnection()->getFromSocket();
+	}
+
+	graph->addOperation(keyingOperation);
+
+	/* apply blur on matte if needed */
+	if (keying_data->blur_post)
+		postprocessedMatte = setupPostBlur(graph, keyingOperation->getOutputSocket(), keying_data->blur_post);
+	else
+		postprocessedMatte = keyingOperation->getOutputSocket();
+
+	/* matte dilate/erode */
+	if (keying_data->dilate_distance != 0) {
+		postprocessedMatte = setupDilateErode(graph, postprocessedMatte, keying_data->dilate_distance);
+	}
+
+	/* set alpha channel to output image */
+	SetAlphaOperation *alphaOperation = new SetAlphaOperation();
+	addLink(graph, originalImage, alphaOperation->getInputSocket(0));
+	addLink(graph, postprocessedMatte, alphaOperation->getInputSocket(1));
+
+	postprocessedImage = alphaOperation->getOutputSocket();
+
+	/* dispill output image */
+	if (keying_data->dispill_factor > 0.0f) {
+		postprocessedImage = setupDispill(graph, postprocessedImage, inputScreen, keying_data->dispill_factor);
+	}
+
+	/* connect result to output sockets */
+	outputImage->relinkConnections(postprocessedImage);
+	outputMatte->relinkConnections(postprocessedMatte);
+
+	graph->addOperation(alphaOperation);
+}
diff --git a/source/blender/compositor/nodes/COM_KeyingNode.h b/source/blender/compositor/nodes/COM_KeyingNode.h
new file mode 100644
index 00000000000..8c1ee8fdf72
--- /dev/null
+++ b/source/blender/compositor/nodes/COM_KeyingNode.h
@@ -0,0 +1,44 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+#include "COM_Node.h"
+#include "DNA_node_types.h"
+
+/**
+  * @brief KeyingNode
+  * @ingroup Node
+  */
+class KeyingNode : public Node {
+protected:
+	NodeBlurData preBlurData;
+	NodeBlurData postBlurData;
+
+	OutputSocket *setupPreBlur(ExecutionSystem *graph, InputSocket *inputImage, int size, OutputSocket **originalImage);
+	OutputSocket *setupPostBlur(ExecutionSystem *graph, OutputSocket *postBLurInput, int size);
+	OutputSocket *setupDilateErode(ExecutionSystem *graph, OutputSocket *dilateErodeInput, int distance);
+	OutputSocket *setupDispill(ExecutionSystem *graph, OutputSocket *dispillInput, InputSocket *inputSrceen, float factor);
+public:
+	KeyingNode(bNode *editorNode);
+	void convertToOperations(ExecutionSystem *graph, CompositorContext *context);
+
+};
diff --git a/source/blender/compositor/nodes/COM_KeyingScreenNode.cpp b/source/blender/compositor/nodes/COM_KeyingScreenNode.cpp
new file mode 100644
index 00000000000..ad58adae48b
--- /dev/null
+++ b/source/blender/compositor/nodes/COM_KeyingScreenNode.cpp
@@ -0,0 +1,57 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+#include "COM_KeyingScreenNode.h"
+#include "COM_ExecutionSystem.h"
+#include "COM_KeyingScreenOperation.h"
+
+extern "C" {
+	#include "DNA_movieclip_types.h"
+}
+
+KeyingScreenNode::KeyingScreenNode(bNode *editorNode): Node(editorNode)
+{
+}
+
+void KeyingScreenNode::convertToOperations(ExecutionSystem *graph, CompositorContext * context)
+{
+	OutputSocket *outputScreen = this->getOutputSocket(0);
+
+	bNode *editorNode = this->getbNode();
+	MovieClip *clip = (MovieClip *) editorNode->id;
+
+	NodeKeyingScreenData *keyingscreen_data = (NodeKeyingScreenData *) editorNode->storage;
+
+	// always connect the output image
+	KeyingScreenOperation *operation = new KeyingScreenOperation();
+
+	if (outputScreen->isConnected()) {
+		outputScreen->relinkConnections(operation->getOutputSocket());
+	}
+
+	operation->setMovieClip(clip);
+	operation->setTrackingObject(keyingscreen_data->tracking_object);
+	operation->setFramenumber(context->getFramenumber());
+
+	graph->addOperation(operation);
+}
diff --git a/source/blender/compositor/nodes/COM_KeyingScreenNode.h b/source/blender/compositor/nodes/COM_KeyingScreenNode.h
new file mode 100644
index 00000000000..7c87219ef6e
--- /dev/null
+++ b/source/blender/compositor/nodes/COM_KeyingScreenNode.h
@@ -0,0 +1,36 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+#include "COM_Node.h"
+#include "DNA_node_types.h"
+
+/**
+  * @brief KeyingScreenNode
+  * @ingroup Node
+  */
+class KeyingScreenNode : public Node {
+public:
+	KeyingScreenNode(bNode *editorNode);
+	void convertToOperations(ExecutionSystem *graph, CompositorContext *context);
+
+};
diff --git a/source/blender/compositor/operations/COM_KeyingDispillOperation.cpp b/source/blender/compositor/operations/COM_KeyingDispillOperation.cpp
new file mode 100644
index 00000000000..5f4eaf3148d
--- /dev/null
+++ b/source/blender/compositor/operations/COM_KeyingDispillOperation.cpp
@@ -0,0 +1,89 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+#include "COM_KeyingDispillOperation.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+
+static int get_pixel_primary_channel(float *pixel)
+{
+	float max_value = MAX3(pixel[0], pixel[1], pixel[2]);
+
+	if (max_value == pixel[0])
+		return 0;
+	else if (max_value == pixel[1])
+		return 1;
+
+	return 2;
+}
+
+KeyingDispillOperation::KeyingDispillOperation(): NodeOperation()
+{
+	this->addInputSocket(COM_DT_COLOR);
+	this->addInputSocket(COM_DT_COLOR);
+	this->addOutputSocket(COM_DT_COLOR);
+
+	this->dispillFactor = 0.5f;
+
+	this->pixelReader = NULL;
+	this->screenReader = NULL;
+}
+
+void KeyingDispillOperation::initExecution()
+{
+	this->pixelReader = this->getInputSocketReader(0);
+	this->screenReader = this->getInputSocketReader(1);
+}
+
+void KeyingDispillOperation::deinitExecution()
+{
+	this->pixelReader = NULL;
+	this->screenReader = NULL;
+}
+
+void KeyingDispillOperation::executePixel(float *color, float x, float y, PixelSampler sampler, MemoryBuffer *inputBuffers[])
+{
+	float pixelColor[4];
+	float screenColor[4];
+
+	this->pixelReader->read(pixelColor, x, y, sampler, inputBuffers);
+	this->screenReader->read(screenColor, x, y, sampler, inputBuffers);
+
+	int screen_primary_channel = get_pixel_primary_channel(screenColor);
+	float average_value, amount;
+
+	average_value = (pixelColor[0] + pixelColor[1] + pixelColor[2] - pixelColor[screen_primary_channel]) / 2.0f;
+	amount = pixelColor[screen_primary_channel] - average_value;
+
+	color[0] = pixelColor[0];
+	color[1] = pixelColor[1];
+	color[2] = pixelColor[2];
+	color[3] = pixelColor[3];
+	
+	if (this->dispillFactor * amount > 0) {
+		color[screen_primary_channel] = pixelColor[screen_primary_channel] - this->dispillFactor * amount;
+	}
+}
diff --git a/source/blender/compositor/operations/COM_KeyingDispillOperation.h b/source/blender/compositor/operations/COM_KeyingDispillOperation.h
new file mode 100644
index 00000000000..a918a918381
--- /dev/null
+++ b/source/blender/compositor/operations/COM_KeyingDispillOperation.h
@@ -0,0 +1,49 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+#ifndef _COM_KeyingDispillOperation_h
+#define _COM_KeyingDispillOperation_h
+
+#include "COM_NodeOperation.h"
+
+/**
+  * Class with implementation of keying dispill node
+  */
+class KeyingDispillOperation : public NodeOperation {
+protected:
+	SocketReader *pixelReader;
+	SocketReader *screenReader;
+	float dispillFactor;
+
+public:
+	KeyingDispillOperation();
+
+	void initExecution();
+	void deinitExecution();
+
+	void setDispillFactor(float value) {this->dispillFactor = value;}
+
+	void executePixel(float *color, float x, float y, PixelSampler sampler, MemoryBuffer *inputBuffers[]);
+};
+
+#endif
diff --git a/source/blender/compositor/operations/COM_KeyingOperation.cpp b/source/blender/compositor/operations/COM_KeyingOperation.cpp
new file mode 100644
index 00000000000..43348568a5d
--- /dev/null
+++ b/source/blender/compositor/operations/COM_KeyingOperation.cpp
@@ -0,0 +1,114 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+#include "COM_KeyingOperation.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+
+static int get_pixel_primary_channel(float *pixel)
+{
+	float max_value = MAX3(pixel[0], pixel[1], pixel[2]);
+
+	if (max_value == pixel[0])
+		return 0;
+	else if (max_value == pixel[1])
+		return 1;
+
+	return 2;
+}
+
+static float get_pixel_saturation(float *pixel, float screen_balance)
+{
+	float min = MIN3(pixel[0], pixel[1], pixel[2]);
+	float max = MAX3(pixel[0], pixel[1], pixel[2]);
+	float mid = pixel[0] + pixel[1] + pixel[2] - min - max;
+	float val = (1.0f - screen_balance) * min + screen_balance * mid;
+
+	return max - val;
+}
+
+KeyingOperation::KeyingOperation(): NodeOperation()
+{
+	this->addInputSocket(COM_DT_COLOR);
+	this->addInputSocket(COM_DT_COLOR);
+	this->addOutputSocket(COM_DT_VALUE);
+
+	this->screenBalance = 0.5f;
+	this->clipBlack = 0.0f;
+	this->clipWhite = 1.0f;
+
+	this->pixelReader = NULL;
+	this->screenReader = NULL;
+}
+
+void KeyingOperation::initExecution()
+{
+	this->pixelReader = this->getInputSocketReader(0);
+	this->screenReader = this->getInputSocketReader(1);
+}
+
+void KeyingOperation::deinitExecution()
+{
+	this->pixelReader = NULL;
+	this->screenReader = NULL;
+}
+
+void KeyingOperation::executePixel(float *color, float x, float y, PixelSampler sampler, MemoryBuffer *inputBuffers[])
+{
+	float pixelColor[4];
+	float screenColor[4];
+
+	this->pixelReader->read(pixelColor, x, y, sampler, inputBuffers);
+	this->screenReader->read(screenColor, x, y, sampler, inputBuffers);
+
+	float saturation = get_pixel_saturation(pixelColor, this->screenBalance);
+	float screen_saturation = get_pixel_saturation(screenColor, this->screenBalance);
+	int primary_channel = get_pixel_primary_channel(pixelColor);
+	int screen_primary_channel = get_pixel_primary_channel(screenColor);
+
+	if (primary_channel != screen_primary_channel) {
+		/* different main channel means pixel is on foreground */
+		color[0] = 1.0f;
+        }
+        else if (saturation >= screen_saturation) {
+		/* saturation of main channel is more than screen, definitely a background */
+		color[0] = 0.0f;
+	}
+	else {
+		float distance;
+
+		distance = 1.0f - saturation / screen_saturation;
+
+		color[0] = distance;
+
+		if (color[0] < this->clipBlack)
+			color[0] = 0.0f;
+		else if (color[0] >= this->clipWhite)
+			color[0] = 1.0f;
+		else
+			color[0] = (color[0] - this->clipBlack) / (this->clipWhite - this->clipBlack);
+        }
+}
diff --git a/source/blender/compositor/operations/COM_KeyingOperation.h b/source/blender/compositor/operations/COM_KeyingOperation.h
new file mode 100644
index 00000000000..546ff355573
--- /dev/null
+++ b/source/blender/compositor/operations/COM_KeyingOperation.h
@@ -0,0 +1,57 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+
+#ifndef _COM_KeyingOperation_h
+#define _COM_KeyingOperation_h
+
+#include <string.h>
+
+#include "COM_NodeOperation.h"
+
+#include "BLI_listbase.h"
+
+/**
+  * Class with implementation of keying node
+  */
+class KeyingOperation : public NodeOperation {
+protected:
+	SocketReader *pixelReader;
+	SocketReader *screenReader;
+	float screenBalance;
+	float clipBlack;
+	float clipWhite;
+
+public:
+	KeyingOperation();
+
+	void initExecution();
+	void deinitExecution();
+
+	void setClipBlack(float value) {this->clipBlack = value;}
+	void setClipWhite(float value) {this->clipWhite = value;}
+
+	void executePixel(float *color, float x, float y, PixelSampler sampler, MemoryBuffer *inputBuffers[]);
+};
+
+#endif
diff --git a/source/blender/compositor/operations/COM_KeyingScreenOperation.cpp b/source/blender/compositor/operations/COM_KeyingScreenOperation.cpp
new file mode 100644
index 00000000000..456ab31db24
--- /dev/null
+++ b/source/blender/compositor/operations/COM_KeyingScreenOperation.cpp
@@ -0,0 +1,217 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+#include "COM_KeyingScreenOperation.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+#include "BLI_math_color.h"
+
+#include "DNA_scene_types.h"
+
+extern "C" {
+	#include "BKE_movieclip.h"
+	#include "BKE_tracking.h"
+
+	#include "IMB_imbuf.h"
+	#include "IMB_imbuf_types.h"
+}
+
+KeyingScreenOperation::KeyingScreenOperation(): NodeOperation()
+{
+	this->addOutputSocket(COM_DT_COLOR);
+	this->movieClip = NULL;
+	this->framenumber = 0;
+	this->trackingObject[0] = 0;
+	setComplex(true);
+}
+
+void KeyingScreenOperation::initExecution()
+{
+	initMutex();
+	this->cachedTriangulation = NULL;
+}
+
+void KeyingScreenOperation::deinitExecution()
+{
+	if (this->cachedTriangulation) {
+		TriangulationData *triangulation = cachedTriangulation;
+
+		if (triangulation->triangulated_points)
+			MEM_freeN(triangulation->triangulated_points);
+
+		if (triangulation->triangles)
+			MEM_freeN(triangulation->triangles);
+
+		MEM_freeN(this->cachedTriangulation);
+
+		this->cachedTriangulation = NULL;
+	}
+}
+
+KeyingScreenOperation::TriangulationData *KeyingScreenOperation::buildVoronoiTriangulation()
+{
+	MovieClipUser user = {0};
+	TriangulationData *triangulation;
+	MovieTracking *tracking = &movieClip->tracking;
+	MovieTrackingTrack *track;
+	VoronoiSite *sites;
+	ImBuf *ibuf;
+	ListBase *tracksbase;
+	ListBase edges = {NULL, NULL};
+	int sites_total;
+	int i;
+	int width = this->getWidth();
+	int height = this->getHeight();
+
+	if (this->trackingObject[0]) {
+		MovieTrackingObject *object = BKE_tracking_named_object(tracking, this->trackingObject);
+
+		if (!object)
+			return NULL;
+
+		tracksbase = BKE_tracking_object_tracks(tracking, object);
+	}
+	else
+		tracksbase = BKE_tracking_get_tracks(tracking);
+
+	sites_total = BLI_countlist(tracksbase);
+
+	if (!sites_total)
+		return NULL;
+
+	triangulation = (TriangulationData *) MEM_callocN(sizeof(TriangulationData), "keying screen triangulation data");
+
+	BKE_movieclip_user_set_frame(&user, framenumber);
+	ibuf = BKE_movieclip_get_ibuf(movieClip, &user);
+
+	sites = (VoronoiSite *) MEM_callocN(sizeof(VoronoiSite) * sites_total, "keyingscreen voronoi sites");
+	track = (MovieTrackingTrack *) tracksbase->first;
+	i = 0;
+	while (track) {
+		VoronoiSite *site = &sites[i];
+		MovieTrackingMarker *marker = BKE_tracking_get_marker(track, framenumber);
+		ImBuf *pattern_ibuf = BKE_tracking_get_pattern_imbuf(ibuf, track, marker, 0, TRUE, NULL, NULL);
+		int j;
+
+		zero_v3(site->color);
+		for (j = 0; j < pattern_ibuf->x * pattern_ibuf->y; j++) {
+			if (pattern_ibuf->rect_float) {
+				add_v3_v3(site->color, &pattern_ibuf->rect_float[4 * j]);
+			}
+			else {
+				unsigned char *rrgb = (unsigned char *)pattern_ibuf->rect;
+
+				site->color[0] += srgb_to_linearrgb((float)rrgb[4 * j + 0] / 255.0f);
+				site->color[1] += srgb_to_linearrgb((float)rrgb[4 * j + 1] / 255.0f);
+				site->color[2] += srgb_to_linearrgb((float)rrgb[4 * j + 2] / 255.0f);
+			}
+		}
+
+		mul_v3_fl(site->color, 1.0f / (pattern_ibuf->x * pattern_ibuf->y));
+		IMB_freeImBuf(pattern_ibuf);
+
+		site->co[0] = marker->pos[0] * width;
+		site->co[1] = marker->pos[1] * height;
+
+		track = track->next;
+		i++;
+	}
+
+	IMB_freeImBuf(ibuf);
+
+	BLI_voronoi_compute(sites, sites_total, width, height, &edges);
+
+	BLI_voronoi_triangulate(sites, sites_total, &edges, width, height,
+	                        &triangulation->triangulated_points, &triangulation->triangulated_points_total,
+                            &triangulation->triangles, &triangulation->triangles_total);
+
+	MEM_freeN(sites);
+	BLI_freelistN(&edges);
+
+	return triangulation;
+}
+
+void *KeyingScreenOperation::initializeTileData(rcti *rect, MemoryBuffer **memoryBuffers)
+{
+	if (this->movieClip == NULL)
+		return NULL;
+
+	if (this->cachedTriangulation)
+		return this->cachedTriangulation;
+
+	BLI_mutex_lock(getMutex());
+	if (this->cachedTriangulation == NULL) {
+		this->cachedTriangulation = buildVoronoiTriangulation();
+	}
+	BLI_mutex_unlock(getMutex());
+
+	return this->cachedTriangulation;
+}
+
+void KeyingScreenOperation::determineResolution(unsigned int resolution[], unsigned int preferredResolution[])
+{
+	resolution[0] = 0;
+	resolution[1] = 0;
+
+	if (this->movieClip) {
+		MovieClipUser user = {0};
+		int width, height;
+
+		BKE_movieclip_user_set_frame(&user, framenumber);
+		BKE_movieclip_get_size(this->movieClip, &user, &width, &height);
+
+		resolution[0] = width;
+		resolution[1] = height;
+	}
+}
+
+void KeyingScreenOperation::executePixel(float *color, int x, int y, MemoryBuffer *inputBuffers[], void *data)
+{
+	color[0] = 0.0f;
+	color[1] = 0.0f;
+	color[2] = 0.0f;
+	color[3] = 1.0f;
+
+	if (this->movieClip && data) {
+		TriangulationData *triangulation = (TriangulationData *) data;
+		int i;
+		for (i = 0; i < triangulation->triangles_total; i++) {
+			int *triangle = triangulation->triangles[i];
+			VoronoiTriangulationPoint *a = &triangulation->triangulated_points[triangle[0]],
+			                          *b = &triangulation->triangulated_points[triangle[1]],
+			                          *c = &triangulation->triangulated_points[triangle[2]];
+			float co[2] = {(float) x, (float) y}, w[3];
+
+			if (barycentric_coords_v2(a->co, b->co, c->co, co, w)) {
+				if (barycentric_inside_triangle_v2(w)) {
+					color[0] += a->color[0] * w[0] + b->color[0] * w[1] + c->color[0] * w[2];
+					color[1] += a->color[1] * w[0] + b->color[1] * w[1] + c->color[1] * w[2];
+					color[2] += a->color[2] * w[0] + b->color[2] * w[1] + c->color[2] * w[2];
+				}
+			}
+		}
+	}
+}
diff --git a/source/blender/compositor/operations/COM_KeyingScreenOperation.h b/source/blender/compositor/operations/COM_KeyingScreenOperation.h
new file mode 100644
index 00000000000..9d3f44f6be2
--- /dev/null
+++ b/source/blender/compositor/operations/COM_KeyingScreenOperation.h
@@ -0,0 +1,79 @@
+/*
+ * Copyright 2012, Blender Foundation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor:
+ *		Jeroen Bakker
+ *		Monique Dewanchand
+ *		Sergey Sharybin
+ */
+
+
+#ifndef _COM_KeyingScreenOperation_h
+#define _COM_KeyingScreenOperation_h
+
+#include <string.h>
+
+#include "COM_NodeOperation.h"
+
+#include "DNA_scene_types.h"
+#include "DNA_movieclip_types.h"
+
+#include "BLI_listbase.h"
+
+extern "C" {
+	#include "BLI_voronoi.h"
+}
+
+/**
+  * Class with implementation of green screen gradient rasterization
+  */
+class KeyingScreenOperation : public NodeOperation {
+protected:
+	typedef struct TriangulationData {
+		VoronoiTriangulationPoint *triangulated_points;
+		int (*triangles)[3];
+		int triangulated_points_total, triangles_total;
+	} TriangulationData;
+
+	MovieClip *movieClip;
+	int framenumber;
+	TriangulationData *cachedTriangulation;
+	char trackingObject[64];
+
+	/**
+	  * Determine the output resolution. The resolution is retrieved from the Renderer
+	  */
+	void determineResolution(unsigned int resolution[], unsigned int preferredResolution[]);
+
+	TriangulationData *buildVoronoiTriangulation();
+
+ public:
+	KeyingScreenOperation();
+
+	void initExecution();
+	void deinitExecution();
+
+	void *initializeTileData(rcti *rect, MemoryBuffer **memoryBuffers);
+
+	void setMovieClip(MovieClip *clip) {this->movieClip = clip;}
+	void setTrackingObject(char *object) {strncpy(this->trackingObject, object, sizeof(this->trackingObject));}
+	void setFramenumber(int framenumber) {this->framenumber = framenumber;}
+
+	void executePixel(float *color, int x, int y, MemoryBuffer *inputBuffers[], void *data);
+};
+
+#endif