git.sesse.net Git - mlt/blob - src/modules/rotoscoping/filter_rotoscoping.c

   1 /*
   2  * rotoscoping.c -- keyframable vector based rotoscoping
   3  * Copyright (C) 2011 Till Theato <root@ttill.de>
   4  *
   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.
   9  *
  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.
  14  *
  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.
  18  */
  19
  20 #include <framework/mlt_filter.h>
  21 #include <framework/mlt_frame.h>
  22
  23 #include "cJSON.h"
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <math.h>
  28 #include <string.h>
  29
  30 #define MAX( x, y ) x > y ? x : y
  31 #define MIN( x, y ) x < y ? x : y
  32 #define SQR( x ) ( x ) * ( x )
  33
  34 /** x, y tuple with double precision */
  35 typedef struct PointF
  36 {
  37     double x;
  38     double y;
  39 } PointF;
  40
  41 typedef struct BPointF
  42 {
  43     struct PointF h1;
  44     struct PointF p;
  45     struct PointF h2;
  46 } BPointF;
  47
  48 enum MODES { MODE_RGB, MODE_ALPHA, MODE_MATTE };
  49 const char *MODESTR[3] = { "rgb", "alpha", "matte" };
  50
  51 enum ALPHAOPERATIONS { ALPHA_CLEAR, ALPHA_MAX, ALPHA_MIN, ALPHA_ADD, ALPHA_SUB };
  52 const char *ALPHAOPERATIONSTR[5] = { "clear", "max", "min", "add", "sub" };
  53
  54
  55 /** Returns the index of \param string in \param stringList.
  56  * Useful for assigning string parameters to enums. */
  57 int stringValue( const char *string, const char **stringList, int max )
  58 {
  59     int i;
  60     for ( i = 0; i < max; i++ )
  61         if ( strcmp( stringList[i], string ) == 0 )
  62             return i;
  63     return 0;
  64 }
  65
  66 /** Linear interp */
  67 void lerp( const PointF *a, const PointF *b, PointF *result, double t )
  68 {
  69     result->x = a->x + ( b->x - a->x ) * t;
  70     result->y = a->y + ( b->y - a->y ) * t;
  71 }
  72
  73 /** Linear interp. with t = 0.5
  74  * Speed gain? */
  75 void lerpHalf( const PointF *a, const PointF *b, PointF *result )
  76 {
  77     result->x = a->x + ( b->x - a->x ) * .5;
  78     result->y = a->y + ( b->y - a->y ) * .5;
  79 }
  80
  81 /** Helper for using qsort with an array of integers. */
  82 int ncompare( const void *a, const void *b )
  83 {
  84     return *(const int*)a - *(const int*)b;
  85 }
  86
  87 /** Turns a json array with two children into a point (x, y tuple). */
  88 void jsonGetPoint( cJSON *json, PointF *point )
  89 {
  90     if ( cJSON_GetArraySize( json ) == 2 )
  91     {
  92         point->x = json->child->valuedouble;
  93         point->y = json->child->next->valuedouble;
  94     }
  95 }
  96
  97 /**
  98  * Turns the array of json elements into an array of Bézier points.
  99  * \param array cJSON array. values have to be Bézier points: handle 1, point , handl2
 100  *              ( [ [ [h1x, h1y], [px, py], [h2x, h2y] ], ... ] )
 101  * \param points pointer to array of points. Will be allocated and filled with the points in \param array
 102  * \return number of points
 103  */
 104 int json2BCurves( cJSON *array, BPointF **points )
 105 {
 106     int count = cJSON_GetArraySize( array );
 107     cJSON *child = array->child;
 108     *points = mlt_pool_alloc( count * sizeof( BPointF ) );
 109
 110     int i = 0;
 111     do
 112     {
 113         if ( cJSON_GetArraySize( child ) == 3 )
 114         {
 115             jsonGetPoint( child->child , &(*points)[i].h1 );
 116             jsonGetPoint( child->child->next, &(*points)[i].p );
 117             jsonGetPoint( child->child->next->next, &(*points)[i].h2 );
 118             i++;
 119         }
 120     } while ( ( child = child->next ) );
 121
 122     if ( i < count )
 123         *points = mlt_pool_realloc( *points, i * sizeof( BPointF ) );
 124
 125     return i;
 126 }
 127
 128 /**
 129  * Determines which points are located in the polygon and sets their value in \param map to \param value
 130  * \param vertices points defining the polygon
 131  * \param count number of vertices
 132  * \param with x range
 133  * \param height y range
 134  * \param value value identifying points in the polygon
 135  * \param map array of integers of the dimension width * height.
 136  *            The map entries belonging to the points in the polygon will be set to \param set * 255 the others to !set * 255.
 137  */
 138 void fillMap( PointF *vertices, int count, int width, int height, uint8_t set, uint8_t *map )
 139 {
 140     int nodes, nodeX[1024], pixelY, i, j, offset;
 141
 142     // Loop through the rows of the image
 143     for ( pixelY = 0; pixelY < height; pixelY++ )
 144     {
 145         offset = width * pixelY;
 146         /*
 147          * Build a list of nodes.
 148          * nodes are located at the borders of the polygon
 149          * and therefore indicate a move from in to out or vice versa
 150          */
 151         nodes = 0;
 152         for ( i = 0, j = count - 1; i < count; j = i++ )
 153             if ( (vertices[i].y > (double)pixelY) != (vertices[j].y > (double)pixelY) )
 154                 nodeX[nodes++] = (int)(vertices[i].x + (pixelY - vertices[i].y) / (vertices[j].y - vertices[i].y) * (vertices[j].x - vertices[i].x) );
 155
 156         qsort( nodeX, nodes, sizeof( int ), ncompare );
 157
 158         if ( nodes && nodeX[0] > 0 )
 159             for ( j = 0; j < nodeX[0] - 1; j++ )
 160                 map[offset + j] = !set * 255;
 161         else if ( !nodes )
 162             for ( j = 0; j < width; j++ )
 163                 map[offset + j] = !set * 255;
 164
 165         // Set map values for points between the node pairs to 1
 166         for ( i = 0; i < nodes - 1; i++ )
 167         {
 168             if ( nodeX[i] >= width )
 169                 break;
 170
 171             if ( nodeX[i+1] > 0 )
 172             {
 173                 nodeX[i] = MAX( 0, nodeX[i] );
 174                 nodeX[i+1] = MIN( nodeX[i+1], width );
 175                 if ( i % 2 )
 176                     for ( j = nodeX[i]; j < nodeX[i+1]; j++ )
 177                         map[offset + j] = !set * 255;
 178                 else
 179                     for ( j = nodeX[i]; j <= nodeX[i+1]; j++ )
 180                         map[offset + j] = set * 255;
 181             }
 182         }
 183
 184         if ( nodes && nodeX[nodes-1] < width )
 185             for ( j = nodeX[nodes-1] + 1; j < width; j++ )
 186                 map[offset + j] = !set * 255;
 187     }
 188 }
 189
 190 /** Determines the point in the middle of the Bézier curve (t = 0.5) defined by \param p1 and \param p2
 191  * using De Casteljau's algorithm.
 192  */
 193 void deCasteljau( BPointF *p1, BPointF *p2, BPointF *mid )
 194 {
 195     struct PointF ab, bc, cd, abbc, bccd, final;
 196
 197     lerpHalf( &(p1->p), &(p1->h2), &ab );
 198     lerpHalf( &(p1->h2), &(p2->h1), &bc );
 199     lerpHalf( &(p2->h1), &(p2->p), &cd );
 200     lerpHalf( &ab, &bc, &abbc );
 201     lerpHalf( &bc, &cd, &bccd );
 202     lerpHalf( &abbc, &bccd, &final );
 203
 204     p1->h2 = ab;
 205     p2->h1 = cd;
 206     mid->h1 = abbc;
 207     mid->p = final;
 208     mid->h2 = bccd;
 209 }
 210
 211 /**
 212  * Calculates points for the cubic Bézier curve defined by \param p1 and \param p2.
 213  * Points are calculated until the squared distanced between neighbour points is smaller than \param errorSquared.
 214  * \param points Pointer to list of points. Will be allocted and filled with calculated points.
 215  * \param count Number of calculated points in \param points
 216  * \param size Allocated size of \param points (in elements not in bytes)
 217  */
 218 void curvePoints( BPointF p1, BPointF p2, PointF **points, int *count, int *size, const double *errorSquared )
 219 {
 220     double errorSqr = SQR( p1.p.x - p2.p.x ) + SQR( p1.p.y - p2.p.y );
 221
 222     if ( *size + 1 >= *count )
 223     {
 224         *size += (int)sqrt( errorSqr / *errorSquared );
 225         *points = mlt_pool_realloc( *points, *size * sizeof ( struct PointF ) );
 226     }
 227
 228     (*points)[(*count)++] = p1.p;
 229
 230     if ( errorSqr <= *errorSquared )
 231         return;
 232
 233     BPointF mid;
 234     deCasteljau( &p1, &p2, &mid );
 235
 236     curvePoints( p1, mid, points, count, size, errorSquared );
 237
 238     curvePoints( mid, p2, points, count, size, errorSquared );
 239
 240     (*points)[*(count)++] = p2.p;
 241 }
 242
 243 /** Do it :-).
 244 */
 245 static int filter_get_image( mlt_frame this, uint8_t **image, mlt_image_format *format, int *width, int *height, int writable )
 246 {
 247     mlt_properties properties = MLT_FRAME_PROPERTIES( this );
 248
 249     // Get the image
 250     *format = mlt_image_rgb24a;
 251     int error = mlt_frame_get_image( this, image, format, width, height, 1 );
 252
 253     // Only process if we have no error and a valid colour space
 254     if ( !error )
 255     {
 256         BPointF *bpoints;
 257         struct PointF *points;
 258         int bcount, length, count, size, i, j;
 259         bpoints = mlt_properties_get_data( properties, "points", &length );
 260         bcount = length / sizeof( BPointF );
 261
 262         for ( i = 0; i < bcount; i++ )
 263         {
 264             // map to image dimensions
 265             bpoints[i].h1.x *= *width;
 266             bpoints[i].p.x  *= *width;
 267             bpoints[i].h2.x *= *width;
 268             bpoints[i].h1.y *= *height;
 269             bpoints[i].p.y  *= *height;
 270             bpoints[i].h2.y *= *height;
 271         }
 272
 273         double errorSqr = (double)SQR( mlt_properties_get_int( properties, "precision" ) );
 274         count = 0;
 275         size = 1;
 276         points = mlt_pool_alloc( size * sizeof( struct PointF ) );
 277         for ( i = 0; i < bcount; i++ )
 278         {
 279             j = (i + 1) % bcount;
 280             curvePoints( bpoints[i], bpoints[j], &points, &count, &size, &errorSqr );
 281         }
 282
 283         if ( count )
 284         {
 285             uint8_t *map = mlt_pool_alloc( *width * *height );
 286             uint8_t setPoint = !mlt_properties_get_int( properties, "invert" );
 287             fillMap( points, count, *width, *height, setPoint, map );
 288
 289             uint8_t *p = *image;
 290             uint8_t *q = *image + *width * *height * 4;
 291
 292             switch ( mlt_properties_get_int( properties, "mode" ) )
 293             {
 294             case MODE_RGB:
 295                 while ( p != q )
 296                 {
 297                     if ( !map[(p - *image) / 4] )
 298                         p[0] = p[1] = p[2] = 0;
 299                     p += 4;
 300                 }
 301                 break;
 302             case MODE_ALPHA:
 303                 switch ( mlt_properties_get_int( properties, "alpha_operation" ) )
 304                 {
 305                 case ALPHA_CLEAR:
 306                     while ( p != q )
 307                     {
 308                         p[3] = map[(p - *image) / 4];
 309                         p += 4;
 310                     }
 311                     break;
 312                 case ALPHA_MAX:
 313                     while ( p != q )
 314                     {
 315                         p[3] = MAX( map[(p - *image) / 4], p[3] );
 316                         p += 4;
 317                     }
 318                     break;
 319                 case ALPHA_MIN:
 320                     while ( p != q )
 321                     {
 322                         p[3] = MIN( map[(p - *image) / 4], p[3] );
 323                         p += 4;
 324                     }
 325                     break;
 326                 case ALPHA_ADD:
 327                     while ( p != q )
 328                     {
 329                         p[3] = MIN( p[3] + map[(p - *image) / 4], 255 );
 330                         p += 4;
 331                     }
 332                     break;
 333                 case ALPHA_SUB:
 334                     while ( p != q )
 335                     {
 336                         p[3] = MAX( p[3] - map[(p - *image) / 4], 0 );
 337                         p += 4;
 338                     }
 339                     break;
 340                 }
 341                 break;
 342             case MODE_MATTE:
 343                 while ( p != q )
 344                 {
 345                     p[0] = p[1] = p[2] = map[(p - *image) / 4];
 346                     p += 4;
 347                 }
 348                 break;
 349             }
 350
 351             mlt_pool_release( map );
 352         }
 353
 354         mlt_pool_release( points );
 355     }
 356
 357     return error;
 358 }
 359
 360 /** Filter processing.
 361 */
 362 static mlt_frame filter_process( mlt_filter this, mlt_frame frame )
 363 {
 364     mlt_properties properties = MLT_FILTER_PROPERTIES( this );
 365     mlt_properties frameProperties = MLT_FRAME_PROPERTIES( frame );
 366     char *spline = mlt_properties_get( properties, "spline" );
 367     char *modeStr = mlt_properties_get( properties, "mode" );
 368
 369     cJSON *root = cJSON_Parse( spline );
 370
 371     if ( root == NULL )
 372         return frame;
 373
 374     BPointF *points;
 375     int count, i;
 376
 377     if ( root->type == cJSON_Array )
 378     {
 379         /*
 380          * constant (over time)
 381          */
 382         count = json2BCurves( root, &points );
 383     }
 384     else
 385     {
 386         /*
 387          * keyframes
 388          */
 389
 390         mlt_position time, pos1, pos2;
 391         time = mlt_frame_get_position( frame );
 392
 393         cJSON *keyframe = root->child;
 394         cJSON *keyframeOld = NULL;
 395         while ( atoi( keyframe->string ) < time && keyframe->next )
 396         {
 397             keyframeOld = keyframe;
 398             keyframe = keyframe->next;
 399         }
 400
 401         if ( keyframeOld == NULL ) {
 402             // parameter has only 1 keyframe or we are before the 1. keyframe
 403             keyframeOld = keyframe;
 404         }
 405
 406         if ( !keyframe )
 407         {
 408             if ( keyframeOld )
 409             {
 410                 // parameter malformed
 411                 keyframe = keyframeOld;
 412             }
 413             else if ( root->child )
 414             {
 415                 // parameter malformed
 416                 keyframe = root->child;
 417                 keyframeOld = keyframe;
 418             }
 419             else
 420             {
 421                 // json object has no children
 422                 cJSON_Delete( root );
 423                 return frame;
 424             }
 425         }
 426
 427         pos2 = atoi( keyframe->string );
 428         pos1 = atoi( keyframeOld->string );
 429
 430         if ( pos1 >= pos2 || time >= pos2 )
 431         {
 432             // keyframes in wrong order or after last keyframe
 433             count = json2BCurves( keyframe, &points );
 434         }
 435         else
 436         {
 437             /*
 438              * pos1 < time < pos2
 439              */
 440
 441             BPointF *p1, *p2;
 442             int c1, c2;
 443             c1 = json2BCurves( keyframeOld, &p1 );
 444             c2 = json2BCurves( keyframe, &p2 );
 445
 446             if ( c1 > c2 )
 447             {
 448                 // number of points decreasing from p1 to p2; we can't handle this yet
 449                 count = c2;
 450                 points = mlt_pool_alloc( count * sizeof( BPointF ) );
 451                 memcpy( points, p2, count * sizeof( BPointF ) );
 452                 mlt_pool_release( p1 );
 453                 mlt_pool_release( p2 );
 454             }
 455             else
 456             {
 457                 // range 0-1
 458                 double position = ( time - pos1 ) / (double)( pos2 - pos1 + 1 );
 459
 460                 count = c1;  // additional points in p2 are ignored
 461                 points = mlt_pool_alloc( count * sizeof( BPointF ) );
 462                 for ( i = 0; i < count; i++ )
 463                 {
 464                     lerp( &(p1[i].h1), &(p2[i].h1), &(points[i].h1), position );
 465                     lerp( &(p1[i].p), &(p2[i].p), &(points[i].p), position );
 466                     lerp( &(p1[i].h2), &(p2[i].h2), &(points[i].h2), position );
 467                 }
 468
 469                 mlt_pool_release( p1 );
 470                 mlt_pool_release( p2 );
 471             }
 472         }
 473     }
 474     cJSON_Delete( root );
 475
 476     int length = count * sizeof( BPointF );
 477
 478     mlt_properties_set_data( frameProperties, "points", points, length, (mlt_destructor)mlt_pool_release, NULL );
 479     mlt_properties_set_int( frameProperties, "mode", stringValue( modeStr, MODESTR, 3 ) );
 480     mlt_properties_set_int( frameProperties, "alpha_operation", stringValue( mlt_properties_get( properties, "alpha_operation" ), ALPHAOPERATIONSTR, 5 ) );
 481     mlt_properties_set_int( frameProperties, "invert", mlt_properties_get_int( properties, "invert" ) );
 482     mlt_properties_set_int( frameProperties, "precision", mlt_properties_get_int( properties, "precision" ) );
 483     mlt_frame_push_get_image( frame, filter_get_image );
 484
 485     return frame;
 486 }
 487
 488 /** Constructor for the filter.
 489 */
 490 mlt_filter filter_rotoscoping_init( mlt_profile profile, mlt_service_type type, const char *id, char *arg )
 491 {
 492         mlt_filter this = mlt_filter_new( );
 493         if ( this != NULL )
 494         {
 495                 this->process = filter_process;
 496                 mlt_properties_set( MLT_FILTER_PROPERTIES( this ), "mode", "rgb" );
 497                 mlt_properties_set( MLT_FILTER_PROPERTIES( this ), "alpha_operation", "clear" );
 498                 mlt_properties_set_int( MLT_FILTER_PROPERTIES( this ), "invert", 0 );
 499                 mlt_properties_set_int( MLT_FILTER_PROPERTIES( this ), "precision", 1 );
 500                 if ( arg != NULL )
 501                     mlt_properties_set( MLT_FILTER_PROPERTIES( this ), "spline", arg );
 502         }
 503         return this;
 504 }