2 * rotoscoping.c -- keyframable vector based rotoscoping
3 * Copyright (C) 2011 Till Theato <root@ttill.de>
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software Foundation,
17 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 #include <framework/mlt_filter.h>
21 #include <framework/mlt_frame.h>
30 #define MAX( x, y ) ( ( x ) > ( y ) ? ( x ) : ( y ) )
31 #define MIN( x, y ) ( ( x ) < ( y ) ? ( x ) : ( y ) )
32 #define SQR( x ) ( x ) * ( x )
34 /** x, y tuple with double precision */
41 typedef struct BPointF
48 enum MODES { MODE_RGB, MODE_ALPHA, MODE_LUMA };
49 const char *MODESTR[3] = { "rgb", "alpha", "luma" };
51 enum ALPHAOPERATIONS { ALPHA_CLEAR, ALPHA_MAX, ALPHA_MIN, ALPHA_ADD, ALPHA_SUB };
52 const char *ALPHAOPERATIONSTR[5] = { "clear", "max", "min", "add", "sub" };
55 /** Returns the index of \param string in \param stringList.
56 * Useful for assigning string parameters to enums. */
57 static int stringValue( const char *string, const char **stringList, int max )
60 for ( i = 0; i < max; i++ )
61 if ( strcmp( stringList[i], string ) == 0 )
66 /** Sets "spline_is_dirty" to 1 if property "spline" was changed.
67 * We then know when to parse the json stored in "spline" */
68 static void rotoPropertyChanged( mlt_service owner, mlt_filter this, char *name )
70 if ( !strcmp( name, "spline" ) )
71 mlt_properties_set_int( MLT_FILTER_PROPERTIES( this ), "_spline_is_dirty", 1 );
75 static inline void lerp( const PointF *a, const PointF *b, PointF *result, double t )
77 result->x = a->x + ( b->x - a->x ) * t;
78 result->y = a->y + ( b->y - a->y ) * t;
81 /** Linear interp. with t = 0.5
83 static inline void lerpHalf( const PointF *a, const PointF *b, PointF *result )
85 result->x = ( a->x + b->x ) * .5;
86 result->y = ( a->y + b->y ) * .5;
89 /** Helper for using qsort with an array of integers. */
90 int ncompare( const void *a, const void *b )
92 return *(const int*)a - *(const int*)b;
95 /** Turns a json array with two children into a point (x, y tuple). */
96 static void jsonGetPoint( cJSON *json, PointF *point )
98 if ( cJSON_GetArraySize( json ) == 2 )
100 point->x = json->child->valuedouble;
101 point->y = json->child->next->valuedouble;
106 * Turns the array of json elements into an array of Bézier points.
107 * \param array cJSON array. values have to be Bézier points: handle 1, point , handl2
108 * ( [ [ [h1x, h1y], [px, py], [h2x, h2y] ], ... ] )
109 * \param points pointer to array of points. Will be allocated and filled with the points in \param array
110 * \return number of points
112 static int json2BCurves( cJSON *array, BPointF **points )
114 int count = cJSON_GetArraySize( array );
115 cJSON *child = array->child;
116 *points = mlt_pool_alloc( count * sizeof( BPointF ) );
121 if ( child && cJSON_GetArraySize( child ) == 3 )
123 jsonGetPoint( child->child , &(*points)[i].h1 );
124 jsonGetPoint( child->child->next, &(*points)[i].p );
125 jsonGetPoint( child->child->next->next, &(*points)[i].h2 );
128 } while ( child && ( child = child->next ) );
131 *points = mlt_pool_realloc( *points, i * sizeof( BPointF ) );
136 /** Blurs \param src horizontally. \See funtion blur. */
137 static void blurHorizontal( uint8_t *src, uint8_t *dst, int width, int height, int radius)
139 int x, y, kx, yOff, total, amount, amountInit;
140 amountInit = radius * 2 + 1;
141 for (y = 0; y < height; ++y)
145 // Process entire window for first pixel
146 int size = MIN(radius + 1, width);
147 for ( kx = 0; kx < size; ++kx )
148 total += src[yOff + kx];
149 dst[yOff] = total / ( radius + 1 );
150 // Subsequent pixels just update window total
151 for ( x = 1; x < width; ++x )
154 // Subtract pixel leaving window
155 if ( x - radius - 1 >= 0 )
156 total -= src[yOff + x - radius - 1];
158 amount -= radius - x;
159 // Add pixel entering window
160 if ( x + radius < width )
161 total += src[yOff + x + radius];
163 amount -= radius - width + x;
164 dst[yOff + x] = total / amount;
169 /** Blurs \param src vertically. \See funtion blur. */
170 static void blurVertical( uint8_t *src, uint8_t *dst, int width, int height, int radius)
172 int x, y, ky, total, amount, amountInit;
173 amountInit = radius * 2 + 1;
174 for (x = 0; x < width; ++x)
177 int size = MIN(radius + 1, height);
178 for ( ky = 0; ky < size; ++ky )
179 total += src[x + ky * width];
180 dst[x] = total / ( radius + 1 );
181 for ( y = 1; y < height; ++y )
184 if ( y - radius - 1 >= 0 )
185 total -= src[( y - radius - 1 ) * width + x];
187 amount -= radius - y;
188 if ( y + radius < height )
189 total += src[( y + radius ) * width + x];
191 amount -= radius - height + y;
192 dst[y * width + x] = total / amount;
198 * Blurs the \param map using a simple "average" blur.
199 * \param map Will be blured; 1bpp
200 * \param width x dimension of channel stored in \param map
201 * \param height y dimension of channel stored in \param map
202 * \param radius blur radius
203 * \param passes blur passes
205 static void blur( uint8_t *map, int width, int height, int radius, int passes )
207 uint8_t *src = mlt_pool_alloc( width * height );
208 uint8_t *tmp = mlt_pool_alloc( width * height );
211 for ( i = 0; i < passes; ++i )
213 memcpy( src, map, width * height );
214 blurHorizontal( src, tmp, width, height, radius );
215 blurVertical( tmp, map, width, height, radius );
218 mlt_pool_release(src);
219 mlt_pool_release(tmp);
223 * Determines which points are located in the polygon and sets their value in \param map to \param value
224 * \param vertices points defining the polygon
225 * \param count number of vertices
226 * \param with x range
227 * \param height y range
228 * \param value value identifying points in the polygon
229 * \param map array of integers of the dimension width * height.
230 * The map entries belonging to the points in the polygon will be set to \param set * 255 the others to !set * 255.
232 static void fillMap( PointF *vertices, int count, int width, int height, int invert, uint8_t *map )
234 int nodes, nodeX[1024], pixelY, i, j, value;
236 value = !invert * 255;
237 memset( map, invert * 255, width * height );
239 // Loop through the rows of the image
240 for ( pixelY = 0; pixelY < height; pixelY++ )
243 * Build a list of nodes.
244 * nodes are located at the borders of the polygon
245 * and therefore indicate a move from in to out or vice versa
248 for ( i = 0, j = count - 1; i < count; j = i++ )
249 if ( (vertices[i].y > (double)pixelY) != (vertices[j].y > (double)pixelY) )
250 nodeX[nodes++] = (int)(vertices[i].x + (pixelY - vertices[i].y) / (vertices[j].y - vertices[i].y) * (vertices[j].x - vertices[i].x) );
252 qsort( nodeX, nodes, sizeof( int ), ncompare );
254 // Set map values for points between the node pairs to 1
255 for ( i = 0; i < nodes; i += 2 )
257 if ( nodeX[i] >= width )
260 if ( nodeX[i+1] > 0 )
262 nodeX[i] = MAX( 0, nodeX[i] );
263 nodeX[i+1] = MIN( nodeX[i+1], width );
264 memset( map + width * pixelY + nodeX[i], value, nodeX[i+1] - nodeX[i] );
270 /** Determines the point in the middle of the Bézier curve (t = 0.5) defined by \param p1 and \param p2
271 * using De Casteljau's algorithm.
273 static void deCasteljau( BPointF *p1, BPointF *p2, BPointF *mid )
275 struct PointF ab, bc, cd;
277 lerpHalf( &(p1->p), &(p1->h2), &ab );
278 lerpHalf( &(p1->h2), &(p2->h1), &bc );
279 lerpHalf( &(p2->h1), &(p2->p), &cd );
280 lerpHalf( &ab, &bc, &(mid->h1) ); // mid->h1 = abbc
281 lerpHalf( &bc, &cd, &(mid->h2) ); // mid->h2 = bccd
282 lerpHalf( &(mid->h1), &(mid->h2), &(mid->p) );
289 * Calculates points for the cubic Bézier curve defined by \param p1 and \param p2.
290 * Points are calculated until the squared distanced between neighbour points is smaller than 2.
291 * \param points Pointer to list of points. Will be allocted and filled with calculated points.
292 * \param count Number of calculated points in \param points
293 * \param size Allocated size of \param points (in elements not in bytes)
295 static void curvePoints( BPointF p1, BPointF p2, PointF **points, int *count, int *size )
297 double errorSqr = SQR( p1.p.x - p2.p.x ) + SQR( p1.p.y - p2.p.y );
299 if ( *size + 1 >= *count )
301 *size += (int)sqrt( errorSqr / 2 );
302 *points = mlt_pool_realloc( *points, *size * sizeof ( struct PointF ) );
305 (*points)[(*count)++] = p1.p;
311 deCasteljau( &p1, &p2, &mid );
313 curvePoints( p1, mid, points, count, size );
315 curvePoints( mid, p2, points, count, size );
317 (*points)[*(count)++] = p2.p;
322 static int filter_get_image( mlt_frame frame, uint8_t **image, mlt_image_format *format, int *width, int *height, int writable )
324 mlt_properties unique = mlt_frame_pop_service( frame );
326 int mode = mlt_properties_get_int( unique, "mode" );
329 if ( mode == MODE_RGB )
330 *format = mlt_image_rgb24;
331 int error = mlt_frame_get_image( frame, image, format, width, height, writable );
333 // Only process if we have no error and a valid colour space
337 struct PointF *points;
338 int bcount, length, count, size, i, j;
339 bpoints = mlt_properties_get_data( unique, "points", &length );
340 bcount = length / sizeof( BPointF );
342 for ( i = 0; i < bcount; i++ )
344 // map to image dimensions
345 bpoints[i].h1.x *= *width;
346 bpoints[i].p.x *= *width;
347 bpoints[i].h2.x *= *width;
348 bpoints[i].h1.y *= *height;
349 bpoints[i].p.y *= *height;
350 bpoints[i].h2.y *= *height;
355 points = mlt_pool_alloc( size * sizeof( struct PointF ) );
356 for ( i = 0; i < bcount; i++ )
358 j = (i + 1) % bcount;
359 curvePoints( bpoints[i], bpoints[j], &points, &count, &size );
364 length = *width * *height;
365 uint8_t *map = mlt_pool_alloc( length );
366 int invert = mlt_properties_get_int( unique, "invert" );
367 fillMap( points, count, *width, *height, invert, map );
369 int feather = mlt_properties_get_int( unique, "feather" );
370 if ( feather && mode != MODE_RGB )
371 blur( map, *width, *height, feather, mlt_properties_get_int( unique, "feather_passes" ) );
374 size = mlt_image_format_size( *format, *width, *height, &bpp );
376 uint8_t *q = *image + size;
384 // *format == mlt_image_rgb24
388 p[0] = p[1] = p[2] = 0;
395 case mlt_image_rgb24:
396 case mlt_image_rgb24a:
397 case mlt_image_opengl:
400 p[0] = p[1] = p[2] = map[i++];
404 case mlt_image_yuv422:
412 case mlt_image_yuv420p:
413 memcpy( p, map, length );
414 memset( p + length, 128, length / 2 );
423 case mlt_image_rgb24a:
424 case mlt_image_opengl:
425 switch ( mlt_properties_get_int( unique, "alpha_operation" ) )
437 p[3] = MAX( p[3], map[i] );
445 p[3] = MIN( p[3], map[i] );
453 p[3] = MIN( p[3] + map[i], 255 );
461 p[3] = MAX( p[3] - map[i], 0 );
469 alpha = mlt_frame_get_alpha_mask( frame );
470 switch ( mlt_properties_get_int( unique, "alpha_operation" ) )
473 memcpy( alpha, map, length );
476 for ( ; i < length; i++, alpha++ )
477 *alpha = MAX( map[i], *alpha );
480 for ( ; i < length; i++, alpha++ )
481 *alpha = MIN( map[i], *alpha );
484 for ( ; i < length; i++, alpha++ )
485 *alpha = MIN( *alpha + map[i], 255 );
488 for ( ; i < length; i++, alpha++ )
489 *alpha = MAX( *alpha - map[i], 0 );
497 mlt_pool_release( map );
500 mlt_pool_release( points );
506 /** Filter processing.
508 static mlt_frame filter_process( mlt_filter filter, mlt_frame frame )
510 mlt_properties properties = MLT_FILTER_PROPERTIES( filter );
511 int splineIsDirty = mlt_properties_get_int( properties, "_spline_is_dirty" );
512 char *modeStr = mlt_properties_get( properties, "mode" );
513 cJSON *root = mlt_properties_get_data( properties, "_spline_parsed", NULL );
515 if ( splineIsDirty || root == NULL )
517 // we need to (re-)parse
518 char *spline = mlt_properties_get( properties, "spline" );
519 root = cJSON_Parse( spline );
520 mlt_properties_set_data( properties, "_spline_parsed", root, 0, (mlt_destructor)cJSON_Delete, NULL );
521 mlt_properties_set_int( properties, "_spline_is_dirty", 0 );
530 if ( root->type == cJSON_Array )
535 count = json2BCurves( root, &points );
537 else if ( root->type == cJSON_Object )
543 mlt_position time, pos1, pos2;
544 time = mlt_frame_get_position( frame );
546 cJSON *keyframe = root->child;
547 cJSON *keyframeOld = keyframe;
552 while ( atoi( keyframe->string ) < time && keyframe->next )
554 keyframeOld = keyframe;
555 keyframe = keyframe->next;
558 pos1 = atoi( keyframeOld->string );
559 pos2 = atoi( keyframe->string );
561 if ( pos1 >= pos2 || time >= pos2 )
563 // keyframes in wrong order or before first / after last keyframe
564 count = json2BCurves( keyframe, &points );
573 int c1 = json2BCurves( keyframeOld, &p1 );
574 int c2 = json2BCurves( keyframe, &p2 );
577 double position = ( time - pos1 ) / (double)( pos2 - pos1 + 1 );
579 count = MIN( c1, c2 ); // additional points are ignored
580 points = mlt_pool_alloc( count * sizeof( BPointF ) );
581 for ( i = 0; i < count; i++ )
583 lerp( &(p1[i].h1), &(p2[i].h1), &(points[i].h1), position );
584 lerp( &(p1[i].p), &(p2[i].p), &(points[i].p), position );
585 lerp( &(p1[i].h2), &(p2[i].h2), &(points[i].h2), position );
588 mlt_pool_release( p1 );
589 mlt_pool_release( p2 );
597 mlt_properties unique = mlt_frame_unique_properties( frame, MLT_FILTER_SERVICE( filter ) );
598 mlt_properties_set_data( unique, "points", points, count * sizeof( BPointF ), (mlt_destructor)mlt_pool_release, NULL );
599 mlt_properties_set_int( unique, "mode", stringValue( modeStr, MODESTR, 3 ) );
600 mlt_properties_set_int( unique, "alpha_operation", stringValue( mlt_properties_get( properties, "alpha_operation" ), ALPHAOPERATIONSTR, 5 ) );
601 mlt_properties_set_int( unique, "invert", mlt_properties_get_int( properties, "invert" ) );
602 mlt_properties_set_int( unique, "feather", mlt_properties_get_int( properties, "feather" ) );
603 mlt_properties_set_int( unique, "feather_passes", mlt_properties_get_int( properties, "feather_passes" ) );
604 mlt_frame_push_service( frame, unique );
605 mlt_frame_push_get_image( frame, filter_get_image );
610 /** Constructor for the filter.
612 mlt_filter filter_rotoscoping_init( mlt_profile profile, mlt_service_type type, const char *id, char *arg )
614 mlt_filter filter = mlt_filter_new( );
617 filter->process = filter_process;
618 mlt_properties properties = MLT_FILTER_PROPERTIES( filter );
619 mlt_properties_set( properties, "mode", "alpha" );
620 mlt_properties_set( properties, "alpha_operation", "clear" );
621 mlt_properties_set_int( properties, "invert", 0 );
622 mlt_properties_set_int( properties, "feather", 0 );
623 mlt_properties_set_int( properties, "feather_passes", 1 );
625 mlt_properties_set( properties, "spline", arg );
627 mlt_events_listen( properties, filter, "property-changed", (mlt_listener)rotoPropertyChanged );