Initial commit of new keying nodes
authorSergey Sharybin <sergey.vfx@gmail.com>
Tue, 29 May 2012 14:00:47 +0000 (14:00 +0000)
committerSergey Sharybin <sergey.vfx@gmail.com>
Tue, 29 May 2012 14:00:47 +0000 (14:00 +0000)
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.

35 files changed:
source/blender/blenkernel/BKE_node.h
source/blender/blenkernel/intern/node.c
source/blender/blenlib/BLI_math_base.h
source/blender/blenlib/BLI_math_color.h
source/blender/blenlib/BLI_math_geom.h
source/blender/blenlib/BLI_voronoi.h [new file with mode: 0644]
source/blender/blenlib/CMakeLists.txt
source/blender/blenlib/intern/math_color.c
source/blender/blenlib/intern/math_geom.c
source/blender/blenlib/intern/voronoi.c [new file with mode: 0644]
source/blender/compositor/CMakeLists.txt
source/blender/compositor/intern/COM_Converter.cpp
source/blender/compositor/nodes/COM_KeyingNode.cpp [new file with mode: 0644]
source/blender/compositor/nodes/COM_KeyingNode.h [new file with mode: 0644]
source/blender/compositor/nodes/COM_KeyingScreenNode.cpp [new file with mode: 0644]
source/blender/compositor/nodes/COM_KeyingScreenNode.h [new file with mode: 0644]
source/blender/compositor/operations/COM_KeyingDispillOperation.cpp [new file with mode: 0644]
source/blender/compositor/operations/COM_KeyingDispillOperation.h [new file with mode: 0644]
source/blender/compositor/operations/COM_KeyingOperation.cpp [new file with mode: 0644]
source/blender/compositor/operations/COM_KeyingOperation.h [new file with mode: 0644]
source/blender/compositor/operations/COM_KeyingScreenOperation.cpp [new file with mode: 0644]
source/blender/compositor/operations/COM_KeyingScreenOperation.h [new file with mode: 0644]
source/blender/editors/space_node/drawnode.c
source/blender/makesdna/DNA_node_types.h
source/blender/makesrna/RNA_access.h
source/blender/makesrna/intern/rna_nodetree.c
source/blender/makesrna/intern/rna_nodetree_types.h
source/blender/nodes/CMakeLists.txt
source/blender/nodes/NOD_composite.h
source/blender/nodes/composite/node_composite_util.c
source/blender/nodes/composite/node_composite_util.h
source/blender/nodes/composite/nodes/node_composite_blur.c
source/blender/nodes/composite/nodes/node_composite_dilate.c
source/blender/nodes/composite/nodes/node_composite_keying.c [new file with mode: 0644]
source/blender/nodes/composite/nodes/node_composite_keyingscreen.c [new file with mode: 0644]

index 7e925e5..fde6d93 100644 (file)
@@ -655,6 +655,8 @@ void                        ntreeGPUMaterialNodes(struct bNodeTree *ntree, struct GPUMaterial *mat);
 #define CMP_NODE_DOUBLEEDGEMASK    266
 #define CMP_NODE_OUTPUT_MULTI_FILE__DEPRECATED 267     /* DEPRECATED multi file node has been merged into regular CMP_NODE_OUTPUT_FILE */
 #define CMP_NODE_MASK          268
+#define CMP_NODE_KEYINGSCREEN          269
+#define CMP_NODE_KEYING                270
 
 #define CMP_NODE_GLARE         301
 #define CMP_NODE_TONEMAP       302
index 54edd70..35e838d 100644 (file)
@@ -1926,6 +1926,8 @@ static void registerCompositNodes(bNodeTreeType *ttype)
        register_node_type_cmp_color_spill(ttype);
        register_node_type_cmp_luma_matte(ttype);
        register_node_type_cmp_doubleedgemask(ttype);
+       register_node_type_cmp_keyingscreen(ttype);
+       register_node_type_cmp_keying(ttype);
 
        register_node_type_cmp_translate(ttype);
        register_node_type_cmp_rotate(ttype);
index 22672db..b0e0d3c 100644 (file)
@@ -53,6 +53,9 @@
 #ifndef M_SQRT1_2
 #define M_SQRT1_2   0.70710678118654752440
 #endif
+#ifndef M_SQRT3
+#define M_SQRT3   1.7320508075688772
+#endif
 #ifndef M_1_PI
 #define M_1_PI      0.318309886183790671538
 #endif
index 746a2b9..44f54c4 100644 (file)
@@ -69,6 +69,8 @@ void rgb_to_hsv(float r, float g, float b, float *lh, float *ls, float *lv);
 void rgb_to_hsv_v(const float rgb[3], float r_hsv[3]);
 void rgb_to_hsv_compat(float r, float g, float b, float *lh, float *ls, float *lv);
 void rgb_to_hsv_compat_v(const float rgb[3], float r_hsv[3]);
+void rgb_to_lab(float r, float g, float b, float *ll, float *la, float *lb);
+void rgb_to_xyz(float r, float g, float b, float *x, float *y, float *z);
 unsigned int rgb_to_cpack(float r, float g, float b);
 unsigned int hsv_to_cpack(float h, float s, float v);
 
@@ -112,6 +114,8 @@ void rgba_uchar_to_float(float col_r[4], const unsigned char col_ub[4]);
 void rgb_float_to_uchar(unsigned char col_r[3], const float col_f[3]);
 void rgba_float_to_uchar(unsigned char col_r[4], const float col_f[4]);
 
+void xyz_to_lab(float x, float y, float z, float *l, float *a, float *b);
+
 /***************** lift/gamma/gain / ASC-CDL conversion *****************/
 
 void lift_gamma_gain_to_asc_cdl(float *lift, float *gamma, float *gain, float *offset, float *slope, float *power);
index 0560a3f..93599de 100644 (file)
@@ -191,6 +191,9 @@ void barycentric_transform(float pt_tar[3], float const pt_src[3],
 void barycentric_weights_v2(const float v1[2], const float v2[2], const float v3[2],
                             const float co[2], float w[3]);
 
+int barycentric_coords_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3]);
+int barycentric_inside_triangle_v2(const float w[3]);
+
 void resolve_tri_uv(float r_uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2]);
 void resolve_quad_uv(float uv[2], const float st[2], const float st0[2], const float st1[2], const float st2[2], const float st3[2]);
 
diff --git a/source/blender/blenlib/BLI_voronoi.h b/source/blender/blenlib/BLI_voronoi.h
new file mode 100644 (file)
index 0000000..a67b01c
--- /dev/null
@@ -0,0 +1,70 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * 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.
+ *
+ * The Original Code is Copyright (C) 2012 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Sergey Sharybin
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BLI_VORONOI_H__
+#define __BLI_VORONOI_H__
+
+struct ListBase;
+
+/** \file BLI_voronoi.h
+ *  \ingroup bli
+ */
+
+typedef struct VoronoiSite {
+       float co[2];
+       float color[3];
+} VoronoiSite;
+
+typedef struct VoronoiEdge {
+       struct VoronoiEdge *next, *prev;
+
+       float start[2], end[2]; /* start and end points */
+
+       /* this fields are used during diagram computation only */
+
+       float direction[2];             /* directional vector, from "start", points to "end", normal of |left, right| */
+
+       float left[2];                  /* point on Voronoi place on the left side of edge */
+       float right[2];                 /* point on Voronoi place on the right side of edge */
+
+       float f, g;                             /* directional coeffitients satisfying equation y = f*x + g (edge lies on this line) */
+
+       /* some edges consist of two parts, so we add the pointer to another part to connect them at the end of an algorithm */
+       struct VoronoiEdge *neighbour;
+} VoronoiEdge;
+
+typedef struct VoronoiTriangulationPoint {
+       float co[2];
+       float color[3];
+       int power;
+} VoronoiTriangulationPoint;
+
+void BLI_voronoi_compute(const VoronoiSite *sites, int sites_total, int width, int height, struct ListBase *edges);
+
+void BLI_voronoi_triangulate(const VoronoiSite *sites, int sites_total, struct ListBase *edges, int width, int height,
+                             VoronoiTriangulationPoint **triangulated_points_r, int *triangulated_points_total_r,
+                             int (**triangles_r)[3], int *triangles_total_r);
+
+#endif /* __BLI_VORONOI_H__ */
index d535e19..ac7681e 100644 (file)
@@ -89,6 +89,7 @@ set(SRC
        intern/time.c
        intern/uvproject.c
        intern/voxel.c
+       intern/voronoi.c
        intern/winstuff.c
 
        BLI_args.h
index 152fc98..9433cfd 100644 (file)
@@ -264,6 +264,35 @@ void rgb_to_hsv_v(const float rgb[3], float r_hsv[3])
        rgb_to_hsv(rgb[0], rgb[1], rgb[2], &r_hsv[0], &r_hsv[1], &r_hsv[2]);
 }
 
+void rgb_to_hsl(float r, float g, float b, float *lh, float *ls, float *ll)
+{
+       float cmax = MAX3(r, g, b);
+       float cmin = MIN3(r, g, b);
+       float h, s, l = (cmax + cmin) / 2.0f;
+
+       if (cmax == cmin) {
+               h = s = 0.0f; // achromatic
+       }
+       else {
+               float d = cmax - cmin;
+               s = l > 0.5f ? d / (2.0f - cmax - cmin) : d / (cmax + cmin);
+               if (cmax == r) {
+                       h = (g - b) / d + (g < b ? 6.0f : 0.0f);
+               }
+               else if (cmax == g) {
+                       h = (b - r) / d + 2.0f;
+               }
+               else {
+                       h = (r - g) / d + 4.0f;
+               }
+        }
+        h /= 6.0f;
+
+       *lh = h;
+       *ls = s;
+       *ll = l;
+}
+
 void rgb_to_hsv_compat(float r, float g, float b, float *lh, float *ls, float *lv)
 {
        float orig_h = *lh;
@@ -603,3 +632,58 @@ void BLI_init_srgb_conversion(void)
                BLI_color_to_srgb_table[i] = b * 0x100;
        }
 }
+static float inverse_srgb_companding(float v)
+{
+    if (v > 0.04045f) {
+        return powf((v + 0.055f) / 1.055f, 2.4);
+    }
+    else {
+        return v / 12.92f;
+    }
+}
+
+void rgb_to_xyz(float r, float g, float b, float *x, float *y, float *z)
+{
+    r = inverse_srgb_companding(r) * 100.0f;
+    g = inverse_srgb_companding(g) * 100.0f;
+    b = inverse_srgb_companding(b) * 100.0f;
+
+    *x = r * 0.4124 + g * 0.3576 + b * 0.1805;
+    *y = r * 0.2126 + g * 0.7152 + b * 0.0722;
+    *z = r * 0.0193 + g * 0.1192 + b * 0.9505;
+}
+
+static float xyz_to_lab_component(float v)
+{
+       const float eps = 0.008856f;
+       const float k = 903.3f;
+
+       if (v > eps) {
+               return pow(v, 1.0f / 3.0f);
+       }
+       else {
+               return (k * v + 16.0f) / 116.0f;
+       }
+}
+
+void xyz_to_lab(float x, float y, float z, float *l, float *a, float *b)
+{
+       float xr = x / 95.047f;
+       float yr = y / 100.0f;
+       float zr = z / 108.883f;
+
+       float fx = xyz_to_lab_component(xr);
+       float fy = xyz_to_lab_component(yr);
+       float fz = xyz_to_lab_component(zr);
+
+       *l = 116.0f * fy - 16.0f;
+       *a = 500.0f * (fx - fy);
+       *b = 200.0f * (fy - fz);
+}
+
+void rgb_to_lab(float r, float g, float b, float *ll, float *la, float *lb)
+{
+       float x, y, z;
+       rgb_to_xyz(r, g, b, &x, &y, &z);
+       xyz_to_lab(x, y, z, ll, la, lb);
+}
index 3962f53..d35624e 100644 (file)
@@ -1825,6 +1825,45 @@ void interp_weights_face_v3(float w[4], const float v1[3], const float v2[3], co
        }
 }
 
+/* return 1 of point is inside triangle, 2 if it's on the edge, 0 if point is outside of triangle */
+int barycentric_inside_triangle_v2(const float w[3])
+{
+       if (IN_RANGE(w[0], 0.0f, 1.0f) &&
+           IN_RANGE(w[1], 0.0f, 1.0f) &&
+           IN_RANGE(w[2], 0.0f, 1.0f))
+       {
+               return 1;
+       }
+       else if (IN_RANGE_INCL(w[0], 0.0f, 1.0f) &&
+                IN_RANGE_INCL(w[1], 0.0f, 1.0f) &&
+                IN_RANGE_INCL(w[2], 0.0f, 1.0f))
+       {
+               return 2;
+       }
+
+       return 0;
+}
+
+/* returns 0 for degenerated triangles */
+int barycentric_coords_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
+{
+       float x = co[0], y = co[1];
+       float x1 = v1[0], y1 = v1[1];
+       float x2 = v2[0], y2 = v2[1];
+       float x3 = v3[0], y3 = v3[1];
+       float det = (y2 - y3) * (x1 - x3) + (x3 - x2) * (y1 - y3);
+
+       if (fabsf(det) > FLT_EPSILON) {
+               w[0] = ((y2 - y3) * (x - x3) + (x3 - x2) * (y - y3)) / det;
+               w[1] = ((y3 - y1) * (x - x3) + (x1 - x3) * (y - y3)) / det;
+               w[2] = 1.0f - w[0] - w[1];
+
+       return 1;
+       }
+
+       return 0;
+}
+
 /* used by projection painting
  * note: using area_tri_signed_v2 means locations outside the triangle are correctly weighted */
 void barycentric_weights_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
diff --git a/source/blender/blenlib/intern/voronoi.c b/source/blender/blenlib/intern/voronoi.c
new file mode 100644 (file)
index 0000000..0088d24
--- /dev/null
@@ -0,0 +1,833 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * 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.
+ *
+ * The Original Code is Copyright (C) 2012 Blender Foundation.
+ * All rights reserved.
+ *
+ * Contributor(s): Sergey Sharybin
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/*
+ * Fortune's algorithm implemented using explanation and some code snippets from
+ * http://blog.ivank.net/fortunes-algorithm-and-implementation.html
+ */
+
+/** \file blender/blenkernel/intern/tracking.c
+ *  \ingroup bli
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+#include "BLI_voronoi.h"
+#include "BLI_utildefines.h"
+
+#define VORONOI_EPS 1e-3
+
+enum {
+       voronoiEventType_Site = 0,
+       voronoiEventType_Circle = 1
+} voronoiEventType;
+
+typedef struct VoronoiEvent {
+       struct VoronoiEvent *next, *prev;
+
+       int type;               /* type of event (site or circle) */
+       float site[2];  /* site for which event was generated */
+
+       struct VoronoiParabola *parabola;       /* parabola for which event was generated */
+} VoronoiEvent;
+
+typedef struct VoronoiParabola {
+       struct VoronoiParabola *left, *right, *parent;
+       VoronoiEvent *event;
+       int is_leaf;
+       float site[2];
+       VoronoiEdge *edge;
+} VoronoiParabola;
+
+typedef struct VoronoiProcess {
+       ListBase queue, edges;
+       VoronoiParabola *root;
+       int width, height;
+       float current_y;
+} VoronoiProcess;
+
+/* event */
+
+static void voronoi_insertEvent(VoronoiProcess *process, VoronoiEvent *event)
+{
+       VoronoiEvent *current_event = process->queue.first;
+
+       while (current_event) {
+               if (current_event->site[1] < event->site[1]) {
+                       break;
+               }
+               if (current_event->site[1] == event->site[1]) {
+                       event->site[1] -= VORONOI_EPS;
+               }
+
+               current_event = current_event->next;
+       }
+
+       BLI_insertlinkbefore(&process->queue, current_event, event);
+}
+
+/* edge */
+static VoronoiEdge *voronoiEdge_new(float start[2], float left[2], float right[2])
+{
+       VoronoiEdge *edge = MEM_callocN(sizeof(VoronoiEdge), "voronoi edge");
+
+       copy_v2_v2(edge->start, start);
+       copy_v2_v2(edge->left, left);
+       copy_v2_v2(edge->right, right);
+
+       edge->neighbour = NULL;
+       edge->end[0] = 0;
+       edge->end[1] = 0;
+
+       edge->f = (right[0] - left[0]) / (left[1] - right[1]);
+       edge->g = start[1] - edge->f * start[0];
+
+       edge->direction[0] = right[1] - left[1];
+       edge->direction[1] = -(right[0] - left[0]);
+
+       return edge;
+}
+
+/* parabola */
+
+static VoronoiParabola *voronoiParabola_new(void)
+{
+       VoronoiParabola *parabola = MEM_callocN(sizeof(VoronoiParabola), "voronoi parabola");
+
+       parabola->is_leaf = FALSE;
+       parabola->event = NULL;
+       parabola->edge = NULL;
+       parabola->parent = 0;
+
+       return parabola;
+}
+
+static VoronoiParabola *voronoiParabola_newSite(float site[2])
+{
+       VoronoiParabola *parabola = MEM_callocN(sizeof(VoronoiParabola), "voronoi parabola site");
+
+       copy_v2_v2(parabola->site, site);
+       parabola->is_leaf = TRUE;
+       parabola->event = NULL;
+       parabola->edge = NULL;
+       parabola->parent = 0;
+
+       return parabola;
+}
+
+/* returns the closest leave which is on the left of current node */
+static VoronoiParabola *voronoiParabola_getLeftChild(VoronoiParabola *parabola)
+{
+       VoronoiParabola *current_parabola;
+
+       if (!parabola)
+               return NULL;
+
+       current_parabola = parabola->left;
+       while (!current_parabola->is_leaf) {
+               current_parabola = current_parabola->right;
+       }
+
+       return current_parabola;
+}
+
+/* returns the closest leave which is on the right of current node */
+static VoronoiParabola *voronoiParabola_getRightChild(VoronoiParabola *parabola)
+{
+       VoronoiParabola *current_parabola;
+
+       if (!parabola)
+               return NULL;
+
+       current_parabola = parabola->right;
+       while (!current_parabola->is_leaf) {
+               current_parabola = current_parabola->left;
+       }
+
+       return current_parabola;
+}
+
+/* returns the closest parent which is on the left */
+static VoronoiParabola *voronoiParabola_getLeftParent(VoronoiParabola *parabola)
+{
+       VoronoiParabola *current_par = parabola->parent;
+       VoronoiParabola *last_parabola = parabola;
+
+       while (current_par->left == last_parabola) {
+               if (!current_par->parent)
+                       return NULL;
+
+               last_parabola = current_par;
+               current_par = current_par->parent;
+       }
+
+       return current_par;
+}
+
+/* returns the closest parent which is on the right */
+static VoronoiParabola *voronoiParabola_getRightParent(VoronoiParabola *parabola)
+{
+       VoronoiParabola *current_parabola = parabola->parent;
+       VoronoiParabola *last_parabola = parabola;
+
+       while (current_parabola->right == last_parabola) {
+               if (!current_parabola->parent)
+                       return NULL;
+
+               last_parabola = current_parabola;
+               current_parabola = current_parabola->parent;
+       }
+
+       return current_parabola;
+}
+
+static void voronoiParabola_setLeft(VoronoiParabola *parabola, VoronoiParabola *left)
+{
+       parabola->left = left;
+       left->parent = parabola;
+}
+
+static void voronoiParabola_setRight(VoronoiParabola *parabola, VoronoiParabola *right)
+{
+       parabola->right = right;
+       right->parent = parabola;
+}
+
+static float voronoi_getY(VoronoiProcess *process, float p[2], float x)
+{
+       float ly = process->current_y;
+
+       float dp = 2 * (p[1] - ly);
+       float a1 = 1 / dp;
+       float b1 = -2 * p[0] / dp;
+       float c1 = ly + dp / 4 + p[0] * p[0] / dp;
+
+       return a1 * x * x + b1 * x + c1;
+}
+
+static float voronoi_getXOfEdge(VoronoiProcess *process, VoronoiParabola *par, float y)
+{
+       VoronoiParabola *left = voronoiParabola_getLeftChild(par);
+       VoronoiParabola *right = voronoiParabola_getRightChild(par);
+       float p[2], r[2];
+       float dp, a1, b1, c1, a2, b2, c2, a, b, c, disc, ry, x1, x2;
+       float ly = process->current_y;
+
+       copy_v2_v2(p, left->site);
+       copy_v2_v2(r, right->site);
+
+       dp = 2.0f * (p[1] - y);
+       a1 = 1.0f / dp;
+       b1 = -2.0f * p[0] / dp;
+       c1 = y + dp / 4 + p[0] * p[0] / dp;
+
+       dp = 2.0f * (r[1] - y);
+       a2 = 1.0f / dp;
+       b2 = -2.0f * r[0] / dp;
+       c2 = ly + dp / 4 + r[0] * r[0] / dp;
+
+       a = a1 - a2;
+       b = b1 - b2;
+       c = c1 - c2;
+
+       disc = b*b - 4 * a * c;
+       x1 = (-b + sqrtf(disc)) / (2*a);
+       x2 = (-b - sqrtf(disc)) / (2*a);
+
+       if (p[1] < r[1])
+               ry = MAX2(x1, x2);
+       else
+               ry = MIN2(x1, x2);
+
+       return ry;
+}
+
+static VoronoiParabola *voronoi_getParabolaByX(VoronoiProcess *process, float xx)
+{
+       VoronoiParabola * par = process->root;
+       float x = 0.0f;
+       float ly = process->current_y;
+
+       while (!par->is_leaf) {
+               x = voronoi_getXOfEdge(process, par, ly);
+
+               if (x > xx)
+                       par = par->left;
+               else
+                       par = par->right;
+       }
+
+       return par;
+}
+
+static int voronoi_getEdgeIntersection(VoronoiEdge *a, VoronoiEdge *b, float p[2])
+{
+       float x = (b->g - a->g) / (a->f - b->f);
+       float y = a->f * x + a->g;
+
+       if ((x - a->start[0]) / a->direction[0] < 0)
+               return 0;
+
+       if ((y - a->start[1]) / a->direction[1] < 0)
+               return 0;
+
+       if ((x - b->start[0]) / b->direction[0] < 0)
+               return 0;
+
+       if ((y - b->start[1]) / b->direction[1] < 0)
+               return 0;
+
+       p[0] = x;
+       p[1] = y;
+
+       return 1;
+}
+
+static void voronoi_checkCircle(VoronoiProcess *process, VoronoiParabola *b)
+{
+       VoronoiParabola *lp = voronoiParabola_getLeftParent(b);
+       VoronoiParabola *rp = voronoiParabola_getRightParent(b);
+
+       VoronoiParabola *a  = voronoiParabola_getLeftChild(lp);
+       VoronoiParabola *c  = voronoiParabola_getRightChild(rp);
+
+       VoronoiEvent *event;
+
+       float ly = process->current_y;
+       float s[2], dx, dy, d;
+
+       if (!a || !c || len_squared_v2v2(a->site, c->site) < VORONOI_EPS)
+               return;
+
+       if (!voronoi_getEdgeIntersection(lp->edge, rp->edge, s))
+               return;
+
+       dx = a->site[0] - s[0];
+       dy = a->site[1] - s[1];
+
+       d = sqrtf((dx * dx) + (dy * dy));
+
+       if (s[1] - d >= ly)
+               return;
+
+       event = MEM_callocN(sizeof(VoronoiEvent), "voronoi circle event");
+
+       event->type = voronoiEventType_Circle;
+
+       event->site[0] = s[0];
+       event->site[1] = s[1] - d;
+
+       b->event = event;
+       event->parabola = b;
+
+       voronoi_insertEvent(process, event);
+}
+
+static void voronoi_addParabola(VoronoiProcess *process, float site[2])
+{
+       VoronoiParabola *root = process->root;
+       VoronoiParabola *par, *p0, *p1, *p2;
+       VoronoiEdge *el, *er;
+       float start[2];
+
+       if (!process->root) {
+               process->root = voronoiParabola_newSite(site);
+
+               return;
+       }
+
+       if (root->is_leaf && root->site[1] - site[1] < 0) {
+               float *fp = root->site;
+               float s[2];
+
+               root->is_leaf = FALSE;
+               voronoiParabola_setLeft(root, voronoiParabola_newSite(fp));
+               voronoiParabola_setRight(root, voronoiParabola_newSite(site));
+
+               s[0] = (site[0] + fp[0]) / 2.0f;
+               s[1] = process->height;
+
+               if(site[0] > fp[0])
+                       root->edge = voronoiEdge_new(s, fp, site);
+               else
+                       root->edge = voronoiEdge_new(s, site, fp);
+
+               BLI_addtail(&process->edges, root->edge);
+
+               return;
+       }
+
+       par = voronoi_getParabolaByX(process, site[0]);
+
+       if (par->event) {
+               BLI_freelinkN(&process->queue, par->event);
+
+               par->event = NULL;
+       }
+
+       start[0] = site[0];
+       start[1] = voronoi_getY(process, par->site, site[0]);
+
+       el = voronoiEdge_new(start, par->site, site);
+       er = voronoiEdge_new(start, site, par->site);
+
+       el->neighbour = er;
+       BLI_addtail(&process->edges, el);
+
+       par->edge = er;
+       par->is_leaf = FALSE;
+
+       p0 = voronoiParabola_newSite(par->site);
+       p1 = voronoiParabola_newSite(site);
+       p2 = voronoiParabola_newSite(par->site);
+
+       voronoiParabola_setRight(par, p2);
+       voronoiParabola_setLeft(par, voronoiParabola_new());
+       par->left->edge = el;
+
+       voronoiParabola_setLeft(par->left, p0);
+       voronoiParabola_setRight(par->left, p1);
+
+       voronoi_checkCircle(process, p0);
+       voronoi_checkCircle(process, p2);
+}
+
+static void voronoi_removeParabola(VoronoiProcess *process, VoronoiEvent *event)
+{
+       VoronoiParabola *p1 = event->parabola;
+
+       VoronoiParabola *xl = voronoiParabola_getLeftParent(p1);
+       VoronoiParabola *xr = voronoiParabola_getRightParent(p1);
+
+       VoronoiParabola *p0 = voronoiParabola_getLeftChild(xl);
+       VoronoiParabola *p2 = voronoiParabola_getRightChild(xr);
+
+       VoronoiParabola *higher = NULL, *par, *gparent;
+
+       float p[2];
+
+       if (p0->event) {
+               BLI_freelinkN(&process->queue, p0->event);
+               p0->event = NULL;
+       }
+
+       if (p2->event) {
+               BLI_freelinkN(&process->queue, p2->event);
+               p2->event = NULL;
+       }
+
+       p[0] = event->site[0];
+       p[1] = voronoi_getY(process, p1->site, event->site[0]);
+
+       copy_v2_v2(xl->edge->end, p);
+       copy_v2_v2(xr->edge->end, p);
+
+       par = p1;
+       while (par != process->root) {
+               par = par->parent;
+
+               if (par == xl)
+                       higher = xl;
+               if (par == xr)
+                       higher = xr;
+       }
+
+       higher->edge = voronoiEdge_new(p, p0->site, p2->site);
+       BLI_addtail(&process->edges, higher->edge);
+
+       gparent = p1->parent->parent;
+       if (p1->parent->left == p1) {
+               if (gparent->left == p1->parent)
+                       voronoiParabola_setLeft(gparent, p1->parent->right);
+               if (gparent->right == p1->parent)
+                       voronoiParabola_setRight(gparent, p1->parent->right);
+       }
+       else {
+               if (gparent->left == p1->parent)
+                       voronoiParabola_setLeft(gparent, p1->parent->left);
+               if (gparent->right == p1->parent)
+                       voronoiParabola_setRight(gparent, p1->parent->left);
+       }
+
+       MEM_freeN(p1->parent);
+       MEM_freeN(p1);
+
+       voronoi_checkCircle(process, p0);
+       voronoi_checkCircle(process, p2);
+}
+
+void voronoi_finishEdge(VoronoiProcess *process, VoronoiParabola *parabola)
+{
+       float mx;
+
+       if (parabola->is_leaf) {
+               MEM_freeN(parabola);
+               return;
+       }
+
+       if (parabola->edge->direction[0] > 0.0f)
+               mx = MAX2(process->width, parabola->edge->start[0] + 10);
+       else
+               mx = MIN2(0.0, parabola->edge->start[0] - 10);
+
+       parabola->edge->end[0] = mx;
+       parabola->edge->end[1] = mx * parabola->edge->f + parabola->edge->g;
+
+       voronoi_finishEdge(process, parabola->left);
+       voronoi_finishEdge(process, parabola->right);
+
+       MEM_freeN(parabola);
+}
+
+void voronoi_clampEdgeVertex(int width, int height, float *coord, float *other_coord)
+{
+       const float corners[4][2] = {{0.0f, 0.0f},
+                                    {width - 1, 0.0f},
+                                    {width - 1, height - 1},
+                                    {0.0f, height - 1}};
+       int i;
+
+       if (IN_RANGE_INCL(coord[0], 0, width-1) && IN_RANGE_INCL(coord[1], 0, height-1)) {
+               return;
+       }
+
+       for (i = 0; i < 4; i++) {
+               float v1[2], v2[2];
+               float p[2];
+
+               copy_v2_v2(v1, corners[i]);
+
+               if (i == 3)
+                       copy_v2_v2(v2, corners[0]);
+               else
+                       copy_v2_v2(v2, corners[i + 1]);
+
+               if (isect_seg_seg_v2_point(v1, v2, coord, other_coord, p) == 1) {
+                       if (i == 0 && coord[1] > p[1])
+                               continue;
+                       if (i == 1 && coord[0] < p[0])
+                               continue;
+                       if (i == 2 && coord[1] < p[1])
+                               continue;
+                       if (i == 3 && coord[0] > p[0])
+                               continue;
+
+                       copy_v2_v2(coord, p);
+               }
+       }
+}
+
+void voronoi_clampEdges(ListBase *edges, int width, int height, ListBase *clamped_edges)
+{
+       VoronoiEdge *edge;
+
+       edge = edges->first;
+       while (edge) {
+               VoronoiEdge *new_edge = MEM_callocN(sizeof(VoronoiEdge), "clamped edge");
+
+               *new_edge = *edge;
+               BLI_addtail(clamped_edges, new_edge);
+
+               voronoi_clampEdgeVertex(width, height, new_edge->start, new_edge->end);
+               voronoi_clampEdgeVertex(width, height, new_edge->end, new_edge->start);
+
+               edge = edge->next;
+       }
+}
+
+static int voronoi_getNextSideCoord(ListBase *edges, float coord[2], int dim, int dir, float next_coord[2])
+{
+       VoronoiEdge *edge = edges->first;
+       float distance = FLT_MAX;
+       int other_dim = dim ? 0 : 1;
+
+       while (edge) {
+               int ok = FALSE;
+               float co[2], cur_distance;
+
+               if (fabsf(edge->start[other_dim] - coord[other_dim]) < VORONOI_EPS &&
+                   len_squared_v2v2(coord, edge->start) > VORONOI_EPS)
+               {
+                       copy_v2_v2(co, edge->start);
+                       ok = TRUE;
+               }
+
+               if (fabsf(edge->end[other_dim] - coord[other_dim]) < VORONOI_EPS &&
+                   len_squared_v2v2(coord, edge->end) > VORONOI_EPS)
+               {
+                       copy_v2_v2(co, edge->end);
+                       ok = TRUE;
+               }
+
+               if (ok) {
+                       if (dir > 0 && coord[dim] > co[dim]) {
+                               ok = FALSE;
+                       }
+                       else if (dir < 0 && coord[dim] < co[dim]) {
+                               ok = FALSE;
+                       }
+               }
+
+               if (ok) {
+                       cur_distance = len_squared_v2v2(coord, co);
+                       if (cur_distance < distance) {
+                               copy_v2_v2(next_coord, co);
+                               distance = cur_distance;
+                       }
+               }
+
+               edge = edge->next;
+       }
+
+       return distance < FLT_MAX;
+}
+
+static void voronoi_createBoundaryEdges(ListBase *edges, int width, int height)
+{
+       const float corners[4][2] = {{width - 1, 0.0f},
+                                    {width - 1, height - 1},
+                                    {0.0f, height - 1},
+                                    {0.0f, 0.0f}};
+       int i, dim = 0, dir = 1;
+
+       float coord[2] = {0.0f, 0.0f};
+       float next_coord[2] = {0.0f, 0.0f};
+
+       for (i = 0; i < 4; i++) {
+               while (voronoi_getNextSideCoord(edges, coord, dim, dir, next_coord)) {
+                       VoronoiEdge *edge = MEM_callocN(sizeof(VoronoiEdge), "boundary edge");
+
+                       copy_v2_v2(edge->start, coord);
+                       copy_v2_v2(edge->end, next_coord);
+                       BLI_addtail(edges, edge);
+
+                       copy_v2_v2(coord, next_coord);
+               }
+
+               if (len_squared_v2v2(coord, corners[i]) > VORONOI_EPS) {
+                       VoronoiEdge *edge = MEM_callocN(sizeof(VoronoiEdge), "boundary edge");
+
+                       copy_v2_v2(edge->start, coord);
+                       copy_v2_v2(edge->end, corners[i]);
+                       BLI_addtail(edges, edge);
+                       copy_v2_v2(coord, corners[i]);
+               }
+
+               dim = dim ? 0 : 1;
+               if (i == 1)
+                       dir = -1;
+       }
+}
+
+void BLI_voronoi_compute(const VoronoiSite *sites, int sites_total, int width, int height, ListBase *edges)
+{
+       VoronoiProcess process;
+       VoronoiEdge *edge;
+       int i;
+
+       memset(&process, 0, sizeof(VoronoiProcess));
+
+       process.width = width;
+       process.height = height;
+
+       for (i = 0; i < sites_total; i++) {
+               VoronoiEvent *event = MEM_callocN(sizeof(VoronoiEvent), "voronoi site event");
+
+               event->type = voronoiEventType_Site;
+               copy_v2_v2(event->site, sites[i].co);
+
+               voronoi_insertEvent(&process, event);
+       }
+
+       while (process.queue.first) {
+               VoronoiEvent *event = process.queue.first;
+
+               process.current_y = event->site[1];
+
+               if (event->type == voronoiEventType_Site) {
+                       voronoi_addParabola(&process, event->site);
+               }
+               else {
+                       voronoi_removeParabola(&process, event);
+               }
+
+               BLI_freelinkN(&process.queue, event);
+       }
+
+       voronoi_finishEdge(&process, process.root);
+
+       edge = process.edges.first;
+       while (edge) {
+               if (edge->neighbour) {
+                       copy_v2_v2(edge->start, edge->neighbour->end);
+                       MEM_freeN(edge->neighbour);
+               }
+
+               edge = edge->next;
+       }
+
+       BLI_movelisttolist(edges, &process.edges);
+}
+
+static int testVoronoiEdge(const float site[2], const float point[2], const VoronoiEdge *edge)
+{
+       float p[2];
+
+       if (isect_seg_seg_v2_point(site, point, edge->start, edge->end, p) == 1) {
+               if (len_squared_v2v2(p, edge->start) > VORONOI_EPS &&
+                   len_squared_v2v2(p, edge->end) > VORONOI_EPS)
+               {
+                       return FALSE;
+               }
+       }
+
+       return TRUE;
+}
+
+static int voronoi_addTriangulationPoint(const float coord[2], const float color[3],
+                                         VoronoiTriangulationPoint **triangulated_points,
+                                         int *triangulated_points_total)
+{
+       VoronoiTriangulationPoint *triangulation_point;
+       int i;
+
+       for (i = 0; i < *triangulated_points_total; i++) {
+               if (equals_v2v2(coord, (*triangulated_points)[i].co)) {
+                       triangulation_point = &(*triangulated_points)[i];
+
+                       add_v3_v3(triangulation_point->color, color);
+                       triangulation_point->power++;
+
+                       return i;
+               }
+       }
+
+       if (*triangulated_points) {
+               *triangulated_points = MEM_reallocN(*triangulated_points,
+                                                   sizeof(VoronoiTriangulationPoint) * (*triangulated_points_total + 1));
+       }
+       else {
+               *triangulated_points = MEM_callocN(sizeof(VoronoiTriangulationPoint), "triangulation points");
+       }
+
+       triangulation_point = &(*triangulated_points)[(*triangulated_points_total)];
+       copy_v2_v2(triangulation_point->co, coord);
+       copy_v3_v3(triangulation_point->color, color);
+
+       triangulation_point->power = 1;
+
+       (*triangulated_points_total)++;
+
+       return (*triangulated_points_total) - 1;
+}
+
+static void voronoi_addTriangle(int v1, int v2, int v3, int (**triangles)[3], int *triangles_total)
+{
+       int *triangle;
+
+       if (*triangles) {
+               *triangles = MEM_reallocN(*triangles, sizeof(int[3]) * (*triangles_total + 1));
+       }
+       else {
+               *triangles = MEM_callocN(sizeof(int[3]), "trianglulation triangles");
+       }
+
+       triangle = (int*)&(*triangles)[(*triangles_total)];
+
+       triangle[0] = v1;
+       triangle[1] = v2;
+       triangle[2] = v3;
+
+       (*triangles_total)++;
+}
+
+void BLI_voronoi_triangulate(const VoronoiSite *sites, int sites_total, ListBase *edges, int width, int height,
+                             VoronoiTriangulationPoint **triangulated_points_r, int *triangulated_points_total_r,
+                             int (**triangles_r)[3], int *triangles_total_r)
+{
+       VoronoiTriangulationPoint *triangulated_points = NULL;
+       int (*triangles)[3] = NULL;
+       int triangulated_points_total = 0, triangles_total = 0;
+       int i;
+       ListBase boundary_edges = {NULL, NULL};
+
+       voronoi_clampEdges(edges, width, height, &boundary_edges);
+       voronoi_createBoundaryEdges(&boundary_edges, width, height);
+
+       for (i = 0; i < sites_total; i++) {
+               VoronoiEdge *edge;
+               int v1;
+
+               v1 = voronoi_addTriangulationPoint(sites[i].co, sites[i].color, &triangulated_points, &triangulated_points_total);
+
+               edge = boundary_edges.first;
+               while (edge) {
+                       VoronoiEdge *test_edge = boundary_edges.first;
+                       int ok_start = TRUE, ok_end = TRUE;
+
+                       while (test_edge) {
+                               float v1[2], v2[2];
+
+                               sub_v2_v2v2(v1, edge->start, sites[i].co);
+                               sub_v2_v2v2(v2, edge->end, sites[i].co);
+
+                               if (ok_start && !testVoronoiEdge(sites[i].co, edge->start, test_edge))
+                                       ok_start = FALSE;
+
+                               if (ok_end && !testVoronoiEdge(sites[i].co, edge->end, test_edge))
+                                       ok_end = FALSE;
+
+                               test_edge = test_edge->next;
+                       }
+
+                       if (ok_start && ok_end) {
+                               int v2, v3;
+
+                               v2 = voronoi_addTriangulationPoint(edge->start, sites[i].color, &triangulated_points, &triangulated_points_total);
+                               v3 = voronoi_addTriangulationPoint(edge->end, sites[i].color, &triangulated_points, &triangulated_points_total);
+
+                               voronoi_addTriangle(v1, v2, v3, &triangles, &triangles_total);
+                       }
+
+                       edge = edge->next;
+               }
+       }
+
+       for (i = 0; i < triangulated_points_total; i++) {
+               VoronoiTriangulationPoint *triangulation_point = &triangulated_points[i];
+
+               mul_v3_fl(triangulation_point->color, 1.0f / triangulation_point->power);
+       }
+
+       *triangulated_points_r = triangulated_points;
+       *triangulated_points_total_r = triangulated_points_total;
+
+       *triangles_r = triangles;
+       *triangles_total_r = triangles_total;
+
+       BLI_freelistN(&boundary_edges);
+}
index 5e778d4..d4e083f 100644 (file)
@@ -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
index dc6409e..747d649 100644 (file)
 #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 (file)
index 0000000..7250603
--- /dev/null
@@ -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 (file)
index 0000000..8c1ee8f
--- /dev/null
@@ -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 (file)
index 0000000..ad58ada
--- /dev/null
@@ -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 (file)
index 0000000..7c87219
--- /dev/null
@@ -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 (file)
index 0000000..5f4eaf3
--- /dev/null
@@ -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 (file)
index 0000000..a918a91
--- /dev/null
@@ -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 (file)
index 0000000..4334856
--- /dev/null
@@ -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 (file)
index 0000000..546ff35
--- /dev/null
@@ -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 (file)
index 0000000..456ab31
--- /dev/null
@@ -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 (file)
index 0000000..9d3f44f
--- /dev/null
@@ -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
index 3c070b4..341926f 100644 (file)
@@ -2394,6 +2394,36 @@ static void node_composit_buts_mask(uiLayout *layout, bContext *C, PointerRNA *p
        uiTemplateID(layout, C, ptr, "mask", NULL, NULL, NULL);
 }
 
+static void node_composit_buts_keyingscreen(uiLayout *layout, bContext *C, PointerRNA *ptr)
+{
+       bNode *node= ptr->data;
+
+       uiTemplateID(layout, C, ptr, "clip", NULL, NULL, NULL);
+
+       if (node->id) {
+               MovieClip *clip = (MovieClip *) node->id;
+               uiLayout *col;
+               PointerRNA tracking_ptr;
+
+               RNA_pointer_create(&clip->id, &RNA_MovieTracking, &clip->tracking, &tracking_ptr);
+
+               col = uiLayoutColumn(layout, 1);
+               uiItemPointerR(col, ptr, "tracking_object", &tracking_ptr, "objects", "", ICON_OBJECT_DATA);
+       }
+}
+
+static void node_composit_buts_keying(uiLayout *layout, bContext *UNUSED(C), PointerRNA *ptr)
+{
+       bNode *node= ptr->data;
+
+       uiItemR(layout, ptr, "blur_pre", 0, NULL, ICON_NONE);
+       uiItemR(layout, ptr, "dispill_factor", 0, NULL, ICON_NONE);
+       uiItemR(layout, ptr, "clip_black", 0, NULL, ICON_NONE);
+       uiItemR(layout, ptr, "clip_white", 0, NULL, ICON_NONE);
+       uiItemR(layout, ptr, "dilate_distance", 0, NULL, ICON_NONE);
+       uiItemR(layout, ptr, "blur_post", 0, NULL, ICON_NONE);
+}
+
 /* only once called */
 static void node_composit_set_butfunc(bNodeType *ntype)
 {
@@ -2586,7 +2616,12 @@ static void node_composit_set_butfunc(bNodeType *ntype)
                case CMP_NODE_MASK:
                        ntype->uifunc= node_composit_buts_mask;
                        break;
-
+               case CMP_NODE_KEYINGSCREEN:
+                       ntype->uifunc = node_composit_buts_keyingscreen;
+                       break;
+               case CMP_NODE_KEYING:
+                       ntype->uifunc = node_composit_buts_keying;
+                       break;
                default:
                        ntype->uifunc = NULL;
        }
index b278167..bad40e8 100644 (file)
@@ -617,6 +617,17 @@ typedef struct TexNodeOutput {
        char name[64];
 } TexNodeOutput;
 
+typedef struct NodeKeyingScreenData {
+       char tracking_object[64];
+} NodeKeyingScreenData;
+
+typedef struct NodeKeyingData {
+       float dispill_factor;
+       float clip_black, clip_white;
+       int dilate_distance;
+       int blur_pre, blur_post;
+} NodeKeyingData;
+
 /* frame node flags */
 #define NODE_FRAME_SHRINK              1       /* keep the bounding box minimal */
 #define NODE_FRAME_RESIZEABLE  2       /* test flag, if frame can be resized by user */
index 0a0efb6..842ad41 100644 (file)
@@ -341,6 +341,7 @@ extern StructRNA RNA_MotionPathVert;
 extern StructRNA RNA_MouseSensor;
 extern StructRNA RNA_MovieSequence;
 extern StructRNA RNA_MovieClipSequence;
+extern StructRNA RNA_MovieTracking;
 extern StructRNA RNA_MovieTrackingTrack;
 extern StructRNA RNA_MovieTrackingObject;
 extern StructRNA RNA_MovieTrackingTrack;
index 59c4af4..7d2935e 100644 (file)
@@ -3046,6 +3046,67 @@ static void def_cmp_mask(StructRNA *srna)
        RNA_def_property_struct_type(prop, "Mask");
        RNA_def_property_flag(prop, PROP_EDITABLE);
        RNA_def_property_ui_text(prop, "Mask", "");
+}
+
+static void def_cmp_keyingscreen(StructRNA *srna)
+{
+       PropertyRNA *prop;
+
+       prop = RNA_def_property(srna, "clip", PROP_POINTER, PROP_NONE);
+       RNA_def_property_pointer_sdna(prop, NULL, "id");
+       RNA_def_property_struct_type(prop, "MovieClip");
+       RNA_def_property_flag(prop, PROP_EDITABLE);
+       RNA_def_property_ui_text(prop, "Movie Clip", "");
+       RNA_def_property_update(prop, NC_NODE|NA_EDITED, "rna_Node_update");
+
+       RNA_def_struct_sdna_from(srna, "NodeKeyingScreenData", "storage");
+
+       prop = RNA_def_property(srna, "tracking_object", PROP_STRING, PROP_NONE);
+       RNA_def_property_string_sdna(prop, NULL, "tracking_object");
+       RNA_def_property_ui_text(prop, "Tracking Object", "");
+       RNA_def_property_update(prop, NC_NODE|NA_EDITED, "rna_Node_update");
+}
+
+static void def_cmp_keying(StructRNA *srna)
+{
+       PropertyRNA *prop;
+
+       RNA_def_struct_sdna_from(srna, "NodeKeyingData", "storage");
+
+       prop = RNA_def_property(srna, "dispill_factor", PROP_FLOAT, PROP_NONE);
+       RNA_def_property_float_sdna(prop, NULL, "dispill_factor");
+       RNA_def_property_range(prop, 0.0f, 1.0f);
+       RNA_def_property_ui_text(prop, "Dispill", "");
+       RNA_def_property_update(prop, NC_NODE|NA_EDITED, "rna_Node_update");
+
+       prop = RNA_def_property(srna, "clip_black", PROP_FLOAT, PROP_FACTOR);
+       RNA_def_property_float_sdna(prop, NULL, "clip_black");
+       RNA_def_property_range(prop, 0.0f, 1.0f);
+       RNA_def_property_ui_text(prop, "Clip Black", "");
+       RNA_def_property_update(prop, NC_NODE|NA_EDITED, "rna_Node_update");
+
+       prop = RNA_def_property(srna, "clip_white", PROP_FLOAT, PROP_FACTOR);
+       RNA_def_property_float_sdna(prop, NULL, "clip_white");
+       RNA_def_property_range(prop, 0.0f, 1.0f);
+       RNA_def_property_ui_text(prop, "Clip White", "");
+       RNA_def_property_update(prop, NC_NODE|NA_EDITED, "rna_Node_update");
+
+       prop = RNA_def_property(srna, "blur_pre", PROP_INT, PROP_NONE);
+       RNA_def_property_int_sdna(prop, NULL, "blur_pre");
+       RNA_def_property_range(prop, 0, 2048);
+       RNA_def_property_ui_text(prop, "Pre Blur", "");
+       RNA_def_property_update(prop, NC_NODE|NA_EDITED, "rna_Node_update");
+
+       prop = RNA_def_property(srna, "blur_post", PROP_INT, PROP_NONE);
+       RNA_def_property_int_sdna(prop, NULL, "blur_post");
+       RNA_def_property_range(prop, 0, 2048);
+       RNA_def_property_ui_text(prop, "Post Blur", "");
+       RNA_def_property_update(prop, NC_NODE|NA_EDITED, "rna_Node_update");
+
+       prop = RNA_def_property(srna, "dilate_distance", PROP_INT, PROP_NONE);
+       RNA_def_property_int_sdna(prop, NULL, "dilate_distance");
+       RNA_def_property_range(prop, -100, 100);
+       RNA_def_property_ui_text(prop, "Dilate/Erode", "");
        RNA_def_property_update(prop, NC_NODE|NA_EDITED, "rna_Node_update");
 }
 
index d5b33f0..d8c27a3 100644 (file)
@@ -166,6 +166,8 @@ DefNode( CompositorNode, CMP_NODE_BOKEHIMAGE,     def_cmp_bokehimage,     "BOKEH
 DefNode( CompositorNode, CMP_NODE_SWITCH,         def_cmp_switch,         "SWITCH"         ,Switch,           "Switch",            ""              )
 DefNode( CompositorNode, CMP_NODE_COLORCORRECTION,def_cmp_colorcorrection,"COLORCORRECTION",ColorCorrection,  "ColorCorrection",   ""              )
 DefNode( CompositorNode, CMP_NODE_MASK,           def_cmp_mask,           "MASK",           Mask,             "Mask",              ""              )
+DefNode( CompositorNode, CMP_NODE_KEYINGSCREEN,   def_cmp_keyingscreen,   "KEYINGSCREEN",   KeyingScreen,     "KeyingScreen",      ""              )
+DefNode( CompositorNode, CMP_NODE_KEYING,         def_cmp_keying,         "KEYING",         Keying,           "Keying",            ""              )
                                                                                                                                                    
 DefNode( TextureNode,    TEX_NODE_OUTPUT,         def_tex_output,         "OUTPUT",         Output,           "Output",            ""              )
 DefNode( TextureNode,    TEX_NODE_CHECKER,        0,                      "CHECKER",        Checker,          "Checker",           ""              )
index 5e36f90..d07d00a 100644 (file)
@@ -76,6 +76,8 @@ set(SRC
        composite/nodes/node_composite_idMask.c
        composite/nodes/node_composite_image.c
        composite/nodes/node_composite_invert.c
+       composite/nodes/node_composite_keying.c
+       composite/nodes/node_composite_keyingscreen.c
        composite/nodes/node_composite_lensdist.c
        composite/nodes/node_composite_levels.c
        composite/nodes/node_composite_lummaMatte.c
index f850ea9..efa107a 100644 (file)
@@ -81,6 +81,7 @@ void register_node_type_cmp_bilateralblur(struct bNodeTreeType *ttype);
 void register_node_type_cmp_vecblur(struct bNodeTreeType *ttype);
 void register_node_type_cmp_dilateerode(struct bNodeTreeType *ttype);
 void register_node_type_cmp_defocus(struct bNodeTreeType *ttype);
+void register_node_type_cmp_denoise(struct bNodeTreeType *ttype);
 
 void register_node_type_cmp_valtorgb(struct bNodeTreeType *ttype);
 void register_node_type_cmp_rgbtobw(struct bNodeTreeType *ttype);
@@ -105,6 +106,8 @@ void register_node_type_cmp_channel_matte(struct bNodeTreeType *ttype);
 void register_node_type_cmp_color_spill(struct bNodeTreeType *ttype);
 void register_node_type_cmp_luma_matte(struct bNodeTreeType *ttype); 
 void register_node_type_cmp_doubleedgemask(struct bNodeTreeType *ttype);
+void register_node_type_cmp_keyingscreen(struct bNodeTreeType *ttype);
+void register_node_type_cmp_keying(struct bNodeTreeType *ttype);
 
 void register_node_type_cmp_translate(struct bNodeTreeType *ttype);
 void register_node_type_cmp_rotate(struct bNodeTreeType *ttype);
index 3806cf4..ff223ac 100644 (file)
@@ -568,6 +568,22 @@ CompBuf *valbuf_from_rgbabuf(CompBuf *cbuf, int channel)
        return valbuf;
 }
 
+void valbuf_to_rgbabuf(CompBuf *valbuf, CompBuf *cbuf, int channel)
+{
+       float *valf, *rectf;
+       int tot;
+
+       valf= valbuf->rect;
+
+       /* defaults to returning alpha channel */
+       if ((channel < CHAN_R) || (channel > CHAN_A)) channel = CHAN_A;
+
+       rectf = cbuf->rect + channel;
+
+       for (tot= cbuf->x*cbuf->y; tot>0; tot--, valf++, rectf+=4)
+               *rectf = *valf;
+}
+
 static CompBuf *generate_procedural_preview(CompBuf *cbuf, int newx, int newy)
 {
        CompBuf *outbuf;
index 51f047b..18dac5d 100644 (file)
@@ -155,6 +155,7 @@ void composit4_pixel_processor(bNode *node, CompBuf *out, CompBuf *src1_buf, flo
                                                                          int src1_type, int fac1_type, int src2_type, int fac2_type);
 
 CompBuf *valbuf_from_rgbabuf(CompBuf *cbuf, int channel);
+void valbuf_to_rgbabuf(CompBuf *valbuf, CompBuf *cbuf, int channel);
 void generate_preview(void *data, bNode *node, CompBuf *stackbuf);
 
 void do_copy_rgba(bNode *node, float *out, float *in);
@@ -220,6 +221,9 @@ void IIR_gauss(CompBuf* src, float sigma, int chan, int xy);
 #define CMP_SCALE_MAX  12000
 
 CompBuf* node_composit_transform(CompBuf *cbuf, float x, float y, float angle, float scale, int filter_type);
+void node_composit_blur_single_image(bNode *node, int filtertype, int sizex, int sizey, CompBuf *new, CompBuf *img, float scale);
+void node_composite_morpho_dilate(CompBuf *cbuf);
+void node_composite_morpho_erode(CompBuf *cbuf);
 float *node_composit_get_float_buffer(RenderData *rd, ImBuf *ibuf, int *alloc);
 
 #endif
index d19ea3f..9afdd6e 100644 (file)
@@ -85,9 +85,8 @@ static float *make_bloomtab(int rad)
 }
 
 /* both input images of same type, either 4 or 1 channel */
-static void blur_single_image(bNode *node, CompBuf *new, CompBuf *img, float scale)
+void node_composit_blur_single_image(bNode *node, int filtertype, int sizex, int sizey, CompBuf *new, CompBuf *img, float scale)
 {
-       NodeBlurData *nbd= node->storage;
        CompBuf *work;
        register float sum, val;
        float rval, gval, bval, aval;
@@ -101,17 +100,17 @@ static void blur_single_image(bNode *node, CompBuf *new, CompBuf *img, float sca
        work= alloc_compbuf(imgx, imgy, img->type, 1); /* allocs */
 
        /* horizontal */
-       if (nbd->sizex == 0) {
+       if (sizex == 0) {
                memcpy(work->rect, img->rect, sizeof(float) * img->type * imgx * imgy);
        }
        else {
-               rad = scale*(float)nbd->sizex;
+               rad = scale*(float)sizex;
                if (rad>imgx/2)
                        rad= imgx/2;
                else if (rad<1)
                        rad= 1;
                
-               gausstab= make_gausstab(nbd->filtertype, rad);
+               gausstab= make_gausstab(filtertype, rad);
                gausstabcent= gausstab+rad;
                
                for (y = 0; y < imgy; y++) {
@@ -152,17 +151,17 @@ static void blur_single_image(bNode *node, CompBuf *new, CompBuf *img, float sca
                MEM_freeN(gausstab);
        }
        
-       if (nbd->sizey == 0) {
+       if (sizey == 0) {
                memcpy(new->rect, work->rect, sizeof(float) * img->type * imgx * imgy);
        }
        else {
-               rad = scale*(float)nbd->sizey;
+               rad = scale*(float)sizey;
                if (rad>imgy/2)
                        rad= imgy/2;
                else if (rad<1)
                        rad= 1;
        
-               gausstab= make_gausstab(nbd->filtertype, rad);
+               gausstab= make_gausstab(filtertype, rad);
                gausstabcent= gausstab+rad;
                
                bigstep = pix*imgx;
@@ -207,6 +206,13 @@ static void blur_single_image(bNode *node, CompBuf *new, CompBuf *img, float sca
        free_compbuf(work);
 }
 
+static void blur_single_image(bNode *node, CompBuf *new, CompBuf *img, float scale)
+{
+       NodeBlurData *nbd = node->storage;
+
+       node_composit_blur_single_image(node, nbd->filtertype, nbd->sizex, nbd->sizey, new, img, scale);
+}
+
 /* reference has to be mapped 0-1, and equal in size */
 static void bloom_with_reference(CompBuf *new, CompBuf *img, CompBuf *UNUSED(ref), float UNUSED(fac), NodeBlurData *nbd)
 {
index ee857dd..1dc56fd 100644 (file)
@@ -44,7 +44,7 @@ static bNodeSocketTemplate cmp_node_dilateerode_out[]= {
        {       -1, 0, ""       }
 };
 
-static void morpho_dilate(CompBuf *cbuf)
+void node_composite_morpho_dilate(CompBuf *cbuf)
 {
        int x, y;
        float *p, *rectf = cbuf->rect;
@@ -78,7 +78,7 @@ static void morpho_dilate(CompBuf *cbuf)
        }
 }
 
-static void morpho_erode(CompBuf *cbuf)
+void node_composite_morpho_erode(CompBuf *cbuf)
 {
        int x, y;
        float *p, *rectf = cbuf->rect;
@@ -133,11 +133,11 @@ static void node_composit_exec_dilateerode(void *UNUSED(data), bNode *node, bNod
                
                if (node->custom2 > 0) { // positive, dilate
                        for (i = 0; i < node->custom2; i++)
-                               morpho_dilate(stackbuf);
+                               node_composite_morpho_dilate(stackbuf);
                }
                else if (node->custom2 < 0) { // negative, erode
                        for (i = 0; i > node->custom2; i--)
-                               morpho_erode(stackbuf);
+                               node_composite_morpho_erode(stackbuf);
                }
                
                if (cbuf!=in[0]->data)
diff --git a/source/blender/nodes/composite/nodes/node_composite_keying.c b/source/blender/nodes/composite/nodes/node_composite_keying.c
new file mode 100644 (file)
index 0000000..8e6fd86
--- /dev/null
@@ -0,0 +1,218 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * 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.
+ *
+ * The Original Code is Copyright (C) 2011 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Blender Foundation,
+ *                 Sergey Sharybin
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/nodes/composite/nodes/node_composite_keying.c
+ *  \ingroup cmpnodes
+ */
+
+#include "BLF_translation.h"
+
+#include "DNA_movieclip_types.h"
+
+#include "BKE_movieclip.h"
+
+#include "BLI_listbase.h"
+#include "BLI_math_base.h"
+#include "BLI_math_color.h"
+#include "BLI_voronoi.h"
+
+#include "node_composite_util.h"
+
+/* **************** Translate  ******************** */
+
+static bNodeSocketTemplate cmp_node_keying_in[] = {
+       {       SOCK_RGBA, 1, "Image",                  0.8f, 0.8f, 0.8f, 1.0f, 0.0f, 1.0f},
+       {       SOCK_RGBA, 1, "Key Color", 1.0f, 1.0f, 1.0f, 1.0f},
+       {       -1, 0, ""       }
+};
+
+static bNodeSocketTemplate cmp_node_keying_out[] = {
+       {       SOCK_RGBA,  0, "Image"},
+       {       SOCK_FLOAT, 0, "Matte"},
+       {       -1, 0, ""       }
+};
+
+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;
+}
+
+static void despil_pixel(float *out, float *pixel, float *screen, float screen_gain)
+{
+       int screen_primary_channel = get_pixel_primary_channel(screen);
+       float average_value, amount;
+
+       average_value = (pixel[0] + pixel[1] + pixel[2] - pixel[screen_primary_channel]) / 2.0f;
+       amount = pixel[screen_primary_channel] - average_value;
+
+       if (screen_gain * amount > 0) {
+               out[screen_primary_channel] = pixel[screen_primary_channel] - screen_gain * amount;
+       }
+}
+
+static void do_key(bNode *node, float *out, float *pixel, float *screen)
+{
+       NodeKeyingData *data = node->storage;
+
+       float screen_balance = 0.5f;
+       float dispill_factor = data->dispill_factor;
+       float clip_black = data->clip_black;
+       float clip_white = data->clip_white;
+
+       float saturation = get_pixel_saturation(pixel, screen_balance);
+       float screen_saturation = get_pixel_saturation(screen, screen_balance);
+       int primary_channel = get_pixel_primary_channel(pixel);
+       int screen_primary_channel = get_pixel_primary_channel(screen);
+
+       if (primary_channel != screen_primary_channel) {
+               /* different main channel means pixel is on foreground,
+                * but screen color still need to be despilled from it */
+               despil_pixel(out, pixel, screen, dispill_factor);
+               out[3] = 1.0f;
+       }
+       else if (saturation >= screen_saturation) {
+               /* saturation of main channel is more than screen, definitely a background */
+               out[0] = 0.0f;
+               out[1] = 0.0f;
+               out[2] = 0.0f;
+               out[3] = 0.0f;
+       }
+       else {
+               float distance;
+
+               despil_pixel(out, pixel, screen, dispill_factor);
+
+               distance = 1.0f - saturation / screen_saturation;
+
+               out[3] = distance;
+
+               if (out[3] < clip_black)
+                       out[3] = 0.0f;
+               else if (out[3] >= clip_white)
+                       out[3] = 1.0f;
+               else
+                       out[3] = (out[3] - clip_black) / (clip_white - clip_black);
+       }
+}
+
+static void exec(void *data, bNode *node, bNodeStack **in, bNodeStack **out)
+{
+       if (in[0]->data) {
+               NodeKeyingData *keying_data = node->storage;
+               CompBuf *cbuf = typecheck_compbuf(in[0]->data, CB_RGBA);
+               CompBuf *keybuf, *mattebuf;
+
+               keybuf = dupalloc_compbuf(cbuf);
+
+               /* single color is used for screen detection */
+               composit2_pixel_processor(node, keybuf, cbuf, in[0]->vec, in[1]->data, in[1]->vec, do_key, CB_RGBA, CB_VAL);
+
+               /* create a matte from alpha channel */
+               mattebuf = valbuf_from_rgbabuf(keybuf, CHAN_A);
+
+               /* apply dilate/erode if needed */
+               if (keying_data->dilate_distance != 0) {
+                       int i;
+
+                       if (keying_data->dilate_distance > 0) {
+                               for (i = 0; i < keying_data->dilate_distance; i++)
+                                       node_composite_morpho_dilate(mattebuf);
+                       }
+                       else {
+                               for (i = 0; i < -keying_data->dilate_distance; i++)
+                                       node_composite_morpho_erode(mattebuf);
+                       }
+               }
+
+               if (keying_data->blur_post > 0.0f) {
+                       /* post-blur of matte */
+                       CompBuf *newmatte = alloc_compbuf(mattebuf->x, mattebuf->y, mattebuf->type, TRUE);
+                       int size = keying_data->blur_post;
+
+                       node_composit_blur_single_image(node, R_FILTER_BOX, size, size, newmatte, mattebuf, 1.0f);
+
+                       free_compbuf(mattebuf);
+                       mattebuf = newmatte;
+
+                       /* apply blurred matte on output buffer alpha */
+                       valbuf_to_rgbabuf(mattebuf, keybuf, CHAN_A);
+               }
+
+               out[0]->data = keybuf;
+               out[1]->data = mattebuf;
+
+               generate_preview(data, node, keybuf);
+
+               if (cbuf!=in[0]->data)
+                       free_compbuf(cbuf);
+       }
+}
+
+static void node_composit_init_keying(bNodeTree *UNUSED(ntree), bNode* node, bNodeTemplate *UNUSED(ntemp))
+{
+       NodeKeyingData *data;
+
+       data = MEM_callocN(sizeof(NodeKeyingData), "node keying data");
+
+       data->dispill_factor = 1.0f;
+       data->clip_black = 0.0f;
+       data->clip_white = 1.0f;
+
+       node->storage = data;
+}
+
+void register_node_type_cmp_keying(bNodeTreeType *ttype)
+{
+       static bNodeType ntype;
+
+       node_type_base(ttype, &ntype, CMP_NODE_KEYING, "Keying", NODE_CLASS_MATTE, NODE_OPTIONS);
+       node_type_socket_templates(&ntype, cmp_node_keying_in, cmp_node_keying_out);
+       node_type_size(&ntype, 140, 100, 320);
+       node_type_init(&ntype, node_composit_init_keying);
+       node_type_storage(&ntype, "NodeKeyingData", node_free_standard_storage, node_copy_standard_storage);
+       node_type_exec(&ntype, exec);
+
+       nodeRegisterType(ttype, &ntype);
+}
diff --git a/source/blender/nodes/composite/nodes/node_composite_keyingscreen.c b/source/blender/nodes/composite/nodes/node_composite_keyingscreen.c
new file mode 100644 (file)
index 0000000..5cbaf4a
--- /dev/null
@@ -0,0 +1,202 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * 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.
+ *
+ * The Original Code is Copyright (C) 2011 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Blender Foundation,
+ *                 Sergey Sharybin
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/nodes/composite/nodes/node_composite_keyingscreen.c
+ *  \ingroup cmpnodes
+ */
+
+#include "BLF_translation.h"
+
+#include "DNA_movieclip_types.h"
+
+#include "BKE_movieclip.h"
+
+#include "BLI_listbase.h"
+#include "BLI_math_base.h"
+#include "BLI_math_color.h"
+#include "BLI_voronoi.h"
+
+#include "node_composite_util.h"
+
+/* **************** Translate  ******************** */
+
+static bNodeSocketTemplate cmp_node_keyingscreen_out[] = {
+       {       SOCK_RGBA,  0, "Screen"},
+       {       -1, 0, ""       }
+};
+
+
+static void compute_gradient_screen(RenderData *rd, NodeKeyingScreenData *keyingscreen_data, MovieClip *clip, CompBuf *screenbuf)
+{
+       MovieClipUser user = {0};
+       MovieTracking *tracking = &clip->tracking;
+       MovieTrackingTrack *track;
+       VoronoiTriangulationPoint *triangulated_points;
+       VoronoiSite *sites;
+       ImBuf *ibuf;
+       ListBase *tracksbase;
+       ListBase edges = {NULL, NULL};
+       int sites_total, triangulated_points_total, triangles_total;
+       int (*triangles)[3];
+       int i, x, y;
+       float *rect = screenbuf->rect;
+
+       if (keyingscreen_data->tracking_object[0]) {
+               MovieTrackingObject *object = BKE_tracking_named_object(tracking, keyingscreen_data->tracking_object);
+
+               if (!object)
+                       return;
+
+               tracksbase = BKE_tracking_object_tracks(tracking, object);
+       }
+       else
+               tracksbase = BKE_tracking_get_tracks(tracking);
+
+       sites_total = BLI_countlist(tracksbase);
+
+       if (!sites_total)
+               return;
+
+       BKE_movieclip_user_set_frame(&user, rd->cfra);
+       ibuf = BKE_movieclip_get_ibuf(clip, &user);
+
+       sites = MEM_callocN(sizeof(VoronoiSite) * sites_total, "keyingscreen voronoi sites");
+       track = tracksbase->first;
+       i = 0;
+       while (track) {
+               VoronoiSite *site = &sites[i];
+               MovieTrackingMarker *marker = BKE_tracking_get_marker(track, rd->cfra);
+               ImBuf *pattern_ibuf = BKE_tracking_get_pattern_imbuf(ibuf, track, marker, 0, FALSE, 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] * screenbuf->x;
+               site->co[1] = marker->pos[1] * screenbuf->y;
+
+               track = track->next;
+               i++;
+       }
+
+       IMB_freeImBuf(ibuf);
+
+       BLI_voronoi_compute(sites, sites_total, screenbuf->x, screenbuf->y, &edges);
+
+       BLI_voronoi_triangulate(sites, sites_total, &edges, screenbuf->x, screenbuf->y,
+                               &triangulated_points, &triangulated_points_total,
+                            &triangles, &triangles_total);
+
+       for (y = 0; y < screenbuf->y; y++) {
+               for (x = 0; x < screenbuf->x; x++) {
+                       int index = 4 * (y * screenbuf->x + x);
+
+                       rect[index + 0] = rect[index + 1] = rect[index + 2] = 0.0f;
+                       rect[index + 3] = 1.0f;
+
+                       for (i = 0; i < triangles_total; i++) {
+                               int *triangle = triangles[i];
+                               VoronoiTriangulationPoint *a = &triangulated_points[triangle[0]],
+                                                         *b = &triangulated_points[triangle[1]],
+                                                         *c = &triangulated_points[triangle[2]];
+                               float co[2] = {x, y}, w[3];
+
+                               if (barycentric_coords_v2(a->co, b->co, c->co, co, w)) {
+                                       if (barycentric_inside_triangle_v2(w)) {
+                                               rect[index + 0] += a->color[0] * w[0] + b->color[0] * w[1] + c->color[0] * w[2];
+                                               rect[index + 1] += a->color[1] * w[0] + b->color[1] * w[1] + c->color[1] * w[2];
+                                               rect[index + 2] += a->color[2] * w[0] + b->color[2] * w[1] + c->color[2] * w[2];
+                                       }
+                               }
+                       }
+               }
+       }
+
+       MEM_freeN(triangulated_points);
+       MEM_freeN(triangles);
+       MEM_freeN(sites);
+       BLI_freelistN(&edges);
+}
+
+static void exec(void *data, bNode *node, bNodeStack **UNUSED(in), bNodeStack **out)
+{
+       NodeKeyingScreenData *keyingscreen_data = node->storage;
+       RenderData *rd = data;
+       CompBuf *screenbuf = NULL;
+
+       if (node->id) {
+               MovieClip *clip = (MovieClip *) node->id;
+               MovieClipUser user = {0};
+               int width, height;
+
+               BKE_movieclip_user_set_frame(&user, rd->cfra);
+               BKE_movieclip_get_size(clip, &user, &width, &height);
+
+               screenbuf = alloc_compbuf(width, height, CB_RGBA, TRUE);
+               compute_gradient_screen(rd, keyingscreen_data, clip, screenbuf);
+       }
+
+       out[0]->data = screenbuf;
+}
+
+static void node_composit_init_keyingscreen(bNodeTree *UNUSED(ntree), bNode* node, bNodeTemplate *UNUSED(ntemp))
+{
+       NodeKeyingScreenData *data;
+
+       data = MEM_callocN(sizeof(NodeKeyingScreenData), "node keyingscreen data");
+
+       node->storage = data;
+}
+
+void register_node_type_cmp_keyingscreen(bNodeTreeType *ttype)
+{
+       static bNodeType ntype;
+
+       node_type_base(ttype, &ntype, CMP_NODE_KEYINGSCREEN, "Keying Screen", NODE_CLASS_MATTE, NODE_OPTIONS);
+       node_type_socket_templates(&ntype, NULL, cmp_node_keyingscreen_out);
+       node_type_size(&ntype, 140, 100, 320);
+       node_type_init(&ntype, node_composit_init_keyingscreen);
+       node_type_storage(&ntype, "NodeKeyingScreenData", node_free_standard_storage, node_copy_standard_storage);
+       node_type_exec(&ntype, exec);
+
+       nodeRegisterType(ttype, &ntype);
+}